Méthodes de réduction spectrales

Section 4.4 Méthodes de réduction spectrales

On va détailler dans cette section la dernière famille d’apprentissage de variété. On parle de méthodes spectrales, car elles sont basées sur l’analyse d’un opérateur différentiel (enfin sa discrétisation) associé à la variété.

Subsection 4.4.1 Méthode EigenMaps

La méthode centrale de cette approche s’appelle la méthode EigenMaps. On considère donc \(\mathcal{M}\) une variété riemannienne. On rappelle comme précédemment que notre objectif de trouver un représentant dans \(\mathbb{R}^{m}\) de chaque point \(x\in \mathcal{M}\subset\mathbb{R}^d\) ce qui revient d’un certain point de vue a déterminer une carte locale associée à notre variété. Soit une carte locale

\begin{equation*} y=\phi_x(x), y\in \mathbb{R}^m, \quad x\in U_x \subset\mathcal{M} \end{equation*}

On considère que ces cartes locales \(\phi_x=[\phi_1(x),...,\phi_d(x)]\) sont linéaires ou proches. On nomme \(\phi\) la fonction \(y=f(x)\) globale (que l’ont suppose deux fois différentiables) qui va approcher nos cartes locales. L’idée fondamentale comme précédemment est de préserver les distances. Si deux points sont proches sur la variété, on veut que leurs coordonnées locales restent proches dans \(\mathbb{R}^m\text{.}\) Cest une propriété raisonnable a attendre des cartes locales sur une variété régulière. On souhaite donc que:

\begin{equation*} \parallel f(x_1) - f(x_2)\parallel_2 \approx d_{\mathcal{M}}(x_1,x_2), \quad \forall (x_1,x_2)\in \mathcal{M} \subset \mathbb{R}^d \end{equation*}

On rappelle que le gradient \(\nabla f\) est un élément de l’espace tangent \(T_x \mathcal{M}\text{,}\) tel que pour \(\forall v\in T_x \mathcal{M}\) on est \(f(v)= g_x(\nabla f(x), v)\) avec \(g_x\) la métrique riemannienne. On définit \(\gamma(t)\) la courbe géodésique avec \(\gamma(0)=x_1\) et \(\gamma(l)=x_2\) paramétrisée par la longueur \(l\text{.}\) On rappelle que \(\dot{\gamma}(t)\) est un vecteur tangent à \(\gamma(t)\text{.}\) On utilise tout cela pour avoir:

\begin{equation*} f(x_2) = f(x_1) + \int_0^l df(\dot{c}(t))dt = f(x_1) + \int_0^l g_{x_1}(\nabla f(\gamma(t)),\dot{\gamma}(t) )dt \end{equation*}

On utilise la correspondance de la métrique avec le produit scalaire dans l’espace tangent. Puis on utilise Cauchy-Schwartz pour obtenir

\begin{equation*} g_{x_1}(\nabla f(\gamma(t)),\dot{\gamma}(t)) = \langle \nabla f(\gamma(t)),\dot{\gamma}(t)\rangle_{T_x \mathcal{M}} \leq \parallel\nabla f(\gamma(t)) \parallel_2 \parallel \dot{\gamma}(t) \parallel_2 \end{equation*}

Puisque la courbe géodésique est de longueur \(l\) alors \(\parallel \dot{\gamma}(t) \parallel_2 =l\) et donc par un développement de Taylor dans l’espace tangent on obtient

\begin{equation*} g_{x_1}(\nabla f(\gamma(t)),\dot{\gamma}(t))= \parallel\nabla f(\gamma(t)) \parallel_2 \approx \parallel\nabla f(x_1) \parallel_2 + o(l) \end{equation*}

et donc

\begin{equation*} \parallel f(x_1) - f(x_2)\parallel_2 \leq l \parallel\nabla f(x_1) \parallel_2 + o(l) \end{equation*}

ce qui est équivalent à

\begin{equation*} \parallel f(x_1) - f(x_2)\parallel_2 \leq d_{\mathcal{M}}(x_1,x_2) \parallel\nabla f(x_1) \parallel_2 + o(d_{\mathcal{M}}(x_1,x_2)) \end{equation*}

On voit donc que \(\parallel\nabla f(x_1) \parallel_2 \) donne une estimation d’à quel point la transformation préserve les distances/voisinages.

le calcul formel précédent montre que si on veut que \(f\) soit une isométrie entre la variété (avec sa distance géodésique associée) et l’espace \(\mathbb{R}^m\) il faut alors construire un plongement tel que le gradient de ce plongement soit petit. On cherche dnc une transformation \(f\) tel que

\begin{equation*} \underset{\parallel f\parallel_{L^2(\mathcal{M})}=1}{\operatorname{argmin}} \int_{\mathcal{M}} \parallel\nabla f(x) \parallel_2^2 dx \end{equation*}

