Business Intelligence

Visualisation de données (partie 2: approches non linéaire)

Benjamin Piwowarski

21 mars 2022

$\def \argmin {\mathop{\textrm{argmin}}} \def \argmax {\mathop{\textrm{argmax}}} \def \RR {\mathbb{R}} \def \Ind#1{\mathbf{1}\left[#1\right]} \def \eqc { \stackrel{\small +}{=}} \def \px {\tilde{x}} \def \py {\tilde{x}} \def \rx {\hat{x}} \def \tr {\mathop{\mathrm{tr}}} \newcommand{\msrinv}[1]{-\frac{1}{\sqrt #1}} \newcommand{\minv}[1]{-\frac{1}{#1}}$

Introduction

Motivation - apprentissage de métriques (variétés)

Projeter sur des axes peut trop déformer les données
Les données peuvent se trouver sur des variétés
Les projections linéaires ne sont plus adaptées

Méthodes

Il y'en a des tonnes. Allez sur wikipedia !

Positionnement multidimensionnel (Multidimensional Scaling, MDS)
Préserve les distances
Isomap
Préserve les distances géodésiques
Représentations localement linéaires (Locally-linear embedding, LLE)
Préserve les relations linéaires
Laplacian eigenmaps (théories des graphes)
Utilisation de l'analyse spectrale sur une matrice représentant le graphe de voisinage
Carte de Kohonen (Self-organizing maps)
Projection sur une structure prédéfinie
Auto-encodeurs (réseaux de neurones)
Compression de l'information
t-SNE (Représentation suivant une distribution de Student)
Alignement de distributions de probabilité
...

Positionnement Multi-Dimensionnel (MDS)

Multi-Dimensional Scaling

Positionnement Multi-Dimensionnel

On associe à chaque point originel $x_i$ une représentation $\tilde x_i$

Préservation des distances

Le but est de préserver des informations géométriques - comme la distance

$$S(\tilde x_1,\tilde x_2,...,\tilde x_N)= \sum_{i\ne j} \bigl(d(x_i, x_j) - ||\tilde x_i-\tilde x_j||\bigr)^2 $$

Cas classique

Métrique

Doit vérifier

Séparation $d(x,y) = 0 \Leftrightarrow x = y$
Symmétrie $d(x,y)=d(y,x)$
Inégalité triangulaire $d(x,z) \le d(x,y) + d(y,z)$

Dans le cas le plus simple, $d(x_i, x_j)$ est une distance Euclidienne, i.e. $$ d(x_i, x_j) = \sqrt{\sum_k (x_{ik} - x_{jk})^2} $$

Cas classique : résolution

Dans ce cas où $d_{ij}$ est une distance euclidienne, alors il existe un algorithme :

La matrice de distance est définie par $D^{(2)}=\left(d_{ij} \right)_{ij}$
Avec un double centrage $B=-\frac{1}{2}CD^{(2)}C$ en utilisant $C=I - \frac{1}{n} \begin{pmatrix} 1 & \ldots & 1 \\ & \ddots & \\ 1 & \ldots & 1 \end{pmatrix} $
Décomposition en valeurs propres $$B = Q \Lambda Q^T$$ avec $\Lambda$ la matrice (diagonale) des valeurs propres ordonnées de manière décroissante et $Q$ orthonormale ($QQ^T=Q^TQ=Id$)
On pose ($Q_m$ = les $m$ premières lignes, $\Lambda_m$ les $m$ premières colonnes/lignes) $$X=Q_m\Lambda_m^{1/2}$$ qui sont les coordonnées (en ligne) de chaque point

Cas classique : résolution

Ça ne vous rappelle rien ?

Une sorte de PCA sur la matrice des distances

Exemple sur MNIST

Chaque chiffre est un vecteur dans $\RR^{64}$

sklearn / Manifold learning on handwritten digits

Cas général

Similarités

On peut généraliser la méthode à n'importe quelle mesure de similarité

$$S(\tilde x_1,\tilde x_2,...,\tilde x_N)= \sum_{i\ne j} \bigl(s(x_i, x_j) - ||\tilde x_i-\tilde x_j||\bigr)^2$$

Dans ce cas, pas de résolution exacte $\Rightarrow$ descente de gradient

Extension non linéaire

On peut utiliser une fonction $f$ qui permet d'amplifier ou non certaines différences dans l'espace de projection

Permet de placer des points lointains plus facilement lorsque les distances sont grandes

$$S(\tilde x_1,\tilde x_2,...,\tilde x_N)= \sum_{i\ne j} \bigl(s(x_i, x_j) - f(||\tilde x_i-\tilde x_j||) \bigr)^2 $$

Limites du MDS

On veut préserver l'ensemble des distances...

Mais...

Certaines distances ne sont-elles pas plus importantes ???

En particulier, plus un point est loin, moins la distance Euclidienne a de sens

Nouvelles méthodes qui respectent le voisinage local

IsoMAP

Variétés

Variété

Une variété est un espace qui en tout point est localement euclidien

exemple : une sphère est une variété dimension 2

En savoir plus : Variété (géométrie)

