基于超結構的BN隨機搜索學習算法

呂亞麗 武佳杰 梁吉業 錢宇華

1(計算智能與中文信息處理教育部重點實驗室(山西大學) 太原 030006) 2(山西財經大學信息管理學院 太原 030006)

(sxlvyali@163.com)

基于超結構的BN隨機搜索學習算法

呂亞麗1,2武佳杰2梁吉業1錢宇華1

1(計算智能與中文信息處理教育部重點實驗室(山西大學) 太原 030006)2(山西財經大學信息管理學院 太原 030006)

(sxlvyali@163.com)

近年來，貝葉斯網絡(Bayesian network, BN)在不確定性知識表示與概率推理方面發揮著越來越重要的作用.其中，BN結構學習是BN推理中的重要問題.然而，在當前BN結構的2階段混合學習算法中，大多存在一些問題：第1階段無向超結構學習中存在容易丟失弱關系的邊的問題；第2階段的爬山搜索算法存在易陷入局部最優的問題.針對這2個問題，首先采用Opt01ss算法學習超結構，盡可能地避免出現丟邊現象;然后給出基于超結構的搜索算子，分析初始網絡的隨機選擇規則和對初始網絡隨機優化策略，重點提出基于超結構的隨機搜索的SSRandom結構學習算法，該算法一定程度上可以很好地跳出局部最優極值;最后在標準Survey， Asia，Sachs網絡上，通過靈敏性、特效性、歐幾里德距離和整體準確率4個評價指標，并與已有3種混合學習算法的實驗對比分析，驗證了該學習算法的良好性能.

貝葉斯網絡；結構學習；隨機搜索；超結構；混合算法

貝葉斯網絡(Bayesian network, BN)模型[1]是人工智能學科表示并處理概率知識的一種重要方法.該模型已被廣泛應用于基因調控、醫療診斷、故障檢測、金融預測分析等方面.其中，BN學習[2-10]是目前BN研究的主要熱點之一，也是該模型推向應用的前提基礎.

BN學習主要包括結構學習[2-7]和參數學習[8-10]2部分.本文主要集中于對其結構學習的研究.目前，對于BN結構學習算法大致可分為3類：

1) 基于約束(constraint based, CB)或者依賴分析的算法[3]，即利用統計學或者信息論中的知識，對變量之間的依賴性進行測試，分析出各變量之間的關系，然后利用這些依賴性關系構建BN模型.該類算法過程比較復雜，但在一些假設下可以得到最優的BN結構，并且算法可具有多項式時間復雜度，該類算法比較適合于建立變量多、網絡稀疏的BN結構學習.

2) 基于評分搜索的算法，即對所有可能的BN結構利用某種優化算法進行搜索，然后對搜索到的BN進行評分[4-5]，以期待找出得分較高的BN結構.該類算法過程簡單規范，但打分函數的運算復雜程度和結構搜索空間大小都隨變量增加呈指數增加，通常以解決時間復雜性高的算法有：①給定節點順序，進行局部打分，如經典的K2算法[6]；②選擇啟發式搜索策略進行整體打分等.該類算法比較適合于變量較少、網絡較稠密的BN結構學習.

3) 目前較為流行的混合學習算法[7,11-12]，該類算法結合上述2類算法的優點，首先基于約束的方法系統檢查條件獨立性關系，得出網絡的基本無向圖框架(skeleton)[7,13]，然后基于此無向圖框架采用評分搜索算法來學習整個BN結構.其中較典型的混合學習算法有MMHC(max-min hill-climbing)[7].在MMHC算法中，首先利用MMPC(max-min parents and children)算法得到網絡的無向圖框架，然后利用爬山算法得到BN結構.但由于MMPC得到的無向圖框架中會丟失應有的一些邊，即存在丟邊問題.另外，對于經典的爬山算法眾所周知的缺點是易陷入局部最優.

2014年，Villanueva和Maciel[14]提出一種有效學習BN超結構(super-structure, SS)的Opt01ss算法，該算法在有限數據情況下，一定程度上可以避免條件獨立性(conditional independence, CI)測試不一致性和近似確定關系(approximate deterministic relationships, ADRs)等問題，盡可能減少了弱關系下邊的丟失問題.因此，本文借鑒文獻[14]中的超結構學習算法，重點研究隨機搜索算法，并考慮解決陷入局部極值問題，提出一種基于超結構的隨機搜索BN結構的混合學習算法.

