PRML学习笔记(九)

第九章 混合模型和EM

Posted by Pelhans on November 22, 2018

PRML 和 ESL 的学习基本上是学十得一。稳扎稳打再来一次

混合模型和EM

我们将引入混合概率分布的潜在变量观点,其中离散潜在变量可以被看将数据点分配到了混合概率分布的具体成分当中。潜在变量模型中寻找最大似然估计的一个一般的方法是期望最大化(EM)算法。

9.1 K均值聚类

现在考虑寻找对维空间中数据点的分组或聚类的问题。我们的目标是找到数据点分别属于的聚类,以及一组向量${\mu_{k}}$,使得每个数据点和与它最近的向量$\mu_{k}$之间的距离的平方和最小。

定义一组对与每个数据点$x_{n}$的二值指示变量$r_{nk}\in {0,1 } $,其中k表示数据点$x_{n}$属于K个聚类中的哪一个,若$x_{n}$被分到类别k,那么$r_{nk}=1$,其余为0。因此我们可以定义一个目标函数,有时被称为失真度量:

它表示每个数据点与它被分配的向量$\mu_{k}$之间的距离的平方和。

目标是找到${r_{nk}}$和${\mu_{k}}$的值,使得J达到最小值。我们将使用迭代的方法完成最优化。首先,我们为$\mu_{k}$选择一些初始值。然后,在第一阶段,我们关于$r_{nk}$最小化J,保持$\mu_{k}$固定。在第二阶段,我们关于$\mu_{k}$最小化J,保持$r_{nk}$固定。不断重复两个阶段直到收敛。这对英语EM算法的E(期望)和M(最大化)步骤。由于$\mu_{k}$的解为:

可以看出,上式的分母等于聚类k中数据点的数量,因此它相当于令$\mu_{k}$等于类别k的所有数据点的均值。因此上述步骤被称为K均值算法。

我们也可以推出关于它的在线随机算法,方法是:将 Robbins-Monro 步骤应用于寻找回归函数的跟的问题中,其中回归函数由前面的失真度量J关于$\mu_{k}$的导数给出,$\mu_{k}$的更新公式为:

除此之外,我们还可以将欧几里得距离替换一个更加一般的不相似程度的度量$\nu(x, x^{‘})$,然后最小化下面的失真度量:

这就给出了K中心点算法。

9.2 混合高斯

前面我们简单的将高斯混合模型看成高斯分量的简单线性叠加,现在我们使用离散潜在变量来描述高斯混合模型。

高斯混合概率分布可以写为:

现在引入一个K为二值随机变量z,它采用了’1-of-K’表示法。z的边缘概率分布根据混合系数$\pi_{k}$进行赋值,即:

其中:

因此:

类似地:

因此:

由上式可以看出,对于新的表示,每个观测数据点$x_{n}$,存在一个对应的潜在变量$z_{n}$。现在我们能够对联合概率分布$p(x,z)$进行操作,而不是对边缘概率分布$p(x)$进行操作,这会产生极大的计算上的简化。通过引入EM算法,即可看到这一点。

除此之外,我们定义$\gamma(z_{k})$表示 $p(z_{k}=1 | x)$:

我们将$\pi_{k}$看成$z_{k}=1$的先验概率,将$\gamma(z_{k})$看成观测到x之后,对应的后验概率。这样$\gamma(z_{k})$可以被看做分量k对于“解释”观测值x的“责任”。

9.2.1 最大似然

假设观测数据集${x_{1}, \dots, x_{N} }$,记做 $\mathbf{X}$的维度为$N\times D$。其中第n行为$x_{n}^{T}$,Z为$n\times K$,第n行为$z_{n}^{T}$。则对数似然函数为:

对于上式的优化比之前更困难,因为对k的求和出现在对数计算内部,从而对数函数不再直接作用于高斯分布。如果我们令对数似然函数的导数等于零,那么我们不会得到一个解析解。一个方法是基于梯度的优化方法,零一种是EM算法。

9.2.2 用于高斯混合模型的EM

首先令似然函数关于$\mu_{k}$的均值等于零,有:

可以将 $N_{k}$看做分配到聚类k的数据点的有效数量。对于求得的$\mu$我们看到第k个高斯分量的均值$\mu_{k}$通过对数据集里所有的数据点求加和平均的方式得到。

令似然函数对 $\Sigma$导数为零,有:

对$\pi$导数为零,有:

因此,第k个分量的混合系数为那个分量对于解释数据点的责任的平均值。

因此,给定一个高斯混合模型,目标是关于参数(均值、协方差、混合系数)最大化似然函数,则它的步骤为:

  • 初始化均值$\mu_{k}$、协方差$\Sigma_{k}$和混合系数$\pi_{k}$,计算对数似然函数的初始值。
  • E步骤,使用当前参数值计算“责任”。
  • M步骤,使用当前的“责任”重新估计参数。
  • 计算对数似然函数:
  • 检查参数或者对数似然函数的收敛性。如果没有满足收敛的准则,则返回第2步。

9.3 EM的另一种观点

EM 算法的目标是找到具有潜在变量的模型的最大似然解。对数似然函数为:

可以看到,求和位于对数内部,这样即使 $p(\mathbf{X,Z} |\theta)$ 属于指数族分布,由于求和式的存在,边缘概率分布 $p(\mathbf{X} | \theta)$也不是指数族分布。使得问题变得复杂。

