How smoothing the affinity matrix affects neighborhood preservation in t-SNE

Résumé technique : Comment le lissage de la matrice d'affinité affecte la préservation du voisinage dans t-SNE

Énoncé du problème
L'algorithme t-Distributed Stochastic Neighbor Embedding (t-SNE) est une technique de réduction de dimensionnalité largement utilisée, connue pour sa capacité à préserver les structures de voisinage locales. Cependant, malgré sa popularité, les plongements (embeddings) de t-SNE présentent souvent des scores de préservation de voisinage absolus faibles, et les erreurs sont fréquemment réparties de manière inégale. Alors que de nombreuses recherches se sont concentrées sur l'amélioration de la préservation de la structure globale de t-SNE ou sur l'optimisation de la procédure d'optimisation (par exemple, l'initialisation, les taux d'apprentissage), il y a eu peu d'investigations explicites pour savoir si la préservation de la structure locale de t-SNE peut être améliorée en modifiant la matrice d'affinité de haute dimension elle-même.

Les auteurs observent que dans le t-SNE standard, les distributions de probabilités conditionnelles (lignes d'affinité) sont souvent très « tranchantes » (sharp), ce qui signifie que quelques plus proches voisins dominent la masse de probabilité. De plus, la netteté de ces distributions varie selon les points de données. L'article étudie comment la « netteté » de ces distributions d'affinité influence la préservation du voisinage à différentes échelles et si la modification de cette netteté peut produire de meilleurs plongements que le t-SNE standard ou d'autres méthodes multiscalaires.

Méthodologie
L'étude introduit une perturbation contrôlée de la construction d'affinité standard de t-SNE : une transformation de puissance par ligne appliquée aux probabilités conditionnelles $p_{j|i}$.

1. La transformation : Pour un point $i$ donné, les probabilités conditionnelles sont transformées à l'aide d'un paramètre $\gamma \geq 0$ :
   $$\tilde{p}_{j|i} = \frac{p_{j|i}^\gamma}{\sum_{m \neq i} p_{m|i}^\gamma}$$

   • $\gamma = 1$ : Recouvre le t-SNE standard.
   • $\gamma < 1$ (Lissage/Smoothing) : Réduit les probabilités élevées par rapport aux plus petites, redistribuant la masse vers les voisins de plus faible probabilité.
   • $\gamma > 1$ (Accentuation/Sharpening) : Concentre davantage la masse sur les plus grandes probabilités.
   • $\gamma = 0$ : Résulte en une distribution uniforme sur les voisins (abandonnant l'ordre de rang).

2. Caractérisation théorique :

   • Les auteurs prouvent que cette transformation de puissance est mathématiquement équivalente à un re-dimensionnement de la largeur de bande Gaussienne ($\sigma_i$) du noyau original. Spécifiquement, la nouvelle largeur de bande effective devient $\tilde{\sigma}_i = \sigma_i / \sqrt{\gamma}$.
   • Crucialement, contrairement au changement du paramètre de perplexité globale $\rho$ (qui force chaque point à avoir le même nombre effectif de voisins), l'application d'un $\gamma$ fixe entraîne des perplexités effectives dépendantes du point. La perplexité effective varie en fonction de la forme de la distribution originale pour chaque point spécifique.

3. Configuration expérimentale :

   • La méthode a été implémentée dans openTSNE et évaluée sur les jeux de données MNIST, UCI Adult et Mouse Cortex.
   • La métrique principale d'évaluation était le Chevauchement de Voisinage à $k$ (NO@k), mesurant la fraction des $k$-plus proches voisins en haute dimension préservés dans le plongement.
   • Les comparaisons ont été faites contre le t-SNE standard, la variation de la perplexité globale, et d'autres constructions d'affinité (Multiscale, Fixed Sigma, Uniform, et tt-SNE).

Résultats clés
Les expériences révèlent un compromis clair dépendant de l'échelle, régi par $\gamma$ :

• Accentuation ($\gamma > 1$) : Améliore la préservation des plus proches voisins (petits $k$). Cependant, les performances se dégradent rapidement à mesure que $k$ augmente.
• Lissage ($\gamma < 1$) : Améliore la préservation des voisinages locaux plus larges (gamme de $k$ intermédiaire) et de la structure globale.
  • Spécifiquement, le lissage avec $\gamma \approx 0,7$ a surpassé le t-SNE standard et les méthodes multiscalaires dans la plage « mid-local » ($k \approx 25–90$).
  • Le lissage a également amélioré la préservation de la structure globale (mesurée par la corrélation de rang de Spearman des distances), particulièrement à des perplexités élevées.
• Comparaison avec le réglage de la perplexité globale : Augmenter simplement la perplexité globale $\rho$ dans le t-SNE standard ne reproduit pas les bénéfices du lissage. Le lissage crée une distribution hétérogène de tailles de voisinage effectives entre les points, tandis qu'augmenter $\rho$ déplace uniformément l'échelle pour tous les points. Par conséquent, le t-SNE lissé a atteint des scores NO@k plus élevés à des valeurs de $k$ spécifiques que le t-SNE standard avec des perplexités équivalentes ou supérieures.
• Comparaison avec d'autres méthodes : Dans la plage mid-locale, la variante lissée ($\gamma=0,7$) a surpassé le mélange Multiscale (Multiscale Mixture) et les méthodes Multiscale, qui incorporent plusieurs échelles de largeur de bande. Les variantes accentuées ($\gamma=1,5$) ont dominé à de très petits $k$, tandis que les distributions uniformes ($\gamma=0$) ont dominé à de très grands $k$.

Signification et affirmations
L'article affirme que la netteté de l'affinité est un axe significatif et jusqu'ici peu exploré du comportement de t-SNE. Les principales contributions sont :

1. Découplage de la taille et de la distribution du voisinage : L'étude démontre que le nombre de voisins (contrôlé par la perplexité) et la distribution de la masse de probabilité parmi eux (contrôlée par $\gamma$) sont deux facteurs distincts.
2. Réglage léger (Lightweight Tuning) : Le paramètre $\gamma$ offre aux praticiens un mécanisme simple et léger pour déplacer le focus de l'embedding :
   • Utiliser des affinités plus accentuées ($\gamma > 1$) si l'objectif est une haute fidélité pour les plus proches voisins.
   • Utiliser des affinités plus lisses ($\gamma < 1$) pour améliorer la préservation des structures locales plus larges et de la topologie globale.
3. Limites : Les auteurs notent modestement que bien que les améliorations soient constantes, elles sont modestes en termes absolus. L'étude se concentre sur une mesure de qualité unique (NO@k), et la traduction pratique de ces améliorations de métriques vers des insights de domaine spécifiques reste une question ouverte. De plus, les hyperparamètres optimaux ($\rho, \gamma$) pour des valeurs de $k$ spécifiques n'ont pas été exhaustivement optimisés dans ce travail.

En conclusion, l'article soutient que le t-SNE standard peut concentrer la masse de probabilité trop lourdement sur les premiers voisins, limitant ainsi sa capacité à préserver les structures locales plus larges. En lissant la matrice d'affinité, on peut redistribuer cette masse vers les voisins de rang intermédiaire, améliorant ainsi la fiabilité des sous-structures de clusters et de la disposition globale sans modifier la procédure d'optimisation ou la scalabilité computationnelle.