戴晶幗 任佳 董超 杜文才

貝葉斯網(wǎng)絡(luò)(Bayesian network,BN) 理論為不確定性知識的表示,節(jié)點(diǎn)間復(fù)雜關(guān)系的表達(dá)和信息融合推理提供了有效的模型框架[1-3].然而,與其他圖形化模型學(xué)習(xí)方法類似,BN 也存在研究對象節(jié)點(diǎn)增加導(dǎo)致候選結(jié)構(gòu)數(shù)量呈指數(shù)級增長的問題.因此,從大規(guī)模候選結(jié)構(gòu)集合中快速,準(zhǔn)確地獲得一個(gè)與數(shù)據(jù)樣本匹配程度最優(yōu)的結(jié)構(gòu)模型是BN 結(jié)構(gòu)學(xué)習(xí)亟待解決的問題之一.

研究人員嘗試?yán)脳l件獨(dú)立性(Conditional independence,CI) 測試度量節(jié)點(diǎn)間的依賴關(guān)系,然后構(gòu)造滿足這些依賴關(guān)系的模型結(jié)構(gòu)[4-6].但該類型學(xué)習(xí)方法運(yùn)算次數(shù)一般為節(jié)點(diǎn)個(gè)數(shù)的指數(shù)次冪,當(dāng)面對節(jié)點(diǎn)數(shù)量較多的復(fù)雜網(wǎng)絡(luò)時(shí),CI 測試效率較低.與此同時(shí),研究人員將模型先驗(yàn)信息作為約束條件,并與結(jié)構(gòu)評分函數(shù)和搜索算法組合,共同完成BN 結(jié)構(gòu)學(xué)習(xí)[7-10].但該類型方法在模型先驗(yàn)信息不準(zhǔn)確或發(fā)生錯(cuò)誤的情況下,將導(dǎo)致結(jié)構(gòu)學(xué)習(xí)結(jié)果精度低或陷入局部最優(yōu).為此,文獻(xiàn)[11]通過構(gòu)建不確定先驗(yàn)信息的評分函數(shù)并設(shè)計(jì)先驗(yàn)搜索算子,提高對錯(cuò)誤先驗(yàn)信息的適應(yīng)能力.但該方法并不能完全消除錯(cuò)誤先驗(yàn)信息對BN 結(jié)構(gòu)學(xué)習(xí)產(chǎn)生的負(fù)面影響.此外,研究人員將節(jié)點(diǎn)間依賴關(guān)系檢驗(yàn)與結(jié)構(gòu)優(yōu)化學(xué)習(xí)方法相結(jié)合,進(jìn)行無先驗(yàn)信息情況下的BN 結(jié)構(gòu)學(xué)習(xí)[12-13].在該思路下,文獻(xiàn)[14] 提出了一種混合式BN 結(jié)構(gòu)學(xué)習(xí)方法,該方法通過計(jì)算互信息量(Mutual information,MI) 構(gòu)造基于支撐樹權(quán)重矩陣的節(jié)點(diǎn)序適應(yīng)度函數(shù),利用改進(jìn)遺傳算法(Genetic algorithm,GA) 獲得節(jié)點(diǎn)排序,最后將節(jié)點(diǎn)排序作為K2 算法的輸入進(jìn)行結(jié)構(gòu)學(xué)習(xí);Wong 等和Ji 等分別將低階CI 測試引入進(jìn)化算法和蟻群優(yōu)化算法,利用CI 測試辨識部分節(jié)點(diǎn)對的獨(dú)立關(guān)系以縮小結(jié)構(gòu)搜索空間,在此基礎(chǔ)上利用評分函數(shù)和啟發(fā)式搜索以獲得BN 結(jié)構(gòu)[15-16];Li 等則提出I-GREEDY-E 算法[17],該算法首先在空圖上計(jì)算節(jié)點(diǎn)間的MI 以確定無向邊,然后利用CI 測試確定邊的指向,最后在等價(jià)類模型空間中利用貪婪搜索算法獲得BN 結(jié)構(gòu).上述學(xué)習(xí)方法在無先驗(yàn)信息的情況下實(shí)現(xiàn)了對結(jié)構(gòu)搜索空間的約束,并在約束空間內(nèi)利用搜索方法獲得了模型結(jié)構(gòu),一定程度上提高了多節(jié)點(diǎn)復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的學(xué)習(xí)效率.然而,在無先驗(yàn)信息的情況下,以CI 測試或MI 檢驗(yàn)為約束條件構(gòu)造的結(jié)構(gòu)搜索空間尺度固定,無法在結(jié)構(gòu)學(xué)習(xí)過程中動態(tài)調(diào)整結(jié)構(gòu)搜索空間的規(guī)模大小,易導(dǎo)致潛在最優(yōu)解丟失.

針對上述問題,提出基于雙尺度約束模型的BN 結(jié)構(gòu)自適應(yīng)學(xué)習(xí)算法(BN structure adaptive learning algorithm based on dual-scale constraint model,DSC-AL).該算法將最大互信息(Maximum mutual information,MMI) 和CI 測試結(jié)合建立結(jié)構(gòu)搜索空間的大尺度約束模型,限制BN 結(jié)構(gòu)搜索空間的規(guī)模,完成結(jié)構(gòu)搜索空間的初始化.借鑒GA迭代尋優(yōu)過程完成BN 結(jié)構(gòu)學(xué)習(xí).在迭代尋優(yōu)過程中建立小尺度約束模型完成搜索空間動態(tài)調(diào)整,構(gòu)建變異概率的自適應(yīng)調(diào)節(jié)函數(shù),提高GA 全局搜索能力.在實(shí)驗(yàn)仿真中,選擇了不同節(jié)點(diǎn)規(guī)模的標(biāo)準(zhǔn)BN 模型和不同樣本量對DSC-AL 算法的有效性進(jìn)行測試,并通過與Lee 等提出的基于雙重GA 編碼的BN 結(jié)構(gòu)學(xué)習(xí)算法[18]和Gheisari 等構(gòu)建的基于粒子群優(yōu)化的BN 結(jié)構(gòu)學(xué)習(xí)方法[19],以及經(jīng)典的K2算法[20]進(jìn)行性能對比,驗(yàn)證DSC-AL 算法的性能.

1 問題描述

為達(dá)到大尺度約束模型完成結(jié)構(gòu)搜索空間的初始化,小尺度約束模型實(shí)現(xiàn)結(jié)構(gòu)搜索空間動態(tài)縮放的目的,在觀測樣本驅(qū)動下,DSC-AL 算法將MI 和CI 測試相結(jié)合辨識節(jié)點(diǎn)間的依賴或獨(dú)立關(guān)系,形成限制結(jié)構(gòu)搜索空間的大尺度約束模型.然而受MI和CI 測試方法辨識精度的影響,可能導(dǎo)致結(jié)構(gòu)搜索空間約束不合理,將會出現(xiàn)以下兩種情況,即約束尺度過大將最優(yōu)結(jié)構(gòu)排除在結(jié)構(gòu)搜索空間之外,或約束尺度較小導(dǎo)致結(jié)構(gòu)搜索空間規(guī)模依然較大.因此,還需要建立小尺度約束模型完成結(jié)構(gòu)搜索空間動態(tài)縮放.DSC-AL 算法框架如圖1 所示.