1 基礎知識

本節主要介紹BN模型與其評價準則、超結構框架及其Opt01ss學習算法.

1.1BN模型與其評價準則

BN模型是圖論和概率論的“結合體”，主要由有向無環圖(directed acyclic graph, DAG)結構和每個節點相對應的條件概率分布表(conditional probability table, CPT)組成.該模型可形式化表示成M=(G,P)，其中G=(V,E)表示BN的DAG結構.V表示節點變量;E表示邊集，反映變量間的相互依賴關系;P表示每個節點相對應的CPT集合，反映父子節點變量之間的依賴程度.

給定數據集D，BN結構學習指從數據中獲得與數據集D擬合程度較好的DAG結構.評價網絡結構與樣本數據擬合程度的函數稱為評分函數.常見的評分函數有多種，如貝葉斯信息評分準則(BIC)[15]、CH評分[6]、最小描述長度(MDL)[5]等，這里簡單介紹本文所采用的BIC評分函數，該函數的評分越高，說明從數據中獲得的DAG網絡結構越好.其具體形式為

1.2超結構

對BN結構的混合學習算法，一般來說，首先基于約束關系構建出其無向框架圖，即其超結構SS；然后在SS的基礎上運用搜索評分方法優化BN結構，得到評分較高的網絡.

定義1. 超結構SS[13-14].對于一個DAGG， 若一個無向圖包含G去掉方向之后的所有邊，即完全包含該DAG的基本架構，則稱該無向圖是G的一個完全超結構，否則稱為不完全超結構.若無特別說明，本文均指完全超結構.

近年來，許多學者研究了BN超結構的學習算法[13-14,16].其中，Villanueva和Maciel[14]提出的Opt01ss算法取得了較好的效果.該算法解決了在樣本量有限的情況下，其他超結構學習算法容易出現的2個問題：1)CI測試不一致的問題；2)如圖1所示的ADRs問題，即避免了存在較弱關系的邊的丟失問題，保留了盡可能多的邊.

Fig. 1 An example to illustrate ADR problem圖1 ADR問題解釋示例

由此，本文采用該Opt01ss算法思想獲得BN超結構，然后重點進行隨機搜索找出較優的BN結構.

2 基于SS的隨機搜索學習算法SSRandom

在基于Opt01ss算法獲得SS的基礎上，本節主要針對爬山算法中網絡最終結果對初始結構的依賴度大，導致易陷入局部極值的問題，研究基于SS的隨機搜索算法.具體地，首先介紹基于SS的3種搜索算子，然后分析基于SS的初始網絡的隨機選取規則，接著討論使得初始網絡避免陷入局部極值的隨機優化策略，進一步提出基于SS的隨機搜索(random search based on SS, SSRandom)的學習算法.

2.1基于SS的搜索算子

由于本文第1階段得出的SS已包含最優BN去掉方向后的所有邊，因此，候選DAG的3個搜索算子主要指：

1) 添方向算子，記作OAdd.該算子不同于爬山法中的加邊算子，它指將超結構中的邊加一個方向后添加到當前DAG中.

2) 減邊算子，記作OSub.即在當前DAG中減去一條邊.

3) 轉方向算子，記作ORev.即將當前DAG中的一條邊的方向進行翻轉.

需要注意的是：與爬山法相同，加邊和轉邊的前提是保證該圖仍保持無環，即保持候選網絡仍是DAG結構.

2.2基于SS的初始網絡的隨機選取規則

定義2. 基于SS的隨機DAG——SSRDAG.通過基于SS的3種搜索算子，對某DAG隨機進行一步或多步OAdd，OSub，ORev操作后得到的DAG，即稱為該DAG基于SS的隨機DAG，記作SSRDAG.

