論理による 知識の表現と推論 (Knowledge Representation and Reasoning in Logic)

Presentation on theme: "論理による 知識の表現と推論 (Knowledge Representation and Reasoning in Logic)"— Presentation transcript:

1 論理による 知識の表現と推論 (Knowledge Representation and Reasoning in Logic)
認知システム論　知識と推論（１） 知識を表現し，それを用いて推論する 論理による 知識の表現と推論 (Knowledge Representation and Reasoning in Logic) 　今回からは「知識と推論」と題し，エージェントがタスクをこなすために必要な実世界に関する知識をコンピュータ内で知識ベースとして表現し，それらの知識を連携させる推論技術によって新しい知識を導き出し，エージェントの問題解決や意志決定に役立てる技術を学ぶ． 　特に今回の授業では「論理」による知識の表現方法と推論方式について学ぶ． 　まず，人工知能と論理の関係を理解した後，いろいろな論理と推論方式があることを見る．また，論理を取り扱う際の学術的な枠組みとして，構文論，意味論，および推論システムを明確に定義する必要があることを理解する． 　つぎに，論理の具体的かつ最も簡単な例として命題論理を取り上げ，その構文論，意味論，および推論システムを学び，例題として，簡単なゲームの世界を見ておく． 　人工知能と論理 　命題論理

2 人工知能と論理(1/5):なぜAIで論理を学ぶのか
探索による問題解決 初期状態 オペレータ（行為） ゴール検査 経路コスト 状態 行為 状態 状態をどのように記述したら良いか？ 行為の結果をどのように計算（推論）したら良いか？ 　これまで学んできた「探索」による問題解決手法では，問題を 　　　初期状態 　　　オペレータ（行為） 　　　ゴール検査 　　　経路コスト の４つの情報で規定し，おもに探索アルゴリズムの性能を議論してきた． 　しかし，ここでは，「状態」や 「行為の結果（状態遷移）」をどのように記述したら良いか，という問題が置き去りにされている．探索アルゴリズムにおいては，状態とは抽象的なものであり，たとえば，整数によって表現された一連番号であってもかまわないし，また，それ以上のことを必要ともしていない． 　しかし，複雑な問題領域においては，探索アルゴリズム以前の問題として，解決すべき問題を探索問題として定式化すること自体が困難である．すなわち，「状態」をコンピュータで扱うためにどのように表現すれば良いのだろうか？　また，「行為の結果」をどのように計算（あるいは推論）したら良いのだろうか？　明らかに，それらを適切に記述するための一般的な方法が必要である．その基盤となるのが，「論理」の一般的な考え方とそれを扱う技術である． 論理

3 人工知能と論理(2/5):なぜAIで論理を学ぶのか
なぜ 人工知能 で 論理 (LOGIC)を学ぶのか． 知識表現のための言語としての論理　⇒　構文論，意味論 推論をおこなうアルゴリズムとしての論理　 ⇒　推論システム 問題固有の知識 知識ベース 背景知識 知識 推論 アルゴリズム (= LOGIC) TELL 知識 ASK／ANSWER 　人工知能における「論理」の役割を説明しておく． 　一般に，人間がコンピュータに情報を与える「言語」といえば，すぐプログラミング言語が思いつく．それはコンピュータへの命令の列すなわちプログラムを具体的に記述したものである．しかし，そもそもAIの究極的な目的の１つは，そのようにいちいち命令しなくても，ふつうの言葉で意図を伝えれば，自動的に適切な命令を組み立てて実行してくれる知的な情報システムを目指しているのである．そのようなAIシステムでは，コンピュータと人間が日本語や英語などの自然言語で対話することを理想としている．その言語は必ずしもコンピュータへの命令を表したものではなく，AIシステムに何らかの知識を与えたり，解いて欲しい問題を与えたり，質問したりするために使われる．AIシステムは獲得した知識を知識ベースと呼ばれる一種のデータベースに蓄える． 　ただ，残念ながら，コンピュータが自然言語を理解するという技術はまだ開発途上にあり，現状ではそれをじゅうぶんに利用することはできない．そこで何らかの人工的な言語で，知識を与えたり，問題を記述したり，質問したりするための知識表現言語と呼ばれる類の言語が必要となる．そのようなものの一つが，論理に基づく言語なのである．つまり，ここでは論理とは言語のことである．したがって，それを理解するには，他のいろいろな言語を理解するのと同様に，正しい文を生成するための文法規則（構文論）や与えられた文を解釈する規則（意味論）を理解する必要がある．つまり，知識や問題を表現するという静的な側面が，AIにおける論理の第一の役割である． 　AIにおける論理の第二の役割は動的なものである．AIシステムは，与えられた知識ベース内の複数の知識を使って，新しい知識を動的に生成する機能が求められる．その機能を推論という．コンピュータに推論を行わせるアルゴリズムは，論理的な推論規則に基づく推論システムとして定義される．したがって，ここでは論理とは推論アルゴリズムという計算手順を作り出すものとして働くことになる． 知識 知識表現言語 (=LOGIC) 　　　　　 推論された知識

