基于飛蛾-燭火優化算法的貝葉斯網絡結構學習

,, ,

(中國科學技術大學 自動化系,合肥 230027)

0 概述

貝葉斯網絡又稱信度網絡,自1988年在文獻[1]中被提出以來,已經廣泛運用于各個領域,是不確定知識表達和推理領域最有效的理論模型之一。貝葉斯網絡的構建包含結構學習和參數學習,其中結構學習是基礎和核心,其結果直接影響參數學習。

完備數據集下的結構學習方法主要有2類:基于依賴分析的方法及基于評分搜索的方法?；谝蕾嚪治龅姆椒╗2-4]根據節點間的條件相關性,利用互信息等準則獲取貝葉斯網絡結構?；谠u分搜索的方法通過定義評分函數,利用有效的搜索算法,尋找評分最高的網絡結構。相比于前者,后者通常能夠獲取到更好的網絡結構。

采用評分搜索的方法來學習貝葉斯網絡結構是一個NP-Hard問題[5],通常用啟發式算法來解決此類問題。文獻[6]給出一種基于貪婪搜索的K2算法,算法需要預先輸入節點順序且無法進行全局搜索。文獻[7]給出了基于爬山算法(Hill Climbing,HC)的結構學習算法,通過選擇不同操作,改變網絡結構,但容易陷入局部最優。進化計算也廣泛應用于結構學習中,文獻[8]給出基于遺傳算法(Genetic Algorithm,GA)的結構學習算法,利用交叉變異算子對網絡更新迭代,取得了良好的效果。文獻[9]根據粒子群的搜索策略,結合遺傳算法交叉變異算子,給出了貝葉斯網絡結構學習算法(BNC-PSO),仿真結果表明,BNC-PSO能夠搜尋到較優的結構。蜂群算法[10]、蟻群算法[11]等進化計算方法已經應用于貝葉斯網絡結構學習中,然而存在收斂性較差、易陷入局部最優或不穩定等問題。

2015年文獻[12]給出了仿生優化算法:飛蛾燭火優化算法(Moth-flame Optimization,MFO),該算法模擬了飛蛾圍繞燭火等角螺線飛行,最終撲向燭火這一曲線運動過程,很好地平衡了解空間的全局探索和潛在最優解的局部探索,能夠快速有效地找到最優解,該算法在連續域問題求解中得到了廣泛運用[13-14]。然而,結構學習是二值離散問題,不能模擬曲線位置更新,算法無法直接運用到貝葉斯網絡結構學習中。

本文將MFO算法引入到貝葉斯網絡結構學習這一離散問題中,保留了原有MFO的排序框架,通過借鑒遺傳算法的相關操作,在變異時參考節點間互信息,解決二值離散問題中無法模擬曲線位置更新的問題,提出用于貝葉斯網絡結構學習的BN-MFO算法。

1 貝葉斯網絡及其結構學習

貝葉斯網絡N(G,θ)包含兩部分:結構矩陣G和參數θ。其中,矩陣G=〈V,E〉為有向無環圖(Directed Acyclic Graph,DAG),V={V1,V2,…,Vn}是貝葉斯網絡的節點集,E={Vk→Vl,Vi→Vj,…}則代表節點間的依賴關系,其中k,l,i,j∈[1,n];參數θ={θ1,θ2,…,θn}是一組節點的條件分布的集合,其中θi=P(Vi|π(Vi))為節點Vi的條件概率分布,若Vi沒有父節點則該分布為其邊緣分布。貝葉斯網絡結構學習問題可描述為:

OM=(D,G′,C,f)

(1)

其中,G′是V構成的所有網絡結構的集合,C是合法結構的約束條件,矩陣D是樣本數據,f是描述結構矩陣G∈G′對于數據矩陣D的匹配程度的評分函數。

結構學習的過程就是在所有符合約束條件的結構中搜索評分最優的結構,即:

(2)

