EM 算法，即期望最大化（Expectation-Maximum）算法，用于含有隐变量的概率模型参数的极大似然估计。区别于微积分中通过求导得到最优解的方法，EM 算法是一种迭代算法，并不保证能够得到全局最优解，但可以得到一个局部最优解。
我们所熟知的 均值聚类算法其实是 EM 算法的一个特例。
EM 算法的基本思想
EM 算法的思想是先固定其中一个，推测另一个，如此反复。
例如：模型中有两个未知参数 和
需要估计，而
和
又存在相互依赖的关系，即知道
才能推出
，知道了
才能推出
，这样的问题就可以用 EM 算法。
使用极大似然估计，通过迭代算法，既能估计模型的参数，并且还能得到隐变量的值。注意：EM 算法并不保证得到全局最优解，但是可以得到局部最优解，这一点和梯度下降法是一样的，最终的解和初值有关，这一点在 均值聚类算法中是一样的。
EM 算法用于解决含有隐含变量的概率模型的参数估计问题
EM 算法是对概率模型进行参数估计是一种常见的问题分析的方法。当然概率模型仅存在观测数据的时候，可以直接利用最大似然估计的方法，对似然函数取对数，令各个参数的偏导数为 ，求得的参数的值作为参数的估计。
但是如果模型含有隐变量，并且隐函数和模型参数是互相影响的，就可以通过使用 EM 算法，通过迭代地求解隐含变量的充分统计量和最大化似然函数以达到参数估计的算法。这样即求得了隐变量，还得到了问题的参数估计。
EM 算法刚接触的时候感觉很晦涩，不过如果熟悉了 均值聚类算法，往 EM 算法上靠就会发现，
均值聚类算法其实就是在执行 EM 算法这个框架。先学习
均值聚类，再来看 EM 算法，或许入门会简单一些。
通过 
均值聚类算法学习 EM 算法
这里“同类数据点到其中心的距离之和最短”就等价于似然函数最大。
学习 EM 算法的时候，很容易把自己绕晕，陷入“鸡生蛋、蛋生鸡”的循环，不过可以通过 均值聚类理解 EM 算法的 E 步和 M 步。在
均值聚类中，首先要明确“模型参数”和“隐变量”分别是什么？
1、每个聚类簇的质心是“隐变量”，“隐变量”决定了一个数据属于哪一个类别，一个数据属于距离它最近的质心所所属的类别。
2、我们要求的是哪些数据可以归为一类，这我们可以理解为是“模型的参数”，是我们直接要求的；
接下来，我们对比 均值聚类算法和 EM 算法：
|
|
EM 算法 | 说明 |
|---|---|---|
| （1）选择参数的初值，开始迭代； | ||
| （1）首先选择 |
（2）E 步：记 |
求出隐变量 |
| （2）将样本逐个指派到与其最近的中心的类中，得到一个聚类的结果。 | （3）M 步：求使 |
求出模型参数 |
| 重复第（3）步和第（2）步，直到收敛为止。 | （4）重复第（2）步和第（3）步，直到收敛。 | |
| 李航《统计学习方法》（第 2 版）P264 | 李航《统计学习方法》（第 2 版）P178 |
我又画了一个表格，可能这样看会更清楚一些：
|
|
EM 算法 |
|---|---|
| 第 1 步：随机初始化给出质心，这一步可以认为是求出了隐变量。 | E 步：固定模型参数，求隐含变量。 |
| 第 2 步：固定质心，把每个数据分配给最近的质心，这一步可以认为是求出模型参数。 | M 步：固定隐含变量，求模型参数。 |
| 第 3 步：把是同类数据点取平均，更新质心，这一步可以认为是求出了隐变量。 | E 步：固定模型参数，求隐含变量。 |
| 第 4 步：固定质心，把每个数据分配给最近的质心，这一步可以认为是求出模型参数。 | M 步：固定隐含变量，求模型参数。 |
| 重复第 3 步、第 4 步，直到质心不再变化或者满足最大迭代次数位置。 | 重复 E 步和 M 步。 |
这里再强调一下： 均值聚类算法的隐变量是质心，模型的参数是每个数据点属于哪个分类。再看看 EM 算法的 E 步和 M 步：
- E 步（固定模型参数，求隐变量）
同类数据点取平均，其实就是在每一个数据点确定的情况下，求隐变量质心的概率分布。具体说来，即我们已知一些数据点的集合 ，我们想求得一个点
，使得这个点
与所有集合
中的点的距离之和最小，我们很容易知道，这个点
就应该取成集合
中所有的点的各个分类的平均值（用距离之和对每个分量求偏导，并令偏导数为
）
根据参数初始值或上一次迭代的模型参数来计算出隐性变量的后验概率，其实就是隐变量的期望，作为隐藏变量的现估计值。即在当前估计的参数 的情况下给定
，计算对数似然函数在条件分布
下的期望值，即
- M 步（固定隐变量，求模型参数）
固定隐变量的前提下，求经过隐变量改写的似然函数的极大。质心确定的前提下，每个数据点分给最近的质心就能够使同类数据点到其中心的距离之和最短。找出使上式最大化的参数：
示例代码：
from sklearn.mixture import GaussianMixture
参数有：1、高斯混合模型的个数；2、协方差的类型；3、最大迭代次数。
理解 EM 算法的迭代步骤
首先先找到“紫”线的一个下界函数，即“蓝”线，一定要有重合的那一个“点”，即被图中“绿”线确定的那个点。
然后对“蓝”线取极大值，即被图中“红”线确定的那个点。
如此反复，你会看到，只会逐步来到局部最优值点。
公式推导
手写笔记，我写在这里了：EM 算法手写笔记。
在公式推导的过程中，要用到 Jensen 不等式或者 KL 散度，也称相对熵。关于 Jensen 不等式，我写在这里了：Jenson 不等式的笔记。关于 KL 散度，我写在这里了：信息熵、条件熵、联合熵、互信息、相对熵、交叉熵。
细节一：在使用 Jensen 不等式的时候，需要假设隐变量服从某种形式的概率分布，才可以将推导过程的一部分看成是期望的表达形式从而应用 Jensen 不等式。然而这个分布不是随便指定的。我们令 Jensen 不等式取等号的时候，可以计算出这个分布其实就是：已知观测数据的隐变量的后验概率分布。由于求 Q 函数需要先求出隐变量的后验概率的期望，因此，这就可以解释为什么EM算法的“通俗”理解角度的E步骤是求隐变量的期望了。
细节二：Q 函数与完全数据的对数似然函数的关系。有时候在用 EM 算法解决某个具体问题的时候，会发现 M 步骤极大化的居然是完全数据的对数似然函数。这是因为，Q 函数虽然是完全数据的对数似然函数的某种期望，但是求这个期望的过程有时其实就是将隐变量的后验概率的期望代入就可以了。因此，本质上我们其实还是在求 Q 函数的极大。
高斯混合模型
模型假设：多个高斯分布的加权平均（线性组合），权重（系数）之和为 。
隐变量 ：样本
属于哪一个高斯分布，
与
一一对应，因为
是离散型随机变量，因此可以有一个概率分布（可以认为属于两个分布，概率有大有小）。
生成模型：生成过程如下：1、随机选择一个高斯分布；2、从这个高斯分布生成一个数据。
直接使用极大似然估计，不能得到解析解。
下面是高斯混合模型的例子：
输入：观测数据和类别的总数。
输出：观测数据所服从的几个分布函数的参数。
例如：输入：7000 份成绩，来自 4 个科目：语文、数学、英语、计算机。
输出：4 个科目分别服从的分布的参数值，由于各科成绩服从高斯分布，因此输出为每科成绩的分布参数，以及样本服从各个分布的概率
。
EM 算法解决这个的思路是使用启发式的迭代方法，既然我们无法直接求出模型分布参数，那么我们可以先猜想隐含参数（EM 算法的 E 步），接着基于观察数据和猜测的隐含参数一起来极大化对数似然，求解我们的模型参数（EM算法的M步)。由于我们之前的隐含参数是猜测的，所以此时得到的模型参数一般还不是我们想要的结果。我们基于当前得到的模型参数，继续猜测隐含参数（EM算法的 E 步），然后继续极大化对数似然，求解我们的模型参数（EM算法的M步)。以此类推，不断的迭代下去，直到模型分布参数基本无变化，算法收敛，找到合适的模型参数。
这个时候有人就想到我们必须从某一点开始，并用迭代的办法去解决这个问题：我们先设定男生身高和女生身高分布的几个参数（初始值），然后根据这些参数去判断每一个样本（人）是男生还是女生，之后根据标注后的样本再反过来重新估计参数。之后再多次重复这个过程，直至稳定。这个算法也就是EM算法。
又如：得到一堆身高数据，但是不知道这些身高数据是男生还是女生。
对于每一个样本或者你抽取到的人，就有两个问题需要估计了，一是这个人是男的还是女的，二是男生和女生对应的身高的正态分布的参数是多少。这两个问题是相互依赖的。
有了每个人的归属，或者说我们已经大概地按上面的方法将这 200 个人分为男生和女生两部分，我们就可以根据之前说的最大似然那样，
通过这些被大概分为男生的 n 个人来重新估计第一个分布的参数，女生的那个分布同样方法重新估计。这个是 Maximization。
然后，当我们更新了这两个分布的时候，每一个属于这两个分布的概率又变了，那么我们就再需要调整 E 步。如此往复，直到参数基本不再发生变化为止。
具体方法为：隐变量是一个数据是男生身高数据还是女生身高数据。
E 步：先设定男生和女生的身高分布参数（初始值，即模型参数），例如男生的身高分布为 ， 女生的身高分布为 ，当然了，刚开始肯定没那么准；
然后计算出每个人更可能属于第一个还是第二个正态分布中的（例如，这个人的身高是 cm，那很明显，他极大可能属于男生），这个是属于 Expectation 一步；
M 步：求问题参数，我们已经大概地按上面的方法将这 200 个人分为男生和女生两部分，我们就可以根据之前说的极大似然估计分别对男生和女生的身高分布参数进行估计（这不变成了极大似然估计了吗？极大即为Maximization）这步称为 Maximization。
然后，当我们更新这两个分布的时候，每一个学生属于女生还是男生的概率又变了，那么我们就再需要调整 E 步；
如此往复，直到参数基本不再发生变化或满足结束条件为止。
上面的学生属于男生还是女生我们称之为隐含参数，女生和男生的身高分布参数称为模型参数。
EM 算法解决这个的思路是使用启发式的迭代方法，既然我们无法直接求出模型分布参数，那么我们可以先猜想隐含参数（EM 算法的 E 步），接着基于观察数据和猜测的隐含参数一起来极大化对数似然，求解我们的模型参数（EM 算法的 M 步)。由于我们之前的隐含参数是猜测的，所以此时得到的模型参数一般还不是我们想要的结果。我们基于当前得到的模型参数，继续猜测隐含参数（EM 算法的 E 步），然后继续极大化对数似然，求解我们的模型参数（EM 算法的 M 步)。以此类推，不断的迭代下去，直到模型分布参数基本无变化，算法收敛，找到合适的模型参数。
这个时候有人就想到我们必须从某一点开始，并用迭代的办法去解决这个问题：我们先设定男生身高和女生身高分布的几个参数（初始值），然后根据这些参数去判断每一个样本（人）是男生还是女生，之后根据标注后的样本再反过来重新估计参数。之后再多次重复这个过程，直至稳定。这个算法也就是EM算法。
引入了坐标上升法。
应用： EM 算法有很多的应用，最广泛的就是 GMM 混合高斯模型、聚类、HMM 等等。
具体可以参考 JerryLead 的 cnblog 中 的Machine Learning 专栏。
应用：隐马尔科夫模型， LDA 主题模型。
参考资料
[1] 李航. 统计学习方法（第 2 版）第 9 章“EM 算法及其推广”. 北京：清华大学出版社，2019.
说明：公式很多，写得比较晦涩，但是比较全面，理解书上的内容和细节要查阅一些资料。
[2] 周志华. 机器学习（第 7 章第 6 节“EM 算法”）. 北京：清华大学出版社，2017.
（本节完）
以下为草稿，我自己留着备用，读者可以忽略，欢迎大家批评指正。
参考资料
1、知乎：EM算法存在的意义是什么？
https://www.zhihu.com/question/40797593/answer/275171156
2、Orange先生：浅谈 EM 算法的两个理解角度
https://blog.csdn.net/xmu_jupiter/article/details/50936177
说明：这篇文章没有抄公式，把重要的思想部分提取出来。
3、人人都懂EM算法：https://zhuanlan.zhihu.com/p/36331115
说明：看这篇文章终于知道了个大概。
4、刘建平的文章：https://www.cnblogs.com/pinard/p/6912636.html
说明：如果手边没有《统计学习方法》这本书，可以看这篇博客。
5、Lasso回归算法： 坐标轴下降法与最小角回归法小结：
http://www.cnblogs.com/pinard/p/6018889.html
6、混合高斯模型（Mixtures of Gaussians）和EM算法
https://www.cnblogs.com/jerrylead/archive/2011/04/06/2006924.html
7、数据分析师进阶必备6大数学利器
https://mp.weixin.qq.com/s/BH4hsLjv7rLvR8xOLU1iNQ
8、矩阵论：向量范数和矩阵范数
https://blog.csdn.net/pipisorry/article/details/51030563
9、知乎上的问题：怎么通俗易懂地解释EM算法并且举个例子?
https://www.zhihu.com/question/27976634/answer/163164402
10、从最大似然到EM算法浅解
https://blog.csdn.net/zouxy09/article/details/8537620
11、深入浅出之EM算法(一）
12、深入浅出EM算法（2）
13、极客时间：
14、从最大似然到EM算法浅解。
15、K-Means聚类算法原理
http://www.cnblogs.com/pinard/p/6164214.html
16、用scikit-learn学习K-Means聚类
https://www.cnblogs.com/pinard/p/6169370.html
17、http://scikit-learn.org/stable/modules/generated/sklearn.preprocessing.LabelEncoder.html
18、“上帝的算法”——EM
https://blog.csdn.net/sb19931201/article/details/53586468?utm_source=blogxgwz1
这篇文章主要是摘抄。写了很多参考文献。
说明：这篇文章 EM 算法的推导直接从极大似然估计开始，讲到了我们的目标就是求观测数据的极大似然。
