機器學習十大算法之一：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不等式的大顯神威的地方。