無公共邊的雙圈圖上置信傳播算法的收斂性和正確性*

靳藝香,楊衛(wèi)華

(太原理工大學 數(shù)學學院,山西 晉中 030600)

0 引言

置信傳播(Belief Propagation)算法是一種在因子圖上描述的消息傳遞算法,1982年由Pearl[1]提出后廣泛應用在數(shù)字通信、人工智能、計算機科學、運籌管理等領域.1988年Pearl[2]證明了置信傳播算法在樹上收斂且收斂到正確先驗概率.2000年Weiss[3]提出單圈上的置信傳播算法(置信更新算法)在單圈圖中收斂,且當變量為二元時糾正置信收斂到正確邊際.Cantwell和Newman[4]給出了置信傳播算法在一類特殊多全圖上的收斂性與正確性.但置信傳播算法在多圈圖上的傳播收斂性與正確性尚未建立有效方法,而其在多圈圖上的收斂性與正確性在通信的譯碼領域扮演著重要的理論角色[5].因此,本文研究置信傳播算法在無公共邊的雙圈圖(網(wǎng)絡)上的收斂性和正確性,并進行仿真分析.

1 置信傳播算法

1.1 置信傳播算法基礎

為了使用置信傳播算法,在馬爾可夫隨機場中定義了兩個概念: 消息和置信.設是節(jié)點X發(fā)送給節(jié)點Y 的消息.定義圖中邊的傳遞矩陣[2]為

1.2 單圈圖的置信傳播算法[3]

1.2.1 單圈

2000年Weiss給出了單圈上的置信傳播算法[3].考慮一個由N個未觀測節(jié)點和N個觀測節(jié)點組成的單圈(即一個圈),每個未觀測節(jié)點上有一個觀測節(jié)點(見圖1(a)).我們用U1,···,UN表示單圈中的未觀測節(jié)點(白色圈),用O1,···,ON表示相應的觀測節(jié)點(黑色圈).Oi稱為Ui的局部證據(jù),定義對角矩陣Di的對角線元素為Oi傳遞給Ui的消息向量(i1,2,···,N),稱Di為局部證據(jù)概率矩陣.

由此可知,置信傳播算法在單圈收斂.

當消息向量為二元時,利用傳遞矩陣的特征值糾正置信.設傳遞矩陣CN1的主特征值為λ1,次特征值為λ2.則節(jié)點U1的糾正置信向量為

1.2.2 單圈和附加樹

將上部分內(nèi)容擴展到帶附加樹的單圈上[3](見圖1(b)).對于圈內(nèi)節(jié)點: 在有限次迭代后,非圈內(nèi)節(jié)點傳入圈中的消息收斂為穩(wěn)態(tài)值視為局部證據(jù),所以圈內(nèi)節(jié)點置信收斂且(二元時)糾正置信正確.對于非圈內(nèi)節(jié)點置信收斂,二元時糾正置信仍可能不正確.

本文使用Weiss[3,6－7]的術語,研究無公共邊的雙圈圖(分為無公共邊的雙圈和帶附加樹的無公共邊的雙圈)中置信傳播的收斂性和正確性.

2 無公共邊的雙圈的置信傳播算法

2.1 無公共邊的雙圈的分類

對帶有局部證據(jù)的無公共邊的雙圈按兩圈間的距離可分為3類: 相鄰的雙圈,兩圈距離為1的雙圈和兩圈距離大于1的雙圈.

相鄰的雙圈:兩圈有一個公共點,見圖2(a).

圖2 雙圈圖分類

兩圈距離為1的雙圈:兩圈距離為1,即雙圈是由兩圈距離為1的一條邊連接,見圖2(b).

兩圈距離大于1的雙圈:兩圈距離大于等于2,即雙圈之間可以有大于1個節(jié)點連接的雙圈,見圖2(c).

2.2 相鄰的雙圈置信傳播算法

考慮一個由N1+N2-1個未觀測節(jié)點和N1+N2-1個觀測節(jié)點組成的相鄰的雙圈(見圖2(a)).我們用A1,···,表示左圈中的未觀測節(jié)點,用OA1,···,表示相應的觀測節(jié)點;用B1,···,表示右圈中的未觀測節(jié)點,用OB1,···表示相應的觀測節(jié)點.兩圈由公共節(jié)點相連.見圖3(a).

圖3 相鄰的雙圈變?yōu)閮扇嚯x為1的雙圈

將相鄰的雙圈變?yōu)閮扇嚯x為1的雙圈的方法:

從而利用兩圈距離為1的雙圈的置信傳播算法規(guī)則解決相鄰的雙圈問題.

2.3 兩圈距離為1的雙圈置信傳播算法

