劉廣怡李 鷗 張大龍

(解放軍信息工程大學(xué) 鄭州 450000)

一種通過(guò)結(jié)構(gòu)邊界進(jìn)行貝葉斯網(wǎng)絡(luò)學(xué)習(xí)的算法

劉廣怡*李 鷗 張大龍

(解放軍信息工程大學(xué) 鄭州 450000)

貝葉斯網(wǎng)絡(luò)是智能算法領(lǐng)域重要的理論工具，其結(jié)構(gòu)學(xué)習(xí)問(wèn)題被認(rèn)為是NP-hard問(wèn)題。該文通過(guò)混合學(xué)習(xí)算法的方式，從分析低階條件獨(dú)立性測(cè)試提供的信息入手，給出了構(gòu)造目標(biāo)網(wǎng)絡(luò)結(jié)構(gòu)空間邊界的方法，并給出了完整的證明。在此基礎(chǔ)上執(zhí)行打分搜索算法獲得最終的網(wǎng)絡(luò)結(jié)構(gòu)。仿真結(jié)果表明該算法與同類(lèi)算法相比具有更高的精度和更好的執(zhí)行效率。

貝葉斯網(wǎng)絡(luò)；結(jié)構(gòu)學(xué)習(xí)；有向無(wú)圈圖；條件獨(dú)立

1 引言

作為人工智能領(lǐng)域表示不確定性知識(shí)和推理的一種重要方法，近些年來(lái)，貝葉斯網(wǎng)絡(luò)(Bayesian Network, BN)一直是眾多國(guó)內(nèi)外學(xué)者研究的熱點(diǎn)，目前在諸如故障檢測(cè)、醫(yī)療診斷、交通管理等方面已經(jīng)取得了成功的運(yùn)用[1?3]。從貝葉斯網(wǎng)絡(luò)發(fā)展的過(guò)程看，一開(kāi)始人們關(guān)注的是尋求一種數(shù)據(jù)結(jié)構(gòu)以對(duì)聯(lián)合概率密度進(jìn)行壓縮表示，并針對(duì)該數(shù)據(jù)結(jié)構(gòu)開(kāi)發(fā)快速的概率推理算法，因此誕生了貝葉斯網(wǎng)絡(luò)。在取得成功之后，人們開(kāi)始轉(zhuǎn)而關(guān)注針對(duì)數(shù)據(jù)的網(wǎng)絡(luò)結(jié)構(gòu)自學(xué)習(xí)算法研究。本質(zhì)上看，貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)問(wèn)題屬于組合優(yōu)化問(wèn)題，并已經(jīng)被證明為NP-hard[4]，盡管如此，一些啟發(fā)式算法還是得到了成功的應(yīng)用[5?7]。

目前，BN結(jié)構(gòu)學(xué)習(xí)算法大致可分為基于獨(dú)立性測(cè)試的方法和基于打分-搜索機(jī)制的方法。近來(lái)，一些研究者結(jié)合上述兩種方法提出一類(lèi)混合算法，該類(lèi)算法首先利用條件獨(dú)立測(cè)試(ConditionalIndependence testing, CI-testing)降低搜索空間的復(fù)雜度，然后執(zhí)行評(píng)分搜索找到最佳網(wǎng)絡(luò)。這類(lèi)算法由于有選擇性地壓縮了搜索空間，因此可以提高結(jié)構(gòu)學(xué)習(xí)算法整體收斂速度，具有較強(qiáng)的實(shí)用性。

