一種優(yōu)化節(jié)點(diǎn)序搜索算子的BN結(jié)構(gòu)學(xué)習(xí)方法

賈柳娜, 董綿綿, 賀楚超, 邸若海, 李曉艷

(西安工業(yè)大學(xué) 電子信息工程學(xué)院, 陜西 西安 710021)

貝葉斯網(wǎng)絡(luò)(Bayesian networks,BN)[1]是一種用于描述隨機(jī)變量之間因果關(guān)系的概率圖形模型,能有效直觀地表達(dá)和推理不確定性問題。現(xiàn)如今各領(lǐng)域數(shù)據(jù)呈現(xiàn)出爆炸式的增長趨勢,傳統(tǒng)的基于專家經(jīng)驗(yàn)的決策方法已經(jīng)不能滿足社會(huì)發(fā)展的需要。而貝葉斯網(wǎng)絡(luò)在處理不確定性問題上的巨大優(yōu)勢使其廣泛應(yīng)用于數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、診斷和評估等領(lǐng)域[2]。在貝葉斯網(wǎng)絡(luò)學(xué)習(xí)中,貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)是參數(shù)學(xué)習(xí)和推理的前提和基礎(chǔ),也是貝葉斯網(wǎng)絡(luò)研究的重點(diǎn)。因此,如何在合理的時(shí)間范圍內(nèi)從復(fù)雜的數(shù)據(jù)中學(xué)習(xí)最優(yōu)結(jié)構(gòu)近年來引起了國內(nèi)外專家學(xué)者的大量研究關(guān)注。

基于評分搜索的方法是一種常用的BN結(jié)構(gòu)學(xué)習(xí)算法[3],通過優(yōu)化評分函數(shù)或搜索策略來改善學(xué)習(xí)效率,其中常用的評分函數(shù)包括BIC[4]、MDL[5]和BD[6]評分等。評分搜索法的搜索空間的可分為網(wǎng)絡(luò)結(jié)構(gòu)空間[7]和節(jié)點(diǎn)序空間[8]兩大類。典型的網(wǎng)絡(luò)結(jié)構(gòu)空間下的BN結(jié)構(gòu)學(xué)習(xí)算法包括K2算法[9]、HC算法[10]等,該類算法的復(fù)雜度隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目的增加呈指數(shù)級增長[11],搜索效率較低。本文重點(diǎn)研究的是節(jié)點(diǎn)序空間下基于評分搜索的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)問題,相較于網(wǎng)絡(luò)結(jié)構(gòu)空間,基于節(jié)點(diǎn)序空間(ordering-based search,OBS)展開搜索時(shí)有以下優(yōu)勢[12]:①搜索范圍由網(wǎng)絡(luò)空間下的2Ω(n2)個(gè)候選網(wǎng)絡(luò)結(jié)構(gòu)轉(zhuǎn)變?yōu)楣?jié)點(diǎn)序空間下的2O(nlgn)條節(jié)點(diǎn)序,搜索空間明顯縮小;②基于網(wǎng)絡(luò)空間展開搜索時(shí)每一步的構(gòu)造網(wǎng)絡(luò)結(jié)構(gòu)和執(zhí)行條件獨(dú)立性測試都很耗時(shí),而節(jié)點(diǎn)序空間下進(jìn)行搜索無需構(gòu)造網(wǎng)絡(luò)結(jié)構(gòu),搜索效率更高;③搜索過程中的每一步對當(dāng)前假設(shè)進(jìn)行的全局性修改程度更大,能夠有效避免算法陷入局部最優(yōu)。

