一種貝葉斯網絡結構學習的混合隨機抽樣算法

胡春玲，胡學鋼，呂 剛

(1. 合肥學院網絡與智能信息處理重點實驗室，合肥 230 602；2. 合肥工業大學計算機與信息學院，合肥 23000 9)

一種貝葉斯網絡結構學習的混合隨機抽樣算法

胡春玲1，胡學鋼2，呂 剛1

(1. 合肥學院網絡與智能信息處理重點實驗室，合肥 230 602；2. 合肥工業大學計算機與信息學院，合肥 23000 9)

貝葉斯網絡結構學習的隨機抽樣算法存在收斂速度慢的問題，為此，結合均勻抽樣和獨立抽樣，從初始樣本、抽樣方式和建議分布3個方面對抽樣過程進行改進，提出一種混合型馬爾可夫鏈蒙特卡羅抽樣算法(HSMHS)?；诠濣c之間的互信息生成網絡結構的初始樣本，在迭代抽樣階段，按一定的概率隨機選擇均勻抽樣和獨立抽樣，并根據當前抽樣的樣本總體計算獨立抽樣的建議分布，以改善抽樣過程的融合性，加快收斂速度。對算法進行正確性分析，證明其抽樣過程收斂于網絡結構的后驗概率分布，可保持較高的學習精度。在標準數據集上的實驗結果表明，HSMHS算法的學習效率和精度均高于同類算法MHS、PopMCMC 和Order-MCMC。

貝葉斯網絡；結構學習；隨機抽樣；混合抽樣；子結構抽樣；建議分布

1 概述

貝葉斯網絡模型是一種可以處理不確定性問題最有效的概率模型之一。如何從數據中學習貝葉斯網絡一直是具有挑戰性且非?；钴S的研究領域[1-2]。貝葉斯網絡的結構學習算法主要分為基于評分-搜索和基于依賴分析的學習算法[3-4]，基于評分-搜索的學習算法存在可能收斂于局部最優解的問題，而基于依賴分析的算法存在獨立性判斷困難等問題，這兩類算法都是按照所選擇的評價標準學習一個最優的貝葉斯網絡結構，而高維小樣本的數據集D本身就具有多個服從其后驗概率分布P( s| D)的網絡結構s，因此，學習一個最優網絡結構的點估計類學習算法通常不能提供可靠的學習結果。

馬爾可夫鏈蒙特卡羅(Markov Chain Monte Carlo, MCMC)方法[5-6]是一類重要的處理復雜問題的隨機抽樣方法，該方法通過構建一條收斂于目標平穩分布的馬爾可夫鏈，得到目標平穩分布的樣本，通過樣本對平穩分布的特性進行估計。MHS(Metropolis-Hasting Sampler)抽樣算法[7]是MCMC方法中常用的算法之一，文獻[8]將這一抽樣算法引入貝葉斯網絡結構學習，采用局部的弧增加、刪除和反向的均勻分布作為抽樣過程的建議分布，利用抽樣過程產生的來自目標平穩分布的網絡結構樣本來估計貝葉斯網絡的結構特征，但MHS算法存在抽樣過程融合性差、收斂速度慢的問題。為此，不同的改進算法相繼被提出[9-11]，其中具有代表性的是針對節點序抽樣的Order-MCMC算法[10]和基于樣本總體抽樣的PopMCMC抽樣算法[11]。Order-MCMC算法假設不同節點序的先驗概率服從均勻分布，符合較多節點序的網絡結構先驗概率較高，先驗概率不均勻分布會給網絡結構的后驗概率估計帶來偏差，導致學習結果的不準確。PopMCMC抽樣算法基于抽樣所得樣本總體來學習抽樣過程的建議分布，當所得的樣本總體的分布不能很好地近似網絡結構的后驗概率分布時，抽樣過程的接收率很低，收斂速度不能得到有效改善。貝葉斯網絡結構學習的MHS抽樣算法能夠較好地解決進化學習方法中由于個體趨同而產生的早熟問題，提高學習精度，但該類算法存在的收斂速度慢問題仍未能得到有效解決。初始值、建議分布和抽樣方式是影響MHS類算法抽樣過程收斂速度的重要因素。

