Resumen Técnico: La Distancia de Wasserstein Observable

Enunciado del Problema

El desafío principal abordado en este artículo es la intratabilidad computacional del cálculo de la distancia de Wasserstein exacta entre medidas de probabilidad en conjuntos de datos a gran escala y no euclidianos. Si bien la teoría del transporte óptimo (OT) proporciona un marco riguroso para comparar distribuciones, el cálculo exacto típicamente escala cúbica o cuadráticamente con el número de puntos de datos, volviéndolo impráctico para conjuntos de datos masivos.

Las aproximaciones existentes, como la distancia de Wasserstein cortada, ofrecen eficiencia computacional proyectando medidas sobre subespacios unidimensionales. Sin embargo, estos métodos dependen de la estructura lineal de los espacios euclidianos ($\mathbb{R}^d$), utilizando productos internos y normas para definir direcciones de proyección. Muchos conjuntos de datos de interés —tales como formas 3D, grafos, estructuras de proteínas y superficies funcionales— residen en espacios métricos generales donde la linealidad y los productos internos están ausentes. En consecuencia, los enfoques estándar de Wasserstein cortado no pueden aplicarse directamente, y existe la necesidad de una alternativa computacionalmente tratable que proporcione cotas inferiores para la distancia de Wasserstein en espacios métricos polacos generales.

Metodología

El Marco de la Distancia de Wasserstein Observable

Los autores introducen la distancia de Wasserstein observable, un marco que generaliza el concepto de corte a espacios métricos arbitrarios $(X, d)$. En lugar de proyectar sobre subespacios lineales, el método proyecta medidas de probabilidad sobre la recta real utilizando observables métricos.

1. Observables Métricos: Un observable se define como una función 1-Lipschitz $f: X \to \mathbb{R}$, que satisface $|f(x) - f(y)| \leq d(x, y)$. El conjunto de todas estas funciones se denota $\Lambda(X)$.
2. Medidas Empujadas (Pushforward): Para una medida $\mu \in \mathcal{P}(X)$ y un observable $f$, la medida empujada $f_\sharp \mu$ se define sobre $\mathbb{R}$.
3. Definición de la Distancia: La distancia $p$-observable de Wasserstein, $\theta_p(\mu, \nu)$, se define como el supremo de las distancias de Wasserstein entre las medidas empujadas sobre todos los observables posibles:
   $$\theta_p(\mu, \nu) := \sup_{f \in \Lambda(X)} w_p(f_\sharp \mu, f_\sharp \nu)$$
   Dado que los observables son 1-Lipschitz, se sigue que $\theta_p(\mu, \nu) \leq w_p(\mu, \nu)$, estableciéndola como una cota inferior.

Aproximación Jerárquica e Identificabilidad

Para gestionar el costo computacional de optimizar sobre el espacio de dimensión infinita $\Lambda(X)$, los autores construyen una jerarquía de subespacios $\Lambda_n(X) \subseteq \Lambda(X)$.

• Observables Básicos: La construcción comienza con funciones de distancia a un punto $f_a(x) = d(x, a)$.
• Productos Cuña: Los observables de orden superior se forman mediante productos cuña ponderados (mínimos) de estas funciones básicas: $f_{\mathbf{a}}^\alpha = \alpha_0 f_{a_0} \wedge \dots \wedge \alpha_n f_{a_n}$.
• La Jerarquía: $\Lambda_n(X)$ consiste en observables formados por productos cuña de a lo sumo $n+1$ funciones básicas. Esto induce una secuencia de pseudométricas $\theta_{p,n}(\mu, \nu)$.

Contribuciones Teóricas: Inyectividad Estratificada

Un resultado teórico central es un análogo en espacios métricos al Dispositivo de Cramér-Wold. El artículo establece que la colección de medidas empujadas mediante observables en $\Lambda_n(X)$ caracteriza unívocamente una medida de probabilidad $\mu$ si la dimensión de recubrimiento métrico de su soporte es $\leq n$.

• Dimensión de Recubrimiento Métrico ($\xi_X$): Una noción de dimensión definida por el refinamiento de cubiertas abiertas en bolas abiertas.
• Teorema de Inyectividad Estratificada: Si el soporte de $\mu$ tiene dimensión de recubrimiento métrico $\leq n$, entonces $\mu$ está determinado unívocamente por sus proyecciones $f_\sharp \mu$ para todo $f \in \Lambda_n(X)$.
• Implicación: Para medidas soportadas en espacios con baja dimensión de recubrimiento métrico (por ejemplo, conjuntos finitos, grafos o variedades de baja dimensión), restringir el espacio de observables a $\Lambda_n(X)$ produce una métrica genuina (no solo una pseudométrica) que está estrictamente acotada inferiormente por la verdadera distancia de Wasserstein.