目前,國內(nèi)外專家學(xué)者已提出許多通過搜索最優(yōu)節(jié)點(diǎn)序來學(xué)習(xí)評分最高的BN結(jié)構(gòu)方法,代表性的方法有OBS[8]、INOBS[13]、IINOBS[13]等,通過搜索最優(yōu)節(jié)點(diǎn)序來學(xué)習(xí)評分最優(yōu)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。這些節(jié)點(diǎn)序空間下的BN結(jié)構(gòu)學(xué)習(xí)算法均取得了較好的學(xué)習(xí)效果,然而在展開搜索時(shí)仍然存在節(jié)點(diǎn)序優(yōu)化不足、學(xué)習(xí)精度低等問題。為了解決這些問題,本文提出了一種新的基于節(jié)點(diǎn)序的BN結(jié)構(gòu)學(xué)習(xí)算法,通過優(yōu)化節(jié)點(diǎn)序搜索算子使當(dāng)前節(jié)點(diǎn)的排序發(fā)生局部變化的程度更大,從而獲得更高評分的結(jié)構(gòu),將窗口算子與INOBS算法(insert neighbourhood OBS,INOBS)相結(jié)合作為迭代局部搜索過程的組成部分,提出基于迭代局部搜索的引入窗口算子的INOBS算法(iterate window operator with INOBS,IWINOBS)。仿真結(jié)果表明,在中小規(guī)模網(wǎng)絡(luò)下IWINOBS算法的學(xué)習(xí)效率和精度優(yōu)于OBS和IINOBS算法等節(jié)點(diǎn)序空間下的經(jīng)典算法。

1 貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)

一個(gè)貝葉斯網(wǎng)絡(luò)用B=(G,P)表示,其中G(V,E)表示貝葉斯網(wǎng)絡(luò)結(jié)構(gòu),是一個(gè)有向無環(huán)圖(directed acyclic graph,DAG),V={X1,X2,…,Xn}表示隨機(jī)變量的集合,E表示有向邊的集合,可以定義為每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)集合Pa(Xi);P是貝葉斯網(wǎng)絡(luò)參數(shù),表示每個(gè)變量在給定其父節(jié)點(diǎn)時(shí)的條件概率分布,定量地描述了變量與其父節(jié)點(diǎn)之間的因果依賴關(guān)系。圖1給出了一個(gè)典型的貝葉斯網(wǎng)絡(luò)模型,該網(wǎng)絡(luò)模型包含5個(gè)節(jié)點(diǎn)和4條有向邊,可以看到每個(gè)節(jié)點(diǎn)對應(yīng)的條件概率分布表和節(jié)點(diǎn)之間的相關(guān)性。模型中所有節(jié)點(diǎn)的類型都是離散的,并且均含有2個(gè)狀態(tài)值(y和n)。

圖1 一個(gè)貝葉斯網(wǎng)絡(luò)模型

由于局部馬爾科夫性,即給定貝葉斯網(wǎng)絡(luò)中節(jié)點(diǎn)Xi的父節(jié)點(diǎn),則節(jié)點(diǎn)Xi條件獨(dú)立于其所有的非后代節(jié)點(diǎn)。因此,完整聯(lián)合概率分布表P(V)可以表示為局部分布函數(shù)的乘積,大大降低了聯(lián)合概率的計(jì)算復(fù)雜度。聯(lián)合概率分布P(V)的表達(dá)式如公式(1)所示,其中Pa(Xi)表示節(jié)點(diǎn)Xi的父節(jié)點(diǎn)集合。

(1)

(2)

由公式(2)可知,對于結(jié)構(gòu)G,其評分s(G,D)僅依賴于節(jié)點(diǎn)Xi和Xi的父節(jié)點(diǎn)集Pa(Xi)。

本文采用BIC作為評分函數(shù),它與DAG的后驗(yàn)概率成正比。BIC評分是可分解的,可以表示成各個(gè)節(jié)點(diǎn)的評分之和,如公式(3)所示。

(3)

2 IWINOBS算法研究

