PRML读书会第九章 Mixture Models and EM

Deep Learning Specialization on Coursera

PRML读书会第九章 Mixture Models and EM

主讲人 网络上的尼采

(新浪微博: @Nietzsche_复杂网络机器学习

网络上的尼采(813394698) 9:10:56
今天的主要内容有k-means、混合高斯模型、 EM算法。
对于k-means大家都不会陌生,非常经典的一个聚类算法,已经50多年了,关于clustering推荐一篇不错的survey:

Data clustering: 50 years beyond K-means。k-means表达的思想非常经典,就是对于复杂问题分解成两步不停的迭代进行逼近,并且每一步相对于前一步都是递减的。
k-means有个目标函数 :

假设有k个簇,是第k个簇的均值;每个数据点都有一个向量表示属于哪个簇,rnk是向量的元素,如果点xn属于第k个簇,则rnk是1,向量的其他元素是0。
上面这个目标函数就是各个簇的点与簇均值的距离的总和,k-means要做的就是使这个目标函数最小。 这是个NP-hard问题,k-means只能收敛到局部最优。

算法的步骤非常简单:
先随机选k个中心点
第一步也就是E步把离中心点近的数据点划分到这个簇里;
第二步M步根据各个簇里的数据点重新确定均值,也就是中心点。
然后就是迭代第一步和第二步,直到满足收敛条件为止。
自强<ccab4209211@qq.com> 9:29:00
收敛是怎么判断的呀?
网络上的尼采(813394698) 9:30:16
不再发生大的变化。大家思考下不难得出:无论E步还是M步,目标函数都比上一步是减少的。 下面是划分两个簇的过程 :

下面这个图说明聚类过程中目标函数单调递减,经过三轮迭代就收敛了,由于目标函数只减不增,并且有界,所以k-means是可以保证收敛的:


 书里还举例一个k-means对图像分割和压缩的例子:

图像分割后,每个簇由均值来表示,每个像素只存储它属于哪个簇就行了。压缩后图像的大小是k的函数 :

现在讨论下k-means的性质和不足 :

首先对初值敏感 ,由于只能收敛到局部最优,初值很大程度上决定它收敛到哪里;

从算法的过程可以看出,k-means对椭球形状的簇效果最好 ,不能发现任意形状的簇;

对孤立点干扰的鲁棒性差,孤立点是异质的,可以说是均值杀手,k-means又是围绕着均值展开的,试想下,原离簇的孤立点对簇的均值的拉动作用是非常大的。
针对这些问题后来又有了基于密度的DBSCAN算法,最近Science上发了另一篇基于密度的方法:Clustering by fast search and find of density peaks。基于密度的方法无论对clustering还是outliers detection效果都不错,和k-means不同,这些算法已经没有了目标函数,但鲁棒性强,可以发现任意形状的簇。
另外如何自动确定k-means的k是目前研究较多的一个问题。k-means就到这里,现在一块讨论下。

口水猫(465191936) 9:49:20
如果对于这批数据想做k-mean 聚类,那么如果去换算距离?
网络上的尼采(813394698) 9:49:53
k-means一般基于欧式距离,关于距离度量是个专门的方向,点集有了度量才能有拓扑,有专门的度量学习这个方向。
口水猫(465191936) 9:50:08
嗯嗯 有没有一些参考意见了,k的选择可以参考coursera上的视频 选择sse下降最慢的那个拐点的k

网络上的尼采(813394698) 9:51:41

关于选哪个k是最优的比较主观,有从结果稳定性来考虑的,毕竟一个算法首先要保证的是多次运行后结果相差不大,关于这方面有一篇survey:
Clustering stability an overview。另外还有其他自动选k的方法,DP、MDL什么的。MDL是最短描述长度,从压缩的角度来看k-means;DP是狄利克雷过程,一种贝叶斯无参方法,感兴趣可以看JORDAN小组的文章。

 

我们下面讲混合高斯模型GMM,第二章我们说过,高斯分布有很多优点并且普遍存在,但是单峰函数,所以对于复杂的分布表达能力差,我们可以用多个高斯分布的线性组合来逼近这些复杂的分布。我们看下GMM的线性组合形式:


对于每个数据点是哪个分布生成的,我们假设有个Z隐变量 ,和k-means类似,对于每个数据点都有一个向量z,如果是由第k个分布生成,元素zk=1,其他为0。
zk=1的概率的先验就是高斯分布前的那个系数:


下面是zk=1概率的后验,由贝叶斯公式推导的:


其实很好理解,如果没有限制,数据点由哪个分布得出的概率大zk=1的期望就大,但前面还有一个系数限制,所以期望形式是:


刚才有人问如何确定模型的参数,我们首先想到的就是log最大似然:

但是我们可以观察下这个目标函数,log里面有加和,求最优解是非常困难的,混合高斯和单个高斯的参数求法差别很大,如果里面有一个高斯分布坍缩成一个点,log似然函数会趋于无穷大。由于直接求解困难,这也是引入EM的原因。
下面是GMM的图表示 :

我们可以试想下,如果隐变量zn是可以观测的,也就是知道哪个数据点是由哪个分布生成的,那么我们求解就会很方便,可以利用高斯分布直接得到解析解。 但关键的是zn是隐变量,我们没法观测到。但是我们可以用它的期望来表示。 现在我们来看一下EM算法在GMM中的应用:

上面是EM对GMM的E步
我们首先对模型的参数初始化
E步就是我们利用这些参数得znk的期望,这种形式我们前面已经提到了:

现在我们有隐藏变量的期望了,由期望得新的模型参数也就是M步,高斯分布的好处就在这儿,可以推导出新参数的闭式解:

然后不断迭代E步和M步直到满足收敛条件。

为什么要这么做,其实EM算法对我们前面提到的log最大似然目标函数:是单调递增的。
karnon(447457116) 10:39:42
用EM来解GMM其实是有问题的,解出来的解并不是最优的。。
网络上的尼采(813394698) 10:40:14
嗯,这个问题最后讲。

我们再来看EM更一般的形式:

是我们的目标函数,加入隐藏变量可以写成这种形式:

先初始化模型的参数,由于隐变量无法观测到,我们用参数来得到它的后验

然后呢,我们通过隐藏变量的期望得到新的完整数据的最大似然函数:


以上是E步M步是求这个似然函数的Q函数的最优解,也就是新的参数:

注意这个Q函数是包含隐变量的完整数据的似然函数,不是我们一开始的目标函数

其实求完整数据的最大似然是在逼近我们目标函数的局部最优解,这个在后面讲。
下面这个是一般化EM算法的步骤:
EM算法只所以用途广泛在于有潜在变量的场合都能用,并不局限于用在GMM上。现在我们回过头来看混合高斯模型的M步,这些得到的新参数就是Q函数的最优解:


再思考下k-means,其实它是EM的特例,只不过是k-means对数据点的分配是硬性的,在E步每个数据点必须分配到一个簇,z里面只有一个1其他是0,而EM用的是z的期望:

下面这个图说明k-means是EM算法特例,这与前面k-means聚类的过程的图对应:


对于EM算法性质的证明最后讲,下面讲混合伯努利模型,高斯分布是针对连续的属性,伯努利是针对离散属性。混合形式:


 目标函数,log里面同样有加和:


znk=1的期望:

Q函数:


以上是E步,下面是M步的解,这两个:


其中:


书里举了一个手写字聚类的例子 ,先对像素二值化 ,然后聚成3个簇:

这是3个簇的代表:


k=1时簇的代表:

=============================================================

最后说下EM算法为什么能收敛到似然函数的局部最优解:

我们的目标函数是分布的最大log似然

引入潜在变量,分布表示为:

定义隐藏变量的分布为q(z),目标函数可以表达为下面形式,这个地方是神来一笔:


其中与q(z)的KL散度;是q(z)的泛函形式。
我们原来讲过根据Jensen不等式来证明KL散度是非负的,这个性质在这里发挥了作用。由于是大于等于零的,所以是目标函数的下界。与目标函数什么时候相等呢?其实就是等于0的时候,也就是q(z)与z的后验分布相同时,这个时候就是E步z取它的期望时候。与目标函数相等是为了取一个比较紧的bound。
M步就是最大化,随着的增大,开始大于0,也就是目标函数比增大的幅度更大。这个过程是使目标函数一直单调递增的。下面是与Q函数的关系,这也是为什么M步新参数取完整数据的最大似然解的原因:

最后上一张非常形象的图,解释为什么EM能收敛到目标函数的局部最优:

红的曲线是目标函数;蓝的绿的曲线是两步迭代。
咱们先看蓝的E步和M步:

E步时就是取z的期望的时候,这时目标函数与相同;
M步就是最大化
绿线是下一轮的迭代,EM过程中,目标函数一直是单调上升的,并且有界,所以EM能够保证收敛。但不一定能收敛到最优解,这与初始值有很大关系,试想一下,目标函数的曲线变动下,EM就有可能收敛到局部最优了。

注:PRML读书会系列文章由 @Nietzsche_复杂网络机器学习 同学授权发布,转载请注明原作者和相关的主讲人,谢谢。

PRML读书会讲稿PDF版本以及更多资源下载地址:http://vdisk.weibo.com/u/1841149974

本文链接地址:http://www.52nlp.cn/prml读书会第九章-mixture-models-and-em

Deep Learning Specialization on Coursera

PRML读书会第九章 Mixture Models and EM》上有1条评论

  1. 斑马行空

    “目标函数可以表达为下面形式,这个地方是神来一笔”,请问这个公式是如何推导出来的??自己推导了半天也推不出,求指导。

    [回复]

发表评论

电子邮件地址不会被公开。 必填项已用*标注