document

エージェントアプローチ
人工知能８章・９章
B4 片渕
08/07/24
1
目次(第２版)

第８章一階述語論理

第９章一階述語論理による推論
2
８章：一階述語論理
目次




論理ごとの相違
一階述語論理
一階述語論理の使い方
まとめ
3
８章：一階述語論理
目次




論理ごとの相違
一階述語論理
一階述語論理の使い方
まとめ
4
論理ごとの相違

オントロジ的立場
－各論理が推論をする際に仮定する事項
・命題論理では「事実」のみを扱う
部屋[1,1]に穴はないetc

認識論的立場
－エージェントが事実に対しての認識方法
・命題論理では「真/偽/不定」で認識
5
形式言語（論理）ごとの
オントロジ的立場と認識論的立場
言語（論理）
オントロジ的立場
認識論的立場
命題論理
事実
真/偽/不定
一階述語論理
事実、オブジェクト真/偽/不定
関係
事実、オブジェクト真/偽/不定
関係、時間
事実
信念の強さ
時制論理
確率論
ファジィ論理
真偽の度合いを
持つ事実
既知の区間値
6
一階述語論理
命題論理との相違

オブジェクト
－推論に影響を及ぼす要素（名詞）
例：部屋、wumpus、穴etc

関係
－オブジェクト間の関係（動詞）
例：「風が吹いている」、「隣接している」etc

関数入力からただ一つの値が求まるようなもの
例：「最大の～」、「１つ上の～」etc
7
８章：一階述語論理
目次




論理ごとの相違
一階述語論理
一階述語論理の使い方
まとめ
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
８章：一階述語論理
目次




論理ごとの相違
一階述語論理
一階述語論理の使い方
まとめ
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
８章：一階述語論理
目次




論理ごとの相違
一階述語論理
一階述語論理の使い方
まとめ
19
まとめ

一階述語論理はオブジェクトとその関係を表現
定数記号（オブジェクト）、述語記号（関係）、関数記号
一般則の表現：限量子（∀・∃）

一階述語論理によって表現力が増した


20
ここまで８章

ここから９章
21
９章：一階述語論理による推論
目次






命題論理化
単一化
前向き連鎖
後ろ向き連鎖
一階述語論理における融合法
まとめ
22
９章：一階述語論理による推論
目次






命題論理化
単一化
前向き連鎖
後ろ向き連鎖
一階述語論理における融合法
まとめ
23
命題論理への帰着

一階述語論理命題論理への変換ができれば
命題論理での推論が可能
－命題論理化
・限量子の無い文に変換
24
命題論理化

全称具現化：全称限量（∀）の無い文に変換
例： ∀x Student(x) ⇒ Human(x)
※知識ベース
・Student(Tom)⇒Human(Tom) にある語彙
・Student(Bob)⇒Human(Bob) 全てについて

存在具現化：存在限量（∃）の無い文に変換
例： ∃x Brother(x,Bob)
※C1が知識ベース
に無いことが条件
・Brother(C1,Bob)
スコーレム定数
25
９章：一階述語論理による推論
目次






命題論理化
単一化
前向き連鎖
後ろ向き連鎖
一階述語論理における融合法
まとめ
26
単一化

KB内の２つの文を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
９章：一階述語論理による推論
目次






命題論理化
単一化
前向き連鎖
後ろ向き連鎖
一階述語論理における融合法
まとめ
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
９章：一階述語論理による推論
目次






命題論理化
単一化
前向き連鎖
後ろ向き連鎖
一階述語論理における融合法
まとめ
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
９章：一階述語論理による推論
目次






命題論理化
単一化
前向き連鎖
後ろ向き連鎖
一階述語論理における融合法
まとめ
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
９章：一階述語論理による推論
目次






命題論理化
単一化
前向き連鎖
後ろ向き連鎖
一階述語論理における融合法
まとめ
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

Download Report