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