基于新型二進制自適應差分演化算法的貝葉斯網絡學習?

趙文強 趙 熙 劉 瀚

（武漢市武昌區長虹橋37-1號 武漢 430064）

基于新型二進制自適應差分演化算法的貝葉斯網絡學習?

趙文強 趙 熙 劉 瀚

（武漢市武昌區長虹橋37-1號 武漢 430064）

貝葉斯網絡是處理不確定的專門知識和推理的最流行的方法，并廣泛應用于大量研究領域。貝葉斯網絡學習的主要策略是利用統計評分來選擇最優網絡的候選者。論文提出了基于新型二進制自適應差分演化算法的貝葉斯網絡學習（BDENBAL），該方法采用一種自適應的0∕1矩陣作為比例因子，并通過交叉和變異算子來實現貝葉斯網絡的學習過程中的信息交換。然后根據貝葉斯信息標準（BIC）評分從網絡空間中選擇貝葉斯網絡候選者。實驗結果證明本文提出的方法具有優良的性能。

貝葉斯網絡；差分演化；貝葉斯信息標準

1 引言

隨著人工智能的發展，Pearl在20世紀80年代提出了貝葉斯網絡。如今，貝葉斯網絡是處理不確定的專門知識和推理的最流行的方法［1］。由于其強大的概率推理功能，貝葉斯網絡被應用于大量研究領域，例如：專家系統、醫療系統、制造系統、語音識別、數據挖掘、經濟活動分析、軍事對抗和預測［2］。

目前，有兩種策略被應用于貝葉斯網絡學習中：一、通過評估網絡節點間的假定獨立關系來構建貝葉斯網絡［3］；二、利用統計評分從網絡模型空間中選擇典型的候選者。最流行的評分函數包括CH評分［4］、BIC評分［5］、MDL評分［6］、AIC評分［7］等。

由于學習貝葉斯網絡是個NP難的問題［8］，基于啟發式搜索（例如：隨機局部搜索、遺傳算法、演化算法）的學習算法通常能夠找到近似最優貝葉斯網絡［9］。AMS-EM 學習算法采用確定性搜索［10］。AMS-EM的初始網絡選擇取決于先驗概率。選擇不同的初始網絡結構可能會造成收斂結果模型的分布區不同。因此，AMS-EM可以發現局部最優的網絡結構。EGA［11］是一個基于遺傳算法的隨機搜索算法。和AMS-EM相比，EGA能夠找到最優的網絡結構，因為它僅編碼網絡結構并通過數學期望轉換不完全數據。Friedman將馬爾可夫鏈蒙特卡爾理論（MCMC）應用到不完全數據的貝葉斯網絡學習中得到EM-MCMC算法［12］，同時還提出結構化的EM算法（SEM）。SEM算法將EM算法應用到網絡參數優化，并將結構搜索方案應用到模型的選擇。

標準差分演化算法（DE）在連續值搜索空間中具有更快的搜索速度和更高的精確度。DE算法的演化算子會使該算法很難直接用于離散空間，為了解決此問題，Engelbrecht提出二進制差分演化算法（BDE）［13］，通過使用三角函數實現了連續空間到二元空間的轉換，標準測試函數已證明BDE算法的搜索準確率要高于二進制粒子群優化算法。此外，他和Han提出了一種使用邏輯操作代替算術計算的新算法來提高BDE算法在二元空間中的表現。

本文提出了一種用于貝葉斯網絡學習的新型二進制自適應差分演化算法（BDENBAL）。通過使用交叉算子和變異算子，BDENBAL算法實現了貝葉斯網絡中的信息交換。基于BIC評分標準，BDENBAL算法從網絡模型空間中選出了最優的典型候選者。

2 背景

2.1 編碼方案

貝葉斯網絡表示出變量之間的條件概率與有向無環圖（DAG）。一個有向無環圖可以表示為（A，B），其中A代表一組頂點，B代表一組邊。一個貝葉斯網絡矩陣X（i，j）（i=1，…N，j=1，…N）可以由當前的DAG構成，如圖1所示。所有矩陣中的元素為0或1。如果點vi和點vj之間存在一條有向邊bij(vi→ vj)，X（i，j）等于1，否則為0。因此，演化算法的熱色體可以被構造為(X1,…Xi,…Xd)，其中每一個遺傳因子都是一個貝葉斯網絡矩陣。

2.2 適應度函數

作為選擇模型中的一種典型評分函數，貝葉斯信息評分標準是邊緣似然函數的大樣本近似［2］。與拉普拉斯近似一致，我們可以獲得大樣本近似G（s|D）來獲得作為后驗概率對數的BIC評分函數。logG(s|D)可以近似為

上述公式中，D是數據集合，s是貝葉斯結構，α*是貝葉斯參數α的最大似然估計值，M是樣本數量。

本文中，BIC評分被選作二進制差分演化貝葉斯網絡學習的適應度函數。在貝葉斯網絡結構學習的過程中，每個網絡的候選者對應一個BIC評分，學習結果將會是該網絡的BIC最大得分。

2.3 循環規避

