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