Bengxy
Little steps lead to great distances.
GMM高斯混合模型和EM算法
2016-03-11 Leave a comment

GMM高斯混合模型和EM算法

有许多讲高斯混合模型Gaussian Mixed Model(GMM)的文章,但很多都是一上来就套理论,讲公式。但对于机器学习的新人来说就比较难理解:受到什么样启发我们提出GMM?GMM适用哪些场景?以及GMM的理论支撑EM是如何保证GMM收敛的?

因此我整理了自己在学GMM时候的困惑以及一些理解。

GMM: 高斯混合模型假设了数据服从K个混合的高斯分布。更通俗的讲:

数据能够由K个确定的高斯分布以一定的权重叠加生成。

求解高斯混合模型,就是要从数据集拟合出这K个高斯分布的参数 $\theta_k=(\mu_k, \sigma_k)$

一维数据上的思考

一维有监督分类(数据有标签)

我们从简单数据开始,考虑一个一维有标签数据的拟合问题。

已知两类数据,服从下图的高斯分布,求解他们的参数$\mu_a$、$\mu_b$和$\sigma_a$、$\sigma_b$

image-20190814135547377

这很简单,对每个类求解极大似然估计。以类a为例,我们求解高斯分布的导数$ \frac{\partial ln L(\theta)}{\partial \theta} = 0 $

对于$\mu$:

$$ \frac{\partial ln L(\mu) } {\mu} = \bar{x}-\mu = 0 $$

$$\mu = \bar{x} = \frac{1}{n} \sum_{i=1}^{n} x_i$$

对于$\sigma$

$$ \frac{\partial ln L(\sigma)} {\sigma} = -\frac{1}{\sigma}+\frac{(x-\mu)^2 }{\sigma^3 } = 0 $$

$$\sigma^2 = \overline{(x-\mu)^2}= \frac{1}{n}\sum_{i=1}^n(x_i - \bar{x})^2$$

最后按照这个高斯分布,计算 $ f(x;N(\mu_1, \sigma_1)) > f(x; N(\mu_2, \sigma_2)) $即可获得分类边界。

一维无监督聚类(数据无标签)

现在我们考虑下面的问题

对于下图,告诉你这个分布是两个高斯分布叠加而成的,求解他们的参数$\mu_a$、$\mu_b$和$\sigma_a$、$\sigma_b$

image-20190814135648247

GMM就是为了解决这一问题。

GMM分步演示

在上面有监督的例子中,如果我们知道了每个数据$x_i$的label,我们可以求解出高斯参数。但第二个无监督问题的难点在于,我们事先并不知道数据 $x_i $的label。

GMM解决问题的思路是,我们可以构造一个隐变量$z_k$,用来表示数据$x_i$ 从第$k$个高斯函数派生的概率。

这个可以发现,GMM和K-means有一个本质区别是:

  • GMM认为,每个样本点是以一定的概率从k个分布中导出,并非严格从属于某个类别。
  • 而K-means认为,每个点只属于一个类别,非对即错。

因此GMM是Soft-Cluster而K-means是Hard-Cluster。

按照这个思路,我们先随机设定高斯参数 $\theta_k$

  1. 获取高斯参数$\theta_k$
  2. 根据当前的高斯参数$\theta_k$ ,对所有点${x_i}$从属的类别进行概率划分,得到隐变量$Z$
  3. 固定$Z$,按照极大似然,求解新一轮的高斯模型参数$\theta_k$
  4. 重复Step 1

我们用一个可视化的例子走一遍:

Step 1

我们获取两个高斯参数$\theta_k$ ,如下图(在第一次,我们随机设定参数)

image-20190814143826779

Step 2

对所有的数据点进行软划分。

image-20190814145234951

这里,我随机采样了 {-7.5, -2.5, 0, 2.5, 7.5},他们从属类别A和B的概率如下表

隐变量Z -7.5 2.5 0 2.5 7.5
Red ~1 0.9995 0.5 0.0005 0
Blue 0 0.0005 0.5 0.9995 ~1

Step 3

现在我们有了在参数$\theta_k$ 条件下的隐变量$Z$,我们固定住隐变量$Z$,并用真实数据(黑线上的数据)代入,重新求解下一轮的高斯参数。算出的隐变量$Z$,等效于在计算高斯参数$\theta = (\mu, \sigma)$时,对样本集合$x_i$做了不同程度的加权。

新计算出的的高斯分布如下,可以发现,两个高斯分布正开始向着我们希望的目标拟合

image-20190814150421906

Step 4

接着,我们将计算出的高斯参数$\theta_k$带回到 Step 1,开始下一轮迭代。最终,红线和蓝线会逐渐拟合到预期的位置。

EM算法

上述的步骤我们称之为EM算法(Expectation Maximization Algorithm)

Step 2是通过假设的高斯模型和真实data,预估隐变量的值,我们称之为E-Step。

Step 3是用最大似然法求解高斯参数,我们称之为M-Step。

其实GMM和K-means非常类似,都是依赖于这两步:

  1. 固定一个参数(GMM固定了高斯分布的参数$\theta=(\mu, \sigma)$,而K-means选择了一个中心。
  2. 把每个data放到对应的类别里(GMM是按照概率,每个点以一定概率存在于某个类,K-means是直接分类)。

但这里有个问题!我们能否保证上述策略可以收敛?

GMM & EM的理论支撑

上图中的黑色线条,是两个高斯分布的和

$$ P(x|\theta) = \sum_{k=1}^K \phi (x,z_k;\theta_k)$$

在所有的样本空间X上计算极大似然时:

$$\sum_i^n ln p(x_i; \theta) = \sum_i^n ln \sum_k^K \phi(x_i, z_k;\theta_k)$$

我们用$Q(z_i)$ 表示隐变量的分布,根据Jensen不等式, 把$z_k$ 提取出来,上式

$$= \sum_i^n ln \sum_k^K Q(z_k) \frac{\phi(x_i;\theta_k)} {Q(z_k)} $$

$$\geq \sum_i^n \sum_k^K Q(z_k) ln \frac{\phi(x_i;\theta_k)} {Q(z_k)} = h(x)$$

因此,最大化 $h(x)$ 和最大化似然函数等价。

本文作者:Bengxy

本文采用署名-非商业性使用 4.0 国际 (CC BY-NC 4.0)协议

本文链接:http://blog.bengxy.com/posts/c31bab3b/

Machine Learning GMM EM