本文中，貝葉斯網絡矩陣被選作判斷矩陣。貝葉斯網絡的回路可根據所有對角線元素之和來檢測。如果貝葉斯網絡中存在一個循環，則總和將不為0，且有循環的貝葉斯網絡應該被丟棄。

3 算法

本文提出的算法包括更新貝葉斯參數和在更新后的貝葉斯網絡的基礎上對其進行選擇。通過變異算子和交叉算子來實現學習過程中的貝葉斯網絡信息交換。在模型的選擇方面，通過使用BIC評分來達到貪婪策略的實現。

3.1 變異操作

標準差分演化算法將基于浮點數的編碼機制用于編碼方案。本文提出的BDENBAL算法將一種二元矩陣替代真實數字并用于編碼方案中。各元素在各個位上的值只有1或0。此外，BDENBAL算法在標準差分演化算法中使用邏輯計算代替了算術計算。

對于某一個體Si,H;i=1,2,…,NP，如下公式推理可以得到另一個體Wi,H=(W1i,H+1,W2i,H+1,…,WDi,H+1)：

上述公式中，⊕代表異或運算；?代表與運算加上或運算。

r1，r2和r3是屬于［1，NP］的不同整數，NP代表群體大小。

Fac代表用于控制變異程度的比例因子。本文中的Fac是和貝葉斯矩陣相同的0∕1矩陣。比例因子Fac可以由如下公式得到：

上述公式中，U1是屬于區間（0，1）的小數，R1是屬于區間（0，1）的隨機數字，ε1是閾值。sizeof(DAG)是用來計算行數和列數的函數。如果R1小于 ε1，比例因子Fac將生成一個0∕1矩陣。交叉操作

一個子代的向量可以由如下公式得到：

其中，對于 vji,H+1,j∈(1,2,3,…,D)，

上述公式中，CE是相交元素，D代表個體的長度，Rb代表隨機小數。

3.2 選擇操作

BDENBAL算法在選擇典型的候選者方面提供了一種貪婪策略：

上述公式中，BIC函數與式（1）相同，如果子代向量vi,H+1的適應度值大于父代Si,H的值，下一代Si,H+1將會被vi,H+1取代。否則，Si,H+1等于Si,H。

3.3 BDENBAL學習算法

在BDENBAL算法中，變量Tmp被設計用來緩沖交叉操作生成的貝葉斯網絡，變量p用來緩沖子代貝葉斯網絡。BDENBAL學習算法的具體步驟如下：

算法1：BDENBAL算法1：變量：Tmp，p，Loop_M，Loop; ∕初始化2：Loop_M=最大代數，Loop=0;3：根據當前遺漏值生成變量e;4：while Loop_M＞＝Loop;5：隨機選擇3個個體Sr1,Sr1,Sr1; ∕個體選擇6：根據式（2）生成一個交叉元素Fac 7：當j=1時； ∕變異操作和交叉操作8：根據式（1）進行變異操作；9：根據式（3）進行交叉操作；10：if no Loop in Tmp；11：p{j}=Tmp；12：根據當前子代貝葉斯網絡和BIC評分算法，得到BIC評分。∕BIC評分13：根據式（4）進行選擇； ∕模型選擇14：Loop=Loop+1；15：End while

4 實驗結果

本文通過將SEM算法、EM-MCMC算法、AMS-EM算法、BDENBAL算法分別在MATLAB上實現的性能進行比較，評價BDENBAL算法的表現，具體實驗參數如下表所示。

本文采用平均對數損失（LOGLOSS）和適應度函數（BIC）作為性能指標。平均對數損失可以通過如下公式計算：

表1 實驗參數

1）在100個訓練實例上的不同算法的性能比較

為了評價BDENBAL算法的學習能力，我們比較了BDENBAL算法、SEM算法、EM-MCMC算法在4個節點、10個節點，和32個節點條件下的貝葉斯網絡。圖1～圖3顯示出BDENBAL算法、SEM算法、EM-MCMC算法的LOGLOSS值隨著不同百分比的缺失值（PMV）的變化。PMV在x軸上的對應值為

實驗結果顯示，所有算法的LOGLOSS值均隨著缺失值百分比的提升而呈遞減趨勢。在所有情況下，BDENBAL算法的LOGLOSS值均大于SEM算法和EM-MCMC算法；同時，BDENBAL算法的遞減程度和其他兩種算法相比較小。該實驗結果證明了和SEM算法、EM-MCMC算法相比，BDENBAL算法擁有更高的性能和預測穩定性。

圖1 節點數為4時，LOGLOSS值隨不同PMV的變化

圖2 節點數為10時，LOGLOSS值隨不同PMV的變化

圖3 節點數為32時，LOGLOSS值隨不同PMV的變化

圖4～圖6顯示出BDENBAL算法在不同代數下的適應度值變化，PMV值分別從0%～40%中選擇。實驗中由EM算法評估失蹤的隨機樣本部分，估計值會比隨機值更加適合。因此，適應度值會隨著PMV值的提高而增大。

圖4 節點數為4時，BIC評分的變化

2）結果形式發表文獻的性能比較

