EM算法简介及其例子

本篇博客内容主要来自英文维基百科（点击访问维基百科）

####EM算法简介 EM（expectation-maximization）算法是统计学中求统计模型的最大似然和最大后验参数估计的一种迭代式算法，模型一般是依赖于不可观测的潜在变量。EM迭代算法交替E步（使用当前参数创造一个log-likelihood函数，并求期望）和M步（求使得E步骤log-likelihood函数期望最大的参数）。然后M步参数估计的结果用作下一个E步骤中潜在变量的分布。

EM算法是1977年Arthur等人的论文。EM算法通常是用来寻找一个统计模型中最大似然参数的。通常这些模型都是涉及到一些无法观测的未知量以及可观测的数据。也就是说，要么数据中包含丢失的值，要么模型的存在要依赖于其他因变量的存在。比如，一个混合模型可以假设每个观测值都与一个相关的但却无法观测的隐变量相关，该隐变量是确定当前观测值属于哪个混合部分的变量。

使用极大似然估计的方法求解后验概率通常需要我们推导关于所有未知变量、因变量参数等的似然函数，同时需要能求解该函数。在带有因变量的统计模型中，这通常都不可能。该似然函数的结果通常都依赖于隐变量的值，也就是说求解该似然函数需要知道因变量结果，而求解因变量的结果又依赖于该似然函数。正常情况下，这是无法得到结果的。而EM算法的来源是作者观察到如下的情况可以解决这些问题。即我们可以先任意对一种未知变量任意赋值，然后利用这个值去求解另一个变量，再用求到的结果反过来求事先任意赋值的变量。如此交替循环直到二者的结果基本不变为止。虽然这个方法并不总是奏效，但是可以证明的是，在二者几乎不变的情况下，似然函数的结果要么是最大值要么是鞍点（saddle point）。一般情况下，我们可能能发现多个最大值，该方法无法保证求得全局最大值。

####EM算法的数学描述 假设有一组观测数据$X$，一组无法观测的隐数据或者是缺失值$Z$，其参数为$\theta$。同时，我们有一个似然函数$L(\theta;X,Z)=p(X,Z|\theta)$，未知参数的极大似然估计是由观测数据的边缘似然决定的：

L(\theta;X)=p(X|\theta)=\sum_Z p(X,Z|\theta)

通常这个式子都是很难求解的（比如，Z是一系列事件的时候，那么这些值的数量就随着序列的长度增长呈指数级增长，那么求和就非常困难了）。而EM算法则通过E步骤和M步骤迭代求解。

1、E步骤（Expectation step）：计算log-likelihood（它是在当前估计的$\theta^{(t)}$条件下，给定$X$关于$Z$的条件分布）的期望值：

Q(\theta|\theta^{(t)})=E_{Z|X,\theta^{(t)}}[\log L(\theta;X,Z)]

2、M步骤（Maximization step）：寻找一个参数使得E步骤中的似然函数最大：

\theta^{(t+1)}= \text{argmax}_\theta Q(\theta|\theta^{(t)})

####EM算法的性质 EM算法是无法保证序列收敛到全局最优的。比如在多峰模型中，根据初始值的选择不同，EM算法很可能收敛到局部最优。一些启发式的或者是元启发式的方法能改进EM算法使其跳出局部最优。EM算法在指数函数中应用的非常好：E步骤就是求充分统计量的和，M步骤就是求线性函数的最大值。在这种情况下，每一个步骤都可以使用Sundberg公式求出一个近似的形式。EM算法可以说是最大后验的一个修改版本。求极大似然的方法还包括梯度下降，共轭下降，或者是高斯-牛顿算法的变种等。与EM算法不同，这些算法通常都需要求似然函数的一阶导数或者是二阶导数。

####EM算法的应用场景 常见的EM算法的应用场景为：

1. 观测数据的点 X 既可以是离散的也可以是连续的，但每个数据点相关联都是一组观测向量。
2. 丢失值 Z 是离散的，是从一组固定值中抽取的结果，每个观测值都与一个潜在变量关联。
3. 参数是连续的，但是有两种：一种是参数与所有的数据点相关；另一种是参数与一个特定的隐变量相关。

当然，除此之外，EM算法也有一些其他的应用场景。如果参数$\theta$已知，那么通常隐变量$Z$的值可以通过寻找所有可能的Z的log-likelihood函数得到，也可以通过类似隐马尔科夫模型中的Viterbi算法迭代求解$Z$。相反的，如果我们知道潜在变量$Z$的值，我们也能比较容易地找出参数$\theta$的估计结果（一般就是将观测值根据隐变量分组，然后求平均值得到）。也就是说，当$\theta$和$Z$都未知的时候，我们可以： 1、首先对参数$\theta$随机初始化； 2、在给定这些参数的情况下，求解最优的$Z$ 3、使用步骤2中计算得到的$Z$来求解更好的$\theta$的参数估计结果。与特殊的$Z$关联的参数讲将只使用与那个$Z$关联的数据进行计算。 4、重复步骤2和步骤3直到收敛。 这是局部最小损失函数算法的描述，也称作hard EM。K-means方法就是该方法的一个种。还有一些改进的方法，这里就不做描述了。 EM算法通常在计算机图像识别和聚类方法中使用。自然语言处理中，也有一些运用。