Optimizing Multidimensional Scaling in Gini Metric Spaces

Résumé technique : Optimisation de l'Analyse des Correspondances Multiples dans les espaces métriques de Gini

Énoncé du problème
L'Analyse des Correspondances Multiples (MDS) est une technique standard de réduction de dimensionnalité, visant à représenter des données de haute dimension dans un espace géométrique de faible dimension (généralement 2D ou 3D) de telle sorte que les distances par paires dans l'embedding approximent les dissimilarités originales. Cependant, la MDS classique repose sur des distances euclidiennes, qui sont hautement sensibles au bruit, aux valeurs aberrantes et aux distributions à queue lourde. Dans les applications réelles où les données peuvent être contaminées ou où les structures latentes sont obscurcies par des valeurs extrêmes, la MDS euclidienne échoue souvent à préserver la géométrie sous-jacente réelle. De plus, les implémentations standards (par exemple, dans sklearn) peuvent être computationnellement inefficaces pour les grands ensembles de données, et les variantes robustes de MDS existantes manquent souvent d'un mécanisme ajustable pour s'adapter aux distributions de données spécifiques.

Méthodologie
L'article propose le cadre de l'Analyse des Correspondances Multiples de Gini (Gini MDS), qui étend la MDS classique en remplaçant la métrique euclidienne par une Pseudo-distance de Gini Généralisée.

1. Pseudo-distance de Gini Généralisée ($D_{G,\nu}$) :

   • Contrairement aux métriques de Gini standards qui reposent uniquement sur les rangs ou les valeurs, cette pseudo-distance intègre les deux. Elle est définie sur la base du concept de norme $p$ de Minkowski, mais adaptée pour inclure l'information de rang.
   • L'innovation centrale est l'introduction d'un hyperparamètre ajustable, $\nu$ (où $\nu > 1$). Ce paramètre contrôle le poids des queues de la distribution :
     • $\nu = 2$ correspond à la minimisation de l'indice de Gini des résidus (similaire à la régression médiane).
     • $\nu \in (1, 2)$ accorde plus de poids à la partie supérieure de la distribution.
     • $\nu > 2$ accorde plus de poids à la partie inférieure.
   • La distance est symétrisée pour garantir qu'elle satisfasse les propriétés d'une pseudo-distance (symétrie, non-négativité, inégalité triangulaire), bien qu'il soit noté que la propriété de « nullité » s'applique également aux distributions égalitaires (où $x = c\mathbf{1}$) ainsi qu'aux points identiques.
   • La structure repose sur les écarts de rang et les écarts de valeur, ce qui la rend intrinsèquement robuste aux valeurs aberrantes.

2. Algorithme d'optimisation :

   • Le cadre emploie une approche de minimisation du stress (Stress de Kruskal) pour trouver l'espace latent optimal.
   • L'Algorithme 1 itère sur une plage de valeurs de $\nu$ (par exemple, de 1,1 à 5). Pour chaque $\nu$, il calcule la matrice de pseudo-distance de Gini, effectue une MDS pour générer un embedding, et calcule le score de stress.
   • Le $\nu^*$ optimal est sélectionné comme celui qui minimise le stress moyen à travers les plis de validation croisée.
   • L'implémentation utilise PyTorch avec des opérations basées sur les tenseurs pour tirer parti de l'accélération GPU, offrant des améliorations de vitesse significatives par rapport aux bibliothèques standards basées sur CPU.

Contributions clés

1. Métrique novatrice : Introduction d'une pseudo-distance de Gini combinant valeurs et rangs avec un hyperparamètre ajustable $\nu$, permettant une exploration flexible des configurations latentes.
2. Robustesse : Démonstration que la pseudo-distance de Gini est robuste au bruit et aux valeurs aberrantes en raison de sa dépendance aux différences de rang, qui atténuent l'impact des valeurs extrêmes.
3. Cadre optimisé : Un algorithme complet pour la « Gini MDS optimisée » qui sélectionne automatiquement le meilleur hyperparamètre pour ajuster les dissimilarités observées, surpassant les approches euclidiennes statiques.
4. Implémentation efficace : Une implémentation basée sur les tenseurs et accélérée par GPU dans PyTorch qui réduit considérablement le temps de calcul par rapport à la MDS standard de sklearn.
5. Évaluation complète : Expériences extensives sur 16 ensembles de données UCI (avec et sans valeurs aberrantes), données d'images MNIST (avec bruit gaussien), et simulations sur des distributions à queue lourde.

Résultats expérimentaux

• Ensembles de données UCI (Contamination par valeurs aberrantes) :
  • Sur 16 ensembles de données avec 2 % et 5 % de contamination, la Gini MDS a constamment surpassé la MDS euclidienne et trois variantes euclidiennes optimisées (Huber, Sammon, SMACOF) en termes de Crédibilité (préservation de la structure locale) et de métriques de Plus Proche Voisin.
  • Bien que les méthodes euclidiennes aient parfois obtenu des scores de Silhouette plus élevés (regroupement global) sur des données propres, la Gini MDS a démontré des performances supérieures dans la préservation des voisinages locaux lorsque les données étaient contaminées.
• Classification MNIST (Bruit) :
  • Dans une tâche de classification distinguant les chiffres 5 et 6 avec du bruit gaussien ajouté, la Gini MDS a surpassé la MDS euclidienne lors de l'utilisation d'un seul composant d'embedding.
  • Les résultats suggèrent que la Gini MDS possède une plus grande « puissance de compression », capturant plus d'informations pertinentes dans le premier composant dans des conditions bruyantes.
• Simulations à queue lourde :
  • Comparée à des méthodes non linéaires (t-SNE, Isomap, UMAP) sur des distributions à queue lourde, la Gini MDS a obtenu les corrélations de Pearson et de Spearman les plus élevées entre les matrices de distance originales et embarquées.
  • Cela indique que la Gini MDS est particulièrement efficace pour préserver la structure géométrique globale (relations de distances par paires) des données à queue lourde, tandis que d'autres méthodes se concentraient davantage sur la préservation du voisinage local.
• Performance :
  • L'implémentation PyTorch était significativement plus rapide que sklearn (par exemple, 9 secondes contre 46 secondes pour l'ensemble de données Banknote avec 1 372 instances).

Signification et affirmations
L'article affirme que la Gini MDS fournit une alternative robuste à la MDS classique, en particulier pour les applications réelles où les données sont bruyantes ou contiennent des valeurs aberrantes. En tirant parti des propriétés des statistiques de Gini (intégration du rang et de la valeur) et en optimisant l'hyperparamètre $\nu$, la méthode offre :

• Robustesse accrue : Gestion supérieure des valeurs aberrantes et des distributions à queue lourde par rapport aux métriques euclidiennes.
• Préservation structurelle : La capacité de maintenir à la fois la structure locale (via la crédibilité) et les relations géométriques globales (via la corrélation des distances) dans l'espace d'embedding.
• Efficacité pratique : Une implémentation évolutive, prête pour GPU, qui rend la réduction de dimensionnalité robuste réalisable pour des ensembles de données plus volumineux.

Les auteurs concluent que, bien que la MDS euclidienne reste efficace pour des données propres, le cadre Gini MDS est un choix supérieur pour les scénarios impliquant une contamination des données, offrant un outil flexible et computationnellement efficace pour la découverte de structures latentes.