基于消息傳播的貝葉斯網絡推理算法及其應用

廖　娟　李德華

(華中科技大學自動化學院　武漢　430074)

?

基于消息傳播的貝葉斯網絡推理算法及其應用

廖娟李德華

(華中科技大學自動化學院武漢430074)

摘要近年來,我國的國際地位不斷提高,如何在錯綜復雜的國際戰略博弈中始終保持有利位置并爭奪戰略先機是當前國家面臨的重要國際問題。而貝葉斯網絡是以概率論為數學基礎的圖形模式,在不確定推理方面具有較強的優勢,因此常常被用于各種決策問題中。論文介紹了貝葉斯網絡的基本知識以及基于消息傳播的貝葉斯網絡推理算法,通過實例演示了基于消息傳播的貝葉斯推理算法在戰略決策問題上的應用。

關鍵詞貝葉斯網絡; 消息傳播; 推演算法; 戰略問題; 決策

A Bayesian Network Inference Algorithm Based on Message Propagation and its Application

LIAO JuanLI Dehua

(School of Automation, Huazhong University of Science & Technology, Wuhan430074)

AbstractIn recent years, China’s international status has improved. How to keep a favorable position in the perplexing international strategy game and get the strategic opportunities is an important international problem for China. Bayesian network is a graphics mode which is based on probability theory. It has a strong advantage in the uncertainty reasoning, so it is often used for various decision problems. The basic knowledge of Bayesian network inference algorithm is introduced based on message transmission. An example is given to demonstrate the application of Bayesian inference algorithm based on message transmission in the issue of strategic decision.

Key WordsBayesian network, message propagation, inference algorithm, strategic problem, decision

Class NumberTP301.6

1引言

2013年9月,國家主席習近平提出了“絲綢之路經濟帶”,引起了國內外廣泛的關注。“絲綢之路經濟帶”是中國應對當前復雜國內外環境的關鍵舉措。與亞歐國家共建“絲綢之路經濟帶”其戰略意義極廣[1]。同時,隨著中國成為世界第二大經濟體,中國對外援助規模也不斷擴大,由此給中國帶來的經濟、政治、外交以及國際聲譽是顯而易見的[2]。通過對外援助以及與他國共建“絲綢之路經濟帶”,可以幫助中國與相應的國家建立友好關系,從而為中國的產品及資本開辟更大的海外市場,提高中國的國際地位[3]。

貝葉斯網絡在不確定性的推理和決策問題中應用十分廣泛[4]。基于消息傳播的貝葉斯網絡推理算法通過給定的證據可以計算出所有節點的后驗概率。因此,本文通過用消息傳播算法來研究關于對外援助以及與他國共建絲綢之路的戰略決策問題。

2基于消息傳播的貝葉斯網絡推理算法

2.1貝葉斯網絡的理論基礎

一個貝葉斯網絡由代表變量的節點和連接這些節點的有向邊構成,節點表示隨機變量,而節點之間的弧表示變量間的聯系。每一個節點都對應著一個條件概率分布表,該分布表顯示了該節點與父節點之間的依賴關系[5]。

設實驗E的樣本空間為S,A為E的事件。B1,B2,…,Bn為E的一組事件,且滿足:B1,B2,…,Bn互不相容,B1∪B2∪…∪Bn=S,則有貝葉斯公式:

(1)

設隨機變量集合X={X1,X2,…,Xn},用xi表示Xi的取值,則變量Xi的取值為xi的概率為聯合概率,記為P(X1=x1,X2=x2,…,Xn=xn)。通常,聯合概率滿足一定的條件獨立性[6],則可以得到:

(2)

要構建一個貝葉斯網絡主要要確定兩方面的問題:網絡的結構關系和依賴關系。結構關系表達了網絡之中事件之間的因果聯系,主要依靠專家經驗、專業文獻和統計學習獲得。而依賴關系主要包括邊緣概率和條件概率,表達網絡中原因對結果的影響程度,主要來源于統計數據、專業文獻和專家經驗[7]。

