概率圖模型及求解方法

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

2、圖分為有向圖模型和無向圖模型兩 種。有向圖模型也叫貝葉斯網(wǎng)絡。我們考慮的有向圖模型中的圖是有向無圈圖， 有向無圈圖是指圖中兩點之間至多存在一條有向路徑。我們可以對有向無圈圖中 的節(jié)點排序，使得圖中的邊都是從序號小的節(jié)點指向序號大的節(jié)點，這種排序稱 為拓撲排序。在有向圖中，我們稱存在有向邊指向節(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對應的概率圖模型，概率分布可以寫成：P(X1,X2,X3,X4,X5) = P(X1)P(X2)P(X3 lx1,x2)P(x4 lx3)P(x5 lx2)假設每個自變量可取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)；反之當 P(bIc) ¥0 時，由 P(a,blc) = F(alc)P(bIc)可以推出 P(a I b,c) = P(a I b)。因此我們有a _LbIc 當且僅 當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的結構與概率分布P中的條件獨來性存在某種關系，為 了揭示這種關系，我們首先給出有向分隔的定義：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表出當且僅當圖G中有向分隔對應于概 率分布P中的條件獨立。定理證明見參考文獻有了定理1，我們可以通過找出圖中所有的有向分隔來找出概率分

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

10、集C分隔開如果在G中刪除C中的節(jié)點后，A與B之間 不存在任何路徑。定理2 (Hammersley-Clifford)如果無向圖模型中的特征函數(shù)取值恒大于0,那么 概率分布P可以表示由無向圖G表出當且僅當圖G中分隔對應于P中的條件獨 立。有了定理2,我們可以通過找出圖中所有的分隔來找出概率分布滿足的條件 獨立性。圖5. 一個簡單的無向圖模型(與圖1相對應)1.3.3有向圖模型與無向圖模型之間的關系有向圖模型總是可以轉(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）,這個問題也叫 推斷問題。”為了描述解決這兩個問題的算法，我們首先給出因式圖的

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

13、簡單情形，即因式圖是一條鏈 的情形，如圖7所示。利用乘法結合律，我們有：尸= 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,圖模型為鏈時求邊際概率的算法我們分析一下算法復雜性，假設每個節(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算法極大的降低 了時間復雜性。下面給出一般情形的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、£傳遞到匕的信息，它對應有向 邊(£,%),如圖8所示：Xj$表示與節(jié)點為相連的£所在分支中的所有隨機變量 的集合，工(X,X、)等于工，所在分支中所有因式的乘積。圖8.求邊際概率尸(x,)假設(X1,X2，.Xm是的自變量，R(Xj,X，)可以寫為：E (xj, Xs ) = t(X” X,., X M ) G(X, X“ ). G M(X時,X加)其中G,是與對應的分支里所有因式的乘積，如圖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,)可以看作由/傳遞到，的信息，它對應有向邊(4,力)。圖9.由乙傳遞到。的信息 (X,)是4對應的分支里所有因式的乘積，因此有：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)這樣，我們就推導出了 sum-product算法中的信息傳遞函數(shù)(L5)和(1.6),下 面我們考慮信息傳遞的順序，把需要求概率分布的變量看作根節(jié)點，我們可以構 造一個有向樹(這個樹只有一個父節(jié)點)，使得樹的邊的方向都是指向根節(jié)

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

19、,計算，區(qū))時，需要對nF項求和。因 此計算復雜性與無向圖G的最大團中的節(jié)點個數(shù)n正相關，并且呈指數(shù)增長。 因此特征函數(shù)的變量個數(shù)越少，時間復雜性越低。算法 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é)點方向傳遞，當一個節(jié)點的所有連接子節(jié)點的邊 上信息都傳遞到了這個節(jié)點后，這個節(jié)點再向它的父節(jié)點傳遞信息。算法終止：根節(jié)點連接的

20、每條邊都向根節(jié)點傳遞了信息，利用公式(1.4)計算出邊 際概率。計算邊際概率分布：尸&)= n hlJx,)sne(x)注意到對于每一個節(jié)點，我們都可以按照公式(1.4)求出節(jié)點的概率分布。因 此只要我們知道因式圖上每條邊的兩個方向的信息傳遞函數(shù)后，我們便可計算出 所有變量的邊際概率分布。為此，我們只需在sum-product算法結束后，由根節(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)形式類似(加法對應求最大值，乘法對應加 法)，因此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é)點方 向傳遞，當一個節(jié)點的所有連接子節(jié)點的邊上信息都傳到了這個節(jié)點后，這個節(jié) 點再向它的父節(jié)點傳遞信息。記錄:在信息傳遞函數(shù)中，記錄：= argmaxln/(x,x,xA/) + Z /%c/(x,)(1.11)內(nèi)，,KMme/ie(fx )Xj算法終止：根節(jié)點連接的每條邊都向根節(jié)點傳遞了信息，再反向從根節(jié)點利用公 式找出最大概率對應的基本事件。1.4.4帶圈置信傳播算法我們可以把sum-produ