基于改進QMAP的貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)算法

邸若海, 李葉, 萬開方, 呂志剛, 王鵬

(1.西安工業(yè)大學(xué) 電子信息工程學(xué)院, 陜西 西安 710021; 2.西北工業(yè)大學(xué) 電子信息學(xué)院, 陜西 西安 710072)

針對小數(shù)據(jù)集條件下的貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)問題，目前主要通過引入?yún)?shù)約束來優(yōu)化參數(shù)學(xué)習(xí)過程。根據(jù)約束數(shù)量的不同，現(xiàn)有的研究分為單一約束和多種約束2種情況。

針對單一約束，Writting等[1]利用定性影響約束構(gòu)造懲罰函數(shù)，并將最大熵函數(shù)與懲罰函數(shù)結(jié)合構(gòu)造目標優(yōu)化函數(shù)，最后利用改進的APN算法對參數(shù)進行求解；Feelders等[2-3]將定性影響條件下的參數(shù)學(xué)習(xí)看作一個保序回歸問題，首先采用最大似然估計算法得到參數(shù)初始值，然后結(jié)合定性影響約束和保序回歸法估計參數(shù)。Plajner等[4]分別利用梯度下降法、保序回歸來處理單調(diào)性約束，大幅度提高了參數(shù)學(xué)習(xí)的精度。國內(nèi)學(xué)者周鋆等[5]通過引入平滑先驗來優(yōu)化似然函數(shù)，并將定性影響約束作為一個懲罰項與改進后的似然函數(shù)構(gòu)成參數(shù)目標優(yōu)化函數(shù)，采用梯度下降方法進行求解。邸若海等[6-7]通過構(gòu)造單調(diào)性約束表示專家經(jīng)驗，然后將單調(diào)性約束轉(zhuǎn)化為狄利克雷分布的超參數(shù)，進而結(jié)合最大后驗概率估計獲取貝葉斯網(wǎng)絡(luò)參數(shù)。任佳等[8]采用區(qū)間約束限制參數(shù)學(xué)習(xí)，將區(qū)間約束轉(zhuǎn)化為貝塔分布的超參數(shù)，進而結(jié)合貝葉斯估計學(xué)習(xí)參數(shù)。黃政等[9]將近似相等的先驗約束以正態(tài)分布的形式融入到單調(diào)性約束的貝葉斯參數(shù)學(xué)習(xí)過程中，提高了參數(shù)學(xué)習(xí)的精度。

由于單一約束方法一般只針對某種特殊的專家知識，限制了專家經(jīng)驗的利用，學(xué)習(xí)精度一般。因此，利用多種約束進行參數(shù)學(xué)習(xí)受到了更多的關(guān)注。Niculescu等[10]和Campos等[11]提出基于凸優(yōu)化的參數(shù)學(xué)習(xí)方法。Liao等[12]結(jié)合EM算法，將約束引入到數(shù)據(jù)缺失條件下的BN參數(shù)學(xué)習(xí)。Zhou等[13-14]提出約束多項式分布參數(shù)學(xué)習(xí)(multinomial parameter learning with constraints,MPL-C)方法。郭志高等[15]提出基于雙重約束的參數(shù)學(xué)習(xí)方法。Rui等[16]提出基于定性最大后驗概率(qualitative maximum a posterior,QMAP)的參數(shù)學(xué)習(xí)方法，采用拒絕-接受采樣的方法獲取滿足約束的模型參數(shù)，并利用采樣所得參數(shù)的均值替代先驗參數(shù)的分布，進而利用MAP計算對應(yīng)的模型參數(shù)的后驗估計。與其他算法相比，QMAP算法不僅給出了一個在多約束條件下的貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)通用框架，而且具有較好的學(xué)習(xí)效果。在此基礎(chǔ)上，Guo等[17]利用QMAP算法學(xué)習(xí)參數(shù)，并進一步利用參數(shù)約束判斷參數(shù)的合理性，避免了QMAP算法所得參數(shù)不滿足約束的情況。然而，當網(wǎng)絡(luò)復(fù)雜度變大，參數(shù)約束較多或約束可行域較小時，由于拒絕-接受采用算法本身的隨機性，導(dǎo)致難以獲得滿足約束的參數(shù)。從而導(dǎo)致QMAP算法非常耗時。

