李曼, 楊俊清, 任靜, 石鋒, 張少應, 馬文勝

(西安航空學院 計算機學院， 陜西 西安 710077)

0 引言

Pearl.J等在20世紀80年代提出了信度傳輸(Belief Propagation, BP)算法[1]，最初是采用樹形結(jié)構(gòu)明確表述的，后來擴展到多樹結(jié)構(gòu)[2]。在有環(huán)的圖模型中使用BP算法，信息將在環(huán)中循環(huán)傳播，信息很可能在重復的路徑中傳播，一方面使得傳播過程變得冗余，另一方面，也可能使得信息來回振蕩而不收斂。

針對信息傳輸算法迭代次數(shù)較多的問題，提出了一種基于根節(jié)點優(yōu)先搜索的信度傳輸DBP算法，用于提高算法優(yōu)化率。首先，分析了BP算法的推理過程，其次，提出了優(yōu)化的信度傳輸算法，分析了樹的定義及樹的遍歷，給出了優(yōu)化的信度傳輸算法的基本原理和實現(xiàn)步驟，最后，在動態(tài)貝葉斯網(wǎng)絡DBN條件下，通過單一證據(jù)和組合證據(jù)推理，對優(yōu)化的DBP算法與BP算法進行實驗研究和仿真分析。

1 信度傳輸算法與優(yōu)化的信度傳輸算法

1.1 信度傳輸算法

信度傳輸BP算法是一種對貝葉斯網(wǎng)絡[3]等圖模型進行推理的消息傳遞算法，其本質(zhì)上是一個貝葉斯過程，采用有向圖的形式表達多個變量的聯(lián)合概率。有向圖中的節(jié)點表示變量,而邊表示變量間的概率依賴關(guān)系，即在給定任意觀察節(jié)點的條件下，計算每一個未觀察節(jié)點的邊緣分布[4]。

由于貝葉斯網(wǎng)絡[5]能如此緊湊地表達聯(lián)合概率，可以有效地進行概率推理，包括計算邊緣概率和后驗概率[6]，通常是使用BP算法。在貝葉斯網(wǎng)絡的推理過程中，常常需要對所有節(jié)點進行計算。但在一個大型網(wǎng)絡中，往往有部分節(jié)點的關(guān)注度較少，甚至不被關(guān)注，如果每次給定證據(jù)節(jié)點后，都對其進行計算，務必延長每一次推理的計算時間。

相對于經(jīng)典BP算法，提出一種信度傳輸優(yōu)化算法(Belief Propagation Optimization Algorithm)，即基于根節(jié)點優(yōu)先搜索的信度傳輸算法 (Belief Propagation Algorithm based on Deepness First Search of root node)，簡寫為DBP算法。下面先介紹樹的定義及遍歷。

1.2 樹的定義及遍歷

樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)[7]，是以分支關(guān)系定義的層次結(jié)構(gòu)。

(1) 定義

如果x是一個離散隨機變量序列，p為聯(lián)合集合函數(shù)，單個xi的邊緣分布為p在其它變量上的疊加和。

定義：樹(tree)是n(n0)個結(jié)點的有限集T，其中，n=0 為空樹；

有且僅有一個特定的結(jié)點，稱為樹的根 (root)；

當n>1時，其余結(jié)點可分為m(m>0)個互不相交的有限集。T1,T2,…,Tm，其中每一個集合本身又是一棵樹，稱為根的子樹(subtree)。

(2) 特點

樹中至少有一個結(jié)點——根；

樹中各子樹是互不相交的集合。

(3) 樹的遍歷

樹的遍歷[7]是指從樹中的某個結(jié)點出發(fā)，按照某種順序訪問樹中的每個頂點，使每個頂點被訪問一次且僅一次；遍歷可分為先根遍歷和后根遍歷兩種方式。

① 先根遍歷樹，即先訪問樹的根結(jié)點，然后依次先根遍歷根的每棵子樹；

② 后根遍歷樹，即先依次后根遍歷每棵子樹，然后訪問根結(jié)點。

1.3 信度傳輸優(yōu)化DBP算法

信度傳輸優(yōu)化DBP算法的基本原理是對于一個樹形結(jié)構(gòu)的貝葉斯網(wǎng)絡，當證據(jù)節(jié)點依次給出時，每獲得一個證據(jù)信息，按照基于根節(jié)點優(yōu)先搜索的方式，搜尋證據(jù)節(jié)點和關(guān)注節(jié)點之間的路徑，只對該路徑上的若干節(jié)點采用BP推理方法進行推理，而對其他節(jié)點的推理在本次計算中省略，只有在這些節(jié)點處于搜尋的路徑上時，對其概率信息進行更新。當同時給出若干證據(jù)時，搜尋出這些給出的證據(jù)到關(guān)注節(jié)點的相關(guān)路徑，這些相關(guān)路徑構(gòu)成了一個路徑網(wǎng)，只對該路徑網(wǎng)上的節(jié)點進行BP推理，省略掉其他不相關(guān)的節(jié)點，從而節(jié)省推理時間。

2 DBN條件下，DBP算法與BP算法實驗研究

實驗環(huán)境

處理器：Intel(R) Pentium(R) Dual

內(nèi)存：1.79 GHz，0.99 GB

操作系統(tǒng)：Microsoft Windows XP

DBP算法軟件實現(xiàn)如下。