在爬山法中，其初始網絡是一個無邊圖，在無邊圖的基礎上進行一步搜索選擇得分較高的候選網絡作為當前網絡，并在此基礎上繼續優化.可知，初始無邊網絡相對距離最優網絡較遠.本文探討的初始網絡是距離最優網絡要較近的網絡.為了加快搜索，我們初始網絡的選擇是保留SS的所有邊，只是在不形成環路的前提下，給每條無向邊通過OAdd算子隨機添加一個方向，并隨機搜索m次，得出m個SSRDAGs，并將BIC得分最高的SSRDAG作為初始模型G0.可知，該初始網絡的選擇較爬山法來說有2個好處：1)離最優網絡更近了一步；2)初始網絡是m個中根據得分函數選出的，自然這時選擇的初始網絡相對較優.

2.3對初始網絡的隨機優化策略

由于初始網絡G0中已包含SS中的所有無向邊，因而對其優化時只需要考慮減邊OSub和轉方向ORev操作，不需要添方向OAdd操作.初始優化時，首先將初始G0作為當前需優化的模型G*，然后隨機選擇OSub和ORev操作m次，得到m個SSRDAGs，即得出m個候選的G*j(1≤j≤m)，并對當前G*和候選的G*j(1≤j≤m)共m+1個SSRDAGs按BIC得分進行非升序排列，將得分最高網絡記為當前網絡模型G*.

為了繼續優化當前網絡G*，并考慮避免結果陷入局部最優，文中引入2個SSRDAGs隨機交叉的概念.

定義3. 2個SSRDAGs的隨機交叉.對于2個SSRDAGs模型，其隨機交叉指隨機選擇1對節點或多對節點，并互相交叉選定的邊后得到2個新SSRDAGs的操作.

例1. 對于常見的一個關于年齡A、性別G、抽煙S和肺癌LC的BN實例，已知其DAG結構包括的有向邊有A,S，G,S，S,LC，下面以該網絡的一個包含無向邊(A,S)，(A,G)，(G,S)，(S,LC)，(G,LC)的SS為例來詳細說明其2個SSRDAGs的隨機交叉操作.

Fig. 2 Two SSRDAGs and their random cross results圖2 兩個SSRDAGs與其隨機交叉結果

對于圖2(a)(b)中的2個SSRDAGs，假設我們隨機選擇了節點對(A,G)和(S,LC)，并互相交叉它們邊的情況，得出如圖2(c)(d)所示的2個新SSRDAGs.

進一步在m+1個排好序的模型中，隨機選取排序的前2個模型中的一個，記為G*，并與后面m-1個中的一個模型隨機交叉.這樣與得分較低網絡的隨機交叉的目的是以一定的概率接受低分網絡，跳出對當前網絡的過度依賴，避免陷入局部極值.并且每次交叉后保留2個SSRDAGs中得分較高的那個模型，這樣的隨機循環搜索共進行m次，并將每次搜索結果記為G*k(1≤k≤m).接著，對m個G*k(1≤k≤m)模型中最高得分與G*的得分相比較，用高分網絡替代當前網絡G*.一直循環，直至達到循環結束條件，最后得出優化的BN模型的DAG結構.

2.4SSRandom學習算法

BN結構學習的SSRandom算法的目標是基于SS隨機搜索出BIC得分較高的BN模型的DAG.大致分為3個步驟:

Step1. 基于Opt01ss算法獲得BN的SS；

Step2. 在SS基礎上，對所有無向邊隨機使用OAdd算子添加方向，獲得得分最高的初始模型G0作為當前模型G*；

Step3. 通過減邊算子OSub和轉方向算子ORev對G*隨機進行m次優化，并將高分網絡與低分網絡進行隨機交叉，允許以一定的概率接受低分網絡，避免結果陷入局部最優，循環得出優化的BN結構.

其偽代碼描述如算法1所示：

算法1.SSRandom算法.

輸入:數據集D、循環次數n、隨機搜索次數m；

輸出:優化后BN的DAGG結構.

通過Opt01ss算法從數據集D中獲得超結構SS；

while循環次數n或循環條件滿足do

fori=1tomdo

通過OAdd算子，隨機獲得m個SSRDAGs模型(G1,G2,…,Gm)，這些模型去掉邊后均包含SS中的所有邊；

endfor

當前模型G*←G0；

forj=1tomdo

隨機通過OSub和ORev算子，優化G*，獲得SSRDAGsG*j；

