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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

2.1 參數(shù)先驗(yàn)分布

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

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

(2)

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

(3)

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

(4)

(5)

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

根據(jù)貝葉斯估計(jì)和領(lǐng)域知識(shí)建立的先驗(yàn)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)在的方法都是將先驗(yàn)知識(shí)引入到參數(shù)學(xué)習(xí)過程之中,來彌補(bǔ)數(shù)據(jù)的不足。先驗(yàn)知識(shí)一般通過不同形式的參數(shù)約束來表示,主要的參數(shù)約束如表1所示。

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

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

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

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

(8)

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

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ū)域?yàn)椤鰿DE,類似于二維的情況,將其轉(zhuǎn)化為一個(gè)目標(biāo)最優(yōu)化問題,具體如下

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

(15)

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

(16)

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

通過(15)～(16)式可以求取約束區(qū)域的邊界點(diǎn),本文通過邊界點(diǎn)直接求平均的方式求取約束區(qū)域的中心點(diǎn),在二維情況下肯定能夠獲取中心點(diǎn)。在三維情況下,當(dāng)約束區(qū)域?yàn)槿切螘r(shí),可以獲得約束區(qū)域的中心點(diǎn),當(dāng)約束區(qū)域?yàn)樗倪呅螘r(shí),只能獲取近似的中心點(diǎn)。在高維情況下,也會(huì)存在只能獲取近似中心點(diǎn)的情況。這是本文算法精度稍差于QMAP算法的原因。

3.2 CMAP算法

CMAP算法的具體步驟如下:

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

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

(17)

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

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

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

3.3 算例說明

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

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

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

(18)

θ1,θ2,θ3,θ4組成了4維參數(shù)空間,首先判斷參數(shù)的約束類型是否包含第2節(jié)中的分布間約束,如果不包含,則可以利用參數(shù)的局部獨(dú)立性將待求參數(shù)進(jìn)行分解和降維。如果包含,則無法利用參數(shù)的局部獨(dú)立性將參數(shù)進(jìn)行分解和降維。很明顯,公式(18)中包含分布間約束θ1>θ3,無法利用參數(shù)局部獨(dú)立性。針對(duì)這種情況,本文利用標(biāo)準(zhǔn)單位基向量構(gòu)建目標(biāo)函數(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)給出了利用標(biāo)準(zhǔn)基向量構(gòu)建目標(biāo)優(yōu)化函數(shù)的方法。利用公式(19)～(22)可以求得參數(shù)約束域的4個(gè)邊界點(diǎn),進(jìn)而將這4個(gè)點(diǎn)的坐標(biāo)進(jìn)行平均,用平均所得的點(diǎn)來近似替代參數(shù)約束域的中心點(diǎn)。

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

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

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

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

(27)

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

4.1 仿真實(shí)驗(yàn)1

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

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

表4 不同算法的運(yùn)行時(shí)間比較

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

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

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

1) 所有算法的學(xué)習(xí)精度排序?yàn)镼MAP>CMAP>others。

2) 所有算法運(yùn)行時(shí)間的大致排序?yàn)镼MAP>CME>CMAP>others。

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

4.2 仿真實(shí)驗(yàn)2

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

1) 所有算法的學(xué)習(xí)精度排序?yàn)镼MAP>CMAP>others。

所有算法的運(yùn)行時(shí)間的大致排序?yàn)镼MAP>CME>CMAP>others

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

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

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

表6 不同算法的運(yùn)行時(shí)間比較

5 結(jié) 論

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