Module 3 · Page 3/4

t-SNE

t-distributed Stochastic Neighbor Embedding — transformer les distances en probabilités, puis minimiser la divergence KL entre les distributions haute et basse dimension.

1. L'idée fondamentale

Approche probabiliste

t-SNE convertit les distances entre points en probabilités de similarité. Deux points proches ont une forte probabilité d'être "voisins", deux points éloignés ont une faible probabilité. L'objectif est de trouver une représentation 2D (ou 3D) où les probabilités de voisinage sont aussi similaires que possible à celles de l'espace original.

Pourquoi "t" dans t-SNE ?

Dans l'espace original, on utilise une distribution gaussienne. Dans l'espace réduit, on utilise une distribution de Student à 1 degré de liberté (= distribution de Cauchy). Cette distribution a des queues plus lourdes — elle pénalise moins les points éloignés, ce qui évite l'"effet crowding" de SNE classique.

2. Les distributions de similarité

Espace original (haute dim.)

Distribution gaussienne centrée sur \(x_i\) :

\(p_{j|i} = \frac{\exp(-\|x_i-x_j\|^2/2\sigma_i^2)}{\sum_{k\neq i}\exp(-\|x_i-x_k\|^2/2\sigma_i^2)}\)

\(\sigma_i\) est choisi pour que la perplexité locale soit égale au paramètre Perp fixé.

Espace réduit (basse dim.)

Distribution de Student (t, ν=1) :

\(q_{ij} = \frac{(1+\|y_i-y_j\|^2)^{-1}}{\sum_{k\neq l}(1+\|y_k-y_l\|^2)^{-1}}\)

Queues plus lourdes → mieux gérer les points modérément éloignés.

3. La fonction de coût — divergence KL

\[ C = KL(P \| Q) = \sum_i \sum_j p_{ij} \log \frac{p_{ij}}{q_{ij}} \]

P : matrice de similarités dans l'espace original (symétrisée : \(p_{ij} = (p_{j|i}+p_{i|j})/2n\))
Q : matrice de similarités dans l'espace réduit (distribution de Student)
KL(P‖Q) : divergence de Kullback-Leibler — mesure l'écart entre deux distributions
Propriété : \(KL(P\|Q) \geq 0\) et \(KL(P\|Q) = 0\) seulement si \(P = Q\)
Asymétrie : \(KL(P\|Q) \neq KL(Q\|P)\) — pénalise fortement les faux voisins proches

4. Optimisation par descente de gradient

Gradient

On minimise \(C\) par rapport aux coordonnées \(y_i\) par descente de gradient. Le gradient a une forme intuitive — il ressemble à des forces attractives/répulsives :

\[ \frac{\partial C}{\partial y_i} = 4 \sum_j (p_{ij} - q_{ij})(y_i - y_j)(1 + \|y_i - y_j\|^2)^{-1} \]

Si \(p_{ij} > q_{ij}\) : les points sont trop éloignés en basse dim. → force attractive
Si \(p_{ij} < q_{ij}\) : les points sont trop proches en basse dim. → force répulsive
L'optimisation est itérative (gradient stochastique), non déterministe.

5. La perplexité — paramètre clé

Définition

La perplexité contrôle le nombre effectif de voisins considérés pour chaque point. Elle détermine \(\sigma_i\) pour chaque point via la relation :

\[ \text{Perp}(P_i) = 2^{H(P_i)} \qquad \text{où} \quad H(P_i) = -\sum_j p_{j|i} \log_2 p_{j|i} \]

\(H(P_i)\) : entropie de Shannon de la distribution locale autour de \(x_i\)
Valeurs typiques : Perp ∈ [5, 50]
Perp faible → structure très locale, clusters serrés · Perp élevée → structure plus globale

6. Visualisation — effet de la perplexité

▶ Simulation t-SNE — effet de la perplexité

Perplexité 10

3 clusters simulés. La perplexité contrôle la résolution locale vs globale.

7. Limites importantes de t-SNE

Limites à connaître

Non déterministe : résultat différent à chaque exécution (initialisation aléatoire).
Distances inter-clusters non interprétables : la distance entre deux clusters dans le plan t-SNE ne reflète pas leur vraie distance — seule la structure interne des clusters est fiable.
Pas de projection de nouveaux points : impossible de projeter de nouveaux points sans recalculer.
Coût élevé : \(O(n^2)\) naïvement, \(O(n \log n)\) avec Barnes-Hut.
Perplexité : un mauvais choix peut créer des clusters artificiels.

t-SNE vs ACP vs ISOMAP vs LLE

ObjectifACP : variance max · ISOMAP/LLE : distances/poids locauxt-SNE : similarités probabilistes locales

Optim.Déterministe (diagonalisation)Itérative (gradient) — non déterministe

DistancesInter-clusters interprétables en ACP/ISOMAPt-SNE : distances inter-clusters NON interprétables

UsageAnalyse, compression, projectiont-SNE : visualisation uniquement (2D/3D)

📌 À retenir / À l'examen

t-SNE = minimiser \(KL(P\|Q)\) entre similarités gaussiennes (haute dim.) et Student (basse dim.)
Distribution haute dim. : gaussienne centrée, \(\sigma_i\) calibré par la perplexité
Distribution basse dim. : Student à 1 ddl (queues lourdes → évite le crowding)
Gradient : \(\partial C/\partial y_i = 4\sum_j (p_{ij}-q_{ij})(y_i-y_j)(1+\|y_i-y_j\|^2)^{-1}\)
Perplexité (5–50) : contrôle le nombre effectif de voisins locaux
⚠ Distances inter-clusters non interprétables · Non déterministe · Visualisation seulement

🧠 Quiz de validation

Pourquoi t-SNE utilise-t-il une distribution de Student dans l'espace réduit plutôt qu'une gaussienne ?

Que mesure la divergence KL(P‖Q) dans t-SNE ?

Peut-on interpréter la distance entre deux clusters dans une visualisation t-SNE ?

← LLE UMAP →