FPEM算法

⑴ 大数据经典算法解析（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算法的简单实例： https://zhuanlan.hu.com/p/40991784

参考：

https://zhuanlan.hu.com/p/40991784

https://blog.csdn.net/u011067360/article/details/24368085

⑶ （十）EM算法

 EM算法的英文全称是 Expectation Maximization Algorithm——期望极大化算法 ，它采用迭代的方式逼近带隐变量的似然函数。通过对似然函数的一个下界求偏导，得到每一步参数估计的过程。
 这个名称由于缺乏作用对象，让人一头雾水。这里的期望是什么？为什么我们要极大化这个期望，我们试图优化什么？
 这里的期望的含义其实是针对 极大似然估计 中的 似然函数 来说的，这里的期望就是似然函数的一个 下界 ，我们的目的是求这样一个期望: 这个下界是根据 詹森不等式(Jensen's inequality） 放缩得到的，为什么要放缩呢？因为我们试图找出一个下界，极大化这个带参数的下界之后，可以无限近似于似然函数。你想，如果这个做法ok的话，意味着什么？意味着我们可以通过这个过程找出极大似然估计或最大后验估计的参数近似解。这也意味着我们可以搞一个迭代法来得到一个近似解。但是即便我说的天花乱坠，这个下界要是不收敛那也白搭。而下界要收敛必须满足两个条件：
 1.这个下界的取值要单调递增（因为每回迭代的结果要比上一次的取值更大）
 2.这个下界必须有上界(这个上界就是对数似然函数，且这一点可以由詹森不等式保证，这个也是EM的核心)
大白话就是 单调有界必有极限 。

我们来证明一下它确实是收敛的。
 首先，在极大似然估计中，我们的目的是根据手头上的 个样本，最大化 后，将参数 估计出来；引入对数： ;此时引入辅助变量 ;我们的对数似然函数就变成了：

设置变分函数： ;那么：

根据琴生不等式,对数函数为凸函数(因为 ：等号在 为常数时取到)：

上面的这个下界，就是用来逼近原对数似然函数的，这里我们已经证明了算法收敛的一个条件， 有界性 ；但是在继续进行下一步的时候，我们还有一个问题没搞清楚，那就是变分函数 的具体形式,实际上，我们可以通过琴生不等式等号成立的条件导出我们要的这个变分函数q。
令 为常数：
接着我们代入变分函数 的形式，定义这个下界的第一项：

定义下界的第二项：

对于第二项，我们看看随着迭代步数的增大，它是否是递增的，

我们将不同参数的 与 看作是两个分布，那么这个结果实际上是一个KL散度，它表征两个分布的相似度,其结果总是大于等于0的。
大于等于0的原因：

所以：

H为一个递增的序列，那么剩下的就是Q是否递增了，基于前面提到的这个下界是有上界的，上界就是我们的对数似然函数。在这个前提下，现在我们只要证明，Q递增是整个下界递增的充分必要条件即可。
必要性：

当整个下界递增，即：
那么：
所以 单调递增，必要性得证。
充分性：
因为：
前面已经证明：

又因为：

所以：

即，在 递增的情况下，整个下界递增。
充分性得证。
证毕。

 这个算法名称里提及的期望究竟是什么？
我们说了这么多，实际都是要做一件事，那就是：

由于前面证明过整个下界有界。且只要找到让第i次迭代的Q函数最大的 作为下一次迭代的参数，我们就可以让Q递增，让算法收敛。
我们来看看Q的形式。

这就是为什么叫期望最大算法的原因。

 我们以概率PCA，来展开EM的应用：
 当然这里的应用只涉及变分函数已知情况下的应用，并不涉及广义EM的内容，日后看完文献在来唠唠广义EM，AVE，GAN等内容。
 我们先来算一下PPCA的EM期望的形式：

在 概率PCA 中，我们有提到：


所以：


所以期望里面是这个式子：

我们的目的是要估计出 和 ;那么我们分别对它们求偏导:

所以：


因为：

代入偏导中

所以：

我们偏导得到的结果就是：

我们会发现我们还有两个估计量没解决，一个是一阶估计量 ,另一个是二阶估计量
在概率PCA中，我们提到过：

那么我们就有了一阶估计量：

二阶估计量可以通过简单的计算得到：

剩下的代入即可.

结果展示：

⑷ em算法为什么可以解决隐含数据问题

EM算法可以看成是特殊情况下计算极大似然的一种算法。
现实的数据经常有一些比较奇怪的问题，比如缺失数据、含有隐变量等问题。当这些问题出现的时候，计算极大似然函数通常是比较困难的，而EM算法可以解决这个问题。
EM算法已经有很多应用，比如最经典的Hidden Markov模型等。

⑸ em算法是什么

最大期望算法（Expectation-Maximization algorithm, EM），或Dempster-Laird-Rubin算法，是一类通过迭代进行极大似然估计（Maximum Likelihood Estimation, MLE）的优化算法 ，通常作为牛顿迭代法（Newton-Raphson method）的替代用于对包含隐变量（latent variable）或缺失数据（incomplete-data）的概率模型进行参数估计。
EM算法的标准计算框架由E步（Expectation-step）和M步（Maximization step）交替组成，算法的收敛性可以确保迭代至少逼近局部极大值 。EM算法是MM算法（Minorize-Maximization algorithm）的特例之一，有多个改进版本，包括使用了贝叶斯推断的EM算法、EM梯度算法、广义EM算法等 。
由于迭代规则容易实现并可以灵活考虑隐变量，EM算法被广泛应用于处理数据的缺测值 ，以及很多机器学习（machine learning）算法，包括高斯混合模型（Gaussian Mixture Model, GMM） 和隐马尔可夫模型（Hidden Markov Model, HMM） 的参数估计。

⑹ 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算法并且举个例子

在统计计算中，最大期望（EM）算法是在概率（probabilistic）模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variable）。最大期望经常用在机器学习和计算机视觉的数据聚类（Data Clustering）领域。

最大期望算法经过两个步骤交替进行计算：

第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；

第二步是最大化（M），最大化在 E 步上求得的最大似然值来计算参数的值。

M 步上找到的参数估计值被用于下一个 E 步计算中，这个过程不断交替进行。

总体来说，EM的算法流程如下：

1. 初始化分布参数

2. 2.重复直到收敛：

3. E步骤：估计未知参数的期望值，给出当前的参数估计。

4. M步骤：重新估计分布参数，以使得数据的似然性最大，给出未知变量的期望估计。