基于信息流改進的貝葉斯網絡結構學習算法

李 明, 張 韌, 洪 梅, 白成祖

(國防科技大學氣象海洋學院, 江蘇 南京 211101)

0 引 言

大數據環境下,分析和挖掘海量數據以獲取科學評價和決策信息,需要有效的知識表達和分析推理,其中以不確定知識的表達推理最為重要,而貝葉斯網絡是對不確定問題模擬和推理的有效工具。從數據樣本集中構建貝葉斯網絡,包括結構學習和參數學習,其中結構學習是基礎和核心。結構學習是指利用訓練數據集,盡可能結合先驗知識,構建與客觀數據最吻合的有向網絡拓撲結構,目前貝葉斯網絡的研究熱點之一就是如何從客觀數據中自動學習和優化網絡的拓撲結構。

貝葉斯網絡結構學習的關鍵在于如何確定網絡節點間的弧和弧方向,常用的結構學習算法可以分為基于統計檢測方法和基于搜索評分方法兩類。基于統計檢測方法關鍵是選取合適的測度函數進行節點間的依賴程度測試,尤其是條件獨立性測試,完成網絡結構學習。基于搜索評分方法通常作為最優化問題來處理,即在一個網絡結構空間中由評分函數引導搜索最優網絡結構。由于從大規模數據庫中進行結構學習是一個非確定性多項式(non-deterministic polynomial,NP)難題,所以對于節點較多情況時大都采用搜索評分方法:文獻[1]提出基于K2評分的爬山算法;文獻[2]提出基于最小描述長度(minimum description length,MDL)評分函數的K3算法;文獻[3-4]先后將模擬退火算法和貪婪搜索算法用于網絡結構的搜索學習;近些年,文獻[5-7]將遺傳算法、蟻群優化算法和粒子群算法用于結構學習。但搜索評分方法的效率通常較低,且易于陷入局部最優,為克服此方法計算和搜索的困難,許多學者進行了大量研究工作:文獻[8]結合經典的K2和馬爾可夫鏈蒙特卡羅(Markov chain Monte Carlo,MCMC)算法提出改進的結構學習思路;文獻[9]基于互信息和混沌映射來改進遺傳算法用于網絡結構學習;文獻[10]基于無約束優化和遺傳算法提出學習結構的限制型遺傳算法;文獻[11]基于卡方測試來改進貪婪搜索結構學習算法。上述改進算法優化了結構搜索空間,提高了搜索收斂速度,但仍然容易陷入局部最優解,最主要的缺陷是弧和弧方向的確定要分步進行,學習效率較低,并且弧方向的確定具有較大的不確定性。

貝葉斯網絡的結構學習實際上是因果分析的過程,信息流[12]是一種新興的因果分析方法,本文首次將信息流引入結構學習,基于信息流構造無約束0/1優化問題,提出一種結構學習的改進型搜索評分算法——改進型貪婪搜索(advanced greedy search,AGS)算法。該方法由2個階段組成:第1階段,基于信息流進行因果分析,對初始網絡進行全局性處理,構造0/1優化問題并求解,獲得初始網絡結構,為第2階段隨機搜索提供一個較優的結構空間;第2階段,在初始網絡結構基礎上進行加弧、減弧操作,進行結構弧的搜索學習,同時根據信息流確定弧方向,最終完成最優結構學習。由于在第2階段中,待搜索結構是以信息流全局優化的初始結構中的弧作為候選弧,并且弧和弧方向同步確定,不需進行傳統的轉弧操作,較傳統的搜索算法更能夠得到近似全局最優結構,提高了結構學習的準確性和時間效率。具體改進算法流程,如圖1所示。

圖1 貝葉斯網絡AGS算法流程Fig.1 AGS algorithm of Bayesian network

1 貝葉斯網絡

貝葉斯網絡,又稱貝葉斯信度網絡[13],是圖論與概率論的結合。貝葉斯網絡是變量間概率關系的圖形化描述,提供了一種將知識直觀的圖解可視化的方法；同時又是一種概率推理技術,使用概率理論來處理在描述不同變量之間因條件相關而產生的不確定性。貝葉斯網絡直觀地表示為一個復雜的賦值因果關系圖,完整的貝葉斯網絡是一個二元組B=〈G,θ〉,其中:

(1)G=(V(G),E(G)),是一個有向無環圖,V(G)是節點集合,節點表示所研究問題域中的變量(或事件);E(G)為弧集合,有向弧定性表示節點之間的概率依賴關系。

(2) 網絡參數θ構成的條件概率表表達了節點之間的因果依賴程度,體現了知識域定量方面的特征。

