The Theory behind UMAP?

Este artículo corrige los errores presentes en la implementación original de UMAP por McInnes et al., ofrece una derivación completa y autorreferida de los funtores de Spivak y su variante finita, y analiza la correspondencia teórica entre dicha variante y el algoritmo UMAP.

Lo esencial

Imagina que tienes una montaña de datos: miles de puntos de información que parecen un caos total. Tu objetivo es reducir esa montaña a un mapa simple de dos o tres dimensiones (como un dibujo en una hoja de papel) sin perder la esencia de cómo se relacionan esos puntos entre sí.

Aquí es donde entra UMAP, un algoritmo muy popular que hace exactamente eso. Pero, ¿cómo sabe UMAP qué conservar y qué tirar?

Este documento, escrito por David Wegmann, es como un detective que revisa las instrucciones de un manual de cocina. El manual original (el artículo de 2018 que creó UMAP) tenía una teoría matemática muy bonita, pero estaba escrita en un idioma confuso y contenía varios errores de cálculo. Wegmann se dedica a:

1. Encontrar los errores: Señalar dónde las matemáticas originales fallaban.
2. Reescribir la receta: Corregir esos errores con una teoría sólida y clara.
3. Explicar el "por qué": Demostrar que el algoritmo realmente funciona como dicen que funciona.

La Analogía del "Lego de Fuzziness" (Borrosidad)

Para entender la teoría detrás de UMAP, imagina que los datos no son puntos rígidos, sino bloques de Lego de goma.

• La realidad borrosa: En el mundo real, las cosas no son "blancas o negras". Un punto de datos puede pertenecer a un grupo con un 80% de certeza y a otro con un 20%. A esto los matemáticos lo llaman "conjunto difuso" (fuzzy set).
• Los bloques de construcción: UMAP intenta construir una estructura (un espacio) usando estos bloques de goma. Cada bloque tiene un tamaño y una "fuerza" de unión.

El Problema Original: Un Mapa con Baches

El artículo original de 2018 (de McInnes et al.) dijo: "Aquí tienes la fórmula mágica para convertir tus bloques de goma en un mapa". Pero Wegmann encontró que la fórmula tenía baches:

• A veces dividía por cero (un error matemático grave).
• A veces usaba reglas que no cuadraban con la lógica de los bloques de goma.
• La explicación de cómo se unían las piezas era confusa.

Wegmann dice: "Esperen, si usamos esta fórmula, el edificio se cae. Vamos a arreglar los cimientos".

La Solución: La "Realización Métrica"

Wegmann introduce un concepto llamado "Realización Métrica". Imagina que tienes un dibujo esquemático de una ciudad (tus datos) y quieres construir la ciudad real.

1. El dibujo (Simplicial Fuzzy Sets): Es tu lista de datos con sus conexiones borrosas.
2. La construcción (Metric Realization): Es el proceso de tomar ese dibujo y convertirlo en un espacio físico donde las distancias tienen sentido.

Wegmann demuestra matemáticamente cómo tomar ese dibujo borroso y convertirlo en un espacio de distancias (como un mapa de carreteras) de una manera que no tiene errores. Él usa herramientas matemáticas avanzadas (categorías, funtores, haces) que son como andamios y grúas para construir el edificio sin que se caiga.

¿Qué tiene que ver esto con UMAP?

UMAP es el algoritmo que usa esta teoría para reducir dimensiones.

• Paso 1: UMAP mira tus datos y crea pequeños "vecindarios" (grafos) donde los puntos cercanos se unen con una fuerza (peso).
• Paso 2: Une todos esos vecindarios en una gran red.
• Paso 3: Usa la teoría corregida por Wegmann para "estirar" y "comprimir" esa red hasta que quepa en 2D o 3D, manteniendo las conexiones importantes.

La Conclusión del Detective

Wegmann concluye que:

• La teoría detrás de UMAP sí tiene sentido, pero solo si corregimos los errores matemáticos del documento original.
• UMAP no es magia; es una construcción matemática muy precisa que, una vez arreglada, explica perfectamente por qué el algoritmo preserva la forma de los datos (como si mantuvieras la forma de una montaña al convertirla en un dibujo).
• Aunque el documento original tenía errores, la idea central de McInnes et al. era correcta y Wegmann ha proporcionado el "manual de instrucciones" definitivo y sin errores para entenderlo.

