• 12 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 !

Mis à jour le 31/05/2019

Transformez un problème non-linéaire en un problème linéaire

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

Beaucoup de phénomènes physiques ne sont pas linéaires. Par exemple, la température mensuelle moyenne dans une ville donnée est approximativement périodique en fonction de la saison.

Températures mensuelles (maximales moyennes) sur deux ans pour la ville de Digne-les-Bains.
Températures mensuelles (maximales moyennes) sur deux ans pour la ville de Digne-les-Bains.

Il est donc inévitable que, en machine learning aussi, les modèles linéaires ne suffisent pas toujours à bien appréhender nos données. Mais que faire si l'on n'a à sa disposition que des algorithmes linéaires comme la SVM linéaire ou la régression ridge ?

Prenons l'exemple de classification sur l'image ci-dessous : il s'agit de séparer, en deux dimensions, les points bleus des points orange.

Comment séparer les points bleus des points orange quand on ne connait que des méthodes linéaires ?
Comment séparer les points bleus des points orange quand on ne connait que des méthodes linéaires ?

Il s'agit de séparer les points oranges des points bleus, en deux dimensions. Un modèle linéaire va donc créer une droite comme fonction de décision. Mais on n'aura jamais de bonnes performances avec une droite ! Quelle frontière de décision serait plus appropriée ? Personnellement, je verrais bien un cercle centré à l'origine. Si j'appelle  $\(x_1\)$ et  $\(x_2\)$ mes deux dimensions, un cercle a pour équation $\(x_1^2 + x_2^2 = R^2\)$, où R est son rayon. J'ai donc 1 unique paramètre à déterminer : le rayon R du cercle. Mais ma boite à outils de modèles linéaires ne permet pas de faire ça...

Comment faire? En fait, il me suffit de remarquer que si je crée deux nouvelles variables $\(\phi_1 = x_1^2\)$  et $\(\phi_2 = x_2^2\)$ , alors mon équation devient  $\(\phi_1 + \phi_2 - R^2 = 0\)$ ce qui est une équation... eh oui,  linéaire ! En utilisant une application $\(\Phi\)$  qui a (x1, x2)' associe (x1², x2²)', j'ai décrit mon problème dans un nouvel espace, appelé espace de redescription, défini par les coordonnées  $\((\Phi(x_1), \Phi(x_2))\)$  et dans lequel mon problème est linéaire.

Dans le cas du cercle centré à l'origine, mon espace de redescription fait la même dimension que l'espace dans lequel mes données étaient initialement décrites.

Mais prenons un cas plus général, par exemple celui d'une ellipse (alignée avec les axes). L'ellipse a pour équation  $\(\frac{(x_1-c_1)^2}{a^2} + \frac{(x_2-c_2)^2}{b^2}\)$ . Pour arriver à la décrire dans un espace linéaire, je vais avoir besoin de plus de deux dimensions. Par exemple, je peux prendre $\(\Phi((x_1, x_2)^\top) = (x_1, x_2, x_1^2, x_2^2)^\top\)$  . J'utilise maintenant quatre dimensions. Ce cas de figure ressemble plus à ce que nous rencontrerons en pratique : l'espace de redescription sera de dimension beaucoup plus grande que l'espace initial.

Par exemple, pour apprendre un polynôme de degré d en p dimensions, il faut utiliser comme nouvelles variables tous les monômes de degrés inférieur ou égal à d, c'est-à-dire tous les polynômes de la forme $\(x_1^{d_1} x_2^{d_2} \dots x_p^{d_p}\)$$\(0 \leq d_1, d_2, \dots, d_p\)$  et $\(d_1 + d_2 + \dots + d_p = d\)$.

Étant donné un jeu de données $\(\{x_1, x_2, \dots, x_n\}\)$ étiquetées par $\(\{y_1, y_2, \dots, y_n\}\)$ , je peux maintenant appliquer un algorithme de machine learning linéaire (par exemple, SVM linéaire ou régression ridge) dans l'espace de redescription : je vais apprendre une fonction g linéaire sur les données transformées $\(\{\Phi(x_1), \Phi(x_2), \dots, \Phi(x_n)\}\)$ et leurs étiquettes $\(\{y_1, y_2, \dots, y_n\}\)$ . Ma fonction de décision sera donc  $\(f = g \circ \Phi\)$ : pour faire une prédiction, je commence par calculer l'image $\(\Phi(x)\)$ de x dans l'espace de redescription, puis je lui applique g. La fonction g est linéaire en $\(\Phi(x)\)$ , mais la fonction f n'est pas linéaire.

Ce processus est bien évidemment valable pour un problème de régression comme de classification.

En conclusion

Ainsi, une façon de construire une fonction de décision non-linéaire est de redécrire les données dans un nouvel espace dans lequel on apprend une fonction de décision linéaire. Deux questions se posent maintenant :

  • comment choisir l'application $\(\Phi\)$ et l'espace de redescription ?

  • comment apprendre de manière efficace dans un espace de redescription de dimension potentiellement très grande ?

C'est ce que nous verrons dans le prochain chapitre.

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