理解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-step和M-step，E-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).