endfor

Sort(G*,G*1,G*2,…,G*m)，即按BIC得分，對m+1個SSRDAGs非升序排列；

G*←Sort中最高得分的網絡；

fork=1tomdo

G*←從G*和Sort中次高得分的網絡中隨機選一個網絡；

G*與剩余m-1個中的任意一個進行隨機交叉，得2個SSRDAGs網絡G1*k和G2*k；

G*k←argmax(fBIC(G1*k),fBIC(G2*k))；

endfor

endif

endwhile

returnG ←G*.

2.5時間復雜性分析

在SSRandom算法中，在SS基礎上的隨機搜索部分，第1個for循環是隨機選擇初始網絡，其時間復雜度為O(m)，m表示隨機搜索次數.Sort排序算法用快速排序時，其時間復雜性為O(mlogm)，其中m表示m次隨機搜索后獲得的m個網絡.第2個和第3個for循環是隨機優化初始網絡，其時間復雜度均為O(m).因而，整個隨機搜索算法部分時間復雜度為O(mlogm).

1) 蠻力法.由于要對無向圖中的e條邊定向，而每條邊的定向情況有2種，因而最終的網絡搜索空間為2e，故其時間復雜度為O(2e).

2) 爬山法.由于其搜索網絡空間為搜索算子對當前網絡的一次加邊、或減邊、或轉邊后得到的網絡集合，易知，在SS的基礎上，有i(0≤i≤e)條有向邊的當前網絡的候選網絡個數為

2e=2(e-i)+i+i，

其中，(e-i)表示一次加邊產生的網絡個數，2個i分別表示一次減邊和一次轉邊后產生的網絡個數，因而i取e種情況下共有2e2個候選網絡，故其時間復雜度為O(e2).

由此，在SS基礎上3種算法的時間復雜度分別如表1所示：

Table 1 The Time Complexity Comparison表1 時間復雜性對比

Notes:mis the number of random search, andeis the number of undirected edge in SS.

通常，大多情況下BN的有向邊數均會大于節點數|V|，因而一般混合學習算法第1階段得出的SS的無向邊數egt;|V|，或至少也會接近|V|.隨著網絡變量數增加，蠻力法和爬山法的搜索空間會較隨機搜索算法的搜索空間快速增加，從本文第3節實驗也可得到，當|V|分別為6，8，11且本文的隨機搜索次數m=10時，大多情況下已比其他BN結構算法學到的結果要好.可見，該隨機搜索策略要比通常基于評分搜索的算法高效.

3 實驗結果與分析

本節在標準數據集上，通過將本文所提算法以及已有的3種BN結構學習算法，分別與標準結果在4方面評估指標上的對比分析，驗證本文所提算法的學習性能.

3.1實驗環境與數據集

實驗運行環境為：操作系統Windows 7、處理器Intel?CoreTMi7-4510U CPU@2.00 GHz、內存4.00 GB.

所有實驗在R語言環境中借助于R語言自帶的bnlearn工具包[17]實現.實驗選用標準的Survey，Asia，Sachs三個網絡[17]，其網絡結構情況如表2所示.實驗中具體所用數據均是通過這些基準網絡經過邏輯抽樣后得出的模擬數據.

Table 2 Three Standard Structures of BNs Used in the Experiments

3.2評價指標

BN結構的學習結果通過靈敏性Sn(sensitivity)、特效性Sp(specificity)、歐幾里德距離Ed(Euclidean distance)[14]以及本文定義的整體準確率Pa(percentage of overall accuracy)四個指標進行評價.各指標具體描述如下：

1) 靈敏性Sn.反映正確學到的邊占實際邊的比率，該指標值越大越好.其格式化表示為

其中，TP表示基準網絡中有邊而且也學出的邊的個數，即正確學出的邊的個數；FN表示基準網絡中有邊但沒有學出的邊的個數，即丟失邊的個數.

2) 特效性Sp.反映正確學出的無邊占實際無邊的比率，該指標值越大越好.其格式化表示為

其中，FP表示基準網絡中無邊但學出有邊的個數，即冗余邊的個數；TN表示基準網絡中無邊而且學出無邊的個數，即正確學出無邊的個數.

