期望最大算法(EM算法)

最大期望算法(Expectation-Maximization algorithm, EM)是一类通过迭代进行极大似然估计(Maximum Likelihood Estimation, MLE)的优化算法。用于含有隐变量(Latent Variable) 的概率模型参数的极大似然估计或极大后验概率估计。Em算法的每次迭代包含两个步骤:1. E步: 求期望;2. M步:求极大,因此该算法被称作EM算法。

1 极大似然估计

极大似然估计是一种利用极大似然函数来求解模型参数 $\theta$ 的一种估计方法。 在数理统计学中,似然函数是一种关于统计模型的参数的函数。在给定一个样本 $x$ 时,关于参数 $\theta$ 的似然函数 $L(\theta|x)$ (在数值上)等于给定参数 $\theta$ 后变量 $x$ 的概率(似然函数与概率的一种关系):

在给定样本集 $\bar x=\{x_1,x_2,…,x_N\}$, 在这个样本集上的似然函数为:

由于公式2中含有连乘运算,因此不方便计算,通常我们利用对数的特性,来对公式2取对数来得到对数似然函数,为了方便,我们还是将 $\log L(\theta|\bar x)$ 记作 $L(\theta|\bar x)$:

通过 $L(\theta|\bar x)$ 对 $\theta$ 求导,并取倒数为0,此时得到最优的 $\theta$.

下面以高斯模型为例来简单说明极大似然估计,并引导出EM算法。

示例一

如下图,我们采集到一些数据(黄色的+)服从单个高斯分布,由于高斯分布中有两个参数,均值和方差,我们将其表示为 $\theta =\{\mu,\sigma\}$,通过极大似然估计方法我们来求得最优的$\theta^{*} =\{\mu^{*},\sigma^{*}\}$,如下图我们就是从$\theta_1,\theta_2,\theta_3$中求得 $\theta_1$

单一高斯极大似然估计
图1 单一高斯模型

大致思路就是利用公式3求得对数似然函数,然后对其求最大值,即求得 $\theta^*$,该过程通过如两个公式来分别求出 $\mu$ 和 $\sigma$:

我们通过上式可以求得

示例二

如图二所示的样本,从图中我们可以明显看出,黄色和黑色样本分别位于两个类中,此时如果我们还是用单一的高斯模型来为该样本集建模,是行不通的,主要有两个原因:

  1. 高斯分布的特点是在 $\mu$ 附近的概率很大,而从徒儿看出,在 $\mu$ 附近没有样本,样本基本位于两端,距离 $\mu$ 很远,这不符合高斯分布特点;
  2. 黄色的样本比黑色的样本更密集,也就是他的概率更大,因此我们不应该同等对待。

混合样本单一模型

既然单一高斯模型已经无法适用于该样本集,那我们用多个高斯模型呢,再此示例中,我们可以看出样本集分布在两个分布中较为合理,其结果如图 3所示.通过比较图2和图3,可以得出,图3时更合理的分布,此时得到高斯混合模型,其混合模型如图4所示。

图3 双高斯模型
图4 混合高斯模型

根据上面的描述,我们对每个高斯叠加起来,即:

但是,我们把公式8对变量 $x$ 进行积分,按照概率,该积分应该为1,事实上,该积分不为一,而为2.为了解决这个问题,我们可以平均每个高斯,即给一个权重 $\frac{1}{2}$, 但是这部理想,有时样本在不同分布中权重不一致,因此我们可以给每个分布一个权重比例,且比例之和为1,我们将其推广到一般形式,即:

该公式的参数变为 $\theta=\{\mu_1,\mu_2,…\mu_k, \sigma_1,\sigma_2,…,\sigma_k, \alpha_1, \alpha_2,…,\alpha_k-1\}$
此时,我们将上式代入公式3得到该样本集的似然函数为:

由于 $\log$ 函数里面存在一个求和公式,如果我们再用极大似然估计法来求解上式的解,将变得很复杂,甚至求不出来,因此极大似然估计发在这里已行不通。

以上就是期望最大算法被提出的一个简单原因。

2 期望最大算法

期望最大算法通过迭代求解来求得最后的一个近似最优的 $\theta$ 值,由“迭代”二字可以看出,当前步的 $\theta$肯定与上一步的 $\theta$ 有关,即存在一种关系:

EM算法对函数 $f$ 的定义为:

其中 $z$ 是为了简化计算,而引入的一个隐变量(Latent Variable), $x$ 为观测变量(Observable Variable).这两个变量对应到高斯混合模型中,分别为: 我们收集到的样本集和隐藏的模型,每个样本 $x_i$ 对应一个 $z_i$,来表示该样本来自哪个分布。因此 $x_i$ 的概率分可表示为:

将上式右边分开描述,$P_{\bar \theta}(x|z_i)$ 表示 $x_i$ 在 $l$ 个高斯分布下的分布,$P(z_l)$ 表示分布为第 $l$ 个高斯分布的概率,即 $\alpha_l$,因此上式为:

该式和公式9保持一致,因此隐变量的引入,并没有改变函数的意义。

一般地,我们将 $x$ 和 $z$ 连在一起成为完全数据(complete-data),观测数据 $x$ 称为不完全数据。

3 EM算法的收敛性

前一节讲解了通过引入隐变量并没有改变 $P(x)$ 的表示,同事给出了 EM 算法的公式,但是EM算法的收敛性如何呢?下面我们就讲解EM算法的收敛性,要使EM算法收敛同时满足公式11的极大似然函数。在迭代过程中,要使 $\theta$ 逐渐收敛,同时满足公式11,则必存在:

根据对数函数和条件概率一个特征 $\log \frac{A}{B}=\log A - \log B$ 和 $P(x)=\frac{P(x, z)}{P(z|x)}$可得:

我们对公式两边分别对分布 $P(z|x, \theta^{(g)})$ 求期望,左边为:

右边为:

我们通常称 $Q(\theta, \theta^{(g)})$ 为 Q函数:完全数据的对数似然函数$\log P(x, z|\theta)$关于给定观测数据和当前参数 $\theta^{(g)}$下对隐藏数据 $z$ 的条件概率的期望称为Q函数。

根据公式17、18和19我们可以得出:

极大似然估计就是对 $\log P(x|\theta)$ 进行极大化,对上面的右边公式进行极大化,可不可以呢?不可以,如果这样做就又回到最大似然函数了,因此得不了解,EM算法只是对 $Q(\theta, \theta^{(g)})$ 进行极大化,因此很容易得出:

我们要想通过优化$Q(\theta, \theta^{(g)})$ 使 $\log P(x|\theta)$ 逐渐增大,则存在:

如果,我们假设,$\forall\theta,H(\theta^{(g)}, \theta^{(g)}) - H(\theta, \theta^{(g)}) \geq 0 \Rightarrow H(\theta^{(g)}, \theta^{(g)}) \geq H(\theta^{(g+1)}, \theta^{(g)})$

下面,就对这个假设进行证明:

$\geq$ 那一步利用了 Jensen 不等式(Jensen Inequality),这其实是凸函数的一个特点,如图5所示。我们求两个点的函数值的期望,即为直线上的黑点,如果我们先对自变量 x 求期望,则 $-\log(Ex)$ 为log函数曲线上的黑点,根据曲线图,我们可以得出

即,函数的均值大于等于均值的函数。

Jensen 不等式

通过以上证明可以得出,EM算法通过迭代最大化 $\int _z \log P(x,z|\theta)P(z|x, \theta^{(g)}) dz$,从而使 $P(x|\theta)$ 逐渐增大。