基于節(jié)點(diǎn)序的OBS算法將BN結(jié)構(gòu)學(xué)習(xí)問題轉(zhuǎn)化為搜索最優(yōu)節(jié)點(diǎn)序的問題,可以顯著縮小搜索空間[12]。給定節(jié)點(diǎn)序,關(guān)于該節(jié)點(diǎn)序的最佳網(wǎng)絡(luò)結(jié)構(gòu)可以在O(Ck)時(shí)間內(nèi)找到,其中,表示最大入度,節(jié)點(diǎn)Xi的最優(yōu)父節(jié)點(diǎn)集為

(4)

式中,Ui是所有可能的父節(jié)點(diǎn)的集合,僅包含節(jié)點(diǎn)序中排在Xi之前的節(jié)點(diǎn),這也被稱為一致性規(guī)則。對節(jié)點(diǎn)序進(jìn)行抽樣后,就可以根據(jù)公式(4)快速獲得給定節(jié)點(diǎn)序的最高評分結(jié)構(gòu)。一般來說,在節(jié)點(diǎn)序空間中進(jìn)行局部搜索的過程包括以下4個(gè)步驟[13]:①采用啟發(fā)式搜索隨機(jī)獲取初始節(jié)點(diǎn)序;②獲得初始節(jié)點(diǎn)序后,使用不同的搜索算子對當(dāng)前節(jié)點(diǎn)序的鄰域展開搜索,以此來改變節(jié)點(diǎn)序中一些節(jié)點(diǎn)的位置,節(jié)點(diǎn)序每改變一次(迭代)說明已進(jìn)行一次優(yōu)化;③當(dāng)一次迭代完成(未達(dá)到終止條件)時(shí),通過更大的搜索步驟來優(yōu)化當(dāng)前節(jié)點(diǎn)序,從而避免陷入局部最優(yōu)狀態(tài);④獲得最優(yōu)節(jié)點(diǎn)序后,再將該節(jié)點(diǎn)序作為K2算法的輸入得到DAG結(jié)構(gòu)。

2.1 節(jié)點(diǎn)序空間中的局部搜索算子

OBS算法使用交換相鄰算子對節(jié)點(diǎn)序進(jìn)行搜索,交換相鄰算子的定義如公式(5)所示,示例如圖2所示。

圖2 節(jié)點(diǎn)E和D在節(jié)點(diǎn)序中交換位置

Oswap(i):(X1,…,Xi,Xi+1,…,Xn)→

(X1,…,Xi+1,Xi,…,Xn)

(5)

由公式(5)可知,根據(jù)新的節(jié)點(diǎn)序來計(jì)算評分最高的網(wǎng)絡(luò)的評分,只需要重新計(jì)算Xi和Xi+1的父節(jié)點(diǎn)集合。因此,給定節(jié)點(diǎn)序,使用一次交換相鄰算子會(huì)產(chǎn)生n-1個(gè)候選節(jié)點(diǎn)序。雖然交換相鄰算子簡單有效,但其搜索空間有限,往往不足以獲得最優(yōu)節(jié)點(diǎn)序,這限制了它避免陷入局部最優(yōu)值的能力。

文獻(xiàn)[14]提到的INOBS算法中引入了插入算子,即給定2個(gè)索引i和j,初始節(jié)點(diǎn)序中索引i處的節(jié)點(diǎn)被插入后續(xù)節(jié)點(diǎn)序中的索引j處,使得排在初始節(jié)點(diǎn)序中索引i和j之間的節(jié)點(diǎn)位置發(fā)生變化。因此,使用插入算子對節(jié)點(diǎn)序的修改程度比交換相鄰算子更大,從而克服了OBS算法的不足。插入算子的定義如公式(6)所示,示例如圖3所示。

圖3 節(jié)點(diǎn)E被插入到節(jié)點(diǎn)B的位置

Oinsert(i,j):(X1,…,Xi,…,Xj,…,Xn)→

(X1,…,Xj,Xi,…,Xn)

(6)

由此可見,交換相鄰算子也是插入算子的一種特殊情況,它應(yīng)用于2個(gè)相鄰的節(jié)點(diǎn)。也就是說Oswap(i)=Oinsert(i+1,i)。