3) 歐幾里德距離Ed.反映學出網絡與真實網絡之間在歐氏空間的差距，該指標值越小越好.其格式化表示為

4) 整體準確率Pa.主要通過正確學出的有向邊和正確學習的無邊的比率來度量學習所得的網絡結構的整體準確度，該指標值越大越好.其格式化表示為

3.3結果對比與分析

實驗主要對比本文所提的SSRandom算法和已有的MMHC,Hiton+HC (bnlearn工具包自帶的Hiton和HC搜索策略的混合)、GS+HC (bnlearn自帶的Grow-Shrink和HC的混合)三種結構學習算法在Survey，Asia，Sachs網絡上的實驗結果，對比指標主要有Sn，Sp，Ed，Pa四個.

由于本文所提方法還涉及到算法的循環次數n和隨機搜索次數m的設置.因而實驗中，對于n的取值，考慮n=100和n=300這2種情況；對于m的取值，考慮m=10和m=30這2種情況.

對于SSRandom算法，每種情況下學習5次進行平均;對于其他3種算法，并不涉及這些參數，所以不需要分情況討論.因而在每種情況下，在每次運行SSRandom算法的相同數據集上，同時運行其他3種算法學習BN結構，即它們是20(即4×5)次或5次的平均.具體實驗結果如表3～5，粗體數字表示每個指標下最好的實驗結果.

Table 3 Comparison Between SSRandom and Other Three Algorithms on the Dataset of Size 5 000表3 樣本容量為5 000時SSRandom與其他3種算法的實驗結果對比

Table 4 Comparison Between SSRandom and Other Three Algorithms on the Dataset of Size 2 000表4 樣本容量為2 000時SSRandom與其他3種算法的實驗結果對比

Notes: The results of each algorithm are the average of 5 times.

Table 5 Comparison Between SSRandom and Other Three Algorithms on the Dataset of Size 10 000

Note: The results of each algorithm are the average of 5 times.

從表3可看出，樣本量達5 000時，分別在(n=100,m=10)，(n=100,m=30)，(n=300,m=10)，(n=300,m=30)四種情況下，除Survey網絡上的Sp和Asia網絡上GS+HC方法的Sp外，SSRandom算法在4種指標下均比其他3種算法效果好，其Pa結果在Survey和Asia網絡上可達90%以上，在Sachs網絡上可達近80%，但其他3種算法在Sachs網絡上的Pa效果卻在63%及其以下.而且可統計出SSRandom算法循環次數n=300時的結果中有83.3%(1012)的要比n=100時好，具體可通過每個網絡上n=300與n=100在m=10和m=30 共4種組合下的比較統計得出.同理得出m=30時中有75%(912)的結果要比m=10時的好.

下面進一步對樣本量減少和增加時，4種學習算法的性能進行對比分析.首先看樣本量減少的情況，由于樣本量為5 000時，SSRandom算法在4種指標下的學習結果大多好于其他3種算法，而且在n=300時的整體效果要比n=100時的好，在m=30時的整體效果要比m=10時的好.因而，當樣本量減少為2 000時，考慮SSRandom算法在(n=300,m=30)情況時與其他3種算法的實驗結果進行對比分析，同樣，每次在樣本量為2 000的相同數據集上運行，共實驗5次后求平均.具體如表4所示.

從表4可知，除部分Sp外，本文SSRandom算法性能在其他指標下均比樣本量為5 000時有所下降，但仍比其他3種算法要好.而且從實驗數據上看，所有Pa均可達78%以上，但其他3種算法，尤其在Sachs網絡上的Pa效果卻在55%以下.因此，本文算法與其他算法相比，仍較適合樣本量2 000時進行BN結構的學習.接著，看樣本量增加的情況.同理，由于樣本量為5 000時，SSRandom算法的學習效果較好，所以當樣本量增加為10 000時，我們只考慮SSRandom算法在(n=100,m=10)情況時與其他3種算法5次平均的實驗結果進行對比分析，具體如表5所示.

從表5可知，除Asia網絡上的Sp外，SSRandom算法在其他情況下的學習結果比其他3種算法的結果要好或一樣好.而且從實驗數據整體上來看，4種算法的學習結果較之前樣本量為2 000和5 000時均有所提高.但對于其他3種算法，在Sachs網絡上的Pa效果仍在60%以下，而本文SSRandom算法可提高到83%以上.

