The Theory behind UMAP?

Cet article corrige les erreurs présentes dans la version originale de l'algorithme UMAP et fournit une dérivation complète et autonome des foncteurs de Spivak ainsi que de leur variante finie utilisée par McInnes et al.

L'essentiel

🌍 Le Guide de l'Explorateur : Réparer la carte du monde des données

Imaginez que vous êtes un explorateur moderne. Vous avez un tas de données (des points sur une carte) qui sont très complexes, comme une forêt dense vue du ciel. Votre but est de dessiner une carte simplifiée (en 2D ou 3D) qui garde l'essentiel de la forme de la forêt : où sont les rivières, où sont les montagnes, et quelles zones sont proches les unes des autres.

C'est ce que fait l'algorithme UMAP, très populaire chez les scientifiques. Mais il y a un problème : la "théorie" qui explique pourquoi UMAP fonctionne a été écrite un peu à la hâte, comme une brouillon de carte avec des trous et des erreurs.

Ce document, écrit par David Wegmann, c'est l'histoire d'un architecte qui décide de réparer cette carte. Il ne se contente pas de dire "ça marche", il veut prouver exactement pourquoi, en corrigeant les erreurs mathématiques des auteurs originaux.

Voici les 4 étapes de son voyage, expliquées simplement :

---

1. Le Problème : Une carte avec des trous 🗺️💥

Les créateurs d'UMAP (McInnes et al.) ont utilisé une idée mathématique très abstraite venant d'un autre chercheur (Spivak). Ils ont essayé de transformer des données floues (où un point peut appartenir à plusieurs groupes en même temps avec plus ou moins de force) en une forme géométrique.

L'analogie : Imaginez que vous essayez de construire une maison avec des briques qui changent de taille selon l'humeur. Les créateurs d'UMAP ont dit : "On va utiliser ces briques !". Mais en regardant de plus près, David Wegmann s'aperçoit que :

• Certaines formules utilisent des logarithmes de zéro (ce qui est mathématiquement impossible, comme diviser par zéro).
• Certaines règles de "collage" des briques ne fonctionnent pas toujours.
• Ils ont mélangé des concepts qui ne devraient pas être mélangés.

C'est comme si le plan de la maison disait : "Mettez un mur ici", mais le mur tombait tout de suite parce que les fondations étaient mal calculées.

2. La Solution : Reconstruire les fondations 🏗️✨

David Wegmann reprend tout depuis le début. Il ne jette pas la maison, il la reconstruit avec des matériaux solides.

• Les "Ensembles Flous" (Fuzzy Sets) : Imaginez un nuage de points. Un point peut être "très proche" du centre ou "juste un peu proche". En mathématiques classiques, un point est dedans ou dehors. Ici, on a un degré d'appartenance (comme un volume de musique : 100%, 50%, 10%).
• La Réparation : Wegmann montre comment transformer ces "nuages de probabilités" en objets géométriques solides (des espaces métriques) sans faire d'erreurs de calcul. Il remplace les formules cassées par des versions qui fonctionnent toujours, même dans les cas extrêmes.

L'image : Il remplace les briques fragiles par du béton armé. Il montre comment mesurer la "distance" entre deux points quand cette distance peut être infinie ou nulle, ce qui est crucial pour les données complexes.

3. Le Secret : Les "Briques" de taille variable 🧱📏

Le cœur de la théorie d'UMAP, c'est la réalisation métrique. C'est un processus qui prend un objet abstrait (un ensemble de données floues) et le transforme en un objet physique (un espace géométrique).

• L'analogie des Lego : Imaginez que vous avez des Lego. Dans la version originale (Spivax/McInnes), la taille du Lego changeait bizarrement selon la "force" du point, ce qui créait des trous.
• La version de Wegmann : Il dit : "Gardons le même Lego, mais changeons la façon dont on le mesure." Il utilise une règle mathématique précise (la métrique $L_1$, ou distance de Manhattan, comme dans un jeu de ville en grille) pour s'assurer que tout colle parfaitement, sans que les pièces ne se chevauchent ou ne laissent de vides.

Il prouve que si vous suivez ses règles, vous obtiendrez toujours une forme géométrique valide, peu importe la complexité des données d'entrée.

4. Le Lien avec UMAP : La carte finale 🗺️🚀

Enfin, Wegmann regarde comment tout cela se relie à l'algorithme UMAP que tout le monde utilise.

