Skeleton Regression: A Graph-Based Approach to Estimation with Manifold Structure

1. Planteamiento del Problema

En la actualidad, muchos conjuntos de datos de gran escala poseen una estructura geométrica subyacente donde las covariables (predictores) residen alrededor de una variedad de baja dimensión incrustada en un espacio vectorial de alta dimensión.

El desafío principal en la regresión no paramétrica con estos datos es doble:

1. La maldición de la dimensionalidad: Los métodos tradicionales (como la regresión por kernel o k-vecinos más cercanos en el espacio euclidiano) sufren un rendimiento deficiente cuando la dimensión del espacio de entrada ($d$) es grande, incluso si la dimensión intrínseca de los datos es baja.
2. Ruido y estructuras complejas: Los datos a menudo contienen ruido aditivo, observaciones corruptas o provienen de la unión de múltiples variedades desconectadas. Los métodos existentes que intentan explotar la estructura local de la variedad (como MALLER o PCR-LE) a menudo no son robustos a perturbaciones que alejan los datos de la variedad real o fallan cuando la estructura es una unión de componentes disjuntos.

El objetivo de este trabajo es estimar una respuesta escalar $Y$ dada covariables $X$ que se distribuyen alrededor de estructuras de variedad, aprovechando dicha geometría para evitar la maldición de la dimensionalidad y ser robusto ante el ruido.

2. Metodología: El Marco de Regresión Esqueleto

Los autores proponen un nuevo marco de trabajo llamado Regresión Esqueleto (Skeleton Regression). La idea central es transformar el problema de regresión en un espacio de alta dimensión a un problema de regresión sobre un grafo métrico de baja dimensión (el "esqueleto").

El procedimiento consta de cuatro pasos principales:

A. Construcción del Esqueleto (Skeleton Construction)

En lugar de usar cada punto de datos como un nodo, se construye una representación gráfica simplificada:

• Nudos (Knots): Se seleccionan puntos representativos del espacio de covariables utilizando el algoritmo de k-medias con un número grande de centros ($k \approx \sqrt{n}$). Estos nudos actúan como centros de celdas de Voronoi.
• Aristas (Edges): Se conectan los nudos si sus celdas de Voronoi adyacentes comparten una frontera significativa. Esto se determina examinando la región de los 2-vecinos más cercanos (2-NN) de los puntos de datos entre pares de nudos.
• Poda y Segmentación: Utilizando una métrica llamada Densidad de Voronoi, se pueden podar aristas o segmentar el grafo en componentes disjuntos si la estructura de los datos sugiere variedades desconectadas.

B. Proyección de Datos (Data Projection)

Las covariables originales $\mathbf{x}_i$ se proyectan sobre el esqueleto $\mathcal{S}$:

• Si un punto está cerca de un solo nudo, se proyecta sobre ese nudo.
• Si un punto está entre dos nudos conectados, se proyecta ortogonalmente sobre la arista que los une.
• El resultado es un conjunto de puntos proyectados $\mathbf{s}_i \in \mathcal{S}$.

C. Definición de la Métrica del Esqueleto

Se define una distancia basada en el grafo, $d_{\mathcal{S}}(\cdot, \cdot)$, que mide la longitud del camino más corto a lo largo de las aristas del esqueleto. Esta distancia es una métrica válida en el espacio del esqueleto y es independiente de la dimensión ambient ($d$).

D. Estimación de la Regresión

Una vez proyectados los datos y definida la métrica, se aplican técnicas de regresión no paramétrica adaptadas al grafo:

1. Regresión por Kernel en Esqueleto (S-Kernel): Una versión del estimador de Nadaraya-Watson donde el kernel depende de la distancia $d_{\mathcal{S}}$ en lugar de la distancia euclidiana.
2. k-Vecinos Más Cercanos en Esqueleto (S-kNN): Se seleccionan los $k$ vecinos más cercanos utilizando la distancia a lo largo del grafo.
3. Regresión por Splines Lineales en Esqueleto (S-Lspline): Se propone un modelo paramétrico donde la función de regresión es lineal en cada arista y continua en los nudos. Esto se formula como un problema de mínimos cuadrados lineales con una transformación de características específica basada en la posición de proyección.

