🤖 machine learning

Voronoi Histograms for Adaptive Vectorization of Expected Persistence Diagrams

Cet article propose une méthode de vectorisation basée sur l'histogramme de Voronoi pour les diagrammes de persistance attendus qui remplace les transformations lisses prédéfinies par un comptage adaptatif par partition, offrant une stabilité prouvée et des performances efficaces sur des ensembles de données réels pour les tâches de classification et de réduction de dimensionnalité.

Auteurs originaux : Kaifeng Zhang, Kai Ming Ting

Publié 2026-07-30

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Kaifeng Zhang, Kai Ming Ting

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 êtes un détective essayant de comprendre la forme d'un objet mystérieux, mais que vous ne pouvez le voir que comme un nuage de milliers de minuscules grains de poussière flottant dans l'espace. C'est le monde de l'Analyse de Données Topologiques (TDA). Au lieu de mesurer la longueur ou le poids d'un objet, la TDA demande : « Ce nuage possède-t-il un trou au milieu ? Est-ce un anneau ? Est-ce une sphère creuse ? » Pour répondre à cela, les mathématiciens utilisent un outil appelé Diagramme de Persistance. Considérez ce diagramme comme une carte où chaque point représente une caractéristique (comme un anneau ou un vide) qui est apparue au fur et à mesure que vous zoomiez lentement sur le nuage de poussière. La position du point vous indique quand la caractéristique est « née » et quand elle est « morte » à mesure que le zoom changeait.

Cependant, il y a un piège. Ces cartes sont désordonnées. Elles sont composées de points dispersés, et les ordinateurs détestent essayer d'apprendre à partir de points dispersés car ils ont besoin de listes de nombres ordonnées (des vecteurs) pour opérer leur magie. Pendant longtemps, les scientifiques ont essayé de transformer ces cartes de points en listes ordonnées en étalant les points avec un filtre doux et flou (comme un flou gaussien) ou en dessinant un paysage lisse par-dessus. C'est comme essayer de compter le nombre de personnes dans une pièce bondée en prenant une photo à longue exposition où tout le monde est un flou ; vous obtenez une image lisse, mais vous pourriez manquer le fait que deux personnes se tiennent juste à côté l'une de l'autre.

C'est là qu'entrent en scène les Diagrammes de Persistance Attendus (EPD). Lorsque le nuage de poussière est trop grand pour être analysé d'un seul coup, les scientifiques prennent de nombreux petits clichés (sous-échantillonnages) de celui-ci, réalisent une carte pour chacun, et les font tous la moyenne. Cette carte moyenne est l'EPD. C'est un résumé statistique de la forme, mais c'est toujours un nuage de points, pas une liste ordonnée. La grande question est : comment transformer ce nuage de points moyen en une liste de nombres qu'un ordinateur peut utiliser pour dire si un objet est un « chat » et un autre un « chien », sans perdre les détails importants ?

La Grande Idée de l'Article : Compter dans des Seaux Personnalisés

Cet article introduit une nouvelle façon ingénieuse de transformer ces nuages de points moyens désordonnés en listes de nombres ordonnées. Les auteurs, Kaifeng Zhang et Kai Ming Ting, proposent une méthode qu'ils appellent Histogrammes de Voronoï.

Au lieu d'étaler les points avec un filtre flou (comme le faisaient les anciennes méthodes), ils décident de construire des « seaux » ou des « bacs » personnalisés autour des points et de simplement compter combien de points tombent dans chaque seau. Imaginez que vous avez un sol géant couvert de billes éparpillées (vos points de données). Au lieu de peindre un gradient lisse sur le sol, vous déposez quelques billes « attractrices » spéciales (appelées codebook ou livre de codes) sur le sol. Ensuite, vous tracez des lignes sur le sol de sorte que chaque endroit du sol appartienne à l'attracteur le plus proche. Cela crée un patchwork de territoires appelés cellules de Voronoï.

La magie opère lors du comptage. Vous regardez votre nuage de billes de données et vous demandez : « Combien de billes sont dans le territoire de l'attracteur n°1 ? Combien dans l'attracteur n°2 ? » Vous notez ces comptes sous forme de liste de nombres. C'est votre vecteur !

L'article soutient que cette approche de « comptage dans des seaux personnalisés » est meilleure que les anciennes méthodes de « lissage flou » pour certains types de données. Voici ce qu'ils ont trouvé :

1. C'est une Carte Dépendante des Données
Contrairement aux anciennes méthodes qui utilisent une grille fixe (comme du papier millimétré) ou une courbe lisse fixe pour tout le monde, cette méthode construit ses seaux en fonction de l'endroit où se trouvent réellement les données. Si vos données sont regroupées dans un coin, les seaux rétrécissent pour s'adapter à ce coin. Si les données sont dispersées, les seaux s'élargissent. Cela rend la méthode « adaptative ». C'est comme avoir un tailleur qui mesure votre corps spécifique pour faire un costume, plutôt que d'acheter un costume « taille unique » qui pourrait être trop large ou trop serré.

