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算法的解将是局部最优解，所以在实际工程中，参数初始值的选取十分重要，常用的办法是选取几个不同的初始值进行迭代，然后对得到的值进行比较，从中选取最好的。