EM算法
好了，重新回到上面那個身高分布估計的問題。現在，通過抽取得到的那100個男生的身高和已知的其身高服從高斯分布，我們通過最大化其似然函數，就可以得到了對應高斯分布的參數θ=[u, ∂]T了。那麼，對于我們學校的女生的身高分布也可以用同樣的方法得到了。
再回到例子本身，如果沒有“男的左邊，女的右邊，其他的站中間！”這個步驟，或者說我抽到這200個人中，某些男生和某些女生一見鐘情，已經好上了，糾纏起來了。咱們也不想那麼殘忍，硬把他們拉扯開。那現在這200個人已經混到一起了，這時候，你從這200個人（的身高）裡面随便給我指一個人（的身高），我都無法确定這個人（的身高）是男生（的身高）還是女生（的身高）。也就是說你不知道抽取的那200個人裡面的每一個人到底是從男生的那個身高分布裡面抽取的，還是女生的那個身高分布抽取的。用數學的語言就是，抽取得到的每個樣本都不知道是從哪個分布抽取的。
這個時候，對于每一個樣本或者你抽取到的人，就有兩個東西需要猜測或者估計的了，一是這個人是男的還是女的？二是男生和女生對應的身高的高斯分布的參數是多少？
隻有當我們知道了哪些人屬于同一個高斯分布的時候，我們才能夠對這個分布的參數作出靠譜的預測，例如剛開始的最大似然所說的，但現在兩種高斯分布的人混在一塊了，我們又不知道哪些人屬于第一個高斯分布，哪些屬于第二個，是以就沒法估計這兩個分布的參數。反過來，隻有當我們對這兩個分布的參數作出了準确的估計的時候，才能知道到底哪些人屬于第一個分布，那些人屬于第二個分布。
這就成了一個先有雞還是先有蛋的問題了。雞說，沒有我，誰把你生出來的啊。蛋不服，說，沒有我，你從哪蹦出來啊。（呵呵，這是一個哲學問題。當然了，後來科學家說先有蛋，因為雞蛋是鳥蛋進化的）。為了解決這個你依賴我，我依賴你的循環依賴問題，總得有一方要先打破僵局，說，不管了，我先随便整一個值出來，看你怎麼變，然後我再根據你的變化調整我的變化，然後如此疊代着不斷互相推導，最終就會收斂到一個解。這就是EM算法的基本思想了。
不知道大家能否了解其中的思想，我再來啰嗦一下。其實這個思想無處在不啊。
例如，小時候，老媽給一大袋糖果給你，叫你和你姐姐等分，然後你懶得去點糖果的個數，是以你也就不知道每個人到底該分多少個。咱們一般怎麼做呢？先把一袋糖果目測的分為兩袋，然後把兩袋糖果拿在左右手，看哪個重，如果右手重，那很明顯右手這代糖果多了，然後你再在右手這袋糖果中抓一把放到左手這袋，然後再感受下哪個重，然後再從重的那袋抓一小把放進輕的那一袋，繼續下去，直到你感覺兩袋糖果差不多相等了為止。呵呵，然後為了展現公平，你還讓你姐姐先選了。
EM 算法就是這樣，假設我們想估計知道 A 和 B 兩個參數，在開始狀态下二者都是未知的，但如果知道了 A 的資訊就可以得到 B 的資訊，反過來知道了 B 也就得到了 A 。可以考慮首先賦予 A 某種初值，以此得到 B 的估計值，然後從 B 的目前值出發，重新估計 A 的取值，這個過程一直持續到收斂為止。
EM的意思是“Expectation Maximization”，在我們上面這個問題裡面，我們是先随便猜一下男生（身高）的正态分布的參數：如均值和方差是多少。例如男生的均值是1米7，方差是0.1米（當然了，剛開始肯定沒那麼準），然後計算出每個人更可能屬于第一個還是第二個正态分布中的（例如，這個人的身高是1米8，那很明顯，他最大可能屬于男生的那個分布），這個是屬于Expectation一步。有了每個人的歸屬，或者說我們已經大概地按上面的方法将這200個人分為男生和女生兩部分，我們就可以根據之前說的最大似然那樣，通過這些被大概分為男生的n個人來重新估計第一個分布的參數，女生的那個分布同樣方法重新估計。這個是Maximization。然後，當我們更新了這兩個分布的時候，每一個屬于這兩個分布的機率又變了，那麼我們就再需要調整E步……如此往複，直到參數基本不再發生變化為止。
這裡把每個人（樣本）的完整描述看做是三元組yi={xi,zi1,zi2}，其中，xi是第i個樣本的觀測值，也就是對應的這個人的身高，是可以觀測到的值。zi1和zi2表示男生和女生這兩個高斯分布中哪個被用來産生值xi，就是說這兩個值标記這個人到底是男生還是女生（的身高分布産生的）。這兩個值我們是不知道的，是隐含變量。确切的說，zij在xi由第j個高斯分布産生時值為1，否則為0。例如一個樣本的觀測值為1.8，然後他來自男生的那個高斯分布，那麼我們可以将這個樣本表示為{1.8, 1, 0}。如果zi1和zi2的值已知，也就是說每個人我已經标記為男生或者女生了，那麼我們就可以利用上面說的最大似然算法來估計他們各自高斯分布的參數。但是它們未知，是以我們隻能用EM算法。
咱們現在不是因為那個惡心的隐含變量（抽取得到的每個樣本都不知道是從哪個分布抽取的）使得本來簡單的可以求解的問題變複雜了，求解不了嗎。那怎麼辦呢？人類解決問題的思路都是想能否把複雜的問題簡單化。好，那麼現在把這個複雜的問題逆回來，我假設已經知道這個隐含變量了，哎，那麼求解那個分布的參數是不是很容易了，直接按上面說的最大似然估計就好了。那你就問我了，這個隐含變量是未知的，你怎麼就來一個假設說已知呢？你這種假設是沒有根據的。呵呵，我知道，是以我們可以先給這個給分布弄一個初始值，然後求這個隐含變量的期望，當成是這個隐含變量的已知值，那麼現在就可以用最大似然求解那個分布的參數了吧，那假設這個參數比之前的那個随機的參數要好，它更能表達真實的分布，那麼我們再通過這個參數确定的分布去求這個隐含變量的期望，然後再最大化，得到另一個更優的參數，……疊代，就能得到一個皆大歡喜的結果了。
這時候你就不服了，說你老疊代疊代的，你咋知道新的參數的估計就比原來的好啊？為什麼這種方法行得通呢？有沒有失效的時候呢？什麼時候失效呢？用到這個方法需要注意什麼問題呢？呵呵，一下子抛出那麼多問題，搞得我适應不過來了，不過這證明了你有很好的搞研究的潛質啊。呵呵，其實這些問題就是數學家需要解決的問題。在數學上是可以穩當的證明的或者得出結論的。那咱們用數學來把上面的問題重新描述下。（在這裡可以知道，不管多麼複雜或者簡單的實體世界的思想，都需要通過數學工具進行模組化抽象才得以使用并發揮其強大的作用，而且，這裡面蘊含的數學往往能帶給你更多想象不到的東西，這就是數學的精妙所在啊）
三、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）。
（2）式中
的期望，（考慮到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)後，下界還可以調整的更大）。那麼一般的EM算法的步驟如下：
EM算法（Expectation-maximization）：
期望最大算法是一種從不完全資料或有資料丢失的資料集（存在隐含變量）中求解機率模型參數的最大似然估計方法。
EM的算法流程：
初始化分布參數θ；
重複以下步驟直到收斂：
E步驟：根據參數初始值或上一次疊代的模型參數來計算出隐性變量的後驗機率，其實就是隐性變量的期望。作為隐藏變量的現估計值：
M步驟：将似然函數最大化以獲得新的參數值：
這個不斷的疊代，就可以得到使似然函數L(θ)最大化的參數θ了。那就得回答剛才的第二個問題了，它會收斂嗎？
感性的說，因為下界不斷提高，是以極大似然估計單調增加，那麼最終我們會到達最大似然估計的最大值。理性分析的話，就會得到下面的東西：
具體如何證明的，看推導過程參考：Andrew Ng《The EM algorithm》
http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006936.html
四、EM算法另一種了解
坐标上升法（Coordinate ascent）：
圖中的直線式疊代優化的路徑，可以看到每一步都會向最優值前進一步，而且前進路線是平行于坐标軸的，因為每一步隻優化一個變量。
這猶如在x-y坐标系中找一個曲線的極值，然而曲線函數不能直接求導，是以什麼梯度下降方法就不适用了。但固定一個變量後，另外一個可以通過求導得到，是以可以使用坐标上升法，一次固定一個變量，對另外的求極值，最後逐漸逼近極值。對應到EM上，E步：固定θ，優化Q；M步：固定Q，優化θ；交替将極值推向最大。
五、EM的應用
EM算法有很多的應用，最廣泛的就是GMM混合高斯模型、聚類、HMM等等。具體可以參考JerryLead的cnblog中的Machine Learning專欄：
（EM算法）The EM Algorithm
混合高斯模型（Mixtures of Gaussians）和EM算法
K-means聚類算法
沒有雞和蛋的先後之争，因為他們都知道“沒有你就沒有我”。從此他們一起過上了幸福美好的生活。