近似圖引導的演化貝葉斯網絡結構學習算法

曾奕博,錢 鴻,李丙棟,竇 亮,周愛民

(華東師范大學 上海智能教育研究院,上海 200062) (華東師范大學 計算機科學與技術學院,上海 200062)

0 引 言

貝葉斯網絡(Bayesian Network,BN)是一種由有向無環圖(Directed Acyclic Graph,DAG)構成的概率圖模型.不同于深度學習等黑盒模型,貝葉斯網絡具備優秀的可解釋性,且是因果推理的基礎.自1986年由Pearl[1]提出后,一直是學術界研究的熱點.BN作為目前不確定知識表達和推理領域最有效的理論模型之一,在可解釋性[2]、因果推理[3]、學習預測[4,5]等研究領域均被廣泛地應用.因此,對BN的研究具有極其重大的意義.

貝葉斯網絡的研究主要包括貝葉斯網絡學習、貝葉斯網絡推理、貝葉斯網絡應用3個部分.貝葉斯網絡學習作為推理和應用的基礎,可以分為:1)貝葉斯網絡結構學習(Bayesian Network Structure Learning,BNSL);2)貝葉斯網絡參數學習(Bayesian Network Parameter Learning,BNPL).BNSL主要是學習能夠反映變量之間相互依賴關系的有向無環圖結構;BNPL是在貝葉斯網絡結構(Bayesian Network Structure,BNS)確定的前提下,從數據中得到各變量的概率分布.BNSL是BNPL的前提.本文的主要研究目標是利用樣本數據進行高效、準確的BNSL.

基于搜索空間的不同,可以將BNSL算法分為以下3類:1)在有向無環圖(Directed Acyclic Graph,DAG)空間搜索;2)在部分有向無環圖(Partially Directed Acyclic Graph,PDAG)空間搜索;3)在序(Ordering)空間搜索.在DAG空間搜索時,搜索空間的復雜度是O(2n2),其中,n是隨機變量的個數.PDAG空間相較于DAG空間在一定程度上縮小了搜索空間的大小,但其搜索空間仍然較大.當在Ordering空間中進行節點序搜索時,其搜索空間的復雜度是O(n!),遠小于在DAG空間和PDAG空間進行搜索.

貝葉斯網絡結構學習的難點在于算法計算消耗和結果準確度之間的平衡.節點序搜索作為貝葉斯網絡結構學習中的一類重要方法,存在難以高效、準確評估解(節點序)的問題.由于評分函數以網絡結構作為輸入,不能直接計算節點序的評分,因此評估節點序需要先將節點序轉換為網絡結構再進行評估.然而,現有的節點序轉換、評估方式難以在準確度和評估效率上取得較好的平衡.例如文獻[6-8] 在每一輪迭代中使用K2算法[9]構建節點序對應的網絡結構并計算其評分,這種方式準確度較高,但多次調用K2算法會導致效率低下;文獻[10] 直接將節點序按順序連接,構建為鏈式結構并計算其評分,這種方式效率較高,但存在準確度較低的問題.通常來說,節點序評估方式是否高效、準確是通過算法計算消耗,解的靈敏性、特異性、精確率、F1評分、正確邊數和漢明距離等評價指標進行衡量的.從高效性和準確性的角度出發,評估節點序應該避免多次調用計算消耗高的算法和使用準確度低的網絡構造方式.因此,本文提出了一種近似圖引導的演化貝葉斯網絡結構學習算法(Approximate Graph Guided Evolutionary Bayesian Network Structure Learning Algorithm,AGEA).具體來說,AGEA主要包括:1)無向近似圖構建;2)最優節點序搜索;3)貝葉斯網絡構建3個部分.無向近似圖構建階段,AGEA通過計算隨機變量間的互信息,構建包含所有節點的無向近似圖,約減了BN的搜索空間;最優節點序搜索階段,提出了一種將無向近似圖和節點序相結合構造有向近似圖,并將其貝葉斯信息準則(Bayesian Information Criterion,BIC)評分[11]作為節點序的適應度來高效且準確評估節點序的方法.此外,在演化優化的框架下提出了一種基于Kendall Tau Distance的交叉算子和基于逆度的變異算子用于在搜索空間中搜索最優節點序;貝葉斯網絡構建階段,將搜索到的最優節點序輸入K2算法,得到完整的BNS.最后,本文在Asia、Alarm、Win95pts、Andes等不同規模網絡上通過實驗結果驗證了AGEA算法的有效性,AGEA算法在4個網絡上的評分相較于次優解分別提升了10.91%、12.28%、53.96%、10.87%.

1 相關工作

演化算法是BNSL算法中的一類重要方法,由于演化算法的全局搜索能力較強[12],因此被廣泛應用于BNSL[6,10,13].問題的表達方式是用演化算法求解該問題的關鍵所在,在搜索BNS時,搜索空間的不同決定了問題表達方式的不同.基于搜索空間的不同,本節將按照以下3類搜索空間作為劃分依據來介紹已有工作:1)在DAG空間搜索;2)在PDAG空間搜索;3)在Ordering空間搜索.