插入算子可以被看作是多次相鄰節(jié)點(diǎn)交換操作的結(jié)果,如圖4所示。每次使用交換相鄰算子只需要重新計(jì)算被交換的2個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)集合,因此,插入算子也可以只重新計(jì)算有限數(shù)量的父節(jié)點(diǎn)集合。

圖4 插入算子的具體執(zhí)行方式

給定節(jié)點(diǎn)序,使用一次插入算子會(huì)產(chǎn)生n(n-1)個(gè)候選節(jié)點(diǎn)序。Alonso-Barba等[15]提出了一種搜索候選節(jié)點(diǎn)序的方法:隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為固定索引,通過一系列交換算子完成對第二個(gè)索引的完整搜索,然后選擇評分更優(yōu)的候選節(jié)點(diǎn)序,直到所有節(jié)點(diǎn)都沒有被進(jìn)一步優(yōu)化時(shí)停止搜索。

Scanagatta等[16]提出了一種用于局部搜索的窗口算子,窗口算子是插入算子的一種,包括起始位置i、插入位置j和組合節(jié)點(diǎn)的窗口大小w這3個(gè)參數(shù),用Owindow(i,j,w)表示。其工作原理如下:選擇初始節(jié)點(diǎn)序中位置i處的節(jié)點(diǎn)和w-1個(gè)后繼節(jié)點(diǎn),將這些節(jié)點(diǎn)插入到位置j,從而得到新的節(jié)點(diǎn)序。

窗口算子在另一個(gè)節(jié)點(diǎn)的前面插入多個(gè)節(jié)點(diǎn),通過同時(shí)改變多個(gè)節(jié)點(diǎn)的索引來更新節(jié)點(diǎn)序,所有改變的節(jié)點(diǎn)必須是相鄰的,因此局部搜索的范圍會(huì)進(jìn)一步擴(kuò)大。窗口算子也可以通過一系列插入算子來實(shí)現(xiàn),其規(guī)則如公式(7)所示,示例如圖5所示。

Owindow(i,j,w):

(X1,…,Xj,…,Xi,…,Xi+w,…,Xn)

→(X1,…,Xi,…,Xi+w,Xj,…,Xn)

(7)

由圖5可知,給定節(jié)點(diǎn)序,使用一次窗口算子會(huì)產(chǎn)生(n-(w-1))·(n-w)個(gè)候選節(jié)點(diǎn)序。窗口

圖5 Owindow(5,2,3)示例:節(jié)點(diǎn)E,F,G插入到初始節(jié)點(diǎn)序中節(jié)點(diǎn)B,C,D的位置

算子可以看作是一系列“窗口交換”,每次窗口交換最多需要重新計(jì)算與w+1個(gè)節(jié)點(diǎn)序一致的最優(yōu)父節(jié)點(diǎn)集。窗口算子在節(jié)點(diǎn)序中的具體使用過程:選擇一個(gè)隨機(jī)節(jié)點(diǎn)作為固定索引,從w=1開始,考慮窗口大小為w的所有后繼節(jié)點(diǎn)序;如果找到了評分更優(yōu)的后繼節(jié)點(diǎn)序,則移動(dòng)到該狀態(tài)并使得w=1;如果所有節(jié)點(diǎn)都已選擇,并且沒有發(fā)現(xiàn)可以提高評分的后繼狀態(tài),則將w增加1;如果超過了最大窗口大小,則返回當(dāng)前狀態(tài)。

2.2 節(jié)點(diǎn)序的迭代局部搜索方法

