Bayes評分與BIC評分對簡單Bayes網絡結構學習結果復雜度的影響

劉曉亮

摘要：在基于評分-搜索的Bayes網絡結構學習算法中，評分函數的選取對學習的結果具有關鍵影響。文章利用隨機給定的觀測數據，采用Bayes評分函數和BIC評分函數，對一些節點數較少的Bayes網絡進行窮舉式結構學習，并對學習結果的復雜度進行了測算和分析。仿真實驗表明，在相同的觀測樣本下，采用BIC評分函數將得到比采用Bayes評分函數更簡單的Bayes網絡。

關鍵詞：Bayes網絡；網絡結構；學習結果；復雜度；Bayes評分；BIC評分 文獻標識碼：A

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

Bayes網絡可以用有向圖的形式形象地表示出考慮的對象間的概率依存關系。與傳統數據挖掘方法相比，它具有理論基礎牢固、推理簡單準確，且可以在丟失數據的不完備信息下進行推理等諸多優勢，因此，基于Bayes網絡的數據挖掘算法在通信編碼、圖像處理、生物醫學工程等方面都具有相當廣泛的應用。

由于Bayes網絡的廣泛應用，自然希望能夠根據現有的先驗知識和觀測數據自動訓練出對象間的Bayes網絡，這就是Bayes網絡的學習問題。這一問題可分為兩類：參數學習和結構學習。所謂參數學習，就是在已知Bayes網絡的結構（即所考慮對象間的條件獨立性質）后，利用觀測數據估計出個節點處的相應參數（即為已知該節點父親節點時該節點的概率分布函數）；結構學習指的是在考慮變量的相互關系未知的情況下，利用觀測數據對它們之間的關系進行估計，從而訓練出相應的Bayes網絡結構。顯然，結構學習是比參數學習更困難、更有挑戰性的任務。

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

為了研究評分函數對于學習結果的影響，必須排除搜索算法可能造成的干擾。由于隨著節點數的增加，全部可能的Bayes網絡總數將以超指數的速度增長（見表1），因此對于節點數較多的情況，窮舉搜索是不可能的。考慮到為了精確得到學習結果平均復雜度而需要進行的試驗次數，本文中只對節點數為2、3、4的情況進行研究。

1 Bayes評分和BIC評分的原理

在基于評分-搜索的結構學習算法中，評分函數是用來衡量各Bayes網絡對數據匹配程度的指標，其自變量為某Bayes網絡結構，函數值越大（小），則該Bayes結構對數據匹配得越好。在定義評分函數時，往往考慮兩個因素：模型匹配數據的精確程度和模型的復雜度。學習算法總是傾向于簡單卻精確匹配數據的Bayes網絡結構。

目前廣泛使用的評分函數主要有Bayes評分和BIC評分，下面分別介紹其原理：

1.1 Bayes評分

為了完全確定一個Bayes網絡，僅僅知道其結構是不夠的，還應當知道決定該結構下各變量條件概率的參數。圖1所示的4節點Bayes網絡，假設各節點均為布爾變量，則需要確定的自由參數共有

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個。

在Bayes評分函數的定義過程中，假設所有的自由參數組成的參數向量為Θ，并記觀測到的數據序列為X，則結構S的Bayes評分定義為在Θ滿足在參數空間中均勻分布的條件下觀測到X的后驗概率的對數值。即：

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

式中：n為節點總數為節點的父親節點集合；為滿足節點的父親節點處于狀態j（共種狀態）且的觀測樣本總數；為滿足節點的父親節點處于狀態j且的觀測樣本總數，。

1.2 BIC評分

Bayes評分假設結構確定時自由參數在參數空間中滿足均勻分布，這一條件實際上隱含了對結構復雜度的限制。因為復雜的結構其參數空間維數一般較大，因此使得觀測數據的后驗概率較大的參數在整個參數空間中所占比重自然較小，這樣平均后的結果會降低該結構的Bayes評分值。另一種常用的評分函數——BIC評分則把對結構精確性和復雜性評估分為兩項。假設各參數定義與上節相同，則結構S的BIC評分定義為：

式中：d為自由參數個數（圖1中d=7）；N為觀測變量總數。上式中第一項為針對模型精確性的評估，而第二項是針對模型復雜度的懲罰。

假設所有觀測值相互獨立，且所有變量均為布爾取值，則結構的BIC評分函數可以簡化成：

2 實驗設計

下面通過MATLAB仿真實驗研究兩種評分方法對于學習結果復雜度的影響。仿真實驗涉及的Bayes網絡節點數僅限于2、3、4，觀測樣本數目限于5～50。

對所有節點數i，觀測樣本總數j，則每個觀測樣本可能出現的所有狀態數為。隨機生成觀測數據矩陣A。該矩陣為N行列，其中N為試驗次數，實際設N=1000，每行為一次試驗的數據樣本，該行每個元素分別代表本次實驗中狀態j的出現次數[如A（k，1）為第k次實驗中所有變量均為0的次數，A（k，）為第k次實驗中所有變量均為1的次數]。有。

用MATLAB編寫結構識別程序，其中為了避免搜索算法的影響，采用窮舉法搜索，并采用相應評分最高的Bayes網絡作為學習結果，用該網絡自由參數個數作為其復雜度。對每組（i，j）所得到的1000個復雜度取平均作為節點數為i，觀測樣本數為j時的平均學習復雜度和。對每個i做出兩種評估函數關于j的曲線并加以比較，從而得到評分函數和學習結果平均復雜度的關系。

3 實驗結果和初步分析

節點數i=2、3、4時的仿真結果分別如圖2、圖3、圖4所示：

由圖2、圖3、圖4可以得到以下結論：（1）在樣本數較多的情況下，隨著樣本數的增多，學習結果的復雜度也會提高；（2）在同樣的觀測條件下，BIC評分的學習結果比Bayes評分的學習結果更為簡單，且隨著節點數的增加，這種復雜度上的差異會越來越大；（3）隨著樣本數的增加，BIC評分訓練結果復雜度的增加幅度要慢于Bayes評分。

綜上所述，可以發現，BIC評分相比于Bayes評分而言，更傾向于選用簡單的網絡。

4 結語

本文對基于評分-搜索的Bayes網絡結構學習算法的兩種主流評分函數——Bayes評分和BIC評分對于學習結果復雜度的影響進行了分析。仿真結果表明，BIC評分在精確性和簡單性的權衡中更傾向于接受簡單的Bayes網絡。這一結論說明：在運算資源有限且對訓練精度要求不高的應用環境中，BIC評分是比Bayes評分更優秀的評分原則。

參考文獻

[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.

（責任編輯：周 瓊）