EM算法（Expectation Maximization Algorithm）詳解

• 主要內容?
  
  • EM算法簡介
  • 預備知識?
    
    • 極大似然估計
    • Jensen不等式
  • EM算法詳解?
    
    • 問題描述
    • EM算法推導
    • EM算法流程
  • EM算法優缺點以及應用

---

1、EM算法簡介?
??EM算法是一種迭代優化策略，由于它的計算方法中每一次迭代都分兩步，其中一個為期望步（E步），另一個為極大步（M步），所以算法被稱為EM算法（Expectation Maximization Algorithm）。EM算法受到缺失思想影響，最初是為了解決數據缺失情況下的參數估計問題，其算法基礎和收斂有效性等問題在Dempster，Laird和Rubin三人于1977年所做的文章Maximum likelihood from incomplete data via the EM algorithm中給出了詳細的闡述。其基本思想是：首先根據己經給出的觀測數據，估計出模型參數的值；然后再依據上一步估計出的參數值估計缺失數據的值，再根據估計出的缺失數據加上之前己經觀測到的數據重新再對參數值進行估計，然后反復迭代，直至最后收斂，迭代結束。?
??EM算法作為一種數據添加算法，在近幾十年得到迅速的發展，主要源于當前科學研究以及各方面實際應用中數據量越來越大的情況下，經常存在數據缺失或者不可用的的問題，這時候直接處理數據比較困難，而數據添加辦法有很多種，常用的有神經網絡擬合、添補法、卡爾曼濾波法等等，但是EM算法之所以能迅速普及主要源于它算法簡單，穩定上升的步驟能非常可靠地找到“最優的收斂值”。隨著理論的發展，EM算法己經不單單用在處理缺失數據的問題，運用這種思想，它所能處理的問題更加廣泛。有時候缺失數據并非是真的缺少了，而是為了簡化問題而采取的策略，這時EM算法被稱為數據添加技術，所添加的數據通常被稱為“潛在數據”，復雜的問題通過引入恰當的潛在數據，能夠有效地解決我們的問題。

2、預備知識?
??介紹EM算法之前，我們需要介紹極大似然估計以及Jensen不等式。?
2.1 極大似然估計?
（1）舉例說明：經典問題——學生身高問題?
??我們需要調查我們學校的男生和女生的身高分布。 假設你在校園里隨便找了100個男生和100個女生。他們共200個人。將他們按照性別劃分為兩組，然后先統計抽樣得到的100個男生的身高。假設他們的身高是服從正態分布的。但是這個分布的均值和方差我們不知道，這兩個參數就是我們要估計的。記作。?
??問題：我們知道樣本所服從的概率分布的模型和一些樣本，需要求解該模型的參數。如圖1?

?
圖1
??我們已知的有兩個：樣本服從的分布模型、隨機抽取的樣本；我們未知的有一個：模型的參數。根據已知條件，通過極大似然估計，求出未知參數。總的來說：極大似然估計就是用來估計模型參數的統計學方法。?
（2）如何估計?
??問題數學化：設樣本集 ,其中 ?， 為概率密度函數，表示抽到男生 （的身高）的概率。由于100個樣本之間獨立同分布，所以我同時抽到這100個男生的概率就是他們各自概率的乘積，也就是樣本集 中各個樣本的聯合概率，用下式表示：?

??這個概率反映了，在概率密度函數的參數是 時，得到 這組樣本的概率。 我們需要找到一個參數 ，使得抽到 這組樣本的概率最大，也就是說需要其對應的似然函數 最大。滿足條件的 叫做 的最大似然估計量，記為?

（3）求最大似然函數估計值的一般步驟?
??首先，寫出似然函數：?

??然后，對似然函數取對數：?

