前言

EM 算法的讲解的内容包括以下几个方面：

1、最大似然估计

2、K-means算法

3、EM算法

4、GMM算法

EM算法本质是统计学中的一种求解参数的方法，基于这种方法，我们可以求解出很多模型中的参数。

1、最大似然估计 MLE

在求解线性模型的过程中，我们用到了最大似然估计(MLE)的思想。

EM算法达到的目的和最大似然估计是一样的，只不过EM算法可以帮助我们去计算一些隐藏变量的参数。

即当极大似然估计无法解决某些问题的时候，我们需要使用EM算法这种迭代算法的思路，不断得逼近最后的参数解。

EM算法不是具体某一种模型，而是一种求解问题的思路。

在统计学中这种算法思想用的特别多。

2、K-means算法

K-means 算法的求解过程本质上就是EM算法的思想，面试中曾经有人问：K-means算法究竟是如何运用EM算法来实现的？

这样两个算法就通过一个问题来挂上钩了。

3、EM算法

然后讲到如何将EM算法用一种比较通式化的方法来实现求解过程，即但凡我们遇到一个可以用EM算法来解决的问题，我们如何去求解这个问题对应的参数。

就好比极大似然估计中，我们使用联合概率作为似然函数的值，然后求解极大值。

当然首先不同的问题会有不同的联合概率，先要把这个联合概率构造出来。

GMM算法

最后使用EM算法解决一个问题：有一个模型叫做高斯混合模型(GMM)，可以通过EM算法来帮助我们来求解它最后的参数值。

最大似然估计回顾

定义

最大似然估计(Maximum Likelihood Estimati) 就是利用已知的样本结果，反推最有可能(最大概率)导致这样结果的参数值的计算过程。

直白来讲，就是给定了一定的数据，假定知道数据是从某种分布中随机抽取出来的，但是不知道这个分布具体的参数值，即“模型已定，参数未知”，MLE就可以用来估计模型的参数。

MLE的目标是找出一组参数(模型中的参数)，使得模型产出观察数据的概率最大。

例子

假定盒子中有黑白两种球，数目未知，黑白球比例也未知，现只知道随机的十次有放回的抽样情况，求各个盒子中抽取出白球的概率？

image

MLE求解过程：

1、编写似然函数(即联合概率函数) <似然函数：在样本固定的情况下，样本出现的概率与参数θ之间的函数>；

2、对似然函数取对数，并整理；(一般都进行)

3、求导数。

4、解似然方程。

image

分析

盒子中只有黑球和白球，假定白球的比例为p，那么黑球的比例为1-p。

因为采取的是有放回的随机抽取，那么每次抽取出来的球的颜色服从同一独立分布情况，即每次抽取之间是独立互不影响的。

image

  • 求解盒子1中抽取出白球的概率：

左-求联合概率 中-取对数 右-求极值

image

  • 求解盒子2中抽取出白球的概率：

左-求联合概率 中-取对数 右-求导并求极值

image

  • 求解盒子3中抽取出白球的概率：

image

  • 求解盒子 4 中抽取出白球的概率：

image

  • 求解盒子 5 中抽取出白球的概率：

image

个人感受

和直接概率的差异在哪里？

EM 算法简介

最大期望算法(Expectation Maximization Algorithm，又译期望最大化算法)，是一种迭代算法，用于含有隐变量(hidden variable)的概率参数模型的最大似然估计或极大后验概率估计。

在统计计算中，最大期望(EM)算法是在概率(probabilistic)模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量(Latent Variable)。

最大期望经常用在机器学习和计算机视觉的数据聚类(Data Clustering)领域。

公式推导

参见 EM 完整推导过程

隐变量

未观测变量的学名是“隐变量”（latent variable）。

EM算法是常用的估计参数隐变量的利器，它是一种迭代式的方法，其基本思想是：

若参数θ已知，则可根据训练数据推断出最优隐变量Z的值(E步)；反之，若Z的值已知，则可以方便地对参数θ做极大似然估计(M步)。

于是，以初始值θ0为起点，可迭代执行以下步骤直至收敛：

  1. 基于θt推断隐变量Z的期望，记为Zt;

  2. 基于已观测变量X和Zt对参数θ做极大似然估计，记为θt+1

抛硬币例子

我们现在考虑两个抛硬币的例子：

入门级别

给定两个硬币A和B，随机抛掷后正面朝上概率分别记为 ‘p’ 和 ‘q’。

每次随机选择一个硬币并投掷。

有以下观察序列：

H A H A T B T A T B H B H B T A H B H  A T  A T  A H  A H B H  A T B

从给定数据估计出’p’和’q’的值”。