本文通過對MHS算法的初始樣本、建議分布和抽樣方式的設計，提出一種混合型包含子結構抽樣的MHS算法(HSMHS)。首先基于節點之間的互信息在縮減的網絡結構狀態空間中生成初始樣本，然后在其迭代抽樣階段，采用混合型的抽樣算法，即按一定的概率分布，隨機選擇均勻抽樣和獨立抽樣2種抽樣算法進行抽樣，獨立抽樣的建議分布采用來自當前樣本總體的邊和子結構的后驗概率，并在獨立抽樣中增加了對網絡子結構的抽樣，以改善抽樣過程的融合性。

2 MHS抽樣算法

為了敘述方便，本文采用X={X1,X2,…,Xn}表示領域變量；D表示訓練數據集；Par( Xi)為網絡結構s中節點Xi的父節點集。

貝葉斯網絡結構學習的MHS算法的建議分布采用弧添加、刪除和反向的均勻分布作為抽樣過程的建議分布，構建一條平穩分布為網絡結構s的后驗概率分布P( s| D)的馬爾可夫鏈，然后通過收斂之后的馬爾可夫鏈抽樣產生樣本來估計待學習貝葉斯網絡的結構。MHS算法的抽樣迭代過程如下：

(1)記網絡結構的當前狀態為s(c)，采用弧添加、刪除和反向的均勻分布作為建議分布R( s(n)|s(c))，生成網絡結構的下一個狀態s(n)。

(2)新生成的網絡結構(n)s的接收概率計算公式為：

其中，P( s| D)為網絡結構的評分，本文采用網絡結構的BDe評分[12]，則網絡結構的轉移概率為：

(3)以概率A( s(n)|s(c))接收新網絡結構s(n)取代原有網絡結構s(c)；以概率1-A( s(n)|s(c ))拒絕接收新網絡結構s(n)，此時保留原有網絡結構s(c)。

(4)重復以上步驟，直到迭代過程收斂。

MHS算法的抽樣過程直觀且計算簡單，但均勻建議分布所對應的抽樣過程通常融合性差、收斂速度慢。建議分布若與s(c)無關，則對應MHS抽樣為獨立抽樣。若R( s(n)|s(c))為網絡結構的后驗概率分布P( s| D)，則抽樣過程為來自P( s| D)的獨立抽樣，此時根據式(1)計算的接收概率為1，抽樣過程對新個體的接收率較高，融合性較好，R( s(n)|s(c))若與P( s| D)的距離較遠，則獨立抽樣的抽樣效果差。網絡結構的后驗概率分布P( s| D)是學習過程的未知目標，故精確來自P( s| D)的獨立抽樣通常不可行。針對均勻抽樣和獨立抽樣各自存在的不足，本文提出一種貝葉斯網絡結構學習的混合抽樣算法(HSMHS)。

3 HSMHS抽樣算法

初始值、建議分布和抽樣方式是影響抽樣算法收斂速度的重要因素。如果初始值和目標分布的距離很小，抽樣過程的收斂速度會很快；若建議分布近似于目標平穩分布，此時的抽樣過程近似于目標平穩分布的獨立抽樣，具有較快的收斂速度。HSMHS算法通過對初始值、建議分布和抽樣方式的設計來改善抽樣過程的收斂速度。HSMHS算法首先基于節點之間的互信息，在縮減的狀態空間中進行網絡結構樣本的初始化，然后進入迭代抽樣階段；迭代抽樣階段采用按照一定的概率分布隨機選擇均勻抽樣和獨立抽樣的混合抽樣方式，其中獨立抽樣又包括弧抽樣和子結構抽樣，弧抽樣和子結構抽樣的建議分布均為當前抽樣樣本總體中弧和子結構的后驗概率估計。重復這一抽樣過程，直到構建馬爾可夫鏈收斂于目標平穩分布：網絡結構的后驗概率分布P( s| D)。

3.1 初始化

互信息度量了節點之間依賴程度[13]，如果節點之間的互信息小于給定的閾值ε，網絡中對應節點之間不存在邊。互信息的計算公式如下：

當數據集完備時，可以通過一遍掃描數據庫，得到式(3)中互信息計算所需的概率參數。