針對上述問題，本文設(shè)計了一種新的約束區(qū)域中心點的解析計算方法來替代原有的拒絕-采樣方法，在此基礎(chǔ)上，提出了CMAP(constrained maximum a posteriori)算法。首先，設(shè)計一種新的目標函數(shù)，結(jié)合參數(shù)約束構(gòu)建一個帶約束的目標優(yōu)化問題；其次，利用一種尋優(yōu)引擎來求解該目標優(yōu)化問題獲得約束區(qū)域的邊界點和中心點，最終以獲得的中心點作為待求參數(shù)的先驗分布，并利用MAP求取待求參數(shù)的后驗估計。

1 貝葉斯網(wǎng)絡(luò)

下面給出貝葉斯網(wǎng)絡(luò)一般的定義：

定義1貝葉斯網(wǎng)絡(luò)[18]由結(jié)構(gòu)G和參數(shù)Θ兩部分組成。貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)為一個有向無環(huán)圖G=(V,E),其中節(jié)點變量集合V={X1,X2,…,Xn}表示變量,有向邊集合E描述變量間的依賴關(guān)系。貝葉斯網(wǎng)絡(luò)的參數(shù)Θ={θi}i=1,2,…,n為一組條件概率分布,每個節(jié)點存儲其自身與其父節(jié)點集之間的條件概率分布,即P(Xi|Pa(Xi))。

即貝葉斯網(wǎng)絡(luò)包含定性和定量兩部分內(nèi)容。在定性層面,有向無環(huán)圖描述變量之間的依賴或獨立關(guān)系。在定量層面,條件概率分布表示變量之間依賴程度的大小。

貝葉斯網(wǎng)絡(luò)通過引入條件獨立性完成了聯(lián)合概率分布的分解,它將聯(lián)合概率分布P分解為

(1)

式中,Xi可取離散值和連續(xù)值。

2 參數(shù)的先驗分布及約束類型

2.1 參數(shù)先驗分布

貝葉斯公式將先驗分布和似然函數(shù)結(jié)合,得到θ后驗分布即

P(θ|D)∝P(θ)L(θ|D)

(2)

式中,概率分布P(θ)表示θ的先驗知識,似然函數(shù)L(θ|D)=P(D|θ)表示數(shù)據(jù)集D的影響。在i.i.d條件下,(2)式中L(θ|D)為多項式似然函數(shù)的共軛分布,假設(shè)先驗分布P(θ)是Dirichlet分布,即

(3)

則后驗分布P(θ|D)也是Dirichlet分布。在觀測樣本下,θ的后驗分布P(θ|D)為

(4)

(5)

Dirichlet先驗分布中參數(shù)的物理意義不明顯,領(lǐng)域?qū)＜译y以直接確定,在實際應(yīng)用中存在困難。根據(jù)Dirichlet分布特性,其條件分布和邊緣分布都是Beta分布且Beta分布為二項式分布的共軛分布族,因此可以通過確定Beta分布中的2個形參來近似表達與其相關(guān)的領(lǐng)域知識。

根據(jù)貝葉斯估計和領(lǐng)域知識建立的先驗Beta分布模型,在i.i.d條件下(6)式成立

P(θ)=B[α1,α2]θα1-1(1-θ)α2-1

(6)

(7)

2.2 參數(shù)約束類型

基于小數(shù)據(jù)集的參數(shù)學(xué)習(xí),僅依靠數(shù)據(jù)已經(jīng)不能獲取滿足精度要求的參數(shù)。因此,現(xiàn)在的方法都是將先驗知識引入到參數(shù)學(xué)習(xí)過程之中,來彌補數(shù)據(jù)的不足。先驗知識一般通過不同形式的參數(shù)約束來表示,主要的參數(shù)約束如表1所示。

