EM估计算法

1. em算法的EM算法

在统计计算中，最大期望（EM）算法是在概率（probabilistic）模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variable）。最大期望经常用在机器学习和计算机视觉的数据聚类（Data Clustering）领域。
最大期望算法经过两个步骤交替进行计算：
第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；
第二步是最大化（M），最大化在 E 步上求得的最大似然值来计算参数的值。
M 步上找到的参数估计值被用于下一个 E 步计算中，这个过程不断交替进行。
总体来说，EM的算法流程如下：
1.初始化分布参数
2.重复直到收敛：
E步骤：估计未知参数的期望值，给出当前的参数估计。
M步骤：重新估计分布参数，以使得数据的似然性最大，给出未知变量的期望估计。

2. 高斯混合模型(GMM)和EM算法

学号：20021110074     电院    姓名：梁雪玲

【嵌牛导读】：GMM与EM算法的学习与推导。

【嵌牛鼻子】：GMM    EM  

【嵌牛提问】：GMM是什么？EM算法是什么？二者之间的关系？算法的推导？如何深入学习？

【嵌牛正文】：

在深度学习的路上，从头开始了解一下各项技术。本人是DL小白，连续记录我自己看的一些东西，大家可以互相交流。

本文参考：

http://www.ituring.com.cn/article/497545(GMM)

https://blog.csdn.net/xmu_jupiter/article/details/50889023(GMM)

http://www.cnblogs.com/wjy-lulu/p/7010258.html(EM算法)

https://blog.csdn.net/zouxy09/article/details/8537620(EM算法)

一、前言

    高斯混合模型(Gaussian Mixture Model)简称GMM，是一种业界广泛使用的聚类算法。它是多个高斯分布函数的线性组合，理论上GMM可以拟合出任意类型的分布，通常用于解决同一集合下的数据包含多种不同的分布的情况。高斯混合模型使用了期望最大(Expectation Maximization， 简称EM)算法进行训练，故此我们在了解GMM之后，也需要了解如何通过EM算法训练(求解)GMM。

二、高斯混合模型(GMM)

    在了解高斯混合模型之前，我们先了解一下这种模型的具体参数模型-高斯分布。高斯分布又称正态分布，是一种在自然界中大量存在的，最为常见的分布形式。

    如上图，这是一个关于身高的生态分布曲线，关于175-180对称，中间高两边低，相信大家在高中已经很了解了，这里就不再阐述。

    现在，我们引用《统计学习方法》-李航 书中的定义，如下图：

    根据定义，我们可以理解为，GMM是多个高斯分布的加权和，并且权重α之和等于1。这里不难理解，因为GMM最终反映出的是一个概率，而整个模型的概率之和为1，所以权重之和即为1。高斯混合模型实则不难理解，接下来我们介绍GMM的训练(求解)方法。

PS.从数学角度看，对于一个概率模型的求解，即为求其最大值。从深度学习角度看，我们希望降低这个概率模型的损失函数，也就是希望训练模型，获得最大值。训练和求解是不同专业，但相同目标的术语。

三、最大似然估计

     想要了解EM算法，我们首先需要了解最大似然估计这个概念。我们通过一个简单的例子来解释一下。

    假设，我们需要调查学校男女生的身高分布。我们用抽样的思想，在校园里随机抽取了100男生和100女生，共计200个人(身高样本数据)。我们假设整个学校的身高分布服从于高斯分布。但是这个高斯分布的均值u和方差∂2我们不知道，这两个参数就是我们需要估计的值。记作θ=[u, ∂]T。

    由于每个样本都是独立地从p(x|θ)中抽取的，并且所有的样本都服从于同一个高斯分布p(x|θ)。那么我们从整个学校中，那么我抽到男生A（的身高）的概率是p(xA|θ)，抽到男生B的概率是p(xB|θ)。而恰好抽取出这100个男生的概率，就是每个男生的概率乘积。用下式表示：

    这个概率反映了，在概率密度函数的参数是θ时，得到X这组样本的概率。在公式中，x已知，而θ是未知，所以它是θ的函数。这个函数放映的是在不同的参数θ取值下，取得当前这个样本集的可能性，因此称为参数θ相对于样本集X的似然函数（likehood function）。记为L(θ)。

    我们先穿插一个小例子，来阐述似然的概念。

