Resumen Técnico: Diagramas de Persistencia No Reducidos para el Aprendizaje Automático Topológico

Planteamiento del Problema

El Análisis de Datos Topológicos (TDA) combinado con el aprendizaje automático (ML) supervisado se ha convertido en un enfoque estándar para analizar datos complejos en diversos dominios, incluyendo la biología, la neurociencia y la ciencia de materiales. El flujo de trabajo estándar implica computar la Homología Persistente (PH) para generar Diagramas de Persistencia (PD), vectorizar estos diagramas y entrenar modelos de ML.

Sin embargo, se han observado dos ineficiencias críticas en este flujo de trabajo:

1. Redundancia de Información: La evidencia empírica sugiere que los modelos de ML a menudo ignoran gran parte de la información contenida en los diagramas de persistencia vectorizados. Por ejemplo, las tareas de regresión han mostrado un rendimiento "casi óptimo" utilizando solo la persistencia del 28º punto más persistente, y los benchmarks indican que las vectorizaciones estadísticas ingenuas suelen funcionar tan bien como las complejas.
2. Costo Computacional: Computar los PD completamente reducidos suele ser el paso más exigente computacionalmente en el flujo de trabajo, requiriendo una cantidad sustancial de memoria y tiempo, particularmente para conjuntos de datos grandes.

La hipótesis central de este trabajo es que si los modelos de ML pueden funcionar bien con vectorizaciones que descartan información, entonces la computación completa de la PH (específicamente la reducción de las matrices de frontera) puede ser un gasto computacional innecesario. Los autores proponen evitar la reducción de la matriz de frontera por completo mediante el uso de diagramas de persistencia no reducidos derivados directamente de matrices de frontera no reducidas.

Metodología

Marco Teórico

Los autores definen varios tipos de diagramas de persistencia (PD) no reducidos construidos a partir de una matriz de frontera $M$ sin realizar el algoritmo estándar de reducción por columnas. Estos se definen basándose en las propiedades de las columnas de la matriz:

• Par Aparente (AP) PD: Pares $(low(M_j), j)$ donde la entrada no nula más baja en la columna $j$ es la única entrada no nula en esa fila a la izquierda (un patrón específico que indica un par de persistencia sin reducción).
• Par Cuasi-Aparente Inferior (qAP↓) PD: Pares $(low(M_j), j)$ donde $\beta(M_j) \neq -1$.
• Par Cuasi-Aparente Superior (qAP↑) PD: Pares $(\beta(M_j), j)$ donde $\beta(M_j) \neq -1$. Aquí, $\beta(M_j)$ es el índice de fila más alto de un 1 en la columna $j$ que no puede ser eliminado por reducción.
• Low-Ones (L1) PD: El multiconjunto de pares $(low(M_j), j)$ para todas las columnas donde $low(M_j) \neq -1$.

Las construcciones L1 y qAP↑ se enfatizan particularmente para los complejos de Vietoris-Rips (VR), ya que otros tipos de no reducidos pueden producir solo pares efímeros (persistencia cero) en dimensiones de homología superior para estas filtraciones.

Análisis de Estabilidad

El artículo investiga la estabilidad de Lipschitz de estas transformaciones con respecto a la distancia de bottleneck ($d_B$).

• Resultados Teóricos: La transformación de PD totalmente reducida (FR) es globalmente estable con una constante de Lipschitz $C=1$. En contraste, los PD no reducidos (AP, qAP) no son globalmente estables. Pequeñas perturbaciones en la función de filtración pueden reordenar las columnas de la matriz de frontera, causando la aparición o desaparición de pares aparentes, lo que conduce a una inestabilidad combinatoria.
• Estabilidad Local: Los autores demuestran que los PD no reducidos son localmente Lipschitz estables. Si la perturbación en la función de filtración es lo suficientemente pequeña como para preservar el orden de los símplices (específicamente, menor que la mitad de la brecha mínima entre valores de filtración adyacentes), las transformaciones permanecen estables.
• Estabilidad Experimental: Los experimentos computacionales en nubes de puntos perturbadas muestran que, si bien ocurren picos de inestabilidad grandes (donde el número de puntos en el diagrama cambia), estos son raros. La mayoría de las perturbaciones resultan en ratios de estabilidad comparables o incluso mejores que los del caso totalmente reducido.

Implementación Computacional

Para evaluar las ventajas computacionales, los autores implementaron una versión modificada del algoritmo Ripser para computar diagramas qAP↑ para complejos VR.