表1 參數(shù)約束類型

3 基于改進QMAP的貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)算法

3.1 低維參數(shù)約束域的可視化及中心點計算

首先分析參數(shù)約束區(qū)域的特點,分別給出二維和三維情況下約束區(qū)域中心點的計算方法。在二維狀態(tài)下,假設(shè)參數(shù)滿足以下約束

(8)

通過將約束區(qū)域可視化,圖1中加粗的線條區(qū)域就是參數(shù)的約束域,即線段AC。只需獲取A點和C點的坐標,即可獲得線段AC的中點。本文將求取點A和C坐標的問題轉(zhuǎn)化為一個帶約束的優(yōu)化問題,通過公式(9)可以求取點C的坐標,通過公式(10)可以求取A點的坐標。

min[(θ1-0)2+(θ2-1)2]

(9)

min[(θ1-1)2+(θ2-0)2]

(10)

圖1 二維參數(shù)的可行域

在三維情況下,假設(shè)參數(shù)滿足以下約束

(11)

圖2 三維參數(shù)的可行域

從圖2可以看出,參數(shù)的約束區(qū)域為△CDE,類似于二維的情況,將其轉(zhuǎn)化為一個目標最優(yōu)化問題,具體如下

下面給出本文參數(shù)約束域中心點計算的一般化的方法,設(shè)待求參數(shù)

(15)

當參數(shù)不包含分布間約束時,可根據(jù)參數(shù)的局部獨立性,將上述高維(mq)的優(yōu)化問題化簡為低維(m)的優(yōu)化問題。具體如下所示：

(16)

式中,w=1,2,…,q,總共需要求解mq個m維的優(yōu)化問題。

通過(15)～(16)式可以求取約束區(qū)域的邊界點,本文通過邊界點直接求平均的方式求取約束區(qū)域的中心點,在二維情況下肯定能夠獲取中心點。在三維情況下,當約束區(qū)域為三角形時,可以獲得約束區(qū)域的中心點,當約束區(qū)域為四邊形時,只能獲取近似的中心點。在高維情況下,也會存在只能獲取近似中心點的情況。這是本文算法精度稍差于QMAP算法的原因。

3.2 CMAP算法

CMAP算法的具體步驟如下:

步驟1 記錄樣本數(shù)據(jù)中的節(jié)點狀態(tài)統(tǒng)計量Nij和Nijk。

步驟2 利用優(yōu)化引擎求解(15)～(16)式,以求取參數(shù)約束的邊界點,進而對邊界點進行平均,獲取參數(shù)約束的中心點。利用中心點替代待求參數(shù)的先驗分布,進而代入最大后驗估計公式(17)獲取待求參數(shù)的后驗估計。

(17)

式中：Mijk=A*P(Xi=k|Πi=j,Ω),A為等價樣本量。P(Xi=k|Πi=j,Ω)為待求參數(shù)的先驗分布,這里用中心點的坐標替代。這是本文算法與QMAP算法最大的不同。QMAP算法是用得到滿足約束的參數(shù)均值替代參數(shù)的先驗分布。

步驟3 利用交叉驗證方法確定系數(shù)A即等價樣本量。

步驟4 根據(jù)公式(17)完成定性最大后驗概率估計。

3.3 算例說明

為了更好地解釋本文的算法,接下來通過一個簡單的算例來說明。

圖3 一個簡單的貝葉斯網(wǎng)絡(luò)

假設(shè)圖3中節(jié)點B的參數(shù)是待求的參數(shù),此時,已知的參數(shù)約束為

(18)

θ1,θ2,θ3,θ4組成了4維參數(shù)空間,首先判斷參數(shù)的約束類型是否包含第2節(jié)中的分布間約束,如果不包含,則可以利用參數(shù)的局部獨立性將待求參數(shù)進行分解和降維。如果包含,則無法利用參數(shù)的局部獨立性將參數(shù)進行分解和降維。很明顯,公式(18)中包含分布間約束θ1>θ3,無法利用參數(shù)局部獨立性。針對這種情況,本文利用標準單位基向量構(gòu)建目標函數(shù)