某位同学与一位猎人一起外出打猎，一只野兔从前方窜过。只听一声枪响，野兔应声到下，如果要你推测，这一发命中的子弹是谁打的？你就会想，只发一枪便打中，由于猎人命中的概率一般大于这位同学命中的概率，看来这一枪是猎人射中的。

      这个例子所作的推断就体现了极大似然法的基本思想，我们并不知道具体是谁打的兔子，但是我们可以估计到一个看似正确的参数。回到男生身高的例子中。在整个学校中我们一次抽到这100个男生(样本)，而不是其他的人，那么我们可以认为这100个男生(样本)出现的概率最大，用上面的似然函数L(θ)来表示。

    所以，我们就只需要找到一个参数θ，其对应的似然函数L(θ)最大，也就是说抽到这100个男生（的身高）概率最大。这个叫做θ的最大似然估计量，记为：

因为L(θ)是一个连乘函数，我们为了便于分析，可以定义对数似然函数，运用对数的运算规则，把连乘转变为连加：

PS.这种数学方法在MFCC中我们曾经用过，可以回溯一下上一篇文章。

    此时，我们要求θ，只需要使θ的似然函数L(θ)极大化，然后极大值对应的θ就是我们的估计。在数学中求一个函数的最值问题，即为求导，使导数为0，解方程式即可(前提是函数L(θ)连续可微)。在深度学习中，θ是包含多个参数的向量，运用高等数学中的求偏导，固定其中一个变量的思想，即可求出极致点，解方程。

总结而言：

    最大似然估计，只是一种概率论在统计学的应用，它是参数估计的方法之一。说的是已知某个随机样本满足某种概率分布，但是其中具体的参数不清楚，参数估计就是通过若干次试验，观察其结果，利用结果推出参数的大概值。最大似然估计是建立在这样的思想上：已知某个参数能使这个样本出现的概率最大，我们当然不会再去选择其他小概率的样本，所以干脆就把这个参数作为估计的真实值。

    求最大似然函数估计值的一般步骤：

（1）写出似然函数；

（2）对似然函数取对数，并整理；(化乘为加)

（3）求导数，令导数为0，得到似然方程；

（4）解似然方程，得到的参数即为所求。

四、EM算法

    期望最大(Expectation Maximization， 简称EM)算法，称为机器学习十大算法之一。它是一种从不完全数据或有数据丢失的数据集（存在隐含变量）中求解概率模型参数的最大似然估计方法。

    现在，我们重新回到男女生身高分布的例子。我们通过抽取100个男生身高，并假设身高分布服从于高斯分布，我们通过最大化其似然函数，可以求的高斯分布的参数θ=[u, ∂]T了，对女生同理。但是，假如这200人，我们只能统计到其身高数据，但是没有男女信息(其实就是面对200个样本，抽取得到的每个样本都不知道是从哪个分布抽取的，这对于深度学习的样本分类很常见)。这个时候，我们需要对样本进行两个东西的猜测或者估计了。

      EM算法就可以解决这个问题。假设我们想估计知道A和B两个参数，在开始状态下二者都是未知的，但如果知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A。可以考虑首先赋予A某种初值，以此得到B的估计值，然后从B的当前值出发，重新估计A的取值，这个过程一直持续到收敛为止。

    在男女生身高分布的例子中，我们运用EM算法的思想。首先随便猜一下男生的高斯分布参数:均值和方差。假设均值是1.7米，方差是0.1米，然后计算出每个人更可能属于第一个还是第二个正态分布中。这是第一步，Expectation。在分开了两类之后，我们可以通过之前用的最大似然，通过这两部分，重新估算第一个和第二个分布的高斯分布参数:均值和方差。这是第二步，Maximization。然后更新这两个分布的参数。这是可以根据更新的分布，重新调整E(Expectation)步骤...如此往复，迭代到参数基本不再发生变化。

    这里原作者提到了一个数学思维，很受启发，转给大家看一眼(比较鸡汤和啰嗦，大家可以跳过)