4 人工知能と論理(3/5):いろいろな論理と推論方式
完全な知識に基づく数学的な推論 Propositional logic 今回の授業 命題論理：命題の真偽を１つの記号で表現 Predicate logic 述語論理：問題領域に存在するオブジェクト（主語，目的語）およびオブジェクト間の関係（動詞，形容詞）を表す複数の記号で１つの命題を表現 Modal logic 様相論理：必然性や可能性を表現(must, can, may) 　単に論理や推論といっても，AIではさまざまなものが考えられている． 　まず，数学の試験問題を解くときのように，問題を解決するための知識が正確ですべてそろっているとき，それは完全な知識であるという．そういう場合には，ギリシャ時代から発展してきて現在でも多くの科学で使われている標準的で数学的な論理と推論の方法がある．もっとも単純なのは，命題の真偽を１つの記号で表現する命題論理(propositional logic)である．それをやや複雑にしたものとして，命題を，主語や目的語を表現する名詞（オブジェクト）とそれらの間の関係を表現する動詞（述語）などに分解して，複数の記号で１つの命題を構造的に表現する述語論理(predicate logic)がある． 　そのほかにも，英語の助動詞 must が表す必然性や can, may が表す可能性を扱うことができる様相論理(modal logic)が研究されている．また，時間の概念を論理的に表現し，always（いつも～である）とか eventually（いつか必ず～となる）のような表現を可能とする時相論理(temporal logic)は，ハードウェアやソフトウェアの設計や検証にも用いられつつある． Temporal logic 時相論理：時間を表現(always, eventually)

5 人工知能と論理(4/5):いろいろな論理と推論方式
不確実な知識に基づく推論 ファジィ推論：あいまいで主観的な知識を扱う 第２回の授業 Fuzzy reasoning 確率推論：観測事実から命題が真である確率を計算 Probabilistic reasoning 第３回の授業 知識が欠けているときの推論 帰納推論：多数の観測事実から一般法則を導く Inductive reasoning 第４回の授業 　実際の応用システムでは，数学と異なり，すべての知識が正確であるとは限らない．そのような不確実な知識を扱うための推論手法として，ファジィ推論(fuzzy reasoning)や確率推論(probabilistic reasoning)がある．また，知識が欠けているときの推論手法として，帰納推論(inductive reasoning)や仮説推論(hypothetical reasoning)などがある．特に，帰納推論は，ＡＩにおける知識獲得(knowledge acquisition)や機械学習(machine learning)の分野と密接に関係している． 仮説推論：観測事実を説明できる仮説を導く Hypothetical reasoning

6 人工知能と論理(5/5):構文論，意味論，推論システム
「論理式」として受理される文法的に正しい記号の並べ方を規定する 構文論 論理を規定する枠組み syntax 論理式の意味（真偽）の判定方法を規定する 意味論 semantics 前提として与えられた論理式から，結論として他の論理式を導く機械的な方式を規定する 推論システム 　このように，一言で「論理」と言っても，様々なものがある．それらの論理を規定する（区別する）ものは，「構文論」，「意味論」，「推論システム」である． 　構文論(syntax) は，その論理の定める「論理式」と呼ばれるものが，記号をどのように並べたものなのかを定める規則である．すなわち，記号の列が与えられたとき，それが「論理式」か否かを判定する規則（いわゆる「文法」）である． 　意味論(semantics) は，論理式の意味を理解するための規則である．論理では，興味のある「意味」とは「真か偽か」ということなので，意味論は，与えられた論理式の真偽を判定する規則となる． 　推論システム(inference system) は，（一般に複数の）論理式が与えられたとき，それを「前提」として，「結論」として言える論理式を導く（推論する）ための規則である．コンピュータを使って推論をさせるので，その規則は，人間が介在しなくても実行可能な「機械的」なものでなければならない． inference system

