大師兄的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)筆記（二十四）：貝葉斯網(wǎng)絡(luò)與概率推理（七）
大師兄的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)筆記（二十五）：貝葉斯網(wǎng)絡(luò)與概率推理（八）
四、消元順序
- 不同的消元順序可能會(huì)導(dǎo)致不同的計(jì)算復(fù)雜度。
- 總成本最低的消元順序成為最優(yōu)消元順序(optimal elimination order)。
- 很自然，我們希望能在推理之前預(yù)先知道最優(yōu)消元順序。
- 然而，尋找最優(yōu)消元順序是一個(gè)NP-難解問題。
- 實(shí)際中，人們使用啟發(fā)式規(guī)則來尋找較好、但卻不一定是最優(yōu)的消元順序。
- 兩個(gè)常用的啟發(fā)算法是：最大勢(shì)搜索(maximum cardinality search)和最小缺邊搜索(minimum deficiency search)。
1. 最大勢(shì)搜索
- 設(shè)G是一個(gè)包含n個(gè)節(jié)點(diǎn)的無(wú)向圖。
- 最大勢(shì)搜索對(duì)G中所有節(jié)點(diǎn)按如下規(guī)則從大到小進(jìn)行編號(hào)：
- 在第i步中，選擇擁有最多已編號(hào)相鄰節(jié)點(diǎn)的未編號(hào)節(jié)點(diǎn)，將其編號(hào)為
- 若這樣的節(jié)點(diǎn)有多個(gè)，則任選其一。
- 在所有的節(jié)點(diǎn)均被編號(hào)以后，按編號(hào)由小到大將節(jié)點(diǎn)排序，就得到一個(gè)變量消元順序。
- 上圖無(wú)向圖共有8個(gè)節(jié)點(diǎn)，用最大勢(shì)搜索將它們排序：
- 第1步任選一個(gè)節(jié)點(diǎn)，例如B，把它變?yōu)?號(hào)；
- 第2步可選的節(jié)點(diǎn)是S,D和R，因?yàn)橹挥兴鼈冇?個(gè)已編號(hào)相鄰節(jié)點(diǎn)，即B。從中任選一個(gè)，設(shè)其為S，把它編為7號(hào)。
- 第3步可選的節(jié)點(diǎn)包括D,R和L，它們的已編號(hào)相鄰節(jié)點(diǎn)的個(gè)數(shù)都是1.任選一個(gè)，設(shè)其為D，把它編為6號(hào)。
- 第4步只能選R，因?yàn)樗囊丫幪?hào)鄰居最多，有兩個(gè)，分別是B和D。把R編為5號(hào)。
- 接著，因?yàn)橥瑯拥睦碛桑?步只能選L，編為4號(hào)。
- 按照同樣的方法，剩余的節(jié)點(diǎn)T,X和A分別編為3,2和1號(hào)。
- 最后得到的消元順序?yàn)?lt;A,X,T,L,R,D,S,B>，可以用CostVE算法計(jì)算一下這個(gè)順序的消元成本。
2. 最小缺邊搜索
- 一個(gè)無(wú)向圖G中的某個(gè)節(jié)點(diǎn)Z的缺邊數(shù)(deficiency)是在用Elim(G,Z)消去Z時(shí)需要添加的邊的條數(shù)。
- 比如在上圖中，各節(jié)點(diǎn){A,T,L,R,S,B,D,X}的缺邊數(shù)分別為{0,2,2,8,1,2,0,0}。
- 最小缺邊搜索一邊為G中的節(jié)點(diǎn)排序，一邊把它們逐個(gè)從G中消去。
- 它在每一步都計(jì)算所有節(jié)點(diǎn)的缺邊數(shù)，選擇缺邊數(shù)最小的那個(gè)節(jié)點(diǎn)作為下一個(gè)消元節(jié)點(diǎn)，同時(shí)將其從圖G中消去。
- 當(dāng)有多個(gè)節(jié)點(diǎn)的缺邊數(shù)相等時(shí)，任選其一。
- 如此循環(huán)，直到所有節(jié)點(diǎn)都被消去。
- 上圖展示的事最小缺邊搜索在無(wú)向圖上的運(yùn)行情況，所獲得的序?yàn)?lt;A,X,D,T,S,L,B,R>。
- 經(jīng)驗(yàn)表明，最小缺邊搜索所給出的消元順序往往優(yōu)于其他方法所給出的順序。
