Visualizing Data using t-SNE

Introduction


Dans ce rapport, nous allons présenter l'article "Visualizing Data using t-SNE" pour ses auteurs Laurens van der Maaten, un scientifique et chercheur dans l’équipe de Yann Lecune à facebook AI Research, et Geoffrey Hinton qui est un professeur au département d'informatique de l'université de Toronto, un pionnier du machine learning et directeur du programme "Neural Computation and Adaptive Perception".
L'article a été publié en novembre 2008 sur "journal of machine learning research", par l'éditeur Yoshua Bengio qui est un chercheur canadien, spécialiste en intelligence artificielle et pionnier du deep learning.
Notre rapport contient plusieurs sections; nous verrons tout d'abord, le contexte de l'article,son positionnement et ses contributions à l'avancée des connaissances dans le domaine de recherche. Ensuite, nous enchaînerons par les expériences mises en place pour démontrer et argumenter le bon fonctionnement de l'approche proposée. Enfin, nous conclurons le travail dans la dernière partie du rapport.

Contexte


La visualisation des données de grandes dimensions est un problème important dans plusieurs domaines; prenons par exemple les noyaux cellulaires qui sont pertinents pour le cancer du sein, sont décrits par 30 variables. Ainsi, vecteurs d'intensité pour présenter les images ont typiquement des milliers de dimensions, nous avons encore les données génomiques qui se comptent par des dizaines de milliers de variables.
L'article présente une nouvelle technique appelée t-SNE qui permet de visualiser les données de grandes dimensions en donnant à chaque point de données un emplacement dans une carte à deux ou trois dimensions.

Positionnement


      Au cours des dernières années, une variété de techniques de visualisation de données ont été proposées, dont nous citons par exemple: affichage iconographique (Chernoff, 1973), techniques à base du pixel (Keim,2000), techniques représentant les dimensions de données comme des sommets dans les graphes (Bttista,1994).
La plupart de ces techniques fournissent des outils pour afficher plus de deux dimensions, et laisser l'interprétation des données à l'observateur humain, par conséquent, limiter l'applicabilité réelle de ces techniques sur des ensembles de données de grandes dimensions.
Les méthodes de réduction de dimensions convertissent l'ensemble de données de grandes dimensions en des données de deux ou trois dimensions. L'objectif de la réduction est de conserver la structure significative de données de grandes dimensions autant que possible dans la carte de faibles dimensions.
Divers techniques sont proposées pour cela; l'ACP est mise à l’échelle multidimensionnelle classique qui met l'accent sur le maintien des représentations. Des techniques non linéaires ont été proposées également la réduction de dimensionnalité et qui préservent la structure locale des données. Ces techniques qui sont examinées par Lee et Verleysen (2007) sont: la cartographie de Sammon (Sammon, 1969), analyse des composantes curvilignes (CCA, Demartines et Hérault 1997), stochastic neighbor embidding (SNE, Hinton et Roweis 2002), isomap (Tenenbaum 2000), maximum variance unfolding (MVU, Weinberger 2004), locally linear embidding (Roweis and saul, 2000), laplacian eigenmap (Belkin et Niyogi 2002).

Contributions


      En dépit des performances des techniques citées dans la partie précédente, sur des ensembles de données artificielles, elles ne sont souvent pas réussies à visualiser des données de grandes dimensions réelles. La plupart des techniques ne sont pas capables de retenir à la fois la structure locale et globale des données en une seule carte.
Dans l'article, il s'agit de la description d'une façon de conversion d'un ensemble de données de grandes dimensions et l'introduction de la nouvelle technique t-SNE pour visualiser les données. Cette dernière est capable de capturer une grande partie de la structure locale de grande dimension, tout en révélant la structure globale.

Expérimentation


      Dans cette partie du rapport, nous évaluerons les performances de la t-SNE, et nous la comparons avec quelques techniques citées ci-dessus. Ainsi,nous démontrons sa supériorité.

   1.  La SNE 


      La méthode Stochastic Neighbor Embedding (SNE) consiste à convertir les distances euclidiennes de grandes dimensions entre les points de données en probabilités conditionnelles qui présentent les similitudes, mathématiquement donnée par l’équation (1).

Pour les homologues yi et yj des points de données xi et xi, il est possible de calculer la probabilité conditionnelle similaire notée Qj /i. On fixe la variance à 1/21/2, par conséquent, on modélise la similarité de la carte de points yj en carte de points yi par l’équation(2).
 
Puisqu’on s’intéresse qu’aux similitudes appariées, on met Qj /i=0. Si les points yi et yj modélisent correctement la similitude entre les points de données, les probabilités conditionnelles sont égales. Partant de cette observation, la SNE vise à trouver une présentation faible dimension qui minimise le décalage entre Pj/i et Qj /i. Pour cela, on utilise la fonction du coût (3)

Mais les différents types d’erreurs dans les distances appariées ne sont pas pondérés de façon égale. En particulier, le coût reste important pour l’utilisation des points largement séparés.

    2.  La t-SNE 


     La SNE telle que présentée par Hinton et Roweis a de bonnes visualisations mais entravée par une fonction de coût difficile à optimiser.
La t-SNE est une nouvelle technique qui vise à atténuer le problème en utilisant une nouvelle version de la fonction de coût de la SNE symétrisée avec des gradients plus simples, et en utilisant aussi la loi de student plutôt que la loi gaussienne pour le calcul de la similarité entre deux points dans l’espace de faible dimension.

        a.      La SNE symétrisée


      On met Pj/i=Qj/i=0, et on réfère à ce que ce type d’SNE est une SNE symétrique.Dans l’espace de faible dimension, la SNE symétrique utilise l’équation (4).