貝葉斯網絡的數學基礎是貝葉斯公式,基于先驗概率,根據相關條件可推導后驗概率;并且網絡蘊含了條件獨立性假設,如果給定根節點的先驗概率分布和非根節點的條件概率分布,則可以通過推理得到包含所有節點的聯合概率分布,即

(1)

式中,Vi為網絡節點;Pa(Vi)為節點Vi的父節點。

貝葉斯網絡的構建主要包括結構學習和參數學習,其中結構學習的目標是將給定數據中的因果依賴關系,用一個圖形化的模型表達出來,找到一個與樣本數據擬合程度最好的網絡拓撲結構。基于搜索評分的結構學習有兩個重要的組成部分:度量機制和搜索過程。度量機制即結構評分函數,是評價網絡好壞的一種標準,常用度量機制包括χ2度量、信息熵度量、貝葉斯度量以及MDL度量等,本文采用貝葉斯信息準則(Bayesian information criterion,BIC)評分函數;搜索過程用來搜索網絡空間,以找到一個度量值最高的網絡,即

best_G=argmax_score[f(Gi:D)],i=1,2…

(2)

式中,f(Gi:D)是依據數據集D而給出的網絡結構Gi的度量評分。本文采用貪婪搜索算法進行最優搜索。

n個節點構成的所有有向無環圖都可能作為貝葉斯網絡的搜索空間,Robinson給出了n個節點構成貝葉斯網絡的結構空間函數為

(3)

由式(3)可知,隨著網絡節點數的增加,網絡結構空間呈指數級增加,當n=10時,搜索空間結構個數達到約4.2×1018,搜索空間巨大,采用傳統的搜索算法,必然導致結構學習效率低下。鑒于從大規模數據庫中學習貝葉斯網絡結構是一個NP問題,本文首先基于信息流構建無約束0/1優化問題,對初始網絡進行全局處理,優化結構搜索空間;然后利用貪婪算法搜索結構弧,同時根據信息流確定弧方向,完成網絡結構學習。由于初始搜索空間性能較好,并且弧和弧方向同步確定,本文提出的AGS算法可以高效、準確地進行最優網絡結構學習。

2 基于信息流的AGS算法

貝葉斯網絡結構學習實際上就是確定節點之間的因果關系,在眾多關于因果關系描述中,確定因果關系一般基于如下3個條件:

(1) 變量之間具有密切聯系,具有較強的因果依賴關系;

(2) 變量之間具有不對稱性,由原因得到結果的可能性大于由結果得到原因的可能性;

(3) 不存在隱藏變量和數據偏差。

梁湘三提出的信息流[12]能夠較優地計算兩者之間的因果關系,因此可將其用于貝葉斯網絡的結構學習。本節首先介紹基于信息流理論的全局因果分析和無約束0/1優化問題的構造,然后提出改進型貪婪搜索算法。

2.1 信息流基本理論

信息流是梁湘三在轉移熵和Granger因果檢驗的基礎上,改進的以一種定量方式來表征變量(或事件)之間因果關系的物理量,通過一個變量序列到另一個變量序列的信息時間速率來衡量因果關系,并且這種因果關系是單向的。兩個變量之間的信息交換量不僅說明了因果關系的大小,而且指明了方向。通過信息流或信息傳遞來衡量變量之間的因果關系,能夠實現因果分析的公式化和定量化。

根據原始信息流形式,考慮一個維隨機系統,則

dX=F(X;θ)dt+B(X;θ)dW

(4)

式中,F為漂移系數向量;θ為參數;B=(bij)為擴散系數矩陣;W為標準的Wiener過程向量。如果系統是二維,則變量X2到X1的信息流為

(5)

式中,ρ1是X1的邊緣概率密度;E是數學期望。從X2到X1的信息流;等于X1的邊際熵變化率與系統排除X2后的邊際熵變化率之差。

梁湘三在此基礎上提出基于信息流的因果分析,推導了變量序列間因果分析的定量公式,對于X1和X2序列,從后者到前者的信息流(單位:單位時間的轉移量)為

(6)

為了能夠進行因果關系的強弱比較,本文采用標準化信息流公式[14],即

(7)

通過式(7)計算的標準化信息流τ2→1可以為零或非零。如果τ2→1=0,表示X2不會導致X1發生;如果τ2→1≠0,則兩者存在因果關系。此時,可以根據信息流的符號細分為兩種情況:τ2→1>0,表示X2導致X1趨向不確定,即X2是X1的原因;τ2→1<0,表示X2導致X1趨向穩定,即X2不能作為X1的原因。特別指出,在顯著性水平為0.1時,τ2→1>1%可判斷因果關系是顯著的。

