概率圖模型及求解方法

1、E率圖模型及求解方法本文介紹概率圖模型的定義和幾個相關(guān)算法，概率圖模型是貝葉斯統(tǒng)計和機 器學(xué)習(xí)中的一個常用方法，在自然語言處理和生物信息中也有重要應(yīng)用。關(guān)于概 率圖模型更詳細(xì)全面的介紹參見1.1 什么是概率圖模型概率圖模型簡單地說是用圖作為數(shù)據(jù)結(jié)構(gòu)來儲存概率分布的模型。圖中的節(jié) 點表示概率分布中的隨機變量，圖中的邊表示它連接的兩個隨機變量之間存在的 某種關(guān)系(具體是什么關(guān)系將在后文提到)。概率圖模型可以簡潔的表示復(fù)雜的 概率分布，并且可以利用圖論中的算法來求解概率分布中的某些特性(條件獨立 性和邊際概率)，因此得到了廣泛應(yīng)用。1.2 有向圖模型1.2.1 定義概率圖模型根據(jù)模型中的圖是否為有向

2、圖分為有向圖模型和無向圖模型兩 種。有向圖模型也叫貝葉斯網(wǎng)絡(luò)。我們考慮的有向圖模型中的圖是有向無圈圖， 有向無圈圖是指圖中兩點之間至多存在一條有向路徑。我們可以對有向無圈圖中 的節(jié)點排序，使得圖中的邊都是從序號小的節(jié)點指向序號大的節(jié)點，這種排序稱 為拓?fù)渑判?。在有向圖中，我們稱存在有向邊指向節(jié)點x的節(jié)點為x的父節(jié)點， 節(jié)點X的邊指向的節(jié)點為x的子節(jié)點。存在由節(jié)點x到節(jié)點y的一條有向路徑， 并且路徑的方向指向節(jié)點y的所有y的集合稱為x的后代節(jié)點。容易看出，在拓 撲排序下父節(jié)點的序號總是小于子節(jié)點的序號。如果圖G中存在有向圈，則節(jié) 點x可能既是節(jié)點y的父節(jié)點乂是節(jié)點的子節(jié)點，因此父節(jié)點、子節(jié)點只對

3、有向 無圈圖有意義。稱概率分布P可以由有向無圈圖G表出，如果概率分布可以分解為：KP(x) = RP(Xa lpa«)(1.1)k=T其中，pa«表示。在圖G中所有父節(jié)點組成的集合。圖1.簡單的概率圖模型例1.我們考慮圖1對應(yīng)的概率圖模型，概率分布可以寫成：P(X1,X2,X3,X4,X5) = P(X1)P(X2)P(X3 lx1,x2)P(x4 lx3)P(x5 lx2)假設(shè)每個自變量可取3個值，那么用概率圖模型表示這個概率分布，我們只需記 錄6+6+18+6+6=42個參數(shù)，而如果不用概率圖模型，則需要記錄3A5-1=242個參 數(shù)。由此可以看出概率圖模型可以節(jié)省儲存

4、空間。1.2.2 條件獨立注意到公式(1.1)中P(x/paQ取不同值時，模型表示的概率分布也不相同, 但由于這些概率分布有相同的因式圖，他們存在一些相同的性質(zhì)?？紤]隨機變量a、b、c：若它們滿足P(alb,c) = P(alb)或P(b,c) = O,則稱a與b 在給定c的條件下條件獨立，記為a_Lblc。由 P(a lb,c) = P(aI b)可以推出 P(a,blc) = P(alc)P(bIc)；反之當(dāng) P(bIc) ¥0 時，由 P(a,blc) = F(alc)P(bIc)可以推出 P(a I b,c) = P(a I b)。因此我們有a _LbIc 當(dāng)且僅 當(dāng)P(a,

5、blc) = P(alc)P(blc)。圖2.三個行點頭尾相接例2. a, b,c三個節(jié)點形狀如圖2所示,P(a,b,c) = P(a)P(cla)P(blc), a, b的概率 分布可以表示為:P(a,b) = P(a)P(c I a)P(b I c) P(a)P(b),因 a 與 b 不獨立。a, b在給定C下的條件概率為:P(a, blc)= P(a)P(clb)P(blc) = pg © p(b |c)P(c)因此a J.blc。圖3.三個直點尾尾相接例3. a, b,c三個節(jié)點形狀如圖3所示,P(a,b,c) = P(c)P(alc)P(bk), ab的概率 分布可以表示為

