3．論理による知識表現

３．論理による知識表現
主として論理による知識表現の代表
Ｐｒｏｌｏｇによる表現
３．１論理による知識表現
①形式化が容易であり、直感的理解と一致するこ
とが多い。
②図表に比べ、イメージに訴えない。
③記述が厳密であり、証明を機械的に行うことがで
きる。
④記述方法が単純であり、新しい事実を追加する
ことが容易である。
⑤記述をどう利用するか、どう蓄積するかを決定す
る部分がない。
知識表現上の注意
• 我々は、
語ることができるより、
もっと多くのことを知っている。
• ひとつの表現で
全てを言い尽くせたとは言えない。
命題論理、述語論理の限界
① 必然性、可能性の概念の欠如
② 形式化が容易な限られた範囲の推論
↓
形式論理学により、形式的に妥当とされ
る推論が論理的推論の全てではない。
…しかし…
かなり成功をおさめた理論化のひとつ
言葉に敏感に！！
Ａ：木村は金に困らなければ、働かない。
Ｂ：木村は働かなければ、金に困る。
Ｐ：金に困る
Ｑ：働かない
Ａ：～Ｐ → Ｑ
Ｂ：Ｑ → Ｐ
ｉｆ…ｔｈｅｎは、しばしば
Ｗｈｉｌｅの替わりに使用される
～Ｐ → Ｑ → Ｐ
∴～Ｐ → Ｐ？
Ｐ：金に困る
Ｑ：働かない
（例）誘導推論
金を出さなければ、殺すぞ～Ｐ → Ｑ
↓
金を出せば、殺さない
Ｑ → ～Ｑ
ＰＱ
～Ｐ～Ｑ～Ｐ→Ｑ
Ｐ→～Ｑ
１１
０
０
１
０
１０
０
１
１
１
０１
１
０
１
１
００
１
１
０
１
（例）推移的性質のモデルの妥当性
ＡはＢの右にある ∩ ＢはＣの右にある → ＡはＣの右にある
基点自身が方向性を持つ
ＡさんはＢさんの右にいます
ＢさんはＣさんの右にいます
しかし、
ＡさんはＢさんの右にいません
はて？
右
右
（例）擬似条件
Ｐ
暑い
Ｑ
のどが渇く
何か飲みたい
Ｓ
昨日、ビールを買った
ビールが冷蔵庫に
入っている
∩
①暑ければ、昨日ビールを買ったよ。
②のどが渇いているなら、
ビールが冷蔵庫に入っているよ。
③ビールが冷蔵庫に入ってるなら、
さっきからのどが渇いてしょうがないんだ
ビールを
飲む
（例）法則的解釈
（様相論理：ＭｏｄａｌＬｏｇｉｃ）
①明日、台風がくれば休校になるな。
②なあに、どうせ創立記念日で休みさ。
③なるほど、それでは当然台風がくれば休校だ。
可能
不可能
偽
偶然
必然
真
３．２論理に基づくプログラミング言語
•
•
•
•
PLANNER（論理をプログラミング言語として初めて採用）
Prolog（論理によるプログラミング言語の代表格）
Prolog-KR（Prologの拡張）
URANUS(Prolog-KRをLispマシンに移植し、多重世界機
能を拡張）
• KAUS（多層論理に基づく知識表現）
• MRS（メタ推論機能）
• KPYPTON（概念の内部構造と概念間の関係を分離）
３．３Ｐｒｏｌｏｇにおけるデータの種類
項(Term)
単純項(Simple Term)
定数(Number)
整数(Integer)
実数(Real)
アトム(Atom)
通常変数
変数(Variable)
複合項(Compound Term)
＊簡単に言えばツリー構造
ドント・ケア(Don’t Care)
＊どんな値でもマッチングし、
マッチング結果を問わない。
アンダーライン１文字で表現
複合項
述語（項１, 項２, …, 項ｎ）
述語
項１
項２
… 項ｎ
ツリー構造で表現すれば
述語
項１
項２
…
項ｎ
複合項で組織図を表現する
Ａ大学
学部
機械工学科
機械工学科,
電気電子工学科
電気電子工学科,
建築学科
建築学科,
システム工学科
システム工学科,
情報工学科
大学院
Ａ大学（学部（
情報工学科）,
機械工学専攻
大学院（機械工学専攻,
電気工学専攻
電気工学専攻,
建築学専攻
建築学専攻,
システム工学専攻
システム工学専攻,
情報工学専攻
情報工学専攻））
演習
次の分類体系を複合項で表現せよ
雑音除去法
平滑化
移動平均法
単純移動平均法
多項式適合法
適応化平滑化法
周波数領域法
積算平均化
特殊な複合項（リストとストリング）
①リスト（データの順序だけを関係としてもつデータの列）
データ１
データ１
データ１
順序が意味を持たないときでも便宜上リストで表現
する場合もある。
（例）
波形データ
名簿（一応、順序がある）
ソースプログラム
②ストリング（文字のリストとして表現される）
“ＡＢＣＤＥＦ”
Ａ
Ｂ
Ｃ
Ｄ
Ｅ
Ｆ
順序が意味を持たないときでも便宜上リストで表現
する場合もある。
Ｐｒｏｌｏｇでは…
ドットペア
Ａ
Ｂ
＝. (A, B) ＝ [A | B]
空リスト
＝ [ ]
拡張
Ａ
Ｂ
Ｃ
|[ α]→ , α
|[]
→ 空白
= . (A, . (B, . (C, [])))
= [A | [B | [C | [ ]]]]
= [A, B, C ]
３．４述語論理とＰｒｏｌｏｇ表現
∀ｘ（犬（ｘ）→動物（ｘ））
動物（X）：－犬（X）.
∀ｘ（猫（ｘ）→動物（ｘ））
動物（X）：－猫（X）.
∀ｘ（（犬（ｘ）∩賢い（ｘ））
噛みつかない（X）
→噛みつかない（ｘ））
∀ｘ ∀ｙ（（動物（ｘ） ∩ 噛みつかない（ｙ））
：－犬（X）, 賢い（X）.
恐れない（X, Y）
→恐れない（ｘ, ｙ））
：－動物（X）, 噛みつかない（Y）.
猫（ミー）
猫（ミー）.
犬（ポチ）
犬（ポチ）.
犬（太郎）
犬（太郎）.
賢い（ポチ）
賢い（ポチ）.
（注意）
「→」の向きが逆（←）になり「：－」で表現されている。
「∩」が「,」になっている。
変数が大文字なっている。
終わりがピリオド（.）
３．５Ｐｒｏｌｏｇの文法
• Ｐｒｏｌｏｇの1文は、「ホーン節（Horn Clause)］と呼
ばれる。
• ピリオドで終わる。
：－も？－も含まないホーン節(右辺が空）
（例）犬（ポチ）.
ホーン節
猫（ミケ）.
：－を含むホーン節
（例）恐れない（ｘ,
ｙ）：－動物（ｘ）, 噛みつかない（ｙ）.
?－を含むホーン節（左辺が空。：－と同じ意味）
（例）?－恐れない(ミケ,
X）.
３．６Ｐｒｏｌｏｇの手続き的解釈
・書き換え過程を計算過程と捉える
左辺1個, 右辺1個以上
左辺1個, 右辺空
左辺空, 右辺1個以上
左辺空, 右辺空
：手続きの定義
：手続きまたはデータの
集まりの定義
：プログラムの開始
：プログラムの停止
例
①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]
バックトラック（backtrack）としての解釈
x :- a1.
x :- a2.
x :- a3.
Prologは深さ優先探索
a1→b2のみ?
a3
a1
a2
a1 :- b1.
a1 :- b2.
b2.
a2 :- c1.
c1
b1
d2
c2
b2
d1
a2 :- c2.
a3 :- d1.
a3 :- d2.
d1.
失敗
成功
失敗
失敗
成功
失敗
複数解を求めるには
偽って成功しなかったとすればよい。
x :- a1.
失敗
x :- a2.
a3
a1
x :- a3.
a2
a1 :- b1.
a1 :- b2.
b2.
a2 :- c1.
b1
c1
d2
c2
b2
d1
a2 :- c2.
a3 :- d1.
a3 :- d2.
d1.
失敗
成功した
が失敗と
みなす
失敗
失敗
成功した失敗
が失敗と
みなす
複数解を求める例
結果を見て、再度試行
|犬（ポチ）.
|犬（タロウ）.
|?- 犬（X）.
X＝ポチ
（ キーを押す）
yes
（成功）
|?- 犬（X）.
X＝ポチ；
（；キーを押して失敗とみなす）
X＝タロウ；（；キーを押して失敗とみなす）
no
（失敗）
定義中で強制的に失敗させる |犬（ポチ）.
|犬（タロウ）.
|表示 :- 犬(X), write(X), writeln, fail.
|?- 表示.
ポチ
（writeln で改行）
タロウ
（ writeln で改行）
no
（失敗）｜
カット（！）の考え方
|犬（ポチ） :- !.
|犬（タロウ）.
|?- 犬（X）.
X＝ポチ；
no
逆流しないような弁が
ついているものと考え
れば分かりやすい
カットによる not の定義
| 犬（ポチ） :- !.
| 犬（タロウ）.
| not (X) :- X, !, fail.
| not (X).
| ?- not (犬(ポチ))；
no
| ?- not (犬(ミケ))；
yes
閉世界仮説（Closed World Assumption）
見当たらないものは「成立しない」
とする
開世界仮説（Open World Assumption）
not(X):-X, !, fail.
における X は高階であることに留意
見当たらないものは「真とも偽とも
判定できない」とする
Ｐｒｏｌｏｇは閉世界仮説をとる
無限ループ
• 常に成功する項(true)の考え方
x :- true, read(X), execute(X), fail.
True
fail
Read(X)
Execute(X)
３．７組込み(Built-in)述語および組込み関数
Prolog-10（エジンバラ大学）
組込み述語
!, true, fail
read(X)
Write(X)
比較
置換
組込み関数
四則
剰余
負数
ビット演算
：
:
:
：
：
(true の替わりに repeat が用いられることもある）
キーボードから項(term)を読み込み、項を変数Ｘに置換する。
ディスプレイ上にＸの値を表示（出力）する。
< , > , >= , =\=（不等号） , =:=（等号）
is
:
：
：
：
+,－,*,/
mod
－
/\ (and), \/ (or), \ (not), << (左シフト）, >> （右シフト）
Infix形式とPrefix形式
[Infix形式] ： X is 2 + 3
[Prefix形式] ： is ( X , + ( 2 , 3))
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.
yes
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) .
３．８高階の述語
abolish(X, N) Xという名前を持ち引数N個の節を削除。
retract(X)
Xにマッチングする最初の節を削除。
assert(X)
Xの形の節を追加。位置は処理系によっ
て異なる。
asserta(X)
Xの形の節をプログラムの先頭に追加。
assertz(X)
Xの形の節をプログラムの最後に追加。
listing(X)
Xに一致する述語で始まる節を出力。
listing
プログラム全部を出力
（高階述語の実行例）
| 犬(ポチ).
| 犬(タロウ).
| ?- listing.
犬(ポチ).
犬(タロウ).
yes
| ?- asserta(犬(クロ)).
yes
| ?- listing.
犬(クロ).
犬(ポチ).
犬(タロウ).
yes
| ?- assertz(犬(ムク)).
yes
| ?- listing.
犬(クロ).
犬(ポチ).
犬(タロウ).
犬(ムク).
yes
| ?- retract(犬(ポチ)).
yes
| ?- listing.
犬(クロ).
犬(タロウ).
犬(ムク).
yes
| ?- retract(X).
X = 犬(クロ).
yes
| ?- listing.
犬(タロウ).
犬(ムク).
yes
大域的変数の代替としての高階述語の使用
| 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
yes
| ?- random(Y).
Y=9
yes
| ?- listing(val).
val(x, 9)
yes
３．９項の作成
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 ) となる。
３．１０ユニフィケーション（単一
化）
置換によって同じ形にすること
制限
[例］
：変数X と項term を単一化する際 term の中に変
数Xが出現しないこと。置換によって同じ形にする
こと。
変数X と項 f(X) を単一化
（記号“←”は代入を示すものとする）
X ← f(X)
X ← f ( f ( X ))
X ← f ( f ( f (X)))
・
・
Most General Unifier(mgu)
２つの表現Ｅ１，Ｅ２をユニファイする代入のうち、他の任意のユニファイ
ヤσに対して、適当な代入が存在して、σ＝μ○θとできるとき、代入μを
mguと呼ぶ。ここで、○は代入の合成をしめす。
Above(X, Y)とabove(cat,V)をユニファイ
代入のパターン
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をmguにした場合（代入２でも可能）
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 は変数*/
・
・
・
処理系を作る手順（１）
１．領域管理を作成
（１）記号処理が中心であることを念頭に領域管理の設計。ゴ
ミ集め(GC)が時間食らい虫であることに注意。
（２）領域の確保(Get Area), フリー(Free Area)関数を作成。
（３）ＧＣを作成（特別なＧＣがなくても構わない領域管理が理
想）
（４）Car部、Cdr部の設定及び取りだし(Cons, Car, Cdr)を作成
（５）アトム及び変数の管理（値、属性など）
（６）述語領域の設定
（７）処理系内部の制御ルーチンの作成
処理系を作る手順（２）
２．入出力述語の作成
（１）標準入力での１文字入出力述語の作成。
（２）標準入力での文字スキャン、トークン作成述語の作成。
（３）入力をリストにする処理を作成。
（４）項作成述語の作成
（５）Read、Write関数の作成
（６）ファイル入出力に拡張(Open, Close)
（７）高水準入出力の作成
処理系を作る手順（３）
３．評価述語（Ｃａｌｌ）の作成
（１）カレント変数生成の作成。
（２）項の比較、代入部の作成。
（３）マッチング部の作成。
（４）多段階のマッチングに拡張。
（５）評価述語の作成
（６）データベースの追加・削除、取りだし等
（７）Read、Write関数の作成
処理系を作る手順（４）
４．各種述語（Ｃａｌｌ）の作成
（１）簡単なものから複雑なものへ
例えば、算術関数から手をつける。
領域管理の例
（なるべく固定長領域に）
ＩＤ
タグ
値部
タグ
値部
１
０
０
０
２
２
０
０
０
３
領域をＧｅｔする度に、
３
０
０
０
４
未使用領域から外す。
・
未使用領域ポインタ
・
領域をＦｒｅｅする度に、
・
未使用領域の先頭に
繋ぐ
９９７
０
０
０
９９８
９９８
０
０
０
９９９
９９９
０
０
０
０

Download Report