1、EM算法简介

EM算法也称期望最大化（Expectation-Maximum，EM）算法，是由美国数学家Arthur Dempster、Nan Laird和Donald Rubin提出的，他们在1977年发表的研究对先前出现的作为特例的EM算法进行了总结并给出了标准算法的计算步骤，EM算法也由此被称为Dempster-Laird-Rubin算法。之后，1983年，美国数学家C.F. Jeff Wu给出了EM算法在指数族分布以外的收敛性证明。

2、EM算法核心

EM算法是在概率模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量。其主要思想就是通过迭代来建立完整数据的对数似然函数的期望界限，然后最大化不完整数据的对数似然函数。

EM算法经过两个步骤交替进行计算，第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；第二步是最大化（M），最大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行。

3、EM算法思想

给定训练样本x(1)，x(2)，⋅⋅⋅，x(m)，样本间相互独立，但每个样本对应的类别z(i)是未知的，也即隐含变量。我们想找到每个样本隐含的类别z，能使得P(x,z)最大。P(x,z)的最大似然估计如下：

第一步是对极大似然函数取对数，第二步是对每个样本的每个可能的类别z求联合分布概率之和。但是直接求上述公式中的θ一般比较困难，因为有隐藏变量z存在，如果z是一个已知的数，那么使用极大似然估计来估算会很容易。在这种z不确定的情形下，EM算法就派上用场了。

EM算法是一种解决存在隐变量优化问题的有效方法。对于上述情况，由于存在隐变量，不能直接最大化l(θ)，我们可以不断地建立l的下界（E步），然后优化下界（M步），依次迭代，直至算法收敛到局部最优。这就是EM算法的核心思想。

EM算法通过引入隐变量，使用MLE进行迭代求解参数。通常引入隐含变量后会有两个参数，EM算法首先固定其中的第一个参数，然后使用MLE计算第二个变量值；接着通过固定第二个变量，再使用MLE估计第一个变量值，依次迭代，直至收敛到局部最优解。

4、EM算法的特点

简单性和普适性；EM算法不能保证找到全局最优点，在应用中，通常选取几个不同的初值进行迭代，然后对得到的几个估计值进行比较，从中选择最好的；EM算法对初值是敏感的，不同初值会得到不同的参数估计值。

5、EM算法的应用

EM算法里已知的是观察数据，未知的是隐含数据和模型参数。在E步，需要做的事情是固定模型参数的值，优化隐含数据的分布；而在M步，需要做的事情是固定隐含数据分布，优化模型参数的值。EM的应用包括：

支持向量机的SMO算法；混合高斯模型；K-means；隐马尔可夫模型。

6、EM算法的优缺点

优点：

算法简单；不需要预先设定类别；比K-means算法计算结果稳定、准确。

缺点：

当所要优化的函数不是凸函数时，EM算法容易给出局部最佳解，而不是最优解；EM算法需要初始化参数θ，而参数θ的选择直接影响收敛效率以及能否得到全局最优解；EM算法比K-means算法计算复杂；收敛速度慢，不适合于大规模数据集。

（本文部分内容来自）