710官方网站抑或讲一下 EM,EM算法验证

GMM,即高斯混合模型(Gaussian Mixture
Model),简单地讲,就是将六个高斯模型混合起来,作为一个新的模型,这样就可以概括选拔多模型的表明能力。EM,指的是均值最大化算法(expectation-maximization),它是一种估计模型参数的策略,在
GMM 这类算法中利用广泛,因而,有时候人们又喜好把 GMM 这类可以用 EM
算法求解的模型称为 EM 算法家族。

目录

目录

这篇小说会简单提一下 GMM 模型的情节,最要紧的,仍然讲一下 EM
算法怎么样采用到 GMM 模型的参数推断上。

EM算法(1):K-means
算法

EM算法(1):K-means
算法

710官方网站 1

EM算法(2):GMM操练算法

EM算法(2):GMM练习算法

高斯混合模型

EM算法(3):EM算法运用

EM算法(3):EM算法运用

什么是 GMM

GMM 可以认为是 K-means 算法的升级版。在 K-means
中,大家会先总结出多少个聚类中央,然后依据数据点与聚类中央的相距,直接将数据点归类到目前的聚类主旨。这种做法实在很“硬”,因为有众多边缘点属于三个聚类核心的概率恐怕离开不大,假诺一股脑就径直将它归到某一个主导,实在是太野蛮了。而
GMM 不同于 K-means
的地点就在于,它除了给出聚类主旨外,仍是可以告诉你每个点归属于某个聚类焦点的几率,由此,GMM
又被称作 soft assignment。

先是,仍旧提交 GMM 模型的公式:
\[ p( x)=\sum_{k=1}^K{\pi_k N(
x|\mu_k, \Sigma_k)} \]
内部,我们规定,\(\sum_{k=1}^K{\pi_k}=1\)。可以见到,GMM
就是将多少个高斯模型线性组合起来,人们习惯上把那中间的相继高斯模型称为
Component。其中,\(\pi_k\)
表示每个模型的占比,或者说数据属于模型 k
的概率,那个值越大,表明聚集在这些模型内的数额越多。

缘何要用那种模型组合的情势吧?我们掌握,高斯模型相似成椭圆状(二维)或椭球状(三维),可以把这么些椭圆或椭球认为是一种聚类的形态,而圆心或球心则是聚类主题(对应高斯函数的参数
\(\mu\))。但实际世界中,数据的遍布并不一定都是按这样的形象分布的(如上边给出的图),由此,一个高斯模型可能没法很好的拟合这多少个数量,而假若能综合考虑几个高斯模型的表达能力,让这多少个模型发挥所长,不同的模型拟合不同的数量,那样一来,所有数据就足以很好地被这一个「组合模型」拟合起来。

实则,这种重组模型的笔触可以利用到无数模子上,比如:泊松模型。而由于高斯模型本身一些不错的特性,由此GMM 这种模型被用的可比多。

眼前说到,GMM 本质上是一种聚类算法,那么,假如已知一个 GMM
模型,现在加以一个点,大家要怎么明白那一个点属于哪个聚类大旨呢?更切实一点说,怎么领悟那一个点属于每个聚类中央的几率是多少?

用数学的语言表达就是,已知一个 GMM 模型: \(p( x)=\sum_{k=1}^K{\pi_k N( x|\mu_k,
\Sigma_k)}\),它的 K 个聚类中心为 \(C_k\),现在要求概率值 \(p( x \in C_k | x)\)。

求解的不二法门很简单,按照贝叶斯公式:\(p(a|b)=\frac{p(b|a)p(a)}{p(b)}\),我们可以得出:
\[ p( x \in C_k | x)=\frac{p(C_k)p( x|
x\in C_k)}{p( x)} \]
由此,对于每个聚类核心 \(C_k\),由于分母 \(p( x)\) 都是同等的,大家只需要总结 \(p(C_k)p( x| x\in C_k)=\pi_k N( x|\mu_k,
\Sigma_k)\) 即可。获得的值就是数量点 $ x$ 属于 \(C_k\) 的几率,至于实际要将 $ x$
归类到哪个中央,可以依照具体情状决定,比如将概率最大的当作归属的聚类中央。这一点也是
GMM 优于 K-means
的地点,前者是经过概率的法门来支配归属,由此提供了一发丰硕的新闻。

EM算法(4):EM算法验证

EM算法(4):EM算法验证

参数预计

