2018-05-27

EM算法原理与推导

EM算法

Jensen不等式

对于凸函数，有$E[f(X)]\ge f(E[X])$。如果$f$是一个严格凸函数，那么只有当$X=E[x]$成立的时候，Jensen不等式中的等号才会满足。

向上图演示的一样，如果函数是严格凸函数，那么想要满足Jensen不等式的话，只能是$X$是一个定值，从而$X=E[x]$。如果$X$可能以某分布取多个值的话，任意两个函数值之间的连线都会大于这一区间内的函数值，就好像将一个木棍放入碗里，木棍和碗之间一定存在空隙。而为什么要求函数值严格凸的，我们可以这样考虑，假设碗内有一块平面，那么木棍如果落入该区间，就会和该碗的平面完全贴合。

对应的，如果$f$是严格凹函数，那么Jensen不等式就是$E[f(X)]\le f(E[X])$，这也是我们要处理的情况，因为我们要用Jensen不等式求解对数似然的极大值。

EM解决的问题

假设我们有数据集$$$X={x_{(1)},x_{(2)},…,x_{(m)}}$$$，我们想利用生成式模型建模$$$P(x;\theta)$$$。
在之前的文章高斯判别模型（GDA）原理与推导中，x就是数据向量，参数$$$\theta$$$就是子高斯模型的均值和协方差，然后利用贝叶斯公式进行分类的目的，即$$$P(y=i|x)=\frac{P(x,y=i)}{P(x)}=\frac{P(x,y=i)}{\sum_yP(x,y)}$$$。
然而，GDA是监督学习算法，我们可以观测到数据标签，从而利用不同标签的数据，单独对单个模型的最优参数进行计算。然而这里我们的数据集没有提供标签，但是并不是说标签不存在。我们依然认为数据来自于多个分布，只不过我们无法观测到数据被哪一个子分布生成，因此不能直接利用公式直接计算解析解。EM算法就是用来处理这种具有“隐标签”的混合模型问题。

$$ l(\theta)=\sum_{i=1}^mlogP(x^{(i)};\theta)\qquad(1)$$
$$ l(\theta)=\sum_{i=1}^mlog\sum_zP(x^{(i)},z^{(i)};\theta)\quad(2)$$
$$ l(\theta)=\sum_{i=1}^mlog\sum_zP(x^{(i)};z^{(i)},\theta)P(z^{(i)};\theta)\qquad(2.1)
$$

如上面的公式所表示的，我们处理无监督学习任务时，假设没有隐标签的存在，直接用（1）公式就可以进行MLE的计算，然而如果有隐标签$$$z$$$的存在，就会使得对数极大似然变成(2)的形式，无法公式直接推导解析式。这里的求和来自于边缘分布的计算。正是因为在对数函数内的求和，造成了计算上的困难。

一个关键的现象是，对于潜在变量的求和位于对数的内部。即使联合概率分布属于指数族分布，由于这个求和式的存在，边缘概率分布通常也不是指数族分布。…… 这使得最大似然解没有解析解。

现在无能直接观测到隐标签的话，只能通过渐进迭代的方式去寻找似然函数极大值，简而言之，EM算法是通过一个构造一个似然函数比较紧下界，然后求解下界极大值，然后重新构造下界，然后再求解下界极大值的方式去迭代的。后面会仔细说明这一点。

