為什么需要聯(lián)結(jié)樹：
當(dāng)Graphical model不再是樹形結(jié)構(gòu)的時候含蓉，factor graph并不能保證有一致的解，我們需要將原本的概率圖構(gòu)造為一種樹形結(jié)構(gòu)的圖帮哈，能夠在這種數(shù)據(jù)結(jié)構(gòu)上執(zhí)行類似factor tree中的message passing膛檀，最終得到我們所感興趣的分布。
- 它并沒有解決fator tree中intractable的問題，在極端情況下仍然是指數(shù)的時間復(fù)雜度咖刃，在原圖為tree時泳炉，是線性的。
- 原本的圖有回路時嚎杨，JTA提供一種inference的方式胡桃，并且能夠得到正確的解，而factor tree不能磕潮。
- JT和factor graph同樣都是一種數(shù)據(jù)結(jié)構(gòu)翠胰，他們并不改變獨(dú)立性假設(shè)。只是作為inference的中間工具自脯。
什么是聯(lián)結(jié)樹：
通俗的說：原本的圖有環(huán)(如果是長度大于3的環(huán)需要映入chord)之景，那么我們可以將幾個相鄰的節(jié)點(diǎn)合并為一個大的節(jié)點(diǎn)，可以消除原本存在的環(huán)膏潮。把所有原本存在的環(huán)路變?yōu)橐粋€個超級節(jié)點(diǎn)锻狗，圖就變成了樹，這就是junction tree 能夠hold主環(huán)路的原因
通過證明焕参，無論是貝葉斯網(wǎng)絡(luò)還是馬兒克夫網(wǎng)絡(luò)的聯(lián)合概率都能夠表示成:
absorption：clique graph 通過前向后向傳播（每條邊都有兩個方向）轻纪，修正后的potential對應(yīng)于clique的邊緣概率。
message-passing調(diào)度：一個clique可以向另一個相鄰clique發(fā)送信息叠纷，只有當(dāng)它接收了除了這個點(diǎn)之外所有相鄰clique的message時刻帚。
如果一個變量出現(xiàn)在一個環(huán)中的每條sep上時，我們可以隨便選擇一個sep涩嚣，將這個變量刪除（brml p105）崇众，如果這個sep變?yōu)榭眨瑒t可以刪除相應(yīng)的邊航厚，從而獲得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，自然不能滿足一致性）
構(gòu)建聯(lián)結(jié)樹的具體步驟（原圖是樹形的）：
- 如果是有向圖的話麻顶，需要先moralised赦抖，將有共同孩子的節(jié)點(diǎn)相連，無向圖不需要（背后的原因是：p(x|a,b) 是由三個節(jié)點(diǎn)共同決定的函數(shù)澈蚌，可以認(rèn)為三個點(diǎn)是一個超級節(jié)點(diǎn)摹芙。而對于無向圖來說不需要灼狰，因?yàn)?p(x,a,b) = \phi(x,a)\phi(x,b)$宛瞄，不需要將a，b相連。
- 構(gòu)造一個clique graph份汗，確定哪些變量組成cliques盈电，如果相鄰clique有交集，則加一個sep在兩個clique之間
- 對于一個原本就是樹形結(jié)構(gòu)的圖杯活，它的clique graph的最大支撐樹就是junction tree（最大指的是整棵樹的sep中bianliang）
- 每個clique的potential等于這個clique中的所有變量的條件概率相乘匆帚。而separator 的potential設(shè)為1
構(gòu)建聯(lián)結(jié)樹的具體步驟（原圖不是樹形的）：
當(dāng)原圖有環(huán)時，variable elimination 消除變量時旁钧，消除變量的相鄰變量需要連邊吸重，這會引入新的邊。
Triangulated Graph： 所有的長度大于3的環(huán)歪今，必須引入弦（chord）（對應(yīng)于variable elimination中新增加的邊）
但是引入chord的順序不同嚎幸，可能導(dǎo)致clique 的大小不同，而junction tree 的性能瓶頸在于clique的大小寄猩。（我們只能通過貪心來讓最大的clique盡量屑稻А）
Greedy variable elimination：
- 先消除不增加邊的節(jié)點(diǎn)
- 沒有上述的節(jié)點(diǎn)時，先消除鄰居數(shù)量最少（或是clique table size刑锲）的節(jié)點(diǎn)
直到所有節(jié)點(diǎn)都被消除掉
如果原圖已經(jīng)有chord替废，那么消除變量不需要引入新的邊。
通過這種variable elimination中新加的邊泊柬，就是JT的chord
完整的JTA步驟:
- Moralisation:鏈接有向圖的父母
- Triangulation ：保證所有長度大于4的環(huán)有chord
- Junction tree：從clique graph 中找到最大支撐樹
- Potential Assignment：將原來各個變量的條件概率乘入到所屬clique的potential中
- Message Propagation： 每條邊的兩個方向都需要做一次message passing
最終clique的potential就是邊緣概率椎镣。
只有原圖為樹形時，JTA才是線性的時間復(fù)雜度
當(dāng)所求的分布不在同一個clique中時兽赁，需要的計算復(fù)雜度為指數(shù)形式
