DBN條件下信度傳輸優(yōu)化算法仿真研究

李曼, 楊俊清, 任靜, 石鋒, 張少應(yīng), 馬文勝

(西安航空學(xué)院 計(jì)算機(jī)學(xué)院， 陜西 西安 710077)

0 引言

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

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

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

1.1 信度傳輸算法

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

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

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

1.2 樹(shù)的定義及遍歷

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

(1) 定義

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

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

有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹(shù)的根 (root)；

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

(2) 特點(diǎn)

樹(shù)中至少有一個(gè)結(jié)點(diǎn)——根；

樹(shù)中各子樹(shù)是互不相交的集合。

(3) 樹(shù)的遍歷

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

① 先根遍歷樹(shù)，即先訪問(wèn)樹(shù)的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹(shù)；

② 后根遍歷樹(shù)，即先依次后根遍歷每棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)。

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

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

2 DBN條件下，DBP算法與BP算法實(shí)驗(yàn)研究

實(shí)驗(yàn)環(huán)境

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

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

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

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

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

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

Void CreatMatrix

{ N=m;

dag=zeros(m，m);

dag(1，2)=x;

dag(2，3)=x;

}

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

Void BulidNetwork

{ discrete_nodes=1:N;

node_sizes=2*ones(1，N);

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

}

(3) 設(shè)置參數(shù)

Void Settings

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

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

}

(4) 過(guò)程推理

Void ProcessReasoning

{ engine=pearl_inf_engine(bnet);

evidence=cell(1，N);

evidence{4}=1;

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

}

貝葉斯模型如下。

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

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

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

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

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

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

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

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

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

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

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

(3) 結(jié)果分析

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

而采用DBP算法，推理得到并使用的推理拓?fù)鋱D，如圖5所示。

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

組合證據(jù)與單一證據(jù)類(lèi)似，輸入組合證據(jù)時(shí)間為1，證據(jù)節(jié)點(diǎn)ENode 30、ENode34為“真”，經(jīng)典BP算法推理拓?fù)洳话l(fā)生改變。DBP算法更新后的推理網(wǎng)絡(luò)拓?fù)鋱D，如圖6所示。

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

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

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

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

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

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

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

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

3 總結(jié)

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