Aller au contenu principal
iaLa descente de gradient

La descente de gradient

Ce que ce chapitre apporte

  • Dire pourquoi une formule fermée n'existe pas en général.
  • Écrire l'itération de la descente de gradient et le rôle du pas.
  • Reconnaître les quatre régimes : ramper, converger, rebondir, diverger.
  • Calculer à la main le gradient d'une erreur quadratique et le vérifier numériquement.
  • Expliquer pourquoi la mise à l'échelle change le nombre d'itérations d'un facteur cent.
  • Distinguer minimum local et minimum global, et dire quand cela compte.
  • Comparer descente par lots, par mini-lots et stochastique.
Le chapitre précédent trouvait son minimum d'un seul coup, par une formule. C'était un luxe, et il ne se reproduira plus : dès que le modèle cesse d'être une combinaison linéaire de ses paramètres, aucune formule ne donne la réponse. Il faut alors la chercher, et la méthode qui sert partout tient en une ligne : regarder la pente, et faire un pas dans le sens qui descend. Tout le reste est une question de réglage, et ce réglage décide de tout.

Pourquoi il faut chercher

La formule fermée est l'exception, pas la règle
Elle existait au chapitre précédent parce que l'erreur y était une fonction quadratique des paramètres : annuler ses dérivées donnait un système linéaire, et un système linéaire se résout.
Il suffit de très peu pour perdre cela. Une fonction de sortie qui n'est pas l'identité, une pénalité qui n'est pas quadratique, deux couches de calcul l'une après l'autre : dans chacun de ces cas, annuler les dérivées donne un système qu'aucune méthode ne résout exactement.
Or l'objectif reste le même : trouver les paramètres qui rendent l'erreur minimale. Puisqu'on ne sait plus résoudre, on va chercher, et la seule information disponible en un point est la pente de l'erreur.
La descente de gradient

Partir d'une valeur quelconque des paramètres, puis répéter :

θ←θ−η ∇E(θ)\theta \leftarrow \theta - \eta \, \nabla E(\theta)

où ∇E(θ)\nabla E(\theta) est le gradient de l'erreur, c'est-à-dire le vecteur de ses dérivées partielles, et η\eta le pas d'apprentissage.

Le gradient pointe dans la direction où l'erreur monte le plus vite. On avance donc dans la direction opposée.

Trois choses dans une seule ligne
La direction vient du signe du gradient. Sur une pente descendante vers la droite, la dérivée est négative, donc −η∇E-\eta\nabla E est positif et l'on va vers la droite. L'algorithme n'a jamais besoin de savoir où est le minimum : la pente locale suffit.
La distance est le produit du pas par la pente. Elle est donc grande là où c'est raide et petite là où c'est plat. La descente ralentit d'elle-même en approchant, ce qui est une propriété heureuse et non un réglage.
L'arrêt vient tout seul : au minimum, la pente est nulle, donc le déplacement aussi. L'algorithme se fige sans qu'on ait à lui dire de s'arrêter.

La figure ci-dessous déroule cela sur une parabole. Le curseur du pas est le sujet du chapitre : il faut le pousser dans tous les sens.

020406080-50510valeur du paramètreerreur
saut 15 / 15x = 2 erreur 3

La pente est nulle : plus aucun saut ne déplace quoi que ce soit. La descente est arrivée.

