吳永廣，周興旺

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

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

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

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

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

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

2.1 布爾型網(wǎng)絡(luò)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

將數(shù)據(jù)集合D劃分為不同的證據(jù)集合，按照證據(jù)變量取值是否相同進(jìn)行分類，D=(e1，e2，e3，…en)。連接樹分解后的貝葉斯網(wǎng)絡(luò)以節(jié)點(diǎn)簇和分割集為單元進(jìn)行參數(shù)學(xué)習(xí)。通過比較網(wǎng)絡(luò)示意圖和連接樹，可以發(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)絡(luò)

圖3 連接樹

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

由上式可知

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

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

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

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

3 結(jié)論

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

［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］ 黃世強(qiáng)，高曉光，任佳.DDBN的無人機(jī)決策推理模型參數(shù)學(xué)習(xí)［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)絡(luò)參數(shù)學(xué)習(xí)算法［J］.計(jì)算機(jī)應(yīng)用，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)絡(luò)參數(shù)學(xué)習(xí)算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2007，28(11):1972 －1975.

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

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

(責(zé)任編輯蒲 東)