圖1 DSC-AL 算法框架示意圖Fig.1 The framework of DSC-AL algorithm

根據(jù)圖1 給出的算法框架,大尺度約束模型作用于算法的初始階段,通過剔除不滿足約束條件的BN 模型限制結(jié)構(gòu)搜索空間,而小尺度約束模型針對GA 種群中的每一個(gè)個(gè)體,在迭代尋優(yōu)過程中,通過刪除不滿足約束條件的連接邊調(diào)整每個(gè)個(gè)體表示的BN 結(jié)構(gòu).DSC-AL 算法為實(shí)現(xiàn)結(jié)構(gòu)搜索空間小尺度動態(tài)縮放,降低GA 結(jié)構(gòu)尋優(yōu)過程發(fā)生早熟收斂的概率,需要解決以下三個(gè)關(guān)鍵問題:

1) 小尺度約束模型需要隨GA 學(xué)習(xí)進(jìn)程不斷調(diào)整,達(dá)到動態(tài)縮放結(jié)構(gòu)搜索空間的目的;

2) GA 學(xué)習(xí)進(jìn)程中若產(chǎn)生新個(gè)體,需要反復(fù)檢測無環(huán)性,并使用修復(fù)算子對無效結(jié)構(gòu)進(jìn)行無環(huán)修復(fù),這將導(dǎo)致算法的時(shí)間成本增加,學(xué)習(xí)效率下降;

3) GA 學(xué)習(xí)進(jìn)程需要保持種群多樣性以及減少對優(yōu)勢基因的破壞,以降低學(xué)習(xí)方法陷入局部最優(yōu)的可能性.

2 雙尺度約束模型

2.1 大尺度約束模型

包含n個(gè)節(jié)點(diǎn)的BN 可生成的結(jié)構(gòu)個(gè)數(shù)如式(1) 所示[21]:

由上式可知,BN 結(jié)構(gòu)搜索空間規(guī)模隨著節(jié)點(diǎn)個(gè)數(shù)的增加呈指數(shù)級增長.為限制BN 結(jié)構(gòu)搜索空間,利用節(jié)點(diǎn)連接邊存在性約束與節(jié)點(diǎn)連接邊缺失性約束[22]構(gòu)建大尺度約束模型.

1) 節(jié)點(diǎn)連接邊存在性約束

BN 中的節(jié)點(diǎn)x與節(jié)點(diǎn)y之間的MI 可以采用式(2) 進(jìn)行計(jì)算:

式中:r和s分別表示節(jié)點(diǎn)x與節(jié)點(diǎn)y的狀態(tài)個(gè)數(shù),ai是x的第i個(gè)可能狀態(tài)值,bj是y的第j個(gè)可能狀態(tài)值.兩個(gè)節(jié)點(diǎn)之間的MI 越大,兩者之間的依賴性越強(qiáng),即兩個(gè)節(jié)點(diǎn)間可能存在一條連接邊.

2) 節(jié)點(diǎn)連接邊缺失性約束

CI 測試在給定觀測樣本和約束集Z的基礎(chǔ)上,采用卡方檢驗(yàn)判定原假設(shè)H0:I(x,y |Z)是否成立.式(3)中統(tǒng)計(jì)量χ2服從自由度為(r－1)×(s－1)×t的分布,其中t表示約束集Z的狀態(tài)個(gè)數(shù),即

根據(jù)節(jié)點(diǎn)連接邊存在性約束與節(jié)點(diǎn)連接邊缺失性約束,主要通過以下6 個(gè)步驟構(gòu)建大尺度約束模型:

a) 利用MI 計(jì)算每個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)之間的依賴程度大小;

b) 將MI 的計(jì)算結(jié)果排序,獲取相應(yīng)的MMI,找出與各節(jié)點(diǎn)依賴程度最高的相關(guān)節(jié)點(diǎn).由于MI的對稱性,即I(x;y)=I(y;x),每個(gè)節(jié)點(diǎn)的MMI所對應(yīng)的連接邊是無向的;

c) 隨機(jī)給定連接邊指向,確定BN 結(jié)構(gòu)的節(jié)點(diǎn)順序.根據(jù)該節(jié)點(diǎn)序列,剔除搜索空間中不滿足該約束條件的候選結(jié)構(gòu),從而縮小結(jié)構(gòu)搜索空間;

d) 根據(jù)c) 獲得的節(jié)點(diǎn)序列建立相應(yīng)的鄰接矩陣,該矩陣的行序?qū)?yīng)節(jié)點(diǎn)序列.由于節(jié)點(diǎn)序列中需要滿足父節(jié)點(diǎn)排在子節(jié)點(diǎn)的前面,因此只需考慮上三角鄰接矩陣.將矩陣的上三角部分中的所有元素設(shè)置為1.然后根據(jù)以下步驟中CI 測試的結(jié)果,修改滿足條件獨(dú)立的節(jié)點(diǎn)對所對應(yīng)的矩陣元素;

e) 考慮到高階CI 測試的不可靠性且較高的計(jì)算復(fù)雜度[23],采用一階CI 測試,即|Z|=1,利用式(3) 計(jì)算鄰接矩陣中所有節(jié)點(diǎn)的卡方統(tǒng)計(jì)量,儲存每一個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)之間的CI 測試結(jié)果中對應(yīng)的最大p-值;

f) 將顯著性水平α(初始值隨機(jī)給定) 作為判斷條件獨(dú)立性的閾值.若最大p-值大于α,則兩節(jié)點(diǎn)之間無連接邊存在,因此將上三角鄰接矩陣中的元素1 修改為0.在此基礎(chǔ)上可對c) 中獲得的結(jié)構(gòu)搜索空間完成進(jìn)一步縮放.

2.2 小尺度約束模型

根據(jù)構(gòu)建大尺度約束模型的步驟f),發(fā)現(xiàn)利用CI 測試辨識節(jié)點(diǎn)獨(dú)立性關(guān)系的精度與其顯著性水平α取值相關(guān).若α取值過小,易出現(xiàn)網(wǎng)絡(luò)的部分連接邊被永久刪除,極有可能丟失潛在最優(yōu)解;若α取值過大,結(jié)構(gòu)搜索空間規(guī)模依然巨大,且候選結(jié)構(gòu)中可能存在較多錯(cuò)誤連接邊,導(dǎo)致結(jié)構(gòu)學(xué)習(xí)的效率和精度下降.因此,需要小尺度約束模型控制顯著性水平α的更新,實(shí)現(xiàn)對結(jié)構(gòu)搜索空間的動態(tài)縮放.

