主として論理による知識表現の代表 Prologによる表現

Slides:



Advertisements
Similar presentations
1 情報基礎 A 第 9 週 プログラミング入門 VBA の基本文法 1 準備・変数・データの入出力 徳山 豪・全 眞嬉 東北大学情報科学研究科 システム情報科学専攻 情報システム評価学分野.
Advertisements

一階述語論理 (first-order predicate logic) 一階述語論理入門 構文論(論理式の文 法) 意味論(論理式の解 釈) 認知システム論 知識と推論(4) 知識と論理でを組み合わせて問題を解決する.
プログラミング言語論 第10回(演習) 情報工学科 木村昌臣   篠埜 功.
人工知能特論2011 No.4 東京工科大学大学院 担当教員:亀田弘之.
情報・知能工学系 山本一公 プログラミング演習Ⅱ 第3回 配列(1) 情報・知能工学系 山本一公
京都大学情報学研究科 通信情報システム専攻 湯淺研究室 M2 平石 拓
プログラミング言語としてのR 情報知能学科 白井 英俊.
数値計算及び実習 第3回 プログラミングの基礎(1).
基礎プログラミングおよび演習 第9回
第四回 線形計画法(2) 混合最大値問題 山梨大学.
データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.
5.チューリングマシンと計算.
5.チューリングマシンと計算.
授業展開#11 コンピュータは 何ができるか、できないか.
プログラミング演習II 2004年10月19日(第1回) 理学部数学科・木村巌.
論理式の表現を数学的に取り扱いやすくするために代数学の助けを借りる.
Prolog演習 PowerPointのアニメーション機能を利用すると分かりやすいと思います.
人工知能特論2011 資料No.6 東京工科大学大学院 担当教員 亀田弘之.
情報科学1(G1) 2016年度.
条件式 (Conditional Expressions)
データ構造と アルゴリズム 知能情報学部 新田直也.
言語処理系(5) 金子敬一.
システム開発実験No.7        解 説       “論理式の簡略化方法”.
①データ構造 ②アルゴリズム ③プログラム言語 ④マークアップ言語
プログラムはなぜ動くのか.
プログラミング演習Ⅰ 課題2 10進数と2進数 2回目.
コンパイラ 2012年10月22日
ML 演習 第 7 回 新井淳也、中村宇佑、前田俊行 2011/05/31.
コンパイラ 2011年10月24日
第7回 条件による繰り返し.
プログラムの制御構造 選択・繰り返し.
PROGRAMMING IN HASKELL
プログラミング言語論プログラミング言語論 プログラムの意味論 水野嘉明
プログラミング入門 電卓を作ろう・パートIV!!.
計算の理論 II Turing機械の合成 月曜5校時 大月美佳 2004/11/15 佐賀大学理工学部知能情報システム学科.
京都大学情報学研究科 通信情報システム専攻 湯淺研究室 D1 平石 拓 2005/10/18
アルゴリズムとデータ構造 補足資料5-2 「サンプルプログラムsetop.c」
Prolog入門 ーIT中級者用ー.
第7回 条件による繰り返し.
 型推論1(単相型) 2007.
