一種優化節點序搜索算子的BN結構學習方法

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

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

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

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

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

1 貝葉斯網絡結構學習

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

圖1 一個貝葉斯網絡模型

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

(1)

(2)

由公式(2)可知,對于結構G,其評分s(G,D)僅依賴于節點Xi和Xi的父節點集Pa(Xi)。

本文采用BIC作為評分函數,它與DAG的后驗概率成正比。BIC評分是可分解的,可以表示成各個節點的評分之和,如公式(3)所示。

(3)

2 IWINOBS算法研究

基于節點序的OBS算法將BN結構學習問題轉化為搜索最優節點序的問題,可以顯著縮小搜索空間[12]。給定節點序,關于該節點序的最佳網絡結構可以在O(Ck)時間內找到,其中,表示最大入度,節點Xi的最優父節點集為

(4)

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

2.1 節點序空間中的局部搜索算子

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

圖2 節點E和D在節點序中交換位置

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

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

(5)

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

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

圖3 節點E被插入到節點B的位置

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

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

(6)

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

插入算子可以被看作是多次相鄰節點交換操作的結果,如圖4所示。每次使用交換相鄰算子只需要重新計算被交換的2個節點的父節點集合,因此,插入算子也可以只重新計算有限數量的父節點集合。

圖4 插入算子的具體執行方式

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

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

窗口算子在另一個節點的前面插入多個節點,通過同時改變多個節點的索引來更新節點序,所有改變的節點必須是相鄰的,因此局部搜索的范圍會進一步擴大。窗口算子也可以通過一系列插入算子來實現,其規則如公式(7)所示,示例如圖5所示。

Owindow(i,j,w):

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

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

(7)

由圖5可知,給定節點序,使用一次窗口算子會產生(n-(w-1))·(n-w)個候選節點序。窗口

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

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

2.2 節點序的迭代局部搜索方法

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

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

2.3 IWINOBS算法構建

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

步驟1 對初始節點序O進行局部搜索得到一個局部最優值O′;

步驟2 將固定的迭代次數P應用于局部最優節點序O′,得到新解O″;

步驟3 使用窗口大小為w的窗口算子以更大的搜索步驟在節點序O″附近繼續搜索,得到節點序O?;

步驟4 若節點序O?沒有滿足終止條件,則返回步驟2繼續應用迭代局部搜索。每次迭代時再次應用窗口算子,并使窗口大小w=w+1,直到滿足指定的終止條件時停止搜索。

給定初始節點序時,窗口大小w既影響算子避免局部最優值的能力,也會影響計算所需的時間。

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

圖7 IWINOBS算法流程圖

算法1:IWINOBS

Input:數據集D,初始節點序prime-order,節點數n,樣本量ns,固定迭代次數It,最大窗口大小w

Output: 最優節點序current-order,最優節點序的評分current-score

1. 選擇初始節點序prime-order的一個隨機節點作為固定索引

2.初始窗口大小w=1;初始迭代次數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 實驗分析

本文的實驗仿真環境為MATLAB R2018b,操作系統為Windows 10,CPU為Intel(R) Core(TM) i5-6300U CPU @ 2.40 GHz,RAM為8.00G。為了評價本文算法的學習性能,基于貝葉斯網絡工具箱FullBNT-1.0.7,使用Asia[17]、Car[18]和Alarm[19]網絡進行實驗仿真,3個網絡的屬性說明如表1所示,標準網絡結構如圖8所示。

圖8 Asia、Car和Alarm網絡的結構圖

表1 標準貝葉斯網絡的參數

本文仿真實驗對比的項目如下:

1) 算法學習效率

算法的學習效率用學習BN結構所需要的時間來計算。

2) 算法學習精度

①結構正確率:算法學習出的BN結構的邊數中正確邊數所占比例。BN結構的邊數包括錯誤邊數和正確邊數,錯誤邊數是指與標準網絡結構相比,該算法獲得的網絡結構的冗余邊數、反向邊數和缺失邊數之和;正確邊數是指與標準網絡結構相比,該算法獲得的網絡結構的正確邊數。

②BIC評分:即采用該算法得到的網絡的BIC評分,評分值越高,說明網絡越好。

3.1 算法學習效率的比較

本實驗主要比較隨著節點數目的增加,OBS、 IINOBS、IWINOBS算法和網絡空間下經典的BN結構學習算法的運行時間。利用Asia、Car和Alarm網絡,分別隨機生成樣本量為1 000,2 000,3 000,5 000的數據集,每種算法分別運行10次,記錄算法每次運行的時間,取平均值。實驗結果如表2～4所示。