經過上述分析可以看出,信息流非常適用于貝葉斯網絡的結構學習,信息流的大小反映了網絡中節點之間依賴關系的強弱,即結構弧的存在問題;信息流的正負則表征了結構弧的方向,基于信息流能夠實現網絡結構的整體化學習。

2.2 無約束0/1優化問題的構建

一個貝葉斯網絡可以進行矩陣編碼,采用鄰接矩陣X=(xij)的形式表示,n個節點的網絡可以表示為

定義1基于鄰接矩陣X=(xij)和信息流τij構造一個度量網絡全局因果程度的量,貝葉斯網絡全局因果度量為

全局因果度量C(X,α)取值越大,表明網絡的因果關系越顯著。在定義1的基礎上,可構造無約束0/1優化問題,即

(8)

基于信息流構建的網絡全局因果度量,通過上述0/1優化問題求解的最優鄰接矩陣,對應一有向拓撲結構,即初始網絡結構。根據信息流性質可知,網絡結構中所保留的有向弧是最優貝葉斯網絡結構的候選弧,基于初始網絡結構可生成因果關系最顯著的結構搜索空間。

2.3 BIC評分函數與貪婪搜索算法描述

接下來,基于搜索評分方法進行網絡結構學習,度量機制采用BIC評分函數,搜索機制采用貪婪搜索(greedy search,GS)算法。BIC評分函數將貝葉斯網絡的復雜度和匹配程度綜合考慮[15],函數表達式為

(9)

式中,Dim(G)表示貝葉斯網絡維度;G表示貝葉斯網絡結構;D表示數據集。

GS算法的基本思想是從一個隨機生成的網絡模型出發,對初始網絡進行加弧、減弧和轉弧操作然后進行評分。若評分增加則保留操作,該過程不斷迭代,直到網絡評分達到最優則停止。需要指出,本文的GS算法不再進行轉弧操作,弧的方向由信息流同步確定。GS算法具體流程描述如下。

GS搜索算法輸入 V為一組變量集,D關于V的完整數據集,初始貝葉斯網絡結構G0輸出 一個貝葉斯網絡結構G步驟 1 對初始網絡結構評分G0→oldscore;步驟 2 依次對初始網絡進行加弧、減弧操作并由信息流確定方向,結構評分G'→tempscore;if (tempscore>oldscore) newscore≡tempscore并保留相應弧操作;else newscore≡oldscore并舍棄相應弧操作;end if步驟 3 if newscore→maxreturn G≡G'

2.4 基于信息流的AGS算法描述

貝葉斯網絡結構學習包括弧和弧方向的確定,但結構學習中的搜索算法,如爬山算法、貪婪算法等,對于結構弧方向的確定具有較大不確定性;弧方向的準確判斷需要另外采用其他算法如條件相對平均熵、最大權重樹等,兩者只能分步進行,不能進行結構的高效學習。

通過求解上述基于信息流構建的0/1優化問題,獲得一個初始網絡結構,以此初始結構為基礎網絡生成結構搜索空間,即搜索空間中的結構弧只能在初始網絡的弧中隨機生成,而初始網絡結構的弧是基于信息流確定的,是最優貝葉斯網絡結構的候選弧,從而實現了對網絡搜索空間的優化處理;并且搜索算法不再進行轉弧操作,確定弧的同時由信息流判斷方向,即同步確定弧及弧方向。較原始的貪婪搜索方法更能獲得近似全局最優結構,簡化了搜索程序,提高了搜索精度。AGS算法具體流程描述如下。

AGS算法輸入 V為一組變量集和一組關于V的完整數據集D輸出 最優貝葉斯網絡G步驟 1 初始化: 設定0/1優化和信息流分析中的顯著性水平;步驟 2 信息流分析: 計算每一對節點(Vi,Vj)的信息流,并進行顯著性分析和因果分析;步驟 3 初始結構確定: 構造無約束0/1優化問題并求解,確定弧和弧方向,得到初始結構G0;步驟 4 GS算法搜索: 在G0的基礎上,用GS算法并結合信息流學習到最優貝葉斯網絡結構G。

3 仿真實驗

3.1 實驗環境與數據

本文采用經典的Asia網(8個節點,8條有向邊)和Alarm網(37個變量,46條有向邊)檢驗所提出算法的有效性。以Matlab為平臺,根據給出的結構和概率參數表,對上述網絡進行采樣,分別獲得800組和3 200組樣本數據,進行仿真實驗。實驗所需相應庫函數來自Murphy K P編寫的BNT工具箱。

