Bayes評(píng)分與BIC評(píng)分對(duì)簡(jiǎn)單Bayes網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)結(jié)果復(fù)雜度的影響

劉曉亮

摘要：在基于評(píng)分-搜索的Bayes網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法中，評(píng)分函數(shù)的選取對(duì)學(xué)習(xí)的結(jié)果具有關(guān)鍵影響。文章利用隨機(jī)給定的觀測(cè)數(shù)據(jù)，采用Bayes評(píng)分函數(shù)和BIC評(píng)分函數(shù)，對(duì)一些節(jié)點(diǎn)數(shù)較少的Bayes網(wǎng)絡(luò)進(jìn)行窮舉式結(jié)構(gòu)學(xué)習(xí)，并對(duì)學(xué)習(xí)結(jié)果的復(fù)雜度進(jìn)行了測(cè)算和分析。仿真實(shí)驗(yàn)表明，在相同的觀測(cè)樣本下，采用BIC評(píng)分函數(shù)將得到比采用Bayes評(píng)分函數(shù)更簡(jiǎn)單的Bayes網(wǎng)絡(luò)。

關(guān)鍵詞：Bayes網(wǎng)絡(luò)；網(wǎng)絡(luò)結(jié)構(gòu)；學(xué)習(xí)結(jié)果；復(fù)雜度；Bayes評(píng)分；BIC評(píng)分 文獻(xiàn)標(biāo)識(shí)碼：A

中圖分類號(hào)：TP181 文章編號(hào)：1009-2374（2016）18-0188-02 DOI：10.13535/j.cnki.11-4406/n.2016.18.094

Bayes網(wǎng)絡(luò)可以用有向圖的形式形象地表示出考慮的對(duì)象間的概率依存關(guān)系。與傳統(tǒng)數(shù)據(jù)挖掘方法相比，它具有理論基礎(chǔ)牢固、推理簡(jiǎn)單準(zhǔn)確，且可以在丟失數(shù)據(jù)的不完備信息下進(jìn)行推理等諸多優(yōu)勢(shì)，因此，基于Bayes網(wǎng)絡(luò)的數(shù)據(jù)挖掘算法在通信編碼、圖像處理、生物醫(yī)學(xué)工程等方面都具有相當(dāng)廣泛的應(yīng)用。

由于Bayes網(wǎng)絡(luò)的廣泛應(yīng)用，自然希望能夠根據(jù)現(xiàn)有的先驗(yàn)知識(shí)和觀測(cè)數(shù)據(jù)自動(dòng)訓(xùn)練出對(duì)象間的Bayes網(wǎng)絡(luò)，這就是Bayes網(wǎng)絡(luò)的學(xué)習(xí)問題。這一問題可分為兩類：參數(shù)學(xué)習(xí)和結(jié)構(gòu)學(xué)習(xí)。所謂參數(shù)學(xué)習(xí)，就是在已知Bayes網(wǎng)絡(luò)的結(jié)構(gòu)（即所考慮對(duì)象間的條件獨(dú)立性質(zhì)）后，利用觀測(cè)數(shù)據(jù)估計(jì)出個(gè)節(jié)點(diǎn)處的相應(yīng)參數(shù)（即為已知該節(jié)點(diǎn)父親節(jié)點(diǎn)時(shí)該節(jié)點(diǎn)的概率分布函數(shù)）；結(jié)構(gòu)學(xué)習(xí)指的是在考慮變量的相互關(guān)系未知的情況下，利用觀測(cè)數(shù)據(jù)對(duì)它們之間的關(guān)系進(jìn)行估計(jì)，從而訓(xùn)練出相應(yīng)的Bayes網(wǎng)絡(luò)結(jié)構(gòu)。顯然，結(jié)構(gòu)學(xué)習(xí)是比參數(shù)學(xué)習(xí)更困難、更有挑戰(zhàn)性的任務(wù)。

