基于信息流改進(jìn)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法

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

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

0 引 言

大數(shù)據(jù)環(huán)境下,分析和挖掘海量數(shù)據(jù)以獲取科學(xué)評價(jià)和決策信息,需要有效的知識表達(dá)和分析推理,其中以不確定知識的表達(dá)推理最為重要,而貝葉斯網(wǎng)絡(luò)是對不確定問題模擬和推理的有效工具。從數(shù)據(jù)樣本集中構(gòu)建貝葉斯網(wǎng)絡(luò),包括結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí),其中結(jié)構(gòu)學(xué)習(xí)是基礎(chǔ)和核心。結(jié)構(gòu)學(xué)習(xí)是指利用訓(xùn)練數(shù)據(jù)集,盡可能結(jié)合先驗(yàn)知識,構(gòu)建與客觀數(shù)據(jù)最吻合的有向網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),目前貝葉斯網(wǎng)絡(luò)的研究熱點(diǎn)之一就是如何從客觀數(shù)據(jù)中自動(dòng)學(xué)習(xí)和優(yōu)化網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。

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

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

圖1 貝葉斯網(wǎng)絡(luò)AGS算法流程Fig.1 AGS algorithm of Bayesian network

1 貝葉斯網(wǎng)絡(luò)

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

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

(2) 網(wǎng)絡(luò)參數(shù)θ構(gòu)成的條件概率表表達(dá)了節(jié)點(diǎn)之間的因果依賴程度,體現(xiàn)了知識域定量方面的特征。

貝葉斯網(wǎng)絡(luò)的數(shù)學(xué)基礎(chǔ)是貝葉斯公式,基于先驗(yàn)概率,根據(jù)相關(guān)條件可推導(dǎo)后驗(yàn)概率;并且網(wǎng)絡(luò)蘊(yùn)含了條件獨(dú)立性假設(shè),如果給定根節(jié)點(diǎn)的先驗(yàn)概率分布和非根節(jié)點(diǎn)的條件概率分布,則可以通過推理得到包含所有節(jié)點(diǎn)的聯(lián)合概率分布,即

(1)

式中,Vi為網(wǎng)絡(luò)節(jié)點(diǎn);Pa(Vi)為節(jié)點(diǎn)Vi的父節(jié)點(diǎn)。

貝葉斯網(wǎng)絡(luò)的構(gòu)建主要包括結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí),其中結(jié)構(gòu)學(xué)習(xí)的目標(biāo)是將給定數(shù)據(jù)中的因果依賴關(guān)系,用一個(gè)圖形化的模型表達(dá)出來,找到一個(gè)與樣本數(shù)據(jù)擬合程度最好的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。基于搜索評分的結(jié)構(gòu)學(xué)習(xí)有兩個(gè)重要的組成部分:度量機(jī)制和搜索過程。度量機(jī)制即結(jié)構(gòu)評分函數(shù),是評價(jià)網(wǎng)絡(luò)好壞的一種標(biāo)準(zhǔn),常用度量機(jī)制包括χ2度量、信息熵度量、貝葉斯度量以及MDL度量等,本文采用貝葉斯信息準(zhǔn)則(Bayesian information criterion,BIC)評分函數(shù);搜索過程用來搜索網(wǎng)絡(luò)空間,以找到一個(gè)度量值最高的網(wǎng)絡(luò),即

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

(2)

式中,f(Gi:D)是依據(jù)數(shù)據(jù)集D而給出的網(wǎng)絡(luò)結(jié)構(gòu)Gi的度量評分。本文采用貪婪搜索算法進(jìn)行最優(yōu)搜索。

n個(gè)節(jié)點(diǎn)構(gòu)成的所有有向無環(huán)圖都可能作為貝葉斯網(wǎng)絡(luò)的搜索空間,Robinson給出了n個(gè)節(jié)點(diǎn)構(gòu)成貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)空間函數(shù)為

(3)

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

2 基于信息流的AGS算法

貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)實(shí)際上就是確定節(jié)點(diǎn)之間的因果關(guān)系,在眾多關(guān)于因果關(guān)系描述中,確定因果關(guān)系一般基于如下3個(gè)條件:

(1) 變量之間具有密切聯(lián)系,具有較強(qiáng)的因果依賴關(guān)系;

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

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

梁湘三提出的信息流[12]能夠較優(yōu)地計(jì)算兩者之間的因果關(guān)系,因此可將其用于貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)。本節(jié)首先介紹基于信息流理論的全局因果分析和無約束0/1優(yōu)化問題的構(gòu)造,然后提出改進(jìn)型貪婪搜索算法。

2.1 信息流基本理論

信息流是梁湘三在轉(zhuǎn)移熵和Granger因果檢驗(yàn)的基礎(chǔ)上,改進(jìn)的以一種定量方式來表征變量(或事件)之間因果關(guān)系的物理量,通過一個(gè)變量序列到另一個(gè)變量序列的信息時(shí)間速率來衡量因果關(guān)系,并且這種因果關(guān)系是單向的。兩個(gè)變量之間的信息交換量不僅說明了因果關(guān)系的大小,而且指明了方向。通過信息流或信息傳遞來衡量變量之間的因果關(guān)系,能夠?qū)崿F(xiàn)因果分析的公式化和定量化。

