期望最大化（EM）算法
原作者未知
EM是我一直想深入學習的算法之一，第一次聽說是在NLP課中的HMM那一節(jié)，為了解決HMM的參數(shù)估計問題，使用了EM算法。在之后的MT中的詞對齊中也用到了。在Mitchell的書中也提到EM可以用于貝葉斯網(wǎng)絡中。
下面主要介紹EM的整個推導過程。
1. Jensen不等式
????? 回顧優(yōu)化理論中的一些概念。設f是定義域為實數(shù)的函數(shù)，如果對于所有的實數(shù)x，，那么f是凸函數(shù)。當x是向量時，如果其hessian矩陣H是半正定的（），那么f是凸函數(shù)。如果或者，那么稱f是嚴格凸函數(shù)。
????? Jensen不等式表述如下：
????? 如果f是凸函數(shù)，X是隨機變量，那么
??????
????? 特別地，如果f是嚴格凸函數(shù)，那么當且僅當，也就是說X是常量。
????? 這里我們將簡寫為。
????? 如果用圖表示會很清晰：
??????
????? 圖中，實線f是凸函數(shù)，X是隨機變量，有0.5的概率是a，有0.5的概率是b。（就像擲硬幣一樣）。X的期望值就是a和b的中值了，圖中可以看到成立。
????? 當f是（嚴格）凹函數(shù)當且僅當-f是（嚴格）凸函數(shù)。
????? Jensen不等式應用于凹函數(shù)時，不等號方向反向，也就是。
2. EM算法
????? 給定的訓練樣本是，樣例間獨立，我們想找到每個樣例隱含的類別z，能使得p(x,z)最大。p(x,z)的最大似然估計如下：
??????
????? 第一步是對極大似然取對數(shù)，第二步是對每個樣例的每個可能類別z求聯(lián)合分布概率和。但是直接求一般比較困難，因為有隱藏變量z存在，但是一般確定了z后，求解就容易了。
????? EM是一種解決存在隱含變量優(yōu)化問題的有效方法。竟然不能直接最大化，我們可以不斷地建立的下界（E步），然后優(yōu)化下界（M步）。這句話比較抽象，看下面的。
????? 對于每一個樣例i，讓表示該樣例隱含變量z的某種分布，滿足的條件是。（如果z是連續(xù)性的，那么是概率密度函數(shù)，需要將求和符號換做積分符號）。比如要將班上學生聚類，假設隱藏變量z是身高，那么就是連續(xù)的高斯分布。如果按照隱藏變量是男女，那么就是伯努利分布了。
可以由前面闡述的內(nèi)容得到下面的公式：
??????
????? （1）到（2）比較直接，就是分子分母同乘以一個相等的函數(shù)。（2）到（3）利用了Jensen不等式，考慮到是凹函數(shù)（二階導數(shù)小于0），而且
??????
????? 就是的期望（回想期望公式中的Lazy Statistician規(guī)則）
| ????? 設Y是隨機變量X的函數(shù)（g是連續(xù)函數(shù)），那么 ????? （1） X是離散型隨機變量，它的分布律為，k=1,2,…。若絕對收斂，則有 ?????? ????? （2） X是連續(xù)型隨機變量，它的概率密度為，若絕對收斂，則有 ?????? |
????? 對應于上述問題，Y是，X是，是，g是到的映射。這樣解釋了式子（2）中的期望，再根據(jù)凹函數(shù)時的Jensen不等式：
??????
可以得到（3）。
????? 這個過程可以看作是對求了下界。對于的選擇，有多種可能，那種更好的？假設已經(jīng)給定，那么的值就決定于和了。我們可以通過調(diào)整這兩個概率使下界不斷上升，以逼近的真實值，那么什么時候算是調(diào)整好了呢？當不等式變成等式時，說明我們調(diào)整后的概率能夠等價于了。按照這個思路，我們要找到等式成立的條件。根據(jù)Jensen不等式，要想讓等式成立，需要讓隨機變量變成常數(shù)值，這里得到：
??????
????? c為常數(shù)，不依賴于。對此式子做進一步推導，我們知道，那么也就有，（多個等式分子分母相加不變，這個認為每個樣例的兩個概率比值都是c），那么有下式：
??????
????? 至此，我們推出了在固定其他參數(shù)后，的計算公式就是后驗概率，解決了如何選擇的問題。這一步就是E步，建立的下界。接下來的M步，就是在給定后，調(diào)整，去極大化的下界（在固定后，下界還可以調(diào)整的更大）。那么一般的EM算法的步驟如下：
| 循環(huán)重復直到收斂 { ????? （E步）對于每一個i，計算 ?????????????????? ????? （M步）計算 ?????????????????? |
????? 那么究竟怎么確保EM收斂？假定和是EM第t次和t+1次迭代后的結果。如果我們證明了，也就是說極大似然估計單調(diào)增加，那么最終我們會到達最大似然估計的最大值。下面來證明，選定后，我們得到E步
??????
????? 這一步保證了在給定時，Jensen不等式中的等式成立，也就是
??????
????? 然后進行M步，固定，并將視作變量，對上面的求導后，得到，這樣經(jīng)過一些推導會有以下式子成立：
??????
????? 解釋第（4）步，得到時，只是最大化，也就是的下界，而沒有使等式成立，等式成立只有是在固定，并按E步得到時才能成立。
????? 況且根據(jù)我們前面得到的下式，對于所有的和都成立
??????
????? 第（5）步利用了M步的定義，M步就是將調(diào)整到，使得下界最大化。因此（5）成立，（6）是之前的等式結果。
????? 這樣就證明了會單調(diào)增加。一種收斂方法是不再變化，還有一種就是變化幅度很小。
????? 再次解釋一下（4）、（5）、（6）。首先（4）對所有的參數(shù)都滿足，而其等式成立條件只是在固定，并調(diào)整好Q時成立，而第（4）步只是固定Q，調(diào)整，不能保證等式一定成立。（4）到（5）就是M步的定義，（5）到（6）是前面E步所保證等式成立條件。也就是說E步會將下界拉到與一個特定值（這里）一樣的高度，而此時發(fā)現(xiàn)下界仍然可以上升，因此經(jīng)過M步后，下界又被拉升，但達不到與另外一個特定值一樣的高度，之后E步又將下界拉到與這個特定值一樣的高度，重復下去，直到最大值。
????? 如果我們定義
??????
????? 從前面的推導中我們知道，EM可以看作是J的坐標上升法，E步固定，優(yōu)化，M步固定優(yōu)化。
3. 重新審視混合高斯模型
????? 我們已經(jīng)知道了EM的精髓和推導過程，再次審視一下混合高斯模型。之前提到的混合高斯模型的參數(shù)和計算公式都是根據(jù)很多假定得出的，有些沒有說明來由。為了簡單，這里在M步只給出和的推導方法。
E步很簡單，按照一般EM公式得到：
??????
????? 簡單解釋就是每個樣例i的隱含類別為j的概率可以通過后驗概率計算得到。
????? 在M步中，我們需要在固定后最大化最大似然估計，也就是
??????
????? 這是將的k種情況展開后的樣子，未知參數(shù)和。
????? 固定和，對求導得
??????
????? 等于0時，得到
??????
????? 這就是我們之前模型中的的更新公式。
????? 然后推導的更新公式。看之前得到的
??????
????? 在和確定后，分子上面的一串都是常數(shù)了，實際上需要優(yōu)化的公式是：
??????
????? 需要知道的是，還需要滿足一定的約束條件就是。
????? 這個優(yōu)化問題我們很熟悉了，直接構造拉格朗日乘子。
??????
????? 還有一點就是，但這一點會在得到的公式里自動滿足。
????? 求導得，
??????
????? 等于0，得到
??????
????? 也就是說再次使用，得到
??????
????? 這樣就神奇地得到了。
????? 那么就順勢得到M步中的更新公式：
??????
??????的推導也類似，不過稍微復雜一些，畢竟是矩陣。結果在之前的混合高斯模型中已經(jīng)給出。
4. 總結
????? 如果將樣本看作觀察值，潛在類別看作是隱藏變量，那么聚類問題也就是參數(shù)估計問題，只不過聚類問題中參數(shù)分為隱含類別變量和其他參數(shù)，這猶如在x-y坐標系中找一個曲線的極值，然而曲線函數(shù)不能直接求導，因此什么梯度下降方法就不適用了。但固定一個變量后，另外一個可以通過求導得到，因此可以使用坐標上升法，一次固定一個變量，對另外的求極值，最后逐步逼近極值。對應到EM上，E步估計隱含變量，M步估計其他參數(shù)，交替將極值推向最大。EM中還有“硬”指定和“軟”指定的概念，“軟”指定看似更為合理，但計算量要大，“硬”指定在某些場合如K-means中更為實用（要是保持一個樣本點到其他所有中心的概率，就會很麻煩）。
????? 另外，EM的收斂性證明方法確實很牛，能夠利用log的凹函數(shù)性質(zhì)，還能夠想到利用創(chuàng)造下界，拉平函數(shù)下界，優(yōu)化下界的方法來逐步逼近極大值。而且每一步迭代都能保證是單調(diào)的。最重要的是證明的數(shù)學公式非常精妙，硬是分子分母都乘以z的概率變成期望來套上Jensen不等式，前人都是怎么想到的。
????? 在Mitchell的Machine Learning書中也舉了一個EM應用的例子，明白地說就是將班上學生的身高都放在一起，要求聚成兩個類。這些身高可以看作是男生身高的高斯分布和女生身高的高斯分布組成。因此變成了如何估計每個樣例是男生還是女生，然后在確定男女生情況下，如何估計均值和方差，里面也給出了公式，有興趣可以參考。
《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀總結
以上是生活随笔為你收集整理的期望最大化（EM）算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 最大似然估计算法
- 下一篇： 最大后验概率估计算法