Maximum Mean Discrepancy

Resources

Main Idea

As a Divergence, the MMD says two distributions are equal if and only if all their moments match. A kernel measures similarity between pairs of samples, so if the similarity for samples taken from within the same distribution is the same as that between distributions, those distributions are the same as one another.

The MMD is also an Integral Probability metric. Formally, for distributions $P (X)$ and $Q (Y)$ ( $X$ from the generator, $Y$ as data in Generative Modeling), this is

MMD (P, Q) = sup_{f \in F} (E_{P} [f (X)] - E_{Q} [f (Y)]),

with

F = {f : | | f | |_{H} \leq 1} .

First, the expectations taken with respect to $P (X)$ and $Q (Y)$ are ultimately integrals, partly explaining the name of Integral Probability Metrics and reaffirming that MMD is one of these methods. Next, $F$ is the class of witness functions or features, where each function maps from the domain of $X$ and $Y$ to $H$ (which could just be $R^{n}$ ?). $H$ is an Reproducing Kernel Hilbert Space (RKHS), which has some associated norm (induced by a particular inner product based on the so-called reproducing Kernel $k (\cdot, \cdot)$ ). Importantly, we don't need to consider the possibly infinite number of functions in $f$ . The supremum occurs at

f^{*} (x) \propto E_{P} [k (X, x)] - E_{Q} [k (Y, x)] .

Given samples of $X$ , ${x_{i}}_{i = 1}^{m}$ , and samples of $Y$ , ${y_{i}}_{i = 1}^{n}$ , both drawn IID, noting potentially $n \neq m$ , the empirical estimate of the ${MMD}^{2}$ is

{\hat{MMD}}^{2} (X, Y) = \frac{1}{m (m - 1)} \sum_{i \neq j}^{m} k (x_{i}, x_{j}) + \frac{1}{n (n - 1)} \sum_{i \neq j}^{n} k (y_{i}, y_{j}) - \frac{2}{m n} \sum_{i = 1}^{m} \sum_{j = 1}^{n} k (x_{i}, y_{j}) .

There is a choice of the kernel, $k$ . One can use the Gaussian RBF Kernel

k (x, y) = \exp (- \frac{1}{2 σ^{2}} | | x - y | |^{2}),

or the rational quadratic kernel

k_{α}^{r q} (x, y) = {(1 + \frac{| | x - y | |^{2}}{2 α})}^{- α} .

We can make new kernels by summing existing ones (similar to the sum of Symmetric Positive Definite matrices). This allows evaluating for a mixture of length scales,

k^{r q} (x, y) = \sum_{α \in A} k_{α}^{r q} (x, y) .

Further, we can even mix kernels of different types, such as

k^{r q *} (x, y) = k^{r q} (x, y) + ⟨ x, y ⟩ .

Resources

Related

Main Idea