??接著，對上式求導，令導數為0，得到似然方程；?
??最后，求解似然方程，得到的參數 即為所求。?
2.2 Jensen不等式 ?
??設 是定義域為實數的函數，如果對于所有的實數 ， 的二次導數大于等于0，那么 是凸函數。?
??Jensen不等式表述如下：如果 是凸函數， 是隨機變量，那么： 。當且僅當 是常量時，上式取等號。其中， 表示 的數學期望。?
??例如，圖2中，實線 是凸函數， 是隨機變量，有0.5的概率是 ，有0.5的概率是 。 的期望值就是 和 的中值了，圖中可以看到 成立。?
?? 注： ?
??1、Jensen不等式應用于凹函數時，不等號方向反向。當且僅當 是常量時，Jensen不等式等號成立。?
??2、關于凸函數，百度百科中是這樣解釋的——“對于實數集上的凸函數，一般的判別方法是求它的二階導數，如果其二階導數在區間上非負，就稱為凸函數（向下凸）”。關于函數的凹凸性，百度百科中是這樣解釋的——“中國數學界關于函數凹凸性定義和國外很多定義是反的。國內教材中的凹凸，是指曲線，而不是指函數，圖像的凹凸與直觀感受一致，卻與函數的凹凸性相反。只要記住“函數的凹凸性與曲線的凹凸性相反”就不會把概念搞亂了”。關于凹凸性這里，確實解釋不統一，博主暫時以函數的二階導數大于零定義凸函數，此處不會過多影響EM算法的理解，只要能夠確定何時 或者 就可以。?
?
圖2

3、EM算法詳解?
3.1 問題描述?
??我們目前有100個男生和100個女生的身高，共200個數據，但是我們不知道這200個數據中哪個是男生的身高，哪個是女生的身高。假設男生、女生的身高分別服從正態分布，則每個樣本是從哪個分布抽取的，我們目前是不知道的。這個時候，對于每一個樣本，就有兩個方面需要猜測或者估計： 這個身高數據是來自于男生還是來自于女生？男生、女生身高的正態分布的參數分別是多少？EM算法要解決的問題正是這兩個問題。如圖3：?

?
圖3
3.2 EM算法推導 ?
??樣本集 ，包含 個獨立的樣本；每個樣本 對應的類別 是未知的（即上文中每個樣本屬于哪個分布是未知的）；我們需要估計概率模型 的參數 ，即需要找到適合的 和 讓 最大。根據上文 2.1 極大似然估計 中的似然函數取對數所得 ，可以得到如下式：?

其中，(1)式是根據 的邊緣概率計算得來，(2)式是由(1)式分子分母同乘一個數得到，(3)式是由(2)式根據Jensen不等式得到。?
??這里簡單介紹一下(2)式到(3)式的轉換過程：由于 為 的期望，且 為凹函數，根據Jensen不等式（當 是凸函數時， 成立；當 是凹函數時， 成立）可由(2)式得到(3)式。此處若想更加詳細了解，可以參考博客 the EM algorithm 。?
??上述過程可以看作是對 （即 ）求了下界。對于 的選擇，有多種可能，那么哪種更好呢？假設 已經給定，那么 的值就取決于 和 了。我們可以通過調整這兩個概率使下界不斷上升，以逼近 的真實值，那么什么時候算是調整好了呢？當不等式變成等式時，說明我們調整后的概率能夠等價于 了。按照這個思路，我們要找到等式成立的條件。根據Jensen不等式，要想讓等式成立，需要讓隨機變量變成常數值，這里得到：?
為常數，不依賴于 。對此式做進一步推導：由于 ，則有 （多個等式分子分母相加不變，則認為每個樣例的兩個概率比值都是 ），因此得到下式：?

??至此，我們推出了在固定其他參數 后， 的計算公式就是后驗概率，解決了 如何選擇的問題。這一步就是E步，建立 的下界。接下來的M步，就是在給定 后，調整 ，去極大化 的下界（在固定 后，下界還可以調整的更大）。這里讀者可以參考文章 EM算法 。?
3.3 EM算法流程 ?
??初始化分布參數 ； 重復E、M步驟直到收斂：?
??E步驟：根據參數 初始值或上一次迭代所得參數值來計算出隱性變量的后驗概率（即隱性變量的期望），作為隱性變量的現估計值：?

??M步驟：將似然函數最大化以獲得新的參數值：?

4、EM算法優缺點以及應用?
??優點：簡介中已有介紹，這里不再贅述。?
??缺點：對初始值敏感：EM算法需要初始化參數，而參數的選擇直接影響收斂效率以及能否得到全局最優解。?
??EM算法的應用：k-means算法是EM算法思想的體現，E步驟為聚類過程，M步驟為更新類簇中心。GMM（高斯混合模型）也是EM算法的一個應用，感興趣的小伙伴可以查閱相關資料。

總結

以上是生活随笔為你收集整理的EM算法（Expectation Maximization Algorithm）详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。