💻 computer science

Unreduced Persistence Diagrams for Topological Machine Learning

Cet article démontre que les pipelines d'apprentissage automatique utilisant des caractéristiques topologiques dérivées de diagrammes de persistance non réduits peuvent atteindre des performances comparables ou supérieures à celles utilisant des diagrammes entièrement réduits, tout en offrant simultanément des avantages significatifs en termes de coût computationnel et d'efficacité mémoire.

Auteurs originaux : Nicole Abreu, Parker B. Edwards, Francis Motta

Publié 2026-06-19

📖 4 min de lecture☕ Lecture pause café

CC BY 4.0

Auteurs originaux : Nicole Abreu, Parker B. Edwards, Francis Motta

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayiez d'apprendre à un ordinateur à reconnaître des formes, comme faire la différence entre un cercle, une sphère et un donut (tore). Pour ce faire, les mathématiciens utilisent un outil appelé homologie persistante. Considérez cet outil comme un « scanner topologique » qui observe un nuage de points et demande : « Où sont les trous ? Où sont les boucles ? »

Le scanner produit un rapport appelé Diagramme de Persistance (DP). Ce rapport est une liste de points, où chaque point représente une caractéristique (comme un trou) et la durée pendant laquelle elle a « persisté » avant de disparaître à mesure que la forme grandissait.

Le Problème : Le Rapport Onéreux

Traditionnellement, pour obtenir ce rapport, l'ordinateur doit effectuer un travail colossal appelé « réduction ». C'est comme si un bibliothécaire tentait d'organiser une bibliothèque en vérifiant chaque livre par rapport à tous les autres pour supprimer les doublons et trouver le résumé parfait. Ce processus est :

Lent : Cela prend beaucoup de temps.
Gourmand en mémoire : Cela nécessite une énorme quantité de RAM (mémoire) informatique.
Gaspilleur : Les auteurs ont remarqué quelque chose d'étrange. Lorsque l'on injectait ces rapports détaillés dans des modèles d'apprentissage automatique, les modèles ignoraient la majeure partie de l'information. C'était comme si le bibliothécaire avait passé des heures à écrire un résumé de 500 pages, mais que le lecteur n'avait besoin que des trois premières phrases pour comprendre l'histoire.

La Solution : L'Esquisse « Non Réduite »

Les auteurs ont posé une question simple : Et si nous sautions l'étape lourde de l'édition ?

Au lieu de faire la « réduction » complète pour obtenir le rapport parfait et final, ils proposent d'utiliser des Diagrammes de Persistance Non Réduits.

L'analogie : Imaginez que vous dessinez un visage. La méthode « réduite » est comme un artiste professionnel passant des heures à affiner chaque ligne, à effacer les erreurs et à perfectionner l'ombrage avant de vous montrer le dessin. La méthode « non réduite » est comme esquisser rapidement les traits principaux (yeux, nez, bouche) directement à partir des données brutes, sans effacer ni raffiner.
Le résultat : Étonnamment, l'ordinateur (le modèle d'apprentissage automatique) peut souvent reconnaître le visage aussi bien à partir d'une esquisse rapide qu'à partir d'un chef-d'œuvre poli.

Ce Qu'Ils Ont Fait

