Algorithme de descente de gradient

mathematics descente de gradient
Temps de lecture : 4 minutes
Share on facebook
Share on twitter
Share on linkedin
Share on email

Beaucoup d’algorithmes de Machine Learning obtiennent de bonnes performances grâce à leur entraînement. Cependant, une grande majorité des entraînements repose sur l’optimisation d’une fonction de perte. Plus sa valeur est petite, meilleurs sont les résultats de l’algorithme. Il existe de nombreux moyens de trouver le minimum (ou maximum) d’une fonction, et l’un des plus connus est celui de l’algorithme de descente du gradient

Une première approche intuitive de cet algorithme a été donnée dans cet article.

Ici, nous allons revenir sur les fondements mathématiques de cet algorithme, l’importance du taux d’apprentissage.

Descente du gradient : Formalisation mathématiques

La descente du gradient est un des nombreux algorithmes dits de descente. La formule générale est la suivante : 

xt+1= xt– η∆xt

où η  le taux d’apprentissage et xt la direction de descente. Cette classe d’algorithme a pour but à chaque itération d’avoir ƒ(xt+1) ≤ ƒ (xt) , avec ƒ une fonction convexe que l’on souhaite minimiser.L’algorithme de descente du gradient décide de suivre comme direction de descente l’opposé du gradient d’une fonction convexe f, ie – Δƒ . Pourquoi ? Le gradient d’une fonction indique sa croissance maximale à partir d’un point. Alors choisir l’opposé revient à prendre la pente la plus abrupte, dans l’objectif de minimiser la valeur de cette fonction.  Voici son fonctionnement :
  1.  Soit un point d’initialisation x0 appartenant au domaine de f
  2. Calculer f(xt)
  3. Mettre à jour les coordonnées : xt+1 = xt– η Δ ƒ (xt )           (*)
  4. Répéter 2 et 3 jusqu’au critère d’arrêt
Généralement, le critère d’arrêt est de la forme xt+1 – ƒxt| ≤ ε , où est très petit. Ce critère semble logique puisqu’on décide d’arrêter quand la différence entre les valeurs de la fonction prise en deux points différents est très peu significative, signe qu’on a convergé. Un critère d’arrêt reconnu dans le machine learning est celui du nombre d’itérations ; on réalise un nombre fini d’optimisation (étape 2 et 3).Deux éléments, à priori négligeables quand on regarde l’algorithme, sont en réalité cruciaux pour le bon fonctionnement de ce dernier ; le point d’initialisation x0 et la valeur du taux d’apprentissage η. Un mauvais point d’initialisation ou un taux d’apprentissage peu adapté peut empêcher l’algorithme de converger vers le minimum. Plus le taux d’apprentissage est élevé, plus on suivra loin la direction indiquée par le gradient. Cela peut nous bloquer dans un minimum local, sur un point-selle où nous faire louper le minimum global. Nous allons étudier à travers un exemple simple  l’impact du taux d’apprentissage sur les performances de la descente de gradient.

Importance du taux d’apprentissage

Prenons le cas d’un exemple simple de régression linéaire. Soit une droite y=w0*x+w1. Nous avons n observations qui suivent une relation linéaire et à l’aide de ces celles-ci, nous allons tenter de trouver les bons paramètres, w0 et w1, qui définissent cette relation. Comme dit précédemment, optimiser un modèle, c’est-à-dire trouver les meilleurs paramètres permettant de bonnes performances, revient à optimiser une fonction de perte. La fonction de perte qui s’impose dans ce genre de situation est la MSE,

gradient
où t représente la tième itération.En calculant le gradient de cette fonction et en appliquant la formule (*), on obtient la formule de mise à jour des paramètres :

wt+1,0 wt+1, 1 = wt,1– ηΔw1L(wt,0, wt,1, X) wt,2 – ηΔw2L(wt,0, wt,1, X)

Au niveau code, cela donne le résultat suivant : 

