Expectation-Maximization（EM）算法是机器学习里的经典算法之一，每次学习它的时候总有新的收获，因此在这里就总结一下。
问题提出
EM算法的目的是为了解决含隐变量模型的参数估计问题。那么含隐变量模型的参数估计难在哪里呢，这里以高斯混合模型（Gaussian Mixture Model, GMM）为例。
GMM模型的基本假设是这样的，我们得到的数据是由多个高斯生成的，那么这里涉及到两个概率分布:
- $p(Y=i;\pi)$: 选择第i个高斯的概率
- $p(X=x_n \vert Y=i;\mu_i, \sigma_i)$ : 用第i个高斯生成数据点 $x_n$ 的概率
如果 $Y$ 对于我们是可观测的，也就是说我们可以知道各个数据点是由哪一个高斯生成的，那么模型参数估计就十分简单，问题就变成了多个单高斯的参数估计问题，用 MLE 可以直接求解。其 log-likelihood 可以写成如下形式, 其中 $\pi$ 是控制 $Y$ 的先验概率分布的参数：
但是，如果 $Y$ 对于我们是不可观测的，我们便无法直接计算联合概率 $p(y_n, x_n)$，因而只能用边缘概率 $p(x_n)=\sum_K p(y_n=k, x_n)$ 带代替。此时，其 log-likelihood 则变为：
可以看出，由于隐变量的存在，所有的参数耦合到了一起，使得直接求解变得十分困难。
但求解困难并不是说这个公式不能求解，设想一下，如果我们直接对上式计算偏导，然后令偏导数等于0，来求解参数。因为有对数函数的存在，所以那个对于隐变量 $y_n=k$ 的求和项会存在于分母当中，因此分母中会包含每个高斯的 $\mu, \sigma$ ，使得我们无法像普通的 MLE 问题那样，直接计算出参数的解析解。
但实际上到了这一步，我们还有多种选择，比如使用梯度下降法、牛顿法等等。
EM算法跟梯度下降法的相似之处在于，它也是一个参数迭代的算法，而且并没有改变我们是在优化一个非凸函数的事实。不过相比梯度下降法，EM算法有着以下优点：
- 更快的收敛速度
- 保证算法可以收敛（虽然可能收敛到局部最优值）
- 不需要设置学习率之类的超参数
基本思路
回想一下，如果隐变量可观测，那么我们可以计算 complete log-likelihood:
EM算法聪明之处就在于，既然隐变量可不观测，那我们就用它的期望来代替，也就是用 expected complete log-likelihood 来代替 complete log-likelihood（使用 $z$ 代替 $y$ 表示变量不可观测）:
因此，EM算法分为以下两步：
- E-step: 根据上一轮的参数 $\theta_{t}$ ，计算隐变量的期望值：
这也是为什么这一步叫做 Expectation 的原因。至于为什么隐变量的期望值就是这个后验概率，后面再做解释。
- M-step: 当隐变量都用它们的期望代替后，计算参数的值就和正常的 MLE 没有什么区别了。这也是为什么这一步叫做 Maximization 的原因。
简单来说，对于混合高斯模型，我们不知道的隐变量是每个数据点 $x_i$ 究竟属于哪一个高斯 $z^k$ 。那我们在 E-step 计算的后验概率：
上式的实际含义就是，数据点 $x_i$ 属于 $z^k$ 的概率是多少。不同于 KMeans 算法，我们这里做的是一种软分配（soft assignment），也就是说对于每个数据点，不强行规定它属于哪个聚类（高斯），而是计算它属于各个聚类的概率是多少。当我们计算出了这个概率之后，就相当于对数据做了一遍标注，消去了隐变量。然后在 M-step 我们就可以像普通的 MLE 算法那样，求解模型的参数。
理论证明
这里主要用来填补上一节留下的两个坑：
- 为什么隐变量的期望值可以用后验概率的形式来计算
- 使用 expected complete log-likelihood 来代替 complete log-likelihood 的方法真的没问题吗？
这里就需要回到我们之前遇到的问题，就是有了隐变量之后计算 log-likelihood 时参数会耦合到一起：
解决这个问题需要用到 jensen 不等式，对于凹函数 $f$，有：
因此：
上式第二项与优化参数 $\theta$ 无关，求解的时候可以约去。
首先，我们可以看到，通过 jensen 不等式，我们实现了参数的解耦（把 $log$ 挪到了第二个求和符号的里面）。而解耦之后的结果，是比较容易直接求解的。
其次，在这里，我们构造了一个分布 $Q_n(z_n^k)$，其实对于任意一个分布，只要满足 $\sum_k Q_n(z_n^k) = 1$，都可以使得 jensen 不等式成立。那现在我们就面临一个问题：我们应该如何选取一个合适的 $Q$ 分布？
解决这个问题需要再次回想我们的优化目标：最大化 log-likelihood。从上述不等式可以看出，我们已经找到了 $l(\theta; X)$ 的下界。一个很自然的想法就是，我们让不等式的等号成立，相当于让一个函数等于它的下界，然后优化这个下界，就可以达到优化函数的目的。
基于这个思想，我们进一步思考，让 jensen 不等式等号成立的条件就是：
也就是说
又因为 $\sum_k Q_n(z_n^k) = 1$，我们可以得到：
看到这里是否有一种似曾相识的感觉，没错，这里的 $Q_n(z_n^k)$ 实际上就是隐变量的期望，而它的形式正是后验概率！
现在来填第二个坑，使用这种不等式的做法真的可以优化对数似然 $l(\theta; X)$ 吗，从直觉上也可以想到答案肯定是 yes ,但是需要一点理论证明：
第一个不等式成立的原因是 jensen 不等式，第二个不等式成立的原因是，$\theta^{t+1}$ 是在 M-step 通过最大化 $\sum_N \sum_K Q_n(z_n^k) log \frac{p(x_n, z_n^k; \theta^{t})}{Q_n(z_n^k)}$ 得到的。所以我们能保证 EM 算法的每次迭代都不会降低对数似然。但是这并不能保证 EM 算法能收敛到全局最优。
总结
再次回顾一下 EM 算法的核心思想，为了解决因为隐变量而产生的参数耦合问题，EM 算法使用 expected complete log log-likelihood 代替 complete log-likelihood，通过 jensen 不等式，证明了：
EM 算法中的 E-step 就是为了使等号成立，并计算隐变量的期望就是其后验概率。 M-step 则是优化 $\langle l(\theta; X, z) \rangle$ ，因为已经将参数解耦，可以直接使用 MLE 的方法，求解十分方便。
后记
本篇文章旨在以一种直观的方式理解 EM 算法，因此不涉及到具体模型的公式推导（如 KMeans, GMM, HMM）。但理解了 EM 算法并不能代表就可以熟练使用它来求解各种模型了，某些模型（如HMM）的具体求解过程比 EM 算法本身还要复杂很多，因此还需要学习一个。