6、:P(a,b) = Z P(c)P(alc)P(blc)WP(a)P(b)因 a 與 b 不獨立。 a-b在給定c下的條件概率為：P(a, blc)= P(c)P(ak)P(blc) = pg © p(b |c),圖4.三個節(jié)點頭頭相接例4 a, b,c三個節(jié)點形狀如圖4所示,P(a,b,c) = P(a)P(b)P(c I a,b) , a, b的概率 分布可以表示為:P(a,b) = Z P(a)P(b)P(cla,b) = P(a)P(b),因 a 與 b 獨立。a, b 在給定c下的條件概率為：P(a)P(b)P(cla,b)P(a, b Ic)=豐 P(a lc)P(b I

7、c),P(c)因此a與b在條件c下不條件獨立。概率圖模型中圖G的結(jié)構(gòu)與概率分布P中的條件獨來性存在某種關(guān)系，為 了揭示這種關(guān)系，我們首先給出有向分隔的定義：A與B被C有向分隔如果A中任意節(jié)點到B中任意節(jié)點的路徑滿足下面兩條中的 任意一條：1 .路徑經(jīng)過C中某個節(jié)點，并且與C中節(jié)點“頭尾相連”（形如圖2）或“頭頭相 連”（圖3中的c）。2 .路徑中“頭頭相連”的節(jié)點（形如圖4中的c）和它的后代節(jié)點都不在C中。我們有下面一個定理：定理1.概率分布P可以表示由有向圖G表出當(dāng)且僅當(dāng)圖G中有向分隔對應(yīng)于概 率分布P中的條件獨立。定理證明見參考文獻(xiàn)有了定理1，我們可以通過找出圖中所有的有向分隔來找出概率分

8、布滿足的 條件獨立性，但這并不能確保找出概率分布中的所有條件獨立性。定理1同時建 立了滿足圖結(jié)構(gòu)的概率分布與滿足一定條件獨立性的概率分布之間的等價性。1.3. 向圖模型1.4. 1定義無向圖模型也叫馬爾科夫隨機場，顧名思義，無向圖模型對應(yīng)的圖是無向圖。首先給出最大團的定義：圖的最大團是指圖G的一個完全子圖C,如果在C 中加入G中的任何不在C中的節(jié)點后，C都不再是完全圖。我們稱概率分布P可以由無向圖G表出，如果概率分布可以分解為：p（x）=Jn./c（xc）（i,2）N CeQ其中X（.是與圖G中的最大團C對應(yīng)的隨機變量的集合（見1.0）,。是圖G中所 有最大團組成的集合，入（X,.）是定義在C

9、上的函數(shù)，稱為特征函數(shù)。我們只考 慮/c取值恒大于0的情形，因為只有在這個條件下，Hammersley-Clifford成立。Z = ZFU（x，）（L3）x cZ稱為劃分函數(shù)，是為了使概率分布滿足歸一性而定義的量。我們可以靈活的定 義人，而不用考慮概率分布的歸一性。例5.圖5中的無向圖模型的概率分布為：P（xpx2,x3,x4） = /；（xI,x2,x3）./,（x2,x5）./i（x3,x4）/Z1.5. 2條件獨立性與有向圖模型類似，我們首先定義無向圖模型中分隔的定義，然后給出分隔 與條件獨立的關(guān)系。無向圖模型的分隔定義與圖論中的分隔定義完全一致：在圖G中，稱節(jié)點 集A與節(jié)點集B被節(jié)點

10、集C分隔開如果在G中刪除C中的節(jié)點后，A與B之間 不存在任何路徑。定理2 (Hammersley-Clifford)如果無向圖模型中的特征函數(shù)取值恒大于0,那么 概率分布P可以表示由無向圖G表出當(dāng)且僅當(dāng)圖G中分隔對應(yīng)于P中的條件獨 立。有了定理2,我們可以通過找出圖中所有的分隔來找出概率分布滿足的條件 獨立性。圖5. 一個簡單的無向圖模型(與圖1相對應(yīng))1.3.3有向圖模型與無向圖模型之間的關(guān)系有向圖模型總是可以轉(zhuǎn)換為無向圖模型。我們只需要連接每個節(jié)點的任意兩 個父節(jié)點，然后把有向邊變?yōu)闊o向邊，這樣我們原來有向圖中的每一個節(jié)點與其 父節(jié)點形成的子圖是完全圖，令人(x4,pa*) = P(x.p

11、aJ)、Z = l,有向圖模型就 轉(zhuǎn)化成了無向圖模型。 例如：令/1(x1,x2,x3) = P(x31 XpX2), f2(x2,x5) = P(x5 lx3) , f3(x3,x4) = P(x4 I x3), Z=1,則例 5 表示的模型就是例 1 表示的模型，如圖5所示。1.6. 率圖模型的兩個基本問題1.7. 1兩個基本問題考慮兩個基本問題:1 .求概率分布的邊際分布，即p（Xj）=z_、p（x），符號E.表示對除去看以 外的所有隨機變量求和。2 .求概率取值最大的基本事件，即求xgx=argmaxP（x）,這個問題也叫 推斷問題?！睘榱嗣枋鼋鉀Q這兩個問題的算法，我們首先給出因式圖的