根據(jù)原始信息流形式,考慮一個(gè)維隨機(jī)系統(tǒng),則

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

(4)

式中,F為漂移系數(shù)向量;θ為參數(shù);B=(bij)為擴(kuò)散系數(shù)矩陣;W為標(biāo)準(zhǔn)的Wiener過程向量。如果系統(tǒng)是二維,則變量X2到X1的信息流為

(5)

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

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

(6)

為了能夠進(jìn)行因果關(guān)系的強(qiáng)弱比較,本文采用標(biāo)準(zhǔn)化信息流公式[14],即

(7)

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

經(jīng)過上述分析可以看出,信息流非常適用于貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí),信息流的大小反映了網(wǎng)絡(luò)中節(jié)點(diǎn)之間依賴關(guān)系的強(qiáng)弱,即結(jié)構(gòu)弧的存在問題;信息流的正負(fù)則表征了結(jié)構(gòu)弧的方向,基于信息流能夠?qū)崿F(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)的整體化學(xué)習(xí)。

2.2 無約束0/1優(yōu)化問題的構(gòu)建

一個(gè)貝葉斯網(wǎng)絡(luò)可以進(jìn)行矩陣編碼,采用鄰接矩陣X=(xij)的形式表示,n個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)可以表示為

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

全局因果度量C(X,α)取值越大,表明網(wǎng)絡(luò)的因果關(guān)系越顯著。在定義1的基礎(chǔ)上,可構(gòu)造無約束0/1優(yōu)化問題,即

(8)

基于信息流構(gòu)建的網(wǎng)絡(luò)全局因果度量,通過上述0/1優(yōu)化問題求解的最優(yōu)鄰接矩陣,對應(yīng)一有向拓?fù)浣Y(jié)構(gòu),即初始網(wǎng)絡(luò)結(jié)構(gòu)。根據(jù)信息流性質(zhì)可知,網(wǎng)絡(luò)結(jié)構(gòu)中所保留的有向弧是最優(yōu)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的候選弧,基于初始網(wǎng)絡(luò)結(jié)構(gòu)可生成因果關(guān)系最顯著的結(jié)構(gòu)搜索空間。

2.3 BIC評分函數(shù)與貪婪搜索算法描述

接下來,基于搜索評分方法進(jìn)行網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí),度量機(jī)制采用BIC評分函數(shù),搜索機(jī)制采用貪婪搜索(greedy search,GS)算法。BIC評分函數(shù)將貝葉斯網(wǎng)絡(luò)的復(fù)雜度和匹配程度綜合考慮[15],函數(shù)表達(dá)式為

(9)

式中,Dim(G)表示貝葉斯網(wǎng)絡(luò)維度;G表示貝葉斯網(wǎng)絡(luò)結(jié)構(gòu);D表示數(shù)據(jù)集。

GS算法的基本思想是從一個(gè)隨機(jī)生成的網(wǎng)絡(luò)模型出發(fā),對初始網(wǎng)絡(luò)進(jìn)行加弧、減弧和轉(zhuǎn)弧操作然后進(jìn)行評分。若評分增加則保留操作,該過程不斷迭代,直到網(wǎng)絡(luò)評分達(dá)到最優(yōu)則停止。需要指出,本文的GS算法不再進(jìn)行轉(zhuǎn)弧操作,弧的方向由信息流同步確定。GS算法具體流程描述如下。

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

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

貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)包括弧和弧方向的確定,但結(jié)構(gòu)學(xué)習(xí)中的搜索算法,如爬山算法、貪婪算法等,對于結(jié)構(gòu)弧方向的確定具有較大不確定性;弧方向的準(zhǔn)確判斷需要另外采用其他算法如條件相對平均熵、最大權(quán)重樹等,兩者只能分步進(jìn)行,不能進(jìn)行結(jié)構(gòu)的高效學(xué)習(xí)。

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

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

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)

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

由于搜索算法的隨機(jī)性,每個(gè)實(shí)驗(yàn)均做10次求取平均值。為了表明結(jié)構(gòu)學(xué)習(xí)的準(zhǔn)確性,以正確弧(C)、丟失弧(L)、多余弧(E)和反向弧(R)的個(gè)數(shù)為評價(jià)指標(biāo),引入漢明距離[11]定量地評價(jià)學(xué)習(xí)到結(jié)構(gòu)的優(yōu)劣。

漢明距離=L+E+R

漢明距離越小,說明學(xué)習(xí)到的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)越準(zhǔn)確;當(dāng)漢明距離為0時(shí),說明學(xué)習(xí)到的結(jié)構(gòu)為最優(yōu)結(jié)構(gòu)。

3.2 實(shí)驗(yàn)結(jié)果與分析

首先,計(jì)算標(biāo)準(zhǔn)化信息流矩陣。以Asia網(wǎng)為例,不同樣本量的結(jié)果如表1、表2所示。

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

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

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

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

