第４回　 推 論（２）.

Presentation on theme: "第４回　 推 論（２）."— Presentation transcript:

1 第４回　 推 論（２）

2 知識表現の種類と特徴-７（再） 述語論理(predicate calculus, logic)
知識表現の種類と特徴-７（再）　 　述語論理(predicate calculus, logic) 種々の知識を表現するための形式的言語 ～　第１階述語論理 知識を記号の式として数学的に表現 cf）述語：　真偽判定可能な叙述 例）　(∀Ｘ)(elephant(X) → color(X, gray)) 理論的基盤が保証されている 導出原理(resolution principle)による推論 人間の持つ曖昧性を組み込むことが困難

3 述語論理表現に用いる記号 定数 変数 関数記号： plus(X, Y)
述語記号：　red(X)、study(x, school, English) 論理結合子：　 -連言(conjunction): ∧　選言(disjunction): ∨ -否定(negation): ￢　　　含意(implication): → 束縛（量）記号： -全称記号: ∀ 存在記号: ∃

4 融合法（背理法） 一階述語論理の論理式が充足不能（恒偽）かどうかを判定する部分的決定手続き 冠頭標準形への変換 Skolem標準形への変換
融合の実行 代入 単一化 融合節の生成 空節の導出　～　矛盾生成

5 融合法（背理法）の原理 対象領域D, 論理式M[x]に対し， 一方， ∀ｘ [M[x]]が真であることを示すのは困難
∃a∈Dに対し， M[a]が偽であることを示せば 　恒偽式であることは示せる

6 節形式 素（原子）命題： 述語記号と項から構成される命題 リテラル(literal)： 素命題、または素命題の否定
素（原子）命題：　述語記号と項から構成される命題 リテラル(literal)：　素命題、または素命題の否定 節(clause)：　リテラル、またはリテラルの選言 節形式命題：　 (∀x1) (∀x2) ・・ (∀xn)[C1∧C2 ∧ ・・∧Cm] []内：　母式(matrix)