顯著性水平α的更新主要依賴結(jié)構(gòu)復(fù)雜度評估函數(shù)對GA 產(chǎn)生的每一代新的BN 結(jié)構(gòu)的復(fù)雜度評估.根據(jù)評估結(jié)果產(chǎn)生更新后的αnew完成結(jié)構(gòu)搜索空間的進(jìn)一步縮放,更新后的結(jié)構(gòu)搜索空間以及更新后的αnew將作用于GA 迭代搜索過程(相關(guān)內(nèi)容將在第3 節(jié)進(jìn)行介紹),小尺度約束模型工作原理如圖2 所示.

圖2 小尺度約束模型工作原理Fig.2 The working principle of small-scale constraint model

圖2 中的結(jié)構(gòu)復(fù)雜度評估函數(shù)是在BIC 評分函數(shù)的基礎(chǔ)上獲得的.考慮到BIC 評分函數(shù)是一種帶懲罰函數(shù)的極大似然函數(shù)評分方法[23],評分函數(shù)中的第二項(xiàng)能夠?qū)N 結(jié)構(gòu)復(fù)雜度進(jìn)行評估,因此可利用BIC 評分函數(shù)中的第二項(xiàng)對α進(jìn)行動態(tài)更新.BIC 評分函數(shù)如式(4) 所示,即

式中:n表示結(jié)構(gòu)中的節(jié)點(diǎn)個(gè)數(shù),qi表示節(jié)點(diǎn)xi的父節(jié)點(diǎn)集合的狀態(tài)數(shù),ri表示節(jié)點(diǎn)xi的狀態(tài)數(shù),mijk是觀測數(shù)據(jù)中滿足節(jié)點(diǎn)xi的父節(jié)點(diǎn)集合為第j個(gè)狀態(tài)且節(jié)點(diǎn)xi為第k個(gè)狀態(tài)的樣本個(gè)數(shù),是觀測數(shù)據(jù)樣本總數(shù).BIC評分的第二項(xiàng)是描述BN 結(jié)構(gòu)復(fù)雜度的懲罰函數(shù),結(jié)構(gòu)復(fù)雜度越高,相應(yīng)的懲罰函數(shù)值越大,如式(5)所示:

根據(jù)小尺度約束模型的工作原理,構(gòu)建小尺度約束模型主要通過以下3 個(gè)步驟實(shí)現(xiàn):

a) 利用式(5) 計(jì)算當(dāng)代種群中每個(gè)個(gè)體的結(jié)構(gòu)復(fù)雜度penaltyk;

b) 將上一步驟中計(jì)算得到的penaltyk與歷史最優(yōu)個(gè)體的結(jié)構(gòu)復(fù)雜度penaltybest比較;若penaltyk＜penaltybest,則選擇輸入口1;若penaltyk ＞ penaltybest,則選擇輸入口3;若penaltyk=penaltybest,則選擇輸入口2.將更新后的αnew作為種群個(gè)體CI 測試的新的顯著性水平;

c) 利用更新后的顯著性水平αnew調(diào)整結(jié)構(gòu)搜索空間.

需要說明的是,步驟b) 中根據(jù)復(fù)雜度評估結(jié)果更新α,即當(dāng)種群個(gè)體的結(jié)構(gòu)復(fù)雜度小于歷史最優(yōu)個(gè)體的結(jié)構(gòu)復(fù)雜度時(shí),需要增加該個(gè)體結(jié)構(gòu)的連接邊,減少CI 測試時(shí)滿足條件獨(dú)立性關(guān)系的節(jié)點(diǎn)對的數(shù)量,即提高顯著性水平α,因此在α更新過程中選擇輸入口1,此時(shí)αnew=α+Δα;當(dāng)種群個(gè)體的結(jié)構(gòu)復(fù)雜度大于歷史最優(yōu)個(gè)體的結(jié)構(gòu)復(fù)雜度時(shí),應(yīng)該減少結(jié)構(gòu)的連接邊數(shù)量,即降低顯著性水平α,因此在α更新過程中選擇輸入口3,此時(shí)αnew=α－Δα;若種群個(gè)體和歷史最優(yōu)個(gè)體有相同的結(jié)構(gòu)復(fù)雜度,此時(shí),α的取值保持不變,因此在α更新過程中選擇輸入口2.

在GA 迭代尋優(yōu)過程中存在新個(gè)體適應(yīng)度不及前代個(gè)體的情況.DSC-AL 算法通過聯(lián)賽選擇算子和精英保留機(jī)制將前代最優(yōu)個(gè)體直接選入下一代中進(jìn)行迭代尋優(yōu),當(dāng)代種群中的最優(yōu)個(gè)體即為歷史最優(yōu)個(gè)體.將當(dāng)代種群中每一個(gè)個(gè)體與該最優(yōu)個(gè)體的結(jié)構(gòu)復(fù)雜度進(jìn)行比較,更新顯著性水平.此外,BIC評分函數(shù)的罰項(xiàng)用于復(fù)雜度評估具有節(jié)點(diǎn)可分解性[8],以節(jié)點(diǎn)為單位將每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)復(fù)雜度用向量的方式保存.在迭代尋優(yōu)過程中通常只有少數(shù)節(jié)點(diǎn)的結(jié)構(gòu)產(chǎn)生變化,因此每次迭代只需更新個(gè)體表示的BN 結(jié)構(gòu)中少數(shù)節(jié)點(diǎn)的結(jié)構(gòu)復(fù)雜度.在動態(tài)調(diào)整顯著性水平時(shí)直接利用結(jié)構(gòu)復(fù)雜度向量中對應(yīng)元素進(jìn)行計(jì)算,可以降低計(jì)算復(fù)雜性.

3 基于雙尺度約束模型的BN 結(jié)構(gòu)自適應(yīng)學(xué)習(xí)算法

3.1 BN 結(jié)構(gòu)自適應(yīng)學(xué)習(xí)過程

基于雙尺度約束模型的BN 結(jié)構(gòu)自適應(yīng)學(xué)習(xí)算法設(shè)計(jì)思路如下:

1) 設(shè)計(jì)種群個(gè)體的編碼方案.將節(jié)點(diǎn)順序和CI測試的顯著性水平α引入種群編碼.其目的主要包含兩個(gè)方面:避免迭代尋優(yōu)過程中對新個(gè)體無環(huán)性的反復(fù)檢驗(yàn)或修復(fù)無效結(jié)構(gòu);利用雙尺度約束模型限制結(jié)構(gòu)搜索空間,提高多節(jié)點(diǎn)復(fù)雜結(jié)構(gòu)的學(xué)習(xí)精度和迭代尋優(yōu)的收斂速度.

2) 動態(tài)調(diào)節(jié)變異概率.在改進(jìn)GA 的進(jìn)化過程中,為保持種群多樣性與結(jié)構(gòu)繼承性之間的平衡,通過動態(tài)調(diào)節(jié)變異概率以提高結(jié)構(gòu)學(xué)習(xí)的收斂速度和全局尋優(yōu)能力.

基于雙尺度約束模型的BN 結(jié)構(gòu)自適應(yīng)學(xué)習(xí)算法流程如圖3 所示.

圖3 DSC-AL 算法流程圖Fig.3 The flowchart of DSC-AL algorithm

3.2 編碼生成

