Jensen’s inequality

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

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

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

收敛性证明

我们想用模型拟合数据，也就是求似然函数： $\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算法分为两步：

1. E step：每次得到似然函数$\ell$的一个下界。
2. 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：

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

GMM revisited

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

E step

E step相对容易一些，我们对于当前步估计的所有参数值，计算$z$的后验分布（这样能保证在当前参数下等式成立，也就是tight bound）： $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算法的迭代过程。