本文同時將BDENBAL算法和AMS-EM算法、EGA算法進行了比較。圖7和圖8顯示出三種算法分別在200、400個訓練實例樣本上的LOGLOSS值變化。實驗結果表明，在兩種訓練實例樣本上，AMS-EM算法的LOGLOSS值是最小的，而BDENBAL算法的LOGLOSS值最大。在缺失值相同的情況下，通過BDENBAL算法得到的貝葉斯網絡所反映的概率分布要更加準確。因此，BDENBAL算法擁有更強大的評估能力并能收斂到全局最優解。同時，三種算法的曲線弧度表明，在缺失值的百分比對BDENBAL算法、AMS-EM算法、EGA算法的影響程度中，BDENBAL算法受影響程度最小。

圖7 200個訓練實例上的性能比較

圖8 400個訓練實例上的性能比較

5 結語

基于評分的模型選擇算法是貝葉斯網絡學習最主要的策略之一。本文提出了基于新型二進制自適應差分演化算法（BDENBAL）的貝葉斯網絡學習，BDENBAL算法通過交叉和變異算子來實現貝葉斯網絡的學習過程中的信息交換。此外，BDENBAL算法根據貝葉斯信息標準（BIC）評分從網絡空間中選擇貝葉斯網絡候選者。為了檢驗BDENBAL算法的性能，我們在Matlab環境下進行模擬仿真，并將不同情況下BDENBAL算法、AMS-EM算法、EGA算法和SEM算法的性能進行比較和分析，實驗結果證明BDENBAL算法擁有更加優良的性能。

［1］D.Mitra，P.Muller，S.Liang，et al.A Bayesian GraphicalModel for ChIP-Seq Data on Histone Modifications［J］.Journal of the American Statistical Association，2013，108（501）：69-80.

［2］ E.Gyftodimos， PA.Flach.Hierarchical Bayesian Networks：An Approrach to Classification and Learning for Structured Data［J］.Springer Berlin Heidelberg，2004，3052：291-300.

［3］D.Heckerma.A tutorial on learning with Bayesian Networks［J］.Studies in Computational Intelligence，2008，156：33-82.

［4］J.Rissanen.Estimation of structure by minimum description length［J］.Circuits System and Signal Processing，1982，156：3-4.

［5］H.Bozdogan.Model selection and Akaike's Information Criterion（AIC）：The general theory and its analytical extensions［J］.Psychometrika，1987，52（3）：345-370.

［6］N.Dojer.Learning Bayesian Networks Does Not Have to Be NP-Hard［J］.International Symposium on MathematicalFoundationsofComputerScience，2006，4162：305-314.

［7］P.Larranaga，M.Poza and Y.Yurramendi.Structure learning of Bayesian networks by genetic algorithms：a performance analysis of control parameters［J］.IEEE Transactions on Pattern Analysisamp;Machine Intelligence，1996，18（9）：912-926.

［8］N.Friedman，G.Dan and M.Goldszmidt.Bayesian Network Classifiers［J］.MachineLearning，1997，29（2-3）：131-163.

［9］L.Dayou，W.Fei and L.Yinan.Research on genetic algorithm based Bayesian Network structure learning［J］.Journal of Computer Research and Development，2001，38（8）：916-922.

［10］C.Riggelsen.Learning parameters of Bayesian Networks from incomplete data via importance sampling［J］.International Journal of Approximate Reasoning，2006，42（1）：69-83.

［11］J.Pena，J.Lozano and P.Larranaga.An improved Bayesian structural EM algorithm for learning Bayesian networks for clustering［J］.Pattern Recognition Letters，2000，21（8）：779-786.

［12］Yu Zhiwen，Li L，Wong H S，et al.Probabilistic cluster structure ensemble［J］.Information Sciences，2014，267（5）：16-34.

［13］Sihem A，Lehocinem B，Miniaih.A Batch Adsorption of Phenol From Industrial Waste Water Using Cereal By-Products As A New Adsrbent［J］，Energy Procedia，2012，18（4）：1135-1144.

Bayesian Network Learning Based on the New Binary System Adaptive Differential Evolution Algorithm

ZHAO Wenqiang ZHAO XiLIU Han
（No.37-1 Changhong Crossroads，Wuchang District，Wuhan 430064）

The Bayesian network is the most popular way to deal with uncertain knowledge and reasoning，and widely used in plenty of research fields.The strategy of Bayesian network learning is to choose the candidate of the optimal network by using the statistical score.The Bayesian network learning is proposed based on the new binary system adaptive differential evolution algorithm（BDENBAL）.BDENBAL uses a self-adaptive 0∕1 matrix as a proportional factor，And through the cross and mutation operator to realize the information exchange in the learning process of Bayesian network.Then，according to the Bayesian Information Criterion（BIC）scoring standard，the candidate is selected from the network space.The experimental results show that the proposed method has excellent performance.

Bayesian network，differential evolution，BIC

TP301.6

10.3969∕j.issn.1672-9730.2017.10.008

Class Number TP301.6

2017年4月6日，

2017年5月27日

趙文強，男，碩士，研究方向：信號與信息處理。趙熙，男，碩士，研究方向：可靠性工程。劉瀚，男，碩士，研究方向：動力工程。