基于雙尺度約束模型的BN 結構自適應學習算法

戴晶幗 任佳 董超 杜文才

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

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

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

1 問題描述

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

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

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

1) 小尺度約束模型需要隨GA 學習進程不斷調整,達到動態(tài)縮放結構搜索空間的目的;

2) GA 學習進程中若產生新個體,需要反復檢測無環(huán)性,并使用修復算子對無效結構進行無環(huán)修復,這將導致算法的時間成本增加,學習效率下降;

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

2 雙尺度約束模型

2.1 大尺度約束模型

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

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

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

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

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

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

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

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

a) 利用MI 計算每個節(jié)點與其他節(jié)點之間的依賴程度大小;

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

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

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

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

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

2.2 小尺度約束模型

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

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

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

圖2 中的結構復雜度評估函數(shù)是在BIC 評分函數(shù)的基礎上獲得的.考慮到BIC 評分函數(shù)是一種帶懲罰函數(shù)的極大似然函數(shù)評分方法[23],評分函數(shù)中的第二項能夠對BN 結構復雜度進行評估,因此可利用BIC 評分函數(shù)中的第二項對α進行動態(tài)更新.BIC 評分函數(shù)如式(4) 所示,即

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

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

a) 利用式(5) 計算當代種群中每個個體的結構復雜度penaltyk;

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

c) 利用更新后的顯著性水平αnew調整結構搜索空間.

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

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

3 基于雙尺度約束模型的BN 結構自適應學習算法

3.1 BN 結構自適應學習過程

基于雙尺度約束模型的BN 結構自適應學習算法設計思路如下:

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

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

基于雙尺度約束模型的BN 結構自適應學習算法流程如圖3 所示.

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

3.2 編碼生成

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

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

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

為了說明搜索空間中所有的BN 結構均能采用上述個體編碼方案進行表達,給出相關定理,并進行證明.

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

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

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

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

當n=2 時,命題顯然成立.假設x1是根節(jié)點,x2是葉節(jié)點,則存在節(jié)點排序為O=12,對應的上三角鄰接矩陣M=,此時顯著性水平α的取值保證節(jié)點x1與x2不是條件獨立;

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

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

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

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

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

3.3 自適應變異算子

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

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

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

式中:scorek是第k個個體所表示的BN 結構的BIC 評分,scoremin是當前種群中的最低BIC 評分,scoremax是當前種群中的最高BIC 評分.

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

3.4 其他算子

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

算法1.交叉算子

輸入.種群個體ind,交叉概率pc

輸出.交叉后的新個體new-ind

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

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

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

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

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

4 仿真實驗

4.1 實驗方案設計

4.1.1 對比實驗

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

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

4.1.2 仿真模型及實驗平臺

1) 選用三種不同規(guī)模的標準BN 模型ASIA,CAR-DIAGNOSIS2 和ALARM 對結構學習方法進行測試,驗證DSC-AL 算法對不同規(guī)模的BN 結構進行學習的性能,其中ASIA 模型為8 個節(jié)點的小規(guī)模網絡,CAR-DIAGNOSIS2 模型包含18 個節(jié)點,ALARM 模型包含37 個節(jié)點.三種模型的拓撲結構如圖5 所示;

圖5 三種標準BN 結構示意Fig.5 Three benchmark BNs

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

4.1.3 仿真實驗參數(shù)設置

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

2) 由于GA 和粒子群優(yōu)化方法的迭代尋優(yōu)過程具有很強的隨機性,為保證對比實驗能夠充分反映每種算法的性能,除K2 算法外,其他迭代優(yōu)化算法均獨立仿真運行30 次完成測試.K2 算法是一種確定性算法,其學習結果與輸入的節(jié)點順序有關.為保證公平性,在不引入先驗知識的情況下,隨機給出不同的節(jié)點序列作為K2 算法的輸入,同樣執(zhí)行30 次仿真實驗;

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

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

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

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

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

8) 對比實驗中,每種算法學習中小型網絡:ASIA 和CAR-DIAGNOSIS2 模型的最高迭代次數(shù)均為300,學習大規(guī)模網絡:ALARM 模型的最高迭代次數(shù)均為500;均采用BIC 評分準則對種群個體的適應度評估.

4.1.4 算法性能評價指標

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

2) 算法獲得的最終結構BIC 評分(BIC);

3) 算法獲得的最終結構與標準模型結構之間的漢明距離(SHD);

4) 算法運行時間(RT);

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

4.2 仿真實驗與結果分析

實驗 4.2.1 和 4.2.2 分別在1 000 組ASIA 網絡樣本數(shù)據集 (ASIA-1000) 和2 000 組CAR-DIAGNOSIS2 網絡樣本數(shù)據集(CAR-DIAGNOSIS2-2000) 下對DSC-AL 算法各功能模塊的有效性進行仿真;實驗4.2.3 分別在2 000 組和5 000 組ALARM 模型樣本數(shù)據集(ALARM-2000 和ALARM-5000) 下對DSC-AL算法的結構學習性能進行測試.

4.2.1 ASIA 模型仿真實驗

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

對表1 仿真結果的分析如下:

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

1) 在30 次的獨立仿真實驗中,DSC-AL 算法的平均結構漢明距離(SHD) 為1.3667,在7 種算法中最小.結構漢明距離越小表示算法學習到的結構越接近標準網絡結構,即證明DSC-AL 算法學習獲得結構與標準ASIA 模型結構相似度最高;

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

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

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

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

圖7 是在ASIA-1000 樣本數(shù)據下分別運行30次,6 種算法(除去K2 算法) 獲得最優(yōu)結構的BIC評分平均值隨迭代次數(shù)變化的曲線.由圖7 可知,DSC-AL 算法初始種群中的最優(yōu)結構評分相較于DGA 算法高,直至迭代終止,DSC-AL 算法最終結構的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)結構BIC 評分平均值變化曲線Fig.7 The curves of BIC scores for optimal structures on ASIA-1000 data set

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

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

4.2.2 CAR-DIAGNOSIS2 模型仿真實驗

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

對表2 仿真結果的分析如下:

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

1) 在30 次的獨立仿真實驗中,DSC-AL 算法的平均結構漢明距離(SHD) 為6.8000,該指標在7種算法中最小,表明該算法學習獲得的結構與標準CAR-DIAGNOSIS2 模型相似度最高;

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

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

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

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

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

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

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

4.2.3 ALARM 模型仿真實驗

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

對表3 仿真結果的分析如下:

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

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

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

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

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

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

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

5 結論

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