(θ3-0)2+(θ4-0)2]

(19)

(θ3-0)2+(θ4-0)2]

(20)

(θ3-1)2+(θ4-0)2]

(21)

(θ3-0)2+(θ4-1)2]

(22)

公式(19)～(22)給出了利用標準基向量構(gòu)建目標優(yōu)化函數(shù)的方法。利用公式(19)～(22)可以求得參數(shù)約束域的4個邊界點,進而將這4個點的坐標進行平均,用平均所得的點來近似替代參數(shù)約束域的中心點。

假設(shè)參數(shù)約束中不包含分布間約束,便可利用參數(shù)的局部獨立性將其分解。具體如下所示：

由(23)～(26)式可知,當參數(shù)約束中不存在分布間約束時,可以將原來4維的參數(shù)約束空間分解為2個2維的參數(shù)約束空間,降低待求問題的復(fù)雜度。

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

為了驗證本文算法的有效性,分別利用Asia、Alarm、Win95PTs和Andes網(wǎng)絡(luò)進行仿真驗證。這些網(wǎng)絡(luò)經(jīng)常被用于貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)和參數(shù)學(xué)習(xí)算法驗證,表2給出了這幾個網(wǎng)絡(luò)的基本信息。采用平均KL距離來衡量參數(shù)學(xué)習(xí)的精度,公式(27)給出了KL距離的計算公式,其中P(X)表示求出的樣本分布,Q(X)表示真實的樣本分布。采用平均運行時間來衡量算法的效率。本文中的運行時間是通過Matlab中的Tic-Toc指令獲取。算法運行20次,求均值和方差。

(27)

表2 仿真網(wǎng)絡(luò)信息

4.1 仿真實驗1

本節(jié)考慮參數(shù)的分布間約束,部分仿真結(jié)果如表3所示。

表3 不同算法的KL距離比較

表4 不同算法的運行時間比較

圖4 不同算法的平均運行時間比較(Alarm網(wǎng)絡(luò))

圖5 不同算法的平均KL距離比較(Alarm網(wǎng)絡(luò))

通過對表3～4和圖4～5中的實驗結(jié)果進行分析,可以得到以下結(jié)論:

1) 所有算法的學(xué)習(xí)精度排序為QMAP>CMAP>others。

2) 所有算法運行時間的大致排序為QMAP>CME>CMAP>others。

3) 本文提出的CMAP的學(xué)習(xí)精度稍差于QMAP算法,但運行效率高于QMAP算法。

4.2 仿真實驗2

本節(jié)不考慮參數(shù)的分布間約束,則可通過公式(16)對公式(15)進行降維,通過對表5～6和圖6～7中的實驗結(jié)果進行分析,可以得到以下結(jié)論:

1) 所有算法的學(xué)習(xí)精度排序為QMAP>CMAP>others。

所有算法的運行時間的大致排序為QMAP>CME>CMAP>others

表5 不同算法的KL距離比較

圖6 不同算法的平均KL距離比較(Alarm網(wǎng)絡(luò))

圖7 不同算法的平均運行時間比較(Alarm網(wǎng)絡(luò))

表6 不同算法的運行時間比較

5 結(jié) 論

為了提高QMAP算法的學(xué)習(xí)效率同時又不影響其學(xué)習(xí)精度，本文設(shè)計了一種新的約束區(qū)域中心點的解析計算方法來替代原有的拒絕-接受采樣計算方法。仿真實驗證明，本文提出的CMAP算法的參數(shù)學(xué)習(xí)精度稍差于QMAP算法，但計算效率比QMAP算法高出一個量級。缺點是CMAP算法仍涉及最優(yōu)化問題求解的引擎，引擎的優(yōu)劣直接決定了算法的時效性，下一步研究工作是引入更高效的引擎用于求解參數(shù)約束域的中心點，進一步提高本文提出的參數(shù)學(xué)習(xí)方法的效率。