• 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

Utilisez une ACP avec un noyau

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

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éaire. 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ée en conservant un maximum d’information, 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 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 $\(\omega\)$ , 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 $\(x^2+y^2\)$ . Pour l’exercice, appelons la transformation d’un point dans cet espace hypothétique 

$\[x → \phi(x)\\ x \in R^D → \omega\]$

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 $\(\phi\)$ (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 ? Et 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 $\( \phi\)$ 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 $\(x_i . x_j\)$ . Ce produit est valable 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 $\(\phi(x_i)\phi(x_j)\)$ .

Aussi, l’idée du kernel trick est de laisser tomber la fonction $\(\phi\)$ et l’espace de redescription pour s’intéresser au produit $\(\phi(x) \phi(y)\)$ à la place. Dans ce cas on va représenter ce produit par une fonction noyau (ou kernel) $\(K(x_i,x_j)\)$ .

En faisant quelques calculs sur la matrice de variance-covariance, on peut exprimer la projection d’une observation $\(x_i\)$ dans cet espace en utilisant seulement la matrice $\(K = K[x_i][x_j]\)$ .

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 $\(\alpha\)$ 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 originel.

Qu’est-ce que ça donne sur l’exemple plus haut? Et bien si on effectue une kernel PCA avec un kernel gaussien (défini par $\(K(x,y) = \text{exp}(\frac{-||x - y||^2}{2 \sigma ^2}) = exp(-\gamma ||x - y||^2)\)$ ), et un $\(\gamma\)$ =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 connait même pas $\(\phi\)$ ni $\(\omega\)$ ?

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érique (par exemple des données textes) tant que cette notion de similarité entre les observations est respectée.

Voici une liste des kernel 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 ? Ca parait 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és 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 sont 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ésentation explicites dont on parlait dans le chapitre précédent.

L’ACP possède une complexité algorithmique de $\( O(D^3)\)$ 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(n^3)\)$$\(n^3\)$ représente le nombre de points d’observations utilisé. De même en complexité espace on est sur $\(O(n^2)\)$ puisqu’on conserve toute la matrice K contrairement à l’ACP classique qui est en $\(O(D^2)\)$

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

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