針對DAG空間,在DAG空間搜索指在完整的有向無環圖空間中進行搜索,此方式搜索空間最大.文獻[14] 提出了一種通過粒子的位置更新策略,提高搜索BNS效率的方法.文獻[15] 提出的PC(Peter-Clark)算法先生成一個完全無向圖,再根據條件獨立性檢測刪除圖中不存在依賴關系的邊.文獻[16] 提出的MMHC(Max-min Hill-climbing)算法通過MMPC(Max-min Parents Children)算法建立網絡結構的框架,再使用Hill-climbing對框架的邊進行定向.文獻[13] 提出了一種改善BNSL算法中的參數過多的問題的算法AESL(Adaptive Elite-based Structure Learner),該算法結合遺傳算法(Genetic Algorithm,GA)和由知識驅動的父集選擇策略來搜索最優的BNS.根據DAG結構的特點,在DAG空間中搜索BNS時,大多數工作都使用鄰接矩陣來編碼代表BNS的個體.由于在DAG空間搜索時,搜索空間的復雜度是O(2n2),由此可知在DAG空間中搜索BNS的搜索空間很大.相較于在PDAG或Ordering空間中搜索,其搜索效率較為低下.

針對PDAG空間,在PDAG空間中搜索又稱為在等價類空間中搜索,指先通過D-Separation確定網絡中存在的V結構,然后在去除已經確定的V結構的等價類空間中進行搜索.文獻[17]提出了一種結合遺傳算法和局部搜索的混合方法,將個體的初始表達擴展到PDAG空間,以在其等價類空間進行搜索.文獻[18]將演化規劃(Evolutionary Programming,EP)算子用于等價類空間中搜索BNS.在PDAG空間中搜索,從一定程度上縮小了搜索空間,提高了算法收斂的速度,但在該空間搜索的計算成本仍然較高.

針對Ordering空間,在Ordering空間搜索指在節點序空間中進行搜索,主要是搜索貝葉斯網絡中隨機變量的先后順序,即變量間信息流動的方向.由于隨機變量的先后順序不是網絡結構,無法評估其好壞,因此需要在得到節點間的順序后,再利用如K2算法[9]等[注]例如[19]用爬山法(Hill Climbing,HC)學習貝葉斯網絡結構.構建得到完整網絡結構來評估節點序的好壞.根據構建網絡結構方式的不同可以將現有的在節點序空間搜索的方法分為3個子類:算法構建、鏈式構建、近似構建.1)算法構建主要是通過K2等算法將節點序轉換為對應的網絡結構.為了得到準確度高的節點序,文獻[6]提出的K2GA(K2 Genetic Algorithm)算法根據遺傳算法搜索節點順序,再利用K2算法得到完整的網絡結構.文獻[7]和文獻[8]在K2GA的基礎上分別提出了K2ACO(K2 Ant Colony Optimization)和PSOK2(Particle Swarm Optimization K2),將K2GA方法中的遺傳算法分別用蟻群算法和粒子群算法做了替代.K2GA及其衍生的這類算法構建的方法在搜索BNS的精度上有所保證,但由于其在每輪演化迭代中,都需要對所有個體執行一次完整的K2算法,因此其計算效率較低.2)鏈式構建主要是直接將節點序鏈接為鏈式結構.文獻[10]提出了ChainGA(Chain Genetic Algorithm)來解決算法構建類方法存在的計算效率較低的問題.ChainGA用節點序鏈式結構的評分來代替K2算法搜索BNS的評分,在一定程度上避免了多次執行K2算法導致的耗費大量計算資源的問題,但是由于鏈式結構包含的信息有限,因此ChainGA的精度較低.3)近似構建主要是通過構建近似結構并結合節點序得到對應的網絡結構.文獻[20]提出了MWST-K2(Maximum Weight Spanning Tree K2),該方法首先構建最大支撐樹,并將其拓撲序輸入K2算法搜索完整的BNS.但最大支撐樹的無向邊定向時準確度較低,因此MWST-K2算法搜索得到的BNS準確度不高.近似構建平衡了構建過程的計算效率和構建結果的準確度,但對近似結構和節點序搜索的要求較高.

由于這些方法在節點序空間(Ordering Space)進行搜索,其搜索空間的復雜度是O(n!),遠小于在DAG和PDAG空間進行搜索.因為節點序限制了隨機變量間信息流動的方向,所以在評估節點序或得到最優節點序并通過K2等算法學習其對應網絡結構的過程中不會產生非法結構,避免了環路檢測及修正等高代價操作.然而K2等算法對節點序的精度要求很高,當節點序相較于真實順序的準確度很低時,K2等算法很難搜索到高精度的BNS.因此,在Ordering空間中搜索對算法的可靠性有很高的要求.然而,在Ordering空間搜索節點序的現有方法分別存在計算效率較低、準確度較低、定向不準確等問題,無法高效、準確評估節點序.本文提出的AGEA算法,在保證收斂速度的情況下,滿足該可靠性的要求.

