标签归档:EM算法

PRML读书会第十章 Approximate Inference

PRML读书会第十章 Approximate Inference

主讲人 戴玮

(新浪微博: @戴玮_CASIA

Wilbur_中博(1954123) 20:02:04

我们在前面看到,概率推断的核心任务就是计算某分布下的某个函数的期望、或者计算边缘概率分布、条件概率分布等等。 比如前面在第九章尼采兄讲EM时,我们就计算了对数似然函数在隐变量后验分布下的期望。这些任务往往需要积分或求和操作。 但在很多情况下,计算这些东西往往不那么容易。因为首先,我们积分中涉及的分布可能有很复杂的形式,这样就无法直接得到解析解,而我们当然希望分布是类似指数族分布这样具有共轭分布、容易得到解析解的分布形式;其次,我们要积分的变量空间可能有很高的维度,这样就把我们做数值积分的路都给堵死了。因为这两个原因,我们进行精确计算往往是不可行的。
为了解决这一问题,我们需要引入一些近似计算方法。

近似计算有随机和确定两条路子。随机方法也就是MCMC之类的采样法,我们会在讲第十一章的时候专门讲到,而确定近似法就是我们这一章讲的变分。变分法的优点主要是:有解析解、计算开销较小、易于在大规模问题中应用。但它的缺点是推导出想要的形式比较困难。也就是说,人琢磨的部分比较复杂,而机器算的部分比较简单。这和第十一章的采样法的优缺点恰好有互补性。所以我们可以在不同的场合应用变分法或采样法。这里我的一个问题是:是否可以结合二者的优点,使得人也不用考虑太多、机器算起来也比较简单?
变分法相当于把微积分从变量推广到函数上。我们都知道,微积分是用来分析变量变化、也就是函数性质的,这里函数定义为f: x -> f(x),而导数则是df/dx;与之相对,变分用到了泛函的概念:F: f -> F(f),也就是把函数映射为某个值,而相应地,也有导数dF/df,衡量函数是如何变化的。比如我们熟悉的信息论中的熵,就是把概率分布这个函数映射到熵这个值上。和微积分一样,我们也可以通过导数为0的条件求解无约束极值问题,以及引入拉格朗日乘子来求解有约束极值问题。比如说,我们可以通过概率分布积分为1的约束,求解最大熵的变分问题。PRML的附录D和E有比较详细的解释,我们后面也还会看到,这里就不多说了。
变分法这名字听起来比较可怕,但它的核心思想,就是从某个函数空间中找到满足某些条件或约束的函数。我们在统计推断当中用到的变分法,实际上就是用形式简单的分布,去近似形式复杂、不易计算的分布,这样再做积分运算就会容易很多。 比如,我们可以在所有高斯分布当中,选一个和目标分布最相似的分布,这样后面做进一步计算时就容易获得解析解。此外,我们还可以假设多元分布的各变量之间独立,这样积分的时候就可以把它们变成多个一元积分,从而解决高维问题。这也是最简单的两种近似。
继续阅读

PRML读书会第九章 Mixture Models and EM

PRML读书会第九章 Mixture Models and EM

主讲人 网络上的尼采

(新浪微博: @Nietzsche_复杂网络机器学习

网络上的尼采(813394698) 9:10:56
今天的主要内容有k-means、混合高斯模型、 EM算法。
对于k-means大家都不会陌生,非常经典的一个聚类算法,已经50多年了,关于clustering推荐一篇不错的survey:

Data clustering: 50 years beyond K-means。k-means表达的思想非常经典,就是对于复杂问题分解成两步不停的迭代进行逼近,并且每一步相对于前一步都是递减的。
k-means有个目标函数 :

假设有k个簇,是第k个簇的均值;每个数据点都有一个向量表示属于哪个簇,rnk是向量的元素,如果点xn属于第k个簇,则rnk是1,向量的其他元素是0。
上面这个目标函数就是各个簇的点与簇均值的距离的总和,k-means要做的就是使这个目标函数最小。 这是个NP-hard问题,k-means只能收敛到局部最优。
继续阅读

PRML读书会第二章 Probability Distributions

PRML读书会第二章 Probability Distributions

主讲人 网络上的尼采

(新浪微博:@Nietzsche_复杂网络机器学习

网络上的尼采(813394698) 9:11:56

开始吧,先不要发言了,先讲PRML第二章Probability Distributions。今天的内容比较多,还是边思考边打字,会比较慢,大家不要着急,上午讲不完下午会接着讲。
顾名思义,PRML第二章Probability Distributions的主要内容有:伯努利分布、 二项式 –beta共轭分布、多项式分布 -狄利克雷共轭分布 、高斯分布 、频率派和贝叶斯派的区别联系 、指数族等。
先看最简单的伯努利分布:

prml2-1

最简单的例子就是抛硬币,正反面的概率。
再看二项式分布:

prml2-2

抛N次有m次是正面或反面的概率,所以伯努利分布是二项式分布的特例。

向大家推荐一本好书,陈希孺的《数理统计简史》,对数理统计的一些基本东西的来龙去脉介绍的很详细,这样有助于理解。先818二项式分布,正态分布被发现前,二项式分布是大家研究的主要内容。
由二项式分布可以推出其他很多分布形式,比如泊松定理:

prml2-3

泊松分布是二项式分布的极限形式,这个估计大家都推导过。由二项式分布也能推出正态分布。
贝叶斯思想也是当时对二项式分布做估计产生的,后来沉寂了一百多年。

数据少时用最大似然方法估计参数会过拟合,而贝叶斯方法认为模型参数有一个先验分布,因此共轭分布在贝叶斯方法中很重要,现在看二项式分布的共轭分布beta分布:

prml2-4

结合上面的二项式分布的形式,不难看出beta分布和二项式分布的似然函数有着相同的形式,这样用beta分布做二项式分布参数的先验分布,乘似然函数以后得到的后验分布依然是beta分布。 继续阅读

概率语言模型及其变形系列-PLSA及EM算法

本系列博文介绍常见概率语言模型及其变形模型,主要总结PLSA、LDA及LDA的变形模型及参数Inference方法。初步计划内容如下

第一篇:PLSA及EM算法

第二篇:LDA及Gibbs Samping

第三篇:LDA变形模型-Twitter LDA,TimeUserLDA,ATM,Labeled-LDA,MaxEnt-LDA等

第四篇:基于变形LDA的paper分类总结

第五篇:LDA Gibbs Sampling 的JAVA实现

第一篇 PLSA及EM算法

[Update 2012/12/21 为了解决部分朋友反映的网页图片无法显示的问题,更新PDF版本

下载地址 PLSA及EM算法-yangliuy]

前言:本文主要介绍PLSA及EM算法,首先给出LSA(隐性语义分析)的早期方法SVD,然后引入基于概率的PLSA模型,其参数学习采用EM算法。接着我们分析如何运用EM算法估计一个简单的mixture unigram 语言模型和混合高斯模型GMM的参数,最后总结EM算法的一般形式及运用关键点。对于改进PLSA,引入hyperparameter的LDA模型及其Gibbs Sampling参数估计方法放在本系列后面的文章LDA及Gibbs Samping介绍。
继续阅读

理解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)

HMM学习最佳范例七:前向-后向算法5

七、前向-后向算法(Forward-backward algorithm)

  上一节我们定义了两个变量及相应的期望值,本节我们利用这两个变量及其期望值来重新估计隐马尔科夫模型(HMM)的参数pi,A及B: 继续阅读

HMM学习最佳范例七:前向-后向算法4

七、前向-后向算法(Forward-backward algorithm)

  隐马尔科夫模型(HMM)的三个基本问题中,第三个HMM参数学习的问题是最难的,因为对于给定的观察序列O,没有任何一种方法可以精确地找到一组最优的隐马尔科夫模型参数(A、B、pi)使P(O|lamda)最大。因而,学者们退而求其次,不能使P(O|lamda)全局最优,就寻求使其局部最优(最大化)的解决方法,而前向-后向算法(又称之为Baum-Welch算法)就成了隐马尔科夫模型学习问题的一种替代(近似)解决方法。 继续阅读

HMM学习最佳范例七:前向-后向算法3

七、前向-后向算法(Forward-backward algorithm)

  前向-后向算法是Baum于1972年提出来的,又称之为Baum-Welch算法,虽然它是EM(Expectation-Maximization)算法的一个特例,但EM算法却是于1977年提出的。那么为什么说前向-后向算法是EM算法的一个特例呢?这里有两点需要说明一下。 继续阅读

HMM学习最佳范例七:前向-后向算法2

七、前向-后向算法(Forward-backward algorithm)

  要理解前向-后向算法,首先需要了解两个算法:后向算法和EM算法。后向算法是必须的,因为前向-后向算法就是利用了前向算法与后向算法中的变量因子,其得名也因于此;而EM算法不是必须的,不过由于前向-后向算法是EM算法的一个特例,因此了解一下EM算法也是有好处的,说实话,对于EM算法,我也是云里雾里的。好了,废话少说,我们先谈谈后向算法。 继续阅读