隱變量對EM算法的影響

劉芝秀，呂鳳姣，李運(yùn)通

(1.南昌工程學(xué)院 理學(xué)院,江西 南昌 330099；2.黃河科技學(xué)院 工學(xué)部,河南 鄭州 450063；3.陜西鐵路工程職業(yè)技術(shù)學(xué)院 基礎(chǔ)課部，陜西 渭南 714025)

引言

EM算法是由Dempester,Larid和Rubin于1977年提出的，它對含有隱變量的概率模型參數(shù)的估計往往非常有效，是一種改進(jìn)的極大似然估計方法[1]。文獻(xiàn)[2]給出了EM算法收斂性的有關(guān)證明，彰顯了EM算法簡單穩(wěn)定的特點(diǎn)，Neal與Hinton又進(jìn)一步給出了推廣的GEM算法[3]，事實(shí)上，該算法引起了許多學(xué)者的關(guān)注，發(fā)展很快并被廣泛的應(yīng)用[4-11]，且在各種不同的具體應(yīng)用上產(chǎn)生了許多新的有價值的問題，促使著人們對它的進(jìn)一步研究。

EM算法的具體步驟是[12]

輸入：觀測變量數(shù)據(jù)Y，隱變量數(shù)據(jù)Z，聯(lián)合分布P(Y,Z|θ)，條件分布P(Z|Y,θ)；

輸出：模型參數(shù)θ。

(1)選擇參數(shù)的初值θ(0)，開始迭代；

(2)E步：記θ(i)為第i次迭代參數(shù)θ的估計值，在第i+1次迭代的E步，計算

Q(θ,θ(i))=Ez[logP(Y,Z|θ)|Y,θ(i)]

其中P(Z|Y,θ(i))是在給定觀測數(shù)據(jù)Y和當(dāng)前的參數(shù)估計θ(i)下隱變量數(shù)據(jù)Z 的條件概率分布；

(3)M步：求使Q(θ,θ(i))極大化的θ，確定第i+1次迭代的參數(shù)的估計值θ(i+1)

(4)重復(fù)第(2)步和第(3)步，直到收斂。

上述EM算法參數(shù)的初值可以任意選擇，在解決實(shí)際問題的過程中，應(yīng)當(dāng)注意初值的選擇，嘗試不同的初值，比較后擇優(yōu)取定。然而，在使用EM算法解決實(shí)際概率模型的參數(shù)估計問題時，不僅僅初值的選擇有多種，隱變量的選擇也并不是一成不變的，隱變量可以有多種選擇方式，它對EM算法的影響如何？本文通過一個具體的模型探討了這一問題。

1 驗證模型與具體算法

所用實(shí)驗?zāi)Ｐ涂赡墚a(chǎn)生四種結(jié)果，分別記為A、B、C、D，每種結(jié)果出現(xiàn)的概率分布和試驗多次后發(fā)生的次數(shù)如表1所示。

其中θ∈(0,1)為分布模型的參數(shù)，y1、y2、y3和y4是總共進(jìn)行y1+y2+y3+y4次實(shí)驗后，結(jié)果分別出現(xiàn)A、B、C、D的次數(shù)，試求θ的估計值[13-14]。

表1 概率分布

1.1 最大似然和牛頓算法

這個模型的參數(shù)估計并不一定要用含隱變量的EM算法，直接采用極大似然法和牛頓法[15]即可給出估計參數(shù)θ的迭代算法。為便于與選擇不同隱變量的EM算法進(jìn)行比較，下面先給出用最大似然法和牛頓法估計θ值的迭代公式。

模型對應(yīng)的最大似然函數(shù)為

取對數(shù)似然函數(shù)，去掉常數(shù)，化簡得

lnL(θ)=y1ln (2-θ)+y2ln (1-θ)+y3ln (1+θ)+y4ln (θ)

求導(dǎo)并令導(dǎo)數(shù)等于0得

即

(y1+y2+y3+y4)θ3+(-y2-3y3-2y4)θ2+(-y1-2y2+2y3-y4)θ+2y4=0

使用牛頓法求解上述方程，記上述方程對應(yīng)的函數(shù)為：

f(θ)=(y1+y2+y3+y4)θ3+(-y2-3y3-2y4)θ2+(-y1-2y2+2y3-y4)θ+2y4

則估計參數(shù)θ的迭代公式為

(1)

置初值為θ0。

1.2 含隱變量的EM算法一

上述z1，z3是為使用EM算法而引入的隱變量，是不可觀測的數(shù)據(jù)。那么，z1服從二項分布：

(2)

z3服從二項分布：

(3)

引入隱變量后模型對應(yīng)的似然函數(shù)為

取對數(shù)似然函數(shù)，去掉常數(shù)，化簡為

