主として論理による知識表現の代表 Ｐｒｏｌｏｇによる表現

Presentation on theme: "主として論理による知識表現の代表 Ｐｒｏｌｏｇによる表現"— Presentation transcript:

1 主として論理による知識表現の代表 Ｐｒｏｌｏｇによる表現
３．論理による知識表現 主として論理による知識表現の代表 Ｐｒｏｌｏｇによる表現

2 ３．１ 論理による知識表現 ①形式化が容易であり、直感的理解と一致することが多い。 ②図表に比べ、イメージに訴えない。
３．１　論理による知識表現 ①形式化が容易であり、直感的理解と一致することが多い。 ②図表に比べ、イメージに訴えない。 ③記述が厳密であり、証明を機械的に行うことができる。 ④記述方法が単純であり、新しい事実を追加することが容易である。 ⑤記述をどう利用するか、どう蓄積するかを決定する部分がない。

3 知識表現上の注意 我々は、 語ることができるより、 もっと多くのことを知っている。 ひとつの表現で 全てを言い尽くせたとは言えない。

4 命題論理、述語論理の限界 ① 必然性、可能性の概念の欠如 ② 形式化が容易な限られた範囲の推論 ↓
①　必然性、可能性の概念の欠如 ②　形式化が容易な限られた範囲の推論 　　　　　　　　　　↓ 形式論理学により、形式的に妥当とされる推論が論理的推論の全てではない。 　　　　　　　　　…しかし… かなり成功をおさめた理論化のひとつ

5 言葉に敏感に！！ Ａ：木村は金に困らなければ、働かない。 Ｂ：木村は働かなければ、金に困る。 Ｐ：金に困る Ｑ：働かない Ａ： ～Ｐ → Ｑ
Ａ：　～Ｐ　→　Ｑ Ｂ：　Ｑ　　→　Ｐ ～Ｐ　→　Ｑ　→　Ｐ ∴～Ｐ　→　Ｐ　？ ｉｆ…ｔｈｅｎ　は、しばしば Ｗｈｉｌｅ　の替わりに使用される Ｐ：金に困る Ｑ：働かない

6 （例）誘導推論 Ｐ Ｑ ～Ｐ ～Ｑ ～Ｐ→Ｑ Ｐ→～Ｑ １ １ ０ ０ １ ０ １ ０ ０ １ １ １ ０ １ １ ０ １ １
金を出さなければ、殺すぞ ～Ｐ　→　Ｑ 　　　　　　　↓ 金を出せば、殺さない Ｑ　　→　～Ｑ Ｐ Ｑ ～Ｐ ～Ｑ ～Ｐ→Ｑ Ｐ→～Ｑ １ １ 　０ 　０ 　　１ 　　０ １ ０ 　０ 　１ 　　１ 　　１ ０ １ 　１ 　０ 　　１ 　　１ ０ ０ 　１ 　１ 　　０ 　　１

7 （例）推移的性質のモデルの妥当性 右 右 ＡはＢの右にある ∩ ＢはＣの右にある → ＡはＣの右にある 基点自身が方向性を持つ
ＡはＢの右にある　∩　ＢはＣの右にある　→　ＡはＣの右にある 基点自身が方向性を持つ ＡさんはＢさんの右にいます ＢさんはＣさんの右にいます しかし、 ＡさんはＢさんの右にいません はて？ 右 右

8 （例）擬似条件 Ｐ Ｑ Ｓ ∩ ①暑ければ、昨日ビールを買ったよ。 ②のどが渇いているなら、 ビールが冷蔵庫に入っているよ。
暑い のどが渇く 何か飲みたい Ｓ ∩ ビールを飲む 昨日、ビールを買った ビールが冷蔵庫に入っている ①暑ければ、昨日ビールを買ったよ。 ②のどが渇いているなら、 ビールが冷蔵庫に入っているよ。 ③ビールが冷蔵庫に入ってるなら、 さっきからのどが渇いてしょうがないんだ