HSMHS算法根據節點之間互信息I( Xi,Xj)和預先給定的閾值ε，去掉在網絡結構中不存在的邊，減小網絡結構的搜索空間，生成網絡結構的初始樣本，該算法首先通過最大生成樹算法，生成初始樣本中一個網絡結構，然后在縮減的網絡結構狀態空間中，采用隨機生成的方法產生初始樣本中的其他網絡個體，所生成的初始樣本比完全隨機生成的樣本更加接近于該網絡結構的后驗概率分布P( s| D)。

3.2 迭代抽樣

算法HSMHS的迭代抽樣過程按照一定的概率隨機選擇獨立抽樣和均勻抽樣。均勻抽樣的建議分布為弧添加、刪除和反向的均勻分布。獨立抽樣的性能取決于所選擇的抽樣方式和建議分布。進化學習在其迭代過程中總是希望好的基因塊能夠在下一代的個體中保留下來，以減少學習過程的迭代次數，對應到網絡結構的抽樣學習算法中，就是希望評分高的網絡子結構能夠在下一代的個體中保留下來，因此，為了改善抽樣過程的融合性，HSMHS算法在其獨立抽樣過程中增加了子結構抽樣方式。獨立抽樣的建議分布等于目標平穩分布時，抽樣效果是最優的，但在實際抽樣問題中，目標平穩分布事先并不知道，事實上，只要選擇能夠較好近似于目標分布的建議分布，則根據式(1)計算的接收概率近似為1，此時獨立抽樣對于拒絕評分低的網絡結構非常有效，其抽樣過程具有較高的接收率和較好的融合性。

綜上，HSMHS算法的具體步驟如下：

(1)初始化：基于節點之間的互信息，在縮減的網絡結構狀態空間中，采用最大生成樹算法和隨機算法生成網絡結構的初始樣本(互信息閾值ε通常取值為0.001,0.05,0.1)。

(2)迭代階段：按概率(ξ， 1-ξ)隨機選擇獨立抽樣和均勻抽樣(0.1ξ0.5）≤≤。

1)若為均勻抽樣，則從當前總體中隨機選擇個體進行弧抽樣，弧抽樣的建議分布為均勻分布，按式(1)計算新個體的接收概率。

2)若為獨立抽樣，則按均勻分布進一步選擇弧抽樣和子結構抽樣：

①若為弧抽樣，則從當前總體中隨機選擇個體進行弧抽樣，弧抽樣的建議分布為按式(4)計算的當前總體中該弧后驗概率估計，按式(1)計算新個體的接收概率。

②若為子結構抽樣，則從當前總體中隨機選擇個體進行子結構抽樣，子抽樣的建議分布為按式(5)計算的當前總體中該子結構后驗概率估計，按式(1)計算新個體的接收概率。

直到算法收斂或已達到預計的迭代次數。算法執行過程中會對生成網絡結構是否滿足有向無環特性進行檢測，若網絡結構非法，則定義式(1)中P( s(n))為0。

4 正確性分析

隨機抽樣算法必須保證其抽樣過程的遍歷性和可逆性，并最終保證抽樣過程收斂于目標平穩分布。以下定理證明了HSMHS算法抽樣過程滿足可逆性，并最終收斂于網絡結構的后驗概率分布P( s| D)。

定理1HSMHS算法的抽樣過程滿足局部可逆性，即滿足：

證畢。

定理2HS MHS算法的抽樣過程收斂于網絡結構的后驗概率分布P( s| D)，即滿足：

證畢。

HSMHS算法通過對目標平穩分布抽樣產生樣本總體來學習貝葉斯網絡的結構，比學習一個最優網絡結構的學習算法具有更高的穩定性和學習精度。HSMHS算法是一種按照一定概率分布隨機選擇均勻抽樣和獨立抽樣的混合抽樣算法，其均勻抽樣有助于在最優解附近發現服從網絡結構后驗概率分布P( s| D)的網絡個體，獨立抽樣基于當前的抽樣樣本總體計算建議分布，其建議分布能較好近似于網絡結構的后驗概率分布并具有自適應性，獨立抽樣還通過子結構的抽樣來進一步改善抽樣過程的融合性，以提高抽樣過程的收斂速度。以下在標準數據集上的實驗結果驗證了HSMHS算法能有效提高其抽樣過程的收斂速度，具有良好的學習效率和學習精度。HSMHS算法采用二維數組存儲貝葉斯網絡結構，如果樣本長度為k，網絡中的節點個數為n，該算法的空間復雜度為O(kn2)。

