基于V-結(jié)構(gòu)&對(duì)數(shù)似然函數(shù)定向與禁忌爬山的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)算法

劉浩然 王念太 王 毅 張力悅 蘇昭玉 劉 文 趙旭丹

①(燕山大學(xué)信息科學(xué)與工程學(xué)院 秦皇島 066004)

②(河北省特種光纖與光纖傳感重點(diǎn)實(shí)驗(yàn)室 秦皇島 066004)

③(北京市機(jī)電研究院 北京 100027)

1 引言

貝葉斯網(wǎng)絡(luò)(Bayesian Networks, BN)源于人們對(duì)人工智能領(lǐng)域不確定性問(wèn)題的研究，是進(jìn)行不確定性問(wèn)題推理和數(shù)據(jù)分析的重要工具[1]。它將有向無(wú)環(huán)圖與概率論知識(shí)相結(jié)合，既直觀揭示問(wèn)題關(guān)聯(lián)結(jié)構(gòu)又降低概率計(jì)算復(fù)雜度，在工業(yè)生產(chǎn)[2]、醫(yī)療衛(wèi)生[3]、生態(tài)學(xué)[4]、金融分析[5]等眾多領(lǐng)域得到廣泛應(yīng)用。

貝葉斯網(wǎng)絡(luò)學(xué)習(xí)分為結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí)兩部分，貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)對(duì)參數(shù)學(xué)習(xí)和推理的精度有較大影響，因此從數(shù)據(jù)中學(xué)習(xí)到精確的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)成為研究熱點(diǎn)，但從數(shù)據(jù)中學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)已被證明為非確定性多項(xiàng)式時(shí)間難題(Non-deterministic Polynomial-time hard, NP-hard)，為此，國(guó)內(nèi)外專家提出了許多貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法，其中最常見(jiàn)的是基于評(píng)分搜索的算法[6]。

爬山算法[7]是經(jīng)典的基于評(píng)分搜索的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法，其通過(guò)局部擇優(yōu)的啟發(fā)式搜索策略提高了搜索效率，但爬山算法搜索空間隨變量數(shù)量增加呈指數(shù)增長(zhǎng)和易陷入局部最優(yōu)的問(wèn)題也較為突出[8]。針對(duì)爬山算法存在的問(wèn)題，許多學(xué)者提出了不同的改進(jìn)算法，Tsamardinos等人[9]提出最大最小爬山(Max-Min Hill-Climbing, MMHC)算法，該算法利用條件獨(dú)立性構(gòu)建網(wǎng)絡(luò)的結(jié)構(gòu)框架，利用爬山搜索獲得最終網(wǎng)絡(luò)結(jié)構(gòu)，有效約束了搜索空間，但其輸出結(jié)果的質(zhì)量仍有較大提升空間；冀俊忠等人[10]提出基于禁忌搜索的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法，該算法利用禁忌搜索策略提高了算法全局尋優(yōu)能力，但并沒(méi)有解決搜索空間過(guò)大的問(wèn)題；Gámez等人[11-13]先后提出約束爬山(Constrained Hill Climbing, CHC)算法、快速約束爬山(Fast Constrained Hill Climbing, FastCHC)及其改進(jìn)算法，以上算法雖然通過(guò)動(dòng)態(tài)限制候選結(jié)構(gòu)縮小了搜索空間，但學(xué)習(xí)到的結(jié)構(gòu)準(zhǔn)確性仍有待提高；劉浩然等人[14]提出最大支撐樹(shù)(Maximum Weight Spanning Tree, MWST)與改進(jìn)爬山策略相結(jié)合的簡(jiǎn)化爬山(Simplify Hill-Climbing, SHC)算法，該算法雖然約束了搜索空間，但需要標(biāo)準(zhǔn)節(jié)點(diǎn)順序作為最大支撐樹(shù)定向條件，此外，SHC中缺少減邊操作導(dǎo)致結(jié)構(gòu)中多邊不能被消除，冗余邊過(guò)多問(wèn)題有待解決；劉彬等人[15]利用最大支撐樹(shù)約束搜索空間來(lái)提高搜索效率，利用改進(jìn)的交叉算子和變異算子替代爬山搜索中的減邊算子來(lái)擴(kuò)展全局尋優(yōu)能力，但其默認(rèn)按照標(biāo)準(zhǔn)節(jié)點(diǎn)順序?qū)ψ畲笾螛?shù)定向，且全局尋優(yōu)能力有待提高；Constantinou[16]利用擴(kuò)展最大生成圖(Extended Maximum Spanning Graph,EMSG)約束搜索空間，在評(píng)分搜索中將爬山搜索得到的結(jié)構(gòu)作為禁忌搜索策略的輸入，經(jīng)過(guò)禁忌搜索后得到最終結(jié)構(gòu)，由于爬山搜索與禁忌搜索在搜索過(guò)程中獨(dú)立進(jìn)行，仍不能解決爬山算法易陷入局部最優(yōu)的問(wèn)題。

