• 15 heures
  • Difficile

Ce cours est visible gratuitement en ligne.

Ce cours est en vidéo.

Vous pouvez obtenir un certificat de réussite à l'issue de ce cours.

J'ai tout compris !

Mis à jour le 01/02/2019

Découvrez une variété qui favorise la structure locale

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Dans ce chapitre nous allons étudier en détail les méthodes qui favorisent la structure locale du phénomène observé. L’objectif n’est donc pas de retrouver la variété globale d’origine mais de souligner certains comportement des données à l’échelle locale.

Problème avec l'ACP et les méthodes globales

Comme on l’a vu précédemment, l’analyse par composantes principales essaie de déterminer la structure sous-jacente d’un jeu de données. Pour rappel, l’ACP maximise la variance en minimisant l’erreur en distance euclidienne entre les données originales et la projection.

Parce qu’on utilise une erreur quadratique, seulement les grandes distances/variations entre les données sont magnifiées, et “écrasent” rapidement les petites variations.

Les points ici sont proches dans l’espace euclidien (en pointillé la distance euclidienne) mais éloignés si on considère le jeu de données (en trait plein la distance “selon les données”)

L’idée des algorithmes de ce chapitre est de considérer la variété (manifold en anglais) tout entière, et se concentrer sur la structure locale des données, en mettant en exergue cette fois les paires de distances euclidiennes entre les points proches.

On gagne ainsi deux avantages principaux :

  • En travaillant seulement à l’échelle locale, on travaille avec beaucoup moins de points sur nos calculs, donc un gain en complexité algorithmique non-négligeable

  • On aura une meilleure représentation d’un plus grand nombre de variétés, dont la géométrie générale est trop éloigné d’une représentation euclidienne pour pouvoir être utile. En se libérant de cette contrainte générale, on ouvre ainsi la possibilité de représentation plus fidèle sur une plus large classe de variété.

LLE (Locally Linear Embedding)

On commence à y être habitué, on veut trouver une représentation de dimension inférieure de nos points $\(X = [x_1, x_2, ... x_N]\)$ . Cette fois ci en revanche, on ne va travailler que sur le voisinage des points.

La technique de LLE (qui est apparu dans le même journal que Isomap d’ailleurs), consiste à effectuer deux optimisations.

La première, c’est dans l’espace d’origine à grande dimension, trouver comment reconstruire chaque points à l’aide de ses K plus proches voisins, en minimisant la fonction suivante :

$\[Min_W E = || X - W V(X) ||\]$

Où V(X) représente la matrice des K voisins de X. On obtient ainsi la matrice W.

A l’aide de cette matrice, on veut trouver les points Y dans la variété de dimension inférieure en minimisant :

$\[min_Y E = || Y - W Y ||\]$

Et voilà ! C’est facile hein 😀

C’est une première méthode, assez classique de visualisation de données non-linéaire. En général, la variété se retrouve représenté le long d’axe qui représentent les degré de libertés principaux du phénomène.

LLE sur des images de spectroscopie
LLE sur des images de spectroscopie

t-SNE (t-Stochastic Neighbour Embedding)

Dans cette partie, nous allons étudier une des méthodes de visualisation les plus usitées en ce moment, t-SNE, pour “t-distributed Stochastic Neighbor Embedding”. Le t désigne une distribution utilisée dans l’algorithme (pour loi t de Student, on verra plus tard pourquoi).

En bref, cette technique permet de visualiser des données de (très) grandes dimensions, en effectuant un plongement (embedding en anglais) dans une variété de plus petite dimension, généralement 2 ou 3 pour pouvoir repérer des caractéristiques intéressantes du phénomène à modéliser. Elle est devenue populaire pour sa capacité à générer des visualisations très parlantes.

Intuition du fonctionnement

Comme je l’ai dit plus haut, le t-SNE met l’accent sur les petites distances. Le concept général de l’algorithme est de considérer chaque point de données séparément, et d’assigner une probabilité conditionnelle (un poids) gaussienne à chacun des autres points en fonction de leur distance par rapport à ce point.

Une fois toutes ces probabilités calculées $\(P_{ij}\)$ , on peut plonger dans une dimension inférieure ce jeu de données en calculant une nouvelle distribution $\(Q_{ij}\)$ (qui est une t-student distribution cette fois, d’où le “t”), qui minimise la KL divergence entre P et Q.