考慮一個由N1+N2個未觀測節(jié)點和N1+N2個觀測節(jié)點組成的兩圈距離為1的雙圈(見圖3(b)).A1,···,表示左圈中的未觀測節(jié)點,B1,···,表示右圈中的未觀測節(jié)點.兩圈之間由間的一條邊相連.

2.3.1 初始消息設置

2.3.2 第n次迭代時的消息傳遞

1）右圈看作左圈的局部證據(jù)

由消息傳遞規(guī)則可知:

由此,將原來的雙圈網(wǎng)絡變?yōu)閱稳W(wǎng)絡.

2）左圈網(wǎng)絡的迭代收斂

現(xiàn)求左圈各節(jié)點置信

當左圈迭代到穩(wěn)態(tài)時該置信稱為穩(wěn)態(tài)置信.

3）穩(wěn)態(tài)的左圈看作右圈的局部證據(jù)

使得雙圈網(wǎng)絡變?yōu)閱稳W(wǎng)絡.

與左圈迭代相似,類比式(9)和式(10)有

4）穩(wěn)態(tài)的右圈看作左圈的局部證據(jù)

2.4 兩圈距離大于1的雙圈置信傳播算法

2.4.1 初始消息設置

2.4.2 第n次迭代時的消息傳遞

1）右圈看作左圈的局部證據(jù)

由此,將原來的雙圈變?yōu)閱稳?

2）左圈網(wǎng)絡的迭代收斂

兩圈距離大于1的雙圈圖中左圈的迭代收斂與2.3.2節(jié)中2)左圈網(wǎng)絡的迭代收斂相同,此處不再贅述.

3）穩(wěn)態(tài)的左圈看作右圈的局部證據(jù)

由此雙圈變?yōu)閱稳?右圈中各節(jié)點置信與式(18)相同.

4）穩(wěn)態(tài)的右圈看作左圈的局部證據(jù)

由式(21)和式(22)可知:

重復2.4.2節(jié)2)～4)部分的公式,直至各消息收斂.

3 無公共邊的二元雙圈的糾正置信傳播算法

利用Weiss[3]對二元單圈（單圈中各節(jié)點變量為二元）的糾正置信傳播算法,對無公共邊的二元雙圈（雙圈中各節(jié)點變量為二元）置信傳播算法中涉及單圈的部分進行糾正.

3.1 相鄰的二元雙圈糾正置信傳播算法

與2.2節(jié)相同,將相鄰的雙圈轉(zhuǎn)變?yōu)閮扇嚯x為1的雙圈,利用兩圈距離為1的雙圈的糾正置信傳播算法解決相鄰的雙圈問題.

3.2 兩圈距離為1的二元雙圈糾正置信傳播算法

設兩圈距離為1的雙圈中變量均為二元.兩圈距離為1的二元雙圈的糾正置信傳播算法僅對2.3.2節(jié)中以下部分進行改變,其余不變.

3.3 兩圈距離大于1的二元雙圈糾正置信傳播算法

兩圈距離大于1的雙圈的糾正置信傳播算法,在其置信傳播算法的基礎上作出以下改變:

1）在2.4.2節(jié)2)后加入式(27).

2）將式(23)改為

3）在2.4.2節(jié)3)后加入式(29).

4）將式(25)改為

4 無公共邊的雙圈的收斂性與正確性

4.1 無公共邊的雙圈的收斂條件

定理1若無公共邊的雙圈網(wǎng)絡中任一消息有(n為迭代次數(shù)),則其全局收斂.

證明置信傳播算法和糾正置信傳播算法僅對置信進行運算,不影響消息的收斂.因此本文僅對無公共邊的雙圈的置信傳播算法進行分析.

本文僅對兩圈距離為1的雙圈進行證明,相鄰或兩圈距離大于1的雙圈證明類似,不予贅述.

對于兩圈距離為1的雙圈:

4.2 雙圈的收斂性實驗

相鄰的雙圈實驗結果與兩圈距離為1的雙圈相同,僅展示兩圈距離為1的雙圈結果.

4.2.1 兩圈距離為1的雙圈

圖4(a)顯示了一個由8個未觀測節(jié)點和8個觀測節(jié)點組成的連接的雙圈圖網(wǎng)絡,圖4(b)顯示了各觀測節(jié)點處于狀態(tài)1或狀態(tài)2時的局部證據(jù)概率.設傳遞矩陣為:

圖4 兩圈距離為1的雙圈收斂實驗結果

圖4(c～d)顯示了節(jié)點1的置信收斂速度和糾正置信收斂速度,可以看到糾正置信收斂速度較快.

圖5(b)顯示了正確的邊際值(通過窮舉枚舉計算),由圖5(c～d)知置信配置與正確邊際配置不同;糾正置信配置與正確邊際配置相同,且糾正置信概率值均與正確邊際值相同(配置: 某節(jié)點概率最大的狀態(tài)).

圖5 兩圈距離為1的雙圈收斂實驗結果