對(duì)于目前大多數(shù)針對(duì)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的混合學(xué)習(xí)算法而言，都是先通過(guò)CI測(cè)試獲得目標(biāo)網(wǎng)絡(luò)的局部結(jié)構(gòu)。文獻(xiàn)[8]中通過(guò)CI測(cè)試分析目標(biāo)網(wǎng)絡(luò)中可能存在的V結(jié)構(gòu)，但是這種方法需要事先獲得網(wǎng)絡(luò)的框架，這一條件在實(shí)際的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)中往往不容易獲得。文獻(xiàn)[9]中提出了一種MMHC(Max-Min Hill Climbing)算法，該算法分為2部分，第1部分稱(chēng)為MMPC(Max-Min Parents and Children)，它通過(guò)CI測(cè)試獲得每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)集，從而給出待學(xué)習(xí)目標(biāo)網(wǎng)絡(luò)的一個(gè)局部框架，進(jìn)而在算法的第2部分執(zhí)行打分搜索確定網(wǎng)絡(luò)中存在的邊及方向。由于算法的第1部分使用了高階CI測(cè)試，而這種測(cè)試的準(zhǔn)確性無(wú)法保證[10]，因此在搜索階段并沒(méi)有嚴(yán)格依據(jù)MMPC給出的先驗(yàn)結(jié)構(gòu)，而是進(jìn)行了相當(dāng)程度的開(kāi)放搜索，這樣就導(dǎo)致了計(jì)算資源的浪費(fèi)。文獻(xiàn)[11]提出了BNEA算法，它是一種基于MMHC和最大主子圖分解(Maximal Prime Decomposition, MPD)的方法，通過(guò)MMHC給出的節(jié)點(diǎn)Markov邊界[12]進(jìn)行MPD，從而在較低的維度上嘗試獲得網(wǎng)絡(luò)的Markov等價(jià)結(jié)構(gòu)。在一定程度上，BNEA算法獲得的Markov等價(jià)結(jié)構(gòu)比直接使用MMPC得到的局部結(jié)構(gòu)要精確，但由于調(diào)用MMPC算法無(wú)法避免高階CI測(cè)試，因此BNEA算法在計(jì)算量和精度的平衡上還有待進(jìn)一步提高。

本文提出基于混合方式的一種上下界候選學(xué)習(xí)(Upper-lower Bounds Candidate sets Searching, UBCS)算法，該方法首先通過(guò)低階CI測(cè)試確定待學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)空間的上下界，從而提供一種更有指導(dǎo)意義的候選網(wǎng)絡(luò)集，在此基礎(chǔ)上使用貪婪搜索算法確定最終的網(wǎng)絡(luò)結(jié)構(gòu)，仿真結(jié)果表明該方法能夠在保證精度的同時(shí)有效降低學(xué)習(xí)算法的時(shí)間復(fù)雜度。

2 相關(guān)知識(shí)

定義1 貝葉斯網(wǎng)絡(luò)定義 給定隨機(jī)變量x1, x2,…,xn的聯(lián)合分布P，和有向無(wú)圈圖G=(V,E)，若V={v1,v2,…,vn}與隨機(jī)變量x1,x2,…,xn一一對(duì)應(yīng)，且(G,P)滿(mǎn)足Markov條件[13]，則稱(chēng)二元組BN=(G,P)為一個(gè)貝葉斯網(wǎng)絡(luò)。

2.1 相關(guān)定義

由于貝葉斯網(wǎng)絡(luò)中節(jié)點(diǎn)和隨機(jī)變量一一對(duì)應(yīng)，因此本文中對(duì)兩者不加區(qū)分，除特殊說(shuō)明外一律統(tǒng)稱(chēng)節(jié)點(diǎn)。此外，對(duì)于圖結(jié)構(gòu)中的有向邊vi→vj用eij表示，無(wú)向邊vi?vj用eij表示，下文不再贅述。

定義2 V結(jié)構(gòu) 貝葉斯網(wǎng)絡(luò)BN=(G,P)中，?vi,vj,vk∈V ，若eik∈E, ejk∈E, eij?E且eji?E，則稱(chēng)vi,vj,vk構(gòu)成V結(jié)構(gòu)。

定義3 條件互信息MI(X,Y|Z) 隨機(jī)變量集(X,Y,Z)的條件互信息MI(X,Y|Z)定義為

其中

由于MI(X,Y|Z)=0意味著，隨機(jī)變量集X,Y在給定Z時(shí)條件獨(dú)立，即Ind(X,Y|Z)，因此一般用MI(X,Y|Z)進(jìn)行隨機(jī)變量的條件獨(dú)立測(cè)試(CI測(cè)試)，并將||Z||稱(chēng)為CI測(cè)試的階數(shù)，若Z=Φ，稱(chēng)為0階CI測(cè)試。

定義4 Markov等價(jià) 兩個(gè)具有相同節(jié)點(diǎn)集的有向無(wú)圈圖G1和G2圖等價(jià)，當(dāng)且僅當(dāng)：(1)G1和G2具有相同骨架；(2)G1和G2具有相同的V結(jié)構(gòu)。