由于搜索算法的隨機性,每個實驗均做10次求取平均值。為了表明結構學習的準確性,以正確弧(C)、丟失弧(L)、多余弧(E)和反向弧(R)的個數為評價指標,引入漢明距離[11]定量地評價學習到結構的優劣。

漢明距離=L+E+R

漢明距離越小,說明學習到的貝葉斯網絡結構越準確;當漢明距離為0時,說明學習到的結構為最優結構。

3.2 實驗結果與分析

首先,計算標準化信息流矩陣。以Asia網為例,不同樣本量的結果如表1、表2所示。

表1 800組樣本的信息流矩陣

表2 樣本量3 200組的信息流矩陣

需要指出:上述信息流矩陣中,信息流方向是由行變量指向列變量。舉例分析表中信息流含義,表1中如τSmoking→Bronchitis=0.010 6>0,τBronchitis→Smoking=-0.013 6<0,且兩者都大于1%,故可以判斷“Smoking”是“Bronchitis”的原因,即在貝葉斯網絡中可能存在弧“Smoking→Bronchitis”;再如τSmoking→Lunecancer=0.015 5>0,τLunecancer→Smoking=0.007 6>0,兩者雖然都大于0,但后者小于1%,因果關系不顯著,則可以判斷“Smoking”是“Lunecancer”的原因。表2中信息流矩陣與表1大體一致,表明采用信息流描述因果關系具有一定的穩定性,但隨著樣本量的增加,因果關系會更為顯著,如τSmoking→Bronchitis=0.018 3,τBronchitis→Smoking=-0.016 7,與表1相比,“Smoking”作為“Bronchitis”的原因更加顯著。

然后,基于信息流構造全局因果度量,求解無約束0/1優化問題,并結合信息流進行顯著性篩選和弧方向確定,獲得最優初始網絡結構。以Asia網為例,鄰接矩陣如圖2(a)所示,對應初始網絡結構如圖2(b)所示。

圖2 Asia網絡0/1優化求解結果Fig.2 0/1 optimization solution of Asia network

最后,以此初始網絡結構為基礎產生搜索空間,采用GS算法進行搜索學習。以Asia網為例,迭代收斂曲線如圖3所示,不同樣本量學習到的結構如圖4所示,在3 200組樣本時,本文算法學習到的網絡結構與標準Asia網一致。

圖3 Asia網絡的收斂曲線Fig.3 Convergence curve of Asia network

為了說明本文提出的AGS算法進行網絡結構學習的有效性,將其與傳統GS算法、爬山算法和文獻[10]提出的改進型遺傳算法(genetic algorithm,GA)學習網絡結構的精度和時間進行比較,將4種算法分別運行10次,取平均值作為實驗結果,Asia網和Alarm網的結果如表3、表4所示。

圖4 不同樣本量的Asia網絡學習結構Fig.4 Learning structure of Asia network at different sample sizes

樣本容量算法CLER漢明距離搜索時間/s800組本文AGS8.001.40.21.62.67改進GA7.80.70.91.63.23.59GS3.64.81.92.18.89.09爬山2.75.31.33.810.437.693 200組本文AGS8.000.100.15.61改進GA7.90.60.41.12.17.89GS5.22.71.21.95.820.91爬山4.53.11.22.97.2106.29

表4 Alarm網絡結構學習結果

從表3的實驗結果可得,對于節點較少的Asia網,在800、3 200組樣本時,本文提出的AGS算法均能學習到較優的結構,隨著樣本量的增加,學習的網絡結構更優。從表4的實驗結果可得,Alarm網在800組樣本時,所列4種算法的學習精度均較差,可見,對于37個節點的Alarm網,800組樣本相對于網絡復雜度而言樣本集規模太小,故數據與結構不能正確擬合。在3 200組樣本時,本文算法能夠學習到較優結構且在準確性和學習效率上較其他算法優勢明顯。

分析表3、表4可得,針對Asia網和Alarm網的結構學習,與傳統GS和爬山算法相比,本文提出的AGS算法在貝葉斯網絡結構學習的準確性和時間效率上都有顯著提升;與文獻[10]中的改進型GA算法相比,兩者在搜索時間上差別不大,但在結構準確性上AGS算法有一定優勢,尤其是在反向弧R一項中,反向弧個數顯著降低,即本文算法在弧方向確定上優勢明顯。以Alarm網為例,繪制4種算法學習迭代曲線，如圖5所示。

圖5 不同算法迭代收斂曲線Fig.5 Iterative convergence curves of different algorithms

