PRML读书笔记:9.2 混合高斯


首先用离散隐变量来描述高斯混合模型。

高斯混合概率分布可以写成以下形式:

$$ p(\boldsymbol{x})=\sum_{k=1}^{K} \pi_{k} \mathcal{N}\left(\boldsymbol{x} | \boldsymbol{\mu}_{k}, \mathbf{\Sigma}_{k}\right) $$

引入$K$维one-hot变量$\boldsymbol{z}$作为隐变量(这个隐变量的含义大概是$\boldsymbol{x}$来自哪一个高斯分布),其中

$$
p(z_k = 1) = \pi_k
$$

则$\boldsymbol{x}$的条件分布为

$$ p\left(\boldsymbol{x} | z_{k}=1\right)=\mathcal{N}\left(\boldsymbol{x} | \boldsymbol{\mu}_{k}, \mathbf{\Sigma}_{k}\right) $$

考虑到$\boldsymbol{z}$的其他分量都为0,上式也可以写成

$$ p(\boldsymbol{x} | \boldsymbol{z})=\prod_{k=1}^{K} \mathcal{N}\left(\boldsymbol{x} | \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)^{z_{k}} $$

于是$\boldsymbol{x}$的边缘概率分布可以通过对所有可能的$\boldsymbol{z}$的联合概率求和得到:

$$ \begin{aligned} p(\boldsymbol{x}) &= \sum_{\boldsymbol{z}} p(\boldsymbol{z}) p(\boldsymbol{x} | \boldsymbol{z}) \\ &= \sum_{k=1}^N p(z_k = 1) p\left(\boldsymbol{x} | z_{k}=1\right)\\ &= \sum_{k=1}^{K} \pi_{k} \mathcal{N}\left(\boldsymbol{x} | \boldsymbol{\mu}_{k}, \mathbf{\Sigma}_{k}\right) \end{aligned} $$

于是就验证了$\boldsymbol{z}$作为隐变量时与高斯混合分布的等价性。对于每个观测数据点$\boldsymbol{x}_n$,都存在一个对应的潜在变量$\boldsymbol{z}_n$。这样做使得我们能够操作联合概率分布$p(\boldsymbol{x}, \boldsymbol{z})$,能够简化EM算法的计算。

另一个重要的量是给定$\boldsymbol{x}$的条件下$\boldsymbol{z}$的条件概率:

$$ \begin{aligned} \gamma\left(z_{k}\right) \equiv p\left(z_{k}=1 | \boldsymbol{x}\right) &=\frac{p\left(z_{k}=1\right) p\left(\boldsymbol{x} | z_{k}=1\right)}{\sum_{j=1}^{K} p\left(z_{j}=1\right) p\left(\boldsymbol{x} | z_{j}=1\right)} \\ &=\frac{\pi_{k} \mathcal{N}\left(\boldsymbol{x} | \boldsymbol{\mu}_{k}, \mathbf{\Sigma}_{k}\right)}{\sum_{j=1}^{K} \pi_{j} \mathcal{N}\left(\boldsymbol{x} | \boldsymbol{\mu}_{j}, \mathbf{\Sigma}_{k}\right)} \end{aligned} $$

不妨认为$\pi_k$是$z_k = 1$的先验概率,$\gamma\left(z_{k}\right)$是观测到$\boldsymbol{x}$后$z_k = 1$的后验概率,它也可以被看做是分量$k$对于“解释”观测值$\boldsymbol{x}$的责任(或者说,$\boldsymbol{x}$是第$k$个高斯分布生成的概率是多少)。

9.2.1 最大似然

假定有一个观测数据集${\boldsymbol{x}_1, \cdots, \boldsymbol{x}_N}$,用高斯混合模型来对数据进行建模,则对数似然函数为

$$ \ln p(\boldsymbol{X} | \boldsymbol{\pi}, \boldsymbol{\mu}, \boldsymbol{\Sigma})=\sum_{n=1}^{N} \ln \left\{\sum_{k=1}^{K} \pi_{k} \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)\right\} $$

