DBN條件下信度傳輸優化算法仿真研究

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

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

0 引言

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

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

1 信度傳輸算法與優化的信度傳輸算法

1.1 信度傳輸算法

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

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

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

1.2 樹的定義及遍歷

樹是一類重要的非線性數據結構[7]，是以分支關系定義的層次結構。

(1) 定義

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

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

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

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

(2) 特點

樹中至少有一個結點——根；

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

(3) 樹的遍歷

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

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

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

1.3 信度傳輸優化DBP算法

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

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

實驗環境

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

內存：1.79 GHz，0.99 GB

操作系統：Microsoft Windows XP

DBP算法軟件實現如下。

DBP算法可分為4個主要模塊予以實現，分別是創建矩陣、構建網絡、設置參數和過程推理，部分主要代碼如下所示。

(1) 創建矩陣

Void CreatMatrix

{ N=m;

dag=zeros(m，m);

dag(1，2)=x;

dag(2，3)=x;

}

(2) 構建網絡

Void BulidNetwork

{ discrete_nodes=1:N;

node_sizes=2*ones(1，N);

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

}

(3) 設置參數

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 貝葉斯網絡模型實例

圖1是一個具有38個節點的樹形結構，并建立動態貝葉斯網絡，時間片長度為3。

(1) 單一證據推理

證據節點ENode = 30；關注節點CNode = 8。

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

圖2 單一證據時，BP和DBP算法執行時間對比圖

(2) 組合證據推理

證據節點Enode1 = 31，Enode2=35；關注節點CNode = 14。

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

圖3 組合證據時，BP和DBP算法執行時間對比圖

(3) 結果分析

輸入單一證據，時間t= 1，節點30為“真”。經典BP算法的網絡推理拓撲圖，如圖4所示。

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

圖5 單一證據輸入，DBP算法推理網絡圖

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

可見無論是輸入單一證據還是組合證據，DBP算法都能生成一個規模小于原樹的新的樹狀網絡圖，在38個節點樹形結構圖的情況下，單一、組合證據下節點數為27、45個。

對經典的BP算法、BP改進算法和DBP算法的優缺點分析如下。

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

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

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

圖6 組合證據輸入，DBP算法推理網絡圖

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

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

3 總結

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