機器學習十大算法之一：EM算法。能評得上十大之一，讓人聽起來覺得挺NB的。什么是NB啊，我們一般說某個人很NB，是因為他能解決一些別人解決不了的問題。神為什么是神，因為神能做很多人做不了的事。那么EM算法能解決什么問題呢？或者說EM算法是因為什么而來到這個世界上，還吸引了那么多世人的目光。

　　我希望自己能通俗地把它理解或者說明白，但是，EM這個問題感覺真的不太好用通俗的語言去說明白，因為它很簡單，又很復雜。簡單在于它的思想，簡單在于其僅包含了兩個步驟就能完成強大的功能，復雜在于它的數學推理涉及到比較繁雜的概率公式等。如果只講簡單的，就丟失了EM算法的精髓，如果只講數學推理，又過于枯燥和生澀，但另一方面，想把兩者結合起來也不是件容易的事。所以，我也沒法期待我能把它講得怎樣。希望各位不吝指導。

　　EM算法 ：

　　相信大家對似然函數已經手到擒來了。那么我們就來看看高深的。

　　一個概率模型有時候既含有觀察變量，有含有隱變量。如果只有觀察變量那么我們可以用最大似然法（或者貝葉斯）估計未知參數，但是如果還含有隱變量就不能如此簡單解決了。這時候就需要EM算法。

　　大家可能對這種問題不是很明白，也不太明白隱變量是什么意思。我舉個例子（引用統計學習方法的例子）：

　　有3枚硬幣分別記為A，B，C，并且出現正面概率分別為p ，q ，k.規則如下：先拋硬幣A，如果為正面就選擇B，否則選擇C，然后再將選擇的硬幣（B或者C拋），然后觀測結果。正面為1 反面為0.獨立重復實驗10次結果如下：1，1，1，0，0，0，1，1，1，0。我們并不知道拋A硬幣時為正面還是方面，只知道最后的結果，問如何估計p，q，k的值？

　　如果我們知道拋的是哪個硬幣就可以使用最大似然估計來估計這些參數，但是我們不知道。因為有p的原因，所以無法估計，這個p就是隱變量

　　log（Θ）=Σlogp（x;Θ）=Σlogp（x，p;Θ），Θ就是要求的q，k 待定參數，x為觀測數據，因為這個p導致我們無法求解MaxΣlogp（x;Θ）。

　　還比如說調查 男生 女生身高的問題。身高肯定是服從高斯分布。以往我們可以通過對男生抽樣進而求出高斯分布的參數，女生也是，但是如果我們只能知道某個人的高度，卻不能知道他是男生或者女生（隱含變量），這時候就無法使用似然函數估計了。這個時候就可以使用EM方法。

　　分為E和M兩步：

　　E步：

　　首先通過隨機賦值一個我們要求的參數，然后求出另外一個隱含參數的后驗概率。這是期望計算過程，我們首先通過隨便賦予模型參數的初始值p，q，k，求出各個數據到模型的結果。

　　M步

　　用求出來的隱含參數的后驗概率進行對傳統的似然函數估計，對要求參數進行修正。迭代直到前后兩次要求的參數一樣為止

　　其實可以這么簡單理解：就是在無監督聚類的時候，我們不知道模型的參數（比如為高斯分布），這時候我們就隨便賦值給模型的待定參數（u和ó）。然后我們就可以計算出各個數據分別屬于那一類。然后我們用這些分類好的數據重新估計u和ó。

　　EM算法推導

　　假設我們有一個樣本集{x（1），…，x（m）}，包含m個獨立的樣本。但每個樣本i對應的類別z（i）是未知的（相當于聚類），也即隱含變量。故我們需要估計概率模型p（x，z）的參數θ，但是由于里面包含隱含變量z，所以很難用最大似然求解，但如果z知道了，那我們就很容易求解了。

　　對于參數估計，我們本質上還是想獲得一個使似然函數最大化的那個參數θ，現在與最大似然不同的只是似然函數式中多了一個未知的變量z，見下式（1）。也就是說我們的目標是找到適合的θ和z讓L（θ）最大。那我們也許會想，你就是多了一個未知的變量而已啊，我也可以分別對未知的θ和z分別求偏導，再令其等于0，求解出來不也一樣嗎？

　　本質上我們是需要最大化（1）式（對（1）式，我們回憶下聯合概率密度下某個變量的邊緣概率密度函數的求解，注意這里z也是隨機變量。對每一個樣本i的所有可能類別z求等式右邊的聯合概率密度函數和，也就得到等式左邊為隨機變量x的邊緣概率密度），也就是似然函數，但是可以看到里面有“和的對數”，求導后形式會非常復雜（自己可以想象下log（f1（x）+ f2（x）+ f3（x）+…）復合函數的求導），所以很難求解得到未知參數z和θ。那OK，我們可否對（1）式做一些改變呢？我們看（2）式，（2）式只是分子分母同乘以一個相等的函數，還是有“和的對數”啊，還是求解不了，那為什么要這么做呢？咱們先不管，看（3）式，發現（3）式變成了“對數的和”，那這樣求導就容易了。我們注意點，還發現等號變成了不等號，為什么能這么變呢？這就是Jensen不等式的大顯神威的地方。