这时候你就不服了，说你老迭代迭代的，你咋知道新的参数的估计就比原来的好啊？为什么这种方法行得通呢？有没有失效的时候呢？什么时候失效呢？用到这个方法需要注意什么问题呢？呵呵，一下子抛出那么多问题，搞得我适应不过来了，不过这证明了你有很好的搞研究的潜质啊。呵呵，其实这些问题就是数学家需要解决的问题。在数学上是可以稳当的证明的或者得出结论的。那咱们用数学来把上面的问题重新描述下。（在这里可以知道，不管多么复杂或者简单的物理世界的思想，都需要通过数学工具进行建模抽象才得以使用并发挥其强大的作用，而且，这里面蕴含的数学往往能带给你更多想象不到的东西，这就是数学的精妙所在啊）

五、EM算法的简单理解方式

    在提出EM算法的推导过程之前，先提出中形象的理解方式，便于大家理解整个EM算法，如果只是实现深度学习模型，个人认为可以不需要去看后面的算法推导，看这个就足够了。

    坐标上升法(Coordinate ascent):

    图中的直线式迭代优化的途径，可以看到每一步都会向最优值靠近，而每一步前进的路线都平行于坐标轴。那么我们可以将其理解为两个未知数的方程求解。俩个未知数求解的方式，其实是固定其中一个未知数，求另一个未知数的偏导数，之后再反过来固定后者，求前者的偏导数。EM算法的思想，其实也是如此。使用坐标上升法，一次固定一个变量，对另外的求极值，最后逐步逼近极值。对应到EM上，E步：固定θ，优化Q；M步：固定Q，优化θ；交替将极值推向最大。 

六、EM算法推导

    现在很多深度学习框架可以简单调用EM算法，实际上这一段大家可以不用看，直接跳过看最后的总结即可。但是如果你希望了解一些内部的逻辑，可以看一下这一段推导过程。

    假设我们有一个样本集{x(1),…,x(m)}，包含m个独立的样本(右上角为样本序号)。但每个样本i对应的类别z(i)是未知的（相当于聚类），也即隐含变量。故我们需要估计概率模型p(x,z)的参数θ(在文中可理解为高斯分布)，但是由于里面包含隐含变量z，所以很难用最大似然求解，但如果z知道了，那我们就很容易求解了。

首先放出似然函数公式，我们接下来对公式进行化简：

    对于参数估计，我们本质上的思路是想获得一个使似然函数最大化的参数θ，现在多出一个未知变量z，公式(1)。那么我们的目标就转变为：找到适合的θ和z让L(θ)最大。

    对于多个未知数的方程分别对未知的θ和z分别求偏导，再设偏导为0，即可解方程。

    因为(1)式是和的对数，当我们在求导的时候，形式会很复杂。

    这里我们需要做一个数学转化。我们对和的部分，乘以一个相等的函数，得到(2)式，利用Jensen不等式的性质，将(2)式转化为(3)式。(Jensen不等式数学推到比较复杂，知道结果即可)

Note:

Jensen不等式表述如下：

如果f是凸函数，X是随机变量，那么：E[f(X)]>=f(E[X])

特别地，如果f是严格凸函数，当且仅当X是常量时，上式取等号。参考链接: https://blog.csdn.net/zouxy09/article/details/8537620

    至此，上面的式（2）和式（3）不等式可以写成：似然函数L(θ)>=J(z,Q)，那么我们可以通过不断的最大化这个下界J(z,Q)函数，来使得L(θ)不断提高，最终达到它的最大值。

    现在，我们推导出了在固定参数θ后，使下界拉升的Q(z)的计算公式就是后验概率，解决了Q(z)如何选择的问题。这一步就是E步，建立L(θ)的下界。接下来的M步，就是在给定Q(z)后，调整θ，去极大化L(θ)的下界J（在固定Q(z)后，下界还可以调整的更大）。

总结而言

EM算法是一种从不完全数据或有数据丢失的数据集(存在隐藏变量)中，求解概率模型参数的最大似然估计方法。

EM的算法流程：

1>初始化分布参数θ；

重复2>, 3>直到收敛:

    2>E步骤(Expectation):根据参数初始值或上一次迭代的模型参数来计算出隐性变量的后验概率，其实就是隐性变量的期望。作为隐藏变量的现估计值：

    3>M步骤(Maximization):将似然函数最大化以获得新的参数值：

