[TUTORIEL] Machine Learning : développez votre première régression linéaire avec la descente de gradient

22 octobre 2020 Modifié le 3 novembre 2020

Coleamment une machine peut-elle apprendre ? Telle est l’une des questions à laquelle nous allons répondre dans cette série d’articles. Vous découvrirez ainsi les principaux algorithmes utilisés en Machine Learning, et ce de manière extrêmement didactique. Pas besoin d’avoir fait un doctorat en informatique et/ou mathématiques pour comprendre leur fonctionnement. Après avoir parcouru ces algorithmes, vous comprendrez mieux comment fonctionne le machine learning, et surtout ce qu’il peut vous apporter.

Régression linéaire et descente de gradient en Machine Learning

Dans cet article, vous allez découvrir l’algorithme le plus simple du Machine Learning : la régression linéaire. Nous en profiterons pour vous expliquer une notion légèrement plus complexe mais surtout utilisée par de nombreux autres algorithmes : la descente de gradient.

Comprendre la notion de Machine Learning

01 décembre
2020

Participez à notre nouvelle série de webinars

Développez vos connaissances #Data & #IA, inscrivez-vous !

Imaginons que nous nous situons dans une forêt composée uniquement d’arbres de la même espèce, tous sont exposés de la même manière aux éléments, tous ont une composition minérale et organique du sol identique…

Bref, ils sont tous identiques à l’exception de leur âge. Certains sont jeunes (le tronc a donc un petit rayon, leur taille est petite également) et d’autres plus âgés (tronc avec un large rayon, grande taille).

Les données disponibles

Nous avons 14 arbres dans cette forêt et avons mesuré pour chacun d’entre eux la taille et le rayon (en cm), puis avons reporté ces résultats dans le tableau suivant.

Nous souhaitons ainsi connaître le rayon d’un 15ème arbre dont on connaît la taille (135 cm), et nous souhaitons également connaître la taille d’un 16ème arbre dont on connaît le rayon (25 cm)…

Régression linéaire et descente de gradient en Machine Learning - Tableau 2

Intérêt

Nous reportons ces mesures dans un graphique et obtenons le nuage de points suivant. Ce sont les valeurs observées.

Régression linéaire et descente de gradient en Machine Learning - valeurs observées

L’être humain y voit tout de suite une relation entre la taille et le rayon. Il pourrait donc facilement dessiner une droite qui relierait au mieux tous ces points.

Régression linéaire et descente de gradient en Machine Learning - relations points

Avec cette droite, nous pourrions connaître le rayon d’un nouvel arbre en mesurant sa taille (et inversement), et ainsi remplir le tableau suivant. On parle ici de valeurs prédites.

Régression linéaire et descente de gradient en Machine Learning - valeurs prédites

Nous allons maintenant voir comment la machine « trouve » cette droite qui relie la taille d’un arbre à son rayon.

Les explications

Régression linéaire et descente de gradient en Machine Learning - Explication

La première chose à comprendre est qu’il existe une infinité de droites possibles, mais laquelle est la meilleure ?

En réalité, c’est très simple, la meilleure droite est celle qui minimise les écarts entre la réalité (les tailles et rayons réellement observés) et les prédictions (les tailles et rayons calculés).

Pour le comprendre, rappelez-vous vos cours de mathématiques, une droite proposant une relation entre 2 variables x et y a pour fonction :

f(x) = a*x + b

a représente la pente, b l’intersection.

Régression linéaire et descente de gradient en Machine Learning - Exemple d'incohérences
Régression linéaire et descente de gradient en Machine Learning - Exemple de lignes cohérentes

La droite rouge est moins bonne que la droite verte, car elle présente des écarts plus importants que l’autre droite.

On va calculer les différences entre la réalité (valeurs observées) et la prédiction (valeurs calculées par les droites).

Régression linéaire et descente de gradient en Machine Learning - Tableau 3

Afin de ne pas annuler les différences, appelées aussi écarts (en additionnant par exemple une différence positive avec une différence négative), nous avons pris le carré de l’écart, puis avons additionné tous ces carrés.

La droite verte présente la somme des carrés des écarts la plus petite (10 069 < 15 671), elle est donc meilleure que la droite rouge.

Pour cet exemple très simple, nous avons comparé 2 droites que nous avons choisies, mais en réalité il y a une infinité de droites. Comment la machine peut-elle trouver la meilleure droite parmi cette infinité de droites, c’est-à-dire celle dont la somme des carrés des écarts à la moyenne est la plus faible ? Il existe pour cela différents moyens.

