Expectation-Maximization Algorithm
Zhao Zhao
  2022-05-07 11:24:06 2022-05-07 11:24    

如何通俗理解EM算法

一. 极大似然

最大期望算法（Expectation-maximization algorithm，又译为期望最大化算法），是在概率模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐性变量。

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

  1. 第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；
  2. 第二步是最大化（M），最大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行，
1.1 似然函数

概率是已知模型和参数，推数据。统计是已知数据，推模型和参数。在数理统计学中，似然函数是一种关于统计模型中的参数的函数，表示模型参数中的似然性。“似然性”与“或然性”或“概率”意思相近，都是指某种事件发生的可能性。

多数情况下我们是根据已知条件来推算结果，而最大似然估计是已经知道了结果，然后寻求使该结果出现的可能性最大的条件，以此作为估计值。 看到没，概率是根据条件推测结果，而似然则是根据结果反推条件。在这种意义上，似然函数可以理解为条件概率的逆反。

假定已知某个参数B时，推测事件A会发生的概率写作 通过贝叶斯公式，可以得出 现在我们反过来：事件A已经发生了，请通过似然函数 估计参数B的可能性。

1.2 似然函数举例：已知样本，求参数

假定我们需要统计10万学员中男生女生的身高分布，怎么统计呢？考虑到10万的数量巨大，所以不可能一个一个的去统计。对的，随机抽样，从10万学员中随机抽取100个男生，100个女生，然后依次统计他们各自的身高。

对于这个问题，我们通过数学建模抽象整理下

  1. 首先我们从10万学员中抽取到100个男生/女生的身高，组成样本集，，其中表示抽到的第个人的身高，等于100，表示抽到的样本个数。
  2. 假定男生的身高服从正态分布, 女生的身高则服从另一个正态分布。
  3. 但是这两个分布的均值和方差都不知道, 设为未知参数。
  4. 现在需要用极大似然法（MLE），通过这100个男生或100个女生的身高结果，即样本集来估计两个正态分布的未知参数，问题定义相当于已知，求，换言之就是求。

因为这些男生（的身高）是服从同一个高斯分布的。那么抽到男生A（的身高）的概率是，抽到男生B的概率是，考虑到他们是独立的，所以同时抽到男生A和男生B的概率是.

同理，我从分布是的总体样本中同时抽到这100个男生样本的概率，也就是样本集中100个样本的联合概率（即它们各自概率的乘积），用下式表示：

有的文章中会用这个表示，有的文章会用

这个概率反映了，在概率密度函数的参数是θ时，得到X这组样本的概率。因为这里X是已知的，也就是说我抽取到的这100个人的身高可以测出来，也就是已知的了。而θ是未知了，则上面这个公式只有θ是未知数，所以它是θ的函数。这个函数放映的是在不同的参数θ取值下，取得当前这个样本集的可能性，因此称为参数θ相对于样本集X的似然函数（likehood function）

在那么多男学员中，我一抽就抽到这100个男生，而不是其他人，那说明在整个学校中，这100个人（的身高）出现的概率最大啊，这个概率就是上面这个似然函数，怎么做到的呢？换言之，怎样的能让)最大？

1.3 极大似然即最大可能

假定我们找到一个参数，能使似然函数最大（也就是说抽到这100个男生的身高概率最大），则应该是“最可能”的参数值，相当于的极大似然估计量。记为： 这里的是连乘的，为了便于分析，我们可以定义对数似然函数，将其变成连加的 极大似然估计，只是一种概率论在统计学的应用，它是参数估计的方法之一。说的是已知某个随机样本满足某种概率分布，但是其中具体的参数不清楚，参数估计就是通过若干次试验，观察其结果，利用结果推出参数的大概值。最大似然估计是建立在这样的思想上：已知某个参数能使这个样本出现的概率最大，我们当然不会再去选择其他小概率的样本，所以干脆就把这个参数作为估计的真实值。

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