BN 結(jié)構(gòu)G=(X,E) 是一個(gè)有向無環(huán)圖(Directed acyclic graph,DAG).令節(jié)點(diǎn)集合X={xi}i=1,2,···,n代表領(lǐng)域變量,節(jié)點(diǎn)間的有向邊E={eij} 代表節(jié)點(diǎn)間的直接依賴關(guān)系,pa(xi) 表示節(jié)點(diǎn)xi的父節(jié)點(diǎn)集合.使用GA 完成BN 結(jié)構(gòu)學(xué)習(xí),可使用鄰接矩陣A=(eij) 對BN 結(jié)構(gòu)進(jìn)行編碼表達(dá)[24].然而隨機(jī)生成的鄰接矩陣,其對應(yīng)的結(jié)構(gòu)無法保證BN 無環(huán)要求.為此設(shè)計(jì)一種新的編碼方案以解決該問題.

新的個(gè)體編碼方案的表達(dá)式如式(6) 所示:

式(6) 中:Ci表示第i個(gè)種群個(gè)體,Oi代表BN 結(jié)構(gòu)的節(jié)點(diǎn)順序,Si代表CI 測試的顯著性水平,Mi表示根據(jù)第i個(gè)種群個(gè)體的節(jié)點(diǎn)序列構(gòu)建的上三角鄰接矩陣,其中元素取值如式(7) 所示.在節(jié)點(diǎn)順序中,每一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)都必須排在該節(jié)點(diǎn)的前面.這一原則使得遺傳算子是封閉的[25],即在進(jìn)化過程中無需檢測或修復(fù)種群個(gè)體,能夠保證產(chǎn)生的新個(gè)體是無環(huán)的.此外,將CI 測試的顯著性水平α加入個(gè)體編碼中,使得顯著性水平α隨迭代過程自適應(yīng)更新.

為了說明搜索空間中所有的BN 結(jié)構(gòu)均能采用上述個(gè)體編碼方案進(jìn)行表達(dá),給出相關(guān)定理,并進(jìn)行證明.

引理1[18].任何一個(gè)具有n+1 個(gè)節(jié)點(diǎn)的DAG都能夠被分解為一個(gè)根節(jié)點(diǎn)(或葉節(jié)點(diǎn)) 和一個(gè)具有n個(gè)節(jié)點(diǎn)的DAG 的連接.

定理1.任何一個(gè)具有n個(gè)節(jié)點(diǎn)的DAG 都能夠使用一個(gè)確定的節(jié)點(diǎn)排序和與該序列對應(yīng)的上三角鄰接矩陣以及CI 測試的顯著性水平進(jìn)行表示.

證明.由CI 測試的定義可知,顯著性水平大小決定兩節(jié)點(diǎn)之間是否存在連接邊,并且該連接邊是無向邊,因此并不影響節(jié)點(diǎn)排序.當(dāng)節(jié)點(diǎn)排序確定后,CI 測試的顯著性水平只決定該序列對應(yīng)的上三角鄰接矩陣中的元素,即條件獨(dú)立的兩節(jié)點(diǎn)對應(yīng)的矩陣元素必為0.因此,只需選擇適當(dāng)?shù)娘@著性水平保證條件獨(dú)立的節(jié)點(diǎn)對集合為DAG 中元素為0 對應(yīng)的節(jié)點(diǎn)對集合的子集.

下面用數(shù)學(xué)歸納法證明.

當(dāng)n=2 時(shí),命題顯然成立.假設(shè)x1是根節(jié)點(diǎn),x2是葉節(jié)點(diǎn),則存在節(jié)點(diǎn)排序?yàn)镺=12,對應(yīng)的上三角鄰接矩陣M=,此時(shí)顯著性水平α的取值保證節(jié)點(diǎn)x1與x2不是條件獨(dú)立;

假設(shè)命題對具有n個(gè)節(jié)點(diǎn)的DAG 成立.考慮G為任一具有n+1 個(gè)節(jié)點(diǎn)的DAG.根據(jù)引理1,G可分解為一個(gè)根節(jié)點(diǎn)(或葉節(jié)點(diǎn)) 和一個(gè)具有n個(gè)節(jié)點(diǎn)的DAG 的連接.若G分解為一個(gè)根節(jié)點(diǎn)和一個(gè)具有n個(gè)節(jié)點(diǎn)的DAGG′的連接,由假設(shè)可知,G′可由一個(gè)節(jié)點(diǎn)排序O及其對應(yīng)的上三角鄰接矩陣M和顯著性水平α表示,其中

根據(jù)顯著性水平α的取值,條件獨(dú)立的節(jié)點(diǎn)對所對應(yīng)的eij=0,即在G′中該節(jié)點(diǎn)對之間必?zé)o連接邊.若G的根節(jié)點(diǎn)為xn+1,則G的節(jié)點(diǎn)排序可表示為O′=xn+1x1x2···xn,故其對應(yīng)的上三角鄰接矩陣為

其中為1×n的矩陣,在加入根節(jié)點(diǎn)后,調(diào)整顯著性水平α的取值,使得滿足CI 測試的條件獨(dú)立關(guān)系的節(jié)點(diǎn)對集合為G中無連接邊的節(jié)點(diǎn)對集合的子集.

同理,若G分解為一個(gè)葉節(jié)點(diǎn)和一個(gè)具有n個(gè)節(jié)點(diǎn)的DAGG′′的連接,則G′′可由一個(gè)節(jié)點(diǎn)排序O及其對應(yīng)的上三角鄰接矩陣M和顯著性水平α表示,如式(8) 和式(9) 所示.若G的葉節(jié)點(diǎn)為xn+1,則G的節(jié)點(diǎn)排序可表示為O′=x1x2···xnxn+1,故其對應(yīng)的上三角鄰接矩陣為

其中為n×1 的矩陣,在加入葉節(jié)點(diǎn)后,調(diào)整顯著性水平α的取值,使得滿足CI 測試的條件獨(dú)立關(guān)系的節(jié)點(diǎn)對集合為G中無連接邊的節(jié)點(diǎn)對集合的子集.故命題對任一具有n+1 個(gè)節(jié)點(diǎn)的DAG 成立.

3.3 自適應(yīng)變異算子

GA 中變異操作的作用是保持種群的多樣性.傳統(tǒng)的GA 變異算子所使用的變異概率是一個(gè)固定值,即GA 每一代種群中的所有個(gè)體都使用相同的變異概率,無法隨GA 迭代過程發(fā)生改變.變異概率取值固定時(shí),若變異概率取值太小,在GA 迭代的中后期,種群多樣性將會急劇下降,GA 不易跳出局部極值點(diǎn);若變異概率取值過大,極易破壞種群個(gè)體的優(yōu)勢基因,從而導(dǎo)致GA 的收斂速度緩慢.為此,設(shè)計(jì)一種基于種群個(gè)體適應(yīng)度的自適應(yīng)變異算子,在GA 迭代過程中為不同階段的種群個(gè)體以及同一種群中的不同個(gè)體提供變異概率,確保種群的多樣性,克服GA 的早熟收斂.

