Dans ce chapitre, nous allons étudier un modèle non supervisé appelé kPCA. Hmm, beaucoup trop de lettres en commun avec PCA pour que ce soit une coïncidence, n’est-ce pas 😛 ?
La lettre supplémentaire "k" désigne ici un objet mathématique appelé kernel (noyau, en français). Nous sommes donc face à un algorithme qui se nomme kernel principal component analysis. L’ajout de ce kernel va nous permettre d’appliquer notre modèle à des données dites non linéaires. C’est ce fameux passage d’un espace euclidien vers une sous-variété dont nous avons parlé dans le chapitre précédent.
Si on reprend l’exemple du chapitre précédent des deux cercles imbriqués :
Ici, appliquer simplement une PCA directement ne pourra pas donner un résultat pratique, puisque la transformation effectuée est linéaire. Pour rappel, l’objectif d’une analyse par composantes principales est de réduire la dimension du jeu de données en conservant un maximum d’informations, c’est-à-dire de variance. En d'autres termes, nous voulons réduire la dimension des données, tout en gardant autant que possible les informations qui permettent de distinguer les observations.
En trouvant les directions qui possèdent le plus de variance des observations, on peut représenter avec quelques axes (2 ou 3) la majorité de la variance globale du jeu de données. Encore une fois, c’est une transformation linéaire que l'on effectue sur les observations.
Ci-dessous, j’ai représenté la première composante principale d’une PCA linéaire appliquée au jeu de données. Pour que vous puissiez mieux comprendre, j’ai mis en orange la seconde classe (celle du petit cercle) de manière artificielle.
Comme on peut le voir, une transformation linéaire sur les composantes principales ne peut clairement pas distinguer les deux classes, car ce qui les sépare n’est pas linéaire. Elle écrase donc la propriété géométrique de cercle du phénomène observé. 😐
On a besoin de changer d’espace et de passer dans un espace non linéaire , dans lequel on pourrait appliquer notre PCA tranquillement. C’est ce qu’on a fait dans la partie précédente justement pour ce problème, en ajoutant la feature . Pour l’exercice, appelons la transformation d’un point dans cet espace hypothétique
Le problème, c’est que souvent cet espace est trop complexe à définir, ou bien même de dimension infinie, et qu’on ne peut donc pas effectuer nos calculs en utilisant (on peut dire qu’il est “intractable”, en anglais, ce qui veut dire qu’il y a très rapidement une explosion du temps de calcul). Du coup, comment faire ? Eh bien nous faisons appel à ce fameux noyau (ou kernel), à l’origine d’une technique très utilisée qui s’appelle le “kernel trick” (astuce du noyau, en français).
Intuition du kernel trick
Notre fonction est trop complexe. Cependant, si on détaille la construction de l’algorithme (ce qu’on ne fera pas ici), on se rend compte qu’on peut formuler notre méthode uniquement à l’aide de produits scalaires de points . Ces produits sont valables dans l’espace euclidien classique. Si on veut effectuer les mêmes calculs sur l’espace de plus petite dimension appelé espace de redescription, ce serait donc sur les produits .
Aussi, l’idée du kernel trick est de laisser tomber la fonction et l’espace de redescription pour s’intéresser au produit à la place. Dans ce cas, on va représenter ce produit par une fonction noyau (ou kernel) .
En faisant quelques calculs sur la matrice de variance-covariance, on peut exprimer la projection d’une observation dans cet espace, en utilisant seulement la matrice .
On aura donc le même genre d’opérations que PCA pour réduire les dimensions, mais en utilisant cette matrice K(x,x) ainsi que les coefficients calculés à partir des valeurs et vecteurs propres de la matrice de variance-covariance C.
Pour en savoir plus sur la formulation de l’algorithme, rendez-vous sur l’article original.
Qu’est-ce que ça donne sur l’exemple plus haut ? Eh bien, si on effectue un kernel PCA avec un kernel gaussien (défini par ), et un =10, on obtient la composante principale suivante :
kpca = KernelPCA(n_components=1, kernel='rbf', gamma=10)
X_spca = kpca.fit_transform(X)
On visualise ci-dessus la composante qui possède le plus de variance dans l’espace dans lequel se trouve le kernel. On peut voir qu’ici la géométrie du modèle a bien été capturée, et qu’on peut bien distinguer les deux classes aisément. Top !
Alors, plusieurs questions se posent :
Comment est défini ce kernel, si on ne connaît même pas ni ?
En fait, il existe plusieurs familles de fonctions kernel pratiques et qui permettent de résoudre la plupart des problèmes. Il faut visualiser ses données, et avoir une petite idée de leur comportement afin de pouvoir prendre une décision. L’idée générale, c’est qu’un kernel doit permettre de représenter la similarité entre les deux points sur lesquels on effectue le produit. On peut même ne pas utiliser de données numériques (par exemple des données textes), tant que cette notion de similarité entre les observations est respectée.
Voici une liste des kernels les plus utilisés :
linéaire – équivalent à une PCA classique ;
polynomial ;
gaussien (RBF) – le noyau gaussien RBF représente le plus usité, dont les cas ci-dessus sont en réalité des cas particuliers ;
laplacien.
Pourquoi ça fonctionne ? Ça paraît un peu facile de ne pas utiliser l’espace final, non ?
Il existe aussi une théorie sous-jacente qui tourne autour de ce qu’on appelle espaces de Hilbert (notamment le théorème de Mercer), qui permet de justifier/vérifier que sous certaines conditions, on peut en effet utiliser un kernel pour y effectuer un plongement, sans tout expliciter. Je vous invite à suivre ce cours si vous êtes intéressé par le sujet.
Quelles sont les limitations?
En réalité, comme je l’ai dit au début, cet algorithme n’est pas le plus utilisé. En effet, un des problèmes principaux des méthodes à noyaux est qu’elles nécessitent le stockage en mémoire de la matrice K(x,y) sur les données afin de pouvoir être utilisées. Comme la taille nécessaire pour le stockage augmente au carré de la taille des données, on peut vite se retrouver avec une utilisation de la mémoire trop importante. Il existe surtout maintenant des algorithmes non supervisés plus efficaces, que l’on va voir dans les prochains chapitres. L’idée ici était d’illustrer ce plongement avec noyau, qui est une notion très importante puisqu’on vit/visualise naturellement dans un espace euclidien.
Le problème : la complexité algorithmique
La bonne nouvelle, c’est que la complexité algorithmique de l’ACP avec noyau ne grandit pas avec la dimension de l’espace de plongement implicite sur lequel on travaille. C’est l’avantage par rapport aux représentations explicites dont on parlait dans le chapitre précédent.
L’ACP possède une complexité algorithmique de , où D représente le nombre de features/dimensions originales. L’ACP avec noyau en revanche, puisqu’on doit travailler avec K(x,y), possède une complexité de , où représente le nombre de points d’observation utilisés. De même, en complexité espace, on est sur puisqu’on conserve toute la matrice K, contrairement à l’ACP classique qui est en
Résumé
Le plongement d’un algorithme linéaire dans une variété non linéaire peut s’effectuer à l’aide du kernel trick.
Les méthodes à noyaux permettent de ne pas avoir à définir la variété dans laquelle on travaille pour appliquer nos algorithmes.
La réduction dimensionnelle non linéaire par kPCA n’est pas la plus utilisée, mais elle illustre la transition entre les méthodes linéaires et non linéaires.
