轉：http://www.jianshu.com/p/f90100680749

Why：

當Graphical model不再是樹形結構的時候，factor graph并不能保證有一致的解，我們需要將原本的概率圖構造為一種樹形結構的圖，能夠在這種數據結構上執行類似factor tree中的message passing，最終得到我們所感興趣的分布。

• 它并沒有解決fator tree 中intractable的問題，在極端情況下仍然是指數的時間復雜度。
• 原本的圖有回路時，JTA提供一種inference 的方式，并且能夠得到正確的解，而factor tree不能。
• JT和factor graph 同樣都是一種數據結構，他們并不改變獨立性假設

What：

通俗的說：原本的圖有環，那么我們可以將幾個相鄰的節點合并為一個大的節點，可以消除原本存在的環。把所有原本存在的環路變為一個個超級節點，圖就變成了樹，這就是JT消除環的原理。

通過證明，無論是貝葉斯網絡還是馬兒克夫網絡的聯合概率都能夠表示成:
$$p(\chi) = \frac{\prod\phi(\chi^c)}{\prod\phi(\chi^s)}$$
（Bayesian reasoning and machine learning P102）

absorption：clique graph 通過前向后向傳播（每條邊都有兩個方向），修正后的potential對應于clique的邊緣概率。
$$P(w) = \sum_{v/s}\frac{\phi(v)\phi(w)}{\phi(s)}$$

$$p(v) = \sum_{w/s}\frac{\phi(v)\phi(w)}{\phi(s)}$$

message-passing調度：一個clique可以向另一個相鄰clique發送信息，只有當它接收了除了這個點之外所有相鄰clique的message時。

如果一個變量出現在一個環中的每條sep上時，我們可以隨便選擇一個sep，將這個變量刪除（brml p105），如果這個sep變為空，則可以刪除相應的邊，從而獲得clique tree。

Running intersection property： if a node appears in two cliques,it apprears everywhere on the path between the cliques

只有滿足了RIP，才能得到全局的一致性。（如果不滿足RIP，那么就不能通過message-passing 將這個node的信息共享給所有的clique，自然不能滿足一致性）

構建聯結樹的具體步驟（原圖是樹形的）：

如果是有向圖的話，需要先moralised，將有共同孩子的節點相連，無向圖不需要（背后的原因是：p(x|a,b) 是由三個節點共同決定的函數，可以認為三個點是一個超級節點。而對于無向圖來說不需要，因為$p(x,a,b) = \phi(x,a)\phi(x,b)$，不需要將a，b相連。

構造一個clique graph，確定哪些變量組成cliques，如果相鄰clique有交集，則加一個sep在兩個clique之間

對于一個原本就是樹形結構的圖，它的clique graph的最大支撐樹就是junction tree（最大指的是整棵樹的sep中bianliang）

每個clique 的potential 等于這個clique中的所有變量的條件概率相乘。而separator 的potential 設為1

構建聯結樹的具體步驟（原圖不是樹形的）：

當原圖有環時，variable elimination 消除變量時，消除變量的相鄰變量需要連邊，這會引入新的邊。

Triangulated Graph： 所有的長度大于3的環，必須引入弦（chord）（對應于variable elimination中新增加的邊）

但是引入chord的順序不同，可能導致clique 的大小不同，而junction tree 的性能瓶頸在于clique的大小。（我們只能通過貪心來讓最大的clique盡量小）

Greedy variable elimination：

先消除不增加邊的節點

沒有上述的節點時，先消除鄰居數量最少（或是clique table size小）的節點

直到所有節點都被消除掉
如果原圖已經有chord，那么消除變量不需要引入新的邊。
通過這種variable elimination中新加的邊，就是JT的chord

完整的JTA步驟:

Moralisation:鏈接有向圖的父母

Triangulation ：保證所有長度大于4的環有chord

Junction tree：從clique graph 中找到最大支撐樹

Potential Assignment：將原來各個變量的條件概率乘入到所屬clique的potential中

Message Propagation： 每條邊的兩個方向都需要做一次message passing

最終clique的potential就是邊緣概率。

只有原圖為樹形時，JTA才是線性的時間復雜度
當所求的分布不在同一個clique中時，需要的計算復雜度為指數形式

總結

以上是生活随笔為你收集整理的联合树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。