其中,G|=C表示結構矩陣G滿足約束條件C。常用的評分函數f有K2評分函數[15]、BDe評分函數[16]、BIC評分函數[17]等,它們各有特點。本文采用BIC評分函數:

(3)

2 MFO算法

NP-Hard問題的啟發式求解方法一般包含兩個關鍵環節:全局搜索和局部搜索。優秀的啟發式算法能夠在兩者之間合理地平衡,提高算法性能。MFO是一種優秀的啟發式算法,成功運用在了連續優化問題的求解過程中。

MFO算法中,飛蛾是解的搜索者,燭火是當前最優解,飛蛾數量和燭火數量在初始時相同。向量Mi是矩陣M中的一行,代表一只飛蛾,其適應值在適應值矩陣OM中對應為OMi。

(4)

其中,n是飛蛾的數量,d是解的維數。算法另一重要組成部分是燭火的描述矩陣F,每一行代表一支燭火向量Fi,且其對應的適應值不劣于Fi+1的適應值,矩陣F對應的適應值矩陣為矩陣OF:

(5)

MFO將飛蛾和燭火均視為解,不同的是迭代過程中更新方式:飛蛾作為搜索的行動者,沿曲線朝著燭火進行搜索;飛蛾搜索到的解若更優,則將其標記為燭火,吸引飛蛾進行搜索。飛蛾的曲線位置更新函數如下:

Mi=Diebtcos(2πt)+Fj

(6)

其中,矩陣Mi代表第i只飛蛾,矩陣Fj代表第j支燭火,Di=|Fj-Mi|是距離,常量b決定了等角螺線形狀,t∈[-1,1]是隨機變量。

MFO人為地使每只飛蛾都繞著對應的燭火飛,即:第i只飛蛾繞著第g(i)優的燭火進行位置更新。每一輪迭代都會根據適應值對燭火進行排序,在下一輪迭代中,飛蛾再繞著對應的燭火飛。燭火的數量FN是變化的:

(7)

其中,l是當前迭代次數,N是最大燭火數,T是最大迭代次數。后期將只有一支燭火,所有飛蛾都會在最優的燭火附近飛,算法結束時返回剩下的燭火位置即為問題的最優解。

3 BN-MFO算法

3.1 初始化

本文貝葉斯網絡的結構矩陣G用鄰接矩陣A表示:

(8)

若節點Vj是Vi的子節點,則aij=1,否則aij=0。相應地,為適應結構學習問題的描述方式,重新定義矩陣M和矩陣F,如式(9)、式(10)所示。

(9)

(10)

其中,M和F分別為原算法飛蛾矩陣和燭火矩陣,Mi和Fi均為有向無環圖DAG對應的鄰接矩陣,其余定義均保持不變。需要指出的是,初始時,向量M和向量F包含完全相同的DAG,只是DAG排列不同。

初始化時,隨機生成n個合法DAG作為向量M并求出對應的適應值矩陣OM,對矩陣OM排序得到矩陣OF及其對應的向量F。初始化時,還從數據中求得節點間的互信息矩陣MI。DAG生成算法為算法1,該算法不同于一般DAG生成算法,它能夠返回一個與節點順序無關的隨機合法DAG,使得初始飛蛾在解空間中的分布更為均勻,其中隨機數k≤size(Q)。

算法1生成DAG

輸入節點個數n

輸出隨機的合法DAG對應的鄰接矩陣A

步驟1將n個節點隨機排列為隊列Q,A=0。

步驟2Q出隊節點Vx。從Q中隨機選擇k個節點為Vx的子節點。將矩陣A相應位置置1。

步驟3若Q非空,轉至步驟2。

步驟4返回矩陣A。

3.2 非法結構及其更正

本文定義貝葉斯網絡的非法結構為存在有向環的結構,如圖1所示,圖中節點2、3、5構成了有向環。除非法結構之外的其他結構都是合法結構,它們構成了飛蛾的飛行空間。當飛蛾位置非法時,需要有機制對位置進行更正,使其重新回到搜索空間。