5 實驗與結果分析

Alarm網絡(37個節點)是用來測試貝葉斯網絡學習算法的標準網絡。根據網站http://www.norsys.com提供的Alarm網概率分布表生成具有2 000個實例的訓練數據集，在針對Alarm網絡的實驗中，MHS、PopMCMC和HSMHS算法抽樣過程的迭代次數為300 00 0次，OrderMCMC是基于節點序的抽樣，一次抽樣所需時間約為基于網絡結構抽樣的10倍，對應的OrderMCMC算法迭代次數約為30 000次，抽樣過程產生的樣本大小為30，HSMHS算法中獨立抽樣的概率ξ=0.2，節點之間互信息的閾值ε=0.001。

算法的收斂速度是衡量隨機抽樣算法性能的一個重要指標，針對Alarm數據集，本文比較了HSMHS算法和同類算法MHS、PopMCMC、OrderMCMC的收斂速度。圖1是在有2 0 00條實例Alarm數據集上，HSMHS、MHS、PopMCMC和OrderMCMC算法收斂速度的比較，該圖中縱坐標表示網絡結構的BDe評分(真實Alarm網絡在該數據集上的BDe評分為–21 945)，圖中從下到上曲線分別表示算法MHS、OrderMHS、PopMCMC和HSMHS的迭代過程?？梢钥闯觯琀SMHS在迭代50 00 0次左右即收斂，其收斂速度明顯優于MHS和PopMCMC算法，一定程度上優于OrderMCMC算法，驗證了HSMHS算法在改善抽樣過程收斂速度方面所具有的優勢。

圖1 收斂速度比較

HSMHS算法的均勻抽樣采用均勻分布作為建議分布，有助于從目標分布附近去發現屬于目標分布的個體；HSMHS算法的獨立抽樣在保證抽樣過程收斂性的前提下其建議分布能夠越來越好地近似于目標分布，抽樣過程具有自適應性，結合子結構的抽樣方式可改善抽樣過程的接收率和融合性，因而可提高抽樣過程的收斂速度。

受試者工作特性(Receiver Operating Characteristic, ROC)曲線是以真陽性率(靈敏度)為縱坐標，假陽性率(1-特異度)為橫坐標繪制的曲線，曲線下方的面積表示結構學習算法的學習精度，面積越大，學習的精度就越高。圖2是MHS、PopMCMC、OrderMCMC和HSMHS算法針對2 000個實例的Alarm數據集，在300 000迭代過程結束后的ROC曲線比較，其中HSMHS和PopMCMC算法迭代過程結束后所產生樣本的ROC曲線，而MHS 算法取其迭代過程最后產生的30個個體的ROC曲線，OrderMCMC算法取其迭代過程最后產生的30個個體的對應網絡結構的ROC曲線，該圖中算法名下的數值對應于不同ROC曲線下的面積，代表相應算法的學習精度，可以看出，HSMHS算法的學習精度最高。

圖2 學習精度比較

6 結束語

隨機抽樣算法具有良好的學習精度，但面臨著抽樣過程收斂速度慢的問題。本文提出的HSMHS算法從初始樣本、抽樣方式和建議分布3個方面對MHS抽樣算法進行改進，以提高抽樣的收斂速度。HSMHS算法的抽樣過程能夠收斂于網絡結構的后驗概率分布，因而具有良好的學習精度，在標準數據集上的實驗結果也證明了該算法的有效性。針對高維小樣本的生物信息數據，后續工作將圍繞如何有效地將HSMHS算法應用于基因調控網絡的建模。

[1] Chickering D M, Heckerman D, Meek C. Large-sample Learning of Bayesian Networks is NP-Hard[J]. Machine Learning Research, 2004, 5(1): 1287-1330.

[2] Acid S, de Campos L M, Fernández M. Score-based Methods for Learning Markov Bundaries by Searching in Constrained Spaces[J]. Data Mining and Knowledge Discov ery, 2 013, 26(1): 174-212.