• Paralelización: A diferencia del algoritmo de reducción estándar, que procesa las columnas de forma serial (de izquierda a derecha), la computación de los diagramas qAP↑ puede paralelizarse. El algoritmo busca a través de las columnas de la matriz de cobondera de la filtración de forma independiente.
• Eficiencia de Memoria: La implementación evita almacenar la matriz de frontera completa y las fronteras de trabajo necesarias para la reducción. Utiliza un mapa de hash para almacenar pares y omite los "pares de cero apariencia" (pares efímeros) de forma temprana en el proceso.

Resultados Clave

Rendimiento Computacional

La evaluación del rendimiento en un sistema AMD Ryzen Threadripper PRO de 32 núcleos frente a la computación estándar de Ripser reveló ganancias significativas:

• Tiempo de Ejecución (Wall Time): La computación paralela de qAP↑ logró una aceleración promedio de 20x en el tiempo de ejecución en comparación con la computación de persistencia completa.
• Memoria: El enfoque no reducido requirió aproximadamente 1/13 parte de la memoria de Ripser para ejemplos sin umbral y 1/1.86 para ejemplos con umbral.
• Escalabilidad: Los autores computaron con éxito diagramas no reducidos para el conjunto de datos torus4 (50,000 puntos), una tarea en la que Ripser falló debido a restricciones de memoria (requiriendo >300GB de RAM). Para el conjunto de datos de cicloctano, la computación qAP↑ utilizó 454 veces menos memoria y 59.5 veces menos tiempo de ejecución que Ripser.

Rendimiento de Aprendizaje Automático

Los autores evaluaron el rendimiento de clasificadores y regresores de Random Forest entrenados con vectorizaciones de PD no reducidos (L1, qAP, AP) frente a PD totalmente reducidos (FR) en tres tareas:

1. Clasificación de Formas Sintéticas: Clasificar nubes de puntos (círculo, esfera, toro, etc.) con niveles variables de ruido.
2. Clasificación de Fashion-MNIST: Clasificar imágenes de ropa utilizando complejos cubicales.
3. Regresión de Árbol de Arterias Cerebrales: Predecir la edad del sujeto a partir de datos de escaneo cerebral 3D.

Hallazgos:

• Paridad y Mejora: En todos los experimentos, al menos un tipo de PD no reducido funcionó tan bien como o mejor que el PD totalmente reducido.
• Superioridad de L1: Los diagramas L1 consistentes mostraron un rendimiento igual o superior a los diagramas FR. En la tarea de Fashion-MNIST, los diagramas L1 superaron a los diagramas FR por al menos 10 puntos porcentuales en precisión promedio.
• Robustez: Estos resultados fueron robustos a través de diferentes tipos de filtración (Alpha, Rips), métodos de vectorización (Imágenes de Persistencia, coordenadas de Adcock-Carlsson) y niveles de ruido.
• Importancia de las Características: El análisis de la tarea de Fashion-MNIST reveló que los modelos L1 y FR dependían de regiones distintas del espacio de la imagen de persistencia. Las características más importantes para los modelos L1 se concentraron en $H_0$ (componentes conectadas), mientras que los modelos FR utilizaron características tanto de $H_0$ como de $H_1$ de manera más equilibrada. Esto sugiere que los diagramas no reducidos codifican información distinta y potencialmente útil que se descarta durante la reducción completa.

Significado y Reivindicaciones

El artículo concluye que los diagramas de persistencia no reducidos son sustitutos efectivos para los diagramas totalmente reducidos en los flujos de trabajo de aprendizaje automático topológico.

• Eficiencia Computacional: Al evitar el costoso paso de reducción, los practicantes pueden lograr reducciones significativas en el uso de memoria y tiempo de computación, permitiendo el análisis de conjuntos de datos que actualmente son intratables para los métodos de PH estándar.
• Rendimiento: Contrario al supuesto de que la reducción es necesaria para la calidad, los autores demuestran que la información descartada por la reducción a menudo no es crítica para el rendimiento del ML downstream e incluso los diagramas no reducidos pueden capturar características distintas y beneficiosas.
• Direcciones Futuras: Los autores señalan que, aunque los diagramas no reducidos ahorran computación, vectorizarlos puede ser más lento debido al mayor número de puntos. Sugieren que el trabajo futuro debería centrarse en diseñar algoritmos que computen las vectorizaciones directamente desde matrices no reducidas sin almacenar explícitamente todos los pares, optimizando aún más el flujo de trabajo.

El estudio afirma modestamente que estos resultados sugieren un cambio en la forma en que se construyen los flujos de trabajo de PH-ML, priorizando potencialmente la eficiencia computacional y la retención de características topológicas "crudas" sobre la estricta completitud matemática de los diagramas totalmente reducidos.