進一步，從表3～5中，分析3個樣本量情況下Sachs網絡的學習結果.由表2可知，Sachs網絡最大度為7，較Survey和Asia網絡來說，該網絡更易產生ADRs問題，丟失較多弱關系邊；而本文算法在有限樣本情況下，可以較好處理這一問題，而且在后續學習階段該算法可以一定概率較好地避免使學習結果陷入局部最優等不足，從而使得學習結果相對理想，提高了實驗結果的Pa.另外，從表3～5可得出，4種算法在不同網絡上的各指標效果與不同樣本量的關系，具體如圖3所示.

從圖3(a)～(l)明顯可知，隨著樣本量的增加，除特效性Sp外，3個網絡在各評價指標下4種算法的性能均在增加.雖然反映正確學出的無邊的特效性Sp的性能有所下降，但關聯到Sp的整體準確率的Pa和歐幾里德距離Ed指標下的性能仍是增加的.并且可看出本文的SSRandom算法在每個樣本量下與其他方法相比，整體上效果較好.更重要的是，當樣本量為2 000時，較其他網絡而言，就可學出很好的網絡結構，尤其對于Survey網絡；當樣本量從2 000增加至5 000時，SSRandom算法的其各項性能增加得較為明顯，很快就可增加至近似最好結果；當樣本量從5 000增加至10 000時，其增長趨勢相對平緩一些，這說明了本文SSRandom算法與其他3種算法相比，在較少樣本量的情況下，可以較好地學得網絡結構.

Fig. 3 The relationship between each evaluation index and sample size in Survey, Aisa and Sachs networks, respectively圖3 各評價指標與樣本量分別在Survey, Aisa, Sachs網絡上的關系

4 結束語

本文針對BN結構混合學習算法中超結構構建時容易丟失邊和空間搜索時爬山法易陷入局部最優等問題，通過采用Opt01ss算法學習超結構，以盡可能地避免了出現丟失邊的問題；接著重點研究了基于超結構隨機搜索的SSRandom學習算法，該隨機算法可以一定的概率跳出局部最優.通過在標準網絡上多種樣本量情況下4種評價指標上的實驗，驗證了該算法的良好學習性能.進一步的研究工作將面向高維小樣本數據探討BN結構的隨機學習方法.

[1]Pearl J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[M]. San Mateo, CA: Morgan Kaufmann, 1988

[2]Bouhamed H, Masmoudi A, Lecroq T, et al. Structure space of Bayesian networks is dramatically reduced by subdividing it in sub-networks[J]. Journal of Computational and Applied Mathematics, 2015, 287: 48-62

[3]Cheng J, Greiner R, Kelly J. Learning Bayesian networks from data: An information-theory based approach[J]. Artificial Intelligence, 2002, 137(12): 43-90

[4]De Campos L M. A scoring function for learning Bayesian networks based on mutual information and conditional independence tests[J]. Journal of Machine Learning Research, 2006, 7(2): 2149-2187

[5]Lam W, Bacchus F. Learning Bayesian belief networks: An approach based on the MDL principle[J]. Computational Intelligence, 1994, 10(3): 269-293

[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]Tsamardinos I, Brown L E, Aliferis C F. The max-min hill-climbing Bayesian network structure learning algorithm[J]. Machine Learning, 2006, 65(1): 31-78

[8]Masegosa A R, Feelders A J, Gaag L C. Learning from incomplete data in Bayesian networks with qualitative influences[J]. International Journal of Approximate Reasoning, 2015, 69: 18-34

[9]Yao Tiansheng, Choi A, Darwiche A. Learning Bayesian network parameters under equivalence constraints[J]. Artificial Intelligence, 2015, 29(9): 1349-1354

[10]Liao Wenhui, Ji Qiang. Learning Bayesian network parameters under incomplete data with domain knowledge[J]. Pattern Recognition, 2009, 42(11): 3046-3056

[11]Masegosa A R, Moral S. New skeleton-based approaches for Bayesian structure learning of Bayesian networks[J]. Applied Soft Computing, 2013, 13(2): 1110-1120

