利用先驗正態分布的貝葉斯網絡參數學習

柴慧敏, 趙昀瑤, 方 敏

(西安電子科技大學計算機學院, 陜西 西安 710071)

0 引 言

貝葉斯網絡(Bayesian networks, BNs)是將概率理論和圖論相結合的不確定性知識推理網絡,對非精確知識表達方面具有較強的能力[1-2]。BNs可應用于一些復雜系統的建模,如已成功地應用于故障診斷[3-4]、圖像處理[5-6]、網絡安全[7-8]、態勢預測[9-10]等領域。

一個BNs由兩部分構成:一是BNs結構,為有向非循環圖,表示了節點(變量)之間的依賴和獨立關系;二是網絡參數,為各個節點條件概率參數的集合,是對節點間依賴關系的定量表示。在網絡結構確定的情況下,如何確定正確的網絡參數,即網絡參數學習,是BNs應用過程中的重要問題之一。

在一些實際的應用中,如:故障診斷系統、戰場態勢評估中,樣本數據很難獲得,可能僅得到樣本量小或者數據不完整的樣本集。對于這樣的問題,一些研究人員提出在進行參數學習時,融入專家針對參數的先驗知識,以提高參數學習精度。這一過程也可視為在參數學習過程中加入約束條件[11]。

目前,針對參數的范圍約束、單調性約束等討論得較多,主要的解決方法有:文獻[12-14]提出通過建立基于凸約束的目標優化模型進行求解;文獻[15]依據約束構建罰項函數,通過降梯度法求解目標函數的最優解,以獲得參數值;文獻[16-17]利用約束條件和蒙特卡羅抽樣方法,獲取表示先驗Dirichlet分布的超參數,再結合樣本數據進行參數估計;文獻[18-20]采用引入輔助BNs,完成約束條件下的BNs參數學習;文獻[21]將先驗約束融入BNs的表示框架中,進行混合BNs的參數學習;文獻[22]在具有一定關聯關系的樣本數據之間添加約束條件,用于不完整數據集下的BNs參數學習。文獻[23-24]給出了單調性約束(也稱序約束)的解決方法,采用均勻分布來表示序約束,然后采用貝葉斯估計法進行參數估計。

而參數的近似等式約束也是一種較常見的專家先驗知識,例如:如果A發生,則B發生的可能性0.8,可得B參數的近似取值的先驗知識:P(B=true|A=true)=0.8。針對這一類約束,本文提出采用正態分布對該類約束進行表示,得到先驗正態分布;然后通過目標優化獲取先驗Dirichlet分布的超參數,采用貝葉斯最大后驗概率(maximum a posteriori,MAP)估計方法計算網絡參數值。

1 貝葉斯網絡參數約束分類

對于BNs參數的學習過程中,可以得到一些定性的先驗知識,這些定性的先驗知識主要可以描述為2種約束形式:線性不等式約束和近似等式約束。

定義1線性不等式約束

對于類似式(1)的專家先驗知識:

(1)

式中,Pk,Pk′為不同的網絡參數,可以是同一節點的參數,也可以是來自不同節點的參數;c屬于[0,1]區間,t為實數,且二者均為常數。可以表示為

(2)

式中,t0,tk均為實數。則式(2)為線性不等式約束。文獻[23-24]中的序約束,及參數的范圍約束實質上就可以歸為線性不等式約束。

定義2近似等式約束

領域專家可以給出類似這樣的斷言:某個網絡參數與另外一個參數近似相等;某個網絡參數是另外一個參數近似t倍;某個參數近似等于某個值等,可以表示為

(3)

但具體應用中,式(3)并不方便計算利用,則可采用式(4)的約束描述,即

(4)

式中,ε∈[0,1]。

2 先驗正態分布的BNs參數學習方法

2.1 近似等式約束的正態分布表示

對于式(4)的近似等式約束,假定參數Pk′先確定,ε取值較小,則可以將Pk限制在一個較小的范圍內,Pk可以取這個范圍的任意值。進一步分析式(3)的專家先驗知識,可以看出,Pk取值Pk′,或者tPk′,或者c的可能性應該是最大的。