為約束爬山算法搜索空間并提高其全局尋優(yōu)能力，本文提出基于V-結(jié)構(gòu)&對(duì)數(shù)似然函數(shù)定向與禁忌爬山的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)算法(Bayesian network structure algorithm based on V-structure & loglikelihood orientation and Tabu Hill climbing,VTH)。VTH利用定向最大支撐樹(shù)約束搜索空間，為解決最大支撐樹(shù)定向問(wèn)題，提出V-結(jié)構(gòu)與對(duì)數(shù)似然函數(shù)結(jié)合(V-structure & Log-Likelihood,VLL)的定向策略；為提高算法全局尋優(yōu)能力，提出禁忌爬山(Tabu Hill Climbing, THC)評(píng)分搜索策略，THC將禁忌表清空機(jī)制與爬山策略的局部擇優(yōu)準(zhǔn)則結(jié)合，提高全局尋優(yōu)能力的同時(shí)也能保證搜索效率。仿真實(shí)驗(yàn)結(jié)果表明，VTH算法相比于其他算法在沒(méi)有大幅增加時(shí)間開(kāi)銷的情況下提高了全局尋優(yōu)能力。

2 VTH算法研究

在VTH算法中，首先計(jì)算網(wǎng)絡(luò)節(jié)點(diǎn)間的互信息，進(jìn)而生成最大支撐樹(shù)，然后利用條件互信息與互信息的差值構(gòu)造判別參數(shù)，通過(guò)判別參數(shù)檢驗(yàn)出最大支撐樹(shù)中所有的V-結(jié)構(gòu)并定向，對(duì)剩余未定向的邊利用對(duì)數(shù)似然函數(shù)進(jìn)行定向，從而得到完全定向的最大支撐樹(shù)；以定向最大支撐樹(shù)作為初始結(jié)構(gòu)進(jìn)入爬山搜索階段，在爬山搜索達(dá)到停止條件后，以當(dāng)前最優(yōu)結(jié)構(gòu)為搜索起點(diǎn)進(jìn)入禁忌搜索階段，若此階段中搜索到更優(yōu)的結(jié)構(gòu)，則清空禁忌表，并以當(dāng)前最優(yōu)結(jié)構(gòu)為搜索起點(diǎn)再回到爬山搜索階段；否則，在禁忌表達(dá)到一定長(zhǎng)度時(shí)，停止搜索，輸出當(dāng)前最優(yōu)結(jié)構(gòu)。

2.1 VTH算法構(gòu)建

將貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)表示為有向無(wú)環(huán)圖結(jié)構(gòu)G=(V,E),V=(X1,X2,...,Xn)表示網(wǎng)絡(luò)節(jié)點(diǎn)Xi(i=1,2,...,n)的 集合，E表示網(wǎng)絡(luò)節(jié)點(diǎn)間有向邊構(gòu)成的集合[17]。設(shè)變量eij表示任意兩個(gè)節(jié)點(diǎn)Xi和Xj之間的連接關(guān)系，eij取值范圍為{?1,0,1,∞}，當(dāng)存在有向邊Xj →Xi時(shí)eij取-1，存在無(wú)向邊Xi ?Xj時(shí)eij取0，存 在 有 向 邊Xi →Xj時(shí)eij取1,Xi和Xj之間不存在邊時(shí)eij取∞，如式(1)所示

圖1 最大支撐樹(shù)中3節(jié)點(diǎn)連接關(guān)系

圖2 ep修改CG得到候選結(jié)構(gòu)

2.2 VTH算法流程圖

VTH算法流程如圖3所示。

圖3 VTH算法流程圖

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

3.1 VTH算法實(shí)驗(yàn)分析

為檢驗(yàn)VLL策略對(duì)最大支撐樹(shù)的定向效果，選取CRAE策略[24]進(jìn)行對(duì)比實(shí)驗(yàn)，利用Asia, Car,Child, Alarm 4種標(biāo)準(zhǔn)網(wǎng)絡(luò)分別生成樣本量為1000,5000, 10000的數(shù)據(jù)集，每組數(shù)據(jù)中獨(dú)立進(jìn)行100次試驗(yàn)，取均值作為最終結(jié)果。兩種策略定向結(jié)果如表1所示，其中T表示定向正確的邊數(shù)，F(xiàn)表示定向錯(cuò)誤的邊數(shù)， acc 表示定向準(zhǔn)確率，a cc通過(guò)式(24)計(jì)算

由表1可見(jiàn)，在Asia, Car和Alarm網(wǎng)絡(luò)實(shí)驗(yàn)中，VLL策略相比于CRAE策略正確定向的邊數(shù)均有提升，錯(cuò)誤定向邊數(shù)相應(yīng)減少，定向準(zhǔn)確率分別提升了35.73%, 23.58%, 31.95%。VLL策略將V-結(jié)構(gòu)與對(duì)數(shù)似然函數(shù)相結(jié)合，利用V-結(jié)構(gòu)特殊的連接形式進(jìn)行前期定向，利用對(duì)數(shù)似然函數(shù)對(duì)邊方向的評(píng)判性進(jìn)行后期定向，最終獲得了較優(yōu)的定向結(jié)果。在Child網(wǎng)絡(luò)中，由于網(wǎng)絡(luò)中V-結(jié)構(gòu)較少，VLL策略定向結(jié)果稍差，但相比于CRAE策略定向準(zhǔn)確率僅下降1.77%。

表1 4種網(wǎng)絡(luò)中VLL策略和CRAE策略定向結(jié)果

為檢驗(yàn)THC策略尋優(yōu)能力，在Asia, Car,Child和Alarm 4種標(biāo)準(zhǔn)網(wǎng)絡(luò)中，選擇樣本量為5000的數(shù)據(jù)集，每種網(wǎng)絡(luò)都從同一初始結(jié)構(gòu)出發(fā)，禁忌表最大長(zhǎng)度設(shè)置為ML=15，將THC策略與HC策略尋優(yōu)過(guò)程進(jìn)行對(duì)比，結(jié)果如圖4所示。

