胡春玲，胡學鋼，呂 剛

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

一種貝葉斯網(wǎng)絡結(jié)構(gòu)學習的混合隨機抽樣算法

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

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

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

貝葉斯網(wǎng)絡；結(jié)構(gòu)學習；隨機抽樣；混合抽樣；子結(jié)構(gòu)抽樣；建議分布

1 概述

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

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

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

2 MHS抽樣算法

為了敘述方便，本文采用X={X1,X2,…,Xn}表示領(lǐng)域變量；D表示訓練數(shù)據(jù)集；Par( Xi)為網(wǎng)絡結(jié)構(gòu)s中節(jié)點Xi的父節(jié)點集。

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

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

(2)新生成的網(wǎng)絡結(jié)構(gòu)(n)s的接收概率計算公式為：

其中，P( s| D)為網(wǎng)絡結(jié)構(gòu)的評分，本文采用網(wǎng)絡結(jié)構(gòu)的BDe評分[12]，則網(wǎng)絡結(jié)構(gòu)的轉(zhuǎn)移概率為：

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

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

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

3 HSMHS抽樣算法

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

3.1 初始化

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

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

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

3.2 迭代抽樣

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

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

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

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

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

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

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

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

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

4 正確性分析

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

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

證畢。

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

證畢。

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

5 實驗與結(jié)果分析

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

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

圖1 收斂速度比較

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

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

圖2 學習精度比較

6 結(jié)束語

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

[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] 胡春玲. 貝葉斯網(wǎng)絡結(jié)構(gòu)學習及其應用研究[D]. 合肥:合肥工業(yè)大學, 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方法的概念性流域水文模型參數(shù)優(yōu)選及不確定性研究[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] 胡春玲, 胡學鋼. 一種基于隨機抽樣的貝葉斯網(wǎng)絡結(jié)構(gòu)學習算法[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

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

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

2013-02-20

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

1000-3428(2014)05-0238-05

A

TP18

·多媒體技術(shù)及應用·