貝葉斯網絡結構學習研究

殷陶

（上海交通大學 計算機系，上海200240）

貝葉斯網絡結構學習研究

殷陶

（上海交通大學 計算機系，上海200240）

針對貝葉斯網絡結構學習方法難以兼顧高準確率和高效率的問題，提出了一種基于Markov Chain Monte Carlo(MCMC)方法的貝葉斯網絡結構學習方法的改進。改進包括：使用依賴關系分析，利用統計學的方法對采樣空間進行大幅縮減，能夠在精確控制準確度的情況下大幅提高時間效率；結合先驗知識，從理論角度將先驗知識融入評分中得到完全服從后驗分布的結果；搜索最優子結構，對于特定的一些結構搜索最優子結構而不是采用貪心的方法，提高了貝葉斯網絡結構學習的準確率。通過理論分析可以證明時間復雜度得到了大幅的降低。并且可以在犧牲可預知的準確率的情況下，將指數時間復雜度降為線性時間。大量的數據實驗表明，經改進后的方法在時間和準確性上都具有良好的表現。

貝葉斯網絡學習;時間效率;獨立性檢測;最優子結構;先驗知識;Markov Chain Monte Carlo(MCMC)

在已知數據中進行貝葉斯網絡結構學習是一個重要的問題，在近些年中也得到了廣泛和深入的研究。貝葉斯網絡成功的應用在多個領域，諸如：生物信息學，計算機視覺，經濟學等。貝葉斯網絡是一個有向無環圖 （directed acyclic graph,DAG），其結構表明了數據間的條件獨立性和因果關系。貝葉斯網絡結構數隨著結點個數的增長呈超指數增長。因此，無論采用任何方法進行貝葉斯網絡結構學習都要面臨巨大的樣本空間的問題。貝葉斯網絡學習問題也被證明是一個NP-hard問題[1],為了克服樣本空間巨大的困難，許多學者進行了大量的研究，并提出了一些學習方法。總體上來說目前貝葉斯結構學習方法分為兩大類：基于啟發式搜索的方法和基于采樣的方法。基于啟發式搜索的方法最大的問題是準確性難以保證，特別是在高維的情況下很難讓人信服。基于采樣的方法中最常使用的方法就是MCMC采樣，其優點在于從理論上可以保證解的最優性。但是往往在實際應用中計算復雜度是不可行的，除非只有很少的結點。本文提出一種改進的方法，在基于MCMC采樣方法上使用一些帶有啟發式的信息，在具有嚴格理論支持的置信度控制下大幅縮減樣本空間來提高效率。并且在一些關鍵環節使用搜索代替貪心等啟發式信息來提高準確率，使得算法可以同時具有較高的準確率和效率。

1 貝葉斯網絡結構學習背景

由于我們可以給出完整的服從后驗概率的評分，所以我們找到后驗概率最大的圖結構變為只需找到最高評分。如前文所述，目前兩大類方法分別為:1）啟發式搜索，特點是時間效率高但不可靠；2）采樣，特點是有正確性理論保證但時間效率低。本文采用采樣的方法并改進其時間效率。

2 基于MCMC的貝葉斯網絡結構學習

2.1 Metropolis-Hastings(MH)

2.2 拓撲排序

拓撲排序是對有向無環圖的頂點的一種排序，它使得如果存在一條從頂點A到頂點B的路徑，那么在排序中B出現在A的后面。基于采樣的方法進行貝葉斯網絡結構學習通常采樣空間是貝葉斯網絡結構的拓撲排序。本文也使用這樣的方法，主要原因在于拓撲排序縮減了指數級的樣本空間，從而大幅提升時間效率和準確率。

2.3 本文基于MCMC的貝葉斯網絡結構學習流程

如圖1所示，本文方法步驟主要如下：1）產生隨機初始序列：由于MH算法保證了采樣過程的遍歷性和穩定性，初始序列的產生只要是符合數據結點個數的任一拓撲排序即可。2）隨機游走：本文采用隨機交換兩個結點作為隨機游走的方法。即以相同概率抽取兩個結點交換。3）評分：根據評分公式計算新得拓撲排序的評分，拓撲排序的評分為所對應最佳圖結構的評分。4）判定是否接受：使用MH算法結合評分計算出轉移概率，再使用隨機的方法使得接受概率符合轉移概率。當接受時則新狀態替換舊狀態繼續進行隨機游走，當不接受時返回原狀態進行隨機游走。5）判定是否穩定：MH算法雖然可以保證采樣過程收斂，但是沒有明確的判定條件，這仍然是很多學者在研究的熱點問題。本文根據實驗和經驗給出了判定條件：隨機游走1 000次沒有找到更優的圖結構即認為穩定。