Cela revient à

\begin{equation*} \underset{\parallel f\parallel_{L^2(\mathcal{M})}=1}{\operatorname{argmin}} \int_{\mathcal{M}} \Delta_{\mathcal{M}}f f dx \end{equation*}

avec \(\Delta_{\mathcal{M}}\) l’opérateur de Laplace Beltrami associé à la variété. Lorsqu’on on ordonne les valeurs propres de façon croissante pour le Laplacian comme pour l’opérateur de Laplace -Beltrami cela revient a ordonner les vecteurs propres du mode le moins oscillant sur la variété aux modes les plus oscillants. Les vecteurs propres de l’opérateur de Laplace Beltrami comme la base de Fourier associée à la variété.

Figure 4.29. Ici on affiche les premières harmoniques du Laplace Beltrami sur la sphère.

Les premiers vecteurs correspondent donc aux fonctions les plus régulières, les moins oscillantes sur la variété. En prenant comme transformation \(f(x)\) une combinaison linéaire des \(d\) premières fonctions propres (sauf celui associé à valeur propre \(\lambda_0\) qui correspond aux fonctions constantes sur la variété et donc qui enverrait tous les points de la variété sur un seul point), on peut assurer une transformation aussi régulière que possible et donc que \(\int_{\mathcal{M}} \parallel\nabla f(x) \parallel_2^2 dx\) soit faible et donc répond à notre objectif. Le principe de la méthode Eigenmaps est de calculer une approximation des fonctions propres associées à l’opérateur de Laplace-Beltrami sur la variété et de projeter sur les premières fonctions propres. Pour cela on va établir une théorie similaire à celle de Laplace-Beltrami, mais sur des graphes en montrer comment les deux sont connectés.

Subsection 4.4.2 Algorithme et limite de la méthode

Ce résultat justifie l’approche précédente (il existe une façon de le faire en utilisant des arguments discret) puisque si nos points sont portés par une variété le Laplacien sur graphe converge vers l’opérateur de Laplace Beltrami et donc les vecteurs propres du Laplacien sur graphe convergent vers ceux de Laplace Beltrami. En projetant sur cette base on peut espérer trouver une transformation qui minimise le gradient au sens de la variété. On en déduit l’algorithme suivant:

Pour la méthode Eigenmaps on utilise en général une autre approche pour calculer la matrice du Laplacien que directement le graphe des plus proches voisins. L’idée est d’utiliser le lien entre l’équation de la chaleur sur une variété et l’opérateur de Laplce Beltrami. Puisque l’opérateur \(\Delta \) et un opérateur autoadjoint positif on peut écrire un semi-groupe

\begin{equation*} A_t = e^{-t \Delta } \end{equation*}

L’action de ce semi-groupe peut s’écrire avec un noyau de green:

\begin{equation*} A_t f= \int_{\mathcal{M}} G_t(x,y)f(y)dy \end{equation*}

On va pas rentrer dans les détails, mais noyau de Green peut s’approcher par

\begin{equation*} G_t(x,y)=\frac{1}{(4\pi t)^{\frac{d}{2}}}e^{\frac{\parallel x-y\parallel_2^2}{4t}} \end{equation*}

On sait que \(A_t=e^{-t \Delta}\text{,}\) par un développement limité très formel autour de zéro on voit que

\begin{equation*} \Delta f\approx \underset{t\rightarrow 0}{\operatorname{lim}}\frac{I_d - A_t}{t}= \frac{1}{t}\left(f(x)-\frac{1}{(4\pi t)^{\frac{d}{2}}}\int_{\mathcal{M}}e^{\frac{\parallel x-y\parallel_2^2}{4t}}f(y)dy\right) \end{equation*}

Maintenant on va discretiser cette formule sur un certains nombres de points \(x_i\) puis observer que si on définit les poids et le degré de la manière suivante

\begin{equation} d_i=\sum_{x_j\in O_i} e^{\frac{\parallel x_i-x_j\parallel_2^2}{4t}}\tag{4.12} \end{equation}

\begin{equation} w_{ij}= e^{\frac{\parallel x_i-x_j\parallel_2^2}{4t}}, \quad \mbox{si }x_j\in O_i \mbox{ et sinon } w_{ij}=0\tag{4.13} \end{equation}

avec \(O_i\) un ensemble de voisins de \(x_i\text{,}\) c’est exactement équivalent à \(\Delta f =(D-W)f\text{.}\) On va donc construire notre matrice du Laplacien en suivant ses définitions. On obtient l’algorithme suivant.

Algorithm 4.30. Algorithme Eigenmaps.