因此,本文引入正態分布構建近似等式約束的數學模型,如圖1所示。

圖1 近似等式的正態分布表示Fig.1 Normal distribution representation for approximate equality constraint

圖1以近似等式約束|Pk-c|<ε為例,假定c=0.5,ε=0.2。可以看出,Pk取值為c的概率最大,而在c兩側的取值的概率將逐漸減小,符合近似等式約束的特點。則圖1中參數Pk的近似等式約束的正態分布為

(5)

式中,μk=c,為正態分布的期望;δ為均方差。本文設定ε=0.2,且需要滿足Pk的取值落在區間:[μi-0.2,μi+0.2],則可令式(5)滿足:

P(μk-0.2≤Pk≤μk+0.2)=

(6)

由式(6)計算可得:δ=0.051 3。

由此,對式(4)的近似等式約束構建正態分布模型時,依據式(5)將期望設定為:Pk′,或者tPk′,或者c,而均方差為:δ=0.051 3。

2.2 基于貝葉斯MAP的參數估計

貝葉斯MAP參數估計視參數為隨機變量,將參數的后驗分布的最大值,作為該參數的估計值。現假定BNs由n個節點構成:X={X1,X2,…,Xn},節點Xi存在ri個狀態值,假定取值1,2,…,ri。其父節點Pa(Xi)的取值共有qi個組合,假定取值1,2,…,qi。則節點Xi的參數可表示為:θijk=P(Xi=k|Pa(Xi)=j),其中k,j分別表示節點Xi的取值和父節點的組合取值。

在貝葉斯MAP參數估計中,BNs參數的先驗分布為Dirichlet分布,其超參數表示為D={aijk}。這樣參數的后驗概率也將是Dirichlet分布,當參數的后驗分布取最大值時,得到該參數的估計值為

(7)

式中,Nijk為樣本數據集中滿足Xi=k和Pa(Xi)=j的樣本的個數。先驗Dirichlet分布的超參數可看作參數θijk的虛擬樣本數。

可以看出,式(7)中的參數估計值計算需要Dirichlet分布的超參數,而正態分布的參數不能直接用于式(7)中,因此,采用第2.1節中先驗正態分布并不適合式(7)中的參數估計。為此,建立目標優化函數,用Dirichlet分布逼近正態分布,獲取相應的超參數。

Dirichlet分布的邊緣分布為Beta分布,表示為Beta(a,b),則對應到BNs中的每個參數θijk,其相應的先驗知識需要服從Beta分布。將正態分布和Beta分布方差的距離最小作為目標函數,期望相等作為約束條件,且要求Beta分布為凸函數,則a>1,b>1為約束條件。則有:

min(DBeta-DG)2

(8)

式中,DBeta,DG分別為Beta分布和正態分布的方差;EBeta,EG分別為相應的數學期望。對式(8)進行求解,可得到Beta分布參數,然后根據式(7)計算θijk的估計值。

3 實驗測試

3.1 實驗內容

本文測試在完整樣本數據集下對本文方法的參數學習精度和運行耗時進行測試,并且與最大似然估計(maximum likelihood estimation, MLE)、無專家先驗的貝葉斯MAP估計、約束優化方法(constrained optimization approach, CO)、參照文獻[23-24]中的均勻分布表示先驗的方法等4種主要方法進行比較,需要說明的是:

(1) 本文方法:實驗測試中采用的近似等式約束為式(4)中:|Pk-c|<ε,且ε=0.2,c為相應參數的真實值。

(2) 無專家先驗的貝葉斯MAP估計:貝葉斯MAP估計中的先驗Dirichlet分布的超參數一般來自專家先驗,在無專家先驗的情況下,可采用一致先驗的方式確定超參數[25],即:式(7)中的超參數aijk=1。本文的實驗測試采用的是該種方式。

