基于根節(jié)點優(yōu)先搜索的信度傳輸DBP算法研究

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

摘要：針對信度傳輸算法迭代次數(shù)較多的問題，提出一種基于根節(jié)點優(yōu)先搜索的信度傳輸DBP算法。DBP算法依據(jù)根節(jié)點優(yōu)先搜索的原理，選擇一種特定的節(jié)點順序進行信度傳播，直接到達信息傳播的不動點，降低迭代次數(shù)，節(jié)省推理時間。首先，分析了BP算法的主要思想、工作原理及推理過程，其次，提出了DBP算法，建立了貝葉斯網(wǎng)絡(luò)模型，給出了該算法的基本原理，最后，給出了DBP算法流程，并通過典型的樹形結(jié)構(gòu)的貝葉斯網(wǎng)絡(luò)實例，對DBP算法進行了分析，結(jié)果表明DBP算法在推理時間上優(yōu)于BP算法，算法的時間優(yōu)化率更高，從而驗證了DBP算法的有效性。

關(guān)鍵詞：信度傳輸算法;DBP算法;貝葉斯網(wǎng)絡(luò);消息傳遞算法;證據(jù)推理

中圖分類號：TP3文獻標識碼：A

文章編號：1009-3044（2020）03-0249-03

1 概述

Pearl.J等在20世紀80年代提出了信度傳輸（Belief Propaga-tion，BP）算法[1]，最初是采用樹形結(jié)構(gòu)明確表述的，后來擴展到多樹結(jié)構(gòu)。BP算法在無環(huán)的圖模型中可得到精確的邊緣概率或者后驗概率，但在有環(huán)的圖模型中只能得到近似的結(jié)果，甚至不收斂。

在有環(huán)的圖模型中使用BP算法，信息將在環(huán)中循環(huán)傳播，信息很可能在重復(fù)的路徑中傳播，一方面使得傳播過程變得冗余，另一方面，也可能使得信息來回振蕩而不收斂。目前解決此類問題的代表方法[2]有基于樹的再參數(shù)方法、基于樹的序列再加權(quán)方法等，相比于經(jīng)典的BP算法，這些算法盡管提高了收斂性，但迭代次數(shù)仍然很多。

針對信息傳輸算法迭代次數(shù)較多的問題，提出了一種基于根節(jié)點優(yōu)先搜索的信度傳輸算法，用于提高算法優(yōu)化率，減少算法執(zhí)行時間。首先闡述了信度傳輸（BP）算法的推理過程，其次提出了一種基于根節(jié)點優(yōu)先搜索的信度傳輸（DBP）算法，給出DBP的算法流程，并予以實驗研究。

2 信度傳輸算法和DBP算法

2.1 信度傳輸算法

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

貝葉斯網(wǎng)的結(jié)構(gòu)體現(xiàn)了變量間的條件獨立性，即一個節(jié)點在其父節(jié)點的條件下與其他的祖先節(jié)點獨立。N個節(jié)點的貝葉斯網(wǎng)的節(jié)點聯(lián)合概率為：

由于貝葉斯網(wǎng)能如此緊湊地表達聯(lián)合概率，可以有效地進行概率推理，包括計算邊緣概率和后驗概率，通常是使用BP算法，其主要思想是每個節(jié)點利用鄰節(jié)點傳來的信度和自己的條件概率更新自身的信度，再將結(jié)果再傳遞給鄰節(jié)點;在整個更新過程中，需要對所有節(jié)點進行迭代，存在迭代次數(shù)較多甚至不收斂等問題，通?？梢宰鳛橐环N近似的推理算法。

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

該算法的工作原理是在節(jié)點之間的邊上傳遞一種稱為消息[6]的真值函數(shù)，包含了一個節(jié)點變量施加于另一個節(jié)點變量的影響。

BP算法成立的一個重要假設(shè)就是在某個節(jié)點的條件下，其父節(jié)點和子節(jié)點是條件獨立的，這意味著該算法只有在樹狀結(jié)構(gòu)的圖中才能得到準確的結(jié)果。

在貝葉斯網(wǎng)絡(luò)的推理過程中，常常需對所有節(jié)點進行計算。但在一個大型網(wǎng)絡(luò)中，往往有部分節(jié)點的關(guān)注度較少，甚至不被關(guān)注，如果每次給定證據(jù)節(jié)點后，都對其進行計算，務(wù)必延長每一次推理的計算時間。

2.2 基于根節(jié)點優(yōu)先搜索的信度傳輸（DBP）算法

相對于經(jīng)典BP算法，提出了基于根節(jié)點優(yōu)先搜索的信度傳輸算法（Belief Propagation Algorithm Based on Deepness FirstSearch of root node），簡寫為DBP算法。

DBP算法的基本原理是：對于一個樹形結(jié)構(gòu)的貝葉斯網(wǎng)絡(luò)，當證據(jù)節(jié)點依次給出時，每獲得一個證據(jù)信息，并不急于對全網(wǎng)絡(luò)進行推理，同時給出所關(guān)注的節(jié)點信息，按照基于根節(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é)省推理時間。

DBP算法的實現(xiàn)步驟如下：

第一階段：首次獲得證據(jù)信息后，DBP算法第一階段推理過程如圖1所示：

