Travaux pratiques - t-SNE

(correspond à 1 séance de TP)

Références externes utiles :

L’objectif de cette séance de TP est de présenter l’utilisation des fonctionnalités de scikit-learn concernant l’apprentissage de variétés et, plus spécifiquement, l’usage de t-SNE. Au passage, ce TP vise à donner une meilleure compréhension de cette méthode et de l’impact de ses paramètres sur les résultats. Pour cela, nous examinerons dans un premier temps un jeu de données synthétiques (les demi-lunes) puis nous travaillerons sur des données réelles de chiffres manuscrits.

Fléau de la dimensionalité

Pour illustrer comment la dimensionalité des données influe sur la distance euclidienne, commençons par générer un jeu de données de 100 observations en dimension 10. Ces données générées suivent une loi aléatoire uniforme.

import numpy as np
import matplotlib.pyplot as plt

n = 100
d = 10

X = np.random.rand(n, d)

À l’aide de la fonction scipy.spatial.distance_matrix, nous pouvons calculer la matrice des distances euclidiennes entre toutes les paires de points. Nous allons ensuite la visualiser sous forme de matrice :

from scipy.spatial import distance_matrix
distances = distance_matrix(x, x, p=2) # norme 2

plt.matshow(distances)
plt.show()

Nous pouvons également définir un point de référence \(q\) et calculer sa distance à chaque point \(x_i\) du jeu de données. Nous pouvons ensuite calculer le minimum et le maximum de ces distances :