3. Contribuciones Clave

1. Marco Unificado para Variedades: El método maneja naturalmente la unión de múltiples variedades (componentes disjuntos) y estructuras de dimensión variable, algo difícil para métodos de aprendizaje de variedades tradicionales.
2. Independencia de la Dimensión: Al operar sobre el esqueleto (una estructura 1D o 0D), la complejidad de la estimación no depende de la dimensión ambient $d$, sino de la densidad de datos en la variedad.
3. Robustez al Ruido: La construcción del esqueleto basada en densidad y la proyección actúan como un filtro, haciendo que el método sea robusto frente a observaciones ruidosas y covariables de alta dimensión con ruido gaussiano.
4. Garantías Teóricas: Los autores demuestran la consistencia y las tasas de convergencia de los estimadores:
   • En las aristas, la tasa de convergencia es $O(h) + O_p(1/\sqrt{nh})$, similar a la regresión por kernel unidimensional.
   • En los nudos con masa de probabilidad, la tasa es $O(h) + O_p(1/\sqrt{n})$.
   • En los nudos sin masa, el estimador converge a un promedio ponderado de los límites de las aristas adyacentes.
5. Análisis de Limitaciones: Discuten por qué otros métodos (regresión polinómica local, splines de orden superior, bases ortonormales) son difíciles de aplicar directamente en grafos debido a la falta de orientación y definiciones de derivadas en los nudos.

4. Resultados Experimentales

Los autores evaluaron el método mediante simulaciones y datos reales, comparándolo con kNN estándar, Ridge/Lasso, Series Espectrales, Kernel Ridge (Fast-KRR) y Autoencoders MLP.

• Datos Sintéticos (Yinyang y SwissRoll):
  • En datos con múltiples componentes desconectados (Yinyang), los métodos basados en esqueleto superaron significativamente a los métodos de aprendizaje de variedades (como Series Espectrales) y a los métodos de regularización estándar.
  • En datos con ruido aditivo masivo (ruido gaussiano en dimensión 1000), los métodos S-Kernel y S-kNN mostraron una superioridad notable, mientras que otros métodos fallaron o tuvieron un error cuadrático medio (SSE) muy alto.
  • En la variedad SwissRoll (conectada y bidimensional), los métodos basados en esqueleto también superaron a kNN estándar y a los métodos de redes neuronales, demostrando que la distancia geodésica aproximada por el grafo es efectiva.
• Datos Reales:
  • Imágenes de Tazas (COIL-20): Predicción de ángulos de rotación. El método S-Lspline obtuvo el mejor rendimiento, superando a kNN, lo que sugiere que la estructura lineal por partes del esqueleto capturó bien la variación circular.
  • Datos SDSS (Astronomía): Predicción de corrimiento al rojo (redshift) a partir de magnitudes fotométricas. Aunque kNN y Series Espectrales tuvieron un rendimiento ligeramente superior en precisión, el esqueleto proporcionó una visualización clara de la estructura unidimensional subyacente de los datos, demostrando su utilidad como herramienta de exploración.

5. Significado e Impacto

El artículo presenta una contribución significativa al campo del análisis de datos geométricos y la estadística no paramétrica:

• Alternativa a las Redes Neuronales: Ofrece un enfoque interpretable y computacionalmente eficiente (sin necesidad de entrenamiento profundo costoso) para datos de alta dimensión con estructura de variedad.
• Interpretabilidad: A diferencia de las "cajas negras" de los métodos de aprendizaje profundo, el esqueleto resultante es un grafo explícito que resume la topología de los datos, permitiendo a los investigadores visualizar la estructura de las covariables y las tendencias de la respuesta.
• Versatilidad: Proporciona un marco robusto que funciona bien tanto en configuraciones de alta dimensión con ruido como en estructuras topológicamente complejas (variedades desconectadas), llenando un vacío dejado por métodos que asumen variedades suaves y conectadas.

En conclusión, la Regresión Esqueleto es una metodología prometedora que combina la simplicidad de la proyección geométrica con la flexibilidad de la regresión no paramétrica, ofreciendo una solución robusta y teóricamente fundamentada para problemas de regresión en espacios de alta dimensión con estructura de variedad.