Faisons varier le taux d’apprentissage pour observer son impact sur les performances du modèle, le tout sur plus de 100 itérations. 

Un petit taux d’apprentissage ?

Prenons un pas volontairement petit de 0.01 pour commencer.  On remarque que le modèle met beaucoup de temps à converger. Après 100 itérations, on voit à peine le modèle approximer les observations. 

On peut d’ailleurs observer sur le troisième graphique que le paramètre w1 varie beaucoup au cours de l’optimisation. Le dernier graphique nous révèle la lenteur de la variation de la fonction de perte vers son minimum global.  Cela est le signe que le taux d’apprentissage est trop petit. Varions-le vers 0.99.

Un grand taux d’apprentissage ?

Analysons graphique par graphique. Le 1er graphique montre une grande instabilité de l’approximation linéaire. On remarque qu’elle au-dessus et en dessous. Cela s’explique par la variation instable et brutale de w1 sur le 3ème graphique, responsable de la « hauteur » de la droite sur le plan. D’où provient cette instabilité ? La réponse se trouve sur le 4ème graphique. 
Le taux élevé fait jouer à la perte une sorte d’effet de ping-pong entre les deux versants sur l’axe de w1 . Cet effet ping-pong ralentit la diminution de la valeur de notre fonction de perte. D’ailleurs sur le second graphique, on voit que la valeur de notre perte reste longtemps élevée au cours des itérations puisqu’elle n’apparaît même pas sur le graphique pendant la moitié du temps. L’intuition nous indique qu’il faudrait le diminuer.  Diminuons donc le taux à 0.7 et observons le résultat. 

Un taux plus adapté

Ce taux d’apprentissage semble être optimal. On remarque sur le dernier graphique que dès la première itération, la valeur de la fonction de perte diminue drastiquement, comme cela est indiqué sur le second graphique. Arrivé au creux de la fonction, l’algorithme se stabilise assez rapidement au minimum vers la dixième époque : le modèle approxime parfaitement les données, la fonction de perte se stabilise en 0, son minimum global, et les paramètres sur le graphique 3 stagnes car optimaux ! 

La complexité du taux d’apprentissage

Nous avons observé que le taux d’apprentissage joue un rôle crucial. S’il est trop élevé, on peut osciller très longtemps autour du minimum, voir le manquer, tandis qu’un taux d’apprentissage trop petit peu mettre beaucoup de temps avant de converger. Un taux même trop élevé peut faire diverger et aller à l’encontre du but voulu, i.e. atteindre le minimum. Le problème est le même pour le point d’initialisation. Deux points d’initialisation peuvent mener à deux résultats différents en fonction de la complexité de la fonction de perte. 

Ici, nous étions dans un modèle simple, avec deux paramètres, ce qui nous a permis de visualiser l’évolution du modèle. Dans les faits, notre modèle comporte bien plus de paramètres, rendant la visualisation impossible. Alors l’ajustement du taux d’apprentissage et le choix du point d’initialisation sont beaucoup plus compliqués dans la réalité. Dans la pratique, il nécessaire d’appliquer à note modèle divers taux d’apprentissage pour observer celui qui apporte les meilleures performances, de même pour le point d’initialisation. 

Cet article vous a plu ? Inscrivez vous à notre Newsletter pour en recevoir d’autres régulièrement ! 

S’abonner
Notifier de
guest
0 Commentaires
Inline Feedbacks
View all comments
text mining de gaulle
📂 Actu et Buzz

Text Mining – Appel du 18 Juin

Qui d’entre vous n’a jamais rêvé d’une analyse de textes automatisée ? Avec le Machine Learning, certaines perspectives auparavant de l’ordre de l’imaginaire sont désormais

Lire plus »
job data science
📂 Business et Data Science

Devenir Data Scientist en 11 semaines

Avec l’émergence des métiers liés à la Data Science et à l’intelligence artificielle, la diversification des postes dans ces domaines rend parfois difficile la compréhension

Lire plus »
Fermer le menu