Une variété de dimension 2 (source Wikipedia)

Isomap

Isomap = Préserver les géodésiques

Au lieu de préserver les distances comme MDS, Isomap préserve les géodésiques

Géodésique

C'est le plus court chemin d'un point à un autre dans une variété

Exemple : grand cercle sur une sphère

Calcul des géodésiques

Approximation des géodésiques

Voisinage Euclidien

Localement, l'espace est Euclidien (variété)

On suppose que ...

soit les $k$ plus proches voisins
soit les voisins à une distance inférieure à ...

... forment un voisinage "Euclidien"

Algorithme

On construit un graphe de voisins
Calcul de la distance de la plus courte
en utilisant par exemple l'algorithme de Dijkstra
Utilisation de MDS avec distances géodésiques

Limites d'Isomap

Conclusions

On prend en compte des distances qui correspondent mieux aux données

On ne prend en compte que les distances aux $k$ plus proches voisins

Problème de l'estimation des distances qui est instable

Difficile de trouver le bon $k$

Isomap surestime les distances

Inégalité triangulaire

Locally-linear embedding (LLE)

Comme dans Isomap, on suppose que le voisinage d'un point est Euclidien

Dans LLE, on suppose que chaque point peut être exprimé comme combinaison linéaire de ses voisins

En quoi cela reflète l'hypothèse d'une variété ?

Les voisins de $x_i$ sont dans un espace Euclidien centré sur ce point

on peut combiner leurs représentations (additions vectorielles)

Locally-linear embedding (LLE)

Reconstruction par les voisins

Chaque point est approximé comme une combinaison linéaire de ses voisins $$\rx_i = \sum_{j \in V_i} w_{ij} x_j$$ avec $\sum_{j \in V_i} w_{ij} = 1$

Il y a deux étapes dans LLE

On cherche les $w_{ij}$ optimaux
On cherche les points dans $\RR^2$ qui reproduisent au mieux ces contraintes

Étape 1 : trouver les reconstructions optimales

Il faut définir deux choses : le voisinage et le critère

Le voisinage $V_i$

$k$-plus proches points (suivant la distance euclidienne)
Voisin plus proches qu'une distance donnée
...

Trouver les meilleures reconstructions

Comme pour la PCA, on minimise $${\color{blue} w}^* = \argmin_{\color{blue} w} MSE(w) = \argmin_{\color{blue} w} \sum_i \| x_i - \hat x_i \|^2$$ Ce qui donne $${\color{blue} w}^* =\argmin_{\color{blue} w} \sum_i \| x_i - \sum_{j \in V_i} {\color{blue} w_{ij}} x_j \|^2 = \argmin_{\color{blue} w} \sum_i \sum_k (x_{ik} - \sum_{j \in V_i} {\color{blue} w_{ij}} x_{jk} )^2 $$

Étape 2 : trouver les représentations

OK, et maintenant ?

On suppose que dans un espace réduit, les points respectent les mêmes relations

On recommence mais dans l'autre sens pour trouver des vecteurs qui "respectent ces contraintes" $${\color{green} y}^* = \argmin_{\color{green} y} MSE({\color{green} y}) = \argmin_{\color{green} y} \sum_i \| {\color{green} y_i} - \sum_{j \in V_i} w_{ij} {\color{green} y_j} \|^2$$ avec ${\color{green} y}\in \RR^d$ ($d$ petite dimension)

avec les contraintes suivantes pour que le problème soit bien posé:

Points centrés $\sum y_i = 0$
Variance unitaire $ \frac 1 N \sum y_i y_i^T = Id$

Locally-linear embedding (LLE) - exemple

Les variantes: LTSA et Hessian LLE

En résumé, LLE

est invariante aux rotations et translations dans un voisinage proche

ne considère pas le processus approximation locale / reconstruction = déformation importante possible

Deux méthodes essaient de corriger ce problème,

LTSA (Local Tangent Space Alignment)
Au lieu de reconstruire les points, on estime quel est l'espace tangent et on les aligne

Zhang, Z. and Zha, H.
2004. Principal Manifolds and Nonlinear Dimensionality Reduction via Tangent Space Alignment.
Hessian LLE
Inspiré par Isomap
Également basé sur l'espace tangent, mais en essayant de préserver les distances (dans la variété)

Exemple

Donoho, D.L. and Grimes, C.
2003. Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data.

Partitionnement spectral

Approches spectrales

Représentation de graphes

Cas de figure

Il n'y a pas de distance bien définie

La seule information disponible sont les arêtes

Impossible d'utiliser les méthodes précédentes

Analyse spectracle des matrices laplaciennes (qui représentent le graphe)

Laplacien du graphe

Matrice d'adjacence

Définie par

$$A_{ij} = \begin{cases} 1 & \mbox{si }i\mbox{ et }j\mbox{ sont lies}\\ 0 & \textrm{sinon} \end{cases} $$

Matrice des degrés

Définie par

$$D_{ij} = \begin{cases} n_i & \mbox{si }i=j\\ 0 & \textrm{sinon} \end{cases}$$

où $n_i$ est le degré du noeud $i$

