• 15 heures
  • Difficile

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 01/02/2019

Découvrez la réduction dimensionnelle non-linéaire

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

Bienvenue dans cette seconde partie sur l’apprentissage non-supervisé ! Une notion centrale sera présente dans cette section : la non-linéarité. J’avais déjà brossé le sujet dans le cours d’initiation au machine learning, mais l’idée ici est de renforcer la compréhension de cette notion afin de pouvoir aborder sereinement les différentes méthodes que nous explorerons par la suite, et que vous utiliserez au quotidien dans votre travail de data scientist.

Notion de non-linéarité

Imaginons que l’on se retrouve face à un problème de classification de la forme suivante :

Pas de problème ici pour séparer les deux nuages de données par un hyperplan (une droite en l’occurence) et donc classer facilement nos points. Prenons un autre exemple de classification :

Mmh, plus compliqué de séparer par une droite n’est-ce pas ? 😛

On peut observer de la même manière des régressions linéaires (on peut modéliser par une droite) vs non-linéaire

Vous vous en doutez, les problèmes rencontrés par les data scientists dans la vie réelle sont en général non linéaires. Comment traiter ce type de comportement ?

Résoudre des problèmes non-linéaires

Il existe globalement deux manières d’aborder le sujet : de manière explicite ou de manière implicite.

La manière explicite

Traiter un problème non-linéaire de manière explicite signifie que l’on va créer des nouvelles features “à la main”, pour ensuite les utiliser dans des algorithmes linéaires. Ces features prennent en compte le comportement non-linéaire des données et “l’annulent” en quelques sorte, en augmentant la dimension du problème.

Par exemple, imaginez que vous voyez un jeu de données de points $\(x = (x_1, x_2)\)$ qui ressemble à ça :

 

On pourrait ici se dire que le comportement a l’air polynomial, c'est à dire que les points d'observation se situent autour d'une courbe avec une équation de type $\(y=a_n*x^n+a_{n-1}*x^{n-1}+\cdots+a_1*x+a_0\)$ , et l'on peut donc créer des features supplémentaires en conséquences, c’est à dire augmenter chaque point avec de nouvelles caractéristique :

 $\(x \rightarrow z = (x,x^2,x^3,x^4,x^5)\)$

x_augmented = np.array([x, x**2, x**3, x**4, x**5]).T

On peut ensuite effectuer une régression linéaire classique sur ce nouveau jeu de données de points z, qu'on affiche ensuite :

regr = linear_model.LinearRegression()
regr.fit(x_augmented, y)

plt.plot(x_augmented[:,0], y, 'o', color='black', markersize=2)
plt.plot(x_augmented[:,0], regr.predict(x_augmented), '-', color='orange')
plt.axis('off')
plt.show()

En orange est représenté le résultat de notre régression linéaire. Plutôt pas mal !

