一種半監(jiān)督機器學習的EM算法改進方法

夏筱筠，張笑東，2，王 帥，2，羅金鳴，崔露露，2，趙智陽，2

1(中國科學院 沈陽計算技術(shù)研究所，沈陽 110168)2(中國科學院大學，北京 100049)3(沈陽工程學院，沈陽 110136)

1 引 言

期望最大化(Expectation Maximization，EM)算法是一種被廣泛應用于極大似然估計的迭代計算方法，用于處理大規(guī)模數(shù)據(jù)不完整問題.

EM算法實際上是一種基于梯度上升的方法，在應用于模型參數(shù)估計時能夠保證迭代之后的似然函數(shù)是遞增的，因此有一個很大的弊端就是通常只能得到一個局部最優(yōu)解.對于EM算法，國內(nèi)外學者提出了很多改進方式，比較經(jīng)典且應用比較廣泛的有PX-EM算法、ECME算法、MCEM算法.PX-EM算法利用協(xié)方差對M步的計算進行修正，通過獲取數(shù)據(jù)的額外信息達到加快收斂速度的目標，在應用上更加簡化，而且未破壞EM算法單調(diào)收斂性質(zhì).但PX-EM算法那也有其缺點，在擴充參數(shù)模型上很難找到一個通用的標準，所以它在局部最優(yōu)解問題上并沒有得到很好的優(yōu)化[1]；ECME算法對E步進行了簡化處理，由于它在極大化過程中針對的一直是實際對象，而不是實際對象的附近量，其擁有的收斂速度比EM和PX-EM算法都要大.然而，ECME算法在局部收斂的問題上依然沒有給出有效的處理方法，依然延續(xù)了EM算法所固有的性質(zhì)[2]；MCEM算法用蒙特卡羅的方法對EM算法進行優(yōu)化，對EM算法中的期望顯示表示進行了改善，從而加速了收斂速度，但由于這種方法過于靈活，在模擬容量選擇和收斂性準則的確認上很難，而且失去了EM算法的單調(diào)性，難以對其收斂特性進行估計，依然在局部最優(yōu)問題上沒有給出有效解決方案[3].

綜上所述，EM算法及其改進算法存在在局部最優(yōu)化問題上還存在著很大的不足，國內(nèi)外學者在改進方法上側(cè)重于解決其收斂速度問題，針對EM算法進入局部最優(yōu)問題還未提出有效方法.對此，本文將半監(jiān)督機器學習方法用于EM算法改進，首先在最大似然函數(shù)中加入最小二乘懲罰項，引入非負約束作為先驗信息，然后結(jié)合半監(jiān)督機器學習法，將EM算法改進方法轉(zhuǎn)化為處理最小化的問題，再采用最大似然算法求解EM問題，有效地求解了混合矩陣和高斯混合模型參數(shù)，實現(xiàn)EM算法的改進.通過實驗理論與實驗結(jié)果分析表明改進后EM算法不會陷入局部最優(yōu)，得到的結(jié)果更加可靠.

2 基于半監(jiān)督機器學習的EM算法改進分析

2.1 改進EM算法先驗信息的獲取

以先驗理論為基礎依據(jù)概率懲罰定理以及二項分布概率函數(shù)[4]，將最大似然函數(shù)表示為：

(1)

公式(1)中，αji=αj(xi)=P(y=j|xi)，yji是j×1的某一個一維向量，代表第i個觀測變量，xi=(x1,x2,…,xp)用于描述協(xié)變量.

通過計算，L對數(shù)似然函數(shù)課表示成：

(2)

對公式(2)關(guān)于j×p進行一階偏導求解，那么得分函數(shù)表示為：

(3)

對S(β)=0進行求解，從而獲取參數(shù)估計值β.

將懲罰項添加到最大似然函數(shù)中會大大減小得分函數(shù)所帶來的誤差[5]，本文添加的懲罰項為最小二乘懲罰項，公式為：

(4)

公式(4)中，p=[p1,p2,…,pi]T代表估計向量；f=[f1,f2,…,fj]T代表懲罰向量；Q(f)為懲罰項；χ代表對懲罰項的影響程度，χ值可利用實驗獲取；H為i×j系統(tǒng)概率矩陣；k代表迭代次數(shù).

利用最優(yōu)化法對上述懲罰項進行求解，并且通過OSL算法獲取迭代公式：

(5)

需要指出，Q(f)主要包含二次與非二次，二次懲罰項結(jié)構(gòu)簡單，通常會導致數(shù)據(jù)丟失，而非二次懲罰項可避免該弊端[6，7]，本文選用非二次懲罰項.

(6)

式中，M=Med(fzj,j′∈Nzj)，Nzj代表fzj的鄰域.

將非二次懲罰因子加到最大似然函數(shù)中后，那么含有多個參數(shù)的估計誤差為：

(7)

事實上，就是在似然函數(shù)添加懲罰最小二乘項|Q(β)|0.5，似然函數(shù)可描述成：

L(β)*=L(β)|Q(β)|0.5

(8)

對數(shù)似然函數(shù)可描述成：

l(βj)*=S(β)0.5log|Q(β)|

(9)

得分函數(shù)的基本形式可描述成：

S(βj)*=S(β)-Ab(β)/n

(10)

其中，

b(β)/n=(XTWX)-1XTWε

(11)

A=XTWX

(12)

利用得分函數(shù)與添加懲罰項之后的最大似然函數(shù)，得到先驗信息如下：

S(β)*=S(β)-XTWε

(13)

2.2 EM算法改進的實現(xiàn)

在上述處理最大似然函數(shù)的基礎上，本節(jié)首先對EM算法實現(xiàn)過程進行分析，然后引入非負約束先驗信息，采用半監(jiān)督機器學習的方式對EM算法實現(xiàn)改進.

EM算法指的是觀測數(shù)據(jù)是否含隱含變量條件下，也就是所用觀測數(shù)據(jù)是非完整數(shù)據(jù)的情況下，使用極大似然函數(shù)對這些數(shù)據(jù)進行處理，經(jīng)過多次循環(huán)，最終獲得最優(yōu)值的算法[9，10].

在傳統(tǒng)EM算法中，通常會使用最大似然準則完成對參數(shù)估量.假設存在N個數(shù)據(jù)X=[x1,x2,…,xN]，這些數(shù)據(jù)是通過特定分布p(X|θ)獨立采樣獲取[11]，結(jié)合先驗知識，則似然函數(shù)可描述成：

(14)

最大似然準則為找到符合以下條件的模型參數(shù)：

θ*=arg maxL(θ|X)

(15)

為了簡化計算過程，使用函數(shù)log(L(θ|X))進行最終解的優(yōu)化，其中，log(L(θ|X))為對數(shù)似然.如果Z代表一個數(shù)據(jù)集，其中有兩組數(shù)據(jù)，一組是已觀測數(shù)據(jù)，另一組是未觀測數(shù)據(jù)，用X代表已觀測，用Y代表未觀測，則Z=(X,Y)一般被稱作完全數(shù)據(jù)集與缺失數(shù)據(jù)集，則有：

p(z|θ)=P(x,y|θ)=p(y|x,θ)p(x|θ)

(16)

假定似然函數(shù)可表示成：

L(θ|Z)=p(X,Y|θ)

(17)

完整數(shù)據(jù)的對數(shù)似然函數(shù)一般是在E步驟中進行的，這里X為已知量，那么針對未知變量Y的期望[12]用R函數(shù)表示：

(18)

在M-step中，通過下式對模型參數(shù)進行更新處理：

(19)

EM算法通常不斷對E步與M步進行循環(huán)處理，直至參數(shù)達到收斂.它在理想狀態(tài)下可獲得局部最優(yōu)化值[13].

EM能夠適應不同的問題環(huán)境，為了充分考慮不同應用場景，統(tǒng)一表示成為：

y=Cx

