研究テーマ: 状況・状態把握技術

第4回
推 論(2)
1
知識表現の種類と特徴-7(再)
述語論理(predicate calculus, logic)
種々の知識を表現するための形式的言語
~ 第1階述語論理
知識を記号の式として数学的に表現
cf)述語: 真偽判定可能な叙述
例) (∀X)(elephant(X) → color(X, gray))



理論的基盤が保証されている
導出原理(resolution principle)による推論
人間の持つ曖昧性を組み込むことが困難
2
述語論理表現に用いる記号






定数
変数
関数記号: plus(X, Y)
述語記号: red(X)、study(x, school, English)
論理結合子:
-連言(conjunction): ∧ 選言(disjunction): ∨
-否定(negation): ¬
含意(implication): →
束縛(量)記号:
-全称記号: ∀
存在記号: ∃
3
融合法(背理法)
一階述語論理の論理式が充足不能(恒偽)かどう
かを判定する部分的決定手続き
1.
冠頭標準形への変換
2.
Skolem標準形への変換
3.
融合の実行

代入

単一化

融合節の生成

空節の導出 ~ 矛盾生成
4
融合法(背理法)の原理
対象領域D, 論理式M[x]に対し,
∀x [M[x]]が真であることを示すのは困難
一方,
∃a∈Dに対し, M[a]が偽であることを示せば
恒偽式であることは示せる
5
節形式




素(原子)命題: 述語記号と項から構成される命題
リテラル(literal): 素命題、または素命題の否定
節(clause): リテラル、またはリテラルの選言
節形式命題:
(∀x1) (∀x2) ・・ (∀xn)[C1∧C2 ∧ ・・∧Cm]
[]内: 母式(matrix)
6
節形式への変換-1
冠頭標準形:論理式F:


(Q1x1)・・・(Qnxn)α
(Q1x1)・・・(Qnxn):冠頭部α:本体 Qi:束縛子
P → Qを¬P∨Qに、
A≡Bを( ¬A∨B)∧( ¬B∨A)に変換
否定記号の括り出し: ¬(¬A)=A
¬(A∧B)= ( ¬A∨¬B)
¬(A∨B)= ( ¬A∧¬B)
¬ ((∀x)α)= (∃x)(¬α)
¬ ((∃x)α)= (∀x)(¬α)
7
節形式への変換 -2
Skolem標準形への変換


連言標準形へ変換
存在記号∃の除去:
(∀x) (∃y)P(x,y) = (∀x) P(x, f(x))
f(x): Skolem関数
存在記号を含む変数を引数とする新しい関数
で置き換えたもの
8
第9回 一階述語論理
[email protected]
節形式への変換 -3
1.
分配法則を用いて、母式を
選言の連言結合形に変換:
(A∧B)∨(B∧C)=(A∨B)∧ (B∨C)∧B∧(A∨C)
P∨(Q∧R)=(P∨Q)∧(P∨R)
P∧(Q ∨ R)=(P∧Q)∨(P∧R)
2.節集合への変換:
P ∨ Q ∨ ¬ R ⇒ {P, Q, ¬ R}
(A∨B)∧ (B∨C)∧B∧(A∨C) ⇒
{{A,B}, {B,C}, {B}, {A,C}}
9
融合法による推論-1

節の統合 ~ 節集合に変換する前
基本:(P, P→Q)⇒Q (P→Q, Q→R)⇒ P→R
例: C1 = L∨M1∨M2 ・・ ∨Mk
C2 = ¬L∨N1∨ N2 ・・ ∨Nl の統合
(¬M1∧ ~M2∧ ・・ ∧ ~Mk) → L 及び
L → (N1∨ N2 ・・ ∨Nl )
⇒ (¬M1∧ ¬M2∧ ・・ ∧ ¬Mk) → (N1∨ N2 ・・ ∨Nl )
⇒ M1∨M2 ・・ ∨Mk∨ N1∨ N2 ・・ ∨Nl = C3
10
融合法による推論-2

単一化(unification)
複数のリテラルの変数に適当な項を置換・代入
することにより、全てのリテラルを同一化すること
置換(substitution) s=P/Q: 変数QをPで置換える
こと ← 全称記号∀のみなのでOK
例)P(y, f(x))とP(a,z)の単一化
s1=a/y: P(y, f(x)) ⇒ P(a, f(x)), P(a,z)不変
s2=f(x)/z: P(a, z) ⇒ P(a, f(x)) で一致
11
融合法による推論-3

