趙文強(qiáng) 趙 熙 劉 瀚

（武漢市武昌區(qū)長虹橋37-1號 武漢 430064）

基于新型二進(jìn)制自適應(yīng)差分演化算法的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)?

趙文強(qiáng) 趙 熙 劉 瀚

（武漢市武昌區(qū)長虹橋37-1號 武漢 430064）

貝葉斯網(wǎng)絡(luò)是處理不確定的專門知識和推理的最流行的方法，并廣泛應(yīng)用于大量研究領(lǐng)域。貝葉斯網(wǎng)絡(luò)學(xué)習(xí)的主要策略是利用統(tǒng)計評分來選擇最優(yōu)網(wǎng)絡(luò)的候選者。論文提出了基于新型二進(jìn)制自適應(yīng)差分演化算法的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)（BDENBAL），該方法采用一種自適應(yīng)的0∕1矩陣作為比例因子，并通過交叉和變異算子來實現(xiàn)貝葉斯網(wǎng)絡(luò)的學(xué)習(xí)過程中的信息交換。然后根據(jù)貝葉斯信息標(biāo)準(zhǔn)（BIC）評分從網(wǎng)絡(luò)空間中選擇貝葉斯網(wǎng)絡(luò)候選者。實驗結(jié)果證明本文提出的方法具有優(yōu)良的性能。

貝葉斯網(wǎng)絡(luò)；差分演化；貝葉斯信息標(biāo)準(zhǔn)

1 引言

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

目前，有兩種策略被應(yīng)用于貝葉斯網(wǎng)絡(luò)學(xué)習(xí)中：一、通過評估網(wǎng)絡(luò)節(jié)點間的假定獨立關(guān)系來構(gòu)建貝葉斯網(wǎng)絡(luò)［3］；二、利用統(tǒng)計評分從網(wǎng)絡(luò)模型空間中選擇典型的候選者。最流行的評分函數(shù)包括CH評分［4］、BIC評分［5］、MDL評分［6］、AIC評分［7］等。

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

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

本文提出了一種用于貝葉斯網(wǎng)絡(luò)學(xué)習(xí)的新型二進(jìn)制自適應(yīng)差分演化算法（BDENBAL）。通過使用交叉算子和變異算子，BDENBAL算法實現(xiàn)了貝葉斯網(wǎng)絡(luò)中的信息交換?；贐IC評分標(biāo)準(zhǔn)，BDENBAL算法從網(wǎng)絡(luò)模型空間中選出了最優(yōu)的典型候選者。

2 背景

2.1 編碼方案

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

2.2 適應(yīng)度函數(shù)

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

上述公式中，D是數(shù)據(jù)集合，s是貝葉斯結(jié)構(gòu)，α*是貝葉斯參數(shù)α的最大似然估計值，M是樣本數(shù)量。

本文中，BIC評分被選作二進(jìn)制差分演化貝葉斯網(wǎng)絡(luò)學(xué)習(xí)的適應(yīng)度函數(shù)。在貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的過程中，每個網(wǎng)絡(luò)的候選者對應(yīng)一個BIC評分，學(xué)習(xí)結(jié)果將會是該網(wǎng)絡(luò)的BIC最大得分。

2.3 循環(huán)規(guī)避

本文中，貝葉斯網(wǎng)絡(luò)矩陣被選作判斷矩陣。貝葉斯網(wǎng)絡(luò)的回路可根據(jù)所有對角線元素之和來檢測。如果貝葉斯網(wǎng)絡(luò)中存在一個循環(huán)，則總和將不為0，且有循環(huán)的貝葉斯網(wǎng)絡(luò)應(yīng)該被丟棄。

3 算法

本文提出的算法包括更新貝葉斯參數(shù)和在更新后的貝葉斯網(wǎng)絡(luò)的基礎(chǔ)上對其進(jìn)行選擇。通過變異算子和交叉算子來實現(xiàn)學(xué)習(xí)過程中的貝葉斯網(wǎng)絡(luò)信息交換。在模型的選擇方面，通過使用BIC評分來達(dá)到貪婪策略的實現(xiàn)。

3.1 變異操作

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

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

上述公式中，⊕代表異或運(yùn)算；?代表與運(yùn)算加上或運(yùn)算。

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

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

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

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

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

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

3.2 選擇操作

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

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

3.3 BDENBAL學(xué)習(xí)算法

在BDENBAL算法中，變量Tmp被設(shè)計用來緩沖交叉操作生成的貝葉斯網(wǎng)絡(luò)，變量p用來緩沖子代貝葉斯網(wǎng)絡(luò)。BDENBAL學(xué)習(xí)算法的具體步驟如下：

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

4 實驗結(jié)果

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

本文采用平均對數(shù)損失（LOGLOSS）和適應(yīng)度函數(shù)（BIC）作為性能指標(biāo)。平均對數(shù)損失可以通過如下公式計算：

表1 實驗參數(shù)

1）在100個訓(xùn)練實例上的不同算法的性能比較

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

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

圖1 節(jié)點數(shù)為4時，LOGLOSS值隨不同PMV的變化

圖2 節(jié)點數(shù)為10時，LOGLOSS值隨不同PMV的變化

圖3 節(jié)點數(shù)為32時，LOGLOSS值隨不同PMV的變化

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

圖4 節(jié)點數(shù)為4時，BIC評分的變化

2）結(jié)果形式發(fā)表文獻(xiàn)的性能比較

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

圖7 200個訓(xùn)練實例上的性能比較

圖8 400個訓(xùn)練實例上的性能比較

5 結(jié)語

基于評分的模型選擇算法是貝葉斯網(wǎng)絡(luò)學(xué)習(xí)最主要的策略之一。本文提出了基于新型二進(jìn)制自適應(yīng)差分演化算法（BDENBAL）的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)，BDENBAL算法通過交叉和變異算子來實現(xiàn)貝葉斯網(wǎng)絡(luò)的學(xué)習(xí)過程中的信息交換。此外，BDENBAL算法根據(jù)貝葉斯信息標(biāo)準(zhǔn)（BIC）評分從網(wǎng)絡(luò)空間中選擇貝葉斯網(wǎng)絡(luò)候選者。為了檢驗BDENBAL算法的性能，我們在Matlab環(huán)境下進(jìn)行模擬仿真，并將不同情況下BDENBAL算法、AMS-EM算法、EGA算法和SEM算法的性能進(jìn)行比較和分析，實驗結(jié)果證明BDENBAL算法擁有更加優(yōu)良的性能。

［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日

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