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

Jensen’s inequality

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

Jensen’s inequality 表述如下：

我们可以下面的图，这里 \(f\) 是一个凸函数，X 是一个随机变量，其有一半概率为 a, 一半概率为 b 。从这个例子中，我们可以看到 \(\mathrm{E}[f(X)] \geq f(\mathrm{E} X)\) 。

注意：如果 \(f\) 是一个凹函数，那么 \(-f\) 就是凸函数。因此对于凹函数存在 \(\mathrm{E}[f(X)] \leq f(\mathrm{E} X)\) 。

The EM algorithm

假设我们有一个包含 \(m\) 个独立样本的训练集数据 \(\left\{x^{(1)}, \ldots, x^{(m)}\right\}\) ，我们需要对一个模型 \(p(x, z)\) 进行拟合参数，其中似然函数为： \[ \begin{aligned} \ell(\theta) &=\sum_{i=1}^{m} \log p(x ; \theta) \\ &=\sum_{i=1}^{m} \log \sum_{z} p(x, z ; \theta) \end{aligned} \] 但是，我们想要找到 \(\theta\) 的最大似然估计值很难。这里，\(z^{(i)}\) 是隐藏的随机变量。如果我们已知 \(z^{(i)}\) ，那么获取最大似然估计值就很容易。

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

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

对于每个个体 \(i\) ，设 \(Q_{i}\) 为 \(z\) 的分布 \(\left(\sum_{z} Q_{i}(z)=1, Q_{i}(z) \geq 0 \right)\) ，因此 (如果 \(z\) 是连续变量，那么 \(Q_{i}\) 就改为概率密度， \(z\) 的求和式子改为积分 ，也就是 \(\sum_{z^{(i)}}\) 改为 \(\int_{z^{(i)}} * dz^{(i)}\) ) \[ \begin{aligned} \ell(\theta) = \sum_{i} \log p\left(x^{(i)} ; \theta\right) &=\sum_{i} \log \sum_{z^{(i)}} p\left(x^{(i)}, z^{(i)} ; \theta\right) \\ &=\sum_{i} \log \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)} \\ & \geq \sum_{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)} \end{aligned} \] 最后一步应用了 Jensen 不等式。因为，我们知道 \(\log(x)\) 是一个凹函数，因为 \(f^{\prime \prime}(x)=-1 / x^{2}<0\) 恒成立。并且，下式可视为 \(\left[\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}\right]\) 对 \(z^{(i)}\) 的期望 \[ \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right)\left[\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}\right] \] 通过 Jensen 不等式，我们有下式成立，得证上面公式的最后一步。这里的 \({z}^{(i)} \sim Q_{i}\) 下标表示这是对 \(z^{(i)}\) 的期望，其中 \(z^{(i)}\) 服从分布 \(Q_i\) 。

\[ f\left(\mathrm{E}_{z^{(i)} \sim Q_{i}}\left[\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}\right]\right) \geq \mathrm{E}_{z^{(i)} \sim Q_{i}}\left[f\left(\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}\right)\right] \] 现在，对于任何一个分布 \(Q_i\) , 我们都能得到一个 \(\ell(\theta)\) 的下限。我们对于 \(Q_i\) 存在很多种选择，那么我们选择哪一个呢？如果我们对参数 \(\theta\) 目前已有估计值，那么一个自然的选择是使得 \(\ell(\theta)\) 的下限与 \(\ell(\theta)\) 的值很接近。换句话说，我们想让上面的不等式针对特定的 \(\theta\) 变成等式，这样做可以使得每次迭代 \(\ell(\theta)\) 单调递增。

为了使得 \(\ell(\theta)\) 的下限等于 \(\ell(\theta)\) ，我们需要上面的 Jensen 不等式在特定的 \(\theta\) 时变成等式，也是就说要对常量求期望，即要求，对所有所有的 \(z^{(i)}\) ，下式均为一个固定的常数。 \[ \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}=c \] 做个变换得到： \[ \sum_{z}p\left(x^{(i)}, z^{(i)} ; \theta\right) = \sum_{z}Q_{i}\left(z^{(i)}\right)c \] 我们知道 \(\sum_{z} Q_{i}\left(z^{(i)}\right)=1\) ，因此我们得到 \[ \sum_{z}p\left(x^{(i)}, z^{(i)} ; \theta\right) = c \] 因此 \[ \begin{aligned} Q_{i}\left(z^{(i)}\right) &=\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{c} \\ &=\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{\sum_{z} p\left(x^{(i)}, z ; \theta\right)} \\ &=\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{p\left(x^{(i)} ; \theta\right)} \\ &=p\left(z^{(i)} \mid x^{(i)} ; \theta\right) \end{aligned} \] 因此，这里我们简单地将 \(Q_i\) 设定为 \(z^{(i)}\) 基于给定的 \(x^{(i)}\) 和 \(\theta\) 的后验分布 。

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

