The EM Algorithm | 期望最大化算法 | SLie's Blog|琴弦之轮

引例：硬币模型

单硬币抛掷

假设某个盒子里有一枚硬币，抛掷该硬币只有两种结果，即正面（Head，H）和背面（Tail，T）。对抛硬币进行 $N$ 次独立重复实验，其中正面朝上的概率设为 $p$ 。记正面朝上为1，背面朝上为0，就不难得出每一次抛硬币的结果 $X\in\{0,1\}$ 且服从于二项分布，即 $\Pr\{X=x\}=p^x(1-p)^{1-x}$ ，其中 $p$ 是未知参数。

换句话说，我们将问题建模出了一个含参的概率模型，我们的目的就是求出这个参数。统计学知识告诉我们对参数 $p$ 的估计 $\hat p$ 可以通过极大似然估计（Maximum Likelihood Estimate，MLE）求得。对上述问题来说可以通过最大化似然函数求得参数：

$\hat p=\arg\max_p\prod_{i=1}^Np^{x_i}(1-p)^{1-x_i}$

通常我们可以采用取对数的方法简化求解过程，从而可以记目标函数为 $\mathscr l(p)$ ：

$\begin{aligned} \mathscr l(p)&=\log p\sum_{i=1}^Nx_i+\log(1-p)\sum_{i=1}^N(1-x_i)\\ &=N\bar x\log p+N(1-\bar x)\log(1-p) \end{aligned}$

令 $\mathrm d\mathscr l(p)/\mathrm d p=0$ 解得 $\hat p=\bar x$ ，是正面朝上占总试验次数的比例。

双硬币抛掷

现假设盒子中有 $A,B$ 两枚硬币，它们正面朝上的概率分别记为 $\theta_A,\theta_B$ 。以相同的概率随机选择一个硬币，进行抛硬币实验，共做 $N=5$ 次，每次实验独立的抛十次，结果如下图所示。

2coinTest

显然，在明确知道每一次实验抛的是 $A$ 还是 $B$ 的情况下，我们可以分别对 $A,B$ 利用单硬币抛掷的方法求得参数（图中a所示）。但是，如果每次实验时并不知道抛的是哪一个硬币，那么传统的 MLE 方法就不再适用了。解决这种问题我们可以使用 EM 算法（图中b所示），这就是本文的重点内容。

EM算法及其原理

EM算法，全称为 Expectation Maximization Algorithm，译作最大期望化算法或期望最大算法。它是一种从不完全数据或有数据丢失的数据集或者说含有隐变量（hidden variable）的概率参数模型中求解参数估计的迭代算法。

原理推导

对于观测数据 $\mathbf Y$ 和概率模型的参数 $\mathbf\Theta$ ，为求参数原本可通过最大化似然函数求得，或者是最大化通常所使用的对数似然函数（log-likelihood function）：

$\mathcal L(\mathbf\Theta;\mathbf Y)=\log P(\mathbf Y;\mathbf\Theta)$

其中分号 (;) 分隔自变量和参数， $P(\mathbf Y;\mathbf\Theta)$ 是全体观测样本 $y\in\mathbf Y$ 的联合分布，也是全体样本的似然函数。当每个样本都独立时， $P(\mathbf Y;\mathbf\Theta)=\prod_{y\in\mathbf Y} P(y;\mathbf\Theta)$ .

而引入隐变量 $\mathbf Z$ 之后，根据概率论的知识我们有：

$P(\mathbf Y;\mathbf\Theta)=\sum_{\mathbf Z}P(\mathbf {Y,Z};\mathbf\Theta)=\sum_{\mathbf Z}\left[P(\mathbf Y|\mathbf Z;\mathbf\Theta)\cdot P(\mathbf Z;\mathbf\Theta)\right]$

系联合分布 $P(\mathbf {Y,Z};\mathbf\Theta)$ 对 $\mathbf Y$ 的边缘分布（上述公式仅展示的是离散版本），也即是边缘似然（marginal likelihood）。

接下来，我们利用 Jensen不等式，引入一个函数 $Q(\mathbf Z)$ 来重审目标优化函数：

