Discrepancia media máxima (distribución de la distancia)

Question

Tengo dos conjuntos de datos (datos de origen y de destino) que siguen distribuciones diferentes. Estoy utilizando MMD - que es una distancia de distribución no paramétrica - para calcular la distribución marginal entre los datos de origen y de destino.

datos de origen, Xs

datos de destino, Xt

Matriz de adaptación A

** _Datos proyectados, Zs = A' _Xs y Zt = A' _Xt___

* MMD => Distancia(P(Xs),P(Xt)) = | media(A'Xs) - media(A' Xt) |

Es decir: la distancia de la distribución entre los datos de origen y de destino en el espacio original es equivalente a la distancia entre las medias de los datos de origen y de destino proyectados en el espacio incrustado.

Tengo una pregunta sobre el concepto de MMD.

En la fórmula MMD, ¿por qué con el cálculo de la distancia en el espacio latente podríamos medir la distancia de la distribución en el espacio original?

Gracias

Answer 1

Podría ayudar a dar una visión un poco más general de la MMD. $\DeclareMathOperator{\E}{\mathbb E}\newcommand{\R}{\mathbb R}\newcommand{\X}{\mathcal X}\newcommand{\h}{\mathcal H}\DeclareMathOperator{\MMD}{MMD}$

En general, el MMD se define por la idea de representar las distancias entre distribuciones como distancias entre media de incrustaciones de características. Es decir, digamos que tenemos distribuciones $P$ y $Q$ sobre un conjunto $\X$ . La MMD se define por un mapa de características $\varphi : \X \to \h$ , donde $\mathcal H$ es lo que se llama un espacio de Hilbert de núcleo reproductor. En general, el MMD es $$ \MMD(P, Q) = \lVert \E_{X \sim P}[ \varphi(X) ] - \E_{Y \sim Q}[ \varphi(Y) ] \rVert_\h .$$

Por ejemplo, podríamos tener $\X = \h = \R^d$ y $\varphi(x) = x$ . En ese caso: \begin{align} \MMD(P, Q) &= \lVert \E_{X \sim P}[ \varphi(X) ] - \E_{Y \sim Q}[ \varphi(Y) ] \rVert_\h \\&= \lVert \E_{X \sim P}[ X ] - \E_{Y \sim Q}[ Y ] \rVert_{\R^d} \\&= \lVert \mu_P - \mu_Q \rVert_{\R^d} ,\end{align} por lo que esta MMD es sólo la distancia entre las medias de las dos distribuciones. Las distribuciones que coincidan de esta manera coincidirán con sus medias, aunque puedan diferir en su varianza o en otros aspectos.