　　Jensen不等式：

　　設f是定義域為實數的函數，如果對于所有的實數x。如果對于所有的實數x，f（x）的二次導數大于等于0，那么f是凸函數。當x是向量時，如果其hessian矩陣H是半正定的，那么f是凸函數。如果只大于0，不等于0，那么稱f是嚴格凸函數。

　　Jensen不等式表述如下：

　　如果f是凸函數，X是隨機變量，那么：E［f（X）］》=f（E［X］）

　　特別地，如果f是嚴格凸函數，當且僅當X是常量時，上式取等號。

　　如果用圖表示會很清晰：

　　圖中，實線f是凸函數，X是隨機變量，有0.5的概率是a，有0.5的概率是b。（就像擲硬幣一樣）。X的期望值就是a和b的中值了，圖中可以看到E［f（X）］》=f（E［X］）成立。

　　當f是（嚴格）凹函數當且僅當-f是（嚴格）凸函數。

　　Jensen不等式應用于凹函數時，不等號方向反向。

　　回到公式（2），因為f（x）=log x為凹函數（其二次導數為-1/x2《0）。

　?。?）式中的期望，（考慮到E（X）=∑x*p（x），f（X）是X的函數，則E（f（X））=∑f（x）*p（x）），又，所以就可以得到公式（3）的不等式了（若不明白，請拿起筆，呵呵）：

　　OK，到這里，現在式（3）就容易地求導了，但是式（2）和式（3）是不等號啊，式（2）的最大值不是式（3）的最大值啊，而我們想得到式（2）的最大值，那怎么辦呢？

　　現在我們就需要一點想象力了，上面的式（2）和式（3）不等式可以寫成：似然函數L（θ）》=J（z，Q），那么我們可以通過不斷的最大化這個下界J，來使得L（θ）不斷提高，最終達到它的最大值。

　　見上圖，我們固定θ，調整Q（z）使下界J（z，Q）上升至與L（θ）在此點θ處相等（綠色曲線到藍色曲線），然后固定Q（z），調整θ使下界J（z，Q）達到最大值（θt到θt+1），然后再固定θ，調整Q（z）……直到收斂到似然函數L（θ）的最大值處的θ*。這里有兩個問題：什么時候下界J（z，Q）與L（θ）在此點θ處相等？為什么一定會收斂？

　　首先第一個問題，在Jensen不等式中說到，當自變量X是常數的時候，等式成立。而在這里，即：

　　再推導下，由于（因為Q是隨機變量z（i）的概率密度函數），則可以得到：分子的和等于c（分子分母都對所有z（i）求和：多個等式分子分母相加不變，這個認為每個樣例的兩個概率比值都是c），則：

　　至此，我們推出了在固定參數θ后，使下界拉升的Q（z）的計算公式就是后驗概率，解決了Q（z）如何選擇的問題。這一步就是E步，建立L（θ）的下界。接下來的M步，就是在給定Q（z）后，調整θ，去極大化L（θ）的下界J（在固定Q（z）后，下界還可以調整的更大）。

　　舉個例子：

　　假設我們有一個袋子，里面裝著白球和黑球，但是我們不知道他們分別有多少個，這時候需要我們估計每次取出一個球是白球的概率是多少？如何估計呢？ 可以通過連續有放回的從袋子里面取一百次，看看是白球還是黑球。假設取100次里面 白球占70次，黑球30次。設抽取是白球的概率為P。 那么一百次抽取的總概率為 p（x;p）

　　p（x;p）=p（x1，x2.。。。。。.x100;θ）=p（x1;θ）*p（x2;θ）。。。。。。。.p（x100;θ）

　　=p70*（1-p）30

　　那么這時候我們希望可以使這個概率最大。

　　求導：logp（x;p）=logp70*（1-p）30 另導數為0則可以求出p=0.7（同理可以用到連續變量里面，這時候就是概率密度函數的乘積so easy）

　　是不是很簡單，對！就是這么簡單！其實最大似然估計就是在給定一組數據和一個待定參數模型，如何確定這個模型未知參數，使得這個確定后的參數模型產生的已知數據概率最大。當然這里我只是舉了一個只有一個未知參數的估計方法，多個未知參數的做法是一樣的，就是求似然函數求導取最大值。其實并不是所有似然函數都可以求導的，當似然函數無法求導時就需要根據定義求使得L（θ）最大的θ。

　　舉個例子，以拋篩子為例：

　　.最大后驗估計 （MAP）：

　　最大后驗估計就是在原來的MLE的基礎上加上了先驗知識：

　　EM算法另一種理解

　　坐標上升法（Coordinate ascent）：

　　圖中的直線式迭代優化的路徑，可以看到每一步都會向最優值前進一步，而且前進路線是平行于坐標軸的，因為每一步只優化一個變量。

　　這猶如在x-y坐標系中找一個曲線的極值，然而曲線函數不能直接求導，因此什么梯度下降方法就不適用了。但固定一個變量后，另外一個可以通過求導得到，因此可以使用坐標上升法，一次固定一個變量，對另外的求極值，最后逐步逼近極值。對應到EM上，E步：固定θ，優化Q；M步：固定Q，優化θ；交替將極值推向最大。