呂亞麗 武佳杰 梁吉業(yè) 錢宇華

1(計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室(山西大學(xué)) 太原 030006) 2(山西財(cái)經(jīng)大學(xué)信息管理學(xué)院 太原 030006)

(sxlvyali@163.com)

基于超結(jié)構(gòu)的BN隨機(jī)搜索學(xué)習(xí)算法

呂亞麗1,2武佳杰2梁吉業(yè)1錢宇華1

1(計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室(山西大學(xué)) 太原 030006)2(山西財(cái)經(jīng)大學(xué)信息管理學(xué)院 太原 030006)

(sxlvyali@163.com)

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

貝葉斯網(wǎng)絡(luò)；結(jié)構(gòu)學(xué)習(xí)；隨機(jī)搜索；超結(jié)構(gòu)；混合算法

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

BN學(xué)習(xí)主要包括結(jié)構(gòu)學(xué)習(xí)[2-7]和參數(shù)學(xué)習(xí)[8-10]2部分.本文主要集中于對(duì)其結(jié)構(gòu)學(xué)習(xí)的研究.目前，對(duì)于BN結(jié)構(gòu)學(xué)習(xí)算法大致可分為3類：

1) 基于約束(constraint based, CB)或者依賴分析的算法[3]，即利用統(tǒng)計(jì)學(xué)或者信息論中的知識(shí)，對(duì)變量之間的依賴性進(jìn)行測(cè)試，分析出各變量之間的關(guān)系，然后利用這些依賴性關(guān)系構(gòu)建BN模型.該類算法過程比較復(fù)雜，但在一些假設(shè)下可以得到最優(yōu)的BN結(jié)構(gòu)，并且算法可具有多項(xiàng)式時(shí)間復(fù)雜度，該類算法比較適合于建立變量多、網(wǎng)絡(luò)稀疏的BN結(jié)構(gòu)學(xué)習(xí).

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

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

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

1 基礎(chǔ)知識(shí)

本節(jié)主要介紹BN模型與其評(píng)價(jià)準(zhǔn)則、超結(jié)構(gòu)框架及其Opt01ss學(xué)習(xí)算法.

1.1BN模型與其評(píng)價(jià)準(zhǔn)則

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

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

1.2超結(jié)構(gòu)

對(duì)BN結(jié)構(gòu)的混合學(xué)習(xí)算法，一般來說，首先基于約束關(guān)系構(gòu)建出其無向框架圖，即其超結(jié)構(gòu)SS；然后在SS的基礎(chǔ)上運(yùn)用搜索評(píng)分方法優(yōu)化BN結(jié)構(gòu)，得到評(píng)分較高的網(wǎng)絡(luò).

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

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

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

由此，本文采用該Opt01ss算法思想獲得BN超結(jié)構(gòu)，然后重點(diǎn)進(jìn)行隨機(jī)搜索找出較優(yōu)的BN結(jié)構(gòu).

2 基于SS的隨機(jī)搜索學(xué)習(xí)算法SSRandom

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

2.1基于SS的搜索算子

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

1) 添方向算子，記作OAdd.該算子不同于爬山法中的加邊算子，它指將超結(jié)構(gòu)中的邊加一個(gè)方向后添加到當(dāng)前DAG中.

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

3) 轉(zhuǎn)方向算子，記作ORev.即將當(dāng)前DAG中的一條邊的方向進(jìn)行翻轉(zhuǎn).

需要注意的是：與爬山法相同，加邊和轉(zhuǎn)邊的前提是保證該圖仍保持無環(huán)，即保持候選網(wǎng)絡(luò)仍是DAG結(jié)構(gòu).

2.2基于SS的初始網(wǎng)絡(luò)的隨機(jī)選取規(guī)則

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

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

2.3對(duì)初始網(wǎng)絡(luò)的隨機(jī)優(yōu)化策略

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

為了繼續(xù)優(yōu)化當(dāng)前網(wǎng)絡(luò)G*，并考慮避免結(jié)果陷入局部最優(yōu)，文中引入2個(gè)SSRDAGs隨機(jī)交叉的概念.

定義3. 2個(gè)SSRDAGs的隨機(jī)交叉.對(duì)于2個(gè)SSRDAGs模型，其隨機(jī)交叉指隨機(jī)選擇1對(duì)節(jié)點(diǎn)或多對(duì)節(jié)點(diǎn)，并互相交叉選定的邊后得到2個(gè)新SSRDAGs的操作.

例1. 對(duì)于常見的一個(gè)關(guān)于年齡A、性別G、抽煙S和肺癌LC的BN實(shí)例，已知其DAG結(jié)構(gòu)包括的有向邊有A,S，G,S，S,LC，下面以該網(wǎng)絡(luò)的一個(gè)包含無向邊(A,S)，(A,G)，(G,S)，(S,LC)，(G,LC)的SS為例來詳細(xì)說明其2個(gè)SSRDAGs的隨機(jī)交叉操作.

Fig. 2 Two SSRDAGs and their random cross results圖2 兩個(gè)SSRDAGs與其隨機(jī)交叉結(jié)果

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

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

2.4SSRandom學(xué)習(xí)算法

BN結(jié)構(gòu)學(xué)習(xí)的SSRandom算法的目標(biāo)是基于SS隨機(jī)搜索出BIC得分較高的BN模型的DAG.大致分為3個(gè)步驟:

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

Step2. 在SS基礎(chǔ)上，對(duì)所有無向邊隨機(jī)使用OAdd算子添加方向，獲得得分最高的初始模型G0作為當(dāng)前模型G*；

Step3. 通過減邊算子OSub和轉(zhuǎn)方向算子ORev對(duì)G*隨機(jī)進(jìn)行m次優(yōu)化，并將高分網(wǎng)絡(luò)與低分網(wǎng)絡(luò)進(jìn)行隨機(jī)交叉，允許以一定的概率接受低分網(wǎng)絡(luò)，避免結(jié)果陷入局部最優(yōu)，循環(huán)得出優(yōu)化的BN結(jié)構(gòu).

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

算法1.SSRandom算法.

輸入:數(shù)據(jù)集D、循環(huán)次數(shù)n、隨機(jī)搜索次數(shù)m；

輸出:優(yōu)化后BN的DAGG結(jié)構(gòu).

通過Opt01ss算法從數(shù)據(jù)集D中獲得超結(jié)構(gòu)SS；

while循環(huán)次數(shù)n或循環(huán)條件滿足do

fori=1tomdo

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

endfor

當(dāng)前模型G*←G0；

forj=1tomdo

隨機(jī)通過OSub和ORev算子，優(yōu)化G*，獲得SSRDAGsG*j；

endfor

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

G*←Sort中最高得分的網(wǎng)絡(luò)；

fork=1tomdo

G*←從G*和Sort中次高得分的網(wǎng)絡(luò)中隨機(jī)選一個(gè)網(wǎng)絡(luò)；

G*與剩余m-1個(gè)中的任意一個(gè)進(jìn)行隨機(jī)交叉，得2個(gè)SSRDAGs網(wǎng)絡(luò)G1*k和G2*k；

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

endfor

endif

endwhile

returnG ←G*.

2.5時(shí)間復(fù)雜性分析

在SSRandom算法中，在SS基礎(chǔ)上的隨機(jī)搜索部分，第1個(gè)for循環(huán)是隨機(jī)選擇初始網(wǎng)絡(luò)，其時(shí)間復(fù)雜度為O(m)，m表示隨機(jī)搜索次數(shù).Sort排序算法用快速排序時(shí)，其時(shí)間復(fù)雜性為O(mlogm)，其中m表示m次隨機(jī)搜索后獲得的m個(gè)網(wǎng)絡(luò).第2個(gè)和第3個(gè)for循環(huán)是隨機(jī)優(yōu)化初始網(wǎng)絡(luò)，其時(shí)間復(fù)雜度均為O(m).因而，整個(gè)隨機(jī)搜索算法部分時(shí)間復(fù)雜度為O(mlogm).

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

2) 爬山法.由于其搜索網(wǎng)絡(luò)空間為搜索算子對(duì)當(dāng)前網(wǎng)絡(luò)的一次加邊、或減邊、或轉(zhuǎn)邊后得到的網(wǎng)絡(luò)集合，易知，在SS的基礎(chǔ)上，有i(0≤i≤e)條有向邊的當(dāng)前網(wǎng)絡(luò)的候選網(wǎng)絡(luò)個(gè)數(shù)為

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

其中，(e-i)表示一次加邊產(chǎn)生的網(wǎng)絡(luò)個(gè)數(shù)，2個(gè)i分別表示一次減邊和一次轉(zhuǎn)邊后產(chǎn)生的網(wǎng)絡(luò)個(gè)數(shù)，因而i取e種情況下共有2e2個(gè)候選網(wǎng)絡(luò)，故其時(shí)間復(fù)雜度為O(e2).

由此，在SS基礎(chǔ)上3種算法的時(shí)間復(fù)雜度分別如表1所示：

Table 1 The Time Complexity Comparison表1 時(shí)間復(fù)雜性對(duì)比

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