不过,GMM 模型最难的地方在于,如何依照一堆数据点估量出模型的参数?

GMM 需要规定的参数有三类:

  1. 高斯模型的个数 \(K\),那么些参数跟
    K-means 的 \(K\)
    一样,需要人工事先设定,\(K\)
    越大,聚类的粒度也越细;
  2. \(\pi_k\), 每个 Component
    的概率分量,或者说在总样本中的占比;
  3. \(\mu_k\)、\(\Sigma_k\),各个 Component 的参数。

假定样本所属分类已知(即已知 \(x\)
属于哪个 \(C_k\)),这 GMM
的参数就很容易确定了。首先,参数 \(K\)
就一目明白拿到了。然后,假如样本容量为 \(N\),归属于聚类中央 \(C_k\) 的样本数量为 \(N_k\),归属每个 \(C_k\) 的样本集合为 \(S(k)\),可以用以下公式求出其他参数:
\[ \pi_k=\frac{N_k}{N} \\
\mu_k=\frac{1}{N_k}\sum_{ x\in S(k)}{ x} \\
\Sigma_k=\frac{1}{N_k}\sum_{ x\in S(k)}{( x-\mu_k)(
x-\mu_k)^T} \]
实在,这跟一个高斯模型的情事是均等的,只不过要依葫芦画瓢求出 \(K\) 个。

但如果样本的分类事先不清楚,又该肿么办吧?首先,由于 \(K\)
那一个值是亟需人工确定的,所以这边暂时要是 \(K\) 已经知道了。现在,大家要揣度 \(K\) 个高斯模型的概率分量 \(\pi_k\) 以及各种模型各自的参数 \(\mu_k\) 和 \(\Sigma_k\)。

最简便易行也最容易想到的章程是高大似然估计。假若有 m 个样本,首先,写出
\(p( x)=\sum_{k=1}^K{\pi_k N( x|\mu_k,
\Sigma_k)}\) 的似然函数:
\[ \begin{eqnarray} \ln{[\prod_{i=1}^m
p( x_i)]}&=&\ln{[\prod_{i=1}^m{\sum_{k=1}^K{\pi_k N(
x|\mu_k, \Sigma_k)}}]} \\
&=&\sum_{i=1}^m{\ln{[\sum_{k=1}^K{\pi_k N( x|\mu_k,
\Sigma_k)]}}} \\ \end{eqnarray} \]
不过,这么些对数函数却万分的繁杂,间接求导数的法子很难求出 \(\mu_k\) 和 \(\Sigma_k\),由此,我们只好换用其他方法来求解。而这就是
EM 算法发挥功效的地方。

 

 

均值最大化算法 EM

 

 

K-means 的启示

在标准开讲 EM 以前,我们先想起一下,K-means
是怎么求出聚类中央的。其实,总共分三步举办:

  1. 肆意起头化 K 个聚类核心的职位;
  2. 将富有样本点,按照跟各类聚类主旨的相距举办分类;
  3. 依据样本重新分类的结果,更新聚类中央的岗位,重复步骤 2
    直到收敛(即聚类主题再次调整的升幅低于某个阈值)。

既然如此 GMM 本身也属于一种聚类算法,那么,我们能无法用 K-means 的笔触来求出
GMM 的参数呢?答案自然是足以的。

而是,在那后面,我们需要先精晓 GMM 的多少个参数(\(\pi_k\),\(\mu_k\),\(\Sigma_k\))要怎么总计。要是大家曾经了解了后验概率
\(P( x \in C_k|
x)\),则可以依据以下公式统计参数(其中,m 表示样本数量):
\[ \pi_k=\frac{1}{n}\sum_{i=1}^m{P(
x_i\in C_k|x_i)} \tag{3} \]
本条公式是把富有样本属于 \(C_k\)
的几率求平均后,作为 \(C_k\)
这么些聚类主旨(或者说这么些高斯模型)的出现概率。
\[ \mu_k=\frac{\sum_{i=1}^m{
xP(x_i\in C_k|x_i)}}{\sum_{i=1}^m{P(x_i\in C_k|x_i)}} \tag{4}
\]
这多少个求均值的公式,跟单个高斯模型不同的地方在于,我们用的是加权平均。因为各种样本点都有必然的概率属于聚类中心
\(C_k\),所以,每个样本对 \(C_k\)
对应的高斯模型的均值也会生出一定的功效,只是出于 \(P(x_i\in C_k|x_i)\)
的值不同,因而这种意义也会有显然差异。
\[
\Sigma_k=\frac{\sum_{i=1}^m{P(x_i\in
C_k|x_i)(x_i-\mu_k)(x_i-\mu_k)^T}}{\sum_{i=1}^m{P(x_i\in
C_k|x_i)}} \tag{5} \]
类似地,协方差也是用加权平均求出来的。

