Expectation Maximization Algorithm(EM)算法_exposure maximization-程序员宅基地

技术标签: 统计学  EM算法  

一、基础数学知识

      在正式介绍EM算法之前,先介绍推导EM算法用到的数学基础知识,包括凸函数,Jensen不等式。

    1.凸函数

      对于凸函数,凹函数,如果大家学过高等数学,都应该知道,需要注意的是国内教材如同济大学的《高等数学》的这两个概念跟国外刚好相反,为了能更好的区别,本文章把凹凸函数称之为上凸函数,下凸函数,具体定义如下

上凸函数:函数f(x)满足对定义域上任意两个数a,b都有f[(a+b)/2] ≥ [f(a)+f(b)]/2

下凸函数:函数f(x)满足对定义域上任意两个数a,b都有f[(a+b)/2] ≤ [f(a)+f(b)]/2

更直观的可以看图2.1和2.2:

                

      可以清楚地看到图2.1上凸函数中,f[(a+b)/2] ≥ [f(a)+f(b)]/2,而且不难发现,如果f(x)是上凸函数,那么-f(x)是下凸函数。

      当a≠b时,f[(a+b)/2] > [f(a)+f(b)]/2成立,那么称f(x)为严格的上凸函数,等号成立的条件当且仅当a=b,下凸函数与其类似。

2.Jensen不等式

            有了上述凸函数的定义后,我们就能很清楚的Jensen不等式的含义,它的定义如下:

      如果f是上凸函数,X是随机变量,那么f(E[X]) ≥ E[f(X)] 

特别地,如果f是严格上凸函数,那么E[f(X)] = f(E[X])当且仅当p(X=E[X]),也就是说X是常量。

    那么很明显 log x 函数是上凸函数,可以利用这个性质。

有了上述的数学基础知识后,我们就可以看具体的EM算法了。


二、EM算法所解决问题的例子

在推导EM算法之前,先引用《统计学习方法》中EM算法的例子:

例1. (三硬币模型) 假设有3枚硬币,分别记作A,B,C。这些硬币正面出现的概率分别为π,pq。投币实验如下,先投A,如果A是正面,即A=1,那么选择投B;A=0,投C。最后,如果B或者C是正面,那么y=1;是反面,那么y=0;独立重复n次试验(n=10),观测结果如下: 1,1,0,1,0,0,1,0,1,1假设只能观测到投掷硬币的结果,不能观测投掷硬币的过程。问如何估计三硬币正面出现的概率,即π,pq的值。

  解:设随机变量y是观测变量,则投掷一次的概率模型为

 
   
   
       有n次观测数据Y,那么观测数据Y的似然函数为

      
       那么利用最大似然估计求解模型解,即



      
这里将概率模型公式和似然函数代入(1)式中,可以很轻松地推出 (1)=> (2) => (3),然后选取θ(π,p,q),使得(3)式值最大,即最大似然。然后,我们会发现因为(3)中右边多项式+符号的存在,使得(3)直接求偏导等于0或者用梯度下降法都很难求得θ值。


      这部分的难点是因为(3)多项式中+符号的存在,而这是因为这个三硬币模型中,我们无法得知最后得结果是硬币B还是硬币C抛出的这个隐藏参数。那么我们把这个latent 随机变量加入到 log-likelihood 函数中,得


     
      略看一下,好像很复杂,其实很简单,请容我慢慢道来。首先是公式(4),这里将zi做为隐藏变量,当z1为结果由硬币B抛出,z2为结果由硬币C抛出,不难发现



  
       