我们很容易计算出

p = 所有A的正面/所有A的投掷 = 5/9，

同理

q = 所有B的正面/所有B的投掷 = 4/7

这很容易，因为计算未知参数所需的所有信息都是可获得的。

标签隐藏

但是，如果硬币上的标签(A和B)被隐藏起来,不知道每次投掷哪个硬币。

鉴于A和B硬币同样可能被选中，那我们如何估计未知参数’p’和’q’?

我们将尝试通过多次迭代计算来解决问题。

在每次迭代中，我们有两个步骤，’E’步骤和’M’步骤。

“E”步骤（期望）：

  1. 首先初始化p和q的值(初始猜测)。

  2. 我们不是说掷硬币来自特定的硬币，而是说它以概率为’x’来自硬币A，来自硬币B概率’1-x’。

  3. 计算每枚硬币的正反期望数量。

“M”步骤（最大化）：

  1. 从“E”步骤计算步骤3中每个硬币的正反期望的对数似然，类似于MLE计算。

  2. 最大似然估计出隐变量，并重新估计p和q的新值

  3. 使用新的p和q值重复“E”步骤，直到它收敛为止。

思想比推导更加重要

如果使用基于最大似然估计的模型，模型中存在隐变量，就要用EM算法做参数估计。

个人认为，理解EM算法背后的idea，远比看懂它的数学推导重要。

idea会让你有一个直观的感受，从而明白算法的合理性，数学推导只是将这种合理性用更加严谨的语言表达出来而已。

打个比方，一个梨很甜，用数学的语言可以表述为糖分含量90%，但只有亲自咬一口，你才能真正感觉到这个梨有多甜，也才能真正理解数学上的90%的糖分究竟是怎么样的。

隐藏变量

现在我们抹去每轮投掷时使用的硬币标记，如下：

硬币 结果 统计
Unknown 正正反正反 3正-2反
Unknown 反反正正反 2正-3反
Unknown 正反反反反 1正-4反
Unknown 正反反正正 3正-2反
Unknown 反正正反反 2正-3反

好了，现在我们的目标没变，还是估计P1和P2，要怎么做呢？

显然，此时我们多了一个隐变量z，可以把它认为是一个5维的向量（z1,z2,z3,z4,z5)，代表每次投掷时所使用的硬币，比如z1，就代表第一轮投掷时使用的硬币是1还是2。但是，这个变量z不知道，就无法去估计P1和P2，所以，我们必须先估计出z，然后才能进一步估计P1和P2。

但要估计z，我们又得知道P1和P2，这样我们才能用最大似然概率法则去估计z，这不是鸡生蛋和蛋生鸡的问题吗，如何破？

答案就是先随机初始化一个P1和P2，用它来估计z，然后基于z，还是按照最大似然概率法则去估计新的P1和P2，如果新的P1和P2和我们初始化的P1和P2一样，请问这说明了什么？（此处思考1分钟）

这说明我们初始化的P1和P2是一个相当靠谱的估计！

就是说，我们初始化的P1和P2，按照最大似然概率就可以估计出z，然后基于z，按照最大似然概率可以反过来估计出P1和P2，当与我们初始化的P1和P2一样时，说明是P1和P2很有可能就是真实的值。

这里面包含了两个交互的最大似然估计。

如果新估计出来的P1和P2和我们初始化的值差别很大，怎么办呢？就是继续用新的P1和P2迭代，直至收敛。

ps: 我们先预估一个值，如果我们用最大似然概率计算，发现符合说明我们就猜对了。如果不对，迭代到收敛。

EM 初级版

这就是下面的EM初级版。

E-假设阶段

我们不妨这样，先随便给P1和P2赋一个值，比如：

P1 = 0.2 P2 = 0.7

然后，我们看看第一轮抛掷最可能是哪个硬币。

如果是硬币1，得出3正2反的概率为 0.2*0.2*0.2*0.8*0.8 = 0.00512

如果是硬币2，得出3正2反的概率为 0.7*0.7*0.7*0.3*0.3 = 0.03087

然后依次求出其他4轮中的相应概率。

做成表格如下：

轮数 若是硬币1 若是硬币2
1 0.00512 0.03087
2 0.02048 0.01323
3 0.08192 0.00567
4 0.00512 0.03087
5 0.02048 0.01323

M-ELM 重新计算概率阶段

按照最大似然法则：

第1轮中最有可能的是硬币2

第2轮中最有可能的是硬币1

第3轮中最有可能的是硬币1

第4轮中最有可能的是硬币2

第5轮中最有可能的是硬币1

我们就把上面的值作为z的估计值。

然后按照最大似然概率法则来估计新的P1和P2。

