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