為提高節(jié)點(diǎn)序空間下BN結(jié)構(gòu)學(xué)習(xí)算法的學(xué)習(xí)精度,本文在搜索節(jié)點(diǎn)序的過程中提出將迭代局部搜索(iterative local search,ILS)方法與窗口插入算子相結(jié)合的搜索方法。ILS算法是一種具有2個(gè)算子的元啟發(fā)式方法,用于提高局部最優(yōu)解的質(zhì)量。第一個(gè)是局部搜索算子,它能在一個(gè)解的鄰域中找出局部最優(yōu)解,第二個(gè)是擾動(dòng)算子,能夠在一個(gè)局部最優(yōu)解的附近繼續(xù)搜索,為局部搜索找到一個(gè)新的最優(yōu)解。一般來說,迭代局部搜索方法由局部搜索、擾動(dòng)和停止標(biāo)準(zhǔn)3個(gè)步驟組成。本文將窗口算子與迭代局部搜索相結(jié)合,從預(yù)先定義的搜索空間內(nèi)的隨機(jī)初始解開始,當(dāng)前達(dá)到的局部最優(yōu)值能夠被隨機(jī)交換擾動(dòng),得到擾動(dòng)后的新解,通過窗口算子在擾動(dòng)解的附近以更大的搜索步驟繼續(xù)搜索更優(yōu)節(jié)點(diǎn)序。若當(dāng)前解大于擾動(dòng)得到的解,返回當(dāng)前解;否則,返回到前一步繼續(xù)進(jìn)行擾動(dòng)交換,直到滿足指定的終止條件。結(jié)合窗口算子后的迭代局部搜索算法圖解如圖6所示。

圖6 結(jié)合窗口算子后的迭代局部搜索算法圖解

2.3 IWINOBS算法構(gòu)建

本文的方法擴(kuò)展了迭代局部搜索的思想,采用增加窗口算子的窗口大小的方式對其進(jìn)行優(yōu)化。IWINOBS算法的最大窗口大小從w=1開始,算法描述如下:

步驟1 對初始節(jié)點(diǎn)序O進(jìn)行局部搜索得到一個(gè)局部最優(yōu)值O′;

步驟2 將固定的迭代次數(shù)P應(yīng)用于局部最優(yōu)節(jié)點(diǎn)序O′,得到新解O″;

步驟3 使用窗口大小為w的窗口算子以更大的搜索步驟在節(jié)點(diǎn)序O″附近繼續(xù)搜索,得到節(jié)點(diǎn)序O?;

步驟4 若節(jié)點(diǎn)序O?沒有滿足終止條件,則返回步驟2繼續(xù)應(yīng)用迭代局部搜索。每次迭代時(shí)再次應(yīng)用窗口算子,并使窗口大小w=w+1,直到滿足指定的終止條件時(shí)停止搜索。

給定初始節(jié)點(diǎn)序時(shí),窗口大小w既影響算子避免局部最優(yōu)值的能力,也會(huì)影響計(jì)算所需的時(shí)間。

IWINOBS算法流程圖如圖7所示,算法的偽代碼如下所示。

圖7 IWINOBS算法流程圖

算法1:IWINOBS

Input:數(shù)據(jù)集D,初始節(jié)點(diǎn)序prime-order,節(jié)點(diǎn)數(shù)n,樣本量ns,固定迭代次數(shù)It,最大窗口大小w

Output: 最優(yōu)節(jié)點(diǎn)序current-order,最優(yōu)節(jié)點(diǎn)序的評分current-score

1. 選擇初始節(jié)點(diǎn)序prime-order的一個(gè)隨機(jī)節(jié)點(diǎn)作為固定索引

2.初始窗口大小w=1;初始迭代次數(shù)It=1;

3.While(It<4)

4.It=It+1;

5.Fori=1:N-2*w+1

6.While(w<=floor(N/2))

7.j=i+w;

8.current-order=prime-order;

9. temp=current-order(i:i+w-1);

10. current-order(i:i+w-1)=current-order(j:j+w-1);

11. current-order(j:j+w-1)=temp;

12. [current-dag,current-score]=learn-struct-K2(data,ns, current-order, ′scoring-fn′,′bic′);

13. If(current-score <=prime-score)

14.w=w+1;

15. Else If(current-score> prime-score)

16. prime-order=current-order

17. prime-score=current-score

