理解EM算法

EM(Expectation-Maximization)算法在机器学习和自然语言处理应用非常广泛,典型的像是聚类算法K-means和高斯混合模型以及HMM(Hidden Markov Model)。笔者觉得讲EM算法最好的就是斯坦福大学Andrew Ng机器学习课的讲课笔记和视频。本文总结性的给出普遍的EM算法的推导和证明,希望能够帮助接触过EM算法但对它不是很明白的人更好地理解这一算法。

EM算法的目标是找出有隐性变量的概率模型的最大可能性解,它分为两个过程E-stepM-stepE-step通过最初假设或上一步得出的模型参数得到后验概率,M-step重新算出模型的参数,重复这个过程直到目标函数值收敛。我们设观察到的变量所组成的向量为[image],所有的隐性变量所组成的向量为[image],模型的参数为[image](一个或多个参数)。在聚类的情况下,[image]是潜在的类,而[image]就是需要分类的数据。我们的目标就是找出模型的参数[image]使得[image]出现的可能性最大,也就是使下面的对数可能性最大化:

[image]

注:这里仿照Andrew Ng 的用法使用[image]而不是[image],因为[image]是模型的参数而不是随机变量。关于为什么要用EM算法而不是不直接通过[image]得出[image],是因为这样可能会出现严重的overfitting (这里不详细说明,请参看Pattern Recognition and Machine Learning一书9.2.1)

假设[image][image]上一个概率分布,所以[image]

[image]

最后一步是根据Jensen不等式[image]如果[image]是凹函数,在这个式子中就是对数函数。[image]就是[image][image]就是[image] [image]是严格的 凹函数的时候,[image]中等号成立的条件是[image]是常数,也就是说在这个特定的式子中[image],满足这个条件加上之前的[image][image]其实就是后验概率[image](参看http://www.stanford.edu/class/cs229/materials.html Lecture notes: The EM Algorithm)。这就是EM算法中E-step的由来。

M-step一般来说就是个就是二次规划的问题,通过[image]得出[image]。这里也就不再赘述。

EM算法其实就是coordinate ascent E-step是将[image]视为常数,选择一个概率分布[image]使得目标函数[image]最大化, M-step就是保持[image]不变,选择[image]使得目标函数[image]最大化,因为每一步的目标函数都比前一步的值大,所以只要目标函数存在最大值,EM算法就会收敛。这个过程用图像表示就是:

E-step找到跟[image](黑色弧线)交于[image][image](蓝色弧线),M-step得到[image]取最大值时的[image],这样下去直到收敛。(此图源于Andrew)

此条目发表在 机器学习 分类目录,贴了 , , 标签。将固定链接加入收藏夹。

理解EM算法》有 23 条评论

  1. 52nlp 说:

    谢谢你的分享,非常受益!

    [回复]

  2. raogaoqi 说:

    看过Ng的视频,呵呵,给力。可惜只练听力了:(

    [回复]

  3. Jeffye 说:

    不直接使用MLE,主要不是因为over-fitting,而是有时候直接MLE无法求解,所以需要引入hidden variable对原始形式进行简化。
    进一步形式更复杂的EM也无法求解,这时可以使用Variational Inference 和sampling techniques.

    [回复]

    emnlp 回复:

    同意mle无解析解的说法

    [回复]

  4. emnlp 说:

    有个问题,估计是作者笔误了。
    在描述E-step的时候,那f应该是凸函数,而不是凹函数:)

    [回复]

    bing 回复:

    f(x)=log(x),此处为凹函数。还有就是对凹函数与凸函数的定义,国内与国外存在差异。详情见
    http://zh.wikipedia.org/wiki/%E5%87%B8%E5%87%BD%E6%95%B0

    [回复]

  5. emnlp 说:

    Andrew的这个图真是太好了!
    简洁清楚明了

    [回复]

  6. jeremy 说:

    为何M-step一般是二次规划问题呢?

    [回复]

    emnlp 回复:

    你推导一下看看
    比如 某max likelihood问题 是让likelihood对某参数的偏倒为0,那。。。

    [回复]

  7. quguanwei 说:

    EM算法用于对齐中,用的那个工具包呀?或者说是那些工具包包含有EM算法呢?谁知道,请告知。

    [回复]

    52nlp 回复:

    giza++

    [回复]

    quguanwei 回复:

    除了这个GIZA++之外,还有那个比较好的工具包,可以直接利用里面的EM算法,只要自己设置好一定的参数。

    [回复]

    52nlp 回复:

    sorry, 不太清楚。

  8. 求知者 说:

    当是严格的 凹函数的时候,中等号成立的条件是是常数,也就是说在这个特定的式子中,满足这个条件加上之前的的其实就是后验概率 请问 等号成立的时候不是取得最小值吗?跟之前目标求最大可能性不一致 ?

    [回复]

  9. 解决 说:

    牛逼,受教了,还在研究中

    [回复]

  10. zoezheng 说:

    公式图片都失效了~

    [回复]

  11. loveGlory 说:

    图挂了,求更新

    [回复]

  12. 宁雨 说:

    图挂了,可不可以更新一下啊

    [回复]

  13. songtianyi 说:

    图都挂了 只有一张幸存

    [回复]

  14. TNTDoctor 说:

    很多图都挂了,怎么回事啊

    [回复]

    52nlp 回复:

    貌似原文引用的一些图片的地方挂了,希望作者有空能修复一下,这篇文章的影响力挺大的。

    [回复]

  15. Jingwen 说:

    图… 哭了….

    楼主修复一下吧!

    [回复]

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>