基于根節點優先搜索的信度傳輸DBP算法研究

李曼 楊俊清 任靜 石鋒 張少應

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

關鍵詞：信度傳輸算法;DBP算法;貝葉斯網絡;消息傳遞算法;證據推理

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

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

1 概述

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

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

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

2 信度傳輸算法和DBP算法

2.1 信度傳輸算法

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

貝葉斯網的結構體現了變量間的條件獨立性，即一個節點在其父節點的條件下與其他的祖先節點獨立。N個節點的貝葉斯網的節點聯合概率為：

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

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

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

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

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

2.2 基于根節點優先搜索的信度傳輸（DBP）算法

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

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

DBP算法的實現步驟如下：

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

給出一個貝葉斯網絡，其節點構成集合Ⅳ={nl，n2，n3，n4....n13），其推理步驟為：

Stepl：輸入證據節點ENode和關注節點CNode，其中ENode、CNode∈N。

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

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

Step4：輸出推理計算得到的關注節點的概率信息。

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

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

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

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

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

對于貝葉斯網絡路徑的搜索，DBP算法流程如圖3所示：

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

Stepl：輸入證據節點ENode，證據節點可能有多個;

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

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

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

Step5：跳轉到step3。

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

舉例：具有9個節點的樹形結構，如圖4所示：

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

4 結束語

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

參考文獻：

[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]項璟.廣義近似消息傳遞算法的研究與應用[D].燕山大學，2018：2-4.

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

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

[6]李梵若，李忠.基于模糊證據推理的醫療診斷專家系統的設計與實現[J].智能計算機與應用，2019，9（4）：13-15.