EM算法
在 最大似然估计 这篇文章中，我们介绍了一种通过样本来估计模型参数的方法。现在，我们把问题变得复杂一些，假设 $\lbrace x_1, x_2, …, x_n \rbrace$ 来自两个不同的正态分布 $N(\mu_1, \sigma_1^2)$ 和 $N(\mu_2, \sigma_2^2)$，如果我们知道每一个样本来自哪个分布，那么估计参数是一件容易的事情，使用最大似然估计方法就可以了。但不幸的是，我们不知道每个样本来自哪个分布，也就是说，每个样本除了自身之外还有一个隐变量 $z_i$, $z_i(j) = 1$ 表示样本 $x_i$ 来自第 $j$ 个正态分布，否则 $z_i(j) = 0$。为了解决这个问题，我们可以使用EM算法。
EM算法
EM(Expectaion-Maximum)算法也称期望最大化算法，是机器学习领域非常重要的算法之一，常被用来解决存在隐含变量的优化问题。EM算法的思想就是，如果有两个参数A和B未知，但是如果知道了A就很容易估算B的值，同样知道了B的值也很容易估算A的值，那么可以考虑先赋予A某一个初始值，以此为基础估算B的值，并以B的值为基础重新估算A的值；如此重复，直到收敛为止。
回到上面的例子，我们希望找到一个参数 $\theta$, 使得该序列发生的概率最大。我们可以先写出对数似然函数
与最大似然不同的是，这里多了隐变量 $z_i$。我们假设隐变量 $z_i$ 符合某种分布 $Q_i$, $Q_i(z_i) \geq 0$ 且 $\sum_{z_i} Q_i(z_i) = 1$。上述对数似然可以改写为
\[L(\theta) = \sum_{i} \ln \sum_{z_i} Q_i(z_i) \frac{p(x_i, z_i \vert \theta)}{Q_i(z_i)}\] \[L(\theta) \geq \sum_i \sum_{z_i} Q_i(z_i) \ln \frac{p(x_i, z_i \vert \theta)}{Q_i(z_i)}\]这一步可以看做是求了 $L(\theta)$ 的一个下界，这个下界主要由 $Q_i(z_i)$ 和 $p(x_i,z_i \vert \theta)$ 确定。我们可以通过调整 $\theta$ 来不断提高这个下界的值，直到等号成立。那么等号什么时候成立呢？根据Jensen不等式，等号成立的条件是 $\frac{p(x_i, z_i \vert \theta)}{Q_i(z_i)}$ 为常数，即
\[\frac{p(x_i, z_i \vert \theta)}{Q_i(z_i)} = c\]由于 $\sum_{z_i} Q_i(z_i) = 1$, 可以很容易得到
\[\sum_{z_i} p(x_i, z_i \vert \theta) = c \sum_{z_i} Q_i(z_i) = c\] \[\begin{split} Q_i(z_i) & = \frac{p(x_i, z_i \vert \theta)}{c} \\ & = \frac{p(x_i, z_i \vert \theta)}{\sum_{z_i} p(x_i, z_i \vert \theta)} \\ & = \frac{p(x_i, z_i \vert \theta)}{p(x_i \vert \theta)} \\ & = p(z_i \vert x_i, \theta) \end{split}\]到这一步，我们解决了 $Q_i(z_i)$ 如何选择的问题，这一步就是E步，确定了 $L(\theta)$ 的下界。接下来需要求解 $\theta$ 以最大化这个下界，这一步就是M步。EM算法的过程总结如下:
- initialize $\theta$
- repeat until convergence $\lbrace$
- E-step:
- M-step:
$\rbrace$
在M步，由于 $Q_i(z_i)$ 已经确定，故优化目标可以简化为
\[\begin{split} \theta & = \mathop{argmax}_{\theta} \sum_i \sum_{z_i} Q_i(z_i) \ln \frac{p(x_i, z_i \vert \theta)}{Q_i(z_i)} \\ & = \mathop{argmax}_{\theta} \lbrace \sum_i \sum_{z_i} Q_i(z_i) \ln p(x_i, z_i \vert \theta) - \underbrace{\sum_i \sum_{z_i} Q_i(z_i) \ln Q_i(z_i)}_{const} \rbrace \\ & = \mathop{argmax}_{\theta} \sum_i \sum_{z_i} Q_i(z_i) \ln p(x_i, z_i \vert \theta) \\ & = \mathop{argmax}_{\theta} L(\theta, \theta^j) \end{split}\]EM算法收敛性思考
EM算法是一个迭代算法，算法是否收敛、能否收敛到最大值关系到算法是否正确。为了证明算法的收敛性，我们需要证明在迭代的过程中，对数似然函数的值一直在增大，即
\[\sum_i \ln p(x_i \vert \theta^{j+1}) \geq \sum_i \ln p(x_i \vert \theta^j)\]令
\[H(\theta, \theta^j) = \sum_i \sum_{z_i} p(z_i \vert x_i, \theta^j) \ln p(z_i \vert x_i, \theta)\]上述两式相减有
\[\begin{split} L(\theta, \theta^j) - H(\theta, \theta^j) & = \sum_i \sum_{z_i} p(z_i \vert x_i, \theta^j) \ln \frac{p(x_i, z_i \vert \theta)}{p(z_i \vert x_i, \theta)} \\ & = \sum_i \sum_{z_i} p(z_i \vert x_i, \theta^j) \ln p(x_i \vert \theta) \\ & = \sum_i \ln p(x_i \vert \theta) \end{split}\]则 \(\begin{split} \sum_i \ln p(x_i \vert \theta^{j+1}) - \sum_i \ln p(x_i \vert \theta^j) & = (L(\theta^{j+1}, \theta^j) - H(\theta^{j+1}, \theta^j)) - (L(\theta^j, \theta^j) - H(\theta^j, \theta^j)) \\ & = (L(\theta^{j+1}, \theta^j) - L(\theta^j, \theta^j)) - (H(\theta^{j+1}, \theta^j) - H(\theta^j, \theta^j)) \end{split}\)
由于 $\theta^{j+1}$ 使得 $L(\theta, \theta^j)$ 极大，因此有
\[L(\theta^{j+1}, \theta^j) - L(\theta^j, \theta^j) \geq 0\]对于后一部分有
\[\begin{split} H(\theta^{j+1}, \theta^j) - H(\theta^j, \theta^j) & = \sum_i \sum_{z_i} p(z_i \vert x_i, \theta^j) \ln \frac{p(z_i \vert x_i, \theta^{j+1})}{p(z_i \vert x_i, \theta^j)} \\ & \leq \sum_i \ln \sum_{z_i} p(z_i \vert x_i, \theta^j) \frac{p(z_i \vert x_i, \theta^{j+1})}{p(z_i \vert x_i, \theta^j)} \\ & = \sum_i \ln \sum_{z_i} p(z_i \vert x_i, \theta^{j+1}) \\ & = 0 \end{split}\]故有
\[\sum_i \ln p(x_i \vert \theta^{j+1}) - \sum_i \ln p(x_i \vert \theta^j) \geq 0\]从而证明EM算法是收敛的，但是并不能保证收敛到全局最大值，可能只是局部极大值，这点和梯度下降比较相似。当然如果优化目标 $L(\theta, \theta^j)$ 是凸函数，EM算法可以保证优化到全局最大值。
参考
[1]. https://www.cnblogs.com/pinard/p/6912636.html