由圖4可見(jiàn)，在前期迭代中THC進(jìn)行爬山搜索，所以其曲線與HC的曲線重合，由于HC策略的停止條件使得其過(guò)早停止迭代，而陷入局部最優(yōu)，THC在爬山搜索不能使評(píng)分進(jìn)一步增大時(shí)，進(jìn)行禁忌搜索來(lái)試圖擺脫局部最優(yōu)狀態(tài)，由于THC策略在禁忌搜索階段允許接受劣解，所以在曲線中會(huì)有評(píng)分下降的過(guò)程，但全局最優(yōu)結(jié)構(gòu)評(píng)分有所增大，通過(guò)對(duì)比可以看出，THC策略在前期有與HC策略相同的搜索效率，在后期擁有更強(qiáng)的全局尋優(yōu)能力。此外，在Asia, Car, Child網(wǎng)絡(luò)的尋優(yōu)后期都出現(xiàn)最大評(píng)分值在較多次迭代中不變的情況，表明目前所設(shè)禁忌表長(zhǎng)度足夠大；由于Alarm網(wǎng)絡(luò)較大，尋優(yōu)后期仍有上升趨勢(shì)，但上升幅度不大，出于時(shí)間考慮不再增大禁忌表長(zhǎng)度，所以后續(xù)試驗(yàn)中ML均設(shè)為15。

圖4 HC與THC在4種網(wǎng)絡(luò)中尋優(yōu)過(guò)程對(duì)比

3.2 VTH與其他算法對(duì)比

為分析VTH算法性能，將其分別與HC算法[6]、MMHC算法[9]、Tabu算法[10]、CHC算法[11]、Fast-CHC算法[12]、SHC算法[14]和SaiyanH算法[16]進(jìn)行對(duì)比，算法介紹如表2所示。

表2 對(duì)比算法介紹

利用Asia, Car, Child和Alarm標(biāo)準(zhǔn)網(wǎng)絡(luò)分別生成1000, 5000, 10000樣本量的數(shù)據(jù)集，本算法與其他算法在不同網(wǎng)絡(luò)和數(shù)據(jù)量的條件下獨(dú)立實(shí)驗(yàn)100次，取均值作為最終結(jié)果，4種標(biāo)準(zhǔn)網(wǎng)絡(luò)中不同數(shù)據(jù)量下的運(yùn)行時(shí)間實(shí)驗(yàn)結(jié)果如圖5所示，漢明距離實(shí)驗(yàn)結(jié)果如圖6所示，F(xiàn)1值和BSF值實(shí)驗(yàn)結(jié)果如表3-表6所示。

由圖5看出，在Asia, Car, Child和Alarm網(wǎng)絡(luò)中，本算法和同樣將爬山算法與禁忌搜索結(jié)合的SaiyanH算法相比運(yùn)行時(shí)間大大降低，與HC,Tabu算法相比，在Child網(wǎng)絡(luò)中運(yùn)行時(shí)間有所增加，其余網(wǎng)絡(luò)中運(yùn)行時(shí)間均有所減少，與CHC,FastCHC算法相比用時(shí)基本持平，本算法用時(shí)減少主要得益于利用定向最大支撐樹(shù)約束搜索空間，其次是爬山算法局部擇優(yōu)特點(diǎn)與簡(jiǎn)化禁忌搜索結(jié)合的策略提高了搜索效率。相比于MMHC算法，VTH算法運(yùn)行時(shí)間有所增加。與同樣利用最大支撐樹(shù)限制搜索空間的SHC算法相比，VTH算法時(shí)間開(kāi)銷略有增加，是因?yàn)镾HC按照標(biāo)準(zhǔn)節(jié)點(diǎn)順序指定最大支撐樹(shù)邊方向(即定向與標(biāo)準(zhǔn)網(wǎng)絡(luò)相同)省去定向時(shí)間，且VTH對(duì)最大支撐樹(shù)不完全正確定向會(huì)增加后續(xù)評(píng)分搜索的運(yùn)行時(shí)間。

圖5 4個(gè)網(wǎng)絡(luò)中不同算法運(yùn)行時(shí)間結(jié)果

由圖6可以看出，在Asia, Car和Alarm網(wǎng)絡(luò)中本算法漢明距離小于其他算法，VTH在評(píng)分搜索過(guò)程中利用簡(jiǎn)化的禁忌搜索輔助爬山算法尋找全局最優(yōu)結(jié)果，有效改善了爬山算法易陷入局部最優(yōu)的問(wèn)題。由于Child網(wǎng)絡(luò)中VTH對(duì)最大支撐樹(shù)定向結(jié)果不理想，導(dǎo)致VTH漢明距離高于按照標(biāo)準(zhǔn)節(jié)點(diǎn)順序(實(shí)際中標(biāo)準(zhǔn)節(jié)點(diǎn)順序是未知的)指定最大支撐樹(shù)邊方向的SHC算法。