18. End if;

19. End while

20. End for;

21.End while;

22.Return current-order,current-score.

3 實(shí)驗(yàn)分析

本文的實(shí)驗(yàn)仿真環(huán)境為MATLAB R2018b,操作系統(tǒng)為Windows 10,CPU為Intel(R) Core(TM) i5-6300U CPU @ 2.40 GHz,RAM為8.00G。為了評價(jià)本文算法的學(xué)習(xí)性能,基于貝葉斯網(wǎng)絡(luò)工具箱FullBNT-1.0.7,使用Asia[17]、Car[18]和Alarm[19]網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)仿真,3個(gè)網(wǎng)絡(luò)的屬性說明如表1所示,標(biāo)準(zhǔn)網(wǎng)絡(luò)結(jié)構(gòu)如圖8所示。

圖8 Asia、Car和Alarm網(wǎng)絡(luò)的結(jié)構(gòu)圖

表1 標(biāo)準(zhǔn)貝葉斯網(wǎng)絡(luò)的參數(shù)

本文仿真實(shí)驗(yàn)對比的項(xiàng)目如下:

1) 算法學(xué)習(xí)效率

算法的學(xué)習(xí)效率用學(xué)習(xí)BN結(jié)構(gòu)所需要的時(shí)間來計(jì)算。

2) 算法學(xué)習(xí)精度

①結(jié)構(gòu)正確率:算法學(xué)習(xí)出的BN結(jié)構(gòu)的邊數(shù)中正確邊數(shù)所占比例。BN結(jié)構(gòu)的邊數(shù)包括錯(cuò)誤邊數(shù)和正確邊數(shù),錯(cuò)誤邊數(shù)是指與標(biāo)準(zhǔn)網(wǎng)絡(luò)結(jié)構(gòu)相比,該算法獲得的網(wǎng)絡(luò)結(jié)構(gòu)的冗余邊數(shù)、反向邊數(shù)和缺失邊數(shù)之和;正確邊數(shù)是指與標(biāo)準(zhǔn)網(wǎng)絡(luò)結(jié)構(gòu)相比,該算法獲得的網(wǎng)絡(luò)結(jié)構(gòu)的正確邊數(shù)。

②BIC評分:即采用該算法得到的網(wǎng)絡(luò)的BIC評分,評分值越高,說明網(wǎng)絡(luò)越好。

3.1 算法學(xué)習(xí)效率的比較

本實(shí)驗(yàn)主要比較隨著節(jié)點(diǎn)數(shù)目的增加,OBS、 IINOBS、IWINOBS算法和網(wǎng)絡(luò)空間下經(jīng)典的BN結(jié)構(gòu)學(xué)習(xí)算法的運(yùn)行時(shí)間。利用Asia、Car和Alarm網(wǎng)絡(luò),分別隨機(jī)生成樣本量為1 000,2 000,3 000,5 000的數(shù)據(jù)集,每種算法分別運(yùn)行10次,記錄算法每次運(yùn)行的時(shí)間,取平均值。實(shí)驗(yàn)結(jié)果如表2～4所示。

表2 Asia網(wǎng)絡(luò)中不同算法的運(yùn)行時(shí)間對比 s

表3 Car網(wǎng)絡(luò)中不同算法的運(yùn)行時(shí)間對比 s

表4 Alarm網(wǎng)絡(luò)中不同算法的運(yùn)行時(shí)間對比 s

通過對比表2～4發(fā)現(xiàn),在算法的運(yùn)行時(shí)間上,K2和HC算法的學(xué)習(xí)時(shí)間明顯高于本文的IWINOBS算法。原因在于K2算法采用遍歷搜索空間來搜索最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu),所以學(xué)習(xí)效率較為低下;HC算法容易陷入局部最優(yōu),因此采用多次運(yùn)行HC算法的方式來避免這個(gè)缺點(diǎn),而爬山次數(shù)的增大也導(dǎo)致了算法學(xué)習(xí)效率明顯降低。