2 AGEA算法構建

為解決在節點序空間中,搜索高質量節點序存在的難以高效、準確評估解的問題,實現算法耗時和結果準確度之間的平衡,本文提出了一種近似圖引導的演化貝葉斯網絡結構學習算法AGEA.AGEA算法框架如圖1所示,該算法包括Part(a):無向近似圖構建、Part(b):最優節點序搜索、Part(c):貝葉斯網絡構建3個部分.無向近似圖構建階段,AGEA將互信息作為先驗信息來構建所有節點的無向近似圖;最優節點序搜索階段,種群中每一個編碼為節點序的個體,均對應一個將其與無向近似圖結合構成的有向近似圖結構,有向近似結構的構造方式將在2.2.1節介紹.將該結構作為對K2GA[6]、K2ACO[7]等方法中用K2算法構造的BNS的一種近似,可以避免多次調用K2算法,提高評估效率.然后將構造的有向圖結構的BIC評分作為該個體的適應度,并在演化算法的框架下,對選擇后的個體利用提出的由精英解指導的基于Kendall Tau Distance(KTD)的交叉算子進行交叉操作,再利用提出的基于逆度的變異算子進行變異操作,并通過環境選擇得到下一代種群,不斷重復上述過程,以達到在搜索空間中搜索最優節點序的目的.最后,貝葉斯網絡構建階段,將搜索到的最優節點序輸入K2算法得到其對應的BNS.

圖1 AGEA算法框架Fig.1 Framework of AGEA algorithm

根據以上對AGEA算法中無向近似圖構建、最優節點序搜索、貝葉斯網絡構建的描述,可以得到AGEA算法如表1所示的偽代碼.在表1中的第5步,AGEA算法采取的停機條件是最大迭代次數itermax和最優解最大未更新代數genbestnotup;在表1中的第10步,AGEA算法采取的環境選擇策略是精英重插入(Elitist Reinsertion),該策略從父代和子代種群的并集中選取出M個適應度最高的個體組成新的種群P.

表1 AGEA算法偽代碼Table 1 Pseudocode of AGEA

2.1 無向近似圖構建

貝葉斯網絡由BNS和條件概率表(Conditional Probability Table,CPT)組成[21],代表BNS的有向無環圖包括一組表示問題域中隨機變量的節點,以及一組表示變量間概率依賴關系的有向邊.因此,BN可以用B(S,θ)來表示,其中S表示BN的結構,θ表示BN參數的集合.圖2展示了一個BN的例子,其結構S可以被表示為S=(V,E),V={V1,V2,…,Vn}表示由網絡中所有隨機變量組成的集合;E表示隨機變量之間邊的集合,即變量間的依賴關系;有向弧ei,j表示節點Vi和節點Vj之間的依賴關系,即信息由節點Vi向節點Vj傳遞.條件概率表由BN中所有隨機變量的條件概率組成,包含了子節點對其父節點依賴程度有關的參數.

圖2 貝葉斯網絡示例Fig.2 Example of Bayesian network

BNS可以分解為無向圖結構G和節點順序ρ,其中,無向圖結構G是BNS的主體框架,包含網絡中節點的依賴關系,但是無法表示具有依賴關系的兩節點間邊的方向;節點順序ρ包含了BN中信息流動的方向,根據具有依賴關系的兩節點Vi、Vj在節點序ρ中的位置,可以確定信息在Vi和Vj之間流動的方向,即Vi和Vj之間邊的方向.在完整的DAG空間中搜索網絡結構時,搜索空間較大,且可能出現非法環路結構.當利用節點順序ρ搜索BNS時,這種方式縮小了搜索空間,固定了節點間信息流動的方向,因此不會出現非法環路結構,但評估節點序好壞的代價十分高昂.

為了降低評估節點序的代價,本文提出了一種近似圖(Approximate Graph)結構作為評估節點序時各節點序對應的BNS的框架.構建近似圖結構時,節點間的互信息[22](Mutual Information,MI)作為啟發式信息,可以有效地表征各隨機變量間依賴關系的大小和其連接性的強弱[23].隨機變量Xi和Xj的互信息越大,則表示Xi和Xj的依賴關系越強,其中1≤i,j≤n,n是隨機變量的數目.隨機變量Xi和Xj的互信息計算公式如公式(1)所示:

(1)

其中,I(Xi,Xj)表示隨機變量Xi和Xj的互信息的值,ri表示隨機變量Xi取值情況的數量,P(Xi=xi,Xj=xj)表示Xi和Xj和的聯合概率分布,P(Xi=xi)表示樣本數據集中Xi取值是xi的概率.由公式(1)可知,隨機變量Xi和Xj的互信息是對稱的,因此得到的互信息矩陣W(Vi,Vj)是一個對角線為0的對稱矩陣,且在隨機變量Xi和Xj對應的節點Vi和Vj之間添加邊時,該邊是無向的,需要通過其他方法來學習邊的方向.

