最大期望算法是什么

Fanly 2020-10-04 00:17:25
QA

最大期望算法(EM)是一类通过迭代进行极大似然估计的优化算法,通常作为牛顿迭代法的替代用于对包含隐变量或缺失数据的概率模型进行参数估计。

最大期望算法(Expectation-Maximization algorithm, EM),或 Dempster-Laird-Rubin 算法,是一类通过迭代进行极大似然估计(Maximum Likelihood Estimation, MLE)的优化算法,通常作为牛顿迭代法(Newton-Raphson method)的替代用于对包含隐变量(latent variable)或缺失数据(incomplete-data)的概率模型进行参数估计。

最大期望算法是什么

EM 算法的标准计算框架由 E 步(Expectation-step)和 M 步(Maximization step)交替组成,算法的收敛性可以确保迭代至少逼近局部极大值。EM 算法是 MM 算法(Minorize-Maximization algorithm)的特例之一,有多个改进版本,包括使用了贝叶斯推断的 EM 算法、EM 梯度算法、广义 EM 算法等。

由于迭代规则容易实现并可以灵活考虑隐变量,EM 算法被广泛应用于处理数据的缺测值,以及很多机器学习(machine learning)算法,包括高斯混合模型(Gaussian Mixture Model, GMM)和隐马尔可夫模型(Hidden Markov Model, HMM)的参数估计。

历史

对 EM 算法的研究起源于统计学的误差分析(error analysis)问题。1886 年,美国数学家 Simon Newcomb 在使用高斯混合模型(Gaussian Mixture Model, GMM)解释观测误差的长尾效应时提出了类似 EM 算法的迭代求解技术。在极大似然估计(Maximum Likelihood Estimation, MLE)方法出现后,英国学者 Anderson McKendrick 在 1926 年发展了 Newcomb 的理论并在医学样本中进行了应用。1956 年,Michael Healy 和 Michael Westmacott 提出了统计学试验中估计缺失数据的迭代方法,该方法被认为是 EM 算法的一个特例。1970 年,B. J. N. Blight 使用 MLE 对指数族分布的 I 型删失数据(Type I censored data)进行了讨论。Rolf Sundberg 在 1971 至 1974 年进一步发展了指数族分布样本的 MLE 并给出了迭代计算的完整推导。

EM 算法的正式提出来自美国数学家 Arthur Dempster、Nan Laird 和 Donald Rubin,其在 1977 年发表的研究对先前出现的作为特例的 EM 算法进行了总结并给出了标准算法的计算步骤,EM 算法也由此被称为 Dempster-Laird-Rubin 算法。1983 年,美国数学家吴建福(C.F. Jeff Wu)给出了 EM 算法在指数族分布以外的收敛性证明。

此外,在二十世纪 60-70 年代对隐马尔可夫模型(Hidden Markov Model, HMM)的研究中,Leonard E. Baum 提出的基于 MLE 的 HMM 参数估计方法,即 Baum-Welch 算法(Baum-Welch algorithm)也是 EM 算法的特例之一。

理论

EM 算法是基于极大似然估计(Maximum Likelihood Estimation, MLE)理论的优化算法。给定相互独立的观测数据

算法

标准算法

计算框架

EM 的计算框架:对数似然(蓝),E 步(绿),M 步(实心点)

1. E 步(Expectation-step, E-step)

由 EM 算法的求解目标可知,E 步有如下优化问题:

2. M 步(Maximization step, M-step)

在 E 步的基础上,M 步求解模型参数使

计算步骤

将统计模型带入 EM 算法的计算框架即可得到其计算步骤。这里以高斯混合模型(Gaussian Mixture Model, GMM)为例进行说明。由 GMM 的一般定义可知,其似然和参数有如下表示:

将上述内容带入 EM 算法的计算框架后,E 步有如下展开:

M 步通过 E 步输出的隐变量后验计算模型参数,在 GMM 中,M 步计算框架的优化问题有如下表示:

根据以上计算步骤,这里给出一个在 Python 3 环境使用 EM 算法求解 GMM 的编程实现:

改进算法

基于贝叶斯推断(Bayesian inference)的 EM 算法

参见:变分贝叶斯 EM

在 MLE 理论下,EM 算法仅能给出模型参数

MAP-EM 在 Dempster et al. (1977)就已被提出,但不同于标准 EM,MAP-EM 的隐分布

VBEM 使用平均场理论(Mean Field Theory, MFT)将隐分布近似为其在各个维度上分布的乘积:

EM 梯度算法(EM gradient algorithm)和广义 EM 算法(Generalized EM algorithm, GEM)

参见:广义期望最大算法

EM 算法的 M 步通过计算偏导数求解代理函数的极大值,EM 梯度算法(EM gradient algorithm)将该过程替换为牛顿迭代法(Newton-Raphson method)以加速迭代收敛。更进一步地,当代理函数

EM 算法的 E 步也可以按 ECM 的方法分解为条件极值问题,由先前推导可知,E 步的优化问题仅有一个全局极大值,即隐分布

α-EM 算法(α-EM algorithm)

α-EM 算法是对标准算法的隐变量概率分布引入权重系数

性质

收敛性与稳定性:EM 算法必然收敛于对数似然的局部极大值或鞍点(saddle point),其证明考虑如下不等关系:

计算复杂度:在 E 步具有解析形式时,EM 算法是一个计算复杂度和存储开销都很低的算法,可以在很小的计算资源下完成计算。在 E 步不具有解析形式或使用 MAP-EM 时,EM 算法需要结合其它数值方法,例如变分贝叶斯估计或 MCMC 对隐变量的后验分布进行估计,此时的计算开销取决于问题本身。

与其它算法的比较:相比于梯度算法,例如牛顿迭代法和随机梯度下降(Stochastic Gradient Descent, SGD),EM 算法的优势是其求解框架可以加入求解目标的额外约束,例如在高斯混合模型的例子中,EM 算法在求解协方差时可以确保每次迭代的结果都是正定矩阵。EM 算法的不足在于其会陷入局部最优,在高维数据的问题中,局部最优和全局最优可能有很大差异。

应用

EM 算法及其改进版本被用于机器学习算法的参数求解,常见的例子包括高斯混合模型(Gaussian Mixture Model, GMM)、概率主成份分析(probabilistic Principal Component Analysis)、隐马尔可夫模型(Hidden Markov Model, HMM)等非监督学习算法。EM 算法可以给出隐变量,即缺失数据的后验

0个人收藏 收藏

评论交流

泪雪默认头像 请「登录」后参与评论
  1. 加载中..

相关推荐