这里第二个式子还可以进一步简化： $$ \[\begin{aligned} \theta & := \operatorname{arg} \max_{\theta} \sum_{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)} \\ & := \operatorname{arg} \max_{\theta} \sum_{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \left( \log p\left(x^{(i)}, z^{(i)} ; \theta\right) - \log Q_{i}\left(z^{(i)}\right) \right) \\ & := \operatorname{arg} \max_{\theta} \sum_{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log p\left(x^{(i)}, z^{(i)} ; \theta\right) \quad \because \text{后一项与} \theta \text{无关，为常量}\\ & := \operatorname{arg} \max_{\theta} \sum_{i} \mathrm{E}_{z^{(i)}|x^{(i)}, \theta^{[t]}} \log p\left(x^{(i)}, z^{(i)} ; \theta\right) \\ & := \operatorname{arg} \max_{\theta} \mathrm{E}_{z^{(i)}|x^{(i)}, \theta^{[t]}} \left( \sum_{i} \log p\left(x^{(i)}, z^{(i)} ; \theta\right) \right) \\ \end{aligned}\]

$$ 其中， \(\theta^{[t]}\) 是上一轮的参数值。

还有一点小问题，因为 E 步是计算条件期望的，因此严格来说计算 \(\sum_{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log p\left(x^{(i)}, z^{(i)} ; \theta\right)\) 的过程应该放在 E 步。

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

EM 算法的收敛性

我们这里证明 EM 算法只会单调地增加对数似然值，即证明 \(\ell\left(\theta^{(t)}\right) \leq \ell\left(\theta^{(t+1)}\right)\) 。

首先，我们通过选择 \(Q_{i}\) ，我们使得 Jensen 不等式在当前参数下满足等式关系，因此，在求 \(\theta^{(t+1)}\) 过程中， 存在： \[ \ell\left(\theta^{(t)}\right)=\sum_{i} \sum_{z^{(i)}} Q_{i}^{(t+1)}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta^{(t)}\right)}{Q_{i}^{(t+1)}\left(z^{(i)}\right)} \] 当我们通过 M 步对上式右手项最大化，获得 \(\theta^{(t+1)}\) 后，此时： \[ \begin{aligned} \ell\left(\theta^{(t+1)}\right) & \geq \sum_{i} \sum_{z^{(i)}} Q_{i}^{(t+1)}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta^{(t+1)}\right)}{Q_{i}^{(t+1)}\left(z^{(i)}\right)} \quad \because \text{Jensen's inequality}\\ & \geq \sum_{i} \sum_{z^{(i)}} Q_{i}^{(t+1)}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta^{(t)}\right)}{Q_{i}^{(t+1)}\left(z^{(i)}\right)} \quad \because \theta^{(t+1)} = \arg \max _{\theta} \sum_{i} \sum_{z^{(i)}} Q_{i}^{(t+1)}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}^{(t+1)}\left(z^{(i)}\right)}\\ &=\ell\left(\theta^{(t)}\right) \end{aligned} \] 因此，我们证明 \[ \ell\left(\theta^{(t)}\right) \leq \ell\left(\theta^{(t+1)}\right) \] 因此，EM 算法只会使对数似然值不断增加，直至收敛。收敛的标准可以看两次迭代的 \(\ell(\theta)\) 的增加量是否低于给定阈值。

注意，如果我们定义： \[ J(Q, \theta)=\sum_{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)} \] 我们知道 \(\ell(\theta) \geq J(Q, \theta)\) 。 EM 算法可以视为对 \(J(Q, \theta)\) 的坐标上升法，其中 E 步可以视为固定 \(\theta\) 对 \(Q\) 的最大化（因为 \(\theta\) 固定，因为 \(J(Q, \theta)\) 的最大值就是 \(\ell(\theta)\) ，因此就是选择一个 \(Q\) 使得不等式成立），而 M 步可以视为固定 \(Q\) 对 \(\theta\) 的最大化（这一点很好理解 \(\ell(\theta)\) ）。

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

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