劉廣怡李 鷗 張大龍

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

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

劉廣怡*李 鷗 張大龍

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

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

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

1 引言

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

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

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

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

2 相關(guān)知識

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

2.1 相關(guān)定義

由于貝葉斯網(wǎng)絡(luò)中節(jié)點(diǎn)和隨機(jī)變量一一對應(yīng)，因此本文中對兩者不加區(qū)分，除特殊說明外一律統(tǒng)稱節(jié)點(diǎn)。此外，對于圖結(jié)構(gòu)中的有向邊vi→vj用eij表示，無向邊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，則稱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時條件獨(dú)立，即Ind(X,Y|Z)，因此一般用MI(X,Y|Z)進(jìn)行隨機(jī)變量的條件獨(dú)立測試(CI測試)，并將||Z||稱為CI測試的階數(shù)，若Z=Φ，稱為0階CI測試。

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

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

按上述關(guān)系可以將同一個結(jié)點(diǎn)集上的所有有向無環(huán)圖分成多個等價類，稱作Markov等價類，每一個等價類唯一決定一個統(tǒng)計(jì)模型，且每一個等價類可以用一個部分有向無環(huán)圖來表示，稱之為完備PDAG。文獻(xiàn)[14]給出了Markov等價的特征[14]，文獻(xiàn)[15]將此特征擴(kuò)展到有向無環(huán)圖，并證明兩個有向無環(huán)圖是Markov等價當(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個節(jié)點(diǎn)可能的BN結(jié)構(gòu)數(shù)為

從式(4)可以看出，隨著節(jié)點(diǎn)的增加，可能的網(wǎng)絡(luò)結(jié)構(gòu)空間呈指數(shù)級增長，因此，尋找好的候選網(wǎng)絡(luò)結(jié)構(gòu)集是有效降維的辦法。基于此，本文給出一種UBCS算法，該算法通過構(gòu)造目標(biāo)網(wǎng)絡(luò)PDAG的上下界給出候選網(wǎng)絡(luò)集合，并通過打分搜索得到最終網(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算法過程可以知道G+是弦化圖，對于弦化圖有定理1成立：

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

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

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

表1 SGLA算法

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

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

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

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

首先引入一個引理：

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

證明從略。

定理4 給定貝葉斯網(wǎng)B=(G,P)，其中G= (V,E)，對于任意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滿足Ind(vi,vk|S)，因此式(5)可以寫為：

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

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

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

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

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

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

表2 LGLA算法

表3 VSTA算法

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

證畢

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

證明略。

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

本文提出了一種混合方式的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法(UBCS)。該算法利用低階的CI測試獲得待學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)空間的上下界，從而提供一種較好的約束結(jié)構(gòu)，進(jìn)而通過打分搜索的方式確定網(wǎng)絡(luò)的最終結(jié)構(gòu)。理論證明和仿真結(jié)果都表明了該算法的有效性。與同類混合結(jié)構(gòu)學(xué)習(xí)算法相比，UBCS算法具有時間復(fù)雜度上的明顯優(yōu)勢，并可以達(dá)到令人較為滿意的學(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í)的其他問題中。

[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é)報, 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] 朱明敏, 劉三陽, 楊有龍. 基于混合方式的貝葉斯網(wǎng)絡(luò)等價類學(xué)習(xí)算法[J]. 電子學(xué)報, 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改回

國家科技重大專項(xiàng)(2014ZX03006003)資助課題

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