エージェントアプローチ
人工知能 7章・8章
B4 片渕
08/07/18
1
始める前に・・・

読み進める本が第2版になりました

今後のスケジュールも第2版に従います
2
目次(第2版)

第7章 論理的エージェント

第8章 一階述語論理
3
第7章 論理的エージェント
目次






論理的エージェントとは
論理とは
命題論理とは
命題論理における推論
命題論理エージェント
まとめ
4
第7章 論理的エージェント
目次






論理的エージェントとは
論理とは
命題論理とは
命題論理における推論
命題論理エージェント
まとめ
5
論理的エージェントとは


知識に基づいて論理的に推論するエージェント
「知識」とは
-知識表現言語(という言語)で記述された文の集合
知識ベース(KB)
論理式

「論理的に推論する」とは
-「知識」から新たな結論を導くこと
6
第7章 論理的エージェント
目次






論理的エージェントとは
論理とは
命題論理とは
命題論理における推論
命題論理エージェント
まとめ
7
論理の構成要素

統語論
-記号間の関係(文法)を規定
例: ○ 「x+y=4」
× 「x4y+=」

意味論
-真理値を定義(真理値表)
例:「x+y=4」は x=2,y=2の時は真
x=1,y=1の時は偽
8
伴意関係

ある文が別の文に従うという関係
-「A╞ B」で表現
・文Aが真ならば文Bも真でなければならない

文「x+y=4」から文「4=x+y」が伴意される
9
第7章 論理的エージェント
目次






論理的エージェントとは
論理とは
命題論理とは
命題論理における推論
命題論理エージェント
まとめ
10
命題論理の構成要素

統語論
PやQで表現
-命題記号(真偽を判定する文)
-論理結合子(「かつ」、「または」etc)

意味論
-真理値表(真か偽か)
11
命題論理における統語論
(論理結合子)





¬(負リテラル):「¬P」は「Pの否定」
∧(連言):「P∧Q」は「PかつQ」
∨(選言):「P∨Q」は「PまたはQ」
⇒(条件文):「P⇒Q」は「PならばQ」
(前提)(結論)
⇔(双条件文):「P⇔Q」は「(P⇒Q)∧(Q⇒P)」
12
命題論理における意味論
(真理値表)
P
false
Q
false
¬P
true
P∧Q
false
P∨Q
false
false
true
true
false
true
true
false
false
false
true
false
false
true
true
false
true
true
true
true
P⇒Q
true
P⇔Q
true
true(※) false
※:前提が偽ならば結論がどうであれ真になる
13
第7章 論理的エージェント
目次






論理的エージェントとは
論理とは
命題論理とは
命題論理における推論
命題論理エージェント
まとめ
14
例題:wumpus world
•獣や落とし穴のある部屋に入らずに黄金の部屋を目指す
•隣の部屋から獣や落とし穴の気配を知覚することが可能
4
s
g
b
P
3
W
G
P
b
2
s
g
b
1
S
b
P
b
1
2
3
4
S:スタート
P:落とし穴
W:獣
G:黄金
s:獣の気配(臭い)
b:落とし穴の気配(風)
g:黄金の気配
15
知識ベース(KB)の構築(1/2)

例:wumpus worldの落とし穴に関するKB
-部屋[i,j]に落とし穴があればPijは真
-部屋[i,j]に風が吹いていればBijは真

上記の命題記号を用いて得られる情報を格納
16
知識ベース(KB)の構築(2/2)




部屋[1,1]には穴は存在しない
 ¬P11 (R1と呼ぶ)
隣の部屋に穴がある時に限り風が吹く
 B11⇔(P12∨P21) etc (R2と呼ぶ)
エージェントが訪れた部屋の情報も与える
 ¬B11、B21 etc (R3と呼ぶ)
この場合KBは「R1∧R2∧R3」とみなせる
17
推論とは

KBと伴意関係にある新たな文αを導出すること
-「KB╞ α」

例:¬P12は伴意されるか(wumpus world)
- ¬B11∧( B11⇔(P12∨P21) )
- (¬P12)∧(¬P21)  ¬P12

ちなみに¬P22はまだ伴意されない(真偽が不明)
18
推論アルゴリズムの
健全性・完全性

健全性
-KBから真なる文を導き出せるか
KB ╞ αを満たせば健全である

完全性
-KBから真なる全ての文を導き出せるか
伴意される限りのαを導き出せれば完全である
落とし穴だけでなく獣や宝の位置情報まで得られるか
19
妥当性・充足可能性

妥当性
-ある文が全ての場合において真かどうか
例:P∨¬Pは妥当である

充足可能性
-ある文が真になる場合が存在するかどうか
例:P∧¬Pは充足不能である
(α∧¬βが充足不能)⇔(α ╞ β)
20
命題論理における推論規則

推論をするための規則

例:モーダスポーネンス(三段論法)
α⇒β,α
β

KB
α
KB ╞ α
(α⇒β∧α) ╞ β
α:「片渕は人間だ」 β:「片渕はいつか死ぬ」 の場合
片渕が人間ならば片渕はいつか死ぬ
片渕は人間である
片渕はいつか死ぬ
21
命題論理における推論法
融合法

2つ以上の文を組み合わせて新たな文を導出
(P11 ∨ P13)∧(¬P11∨P22)
P13∨P22

P11と¬P11は
相補リテラル
融合規則
-論理記号の選言の連言から成る(連言標準形)
(l1∨l2∨・・∨lk) ∧ (m1∨m2∨・・∨mk)
l1∨・・∨li-1∨li+1∨・・∨lk∨m1∨ ・・∨mi-1∨mi+1∨・・∨mk
※liとmjは相補リテラル
22
ホーン節

高々1つの正リテラルを含むリテラルの選言
-「¬P∨¬Q∨R」

条件文に変換可能
-「¬P∨¬Q∨R」「P∧Q⇒R」

推論アルゴリズムの構築に役立つ
-前向き推論・後ろ向き推論
23
ホーン節を用いた推論

文Qがホーン節からなるDBから伴意されるか
データベース
P⇒Q
L∧M ⇒P
B∧L ⇒M
A∧P⇒L
A∧B⇒L
A(既知)
B(既知)
Q
既知の情報から
可能な限り
推論を行う
P
M
L
前向き推論
A
B
AND-ORグラフ
24
第7章 論理的エージェント
目次






論理的エージェントとは
論理とは
命題論理とは
命題論理における推論
命題論理エージェント
まとめ
25
命題論理エージェントの一例
(回路エージェント)

命題を回路図で表現(時間毎に情報を更新)
1ステップ遅延
A
∧
∧
B
∧
Q
∨
文Qが真かを決定する回路
26
第7章 論理的エージェント
目次






論理的エージェントとは
論理とは
命題論理とは
命題論理における推論
命題論理エージェント
まとめ
27
まとめ




推論とはKBから新たな文を導くことである
命題論理=命題記号+論理結合子
融合法では論理記号の操作で推論
ホーン節により推論を図で表現可能
28
ダウンロード

Document