2. C'est Stable (Pour l'essentiel)
Les auteurs ont fait des mathématiques pour prouver que si vous déplacez légèrement les points de données (comme en secouant légèrement la table), les comptes dans les seaux ne changent pas radicalement. Ils ont montré que la méthode est « stable », ce qui signifie que de petites erreurs dans les données ne provoqueront pas de variations folles dans la liste finale. Cependant, ils ont également trouvé un compromis : si vous utilisez trop de seaux (rendant la liste très longue), la méthode devient légèrement moins stable. C'est un équilibre entre avoir assez de détails et maintenir le système robuste.

3. Cela Fonctionne Très Bien pour les Changements « Grossiers »
L'article a testé cette méthode sur des ensembles de données réels, comme des structures de protéines et des pièces mécaniques. Ils ont découvert que lorsque la différence entre deux objets est un changement important et évident de la forme (comme un anneau se déplaçant d'un côté à l'autre de la carte), cette méthode de comptage est incroyablement précise. Elle capture très bien le mouvement de la masse globale.

4. Mais Ce N'est Pas une Solution Miracle
Les auteurs sont très prudents et ne prétendent pas que c'est la meilleure méthode pour tout. Ils montrent explicitement que si la différence entre deux objets est un minuscule mouvement subtil à l'intérieur d'un seul seau, cette méthode pourrait le manquer. Dans ces cas-là, les anciennes méthodes de « lissage flou » pourraient être meilleures car elles peuvent voir ces micro-déplacements. De plus, l'article note que bien que cette méthode soit rapide et fonctionne bien avec des classificateurs simples (comme les Forêts Aléatoires), elle ne bat pas toujours les réseaux neuronaux les plus complexes et puissants (comme PointNet) dans chaque test.

5. Le Choix du « Codebook » Importante
Les auteurs ont expérimenté la manière de choisir ces billes « attractrices » (le codebook). Ils ont trouvé que si vous les choisissez en fonction des caractéristiques les plus importantes des données (comme les anneaux les plus persistants), la méthode fonctionne encore mieux. Si vous les choisissez au hasard ou à partir d'un cadre fixe, c'est correct, mais pas aussi performant.

L'Essentiel à Retenir

Cet article suggère que pour de nombreux problèmes d'analyse de forme, nous n'avons pas besoin de lisser nos données en un paysage flou. Au lieu de cela, nous pouvons construire un patchwork personnalisé piloté par les données et simplement compter les points dans chaque patch. C'est une façon plus simple et plus directe de transformer des formes complexes en nombres que les ordinateurs peuvent comprendre.

Les auteurs démontrent que cette approche d'« Histogramme de Voronoï » est un sérieux concurrent aux méthodes existantes. Elle est particulièrement efficace pour repérer les changements structurels majeurs dans les formes et elle est efficace sur le plan computationnel. Cependant, ils admettent qu'il s'agit d'une représentation « avec perte » — ce qui signifie que certains détails infimes à l'intérieur des seaux sont abandonnés. Ainsi, bien qu'elle soit un nouvel outil puissant dans la boîte à outils du topologue, elle n'est pas un remplacement pour tous les autres outils. Elle est préférable lorsque vous voulez capturer l'histoire principale de la forme sans vous perdre dans le bruit.

Résumé Technique : Histogrammes de Voronoi pour la Vectorisation Adaptative des Diagrammes de Persistance Attendus

1. Énoncé du Problème

L'Analyse Topologique des Données (TDA) utilise l'Homologie Persistante (PH) pour capturer les caractéristiques topologiques des nuages de points, encodées sous forme de Diagrammes de Persistance (PD). Un PD représente les caractéristiques topologiques (cycles) comme des points $(b, d)$ dans un demi-plan ouvert $\Omega$ , où $b$ et $d$ dénotent respectivement les temps de naissance et de mort.

Un goulot d'étranglement important dans l'utilisation des PD est leur haute complexité computationnelle ; l'obtention d'un PD peut atteindre $O(m^3)$ ou même $O(|X|^9)$ pour les caractéristiques de dimension 1. Pour atténuer cela, le Diagramme de Persistance Attendu (EPD) a été développé. Un EPD est une distribution de caractéristiques topologiques dérivée en moyennant les PD de multiples sous-échantillonnages d'un nuage de points. Bien que les EPD réduisent les coûts temporels, les méthodes de vectorisation existantes pour les EPD (telles que les Images de Persistance, les Silhouettes de Persistance et les Paysages de Persistance) reposent sur des fonctions de transformation de points continues prédéfinies (par exemple, des noyaux gausiens ou des fonctions de paysage) et des grilles de discrétisation fixes. Ces méthodes introduisent des choix de conception concernant la lissité, la largeur de bande et la résolution de la grille, ce qui peut estomper les différences de masse locale ou accentuer des régions non optimales du plan $(naissance, mort)$.