On calcule le graphe des plus proches voisins au sens du rayon,
On calcule les matrices de degré \(D\) et de poids \(W\) (symétrisée) avec les définitions (4.12), (4.13),
On calcule la matrice de Laplacien sur le graphe,
On calcule les \(m\) premiers vecteurs propres,
On obtient à chaque point du graphe \(i\) un vecteur de taille \(m\) avec les ième composantes de chaque vecteur.

Figure 4.31. On compare les resultats données par Eigenmaps sur une sous variété 2D de \(\mathbb{R}^3\) plongé en 2D. On utilise 2000 points et on fait variété le nombre de voisins dans l’algorithme de graphe. 5 en haut, 20 au milieu et 50 en bas. On peut retrouver le notebook ici ³.

Sur la figure Figure 4.31 on voit que la méthode Eigenmaps donne des résultats correct, mais moins bon que la méthode ISOMAP par exemple (qui est cependant beaucoup plus coûteuse). En effet elle a tendance a concentrer les points sur une courbe (en dimension 1) plutôt que sur un plan alors qu’on fait une projection dans \(\mathbb{R}^2\text{.}\) Comme pour eigenmaps la qualité dépend aussi du nombre de voisins choisis.

Subsection 4.4.3 Limite de la méthode

Figure 4.32. On compare les resultats données par Eigenmaps sur une sous variété 2D de \(\mathbb{R}^3\) plongé en 2D. On utilise 1500 points et On projette par rapport à différent vecteurs propres. On peut retrouver le notebook ici ⁴.

Sur la figure Figure 4.32 on compare les projections en dimension 2D de la sphère avec différents vecteurs propres. Comme attenu on voit que la projection sur le couple \((1,0)\) ne marche pas. Le vecteur \(0\) étant la fonction propre constante sur la variété on s’y attendait. La meilleur projection (celle qui semble le mieux conserver les voisinages) semble etre la projection \((1,2)\) qui aux deux premières fonctions propres associés à des valeurs propres non nulles.

Figure 4.33. On compare les resultats données par Eigenmaps sur une sous variété 2D de \(\mathbb{R}^3\) plongé en 2D. On utilise 1500 points et On projette par rapport à différent vecteurs propres. On peut retrouver le notebook ici ⁵.

Sur la figure Figure 4.33 on compare les projections en dimension 2D deux sphères avec différents vecteurs propres. On a donc deux composantes connexes. On voit que toute les projections permettent de préserver cela (on utilise d’alleurs cette méthode pour du clutsering). Comme précedemment La meilleur projection semble etre la projection \((1,2)\) comme attendu.

Figure 4.34. On compare les resultats données par Eigenmaps sur une sous variété 2D de \(\mathbb{R}^3\) plongé en 2D. On utilise 1500 points et On projette par rapport à différent vecteurs propres. On peut retrouver le notebook ici ⁶.

Sur la figure Figure 4.34 on compare les projections en dimension 2D de la courbe en forme de S avec différents vecteurs propres. Ici les résultats sont différents. On voit bien que la projection sur les premières fonctions propres conservent bien les voisinages locaux mais concentre la variété sur une ligne. Il faut utiliser la projection sur les fonctions propres \((1,5)\) pour obtenir un bon résultat qui en plus préserve l’aspect 2d de la variété. Bien que le résultats avec la projection classique \((1,2)\) soit satisfaisant cela ne semble pas être les meilleurs.

On retrouve donc le phénomène de concentration de la variété lors de la projection. Cependant on voit que si on prend des vecteurs propres un peu plus grands on peut parfois remédier partiellement à cela. En faite se phénomène se comprend très bien sûr le cas d’un plan. Si on prend un carré et qu’on calcul ces deux vecteurs premiers vecteurs propres on va projeter notre fonction sur:

\begin{equation*} sin\left(\frac{2\pi}{L} x\right), \quad sin\left(\frac{2\pi}{L} y\right) \end{equation*}

car il s’agit des modes associés aux plus basses fréquences \(\frac{2\pi}{L}\text{.}\) Maintenant supposons que l’on considère un rectangle de longueur \(L_x\) 3 fois plus grande que la largeur \(L_y\) alors les deux plus basses fréquences vont être \(\frac{2\pi}{L_x}\) et \(\frac{4\pi}{L_x}\) et donc les premiers vecteurs propres sont:

\begin{equation*} sin\left(\frac{4\pi}{L_x} x\right), \quad sin\left(\frac{4\pi}{L_x} x\right) \end{equation*}

on va donc projeter nos données sur deux fonctions propres dépendante de \(x\) et indépendante de \(y\text{.}\) Cela va faireperdre l’aspect 2D de la variété lors de la projection. Pour éviter cela il faudrait prendre le premier vecteur propre selon \(y\text{.}\) A priori la méthode standard EigenMaps ne permet pas cela car il n’est pas évident de l’identifier sans connaitre la variété cible.

Subsection 4.4.4 Variantes de la méthode

Prev Top Next