Modelo Computacional Discreto

Para la implementación práctica, los autores proponen un modelo discreto donde el espacio métrico se aproxima mediante un $\delta$-recubrimiento finito (una cuadrícula). Los observables se restringen a aquellos anclados en puntos dentro de este conjunto finito. Se proporcionan cotas teóricas que muestran que la distancia observable discreta converge a la versión continua a medida que aumenta la resolución de la cuadrícula, con un error proporcional al espaciado de la cuadrícula $\delta$.

Resultados Clave

Hallazgos Teóricos

• Propiedad Métrica: $\theta_p$ es una métrica en el espacio de todas las medidas de probabilidad. La versión restringida $\theta_{p,n}$ es una métrica en el subespacio de medidas con dimensión de soporte $\leq n$.
• Equivalencia para $p=1$: Para $p=1$, la distancia de Wasserstein observable es exactamente igual a la distancia de Wasserstein estándar ($\theta_1 = w_1$), un resultado derivado de la dualidad de Kantorovich-Rubinstein.
• Monotonía: La jerarquía satisface $\theta_{p,n} \leq \theta_{p,m} \leq \theta_p \leq w_p$ para $n \leq m$, ofreciendo un compromiso ajustable entre la eficiencia computacional y la nitidez de la cota.

Experimentos Numéricos

El artículo presenta varios experimentos de concepto que comparan las distancias de Wasserstein Observable (OW) frente a la distancia de Wasserstein Cortada (SW), la distancia de Wasserstein estándar y las distancias de Chamfer:

1. Clasificación Gaussiana: En espacios euclidianos de alta dimensión, OW y SW tienen un rendimiento comparable al distinguir clases gaussianas. Sin embargo, OW muestra una ventaja de rendimiento relativa a medida que aumenta la dimensión, posiblemente debido al fenómeno de concentración de la medida que afecta las proyecciones 1D en SW.
2. Distribuciones en Grafos: En espacios de grafos no euclidianos, OW supera significativamente a la distancia de Wasserstein estándar en tareas de clasificación mientras mantiene una escalabilidad computacional superior. OW demuestra robustez ante el ruido que carece el Wasserstein clásico.
3. Distribuciones en Esferas: Los experimentos en esferas ilustran el compromiso entre el número de observables/funciones y el costo computacional. Aumentar la complejidad de los observables (mayor $n$) reduce el error relativo pero incurre en costos combinatorios.
4. Clasificación de Nubes de Puntos (ModelNet10): En datos reales de objetos 3D, las distancias OW logran las mejores puntuaciones de clasificación entre las métricas escalables, particularmente en regímenes ruidosos, superando tanto a SW como a la distancia de Chamfer.
5. Aplicación en Aprendizaje Profundo: Los autores integraron OW en una función de pérdida de autoencoder para nubes de puntos. El uso de OW (específicamente una variante estilo $L_2$ para diferenciabilidad) resultó en una mayor precisión de clasificación en el espacio latente y una densidad de puntos más uniforme en las reconstrucciones en comparación con la distancia de Chamfer, que produjo salidas más nítidas pero con densidad desigual.

Significado y Afirmaciones

El artículo afirma proporcionar un marco computacionalmente tratable para derivar cotas inferiores de la distancia de Wasserstein en espacios métricos generales, eludiendo las limitaciones de los métodos específicos de Euclides como el Wasserstein cortado.

• Novelidad Teórica: El trabajo establece un vínculo riguroso entre la dimensión de recubrimiento métrico del soporte de una medida y el orden de observables requerido para la recuperación única. Esto sirve como una herramienta teórica fundamental para comprender la identificabilidad en el OT no euclidiano.
• Utilidad Práctica: El marco ofrece un enfoque "ajustable" donde los practicantes pueden ajustar el orden de los observables ($n$) para equilibrar el costo computacional contra la nitidez de la cota de distancia.
• Escalabilidad: El modelo discreto permite una implementación eficiente en conjuntos de datos grandes, con evidencia empírica que sugiere una escalabilidad lineal en el número de proyecciones/anclajes, haciéndolo adecuado para conjuntos de datos masivos donde el OT exacto es inviable.
• Robustez: Los experimentos sugieren que las distancias OW pueden ofrecer una robustez superior ante el ruido en comparación con las distancias de Wasserstein clásicas, haciéndolas adecuadas para aplicaciones con datos del mundo real.

Los autores posicionan este trabajo como un paso fundamental, señalando que, si bien los experimentos numéricos actuales son de concepto, el marco abre vías para futuras investigaciones sobre la convergencia de muestreo, la equivalencia bi-Lipschitz para $p \neq 1$ y la integración de observables aprendibles en pipelines de aprendizaje profundo.