在學(xué)習(xí)有8個(gè)節(jié)點(diǎn)的Asia網(wǎng)絡(luò)時(shí),本文提出的IWINOBS算法的學(xué)習(xí)效率與IINOBS算法相比提高了30.17%,精度沒有變化;與K2算法相比學(xué)習(xí)效率提升了30.96%,精度僅下降了3.41%。在學(xué)習(xí)有12個(gè)節(jié)點(diǎn)的Car網(wǎng)絡(luò)時(shí),本文算法的學(xué)習(xí)效率與IINOBS算法相比提高了45.01%,精度提高了2.33%;與K2算法相比學(xué)習(xí)效率提升了54.12%,精度僅下降了6.38%。在學(xué)習(xí)有37個(gè)節(jié)點(diǎn)的Alarm網(wǎng)絡(luò)時(shí),算法的運(yùn)行時(shí)間大大增加,在學(xué)習(xí)效率方面OBS算法表現(xiàn)較好,與K2算法相比學(xué)習(xí)效率提升了49.26%,學(xué)習(xí)精度僅僅降低了3.45%。

3.2 算法學(xué)習(xí)精度的比較

3.2.1 結(jié)構(gòu)正確率

貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)正確率(structural accuracy,SA)指標(biāo)一般由該算法獲得的網(wǎng)絡(luò)結(jié)構(gòu)的冗余邊數(shù)(redundant edge,RE)、缺失邊數(shù)(missing edge,ME)、反向邊數(shù)(inverted edge,IE)和正確邊數(shù)(correct edge,CE)來衡量,其計(jì)算方法如公式(8)所示。

(8)

為評價(jià)本文算法的求解質(zhì)量,本實(shí)驗(yàn)分別對1 000組Asia、Car和Alarm網(wǎng)絡(luò)進(jìn)行學(xué)習(xí),比較OBS、 IINOBS、IWINOBS和K2算法學(xué)習(xí)結(jié)果的結(jié)構(gòu)正確率。將每種算法分別運(yùn)行10次,記錄每次的學(xué)習(xí)結(jié)果中貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)中冗余邊、缺失邊、反向邊和正確邊的情況,取平均值,算法學(xué)習(xí)結(jié)果對比如表5～7和圖9所示。

表5 Asia網(wǎng)絡(luò)中不同算法的BN結(jié)構(gòu)學(xué)習(xí)結(jié)果對比

表6 Car網(wǎng)絡(luò)中不同算法的BN結(jié)構(gòu)學(xué)習(xí)結(jié)果對比

表7 Alarm網(wǎng)絡(luò)中不同算法的BN結(jié)構(gòu)學(xué)習(xí)結(jié)果對比

圖9 不同算法的BN結(jié)構(gòu)正確率對比

K2算法給定了正確的節(jié)點(diǎn)序作為輸入,因此在學(xué)習(xí)精度方面有著明顯優(yōu)勢。根據(jù)表5～7和圖9可以得出,在學(xué)習(xí)有8個(gè)節(jié)點(diǎn)的小型Asia網(wǎng)絡(luò)時(shí),本文提出的IWINOBS 算法學(xué)習(xí)出的BN結(jié)構(gòu)與K2算法相比結(jié)構(gòu)正確率僅降低3.41%,與IINOBS算法相比無變化;在學(xué)習(xí)有12個(gè)節(jié)點(diǎn)的Car網(wǎng)絡(luò)時(shí),本文算法與K2算法相比結(jié)構(gòu)正確率僅降低了6.38%,與IINOBS算法相比提高了2.33%;在學(xué)習(xí)有37個(gè)節(jié)點(diǎn)的大型Alarm網(wǎng)絡(luò)時(shí),本文算法與K2算法相比結(jié)構(gòu)正確率僅降低了3.45%,與IINOBS算法相比提高了1.19%。通過對比第3.1節(jié)可知,本文算法在提高學(xué)習(xí)效率的同時(shí)能夠?qū)W習(xí)出正確率較高的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。