並行プログラミング concurrent programming
VBで始めるプログラミング こんにちは、世界。 /28 NARC.
計算機構成 第3回 データパス:計算をするところ テキスト14‐19、29‐35
プログラミング言語論 第四回 理工学部 情報システム工学科 新田直也.
論理プログラミング 導出の効率化 論理プログラム ホーン節 ホーン集合に対する導出戦略 論理式の手続き的解釈 Prolog
第5章 計算とプログラム 本章で説明すること ・計算の概観と記述法 ・代表的な計算モデル ・プログラムとプログラム言語.
コンパイラ 2011年10月20日
 型推論3(MLの多相型).
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
C言語 はじめに 2016年 吉田研究室.
15.cons と種々のデータ構造.
プログラミング基礎a 第6回 C言語によるプログラミング入門 配列と文字列(その2)
オブジェクト指向言語論 第三回 知能情報学部 新田直也.
5.チューリングマシンと計算.
福井大学大学院工学研究科機械工学専攻 川谷 亮治
情報処理Ⅱ 2006年11月24日(金).
4.プッシュダウンオートマトンと 文脈自由文法の等価性
情報処理Ⅱ 第7回 2004年11月16日(火).
情報処理Ⅱ 2005年10月28日(金).
プログラミング基礎a 第3回 C言語によるプログラミング入門 データ入力
PROGRAMMING IN HASKELL
情報数理Ⅱ 第10章 オートマトン 平成28年12月21日.
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
情報処理Ⅱ 2005年11月25日(金).
情報処理Ⅱ 小テスト 2005年2月1日(火).
プログラミング基礎a 第3回 C言語によるプログラミング入門 データ入力
printf・scanf・変数・四則演算
情報処理Ⅱ 2006年10月27日(金).
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
アルゴリズム ~すべてのプログラムの基礎~.
Presentation transcript:

主として論理による知識表現の代表 Prologによる表現 3.論理による知識表現 主として論理による知識表現の代表 Prologによる表現

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

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

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

言葉に敏感に!! A:木村は金に困らなければ、働かない。 B:木村は働かなければ、金に困る。 P:金に困る Q:働かない A: ~P → Q A: ~P → Q B: Q  → P ~P → Q → P ∴~P → P ? if…then は、しばしば While の替わりに使用される P:金に困る Q:働かない

(例)誘導推論 P Q ~P ~Q ~P→Q P→~Q 1 1 0 0 1 0 1 0 0 1 1 1 0 1 1 0 1 1 金を出さなければ、殺すぞ ~P → Q        ↓ 金を出せば、殺さない Q  → ~Q P Q ~P ~Q ~P→Q P→~Q 1 1  0  0   1   0 1 0  0  1   1   1 0 1  1  0   1   1 0 0  1  1   0   1

(例)推移的性質のモデルの妥当性 右 右 AはBの右にある ∩ BはCの右にある → AはCの右にある 基点自身が方向性を持つ AはBの右にある ∩ BはCの右にある → AはCの右にある 基点自身が方向性を持つ AさんはBさんの右にいます BさんはCさんの右にいます しかし、 AさんはBさんの右にいません はて? 右 右

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

(例)法則的解釈 (様相論理:Modal Logic) (例)法則的解釈 (様相論理:Modal Logic) ①明日、台風がくれば休校になるな。 ②なあに、どうせ創立記念日で休みさ。 ③なるほど、それでは当然台風がくれば休校だ。 可能 不可能 偶然 必然 真 偽

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

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

複合項 述語(項1, 項2, …, 項n ) 述語 項1 項2 … 項n ツリー構造で表現すれば 述語 項1 項2 … 項n

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

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

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

②ストリング(文字のリストとして表現される) “ABCDEF” A B C D E F 順序が意味を持たないときでも便宜上リストで表現する場合もある。

Prologでは… ドットペア A B =. (A, B) = [A | B] 空リスト = [ ] 拡張 A B C A  B =. (A, B) = [A | B] 空リスト = [ ] 拡張 A B C = . (A, . (B, . (C, []))) = [A | [B | [C | [ ]]]] = [A, B, C ] | [ α ] → , α | [ ] → 空白

