http://www.cnblogs.com/mindpuzzle/archive/2013/04/05/2998746.html

EM算法學習(Expectation Maximization Algorithm)

一、前言

      這是本人寫的第一篇部落格，是學習李航老師的《統計學習方法》書以及斯坦福機器學習課Andrew Ng的EM算法課後，對EM算法學習的介紹性筆記，如有寫得不恰當或錯誤的地方，請指出，并多多包涵，謝謝。另外本人數學功底不是很好，有些數學公式我會說明的仔細點的，如果數學基礎好，可直接略過。

二、基礎數學知識

      在正式介紹EM算法之前，先介紹推導EM算法用到的數學基礎知識，包括凸函數，Jensen不等式。

    1.凸函數

      對于凸函數，凹函數，如果大家學過高等數學，都應該知道，需要注意的是國内教材如同濟大學的《高等數學》的這兩個概念跟國外剛好相反，為了能更好的差別，本文章把凹凸函數稱之為上凸函數，下凸函數，具體定義如下：

上凸函數：函數f(x)滿足對定義域上任意兩個數a,b都有f[(a+b)/2] ≥ [f(a)+f(b)]/2

下凸函數：函數f(x)滿足對定義域上任意兩個數a,b都有f[(a+b)/2] ≤ [f(a)+f(b)]/2

更直覺的可以看圖2.1和2.2：

      可以清楚地看到圖2.1上凸函數中，f[(a+b)/2] ≥ [f(a)+f(b)]/2，而且不難發現，如果f(x)是上凸函數，那麼-f(x)是下凸函數。

      當a≠b時，f[(a+b)/2] > [f(a)+f(b)]/2成立，那麼稱f(x)為嚴格的上凸函數，等号成立的條件當且僅當a=b,下凸函數與其類似。

2.Jensen不等式

            有了上述凸函數的定義後，我們就能很清楚的Jensen不等式的含義，它的定義如下：

      如果f是上凸函數，X是随機變量，那麼f(E[X]) ≥ E[f(X)] 

特别地，如果f是嚴格上凸函數，那麼E[f(X)] = f(E[X])當且僅當p(X=E[X])，也就是說X是常量。

    那麼很明顯 log x 函數是上凸函數，可以利用這個性質。

有了上述的數學基礎知識後，我們就可以看具體的EM算法了。

三、EM算法所解決問題的例子

在推導EM算法之前，先引用《統計學習方法》中EM算法的例子：

例1. (三硬币模型) 假設有3枚硬币,分别記作A,B,C。這些硬币正面出現的機率分别為π，p和q。投币實驗如下，先投A，如果A是正面，即A=1，那麼選擇投B；A=0，投C。最後，如果B或者C是正面，那麼y=1；是反面，那麼y=0；獨立重複n次試驗（n=10)，觀測結果如下： 1,1,0,1,0,0,1,0,1,1假設隻能觀測到投擲硬币的結果，不能觀測投擲硬币的過程。問如何估計三硬币正面出現的機率，即π，p和q的值。

  解：設随機變量y是觀測變量，則投擲一次的機率模型為

       有n次觀測資料Y，那麼觀測資料Y的似然函數為

       那麼利用最大似然估計求解模型解，即

      這裡将機率模型公式和似然函數代入（1）式中，可以很輕松地推出 (1)=> (2) => (3)，然後選取θ(π,p,q)，使得（3）式值最大，即最大似然。然後，我們會發現因為（3）中右邊多項式+符号的存在，使得（3）直接求偏導等于0或者用梯度下降法都很難求得θ值。

      這部分的難點是因為（3）多項式中+符号的存在，而這是因為這個三硬币模型中，我們無法得知最後得結果是硬币B還是硬币C抛出的這個隐藏參數。那麼我們把這個latent 随機變量加入到 log-likelihood 函數中，得

      略看一下，好像很複雜，其實很簡單，請容我慢慢道來。首先是公式（4），這裡将zi做為隐藏變量，當z1為結果由硬币B抛出，z2為結果由硬币C抛出，不難發現

       注：一下Q中有些許漏了下标j,但不影響了解

       接下來公式說明（4）=> （5）（其中（5）中Q(z)表示的是關于z的某種分布，