注:一下Q中有些许漏了下标j,但不影响理解

       接下来公式说明(4)=> (5)(其中(5)中Q(z)表示的是关于z的某种分布,),很直接,在P的分子分母同乘以Q(zi)。最后是(5)=>(6),到了这里终于用到了第二节介绍的Jensen不等式,数学好的人可以很快发现,

             就是的期望值(如果不懂,可google期望公式并理解),


       且log是上凸函数,所以就可以利用Jensen不等式得出这个结论。因为我们要让log似然函数l(θ)最大,那么这里就要使等号成立。根据Jensen不等式可得,要使等号成立,则要使成立。

       再因为,所以得,c为常数,那么


      这里可以发现




     
 OK,到这里,可以发现公式(6)中右边多项式已经不含有“+”符号了,如果知道Q(z)的所有值,那么可以容易地进行最大似然估计计算,但是Q的计算需要知道θ的值。这样的话,我们是不是可以先对θ进行人为的初始化θ0,然后计算出Q的所有值Q1(在θ0固定的情况下,可在Q1取到公式(6)的极大值),然后在对公式(6)最大似然估计,得出新的θ1(在固定Q1的情况下,取到公式(6)的极大值),这样又可以计算新的Q值Q1,然后依次迭代下去。答案当然是可以。因为Q1是在θ0的情况下产生的,可以调节公式(6)中θ值,使公式(6)的值再次变大,而θ值变了之后有需要调节Q使(6)等号成立,结果又变大,直到收敛(单调有界必收敛),如果到现在还不是很清楚,具体清晰更广义的证明可以见下部分EM算法说明。

     ps:看到上述红色内容,如果大家懂得F函数的极大-极大算法的话,就可以知道其实它们是一码事。

    另外对公式(6)进行求偏导等于0,求最大值,大家可以自己练习试试,应该很简单的,这里不做过多陈述。
     
    在《统计学习方法》书中,进行两组具体值的计算

      
(1)π0=0.5, p0=0.5, q0=0.5,迭代结果为π=0.5, p=0.6, q=0.5
      (2)π0=0.4, p0=0.6, q0=0.7,迭代结果为π=0.4064, p=0.5368, q=0.6432
    两组值的最后结果不相同,这说明EM算法对初始值敏感,选择不同的初值可能会有不同的结果,只能保证参数估计收敛到稳定点。因此实际应用中常用的办法就是选取多组初始值进行迭代计算,然后取结果最好的值。

     在进行下部分内容之前,还需说明下一个东西。在上面的举例说明后,其实可以发现上述的解决方法跟一个简单的聚类方法很像,没错,它就是K-means聚类(不懂的见百度百科关于K-means算法的说明)。K-means算法先假定k个中心,然后进行最短距离聚类,之后根据聚类结果重新计算各个聚类的中心点,一次迭代,是不是很像,而且K-means也是初始值敏感,因此其实K-means算法也包含了EM算法思想,只是这边EM算法中用P概率计算,而K-means直接用最短距离计算。所以EM算法可以用于无监督学习。在下一篇文章,我准备写下典型的用EM算法的例子,高斯混合模型(GMM,Gaussian Mixture Model)


、EM算法

1.模型说明

      考虑一个参数估计问题,现有共n个训练样本,需有多个参数θ去拟合数据,那么这个log似然函数是:

      可能因为θ中多个参数的某种关系(如上述例子中以及高斯混合模型中的3类参数),导致上面的log似然函数无法直接或者用梯度下降法求出最大值时的θ值,那么这时我们需要加入一个隐藏变量z,以达到简化l(θ),迭代求解l(θ)极大似然估计的目的。

 

2.EM算法推导

    这小节会对EM算法进行具体推导,许多跟上面例子的解法推导是相同的,如果已经懂了,可以加速阅读。首先跟“三硬币模型”一样,加入隐变量z后,假设Q(z)是关于隐变量z的某种分布,那么有如下公式:


    公式(7)是加入隐变量,(7)=>(8)是在基础上分子分母同乘以,(8)=>(9)用到Jensen不等式(跟“三硬币模型”一样),等号成立的条件是,c是常数。再因为,则有如下Q的推导:

    再一次重复说明,要使(9)等式成立,则为yj,z的后验概率。算出后(9)就可以进行求偏导,以剃度下降法求得θ值,那么又可以计算新的值,依次迭代,EM算法就实现了。

EM算法(1):

选取初始值θ0初始化θ,t=0

Repeat {

      E步:

            

      M步:

            

}直到收敛

 

  3.EM算法收敛性证明

    当θ取到θt值时,求得

    那么可得如下不等式:

    (10)=>(11)是因为Jensen不等式,因为等号成立的条件是θ为θt的时候得到的,而现在中的θ值为θt+1,所以等号不一定成立,除非θt+1t

    (11)=>(12)是因为θt+1已经使得取得最大值,那必然不会小于(12)式。

    所以l(θ)在迭代下是单调递增的,且很容易看出l(θ)是有上界的(单调有界收敛),则EM算法收敛性得证。

 

      4.EM算法E步说明

   上述EM算法描述,主要是参考Andrew NG教授的讲义,如果看过李航老师的《统计方法学》,会发现里面的证明以及描述表明上有些许不同,Andrew NG教授的讲义的说明(如上述)将隐藏变量的作用更好的体现出来,更直观,证明也更简单,而《统计方法学》中则将迭代之间θ的变化罗列的更为明确,也更加准确的描述了EM算法字面上的意思:每次迭代包含两步:E步,求期望;M步,求极大化。下面列出《统计方法学》书中的EM算法,与上述略有不同:

EM算法(2):

选取初始值θ0初始化θ,t=0

Repeat {

 E步:

 

M步:

 

}直到收敛

    (13)式中,Y={y1,y2,...,ym},Z={z1,z2,...,zm},不难看出将(9)式中两个Σ对换,就可以得出(13)式,而(13)式即是关于分布z的一个期望值,而需要求这个期望公式,那么要求出所有的EM算法(1)中E步的值,所以两个表明看起来不同的EM算法描述其实是一样的。


四、小结

    EM算法的基本思路就已经理清,它计算是含有隐含变量的概率模型参数估计,能使用在一些无监督的聚类方法上。在EM算法总结提出以前就有该算法思想的方法提出,例如HMM中用的Baum-Welch算法就是。

     在EM算法的推导过程中,最精妙的一点就是(10)式中的分子分母同乘以隐变量的一个分布,而套上了Jensen不等式,是EM算法顺利的形成。


 


转自:http://www.cnblogs.com/mindpuzzle/archive/2013/04/05/2998746.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u010555688/article/details/24538717

智能推荐

Unable to delete directory 'E:\workspace-android\xxx\app\build' Failed to delete some children. This-程序员宅基地

文章浏览阅读2.8k次。版本问题解决方法第一步:共享2. 第二步:停止共享3. android studio : Clean Project4. 错误解决如果你觉得有用,那就点个赞吧!!!

jsp使用七牛云API和webuploader上传多组图片_jsp界面上传多张图片-程序员宅基地

文章浏览阅读1.7k次。文章目录jsp使用七牛云API和webuploader上传多组图片介绍目录树遇到的问题上传组件的选择问题进度条多线程前端界面数据库关键代码UserPhotoDaoImplUploadServletJDBCServletlist.jspadd.jsppom.xml参考jsp使用七牛云API和webuploader上传多组图片介绍前作:JavaWeb servlet jsp 使用七牛云API上传图片使用mysql保存图片七牛云路径,在上传图片的时候直接上传到七牛云前端使用了layui,图片多组上传使用_jsp界面上传多张图片

matlab处理汉字文本,Matlab读取CSV文件(补足六个汉字).docx-程序员宅基地

