概率圖模型及求解方法

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

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

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

4、空間。1.2.2 條件獨(dú)立注意到公式(1.1)中P(x/paQ取不同值時(shí)，模型表示的概率分布也不相同, 但由于這些概率分布有相同的因式圖，他們存在一些相同的性質(zhì)?？紤]隨機(jī)變量a、b、c：若它們滿足P(alb,c) = P(alb)或P(b,c) = O,則稱a與b 在給定c的條件下條件獨(dú)立，記為a_Lblc。由 P(a lb,c) = P(aI b)可以推出 P(a,blc) = P(alc)P(bIc)；反之當(dāng) P(bIc) ¥0 時(shí)，由 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.三個(gè)行點(diǎn)頭尾相接例2. a, b,c三個(gè)節(jié)點(diǎn)形狀如圖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 不獨(dú)立。a, b在給定C下的條件概率為:P(a, blc)= P(a)P(clb)P(blc) = pg © p(b |c)P(c)因此a J.blc。圖3.三個(gè)直點(diǎn)尾尾相接例3. a, b,c三個(gè)節(jié)點(diǎn)形狀如圖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 不獨(dú)立。 a-b在給定c下的條件概率為：P(a, blc)= P(c)P(ak)P(blc) = pg © p(b |c),圖4.三個(gè)節(jié)點(diǎn)頭頭相接例4 a, b,c三個(gè)節(jié)點(diǎn)形狀如圖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 獨(dú)立。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下不條件獨(dú)立。概率圖模型中圖G的結(jié)構(gòu)與概率分布P中的條件獨(dú)來性存在某種關(guān)系，為 了揭示這種關(guān)系，我們首先給出有向分隔的定義：A與B被C有向分隔如果A中任意節(jié)點(diǎn)到B中任意節(jié)點(diǎn)的路徑滿足下面兩條中的 任意一條：1 .路徑經(jīng)過C中某個(gè)節(jié)點(diǎn)，并且與C中節(jié)點(diǎn)“頭尾相連”（形如圖2）或“頭頭相 連”（圖3中的c）。2 .路徑中“頭頭相連”的節(jié)點(diǎn)（形如圖4中的c）和它的后代節(jié)點(diǎn)都不在C中。我們有下面一個(gè)定理：定理1.概率分布P可以表示由有向圖G表出當(dāng)且僅當(dāng)圖G中有向分隔對(duì)應(yīng)于概 率分布P中的條件獨(dú)立。定理證明見參考文獻(xiàn)有了定理1，我們可以通過找出圖中所有的有向分隔來找出概率分

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

9、上的函數(shù)，稱為特征函數(shù)。我們只考 慮/c取值恒大于0的情形，因?yàn)橹挥性谶@個(gè)條件下，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條件獨(dú)立性與有向圖模型類似，我們首先定義無向圖模型中分隔的定義，然后給出分隔 與條件獨(dú)立的關(guān)系。無向圖模型的分隔定義與圖論中的分隔定義完全一致：在圖G中，稱節(jié)點(diǎn) 集A與節(jié)點(diǎn)集B被節(jié)點(diǎn)