Descente sur l'erreur x² − 4x + 7, dont le minimum est en 2. Avec le pas 0,25 la descente arrive en quelques sauts. Le curseur va de 0,0125 à 1,5 : en dessous de 0,05 elle rampe, à 0,5 elle arrive en un seul saut, à 0,9 elle rebondit de part et d'autre, à 1 elle rebondit indéfiniment sans jamais arriver, et au-delà elle part à l'infini.
Les quatre régimes, et il faut les provoquer
Pas trop petit (0,0125) : après quinze sauts, la position est encore à 6,1 alors que le minimum est à 2. Rien ne va mal, tout est simplement trop lent. C'est le régime le plus coûteux, parce qu'il n'échoue pas visiblement.
Pas bien réglé (0,25) : la descente arrive en quelques sauts, chacun plus court que le précédent.
Pas trop grand (0,9) : chaque saut dépasse le minimum et atterrit de l'autre côté, mais plus près. La descente rebondit et finit par arriver.
Pas au-delà de la limite (1,25) : chaque saut dépasse le minimum plus loin que le précédent. La position s'échappe et l'erreur part à l'infini.
Le cas exactement critique mérite d'être vu : à 0,5 la descente arrive en un seul saut, et à 1,0 elle saute éternellement entre 8 et −4-4 sans jamais s'approcher.
Où se trouve la limite
Sur une erreur de la forme ax2+…a x^2 + \dots, la distance au minimum est multipliée à chaque saut par ∣1−2ηa∣|1 - 2 \eta a|.
Ce facteur est inférieur à 1, donc la descente converge, tant que η<1/a\eta < 1/a. Il vaut exactement 0 pour η=1/(2a)\eta = 1/(2a), ce qui explique l'arrivée en un seul saut. Il vaut −1-1 pour η=1/a\eta = 1/a, ce qui explique le rebond éternel.
En dimension quelconque, aa est remplacé par la plus grande courbure de la surface d'erreur. La limite du pas est donc fixée par la direction la plus raide, alors que la vitesse d'arrivée est fixée par la direction la plus plate. Tout le problème du conditionnement est là, et il est traité plus bas.

Le gradient, calculé puis vérifié

main.py
Sortie
>_ Prêt à exécuter…
Le calcul du gradient, à la main

L'erreur vaut E(β)=1n∑i(xi⊤β−yi)2E(\beta) = \frac{1}{n}\sum_i (x_i^{\top}\beta - y_i)^2.

Sa dérivée par rapport à la composante jj de β\beta vaut 2n∑i(xi⊤β−yi) xij\frac{2}{n}\sum_i (x_i^{\top}\beta - y_i)\, x_{ij}.

En notation matricielle, cela s'écrit ∇E=2nX⊤(Xβ−y)\nabla E = \frac{2}{n} X^{\top}(X\beta - y), ce qui est exactement la ligne de code.

Le facteur 22 vient du carré, et la division par nn rend l'erreur indépendante du nombre d'exemples, ce qui permet de garder le même pas quand la taille du jeu change.

Toujours vérifier un gradient par différence finie
La dérivée numérique E(θ+h)−E(θ−h)2h\dfrac{E(\theta + h) - E(\theta - h)}{2h} est lente et imprécise, donc inutilisable pour apprendre. Elle est en revanche presque impossible à écrire de travers, ce qui en fait l'outil de vérification idéal.
Un gradient faux ne provoque pas d'erreur : il produit un apprentissage qui converge mal, ou vers autre chose, et l'on cherche alors le problème partout ailleurs. Quelques lignes de vérification épargnent des heures.
Utiliser la forme centrée, avec +h+h et −h-h : son erreur est en h2h^2 alors que la forme simple est en hh. Avec h=10−6h = 10^{-6} les deux gradients doivent coïncider sur cinq ou six décimales, ce que fait le bloc ci-dessus.

Le pas, en figure

main.py
Sortie
>_ Prêt à exécuter…
Les deux courbes ne disent pas la même chose
En haut, l'erreur. Elle décroît de façon lisse dans les trois cas qui convergent, et l'on n'y voit rien du rebond : à 0,95 la descente saute de part et d'autre du but, mais son erreur baisse quand même à chaque saut. Une courbe d'erreur qui descend n'est donc pas la preuve que le pas est bien réglé.
En bas, l'écart du coefficient au but. C'est là que tout se voit : le pas 0,005 rampe en ligne droite sans arriver, le pas 0,20 arrive en huit tours, le pas 0,95 zigzague de part et d'autre en s'approchant lentement, et le pas 1,05 zigzague en s'éloignant.
Le tableau confirme les valeurs : à 0,005 l'erreur reste à 339 alors que le plancher est à 2,16, et à 0,95 elle vaut 2,36, c'est-à-dire qu'après quarante tours elle n'est toujours pas arrivée.

Le conditionnement, ou pourquoi la mise à l'échelle est indispensable

