EM算法是英文expectation-maximization算法的英文簡寫,翻譯過來就是期望最大化算法,其實是一種根據(jù)求參的極大似然估計的一種迭代的優(yōu)化策略,EM算法可以廣泛估計是因為他可以從非完整的數(shù)據(jù)集中對于參數(shù)進行極大似然的估計,這樣的方法對于處理殘缺數(shù)據(jù),截尾數(shù)據(jù)和一些帶有噪聲的數(shù)據(jù)來說是很有效的.
在寫這篇文章之前,我看了很多篇博客,學(xué)習(xí)了很多的知識,也參照了很多的資料,希望可以從EM算法的迭代優(yōu)化理論和一般的步驟中出發(fā),然后能夠舉一個例子來使我們理解這個EM算法,然后在對其收斂性進行證明,目的是為了說明EM算法每一次迭代都是能夠提高似然函數(shù)值然后收斂到一個穩(wěn)定的點,再引出EM算法的收斂速度.
大概通過上述部分,我們可以得到基于其簡單,收斂,穩(wěn)定上升的優(yōu)勢,但是也會產(chǎn)生一些缺點,比如收斂速度過慢的加速方法等,在第二篇文章中將會介紹這個處理缺點的方法,然后會寫一些關(guān)于EM算法的重要應(yīng)用,包括EM算法在二元正態(tài)分布上的參數(shù)估計的應(yīng)用,混合高斯分布參數(shù)估計方面的應(yīng)用,以及EM算法在隱馬爾科夫模型上參數(shù)的應(yīng)用(一種EM算法的特殊情形),希望通過這一系列的文章可以讓大家理解好EM算法的明顯優(yōu)勢以及原理,讓我們開始吧!
背景:
極大似然估計和貝葉斯統(tǒng)計其實是作為現(xiàn)在的統(tǒng)計領(lǐng)域中非常熱門的領(lǐng)域了,其實來說他們的計算過程是有一定的相似成分的,比如極大似然函數(shù)估計在計算的方法上跟貝葉斯的后驗概率的計算是非常相似的,學(xué)過統(tǒng)計學(xué)習(xí)的我們知道,貝葉斯是分為兩種的大類的,一種是擁有顯式的后驗分布,這樣的一般用于簡單的似然函數(shù),另外一種是數(shù)據(jù)添加的算法,有些時候我們的數(shù)據(jù)可能會存在缺失或者是似然函數(shù)不是顯性的,數(shù)據(jù)添加類在這時候就可以很好的應(yīng)用,他可以將已經(jīng)觀測到的數(shù)據(jù)基礎(chǔ)上加上一些”潛在數(shù)據(jù)”,從而使得變得更簡單,完成極大化的工作,然后我們常用的一種數(shù)據(jù)添加法其實就是我們今天介紹的EM算法.
EM算法是一種迭代的優(yōu)化策略,他的計算方法是分為期望步(E步)和極大步(M步)的,所以這個算法的名字是這樣來的,EM算法受到了缺失算法的影響,最初就是為了解決上邊提到的數(shù)據(jù)缺失的問題,基本的思想就是首先根據(jù)已經(jīng)觀測出來的數(shù)據(jù)估計出模型參數(shù)的值,然后再根據(jù)上一步估計出的參數(shù)值來估計缺失數(shù)據(jù)的值,然后再根據(jù)估計中缺失的數(shù)據(jù)加上之前的已經(jīng)觀測到的數(shù)據(jù)重新在對參數(shù)值進行估計,然后反復(fù)的進行迭代,直到最后收斂,迭代結(jié)束.
而現(xiàn)在EM算法發(fā)展了幾十年了,在當(dāng)時的數(shù)據(jù)快速增長得那個時代,那時候處理數(shù)據(jù)很困難,經(jīng)常會出現(xiàn)數(shù)據(jù)缺失或者不可用的情況,當(dāng)時無非就是用用神經(jīng)網(wǎng)絡(luò)擬合,添補法,卡爾曼濾波法等等,但是最后還是EM脫穎而出,最主要還是他的算法步驟簡單,穩(wěn)定上升可以很可靠的找到最優(yōu)的收斂值,但是運用這種思想,我們拓展到了簡化問題策略,有時候缺失數(shù)據(jù)并非真的缺少了,這時候EM引入恰當(dāng)?shù)臄?shù)據(jù)添加技術(shù),這樣的數(shù)據(jù)被稱為”潛在數(shù)據(jù)”,復(fù)雜問題通過引入潛在數(shù)據(jù),能夠有效的解決我們的問題
“潛在數(shù)據(jù)”可以解釋為數(shù)據(jù)本身并不存在缺失變量秧倾，但觀察數(shù)據(jù)比較難以處理魔种，如果添加上額外的變量屎蜓，處理起來會變得比較簡 單惫周。假設(shè)X是已知的觀測數(shù)據(jù)，想象由隨機變量X生成的觀察數(shù)據(jù)連同來 自隨機變量y的缺失或未觀測數(shù)據(jù)惭适，得到Z=(X,Y)為完全數(shù)據(jù)笙瑟。通過給定觀察數(shù)據(jù)X,我們希望最大化似然的函數(shù)L(0/x).由于數(shù)據(jù)缺失或者其他原因?qū)?/p>
致采用該似然函數(shù)會難以處理，而采用Z|0和Y|(x,0)的密度則比較容易處 理腥沽。EM算法通過采用這些較容易的密度p(0|z),從而避開考慮了P(0|X).但是這在貝葉斯應(yīng)用中,對于后驗分布的P都是隨機變量.
但是不可避免EM算法也有一些缺點:
1:在缺失數(shù)據(jù)較多的情形,收斂的速度較慢.
2:對于某些情況下,要計算算法中的M步,即完成對似然函數(shù)的估計是非常困難的
3:在某些情況下是要獲得EM算法中的E步的期望顯式是非常困難或者不可能的
算法原理和步驟:
現(xiàn)在我們假設(shè)X是觀測數(shù)據(jù),Y是潛在數(shù)據(jù),EM算法迭代是為了尋求關(guān)于0最大化函數(shù)L(0|X),設(shè)0(k)是在進行K次迭代以后估計得到的最大值點,K屬于(0,1,2......),定義Q(0|0(k))
是在觀測數(shù)據(jù)X ={x1,x2….xn}的條件下完全數(shù)據(jù)的聯(lián)合對數(shù)函數(shù)似然的期望,既可以獲得以下式子:
通過上式我們可以發(fā)現(xiàn),一旦我們的樣本點X給定,那么Y就是Z的唯一的隨機部分,通過對于Y求條件期望,就又可以把Y給積分掉了,這樣使得Q(0|0(k))就完全成為了一個關(guān)于0的函數(shù),這樣就可以求使得Q(0|0(k))最大的0,并且記為0(k+1),以供下一次迭代使用.
EM算法從0(0)開始,然后在這兩部之間進行交替,E表示期望,M表示最大化,該算法可以概括如下:
1:E步,在給定的觀測數(shù)據(jù)X和已經(jīng)知道的參數(shù)條件下,求缺失數(shù)據(jù)Y的數(shù)學(xué)期望,即計算上面的提到的對數(shù)似然函數(shù)的條件期望Q(0|0(k)).
2:M步,就像不存在缺失數(shù)據(jù)Y一樣(在填充缺失數(shù)據(jù)后),針對完全數(shù)據(jù)下的對數(shù)似然函數(shù)的期望進行最大化處理,即求關(guān)于0似然函數(shù)Q(0|0(k))的最大化.設(shè)0(k+1)等于最大值點,更新0(k):
3:返回E步,知道滿足某停止規(guī)則為止.一般依賴于
現(xiàn)在使用韓佳偉的數(shù)據(jù)分析中的例子來詳細的說明EM算法:
1:現(xiàn)在假設(shè)進行一個實驗會出現(xiàn)現(xiàn)在四種結(jié)果,每種結(jié)果發(fā)生的概率分別為:
實驗進行了197次,四種結(jié)果發(fā)生了125,18,20,34次,這個時候的X={x1,x2,x3,x4}={125,18,20,34}
為了估計參數(shù),我們可以取0的先驗分布p(0)為U(0,1),由貝葉斯公式可知,0的后驗分布為:
把第一種結(jié)果分成發(fā)生概率分別為1/2和0/4的兩個部分,令Y和x1-Y分別表示為這兩部分試驗成功的次數(shù)(Y為缺失數(shù)據(jù)),則0的添加的后驗分布為:
這時候就該輪到了EM算法添加數(shù)據(jù)了,直接求0的極大似然估計也是比較麻煩的,現(xiàn)在使用EM算法后迭代最后一個后驗分布函數(shù)就簡單多了,(在上面的計算過程中,最下邊的那個符號,他表示的是符號兩端的式子成比例,并且這個比例跟0無關(guān),這個比例不會影響到EM迭代算法估計的結(jié)果,因為后面的極大化可以進行約去).
現(xiàn)在我們假設(shè)在第i+1次的迭代中,有估計值0(i),則可以通過EM算法中的E步和M步得到一個新的估計,在E步中:
因為在x和0(i)給定的情況下,Y服從二項式分布,因此可以得到E(Y|X,0(i))=2x(1)/[2+0(i)],于是便有:
在M步中,對上邊的式子中的0進行求導(dǎo)并且使結(jié)果為0,可以得到迭代的公式為:
這個時候從0(0)=0.5開始,經(jīng)過EM四次迭代以后收斂到0.6268,根據(jù)Matlab進行作圖,收斂曲線如下所示:
另外韓佳偉那本書使用的R,我這里使用的是MATLAB,效果類似,都可以實現(xiàn).
EM算法收斂性證明:
算法簡單逮走、收斂穩(wěn)定是EM算法的最大優(yōu)點鸠蚪，EM算法的簡便性在上文中已經(jīng)得到充足的認識今阳，現(xiàn)在需要對其估計得到的序列是不是達到了預(yù)期 的收斂要求师溅，即EM算法估計的結(jié)果是不是能穩(wěn)定收斂，以及收斂結(jié)果是不 是p(0IX)的最大值或局部最大值來進行驗證盾舌，本文下面需要來證明EM算法的收斂性墓臭。
第一步:吉布斯不等式:
當(dāng)且僅當(dāng)x=1時,等號成立
{PS:其實吉布斯不等式是詹森不等式的一個特例,因為log(x)是一個凸函數(shù),作圖的話就能夠發(fā)現(xiàn)在某一個時刻,吉布斯不等式和詹森不等式是有交點的在曲線上}
第二步:
現(xiàn)在先引出幾個定理:如果f(x),g(x)具有相同的支集的概率密度函數(shù),現(xiàn)在令:
則:
證明:
當(dāng)且僅當(dāng)f(x)=g(x)時,等號成立,此時log(g(x)/f(x))=f(x)/g(x)-1
第三步:
記錄EM算法的估計序列為{0(k)},證明EM算法每個最大化步都提高了對于觀測數(shù)據(jù)的對數(shù)似然函數(shù)L(0|X)的值,即:
記:
證明:已知:
然后根據(jù)貝葉斯統(tǒng)計先驗后驗的函數(shù)關(guān)系式得到:
可以得知,在大樣本以及0均勻分布的前提下,其中p(x|0)是已經(jīng)觀測到的X的密度,而p(y|x,0)是給定已經(jīng)觀測到的數(shù)據(jù)后缺失數(shù)據(jù)的密度:
記:
則:
從而:
進而得到:
所以:
由M步一直求極大化過程:
可知Q一直在增大,有第二步的定理1得到:
這里可以知道在EM算法在E步和M步的交替運算下,似然函數(shù)是不斷地變大的,我們就可以認為估計的參數(shù)序列最終會收斂到極大似然估計.
如果在每次迭代中,都是通過求似然函數(shù)的極大似然估計,選擇最大化的0(k+1)來代替0,這樣就構(gòu)成了EM算法,大部分時候極大似然函數(shù)都是有顯式表達式,但是不是總是這樣,所以有時候會有廣義EM算法(GEM),增大Q的哪一步也增大了對數(shù)似然函數(shù).
這里我不加證明的給出,得到的收斂性結(jié)論主要是針對對數(shù)似然函數(shù)值給出的，而不是針對的估計序列的收斂性;而且在一般的情況下妖谴，我們用EM算法得到的估計值0(k)窿锉，只能保證收斂到似然函數(shù)的一個穩(wěn)定點,并不能其保證收斂到全局最大值點或者局部最大值點。
參考資料:
The EM algorithm 吳恩達
http://blog.csdn.net/zouxy09/article/details/8537620/
http://www.cnblogs.com/openeim/p/3921835.html
以及更多的人的幫助,謝謝他們,接下來將會進行后續(xù)的對于加速EM算法收斂的方法,感謝閱讀
