大数据经典算法解析（5）一EM算法

姓名：崔升    学号：14020120005

创新互联建站是一家朝气蓬勃的网站建设公司。公司专注于为企业提供信息化建设解决方案。从事网站开发，网站制作，网站设计，网站模板，微信公众号开发，软件开发，小程序设计，十载建站对轻质隔墙板等多个行业，拥有多年的网站设计经验。

【嵌牛导读】：

EM作为一种经典的处理大数据的算法，是我们在学习互联网大数据时不得不去了解的一种常用算法

【嵌牛鼻子】：经典大数据算法之EM简单介绍

【嵌牛提问】：EM是一种怎么的算法，其如何去观测其中隐变量的？

【嵌牛正文】：

1. 极大似然

极大似然（Maximum Likelihood）估计为用于已知模型的参数估计的统计学方法。比如，我们想了解抛硬币是正面（head）的概率分布θθ；那么可以通过最大似然估计方法求得。假如我们抛硬币1010次，其中88次正面、22次反面；极大似然估计参数θθ值：

θ^=argmaxθl(θ)=argmaxθθ8(1−θ)2θ^=arg⁡maxθl(θ)=arg⁡maxθθ8(1−θ)2

其中，l(θ)l(θ)为观测变量序列的似然函数（likelihood function of the observation sequence）。对l(θ)l(θ)求偏导

∂l(θ)∂θ=θ7(1−θ)(8−10θ)⇒θ^=0.8∂l(θ)∂θ=θ7(1−θ)(8−10θ)⇒θ^=0.8

因为似然函数l(θ)l(θ)不是凹函数（concave），求解极大值困难。一般地，使用与之具有相同单调性的log-likelihood，如图所示

凹函数（concave）与凸函数（convex）的定义如图所示：

从图中可以看出，凹函数“容易”求解极大值，凸函数“容易”求解极小值。

2. EM算法

EM算法（Expectation Maximization）是在含有隐变量（latent variable）的模型下计算最大似然的一种算法。所谓隐变量，是指我们没有办法观测到的变量。比如，有两枚硬币A、B，每一次随机取一枚进行抛掷，我们只能观测到硬币的正面与反面，而不能观测到每一次取的硬币是否为A；则称每一次的选择抛掷硬币为隐变量。

用Y表示观测数据，Z表示隐变量；Y和Z连在一起称为完全数据( complete-data )，观测数据Y又称为不完全数据(incomplete-data)。观测数据的似然函数：

P(Y|θ)=∑ZP(Z|θ)P(Y|Z,θ)P(Y|θ)=∑ZP(Z|θ)P(Y|Z,θ)

求模型参数的极大似然估计：

θ^=argmaxθlogP(Y|θ)θ^=arg⁡maxθlog⁡P(Y|θ)

因为含有隐变量，此问题无法求解。因此，Dempster等人提出EM算法用于迭代求解近似解。EM算法比较简单，分为两个步骤：

E步（E-step），以当前参数θ(i)θ(i)计算ZZ的期望值

Q(θ,θ(i))=EZ[logP(Y,X|θ)|Y,θ(i)]Q(θ,θ(i))=EZ[log⁡P(Y,X|θ)|Y,θ(i)]

M步（M-step），求使Q(θ,θ(i))Q(θ,θ(i))极大化的θθ，确定第i+1i+1次迭代的参数的估计值θ(i+1)θ(i+1)

θ(i+1)=argmaxθQ(θ,θ(i))θ(i+1)=arg⁡maxθQ(θ,θ(i))

如此迭代直至算法收敛。关于算法的推导及收敛性证明，可参看李航的《统计学习方法》及Andrew Ng的《CS229 Lecture notes》。 这里 有一些极大似然以及EM算法的生动例子。

3. 实例

[2]中给出极大似然与EM算法的实例。如图所示，有两枚硬币A、B，每一个实验随机取一枚抛掷10次，共5个实验，我们 可以 观测到每一次所取的硬币，估计参数A、B为正面的概率θ=(θA,θB)θ=(θA,θB)，根据极大似然估计求解

如果我们 不能 观测到每一次所取的硬币，只能用EM算法估计模型参数，算法流程如图所示：

隐变量ZZ为每次实验中选择A或B的概率，则第一个实验选择A的概率为