L'équipe a construit une nouvelle version plus rapide du logiciel (basée sur un outil populaire appelé Ripser) qui saute l'édition lourde. Au lieu du rapport complet, il génère ces « esquisses » (qu'ils appellent Diagrammes Non Réduits ou des types spécifiques comme Low-Ones et Quasi-Apparent Pairs).

Ils ont testé cela sur trois défis différents :

Reconnaissance de Formes : Distinguer des cercles, des sphères et des donuts dans des données bruitées.
Classification d'Images : Identifier des articles de mode (comme des sandales versus des baskets) dans le jeu de données Fashion-MNIST.
Régression de Scanners Cérébraux : Prédire l'âge d'une personne en se basant sur la structure des vaisseaux sanguins de son cerveau.

Les Résultats

Performance : Dans presque tous les tests, les modèles entraînés sur les « esquisses » (diagrammes non réduits) ont obtenu des performances aussi bonnes, voire parfois meilleures, que les modèles entraînés sur les « rapports polis » (diagrammes entièrement réduits).
Vitesse et Mémoire : C'est la victoire majeure. Parce qu'ils ont sauté l'édition lourde :
- La nouvelle méthode a utilisé beaucoup moins de mémoire (parfois jusqu'à 13 fois moins).
- Elle était beaucoup plus rapide, surtout en utilisant plusieurs cœurs d'ordinateur simultanément (traitement parallèle).
- Dans un cas extrême, l'ancienne méthode est tombée en panne de mémoire et a planté, tandis que la nouvelle méthode a terminé le travail avec succès.

Le Bémol (Stabilité)

Les auteurs admettent que ces « esquisses » sont un peu plus sensibles au bruit que les « rapports polis ». Si vous secouez trop les données, l'esquisse peut changer de forme de manière plus radicale que le rapport poli. Cependant, dans leurs expériences avec des niveaux de bruit réalistes, les esquisses sont restées suffisamment stables pour être utiles.

L'Essentiel

L'article suggère que dans le monde de l'apprentissage automatique topologique, nous perdons peut-être beaucoup de temps et de puissance informatique à essayer de rendre nos rapports de données « parfaits ». En utilisant des Diagrammes de Persistance Non Réduits, nous pouvons obtenir un résumé « assez bon » beaucoup plus rapidement et avec moins de mémoire, et l'ordinateur apprend tout aussi efficacement grâce à lui. C'est un compromis : une esquisse légèrement plus brute pour un gain massif de vitesse et d'efficacité.

Résumé technique : Diagrammes de persistance non réduits pour l'apprentissage automatique topologique

Énoncé du problème

L'analyse des données topologiques (TDA) combinée à l'apprentissage automatique (ML) supervisé est devenue une approche standard pour analyser des données complexes dans divers domaines, notamment la biologie, les neurosciences et la science des matériaux. Le pipeline standard consiste à calculer l'homologie persistante (PH) pour générer des diagrammes de persistance (PD), puis à vectoriser ces diagrammes et à entraîner des modèles de ML.

Cependant, deux inefficacités critiques ont été observées dans ce pipeline :

Redondance de l'information : Des preuves empiriques suggèrent que les modèles de ML ignorent souvent une partie importante de l'information contenue dans les diagrammes de persistance vectorisés. Par exemple, des tâches de régression ont montré des performances « quasi optimales » en utilisant uniquement la persistance du 28e point le plus persistant, et des tests indiquent que les vectorisations statistiques naïves sont souvent aussi performantes que les plus complexes.
Coût computationnel : Le calcul de PD entièrement réduits est souvent l'étape la plus exigeante en termes de ressources dans le pipeline, nécessitant une mémoire et un temps substantiels, particulièrement pour les grands ensembles de données.

L'hypothèse centrale de ce travail est que si les modèles de ML peuvent obtenir de bonnes performances avec des vectorisations qui rejettent de l'information, alors le calcul complet de la PH (spécifiquement la réduction des matrices de bord) peut être une dépense computationnelle inutile. Les auteurs proposent d'éviter entièrement la réduction de la matrice de bord en utilisant des diagrammes de persistance non réduits dérivés directement de matrices de bord non réduites.

Méthodologie

Cadre théorique

Les auteurs définissent plusieurs types de diagrammes de persistance (PD) non réduits construits à partir d'une matrice de bord $M$ sans effectuer l'algorithme de réduction par colonnes standard. Ils sont définis selon les propriétés des colonnes de la matrice :

Diagramme de paires apparentes (AP) : Paires $(low(M_j), j)$ où l'entrée non nulle la plus basse dans la colonne $j$ est la seule entrée non nulle dans cette ligne à gauche (un motif spécifique indiquant une paire de persistance sans réduction).
Diagramme de paires quasi-apparentes inférieures (qAP↓) : Paires $(low(M_j), j)$ où $\beta(M_j) \neq -1$ .
Diagramme de paires quasi-apparentes supérieures (qAP↑) : Paires $(\beta(M_j), j)$ où $\beta(M_j) \neq -1$ . Ici, $\beta(M_j)$ est l'indice de ligne le plus élevé contenant un 1 dans la colonne $j$ qui ne peut pas être éliminé par réduction.
Diagramme Low-Ones (L1) : Le multiensemble de paires $(low(M_j), j)$ pour toutes les colonnes où $low(M_j) \neq -1$ .

Les constructions L1 et qAP↑ sont particulièrement mises en avant pour les complexes de Vietoris-Rips (VR), car les autres types de PD non réduits peuvent ne produire que des paires éphémères (persistance nulle) dans les dimensions d'homologie supérieures pour ces filtrations.

Analyse de stabilité

L'article étudie la stabilité de Lipschitz de ces transformations par rapport à la distance de bottleneck ( $d_B$ ).

Résultats théoriques : La transformation de PD entièrement réduite (FR) est globalement stable avec une constante de Lipschitz $C=1$ . En revanche, les PD non réduits (AP, qAP) ne sont généralement pas globalement stables. De petites perturbations dans la fonction de filtration peuvent réordonner les colonnes de la matrice de bord, provoquant l'apparition ou la disparition de paires apparentes, ce qui entraîne une instabilité combinatoire.
Stabilité locale : Les auteurs proument que les PD non réduits sont localement Lipschitz stables. Si la perturbation de la fonction de filtration est suffisamment petite pour préserver l'ordre des simplexes (plus précisément, plus petite que la moitié de l'écart minimum entre les valeurs de filtration adjacentes), les transformations restent stables.
Stabilité expérimentale : Des expériences computationnelles sur des nuages de points perturbés montrent que, bien que des pics d'instabilité importants (où le nombre de points dans le diagramme change) surviennent, ils sont rares. La majorité des perturbations entraînent des ratios de stabilité comparables ou meilleurs que ceux du cas entièrement réduit.

Implémentation computationnelle

Pour évaluer les avantages computationnels, les auteurs ont implémenté une version modifiée de l'algorithme Ripser afin de calculer les diagrammes qAP↑ pour les complexes VR.

Parallélisation : Contrairement à l'algorithme de réduction standard, qui traite les colonnes sériellement (de gauche à droite), le calcul des diagrammes qAP↑ peut être parallélisé. L'algorithme parcourt les colonnes de la matrice de cobord de la filtration de manière indépendante.
Efficacité de la mémoire : L'implémentation évite de stocker la matrice de bord complète et les bordures de travail nécessaires à la réduction. Elle utilise une table de hachage pour stocker les paires et ignore les « paires à zéro apparent » (paires éphémères) précocement dans le processus.

Résultats clés

Performance computationnelle

Le benchmarking sur un système AMD Ryzen Threadripper PRO à 32 cœurs contre Ripser standard a révélé des gains significatifs :

Temps d'exécution (Wall Time) : Le calcul parallèle de qAP↑ a obtenu une accélération moyenne de 20x du temps d'exécution par rapport au calcul de la persistance complète.
Mémoire : L'approche non réduite a nécessité environ 1/13e de la mémoire de Ripser pour les exemples non seuillés et 1/1,86 pour les exemples seuillés.
Scalabilité : Les auteurs ont réussi à calculer des diagrammes non réduits pour le jeu de données torus4 (50 000 points), une tâche où Ripser a échoué en raison de contraintes de mémoire (nécessitant >300 Go de RAM). Pour le jeu de données cyclo-octane, le calcul qAP↑ a utilisé 454 fois moins de mémoire et 59,5 fois moins de temps d'exécution que Ripser.

Performance en apprentissage automatique

Les auteurs ont évalué les performances de classifieurs et de régresseurs Random Forest entraînés sur des vectorisations de PD non réduits (L1, qAP, AP) par rapport aux PD entièrement réduits (FR) à travers trois tâches :

Classification de formes synthétiques : Classer des nuages de points (cercle, sphère, tore, etc.) avec différents niveaux de bruit.
Classification Fashion-MNIST : Classer des images de vêtements en utilisant des complexes cubiques.
Régression d'arbre artériel cérébral : Prédire l'âge du sujet à partir de données d'imagerie cérébrale 3D.

Constatations :

Parité et amélioration : Dans toutes les expériences, au moins un type de PD non réduit a performé aussi bien ou mieux que le PD entièrement réduit.
Supériorité de L1 : Les diagrammes L1 ont systématiquement performé au même niveau ou mieux que les diagrammes FR. Dans la tâche Fashion-MNIST, les diagrammes L1 ont surpassé les diagrammes FR d'au moins 10 points de pourcentage en précision moyenne.
Robustesse : Ces résultats étaient robustes à travers différents types de filtrations (Alpha, Rips), méthodes de vectorisation (Images de Persistance, coordonnées d'Adcock-Carlsson) et niveaux de bruit.
Importance des caractéristiques : L'analyse de la tâche Fashion-MNIST a révélé que les modèles L1 et FR s'appuient sur des régions distinctes de l'espace de l'image de persistance. Les caractéristiques les plus importantes pour les modèles L1 étaient concentrées dans $H_0$ (composantes connexes), tandis que les modèles FR utilisaient plus équitablement les caractéristiques de $H_0$ et $H_1$ . Cela suggère que les diagrammes non réduits encodent des informations différentes, potentiellement utiles, qui sont écartées lors de la réduction complète.

Signification et affirmations

L'article conclut que les diagrammes de persistance non réduits sont des substituts efficaces aux diagrammes entièrement réduits dans les pipelines d'apprentissage automatique topologique.

Efficacité computationnelle : En évitant l'étape coûteuse de la réduction, les praticiens peuvent réaliser des réductions significatives de l'utilisation de la mémoire et du temps de calcul, permettant l'analyse de jeux de données actuellement intraitables pour les méthodes de PH standard.
Performance : Contrairement à l'hypothèse selon laquelle la réduction est nécessaire pour la qualité, les auteurs démontrent que l'information écartée par la réduction n'est souvent pas critique pour la performance du ML en aval et que les diagrammes non réduits peuvent même capturer des caractéristiques distinctes et bénéfiques.
Directions futures : Les auteurs notent que si les diagrammes non réduits font gagner du temps de calcul, leur vectorisation peut être plus lente en raison du plus grand nombre de points. Ils suggèrent que les travaux futurs devraient se concentrer sur la conception d'algorithmes capables de calculer les vectorisations directement à partir de matrices non réduites sans stocker explicitement toutes les paires, optimisant ainsi davantage le pipeline.

L'étude affirme modestement que ces résultats suggèrent un changement dans la manière dont les pipelines PH-ML sont construits, en privilégiant potentiellement l'efficacité computationnelle et la rétention de caractéristiques topologiques « brutes » plutôt que la stricte complétude mathématique des diagrammes entièrement réduits.