Comprendre comment marche la méthode du gradient

Publié par Auguste Hoang le 7 mai 20227 mai 2022

Partagez sur les réseaux sociaux !

La méthode du gradient est un outil indispensable en machine learning. Dans la plupart des algorithmes, on doit souvent trouver les paramètres qui minimisent une fonction.

Si par exemple la fonction à minimiser est $f(x) = ax^2+bx+c$ , alors on sait que le minimum (ou maximum si $a<0$ ), est obtenue pour $x=\tfrac{-b}{2a}$ . Malheureusement pour les autres fonctions, il n’y a pas toujours de formules magiques pour obtenir ce minimum, surtout lorsque la fonction admet plusieurs variables.

Cependant, il existe une méthode relativement efficace qui permet de résoudre ce problème pour n’importe quelle fonctions. C’est la méthode du gradient. Et c’est elle qui est utilisée pour entraîner un réseau de neurones lorsque l’on fait de la backpropagation.

Dans cet article, tu vas comprendre:

Comment fonctionne cette méthode ✔
Pourquoi elle fonctionne ✔
Ses limites d’utilisation ✔

D’où vient la méthode du gradient ?

Le cadre général d’utilisation de la méthode de gradient est le suivant. On dispose d’une fonction $f$ de plusieurs variables $x = (x_1, x_2, \cdots, x_n)$ dont on sait évaluer sa valeur et son gradient en tout point $x$ . La question est de trouver le point $x$ qui minimise $f(x)$ .

Le principe général de la méthode de gradient est de partir d’un point $x$ au hasard, et de le déplacer d’un petit pas pour faire diminuer la valeur $f(x)$ .

Pour comprendre comment faire déplacer $x$ , il faut utiliser le résultat mathématique suivant. Si $f$ est fonction de une seule variable $x$ , alors on peut faire l’approximation suivante:

$f(x+h) \simeq f(x) + f'(x) \times h,$