P(z1=A|y1,θ(0))=P(z1=A|y1,θ(0))P(z1=A|y1,θ(0))+P(z1=B|y1,θ(0))=0.65∗0.450.65∗0.45+0.510=0.45P(z1=A|y1,θ(0))=P(z1=A|y1,θ(0))P(z1=A|y1,θ(0))+P(z1=B|y1,θ(0))=0.65∗0.450.65∗0.45+0.510=0.45

按照上面的计算方法可依次求出隐变量ZZ，然后计算极大化的θ(i)θ(i)。经过10次迭代，最终收敛。

4. 参考资料

[1] 李航，《统计学习方法》.

[2] Chuong B Do Serafim Batzoglou, What is the expectation maximization algorithm?

[3] Pieter Abbeel, Maximum Likelihood (ML), Expectation Maximization (EM) .

[4] Rudan Chen, 【机器学习算法系列之一】EM算法实例分析 .

数据挖掘十大经典算法之EM

EM（Expectation-Maximum）算法也称期望最大化算法，它是最常见的隐变量估计方法，在机器学习中有极为广泛的用途，例如常被用来学习高斯混合模型（Gaussian mixture model，简称GMM）的参数；隐式马尔科夫算法（HMM）、LDA主题模型的变分推断等等。

EM算法是一种迭代优化策略，由于它的计算方法中每一次迭代都分两步，其中一个为期望步（E步），另一个为极大步（M步），一轮轮迭代更新隐含数据和模型分布参数，直到收敛，即得到我们需要的模型参数。

1. EM算法推导过程

补充知识：Jensen不等式：

如果f是凸函数，函数的期望 大于等于 期望的函数。当且仅当下式中X是常量时，该式取等号。（应用于凹函数时，不等号方向相反）

2. EM算法流程

3. EM算法的其他问题

上面介绍的传统EM算法对初始值敏感，聚类结果随不同的初始值而波动较大。总的来说，EM算法收敛的优劣很大程度上取决于其初始参数。

EM算法可以保证收敛到一个稳定点，即EM算法是一定收敛的。

EM算法可以保证收敛到一个稳定点，但是却不能保证收敛到全局的极大值点，因此它是局部最优的算法，当然，如果我们的优化目标是凸的，则EM算法可以保证收敛到全局最大值，这点和梯度下降法这样的迭代算法相同。

EM算法的简单实例：

参考：

EM算法详解

作为N大机器学习方法的一员，EM算法在各种书籍、博客、网上视频上被描述或者介绍，每次看完总感觉很多地方含糊不清，不能让一个初学者（有一定统计概率基础）接受。最近再B站上，看到 徐亦达老师的课程 ，EM算法这块讲解易于理解和接受，再结合PRML一书的关于混合模型和EM章节内容，对整个EM算法从具体的原理上面有了更深入的理解。

在下文中，更多的是通过公式推导和一些文字说明来梳理EM算法，尽量做到大家一看就明白。

极大似然估计是概率统计中，估计模型参数的一种方法，如果对似然概念以及极大似然估计的概念不理解，可参考维基百科

这里，我们给出一个一维高斯函数的例子。如图1所示，一维空间里面离散分布的样本点其分布特点可以看成是一种高斯分布。那这些样本的高斯分布函数参数怎么求解呢？可以通过极大似然估计获得。

假设我们获取图1中数据样本集合为 ，其分布函数假设为一维高斯分布，即：

那所有数据的联合概率,即似然函数为：

对等式两边求log，即log-likelihood：

分别对参数求导：

可以得到：

通过上述方法，就可以得到基于样本数据和假设分布函数模型情况下，得到样本数据的分布函数。

从图2所示中，如果样本数据分布式蓝色点和橙色点的集合，如果依然用高斯分布去进行最大似然估计，得到的分布模型自然是不合适的。很显然，样本数据分布存在两个密集区（蓝色点和橙色点），如果能通过一种方法，确认样本数据里面的蓝色点和橙色点，然后分别对蓝色点集合进行一个高斯估计，对橙色点集进行另外一个高斯估计，两个高斯混合到一起，是不是比单个高斯能更好的匹配样本数据的分布情况。这种情况下的分布函数就是高斯混合模型。

这里我们先直接给出高斯混合模型的分布函数(多维)：

