EM算法

转自:https://snaildove.github.io/2018/10/01/9.EM_and_GEM_LiHang-Statistical-Learning-Methods/

前言

EM(期望最大)算法有很多的应用,最广泛的就是混合高斯模型、聚类、HMM等等,本质上就是一种优化算法,不断迭代,获得优值,与梯度下降、牛顿法、共轭梯度法都起到同一类的作用。

本文是对李航《统计学习方法》的第9章复习总结,主要内容如下

  1. EM(期望最大)算法证明有跳跃性的地方全部事无巨细地写出来,

  2. 三硬币例子解析 这一节将会把这个例子跟公式一一对应起来

  3. GMM(高斯混合模型)迭代公式证明

  4. F函数的极大-极大算法(Maximization-Maximization-algorithm)和GEM 详细证明

当然大家也可以参考 Stanford 吴恩达主讲的 CS299 Machine LearningEM课件 ,相比之下《统计学习方法》这本书在 Jensen‘s inequality(琴声不等式)讲的不够详细,其他都差不多,只是Q函数定义不同,这两种定义都很流行所以后文也会介绍区别

正文

9.1 EM算法的引入

概率模型有时既含有观测变量(observable variable) , 又含有隐变量(hidden variable)潜在变量(latent variable)

如果概率模型的变量都是观测变量, 那么给定数据, 可以直接用极大似然估计法或贝叶斯估计法估计模型参数。 但是, 当模型含有隐变量时, 就不能简单地使用这些估计方法。 EM算法就是含有隐变量的概率模型参数的极大似然估计法, 或极大后验概率估计法。 我们仅讨论极大似然估计, 极大后验概率估计与其类似。

9.1.1 EM算法

EM算法

这里, 随机变量 y 是观测变量, 表示一次试验观测的结果是1或0; 随机变量 z 是隐变量, 表示未观测到的掷硬币 A 的结果; θ(π,pq) 是模型参数。 这一模型是以上数据的生成模型。 注意, 随机变量 y 的数据可以观测, 随机变量 z 的数据不可观测。