上述似然函数可能具有奇异性,而且令导数为0时没有解析解,为此,我们需要引入EM算法。

9.3.2 用于高斯混合模型的EM

下面针对高斯混合模型的问题给出EM(expection-maximization)算法的一种形式。

推导似然函数最大值需要满足的条件

将$\ln p(\boldsymbol{X} | \boldsymbol{\pi}, \boldsymbol{\mu}, \boldsymbol{\Sigma})$对$\boldsymbol{\mu}_k$求导,导数置为0(高斯分布的导数见数学基础):

$$ \begin{aligned} \frac{\partial}{\partial \boldsymbol{\mu}_k}\ln p(\boldsymbol{X} | \boldsymbol{\pi}, \boldsymbol{\mu}, \boldsymbol{\Sigma}) &= \sum_{n=1}^N \frac{\pi_k \frac{\partial \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)}{\partial \boldsymbol{\mu}_k} }{\sum_{j=1}^{K} \pi_{j} \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{j}, \boldsymbol{\Sigma}_{j}\right)} \\ &= \sum_{n=1}^N \frac{\pi_k \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right) \boldsymbol{\Sigma}_{k}^{-1} (\boldsymbol{x}_n - \boldsymbol{\mu}_k) }{\sum_{j=1}^{K} \pi_{j} \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{j}, \boldsymbol{\Sigma}_{j}\right)} \end{aligned} $$

得到

$$ 0=\sum_{n=1}^{N} \underbrace{\frac{\pi_{k} \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{k}, \mathbf{\Sigma}_{k}\right)}{\sum_{j} \pi_{j} \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{j}, \mathbf{\Sigma}_{j}\right)}}_{\gamma\left(z_{n k}\right)} \boldsymbol{\Sigma}_{k}^{-1}\left(\boldsymbol{x}_{n}-\boldsymbol{\mu}_{k}\right) $$

可以发现$\gamma\left(z_{n k}\right)$出现在了等式中。

两侧同乘$\boldsymbol{\Sigma}_{k}$,整理,可以得到

$$\boldsymbol{\mu}_{k}=\frac{1}{N_{k}} \sum_{n=1}^{N} \gamma\left(z_{n k}\right) \boldsymbol{x}_{n}$$

其中

$$N_{k}=\sum_{n=1}^{N} \gamma\left(z_{n k}\right)$$

由于$\gamma\left(z_{k}\right)$可以被看成是分量$k$对于“解释”观测值$\boldsymbol{x}$的责任,因此$N_k$可以被看成是分配到聚类$k$的数据点的有效数量,$\boldsymbol{\mu} _ k$可以被看成是数据集内所有数据点的加权平均,权值是$\gamma\left(z _ {k}\right)$。

将$\ln p(\boldsymbol{X} | \boldsymbol{\pi}, \boldsymbol{\mu}, \boldsymbol{\Sigma})$对$\boldsymbol{\Sigma}_k$求导,导数置为0,得到

$$ \begin{aligned} & \frac{\partial}{\partial \boldsymbol{\Sigma}_k}\ln p(\boldsymbol{X} | \boldsymbol{\pi}, \boldsymbol{\mu}, \boldsymbol{\Sigma}) \\ =& \sum_{n=1}^N \frac{\pi_k \frac{\partial \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)}{\partial \boldsymbol{\Sigma}_k} }{\sum_{j=1}^{K} \pi_{j} \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{j}, \boldsymbol{\Sigma}_{j}\right)} \\ =& \sum_{n=1}^N \frac{\pi_k \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right) }{\sum_{j=1}^{K} \pi_{j} \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{j}, \boldsymbol{\Sigma}_{j}\right)} \frac{1}{2} \left[\boldsymbol{\Sigma}_k^{-1} (\boldsymbol{x}_n - \boldsymbol{\mu}_k)(\boldsymbol{x}_n - \boldsymbol{\mu}_k)^T \boldsymbol{\Sigma}_k^{-1} - \boldsymbol{\Sigma}_k^{-1} \right] \\ =& \sum_{n=1}^N \frac{1}{2} \gamma(z_{nk}) \left[\boldsymbol{\Sigma}_k^{-1} (\boldsymbol{x}_n - \boldsymbol{\mu}_k)(\boldsymbol{x}_n - \boldsymbol{\mu}_k)^T \boldsymbol{\Sigma}_k^{-1} - \boldsymbol{\Sigma}_k^{-1} \right] \end{aligned} $$