由圖5可得,本文基于信息流的全局因果分析所構建的初始結構搜索空間,明顯優于其他3種算法,初始搜索空間的優化避免了隨機搜索算法對網絡進行過多的搜索,使得結構學習的精度和時間效率得到顯著提高,實驗結果驗證了AGS算法的有效性。

4 結 論

從大規模數據集中進行貝葉斯網絡自動建模,是貝葉斯網絡建模研究的難點之一。為有效進行貝葉斯網絡的結構學習,本文基于信息流的全局因果分析和0/1優化提出一種AGS算法。首先基于信息流引入全局因果度量,構造0/1優化問題,得到最優初始網絡結構;隨后以此結構為基礎產生結構搜索空間,通過貪婪算法搜索結構弧,同時根據信息流確定弧方向,實現結構的一體化學習,得到最優網絡結構。實驗表明,AGS算法與經典算法相比能夠更優近似全局最優結構,信息流的引入實現了弧和弧方向的同步確定,簡化了搜索程序,使得算法在準確性和時間性能上更高效。下一步研究的重點是信息流矩陣異常值的檢驗以及樣本量較小時如何獲得質量較高的結構。

參考文獻：

[1] COOPER G F, HERSKOVITS E. A Bayesian method for the induction of probabilistic networks from data[J]. Machine Learning, 1992, 9(4):309-347.

[2] BOUCKAERT R R. A stratified simulation scheme for inference in Bayesian belief networks[C]∥Proc.of the 10th International Conference on Uncertainty in Artificial Intelligence, 1994:110-117.

[3] CHICKERING D M, GEIGER D, HECKERMAN D. Learning Bayesian networks: search methods and experimental results[J]. General Information, 1995, 35(3):214-236.

[4] CHICKERING D M. Optimal structure identification with greedy search[J].Journal of Machine Learning Research,2003,3(3):507-554.

[5] LIU D Y, WANG F, LU Y N, et al. Research on learning Bayesian network structure based on genetic algorithms[J]. Chinese Journal of Electronics, 2001, 38(8):572-589.

[6] PINTO P C, NAGELE A, DEJORI M, et al. Using a local discovery ant algorithm for Bayesian network structure learning[J]. IEEE Trans.on Evolutionary Computation, 2009, 13(4):767-779.

[7] WANG T, YANG J. A heuristic method for learning Bayesian networks using discrete particle swarm optimization[J]. Knowledge and Information Systems, 2010, 24(2):269-281.

[8] 范敏, 黃席樾, 石為人,等. 一種改進的貝葉斯網絡結構學習算法[J]. 系統仿真學報, 2008, 20(17):4613-4617.

FAN M, HUNG X Y, SHI W R, et al. Improved Bayesian network structure learning algorithm[J]. Journal of System Simulation, 2008, 20 (17): 4613-4617.

[9] 劉寶寧, 章衛國, 李廣文,等. 一種改進遺傳算法的貝葉斯網絡結構學習[J]. 西北工業大學學報, 2013, 31(5):716-721.

LIU B N, ZHANG W G, LI G W, et al. A Bayesian network structure learning for improved genetic algorithm[J]. Journal of Northwestern Polytechnical University,2013,31(5):716-721.

[10] 汪春峰, 張永紅. 基于無約束優化和遺傳算法的貝葉斯網絡結構學習方法[J]. 控制與決策, 2013(4):618-622.

WANG C F, ZHANG Y H. Research on Bayesian network structure learning method based on unconstrained optimization and genetic algorithm[J].Control and Decision,2013(4):618-622.

[11] 劉向南. 因果貝葉斯網絡結構學習研究[D]. 合肥:合肥工業大學, 2012.

LIU X N. Study on Bayesian network structure learning[D]. Hefei: Journal of Hefei University of Technology, 2012.

[12] LIANG X S. Unraveling the cause-effect relation between time series[J]. Physical Review E Statistical， Nonlinear & Soft Matter Physics, 2014, 90(5/1):052150.

[13] 史志富. 貝葉斯網絡理論及其在軍事系統中的應用[M]. 北京:國防工業出版社, 2012.

SHI Z F. Bayesian network theory and its application in military system[M]. Beijing: Defense Industry Press, 2012.

[14] LIANG X S. Normalizing the causality between time series[J]. Physical Review E Statistical, Nonlinear & Soft Matter Physics, 2015, 92(2):022126.

[15] 邸若海, 高曉光. 基于限制型粒子群優化的貝葉斯網絡結構學習[J]. 系統工程與電子技術, 2011, 33(11):2423-2427.

DI R H, GAO X G. Bayesian Network structure learning based on restricted particle swarm optimization[J]. Systems Engineering and Electronics, 2011, 33 (11): 2423-2427.