PRO会员通讯
在执行分类学习的时候，实际情况中，我们经常会遇到一些不完整样本，即样本的部分变量未知。为贯彻的变量学名称之为“隐变量”。我们令 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的值已知，则可方便的对参数Θ做极大似然估计
所以我们首先初始化Θ，将以下步骤不断迭代直到收敛：
- 基于Θ推断隐变量Z的期望；
- 基于已知变量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 算法。
主要事件
| 年份 | 事件 | 相关论文 |
| 1977 | Dempster 等人提出 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-1976 | Sundberg 对 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. |
| 1982 | Louis 发表了Finding the Observed Information Matrix when Using the EM Algorithm | Louis, T. A. (1982). Finding the observed information matrix when using the EM algorithm. Journal of the Royal Statistical Society. Series B (Methodological), 226-233. |
| 1983 | Wu 对EM算法的收敛性进行了分析 | Wu, C. J. (1983). On the convergence properties of the EM algorithm. The Annals of statistics, 95-103. |
| 1994 | Fessler 提出了 SAGE 算法 | Fessler, J. A., & Hero, A. O. (1994). Space-alternating generalized expectation-maximization algorithm. IEEE Transactions on Signal Processing, 42(10), 2664-2677. |
| 1997 | McLachlan 编写的书籍 The EM Algorithm and Extensions 出版 | McLachlan, G. J., & Krishnan, T. (1997). The EM algorithm and extensions. |
| 2003 | Matsuyama 提出 α-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. |
| 2007 | The 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