When One Point Is Not Enough: Addressing Ambiguous Instances in Dimensionality Reduction by Splitting

Resumen Técnico: Abordaje de Instancias Ambiguas en Reducción de Dimensionalidad mediante División

Definición del Problema
La Reducción de Dimensionalidad (DR) es una herramienta fundamental para visualizar datos de alta dimensión, sin embargo, es inherentemente un proceso con pérdida. Aunque la literatura existente ha catalogado diversas distorsiones, como el desgarro de variedades, este artículo identifica una fuente previamente pasada por alto de artefactos visuales: instancias ambiguas. Estas son puntos de datos que son altamente similares a múltiples vecindarios mutuamente disímiles en el espacio de alta dimensión.

Los métodos estándar de DR mapean cada instancia de datos a un único punto en el espacio visual. En consecuencia, una instancia ambigua no puede representar fielmente su pertenencia a múltiples vecindarios distintos simultáneamente. Se ve forzada a una única ubicación, resultando en una incrustación parcial de vecindario. En este estado, la instancia parece pertenecer solo a un vecindario (o a ninguno), oscureciendo su verdadera relación con otros grupos disímiles. Este artefacto es particularmente problemático para análisis a nivel de instancia, como la Inteligencia Artificial Explicable (XAI) o la biología de células individuales, donde comprender la estructura precisa del vecindario es crítico. Las métricas existentes, como la confiabilidad y la continuidad, no logran distinguir la incrustación parcial de vecindario de otras distorsiones porque operan sobre la incrustación final sin acceso a la ambigüedad subyacente de los datos.

Metodología
Los autores proponen un enfoque basado en grafos para identificar y resolver estas ambigüedades mediante la "división" de instancias ambiguas en múltiples puntos, cada uno colocado dentro de su respectivo vecindario. La metodología sigue el marco de DR de dos fases (relación y mapeo) introducido por Paulovich et al.:

1. Construcción y Esparsificación del Grafo:

   • Las relaciones de alta dimensión se modelan como un grafo ponderado no dirigido $G$.
   • Para exponer estructuras de vecindario significativas y eliminar bordes redundantes causados por la proximidad incidental, los autores aplican esparsificación espectral utilizando el algoritmo de Spielman-Srivastava. Esto produce un grafo reducido $\bar{G}$ que preserva las propiedades estructurales y algebraicas del original mientras elimina conexiones débiles.

2. Identificación de Instancias Ambiguas:

   • La ambigüedad se define topológicamente. Los autores adaptan el concepto de Puntos de Articulación Locales (LAP). Un vértice se considera un LAP si su eliminación aumenta el número de componentes conectados dentro de un vecindario inducido local de $r$ pasos.
   • Una instancia se considera ambigua si es un LAP en el grafo esparsificado $\bar{G}$. Esto indica que la instancia conecta vecindarios disjuntos que de otro modo estarían separados.
   • Se utiliza el Lema 3.1 para optimizar el cálculo: si un vértice no es un LAP en un radio determinado $r$, no puede ser un LAP en ningún radio mayor $r' > r$.

3. División de Vértices y Reglas de Decisión:

   • Una vez identificado un vértice ambiguo $v_i$, se divide en $K$ copias, donde $K$ corresponde al número de componentes conectados restantes después de eliminar $v_i$ de su vecindario local.
   • Reglas de Decisión: No se ejecutan todas las divisiones potenciales. El enfoque filtra:
     • Conexiones LAP-LAP: Si un borde une dos vecindarios y ambos extremos son LAPs, la división se suprime para evitar crear aislamiento artificial.
     • Conexiones débiles: Un umbral definido por el usuario $\tau_w$ (relación de la fuerza de conexión con el componente más fuerte) filtra divisiones donde la conexión a un vecindario es demasiado débil para ser significativa. Esto previene la creación de puntos visualmente aislados debido a fuerzas de atracción insuficientes.

4. Mapeo y Visualización:

   • El grafo modificado, que contiene vértices divididos, se proyecta en el espacio visual utilizando técnicas estándar de DR local (por ejemplo, UMAP o ForceAtlas2).
   • Codificación Visual: Las instancias divididas se representan como marcadores distintos (por ejemplo, cruces) conectados mediante líneas discontinuas a su posición original o entre sí, permitiendo a los analistas rastrear las múltiples pertenencias a vecindarios de un único punto de datos.

Contribuciones Clave

• Definición de Incrustación Parcial de Vecindario: El artículo introduce y define formalmente este artefacto específico que surge de instancias ambiguas, distinguiéndolo de las distorsiones generales de DR.
• Detección Basada en Teoría de Grafos: Presenta un método para identificar instancias ambiguas utilizando Puntos de Articulación Locales en grafos de vecindario esparsificados.
• Mecanismo de División: Los autores proponen un enfoque concreto, con complejidad temporal casi lineal, para dividir instancias ambiguas, replicándolas en la proyección para reflejar múltiples pertenencias a vecindarios.
• Validación Empírica: El enfoque se demuestra en diversos conjuntos de datos (SVHN, MNIST, corpus de texto y secuenciación de ARN de células individuales), mostrando que revela pertenencias a vecindarios ocultas no visibles en proyecciones estándar.

Resultados

• Insights Cualitativos: En el conjunto de datos SVHN, un dígito '1' mal clasificado (predicho como '7') se mostró en UMAP estándar como perteneciendo únicamente al vecindario de '7'. El enfoque propuesto dividió la instancia, revelando su similitud simultánea con el vecindario de '1', explicando así la ambigüedad del error del clasificador. De manera similar, en datos de texto, un artículo sobre "Modelos Asistidos por ILP para Toxicología" se mostró como perteneciente a ambos clústeres de ILP y Razonamiento Basado en Casos (CBR), una dualidad oscurecida en proyecciones estándar.
• Análisis Cuantitativo:
  • Impacto de la Esparsificación: Los experimentos que miden los $k$-vecinos más cercanos ($k$NN) preservados mostraron que la esparsificación espectral retiene estructuras de vecindario local comparables al grafo original (proporciones cercanas a 1 para la mayoría de los conjuntos de datos), aunque se observó cierta variación en datos de células individuales de alta dimensión intrínseca.
  • Limitaciones de las Métricas: Se encontró que las métricas estándar (confiabilidad y continuidad) son ineficaces para identificar instancias ambiguas, ya que estos puntos se distribuyen de manera similar a los puntos no ambiguos a través de las distribuciones de las métricas.
  • Sensibilidad a Parámetros: Aumentar el número de vecinos en el grafo inicial generalmente redujo el número de divisiones detectadas, ya que una mayor conectividad une vecindarios que de otro modo parecerían disjuntos.

Significado y Afirmaciones
El artículo argumenta que reconocer la ambigüedad es esencial para interpretar estructuras locales de grano fino en DR. Los autores afirman que no tener en cuenta las instancias ambiguas puede llevar a interpretaciones incompletas o incorrectas, particularmente en dominios como XAI y biología donde el contexto a nivel de instancia es vital. Al dividir estas instancias, el método proporciona una representación más fiel de la topología de alta dimensión de los datos, revelando "pertenencias a vecindarios previamente ocultas". El trabajo sugiere que las métricas actuales de calidad de DR son insuficientes para este tipo específico de artefacto y que los futuros marcos de evaluación deben tener en cuenta la ambigüedad impulsada por los datos en lugar de solo la inestabilidad inducida por el mapeo.