（1）写出似然函数；

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

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

（4）解似然方程，得到的参数即为所求；

二. EM算法

2.1 极大似然估计的复杂情形

极大似然估计的目标是求解实现结果的最佳参数，但极大似然估计需要面临的概率分布只有一个或者知道结果是通过哪个概率分布实现的，只不过你不知道这个概率分布的参数。但现在我们让情况复杂一点，比如这100个男生和100个女生混在一起了。我们拥有200个人的身高数据，却不知道这200个人每一个是男生还是女生，此时的男女性别就像一个隐变量。而EM算法就是为了解决“极大似然估计”这种更复杂而存在的。

2.2 EM算法中的隐变量

一般的用Y表示观测到的随机变量的数据，Z表示隐随机变量的数据(因为我们观测不到结果是从哪个概率分布中得出的，所以将这个叫做隐变量)。于是Y和Z连在一起被称为完全数据，仅Y一个被称为不完全数据。

这时有没有发现EM算法面临的问题主要就是：有个隐变量数据Z。而如果Z已知的话，那问题就可用极大似然估计求解了。 于是乎，怎么把Z变成已知的？

2.3 抛硬币

两枚硬币A和B，假定随机抛掷后正面朝上概率分别为PA，PB。为了估计这两个硬币朝上的概率，咱们轮流抛硬币A和B，每一轮都连续抛5次，总共5轮

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

硬币A被抛了15次，在第一轮、第三轮、第五轮分别出现了3次正、1次正、2次正，所以很容易估计出PA，类似的，PB也很容易计算出来，如下： 问题来了，如果我们不知道抛的硬币是A还是B呢（即硬币种类是隐变量），然后再轮流抛五轮，得到如下结果：

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

我们不妨这样，先随便给PA和PB赋一个值，比如：硬币A正面朝上的概率PA = 0.2，硬币B正面朝上的概率PB = 0.7

然后，我们看看第一轮抛掷最可能是哪个硬币。 如果是硬币A，得出3正2反的概率为 0.2*0.2*0.2*0.8*0.8 = 0.00512 如果是硬币B，得出3正2反的概率为0.7*0.7*0.7*0.3*0.3=0.03087

然后依次求出其他4轮中的相应概率。做成表格如下（标粗表示其概率更大）：

轮数 若是硬币A 若是硬币B
1 0.00512，即0.2 0.2 0.2 0.8 0.8，3正-2反 0.03087，3正-2反
2 0.02048，即0.2 0.2 0.8 0.8 0.8，2正-3反 0.01323，2正-3反
3 0.08192，即0.2 0.8 0.8 0.8 0.8，1正-4反 0.00567，1正-4反
4 0.00512，即0.2 0.2 0.2 0.8 0.8，3正-2反 0.03087，3正-2反
5 0.02048，即0.2 0.2 0.8 0.8 0.8，2正-3反 0.01323，2正-3反

按照最大似然法则： 第1轮中最有可能的是硬币B 第2轮中最有可能的是硬币A 第3轮中最有可能的是硬币A 第4轮中最有可能的是硬币B 第5轮中最有可能的是硬币A

我们就把概率更大，即更可能是A的，即第2轮、第3轮、第5轮出现正的次数2、1、2相加，除以A被抛的总次数15（A抛了三轮，每轮5次），作为z的估计值，B的计算方法类似。然后我们便可以按照最大似然概率法则来估计新的PA和PB。 那么对比下我们初始化的PA和PB和新估计出的PA和PB：

始化的PA 估计出的PA 真实的PA 初始化的PB 估计出的PB 真实的PB
0.2 0.33 0.4 0.7 0.6 0.5

看到没？我们估计的PA和PB相比于它们的初始值，更接近它们的真实值了！就这样，不断迭代 不断接近真实值，这就是EM算法的奇妙之处。

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

三. EM算法的公式推导