$\begin{aligned} \mathcal L&=\log\sum_{\mathbf Z}P(\mathbf {Y,Z};\mathbf\Theta)\\ &=\log\sum_{\mathbf Z}\left(Q(\mathbf Z)\cdot\frac{P(\mathbf {Y,Z};\mathbf\Theta)}{Q(\mathbf Z)}\right) \color{grey}{=\log\mathbb E_Q\left[\frac{P(\mathbf {Y,Z};\mathbf\Theta)}{Q(\mathbf Z)}\right]}\\ &\geq \sum_{\mathbf Z}\left(Q(\mathbf Z)\cdot\log\frac{P(\mathbf {Y,Z};\mathbf\Theta)}{Q(\mathbf Z)}\right) \color{grey}{=\mathbb E_Q\left[\log\frac{P(\mathbf {Y,Z};\mathbf\Theta)}{Q(\mathbf Z)}\right]} \end{aligned}$

其中保证 $\sum_{\mathbf Z}Q(\mathbf Z)=1$ . 事实上，我们可以把 $Q(\mathbf Z)$ 视为隐变量 $\mathbf Z$ 的概率分布，也就是 Jensen 不等式的概率版本（上式灰色部分，可适用于连续型分布的情况，用积分表示）。

显然不等式右边是目标函数的下界，在取等条件下，极大化这个下界就等同于极大化目标函数。并且还可以进一步将与 $\mathbf\Theta$ 无关的项摘掉，这并不影响极大化操作：

$\begin{aligned} \mathbf\Theta^*=\arg\max_{\mathbf\Theta}\mathcal L &=\arg\max_{\mathbf\Theta}\mathbb E_Q\left[\log\frac{P(\mathbf {Y,Z};\mathbf\Theta)}{Q(\mathbf Z)}\right]\\ &=\arg\max_{\mathbf\Theta}\mathbb E_Q\left[\log P(\mathbf {Y,Z};\mathbf\Theta)\right]\\ &=\arg\max_{\mathbf\Theta}\sum_{\mathbf Z}Q(\mathbf Z)\log P(\mathbf {Y,Z};\mathbf\Theta) \end{aligned}$

值得注意的是，此处的 $Q$ 函数是我们人工引入的只与 $\mathbf Z$ 有关的函数，唯有这样上述的推导才是正确的！

而根据 Jensen 不等式，当且仅当 $\frac{P(\mathbf {Y,Z};\mathbf\Theta)}{Q(\mathbf Z)}=c$ 为定值时，可以取等。从而我们可以推导确定 $Q$ 函数的表达式：

$\begin{aligned} Q(\mathbf Z) = \frac{P(\mathbf {Y,Z};\mathbf\Theta)}{\sum_{\mathbf Z}P(\mathbf {Y,Z};\mathbf\Theta)} = \frac{P(\mathbf {Y,Z};\mathbf\Theta)}{P(\mathbf Y;\mathbf\Theta)} = P(\mathbf Z|\mathbf Y;\mathbf\Theta) \end{aligned}$

这个表达式与 $\mathbf\Theta$ 有关，所以 EM 算法作为一个迭代算法，提出了一个 2-step 操作。在每次迭代时分别对 $\mathbf Z$ 的分布和 $\mathbf\Theta$ 的选取进行计算：

E step (Expectation)：固定当前迭代次数 $t$ 已得到的参数 $\mathbf\Theta^{(t)}$ 计算 $P(\mathbf Z|\mathbf Y;\mathbf\Theta^{(t)})$ ；
M step (Maximization)：固定 $\mathbf Z$ 的分布，最优化目标函数求得当前最优的参数 $\mathbf\Theta^{(t+1)}$ ，即 $\mathbf\Theta^{(t+1)}=\arg\max_{\mathbf\Theta}\mathcal L(\mathbf\Theta,\mathbf\Theta^{(t)})$

此外算法的收敛性同样需要我们思考：

EM算法能保证收敛吗？
EM算法如果收敛，那么能否保证收敛到全局最大值？

详见：机器学习-白板推导系列(十)-EM算法

算法流程

虽然推导看似很复杂，但是我们可以总结出这样一个流程：

输入观测样本数据 $\mathbf Y$ ，隐变量数据 $\mathbf Z$ ，联合分布(或联合密度函数) $P(\mathbf {Y,Z};\mathbf\Theta)$ 和条件分布(或条件密度函数) $P(\mathbf Z|\mathbf Y;\mathbf\Theta)$ 以及迭代次数 $T$ ;
随机初始化参数的初值 $\mathbf\Theta^{(0)}$ ；
E步→M步；
判断参数是否收敛，否则继续上一步操作。