这个不断迭代的过程，最终会让E、M步骤收敛，得到使似然函数L(θ)最大化的参数θ。

在L(θ)的收敛证明:

3. EM算法和混合高斯模型（一）

EM（Expectation Maximization）算法是一种迭代算法，用于含有隐变量的概率模型参数的极大似然估计，或极大后验估计。EM算法的每次迭代由两步组成：E步，求期望（expectation）；M步，求极大值，因而被称为期望极大算法，简称EM算法。

本文从EM算法的引入说起，简单介绍EM算法的推导过程，以及其在高斯混合模型中的应用。更多的关于EM算法的推导细节，可参见 人人都懂EM算法 。

假设我们需要调查我们学校学生的身高分布。我们先假设学校所有学生的身高服从正态分布 。( 注意：极大似然估计的前提一定是要假设数据总体的分布，如果不知道数据分布，是无法使用极大似然估计的 )，这个分布的均值μ和标准差为σ 未知，如果我们估计出这两个参数，那我们就得到了最终的结果。那么怎样估计这两个参数呢？

学校的学生这么多，我们不可能挨个统计吧？这时候我们需要用到概率统计的思想，也就是抽样，根据样本估算总体。假设我们随机抽到了 200 个人（也就是 200 个身高的样本数据，为了方便表示，下面“人”的意思就是对应的身高）。然后统计抽样这 200 个人的身高。根据这 200 个人的身高估计均值 μ和方差σ 。例子来自 人人都懂EM算法 。

现在我们假设这200个人的身高服从一个正态分布N(μ，σ)，因此可以直接使用极大似然估计方法估计出这个分布的参数μ和σ。

但是，这200个人的身高真的是服从同一个正态分布吗？实际情况并不是这样的，男生和女生分别服从两种不同的正态分布，即男生 女生各服从一个正态分布 ，( 注意：EM算法和极大似然估计的前提是一样的，都要假设数据总体的分布，如果不知道数据分布，是无法使用EM算法的 )，而且假设我们现在只有身高数据，丢失了性别数据，那么该怎样评估学生的身高分布呢？

这个时候，对于每一个样本或者你抽取到的人，就有两个问题需要估计了，一是这个人是男的还是女的，二是男生和女生对应的身高的正态分布的参数是多少。这两个问题是相互依赖的：

但是现在我们既不知道每个学生是男生还是女生，也不知道男生和女生的身高分布。这就成了一个先有鸡还是先有蛋的问题了。鸡说，没有我，谁把你生出来的啊。蛋不服，说，没有我，你从哪蹦出来啊。为了解决这个你依赖我，我依赖你的循环依赖问题，总得有一方要先打破僵局，不管了，我先随便整一个值出来，看你怎么变，然后我再根据你的变化调整我的变化，然后如此迭代着不断互相推导，最终就会收敛到一个解（草原上的狼和羊，相生相克）。这就是EM算法的基本思想了。

EM的意思是“Expectation Maximization”，具体方法为：

上面的学生属于男生还是女生我们称之为隐含参数，女生和男生的身高分布参数称为模型参数。

EM 算法解决这个的思路是使用启发式的迭代方法，既然我们无法直接求出模型分布参数，那么我们可以先猜想隐含参数（EM 算法的 E 步），接着基于观察数据和猜测的隐含参数一起来极大化对数似然，求解我们的模型参数（EM算法的M步)。由于我们之前的隐含参数是猜测的，所以此时得到的模型参数一般还不是我们想要的结果。我们基于当前得到的模型参数，继续猜测隐含参数（EM算法的 E 步），然后继续极大化对数似然，求解我们的模型参数（EM算法的M步)。以此类推，不断的迭代下去，直到模型分布参数基本无变化，算法收敛，找到合适的模型参数。

在开始介绍EM算法之前，让我们先来了解一个重要的定理——Jensen不等式。

如下图，如果函数f(x)是凸函数，x是随机变量，有 0.5 的概率是 a，有 0.5 的概率是 b， x的期望值就是 a 和 b 的中值了，那么：

对于m个相互独立的样本:

假如没有隐含变量z， 我们仅需要找到合适的θ极大化对数似然函数即可:

