EM算法
- 提出者
- Dempster, Laird & Rubin
- 年份
- 1977
- 类型
- Iterative optimization algorithm
- 类别
- Estimation
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
期望最大化(EM)算法是一种迭代优化过程,用于在具有潜在变量或缺失数据的统计模型中寻找参数的最大似然估计或最大后验估计。该算法由Dempster、Laird和Rubin在他们1977年的开创性论文中提出,它在计算完整数据对数似然的期望(E步)和最大化该期望关于参数(M步)之间交替进行,保证了每次迭代似然度单调非减。
方法背后的直觉
想象一下,通过观察玩家们打牌但看不到他们的手牌来学习游戏规则。在每一轮中,你根据观察到的情况猜测他们可能持有怎样的牌,然后假设这些猜测是正确的来更新你对规则的理解。EM算法正是这样做的:E步利用当前的参数估计值以概率方式填补缺失的信息,而M步则在假设这些填补的值是真实观测值的情况下重新拟合模型。
历史学
该算法由Arthur Dempster、Nan Laird和Donald Rubin在他们1977年发表于JRSS-B的论文中正式统一并命名,该论文至今仍是统计学引用率最高的文章之一。该论文将先前为特定缺失数据问题独立开发的特殊情况程序进行了推广。随后的几十年里,出现了许多扩展,包括ECM、ECME、AECM和SEM算法,拓宽了应用范围并加速了许多实际应用中的收敛速度。
何时使用
当数据包含缺失值、隐藏状态或潜在变量,并且需要最大似然估计时,请使用EM算法。它非常适合高斯混合模型、隐马尔可夫模型、因子分析和缺失数据插补。关键假设包括缺失数据是随机缺失(MAR),并且完整数据模型是可处理的。局限性包括对初始化的敏感性、可能收敛到局部最大值以及在鞍点附近收敛缓慢。替代方法包括数值积分的梯度下降优化、变分推断或MCMC方法。
局限与注意事项
- 当似然曲面是多峰的时,收敛到局部最大值而非全局最大值
- 当缺失信息比例很大时,可能出现非常缓慢(线性)的收敛
- 要求分析者指定完整数据模型和潜在变量的分布
- 标准的EM算法不能直接提供估计值的观测数据协方差矩阵;需要一个辅助步骤(例如,Louis方法或SEM算法)来获得标准误差
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 保证每次迭代观测数据似然度单调增加,确保稳定收敛
- 将硬缺失数据问题转化为一系列可处理的完整数据优化问题
- 广泛适用于指数族模型、混合模型和潜在变量框架
- 许多标准模型都有闭式M步更新,使得实现效率高
应用
- 拟合高斯混合模型用于聚类和密度估计
- 训练隐马尔可夫模型用于语音识别和生物序列分析
- 临床和社会科学研究中的多重插补和缺失数据分析
- 因子分析和潜在类别分析中的参数估计
- 医学影像中的图像分割和重建
使用方式
使用方式
在迭代开始之前,分析者会选择未知参数的初始值,记为theta-0。这些值可以随机选择,也可以从简化拟合或领域知识中获得。初始化的质量会影响算法收敛到的局部最大值,因此多次随机重启是一种常见的做法。
公式
\text{Choose initial parameter estimates } \theta^{(0)}给定当前的参数估计theta-t,E步计算Q值,即在给定观测数据X的条件下,关于未观测到的潜在变量Z的分布的完整数据对数似然的期望值。这个期望值有效地用其概率估计替换了未知量,而无需确定单一的插补值。
公式
Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{Z \mid X, \theta^{(t)}}[\log p(X, Z \mid \theta)]M步根据从E步得到的Q函数,相对于theta进行最大化,产生更新的估计值theta-(t+1)。由于完整数据对数似然通常比边际观测数据似然更容易最大化,因此即使直接最大似然估计不可行,这一步也常常是可行的。
公式
\theta^{(t+1)} = \arg\max_{\theta} \, Q(\theta \mid \theta^{(t)})E步和M步交替重复进行。在每个完整周期之后,都会评估观测数据对数似然。当对数似然(或参数向量)的变化低于用户定义的容差epsilon时,迭代停止。Dempster等人证明了每个周期都不会降低观测数据似然度,从而确保了稳定的收敛。
公式
\text{Repeat E- and M-steps until } |\ell(\theta^{(t+1)}) - \ell(\theta^{(t)})| < \epsilon常见陷阱
- 使用单一的随机初始化存在收敛到较差局部最大值的风险;务必运行多次重启并选择最终对数似然度最高的解
- 仅通过监控参数变化而非观测数据对数似然度而过早声明收敛,可能导致估计不准确
- 在数据是随机缺失(MNAR)的情况下应用EM而未进行模型调整,可能在估计中引入系统偏差
- 在混合模型中忽略标签切换问题会导致即使正确收敛后组件分配也无法解释
常见问题
EM算法是否总是收敛到全局最大值?
否。EM算法只能保证收敛到观测数据似然度的局部最大值(或鞍点)。当似然曲面有多个峰值时,最终解取决于初始化。从多个不同的起始点运行算法并保留具有最高对数似然度的解是标准的实际解决方案。
EM与直接最大似然优化有何不同?
直接MLE最大化观测数据对数似然,这可能涉及对潜在变量的难以处理的积分。EM通过迭代最大化完整数据对数似然的期望来规避这一点,后者通常是解析可处理的。权衡是EM可能收敛缓慢,而当边际似然的梯度可用时,基于梯度的方法可能更快。
何时应优先选择MICE插补而非EM算法?
当数据包含混合类型变量、非线性关系或难以在单个参数化完整数据模型中编码的复杂交互结构时,MICE(链式方程多重插补)是更优的选择。当存在所有变量的良好指定的联合模型,并且推断目标是模型参数而非插补数据集时,EM更为自然。
相关方法
参考文献
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.
打开 DOI 文献已复制。