計算智能課件24bayesian network2

1、 貝葉斯網(wǎng)絡(luò)中的精確推理 通過枚舉進行推理 變量消元算法 精確推理的復雜度 團算法 貝葉斯網(wǎng)絡(luò)中的近似推理直接采樣算法Markov鏈仿真推理 簡單詢問：計算后驗邊緣概率P(Xi|E=e) 聯(lián)合詢問：P(Xi,Xj|e)=P(Xi|E=e)P(Xj|Xi,E=e) 最優(yōu)決策：P(outcome|action,evidence) 敏感性分析：哪個因素起關(guān)鍵作用 最佳解釋：比如為什么需要一個新的引擎？(| ,)( )( )( |, ) ( | ) (| )eaP B j mP BP eP a B e P j a P m a(| ,) 0.001,0.9990.0020.95,0.290.9 0.70

2、.001,0.9990.0020.05,0.710.05 0.010.001,0.9990.9980.94,0.0010.9 0.70.001,0.9990.9980.06,0.9990.05 0.01P B j m 0.001,0.999( 0.0012,0.0040.5910,0.0011 )0.001,0.9990.5922,0.00150.0005922,0.00149850.283,0.717 (| ,)( )( )( |, ) ( | ) (| )eaP B j mP BP eP a B e P j a P m afB(B)fE(E)fA(A,B,E)fJ(A)fM(A)( | )

3、0.9( )( |)0.05JP j afAP ja( , ,) ( |,), (|,)0.950.050.940.060.290.710.0010.999AfA B EP a B E Pa B E(| )0.7( )(|)0.01MP m afAP ma( ,)( , ,)( )( )( , ,)( )( )(, ,)()()AJMAJMaAJMAJMfB Efa B Efafafa B Efafafa B Efafa0.950.050.940.060.70.90.01 0.050.290.710.0010.9990.59850.59220.18310.0011( )( )( , )()(

4、,)EEEAJMAJMAJMfBfefB efefBe0.0020.5985,0.18310.9980.5922,0.0011(| ,)( )( )BEAJMP B j mfBfB 從因子乘積中對一個變量進行求和消元是從因子乘積中對一個變量進行求和消元是直接計算。注意的技巧是，任何不依賴于直接計算。注意的技巧是，任何不依賴于將被求和消元的變量都可以移到求和符號將被求和消元的變量都可以移到求和符號的外面。的外面。 注意直到我們需要將變量從累積乘積中消注意直到我們需要將變量從累積乘積中消去前不會進行矩陣乘法。去前不會進行矩陣乘法。 可以刪除任何既非查詢變量，也非證據(jù)變可以刪除任何既非查詢變量，也非