[3] Wong M L, Leung K S. An Efficient Data Mining Method for Learning Bayesian Networks Using an Evolutionary Algorithmbased Hybrid Approach[J]. IEEE Transactions on Evolu tionary Computation, 2004, 8(4): 378-404.

[4] 胡春玲. 貝葉斯網絡結構學習及其應用研究[D]. 合肥:合肥工業大學, 2011.

[5] Soliman A A, Abd-Ellah A H, Abou-Elheggag N A. Modified Weibull Model: A Bayes Study Using M CMC Approa ch Based on Progressive Censoring Data[J]. Reliability Engineering & System Safety, 2012, 100(4): 48-57.

[6] 曹飛鳳. 基于MCMC方法的概念性流域水文模型參數優選及不確定性研究[D]. 杭州: 浙江大學, 2010.

[7] Hou Yunshan, Huang Jianguo, Jin Yong. Fast Algorithm for Bayesian DOA Estimator Based on Metropol is-Hastings Sampling[J]. Journal of System Simulation, 2009, 21(19): 6033-6072.

[8] Madigan D, York J. Bayesian Graphical Models for Discrete Data[J]. International Statisti cal Review, 19 95, 6 3(2): 215-232.

[9] 胡春玲, 胡學鋼. 一種基于隨機抽樣的貝葉斯網絡結構學習算法[J]. 2009, 計算機科學, 36(2): 199-202.

[10] Friedman N, Koller D. Being Bay esian About Network Structure: A Ba yesian Ap proach to Structure Discovery in Bayesian Networks[J]. Machine L earning, 2003, 50(1/2): 95-125.

[11] Myers J W. Population Markov Chain Monte Carlo[J]. Machine Learning, 2003, 50(1/2): 175-196.

[12] Heckerman D, Geiger D, Chickering D M. Learning Bayesian Networks: The Combination of Knowledge and Statistical Data[J]. Machine Learning, 1995, 20(3): 197-243.

[13] Cheng J, Greiner R, Kelly J. Learning Bayesian Networks from Data: An Efficient Information-t heory Based Approach[J]. Artificial Intelligence, 2002, 137(1/2): 43-90.

編輯 金胡考

A Hybrid Stochastic Sampling Algorithm for Bayesian Network Structure Learning

HU Chun-ling1, HU Xue-gang2, LV Gang1

(1. Key Laboratory of Network and Intelligent Information Processing, Hefei University, Hefei 230602, China; 2. School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

According to slow convergence speed of stochastic sampling algorithm, based on uniform sampler and independent sampler, by improving convergence speed from the initial sample, sampling method and proposal distribution, a hybrid markov chain Monte Carlo sampling algorithm(HSMHS) is put forward in this paper. Based on mutual information between network nodes, it generates initial samples of network structure. In iteration sampling phase, according to certain probability distribut ion, it randomly selects un iform sampler or independent sampler, and computs proposal distribution of independent sampler based on the current samples to improve the mixing of sampling process. It can be proved that sampling process of HSM HS converges to the posterior probability of network structure, and the algorithm has a good learning accuracy. Experimental results on standard data set also verify that both l earning efficiency and precision of HSMHS outperform classical algorithms MHS, PopMCMC and Order-MCMC.

Bayesian network; structure learning; stochastic sampling; hybrid sampling; sub-structure sampling; proposal distribution

10.3969/j.issn.1000-3428.2014.05.049

國家自然科學基金資助項目“基于協同訓練策略的不完全標記數據流分類問題研究”(61273292)；安徽省自然科學基金資助項目“面向若干復雜場景的水平集圖像分割關鍵技術研究”(1308085MF84)；合肥學院人才基金資助項目“基于多數據源和概率圖模型的基因調控網絡建模與分析研究”(1308085MF84)。

胡春玲(1970－)，女，副教授、博士，主研方向：貝葉斯網絡，數據挖掘；胡學鋼，教授、博士、博士生導師；呂 剛，副教授、碩士。

2013-02-20

2013-05-17E-mail：huchunling8787@aliyun.com

1000-3428(2014)05-0238-05

A

TP18

·多媒體技術及應用·