A Kernel Two-Sample Test

1 Journal of Machine Learning Research 13 (2012) 723-773 Submitted 4/08; Revised 11/11; Published 3/12A Kernel Two-Sample TestArthur Gretton for Intelligent SystemsSpemannstrasse 3872076 T ubingen, GermanyKarsten M. Borgwardt Learning and Computational Biology Research GroupMax Planck Institutes T ubingenSpemannstrasse 3872076 T ubingen, GermanyMalte J. Rasch XinJieKouWai Key Laboratory of Cognitive Neuroscience and Learning,Beijing Normal University,Beijing, 100875, ChinaBernhard Sch for Intelligent SystemsSpemannstrasse 3872076, T ubingen, GermanyAlexander Smola Research2821 Mission College BlvdSanta Clara, CA 95054, USAE ditor:Nicolas VayatisAbstractWe propose a framework for analyzing and comparing distributions, which we use to construct sta-tistical tests to determine if two samples are drawn from different distributions. Our test statistic isthe largest difference in expectations over functions in the unit ball of a reproducing Kernel Hilbertspace (RKHS), and is called themaximum mean discrepancy(MMD).

2 We present two distribution-free tests based on large deviation bounds for the MMD, and a third test based on the asymptoticdistribution of this statistic. The MMD can be computed in quadratic time, although efficient lineartime approximations are available. Our statistic is an instance of an integral probability metric, andvarious classical metrics on distributions are obtained when alternative function classes are usedin place of an RKHS. We apply our Two-Sample tests to a varietyof problems, including attributematching for databases using the Hungarian marriage method, where they perform strongly. Ex-cellent performance is also obtained when comparing distributions over graphs, for which these arethe first such tests .. Also at Gatsby Computational Neuroscience Unit, CSML, 17 Queen Square, London WC1N 3AR, UK.. This work was carried out while was with the Ludwig-Maximilians-Universit at M unchen.

3 This work was carried out while was with the Graz University ofTechnology.. Also at The Australian National University, Canberra, ACT 0200, 2012 Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Sch olkopf and Alexander , BORGWARDT, RASCH, SCH OLKOPF ANDSMOLAK eywords: Kernel methods, Two-Sample test, uniform convergence bounds, schema matching,integral probability metric, hypothesis testing1. IntroductionWe address the problem of comparing samples from two probability distributions, by proposingstatistical tests of the null hypothesis that these distributions are equal against the alternative hy-pothesis that these distributions are different (this is called the Two-Sample problem). Such testshave application in a variety of areas. In bioinformatics, it is of interest to compare microarraydata from identical tissue types as measured by different laboratories, todetect whether the datamay be analysed jointly, or whether differences in experimental procedure have caused systematicdifferences in the data distributions.

4 Equally of interest are comparisons between microarray datafrom different tissue types, either to determine whether two subtypes of cancer may be treated asstatistically indistinguishable from a diagnosis perspective, or to detect differences in healthy andcancerous tissue. In database attribute matching, it is desirable to merge databases containing mul-tiple fields, where it is not known in advance which fields correspond: thefields are matched bymaximising the similarity in the distributions of their test whether distributionspandqare different on the basis of samples drawn from each ofthem, by finding a well behaved ( , smooth) function which is large on the points drawn fromp,and small (as negative as possible) on the points fromq. We use as our test statistic the differencebetween the mean function values on the two samples ; when this is large, the samples are likelyfrom different distributions.

5 We call this test statistic the Maximum Mean Discrepancy (MMD).Clearly the quality of the MMD as a statistic depends on the classFof smooth functions thatdefine it. On one hand,Fmust be rich enough so that the population MMD vanishes if and onlyifp=q. On the other hand, for the test to be consistent in power,Fneeds to be restrictive enoughfor the empirical estimate of the MMD to converge quickly to its expectation as the sample sizeincreases. We will use the unit balls in characteristic reproducing kernelHilbert spaces (Fukumizuet al., 2008; Sriperumbudur et al., 2010b) as our function classes, since these will be shown to satisfyboth of the foregoing properties. We also review classical metrics on distributions, namely theKolmogorov-Smirnov and Earth-Mover s distances, which are based ondifferent function classes;collectively these are known as integral probability metrics (M uller, 1997).

