計(jì)算智能課件24bayesian network2

1、 貝葉斯網(wǎng)絡(luò)中的精確推理 通過枚舉進(jìn)行推理 變量消元算法 精確推理的復(fù)雜度 團(tuán)算法 貝葉斯網(wǎng)絡(luò)中的近似推理直接采樣算法Markov鏈仿真推理 簡(jiǎn)單詢問：計(jì)算后驗(yàn)邊緣概率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) 敏感性分析：哪個(gè)因素起關(guān)鍵作用 最佳解釋：比如為什么需要一個(gè)新的引擎？(| ,)( )( )( |, ) ( | ) (| )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 從因子乘積中對(duì)一個(gè)變量進(jìn)行求和消元是從因子乘積中對(duì)一個(gè)變量進(jìn)行求和消元是直接計(jì)算。注意的技巧是，任何不依賴于直接計(jì)算。注意的技巧是，任何不依賴于將被求和消元的變量都可以移到求和符號(hào)將被求和消元的變量都可以移到求和符號(hào)的外面。的外面。 注意直到我們需要將變量從累積乘積中消注意直到我們需要將變量從累積乘積中消去前不會(huì)進(jìn)行矩陣乘法。去前不會(huì)進(jìn)行矩陣乘法。 可以刪除任何既非查詢變量，也非證據(jù)變可以刪除任何既非查詢變量，也非

5、證據(jù)變量的葉節(jié)點(diǎn)。量的葉節(jié)點(diǎn)。),()()(),()()()()()(),()(,BAfAfAfeBAfefAfAfAfAfeBAfefAEMJeAEeMJMJAEMultiply connected networks:在最壞情況下，具有指數(shù)級(jí)的時(shí)間空間復(fù)雜度在最壞情況下，具有指數(shù)級(jí)的時(shí)間空間復(fù)雜度. .團(tuán)算法團(tuán)算法（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 對(duì)于回答單個(gè)查詢，變量消元算法是簡(jiǎn)單對(duì)于回答單個(gè)查詢，變量消元算法是簡(jiǎn)單有效的。然而，若希望計(jì)算網(wǎng)絡(luò)中所有節(jié)有效的。然而，若希望計(jì)算網(wǎng)絡(luò)中所有節(jié)點(diǎn)的后驗(yàn)概率它就不那么有效率了。點(diǎn)的后驗(yàn)概率它就不那么有效率了。 例如，在一個(gè)是多樹網(wǎng)絡(luò)中可能需要處理例如，在一個(gè)是多樹網(wǎng)絡(luò)中可能需要處理O(n)O(n)個(gè)查詢，查詢共需要個(gè)查詢，查詢共需要O(n)O(n)的開銷，因的開銷，因此總的時(shí)間復(fù)雜度是此總的時(shí)間復(fù)雜度是O(nO(n2 2).). 通過團(tuán)算法（聯(lián)合樹算法），時(shí)間可以減通過團(tuán)算法（聯(lián)合樹算法），時(shí)間可以減少到少到O(n).O(n). 精確推理的局

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

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

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

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

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

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

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

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

15、進(jìn)行采樣: :Parents(Zi)Parents(Zi)可能包含隱變量和證據(jù)變量。與可能包含隱變量和證據(jù)變量。與P(z)P(z)不不同的是，同的是，SwsSws給予證據(jù)某種特別的關(guān)注：每個(gè)給予證據(jù)某種特別的關(guān)注：每個(gè)ZiZi的采的采樣值會(huì)受到它的祖先節(jié)點(diǎn)中證據(jù)的影響，另外，樣值會(huì)受到它的祖先節(jié)點(diǎn)中證據(jù)的影響，另外， SwsSws對(duì)證據(jù)的考慮要少于對(duì)真實(shí)的后驗(yàn)概對(duì)證據(jù)的考慮要少于對(duì)真實(shí)的后驗(yàn)概P(z|e)P(z|e)的考慮。的考慮。 似然權(quán)值似然權(quán)值w w補(bǔ)償了真實(shí)采樣分布與期望采樣補(bǔ)償了真實(shí)采樣分布與期望采樣分布之間的差距分布之間的差距 對(duì)已知事件對(duì)已知事件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)回到一致估計(jì)似然加權(quán)回到一致估計(jì) 使用了所有的樣本，效率比拒絕采樣高。使用了所有的樣本，效率比拒絕采樣高。 局限性：局限性： 證據(jù)變量的個(gè)數(shù)增加時(shí)，它仍然要承受大證據(jù)變量的個(gè)數(shù)增加時(shí)，它仍然要承受大幅度的性能下降。因?yàn)榇蠖鄶?shù)的樣本權(quán)值幅度的性能下降。因?yàn)榇蠖鄶?shù)的樣本權(quán)值都非常低，導(dǎo)致在加權(quán)估計(jì)中起主導(dǎo)作用都非常低，導(dǎo)致在加權(quán)估計(jì)中起主導(dǎo)作用的只是

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

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

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

20、T,T,T.F,T,T,T. 基本觀點(diǎn)：基本觀點(diǎn)：采樣過程最終會(huì)進(jìn)入一種動(dòng)態(tài)平衡。采樣過程最終會(huì)進(jìn)入一種動(dòng)態(tài)平衡。 該特性來(lái)自于特定的轉(zhuǎn)移概率，即過程從一種狀該特性來(lái)自于特定的轉(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)為時(shí)刻為時(shí)刻t t

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