3.1 EM算法的目标函数

假设我们有一个样本集，包含个独立的样本，现在我们想找到每个样本隐含的类别，能使得最大。的极大似然估计如下： 其中第二个等式是对每个样例的每个可能类别求联合分布概率和.

对于参数估计，我们本质上还是想获得一个使似然函数最大化的那个参数，现在与极大似然不同的只是似然函数式中多了一个未知的变量，也就是说我们的目标是找到适合的和，以让最大. 我们把分子分母同乘以一个相等的函数（即隐变量的概率分布，其概率之和等于1, ).

3.2 Jensen不等式
  1. 若是区间上的下凸函数， 则对于任意, 有不等式

当且仅当时等号成立。

  1. 其加权形式为：

    是区间上的下凸函数， 则对于任意，且, 有 当且仅当时等号成立。

在概率论中，如果把看成取值为 的离散变量的概率分布，那么公式（11）可以写为 为凸函数为凹函数

期望公式中的Lazy Statistician规则：

设是随机变量的函数， （是连续函数），那么

  1. 是离散型随机变量，它的分布律为,若绝对收敛，则有

  2. 是连续型随机变量，它的概率密度为, 若绝对收敛，则有

那么对于 我们有 再根据凹函数时的Jensen不等式，我们有 公式（9）可以看作是对求了下界。假设已经给定，那么取决于 和 . 我们可以通过调整这两个概率使(9)式下界不断上升来逼近 的真实值。那么如何算是调整好呢？当不等式变成等式时，说明我们调整后的概率能够等价于了。按照这个思路，我们要找到等式成立的条件。

在Jensen不等式中说到，当自变量X是常数的时候，等式成立。换言之，为了让（9）式取等号，我们需要： 对该式做个变换，并对所有的求和，得到 由上面两个式子，我们可以得到 至此，我们推出了在固定参数后，使下界拉升的的计算公式就是条件概率。解决了如何选择的问题。这一步就是E步，建立的下界。

接下来的M步，就是在给定后，调整，去极大化的下界，毕竟在固定下界还可以调整的更大。

3.3 EM算法的流程

​ 我们来总结下，期望最大EM算法是一种从不完全数据或有数据丢失的数据集（存在隐含变量）中求解概率模型参数的最大似然估计方法。

输入： 观察到的数据,联合分布, 条件分布, 最大迭代次数。

算法步骤：

  1. 随机初始化分布参数

  2. 开始EM算法迭代：

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

    • M步：极大化, 得到

    • 如果已经收敛，则算法结束。否则继续进行E步和M步进行迭代。

输出： 模型参数.

  1. 上面介绍的传统EM算法对初始值敏感，聚类结果随不同的初始值而波动较大。总的来说，EM算法收敛的优劣很大程度上取决于其初始参数。
  2. EM算法可以保证收敛到一个稳定点，即EM算法是一定收敛的。
  3. EM算法可以保证收敛到一个稳定点，但是却不能保证收敛到全局的极大值点，因此它是局部最优的算法，当然，如果我们的优化目标是凸的，则EM算法可以保证收敛到全局最大值，这点和梯度下降法这样的迭代算法相同。
3.4 收敛性证明

假定和是EM第次和次迭代后的结果，如果证明, 也就是说极大似然估计单调增加，那么最终我们会到达最大似然估计的最大值。

选定后，我们得到E步： 这一步保证了在给定时，Jensen不等式中的等式成立，也就是 然后进行M步，固定, 并将求导后，得到, 因此一下式子成立 第一步利用了Jensen不等式；第二步成立是因为 是下界函数的极大值点；第三步是Jensen不等式取等号。

https://blog.csdn.net/v_july_v/article/details/81708386

https://blog.csdn.net/u010834867/article/details/90762296

https://blog.csdn.net/u011508640/article/details/72815981

https://www.cnblogs.com/peizhe123/p/4805690.html