7 命題論理 構文論 意味論 推論システム 例題 魔宮の世界
例題　魔宮の世界 　命題論理の構文論，意味論，推論システムについて学ぶ．また，例題として，簡単なゲームの世界を見ておく．

8 命題論理の構文論（1/2）構文要素 命題論理の構文要素 論理定数： true ，false
構文要素を一定の規則で並べると論理式となる． 命題論理の構文要素 論理定数：　true ，false 命題記号：　それ以上分解できない命題（原始命題） 　　　　　　　　を表す記号．p, q, r など． 論理記号：　命題を結合して複合した命題を作る記号． 同値 等しい EQUIV 含意 ならば IMPLY 否定 でない NOT 選言 または OR 連言 かつ AND 　命題論理の構文論（文法）は，論理式を作るための正しい規則からなっている． 　まず，論理式を作るための素材ともいえる構文要素を覚えてほしい．これは，論理定数，命題記号，論理記号の３つに分類される．その説明はこのスライドに書かれているとおりである．

9 命題論理の構文論（2/2）論理式 論理式 論理定数 は論理式である． true false 命題記号 は論理式である．
論理式： 原始命題を論理記号でつないだ文． 論理式 論理定数　は論理式である． true false 命題記号　は論理式である． が論理式ならば，　　　　 　　は論理式である． ，　　が論理式ならば，以下の４つも論理式である． 　これらの構文要素を適切な規則にしたがって並べた記号列が文法的に正しい論理式である．その規則はこのスライドに書かれた４つである． その他に，カッコを適切に省略する規則がある．

10 命題論理の意味論（1/4）：解釈の概念 解釈 解釈 (interpretation)： 論理式を真偽に対応付ける写像 論理式 （構文領域）
真偽値 （意味領域） 解釈 　つぎに，文法的に正しい論理式が与えられたとして，それが何を意味するのかを決める意味論を見ていこう．ここでいう「意味」とは，命題論理の場合，その論理式が表している命題が「真」なのか「偽」なのかということである． 　その基礎となる概念は，論理式を真偽に対応付けるための解釈(interpretation)というものである．スライドの図のように，論理式の集合（構文領域と呼ぶ）と真偽値の集合（意味領域と呼ぶ）を考える．解釈とは，構文領域に含まれる論理式の１つ１つを意味領域に含まれる真偽値に対応付けるもの（写像）である．そのような対応は組合せに応じてたくさんあるので，解釈というものもたくさんあることになる． 　しかし，つぎのような条件によって，実際には，命題変数にのみ対応（意味）を決めることにして，それ以外の論理式に対する対応（意味）は自動的に決まるようにする．その仕組みは，つぎの２つの条件を満たすように解釈を定めることである． 　１つめの条件は，true という論理式にはT(真)を対応付け，falseという論理式にはF(偽)を対応付けるということである．この条件は，true, falseの常識的な意味付けを要求している． 　２つめの条件は，not, and, or, →，⇔の５つの論理記号を用いて作られた論理式の意味は，その中に含まれる命題変数の意味に基づいて，計算によって自動的に求めるということである．このスライドの例の場合，p にT(真)を対応付けているので，計算規則により，not p は必ずF(偽)に対応付けられる．その計算規則は，つぎのスライドで． 命題変数 p,q,.. の解釈だけは 自由に決められる．.

11 命題論理の意味論（2/4）：論理式の解釈 T F P Q P→Q P∨Q P∧Q Q P «
true の値はT（真）， false の値はF（偽） 　　　 　　　　の値は　　の値の逆． 　の値は，以下の真理値表に基づいて決める． T F P　 Q P→Q P∨Q P∧Q Q P 　このスライドがその計算規則である．これを使うと，どんな複雑な論理式の値も命題変数の値に基づいて計算することができる．