(公式 (3) (4) (5)
其实是从极大似然函数推出去的,在周志华先生的西瓜书PRML书中都有详实推导,不过这里我只想付出感性的认识)

但是,以上公式都是基于 \(P( x \in C_k|
x)=\frac{p(C_k)p( x| x\in C_k)}{p(
x)}\)总计出来的,而以此公式本身又需要通晓 \(P(C_k)\)(即 \(\pi_k\))等参数,这就陷入一个鸡生蛋如故蛋生鸡的怪圈。

可是,借助 K-means 的思绪,大家得以优先随机伊始化这个参数,然后总计出
\(P( x \in C_k| x)\),再用它创新GMM 参数,然后再用改进的模子总括 \(P( x \in
C_k| x)\),如此迭代下去,总有没有的时候,那样,我们不就足以像
K-means 一样总计出参数了吗?!

上边,大家就模仿 K-means 的不二法门,给出迭代计量 GMM 参数的手续:

  1. 轻易起头化各种高斯模型的参数;
  2. 基于参数,总结 \(P( x \in C_k|
    x)\),这一步其实是统计出每一个样书归属于每一个聚类中央的几率;
  3. 据悉第 2 步总结拿到的 \(P( x \in C_k|
    x)\),依照公式 (3) (4) (5) 重新总计 GMM 参数,不分轩轾复步骤 2
    直到收敛。

              EM算法(3):EM算法运用

 

EM 算法

事实上,下面仿照 K-means 算法的测算步骤,就是 EM 算法的基本部分了。

EM 算法首要分为 E 和 M 两步:

  1. E 指的是 Expectation,即统计均值的历程,对应的是下面的步子
    2,这一步关键是测算每个样本归属的聚类中央;
  2. M 指的是 马克斯(Max)imum,即对参数的最大似然算计,对应的是地点的步调
    3。我面前也说了,公式 (3) (4) (5)
    统计参数的公式是用最大似然函数推出去的,所以,这一步其实是在遵照步骤
    2 的归类结果,重新用最大似然函数来臆度参数。

下边那幅图是从西瓜书上截下来的,是 EM 算法求解 GMM 参数的完整过程。

710官方网站 2

图中有众多公式标记,可能要参照原书才看得懂,然而,它的流程和本人事先交付的
3
个步骤是一律。其余,算法的平息条件得以是高达最大迭代次数,或者是似然函数(公式
(2))的进步低于某个阈值。

好了,本文到此地就不再深入下去了。EM
算法博大精深,吴军先生在《数学之美》称它为上帝的算法,可见这些算法的有力之处。EM
算法能够行使的场馆特别多,从本文给出的 GMM
例子来看,它实质上很类似梯度下降算法,在给定的对象函数很复杂、难以求解时,EM
算法用一种迭代的策略来优化起始参数,并逐渐消失到最优解。关于这一个算法的具体内容,我想进一步深刻通晓后,再用一篇小说好好写一下。

1.
内容

                EM算法(2):GMM磨炼算法

参考

  EM算法全称为
Expectation-马克斯imization

1.
简介

算法,其具体内容为:给定数据集$\mathbf{X}=\{\mathbf{x}_1,\mathbf{x}_2,…,\mathbf{x}_n\}$,假定这一个数额集是不完全的,其还缺失了有些音信Y,一个完好的样本Z

{X,Y}。而且只要假诺大家能获取完全样本新闻的话,锻炼模型就有闭式解(这些只要对于EM算法理论上得以没有,但是实际操作时我们仍然要选定这样的完全消息)。那么EM算法分为两步,第一步(E-step),按照前一步得到的参数$\theta^{(i)}$,总结目的函数的梦想$Q(\theta;\theta^{(i)})$:

            $Q(\theta;\theta^{(i)})
= E_Y[lnp(X,Y|\theta) | X,\theta^{(i)}]$

                $=\int
lnp(X,Y|\theta)\cdot p(Y|X,\theta^{(i)})dY$

  第二步,选取一个$\theta^{(i+1)}$,使得$Q(\theta;\theta^{(i)})$最大化。

 