在图2例子中，提到如果给每一个数据样本能够先进行分类，即确定属于哪一个集中的簇中，就能比较容易的进行混合模型的求解。这说明了什么呢？我们可以理解，原始样本数据是不完全的（incomplete），引入一个K维的二值随机变量 ，这个变量采用"1-of-K"的表示方法，即K维中，只有一维是1，其余所有元素等于0。那么每一个样本数据，即有数据特征 ，再匹配一个分配变量 ，就可以将图2过程完整描述，即我们认为 和 联合在一起才是完全的（complete）。

数学表示上，我们利用边缘概率分布 和条件概率分布 定义联合概率分布 .

的边缘概率分布根据混合系数 进行赋值，即 ,使得边缘概率分布是合法，那么：

类似的，在给定 的一个特定的值，即针对某一簇的情况， 的条件概率分布是一个高斯分布，即

那么根据贝叶斯公式得到高斯混合模型：

由于我们只能观察样本数据 ,无法直接获取每个数据的分配变量 ,可理解 为潜在变量（latent）

依据极大似然函数的求解方法，我们可以对高斯混合模型写出数据的对数似然函数：

由于对数函数内部出现求和，这种情况是没有办法通过求导等于0的方式获取估计参数的解析解的。这种情况下，就需要用到EM算法，通过迭代方式获取估计参数。下面我们先从一般性问题上进行EM算法的理论描述，然后再利用EM算法推导高斯混合模型的计算方法。

EM算法叫做期望最大化方法，首先我们给出EM算法一般性结论或者说步骤，其具体分为两步，即E-step和M-step。

EM算法的步骤，通过高斯混合模型可以直观理解记忆。 是什么意思呢，其含义是在给定数据样本的情况下，潜在变量的概率情况。也就是说在高斯混合模型中，给定样本数据，我们推测样本属于哪一个高斯簇的概率情况。在确定分配情况后，每一个簇都用高斯进行估计，衡量估计好还是不好，用期望形式表示。这样可以帮助理解和记忆Q的定义。那EM算法怎么证明其收敛性呢？

我们要保证：

这样每次迭代可以使得似然函数随着参数变大，一直到似然函数不再增大或满足其他终止条件止。

那怎么保证呢？首先，利用贝叶斯公式有：

两边同时取log

然后两边同时用 求期望，可以得：

等式左边 和 没有关系， 是概率密度函数，积分是1，所以等式左边依然是 .

等式右边第一项就是E-step里面的Q函数，第二项我们记做H函数，则：

要保证 ，首先 ，那么是不是保证 满足，就一定有 ？答案是肯定的。（说明一下，这里面的H和Q函数都是关于 的函数，每一次迭代 是已知的，他不是变量）

那下面只要证明 就可以了。

因此可以得到 ，则整个EM算法的收敛性证毕。

注：这里用到了Jessian不等式，如果函数是convex的，则有函数的期望大于期望的函数，即 .

上述EM算法的证明，有一些技巧性，而这些技巧性有没有一种是在已知结论基础上硬凑的感觉呢，尤其是用 去求期望，就是为了去构造Q函数。那有没有更好的解释或者更为直观的方式来得到相同的结论呢？答案是有的。

首先，仍然用到：

我们稍微变个型，假设一个概率密度函数 :

两边同时用 求期望：

其中等式右边第一项，我们记做 ，可以称为ELOB，EvidenceLowerBound，第二项是 和 的KL散度。

如图4所示，当我固定参数 时候，ELOB就是关于 的泛函（只听过没学过，可理解为函数的函数），那ELOB的上界是什么呢？那首先要理解KL散度，KL散度是衡量两个概率分布之间的差异性，如果两个分布没有差异，则KL散度等于0，如果有差异则大于0，所以KL散度的最小值就是0，那ELOB的上界就是此刻的似然函数。

在EM算法中，当前迭代时，参数 ，则对于E-step，我们需要使得ELOB最大，即KL散度为0，如图5所示，其中 为 。此时，

对于M-Step，我们是需要得到新的估计参数，这个时候，固定 ,重新获得ELOB的最大值，这个时候的ELOB是什么样的呢？

右边第二项没有参数 ，所以固定 最大化ELOB，就等于最大化第一项，而第一项是什么呢？就是 函数。

