EM算法的推导与应用

发表于

EM算法的推导与应用

什么是EM算法

EM是一种迭代算法（梯度下降也是一种迭代算法），用于含有隐变量的概率模型参数的极大似然估计（极大后验概率估计）。EM算法由两部组成：E步，求期望（expectation）；M步，求极大（maximization）。

概率模型有时既含有观测变量（observable variable），又含有隐变量或潜在变量（latent variable）。如果概率模型的变量都是观测变量，那么可以直接使用极大似然估计的方法估计模型参数。EM算法是含有隐变量的极大似然估计法。

一个例子

三硬币模型： 假设有三枚硬币，分别记作A，B，C，这些硬币正面出现的概率为$\pi$，$p$，$q$。进行如下掷硬币实验，先掷硬币A，如果A为正面选硬币B，如果A为反面，选硬币C，然后掷选出的硬币，出现正面记作1，反面记作0。独立重复n次实验，观测结果如下：
$$
1,1,0,1,0,0,1,0,1,1
$$
假设只能观测掷硬币的结果，不能观测掷硬币的过程，求三硬币正面出现的概率，即模型参数，$\pi$，$p$，$q$。

将观测数据表示为$Y=(Y_1,Y_2,…,Y_n)^T$，未观测数据表示为$Z=(Z_1,Z_2,…,Z_n)^T$，观测数据的似然函数为
$$
P(Y|\theta) = \sum_Z{P(Z|\theta)P(Y|Z,\theta)}
$$
即
$$
P(y|\theta) = {\pi{p^{y}}{(1-p)^{1-y}}} + {(1-\pi){q^y}{(1-q)^{1-y}}}
$$

一般用Y表示观测随机变量的数据，Z表示隐随机变量的数据。Y与Z连在一起称为完全数据，观测数据Y称为不完全数据。假设给定观测数据Y，其概率分布是$P(Y|\theta)$，其中$\theta$是需要估计的模型参数，那么不完全数据Y的似然函数是$P(Y|\theta)$，对数似然函数$L(\theta)=logP(Y|\theta)$；假设$Y$和$Z$的联合概率分布是$P(Y,Z|\theta)$，那么完全数据的对数似然函数是$logP(Y,Z|\theta)$。

EM算法是通过迭代求$L(\theta)=logP(Y|\theta)$的极大似然估计。

EM算法步骤

  • 步骤1：选择参数的初值$\theta^{(0)}$；初值可以任意选择，但是EM算法是初值敏感的。

  • 步骤2：E步，记$\theta^{(i)}$为第$i$次迭代参数$\theta$的估计值，在第$i+1$次迭代的E步，计算
    $$
    \begin{split}
    Q(\theta,\theta^{(i)}) &= E_Z{[logP(Y,Z|\theta)|Y,\theta^{(i)}]}\
    &=\sum_Z{logP(Y,Z|\theta)P(Z|Y,\theta^{(i)})}
    \end{split}
    $$

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

  • 步骤4：重复第2步与第三步。