em算法更新方差

‘壹’ GMM模型是什么

就是用高斯概率密度函数（正态分布曲线）精确地量化事物，将一个事物分解为若干的基于高斯概率密度函数（正态分布曲线）形成的模型。GMMs已经在数值逼近、语音识别、图像分类、图像去噪、图像重构、故障诊断、视频分析、邮件过滤、密度估计、目标识别与跟踪等领域取得了良好的效果。

对图像背景建立高斯模型的原理及过程：图像灰度直方图反映的是图像中某个灰度值出现的频次，也可以认为是图像灰度概率密度的估计。如果图像所包含的目标区域和背景区域相比比较大，且背景区域和目标区域在灰度上有一定的差异，那么该图像的灰度直方图呈现双峰-谷形状。

主要步骤

1、为图像的每个像素点指定一个初始的均值、标准差以及权重。

2、收集N（一般取200以上，否则很难得到像样的结果）帧图像利用在线EM算法得到每个像素点的均值、标准差以及权重）。

3、从N+1帧开始检测，检测的方法：

对每个像素点：

1）将所有的高斯核按照ω/σ降序排序

2）选择满足公式的前M个高斯核：M= arg min(ω/σ>T)

3）如果当前像素点的像素值在中有一个满足：就可以认为其为背景点。

‘贰’ 高斯混合模型（GMM）及EM算法的初步理解

高斯混合模型（Gaussian Mixed Model）指的是多个高斯分布函数的线性组合，理论上GMM可以拟合出任意类型的分布，通常用于解决同一集合下的数据包含多个不同的分布的情况（或者是同一类分布但参数不一样，或者是不同类型的分布，比如正态分布和伯努利分布）。

如图1，图中的点在我们看来明显分成两个聚类。这两个聚类中的点分别通过两个不同的正态分布随机生成而来。但是如果没有GMM，那么只能用一个的二维高斯分布来描述图1中的数据。图1中的椭圆即为二倍标准差的正态分布椭圆。这显然不太合理，毕竟肉眼一看就觉得应该把它们分成两类。

这时候就可以使用GMM了！如图2，数据在平面上的空间分布和图1一样，这时使用两个二维高斯分布来描述图2中的数据，分别记为N(μ1,Σ1)和N(μ2,Σ2) 。图中的两个椭圆分别是这两个高斯分布的二倍标准差椭圆。可以看到使用两个二维高斯分布来描述图中的数据显然更合理。实际上图中的两个聚类的中的点是通过两个不同的正态分布随机生成而来。如果将两个二维高斯分布N(μ1,Σ1)和N(μ2,Σ2) 合成一个二维的分布，那么就可以用合成后的分布来描述图2中的所有点。最直观的方法就是对这两个二维高斯分布做线性组合，用线性组合后的分布来描述整个集合中的数据。这就是高斯混合模型（GMM）。

高斯混合模型（GMM）的数学表示：

期望极大（Expectation Maximization）算法，也称EM算法，是一种迭代算法，由Dempster et. al 在1977年提出，用于含有隐变量的概率参数模型的极大似然估计。

EM算法作为一种数据添加算法，在近几十年得到迅速的发展，主要源于当前科学研究以及各方面实际应用中数据量越来越大的情况下，经常存在数据缺失或者不可用的的问题，这时候直接处理数据比较困难，而数据添加办法有很多种，常用的有神经网络拟合、添补法、卡尔曼滤波法等，但是EM算法之所以能迅速普及主要源于它算法简单，稳定上升的步骤能相对可靠地找到“最优的收敛值”。

(个人的理解就是用含有隐变量的含参表达式不断拟合，最终能收敛并拟合出不含隐变量的含参表达式)

模型的EM训练过程，直观的来讲是这样：我们通过观察采样的概率值和模型概率值的接近程度，来判断一个模型是否拟合良好。然后我们通过调整模型以让新模型更适配采样的概率值。反复迭代这个过程很多次，直到两个概率值非常接近时，我们停止更新并完成模型训练。现在我们要将这个过程用算法来实现，所使用的方法是模型生成的数据来决定似然值，即通过模型来计算数据的期望值。通过更新参数μ和σ来让期望值最大化。这个过程可以不断迭代直到两次迭代中生成的参数变化非常小为止。该过程和k-means的算法训练过程很相似（k-means不断更新类中心来让结果最大化），只不过在这里的高斯模型中，我们需要同时更新两个参数：分布的均值和标准差.[3]

