em算法极大似然估计

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

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

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

剩下的代入即可.

结果展示：

B. EM算法有什么用

EM算法是求含有隐变量的极大似然估计，可以用于包含隐变量的参数估计

C. EM算法详解

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

极大似然估计是概率统计中，估计模型参数的一种方法，如果对似然概念以及极大似然估计的概念不理解，可参考维基网络 https://zh.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E4%BC%BC%E7%84%B6%E4%BC%B0%E8%AE%A1

这里，我们给出一个一维高斯函数的例子。如图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步的内容。这一部分内容来自徐亦达老师的课件。由于公式太多了，我就放一些截图，供大家一起学习和参考。

徐亦达老师的课件在： https://github.com/roboticcam/machine-learning-notes/blob/master/em.pdf

后续关于EM算法的应用会举例以下几方面内容
(1)Kmeans和高斯混合模型
(2)EM算法应用之贝叶斯线性回归
(3)EM算法应用之PLSA
(4)EM算法应用之缺失数据参数估计问题

D. 最大似然函数和EM 算法

在 数理统计学 中， 似然函数 是一种关于 统计模型 中的 参数 的 函数 ，表示模型参数中的 似然性 。

似然函数在 统计推断 中有重大作用，如在 最大似然估计 和 费雪信息 之中的应用等等。“似然性”与“或然性”或“ 概率 ”意思相近，都是指某种事件发生的可能性，但是在 统计学 中，“似然性”和“或然性”或“概率”又有明确的区分。

概率 用于在已知一些参数的情况下，预测接下来的观测所得到的结果，而

似然性 则是用于在已知某些观测所得到的结果时，对有关事物的性质的参数进行估计。

最大似然估计你可以把它看作是一个反推。多数情况下我们是根据已知条件来推算结
果，而最大似然估计是已经知道了结果，然后寻求使该结果出现的可能性最大的条件，以此作为估计值。

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

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

（1）写出似然函数；

（2）对似然函数取对数，并整理；

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

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

背景是数学之美的聚类的情况下，
首先，根据现有模型，计算各个观测数据输入到模型中的计算结果，这个过程称为期望值计算过程（Expectation），或E过程；接下来，重新计算模型的参数，以最大化期望值。在上面的例子中，我们最大化D和 -d ，这个过程称为最大化的过程（Maximization），或 M 过程。这列算法都成为EM算法。

大西瓜：它是一种迭代式的方法，其基本思法是：若参数 s 已知，则可根据训练数据推断出最优隐变量 Z 的值（E 步）；反之，若 Z 的值已知，则可方便地对参数 s 做极大似然估计（M 步）。

EM 算法还包括：隐马尔可夫模型的训练方法Baum-Welch 算法，以及最大熵模型的训练方法GIS算法。
EM 算法不一定保证全局最优解，如果目标函数是一个凸函数，那么一定能保证最优解。所幸熵函数是一个凸函数，如果在 N 维空间以欧氏距离做度量，聚类中我们试图优化的两个函数也是凸函数。但是，很多情况下，包括文本分类中的余弦距离都不能保证是凸函数，因此哟可能EM 算法给出的局部最优解而不是全局最优解。

高斯分布、指数分布那个得到全局最优。
混合高斯不一定，如果是凸函数就可以。

机器学习——几种距离度量方法比较
从最大似然到EM算法浅解

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

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

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

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

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

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

那么怎样估算 呢？

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

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

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

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

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

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

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

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

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

F. 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算法的主要目的是提供一个简单的迭代算法计算后验密度函数，它的最大优点是简单和稳定，但容易陷入局部最优。

G. 大数据经典算法解析（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算法实例分析 .

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

I. EM算法和K-Means算法

在实际工作中，会遇到这样的问题，给机器输入大量的特征数据，并希望机器希望学习找到某种共同的特征或者结构，亦或是数据之间存在的某种关联，例如，视频网站根据用户的观看行为进行分组，从而建立不同的推荐策略，或是找到视频是否流畅与用户是否退订之间的关系等。属于无监督学习算法。

包括两大类，一：数据聚类，此类方案往往是通过数次迭代找到数据的最优分割。二：特征变量的关联规则，此类方法利用各种相关性分析找到变量之间的关系。

Kmeans的 核心 是将给定的数据集划分成K个簇，并给出每个数据对应的中心点。算法具体步骤如下：

1：数据预处理，如归一化、离散点处理等

2：随机选取K个簇中心，记为 。

3：定义代价函数： 。

4：令 为迭代步数，重复下面过程直到 收敛

4.1 对于每一个样本将其分到距离最近的簇

