今回からは 知識と推論 と題し, エージェントがタスクをこなすために必要な実世界に関する知識をコンピュータ内で知識ベースとして表現し, それらの知識を連携させる推論技術によって新しい知識を導き出し, エージェントの問題解決や意志決定に役立てる技術を学ぶ. 特に今回の授業では 論理 による知識の表現方法と推論方式について学ぶ. まず, 人工知能と論理の関係を理解した後, いろいろな論理と推論方式があることを見る. また, 論理を取り扱う際の学術的な枠組みとして, 構文論, 意味論, および推論システムを明確に定義する必要があることを理解する. つぎに, 論理の具体的かつ最も簡単な例として命題論理を取り上げ, その構文論, 意味論, および推論システムを学び, 例題として, 簡単なゲームの世界を見ておく. 1
これまで学んできた 探索 による問題解決手法では, 問題を初期状態オペレータ ( 行為 ) ゴール検査経路コストの4つの情報で規定し, おもに探索アルゴリズムの性能を議論してきた. しかし, ここでは, 状態 や 行為の結果( 状態遷移 ) をどのように記述したら良いか, という問題が置き去りにされている. 探索アルゴリズムにおいては, 状態とは抽象的なものであり, たとえば, 整数によって表現された一連番号であってもかまわないし, また, それ以上のことを必要ともしていない. しかし, 複雑な問題領域においては, 探索アルゴリズム以前の問題として, 解決すべき問題を探索問題として定式化すること自体が困難である. すなわち, 状態 をコンピュータで扱うためにどのように表現すれば良いのだろうか? また, 行為の結果 をどのように計算 ( あるいは推論 ) したら良いのだろうか? 明らかに, それらを適切に記述するための一般的な方法が必要である. その基盤となるのが, 論理 の一般的な考え方とそれを扱う技術である. 2
人工知能における 論理 の役割を説明しておく. 一般に, 人間がコンピュータに情報を与える 言語 といえば, すぐプログラミング言語が思いつく. それはコンピュータへの命令の列すなわちプログラムを具体的に記述したものである. しかし, そもそもAIの究極的な目的の1つは, そのようにいちいち命令しなくても, ふつうの言葉で意図を伝えれば, 自動的に適切な命令を組み立てて実行してくれる知的な情報システムを目指しているのである. そのようなAIシステムでは, コンピュータと人間が日本語や英語などの自然言語で対話することを理想としている. その言語は必ずしもコンピュータへの命令を表したものではなく,AIシステムに何らかの知識を与えたり, 解いて欲しい問題を与えたり, 質問したりするために使われる.AIシステムは獲得した知識を知識ベースと呼ばれる一種のデータベースに蓄える. ただ, 残念ながら, コンピュータが自然言語を理解するという技術はまだ開発途上にあり, 現状ではそれをじゅうぶんに利用することはできない. そこで何らかの人工的な言語で, 知識を与えたり, 問題を記述したり, 質問したりするための知識表現言語と呼ばれる類の言語が必要となる. そのようなものの一つが, 論理に基づく言語なのである. つまり, ここでは論理とは言語のことである. したがって, それを理解するには, 他のいろいろな言語を理解するのと同様に, 正しい文を生成するための文法規則 ( 構文論 ) や与えられた文を解釈する規則 ( 意味論 ) を理解する必要がある. つまり, 知識や問題を表現するという静的な側面が,AIにおける論理の第一の役割である. AIにおける論理の第二の役割は動的なものである.AIシステムは, 与えられた知識ベース内の複数の知識を使って, 新しい知識を動的に生成する機能が求められる. その機能を推論という. コンピュータに推論を行わせるアルゴリズムは, 論理的な推論規則に基づく推論システムとして定義される. したがって, ここでは論理とは推論アルゴリズムという計算手順を作り出すものとして働くことになる. 3
単に論理や推論といっても,AIではさまざまなものが考えられている. まず, 数学の試験問題を解くときのように, 問題を解決するための知識が正確ですべてそろっているとき, それは完全な知識であるという. そういう場合には, ギリシャ時代から発展してきて現在でも多くの科学で使われている標準的で数学的な論理と推論の方法がある. もっとも単純なのは, 命題の真偽を1つの記号で表現する命題論理 (propositional logic) である. それをやや複雑にしたものとして, 命題を, 主語や目的語を表現する名詞 ( オブジェクト ) とそれらの間の関係を表現する動詞 ( 述語 ) などに分解して, 複数の記号で1つの命題を構造的に表現する述語論理 (predicate logic) がある. そのほかにも, 英語の助動詞 must が表す必然性や can, may が表す可能性を扱うことができる様相論理 (modal logic) が研究されている. また, 時間の概念を論理的に表現し,always( いつも~である ) とか eventually( いつか必ず~となる ) のような表現を可能とする時相論理 (temporal logic) は, ハードウェアやソフトウェアの設計や検証にも用いられつつある. 4
実際の応用システムでは, 数学と異なり, すべての知識が正確であるとは限らない. そのような不確実な知識を扱うための推論手法として, ファジィ推論 (fuzzy reasoning) や確率推論 (probabilistic reasoning) がある. また, 知識が欠けているときの推論手法として, 帰納推論 (inductive reasoning) や仮説推論 (hypothetical reasoning) などがある. 特に, 帰納推論は,AI における知識獲得 (knowledge acquisition) や機械学習 (machine learning) の分野と密接に関係している. 5
このように, 一言で 論理 と言っても, 様々なものがある. それらの論理を規定する ( 区別する ) ものは, 構文論, 意味論, 推論システム である. 構文論 (syntax) は, その論理の定める 論理式 と呼ばれるものが, 記号をどのように並べたものなのかを定める規則である. すなわち, 記号の列が与えられたとき, それが 論理式 か否かを判定する規則( いわゆる 文法 ) である. 意味論 (semantics) は, 論理式の意味を理解するための規則である. 論理では, 興味のある 意味 とは 真か偽か ということなので, 意味論は, 与えられた論理式の真偽を判定する規則となる. 推論システム (inference system) は,( 一般に複数の ) 論理式が与えられたとき, それを 前提 として, 結論 として言える論理式を導く( 推論する ) ための規則である. コンピュータを使って推論をさせるので, その規則は, 人間が介在しなくても実行可能な 機械的 なものでなければならない. 6
命題論理の構文論, 意味論, 推論システムについて学ぶ. また, 例題として, 簡単なゲームの世界を見ておく. 7
命題論理の構文論 ( 文法 ) は, 論理式を作るための正しい規則からなっている. まず, 論理式を作るための素材ともいえる構文要素を覚えてほしい. これは, 論理定数, 命題記号, 論理記号の3つに分類される. その説明はこのスライドに書かれているとおりである. 8
これらの構文要素を適切な規則にしたがって並べた記号列が文法的に正しい論理式である. その規則はこのスライドに書かれた 4 つである. 9
つぎに, 文法的に正しい論理式が与えられたとして, それが何を意味するのかを決める意味論を見ていこう. ここでいう 意味 とは, 命題論理の場合, その論理式が表している命題が 真 なのか 偽 なのかということである. その基礎となる概念は, 論理式を真偽に対応付けるための解釈 (interpretation) というものである. スライドの図のように, 論理式の集合 ( 構文領域と呼ぶ ) と真偽値の集合 ( 意味領域と呼ぶ ) を考える. 解釈とは, 構文領域に含まれる論理式の1つ1つを意味領域に含まれる真偽値に対応付けるもの ( 写像 ) である. そのような対応は組合せに応じてたくさんあるので, 解釈というものもたくさんあることになる. しかし, つぎのような条件によって, 実際には, 命題変数にのみ対応 ( 意味 ) を決めることにして, それ以外の論理式に対する対応 ( 意味 ) は自動的に決まるようにする. その仕組みは, つぎの2つの条件を満たすように解釈を定めることである. 1つめの条件は,true という論理式にはT( 真 ) を対応付け,falseという論理式には F( 偽 ) を対応付けるということである. この条件は,true, falseの常識的な意味付けを要求している. 2つめの条件は,not, and, or,, の5つの論理記号を用いて作られた論理式の意味は, その中に含まれる命題変数の意味に基づいて, 計算によって自動的に求めるということである. このスライドの例の場合,p にT( 真 ) を対応付けているので, 計算規則により,not p は必ずF( 偽 ) に対応付けられる. その計算規則は, つぎのスライドで. 10
このスライドがその計算規則である. これを使うと, どんな複雑な論理式の値も命題変数の値に基づいて計算することができる. 11
これは論理式の意味 ( 真偽値 ) の計算例である. 12
論理式 P1,P2,...,Pnのすべてを真とするような任意の解釈のもとで論理式 Qが真となるとき,QはP1,P2,...,Pnの論理的帰結(logical consequence) であるといい, このスライドのような表記をする. 論理的帰結かどうかを判断する一般的な方法は, その定義にしたがって, つぎのようなものとなる. まず, P1,P2,...,Pnのすべてを真とする解釈をすべて求める. これは命題変数に真偽値を与えるすべての組合せについて, 論理式の値を計算することによってできる. つぎに, それらの解釈ごとにQが真かどうかを計算する. どの解釈に対してもQが真ならば, 定義によって,QはP1,P2,...,Pnの論理的帰結である. そうでなければ,Qは論理的帰結ではない. しかし, この方法は, 組合せ的 ( 指数関数的 ) な数 (2の m 乗 : mは命題変数の数 ) のすべての解釈について論理式の真偽を計算するので多くの手間が必要である. これから学ぶ推論システムを用いればそのような手間を軽減して結論を導くことができる場合がある. 13
最後に, 命題論理の推論システムについて見ていこう. 推論システムは, 推論規則の集まりからなっている. 推論規則は, スライドのように, 一見, 分数のように見える形式で表現される. 横線の上にある論理式を前提, 横線の下にある論理式を結論という. いま いろいろな知識が論理式の形式で知識ベース (KB) に格納されているとしよう 推論規則の意味は, 前提がすべて KB に入っていたら, 結論を KB に追加してよい ということである. これにより,KB の状態が遷移することになる. 14
実際には, 推論規則内に書かれている変数は,KB 内の論理式 ( 命題 ) そのものではなく, それらを値としてとる変数 ( 命題変数 ) を表している. たとえば, スライドに書かれている モーダス ポネンス という推論規則は, KB 内に知識 P および知識 P Q が含まれていれば, 知識 Q を KB に追加してよい という意味だが, 実際には, このスライドにあるように, 知識 Glitter と知識 Glitter Gold から知識 Gold を推論するために使うことができる. 15
推論規則は, その結論が前提の論理的帰結であるとき, 健全 (sound) であるという. すなわち, その前提がすべて真であるときに, 結論もまた必ず ( いかなる解釈によっても ) 真であるということである. 16
すでに見たモーダス ポネンスは健全な推論規則である. それを確かめるには P, Q に与える4 通りの解釈 (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だからである. 17
この授業では, 健全な推論規則のみに興味がある. このスライドに示す 6 つの推論規則は, いずれも健全である. この他にも健全な推論規則は, たくさんある. 18
例題として, 図のような 魔宮の世界 を考えよう. 舞台はある洞窟をモデル化した4 4の格子からなっている.AIの研究では, このようなモデルが良く用いられることが多く, 一般に, 格子の世界 (grid world) と呼ばれている. 登場人物は, エージェント と モンスター. そして, 人物ではないが, 黄金 と 落とし穴 というオブジェクトが登場する. 19
エージェントがとることのできる行為 ( アクション ) はスライドに示されているとおりである. 基本的には, 上下左右のいずれかに1マス進むことを繰り返す. 黄金のあるマスまで来るとそれを拾う. その後, 出発地点まで戻り, 洞窟から脱出する. エージェントのタスク ( ゴール ) は, モンスターと落とし穴を避けながら黄金を拾って, 出発点に戻って脱出することである. 20
エージェントはつぎのような知覚能力 ( センサー ) によって, 自分の置かれている環境の情報の一部を知ることができる. (1) モンスターのいる部屋およびそれに隣接した部屋では異臭 (Stench) を感じる. (2) 穴のある部屋およびそれに隣接した部屋では風 (Breeze) を感じる. (3) 黄金のある部屋では黄金の光 (Glitter) を感じる. (4) この世界の周囲を囲んでいる壁にぶつかると衝撃 (Bump) を感じる. 21
では, エージェントがどのような判断のもとで行動したらよいか, 考えてみよう. まず,(1,1) には異臭も風もないので,(1,2),(2,1) はOKである. エージェントは, その事実を記憶する. スライドでは,OKを表すマークを図に記入して, エージェントの記憶の状態を表示している. 22
エージェントは (2,1) に進んだとしよう. そこで風を感知するので, (2,2) または (3,1) に落とし穴がある ということがわかる. エージェントはそれを記憶する. スライドでは, (2,2) および (3,1) のそれぞれに 落とし穴があるかもしれない ことを表すマークを記入している. 23
(2,2) と (3,1) は危険なので, エージェントは, 安全とわかっている (1,1) を経由して, (1,2) へ進む. 24
(1,2) で異臭を感知するので, (1,1)or(2,2)or(1,3) にモンスターがいるということがわかる. しかし, 実際には, (1,1) にはモンスターはいない (2,2) にはモンスターがいるはずはないということがわかる. なぜなら,(1,1) はさきほどまでいた場所であり, また,(2,2) にもしモンスターがいるなら, さきほど行った (2,1) で異臭を感じたはずだからである. ゆえに, (1,3) にモンスターがいるということがわかる. スライドには, そのマークを記入してある. 25
また,(1,2) に風がないことから, (2,2) には落とし穴がないということがわかる. ところで, すでに3 枚前のスライドで (2,2) または (3,1) に落とし穴があるということがわかっていた.(2,2) には落とし穴がないことがわかったので, (3,1) に落とし穴があるということがわかる. 26
その後, エージェントは安全が保証された (2,2) へ進み,( その後, いったん (3,2) へ進んでも, また (2,2) へ戻ってきて,) 安全とわかっている (2,3) へ進んで黄金を手に入れることになる. 27
この例題においては, - 異臭とモンスター, および風と落とし穴を結び付ける一般的な知識 ( 背景知識 ) - 現場でセンサー入力から得たその場限りの知識 ( 事実 ) を論理的に組み合わせて推論を行うことによって, エージェントは適切な行動を決定することができている. 命題論理を用いて, 背景知識と事実の一部を記述すると, このスライドのようになる. ( それぞれの命題記号の意味は説明しないが, 自明であろう.) 28
いま記述した 5 つの知識から,(1,2) が安全であることを, 推論システムを用いて, 機械的に導くことができる. 29