0 EM算法综述
迭代使用EM步骤，直至收敛。
可以有一些比较形象的比喻说法把这个算法讲清楚。比如说食堂的大师傅炒了一份菜，要等分成两份给两个人吃，显然没有必要拿来天平一点一点的精确的去称分量，最简单的办法是先随意的把菜分到两个碗中，然后观察是否一样多，把比较多的那一份取出一点放到另一个碗中，这个过程一直迭代地执行下去，直到大家看不出两个碗所容纳的菜有什么分量上的不同为止。EM算法就是这样，假设我们估计知道A和B两个参数，在开始状态下二者都是未知的，并且知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A。可以考虑首先赋予A某种初值，以此得到B的估计值，然后从B的当前值出发，重新估计A的取值，这个过程一直持续到收敛为止。
EM 算法是 Dempster，Laind，Rubin 于 1977 年提出的求参数极大似然估计的一种方法，它可以从非完整数据集中对参数进行 MLE 估计，是一种非常简单实用的学习算法。这种方法可以广泛地应用于处理缺损数据，截尾数据，带有噪声等所谓的不完全数据(incomplete data)。
假定集合Z = (X,Y)由观测数据 X 和未观测数据Y 组成，X 和Z = (X,Y)分别称为不完整数据和完整数据。假设Z的联合概率密度被参数化地定义为P(X,Y|Θ)，其中Θ表示要被估计的参数。Θ的最大似然估计是求不完整数据的对数似然函数L(X;Θ)的最大值而得到的：
L(Θ;X)= log p(X|Θ) = ∫log p(X,Y|Θ)dY ；
EM算法包括两个步骤：由E步和M步组成，它是通过迭代地最大化完整数据的对数似然函数Lc(X;Θ)的期望来最大化不完整数据的对数似然函数，其中：
Lc(X;Θ) =log p(X,Y |Θ) ；
假设在算法第t次迭代后Θ获得的估计记为Θ(t) ，则在(t+1)次迭代时，
E-步：计算完整数据的对数似然函数的期望，记为：
Q(Θ|Θ (t)) = E{Lc(Θ;Z)|X;Θ(t)}；
M-步：通过最大化Q(Θ|Θ(t) ) 来获得新的Θ 。
通过交替使用这两个步骤，EM算法逐步改进模型的参数，使参数和训练样本的似然概率逐渐增大，最后终止于一个极大点。直观地理解EM算法，它也可被看作为一个逐次逼近算法：事先并不知道模型的参数，可以随机的选择一套参数或者事先粗略地给定某个初始参数λ0 ，确定出对应于这组参数的最可能的状态，计算每个训练样本的可能结果的概率，在当前的状态下再由样本对参数修正，重新估计参数λ，并在新的参数下重新确定模型的状态，这样，通过多次的迭代，循环直至某个收敛条件满足为止，就可以使得模型的参数逐渐逼近真实参数。
EM算法的主要目的是提供一个简单的迭代算法计算后验密度函数，它的最大优点是简单和稳定，但容易陷入局部最优。
1. Jensen不等式
回顾优化理论中的一些概念。设f是定义域为实数的函数，如果对于所有的实数x，，那么f是凸函数。当x是向量时，如果其hessian矩阵H是半正定的（
），那么f是凸函数。如果
或者
，那么称f是严格凸函数。
Jensen不等式表述如下：
如果f是凸函数，X是随机变量，那么
特别地，如果f是严格凸函数，那么当且仅当
，也就是说X是常量。
这里我们将简写为
。
如果用图表示会很清晰：
图中，实线f是凸函数，X是随机变量，有0.5的概率是a，有0.5的概率是b。（就像掷硬币一样）。X的期望值就是a和b的中值了，图中可以看到成立。
当f是（严格）凹函数当且仅当-f是（严格）凸函数。
Jensen不等式应用于凹函数时，不等号方向反向，也就是。
2. EM算法
给定的训练样本是，样例间独立，我们想找到每个样例隐含的类别z，能使得p(x,z)最大。p(x,z)的最大似然估计如下：
第一步是对极大似然取对数，第二步是对每个样例的每个可能类别z求联合分布概率和。但是直接求一般比较困难，因为有隐藏变量z存在，但是一般确定了z后，求解就容易了。
EM是一种解决存在隐含变量优化问题的有效方法。竟然不能直接最大化，我们可以不断地建立
的下界（E步），然后优化下界（M步）。这句话比较抽象，看下面的。
对于每一个样例i，让表示该样例隐含变量z的某种分布，
满足的条件是
。（如果z是连续性的，那么
是概率密度函数，需要将求和符号换做积分符号）。比如要将班上学生聚类，假设隐藏变量z是身高，那么就是连续的高斯分布。如果按照隐藏变量是男女，那么就是伯努利分布了。
可以由前面阐述的内容得到下面的公式：
（1）到（2）比较直接，就是分子分母同乘以一个相等的函数。（2）到（3）利用了Jensen不等式，考虑到是凹函数（二阶导数小于0），而且
就是
的期望（回想期望公式中的Lazy Statistician规则）
设Y是随机变量X的函数（g是连续函数），那么
（1） X是离散型随机变量，它的分布律为，k=1,2,…。若
绝对收敛，则有
（2） X是连续型随机变量，它的概率密度为，若
绝对收敛，则有
对应于上述问题，Y是，X是
，
是
，g是
到
的映射。这样解释了式子（2）中的期望，再根据凹函数时的Jensen不等式：
可以得到（3）。
这个过程可以看作是对求了下界。对于
的选择，有多种可能，那种更好的？假设
已经给定，那么
的值就决定于
和
了。我们可以通过调整这两个概率使下界不断上升，以逼近
的真实值，那么什么时候算是调整好了呢？当不等式变成等式时，说明我们调整后的概率能够等价于
了。按照这个思路，我们要找到等式成立的条件。根据Jensen不等式，要想让等式成立，需要让随机变量变成常数值，这里得到：
c为常数，不依赖于。对此式子做进一步推导，我们知道
，那么也就有
，（多个等式分子分母相加不变，这个认为每个样例的两个概率比值都是c），那么有下式：
至此，我们推出了在固定其他参数后，
的计算公式就是后验概率，解决了
如何选择的问题。这一步就是E步，建立
的下界。接下来的M步，就是在给定
后，调整
，去极大化
的下界（在固定
后，下界还可以调整的更大）。那么一般的EM算法的步骤如下：
循环重复直到收敛 { （E步）对于每一个i，计算
（M步）计算
那么究竟怎么确保EM收敛？假定和
是EM第t次和t+1次迭代后的结果。如果我们证明了
，也就是说极大似然估计单调增加，那么最终我们会到达最大似然估计的最大值。下面来证明，选定
后，我们得到E步
这一步保证了在给定时，Jensen不等式中的等式成立，也就是
然后进行M步，固定，并将
视作变量，对上面的
求导后，得到
，这样经过一些推导会有以下式子成立：
解释第（4）步，得到时，只是最大化
，也就是
的下界，而没有使等式成立，等式成立只有是在固定
，并按E步得到
时才能成立。
况且根据我们前面得到的下式，对于所有的和
都成立
第（5）步利用了M步的定义，M步就是将调整到
，使得下界最大化。因此（5）成立，（6）是之前的等式结果。
这样就证明了会单调增加。一种收敛方法是
不再变化，还有一种就是变化幅度很小。
再次解释一下（4）、（5）、（6）。首先（4）对所有的参数都满足，而其等式成立条件只是在固定，并调整好Q时成立，而第（4）步只是固定Q，调整
，不能保证等式一定成立。（4）到（5）就是M步的定义，（5）到（6）是前面E步所保证等式成立条件。也就是说E步会将下界拉到与
一个特定值（这里
）一样的高度，而此时发现下界仍然可以上升，因此经过M步后，下界又被拉升，但达不到与
另外一个特定值一样的高度，之后E步又将下界拉到与这个特定值一样的高度，重复下去，直到最大值。
如果我们定义
从前面的推导中我们知道，EM可以看作是J的坐标上升法，E步固定
，优化
，M步固定
优化
。
3. 重新审视混合高斯模型
我们已经知道了EM的精髓和推导过程，再次审视一下混合高斯模型。之前提到的混合高斯模型的参数和
计算公式都是根据很多假定得出的，有些没有说明来由。为了简单，这里在M步只给出
和
的推导方法。
E步很简单，按照一般EM公式得到：
简单解释就是每个样例i的隐含类别为j的概率可以通过后验概率计算得到。
在M步中，我们需要在固定后最大化最大似然估计，也就是
这是将的k种情况展开后的样子，未知参数
和
。
固定和
，对
求导得
等于0时，得到
这就是我们之前模型中的的更新公式。
然后推导的更新公式。看之前得到的
在和
确定后，分子上面的一串都是常数了，实际上需要优化的公式是：
需要知道的是，还需要满足一定的约束条件就是
。
这个优化问题我们很熟悉了，直接构造拉格朗日乘子。
还有一点就是，但这一点会在得到的公式里自动满足。
求导得，
等于0，得到
也就是说再次使用
，得到
这样就神奇地得到了。
那么就顺势得到M步中的更新公式：
的推导也类似，不过稍微复杂一些，毕竟是矩阵。结果在之前的混合高斯模型中已经给出。
4. 总结
如果将样本看作观察值，潜在类别看作是隐藏变量，那么聚类问题也就是参数估计问题，只不过聚类问题中参数分为隐含类别变量和其他参数，这犹如在x-y坐标系中找一个曲线的极值，然而曲线函数不能直接求导，因此什么梯度下降方法就不适用了。但固定一个变量后，另外一个可以通过求导得到，因此可以使用坐标上升法，一次固定一个变量，对另外的求极值，最后逐步逼近极值。对应到EM上，E步估计隐含变量，M步估计其他参数，交替将极值推向最大。EM中还有“硬”指定和“软”指定的概念，“软”指定看似更为合理，但计算量要大，“硬”指定在某些场合如K-means中更为实用（要是保持一个样本点到其他所有中心的概率，就会很麻烦）。