main.py
Sortie
>_ Prêt à exécuter…
Cent itérations contre plus de dix mille
Sur les données mises à l'échelle, la descente atteint le plancher de 2,1617 en cent tours. Sur les données brutes, après dix mille tours, l'erreur vaut encore 24,3.
La figure explique pourquoi. À gauche, les lignes de niveau sont des ellipses très allongées : la surface est un ravin étroit, raide dans une direction et presque plate dans l'autre. Le gradient pointe vers la paroi du ravin, pas vers le fond, et la descente monte la paroi puis s'arrête, sans jamais parcourir la longueur.
À droite, les lignes de niveau sont des cercles. Le gradient pointe exactement sur le but, et la descente y va en ligne droite.
La raison en une phrase : la limite du pas est fixée par la direction la plus raide, tandis que la vitesse d'arrivée est fixée par la direction la plus plate. Plus l'écart entre les deux est grand, plus le pas admissible est petit par rapport à la distance à parcourir.
Une conséquence à retenir au-delà de ce chapitre
La mise à l'échelle n'était, au chapitre 3, qu'une commodité pour rendre les attributs comparables. Ici elle devient une condition de fonctionnement : sans elle, la descente n'arrive pas, quel que soit le temps qu'on lui laisse.
Tout ce qui apprend par descente de gradient est concerné, ce qui veut dire à peu près tout ce que ce module verra ensuite. C'est pourquoi la standardisation est une étape systématique et non un raffinement.

Le minimum trouvé n'est pas forcément le bon

0255075-202valeur du paramètreerreur
saut 25 / 25x = -1,327 erreur 3,901

La pente est nulle : plus aucun saut ne déplace quoi que ce soit. La descente est arrivée.

La même erreur, avec deux vallées. Partie de −2, la descente tombe dans celle de gauche et s'y arrête, à une erreur de 3,90. Elle ne verra jamais l'autre.
0255075-202valeur du paramètreerreur
saut 25 / 25x = 2,53 erreur -7,702

La pente est nulle : plus aucun saut ne déplace quoi que ce soit. La descente est arrivée.

Exactement la même erreur, exactement le même pas, un point de départ différent. La descente tombe cette fois dans la vallée de droite et atteint 7,70 au-dessous de zéro. Le résultat ne dépend que de l'endroit où l'on a commencé.
Minimum local, minimum global

Un minimum local est un point dont aucun voisin immédiat n'a une erreur plus faible.

Un minimum global est le point de plus faible erreur de tout l'espace.

La descente de gradient ne sait aller que vers un minimum local, puisque son unique information est la pente immédiate.

Ce qui compte n'est pas d'atteindre le minimum global
Le réflexe est de vouloir corriger le problème. C'est rarement le bon.
En petite dimension, on peut relancer depuis plusieurs départs et garder le meilleur, comme pour les k moyennes du chapitre 4. C'est exactement le même remède au même problème.
En grande dimension, la question change de nature. Avec des millions de paramètres, les vrais minima locaux sont rares : ce que l'on rencontre sont surtout des points-selles, descendants dans certaines directions et montants dans d'autres, dont le bruit des mini-lots suffit à sortir.
Et surtout, l'objectif n'est pas de minimiser l'erreur sur les données d'apprentissage : c'est de bien se comporter sur des données nouvelles. Un minimum local un peu moins profond fait souvent tout aussi bien, parfois mieux. Le chapitre suivant est entièrement consacré à cette distinction.

Lots, mini-lots, stochastique

Trois façons de compter le gradient

Par lots entiers : le gradient est calculé sur toutes les données. Une mise à jour par passage, exacte et coûteuse.

Stochastique : le gradient est calculé sur un seul exemple. Autant de mises à jour que d'exemples, chacune très bruitée.

Par mini-lots : le gradient est calculé sur un petit paquet, typiquement 32 à 256 exemples. C'est le compromis employé partout.

main.py
Sortie
>_ Prêt à exécuter…
Ce que montrent les deux panneaux

À gauche, le stochastique et les mini-lots atteignent le plancher dès le premier passage sur les données, là où les lots entiers en demandent quatre. Pour le même coût en lectures, on a fait 2000 pas au lieu d'un seul.

À droite, en zoomant sur le plancher, le tableau s'inverse. Les lots entiers s'y posent exactement et n'en bougent plus. Les mini-lots restent juste au-dessus. Le stochastique rebondit sans cesse entre 0,99 et 1,06, sans jamais se poser.

C'est le compromis complet, en une figure : plus de mises à jour donne une descente plus rapide et une arrivée moins précise. Le bruit est le prix de la vitesse.