貝葉斯網絡的推理實際上就是進行概率計算。貝葉斯網絡推理的基本思路就是:在給定貝葉斯網絡模型的情況下,根據已知的結構和證據,利用各種條件概率的計算方法來計算某一事件發生的后驗概率P(X|E)。貝葉斯網絡的推理主要有以下三種形式[8]:

1) 因果推理:原因推知結論,自頂向下的推理,在已知某些原因(也可稱之為證據)的情況下,推導出結果發生的概率。該推理往往被用于預測。

2) 診斷推理:結論推知原因,自底向上的推理,在已知結果的情況下,找出產生該結果的原因以及該原因發生的概率。通常將該推理形式應用于病理診斷、故障診斷等情況下。

3) 支持推理:對所發生的現象提供解釋。運用支持推理的目的一般是通過對不同原因之間的相互影響進行分析,得到多個影響元素之間的關聯度。

如圖1,在已知A、B的情況下,推導出C的概率為因果推理。在C已知的情況下,推導出A、B的概率為診斷推理。在A、C已知的情況下,推導出B的概率為支持推理。

2.2消息傳播算法

基于消息傳播的推理算法是J.Pearl根據條件獨立性在1988年提出的一種精確推理算法。基于消息傳播的推理算法根據證據結點集合E的各個節點的取值,可以求出貝葉斯網中任意結點Xi在取不同的xi,j值時,該節點的條件概率分布P(xi,j|e)。各個相鄰的節點之間通過傳遞λ消息和ρ消息來實現這個消息傳播的過程,如圖2所示,通過給定的證據可以計算出所有節點的后驗概率[9]。對于網絡中的任一節點,若己知該節點的取值狀態,則稱該節點為證據節點;否則稱之為非證據節點。

圖1　貝葉斯網絡的推理形式

圖2　消息傳播方式

對于每個非證據節點Xi:

1) 若Xi收到所有來自其父節點的數據,則由式(3)算出ρXi(xi)。

(3)

2) 若Xi收到所有來自其子節點的數據,則由式(4)算出λXi(xi)。

(4)

3) 若Xi算出λXi(xi),則對于它的每個子節點Yj,只要收到來自其異于Yj的所有子節點的λ信息時,就用式(5)算出ρXiYj(xi),并且將其作為ρ消息傳遞給它的子節點Yj:

ρXiYj(xi)=ρXi(xi)∏k≠jλYkXi(xi)

(5)

4) 若Xi算出λXi(xi),則對于它的每個父節點Uj,只要收到來自其異于Uj的所有父節點的ρ信息時,就用式(6)算出λXiUj(uj),并且將其作為λ消息傳遞給它的父節點Uj:

λYjXi(xi)=∑yjλYj(yj)∑v1,v2,…,vq

(6)

5) 當網絡中沒有消息傳播時,對于非證據節點Xi,根據式(7)算出βXi(xi),并且將得到的值進行歸一化處理,可得后驗概率分布P(xi|e)[10]。

βXi(xi)=λXi(xi)ρXi(xi)

(7)

3消息傳播算法在戰略問題上的應用

3.1戰略問題分析

2013年9月國家主席習近平提出了“絲綢之路經濟帶”,引起了國內外廣泛的反響。“絲綢之路經濟帶”是中國應對當前復雜國內外環境的關鍵舉措,是中國提出的規劃全球戰略部署的重要戰略。與亞歐國家共建“絲綢之路經濟帶”其戰略意義極廣。同時,隨著中國成為世界第二大經濟體,中國對外援助規模也不斷擴大,由此給中國帶來的經濟、政治、外交以及國際聲譽是顯而易見的。通過對外援助以及與他國共建“絲綢之路經濟帶”,可以幫助中國與相應的國家建立友好關系,從而為中國營造一個更加和諧的外部環境,為中國的產品及資本開辟廣大的海外市場,提高中國的國際地位,實現中華民族的偉大復興。由于關于國際戰略方面的信息很難通過大量的樣本數據來學習網絡結構和參數,因此本文主要根據相關文獻和專家知識來構建貝葉斯網絡模型,如圖3所示。這個貝葉斯網絡是關于中國對中亞某國(簡稱W國)進行對外援助,以及中國與該國共建絲綢之路合作而構造的,各節點代表的含義如下:

