Resumen Técnico: Histogramas de Voronoi para la Vectorización Adaptativa de Diagramas de Persistencia Esperados

1. Planteamiento del Problema

El Análisis de Datos Topológicos (TDA) utiliza la Homología Persistente (PH) para capturar las características topológicas de nubes de puntos, codificadas como Diagramas de Persistencia (PD). Un PD representa características topológicas (ciclos) como puntos $(b, d)$ en un semiplano abierto $\Omega$, donde $b$ y $d$ denotan los tiempos de nacimiento y muerte. Sin embargo, los PD no pueden utilizarse directamente como entradas para algoritmos estándar de aprendizaje automático, lo que requiere su vectorización.

Un cuello de botella significativo en el uso de los PD es su alta complejidad computacional; obtener un PD puede alcanzar $O(m^3)$ o incluso $O(|X|^9)$ para características de dimensión 1. Para mitigar esto, se desarrolló el Diagrama de Persistencia Esperado (EPD). Un EPD es una distribución de características topológicas derivada de promediar los PD de múltiples submuestreos de una nube de puntos. Aunque los EPD reducen los costos de tiempo, los métodos de vectorización existentes para los EPD (como las Imágenes de Persistencia, las Siluetas de Persistencia y los Paisajes de Persistencia) dependen de funciones de transformación de puntos continuas predefinidas (por ejemplo, núcleos gaussianos o funciones de paisaje) y rejillas de discretización fijas. Estos métodos introducen decisiones de diseño con respecto a la suavidad, el ancho de banda y la resolución de la rejilla, lo que puede difuminar las diferencias de masa local o enfatizar regiones no óptimas en el plano $(nacimiento, muerte)$.

El artículo aborda la necesidad de un método de vectorización alternativo que evite los modelos explícitos de transformación de puntos suaves y, en su lugar, utilice una partición adaptativa dependiente de los datos para representar la distribución del EPD.

2. Metodología: Representación basada en Voronoi (Vrep)

Los autores proponen Vrep, un método de vectorización que trata el EPD empírico como una distribución de características topológicas y lo representa utilizando histogramas basados en Diagramas de Voronoi.

Mecanismo Central

1. Muestreo de Codebooks: En lugar de una rejilla fija, Vrep construye un conjunto de codebooks aleatorios $S$. Cada codebook $C = \{c_1, ..., c_k\}$ consiste en puntos muestreados del soporte del EPD (el conjunto de características topológicas).
2. Partición de Voronoi: Para un codebook dado $C$, el semiplano abierto $\Omega$ se particiona en celdas de Voronoi $V(c_i)$, donde cada celda contiene puntos más cercanos a $c_i$ que a cualquier otro $c_j$.
3. Construcción del Histograma: La representación $\Phi(\bar{\mu}, C)$ se define como el vector de masas normalizadas del EPD $\bar{\mu}$ que caen en cada celda de Voronoi:
   $$\Phi(\bar{\mu}, C) = [\bar{\mu}(V(c_1)), \bar{\mu}(V(c_2)), ..., \bar{\mu}(V(c_k))]$$
4. Agregación: Para formar la representación final $\hat{\Phi}(\bar{\mu})$, el método concatena los histogramas generados a partir de múltiples codebooks muestreados del conjunto de datos.
5. Variante Consciente de la Diagonal (Vrepd): Una variante específica, Vrepd, incluye una celda de Voronoi centrada en la diagonal $\partial\Omega$ (donde $b=d$). Esto es crucial para separar el ruido (características cerca de la diagonal) de las características topológicas significativas.

Estrategias de Muestreo de Codebook

El artículo evalúa tres estrategias para el muestreo de los puntos dentro de un codebook:

• Default (Por defecto): Muestreo uniforme del soporte del EPD.
• Persistence-Weighted (Pesado por Persistencia): Muestreo ponderado por la persistencia ($d-b$), priorizando las características significativas.
• Uniform (Uniforme): Muestreo desde un rectángulo fijo por encima de la diagonal (irrelevante para el EPD).

Normalización

El método normaliza el EPD a una norma $l_1$ unitaria ($\bar{\mu} \leftarrow \bar{\mu}/\bar{\mu}(\Omega)$). Esto trata al EPD como una distribución de probabilidad, asegurando que todos los EPD tengan la misma masa, lo que permite el uso directo de la distancia de Wasserstein para el análisis de estabilidad y la medición de disimilitud, evitando la necesidad de métricas de Transporte Parcial Óptimo.

3. Contribuciones Teóricas

El artículo establece garantías teóricas con respecto a la estabilidad y la capacidad de representación de Vrep bajo condiciones específicas:

• Límites de Estabilidad: Los autores demuestran que Vrep es estable bajo perturbaciones del EPD. Específicamente, si el EPD experimenta una perturbación $\Delta$ (pequeño movimiento de masas de Dirac), el cambio en la representación Vrep es Lipschitz continuo con respecto a $\Delta$. El límite de error depende del tamaño del codebook $k$ y las propiedades del conjunto de datos.
• Límites Relacionados con Wasserstein: El artículo proporciona un límite inferior condicional que relaciona la distancia $l_1$ entre dos vectores Vrep con la distancia de Wasserstein ($W_1$) entre los EPD subyacentes.
  $$\|\Phi(\bar{\mu}, C) - \Phi(\bar{\nu}, C)\|_1 \geq \frac{W_1(\bar{\mu}, \bar{\nu}) - \text{errores de aproximación}}{d_{max}(C)}$$
  Este resultado aclara que Vrep preserva eficazmente las variaciones de escala de Wasserstein cuando el codebook está "bien resuelto" (es decir, el error de aproximación es pequeño en relación con la separación de las distribuciones). No es una garantía de preservación monótona general, sino una declaración de consistencia condicional.

4. Resultados Experimentales

Los autores evaluaron Vrep y Vrepd en tareas de clasificación de nubes de puntos supervisadas y de reducción de dimensionalidad no supervisada, comparándolos con métodos estándar: Imagen de Persistencia (PI), Siluetas de Persistencia (PS), Paisaje de Persistencia (PL) y la red de extremo a extremo PointNet.

Desempeño de Clasificación

• Conjuntos de Datos: Los experimentos se realizaron en diversos conjuntos de datos, incluyendo estructuras de Proteínas, componentes mecánicos de CAD y datos de series temporales (transformados en nubes de puntos mediante el método de embebido de retardo temporal).
• Resultados: Vrep y Vrepd lograron consistentemente una precisión de clasificación mayor o comparable (usando un clasificador Random Forest) en comparación con PI, PS y PL en la mayoría de los conjuntos de datos sensibles a la topología.
  • En el conjunto de datos de Proteínas, Vrep alcanzó un 98.5% de precisión (frente al 95.5% de PI).
  • En los conjuntos de datos CAD, Vrep y Vrepd superaron a otros métodos no supervisados, aunque PI mostró resultados competitivos en algunos entornos con ruido.
• Sensibilidad del Codebook: La estrategia de muestreo de codebook persistente-pesada a menudo produjo los mejores resultados, particularmente en entornos ruidosos, ya que se enfoca en las características topológicas significativas.

Estabilidad y Escalabilidad

• Estabilidad de Perturbación: Experimentos en un conjunto de datos de sistema dinámico 3D mostraron que Vrep es estable bajo perturbaciones de ruido Gaussiano. Curiosamente, Vrepd (con la celda de la diagonal) demostró una estabilidad ligeramente superior a Vrep, probablemente debido a una mejor separación del ruido cerca de la diagonal.
• Complejidad Temporal:
  • Vrep tiene una complejidad temporal de $O(m^2tk)$ para un conjunto de datos de tamaño $m$, donde $t$ es el número de codebooks y $k$ es el tamaño del codebook. Es cuadrática respecto al tamaño del conjunto de datos.
  • Sin embargo, Vrep es más rápido que PL y PS en tiempo de ejecución real y escala mejor con el número de PD muestreados ($n$) porque submuestrea el soporte del EPD a un tamaño fijo, mientras que PI/PS/PL deben procesar cada PD muestreado individualmente.
  • Aunque PointNet (supervisado) logró una alta precisión, Vrep ofrece una alternativa competitiva para tareas no supervisadas (como la reducción de dimensionalidad) donde PointNet no puede aplicarse.

Reducción de Dimensionalidad No Supervisada

En una tarea de visualización t-SNE en un conjunto de datos de sistemas dinámicos, Vrep produjo clústeres con índices Calinski-Harabasz (CH) más altos (1751) en comparación con PI (569) y PL (1655), indicando una separación de clústeres superior.

5. Significado y Reivindicaciones

El artículo posiciona a Vrep como una representación complementaria en lugar de un reemplazo universal de los métodos existentes.

• Adaptativo vs. Suave: La contribución principal es el cambio de aproximaciones funcionales suaves basadas en núcleos hacia un conteo adaptativo dependiente de los datos. Vrep agrega masa sobre celdas definidas por los propios datos, lo que la hace potencialmente más fiel a la asignación de masa empírica del EPD.
• Compromiso (Trade-off): Los autores reconocen explícitamente el compromiso: Vrep resume eficientemente la asignación de masa gruesa, pero es inherentemente con pérdida de información respecto a la geometría fina dentro de una celda de Voronoi. En consecuencia, los métodos suaves (como PI o métodos de núcleo) pueden superar a Vrep cuando la variación topológica relevante implica cambios locales finos o de forma dentro de una celda.
• Utilidad No Supervisada: Un significado clave es la aplicabilidad del método a la enseñanza no supervisada. A diferencia de los enfoques de aprendizaje profundo supervisado (ej. PointNet, PersLay), Vrep no requiere etiquetas para la extracción de características, lo que la hace adecuada para tareas de reducción de dimensionalidad y agrupamiento (clustering).
• Reivindicaciones Modestas: Los autores no pretenden que Vrep domine todas las vectorizaciones existentes. Observan que los métodos de núcleo (PWGK, SWK) pueden superar a Vrep en conjuntos de datos específicos (ej. CAD) pero a un costo computacional significativamente mayor. El artículo concluye que Vrep es una alternativa adaptativa y competitiva que ofrece un escalado favorable con el número de PD muestreados y proporciona un sesgo de aproximación distinto adecuado para la clasificación sensible a la topología.