GMM常用于聚类。如果要从 GMM 的分布中随机地取一个点的话，实际上可以分为两步：首先随机地在这 K 个 Component 之中选一个，每个 Component 被选中的概率实际上就是它的系数Πk ，选中 Component 之后，再单独地考虑从这个 Component 的分布中选取一个点就可以了──这里已经回到了普通的 Gaussian 分布，转化为已知的问题。

根据数据来推算概率密度通常被称作 density estimation 。特别地，当我已知（或假定）概率密度函数的形式，而要估计其中的参数的过程被称作‘参数估计’。

（推导和迭代收敛过程这里省略，可参考资料1）

一个实际的例子：用GMM对iris数据集进行聚类，并通过make_ellipses表示出来

make_ellipses方法概念上很简单，它将gmm对象（训练模型）、坐标轴、以及x和y坐标索引作为参数，运行后基于指定的坐标轴绘制出相应的椭圆图形。

在特定条件下，k-means和GMM方法可以互相用对方的思想来表达。在k-means中根据距离每个点最接近的类中心来标记该点的类别，这里存在的假设是每个类簇的尺度接近且特征的分布不存在不均匀性。 这也解释了为什么在使用k-means前对数据进行归一会有效果。高斯混合模型则不会受到这个约束 ，因为它对每个类簇分别考察特征的协方差模型。

K-means算法可以被视为高斯混合模型（GMM）的一种特殊形式。 整体上看，高斯混合模型能提供更强的描述能力，因为聚类时数据点的从属关系不仅与近邻相关，还会依赖于类簇的形状。n维高斯分布的形状由每个类簇的协方差来决定。在协方差矩阵上添加特定的约束条件后，可能会通过GMM和k-means得到相同的结果。

在k-means方法中使用EM来训练高斯混合模型时对初始值的设置非常敏感。而对比k-means，GMM方法有更多的初始条件要设置。实践中不仅初始类中心要指定，而且协方差矩阵和混合权重也要设置。可以运行k-means来生成类中心，并以此作为高斯混合模型的初始条件。由此可见并两个算法有相似的处理过程，主要区别在于模型的复杂度不同。

高斯混合模型的基本假设是 已知类别的比例 和 类别的个数 ，但是不知道每个样例的具体标签，据此用EM的模式为每个样本进行最优的标注。也就是说它适合的是 无标签学习的分类问题 ，并且需要已知基本假设。

整体来看，所有无监督机器学习算法都遵循一条简单的模式：给定一系列数据，训练出一个能描述这些数据规律的模型（并期望潜在过程能生成数据）。 训练过程通常要反复迭代，直到无法再优化参数获得更贴合数据的模型为止。

【1】https://blog.csdn.net/jinping_shi/article/details/59613054  高斯混合模型（GMM）及其EM算法的理解

【2】https://cloud.tencent.com/developer/news/231599    机器学习中的数学（4）-EM算法与高斯混合模型（GMM）

【3】https://zhuanlan.hu.com/p/31103654    一文详解高斯混合模型原理

‘叁’ 数据挖掘十大经典算法之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 Algorithm

EM算法和之前学的都不太一样，EM算法更多的是一种思想，所以后面用几个例子讲解，同时也会重点讲解GMM高斯混合模型。

极大似然估计这里面用的比较多。假设我们想要知道我们学生身高的分布，首先先假设这些学生都是符合高斯分布 我们要做的就是要估计这两个参数到底是多少。学生这么多，挨个挨个来肯定是不切实际的，所以自然就是抽样了。
为了统计学生身高，我们抽样200个人组成样本
我们需要估计的参数 首先估计一下抽到这两百人的概率一共是多少，抽到男生A的概率 抽到学生B的概率 所以同时抽到这两个学生的概率就是 那么同时抽到这200个学生的G概率
最后再取一个对数就好了：

似然函数的执行步骤：
1.得到似然函数
2.取对数整理
3.求导数，另导数为零
4.解方程得到解

首先引出凸函数的概念 那么就是凸函数，所以它的图像就是一个勾形的，看起来是一个凹函数，实际上是凸函数。

正常来看先是要引入一个最大似然函数： 但这样其实是和难求的，P(x|θ)完全混在了一起，根本求不出来，所以我们要引入一个辅助变量z。