A:中國對W國進行援助

B:中國與W國合作共建絲綢之路

C:W國經濟發展

D:中國與W國關系友好

E:中國經濟發展

F:中國開辟更大的海外市場

G:中國國際地位提升

圖3　貝葉斯網絡模型

假設每個節點都只對應兩個狀態值,設為0和1,0代表該節點對應的事件沒有發生,1代表該節點對應的事件發生。比如:A=1代表中國對W國進行了援助,A=0代表中國沒有對W國進行援助。給出各個節點的條件概率表,如圖4所示。

圖4　條件概率矩陣

3.2消息傳播算法實例分析

下面用基于消息傳播的推理算法來分析上節中提到的戰略問題,圖3為其網絡結構,圖4是給出了所有節點的條件概率矩陣,證據集合為{D},其取值狀態為e={d=0}。即有:

輸入:貝葉斯網絡(圖3中的網絡結構和圖4中的條件概率矩陣)。證據節點集合E={D}的取值狀態e={d=0};

輸出:分別求出非證據節點A、B、C、E、F、G的條件概率分布P(A|e)、P(B|e)、P(C|e)、P(E|e)、P(F|e)、P(G|e);

步驟:

1) 初始化

(1)對證據節點D作如下設定:

ρD(0)=0.0,ρD(1)=1.0,λD(0)=0.0,λD(1)=1.0

(2)對于沒有父節點的非證據節點A、B和E,根據圖4中的概率表,作如下設定:

ρA(0)=0.3,ρB(0)=0.5,ρE(0)=0.1,

ρA(1)=0.7,ρB(1)=0.5,ρE(1)=0.9

(3)對于沒有子節點的非證據節點C、F和G,根據圖4中的概率表,作如下設定:

λC(0)=1.0,λF(0)=1.0,λG(0)=1.0,

λC(1)=1.0,λF(1)=1.0,λG(1)=1.0

(4)計算節點C、D、F、G的先驗概率

通過計算可得:

(ρC(0),ρC(1))=(0.325,0.675);

(ρD(0),ρD(1))=(0.2575,0.7425)。

(ρF(0),ρF(1))=(0.303,0.697);

(ρG(0),ρG(1))=(0.139,0.861)。

綜上,可以得各節點的先驗概率如圖5所示。

圖5　各節點的先驗概率

2) 消息傳播過程的計算

(1)第一輪計算

對于節點A:ρA(a)已經由初始化得到,但是由于網絡中還沒有消息傳播,所以不需要計算λ消息和ρ消息。

對于節點B:節點D是其唯一的子節點,根據式(5),節點B傳遞給其子節點D的ρ消息為:ρBD(b)=ρB(b)∏yjdλYjB(b)。

則有ρBD(b)=ρB(b),即(ρBD(0),ρBD(1))=(0.5,0.5)。

對于節點C:節點A是節點C的唯一的父節點,根據式(6)可以得到,節點C傳遞給其父節點A的λ消息為:λCA(a)=∑cλC(c)P(c|a)

由此可以得到:

λCA(0)=λC(0)P(C=0|A=0)

+λC(1)P(C=1|A=0)=1.0

λCA(1)=λC(0)P(C=0|A=1)

+λC(1)P(C=1|A=1)=1.0

即有(λCA(0),λCA(1))=(1.0,1.0)。

對于節點D:由于它是證據節點,還沒有收到任何來自其父節點或子節點的消息,此次無需計算。

對于節點E:節點G是節點E的唯一的子節點,參考對節點B的計算,可以得到:(ρEG(0),ρEG(1))=(0.1,0.9)。

對于節點F:節點D是節點F的唯一的父節點,參考對節點C的計算,可以得到:λFD(d)=∑fλF(f)P(f|d)。

代入數據可得:(λFD(0),λFD(1))=(1.0,1.0)。