6 On a more practicalnote, the MMD has a reasonable computational cost, when compared with other Two-Sample tests :givenmpoints sampled frompandnfromq, the cost isO(m+n)2time. We also propose a teststatistic with a computational cost ofO(m+n): the associated test can achieve a given Type II errorat a lower overall computational cost than the quadratic-cost test, by looking at a larger volume define three nonparametric statistical tests based on the MMD. The first two tests aredistribution-free, meaning they make no assumptions regardingpandq, albeit at the expense ofbeing conservative in detecting differences between the distributions. The third test is based on theasymptotic distribution of the MMD, and is in practice more sensitive to differences in distribution atsmall sample sizes. The present work synthesizes and expands on results of Gretton et al.

7 (2007a,b)and Smola et al. (2007),1who in turn build on the earlier work of Borgwardt et al. (2006). Note that1. In particular, most of the proofs here were not provided by Grettonet al. (2007a), but in an accompanying technicalreport (Gretton et al., 2008a), which this document KERNELTWO-SAMPLETESTthe latter addresses only the third kind of test, and that the approach of Gretton et al. (2007a,b) isrigorous in its treatment of the asymptotic distribution of the test statistic under the null begin our presentation in Section 2 with a formal definition of the MMD. We review thenotion of a characteristic RKHS, and establish that whenFis a unit ball in a characteristic RKHS,then the population MMD is zero if and only ifp=q. We further show that universal RKHSs inthe sense of Steinwart (2001) are characteristic. In Section 3, we givean overview of hypothesistesting as it applies to the Two-Sample problem, and review alternative test statistics, including theL2distance between Kernel density estimates (Anderson et al.)

8 , 1994), whichis the prior approachclosest to our work. We present our first two hypothesis tests in Section 4, based on two differentbounds on the deviation between the population and empirical MMD. We take a different approachin Section 5, where we use the asymptotic distribution of the empirical MMD estimate as the basisfor a third test. When large volumes of data are available, the cost of computingthe MMD (quadraticin the sample size) may be excessive: we therefore propose in Section 6 a modified version of theMMD statistic that has a linear cost in the number of samples , and an associatedasymptotic Section 7, we provide an overview of methods related to the MMD in the statistics and machinelearning literature. We also review alternative function classes for which the MMD defines a metricon probability distributions. Finally, in Section 8, we demonstrate the performance of MMD-basedtwo-sample tests on problems from neuroscience, bioinformatics, and attribute matching using theHungarian marriage method.

9 Our approach performs well on high dimensional data with low samplesize; in addition, we are able to successfully distinguish distributions on graph data, for which oursis the first proposed Matlab implementation of the tests is gretton/ The Maximum Mean DiscrepancyIn this section, we present the maximum mean discrepancy (MMD), and describe conditions underwhich it is a metric on the space of probability distributions. The MMD is defined interms ofparticular function spaces that witness the difference in distributions: we therefore begin in by introducing the MMD for an arbitrary function space. In Section ,we compute both thepopulation MMD and two empirical estimates when the associated function spaceis a reproducingkernel Hilbert space, and in Section we derive the RKHS function thatwitnesses the MMD fora given pair of Definition of the Maximum Mean DiscrepancyOur goal is to formulate a statistical test that answers the following question:Problem 1 Let x and y be random variables defined on a topological spaceX, with respectiveBorel probability measures p and q.

10 Given observations X:={x1,..,xm}and Y:={y1,..,yn},independently and identically distributed ( ) from p and q, respectively, canwe decide whetherp6=q?Where there is no ambiguity, we use the shorthand notationEx[f(x)]:=Ex p[f(x)]andEy[f(y)]:=Ey q[f(y)]to denote expectations with respect topandq, respectively, wherex pindicatesxhasdistributionp. To start with, we wish to determine a criterion that, in the population setting, takeson a unique and distinctive value only whenp=q. It will be defined based on Lemma ofDudley (2002).725 GRETTON, BORGWARDT, RASCH, SCH OLKOPF ANDSMOLAL emma 1 Let(X,d)be a metric space, and let p,q be two Borel probability measures defined onX. Then p=q if and only ifEx(f(x)) =Ey(f(y))for all f C(X), where C(X)is the space ofbounded continuous functions (X)in principle allows us to identifyp=quniquely, it is not practical to work with sucha rich function class in the finite sample setting.