Là, j’ai présenté un modèle unidimensionel donc tout va bien. Mais si je suis dans un modèle multidimensionel, disons de 10 dimensions par exemple (donc avec 10 features), et que je souhaite utiliser les features quadratiques (c'est-à-dire x²,x³,x⁴,... comme précédemment), j’aurais au minimum 10 x P features supplémentaires (où P est le nombre de degré polynomiaux dont j’ai besoin). Imaginez aussi que je souhaite connaître les interactions entre les différentes variables ( $\(x_1, x_2, x_3, x_4\)$ , etc) on explose facilement notre nombre de features ! Heureusement pour nous, il existe des méthodes pour ne pas avoir à calculer explicitement toutes ces features, on voit ça dans la partie suivante 😉

 Prenons un autre exemple, de classification cette fois, avec un jeu de données $\((x_1,x_2)\)$

Si on imagine que l’on veut séparer les deux cercles ci-dessus, on peut naturellement créer la feature $\((x_1,x_2) \rightarrow (x_1, x_2, x_1^2 + x_2^2)\)$ car l'équation d'un cercle (centré en (0,0) est $\(x^2+y^2=Constante\)$ ).

X_augmented = np.array([X[:,0], X[:,1], X[:,0]**2 + X[:,1]**2).T

Dans ce nouvel espace de dimension 3, on peut représenter notre jeu de données qui devient alors linéairement séparable (j’ai volontairement ajouté la couleur orange pour distinguer les deux cercles) :

On peut maintenant facilement imaginer un hyperplan qui sépare les deux classes.

La manière implicite

Bien, maintenant que l’on a vu les méthodes explicites, qui sont plus souvent utilisées dans un cadre supervisé d’ailleurs, on peut passer aux méthodes implicites. Comme évoqué plus haut, un ensemble de méthodes existent pour traiter les données au comportement non linéaire directement.

C’est notamment le cas des méthodes de noyaux (ou kernel methods), qui permettent de transformer certains algorithmes linéaires (telle que l’analyse par composante principale) en algorithmes non linéaires, sans avoir besoin d’effectuer des calculs dans cet espace de dimension supérieure. On va détailler un peu plus comment ça fonctionne dans le chapitre suivant.

Dans le cadre de la réduction dimensionnelle

Dans la partie précédente, vous avez pu utiliser un algorithme très classique de réduction dimensionnelle appelé Analyse par Composantes Principales. Son objectif est de déterminer les directions dans lesquelles notre jeu de données possède le plus de variance et de “projeter” linéairement les données dans ces directions là (en général pas plus de 3 dimensions). Cette projection nous permet de mieux visualiser le comportement du phénomène observé.

Cette méthode est très efficace, je vous conseille d’en faire fréquemment lors de votre analyse exploratoire. Deux choses à noter cependant :

  • C’est le comportement global du phénomène qu’on observe car on travaille sur la matrice de variance-covariance de tout le jeu de données directement.

  • C’est une projection (plongement) linéaire (on transforme les données seulement par des opérations de la forme AX + b).

Plongement non-linéaire

On peut généraliser cette notion de factorisation de matrice (dont l’ACP fait partie) pour gérer des données qui réside sur une sous-variété non-linéaire (et non pas un sous-espace).

Hmm… Tu as déjà évoqué la notion de variété, mais ça me parait un peu ésotérique comme notion…

Bien que la notion de variété géométrique (ou manifold en anglais) en mathématique soit assez rigoureuse, elle est utilisée en machine learning un peu plus librement pour désigner des espaces plus généraux que les espaces euclidiens, dans lequel se trouve notre phénomène.

Bouteille de Klein
Bouteille de Klein

Cette bouteille de Klein est un objet en 3 dimensions, mais sa surface est elle, en 2 dimensions. Supposons que nous ayions des données à 3 dimensions. On peut les représenter par des points dans cet espace à 3 dimension. Supposons en plus que tous ces points soient situés sur la surface de la bouteille de Klein. On peut alors dérouler (ou aplatir) la surface de cette bouteille. Une fois la surface applatie, on se retrouvera avec les points qui pourront être décrits en 2 dimensions au lieu de 3 originellement. L'action de dérouler la bouteille est une tranformation. Plus tart, on appelera cette transformation fonction $\(\Phi\)$ . Très souvent, l'action de dérouler sera très complexe (imaginez-vous dérouler cette bouteille qui a une forme tellement bizare !), comme nous le verrons au chapitre suivant.

Cette notion sera plus facile à appréhender pour vous avec la pratique.

Ok donc pour reprendre, pourquoi tu parles de variété déjà ?

Comme je le disais plus haut, l’idée est de généraliser des algorithmes qui travaillent dans des espaces euclidiens pour passer sur des variétés, donc des espaces non-linéaires.

Dans le contexte de l’apprentissage non-supervisé, l’objectif est de trouver une variété de dimension (bien) inférieure à la dimension originelle dans laquelle se trouvent les données. On l'appelle Espace de Redéfinition. On peut ainsi représenter nos données plus facilement ou les simplifier en terme de feature représentatives, prédire en parcourant ce manifold… de manière beaucoup plus simple.

De manière un peu plus formelle, on a nos points de départs $\(X = [x_1, x_2, x_3, ..., x_N]\)$ où chaque point est de dimension P et on essaie de trouver une application : X → Y, où $\(Y = [y_1, y_2, ... , y_N]\)$ sont des points qui approximent X dans un espace de dimension bien inférieur. Par exemple, de dimension 2 pour une visualisation

Global vs Local

Dans cet ensemble de méthodes de réduction dimensionnelles non-linéaires, on peut encore séparer les algorithmes en deux catégories : ceux qui travaillent sur la structure globale vs ceux qui se concentrent sur la structure locale.

Hmm, je pense qu’intuitivement je comprends ce que ça veut dire mais concrètement ?

Concrètement, les méthodes s’intéressant à la structure globale s’intéressent aux paires de distances entre les points et les considère comme toutes équivalentes alors que les méthodes s’intéressant à la structure locale vont pondérer les paires de distances (relativement) proches avec plus d’importance.

Résumé

  • Les données non-linéaires sont abordables de manière explicites en effectuant directement un feature engineering sur les observations de départ, ou bien de manière implicite en utilisant des méthodes spécifiques à la non-linéarité. On retrouvera parmi ces méthodes les méthodes à noyaux et les méthodes à plongement dans des variété.

  • Les données à grandes dimensions reposent souvent sur une variété non-linéaire de dimension bien inférieure (ou bien sont proches de celle-ci).

  • Les méthodes de réduction dimensionnelles non linéaires que nous allons étudier permettent ainsi de retrouver une approximation de ces variété et de bien mieux représenter ces données dessus.

  • On s’intéresse aux informations liées à la structure du phénomène représenté, mais c’est parfois suffisant de n'observer que les paires de distances entre les points dans l’espace original. C’est le cas d’une partie des méthodes que nous allons étudier.

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