對于節點G:它有兩個父節點D和E,由初始化已經得到了λG(g)。節點G收到了來自于其父節點E的ρ消息,可以使用式(6)算出節點G發送給它的另一個父節點D的λ消息,則有:λGD(d)=∑gλG(g)∑eP(g|d,e)ρEG(e)。

代入數據可得:(λGD(0),λGD(1))=(1.0,1.0)。

(2)第二輪計算

對于節點A:由初始化已經得到了ρA(a),A節點收到了來自其子節點C的λ消息,可以計算節點A傳送給其子節點D的ρ消息:ρAD(a)=ρA(a)λCA(a)。

即有(ρAD(a),ρAD(a))=(0.3,0.7)。

對于節點B:它還沒有收到來自其子節點D的任何消息,因此無需計算。

對于節點C:它還沒有收到來自其父節點A的任何消息,因此無需計算。

對于節點D:由初始化已經得到了ρD(d)和λD(d)。并且D節點已經收到了來自其父節點和子節點的消息:ρAD(a)、ρBD(b)、λGD(d)、λFD(d)。

由式(5)可得節點D傳送給其子節點F、G的消息為

ρDF(d)=ρD(d)λGD(d)和ρDG(d)=ρD(d)λFD(d)

代入數據可得:

(ρDF(0),ρDF(1))=(0.0,1.0)和(ρDG(0),ρDG(1))=(0.0,1.0)

由式(6)可得節點D傳送給其父節點A、B的消息為:

由于λD(0)=0.0,因此代入數據計算得:

即有:

(λDA(0),λDA()1)=(0.55,0.825)和(λDB(0),λDB(1))=(0.66,0.825)

對于節點E:它還沒有收到來自其父節點A的任何消息,因此無需計算。

對于節點F:它收到了來自其父節點D的消息ρDF(d),根據式(3)可以得到:ρF(f)=∑dP(f|d)ρDF(d)。

代入數據計算得:(ρF(0),ρF(1))=(0.2,0.8)。

對于節點G:它收到了來自其父節點D和E的消息:ρEG(d)和ρDG(d),根據式(3)可以得到:ρG(g)=∑d,eP(g|d,e)ρDG(d)ρEG(e)。

代入數據計算得:(ρG(0),ρG(1))=(0.085,0.915)。

由初始化已經得到了λG(g),由式(6)可得節點G傳送給其父節點E的λ消息為:λGE(e)=∑gλG(g)∑dP(g|d,e)ρDG(d)。

代入數據計算得(λGE(0),λGE(1))=(1.0,1.0)。

(3)第三輪計算

這一輪計算,只有節點A和節點C之間還有消息傳播。

對于節點A:它收到了來自其子節點D的消息:λDA(a)。由式(5)可得節點A傳送給其子節點C的消息為:ρAC(a)=ρA(a)λDA(a)。

代入數據計算得:(ρAC(0),ρAC(1))=(0.165,0.5775)。

對于節點C:它收到了來自其父節點A的消息:ρAC(a),根據式(3)可以得到:ρC(c)=∑aP(c|a)ρCA(a)。

代入數據計算得:(ρC(0),ρC(1))=(0.2269,0.5156)。

3) 歸一化

對于每個非證據節點Xi,算出βXi(xi)=λXi(xi)ρXi(xi),并將得到的值進行歸一化,得到后驗概率分布P(xi|e),如圖6所示。

圖6　各節點的后驗概率

3.3分析與仿真

利用Netica軟件進行仿真,可以得到該模型的先驗概率及后驗概率如圖7所示。若仿真所得數據與3.1節中計算所得數據一致。可以看到,若中國與W國關系友好,在這種情況下,中國開辟更大的海外市場的概率由0.697升為了0.8,中國國際地位提升的概率由0.861變為了0.915,而中國對W國進行援助的可能性由0.7變為了0.778,中國與W國合作絲綢之路的概率由0.5變為了0.556。這些得到的數據還是和實際較符合的,可以很好地給做決策提供幫助。運用同樣的方法,也可以得到將不同的節點定為證據時,得到的不同的后驗概率。

(a)先驗概率