本文提出的無向近似圖共包含Q=α×n條邊,其中α是系數,n是節點數目.根據互信息矩陣W(Vi,Vj)構建無向近似圖時,首先根據Prim算法構建最大生成樹,再選擇其余互信息最大的邊加入最大生成樹,直到無向近似圖中邊的數量達到Q.其具體構建方式如下:

步驟1.初始化空的節點集合U={?},包含所有節點的集合V={V1,V2,…,Vn},以及空的邊集E={?};

步驟2.在集合V中隨機選擇一個節點Vi,并添加至集合U,然后從集合V中移除節點Vi,此時U={Vi},V={V1,…,Vi-1,Vi+1,…,Vn};

步驟3.根據互信息矩陣W(Vi,Vj),在集合V中選擇節點Vj,使得其到集合U中任一節點u的互信息最大.若存在多個滿足前述條件的節點Vj,則任取其中一個節點.將節點Vj加入到集合U,邊(Vj,u)加入集合E,并在集合V中移除Vj;

步驟4.重復步驟3,直到最大生成樹構造完成,此時無向近似圖結構共有n-1條邊;

步驟5.選擇互信息矩陣W(Vi,Vj)中互信息值最大且不在集合E中的Q-n+1條非重復邊,添加至集合E中,使得集合E內無向邊的數量達到Q.至此,便完成了無向近似圖的構建.

以圖1中的Part(a)為例,假設α=1,因此無向近似圖中邊的數量為Q=α×n=5.當根據Prim算法以及互信息矩陣W(Vi,Vj)構建最大生成樹后,邊集E={(a,b),(a,c),(b,c),(c,e)}.此時無向近似圖結構共有4條邊.選擇互信息值最大且不在集合E中的Q-n+1=1條邊(c,d)加入E,此時E={(a,b),(a,c),(b,c),(c,e),(c,d)},無向近似圖構建完畢.

當前無向近似圖結構只包含所有節點和節點間的無向邊,但缺乏節點間的依賴關系或信息流動的方向.該結構包括了真實網絡的部分信息,在對邊定向后,可以用其代替將節點序輸入K2算法得到的BNS,降低評估節點序的代價.

AGEA通過構造無向近似圖作為評估節點序時各節點序對應的BNS的框架,既避免了多次在完整的DAG空間中搜索,又大幅降低了評估節點序優劣的代價,在搜索空間和評估代價兩者間實現了較好的平衡.高效可行的無向圖結構是算法具備上述優點的有力保證,與以往基于鏈式結構或最大支撐樹等方法相比,近似圖結構包含了更多的信息.通過近似圖來實現BNS剪枝的策略,極大地減少了網絡結構中冗余邊的存在.

2.2 最優節點序搜索

得到可以有效表示節點間依賴關系的無向圖結構后,還需要搜索能夠準確描述節點間信息流動方向的節點序,將其結合得到完整的BNS.由于節點序的搜索是一個NP-hard問題[24],其搜索空間隨著節點的增多呈指數增長.因此,本文采用近似算法中的演化算法來搜索BNS的節點序.

演化算法[25](Evolution Algorithm,EA)是一種具有高魯棒性的全局優化算法,其以數學的形式將問題的候選解編碼(Encode)成染色體,染色體的每一位基因表示問題的每一個維度,通過染色體的交叉、變異過程,實現染色體間的信息交換和更新,并根據染色體對該問題的適應度,選擇適應度更高的個體保留下來.演化算法與一些常規的優化算法相比,具有更快的收斂性,通常也能搜索到更好的結構.本小節將介紹AGEA算法中的個體表達與評估、由精英解指導的基于KDT的交叉算子以及基于逆度的變異算子.

2.2.1 個體表達與評估

本文提出的AGEA算法在節點序空間中搜索BNS,目的是尋找隨機變量間的最佳排序.要求搜索一個包含所有節點,且節點不重復的序列,使得其對應的網絡結構評分最高.因此當BN的節點數為n時,可以采用n維序列(Permutation)來作為個體的編碼.該方法用數字組成的列表Per來表示變量的先后順序,n維序列Per由不重復的數字(1,2,…,n)組成,當節點Vj位于序列中第l個位置時,則序列中第l個元素是j.例如,若個體編碼為(5,2,3,1,4),則其代表的節點序列為Per=(V5,V2,V3,V1,V4).

已知個體編碼的節點序列Per后,將其與無向近似圖結合,構建有向近似圖.該方法的具體方式為:在已有無向近似圖的基礎上,根據節點Vi和Vj在個體編碼所對應的節點序列Per的先后順序對邊(Vi,Vj)進行定向,若節點Vi在節點Vj之前,則表示Vi為Vj的因,信息從Vi流向Vj,因此將從Vi到Vj該條有向邊加入到有向近似圖中.反之,則將從Vj到Vi該條有向邊加入到有向近似圖中.以圖1所示的無向近似圖和節點序(A,B,C,D,E)為例,構建有向近似圖的過程如圖3所示.