12、定義。因式圖中的節(jié)點分為兩種，一種稱為因式節(jié)點，對應(yīng)概率圖模型中的特征函數(shù)；一種稱為變 量節(jié)點，對應(yīng)于概率圖模型中的隨機變量。因式節(jié)點與它的對應(yīng)的自變量之間有 一條連線。因式圖是二部圖。例5的因式圖如圖6所示。圖6.例5對應(yīng)的因式圖對于因式圖為樹的模型，sum-product算法是求邊際分布的一個有效精確算 法，max-sum算法是為解決推斷問題的一個有效精確算法。這一節(jié)介紹的sum-product算法和max-sum算法都是針對無向圖模型的算 法，對于有向圖模型可以通過133介紹的方法轉(zhuǎn)換為無向圖模型。1.4. 2sum-product 算法為了理解sum-product算法，我們首先考慮最

13、簡單情形，即因式圖是一條鏈 的情形，如圖7所示。利用乘法結(jié)合律，我們有：尸= jZ/；（XI，X2）/2（X2，X3）.f"Xg,X"）2人制血）Z（Xg,X.）其中X,代表第i個變量的取值，我們令:4(Xz)=,%(X2)= /2(XrX3)/(X3)P(x2) = /7(x2)/za(x2)與計算P(X。的情形類似，我們只需要求出4(Xj 尸(Xj)即可求出P(Xj)概 率分布，如圖7所示。%(xQ圖7,圖模型為鏈時求邊際概率的算法我們分析一下算法復(fù)雜性，假設(shè)每個節(jié)點可以取到m個狀態(tài)，對每一個X， 計算Wf(x,T，Xj)需要m次加法運算，因此總共需要n次加法運算。計算

14、 /a(x2)需要m次加法計算，計算(X?)需要(n-3)m2 + m次加法運算和n-2次乘 法運算，因此總共需要Odvn?)次運算。如果不利用上述公式，直接枚舉所有 P(x)然后求和需要0?！看?次運算。由此可以看出sum-product算法極大的降低 了時間復(fù)雜性。下面給出一般情形的sum-product算法,我們計算變量為的概率分布,把看看 作根節(jié)點，為了記號方便，把變量芯的取值也記為罰，可以得到：P(X,) = ZP(X)= Z I K(Xj，XQ= fl ZRXj，XQ國樂 swe(x)sw，e(x) Xs=n /(L4)sene(x)其中/;-為儀,)=2,以儀,，*5)可以看作由

15、£傳遞到匕的信息，它對應(yīng)有向 邊(£,%),如圖8所示：Xj$表示與節(jié)點為相連的£所在分支中的所有隨機變量 的集合，工(X,X、)等于工，所在分支中所有因式的乘積。圖8.求邊際概率尸(x,)假設(shè)(X1,X2，.Xm是的自變量，R(Xj,X，)可以寫為：E (xj, Xs ) = t(X” X,., X M ) G(X, X“ ). G M(X時,X加)其中G,是與對應(yīng)的分支里所有因式的乘積，如圖9所示。把上式代入七一七 (X。= £月(Xi，XJ 得：X,"fsTXj(Xi)= ZZ G(X,Xs).Gm(Xm，Xs,“)r!XMXJX1，X2

16、.-XW 二 z e £( x i, x 1,x m)n z G < x 團,X 刖) 玉xmmene(f5)Xi Xsm其中e(f$)表示與£相鄰的節(jié)點的集合也就是£的自變量的集合，X”表示與，相連的4所在分支中的所有隨機變量的集合，見圖9。令 X/)= ZG,“(x,X”“)我們得到：勺f 區(qū))二 W£(X，XI，,Xm) n 4i(X,)(1.5)X| A；ymene(fs )X/(x,)可以看作由/傳遞到，的信息，它對應(yīng)有向邊(4,力)。圖9.由乙傳遞到。的信息 (X,)是4對應(yīng)的分支里所有因式的乘積，因此有：G,(x,，X,)= n 5(

17、x,，X“)lne(fs)fs代入此1(X加)=ZG,(Xj“, X.)得到：Xg即)=z n 尸/區(qū))=n z 4(x,“，x“)xsfn lene(fs )fv/eneffJXf Xml=n me(ie/01也M其中，X,”,表示與4相連的為所在分支中的所有隨機變量的集合，見圖10。 耳(Xj,Xs)與式(1.4)中定義一樣。圖10. ft傳遞到Xm的信息/心(X)這樣，我們就推導(dǎo)出了 sum-product算法中的信息傳遞函數(shù)(L5)和(1.6),下 面我們考慮信息傳遞的順序，把需要求概率分布的變量看作根節(jié)點，我們可以構(gòu) 造一個有向樹(這個樹只有一個父節(jié)點)，使得樹的邊的方向都是指向根節(jié)

18、點。 首先信息從最靠外連接葉節(jié)點的邊向內(nèi)傳遞，當(dāng)一個節(jié)點的所有連接子節(jié)點的邊 都傳遞信息到了這個節(jié)點后，這個節(jié)點再向它的父節(jié)點傳遞信息?？梢钥闯霭凑?這個規(guī)定，只要給定連接葉節(jié)點的邊一組初始信息，那么信息會遍歷圖中每一條 邊，傳向根節(jié)點，根節(jié)點連接的每條邊都向根節(jié)點傳遞了信息后，我們便可按照 公式(1.4)求出概率分布。下面我們給出初始信息，當(dāng)信息所在的邊連接的葉節(jié)點 是變量節(jié)點時，當(dāng)信息所在的邊連接的葉節(jié)點是因式節(jié)點時， 勺(x) = /(x)。容易的驗證初始信息的正確性。下面我們來分析一下sum-product的計算復(fù)雜性:假設(shè)每個變量可取m個值, 工,的自變量個數(shù)為M,注意公式(1.5)

19、,計算，區(qū))時，需要對nF項求和。因 此計算復(fù)雜性與無向圖G的最大團中的節(jié)點個數(shù)n正相關(guān)，并且呈指數(shù)增長。 因此特征函數(shù)的變量個數(shù)越少，時間復(fù)雜性越低。算法 1. sum-product 算法初始條件：對連接葉節(jié)點的邊，定義初始信息為：4 f (x) = l(X) = /(X)信息傳遞函數(shù):4f(x) = X,W/'(x，X|,.,Xm)n(1.7)Xj xMmene(f)xi4一/(x)= 口 4f (x)(1.8)/ene(f)f信息傳遞協(xié)議：山葉節(jié)點向根節(jié)點方向傳遞，當(dāng)一個節(jié)點的所有連接子節(jié)點的邊 上信息都傳遞到了這個節(jié)點后，這個節(jié)點再向它的父節(jié)點傳遞信息。算法終止：根節(jié)點連接的