现在我们假定${\mathbf{X,Z} }$是完整的数据集,实际的观测数据集X是不完整的。完整数据集的对数似然函数的形式为 $\ln p(\mathbf{X,Z} | \theta)$,并且假定对这个完整的对数似然函数进行最大化是容易的。

然而,在实际应用中,我们没有完整的数据集${\mathbf{X,Z}}$,只有不完整的X。关于变量Z的取值知识仅仅来源于后验概率分布 $p(\mathbf{Z} | \mathbf{X}, \theta)$。由于我们不能使用完整数据的对数似然函数,因此我们反过来考虑在潜在变量的后验概率分布下,它的期望值,这对应于EM算法的E步骤。接下来在M步骤中,我们最大化这个期望。如果当前对于参数的估计为$\theta^{old}$,那么一次连续的E步骤和M步骤会产生一个修正的$\theta^{new}$。

给定观测变量X和潜在变量Z上的一个联合概率分布 $p(X,Z | \theta)$,由参数$\theta$控制,目标是关于$\theta$最大化似然函数 $p(\mathbf{X} | \theta)$一般的EM算法总结如下:

  • 选择参数$\theta^{old}的一个初始设置。

  • E 步骤。计算 $p(\mathbf{Z} | \mathbf{X}, \theta^{old})$。

  • M 步骤。计算$\theta^{new}$,由下式给出。

  • 检查对数似然函数或者参数值的收敛性。如果不满足收敛准则,则令 $\theta^{old}\rightarrow \theta^{new} $。而后回到第二步。

9.3.1 重新考察高斯混合模型

现在考虑对完整的数据集$\mathbf{X, Z}$进行最大化。则似然函数的对数为:

与不完整数据的对数似然函数相比,我们看到在k上的求和与对数运算的顺序交换了。对数运算现在直接作用于高斯分布上,而高斯分布本身是指数族分布的一个成员。

在实际应用中,我们并没有潜在变量的值,考虑完整数据对数似然函数关于潜在变量后验概率分布的期望。后验概率分布的形式为:

因此完整数据的对数似然函数的期望值为:

这样我们就可以用EM算法进行迭代了。

9.3.3 伯努利分布的混合

现在讨论伯努利分布描述的离散二值变量的混合。这个模型也被称为潜在类别分析(Latent Class Analysis)。

完整数据的对数似然函数为:

完整数据的对数似然函数关于潜在变量后验概率分布的期望为:

其中$\gamma(z_{nk}) = E[z_{nk}]$是给定数据点$x_{n}$的条件下,分量k的后验概率分布,或者“责任”。

接下来我们就可以使用EM算法循环计算“责任”、期望和参数了。

9.4 一般形式的EM算法

EM 算法是寻找具有潜在变量的概率模型的最大似然解的一种通用方法。现在我们给出一般化的讨论。

首先引入一个定义在潜在变量上的分布q(Z)。对于任意的q(Z),下面的分解成立:

其中我们定义了:

我们看到,$\mathcal{L}(q, \theta)$给出了X和Z的联合概率分布,而 $KL(q||p)$包含了给定X条件下,Z的条件概率分布。由于KL散度非负,因此$\mathcal{L}(q, \theta)$ 是 $\mathcal{L}(q, \theta)$的一个下界。

现在我们证明,EM算法确实最大化了对数似然函数。假设参数向量的当前值为$\theta^{old}$。

在E步骤中,下届$\mathcal{L}(q, \theta^{old})$关于q(Z)的最大化,而$\theta^{old}$保持固定。可以看出,$\mathcal{L}(q,\theta^{old})$的最大值出现在KL散度等于零的时候,换句话说,最大值出现在q(Z)与后验概率分布 $p(Z|X, \theta^{old})$相等的时候。此时,下界等于对数似然函数。

在M步骤中,分布q(Z)保持固定,下界$\mathcal{L}(q,\theta)$关于$\theta$进行最大化,得到了某个新值$\theta^{new}$。这会使得下界$\mathcal{L}$增大(除非到达了最大值),也就使得对数似然函数增大。由于概率分布q由就得参数值确定,并且在M步骤不变,因此KL散度非零,于是对数似然函数的增加量大于下界的增加量。从而在M步骤中,最大化的量是完整数据对数似然函数的期望。如下图所示:

EM 算法也可以被看做参数空间中的运算,如下图所示。红色曲线表示不完整数据的对数似然函数,它的最大值使我们想要的。我们首先选择某个初始的参数值$\theta^{old}$,然后在第一个E步骤中,我们计算潜在变量上的后验概率分布,得到了$\mathcal{L}(q, \theta^{old})$的一个更小的下界,它的值等于在$\theta^{old}$处的对数似然函数值,用蓝色曲线表示。注意,下界与对数似然函数在$\theta^{old}$处以切线的方式连接,因此两条曲线的梯度相同。这个界是一个凹函数,对于指数族分布的混合分布来说,有唯一最大值。在M步骤中,下界被最大化,得到了新的值$\theta^{new}$,这个值给出了比$\theta^{old}$处更大的对数似然函数值。接下来的E步骤构建了一个新的下界,它在$\theta^{new}$处与对数似然函数切线链接,用绿色线表示。如下图所示: