算法詳細例子及推導(dǎo)

December3,2012簡 一個例子 數(shù)學基礎(chǔ) 極大似然估計 聚 簡期望最大化(Expectation)算法最初是由eppellini2]等人1950年在討論頻率的估計的時候。后來又被[]和aum[4]等人發(fā)展的更加廣泛。目前的較多的是1977年]等人的工作。它主要用于從不完整的數(shù)據(jù)中計算最大似然估計。后來經(jīng)過一個本章節(jié)希望通過一個例子來解釋期望最大化算法的來由以及合理性。A和普通的硬幣不一樣，他們投擲出正面的概率和投擲出的概率不一定相。A和B投為θA和B地做511011B52A93A84B45A7:在這個實驗中，我們記錄兩組隨量X=(X1,X2,X3,X4,X5),Z=(Z1Z2Z3Z4Z5)Xi∈{12345678910}i中出現(xiàn)正面的次數(shù)，Zi∈{AB}AB我們的目標是通過這個實驗來估計θ=(θA,θB)參數(shù)估計就是有完整數(shù)據(jù)的參數(shù)估計，這個是因為我們不僅僅知道每次試驗中投擲出正面的次數(shù)，我們還知道每次試驗中投擲的是硬幣A還是。一個很簡單也很直接的估計θ的方法如公式1

A投擲出正面的次數(shù)用硬A投擲的次數(shù)B

B B實際上這樣的估計就是統(tǒng)計上的極大似然估計(umlikelihoodestimation)P(X,Z|θ)X,Z的聯(lián)合概率分布（其中帶有參x0=(59847)z0=(BAABA)的概率2P(X=x(0)Zz)θ)就叫做θ的似然函數(shù)。它對θ求偏導(dǎo)并令偏導(dǎo)數(shù)為0，就可以得到如1的結(jié)果。P(X=x(0),Z=z)θ=C3P(Z=A)3(1?P(Z=5×C9θ9(1?θA0 (1?10 ×C7θ7(1? (1? (1?10這個問題稍微改變一下，我們所觀察到的結(jié)果修改一下：Z(Hiddenriable，X(Observdariable。這個時候再來估計參數(shù)A和B，就沒有那么多數(shù)據(jù)可供使用了，這個時候的估計叫做不完整數(shù)據(jù)的參數(shù)估計。如果我們這個時候有某種方法（比如，正確的猜到每次投擲硬幣是A還是B，這樣的話我們就可以將這個不完整的數(shù)據(jù)估計變?yōu)橥暾麛?shù)據(jù)估計。當然我們?nèi)绻麤]有方法來獲得的數(shù)據(jù)的話，那么下面提供了一種在這種不完整數(shù)據(jù)的情況下來估計參數(shù)θ的方法。我們用迭代的方式來進行：我們先賦給θ一個初始值，這個值不管是經(jīng)驗也好猜的也好，反正我們給它一個初始值。在實際使用中往往這個初始值是有其他算法的結(jié)果給出的，當然隨機給他分配一個符合定義域的值也可以。這里我們θA=0.7,B=0.41A5個正面的概率為C105×0.75×(1?0.7)5≈0.1029；如果投擲的是B5個正面的概C105×0.45×(1?0.4)5≈0.20071的試驗結(jié)果，可以判B的概率為0.2007/(0.1029+0.2007)=0.6611。因此這個結(jié)果更可能是投擲B出現(xiàn)的結(jié)果。假設(shè)上一步猜測的結(jié)果為B,A,A,B,A，那么根據(jù)這個猜測，可以像完(公式2)重新計θ的值。2-3θ的估計?，F(xiàn)在你期望最大化算法就是在這個想法上改進的。它在估計每次投擲的硬幣的時候，并不要確定住這次就是硬幣A或者B，它計算出來這次投擲的硬幣是AB或者叫做ZEθZ的（條件）分布Pθ(Zzj|Xixi)logPθ(ZXx)1E(logPθ(Z,X=x))

Pθ′(Z=zj|Xi=xi)logPθ(Z=zj,Xi=

θθθ′θ值。公式3中已經(jīng)θ一個變量了，θ′是一個確定的值，這個公式或者函數(shù)常常叫做Q函數(shù)，用Q(θ,θ′)來表示。M步驟極大化Q，往往這一步是求導(dǎo)，得到由舊的θ值θ′來計算新的θ值的 = 通常稱為EM數(shù)學X和給定觀察樣本x1,x2,...,xn的情況下，極大化對數(shù)似然函數(shù)l(θ)

lnP(Xi= ∑P(Xi=xi) P(Xi=xi,Z= j1這里因為參數(shù)θ的寫法與條件概率的寫法相同，因此將參數(shù)θ寫到下標以更明確的述其中Z為隱藏隨量,{zj}是Z的所有可能的取值。那l(θ)

P(Xi=xi,Z=n

P(Xi=xi,Z=

?可能的j,αj(01]和jαj=1叫做凸函數(shù)的定義。f(x)為凸函數(shù)，?i=1,2,...,n,λi∈[0,1], λi=f(xnx1x2xn f λixi) nλif 1=2=...=n凸函數(shù)的其他性質(zhì)不再贅述。對數(shù)函數(shù)是一個嚴格凸函數(shù)。因而我們可以l(θ)

P(Xi=xi,Z=α ≥∑∑αlnP(Xi=xi,Z=

P(Xi=xi,Z=zj)= cj

jαj=1α=P(Xi=xi,Z= i P(X=xiiα現(xiàn)在來解釋一下我們得到了什么。αjZ=zjX=xi下的條件概率或者后驗概率。求α就是求隱藏隨量Z的條件分布。總結(jié)一下目前得到αl(θ)

αj

P(Xi=xi,Z= 2它就是大名鼎鼎的琴生（Jensen）不θαθ極大似然估計好吧，我覺得還是再說說極大似然估計吧。給定一個概率分布D，假設(shè)其概率密度函數(shù)為，其中f帶有一組參數(shù)θ。為了估計這組參數(shù)θ，我們可以從這個分布中抽出一個具有n個采樣值的1,2,...,Xn，那么這個就是n個隨值1,2,...,xn那么l(θ)

f 對于fl(θ)

P(Xi= 注意，這個函數(shù)中是含有參數(shù)θ的。θ的極大似然估計就是求讓上面似然函數(shù)取極大值的時候的參數(shù)θ值。一般來說，會將上面那個似然函數(shù)取自然對數(shù)，這樣往往可以簡化計算。記住，這樣僅僅是為了簡化計算3。取了自然對數(shù)之后的函數(shù)叫做對數(shù)似然函數(shù)lnl(θ)

lnf 3取了對數(shù)之后還可以跟信息熵等概念聯(lián)系4關(guān)于凸函數(shù)有很多種說法，上凸函數(shù)和下凸函數(shù)，凸函數(shù)和凹函數(shù)等等，這里指二階導(dǎo)數(shù)大于（等于 的一類函數(shù)，而凹函數(shù)是其相反數(shù)為凸函數(shù)的一類函期望最大化算法收斂lθ))≥lθ)n P(X=x,Z=zαl(θ(t+1)) α(t+1) α≥

P(X=x,Z=zαα(t)ln α≥

P(X=x,Z=zα(t)ln

=l)件）的時候才有等號成立，第二個大于等于號正是M步驟的操作所致。l(θ是隨著迭代次數(shù)的增加越來越大的，收斂條件是值不應(yīng)用參數(shù)估聚最大似然估 Ceppellini,r.,Siniscalco,M.&Smith,C.A.Ann.Hum.Genet.20,97–115Hartley,H.Biometrics14,174–194Baum,L.E.,Petrie,T.,Soules,G.&Weiss,N.Ann.Math.Stat.41,Dempster,A.P.;Laird,N.M.;Rubin,D.B.(1977)."umLikelihood pleteDataviatheEMAlgorithm".Journalof