圖2 Asia網(wǎng)絡(luò)0/1優(yōu)化求解結(jié)果Fig.2 0/1 optimization solution of Asia network

最后,以此初始網(wǎng)絡(luò)結(jié)構(gòu)為基礎(chǔ)產(chǎn)生搜索空間,采用GS算法進(jìn)行搜索學(xué)習(xí)。以Asia網(wǎng)為例,迭代收斂曲線如圖3所示,不同樣本量學(xué)習(xí)到的結(jié)構(gòu)如圖4所示,在3 200組樣本時(shí),本文算法學(xué)習(xí)到的網(wǎng)絡(luò)結(jié)構(gòu)與標(biāo)準(zhǔn)Asia網(wǎng)一致。

圖3 Asia網(wǎng)絡(luò)的收斂曲線Fig.3 Convergence curve of Asia network

為了說明本文提出的AGS算法進(jìn)行網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的有效性,將其與傳統(tǒng)GS算法、爬山算法和文獻(xiàn)[10]提出的改進(jìn)型遺傳算法(genetic algorithm,GA)學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)的精度和時(shí)間進(jìn)行比較,將4種算法分別運(yùn)行10次,取平均值作為實(shí)驗(yàn)結(jié)果,Asia網(wǎng)和Alarm網(wǎng)的結(jié)果如表3、表4所示。

圖4 不同樣本量的Asia網(wǎng)絡(luò)學(xué)習(xí)結(jié)構(gòu)Fig.4 Learning structure of Asia network at different sample sizes

樣本容量算法CLER漢明距離搜索時(shí)間/s800組本文AGS8.001.40.21.62.67改進(jìn)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改進(jìn)GA7.90.60.41.12.17.89GS5.22.71.21.95.820.91爬山4.53.11.22.97.2106.29

表4 Alarm網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)結(jié)果

從表3的實(shí)驗(yàn)結(jié)果可得,對于節(jié)點(diǎn)較少的Asia網(wǎng),在800、3 200組樣本時(shí),本文提出的AGS算法均能學(xué)習(xí)到較優(yōu)的結(jié)構(gòu),隨著樣本量的增加,學(xué)習(xí)的網(wǎng)絡(luò)結(jié)構(gòu)更優(yōu)。從表4的實(shí)驗(yàn)結(jié)果可得,Alarm網(wǎng)在800組樣本時(shí),所列4種算法的學(xué)習(xí)精度均較差,可見,對于37個(gè)節(jié)點(diǎn)的Alarm網(wǎng),800組樣本相對于網(wǎng)絡(luò)復(fù)雜度而言樣本集規(guī)模太小,故數(shù)據(jù)與結(jié)構(gòu)不能正確擬合。在3 200組樣本時(shí),本文算法能夠?qū)W習(xí)到較優(yōu)結(jié)構(gòu)且在準(zhǔn)確性和學(xué)習(xí)效率上較其他算法優(yōu)勢明顯。

分析表3、表4可得,針對Asia網(wǎng)和Alarm網(wǎng)的結(jié)構(gòu)學(xué)習(xí),與傳統(tǒng)GS和爬山算法相比,本文提出的AGS算法在貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的準(zhǔn)確性和時(shí)間效率上都有顯著提升;與文獻(xiàn)[10]中的改進(jìn)型GA算法相比,兩者在搜索時(shí)間上差別不大,但在結(jié)構(gòu)準(zhǔn)確性上AGS算法有一定優(yōu)勢,尤其是在反向弧R一項(xiàng)中,反向弧個(gè)數(shù)顯著降低,即本文算法在弧方向確定上優(yōu)勢明顯。以Alarm網(wǎng)為例,繪制4種算法學(xué)習(xí)迭代曲線，如圖5所示。

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

由圖5可得,本文基于信息流的全局因果分析所構(gòu)建的初始結(jié)構(gòu)搜索空間,明顯優(yōu)于其他3種算法,初始搜索空間的優(yōu)化避免了隨機(jī)搜索算法對網(wǎng)絡(luò)進(jìn)行過多的搜索,使得結(jié)構(gòu)學(xué)習(xí)的精度和時(shí)間效率得到顯著提高,實(shí)驗(yàn)結(jié)果驗(yàn)證了AGS算法的有效性。

4 結(jié) 論

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

參考文獻(xiàn)：

[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ìn)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法[J]. 系統(tǒng)仿真學(xué)報(bào), 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] 劉寶寧, 章衛(wèi)國, 李廣文,等. 一種改進(jìn)遺傳算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)[J]. 西北工業(yè)大學(xué)學(xué)報(bào), 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] 汪春峰, 張永紅. 基于無約束優(yōu)化和遺傳算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法[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] 劉向南. 因果貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)研究[D]. 合肥:合肥工業(yè)大學(xué), 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] 史志富. 貝葉斯網(wǎng)絡(luò)理論及其在軍事系統(tǒng)中的應(yīng)用[M]. 北京:國防工業(yè)出版社, 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] 邸若海, 高曉光. 基于限制型粒子群優(yōu)化的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)[J]. 系統(tǒng)工程與電子技術(shù), 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.