理解EM算法

2024-11-28

---

$EM$算法是1977年发明的，但是到今天，想要透彻理解并不容易。到底什么是隐变量？$Q$函数到底是怎么回事？作者怎么想到$Jessen$不等式来证明的？有没有一种简单直观的理解方式？本文试图解答。

在$EM$中，隐变量是一个比较核心又难以理解的概念。

隐变量

考虑我们有一些身高数据，$170,161,172,173,164,175,176,167,\dots ,179,180$。 此时不能简单假设这些身高数据来自某个正态分布。因为男生和女生身高数据，应该来自两个不同的正态分布。 所以我们这些数据实际上是来自两个正态分布的混合。

请仔细体会，我们现在从一个身高的数据分布中进行抽样，得到了上面的数据。我们知道每条具体抽样的身高数据，要么来自男生，要么来自女生。 这个“身高的数据分布”背后实际上对应着一个男生女生分布。怎么理解这里的对应？我们可以理解，每次抽样一条身高数据，同时也是从男生女生分布中抽样了一个样本。

一条身高数据样本<—>一个男生女生分布中的样本

唯一的不同，作为身高数据样本，我们是可以看到样本的具体值的，也就是上面的身高数字，但是当将该抽样作为男生女生分布中的样本时，我们是看不到样本的具体值的，即不知道该样本到底是来自男生还是女生，这就是“隐”的含义。

我们记身高数据分布为$P(x)$，男生女生分布为$P(z)$。 将$x$称为观测变量，$z$称为隐变量。

观测变量可以由隐变量生成，即：

$$\begin{array}{}\text{(1)}& P(x)=\sum _{z}P(x,z)=\sum _{z}P(z)P(x|z)\end{array}$$

理解这个公式，我们可以使用上面男生女生身高的例子。假设男生身高分布为$P(x|z=boy)$，女生身高分布为$P(x|z=girl)$。 那么，$P(x)$就是男生女生身高分布的混合。 即：

$$\begin{array}{}\text{(2)}& P(x)=P(z=boy)P(x|z=boy)+P(z=girl)P(x|z=girl)\end{array}$$

一般化，$P(x)$可以表示为：

$$\begin{array}{}\text{(3)}& P(x)=\sum _{z}P(z)P(x|z)\end{array}$$

对于连续变量，公式3可以写成：

$$\begin{array}{}\text{(4)}& P(x)={\int }_{z}P(z)P(x|z)dz\end{array}$$

上面的公式可以类比全概率公式来理解。为便于理解，下面都使用$z$的离散形式。

极大似然

有了上面含隐变量公式，我们可以用log-likelihood来求解模型参数。 我们知道log-likelihood的公式是：

$$\begin{array}{}\text{(5)}& \begin{array}{rl}\theta & =\arg \underset{\theta }{max}\sum _{i=1}^n\log P(x_i|\theta )\\ & =\arg \underset{\theta }{max}\sum _{i=1}^n\log \sum _{z}P(z)P(x_i|z)\\ & =\arg \underset{\theta }{max}\sum _{i=1}^n\log \sum _{z}P(z|\theta )P(x_i|z,\theta )\end{array}\end{array}$$

此时，需要注意一下，$\theta$是模型参数。具体是哪些参数呢？这点有必要先澄清一下。 以上面的男生女生例子，$\theta$包含了三部分参数：

1. 男生身高分布的参数，${\mu }_{boy}$和${\sigma }_{boy}$
2. 女生身高分布的参数，${\mu }_{girl}$和${\sigma }_{girl}$
3. 男生女生分布的参数，$P(z=boy)$和$P(z=girl)$

符号$P(z|\theta )$中的$\theta$特指的是属于$z$的那部分参数。笔者最初学习的时候，在这一点上困惑过。 log-likelihood外面的对$x$的求和，表示的是对所有样本的求和。将似然最大化，就是将每个样本的似然最大化。 为了简化推导，后面省略这个求和符号。

对上面的式子进行求梯度，得到：

$$\begin{array}{}\text{(6)}& \begin{array}{rl}\mathrm{\nabla }\theta & =\frac{\partial }{\partial \theta }\log \sum _{z}P(z|\theta )P(x|z,\theta )\\ & =\frac{\partial \sum _{z}P(z|\theta )P(x|z,\theta )}{\sum _{z}P(z|\theta )P(x|z,\theta )}\\ & =\frac{\sum _z(\partial P(z|\theta )P(x|z,\theta )+P(z|\theta )\partial P(x|z,\theta ))}{\sum _{z}P(z|\theta )P(x|z,\theta )}\end{array}\end{array}$$

有了梯度，就可以使用梯度上升法来优化模型参数。万事大吉？ 其实没那么容易。上面基于梯度求解，有个难以忽视的问题：

通过梯度进行更新，难以满足非负约束。

上面的公式中，有两个分布：

$$P(z|\theta )$$