7 節形式への変換-1 冠頭標準形：論理式F: (Q1x1)・・・(Qnxn)α (Q1x1)・・・(Qnxn)：冠頭部α：本体 Qi:束縛子
P → Qを￢P∨Qに、 Ａ≡Ｂを（ ￢Ａ∨Ｂ）∧（ ￢Ｂ∨Ａ）に変換 否定記号の括り出し： ￢（￢Ａ）=Ａ ￢（Ａ∧Ｂ）= （ ￢Ａ∨￢Ｂ） ￢（Ａ∨Ｂ）= （ ￢Ａ∧￢Ｂ） ￢ ((∀x)α）= (∃x)(￢α) ￢ ((∃x)α）= (∀x)(￢α)

8 節形式への変換 -2 Skolem標準形への変換 連言標準形へ変換
存在記号∃の除去： (∀x) (∃y)P(x,y) = (∀x) P(x, f(x)) 　　　 f(x):　Skolem関数 存在記号を含む変数を引数とする新しい関数で置き換えたもの

9 節形式への変換 -3 分配法則を用いて、母式を 選言の連言結合形に変換： （Ａ∧Ｂ）∨（Ｂ∧C）=（Ａ∨Ｂ）∧ （Ｂ∨C）∧Ｂ∧（Ａ∨C）
第９回　 一階述語論理 節形式への変換　-3 分配法則を用いて、母式を 選言の連言結合形に変換： （Ａ∧Ｂ）∨（Ｂ∧C）=（Ａ∨Ｂ）∧ （Ｂ∨C）∧Ｂ∧（Ａ∨C） P∨（Q∧R）=（P∨Q）∧（P∨R） P∧（Q ∨ R）=（P∧Q）∨（P∧R） ２．節集合への変換： 　P ∨ Q ∨ ￢ R　 ⇒ 　{P, Q, ￢ R} 　（Ａ∨Ｂ）∧ （Ｂ∨C）∧Ｂ∧（Ａ∨C） ⇒ {{A,B}, {B,C}, {B}, {A,C}}

10 融合法による推論-1 節の統合 ～ 節集合に変換する前 基本：(P, P→Ｑ）⇒Ｑ (P→Ｑ, Ｑ→R）⇒ P→R
節の統合 ～　節集合に変換する前 基本：(P, P→Ｑ）⇒Ｑ　 (P→Ｑ,　Ｑ→R）⇒ P→R 例： C1 = L∨M1∨M２ ・・ ∨Mｋ 　　C２ = ￢L∨N1∨ N2 ・・ ∨Nl の統合 (￢M1∧ ～M２∧ ・・ ∧ ～Mｋ） → L　及び L → (N1∨ N2 ・・ ∨Nl ） ⇒　 (￢M1∧ ￢M２∧ ・・ ∧ ￢Mｋ） → (N1∨ N2 ・・ ∨Nl ） ⇒　 M1∨M２ ・・ ∨Mｋ∨ N1∨ N2 ・・ ∨Nl = C３

11 融合法による推論-2 単一化(unification) 複数のリテラルの変数に適当な項を置換・代入することにより、全てのリテラルを同一化すること 置換(substitution) s=P/Q: 変数QをPで置換える こと　←　全称記号∀のみなのでOK 例）P(y, f(x))とP(a,z)の単一化 　ｓ１=a/y: P(y, f(x)) ⇒ P(a, f(x)), P(a,z)不変 ｓ2=f(x)/z: P(a, z) ⇒ P(a, f(x))　で一致

12 融合法による推論-3 融合節の生成・空節の導出 ←　導出原理(resolution principle) 目標の否定を前提に加えた節の集合から導出・単一化を繰り返すことにより、矛盾（空節）を導く

13 融合法による推論例 前提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)))を前提Ｓに加えて 　ＮＩＬを導出: 一通りとは限らない

14 融合法による推論の例(結果） ￢ P∧￢P＝空 ￢ ￢

15 不確実な事実・知識による推論 例外（非単調性）に起因する不確実性： - サーカムスクリプション - デフォルト推論
曖昧さに起因する不確実性： - 信頼性係数（ＣＦ：Certainty Factor) - ファジィ理論 - Dempster-Shafer(DS)理論

16 非単調論理による推論 論理体系の単調性： 　Ａ⊂Ｂ　ならば　Ｔｈ（Ａ） ⊂Ｔｈ（Ｂ） Ｘ：　矛盾の無い命題（公理）の集合 Ｔｈ（Ｘ）：　Ｘから証明される定理の集合 ＊拡張：　公理系に推論規則を適用することにより 論理式の集合（定理群）を得ること 非単調論理(non-monotonic logic)： 単調性が成立しない論理体系　 ←例外を含む知識（常識・・）が存在、・・ 　

17 例外への対処 知識の適用対象を限定することによる 古典（述語）論理への帰着： - サーカムスクリプション
様相記号の導入による古典論理の拡張： - デフォルト推論

18 閉世界仮説とサーカムスクリプション 閉世界仮説(closed world assumption)： ￢P(x)が証明できなければP(x)は真とする ～　実世界では不成立、人間の通常の推論過程 サーカムスクリプション(極小限定) ： 述語P(x)に関する命題A(P)が成立している場合A(φ）∧(∀x)[{φ(x)∧ ￢E(φ）} → P(x)] → (∀x) [P(x) →φ(x)] E:例外

19 閉世界仮説とサーカムスクリプションの例 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)]

20 デフォルト推論 Ｐが成立ち、￢Ｑが証明されていなければ、 Ｒが成立つ； Ｐ：ＭＱ Ｒ Ｐ：前提 Ｑ：仮定 Ｒ：帰結 Ｍ：様相記号
　Ｒが成立つ；　　Ｐ：ＭＱ 　　　　　　　　　　　Ｒ 　Ｐ：前提　Ｑ：仮定　Ｒ：帰結　Ｍ：様相記号 正規デフォルト規則：　Ｐ：ＭＱ 　　　　　　　　　　　 Ｑ 拡張：　公理系に推論規則を適用することにより 論理式の集合（定理群）を得ること 　- 多重拡張 ～　拡張結果が複数通り出現 - 演繹結果が規則の適用順序に依存

21 デフォルト推論の例 哺乳類(x) → ゆったり(x) 鯨(x) → 脊椎動物(x) 鯨(x) → ￢翼がある(x) 鯨(x) → 水棲(x)

22 信頼性係数による推論 血液感染症診断支援・MYCINで最初に導入 後向き推論の効率化に有効 理論的裏付けに乏しい
更新規則：前件（左辺）C1＊C２ ・・、 後件(右辺)Ａ CF(右辺)= CF(左辺) CF(規則) CF(C1∧C２ ・・ ∧Cｋ)=min(CF(Ci ) ) CF(C1∨C２ ・・ ∨Cｋ)=max(CF(Ci ) )　～当初 　その後は、　　=CF(C1)+CF(C２)(1-CF(C1))・・

23 ＭＹＣＩＮにおける知識の例 事実型： ・培養基の場所は血液である(1.0) ・培養基の菌は好気性である(0.25) ・培養基の菌は大腸菌である(0.75) (): 確信度 プロダクションルール型： もし 　感染症の種類が一次敗血症であり、 　培養基の場所が無菌の場所であり、 　培養された菌の入口が胃腸管と推定される ならば、 　その菌はバクテロイドである兆候がある(0.7)

24 ＭＹＣＩＮにおける推論の例 ( )=0.72 後向き推論： 結論を仮定して、 ルールの前件部を チェックすることにより、 結論の確からしさを チェック ( )=0.9

25 ベイズネットワークにおける確率推論 ベイズの定理に基づく不確実な情報に 基づく推論
第１2回　　　不確実性の取り扱い ベイズネットワークにおける確率推論 ベイズの定理に基づく不確実な情報に 基づく推論 確率変数間の依存関係に関する知識を グラフとして保持・更新 ・ノード：　確率変数 ・アーク：　ノード間の因果関係の存在

26 確率集合関数 コルモゴロフの公理系 P(E)≧０ P(Ω) =１ Ω：基礎空間（事象の全体集合） Fi が互いに独立（素）の時
第１2回　　　不確実性の取り扱い 確率集合関数 コルモゴロフの公理系 P(E)≧０ P(Ω) =１ 　　 Ω：基礎空間（事象の全体集合） Fi が互いに独立（素）の時 　　P(F1∪Ｆ２ ∪・・ ∪Ｆｋ) = P(F1) ＋ P(Ｆ２ ) ＋・・ ＋P(Ｆｋ)

27 基本的な性質 P(φ）= 0 φ:空集合 E⊇Fの時 P(E)≧P（F) P(Ec)=1 - P(E) Ec :Eの補集合≡Ω- E
第１2回　　　不確実性の取り扱い 基本的な性質 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): 確率の加法公式

28 条件付確率と乗法定理 事象E,Fに関して， 条件付確率： P(E/F) = P(E∩F)/P(F)
第１2回　　　不確実性の取り扱い 条件付確率と乗法定理 事象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)

29 第１2回　　　不確実性の取り扱い mutty@ics.kagoshima-u.ac.jp
ベイズの定理 Fi が互いに独立（素），かつ F1∪Ｆ２ ∪・・ ∪Ｆｋ= Ω P(E) =　P(E/F1)P(F1)+ P(E/F２)P(F２) +・・・ 　　　　 + P(E/Fｋ)P(Fｋ) ベイズの定理： P(Fi/E) = P(E/Fi)・P(Fi) / P(E) = P(E/Fi)・P(Fi) / ｛P(E/F1)P(F1)+ 　　P(E/F２)P(F２) +・・・+ P(E/Fｋ)P(Fｋ) ｝

30 ベイジアンネットの性質 ネットワークにおける全ての変数に対し，その親に条件付けされた各ノードの結合確率を規定するだけでOK
第１2回　　　不確実性の取り扱い ベイジアンネットの性質 ネットワークにおける全ての変数に対し，その親に条件付けされた各ノードの結合確率を規定するだけでOK 以上で規定された条件付き確率は大域的に無矛盾であることが保証 各ノードにおける条件付き確率の集合は ネットワークにおける全てのノードの唯一の結合確率分布を規定 確率変数：｛真，偽｝

31 第１2回　　　不確実性の取り扱い mutty@ics.kagoshima-u.ac.jp
ベイズネットワークの例 「ボーナス」－「収入」： ボーナスが真のとき， 　収入が真の確率0.8 　 偽の確率0.2 ボーナスが偽のとき， 　収入が真の確率0.3 　 偽の確率0.7

32 ベイズネットワークのアルゴリズム 観測された変数の値をノードにセット 親ノードも観測値も持たないノードには 事前確率分布を付与
第１2回　　　不確実性の取り扱い ベイズネットワークのアルゴリズム 観測された変数の値をノードにセット 親ノードも観測値も持たないノードには 事前確率分布を付与 確率を伝播し，知りたい対象の変数Xの事後確率を計算

33 P(旅行）＝P(旅行/収入）・P(収入）＋ P(旅行/￢収入）・P(￢収入） ＝0.2・0.6 + 0.5・(1.0-0.6) = 0.32
第１2回　　　不確実性の取り扱い ベイズネットワークの例：確率計算 P(収入）＝P(収入/ボーナス）・P(ボーナス）＋ P(収入/￢ボーナス）・P(￢ボーナス） ＝0.8・ ・( ) = 0.6 P(旅行）＝P(旅行/収入）・P(収入）＋ P(旅行/￢収入）・P(￢収入） ＝0.2・ ・( ) = 0.32

34 ファジイ理論による推論 米・L.A.Zadehが提案 (1965) 確からしさを0～１の実数値で表現：主観
membership(所属度)関数による連続表現 μ(f(x)∧g(y))=min{μ(f(x)), μ(g(y)) } μ(f(x)∨g(y))=max{μ(f(x)), μ(g(y)) }

35 推論の例(エアコンの制御） 温度３０度のときの目盛？ 快適　→　切る やや暑い　→　弱にする 暑い　→　強にする　　

36 推論結果(エアコンの制御） 温度３０度 大きい方を選択 (1x0.4+2x0.4+ 3x0.2+4x0.6+
) =3.3