现在我们给定一个θ值（初始化θ），那么logL(θ)的值就取决于Q i (z)和P(x (i) ,z (i) )。我们可以通过调整这两个概率使下届逼近logL(θ)的真实值，当不等式变为等式时，说明我们调整后的下届就等于logL(θ)了。由Jeson不等式可知，等式成立的条件是随机变量是常数，则有：

如果Q i (z (i) ) = P(z (i) |x (i) , θ)，则（2）式使我们包含隐藏数据的对数似然函数的一个下届。如果我们能极大化这个下届，则也在尝试极大化我们的对数似然函数。即我们需要极大化下式：

由于对logaf(x)求导的结果与f(x)的系数无关（(ln(ax))'= (lna + lnx)'=1/x），因此对θ求极大似然时，可以去掉式中的常数部分Q i (z (i) )：

现在，让我们来总结一下EM算法的流程。

输入：观察数据x = (x (1) , x (2) , ... , x (m) ), 联合分布P(x, z|θ)，条件分布P(z|x,θ)，极大迭代次数J。
（1）随机初始化模型参数θ值；
（2）迭代求解各个分布模型的参数以及各个模型的概率：
for j from 1 to J:

输出：模型参数θ

图中的直线式迭代优化的路径，可以看到每一步都会向最优值前进一步，而且前进路线是平行于坐标轴的，因为每一步只优化一个变量。

这犹如在x-y坐标系中找一个曲线的极值，然而曲线函数不能直接求导，因此什么梯度下降方法就不适用了。但固定一个变量后，另外一个可以通过求导得到，因此可以使用坐标上升法，一次固定一个变量，对另外的求极值，最后逐步逼近极值。对应到EM上，E步：固定 θ，优化Q；M步：固定 Q，优化 θ；交替将极值推向极大。

E步 ：初始化θ A =0.6和θ B =0.5（θ A 和θ B 分别表示两个硬币出现正面的概率），计算每次掷硬币选择A和B的概率，例如第一个实验中选择A的概率为：

M步 ：求出似然函数下届Q(θ，θ i ), y i 代表第j次试验正面朝上的个数，μ j 代表第j次试验选择硬币A的概率，1-μ j 代表第j次试验选择硬币B的概率。

参考：
人人都懂EM算法
《统计学习方法》. 李航

4. em算法原理

我最近也在看EM算法，主要是它在无监督学习中的应用，例子倒是没有，原理差不多弄明白了一些，其实是出于一种很自然的想法，似然度均值的最大化，但是中间有些问题就是在迭代的过程中似然度是单调增加的，这个证明过程比较繁琐，具体你在模式识别中的应用可以参考这个WiKi页：http://en.wikipedia.org/wiki/Expectation-maximization_algorithm

5. 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算法的收敛性很容易，只需要证明每一轮迭代之后，参数的似然函数递增，即

6. 极大似然估计和EM算法初步

本文来自我的个人博客 https://www.zhangshenghai.com/posts/1422/

极大似然估计是在知道结果的情况下，寻求使该结果出现可能性极大的条件，以此作为估计值。在维基网络中，极大似然估计的定义是这样的：

首先从一个例子入手，假设我们需要调查某个地区的人群身高分布，那么先假设这个地区人群身高服从正态分布 。注意，极大似然估计的前提是要假设数据总体的分布， 不知道数据分布是无法使用极大似然估计的 。假设的正态分布的均值和方差未知，这个问题中极大似然估计的目的就是要估计这两个参数。

根据概率统计的思想，可以依据样本估算总体，假设我们随机抽到了1000个人，根据这1000个人的身高来估计均值 和方差 。

将其翻译成数学语言：为了统计该地区的人群身高分布，我们独立地按照概率密度 抽取了1000个样本组成样本集 ，我们想通过样本集 来估计总体的未知参数 。这里概率密度 服从高斯分布 ，其中的未知参数是 。

那么怎样估算 呢？

这里每个样本都是独立地从 中抽取的，也就是说这1000个人之间是相互独立的。若抽到 的概率是 ，抽到 的概率是 ，那么同时抽到它们的概率就是 。同理，同时抽到这1000个人的概率就是他们各自概率的乘积，即为他们的联合概率，这个联合概率就等于这个问题的似然函数：

