em演算法極大似然估計

A. （十）EM演算法

 EM演算法的英文全稱是 Expectation Maximization Algorithm——期望極大化演算法 ，它採用迭代的方式逼近帶隱變數的似然函數。通過對似然函數的一個下界求偏導，得到每一步參數估計的過程。
 這個名稱由於缺乏作用對象，讓人一頭霧水。這里的期望是什麼？為什麼我們要極大化這個期望，我們試圖優化什麼？
 這里的期望的含義其實是針對 極大似然估計 中的 似然函數 來說的，這里的期望就是似然函數的一個 下界 ，我們的目的是求這樣一個期望: 這個下界是根據 詹森不等式(Jensen's inequality） 放縮得到的，為什麼要放縮呢？因為我們試圖找出一個下界，極大化這個帶參數的下界之後，可以無限近似於似然函數。你想，如果這個做法ok的話，意味著什麼？意味著我們可以通過這個過程找出極大似然估計或最大後驗估計的參數近似解。這也意味著我們可以搞一個迭代法來得到一個近似解。但是即便我說的天花亂墜，這個下界要是不收斂那也白搭。而下界要收斂必須滿足兩個條件：
 1.這個下界的取值要單調遞增（因為每回迭代的結果要比上一次的取值更大）
 2.這個下界必須有上界(這個上界就是對數似然函數，且這一點可以由詹森不等式保證，這個也是EM的核心)
大白話就是 單調有界必有極限 。

我們來證明一下它確實是收斂的。
 首先，在極大似然估計中，我們的目的是根據手頭上的 個樣本，最大化 後，將參數 估計出來；引入對數： ;此時引入輔助變數 ;我們的對數似然函數就變成了：

設置變分函數： ;那麼：

根據琴生不等式,對數函數為凸函數(因為 ：等號在 為常數時取到)：

上面的這個下界，就是用來逼近原對數似然函數的，這里我們已經證明了演算法收斂的一個條件， 有界性 ；但是在繼續進行下一步的時候，我們還有一個問題沒搞清楚，那就是變分函數 的具體形式,實際上，我們可以通過琴生不等式等號成立的條件導出我們要的這個變分函數q。
令 為常數：
接著我們代入變分函數 的形式，定義這個下界的第一項：

定義下界的第二項：

對於第二項，我們看看隨著迭代步數的增大，它是否是遞增的，

我們將不同參數的 與 看作是兩個分布，那麼這個結果實際上是一個KL散度，它表徵兩個分布的相似度,其結果總是大於等於0的。
大於等於0的原因：

所以：

H為一個遞增的序列，那麼剩下的就是Q是否遞增了，基於前面提到的這個下界是有上界的，上界就是我們的對數似然函數。在這個前提下，現在我們只要證明，Q遞增是整個下界遞增的充分必要條件即可。
必要性：

當整個下界遞增，即：
那麼：
所以 單調遞增，必要性得證。
充分性：
因為：
前面已經證明：

又因為：

所以：

即，在 遞增的情況下，整個下界遞增。
充分性得證。
證畢。

 這個演算法名稱里提及的期望究竟是什麼？
我們說了這么多，實際都是要做一件事，那就是：

由於前面證明過整個下界有界。且只要找到讓第i次迭代的Q函數最大的 作為下一次迭代的參數，我們就可以讓Q遞增，讓演算法收斂。
我們來看看Q的形式。

這就是為什麼叫期望最大演算法的原因。

 我們以概率PCA，來展開EM的應用：
 當然這里的應用只涉及變分函數已知情況下的應用，並不涉及廣義EM的內容，日後看完文獻在來嘮嘮廣義EM，AVE，GAN等內容。
 我們先來算一下PPCA的EM期望的形式：

在 概率PCA 中，我們有提到：


所以：


所以期望裡面是這個式子：

我們的目的是要估計出 和 ;那麼我們分別對它們求偏導:

所以：


因為：

代入偏導中

所以：

我們偏導得到的結果就是：

我們會發現我們還有兩個估計量沒解決，一個是一階估計量 ,另一個是二階估計量
在概率PCA中，我們提到過：

那麼我們就有了一階估計量：

二階估計量可以通過簡單的計算得到：

剩下的代入即可.

結果展示：

B. EM演算法有什麼用

EM演算法是求含有隱變數的極大似然估計，可以用於包含隱變數的參數估計

C. EM演算法詳解

作為N大機器學習方法的一員，EM演算法在各種書籍、博客、網上視頻上被描述或者介紹，每次看完總感覺很多地方含糊不清，不能讓一個初學者（有一定統計概率基礎）接受。最近再B站上，看到 徐亦達老師的課程 ，EM演算法這塊講解易於理解和接受，再結合PRML一書的關於混合模型和EM章節內容，對整個EM演算法從具體的原理上面有了更深入的理解。
在下文中，更多的是通過公式推導和一些文字說明來梳理EM演算法，盡量做到大家一看就明白。

極大似然估計是概率統計中，估計模型參數的一種方法，如果對似然概念以及極大似然估計的概念不理解，可參考維基網路 https://zh.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E4%BC%BC%E7%84%B6%E4%BC%B0%E8%AE%A1

這里，我們給出一個一維高斯函數的例子。如圖1所示，一維空間裡面離散分布的樣本點其分布特點可以看成是一種高斯分布。那這些樣本的高斯分布函數參數怎麼求解呢？可以通過極大似然估計獲得。

假設我們獲取圖1中數據樣本集合為 ，其分布函數假設為一維高斯分布，即：

那所有數據的聯合概率,即似然函數為：

對等式兩邊求log，即log-likelihood：

分別對參數求導：

可以得到：

通過上述方法，就可以得到基於樣本數據和假設分布函數模型情況下，得到樣本數據的分布函數。

從圖2所示中，如果樣本數據分布式藍色點和橙色點的集合，如果依然用高斯分布去進行最大似然估計，得到的分布模型自然是不合適的。很顯然，樣本數據分布存在兩個密集區（藍色點和橙色點），如果能通過一種方法，確認樣本數據裡面的藍色點和橙色點，然後分別對藍色點集合進行一個高斯估計，對橙色點集進行另外一個高斯估計，兩個高斯混合到一起，是不是比單個高斯能更好的匹配樣本數據的分布情況。這種情況下的分布函數就是高斯混合模型。

這里我們先直接給出高斯混合模型的分布函數(多維)：

在圖2例子中，提到如果給每一個數據樣本能夠先進行分類，即確定屬於哪一個集中的簇中，就能比較容易的進行混合模型的求解。這說明了什麼呢？我們可以理解，原始樣本數據是不完全的（incomplete），引入一個K維的二值隨機變數 ，這個變數採用"1-of-K"的表示方法，即K維中，只有一維是1，其餘所有元素等於0。那麼每一個樣本數據，即有數據特徵 ，再匹配一個分配變數 ，就可以將圖2過程完整描述，即我們認為 和 聯合在一起才是完全的（complete）。

數學表示上，我們利用邊緣概率分布 和條件概率分布 定義聯合概率分布 .
的邊緣概率分布根據混合系數 進行賦值，即 ,使得邊緣概率分布是合法，那麼：

類似的，在給定 的一個特定的值，即針對某一簇的情況， 的條件概率分布是一個高斯分布，即

那麼根據貝葉斯公式得到高斯混合模型：

由於我們只能觀察樣本數據 ,無法直接獲取每個數據的分配變數 ,可理解 為潛在變數（latent）
依據極大似然函數的求解方法，我們可以對高斯混合模型寫出數據的對數似然函數：

由於對數函數內部出現求和，這種情況是沒有辦法通過求導等於0的方式獲取估計參數的解析解的。這種情況下，就需要用到EM演算法，通過迭代方式獲取估計參數。下面我們先從一般性問題上進行EM演算法的理論描述，然後再利用EM演算法推導高斯混合模型的計算方法。

EM演算法叫做期望最大化方法，首先我們給出EM演算法一般性結論或者說步驟，其具體分為兩步，即E-step和M-step。

EM演算法的步驟，通過高斯混合模型可以直觀理解記憶。 是什麼意思呢，其含義是在給定數據樣本的情況下，潛在變數的概率情況。也就是說在高斯混合模型中，給定樣本數據，我們推測樣本屬於哪一個高斯簇的概率情況。在確定分配情況後，每一個簇都用高斯進行估計，衡量估計好還是不好，用期望形式表示。這樣可以幫助理解和記憶Q的定義。那EM演算法怎麼證明其收斂性呢？

我們要保證：

這樣每次迭代可以使得似然函數隨著參數變大，一直到似然函數不再增大或滿足其他終止條件止。

那怎麼保證呢？首先，利用貝葉斯公式有：

兩邊同時取log

然後兩邊同時用 求期望，可以得：

等式左邊 和 沒有關系， 是概率密度函數，積分是1，所以等式左邊依然是 .
等式右邊第一項就是E-step裡面的Q函數，第二項我們記做H函數，則：

要保證 ，首先 ，那麼是不是保證 滿足，就一定有 ？答案是肯定的。（說明一下，這裡面的H和Q函數都是關於 的函數，每一次迭代 是已知的，他不是變數）

那下面只要證明 就可以了。

因此可以得到 ，則整個EM演算法的收斂性證畢。

註：這里用到了Jessian不等式，如果函數是convex的，則有函數的期望大於期望的函數，即 .

上述EM演算法的證明，有一些技巧性，而這些技巧性有沒有一種是在已知結論基礎上硬湊的感覺呢，尤其是用 去求期望，就是為了去構造Q函數。那有沒有更好的解釋或者更為直觀的方式來得到相同的結論呢？答案是有的。

首先，仍然用到：

我們稍微變個型，假設一個概率密度函數 :

兩邊同時用 求期望：

其中等式右邊第一項，我們記做 ，可以稱為ELOB，EvidenceLowerBound，第二項是 和 的KL散度。

如圖4所示，當我固定參數 時候，ELOB就是關於 的泛函（只聽過沒學過，可理解為函數的函數），那ELOB的上界是什麼呢？那首先要理解KL散度，KL散度是衡量兩個概率分布之間的差異性，如果兩個分布沒有差異，則KL散度等於0，如果有差異則大於0，所以KL散度的最小值就是0，那ELOB的上界就是此刻的似然函數。

在EM演算法中，當前迭代時，參數 ，則對於E-step，我們需要使得ELOB最大，即KL散度為0，如圖5所示，其中 為 。此時，

對於M-Step，我們是需要得到新的估計參數，這個時候，固定 ,重新獲得ELOB的最大值，這個時候的ELOB是什麼樣的呢？

右邊第二項沒有參數 ，所以固定 最大化ELOB，就等於最大化第一項，而第一項是什麼呢？就是 函數。

如圖6所示，我們最大化 函數，也就是最大化此次迭代的ELOB。在新的參數下， ，此刻 不變，所以和新的 在沒有達到局部（或者全局）極大值的情況下，是兩個不同的概率分布，即二者KL散度是大於0的，那此刻的似然函數等於此刻的KL散度加上此刻的ELOB，自然是有 。

從ELOB和KL散度的層面可以更好的理解EM演算法的迭代過程。

PRML一書中，有圖7所示的示意圖，能比較形象的說明，EM演算法的迭代過程。

圖7中，紅色曲線表示(不完整數據)對數似然函數，它的最大值是我們想要得到的。我們首先選擇某個初始的參數值 ,然後在第一個E步驟中,我們計算潛在變數上的後驗概率分布,得到了 的一個更小的下界，它的值等於在 處的對數似然函數值，用藍色曲線表示。注意，下界與對數似然函數在 處以切線的方式連接，因此兩條曲線的梯度相同。這個界是一個凹函數，對於指數族分布的混合分布來說，有唯一的最大值。在M步驟中,下界被最大化，得到了新的值 ,這個值給出了比 處更大的對數似然函數值。接下來的E步驟構建了一個新的下界,它在 處與對數似然函數切線連接,用綠色曲線表示。以這樣的方式不停迭代，直到滿足條件。

了解了EM演算法，我們來詳細推導高斯混合模型的E步和M步的內容。這一部分內容來自徐亦達老師的課件。由於公式太多了，我就放一些截圖，供大家一起學習和參考。

徐亦達老師的課件在： https://github.com/roboticcam/machine-learning-notes/blob/master/em.pdf

後續關於EM演算法的應用會舉例以下幾方面內容
(1)Kmeans和高斯混合模型
(2)EM演算法應用之貝葉斯線性回歸
(3)EM演算法應用之PLSA
(4)EM演算法應用之缺失數據參數估計問題

D. 最大似然函數和EM 演算法

在 數理統計學 中， 似然函數 是一種關於 統計模型 中的 參數 的 函數 ，表示模型參數中的 似然性 。

似然函數在 統計推斷 中有重大作用，如在 最大似然估計 和 費雪信息 之中的應用等等。「似然性」與「或然性」或「 概率 」意思相近，都是指某種事件發生的可能性，但是在 統計學 中，「似然性」和「或然性」或「概率」又有明確的區分。

概率 用於在已知一些參數的情況下，預測接下來的觀測所得到的結果，而

似然性 則是用於在已知某些觀測所得到的結果時，對有關事物的性質的參數進行估計。

最大似然估計你可以把它看作是一個反推。多數情況下我們是根據已知條件來推算結
果，而最大似然估計是已經知道了結果，然後尋求使該結果出現的可能性最大的條件，以此作為估計值。

極大似然估計，只是一種概率論在統計學的應用，它是參數估計的方法之一。說的是已知某個隨機樣本滿足某種概率分布，但是其中具體的參數不清楚，參數估計就是通過若干次試驗，觀察其結果，利用結果推出參數的大概值。最大似然估計是建立在這樣的思想上：已知某個參數能使這個樣本出現的概率最大，我們當然不會再去選擇其他小概率的樣本，所以乾脆就把這個參數作為估計的真實值。

求最大似然函數估計值的一般步驟：

（1）寫出似然函數；

（2）對似然函數取對數，並整理；

（3）求導數，令導數為0，得到似然方程；

（4）解似然方程，得到的參數即為所求；

背景是數學之美的聚類的情況下，
首先，根據現有模型，計算各個觀測數據輸入到模型中的計算結果，這個過程稱為期望值計算過程（Expectation），或E過程；接下來，重新計算模型的參數，以最大化期望值。在上面的例子中，我們最大化D和 -d ，這個過程稱為最大化的過程（Maximization），或 M 過程。這列演算法都成為EM演算法。

大西瓜：它是一種迭代式的方法，其基本思法是：若參數 s 已知，則可根據訓練數據推斷出最優隱變數 Z 的值（E 步）；反之，若 Z 的值已知，則可方便地對參數 s 做極大似然估計（M 步）。

EM 演算法還包括：隱馬爾可夫模型的訓練方法Baum-Welch 演算法，以及最大熵模型的訓練方法GIS演算法。
EM 演算法不一定保證全局最優解，如果目標函數是一個凸函數，那麼一定能保證最優解。所幸熵函數是一個凸函數，如果在 N 維空間以歐氏距離做度量，聚類中我們試圖優化的兩個函數也是凸函數。但是，很多情況下，包括文本分類中的餘弦距離都不能保證是凸函數，因此喲可能EM 演算法給出的局部最優解而不是全局最優解。

高斯分布、指數分布那個得到全局最優。
混合高斯不一定，如果是凸函數就可以。

機器學習——幾種距離度量方法比較
從最大似然到EM演算法淺解

E. 極大似然估計和EM演算法初步

本文來自我的個人博客 https://www.zhangshenghai.com/posts/1422/

極大似然估計是在知道結果的情況下，尋求使該結果出現可能性極大的條件，以此作為估計值。在維基網路中，極大似然估計的定義是這樣的：

首先從一個例子入手，假設我們需要調查某個地區的人群身高分布，那麼先假設這個地區人群身高服從正態分布 。注意，極大似然估計的前提是要假設數據總體的分布， 不知道數據分布是無法使用極大似然估計的 。假設的正態分布的均值和方差未知，這個問題中極大似然估計的目的就是要估計這兩個參數。

根據概率統計的思想，可以依據樣本估算總體，假設我們隨機抽到了1000個人，根據這1000個人的身高來估計均值 和方差 。

將其翻譯成數學語言：為了統計該地區的人群身高分布，我們獨立地按照概率密度 抽取了1000個樣本組成樣本集 ，我們想通過樣本集 來估計總體的未知參數 。這里概率密度 服從高斯分布 ，其中的未知參數是 。

那麼怎樣估算 呢？

這里每個樣本都是獨立地從 中抽取的，也就是說這1000個人之間是相互獨立的。若抽到 的概率是 ，抽到 的概率是 ，那麼同時抽到它們的概率就是 。同理，同時抽到這1000個人的概率就是他們各自概率的乘積，即為他們的聯合概率，這個聯合概率就等於這個問題的似然函數：

對 L 取對數，將其變成連加的，稱為對數似然函數，如下式：

對似然函數求所有參數的偏導數，然後讓這些偏導數為0，假設有n個參數，就可以得到n個方程組成的方程組，方程組的解就是似然函數的極值點了，在似然函數極大的情況下得到的參數值 即為我們所求的值：

極大似然估計是建立在這樣的思想上：已知某個參數能使這個樣本出現的概率極大，我們當然不會再去選擇其他小概率的樣本，所以乾脆就把這個參數作為估計的真實值。

和極大似然估計一樣，EM演算法的前提也是要假設數據總體的分布， 不知道數據分布是無法使用EM演算法的 。

概率模型有時既含有觀測變數，又含有隱變數。如果概率模型的變數都是觀測變數，那麼給定數據，可以直接用極大似然估計法，或貝葉斯估計法估計模型參數。但是，當模型含有隱變數時，就不能簡單地使用這些估計方法。EM演算法就是含有隱變數的概率模型參數的極大似然估計法，或極大後驗概率估計法。

函數：完全數據的對數似然函數 關於在給定觀測數據 和當前參數 下對未觀測數據 的條件概率分布 的期望

含有隱變數 的概率模型，目標是極大化觀測變數 關於參數 的對數似然函數，即

輸入：觀測隨機變數數據 ，隱隨機變數數據 ，聯合分布 ，條件分布 ；
輸出：模型參數

F. em演算法的EM演算法簡述

迭代使用EM步驟，直至收斂。
可以有一些比較形象的比喻說法把這個演算法講清楚。比如說食堂的大師傅炒了一份菜，要等分成兩份給兩個人吃，顯然沒有必要拿來天平一點一點的精確的去稱分量，最簡單的辦法是先隨意的把菜分到兩個碗中，然後觀察是否一樣多，把比較多的那一份取出一點放到另一個碗中，這個過程一直迭代地執行下去，直到大家看不出兩個碗所容納的菜有什麼分量上的不同為止。EM演算法就是這樣，假設我們估計知道A和B兩個參數，在開始狀態下二者都是未知的，並且知道了A的信息就可以得到B的信息，反過來知道了B也就得到了A。可以考慮首先賦予A某種初值，以此得到B的估計值，然後從B的當前值出發，重新估計A的取值，這個過程一直持續到收斂為止。
EM 演算法是 Dempster，Laind，Rubin 於 1977 年提出的求參數極大似然估計的一種方法，它可以從非完整數據集中對參數進行 MLE 估計，是一種非常簡單實用的學習演算法。這種方法可以廣泛地應用於處理缺損數據，截尾數據，帶有雜訊等所謂的不完全數據(incomplete data)。
假定集合Z = (X,Y)由觀測數據 X 和未觀測數據Y 組成，X 和Z = (X,Y)分別稱為不完整數據和完整數據。假設Z的聯合概率密度被參數化地定義為P(X,Y|Θ)，其中Θ表示要被估計的參數。Θ的最大似然估計是求不完整數據的對數似然函數L(X;Θ)的最大值而得到的：
L(Θ;X)= log p(X|Θ) = ∫log p(X,Y|Θ)dY ；
EM演算法包括兩個步驟：由E步和M步組成，它是通過迭代地最大化完整數據的對數似然函數Lc(X;Θ)的期望來最大化不完整數據的對數似然函數，其中：
Lc(X;Θ) =log p(X,Y |Θ) ；
假設在演算法第t次迭代後Θ獲得的估計記為Θ(t) ，則在(t+1)次迭代時，
E-步：計算完整數據的對數似然函數的期望，記為：
Q(Θ|Θ (t)) = E{Lc(Θ;Z)|X;Θ(t)}；
M-步：通過最大化Q(Θ|Θ(t) ) 來獲得新的Θ 。
通過交替使用這兩個步驟，EM演算法逐步改進模型的參數，使參數和訓練樣本的似然概率逐漸增大，最後終止於一個極大點。直觀地理解EM演算法，它也可被看作為一個逐次逼近演算法：事先並不知道模型的參數，可以隨機的選擇一套參數或者事先粗略地給定某個初始參數λ0 ，確定出對應於這組參數的最可能的狀態，計算每個訓練樣本的可能結果的概率，在當前的狀態下再由樣本對參數修正，重新估計參數λ，並在新的參數下重新確定模型的狀態，這樣，通過多次的迭代，循環直至某個收斂條件滿足為止，就可以使得模型的參數逐漸逼近真實參數。
EM演算法的主要目的是提供一個簡單的迭代演算法計算後驗密度函數，它的最大優點是簡單和穩定，但容易陷入局部最優。

G. 大數據經典演算法解析（5）一EM演算法

  姓名：崔升    學號：14020120005

【嵌牛導讀】：

  EM作為一種經典的處理大數據的演算法，是我們在學習互聯網大數據時不得不去了解的一種常用演算法

【嵌牛鼻子】：經典大數據演算法之EM簡單介紹

【嵌牛提問】：EM是一種怎麼的演算法，其如何去觀測其中隱變數的？

【嵌牛正文】：

1. 極大似然

極大似然（Maximum Likelihood）估計為用於已知模型的參數估計的統計學方法。比如，我們想了解拋硬幣是正面（head）的概率分布θθ；那麼可以通過最大似然估計方法求得。假如我們拋硬幣1010次，其中88次正面、22次反面；極大似然估計參數θθ值：

θ^=argmaxθl(θ)=argmaxθθ8(1−θ)2θ^=arg⁡maxθl(θ)=arg⁡maxθθ8(1−θ)2

其中，l(θ)l(θ)為觀測變數序列的似然函數（likelihood function of the observation sequence）。對l(θ)l(θ)求偏導

∂l(θ)∂θ=θ7(1−θ)(8−10θ)⇒θ^=0.8∂l(θ)∂θ=θ7(1−θ)(8−10θ)⇒θ^=0.8

因為似然函數l(θ)l(θ)不是凹函數（concave），求解極大值困難。一般地，使用與之具有相同單調性的log-likelihood，如圖所示

凹函數（concave）與凸函數（convex）的定義如圖所示：

從圖中可以看出，凹函數「容易」求解極大值，凸函數「容易」求解極小值。

2. EM演算法

EM演算法（Expectation Maximization）是在含有隱變數（latent variable）的模型下計算最大似然的一種演算法。所謂隱變數，是指我們沒有辦法觀測到的變數。比如，有兩枚硬幣A、B，每一次隨機取一枚進行拋擲，我們只能觀測到硬幣的正面與反面，而不能觀測到每一次取的硬幣是否為A；則稱每一次的選擇拋擲硬幣為隱變數。

用Y表示觀測數據，Z表示隱變數；Y和Z連在一起稱為完全數據( complete-data )，觀測數據Y又稱為不完全數據(incomplete-data)。觀測數據的似然函數：

P(Y|θ)=∑ZP(Z|θ)P(Y|Z,θ)P(Y|θ)=∑ZP(Z|θ)P(Y|Z,θ)

求模型參數的極大似然估計：

θ^=argmaxθlogP(Y|θ)θ^=arg⁡maxθlog⁡P(Y|θ)

因為含有隱變數，此問題無法求解。因此，Dempster等人提出EM演算法用於迭代求解近似解。EM演算法比較簡單，分為兩個步驟：

E步（E-step），以當前參數θ(i)θ(i)計算ZZ的期望值

Q(θ,θ(i))=EZ[logP(Y,X|θ)|Y,θ(i)]Q(θ,θ(i))=EZ[log⁡P(Y,X|θ)|Y,θ(i)]

M步（M-step），求使Q(θ,θ(i))Q(θ,θ(i))極大化的θθ，確定第i+1i+1次迭代的參數的估計值θ(i+1)θ(i+1)

θ(i+1)=argmaxθQ(θ,θ(i))θ(i+1)=arg⁡maxθQ(θ,θ(i))

如此迭代直至演算法收斂。關於演算法的推導及收斂性證明，可參看李航的《統計學習方法》及Andrew Ng的《CS229 Lecture notes》。 這里 有一些極大似然以及EM演算法的生動例子。

3. 實例

[2]中給出極大似然與EM演算法的實例。如圖所示，有兩枚硬幣A、B，每一個實驗隨機取一枚拋擲10次，共5個實驗，我們 可以 觀測到每一次所取的硬幣，估計參數A、B為正面的概率θ=(θA,θB)θ=(θA,θB)，根據極大似然估計求解

如果我們 不能 觀測到每一次所取的硬幣，只能用EM演算法估計模型參數，演算法流程如圖所示：

隱變數ZZ為每次實驗中選擇A或B的概率，則第一個實驗選擇A的概率為

P(z1=A|y1,θ(0))=P(z1=A|y1,θ(0))P(z1=A|y1,θ(0))+P(z1=B|y1,θ(0))=0.65∗0.450.65∗0.45+0.510=0.45P(z1=A|y1,θ(0))=P(z1=A|y1,θ(0))P(z1=A|y1,θ(0))+P(z1=B|y1,θ(0))=0.65∗0.450.65∗0.45+0.510=0.45

按照上面的計算方法可依次求出隱變數ZZ，然後計算極大化的θ(i)θ(i)。經過10次迭代，最終收斂。

4. 參考資料

[1] 李航，《統計學習方法》.

[2] Chuong B Do & Serafim Batzoglou, What is the expectation maximization algorithm?

[3] Pieter Abbeel, Maximum Likelihood (ML), Expectation Maximization (EM) .

[4] Rudan Chen, 【機器學習演算法系列之一】EM演算法實例分析 .

H. EM演算法深度解析

最近在做文本挖掘的時候遇到了EM演算法，雖然讀書的時候簡單地接觸過，但當時並沒有深入地去了解，導致現在只記得演算法的名字。既然EM演算法被列為數據挖掘的十大演算法之一，正好借這個機會，重新學習一下這個經典的演算法。學習的過程中，我發現網上的資料大多講解地不夠細致，很多地方解釋得並不明了。因此我決定拋開別人的想法，僅從數學推導本身出發，盡力理解每一個公式的含義，並將其對應到實際的實驗過程當中。這篇博客記錄了我對與EM演算法的思考與理解，也是我人生中的第一篇博客，希望能夠對於想要學習EM演算法的同學有所幫助。

前面談到我在做文本挖掘的時候遇到了EM演算法，EM演算法用於估計模型中的參數。提到參數估計，最常見的方法莫過於極大似然估計——在所有的候選參數中，我們選擇的參數應該讓樣本出現的概率最大。相信看到這篇筆記的同學一定對極大似然估計非常熟悉，而EM演算法可以看作是極大似然估計的一個擴充，這里就讓我們用極大似然估計來解決一個簡單的例子，來開始正式的討論。

有A，B，C三枚硬幣，我們想要估計A，B，C三枚硬幣拋出正面的概率 , , 。我們按如下流程進行實驗100次：

記錄100次實驗的結果如下：

我們將上面的實驗結果表述如下：
表示第i次實驗中，硬幣A的結果，1代表正面，0代表反面； 表示第i次實驗中，硬幣B或硬幣C拋出正面的個數，則參數 的極大似然估計分別為：

即硬幣A，B，C各自拋出正面的次數占總次數的比例，其中 為指示函數。

實驗流程與1相同，但是我們不慎遺失了硬幣A的記錄結果，導致我們只知道隨後十次拋出了多少次正面，多少次反面，卻不知道實驗結果來自於硬幣B還是硬幣C。在這種情況下，我們是否還能估計出 , , 的值呢？

這時候利用極大似然估計似乎行不通了， 因為這種情況下，我們不但缺失了硬幣A產生的觀測值，同時也不知道哪些觀測值屬於硬幣B，哪些觀測值屬於硬幣C。

有些同學可能會提出，雖然我們無法得到三個硬幣各自產生的樣本，但是我們依然可以得到每個觀測值出現的概率。比如在第一次實驗中， 我們拋出了5次正面5次反面，我們可以做如下思考：

  假設這5次正面由硬幣B得到，那麼概率應該為 ，而這次觀測值來自於硬幣B，也就是硬幣A拋出正面的概率為

  假設這5次正面由硬幣C得到，那麼概率應該為 ，而這次觀測值來自於硬幣C，也就是硬幣A拋出反面的概率為

  綜合起來，利用條件概率公式，這個觀測值出現的概率就是

因此我們可以將樣本整體的概率和似然函數利用 , , 表示出來，通過對似然函數求導，令其關於 的偏導數等於0，我們可以求出三個參數的值。

這個思路聽上去十分合理，我們可以順著這個思路進行數學推導，看看可以得到什麼樣的結果。首先我們計算樣本的概率:

對應的似然函數為

其中 關於 的條件分布為

的分布為

因此我們可以得到

至此，我們成功地得到了似然函數。然而觀察可以發現，這個函數是由100項對數函數相加組成，每個對數函數內部包含一個求和，想通過求導並解出導數的零點幾乎是不可能的。當然我們可以通過梯度下降來極小化這個函數，藉助深度學習庫的自動微分系統在實現上也非常容易。但是這種做法過於簡單粗暴，有沒有辦法來優雅地解決這個問題呢？在繼續討論之前，我們先將這類問題進行一般化表述：

我們觀測到隨機變數 產生的m個相互獨立的樣本 , 的分布由聯合分布 決定， 是缺失數據或無法在實驗中被直接觀測到，稱為 隱變數 ，我們想要從樣本中估計出模型參數 的值。在接下來的討論中，我們假定 的取值是離散的，於是可以得到似然函數如下:

接下來，我們就探討一下，如何利用EM演算法解決這個問題。

這一部分的數學推導，主要參考了吳恩達CS229n的筆記，並且根據個人的思考和理解，盡力對公式的每一步進行詳細的解釋。我們先簡單地介紹一下琴生不等式。

琴生不等式有多種形式，下面給出其離散形式的表述和概率論中的表述:
1.若 為嚴格凹函數， 為定義域內的n個點， 是n個正實數，且滿足 , 則下述不等式成立:

當且僅當 時，不等式取等號。

2.若 為嚴格凹函數， 為實值隨機變數，且期望存在，則下述不等式成立:

當且僅當 ，即 為常數時，不等式取等號。

註： 這里將函數上方為凹集的函數稱為凹函數， 例如 函數就是凹函數。
相信大家對琴生不等式都十分熟悉，因此這里就不做過多的說明。接下來，我們將琴生不等式應用到我們的問題中。

回到我們之前的問題上， 我們想要極大化下面這個函數:

但是我們無法對這個函數直接求導，因此我們藉助琴生不等式，對這個函數進行變換。為了讓過程看上去簡潔，下面只對求和中的第 項進行計算。

令 滿足 ，且 ，則根據琴生不等式，可以得到：

當且僅當 為常數時，上述不等式取等號。也就是說，對於任意 ， 是一個與 無關的量。設對於任意 ，我們可以得到：

因此當 時，不等式 取等號，容易驗證此時 , 與 無關。將 綜合一下，我們可以得到以下結論:

到這里為止，我們已經擁有了推導出EM演算法的全部數學基礎，基於 我們可以構建出E步和M步。上面的數學推導雖然看上去略為復雜，但實際上只用到了三個知識點：
  1.琴生不等式:

  2.條件概率:

  3.聯合分布求和等於邊緣分布:

對上面的數學推導有疑問的同學，可以結合上面這三點，再將整個推導過程耐心地看一遍。

大部分關於EM演算法的資料，只是在數學形式上引入了 函數，即 ，以滿足琴生不等式的使用條件，卻沒有過多地解釋 函數本身。這導致了很多人完全看懂了演算法的推導，卻還是不理解這些數學公式究竟在做什麼，甚至不明白EM演算法為什麼叫做EM演算法。所以在給出E步和M步之前，我想先談一談 函數。

我們回顧一下 函數所滿足的條件（暫時不考慮琴生不等式取等號的限制），

在 所有可能的取值處有定義。可以看出， 是 的樣本空間上任意的一個概率分布。因此，我們可以對不等式 進行改寫。首先我們可以將含有 的求和寫成期望的形式:

這里 指的是在概率分布 下，求隨機變數 和 的期望。有同學會問，為什麼我們平時求期望的時候只要寫 ，並沒有指明是在哪個概率分布下的期望。這是因為一般情況下，我們都清楚地知道隨機變數 所服從的分布 ，並且默認在分布 下求期望。

舉個例子，我手上有一個硬幣，拋了10次，問拋出正面次數的期望。這種情況下，大部分人會默認硬幣是均勻的，也就是說拋出正面的次數 服從二項分布 ，期望 。這時有人提出了質疑，他說我認為你這個硬幣有問題，拋出正面的概率只有0.3，那麼在他眼裡， 期望 。

回到正題，我們利用等式 改寫不等式 ，可以得到:

這正是琴生不等式在概率論中的形式。我們可以將不等式倒過來理解：
  首先，假定隨機變數 服從概率分布 ， 是 的樣本空間上的任意一個概率分布。這里 可以是一組定值，也可以是關於參數 的函數。

  顯然，當我們取不同的 時，隨機變數 的期望也會隨之改變。需要注意的是，由於 與 相關，所以這里的期望不是一個數值，而是關於 的函數。

  當我們令 為 的後驗分布 時，上面的期望最大。這里有兩點需要注意，1. 後驗分布 也是一個關於參數 的函數。2. 由於期望是關於 的函數，所以這里的最大指的並非是最大值，而是最大的函數。

  若對於每一個 ，我們都令 為 的後驗分布 ，則上述期望之和等於我們要極大化的似然函數，即

通過上述分析，我們為尋找似然函數的極大值點 提供了一個思路。我們不去極大化似然函數本身，而是去極大化 。至於如何將這個思路實際應用，就要利用到EM演算法中的E-step和M-step。

這一節中，我們先給出E-step和M-step的數學形式，隨後在結合拋硬幣的例子來解釋這兩步究竟在做什麼。下面進入演算法的流程，首先我們任意初始化 ，按下述過程進行迭代直至收斂：

在第 次迭代中，
(E-step)對於每個 ，令
(M-step)更新 的估計值，令

EM演算法從任意一點 出發，依次利用E-step優化 ，M-step優化 ，重復上述過程從而逐漸逼近極大值點。而這個過程究竟是怎樣的呢，就讓我們一步步地揭開EM演算法的面紗。

假設我們現在隨機初始化了 ，進入第一輪迭代：
(E-step)

由於我們已經假定模型參數為 ，所以此時 不再是與 有關的函數，而是由一組常數構成的概率分布。結合拋硬幣的例子來看，這一步是在我們已知模型參數 的基礎上(雖然這是我們瞎猜的)，去推測每一次的觀測值是由哪個硬幣產生的，或者說我們對每一次觀測值做一個軟分類。比如我們根據初始化的參數，計算出 ， 。可以解釋為第 個觀測值有20%的概率來自於硬幣B，80%的概率來自於硬幣C；或者說硬幣A拋出了0.2個正面，0.8個反面。

(M-step)

考慮到 是一組常數，我們可以舍棄常數項，進一步簡化上面這個要極大化的函數

由於 不再與 相關，因此上面的函數變成了對數函數求和的形式，這個函數通常來說是容易求導的，令導數等於0，我們可以求出新的參數 。我們仍舊以拋硬幣為例進行解釋，

令 , 可以得到，

這三個參數的解釋是顯而易見的。我們在E-step中對每個觀測值進行了軟分類， 可以看成是硬幣A拋出正面的次數，所以 是 的極大似然估計； 是我們拋硬幣B的次數， 是硬幣B拋出正面的次數，所以 是 的極大似然估計；對於 我們有相同的解釋。

我們將這個結果與拋硬幣1中極大似然估計的結果相比較可以發現，之前結果中的指示函數 變成了這里的 ，在指示函數下，某個觀測值要麼來自於硬幣B，要麼來自於硬幣C，因此也稱為硬分類。而在 函數下，某個觀測值可以一部分來自於硬幣B，一部分來自於硬幣C，因此也稱作軟分類。

將上述兩步綜合起來，EM演算法可以總結如下：我們首先初始化模型的參數，我們基於這個參數對每一個隱變數進行分類，此時相當於我們觀測到了隱變數。有了隱變數的觀測值之後，原來含有隱變數的模型變成了不含隱變數的模型，因此我們可以直接使用極大似然估計來更新模型的參數，再基於新的參數開始新一輪的迭代，直到參數收斂。接來下我們就討論為什麼參數一定會收斂。

前面寫了太多的公式，但是這一部分我不打算給出收斂性的數學推導。其實數學上證明EM演算法的收斂性很容易，只需要證明每一輪迭代之後，參數的似然函數遞增，即

I. EM演算法和K-Means演算法

在實際工作中，會遇到這樣的問題，給機器輸入大量的特徵數據，並希望機器希望學習找到某種共同的特徵或者結構，亦或是數據之間存在的某種關聯，例如，視頻網站根據用戶的觀看行為進行分組，從而建立不同的推薦策略，或是找到視頻是否流暢與用戶是否退訂之間的關系等。屬於無監督學習演算法。

包括兩大類，一：數據聚類，此類方案往往是通過數次迭代找到數據的最優分割。二：特徵變數的關聯規則，此類方法利用各種相關性分析找到變數之間的關系。

Kmeans的 核心 是將給定的數據集劃分成K個簇，並給出每個數據對應的中心點。演算法具體步驟如下：

1：數據預處理，如歸一化、離散點處理等

2：隨機選取K個簇中心，記為 。

3：定義代價函數： 。

4：令 為迭代步數，重復下面過程直到 收斂

4.1 對於每一個樣本將其分到距離最近的簇

4.2 對於每一個類簇k，重新計算類簇的中心

K均值在迭代時，交替方向法求解，假設當前 沒有達到最小值，那麼首先固定簇中心 ,調整樣本 所屬的類別 來讓 函數減小，然後再固定 ,調整中心 使 減小，這兩個過程交替循環， 單調遞減，當 遞減到最小時， 和 同時收斂。

缺點：

1：受初始值的影響

2：異常值的影響

3：當簇分布相差很大時，不適合

優點：

大數據集， 均值聚類相對是可伸縮和高效的，計算復雜度 ,其中 是數據對象的數目， 是聚類簇數， 是迭代的輪數。盡管演算法經常局部最優結束，一般情況下局部最優已經滿足要求

調優方向

1：數據歸一化和離散點處理

2：合理選擇 值

一：手肘法：選擇若干個K畫均方誤差的折線圖肉眼查看拐點 二：Gap Statistic方法的基本思路是：引入參考的測度值，其可以通過Monte Carlo采樣的方法獲得。 

3：採用核函數

利用kmeans假設各個數據簇的數據具有一樣的先驗概率，並呈現高緯球形分布，但是實際生活中是不常見的。面對非凸的數據分布時，引入核函數來優化。核心：利用非線性核函數將樣本映射到高緯空間，並在新的特徵空間中進行聚類。非線性映射增加了數據的線性可分的概率。

針對對初始值敏感的改進

K-means++演算法：

起步

由於 K-means 演算法的分類結果會受到初始點的選取而有所區別，因此有提出這種演算法的改進: K-means++ 。

演算法步驟

其實這個演算法也只是對初始點的選擇有改進而已，其他步驟都一樣。初始質心選取的基本思路就是，初始的聚類中心之間的相互距離要盡可能的遠。

演算法描述如下：

步驟一： 隨機選取一個樣本作為第一個聚類中心；

步驟二：

計算每個樣本與當前已有類聚中心最短距離（即與最近一個聚類中心的距離） 這個值越大，表示被選取作為聚類中心的概率較大；

最後，用輪盤法選出下一個聚類中心；

步驟三： 重復步驟二，知道選出 k 個聚類中心 。

選出初始點後，就繼續使用標準的 k-means 演算法了。

      ISODATA的聚類個數是可變的，因為在聚類的過程中，對類別數有一個「合並」和「分裂」的操作。合並是當聚類結果某一類中樣本數太少，或兩個類間的距離太近時，將這兩個類別合並成一個類別；分裂是當聚類結果中某一類的類內方差太大，將該類進行分裂，分裂成兩個類別。

ISODATA分類的過程和K-Means一樣，用的也是迭代的思想：先隨意給定初始的類別中心，然後做聚類，通過迭代，不斷調整這些類別中心，直到得到最好的聚類中心為止。

註：

初始簇個數 ，最終簇大小范圍

分裂和合並的標准

每個簇的樣本數最小 ，小於這個值不進行分裂

每個簇樣本的最大方差 ，大於這個則進行分裂

兩個簇之間的最小距離圍 ，小於這個則進行合並

EM演算法是一種迭代演算法，用於含有隱變數的概率模型的極大似然估計，或者說是極大後驗概率估計。

演算法步驟

輸入：觀測變數數據Y，隱變數Z，聯合分布 ，條件分布

輸出：模型參數

1：選擇參數的初始值

2：E步：記 為第 次迭代參數 的估計值，在第 次迭代的E步，計算 函數 ，其中， 是再幫給定Y和 下隱變數數據Z的條件概率分布；

3：M步：求使 極大化的 ，確定第 次迭代的參數的估計值 ,

4：重復2，3步，直到收斂

EM演算法推導

通過不斷求解下界的極大化逼近求解對數似然函數的極大化的演算法

含有隱變數的概率模型的極大似然估計

下面證明

利用Jensen不等式

令

則 即函數 增大 ，也可以使得 有盡可能的增大，選擇 使得 達到極大，即 現在求 的表達式 = = = =

假設有m個觀察樣本，模型的參數 ，最大化對數似然函數可以寫成如下的形式

當概率模型含有無法觀測的隱變數時，參數的最大似然估計

因為含有不可觀測的隱變數，無法通過極大似然估計求解參數，這時可以通過EM演算法求解。假設 對應的分布 ，並滿足 。利用Jensen不等式，可以得到，

。不等式右側，即為 。當等式成立時，我們相當於優化的函數找到了一個逼近的下界，然後最大化這個下界

EM演算法和k-means關系

1：E步驟

2：M步驟：最大化

K均值演算法等價於以下隱變數求最大似然問題

相當於E步找到x當前最近的簇

在M步驟 來更新簇中心

#####引用葫蘆書和李航機器學習