Son principal avantage est la forme simple du gradient qui est plus rapide à calculer, il est donné par(5)

       b.      La loi student


      Dans la t-SNE, on emploie une distribution t de student avec un seul degré de liberté, ce qui rend la présentation de la carte des probabilités conjointes invariante aux changements dans l’échelle  de la carte pour des points qui sont éloignés. Cela signifie que de grands groupes de points qui sont éloignés interagissent exactement de la même manière que les points individuels, de sorte que l’optimisation fonctionne de la même façon pour tous.

      c.      Méthodes d’optimisation de t-SNE 


      C’est une procédure du gradient descendant pour optimiser la fonction du coût de t-SNE, une procédure qui utilise un terme dynamique pour réduire le nombre d’itérations nécessaires. Deux astuces pour améliorer les résultats :
La compression précoce, en forçant les points de la carte pour rester rapprochés au début de l’optimisation.
L’exagération précoce, en multipliant par exemple toutes les probabilités par 4 au cours des étapes initiales d’optimisation.
L’effet est que les grappes naturelles ont tendance à former des grappes serrées largement séparées dans la carte, cela crée beaucoup d’espace vide sur la carte qui rend beaucoup plus facile le déplacement des grappes les unes par rapport aux autres afin de trouver une organisation globale.

    3.  Expérimentation

      On compare la t-SNE avec d’autres méthodes de réduction de dimensionnalité. Les expériences ont été effectuées sur des ensembles de données qui présentent une variété de domaines d’application.

      a.      Les ensembles de données


      Les données MINIST contiennent 60000 images au niveau de gris de chiffres manuscrits ; pour les essais, on choisit 6000 par hasard en raison de calcul.
Les données OLIVETTIFACES  se composent des images de 40 individus, l’ensemble de données contient 400 images (10 par individu) de taille 10304 pixels.
L’ensemble de données COIL-20 contient des images de 20differents objets vus de 72 orientations également espacées qui donne un total de 1440 images contenant 1024 pixels.

     b.      Configuration expérimentale


    On commence par l’utilisation de l’ACP pour réduire les dimensions à 30 afin d’accélérer les calculs et supprimer les bruits sans gravement fausser les différences entre les points de données. On utilise ensuite pour chacune des dimensions une technique de réduction pour convertir la présentation tridimensionnelle 30 en une carte bidimensionnelle, et on affiche le résultat comme un nuage de points. La coloration fournit un moyen d’évaluer la façon dont la carte préserve les similitudes dans chaque classe.

     c.       Les résultats


      La figure  1 présente les résultats de la visualisation avec t-SNE, cartographie sammon et LLE sur l’ensemble de données MINIST. Les résultats relèvent la forte performance de la t-SNE  par rapport aux autres techniques ; en particulier, la cartographie Sammon construit une boule dans laquelle seuls trois classes sont séparés des autres classes, quant à et LLE produit des solutions dans lesquelles il y’ a de grands chevauchements entre les classes de chiffres. En revanche, t-SNE construit une carte dans laquelle la séparation entre les classes et les chiffres est presque parfaite.

La figure 2 montre les résultats de l’application de t-SNE, cartographie de sommon et LLE à l’ensemble de données OLIVETTIFACES. Encore une fois, Sammon et LLE produisent des solutions qui fournissent peu d’informations sur les classes de données. La carte construite par Sammon est significativement meilleure car elle modélise un bon nombre de catégories approchées, mais aucune des classes n’est clairement séparée. La t-SNE  fait un bon travail, certaines personnes ont leurs images divisées en deux groupes, pour ces personnes, c’est clair que leurs 10 images forment une classe naturelle en utilisant la distance euclidienne dans l’espace du pixel.

La figure 3 montre les résultats de la t-SNE , cartographie sammon et LLE pour la COIL-20. Pour la plupart des 20 objets, t-SNE représente avec un précision le collecteur à une dimension des points de vue comme une boucle fermée.  Cette figure montre également que les trois autres techniques ne sont pas aussi bien à séparer proprement les collecteurs qui correspondent à des objets très différents, de plus, LLE visualise seulement un petit nombre de classes à partir de l’ensemble de données COIl-20  parce que ce dernier, comprend un grand nombre de sous-variétés largement séparées qui donne lieu à une connectivité des composants du graphe de voisinage.


Discussion


      Les résultats de l’expérimentation démontrent les performances de la t-SNE sur une grande variété d’ensemble de données, mais elle a tout de même quelques faiblesses comme la difficulté de savoir comment elle joue sur la dimensionnalité de réduction de tâches. Ainsi qu’elle n’est pas garantie à converger vers un optimum global de sa fonction du coût.
Pour valider encore plus les performances de la t-SNE, on a exécuté le programme se trouvant dans la toolbox  qui évalue plusieurs techniques sur un ensemble de données de 1000 points.

Les résultats sur la figure 4 démontrent la forte performance de la t-SNE par rapport aux autres techniques. La t-SNE a pu préserver toutes les données en les séparant  dans des classes différentes, contrairement à Isomap et LLE.

Conclusion



      La t-SNE est une nouvelle technique de visualisation de données qui est capable de retenir la structure locale de données tout en révélant une structure globale importante. Elle est capable de visualiser un grand nombre d’ensemble de données avec des demandes de calculs limitées.
Les expériences sur divers ensembles de données montrent que la t-SNE surpasse les autres techniques existantes pour visualiser une large variété d’ensembles de données.
Les auteurs de l’article prévoient d’enquêter dans l’avenir, sur l’optimisation du nombre de degrés de liberté de la distribution t-student utilisée dans la t-SNE. Ils visent aussi à améliorer et développer une version paramétrique de t-SNE qui permet de généraliser les données d’essais détenues pour former un empilement de réseau de neurones qui fournit une cartographie explicite dans l’espace de faible dimension.


ANNEXE