P(y|θ)=zP(y,z|θ)=zP(z,θ)P(θ)P(y,z,θ)P(z,θ)=zP(z|θ)P(y|z,θ)=P(z=1|θ)P(y|z=1,θ)+P(z=0|θ)P(y|z=0,θ)(9.1)=πpy(1p)(1y)+(1π)qy(1q)(1y)={πp+(1π)q,y=1π(1p)+(1π)(1q),y=0
将观测数据表示为 Y(Y1Y2,,Yn)T, 未观测数据表示为 Z(Z1,Z2,,Zn)T, 则观测数据的似然函数为
(9.2)P(Y|θ)=ZP(Y,Z|θ)=ZP(Z|θ)P(Y|Z,θ)
即:
(9.3)P(Y|θ)=j=1n{πpyj(1p)(1yj)+(1π)qyj(1q)(1yj)}
考虑求模型参数 θ=(π,p,q) 的极大似然估计,即:
θ^=argmaxθlogP(Y|θ)=argmaxθlogj=1nP(Y|θ)n次抛硬币试验都是独立=argmaxθj=1nlogP(Y|θ)(9-3)=argmaxθj=1nlog{ZP(Z|θ)P(Y|Z,θ)}
问题:这里为什么要取对数?

  • 取对数之后累积变为累和,求导更加方便(后面三硬币例子解析将会看到)
  • 概率累积会出现数值非常小的情况,比如1e-30,由于计算机的精度是有限的,无法识别这一类数据,取对数之后,更易于计算机的识别(1e-30以10为底取对数后便得到-30)。

这个问题没有解析解,因为隐变量数据无法获得,只有通过迭代的方法求解。 EM算法就是可以用于求解这个问题的一种迭代算法。

一般地, 用 Y 表示观测随机变量的数据, Z 表示隐随机变量的数据。 YZ 连在一起称为完全数据(complete-data) , 观测数据 Y 又称为不完全数据(incomplete-data) 。 假设给定观测数据 Y, 其概率分布是 P(Y|θ), 其中是需要估计的模型参数, 那么不完全数据 Y 的似然函数是 P(Y|θ), 对数似然函数 L(θ)logP(Y|θ) ; 假设 YZ 的联合概率分布是 P(Y,Z|θ), 那么完全数据的对数似然函数是 logP(Y,Z|θ)

9.1.2 EM算法的导出

EM算法

EM算法

:书上给出琴声不等式(lnjλjyjjλjlogyj,λj0,jλj=1),自行*一下了解详情。最后一步源自于 Z 所有可能取值的概率和为1

logP(Y|θ(i))=logP(Y|θ(i))ZP(Z|Y,θ(i))
EM算法
θ(i+1)=argmaxθ{L(θ(i))+ZP(Z|Y,θ(i))logP(Y|Z,θ)P(Z|θ)P(Z|Y,θ(i))P(Y|θ(i))}=argmaxθ{logP(Y|θ(i))ZP(Z|Y,θ(i))+ZP(Z|Y,θ(i))logP(Y|Z,θ)P(Z|θ)P(Z|Y,θ(i))P(Y|θ(i))}
加号右边,利用对数函数的性质得到:
ZP(Z|Y,θ(i))logP(Y|Z,θ)P(Z|θ)P(Z|Y,θ(i))P(Y|θ(i))=ZP(Z|Y,θ(i)){log[P(Y|Z,θ)P(Z|θ)]log[P(Z|Y,θ(i))P(Y|θ(i))]}=ZP(Z|Y,θ(i)){log[P(Y|Z,θ)P(Z|θ)]logP(Z|Y,θ(i))logP(Y|θ(i))}=ZP(Z|Y,θ(i))log[P(Y|Z,θ)P(Z|θ)]ZP(Z|Y,θ(i))logP(Z|Y,θ(i))ZP(Z|Y,θ(i))logP(Y|θ(i))
代入上式可得:
θ(i+1)=argmaxθ{ZP(Z|Y,θ(i))log[P(Y|Z,θ)P(Z|θ)]ZP(Z|Y,θ(i))logP(Z|Y,θ(i))}

由于在迭代求第 i+1 步时,θ(i) 是已知的,那么由训练数据中可以求得 P(Z|Y,θ(i)) ,所以在 θ(i) 值确定的情况下,P(Z|Y,θ(i)) 的值也是确定的而不是变量,那么对上式极大化等价求解对下面式子的极大化

θ(i+1)=argmaxθ{ZP(Z|Y,θ(i))log[P(Y|Z,θ)P(Z|θ)]}=argmaxθ{ZP(Z|Y,θ(i))logP(Y,Z|θ)}(9.17)=argmaxθQ(θ,θ(i))

Q函数

EM算法

EM算法

EM算法

EM算法

EM算法

EM算法解释

EM算法

EM算法

9.1.3 EM算法在非监督学习中的应用

EM算法

9.2 EM算法的收敛性

这一部分原书讲的比较详细,不画蛇添足,贴上来。

EM算法

EM算法

EM算法

三硬币例子解析

前文讲到抛硬币的例子,现在重新详细推导一下三硬币这个例子。

EM算法

j 是训练集中的数据编号,实际上书上这里求得是

P(Z|yj,θ(i))={P(Z=1|yj,θ(i))=μj(i+1)P(Z=0|yj,θ(i))=1μj(i+1)
前文已知Q函数:
Q(θ,θ(i))=ZP(Z|Y,θ(i))logP(Y,Z|θ)

第一步求期望

即求Q函数,由本文开头的 9.1.1 EM算法 这一节的公式 (9-3) 和 Q函数得到,在多个样本情况下 Q 函数为:

Q(θ,θ(i))=j=1nZP(Z|yj,θ(i))logP(yj,Z|θ)=j=1n{P(Z=1|yj,θ(i))logP(yj,Z=1|θ)+P(Z=0|yj,θ(i))logP(yj,Z=0|θ)}=j=1n{μj(i+1)logP(yj,Z=1|θ)+(1μj(i+1))logP(yj,Z=0|θ)}=j=1n{μj(i+1)log[πpyj(1p)1yj]+(1μj(i+1))log[(1π)qyj(1q)1yj]}

第二步极大化Q函数

θ(i+1)=argmaxθQ(θ,θ(i))=argmaxθ{j=1nZP(Z|yj,θ(i))logP(yj,Z|θ)} 用微积分求解最大值,先求导数为0点(为了求导方便令对数的底数为e,即认为此处对数函数为自然对数):

Q(θ,θ(i))π=j=1N{μj(i+1)ln[πpyj(1p)1yj]+(1μj(i+1))ln[(1π)qyj(1q)1yj]π}=j=1N{μj(i+1)pyj(1p)1yjπpyj(1p)1yj+(1μj(i+1))qyj(1q)1yj(1π)qyj(1q)1yj}=j=1N{μj(i+1)ππ(1π)}=(j=1Nμj(i+1))nππ(1π)

Q(θ,θ(i))π=0π=1nj=1Nμj(i+1)π(i+1)=1nj=1Nμj(i+1)

Q(θ,θ(i))p=j=1N{μj(i+1)ln[πpyj(1p)1yj]+(1μj(i+1))ln[(1π)qyj(1q)1yj]p}=j=1N{μj(i+1)π(yjpyj1(1p)1yj+pyj(1)(1yj)(1p)1yj1)πpyj(1p)1yj+0}=j=1N{μj(i+1)(yjp)p(1p)}=(j=1Nμj(i+1)yj)(pj=1Nμj(i+1))p(1p)

Q(θ,θ(i))p=0p=j=1Nμj(i+1)yjj=1Nμj(i+1)p(i+1)=j=1Nμj(i+1)yjj=1Nμj(i+1)q(i+1)=j=1N(1μj(i+1))yjj=1N(1μj(i+1))
可以参照书上的结果,一模一样:

EM算法

EM算法

CS299 EM算法与《统计学习方法》的表述不同点

  1. 《统计学习方法》这部分术语源自于鼎鼎大名的ESL 全称:The Elements of Statistical Learning,这也是Stanford统计经典巨作。

    EM算法

  2. Stanford 吴恩达主讲的 CS299 Machine LearningEM课件

    EM算法

    由本文的推导,易得 ESL 中的 QESL=QCS299logP(X,Z;θ)QCS299

9.3 EM算法在高斯混合模型学习中的应用

EM算法的一个重要应用是高斯混合模型的参数估计。 高斯混合模型应用广泛, 在许多情况下, EM算法是学习高斯混合模型(Gaussian misture model) 的有效方法。

9.3.1 高斯混合模型

EM算法

9.3.2 高斯混合模型参数估计的EM算法

EM算法

EM算法

EM算法

注意:上面的极大化的求混合模型参数迭代公式的过程参考: 大牛JerryLead(EM算法)The EM Algorithm

EM算法

与K-means比较

相同点:都是可用于聚类的算法;都需要指定K值。

不同点:GMM可以给出一个样本属于某类的概率是多少。

9.4 EM算法的推广

EM算法还可以解释为F函数(F function) 的极大-极大算法(maximization maximization algorithm) , 基于这个解释有若干变形与推广, 如广义期望极大(generalized expectation maximization,GEM) 算法。

注:原文引理(9.1)(9.2)的证明有坑需要注意,先看原文,后面列出详细过程

9.4.1 F函数的极大-极大算法

EM算法

熵这块,不清楚的可以回顾一下我的另一篇总结:《机器学习中的信息论基础》

引理9.1需要更详细说明:

L=Ep~logP(Y,Z|θ)Ep~logP~(Z)+λ{1ZP~(Z)}
证明过程思路:拉格朗日求有约束的极大值。需要注意,由累加号和均值可以看出这里的 Z 是指 Zi,i 这里是 Z 的离散值的标号 ,因此需要重写公式 (9.35) 比较清楚:
L=ZiP~(Zi)logP(Y,Zi|θ)ZiP~(Zi)logP~(Zi)+λ{1ZiP~(Zi)}
所以这里其实是 L 关于 P(Zi)的求导(这里作者求导的时候把对数函数默认当做自然对数):
LP~(Zi)=logP(Y,Zi|θ)logP~(Zi)1λLP~(Zi)=0λ=logP(Y,Zi|θ)logP~(Zi)1
上式两端同取对数:
λ+1=logP(Y,Zi|θ)logP~(Zi)eλ+1=P(Y,Zi|θ)P~(Zi)(9-1)P~(Zi)=P(Y,Zi|θ)eλ+1
由离散变量的概率和为1,得到:
Zieλ+1=ZiP(Y,Zi|θ)ZiP~(Zi)(9-2)eλ+1=P(Y|θ)
将 (9-2) 代入 (9-1)​ 式,得到
P~(Zi)=P(Y,Zi|θ)P(Y|θ)=P(Y,Zi,θ)p(θ)P(θ)P(Y,θ)=P(Zi|Y,θ)
这里前提条件是 θ 是固定情况下的推导过程,所以原文给上式标记出了 θ ,又因为每个 Zi 都符合这个式子,那么可重写上式:
P~θ(Z)=P(Z|Y,θ)
这样引理9.1证明完毕。

EM算法

引理9.2如下

由公式 (9.33)(9.34) :

F(P~,θ)=Ep~[logP(Y,Z|θ)]+H(P~)P~θ(Z)=P(Z|Y,θ)
得到:
F(P~,θ)=ZP~θ(Z)logP(Y,Z|θ)ZP~θ(Z)logP~θ(Z)=ZP(Z|Y,θ)logP(Y,Z|θ)ZP(Z|Y,θ)logP(Z|Y,θ)=ZP(Z|Y,θ)[logP(Y,Z|θ)logP(Z|Y,θ)]=ZP(Z|Y,θ)logP(Y,Z|θ)P(Z|Y,θ)=ZP(Z|Y,θ)log{P(Y,Z,θ)p(θ)P(Y,θ)P(Y,Z,θ)}=ZP(Z|Y,θ)logP(Y|θ)=logP(Y|θ)
引理9.2证明完毕

EM算法

EM算法

9.4.2 GEM算法

EM算法

本章概要

EM算法

引用

  1. The Expectation Maximization Algorithm: A short tutorial - Sean Borman

  2. 李航《统计学习方法》

  3. 大牛JerryLead(EM算法)The EM Algorithm

  4. 人人都懂EM算法

  5. EM算法简述及简单示例(三硬币模型)

</div>
上一篇:Java学习第九章 之 接口,多态


下一篇:Java学习之多态---类成员变化