011 精读2017年NIPS最佳研究论文之二:KSD测试如何检验两个分布的异同?

本周我们来分析和探讨NIPS 2017上的三篇最佳论文。周一我们分享的文章主要研究的是一种“健壮的优化问题”,也就是说我们在优化一个“损失函数”的时候,不仅要考虑损失函数的“均值”,还要考虑损失函数的“方差”。

今天,我们来看另外一篇最佳论文《线性时间内核拟合优度测试》(A Linear-Time Kernel Goodness-of-Fit Test),讲的是如何来衡量一组数据是否来自于某一个分布。

今天的这篇文章理论性也很强,这里我尝试从更高的维度为你做一个归纳,如果对文章内容感兴趣,建议你一定要去阅读原文。

作者群信息介绍

本文一共有五位作者,我们在这里进行一个简要介绍。

第一作者叫维特瓦特·吉特克鲁特(Wittawat Jitkrittum),刚从伦敦大学学院(University College London)的“加斯比计算人脑科学所”(Gatsby Computational Neuroscience Unit)博士毕业。他在博士期间的主要研究是“统计测试”(Statistical Tests),特别是如何利用“核方法”(Kernel Method)来对“分布特征”(Distributional Features)进行测试。吉特克鲁特在泰国完成本科学习,于日本京的东京科技学院(Tokyo Institute Of Technology)获得硕士学位。最近几年,吉特克鲁特已经在NIPS、ICML、UAI等会议连续发表了多篇高质量论文,可以说是统计测试界的学者新秀。

第二作者许文凯(Wenkai Xu)是加斯比计算人脑科学所的一名博士生。

第三作者佐尔坦·萨博(Zoltán Szabó)来自法国一所著名的理工大学“巴黎综合理工学院”(École Polytechnique)。萨博之前也曾在加斯比计算人脑科学所工作过,目前在巴黎综合理工学院任职研究副教授(类似于研究员),长期从事核方法、信息论(Information Theory)、统计机器学习等方面的研究。

第四作者福水健次(Kenji Fukumizu)是“统计数学学院”(The Institute of Statistical Mathematics)的教授,长期从事核方法的研究,可以说是这方面的专家。

最后一个作者阿瑟·格里顿(Arthur Gretton)是加斯比计算人脑科学所的机器学习教授,长期从事机器学习,特别是核方法的研究。他的论文有9千多次的引用数。

论文的主要贡献和核心方法

我们首先来看一下这篇文章的主要贡献,理解这篇文章主要解决了什么场景下的问题。

在一般的建模场景里,我们常常会对一组数据提出一个模型,来描述产生这些数据背后的过程。这个过程我们通常是看不见的,是一个隐含的过程。那么,当我们提出了模型之后,如何知道用这个模型描述现实就是准确的呢?这时候我们就需要用到一些统计检验(Statistical Testing)的方法。

一种比较普遍的方法,那就是假设我们的模型是P,而数据的产生分布是Q。说得直白一些,就需要去验证P是不是等于Q,也就是需要验证两个分布是否相等。一个基本的做法就是,从P里“产生”(Generate)一组样本,或者叫一组数据,然后我们已经有了一组从Q里产生的数据,于是用“两个样本假设检验”(Two Sample Tests)来看这两组数据背后的分布是否相等。

这个想法看似无懈可击,但是在实际操作中往往充满困难。最大的操作难点就是从P中产生样本。比如P是一个深度神经网络模型,那从中产生样本就不是一个简单且计算效率高的流程,这就为基于“两个样本假设检验”带来了难度。

另一方面,我们在做这样的统计检验的时候,最好能够针对每一个数据点,得到一个数值,来描述当前数据点和模型之间的关系,从而能够给我们带来更加直观的认识,看模型是否符合数据。

这里,有一种叫作“最大均值差别”(Maximum Mean Discrepancy),或者简称为 MMD 的检验方法能够达到这样的效果。MMD的提出者就是这篇论文的最后一位作者阿瑟·格里顿,MMD是在NIPS 2016提出的一个检验两个样本是否来自同一个分布的一种方法。当MMD值大的时候,就说明这两个样本更有可能来自不同的分布。

和一般的衡量两个分布距离的方法相比,MMD的不同之处是把两个分布都通过核方法转换到了另外一个空间,也就是通常所说的“再生核希尔伯特空间”(Reproducing Kernel Hilbert Space),或者简称为 RKHS。在这个空间里,测量会变得更加容易。然而遗憾的是,MMD依然需要得到两个分布的样本,也就是说我们依然需要从P里得到样本。

那么,这篇文章的最大贡献,就是使用了一系列的技巧让P和Q的比较不依赖于从P中得到样本,从而让数据对于模型的验证,仅仅依赖于P的一个所谓的“打分函数”(Score Function)。

其实在MMD里,这个打分函数就是存在的,那就是针对我们从P或者是Q里抽取出来的样本,我们先经过一个函数F的变换,然后再经过一个叫“核函数”T的操作,最后两个样本转换的结果相减。

在这篇文章里,作者们提出了一个叫“核斯特恩差异”(Kernel Stein Discrepancy),或者叫KSD测试的概念,本质上就是希望能够让这两个式子中关于P的项等于零。

什么意思呢?刚才我们说了MMD的一个问题是依然要依赖于P,依赖于P的样本。假设我们能够让依赖P的样本这一项成为零,那么我们这个测试就不需要P的样本了,那也就是绕过了刚才所说的难点。

KSD的本质就是让MMD的第二项在任何时候都成为零。注意,我们这里所说的是“任何时候”,也就是说,KSD构造了一个特殊的T,这个T叫作“斯特恩运算符”(Stein Operator),使得第二项关于P的样本的计算,在任何函数F的情况下都是零,这一点在文章中提供了详细证明。于是,整个KSD就不依赖于P的样本了。

这篇文章不仅阐述了KSD的思想,而且在KSD的思想上更进了一步,试图把KSD的计算复杂度,也就是在平方级别的计算复杂度变为线性复杂度。什么意思呢?也就是说,希望能够让KSD的计算复杂度随着数据点的增加而线性增加,从而能够应用到大数据上。这个内容我们就不在这里复述了。

方法的实验效果

虽然这篇文章的核心内容是一个理论结果,或者是算法革新,文章还是在“受限波兹曼机”(Restricted Boltzmann Machine),简称RBM上做了实验。本质上就是在RBM的某一个链接上进行了简单的改变而整个模型都保持原样。

如果我们有从这两个RBM中得到的样本,其实是很难知道他们之间的区别的。在实验中,传统的MMD基本上没法看出这两个样本的差别。然而不管是KSD,还是线性的KSD都能够得出正确的结论,而最终的线性KSD基本上是随着数据点的增多而性能增加,达到了线性的效果。

最后,作者们用了芝加哥犯罪记录来作为说明,使用“打分函数”来形象地找到哪些点不符合模型。应该说,理论性这么强的论文有如此直观的结果,实在难能可贵。

小结

今天我为你讲了NIPS 2017年的另外一篇最佳研究论文,文章的一个核心观点是希望能够通过构建一个特殊的运算符,使得传统的通过样本来检验两个分布的异同的方法,比如MMD方法,可以不依赖于目标分布的样本,并且还能达到线性计算速度。

一起来回顾下要点:第一,我们简要介绍了这篇文章的作者群信息。第二,我们详细介绍了这篇文章要解决的问题以及贡献 。第三,我们简要地介绍了文章的实验结果 。

最后,给你留一个思考题,这种衡量分布之间距离的想法,除了在假设检验中使用以外,在机器学习的哪个环节也经常碰到?