A scalable version of MADD for big-data classification

Resumen Técnico: Una Versión Escalable de MADD para la Clasificación de Big-Data

Planteamiento del Problema
Los clasificadores basados en distancias, particularmente aquellos que dependen de la distancia euclidiana, son fundamentales en el aprendizaje automático moderno. Sin embargo, en escenarios de alta dimensionalidad y bajo tamaño de muestra (HDLSS, por sus siglas en inglés), la distancia euclidiana sufre de "concentración de distancia", donde las distancias entre puntos de una misma clase se vuelven mayores que las distancias entre puntos de clases diferentes. Esto viola las estructuras de vecindad y conduce a la aparición de "hubs" (centros), degradando severamente el rendimiento del clasificador.

Para abordar esto, Pal et al. (2016) introdujeron la Diferencia de Distancias de la Media Absoluta (MADD), una semimétrica basada en datos que evita con éxito estos problemas de alta dimensionalidad al mantener estructuras de vecindad correctas basadas en diferencias de localización y escala. A pesar de sus ventajas teóricas, MADD enfrenta un cuello de botella crítico: su complejidad computacional. Calcular MADD entre dos puntos requiere $O(nd)$ operaciones (donde $n$ es el tamaño de la muestra de entrenamiento y $d$ es la dimensionalidad), y clasificar un único punto de prueba mediante un enfoque de Vecino Más Cercano (NN) requiere $O(n^2d)$ operaciones. Como demuestra el artículo, esta escala cuadrática hace que MADD sea computacionalmente prohibitivo para grandes conjuntos de datos con $n$ grande, incluso en hardware moderno.

Metodología
Los autores proponen una versión escalable de MADD, denominada MADDsc, la cual reduce significativamente la complejidad computacional mientras retiene las ventajas estadísticas de la métrica original. La metodología consta de tres componentes principales:

1. Selección de Conjunto Representativo mediante Procesos de Punto Determinantal (DPP):
   En lugar de calcular distancias contra todo el conjunto de entrenamiento, MADDsc redefine la métrica utilizando un subconjunto pequeño y representativo de observaciones, $X^* \subset X$. Los autores argumentan que las propiedades de separación teórica de MADD se preservan si el conjunto representativo captura la diversidad de los datos originales.

   • Para seleccionar este conjunto, los autores emplean Procesos de Punto Determinantal (DPP). A diferencia del muestreo aleatorio simple, que puede omitir estructuras intrínsecas de los datos (especialmente en distribuciones multimodales), los DPP introducen un efecto de "repulsión". Al construir una matriz de similitud $L$ utilizando un núcleo de base radial gaussiano, los DPP seleccionan un subconjunto de puntos que son diversos y están dispersos a través de la nube de datos, asegurando que el conjunto representativo capture el paisaje de la muestra de entrenamiento completa.
   • El costo computacional se reduce de $O(n^2d)$ a $O(knd)$, donde $k$ es el tamaño del conjunto representativo ($k \ll n$).

2. Validación Cruzada Incremental para la Selección de Hiperparámetros:
   El tamaño del conjunto representativo ($k$) es un hiperparámetro crucial. La validación cruzada estándar requeriría seleccionar repetidamente muestras de DPP y recomputar distancias para cada iteración y cada candidato a $k$, lo que anularía las ganancias de velocidad.

   • Los autores proponen una técnica de validación cruzada incremental. Al modificar el algoritmo de muestreo de DPP para asegurar que los subconjletos seleccionados sean anidados (es decir, $X^*(k_t) \subseteq X^*(k_{t+1})$), los valores de MADDsc pueden calcularse de forma incremental. Esto permite que el algoritmo actualice la métrica a medida que $k$ aumenta sin recomputar la matriz de distancia completa, reduciendo drásticamente la sobrecarga computacional de la selección del modelo.

3. Características de Fourier Aleatorias (RFF) para Conjuntos de Datos Masivos:
   Para conjuntos de datos extremadamente grandes donde incluso la construcción de la matriz de similitud $n \times n$ para el DPP es inviable (debido a costos de memoria o de descomposición de autovalores), los autores integran Características de Fourier Aleatorias (RFF).

   • Basándose en el teorema de Bochner, el núcleo gaussiano se aproxima mediante una expectativa de Monte Carlo. La matriz de similitud $L$ se aproxima por $R R^T$, donde $R$ es una matriz de mapeo de características de baja dimensión ($n \times 2D$).
   • Esto permite que la descomposición de autovalores requerida para el muestreo de DPP se realice sobre una matriz mucho más pequeña de $2D \times 2D$ (o mediante SVD de $R$), reduciendo tanto el tiempo como la complejidad de memoria. Este enfoque se formaliza como NN-MADDsc con RFF.

El marco también se extiende a gMADDsc, una versión escalable de la MADD generalizada (gMADD), que maneja casos donde las poblaciones difieren más allá de solo los dos primeros momentos (localización y escala).

Resultados Clave
Estudios de simulación extensos y análisis de datos reales en conjuntos de datos de series temporales UCR demuestran la eficacia de los métodos propuestos:

• Desempeño vs. MADD Original: En simulaciones a través de diversas distribuciones (localización, escala, mezcla y cola pesada), NN-MADDsc logra tasas de error de clasificación casi idénticas a las de la NN-MADD original (las diferencias son típicamente $\le 1\%$).
• Eficiencia Computacional:
  • NN-MADDsc es significativamente más rápida que NN-MADD. Para un tamaño de entrenamiento de $n=16,384$, NN-MADD tomó más de 6.5 horas, mientras que NN-MADDsc completó la tarea en una fracción de ese tiempo.
  • La estrategia de validación cruzada incremental reduce aún más el tiempo de ejecución en comparación con la validación cruzada estándar, recortando el tiempo de computación casi a la mitad para $n=4096$.
  • El enfoque basado en RFF ofrece la aceleración más dramática. Para $n=25,000$, el método basado en RFF completó en menos de 25 minutos, mientras que la NN-MADDsc estándar tomó más de 15 horas, y la NN-MADD original falló debido a restricciones de memoria.
• Comparación con Otros Clasificadores: NN-MADDsc supera consistentemente o iguala a los clasificadores de vanguardia (incluyendo Random Forest, SVM y GLMNET) en entornos de alta dimensionalidad, particularmente cuando las distribuciones de los datos difieren en forma o escala. En pruebas de series temporales del mundo real, alcanzó las tasas de error más bajas en varios conjuntos de datos (por ejemplo, Synthetic Control Chart, Two Patterns).
• Garantías Teóricas: El artículo establece que, bajo regímenes de alta dimensión y alto tamaño de muestra (HDHSS), las decisiones de clasificación de NN-MADDsc convergen a las de NN-MADD con una probabilidad que tiende a 1, siempre que el tamaño del conjunto representativo crezca apropiadamente en relación con el logaritmo del tamaño de la muestra.

Significancia y Reivindicaciones
El artículo afirma ampliar el alcance de MADD, haciéndolo aplicable a escenarios de big-data caracterizados tanto por alta dimensionalidad como por grandes recuentos de observaciones. La contribución principal es el desacoplamiento de la robustez estadística de MADD de su complejidad computacional cuadrática. Al aprovechar los DPP para el submuestreo que preserva la diversidad y los RFF para la aproximación de núcleos, los autores proporcionan una solución práctica y escalable que retiene los beneficios teóricos de MADD en espacios de alta dimensión. El trabajo no pretende reemplazar a todos los clasificadores, sino posicionar a MADDsc como una alternativa superior para la clasificación basada en distancias en regímenes donde la distancia euclidiana falla y la MADD tradicional es computacionalmente intratable.