胡春玲，胡學(xué)鋼，呂 剛

(1. 合肥學(xué)院網(wǎng)絡(luò)與智能信息處理重點(diǎn)實(shí)驗(yàn)室，合肥 230 602；2. 合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，合肥 23000 9)

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

胡春玲1，胡學(xué)鋼2，呂 剛1

(1. 合肥學(xué)院網(wǎng)絡(luò)與智能信息處理重點(diǎn)實(shí)驗(yàn)室，合肥 230 602；2. 合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，合肥 23000 9)

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

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

1 概述

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

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

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

2 MHS抽樣算法

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

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

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

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

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

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

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

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

3 HSMHS抽樣算法

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

3.1 初始化

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

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

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

3.2 迭代抽樣

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

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

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

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

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

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

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

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

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

4 正確性分析

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

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

證畢。

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

證畢。

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

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

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

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

圖1 收斂速度比較

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

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

圖2 學(xué)習(xí)精度比較

6 結(jié)束語

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

[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)絡(luò)結(jié)構(gòu)學(xué)習(xí)及其應(yīng)用研究[D]. 合肥:合肥工業(yè)大學(xué), 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]. 杭州: 浙江大學(xué), 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] 胡春玲, 胡學(xué)鋼. 一種基于隨機(jī)抽樣的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法[J]. 2009, 計(jì)算機(jī)科學(xué), 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

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

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

2013-02-20

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

1000-3428(2014)05-0238-05

A

TP18

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