Le présent article traite de la nécessité d'une méthode de vectorisation alternative qui évite les modèles explicites de transformation de points lissés et utilise plutôt un partitionnement adaptatif dépendant des données pour représenter la distribution de l'EPD.

2. Méthodologie : Représentation basée sur Voronoi (Vrep)

Les auteurs proposent Vrep, une méthode de vectorisation qui traite l'EPD empirique comme une distribution de caractéristiques topologiques et la représente à l'aide d'histogrammes basés sur des Diagrammes de Voronoi.

Mécanisme Central

Échantillonnage du Codebook : Au lieu d'une grille fixe, Vrep construit un ensemble de codebooks aléatoires $S$ . Chaque codebook $C = \{c_1, ..., c_k\}$ consiste en des points échantillonnés à partir du support de l'EPD (l'ensemble des caractéristiques topologiques).
Partition de Voronoi : Pour un codebook $C$ donné, le demi-plan ouvert $\Omega$ est partitionné en cellules de Voronoi $V(c_i)$ , où chaque cellule contient les points plus proches de $c_i$ que de n'importe quel autre $c_j$ .
Construction de l'Histogramme : La représentation $\Phi(\bar{\mu}, C)$ est définie comme le vecteur des masses normalisées de l'EPD $\bar{\mu}$ tombant dans chaque cellule de Voronoi :
$\Phi(\bar{\mu}, C) = [\bar{\mu}(V(c_1)), \bar{\mu}(V(c_2)), ..., \bar{\mu}(V(c_k))]$
Agrégation : Pour former la représentation finale $\hat{\Phi}(\bar{\mu})$ , la méthode concatène les histogrammes générés à partir de plusieurs codebooks échantillonnés à partir du jeu de données.
Variante Sensible à la Diagonale (Vrepd) : Une variante spécifique, Vrepd, inclut une cellule de Voronoi centrée sur la diagonale $\partial\Omega$ (où $b=d$ ). Cela est crucial pour séparer le bruit (caractéristiques proches de la diagonale) des caractéristiques topologiques significatives.

Stratégies d'Échantillonnage du Codebook

L'article évalue trois stratégies pour l'échantillonnage des points au sein d'un codebook :

Par Défaut : Échantillonnage uniforme du support de l'EPD.
Pondéré par la Persistance : Échantillonnage pondéré par la persistance ( $d-b$ ), privilégiant les caractéristiques significatives.
Uniforme : Échantillonnage à partir d'un rectangle fixe au-dessus de la diagonale (indépendant de l'EPD).

Normalisation

La méthode normalise l'EPD pour obtenir une norme $l_1$ unitaire ( $\bar{\mu} \leftarrow \bar{\mu}/\bar{\mu}(\Omega)$ ). Cela traite l'EPD comme une distribution de probabilité, garantissant que tous les EPD ont la même masse, ce qui permet l'utilisation directe de la distance de Wasserstein pour l'analyse de stabilité et la mesure de dissimilarité, évitant ainsi le besoin de métriques de Transport Partiel Optimal.

3. Contributions Théoriques

L'article établit des garanties théoriques concernant la stabilité et la capacité de représentation de Vrep sous des conditions spécifiques :

