機(jī)器學(xué)習(xí)概率圖模型推理團(tuán)樹(shù)算法

在之前的消息傳遞算法中，談到了聚類圖模型的一些性質(zhì)。其中就有消息不能形成閉環(huán)，否則會(huì)導(dǎo)致“假消息傳到最后我自己都信了”。為了解決這種問(wèn)題，引入了一種稱為團(tuán)樹(shù)（cliquetree)的數(shù)據(jù)結(jié)構(gòu)，樹(shù)模型沒(méi)有圖模型中的環(huán)，所以此模型要比圖模型更健壯，更容易收斂。1.團(tuán)樹(shù)模型鏈模型是一種最簡(jiǎn)單的樹(shù)模型，其結(jié)構(gòu)如下圖所示，假設(shè)信息從最左端傳入則有以下式子。假設(shè)要對(duì)變量CD進(jìn)行推斷，則應(yīng)該求Belief(3)

=deta2->3*deta4->3*phi(3).從這里可以看出，團(tuán)樹(shù)算法是一種精確推斷算法。它和變量消除算法在理論推導(dǎo)上是等價(jià)的。上面的例子只是一種非常簡(jiǎn)單的團(tuán)樹(shù)，團(tuán)樹(shù)的本質(zhì)還是聚類圖，只不過(guò)是一種特殊的聚類圖。對(duì)于更一般的概率圖，也可以生成團(tuán)樹(shù)圖。其中，每個(gè)cluster都是變量消除誘導(dǎo)圖中的一個(gè)最小map。

2.團(tuán)樹(shù)模型的計(jì)算從上面分析可知，團(tuán)樹(shù)模型本質(zhì)上和變量消除算法還有說(shuō)不清道不明的關(guān)系（團(tuán)樹(shù)模型也是精確推理模型）。但是這個(gè)算法的優(yōu)勢(shì)在于，它可以利用消息傳遞機(jī)制達(dá)到收斂。之前提過(guò)，聚類圖模型中的收斂指的是消息不變。除此之外，聚類圖的本質(zhì)是一種數(shù)據(jù)結(jié)構(gòu)，它可以儲(chǔ)存很多中間計(jì)算結(jié)果。如果我們有很多變量ABCDEF，那么我們想知道P(A)，則需要執(zhí)行一次變量消除。如果要計(jì)算P(B)又要執(zhí)行一次變量消除。如果中途得到了某個(gè)變量的觀測(cè)，又會(huì)對(duì)算法全局產(chǎn)生影響。但是使用團(tuán)樹(shù)模型可以巧妙的避免這些問(wèn)題。首先，一旦模型迭代收斂之后。所有的消息都是不變的，每個(gè)消息都是可以被讀取的。每個(gè)團(tuán)的belief，實(shí)際上就是未歸一劃的聯(lián)合概率，要算單個(gè)變量的概率，只需要把其他的變量邊際掉就行。這樣一來(lái)，只需要一次迭代收斂，每個(gè)變量的概率都是可算的。并且算起來(lái)方便。其次，如果對(duì)模型引入先驗(yàn)知識(shí)比如A=a時(shí)，我們需要對(duì)D的概率進(jìn)行估計(jì)。按照變量消除的思路又要從頭來(lái)一次。但是如果使用團(tuán)樹(shù)結(jié)構(gòu)則不用，因?yàn)锳的取值只影響deta1->2以及左向傳遞的消息，對(duì)右向傳遞的消息則毫無(wú)影響，可以保留原先對(duì)右向傳遞消息的計(jì)算值，只重新計(jì)算左向傳遞結(jié)果即可。總而言之，使用團(tuán)樹(shù)算法相對(duì)于變量消除算法，可以大幅降低計(jì)算規(guī)模，也便于對(duì)任意一個(gè)隨機(jī)變量進(jìn)行查詢。

3.團(tuán)樹(shù)算法與獨(dú)立性聚類圖是由概率圖分析得到的。同樣，聚類圖中也繼承了概率圖在獨(dú)立性方面的某些特性。團(tuán)樹(shù)圖有以下性質(zhì)：如果能觀測(cè)到edge上的變量，則edge兩端的變量的獨(dú)立的。顯然，如果給定GS,CDI與HJL就是獨(dú)立的。4.團(tuán)樹(shù)算法與VE算法的聯(lián)系之前提到團(tuán)樹(shù)算法和VE算法都是精確推理的算法。本質(zhì)上他們之間存在對(duì)應(yīng)關(guān)系。1.團(tuán)樹(shù)傳遞的消息實(shí)際上是兩個(gè)cluster之間共同變量。從1->2消除了1中2不包含的變量。這與VE算法中把勢(shì)函數(shù)邊際成

τ是一樣的。也就是說(shuō)deta--->tau.

2.團(tuán)樹(shù)的cluster是多個(gè)phi相乘得到的。多個(gè)phi相乘是VE算法構(gòu)造初始的因子相乘。利用團(tuán)樹(shù)算法和VE算法之間的關(guān)系，我們可以利用模擬VE算法運(yùn)行，來(lái)生成團(tuán)樹(shù)圖。也就是說(shuō)，假設(shè)我在執(zhí)行VE算法（順序由概率圖決定）,用VE算法生成團(tuán)樹(shù)圖，再利用團(tuán)樹(shù)結(jié)構(gòu)簡(jiǎn)化VE的計(jì)算，最終達(dá)到變量推斷的目的。圖中顯示了一個(gè)簡(jiǎn)單的例子。

5.實(shí)際置信傳播算法的操作在之前的分析中，我們已經(jīng)得到了消息傳遞算法的性質(zhì)，執(zhí)行機(jī)制等。但是如果把它編程成代碼的時(shí)候，我們會(huì)遇到以下幾個(gè)問(wèn)題：1.如果cluster很多，我每次只傳遞一條消息，那么大部分節(jié)點(diǎn)都處于無(wú)所事事?tīng)顟B(tài)，這樣好么2.迭代一定次數(shù)以后一定會(huì)收斂嗎3.收斂了結(jié)果一定對(duì)嗎4.怎樣才能盡可能收斂針對(duì)第一個(gè)問(wèn)題，計(jì)算機(jī)科學(xué)家采用的往往是并行消息傳遞，并行消息傳遞又分同時(shí)傳遞與非對(duì)稱傳遞（主要針對(duì)網(wǎng)格聚類圖），結(jié)果是非同時(shí)傳遞的效果往往更好。此外，還可以在圖中選出一棵團(tuán)樹(shù)，盡量在這棵團(tuán)樹(shù)上達(dá)到收斂，以保證盡可能多的節(jié)點(diǎn)收斂。本身只有形成環(huán)的時(shí)候才會(huì)不收斂。第二個(gè)問(wèn)題，是不是一定會(huì)收斂，答案是不是的，奇怪的是有些消息會(huì)收斂，有些消息卻不會(huì)。實(shí)際上在傳遞的過(guò)程中，有些消息已經(jīng)達(dá)成平衡，在平衡狀態(tài)下和其他不收斂的消息解耦了。此外，消息傳遞順序?qū)κ諗啃杂绊懸埠艽?。第三個(gè)問(wèn)題，結(jié)果不一