EM算法

EM算法（Expectation-Maximization Algorithm)是一个十分经典且精妙的统计学习算法，在机器学习领域等具有重要的意义。

Introduction

EM算法所要解决的是参数估计中包含隐变量的情形，对于只包含显变量的情形通常可以使用极大似然估计(MLE)未知参数$\theta$，关于ML及BO其性质可以参见 极大似然估计的性质，但是对于同时包含隐变量$z$和显变量$x$的情形，对于$x$的似然函数为，

$\log p(x) = \log \int p(x,z) dz$，但是上述式子的积分符号在对数符号内部，非常难以求导。

EM算法引入了一个额外的分布，转换了上述式子，成为便于求导的形式。

下面的证明等，主要参考了 深度学习，邱锡鹏著

ELBO（Evidence Lower Bound）

引入定义在隐变量上的分布$q(z)$， 我们将对数似然函数重写为，

最后一行第一项是我们定义的证据下界(Evidence Lower Bound，ELBO), 而第二项正好是KL散度的定义。

根据Jenson不等式，我们知道KL散度大于0，且仅当两个分布相等的时候取等：

因此，ELBO是对数似然的一个下界。

EM算法的核心在于不是直接优化对数似然，而是优化上述定义的ELBO，而我们可以观察到ELBO正好将对数似然的积分符号和对数符号的内外顺序改变了，因此最大化ELBO可以基于梯度对其进行求导，导数通常是好计算的形式。

Algorithm

EM算法分为E步和M步，

• Expectation Step，固定$\theta$, 改变额外引入的$q(z)$的分布，使得$q(z) = p(z \vert x)$ ,则ELBO和对数似然取等。
• Maximization Step，根据E步计算得到的$q(z)$ ,最大化ELBO，得到对参数$\theta$新的估计

下面证明其收敛性，只需证明不断迭代地进行E步和M步可以不断抬升ELBO：

• 在E步中，改变了隐变量$q(z)$ ,对于$\log p(x)$ 没有任何影响，因此本质上抬升了新的ELBO使得其与$\log p(x)$相等。
• 在M步中，最大化ELBO，可以认为寻找到了当前条件下ELBO的最大值，因此显然也直接抬升了ELBO

因此，不断迭代的过程中，ELBO不断抬升，则对数似然也不断抬升，可以不断接近最大似然估计的结果。

GMM（Gaussian Mixture Model）

混合高斯模型（GMM，Gaussian Mixed Model）是EM算法一个最经典的入门例子，理解该模型，对EM算法的本质和流程都可以有更清晰的认识，这里暂略，但强烈推荐邱锡鹏的深度学习书中的讲述： 深度学习，邱锡鹏著

Application

EM算法不仅可以用在直接解决带隐变量的参数估计问题，还有诸多应用，例如可以用来解决推断问题。

考虑要估计$p( z \vert x) = \frac{p(z,x)}{ \int p(z,x) dz}$ ,由于下式存在积分非常不好计算，

也许可以考虑基于蒙特卡罗方法近似计算，可以参见：蒙特卡罗方法

这里基于EM算法和ELBO给出另一种方法，本质上是泛函分析中的变分法：在一族简单的函数$q(z)$中找到最接近$p(z \vert x)$的一个。

根据上述结论，$\log p(x) = \text{ELBO} + \text{KL}( q(z) \Vert p(z \vert x))$

给定了$x$,我们要$\min \text{KL}( q(z) \Vert p(z \vert x))$ ,等价于$\max \text{ELBO}$,此即变分法。

如果使用神经网络使得$q(z)$对$p(z \vert x)$进行拟合，则可以得到变分自编码器(VAE, Variational Auto Encoder)。