• Ce que dit UMAP : "On prend nos données, on crée un graphe (des points reliés par des lignes), et on le comprime."
• Ce que prouve Wegmann : Il montre que l'étape où UMAP "comprime" les données est en fait une application de sa théorie réparée.
  • Les lignes du graphe sont comme des "ponts" entre des îles de données.
  • La "force" de la ligne (le poids) indique à quel point les îles sont proches.
  • L'algorithme essaie de recréer une carte 2D où la longueur des ponts correspond à la force des liens.

Le verdict : Wegmann confirme que l'intuition d'UMAP est bonne, mais il précise que certaines justifications mathématiques dans l'article original étaient un peu "magiques" (ou erronées). Il remplace la magie par des mathématiques solides.

🎯 En résumé

Ce document est un manuel de réparation pour les mathématiciens et les data scientists.

• Avant : "Faites confiance à la théorie, ça marche bien en pratique, même si les formules sont un peu bizarres."
• Après (avec Wegmann) : "Voici exactement comment les formules doivent fonctionner, pourquoi elles fonctionnent, et comment on peut les utiliser sans avoir peur que tout s'effondre."

C'est comme passer d'une recette de cuisine écrite sur un essuie-tout taché ("ajoutez un peu de sel, peut-être") à un livre de cuisine professionnel avec des mesures exactes et des explications sur la chimie des aliments. Le plat (UMAP) reste délicieux, mais maintenant vous savez exactement pourquoi il a bon goût.

Résumé technique

Voici un résumé technique détaillé de la thèse de David Wegmann, intitulée « The Theory behind UMAP ? », rédigé en français.

1. Problématique

L'algorithme UMAP (Uniform Manifold Approximation and Projection), introduit par McInnes et al. en 2018, est devenu un outil de réduction de dimension extrêmement populaire. Sa justification théorique repose sur une construction catégorielle appelée réalisation métrique (metric realization), dérivée d'un brouillon non publié de David Spivak.

Cependant, la thèse identifie plusieurs erreurs fondamentales, des lacunes logiques et des définitions incorrectes dans les travaux de Spivak [9] et leur reprise par McInnes et al. [5] :