Su caso es ligeramente diferente: tenemos $\mathcal X = \mathbb R^d$ y $\mathcal H = \mathbb R^p$ con $\varphi(x) = A' x$ , donde $A$ es un $d \times p$ matriz. Así que tenemos \begin{align} \MMD(P, Q) &= \lVert \E_{X \sim P}[ \varphi(X) ] - \E_{Y \sim Q}[ \varphi(Y) ] \rVert_\h \\&= \lVert \E_{X \sim P}[ A' X ] - \E_{Y \sim Q}[ A' Y ] \rVert_{\R^p} \\&= \lVert A' \E_{X \sim P}[ X ] - A' \E_{Y \sim Q}[ Y ] \rVert_{\R^p} \\&= \lVert A'( \mu_P - \mu_Q ) \rVert_{\R^p} .\end{align} Esta MMD es la diferencia entre dos proyecciones diferentes de la media. Si $p < d$ o el mapeo $A'$ de lo contrario no es invertible, entonces este MMD es más débil que la anterior: no distingue entre algunas distribuciones que sí lo hace la anterior.

También puedes construir distancias más fuertes. Por ejemplo, si $\X = \R$ y usted utiliza $\varphi(x) = (x, x^2)$ entonces la MMD se convierte en $\sqrt{(\E X - \E Y)^2 + (\E X^2 - \E Y^2)^2}$ y puede distinguir no sólo distribuciones con diferentes medias sino también con diferentes varianzas.

Y puedes ser mucho más fuerte que eso: si $\varphi$ mapea a un espacio de Hilbert de núcleo reproductor general, entonces se puede aplicar la truco del núcleo para calcular la MMD, y resulta que muchos núcleos, incluido el núcleo gaussiano, conducen a que la MMD sea cero si y sólo si las distribuciones son idénticas.

En concreto, dejar que $k(x, y) = \langle \varphi(x), \varphi(y) \rangle_\h$ , se obtiene \begin{align} \MMD^2(P, Q) &= \lVert \E_{X \sim P} \varphi(X) - \E_{Y \sim Q} \varphi(Y) \rVert_\h^2 \\&= \langle \E_{X \sim P} \varphi(X), \E_{X' \sim P} \varphi(X') \rangle_\h + \langle \E_{Y \sim Q} \varphi(Y), \E_{Y' \sim Q} \varphi(Y') \rangle_\h - 2 \langle \E_{X \sim P} \varphi(X), \E_{Y \sim Q} \varphi(Y) \rangle_\h \\&= \E_{X, X' \sim P} k(X, X') + \E_{Y, Y' \sim Q} k(Y, Y') - 2 \E_{X \sim P, Y \sim Q} k(X, Y) \end{align} que se puede estimar directamente con muestras.

---

Actualización: de aquí viene el "máximo" del nombre.

El mapa de características $\varphi: \X \to \h$ mapea en un espacio de Hilbert de núcleo reproductor. Estos son espacios de funciones y satisfacen una propiedad clave (llamada propiedad reproductora ): $\langle f, \varphi(x) \rangle_\h = f(x)$ para cualquier $f \in \h$ .

En el ejemplo más sencillo, $\X = \h = \R^d$ con $\varphi(x) = x$ , vemos cada $f \in \h$ como la función correspondiente a algún $w \in \R^d$ , por $f(x) = w' x$ . Entonces la propiedad de reproducción $\langle f, \varphi(x) \rangle_\h = \langle w, x \rangle_{\R^d}$ debería tener sentido.

En configuraciones más complejas, como un núcleo gaussiano, $f$ es una función mucho más complicada, pero la propiedad de reproducción se mantiene.

Ahora, podemos dar una caracterización alternativa de la MMD: \begin{align} \MMD(P, Q) &= \lVert \E_{X \sim P}[\varphi(X)] - \E_{Y \sim Q}[\varphi(Y)] \rVert_\h \\&= \sup_{f \in \h : \lVert f \rVert_\h \le 1} \langle f, \E_{X \sim P}[\varphi(X)] - \E_{Y \sim Q}[\varphi(Y)] \rangle_\h \\&= \sup_{f \in \h : \lVert f \rVert_\h \le 1} \langle f, \E_{X \sim P}[\varphi(X)] \rangle_\h - \langle f, \E_{Y \sim Q}[\varphi(Y)] \rangle_\h \\&= \sup_{f \in \h : \lVert f \rVert_\h \le 1} \E_{X \sim P}[\langle f, \varphi(X)\rangle_\h] - \E_{Y \sim Q}[\langle f, \varphi(Y) \rangle_\h] \\&= \sup_{f \in \h : \lVert f \rVert_\h \le 1} \E_{X \sim P}[f(X)] - \E_{Y \sim Q}[f(Y)] .\end{align} La segunda línea es un hecho general sobre las normas en los espacios de Hilbert: $\sup_{f : \lVert f \rVert \le 1} \langle f, g \rangle_\h = \lVert g \rVert$ se consigue mediante $f = g / \lVert g \rVert$ . La cuarta depende de una condición técnica conocida como integrabilidad de Bochner, pero es cierta, por ejemplo, para núcleos acotados o distribuciones con soporte acotado. Al final utilizamos la propiedad de reproducción.

Esta última línea es la razón por la que se llama "máxima discrepancia media" - es el máximo, sobre las funciones de prueba $f$ en la bola unitaria de $\h$ de la diferencia media entre las dos distribuciones.

Answer 2

Así es como interpreté a MMD. Dos distribuciones son similares si sus momentos son similares. Aplicando un kernel, puedo transformar la variable de forma que se calculen todos los momentos (primero, segundo, tercero, etc.). En el espacio latente puedo calcular la diferencia entre los momentos y promediarla. Esto da una medida de la similitud/disimilitud entre los conjuntos de datos.

Answer 3

Lo que hoy conocemos como Máxima Discrepancia Media se deriva en realidad de la siguiente Métrica de Probabilidad Integral [A]:

Si p y q son dos distribuciones y $\mathcal{F}$ es una clase de real funciones medibles acotadas de valor real, entonces la métrica se definida como, $$D(p, q, \mathcal{F}) = \sup_{f \in \mathcal{F}} \left|\mathbb{E}_p[f(x)] - \mathbb{E}_q[f(x)]\right|$$

Si selecciona la clase de función $\mathcal{F} = \{f \;\;|\;\; \|f\|_{\mathcal{H}} \leq 1\}$ donde $\mathcal{H}$ representa el espacio de Hilbert del núcleo reproductor con el núcleo reproductor $k$ se puede demostrar que la métrica anterior se reduce a [D]: $$D(p, q, \mathcal{F}) = \left|\mathbb{E}_p[k(x, \cdot)] - \mathbb{E}_q[k(x, \cdot)]\right|$$

Así, resulta que el cálculo de las diferencias de la media en el espacio del núcleo da la distancia entre la distribución calculada sobre una determinada clase de funciones. En realidad, se pueden derivar otras métricas de esta manera, seleccionando ciertas clases de funciones y analizando la métrica de probabilidad integral original bajo esa clase de función, por ejemplo, la distancia de variación total, la distancia de Wasserstein [B].

Ahora bien, llegando a la descripción que has hecho en el post original, me preocupa un poco cómo vas a calcular el MMD. Incluso para la medida original de la MMD, el núcleo tenía que satisfacer algunas propiedades [C]. Sin embargo, todo lo que parece estar haciendo es multiplicar sus características con alguna matriz y calcular la distancia en ese espacio. Lo que realmente no significa nada a menos que las matrices de proyección sean especiales. Por lo tanto, sería bueno revisar los artículos enlazados y asegurarse de que lo que estás haciendo cumple con los requisitos de una incrustación media del núcleo.

[A] Métrica integral de la probabilidad y sus clases generadoras de funciones, Muller, 1997

[B] Sobre la métrica de probabilidad integral, las divergencias y la clasificación binaria, Sriperumbudur et. al, 2009

[C] Universalidad, núcleos característicos e incrustación RKHS de medidas, Sriperumbudur et. al, 2012 (PDF)

[D] Incrustación de la media del núcleo de las distribuciones: A Review and Beyond, Muandet et. al, 2016

Answer 4

Para el núcleo gaussiano $K({\mathbf x}, {\mathbf y})=e^{-||{\mathbf x}-{\mathbf y}||^2/4\sigma^2}$ en ${\mathbb R}^n$ el MMD satisface:

${\rm MMD}(P,Q) \propto \sup\limits_{f\in L_2({\mathbb R}^n), ||f||_{L_2}\leq 1} {\mathbb E}_{X\sim P, \epsilon\sim N(0, \sigma^2I_n)} f(X+\epsilon)-{\mathbb E}_{Y\sim Q, \epsilon'\sim N(0, \sigma^2I_n)} f(Y+\epsilon')$

Esta representación ayuda a entender en qué consiste el MMD: la función del crítico es de la bola unitaria en $L_2$ y se aplica a vectores aleatorios distribuidos según ``smoothed'' $P$ y $Q$ .

Para el núcleo invariable por traslación, $K({\mathbf x}, {\mathbf y}) = k({\mathbf x} - {\mathbf y})$ se puede representar el MMD como

${\rm MMD}(P,Q) \propto \sup\limits_{f\in L_2({\mathbb R}^n), ||f||_{L_2}\leq 1} {\mathbb E}_{X\sim P, \epsilon\sim E} f(X+\epsilon)-{\mathbb E}_{Y\sim Q, \epsilon'\sim E} f(Y+\epsilon')$ (1)

donde $E({\mathbf x}) = \frac{F({\mathbf x})}{||F||_{L_1}}$ donde $F=\mathcal{F}\big\{\sqrt{\mathcal{F}^{-1}[k]}\big\}$ y $\mathcal{F}$ denota la transformada de Fourier.

Demostremos por qué se cumple la fórmula (1) ( $P$ y $Q$ son pdfs suaves, $\ast$ denota convolución):

$ \begin{align} {\rm MMD}(P,Q)^2 = {\mathbb E}_{X, X' \sim P} k(X - X') + {\mathbb E}_{Y, Y' \sim Q} k(Y- Y') - 2 {\mathbb E}_{X \sim P, Y \sim Q} k(X- Y) = \\ \langle P, k\ast P\rangle_{L_2}+\langle Q, k\ast Q\rangle_{L_2} - 2 \langle P, k\ast Q\rangle_{L_2} \propto \\ \langle F\ast P, F\ast P\rangle_{L_2}+\langle F\ast Q, F\ast Q\rangle_{L_2} - 2 \langle F\ast P, F\ast Q\rangle_{L_2} = \\ ||F\ast P - F\ast Q||^2_{L_2} \end{align} $

Por lo tanto,

$ \begin{align} {\rm MMD}(P,Q) = ||F\ast P - F\ast Q||_{L_2} = \\ \sup\limits_{f\in L_2({\mathbb R}^n), ||f||_{L_2}\leq 1} \langle f, F\ast P - F\ast Q\rangle_{L_2} = \sup\limits_{f\in L_2({\mathbb R}^n), ||f||_{L_2}\leq 1} \langle f, F\ast P\rangle - \langle f, F\ast Q\rangle_{L_2} = \\ \sup\limits_{f\in L_2({\mathbb R}^n), ||f||_{L_2}\leq 1} {\mathbb E}_{X\sim P, \epsilon\sim E} f(X+\epsilon)-{\mathbb E}_{Y\sim Q, \epsilon'\sim E} f(Y+\epsilon') \end{align} $

Incluso para el núcleo general se pueden obtener fórmulas similares, pero entonces se necesita algo de cálculo pseudodiferencial (véase https://arxiv.org/pdf/2106.14277.pdf ).