Expectation-Maximization Algorithm/zh

Article
Topic area	Machine Learning
Prerequisites	Maximum Likelihood Estimation, Latent Variable Models, Kullback-Leibler Divergence

期望-最大化（EM）是一种迭代算法，用于在含有未观测潜变量的统计模型中求解参数的最大似然估计或最大后验（MAP）估计。每一轮迭代交替执行两步：在当前潜变量后验下计算数据的期望对数似然（E 步），以及关于参数最大化该期望（M 步）。EM 是拟合混合模型、隐马尔可夫模型、因子分析模型以及许多其他潜变量模型的标准工具，也是现代变分推断理论的基础。

概述

许多具有实际意义的模型都假设每个观测数据点 $ x $ 是与一个从不直接观测的潜变量 $ z $ 联合生成的。例子包括高斯混合模型中的聚类指派、隐马尔可夫模型中的隐状态序列、Latent Dirichlet Allocation 中某个词的主题，以及因子分析中的共享因子。边际似然

$ p(x \mid \theta) = \sum_{z} p(x, z \mid \theta) \quad \text{or} \quad \int p(x, z \mid \theta)\, dz $

通常没有可处理的闭式表达，而直接对 $ \log p(x \mid \theta) $ 进行梯度上升又很不方便，因为求和或积分被放在对数函数内部。

EM 通过引入后验 $ p(z \mid x, \theta) $ 作为耦合分布来绕开这一困难。在每一轮迭代中，算法用当前参数计算（或界定）该后验，然后优化一个替代目标，在其中潜变量实际上已被“填补”进去。Dempster、Laird 与 Rubin 在 1977 年给出了该方法的命名和一般化表述，但若干特殊情形早在数十年前已出现于遗传学、信号处理和聚类等文献中。

EM 之所以具有吸引力，是因为每次迭代都保证边际对数似然不会减小，M 步通常可归结为常见的完全观测最大似然问题，而且算法既不需要学习率也不需要步长。它是 Majorization-Minimization 类方法的典范，也是现代 Variational Inference 的直接前身。

直观理解

EM 可以通过一个简单的“鸡生蛋、蛋生鸡”的观察来理解。若潜变量 $ z $ 已知，那么对 $ \theta $ 的拟合就退化为完整数据 $ (x, z) $ 上的标准 Maximum Likelihood Estimation。反过来，若 $ \theta $ 已知，则后验 $ p(z \mid x, \theta) $ 会告诉我们潜变量最可能是什么。两者在一开始都不可得，因此 EM 采用自举的方式：用当前参数对潜变量做一个软的猜测，再像该猜测为真那样重新拟合参数，如此反复迭代。

“软”这一限定词很关键。与k 均值这类经典的硬指派启发式不同，EM 并不把 $ z $ 锁定为单一取值，而是计算潜变量上的一个分布，并以该分布对 M 步进行加权。正是这种软指派使得边际对数似然非递减，也使 EM 区别于在硬指派目标上做坐标下降的方法。

形式化表述

证据下界

设 $ q(z) $ 是潜变量上的任意一个分布。由延森不等式可得证据下界（ELBO）：

$ {\displaystyle \log p(x \mid \theta) \;\geq\; \mathbb{E}_{q(z)}\!\left[\log p(x, z \mid \theta)\right] - \mathbb{E}_{q(z)}\!\left[\log q(z)\right] \;\equiv\; \mathcal{L}(q, \theta).} $

边际对数似然与 ELBO 之间的差正好是 $ q(z) $ 到真实后验之间的 Kullback-Leibler Divergence：

$ {\displaystyle \log p(x \mid \theta) - \mathcal{L}(q, \theta) = \mathrm{KL}\!\left(q(z) \,\Vert\, p(z \mid x, \theta)\right) \geq 0.} $

于是 EM 就是对 $ \mathcal{L} $ 的坐标上升：交替地在固定 $ \theta $ 时关于 $ q $ 最大化，以及在固定 $ q $ 时关于 $ \theta $ 最大化。

E 步

将 $ \theta $ 固定在当前估计 $ \theta^{(t)} $ 时，ELBO 在 $ q $ 等于后验时取得最大：

$ q^{(t+1)}(z) = p(z \mid x, \theta^{(t)}). $

这使 KL 项归零并收紧下界。等价地，E 步计算完整数据期望对数似然，通常记作

$ Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{p(z \mid x, \theta^{(t)})}\!\left[\log p(x, z \mid \theta)\right]. $

在实际操作中，E 步归结为计算 $ z $ 在后验下的充分统计量——例如混合模型中的责任度 $ r_{ik} = p(z_i = k \mid x_i, \theta^{(t)}) $，或在隐马尔可夫模型中由前向-后向递归计算的平滑状态概率。

M 步

在固定 $ q^{(t+1)} $ 的情况下，ELBO 仅相差一个常数即等于完整数据期望对数似然，于是 M 步求解

$ {\displaystyle \theta^{(t+1)} = \arg\max_{\theta} \; Q(\theta \mid \theta^{(t)}).} $

由于 $ q^{(t+1)} $ 不依赖于 $ \theta $，潜变量相当于固定权重，整个优化通常可归约为常见的完全观测最大似然问题。对指数族而言，M 步往往具有闭式解：加权均值、加权协方差和加权多项式计数分别替代其无权重版本。

单调改进

组合后的更新满足

$ \log p(x \mid \theta^{(t+1)}) \;\geq\; \mathcal{L}(q^{(t+1)}, \theta^{(t+1)}) \;\geq\; \mathcal{L}(q^{(t+1)}, \theta^{(t)}) \;=\; \log p(x \mid \theta^{(t)}), $

因此每一迭代中边际对数似然都不会减小。在适度的正则性条件下，迭代序列会收敛到边际似然的某个驻点，但未必是全局最优。

经典示例：高斯混合模型

对于具有 $ K $ 个分量、参数 $ \theta = \{\pi_k, \mu_k, \Sigma_k\} $ 以及潜在指派 $ z_i \in \{1, \ldots, K\} $ 的高斯混合模型，EM 的更新规则形式格外清晰。

E 步计算每个分量对每个数据点的责任度：

$ r_{ik} = \frac{\pi_k \, \mathcal{N}(x_i \mid \mu_k, \Sigma_k)}{\sum_{j=1}^{K} \pi_j \, \mathcal{N}(x_i \mid \mu_j, \Sigma_j)}. $

M 步则把这些责任度作为软计数使用：

$ {\displaystyle N_k = \sum_{i=1}^{N} r_{ik}, \quad \pi_k^{\text{new}} = \frac{N_k}{N}, \quad \mu_k^{\text{new}} = \frac{1}{N_k}\sum_{i=1}^{N} r_{ik}\, x_i, \quad \Sigma_k^{\text{new}} = \frac{1}{N_k}\sum_{i=1}^{N} r_{ik}\,(x_i - \mu_k^{\text{new}})(x_i - \mu_k^{\text{new}})^{\!\top}.} $

当每个责任度都退化为一个独热向量（例如协方差收缩为各向同性的 $ \sigma^2 I $ 且 $ \sigma \to 0 $）时，该算法恰好退化为 k 均值——因此 k 均值就是球形高斯混合下 EM 的硬指派极限。

变体与推广

对基本方案的若干松弛使其在 E 步或 M 步难以处理时仍然可用。

• 广义 EM（GEM）：M 步被任何能提高（而不必最大化） $ Q(\theta \mid \theta^{(t)}) $ 的更新所取代，仍然保留边际对数似然的单调改进性质。
• 期望-条件最大化（ECM）：将 M 步分解为关于若干互不相交参数块的条件最大化序列，适用于联合最大化困难但条件最大化容易的场合。
• 随机 EM 与蒙特卡洛 EM：当后验 $ p(z \mid x, \theta) $ 难以处理时，用采样代替 E 步。随机 EM 仅抽取一个样本；蒙特卡洛 EM 则用样本均值近似期望。
• 变分 EM：E 步把 $ q $ 限制在一个可处理的分布族 $ \mathcal{Q} $ 中，并在该族内最小化到真实后验的KL 散度。这样得到的边际对数似然只是被界定但未必被取到，是以精确性换取可处理性。它正是经典 EM 与现代变分方法之间的桥梁。
• 在线与增量 EM：在小批量数据上以指数加权移动平均的方式更新充分统计量，从而把 EM 扩展到流式数据或大规模数据集。
• 硬 EM：每个 E 步用其后验众数处的点质量替代后验。这会失去单调改进的保证，但在追求速度或后验高度集中时仍然有时被采用。

收敛性质