目前有關(guān)結(jié)構(gòu)學(xué)習(xí)的算法研究主要分為兩類：一類是基于條件獨(dú)立性檢測(cè)的算法。這類算法主要通過檢查變量間鑒別信息或交叉熵等方法來判斷變量間的條件獨(dú)立性，再建立滿足這些條件獨(dú)立性的Bayes網(wǎng)絡(luò)。該方法的計(jì)算量較小，在節(jié)點(diǎn)數(shù)不多的情況下準(zhǔn)確度也較高，但在節(jié)點(diǎn)數(shù)較多的情況下，對(duì)條件獨(dú)立性的不準(zhǔn)確判斷造成的誤差會(huì)產(chǎn)生連鎖反應(yīng)，導(dǎo)致學(xué)習(xí)結(jié)果的準(zhǔn)確性大大降低。第二類算法是基于評(píng)分-搜索的結(jié)構(gòu)學(xué)習(xí)算法。這類算法首先確定一個(gè)能夠反映Bayes網(wǎng)絡(luò)準(zhǔn)確度的評(píng)分函數(shù)，然后在滿足節(jié)點(diǎn)數(shù)要求的全體Bayes網(wǎng)絡(luò)中采用啟發(fā)式搜索等辦法，找出使得評(píng)分函數(shù)盡量大（或?。┑木W(wǎng)絡(luò)作為學(xué)習(xí)結(jié)果。由于這一問題是NP問題，在節(jié)點(diǎn)數(shù)較大的情況下無法求出最優(yōu)解，所以搜索算法一般為梯度下降、蒙特卡洛等次優(yōu)算法?；谠u(píng)分-搜索的結(jié)構(gòu)學(xué)習(xí)算法因其出色的準(zhǔn)確性和對(duì)觀測(cè)數(shù)據(jù)的魯棒性而成為結(jié)構(gòu)識(shí)別算法中的主流。在基于評(píng)分-搜索的結(jié)構(gòu)學(xué)習(xí)算法中，評(píng)分函數(shù)的選取對(duì)于學(xué)習(xí)結(jié)果的性能是具有關(guān)鍵性影響的。好的評(píng)分函數(shù)可以在模型的準(zhǔn)確性與復(fù)雜性之間做出合適的權(quán)衡，對(duì)之后將學(xué)習(xí)結(jié)果用于推理時(shí)的效率會(huì)有很大提高，目前被廣泛采用的評(píng)分標(biāo)準(zhǔn)有Bayes評(píng)分、BIC評(píng)分等。本文的目的即為研究這兩種評(píng)分對(duì)于學(xué)習(xí)結(jié)果復(fù)雜性的影響。本文以下的部分將這樣安排：第1部分介紹Bayes評(píng)分和BIC評(píng)分的原理；第2部分介紹仿真實(shí)驗(yàn)的設(shè)計(jì)；第3部分對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行初步分析；第4部分給出結(jié)論。

為了研究評(píng)分函數(shù)對(duì)于學(xué)習(xí)結(jié)果的影響，必須排除搜索算法可能造成的干擾。由于隨著節(jié)點(diǎn)數(shù)的增加，全部可能的Bayes網(wǎng)絡(luò)總數(shù)將以超指數(shù)的速度增長(zhǎng)（見表1），因此對(duì)于節(jié)點(diǎn)數(shù)較多的情況，窮舉搜索是不可能的?？紤]到為了精確得到學(xué)習(xí)結(jié)果平均復(fù)雜度而需要進(jìn)行的試驗(yàn)次數(shù)，本文中只對(duì)節(jié)點(diǎn)數(shù)為2、3、4的情況進(jìn)行研究。

1 Bayes評(píng)分和BIC評(píng)分的原理

在基于評(píng)分-搜索的結(jié)構(gòu)學(xué)習(xí)算法中，評(píng)分函數(shù)是用來衡量各Bayes網(wǎng)絡(luò)對(duì)數(shù)據(jù)匹配程度的指標(biāo)，其自變量為某Bayes網(wǎng)絡(luò)結(jié)構(gòu)，函數(shù)值越大（?。?，則該Bayes結(jié)構(gòu)對(duì)數(shù)據(jù)匹配得越好。在定義評(píng)分函數(shù)時(shí)，往往考慮兩個(gè)因素：模型匹配數(shù)據(jù)的精確程度和模型的復(fù)雜度。學(xué)習(xí)算法總是傾向于簡(jiǎn)單卻精確匹配數(shù)據(jù)的Bayes網(wǎng)絡(luò)結(jié)構(gòu)。

