布爾型貝葉斯網(wǎng)絡參數(shù)學習

吳永廣，周興旺

(空軍航空大學基礎(chǔ)部，長春 130022)

隨著互聯(lián)網(wǎng)技術(shù)發(fā)展，大數(shù)據(jù)時代的4V特性:Volume(大量)、Velocity(高速)、Variety(多樣)、Value(價值)，對海量數(shù)據(jù)處理的能力提出了更高的要求。貝葉斯網(wǎng)絡理論的發(fā)展適應了大數(shù)據(jù)特性，它以靈活的推理能力和知識表達能力受到了學者的廣泛認可。貝葉斯網(wǎng)絡理論在人工智能、數(shù)據(jù)挖掘、統(tǒng)計決策、醫(yī)療診斷、專家系統(tǒng)、軍事評估等領(lǐng)域［1－2］發(fā)揮重要作用。關(guān)于貝葉斯網(wǎng)絡學習的理論和方法也不斷被提出和改進來滿足實際的需要:從靜態(tài)貝葉斯網(wǎng)絡發(fā)展到了動態(tài)貝葉斯網(wǎng)絡，實時動態(tài)地分析處理數(shù)據(jù)能力不斷改善［3］;從專家知識表示發(fā)展到了智能化學習算法［4］，對于知識表達也更加客觀合理;從推理算法到貝葉斯分類算法也呈現(xiàn)了多樣性的發(fā)展趨勢［5］。擺脫專家知識的主觀性，基于數(shù)據(jù)知識驅(qū)動下的貝葉斯網(wǎng)絡參數(shù)學習算法將對數(shù)據(jù)挖掘、人工智能發(fā)展具有重大意義。

1 參數(shù)學習研究現(xiàn)狀

貝葉斯網(wǎng)絡學習算法分為結(jié)構(gòu)學習和參數(shù)學習兩步驟。專家構(gòu)建網(wǎng)絡模型或者結(jié)構(gòu)學習是參數(shù)學習的前提和基礎(chǔ)。參數(shù)學習依據(jù)學習的樣本數(shù)據(jù)劃分為完整數(shù)據(jù)下和不完整數(shù)據(jù)下的貝葉斯網(wǎng)絡參數(shù)學習。最大似然估計算法［6］作為統(tǒng)計學的經(jīng)典算法，它是具有理論性的點估計法，為參數(shù)學習算法奠定了基礎(chǔ)。貝葉斯估計算法［7］以狄利克雷分布作為先驗概率，這樣參數(shù)θ的后驗概率也服從狄利克雷分布，它將先驗知識和樣本數(shù)據(jù)統(tǒng)一起來，以共軛先驗分布為前提，隨著樣本數(shù)據(jù)的增加而逐漸減少對先驗知識的依賴。Lauriten［8］提出的基于EM算法下的可以應用于數(shù)據(jù)缺失情況下的貝葉斯網(wǎng)絡的參數(shù)學習，它通過不斷修正初始估計參數(shù)值θ來最大化似然函數(shù)或者后驗概率，尋找最優(yōu)參數(shù)。面向大規(guī)模數(shù)據(jù)集的貝葉斯網(wǎng)絡參數(shù)學習算法［9］通過改進E步驟試圖通過更新部分數(shù)據(jù)塊的期望值來降低EM算法的計算量，同時提高計算精度。這些傳統(tǒng)的參數(shù)學習算法都是以狄利克雷、高斯分布描述參數(shù)的分布律，且變量的參數(shù)服從同一分布，它對參數(shù)學習過于理想化，應用中的貝葉斯網(wǎng)絡的節(jié)點分布律難以同實際相結(jié)合，制約了其在應用中的價值。

2 布爾型貝葉斯參數(shù)學習算法

布爾型網(wǎng)絡結(jié)構(gòu)下的參數(shù)學習方法在處理數(shù)據(jù)方法上有了很大改進，二進制的隨機變量能夠進行邏輯運算，方便了數(shù)據(jù)處理?？紤]到指示變量對算法復雜度影響，引入連接樹(Junction Tree)算法［10］對布爾型網(wǎng)絡函數(shù)分解，使數(shù)據(jù)處理更加易于實現(xiàn)，提高了效率。通過引用布爾型網(wǎng)絡函數(shù)，利用最大似然估計最優(yōu)化參數(shù)的方法將為參數(shù)學習及其實際應用提供有力的理論支撐。

2.1 布爾型網(wǎng)絡