圖3 構建有向近似圖Fig.3 Construction of directed approximate graph

根據節點序和無向近似圖構建的有向近似圖,在很大程度上包含了實際貝葉斯網絡的信息,是對實際貝葉斯網絡的一種有效逼近.根據以上方法得到有向近似圖結構后,以該結構作為個體對應的完整BNS的近似,通過BIC評分函數[11]計算該結構的評分,并將BIC評分作為個體的適應度(fitness),再利用演化算法搜索最優的節點序.適應度的具體定義如公式(2)所示:

(2)

其中,n表示節點數量,qi表示節點Vi的父節點所有取值情況的數量,ri表示節點Vi取值情況的數量,mijk表示節點Vi的父節點取值情況為j時,在數據集中節點Vi取值為k的數量.由于BIC評分為負數,因此演化算法搜索的目標是一個對應fitness最高,即損失函數loss最低的節點序.

2.2.2 精英解指導的基于KDT的交叉算子

演化算法是一種通過不斷迭代尋優的搜索算法,在每次迭代中,利用交叉算子的全局搜索能力和變異算子的局部搜索能力,在解空間中搜索最優解.為了加快AGEA全局搜索的速度,并平衡對搜索空間的探索與利用(exploration and exploitation),本文提出了一種由精英解指導的基于KDT的交叉算子.該交叉算子首先在種群P中選擇β×PNum個適應度最高的個體組成精英解集合Eelite,其中β表示精英解占種群中所有個體的比例,PNum表示種群中個體的數量.然后對每一個需要進行交叉操作的個體Indt,計算其與精英解集合Eelite中每一個精英解Eelite_i的Kendall tau 距離,Kendall tau 距離的計算公式如公式(3)所示:

Kd(τ1,τ2)=|{(i,j):iτ2(j)]∨

[τ1(i)>τ1(j)∧τ2(i)<τ2(j)]}|

(3)

其中τ1,τ2表示表示個體1與個體2,τ1(i)和τ2(i)分別表示節點Vi在τ1和τ2中的索引位置.根據公式(3)得到個體Indt與精英解集合Eelite中每一個精英解Eelite_i的Kendall tau距離后,根據該距離利用輪盤賭算法選擇出與Indt進行交叉操作的精英解Eelite_i,并采用部分匹配交叉[26](Partially Matched Crossover,PMC)得到交叉后的子代個體.部分匹配交叉的具體步驟如下:

Step 1.從父代個體parent1中選擇一段基因賦值到子代個體children中,并記下基因的起始和結束位置;

Step 2.在父代個體parent2中的相同位置,選擇尚未復制到children中的所有值,對于每個值valuei,令value=valuei:

Step 2.1.根據value在parent2中的位置索引,找到parent1在同一位置的值valuej;

Step 2.2.在parent2中找到valuej的位置,若該位置在Step 1中選擇的基因片段中,則另value=valuej,并回到Step 2.1;若該位置不在Step 1中選擇的基因片段中,則將valuei插入到該位置;

Step 3.根據children中空余的位置,從parent2中相同的位置拷貝值填入children中;

由精英解指導的基于KDT的交叉算子通過從精英解集合中選擇與當前個體交叉的父代,能夠提高AGEA算法全局搜索的速度,縮減了對低質量解的探索.同時,基于與精英解的Kendall tau距離,利用輪盤賭算法選擇交叉的精英解,保證了種群的多樣性,避免了算法因陷入局部最優而提前收斂.

2.2.3 基于逆度的變異算子

為了提升解的多樣性,防止算法因陷入局部最優而過早收斂,本文提出了一種基于逆度的變異算子.該算子首先根據2.2.2節中構建的精英解集合Eelite計算逆度矩陣(Inverse Degree Matrix),逆度矩陣IDij的定義如公式(4)所示:

IDij=|(Vi,Vj):Indt(i)

(4)

其中IDij表示在Eelite集合中節點Vi位置在節點Vj前的個體數目,Indt(i)節點Vi在Indt中的索引位置.根據公式(4)得到逆度矩陣IDij后,對需要進行變異操作的個體ind中的每一個節點Vi,產生一個(0,1)區間的隨機數rand,若rand小于變異率,則對該節點進行變異操作,計算該節點與ind中其余所有節點的逆度,計算節點Vi和Vj(i≠j)的逆度idij的公式如公式(5)所示:

(5)

公式(5)表示,當ind中節點Vi和Vj的先后順序與精英解集合Eelite中Vi和Vj出現較多的先后順序相同時,idij的值為0;當ind中節點Vi和Vj的先后順序與精英解集合Eelite中Vi和Vj出現較多的先后順序不同時,idij的值為Eelite中Vi和Vj出現較多的先后順序的數目.最后,根據公式(6):

(6)

選擇出節點Vj,并在ind將節點Vi和Vj的位置互換,便完成了基于逆度的變異操作.以編碼為(1,2,3,4,5)的個體為例,當變異的位置為第3位的節點V3,且根據公式(6)選擇出的與之互換位置的節點為V5時,該個體的染色體變為(1,2,5,4,3).