稱(chēng)兩個(gè)貝葉斯網(wǎng)BN1=(G1,P1)和BN2=(G2, P2)Markov等價(jià)，若圖G1和G2圖等價(jià)。

按上述關(guān)系可以將同一個(gè)結(jié)點(diǎn)集上的所有有向無(wú)環(huán)圖分成多個(gè)等價(jià)類(lèi)，稱(chēng)作Markov等價(jià)類(lèi)，每一個(gè)等價(jià)類(lèi)唯一決定一個(gè)統(tǒng)計(jì)模型，且每一個(gè)等價(jià)類(lèi)可以用一個(gè)部分有向無(wú)環(huán)圖來(lái)表示，稱(chēng)之為完備PDAG。文獻(xiàn)[14]給出了Markov等價(jià)的特征[14]，文獻(xiàn)[15]將此特征擴(kuò)展到有向無(wú)環(huán)圖，并證明兩個(gè)有向無(wú)環(huán)圖是Markov等價(jià)當(dāng)且僅當(dāng)它們有同樣的構(gòu)架，并且有同樣的“V”結(jié)構(gòu)。

3 算法描述

貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法是在給定數(shù)據(jù)集D的情況下尋找貝葉斯網(wǎng)BN=(G,P)的最佳網(wǎng)絡(luò)結(jié)。文獻(xiàn)[16]證明了包含n個(gè)節(jié)點(diǎn)可能的BN結(jié)構(gòu)數(shù)為

從式(4)可以看出，隨著節(jié)點(diǎn)的增加，可能的網(wǎng)絡(luò)結(jié)構(gòu)空間呈指數(shù)級(jí)增長(zhǎng)，因此，尋找好的候選網(wǎng)絡(luò)結(jié)構(gòu)集是有效降維的辦法?；诖耍疚慕o出一種UBCS算法，該算法通過(guò)構(gòu)造目標(biāo)網(wǎng)絡(luò)PDAG的上下界給出候選網(wǎng)絡(luò)集合，并通過(guò)打分搜索得到最終網(wǎng)絡(luò)模型。下文中首先給出UBCS 的第1部分SGLA算法，并證明其輸出結(jié)果G+是目標(biāo)網(wǎng)絡(luò)道德圖的上界，之后引入0階互信息量不增原理，從而給出UBCS 的第2部分LGLA算法，即目標(biāo)網(wǎng)絡(luò)PDAG下界的學(xué)習(xí)算法，在這之后討論搜索算法。

3.1 候選網(wǎng)絡(luò)學(xué)習(xí)算法

首先給出SGLA描述(表1)。

由SGLA算法過(guò)程可以知道G+是弦化圖，對(duì)于弦化圖有定理1成立：

定理1 對(duì)于任意無(wú)向圖G，若它是完備PDAG當(dāng)且僅當(dāng)G是弦化的。

定理證明參見(jiàn)文獻(xiàn)[17]。由定理知G+是完備PDAG，即在最好的情況下，由SGLA算法得到的G+就是目標(biāo)網(wǎng)絡(luò)的完備PDAG，但此條件太強(qiáng)，下面給出一個(gè)更為一般性的定理。

定理2 給定數(shù)據(jù)集D，設(shè)待求貝葉斯網(wǎng)BN= (G,P)在數(shù)據(jù)集D下可能的結(jié)構(gòu)為GD，其對(duì)應(yīng)的道德圖為GD_m，則由SGLA算法生成的無(wú)向圖G+是由GD_m構(gòu)成的偏序集GM=(GD_m,?)的上界。

表1 SGLA算法

于?ejk∈_m,0階CI測(cè)試保證了一定有ejk∈E+；對(duì)于?ejk∈_m，雖然0階CI測(cè)試不能保證一定有ejk∈E+，但SGLA算法第4步保證了此時(shí)一定有ejk∈E+。 證畢

定理 3 存在于BN=(G,P)中的任意V結(jié)構(gòu)，一定存在于G+的MPD分解[18]的某一子圖中。

定理3的證明參見(jiàn)文獻(xiàn)[11]，該定理保證了SGLA輸出結(jié)果中G,G,…,G覆蓋原圖所有的V結(jié)構(gòu)，為下文將要給出的LGLA算法提供初始值。

