柴慧敏, 趙昀瑤, 方 敏

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

0 引 言

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

一個BNs由兩部分構(gòu)成:一是BNs結(jié)構(gòu),為有向非循環(huán)圖,表示了節(jié)點(變量)之間的依賴和獨立關(guān)系;二是網(wǎng)絡(luò)參數(shù),為各個節(jié)點條件概率參數(shù)的集合,是對節(jié)點間依賴關(guān)系的定量表示。在網(wǎng)絡(luò)結(jié)構(gòu)確定的情況下,如何確定正確的網(wǎng)絡(luò)參數(shù),即網(wǎng)絡(luò)參數(shù)學(xué)習(xí),是BNs應(yīng)用過程中的重要問題之一。

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

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

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

1 貝葉斯網(wǎng)絡(luò)參數(shù)約束分類

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

定義1線性不等式約束

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

(1)

式中,Pk,Pk′為不同的網(wǎng)絡(luò)參數(shù),可以是同一節(jié)點的參數(shù),也可以是來自不同節(jié)點的參數(shù);c屬于[0,1]區(qū)間,t為實數(shù),且二者均為常數(shù)?？梢员硎緸?/p>

(2)

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

定義2近似等式約束

領(lǐng)域?qū)＜铱梢越o出類似這樣的斷言:某個網(wǎng)絡(luò)參數(shù)與另外一個參數(shù)近似相等;某個網(wǎng)絡(luò)參數(shù)是另外一個參數(shù)近似t倍;某個參數(shù)近似等于某個值等,可以表示為

(3)

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

(4)

式中,ε∈[0,1]。

2 先驗正態(tài)分布的BNs參數(shù)學(xué)習(xí)方法

2.1 近似等式約束的正態(tài)分布表示

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

因此,本文引入正態(tài)分布構(gòu)建近似等式約束的數(shù)學(xué)模型,如圖1所示。

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

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

(5)

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

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

(6)

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

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

2.2 基于貝葉斯MAP的參數(shù)估計

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

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

(7)

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

可以看出,式(7)中的參數(shù)估計值計算需要Dirichlet分布的超參數(shù),而正態(tài)分布的參數(shù)不能直接用于式(7)中,因此,采用第2.1節(jié)中先驗正態(tài)分布并不適合式(7)中的參數(shù)估計。為此,建立目標(biāo)優(yōu)化函數(shù),用Dirichlet分布逼近正態(tài)分布,獲取相應(yīng)的超參數(shù)。

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

min(DBeta-DG)2

(8)

式中,DBeta,DG分別為Beta分布和正態(tài)分布的方差;EBeta,EG分別為相應(yīng)的數(shù)學(xué)期望。對式(8)進(jìn)行求解,可得到Beta分布參數(shù),然后根據(jù)式(7)計算θijk的估計值。

3 實驗測試

3.1 實驗內(nèi)容

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

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

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

(3) 約束優(yōu)化方法:對于約束優(yōu)化這一類方法,以文獻(xiàn)[15]中的約束優(yōu)化方法為代表進(jìn)行比較測試。在本文的實驗測試中,利用近似等式約束構(gòu)建罰項函數(shù),且文獻(xiàn)[15]所給目標(biāo)優(yōu)化函數(shù)中的罰項權(quán)值設(shè)定為1,約束信任度設(shè)定為1。在采用降梯度法進(jìn)行求解時,步長設(shè)為1。

實驗測試首先采用如圖2所示的草坪濕潤推理BNs,該BNs被廣泛應(yīng)用于網(wǎng)絡(luò)推理和參數(shù)估計算法的測試中。

圖2 草坪濕潤推理貝葉斯網(wǎng)絡(luò)Fig.2 Structure of lawn wet Bayesian network

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

表1 節(jié)點S,R和W參數(shù)表

在實驗測試中,根據(jù)圖2網(wǎng)絡(luò)結(jié)構(gòu)和上述所給的參數(shù)真實值,采用隨機抽樣算法生成樣本數(shù)據(jù)。實驗測試環(huán)境為:操作系統(tǒng):Windows 7,處理器為:Intel CPU 3.30 GHz,平臺軟件為:Matlab R2014a。

3.2 測試結(jié)果1

(1)參數(shù)學(xué)習(xí)精度測試

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

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

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

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

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

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

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

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

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

(2)運行時間測試

在不同的樣本集下,對5種方法的運行時間進(jìn)行測試,每一種樣本集重復(fù)測試10次,統(tǒng)計各方法的平均運行時間,測試結(jié)果如表3所示。

表3 5種方法的運行時間

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

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

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

顯然,本文方法提高了參數(shù)學(xué)習(xí)精度,但增加了運行時間。但進(jìn)一步綜合比較學(xué)習(xí)精度和運行時間的測試結(jié)果,本文方法提高學(xué)習(xí)精度程度要遠(yuǎn)高于增加運行時間的程度。例如:10樣本集下,本文方法相比于約束優(yōu)化方法,精度提高了700多倍,運行時間增加了近10倍。因此,綜合考慮學(xué)習(xí)精度和運行時間,本文方法優(yōu)于其他4種方法。

3.3 測試結(jié)果2

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

參照第3.1節(jié)中的測試內(nèi)容和實驗測試環(huán)境,對Alarm BNs在數(shù)據(jù)樣本集:50,200,400,600,1 000,以BNs平均KL散度和運行時間為衡量指標(biāo),進(jìn)行實驗測試。其中,BNs平均KL散度與第3.2節(jié)中的相同,即為:網(wǎng)絡(luò)各節(jié)點的平均KL散度值的總和。

(1) BNs平均KL散度

測試過程中對Alarm BNs的37個節(jié)點的參數(shù)均加入近似等式約束,且所加入的近似等式約束按照第3.1節(jié)中(1)。對相同樣本量的樣本集重復(fù)測試10次,分別統(tǒng)計37個節(jié)點的平均KL散度值,并進(jìn)行相加求和,結(jié)果如圖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;約束優(yōu)化方法:0.259,0.169;貝葉斯MAP估計:0.245,0.163;先驗均勻分布方法:0.082,0.071;本文方法:0.017,0.016。本文方法和先驗均勻分布方法的平均KL散度均低于其他3種方法,即參數(shù)學(xué)習(xí)精度好于其他3種方法。

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

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

圖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種方法的運行時間進(jìn)行測試,重復(fù)測試10次,統(tǒng)計各方法的平均運行時間,測試結(jié)果如圖8所示。

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

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

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

4 結(jié) 論

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