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

Jensen’s inequality

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

Jensen’s inequality 表述如下：

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

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

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 算法，描述如下：

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

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

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

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

EM 算法的收敛性

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

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

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

因此，我们证明

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

注意，如果我们定义：

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

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

因此 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