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

推荐阅读：
👉《Python matplotlib教程1.0》
👉《R 可视化教程1.0》

下面我会从一个案例开始讲解极大似然估计，然后过渡到EM算法，讲解EM算法到底是个什么玩意儿以及它的核心的idea是什么。之后讲解EM算法的推导公式，鉴于网上很多博客文章都是直接翻译吴恩达的课程笔记内容，有很多推导步骤都是跳跃性的，我会把这些中间步骤弥补上，让大家都能看懂EM算法的推导过程。最后以一个二硬币模型作为EM算法的一个实例收尾。希望阅读本篇文章之后能对EM算法有更深的了解和认识。

极大似然和EM(Expectation Maximization)算法，与其说是一种算法，不如说是一种解决问题的思想，解决一类问题的框架，和线性回归，逻辑回归，决策树等一些具体的算法不同，极大似然和EM算法更加抽象，是很多具体算法的基础。

1.1 极大似然

1.1.1 问题描述

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

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

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

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

1.1.2 估算参数

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

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

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

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

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

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

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

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

1.1.3 极大似然估计总结

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

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

1.1.5 极大似然函数的应用

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

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

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

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

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

在分类问题中，交叉熵的本质就是似然函数的极大化，逻辑回归的假设函数为：

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

当  时， 

当  时，

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

1.2 EM算法

1.2.1 问题描述

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

1.2.2 EM 算法

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

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

1.2.3 总结

2.1 基础知识

2.1.1 凸函数

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

那么是凸函数。若不是单个实数，而是由实数组成的向量，此时，如果函数的 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的概率密度函数为  ，则数学期望  为：

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

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

2.2 EM算法的推导

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

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

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

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

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

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

其中：

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

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

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

方程两边同时累加和：

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

边缘概率公式： 

条件概率公式： 

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

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

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

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

2.3 EM算法流程

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

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

2) ：

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

• M步：极大化  ,得到  :

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

输出：模型参数 

2.4 EM算法另一种理解

2.5 EM算法的收敛性思考

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

由于使得极大，因此有：

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

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

2.6. EM算法应用

• 支持向量机的SMO算法

• 混合高斯模型

• K-means

• 隐马尔可夫模型

已知每个实验选择的是硬币A 还是硬币 B，重点是如何计算输出的概率分布，这其实也是极大似然求导所得。

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

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

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

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

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

3. 《What is the expectation maximization algorithm?》http://ai.stanford.edu/~chuongdo/papers/em_tutorial.pdf

本文来源网络。仅用于传递和分享更多信息，并不代表本平台赞同其观点和对其真实性负责，版权归原作者所有，如有侵权请联系我们删除。

-END-

推荐阅读：

• 10W字《R ggplot2可视化教程1.0》来了!
  
• 详解Python列表推导式|迭代器|生成器|匿名函数
• Jupyter Notebook的16个超棒插件！
• 临床WGS/WES/Gene Panel/Single gene异同
  
• 一图胜千言，超形象图解NumPy教程！
• 那些神经网络可视化利器
• R Graphics Cookbook中译教程

我的学习小圈子👉
加入
赞、在看就是最大的支持