(3) 約束優化方法:對于約束優化這一類方法,以文獻[15]中的約束優化方法為代表進行比較測試。在本文的實驗測試中,利用近似等式約束構建罰項函數,且文獻[15]所給目標優化函數中的罰項權值設定為1,約束信任度設定為1。在采用降梯度法進行求解時,步長設為1。

實驗測試首先采用如圖2所示的草坪濕潤推理BNs,該BNs被廣泛應用于網絡推理和參數估計算法的測試中。

圖2 草坪濕潤推理貝葉斯網絡Fig.2 Structure of lawn wet Bayesian network

該BNs參數的真實值為:根節點C:P(C=true)=0.5,P(C=false)=0.5。其他節點分別為表1所示。

表1 節點S,R和W參數表

在實驗測試中,根據圖2網絡結構和上述所給的參數真實值,采用隨機抽樣算法生成樣本數據。實驗測試環境為:操作系統:Windows 7,處理器為:Intel CPU 3.30 GHz,平臺軟件為:Matlab R2014a。

3.2 測試結果1

(1)參數學習精度測試

本文實驗以KL散度為參數學習精度的衡量指標,在不同的數據樣本集下進行了測試,測試過程中對圖2中的4個節點的參數均加入近似等式約束。測試樣本集樣本量分別為:10,20,30,50,100,對相同樣本量的樣本集重復測試10次,分別統計4個節點:C,S,R,W的平均KL散度值,結果如表2所示。

由表2的測試結果可以看出,在參數學習精度方面,本文方法和先驗均勻分布方法明顯要好于最大似然估計、無專家先驗的貝葉斯MAP估計、約束優化方法,尤其是在樣本量較小的情況下,如:10樣本集和20樣本集。但在樣本較多,即樣本充足的情況下,這5種方法的精度均能達到較好的水平,例如:在100樣本集下,4個節點的平均KL散度在5種方法中均沒有超過0.060。

單純分析本文方法和先驗均勻分布,在不同的樣本集下采用本文方法,節點的平均KL散度多次出現為0.0,出現的次數為:13次,明顯多于先驗均勻分布出現的次數:5次。因此,本文方法的精度要更好于先驗均勻分布方法。

為了從整體上比較這5種方法,將表2中不同的測試樣本集和不同的測試方法下,4個節點的平均KL散度值相加,得到圖2中的BNs的平均KL散度值,其結果如圖3所示。

表2 節點C,S,R,W的平均KL散度值

由圖3曲線可以看出:在樣本量為10、20、30的情況下,本文方法和先驗均勻分布的精度高于其他3種方法,無專家先驗的貝葉斯MAP估計法的精度高于約束優化方法和最大似然估計方法。在樣本量為50、100的情況下,最大似然估計、無專家先驗的貝葉斯MAP估計、約束優化方法的精度近似趨于一致,但本文方法和先驗均勻分布的精度仍高于其他3種方法。

為了進一步分析本文方法和先驗均勻分布方法,將圖3中的這2個方法的曲線單獨顯示,如圖4所示。

圖4 本文方法與先驗均勻分布方法的平均KL散度(草坪濕潤貝葉斯網絡) Fig.4 Average KL divergence for the proposed method and the method of prior uniform distribution(lawn wet Bayesian network)

由圖4可以看出,本文方法和先驗均勻分布方法均能得到較高的精度,但本文方法在5個樣本集下的精度都高于先驗均勻分布方法。

(2)運行時間測試

在不同的樣本集下,對5種方法的運行時間進行測試,每一種樣本集重復測試10次,統計各方法的平均運行時間,測試結果如表3所示。

表3 5種方法的運行時間

為了直觀顯示5種方法的運行時間比較,給出如圖5的曲線表示。

圖5 5種方法運行時間比較(草坪濕潤BNs)Fig.5 Comparison of run time for five method (lawn wet Bayesian network)

由圖5可以看出,本文方法和先驗均勻分布方法的運行時間近似相等,且耗時大于其他3種方法。

顯然,本文方法提高了參數學習精度,但增加了運行時間。但進一步綜合比較學習精度和運行時間的測試結果,本文方法提高學習精度程度要遠高于增加運行時間的程度。例如:10樣本集下,本文方法相比于約束優化方法,精度提高了700多倍,運行時間增加了近10倍。因此,綜合考慮學習精度和運行時間,本文方法優于其他4種方法。