• Définitions erronées des ensembles flous : Les définitions des ensembles flous (fuzzy sets) et des catégories associées dans [5] et [9] sont incorrectes (notamment concernant la topologie sur l'intervalle $(0, 1]$ et la nature des préfaisceaux vs faisceaux).
• Problèmes de définition de la réalisation métrique : La formule de la réalisation métrique originale contient des erreurs mathématiques, notamment l'utilisation de logarithmes de paramètres qui peuvent être nuls ou égaux à 1, entraînant des divisions par zéro ou des définitions de métriques non valides.
• Non-expansivité : La preuve que les applications induites par la réalisation métrique sont non-expansives (non-expansive maps) est fautive dans la littérature existante, en particulier concernant les métriques utilisées sur les simplexes.
• Manque de rigueur sur les variantes finies : La version « finie » de l'algorithme utilisée par UMAP n'est pas rigoureusement définie dans les travaux antérieurs, laissant place à des interprétations vagues.

L'objectif de cette thèse est de réparer ces erreurs, de fournir une construction explicite et auto-contenue de la réalisation métrique de Spivak et de sa variante finie, et d'établir un lien rigoureux entre cette théorie et l'algorithme UMAP.

2. Méthodologie

L'auteur utilise une approche basée sur la théorie des catégories et la topologie algébrique pour reconstruire les fondements théoriques :

• Fondements Catégoriels : La thèse commence par établir les prérequis nécessaires : les extensions de Kan à gauche, les embeddings de Yoneda, les limites et colimites, et la théorie des faisceaux sur les locales (espaces topologiques sans points).
• Révision des Ensembles Valorisés (Valued Sets) : L'auteur reformule la théorie des ensembles flous en s'appuyant sur les travaux de Barr [1]. Il distingue clairement entre :
  • Les ensembles classiques valorisés (définis par une application de valeur dans un locale).
  • Les ensembles valorisés comme faisceaux (une perspective plus puissante et équivalente sous certaines conditions de connectivité totale du locale).
    Il prouve explicitement l'équivalence de catégories entre ces deux perspectives, comblant les lacunes des travaux antérieurs.
• Construction de la Réalisation Métrique :
  • L'auteur définit la catégorie des espaces pseudo-métriques étendus ($EPMet$), qui permet des distances infinies et nulles entre points distincts, garantissant la complétude de la catégorie (existence de toutes les colimites).
  • Il construit la réalisation métrique comme une extension de Kan à gauche d'un foncteur définissant des simplexes métriques.
  • Correction critique : Contrairement à Spivak qui utilisait la métrique euclidienne ($\ell_2$) et des simplexes dont la taille changeait l'ensemble sous-jacent, Wegmann utilise la métrique $\ell_1$ (de Manhattan) et garde l'ensemble sous-jacent constant, en ne modifiant que l'échelle de la métrique. Cela résout les problèmes de non-expansivité des applications de dégénérescence.
• Variantes Finies : L'auteur définit rigoureusement les sous-catégories finies (espaces métriques finis, ensembles flous finis) et prouve l'existence de la réalisation métrique finie en tant qu'extension de Kan, en démontrant que les colimites nécessaires existent bien dans ces sous-catégories restreintes.

3. Contributions Clés

1. Correction des Erreurs Fondamentales : La thèse identifie et corrige les erreurs mathématiques dans les définitions des ensembles flous, des métriques sur les simplexes et des propriétés de non-expansivité présentes dans [5] et [9].
2. Description Explicite de la Réalisation Métrique :
   • Fournit une description complète de la réalisation métrique et de son adjoint (le nerf singulier) en termes d'ensembles classiques valorisés (normés), rendant le calcul concret et compréhensible.
   • Démonstration que la métrique $\ell_1$ est la seule métrique $\ell_p$ ($p \in [1, \infty]$) qui préserve la propriété de non-expansivité pour les applications de dégénérescence.
3. Construction Rigoureuse de la Variante Finie : Définition précise des catégories finies nécessaires pour UMAP et preuve de l'existence de la réalisation métrique finie, comblant le vide conceptuel laissé par McInnes et al.
4. Équivalence des Perspectives : Établissement explicite de l'équivalence entre la perspective des ensembles flous classiques et la perspective des faisceaux, permettant de naviguer entre les deux formalismes selon les besoins de calcul ou de preuve.
5. Analyse Critique de UMAP : Une évaluation honnête et rigoureuse des affirmations théoriques de l'algorithme UMAP, distinguant ce qui est prouvé mathématiquement de ce qui reste une conjecture ou une intuition non justifiée.

4. Résultats

• Théorème d'Équivalence : Les catégories d'ensembles flous classiques et d'ensembles flous comme faisceaux sont équivalentes pour les locales totalement connectés.
• Formule de Réalisation : La thèse fournit une formule explicite pour la réalisation métrique d'un ensemble simplicial normé classique : c'est un quotient d'une somme disjointe de simplexes métriques, où la taille du simplexe est déterminée par la norme de l'élément.
• Validité de la Variante Finie : Il est prouvé que la réalisation métrique finie existe bien et correspond à une extension de Kan, même si la catégorie cible n'est pas complètement cocomplète (elle est seulement finiment cocomplète).
• Correspondance avec UMAP :
  • L'auteur confirme que les graphes pondérés locaux utilisés dans UMAP correspondent effectivement à la 1-squelette du nerf singulier fini.
  • Cependant, il démontre que l'interprétation des poids des arêtes comme des probabilités (utilisée pour justifier l'union probabiliste et la fonction de perte par entropie croisée dans UMAP) n'est pas étayée par une argumentation probabiliste formelle dans la littérature existante.

5. Signification et Impact

Cette thèse est significative pour plusieurs raisons :

• Rigueur Mathématique : Elle offre la première reconstruction mathématiquement solide et auto-contenue de la théorie derrière UMAP, éliminant les erreurs qui ont persisté depuis l'introduction de l'algorithme.
• Clarification Conceptuelle : En distinguant clairement les différentes variantes (classique vs faisceau, métrique $\ell_1$ vs $\ell_2$), elle clarifie la nature exacte de ce que l'algorithme calcule.
• Limites de la Théorie Actuelle : La thèse met en lumière que, bien que la construction catégorielle (la réalisation métrique) soit maintenant correcte, les justifications probabilistes avancées par les créateurs de UMAP pour expliquer pourquoi l'algorithme préserve la topologie des données manquent de fondement formel.
• Fondation pour l'Avenir : Ce travail fournit une base théorique solide pour les futurs développements de l'algorithme UMAP ou d'autres méthodes de réduction de dimension basées sur des concepts topologiques et catégoriels, permettant de construire des variantes plus robustes et mieux comprises.

En résumé, David Wegmann réussit à transformer une théorie populaire mais mathématiquement fragile en un cadre rigoureux, tout en restant critique sur les affirmations non prouvées concernant la nature probabiliste de l'algorithme.