所以我们引入隐变量的原因是为了转化成和这几个高斯模型相关的式子，否则无从下手。化简一下上式子： 既然z可以指定x，那么我们只需要求解出z就好了。
注意上面凸函数所提到的一个期望性质，这里就可以使用了。因为虽然优化了上面的式子，还是不能求出来，因为z变量实在是太抽象了，找不到一个合适的公式来表示它。EM的一个方法就是用优化下界函数的方法来达到优化目标函数的目的。
既然z很抽象，那么我们就需要一个转变一下。对于每一个样例x都会对应一个z，那么假设一个分布Q(z)是满足了z的分布的，而Q(z)满足的条件是 Qi意味着每一个x对应的z都会对应着一个Q了，这里有点复杂，再详细解释一下。一个x对应一组z，z是一个向量，但是每一个z又会分别对应一个一个分布Q。以为最后得到的z不会是一个数字，而是一个概率，也就是说Q(z)得到的是这个x样例属于这个类别的概率是多少。而z的数量，一个是当前有多少个分布混合在一起的数量。
再梳理一下：现在的样本是xi，那么每一个xi将会对应着一组的z，每一个xi同时也会对应着一个分布Qi，z其实就是反应了这个样本是来自于哪个分布的。比如这个x是A1分布做了3，A2分布做了5，那么z可能就是={3,5}。所以Qi(z)得到的是这个x属于这些个分布的概率，也就是说这些分布对x做了多少百分比的功，自然就是要等于1了。
还要注意的是，上面的 这个并不能得到Qi(z)就是分布对x做了多少功的结论，得到这个结论是后面下界函数与目标函数相等得到的。这里只是知道了总和等于1，因为是分布的总和嘛。
现在就到了公式的化简：
仔细看一下这个式子 这个式子其实就是求 的期望，假设 ，那么可以利用上面 。于是化简：
这个时候就得到了下界函数，上面也讲过了，想要相等，自然就是x要是常数，所以 既然 ，而且z也是一样的，因为一个样本嘛。所以上下加和（如果是离散的，那就sum一下，连续的那就积分，这里是离散的，所以就是sum一下）。于是有
于是有：

这就是整一个EM算法的框架了，可以看到其实没有比较具体的算法，大致上就是一个框架。那么问题来了，怎么样证明这东西是一个收敛的？？

可以直接把高斯混合模型代入EM框架里面。
存在多个高斯分布混合生成了一堆数据X，取各个高斯分布的概率是 ，第i个高斯分布的均值是 ，方差是 ，求法φ，μ，σ。
按照套路，第一个E-step求出Q，于是有：
意思就是求出第i个样本属于第j个分布的概率是多少。之后就是M-step了，就是化简了：

这里可能需要解释一下，根据 至于条件，因为很明显，z是隐变量，只是指明了x是属于哪个类别，和μ，Σ没有什么关系，所以直接忽略那两个参数了，所以P(z)是没有那两个参数的，z是代表了分布，所以每一个分布的概率肯定是包括了，所以就只有一个概率的参数。P(x|z)是本身的概率，就是已经知道分布是那个了，求属于这个分布的概率是多少，既然已经选定了分布那么自然就不需要再看φ了，因为φ是各个分布的概率。

现在有两个硬币AB，进行5次试验每一次投10次，并不知道是哪个硬币投的，求两种硬币的正面的概率。
首先E-step：
首先先初始化一下，
第一个试验选中A的概率：
同样求得
计算机出每一个试验的概率然后相加求均值。
之后就是M-step了：

方差的求解就不玩了，主要就是迭代求解μ和φ的值了。
首先是生成数据，4个高斯分布，每一个高斯分布的sigma都是一样的，不一样的只有μ和α，也就是φ，习惯上把前面的一个参数叫做权值，所以用α来表示。

这四个模型的比例分别是1:2:3:4，使用EM来找到他们属于的类别。

其实如果用kmeans聚类的话更加快速，但是这里还是用EM。
E-step：

就是按照公式来求解w即可，求解每一个分布对样本点做了多少的功，之后求单个样本点求比例。
M-step：

直接按照公式优化即可。

运行函数。看看结果：

结果其实还是相差不大。达到预期。

