Kernel Maximum Mean Discrepancy

The Kernel Maximum Mean Discrepancy (MMD) is a distance on the space of probability measures, evaluated based on the maximum difference in expectations over functions in a reproducing kernel Hilbert space (RKHS). It is a powerful tool to determine if two samples are drawn from different distributions.

Concept Overview

The Maximum Mean Discrepancy (MMD) compares the means of two samples after mapping them into a high-dimensional feature space using a kernel function. If the two distributions are identical, their kernel sample means will be close. A non-zero empirical MMD suggests the distributions are distinct. In this module, we use the Gaussian RBF kernel:
k(x, y) = exp(-(x - y)² / (2ℓ²))

Worked Example

Let us calculate the biased MMD squared and the unbiased estimator for the Shifted dataset with length scale ℓ = 1. The samples are X = [0, 1] and Y = [1, 2].

Kernel computations:
k(x, y) = exp(-(x - y)² / 2)
Sum of kernel values within X (m=2):
k(0,0) = 1, k(0,1) ≈ 0.6065, k(1,0) ≈ 0.6065, k(1,1) = 1
Sum(XX) = 1 + 0.6065 + 0.6065 + 1 ≈ 3.2130
Sum(XX_unbiased) = 0.6065 + 0.6065 = 1.2130
Sum of kernel values within Y (n=2):
k(1,1) = 1, k(1,2) ≈ 0.6065, k(2,1) ≈ 0.6065, k(2,2) = 1
Sum(YY) = 1 + 0.6065 + 0.6065 + 1 ≈ 3.2130
Sum(YY_unbiased) = 0.6065 + 0.6065 = 1.2130
Sum of cross-kernel values (X and Y):
k(0,1) ≈ 0.6065, k(0,2) ≈ 0.1353, k(1,1) = 1, k(1,2) ≈ 0.6065
Sum(XY) = 0.6065 + 0.1353 + 1 + 0.6065 ≈ 2.3484
Compute MMD squared:
Biased MMD² = Sum(XX)/4 + Sum(YY)/4 - 2*Sum(XY)/4
≈ (3.2130/4) + (3.2130/4) - 2 * (2.3484/4) ≈ 0.8032 + 0.8032 - 1.1742 = 0.4323
Unbiased estimator = Sum(XX_unbiased)/2 + Sum(YY_unbiased)/2 - 2*Sum(XY)/4
≈ (1.2130/2) + (1.2130/2) - 1.1742 ≈ 0.6065 + 0.6065 - 1.1742 = 0.0388

Experiment

To see the difference between the biased and unbiased estimators, explore the Kernel Maximum Mean Discrepancy module.

Select the Identical samples preset. Notice how the biased MMD squared is zero, as the sample means match perfectly. However, the unbiased estimator is negative.
Change the Length scale to 0.5. Observe how the witness function becomes more sharply peaked around the sample points, as the kernel falls off more quickly.
Switch to the Empty sample preset. Observe that both estimators become Unavailable, demonstrating that at least one sample in each set is required to compute the biased MMD squared.

Limitations

The unbiased MMD squared estimator requires at least 2 samples from each distribution to be computed (to evaluate off-diagonal elements in the Gram matrix). For sets like the Singleton case, the unbiased estimator is unavailable. Furthermore, while a large positive MMD suggests distributions differ, we cannot automatically derive a p-value or statistical significance from the empirical MMD squared value alone without knowing the asymptotic distribution under the null hypothesis (which typically requires a permutation test).

References

The following reference describes the Maximum Mean Discrepancy using kernels, its estimation, and its application in two-sample testing.

Gretton, A., Borgwardt, K. M., Rasch, M. J., Schölkopf, B., & Smola, A. (2012). A Kernel Two-Sample Test. Journal of Machine Learning Research (JMLR). This paper introduces the Kernel MMD, covering the unbiased estimator, its variance, and the conditions under which MMD is a valid metric on probability measures.

Kernel Maximum Mean Discrepancy