上文討論了GM=(GD_m,?)的上界，從而為搜索提供了可能的備選，下面討論待學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)空間的下界，從而為搜索算法給出一個(gè)較為精確的初始值。

首先引入一個(gè)引理：

引理1 對(duì)于任意兩個(gè)離散隨機(jī)變量vi,vj∈V和V的子集S?V/{vi,vj}，有H(vi|vj,S)≤H(vi|vj)成立，等號(hào)成立的條件為當(dāng)且僅當(dāng)：Ind(vi, vj|S)。

證明從略。

定理4 給定貝葉斯網(wǎng)B=(G,P)，其中G= (V,E)，對(duì)于任意vi,vj,vk∈V，有MI(vi,vk)=，其中V′={vi,vj,vk}?V成立，如果存在eij∈E,ekj∈E,eik?E,eki?E。

證明 由于存在eij∈E,ekj∈E，不失一般性，不妨設(shè)MI(vi,vj)=min{MI(vi,vj),MI(vk,vj)}，只需要證明MI(vi,vk)＞MI(vi,vj)，由互信息定義：MI(vi, vk)=H(vi)?H(vi|vk),MI(vi,vj)=H(vi)?H(vi|vj),

則有

由vi,vj,vk關(guān)系可知節(jié)點(diǎn)vj∈S，其中S滿(mǎn)足Ind(vi,vk|S)，因此式(5)可以寫(xiě)為：

由引理1可得MI(vi,vk)≤MI(vi,vj)，其中等號(hào)成立的條件是S/vj=Φ。 證畢

定理4稱(chēng)為0階互信息量不增性原理。從定理的條件可知，對(duì)于存在V結(jié)構(gòu)的情況該定理是不適用的。即對(duì)于如圖1所示的結(jié)構(gòu)而言，定理4無(wú)法判斷MI(a,d)和MI(a,b)的大小關(guān)系。如果首先在網(wǎng)絡(luò)中排除所有的V結(jié)構(gòu)，再來(lái)考慮節(jié)點(diǎn)a和節(jié)點(diǎn)cbe的可能連接關(guān)系，若MI(a,c)最大，則一定有MI(a,c) =MI(a,b)＞MI(a,e)，此時(shí)由1階CI測(cè)試可以直接排除掉ac連接的可能性，因此就能直接確定ab是相連的。通過(guò)以上分析可以看出，0階互信息量不增性原理實(shí)際上提供了一種除V結(jié)構(gòu)外的確定網(wǎng)絡(luò)中無(wú)向邊存在性的思路。

基于以上分析給出G?學(xué)習(xí)算法(LGLA)示于表2。

LGLA算法中涉及的V結(jié)構(gòu)測(cè)試算法VSTA (V-Structure Test Algorithm)描述如表3所示。

VSTA是一種“盡力而為”的檢測(cè)算法，由于僅使用了0階和1階CI測(cè)試，其低階檢測(cè)的準(zhǔn)確性保證了檢測(cè)出的V結(jié)構(gòu)的存在性，而對(duì)于構(gòu)成V結(jié)構(gòu)的兩個(gè)父節(jié)點(diǎn)間通路多于一條時(shí)，將不予檢測(cè)。這種檢測(cè)方式避免了高計(jì)算量和干擾邊的引入。

圖1 BN中存在V結(jié)構(gòu)的情況

表2 LGLA算法

表3 VSTA算法

對(duì)于LGLA的輸出結(jié)果G?，有定理5成立。

定理 5 設(shè)待求貝葉斯網(wǎng)BN=(G,P)中G的所有可能的完備PDAG結(jié)構(gòu)和包含關(guān)系構(gòu)成偏序集PG=(GPDAG,?)，則由LGLA算法生成的G?是PDAG。

證明 G?包含有向邊和無(wú)向邊，對(duì)于無(wú)向邊，上文給出的0階互信息量不增原理保證了對(duì)任意無(wú)向邊eij∈G?[E?]一定有eij∈G[E]成立。G?中的有向邊由VSTA給出。由定理3知BN=(G,P)中的任意V結(jié)構(gòu)，一定存在于某個(gè)中，由VSTA算法的性質(zhì)可知任意存在于G?中的V結(jié)構(gòu)一定存在于G中，反之則不一定成立。對(duì)于無(wú)圈圖而言，刪除任意有向邊得到的仍是無(wú)圈圖。因此G?是PDAG。