2.3 貝葉斯網絡構建

本節將主要介紹在根據隨機變量間的互信息構建無向近似圖,并在演化算法的框架下,利用由精英解指導的基于KDT的交叉算子和基于逆度的變異算子搜索得到最優節點序后,如何根據最優節點序構建BNS.

根據無向近似圖結構和節點序構建的BNS,只包含部分互信息較高的邊,缺失了一些實際存在但互信息較不顯著的邊,因此需要K2算法對網絡結構進行修正.K2算法首先構造一個包含全部節點,但不包含邊的網絡結構,然后按照節點順序逐一搜索各變量的父節點,將能夠提高網絡評分的父節點到子節點的邊加入到網絡結構中.在AGEA算法的貝葉斯網絡構建階段,AGEA算法將2.2節中搜索得到的最優節點序作為K2算法的輸入,并將K2算法搜索得到的BNS作為輸出,以此完成貝葉斯網絡的構建.

2.4 AGEA算法收斂性分析

本節將使用概率測度法[27]來分析AGEA算法的收斂性.

引理1.AGEA算法滿足:f(G(z,ξ))≥f(z),且若ξ∈S,則f(G(z,ξ))≥f(ξ).

其中,f表示2.2.1節中計算個體適應度的函數,G表示以z和ξ為參數的生成較優新解的函數,z表示搜索空間S中的最優解空間Sgbest內的個體,其對應的適應度值是S上可接受的適應度值的上確界,Sgbest是S的子集,ξ是AGEA算法在搜索空間S上產生的任一個體.

證明:根據2.4節中AGEA算法采取精英重插入作為環境選擇策略的介紹,因此生成較優新解的函數G可以定義為如公式(7)所示的形式:

(7)

引理2.對S的任何Lebesgue測度大于0的Borel子集A,有:

(8)

其中,iter表示第iter輪迭代,μiter(A)表示由μiter產生的對子集A的概率測度.

證明:S為AGEA算法的搜索空間,顯然其Lebesgue測度[28]總大于0,即L(S)>0.根據子集A的定義,可得0<μi,iter(A)<1,由μiter產生的對子集A的概率測度為:

(9)

將公式(9)代入到公式(8)可得:

(10)

所以,引理2得證.

因為AGEA的最優解空間Sgbest屬于S的Borel[28]子集,且根據其定義可得L(Sgbest)>0,AGEA的最優解空間Sgbest滿足:

(11)

根據文獻[27]中的Theorem 1,有:當適應度函數f為可度量函數,S為Rn的可度量子集,滿足引理1和引理2,則:

(12)

其中,inditer為第iter輪迭代產生的結果.公式(12)表明,第iter輪迭代產生的結果inditer落在Sgbest的概率為1,即AGEA算法經過有限次的迭代后,一定會產生在最優解空間Sgbest中的個體.至此,AGEA算法的收斂性得證.

3 實驗結果及分析

為驗證提出的AGEA算法的可行性和效果,本文在操作系統Ubuntu 18.04,處理器Intel Xeon Gold 6354 3.0GHz,內存64GB,python 3.7,以及貝葉斯網絡python庫pgmpy 0.1.12的環境下進行實驗.實驗在Asia,Alarm,Win95pts,以及Andes等不同規模的經典貝葉斯網絡模型上進行,在這些網絡上進行實驗的樣本量分別為5000、5000、5000、2000條.對比算法包括AESL[13],PC-stable[29],MMHC[16],K2-GA[6],Chain-GA[10],K2[9].表2展示了各網絡的節點數、邊數等信息,表3展示了AGEA算法的參數設置.

表2 貝葉斯網絡信息Table 2 Information of different Bayesian network

表3 AGEA算法參數設置Table 3 Parameter setting of AGEA

3.1 AGEA算法與其他算法實驗結果對比

本文采用靈敏性(Sensitivity)、特異性(Specificity)、精確率(Precision)、F1評分(F1-Score)、正確邊數、漢明距離(Hamming Distance)作為衡量AGEA與其他對比算法的指標.其中,Sensitivity表示識別出的正樣本在所有正樣本中的比例,衡量了算法識別正樣本的能力,其計算方式如公式(13)所示:

(13)

TP(True Positive)表示在真實網絡中存在且被算法預測為存在的邊數,FN(False Positive)表示在真實網絡中存在但被算法預測為不存在的邊數;Specificity表示算法識別出不存在的邊在所有真實網絡不存在的邊中的比例,衡量了算法識別負樣本的能力,其計算方式如公式(14)所示:

(14)

TN(True Negative)表示在真實網絡中不存在且被算法預測為不存在的邊數,FP(False Positive)表示在真實網絡中不存在但被算法預測為存在的邊數;Precision表示算法預測為存在的邊中實際存在的邊的比例,其計算方式如公式(15)所示:

(15)

