Ⅰ 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演算法應用之缺失數據參數估計問題