エージェントアプローチ 人工知能 8章・9章 B4 片渕 08/07/24 1 目次(第2版) 第8章 一階述語論理 第9章 一階述語論理による推論 2 8章:一階述語論理 目次 論理ごとの相違 一階述語論理 一階述語論理の使い方 まとめ 3 8章:一階述語論理 目次 論理ごとの相違 一階述語論理 一階述語論理の使い方 まとめ 4 論理ごとの相違 オントロジ的立場 -各論理が推論をする際に仮定する事項 ・命題論理では「事実」のみを扱う 部屋[1,1]に穴はないetc 認識論的立場 -エージェントが事実に対しての認識方法 ・命題論理では「真/偽/不定」で認識 5 形式言語(論理)ごとの オントロジ的立場と認識論的立場 言語(論理) オントロジ的立場 認識論的立場 命題論理 事実 真/偽/不定 一階述語論理 事実、オブジェクト 真/偽/不定 関係 事実、オブジェクト 真/偽/不定 関係、時間 事実 信念の強さ 時制論理 確率論 ファジィ論理 真偽の度合いを 持つ事実 既知の区間値 6 一階述語論理 命題論理との相違 オブジェクト -推論に影響を及ぼす要素(名詞) 例:部屋、wumpus、穴etc 関係 -オブジェクト間の関係(動詞) 例:「風が吹いている」、「隣接している」etc 関数 入力からただ一つの値が求まるようなもの 例:「最大の~」、「1つ上の~」etc 7 8章:一階述語論理 目次 論理ごとの相違 一階述語論理 一階述語論理の使い方 まとめ 8 一階述語論理のモデル(一例) hat on head Tom brother Bob student right leg right leg 9 一階述語論理における統語論 定数記号 オブジェクトを記述 例:「Tom」、「Bob」 述語記号 関係を記述 例:「Brother」 「OnHead」「Student」etc 関数記号 関数を記述 例:「Hat」(hatを被っているのはBobのみ) 「Rightleg(Tom)」(Tomの右足) 10 一階述語論理における意味論 前述の記号に厳密に「解釈」を規定 例:Brotherは兄弟関係 Onheadは帽子が人の頭上にある関係 Studentは学生かどうか Humanは人間かどうか etc を規定 Brother(Tom,Bob)は トムとボブが兄弟の時、真を返す 11 論理結合子を用いた 一階述語論理の表現例 ¬Brother(Tom,Rightleg(Bob)) -トムとボブの右足は兄弟ではない Student(Tom)∨Student(Bob) -トムかボブのいずれかは学生である ¬Student(Tom) ⇒ Student(Bob) -トムが学生でなければボブは学生である 12 限量子 全称限量(∀) -全てのオブジェクトに関する記述を表現 例:∀x Student(x) ⇒ Human(x) x:変数 「全ての学生は人間である」 存在限量(∃) -世界に存在するオブジェクトに関する記述を表現 例:∃x Brother(x,Bob) 「ボブには兄弟が存在する」 13 一階述語論理における表明と質問 表明(TELL):文を知識ベース(KnowledgeBase,KB)に追加 例:TELL(KB,Student(Bob)) -文「Student(Bob)」をKBに追加 質問(ASK):文の真偽を知識ベースに質問 例:ASK(KB,Student(Bob)) -KBに文「Student(Bob)」があるのでtrueを返す 注: ASK(KB,∃x Student(x))は{x/Bob}を返す 代入:条件を満たすx 14 8章:一階述語論理 目次 論理ごとの相違 一階述語論理 一階述語論理の使い方 まとめ 15 一階述語論理の使い方 例: wumpus world 部屋に風が吹いていれば隣の部屋に穴が無け ればならない ∀s Breezy(s) ⇒∃r Adjacent(r,s)∧Pit(r) 部屋sで 風が吹く 部屋rは部屋sの 隣にある 部屋rに 穴がある ちなみに命題論理の場合 Bi,j ⇒ Pi-1,j-1∨ Pi-1,j+1∨ Pi+1,j-1∨ Pi+1,j+1 一階述語論理によって表現の幅が広がった 16 診断規則・因果規則 診断規則 -観測された結果から原因を導くもの ∀s Breezy(s) ⇒∃r Adjacent(r,s)∧Pit(r) 部屋に風が吹いていれば隣の部屋に穴が無ければならない 因果規則 モデルベース推論 -想定された因果関係から結果が導かれる ∀r Pit(r) ⇒ [∀s Adjacent(r,s)⇒Breezy(s)] 穴によって隣の部屋全てに風が吹く 17 おまけ:知識ベースの構築 (知識工学) タスクの特定 関連知識の収集 定数、述語、関数の語彙の決定 問題領域に関する一般的知識の記述 -例:「Americaは国である」etc 特定の問題例の記述 -例:「風が吹いていれば隣の部屋に穴がある」etc 推論手続きへの質問と答えの獲得 知識ベースのデバッグ 18 8章:一階述語論理 目次 論理ごとの相違 一階述語論理 一階述語論理の使い方 まとめ 19 まとめ 一階述語論理はオブジェクトとその関係を表現 定数記号(オブジェクト)、述語記号(関係)、関数記号 一般則の表現:限量子(∀・∃) 一階述語論理によって表現力が増した 20 ここまで8章 ここから9章 21 9章:一階述語論理による推論 目次 命題論理化 単一化 前向き連鎖 後ろ向き連鎖 一階述語論理における融合法 まとめ 22 9章:一階述語論理による推論 目次 命題論理化 単一化 前向き連鎖 後ろ向き連鎖 一階述語論理における融合法 まとめ 23 命題論理への帰着 一階述語論理命題論理への変換ができれば 命題論理での推論が可能 -命題論理化 ・限量子の無い文に変換 24 命題論理化 全称具現化:全称限量(∀)の無い文に変換 例: ∀x Student(x) ⇒ Human(x) ※知識ベース ・Student(Tom)⇒Human(Tom) にある語彙 ・Student(Bob)⇒Human(Bob) 全てについて 存在具現化:存在限量(∃)の無い文に変換 例: ∃x Brother(x,Bob) ※C1が知識ベース に無いことが条件 ・Brother(C1,Bob) スコーレム定数 25 9章:一階述語論理による推論 目次 命題論理化 単一化 前向き連鎖 後ろ向き連鎖 一階述語論理における融合法 まとめ 26 単一化 KB内の2つの文を1つの文にまとめる技法 -UNIFY(p,q)={代入} 例1:UNIFY(Brothers(Tom,x),Brothers(Tom,Bob)) ={x/Bob}(Brothers(Tom,Bob)に単一化) 例2:UNIFY(Brothers(Tom,x),Brothers(y,Bob)) ={x/Bob,y/Tom} (Brothers(Tom,Bob)に単一化) 同じ述語記号(含:引数の数)であることが条件 27 9章:一階述語論理による推論 目次 命題論理化 単一化 前向き連鎖 後ろ向き連鎖 一階述語論理における融合法 まとめ 28 前向き連鎖 できる限りの推論を行っていきゴールを目指す 例:「(1)アメリカ人が敵対国に武器を売るのは犯罪」 である。「(2)Nonoという国はアメリカの敵国」であり、 「(3)ミサイルを持っていて」、「(4)その全てがアメリカ 人のWestにより販売された」。 29 知識ベースへの格納(例題) (1)American(x)∧Weapon(y) ∧Sells(x,y,z)∧Hostile(z) ⇒ Criminal(x) (2)Hostile(Nono) (3)∃x Owns(Nono,x)∧Missile(x) 命題論理化(3.1)Owns(Nono,C1) (3.2)Missile(C1) (4)Missile(x)∧Owns(Nono,x) ⇒Sells(West,x,Nono) ※「ミサイルが武器」「Westはアメリカ人」という事実も格納 (5)Missile(x) ⇒ Weapon(x) (6)American(West) 30 前向き連鎖での推論(例) KBより「Westが犯罪者である」ことを証明 (3.1)(3.2)(4)より (7)Sells(West,C1,Nono) (3.2)(5)より (8)Weapon(C1) (1)(2)(6)(7)(8)より (9)Criminal(West) 31 前向き連鎖の証明木 Criminal(West) Weapon(C1) Sells(West,C1,Nono) American(West) Missile(C1) Hostile(Nono) Owns(Nono,C1) 32 9章:一階述語論理による推論 目次 命題論理化 単一化 前向き連鎖 後ろ向き連鎖 一階述語論理における融合法 まとめ 33 後ろ向き連鎖 ゴールが正しいことをKBの文を用いて証明していく 例:「Westが犯罪者である」ことを証明するには (1)より「American(West)」 KBに存在 「Weapon(y)」 「Sells(West,y,z)」 「Hostile(Nono)」 KBに存在 を証明する必要がある(以下同様) 34 後ろ向き連鎖の証明木 Criminal(West) Weapon(y) Sells(West,C1,z) {z/Nono} American(West) Missile(y) {y/C1} Hostile(Nono) Missile(C1) Owns(Nono,C1) 単一化によりMissile(C1)と同等になる 35 9章:一階述語論理による推論 目次 命題論理化 単一化 前向き連鎖 後ろ向き連鎖 一階述語論理における融合法 まとめ 36 一階述語論理における融合法 連言標準形(conjunctive normal form:CNF)への変換 -命題論理における融合規則を利用 (l1∨l2∨・・∨lk) ∧ (m1∨m2∨・・∨mk) l1∨・・∨li-1∨li+1∨・・∨lk∨m1∨ ・・∨mi-1∨mi+1∨・・∨mk 消去する相補リテラルについて -述語記号が同じで引数が異なる場合は単一化で消去 例:[P(Tom)∨Q(Tom,Bob)]∧[¬Q(x,y)∨R(Bob)] [P(Tom)∨R(Bob)] ({x/Tom, y/Bob}で単一化) 37 CNFへの変換方法(1/2) 条件文の消去 -∀x Missile(x) ⇒ Weapon(x) ∀x ¬Missile(x) ∨ Weapon(x) 負リテラル(¬)を限量子の内部に移す -¬∀x Criminal(x) ∃x ¬Criminal(x) 変数標準化:変数の混同を回避 -(∀x P(x) )∨(∃x Q(x) ) (∀x P(x) )∨(∃y Q(y) ) ホーン節 38 CNFへの変換方法(2/2) スコーレム化:(「∃」の削除) -∀x [∃y Brother(x,y)] ∀x Brother(x,F(x)) スコーレム関数 xに依存する ことを明示 全称限量子「∀」の削除 - ∀x Brother(x,F(x)) Brother(x,F(x)) ∧を∨に分配 -[P(x) ∧ Q(x)] ∨ R(x) [P(x) ∨ R(x)] ∧ [P(x) ∨ R(x)] CNF 39 融合法での推論(1/2) 例:犯罪例題 KB内の文をCNFに変換 (1) ¬American(x)∨¬Weapon(y) ∨ ¬Sells(x,y,z)∨¬Hostile(z) ∨ Criminal(x) (2)Hostile(Nono) (3.1)Owns(Nono,C1) (3.2)Missile(C1) (4)Missile(x)∧Owns(Nono,x) ⇒Sells(West,x,Nono) (5)¬Missile(x)∨Weapon(x) (6)American(West) ゴールの文の否定も追加(背理法で解く) (7)¬Criminal(West) 40 融合法での推論(2/2) 例:犯罪例題 融合規則により文を消去していく (1)∧(7) (Criminal(West)と¬Criminal(West)を消去) (8)¬American(x)∨¬Weapon(y)∨ ¬Sells(x,y,z)∨¬Hostile(z) (6)∧(8) ( American(West)と¬American(West)を消去) (9) ¬Weapon(y)∨ ¬Sells(x,y,z)∨¬Hostile(z) 最終的にHostile(x)∧¬Hostile(x)になる矛盾 41 9章:一階述語論理による推論 目次 命題論理化 単一化 前向き連鎖 後ろ向き連鎖 一階述語論理における融合法 まとめ 42 まとめ 命題論理化:一階述語論理を命題論理に変換 単一化:同じ述語を一つにまとめる 前向き連鎖:KBを基にできる限りの推論を行う 後ろ向き連鎖:ゴールから後ろ向きに証明する 融合法を用いる時は連言標準形に変換 -全ての一階述語論理はCNFに変換可能 43 おまけ: Prolog 一階述語論理に基づいた推論を行うプログラム言語 知識ベース 質問と回答 Student(Bob). Human(x) := Student(x). ?Human(Bob). true Student(Bob). Student(Tom). Human(x) := Student(x). ?Human(x). x=Bob ; x=Tom Student(x)⇒Human(x) 44
© Copyright 2025 ExpyDoc