ln [(1-θ)z1+y2θz3+y4]=(z3+y4)lnθ+(z1+y2)ln (1-θ)

該結(jié)果中含有不能觀測的隱變量z1和z3，根據(jù)EM算法操作如下

E步：取初始值θ0，這里的θ0是上述指二項分布中的參數(shù)θ。化簡后的似然函數(shù)(z3+y4)lnθ+(z1+y2)ln (1-θ)是關(guān)于z1和z3的隨機(jī)變量，且z1和z3服從(1.2)和(1.3)式的二項分布，取期望得

E[(z3+y4)lnθ+(z1+y2)ln (1-θ)]=(Ez3+y4)lnθ+(Ez1+y2)ln (1-θ)

記

(4)

M步：求Q(θ)的最大值，令其導(dǎo)數(shù)為0得

解方程得

令θ0=θi，θ=θi+1，則得估計參數(shù)θ的EM迭代公式

(5)

1.3 含隱變量的EM算法二

下面換一種新的隱變量，從而給出估計參數(shù)θ的EM算法的新迭代公式。

(6)

(7)

則引入新隱變量后，模型對應(yīng)的似然函數(shù)為

取對數(shù)似然函數(shù)，去掉常數(shù)，化簡為

(z1+y3-z3+y4)lnθ+(y1-z1+y2)ln (1-θ)-z1ln 2

同樣的根據(jù)EM算法操作

E步：取初始值θ0，求期望

E[(z1+y3-z3+y4)lnθ+(y1-z1+y2)ln (1-θ)-z1ln 2]

=(Ez1+y3-Ez3+y4)lnθ+(y1-Ez1+y2)ln (1-θ)-Ez1ln 2

記

(8)

M步：求Q(θ)的最大值，令其導(dǎo)數(shù)為0得

解方程得

則含新隱變量的EM迭代公式為

(9)

2 數(shù)據(jù)實(shí)驗

下面我們通過兩組數(shù)據(jù)實(shí)驗說明EM算法的收斂性并具體觀察不同隱變量對EM算法的影響。

2.1 數(shù)據(jù)實(shí)驗一

設(shè)已經(jīng)進(jìn)行了(y1+y2+y3+y4=)197次測試，四個實(shí)驗結(jié)果出現(xiàn)的次數(shù)分別為(y1=)75,(y2=)18,(y3=)70,(y4=)34，下面計算θ的估計值。

將y1=75,y2=18,y3=70,y4=34代入(1)、(5)和(9)等迭代公式分別得

(10)

(11)

(12)

取不同初值分別按(10)-(12)式進(jìn)行迭代，借助計算機(jī)執(zhí)行，迭代計算的結(jié)果如表2所示。

2.2 數(shù)據(jù)實(shí)驗二

設(shè)已經(jīng)進(jìn)行了(y1+y2+y3+y4=)2081次測試，四個實(shí)驗結(jié)果出現(xiàn)的次數(shù)分別為(y1=)780,(y2=)263,(y3=)781,(y4=)257，下面計算θ的估計值。

將y1=780,y2=263,y3=781,y4=257代入(1)、(5)和(9)等迭代公式分別得

(13)

(14)

(15)

取不同初值分別按(13)、(14)和(15)式進(jìn)行迭代，借助計算機(jī)執(zhí)行，迭代計算的結(jié)果如表3所示。

3 分析與結(jié)論

從數(shù)據(jù)實(shí)驗的結(jié)果表2和表3可知，兩種不同隱變量所對應(yīng)的EM算法都是穩(wěn)定可靠的，即使初值的選擇不同，亦能使得EM算法收斂(見表2和表3第三和四列)；而通常的最大似然和牛頓法雖然比EM算法快4至12倍(見表2和表3第三列，34/5，63/5，33/5，61/5，33/5，63/5，34/8，65/8，32/5，62/5，29/3，54/3，32/5，61/5的平均值約為9.63)，但卻對初值非常敏感，初值選擇不恰當(dāng)，甚至?xí)?dǎo)致最大似然和牛頓法不收斂。

表2 不同迭代的實(shí)驗結(jié)果

表3 不同迭代的實(shí)驗結(jié)果

另外，從(4)和(8)式可以看到，隱變量選擇的不同直接影響Q函數(shù)的形式，由此而得到的迭代公式自然不同，其收斂速度可能差別較大，服從(6)和(7)式分布的隱變量所對應(yīng)的EM算法比服從(2)和(3)式的隱變量所對應(yīng)的EM算法的收斂速度要將近慢一倍(見表2.1和2.2第三列，64/34，63/34，61/33，63/33，65/34，64/33，62/32，54/29，61/32，62/33的平均值約為1.86)，因此可以推斷，隱變量的選擇對于EM算法的收斂速度有較大的影響。