3.4 述語論理とProlog表現 ∀x(犬(x)→動物(x)) ∀x(猫(x)→動物(x)) ∀x((犬(x)∩賢い(x)) 3.4 述語論理とProlog表現 ∀x(犬(x)→動物(x)) ∀x(猫(x)→動物(x)) ∀x((犬(x)∩賢い(x)) →噛みつかない(x)) ∀x ∀y((動物(x) ∩ 噛みつかない(y)) →恐れない(x, y)) 猫(ミー) 犬(ポチ) 犬(太郎) 賢い(ポチ) 動物(X) :- 犬(X). 動物(X) :- 猫(X). 噛みつかない(X)      :-犬(X), 賢い(X). 恐れない(X, Y)     :-動物(X), 噛みつかない(Y). 猫(ミー). 犬(ポチ). 犬(太郎). 賢い(ポチ). (注意) 「→」の向きが逆(←)になり「:-」で表現されている。 「∩」が「,」になっている。 変数が大文字なっている。 終わりがピリオド(.)

3.5 Prologの文法 Prologの1文は、「ホーン節(Horn Clause)]と呼ばれる。 ピリオドで終わる。 3.5 Prologの文法 Prologの1文は、「ホーン節(Horn Clause)]と呼ばれる。 ピリオドで終わる。 :-も?-も含まないホーン節(右辺が空) (例)犬(ポチ).   猫(ミケ). :-を含むホーン節 (例)恐れない(x, y) :-動物(x), 噛みつかない(y). ホーン節 ?-を含むホーン節(左辺が空。 :- と同じ意味) (例)?-恐れない(ミケ, X).

3.6 Prologの手続き的解釈 ・書き換え過程を計算過程と捉える 左辺1個, 右辺1個以上 : 手続きの定義 3.6 Prologの手続き的解釈 ・書き換え過程を計算過程と捉える 左辺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. 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 失敗 成功 失敗 失敗 成功 失敗

複数解を求めるには 偽って成功しなかったとすればよい。 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 成功したが失敗とみなす 失敗 成功したが失敗とみなす 失敗 失敗 失敗

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

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

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

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

3.7 組込み(Built-in)述語および組込み関数 Prolog-10(エジンバラ大学) 組込み述語 !, true, fail : (true の替わりに repeat が用いられることもある) read(X) : キーボードから項(term)を読み込み、項を変数Xに置換する。 Write(X) : ディスプレイ上にXの値を表示(出力)する。 比較 : < ,  > ,  >= , =\=(不等号) ,  =:=(等号) 置換 : 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. 比較 右辺 + 3 4

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) .

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

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

大域的変数の代替としての高階述語の使用 | 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)

3.9 項の作成 X=[a, b, c], A= .. X X=a, Y=[b, c], A= .. [X | Y] 3.9 項の作成 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 ) となる。

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

Most General Unifier(mgu) 2つの表現E1,E2をユニファイする代入のうち、他の任意のユニファイヤσに対して、適当な代入が存在して、σ=μ○θとできるとき、代入μをmguと呼ぶ。ここで、○は代入の合成をしめす。 Above(X, Y)とabove(cat,V)をユニファイ 代入のパターン 代入1をmguにした場合(代入2でも可能) 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 は変数*/ ・

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

処理系を作る手順(2) 2.入出力述語の作成 (1)標準入力での1文字入出力述語の作成。 (2)標準入力での文字スキャン、トークン作成述語の作成。 (3)入力をリストにする処理を作成。 (4)項作成述語の作成 (5)Read、Write関数の作成 (6)ファイル入出力に拡張(Open, Close) (7)高水準入出力の作成

処理系を作る手順(3) 3.評価述語(Call)の作成 (1)カレント変数生成の作成。 (2)項の比較、代入部の作成。 (3)マッチング部の作成。 (4)多段階のマッチングに拡張。 (5)評価述語の作成 (6)データベースの追加・削除、取りだし等 (7)Read、Write関数の作成

処理系を作る手順(4) 4.各種述語(Call)の作成 (1)簡単なものから複雑なものへ    例えば、算術関数から手をつける。

領域管理の例 (なるべく固定長領域に) ID タグ 値部 タグ 値部 1 0 0 0 2 2 0 0 0 3 3 0 0 0 4 ・ ID タグ 値部 タグ 値部 1 0 0 0 2 2 0 0 0 3 3 0 0 0 4 ・ 997 0 0 0 998 998 0 0 0 999 999 0 0 0 0 未使用領域ポインタ 領域をGetする度に、 未使用領域から外す。 領域をFreeする度に、 未使用領域の先頭に繋ぐ