Bornes de Stabilité : Les auteurs prouvent que Vrep est stable sous des perturbations de l'EPD. Plus précisément, si l'EPD subit une $\Delta$ -perturbation (petit mouvement des masses de Dirac), le changement dans la représentation Vrep est lipschitzien par rapport à $\Delta$ . La borne d'erreur dépend de la taille du codebook $k$ et des propriétés du jeu de données.
Bornes liées à Wasserstein : L'article fournit une borne inférieure conditionnelle reliant la distance $l_1$ entre deux vecteurs Vrep à la distance de Wasserstein ( $W_1$ ) entre les EPD sous-jacents.
$\|\Phi(\bar{\mu}, C) - \Phi(\bar{\nu}, C)\|_1 \geq \frac{W_1(\bar{\mu}, \bar{\nu}) - \text{erreurs d'approximation}}{d_{max}(C)}$
Ce résultat clarifie que Vrep préserve efficacement les variations d'échelle de Wasserstein lorsque le codebook est "bien résolu" (c'est-à-dire que l'erreur d'approximation est petite par rapport à la séparation des distributions). Il ne s'agit pas d'une garantie de préservation monotone générale, mais d'un énoncé de cohérence conditionnelle.

4. Résultats Expérimentaux

Les auteurs ont évalué Vrep et Vrepd sur des tâches de classification de nuages de points supervisées et de réduction de dimensionnalité non supervisée, en comparant ces méthodes aux méthodes standards : l'Image de Persistance (PI), les Silhouettes de Persistance (PS), le Paysage de Persistance (PL) et le réseau de bout en bout PointNet.

Performance de Classification

Jeux de Données : Les expériences ont été menées sur divers jeux de données incluant des structures de protéines, des composants mécaniques CAO et des données de séries temporelles (transformées en nuages de points via l'encapsulation par retard temporel).
Résultats : Vrep et Vrepd ont systématiquement obtenu des précisions de classification plus élevées ou comparables (en utilisant un classifieur Random Forest) à PI, PS et PL sur la plupart des jeux de données sensibles à la topologie.
- Sur le jeu de données Protéine, Vrep a atteint 98,5 % de précision (contre 95,5 % pour PI).
- Sur les jeux de données CAO, Vrep et Vrepd ont surpassé les autres méthodes non supervisées, bien que PI ait montré des résultats compétitifs dans certains contextes de bruit.
Sensibilité du Codebook : La stratégie d'échantillonnage de codebook pondérée par la persistance a souvent donné les meilleurs résultats, particulièrement dans les environnements bruités, car elle concentre la représentation sur les caractéristiques topologiques significatives.

Stabilité et Scalabilité

Stabilité de la Perturbation : Des expériences sur un jeu de données de système dynamique 3D ont montré que Vrep est stable sous des perturbations de bruit gaussien. Curieusement, Vrepd (avec la cellule de la diagonale) a démontré une stabilité légèrement supérieure à Vrep, probablement en raison d'une meilleure séparation du bruit près de la diagonale.
Complexité Temporelle :
- Vrep a une complexité temporelle de $O(m^2tk)$ pour un jeu de données de taille $m$ , où $t$ est le nombre de codebooks et $k$ la taille du codebook. Elle est quadratique par rapport à la taille du jeu de données.
- Cependant, Vrep est plus rapide que PL et PS en temps d'exécution réel et passe mieux à l'échelle avec le nombre de PD échantillonnés ( $n$ ) car elle sous-échantillonne le support de l'EPD à une taille fixe, alors que PI/PS/PL doivent traiter chaque PD échantillonné individuellement.
- Bien que PointNet (supervisé) ait atteint une haute précision, Vrep offre une alternative compétitive pour les tâches non supervisées (comme la réduction de dimensionnalité) où PointNet ne peut être appliqué.

Réduction de Dimensionnalité Non Supervisée

Dans une tâche de visualisation t-SNE sur un jeu de données de système dynamique, Vrep a produit des clusters avec des indices Calinski-Harabasz (CH) plus élevés (1751) que PI (569) et PL (1655), indiquant une meilleure séparation de clusters.

5. Signification et Revendications

L'article positionne Vrep comme une représentation complémentaire plutôt que comme un remplacement universel des méthodes existantes.

Adaptatif vs Lisse : La contribution primaire est le passage d'approximations fonctionnelles lissées basées sur des noyaux à un comptage adaptatif dépendant des données. Vrep agrège la masse sur des cellules définies par les données elles-mêmes, ce qui la rend potentiellement plus fidèle à l'allocation de la masse empirique de l'EPD.
Compromis : Les auteurs reconnaissent explicitement le compromis : Vrep résume efficacement l'allocation de masse grossière mais est intrinsèquement perteuse concernant la géométrie fine à l'intérieur d'une cellule de Voronoi. Par conséquent, les méthodes lissées (comme PI ou les méthodes à noyaux) peuvent surpasser Vrep lorsque la variation topologique pertinente implique des changements de forme ou des déplacements locaux fins au sein d'une cellule.
Utilité Non Supervisée : Une signification clé est l'applicabilité de la méthode à l'apprentissage non supervisé. Contrairement aux approches d'apprentissage profond supervisées (ex: PointNet, PersLay), Vrep ne nécessite pas d'étiquettes pour l'extraction de caractéristiques, ce qui la rend adaptée à la réduction de dimensionnalité et au clustering.
Revendications Modestes : Les auteurs ne prétendent pas que Vrep domine toutes les vectorisations. Ils notent que les méthodes à noyaux (PWGK, SWK) peuvent surpasser Vrep sur des jeux de données spécifiques (ex: CAO) mais à un coût computationnel nettement plus élevé. L'article conclut que Vrep est une alternative adaptative compétitive qui offre une mise à l'échelle favorable avec le nombre de PD échantillonnés et fournit un biais d'approximation distinct adapté à la classification sensible à la topologie.