融合節の生成・空節の導出
← 導出原理(resolution principle)
目標の否定を前提に加えた節の集合から
導出・単一化を繰り返すことにより、矛盾
(空節)を導く
12
融合法による推論例
前提S: A(x, b, c)∨B(x)
¬A(g(a), y, z)
¬B(v)∨ C(y, f(u))
目標: C(b, f(h(y)))
[解法]
目標の否定¬C(b, f(h(y)))を前提Sに加えて
NILを導出: 一通りとは限らない
13
融合法による推論の例(結果)
¬
P∧¬P=空
¬
¬
14
不確実な事実・知識による推論


例外(非単調性)に起因する不確実性:
- サーカムスクリプション
- デフォルト推論
曖昧さに起因する不確実性:
- 信頼性係数(CF:Certainty Factor)
- ファジィ理論
- Dempster-Shafer(DS)理論
15
非単調論理による推論
論理体系の単調性:
A⊂B ならば Th(A) ⊂Th(B)
X: 矛盾の無い命題(公理)の集合
Th(X): Xから証明される定理の集合
*拡張: 公理系に推論規則を適用することにより
論理式の集合(定理群)を得ること
非単調論理(non-monotonic logic):
単調性が成立しない論理体系
←例外を含む知識(常識・・)が存在、・・
16
例外への対処


知識の適用対象を限定することによる
古典(述語)論理への帰着:
- サーカムスクリプション
様相記号の導入による古典論理の拡張:
- デフォルト推論
17
閉世界仮説とサーカムスクリプション
閉世界仮説(closed world assumption):
¬P(x)が証明できなければP(x)は真とする
~ 実世界では不成立、人間の通常の推論過程
サーカムスクリプション(極小限定) :
述語P(x)に関する命題A(P)が成立している場合
A(φ)∧(∀x)[{φ(x)∧ ¬E(φ)} → P(x)] →
(∀x) [P(x) →φ(x)] E:例外
18
閉世界仮説とサーカムスクリプションの例
P≡BLOCK:
(∀x)[BLOCK(x)→(x=a∨x=b∨x=c)]:閉世界仮説
A(φ)∧(∀x)[φ(x) → BLOCK(x)] →
(∀x) [BLOCK(x) →φ(x)]
ここでφ(x) ≡ (x=a ∨x=b ∨ x=c)とすれば、
(∀x)[(x=a ∨x=b ∨ x=c) → BLOCK(x)] →
(∀x)→[BLOCK(x)(x=a ∨x=b ∨ x=c)]
φ(x)≡RED (x)とすれば、
[RED(a)∧RED(b)∧RED(c)] ∧(∀x)[RED(x) → BLOCK(x)]
→(∀x) [BLOCK(x) →RED(x)]
19
デフォルト推論
Pが成立ち、¬Qが証明されていなければ、
Rが成立つ; P:MQ
R
P:前提 Q:仮定 R:帰結 M:様相記号
正規デフォルト規則: P:MQ
Q
拡張: 公理系に推論規則を適用することにより
論理式の集合(定理群)を得ること
- 多重拡張 ~ 拡張結果が複数通り出現
- 演繹結果が規則の適用順序に依存
20
デフォルト推論の例
鯨(x) → 脊椎動物(x)
鯨(x) → ¬翼がある(x)
哺乳類(x) → ゆったり
鯨(x) → 水棲(x)
(x)
鯨(x) → 恒温動物(x)
¬翼がある(x) → ¬飛ぶ(x)
哺乳類(x) → ¬魚類(x)
鯨(x) → ゆったり(x)
恒温動物(x) ∧¬飛ぶ(x):M哺乳類(x)
哺乳類(x)
21
信頼性係数による推論
血液感染症診断支援・MYCINで最初に導入
 後向き推論の効率化に有効
 理論的裏付けに乏しい
 更新規則:前件(左辺)C1*C2 ・・、 後件(右辺)A
CF(右辺)= CF(左辺) CF(規則)
CF(C1∧C2 ・・ ∧Ck)=min(CF(Ci ) )
CF(C1∨C2 ・・ ∨Ck)=max(CF(Ci ) ) ~当初
その後は、 =CF(C1)+CF(C2)(1-CF(C1))・・

22
MYCINにおける知識の例


