()EM算法-大数据文档资料.docx

TheEMAlgorithm

JerryLead

csxulijie@

EM是我一直想深入学习的算法之一，第一次听说是在NLP课中的HMM那一节，为了解决HMM的参数估计问题，使用了EM算法。在之后的MT中的词对齐中也用到了。在Mitchell的书中也提到EM可以用于贝叶斯网络中。

下面主要介绍EM的整个推导过程。

1.Jensen不等式

回顾优化理论中的一些概念。设f是定义域为实数的函数，如果对于所有的实数x，f′′(x)≥0，那么f是凸函数。当x是向量时，如果其hessian矩阵H是半正定的（H≥0），那么f是凸函数。如果f′′(x)0或者H0，那么称f是严格凸函数。

Jensen不等式表述如下：

如果f是凸函数，X是随机变量，那么E,f(X)-≥f(EX)

特别地，如果f是严格凸函数，那么E,f(X)-=f(EX)当且仅当p(x=E,X-)=1，也就是说X是常量。

这里我们将f(E,X-)简写为f(EX)。如果用图表示会很清晰：

图中，实线f是凸函数，X是随机变量，有0.5的概率是a，有0.5的概率是b。（就像掷硬币一样）。X的期望值就是a和b的中值了，图中可以看到E,f(X)-≥f(EX)成立。

当f是（严格）凹函数当且仅当-f是（严格）凸函数。

Jensen不等式应用于凹函数时，不等号方向反向，也就是E,f(X)-≤f(EX)。

2.EM算法

给定的训练样本是*x(1),…,x(m)+，样例间独立，我们想找到每个样例隐含的类别z，能使得p(x,z)最大。p(x,z)的最大似然估计如下：

第一步是对极大似然取对数，第二步是对每个样例的每个可能类别z求联合分布概率和。但是直接求θ一般比较困难，因为有隐藏变量z存在，但是一般确定了z后，求解就容易了。

EM是一种解决存在隐含变量优化问题的有效方法。竟然不能直接最大化?(θ)，我们可以不断地建立?的下界（E步），然后优化下界（M步）。这句话比较抽象，看下面的。

对于每一个样例i，让Qi表示该样例隐含变量z的某种分布，Qi满足的条件是∑zQi(z)=1,Qi(z)≥0。（如果z是连续性的，那么Qi是概率密度函数，需要将求和符号换做积分符号）。比如要将班上学生聚类，假设隐藏变量z是身高，那么就是连续的高斯分布。如果按照隐藏变量是男女，那么就是伯努利分布了。

可以由前面阐述的内容得到下面的公式：

（1）到（2）比较直接，就是分子分母同乘以一个相等的函数。（2）到（3）利用了Jensen不等式，考虑到log(x)是凹函数（二阶导数小于0），而且

就是的期望（回想期望公式中的LazyStatistician规则）

设Y是随机变量X的函数，Y=g(X)（g是连续函数），那么

（1）X是离散型随机变量，它的分布律为P(X=xk)=pk，k=1,2,…。若∑=1g(xk)pk绝对

收敛，则有

E(Y)=E,g(X)-=1g(xk)pk

（2）X是连续型随机变量，它的概率密度为f(x)，若∫g(x)f(x)dx绝对收敛，则有

对应于上述问题，Y是，X是z(i)，Qi(z(i))是pk，g是z(i)到

的映射。这样解释了式子（2）中的期望，再根据凹函数时

的Jensen不等式：

可以得到（3）。

这个过程可以看作是对?(θ)求了下界。对于Qi的选择，有多种可能，那种更好的？假设θ已经给定，那么?(θ)的值就决定于Qi(z(i))和p(x(i),z(i))了。我们可以通过调整这两个概率使下界不断上升，以逼近?(θ)的真实值，那么什么时候算是调整好了呢？当不等式变成等式时，说明我们调整后的概率能够等价于?(θ)了。按照这个思路，我们要找到等式成立的条件。根据Jensen不等式，要想让等式成立，需要让随机变量变成常数值，这里得到：

c为常数，不依赖于z(i)。对此式子做进一步推导，我们知道∑zQi(z(i))=1，那么也就有∑zp(x(i),z(i);θ)=c，（多个等式分子分母相加不变，这个认为每个样例的两个概率比值都是c），那么有下式：

至此，我们推出了在固定其他参数θ后，Qi(z(i))的计算公式就是后验概率，解决了Qi(z(i))如何选择的问题。这一步就是E步，建立?(θ)的下界。接下来的M步，就是在给定Qi(z(i))后，调整θ,去极大化?(θ)的下界（