基于融合先驗方法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學習

高曉光, 葉思懋, 邸若海, 寇振超

(西北工業(yè)大學電子信息學院, 陜西 西安 710129)

0　引　言

概率論與數(shù)理統(tǒng)計為很多現(xiàn)代自然科學與工程問題的解決提供了有效的方法。貝葉斯網(wǎng)絡(luò)作為一種概率圖模型,其堅實的理論基礎(chǔ)、知識結(jié)構(gòu)的自然表述方式、強大的推理能力使其成為數(shù)據(jù)分析時強有力的建模工具,特別地在機器學習[1]、數(shù)據(jù)挖掘[2-3]、決策分析[4]等領(lǐng)域,已成為了一種重要的數(shù)學工具。

貝葉斯網(wǎng)絡(luò)可以手工構(gòu)造也可以從數(shù)據(jù)中學習,后者稱為貝葉斯網(wǎng)絡(luò)學習,現(xiàn)在隨著人工智能的發(fā)展和應(yīng)用情況的復(fù)雜化,如何有效地進行貝葉斯網(wǎng)絡(luò)學習是研究的主要內(nèi)容,其中結(jié)構(gòu)學習是研究的熱點。

貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學習是一個非確定性多項式困難(non-deterministic polynomial hard, NP-hard)問題[5],通常需要較大的樣本量[6],但有些情況下只能獲得比較少的數(shù)據(jù)[7],用這些小數(shù)據(jù)進行結(jié)構(gòu)學習會造成學習誤差大、決策不準確的后果。利用先驗信息能夠有效提高學習準確度[8],彌補數(shù)據(jù)量的不足[9]。

對于如何利用先驗信息,有很多學者已經(jīng)對此進行了研究,利用先驗信息進行結(jié)構(gòu)學習一般都使用評分搜索法,文獻[10]對這些方法做了一定的總結(jié)。比較典型的是以下幾種:文獻[11]利用節(jié)點序作為先驗信息,用K2算法進行學習;文獻[12]利用邊是否存在作為先驗信息;文獻[13]利用邊存在的概率作為先驗信息。

現(xiàn)有的文獻都沒有考慮到對錯誤不確定先驗信息的適應(yīng)能力,而在某些情況下,比如戰(zhàn)場環(huán)境中應(yīng)用貝葉斯網(wǎng)絡(luò)需要較強的可靠性,且該環(huán)境下獲得的數(shù)據(jù)量小,對專家先驗信息的依賴比較大。所以當專家給出不正確的先驗信息時,希望算法對錯誤有一定的適應(yīng)能力,當先驗信息有部分錯誤時,能夠降低其對結(jié)果的負面影響。這樣能夠增強結(jié)構(gòu)學習算法的可靠性和魯棒性。

本文采用評分搜索的方法進行結(jié)構(gòu)學習,在評分和搜索環(huán)節(jié)都利用了先驗信息。首先本文提出了一種新的融合先驗信息的評分函數(shù),該評分函數(shù)融合先驗信息的方式有兩個特點:第一,當數(shù)據(jù)量越大時,評分先驗項所占的權(quán)重越小;第二,評分函數(shù)的先驗項可以任意構(gòu)造,達到期望的要求。本文借鑒文獻[14]中構(gòu)造先驗的思想,設(shè)置一個關(guān)于先驗信息的懲罰項,當先驗信息與當前網(wǎng)絡(luò)的差距越大,距離越大,懲罰越大。先驗項的另一種構(gòu)造方法是計算先驗部分的聯(lián)合概率,但精確求先驗部分的聯(lián)合概率是很復(fù)雜的[15],本文提出的方法相對簡單有效。

在搜索環(huán)節(jié),本文從增強魯棒性的角度出發(fā)提高對錯誤先驗信息的適應(yīng)能力:評分搜索算法很容易搜不到與先驗信息有關(guān)的邊,就達到局部最優(yōu),這樣就造成了先驗利用的不充分,當先驗信息存在部分錯誤時,現(xiàn)有的評分搜索算法可能會學到這些錯誤先驗信息有關(guān)的邊,而忽略了正確先驗信息的邊,雖然概率比較小,但是說明現(xiàn)有的算法魯棒性不夠好。本文提出一種關(guān)于先驗信息的引導策略,在搜索過程中增加了一個先驗信息搜索算子,從而擴展搜索空間,最后能充分地利用正確的先驗信息,這樣就能增強魯棒性,從而提高對錯誤先驗信息的適應(yīng)能力。

1　先驗信息的表示方式

通常情況下,先驗信息是專家對部分變量的主觀認知,所以一般給出的是部分邊存在的概率大小,而且專家也很難給出這些邊的聯(lián)合概率,能提供的是每條邊存在的邊緣概率。所以按照這種情況經(jīng)行建模。

圖1　先驗信息實例

2　融合先驗信息改進評分

本文要將先驗信息融合到評分函數(shù)中去,在利用評分—搜索算法進行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學習時, 對于結(jié)構(gòu),貝葉斯評分的模型為

lnP(G,D)=lnP(D|G)+lnP(G)

(1)

式中，lnP(D|G)項為對數(shù)據(jù)的似然度；lnP(G)項為結(jié)構(gòu)G的先驗信息概率,本文融合先驗信息的方法是對lnP(G)進行估計,其充當了一個罰項,當先驗信息與當前網(wǎng)絡(luò)的差距越大,距離越大,懲罰值越大。

文獻[14]為了利用確定性先驗信息,提出一種先驗信息分布的估計方法,設(shè)任意的網(wǎng)絡(luò)結(jié)構(gòu)Bs,先驗信息ξ代表的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)為Bp,然后計算Bs的先驗信息分布估計為

P(G)=P(Bs|ξ)=ckδ

(2)

本文借鑒這種思路與模型,為了融合不確定先驗信息,研究得到了一個新的評分模型。

本文將k替換為一個關(guān)于數(shù)據(jù)樣本量的函數(shù),將δ替換為一個關(guān)于概率取值的函數(shù),就能得到一個處理不確定先驗的模型。

已知先驗信息ξ(V,P),其中包含n對節(jié)點。對于特定結(jié)構(gòu)G,參照式(2)構(gòu)造罰項為

(3)

式中,k(s)、εi(p)都是函數(shù),其中s代表樣本量的大小,p代表在G中某條邊ei在ξ中對應(yīng)的概率。對式(3)取對數(shù)并進行化簡得

(4)

式中,C為常數(shù),對任意的結(jié)構(gòu)均相同,該項在比較過程中可以省略;K(s)是一個函數(shù),記為數(shù)據(jù)權(quán)衡項;εi(p)中包含了先驗信息,記為融合先驗信息項。

2.1　數(shù)據(jù)權(quán)衡項的構(gòu)造

對于貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學習,樣本量較少時需要用先驗信息來彌補樣本的不足。隨著樣本量的增多,對先驗信息的依賴會越來越弱,但錯誤的先驗信息始終會影響學習結(jié)果。所以本文構(gòu)造K(s)隨樣本量的增加而減小,這樣在樣本增多時,錯誤先驗信息的影響會減小,具體函數(shù)為

(5)

式中,s為樣本量;c和φ是一個可調(diào)的平衡因子,其取值可以根據(jù)要求解的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜度設(shè)定,一般的準則是,網(wǎng)絡(luò)結(jié)構(gòu)越復(fù)雜,φ的取值應(yīng)該越大。當c取1,φ取不同值時對|K(s)|函數(shù)進行了仿真,如圖2所示。

圖2　φ取不同值時|K(s)|的大小

由圖2可知,數(shù)據(jù)集越大,K(s)的值越小,先驗所占的權(quán)值就越小。

2.2　融合先驗信息項的構(gòu)造

圖3　線性罰項函數(shù)

這種線性函數(shù)有一個缺點,若先驗信息有誤則很容易學到錯誤的網(wǎng)絡(luò),為了克服這個問題,本文從信息論中不確定度的角度出發(fā),利用熵的概念,構(gòu)造一個非線性的罰項函數(shù)。思想是,若ei造成不確定度越大,罰項的變化就越小,即εi(p)的導數(shù)的絕對值越小。所以目標是構(gòu)造導函數(shù)D(p),當不確定度達到最大值時,導數(shù)為0。將ei視為隨機變量,則該隨機變量的熵計算公式為

