人人都能看懂的EM算法推导

来源：深度学习初学者
本文约6800字，建议阅读10分钟
本文通过案例带大家学习EM算法的推导。

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

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

用数学的语言来说就是：为了统计学校学生的身高分布，我们独立地按照概率密度  抽取了 200 个（身高），组成样本集 (其中 表示抽到的第  个人的身高，这里 N 就是 200，表示样本个数)，我们想通过样本集 X 来估计出总体的未知参数  。这里概率密度  服从高斯分布  ，其中的未知参数是  。

那么问题来了怎样估算参数  呢？

1.1.2 估计参数

我们先回答几个小问题：

问题一：抽到这 200 个人的概率是多少呢？

由于每个样本都是独立地从  中抽取的，换句话说这 200 个学生随便捉的，他们之间是没有关系的，即他们之间是相互独立的。假如抽到学生 A（的身高）的概率是  ，抽到学生B的概率是  ，那么同时抽到男生 A 和男生 B 的概率是  ，同理，我同时抽到这 200 个学生的概率就是他们各自概率的乘积了，即为他们的联合概率，用下式表示：

n 为抽取的样本的个数，本例中  ，这个概率反映了，在概率密度函数的参数是  时，得到 X 这组样本的概率。上式中等式右侧只有  是未知数，所以 L 是  的函数。

这个函数反映的是在不同的参数  取值下，取得当前这个样本集的可能性，因此称为参数  相对于样本集 X 的似然函数（likelihood function），记为  。

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

Q：这里为什么要取对数？

• 取对数之后累积变为累和，求导更加方便

• 概率累积会出现数值非常小的情况，比如1e-30，由于计算机的精度是有限的，无法识别这一类数据，取对数之后，更易于计算机的识别(1e-30以10为底取对数后便得到-30)。

问题二：学校那么多学生，为什么就恰好抽到了这 200 个人 ( 身高) 呢？

在学校那么学生中，我一抽就抽到这 200 个学生（身高），而不是其他人，那是不是表示在整个学校中，这 200 个人（的身高）出现的概率极大啊，也就是其对应的似然函数  极大，即

 这个叫做  的极大似然估计量，即为我们所求的值。

问题三：那么怎么极大似然函数？

求  对所有参数的偏导数，然后让这些偏导数为 0，假设有  个参数，就有  个方程组成的方程组，那么方程组的解就是似然函数的极值点了，从而得到对应的  了。

1.1.3 极大似然估计

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

比如说：

• 假如一个学校的学生男女比例为 9:1 (条件)，那么你可以推出，你在这个学校里更大可能性遇到的是男生 (结果)；

• 假如你不知道那女比例，你走在路上，碰到100个人，发现男生就有90个 (结果)，这时候你可以推断这个学校的男女比例更有可能为 9:1 (条件)，这就是极大似然估计。

极大似然估计，只是一种概率论在统计学的应用，它是参数估计的方法之一。说的是已知某个随机样本满足某种概率分布，但是其中具体的参数不清楚，通过若干次试验，观察其结果，利用结果推出参数的大概值。

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

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

（1）写出似然函数；

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

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

（4）解似然方程，得到的参数。

应用一 ：回归问题中的极小化平方和 （极小化代价函数）

假设线性回归模型具有如下形式: ，其中  ， 误差  ， 如何求  呢？

• 最小二乘估计：最合理的参数估计量应该使得模型能最好地拟合样本数据，也就是估计值和观测值之差的平方和最小，其推导过程如下所示：

  
  

求解方法是通过梯度下降算法，训练数据不断迭代得到最终的值。

• 极大似然法：最合理的参数估计量应该使得从模型中抽取 m 组样本观测值的概率极大，也就是似然函数极大。1

• 假设误差项  ，

则  (建议复习一下正态分布的概率密度函数和相关的性质)

令  则 ， 即将极大似然函数等价于极小化代价函数。

根据之前学过的内容我们知道  ，

当  时， 

当  时，

 

令  

则  ， 即将极大似然函数等价于极小化代价函数。

上面我们先假设学校所有学生的身高服从正态分布  。实际情况并不是这样的，男生和女生分别服从两种不同的正态分布，即男生  ，女生  ，(注意：EM算法和极大似然估计的前提是一样的，都要假设数据总体的分布，如果不知道数据分布，是无法使用EM算法的)。那么该怎样评估学生的身高分布呢？

1.2.2 EM 算法

• 当我们知道了每个人是男生还是女生，我们可以很容易利用极大似然对男女各自的身高的分布进行估计。
• 反过来，当我们知道了男女身高的分布参数我们才能知道每一个人更有可能是男生还是女生。例如我们已知男生的身高分布为  ， 女生的身高分布为  ， 一个学生的身高为180，我们可以推断出这个学生为男生的可能性更大。

• 先设定男生和女生的身高分布参数(初始值)，例如男生的身高分布为  ， 女生的身高分布为  ，当然了，刚开始肯定没那么准；
• 然后计算出每个人更可能属于第一个还是第二个正态分布中的（例如，这个人的身高是180，那很明显，他极大可能属于男生），这个是属于Expectation 一步；
• 我们已经大概地按上面的方法将这 200 个人分为男生和女生两部分，我们就可以根据之前说的极大似然估计分别对男生和女生的身高分布参数进行估计（这不变成了极大似然估计了吗？极大即为Maximization）这步称为 Maximization；
• 然后，当我们更新这两个分布的时候，每一个学生属于女生还是男生的概率又变了，那么我们就再需要调整E步；
• ……如此往复，直到参数基本不再发生变化或满足结束条件为止。