Moyen 1 : Tester toutes les valeurs possibles pour a et b

Cette méthode n’est pas du tout recommandée (et surtout impossible à utiliser telle quelle dans un véritable environnement), mais elle va nous permettre d’illustrer certains points que l’on utilisera dans la suite de cet article.

En prenant des valeurs aléatoires pour a et b (pour rappel, la fonction est f(x) = a*x + b), on obtient les résultats suivants.

Régression linéaire et descente de gradient en Machine Learning - Tableau Test de valeurs

Avec cette méthode, la somme des écarts au carré la plus petite est égale à 144,51. Cela correspond à « a= 0,19 ; b = 1 ».

La droite ressemble à celle-ci. Elle semble effectivement passer au plus proche des points.

Régression linéaire et descente de gradient en Machine Learning - Exemple de droite au plus proche des points

Pourtant, nous sommes loin d’avoir testé toutes les valeurs de a et de b (ex. la droite ne serait-elle pas meilleure par exemple avec a = 0,195 et b = 1,002 ?), nous ne sommes donc pas sûr qu’il n’existe pas une meilleure droite. C’est pour cela qu’il existe la descente de gradient.

Moyen 2 : Utiliser la descente de gradient aléatoire.

Pour rappel, nous souhaitons que la somme des carrés des erreurs soit la plus petite possible.

Pour continuer l’explication, nous allons non pas prendre la somme mais la moyenne. Cette moyenne est appelée fonction coût.

Elle s’écrit de la manière suivante :

Régression linéaire et descente de gradient en Machine Learning - Fonction coût

m = représente le nombre d’observations, dans notre exemple, le nombre d’arbres, à savoir 14 arbres.

(rem. la littérature divise la fonction coût par 2m et non par m, je choisis ici de diviser par m pour ne pas compliquer l’explication).

Avec nos données d’exemple, qui pour rappel, sont les suivantes, nous aurions la fonction coût suivante :

Régression linéaire et descente de gradient en Machine Learning - Tableau 5

J(a, b) =
          (1/14) *
          [
            (a*184+b-38)^2
            + (a*246+b-45)^2
            + (a*322+b-65)^2
            + (a*257+b-57)^2
            + (a*248+b-46)^2
            + (a*215+b-43)^2
            + (a*173+b-32)^2
            + (a*93+b-17)^2
            + (a*71+b-10)^2
            + (a*52+b-17)^2
            + (a*68+b-13,60)^2
            + (a*60+b-13)^2
            + (a*80+b-18)^2
            + (a*140+b-28)^2
          ]

Ce que l’on souhaite découvrir, c’est le minimum de cette fonction coût, i.e. les valeurs de a et de b permettant de minimiser la fonction coût.

Dans un premier temps, on va simplifier la fonction afin de mieux comprendre la descente de gradient.

La fonction n’est plus « f(x) = a*x + b » mais « f(x) = a*x » (cela signifie que la droite passera obligatoirement par le point {y ; x = 0 ; 0}).

La fonction coût devient alors :

Régression linéaire et descente de gradient en Machine Learning - Fonction coût minimisée

Avec nos données d’exemple, cette fonction coût est la suivante :

J(a) 

= (1/14)*((a*184-38)^2+(a*246-45)^2+(a*322-65)^2+(a*257-57)^2+ (a*248-46)^2+(a*215-43)^2+(a*173-32)^2+(a*93-17)^2+(a*71-10)^2+ (a*52-17)^2+(a*68-13,60)^2+(a*60-13)^2+(a*80-18)^2+(a*140-28)^2)

= (452 381/14)*a^2 – 12867,114*a + 1290,854

En remplaçant a par quelques valeurs aléatoires, on obtient le tableau suivant.

Régression linéaire et descente de gradient en Machine Learning - Tableau 6

Si l’on affiche ces chiffres sur un nuage de points et en dessinant une courbe, nous obtenons le graphique suivant.

Régression linéaire et descente de gradient en Machine Learning - Courbe nuage de points

Visuellement, l’être humain peut trouver la valeur de a qui minimise la fonction coût J(a), dans notre exemple, ça semble être a = 0,2. Mais comment la machine peut-elle trouver cette valeur, et surtout comment peut-elle la trouver de manière plus précise que l’être humain (après tout, visuellement, ça semble être 0,20 mais n’est-ce pas plutôt 0.199, 0.201, 0.20001… etc. ?) ?

