文档介绍：EM 是我一直想深入学****的算法之一, 第一次听说是在 NL P 课中的 HM M 那一节, 为了解决 HM M 的参数估计问题,使用了 EM 算法。在之后的 MT 中的词对齐中也用到了。在 Mitchell 的书中也提到 EM 可以用于贝叶斯网络中。下面主要介绍 EM 的整个推导过程。 1. Jensen 不等式回顾优化理论中的一些概念。设 f 是定义域为实数的函数,如果对于所有的实数 x, ,那么 f 是凸函数。当 x 是向量时,如果其 hessian 矩阵 H 是半正定的( ), 那么 f 是凸函数。如果或者,那么称 f 是严格凸函数。 Jensen 不等式表述如下: 如果 f 是凸函数, X 是随机变量,那么特别地,如果 f 是严格凸函数,那么当且仅当,也就是说X 是常量。这里我们将简写为。如果用图表示会很清晰: 图中,实线 f 是凸函数, X 是随机变量,有 的概率是 a ,有 的概率是 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) 利用了 Jense n 不等式,考虑到是凹函数(二阶导数小于 0 ),而且就是的期望( 回想期望公式中的 Lazy Statistician 规则) 设Y 是随机变量 X 的函数(g 是连续函数),那么( 1) X 是离散型随机变量, 它的分布律为, k=1,2, …。若绝对收敛,则有( 2) X 是连续型随机变量,它的概率密度为,若绝对收敛,则有对应于上述问题,Y是,X是,是,g是到的映射。这样解释了式子( 2 )中的期望,再根据凹函数时的 Jensen 不等式: 可以得到( 3 )。这个过程可以看作是对求了下界。对于的选择, 有多种可能, 那种更好的?假设已经给定,那么的值就决定于和了。我们可以通过调整这两个概率使下界不断上升, 以逼近的真实值, 那么什么时候算是调整好了呢?当不等式变成等式时, 说明我们调整后的概率能够等价于了。按照这个思路, 我们要找到等式成立的条件。根据 Jense n 不等式,要想让等式成立,需要让随机变量变成常数值,这里得到: c 为常数,不依赖于。