圖1 本文基于MCMC的貝葉斯網絡結構學習流程Fig.1 Our flow chat of Bayesian network structure learning method based on MCMC

2.4 時間復雜度分析

基于MCMC采樣方法的貝葉斯網絡結構學習的時間復雜度決定因素主要為：收斂次數和每次迭代所用時間。收斂次數與空間大小（結點個數），空間樣貌，隨機路線，隨機游走方法，采樣方法等相關。優化收斂次數屬于如何改進MCMC算法范疇，這個問題也是當前的熱點問題，但是不在本文討論范疇。另外一個因素就是每次迭代時間，由于拓撲排序的評分由最佳子結構決定，盡管最佳子結構可以化簡為每個結點找尋最佳父集合，但是如果使用樸素的方法仍然需要O(L×node×2node)。其中L為數據集長度。如果設收斂次數為T，則總時間復雜度為 O(T×L×node×2node)。

3 基于MCMC貝葉斯網絡結構學習方法改進

針對基于MCMC的貝葉斯網絡結構學習方法時間效率較低的問題本文提供了一種結合獨立性檢測的方法進行優化。同時為了結合實際應用的需要給出了在理論框架下加入先驗知識的方法。最后，為了增加準確率使用了一種搜索記憶最佳子結構的方法，試圖兼顧時間效率與準確率。

3.1 獨立性檢測

基于MCMC貝葉斯網絡結構學習方法通常都會選擇拓撲排序作為采樣空間以獲得更好的效果。但是必然面臨拓撲排序評分的問題，時間復雜度通常為O（L×node×2node)。這時存在一個可能的改進方法即預處理每一個局部結構（每個結點的父集合）的評分，但是顯而易見空間復雜度達到O（node×2node)，除非只有少數結點否則空間不可接受。本文在此提供了一個妥協的方案，引進啟發式搜索學習方法中有時使用的獨立性檢測，可以在控制準確率的情況下大幅縮減空間復雜度。這里包含一個重要的假設，就是每個子結點的父集合是比較少的，在大多數貝葉斯網絡結構學習中都包含此假設，而且存在此假設仍然為NP-hard問題。同時在實際應用中，如果父結點過多，條件概率表也是呈指數上漲，將不存在實際應用的意義。

此時我們可以根據實際需要設置置信度，利用G2統計和假設檢驗的思路，使用Max-Min Parents and Children（MMPC）方法[5]對所有結點進行獨立性檢驗，可以得到每個結點的非條件獨立集合。此方法帶來的好處是縮小了每個結點的備選父集合，之所以能夠縮減是因為父結點一定與子結點條件不獨立。這樣以來使得預處理的方式變為可行方法，因為備選集合的縮減使得空間不再成為限制。預處理使得每次評分不再需要遍歷整個數據集進行計算，將時間復雜度由O(L×node×2node)降為 O(node×2node)cpc 代表備選集合個數。 在此基礎上，如果我們認為獨立性檢測足夠準確，即對于任意結點，凡是非條件獨立且拓撲排序在該結點之前的結點均為該結點的父親。這樣以來，我們就不再需要對備選父集合進行搜索，直接獲得父集合，將時間復雜度由O(node×2cpc)降低到O(node)，即為線性復雜度。

3.2 先驗知識

在實際應用中，很多情況下我們不僅有實驗數據，還有很多先驗知識。如何將先驗知識結合實驗數據進行結構學習就成為一個重要的課題。本文在此從理論角度將先驗知識融入評分公式，使得評分服從結合先驗后的數據概率分布。前文中已經提到：P（D，G）=P(G)P(D|G)。

在沒有先驗的情況下我們默認認為P(G)具有相同的概率，由于評分只用來計算相對值，所以相同的P(G)值可以不進行考慮。當我們需要進行先驗的融入時，我們將先驗知識表示為P(E)=p,P∈[0,1],E表示了一條有向邊，p表示先驗知識估計E出現的概率。而在評分時我們搜索每一條先驗知識，若符合，我們對評分乘以系數p，若不符合，我們對評分乘以系數（1-p）。可以看到至此我們成功的將先驗概率部分P(G)融入到評分公式中。

3.3 最佳子結構

由此可以估計出時間復雜度為O（node×2cpc)，與每次迭代需時復雜度相同。因為做預處理只需一次，所以明顯優于在MCMC采樣隨機游走迭代過程中進行計算。本文方法通過預處理得到最佳子結構后就可以較低的設置置信度來確保幾乎所有的非條件獨立結點對被找出，同時以常數時間得到最優子結構評分而不受錯誤非條件獨立結點對影響。

4 實驗數據和分析

