理解EM算法

标签: 机器学习 EM EM算法 | 发表时间:2011-04-05 17:25 | 作者:jenna Chin
出处:http://www.52nlp.cn

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)

相关文章:

  1. Google’s Python Class
  2. 一个不错的自然语言处理词典
  3. 斯坦福大学“自然语言处理”授课视频
  4. MIT自然语言处理第一讲:简介和概述(第三部分)
  5. Google’s Python Class – SOS
  6. 条件随机场文献阅读指南
  7. Google’s Python Class SOS 续 –下载
  8. HMM学习最佳范例七:前向-后向算法4
  9. HMM学习最佳范例七:前向-后向算法2
  10. HMM学习最佳范例七:前向-后向算法3

相关 [理解 em 算法] 推荐:

理解EM算法

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

px和em的战争

- 小明 - 博客园-首页原创精华区
其实我就是想说px和em的区别,网上资料其实一堆堆,但是还不如自己试验总结的清楚. 前端高手可能觉得这玩意简单,但是作为小猫,还是好好学一下. px和em都是长度单位,区别是,px的值是固定的,指定是多少就是多少,计算比较容易. em得值不是固定的,并且em会继承父级元素的字体大小. 任意浏览器的默认字体高都是16px.

在EM中管理Metric

- - CSDN博客数据库推荐文章
Metric的引入主要为了实现proactive(积极、主动)维护数据库:. 在EM中可以对Metrics进行管理:. 在这里可以对各项指标设置告警的Warning Threshold(阈值):. 就如我们刚才设置的,如果表空间使用率超过35%,则会告警:. 点击我们可以看到系统给出的建议,当然也可以在视图中查看:.

转载一篇单字符串匹配KMP算法最好理解的文章

- - 编程语言 - ITeye博客
字符串匹配是计算机的基本任务之一.   举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD".   许多算法可以完成这个任务,. Knuth-Morris-Pratt算法(简称KMP)是最常用的之一. 它以三个发明者命名,起头的那个K就是著名科学家Donald Knuth.

缓存算法

- lostsnow - 小彰
没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率. 我是LRU缓存算法,我把最近最少使用的缓存对象给踢走. 我总是需要去了解在什么时候,用了哪个缓存对象.

BFPRT算法

- zii - 小彰
BFPRT算法的作者是5位真正的大牛(Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan),该算法入选了在StackExchange上进行的当今世界十大经典算法,而算法的简单和巧妙颇有我们需要借鉴学习之处. BFPRT解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度.

贪心算法

- Shan - 博客园-首页原创精华区
顾名思义,贪心算法总是作出在当前看来最好的选择. 也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择. 当然,希望贪心算法得到的最终结果也是整体最优的. 虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解. 如单源最短路经问题,最小生成树问题等.

缓存算法

- 成 - FeedzShare
来自: 小彰 - FeedzShare  . 发布时间:2011年09月25日,  已有 2 人推荐. 没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率.

K-Means 算法

- - 酷壳 - CoolShell.cn
最近在学习一些数据挖掘的算法,看到了这个算法,也许这个算法对你来说很简单,但对我来说,我是一个初学者,我在网上翻看了很多资料,发现中文社区没有把这个问题讲得很全面很清楚的文章,所以,把我的学习笔记记录下来,分享给大家. k-Means 算法是一种  cluster analysis 的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法.

查找算法:

- - CSDN博客推荐文章
从数组的第一个元素开始查找,并将其与查找值比较,如果相等则停止,否则继续下一个元素查找,直到找到匹配值. 注意:要求被查找的数组中的元素是无序的、随机的. 比如,对一个整型数组的线性查找代码:. // 遍历整个数组,并分别将每个遍历元素与查找值对比. 要查找的值在数组的第一个位置. 也就是说只需比较一次就可达到目的,因此最佳情况的大O表达式为:O(1).