En resumen: Este paper es la "edición corregida y aumentada" de la teoría de UMAP. Es como si alguien hubiera escrito un libro de instrucciones para armar un mueble IKEA, pero con algunas piezas mal numeradas. Wegmann es quien revisó el libro, encontró los errores, reescribió las instrucciones paso a paso y nos aseguró que, si seguimos su versión, el mueble (el mapa de datos) quedará perfecto.

Resumen técnico

Aquí presento un resumen técnico detallado del documento "The Theory behind UMAP?" de David Wegmann, estructurado según los puntos solicitados.

1. El Problema

El algoritmo UMAP (Uniform Manifold Approximation and Projection), introducido por McInnes et al. en 2018, es una herramienta extremadamente popular para la reducción de dimensionalidad. Sin embargo, la justificación teórica presentada en el artículo original [5] se basa en una variante finita de un functor llamado "realización métrica" (metric realization), propuesto originalmente en un borrador no publicado de David Spivak [9].

El problema central identificado por el autor es que tanto el borrador de Spivak como la implementación teórica de McInnes et al. contienen errores matemáticos significativos, lagunas en las demostraciones y definiciones incorrectas que comprometen la validez rigurosa de la teoría subyacente. Específicamente:

• Definiciones de conjuntos difusos: Se utilizan definiciones incorrectas de conjuntos difusos como pre-functoriales o haces (sheaves) que no cumplen con las condiciones de equivalencia de categorías necesarias.
• Errores en la Realización Métrica: La definición original utiliza logaritmos de parámetros que pueden ser cero (causando división por cero o logaritmos indefinidos) y emplea la métrica euclidiana ($\ell_2$), lo cual falla al garantizar que las aplicaciones de degeneración sean no expansivas.
• Falta de rigor en la construcción: La conexión entre la construcción teórica (realización métrica) y el algoritmo práctico (UMAP) se basa en interpretaciones vagas de categorías "finitas" y "acotadas" sin una definición formal precisa.

2. Metodología

El autor adopta un enfoque puramente categórico y topológico para reparar y reconstruir la teoría desde cero. La metodología se basa en los siguientes pilares:

• Teoría de Categorías y Topos: Se utiliza la teoría de categorías avanzada, incluyendo extensiones de Kan izquierda, embeddings de Yoneda, y la teoría de haces sobre locales (espacios sin puntos).
• Reformulación de Conjuntos Valorados: Se redefine la base teórica utilizando "conjuntos valorados" (valued sets) y "conjuntos normados" (normed sets) en lugar de los conjuntos difusos mal definidos de Spivak. Se demuestra la equivalencia entre la perspectiva clásica (conjuntos con mapas de pertenencia) y la perspectiva de haces (sheaf-theoretic).
• Construcción de la Realización Métrica:
  • Se define la categoría de espacios pseudo-métricos extendidos (EPMet), que permite distancias infinitas y cero entre puntos distintos, garantizando que la categoría sea cocompleta (necesaria para la existencia de extensiones de Kan).
  • Se reemplaza la métrica euclidiana por la métrica $\ell_1$ (Manhattan) en los símplices métricos. Esto es crucial para asegurar que los mapas de degeneración sean no expansivos.
  • Se evita el uso de logaritmos directos en la definición de los símplices, optando por escalar la métrica en lugar de escalar el conjunto subyacente, resolviendo así los problemas de división por cero cuando el parámetro de tamaño es 1.
• Formalización de la Variante Finita: Se proporcionan definiciones precisas para las categorías finitas (Fin-EPMet y Fin-USFuz) que utiliza McInnes et al., demostrando la existencia de la realización métrica finita mediante el análisis de colímites en subcategorías completas.

3. Contribuciones Clave

El trabajo aporta varias correcciones y construcciones explícitas que no existían en la literatura previa:

1. Corrección de Errores Fundamentales: Se identifican y reparan errores en las definiciones de conjuntos difusos, la topología del intervalo $(0, 1]$, y la construcción del functor de realización métrica.
2. Descripción Explícita de la Realización Métrica: Se ofrece una descripción completa y rigurosa del functor de realización métrica ($MetRe$) y su adjunto (la "nervio singular" o singular nerve), tanto en su versión clásica (en términos de conjuntos normados) como en su versión de haces.
3. Uso de la Métrica $\ell_1$: Se demuestra que la métrica $\ell_1$ es la única métrica $\ell_p$ que hace que la realización métrica sea un functor bien definido (preservando la propiedad de no expansión en mapas de degeneración), corrigiendo el uso incorrecto de la métrica euclidiana en trabajos anteriores.
4. Equivalencia de Categorías: Se construyen explícitamente los funtores de equivalencia entre la categoría de conjuntos difusos clásicos y la categoría de haces sobre locales, proporcionando las herramientas necesarias para traducir entre ambas perspectivas.
5. Validación de la Variante Finita: Se demuestra formalmente que la variante finita de la realización métrica propuesta por McInnes et al. existe y está bien definida, aclarando las definiciones ambiguas de "finito" y "acotado".

4. Resultados

• Construcción Rigurosa: Se ha establecido que la realización métrica es una extensión de Kan izquierda bien definida desde la categoría de símplices de conjuntos normados (o difusos) hacia la categoría de espacios pseudo-métricos extendidos.
• Corrección de la Interpretación de UMAP: Se ha demostrado que el algoritmo UMAP puede interpretarse teóricamente como un proceso que:
  1. Construye un "nervio singular finito" ($FinSing$) de los datos, donde las aristas del grafo corresponden a elementos de un conjunto difuso clásico con una fuerza de pertenencia $e^{-d(x,y)}$.
  2. Realiza una unión de estos grafos locales utilizando una T-conorma probabilística.
  3. Aplica una realización métrica finita para obtener un espacio métrico que preserva la estructura topológica.
• Análisis de las Afirmaciones de McInnes et al.:
  • Se confirma que la correspondencia entre los grafos locales y el 1-esqueleto del nervio singular es correcta bajo la nueva definición formal.
  • Se señala que la afirmación de que los pesos de las aristas representan "probabilidades" de existencia de una arista carece de justificación teórica formal en el artículo original y requiere más trabajo para ser validada.
  • Se indica que no existen teoremas formales en la literatura que garanticen que el algoritmo preserva la estructura topológica de la variedad de Riemann subyacente, a pesar de las afirmaciones hechas.

5. Significancia

Este trabajo es fundamental para la comunidad de aprendizaje automático y ciencia de datos por las siguientes razones:

• Rigor Matemático: Proporciona la base teórica sólida y libre de errores que el algoritmo UMAP necesitaba, transformando una justificación heurística en una construcción matemática rigurosa.
• Clarificación Conceptual: Diferencia claramente entre las interpretaciones "clásicas" (conjuntos normados) y "de haces" de los conjuntos difusos, permitiendo a los investigadores elegir la perspectiva más adecuada para sus aplicaciones.
• Validación y Limitaciones: Si bien valida la estructura matemática de la construcción teórica detrás de UMAP, también actúa como una advertencia crítica: la teoría matemática reparada no prueba automáticamente que el algoritmo funcione bien en la práctica para todos los casos de uso. Las afirmaciones sobre la preservación de la topología de variedades y la interpretación probabilística de los pesos siguen siendo conjeturas no demostradas que requieren investigación futura.
• Herramienta para Futuras Investigaciones: Al proporcionar definiciones precisas de las categorías finitas y los funtores involucrados, habilita el desarrollo de variantes del algoritmo con garantías teóricas más fuertes y la exploración de nuevas aplicaciones basadas en la teoría de haces y la topología algebraica.

En resumen, Wegmann no solo "repara" la teoría de UMAP, sino que la eleva a un estándar de rigor matemático que permite una comprensión profunda de lo que el algoritmo hace realmente, separando la construcción formal de las afirmaciones empíricas no verificadas.