EM算法

EM算法(Expectation Maximization)可以解决的问题示例:

  • GMM和HMM的参数估计(统计学习方法 第9、10章)
  • Mitchell书中提到可以用于贝叶斯网络

问题定义

给定的训练样本是$\brace{x^{(1)},x^{(2)},\cdots,x^{(m)} }$,样本间独立,我们想找到每个样本隐含的类别$z$,能使得$p(x,z)$最大。$p(x,z)$的最大似然估计如下:

第一步是对极大似然取对数,第二步是对每个样例的每个可能类别$z$求联合分布概率和。但是直接求$\theta$一般比较困难,因为有隐藏变量$z$存在,但是一般确定了$z$后,求解就容易了。

EM是一种解决存在隐含变量优化问题的有效方法。既然不能直接最大化$\ell(\theta)$,但可以不断地建立$\ell$的下界(E步),然后优化下界(M步)。

推导思路

利用$\log$的凹函数性质,把分子分母都乘以$z$的概率变成期望来套上Jensen不等式,推导出似然的下界,然后不断优化下界来逼近极大值。

从$(2)$到$(3)$利用了Jensen不等式,若等式成立,需要随机变量为常数,可以进一步推导得到$Q_i(z^{(i)})$:

EM算法

循环重复直到收敛:

(E步)对于每一个样本$i$,计算

(M步)计算

代码示例:求解混合高斯模型参数

参考

  • PRML Chapter 9
  • 《统计学习方法》李航, EM算法及其推广
  • http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006936.html