目前廣泛使用的評(píng)分函數(shù)主要有Bayes評(píng)分和BIC評(píng)分，下面分別介紹其原理：

1.1 Bayes評(píng)分

為了完全確定一個(gè)Bayes網(wǎng)絡(luò)，僅僅知道其結(jié)構(gòu)是不夠的，還應(yīng)當(dāng)知道決定該結(jié)構(gòu)下各變量條件概率的參數(shù)。圖1所示的4節(jié)點(diǎn)Bayes網(wǎng)絡(luò)，假設(shè)各節(jié)點(diǎn)均為布爾變量，則需要確定的自由參數(shù)共有

p（A=0），p（B=0|A=0），p（B=0|A=1），p（C=0|A=0），

p（C=0|A=1），p（D=0|C=0），p（D=0|C=1）共

7個(gè)。

在Bayes評(píng)分函數(shù)的定義過程中，假設(shè)所有的自由參數(shù)組成的參數(shù)向量為Θ，并記觀測(cè)到的數(shù)據(jù)序列為X，則結(jié)構(gòu)S的Bayes評(píng)分定義為在Θ滿足在參數(shù)空間中均勻分布的條件下觀測(cè)到X的后驗(yàn)概率的對(duì)數(shù)值。即：

假設(shè)所有觀測(cè)值相互獨(dú)立，且所有變量均為布爾取值，則由積分公式可以推出：

式中：n為節(jié)點(diǎn)總數(shù)為節(jié)點(diǎn)的父親節(jié)點(diǎn)集合；為滿足節(jié)點(diǎn)的父親節(jié)點(diǎn)處于狀態(tài)j（共種狀態(tài)）且的觀測(cè)樣本總數(shù)；為滿足節(jié)點(diǎn)的父親節(jié)點(diǎn)處于狀態(tài)j且的觀測(cè)樣本總數(shù)，。

1.2 BIC評(píng)分

Bayes評(píng)分假設(shè)結(jié)構(gòu)確定時(shí)自由參數(shù)在參數(shù)空間中滿足均勻分布，這一條件實(shí)際上隱含了對(duì)結(jié)構(gòu)復(fù)雜度的限制。因?yàn)閺?fù)雜的結(jié)構(gòu)其參數(shù)空間維數(shù)一般較大，因此使得觀測(cè)數(shù)據(jù)的后驗(yàn)概率較大的參數(shù)在整個(gè)參數(shù)空間中所占比重自然較小，這樣平均后的結(jié)果會(huì)降低該結(jié)構(gòu)的Bayes評(píng)分值。另一種常用的評(píng)分函數(shù)——BIC評(píng)分則把對(duì)結(jié)構(gòu)精確性和復(fù)雜性評(píng)估分為兩項(xiàng)。假設(shè)各參數(shù)定義與上節(jié)相同，則結(jié)構(gòu)S的BIC評(píng)分定義為：

式中：d為自由參數(shù)個(gè)數(shù)（圖1中d=7）；N為觀測(cè)變量總數(shù)。上式中第一項(xiàng)為針對(duì)模型精確性的評(píng)估，而第二項(xiàng)是針對(duì)模型復(fù)雜度的懲罰。

假設(shè)所有觀測(cè)值相互獨(dú)立，且所有變量均為布爾取值，則結(jié)構(gòu)的BIC評(píng)分函數(shù)可以簡(jiǎn)化成：

2 實(shí)驗(yàn)設(shè)計(jì)

下面通過MATLAB仿真實(shí)驗(yàn)研究?jī)煞N評(píng)分方法對(duì)于學(xué)習(xí)結(jié)果復(fù)雜度的影響。仿真實(shí)驗(yàn)涉及的Bayes網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)僅限于2、3、4，觀測(cè)樣本數(shù)目限于5～50。