如图6所示，我们最大化 函数，也就是最大化此次迭代的ELOB。在新的参数下， ，此刻 不变，所以和新的 在没有达到局部（或者全局）极大值的情况下，是两个不同的概率分布，即二者KL散度是大于0的，那此刻的似然函数等于此刻的KL散度加上此刻的ELOB，自然是有 。

从ELOB和KL散度的层面可以更好的理解EM算法的迭代过程。

PRML一书中，有图7所示的示意图，能比较形象的说明，EM算法的迭代过程。

图7中，红色曲线表示(不完整数据)对数似然函数，它的最大值是我们想要得到的。我们首先选择某个初始的参数值 ,然后在第一个E步骤中,我们计算潜在变量上的后验概率分布,得到了 的一个更小的下界，它的值等于在 处的对数似然函数值，用蓝色曲线表示。注意，下界与对数似然函数在 处以切线的方式连接，因此两条曲线的梯度相同。这个界是一个凹函数，对于指数族分布的混合分布来说，有唯一的最大值。在M步骤中,下界被最大化，得到了新的值 ,这个值给出了比 处更大的对数似然函数值。接下来的E步骤构建了一个新的下界,它在 处与对数似然函数切线连接,用绿色曲线表示。以这样的方式不停迭代，直到满足条件。

了解了EM算法，我们来详细推导高斯混合模型的E步和M步的内容。这一部分内容来自徐亦达老师的课件。由于公式太多了，我就放一些截图，供大家一起学习和参考。

徐亦达老师的课件在：

后续关于EM算法的应用会举例以下几方面内容

(1)Kmeans和高斯混合模型

(2)EM算法应用之贝叶斯线性回归

(3)EM算法应用之PLSA

(4)EM算法应用之缺失数据参数估计问题

EM算法深度解析

最近在做文本挖掘的时候遇到了EM算法，虽然读书的时候简单地接触过，但当时并没有深入地去了解，导致现在只记得算法的名字。既然EM算法被列为数据挖掘的十大算法之一，正好借这个机会，重新学习一下这个经典的算法。学习的过程中，我发现网上的资料大多讲解地不够细致，很多地方解释得并不明了。因此我决定抛开别人的想法，仅从数学推导本身出发，尽力理解每一个公式的含义，并将其对应到实际的实验过程当中。这篇博客记录了我对与EM算法的思考与理解，也是我人生中的第一篇博客，希望能够对于想要学习EM算法的同学有所帮助。

前面谈到我在做文本挖掘的时候遇到了EM算法，EM算法用于估计模型中的参数。提到参数估计，最常见的方法莫过于极大似然估计——在所有的候选参数中，我们选择的参数应该让样本出现的概率最大。相信看到这篇笔记的同学一定对极大似然估计非常熟悉，而EM算法可以看作是极大似然估计的一个扩充，这里就让我们用极大似然估计来解决一个简单的例子，来开始正式的讨论。

有A，B，C三枚硬币，我们想要估计A，B，C三枚硬币抛出正面的概率 , , 。我们按如下流程进行实验100次：

记录100次实验的结果如下：

我们将上面的实验结果表述如下：

表示第i次实验中，硬币A的结果，1代表正面，0代表反面； 表示第i次实验中，硬币B或硬币C抛出正面的个数，则参数 的极大似然估计分别为：

即硬币A，B，C各自抛出正面的次数占总次数的比例，其中 为指示函数。

实验流程与1相同，但是我们不慎遗失了硬币A的记录结果，导致我们只知道随后十次抛出了多少次正面，多少次反面，却不知道实验结果来自于硬币B还是硬币C。在这种情况下，我们是否还能估计出 , , 的值呢？

这时候利用极大似然估计似乎行不通了， 因为这种情况下，我们不但缺失了硬币A产生的观测值，同时也不知道哪些观测值属于硬币B，哪些观测值属于硬币C。

有些同学可能会提出，虽然我们无法得到三个硬币各自产生的样本，但是我们依然可以得到每个观测值出现的概率。比如在第一次实验中， 我们抛出了5次正面5次反面，我们可以做如下思考：

  假设这5次正面由硬币B得到，那么概率应该为 ，而这次观测值来自于硬币B，也就是硬币A抛出正面的概率为

  假设这5次正面由硬币C得到，那么概率应该为 ，而这次观测值来自于硬币C，也就是硬币A抛出反面的概率为

  综合起来，利用条件概率公式，这个观测值出现的概率就是