Pour cela, on va utiliser la dérivée. Pour rappel, la dérivée mesure la pente d’un point située sur une courbe.

Régression linéaire et descente de gradient en Machine Learning - Dérivée
Régression linéaire et descente de gradient en Machine Learning - Dérivée positive / négative

La descente de gradient aléatoire est une suite d’opérations que voici.

Etape a. La machine choisit aléatoirement un nombre pour a.

  Exemple : a = -758

Etape b. La machine calcule la dérivée afin de savoir si elle est à gauche ou à droite du point minimum.

Régression linéaire et descente de gradient en Machine Learning - Calcul de la dérivée
Régression linéaire et descente de gradient en Machine Learning - Tableau 7

La dérivée de « a = -758 » est négative, cela signifie que la pente descend, on se situe à gauche du minimum.

On peut donc continuer et proposer un « a » plus grand que « -758 ».

Étape c. La machine propose aléatoirement un nouveau chiffre plus grand que « -758 ».

Exemple : a = -432

Étape d. La machine calcule la dérivée afin de savoir si elle est à gauche ou à droite du point minimum.

Régression linéaire et descente de gradient en Machine Learning - Tableau 8

La dérivée de « a = -432 » est toujours négative, cela signifie que la pente descend, on se situe à gauche du minimum.

On peut donc continuer et proposer un a plus grand que « -432 ».

Étape e. La machine propose aléatoirement un nouveau chiffre plus grand que « -432 ».

Exemple : a = 23

Étape f. La machine calcule la dérivée afin de savoir si elle est à gauche ou à droite du point minimum.

Régression linéaire et descente de gradient en Machine Learning - Tableau 9

La dérivée de « a = 23 » est positive, cela signifie que la pente monte, on se situe à droite du minimum.

On peut donc continuer et proposer un a situé entre « -432 » et « 23 ».

Etape … n. La machine se stabilise et trouve la valeur de a permettant de minimiser la fonction de coût.

Cette méthode fonctionne mais peut prendre beaucoup de temps et nécessite de nombreux calculs, on va donc voir comment gagner du temps et minimiser le nombre de calculs à effectuer.

Moyen 3 : Utiliser la descente de gradient « optimisée »

Plutôt que proposer aléatoirement à chacune des étapes une nouvelle valeur pour a, on va soustraire à a un certain pourcentage de la dérivée calculée à l’étape précédente, pourcentage que l’on appelle « learning rate ». Cette technique est appelée communément la descente de gradient. Rassurez-vous, avec quelques exemples, ça vous semblera bien plus facile.

Etape a. Comme précédemment, la machine choisit aléatoirement un nombre pour a, c’est la seule étape ou un chiffre aléatoire va être utilisé.

Exemple : a = -758

Etape b. Comme précédemment, la machine calcule la dérivée afin de voir si celle-ci est extrêmement proche de 0 ou non.

a = -758
Dérivée de J(a) par rapport à a = (452381 / 7) * a – 12 867,114 = (452381 / 7) * (-758) – 12 867,114 = – 48999266,83

La dérivée n’est pas du tout proche de 0, une nouvelle valeur de a doit être trouvée.

Etape c. La nouvelle valeur de a est calculée de la manière suivante :

« Nouveau a » = « Ancien a » – « learning_rate » * « Dérivée »

Pour cet article, le « learning_rate » (taux d’apprentissage) sera égal à 0,00001 (en règle générale, il est égal à 0,01 et son identification fait l’objet de méthodes spécifiques que nous n’aborderons pas dans cet article). Quoi qu’il en soit, il sera pour cet article constant et égal à 0,00001.

Cela donne donc :
« Nouveau a » = -758 – (0,00001 * -48999266,83) = -268,0073317

Etape d., e. … n. La machine recommence indéfiniment jusqu’à ce :
– la « dérivée de J(a) par rapport à a » soit très proche de 0 (tende vers 0)
– la valeur de a se stabilise (ne change presque plus entre chaque itération)

Sous forme de tableaux, voici ce que cela donne.

Tableau - Utiliser la descente de gradient optimisé

Au bout de la 24° étape, la valeur de a se stabilise et est égale à 0,199102.

Moyen 4 : Utiliser la descente de gradient « optimisée » pour trouver, cette fois, a et b