4.2 对于每一个类簇k，重新计算类簇的中心

K均值在迭代时，交替方向法求解，假设当前 没有达到最小值，那么首先固定簇中心 ,调整样本 所属的类别 来让 函数减小，然后再固定 ,调整中心 使 减小，这两个过程交替循环， 单调递减，当 递减到最小时， 和 同时收敛。

缺点：

1：受初始值的影响

2：异常值的影响

3：当簇分布相差很大时，不适合

优点：

大数据集， 均值聚类相对是可伸缩和高效的，计算复杂度 ,其中 是数据对象的数目， 是聚类簇数， 是迭代的轮数。尽管算法经常局部最优结束，一般情况下局部最优已经满足要求

调优方向

1：数据归一化和离散点处理

2：合理选择 值

一：手肘法：选择若干个K画均方误差的折线图肉眼查看拐点 二：Gap Statistic方法的基本思路是：引入参考的测度值，其可以通过Monte Carlo采样的方法获得。 

3：采用核函数

利用kmeans假设各个数据簇的数据具有一样的先验概率，并呈现高纬球形分布，但是实际生活中是不常见的。面对非凸的数据分布时，引入核函数来优化。核心：利用非线性核函数将样本映射到高纬空间，并在新的特征空间中进行聚类。非线性映射增加了数据的线性可分的概率。

针对对初始值敏感的改进

K-means++算法：

起步

由于 K-means 算法的分类结果会受到初始点的选取而有所区别，因此有提出这种算法的改进: K-means++ 。

算法步骤

其实这个算法也只是对初始点的选择有改进而已，其他步骤都一样。初始质心选取的基本思路就是，初始的聚类中心之间的相互距离要尽可能的远。

算法描述如下：

步骤一： 随机选取一个样本作为第一个聚类中心；

步骤二：

计算每个样本与当前已有类聚中心最短距离（即与最近一个聚类中心的距离） 这个值越大，表示被选取作为聚类中心的概率较大；

最后，用轮盘法选出下一个聚类中心；

步骤三： 重复步骤二，知道选出 k 个聚类中心 。

选出初始点后，就继续使用标准的 k-means 算法了。

      ISODATA的聚类个数是可变的，因为在聚类的过程中，对类别数有一个“合并”和“分裂”的操作。合并是当聚类结果某一类中样本数太少，或两个类间的距离太近时，将这两个类别合并成一个类别；分裂是当聚类结果中某一类的类内方差太大，将该类进行分裂，分裂成两个类别。

ISODATA分类的过程和K-Means一样，用的也是迭代的思想：先随意给定初始的类别中心，然后做聚类，通过迭代，不断调整这些类别中心，直到得到最好的聚类中心为止。

注：

初始簇个数 ，最终簇大小范围

分裂和合并的标准

每个簇的样本数最小 ，小于这个值不进行分裂

每个簇样本的最大方差 ，大于这个则进行分裂

两个簇之间的最小距离围 ，小于这个则进行合并

EM算法是一种迭代算法，用于含有隐变量的概率模型的极大似然估计，或者说是极大后验概率估计。

算法步骤

输入：观测变量数据Y，隐变量Z，联合分布 ，条件分布

输出：模型参数

1：选择参数的初始值

2：E步：记 为第 次迭代参数 的估计值，在第 次迭代的E步，计算 函数 ，其中， 是再帮给定Y和 下隐变量数据Z的条件概率分布；

3：M步：求使 极大化的 ，确定第 次迭代的参数的估计值 ,

4：重复2，3步，直到收敛

EM算法推导

通过不断求解下界的极大化逼近求解对数似然函数的极大化的算法

含有隐变量的概率模型的极大似然估计

下面证明

利用Jensen不等式

令

则 即函数 增大 ，也可以使得 有尽可能的增大，选择 使得 达到极大，即 现在求 的表达式 = = = =

假设有m个观察样本，模型的参数 ，最大化对数似然函数可以写成如下的形式

当概率模型含有无法观测的隐变量时，参数的最大似然估计

因为含有不可观测的隐变量，无法通过极大似然估计求解参数，这时可以通过EM算法求解。假设 对应的分布 ，并满足 。利用Jensen不等式，可以得到，

。不等式右侧，即为 。当等式成立时，我们相当于优化的函数找到了一个逼近的下界，然后最大化这个下界

EM算法和k-means关系

1：E步骤

2：M步骤：最大化

K均值算法等价于以下隐变量求最大似然问题

相当于E步找到x当前最近的簇

在M步骤 来更新簇中心

#####引用葫芦书和李航机器学习