網(wǎng)絡的拓撲結(jié)構(gòu)研究廣泛，其中布爾型網(wǎng)絡是指一類具有二值(True，F(xiàn)alse)節(jié)點集組成的貝葉斯網(wǎng)絡，它繼承了網(wǎng)絡分析處理的能力，且易于計算機實現(xiàn)。從化學，生物，到經(jīng)濟計算機科學，基于布爾網(wǎng)絡的網(wǎng)絡應用程序可以在許多領(lǐng)域發(fā)現(xiàn)其價值［11］。Darwiche教授對布爾型貝葉斯網(wǎng)絡推理也有深入研究，通過引入證據(jù)變量的方法對于處理布爾型貝葉斯網(wǎng)絡具有很好的效果［12－13］。在他們研究的基礎(chǔ)上，本文提出了針對布爾型貝葉斯網(wǎng)絡的參數(shù)學習。

定義一個布爾型函數(shù)

證據(jù)變量λx:對于貝葉斯網(wǎng)絡參數(shù)X，變量λx代表事件發(fā)生的狀態(tài)，為布爾型變量。引入證據(jù)變量，使證據(jù)事件同變量的狀態(tài)結(jié)合，能夠很好地通過線性函數(shù)表達式進行分析處理。

參數(shù)變量θx|u:對于任意的父節(jié)點u及其子節(jié)點x，以θx|u表示網(wǎng)絡參數(shù)在父節(jié)點狀態(tài)發(fā)生時的條件概率。當父節(jié)點不存在時，θx|u表示節(jié)點概率值。

如圖1所示，當X和U為布爾型變量，以節(jié)點A為父節(jié)點，B和C為子節(jié)點的貝葉斯網(wǎng)絡線性表達式為

證據(jù)事件e發(fā)生時，線性多項式f的函數(shù)值以fe表示。證據(jù)事件通過λx影響函數(shù)的取值。當變量x與證據(jù)事件e一致時，證據(jù)變量取值為1;如果變量x與證據(jù)事件對立時，證據(jù)變量取值為0;當變量x同證據(jù)事件e不存在相互影響的關(guān)系時，則證據(jù)變量以未知參數(shù)λx形式存在。

圖1 布爾型網(wǎng)絡概率表

對函數(shù)作偏微分計算

證據(jù)變量的微分特性［12］

證據(jù)運算具有邏輯運算的特點，它對于處理變量關(guān)系的運算和性質(zhì)有重要作用。當證據(jù)變量e實例化為b，變量x取值為時，e－X表示為時，證據(jù)變量表述為

這樣，變量的概率同變量的偏微分成了互相轉(zhuǎn)化的函數(shù)關(guān)系，對于計算節(jié)點聯(lián)合概率，分析變量概率特性有重要作用，同時也使復雜數(shù)據(jù)處理過程變得簡單化。

參數(shù)變量的微分特性，描述了節(jié)點變量的父子節(jié)點和證據(jù)的聯(lián)合概率同參數(shù)變量偏微分值的等價關(guān)系，是離散變量的另一重要性質(zhì)［12］

在證據(jù)e作為學習樣本數(shù)據(jù)時，使得觀察證據(jù)e、父節(jié)點u和子節(jié)點x的聯(lián)合概率分布最大化，參數(shù)變量θx|u則為參數(shù)變量的最大似然估計。

2.2 基于連接樹的網(wǎng)絡分解

貝葉斯網(wǎng)絡學習是一個NP-Hard難題，節(jié)點數(shù)量上升對算法性能有很大影響。為了簡化算法，PL-EM算法就是對數(shù)據(jù)樣本進行并行性劃分來提高EM算法的效率［14］?；谌斯~群算法的參數(shù)學習算法［15］通過人工魚的覓食、聚群和追尾行為進行搜索，以調(diào)整人工魚隨機移動速度的方法提高了算法的收斂性能和速度。目前基于貝葉斯網(wǎng)絡的推理研究人員提出了多種精確和近似推理算法，其中連接樹(Junction Tree)算法在貝葉斯網(wǎng)絡精確推理算法中具有計算速度快、應用廣泛的特點。它能夠?qū)⒁粋€復雜的網(wǎng)絡進行合理地分解，簡化運算。

首先將貝葉斯網(wǎng)絡進行去向處理，使網(wǎng)絡有向圖變成對應的摩爾圖，實現(xiàn)道義化，再將道義化后的無向圖轉(zhuǎn)化為一個有弦圖，就可以生成一棵連接樹，最后根據(jù)連接樹的特性及算法進行推理。

通過引入勢(Potentials)函數(shù)理論［16］可以證明連接樹分解算法的合理性。一組變量X上的勢定義為一個函數(shù)，每個變量對應的值x稱為它的實例。勢函數(shù)能夠?qū)嵗成錇橐粋€非零實數(shù)，用φx表示。勢可以構(gòu)成向量或矩陣，也可以實現(xiàn)邊緣化并進行乘法算法:

1)假設(shè)有一組變量Y，它的勢為φy;另外有一組變量X，X?Y，則

2)給定兩組變量X和Y以及它們的勢φx和φy，若X?Y，則

根據(jù)勢函數(shù)理論，節(jié)點簇的勢可用φx表示，分割集的勢可用φy表示。容易證明貝葉斯網(wǎng)絡的聯(lián)合概率分布可以表示為［12］

2.3 基于最大似然估計參數(shù)算法

Spiegelhalter于1992年將最大似然估計(maximum likelihood estimation，MLE)方法成功應用于參數(shù)學習，以數(shù)據(jù)集中的變量狀態(tài)影響參數(shù)的取值。最大似然估計方法就是基于實例化參數(shù)變量思想，實現(xiàn)最大似然化目標函數(shù)。

選取觀測數(shù)據(jù)集 D=(d1，d2，d3，…，dn)，每個觀測數(shù)據(jù)是一個樣本點，表示貝葉斯網(wǎng)絡中各節(jié)點的觀測值。參數(shù)θs表示待學習的參數(shù)變量，以向量形式表示。參數(shù)學習是基于貝葉斯網(wǎng)絡結(jié)構(gòu)已知的情況下進行(見圖2)，以G表示網(wǎng)絡結(jié)構(gòu)。最大似然估計在參數(shù)學習中應用表述如下

布爾函數(shù)是以線性多參數(shù)表達式形式存在，在計算過程中引入了n個指示變量，在方便數(shù)據(jù)處理的同時，也增加了算法的復雜度。根據(jù)布爾函數(shù)表達式f可知，求積項數(shù)目可以表示為O(2n)，求和項數(shù)目以指數(shù)階O(2n)上升。當節(jié)點數(shù)上升時，線性表達函數(shù)復雜度以指數(shù)形式增加，導致參數(shù)θs維度上升，算法的效率在不斷下降，甚至參數(shù)學習無法收斂到一個最優(yōu)解。引入連接樹算法對于復雜貝葉斯網(wǎng)絡的處理意義重大，它合理地分解網(wǎng)絡，能夠除去不相關(guān)的狀態(tài)變量對參數(shù)學習的影響。

圖3是圖2所對應的連接樹，圖3中的橢圓代表連接樹的節(jié)點Ci，節(jié)點里的一組變量構(gòu)成一個節(jié)點簇，方框代表節(jié)點之間的分割集。該連接樹具有以下屬性［16］:

1)任意兩相鄰節(jié)點Ci和Cj之間的邊Tij對應節(jié)點集Ci∩Cj，并稱 Tij為 Ci和 Cj之間的分割集。

2)連接樹中任意兩節(jié)點Ci和Cj之間的路徑上的每條邊和節(jié)點對應的變量集都包含Ci∩Cj。

將數(shù)據(jù)集合D劃分為不同的證據(jù)集合，按照證據(jù)變量取值是否相同進行分類，D=(e1，e2，e3，…en)。連接樹分解后的貝葉斯網(wǎng)絡以節(jié)點簇和分割集為單元進行參數(shù)學習。通過比較網(wǎng)絡示意圖和連接樹，可以發(fā)現(xiàn)證據(jù)集e的數(shù)目上升，證據(jù)e維度在下降。根據(jù)不同證據(jù)集合的相關(guān)性可知

對于各證據(jù)集，證據(jù)事件發(fā)生的可能性是不相同的，使所有證據(jù)發(fā)生的可能性都最大化是不合理的。引入線性權(quán)重向量 w=(w1，w2，w3，…wn)，wi=nei/ND來描述不同證據(jù)在似然函數(shù)中的重要性，可以解決證據(jù)變量的相關(guān)性問題。理想?yún)?shù)θs能夠使函數(shù)wP(x，u，e)的取值最大化，根據(jù)最大似然函數(shù)可知，使wP(x，u，e)函數(shù)取極大值下的參數(shù)?θs≈θs。

圖2 貝葉斯網(wǎng)絡

圖3 連接樹

當數(shù)據(jù)D以證據(jù)形式存在時，P(D)作為一個常量，P(θ)由參數(shù)決定，在沒有先驗知識的情況下，不同參數(shù)θ發(fā)生概率是未知的，P(θ)假定為一個未知的常量，引入貝葉斯定理

由上式可知

結(jié)合公式最優(yōu)化wP(x，u，e)

似然函數(shù)取對數(shù)處理，得到的是參數(shù)學習對數(shù)似然函數(shù)，表示如下