Nous allons enfin voir dans cette dernière partie comment utiliser la descente de gradient optimisée à la fois à a et à b.

Le fonctionnement est à peu près identique.

Afin de simplifier les calculs, nous allons prendre les valeurs suivantes.

Tableau - Utiliser la descente de gradient stochastique pour trouver a et b

L’objectif reste identique, trouver le rayon d’un arbre dont la taille est de 7 cm et la taille d’un arbre dont le rayon est de 6 cm.

Il faut seulement comprendre que l’ajout d’une nouvelle variable, en l’occurrence b, transforme notre fonction coût en un graphique en 3D dimensions.

En 3 dimensions, une fonction coût pourrait se présenter sous cette forme.

Graphique en 3D - Utiliser la descente de gradient stochastique pour trouver a et b
Graphique en 3D - Utiliser la descente de gradient stochastique pour trouver a et b

L’objectif reste donc le même, quelles sont les valeurs respectives de a et de b permettant de minimiser la fonction coût.

Descente de gradient optimisé - Minimiser la fonction coût
Descente de gradient optimisé - Graphique 2 Minimiser la fonction coût

Pour cela, on va une nouvelle fois utiliser la descente de gradient optimisée.

Voici la fonction coût après introduction de la variable b.

J(a,b) = (3 – (a*1+b))^2 + (4,5 – (a*4+b))^2 +  (7 – (a*6+b))^2

Cette fois, nous allons calculer deux dérivées :

Descente de gradient optimisé - Calcul de la dérivée

Comme précédemment, nous allons procéder par une succession d’étapes itératives jusqu’à ce que les valeurs de a et b se stabilisent. Des valeurs de a et de b stabilisées signifieraient :

  • des dérivées très proches de 0 (i.e. horizontales)
Descente de gradient optimisé - Second Calcul de la dérivée

Etape c.

On analyse les résultats et on prend une décision.

Les 2 dérivées ne sont pas du tout proches de 0, on continue donc.

Descente de gradient optimisé - Calcul de la valeur de j

Etape d.

Comme précédemment, on va utiliser un learning rate afin de calculer les 2 nouvelles valeurs de a et de b.

Learning rate = 0,001

  “Nouveau a
  = “Ancien a” – “Learning rate” * “Dérivée de J(a,b) par rapport à a
  = 10 – 0,001 * 1198
  = 8,802

  “Nouveau b
  = “Ancien b” – “Learning rate” * “Dérivée de J(a,b) par rapport à b
  = 12 – 0,001 * 263
  = 11,737

Etape e.

On recommence.

La machine calcule les dérivées de J(a,b) par rapport à a et à b

Descente de gradient optimisé - Calcul derivée 3

Etape f.

On analyse les résultats et on prend une décision.

Les 2 dérivées ne sont pas du tout proches de 0, on continue donc.

Etape … n :

On recommence jusqu’à ce que les valeurs de a et de b se stabilisent.

Sous forme de tableaux, voici les résultats obtenus à chacune des étapes.

Descente de gradient optimisé - Résultats

On voit qu’à partir de la 2000° étape, les valeurs se sont bien stabilisées.
  a ≃ 0,6724…
  b ≃ 2,4812… 

Descente de gradient optimisé - Tableau de relations taille / rayon

Notre relation entre taille et rayon est donc la suivante :

Descente de gradient optimisé - Calcul taille / rayon

 Nous pouvons ainsi calculer les valeurs manquantes.

Descente de gradient optimisé - Tableau 2 taille / rayon

  Le rayon de l’arbre A4

  = 0,6724 * 7 + 2,4812
  = 7,188

  La taille de l’arbre A5

  = (6 – 2,4812) / 0,6724
  = 5,233

Et voilà ! Vous venez de découvrir la descente de gradient optimisée appliquée à une régression linéaire simple (i.e. f(x) = a*x + b). Dans de prochains articles, nous décortiquerons d’autres algorithmes…

Kévin VANCAPPEL
Kévin VANCAPPEL Consultant Senior
Business & Decision

Je suis tout particulièrement intéressé par l'innovation technologique au service de l'expérience d'achat.

En savoir plus

Laissez un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Votre adresse de messagerie est uniquement utilisée par Business & Decision, responsable de traitement, aux fins de traitement de votre demande et d’envoi de toute communication de Business & Decision en relation avec votre demande uniquement. En savoir plus sur la gestion de vos données et vos droits.