怎么通俗易懂地解释EM算法并且举个例子

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

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

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

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

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

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

初始化分布参数

2.重复直到收敛：

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

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

1977年，DempSter首次提出EM算法。

假设四种实验结果，发生的概率依次为 ，且发生的次数为 ，求 的估计。

解：使用MLE，得到：

上式是关于 的一元三次方程，不易解。

因此，以下另作处理（引入隐变量）：

将第一部分 分为 ，且出现次数为 次

将第三部分 分为 ，且出现次数为 次；

则

(1)

现在，并不知道 （隐变量）的值，只能知道分布的信息， 服从的分布为二项分布，概扮毕率数值类似于条件概率，第一个的概率是用 除以得到的，第二个同理：

其中， ，

第一步（E步）：求期望的目的是为了消去隐变量 。

代入(1)式，得到：

第二步（M步）：取最大值。

EM算法使用迭代法来更新参数。 （精髓）

任意取 ，就可以开始按照上面的公式进行迭代了。

收敛性 ：

DempSter证明：在很一般的条件下，最后会收敛。（可以参考李航老师的《统计学习方法》）

解析解：能列出公式解决的，数值上是更准确的（相比迭代解），比如MLE就是列出公式求解。

迭代解：退而求其次，当解析解难求的时候，通过迭代逼近的方式，可以获得令人满意的解，比如EM就是为了解决当MLE遇到高次方程难以求解的时候，提出的方法。

问：给定参数 ，观测变量 ，隐变量 ，如何估计参数 ？

从观测序列，可以获得：

此时，对数似然函数为：

由于包含和（积分）的对数，因此直接求解困难。

解析解困难，转而使用迭代解：假设第i次迭代后的为 ，由于我们希望似然函数 是增大的，即 。

此时，考虑两者的差：

不等式右边是 的下界，记为 ，那么，使得下界尽可能大，即：

Algorithm: Estimation Maximum (EM)

举例：以三硬币模型为例。有A、B、C三枚硬币，分别有皮缺誉 的概率为正面。每次试验为：先投A硬币，如果A为正面，则投B硬币；否则，投C硬币。最终，可以观测到的结果为硬币的正/反面，但是不知道是由B还燃段是C投出的（隐变量）。问：如果某次试验数为10的结果为：{1,1,0,1,0,0,1,0,1,1}，如何估计参数 ？

显然，题目的 隐变量为A硬币投出的结果，此时可以采用EM解法。

先从“E”入手，求解Q函数：

然后，逐一击破：

回代 函数：

极大似然求导数，令其为0，能取得极值点：

令上式为0

------对应书(9.6)式

令上式为0

------对应书(9.7)式

令上式为0

------对应书(9.8)式

至此，只要根据当前迭代下的 ，就能得到不同下标的 ，进而得到下一次迭代的 。

作为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算法应用之缺失数据参数估计问题

---