(20)

其中，矢量y∈Rm×1代表測量數(shù)據(jù)，矢量x∈Rn×1代表觀測對象密度分布估計值，矩陣C∈Rm×n代表映射矩陣.

考慮到大部分物理過程均為衰減過程，x與y均為非負矢量，然而矢量δU與δσ無法保證非負約束，為此，引入先驗信息對δU進行計算：

δU=(-1)q(Umea-Uref)

(21)

其中，Uref用于描述理論測量值，Umea用于描述實際測量值.q值主要取決于先驗信息(1.1節(jié)得到)，也就是如果Uref和Umea相比，Uref為較低的測量值，那么q=2；否則，q=1.

在上述非負約束先驗信息下，將半監(jiān)督機器學算法思想應用于EM算法的優(yōu)化之中.

通常來講，如圖1所示，在EM算法的每次循環(huán)中.

圖1 EM算法迭代過程示意圖Fig.1 Schematic diagram of iteration process of EM algorithm

設定沒有標注樣本di按照權(quán)重P(cj|di;θ′)分配，也就是在確定c*值的情況下，下一輪計算di也僅可用于占其P(c*|di;θ′)部分參與和c*的訓練，并且需考慮其和其余類別相關(guān)P(cj|di;θ′)的可能性.EM算法不判斷為標定樣本量，從而導致陷入局部最優(yōu)，且收斂速度變慢.在EM算法中，P(cj|di;θ′)一直非零，所以本和其它種類相關(guān)的未標注的信息也在很大程度上會以P(cj|di;θ′)的部分對其余訓練產(chǎn)生干擾，導致陷入局部最優(yōu).

半監(jiān)督機器學習方法在每次訓練時，可把確定結(jié)果引入到當前標注樣本集，使用已經(jīng)得到的結(jié)果訓練，達到較好的訓練效果，這是一種自訓練的方式，大大避免了局部最優(yōu)化問題.

本節(jié)把這種半監(jiān)督機器學習方法用于EM改進中，在每次迭代，按照E步驟所得結(jié)果標注確定的樣本數(shù)據(jù)，M步驟訓練新訓練集下樣本[14，15].使得每次迭代未標注樣本集U逐步減小，加大迭代速度，并且防止干擾.所以針對當前剛被添加至標注樣本集的文本di∈L，如圖2所示，依據(jù)訓練結(jié)果直接設置P(cj|di;θ′)∈{0,1}，其余信息不會對其它訓練產(chǎn)生干擾.

本文給出半監(jiān)督機器學習改進EM算法的方法，如下：

1)假設t=0.

2)定義θ′(0)=argmaxθP(θ|L).

3)當U!=?時，執(zhí)行E步驟，假設z′(t+1)=E[z|D;θ′(t)]，則有：

P(i*,j*)=argmax(i,j){zij|di∈U}

(22)

令L=L∪{(di*,lj*)}，U=U{di*}，針對j=1～|C|，令zi*j=0，否則zi*j*=1

4)那么M步有，θ′(t+1)=argmaxθP(θ|D;z′(t+1)).

5)令t=t+1，循環(huán)進行上述步驟，輸出θ′(t).

本節(jié)使用半監(jiān)督機器學習的方式，在每輪E步中都會選擇zj中最大的zi*j*，同時把di*從U中刪除，把(di*,lj*)添加至集合L，并且將zi*j(j≠j*)置0，將zi*j*置1.M-step在訓練集上對θ′進行估計.事實上，每輪迭代不是只選擇一個沒有標注的樣本進行標注，可依據(jù)差異原則，標注若干可標注樣本，實現(xiàn)標注效率的大幅度提升.

半監(jiān)督機器學習方法在每輪迭代過程中會將完全確定的未標注樣本添加標簽，放入標注樣本集合，為后續(xù)訓練提供高質(zhì)量標注樣本，大大減少循環(huán)次數(shù)，從而避免了局部最優(yōu)化問題的發(fā)生，提高訓練性能.

圖2 改進EM過程示意圖Fig.2 Modified EM process diagram

在上述分析的基礎上，將最大似然方法引入，利用其對EM模型進行求解計算，構(gòu)造下述似然函數(shù)：

(23)

上式中，λi=(Jδθ)i代表期望值.為了提高收斂速度，在似然函數(shù)中加入懲罰最小二乘，引入非負約束當成先驗信息，轉(zhuǎn)換成最小化問題：

(24)

2.3 改進EM算法的應用

為更深入闡述本文優(yōu)化方法，現(xiàn)使用本文優(yōu)化后的方法對混合矩陣與高斯混合模型參數(shù)進行計算估量.

首先對混合矩陣進行剖析，x=[x1,x2,…,xd]T是d維隨機變量，它概率密度函數(shù)可表示成：

(25)

用θm代表某個變量的密度模型中的參數(shù)，通過各p(x|θm)，獲取差異混合矩陣.混合矩陣全部參數(shù)集合可描述成θm={(?m,θm)}.

混合高斯模型把各點出現(xiàn)的概率當成多個混合模型得到的結(jié)果，這是一種聚類的思維[16].混合高斯模型將每個模型經(jīng)過加權(quán)處理之后，可得其概率密度函數(shù)[17]：

(26)

(27)

其中，πk代表權(quán)重，代表模型被選中概率，μk、∑k分別代表均值和方差.

使用最大似然函數(shù)[18]的方式對混合高斯模型進行訓練，可表示成為：

(28)

針對上式及混合矩陣參數(shù)的直接求解非常困難，本節(jié)采用改進EM算法迭代訓練獲取.

給出有限標記訓練樣本集，用Gl={(X1,y1),…,(XL,yL)}進行描述，其中Xi代表某樣本，該樣本是高斯混合模型，yi代表對應類標.在整個訓練樣本集Gl中，共存在M個類型，因此有yi∈{c1,c2,…,cM}.

X=〈x1,x2,…,xN〉，xn∈Rd.針對各Sl中的(Xi,yi)，假設其均互相獨立同分布，并假設針對未標記樣本X，如果最大后驗概率為P(cj|X)，那么j類中包含X，可通過類條件概率密度函數(shù)p(X|cj)與相關(guān)法則對后驗概率進行求解：

(29)

式中，P(cj)代表先驗概率.

(30)

針對于變量分類條件概率密度，使用混合高斯模型進行表示[19]，如公式(31)所示.

(31)

某一種混合變量的數(shù)量用K表示，混合權(quán)重用?jk進行表示，使用p(x|μjk,∑jk)代表多元混合高斯模型的概率密度.

完整高斯混合模型，也就是X=〈x1,x2,…,xN〉的類條件概率密度可寫成公式(32)的結(jié)構(gòu)形式.

(32)

則可獲取后驗概率，P(cj|X)，令：

(33)

利用上述過程實現(xiàn)樣本標記.

θj=(?jk,μjk,∑jk)代表混合高斯模型，θm={(?m,θm)}代表混合矩陣全部參數(shù)集合，使用EM算法對它們的參數(shù)進行估量，在半監(jiān)督機器學習過程中，如果學習樣本集包含兩種不同的集合組，即：G=Gl∪Gu，可以為為標記和已標記兩個組.

G={(x1,y1),…,(xl,yl),(xl+1,yl+1),…,(xl+1,yl+u)}

(34)

針對各未標記樣本xi，對描述類別數(shù)量的M個隱含變量zij進行定義：

(35)

θj代表混合矩陣和混合高斯模型參數(shù)，使用改進之后的EM算法進行求解.其中，初始迭代參數(shù)θ0使用已經(jīng)做過標注樣本進行計算，再通過下述過程進行迭代：

對于未分類的樣本，在E步驟中使用最大后驗概率進行標記，通過公式(36)計算：

(36)

在M步驟中，按照所作標記的新樣本使用最大似然對參數(shù)進行重新求解，得到新的結(jié)果.

基于上述過程，設計改進EM算法估計參數(shù)流程為：

1)假設t=0.

4)針對M步驟，令θl+1=argmaxθP(G,z(l+1)|θ).

5)令t=t+1，對以上步驟循環(huán)至收斂.

6)輸出θl，需要注意的是，每一類的混合高斯模型的參數(shù)都是通過當前類別中的樣本集進行估計的.

3 實驗與分析

3.1 實驗理論

對于EM算的局部最優(yōu)化問題，主要原因為其初始值的設置不夠合理.

在本次實驗中，首先對EM算法的初始化值進行訓練學習，同時，將傳統(tǒng)方法作為對照實驗組，與所提方法進行對比，并給出對比結(jié)果.

衡量算法有效性的另一個參數(shù)為算法擬合值，所謂算法擬合效果即算法能否按照原設定進行運算和應用.本次實驗獲取文獻[4]算法、文獻[6]算法以及所提算法的擬合曲線，具體獲取方法如下：

將待測數(shù)據(jù)集H劃分為兩個子集H1與H2，其劃分規(guī)則如下：將每個待測數(shù)據(jù)隨機的劃分到兩個子集的其中任意一個中去.分別在兩個觀測樣本子集H1，H2上將算法目標函數(shù)極大化，得到擬合值，并對多個擬合值進行整合，得到擬合曲線.利用擬合曲線可以看出算法的擬合效果，擬合的吻合程度越高，則說明實驗方法的性能越高.

3.2 實驗過程

針對EM方法在執(zhí)行過程中經(jīng)常會經(jīng)過很多次學習來篩選出最優(yōu)的初始值.表1為傳統(tǒng)方法和改進之后的方法性能對比.

分析表1可知，初始化相同的情況下，改進之后的方法對局部最優(yōu)化問題起到了明顯的抑制作用.

利用復合抽樣法形成三階數(shù)據(jù)，參數(shù)設置成，樣本數(shù)量是2000個.樣本采樣序列以及理論曲線分別用圖3和圖4進行描述.

在進行實驗過程中，本文分別將文獻[4]方法和文獻[6]方法作為對比進行參數(shù)估計，預設的研究模型的階數(shù)是3，但本文方法模型階數(shù)是4，這主要是由于復雜曲線可利用各種組成成分構(gòu)成.

表1 傳統(tǒng)方法和改進后的方法性能對比
Table 1 Performance comparison between traditional
method and improved method

實驗次數(shù)算法迭代次數(shù)迭代時間/s對數(shù)似然函數(shù)值1傳統(tǒng)算法5019-3.52e6改進算法7826-3.44e62傳統(tǒng)算法5019-3.53e6改進算法4318-3.48e63傳統(tǒng)算法8327-3.52e6改進算法3617-3.48e6

圖3 樣本采樣序列Fig.3 Sample sampling sequence

010.008.006.004.002.0擬合值-20-100102030樣本值圖4 理論曲線Fig.4 Theoretical curve010.008.006.004.002.0擬合值-20-100102030樣本值原始曲線本文方法擬合結(jié)果圖5 本文方法擬合結(jié)果Fig.5 Fitting results of thismethod

為了將本文方法和文獻[4]方法、文獻[6]方法進行比較，也把這兩種方法的階數(shù)設置成6.本實驗利用不同方法擬合曲線和原始曲線相比，替代參數(shù)估計值與設定值的比較，從而便于分析.

010.008.006.004.002.0擬合值-20-100102030樣本值原始曲線文獻[]4方法擬合結(jié)果圖6 文獻[4]方法擬合結(jié)果Fig.6 Fitting results ofdocument[4]010.008.006.004.002.0擬合值-20-100102030樣本值原始曲線文獻[6]方法擬合結(jié)果圖7 文獻[6]方法擬合結(jié)果Fig.7 Fitting results ofdocument[6]

采用本文方法、文獻[4]方法、文獻[6]方法進行擬合，得到的擬合曲線和原始曲線比較結(jié)果依次用圖5、圖6和圖7進行描述.

本文實驗樣本數(shù)量較為充足，將不同樣本初始條件劃分成6類，針對6種初始條件，獲取本文方法擬合結(jié)果和文獻[4]方法、文獻[6]方法相比的性能可通過表2進行描述.

表2 源信號處理前后功率譜峰值及對應頻率
Table.2 Comparison of fitting performance of three methods

初始條件采用方法迭代次數(shù)/次迭代時間/s似然函數(shù)值初始條件1本文方法4215-3.46E+06文獻[4]方法5323-3.59E+06文獻[6]方法8235-3.56E+06初始條件2本文方法4919-3.47E+06文獻[4]方法6828-3.61E+06文獻[6]方法7533-3.58E+06初始條件3本文方法3812-3.49E+06文獻[4]方法6531-3.55E+06文獻[6]方法8925-3.59E+06初始條件4本文方法3220-3.46E+06文獻[4]方法5139-3.54E+06文獻[6]方法5551-3.62E+06初始條件5本文方法4518-3.49E+06文獻[4]方法7237-3.59E+06文獻[6]方法8842-3.53E+06初始條件6本文方法4113-3.49E+06文獻[4]方法8921-3.62E+06文獻[6]方法6036-3.65E+06

3.3 實驗結(jié)果分析

綜合分析不同方法擬合曲線和原始曲線比較結(jié)果可以看出，本文提出的基于半監(jiān)督機器學習的改進EM算法得到的擬合曲線和原始曲線的重合程度比文獻[4]方法、文獻[6]方法明顯更優(yōu)，表明本文方法擬合性能明顯高于其它兩種方法，這主要是因為本文改進EM算法對傳統(tǒng)EM算法容易陷入局部最優(yōu)的弊端進行了有效的優(yōu)化，使得本文方法得到的最優(yōu)解和實際值更加吻合，而文獻[4]方法、文獻[6]方法無法解決傳統(tǒng)EM算法容易陷入局部最優(yōu)的問題，得到的解并非最優(yōu)解，導致擬合精度低.

分析不同方法擬合性能可以看出，在初始化相同情況下，本文方法對模型容易進入局部最優(yōu)的問題起到了明顯的抑制作用，能夠獲取更優(yōu)的擬合結(jié)果.不僅如此，本文方法迭代次數(shù)最少，迭代時間最短，整體性能優(yōu).

4 結(jié) 論

本文針對EM算法及其改進改進所存在的不足，使用半監(jiān)督機器學習機制對其進行改進和優(yōu)化.

使用二項分布概率函數(shù)以及懲罰概率定理以及，對最大似然函數(shù)進行描述，將懲罰因子加入到最大似然函數(shù)之中，大大降低了模型的最大似然估計的誤差.

對EM算法實現(xiàn)過程進行分析，引入非負約束先驗信息，針對EM算法很難在全局量空間中求解出最優(yōu)解問題，結(jié)合半監(jiān)督機器學習機制實現(xiàn)EM算法的優(yōu)化改進，利用其中的一種自訓練學習模式，在每次的訓練的過程中，把確定標本放入到標記集合之中，經(jīng)過自己所得到的結(jié)果進行訓練，獲得很好的訓練結(jié)果，很好地避免了陷入局部最優(yōu).在此基礎上，EM算法數(shù)學模型參數(shù)通過最大似然方法進行計算和優(yōu)化，構(gòu)造似然函數(shù)，在最大似然函數(shù)增加懲罰最小二乘因子，引入非負約束當成先驗信息，轉(zhuǎn)換成最小化問題.

仿真實驗結(jié)果表明，本文所提的基于半監(jiān)督機器學習模式的改進EM算法得到的擬合曲線和原始曲線的重合程度比其它方法明顯更優(yōu)，說明所提方法不會陷入局部最優(yōu)，擬合性能好.除此之外，所提方法迭代次數(shù)最少，迭代時間最短，整體性能優(yōu).