2.
EM算法在GMM模型上的应用

  下面讲的EM算法我们自然觉得很肤浅、无法精通,这样就对了,光看那么些肯定是看不出什么来的,这些时候就需要一个事例来注解,GMM模型是最合适的。

  在采纳EM算法在此以前,大家首先要显然,缺失的Y取什么,这个得投机选用。那么由我们事先这篇博客,Y用来表示数量属于某个高斯分量最合适。y取1~k,分别代表k个高斯分量。那么很容易有$p(x,y=l|\pi,\mu,\Sigma)
= \pi_l\mathcal{N}(x|\mu_l,\Sigma_l)$,而$p(x|\pi,\mu,\Sigma)
= \sum_kp(x,y=k|\pi,\mu,\Sigma) =
\sum_k\pi_k\mathcal{N}(x|\mu_k,\Sigma_k)$,这与我么GMM模型的结果也是一律的。

  首先大家先总括$Q(\theta;\theta^{(i)})$(这里公式比较复杂,新浪的Latex相比坑,我就从来用Latex写了解后截图了):

      710官方网站 3

 

  GMM模型全称为Gaussian
Mixture
Model,即高斯混合模型。其首如果本着普通的单个高斯模型提出来的。我们了然,普通高斯模型对实际多少拟合效果还不错,不过其有一个沉重的瑕疵,就是其为单峰函数,尽管数额的真人真事分布为复杂性的多峰分布,那么单峰高斯的拟合效果就不够好了。

  其中$p(\mathbf{y}_n=k|\mathbf{x}_n,\theta^{(i)})

\frac{p(\mathbf{y}_n=k,\mathbf{x}_n|\theta^{(i)})}{p(\mathbf{x}_n|\theta^{(i)})}
= \gamma_{nk}$(推导要运用本小节第二段中的两个姿态,$\gamma_{nk}$定义见本体系第二篇博客)。

  第二步,我们对$Q(\theta;\theta^{(i)})$举行最值优化,首先对均值举行求导,则有:

    $\frac{\partial
Q}{\partial \mu_k}=0$ 得到 $\mu_k^{(i+1)} =
\frac{\sum_n\gamma_{nk}\mathbf{x}_n}{\sum_n\gamma_{nk}}$

  细心的读者也许已经发现,这与我们在第二篇博客中拿到的结果是一律的。同样,对$\pi$和$\Sigma$求导拿到的结果一律和第二篇博客中平等(有趣味的读者可以自行推导一下,其中对$\Sigma$求导可能需要参考我的另一篇博文多维高斯概率密度函数对协方差矩阵求导),这样我们就由EM算法得到了GMM的教练算法。

 

  与单峰高斯模型不同,GMM模型是三个高斯模型的加权和,具体一点就是:

            $p(\mathbf{x})\
=\
\sum_k\pi_k\mathcal{N}(\mathbf{x}|\mu_k,\Sigma_k)$  

  这是一个多峰分布,理论上,只要k丰盛大,GMM模型能拟合任何分布。

2. 困难

  GMM模型比平日高斯模型拟合能力更强了,不过对其锻炼的难度也加进了。记念一下,在教练普通高斯模型时,我们是对其分布函数去ln举行求导,具体一点就是:

            $\frac{\partial
lnp(\mathbf{x})}{\partial \mathbf{\theta}}\ =\ 0$

  那么对于普通高斯函数来说,$lnp(\mathbf{x})
= C –
\frac{1}{2}(\mathbf{x}-\mu)^T\Sigma^{-1}(\mathbf{x}-\mu)$,可以观察,ln将遍布函数中的指数情势消除了,那么对其求导很容易获取闭式解。但是对于GMM模型来说就不是那样简单了。大家得以测算一下,其概率函数取ln情势为:

            $lnp(\mathbf{x})
= ln\{
\sum_k\pi_k\mathcal{N}(\mathbf{x}|\mu_k,\Sigma_k)\}$

  我们得以看出,因为在ln里面还有加法,所以其不可以排除其中的指数形式,导致其最优化问题没有闭式解。所以想要用calculus的格局来缓解GMM模型磨练的问题是非常的。

3.
Inspiration from k-means algorithm

  没有怎么工作是一步解决不了的,假若有,这就用两步。

                        –沃