以及

$$P(x|z,\theta )$$

因为是概率分布，需要是正数。仅通过梯度更新，很容易破坏这个约束。

至此，我们理解了隐变量，也尝试基于隐变量方案的最大似然求解，由于遇到了计算上的困难，导致无法求解。 EM算法就是来帮我们绕过这个困难的。

EM算法

EM算法的起手式，就是对上面的$logP(x|\theta )$进行新的分解。 如下所示：

$$\begin{array}{}\text{(7)}& \log P(x|\theta )=\log P(x,z|\theta )-\log P(z|x,\theta )\end{array}$$

其中：

$$\begin{array}{}\text{(8)}& P(x,z|\theta )=P(z|\theta )P(x|z,\theta )\end{array}$$ $$\begin{array}{}\text{(9)}& \begin{array}{rl}P(z|x,\theta )& =\frac{P(x,z|\theta )}{P(x|\theta )}\\ & =\frac{P(z|\theta )P(x|z,\theta )}{\sum _{z}P(z|\theta )P(x|z,\theta )}\end{array}\end{array}$$

这里我们细细体会一下这个分解和之前的分解的差别。之前的分解是：

$$\begin{array}{}\text{(10)}& \log P(x|\theta )=\log \sum _{z}P(z|\theta )P(x|z,\theta )\end{array}$$

现在我们继续推导公式7。 假设，我们在第n次迭代中，已经有了一个${\theta }^{(n)}$。我们可以对公式7进行变形：

$$\begin{array}{}\text{(11)}& \begin{array}{rl}\sum _{z}P(z|x,{\theta }^{(n)})\log P(x|\theta )& =\sum _{z}P(z|x,{\theta }^{(n)})\log \frac{P(x,z|\theta )}{P(z|x,{\theta }^{(n)})}\\ & -\sum _{z}P(z|x,{\theta }^{(n)})\log \frac{P(z|x,\theta )}{P(z|x,{\theta }^{(n)})}\end{array}\end{array}$$

这步变化，是最费解的，就是为什么要这么变形。我们暂且不管，继续推导一步，答案就会揭晓。

$$\begin{array}{}\text{(12)}& \log P(x|\theta )=\underset{ELBO}{\underbrace{E_{z\in P(z|x,{\theta }^{(n)})}\log \frac{P(x,z|\theta )}{P(z|x,{\theta }^{(n)})}}}+KL(P(z|x,{\theta }^{(n)}),P(z|x,\theta ))\end{array}$$

我们知道$KL$是一个非负的值。 所以上式中的$ELBO$，实际上是$\log P(x|\theta )$的一个下界。这也是$ELBO$名称的来源，Evidence Lower Bound。

那么，我们只要想办法最大化$ELBO$，就可以间接最大化$\log P(x|\theta )$。 $ELBO$中$\log$里面的分母与$\theta$无关，可以直接去掉。于是可以得到：

$$\begin{array}{}\text{(13)}& Q(\theta ,{\theta }^{(n)})=E_{z\in P(z|x,{\theta }^{(n)})}\log P(x,z|\theta )\end{array}$$

这个，就是千呼万唤的$Q$函数了。 $EM$的$E$，就是上式中的求期望，$M$就是求期望的最大化。 这就是$EM$算法的全部。

让我们回顾一下，刚才那个看似很奇怪的变形，其本质是通过构造一个$KL$散度，将第二项处理成非负的，让我们可以清晰得到$ELBO$这个下界。

等等，刚才说梯度下降难以满足非负约束，这里难道就满足了吗？答案是满足了。 只要我们保证初始化时$P(x|z,\theta )$和$P(z|\theta )$是正数，那么在Q函数最大化的过程中，一定是使得$P(x|z,\theta )$和$P(z|\theta )$越来越大的。

还有，文章开头提到了$Jessen$不等式，为什么整个推导过程中，没有看到$Jessen$不等式呢？

如果用$Jessen$不等式，推导起来会更加直接。

$$\begin{array}{}\text{(14)}& \begin{array}{rl}\log P(x|\theta )& =\log \sum _{z}P(x,z|\theta )\\ & =\log \sum _{z}P(z|x,{\theta }^{(n)})\frac{P(x,z|\theta )}{P(z|x,{\theta }^{(n)})}\\ & =\log E_{z\in P(z|x,{\theta }^{(n)})}\frac{P(x,z|\theta )}{P(z|x,{\theta }^{(n)})}\\ & \ge E_{z\in P(z|x,{\theta }^{(n)})}\log P(x,z|\theta )+\text{const}\end{array}\end{array}$$

最后一步就是使用的$Jessen$不等式。$Jessen$不等式，可以参考Jessen不等式。

不过，使用$Jessen$不等式后，整体的启发性就不足了。

原创文章，转载请注明出处，否则拒绝转载！
本文链接：抬头看浏览器地址栏

---