Gradient descent – l’algorithme du gradient

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.

\[\theta:=\theta – \alpha \frac{\partial }{\partial \theta} J(\theta)\]
où \(\theta =\) paramètre de la fonction à minimiser, \(\alpha\) le taux d'apprentissage et J(\(\theta\)) = La fonction à minimiser.

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 :

\[ J(\theta) = \theta^4 + \theta^2 + 1 \]
Fonction à minimiser

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

\[\theta:=\theta - \alpha \frac{\partial }{\partial \theta} J(\theta)\] où \( J(\theta) = \theta^4 + \theta^2 + 1 \)
donc \[\theta:=\theta - \alpha \frac{\partial }{\partial \theta} ( \theta^4 + \theta^2 + 1 )\]
Alors \[\theta:=\theta - \alpha( 4\theta^3 + 2\theta )\]
D'où \[\theta:=\theta(1- 2\alpha) - \alpha 4\theta^3\]

É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.

On fixe le taux d'apprentissage à 0.1. ( \( \alpha = 0.1\) ). On a donc la fonction de mise à jour suivante : \[\theta:=0.8*\theta - 0.4*\theta^3\] .
Cela veut dire qu'à chaque itération le paramètre \(\theta\) prend la valeur \(\ 0.8*\theta - 0.4*\theta^3\) jusqu'à atteindre le minimum de la fonction \( J(\theta)\).

Étape 3: Itérer jusqu'à atteindre le minimum

Comme je l'ai présenté plus haut, le gradient descent débute par un choix aléatoire des paramètres. Pour notre exemple on initialise alors \(\theta\) comme suit : \(\theta\) = 2. L'idée sera d'itérer un grand nombre de fois pour atteindre le minimum.
itérations
du gradient descent
θ J(θ )
0221
1-1.610.113600000000002
20.35840000000000031.144950106364314
30.26830532771840021.0771699848711873
40.206918383552513821.044648360297446
.........
.........
330.00030238182488735221.0000000914347764
340.000241905448850596991.0000000585182496
350.000193524353418124561.0000000374516769
Itérations du gradient descent
Différentes étapes du gradient descent
Différentes étapes du gradient descent

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.

Ouvrir dans 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.

Supposons que nous avons un modèle \( h( \theta ,x) \) où \(x\) un vecteur correspondant aux entrées du modèle, \( \theta \) les paramètres du modèle et \(y\) un vecteur correspondant aux sorties du modèle.
Un exemple de fonction de coût s'écrirait comme suit : \[J(\theta) =\frac{1}{2m} \sum _{i=1}^{m} (h( \theta ,x) - y )^2 \] \( m\) étant la taille de notre jeu de données.

Attention le minimum local n'est pas forcément le minimum global

challenges-gradient descent
Source : https://blog.paperspace.com/intro-to-optimization-in-deep-learning-gradient-descent/

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.

La source An overview of gradient descent optimization algorithms Intro to optimization in deep learning: Gradient Descent

Laisser un commentaire

Votre adresse email ne sera pas publiée.

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.

Voulez-vous en savoir plus sur la Data Science ?

Inscrivez-vous alors à notre newsletter et vous receverez gratuitement nos derniers articles et actualités ! 
S'INSCRIRE MAINTENANT 
close-link