Resumen Técnico: Distancia de Kolmogorov-Smirnov Multidimensional Eficiente y Estable

Planteamiento del Problema

El artículo aborda el desafío de extender la distancia de Kolmogorov-Smirnov (KS), una métrica no paramétrica fundamental para comparar distribuciones univariantes, al entorno multidimensional ($d > 1$). Si bien la distancia KS univariante es bien comprendida, estable y computable de manera eficiente, las generalizaciones existentes para altas dimensiones sufren limitaciones significativas:

1. Inestabilidad: Se demuestra que los heurísticos populares como "quad-KS" (que restringen el espacio de búsqueda a cuadrantes definidos por los datos) son inestables; la distancia puede cambiar drásticamente con la adición o eliminación de un solo punto de datos, lo que impide establecer límites rigurosos de complejidad de la muestra.
2. Intratabilidad Computacional: El cálculo exacto de la distancia KS multidimensional sobre todos los rangos posibles es computacionalmente costoso (naífamente $O(n^d)$), y muchos de los tests de permutación existentes requieren un tiempo exponencial respecto al tamaño de la muestra.
3. Sensibilidad a las Unidades: Muchas métricas alternativas (por ejemplo, Wasserstein, Maximum Mean Discrepancy) dependen de distancias de base euclidianas, lo que las hace sensibles a la elección de unidades o la escala de las dimensiones, lo cual es problemático cuando las dimensiones tienen diferentes unidades físicas (por ejemplo, altura frente a peso).

Los autores proponen una formulación de la distancia de Kolmogorov-Smirnov multidimensional ($dKS$) que es una Métrica de Probabilidad Integral (IPM), invariante a la elección de unidades y capaz de ser computada eficientemente con garantías de aproximación demostrables.

Metodología

1. Definición de la Kolmogorov-Smirnov Multidimensional ($dKS$)

Los autores definen la distancia entre dos distribuciones $\mu$ y $\nu$ en $\mathbb{R}^d$ como la diferencia máxima en sus funciones de distribución acumulativa sobre rangos rectangulares dominantes ortogonales.
$$dKS(\mu, \nu) = \sup_{z \in \mathbb{R}^d} \left| \int_{x \preceq z} d\mu(x) - \int_{x \preceq z} d\nu(x) \right|$$
donde $x \preceq z$ denota que cada coordenada de $x$ es menor o igual a la coordenada correspondiente de $z$. A diferencia de algunas extensiones previas (por ejemplo, las de Peacock) que consideran todas las $2^d$ ortantes, esta formulación se centra en un único cuadrante (rectángulos dominantes), lo cual los autores argumentan es suficiente para una métrica robusta.

2. Propiedades Teóricas

• Propiedades de Métrica: El artículo demuestra que $dKS$ es una métrica completa (que satisface simetría, desigualdad triangular e identidad fuerte) en el espacio de las medidas de probabilidad, a diferencia de las variantes heurísticas que pueden ser solo pseudométricas o carecer de estabilidad.
• Complejidad de la Muestra: Utilizando la teoría de la dimensión VC para espacios de rango, los autores establecen que $n = O(\frac{1}{\epsilon^2}(d + \log(1/\delta)))$ muestras son suficientes para estimar la distancia dentro de un error $\epsilon$ con una probabilidad de $1-\delta$. Este límite es lineal en la dimensión $d$.

3. Algoritmos Computacionales

El artículo introduce algoritmos para calcular una $\epsilon$-aproximación de $dKS$ con un Tiempo de Ejecución Computacional-Estadístico (CSR) que es casi lineal en el tamaño de la muestra requerido para dimensiones $d \le 4$.

• Para $d=2$: Los autores proponen un enfoque de esquematización (Algoritmo 2, dKS-Sketch). Mediante el ordenamiento de puntos y la construcción de una rejilla estratificada de tamaño $O((d/\epsilon)^d)$, el algoritmo reduce el problema a programación dinámica sobre la rejilla.
  • Tiempo de ejecución: $O(n \log n + (d/\epsilon)^d)$. Para $d=2$ y $\epsilon \approx 1/\sqrt{n}$, esto produce $O(n \log n)$.
