简述

EM算法是一种迭代算法，用于含有隐变量（hidden variable）的概率模型参数的极大似然估计，或极大后验概率估计。

EM算法步骤如其名，共两步：

• E步，求期望（expectation）
• M步，求极大（maximization）

这一算法也因此称为期望极大算法（expectation maximization algorithm）

EM算法引入

隐变量

概率模型有时既含有观测变量（observable variable），又含有隐变量或称潜在变量（latent variable）。

两种变量的含义都如其名，观测变量是指在试验中可以通过观测直接得到的变量。而隐变量，则意味着无法通过观测直接得到，或者虽然能够被观测但却需要通过其它方法加以综合的指标，例如某个数据集上的高斯混合模型的参数。

当一个概率模型拥有隐变量的时候，EM算法就是这类型模型的极大似然估计法，或极大后验概率估计法。

三硬币模型

假设有3个硬币，分别记作A，B，C，三个硬币出现正面的概率分别为$$π，p，q$$，做如下实验：

1.先抛硬币A 2.硬币A为正，选择抛硬币B，否则选择抛硬币C 3.选择的硬币被抛出后，出现正面记为1，出现反面记为0 4.独立地重复$$n$$次实验

假设重复10次后观测结果如下：

问如何估计三硬币正面出现的概率，即三硬币模型的参数？

三硬币模型可以写作：

其中$$y$$时观测变量，表示一次实验观测的结果是1还是0；随机变量$$z$$是隐变量，表示未观测到的抛硬币A的结果；$$θ=(π,p,q)$$是模型参数。显然，随机变量$$y$$的数据可以观测，随机变量$$z$$的数据不可观测。

将观测数据表示为$$Y=(Y_1,Y_2,...,Y_n)^T$$,未观测数据表示为$$Z=(Z_1,...,Z_n)^T$$，得到观测数据似然函数

考虑求该模型参数$$\theta =(π,p,q)$$的极大似然估计：

该问题没有解析解（闭式解），因此我们只能通过迭代方式求解。

我们先用针对以上问题的EM算法求解一回：

1.选取参数的初值，记为$$\theta^{(0)}=(π^{(0)},p^{(0)},q^{(0)})$$ 2.通过下面步骤迭代计算参数估计值直至收敛。记第$$i$$次迭代参数的估计值为$$\theta^{(i)}=(π^{(i)},p^{(i)},q^{(i)})$$，则EM算法的第$$i+1$$次迭代如下：

• E步：计算在模型参数$$π^{(i)},p^{(i)},q^{(i)}$$下观测数据$$y_j$$来自抛硬币B的概率：

• M步：计算模型参数的新估计值

构建算法步骤后可以直接进行数字计算，初始化模型参数初值为

由式子（9.5）得到，对$$y_j=1$$和$$y_j=0$$都有$$μ^{(1)}_j=0.5$$

再利用公式（9.6）~（9.8）进行迭代，得到

再带回（9.5）得到

继续迭代，有

从而得到模型参数$$\theta$$的极大似然估计

但如果取初值

那么就又会得到极大似然估计

由此可以看到，EM算法得出的参数估计值未必是固定的，EM算法的计算过程与初值的选择关系很大。

*E步：求期望（expectation）

*M步：求极大化（maximization）

下面我们来看看EM算法的通用形式：

EM算法

输出：模型参数$$θ$$

1.选择参数初值$$\theta^{(0)}$$ 2.开始迭代：

• E步：记$$\theta^{(i)}$$为第 $$i$$ 次迭代参数$$\theta$$的估计值，在第 $$i+1$$ 次迭代的E步，计算

• M步：求使$$Q(\theta,\theta^{(i)})$$极大化的$$\theta$$，确定第$$i+1$$次迭代的参数的估计值$$\theta^{(i+1)}$$

3.重复迭代，直至收敛。

式子（9.9）的函数$$Q(\theta,\theta^{(i)})$$为EM算法的核心，称为Q函数（Q function） 。

Q函数定义

小结

关于EM算法应用过程的几点说明

第一步中，参数的初值可以任意选择，但是EM算法对初值是相当敏感的，换言之，初值对最终结果影响很大。

第二步，E 步中求$$Q(\theta,\theta^{(i)})$$，Q函数式中的第1个变元表示要极大化的参数，第2个变元表示参数的当前估计值。每次迭代实际在求Q函数及其极大。

M步中求$$Q(\theta,\theta^{(i)})$$的极大化完成一次迭代。

最后，给出停止迭代的条件，常用的是相对两个较小的正数$$ε_1,ε_2$$，如果满足

则停止迭代。

EM算法的导出

接下来我们通过近似求解观测数据的对数似然函数的极大化问题来导出EM算法从而了解EM算法究竟是如何实现抵达使然估计的。

我们先假设我们有一个需要估计极大似然的概率模型：$$Y$$关于参数$$θ$$的对数似然函数：

我们知道，EM算法就是通过不断迭代从而近似极大化$$L(\theta)$$，因此我们可以假设在有第$$i$$次迭代后的参数$$\theta^{(i)}$$后，我们需要估计一个新的$$\theta$$使得$$L(\theta) > L(\theta^{(i)})$$。为此我们考虑两者的差为：

用Jensen不等式（Jensen inequality）（即琴生不等式）得到下界（此处不等式形式为$$log\sum_j\lambda_jy_j≥\sum_j\lambda_jlog y_j ,且 \lambda_j≥0,\sum_j\lambda_j=1$$）

再令

得

这样我们得到一个$$L(\theta)$$的下界函数$$B(\theta,\theta^{(i)})$$，并且我们知道$$L(\theta^{(i)})=B(\theta^{(i)},\theta^{(i)})$$

为了让$$L(\theta)$$增大，选择$$\theta^{(i+1)}$$使$$B(\theta,\theta^{(i)})$$增大，因此有问题：

求$$\theta^{(i+1)}$$的表达式，省去对于$$\theta$$的极大化而言为常数的项，得到：

该式等价于EM算法一次迭代的效果（即对Q函数求一次极大化）。EM算法本质上就是通过不断求解下界的极大化逼近求解对数似然函数极大化算法。

EM算法收敛性

下面是关于EM算法的收敛性的两个定理

• 定理1 设$$$P(Y

  \theta)$$为观测数据的似然函数，$$\theta^{(i)}(i=1,2…)$$为EM算法得到的参数估计序列，$$P(Y

  \theta^{(i)})(i=1,2,…)$$为对应的似然函数序列，则$$P(Y

  \theta^{(i)})$$$是单调递增的，即

• 定理2 设$$$L(\theta)=logP(Y

  \theta)$$为观测数据的对数似然函数，$$\theta^{(i)}(i=1,2…)$$为EM算法得到的参数估计序列，$$L(\theta^{(i)})(i=1,2…)$$$为对应的对数似然函数序列，则：

1. 如果$$$P(Y

   \theta)$$有上界，则$$L(\theta^{(i)})=logP(Y

   \theta^{(i)})$$收敛到某一值$$L^*$$$

2. 在函数$$Q(\theta,\theta')$$与$$L(\theta)$$满足一定条件下，由EM算法得到的参数估计序列$$\theta^{(i)}$$的收敛值$$\theta^*$$是$$L(\theta)$$的稳定点。

资料参考来源：

清华大学出版社 李航《统计学习方法》 第九章