学位論文題名 様相論理および可能性理論に基づく 知識

博士（工学）工藤康生
学 位 論 文 題 名
様相論理および可能性理論に基づく
知識ベース管理の定式化に関する研究
学位論文内容の要旨
情報 処理 技術 の高 速化 に伴 って ，大 量の 情 報を 蓄積 ，処 理す る技 術の 必要 性が
高 ま って いる 。蓄 積さ れた 情報 を知 識ベ ース と して 扱う ため には ，知 識ベ ース を管
理 す る機 能が 必要 とな るが ，知 識ベ ース およ び その 管理 シス テム に関 する 研究 は理
論 的 定式 化と 実用 的応 用の 両面 から 行わ れて い る。 知識 ベー ス管 理に 関す る問 題の
ー っ とし て， 知識 ベー スに 対し て情 報の 追加 ， 削除 など の操 作を 施し た場 合に ，い
か に して 知識 ベー スの 整合 性を 保っ かが 挙げ ら れる 。所 有す る情 報の 整合 性に 関す
る 議 論は 論理 学や 哲学 ，人 工知 能な どの 分野 で 行わ れて いる が， この 問題 を論 理や
確 率 ，フ んジ ィ測 度な どの 枠組 で定 式化 し， そ の理 論的 性質 を扱 う研 究は 信念 変更
の理論と 呼ばれている。
論 理 的 枠 組 に お け る 信 念 変 更 は ， 信 念 修 正 と 信 念 更 新 と に大 別さ れる 。信 念修
正 は ，得 られ た新 情報 が所 有す る情 報と 論理 的 に矛 盾す る場 合に ，所 有す る情 報に
間 違 いが ある とみ なし て， その 誤り を新 情報 に 基い て訂 正し ，論 理的 整合 性を 保と
う と する 操作 であ る。 これ に対 して 信念 更新 は ，現 実世 界が 動的 に変 化し たこ とに
よ っ て， 現実 世界 の状 況と 所有 する 情報 とが 食 い違 うよ うに なっ たと みな して ，そ
の よ うな 世界 の変 化を 所有 する 情報 に反 映さ せ る操 作で ある 。し かし ，こ れら の方
法 は 本質 的に 異な る操 作と みな され てお り， 信 念修 正と 信念 更新 を統 一的 に扱 った
研 究 は行 われ てお らず ，こ れら の操 作に つい て の関 連性 は明 らか にさ れて いな い。
数値 的な 枠組 での 信念 変更 の定 式化 とし て は， フん ジィ 測度 の一 種で ある 可能
性 理 論の 枠組 での 定式 化が 試み られ てい る。 可 能性 理論 の枠 組で は， 所有 する 情報
を可能な 状況の集合から閉区間［0
，1
］への可能性分布と呼ばれ る関数で数値的に表現
す る 。従 来の 研究 では ，信 念修 正の 操作 と， 信 念更 新の 操作 の一 部が 定式 化さ れて
い る 。し かし ，信 念更 新の 従来 の定 式化 には 不 十分 な点 が多 く， また ，信 念更 新の
他の操作 についてはまだ定式化されていない。
本論 文で は， これ らの 問題 に基 いて ，信 念 修正 と信 念変 更の 操作 を統 一的 な枠
組 で 扱い ，こ れら の操 作の 関連 性を 明ら かに す る。 また ，信 念変 更を それ ぞれ 様相
論 理 と 可 能 性 理 論 に 基 い て 定 式 化 し ， そ の 性 質 に つ い て考 察 す る 。
第 1章 で は ， 序 論 と し て 研 究の 背景 と本 研 究の 位置 づけ およ び目 的に つい て述
べている 。
第 2章 で は ， 本 論 文 の 数 学 的準 備と して ， 様相 論理 とフ んジ ィ測 度の 一種 であ
る 可 能性 理論 につ いて 概要 をま とめ てい る。 ま ず， 様相 論理 の証 明論 と可 能世 界に
基づく意 味論， 特にクリプキ・モデルについて説明する。次に，フんジィ測度に二二冫
い て 述 ベ ， そ の 特 別な 場 合で ある 可 能性 理 論に つ いて 説 明す る。
第3章 で は， Alch
orro
nら が 提案 し た 信念 修 正 とKats
uno a
nd M
en
de
lz
on
が 提案
した 信 念 更新 に つ いて ， そ の 関連 性 を 明らか にする。 まず， 信念修正 と信念 更新に
つい て 概 略を 述 べ ，Katsu
no a
nd M
ende
lzon
に よ る 更新 と 消 去 の操 作に ついて， こ
れら の 操 作を 特 徴 づけ る メ 夕 論理 的 な 公準に 不十分な 点があ ることを 指摘し ，その
不備 を 補 う。 次 に ，更 新 か ら 消去 を 定 義する 同ー性と 消去か ら更新を 定義す る同一
性を そ れ ぞれ 提 案 し， 不 備 を 補っ た 公 準に基 づ＜更新 と消去 について ，相互 に定義
可能 な 性 質が 成 り 立つ こ と を 示す 。 更 に，修 正および 縮小か ら消去を 定義す る同一
性を 提 案 し， こ れ らの 同 一 性 に基 づ く 相互定 義につい て，可 換な性質 が成り 立つこ
とを 示 す 。相 互 定 義に 関 す る 可換 性 は ，信念 変更を行 う種々 の操作間 の関連 を明ら
かにする 6
第 4章で は ， 信念 変 更 の 操作 の 中 で特 に 更 新と 消 去 に着 目 し ，こ れら の操作 を様
相論 理 ， 具体 的 に はVakar
elov
が 提 案 した 矢 印 の様 相 論 理を ， 矢 印の 間の順 序関係
につ い て 扱え る よ うに 拡 張 し た順 序 を 持つ矢 印の様相 論理に 基いて定 式化す る。ま
ず， 有 向 グラ フ の 構造 的 な 性 質と 矢 印 の間の 順序関係 を表現 する，順 序を持 つ矢印
の様 相 論 理の フ レ ーム と モ デ ル（ 以 下 ，OA
モデ ル）を 提案する 。また， 順序を 持つ
矢 印 の 様 相 論 理 体 系 OAL（ ordered arrow lo
gic）を 提 案 し， OAL
は す べ ての OAモ
デルのク ラスに 対して健 全かつ 完全であ ること を示す。 次に，更 新と消去の操作を，
所有 す る 情報 を 表 す論 理 文 の 集合 の そ れぞ れ の モデ ル wに対 し て ．り におい て最も
「起 こ り やす い」 状態遷 移を選択 する操 作に基づ ぃて定 義すると ，それぞ れKa
ts
un
o
a
nd M
ende
lzonの更 新 の 性質 お よ び消 去 の 性質 を 満 たす こ と を示 す 。更 に，更新 と
消去 の 操 作お よ び それ ぞ れ の 操作 が 満 たす べ き 性質 は ， O
ALの 論理 文と して明 示的
に表 現 で きる こ と を示 す 。 こ のこ と は ，更 新 と 消去 の 操 作は OAL
に おけ る論理 演算
として表 現でき ることを 意味す る。
第 5章で は ， 可能 性 理 論 の枠 組 に おけ る 信 念更 新 の 厳密 な 定 式化 を行 う。ま ず，
D
uboi
s an
d Pra
deに よる 可 能 性理 論 に おける 更新の 定式化で は，更 新の結果 が常に
構成 で き ると は 限 らな い こ と を指 摘 し ，可能 性理論に おける 更新の操 作を正 確に再
定式 化 す るこ と で この 問 題 を 解決 す る 。また ，論理的 枠組に おける消 去の操 作およ
び対 称 的 消去 の 操 作を 可 能 性 理論 の 枠 組で新 たに定式 化し， その性質 につい て考察
する。更 に，不 確実な情 報に基 づく信念 更新を 提案し， その性質 について考察する。
特に ， 不 確実 な 情 報に 基 づ く 信念 更 新 は，特 殊な場合 として 確実な情 報に基 づく信
念修 正 と 信念 更 新 ，お よ び 不 確実 な 情 報に基 づ＜信念 修正を 含んでお り，よ り一般
的な信念 変更の 枠組であ ること を示す。
第6章 で は， 結 論 と して ， 本 論文 で 得 られ た 結 果に つ い て考 察 し， 今後の研 究
の方 向 性 と課 題 を 示す 。 ま た ，本 論 文 での主 な定理お よび補 題，命題 につい て，証
明を付録 として 添付して いる。
学位論文審査の要旨
主査
副査
副査
副査
教 授
伊
教 授
新
教 授
宮
助教授
村
達 惇
保 勝
腰政明
井哲也
学 位 論 文 題 名
様相論理および可能性理論に基づく
知識ベース管理の定式化に関する研究
知 識 ベ ー ス に 含 ま れ る 情 報 を 変 更 し た 場 合 に 知 識 ベ ー ス の 整 合 性を 保っ とい う
問 題 は ， 人 工知 能の 分野 で基 礎的 理論 と 工学 的応 用の 両面 から 研究 され てい る。 こ
の 問 題 を 論 理， 確率 およ びフ んジ ィ測 度 に基 づぃ て定 式化 し， その 性質 を扱 う研 究
は 信 念 変 更 の理 論と して 扱わ れて おり ， これ は新 たに 得た 情報 に基 いて 知識 ベー ス
に 論 理 矛 盾 が生 じた 場合 に訂 正を 行う 信 念修 正と いう 課題 と， 現実 世界 の動 的な 変
化 を 知 識 ベ ー スに 反 映 さ せ る 信 念 更 新 と いう 課 題 の ニ つ に 分 かれる 。
論 理 的 枠 組に 基づ く従 来の 研究 では ， これ らニ つの 課題 は本 質的 に異 なる 操作 と
み なさ れて おり ，両 者の 関連 性は 追究 されていな かった。これは確率およびファシィ
測 度 に 基 づ く研 究に おい ても 同様 であ り ，可 能性 理論 を用 いた 信念 修正 と信 念更 新
の 操 作 の 一 部が 構築 され てい るが ，こ れ らニ つの 課題 を包 括的 に扱 うに は至 って お
ら ず ， こ れ らの 操作 は知 識ベ ース 管理 に 関す る応 用研 究に おい て活 用さ れる 段階 に
至 って いな い。
本 論 文 は ，知 識ベ ース の整 合性 を保 つ 様々 な操 作の 統一 的な 取り 扱い と情 報工 学
に お け る 応 用を 目的 とし て， 知識 ベー ス 管理 にお ける 信念 変更 を記 述す る公 準を 定
式 化 し ， そ れぞ れの 操作 の関 連性 を明 ら かに して いる 。第 一段 階と して ，古 典命 題
論 理 に 基 づ ぃて ，知 識ベ ース の整 合性 を 保つ 様々 な操 作の 関連 性を 明ら かに し， 第
二 段 階 と し て， 従来 の研 究で 一部 が構 築 され てい る可 能性 理論 に基 づく 信念 変更 の
厳 密 な 定 式 化を 行い ，統 一的 な枠 組の 構 築を 行っ てい る。 第三 段階 とし て， 様相 論
理に 基づ く知 識ベ ース 管理 の定 式化 およ び統一的な枠組の構築を行っている。
第 1章 で は ， 本 論 文 の 背 景 ， 目 的 お よ び 構 成 に つ い て 述 ぺ て い る 。
第 2章 で は ， 様 相 論 理 お よ び 可 能 性 理論 につ いて ，本 研究 に用 いる 成果 を抽 出
し て 整 理 す る と と も に， 信念 変更 に関 する 従来 の研 究の 概要 を述ぺ てい る。
-6
98―
第3章 で は ，古 典 命 題論 理 に 基づ ぃ て ，知 識 ベ ース の 整 合性 を 保 つニつ の課題
であ る 信 念修 正 お よ び信 念 更 新の 関 連 性を 明らか にして いる。ま ず，信 念更新の 操
作の 一 部 であ る 更 新 操作 お よ び消 去 操 作に ついて ，消去 操作を記 述する 既存の公 準
の不 備 を 解消 し ， そ れら ニ つ の操 作 を 相互 に定義 するこ とが可能 である ことを証 明
した 。 更 に， 信 念 修 正の 操 作 であ る 修 正操 作およ び縮小 操作を用 いて， 更新操作 お
よび 消 去 操作 を 構 成 する こ と が可 能 で ある ことを 証明し ，知識ベ ースの 整合性を 保
つ様々 な操作の 関連性を 明らか にしてい る。
第 4章で は ， 様 相論 理 に 基づ く 知 識ベ ー ス 管理 の 定 式化 お よ び統 一 的な 枠組の構
築を 行 っ てい る 。 ま ず， 状 態 遷移 図 の 構造 を表現 する矢 印の様相 論理に ついて， 状
態遷 移 の 発生 に 関 す る選 択 の 順序 を 与 えて 論理を 拡張し ，この論 理に意 味論を与 え
るモ デ ル を考 案 し て ，そ れ を 詳述 し て いる 。この 拡張し た論理が 全ての モデルの ク
ラス に 対 して 健 全 か つ完 全 で ある こ と を証 明する ととも に，知識 ベース の整合性 を
保つ操 作を統一 的に扱う 枠組を 構築して いる。
第 5章 で は ， 従 来 の 研 究 で 一 部 が 構 築 さ れ て いた 可 能 性理 論 に 基づ く 信 念変 更
の厳 密 な 定式 化 を 行 い， そ れ らを 統 一 的に 扱う枠 組を構 築してい る。ま ず，可能 性
理論 に お ける 更 新 操 作に つ い て， 従 来 の定 式化の 不備を 解消し， 消去操 作と対称 的
消去 操 作 を新 た に 考 案し て い る。 更 に ，不 確実な 情報に 基づく信 念更新 という概 念
を創 出 し ，可 能 性 理 論に 基 づ く信 念 変 更の それぞ れの操 作はその 新しい 概念に基 づ
いて取 り扱うこ とができ ること を論じて いる。
第6章 で は ，本 論 文 のま と め およ び 今 後の 課 題 につ い て 述べ て い る。ま た，本
論 文 で 示 さ れ て い る 定理 お よ び補 題 に つい て ， 証 明を 付 録 とし て 添 付し て い る。
これ を 要 す るに ， 著 者は ， 知 識ベ ー スの 整合性 を保つ様 々な操作 の関連 性を明
らか に し ，様 相 論 理 およ び 可 能性 理 論 に基 づぃて それら の操作を 統一的 に扱う枠 組
を構 築 し ，知 識 ベ ー ス管 理 へ の応 用 に 関す る新知 見を得 たもので あり， 情報工学 の
発展に 貢献する ところ大 なるも のがある 。
よって 著者は， 北海道大学博士（工学）の学位を授与される資格あるものと認める。
― 699―