F1-Score同時兼顧了模型的精確率和召回率(Recall),其計算方式如公式(16)所示:

(16)

其中,Recall=Sensitivity;正確邊數為在算法學習到的BNS中存在的邊且在真實網絡結構中存在的邊的數目,其值為TP;漢明距離表示學習到的BNS和真實網絡結構不相同的邊的數量之和,即反向邊、多余邊、缺失邊的數目之和.漢明距離的計算公式如公式(17)所示:

HammingDistance=FP+FN

(17)

漢明距離越小,表示算法學習到的BNS準確度越高.表4展示了AGEA算法及其他對比算法在Asia、Alarm、Win95pts、Andes等不同規模的BN模型上,根據前文所描述的采樣條數進行隨機采樣并重復試驗20次取平均的結果.K2-GA算法在Win95pts和Andes上運行時間過長,超出了72小時,因此沒有實驗結果.此外,本文對表4中的評價指標進行了置信度為95%的t檢驗,數據后的實心點或空心點表示對應方法的該指標明顯優于或劣于AGEA算法的該指標.從表4中的數據可知,在Asia、Alarm網絡上,AGEA算法的Sensitive、Specificity、Precision指標均明顯優于其他對比算法;在Win95pts網絡上AGEA算法的Sensitive、Precision指標均明顯優于其他對比算法,Specificity略低于PC-stable;在Andes網絡上,AGEA算法的Sensitive指標明顯優于其他對比算法,Specificity指標略低于AESL,PC-stable和MMHC算法,Precision指標低于PC-stable和MMHC算法,這是由于基于評分的方法傾向于盡可能找到能夠提升網絡結構評分的邊,在這個過程中會導致出現部分多余邊,使得Precision指標下降.

表4 AGEA與其他對比算法實驗結果Table 4 Experiment results of AGEA and other algorithms

圖4展示了AGEA算法及其他對比算法在Asia、Alarm、Win95pts、Andes等不同規模的網絡上學習到的網絡結構與真實結構相比的正確邊數與標準差.由于K2-GA在Win95pts、Andes上沒有實驗結果,因此將其正確邊數置為0.由圖4可知,AGEA算法相較于其他算法,在4種不同規模的網絡上均能學習到最多的正確邊數.AGEA算法學習到的平均正確邊數分別為7.95、43.85、97.70、261.60,相較于次優解,分別提升了22.31%、25.29%、114.96%、109.53%,由此可知,AGEA算法不僅在4個數據集上都能學習到最多的正確邊數,且在節點數較多的網絡Win95pts和Andes中,相較于對比算法在正確邊數上的提升更大.在由223個節點、338條邊構成的網絡Andes中,MMS平均學習到261.6條正確邊,占總邊數的77.40%,而次優解MMHC的該比例僅為44.38%.

圖4 AGEA算法與各對比算法正確邊數Fig.4 Correct edges of AGEA and other algorithms

圖5展示了AGEA算法及其他對比算法在Asia、Alarm、Win95pts、Andes等不同規模的網絡上學習到的網絡結構與真實結構相比的漢明距離與標準差.由圖5可知,AGEA算法在這4個網絡上的漢明距離分別為0.25、7.80、55.40、330.55.相較于其他算法,在Asia、Alarm、Win95pts這3個不同規模網絡上的漢明距離均低于其他對比算法,相較于次優解分別降低了84.38%、49.51%、37.37%;在Andes網絡上的漢明距離略高于PC-stable和MMHC,相較于最優解提高了40.78%.

圖5 AGEA算法與各對比算法漢明距離Fig.5 Hamming distance of AGEA and other algorithms

由于F1-Score同時兼顧了精確率和召回率,因此本文選取F1-Score來作為衡量算法優劣的指標.圖6展示了AGEA算法及其他對比算法在Asia、Alarm、Win95pts、Andes等不同規模的網絡上學習到的網絡結構與真實結構相比的F1-Score.由圖6可知,AGEA算法相較于其他算法,在Asia、Alarm、Win95pts、Andes等不同規模的網絡上均能得到最高的F1-Score.在該4種不同規模的網絡上,AGEA算法的F1-Score分別為0.9849、0.9187、0.7795、0.6132,相較于次優解,分別提升了10.91%、12.28%、53.96%、10.87%.以上數據表明,AGEA算法相較于其他對比算法,具有更高的學習精度,驗證了AGEA算法的準確性.此外,與K2算法的各項指標對比結果表明,AGEA搜索到的節點序是有效的.

圖6 AGEA算法與各對比算法F1-Score Fig.6 F1-Score of AGEA and other algorithms

3.2 AGEA算法與其他算法計算時間對比