圖1 非法結構

根據圖論知識設計了算法2實現檢測并更正,若輸入的矩陣合法則不處理,否則更正,該算法更正時能夠保持DAG的大部分結構不變。本文標記檢測更正算子為CC(Check and Correct)。

算法2DAG合法檢測及更正

輸入DAG的鄰接矩陣A

輸出保證合法的鄰接矩陣A

步驟1矩陣A的副本矩陣C,i=1。

步驟2矩陣C對角線不含非零元素,則C=C*C,i=i+1;否則轉至步驟4。

步驟3若i

步驟4隨機選擇矩陣C非零元素對應的2個節點Vx、Vy,將矩陣A中Vx、Vy對應的邊刪除或反向,將新矩陣作為輸入,遞歸調用本算法,返回值賦給矩陣A并返回矩陣A。

3.3 位置更新

貝葉斯網絡結構學習的解空間離散,MFO中的曲線移動策略無法實施。位置更新本質是繼承燭火和飛蛾的部分信息,飛蛾的下一個位置和當前位置、目標位置相關。通過借鑒遺傳算法,可以定義貝葉斯網絡結構學習問題中雜交、變異、選擇等操作,實現飛蛾的位置移動。

3.3.1 雜交操作

如圖2所示,隨機選擇飛蛾矩陣Mi和對應燭火矩陣Fg(i)的若干列進行交換,生成新的2個子代,考慮到效率問題,列數與網絡節點總數相關。該操作可能會產生非法的DAG,暫時不做處理,本文標記雜交算子為CO(Crossover)。

圖2 雜交操作

3.3.2 變異操作

在結構學習中,變異操作(如圖3所示)包含3種行為,即增加邊、刪除邊、反向邊。通常3種操作是隨機的,事實上,在貝葉斯網絡中,若節點間互信息較大,說明該對節點有較大相關性,可以認為它們之間存在有向邊[3]。在BN-MFO變異過程中,選擇若干節點對,參考對節點間的標準互信息,采取不同的操作:對于互信息值較大的節點對,若節點間有邊存在,傾向于將邊反向,若沒有邊,傾向于加邊;對于互信息較小的節點對,傾向于刪邊。同樣,選擇的節點對數和網絡節點總數相關。本文標記變異算子為V(Variation)。

圖3 變異操作

變異操作之后,需要檢查DAG的合法性,若該DAG非法,需要按照3.2節中的方法對其進行更正,保證結構合法。由于該步驟參考了節點間的互信息,這使得飛蛾更傾向飛向樣本數據的潛在結構,保證了學習結果的穩定性。

3.3.3 選擇操作

飛蛾矩陣Mi與對應的燭火矩陣Fg(i)雜交后生成2個子代矩陣ChAi、ChBi,子代經過變異、糾正之后,通過評分函數對其進行評分,選出評分較優的子代為飛蛾的下一位置,所有的子代加上全部燭火排序之后,選擇合前R優的為新的燭火,過程如圖4所示。

圖4 排序選擇框架

(11)

事實上,可以采用其他的函數關系來描述燭火數量和迭代代數的關系,不同的關系也會有不同的性能效果。

本文算法描述見算法3,算法將n只飛蛾按編號對R取余分配目標燭火,即g(i)=i%R+1;判斷是否需要淘汰飛蛾取決于當前迭代代數和飛蛾的適應值。

算法3BN-MFO

輸入數據矩陣D,飛蛾數量n,迭代次數T

輸出貝葉斯網絡結構鄰接矩陣A

步驟1初始化向量M,求對應的矩陣OM,對矩陣OM排序得到矩陣OF,根據對應關系得到向量F,求互信息矩陣MI,矩陣ChA=0、矩陣ChB=0用于放置子代。

步驟2根據式(11)更新R。