令上式等于0,左右两边同乘$\boldsymbol{\Sigma}_k$,整理得到

$$\boldsymbol{\Sigma}_{k}=\frac{1}{N_{k}} \sum_{n=1}^{N} \gamma\left(z_{n k}\right)\left(\boldsymbol{x}_{n}-\boldsymbol{\mu}_{k}\right)\left(\boldsymbol{x}-\boldsymbol{\mu}_{k}\right)^{T}$$

这与多元高斯分布对应的结果类似,只不过同样进行了加权平均。

最后,关于系数$\pi_k$最大化$\ln p(\boldsymbol{X} | \boldsymbol{\pi}, \boldsymbol{\mu}, \boldsymbol{\Sigma})$。此处必须考虑$\sum_{k=1}^K \pi_k = 1$这一条件,因此我们使用拉格朗日乘数法,最大化下面的量:

$$\ln p(\boldsymbol{X} | \boldsymbol{\pi}, \boldsymbol{\mu}, \boldsymbol{\Sigma})+\lambda\left(\sum_{k=1}^{K} \pi_{k}-1\right)$$

将上式对$\pi_k$求导,得到

$$ \sum_{n=1}^{N} \frac{\mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{k}, \mathbf{\Sigma}_{k}\right)}{\sum_{j} \pi_{j} \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{j}, \mathbf{\Sigma}_{j}\right)}+\lambda = \sum_{n=1}^{N} \frac{\gamma\left(z_{n k}\right)}{\pi_k} + \lambda = 0 $$

两侧乘以$\pi_k$,对$k$求和,得到

$$ \sum_{k=1}^K\sum_{n=1}^{N} \gamma\left(z_{n k}\right) + \lambda \sum_{k=1}^K \pi_k = 0 $$

得到$\lambda = -N$,代回原式,得到

$$\pi_{k}=\frac{N_{k}}{N}$$

因此第$k$个高斯分量的混合系数为这个分量对于解释数据点的“责任”的平均值。

EM算法

虽然上述推导并没有给出混合模型参数的一个解析解,但却给出了一个简单的用于寻找问题的极大似然解的迭代方法。这个迭代过程是EM算法应用于高斯混合模型的一个实例。在EM算法中,我们首先为$\boldsymbol{\mu}_k$、$\boldsymbol{\Sigma}_k$和$\pi_k$选择一个初始值,然后交替进行E和M两个更新步骤:

  • E(期望)步骤:使用参数的当前值计算$\gamma(z_{nk})$
  • M(最大化)步骤:使用$\gamma(z_{nk})$的值重新计算$\boldsymbol{\mu}_k$、$\boldsymbol{\Sigma}_k$和$\pi_k$的值(其中先计算新的均值,再用新的均值计算协方差)

之后将证明每一轮迭代都能够保证对数似然函数的增大。

在实际应用中,当对数似然函数的变化量或者参数的变化量低于某个阈值时,我们就认为算法收敛。

K-means算法通常被用于初始化EM算法。$\boldsymbol{\mu}_k$可以设置为聚类的中心点,$\boldsymbol{\Sigma}_k$可以设置为每一类的样本协方差,$\pi_k$可以被设置为第$k$类中数据点所占的比例。

例:用EM算法进行聚类

// TODO


 评论