因此我们可以将样本整体的概率和似然函数利用 , , 表示出来，通过对似然函数求导，令其关于 的偏导数等于0，我们可以求出三个参数的值。

这个思路听上去十分合理，我们可以顺着这个思路进行数学推导，看看可以得到什么样的结果。首先我们计算样本的概率:

对应的似然函数为

其中 关于 的条件分布为

的分布为

因此我们可以得到

至此，我们成功地得到了似然函数。然而观察可以发现，这个函数是由100项对数函数相加组成，每个对数函数内部包含一个求和，想通过求导并解出导数的零点几乎是不可能的。当然我们可以通过梯度下降来极小化这个函数，借助深度学习库的自动微分系统在实现上也非常容易。但是这种做法过于简单粗暴，有没有办法来优雅地解决这个问题呢？在继续讨论之前，我们先将这类问题进行一般化表述：

我们观测到随机变量 产生的m个相互独立的样本 , 的分布由联合分布 决定， 是缺失数据或无法在实验中被直接观测到，称为 隐变量 ，我们想要从样本中估计出模型参数 的值。在接下来的讨论中，我们假定 的取值是离散的，于是可以得到似然函数如下:

接下来，我们就探讨一下，如何利用EM算法解决这个问题。

这一部分的数学推导，主要参考了吴恩达CS229n的笔记，并且根据个人的思考和理解，尽力对公式的每一步进行详细的解释。我们先简单地介绍一下琴生不等式。

琴生不等式有多种形式，下面给出其离散形式的表述和概率论中的表述:

1.若 为严格凹函数， 为定义域内的n个点， 是n个正实数，且满足 , 则下述不等式成立:

当且仅当 时，不等式取等号。

2.若 为严格凹函数， 为实值随机变量，且期望存在，则下述不等式成立:

当且仅当 ，即 为常数时，不等式取等号。

注： 这里将函数上方为凹集的函数称为凹函数， 例如 函数就是凹函数。

相信大家对琴生不等式都十分熟悉，因此这里就不做过多的说明。接下来，我们将琴生不等式应用到我们的问题中。

回到我们之前的问题上， 我们想要极大化下面这个函数:

但是我们无法对这个函数直接求导，因此我们借助琴生不等式，对这个函数进行变换。为了让过程看上去简洁，下面只对求和中的第 项进行计算。

令 满足 ，且 ，则根据琴生不等式，可以得到：

当且仅当 为常数时，上述不等式取等号。也就是说，对于任意 ， 是一个与 无关的量。设对于任意 ，我们可以得到：

因此当 时，不等式 取等号，容易验证此时 , 与 无关。将 综合一下，我们可以得到以下结论:

到这里为止，我们已经拥有了推导出EM算法的全部数学基础，基于 我们可以构建出E步和M步。上面的数学推导虽然看上去略为复杂，但实际上只用到了三个知识点：

  1.琴生不等式:

  2.条件概率:

  3.联合分布求和等于边缘分布:

对上面的数学推导有疑问的同学，可以结合上面这三点，再将整个推导过程耐心地看一遍。

大部分关于EM算法的资料，只是在数学形式上引入了 函数，即 ，以满足琴生不等式的使用条件，却没有过多地解释 函数本身。这导致了很多人完全看懂了算法的推导，却还是不理解这些数学公式究竟在做什么，甚至不明白EM算法为什么叫做EM算法。所以在给出E步和M步之前，我想先谈一谈 函数。

我们回顾一下 函数所满足的条件（暂时不考虑琴生不等式取等号的限制），

在 所有可能的取值处有定义。可以看出， 是 的样本空间上任意的一个概率分布。因此，我们可以对不等式 进行改写。首先我们可以将含有 的求和写成期望的形式:

这里 指的是在概率分布 下，求随机变量 和 的期望。有同学会问，为什么我们平时求期望的时候只要写 ，并没有指明是在哪个概率分布下的期望。这是因为一般情况下，我们都清楚地知道随机变量 所服从的分布 ，并且默认在分布 下求期望。