證畢

定理 6 當(dāng)VSTA返回結(jié)果完全準(zhǔn)確時(shí)，G?是PG的下界。

證明略。

定理 6的條件較強(qiáng)。事實(shí)上，在很多情況下，可以近似認(rèn)為G?是PG的下界。以Asia網(wǎng)絡(luò)為例。通過(guò)圖2可以看到，G?中的任意邊都存在于原始網(wǎng)絡(luò)的PDAG中。

圖2 Asia網(wǎng)絡(luò)結(jié)構(gòu)及其對(duì)應(yīng)的PDAG和G?

3.2 打分搜索學(xué)習(xí)算法

爬山法是關(guān)于貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)中基于打分搜索的一種常用貪婪搜索算法，其搜索算子共有3種：加邊、減邊和反轉(zhuǎn)邊。在UDCS算法中，同樣使用爬山搜索算法，只是搜索過(guò)程受到SGLA和LGLA算法給出的上下界的限制，即搜索算子產(chǎn)生的新的網(wǎng)絡(luò)結(jié)構(gòu)如果超出SGLA和LGLA給定的邊界，則丟棄該結(jié)構(gòu)。為了避免搜索過(guò)快的陷入局部最優(yōu)結(jié)構(gòu)，引入次優(yōu)競(jìng)爭(zhēng)機(jī)制，每一輪搜索保留前N個(gè)得分最高的結(jié)構(gòu)進(jìn)入下一輪迭代。原則上N的大小由網(wǎng)絡(luò)結(jié)構(gòu)的規(guī)模決定，網(wǎng)絡(luò)規(guī)模越大，N越大，但過(guò)大的次優(yōu)候選集將導(dǎo)致算法時(shí)間復(fù)雜度的增加。對(duì)于規(guī)模如Alarm網(wǎng)絡(luò)的待學(xué)習(xí)網(wǎng)絡(luò)而言，推薦經(jīng)驗(yàn)值N=10。為了便于與文獻(xiàn)[11]中的BENA算法進(jìn)行比較，采用BDeu評(píng)分函數(shù)作為搜索的目標(biāo)函數(shù)。

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

使用標(biāo)準(zhǔn)的Alarm網(wǎng)絡(luò)對(duì)本算法進(jìn)行測(cè)試，并與BNEA和MMHC算法進(jìn)行比較。首先比較的是在不同樣本數(shù)3種算法得到的網(wǎng)絡(luò)結(jié)構(gòu)的評(píng)分，如表 4所示，其中，為了便于對(duì)比觀察，將評(píng)分結(jié)果進(jìn)行了歸一化處理，仿真結(jié)果示于表4。

表4的結(jié)果是重復(fù)實(shí)驗(yàn)10次的平均結(jié)果。從表4中可以看出，UBCS算法得到的網(wǎng)絡(luò)結(jié)構(gòu)評(píng)分在小樣本數(shù)量下優(yōu)于BENA和MMHC，隨著樣本數(shù)的增加，3種算法學(xué)習(xí)出的網(wǎng)絡(luò)結(jié)構(gòu)評(píng)分趨于一致，在樣本數(shù)達(dá)到5000時(shí)已經(jīng)和真實(shí)網(wǎng)絡(luò)的評(píng)分非常接近。UBCS算法中包含SGLA和LGLA兩個(gè)主要算法，其中LGLA中由于VSTA算法并不能充分保證檢測(cè)結(jié)果的真實(shí)性，但是從仿真結(jié)果來(lái)看，對(duì)最終學(xué)習(xí)性能幾乎沒(méi)有影響，這一方面由于SGLA提供的上界具有很高的穩(wěn)定性，另一方面在受約束的打分搜索學(xué)習(xí)過(guò)程中這種影響被進(jìn)一步減弱所致。應(yīng)當(dāng)指出的是算法在樣本數(shù)較大時(shí)(樣本數(shù)大于5000以上)容易出現(xiàn)過(guò)學(xué)習(xí)的現(xiàn)象，一般認(rèn)為過(guò)學(xué)習(xí)現(xiàn)象出現(xiàn)在小樣本階段，但對(duì)于如貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)而言的高維組合優(yōu)化問(wèn)題，由于組合空間的指數(shù)級(jí)增長(zhǎng)，一般情況下很難使用充分的樣本進(jìn)行學(xué)習(xí)，且目前的算法在巨大樣本數(shù)面前所付出的時(shí)間性能的代價(jià)也是不容忽視的問(wèn)題，因此，對(duì)于維數(shù)較高的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)問(wèn)題，應(yīng)當(dāng)探索在適當(dāng)樣本數(shù)下精度和泛化能力平衡的學(xué)習(xí)算法。UBCS算法中由于SGLA和LGLA的使用對(duì)泛化能力起到了一定的保證，因此在學(xué)習(xí)過(guò)程中沒(méi)有發(fā)現(xiàn)過(guò)學(xué)習(xí)現(xiàn)象的發(fā)生。