L’idée est de trouver un espace de dimension inférieure mais qui respecte une distribution proche en KL divergence de la distribution d’origine.

Encore une fois, la probabilité met l’accent sur la structure locale, puisqu’elle met plus de poids sur les petites distances entre les points du jeu de données.

On peut par exemple appliquer t-SNE sur le jeu de données de visages (Olivetti dataset).

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import fetch_olivetti_faces
from sklearn import (manifold, datasets, decomposition, ensemble,discriminant_analysis, random_projection)
from matplotlib import offsetbox

olivetti = fetch_olivetti_faces()
targets = olivetti.target
data = olivetti.data
images = olivetti.images

# fonction pour afficher une partie des images sur la visualisation 2D
def plot_embedding(X, title=None):
    x_min, x_max = np.min(X, 0), np.max(X, 0)
    X = (X - x_min) / (x_max - x_min)

    plt.figure(figsize=(15, 15))
    ax = plt.subplot(111)

    if hasattr(offsetbox, 'AnnotationBbox'):
        shown_images = np.array([[1., 1.]])
        for i in range(data.shape[0]):
            dist = np.sum((X[i] - shown_images) ** 2, 1)
            if np.min(dist) < 2e-3:
                continue
            shown_images = np.r_[shown_images, [X[i]]]
            props=dict(boxstyle='round', edgecolor='white')
            imagebox = offsetbox.AnnotationBbox(offsetbox.OffsetImage(images[i], cmap=plt.cm.gray, zoom=0.5), X[i], bboxprops=props)
            ax.add_artist(imagebox)
    if title is not None:
        plt.title(title)
        
        
X = data
tsne = manifold.TSNE(n_components=2, perplexity=40, n_iter=3000 init='pca')
X_tsne = tsne.fit_transform(X)
plot_embedding(X_tsne, "Principal Components projection of the digits")
plt.show()

Comme on peut le voir, t-SNE permet de distinguer différents clusters, associés au différents visage, sans supervision ! Vous pouvez essayer de reproduire une visualisation similaire à l'aide de différents hyperparamètres (perplexité, nombre d'itérations)

Utilisation en pratique

Maintenant que vous avez une intuition du fonctionnement du t-SNE, on va voir comment l’utiliser en pratique et dans quelles circonstances il sera le plus pertinent.

 Attends mais ce n’est pas censé être un algorithme non-supervisé ? Je ne suis pas censé appuyer sur un bouton magique et avoir mon résultat ?

Même si c’est un algorithme non-supervisé, il demande de développer une petite intuition de son fonctionnement et des différents comportement sur des cas simples afin de pouvoir comprendre un peu mieux les visualisations créées et les interpréter correctement.

Perplexité

Une notion que je n’ai pas évoqué dans l’explication sur le fonctionnement du t-SNE est la notion de perplexité, que vous allez devoir fixer pour utiliser l’algorithme. La perplexité représente en fait la taille de la variance de $\(p_{ij}\)$ . Grosso modo elle représente la balance entre prise en compte de la structure globale et locale c’est à dire une estimation du nombre de voisins “proches” (relativement à l’ensemble du jeu de données) que possède chaque points.

Typiquement, vous pouvez tester une valeur de la perplexité entre 5 et 50 à partir de 5-10k observations.

Visualisation du dataset

t-SNE permet de visualiser la structure des données à très hautes dimension, afin de pouvoir orienter par la suite la modélisation.

Alors, que représente cette visualisation du jeu de données?

Et bien la principale chose qu’on peut distinguer sur le t-SNE c’est les différents cluster créés, qui peuvent représenter plusieurs catégories de données qui ont été détectées. Comme les chiffres sur l’image plus haut par exemple.

La seconde chose qui peut arriver, c’est que l’ordre relatif des différentes observations peut représenter une feature sous jacente. Par exemple, j’ai zoomé ci-dessous sur le cluster de “1” d’une visualisation t-SNE des données MNIST. Comme on peut le voir, les 1 sont organisés selon leur orientation (de légèrement penché vers la gauche à légèrement penché vers la droite).