9 （例）法則的解釈 （様相論理：Ｍｏｄａｌ Ｌｏｇｉｃ）
（例）法則的解釈 （様相論理：Ｍｏｄａｌ　Ｌｏｇｉｃ） ①明日、台風がくれば休校になるな。 ②なあに、どうせ創立記念日で休みさ。 ③なるほど、それでは当然台風がくれば休校だ。 可能 不可能 偶然 必然 真 偽

10 ３．２ 論理に基づくプログラミング言語 PLANNER（論理をプログラミング言語として初めて採用）
３．２　論理に基づくプログラミング言語 PLANNER（論理をプログラミング言語として初めて採用） Prolog（論理によるプログラミング言語の代表格） Prolog-KR（Prologの拡張） URANUS(Prolog-KRをLispマシンに移植し、多重世界機能を拡張） KAUS（多層論理に基づく知識表現） MRS（メタ推論機能） KPYPTON（概念の内部構造と概念間の関係を分離）

11 ３．３ Ｐｒｏｌｏｇにおけるデータの種類 項(Term) 単純項(Simple Term) 整数(Integer) 定数(Number)
３．３　Ｐｒｏｌｏｇにおけるデータの種類 項(Term) 単純項(Simple Term) 整数(Integer) 定数(Number) 実数(Real) アトム(Atom) 通常変数 変数(Variable) ドント・ケア(Don’t Care) ＊どんな値でもマッチングし、マッチング結果を問わない。アンダーライン１文字で表現 複合項(Compound Term) ＊簡単に言えばツリー構造

12 複合項 述語（項１,　項２,　…,　項ｎ ） 述語 項１ 項２ …　項ｎ ツリー構造で表現すれば 述語 項１ 項２ … 項ｎ

13 複合項で組織図を表現する Ａ大学（ 学部（ 機械工学科, 電気電子工学科, 建築学科, システム工学科, 情報工学科）,
Ａ大学（ 学部（ 機械工学科, 電気電子工学科, 建築学科, システム工学科, 情報工学科）, 大学院（ 機械工学専攻, 電気工学専攻, 建築学専攻, システム工学専攻, 情報工学専攻）） 電気電子工学科 建築学科 システム工学科 情報工学科 大学院 機械工学専攻 電気工学専攻 建築学専攻 システム工学専攻 情報工学専攻

14 演習 次の分類体系を複合項で表現せよ 雑音除去法 平滑化 移動平均法 単純移動平均法 多項式適合法 適応化平滑化法 周波数領域法 積算平均化

15 特殊な複合項（リストとストリング） ①リスト（データの順序だけを関係としてもつデータの列）
データ１ データ１ データ１ 順序が意味を持たないときでも便宜上リストで表現する場合もある。 （例） 波形データ 名簿（一応、順序がある） ソースプログラム

16 ②ストリング（文字のリストとして表現される）
“ＡＢＣＤＥＦ” Ａ Ｂ Ｃ Ｄ Ｅ Ｆ 順序が意味を持たないときでも便宜上リストで表現する場合もある。

17 Ｐｒｏｌｏｇでは… ドットペア Ａ Ｂ ＝. (A, B) ＝ [A | B] 空リスト ＝ [ ] 拡張 Ａ Ｂ Ｃ
Ａ　　Ｂ ＝. (A, B) ＝　[A | B] 空リスト ＝　[　] 拡張 Ａ Ｂ Ｃ = . (A, . (B, . (C, []))) = [A | [B | [C | [ ]]]] = [A, B, C ] | [ α ] →　, α | [ ] →　空白

18 ３．４ 述語論理とＰｒｏｌｏｇ表現 ∀ｘ（犬（ｘ）→動物（ｘ）） ∀ｘ（猫（ｘ）→動物（ｘ）） ∀ｘ（（犬（ｘ）∩賢い（ｘ））
３．４　述語論理とＰｒｏｌｏｇ表現 ∀ｘ（犬（ｘ）→動物（ｘ）） ∀ｘ（猫（ｘ）→動物（ｘ）） ∀ｘ（（犬（ｘ）∩賢い（ｘ）） →噛みつかない（ｘ）） ∀ｘ　∀ｙ（（動物（ｘ）　∩　噛みつかない（ｙ）） →恐れない（ｘ,　ｙ）） 猫（ミー） 犬（ポチ） 犬（太郎） 賢い（ポチ） 動物（X） ：－ 犬（X）. 動物（X） ：－ 猫（X）. 噛みつかない（X） 　　　　 ：－犬（X）, 賢い（X）. 恐れない（X,　Y） 　　　　：－動物（X）,　噛みつかない（Y）. 猫（ミー）. 犬（ポチ）. 犬（太郎）. 賢い（ポチ）. （注意） 「→」の向きが逆（←）になり「：－」で表現されている。 「∩」が「,」になっている。 変数が大文字なっている。 終わりがピリオド（.）

19 ３．５ Ｐｒｏｌｏｇの文法 Ｐｒｏｌｏｇの1文は、「ホーン節（Horn Clause)］と呼ばれる。 ピリオドで終わる。
３．５　Ｐｒｏｌｏｇの文法 Ｐｒｏｌｏｇの1文は、「ホーン節（Horn Clause)］と呼ばれる。 ピリオドで終わる。 ：－も？－も含まないホーン節(右辺が空） （例）犬（ポチ）.　　　猫（ミケ）. ：－を含むホーン節 （例）恐れない（ｘ,　ｙ） ：－動物（ｘ）,　噛みつかない（ｙ）. ホーン節 ?－を含むホーン節（左辺が空。 ：－ と同じ意味） （例）?－恐れない(ミケ,　X）.

20 ３．６ Ｐｒｏｌｏｇの手続き的解釈 ・書き換え過程を計算過程と捉える 左辺1個, 右辺1個以上 ： 手続きの定義
３．６　Ｐｒｏｌｏｇの手続き的解釈 ・書き換え過程を計算過程と捉える 左辺1個,　右辺1個以上 ： 手続きの定義 左辺1個,　右辺空 ： 手続きまたはデータの集まりの定義 左辺空,　右辺1個以上 ： プログラムの開始 左辺空,　右辺空 ：プログラムの停止　

21 例 ①append([ ], B, B). ②append([ X|L], B,[X|LL]) :- append(L, B, LL).
?-append([a, b, c], [d, e], X). ②とマッチングして X≡a としてappend([b,c],[d,e], LL)が試される。 ②とマッチングしてX≡b としてappend([c],[d,e], LL)が試される。 ②とマッチングして X≡c としてappend([],[d,e], LL)が試される。 ①とマッチングして　LL≡[d, e] LL≡[X | 下位のLL]≡[c, d, e] LL≡[X | 下位のLL]≡[b, c, d, e] LL≡[X | 下位のLL]≡[a, b, c, d, e]

22 バックトラック（backtrack）としての解釈
x :- a1. x :- a2. x :- a3. a1 :- b1. a1 :- b2. b2. a2 :- c1. a2 :- c2. a3 :- d1. a3 :- d2. d1. Prologは深さ優先探索 a1→b2のみ? a3 a1 a2 d2 c1 c2 b1 b2 d1 失敗 成功 失敗 失敗 成功 失敗

23 複数解を求めるには 偽って成功しなかったとすればよい。
x :- a1. x :- a2. x :- a3. a1 :- b1. a1 :- b2. b2. a2 :- c1. a2 :- c2. a3 :- d1. a3 :- d2. d1. 失敗 a3 a1 a2 d2 c1 c2 b1 b2 d1 成功したが失敗とみなす 失敗 成功したが失敗とみなす 失敗 失敗 失敗

24 複数解を求める例 結果を見て、再度試行 定義中で強制的に失敗させる |犬（ポチ）. |犬（タロウ）. |?- 犬（X）.
yes　　　　　　（成功） X＝ポチ；　　　（；キーを押して失敗とみなす） X＝タロウ；　　（；キーを押して失敗とみなす） no　　　　　　　（失敗） 結果を見て、再度試行 |犬（ポチ）. |犬（タロウ）. |表示 :- 犬(X), write(X), writeln, fail. |?- 表示. ポチ 　 　（writeln で改行） タロウ　 　（ writeln で改行） no　　　　　　　（失敗）｜ 定義中で強制的に失敗させる

25 カット（！）の考え方 逆流しないような弁がついているものと考えれば分かりやすい |犬（ポチ） :- !. |犬（タロウ）.
|?- 犬（X）. X＝ポチ；　　 no　　　　　 逆流しないような弁がついているものと考えれば分かりやすい

26 カットによる not の定義 閉世界仮説（Closed World Assumption） 見当たらないものは「成立しない」とする
| 犬（ポチ） :- !. | 犬（タロウ）. | not (X) :- X, !, fail. | not (X). | ?- not (犬(ポチ))；　　 no　 | ?- not (犬(ミケ))；　　 yes　　　　　 閉世界仮説（Closed World Assumption） 見当たらないものは「成立しない」とする 開世界仮説（Open World Assumption） 見当たらないものは「真とも偽とも判定できない」とする Ｐｒｏｌｏｇは閉世界仮説をとる not(X):-X, !, fail. における X は高階であることに留意

27 無限ループ 常に成功する項(true)の考え方 x :- true, read(X), execute(X), fail. True

28 ３．７ 組込み(Built-in)述語および組込み関数 Prolog-10（エジンバラ大学）
組込み述語 !, true, fail ： (true の替わりに　repeat が用いられることもある） read(X) : キーボードから項(term)を読み込み、項を変数Ｘに置換する。 Write(X) : ディスプレイ上にＸの値を表示（出力）する。 比較 ： <　,　 >　,　 >=　,　=\=（不等号）　,　 =:=（等号） 置換 ： is 組込み関数 四則 : + , － , * , / 剰余 ： mod 負数 ： － ビット演算 ： /\ (and), \/ (or), \ (not), << (左シフト）, >> （右シフト） Infix形式とPrefix形式 [Infix形式] ： X is [Prefix形式] ： is ( X , + ( 2 , 3))

29 Is と = R is X : Xを数値的に計算し、計算結果をRとマッチングする。同じ形式にならない場合、エラーの場合は失敗。
R = X ： Xは計算されない。 （例） | ?- X = 3+4. X = 3+4 yes | ?- 7 = 3+4. no | ?- X is 3+4. X = 7 yes | ?- 7 is 3+4. 比較 右辺 ＋ ３ ４

30 If-Then-Else P ->Q ; R
定義 　　(P-> Q ; R) :- P, ! , Q. (P-> Q ; R) :- R. Qを fail,　Rを true とすると (P -> fail ; true) :- P, ! , fail. (P -> fail ; true) :- true. (右辺の true はあってもなくても同じ） Not(P)の右辺と比較 　not(P) :- P, ! , fail. Not(P) .

31 ３．８ 高階の述語 abolish(X, N) Xという名前を持ち引数N個の節を削除。
３．８　高階の述語 abolish(X, N) Xという名前を持ち引数N個の節を削除。 retract(X) Xにマッチングする最初の節を削除。 assert(X) Xの形の節を追加。位置は処理系によって異なる。 asserta(X) Xの形の節をプログラムの先頭に追加。 assertz(X) Xの形の節をプログラムの最後に追加。 listing(X) Xに一致する述語で始まる節を出力。 listing プログラム全部を出力

32 （高階述語の実行例） | 犬(ポチ). | 犬(タロウ). | ?- listing. 犬(ポチ). 犬(タロウ). yes | ?- asserta(犬(クロ)). 犬(クロ). | ?- assertz(犬(ムク)). yes | ?- listing. 犬(クロ). 犬(ポチ). 犬(タロウ). 犬(ムク). | ?- retract(犬(ポチ)). | ?- retract(X). X = 犬(クロ). yes | ?- listing. 犬(タロウ). 犬(ムク).

33 大域的変数の代替としての高階述語の使用 | random(Y) :- val(x, X), Y is ((X*7 + 7) mod 10),
retract(val(x, X)) , assert(val(x,Y)). | ?- assert(val(x,7)). yes | ?- random(Y). Y=6 Y=9 | ?- listing(val). val(x, 9)

34 ３．９ 項の作成 X=[a, b, c], A= .. X X=a, Y=[b, c], A= .. [X | Y]
３．９　項の作成 X=[a, b, c], A= .. X X=a, Y=[b, c], A= .. [X | Y] X=a, Y=b, Z=c, A= .. [X, Y, Z] いずれも　A= a ( b , c ) となる。

35 ３．１０ ユニフィケーション（単一化） 置換によって同じ形にすること
３．１０　ユニフィケーション（単一化） 置換によって同じ形にすること 制限 ： 変数X と 項term を単一化する際 term の中に変数Xが出現しないこと。置換によって同じ形にすること。 [例］ 変数X と 項 f(X) を単一化 （記号“←”は代入を示すものとする） X ←　f(X) X ←　f ( f ( X )) X ←　f ( f ( f (X))) ・

36 Most General Unifier(mgu) ２つの表現Ｅ１，Ｅ２をユニファイする代入のうち、他の任意のユニファイヤσに対して、適当な代入が存在して、σ＝μ○θとできるとき、代入μをmguと呼ぶ。ここで、○は代入の合成をしめす。 Above(X, Y)とabove(cat,V)をユニファイ 代入のパターン 代入1をmguにした場合（代入２でも可能） 1. {X ← cat, Y ← V} 2. {X ← cat, V ← Y} 3. {X ← cat, Y ← cat, V ← cat} 4. {X ← cat, Y ← dog, V ← dog} 5. {X ← cat, Y ← caw, V ← caw} 6. {X ← cat, Y ← Z, V ← Z} 　　　　　　　 /* Zは新しい変数　*/ 7. {X ← cat, Y ← f(U), V ← f(U)} 　　　　　　　 /* f は関数, U は変数*/ ・ 1. 自分自身。θとして空集合をとる。 2. {X ← cat, Y ← V} ○ { V ← Y} 3. {X ← cat, Y ← V} ○ { V ← cat} 4. {X ← cat, Y ← V} ○ { V ← dog} 5. {X ← cat, Y ← V} ○ { V ← caw} 6. {X ← cat, Y ← V} ○ { V ← Z} 　 /* Zは新しい変数　*/ 　　　　　　 7. {X ← cat, Y ← V} ○{ V ← f(U)} 　　　　　　　 /* f は関数, U は変数*/ ・

37 処理系を作る手順（１） １．領域管理を作成 （１）記号処理が中心であることを念頭に領域管理の設計。ゴミ集め(GC)が時間食らい虫であることに注意。 （２）領域の確保(Get Area), フリー(Free Area)関数を作成。 （３）ＧＣを作成（特別なＧＣがなくても構わない領域管理が理想） （４）Car部、Cdr部の設定及び取りだし(Cons, Car, Cdr)を作成 （５）アトム及び変数の管理（値、属性など） （６）述語領域の設定 （７）処理系内部の制御ルーチンの作成

38 処理系を作る手順（２） ２．入出力述語の作成 （１）標準入力での１文字入出力述語の作成。
（２）標準入力での文字スキャン、トークン作成述語の作成。 （３）入力をリストにする処理を作成。 （４）項作成述語の作成 （５）Read、Write関数の作成 （６）ファイル入出力に拡張(Open, Close) （７）高水準入出力の作成

39 処理系を作る手順（３） ３．評価述語（Ｃａｌｌ）の作成 （１）カレント変数生成の作成。 （２）項の比較、代入部の作成。
（３）マッチング部の作成。 （４）多段階のマッチングに拡張。 （５）評価述語の作成 （６）データベースの追加・削除、取りだし等 （７）Read、Write関数の作成

40 処理系を作る手順（４） ４．各種述語（Ｃａｌｌ）の作成 （１）簡単なものから複雑なものへ 　　　例えば、算術関数から手をつける。

41 領域管理の例 （なるべく固定長領域に） ＩＤ タグ 値部 タグ 値部 １ ０ ０ ０ ２ ２ ０ ０ ０ ３ ３ ０ ０ ０ ４ ・
ＩＤ タグ 値部 タグ 値部 １ ０ ０ ０ ２ ２ ０ ０ ０ ３ ３ ０ ０ ０ ４ ・ ９９７ ０ ０ ０ ９９８ ９９８ ０ ０ ０ ９９９ ９９９ ０ ０ ０ ０ 未使用領域ポインタ 領域をＧｅｔする度に、 未使用領域から外す。 領域をＦｒｅｅする度に、 未使用領域の先頭に繋ぐ