举个例子，我手上有一个硬币，抛了10次，问抛出正面次数的期望。这种情况下，大部分人会默认硬币是均匀的，也就是说抛出正面的次数 服从二项分布 ，期望 。这时有人提出了质疑，他说我认为你这个硬币有问题，抛出正面的概率只有0.3，那么在他眼里， 期望 。

回到正题，我们利用等式 改写不等式 ，可以得到:

这正是琴生不等式在概率论中的形式。我们可以将不等式倒过来理解：

  首先，假定随机变量 服从概率分布 ， 是 的样本空间上的任意一个概率分布。这里 可以是一组定值，也可以是关于参数 的函数。

  显然，当我们取不同的 时，随机变量 的期望也会随之改变。需要注意的是，由于 与 相关，所以这里的期望不是一个数值，而是关于 的函数。

  当我们令 为 的后验分布 时，上面的期望最大。这里有两点需要注意，1. 后验分布 也是一个关于参数 的函数。2. 由于期望是关于 的函数，所以这里的最大指的并非是最大值，而是最大的函数。

  若对于每一个 ，我们都令 为 的后验分布 ，则上述期望之和等于我们要极大化的似然函数，即

通过上述分析，我们为寻找似然函数的极大值点 提供了一个思路。我们不去极大化似然函数本身，而是去极大化 。至于如何将这个思路实际应用，就要利用到EM算法中的E-step和M-step。

这一节中，我们先给出E-step和M-step的数学形式，随后在结合抛硬币的例子来解释这两步究竟在做什么。下面进入算法的流程，首先我们任意初始化 ，按下述过程进行迭代直至收敛：

在第 次迭代中，

(E-step)对于每个 ，令

(M-step)更新 的估计值，令

EM算法从任意一点 出发，依次利用E-step优化 ，M-step优化 ，重复上述过程从而逐渐逼近极大值点。而这个过程究竟是怎样的呢，就让我们一步步地揭开EM算法的面纱。

假设我们现在随机初始化了 ，进入第一轮迭代：

(E-step)

由于我们已经假定模型参数为 ，所以此时 不再是与 有关的函数，而是由一组常数构成的概率分布。结合抛硬币的例子来看，这一步是在我们已知模型参数 的基础上(虽然这是我们瞎猜的)，去推测每一次的观测值是由哪个硬币产生的，或者说我们对每一次观测值做一个软分类。比如我们根据初始化的参数，计算出 ， 。可以解释为第 个观测值有20%的概率来自于硬币B，80%的概率来自于硬币C；或者说硬币A抛出了0.2个正面，0.8个反面。

(M-step)

考虑到 是一组常数，我们可以舍弃常数项，进一步简化上面这个要极大化的函数

由于 不再与 相关，因此上面的函数变成了对数函数求和的形式，这个函数通常来说是容易求导的，令导数等于0，我们可以求出新的参数 。我们仍旧以抛硬币为例进行解释，

令 , 可以得到，

这三个参数的解释是显而易见的。我们在E-step中对每个观测值进行了软分类， 可以看成是硬币A抛出正面的次数，所以 是 的极大似然估计； 是我们抛硬币B的次数， 是硬币B抛出正面的次数，所以 是 的极大似然估计；对于 我们有相同的解释。

我们将这个结果与抛硬币1中极大似然估计的结果相比较可以发现，之前结果中的指示函数 变成了这里的 ，在指示函数下，某个观测值要么来自于硬币B，要么来自于硬币C，因此也称为硬分类。而在 函数下，某个观测值可以一部分来自于硬币B，一部分来自于硬币C，因此也称作软分类。

将上述两步综合起来，EM算法可以总结如下：我们首先初始化模型的参数，我们基于这个参数对每一个隐变量进行分类，此时相当于我们观测到了隐变量。有了隐变量的观测值之后，原来含有隐变量的模型变成了不含隐变量的模型，因此我们可以直接使用极大似然估计来更新模型的参数，再基于新的参数开始新一轮的迭代，直到参数收敛。接来下我们就讨论为什么参数一定会收敛。

前面写了太多的公式，但是这一部分我不打算给出收敛性的数学推导。其实数学上证明EM算法的收敛性很容易，只需要证明每一轮迭代之后，参数的似然函数递增，即

名称栏目：em函数python popitem函数
URL地址：http://azwzsj.com/article/hhgeei.html