EM算法
我們知道在機器學習中，很多時候問題都可以歸結為一個最優化問題，而要解決這個最優化問題只需要求解出模型參數即可。大多數時候，只要給定數據可以直接用極大似然估計法估計模型參數。但是當模型里含有隱變量的時候，直接求解參數的極大似然估計就會失效。這時就需要用到EM算法來對參數進行迭代求解。EM算法說白了也是求參數的極大似然估計，只不過它解決的問題是含有隱變量的模型參數的極大似然估計。
EM算法是一個十分重要且廣泛應用的算法，因為有相當一部分模型實際上是存在隱變量的，比如混合模型（高斯混合模型，伯努利混合模型），訓練推理主題模型（topic model）時的pSLA等等。
我們首先通過一般性的推理來了解什么是EM算法，然后通過高斯混合模型作為例子來闡釋EM算法。
我們知道，EM算法的目標是對于含有隱變量的模型求出模型參數的極大似然估計。我們假設可觀測變量的集合為X，隱藏變量的集合為Z，模型參數用W表示。因此，相應的對數似然函數為：
（1）
上式中等式左右兩端用到了聯合概率分布和邊緣概率分布之間的一個轉換，即：
（2）
從（1）式中我們可以看出，式中的求和符號是很“討厭的”，它使得對數符號無法作用于聯合概率密度函數上，這就使得求解參數W的極大似然估計變得復雜了。究其原因還是隱變量Z的引入，從而使得（1）式右邊必須對Z求和，如果去掉隱變量，那么就變成了一般情況下的參數極大似然估計，這就很容易求解了。
對于X和Z，如果X對應的Z都是已知的，那么我們稱{X,Z}為完全數據，在這種情況下由于Z已知，那么求解參數W的極大似然估計是相對容易和直接的。
但實際上問題中的Z往往是未知的，我們所知道的隱變量Z的信息只有它的后驗概率P(Z|X,W)。由前面的分析可知，如果知道X和Z，那么求解完全數據{X, Z}的對數似然函數logp(X,Z|W)的參數W是容易的，但是我們現在只知道Z的后驗概率，因此，我們轉而求解logp(X,Z|W)在隱變量Z的后驗概率下的期望值，而這就對應了EM算法的E步，即期望（expectation）；在接下來的M步，要做的工作就是極大化（maximum）這個期望。由上可知，如果參數目前的估計值為Wold，那么經過一個E步和M步之后，算法就會得到一個新估計的參數值Wnew。
在E步的時候，我們用Wold來得到隱變量Z的后驗概率，即p(Z|X,Wold)，接著，算法用得到的后驗概率來求出logp(X, Z|W)的期望。由于X已知，Z的后驗概率也已知，我們可以理解為X和Z都已知了，因此在求出期望后，就可以像已知完全數據{X,Z}的情況下，直接求解W的極大似然估計，這也對應了M步。期望的公式如下：
（3）
以上公式是由E步得到的，在M步，算法通過極大化期望來得到新一輪的參數估計值Wnew。公式如下：
（4）
由（3）式可知，此時對數符號log已經直接作用于X和Z的聯合概率密度函數上了，因此在（4）式中計算W的值就容易多了。
接下來將EM算法的步驟做一個總結。
給定X和Z的聯合概率分布，該分布帶有參數W，即，p(X,Z|W)，目標是要最大化似然函數p(X|W)，也就是要求出W使得p(X|W)最大。
1. 選擇參數W的初始值，Wold。
2. E步：利用初始值Wold計算隱變量Z的后驗概率分布，p(Z|X,Wold)，進而找出logp(X,Z|W)在Z的后驗概率下的期望Q(W,Wold)。
3. M步：極大化Q(W,Wold)，以求出W。
4. 檢查收斂條件，如果滿足收斂條件則停止；否則，令Wold= Wnew，然后跳轉到第2步，繼續迭代執行。
注意：以上對于EM算法的討論是假設隱變量Z為離散型隨機變量，當Z為連續型隨機變量時，上面的討論依然成立。
接下來我們看看EM算法的一個具體應用：求解高斯混合模型。
高斯混合模型是密度估計里十分常用的模型，如果樣本點的分布是單峰的，那么高斯分布能夠很好地估計樣本點的概率密度，但是如果樣本點的分布是多峰的，那么高斯分布不管怎么調整，也無法對樣本點做一個很好的估計，這時就需要用到高斯混合模型來估計樣本點的概率密度。假設我們接下來要求解的高斯混合模型的隱變量是離散型隨機變量。
設隨機變量X服從高斯混合分布，其概率密度函數為：
（5）
由上式可知，該高斯混合分布由K個高斯分布的加權線性組合構成，ak的含義是X為第k個高斯分模型生成的概率，因此X由哪個高斯分模型生成實際上是未知的，也就是“隱藏的”。
下面來推導式（5）。這里定義一個K維的隨機變量Z（隱變量），Z的取值特點為：僅有一個元素取值為1，其它K-1個元素取值為0。因此，對于向量Z，可能的取值方式有K種。我們定義p(Zk= 1) = ak，滿足0 <= ak<= 1，并且所有ak的和等于1。由于p(Zk= 1) = ak，因此我們可以寫出Z的邊緣概率密度函數：
（6）
由高斯混合分布的定義可知，給定一個Z的取值，那么X的分布就是一個高斯分布：
（7）
由（7）式可知：
（8）
由于p(X, Z) =p(Z)*p(X|Z)，
(9)
由（9）式：
（10）
至此，由（10）式可知，我們已經推出了（5）式，即高斯混合分布。
下面介紹如何用EM算法來求解高斯混合模型。
假設有N個觀測值x(1), x(2), … , x(n)，每個觀測值可以看作是高斯混合分布中的一個分模型產生的，因此每個x(i)對應了一個隱變量z(i)。下面寫出關于p(X)中參數W的似然函數：
（11）
其中W表示高斯混合分布里的所有參數。由于式（11）帶有求積符號，因此不太容易求解，一般都是對上式作用log之后，再求解：
（12）
我們的目標是極大化上面這個對數似然函數，由前面對EM算法的一般性分析可知，這里log沒有直接作用在高斯分布上，而是在log里還有求和式，這就導致了直接求解式（12）比較麻煩。根據之前的分析，假設我們現在不僅知道觀測數據X，也知道隱變量Z，那么我們可以寫出p(X,Z)，并寫出關于p(X,Z)中參數的對數似然函數。根據式（9），我們得到似然函數如下：
（13）
由此可知，對數似然函數為：
（14）
現在我們已經得到完全數據{X, Z}的對數似然函數，按照之前的一般性分析，我們要求得完全數據{X, Z}的對數似然函數在Z的后驗概率下的期望，即Q函數。根據式（14），我們只需要求出E[Z(i)k]。
由于Z(i)k表示第i個觀測數據是由第k個分模型生成的，因此我們可以認為E[Z(i)k]為第k個分模型生成第i個觀測數據的概率，或者說貢獻度。因此可以得到下式：
（15）
由此，我們得到完全數據的對數似然函數的期望如下式：
在得到上式之后，我們首先選擇初始的參數值Wold，然后用Wold來得到上式中的E[Z(i)k]，這也就是EM算法中的E步。最后我們固定這個期望，然后極大化上式來求得Wnew，這對應了算法的M步。
以上就是EM算法的原理及推導和EM算法求解高斯混合模型的過程。