EM（Expectation Maximum，期望最大化）是一種迭代算法，用於對含有隱變量概率參數模型的極大似然估計或極大後驗估計。模型參數的每一次迭代，含有隱變量概率參數模型的似然函數都會增加，當似然函數不再增加或增加的值小於設置的閾值時，迭代結束。
EM算法在機器學習和計算機視覺的數據聚類領域有廣泛的應用，只要是涉及到後驗概率的應用，我們都可以考慮用EM算法去解決問題。EM算法更像是一種數值分析方法，正確理解了EM算法，會增強你機器學習的自學能力，也能讓你對機器學習算法有新的認識，本文詳細總結了EM算法原理。
目錄
1. 只含有觀測變量的模型估計
2. 含有觀測變量和未觀測變量的模型參數估計
3. EM算法流程
4. 拋硬幣問題舉例
5. 高斯混合模型的參數估計
6. 聚類蘊含的EM算法思想
7. 小結
我們首先考慮比較簡單的情況，即模型只含有觀測變量不含有隱藏變量，如何估計模型的參數？我們用邏輯斯蒂回歸模型（logistic regression model）來解釋這一過程。
假設數據集有d維的特徵向量X和相應的目標向量Y，其中，。下圖表示邏輯斯蒂回歸模型：
由之前的文章介紹，邏輯斯蒂回歸模型的目標預測概率是S型函數計算得到，定義為：
若，則目標預測變量為1；反之，目標預測變量為0。其中w是待估計的模型參數向量。
機器學習模型的核心問題是如何通過觀測變量來構建模型參數w，最大似然方法是使觀測數據的概率最大化，下面介紹用最大似然方法（Maximum Likelihood Approach）求解模型參數w。
假設數據集，樣本數據，模型參數。
觀測數據的對數似然函數可寫為：
由對數性質可知，上式等價於：
式(1)代入式(2)，得：
其中：
由於(3)式是各個樣本的和且模型參數間並無耦合，因此用類似梯度上升的迭代優化算法去求解模型參數w。
因為：
由式(4)(5)(6)可得：
因此，模型參數w的更新方程為：
其中η是學習率。
根據梯度更新方程（7）迭代參數w，似然函數L(w)逐漸增加，當似然函數收斂時，模型參數w不再更新，這種參數估計方法稱為最大似然估計。
上節介紹當模型只含有觀測變量時，我們用極大似然估計方法計算模型參數w。但是當模型含有隱變量或潛在變量（latent）時，是否可以用極大似然估計方法去估計模型參數，下面我們討論這一問題：
假設V是觀測變量，Z是隱變量，θ是模型參數，我們考慮用極大似然估計方法去計算模型參數：
由於隱變量在log內部求和，造成不同參數間相互耦合，因此用極大似然方法估計模型參數非常難。(8)式不能估計模型參數的主要原因是隱變量，若隱變量Z已知，完全數據的似然函數為，為了書寫方便，觀測變量V，Y統一用V表示，即。
那麼問題來了，如何通過已觀測變量估計隱變量Z的值？這個時候我們想到了後驗概率：
EM算法最大化完全數據在隱變量分布的對數似然函數期望，得到模型參數θ即：
現在我們總結EM算法的流程：
1）初始化模型參數；
2）E步估計隱變量的後驗概率分布：
3）M步估計模型參數：
4）當模型參數或對數似然函數收斂時，迭代結束；反之，返回第（2）步，繼續迭代。
上節我們介紹了EM算法的模型參數估計過程，相信大家會有個疑問：為什麼最大化下式來構建模型參數。
下面我給大家解釋這一算法的推導過程以及其中蘊含的含義：
假設隱藏變量的理論分布為，觀測數據的對數似然函數可以分解為下式：
由貝葉斯理論可知：
（9）式得：
分子分母除q(Z)，得：
（10）式第二項表示相對熵，含義為隱變量後驗概率分布與理論概率分布的差異，相對熵的一個性質是：
根據（10）式我們推斷：
因此觀測數據的對數似然函數的下界為，如果我們能夠極大化這個下界，那麼同時也極大化了可觀測數據的對數似然函數。
當相對熵等於0時，即：
由上式得到隱藏變量的後驗概率分布與理論分布相等，即：
進而（11）式等號成立，即：
取得上界，現在我們需要最大化的上界，即：
當相對熵等於0時，式(12)代入式(13)得到的上界為：
式（15）的第二項對應隱變量的熵，可看成是常數，因此最大化（15）式等價於最大化，其中：
最大化（16）式對應上節介紹EM算法的M步。
重新整理算法EM的流程：
1）初始化模型參數為；
2）當等式（12）成立時，取得上界，最大化等價於最大化下式：
3）最大化，返回參數；
4）當收斂時，迭代結束；否則，算法返回到第（2）步繼續迭代；
為了大家清晰理解這一算法流程，下面用圖形表示EM算法的含義。
E步：模型參數是時，由（13）式可知，用黑色實心點標記；
M步：最大化，返回參數，用紅色實心點標記；
令，重複E步和M步，當收斂時，迭代結束。
我們有兩種硬幣A和B，選擇硬幣A和硬幣B的概率分別為π和（1-π），硬幣A和硬幣B正面向上的概率分別為p和q，假設觀測變量為，1，0表示正面和反面，i表示硬幣拋擲次數；隱變量，1，0表示選擇硬幣A和硬幣B進行拋擲。
問題：硬幣共拋擲n次，觀測變量已知的情況下求模型參數的更新表達式。
根據EM算法，完全數據的對數似然函數的期望：
其中表示觀測數據來自擲硬幣A的概率，用表示：
最大化，得到如下更新表達式：
現在我們知道了模型參數θ的更新方程，假設共拋擲硬幣10次，觀測結果如下：1,1,0,1,0,0,1,0,1,1。
初始化模型參數為：
由式（18）得：
利用模型參數更新得：
由式（18），得：
模型參數繼續更新：
因此，收斂時，最終的模型參數為：
表示選擇硬幣A和硬幣B的概率是一樣的，如果模型參數的初始值不同，得到的最終模型參數也可能不同，模型參數的初始化和先驗經驗有關。
一維變量的高斯分布：
其中u和σ分別表示均值和標準差。
n維變量的高斯分布：
其中u是n維均值向量，是n×n的協方差矩陣。
n維變量的混合高斯分布：
該分布共由k個混合成分組成，每個混合成分對應一個高斯分布，其中與是第k個高斯混合成分的均值和協方差。
是歸一化混合係數，含義為選擇第k個高斯混合成分的概率，滿足以下條件：
下圖為k=3的高斯混合成分的概率分布圖（紅色）：
假設由高斯混合分布生成的觀測數據，其對數似然函數：
我們用EM算法估計模型參數，其中隱變量對應模型的高斯混合成分，即對於給定的數據x，計算該數據屬於第k個高斯混合分布生成的後驗概率，記為。
根據貝葉斯定律：
最大化式（19），令
由式（20）（21）（22）（23）可得模型參數：
小結EM算法構建高斯混合模型的流程：
1）初始化高斯混合模型的均值，協方差和混合係數，計算完全數據的對數似然值（式（19））；
2）E步：使用當前的參數值，通過下式計算均值：
表示觀測數據x屬於第k個高斯混合成分的後驗概率；
3）M步：最大化對數似然函數，得到式（24）（25）（26）的模型更新參數；
4）根據更新的參數值，重新計算完全數據的對數似然函數：
若收斂，則得到最終的模型參數值；反之，回到算法第（2）步繼續迭代。
我們可以把聚類理解為：計算觀測數據x屬於不同簇類的後驗概率，記為，其中j是簇類個數（j=1,2,...,K），觀測數據x所屬的簇標記由如下確定：
我們可以用EM算法計算每個樣本由不同高斯混合成分生成的後驗概率，步驟可參考上一節。
【例】 如下的觀測數據，假設簇類個數K=2，初始化每個高斯混合參數得到，根據式（27）得到聚類結果：
根據上一節介紹的EM算法步驟，迭代1次後得到，根據式（27）得到聚類結果：
迭代5次後得到，根據式（27）得到聚類結果：
迭代20次後的，根據式（27）得到聚類結果：
k均值聚類是高斯混合聚類的特例，k均值假設各個維是相互獨立的，其算法過程也可用EM思想去理解：
2）E步：通過簇類中心計算每個樣本所屬簇類的後驗概率；3）M步：最大化當前觀測數據的對數似然函數，更新簇類中心4）當觀測數據的對數似然函數不再增加時，迭代結束；反之，返回（2）步繼續迭代；EM算法在各領域應用極廣，運用了後驗概率，極大似然方法和迭代思想構建最優模型參數，希望通過這篇文章能讓讀者對EM算法不再陌生。
推薦閱讀：
博士論文工作的基本特徵和創新能力評價存在的挑戰
不是每次都能這麼有驚無險…
一首可靠性工程哲理的古老詩歌—執事的傑作，神奇的「單馬馬車」
遺傳算法解決帶時間窗的車輛路徑規劃問題(附java代碼及詳細注釋）
分治法（Divide-and-Conquer Algorithm）經典例子分析