Gradient descent ou algorithme du gradient est un processus itératif qui permet de calculer le minimum d’une fonction. Cet algorithme est beaucoup utilisé en Machine Learning.
Dans cet article, nous présenterons l’algorithme du gradient, comment il fonctionne et un exemple pratique.
Qu’est-ce que le gradient descent ?
Le gradient descent est un algorithme d’optimisation qui permet de calculer le minimum local d’une fonction (convexe) en changeant au fur et à mesure (itérations) les paramètres de cette fonction.
En d’autres termes, le gradient descent est un algorithme permettant de trouver le minimum local d’une fonction différentiable. La descente de gradient est simplement utilisée pour trouver des valeurs aux paramètres d’une fonction permettant d’atteindre ce minimum local.
Alors comment fonctionne le gradient descent ?
Avant d’aller plus loin, définissons ce qu’est le gradient.
Le gradient d’une fonction de plusieurs variables en un certain point est un vecteur qui caractérise la variabilité de cette fonction au voisinage de ce point. (wikipédia).
« Un gradient mesure de combien le résultat d’une fonction change lorsqu’on fait varier légèrement les paramètres de celle-ci. »
Lex Fridman (MIT)
Cela veut bien dire que si on prend un point très proche du minimum (ou du maximum) le gradient est pratiquement nul car la fonction varie très peu en ce point.
Ainsi, l’objectif du gradient descent est de modifier les paramètres d’une fonction donnée jusqu’a ce que son gradient soit nul.
Pour être plus précis, la descente de gradient est un moyen de minimiser une fonction objectif J(θ) en mettant à jour les paramètres dans le sens inverse du gradient de la fonction objectif.
Fonctionnement
On commence avec des valeurs initiales (aléatoires).
Puis on calcule la fonction de mise à jour avec ces valeurs.
On répète l’opération jusqu’à trouver les valeurs qui minimisent la fonction de coût.
Exemple de calcul de minimum avec l’algorithme gradient descent
Nous allons utiliser l’algorithme du gradient pour calculer le minimum d’une fonction. Notre fonction est la suivante :
Il est évident que le minimum de cette fonction est 1. Essayons de le prouver avec le gradient descent !
Étape 1 : calcul de la fonction de mise à jour
Étape 2 : Choix du learning rate a.k.a (taux d’apprentissage)
Le taux d’apprentissage nous permet en quelque sorte de régler la vitesse de l’algorithme du gradient. On le choisit suffisamment petit afin de parcourir le maximum de points dans l’optique d’atteindre le minimum de notre fonction.
Étape 3: Itérer jusqu’à atteindre le minimum
| itérations du gradient descent | θ | J(θ ) |
| 0 | 2 | 21 |
| 1 | -1.6 | 10.113600000000002 |
| 2 | 0.3584000000000003 | 1.144950106364314 |
| 3 | 0.2683053277184002 | 1.0771699848711873 |
| 4 | 0.20691838355251382 | 1.044648360297446 |
| … | … | … |
| … | … | … |
| 33 | 0.0003023818248873522 | 1.0000000914347764 |
| 34 | 0.00024190544885059699 | 1.0000000585182496 |
| 35 | 0.00019352435341812456 | 1.0000000374516769 |
On voit qu’après plusieurs itérations nous avons (pratiquement) atteint le minimum de notre fonction. Je vous laisse tester via ce notebook sur google colab.
L’algorithme du gradient en machine learning
En machine learning, le gradient descent est le plus souvent utilisé pour minimiser une fonction de coût.
En effet, une fonction de coût (lost function) en ML est une fonction qui permet de déterminer si un modèle est capable de faire de bonnes prédictions pour un jeu de données.
Attention le minimum local n’est pas forcément le minimum global
Dans l’image ci-dessus, il existe un minimum local où le gradient est nul. Cependant, nous voyons qu’il ne s’agit pas du minimum de cette fonction. Ce problème est souvent rencontré en Machine Learning pour les modèles assez complexes car les fonctions objectifs sont difficilement convexes. Plusieurs méthodes existent pour pallier ce problème, nous les présenterons dans un prochain article.
Ressources complémentaires
Extremum, minimum, et maximum d’une fonction – Maximum dans un ensemble ordonné
Gradient Descent in Python
Conclusion
En somme, nous avons présenté l’un des algorithmes d’optimisation les plus utilisés (surtout en ML): le gradient descent.
Il faut retenir que le gradient descent requiert une fonction convexe comme fonction objectif et que le minimum trouvé n’est pas forcément un minimum global. Aussi, il faut s’assurer de bien choisir les paramètres de l’algorithme; on peut citer le taux d’apprentissage comme exemple. N’hesitez pas à laisser des commentaires pour les questions et suggestions.
