机器学习笔记——10 上帝的算法EM算法

机器学习笔记——10 上帝的算法EM算法

EM算法是一种迭代算法，它可以用来求解一些含有潜在变量的模型的参数。比如后面我们将介绍的混合高斯模型、kmean聚类以及因子分析，它们都利用EM算法来求解参数。EM算法非常美妙，在吴军的《数学之美》一书中，将该算法称为上帝的算法，本文标题即是延用他的说法。在本文中，我们主要介绍EM算法及其相关的数学理论，重点解释为什么EM算法可以保证收敛，以及EM算法是否能够保证得到全局最优解。

潜变量模型

给定了一个训练集$S=\{x^{(1)}，...，x^{(m)}\}$，训练的模型是$p(x,z;\theta )$，注意到这是一个潜变量模型(latent variable model)，我们的目的是通过训练集训练出参数$\theta$。因此按照正常的思路，我们需要构建一个似然函数，并尝试通过MLE获得$\theta$的参数估计。由于变量z是无法观测的，因此我们需要获得$x$的边缘分布：$$p(x;\theta )=\sum _{z}p(x,z;\theta )$$然后就可以得到对数似然函数$$\ell (\theta )=\sum _{i==1}^m\log p(x^{(i)};\theta )=\sum _{i==1}^m\log \sum _{z^{(i)}}p(x^{(i)},z^{(i)};\theta )$$事实上我们会发现求此函数的驻点是没有封闭解的，这就是潜变量模型参数估计时的困难。但是，通过EM算法，我们可以通过迭代给出一个满意的参数估计。

EM算法

EM算法通过E-step和M-step两步来不断迭代${\theta }^{(t)}$，最终达到收敛。需要特别指出，除非迭代的函数是一个凸函数，否则一般而言是无法保证达到全局最优解。此外，EM算法是可以保证收敛，这一点我们会在下文中证明。现在我们具体阐述EM算法的步骤： Repeate until convergence (E-step) For each i,set $$Q^{(i)}=p(z^{(i)}|x^{(i)},\theta )$$(M-step) Update the parameters :$$\theta =argMa{x}_{\theta \in \Theta }\sum _{i=1}^{m}ELBO(x^{(i)},Q,\theta )$$注意到，上述M-step中的ELBO，表示evidence lower bound，根据詹森不等式(Jensen’s inequality)，对于上述的对数似然函数$\ell (\theta )$，成立下列不等式：$$\begin{array}{rl}\ell (\theta )& =\sum _{i=1}^m\log \sum _{z^{(i)}}Q(z^{(i)})\frac{p(x^{(i)},z^{(i)};\theta )}{Q(z^{(i)})}\\ & \ge \sum _{i=1}^m\sum _{z^{(i)}}Q(z^{(i)})\log \frac{p(x^{(i)},z^{(i)};\theta )}{Q(z^{(i)})}\\ & =\sum _{i=1}^{m}ELBO(x^{(i)},Q,\theta )\end{array}$$其中我们记$$ELBO(x^{(i)},Q,\theta )=\sum _{z^{(i)}}Q(z^{(i)})\log \frac{p(x^{(i)},z^{(i)};\theta )}{Q(z^{(i)})}$$它表示似然函数的一个下界。此外不等式成立的原因是因为$\sum Q(z^{(i)})=1$而且$\log (x)$是一个凹函数，所以有$\log (E(x))\ge E(\log x)$。

EM算法的收敛性

EM算法是能够收敛的，其原因在于我们每一轮的E-step和M-step都能增大对数似然函数$\ell (\theta )$。以下具体地说明这两点： E-step： 我们知道，詹森不等式，当且仅当x是一个常数时，等号成立，所以当$Q(z^{(i)})\propto p(x^{(i)},z^{(i)};\theta )$时，等号成立，此时便有 $$\ell (\theta )=ELBO(x^{(i)},Q,\theta )$$因此在E-step中，我们利用贝叶斯公式，更新$Q^{(i)}$为其后验分布，即： $$Q(z^{(i)})=p(z^{(i)}|x^{(i)};\theta )=\frac{p(z^{(i)},x^{(i)};\theta )}{{\sum }_{z}p(z^{(i)},x^{(i)};\theta )}\propto p(x^{(i)},z^{(i)};\theta )$$因此这一过程通过更新$Q$，必然会提高$ELBO(x^{(i)},Q,\theta )$。 M-step: 我们通过调整$\theta$，最大化$ELBO(x^{(i)},Q,\theta )$。因此也会导致下界的提高。 综上所述，在第t轮迭代中，我们通过控制住变量${\theta }^{(t)}$，在E步骤调整$Q^{(t)}$为$Q^{(t+1)}$；然后控制住$Q^{(t+1)}$，在M步骤将${\theta }^{(t)}$调整${\theta }^{(t+1)}$。由此使得似然函数的下界不断提高，在此过程也不断地提高似然函数$\ell (\theta )$。即：$$\begin{array}{rl}Jense{n}^{\prime }sinequality& \\ \ell ({\theta }^{(t)})& \ge \sum _{i=1}^{m}ELBO(x^{(i)},Q^{(t)},{\theta }^{(t)})\\ (E-step)& \\ \ell ({\theta }^{(t)})& =\sum _{i=1}^{m}ELBO(x^{(i)},Q^{(t+1)},{\theta }^{(t)})\\ (M-step)& \\ \ell ({\theta }^{(t)})& <\sum _{i=1}^{m}ELBO(x^{(i)},Q^{(t+1)},{\theta }^{(t+1)})\\ Jense{n}^{\prime }sinequality& \\ \ell ({\theta }^{(t)})& <\ell ({\theta }^{(t+1)})\end{array}$$因此每一轮迭代都会导致$\ell (\theta )$的增大，而$\ell (\theta )$又是有上界，因此必然会存在某一次迭代，使得$\ell ({\theta }^{(t+1)})-\ell ({\theta }^{(t)})<ϵ$，此时即算法收敛。 最后，需要特别指出，EM并不能保证得到全局最优解，但是实践发现，EM算法经常能够给出比较令人满意的结果。在下一篇文章中，我们介绍混合高斯模型，其参数的估计即是利用EM算法进行的，因此其可以视为本文所述理论的一个具体的案例。根据本文的一般化讨论，我们也将不再必要地去具体地说明其算法的收敛性。