EM算法推导

2019-04-18 本文已影响0人 zealscott

推导EM算法，并证明收敛性。

Jensen’s inequality

定理：若 $f$ 是凸函数， $X$ 是随机变量，我们有： $\mathrm{E}[f(X)] \geq f(\mathrm{E} X)$

若 $f$ 是严格凸函数，也就是 $f^{''} > 0$ 恒成立，同时 $X=E[X]$ （也就是概率为1），则等号成立。
若 $f$ 是凹函数，则该定理也成立，只不过将大于等于换成小于等于。

忽略证明，该定理并不直观，可以用一个简单的例子帮助记忆：

image-20190418202130305

收敛性证明

我们想用模型拟合数据，也就是求似然函数：
$\begin{aligned} \ell(\theta) &=\sum_{i=1}^{m} \log p(x ; \theta) \\ &=\sum_{i=1}^{m} \log \sum_{z} p(x, z ; \theta) \end{aligned}$
其中， $z$ 是隐变量。如果 $z$ 已知，那么直接用MLE求解即可，如果未知，则需要用EM算法迭代求解。

EM算法分为两步：

E step：每次得到似然函数 $\ell$ 的一个下界。
M step：对该下界进行优化。

我们首先可以假设 $Q$ 是 $z$ 的分布，也就是满足： $\sum_{z} Q_{i}(z)=1, Q_{i}(z) \geq 1$

因此可以得到：
$\begin{aligned} \sum_{i} \log p\left(x^{(i)} ; \theta\right) &=\sum_{i} \log \sum_{z^{(i)}} p\left(x^{(i)}, z^{(i)} ; \theta\right) \\ &=\sum_{i} \log \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)} \\ & \geq \sum_{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)} \end{aligned}$
这里用到了期望就是概率的思想。我们将 $Q$ 函数看成是在随机变量 $\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}$ 上的概率分布，将函数 $f$ 看成是log function。因此，第二个等式可以看作是 $f(EX)$ 。而由于 $f$ 函数是凹函数，因此根据Jensen’s inequality，可以得到不等式三。

这样，对于任意的分布 $Q$ ，我们给出了似然函数的下界。因此，我们如何选择一个合适的 $Q$ 呢？

我们如果对当前的 $\theta$ 有一个估计值，那么很自然的思想就是用这个估计值来得到不等式的下界。根据之前Jensen’s inequality不等式的分析，如果我们的随机变量是一个常量，那么等式一定成立，即：
$\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}=c$
因此，我们只需要 $Q_{i}\left(z^{(i)}\right) \propto p\left(x^{(i)}, z^{(i)} ; \theta\right)$ 即可。同时，由于 $\sum_{z} Q_{i}\left(z^{(i)}\right)=1$ 的条件需要满足，因此构造一个 $Q$ 函数为：
$\begin{aligned} Q_{i}\left(z^{(i)}\right) &=\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{\sum_{z} p\left(x^{(i)}, z ; \theta\right)} \\ &=\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{p\left(x^{(i)} ; \theta\right)} \\ &=p\left(z^{(i)} | x^{(i)} ; \theta\right) \end{aligned}$
实际上，这个 $Q$ 函数就是我们熟悉的在给定 $\theta$ 下的后验分布。

如何证明收敛性呢？也就是需要证明 $\ell\left(\theta^{(t)}\right) \leq \ell\left(\theta^{(t+1)}\right)$ 始终成立。

由于我们选择的 $Q$ 函数能使得等式成立，因此在第 $t$ 次迭代时，有：
$\ell\left(\theta^{(t)}\right)=\sum_{i} \sum_{z^{(i)}} Q_{i}^{(t)}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta^{(t)}\right)}{Q_{i}^{(t)}\left(z^{(i)}\right)}$
在第 $t+1$ 次时，我们的 $\theta^{(t+1)}$ 是最大化右边的式子的来的，因此：
$\begin{aligned} \ell\left(\theta^{(t+1)}\right) & \geq \sum_{i} \sum_{z^{(i)}} Q_{i}^{(t)}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta^{(t+1)}\right)}{Q_{i}^{(t)}\left(z^{(i)}\right)} \\ & \geq \sum_{i} \sum_{z^{(i)}} Q_{i}^{(t)}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta^{(t)}\right)}{Q_{i}^{(t)}\left(z^{(i)}\right)} \\ &=\ell\left(\theta^{(t)}\right) \end{aligned}$
其中，第一个不等式是根据Jensen’s inequality，第二个不等式是根据最大化 $\theta$ 的性质来的。

如果我们定义：
$J(Q, \theta)=\sum_{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}$
那么，EM算法也可以看作是在 $J$ 上进行coordinate ascent：

E step 时，固定，根据最大化
- 实际上是通过Jensen’s inequality的性质，定义 $Q$ 函数为后验概率满足等式）
M step 时，固定，根据最大化
- 实际上是通过MLE进行最大化

GMM revisited

GMM的思想不再阐述，这里主要进行推导closed form。

E step

E step相对容易一些，我们对于当前步估计的所有参数值，计算 $z$ 的后验分布：
$w_{j}^{(i)}=Q_{i}\left(z^{(i)}=j\right)=P\left(z^{(i)}=j | x^{(i)} ; \phi, \mu, \Sigma\right)$

M step

根据上一步得到的 $z$ 的分布，我们最大化 $\ell$ 的下界：
$\begin{aligned} \sum_{i=1}^{m} & \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \phi, \mu, \Sigma\right)}{Q_{i}\left(z^{(i)}\right)} \\ &=\sum_{i=1}^{m} \sum_{j=1}^{k} Q_{i}\left(z^{(i)}=j\right) \log \frac{p\left(x^{(i)} | z^{(i)}=j ; \mu, \Sigma\right) p\left(z^{(i)}=j ; \phi\right)}{Q_{i}\left(z^{(i)}=j\right)} \\ &=\sum_{i=1}^{m} \sum_{j=1}^{k} w_{j}^{(i)} \log \frac{\frac{1}{(2 \pi)^{n / 2}\left|\Sigma_{j}\right|^{1 / 2}} \exp \left(-\frac{1}{2}\left(x^{(i)}-\mu_{j}\right)^{T} \Sigma_{j}^{-1}\left(x^{(i)}-\mu_{j}\right)\right) \cdot \phi_{j}}{w_{j}^{(i)}}\end{aligned}$
我们只需要分别对三个参数进行求导，即可得到：
$\mu_{l} :=\frac{\sum_{i=1}^{m} w_{l}^{(i)} x^{(i)}}{\sum_{i=1}^{m} w_{l}^{(i)}}\\ \phi_{j} :=\frac{1}{m} \sum_{i=1}^{m} w_{j}^{(i)}\\ \Sigma_{j} :=\frac{\sum_{i=1}^{m} w_{j}^{(i)}\left(x^{(i)}-\mu_{j}\right)\left(x^{(i)}-\mu_{j}\right)^{T}}{\sum_{i=1}^{m} w_{j}^{(i)}}$
这也就是我们上一个博客给出的EM算法的迭代过程。