5、證據(jù)變量的葉節(jié)點。量的葉節(jié)點。),()()(),()()()()()(),()(,BAfAfAfeBAfefAfAfAfAfeBAfefAEMJeAEeMJMJAEMultiply connected networks:在最壞情況下，具有指數(shù)級的時間空間復雜度在最壞情況下，具有指數(shù)級的時間空間復雜度. .團算法團算法（cluster algorithm）cloudySprinklerRainWetGrassP(C)=.5C P(R)T .8F .2C P(S)T .1F .5cloudySpr+RainWetGrassP(C)=.5C P(S+R)=x tt tf ft ffT .08 .02

6、 .72 .18F .10 .40 .10 .40 對于回答單個查詢，變量消元算法是簡單對于回答單個查詢，變量消元算法是簡單有效的。然而，若希望計算網(wǎng)絡(luò)中所有節(jié)有效的。然而，若希望計算網(wǎng)絡(luò)中所有節(jié)點的后驗概率它就不那么有效率了。點的后驗概率它就不那么有效率了。 例如，在一個是多樹網(wǎng)絡(luò)中可能需要處理例如，在一個是多樹網(wǎng)絡(luò)中可能需要處理O(n)O(n)個查詢，查詢共需要個查詢，查詢共需要O(n)O(n)的開銷，因的開銷，因此總的時間復雜度是此總的時間復雜度是O(nO(n2 2).). 通過團算法（聯(lián)合樹算法），時間可以減通過團算法（聯(lián)合樹算法），時間可以減少到少到O(n).O(n). 精確推理的局

7、限性：精確推理的局限性：對大規(guī)模多連通網(wǎng)絡(luò)中的精確推理是不可操對大規(guī)模多連通網(wǎng)絡(luò)中的精確推理是不可操作的。作的。近似推理基本思想：近似推理基本思想：1.1.從分布從分布S S中進行中進行N N個樣本的采樣個樣本的采樣2.2.計算一個逼近的后驗概率計算一個逼近的后驗概率3.3.證明它收斂到真實概率證明它收斂到真實概率P PP 直接采樣算法直接采樣算法 拒絕采樣算法拒絕采樣算法 似然加權(quán)算法似然加權(quán)算法 MCMCMCMC算法算法 任何采樣算法中最基本的要素是根據(jù)已知任何采樣算法中最基本的要素是根據(jù)已知概率分布生成樣本。概率分布生成樣本。 對貝葉斯網(wǎng)絡(luò)，最簡單種類的隨機采樣過對貝葉斯網(wǎng)絡(luò)，最簡單種類

8、的隨機采樣過程是對沒有與之關(guān)聯(lián)的證據(jù)網(wǎng)絡(luò)事件進行程是對沒有與之關(guān)聯(lián)的證據(jù)網(wǎng)絡(luò)事件進行采樣。其思想是，按照拓撲次序依次對每采樣。其思想是，按照拓撲次序依次對每個變量進行采樣。被采樣的概率分布依賴個變量進行采樣。被采樣的概率分布依賴于父節(jié)點已得到的賦值。于父節(jié)點已得到的賦值。 容易證明直接采樣生成的樣本服從網(wǎng)絡(luò)所容易證明直接采樣生成的樣本服從網(wǎng)絡(luò)所指定的先驗聯(lián)合概率分布。指定的先驗聯(lián)合概率分布。 令令S Spsps(x(x1 1, ,x,xn n) )為由為由Prior-SamplePrior-Sample生成的特生成的特定事件的概率。由采樣過程得到，定事件的概率。由采樣過程得到， 所得到的是該事

9、件的真實概率。所得到的是該事件的真實概率。 例：例： 在任何采樣方法中，都是通過對實際生成在任何采樣方法中，都是通過對實際生成的樣本數(shù)來計算答案。假設(shè)共有的樣本數(shù)來計算答案。假設(shè)共有N N個樣本，個樣本，令令N(xN(x1 1, ,x,xn n) )為特定事件為特定事件x x1 1, ,x xm m發(fā)生頻率，發(fā)生頻率，我們期望該頻率在極限情況下收斂到根據(jù)我們期望該頻率在極限情況下收斂到根據(jù)采樣概率得到的它的期望值采樣概率得到的它的期望值： 估計概率在大量樣本極限下成為精確值，估計概率在大量樣本極限下成為精確值，這樣的估計被稱為這樣的估計被稱為一致估計一致估計。 例如：可以為不完全指定事件例如：

10、可以為不完全指定事件x x1 1, ,x xm m的概的概率產(chǎn)生一個一致估計，其中率產(chǎn)生一個一致估計，其中m mn,n,即即 假設(shè)我們從草坪噴灌網(wǎng)絡(luò)中生成假設(shè)我們從草坪噴灌網(wǎng)絡(luò)中生成10001000個樣本，個樣本，其中其中511511個樣本滿足個樣本滿足Rain=true,Rain=true,則則11(,)(,)/mpsmP xxNxxN()0.511P rain 該算法是一類由一個易于采樣的分布出發(fā)，為一該算法是一類由一個易于采樣的分布出發(fā)，為一個難以直接采樣的分布產(chǎn)生采樣樣本的通用算法。個難以直接采樣的分布產(chǎn)生采樣樣本的通用算法。在其最簡單的形式中，它可以用于計算條件概率。在其最簡單的形式

11、中，它可以用于計算條件概率。計算步驟：計算步驟：1.1.根據(jù)網(wǎng)絡(luò)指定的先驗概率分布生成采樣樣本。根據(jù)網(wǎng)絡(luò)指定的先驗概率分布生成采樣樣本。2.2.拒絕所有與證據(jù)不匹配的樣本。拒絕所有與證據(jù)不匹配的樣本。3.3.在剩余樣本中對事件在剩余樣本中對事件X=xX=x的出現(xiàn)頻繁程度計數(shù)從的出現(xiàn)頻繁程度計數(shù)從而得到估計概率。而得到估計概率。 拒絕采樣能夠產(chǎn)生真實概率的一致估計拒絕采樣能夠產(chǎn)生真實概率的一致估計。 直接采樣算法的局限性：直接采樣算法的局限性：拒絕了太多的樣本拒絕了太多的樣本！隨著證據(jù)變量個數(shù)的增！隨著證據(jù)變量個數(shù)的增多，與證據(jù)多，與證據(jù)e e相一致的樣本在所有樣本中所相一致的樣本在所有樣本中所

12、占的比例呈指數(shù)級下降，所以對于復雜問占的比例呈指數(shù)級下降，所以對于復雜問題這種方法是完全不可用的。題這種方法是完全不可用的。 只生成與證據(jù)只生成與證據(jù)e e一致的事件，避免拒絕采樣算法的一致的事件，避免拒絕采樣算法的低效率。低效率。 算法描述：算法描述： 該算法固定證據(jù)變量該算法固定證據(jù)變量E E的值，只對證據(jù)以外的其的值，只對證據(jù)以外的其余變量余變量X X和和Y Y進行采樣進行采樣。這保證了采樣樣本與證據(jù)這保證了采樣樣本與證據(jù)一致。在對查詢變量的分布進行計數(shù)之前，把根一致。在對查詢變量的分布進行計數(shù)之前，把根據(jù)證據(jù)得到的事件的似然作為每個事件的權(quán)值，據(jù)證據(jù)得到的事件的似然作為每個事件的權(quán)值，

13、該權(quán)值通過每個證據(jù)變量在給定其父節(jié)點取值下該權(quán)值通過每個證據(jù)變量在給定其父節(jié)點取值下的條件概率的乘積進行度量。的條件概率的乘積進行度量。 求解查詢求解查詢P(Rain|sprinkler,wetgrass).w=1.0.P(Rain|sprinkler,wetgrass).w=1.0. 1 對對P(cloudy)=(0.5,0.5)P(cloudy)=(0.5,0.5)進行采樣：假設(shè)進行采樣：假設(shè)返回返回truetrue 2 SprinklerSprinkler是證據(jù)變量，其取值為是證據(jù)變量，其取值為true,true,計計算算(|)0.1ww P sprinkler cloudy 3 對對P

14、(Rain|cloudy)=(0.8,0.2)P(Rain|cloudy)=(0.8,0.2)進行采樣進行采樣假設(shè)返回假設(shè)返回true, w=0.1true, w=0.1 4.WetGrass4.WetGrass是證據(jù)變量，其取值為是證據(jù)變量，其取值為true,true,計計算算(|)0.099wwP wetgrass sprinkler令令SwsSws為為Weight-sampleWeight-sample的采樣分布，證據(jù)變量的固定的采樣分布，證據(jù)變量的固定值為值為e,e,證據(jù)以外的其它變量為證據(jù)以外的其它變量為Z Z。給定父節(jié)點后，對。給定父節(jié)點后，對Z Z中的每個變量進行采樣中的每個變量

15、進行采樣: :Parents(Zi)Parents(Zi)可能包含隱變量和證據(jù)變量。與可能包含隱變量和證據(jù)變量。與P(z)P(z)不不同的是，同的是，SwsSws給予證據(jù)某種特別的關(guān)注：每個給予證據(jù)某種特別的關(guān)注：每個ZiZi的采的采樣值會受到它的祖先節(jié)點中證據(jù)的影響，另外，樣值會受到它的祖先節(jié)點中證據(jù)的影響，另外， SwsSws對證據(jù)的考慮要少于對真實的后驗概對證據(jù)的考慮要少于對真實的后驗概P(z|e)P(z|e)的考慮。的考慮。 似然權(quán)值似然權(quán)值w w補償了真實采樣分布與期望采樣補償了真實采樣分布與期望采樣分布之間的差距分布之間的差距 對已知事件對已知事件z,ez,e的權(quán)值的權(quán)值 加權(quán)采樣

16、概率為：加權(quán)采樣概率為：( | )( , , ) ( , , )wsyP x eNx y e w x y e( , , ) ( , , )wsySx y e w x y e( , , )( , )( | )yP x y eP x eP x e 似然加權(quán)回到一致估計似然加權(quán)回到一致估計 使用了所有的樣本，效率比拒絕采樣高。使用了所有的樣本，效率比拒絕采樣高。 局限性：局限性： 證據(jù)變量的個數(shù)增加時，它仍然要承受大證據(jù)變量的個數(shù)增加時，它仍然要承受大幅度的性能下降。因為大多數(shù)的樣本權(quán)值幅度的性能下降。因為大多數(shù)的樣本權(quán)值都非常低，導致在加權(quán)估計中起主導作用都非常低，導致在加權(quán)估計中起主導作用的只是

17、那些所占比例很小的、與證據(jù)相符的只是那些所占比例很小的、與證據(jù)相符合的似然程度不是非常小的樣本。合的似然程度不是非常小的樣本。 MCMC: Markov chain Monte Carlo 算法描述：算法描述： 1 1該算法總是通過對前一事件進行隨機改變而生成該算法總是通過對前一事件進行隨機改變而生成每個事件樣本。每個事件樣本。 2 2可以認為網(wǎng)絡(luò)處于為每個變量指定了值的一個特可以認為網(wǎng)絡(luò)處于為每個變量指定了值的一個特定的當前狀態(tài)，而下一個狀態(tài)則通過非證據(jù)變量定的當前狀態(tài)，而下一個狀態(tài)則通過非證據(jù)變量X Xi i進行采樣來產(chǎn)生，其取決于進行采樣來產(chǎn)生，其取決于X Xi i的的MarkovMar

18、kov覆蓋中覆蓋中的變量的當前值的變量的當前值 3. 3. 在狀態(tài)空間中的隨機走動，但保持證據(jù)變量在狀態(tài)空間中的隨機走動，但保持證據(jù)變量的值固定不變。的值固定不變。查詢查詢P(Rain|Sprinkler=T,WetGrass=T).P(Rain|Sprinkler=T,WetGrass=T).證據(jù)證據(jù)變量固定為他們的觀察值，而隱變量變量固定為他們的觀察值，而隱變量cloudycloudy和和rain rain 則隨機的初始化：則隨機的初始化：T,T,F,T.T,T,F,T.反復執(zhí)行下面的步驟：反復執(zhí)行下面的步驟：1 1對對cloudycloudy采樣，給定它的采樣，給定它的Markov bl

19、anketMarkov blanket當當前值，即根據(jù)前值，即根據(jù)P(cloudy|Sprinkler=T,Rain=F)P(cloudy|Sprinkler=T,Rain=F)采樣。采樣。2 2對節(jié)點對節(jié)點RainRain采樣，給定它的采樣，給定它的Markov blanketMarkov blanket當前值，即根據(jù)當前值，即根據(jù)P(Rain|Cloudy=P(Rain|Cloudy=F,Sprinkler=T,WetGrass=T)F,Sprinkler=T,WetGrass=T)進行采樣。假設(shè)進行采樣。假設(shè)采樣結(jié)果為采樣結(jié)果為Rain=T.Rain=T.新的當前狀態(tài)是新的當前狀態(tài)是F,

20、T,T,T.F,T,T,T. 基本觀點：基本觀點：采樣過程最終會進入一種動態(tài)平衡。采樣過程最終會進入一種動態(tài)平衡。 該特性來自于特定的轉(zhuǎn)移概率，即過程從一種狀該特性來自于特定的轉(zhuǎn)移概率，即過程從一種狀態(tài)轉(zhuǎn)移到另一種狀態(tài)的概率，通過被采樣變量在態(tài)轉(zhuǎn)移到另一種狀態(tài)的概率，通過被采樣變量在給定給定MarkovMarkov覆蓋下的條件概率分布定義。覆蓋下的條件概率分布定義。 令令q(x-xq(x-x) )為過程從狀態(tài)為過程從狀態(tài)x x轉(zhuǎn)移到狀態(tài)轉(zhuǎn)移到狀態(tài)x x的概率，的概率，該轉(zhuǎn)移概率定義了狀態(tài)空間上的該轉(zhuǎn)移概率定義了狀態(tài)空間上的MarkovMarkov鏈鏈, , t t(x)(x)為時刻為時刻t t

21、處于狀態(tài)處于狀態(tài)x x的概率。的概率。 t+1t+1(x(x) )表示在時刻表示在時刻t+1t+1處于狀態(tài)處于狀態(tài)x x的概率。的概率。 給定給定t t(x)(x)，我們對算法可能于時刻，我們對算法可能于時刻t t到達到達的所有狀態(tài)，通過對處于該狀態(tài)的概率與的所有狀態(tài)，通過對處于該狀態(tài)的概率與從該狀態(tài)轉(zhuǎn)移到狀態(tài)從該狀態(tài)轉(zhuǎn)移到狀態(tài)x x的概率的乘積求和來的概率的乘積求和來計算計算t+1t+1(x(x) )： 當當t t(x)= (x)= t+1t+1(x(x) )時，時，MarkovMarkov鏈達到了穩(wěn)鏈達到了穩(wěn)態(tài)分布，記為態(tài)分布，記為, ,即即1()() ()ttxxx q xx()() ()xxx q xx 對穩(wěn)態(tài)分布的理解：對穩(wěn)態(tài)分布的理解：從每個狀態(tài)的期望從每個狀態(tài)的期望“流出流出”等于來自于所有等于來自于所有狀態(tài)的期望狀態(tài)的期望“流入流入”。一個明顯滿足該關(guān)。一個明顯滿足該關(guān)系的方式是任何兩個狀態(tài)之間沿兩個方向系的方式是任何兩個狀態(tài)之間沿兩個方向的期望流量相等，稱為細致平衡：的期望流量相等，稱為細致平衡：() ()() ()xq xxx q xx 細致平衡中蘊涵著穩(wěn)態(tài)分布細致平衡中蘊涵著穩(wěn)態(tài)分布() ()() ()()()()xxxx q xxxq xxxq xxx 證明證明MCMCMCMC采樣步驟中定義的轉(zhuǎn)移概率滿足采樣步驟中定義的