📊 statistics

Prototype Selection Using Topological Data Analysis

Cet article introduit deux méthodes de sélection de prototypes basées sur l'analyse de données topologiques, TPS et BoundaryTPS, qui exploitent des structures de persistance multi-échelles pour préserver efficacement les frontières de décision et les proportions de classes, tout en démontrant une stabilité supérieure et des caractéristiques de fonctionnement distinctes par rapport aux bases classiques existantes.

Auteurs originaux : Jordan Eckert, Elvan Ceyhan, Henry Schenck

Publié 2026-06-02

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jordan Eckert, Elvan Ceyhan, Henry Schenck

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 robot à reconnaître différents types de fruits. Vous avez une boîte énorme contenant 10 000 pommes, oranges et bananes. Si vous montrez au robot chaque morceau de fruit, cela prendra une éternité pour apprendre, et il pourrait être confus par quelques fruits meurtris ou de forme étrange (le bruit).

La Sélection de Prototypes est l'art de choisir une petite poignée "représsentative" et parfaite de fruits parmi cette boîte géante pour enseigner au robot. Le but est de rendre le robot intelligent tout en étant rapide.

Pendant longtemps, les scientifiques ont utilisé différentes méthodes pour choisir cette poignée :

Le "Nettoyeur" : jette les fruits meurtris.
Le "Groupeur" (Clusterer) : choisit le fruit d'apparence moyenne au sein d'un groupe.
L' "Optimisateur" : cherche les quelques fruits mathématiquement parfaits.

Mais ces méthodes regardent le fruit comme de simples points dans l'espace. Elles ne comprennent pas vraiment la forme du problème — spécifiquement, là où les pommes s'arrêtent et où les oranges commencent (la "frontière de décision").

La Nouvelle Idée : L'Analyse de Données Topologiques (TDA)

Ce document présente deux nouvelles méthodes, TPS et BoundaryTPS, qui utilisent une branche des mathématiques appelée Analyse de Données Topologiques.

Voyez la TDA non pas comme l'examen de fruits individuels, mais comme l'observation de la forme de l'ensemble du tas.

Si vous avez un tas de fruits avec un trou au milieu (comme une forme de donut), la TDA voit la "boucle" ou le "trou".
Si les fruits forment juste une masse solide, la TDA voit une "masse solide".

Les auteurs soutiennent que la partie la plus importante de l'apprentissage est la frontière — l'endroit complexe et désordonné où une classe de fruits se transforme en une autre. Leurs nouvelles méthodes sont conçues pour préserver spécifiquement la forme de ces bords.

Les Deux Nouvelles Méthodes

1. BoundaryTPS (Le "Gardien de la Frontière")

Comment ça marche : Imaginez que vous gardiez une frontière entre deux pays. Vous voulez garder les personnes vivant juste sur la ligne de frontière car elles connaissent le mieux le terrain. Vous ne vous souciez pas autant des personnes vivant profondément au milieu du pays.
L'astuce : Cette méthode attribue un "poids" à chaque point de donnée. Les points proches de la frontière de décision reçoivent un "poids faible" (ils entrent plus tôt dans le processus de sélection). Les points situés profondément à l'intérieur d'une classe reçoivent un "poids élevé" (ils sont retardés).
Le résultat : Elle filtre les données afin que la poignée finale de prototypes soit regroupée étroitement autour des frontières de décision, préservant ainsi la forme complexe du bord.