20、每條邊都向根節(jié)點傳遞了信息，利用公式(1.4)計算出邊 際概率。計算邊際概率分布：尸&)= n hlJx,)sne(x)注意到對于每一個節(jié)點，我們都可以按照公式(1.4)求出節(jié)點的概率分布。因 此只要我們知道因式圖上每條邊的兩個方向的信息傳遞函數(shù)后，我們便可計算出 所有變量的邊際概率分布。為此，我們只需在sum-product算法結(jié)束后，由根節(jié) 點向葉節(jié)點反向求出所有信息，如圖11所示。圖11.由根節(jié)點反向傳遞信息1.4. 3max-sum 算法在計算概率的時候，可能會出現(xiàn)概率非常接近0的情況，這時會出現(xiàn)下溢問 題。為了避免這個問題，我們計算log-概率：In P(x) = Zlnf

21、(x,)-ZceQ其中Z是一個常數(shù)，因此我們只需計算4%1】穌2足工.61。x <eQmax-product算法利用了 max(a + b,a + c) = a + max(b,c)這個思想。注意到這 個式子與乘法分配率ab+ac = a(b+c)形式類似(加法對應(yīng)求最大值，乘法對應(yīng)加 法)，因此max-product算法與sum-product算法形式一致。我們可以按照 sum-product算法的思路，推出max-sum算法。注意到max-sum算法需要找出取 最大概率的基本事件，我們需要在信息傳遞過程中記錄：' = argmaxln/(x,x”,xQ+xi .xm)x,最后

22、從根節(jié)點利用上式反推出最大概率事件中各個隨機變量的取值。算法2. max-sum算法初始條件：對連接葉節(jié)點的邊，定義初始信息為:Nxt f(X)= °/»(x) = ln/(x)信息傳遞函數(shù)：(1.9)(1.10)勺f (x) = max In f(x, x，,x)+ / (xQ4一/(x)= A "/-x(x) /ene(Df信息傳遞協(xié)議：隨機選定樹中的一個節(jié)點作為根節(jié)點，信息由葉節(jié)點向根節(jié)點方 向傳遞，當(dāng)一個節(jié)點的所有連接子節(jié)點的邊上信息都傳到了這個節(jié)點后，這個節(jié) 點再向它的父節(jié)點傳遞信息。記錄:在信息傳遞函數(shù)中，記錄：= argmaxln/(x,x,xA/) + Z /%c/(x,)(1.11)內(nèi)，,KMme/ie(fx )Xj算法終止：根節(jié)點連接的每條邊都向根節(jié)點傳遞了信息，再反向從根節(jié)點利用公 式找出最大概率對應(yīng)的基本事件。1.4.4帶圈置信傳播算法我們可以把sum-produ