(b)后驗概率圖7　Netica仿真結果

4結語

本文介紹了基于消息傳播的貝葉斯網絡傳播算法,建立了有關對外援助以及與他國共建“絲綢之路經濟帶”的模型,并參考相關文獻和專家知識確定了模型的拓撲結構,在專家的指導下選定了參數,最后用基于消息傳播的貝葉斯推算法對該模型進行了具體的案例分析,在Netica軟件上進行了仿真。計算與仿真的結果可以很好地給戰略問題的決策行動提供參考意見。

參 考 文 獻

[1] 胡鞍鋼,馬偉,鄢一龍.“絲綢之路經濟帶”:戰略內涵、定位和實現路徑[J].新疆師范大學學報,2014,35(2):1-10.

HU Angang, MA Wei, YAN Yilong. Connotation, Definition and Passage of “Silk-road Economic Belt” Strategy[J]. Journal of Xinjiang Normal University,2014,35(2):1-10.

[2] 王飛.復興絲綢之路與中國對外援助[J].黑龍江民族叢刊,2015,(2):48-53.

WANG Fei. The revival of Silk-road and China’s Foreign Aid[J]. Heilongjiang National Series,2015,(2):48-53.

[3] 白永秀,王頌吉.絲綢之路經濟帶的縱深背景與地緣戰略[J].改革,2014,12(3):64-73.

BAI Yongxiu, WANG Songji. Deep Background and Geopolitical Strategy of Silk-road Economic Belt[J]. Reform,2014,12(03):64-73.

[4] 王發智.基于貝葉斯網絡的交通突發事件態勢評估技術[D].大連:大連理工大學,2006:3-4.

WANG Fazhi. Methods Based on the Bayesian Networks of Traffic Accidental Event Situation Assessment[D]. Dalian: Dalian University of Technology,2006:3-4.

[5] 劉家鵬,詹原瑞,劉睿.基于貝葉斯網絡的操作風險建模[J].西安電子科技大學學報(社會科學版),2007,17(4):32-39.

LIU Jiapeng, ZHAN Yuanrui, LIU Rui. Model of Operational Risk of Bank Based on Bayesian Network[J]. Journal of Xidian University(Social Science Edition),2007,17(4):32-39.

[6] 劉俊娜.貝葉斯網絡推理算法研究[D].合肥:合肥工業大學,2007:10-14.

LIU Junna. Research on the Bayesian Networks Inference[D]. Hefei: Hefei University of Technology,2007:10-14.

[7] 胡笑旋.貝葉斯網建模技術及其在決策中的應用[D].合肥:合肥工業大學,2006:5-7.

HU Xiaoxuan. Bayesian Network Modeling Techniques and the Application in Decision-making[D]. Hefei: Hefei University of Technology,2006:5-7.

[8] 楊海深.貝葉斯網絡中不確定性知識推理算法及其應用研究[D].廣州:華南理工大學,2010:35-37.

YANG Haishen. Research on Uncertain Knowledge Inference and Its Applications in Bayesian Networks[D]. Guangzhou: South China University of Technology,2010:35-37.

[9] 董旭初.Bayesian網推理算法及基于Bayesian網的農業專家系統開發工具組件[D].吉林:吉林大學,2002:12-15.

DONG Xuchu. Inference Algorithms for Bayesian Networks and A Tool for Developing Agricultural Expert System Based on Bayesian Networks[D]. Jilin: Jilin University,2002:12-15.

[10] 汪榮貴.Bayes網絡理論及其在目標檢測中應用研究[D].合肥:合肥工業大學,2004:31-35.

WANG Ronggui. Research on the Theory of Bayesian Network and It’s Application in Object Detection[D]. Hefei: Hefei University of Technology,2004:31-35.

中圖分類號TP301.6

DOI:10.3969/j.issn.1672-9722.2016.01.004

作者簡介:廖娟,女,碩士研究生,研究方向:人工智能。李德華,男,教授,博士生導師,研究方向:人工智能、模式識別、思維科學。

收稿日期:2015年7月7日,修回日期:2015年8月24日