对 L 取对数，将其变成连加的，称为对数似然函数，如下式：

对似然函数求所有参数的偏导数，然后让这些偏导数为0，假设有n个参数，就可以得到n个方程组成的方程组，方程组的解就是似然函数的极值点了，在似然函数极大的情况下得到的参数值 即为我们所求的值：

极大似然估计是建立在这样的思想上：已知某个参数能使这个样本出现的概率极大，我们当然不会再去选择其他小概率的样本，所以干脆就把这个参数作为估计的真实值。

和极大似然估计一样，EM算法的前提也是要假设数据总体的分布， 不知道数据分布是无法使用EM算法的 。

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

函数：完全数据的对数似然函数 关于在给定观测数据 和当前参数 下对未观测数据 的条件概率分布 的期望

含有隐变量 的概率模型，目标是极大化观测变量 关于参数 的对数似然函数，即

输入：观测随机变量数据 ，隐随机变量数据 ，联合分布 ，条件分布 ；
输出：模型参数

7. （十）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中，我们提到过：

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

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

剩下的代入即可.

结果展示：

8. em算法的EM算法简述

迭代使用EM步骤，直至收敛。
可以有一些比较形象的比喻说法把这个算法讲清楚。比如说食堂的大师傅炒了一份菜，要等分成两份给两个人吃，显然没有必要拿来天平一点一点的精确的去称分量，最简单的办法是先随意的把菜分到两个碗中，然后观察是否一样多，把比较多的那一份取出一点放到另一个碗中，这个过程一直迭代地执行下去，直到大家看不出两个碗所容纳的菜有什么分量上的不同为止。EM算法就是这样，假设我们估计知道A和B两个参数，在开始状态下二者都是未知的，并且知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A。可以考虑首先赋予A某种初值，以此得到B的估计值，然后从B的当前值出发，重新估计A的取值，这个过程一直持续到收敛为止。
EM 算法是 Dempster，Laind，Rubin 于 1977 年提出的求参数极大似然估计的一种方法，它可以从非完整数据集中对参数进行 MLE 估计，是一种非常简单实用的学习算法。这种方法可以广泛地应用于处理缺损数据，截尾数据，带有噪声等所谓的不完全数据(incomplete data)。
假定集合Z = (X,Y)由观测数据 X 和未观测数据Y 组成，X 和Z = (X,Y)分别称为不完整数据和完整数据。假设Z的联合概率密度被参数化地定义为P(X,Y|Θ)，其中Θ表示要被估计的参数。Θ的最大似然估计是求不完整数据的对数似然函数L(X;Θ)的最大值而得到的：
L(Θ;X)= log p(X|Θ) = ∫log p(X,Y|Θ)dY ；
EM算法包括两个步骤：由E步和M步组成，它是通过迭代地最大化完整数据的对数似然函数Lc(X;Θ)的期望来最大化不完整数据的对数似然函数，其中：
Lc(X;Θ) =log p(X,Y |Θ) ；
假设在算法第t次迭代后Θ获得的估计记为Θ(t) ，则在(t+1)次迭代时，
E-步：计算完整数据的对数似然函数的期望，记为：
Q(Θ|Θ (t)) = E{Lc(Θ;Z)|X;Θ(t)}；
M-步：通过最大化Q(Θ|Θ(t) ) 来获得新的Θ 。
通过交替使用这两个步骤，EM算法逐步改进模型的参数，使参数和训练样本的似然概率逐渐增大，最后终止于一个极大点。直观地理解EM算法，它也可被看作为一个逐次逼近算法：事先并不知道模型的参数，可以随机的选择一套参数或者事先粗略地给定某个初始参数λ0 ，确定出对应于这组参数的最可能的状态，计算每个训练样本的可能结果的概率，在当前的状态下再由样本对参数修正，重新估计参数λ，并在新的参数下重新确定模型的状态，这样，通过多次的迭代，循环直至某个收敛条件满足为止，就可以使得模型的参数逐渐逼近真实参数。
EM算法的主要目的是提供一个简单的迭代算法计算后验密度函数，它的最大优点是简单和稳定，但容易陷入局部最优。