• Para $d=3, 4$: Los autores reducen el problema a encontrar un punto de máxima profundidad en un conjunto de rectángulos ponderados (una variación del Problema de la Medida de Klee).
  • Primero comprimen la muestra a un conjunto de $\epsilon$-aproximación más pequeño utilizando coloraciones de baja discrepancia (Lema 2).
  • Luego aplican el algoritmo de Chan para el punto de máximo peso en $O(s^{d/2} \text{polylog}(s))$ tiempo, donde $s$ es el tamaño de la muestra comprimida.
  • Tiempo de ejecución: Casi lineal en la complejidad de la muestra $n_\epsilon$. Específicamente, $O(n \log^3 n)$ para $d=3$ y $O(n \log^{21} n)$ para $d=4$.
• Dureza: El artículo argumenta que lograr un tiempo de ejecución casi lineal para $d > 4$ es improbable, ya que implicaría un avance en la resolución del problema de Máximo Peso de $k$-Clique, un problema ampliamente considerado difícil en la complejidad fina.

4. Test de Hipótesis

Utilizando los límites de complejidad de la muestra derivados y las propiedades de la métrica, los autores construyen un test de dos muestras de nivel-$\delta$.

• El test rechaza la hipótesis nula ($\mu = \nu$) si el $dKS$ computado excede un umbral derivado del tamaño de la muestra y el nivel de confianza.
• Crucialmente, a diferencia de los tests basados en Monte Carlo, este test proporciona una garantía precisa de muestra finita sobre la tasa de error de Tipo I sin depender de aproximaciones asintóticas.

Resultados Clave

1. Estabilidad: La formulación propuesta de $dKS$ es estable con respecto al muestreo, a diferencia de "quad-KS" u otros heurísticos restringidos a cuadrantes. Los autores construyen ejemplos patológicos donde la adición de un solo punto a un cálculo de quad-KS duplica la distancia, mientras que $dKS$ permanece estable.
2. Eficiencia:
   • $d=2$: Logra un tiempo de ejecución de $O(n \log n)$, igualando la eficiencia del caso univariante.
   • $d=3, 4$: Logra un tiempo de ejecución casi lineal en la complejidad de la muestra, una mejora significativa sobre los costos exponenciales o de alto polinomio de los métodos exactos anteriores.
3. Precisión: El test de hipótesis derivado es el primero en ofrecer un test preciso, no asintótico y no basado en simulaciones para distribuciones multidimensionales en dimensiones moderadas ($d \le 4$).
4. Validación Empírica: Los experimentos en datos de $d=2$ muestran que el algoritmo dKS-Sketch es órdenes de magnitud más rápido (por ejemplo, 0.2s frente a 4.2 horas para $n \approx 10^6$) que el algoritmo exacto de referencia, manteniendo una precisión comparable. En las evaluaciones de potencia, el test basado en esquemas logra la potencia estadística total en segundos, mientras que los baselines de permutación requieren horas o días.

Significancia y Reivindicaciones

El artículo afirma proporcionar la "forma correcta" de generalizar la distancia KS a múltiples dimensiones equilibrando la rigurosidad matemática (estabilidad, propiedades de métrica, complejidad de la muestra) con la viabilidad computacional.

• Contribución Teórica: Establece que una formulación de un solo cuadrante es suficiente para una métrica robusta y demuestra que esta métrica admite algoritmos de aproximación eficientes en bajas dimensiones.
• Impacto Práctico: Permite la aplicación de pruebas de dos muestras no paramétricas a datos de dimensiones moderadas (por ejemplo, de 2D a 4D) con diferentes unidades, donde las métricas basadas en la distancia euclidiana fallan y las extensiones previas de KS eran inestables o computacionalmente prohibitivas.
• Limitaciones: Los autores señalan explícitamente que para dimensiones $d > 4$, el problema es probablemente intratable de resolver con un tiempo de ejecución casi lineal a menos que se resuelvan importantes conjeturas en la teoría de la complejidad. También reconocen que los algoritmos para $d=3, 4$ dependen de reducciones complejas al problema de la medida de Klee y pueden ser difíciles de implementar en la práctica en comparación con el caso de $d=2$.

El trabajo posiciona al $dKS$ propuesto como una alternativa preferida a las extensiones de alta dimensión existentes, ofreciendo una herramienta estable, precisa y computacionalmente eficiente para el análisis estadístico en dimensiones moderadas.