EM算法是什么？EM算法实现流程

EM算法也称期望最大化(Expectation-Maximum,简称EM)算法。 它是一个基础算法，是很多机器学习领域算法的基础，比如隐式马尔科夫算法(HMM)等等。 EM算法是一种迭代优化策略，由于它的计算方法中每一次迭代都分两步， 其中一个为期望步(E步)， 另一个为极大步(M步)， 所以算法被称为EM算法(Expectation-Maximization Algorithm)。

EM算法受到缺失思想影响，最初是为了解决数据缺失情况下的参数估计问题，其算法基础和收敛有效性等问题在Dempster、Laird和Rubin三人于1977年所做的文章《Maximum likelihood from incomplete data via the EM algorithm》中给出了详细的阐述。其基本思想是：

  • 首先根据已经给出的观测数据，估计出模型参数的值;

  • 然后再依据上一步估计出的参数值估计缺失数据的值，再根据估计出的缺失数据加上之前已经观测到的数据重新再对参数值进行估计;

  • 然后反复迭代，直至最后收敛，迭代结束。

EM算法计算流程：

EM算法一个超级简单的案例

假设现在有两枚硬币1和2，,随机抛掷后正面朝上概率分别为P1，P2。为了估计这两个概率，做实验，每次取1枚硬币，连掷5下，记录下结果，如下：

可以很容易地估计出P1和P2，如下：

P1 = (3+1+2)/ 15 = 0.4 P2= (2+3)/10 = 0.5

到这里，一切似乎很美好，下面我们加大难度。 

加入隐变量z后的求解，还是上面的问题，现在我们抹去每轮投掷时使用的硬币标记，如下：

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

显然，此时我们多了一个隐变量z，可以把它认为是一个5维的向量(z1,z2,z3,z4,z5)，代表每次投掷时所使用的硬币，

比如z1，就代表第一轮投掷时使用的硬币是1还是2。但是，这个变量z不知道，就无法去估计P1和P2，所以，我们必须先估计出z，然后才能进一步估计P1和P2。

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

EM初级版

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

  • P1 = 0.2

  • P2 = 0.7

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

如果是硬币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

第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和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，数学可以证明，但这超出了本⽂的主题，请参阅其他书籍或文章。

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 = 32种，需要我们进行32次估值??

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

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

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

  • 0.00512/(0.00512 + 0.03087) = 0.14

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

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

上表中的右两列表示期望值。看第一行，0.86表示，从期望的⻆度看，这轮抛掷使用硬币2的概率是0.86。相比于前面的方法，我们按照最大似然概率，直接将第1轮估计为用的硬币2，此时的我们更加谨慎，我们只说，有0.14的概率是硬 币1，有0.86的概率是硬币2，不再是非此即彼。这样我们在估计P1或者P2时，就可以用上全部的数据，而不是部分的数据，显然这样会更好一些。

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

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

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

0.14*3=0.42正

0.14*2=0.28反

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

P1=4.22/(4.22+7.98)=0.35

可以看到，改变了z值的估计方法后，新估计出的P1要更加接近0.4。原因就是我们使用了所有抛掷的数据，而不是之前只使用了部分的数据。

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