文档介绍：EM是我一直想深入学****的算法之一
2
———————————————————————————————— 作者：
———————————————————————————————— 日期：
个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
EM是我一直想深入学****的算法之一,第一次听说是在NLP课中的HMM那一节,为了解决HMM的参数估计问题,使用了EM算法。在之后的MT中的词对齐中也用到了。在Mitchell的书中也提到EM可以用于贝叶斯网络中.
下面主要介绍EM的整个推导过程。
1。 Jensen不等式
      回忆优化理论中的一些概念。设f是定义域为实数的函数，如果对于所有的实数x，，那么f是凸函数。当x是向量时，如果其hessian矩阵H是半正定的〔)，那么f是凸函数。如果或者，那么称f是严格凸函数。
      Jensen不等式表述如下：
      如果f是凸函数，X是随机变量，那么
     
      特别地，如果f是严格凸函数，那么当且仅当,也就是说X是常量。
      这里我们将简写为。
      如果用图表示会很清晰：
     
      图中，实线f是凸函数，X是随机变量,有0。5的概率是a，.〔就像掷硬币一样〕。X的期望值就是a和b的中值了，图中可以看到成立.
3
个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
      当f是〔严格)凹函数当且仅当—f是(严格)凸函数。
      Jensen不等式应用于凹函数时，不等号方向反向,也就是.
2。 EM算法
      给定的训练样本是，样例间独立，我们想找到每个样例隐含的类别z，能使得p(x，z)〔x,z〕的最大似然估计如下：
     
一般比拟困难，因为有隐藏变量z存在，但是一般确定了z后,求解就容易了。
      EM是一种解决存在隐含变量优化问题的有效方法。竟然不能直接最大化,我们可以不断地建立的下界〔E步〕，然后优化下界〔M步〕。这句话比拟抽象，看下面的。
      对于每一个样例i,让表示该样例隐含变量z的某种分布，满足的条件是。〔如果z是连续性的,那么是概率密度函数，需要将求和符号换做积分符号〕。比方要将班上学生聚类，假设隐藏变量z是身高,那么就是连续的高斯分布。如果按照隐藏变量是男女,那么就是伯努利分布了.
可以由前面阐述的内容得到下面的公式:
     
      〔1〕到〔2〕比拟直接,就是分子分母同乘以一个相等的函数.(2)到〔3〕利用了Jensen不等式,考虑到是凹函数(二阶导数小于0)，而且
4
个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
     
      就是的期望〔回想期望公式中的Lazy Statistician规那么〕
      设Y是随机变量X的函数〔g是连续函数),那么
      〔1) X是离散型随机变量，它的分布律为,k=1,2,….假设绝对收敛,那么有
     
      〔2〕 X是连续型随机变量，它的概率密度为，假设绝对收敛，那么有
     
      对应于上述问题，Y是，X是,是,g是到的映射。这样解释了式子〔2〕中的期望，再根据凹函数时的Jensen不等式：
     
可以得到〔3〕。
      这个过程可以看作是对求了下界。对于的选择，有多种可能，那种更好的?假设已经给定，，以逼近的真实值,那么什么时候算是调整好了呢？当不等式变成等式时，说明我们调整后的概率能够等价于
6