最大期望算法

最大期望算法(Expectation-maximization algorithm,又译期望最大化算法)在统计中被用于寻找,依赖于不可观察的隐性变量的概率模型中,参数的最大似然估计。在统计计算中,最大期望(EM)算法是在概率模型中寻找参数最大似然估计或者最大后验估计的算法,其中概率模型依赖于无法观测的隐性变量。最大期望算法经常用在机器学习和计算机视觉的数据聚类(Data Clustering)领域。最大期望算法经过两个步骤交替进行计算,第一步是计算期望(E),利用对隐藏变量的现有估计值,计算其最大似然估计值;第二步是最大化(M),最大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中,这个过程不断交替进行。

简介

在执行分类学习的时候,实际情况中,我们经常会遇到一些不完整样本,即样本的部分变量未知。为贯彻的变量学名称之为“隐变量”。我们令 X 表示已知变量集,Z 表示未知变量集,Θ 表示模型的参数。如果我们想要对模型参数做最大似然估计,那么我们应该最大化对数似然

LL(\Theta | X, Z) = ln P (X, Z|\Theta )

这里由于 Z 是隐变量,上边的式子无法直接求解,这个时候我们可以通过计算 Z 的期望,来最大化已知变量的对数边际似然。

LL(\Theta | X ) = ln P (X|\Theta )= ln \sum_{z}^{ } P(X,Z|\Theta )

EM算法正是通常用来估计参数的隐变量的一种方法,它是一种迭代的方法,大致可以分为E步和M步:

  • 期望E步:若参数Θ已知,则可根据训练数据推断出最优隐变量Z的值;
  • 最大化M步:若Z的值已知,则可方便的对参数Θ做极大似然估计

所以我们首先初始化Θ,将以下步骤不断迭代直到收敛:

  1. 基于Θ推断隐变量Z的期望;
  2. 基于已知变量X和Z的期望对参数Θ做极大似然估计,得到新的Θ;

同理我们也可以不求Z的期望,而是基于新的Θ计算Z的概率分布,只需要

  • E步:根据当前参数Θ来推断Z的分布,并计算Z的期望;
  • M步:寻找参数最大化期望似然;

虽然隐变量估计问题也可以使用梯度下降等优化算法求解,但由于计算量过大,所以 EM 算法通常被看作一种非梯度优化方法。由于 EM 收敛较慢的问题,有很多加速算法,例如使用共轭梯度法(Conjugate gradient method)和牛顿-拉弗森方法(Newton's method)。α-EM 算法是 EM 算法的另外一个变种,他不需要计算梯度便能很快的收敛。

EM 算法被广泛的应用于聚类和计算机视觉等机器学习邻域,在自然语言处理方面,Baum-Welch 算法和内部外部算法是都应用到了 EM 算法。同时,EM 算法还被应用于心理统计学,商业和风险管理,医学图像处理,结构工程等多个领域。

【描述来源:周志华. (2016). 机器学习: = Machine learning.清华大学出版社.】

【描述来源: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 (methodological), 1-38.】

EM 算法最初由来自哈弗大学 Dempster 等人在1977年最先提出,初衷就是用来处理缺失数据的时候求解最大似然,后来 Rolf Sundberg 在他的几篇相关论文给出了 EM 算法的详细系统的描述与分析。在之后的1983年, Wu (美国华裔统计学家 吴建福)对 EM 算法的收敛性进行了分析。EM 算法在机器学习中用途非常广泛,高斯混合模型(GMM)的参数估计常会用到它,而 k 均值聚类算法本身就是一个典型的 EM 算法。由澳大利亚昆士兰大学教授 McLachlan 编写的书籍 The EM Algorithm and Extensions 对 EM 算法的原理以及相关的应用做了深入的分析和拓展。1982年,美国约翰·霍普金斯大学布隆博格公共卫生学院的生物学教授 Louis 对使用 EM 算法来寻找样本完整数据和加速 EM 算法的收敛进行了研究。1994年,美国密歇根大学的 Fessler 提出了 SAGE 算法,该算法主要致力加速 EM 收敛等问题。1998年,美国华盛顿大学的教授 Bilmes 编写了如何使用 EM 算法求解高斯混合模型的辅导教程,受到学界的一致好评。2003年,来自日本早稻田大学的 Matsuyama 教授提出 α-EM 算法。

主要事件

年份事件相关论文
1977Dempster 等人提出 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 (methodological), 1-38.
1974-1976Sundberg 对 EM 算法进行具体的描述Sundberg, R. (1974). Maximum likelihood theory for incomplete data from an exponential family. Scandinavian Journal of Statistics, 49-58.Sundberg, R. (1976). An iterative method for solution of the likelihood equations for incomplete data from exponential families. Communication in Statistics-Simulation and Computation, 5(1), 55-64.
1982Louis 发表了Finding the Observed Information Matrix when Using the EM AlgorithmLouis, T. A. (1982). Finding the observed information matrix when using the EM algorithm. Journal of the Royal Statistical Society. Series B (Methodological), 226-233.
1983Wu 对EM算法的收敛性进行了分析Wu, C. J. (1983). On the convergence properties of the EM algorithm. The Annals of statistics, 95-103.
1994Fessler 提出了 SAGE 算法Fessler, J. A., & Hero, A. O. (1994). Space-alternating generalized expectation-maximization algorithm. IEEE Transactions on Signal Processing, 42(10), 2664-2677.
1997McLachlan 编写的书籍 The EM Algorithm and Extensions 出版McLachlan, G. J., & Krishnan, T. (1997). The EM algorithm and extensions.
2003Matsuyama 提出 α-EM 算法Matsuyama, Y. (2003). The/spl alpha/-EM algorithm: surrogate likelihood maximization using/spl alpha/-logarithmic information measures. IEEE Transactions on Information Theory, 49(3), 692-706.
2007The EM Algorithm and Extensions 第二版出版McLachlan, G., & Krishnan, T. (2007). The EM algorithm and extensions (Vol. 382). John Wiley & Sons.

发展分析。

瓶颈

EM 算法有几个问题:1迭代算法的收敛速度慢;2对初始值的选择很敏感;3由于EM算法本质上是非凸的,容易陷入局部最优;4不适合大数据集。

未来发展方向

EM 算法的初始值的选取和加快模型收敛速度仍然是当前研究的方向之一,其次,如何在更大的数据,更多的领域应用 EM 算法来解决实际问题是未来的主要发展方向。

Contributor: Chao Yang

相关人物
Jeffrey A. Fessler
Jeffrey A. Fessler
Rolf Sundberg
Rolf Sundberg
松山泰男
松山泰男
早稲田大学名誉教授,理工学研究所名誉研究员,IEEE Fellow,ACM Fellow。主要研究机器学习和人类感知信息处理。
杰弗里·麦克拉克伦
杰弗里·麦克拉克伦
生于1946年,澳大利亚计算统计学、机器学习和模式识别领域的研究人员,以其在分类和有限混合模型方面的工作而闻名,目前是昆士兰大学数学和物理学院的统计学教授。
简介
相关人物