2. TPS (L' "Éclaireur en Deux Étapes")

Comment ça marche : Cette méthode adop素 une approche en deux étapes.
- Étape 1 : Elle regarde la frontière entre les classes (comme le mélange de pommes et d'oranges) pour trouver les points de l' "edge" (le bord).
- Étape 2 : Elle regarde les survivants de l'étape 1 et sélectionne les points "typiques" qui représentent le milieu des tas de fruits.
Le résultat : Elle offre une équipe équilibrée : des experts sur les bords complexes, et des experts sur l'intérieur typique et sûr.

Qu'ont-ils découvert ?

Les auteurs ont testé ces nouvelles méthodes contre sept anciennes méthodes classiques en utilisant 15 jeux de données réels (comme des dossiers médicaux, des images satellites et des analyses chimiques de vin). Voici ce qui s'est passé :

Préservation de la Forme (Le Test de la "Carte") :
- Si vous prenez la carte d'une ville et que vous supprimez la plupart des rues, vous voulez vous assurer que vous pouvez toujours voir les principaux quartiers et boucles.
- BoundaryTPS a été la meilleure pour conserver les "boucles" et les "trous" des données originales. Elle a préservé la forme topologique mieux que n'importe quelle autre méthode testée.
- TPS arrive juste après.
- Les anciennes méthodes ont souvent aplati ces formes, perdant la structure complexe des données.
Stabilité (Le Test de la "Répétabilité") :
- Si vous mélangez légèrement les données (comme distribuer un jeu de cartes différemment), choisirez-vous la même poignée de prototypes ?
- TPS est la plus stable. Elle choisit presque toujours les mêmes personnes, même lorsque les données changent légèrement.
- Beaucoup d'anciennes méthodes étaient "instables", choisissant des ensembles totalement différents juste parce que les données avaient été légèrement mélangées.
Performance (Le Test du "Score de Test") :
- Ces nouvelles méthodes ont-elles rendu le robot plus intelligent ?
- Surprise : Elles étaient compétitives, mais pas les vainqueurs absolus. Les anciennes méthodes (comme K-Means ou SPOTGreedy) obtenaient souvent des scores de test légèrement plus élevés.
- Cependant, les nouvelles méthodes étaient très bonnes pour gérer les données déséquilibrées (lorsqu'une classe de fruits est rare). Elles n'ont pas accidentellement jeté les fruits rares.
Vitesse :
- Les deux nouvelles méthodes sont rapides. Elles passent bien à l'échelle, ce qui signifie qu'elles ne deviennent pas exponentiellement plus lentes à mesure que le jeu de données s'agrandit.

L'Essentiel

Ce document ne prétend pas que ces nouvelles méthodes vous donneront toujours le score de test le plus élevé. Au contraire, il affirme qu'elles offrent une valeur différente :

Elles sont plus stables (vous obtenez le même résultat à chaque fois).
Elles sont meilleures pour préserver la forme des frontières de vos données.
Elles gèrent naturellement les données déséquilibrées sans avoir besoin de trucs spéciaux.

Si vous avez besoin d'une méthode de réduction de données qui est fiable, préserve la géométrie complexe de vos données et ne se laisse pas déstabiliser par de petits changements dans l'entrée, ces méthodes topologiques sont un nouvel outil puissant dans votre boîte à outils.

Résumé Technique : Sélection de Prototypes par l'Analyse de Données Topologiques

Énoncé du Problème
Les pipelines de classification modernes sont souvent confrontés à des goulots d'étranglement où la taille de l'ensemble d'entraînement, plutôt que le coût d'une prédiction unique, domine le temps d'inférence. Bien que les modèles paramétriques (par exemple, SVM, Forêts Aléatoires) déplacent la charge vers le temps d'entraînement, ils dépendent toujours du nombre d'instances d'entraînement. La sélection de prototypes répond à cela en compressant l'ensemble d'entraînement en un sous-ensemble restreint et représentatif. Les taxonomies existantes de la sélection de prototypes — incluant les familles de condensation, d'édition, hybrides, basées sur la compétence, basées sur l'optimisation et basées sur le partitionnement (clustering) — opèrent sans une représentation explicite de la structure topologique des données. Par conséquent, la géométrie des frontières de décision entre les classes, qui peut présenter une structure complexe à travers plusieurs échelles spatiales, n'est capturée que de manière implicite. Cet article comble la lacune consistant à utiliser la structure topologique multi-échelle des données comme un critère direct de sélection de prototypes.

Méthodologie
Les auteurs introduisent deux variantes d'un Sélecteur de Prototypes Topologiques (TPS - Topological Prototype Selector) qui utilisent l'homologie persistante, un outil central de l'Analyse de Données Topologiques (TDA), pour identifier et conserver les prototypes. Les deux méthodes reposent sur la filtration de Rips, mais diffèrent dans leur manière d'encoder l'information de frontière :

Sélecteur de Prototypes Topologiques Sensible aux Frontières (BoundaryTPS) :
- Mécanisme : Il s'agit d'une méthode à étape unique utilisant une filtration de Rips à poids de sommets. Elle assigne des poids aux points de la classe cible en fonction de leur proximité avec les classes non cibles (spécifiquement, la somme des distances aux $k$ plus proches voisins non cibles).
- Processus : Les points proches de la frontière de décision reçoivent des poids faibles et entrent tôt dans la filtration, tandis que les points intérieurs reçoivent des poids élevés et sont retardés. Cela garantit que la topologie de la région de frontière est résolue à des échelles plus fines.
- Sélection : Les prototypes sont sélectionnés en identifiant les caractéristiques de persistance à un quantile spécifié de la distribution de durée de vie. Un paramètre de tolérance $\tau$ permet de sélectionner une fenêtre de caractéristiques autour du quantile cible pour améliorer la robustance.
Sélecteur de Prototypes Topologiques (TPS) :
- Mécanisme : Il s'agit d'une méthode en deux étapes qui encode l'information de frontière de manière implicite en construisant un nuage de points mixte contenant à la fois des observations cibles et non cibles.
- Étape 1 (Voisinage de la Frontière) : Une filtration de Rips standard est construite sur le nuage mixte pour capturer la structure topologique entre les classes. Les caractéristiques sont sélectionnées sur la base d'un quantile de la distribution de durée de vie, et les points de la classe cible survivants sont conservés.
- Étape 2 (Intérieur) : Une seconde filtration de Rips est construite sur les survivants de l'étape 1 pour capturer la topologie intra-classe. Les caractéristiques sont sélectionnées sur la base de la durée de vie moyenne pour conserver les échantillons typiques de l'intérieur.
- Résultat : L'ensemble final combine les points pertinents de la frontière de l'étape 1 avec les points de support intérieur de l'étape 2.

Contributions Clés

Nouveau Critère : L'article introduit l'homologie persistante comme un critère de sélection de prototypes, une capacité qui n'avait pas été utilisée auparavant dans ce domaine.
Double Réalisation : Il présente le TPS et le BoundaryTPS, démontrant que l'encodage de l'information de frontière via des filtrations de classes mixtes (TPS) par rapport aux poids de sommets (BoundaryTPS) conduit à des spécialisations empiriquement différentes.
Évaluation Comparative Exhaustive : Les deux méthodes sont évaluées par rapport à sept bases classiques (CNN, CNN+ENN, DROP3, ICF, IB3, KMeans, SPOTGreedy) sur quinze jeux de données réels et six classifieurs en aval sous validation croisée imbriquée.
Préservation Topologique : L'étude démontre que les méthodes topologiques préservent la structure du diagramme de persistance $H_1$ de manière nettement supérieure aux bases basées sur la densité ou sur des décisions en chaîne.
Stabilité : Les deux méthodes présentent une plus grande stabilité de sélection (mesurée par la similitude de Jaccard d'un pli à l'autre) que n'importe quel sélecteur à décision en chaîne testé.
Déséquilibre des Classes : Les méthodes héritent des proportions de classes de l'ensemble source sans nécessiter de mécanisme sensible aux étiquettes.

Résultats

Fidélité Topologique : BoundaryTPS obtient le rang moyen de Friedman le plus bas (2,00) sur la distance de Wasserstein-1 de $H_1$ , surpassant de manière significative cinq des sept bases. Le TPS se classe troisième (3,60). Les deux méthodes se regroupent au sommet du spectre de performance pour la préservation des structures de boucles ( $H_1$ ), alors que les méthodes classiques aplatissent souvent ces caractéristiques.
Stabilité de Sélection : Le TPS atteint la similitude de Jaccard moyenne la plus élevée (0,225) entre les plis, suivi par BoundaryTPS (0,202). Les deux sont nettement plus stables que les méthodes à décision en chaîne comme CNN+ENN (0,057) et DROP3 (0,080).
Performance de Classification : Sur la Moyenne Géométrique (G-Mean) agrégée, les méthodes topologiques sont compétitives mais ne sont pas en tête. SPOTGreedy et KMeans atteignent la G-Mean agrégée la plus élevée (0,84). Le TPS et le BoundaryTPS atteignent respectivement 0,79 et 0,76. L'article note que bien qu'ils ne dominent pas la précision de classification brute, ils offrent un point de fonctionnement distinct dans l'espace de conception, particulièrement concernant la préservation structurelle et la stabilité.
Scalabilité : Empiriquement, les deux méthodes évoluent de manière sous-quadratique par rapport à la taille de l'échantillon.

Signification et Revendications
L'article affirme que la principale importance de ce travail réside dans le passage du paradigme de la sélection de prototypes d'heuristiques purement géométriques ou statistiques vers un cadre fondé sur des invariants topologiques multi-échelles. Les auteurs soutiennent que si les méthodes existantes supposent implicitement un principe de proximité de frontière, elles échouent à résoudre la structure complexe et multi-échelle des frontières de décision. En utilisant explicitement l'homologie persistante, les méthodes proposées offrent un moyen rigoureux de conserver les points qui définissent la "forme" topologique des données, en particulier les boucles et les frontières qui sont souvent perdues dans la réduction basée sur la densité.

Les auteurs caractérisent modestement les résultats : les méthodes topologiques ne surpassent pas universellement les bases existantes en termes de précision de classification en aval (G-Mean), mais elles occupent une région unique et précieuse de l'espace de conception en offrant une préservation topologique et une stabilité de sélection supérieures. Le travail suggère que pour les applications où l'intégrité structurelle de la frontière de décision ou la reproductibilité du processus de sélection est primordiale, les critères topologiques offrent une alternative distincte et efficace aux approches classiques.