Pourquoi le bruit est parfois un avantage
Un gradient calculé sur 32 exemples n'est pas le vrai gradient : c'est une estimation, qui pointe à peu près dans la bonne direction. Cette imprécision a trois effets utiles.
Elle permet de sortir des points-selles et des minima peu profonds, là où un gradient exact resterait bloqué.
Elle rend le coût d'une mise à jour indépendant de la taille du jeu, ce qui est la seule façon d'apprendre sur des données qui ne tiennent pas en mémoire.
Elle agit comme une régularisation légère, en empêchant de se poser exactement au fond du minimum d'apprentissage, ce qui se révèle souvent bénéfique sur des données nouvelles.
La contrepartie s'annule en diminuant le pas au fil des passages : on garde le bruit tant qu'il aide à explorer, puis on le réduit pour se poser.
Ce que font les optimiseurs réels
La ligne θ←θ−η∇E\theta \leftarrow \theta - \eta \nabla E est le point de départ, jamais le point d'arrivée. Trois idées s'y ajoutent, toujours les mêmes.
Le moment : accumuler les gradients successifs, comme une bille qui garde son élan. Cela traverse les ravins étroits sans osciller d'une paroi à l'autre.
Un pas par paramètre : diviser le pas de chaque coordonnée par l'ampleur récente de son gradient. Les directions plates avancent alors autant que les raides, ce qui corrige en partie le problème de conditionnement vu plus haut. C'est l'idée d'Adam, l'optimiseur employé par défaut aujourd'hui.
Un pas qui décroît : grand au début pour explorer, petit à la fin pour se poser.
Aucune de ces idées ne change la nature de la méthode. Elles règlent le pas mieux qu'à la main, et c'est tout.

Exercices type

Pourquoi la descente ralentit-elle toute seule en approchant du minimum ?

Parce que la distance parcourue à chaque saut est le produit du pas par la pente, et que la pente s'annule au minimum.

Loin du minimum, la surface est raide, la pente est grande, les sauts sont longs. Près du minimum, elle s'aplatit, et les sauts se raccourcissent d'eux-mêmes.

C'est une propriété de la méthode, pas un réglage : rien dans le code ne dit de ralentir.

C'est aussi ce qui fait que l'algorithme s'arrête sans qu'on le lui demande. Au minimum exact, le déplacement est nul.

La courbe d'erreur descend régulièrement. Le pas est-il bien réglé ?

On ne peut pas le dire à partir de cette seule courbe.

Le chapitre le montre : avec un pas de 0,95, la descente saute de part et d'autre du but à chaque tour, et son erreur baisse pourtant à chaque saut. La courbe d'erreur est lisse et le comportement est mauvais.

Ce qu'il faut regarder est la trajectoire des paramètres, ou à défaut la vitesse d'arrivée : après quarante tours, le pas 0,20 est au plancher de 2,1617 tandis que le pas 0,95 est encore à 2,36.

Une courbe d'erreur qui descend écarte seulement la divergence. Elle ne dit rien sur le fait qu'on aurait pu arriver dix fois plus vite.

Une descente diverge. Quelles sont les causes possibles, et dans quel ordre les examiner ?

Le pas trop grand, d'abord et presque toujours. Le diviser par dix et regarder. Si la divergence disparaît, c'était cela.

Des attributs non mis à l'échelle, ensuite. Un attribut à grande étendue rend la surface très raide dans sa direction, ce qui abaisse la limite du pas pour tout le monde. Standardiser, puis retenter avec le pas initial.

Un gradient faux, enfin. Le vérifier par différence finie centrée. Un signe inversé produit une remontée systématique, qui ressemble à s'y méprendre à un pas trop grand.

Ces trois causes couvrent la quasi-totalité des cas, et il est inutile de chercher plus loin avant de les avoir écartées.

Faut-il craindre les minima locaux ?

En petite dimension, oui, et le remède est de relancer depuis plusieurs départs, exactement comme pour les k moyennes. Le chapitre en donne l'exemple : la même erreur et le même pas, deux départs différents, deux vallées d'erreurs 3,90 et −7,70-7{,}70.

En grande dimension, beaucoup moins. Avec des millions de paramètres, un vrai minimum local exige que la surface remonte dans toutes les directions à la fois, ce qui est très improbable. On rencontre plutôt des points-selles, dont le bruit des mini-lots suffit à sortir.