$$ l(\theta)=\sum_ilogP(x^{(i)};\theta) \qquad(1)$$
$$ l(\theta)=\sum_ilog\sum_{z^{(i)}}Q_i(z^{(i)})\frac{P(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} \qquad(3)$$
$$ l(\theta)=\sum_ilogE_{z^{(i)}\sim Q_i}\Big[\frac{P(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\Big] \qquad(4)$$
$$ l(\theta)\ge\sum_iE_{z^{(i)}\sim Q_i}\Big[log\frac{P(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\Big]\qquad(5)$$
$$ l(\theta)\ge\sum_i\sum_{z^{(i)}}Q_i(z^{(i)})log\frac{P(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} \qquad(6)$$

我研一第一次看见这一串推导的时候，记得还是下午的时候，和现在季节差不多，也是春夏之交。差不多自己在单人间宿舍看了好久，午后斜阳照在我懵逼的我脸上，我脑海中只有一个念头：“这都是些什么操作？”，去吃晚饭的路上还是浑浑噩噩的。然后晚上吃完饭自己在操场溜达好一会，决定说服自己假装看明白了。然后研二的时候，复习线性回归和最小二乘部分的时候，搞明白了极大似然估计，然后查找资料的时候又看见了EM算法这个词，于是回想起了被其支配的恐惧，直到最近，由于考虑项目方案，复习了HMM，才重新看了一遍EM算法，这次觉得真心是差不多看明白了，然后心里只有一个念头：“怎么能有人想出这种操作？”其实当时看不明白，我觉得有一个原因是模式识别的老师把这个EM用交叉熵解释，我就是真心懵逼了，要是当时塌下心好好看Andrew的讲义，应该还是可以看明白的。闲话不多说了，解释一下上面的推导。

（3）是从式子中提出一个恒正因子$$$Q$$$，并且$$$Q$$$一定小于等于1，这步就是这么要求$$$Q$$$的，只要满足条件，$$$Q$$$其实可以有无数种情况，（这个$$$Q$$$实际上就决定的对数似然下界的形状）。至于为什么这么做，实际上就是为了提出一个和$$$z$$$相关的分布，然后往期望上面靠，靠到了期望，就可以用Jensen不等式，后面的推导也是围绕这个目的。用这种方式考虑，(4)步中$$$Q$$$是$$$z$$$的分布函数，剩下的部分固定$$$\theta和x$$$的话，就是一个之和$$$z$$$有关的函数，所以表示为期望的形式。(5)中就是利用Jensen不等式的一步，$$$log$$$就是Jensen不等式中的函数$$$f$$$，并且log函数的确是一个严格凹函数。最后一步将期望的形式展开，得到（6）。

那么上面这一堆通过对比（3）（6）可以发现，实际上就是把log函数放到里面了，然后等式转变为不等式。我的问题是为啥这么做是好的？

在前面导出问题的时候，我们已经发现了，真正难住我们的，是我们不知道数据的隐标签是啥，这也就使得不能为拥有不同标签的数据单独建模。现在经过上述变换，尽管我们依然不知道数据的隐标签是啥，但是我们可以计算隐标签的后验分布了，即$$$Q_i(z^{(i)})$$$其实就是$$$P(z^{(i)}|x^{(i)};\theta)$$$，这个后验分布，在EM算法中被称为责任(responsibility)，即哪一个分布对此数据负责。本来我们是不能直接求混合模型的对数似然的，但是确定了责任后我们就可以求解(2.1)式的极大似然估计了。那么，问题来了，为什么$$$Q_i(z^{(i)})$$$其实就是$$$P(z^{(i)}|x^{(i)};\theta)$$$？

前面提到直到满足分布条件的Q都可以满足Jensen不等式，不过我们想找到好的那个特殊的一个Q，naive的想法就是让Q使得Jensen不等式成立，根据开始提到的，函数内的取值必须是常数时，Jensen不等式才满足等号，也就是说$$$\frac{P(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}$$$需要是常数。（后面也会证明，这也是保证EM单调收敛性的条件。）
即，
$$ \frac{P(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}=c \qquad(7)$$
$$ Q_i(z^{(i)})\propto P(x^{(i)},z^{(i)};\theta) \qquad(7.1)$$
$$ Q_i(z^{(i)})=\frac{P(x^{(i)},z^{(i)};\theta)}{\sum_zP(x^{(i)},z;\theta)} \qquad(8)$$
$$ Q_i(z^{(i)})=\frac{P(x^{(i)},z^{(i)};\theta)}{P(x^{(i)};\theta)} \qquad(8.1)$$
$$ Q_i(z^{(i)})=P(z^{(i)}|x^{(i)};\theta) \qquad(8.2)$$

（7）在前面已经解释了，然而这个常数$$$c$$$是多少不是限制$$$Q$$$的条件，只要满足$$$Q$$$和联合概率是正比关系即可。而Q也是概率分布，需要满足求和为一的要求，这也是真正限制$$$Q$$$的条件，因此得到（8）。后面的（8.1）和（8.2）就是概率论的基础操作了。因此我们得到结论，Q实际上就是给定$$$x$$$和当前$$$\theta$$$条件下，隐标签的后验概率。然后就可以简单的求解MLE，转化后的式子通常是凸的，并且存在解析解。

《统计机器学习》书上的证明更加简单粗暴，直接就把后验概率提出来。我直接把原文贴在下面。仅做一个参考，这篇文章主要还是跟着CS229的讲义来走。

摘自《统计机器学习》

所以EM算法整理如下：首先随意对参数设定一个值。E-Step就是计算当前参数下，x对应的z的后验概率分布。然后M-Step就是假设已知当前z的后验分布，求解模型参数$\theta$的MLE。用公示表示的话：
$$ \theta := argmax_\theta\sum_i\sum_{z^{(i)}}Q_i(z^{(i)})log\frac{P(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} \qquad(9)$$

然而没感觉这个式子好算啊？真的可以算吗？其实我在推导的时候，甚至写到这里的时候也是有这个疑问的，但是这个问题我们还是需要真正的去解决一个问题才能彻底明白，因此结合GMM来看想必是极好的吧。

收敛性证明

如果$$$\theta^{(i)}$$$和$$$\theta^{(i+1)}$$$是EM算法两轮连续迭代的参数，那么我们可以证明$$$l(\theta^{(t)})<l(\theta^{(t+1)})$$$，即EM算法会使得似然单调增加。
令：
$$ J(Q,\theta)=\sum_i\sum_{z^{(i)}}Q_i(z^{(i)})log\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} \qquad(10)$$
且（6）易知：
$$l(\theta) \ge J(Q,\theta)$$

在E步，由于我们保证了Jensen不等式的等号成立，因此E步更新Q之后，$$$ l(\theta^{(t)})=J(Q^{(t+1)},\theta^{(t)}) $$$。而由于M步通过（9）的方法更新$$$\theta$$$，因此，$$$ J(Q^{(t+1)},\theta^{(t+1)}) \ge J(Q^{(t+1)},\theta^{(t)})$$$，下一回合的E步，再次更新Q，使得$$$ l(\theta^{(t+1)})=J(Q^{(t+2)},\theta^{(t+1)})$$$，因此$$$l(\theta^{(t+1)}) \ge l(\theta^{(t)})$$$

要走的路还很长

参考文献中提到认识EM算法有九重境界：

EM 就是 E + M

EM 是一种局部下限构造

K-Means是一种Hard EM算法

从EM 到广义EM

广义EM的一个特例是VBEM

广义EM的另一个特例是WS算法

广义EM的再一个特例是Gibbs抽样算法

WS算法是VAE和GAN组合的简化版

KL距离的统一

我大概看了一下…前三层可以理解，第四层摸到了边，后面的嘛……

数据缺失问题

可以说EM算法天生就是用来解决缺失数据的问题的，将第3节的隐变量z看成是数据中缺失的数据即可。
在完全数据X(无缺失数据)下，已知模型为f(x|θ)，求数据满足何种模型？这可以由第1节的极大似然估计求解；如果采样数据存在部分未知Z，预测这些含未知的数据的数据符何什么模型？这就可借用第3节的EM算法了，先随机假设θ，迭代求解，最后求知f(x|θ)，当然也就可求出z。

后续

在本来以为本文要结束的时候，看到了参考资料中的567几篇文章，仿佛给我打开了新视角。无监督学习我一直很感兴趣但是也仅限于感兴趣而已，这次以HMM与CRF入手，“深入”理解了EM、GDA、K-means、GMM等知识点，觉得这应该是以后继续探索的一个很好的入手点。
期待后面来填坑。

参考：