3.2.2 BIC評分

本實(shí)驗(yàn)主要通過比較不同算法學(xué)習(xí)出的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的BIC評分來評價(jià)該算法的性能。在樣本量為1 000,2 000,3 000,5 000的情況下,分別采用K2、OBS、IINOBS、IWINOBS算法學(xué)習(xí)Asia、Car和Alarm網(wǎng)絡(luò)。考慮到算法的隨機(jī)性,將每種算法分別運(yùn)行10次,并記錄每次結(jié)果的BIC評分,取平均值。實(shí)驗(yàn)結(jié)果如表8所示。

表8 不同算法學(xué)習(xí)出BN結(jié)構(gòu)的BIC評分對比

表8表明,隨著節(jié)點(diǎn)數(shù)的增加,Asia、Car和Alarm網(wǎng)絡(luò)在不同樣本量下采用4種算法學(xué)習(xí)出BN結(jié)構(gòu)的BIC評分之間的差異逐漸變大。其中最優(yōu)BIC評分在表8中用加粗字體表示,可以看出,IWINOBS算法學(xué)習(xí)出的BIC評分總是優(yōu)于K2算法和OBS算法,在大多數(shù)情況下是優(yōu)于IINOBS算法的。對于有8個(gè)節(jié)點(diǎn)的Asia網(wǎng)絡(luò),IWINOBS算法在不同樣本量下學(xué)習(xí)出的BIC評分相較于K2算法分別提高了93.96%,96.20%,97.11%,98.23%,相較于OBS算法分別提高了93.54%,95.87%,97.05%,98.07%;對于有12個(gè)節(jié)點(diǎn)的Car網(wǎng)絡(luò),IWINOBS算法在不同樣本量下學(xué)習(xí)出的BIC評分相較于K2算法分別提高60.45%,61.04%,43.57%,46.72%,相較于OBS算法分別提高了53.48%,53.12%,40.08%,38.18%;對于有37個(gè)節(jié)點(diǎn)的Alarm網(wǎng)絡(luò),IWINOBS算法在不同樣本量下學(xué)習(xí)出的BIC評分相較于K2算法分別提高了55.28%,63.53%,61.47%,68.94%,相較于OBS算法分別提高了21.92%,62.03%,59.72%,68.29%。由此可見,本文提出的IWINOBS算法與網(wǎng)絡(luò)空間下的K2算法相比學(xué)習(xí)效率大大提升,但仍然可以學(xué)習(xí)出到學(xué)習(xí)精度相對理想的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。

4 結(jié) 論

本文將貝葉斯網(wǎng)絡(luò)學(xué)習(xí)問題轉(zhuǎn)化為搜索最優(yōu)節(jié)點(diǎn)序的問題,在節(jié)點(diǎn)序空間中提出了一種迭代局部搜索與窗口插入算子相結(jié)合的BN結(jié)構(gòu)學(xué)習(xí)方法——IWINOBS算法,從而降低了算法陷入局部最優(yōu)狀態(tài)的概率。將本文提出的IWINOBS算法與目前基于節(jié)點(diǎn)序空間的BN結(jié)構(gòu)學(xué)習(xí)性能較好的方法進(jìn)行比較發(fā)現(xiàn),本文算法能得到性能更優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu)。與網(wǎng)絡(luò)空間下的經(jīng)典算法如K2、HC算法進(jìn)行比較發(fā)現(xiàn),在保持算法精度損失較小的情況下,IWINOBS算法的學(xué)習(xí)效率更高。在之后的研究工作中,將進(jìn)一步優(yōu)化節(jié)點(diǎn)序的搜索方法,在大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)中實(shí)現(xiàn)精度損失盡可能小且能夠降低復(fù)雜度,進(jìn)而提升大規(guī)模貝葉斯網(wǎng)絡(luò)的學(xué)習(xí)性能。