A kernel method for the two-sample-problem

Arthur Gretton; Karsten M. Borgwardt; Malte Rasch; Bernhard Schölkopf; Alexander J. Smola

A kernel method for the two-sample-problem

Arthur Gretton^*, Karsten M. Borgwardt, Malte Rasch, Bernhard Schölkopf, Alexander J. Smola

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1143 Citations (Scopus)

Abstract

We propose two statistical tests to determine if two samples are from different distributions. Our test statistic is in both cases the distance between the means of the two samples mapped into a reproducing kernel Hilbert space (RKHS). The first test is based on a large deviation bound for the test statistic, while the second is based on the asymptotic distribution of this statistic. The test statistic can be computed in O(m ²) time. We apply our approach to a variety of problems, including attribute matching for databases using the Hungarian marriage method, where our test performs strongly. We also demonstrate excellent performance when comparing distributions over graphs, for which no alternative tests currently exist.

Original language	English
Title of host publication	Advances in Neural Information Processing Systems 19 - Proceedings of the 2006 Conference
Pages	513-520
Number of pages	8
Publication status	Published - 2007
Event	20th Annual Conference on Neural Information Processing Systems, NIPS 2006 - Vancouver, BC, Canada Duration: 4 Dec 2006 → 7 Dec 2006

Publication series

Name	Advances in Neural Information Processing Systems
ISSN (Print)	1049-5258

Conference

Conference	20th Annual Conference on Neural Information Processing Systems, NIPS 2006
Country/Territory	Canada
City	Vancouver, BC
Period	4/12/06 → 7/12/06

Cite this

@inproceedings{0e74c350d0e64497956b583f51fc25ff,

title = "A kernel method for the two-sample-problem",

abstract = "We propose two statistical tests to determine if two samples are from different distributions. Our test statistic is in both cases the distance between the means of the two samples mapped into a reproducing kernel Hilbert space (RKHS). The first test is based on a large deviation bound for the test statistic, while the second is based on the asymptotic distribution of this statistic. The test statistic can be computed in O(m 2) time. We apply our approach to a variety of problems, including attribute matching for databases using the Hungarian marriage method, where our test performs strongly. We also demonstrate excellent performance when comparing distributions over graphs, for which no alternative tests currently exist.",

author = "Arthur Gretton and Borgwardt, {Karsten M.} and Malte Rasch and Bernhard Sch{\"o}lkopf and Smola, {Alexander J.}",

year = "2007",

language = "English",

isbn = "9780262195683",

series = "Advances in Neural Information Processing Systems",

pages = "513--520",

booktitle = "Advances in Neural Information Processing Systems 19 - Proceedings of the 2006 Conference",

note = "20th Annual Conference on Neural Information Processing Systems, NIPS 2006 ; Conference date: 04-12-2006 Through 07-12-2006",

}

Gretton, A, Borgwardt, KM, Rasch, M, Schölkopf, B & Smola, AJ 2007, A kernel method for the two-sample-problem. in Advances in Neural Information Processing Systems 19 - Proceedings of the 2006 Conference. Advances in Neural Information Processing Systems, pp. 513-520, 20th Annual Conference on Neural Information Processing Systems, NIPS 2006, Vancouver, BC, Canada, 4/12/06.

A kernel method for the two-sample-problem. / Gretton, Arthur; Borgwardt, Karsten M.; Rasch, Malte et al.
Advances in Neural Information Processing Systems 19 - Proceedings of the 2006 Conference. 2007. p. 513-520 (Advances in Neural Information Processing Systems).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A kernel method for the two-sample-problem

AU - Gretton, Arthur

AU - Borgwardt, Karsten M.

AU - Rasch, Malte

AU - Schölkopf, Bernhard

AU - Smola, Alexander J.

PY - 2007

Y1 - 2007

N2 - We propose two statistical tests to determine if two samples are from different distributions. Our test statistic is in both cases the distance between the means of the two samples mapped into a reproducing kernel Hilbert space (RKHS). The first test is based on a large deviation bound for the test statistic, while the second is based on the asymptotic distribution of this statistic. The test statistic can be computed in O(m 2) time. We apply our approach to a variety of problems, including attribute matching for databases using the Hungarian marriage method, where our test performs strongly. We also demonstrate excellent performance when comparing distributions over graphs, for which no alternative tests currently exist.

AB - We propose two statistical tests to determine if two samples are from different distributions. Our test statistic is in both cases the distance between the means of the two samples mapped into a reproducing kernel Hilbert space (RKHS). The first test is based on a large deviation bound for the test statistic, while the second is based on the asymptotic distribution of this statistic. The test statistic can be computed in O(m 2) time. We apply our approach to a variety of problems, including attribute matching for databases using the Hungarian marriage method, where our test performs strongly. We also demonstrate excellent performance when comparing distributions over graphs, for which no alternative tests currently exist.

UR - http://www.scopus.com/inward/record.url?scp=84864063983&partnerID=8YFLogxK

M3 - Conference contribution

SN - 9780262195683

T3 - Advances in Neural Information Processing Systems

SP - 513

EP - 520

BT - Advances in Neural Information Processing Systems 19 - Proceedings of the 2006 Conference

T2 - 20th Annual Conference on Neural Information Processing Systems, NIPS 2006

Y2 - 4 December 2006 through 7 December 2006

ER -

A kernel method for the two-sample-problem

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this