12 命題論理の意味論（3/4）：論理式の解釈 例 のとき のとき 　これは論理式の意味（真偽値）の計算例である．

13 命題論理の意味論（4/4）：論理的帰結 論理的帰結 (logical consequence) のすべてを真とするどんな解釈のもとでも
が真のとき， の論理的帰結　 は 　論理式P1,P2,...,Pnのすべてを真とするような任意の解釈のもとで論理式Qが真となるとき，QはP1,P2,...,Pnの論理的帰結(logical consequence)であるといい，このスライドのような表記をする． 　論理的帰結かどうかを判断する一般的な方法は，その定義にしたがって，つぎのようなものとなる． 　まず， P1,P2,...,Pnのすべてを真とする解釈をすべて求める．これは命題変数に真偽値を与えるすべての組合せについて，論理式の値を計算することによってできる．つぎに，それらの解釈ごとにQが真かどうかを計算する．どの解釈に対してもQが真ならば，定義によって，QはP1,P2,...,Pnの論理的帰結である．そうでなければ，Qは論理的帰結ではない． 　しかし，この方法は，組合せ的（指数関数的）な数（２の m 乗: mは命題変数の数）のすべての解釈について論理式の真偽を計算するので多くの手間が必要である．これから学ぶ推論システムを用いればそのような手間を軽減して結論を導くことができる場合がある．

14 KB KB 命題論理の推論システム（1/5）：推論規則 状態遷移 前提 結論 推論システム＝推論規則の集まり 推論規則
前提がすべて知識ベース（ＫＢ）に入っていたら， 結論をＫＢに追加してよい． KB KB 　最後に，命題論理の推論システムについて見ていこう．推論システムは，推論規則の集まりからなっている．推論規則は，スライドのように，一見，分数のように見える形式で表現される．横線の上にある論理式を前提，横線の下にある論理式を結論という．いま、いろいろな知識が論理式の形式で知識ベース（ＫＢ）に格納されているとしよう。推論規則の意味は，「前提がすべてＫＢに入っていたら，結論をＫＢに追加してよい」ということである．これにより，ＫＢの状態が遷移することになる． 状態遷移

15 命題論理の推論システム（2/5）：モーダス・ポネンス
P, Q はKB内の論理式（命題）そのものではなく，それらを値としてとる変数（命題変数）を表している． KB KB Glitter→Gold Glitter→Gold Glitter 　実際には，推論規則内に書かれている変数は，KB内の論理式（命題）そのものではなく，それらを値としてとる変数（命題変数）を表している．たとえば，スライドに書かれている「モーダス・ポネンス」という推論規則は，「ＫＢ内に知識Ｐおよび知識Ｐ→Ｑが含まれていれば，知識ＱをＫＢに追加してよい」という意味だが，実際には，このスライドにあるように，知識 Glitter と知識 Glitter→Gold から知識 Gold を推論するために使うことができる． Glitter Gold 輝くものは黄金である． それは輝いている． それは黄金である．

16 命題論理の推論システム（3/5）：健全性 推論規則 は， を満たすとき，健全 (sound) であるという． の論理的帰結 は
の論理的帰結　 は 　推論規則は，その結論が前提の論理的帰結であるとき，健全(sound)であるという．すなわち，その前提がすべて真であるときに，結論もまた必ず（いかなる解釈によっても）真であるということである． のすべてを真とする どんな解釈のもとでも が真

17 命題論理の推論システム（4/5）：健全な推論規則
例 モーダス・ポネンス は，健全な推論規則である． （４通りの解釈について確認せよ） 例 逆は真なり 　すでに見たモーダス・ポネンスは健全な推論規則である．それを確かめるには、P, Q に与える４通りの解釈 (P,Q) =(T,T),(T,F),(F,T),(F,F)のそれぞれについて、前提P, P→Q がTならば、結論QもまたTであることを確認すればよい．実際、前提P, P→Q がTである解釈は(P,Q) =(T,T)のみであり、このとき確かにQ=Tとなる． 　「逆は真なり」は健全な推論規則ではない．P=F, Q=T という解釈を考えると，前提 P→Q はTだが，結論Q→PはFだからである． は，健全ではない． （逆は真とは限らぬ．P =F，Q =T のときを考えよ）

18 命題論理の推論システム（5/5）：その他の推論規則
以下の推論規則は，いずれも健全である 対偶 三段論法 ∧導入 ∧除去 ∨導入 ∨除去 　この授業では，健全な推論規則のみに興味がある．このスライドに示す６つの推論規則は，いずれも健全である．この他にも健全な推論規則は，たくさんある．

19 例題 魔宮の世界(1/11) 舞台と登場人物 格子の世界 (grid world) 落とし穴 黄金 ４ モンスター ３ ２ エージェント １
例題　魔宮の世界(1/11) 舞台と登場人物 格子の世界 (grid world) 落とし穴 黄金 ４ モンスター ３ ２ エージェント 　例題として，図のような「魔宮の世界」を考えよう． 　舞台はある洞窟をモデル化した４×４の格子からなっている．ＡＩの研究では，このようなモデルが良く用いられることが多く，一般に，格子の世界（grid world）と呼ばれている． 　登場人物は，「エージェント」と「モンスター」．そして，人物ではないが，「黄金」と「落とし穴」というオブジェクトが登場する． １ １ ２ ３ ４

20 魔宮の世界(2/11) アクションとゴール アクション 上下左右のいずれかに １マス進む 黄金を拾う 洞窟から脱出する ゴール
上下左右のいずれかに 　１マス進む 黄金を拾う 洞窟から脱出する ゴール モンスターと落とし穴を避けながら黄金を拾って，出発点に戻って脱出する 　　エージェントがとることのできる行為（アクション）はスライドに示されているとおりである．基本的には，上下左右のいずれかに１マス進むことを繰り返す．黄金のあるマスまで来るとそれを拾う．その後，出発地点まで戻り，洞窟から脱出する． 　　エージェントのタスク（ゴール）は，モンスターと落とし穴を避けながら黄金を拾って，出発点に戻って脱出することである．

21 魔宮の世界(3/11) エージェントのセンサー モンスターのいる部屋およびそれに隣接した部屋では 異臭 (Stench) を感じる
魔宮の世界(3/11)　エージェントのセンサー モンスターのいる部屋およびそれに隣接した部屋では 異臭 (Stench) を感じる 壁にぶつかると 衝撃 (Bump) を感じる 黄金のある部屋では 黄金の光 (Glitter) を感じる 　　エージェントはつぎのような知覚能力（センサー）によって，自分の置かれている環境の情報の一部を知ることができる． 　(1)モンスターのいる部屋およびそれに隣接した部屋では異臭 (Stench) を感じる． 　(2)穴のある部屋およびそれに隣接した部屋では風 (Breeze) を感じる． 　(3)黄金のある部屋では黄金の光 (Glitter) を感じる． 　(4)この世界の周囲を囲んでいる壁にぶつかると衝撃 (Bump) を感じる． 穴のある部屋およびそれに隣接した部屋では 風 (Breeze) を感じる

22 魔宮の世界(4/11) シミュレーション ４ ３ ２ １ １ ２ ３ ４ (1,1)には異臭も風もない → (1,2),(2,1)はOK
魔宮の世界(4/11)　シミュレーション ４ ３ ２ OK １ 　では，エージェントがどのような判断のもとで行動したらよいか，考えてみよう． 　まず，(1,1)には異臭も風もないので，(1,2),(2,1)はOKである．エージェントは，その事実を記憶する．スライドでは，OKを表すマークを図に記入して，エージェントの記憶の状態を表示している． １ ２ ３ ４ (1,1)には異臭も風もない　→　(1,2),(2,1)はOK

23 魔宮の世界(5/11)　シミュレーション OK ４ ３ PIT ? ２ １ 　エージェントは(2,1)に進んだとしよう．そこで風を感知するので， 　　　(2,2)または(3,1)に落とし穴がある ということがわかる．エージェントはそれを記憶する．スライドでは， (2,2)および(3,1)のそれぞれに「落とし穴があるかもしれない」ことを表すマークを記入している． １ ２ ３ ４ (2,1)で風を感知　→　(2,2)または(3,1)に落とし穴がある