· 兹基硕德

  我们再度来看望GMM模型的表达式,其由两个高斯函数相加而成,你可以考虑一个空中中有众多高斯函数,它们各自在分级主旨点所在的职位。一个一维的五个高斯混合的模子示意如下:

          710官方网站 4

  那么对于其它一个点,都有其最靠近的一个峰。比如在当中峰处的点,其概率几乎全是缘于于第二个高斯分布。那么我们就足以如此想,是不是每个点都有其更加偏向的高斯峰呢?等等,那个想法近乎在哪个地方见过?k-means算法中的第一步不就是干的这事吗?将各种点都分配给近期的一个类。但是,我们这里怎么去度量距离吗?继续运用点到基本的偏离?这样类似把各类高斯的方差忽略掉了。那么既然是概率模型,最好的办法就是用概率来相比。对于一个点$\mathbf{x}$,第k个高斯对其的孝敬为$\pi_k\mathcal{N}(\mathbf{x}|\mu_k,\Sigma_k)$,那么把$\mathbf{x}$分配给进献最大的一个,这样看起来把各种要素考虑进去,似乎很有理了。

  不过,大家发现,假若一个点处于六个峰之间吧,那样把其归为任何一个峰都不太好吧?当然,k-means也未尝解决那一个问题,可是我们这边是概率模型,我们有更好的讲述方法,我们得以测算一个点$\mathbf{x}$属于每个高斯的几率。这样的考虑就比较完美了。那么点$\mathbf{x}$属于每个高斯的票房价值自然就取这一个高斯对其的进献$\pi_k\mathcal{N}(\mathbf{x}|\mu_k,\Sigma_k)$。为了使其变为一个概率,我们还索要对其归一化,所以博得第n个数据点属于第k个高斯的票房价值:

            $\gamma_{nk}=\frac{\pi_k\mathcal{N}(\mathbf{x}_n|\mu_k,\Sigma_k)}{\sum_j\pi_j\mathcal{N}(\mathbf{x}_n|\mu_j,\Sigma_j)}$

  遵照k-means算法,第二步就是把$\gamma_{nk}$当做已知去做最优化。这里既是是要拟合分布,那么就采取最大似然的措施,最大化$lnp(\mathbf{X})$。那么这里就有一个题目了:在k-means算法中,目的函数是有$r_{nk}$这一项的,可是$lnp(\mathbf{X})$中并没有$\gamma_{nk}$这一项呀,我怎么把其看成已知的吗?这里我们不急,暂时不去管这个,大家先总计$\frac{\partial
lnp(\mathbf{X})}{\partial \mu_k}$:

            $\frac{\partial
lnp(\mathbf{X})}{\partial \mu_k}\ =\ -\
\sum_n\frac{\pi_k\mathcal{N}(\mathbf{x}_n|\mu_k,\Sigma_k)}{\sum_j\pi_j\mathcal{N}(\mathbf{x}_n|\mu_j,\Sigma_k)}\Sigma_k(\mathbf{x}_n\
-\ \mu_k) $      (1)

  我们的$\gamma_{nk}$是不是曾经冒出了,那么上式可以简写为:

            $\ -\
\sum_n\gamma_{nk}\Sigma_k(\mathbf{x}_n\ -\
\mu_k)$

  令其等于0,可以得到:

            $\mu_k\ =\
\frac{\sum_n\gamma_{nk}\mathbf{x}_n}{\sum_n\gamma_{nk}}$              (2)

  可以看出,其与k-means算法第二步主题点的算计办法$\mu_k=\frac{\sum_nr_{nk}\mathbf{x}_n}{\sum_nr_{nk}}$非凡相似。

  类似的,对$\Sigma_k$求导,可以取得:

            $\Sigma_k\ =\
\frac{\sum_n\gamma_{nk}(\mathbf{x}_n-\mu_k)(\mathbf{x}_n-\mu_k)^T}{\sum_n\gamma_{nk}}$        (3)

  对$\pi_k$求导,可以拿到:

            $\pi_k\ =\
\frac{\sum_n\gamma_{nk}}{\sum_k\sum_n\gamma_{nk}}$
              (4)

  自此,GMM磨炼方法就收获了,第一步,使用式(1)总结所有点的属于各种高斯的票房价值;第二步,利用式(2),(3),(4)更新均值、方差和权值。重复这两步直到收敛。

4.
与EM算法的涉嫌

  这里我们是从k-means算法出发拿到的GMM磨练算法,那么其与EM算法的涉及与k-means算法和EM算法的涉及近乎。同样,我们前边可以看出,利用EM算法可以推导出GMM练习算法。

相关文章