(6)

熵表示了這個變量的不確定度,熵越大說明ei的不確定度越大,ei一共有3種情況。不失一般性,對另外兩種情況取均勻分布。

結(jié)合式(6)記

(7)

給出導函數(shù)公式

(8)

εi(p)應(yīng)該滿足條件

(9)

式中,k是一個常數(shù)。

進行數(shù)值積分后,εi(p)的函數(shù)圖像如圖4所示。

圖4　基于熵的罰項函數(shù)

由圖4可知,當專家先驗信息給出的概率具有的不確定度越大,在此概率值附近的改變造成的影響就越小,比如概率為0.3和概率為0.6兩處造成的懲罰度差值就很小,因為專家經(jīng)驗具有的不確定度很大。這樣優(yōu)點在于,若錯誤的先驗信息不是很絕對,則其造成的影響較小。

3　融合先驗信息的搜索過程

由于貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學習是一個NP-hard的問題。在啟發(fā)式搜索的過程中,隨著節(jié)點數(shù)的增加,貝葉斯網(wǎng)的局部峰值會越來越多,容易陷入局部最優(yōu),在貝葉斯的結(jié)構(gòu)學習中,雖然已經(jīng)發(fā)展了很多的搜索算法,包括一些群智能算法,也很難搜索到全局最優(yōu)解。這樣在給出先驗信息后,搜索算法很可能搜索不到先驗信息中的那些邊,尤其是那些概率取值比較大的邊。此時當先驗信息中有部分錯誤時,就可能會只用到那些錯誤的先驗信息,使得學習結(jié)果很差,為了改善這種情況,本文在搜索過程中,增加了一個“先驗搜索”算子,盡可能地利用正確的先驗信息,這樣能提高算法的魯棒性,提高整體的學習效果水平。

先驗信息搜索算子的設(shè)計思路為:搜索過程中,對先驗信息中的每個節(jié)點對,都按照先驗信息的概率進行置邊,例如對于節(jié)點對vi對應(yīng)的概率pi=[0.1,0.8,0.1],則這對節(jié)點間有0.8的概率置為正向。但是經(jīng)過先驗信息搜索算子的修改后,得到的結(jié)構(gòu)可能會成環(huán),所以要進行去環(huán)操作。

下面給出先驗信息搜索算法和去環(huán)算法流程，如表1和表2所示。

表1　先驗信息搜索算法流程

將先驗搜索算子加入到爬山算法中得到先驗搜索爬山(informed-search hill climbing,IS-HC)算法，流程如表3所示。

4　仿真結(jié)果及其分析

4.1　仿真說明

為了驗證文中提出方法的有效性,仿真采用經(jīng)典的Asia網(wǎng)絡(luò),用爬山法進行結(jié)構(gòu)學習。對于一些特定的參數(shù),數(shù)據(jù)權(quán)衡項K(s)中φ取500,融合先驗信息項默認采用基于熵的罰項函數(shù)。為簡便起見,若不作說明,本文先驗給出的形式為對Asia網(wǎng)中所有真實存在的邊加一個相同先驗概率。例如當說正確先驗為pi=[0.1,0.8,0.1],則所有真實存在的邊的概率一律設(shè)pi=[0.1,0.8,0.1],此時給出的先驗信息如圖5所示。

表3　IS-HC算法流程

圖5　仿真的先驗信息

為證明本文提出算法的有效性,仿真過程中對不同數(shù)量的訓練樣本進行了對比測試。本文用貝葉斯信息準則(Bayesian information criterion,BIC)評分、Kullback-Leibler (KL)距離和漢明距離評判網(wǎng)絡(luò)的優(yōu)劣性。KL距離衡量學習得到的網(wǎng)絡(luò)和真實網(wǎng)絡(luò)分布的差距,而漢明距離是網(wǎng)絡(luò)結(jié)構(gòu)間的多邊、少邊、反邊之和。評分越高、KL距離和漢明距離越小,說明學習得到的網(wǎng)絡(luò)越接近真實網(wǎng)絡(luò)。

4.2　本文方法有效性的驗證