種群個(gè)體的適應(yīng)度能夠反應(yīng)變異概率變化情況.當(dāng)種群個(gè)體適應(yīng)度逐漸趨于一致時(shí),變異概率應(yīng)該適度增大,以防止GA 迭代陷入局部最優(yōu);當(dāng)種群個(gè)體的適應(yīng)度較分散時(shí),變異概率應(yīng)該適度減小,使GA 迭代盡快收斂到全局最優(yōu)解[26].因此,可通過種群的最大適應(yīng)度fitmax和平均適應(yīng)度fitavg來描述種群適應(yīng)度的一致性,構(gòu)建的變異概率pm的自適應(yīng)調(diào)節(jié)函數(shù)如式(12) 所示.

式中:(g) 表示第g代種群中第k個(gè)個(gè)體的變異概率,為一常數(shù),01,fitk表示第k個(gè)個(gè)體的適應(yīng)度值,fitmax－fitavg的差值反映了種群適應(yīng)度的集中情況,fitk與fitavg的比較則描述了第k個(gè)個(gè)體的優(yōu)異程度.fitk的計(jì)算公式如式(13)所示:

式中:scorek是第k個(gè)個(gè)體所表示的BN 結(jié)構(gòu)的BIC 評分,scoremin是當(dāng)前種群中的最低BIC 評分,scoremax是當(dāng)前種群中的最高BIC 評分.

在獲得變異概率pm的基礎(chǔ)上,若變異位置出現(xiàn)在表示上三角鄰接矩陣的編碼部分,則該位置上的基因由0 變?yōu)? 或者由1 變?yōu)?;若變異位置出現(xiàn)在節(jié)點(diǎn)順序的編碼部分,則隨機(jī)選擇另一個(gè)節(jié)點(diǎn)與該位置上的節(jié)點(diǎn)互換.需要注意,隨機(jī)選定的個(gè)體變異位置將不包含顯著性水平α的部分,即個(gè)體中的顯著性水平α不參與變異.

3.4 其他算子

DSC-AL 算法的選擇算子采用聯(lián)賽選擇方法從當(dāng)前種群中挑選出優(yōu)良個(gè)體作為父代執(zhí)行交叉,變異操作.此外,算法使用單點(diǎn)交叉算子,具體實(shí)現(xiàn)過程如算法1 所示,其中關(guān)于交叉點(diǎn)位于種群個(gè)體編碼的第一部分,即節(jié)點(diǎn)順序的情況,圖4 給出了一個(gè)實(shí)例.

算法1.交叉算子

輸入.種群個(gè)體ind,交叉概率pc

輸出.交叉后的新個(gè)體new-ind

1) 交叉概率pc→交叉位置pos;

2)pos出現(xiàn)在ind編碼的第三部分,即顯著性水平→不交叉;

3)pos出現(xiàn)在ind編碼的第二部分,即連接邊→從pos開始的后半段交叉;

4)pos出現(xiàn)在ind編碼的第一部分,即節(jié)點(diǎn)順序→二,三部分直接互換,第一部分按照圖4 交叉.

圖4 節(jié)點(diǎn)順序交叉方法Fig.4 The crossover of node order

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)方案設(shè)計(jì)

4.1.1 對比實(shí)驗(yàn)

1) 為驗(yàn)證DSC-AL 算法中各功能模塊的有效性,選擇的對比算法如下:利用隨機(jī)初始種群替代大尺度約束模型的算法(DSC-AL+RdInit),采用固定顯著性水平替代小尺度約束模型的算法(DSCAL+FixAlp),使用固定變異概率的算法(DSC-AL+FixP) 以及在進(jìn)化過程中隨機(jī)改變顯著性水平的算法(DSC-AL+RdAlp);

2) 為驗(yàn)證DSC-AL 算法學(xué)習(xí)BN 結(jié)構(gòu)的性能,采用下列算法進(jìn)行對比實(shí)驗(yàn):Lee 利用節(jié)點(diǎn)順序和上三角鄰接矩陣提出的基于雙重GA 編碼的BN結(jié)構(gòu)學(xué)習(xí)算法(Dual genetic algorithm,DGA) 和Gheisari 等構(gòu)建的基于粒子群優(yōu)化的BN 結(jié)構(gòu)學(xué)習(xí)方法(BN construction algorithm using particle swarm optimization,BNC-PSO) 以及K2 算法.

4.1.2 仿真模型及實(shí)驗(yàn)平臺

1) 選用三種不同規(guī)模的標(biāo)準(zhǔn)BN 模型ASIA,CAR-DIAGNOSIS2 和ALARM 對結(jié)構(gòu)學(xué)習(xí)方法進(jìn)行測試,驗(yàn)證DSC-AL 算法對不同規(guī)模的BN 結(jié)構(gòu)進(jìn)行學(xué)習(xí)的性能,其中ASIA 模型為8 個(gè)節(jié)點(diǎn)的小規(guī)模網(wǎng)絡(luò),CAR-DIAGNOSIS2 模型包含18 個(gè)節(jié)點(diǎn),ALARM 模型包含37 個(gè)節(jié)點(diǎn).三種模型的拓?fù)浣Y(jié)構(gòu)如圖5 所示;

圖5 三種標(biāo)準(zhǔn)BN 結(jié)構(gòu)示意Fig.5 Three benchmark BNs

2) 實(shí)驗(yàn)平臺為Intel Core i5-5300U,2.30 GHz CPU,32 位的微機(jī),操作系統(tǒng)為Windows 7,算法程序均在MATLAB R2014a 上編譯.

4.1.3 仿真實(shí)驗(yàn)參數(shù)設(shè)置

1) 由于BN 中父節(jié)點(diǎn)集合的狀態(tài)個(gè)數(shù)隨父節(jié)點(diǎn)數(shù)量的增加呈指數(shù)級增長,為簡化算法實(shí)現(xiàn)過程,在仿真實(shí)驗(yàn)中令每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)個(gè)數(shù)不超過5 個(gè);

2) 由于GA 和粒子群優(yōu)化方法的迭代尋優(yōu)過程具有很強(qiáng)的隨機(jī)性,為保證對比實(shí)驗(yàn)?zāi)軌虺浞址从趁糠N算法的性能,除K2 算法外,其他迭代優(yōu)化算法均獨(dú)立仿真運(yùn)行30 次完成測試.K2 算法是一種確定性算法,其學(xué)習(xí)結(jié)果與輸入的節(jié)點(diǎn)順序有關(guān).為保證公平性,在不引入先驗(yàn)知識的情況下,隨機(jī)給出不同的節(jié)點(diǎn)序列作為K2 算法的輸入,同樣執(zhí)行30 次仿真實(shí)驗(yàn);

3) DSC-AL 算法的參數(shù)設(shè)置如下:種群規(guī)模為200,聯(lián)賽選擇算子中聯(lián)賽規(guī)模取4,交叉概率為0.9,變異算子中常數(shù)=0.1,小尺度約束模型中Δα=0.02;

4) DGA 的參數(shù)設(shè)置如下:種群規(guī)模為500,交叉概率為0.65,變異概率為0.05;

