摘自：以下课程

教师：Andrew Ng.

课程主页

http://cs229.stanford.edu/

课程材料

http://cs229.stanford.edu/materials.html

EM算法：  作者 Andrew Ng.

预备知识：Jensen不等式

如果f(x) 是个凸函数(convex function)，X是随机变量，那么  E[f(x)] >=f  (E[x]).  当且仅当 E[x]=X, 即X是常数时取等号。

注： 如果f(x)是个凹函数(concave function), 有 E[f(x)]<=f (E[x]).

EM 算法：

设 训练集{x^1,x^2,...x^m}  是m个独立的样本。我们希望拟合模型p(x,z)中的参数。p(x,z)的极大似然函数如下：

显然，如果直接求解参数theta的极大似然估计是非常困难的。这里z是隐随机变量（latent random variables).如果z已知，则参数theta的极大似然估计会很容易求出来。

如果直接最大化似然函数 L(theta)可能很困难，但是我们可以这么做，重复构建L函数的下界（E步），然后优化这个下界（M步）。

对每一个i，设Q_i(z)是随机变量z的某个分布，满足 ：

Q_i(z)>=0.

考虑下面式子：

其中最后一步应用了Jensen不等式。因为f(x)=log(x) 是凹函数(concave function), 并且

是变量  的期望，所以，由Jensen不等式知（3）式成立。

对于任意的分布Qi(z), 公式（3） 都给出了似然函数L（ $\theta$ ）的一个下界。Qi(z)的选择有多重多样。但是我们可以选择一种Qi(z)使得在给定 $\theta$ 的情况下，上面的不等式取等号。

在给定theta的情况下，为了是边界更紧，我们需要应用使得Jensen不等式取等号的条件。由Jensen不等式可知，只有当变量上常数（常数：是指和式子中的变量无关）时，取等号。我们令

其中c是和式子中的变量z无关的常数。由上面式子我们可以知道Q_i(z) 与 p（x^i,z^i,theta) 成正比例。

因为Q_i(z)是z的分布，满足

经过简单推导，我们有

这样我们可以简单地令Q_i等于，在给定x^i,和参数theta的情况下，随机变量z的后验分布分布即可。

通过这样选择Q_i，等式（3） 就给出了似然函数L的下界。（这个下界是我们想要最大化的）。这一步称为E步。

在M步中，我们希望通过设定新的theta来最大化等式（3）。重复E，M两步，就是我们所说的EM算法。具体算法流程如下：

算法大体流程已经知道。那么我们的算法是否收敛呢？

我们设theta^{t}, 和theta^{t+1}, 是EM算法中前后两次迭代的参数。我们现在证明

L(theta^{t}) <= L(theta^{t+1}).   该式可以证明EM算法总是单调增加来改进似然函数L的值。

证明的关键是我们如何选取Q_i. 在EM算法中，我们已经取：

这种取法，可以保证我们在等式（3）中应用Jensen不等式时，取等号。因此：

参数theta^{t+1} 之后就可以用来极大化上面等式的右边。

这样我们有：

对第一个不等式（4） ： 由于我们知道对任意的Q_i 和theta 我们都有

只要令 theta=theat^{t+1}即可得到（4）。

对于等式（5）:  我们使用如下事实：  theta^{t+1} 是使得取最大值的theta。

对于等式（6）， 是L（theta）的定义式。

因此，EM算法可以使得极大使然函数单调收敛。

注： 如果我们设

由上面的推导，我们知道  theat的似然函数L(theta)>=J(Q,theta).  EM 算法可以看做是J（Q， theta）函数在坐标系 Q-theta 下的递增。 E步是 沿着Q方向极大化， M步是沿着theta方向极大化。