EM算法及其推广

liang @ 2019年10月29日

EM算法是一种迭代算法,1977年由Dempster等人总结提出,用于含有隐变量(hidden variable)的概率模型参数的极大似然估计,或极大后验概率估计。EM算法的每次迭代由两步组成:

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

所以这一算法称为期望极大算法(expectation maximization algorithm),简称EM算法。

EM算法

概率模型有时即含有观测变量(observable variable),又含有隐变量或潜在变量(latent variable)。如果概率模型的变量都是观测变量,那么给定数据,可以直接用极大似然估计法,或贝叶斯估计法估计模型参数。但是,当模型含有隐变量时,就不能简单地使用这些估计方法。EM算法就是含有隐变量的概率模型参数的极大似然估计法,或极大后验概率估计法。

首先介绍一个使用EM算法的例子 ---- 三硬币模型

假设有3枚硬币,分别记作A,B,C。这些硬币正面出现的概率分别是$\pi, p$和$q$。进行如下抛硬币实验:先抛硬币A,根据其结果选出硬币B或硬币C,正面选硬币B,反面选硬币C;然后抛选出的硬币,抛硬币的结果,出现正面记作1,出现反面记作0;独立地重复n次实验(这里,n=10),观测结果如下:

$$1,1,0,1,0,0,1,0,1,1$$

假设只能观测到抛硬币的结果,不能观测到抛硬币的过程。问如何估计三硬币正面出现的概率,即三硬币模型的参数:

三硬币偶像可以写作:

$$P(y|\theta)=\sum_zP(y,z|\theta)=\sum_zP(z|\theta)P(y|z,\theta) \\ = \pi p^y(1-p)^(1-y) + (1-\pi)q^y(1-q)^)(1-y)$$