Si t-SNE vous fournit un clustering satisfaisant (avec des groupes assez bien séparés) par rapport à une PCA linéaire classique, cela veut dire que vous pourrez utiliser des algorithmes supervisés favorisant cette structure locale (comme le SVM que nous étudierons dans un autre cours).

Validation de features

Visualiser les données, c’est pas mal pour développer une intuition sur notre dataset. Une autre application assez utilisée du t-SNE c’est de valider les features que l’on vient de créer.

En effet, si vous avez créé des features qui vous semblent représentatives des distinctions entre les données, cette distinction doit se retrouver lors de la visualisation du t-SNE. Si vos features ne semble pas se retrouver groupées de manière significative, c’est peut être qu’elles ne sont pas si représentative des similarités/distinctions entre les données qui vous permettront de les modéliser.

Le t-SNE dans ce sens, permet de valider que les features créées sont bien représentatives de la topologie du jeu de données, et permettront potentiellement une modélisation correcte du phénomène.

Potentiels problèmes

Problèmes d'interprétation

Il existe pléthore d’erreurs d’interprétation possible, sur tous les autres aspects du phénomène : la taille des cluster n’est pas significative, ni la distance entre les différents clusters, difficile de détecter la topologie (i.e. si une catégorie de points est contenue dans l’autre). Attention à ne pas surinterpréter les visualisations.

Je vous conseille l'excellent article sur le sujet : http://distill.pub/2016/misread-tsne/

Problèmes de temps de calcul

t-SNE possède une complexité quadratique $\(O(N^2)\)$ au nombre de points N, en temps et espace. Ce qui veut dire que ça devient rapidement inutilisable au delà de quelque milliers/dizaine de milliers de points.

Heureusement, une technique a été développée depuis qui partitionne l’espace pour optimiser le calcul des différentes $\(p_{ij}\)$ . Cette méthode utilise la méthode de Barnes-Hut qui permet de partitionner l’espace afin d’optimiser le calcul des distances entre chaque point qui est le plus lourd en termes de calculs. En utilisant cette méthode d’approximation, t-SNE est applicable sur un gros jeu de données, et passe à une complexité   $\(O(N log N)\)$ . C’est en fait la méthode recommandée, qui est déjà implémentée dans la fonction t-SNE de scikit 😱

Données métriques

Il faut faire attention à la nature des données évaluées. En effet, t-SNE n’est pratique que lorsqu’il existe une symétrie entre les données. C’est à dire que si un point A est proche de B et B est proche de C, alors A est proche de C (l’inégalité triangulaire est respectée). Il existe une variante du t-SNE pour ce genre de besoin, à l'aide de plusieurs visualisations (l'article de référence ici)

Quand est-ce que ce n’est pas le cas ?

Un cas simple qui n’est pas représentable par un t-SNE classique sont les données texte. Imaginons que le mot “roi” est proche de “reine” et que “reine” est proche du mot “femme”, ça ne veut pas dire que “roi” est proche de “femme” ! t-SNE ne fera pas cette distinction. Faîtes donc bien attention à la signification des relations entre les observations. 

Pas de préservation de la structure globale

Comme je l’ai dit plus haut, l’algorithme t-SNE a été construit spécifiquement pour mettre en exergue la structure locale du jeu de données. C’est pourquoi il perd facilement la structure globale du dataset, qui peut aussi être utile à visualiser.

L’idée dans ce cas est soit d’utiliser plusieurs visualisations (une t-SNE pour observer la structure locale, et PCA ou Isomap pour la structure globale par exemple). Une autre solution est d’initialiser l’algorithme t-SNE par une PCA avant de le lancer, ce qui permet de conserver de base un peu plus de la structure globale (avec l'optioninit=’pca’)

Résumé

On a vu dans ce chapitre l’algorithme t-SNE qui est une des méthodes les plus utilisées pour visualiser des données à grandes dimensions non-linéaires afin de repérer des structures locales intéressantes pour le travail de modélisation.

Attention encore une fois à bien développer une intuition de ce que peut apporter une visualisation t-SNE et à bien en faire plusieurs exécutions avec différents hyperparamètres. Il faut tester un bon nombre de fois ces méthodes avec des datasets différents pour bien les prendre en main.

Exemple de certificat de réussite
Exemple de certificat de réussite