A Kernel Method for the Two-Sample-Problem
By Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, Alex Smola. 2006
2,657 citations recorded by the source corpus.
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(m2) 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.
Subfields: Artificial Intelligence, Statistics and Probability, Statistical Learning Theory, Signal Processing
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Yoshua Bengio
- Sergey Levine
- Mohit Bansal
- Dacheng Tao
- Bernhard Schölkopf
- Trevor Darrell
- Quoc V. Le
- Percy Liang
In Statistics and Probability
- Bernhard Schölkopf
- Arthur Gretton
- Kenji Fukumizu
- Bharath K. Sriperumbudur
- Krikamol Muandet
- Dino Sejdinovic
- Alex Smola
- David Lopez-Paz
In Statistical Learning Theory
- Arthur Gretton
- Kenji Fukumizu
- Bernhard Schölkopf
- Bharath K. Sriperumbudur
- Krikamol Muandet
- Dino Sejdinovic
- Le Song
- Francis R. Bach
In Signal Processing
- Bernhard Schölkopf
- Yoshua Bengio
- Stefano Ermon
- Arthur Gretton
- Kenji Fukumizu
- David Lopez-Paz
- Bharath K. Sriperumbudur
- Mingsheng Long
Citations in the corpus
- Neural Autoregressive Distribution Estimation (2016, methodology): “Li et al. (2015) instead propose a training objective derived from Maximum Mean Discrepancy (MMD; Gretton et al., 2007).”
- Diagnosing and Enhancing VAE Models (2019, methodology): “We also used these same sample matrices to estimate the MMD metric (Gretton et al., 2007) between N (0, I) and the aggregated posterior distributions from the first and second stages in Table 4.”
- A note on the evaluation of generative models (2015, methodology): “…on the log-likelihood (Bishop, 2006), noise-contrastive estimation (Gutmann & Hyv¨arinen, 2010), probability flow (Sohl-Dickstein et al., 2011), maximum mean discrepancy (MMD) (Gretton et al., 2007; Li et al., 2015), or approximations to the Jensen-Shannon divergence (JSD) (Goodfellow et al., 2014).”
- Generative Moment Matching Networks (2015, methodology): “The key idea behind GMMNs is the use of a statistical hypothesis testing framework called maximum mean discrepancy (Gretton et al., 2007).”
- Learning Adversarially Fair and Transferable Representations (2018, methodology): “We give two metrics: maximum mean discrepancy (MMD) (Gretton et al., 2007), which is a general measure of distributional distance; and adversarial accuracy (if an adversary is given these representations, how well can it learn to predict the sensitive attribute?).”
- A Survey on Multi-Task Learning (2017, background): “Since Ψ models the covariance between pairs of tasks, it can be determined based on the maximum mean discrepancy (MMD).”
- DISCO Nets : DISsimilarity COefficients Networks (2016, background): “[8, 9]) is a statistical hypothesis test assessing if two probabilistic distributions are similar.”
- The Variational Fair Autoencoder (2015, methodology): “The resulting estimator is known as Maximum Mean Discrepancy (MMD) (Gretton et al., 2006): `MMD(X,X ′) = 1 N20 N0∑ n=1 N0∑ m=1 k(xn,xm) + 1 N21 N1∑ n=1 N1∑ m=1 k(x′n,x ′ m)− 2 N0N1 N0∑ n=1 N1∑ m=1 k(xn,x ′ m).”
- On the Fairness of Disentangled Representations (2019, background): “In practice, [63] extends the VAE objective with a Maximum Mean Discrepancy [33] to ensure independence between the latent representation and the sensitive factors.”
- Causal Generative Neural Networks (2017, methodology): “CGNNs learn functional causal models (Section 2) as generative neural networks, trained by backpropagation to minimize the Maximum Mean Discrepancy (MMD) [Gretton et al. , 2007; Li et al. , 2015] between the observational and the generated data (Section 3).”
- Multi-Source Domain Adaptation: A Causal View (2015, methodology): “2 Parameter Estimation by Reproducing the Target Feature Distribution We can estimate the parameters βij , and hence αij and P Y , by minimizing the maximum mean discrepancy (MMD; see (Gretton et al. 2007)): ∣∣∣∣∣∣μ[Pnew X ]− μ[P t X ]]∣∣∣∣∣∣ = ∣∣∣∣∣∣EPnew X [ψ(X)]− μ[P t X ]∣∣∣∣∣∣”
- Prototypal Analysis and Prototypal Regression (2017, background): “2 Prototypal Learning on Distributions through Kernel Embedding Probability distributions or samples thereof can also be mapped to a reproducing kernel Hilbert space via kernel embedding (see Berlinet and Thomas-Agnan, 2004; Gretton et al., 2006; Smola et al., 2007; Sriperumbudur et al., 2010; Sejdi”
- Balanced Policy Evaluation and Learning (2017, methodology): “In fact, as a distributional distance metric, it is the maximum mean discrepancy (MMD) used, for example, for testing whether two samples come from the same distribution [16].”
- Minimax Estimation of Kernel Mean Embeddings (2016, methodology): “Some of these applications include kernel two-sample testing (Gretton et al., 2007, 2012), kernel independence and conditional independence tests (Gretton et al., 2008; Fukumizu et al., 2008), covariate-shift (Smola et al., 2007), density estimation (Sriperumbudur, 2011), feature selection (Song et…”
- A Test of Relative Similarity For Model Selection in Generative Models (2015, methodology): “Our model selection criterion is based on the maximum mean discrepancy (MMD) (Gretton et al., 2006; 2012a), which represents the distance between embeddings of empirical distributions in a re-producing kernel Hilbert space (RKHS).”
- Adaptivity and Computation-Statistics Tradeoffs for Kernel and Distance based High Dimensional Two Sample Testing (2015, methodology): “One popular class of tests for the multivariate GDA problem that has emerged over the last decade, are kernel-based tests introduced in parallel by Fern´andez et al. [2008] and Gretton et al. [2006], and expanded on in Gretton et al. [2012a].”
- Kernel Mean Estimation via Spectral Filtering (2014, neutral): “…of Theorem 1 (cid:13)(cid:13)(cid:13)(cid:13) (cid:13)(cid:13)(cid:13)(cid:13) (cid:13)(cid:13)(cid:13)(cid:13) (cid:13)(cid:13)(cid:13)(cid:13) (cid:13)(cid:13)(cid:13)(cid:13) (cid:13)(cid:13)(cid:13)(cid:13) From [7], we have that ˆ µ P − µ P = O P ( n − 1 / 2 ) and therefore the result follows.”