When One Point Is Not Enough: Addressing Ambiguous Instances in Dimensionality Reduction by Splitting

Résumé technique : Traitement des instances ambiguës en réduction de dimension par scission

Définition du problème
La réduction de dimension (DR) est un outil fondamental pour visualiser des données de haute dimension, mais c'est un processus intrinsèquement destructeur. Bien que la littérature existante ait répertorié diverses distorsions, telles que le déchirement des variétés, cet article identifie une source d'artefacts visuels jusque-là négligée : les instances ambiguës. Il s'agit de points de données hautement similaires à plusieurs voisinages mutuellement dissemblables dans l'espace de haute dimension.

Les méthodes de DR standard mappent chaque instance de données vers un seul point dans l'espace visuel. Par conséquent, une instance ambiguë ne peut pas représenter fidèlement son appartenance à plusieurs voisinages distincts simultanément. Elle est contrainte à une seule position, ce qui entraîne un mappage partiel du voisinage. Dans cet état, l'instance semble appartenir à un seul voisinage (ou aucun), masquant sa véritable relation avec d'autres groupes dissemblables. Cet artefact est particulièrement problématique pour les analyses au niveau des instances, telles que l'IA explicable (XAI) ou la biologie des cellules uniques, où la compréhension de la structure précise du voisinage est cruciale. Les métriques existantes, telles que la fiabilité et la continuité, échouent à distinguer le mappage partiel du voisinage d'autres distorsions car elles opèrent sur le mappage final sans accès à l'ambiguïté sous-jacente des données.

Méthodologie
Les auteurs proposent une approche basée sur les graphes pour identifier et résoudre ces ambiguïtés en « scindant » les instances ambiguës en plusieurs points, chacun étant placé au sein de son voisinage respectif. La méthodologie suit le cadre de DR en deux phases (relation et mappage) introduit par Paulovich et al. :

1. Construction et épuration du graphe :

   • Les relations de haute dimension sont modélisées comme un graphe pondéré non orienté $G$.
   • Pour révéler des structures de voisinage significatives et éliminer les arêtes redondantes causées par une proximité accidentelle, les auteurs appliquent une épuration spectrale en utilisant l'algorithme de Spielman-Srivastava. Cela produit un graphe réduit $\bar{G}$ qui préserve les propriétés structurelles et algébriques de l'original tout en éliminant les connexions faibles.

2. Identification des instances ambiguës :

   • L'ambiguïté est définie topologiquement. Les auteurs adaptent le concept de points d'articulation locaux (LAP). Un sommet est considéré comme un LAP si sa suppression augmente le nombre de composantes connexes au sein d'un voisinage induit local de $r$ étapes.
   • Une instance est jugée ambiguë si elle est un LAP dans le graphe épuré $\bar{G}$. Cela indique que l'instance connecte des voisinages disjoints qui seraient autrement séparés.
   • Le lemme 3.1 est utilisé pour optimiser le calcul : si un sommet n'est pas un LAP à un certain rayon $r$, il ne peut pas être un LAP à un rayon plus grand $r' > r$.

3. Scission des sommets et règles de décision :

   • Une fois un sommet ambigu $v_i$ identifié, il est scindé en $K$ copies, où $K$ correspond au nombre de composantes connexes restantes après la suppression de $v_i$ de son voisinage local.
   • Règles de décision : Toutes les scissions potentielles ne sont pas exécutées. L'approche filtre :
     • Les connexions LAP-LAP : Si une arête relie deux voisinages et que les deux extrémités sont des LAP, la scission est supprimée pour éviter de créer un isolement artificiel.
     • Les connexions faibles : Un seuil défini par l'utilisateur $\tau_w$ (rapport de la force de connexion à la composante la plus forte) filtre les scissions où la connexion à un voisinage est trop faible pour être significative. Cela empêche la création de points visuellement isolés en raison de forces d'attraction insuffisantes.

4. Mappage et visualisation :

   • Le graphe modifié, contenant les sommets scindés, est projeté dans l'espace visuel en utilisant des techniques de DR locales standard (par exemple, UMAP ou ForceAtlas2).
   • Encodage visuel : Les instances scindées sont rendues sous forme de marqueurs distincts (par exemple, des croix) reliés par des lignes pointillées à leur position d'origine ou entre elles, permettant aux analystes de retracer les appartenances multiples au voisinage d'un seul point de données.

Contributions clés

• Définition du mappage partiel du voisinage : L'article introduit et définit formellement cet artefact spécifique résultant des instances ambiguës, le distinguant des distorsions générales de la DR.
• Détection par théorie des graphes : Il présente une méthode pour identifier les instances ambiguës en utilisant les points d'articulation locaux sur des graphes de voisinage épurés.
• Mécanisme de scission : Les auteurs proposent une approche concrète, de complexité quasi linéaire, pour scinder les instances ambiguës, en les répliquant dans la projection afin de refléter les appartenances multiples au voisinage.
• Validation empirique : L'approche est démontrée sur divers ensembles de données (SVHN, MNIST, corpus textuels et séquençage d'ARN de cellules uniques), montrant qu'elle révèle des appartenances au voisinage cachées non visibles dans les projections standard.

Résultats

• Insights qualitatifs : Dans l'ensemble de données SVHN, un chiffre '1' mal classifié (prédit comme '7') était montré dans UMAP standard comme appartenant uniquement au voisinage '7'. L'approche proposée a scindé l'instance, révélant sa similarité simultanée avec le voisinage '1', expliquant ainsi l'ambiguïté de l'erreur du classifieur. De même, dans les données textuelles, un article sur les « Modèles assistés par ILP pour la toxicologie » s'est avéré appartenir à la fois aux clusters ILP et au Raisonnement Basé sur les Cas (CBR), une dualité obscurcie dans les projections standard.
• Analyse quantitative :
  • Impact de l'épuration : Des expériences mesurant les $k$ plus proches voisins ($k$NN) préservés ont montré que l'épuration spectrale conserve des structures de voisinage locales comparables au graphe original (des ratios proches de 1 pour la plupart des ensembles de données), bien qu'une certaine variance ait été observée dans les données de cellules uniques à haute dimension intrinsèque.
  • Limites des métriques : Les métriques standard (fiabilité et continuité) se sont révélées inefficaces pour identifier les instances ambiguës, car ces points sont distribués de manière similaire aux points non ambigus dans les distributions de métriques.
  • Sensibilité aux paramètres : L'augmentation du nombre de voisins dans le graphe initial a généralement réduit le nombre de scissions détectées, car une connectivité accrue relie des voisinages qui autrement apparaîtraient disjoints.

Signification et affirmations
L'article soutient que la reconnaissance de l'ambiguïté est essentielle pour interpréter les structures locales fines en DR. Les auteurs affirment que ne pas tenir compte des instances ambiguës peut conduire à des interprétations incomplètes ou incorrectes, en particulier dans des domaines comme la XAI et la biologie où le contexte au niveau de l'instance est vital. En scindant ces instances, la méthode fournit une représentation plus fidèle de la topologie de haute dimension des données, révélant des « appartenances au voisinage précédemment cachées ». Le travail suggère que les métriques actuelles de qualité de la DR sont insuffisantes pour ce type spécifique d'artefact et que les futurs cadres d'évaluation doivent prendre en compte l'ambiguïté pilotée par les données plutôt que simplement l'instabilité induite par le mappage.