表4 UBCS, BENA, MMHC在Alarm網(wǎng)絡(luò)數(shù)據(jù)集上的評(píng)分對(duì)比

3種算法所消耗的時(shí)間如圖3算法所示。仿真使用的計(jì)算機(jī)是主頻為2.50 GHz的Intel 4核處理器，內(nèi)存4G。從圖3算法中可以看出，UBCS相比于其他兩種算法在時(shí)間復(fù)雜度上具有明顯的優(yōu)勢(shì)，與MMHC相比，BNEA和UBCS都使用了MDP分解降低了搜索空間維度，從而壓縮了學(xué)習(xí)時(shí)間，而B(niǎo)NEA由于調(diào)用了MMHC中的MMPC算法，在最壞情況下BNEA可能與MMHC具有相同的復(fù)雜度，BNEA的空間分解從頭至尾僅依賴(lài)分解空間中的0階和1階CI測(cè)試，因而具有更好的時(shí)間復(fù)雜度性能。

5 結(jié)束語(yǔ)

圖3 算法時(shí)間復(fù)雜度比較

本文提出了一種混合方式的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法(UBCS)。該算法利用低階的CI測(cè)試獲得待學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)空間的上下界，從而提供一種較好的約束結(jié)構(gòu)，進(jìn)而通過(guò)打分搜索的方式確定網(wǎng)絡(luò)的最終結(jié)構(gòu)。理論證明和仿真結(jié)果都表明了該算法的有效性。與同類(lèi)混合結(jié)構(gòu)學(xué)習(xí)算法相比，UBCS算法具有時(shí)間復(fù)雜度上的明顯優(yōu)勢(shì)，并可以達(dá)到令人較為滿(mǎn)意的學(xué)習(xí)精度。下一步的研究目標(biāo)為進(jìn)一步完善UBCS算法中的上下界學(xué)習(xí)算法(SGLA和LGLA)，并嘗試應(yīng)用到諸如增量學(xué)習(xí)和不完備數(shù)據(jù)下的學(xué)習(xí)等貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的其他問(wèn)題中。

[1] Pourali M and Mosleh A. A functional sensor placement optimization method for power systems health monitoring[J]. IEEE Transactions on Industry Applications, 2013, 49(4): 1711-1719.

[2] Andrzej W and Edyta W. Integrating Bayesian networks into fuzzy hypothesis testing problem-case based presentation[C]. 2013 IEEE 15th International Conference on e-Health Networking, Application & Services (Healthcom), Lisbon, 2013: 100-104.

[3] Neumann T, Bohnke, P L, and Tcheumadjeu T. Dynamic representation of the fundamental diagram via Bayesian networks for estimating traffic flows from probe vehicle data[C]. 2013 16th International IEEE Conference on Intelligent Transportation Systems (ITSC), The Hague, 2013: 1870-1875.

[4] Chickering D M, Geiger D, and Heckerman D. Learning Bayesian networks is NP-hard[R]. Technical Report MSRTR-94-17, Microsoft Research, 1994: 1-22.

[5] Carvalho A. A cooperative coevolutionary genetic algorithm for learning bayesian network structures[OL]. http://arxiv. org/abs/1305.6537. 2013: 1131-1138.

[6] Aouay S, Jamoussi S, and Ben Ayed Y. Particle swarm optimization based method for Bayesian Network structure learning[C]. 2013 5th International Conference on Modeling, Simulation and Applied Optimization (ICMSAO), Hammamet, 2013: 1-6.

[7] Basak A, Brinster I, Ma X, et al.. Accelerating Bayesian network parameter learning using Hadoop and MapReduce [C]. Proceedings of the 1st International Workshop on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications, ACM, Beijing, 2012: 101-108.

