,, ,
(中國科學(xué)技術(shù)大學(xué) 自動化系,合肥 230027)
貝葉斯網(wǎng)絡(luò)又稱信度網(wǎng)絡(luò),自1988年在文獻[1]中被提出以來,已經(jīng)廣泛運用于各個領(lǐng)域,是不確定知識表達和推理領(lǐng)域最有效的理論模型之一。貝葉斯網(wǎng)絡(luò)的構(gòu)建包含結(jié)構(gòu)學(xué)習和參數(shù)學(xué)習,其中結(jié)構(gòu)學(xué)習是基礎(chǔ)和核心,其結(jié)果直接影響參數(shù)學(xué)習。
完備數(shù)據(jù)集下的結(jié)構(gòu)學(xué)習方法主要有2類:基于依賴分析的方法及基于評分搜索的方法?;谝蕾嚪治龅姆椒╗2-4]根據(jù)節(jié)點間的條件相關(guān)性,利用互信息等準則獲取貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)?;谠u分搜索的方法通過定義評分函數(shù),利用有效的搜索算法,尋找評分最高的網(wǎng)絡(luò)結(jié)構(gòu)。相比于前者,后者通常能夠獲取到更好的網(wǎng)絡(luò)結(jié)構(gòu)。
采用評分搜索的方法來學(xué)習貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)是一個NP-Hard問題[5],通常用啟發(fā)式算法來解決此類問題。文獻[6]給出一種基于貪婪搜索的K2算法,算法需要預(yù)先輸入節(jié)點順序且無法進行全局搜索。文獻[7]給出了基于爬山算法(Hill Climbing,HC)的結(jié)構(gòu)學(xué)習算法,通過選擇不同操作,改變網(wǎng)絡(luò)結(jié)構(gòu),但容易陷入局部最優(yōu)。進化計算也廣泛應(yīng)用于結(jié)構(gòu)學(xué)習中,文獻[8]給出基于遺傳算法(Genetic Algorithm,GA)的結(jié)構(gòu)學(xué)習算法,利用交叉變異算子對網(wǎng)絡(luò)更新迭代,取得了良好的效果。文獻[9]根據(jù)粒子群的搜索策略,結(jié)合遺傳算法交叉變異算子,給出了貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習算法(BNC-PSO),仿真結(jié)果表明,BNC-PSO能夠搜尋到較優(yōu)的結(jié)構(gòu)。蜂群算法[10]、蟻群算法[11]等進化計算方法已經(jīng)應(yīng)用于貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習中,然而存在收斂性較差、易陷入局部最優(yōu)或不穩(wěn)定等問題。
2015年文獻[12]給出了仿生優(yōu)化算法:飛蛾燭火優(yōu)化算法(Moth-flame Optimization,MFO),該算法模擬了飛蛾圍繞燭火等角螺線飛行,最終撲向燭火這一曲線運動過程,很好地平衡了解空間的全局探索和潛在最優(yōu)解的局部探索,能夠快速有效地找到最優(yōu)解,該算法在連續(xù)域問題求解中得到了廣泛運用[13-14]。然而,結(jié)構(gòu)學(xué)習是二值離散問題,不能模擬曲線位置更新,算法無法直接運用到貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習中。
本文將MFO算法引入到貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習這一離散問題中,保留了原有MFO的排序框架,通過借鑒遺傳算法的相關(guān)操作,在變異時參考節(jié)點間互信息,解決二值離散問題中無法模擬曲線位置更新的問題,提出用于貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習的BN-MFO算法。
貝葉斯網(wǎng)絡(luò)N(G,θ)包含兩部分:結(jié)構(gòu)矩陣G和參數(shù)θ。其中,矩陣G=〈V,E〉為有向無環(huán)圖(Directed Acyclic Graph,DAG),V={V1,V2,…,Vn}是貝葉斯網(wǎng)絡(luò)的節(jié)點集,E={Vk→Vl,Vi→Vj,…}則代表節(jié)點間的依賴關(guān)系,其中k,l,i,j∈[1,n];參數(shù)θ={θ1,θ2,…,θn}是一組節(jié)點的條件分布的集合,其中θi=P(Vi|π(Vi))為節(jié)點Vi的條件概率分布,若Vi沒有父節(jié)點則該分布為其邊緣分布。貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習問題可描述為:
OM=(D,G′,C,f)
(1)
其中,G′是V構(gòu)成的所有網(wǎng)絡(luò)結(jié)構(gòu)的集合,C是合法結(jié)構(gòu)的約束條件,矩陣D是樣本數(shù)據(jù),f是描述結(jié)構(gòu)矩陣G∈G′對于數(shù)據(jù)矩陣D的匹配程度的評分函數(shù)。
結(jié)構(gòu)學(xué)習的過程就是在所有符合約束條件的結(jié)構(gòu)中搜索評分最優(yōu)的結(jié)構(gòu),即:
(2)
其中,G|=C表示結(jié)構(gòu)矩陣G滿足約束條件C。常用的評分函數(shù)f有K2評分函數(shù)[15]、BDe評分函數(shù)[16]、BIC評分函數(shù)[17]等,它們各有特點。本文采用BIC評分函數(shù):
(3)
NP-Hard問題的啟發(fā)式求解方法一般包含兩個關(guān)鍵環(huán)節(jié):全局搜索和局部搜索。優(yōu)秀的啟發(fā)式算法能夠在兩者之間合理地平衡,提高算法性能。MFO是一種優(yōu)秀的啟發(fā)式算法,成功運用在了連續(xù)優(yōu)化問題的求解過程中。
MFO算法中,飛蛾是解的搜索者,燭火是當前最優(yōu)解,飛蛾數(shù)量和燭火數(shù)量在初始時相同。向量Mi是矩陣M中的一行,代表一只飛蛾,其適應(yīng)值在適應(yīng)值矩陣OM中對應(yīng)為OMi。
(4)
其中,n是飛蛾的數(shù)量,d是解的維數(shù)。算法另一重要組成部分是燭火的描述矩陣F,每一行代表一支燭火向量Fi,且其對應(yīng)的適應(yīng)值不劣于Fi+1的適應(yīng)值,矩陣F對應(yīng)的適應(yīng)值矩陣為矩陣OF:
(5)
MFO將飛蛾和燭火均視為解,不同的是迭代過程中更新方式:飛蛾作為搜索的行動者,沿曲線朝著燭火進行搜索;飛蛾搜索到的解若更優(yōu),則將其標記為燭火,吸引飛蛾進行搜索。飛蛾的曲線位置更新函數(shù)如下:
Mi=Diebtcos(2πt)+Fj
(6)
其中,矩陣Mi代表第i只飛蛾,矩陣Fj代表第j支燭火,Di=|Fj-Mi|是距離,常量b決定了等角螺線形狀,t∈[-1,1]是隨機變量。
MFO人為地使每只飛蛾都繞著對應(yīng)的燭火飛,即:第i只飛蛾繞著第g(i)優(yōu)的燭火進行位置更新。每一輪迭代都會根據(jù)適應(yīng)值對燭火進行排序,在下一輪迭代中,飛蛾再繞著對應(yīng)的燭火飛。燭火的數(shù)量FN是變化的:
(7)
其中,l是當前迭代次數(shù),N是最大燭火數(shù),T是最大迭代次數(shù)。后期將只有一支燭火,所有飛蛾都會在最優(yōu)的燭火附近飛,算法結(jié)束時返回剩下的燭火位置即為問題的最優(yōu)解。
本文貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)矩陣G用鄰接矩陣A表示:
(8)
若節(jié)點Vj是Vi的子節(jié)點,則aij=1,否則aij=0。相應(yīng)地,為適應(yīng)結(jié)構(gòu)學(xué)習問題的描述方式,重新定義矩陣M和矩陣F,如式(9)、式(10)所示。
(9)
(10)
其中,M和F分別為原算法飛蛾矩陣和燭火矩陣,Mi和Fi均為有向無環(huán)圖DAG對應(yīng)的鄰接矩陣,其余定義均保持不變。需要指出的是,初始時,向量M和向量F包含完全相同的DAG,只是DAG排列不同。
初始化時,隨機生成n個合法DAG作為向量M并求出對應(yīng)的適應(yīng)值矩陣OM,對矩陣OM排序得到矩陣OF及其對應(yīng)的向量F。初始化時,還從數(shù)據(jù)中求得節(jié)點間的互信息矩陣MI。DAG生成算法為算法1,該算法不同于一般DAG生成算法,它能夠返回一個與節(jié)點順序無關(guān)的隨機合法DAG,使得初始飛蛾在解空間中的分布更為均勻,其中隨機數(shù)k≤size(Q)。
算法1生成DAG
輸入節(jié)點個數(shù)n
輸出隨機的合法DAG對應(yīng)的鄰接矩陣A
步驟1將n個節(jié)點隨機排列為隊列Q,A=0。
步驟2Q出隊節(jié)點Vx。從Q中隨機選擇k個節(jié)點為Vx的子節(jié)點。將矩陣A相應(yīng)位置置1。
步驟3若Q非空,轉(zhuǎn)至步驟2。
步驟4返回矩陣A。
本文定義貝葉斯網(wǎng)絡(luò)的非法結(jié)構(gòu)為存在有向環(huán)的結(jié)構(gòu),如圖1所示,圖中節(jié)點2、3、5構(gòu)成了有向環(huán)。除非法結(jié)構(gòu)之外的其他結(jié)構(gòu)都是合法結(jié)構(gòu),它們構(gòu)成了飛蛾的飛行空間。當飛蛾位置非法時,需要有機制對位置進行更正,使其重新回到搜索空間。
圖1 非法結(jié)構(gòu)
根據(jù)圖論知識設(shè)計了算法2實現(xiàn)檢測并更正,若輸入的矩陣合法則不處理,否則更正,該算法更正時能夠保持DAG的大部分結(jié)構(gòu)不變。本文標記檢測更正算子為CC(Check and Correct)。
算法2DAG合法檢測及更正
輸入DAG的鄰接矩陣A
輸出保證合法的鄰接矩陣A
步驟1矩陣A的副本矩陣C,i=1。
步驟2矩陣C對角線不含非零元素,則C=C*C,i=i+1;否則轉(zhuǎn)至步驟4。
步驟3若i 步驟4隨機選擇矩陣C非零元素對應(yīng)的2個節(jié)點Vx、Vy,將矩陣A中Vx、Vy對應(yīng)的邊刪除或反向,將新矩陣作為輸入,遞歸調(diào)用本算法,返回值賦給矩陣A并返回矩陣A。 貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習的解空間離散,MFO中的曲線移動策略無法實施。位置更新本質(zhì)是繼承燭火和飛蛾的部分信息,飛蛾的下一個位置和當前位置、目標位置相關(guān)。通過借鑒遺傳算法,可以定義貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習問題中雜交、變異、選擇等操作,實現(xiàn)飛蛾的位置移動。 3.3.1 雜交操作 如圖2所示,隨機選擇飛蛾矩陣Mi和對應(yīng)燭火矩陣Fg(i)的若干列進行交換,生成新的2個子代,考慮到效率問題,列數(shù)與網(wǎng)絡(luò)節(jié)點總數(shù)相關(guān)。該操作可能會產(chǎn)生非法的DAG,暫時不做處理,本文標記雜交算子為CO(Crossover)。 圖2 雜交操作 3.3.2 變異操作 在結(jié)構(gòu)學(xué)習中,變異操作(如圖3所示)包含3種行為,即增加邊、刪除邊、反向邊。通常3種操作是隨機的,事實上,在貝葉斯網(wǎng)絡(luò)中,若節(jié)點間互信息較大,說明該對節(jié)點有較大相關(guān)性,可以認為它們之間存在有向邊[3]。在BN-MFO變異過程中,選擇若干節(jié)點對,參考對節(jié)點間的標準互信息,采取不同的操作:對于互信息值較大的節(jié)點對,若節(jié)點間有邊存在,傾向于將邊反向,若沒有邊,傾向于加邊;對于互信息較小的節(jié)點對,傾向于刪邊。同樣,選擇的節(jié)點對數(shù)和網(wǎng)絡(luò)節(jié)點總數(shù)相關(guān)。本文標記變異算子為V(Variation)。 圖3 變異操作 變異操作之后,需要檢查DAG的合法性,若該DAG非法,需要按照3.2節(jié)中的方法對其進行更正,保證結(jié)構(gòu)合法。由于該步驟參考了節(jié)點間的互信息,這使得飛蛾更傾向飛向樣本數(shù)據(jù)的潛在結(jié)構(gòu),保證了學(xué)習結(jié)果的穩(wěn)定性。 3.3.3 選擇操作 飛蛾矩陣Mi與對應(yīng)的燭火矩陣Fg(i)雜交后生成2個子代矩陣ChAi、ChBi,子代經(jīng)過變異、糾正之后,通過評分函數(shù)對其進行評分,選出評分較優(yōu)的子代為飛蛾的下一位置,所有的子代加上全部燭火排序之后,選擇合前R優(yōu)的為新的燭火,過程如圖4所示。 圖4 排序選擇框架 (11) 事實上,可以采用其他的函數(shù)關(guān)系來描述燭火數(shù)量和迭代代數(shù)的關(guān)系,不同的關(guān)系也會有不同的性能效果。 本文算法描述見算法3,算法將n只飛蛾按編號對R取余分配目標燭火,即g(i)=i%R+1;判斷是否需要淘汰飛蛾取決于當前迭代代數(shù)和飛蛾的適應(yīng)值。 算法3BN-MFO 輸入數(shù)據(jù)矩陣D,飛蛾數(shù)量n,迭代次數(shù)T 輸出貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)鄰接矩陣A 步驟1初始化向量M,求對應(yīng)的矩陣OM,對矩陣OM排序得到矩陣OF,根據(jù)對應(yīng)關(guān)系得到向量F,求互信息矩陣MI,矩陣ChA=0、矩陣ChB=0用于放置子代。 步驟2根據(jù)式(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按照適應(yīng)值排序,取前R優(yōu)為新的向量F,同時更新矩陣OF,根據(jù)算法1生成新飛蛾替換需要淘汰飛蛾同時更新向量M和矩陣OM;若迭代未完成,轉(zhuǎn)至步驟2。 步驟5返回向量F(此時最優(yōu)燭火即為所求矩陣A)。 本文采用經(jīng)典的8個節(jié)點Asia網(wǎng)和5個節(jié)點Cancer網(wǎng)檢驗算法的有效性。首先,對網(wǎng)絡(luò)進行采樣,分別獲得3個數(shù)據(jù)集。算法有效性有4個評價指標:1)反向邊數(shù)量;2)缺失邊數(shù)量;3)多余邊數(shù)量;4)求得的結(jié)構(gòu)的評分。實驗中,飛蛾數(shù)量設(shè)為30只,迭代次數(shù)分別為200(Cancer)、250(Asia)。實驗對比算法為經(jīng)典算法HC和同樣基于群的優(yōu)化算法BNC-PSO,其粒子群數(shù)為50,迭代次數(shù)和BN-MFO相同,每個實驗均做10次,實驗結(jié)果如表1、表2所示。 表1 Cancer網(wǎng)絡(luò)實驗結(jié)果 表2 Asia網(wǎng)絡(luò)實驗結(jié)果 對于Cancer網(wǎng)絡(luò)BN-MFO能夠保持和HC一樣的效果,且返回的結(jié)果穩(wěn)定,雖然BNC-PSO能夠返回評分最優(yōu)的結(jié)構(gòu),但是每次返回的結(jié)果和標準Cancer網(wǎng)有較大差別。對于Asia網(wǎng)絡(luò),3種算法中BN-MFO能夠找到和標準Asia網(wǎng)最為相近的結(jié)構(gòu),且10次實驗返回的結(jié)構(gòu)基本相同、結(jié)果穩(wěn)定、評分普遍優(yōu)于標準Asia網(wǎng);HC算法返回結(jié)構(gòu)的評分有時甚至不如標準Asia網(wǎng)的評分優(yōu),BNC-PSO返回的結(jié)構(gòu)評分普遍優(yōu)于標準Asia網(wǎng),但是每次返回的結(jié)構(gòu)均有較大差別、不穩(wěn)定。 圖5和圖6分別是BN-MFO算法在Cancer1000和Asia2000數(shù)據(jù)集下的迭代記錄,其中,粗線表示了10次實驗的平均值,細線表示單次的收斂曲線。對于Cancer網(wǎng),算法在30代左右就找到了潛在結(jié)構(gòu),Asia網(wǎng)絡(luò)的解空間較大,找到潛在結(jié)構(gòu)的迭代次數(shù)較大。 圖5 Cancer1000收斂曲線 圖6 Asia2000收斂曲線 實驗結(jié)果表明,3種算法均能學(xué)習到網(wǎng)絡(luò)結(jié)構(gòu)的大部分結(jié)構(gòu),仍有部分結(jié)構(gòu)和標準結(jié)構(gòu)不同。BN-MFO返回的結(jié)果穩(wěn)定且最接近標準結(jié)構(gòu);HC算法能夠快速學(xué)習出網(wǎng)絡(luò)結(jié)構(gòu),但是有時不能學(xué)到最優(yōu)的結(jié)構(gòu);BNC-PSO普遍能夠?qū)W到評分最優(yōu)的結(jié)構(gòu),但每次學(xué)到的都有較大差別,不夠穩(wěn)定。 BN-MFO保留了MFO的整體框架,從而繼承了MFO的優(yōu)良性質(zhì)。由于飛蛾和燭火間的動態(tài)對應(yīng)關(guān)系g(i)和數(shù)量變化的燭火數(shù)量R的綜合作用,在算法初期飛蛾與對應(yīng)燭火的位置距離較遠,飛蛾將有更大概率探索到更多區(qū)域,保證了全局探索性;在中期,一支燭火將會對應(yīng)多只飛蛾,保證了對燭火鄰域的局部探索,后期產(chǎn)生的新生飛蛾也使得算法有機會發(fā)現(xiàn)新的潛在最優(yōu)解??梢夿N-MFO很好地平衡了對解空間的全局探索和局部探索。同時,在飛蛾通過雜交、變異等操作具有隨機性,使得飛蛾位置能夠較為均勻地分布;另一方面,在變異時參考節(jié)點間的互信息,使變異有更大概率向數(shù)據(jù)潛在結(jié)構(gòu)發(fā)生,保障了對潛在結(jié)構(gòu)的充分探索,使得返回的結(jié)構(gòu)更為穩(wěn)定。 3種算法均為基于評分搜索的算法,影響結(jié)果的自然是搜索的過程和評分函數(shù),實驗已經(jīng)表明,3種算法的搜索方式甚至能夠?qū)W到評分優(yōu)于標準網(wǎng)的網(wǎng)絡(luò)結(jié)構(gòu),驗證了搜索過程的正確性??梢?評分函數(shù)是導(dǎo)致實驗中的3種算法不能學(xué)到與原結(jié)構(gòu)完全一致的結(jié)構(gòu)的主要原因。BNC-PSO和BN-MFO得到的結(jié)果表明,不同的結(jié)構(gòu)能夠獲得相同的BIC評分,這一現(xiàn)象進一步表明評分函數(shù)的選擇能夠影響結(jié)構(gòu)學(xué)習的過程。 本文將MFO引入到貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習離散問題領(lǐng)域,借鑒遺傳算法,替換原算法的位置更新方式,在移動的過程中參考網(wǎng)絡(luò)節(jié)點的互信息,提出BN-MFO。該算法繼承了原算法的優(yōu)良性能,同時,因為互信息的運用,保證了BN-MFO的穩(wěn)定性。在標準貝葉斯網(wǎng)絡(luò)Cancer網(wǎng)和Asia網(wǎng)上,與經(jīng)典結(jié)構(gòu)學(xué)習算法及同類型結(jié)構(gòu)學(xué)習算法進行實驗對比,驗證了算法的有效性和優(yōu)越性。 [1] PEARL J.Probabilistic Reasoning in Intelligent Systems[J].Computer Science Artificial Intelligence,1988,70(2):1022-1027. [2] 胡學(xué)鋼,胡春玲.一種基于依賴分析的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習算法[J].模式識別與人工智能,2006,19(4):445-449. [3] 李冰寒,高曉利,劉三陽,等.利用互信息學(xué)習貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)[J].智能系統(tǒng)學(xué)報,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] 郭 童,林 峰.基于混合差分蜂群算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習[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.3.3 位置更新
4 實驗及分析
4.1 實驗設(shè)置及結(jié)果
4.2 結(jié)果分析
5 結(jié)束語