布爾型貝葉斯網絡參數學習

吳永廣，周興旺

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

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

1 參數學習研究現狀

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

2 布爾型貝葉斯參數學習算法

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

2.1 布爾型網絡

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

定義一個布爾型函數

證據變量λx:對于貝葉斯網絡參數X，變量λx代表事件發生的狀態，為布爾型變量。引入證據變量，使證據事件同變量的狀態結合，能夠很好地通過線性函數表達式進行分析處理。

參數變量θx|u:對于任意的父節點u及其子節點x，以θx|u表示網絡參數在父節點狀態發生時的條件概率。當父節點不存在時，θx|u表示節點概率值。

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

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

圖1 布爾型網絡概率表

對函數作偏微分計算

證據變量的微分特性［12］

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

這樣，變量的概率同變量的偏微分成了互相轉化的函數關系，對于計算節點聯合概率，分析變量概率特性有重要作用，同時也使復雜數據處理過程變得簡單化。

參數變量的微分特性，描述了節點變量的父子節點和證據的聯合概率同參數變量偏微分值的等價關系，是離散變量的另一重要性質［12］

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

2.2 基于連接樹的網絡分解

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

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

通過引入勢(Potentials)函數理論［16］可以證明連接樹分解算法的合理性。一組變量X上的勢定義為一個函數，每個變量對應的值x稱為它的實例。勢函數能夠將實例映射為一個非零實數，用φx表示。勢可以構成向量或矩陣，也可以實現邊緣化并進行乘法算法:

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

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

根據勢函數理論，節點簇的勢可用φx表示，分割集的勢可用φy表示。容易證明貝葉斯網絡的聯合概率分布可以表示為［12］

2.3 基于最大似然估計參數算法

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

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

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

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

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

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

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

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

圖2 貝葉斯網絡

圖3 連接樹

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

由上式可知

結合公式最優化wP(x，u，e)

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

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

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

3 結論

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

［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的無人機決策推理模型參數學習［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］ 張少中，章錦文，張志勇，等.面向大規模數據集的貝葉斯網絡參數學習算法［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］俞奎，王浩，姚宏亮，等.并行的貝葉斯網絡參數學習算法［J］.小型微型計算機系統，2007，28(11):1972 －1975.

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

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

(責任編輯蒲 東)