表2 Asia網絡中不同算法的運行時間對比 s

表3 Car網絡中不同算法的運行時間對比 s

表4 Alarm網絡中不同算法的運行時間對比 s

通過對比表2～4發現,在算法的運行時間上,K2和HC算法的學習時間明顯高于本文的IWINOBS算法。原因在于K2算法采用遍歷搜索空間來搜索最優網絡結構,所以學習效率較為低下;HC算法容易陷入局部最優,因此采用多次運行HC算法的方式來避免這個缺點,而爬山次數的增大也導致了算法學習效率明顯降低。

在學習有8個節點的Asia網絡時,本文提出的IWINOBS算法的學習效率與IINOBS算法相比提高了30.17%,精度沒有變化;與K2算法相比學習效率提升了30.96%,精度僅下降了3.41%。在學習有12個節點的Car網絡時,本文算法的學習效率與IINOBS算法相比提高了45.01%,精度提高了2.33%;與K2算法相比學習效率提升了54.12%,精度僅下降了6.38%。在學習有37個節點的Alarm網絡時,算法的運行時間大大增加,在學習效率方面OBS算法表現較好,與K2算法相比學習效率提升了49.26%,學習精度僅僅降低了3.45%。

3.2 算法學習精度的比較

3.2.1 結構正確率

貝葉斯網絡結構正確率(structural accuracy,SA)指標一般由該算法獲得的網絡結構的冗余邊數(redundant edge,RE)、缺失邊數(missing edge,ME)、反向邊數(inverted edge,IE)和正確邊數(correct edge,CE)來衡量,其計算方法如公式(8)所示。

(8)

為評價本文算法的求解質量,本實驗分別對1 000組Asia、Car和Alarm網絡進行學習,比較OBS、 IINOBS、IWINOBS和K2算法學習結果的結構正確率。將每種算法分別運行10次,記錄每次的學習結果中貝葉斯網絡結構中冗余邊、缺失邊、反向邊和正確邊的情況,取平均值,算法學習結果對比如表5～7和圖9所示。

表5 Asia網絡中不同算法的BN結構學習結果對比

表6 Car網絡中不同算法的BN結構學習結果對比

表7 Alarm網絡中不同算法的BN結構學習結果對比

圖9 不同算法的BN結構正確率對比

K2算法給定了正確的節點序作為輸入,因此在學習精度方面有著明顯優勢。根據表5～7和圖9可以得出,在學習有8個節點的小型Asia網絡時,本文提出的IWINOBS 算法學習出的BN結構與K2算法相比結構正確率僅降低3.41%,與IINOBS算法相比無變化;在學習有12個節點的Car網絡時,本文算法與K2算法相比結構正確率僅降低了6.38%,與IINOBS算法相比提高了2.33%;在學習有37個節點的大型Alarm網絡時,本文算法與K2算法相比結構正確率僅降低了3.45%,與IINOBS算法相比提高了1.19%。通過對比第3.1節可知,本文算法在提高學習效率的同時能夠學習出正確率較高的貝葉斯網絡結構。

3.2.2 BIC評分

本實驗主要通過比較不同算法學習出的貝葉斯網絡結構的BIC評分來評價該算法的性能。在樣本量為1 000,2 000,3 000,5 000的情況下,分別采用K2、OBS、IINOBS、IWINOBS算法學習Asia、Car和Alarm網絡。考慮到算法的隨機性,將每種算法分別運行10次,并記錄每次結果的BIC評分,取平均值。實驗結果如表8所示。

表8 不同算法學習出BN結構的BIC評分對比

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

4 結 論

本文將貝葉斯網絡學習問題轉化為搜索最優節點序的問題,在節點序空間中提出了一種迭代局部搜索與窗口插入算子相結合的BN結構學習方法——IWINOBS算法,從而降低了算法陷入局部最優狀態的概率。將本文提出的IWINOBS算法與目前基于節點序空間的BN結構學習性能較好的方法進行比較發現,本文算法能得到性能更優的網絡結構。與網絡空間下的經典算法如K2、HC算法進行比較發現,在保持算法精度損失較小的情況下,IWINOBS算法的學習效率更高。在之后的研究工作中,將進一步優化節點序的搜索方法,在大規模網絡結構學習中實現精度損失盡可能小且能夠降低復雜度,進而提升大規模貝葉斯網絡的學習性能。