用二階隨機矩陣定義圖5(a)中邊的過渡矩陣及各節(jié)點的局部證據(jù)概率矩陣.分別用置信傳播算法和糾正置信傳播算法對該圖進行仿真分析,各進行5 000次仿真實驗,由表1知兩圈距離為1的二元雙圈100%收斂.

表1 進行5 000次仿真，兩圈距離為1的雙圈的全局收斂率

4.2.2 兩圈距離大于1的雙圈

圖6(a)顯示了一個由9個未觀測節(jié)點和9個觀測節(jié)點組成的兩圈距離大于1的雙圈.設過渡矩陣不變,利用其置信傳播算法和糾正置信傳播算法對該圖進行仿真實驗.由實驗結果(圖7)可知,置信配置與正確邊際配置不同;糾正置信配置與正確邊際配置相同,且糾正置信概率值均與正確邊際值相同.

圖6 兩圈距離大于1的雙圈收斂實驗結果

圖7 兩圈距離大于1的雙圈實驗結果

利用兩種算法進行5 000次仿真實驗,仿真結果見表2,可知兩圈距離大于1的雙圈100%收斂,由此可以看出研究雙圈全局收斂是有意義的,且定理1是有意義的.

表2 進行5 000次仿真，兩圈距離大于1的雙圈的全局收斂率

4.3 無公共邊的雙圈的正確性實驗

利用無公共邊的雙圈的置信傳播算法和糾正置信傳播算法對各類二元雙圈進行5 000次仿真實驗(表3),觀察全局收斂時穩(wěn)態(tài)置信與正確邊際配置相同的次數(shù),并計算各自的正確率.由表3可知,對于無公共邊的二元雙圈,糾正置信傳播算法的正確率為100%,大于置信傳播算法.

表3 無公共邊的二元雙圈的正確性

5 帶附加樹的無公共邊雙圈的收斂性與正確性

將上節(jié)內(nèi)容擴展到無公共邊的雙圈和附加樹上,研究各類帶附加樹的無公共邊雙圈中置信傳播的收斂性和正確性.

5.1 相鄰的雙圈與附加樹分類

無附加樹的相鄰的雙圈圖見圖8(a),帶附加樹的相鄰的雙圈圖可分為兩類: 附加樹在圈上且不在兩圈公共點上(見圖8(b));附加樹在兩圈公共點上(見圖8(c)).

圖8 相鄰的雙圈與附加樹

5.2 兩圈距離為1的雙圈與附加樹分類

無附加樹的兩圈距離為1的雙圈圖見圖9(a),帶附加樹的兩圈距離為1的雙圈圖可分為兩類: 附加樹在圈上且不在兩圈連接線上(見圖9(b));附加樹在圈上且在兩圈連接線上(見圖9(c)).

圖9 兩圈距離為1的雙圈與附加樹

5.3 兩圈距離大于1的雙圈與附加樹分類

無附加樹的兩圈距離大于1的雙圈圖見圖10(a);帶附加樹的兩圈距離大于1的雙圈圖可分為三類: 附加樹在圈上且不在兩圈連接線上(見圖10(b));附加樹在圈上且在兩圈連接線上(見圖10(c));附加樹不在圈上且在兩圈連接線上(見圖10(d)).

圖10 兩圈距離大于1的雙圈與附加樹

5.4 實驗

對于相鄰的雙圈,若附加樹在非共同節(jié)點上,利用2.2節(jié)轉(zhuǎn)換為兩圈距離為1的雙圈進行實驗;若附加樹在兩圈共同節(jié)點上,將附加樹看作觀測節(jié)點,復制后實驗.由此相鄰的雙圈圖實驗包含于兩圈距離為1的雙圈圖實驗.

分別用置信傳播算法和糾正置信傳播算法對各類帶附加樹的無公共邊的二元雙圈進行5 000次仿真實驗,計算全局收斂率和正確率.結果見表4和表5.由表4和表5可知無論有沒有附加樹,無公共邊的二元雙圈均100%收斂,且糾正置信與正確邊際的配置相同.

表4 兩圈距離為1的二元雙圈與附加樹的收斂率和正確率

表5 兩圈距離大于1的二元雙圈與附加樹的收斂率和正確率

6 結論

1）無公共邊的雙圈圖全局收斂的條件: 無公共邊的雙圈圖中任一消息有(n為迭代次數(shù)),則該圖全局收斂.

2）置信傳播算法在無公共邊的雙圈圖(雙圈和帶有附加樹的雙圈)上均全局收斂,仿真實驗得出兩類圖收斂率均為100%.

3）仿真實驗得出:對于無公共邊的雙圈圖(雙圈和帶附加樹的雙圈),穩(wěn)態(tài)置信與正確邊際分布不同,配置可能相同;二元穩(wěn)態(tài)糾正置信與正確邊際分布完全相同.