【文章內(nèi)容簡介】 ， 或 )|(),|( ?? iji VPVVP ? )|(),|( ?? jij VPVVP ?)|,( ?ji VVI )|,( ?ij VVI 《 人工智能原理 》 第五章 不確定性推理 貝葉斯網(wǎng)絡(luò) （ D分離 (圖示 )） V iVb3VjVb1 Vb2證據(jù)集 ε給定證據(jù)結(jié)點集 ε ，Vi獨立Vj：Vi到Vj的所有三條路徑都被阻塞a)Vb1是證據(jù)結(jié)點，兩條弧都以Vb1為尾b)Vb2是證據(jù)結(jié)點，一條以Vb2為頭，一條以Vb2為尾c)Vb3及其任何后繼都不在證據(jù)結(jié)點集中，兩條弧都以Vb3為頭 《 人工智能原理 》 第五章 不確定性推理 貝葉斯網(wǎng)絡(luò) （ 定義 ） ? 條件獨立： – 如具有以上三個屬性之一 ， 就說結(jié)點 Vi和 Vj條件獨立于給定的結(jié)點集 ε 。 ? 阻塞： – 給定證據(jù)集合 ε ， 當(dāng)上述條件中的任何一個滿足時 ，就說 Vb阻塞相應(yīng)的那條路徑 。 ? D分離： – 如果 Vi和 Vj之間所有的路徑被阻塞 ， 就叫證據(jù)集合ε 可以 D分離 Vi和 Vj 《 人工智能原理 》 第五章 不確定性推理 貝葉斯網(wǎng)絡(luò) （ D分離 (例 1)） Z X Y Z X、 Y獨立 X、 Y條件獨立 Yes Yes X Y Z X、 Y獨立 X、 Y條件獨立 Yes No X Y Z X、 Y獨立 X、 Y條件獨立 Yes No X Y Z X、 Y獨立 X、 Y條件獨立 No Yes X Y X、 Y獨立 X、 Y條件獨立 No No 《 人工智能原理 》 第五章 不確定性推理 貝葉斯網(wǎng)絡(luò) （ D分離 (例 2)） Z X Y X—草濕 Y—彩虹 Z—下雨 P(X,Y)≠P(X)P(Y) P(X|Y,Z) = P(X,Z) Z X Y X—下雨 Y—灑水 Z—草濕 P(X,Y） = P(X)P(Y) P(X|Y,Z) )≠ P(X,Z) 《 人工智能原理 》 第五章 不確定性推理 貝葉斯網(wǎng)絡(luò) （ D分離 (例 3)） X Z W X—草濕 Y—灑水者 Z—彩虹 W—長蟲 P(X,Y) = P(X)P(Y) P(X|Y,Z) = P(X|Z) Y X Z W X—草濕 Y—灑水者 Z—彩虹 W—長蟲 P(X,Y) ≠ P(X)P(Y) P(X|Y,Z) ≠ P(X|Z) Y 《 人工智能原理 》 第五章 不確定性推理 貝葉斯網(wǎng)絡(luò) （ D分離 (例 4） Radio and Ignition, given Battery? Yes Radio and Start, given Ignition? Yes Gas and Radio, given Battery? Yes Gas and Radio, given Start? No Gas and Battery, given Moves? No Battery Radio Ignition Gas Moves Start 《 人工智能原理 》 第五章 不確定性推理 貝葉斯網(wǎng)絡(luò) （ 推理 ） ? 建立貝葉斯網(wǎng)絡(luò)的目的 – 有了網(wǎng)絡(luò)?？梢蕴岢鰡栴}： ? P(問題 |證據(jù) )， 如： P(吸煙 |肺癌） – 進(jìn)行概率推理 – 與謂詞邏輯有相似之處 。如：患?。ㄎ鼰?，肺癌） ? 在某些場合下有有效的推理方法。有一些工具包。 ? 一般情況下是很困難的，原因 – 不是所有的 CPT表都能夠得到 – 網(wǎng)絡(luò)結(jié)構(gòu)大且復(fù)雜 – NPhard推理 ? 我們要做的是，將問題正確的表示為合理的網(wǎng)絡(luò)形式，選用適合的算法。 《 人工智能原理 》 第五章 不確定性推理 貝葉斯網(wǎng)絡(luò) （ 推理續(xù) ） ? 貝葉斯網(wǎng)絡(luò)通常使用因果或診斷規(guī)則與推理 – 因果規(guī)則： X Cause Y with some probability – 診斷規(guī)則 ： Y is evidence of X with some probability – 因果推理： Given cause C, determine P(Query|C) – 診斷推理： Given evidence E, determine P(Query|E) 《 人工智能原理 》 第五章 不確定性推理 貝葉斯網(wǎng)絡(luò) （ 推理續(xù) ） ? 推理需求： P(X|Y) – 診斷推理是從效果到起因 證據(jù)是一些征兆： X是起因， Y是征兆 – 因果推理是從起因到效果 證據(jù)是一些起因： X是征兆， Y是起因 – 解釋歷史 X和 Y是起因， Z是兩個起因的征兆。這時可以用一個起因 Y解釋另一個起因 X。 《 人工智能原理 》 第五章 不確定性推理 貝葉斯網(wǎng)絡(luò) （ 推理例 ） ? 下雨、草濕、灑水 P(X) P(Y) 下雨 草濕 Query:P(X|Y) P(X) P(Y) 草濕 下雨 Query:P(X|Y) P(X) P(Z|X,Y) 下雨 草濕 Query:P(X|Y,Z) and P(X|Z) P(Y) 灑水 《 人工智能原理 》 第五章 不確定性推理 貝葉斯網(wǎng)絡(luò) （ 推理例續(xù) ） ? 條件： – 下雨 – 草濕 – 出現(xiàn)蟲子 ? 求： – P(Raining|Worm Sighting) P(Y|X) 下雨 草濕 Query:P(X|Z) P(X) 出現(xiàn)蟲子 P(Z|Y) 《 人工智能原理 》 第五章 不確定性推理 貝葉斯網(wǎng)絡(luò) （ 因果推理例 ） 給定患者是一個吸煙者（ S），計算他患肺氣腫（ E）的概率 P(E|S)。S稱作推理的證據(jù)， E叫詢問結(jié)點。 ? 首先， E的另一個父結(jié)點（ C）， P(E|S)=P(E,C|S)+P(E,~C|S)。 ? 右邊的第一項 ， P(E,C|S)＝ P(E,C,S)/P(S)＝ P(E|C,S)*P(C,S)/P(S)＝ P(E|C,S)*P(C|S） ? 同理可得公式的右邊的第二項為： P(E,~C|S) = P(E|~C,S)*P(~C)。 ? 由此可得： ? P(E|S) = P(E| C,S)*P(C)+P(E|~C,S)*P(~C) ? 如果采用概述中的例題數(shù)據(jù)，有 P(~C) = 1 P(C)，則有， ? P(E|S)＝ *+*()= 主要操作： ? 按照給定證據(jù)的 V和它的所有雙親的聯(lián)合概率，重新表達(dá)給定證據(jù)的詢問結(jié)點的所求條件概率。 ? 直到所有的概率值可從 CPT表中得到，推理完成。 《 人工智能原理 》 第五章 不確定性推理 貝葉斯網(wǎng)絡(luò) （ 推理自學(xué) ） 《 Artificial Intelligence: A New Synthesis》 Nils. J. Nilsson, 機械工業(yè)出版社， 1999 Probabilistic Inference in Polytrees () 《 人工智能原理 》 第五章 不確定性推理 第五章 不確定性推理 ? 概述 ? 概率論基礎(chǔ) ? Bayes網(wǎng)絡(luò) ? 主觀 Bayes方法 ? 確定性方法 ? 證據(jù)理論 《 人工智能原理 》 第五章 不確定性推理 第五章 不確定性推理 ? 概述 ? 概率論基礎(chǔ) ? Bayes網(wǎng)絡(luò) ? 主觀 Bayes方法 ? 確定性方法 ? 證據(jù)理論 《 人工智能原理 》 第五章 不確定性推理 主觀 貝葉斯 方法 (概述 ） ? 在 Prospector的探礦系統(tǒng)的研究過程中提出的。 原有貝葉斯公式只考慮 A出現(xiàn)對 B的影響，沒有考慮 A不出現(xiàn)的影響。 ? 貝葉斯規(guī)則： 當(dāng) B為 n個 互不相容事件的集合時，貝葉斯公式可寫為： P ( A )B ) P ( B )|P ( AA)|P ( B ???? n1jjjiii)) P ( BB|P ( A)) P ( BB|P ( AA)|P ( B n 1i ?? 《 人工智能原理 》 第五章 不確定性推理 主觀 貝葉斯 方法 (概述 ） ? 思路 – 先定好應(yīng)該怎么辦，再湊公式。主要是避開P(A| B)的計算。 《 人工智能原理 》 第五章 不確定性推理 主觀 貝葉斯 方法 (概述 ） ? 規(guī)則的不確定性 – 定義： B)|~P ( A B)|P ( ALS ?表示 A為真時，對 B的影響。（規(guī)則成立的充分性） B)|~AP ( ~B)|AP ( ~LN ?表示 A為假時，對 B的影響。（規(guī)則成立的必要性） （確定性理論中沒有考慮這點） 《 人工智能原理 》 第五章 不確定性推理 主觀 貝葉斯 方法 （ 規(guī)則的不確定性 ） P ( X )1P ( X )O ( X ) ?幾率函數(shù) O(X) )|(1)|()|(~)|()|(ABPABPABPABPABO???)(1)()(XOXOXP??O(X)稱為先驗幾率 。 表示證據(jù) X的出現(xiàn)概率和不出現(xiàn)的概率之比 ， 顯然 O(X)是 P(X)的增函數(shù) ， 且有： 當(dāng) P(X)＝ 0， 有 O(X)＝ 0 當(dāng) P(X)＝ ， 有 O(X)＝ 1 當(dāng) P(X)＝ 1， 有 O(X)＝ ∞ 由此可見 ， 幾率函數(shù)實際上表示了證據(jù) X的不確定性 。 相應(yīng)有， 稱為后驗幾率 ． )|( ABO 《 人工智能原理 》 第五章 不確定性推理 主觀 貝葉斯 方法 （ 規(guī)則的不確定性 ） – O(X)的性質(zhì) ? P(X) = 0時 , O(X) = 0 假 ? P(X) = , O(X) = 1 ? P(X) = 1時 , O(X) = ∞ 真 – O(X)與 LN， LS的關(guān)系 ? O(B|A) = LS ? O(B) ? O(B|~A) = LN ? O(B) 《 人工智能原理 》 第五章 不確定性推理 主觀 貝葉斯 方法 （ 規(guī)則的不確定性 ） ???????????BA O ( B )A)|B O( 1BA O ( B )A)|O ( B 1BA O ( B )A)|O ( B 1LS不支持支持沒影響對???????????BA~ O ( B )A)|~B O( 1BA~ O ( B )A)|~O ( B 1BA~ O ( B )A)|~O ( B 1LN不支持支持沒影響對， 且必須滿足 ： 《 人工智能原理 》 第五章 不確定性推理 主觀 貝葉斯 方法 （ 規(guī)則的不確定性 ） – LS、 LN≥０ ， 不獨立 。 – LS, LN不能同時 ＞１或 ＜１ – LS, LN可同時＝ 1 《 人工智能原理 》 第五章 不確定性推理 主觀 貝葉斯 方法 （ 證據(jù) A的不確定性 ） ??????????一般情況），（真當(dāng)，假當(dāng)0,0)(1)()( AAAPAPAO? P(A)或 O(A)表示證據(jù) A的不確定性 《 人工智能原理 》 第五章 不確定性推理 主觀 貝葉斯 方法 （ 推理計算 1） ? A必出現(xiàn)時： – O(B|A) = LS?O(B) – O(B|~A) = LN?O(B) 若需要概率時： )(1)()(AOAOAP?? 《 人工智能原理 》 第五章 不確定性推理 主觀 貝葉斯 方法 （ 推理計算 2） A不確定時：即 P(A) ? 1 （ 1976年的算法） – 向前看一步 A’， A’ 為與 A有關(guān)的所有觀察 P(B|A’) = P(B|A)P(A| A’)+P(B|～ A)P(～ A| A’) ? P(A| A’) = 1時，證據(jù) A必然出現(xiàn)（ P95） ? P(A| A’) = 0時， LN代替上式 的 LS， 公式（ 2） ? P