文章浏览阅读854次。Matlab读取CSV文件环境:Matlab R2009a,Win 71、用csvread函数注意:csvread函数只试用与用逗号分隔的纯数字文件第一种:M = CSVREAD('FILENAME') ,直接读取csv文件的数据,并返回给M第二种:M = CSVREAD('FILENAME',R,C) ,读取csv文件中从第R-1行,第C-1列的数据开始的数据,这对带有头文件说明的csv文件(如..._matlab读取csv文件中的文字

在Jetson Nano上学习ROS的记录(版本Ubuntu18.04,课程来源赵虚左老师的《ROS理论与实践》)第二章 话题通信_jeston nano python与ros通信-程序员宅基地

文章浏览阅读1.3k次,点赞11次,收藏11次。系列文章目录第一章 ROS空间创建、helloworld的实现、开启多个节点第二章 话题通信文章目录系列文章目录前言一、话题通信是什么?二、话题通信基本操作(Python)1.流程2.编写发布方3.订阅方4.话题通信自定义msg总结前言现在大二,之前大一有幸参加了2021的国赛,很壮烈的拿了个江苏赛区的二等奖。但发现无人机这个题,真的是往堆钱上走了。不上ROS不行,现在来记录一下一个纯小白学习ROS的过程和遇到的问题。防止学弟、学妹们再走我走过的弯路。板子用的是学长给的Jetson Nano(_jeston nano python与ros通信

笔记本usb转vga外连显示器问题解决记录_usb转vga连接显示器没反应-程序员宅基地

文章浏览阅读7.7k次,点赞5次,收藏4次。由于工位的笔记本只有十分老式的DELL老款显示器,只有双头vga接口,电脑上无vga接口,手头只有一个达尔稳的usb转接vga接口,笔记本的usb外接和显示器相连相连。最近买了一台新的笔记本,直接插上转接口无法点亮外接屏,显示驱动错误,由于忘记老笔记本当时使用的是何转接驱动,问了网店客服未得到明确答案,前后尝试下载了绿联的官方驱动、以及百度查找的驱动下载等,驱动名称诸如DisplayLink,但是下载完电脑依旧无法识别usb转vga。后来打开老笔记本,在驱动精灵的驱动管理一项项对比,发现使用的是Fresc_usb转vga连接显示器没反应

[Adobe Devnet]嵌入字体_adobedevabagaru字体-程序员宅基地

文章浏览阅读794次。http://www.riadev.com/forum.php?mod=viewthread&tid=587嵌入字体 - RIAMeeting翻译小组 - 王成 2 D$ d$ A; b9 c4 R 在这张图的下面,你能看到2个版本的XYZ公司的Logo. 5 o: g4 q0 T2 B$ K' G- w 这两个版本都是由一个球形图案加上文字"XYZ Company"组成的。 在屏幕左侧的_adobedevabagaru字体

随便推点

JS 分页打印_js打印表格在一页显示-程序员宅基地

文章浏览阅读1.3k次。在调用window.print()时,可以实现打印效果,但内容太多时要进行分页打印。在样式中有规定几个打印的样式page-break-before和page-break-afterCSS属性并不会修改网页在屏幕上的显示,这两个属性是用来控制文件的打印方式。每个打印属性都可以设定4种设定值:auto、always、left和right。其中Auto是默认值,只有在有需要时,才需设定分页符号 (Pa..._js打印表格在一页显示

XXL-JOB原理--任务调度中心任务管理(四)_triggerkey triggerkey = triggerkey.triggerkey(jobn-程序员宅基地

文章浏览阅读2.1w次,点赞3次,收藏32次。 在任务调度中心可以进行新建任务,新建任务之后可以在任务列表中查看相关任务,任务可以根据我们配置的cron表达式进行任务调度,或者也可以在任务列表中执行、暂停、删除和查看相关运行日志等操作。一、任务调度中心管理1、新建任务、2、任务列表任务操作二、任务创建与操作 我们了解到xxl-job是基于quartz来实现定时任务的(其实任务调度中心任务执行..._triggerkey triggerkey = triggerkey.triggerkey(jobname, jobgroup)

关于计算机基础的重要性_学习计算机基础的意义-程序员宅基地

文章浏览阅读2.2k次,点赞4次,收藏11次。计算机基础的重要性,推荐了http://bbs.theithome.com/read-htm-tid-123.html的帖子,但是网站已经上不去了,从别处搜来看了,觉得很有道理,与大家共享一下。 我始终认为,对一个初学者来说,IT界的技术风潮是不可以追赶的,而且也没有能力去追赶。 我时常看见自己的DDMM们把课本扔了,去卖些价格不菲的诸如C#, VB.Net_学习计算机基础的意义

RTL8762C SDK开发-点ST7567(TM9665)屏-程序员宅基地

文章浏览阅读605次,点赞2次,收藏4次。本文参考:1)如何使用STM32F103驱动ST7567液晶屏2)瑞昱rtl8762芯片通过SPI控制st7789,从而实现LCD显示_Small_Six_的博客-程序员宅基地1、瑞昱rtl8762芯片通过SPI控制st7789,从而实现LCD显示_Small_Six_的博客-程序员宅基地中关于怎么SPI驱动屏写的很清楚,不再赘述,本文只是模仿。2、完整的源码以后在贴吧,现在源码审核的时间太长。_st7567

go语言中文乱码gbk转UTF8_go gbk转utf8中文乱码-程序员宅基地

文章浏览阅读1.5k次。/** * gbk转utf8 */func coverGBKToUTF8(src string) string { return mahonia.NewDecoder("gbk").ConvertString(src)}/** * 替换乱码 */func replaceNullHtml(src string) string { temp := strings.Replace(src, "聽", "", -1) return temp}/** * gbk转utf8 */fun._go gbk转utf8中文乱码

pythonFlask框架学习_flask layout-程序员宅基地

文章浏览阅读1k次,点赞3次,收藏33次。Flask是由python实现的一个web微框架,让我们可以使用Python语言快速实现一个网站或Web服务。而且有对应的python3及python2版本。首先这边选择的是python3.6,虽然python3在网上好像名声不咋地,而且一度有文章说python3正在毁灭Python,但是反正是别人选的,也就将就了。在网上看别人下载个flask很麻烦,反正我的很简单,windows环境下的..._flask layout

推荐文章

热门文章

相关标签