基于融合先驗方法的貝葉斯網絡結構學習

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

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

0　引　言

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

貝葉斯網絡可以手工構造也可以從數據中學習,后者稱為貝葉斯網絡學習,現在隨著人工智能的發展和應用情況的復雜化,如何有效地進行貝葉斯網絡學習是研究的主要內容,其中結構學習是研究的熱點。

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

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

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

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

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

1　先驗信息的表示方式

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

圖1　先驗信息實例

2　融合先驗信息改進評分

本文要將先驗信息融合到評分函數中去,在利用評分—搜索算法進行貝葉斯網絡結構學習時, 對于結構,貝葉斯評分的模型為

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

(1)

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

文獻[14]為了利用確定性先驗信息,提出一種先驗信息分布的估計方法,設任意的網絡結構Bs,先驗信息ξ代表的貝葉斯網絡結構為Bp,然后計算Bs的先驗信息分布估計為

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

(2)

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

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

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

(3)

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

(4)

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

2.1　數據權衡項的構造

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

(5)

式中,s為樣本量;c和φ是一個可調的平衡因子,其取值可以根據要求解的貝葉斯網絡結構的復雜度設定,一般的準則是,網絡結構越復雜,φ的取值應該越大。當c取1,φ取不同值時對|K(s)|函數進行了仿真,如圖2所示。

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

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

2.2　融合先驗信息項的構造

圖3　線性罰項函數

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

(6)

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

結合式(6)記

(7)

給出導函數公式

(8)

εi(p)應該滿足條件

(9)

式中,k是一個常數。

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

圖4　基于熵的罰項函數

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

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

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

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

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

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

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

4　仿真結果及其分析

4.1　仿真說明

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

表3　IS-HC算法流程

圖5　仿真的先驗信息

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

4.2　本文方法有效性的驗證

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

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

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

4.3　對錯誤先驗適應能力分析

為驗證本文提出幾種方法對錯誤先驗的適應能力,本節分別做以下仿真:有無數據權衡項的對比仿真,融合先驗項中不同罰項函數的對比仿真,有無先驗搜索算子的對比仿真。

4.3.1數據權衡項分析

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

圖7　有無數據權衡項的比較

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

4.3.2融合先驗信息項分析

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

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

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

KL距離和漢明距離的比較也有同樣的結果,說明了本文罰項函數構造方法的合理性與有效性。

4.3.3先驗搜索算子分析

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

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

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

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

5　結　論

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

參考文獻：

[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] 邸若海, 高曉光, 郭志高. 小數據集BN建模方法及其在威脅評估中的應用[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.