EM算法原理总结

作者:刘建平

编辑:田 旭

授权转发自:刘建平《EM算法原理总结》

地址:http://www.cnblogs.com/pinard/p/6912636.html

简 介

EM算法也称期望最大化(Expectation-Maximum,简称EM)算法,它是一个基础算法,是很多机器学习领域算法的基础,比如隐式马尔科夫算法(HMM), LDA主题模型的变分推断等等。本文就对EM算法的原理做一个总结。

01

EM算法要解决的问题

我们经常会从样本观察数据中,找出样本的模型参数。 最常用的方法就是极大化模型分布的对数似然函数。

但是在一些情况下,我们得到的观察数据有未观察到的隐含数据,此时我们未知的有隐含数据和模型参数,因而无法直接用极大化对数似然函数得到模型分布的参数。怎么办呢?这就是EM算法可以派上用场的地方了。

EM算法解决这个的思路是使用启发式的迭代方法,既然我们无法直接求出模型分布参数,那么我们可以先猜想隐含数据(EM算法的E步),接着基于观察数据和猜测的隐含数据一起来极大化对数似然,求解我们的模型参数(EM算法的M步)。由于我们之前的隐藏数据是猜测的,所以此时得到的模型参数一般还不是我们想要的结果。不过没关系,我们基于当前得到的模型参数,继续猜测隐含数据(EM算法的E步),然后继续极大化对数似然,求解我们的模型参数(EM算法的M步)。以此类推,不断的迭代下去,直到模型分布参数基本无变化,算法收敛,找到合适的模型参数。

从上面的描述可以看出,EM算法是迭代求解最大值的算法,同时算法在每一次迭代时分为两步,E步和M步。一轮轮迭代更新隐含数据和模型分布参数,直到收敛,即得到我们需要的模型参数。

一个最直观了解EM算法思路的是K-Means算法,见之前写的K-Means聚类算法原理。在K-Means聚类时,每个聚类簇的质心是隐含数据。我们会假设K个初始化质心,即EM算法的E步;然后计算得到每个样本最近的质心,并把样本聚类到最近的这个质心,即EM算法的M步。重复这个E步和M步,直到质心不再变化为止,这样就完成了K-Means聚类。

当然,K-Means算法是比较简单的,实际中的问题往往没有这么简单。上面对EM算法的描述还很粗糙,我们需要用数学的语言精准描述。

02

EM算法的推导

对于m个样本观察数据

,找出样本的模型参数

,极大化模型分布的对数似然函数如下:

如果我们得到的观察数据有未观察到的隐含数据

,此时我们的极大化模型分布的对数似然函数如下:

上面这个式子是没有 办法直接求出

的。因此需要一些特殊的技巧,我们首先对这个式子进行缩放如下:

上面第(1)式引入了一个未知的新的分布

,第(2)式用到了Jensen不等式:

或者说由于对数函数是凹函数,所以有:

此时如果要满足Jensen不等式的等号,则有:

由于

是一个分布,所以满足:

从上面两式,我们可以得到:

如果

, 则第(2)式是我们的包含隐藏数据的对数似然的一个下界。如果我们能极大化这个下界,则也在尝试极大化我们的对数似然。即我们需要最大化下式:

去掉上式中为常数的部分,则我们需要极大化的对数似然下界为:

上式也就是我们的EM算法的M步,那E步呢?注意到上式中

是一个分布,因此

可以理解为

基于条件概率分布

的期望。

至此,我们理解了EM算法中E步和M步的具体数学含义。

03

EM算法流程

现在我们总结下EM算法的流程。

输入:观察数据

,联合分布

,条件分布

,最大迭代次数J。

1) 随机初始化模型参数

的值

2) for j from 1 to J开始EM算法迭代:

a) E步:计算联合分布的条件概率期望:

   b) M步:极大化

,得到

c) 如果

已收敛,则算法结束。否则继续回到步骤a)进行E步迭代。

输出:模型参数

04

EM算法收敛性思考

EM算法的流程并不复杂,但是还有两个问题需要我们思考:

  1) EM算法能保证收敛吗?

  2) EM算法如果收敛,那么能保证收敛到全局最大值吗? 

首先我们来看第一个问题, EM算法的收敛性。要证明EM算法收敛,则我们需要证明我们的对数似然函数的值在迭代的过程中一直在增大。即:

由于

令:

上两式相减得到:

在上式中分别取

,并相减得到:

要证明EM算法的收敛性,我们只需要证明上式的右边是非负的即可。

由于

使得

极大,因此有:

而对于第二部分,我们有:

其中第(4)式用到了Jensen不等式,只不过和第二节的使用相反而已,第(5)式用到了概率分布累积为1的性质。

至此,我们得到了:

证明了EM算法的收敛性。

从上面的推导可以看出,EM算法可以保证收敛到一个稳定点,但是却不能保证收敛到全局的极大值点,因此它是局部最优的算法,当然,如果我们的优化目标

是凸的,则EM算法可以保证收敛到全局最大值,这点和梯度下降法这样的迭代算法相同。至此我们也回答了上面提到的第二个问题。

05

EM算法的一些思考

如果我们从算法思想的角度来思考EM算法,我们可以发现我们的算法里已知的是观察数据,未知的是隐含数据和模型参数,在E步,我们所做的事情是固定模型参数的值,优化隐含数据的分布,而在M步,我们所做的事情是固定隐含数据分布,优化模型参数的值。比较下其他的机器学习算法,其实很多算法都有类似的思想。比如SMO算法(支持向量机原理(四)SMO算法原理),坐标轴下降法(Lasso回归算法: 坐标轴下降法与最小角回归法小结), 都使用了类似的思想来求解问题。

大家也可以去比较下这些算法的优化方法,看思路上是不是有共同之处。

END

原文发布于微信公众号 - 机器学习算法工程师(Jeemy110)

原文发表时间:2018-07-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

徒手实现CNN:综述论文详解卷积网络的数学本质

选自arXiv 机器之心编译 参与:黄小天、路雪、蒋思源 近日南洋理工大学研究者发布了一篇描述卷积网络数学原理的论文,该论文从数学的角度阐述整个卷积网络的运算与...

380110
来自专栏机器学习算法工程师

梯度提升树(GBDT)原理小结

地址:https://www.cnblogs.com/pinard/p/6140514.html

18720
来自专栏磐创AI技术团队的专栏

使用Keras进行深度学习:(三)使用text-CNN处理自然语言(下)

前言:在上一篇文章中,已经介绍了Keras对文本数据进行预处理的一般步骤。预处理完之后,就可以使用深度学习中的一些模型进行文本分类。在这篇文章中,将介绍text...

44840
来自专栏梦里茶室

读论文系列:Object Detection ECCV2016 SSD

转载请注明作者:梦里茶 Single Shot MultiBox Detector Introduction 一句话概括:SSD就是关于类别的多尺度RPN...

32460
来自专栏杨熹的专栏

常用激活函数比较

本文结构: 什么是激活函数 为什么要用 都有什么 sigmoid ,ReLU, softmax 的比较 如何选择 ---- 1. 什么是激活函数 如下图,在神经...

49680
来自专栏计算机视觉战队

卷积神经网络就是这么简单就能学会

卷积神经网络和前几次介绍的神经网络非常相似:它们都是由神经元组成,神经元中有具有学习能力的权重和偏差。每个神经元都得到一些输入数据,进行内积运算后再进行激活函数...

14120
来自专栏机器学习算法与Python学习

Pre-training到底有没有用?何恺明等人新作:Rethinking ImageNet Pre-training

使用基于ImageNet预训练(Pre-training)的网络已成为计算机视觉任务中一种常规的操作。何恺明等人在新作Rethinking ImageNet P...

11120
来自专栏人工智能头条

北大、北理工、旷视联手:用于图像语义分割的金字塔注意力网络

21880
来自专栏null的专栏

优化算法——梯度下降法

一、优化算法概述     优化算法所要求解的是一个问题的最优解或者近似最优解。现实生活中有很多的最优化问题,如最短路径问题,如组合优化问题等等,同样,也存在很多...

45760
来自专栏一直在跳坑然后爬坑

向量空间相关概念总结-线性相关

严格定义: 如果存在不全为零的实数k1、k2...km,使上面的等式成立,则这个向量组线性相关,否则线性无关。 注:这里这个向量组里是包含...

18530

扫码关注云+社区

领取腾讯云代金券