机器学习之EM算法

前言

EM算法不是模型，更确切的说是一种解决问题的思路。这个思路在机器学习中的场景是什么呢？

举周志华《机器学习》的例子吧，说的是如何根据西瓜的一大堆特征，来判断这个西瓜是不是好瓜。当样本特征都是完整的时候，我们可以用各种模型来推导。但是当样本特征不完整的时候，比如说西瓜的一个特征根蒂已经脱落，无法获取它是“蜷缩”还是“硬挺”，这时候根蒂这个特征就变成一个隐变量了，事实上实际特征缺失是比较场景的，这时候如何进行参数估计呢？EM算法是一种思路。

最大似然估计

EM其实是最大似然估计的拓展。最大似然估计是通过已知样本来反推最可能样本参数的一种方法。一个简单的例子：

有一枚特殊的硬币，它抛的正反面概率未知的，但是在一次实验中抛了4次，得到“正正反正”。那么请问这枚硬币抛一次得到正面的概率最可能是多大？

显然是3/4，为什么呢？因为只有在3/4的时候，"抛4次得到正正反正”这个事件发生的概率最大。简单算下：

当为3/4时，抛4次得到正正反正的概率为，P(3/4)=3/4*3/4*1/4*3/4=27/256。

其他概率比如说1/2，抛4次得到正正反正的概率为，P(1/2)=1/2*1/2*1/2*1/2=16/256，都会小于27/256。

这就是说这枚硬币抛一次得到的正面的概率最有可能是3/4。

只有1枚硬币的情况下，我们可以通过似然函数（L(p) = p*p*(1-p)*p）对求p偏导的方式来求解（这部分很简单，不继续了）。

EM算法

直观理解

小明的妈妈给了她一袋樱桃，要他平均分给妹妹吃。如果有一杆秤，这些都好办，如果没有的话，小明通常这么做。

1）拿两个袋子先随便分开装

2）左右手一边提一个掂量一下

3）把感觉重的一边放一点到轻的一边

4）再次掂量，直到感觉差不多了

哈哈，这不就我们一直在做的事吗。。。

数字解释

回到最大似然估计的例子，如果有两枚不同的硬币且未知抛的是哪个硬币，问题就不一样了。

引用附件paper的一个例子 - 最大似然估计解决问题

如图，先看两个硬币都是已知的情况，我们有这么一些实验，怎么推算硬币A和B的正面概率？

很容易跟上面一章一样，可以求得A正面的概率为0.8，B正面的概率为0.45.

EM算法解决问题

如果问题变成这样呢？已知有两枚不同的硬币A和B，经过一些试验后得出以下样本，只知道样本，但不知道是哪个硬币抛的，这时候怎么求两枚硬币正面的概率？

问题现在其实有两个变量：一、五次实验中每次使用的硬币的可能性。二、每一枚硬币正面向上的概率。这两个变量，我们如果知道其中任意一个，就能反推出另外一个。

EM算法的思想很简单

先假设固定一个变量，再反推另一个的可能性分布，再以这个可能性分布反馈给固定的变量，再进行迭代。主要步骤有：

1、假设θ(A) = 0.6, θ(B) = 0.5

2、E步 - 根据这个概率，我们反推每次实验的概率，得出以下结果

以第一次实验为例，怎么得出0.45和0.55的呢？

假设第一次实验为A，那么其出现这种结果的概率为

P(A) = 0.6*0.4*0.4*0.4*0.6*0.6*0.4*0.6*0.4*0.6=0.000804225024

假设第一次实验为B，那么其出现这种结果的概率为

P(B) = 0.5*0.5*0.5*0.5*0.5*0.5*0.5*0.5*0.5*0.5=0.0009765625

那么为硬币A的比重是P(A)/(P(A)+P(B)) = 0.000804225024/(0.000804225024+0.0009765625) = 0.45。

其他情况亦是如此。

3、计算每个硬币正反面概率分布

还是以第一个实验为例，其中0.45的概率为A，0.55的概率为B。这时候，如果我们简单粗暴的把第一次实验当作B，其他的情况也这么处理的话，我们也能得到一组比初值0.6和0.5更精确一点的数据。但是EM算法采用的是求期望的方式，往往会比简单粗暴的方式更有效率。

这里面做的是，既然A是0.45，B是0.55，那么你们两根据概率把实验结果分一下就好了。

这时候A就拿到4.5个数据，B拿到5.5个。按照正反1：1的结果，进一步得到：

A：2.2正 2.2反 B：2.8正 2.8反。

对每个以此做一遍类似的，我们得到最终的结果。

A：21.3正 8.6反 B：11.7正 8.4反

4、M步 - 最大似然估计计算概率，反馈迭代

步骤3中，我们得到一组可能的数据。我们利用最大似然估计，来计算基于此A和B的概率，得到：

大家有没有发现，这样得到的概率会比真实的概率要精确些。然后我们继续把这个概率迭代回1中，最终结果会趋于一个稳定的数据。

可能会有两个疑问：

1、新估计出的θ(A) 和θ(B) 一定会更接近真实的θ(A) 和θ(B) ？

答案是一定的，这里可以用Jensen不等式来证明，这里就不细讲了！

2、θ(A) 和θ(B) 一定会收敛于真实值吗？

答案是不一定，有可能会陷入局部最优。

参考资料

附件论文 what is EM