EM 是一种局部搜索算法。其单调改进性质保证边际对数似然序列收敛到某个极限；在标准正则条件下，参数迭代会收敛到某个驻点——通常是局部极大值，但也可能是鞍点或参数空间的边界点。收敛速度一般是线性的，由 Dempster、Laird 与 Rubin 的“缺失信息原理”所支配：潜变量后验越接近点质量，EM 的收敛就越快。当缺失信息所占比例较大时，收敛会非常缓慢，因此有时会使用拟牛顿加速方法（Aitken、SQUAREM、参数扩展的 EM）。

对初始化的敏感性是一个众所周知的实际问题。对于混合模型，常用策略包括多次随机重启、用 k 均值进行初始化，以及确定性退火——后者先以高度平滑的目标开始，再逐步使之变得尖锐。

关联

EM 是 Majorization-Minimization 族的一个特例：每次迭代都构造一个切线下界（即在当前参数处的 ELBO）并最大化该下界。这一视角把 EM 与邻近方法、最优化中的 MM 算法以及关于非凸问题下界最大化的近期文献统一了起来。

EM 同样是 Variational Inference 与变分自编码器在概念上的祖先。EM 在 E 步精确求解后验，而变分方法则用一个可处理的近似来替代；EM 在 M 步优化参数，而摊销变分推断则学习一个推断网络，从数据直接预测变分后验。最初作为分析 EM 的工具而提出的 ELBO，如今已成为概率深度生成模型的核心训练目标。

在概率主成分分析（PPCA）、因子分析和独立分量分析中，EM 都是替代直接特征分解或不动点迭代的可扩展方案。在隐马尔可夫模型中，EM 算法特化为Baum-Welch 算法，其中 E 步对应前向-后向递归，M 步对应转移概率与发射概率的闭式重新估计。

局限性

EM 虽然强大，但并非万能。其主要的实际局限包括：

• 局部最优：边际似然通常是非凸的，EM 只能收敛到一个驻点。尤其在分量分离度差的混合模型中，会存在大量局部极大值和鞍点。
• 高缺失信息下的缓慢收敛：当后验较为弥散时，M 步只能产生很小的参数变化，算法可能需要非常多的迭代次数。
• 奇异性：在协方差不受约束的高斯混合中，似然是无界的——某个分量可能塌缩到单个数据点上并使似然趋于无穷。实际实现通常通过对协方差正则化或施加先验来避免这种病态。
• E 步难以处理：对于具有高维离散潜变量或潜变量耦合很强的复杂模型，精确计算后验不可行，需要使用变分或蒙特卡洛近似。
• 缺乏不确定性量化：EM 仅给出 $ \theta $ 的点估计，自身并不提供关于参数的后验分布。引入先验并使用 MAP-EM 可部分缓解这一点；要做完全的贝叶斯处理则需借助变分贝叶斯或 MCMC。

这些局限性也正是现代概率机器学习中更广阔的近似推断技术格局的内在动因。

另见

• Maximum Likelihood Estimation
• Variational Inference
• Gaussian Mixture Models
• Hidden Markov Models
• K-Means Clustering
• Latent Dirichlet Allocation
• Principal Component Analysis
• Kullback-Leibler Divergence
• Majorization-Minimization

参考文献

• Dempster, A. P., Laird, N. M. 与 Rubin, D. B. (1977). "Maximum Likelihood from Incomplete Data via the EM Algorithm". Journal of the Royal Statistical Society, Series B, 39(1), 1-38.
• Wu, C. F. J. (1983). "On the Convergence Properties of the EM Algorithm". The Annals of Statistics, 11(1), 95-103.
• McLachlan, G. J. 与 Krishnan, T. (2008). The EM Algorithm and Extensions（第 2 版）。Wiley。
• Neal, R. M. 与 Hinton, G. E. (1998). "A View of the EM Algorithm that Justifies Incremental, Sparse, and Other Variants"。收录于 Learning in Graphical Models，M. I. Jordan（编），Kluwer，355-368。
• Bishop, C. M. (2006). Pattern Recognition and Machine Learning。Springer，第 9 章。
• Murphy, K. P. (2012). Machine Learning: A Probabilistic Perspective。MIT Press，第 11 章。
• Baum, L. E., Petrie, T., Soules, G. 与 Weiss, N. (1970). "A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains". The Annals of Mathematical Statistics, 41(1), 164-171.