5) BNC-PSO 的參數(shù)設(shè)置如下:種群規(guī)模為200,其他參數(shù)與文獻(xiàn)[19] 取值相同;

6) DSC-AL+FixAlp 算法的參數(shù)設(shè)置如下:顯著性水平更新算子中α=0.05;

7) 在DSC-AL+FixP 算法中,變異概率為0.1;

8) 對比實(shí)驗(yàn)中,每種算法學(xué)習(xí)中小型網(wǎng)絡(luò):ASIA 和CAR-DIAGNOSIS2 模型的最高迭代次數(shù)均為300,學(xué)習(xí)大規(guī)模網(wǎng)絡(luò):ALARM 模型的最高迭代次數(shù)均為500;均采用BIC 評分準(zhǔn)則對種群個(gè)體的適應(yīng)度評估.

4.1.4 算法性能評價(jià)指標(biāo)

1) 初始種群中最優(yōu)結(jié)構(gòu)的BIC 評分(IBIC);

2) 算法獲得的最終結(jié)構(gòu)BIC 評分(BIC);

3) 算法獲得的最終結(jié)構(gòu)與標(biāo)準(zhǔn)模型結(jié)構(gòu)之間的漢明距離(SHD);

4) 算法運(yùn)行時(shí)間(RT);

5) 獲得最優(yōu)解的迭代次數(shù)(BG).

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

實(shí)驗(yàn) 4.2.1 和 4.2.2 分別在1 000 組ASIA 網(wǎng)絡(luò)樣本數(shù)據(jù)集 (ASIA-1000) 和2 000 組CAR-DIAGNOSIS2 網(wǎng)絡(luò)樣本數(shù)據(jù)集(CAR-DIAGNOSIS2-2000) 下對DSC-AL 算法各功能模塊的有效性進(jìn)行仿真;實(shí)驗(yàn)4.2.3 分別在2 000 組和5 000 組ALARM 模型樣本數(shù)據(jù)集(ALARM-2000 和ALARM-5000) 下對DSC-AL算法的結(jié)構(gòu)學(xué)習(xí)性能進(jìn)行測試.

4.2.1 ASIA 模型仿真實(shí)驗(yàn)

以ASIA 模型為標(biāo)準(zhǔn)結(jié)構(gòu)的仿真實(shí)驗(yàn)結(jié)果如表1 所示.表1 給出了ASIA-1000 樣本數(shù)據(jù)集下,7種BN 結(jié)構(gòu)學(xué)習(xí)算法的5 個(gè)性能指標(biāo)平均結(jié)果,即表中每種算法的性能指標(biāo)值為30 次重復(fù)實(shí)驗(yàn)的平均值,括號中的數(shù)據(jù)為標(biāo)準(zhǔn)差.在“數(shù)據(jù)集” 列中,括號中的數(shù)值為ASIA 模型對應(yīng)的BIC 評分.由于K2 算法未使用GA,因此表1 中K2 對應(yīng)的IBIC,RT 和BG 中無數(shù)據(jù).

對表1 仿真結(jié)果的分析如下:

表1 ASIA 模型下不同算法結(jié)果對比Table 1 Comparisons of different methods on ASIA network

1) 在30 次的獨(dú)立仿真實(shí)驗(yàn)中,DSC-AL 算法的平均結(jié)構(gòu)漢明距離(SHD) 為1.3667,在7 種算法中最小.結(jié)構(gòu)漢明距離越小表示算法學(xué)習(xí)到的結(jié)構(gòu)越接近標(biāo)準(zhǔn)網(wǎng)絡(luò)結(jié)構(gòu),即證明DSC-AL 算法學(xué)習(xí)獲得結(jié)構(gòu)與標(biāo)準(zhǔn)ASIA 模型結(jié)構(gòu)相似度最高;

2) DSC-AL 算法的初始種群的平均BIC 評分(IBIC) 為－2375.1,比DGA 算法(－2406.9) 和DSC-AL+RdInit 算法(－2421.9) 的分值高,與其他對比方法的IBIC 分值接近.證明利用MMI 和CI 測試構(gòu)造的大尺度約束模型對GA 種群進(jìn)行初始化,能夠有效提高初始化種群的適應(yīng)度;

3) 在相同的終止條件下,DSC-AL 算法的平均運(yùn)行時(shí)間(RT) 為103.4270 秒,比DGA 算法(173.9571 秒) 的用時(shí)短.表明DSC-AL 算法的學(xué)習(xí)效率優(yōu)于DGA 算法.相較于基于DSC-AL 算法的修改方法,DSC-AL 算法需要利用大尺度約束模型完成種群初始化操作,且在迭代尋優(yōu)過程中需要不斷自適應(yīng)調(diào)整CI 測試的顯著性水平和變異概率,因此DSC-AL 算法耗時(shí)較長;

4) DSC-AL 算法的平均結(jié)構(gòu)漢明距離(1.3667)遠(yuǎn)遠(yuǎn)小于K2 算法的平均結(jié)構(gòu)漢明距離(7.5667).表明在無先驗(yàn)知識的情況下,DSC-AL 算法的學(xué)習(xí)精度遠(yuǎn)高于K2 算法,并且不需要依賴于專家經(jīng)驗(yàn).為了清晰地對比6 種結(jié)構(gòu)學(xué)習(xí)算法(除去K2 算法) 的性能,圖6(a)～6(c) 分別描述了在ASIA-1000 樣本數(shù)據(jù)下的平均漢明距離,獲得最優(yōu)解的平均迭代次數(shù)和算法運(yùn)行的平均消耗時(shí)間.由圖6 可知,與DGA 算法相比,DSC-AL 算法能夠使用較少的迭代次數(shù)獲得最優(yōu)的BN 結(jié)構(gòu);并且相較于DSC-AL+FixP,DSC-AL+RdAlp 和DSC-AL+RdInit算法,雖然DSC-AL 算法在相同終止條件下所耗費(fèi)的時(shí)間較多,但是該算法學(xué)習(xí)到的最終結(jié)構(gòu)明顯優(yōu)于其他算法,獲得最優(yōu)解的平均迭代次數(shù)也少于其他算法.但是在小規(guī)模ASIA 模型的仿真結(jié)果中,與DSC-AL+FixAlp 算法比較,DSC-AL 算法的優(yōu)勢并不明顯.

圖6 6 種算法在ASIA-1000 數(shù)據(jù)集下的3 種性能指標(biāo)的誤差條形圖Fig.6 Error bar graph of 3 measures for 6 algorithms on ASIA-1000 data set

圖7 是在ASIA-1000 樣本數(shù)據(jù)下分別運(yùn)行30次,6 種算法(除去K2 算法) 獲得最優(yōu)結(jié)構(gòu)的BIC評分平均值隨迭代次數(shù)變化的曲線.由圖7 可知,DSC-AL 算法初始種群中的最優(yōu)結(jié)構(gòu)評分相較于DGA 算法高,直至迭代終止,DSC-AL 算法最終結(jié)構(gòu)的BIC 評分值始終高于DGA 算法,并且DSCAL 算法收斂速度比DGA 算法快.與其他修改算法對比,DSC-AL 算法的BIC 評分的平均值在迭代過程中始終高于DSC-AL+RdInit 算法,且DSC-AL 算法的收斂速度高于DSC-AL+FixP 算法和DSC-AL+RdAlp 算法,但是與DSC-AL +FixAlp 算法的趨勢及大小無明顯差異.