通過計算獲取對數(shù)似然函數(shù)極值，找到滿足條件的參數(shù)

極大似然估計，在統(tǒng)計學中有著重要的應用，它是一種重要的參數(shù)學習方法。在離散變量概率學習中，它通過選取合適的似然函數(shù)，能夠快速有效地實現(xiàn)參數(shù)學習。極大似然估計作為一種依賴粗略數(shù)學期望的算法，在實際中已廣泛應用。在工程應用領(lǐng)域中，有些樣本的概率是不得而知的，需要通過若干重復實驗的方法獲取樣本數(shù)據(jù)，依據(jù)這些數(shù)據(jù)，推理出這些條件概率參數(shù)值，極大似然方法就建立在這個基礎(chǔ)上的。如果某個參數(shù)能夠最大化樣本數(shù)據(jù)發(fā)生概率，忽略噪聲對數(shù)據(jù)影響，它是基于已獲得的數(shù)據(jù)知識下的最真實值。

3 結(jié)論

布爾型貝葉斯網(wǎng)絡參數(shù)學習算法是基于似然函數(shù)估計的方法，引入證據(jù)的方法處理數(shù)據(jù)行之有效，它以優(yōu)化線性多元函數(shù)的方式最優(yōu)化參數(shù)，對于參數(shù)學習在應用中推廣有很大價值。連接樹的算法能夠合理分解降低學習未知參數(shù)變量的維度，提高似然函數(shù)算法的性能。但算法局限于布爾型網(wǎng)絡在一定程度下影響其應用范圍，下一步將重點使算法推廣到多值變量的處理中。

［1］ Julia Flores M，Nicholson A E，Brunskill A，et al.Incorporating expert knowledge when learning Bayesian network structure:a medical case study［J］.Artificial intelligence in medicine，2011，53(3):181 －204.

［2］ Park C Y，Laskey K B，Costa P C G，et al.Multi-Entity Bayesian Networks Learning In Predictive Situation Awareness［C］//Proceedings of the 18th International Command and Control Technology and Research Symposium.［S.l.］:［s.n.］，2013.

［3］ 黃世強，高曉光，任佳.DDBN的無人機決策推理模型參數(shù)學習［J］.火力與指揮控制，2013，38(1):26 －29.

［4］ Masegosa A R，Moral S.An interactive approach for Bayesian network learning using domain expert knowledge［J］.International Journal of Approximate Reasoning，2013，54(8):1168－1181.

［5］ Ngai E W T，Hu Y，Wong Y H，et al.The application of data mining techniques in financial fraud detection:A classification framework and an academic review of literature［J］.Decision Support Systems，2011，50(3):559 －569.

［6］ Spiegelhalter D J，Dawid A P，Lauritzen S L，et al.Bayesian analysis in expert systems［J］.Statistical science，1993，8(3):219－247.

［7］ Heckerman D.A tutorial on learning with Bayesian networks［M］.US:Springer Netherlands，1998.

［8］ Lauritzen S L.The EM algorithm for graphical association models with missing data［J］.Computational Statistics ＆Data Analysis，1995，19(2):191 －201.

［9］ 張少中，章錦文，張志勇，等.面向大規(guī)模數(shù)據(jù)集的貝葉斯網(wǎng)絡參數(shù)學習算法［J］.計算機應用，2006.26(7):1690－1692.

［10］ Jensen F，Jensen F V，Dittmer S L.From influence diagrams to junction trees［C］//Proceedings of the Tenth international conference on Uncertainty in artificial intelligence.Morgan Kaufmann Publishers Inc.，1994:367 －373.

［11］ Shmulevich I，Kauffman S A.Activities and sensitivities in Boolean network models［J］.Physical Review Letters，2004，93(4):048701.

［12］ Darwiche A.A differential approach to inference in Bayesian networks［J］.Journal of the ACM(JACM)，2003，50(3):280－305.

［13］ Van den Broeck G，Darwiche A.On the complexity and approximation of binary evidence in lifted inference［C］//Advances in Neural Information Processing Systems.［S.l.］:［s.n.］，2013:2868 －2876.

［14］俞奎，王浩，姚宏亮，等.并行的貝葉斯網(wǎng)絡參數(shù)學習算法［J］.小型微型計算機系統(tǒng)，2007，28(11):1972 －1975.

［15］王艷，郭軍.基于人工魚群算法的貝葉斯網(wǎng)絡參數(shù)學習方法［J］.計算機仿，2011，29(1):185 －188.

［16］史志富，張安.貝葉斯網(wǎng)絡理論及其在軍事系統(tǒng)中的應用［M］.北京:國防工業(yè)出版社，2012:83－97.

(責任編輯蒲 東)