為驗證本文的融合先驗方法確實能夠有效地利用先驗信息,對用本文的方法融合正確先驗和不融合正確先驗進行對比仿真。先驗設(shè)置為pi=[0.1,0.8,0.1],不同數(shù)據(jù)樣本量的仿真結(jié)果如圖6所示。

圖6　兩種方法在不同樣本量下的比較

對圖6進行分析,以BIC評分為例,添加先驗的BIC評分明顯高于無先驗的BIC評分,KL距離和漢明距離的比較也有同樣的結(jié)果,說明本文提出的方法能有效融合先驗信息。

4.3　對錯誤先驗適應(yīng)能力分析

為驗證本文提出幾種方法對錯誤先驗的適應(yīng)能力,本節(jié)分別做以下仿真:有無數(shù)據(jù)權(quán)衡項的對比仿真,融合先驗項中不同罰項函數(shù)的對比仿真,有無先驗搜索算子的對比仿真。

4.3.1數(shù)據(jù)權(quán)衡項分析

為驗證數(shù)據(jù)權(quán)衡項K(s)的效果,對不融合先驗信息、融合錯誤先驗信息無數(shù)據(jù)權(quán)衡項、融合錯誤先驗信息有數(shù)據(jù)權(quán)衡項進行仿真,記錄其結(jié)果進行對比。其中，錯誤先驗信息設(shè)置為pi=[0.9,0.05,0.05],正確先驗信息設(shè)置為pi=[0.1,0.8,0.1],不同數(shù)據(jù)樣本量的仿真結(jié)果如圖7所示。

圖7　有無數(shù)據(jù)權(quán)衡項的比較

對圖7進行分析,以BIC評分為例,當樣本量較小時,無權(quán)衡項和有權(quán)衡項方法的BIC評分類似,都明顯低于不融合錯誤先驗信息的BIC評分,但隨著樣本量增加,權(quán)衡因子發(fā)揮作用,有權(quán)衡項方法的得分曲線最后能逼近不融合錯誤先驗信息的得分曲線,而無數(shù)據(jù)權(quán)衡的BIC評分始終比較小。KL距離和漢明距離的比較也有同樣結(jié)果,說明了數(shù)據(jù)權(quán)衡項的有效性。

4.3.2融合先驗信息項分析

為驗證本文融合先驗信息項中罰項函數(shù)構(gòu)造的合理性,采取不同的錯誤概率值,觀察學習結(jié)果的變化情況。錯誤概率設(shè)置為:pi=[(1-p)/2,p,(1-p)/2],圖8中的橫坐標值為p,仿真數(shù)據(jù)量取為200。文獻[15]提出一種融合先驗信息的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學習方法,仿真中將其與本文所提方法做比較,對比對錯誤先驗信息的適應(yīng)能力，結(jié)果如圖8所示。

對圖8進行分析,以BIC評分為例,在錯誤的先驗信息條件下,罰項函數(shù)用熵函數(shù)構(gòu)造要比用線性函數(shù)構(gòu)造得分要高,說明了前者對錯誤先驗信息具有更好的適應(yīng)能力。

用本文的方法與文獻[15]提出的方法進行對比,當先驗信息錯誤程度比較大時,本文采用熵函數(shù)構(gòu)造方法的得分較高,對比而言說明本文方法在錯誤適應(yīng)能力方面有一定優(yōu)勢。

KL距離和漢明距離的比較也有同樣的結(jié)果,說明了本文罰項函數(shù)構(gòu)造方法的合理性與有效性。

4.3.3先驗搜索算子分析

為驗證先驗搜索算子的有效性,本節(jié)在仿真中設(shè)置兩組錯誤的先驗概率:p1,p2=[0.8,0.1,0.1]。其余正確的先驗信息為:pi=[0.1,0.8,0.1],對加先驗搜索算子和不加先驗搜索算子兩種情況進行了仿真對比,不同數(shù)據(jù)樣本量的仿真結(jié)果如圖9所示。

圖8　不同融合先驗項的比較

圖9　有無先驗搜索算子的比較

