EM演算法簡單總結

EM演算法也被稱為上帝的演算法，它常用於含有隱變數的概率模型中的極大似然估計。EM演算法稱為期望最大化演算法（Expectation Maximization Algorithm），由名字就可以看出，它的演算法思想很簡單，基本來說由兩步組成

1. E步：求期望（Expectation）
2. M步：求極大（Maximization）

EM演算法的由來

在含有隱變數的概率模型中，通常目標是極大化似然函數

因為似然函數含有未知變數並且有積分項，直接優化比較困難，因而我們採用一種迭代的方法求解，正是這種轉變產生了EM演算法。假設當前的參數估計值為，我們希望找到新的估計值使得變大，並逐步接近最大值。因而我們的優化目標可以轉化為最大化，因此

其中第（3）步計算利用了Jensen不等式。

Q函數的由來

對於上式，令

那麼，並且由上式可以得出，因此是的下界。由下圖可以了解各函數之間的關係，其實由圖也可以看出，如果目標函數不是凸函數，EM演算法不能保證找到全局最優解。

這樣，我們就可以通過最大化來間接地優化，即，則

則EM演算法可以轉化為極大化，它是EM演算法的核心。其實，稱為Q函數，定義為

它是完全數據（觀測變數，隱變數）的對數似然函數關於在給定觀測數據和當前參數下對未觀測數據的條件概率分布的期望。

EM演算法的步驟

至此，可以給出EM演算法的步驟：

1. 選擇合適的初始參數，開始迭代（EM演算法是初值敏感的）

2. E步：記為第i次參數的估計值，計算第i+1次的Q函數的值
3. M步：求使極大化的參數，確定新的參數估計值

4. 重複（2），（3）直到收斂，收斂條件一般為或者

參考

• 《統計學習方法》李航

推薦閱讀：