P1 = （2+1+2）/ 15 = 0.33
P2 =（3+3）/ 10 = 0.6

设想我们是全知的神，知道每轮抛掷时的硬币就是如本文第001部分标示的那样，那么，P1和P2的最大似然估计就是0.4和0.5（下文中将这两个值称为P1和P2的真实值）。

那么对比下我们初始化的P1和P2和新估计出的P1和P2：

初始化的P1  0.2
估计出的P1	0.33
真实的P1	0.4
初始化的P2	0.7 
估计出的P2	0.6
真实的P2    0.5

看到没？我们估计的P1和P2相比于它们的初始值，更接近它们的真实值了！

可以期待，我们继续按照上面的思路，用估计出的P1和P2再来估计z，再用z来估计新的P1和P2，反复迭代下去，就可以最终得到P1 = 0.4，P2=0.5，此时无论怎样迭代，P1和P2的值都会保持0.4和0.5不变，于是乎，我们就找到了P1和P2的最大似然估计。

反思

这里有两个问题：

1、新估计出的P1和P2一定会更接近真实的P1和P2？

答案是：没错，一定会更接近真实的P1和P2，数学可以证明，参见 EM 完整推导过程。

2、迭代一定会收敛到真实的P1和P2吗？

答案是：不一定，取决于P1和P2的初始化值，上面我们之所以能收敛到P1和P2，是因为我们幸运地找到了好的初始化值。

EM进阶版

下面，我们思考下，上面的方法还有没有改进的余地？

我们是用最大似然概率法则估计出的z值，然后再用z值按照最大似然概率法则估计新的P1和P2。

也就是说，我们使用了一个最可能的z值，而不是所有可能的z值。

如果考虑所有可能的z值，对每一个z值都估计出一个新的P1和P2，将每一个z值概率大小作为权重，将所有新的P1和P2分别加权相加，这样的P1和P2应该会更好一些。

所有的z值有多少个呢？

显然，有2^5=32种，需要我们进行32次估值？？

期望简化

不需要，我们可以用期望来简化运算。

轮数 若是硬币1 若是硬币2
1 0.00512 0.03087
2 0.02048 0.01323
3 0.08192 0.00567
4 0.00512 0.03087
5 0.02048 0.01323

利用上面这个表，我们可以算出每轮抛掷中使用硬币1或者使用硬币2的概率。

比如第1轮，使用硬币1的概率是：

0.00512/(0.00512+0.03087)=0.14

使用硬币2的概率是 1-0.14=0.86

依次可以算出其他4轮的概率，如下：

轮数 z_i=硬币1 z_i=硬币2
1 0.14 0.86
2 0.61 0.39
3 0.94 0.06
4 0.14 0.86
5 0.61 0.39

上表中的右两列表示期望值。

看第一行，0.86表示，从期望的角度看，这轮抛掷使用硬币2的概率是0.86。

相比于前面的方法，我们按照最大似然概率，直接将第1轮估计为用的硬币2，此时的我们更加谨慎，我们只说，有0.14的概率是硬币1，有0.86的概率是硬币2，不再是非此即彼。

这样我们在估计P1或者P2时，就可以用上全部的数据，而不是部分的数据，显然这样会更好一些。

这一步，我们实际上是估计出了z的概率分布，这步被称作E步。

结合下表：

硬币 结果 统计
Unknown 正正反正反 3正-2反
Unknown 反反正正反 2正-3反
Unknown 正反反反反 1正-4反
Unknown 正反反正正 3正-2反
Unknown 反正正反反 2正-3反

我们按照期望最大似然概率的法则来估计新的P1和P2：

以P1估计为例，第1轮的3正2反相当于

0.14*3=0.42正
0.14*2=0.28反

依次算出其他四轮，列表如下：

轮数 正面 反面
1 0.42 0.28
2 1.22 1.83
3 0.94 3.76
4 0.42 0.28
5 1.22 1.83
总计 4.22 7.98

P1=4.22/(4.22+7.98)=0.35

可以看到，改变了z值的估计方法后，新估计出的P1要更加接近0.4。

原因就是我们使用了所有抛掷的数据，而不是之前只使用了部分的数据。

这步中，我们根据E步中求出的z的概率分布，依据最大似然概率法则去估计P1和P2，被称作M步。

拓展阅读

贝叶斯定理

HMM

卡尔曼滤波

参考资料

《统计学习方法》，李航

《机器学习》，Tom M.Mitchell

机器学习（十九）EM:期望最大算法

如何感性地理解EM算法？

知乎-机器学习十大算法之一： EM 算法 (从极大似然估计到EM算法)

EM最大期望算法