q = np.random.rand(d)
dists = np.array([np.linalg.norm(q -  xx) for xx in x])
print(np.min(dists)
print(np.max(dists)

Question

Augmentez la dimensionalité des données (variable d) et répétez les opérations précédentes. Que constatez-vous ? En quoi cela illustre le fléau de la dimensionalité ?

Correction

Lorsque l’on augmente la dimension des données, l’écart entre la distance minimale et la distance maximale se resserre. De la même façon, la matrice des distances devient de plus en plus homogène. Cela illustre que, pour des variables indépendantes, tous les points se retrouvent à peu près à la même distance des uns des autres quand la dimension augmente. Autrement dit, la distance euclidienne ne permet plus de séparer les différentes observations.

Réduction de dimension de données générées

Afin de nous permettre de mieux comprendre l’effet de la réduction de dimension sur un nuage d’observations, nous allons commencer par manipuler des données bidimensionnelles et tridimensionnelles. Bien sûr, l’usage de la réduction de dimension sur de telles données est limitée car la dimension de départ est déjà faible. Toutefois, cela permet de se construire des intuitions sur l’effet des algorithmes utilisés en visualisant à la fois les données d’origine et les données réduites.

Données demi-lunes

Dans cette partie, nous allons travailler avec le jeu de données des « lunes ». Il s’agit d’un jeu de données bidimensionnel où le nuage des observations prend la forme de deux demi-lunes imbriquées. Ces deux groupes ne sont pas linéairement séparables. scikit-learn dispose d’une fonction intégrée pour générer une matrice d’observations correspondant aux demi-lunes dans sklearn.datasets.make_moons. Se référer à la documentation pour plus d’informations sur cette fonction.

import matplotlib.pyplot as plt
import numpy as np
import sklearn

from sklearn.datasets import make_moons
X, y = make_moons(n_samples=200, noise=0.1)
plt.scatter(X[:,0], X[:,1], c=y)
plt.show()

Implémentation de t-SNE

La description de l’implémentation de la réduction de dimension par l’algorithme t-SNE se trouve dans TSNE.

Le nombre de dimensions de l’espace réduit est spécifié dans le paramètre n_components, comme dans le cas de l’analyse en composantes principales. Par défaut, scikit-learn projette les données dans un espace bidimensionnel à des fins de visualisation (n_components=2) mais il est bien entendu possible de choisir un espace de n’importe quelle dimension.

Le paramètre le plus important de t-SNE est la perplexité, définie par la valeur du paramètre perplexity. Pour rappel, la perplexité peut être vue comme une estimation du nombre moyen de voisins d’un point. La variance de la gaussienne utilisée pour calculer les similarités entre les paires de points dans l’espace de départ est déterminée à partir de la valeur de la perplexité (qui augmente avec cette variance). Plus la perplexité est élevée, plus les voisins éloignés d’un point seront considérés. À l’inverse, une perplexité faible n’accordera d’importance qu’aux voisins les plus proches du point. En d’autres termes, augmenter la perplexité renforce l’importance accordée à la structure globale du jeu de données, tandis qu’une perplexité faible accorde plus d’importance aux structures locales. Par défaut, perplexity=30 dans Scikit-learn.

Un dernier paramètre d’intérêt de TSNE est le paramètre init qui contrôle la méthode d’initialisation des points dans l’espace réduit. De cette initialisation dépend en grande partie la visualisation obtenue par t-SNE puisque les points seront ensuite déplacés par la descente de gradient. Leur position initiale peut donc grandement affecter les résultats. Par défaut, TSNE utilise une initialisation aléatoire (init="random") mais ce comportement peut être modifié pour commencer par appliquer une analyse en composantes principales sur les données pour placer les points initiaux dans l’espace réduit (init="pca"). L’initialisation par ACP est généralement plus stable.

Outre les paramètres généraux de l’algorithme, l’optimisation de TSNE peut être modifiée à l’aide des paramètres optionnels suivants:

  • early_exaggeration: facteur d’exagération des similarités pour la phase initiale de l’optimisation.

  • learning_rate: détermine le pas de l’algorithme de descente de gradient. L’utilisation de la valeur "auto" est recommandée (elle exploite l’heuristique de [BCA19]).

  • n_iter: nombre d’itérations de la descente de gradient. Il peut être utile d’augmenter ce paramètre si t-SNE ne converge pas dans le temps imparti.

  • method ("barnes_hut" par défaut, accepte aussi la valeur "exact"): définit la méthode utilisée pour le calcul du gradient. Par défaut, TSNE utilise la méthode de Barnes-Hut qui est une approximation en \(O(N\log N)\) plutôt que la méthode exacte en \(O(N^2)\). La méthode exacte ne passe pas à l’échelle au-delà de quelques milliers d’exemples.

En règle générale, il est souhaitable de standardiser les données avant d’appliquer t-SNE.

Les méthodes qui peuvent être employées sont :

  • fit(X): calcul du modèle à partir des observations qui sont les lignes de X. Les valeurs réduites sont ensuite accessibles dans l’attribut .embeddings_.

  • fit_transform(X): calcule le modèle à partir des observations qui sont les lignes de X et renvoie la matrice des observations réduites.

Réduction des données demi-lunes

Nous pouvons appliquer l’algorithme t-SNE sur les demi-lunes afin de projeter les points sur une droite. Dans ce cas, le nombre de composantes de l’espace cible vaut 1. Nous laissons les paramètres par défaut de t-SNE pour l’instant.

from sklearn.manifold import TSNE

tsne = TSNE(n_components=1, perplexity=30)
embedding = tsne.fit_transform(X)
plt.scatter(embedding[:,0], np.zeros(len(embedding)), c=y)
plt.show()

Question

Appliquer TSNE à 10 reprises avec la méthode d’initialisation random. Calculer la moyenne et l’écart-type des valeurs finales de divergence de Kullback-Leibler obtenues (attribut .kl_divergence_).

Répéter avec la méthode d’initialisation pca et comparer les résultats.

Que constatez-vous ?

Correction

divergences = []

for i in range(20):
    tsne = TSNE(n_components=1, perplexity=30, init="pca").fit(X)
    divergences.append(tsne.kl_divergence_)

print(f"KL-divergence moyenne: {np.mean(divergences):.2f} +- {np.std(divergences):.2f}")

divergences = []

for i in range(20):
    tsne = TSNE(n_components=1, perplexity=30, init="random").fit(X)
    divergences.append(tsne.kl_divergence_)

print(f"KL-divergence moyenne: {np.mean(divergences):.2f} +- {np.std(divergences):.2f}")

La divergence KL moyenne est plus faible avec un écart-type plus resserré dans le cas de l’initialisation pca. Ce résultat est attendu: cette initialisation est plus stable que l’initialisation aléatoire utilisée par défaut.

Pour mieux comprendre l’impact de la valeur de la perplexité sur les résultats de la réduction de dimension obtenue par t-SNE, il peut être instructif d’appliquer l’algorithme sur des données bidimensionnelles sans changer la dimension. Cela permet de « simplifier » les données en cherchant, dans un espace de même dimension, une matrice d’observations qui a le même « structure » que celle des données initiales. Ce n’est pas une opération que l’on réaliserait en temps normal mais qui est riche d’enseignements pour se construire une intuition dans un TP.

from sklearn.manifold import TSNE

tsne = TSNE(n_components=2, perplexity=30)
embedding = tsne.fit_transform(X)
plt.scatter(embedding[:,0], embedding[:,1], c=y)
plt.show()

Question

Expérimenter avec différentes valeurs pour le paramètre de perplexité. Que constatez-vous ?

Correction

Avec une perplexité faible, les demi-lunes sont fragmentées et fortement détachées: t-SNE surdivise les groupes en se concentrant sur les structures locales.

Avec une perplexité élevée, on retrouve la structure globale du jeu de données et t-SNE reproduit presque exactement les demi-lunes.

Réduction de dimension sur les données Digits

Digits est un jeu de données contenant des images en niveaux de gris de chiffres manuscrits de \(8\times 8 = 64\) pixels. Il comporte 1797 observations réparties en 10 classes, une par chiffre. Un total de 43 personnes ont participé à la collecte de données. Les valeurs de pixels sont des entiers dans l’intervalle \([0,16]\). Plus d’informations sont disponibles dans la documentation de scikit-learn.

from sklearn.datasets import load_digits

X, y = load_digits(return_X_y=True)
print(X.shape)
plt.imshow(X[0].reshape((8,8)), cmap=plt.cm.binary)
plt.show()

Question

Appliquer une analyse en composantes principales sur le jeu de données Digits. Visualiser le nuage de points projeté sur les deux premières composantes principales.

Correction

pca = PCA(n_components=2)
X_pca = pca.fit_transform(X)
plt.scatter(X_pca[:,0], X_pca[:,1], c=y)
plt.show()

Question

Appliquer une réduction de dimension à l’aide de t-SNE (n_components=2) sur le jeu de données Digits puis afficher le nuage de points résultant. Varier la valeur du coefficient de perplexité dans une plage raisonnable (entre 1 et 100, par exemple). Que constatez-vous ?

Correction

for p in [1, 10, 30, 50, 100]:
    tsne = TSNE(n_components=2, perplexity=p)
    embedding = tsne.fit_transform(X)
    plt.scatter(embedding[:,0], embedding[:,1], c=y)
    plt.show()

Avec une perplexité faible, on ne distingue pas les groupes correspondant aux classes: des chiffres très similaires sont rapprochés mais ne sont pas connectés avec les autres du même groupe. Une perplexité forte capte mieux la structure globale et le positionnement des groupes entre eux.

[BCA19]

Belkina Anna, Ciccolella Christopher, Anno Rina, Halpert Richard, Spidlen Josef and Snyder-Cappione Jennifer. Automated optimized parameters for T-distributed stochastic neighbor embedding improve visualization and analysis of large datasets, Nature Communications, Volume 10, November 2019, http://dx.doi.org/10.1038/s41467-019-13055-y.