DBP算法可分為4個主要模塊予以實現(xiàn)，分別是創(chuàng)建矩陣、構(gòu)建網(wǎng)絡、設置參數(shù)和過程推理，部分主要代碼如下所示。

(1) 創(chuàng)建矩陣

Void CreatMatrix

{ N=m;

dag=zeros(m，m);

dag(1，2)=x;

dag(2，3)=x;

}

(2) 構(gòu)建網(wǎng)絡

Void BulidNetwork

{ discrete_nodes=1:N;

node_sizes=2*ones(1，N);

bnet=mk_bnet(dag，node_sizes，'discrete'，discrete_nodes);

}

(3) 設置參數(shù)

Void Settings

{ bnet.CPD{1}=tabular_CPD(bnet，1，[x1 x2]);

bnet.CPD{2}=tabular_CPD(bnet，2，[x1 x2 x3]);

}

(4) 過程推理

Void ProcessReasoning

{ engine=pearl_inf_engine(bnet);

evidence=cell(1，N);

evidence{4}=1;

[engine，ll]=enter_evidence(engine，evidence);

}

貝葉斯模型如下。

采用的貝葉斯模型，如圖1所示。

圖1 貝葉斯網(wǎng)絡模型實例

圖1是一個具有38個節(jié)點的樹形結(jié)構(gòu)，并建立動態(tài)貝葉斯網(wǎng)絡，時間片長度為3。

(1) 單一證據(jù)推理

證據(jù)節(jié)點ENode = 30；關(guān)注節(jié)點CNode = 8。

推理進行一百次的執(zhí)行時間對比結(jié)果，如圖2所示(單位s)。

圖2 單一證據(jù)時，BP和DBP算法執(zhí)行時間對比圖

(2) 組合證據(jù)推理

證據(jù)節(jié)點Enode1 = 31，Enode2=35；關(guān)注節(jié)點CNode = 14。

推理進行一百次的執(zhí)行時間對比結(jié)果，如圖3所示(單位s)。

圖3 組合證據(jù)時，BP和DBP算法執(zhí)行時間對比圖

(3) 結(jié)果分析

輸入單一證據(jù)，時間t= 1，節(jié)點30為“真”。經(jīng)典BP算法的網(wǎng)絡推理拓撲圖，如圖4所示。

而采用DBP算法，推理得到并使用的推理拓撲圖，如圖5所示。

圖5 單一證據(jù)輸入，DBP算法推理網(wǎng)絡圖

組合證據(jù)與單一證據(jù)類似，輸入組合證據(jù)時間為1，證據(jù)節(jié)點ENode 30、ENode34為“真”，經(jīng)典BP算法推理拓撲不發(fā)生改變。DBP算法更新后的推理網(wǎng)絡拓撲圖，如圖6所示。

可見無論是輸入單一證據(jù)還是組合證據(jù)，DBP算法都能生成一個規(guī)模小于原樹的新的樹狀網(wǎng)絡圖，在38個節(jié)點樹形結(jié)構(gòu)圖的情況下，單一、組合證據(jù)下節(jié)點數(shù)為27、45個。

對經(jīng)典的BP算法、BP改進算法和DBP算法的優(yōu)缺點分析如下。

(1) 在有環(huán)的圖模型[8]中使用BP算法，信息將在環(huán)中循環(huán)傳播，信息很可能在重復的路徑中傳播，一方面使得傳播過程變得冗余，另一方面，也可能使得信息來回振蕩而不收斂；

(2) 基于樹的再參數(shù)方法、基于樹的序列再加權(quán)方法[9]等，相比于經(jīng)典的BP算法，這些算法盡管提高了收斂性，但迭代次數(shù)仍然很多；

(3) 還有降低推理復雜度的按良序的信度傳輸方法[10]

圖6 組合證據(jù)輸入，DBP算法推理網(wǎng)絡圖

以及關(guān)于Bethe自由能最小化的方法，不同的Bethe自由能最小化方法對應于不同的信息傳播策略；

(4) 針對信息傳輸算法迭代次數(shù)較多的問題，提出了優(yōu)化的信度傳輸算法，即基于根節(jié)點優(yōu)先搜索的信度傳輸DBP算法，用于提高算法優(yōu)化率，減少算法執(zhí)行時間。主要是因為隨著網(wǎng)絡趨于復雜，DBP算法推理得到新網(wǎng)絡相對于原來的網(wǎng)絡消除了更多的無關(guān)節(jié)點，而得到新網(wǎng)絡的算法本身并不隨著網(wǎng)絡節(jié)點數(shù)的增多而時間明顯增加，從而減少迭代次數(shù)、提高算法優(yōu)化率。

3 總結(jié)

首先闡述了信度傳輸(BP)算法的基本內(nèi)容，分析了BP算法的主要思想和推理過程；其次，提出了優(yōu)化的信度傳輸算法，分析了樹的定義及樹的先根遍歷，給出了優(yōu)化的信度傳輸算法的基本原理和實現(xiàn)步驟；最后，通過典型的樹形結(jié)構(gòu)的貝葉斯網(wǎng)絡實例，在DBN條件下，對DBP算法和BP算法進行了分析。DBP算法在推理時間上優(yōu)于BP算法，且優(yōu)化率隨關(guān)鍵節(jié)點的變化而浮動。實驗表明：DBP算法更適用于大型的網(wǎng)絡，原因在于大型網(wǎng)絡中節(jié)點更復雜，DBP算法可減少迭代次數(shù)，節(jié)省更多的推理時間，提高算法有效性。