通常，大多情況下BN的有向邊數(shù)均會(huì)大于節(jié)點(diǎn)數(shù)|V|，因而一般混合學(xué)習(xí)算法第1階段得出的SS的無向邊數(shù)egt;|V|，或至少也會(huì)接近|V|.隨著網(wǎng)絡(luò)變量數(shù)增加，蠻力法和爬山法的搜索空間會(huì)較隨機(jī)搜索算法的搜索空間快速增加，從本文第3節(jié)實(shí)驗(yàn)也可得到，當(dāng)|V|分別為6，8，11且本文的隨機(jī)搜索次數(shù)m=10時(shí)，大多情況下已比其他BN結(jié)構(gòu)算法學(xué)到的結(jié)果要好.可見，該隨機(jī)搜索策略要比通?；谠u(píng)分搜索的算法高效.

3 實(shí)驗(yàn)結(jié)果與分析

本節(jié)在標(biāo)準(zhǔn)數(shù)據(jù)集上，通過將本文所提算法以及已有的3種BN結(jié)構(gòu)學(xué)習(xí)算法，分別與標(biāo)準(zhǔn)結(jié)果在4方面評(píng)估指標(biāo)上的對(duì)比分析，驗(yàn)證本文所提算法的學(xué)習(xí)性能.

3.1實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

實(shí)驗(yàn)運(yùn)行環(huán)境為：操作系統(tǒng)Windows 7、處理器Intel?CoreTMi7-4510U CPU@2.00 GHz、內(nèi)存4.00 GB.

所有實(shí)驗(yàn)在R語言環(huán)境中借助于R語言自帶的bnlearn工具包[17]實(shí)現(xiàn).實(shí)驗(yàn)選用標(biāo)準(zhǔn)的Survey，Asia，Sachs三個(gè)網(wǎng)絡(luò)[17]，其網(wǎng)絡(luò)結(jié)構(gòu)情況如表2所示.實(shí)驗(yàn)中具體所用數(shù)據(jù)均是通過這些基準(zhǔn)網(wǎng)絡(luò)經(jīng)過邏輯抽樣后得出的模擬數(shù)據(jù).

Table 2 Three Standard Structures of BNs Used in the Experiments

3.2評(píng)價(jià)指標(biāo)

BN結(jié)構(gòu)的學(xué)習(xí)結(jié)果通過靈敏性Sn(sensitivity)、特效性Sp(specificity)、歐幾里德距離Ed(Euclidean distance)[14]以及本文定義的整體準(zhǔn)確率Pa(percentage of overall accuracy)四個(gè)指標(biāo)進(jìn)行評(píng)價(jià).各指標(biāo)具體描述如下：

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

其中，TP表示基準(zhǔn)網(wǎng)絡(luò)中有邊而且也學(xué)出的邊的個(gè)數(shù)，即正確學(xué)出的邊的個(gè)數(shù)；FN表示基準(zhǔn)網(wǎng)絡(luò)中有邊但沒有學(xué)出的邊的個(gè)數(shù)，即丟失邊的個(gè)數(shù).

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

其中，F(xiàn)P表示基準(zhǔn)網(wǎng)絡(luò)中無邊但學(xué)出有邊的個(gè)數(shù)，即冗余邊的個(gè)數(shù)；TN表示基準(zhǔn)網(wǎng)絡(luò)中無邊而且學(xué)出無邊的個(gè)數(shù)，即正確學(xué)出無邊的個(gè)數(shù).

3) 歐幾里德距離Ed.反映學(xué)出網(wǎng)絡(luò)與真實(shí)網(wǎng)絡(luò)之間在歐氏空間的差距，該指標(biāo)值越小越好.其格式化表示為

4) 整體準(zhǔn)確率Pa.主要通過正確學(xué)出的有向邊和正確學(xué)習(xí)的無邊的比率來度量學(xué)習(xí)所得的網(wǎng)絡(luò)結(jié)構(gòu)的整體準(zhǔn)確度，該指標(biāo)值越大越好.其格式化表示為

3.3結(jié)果對(duì)比與分析

實(shí)驗(yàn)主要對(duì)比本文所提的SSRandom算法和已有的MMHC,Hiton+HC (bnlearn工具包自帶的Hiton和HC搜索策略的混合)、GS+HC (bnlearn自帶的Grow-Shrink和HC的混合)三種結(jié)構(gòu)學(xué)習(xí)算法在Survey，Asia，Sachs網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果，對(duì)比指標(biāo)主要有Sn，Sp，Ed，Pa四個(gè).

由于本文所提方法還涉及到算法的循環(huán)次數(shù)n和隨機(jī)搜索次數(shù)m的設(shè)置.因而實(shí)驗(yàn)中，對(duì)于n的取值，考慮n=100和n=300這2種情況；對(duì)于m的取值，考慮m=10和m=30這2種情況.