Laplacien du graphe (2)

Laplacien du graphe

La matrice laplacienne est définie par $L = D - A$ ou (version normalisée) $L = D^{-\frac{1}{2}} (D - A) D^{-\frac{1}{2}} $

Décomposition spectrale des graphes

Décomposition spectrale

On utilise une décomposition en valeurs propres $$ L = Q \Lambda Q^T $$

On utilise le même principe que pour la PCA

On prend les $d$ premières colonnes de Q

Intuition

On a $$ \hat L = \sum_{i} \lambda_i Q_{\bullet i} Q^T_{\bullet i} $$

Pour reproduire au mieux la matrice $L$, il faut que les vecteurs $Q_{\bullet i}$ aient des composantes non nulles pour les noeuds liés

Conclusion

Conclusion sur le partionnement spectral

Il est possible de représenter un graphe / des données pour lesquelles seul l'ordre importe

Complexité numérique (décomposition en valeur propres)

Pas de préservation des distances et/ou relations

t-SNE

Très utilisé pour la visualisation en haute dimension

Comparaison de distribution de probabilités

Au lieu de comparer des distances

on compare deux distributions de probabilité sur les voisins définies sur

le voisinage dans l'espace d'origine
le voisinage dans l'espace projeté

Comparer deux distributions de probabilité

Pour comparer deux distributions de probabilités, il existe de nombreuses mesures (distances statistiques)

Divergence de Kullback-Leibler
Earth mover's distance ou distance de Wasserstein
test de Kolmogorov-Smirnov
...

t-SNE utilise la divergence de Kullback-Leibler

Divergence de Kullback-Leibler

$$KL(p||q) = \sum_{i} p(i) \log \frac{p(i)}{q(i)}$$

Minimiser KL revient à faire en sorte que $p$ "implique" $q$

$\Rightarrow$ lorsque $p$ est non nul, $q$ doit être non nul

Définition de t-SNE

Dans t-SNE,

$P_i$ est la distribution sur le voisinage de $i$ dans les données
Modélisé comme une gaussienne
$Q_i$ est la distribution pour les projections
Loi de Student (2d ou 3d)

t-SNE : estimer p (distribution source)

Similarité des points (source)

Chaque point $x_i$ permet de définir la distribution de probabilité conditionnelle :

$$ p_{j\mid i} \propto \mathcal N\left( x_j; x_i, \sigma_i^2 \right)$$

t-SNE : estimer p (distribution source)

Comment déterminer $\sigma_i$ ?

On fait en sorte de maintenir le maintenir le niveau d'entropie

L'entropie est définie par $$H(P_{.|i})=-\sum_j p_{j\mid i} \log_2 p_{j\mid i}$$

On utilise plutôt la perplexité définie par $2^{H(P_{.|i})}$

$\sigma_i$ fixé de façon à ce que la perplexité $2^{H(P_i)}$ soit égale à une constante prédéfinie

La perplexité $\approx$ nombre de points moyen qui doivent être considérés comme des voisins d'un point quelconque; plus la perplexité est grande, plus le voisinage lointain d'un point sera pris en compte.

Cela permet de s'adapter à la densité du voisinage

t-SNE : estimer p (distribution source)

Symmétrie

En pratique, la distribution utilisée est $$p_{ij}=p_{ji}= \frac{p_{j\mid i}+p_{i\mid j}}{2}$$

Pas de vraie justification théorique (mais marche mieux en pratique)

t-SNE : estimer q (distribution cible dans un espace réduit)

Similarité des points (cible)

La distribution cible $$q_{ij} \propto \mbox{Student}-t(||\px_i - \py_j||^2; 1)$$

La distribution de Student est moins "abrupte" que la distribution normale

Important car on utilise une KL

Distribution de student $\propto (1 + \frac{t^2}{k})^{-\frac{k+1}{2}}$

Perplexité

Effet de la perplexité

sklearn; t-SNE: The effect of various perplexity values on the shape]

Voir aussi l'article de Wattenberg (blog)

Barnes Hut t-SNE

Complexité numérique

Lorsque le nombre de points est grand, l'optimisation est probablématique ($O(n^2)$)

On se limite au voisinage proche

$$p_{j \mid i}=\left\{\begin{array}{rlr} \frac{\exp \left(-d\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right)^{2} / 2 \sigma_{i}^{2}\right)}{\sum_{k \in \mathcal{N}_{i}} \exp \left(-d\left(\mathbf{x}_{i} \mathbf{x}_{k}\right)^{2} / 2 \sigma_{i}^{2}\right)} & \text { si } j \in \mathfrak{N}_{i} \\ 0 & \text { sinon } \end{array}\right.$$

Algorithme de Barnes-Hut:

Construction d'un quadtree,
Traversée du quadtree,
Décision pour le calcul du gradient

van der Maaten, L.

2013. Barnes-Hut-SNE.

Exemples

Voir aussi la démo de Karpathy

Liens

Comparaison des méthodes de projection (sklearn)

Sur MNIST (chiffres manuscripts)
Sur un S en 3D
Sur une sphère tronquée