EM算法学习(一)

EM算法是英文expectation-maximization算法的英文简写,翻译过来就是期望最大化算法,其实是一种根据求参的极大似然估计的一种迭代的优化策略,EM算法可以广泛估计是因为他可以从非完整的数据集中对于参数进行极大似然的估计,这样的方法对于处理残缺数据,截尾数据和一些带有噪声的数据来说是很有效的.

在写这篇文章之前,我看了很多篇博客,学习了很多的知识,也参照了很多的资料,希望可以从EM算法的迭代优化理论和一般的步骤中出发,然后能够举一个例子来使我们理解这个EM算法,然后在对其收敛性进行证明,目的是为了说明EM算法每一次迭代都是能够提高似然函数值然后收敛到一个稳定的点,再引出EM算法的收敛速度.

大概通过上述部分,我们可以得到基于其简单,收敛,稳定上升的优势,但是也会产生一些缺点,比如收敛速度过慢的加速方法等,在第二篇文章中将会介绍这个处理缺点的方法,然后会写一些关于EM算法的重要应用,包括EM算法在二元正态分布上的参数估计的应用,混合高斯分布参数估计方面的应用,以及EM算法在隐马尔科夫模型上参数的应用(一种EM算法的特殊情形),希望通过这一系列的文章可以让大家理解好EM算法的明显优势以及原理,让我们开始吧!

背景:

极大似然估计和贝叶斯统计其实是作为现在的统计领域中非常热门的领域了,其实来说他们的计算过程是有一定的相似成分的,比如极大似然函数估计在计算的方法上跟贝叶斯的后验概率的计算是非常相似的,学过统计学习的我们知道,贝叶斯是分为两种的大类的,一种是拥有显式的后验分布,这样的一般用于简单的似然函数,另外一种是数据添加的算法,有些时候我们的数据可能会存在缺失或者是似然函数不是显性的,数据添加类在这时候就可以很好的应用,他可以将已经观测到的数据基础上加上一些”潜在数据”,从而使得变得更简单,完成极大化的工作,然后我们常用的一种数据添加法其实就是我们今天介绍的EM算法.

EM算法是一种迭代的优化策略,他的计算方法是分为期望步(E步)和极大步(M步)的,所以这个算法的名字是这样来的,EM算法受到了缺失算法的影响,最初就是为了解决上边提到的数据缺失的问题,基本的思想就是首先根据已经观测出来的数据估计出模型参数的值,然后再根据上一步估计出的参数值来估计缺失数据的值,然后再根据估计中缺失的数据加上之前的已经观测到的数据重新在对参数值进行估计,然后反复的进行迭代,直到最后收敛,迭代结束.

而现在EM算法发展了几十年了,在当时的数据快速增长得那个时代,那时候处理数据很困难,经常会出现数据缺失或者不可用的情况,当时无非就是用用神经网络拟合,添补法,卡尔曼滤波法等等,但是最后还是EM脱颖而出,最主要还是他的算法步骤简单,稳定上升可以很可靠的找到最优的收敛值,但是运用这种思想,我们拓展到了简化问题策略,有时候缺失数据并非真的缺少了,这时候EM引入恰当的数据添加技术,这样的数据被称为”潜在数据”,复杂问题通过引入潜在数据,能够有效的解决我们的问题

“潜在数据”可以解释为数据本身并不存在缺失变量,但观察数据比较难以处理,如果添加上额外的变量,处理起来会变得比较简 单。假设X是已知的观测数据,想象由随机变量X生成的观察数据连同来 自随机变量y的缺失或未观测数据,得到Z=(X,Y)为完全数据。通过给定观察数据X,我们希望最大化似然的函数L(0/x).由于数据缺失或者其他原因导

致采用该似然函数会难以处理,而采用Z|0和Y|(x,0)的密度则比较容易处 理。EM算法通过采用这些较容易的密度p(0|z),从而避开考虑了P(0|X).但是这在贝叶斯应用中,对于后验分布的P都是随机变量.

但是不可避免EM算法也有一些缺点:

1:在缺失数据较多的情形,收敛的速度较慢.

2:对于某些情况下,要计算算法中的M步,即完成对似然函数的估计是非常困难的

3:在某些情况下是要获得EM算法中的E步的期望显式是非常困难或者不可能的

算法原理和步骤:

现在我们假设X是观测数据,Y是潜在数据,EM算法迭代是为了寻求关于0最大化函数L(0|X),设0(k)是在进行K次迭代以后估计得到的最大值点,K属于(0,1,2......),定义Q(0|0(k))

是在观测数据X ={x1,x2….xn}的条件下完全数据的联合对数函数似然的期望,既可以获得以下式子:

通过上式我们可以发现,一旦我们的样本点X给定,那么Y就是Z的唯一的随机部分,通过对于Y求条件期望,就又可以把Y给积分掉了,这样使得Q(0|0(k))就完全成为了一个关于0的函数,这样就可以求使得Q(0|0(k))最大的0,并且记为0(k+1),以供下一次迭代使用.

EM算法从0(0)开始,然后在这两部之间进行交替,E表示期望,M表示最大化,该算法可以概括如下:

1:E步,在给定的观测数据X和已经知道的参数条件下,求缺失数据Y的数学期望,即计算上面的提到的对数似然函数的条件期望Q(0|0(k)).

2:M步,就像不存在缺失数据Y一样(在填充缺失数据后),针对完全数据下的对数似然函数的期望进行最大化处理,即求关于0似然函数Q(0|0(k))的最大化.设0(k+1)等于最大值点,更新0(k):

3:返回E步,知道满足某停止规则为止.一般依赖于

现在使用韩佳伟的数据分析中的例子来详细的说明EM算法:

1:现在假设进行一个实验会出现现在四种结果,每种结果发生的概率分别为:

实验进行了197次,四种结果发生了125,18,20,34次,这个时候的X={x1,x2,x3,x4}={125,18,20,34}

为了估计参数,我们可以取0的先验分布p(0)为U(0,1),由贝叶斯公式可知,0的后验分布为:

把第一种结果分成发生概率分别为1/2和0/4的两个部分,令Y和x1-Y分别表示为这两部分试验成功的次数(Y为缺失数据),则0的添加的后验分布为:

这时候就该轮到了EM算法添加数据了,直接求0的极大似然估计也是比较麻烦的,现在使用EM算法后迭代最后一个后验分布函数就简单多了,(在上面的计算过程中,最下边的那个符号,他表示的是符号两端的式子成比例,并且这个比例跟0无关,这个比例不会影响到EM迭代算法估计的结果,因为后面的极大化可以进行约去).

现在我们假设在第i+1次的迭代中,有估计值0(i),则可以通过EM算法中的E步和M步得到一个新的估计,在E步中:

因为在x和0(i)给定的情况下,Y服从二项式分布,因此可以得到E(Y|X,0(i))=2x(1)/[2+0(i)],于是便有:

在M步中,对上边的式子中的0进行求导并且使结果为0,可以得到迭代的公式为:

这个时候从0(0)=0.5开始,经过EM四次迭代以后收敛到0.6268,根据Matlab进行作图,收敛曲线如下所示:

另外韩佳伟那本书使用的R,我这里使用的是MATLAB,效果类似,都可以实现.

EM算法收敛性证明:

算法简单、收敛稳定是EM算法的最大优点,EM算法的简便性在上文中已经得到充足的认识,现在需要对其估计得到的序列是不是达到了预期 的收敛要求,即EM算法估计的结果是不是能稳定收敛,以及收敛结果是不 是p(0IX)的最大值或局部最大值来进行验证,本文下面需要来证明EM算法的收敛性。

第一步:吉布斯不等式:

当且仅当x=1时,等号成立

{PS:其实吉布斯不等式是詹森不等式的一个特例,因为log(x)是一个凸函数,作图的话就能够发现在某一个时刻,吉布斯不等式和詹森不等式是有交点的在曲线上}

第二步:

现在先引出几个定理:如果f(x),g(x)具有相同的支集的概率密度函数,现在令:

则:

证明:

当且仅当f(x)=g(x)时,等号成立,此时log(g(x)/f(x))=f(x)/g(x)-1

第三步:

记录EM算法的估计序列为{0(k)},证明EM算法每个最大化步都提高了对于观测数据的对数似然函数L(0|X)的值,即:

记:

证明:已知:

然后根据贝叶斯统计先验后验的函数关系式得到:

可以得知,在大样本以及0均匀分布的前提下,其中p(x|0)是已经观测到的X的密度,而p(y|x,0)是给定已经观测到的数据后缺失数据的密度:

记:

则:

从而:

进而得到:

所以:

由M步一直求极大化过程:

可知Q一直在增大,有第二步的定理1得到:

这里可以知道在EM算法在E步和M步的交替运算下,似然函数是不断地变大的,我们就可以认为估计的参数序列最终会收敛到极大似然估计.

如果在每次迭代中,都是通过求似然函数的极大似然估计,选择最大化的0(k+1)来代替0,这样就构成了EM算法,大部分时候极大似然函数都是有显式表达式,但是不是总是这样,所以有时候会有广义EM算法(GEM),增大Q的哪一步也增大了对数似然函数.

这里我不加证明的给出,得到的收敛性结论主要是针对对数似然函数值给出的,而不是针对的估计序列的收敛性;而且在一般的情况下,我们用EM算法得到的估计值0(k),只能保证收敛到似然函数的一个稳定点,并不能其保证收敛到全局最大值点或者局部最大值点。

参考资料:

The EM algorithm 吴恩达

http://blog.csdn.net/zouxy09/article/details/8537620/

http://www.cnblogs.com/openeim/p/3921835.html

以及更多的人的帮助,谢谢他们,接下来将会进行后续的对于加速EM算法收敛的方法,感谢阅读

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏新智元

【深度】解析深度神经网络背后的数学原理

如今,已有许多像 Keras, TensorFlow, PyTorch 这样高水平的专门的库和框架,我们就不用总担心矩阵的权重太多,或是对使用的激活函数求导时存...

24550
来自专栏AI派

一份机器学习模型离线评估方法的详细手册

读完分类与回归算法的评估指标以及排序算法的评估指标之后,你已经知道了机器学习中分类、回归以及排序算法相关的评估指标。在这篇给大家介绍一些机器学习中离线评估模型性...

17720
来自专栏达观数据

技术干货 | 一文详解高斯混合模型原理

高斯混合模型(Gaussian Mixture Model)通常简称GMM,是一种业界广泛使用的聚类算法,该方法使用了高斯分布作为参数模型,并使用了期望最大(E...

49160
来自专栏AI研习社

视频 | 硅谷深度学习网红传授超参数优化宝典

AI 研习社按:今天为大家带来硅谷深度学习网红 Siraj 在人工智能在线大会 AI WITH THE BEST(AIWTB)上的演讲,雷锋字幕组独家译制。本次...

38150
来自专栏人人都是极客

【重磅】彻底让你理解卷积神经网络

在各种深度神经网络结构中,卷积神经网络是应用最广泛的一种,它由LeCun在1989年提出[1]。卷积神经网络在早期被成功应用于手写字符图像识别[1][2][3]...

16440
来自专栏机器之心

学界 | 金字塔注意力网络:一种利用底层像素与高级特征的语义分割网络

在卷积神经网络的近期发展中,根据其丰富的层级特征和端到端的可训练框架,像素级语义分割方面有了可观的进步。但是在编程高维度代表的过程中,原本像素级的环境背景中的空...

21300
来自专栏AI科技大本营的专栏

干货 | 目标检测入门,看这篇就够了(上)

作者 | 李家丞( 同济大学数学系本科在读,现格灵深瞳算法部实习生) 近年来,深度学习模型逐渐取代传统机器视觉方法而成为目标检测领域的主流算法,本系列文章将回顾...

7.9K140
来自专栏专知

【深度学习最精炼中文讲义】前馈与卷积神经网络详解,复旦邱锡鹏老师《神经网络与深度学习》报告分享02(附报告pdf下载)

【导读】复旦大学副教授、博士生导师、开源自然语言处理工具FudanNLP的主要开发者邱锡鹏(http://nlp.fudan.edu.cn/xpqiu/)老师撰...

2K60
来自专栏云时之间

EM算法学习(一)

EM算法是英文expectation-maximization算法的英文简写,翻译过来就是期望最大化算法,其实是一种根据求参的极大似然估计的一种迭代的优化策略,...

39170
来自专栏AI科技大本营的专栏

解析深度神经网络背后的数学原理!

【导读】为了更好地理解神经网络的运作,今天只为大家解读神经网络背后的数学原理。而作者写这篇文章的目的一个是为了整理自己学到的知识;第二个目的也是为了分享给大家,...

13830

扫码关注云+社区

领取腾讯云代金券