lorsque $h$ est un nombre suffisamment petit (on rappelle que $f'(x)$ est la dérivée de $f$ en $x$ ). Cette formule s’appelle le développement limité de $f$ .

Ce qu’il faut comprendre de cette formule est que si on change $x$ d’une petite valeur $h$ , alors on change $f(x)$ d’une valeur proportionnelle à $h$ , à savoir $f'(x) \times h$ 👍.

En particulier si on veut faire diminuer $f$ , alors il faut prendre $h$ un nombre de signe opposé à $f'(x)$ 👍.

Pour les fonctions de plusieurs variables

Qu’en est-il des fonctions à plusieurs variables ? Nous avons expliqué la formule du développement limité pour des fonctions à une seule variable. On peut facilement la généraliser pour les fonctions de plusieurs variables.

Si $f$ est une fonction de plusieurs variables $x = (x_1, x_2, \cdots, x_n)$ , alors en figeant toutes les variables sauf une, on se ramène à une fonction d’une seule variable. Donc si on fige toutes les composantes sauf $x_1$ , on obtient la formule:

$f(x_1 + h_1, x_2, \cdots, x_n) \simeq f(x) + \tfrac{\partial f}{\partial x_1}(x) \times h_1,$

où $h_1$ est un petit nombre et $\tfrac{\partial f}{\partial x_1}$ est la dérivée partielle de $f$ par rapport à $x_1$ .

En itérant ce procédé sur toutes les composantes, on peut en déduire que si $h_1, h_3, \cdots, h_n$ sont des nombres assez petits, alors:

$f(x_1+h_1, x_2+h_2, \cdots, x_n+h_n) \simeq f(x) + \sum_{i=1}^n \tfrac{\partial f}{\partial x_i}(x) \times h_i.$

La dernière somme peut s’écrire comme étant $\langle \mathrm{grad}f(x), h \rangle$ le produit scalaire entre le gradient de $f$ en $x$ et le vecteur $h = (h_1, h_3, \cdots, h_n)$ . Autrement dit la formule précédente peut s’écrire de manière plus compacte:

$f(x + h) \simeq f(x) + \langle \mathrm{grad}f(x), h \rangle.$

En conséquence, si $h$ est un petit vecteur dans la direction opposée au gradient $\mathrm{grad}f(x)$ , alors le produit scalaire $\langle \mathrm{grad}f(x), h \rangle$ est négatif et donc $f(x + h)$ est strictement inférieur à $f(x)$ .

Voilà le principe fondamental de la méhode du gradient 👌.

Algorithme de la méthode du gradient

Nous avons vu que si on déplace $x$ d’un petit pas dans la direction opposé au gradient, alors on fait diminuer $f(x)$ . La méthode du gradient consiste à répéter cette opération.

L’algorithme se présente de la manière suivante :

Choisir une petite valeur $\eta >0$ , appelée learning rate (ou coefficient d’apprentissage).
Initialiser aléatoirement un point $x$ .
Répéter un nombre fini de fois:
1. Calculer $g$ , le gradient de $f$ en $x$ .
2. Changer $x \leftarrow x - \eta \times g$ .
Renvoyer la valeur de $x$ .

Le point $x$ renvoyé est alors une estimation du paramètre qui minimise $f$ .

Il y a plusieurs façons de choisir le nombre d’itérations de l’étape 3:

Soit on le répète un nombre de fois prédéterminé (par exemple 100).
Soit on s’arrête lorsque $f(x)$ ne diminue plus ou diminue très peu.

Le problème du choix du learning rate

Lorsqu’on veut appliquer la méthode du gradient, il faut choisir le learning rate $\eta$ . Si on choisit un learning rate trop petit, alors il faudra plus d’étapes pour converger le minimum, et si on choisit un learning rate trop grand, alors on va louper le minimum 🤔.

Pour comprendre ce phénomène, nous allons l’illustrer par exemple simple. Admettons que l’on veuille minimiser la fonction d’une seule variable $f(x) = x^2$ . Si on applique l’algorithme avec un learning rate $\eta$ , et que l’on note $x_0$ la valeur de $x$ à l’étape initial et $x_t$ la valeur de $x$ à l’étape $t$ . Alors on a la formule:

$x_{t+1} = x_t - \eta f'(x_t).$

Comme la dérivé de $f$ vaut $f'(x) = 2x$ , on peut réécrire la formule précédente en:

$x_{t+1} = (1-2\eta) x_t.$

Ainsi la suite $(x_t)_{t=0...}$ est une suite géométrique de raison $(1-2\eta)$ , autrement dit pour tout $t$ , on a:

$x_t = (1-2\eta)^t x_0.$

Il y a alors 3 possibilités:

Soit $\eta<0.5$ , auquel cas la raison est entre $0$ et $1$ , et la suite $(x_t)_{t=0...}$ tends vers le minimum $0$ .
Soit $0.5<\eta<1$ , auquel cas la raison est entre $-1$ et $0$ , et la suite $(x_t)_{t=0...}$ tends vers le minimum $0$ , mais en oscillant.
Soit $1<\eta$ , auquel cas la raison est $<-1$ , et la suite $(x_t)_{t=0...}$ diverge.

Dans cet exemple il faut que $\eta$ soit entre $0$ et $1$ pour que l’algorithme converge vers le bon résultat. A noter que si $\eta$ est trop proche de $0$ , alors la raison vaudra environ $1$ , et donc l’algorithme ne convergera pratiquement pas 😬.

Pour une fonction $f$ quelconque, il faut choisir $\eta$ entre $0$ et $\tfrac{\lambda}{2}$ , où $\lambda$ est la dérivée seconde de $f$ au point minimum pour que l’algorithme converge, et idéalement prendre $\eta$ autour de $\tfrac{\lambda}{4}$ pour que l’algorithme ne converge pas trop lentement. Le problème est qu’on ne peut pas calculer $\lambda$ vu que l’on ne connaît pas le point minimum…😕

A cause de ce problème du choix de learning rate, il y a des variantes qui permettent d’ajuster le learning rate au cours de l’algorithme 😀. Citons les principaux:

RProp (Resilient backPropagation).
RMSProp (Root Mean Square Propagation).
AdaGrad (Adaptative Gradient).
Adam (Adaptative moment Estimation).

Les limites de la méthode du gradient

Bien qu’elle s’applique à pratiquement n’importe quelle situation (la seule condition est que l’on puisse calculer le gradient de $f$ ), la méthode du gradient admet des inconvénients:

L’algorithme peut retourner un minimum local de $f$ qui n’est pas un minimum global.
On a vu qu’il faut choisir un bon learning pour que l’algorithme converge. Mais il y a des cas où il n’y aucun bon learning rate ! En effet, si on considère la fonction de deux variables
$f(x,y) = x^2 + 100y^2,$

alors la dérivée seconde de $f$ est une matrice qui a deux valeurs propres $\lambda_1 = 2$ et $\lambda_2 = 200$ . Il faut donc que learning rate soit inférieur à $\frac{\lambda_1}{2} = 1$ pour que l’algorithme converge, et il faut qu’il soit de l’ordre de $\frac{\lambda_2}{4} = 50$ pour que l’algorithme ne converge pas trop lentement. Or il n’y a aucune valeur de $\eta$ qui vérifie ces deux conditions 😕.

Conclusion

Maintenant tu connais toutes les explications de méthode du gradient 🙂.

Si tu as des remarques ou des questions, alors n’hésite pas à le dire en commentaire.

Catégories : Mathématiques

Comprendre comment marche la méthode du gradient

D’où vient la méthode du gradient ?

Pour les fonctions de plusieurs variables

Algorithme de la méthode du gradient

Le problème du choix du learning rate

Les limites de la méthode du gradient

Conclusion

Le guide du calcul différentiel pour le Deep-Learning

Merci pour votre demande de recevoir le cadeau ! Vous allez tout de suite recevoir le lien de téléchargement dans votre boîte email. Si vous n'avez pas reçu l'email d'ici quelques minutes, pensez à regarder vos "spams".

0 commentaire

Laisser un commentaireAnnuler la réponse.

Le guide du calcul différentiel pour le Deep-Learning

Deep Learning

Une introduction à la Convolution pour débutant

Deep Learning

Comprendre le mécanisme d’attention : la clé du succès en Deep Learning

Deep Learning

Comprendre facilement la Backpropagation

Le guide du calcul différentiel pour le Deep-Learning

Merci pour votre demande de recevoir le cadeau ! Vous allez tout de suite recevoir le lien de téléchargement dans votre boîte email. Si vous n'avez pas reçu l'email d'ici quelques minutes, pensez à regarder vos "spams".

Le guide du calcul différentiel pour le Deep-Learning

Merci pour votre demande de recevoir le cadeau ! Vous allez tout de suite recevoir le lien de téléchargement dans votre boîte email. Si vous n'avez pas reçu l'email d'ici quelques minutes, pensez à regarder vos "spams".

Le guide du calcul différentiel pour le Deep-Learning

Merci pour votre demande de recevoir le cadeau ! Vous allez tout de suite recevoir le lien de téléchargement dans votre boîte email. Si vous n'avez pas reçu l'email d'ici quelques minutes, pensez à regarder vos "spams".

Comprendre comment marche la méthode du gradient

D’où vient la méthode du gradient ?

Pour les fonctions de plusieurs variables

Algorithme de la méthode du gradient

Le problème du choix du learning rate

Les limites de la méthode du gradient

Conclusion

Le guide du calcul différentiel pour le Deep-Learning

Merci pour votre demande de recevoir le cadeau ! Vous allez tout de suite recevoir le lien de téléchargement dans votre boîte email. Si vous n'avez pas reçu l'email d'ici quelques minutes, pensez à regarder vos "spams".

0 commentaire

Laisser un commentaireAnnuler la réponse.

Articles similaires

Deep Learning

Une introduction à la Convolution pour débutant

Deep Learning

Comprendre le mécanisme d’attention : la clé du succès en Deep Learning

Deep Learning

Comprendre facilement la Backpropagation

Le guide du calcul différentiel pour le Deep-Learning

Merci pour votre demande de recevoir le cadeau ! Vous allez tout de suite recevoir le lien de téléchargement dans votre boîte email. Si vous n'avez pas reçu l'email d'ici quelques minutes, pensez à regarder vos "spams".

Le guide du calcul différentiel pour le Deep-Learning

Merci pour votre demande de recevoir le cadeau ! Vous allez tout de suite recevoir le lien de téléchargement dans votre boîte email. Si vous n'avez pas reçu l'email d'ici quelques minutes, pensez à regarder vos "spams".

Le guide du calcul différentiel pour le Deep-Learning

Merci pour votre demande de recevoir le cadeau ! Vous allez tout de suite recevoir le lien de téléchargement dans votre boîte email. Si vous n'avez pas reçu l'email d'ici quelques minutes, pensez à regarder vos "spams".