步驟3對n只飛蛾矩陣Mi均按如下流程移動位置[ChAi,ChBi] =CO(Mi,Fg(i)),ChAi=V(ChAi),ChBi=V(ChBi),ChAi=CC(ChAi),ChBi=CC(ChBi),Mi=BiggerOne(ChAi,ChBi),更新OMi。

步驟4對向量F、矩陣ChA、矩陣ChB按照適應值排序,取前R優為新的向量F,同時更新矩陣OF,根據算法1生成新飛蛾替換需要淘汰飛蛾同時更新向量M和矩陣OM;若迭代未完成,轉至步驟2。

步驟5返回向量F(此時最優燭火即為所求矩陣A)。

4 實驗及分析

4.1 實驗設置及結果

本文采用經典的8個節點Asia網和5個節點Cancer網檢驗算法的有效性。首先,對網絡進行采樣,分別獲得3個數據集。算法有效性有4個評價指標:1)反向邊數量;2)缺失邊數量;3)多余邊數量;4)求得的結構的評分。實驗中,飛蛾數量設為30只,迭代次數分別為200(Cancer)、250(Asia)。實驗對比算法為經典算法HC和同樣基于群的優化算法BNC-PSO,其粒子群數為50,迭代次數和BN-MFO相同,每個實驗均做10次,實驗結果如表1、表2所示。

表1 Cancer網絡實驗結果

表2 Asia網絡實驗結果

對于Cancer網絡BN-MFO能夠保持和HC一樣的效果,且返回的結果穩定,雖然BNC-PSO能夠返回評分最優的結構,但是每次返回的結果和標準Cancer網有較大差別。對于Asia網絡,3種算法中BN-MFO能夠找到和標準Asia網最為相近的結構,且10次實驗返回的結構基本相同、結果穩定、評分普遍優于標準Asia網;HC算法返回結構的評分有時甚至不如標準Asia網的評分優,BNC-PSO返回的結構評分普遍優于標準Asia網,但是每次返回的結構均有較大差別、不穩定。

圖5和圖6分別是BN-MFO算法在Cancer1000和Asia2000數據集下的迭代記錄,其中,粗線表示了10次實驗的平均值,細線表示單次的收斂曲線。對于Cancer網,算法在30代左右就找到了潛在結構,Asia網絡的解空間較大,找到潛在結構的迭代次數較大。

圖5 Cancer1000收斂曲線

圖6 Asia2000收斂曲線

實驗結果表明,3種算法均能學習到網絡結構的大部分結構,仍有部分結構和標準結構不同。BN-MFO返回的結果穩定且最接近標準結構;HC算法能夠快速學習出網絡結構,但是有時不能學到最優的結構;BNC-PSO普遍能夠學到評分最優的結構,但每次學到的都有較大差別,不夠穩定。

4.2 結果分析

BN-MFO保留了MFO的整體框架,從而繼承了MFO的優良性質。由于飛蛾和燭火間的動態對應關系g(i)和數量變化的燭火數量R的綜合作用,在算法初期飛蛾與對應燭火的位置距離較遠,飛蛾將有更大概率探索到更多區域,保證了全局探索性;在中期,一支燭火將會對應多只飛蛾,保證了對燭火鄰域的局部探索,后期產生的新生飛蛾也使得算法有機會發現新的潛在最優解。可見BN-MFO很好地平衡了對解空間的全局探索和局部探索。同時,在飛蛾通過雜交、變異等操作具有隨機性,使得飛蛾位置能夠較為均勻地分布;另一方面,在變異時參考節點間的互信息,使變異有更大概率向數據潛在結構發生,保障了對潛在結構的充分探索,使得返回的結構更為穩定。

3種算法均為基于評分搜索的算法,影響結果的自然是搜索的過程和評分函數,實驗已經表明,3種算法的搜索方式甚至能夠學到評分優于標準網的網絡結構,驗證了搜索過程的正確性?？梢?評分函數是導致實驗中的3種算法不能學到與原結構完全一致的結構的主要原因。BNC-PSO和BN-MFO得到的結果表明,不同的結構能夠獲得相同的BIC評分,這一現象進一步表明評分函數的選擇能夠影響結構學習的過程。

