《EM是我直想深入学习的算法之》由会员分享，可在线阅读，更多相关《EM是我直想深入学习的算法之（9页珍藏版）》请在金锄头文库上搜索。
1、EM 是我一直想深入学习的算法之一，第一次听说是在 NLP 课中的 HMM 那一节，为了解决HMM 的参数估计问题，使用了 EM 算法。在之后的 MT 中的词对齐中也用到了。在 Mitchell的书中也提到 EM 可以用于贝叶斯网络中。下面主要介绍 EM 的整个推导过程。1. Jensen 不等式不等式回顾优化理论中的一些概念。设 f 是定义域为实数的函数，如果对于所有的实数 x，那么 f 是凸函数。当 x 是向量时，如果其 hessian 矩阵 H 是半正定的（），那么 f 是凸函数。如果或者，那么称 f 是严格凸函数。Jensen 不等式表述如下：如果 f 是凸函数，X 是随机变量，那么特
2、别地，如果 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
3、求联合分布概率和。但是直接求 一般比较困难，因为有隐藏变量 z 存在，但是一般确定了 z 后，求解就容易了。EM 是一种解决存在隐含变量优化问题的有效方法。竟然不能直接最大化，我们可以不断地建立 的下界（E 步），然后优化下界（M 步）。这句话比较抽象，看下面的。对于每一个样例 i，让表示该样例隐含变量 z 的某种分布，满足的条件是。（如果 z 是连续性的，那么是概率密度函数，需要将求和符号换做积分符号）。比如要将班上学生聚类，假设隐藏变量 z 是身高，那么就是连续的高斯分布。如果按照隐藏变量是男女，那么就是伯努利分布了。可以由前面阐述的内容得到下面的公式：（1）到（2）比较直接，就是分子分母
4、同乘以一个相等的函数。（2）到（3）利用了Jensen 不等式，考虑到是凹函数（二阶导数小于 0），而且就是的期望（回想期望公式中的 Lazy Statistician 规则）设 Y 是随机变量 X 的函数（g 是连续函数），那么（1） X 是离散型随机变量，它的分布律为，k=1,2,。若绝对收敛，则有（2） X 是连续型随机变量，它的概率密度为，若绝对收敛，则有对应于上述问题，Y 是，X 是，是，g 是到的映射。这样解释了式子（2）中的期望，再根据凹函数时的 Jensen 不等式：可以得到（3）。这个过程可以看作是对求了下界。对于的选择，有多种可能，那种更好的？假设已经给定，那么的值就决定于
5、和了。我们可以通过调整这两个概率使下界不断上升，以逼近的真实值，那么什么时候算是调整好了呢？当不等式变成等式时，说明我们调整后的概率能够等价于了。按照这个思路，我们要找到等式成立的条件。根据Jensen 不等式，要想让等式成立，需要让随机变量变成常数值，这里得到：c 为常数，不依赖于。对此式子做进一步推导，我们知道，那么也就有，（多个等式分子分母相加不变，这个认为每个样例的两个概率比值都是c），那么有下式：至此，我们推出了在固定其他参数 后，的计算公式就是后验概率，解决了如何选择的问题。这一步就是 E 步，建立的下界。接下来的 M 步，就是在给定后，调整 ，去极大化的下界（在固定后，下界还可以
6、调整的更大）。那么一般的 EM 算法的步骤如下： 循环重复直到收敛 （E 步）对于每一个 i，计算（M 步）计算那么究竟怎么确保 EM 收敛？假定和是 EM 第 t 次和 t+1 次迭代后的结果。如果我们证明了，也就是说极大似然估计单调增加，那么最终我们会到达最大似然估计的最大值。下面来证明，选定后，我们得到 E 步这一步保证了在给定时，Jensen 不等式中的等式成立，也就是然后进行 M 步，固定，并将视作变量，对上面的求导后，得到，这样经过一些推导会有以下式子成立：解释第（4）步，得到时，只是最大化，也就是的下界，而没有使等式成立，等式成立只有是在固定 ，并按 E 步得到时才能成立。况且根
7、据我们前面得到的下式，对于所有的和 都成立第（5）步利用了 M 步的定义，M 步就是将调整到，使得下界最大化。因此（5）成立，（6）是之前的等式结果。这样就证明了会单调增加。一种收敛方法是不再变化，还有一种就是变化幅度很小。再次解释一下（4）、（5）、（6）。首先（4）对所有的参数都满足，而其等式成立条件只是在固定 ，并调整好 Q 时成立，而第（4）步只是固定 Q，调整 ，不能保证等式一定成立。（4）到（5）就是 M 步的定义，（5）到（6）是前面 E 步所保证等式成立条件。也就是说 E 步会将下界拉到与一个特定值（这里）一样的高度，而此时发现下界仍然可以上升，因此经过 M 步后，下界又被拉升
8、，但达不到与另外一个特定值一样的高度，之后 E 步又将下界拉到与这个特定值一样的高度，重复下去，直到最大值。如果我们定义从前面的推导中我们知道，EM 可以看作是 J 的坐标上升法，E 步固定 ，优化 ，M 步固定 优化 。3. 重新审视混合高斯模型重新审视混合高斯模型我们已经知道了 EM 的精髓和推导过程，再次审视一下混合高斯模型。之前提到的混合高斯模型的参数和 计算公式都是根据很多假定得出的，有些没有说明来由。为了简单，这里在 M 步只给出 和 的推导方法。E 步很简单，按照一般 EM 公式得到：简单解释就是每个样例 i 的隐含类别为 j 的概率可以通过后验概率计算得到。在 M 步中，我们需
9、要在固定后最大化最大似然估计，也就是这是将的 k 种情况展开后的样子，未知参数和。固定和，对求导得等于 0 时，得到这就是我们之前模型中的 的更新公式。然后推导的更新公式。看之前得到的在 和 确定后，分子上面的一串都是常数了，实际上需要优化的公式是：需要知道的是，还需要满足一定的约束条件就是。这个优化问题我们很熟悉了，直接构造拉格朗日乘子。还有一点就是，但这一点会在得到的公式里自动满足。求导得，等于 0，得到也就是说再次使用，得到这样就神奇地得到了 。那么就顺势得到 M 步中的更新公式：的推导也类似，不过稍微复杂一些，毕竟是矩阵。结果在之前的混合高斯模型中已经给出。4. 总结总结如果将样本看作
10、观察值，潜在类别看作是隐藏变量，那么聚类问题也就是参数估计问题，只不过聚类问题中参数分为隐含类别变量和其他参数，这犹如在 x-y 坐标系中找一个曲线的极值，然而曲线函数不能直接求导，因此什么梯度下降方法就不适用了。但固定一个变量后，另外一个可以通过求导得到，因此可以使用坐标上升法，一次固定一个变量，对另外的求极值，最后逐步逼近极值。对应到 EM 上，E 步估计隐含变量，M 步估计其他参数，交替将极值推向最大。EM 中还有“硬”指定和“软”指定的概念，“软”指定看似更为合理，但计算量要大，“硬”指定在某些场合如 K-means 中更为实用（要是保持一个样本点到其他所有中心的概率，就会很麻烦）。另
11、外，EM 的收敛性证明方法确实很牛，能够利用 log 的凹函数性质，还能够想到利用创造下界，拉平函数下界，优化下界的方法来逐步逼近极大值。而且每一步迭代都能保证是单调的。最重要的是证明的数学公式非常精妙，硬是分子分母都乘以 z 的概率变成期望来套上Jensen 不等式，前人都是怎么想到的。在 Mitchell 的 Machine Learning 书中也举了一个 EM 应用的例子，明白地说就是将班上学生的身高都放在一起，要求聚成两个类。这些身高可以看作是男生身高的高斯分布和女生身高的高斯分布组成。因此变成了如何估计每个样例是男生还是女生，然后在确定男女生情况下，如何估计均值和方差，里面也给出了公式，有兴趣可以参考。