），很直接，在P的分子分母同乘以Q(zi)。最後是（5）=>（6），到了這裡終于用到了第二節介紹的Jensen不等式，數學好的人可以很快發現，

就是

的期望值（如果不懂，可google期望公式并了解），

       且log是上凸函數，是以就可以利用Jensen不等式得出這個結論。因為我們要讓log似然函數l(θ)最大，那麼這裡就要使等号成立。根據Jensen不等式可得，要使等号成立，則要使

成立。

       再因為

，是以得

,c為常數，那麼

      這裡可以發現

      OK,到這裡，可以發現公式（6）中右邊多項式已經不含有“+”符号了，如果知道Q(z)的所有值，那麼可以容易地進行最大似然估計計算，但是Q的計算需要知道θ的值。這樣的話，我們是不是可以先對θ進行人為的初始化θ0，然後計算出Q的所有值Q1(在θ0固定的情況下，可在Q1取到公式（6）的極大值)，然後在對公式（6）最大似然估計，得出新的θ1值（在固定Q1的情況下，取到公式（6）的極大值），這樣又可以計算新的Q值Q1,然後依次疊代下去。答案當然是可以。因為Q1是在θ0的情況下産生的，可以調節公式（6）中θ值，使公式（6）的值再次變大，而θ值變了之後有需要調節Q使（6）等号成立，結果又變大，直到收斂（單調有界必收斂），如果到現在還不是很清楚，具體清晰更廣義的證明可以見下部分EM算法說明。

     ps:看到上述的橙黃色内容，如果大家懂得F函數的極大-極大算法的話，就可以知道其實它們是一碼事。

    另外對公式（6）進行求偏導等于0，求最大值，大家可以自己練習試試，應該很簡單的，這裡不做過多陳述。

    在《統計學習方法》書中，進行兩組具體值的計算

      （1）π0=0.5, p0=0.5, q0=0.5，疊代結果為π=0.5, p=0.6, q=0.5

      （2）π0=0.4, p0=0.6, q0=0.7，疊代結果為π=0.4064, p=0.5368, q=0.6432

    兩組值的最後結果不相同，這說明EM算法對初始值敏感，選擇不同的初值可能會有不同的結果，隻能保證參數估計收斂到穩定點。是以實際應用中常用的辦法就是選取多組初始值進行疊代計算，然後取結果最好的值。

     在進行下部分内容之前，還需說明下一個東西。在上面的舉例說明後，其實可以發現上述的解決方法跟一個簡單的聚類方法很像，沒錯，它就是K-means聚類(不懂的見百度百科關于K-means算法的說明）。K-means算法先假定k個中心，然後進行最短距離聚類，之後根據聚類結果重新計算各個聚類的中心點，一次疊代，是不是很像，而且K-means也是初始值敏感，是以其實K-means算法也包含了EM算法思想，隻是這邊EM算法中用P機率計算，而K-means直接用最短距離計算。是以EM算法可以用于無監督學習。在下一篇文章，我準備寫下典型的用EM算法的例子，高斯混合模型（GMM,Gaussian Mixture Model）。

 四、EM算法

1.模型說明

      考慮一個參數估計問題，現有

共n個訓練樣本，需有多個參數θ去拟合資料，那麼這個log似然函數是：

      可能因為θ中多個參數的某種關系（如上述例子中以及高斯混合模型中的3類參數），導緻上面的log似然函數無法直接或者用梯度下降法求出最大值時的θ值，那麼這時我們需要加入一個隐藏變量z，以達到簡化l(θ),疊代求解l(θ)極大似然估計的目的。

2.EM算法推導

    這小節會對EM算法進行具體推導，許多跟上面例子的解法推導是相同的，如果已經懂了，可以加速閱讀。首先跟“三硬币模型”一樣，加入隐變量z後，假設Q(z)是關于隐變量z的某種分布，那麼有如下公式：

    公式（7）是加入隐變量，（7）=>（8）是在

基礎上分子分母同乘以

，（8）=>（9）用到Jensen不等式（跟“三硬币模型”一樣），等号成立的條件是

，c是常數。再因為

，則有如下Q的推導：

    再一次重複說明，要使（9）等式成立，則

為yj,z的後驗機率。算出

後（9）就可以進行求偏導，以剃度下降法求得θ值，那麼又可以計算新的

值，依次疊代，EM算法就實作了。

EM算法（1）：

選取初始值θ0初始化θ，t=0

Repeat {

      E步：

      M步：

}直到收斂

　　3.EM算法收斂性證明

    當θ取到θt值時，求得

    那麼可得如下不等式：

    （10）=>（11）是因為Jensen不等式，因為等号成立的條件是θ為θt的時候得到的

，而現在

中的θ值為θt+1，是以等号不一定成立，除非θt+1=θt，

    （11）=>（12）是因為θt+1已經使得

取得最大值，那必然不會小于（12）式。

    是以l(θ)在疊代下是單調遞增的，且很容易看出l(θ)是有上界的（單調有界收斂），則EM算法收斂性得證。

      4.EM算法E步說明

   上述EM算法描述，主要是參考Andrew NG教授的講義，如果看過李航老師的《統計方法學》，會發現裡面的證明以及描述表明上有些許不同，Andrew NG教授的講義的說明（如上述）将隐藏變量的作用更好的展現出來，更直覺，證明也更簡單，而《統計方法學》中則将疊代之間θ的變化羅列的更為明确，也更加準确的描述了EM算法字面上的意思：每次疊代包含兩步：E步，求期望；M步，求極大化。下面列出《統計方法學》書中的EM算法，與上述略有不同：

EM算法（2）：

選取初始值θ0初始化θ，t=0

Repeat {

 E步：

M步：

}直到收斂

    (13)式中，Y={y1,y2,...,ym},Z={z1,z2,...,zm},不難看出将（9）式中兩個Σ對換，就可以得出（13）式，而（13）式即是關于分布z的一個期望值，而需要求這個期望公式，那麼要求出所有的EM算法（1）中E步的值，是以兩個表明看起來不同的EM算法描述其實是一樣的。

 五、小結

    EM算法的基本思路就已經理清，它計算是含有隐含變量的機率模型參數估計，能使用在一些無監督的聚類方法上。在EM算法總結提出以前就有該算法思想的方法提出，例如HMM中用的Baum-Welch算法就是。

     在EM算法的推導過程中，最精妙的一點就是（10）式中的分子分母同乘以隐變量的一個分布，而套上了Jensen不等式，是EM算法順利的形成。

 六、主要參考文獻

[1]Rabiner L, Juang B. An introduction to hidden markov Models. IEEE ASSP Magazine, January 1986，EM算法原文

[2]http://v.163.com/special/opencourse/machinelearning.html，Andrew NG教授的公開課中的EM視訊

[3]http://cs229.stanford.edu/materials.html, Andrew NG教授的講義，非常強大，每一篇都寫的非常精煉，易懂

[4]http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006936.html, 一個将Andrew NG教授的公開課以及講義了解非常好的部落格，并且我許多都是參考他的

[5]http://blog.csdn.net/abcjennifer/article/details/8170378, 一個浙大研一的女生寫的，裡面的部落格内容非常強大，csdn排名前300，ps:大學就開部落格，唉，我的大學四年大學就給了遊戲，玩，慚愧哈，導緻現在啥都不懂。

[6]李航.統計學習方法.北京：清華大學出版社，2012

下節預告：高斯混合模型（GMM,Gaussian Mixture Model）及例子，大家可以看看JerryLead的http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006924.html,寫得挺好，大部分翻譯自 Andrew NG教授的講義