圖7 ASIA-1000 下最優(yōu)結(jié)構(gòu)BIC 評分平均值變化曲線Fig.7 The curves of BIC scores for optimal structures on ASIA-1000 data set

圖8 是在ASIA-1000 樣本數(shù)據(jù)下分別運(yùn)行30次,6 種算法(除去K2 算法) 獲得的優(yōu)于上一代種群的個(gè)體數(shù)平均值.由圖8 可知,每種算法在迭代尋優(yōu)過程的后期所獲得的比上一代更優(yōu)的結(jié)構(gòu)個(gè)數(shù)都趨于零.然而即使將DGA 算法的種群規(guī)模放寬至500 (遠(yuǎn)遠(yuǎn)大于DSC-AL 算法的種群規(guī)模),該算法出現(xiàn)優(yōu)于上一代種群的個(gè)體數(shù)平均值為零的情況的時(shí)間更早,即更容易陷入局部最優(yōu),發(fā)生早熟收斂.

圖8 ASIA-1000 下優(yōu)于上一代種群的個(gè)體數(shù)平均值變化曲線Fig.8 The curves of number of better individuals on ASIA-1000 data set

4.2.2 CAR-DIAGNOSIS2 模型仿真實(shí)驗(yàn)

以CAR-DIAGNOSIS2 模型為標(biāo)準(zhǔn)結(jié)構(gòu)的仿真實(shí)驗(yàn)結(jié)果如表2 所示.表2 給出了CAR-DIAGNOSIS2-2000 樣本數(shù)據(jù)集下,7 種BN結(jié)構(gòu)學(xué)習(xí)算法的5 個(gè)性能指標(biāo)平均結(jié)果,即表中每種算法的性能指標(biāo)值為30 次重復(fù)實(shí)驗(yàn)的平均值,括號中的數(shù)據(jù)為標(biāo)準(zhǔn)差.在“數(shù)據(jù)集” 列中,括號中的數(shù)值為CAR-DIAGNOSIS2 模型對應(yīng)的BIC 評分.由于K2 算法未使用GA,因此表2 中K2 對應(yīng)的IBIC,RT 和BG 中無數(shù)據(jù).

對表2 仿真結(jié)果的分析如下:

表2 CAR-DIAGNOSIS2 模型下不同算法結(jié)果對比Table 2 Comparisons of different methods on CAR-DIAGNOSIS2 network

1) 在30 次的獨(dú)立仿真實(shí)驗(yàn)中,DSC-AL 算法的平均結(jié)構(gòu)漢明距離(SHD) 為6.8000,該指標(biāo)在7種算法中最小,表明該算法學(xué)習(xí)獲得的結(jié)構(gòu)與標(biāo)準(zhǔn)CAR-DIAGNOSIS2 模型相似度最高;

2) 在相同的終止條件下,DSC-AL 算法的平均運(yùn)行時(shí)間(RT) 為520.6599 秒,比DGA 算法(856.7351 秒) 的用時(shí)短,表明DSC-AL 算法的學(xué)習(xí)效率比DGA 算法高.

圖9(a)～9(c) 分別描述了上述6 種算法(除去K2 算法) 在CAR-DIAGNOSIS2-2000 樣本數(shù)據(jù)下的平均漢明距離,獲得最優(yōu)解的平均迭代次數(shù)和算法運(yùn)行的平均消耗時(shí)間.如圖9 所示,可以獲得與ASIA 模型仿真結(jié)果所顯示的相同結(jié)論.此外,通過比較CAR-DIAGNOSIS2 模型和ASIA 模型的仿真實(shí)驗(yàn)結(jié)果,發(fā)現(xiàn)隨著網(wǎng)絡(luò)規(guī)模的增大,DSC-AL 算法的優(yōu)勢表現(xiàn)得更加明顯.

圖9 6 種算法在CAR-DIAGNOSIS2-2000 數(shù)據(jù)集下的3種性能指標(biāo)的誤差條形圖Fig.9 Error bar graph of 3 measures for 6 algorithms on CAR-DIAGNOSIS2-2000 data set

圖10 是在CAR-DIAGNOSIS2-2000 樣本數(shù)據(jù)下分別運(yùn)行30 次,6 種算法(除去K2 算法) 獲得最優(yōu)結(jié)構(gòu)的BIC 評分平均值隨迭代次數(shù)變化的曲線.由圖10 可知,與ASIA-1000 樣本數(shù)據(jù)下的仿真結(jié)果相似,與DGA 算法相比,從初始種群開始直至算法結(jié)束,DSC-AL 算法獲得的每一代的最優(yōu)結(jié)構(gòu)性能更好,并且DSC-AL 算法收斂速度更快.此外,DSC-AL+RdInit 算法和DGA 算法的初始種群中最優(yōu)結(jié)構(gòu)評分低于其他算法,即上述兩種算法的初始種群所表示的結(jié)構(gòu)最差.

圖10 CAR DIAGNOSIS2-2000 下最優(yōu)結(jié)構(gòu)BIC 評分平均值變化曲線Fig.10 The curves of BIC scores for optimal structures on CAR-DIAGNOSIS2-2000 data set

圖11 是在CAR-DIAGNOSIS2-2000 樣本數(shù)據(jù)下分別運(yùn)行30 次,6 種算法(除去K2 算法) 獲得的優(yōu)于上一代種群的個(gè)體數(shù)平均值.如圖11 所示,由于DGA 算法種群個(gè)體數(shù)為500,在迭代尋優(yōu)過程的前期和中期,該算法獲得的優(yōu)于上一代種群的個(gè)體數(shù)的平均值最高,但是到迭代的后期,與ASIA 模型仿真結(jié)果相似,DGA 算法仍然最先出現(xiàn)比上一代更優(yōu)結(jié)構(gòu)個(gè)數(shù)為零的情況.

圖11 CAR-DIAGNOSIS2-2000 下優(yōu)于上一代種群的個(gè)體數(shù)平均值變化曲線Fig.11 The curves of number of better individuals on CAR-DIAGNOSIS2-2000 data set

4.2.3 ALARM 模型仿真實(shí)驗(yàn)