對圖9進行分析,以BIC評分為例,應(yīng)用先驗信息搜索算子的方法得到的評分要更高,KL距離和漢明距離的比較也有同樣的結(jié)果,說明在有部分錯誤先驗信息的情況下,先驗信息搜索算子能增強結(jié)構(gòu)學習利用正確先驗的魯棒性,從而提高對錯誤先驗信息的適應(yīng)能力。

5　結(jié)　論

本文為了提高結(jié)構(gòu)學習時對錯誤先驗信息的適應(yīng)能力,提出了一種新的融合先驗信息進行結(jié)構(gòu)學習的方法。仿真結(jié)果表明本文提出的方法能夠有效地利用先驗信息,并且對錯誤的先驗信息有適應(yīng)能力,降低錯誤先驗信息帶來的負面影響。另外,本文提出的模型高度概括了評分搜索法來利用先驗信息的模式,參數(shù)可以自由調(diào)節(jié),且可以應(yīng)用到粒子群優(yōu)化算法、遺傳算法等方法中。下一步工作是進一步對融合先驗信息的方法進行研究,以增強算法的容錯性。

參考文獻：

[1] SCHNEIDERMAN H. Object recognizer and detector for two-dimensional images using Bayesian network based classifier[P]. US: US 7848566 B2, 2015.

[2] HUANG J, YUAN Y. Construction and application of Bayesian network model for spatial data mining[C]∥Proc.of the IEEE International Conference on Control and Automation, 2007: 2802-2805.

[3] BANDYOPADHYAY S, WOLFSON J, VOCK D M, et al. Data mining for censored time-to-event data: a Bayesian network model for predicting cardiovascular risk from electronic health record data[J].Data Mining & Knowledge Discovery,2015,29(4): 1033-1069.

[4] SHENTON W, HART B T, CHAN T. Bayesian network models for environmental flow decision-making:1.Latrobe River Australia[J].River Research & Applications, 2015, 27(3): 283-296.

[5] CHICKERING D M. Learning Bayesian networks is NP-complete[J]. Networks, 1996, 112(2): 121-130.

[6] KOLLER D, FRIEDMAN N. Probabilistic graphical models[M]. Cambridge: MIT Press, 2009.

[7] 邸若海, 高曉光, 郭志高. 小數(shù)據(jù)集BN建模方法及其在威脅評估中的應(yīng)用[J]. 電子學報, 2016, 44(6):1504-1511.

DI R H, GAO X G, GUO Z G. The modeling method with Bayesian networks and its application in the threat assessment under small data sets[J]. Acta Electronica Sinica, 2016, 44(6):1504-1511.

[8] AMIRKHANI H, RAHMATI M, LUCAS P, et al. Exploiting experts’ knowledge for structure learning of Bayesian networks[J]. IEEE Trans.on Pattern Analysis & Machine Intelligence, 2016, PP(99): 2154-2170.

[9] CANO A, MASEGOSA A R, MORAL S. A method for integrating expert knowledge when learning Bayesian networks from data[J]. IEEE Trans.on Systems, Man & Cybernetics-Part B: Cybernetics, 2011, 41(5): 1382-1394.

[10] ANGELOPOULOS N, CUSSENS J. Bayesian learning of Bayesian networks with informative priors[J]. Kluwer Academic Publishers,2008,54(1/3):53-98.

[11] COOPER G F, HERSKOVITS E. A Bayesian method for the induction of probabilistic networks from data[J]. Machine Learning, 1992, 9(4): 309-347.

[12] CAMPOS L M D, CASTELLANOA J G. Bayesian network learning algorithms using structural restrictions[J]. International Journal of Approximate Reasoning,2007,45(2):233-254.

[13] CASTELO R, SIEBES A. Priors on network structures. Biasing the search for Bayesian networks[J]. International Journal of Approximate Reasoning, 2000, 24(1): 39-57.

[14] HECKERMAN D, DAN G, CHICKERING D M. Learning Bayesian networks: the combination of knowledge and statistical data[J]. Machine Learning, 1995, 20(3): 197-243.

[15] BORBOUDAKIS G, TSAMARDINOS I. Scoring and searching over Bayesian networks with causal and associative priors[C]∥Proc.of the 29th International Conference on Uncertainty in Artificial Intelligence, 2013: 1210-1232.