5 結束語

本文將MFO引入到貝葉斯網絡結構學習離散問題領域,借鑒遺傳算法,替換原算法的位置更新方式,在移動的過程中參考網絡節點的互信息,提出BN-MFO。該算法繼承了原算法的優良性能,同時,因為互信息的運用,保證了BN-MFO的穩定性。在標準貝葉斯網絡Cancer網和Asia網上,與經典結構學習算法及同類型結構學習算法進行實驗對比,驗證了算法的有效性和優越性。

[1] PEARL J.Probabilistic Reasoning in Intelligent Systems[J].Computer Science Artificial Intelligence,1988,70(2):1022-1027.

[2] 胡學鋼,胡春玲.一種基于依賴分析的貝葉斯網絡結構學習算法[J].模式識別與人工智能,2006,19(4):445-449.

[3] 李冰寒,高曉利,劉三陽,等.利用互信息學習貝葉斯網絡結構[J].智能系統學報,2011,6(1):68-72.

[4] SPIRTES P G C,SCHEINES R,TILLMAN R.Automated Search for Causal Relations——Theory and Practice[EB/OL].(2010-11-21).http://repository.cmu.edu/philosophy/435/.

[5] CHICKERING D M.Learning Bayesian Networks is NP-Complete[J].Networks,1996,112(2):121-130.

[6] COOPER G F,HERSKOVITS E.A Bayesian Method for the Induction of Probabilistic Networks from Data[J].Machine Learning,1992,9(4):309-347.

[7] ALCOBé J R.Incremental Hill-climbing Search Applied to Bayesian Network Structure Learning[C]//Proceedings of the 15th European Conference on Machine Learning.Pisa,Italy:Springer,2004:301-311.

[8] LARRANAGA P,KUIJPERS C M H,MURGA R H,et al.Learning Bayesian Network Structures by Searching for the Best Ordering with Genetic Algorithms[J].IEEE Transactions on Systems Man & Cybernetics Part A Systems & Humans,1996,26(4):487-493.

[9] GHEISARI S,MEYBODI M R.BNC-PSO:Structure Learning of Bayesian Networks by Particle Swarm Optimization[J].Information Sciences,2016,348:272-289.

[10] 郭 童,林 峰.基于混合差分蜂群算法的貝葉斯網絡結構學習[J].模式識別與人工智能,2014,27(6):540-545.

[11] CAMPOS L M D,FERNNDEZ-LUNA J M,GMEZ J A,et al.Ant Colony Optimization for Learning Bayesian Networks[J].International Journal of Approximate Reasoning,2002,31(3):291-311.

[12] MIRJALILI S.Moth-flame Optimization Algorithm:A Novel Nature-inspired Heuristic Paradigm[J].Knowledge-based Systems,2015,89:228-249.

[13] ALLAM D,YOUSRI D A,ETEIBA M B.Parameters Extraction of the Three Diode Model for the Multi-crystalline Solar Cell/module Using Moth-flame Optimization Algorithm[J].Energy Conversion & Management,2016,123:535-548.

[14] YAMANY W,FAWZY M,THARWAT A,et al.Moth-flame Optimization for Training Multi-layer Perceptrons[C]//Proceedings of International Computer Engineering Conference.Washington D.C.,USA:IEEE Press,2015:267-272.

[15] COOPER G F,HERSKOVITS E.A Bayesian Method for the Induction of Probabilistic Networks from Data[J].Machine Learning,1992,9(4):309-347.

[16] HECKERMAN D,DAN G,CHICKERING D M.Learning Bayesian Networks:The Combination of Knowledge and Statistical Data[J].Machine Learning,1995,20(3):197-243.

[17] LAM W,BACCHUS F.Learning Bayesian Belief Networks:An Approach Based on the MDL Principle[J].Computational Intelligence,1994,10(3):269-293.