10、集C分隔開如果在G中刪除C中的節(jié)點(diǎn)后，A與B之間 不存在任何路徑。定理2 (Hammersley-Clifford)如果無向圖模型中的特征函數(shù)取值恒大于0,那么 概率分布P可以表示由無向圖G表出當(dāng)且僅當(dāng)圖G中分隔對(duì)應(yīng)于P中的條件獨(dú) 立。有了定理2,我們可以通過找出圖中所有的分隔來找出概率分布滿足的條件 獨(dú)立性。圖5. 一個(gè)簡單的無向圖模型(與圖1相對(duì)應(yīng))1.3.3有向圖模型與無向圖模型之間的關(guān)系有向圖模型總是可以轉(zhuǎn)換為無向圖模型。我們只需要連接每個(gè)節(jié)點(diǎn)的任意兩 個(gè)父節(jié)點(diǎn)，然后把有向邊變?yōu)闊o向邊，這樣我們原來有向圖中的每一個(gè)節(jié)點(diǎn)與其 父節(jié)點(diǎn)形成的子圖是完全圖，令人(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. 率圖模型的兩個(gè)基本問題1.7. 1兩個(gè)基本問題考慮兩個(gè)基本問題:1 .求概率分布的邊際分布，即p（Xj）=z_、p（x），符號(hào)E.表示對(duì)除去看以 外的所有隨機(jī)變量求和。2 .求概率取值最大的基本事件，即求xgx=argmaxP（x）,這個(gè)問題也叫 推斷問題。”為了描述解決這兩個(gè)問題的算法，我們首先給出因式圖的

12、定義。因式圖中的節(jié)點(diǎn)分為兩種，一種稱為因式節(jié)點(diǎn)，對(duì)應(yīng)概率圖模型中的特征函數(shù)；一種稱為變 量節(jié)點(diǎn)，對(duì)應(yīng)于概率圖模型中的隨機(jī)變量。因式節(jié)點(diǎn)與它的對(duì)應(yīng)的自變量之間有 一條連線。因式圖是二部圖。例5的因式圖如圖6所示。圖6.例5對(duì)應(yīng)的因式圖對(duì)于因式圖為樹的模型，sum-product算法是求邊際分布的一個(gè)有效精確算 法，max-sum算法是為解決推斷問題的一個(gè)有效精確算法。這一節(jié)介紹的sum-product算法和max-sum算法都是針對(duì)無向圖模型的算 法，對(duì)于有向圖模型可以通過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個(gè)變量的取值，我們令:4(Xz)=,%(X2)= /2(XrX3)/(X3)P(x2) = /7(x2)/za(x2)與計(jì)算P(X。的情形類似，我們只需要求出4(Xj 尸(Xj)即可求出P(Xj)概 率分布，如圖7所示。%(xQ圖7,圖模型為鏈時(shí)求邊際概率的算法我們分析一下算法復(fù)雜性，假設(shè)每個(gè)節(jié)點(diǎn)可以取到m個(gè)狀態(tài)，對(duì)每一個(gè)X， 計(jì)算Wf(x,T，Xj)需要m次加法運(yùn)算，因此總共需要n次加法運(yùn)算。計(jì)算

14、 /a(x2)需要m次加法計(jì)算，計(jì)算(X?)需要(n-3)m2 + m次加法運(yùn)算和n-2次乘 法運(yùn)算，因此總共需要Odvn?)次運(yùn)算。如果不利用上述公式，直接枚舉所有 P(x)然后求和需要0。】打)次運(yùn)算。由此可以看出sum-product算法極大的降低 了時(shí)間復(fù)雜性。下面給出一般情形的sum-product算法,我們計(jì)算變量為的概率分布,把看看 作根節(jié)點(diǎn)，為了記號(hào)方便，把變量芯的取值也記為罰，可以得到：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、£傳遞到匕的信息，它對(duì)應(yīng)有向 邊(£,%),如圖8所示：Xj$表示與節(jié)點(diǎn)為相連的£所在分支中的所有隨機(jī)變量 的集合，工(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時(shí),X加)其中G,是與對(duì)應(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 團(tuán),X 刖) 玉xmmene(f5)Xi Xsm其中e(f$)表示與£相鄰的節(jié)點(diǎn)的集合也就是£的自變量的集合，X”表示與，相連的4所在分支中的所有隨機(jī)變量的集合，見圖9。令 X/)= ZG,“(x,X”“)我們得到：勺f 區(qū))二 W£(X，XI，,Xm) n 4i(X,)(1.5)X| A；ymene(fs )X/(x,)可以看作由/傳遞到，的信息，它對(duì)應(yīng)有向邊(4,力)。圖9.由乙傳遞到。的信息 (X,)是4對(duì)應(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相連的為所在分支中的所有隨機(jī)變量的集合，見圖10。 耳(Xj,Xs)與式(1.4)中定義一樣。圖10. ft傳遞到Xm的信息/心(X)這樣，我們就推導(dǎo)出了 sum-product算法中的信息傳遞函數(shù)(L5)和(1.6),下 面我們考慮信息傳遞的順序，把需要求概率分布的變量看作根節(jié)點(diǎn)，我們可以構(gòu) 造一個(gè)有向樹(這個(gè)樹只有一個(gè)父節(jié)點(diǎn))，使得樹的邊的方向都是指向根節(jié)

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

19、,計(jì)算，區(qū))時(shí)，需要對(duì)nF項(xiàng)求和。因 此計(jì)算復(fù)雜性與無向圖G的最大團(tuán)中的節(jié)點(diǎn)個(gè)數(shù)n正相關(guān)，并且呈指數(shù)增長。 因此特征函數(shù)的變量個(gè)數(shù)越少，時(shí)間復(fù)雜性越低。算法 1. sum-product 算法初始條件：對(duì)連接葉節(jié)點(diǎn)的邊，定義初始信息為：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é)點(diǎn)向根節(jié)點(diǎn)方向傳遞，當(dāng)一個(gè)節(jié)點(diǎn)的所有連接子節(jié)點(diǎn)的邊 上信息都傳遞到了這個(gè)節(jié)點(diǎn)后，這個(gè)節(jié)點(diǎn)再向它的父節(jié)點(diǎn)傳遞信息。算法終止：根節(jié)點(diǎn)連接的

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

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

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