對(duì)于SSRandom算法，每種情況下學(xué)習(xí)5次進(jìn)行平均;對(duì)于其他3種算法，并不涉及這些參數(shù)，所以不需要分情況討論.因而在每種情況下，在每次運(yùn)行SSRandom算法的相同數(shù)據(jù)集上，同時(shí)運(yùn)行其他3種算法學(xué)習(xí)BN結(jié)構(gòu)，即它們是20(即4×5)次或5次的平均.具體實(shí)驗(yàn)結(jié)果如表3～5，粗體數(shù)字表示每個(gè)指標(biāo)下最好的實(shí)驗(yàn)結(jié)果.

Table 3 Comparison Between SSRandom and Other Three Algorithms on the Dataset of Size 5 000表3 樣本容量為5 000時(shí)SSRandom與其他3種算法的實(shí)驗(yàn)結(jié)果對(duì)比

Table 4 Comparison Between SSRandom and Other Three Algorithms on the Dataset of Size 2 000表4 樣本容量為2 000時(shí)SSRandom與其他3種算法的實(shí)驗(yàn)結(jié)果對(duì)比

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可看出，樣本量達(dá)5 000時(shí)，分別在(n=100,m=10)，(n=100,m=30)，(n=300,m=10)，(n=300,m=30)四種情況下，除Survey網(wǎng)絡(luò)上的Sp和Asia網(wǎng)絡(luò)上GS+HC方法的Sp外，SSRandom算法在4種指標(biāo)下均比其他3種算法效果好，其Pa結(jié)果在Survey和Asia網(wǎng)絡(luò)上可達(dá)90%以上，在Sachs網(wǎng)絡(luò)上可達(dá)近80%，但其他3種算法在Sachs網(wǎng)絡(luò)上的Pa效果卻在63%及其以下.而且可統(tǒng)計(jì)出SSRandom算法循環(huán)次數(shù)n=300時(shí)的結(jié)果中有83.3%(1012)的要比n=100時(shí)好，具體可通過每個(gè)網(wǎng)絡(luò)上n=300與n=100在m=10和m=30 共4種組合下的比較統(tǒng)計(jì)得出.同理得出m=30時(shí)中有75%(912)的結(jié)果要比m=10時(shí)的好.

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

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

從表5可知，除Asia網(wǎng)絡(luò)上的Sp外，SSRandom算法在其他情況下的學(xué)習(xí)結(jié)果比其他3種算法的結(jié)果要好或一樣好.而且從實(shí)驗(yàn)數(shù)據(jù)整體上來看，4種算法的學(xué)習(xí)結(jié)果較之前樣本量為2 000和5 000時(shí)均有所提高.但對(duì)于其他3種算法，在Sachs網(wǎng)絡(luò)上的Pa效果仍在60%以下，而本文SSRandom算法可提高到83%以上.

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

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

Fig. 3 The relationship between each evaluation index and sample size in Survey, Aisa and Sachs networks, respectively圖3 各評(píng)價(jià)指標(biāo)與樣本量分別在Survey, Aisa, Sachs網(wǎng)絡(luò)上的關(guān)系

4 結(jié)束語

本文針對(duì)BN結(jié)構(gòu)混合學(xué)習(xí)算法中超結(jié)構(gòu)構(gòu)建時(shí)容易丟失邊和空間搜索時(shí)爬山法易陷入局部最優(yōu)等問題，通過采用Opt01ss算法學(xué)習(xí)超結(jié)構(gòu)，以盡可能地避免了出現(xiàn)丟失邊的問題；接著重點(diǎn)研究了基于超結(jié)構(gòu)隨機(jī)搜索的SSRandom學(xué)習(xí)算法，該隨機(jī)算法可以一定的概率跳出局部最優(yōu).通過在標(biāo)準(zhǔn)網(wǎng)絡(luò)上多種樣本量情況下4種評(píng)價(jià)指標(biāo)上的實(shí)驗(yàn)，驗(yàn)證了該算法的良好學(xué)習(xí)性能.進(jìn)一步的研究工作將面向高維小樣本數(shù)據(jù)探討B(tài)N結(jié)構(gòu)的隨機(jī)學(xué)習(xí)方法.

[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

國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目(61432011)；軍民共用重大研究計(jì)劃聯(lián)合基金重點(diǎn)項(xiàng)目(U1435212)；國(guó)家自然科學(xué)基金優(yōu)秀青年科學(xué)基金項(xiàng)目(61322211)；國(guó)家自然科學(xué)基金項(xiàng)目(61672332)；中國(guó)博士后科學(xué)基金項(xiàng)目(2016M591409)；山西省自然科學(xué)基金項(xiàng)目(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