一種通過結構邊界進行貝葉斯網絡學習的算法

劉廣怡李 鷗 張大龍

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

一種通過結構邊界進行貝葉斯網絡學習的算法

劉廣怡*李 鷗 張大龍

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

貝葉斯網絡是智能算法領域重要的理論工具，其結構學習問題被認為是NP-hard問題。該文通過混合學習算法的方式，從分析低階條件獨立性測試提供的信息入手，給出了構造目標網絡結構空間邊界的方法，并給出了完整的證明。在此基礎上執行打分搜索算法獲得最終的網絡結構。仿真結果表明該算法與同類算法相比具有更高的精度和更好的執行效率。

貝葉斯網絡；結構學習；有向無圈圖；條件獨立

1 引言

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

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

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

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

2 相關知識

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

2.1 相關定義

由于貝葉斯網絡中節點和隨機變量一一對應，因此本文中對兩者不加區分，除特殊說明外一律統稱節點。此外，對于圖結構中的有向邊vi→vj用eij表示，無向邊vi?vj用eij表示，下文不再贅述。

定義2 V結構 貝葉斯網絡BN=(G,P)中，?vi,vj,vk∈V ，若eik∈E, ejk∈E, eij?E且eji?E，則稱vi,vj,vk構成V結構。

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

其中

由于MI(X,Y|Z)=0意味著，隨機變量集X,Y在給定Z時條件獨立，即Ind(X,Y|Z)，因此一般用MI(X,Y|Z)進行隨機變量的條件獨立測試(CI測試)，并將||Z||稱為CI測試的階數，若Z=Φ，稱為0階CI測試。

定義4 Markov等價 兩個具有相同節點集的有向無圈圖G1和G2圖等價，當且僅當：(1)G1和G2具有相同骨架；(2)G1和G2具有相同的V結構。

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

按上述關系可以將同一個結點集上的所有有向無環圖分成多個等價類，稱作Markov等價類，每一個等價類唯一決定一個統計模型，且每一個等價類可以用一個部分有向無環圖來表示，稱之為完備PDAG。文獻[14]給出了Markov等價的特征[14]，文獻[15]將此特征擴展到有向無環圖，并證明兩個有向無環圖是Markov等價當且僅當它們有同樣的構架，并且有同樣的“V”結構。

3 算法描述

貝葉斯網絡結構學習算法是在給定數據集D的情況下尋找貝葉斯網BN=(G,P)的最佳網絡結。文獻[16]證明了包含n個節點可能的BN結構數為

從式(4)可以看出，隨著節點的增加，可能的網絡結構空間呈指數級增長，因此，尋找好的候選網絡結構集是有效降維的辦法。基于此，本文給出一種UBCS算法，該算法通過構造目標網絡PDAG的上下界給出候選網絡集合，并通過打分搜索得到最終網絡模型。下文中首先給出UBCS 的第1部分SGLA算法，并證明其輸出結果G+是目標網絡道德圖的上界，之后引入0階互信息量不增原理，從而給出UBCS 的第2部分LGLA算法，即目標網絡PDAG下界的學習算法，在這之后討論搜索算法。

3.1 候選網絡學習算法

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

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

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

定理證明參見文獻[17]。由定理知G+是完備PDAG，即在最好的情況下，由SGLA算法得到的G+就是目標網絡的完備PDAG，但此條件太強，下面給出一個更為一般性的定理。

定理2 給定數據集D，設待求貝葉斯網BN= (G,P)在數據集D下可能的結構為GD，其對應的道德圖為GD_m，則由SGLA算法生成的無向圖G+是由GD_m構成的偏序集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結構，一定存在于G+的MPD分解[18]的某一子圖中。

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

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

首先引入一個引理：

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

證明從略。

定理4 給定貝葉斯網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，不失一般性，不妨設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關系可知節點vj∈S，其中S滿足Ind(vi,vk|S)，因此式(5)可以寫為：

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

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

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

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

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

圖1 BN中存在V結構的情況

表2 LGLA算法

表3 VSTA算法

對于LGLA的輸出結果G?，有定理5成立。

定理 5 設待求貝葉斯網BN=(G,P)中G的所有可能的完備PDAG結構和包含關系構成偏序集PG=(GPDAG,?)，則由LGLA算法生成的G?是PDAG。

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

證畢

定理 6 當VSTA返回結果完全準確時，G?是PG的下界。

證明略。

定理 6的條件較強。事實上，在很多情況下，可以近似認為G?是PG的下界。以Asia網絡為例。通過圖2可以看到，G?中的任意邊都存在于原始網絡的PDAG中。

圖2 Asia網絡結構及其對應的PDAG和G?

3.2 打分搜索學習算法

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

4 實驗結果與分析

使用標準的Alarm網絡對本算法進行測試，并與BNEA和MMHC算法進行比較。首先比較的是在不同樣本數3種算法得到的網絡結構的評分，如表 4所示，其中，為了便于對比觀察，將評分結果進行了歸一化處理，仿真結果示于表4。

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

表4 UBCS, BENA, MMHC在Alarm網絡數據集上的評分對比

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

5 結束語

圖3 算法時間復雜度比較

本文提出了一種混合方式的貝葉斯網絡結構學習算法(UBCS)。該算法利用低階的CI測試獲得待學習網絡結構空間的上下界，從而提供一種較好的約束結構，進而通過打分搜索的方式確定網絡的最終結構。理論證明和仿真結果都表明了該算法的有效性。與同類混合結構學習算法相比，UBCS算法具有時間復雜度上的明顯優勢，并可以達到令人較為滿意的學習精度。下一步的研究目標為進一步完善UBCS算法中的上下界學習算法(SGLA和LGLA)，并嘗試應用到諸如增量學習和不完備數據下的學習等貝葉斯網絡結構學習的其他問題中。

[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] 賈海洋, 陳娟, 朱允剛, 等. 基于混合方式的貝葉斯網弧定向算法[J]. 電子學報, 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] 朱明敏, 劉三陽, 楊有龍. 基于混合方式的貝葉斯網絡等價類學習算法[J]. 電子學報, 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年生，博士生，研究方向為網絡數據智能處理、智能算法、貝葉斯網絡.

李 鷗： 男，1961年生，教授，博士生導師，研究方向為人工智能、計算機網絡協議、認知網絡.

張大龍： 男，1976年生，博士，講師，研究方向為網絡數據智能處理、網絡協議分析.

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改回

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

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