[12]GaSSe M, AuSSem A, Elghazel H. A hybrid algorithm for Bayesian network structure learning with application to multi-label learning[J]. Expert Systems with Applications 2014, 41(15): 6755-6772

[13]Perrier E, Imoto S, Miyano S. Finding optimal Bayesian network given a super-structure[J]. Journal of Machine Learning Research, 2008, 9(4): 2251-2286

[14]Villanueva E, Maciel C. Efficient methods for learning Bayesian network super-structures[J]. Neurocomputing, 2014, 123: 3-12

[15]L?hdesm?ki H, Shmulevich I. Learning the structure of dynamic Bayesian networks from time series and steady state measurements[J]. Machine Learning, 2008, 71(2): 185-217

[16]Villanueva E, Maciel C. Optimized algorithm for learning Bayesian network super-structures[COL]Proc of the ICPRAM’12. 2012 [2016-07-01]. https:www.researchgate.netpublication289765566_Optimized_algorithm_for_learning_Bayesian_network_super-structures?ev=auth_pub

[17] Scutari M. Learning Bayesian networks with the bnlearn R package[J]. Journal of Statistical Software, 2010, 35(3): 1-22

LüYali, born in 1975. PhD. Associate professor. Member of CCF. Her main research interests include probabilistic reasoning, data mining and machine learning.

WuJiajie, born in 1989. Master candidate. Student member of CCF. His main research interests include machine learning and probabilistic reasoning(sxcjdxjsjw@163.com).

LiangJiye, born in 1962. Professor and PhD supervisor. Distinguished member of CCF. His main research interests include granular computing, data mining and machine learning(ljy@sxu.edu.cn).

QianYuhua, born in 1976. Professor and PhD supervisor. Member of CCF. His main research interests include granular computing, social computing and machine learning for big data(jinchengqyh@126.com).

RandomSearchLearningAlgorithmofBNBasedonSuper-Structure

Lü Yali1,2, Wu Jiajie2, Liang Jiye1, and Qian Yuhua1

1(Key Laboratory of Computational Intelligence and Chinese Information Processing (Shanxi University), Ministry of Education, Taiyuan 030006)2(School of Information Management, Shanxi University of Finance amp; Economics, Taiyuan 030006)

Recently, Bayesian network(BN) plays a vital role in knowledge representation and probabilistic inference. BN structure learning is crucial to research on BN inference. However, there are some disadvantages in the most two-stage hybrid learning method of BN structure: it is easy to lose edges with weak relationship in the first stage, when we learn the super-structure; hill climbing search method is easily plunged into local optimum in the second stage. To avoid the two disadvantages, the super-structure of BN is firstly learned by Opt01ss algorithm, which makes the result miss few edges as much as possible. Secondly, based on super-structure, three search operators are given to analyze the random selection rule of the initial network and address the random optimization strategy for the initial network. Further, SSRandom learning algorithm of BN structure is proposed. The algorithm is a good way to jump out of local optimum extremum to a certain extent. Finally, the learning performance of the proposed SSRandom algorithm is verified by the experiments on the standard Survey, Asia and Sachs networks, by comparing with other three hybrid algorithms according to four evaluation indexs, such as the sensitivity, specificity, Euclidean distance and the percentage of overall accuracy.

Bayesian network (BN); structure learning; random search; super-structure; hybrid algorithm

2016-09-20；

2017-02-21

國家自然科學基金重點項目(61432011)；軍民共用重大研究計劃聯合基金重點項目(U1435212)；國家自然科學基金優秀青年科學基金項目(61322211)；國家自然科學基金項目(61672332)；中國博士后科學基金項目(2016M591409)；山西省自然科學基金項目(2013011016-4，2014011022-2)

This work was supported by the Key Program of the National Natural Science Foundation of China (61432011), the Key Program of Plan Joint Foundation for Military and Civilian Sharing Major Research (U1435212), the National Natural Science Foundation of China for Excellent Young Scientists (61322211), the National Natural Science Foundation of China (61672332), the China Postdoctoral Science Foundation (2016M591409), and the Natural Science Foundation of Shanxi Province (2013011016-4, 2014011022-2).

TP18