3.3 測試結果2

為了進一步對本文所提出的方法進行實驗測試,選擇常用的用于測試的BNs:Alarm(www.norsys.com/netlibrary/index.htm),該BNs共有37個節點,最多父節點個數為4個。

參照第3.1節中的測試內容和實驗測試環境,對Alarm BNs在數據樣本集:50,200,400,600,1 000,以BNs平均KL散度和運行時間為衡量指標,進行實驗測試。其中,BNs平均KL散度與第3.2節中的相同,即為:網絡各節點的平均KL散度值的總和。

(1) BNs平均KL散度

測試過程中對Alarm BNs的37個節點的參數均加入近似等式約束,且所加入的近似等式約束按照第3.1節中(1)。對相同樣本量的樣本集重復測試10次,分別統計37個節點的平均KL散度值,并進行相加求和,結果如圖6所示。

圖6 不同樣本集下BNs(Alarm)平均KL散度Fig.3 Average KL divergence of Bayesian network (Alarm) under different data set

圖6中,在樣本集為:50,200,400,本文方法和先驗均勻分布方法的平均KL散度值均小于其他3種方法。而在樣本集為600,1 000時,5種方法的平均KL散度分別為:最大似然估計:0.266,0.176;約束優化方法:0.259,0.169;貝葉斯MAP估計:0.245,0.163;先驗均勻分布方法:0.082,0.071;本文方法:0.017,0.016。本文方法和先驗均勻分布方法的平均KL散度均低于其他3種方法,即參數學習精度好于其他3種方法。

為了進一步分析本文方法和先驗均勻分布方法,將圖6中的這兩個方法的曲線單獨顯示,如圖7所示。

由圖7可以看出,本文方法在5個樣本集下的參數學習精度均好于先驗均勻分布方法。

圖7 本文方法與先驗均勻分布方法的平均KL散度(Alarm BNs)Fig.7 Average KL divergence for the proposed method and the method of prior uniform distribution (Alarm Bayesian network)

(2)運行時間

針對Alarm BNs,在樣本集:50,200,400,600,1 000下,對5種方法的運行時間進行測試,重復測試10次,統計各方法的平均運行時間,測試結果如圖8所示。

圖8 5種方法運行時間比較(Alarm BNs)Fig.8 Comparison of run time for five methods (Alarm wet Bayesian network)

圖8中,本文方法和先驗均勻分布方法的運行時間近似相等,但都大于其他3種方法。進一步綜合比較KL散度和運行時間,在樣本集:50, 200的測試中,本文方法相比于其他4種方法,參數學習精度的提高倍數遠大于運行時間的增加倍數。

在樣本集:600,1 000的測試中,本文方法相比較于其他4種方法學習精度提高的倍數為:最大似然估計:15.65,11.00;約束優化方法:15.24,10.56;貝葉斯MAP估計:14.41,10.18;先驗均勻分布方法:4.82,4.44。而運行時間相比于其他4種方法增加的倍數依次為:最大似然估計:2.26,1.45;約束優化方法:1.16,1.12;貝葉斯MAP估計:2.09,1.39;先驗均勻分布方法:0.99,0.98。可以看出,本文方法參數學習精度提高的倍數均大于運行時間增加的倍數。因此,綜合考慮學習精度和運行時間,本文方法是優于其他4種方法。

4 結 論

本文針對BNs參數的近似等式約束,提出了采用正態分布的先驗表示方式,實驗測試結果表明:該方法的參數學習精度好于最大似然估計、無專家先驗的貝葉斯MAP估計、約束優化方法等4種方法,而運行時間要高于這4種方法。但綜合考慮比較KL散度和運行時間,相比較于其他4種方法,本文方法參數學習精度提高的倍數均大于運行時間增加的倍數。本文只是考慮了完整數據樣本下的參數學習,后續需要進一步研究缺失數據樣本下的學習問題。