Mis à jour le 14/05/2018
  • 10 heures
  • Moyenne

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 !

Gérez le fléau de la dimension

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

Une dernière difficulté dont je veux que vous ayez conscience avant d'aborder votre prochain problème de machine learning est le fléau de la dimension, ou curse of dimensionality en anglais. 

Cette expression désigne une problématique majeure qui apparait souvent en data science, plus précisément lorsqu'on se retrouve avec un grand nombre de features relativement au nombre de d'observations.

Qu'est-ce que le fléau de la dimension ?

À nouveau, reprenons notre exemple maintenant bien connu du modèle 5-NN pour développer une intuition de ce problème.

truc
Modèle 5-NN appliqué  à un jeu de données

En fait, on a ici deux features en entrée qui permettent de prédire la classe rouge ou bleu : la position (x, y), déterminée par les coordonnées x et y sur le graphe.

Si on passe sur un exemple à 3 features, avec le même nombre de données d'entraînement, on obtient par exemple le nuage tridimensionnel ci-dessous :

/// légende ? ///
Jeu de données en 3 dimensions

Si on essaye à nouveau d'effectuer une classification avec un 5-NN sur ce jeu de données, on remarque instinctivement qu'il y a moins de points d'exemple disponibles pour effectuer la prédiction relativement à la taille de l'espace à couvrir. L'algorithme devra donc aller chercher plus loin les 5 plus proches voisins pour effectuer la prédiction.

En fait si on augmente encore le nombre de features, il devient de plus en plus difficile d'avoir assez de données d'entraînement aux alentours pour pouvoir effectuer une prédiction correcte.

Le manque de données nécessaire à l'apprentissage du modèle explose très vite lorsqu'on augmente la dimension des données en entrée, c'est pourquoi on surnomme ce phénomène curse of dimensionality.

Pour visualiser ce phénomène autrement, imaginez que vous devez traiter un problème qui possède N features et chacune peut posséder 10 valeurs différentes. Notre algorithme d'apprentissage doit pouvoir distinguer parmi  $\(10 \times 10 \times ... = 10^N\)$ configurations différentes. On voit rapidement que plus N grandi (la dimension des données), plus un algorithme aura besoin d'exemples pour pouvoir apprendre correctement le phénomène. C'est pour cette raison qu'on dit qu'augmenter la dimension des données d'entrée est un fléau pour le machine learning. 💀

En effet, s'il y a beaucoup de features en entrée qui peuvent prendre beaucoup de valeurs différentes mais qu'en réalité le comportement est facilement généralisable, alors on a besoin de moins d'exemples d'entraînement puisqu'on peut déduire ce qu'il se passe entre les exemples par extrapolation. Il nous faut quand même un algorithme assez intelligent pour comprendre le modèle et effectuer ces généralisations. 😉 

Exemple de complexité plus ou moins importante pour la curse of dimensionality
Exemple de complexité plus ou moins importante

Sur l'exemple ci-dessus, à partir des données d'exemple désignées par des points rouges, on imagine qu'il sera beaucoup plus facile de créer un modèle à gauche, alors qu'à droite il manquera des données pour représenter la seconde bosse (qu'on appelle mode). C'est une complexité qui demande d'avoir plus de données, alors qu'on a le même nombre de dimensions pour les deux graphiques (une seule en l'occurence).

Comment résoudre ce problème ?

Comment faire donc, quand on se retrouve dans une situation ou il y a trop de features par rapport au nombre de données qu'on possède?

Réduire les dimensions

La première solution est bien sûr de réduire le nombre de dimensions des données en entrée. De nombreuses techniques non-supervisées existent pour cela, même si ce n'est pas l'objet de ce cours d'introduction. Il existe deux manières de réduire le nombre de dimensions d'un problème de machine learning :

  • Retrouver les dimensions principales d'un phénomène, qui ne sont pas forcément celles qu'on observe directement mais peuvent être notamment une combinaison linéaire de celles-ci.

  • Retrouver la variété sous-jacente (ou manifold en anglais). Une variété est un objet mathématique qui grossièrement représente une surface topologique de dimension inférieure au problème de grande dimension traité. Ce n'est pas très important de comprendre la théorie liée à ce type de traitement, l'essentiel est de comprendre la différence avec la réduction de dimension linéaire simple (qui est en fait un cas particulier de manifold)

C'est un peu compliqué cette histoire non ?

Effectivement ! L'essentiel, c'est juste de faire la distinction entre un espace qui peut simplement être représenté par ses dimensions principales versus des espaces complexes qui auront besoins d'algorithmes de manifold learning. Il vous faudra bien penser à tester les deux. Ces méthodes seront étudiées plus en détail dans un prochain cours.

http://stats.stackexchange.com/questions/124534/how-to-understand-nonlinear-as-in-nonlinear-dimensionality-reduction
Exemple de stackexchange

Dans le dessin ci-dessus, les données sont représentées par des points. La droite légendée "PCA" représente une réduction linéaire des points par un algorithme appelé PCA (Principal Component Analysis). La courbe représente une réduction non-linéaire effectuée par un algorithme appelé Isomap. Comme on peut le voir ici, une réduction linéaire va écraser les données, alors qu'une réduction non-linéaire va mieux conserver la forme du phénomène qu'on cherche à simplifier. J'ai récupéré l'exemple ci dessus ici.

Choisir le bon algorithme

Pour en revenir au travail de modélisation, votre travail ici consiste à choisir un modèle assez contraint pour pouvoir supporter les variations dimensionnelles sans augmenter en complexité. C'est une balance qui est à trouver.

Par exemple, une régression linéaire contraint le modèle sous forme de droite. Si les données sont linéaires de cette manière, c'est pas mal. Si ce n'est pas le cas, on risque de perdre de l'information importante qui représente le phénomène. Finalement, on se retrouve dans le même genre de dilemme que d'habitude, c'est juste qu'en plus grande dimension, on doit faire encore plus attention à cette sélection. 😀 

En résumé

  • Le fléau de la dimension représente simplement le fait qu'il y a une explosion dans la taille du jeu de données nécessaire à l'apprentissage du modèle lorsqu'on augmente le nombre de features en entrée.

  • De ce fait, on doit choisir avec encore plus d'attention notre modèle, sa complexité et son apprentissage.

  • On peut aussi réduire les dimensions de l'entrée en amont afin de simplifier encore le traitement du problème.

Le mot de la fin 😊

Nous arrivons à la fin du cours ! (Attention, il vous reste encore un quiz...)

J'espère que vous avez maintenant une meilleure idée de ce qu'on peut faire avec le machine learning et comment vous allez pouvoir l'utiliser pour modéliser vos données.

N'hésitez surtout pas à utiliser dès maintenant les librairies et tester des modèles que nous avons pu voir ensemble dans ce premier cours d'initiation. La data science vient avec une pratique régulière, je vous donne seulement les outils et les concepts-clés pour y arriver !

Et j'espère vous retrouver très vite pour de prochains cours d'approfondissement et la découverte de nombreux algorithmes...

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