圖6 4個(gè)網(wǎng)絡(luò)中不同算法漢明距離結(jié)果

由表3-表6數(shù)據(jù)可知，在Asia, Car, Child和Alarm網(wǎng)絡(luò)實(shí)驗(yàn)中，VTH學(xué)習(xí)到的結(jié)果相比于HC，F(xiàn)1值平均提高43.72%, 34.55%, 21.69%,68.20%，BSF值平均提高50.79%, 27.23%, 19.74%,37.55%，相較于MMHC, Tabu, CHC, FastCHC和SaiyanH, F1值與BSF值也均有不同程度提高；VTH與按照標(biāo)準(zhǔn)節(jié)點(diǎn)順序定向最大支撐樹(shù)的SHC相比，在Asia網(wǎng)絡(luò)中F1值與BSF值分別提高4.18%, 2.58%，在Car網(wǎng)絡(luò)中F1值與BSF值分別提高15.45%, 7.64%，在Child網(wǎng)絡(luò)中F1值與BSF值分別降低2.55%, 2.27%，在Alarm網(wǎng)絡(luò)中F1值與BSF值分別提高3.25%, 2.64%。VTH在不需要任何先驗(yàn)條件的情況下，在4種網(wǎng)絡(luò)中學(xué)習(xí)到的結(jié)果要優(yōu)于多數(shù)算法，這是由于VTH在爬山搜索達(dá)到停止條件后，利用禁忌搜索以目前最優(yōu)解為基礎(chǔ)在一定步數(shù)內(nèi)進(jìn)行可接受劣解的尋優(yōu)搜索，最終增強(qiáng)了算法的全局尋優(yōu)能力。

表3 Asia網(wǎng)絡(luò)中不同算法F1值和BSF值結(jié)果

表4 Car網(wǎng)絡(luò)中不同算法F1值和BSF值結(jié)果

表5 Child網(wǎng)絡(luò)中不同算法F1值和BSF值結(jié)果

表6 Alarm網(wǎng)絡(luò)中不同算法F1值和BSF值結(jié)果

4 結(jié)束語(yǔ)

針對(duì)爬山算法搜索空間大和評(píng)分搜索過(guò)程中易陷入局部最優(yōu)問(wèn)題，本文提出基于VLL定向與禁忌爬山的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)算法，通過(guò)VLL策略定向的最大支撐樹(shù)結(jié)構(gòu)作為后續(xù)評(píng)分搜索的初始結(jié)構(gòu)，縮小了搜索空間，提高了算法效率；評(píng)分搜索策略中將禁忌表清空機(jī)制與爬山算法的局部擇優(yōu)準(zhǔn)則結(jié)合，使得算法在評(píng)分搜索過(guò)程的前期具有較高的搜索效率，搜索過(guò)程的后期具有較強(qiáng)的跨越坪區(qū)和擺脫局部最優(yōu)的能力。仿真實(shí)驗(yàn)表明，VTH算法在多數(shù)標(biāo)準(zhǔn)網(wǎng)絡(luò)的實(shí)驗(yàn)中，能夠在保證效率的同時(shí)獲得到較優(yōu)結(jié)構(gòu)，但在最大支撐樹(shù)定向不佳的網(wǎng)絡(luò)中，仍然會(huì)有運(yùn)行時(shí)間上升和陷入局部最優(yōu)的問(wèn)題，后續(xù)可用不同方式對(duì)初始結(jié)構(gòu)進(jìn)一步優(yōu)化，以提高算法效率和準(zhǔn)確性。