事実型:
・培養基の場所は血液である(1.0)
・培養基の菌は好気性である(0.25)
・培養基の菌は大腸菌である(0.75)
(): 確信度
プロダクションルール型:
もし
感染症の種類が一次敗血症であり、
培養基の場所が無菌の場所であり、
培養された菌の入口が胃腸管と推定される
ならば、
その菌はバクテロイドである兆候がある(0.7)
23
MYCINにおける推論の例
0.4+0.54(1.0-0.4)=0.72
後向き推論:
結論を仮定して、
ルールの前件部を
チェックすることにより、
結論の確からしさを
チェック
0.5+0.8(1.0-0.5)=0.9
24
第12回
不確実性の取り扱い
[email protected]
ベイズネットワークにおける確率推論
ベイズの定理に基づく不確実な情報に
基づく推論
確率変数間の依存関係に関する知識を
グラフとして保持・更新
・ノード: 確率変数
・アーク: ノード間の因果関係の存在
25
第12回
不確実性の取り扱い
[email protected]
確率集合関数
コルモゴロフの公理系
 P(E)≧0
 P(Ω) =1
Ω:基礎空間(事象の全体集合)
 Fi が互いに独立(素)の時
P(F1∪F2 ∪・・ ∪Fk) = P(F1) + P(F2 ) +・・ +P(Fk)
26
第12回
不確実性の取り扱い
[email protected]
基本的な性質
1.
2.
3.
4.
P(φ)= 0
φ:空集合
E⊇Fの時 P(E)≧P(F)
P(Ec)=1 - P(E)
Ec :Eの補集合≡Ω- E
P(E∪F)=P(E)+P(F)- P(E∩F):
確率の加法公式
27
第12回
不確実性の取り扱い
[email protected]
条件付確率と乗法定理
事象E,Fに関して,
条件付確率:
P(E/F) = P(E∩F)/P(F)
確率の乗法公式:
P(E∩F)= P(F) P(E/F) = P(E) P(F/E)
●E,Fが独立の時,
P(E∩F)= P(E) P(F)
28
第12回
不確実性の取り扱い
[email protected]
ベイズの定理
Fi が互いに独立(素),かつ
F1∪F2 ∪・・ ∪Fk= Ω
P(E) = P(E/F1)P(F1)+ P(E/F2)P(F2) +・・・
+ P(E/Fk)P(Fk)
ベイズの定理:
P(Fi/E) = P(E/Fi)・P(Fi) / P(E)
= P(E/Fi)・P(Fi) / {P(E/F1)P(F1)+
P(E/F2)P(F2) +・・・+ P(E/Fk)P(Fk) }
29
第12回
不確実性の取り扱い
[email protected]
ベイジアンネットの性質



ネットワークにおける全ての変数に対し,その親
に条件付けされた各ノードの結合確率を規定す
るだけでOK
以上で規定された条件付き確率は大域的に無
矛盾であることが保証
各ノードにおける条件付き確率の集合は
ネットワークにおける全てのノードの唯一の結合
確率分布を規定
確率変数:{真,偽}
30
第12回
不確実性の取り扱い
[email protected]
ベイズネットワークの例
「ボーナス」-「収入」:
ボーナスが真のとき,
収入が真の確率0.8
偽の確率0.2
ボーナスが偽のとき,
収入が真の確率0.3
偽の確率0.7
31
第12回
不確実性の取り扱い
[email protected]
ベイズネットワークのアルゴリズム
1.
2.
3.
観測された変数の値をノードにセット
親ノードも観測値も持たないノードには
事前確率分布を付与
確率を伝播し,知りたい対象の変数Xの
事後確率を計算
32
第12回
不確実性の取り扱い
[email protected]
ベイズネットワークの例:確率計算
P(収入)=P(収入/ボーナス)・P(ボーナス)+ P(収入/¬ボーナス)・P(¬ボーナス)
=0.8・0.6 + 0.3・(1.0-0.6) = 0.6
P(旅行)=P(旅行/収入)・P(収入)+ P(旅行/¬収入)・P(¬収入)
=0.2・0.6 + 0.5・(1.0-0.6) = 0.32
33
ファジイ理論による推論

米・L.A.Zadehが提案 (1965)
確からしさを0~1の実数値で表現:主観

membership(所属度)関数による連続表現

μ(f(x)∧g(y))=min{μ(f(x)), μ(g(y)) }
μ(f(x)∨g(y))=max{μ(f(x)), μ(g(y)) }
34
推論の例(エアコンの制御)



温度30度のときの目盛?
快適 → 切る
やや暑い → 弱にする
暑い → 強にする
35
推論結果(エアコンの制御)
温度30度
大きい方を選択
(1x0.4+2x0.4+
3x0.2+4x0.6+
5x0.6)/(0.4+0.4+
0.2+0.6+0.6)
=3.3
36