Et surtout, la question est mal posée. L'objectif n'est pas de minimiser l'erreur sur les données d'apprentissage mais de bien se comporter sur des données nouvelles, et le minimum global de la première n'est pas nécessairement le meilleur choix pour la seconde.

Pourquoi la mise à l'échelle change-t-elle le nombre d'itérations d'un facteur cent ?

Parce que la limite du pas est fixée par la direction la plus raide de la surface, alors que la vitesse d'arrivée est fixée par la direction la plus plate.

Sans mise à l'échelle, les lignes de niveau sont des ellipses très allongées. Le pas doit rester assez petit pour ne pas diverger dans la direction raide, ce qui le rend ridiculement petit par rapport à la distance à parcourir dans la direction plate. Le gradient pointe alors vers la paroi du ravin plutôt que vers le fond.

Après standardisation, les lignes de niveau deviennent des cercles, le gradient pointe droit sur le but, et la descente y va en ligne droite.

Le chapitre le mesure : cent tours contre plus de dix mille, sur exactement les mêmes données.

Quelle taille de lot choisir ?

Des mini-lots, de 32 à 256 exemples, dans la quasi-totalité des cas.

Les lots entiers donnent un gradient exact et une arrivée précise, mais une seule mise à jour par passage sur les données. Ils sont impraticables dès que le jeu ne tient plus en mémoire.

Le stochastique, un exemple à la fois, avance très vite au début mais rebondit indéfiniment autour du minimum sans jamais s'y poser, comme le montre la figure du chapitre.

Les mini-lots prennent le meilleur des deux : assez d'exemples pour que le gradient soit à peu près juste, assez peu pour faire beaucoup de mises à jour, et une taille qui exploite bien le calcul vectoriel.

Le résidu de bruit se règle en diminuant le pas au fil des passages.

Vérification rapideon peut se reprendre

1.Que fait la descente de gradient à chaque itération ?

2.Un pas trop grand produit…

3.La courbe d'erreur descend régulièrement. Que peut-on en conclure ?

4.Pourquoi standardiser avant une descente de gradient ?

5.Comment vérifier qu'un gradient calculé à la main est juste ?

6.Par rapport aux lots entiers, la descente stochastique…

La méthode

  1. Standardiser les attributs, sans exception, avant toute descente.
  2. Écrire le gradient à la main, puis le vérifier par différence finie centrée.
  3. Partir d'un pas modeste, puis le multiplier par trois tant que la descente reste stable.
  4. Tracer l'erreur en échelle logarithmique au fil des tours, et non seulement sa valeur finale.
  5. Regarder aussi la trajectoire des paramètres, où le rebond se voit et où l'erreur ne le montre pas.
  6. Employer des mini-lots de 32 à 256, et rebattre les données à chaque passage.
  7. Diminuer le pas au fil des passages pour se poser.
  8. Relancer depuis plusieurs départs quand la dimension est petite et la surface accidentée.

Synthèse

  • La formule fermée du chapitre précédent est l'exception ; en général il faut chercher.
  • La descente répète θ←θ−η∇E(θ)\theta \leftarrow \theta - \eta \nabla E(\theta) : la pente donne la direction, le pas multiplié par la pente donne la distance.
  • Elle ralentit d'elle-même en approchant, et s'arrête là où la pente est nulle.
  • Quatre régimes : ramper, converger, rebondir, diverger. Sur ax2a x^2, la limite est η=1/a\eta = 1/a.
  • Une courbe d'erreur lisse n'est pas la preuve d'un bon réglage ; la trajectoire des paramètres l'est.
  • Le gradient de l'erreur quadratique vaut 2nX⊤(Xβ−y)\frac{2}{n} X^{\top}(X\beta - y), et se vérifie par différence finie centrée.
  • La mise à l'échelle n'est plus une commodité : cent tours contre plus de dix mille sur les mêmes données.
  • Des lignes de niveau allongées signifient que le gradient pointe vers la paroi du ravin, pas vers le fond.
  • La descente ne trouve qu'un minimum local ; le résultat dépend du départ.
  • En grande dimension, les points-selles sont le vrai obstacle, et le bruit des mini-lots en sort.
  • Mini-lots de 32 à 256 partout : assez précis pour avancer droit, assez nombreux pour avancer vite.
  • Le bruit du gradient est aussi un avantage, et son résidu se règle en diminuant le pas.