EM算法原理詳解

1.引言

以前我們討論的概率模型都是只含 觀測變量(observable variable ), 即這些變量都是可以觀測出來的，那么給定數據，可以直接使用極大似然估計的方法或者貝葉斯估計的方法；但是當模型含有 隱變量(latent variable) 的時候, 就不能簡單地使用這些估計方法。

如在 高斯混合和EM算法 中討論的高斯混合就是典型的含有隱變量的例子，已經給出EM算法在高斯混合模型中的運用，下面我們來討論一些原理性的東西。

2.Jensen 不等式

令 是值域為實數的函數，那么如果 ，則 就是一個 凸函數 ，如果自變量 x 是向量, 那么當函數的海森矩陣  是 半正定 時( ),  是凸函數，這是函數為凸函數的條件在向量輸入時的泛化。

如果 ，則稱 是 嚴格凸函數 ，對應的向量輸入時的泛化是 .

定理  令 是一個凸函數，令 是一個隨機變量，那么

當 時嚴格凸函數的時，當且僅當 以概率 1 成立的時， . 即當 時常量時，上面不等式的等號成立。

注意上面 E 是表示期望的意思，習慣上，在寫變量期望的時候，會把緊跟括號略去，即 .

用下面的圖對上面的定理作一個解釋：

這個圖中的實線代表凸函數 , 隨機變量 有 0.5 的概率取 a, 同樣以 0.5 的概率取 b, 所以 的期望位于a,b的正中間，即a,b的均值.

從圖中可以看出，在 y 軸上,  位于 之間，因為 是凸函數，則必如上圖所示，

所以很多情況下，許多人并去記憶這個不等式，而是記住上面的圖，這樣更容易理解。

注意 ：如果 是（嚴格）凹函數，即 使（嚴格）凸函數（即， ），那么Jensen不等式照樣成立，只不過不等號方向相反：

3.EM算法

假設在一個估計問題中有m個獨立樣本 ，根據這些數據，希望擬合出模型 的參數，那么對數似然函數：

這里， 是隱變量，如果 能夠被觀測出來，最大似然估計就會變得很容易，但是現在 觀測不出來，是隱變量。

在這種情況下，EM算法給出了一種很有效的最大似然估計的方法： 重復地構造 的下界（E步），然后最大化這個下界（M步） 。

對于每個 ，令 表示隱變量 的分布，即 ，考慮：

由（2）到（3）的推導用到了上面的 Jensen不等式 ，此時 是一個凹函數，因為 ，考慮上面關于 的分布 ，

正好是數量 的期望，由Jensen不等式可以得到：

由此可以從（2）推出（3）.

但是由于隱變量的存在，直接最大化 很困難！試想如果能讓 直接與它的下界相等，那么任何可以使 的下界增大的 ，也可以使 增大，所以自然就是選擇出使 的下界達到極大的參數 .

怎么樣才能使得 取得下界呢，即上面不等式取等號，關鍵在于隱變量 如何處理，下面就此討論。

現在，對于任意的分布 ，（3）給出了似然函數 的下界. 對于分布 到底是什么分布，可以有很多種選擇，到底該選擇哪一種呢？

在上面 討論Jensen不等式的時候可以看出，不等式中等號成立的條件是隨機變量變成“常量 ”，對于 要想取得下界值，必須要求

其中常數 c 與變量 無關，這很容易做到，我們選擇分布 的時候，滿足下面的條件即可：

由于 ，于是我們可以知道：

注意理解上面這個等式式子是如何得出來的！！

于是就可以把分布 設定為：在參數 下，給定 后， 的后驗分布。

這樣設定好隱變量的分布 之后， 就直接取其下界， 原來最大化似然函數 的問題轉換為最大化其下界，這就是E步！

在M步中，就是去調整參數 最大化上面提到的式子（3） .

不斷重復E步和M步就是EM算法：

重復迭代直至收斂{

}

我們如何知道 算法收斂 呢？

假如 和 是兩次連續迭代后的參數, 需要證明 .

正如上面所述，由于我們再選擇分布 時，選擇： ，于是：

參數 就是通過極大化上面右邊的式子得出，因此：

注意第不等式（4）來自于：

這個式子對于任意的 和 都成立，當然對于 和 也成立。對于不等式（5），因為 是通過如下極大化過程選出來的：

所以在 處，式子的值要比在 處式子的值要大！

式子（6）是通過上面討論過的方法選擇出合適的 使得Jensen不等式取等號！

因此， EM算法使得似然函數單調收斂 。在上面描述EM算法的時候，說是“重復迭代直至收斂”， 一個常用的檢查收斂的方法是 ：如果兩次連續迭代之后，似然函數 的值變化很小（在某個可容忍的范圍內），就EM算法中 的變化已經很慢，可以停止迭代了。

注意：如果定義：

從之前的推導，我們知道 . EM算法看作是關于函數 J 的梯度上升 ：E步是關于參數Q，M步是關于參數 .

4.高斯混合的修正

在 高斯混合和EM算法中，我們將EM算法用于優化求解高斯混合模型，擬合參數 和 .

E步：

這里 表示的是在分布 下， 取 的概率。

M步：考慮參數 ，最大化數值：

最大化求 ，對上面的式子關于 求偏導數：

令這個偏導數為0，求出 的更新方式：

這是在 高斯混合和EM算法中已經得出的結論。

再考慮如何更新參數 ,把只與 有關的項寫出來，發現只需要最大化：

因為， ，所有 的和為1，所以這是一個約束優化問題，參考 簡易解說拉格朗日對偶（Lagrange duality） ，構造拉格朗日函數：

其中 β 是拉格朗日乘子. 求偏導數：

令偏導數為0，得到：

即： 利用約束條件： ，得到： (注意這里用到： ).

于是可以得到參數 的更新規則：

關于參數 的更新規則，以及整個EM算法如何運用到高斯混合模型的優化，請參考：高斯混合和EM算法！

5.總結

所謂EM算法就是在含有隱變量的時候，把隱變量的分布設定為一個以觀測變量為前提條件的后驗分布，使得參數的似然函數與其下界相等，通過極大化這個下界來極大化似然函數，從避免直接極大化似然函數過程中因為隱變量未知而帶來的困難 ！ EM算法主要是兩步,E步選擇出合適的隱變量分布（一個以觀測變量為前提條件的后驗分布），使得參數的似然函數與其下界相等；M步：極大化似然函數的下界，擬合出參數.