給出一個貝葉斯網(wǎng)絡(luò)，其節(jié)點構(gòu)成集合Ⅳ={nl，n2，n3，n4....n13），其推理步驟為：

Stepl：輸入證據(jù)節(jié)點ENode和關(guān)注節(jié)點CNode，其中ENode、CNode∈N。

Step2：搜尋ENode到CNode的一條推理路徑，記錄路徑上各節(jié)點的順序。

Step3：根據(jù)路徑上各節(jié)點順序，采用信度傳輸算法對各節(jié)點進行BP推理。

Step4：輸出推理計算得到的關(guān)注節(jié)點的概率信息。

第二階段：當再次獲得證據(jù)信息后，第一階段的推理過程不再適用，DBP算法第二階段推理過程如圖2所示： 相比第一階段證據(jù)推理過程，第二階段推理增加了一個更新路徑上概率信息的模塊，如圖3所示。在首次給出證據(jù)節(jié)點和關(guān)注節(jié)點后，搜索到證據(jù)節(jié)點到關(guān)注節(jié)點的一條路徑，并且進行了推理運算，當再次給出證據(jù)節(jié)點和關(guān)注節(jié)點后，搜索到新的路徑和原路徑相比有以下幾種情況：

（1）新路徑和原路徑一致，路徑上的概率信息已經(jīng)得到更新，只需直接進行推理計算即可;

（2）新路徑上節(jié)點有部分在原路徑上，則只需更新不在原路徑上的節(jié)點即可;

（3）新路徑完全不和原路徑重合，則需要對新路徑上的所有節(jié)點進行更新后再完成本次BP推理。

3 基于DBP算法流程和實例分析

對于貝葉斯網(wǎng)絡(luò)路徑的搜索，DBP算法流程如圖3所示：

在路徑搜索之前，首先給貝葉斯網(wǎng)絡(luò)編號。要搜尋一條從證據(jù)節(jié)點到關(guān)注節(jié)點的路徑.為了簡化搜索過程，分別搜索證據(jù)節(jié)點和關(guān)注節(jié)點到根節(jié)點的路徑，將這兩條路徑合并得到所要尋找的路徑，具體算法步驟為：

Stepl：輸入證據(jù)節(jié)點ENode，證據(jù)節(jié)點可能有多個;

Step2：依次搜尋從節(jié)點1到證據(jù)節(jié)點的若干節(jié)點是否與證據(jù)節(jié)點有連接，由于樹形結(jié)構(gòu)的特殊性，一定能從這些節(jié)點中尋找出證據(jù)節(jié)點的下一個路徑，記為R1，得到路徑[ENode，R1];

Step3：判斷搜索到的新路徑節(jié)點是否為根節(jié)點l，如果是節(jié)點1，則停止搜索，如果不是，則繼續(xù)搜索;

Step4：繼續(xù)搜尋從節(jié)點1到R1的若干節(jié)點是否與R1相連，從而搜索到R1的下一個路徑，記為R2，得到路徑[ENode，R1，R2];

Step5：跳轉(zhuǎn)到step3。

通過給出的流程，可分別獲得證據(jù)節(jié)點到根節(jié)點的路徑[ENode，R1，R2，…，1]以及關(guān)注節(jié)點到根節(jié)點的路徑[CNode，Q1，Q2，…，1]，將兩個路徑進行合并即可得到所要搜尋的路徑[ENode， R1， R2.…，1，…，Q2， Q1， CNode].

舉例：具有9個節(jié)點的樹形結(jié)構(gòu)，如圖4所示：

方法：首先，輸人證據(jù)節(jié)點ENode或關(guān)注節(jié)點CNode。其中ENode=n5，CNode=n4，如圖5（b）所示。其次，從證據(jù)節(jié)點遍歷搜尋到根節(jié)點的路徑，路徑順序為：n5→n2→n1，以相同的方法從關(guān)注節(jié)點遍歷搜尋到根節(jié)點的路徑，路徑順序為：n4→n1，從而我們得到了從證據(jù)節(jié)點到關(guān)注節(jié)點的路徑順序為：n5→n2→n1→n2。如圖5（c）所示，根據(jù)得到的路徑順序，便可以對其進行貝葉斯推理了。

4 結(jié)束語

首先闡述了信度傳輸（BP）算法的基本內(nèi)容，分析了BP算法的主要思想、工作原理及推理過程;其次，提出了一種基于根節(jié)點優(yōu)先搜索的信度傳輸（DBP）算法，分析了該算法的基本原理，最后，給出了DBP算法流程，并進行實例分析。DBP算法在推理時間上優(yōu)于BP算法，節(jié)省更多的推理時間，提高算法優(yōu)化率和有效性。

參考文獻：

[1] Jin Boru， Liu Huayan. Comparative efficacy and safety of ther-apy for the behavioral and psychological symptoms of demen-tia：a systemic review and Bayesian network meta-analysis[J].Joumal of neurology， 2019， 2363-2375.

[2] Gu Yiming. Bayesian-based traffic state estimation in large-scale networks using big data[D].Pittsburgh： Carnegie Mel-lon University.2017.

[3]項璟.廣義近似消息傳遞算法的研究與應(yīng)用[D].燕山大學，2018：2-4.

[4]王亞萍，成衛(wèi)，李黎山.基于分層貝葉斯網(wǎng)絡(luò)的交通密度估測模型[J]交通科學與工程. 2019。35（3）：104-110.

[5]陳龍，馬亞平，基于分層貝葉斯網(wǎng)絡(luò)的航母編隊對潛威脅評估[J].系統(tǒng)仿真學報，2017，29（9）：2206-2212.

[6]李梵若，李忠.基于模糊證據(jù)推理的醫(yī)療診斷專家系統(tǒng)的設(shè)計與實現(xiàn)[J].智能計算機與應(yīng)用，2019，9（4）：13-15.