1.2.3 总结

设是定义在实数域上的函数，如果对于任意的实数，都有：

那么是凸函数。若不是单个实数，而是由实数组成的向量，此时，如果函数的 Hesse 矩阵是半正定的，即

是凸函数。特别地，如果  或者  ，称为严格凸函数。

2.1.2 Jensen不等式

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

其中， ，这里 a 和 b 的权值为 0.5,  与 a 的权值相等， 与 b 的权值相等。

特别地，如果函数  是严格凸函数，当且仅当： (即随机变量是常量) 时等号成立。

注：若函数  是凹函数，Jensen不等式符号相反。

2.1.3 期望

对于离散型随机变量 X 的概率分布为  ，数学期望  为：

 是权值，满足两个条件  。

若连续型随机变量X的概率密度函数为  ，则数学期望  为：

设 ， 若  是离散型随机变量，则：

若  是连续型随机变量，则：

对于  个相互独立的样本  ，对应的隐含数据  ，此时  即为完全数据，样本的模型参数为  , 则观察数据  的概率为  ，完全数据  的似然函数为  。

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

增加隐含变量  之后，我们的目标变成了找到合适的  和  让对数似然函数极大：

不就是多了一个隐变量  吗？那我们自然而然会想到分别对未知的  和  分别求偏导，这样做可行吗？

理论上是可行的，然而如果对分别对未知的  和  分别求偏导，由于 是  边缘概率(建议没基础的同学网上搜一下边缘概率的概念)，转化为  求导后形式会非常复杂（可以想象下 复合函数的求导) ，所以很难求解得到  和  。那么我们想一下可不可以将加号从 log 中提取出来呢？我们对这个式子进行缩放如下：

 

上面第(1)式引入了一个未知的新的分布 ，满足：

其中：

也就是说  为第 i 个样本，  为第 i 个样本对应的权重，那么：

上式我实际上是我们构建了  的下界，我们发现实际上就是  的加权求和，由于上面讲过权值  累积和为1，因此上式是  的加权平均，也是我们所说的期望，这就是Expectation的来历啦。下一步要做的就是寻找一个合适的  最优化这个下界(M步)。

假设  已经给定，那么  的值就取决于  和  了。我们可以通过调整这两个概率使下界逼近  的真实值，当不等式变成等式时，说明我们调整后的下界能够等价于 了。由 Jensen 不等式可知，等式成立的条件是随机变量是常数，则有：

 

其中 c 为常数，对于任意 ，我们得到：

由于 。从上面两式，我们可以得到：

边缘概率公式： 

条件概率公式： 

从上式可以发现 是已知样本和模型参数下的隐变量分布。

如果  , 则第 (2) 式是我们的包含隐藏数据的对数似然的一个下界。如果我们能极大化这个下界，则也在尝试极大化我们的对数似然。即我们需要极大化下式：

 

至此，我们推出了在固定参数 后分布  的选择问题， 从而建立了  的下界，这是 E 步，接下来的M 步骤就是固定  后，调整 ，去极大化的下界。

去掉上式中常数的部分  ，则我们需要极大化的对数似然下界为：

输入：观察数据，联合分布  ，条件分布 ， 极大迭代次数  。

1) 随机初始化模型参数  的初值 

2) ：

• E步：计算联合分布的条件概率期望：

• M步：极大化  ,得到  :

• 重复E、M步骤直到  收敛

输出：模型参数 

在上式中分别取  为  和 ，并相减得到：

由于使得极大，因此有：

至此，我们得到了： ，证明了EM算法的收敛性。

从上面的推导可以看出，EM 算法可以保证收敛到一个稳定点，但是却不能保证收敛到全局的极大值点，因此它是局部最优的算法，当然，如果我们的优化目标  是凸的，则EM算法可以保证收敛到全局极大值，这点和梯度下降法这样的迭代算法相同。至此我们也回答了上面提到的第二个问题。

• 支持向量机的SMO算法
• 混合高斯模型
• K-means
• 隐马尔可夫模型

http://ai.stanford.edu/~chuongdo/papers/em_tutorial.pdf

上面这个式子求导之后发现，5 次实验中A正面向上的次数再除以总次数作为即为  ，5次实验中B正面向上的次数再除以总次数作为即为 ，即：

E步：初始化和  ，计算每个实验中选择的硬币是 A 和 B 的概率，例如第一个实验中选择 A 的概率为：

M步：求出似然函数下界 ， 代表第  次实验正面朝上的个数， 代表第  次实验选择硬币 A 的概率， 代表第  次实验选择硬币B的概率 。

针对L函数求导来对参数求导，例如对 求导：

第二轮迭代：基于第一轮EM计算好的  , 进行第二轮 EM，计算每个实验中选择的硬币是 A 和 B 的概率（E步），然后在计算M步，如此继续迭代......迭代十步之后

 

编辑：王菁