柴慧敏, 趙昀瑤, 方 敏
(西安電子科技大學(xué)計(jì)算機(jī)學(xué)院, 陜西 西安 710071)
貝葉斯網(wǎng)絡(luò)(Bayesian networks, BNs)是將概率理論和圖論相結(jié)合的不確定性知識(shí)推理網(wǎng)絡(luò),對(duì)非精確知識(shí)表達(dá)方面具有較強(qiáng)的能力[1-2]。BNs可應(yīng)用于一些復(fù)雜系統(tǒng)的建模,如已成功地應(yīng)用于故障診斷[3-4]、圖像處理[5-6]、網(wǎng)絡(luò)安全[7-8]、態(tài)勢(shì)預(yù)測(cè)[9-10]等領(lǐng)域。
一個(gè)BNs由兩部分構(gòu)成:一是BNs結(jié)構(gòu),為有向非循環(huán)圖,表示了節(jié)點(diǎn)(變量)之間的依賴和獨(dú)立關(guān)系;二是網(wǎng)絡(luò)參數(shù),為各個(gè)節(jié)點(diǎn)條件概率參數(shù)的集合,是對(duì)節(jié)點(diǎn)間依賴關(guān)系的定量表示。在網(wǎng)絡(luò)結(jié)構(gòu)確定的情況下,如何確定正確的網(wǎng)絡(luò)參數(shù),即網(wǎng)絡(luò)參數(shù)學(xué)習(xí),是BNs應(yīng)用過程中的重要問題之一。
在一些實(shí)際的應(yīng)用中,如:故障診斷系統(tǒng)、戰(zhàn)場(chǎng)態(tài)勢(shì)評(píng)估中,樣本數(shù)據(jù)很難獲得,可能僅得到樣本量小或者數(shù)據(jù)不完整的樣本集。對(duì)于這樣的問題,一些研究人員提出在進(jìn)行參數(shù)學(xué)習(xí)時(shí),融入專家針對(duì)參數(shù)的先驗(yàn)知識(shí),以提高參數(shù)學(xué)習(xí)精度。這一過程也可視為在參數(shù)學(xué)習(xí)過程中加入約束條件[11]。
目前,針對(duì)參數(shù)的范圍約束、單調(diào)性約束等討論得較多,主要的解決方法有:文獻(xiàn)[12-14]提出通過建立基于凸約束的目標(biāo)優(yōu)化模型進(jìn)行求解;文獻(xiàn)[15]依據(jù)約束構(gòu)建罰項(xiàng)函數(shù),通過降梯度法求解目標(biāo)函數(shù)的最優(yōu)解,以獲得參數(shù)值;文獻(xiàn)[16-17]利用約束條件和蒙特卡羅抽樣方法,獲取表示先驗(yàn)Dirichlet分布的超參數(shù),再結(jié)合樣本數(shù)據(jù)進(jìn)行參數(shù)估計(jì);文獻(xiàn)[18-20]采用引入輔助BNs,完成約束條件下的BNs參數(shù)學(xué)習(xí);文獻(xiàn)[21]將先驗(yàn)約束融入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ì)法進(jìn)行參數(shù)估計(jì)。
而參數(shù)的近似等式約束也是一種較常見的專家先驗(yàn)知識(shí),例如:如果A發(fā)生,則B發(fā)生的可能性0.8,可得B參數(shù)的近似取值的先驗(yàn)知識(shí):P(B=true|A=true)=0.8。針對(duì)這一類約束,本文提出采用正態(tài)分布對(duì)該類約束進(jìn)行表示,得到先驗(yàn)正態(tài)分布;然后通過目標(biāo)優(yōu)化獲取先驗(yàn)Dirichlet分布的超參數(shù),采用貝葉斯最大后驗(yàn)概率(maximum a posteriori,MAP)估計(jì)方法計(jì)算網(wǎng)絡(luò)參數(shù)值。
對(duì)于BNs參數(shù)的學(xué)習(xí)過程中,可以得到一些定性的先驗(yàn)知識(shí),這些定性的先驗(yàn)知識(shí)主要可以描述為2種約束形式:線性不等式約束和近似等式約束。
定義1線性不等式約束
對(duì)于類似式(1)的專家先驗(yàn)知識(shí):
(1)
式中,Pk,Pk′為不同的網(wǎng)絡(luò)參數(shù),可以是同一節(jié)點(diǎn)的參數(shù),也可以是來自不同節(jié)點(diǎn)的參數(shù);c屬于[0,1]區(qū)間,t為實(shí)數(shù),且二者均為常數(shù)??梢员硎緸?/p>
(2)
式中,t0,tk均為實(shí)數(shù)。則式(2)為線性不等式約束。文獻(xiàn)[23-24]中的序約束,及參數(shù)的范圍約束實(shí)質(zhì)上就可以歸為線性不等式約束。
定義2近似等式約束
領(lǐng)域?qū)<铱梢越o出類似這樣的斷言:某個(gè)網(wǎng)絡(luò)參數(shù)與另外一個(gè)參數(shù)近似相等;某個(gè)網(wǎng)絡(luò)參數(shù)是另外一個(gè)參數(shù)近似t倍;某個(gè)參數(shù)近似等于某個(gè)值等,可以表示為
(3)
但具體應(yīng)用中,式(3)并不方便計(jì)算利用,則可采用式(4)的約束描述,即
(4)
式中,ε∈[0,1]。
對(duì)于式(4)的近似等式約束,假定參數(shù)Pk′先確定,ε取值較小,則可以將Pk限制在一個(gè)較小的范圍內(nèi),Pk可以取這個(gè)范圍的任意值。進(jìn)一步分析式(3)的專家先驗(yàn)知識(shí),可以看出,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è)的取值的概率將逐漸減小,符合近似等式約束的特點(diǎn)。則圖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)計(jì)算可得:δ=0.051 3。
由此,對(duì)式(4)的近似等式約束構(gòu)建正態(tài)分布模型時(shí),依據(jù)式(5)將期望設(shè)定為:Pk′,或者tPk′,或者c,而均方差為:δ=0.051 3。
貝葉斯MAP參數(shù)估計(jì)視參數(shù)為隨機(jī)變量,將參數(shù)的后驗(yàn)分布的最大值,作為該參數(shù)的估計(jì)值?,F(xiàn)假定BNs由n個(gè)節(jié)點(diǎn)構(gòu)成:X={X1,X2,…,Xn},節(jié)點(diǎn)Xi存在ri個(gè)狀態(tài)值,假定取值1,2,…,ri。其父節(jié)點(diǎn)Pa(Xi)的取值共有qi個(gè)組合,假定取值1,2,…,qi。則節(jié)點(diǎn)Xi的參數(shù)可表示為:θijk=P(Xi=k|Pa(Xi)=j),其中k,j分別表示節(jié)點(diǎn)Xi的取值和父節(jié)點(diǎn)的組合取值。
在貝葉斯MAP參數(shù)估計(jì)中,BNs參數(shù)的先驗(yàn)分布為Dirichlet分布,其超參數(shù)表示為D={aijk}。這樣參數(shù)的后驗(yàn)概率也將是Dirichlet分布,當(dāng)參數(shù)的后驗(yàn)分布取最大值時(shí),得到該參數(shù)的估計(jì)值為
(7)
式中,Nijk為樣本數(shù)據(jù)集中滿足Xi=k和Pa(Xi)=j的樣本的個(gè)數(shù)。先驗(yàn)Dirichlet分布的超參數(shù)可看作參數(shù)θijk的虛擬樣本數(shù)。
可以看出,式(7)中的參數(shù)估計(jì)值計(jì)算需要Dirichlet分布的超參數(shù),而正態(tài)分布的參數(shù)不能直接用于式(7)中,因此,采用第2.1節(jié)中先驗(yàn)正態(tài)分布并不適合式(7)中的參數(shù)估計(jì)。為此,建立目標(biāo)優(yōu)化函數(shù),用Dirichlet分布逼近正態(tài)分布,獲取相應(yīng)的超參數(shù)。
Dirichlet分布的邊緣分布為Beta分布,表示為Beta(a,b),則對(duì)應(yīng)到BNs中的每個(gè)參數(shù)θijk,其相應(yīng)的先驗(yàn)知識(shí)需要服從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é)期望。對(duì)式(8)進(jìn)行求解,可得到Beta分布參數(shù),然后根據(jù)式(7)計(jì)算θijk的估計(jì)值。
本文測(cè)試在完整樣本數(shù)據(jù)集下對(duì)本文方法的參數(shù)學(xué)習(xí)精度和運(yùn)行耗時(shí)進(jìn)行測(cè)試,并且與最大似然估計(jì)(maximum likelihood estimation, MLE)、無專家先驗(yàn)的貝葉斯MAP估計(jì)、約束優(yōu)化方法(constrained optimization approach, CO)、參照文獻(xiàn)[23-24]中的均勻分布表示先驗(yàn)的方法等4種主要方法進(jìn)行比較,需要說明的是:
(1) 本文方法:實(shí)驗(yàn)測(cè)試中采用的近似等式約束為式(4)中:|Pk-c|<ε,且ε=0.2,c為相應(yīng)參數(shù)的真實(shí)值。
(2) 無專家先驗(yàn)的貝葉斯MAP估計(jì):貝葉斯MAP估計(jì)中的先驗(yàn)Dirichlet分布的超參數(shù)一般來自專家先驗(yàn),在無專家先驗(yàn)的情況下,可采用一致先驗(yàn)的方式確定超參數(shù)[25],即:式(7)中的超參數(shù)aijk=1。本文的實(shí)驗(yàn)測(cè)試采用的是該種方式。
(3) 約束優(yōu)化方法:對(duì)于約束優(yōu)化這一類方法,以文獻(xiàn)[15]中的約束優(yōu)化方法為代表進(jìn)行比較測(cè)試。在本文的實(shí)驗(yàn)測(cè)試中,利用近似等式約束構(gòu)建罰項(xiàng)函數(shù),且文獻(xiàn)[15]所給目標(biāo)優(yōu)化函數(shù)中的罰項(xiàng)權(quán)值設(shè)定為1,約束信任度設(shè)定為1。在采用降梯度法進(jìn)行求解時(shí),步長設(shè)為1。
實(shí)驗(yàn)測(cè)試首先采用如圖2所示的草坪濕潤推理BNs,該BNs被廣泛應(yīng)用于網(wǎng)絡(luò)推理和參數(shù)估計(jì)算法的測(cè)試中。
圖2 草坪濕潤推理貝葉斯網(wǎng)絡(luò)Fig.2 Structure of lawn wet Bayesian network
該BNs參數(shù)的真實(shí)值為:根節(jié)點(diǎn)C:P(C=true)=0.5,P(C=false)=0.5。其他節(jié)點(diǎn)分別為表1所示。
表1 節(jié)點(diǎn)S,R和W參數(shù)表
在實(shí)驗(yàn)測(cè)試中,根據(jù)圖2網(wǎng)絡(luò)結(jié)構(gòu)和上述所給的參數(shù)真實(shí)值,采用隨機(jī)抽樣算法生成樣本數(shù)據(jù)。實(shí)驗(yàn)測(cè)試環(huán)境為:操作系統(tǒng):Windows 7,處理器為:Intel CPU 3.30 GHz,平臺(tái)軟件為:Matlab R2014a。
(1)參數(shù)學(xué)習(xí)精度測(cè)試
本文實(shí)驗(yàn)以KL散度為參數(shù)學(xué)習(xí)精度的衡量指標(biāo),在不同的數(shù)據(jù)樣本集下進(jìn)行了測(cè)試,測(cè)試過程中對(duì)圖2中的4個(gè)節(jié)點(diǎn)的參數(shù)均加入近似等式約束。測(cè)試樣本集樣本量分別為:10,20,30,50,100,對(duì)相同樣本量的樣本集重復(fù)測(cè)試10次,分別統(tǒng)計(jì)4個(gè)節(jié)點(diǎn):C,S,R,W的平均KL散度值,結(jié)果如表2所示。
由表2的測(cè)試結(jié)果可以看出,在參數(shù)學(xué)習(xí)精度方面,本文方法和先驗(yàn)均勻分布方法明顯要好于最大似然估計(jì)、無專家先驗(yàn)的貝葉斯MAP估計(jì)、約束優(yōu)化方法,尤其是在樣本量較小的情況下,如:10樣本集和20樣本集。但在樣本較多,即樣本充足的情況下,這5種方法的精度均能達(dá)到較好的水平,例如:在100樣本集下,4個(gè)節(jié)點(diǎn)的平均KL散度在5種方法中均沒有超過0.060。
單純分析本文方法和先驗(yàn)均勻分布,在不同的樣本集下采用本文方法,節(jié)點(diǎn)的平均KL散度多次出現(xiàn)為0.0,出現(xiàn)的次數(shù)為:13次,明顯多于先驗(yàn)均勻分布出現(xiàn)的次數(shù):5次。因此,本文方法的精度要更好于先驗(yàn)均勻分布方法。
為了從整體上比較這5種方法,將表2中不同的測(cè)試樣本集和不同的測(cè)試方法下,4個(gè)節(jié)點(diǎn)的平均KL散度值相加,得到圖2中的BNs的平均KL散度值,其結(jié)果如圖3所示。
表2 節(jié)點(diǎn)C,S,R,W的平均KL散度值
由圖3曲線可以看出:在樣本量為10、20、30的情況下,本文方法和先驗(yàn)均勻分布的精度高于其他3種方法,無專家先驗(yàn)的貝葉斯MAP估計(jì)法的精度高于約束優(yōu)化方法和最大似然估計(jì)方法。在樣本量為50、100的情況下,最大似然估計(jì)、無專家先驗(yàn)的貝葉斯MAP估計(jì)、約束優(yōu)化方法的精度近似趨于一致,但本文方法和先驗(yàn)均勻分布的精度仍高于其他3種方法。
為了進(jìn)一步分析本文方法和先驗(yàn)均勻分布方法,將圖3中的這2個(gè)方法的曲線單獨(dú)顯示,如圖4所示。
圖4 本文方法與先驗(yàn)均勻分布方法的平均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可以看出,本文方法和先驗(yàn)均勻分布方法均能得到較高的精度,但本文方法在5個(gè)樣本集下的精度都高于先驗(yàn)均勻分布方法。
(2)運(yùn)行時(shí)間測(cè)試
在不同的樣本集下,對(duì)5種方法的運(yùn)行時(shí)間進(jìn)行測(cè)試,每一種樣本集重復(fù)測(cè)試10次,統(tǒng)計(jì)各方法的平均運(yùn)行時(shí)間,測(cè)試結(jié)果如表3所示。
表3 5種方法的運(yùn)行時(shí)間
為了直觀顯示5種方法的運(yùn)行時(shí)間比較,給出如圖5的曲線表示。
圖5 5種方法運(yùn)行時(shí)間比較(草坪濕潤BNs)Fig.5 Comparison of run time for five method (lawn wet Bayesian network)
由圖5可以看出,本文方法和先驗(yàn)均勻分布方法的運(yùn)行時(shí)間近似相等,且耗時(shí)大于其他3種方法。
顯然,本文方法提高了參數(shù)學(xué)習(xí)精度,但增加了運(yùn)行時(shí)間。但進(jìn)一步綜合比較學(xué)習(xí)精度和運(yùn)行時(shí)間的測(cè)試結(jié)果,本文方法提高學(xué)習(xí)精度程度要遠(yuǎn)高于增加運(yùn)行時(shí)間的程度。例如:10樣本集下,本文方法相比于約束優(yōu)化方法,精度提高了700多倍,運(yùn)行時(shí)間增加了近10倍。因此,綜合考慮學(xué)習(xí)精度和運(yùn)行時(shí)間,本文方法優(yōu)于其他4種方法。
為了進(jìn)一步對(duì)本文所提出的方法進(jìn)行實(shí)驗(yàn)測(cè)試,選擇常用的用于測(cè)試的BNs:Alarm(www.norsys.com/netlibrary/index.htm),該BNs共有37個(gè)節(jié)點(diǎn),最多父節(jié)點(diǎn)個(gè)數(shù)為4個(gè)。
參照第3.1節(jié)中的測(cè)試內(nèi)容和實(shí)驗(yàn)測(cè)試環(huán)境,對(duì)Alarm BNs在數(shù)據(jù)樣本集:50,200,400,600,1 000,以BNs平均KL散度和運(yùn)行時(shí)間為衡量指標(biāo),進(jìn)行實(shí)驗(yàn)測(cè)試。其中,BNs平均KL散度與第3.2節(jié)中的相同,即為:網(wǎng)絡(luò)各節(jié)點(diǎn)的平均KL散度值的總和。
(1) BNs平均KL散度
測(cè)試過程中對(duì)Alarm BNs的37個(gè)節(jié)點(diǎn)的參數(shù)均加入近似等式約束,且所加入的近似等式約束按照第3.1節(jié)中(1)。對(duì)相同樣本量的樣本集重復(fù)測(cè)試10次,分別統(tǒng)計(jì)37個(gè)節(jié)點(diǎn)的平均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,本文方法和先驗(yàn)均勻分布方法的平均KL散度值均小于其他3種方法。而在樣本集為600,1 000時(shí),5種方法的平均KL散度分別為:最大似然估計(jì):0.266,0.176;約束優(yōu)化方法:0.259,0.169;貝葉斯MAP估計(jì):0.245,0.163;先驗(yàn)均勻分布方法:0.082,0.071;本文方法:0.017,0.016。本文方法和先驗(yàn)均勻分布方法的平均KL散度均低于其他3種方法,即參數(shù)學(xué)習(xí)精度好于其他3種方法。
為了進(jìn)一步分析本文方法和先驗(yàn)均勻分布方法,將圖6中的這兩個(gè)方法的曲線單獨(dú)顯示,如圖7所示。
由圖7可以看出,本文方法在5個(gè)樣本集下的參數(shù)學(xué)習(xí)精度均好于先驗(yàn)均勻分布方法。
圖7 本文方法與先驗(yàn)均勻分布方法的平均KL散度(Alarm BNs)Fig.7 Average KL divergence for the proposed method and the method of prior uniform distribution (Alarm Bayesian network)
(2)運(yùn)行時(shí)間
針對(duì)Alarm BNs,在樣本集:50,200,400,600,1 000下,對(duì)5種方法的運(yùn)行時(shí)間進(jìn)行測(cè)試,重復(fù)測(cè)試10次,統(tǒng)計(jì)各方法的平均運(yùn)行時(shí)間,測(cè)試結(jié)果如圖8所示。
圖8 5種方法運(yùn)行時(shí)間比較(Alarm BNs)Fig.8 Comparison of run time for five methods (Alarm wet Bayesian network)
圖8中,本文方法和先驗(yàn)均勻分布方法的運(yùn)行時(shí)間近似相等,但都大于其他3種方法。進(jìn)一步綜合比較KL散度和運(yùn)行時(shí)間,在樣本集:50, 200的測(cè)試中,本文方法相比于其他4種方法,參數(shù)學(xué)習(xí)精度的提高倍數(shù)遠(yuǎn)大于運(yùn)行時(shí)間的增加倍數(shù)。
在樣本集:600,1 000的測(cè)試中,本文方法相比較于其他4種方法學(xué)習(xí)精度提高的倍數(shù)為:最大似然估計(jì):15.65,11.00;約束優(yōu)化方法:15.24,10.56;貝葉斯MAP估計(jì):14.41,10.18;先驗(yàn)均勻分布方法:4.82,4.44。而運(yùn)行時(shí)間相比于其他4種方法增加的倍數(shù)依次為:最大似然估計(jì):2.26,1.45;約束優(yōu)化方法:1.16,1.12;貝葉斯MAP估計(jì):2.09,1.39;先驗(yàn)均勻分布方法:0.99,0.98??梢钥闯?本文方法參數(shù)學(xué)習(xí)精度提高的倍數(shù)均大于運(yùn)行時(shí)間增加的倍數(shù)。因此,綜合考慮學(xué)習(xí)精度和運(yùn)行時(shí)間,本文方法是優(yōu)于其他4種方法。
本文針對(duì)BNs參數(shù)的近似等式約束,提出了采用正態(tài)分布的先驗(yàn)表示方式,實(shí)驗(yàn)測(cè)試結(jié)果表明:該方法的參數(shù)學(xué)習(xí)精度好于最大似然估計(jì)、無專家先驗(yàn)的貝葉斯MAP估計(jì)、約束優(yōu)化方法等4種方法,而運(yùn)行時(shí)間要高于這4種方法。但綜合考慮比較KL散度和運(yùn)行時(shí)間,相比較于其他4種方法,本文方法參數(shù)學(xué)習(xí)精度提高的倍數(shù)均大于運(yùn)行時(shí)間增加的倍數(shù)。本文只是考慮了完整數(shù)據(jù)樣本下的參數(shù)學(xué)習(xí),后續(xù)需要進(jìn)一步研究缺失數(shù)據(jù)樣本下的學(xué)習(xí)問題。