對(duì)所有節(jié)點(diǎn)數(shù)i，觀測(cè)樣本總數(shù)j，則每個(gè)觀測(cè)樣本可能出現(xiàn)的所有狀態(tài)數(shù)為。隨機(jī)生成觀測(cè)數(shù)據(jù)矩陣A。該矩陣為N行列，其中N為試驗(yàn)次數(shù)，實(shí)際設(shè)N=1000，每行為一次試驗(yàn)的數(shù)據(jù)樣本，該行每個(gè)元素分別代表本次實(shí)驗(yàn)中狀態(tài)j的出現(xiàn)次數(shù)[如A（k，1）為第k次實(shí)驗(yàn)中所有變量均為0的次數(shù)，A（k，）為第k次實(shí)驗(yàn)中所有變量均為1的次數(shù)]。有。

用MATLAB編寫結(jié)構(gòu)識(shí)別程序，其中為了避免搜索算法的影響，采用窮舉法搜索，并采用相應(yīng)評(píng)分最高的Bayes網(wǎng)絡(luò)作為學(xué)習(xí)結(jié)果，用該網(wǎng)絡(luò)自由參數(shù)個(gè)數(shù)作為其復(fù)雜度。對(duì)每組（i，j）所得到的1000個(gè)復(fù)雜度取平均作為節(jié)點(diǎn)數(shù)為i，觀測(cè)樣本數(shù)為j時(shí)的平均學(xué)習(xí)復(fù)雜度和。對(duì)每個(gè)i做出兩種評(píng)估函數(shù)關(guān)于j的曲線并加以比較，從而得到評(píng)分函數(shù)和學(xué)習(xí)結(jié)果平均復(fù)雜度的關(guān)系。

3 實(shí)驗(yàn)結(jié)果和初步分析

節(jié)點(diǎn)數(shù)i=2、3、4時(shí)的仿真結(jié)果分別如圖2、圖3、圖4所示：

由圖2、圖3、圖4可以得到以下結(jié)論：（1）在樣本數(shù)較多的情況下，隨著樣本數(shù)的增多，學(xué)習(xí)結(jié)果的復(fù)雜度也會(huì)提高；（2）在同樣的觀測(cè)條件下，BIC評(píng)分的學(xué)習(xí)結(jié)果比Bayes評(píng)分的學(xué)習(xí)結(jié)果更為簡(jiǎn)單，且隨著節(jié)點(diǎn)數(shù)的增加，這種復(fù)雜度上的差異會(huì)越來越大；（3）隨著樣本數(shù)的增加，BIC評(píng)分訓(xùn)練結(jié)果復(fù)雜度的增加幅度要慢于Bayes評(píng)分。

綜上所述，可以發(fā)現(xiàn)，BIC評(píng)分相比于Bayes評(píng)分而言，更傾向于選用簡(jiǎn)單的網(wǎng)絡(luò)。

4 結(jié)語

本文對(duì)基于評(píng)分-搜索的Bayes網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法的兩種主流評(píng)分函數(shù)——Bayes評(píng)分和BIC評(píng)分對(duì)于學(xué)習(xí)結(jié)果復(fù)雜度的影響進(jìn)行了分析。仿真結(jié)果表明，BIC評(píng)分在精確性和簡(jiǎn)單性的權(quán)衡中更傾向于接受簡(jiǎn)單的Bayes網(wǎng)絡(luò)。這一結(jié)論說明：在運(yùn)算資源有限且對(duì)訓(xùn)練精度要求不高的應(yīng)用環(huán)境中，BIC評(píng)分是比Bayes評(píng)分更優(yōu)秀的評(píng)分原則。

參考文獻(xiàn)

[1] N.Friedman.Learning belief networks in the presence of missing values and hidden variables[J].machine learning international workshop then conference，1997.

[2] N.Friedman.The Bayesian EM structural Algorithm[J].Proc.UAI，1998.

[3] JM Pena，JA Lozano，P Larranaga.An improved Bayesian structural EM algorithm for learning Bayesian networks for clustering[J].Pattern Recognition Letters，2000.

[4] D Heckerman.A tutorial on learning with Bayesian networks[J].Learning in Graphical Models，1998.

[5] GF Cooper E Herskovits.A Bayesian method for the induction of probabilistic networks from data[J].Machine Learning，1992.

（責(zé)任編輯：周 瓊）