24 魔宮の世界(6/11) シミュレーション ４ ３ PIT ? ２ １ １ ２ ３ ４ (1,1)を経由して，(1,2)へ進む OK
魔宮の世界(6/11)　シミュレーション OK ４ ３ PIT ? ２ １ 　(2,2)と(3,1)は危険なので，エージェントは，安全とわかっている(1,1)を経由して，(1,2)へ進む． １ ２ ３ ４ (1,1)を経由して，(1,2)へ進む

25 魔宮の世界(7/11) シミュレーション ４ ３ PIT ? ２ MONSTER １ １ ２ ３ ４
魔宮の世界(7/11)　シミュレーション OK ４ ３ PIT ? ２ MONSTER １ 　(1,2)で異臭を感知するので， 　　　　　(1,1)or(2,2)or(1,3)にモンスターがいる ということがわかる．しかし，実際には， 　　　　　(1,1)にはモンスターはいない 　　　　　(2,2)にはモンスターがいるはずはない ということがわかる．なぜなら，(1,1)はさきほどまでいた場所であり，また，(2,2)にもしモンスターがいるなら，さきほど行った(2,1)で異臭を感じたはずだからである． 　ゆえに， 　　　　　(1,3)にモンスターがいる ということがわかる．スライドには，そのマークを記入してある． １ ２ ３ ４ (1,2)で異臭を感知　→　(1,1)or(2,2)or(1,3)にモンスターがいる (1,1),(2,2)にモンスターはいない　→　(1,3)にモンスターがいる

26 魔宮の世界(8/11) シミュレーション ４ ３ PIT ? PIT ２ MONSTER PIT １ １ ２ ３ ４
魔宮の世界(8/11)　シミュレーション OK ４ ３ PIT ? PIT ２ MONSTER PIT １ 　また，(1,2)に風がないことから， 　　　　　(2,2)には落とし穴がない ということがわかる．ところで，すでに３枚前のスライドで 　　　　　(2,2)または(3,1)に落とし穴がある ということがわかっていた．(2,2)には落とし穴がないことがわかったので， 　　　　　(3,1)に落とし穴がある ということがわかる． １ ２ ３ ４ (1,2)に風がない　→　(2,2)に落とし穴がない 　　　　　　　　　　　→　(3,1)に落とし穴がある

27 魔宮の世界(9/11) シミュレーション ４ ３ PIT ? PIT ２ MONSTER １ １ ２ ３ ４ （途中省略）
魔宮の世界(9/11)　シミュレーション OK ４ ３ PIT ? PIT ２ MONSTER １ 　その後，エージェントは安全が保証された(2,2)へ進み，（その後，いったん(3,2)へ進んでも，また(2,2)へ戻ってきて，）安全とわかっている(2,3)へ進んで黄金を手に入れることになる． １ ２ ３ ４ （途中省略） (2,3)まで進んで黄金を拾う

28 魔宮の世界(10/11) 命題論理による知識表現 背景知識 (1,2) にモンスターがいるなら，(1,1) で異臭を感じる
魔宮の世界(10/11)　命題論理による知識表現 背景知識 (1,2) にモンスターがいるなら，(1,1) で異臭を感じる (1,2) に落とし穴があるなら，(1,1) で風を感じる (1,2) にモンスターも落とし穴もないなら，(1,2) はOK 事実 (1,1) で異臭を感じない 　この例題においては， 　　- 異臭とモンスター，および風と落とし穴を結び付ける一般的な知識（背景知識） 　　- 現場でセンサー入力から得たその場限りの知識（事実） を論理的に組み合わせて推論を行うことによって， エージェントは適切な行動を決定することができている． 　命題論理を用いて，背景知識と事実の一部を記述すると，このスライドのようになる．（それぞれの命題記号の意味は説明しないが，自明であろう．） (1,1) で風を感じない

29 魔宮の世界(11/11)：推論システムによる推論
推論規則 (4)と(1)より (5)と(2)より 　いま記述した５つの知識から，(1,2)が安全であることを，推論システムを用いて，機械的に導くことができる． (6),(7)と(3)より ゆえに (1,2) は安全（進んでもＯＫ）．