上面所讲的其实只是一种理解方法，在李航老师的统计学习方法里面是另一种比较厉害的解法：
1.E-step：求出Q函数。
2.M-step：利用Q函数求极大值。
其实这两种方法是完全一样的，Q函数就是下界函数，

EM和Kmeans算法其实很类似，事实上步骤基本可以用EM框架来替换，但是Kmeans算法是硬分类，说一不二，但是EM算法不太一样，是软分类，百分之几是那个，百分之几是这个。

缺点也还是有的：初值敏感，局部最优。因为存在了隐变量，所以导致了直接对x做极大似然是不可行的，log已经在sum的外面了。所以EM算法就转向了下界函数，而这种方法本来就不保证找到局部最优解。

如果将样本看作观察值，潜在类别看作是隐藏变量，那么聚类问题也就是参数估计问题。如果一个目标函数存在多个变量，那么梯度下降牛顿法这些逼近方法就用不了了。但我们可以使用坐标上升方法，固定一个变量，对另外一个求导数，然后替换最后逐步逼近极值点。对应到EM算法也是一样，E步求隐含的z变量，Mstep求解其他参数。

‘伍’ 高斯混合模型(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(θ)的收敛证明:

‘陆’ 05 EM算法 - 高斯混合模型 - GMM

04 EM算法 - EM算法收敛证明

GMM (Gaussian Mixture Model, 高斯混合模型)是指该算法由多个高斯模型线性叠加混合而成。每个高斯模型称之为component。

GMM算法 描述的是数据的本身存在的一种分布，即样本特征属性的分布，和预测值Y无关。显然GMM算法是无监督的算法，常用于聚类应用中，component的个数就可以认为是类别的数量。

回到昨天说的例子：随机选择1000名用户，测量用户的身高；若样本中存在男性和女性，身高分别服从高斯分布N(μ1,σ1)和N(μ2,σ2)的分布，试估计参数:μ1,σ1,μ2,σ2；

1、如果明确的知道样本的情况(即男性和女性数据是分开的)，那么我们使用极大似然估计来估计这个参数值。

2、如果样本是混合而成的，不能明确的区分开，那么就没法直接使用极大似然估计来进行参数的估计。

我们可以认为当前的1000条数据组成的集X，是由两个高斯分布叠加而成的(男性的分布和女性的分布)。

如果能找到一种办法把每一个高斯分布对应的参数π、 μ、σ求出来，那么对应的模型就求解出来了。

如果模型求解出来后，如何对数据进行聚类？

这个公式求出来的分别是男性和女性身高分布的概率密度，如果把π、 μ、σ都求出来，以后我们可以构建出一个 能够根据样本特征 计算出样本属于男性或女性的可能性。

实际做样本分类的时候，我们把样本X的特征x1~xn分别代入两个公式中，求出来的两个结果分别是：样本X的性别是男、是女的可能性。如果是男的可能性大于是女的可能性，我们就把样本X归入男性的分类。

假定 GMM 由k个Gaussian分布线性叠加而成，那么概率密度函数如下：

分析第1个等式：
p(x)： 概率密度函数，k个Gaussian分布线性叠加而成的概率密度函数。
∑p(k)p(x|k)： k个某种模型叠加的概率密度函数。
p(k)： 每个模型占的权重，即上面提到的π。
p(x|k)： 给定类别k后，对应的x的概率密度函数。

分析第2个等式： 目标 - 将公式写成高斯分布的样子。
π k ： 即p(k)
p(x;μ k ,∑ k )： 多元高斯(正态)分布。有了观测数据x后，在 给定了条件 下的高斯分布。这个 条件 是 1、第k个分类的均值μ k ; 2、第k个分类的方差∑ k ;

深入分析p(x;μ k ,∑ k )的参数：
如果样本有n个特征，所有的特征x1~xn一起服从一个多元的高斯分布(正态分布)，所有特征的均值应该是一个向量 (μ 1 ~μ n )；
μ k ： 第k个分类的情况下(第k个高斯分布的情况下对应的每一列的均值)；μ k = (μ k1 ~μ kn )

∑ k ： 协方差矩阵(对称阵)。现在有n个特征，协方差矩阵是一个n×n的矩阵。现在我们要算的是：

cov(x1,x1)，cov(x1,x2)，...，cov(x1,xn)

cov(x2,x1)，cov(x2,x2)，...，cov(x2,xn)
....
cov(xn,x1)，cov(x1,x2)，...，cov(xn,xn)

其中， 对角线 cov(x1,x1)、cov(x2,x2)， ... ，cov(xn,xn)中，x1和x1的协方差 = x1的方差；即cov(x1,x1) = var(x1)；所以 对角线上两个特征的协方差 = 对应的特征的方差。

协方差 （Covariance）在 概率论 和 统计学 中用于衡量两个变量的总体 误差 。而 方差 是协方差的一种特殊情况，即当两个变量是相同的情况。

协方差表示的是两个变量的总体的 误差 ，这与只表示一个变量误差的 方差 不同。 如果两个 变量 的变化趋势一致，也就是说如果其中一个大于自身的期望值，另外一个也大于自身的期望值，那么两个变量之间的协方差就是正值。 如果两个变量的变化趋势相反，即其中一个大于自身的期望值，另外一个却小于自身的期望值，那么两个变量之间的协方差就是负值。

理解了公式后，再来看看公式在图像上是如何体现的：

如果样本X只有一个特征x1，在二维的坐标系上的表示出来。特征x1是由n个单变量样本的高斯分布叠加而成的。向量x1 k = ∑ k (x1 (1) ,x1 (2) ,~,x1 (n) )，如k=(男、女)，累加男性分类下的特征高斯分布和女性分类下的高斯分布；

图中 红色曲线 表示原有数据的分布情况，我认为这个原有数据是由多个比较的高斯分布叠加而成的， 蓝色曲线 表示单个单个高斯分布的分布情况。向量x1 = (x1 (1) ,x1 (2) ,~,x1 (n) )；

PS： 蓝1+蓝2=红 体现的就是公式 p(x) = ∑πp(x;μ,∑k)；

在得知数据的特征 x=(x1~xn) 后，如果我们想把数据合理得聚类到一个分类中，我们该如何去计算呢？

既然我已经得到了k个高斯分布对应的概率密度函数(现在设k=3，共3个分类)，将当前特征的x=(x1~xn)代入我们的概率密度函数： p(x) = ∑πp(x;μ,∑k)；

我们分别计算p(蓝1)、p(蓝2)、p(蓝3)，蓝色三条线各对应k分类中的一个，哪个数大，我认为当前的样本该分到哪一类。

GMM算法的两个前提：
1、数据服从高斯分布；
2、我们人为定义了分类个数k。

问：我们人为假定了高斯分布的分类个数k，就类似于我们聚簇时分的聚簇中心个数一样。参数π、μ、σ该如何求出来?

答：和K-Means算法一样，我们可以用 EM算法 来求解这个问题。 GMM也满足EM算法的聚类思想，首先人为得定义了聚类的个数k，从数据特征X中发掘潜在关系的一种模型。而且我还默认数据是服从多个高斯分布的。

GMM算法中的隐含条件是：第k个模型占的权重 - 、 第k个高斯分布的情况下对应的每一列的均值 - 、协方差矩阵 cov(xi,xj) - ；因为本质上我们是知道数据原有的分类状况的，只是无法观测到隐含在数据中的这些特性，使用EM的思想可以迭代得求解出这些隐含变量。

对联合概率密度函数求对数似然函数：

对联合概率密度函数求对数后，原本 连乘 的最大似然估计变成了 连加 的函数状态。

EM算法求解 - E步：

套用公式后，我们可以假定隐含变量z的分布：Q(z (i) = j)；
我们认为分布wj (i) = 第i个观测值对应的隐含分类第z (i) 类； = 以(看不见的参数π、μ、∑)为参数的情况下，输入第i观测值的特征x后得到的分类z (i) 类；

EM算法求解 - M步：
M步第1行就是上一章通过化简找到 下界 的那个函数：

1、对均值求偏导:

2、对方差求偏导:

3、对概率使用拉格朗日乘子法求解:

06 EM算法 - 案例一 - EM分类初识及GMM算法实现

‘柒’ 极大似然估计和EM算法初步

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

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

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

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

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

那么怎样估算 呢？

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

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

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

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

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

概率模型有时既含有观测变量，又含有隐变量。如果概率模型的变量都是观测变量，那么给定数据，可以直接用极大似然估计法，或贝叶斯估计法估计模型参数。但是，当模型含有隐变量时，就不能简单地使用这些估计方法。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算法的收敛性很容易，只需要证明每一轮迭代之后，参数的似然函数递增，即