理解EM算法
EM(Expectation-Maximization)算法在机器学习和自然语言处理应用非常广泛,典型的像是聚类算法K-means和高斯混合模型以及HMM(Hidden Markov Model)。笔者觉得讲EM算法最好的就是斯坦福大学Andrew Ng机器学习课的讲课笔记和视频。本文总结性的给出普遍的EM算法的推导和证明,希望能够帮助接触过EM算法但对它不是很明白的人更好地理解这一算法。
EM算法的目标是找出有隐性变量的概率模型的最大可能性解,它分为两个过程E-step和M-step,E-step通过最初假设或上一步得出的模型参数得到后验概率,M-step重新算出模型的参数,重复这个过程直到目标函数值收敛。我们设观察到的变量所组成的向量为,所有的隐性变量所组成的向量为
,模型的参数为
(一个或多个参数)。在聚类的情况下,
是潜在的类,而
就是需要分类的数据。我们的目标就是找出模型的参数
使得
出现的可能性最大,也就是使下面的对数可能性最大化:
注:这里仿照Andrew Ng 的用法使用而不是
,因为
是模型的参数而不是随机变量。关于为什么要用EM算法而不是不直接通过
得出
,是因为这样可能会出现严重的overfitting (这里不详细说明,请参看Pattern Recognition and Machine Learning一书9.2.1节)。
假设是
上一个概率分布,所以
最后一步是根据Jensen不等式如果
是凹函数,在这个式子中就是对数函数。
就是
而
就是
。 当
是严格的 凹函数的时候,
中等号成立的条件是
是常数,也就是说在这个特定的式子中
,满足这个条件加上之前的
的
其实就是后验概率
(参看http://www.stanford.edu/class/cs229/materials.html Lecture notes: The EM Algorithm)。这就是EM算法中E-step的由来。
M-step一般来说就是个就是二次规划的问题,通过得出
。这里也就不再赘述。
EM算法其实就是coordinate ascent, E-step是将视为常数,选择一个概率分布
使得目标函数
最大化, M-step就是保持
不变,选择
使得目标函数
最大化,因为每一步的目标函数都比前一步的值大,所以只要目标函数存在最大值,EM算法就会收敛。这个过程用图像表示就是:
E-step找到跟(黑色弧线)交于
的
(蓝色弧线),M-step得到
取最大值时的
,这样下去直到收敛。(此图源于Andrew)
相关文章:
- Google’s Python Class
- 一个不错的自然语言处理词典
- 斯坦福大学“自然语言处理”授课视频
- MIT自然语言处理第一讲:简介和概述(第三部分)
- Google’s Python Class – SOS
- 条件随机场文献阅读指南
- Google’s Python Class SOS 续 –下载
- HMM学习最佳范例七:前向-后向算法4
- HMM学习最佳范例七:前向-后向算法2
- HMM学习最佳范例七:前向-后向算法3