EM算法及其推广

EM算法

对于一般概率模型的学习策略，我们往往会采取极大似然估计或者贝叶斯估计的方法对模型的参数进行估计，但是需要注意的是这种估计方法都是建立在待估参数全部为已经知道结果的参数（观测变量）的基础之上的。当模型中有隐变量/潜在变量（数据不可观测的变量）时，往往会给极大化似然函数带来困难（隐变量可能会使得似然很难，包含有和或者积分的对数，难以利用传统的方法求得解析解）。

由于隐变量的取值是无法直接观测得到的，因此我们称这种情况下的观测数据为“不完全数据”，当隐变量的观测值已知时才称为完全数据。

面对上述问题我们很自然的一种想法是通过迭代算法来求解近似最大值，而EM算法正是在针对这个问题的求解过程中导出的一种来近似求解的对数似然函数极大化问题的算法。EM算法主要分为两步：

• E:求期望(expectation)
• M:求极大(maximization)

EM算法的核心思想是在既定样本数据下在因变量最有可能的分布状态下利用极大似然估计模型的参数。

算法导出

EM算法就是通过不断求解下界的极大化逼近求解对数似然函数极大化的算法，这里的Q其实就是求logP(Y,Z∣θ)logP(Y,Z|\theta)logP(Y,Z∣θ)的期望值（注意这里的YYY是观测值，换言之相当于是在Y和模型参数给定的条件下最大化期望值）

算法收敛性

可以证明随着迭代次数的增加，似然函数的值会不断增大，这也意味着如果似然函数有界，那么一定存在局部最优解或者全局最优解。本身是局部最优的算法，

坐标上升法（Coordinate ascent）

坐标上升法是一种与梯度下降法类似的方法，与梯度下降法不同之处在于梯度下降法目的是最小化代价函数，坐标上升法的目的是最大化似然函数；

梯度下降法每一步只更新模型参数，而Em算法的每一步既更新模型参数又更新隐含参数：

需要注意的是EM算法每一步只会优化一种参数，因此我们看到的优化路径是一种阶梯类型的（E步固定模型参数优化隐变量，M步固定因变量优化模型参数）

应用

本质上来说算法的应用首先是一种局部固定单点突破的思想。

如果我们从算法思想的角度来思考EM算法，我们可以发现我们的算法里已知的是观察数据，未知的是隐含数据和模型参数，在E步，我们所做的事情是固定模型参数的值，优化隐含数据的分布，而在M步，我们所做的事情是固定隐含数据分布，优化模型参数的值。

高斯混合模型

支持向量机的SMO算法

K-means

马尔科夫模型