本文所采用的實驗數據為隨機數據。方法為隨機生成貝葉斯網絡結構，同時隨機生成符合該貝葉斯網絡結構的數據集。然后使用本文所述方法通過該數據進行網絡結構學習，由于我們已知生成網絡，所以可以精度得到學習的網絡結構和真實網絡結構的區別。

4.1 時間對比

下面我們列出在不同結點情況下一般方法和本文改進過后的方法時間對比。所列時間為從一個初始拓撲排序出發利用MCMC采樣到收斂的時間。

表1時間對比Tab.1 Time comparison

從上表可以明顯看出我們的方法改進后時間效率得到了極大的提高，特別是當結點增多的時候本文改進方法的提高更加明顯。從本文方法所用時間來進行分析，由于不同數據和不同隨機情況會導致MCMC收斂過程長度不一，有一定波動。但是總體上講MCMC收斂過程會隨空間的增長收斂過程邊長，而我們的時間增長僅略高于線性增長，所以可以基本證實我們在MCMC過程中每次迭代所需的時間復雜度確實為線性。

4.2 準確性對比

由于我們的改進引入了一些啟發信息，所以可能會對我們的準確性產生影響，在這里我們對比一般方法和我們改進后的方法來分析準確性損失。在這里我們不區分學習方法是漏掉原結構邊或者錯誤找出原結構沒有的邊，以上兩種錯誤我們都認為是錯誤邊。準確率定義為1-e/E。e代表錯誤邊，E代表圖結構中的邊數。

在這里為了增加方法的準確率使用了50個初始序列，這也是隨機采樣方法中通常會使用的方法。即產生多個初始點從而產生多條馬爾科夫鏈，最終選擇評分最高的結構作為解。

表2準確率對比Tab.2 Accuracy comparison

通過對比我們發現本文的方法可以獲得很好的準確率，漏掉的邊和錯誤邊之和通常不到10%，明顯優于很多基于啟發式搜索的方法其錯誤率可能50%以上甚至更多[7]，而且相對于一般的采樣方法在精確度方面損失并不明顯。

5 結論

經過本文方法的改進，實現了在時間效率和準確率的兼顧。提供了一種基于采樣方法解決更大網絡的方法，雖然在時間效率上仍然低于啟發式搜索，但是卻提供了更為可靠的準確率和理論保障。

[1]Chickering D,Meek C,Heckerman D.Large-sample learning of Bayesian networks is NP-hard[J].Journal of Machine Learning Research,2004（5）:1287-1330.

[2]Narges Bani Asadi,Meng T H,Wong W H.Reconfigurable computing for learning Bayesian networks[C]//Proceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays,February 24-26,2008,Monterey,California,USA.

[3]Heckerman D，GeigerD，ChickeringD.LearningBayesian networks:the combination of knowledge and statistical data[J].Machine Learning,1995(20):197-243.

[4]Neapolitan R.Learning Bayesian networks[M].Prentice Hall,2003.

[5]Tsamardinos,Brown L E,Aliferis C F.The max-min hillclimbing Bayesian network structure learning algorithm[J].Machine Learning,2006,65(1):31-78.

[6]O Nikolova,S AluruParallel Bayesian network structure learning with application to gene networks[C]//High Performance Computing,Networking,Storage and Analysis(SC),2012 ieeexplore.ieee.org.

[7]Yoshinori Tamada,SeiyaImoto,Hiromitsu Araki.Estimating genome-wide gene networks using nonparametric bayesian network modelson massively parallel computersIEEE[J].ACM Transactions on Computational Biology and Bioinform-atics,2001,8(3):683-697.

Bayesian network structure learning method study

YIN Tao
（Department of Computer Science and Engineering,Shanghai Jiaotong University，Shanghai 200240，China）

For the difficulties of learning the structure of Bayesian network both high accuracy and high efficiency,we proposed an adaptive method based on Markov Chain Monte Carlo(MCMC)method.Improvements include Dependency analysis;using statistical methods to substantially reduce the sampling space,we can control the accuracy and substantial increase the time efficiency.Combined with priori knowledge;from the theoretical point,we can add priori knowledge to the score which exactly obey the posterior distribution.Search for optimal substructure;search for optimal substructure of some specific structure will get the high accuracy of learning Bayesian network rather than greedy methods.By theoretical analysis we can prove the time complexity is significantly reduced.Under the expense of the accuracy which can predict,we can reduce the time complexity from exponential linear time.Large amounts of data experiments show that the improved method has good performance both in time and accuracy.

Bayesian network structure learning;time efficiency;independence test;optimal substructure;priori knowledge；Markov Chain Monte Carlo(MCMC)

TP311

A

1674-6236（2014）17-005-04

2013-11-05 稿件編號：201311036

國家自然科學基金（61073087）

殷 陶(1988—)，男，河北石家莊人，碩士研究生。研究方向：數據分析，貝葉斯網絡等。