為了驗證AGEA算法的計算效率,本文對AGEA及其他對比算法在Asia、Alarm、Win95pts、Andes等網絡上學習BNS所用的時間進行了比較.各方法學習得到最終網絡結構平均所用時間如表5所示,單位為秒.從表5所示的各方法在不同網絡上學習最優BNS所耗計算時間可知,在Asia網絡和Alarm網絡中,AGEA學習BNS的時間與Chain-GA、PC-stable、MMHC、K2在同一個數量級,比K2-GA、AESL低一個數量級.以37個結點,46條邊的Alarm網絡為例,AGEA與計算時間相同數量級的Chain-GA、PC-stable、MMHC、K2相比,F1-Score分別提升99.93%、20.98%、68.08%、139.43%;與計算時間高一個數量級的AESL、K2-GA相比,F1-Score分別提升54.04%、12.28%.在Win95pts網絡和Andes網絡中,AGEA學習BNS的時間與AESL、Chain-GA在同一個數量級,與PC-stable、MMHC相比在Win95pts中高一個數量級,在Andes中高兩個數量級.以76個結點,112條邊的Win95pts網絡為例,AGEA與計算時間相同數量級的AESL、Chain-GA相比,F1-Score分別提升141.41%、146.21%;與低一個數量級的PC-stable、MMHC、K2相比,F1-Score分別提升53.96%、89.06%、159.31%.

表5 AGEA算法與各對比算法計算時間(秒)Table 5 Computation time of AGEA and other algorithms

從以上數據可知,AGEA算法與AESL、K2-GA、Chain-GA等耗時較高的算法相比,能夠在有效降低耗時的情況下,學習到更優的BNS;與PC-stable、MMHC、K2等耗時較低的算法相比,AGEA算法能夠在控制計算時間的情況下,極大地提高學習BNS的精度.

3.3 教育數據集驗證

為驗證AGEA算法在真實數據集上學習BNS的效果,本文針對教育領域中幫助學生厘清知識點脈絡、輔助個性化學習的知識結構學習問題,在一組由文獻[30]提出并使用的教育數據集上用AGEA和其他算法做了實驗.該數據集為某市部分高中學生數學測驗的題目信息及學生作答成績.其中,數據集1和數據集2分別包含題目15、16題,知識點11、16個,學生做題數據4209、3911條.本文針對函數應用題在部分數據上進行了實驗,圖7給出了其對應的真實網絡結構.利用DINA模型[31]得到各學生的認知診斷結果后,本文使用AGEA及其他對比算法在該數據集上學習知識點間關系的BNS,并對各方法的正確邊數、漢明距離以及F1-Score進行了比較,其具體結果如表6所示.其中PC-stable學習到的正確邊數為0,因此F1-Score為0.

表6 AGEA算法與各算法在教育數據集上對比Table 6 Comparison of AGEA and other algorithms on educational data set

圖7 知識點真實網絡結構Fig.7 Network structure of knowledge concepts

根據表6的結果可知,相較于AESL、MMHC等其他算法,AGEA在該教育數據集上能學習到更接近真實結構的BNS.其中,AGEA算法的正確邊數相較于次優解提升了24.77%,漢明距離相較于次優解降低了18.22%,F1-Score相較于次優解由0.3786提升至0.5726,提升了51.24%.由此可知,本文提出的AGEA算法在該真實數據集上也能取得良好的效果,根據真實數據集構建符合實際情況的BN模型.

4 總 結

貝葉斯網絡是不確定知識表達與推理領域最有效的模型之一,對貝葉斯網絡的研究具有重要意義.針對在節點序空間中,搜索高質量節點序存在的難以高效、準確評估解的問題,本文提出了一種近似圖引導的演化貝葉斯網絡結構學習算法AGEA.該算法包括無向近似圖構建、最優節點序搜索、貝葉斯網絡構建3個部分.無向近似圖構建階段,AGEA通過計算隨機變量間的互信息構建無向近似圖;最優節點序搜索階段,AGEA通過構建有向近似圖來快速且高效地評估節點序,并在演化算法的框架下利用基于KTD的交叉算子和基于逆度的變異算子在搜索空間中搜索最優節點序;貝葉斯網絡構建階段,AGEA將搜索到的最優節點序輸入K2算法,得到BNS.實驗結果表明,從節點數較少的Asia網絡到節點數較多的Andes網絡,AGEA算法均能找到接近于原始網絡的貝葉斯網絡結構,F1-Score相較于次優解也分別提升了10.91%、12.28%、53.96%、10.87%.此外,與耗時較高的對比算法相比,AGEA算法能夠在有效降低耗時的情況下,學習到更優的BNS;與耗時較低的算法相比,AGEA算法能夠在控制計算時間的情況下,極大地提高學習BNS的精度.AGEA算法在真實教育數據集上取得了良好的效果,F1-Score相較于次優解提升了0.194(0.3786→0.5726),提升了51.24%,驗證了AGEA算法在真實數據集上的有效性.

下一步的工作可以從改進無向近似圖構建和最優節點序搜索兩個方向展開.針對無向近似圖構建,將探究更高效的無向近似圖表示方式,例如選擇更能代表隨機變量間關系的先驗信息來替換互信息;針對最優節點序搜索,將設計更加高效的搜索算子以及更加合理的個體編碼方式,以進一步提高算法的效率和準確度.