高斯混合模型和EM算法

一、混合模型(Mixture Model)

混合模型是一个可以用来表示在总体分布(distribution)中含有 K 个子分布的概率模型。换句话说,混合模型表示了观测数据在总体中的概率分布,它是一个由 K 个子分布组成的混合分布。混合模型不要求观测数据提供关于子分布的信息,来计算观测数据在总体分布中的概率。

二、高斯混合模型(Gaussian Mixture Model,GMM)

1. 单高斯模型
  • 当样本数据 X 是一维数据(Univariate)时,高斯分布(也叫正态分布)遵从下方概率密度函数(Probability Density Function):

正态分布通常也记为 $N(x|\theta)$,其中 $\mu$ 为数据均值(期望), $\sigma$ 为数据标准差(Standard deviation)`。

  • 当样本数据 X 是多维数据(Multivariate)时,高斯分布遵从下方概率密度函数:

其中, $\mu$ 为数据均值(期望), $\Sigma$ 为协方差(Covariance),D 为数据维度。注意这里的 T 是矩阵转置符号,多维数据 $x-\mu$ 是一个矩阵。

2. 高斯混合模型

高斯混合模型可以看作是由 K 个单高斯模型组合而成的模型,每个 Gaussian 称为一个“Component”,这 K 个子模型是混合模型的隐变量(Hidden variable)。也就是说我们假设样本中的每个数据都由这 K 个子模型中的某一个生成。一般来说,一个混合模型可以使用任何概率分布,这里使用高斯混合模型是因为高斯分布具备很好的数学性质以及良好的计算性能。下面给出高斯混合模型的数学定义:

首先定义如下信息:

  • $x_j$ 表示第 j 个观测数据, j = 1,2,…,N
  • K 是混合模型中子高斯模型的数量, k = 1,2,…,K
  • $\alpha_k$ 是观测数据属于第 i 个子模型的概率, $\alpha_k \geq 0 , \sum_{i=1}^{K}{\alpha_k} = 1$
  • $\phi(x|\theta_k)$ 是第 k 个子模型的高斯分布密度函数, $\theta_k = (\mu_k, \sigma_k^{2})$ 。其展开形式与上面介绍的单高斯模型相同
  • $\gamma_{ji}$ 表示第 j 个观测数据属于第 i 个子模型的概率。

那么,高斯混合模型的概率分布为:

对于这个高斯混合模型而言,参数 $\theta = (\tilde{\mu_k}, \tilde{\sigma_k}, \tilde{\alpha_k})$ ,也就是每个子模型的期望、方差(或协方差)、在混合模型中发生的概率。

根据上面的式子,如果我们要从 GMM 的分布中随机地取一个点的话,实际上可以分为两步:首先随机地在这 K 个 Component 之中选一个,每个 Component 被选中的概率实际上就是它的系数 $\alpha_k$ ,选中了 Component 之后,再单独地考虑从这个 Component 的分布中选取一个点就可以了──这里已经回到了普通的 Gaussian 分布,转化为了已知的问题。

那么如何用 GMM 来做聚类呢?其实很简单,现在我们有了数据,假定它们是由 GMM 生成出来的,那么我们只要根据数据推出 GMM 的概率分布来就可以了,然后 GMM 的 K 个 Component 实际上就对应了 K 个 cluster 了。根据数据来推算概率密度通常被称作密度估计(density estimation) ,特别地,当我们在已知(或假定)了概率密度函数的形式,而要估计其中的参数的过程被称作“参数估计”

GMM与K-means比较

  • 相同点:都是可用于聚类的算法;都需要指定K值。

  • 不同点:GMM可以给出一个样本属于某类的概率是多少。

三、极大似然估计

上面只是给出了 GMM 的概率密度,但是它的参数还是未知的,那么如何该如何求概率密度的参数呢?

先来聊聊似然函数。现在假设我们有 N 个数据点,并假设它们服从某个分布(记作 p(x) ),要确定里面的一些参数的值。现在这里的分布就是高斯混合分布,我们就需要确定 $\alpha_k、\mu_k 和 \Sigma_k$ 这些参数。 我们的想法是,找到这样一组参数,它所确定的概率分布生成这些给定的数据点的概率最大,而这个概率实际上就等于 $\prod_{i=1}^N p(x_i)$ ,我们把这个乘积称作似然函数 (Likelihood Function)

通常单个点的概率都很小,许多很小的数字相乘起来在计算机里很容易造成浮点数下溢,因此我们通常会对其取对数,把乘积变成加和 $\sum_{i=1}^N \log p(x_i)$,得到对数似然函数(log-likelihood function) 。接下来我们只要将这个函数最大化(通常的做法是求导并令导数等于零,然后解方程),亦即找到这样一组参数值,它让似然函数取得最大值,我们就认为这是最合适的参数,这样就完成了参数估计的过程。下面让我们来看一看 GMM 的对数似然函数的具体形式 :

由于在对数函数里面又有加和,我们没法直接用求导解方程的办法直接求得最大值。为了解决这个问题,我们要用到 EM算法

四、EM算法

EM算法全程是 Expectation Maximization,即期望最大化算法,专门用来迭代求解极大似然估计。我们就是要找到最佳的模型参数,使得3.1式的期望最大,“期望最大化算法”名字由此而来。

EM算法每次迭代包含两个步骤:

  • E-step:求期望 $E(\gamma_{jk} | X, \theta)$ for all j = 1,2,…,N;
  • M-step:求极大,计算新一轮迭代的模型参数。

这里不具体介绍一般性的 EM 算法(通过 Jensen 不等式得出似然函数的下界 Lower bound,通过极大化下界做到极大化似然函数),只介绍怎么在高斯混合模型里应用从来推算出模型参数。通过 EM 迭代更新高斯混合模型参数的方法如下:

假设:我们有样本数据 $x_{1}, x_{2}, …,x_{N}$ 和一个有 K 个子模型的高斯混合模型,想要推算出这个高斯混合模型的最佳参数。

1. 首先初始化参数
2. E-step:依据当前参数,计算每个数据 j 来自子模型 k 的可能性

估计数据由每个 Component 生成的概率(并不是每个 Component 被选中的概率):对于每个数据 $x_i$ 来说,它由第 k 个 Component 生成的概率为:

3. M-step:计算新一轮迭代的模型参数

估计每个 Component 的参数:现在我们假设上一步中得到的 $\gamma(i, k)$ 就是正确的“数据 $x_i$ 由 Component k 生成的概率”,亦可以当做该 Component 在生成这个数据上所做的贡献。或者说,我们可以看作 $x_i$ 这个值其中有 $\gamma(i, k)x_i$ 这部分是由 Component k 所生成的。集中考虑所有的数据点,现在实际上可以看作 Component 生成了 $\gamma(1, k)x_1, \ldots, \gamma(N, k)x_N$ 这些点。由于每个 Component 都是一个标准的 Gaussian 分布,可以很容易分布求出最大似然所对应的参数值:

4. 重复计算 E-step 和 M-step 直至收敛

也就是要求 $||\theta_{i+1} - \theta_{i}|| < \varepsilon$, $\varepsilon$ 是一个很小的正数,表示经过一次迭代之后参数变化非常小。否则重复2,3两步。

至此,我们就找到了高斯混合模型的参数。需要注意的是,EM 算法具备收敛性,但并不保证找到全局最大值,有可能找到局部最大值。解决方法是初始化几次不同的参数进行迭代,取结果最好的那次


参考:

[0]. 高斯混合模型

[1]. 高斯混合模型(GMM)

[2]. 漫谈 Clustering (3): Gaussian Mixture Model

[3]. EM及高斯混合模型

[4]. 如何通俗理解EM算法


THE END.

评论