前面兩小節(jié)的實(shí)驗(yàn)結(jié)果已經(jīng)驗(yàn)證DSC-AL 算法各功能模塊的有效性,為了進(jìn)一步探究DSC-AL 算法的結(jié)構(gòu)學(xué)習(xí)性能,以ALARM 模型為標(biāo)準(zhǔn)結(jié)構(gòu)進(jìn)行仿真實(shí)驗(yàn),對比三種群智能優(yōu)化算法,包括DSCAL,BNC-PSO 和DGA,結(jié)果如表3 所示.表3 分別給出了ALARM-2000 和ALARM-5000 樣本數(shù)據(jù)集下,3 種結(jié)構(gòu)學(xué)習(xí)算法的3 個(gè)性能指標(biāo)平均結(jié)果,即表中每種算法的性能指標(biāo)值為30 次重復(fù)實(shí)驗(yàn)的平均值,括號中的數(shù)據(jù)為標(biāo)準(zhǔn)差.在“數(shù)據(jù)集” 列中,括號中的數(shù)值為ALARM 模型不同數(shù)據(jù)集對應(yīng)的BIC 評分.

對表3 仿真結(jié)果的分析如下:

表3 ALARM 模型下不同算法結(jié)果對比Table 3 Comparisons of different methods on ALARM network

1) 在ALARM-2000 和ALARM-5000 兩個(gè)不同規(guī)模的數(shù)據(jù)集下,DSC-AL 算法的平均結(jié)構(gòu)漢明距離(SHD) 在3 種基于群智能優(yōu)化的BN 結(jié)構(gòu)學(xué)習(xí)算法中均最小,表明DSC-AL 算法學(xué)習(xí)獲得結(jié)構(gòu)與標(biāo)準(zhǔn)AL-ARM 模型結(jié)構(gòu)相似度最高,并且受到數(shù)據(jù)規(guī)模的影響較小;

2) 在相同的終止條件下,針對ALARM-2000和ALARM-5000 兩個(gè)不同數(shù)據(jù)集規(guī)模,結(jié)合3種學(xué)習(xí)方法獲得最優(yōu)解的平均迭代次數(shù)(GB:225.8000＜267.7778＜498.1667,203.4000＜度和迭代尋優(yōu)的收斂速度提高.與DGA 和BN315.9000＜498.3333) 和平均結(jié)構(gòu)漢明距離(SHD) 的仿真結(jié)果可知,DSC-AL 算法能夠使用最少的迭代次數(shù)獲得與標(biāo)準(zhǔn)模型最相似的結(jié)構(gòu),表明在不同規(guī)模數(shù)據(jù)集下,DSC-AL 算法的收斂速度和BN 結(jié)構(gòu)復(fù)原能力均優(yōu)于DGA 和BNC-PSO 算法.

圖12 和圖13 是3 種基于群智能方法的BN 結(jié)構(gòu)學(xué)習(xí)算法分別在ALARM-2000 和ALARM-5000樣本數(shù)據(jù)下運(yùn)行30 次獲得最優(yōu)結(jié)構(gòu)的BIC 評分平均值隨迭代次數(shù)變化的曲線.由圖12 和圖13 可知,在不同數(shù)據(jù)樣本規(guī)模下,3 種算法評分平均值隨迭代次數(shù)的變化趨勢是相似的.DSC-AL 算法初始種群中的最優(yōu)結(jié)構(gòu)評分相較于DGA 和BNC-PSO 算法高,直至迭代終止,DSC-AL 算法學(xué)習(xí)到的結(jié)構(gòu)評分值始終明顯高于DGA 算法,但與BNC-PSO 算法獲得的BN 結(jié)構(gòu)的評分值差異小;此外,DSC-AL算法收斂速度比BNC-PSO 算法快,DGA 算法在迭代終止時(shí)并沒有達(dá)到收斂狀態(tài).

圖12 ALARM-2000 下最優(yōu)結(jié)構(gòu)BIC 評分平均值變化曲線Fig.12 The curves of BIC scores for optimal structures on ALARM-2000 data set

圖13 ALARM-5000 下最優(yōu)結(jié)構(gòu)BIC 評分平均值變化曲線Fig.13 The curves of BIC scores for optimal structures on ALARM-5000 data set

仿真實(shí)驗(yàn)結(jié)果說明,在無先驗(yàn)知識的情況下,本文提出的DSC-AL 算法通過采用大小尺度約束模型和變異概率自適應(yīng)調(diào)節(jié)函數(shù),使得結(jié)構(gòu)學(xué)習(xí)的精C-PSO 兩種基于評分搜索的算法不同,DSC-AL 算法是一種混合學(xué)習(xí)方法,融合條件獨(dú)立關(guān)系檢驗(yàn)和智能優(yōu)化方法.為縮小結(jié)構(gòu)搜索空間,DSC-AL 算法采用一階CI 測試和MMI 計(jì)算結(jié)果結(jié)合,假設(shè)n為變量數(shù),在最壞的情況下算法需要進(jìn)行O(n3)次CI測試和O(n2)次MI 計(jì)算.雖然與DGA和BNC-PSO 算法比較,DSC-AL 算法在進(jìn)行迭代尋優(yōu)之前增加了大尺度約束模型過濾無效結(jié)構(gòu)的步驟,但是在后續(xù)的評分搜索階段,DSC-AL 算法利用節(jié)點(diǎn)順序設(shè)計(jì)編碼方案,使得該算法無需進(jìn)行無環(huán)檢驗(yàn),并且通過小尺度約束模型動態(tài)更新結(jié)構(gòu)搜索空間,進(jìn)一步剔除無效結(jié)構(gòu),提高迭代尋優(yōu)的搜索效率.相較于DGA 和BNC-PSO 算法,DSC-AL 算法完成BN 結(jié)構(gòu)學(xué)習(xí)任務(wù)的性能更優(yōu),并且受到數(shù)據(jù)樣本規(guī)模的影響小.

5 結(jié)論

從大規(guī)模候選結(jié)構(gòu)集合中快速,準(zhǔn)確地獲得一個(gè)與數(shù)據(jù)樣本匹配程度最優(yōu)的結(jié)構(gòu)模型是BN 結(jié)構(gòu)學(xué)習(xí)亟待解決的問題之一.為此,提出了一種基于雙尺度約束模型的BN 結(jié)構(gòu)自適應(yīng)學(xué)習(xí)(DSC-AL) 算法,解決了在無先驗(yàn)知識的情況下,通過數(shù)據(jù)樣本信息動態(tài)限制搜索空間,高效挖掘節(jié)點(diǎn)間相關(guān)性的BN結(jié)構(gòu)學(xué)習(xí)問題.該算法在MMI 和CI 測試的雙重約束條件下產(chǎn)生GA 的初始種群,獲得BIC 評分高的種群個(gè)體,加快收斂速度;通過在個(gè)體編碼中引入CI 測試的顯著性水平,DSC-AL 算法在進(jìn)化過程中利用更新模型不斷調(diào)整顯著性水平的大小,使得對應(yīng)的搜索空間動態(tài),合理地變化,提高算法的全局搜索能力;同時(shí)充分利用種群個(gè)體的適應(yīng)度分布自適應(yīng)地調(diào)節(jié)變異概率,克服算法的早熟收斂.仿真結(jié)果驗(yàn)證了本文算法對解決BN 結(jié)構(gòu)學(xué)習(xí)問題的有效性,該算法能夠確保種群個(gè)體的多樣性,提高結(jié)構(gòu)學(xué)習(xí)的精度和迭代尋優(yōu)的收斂速度.