EM算法

EM 算法 (expectation-maximization) 是获得最大似然估计值的一种迭代算法,当原始的似然函数很复杂时,无法直接得到显式解时,我们可以选择使用 EM 算法。

Jensen’s inequality

假设 是一个定义域为实数的函数,只有当 恒成立是, 才是一个凸函数。如果 输入是一个向量,那么其为凸函数的条件一般化为,只有当其 hessian 矩阵是一个半正定矩阵成立 ()。 如果 () ,那么我们称 是一个严格凸函数 (strictly convex)

Jensen’s inequality 表述如下:

1

我们可以下面的图,这里 是一个凸函数,X 是一个随机变量,其有一半概率为 a, 一半概率为 b 。从这个例子中,我们可以看到

1

注意:如果 是一个凹函数,那么 就是凸函数。因此对于凹函数存在

The EM algorithm

假设我们有一个包含 个独立样本的训练集数据 ,我们需要对一个模型 进行拟合参数,其中似然函数为:

但是,我们想要找到 的最大似然估计值很难。这里, 是隐藏的随机变量。如果我们已知 ,那么获取最大似然估计值就很容易。

在这种情况下,EM 算法提供了一种估计参数的最大似然估计值的有效方法(哈哈哈,估计最大似然估计值,“估计估计值”,双重估计)。

Maximizing explicitly might be difficult,our strategy will be to instead repeatedly construct a lower-bound on (E-step), and then optimize that lower-bound (M-step).

对于每个个体 ,设 的分布 ,因此 (如果 是连续变量,那么 就改为概率密度, 的求和式子改为积分 ,也就是 改为 )

最后一步应用了 Jensen 不等式。因为,我们知道 是一个凹函数,因为 恒成立。并且,下式可视为 的期望

通过 Jensen 不等式,我们有下式成立,得证上面公式的最后一步。这里的 下标表示这是对 的期望,其中 服从分布

现在,对于任何一个分布 , 我们都能得到一个 的下限。我们对于 存在很多种选择,那么我们选择哪一个呢?如果我们对参数 目前已有估计值,那么一个自然的选择是使得 的下限与 的值很接近。换句话说,我们想让上面的不等式针对特定的 变成等式,这样做可以使得每次迭代 单调递增。

为了使得 的下限等于 ,我们需要上面的 Jensen 不等式在特定的 时变成等式,也是就说要对常量求期望,即要求,对所有所有的 ,下式均为一个固定的常数。

做个变换得到:

我们知道 ,因此我们得到

因此

因此,这里我们简单地将 设定为 基于给定的 后验分布

现在,通过我们选择的 ,我们得到了想要最大化的 的下限,这是 E 步。在 M 步中,我们则基于 最大化 的下限公式,得到一组新的参数 。重复上面的步骤就是 EM 算法,描述如下:

1

这里第二个式子还可以进一步简化:

其中, 是上一轮的参数值。

还有一点小问题,因为 E 步是计算条件期望的,因此严格来说计算 的过程应该放在 E 步。

那么,我们如何知道EM算法是否收敛呢?

EM 算法的收敛性

我们这里证明 EM 算法只会单调地增加对数似然值,即证明

首先,我们通过选择 ,我们使得 Jensen 不等式在当前参数下满足等式关系,因此,在求 过程中, 存在:

当我们通过 M 步对上式右手项最大化,获得 后,此时:

因此,我们证明

因此,EM 算法只会使对数似然值不断增加,直至收敛。收敛的标准可以看两次迭代的 的增加量是否低于给定阈值。

注意,如果我们定义:

我们知道 。 EM 算法可以视为对 的坐标上升法,其中 E 步可以视为固定 的最大化(因为 固定,因为 的最大值就是 ,因此就是选择一个 使得不等式成立),而 M 步可以视为固定 的最大化(这一点很好理解 )。

下图为形象化的解释,其中红线为

1

因此 EM 算法一定会收敛,只不过收敛的位置可能是局部最优解

参考文献

  1. Ng A. CS229 Lecture notes[J]. CS229 Lecture notes, 2000, 1(1): 1-3.

  2. https://www.cnblogs.com/pinard/p/6912636.html

  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2019-2023 Vincere Zhou
  • 访问人数: | 浏览次数:

请我喝杯茶吧~

支付宝
微信