EM算法的證明
上篇文章說了一些EM算法的原理性東西以及簡單的應用，在平時的學習中，確實感覺EM算法太重要了，所以本文將對EM算法的合理性作一個解釋，并給出其收斂性的證明。
在上一篇文章中，我們提到了EM算法是解決含有隱變量的概率模型參數極大似然估計的方法。不過我們可能會問，為什么在求解完全數據的對數似然函數的期望時要用到隱變量Z的后驗概率？為什么EM算法就一定能夠保證收斂？下面我們來解決這些問題。
這里，我們假設X為觀測變量的集合，Z為隱變量的集合，那么完全數據{X, Z}的聯合分布可以寫成p(X,Z|W)，其中W為參數集合。我們的目標是極大化以下的似然函數：
(1)
由于直接求解上式比較困難，因此我們想到求解完全數據{X, Z}的極大似然，而這是很容易的。根據貝葉斯定理，我們可以得到：
（2）
兩邊作用log后，得到下式：
（3）
接下來我們引入在隱變量Z上的一個分布q(Z)，由式（3）可得：
（4）
對上式中的右邊做合并，可得：
（5）
回憶一下，由于隱變量Z的取值特點為：只有一個元素取1，其它元素取0，并且q(Z)所有取值的和為1。因此式（5）兩邊在q(Z)下的期望為：
（6）
由于式（6）左邊的對數不含Z，又因為q(Z)所有取值的和為1，因此等式可以寫成：
（7）
令式（7）右邊的第一項為L(q,W)，右邊的第二項為KL(q||p)。由此可得：
（8）
（9）
由式（8）和式（9）可知：
（10）
從式（9）可以看出KL(q||p)是q(Z)和p(Z|X,W)之間的KL散度，p和q越相似KL散度越小，否則KL散度越大。由于KL(q||p)>= 0，并且當q(Z) =p(Z|X,W)時，等式成立，這可以理解為當q(Z)和p(Z|X,W)相等時，它倆之間的KL散度為0。由此得出結論：在式（10）中L(q,W) <= log p(X|W)，即L(q, W)是log p(X|W)的下界。
EM算法的過程可以分為兩階段，即E步和M步。假設初始時，參數取值為Wold。在E步，算法需要極大化下界L(q,Wold)，而下界在W確定后，是由分布q決定的，由式（10）可知，當KL(q||p)= 0，也就是q(Z) =p(Z|X, Wold)時，下界L(q, Wold)取到極大，這樣一來，下界L(q,Wold) = log p(X|Wold)。上面的推理也解釋了為什么在EM算法中要用到隱變量Z的后驗概率求解完全數據{X, Z}的對數似然函數的期望。
在M步，下界L中的q保持不變，即，q(Z) =p(Z|X, Wold)保持不變，求下界L(q, W)在W下的極大，以此得到Wnew，這就會使得下界L增大，因為下界L增大，由此帶來的結果就是log p(X|W)的增大，并且增大的幅度比下界L還大，原因是：在M步，q(Z) =p(Z|X, Wold)被固定，這里用的W還是更新前的值，即Wold，所以q(Z)不會等于p(Z|X,Wnew)，進而KL散度不為0，從而得到了剛才的結論：log p(X|W)增大的幅度比下界L還大。
從上面的分析可以看出，EM算法的兩步都是在極大化下界L，只不過固定的變量不一樣，在E步，固定住參數W，求下界在分布q下的極大；在M步，固定住分布q，然后求下界在W下的極大。第一次求出的下界的極大使得下界等于log p(X|Wold)，而第二次求出的下界的極大則使得log p(X|Wnew)變得更大，直到log p(X|Wnew)達到局部最優值，算法結束。
那么這里的分析是如何與之前的EM算法的步驟聯系起來的呢？
將q(Z) = p(Z|X, Wold)代入式（8），我們得到下式：
(11)
由式（11）我們可以看出，我們在E步和M步極大化的下界L，也就是我們的Q函數，這與上篇文章中EM算法的思路是一樣的，因此也可以認為EM算法的E步和M步是在極大化Q函數。值得注意的是，在式（11）中，要求解的參數W只出現在了log的里面，因此，如果log里面的概率分布屬于指數族，那么log就會將其抵消，從而簡化了求解過程。
最后需要注意的是，如果目標函數不是凸函數，那么EM算法的解將是局部最優解，所以在實際工程中，參數初始值的選取十分重要，常用的辦法是選取幾個不同的初始值進行迭代，然后對得到的值進行比較，從中選取最好的。