聯合樹

聯合樹是一種算法，將有向圖轉換為樹，從而減少計算的難度。

基本介紹

• 中文名：聯合樹
• 外文名：junction tree
• 方法：將有向圖轉換為樹
• 目的：減少計算的難度
• 步驟：4步
• 擴展：3/2片聯合樹算法

定義

貝葉斯網路由有向圖和條件機率分布函式構成。前者說明了各種條件之間的影響關係，後者說明了各種取值的機率。後者的表現形式有兩種，函式形式和表形式。

在貝葉斯網路確定之後，可以根據觀察到的數據來做一系列假設。這些假設會改變網路中的先驗數據，並逐步影響整個網路。

步驟

1、將有向圖轉換為無向圖。

將每個有共同子節點的父節點連線起來，把所有的有向邊改為無向邊

2、將無向圖三角化。

三角化問題，是指讓圖中不存在超過3個點的環。如果有，則需要增加邊來破除。理想的三角化問題是指，通過增加最少的邊來達到三角化的目的。然而這個問題是NPC的。三角化問題的解決比較簡單，指定一個節點順序，然後查看與這個節點相連的幾個節點，是否屬於三角區域。如果不屬於的話，那么他們之間是否存在邊。如果不存在則增加邊將他們連線即可。三角化的結果是否簡單，取決於查看節點的順序。

3、將三角化的圖轉換為樹。

每個三角都代表了一個節點。兩個相臨的三角具有共同的邊。這條邊就成為兩個節點之間的中間節點。如此就組成一張聯通圖。

4、尋找這張圖的根，並尋找最大生成樹，從而得到最終的結果。

對於每個evidence variable，把它放到包括這個變數的表里，然後把所有不滿足這個evidence的entry全設為0。接著做一個自底向上的疊代，對於每個葉子節點，給它的父節點傳送一個信息，即相關的表，父節點得到信息後就將其跟自己的表相乘，依次往上疊代，直到根節點。之後再做一個自頂向下的疊代，類似的，父節點向子節點傳送信息，子節點得到信息後將其與自己的表相乘，依次往下疊代，直到所有葉子節點收到信息。如果我們需要詢問一個變數對應的機率，我們就找到跟這個變數相關的完全子圖，把這些table加起來去除掉其它變數的干擾，然後就得到了答案。(這個陳述很可疑，因為想去掉別的變數根本不需要把所有變數都遍歷一遍。我們可以直接在表中合併其它變數對應的維度，就得到某個變數的機率了。

套用

3/2片聯合樹算法

基於動態貝葉斯網路處理動態不確定性問題的過程中推理是非常重要的，而推理算法的優劣決定著推理的執行效率。聯合樹可以作為貝葉斯網路的第二結構，是將貝葉斯網路中的變數按聯合樹特性進行改造的無向樹，對於動態貝葉斯網路還要將時間片間的連線點進行聯合，利用貝葉斯規則計算出用戶所關心的變數或變數集的機率分布。該方法需要不斷擴充時間片，對於較多的貝葉斯網路，尋找一個非常好的消去順序NP-hard問題。該文提出一種較簡單的3/2片聯合樹算法，在不需要限制消去順序且只作一次擴展的條件下構造聯合樹，所以算法簡單且具有較小的複雜度。

基於圖的鄰接點優先的聯合樹算法

貝葉斯網路是以機率理論為基礎的不確定知識表示模型,聯合樹算法是一種套用廣泛的貝葉斯網路推理算法。提出了基於鄰接點優先的聯合樹算法，從圖模型和計算效率兩個方面對聯合樹算法(JT)和基於圖的鄰接點優先的聯合樹(AD-JT)算法進行推理時間的比較，實驗表明：基於圖的鄰接點優先的聯合樹算法能夠有效地處理大規模數據，極大地減少了消耗時間，計算效率有顯著改進。

這裡提出的基於圖的鄰接點優先的聯合樹算法，就是基於這個思想，具體思路如下：

①需要關注的節點常常是少數幾個，每次輸入的證據往往也是為數不多的幾個節點，不妨稱它們為關鍵節點；

②可以在每一次輸入證據和觀察的時候確定關鍵節點，如果關鍵節點可以得到想要的結果，那么其它的節點就可以忽略掉；

③要找出推理出關鍵節點結果的必需的那些節點，不妨稱它們為重要節點，可以確定的是關鍵節點都是重要節點，與這些關鍵節點相連的上一個節點也是重要節點，以此類推，直到所有的重要節點都被找到為止；

④利用鄰接點優先算法，遍歷每一個關鍵節點外的點，找出來所有的重要節點；

⑤找出所有的重要節點， 用這些重要節點建立一個精簡過後的貝葉斯網路，這樣的推理勢必在空間和時間上有大量節約。