[8] 賈海洋, 陳娟, 朱允剛, 等. 基于混合方式的貝葉斯網(wǎng)弧定向算法[J]. 電子學(xué)報(bào), 2009, 37(8): 1842-1847.

Jia Hai-yang, Chen Juan, and Zhu Yun-gang. A Hybrid method for orienting edges of Bayesian network[J]. Acta Electronica Sinica, 2009, 37(8): 1842-1847.

[9] Tsamardinos I, Brown L F, and Aliferis C F. The max-min hill climbing BN structure learning algorithm[J]. Machine Learning, 2006, 65(1): 31-78.

[10] Wong M L and Leung K S. An efficient data mining method for learning Bayesian networks using an evolutionary algorithm-based hybrid approach[J]. IEEE Transactions on Evolutionary Computation, 2004, 8(4): 378-404.

[11] 朱明敏, 劉三陽(yáng), 楊有龍. 基于混合方式的貝葉斯網(wǎng)絡(luò)等價(jià)類(lèi)學(xué)習(xí)算法[J]. 電子學(xué)報(bào), 2013, 41(1): 98-104.

Zhu Ming-min, Liu San-yang, and Yang You-long. Structural learning bayesian network equivalence classes based on a hybrid method[J]. Acta Electronica Sinica, 2013, 41(1): 98-104.

[12] De Morais S R and Aussem A. A novel Markov boundary based feature subset selection algorithm[J]. Neurocomputing, 2010, 73(4): 578-584.

[13] Neapolian R E. Learning Bayesian Networks [M]. Englewood Cliffs, NJ, US, Prentice-Hall, Inc., 2004: 31-39.

[14] Frydengberg M. The chain graph markov property[J]. Scandinavian Journal of Statistics, 1990, 17(4): 333-353.

[15] Verma T and pearl J. An algorithm for deciding if a set of observed independencies has a causal explanation[C]. Proceedings of the Eighth Annual Conference on Uncertainty in Artificial Intelligence, Stanford, California, 1992: 323-330.

[16] Robinson R W. Counting Unlabeled Acyclic Diagraphs[M]. Berlin Heidelberg, Springer, 1977: 28-43.

[17] Andersson S A, Madigan D, and Perlman M D. A characterization of Markov equivalence classes for acyclic digraphs[J]. The Annals of Statistics, 1997, 25(2): 505-541.

[18] Wu D. Maximal prime subgraph decomposition of Bayesian networks: a relational database perspective[J]. International Journal of Approximate Reasoning, 2007, 46(2): 334-345.

劉廣怡： 男，1982年生，博士生，研究方向?yàn)榫W(wǎng)絡(luò)數(shù)據(jù)智能處理、智能算法、貝葉斯網(wǎng)絡(luò).

李 鷗： 男，1961年生，教授，博士生導(dǎo)師，研究方向?yàn)槿斯ぶ悄堋⒂?jì)算機(jī)網(wǎng)絡(luò)協(xié)議、認(rèn)知網(wǎng)絡(luò).

張大龍： 男，1976年生，博士，講師，研究方向?yàn)榫W(wǎng)絡(luò)數(shù)據(jù)智能處理、網(wǎng)絡(luò)協(xié)議分析.

Learning Bayesian Network from Structure Boundaries

Liu Guang-yi Li Ou Zhang Da-long
(The PLA Information Engineering University, Zhengzhou 450000, China)

Bayesian network is an important theoretical tool in the artificial algorithm field, and learning structure from data is considered as NP-hard. In this article, a hybrid learning method is proposed by starting from analysis of information provided by low-order conditional independence testing. The methods of constructing boundaries of the structure space of the target network are given, as well as the complete theoretical proof. A search & scoring algorithm is operated to find the final structure of the network. Simulation results show that the hybrid learning method proposed in this article has higher learning precision and is more efficient than similar algorithms.

Bayesian Network (BN); Structure learning; Directed acyclic graph; Conditional Independence (CI)

TP18

： A

：1009-5896(2015)04-0894-06

10.11999/JEIT140786

2014-06-17收到，2014-12-20改回

國(guó)家科技重大專(zhuān)項(xiàng)(2014ZX03006003)資助課題

*通信作者：劉廣怡 liu.guangyi@outlook.com