Descendez le gradient

Au chapitre précédent, nous avons trouvé les minimums en résolvant $\nabla f = 0$ à la main. C’est possible pour $x^2 + xy + y^2$, mais pas pour la fonction d’erreur d’un réseau de neurones à dix millions de paramètres. Il faut une méthode qui s’approche du minimum pas à pas, sans jamais résoudre d’équation.

Revenez à notre randonneur dans le brouillard. Sa stratégie la plus naturelle : regarder dans quel sens le terrain descend le plus, faire quelques pas dans cette direction, et recommencer. C’est exactement la descente de gradient, la méthode d’optimisation la plus utilisée au monde. Dans ce chapitre, vous allez la programmer et la régler, en suivant les fonctions de notre TP.

Le principe : suivre la plus forte pente

On part d’un point $x_0$ et l’on construit une suite de points par la règle

$$x_{k+1} = x_k - \alpha_k \, \nabla f(x_k)$$

• $x_k$ est le point courant à l’itération $k$ ;
• $\nabla f(x_k)$ est le gradient en ce point, et $-\nabla f(x_k)$ la direction de plus forte descente ;
• $\alpha_k \gt 0$ est le pas (step size), la longueur du déplacement. En apprentissage automatique, on l’appelle le taux d’apprentissage (learning rate).

Pourquoi est-ce que ça descend ? D’après Taylor à l’ordre 1, $f(x_k - \alpha \nabla f(x_k)) \approx f(x_k) - \alpha \lVert \nabla f(x_k) \rVert^2$, qui est plus petit que $f(x_k)$ dès que le gradient n’est pas nul et que $\alpha$ est assez petit. Plus généralement, toute direction $d$ telle que $\nabla f(x_k)^T d \lt 0$ est une direction de descente.

On s’arrête quand le gradient devient presque nul (on est près d’un point critique), ou après un nombre maximal d’itérations :

$$\lVert \nabla f(x_k) \rVert \lt \delta \quad \text{ou} \quad k = K$$

Dans notre TP, la tolérance valait $\delta = 0{,}025$ et le nombre maximal d’itérations $K = 20$.

Tout le réglage tient dans le choix du pas. Trop petit, le randonneur avance à pas de fourmi. Trop grand, il enjambe la vallée et se retrouve sur le versant d’en face. Voyons cela sur des chiffres.

Le pas fixe

La version la plus simple garde le même pas $\alpha$ à chaque itération.

Un exemple en dimension 1

En TP, nous avons minimisé $f(x) = x^4 - 7x + 8$ en partant de $x_0 = 0{,}8$, dont le minimum exact est $x^* = (7/4)^{1/3} \approx 1{,}2051$. Nous avons testé trois pas : 0,125, 0,1 et 0,01. Le pas 0,125 ne converge pas, le pas 0,01 converge plus lentement, et le pas 0,1 donne le meilleur résultat des trois : en sortie, $x \approx 1{,}204474$ et $f(x) \approx 1{,}673380$, pour un minimum exact $f(x^*) \approx 1{,}673377$.

Pourquoi un écart aussi net entre 0,1 et 0,125 ? Près du minimum, $f'(x) \approx f''(x^*)(x - x^*)$, donc une itération donne

$$x_{k+1} - x^* \approx \big(1 - \alpha f''(x^*)\big)(x_k - x^*)$$

L’erreur est multipliée à chaque pas par le facteur $1 - \alpha f''(x^*)$. Elle diminue si ce facteur est compris entre $-1$ et $1$, c’est-à-dire si $\alpha \lt 2 / f''(x^*)$. Ici $f''(x^*) = 12 (x^*)^2 \approx 17{,}43$, d’où la limite $\alpha \lt 0{,}115$.

Tant que le facteur reste sous 1 en valeur absolue, l'erreur diminue. Le pas 0,125 franchit la limite 2 / f″(x*) ≈ 0,115 : l'erreur grandit à chaque itération.

Pas $\alpha$	Facteur $1 - \alpha f''(x^*)$	Comportement
0,125	$\approx -1{,}18$	l’erreur grandit en changeant de signe : pas de convergence
0,1	$\approx -0{,}74$	oscillations de part et d’autre du minimum, qui s’amortissent
0,01	$\approx 0{,}83$	approche monotone mais lente

Si l’on rejoue le code du TP, on le voit très bien : avec 0,125, les itérées finissent par sauter indéfiniment entre environ 0,87 et 1,42 sans jamais s’approcher de 1,205 ; avec 0,01, elles ne sont encore qu’à 1,19 après les 20 itérations autorisées.

Les trois pas du TP : trop grand, les itérées sautent d'un versant à l'autre sans fin ; trop petit, elles avancent à pas de fourmi ; bien choisi, les oscillations s'amortissent vers x* ≈ 1,2051.

À retenir

Pour une fonction convexe dont le gradient est $L$-lipschitzien (la courbure ne dépasse jamais $L$), la descente à pas fixe converge si $0 \lt \alpha \lt 2/L$. Le choix $\alpha = 1/L$ est toujours sûr. Au-delà de $2/L$, les itérées oscillent ou divergent.

Un exemple en dimension 2

Passons à la quadratique du TP, $f_1(x, y) = 2x^2 + 3x + y^2 - 2$, de minimum $(-0{,}75 ; 0)$ et de valeur $-3{,}125$. Son gradient vaut $(4x + 3, 2y)$. Avec un pas fixe $\alpha = 0{,}1$, nous avons obtenu :

Départ	Point final	$f_1$ final
$(3, 3)$	$(-0{,}749771 ; 0{,}043235)$	$-3{,}123131$
$(10, 10)$	$(-0{,}749607 ; 0{,}115292)$	$-3{,}111707$

La coordonnée $x$ est presque exacte, mais $y$ traîne. L’explication tient en une ligne. Une itération s’écrit, coordonnée par coordonnée :

$$x_{k+1} + 0{,}75 = (1 - 4\alpha)(x_k + 0{,}75), \qquad y_{k+1} = (1 - 2\alpha)\, y_k$$

Avec $\alpha = 0{,}1$, l’erreur sur $x$ est multipliée par 0,6 à chaque pas, celle sur $y$ par 0,8 seulement. Depuis $(10, 10)$, après 20 itérations, $y = 10 \times 0{,}8^{20} \approx 0{,}115$ : c’est exactement ce qu’affiche le TP. Les deux directions ont des courbures différentes (4 et 2, les valeurs propres de la Hessienne), et un pas unique ne peut pas convenir parfaitement aux deux.

La coordonnée x (courbure 4) converge vite, la coordonnée y (courbure 2) traîne : après 20 pas, y vaut encore 0,115, exactement 10 × 0,8²⁰.

Le pas optimal

Plutôt que de fixer $\alpha$, on peut choisir à chaque itération le meilleur pas possible dans la direction de descente :

$$\alpha_k = \arg\min_{\alpha \gt 0} \; f\big(x_k - \alpha \nabla f(x_k)\big)$$

C’est une minimisation en une seule variable, qu’on appelle recherche linéaire (line search). Pour une fonction quadratique $f(x) = \tfrac12 x^T A x - b^T x$, elle se résout exactement. Notons $d_k = -\nabla f(x_k)$. La fonction $\varphi(\alpha) = f(x_k + \alpha d_k)$ est un polynôme de degré 2 en $\alpha$, de dérivée $\varphi'(\alpha) = -d_k^T d_k + \alpha \, d_k^T A d_k$. Elle s’annule pour

$$\alpha_k = \frac{d_k^T d_k}{d_k^T A d_k}$$

où $A$ est la matrice (définie positive) de la quadratique. C’est la formule que nous avons programmée en TP.

Exemple

Premier pas sur $f_1$ depuis $(10, 10)$, avec $A = \begin{pmatrix} 4 & 0 \\ 0 & 2 \end{pmatrix}$. Le gradient vaut $(43, 20)$, donc $d_0 = (-43, -20)$. Alors $d_0^T d_0 = 1849 + 400 = 2249$ et $d_0^T A d_0 = 4 \times 1849 + 2 \times 400 = 8196$, d’où $\alpha_0 = 2249 / 8196 \approx 0{,}2744$. Le nouveau point est $(10 - 43 \times 0{,}2744 ; 10 - 20 \times 0{,}2744) \approx (-1{,}799 ; 4{,}512)$.

Le gradient en ce point vaut environ $(-4{,}197 ; 9{,}024)$. Son produit scalaire avec $d_0$ : $(-43)(-4{,}197) + (-20)(9{,}024) \approx 180{,}5 - 180{,}5 = 0$. La nouvelle direction est perpendiculaire à l’ancienne.

Ce n’est pas un hasard : au pas optimal, $\varphi'(\alpha_k) = 0$, ce qui s’écrit $\nabla f(x_{k+1})^T d_k = 0$. Deux directions successives sont toujours orthogonales, et la trajectoire dessine un zigzag caractéristique. Le TP insistait d’ailleurs sur un détail : tracer les itérées dans un repère orthonormé, sans quoi ces angles droits ne se voient pas.

En TP, depuis $(10, 10)$, le pas optimal a atteint $(-0{,}750332 ; 0{,}001427)$, où $f_1 \approx -3{,}124998$ : bien plus près du minimum qu’avec le pas fixe (où $y$ valait encore 0,115). Sur $f_2(x, y) = x^2 + y^2 - 2y + 1$, le résultat est encore plus frappant : le point final est exactement $(0, 1)$, avec $f_2 = 0$. Pourquoi ? Sa matrice est $A = 2I$, ses lignes de niveau sont des cercles centrés sur le minimum, et le gradient pointe droit vers le centre : un seul pas optimal suffit.

Attention

Le code du TP s’arrêtait quand deux gradients successifs étaient proches, et non quand le gradient lui-même était petit. Ce critère est fragile : si l’algorithme avance très lentement, deux gradients successifs sont proches alors que l’on est encore loin du minimum. Préférez $\lVert \nabla f(x_k) \rVert \lt \delta$, éventuellement relatif à $\lVert \nabla f(x_0) \rVert$.

Le conditionnement, ennemi du gradient

Le zigzag est d’autant plus lent que les lignes de niveau sont allongées. On mesure cet allongement par le conditionnement de la Hessienne :

$$\kappa = \frac{\lambda_{\max}}{\lambda_{\min}}$$

où $\lambda_{\max}$ et $\lambda_{\min}$ sont la plus grande et la plus petite valeur propre. Des cercles donnent $\kappa = 1$ ; des ellipses très aplaties, un $\kappa$ énorme. Sur une quadratique, on montre que chaque itération à pas optimal multiplie l’erreur (mesurée dans la norme associée à $A$) par au plus

$$\frac{\kappa - 1}{\kappa + 1}$$

C’est aussi le meilleur facteur accessible avec un pas fixe, obtenu pour $\alpha = 2 / (\lambda_{\min} + \lambda_{\max})$.

Fonction	$\kappa$	Facteur $\frac{\kappa - 1}{\kappa + 1}$	Conséquence
$f_2$ (cercles)	1	0	un pas suffit
$f_1$	2	0,33	convergence rapide
ellipses aplaties	100	0,98	des centaines d’itérations

Plus les ellipses sont allongées, plus le zigzag est serré. À droite, l'erreur est multipliée à chaque pas par (κ − 1)/(κ + 1) : 0 pour les cercles de f₂, 1/3 pour f₁, 0,98 pour κ = 100.

Piège

En apprentissage automatique, des variables d’échelles très différentes (un âge en années et un revenu en euros) produisent une fonction de perte très mal conditionnée : la descente de gradient zigzague interminablement. C’est l’une des raisons pour lesquelles on standardise les variables avant d’entraîner un modèle.

Pour lutter contre un mauvais conditionnement, on peut changer d’échelle (préconditionnement), utiliser le gradient conjugué (qui résout une quadratique de dimension $n$ en au plus $n$ itérations) ou exploiter la courbure avec la méthode de Newton, au chapitre suivant.

Le pas adaptatif : la règle d’Armijo

Sur une fonction non quadratique, le pas optimal n’a pas de formule. Le chercher exactement coûterait trop cher, et ce serait inutile : il suffit d’un pas raisonnable. La règle d’Armijo (backtracking line search) accepte un pas dès qu’il fait baisser $f$ suffisamment :

$$f\big(x_k - \alpha \nabla f(x_k)\big) \leq f(x_k) - c \, \alpha \, \lVert \nabla f(x_k) \rVert^2$$

avec une petite constante $c$ (typiquement $10^{-4}$). On part de $\alpha = 1$ et l’on divise le pas par 2 tant que la condition n’est pas remplie. On évite ainsi les pas trop grands sans connaître la constante $L$.

Le retour arrière sur f(x) = x⁴ − 7x + 8 depuis x₀ = 0,8 : on part de α = 1 et l'on divise par 2 jusqu'à passer sous le seuil. Ici, le premier pas accepté est α = 1/8.

Voici une descente de gradient propre, avec un critère d’arrêt sur la norme du gradient :

import numpy as np

def descente_gradient(grad, x0, pas, tol=1e-6, max_iter=10_000):
    """Descente de gradient à pas fixe ; s'arrête quand le gradient est presque nul."""
    x = np.asarray(x0, dtype=float)
    for k in range(max_iter):
        g = grad(x)
        if np.linalg.norm(g) < tol:
            return x, k
        x = x - pas * g
    return x, max_iter

grad_f1 = lambda v: np.array([4 * v[0] + 3, 2 * v[1]])

for pas in [0.1, 1 / 3]:
    x, k = descente_gradient(grad_f1, [10, 10], pas)
    print(f"pas {pas:.3f} : {k} itérations, point final {x.round(4)}")
# pas 0.100 : 76 itérations ; pas 0.333 : 17 itérations (les deux autour de (-0.75, 0))

Le pas $1/3 = 2/(2 + 4)$ est le meilleur pas fixe pour $f_1$ : il divise le nombre d’itérations par plus de quatre.

En entretien

« La descente de gradient avance dans la direction opposée au gradient, avec un pas appelé taux d’apprentissage. Trop grand, elle oscille ou diverge ; trop petit, elle est lente. Sa vitesse dépend du conditionnement : si la fonction est très allongée dans une direction, elle zigzague. »

En résumé

• La descente de gradient itère $x_{k+1} = x_k - \alpha_k \nabla f(x_k)$ et s’arrête quand $\lVert \nabla f \rVert$ est petit.
• Avec un pas fixe, il faut $\alpha \lt 2/L$, où $L$ majore la courbure ; au-delà, oscillations ou divergence, comme le pas 0,125 du TP.
• Le pas optimal minimise $f$ le long de la direction ; sur une quadratique, $\alpha_k = \frac{d_k^T d_k}{d_k^T A d_k}$.
• Au pas optimal, deux directions successives sont orthogonales : la trajectoire zigzague.
• La vitesse dépend du conditionnement $\kappa$ : facteur $\frac{\kappa - 1}{\kappa + 1}$ par itération. Des lignes de niveau circulaires ($\kappa = 1$) se résolvent en un pas.
• La règle d’Armijo choisit un pas qui fait suffisamment baisser $f$, sans connaître $L$.

Exercices

Exercice · Un pas à la main

facile

Pour $f_2(x, y) = x^2 + y^2 - 2y + 1$, calculez une itération de gradient à pas fixe depuis $(10, 10)$ avec $\alpha = 0{,}1$, puis avec $\alpha = 0{,}5$. Que remarquez-vous ?

Voir la solution

Le gradient vaut $(2x, 2y - 2)$, soit $(20, 18)$ en $(10, 10)$.

• Avec $\alpha = 0{,}1$ : $(10 - 2, \; 10 - 1{,}8) = (8 ; 8{,}2)$.
• Avec $\alpha = 0{,}5$ : $(10 - 10, \; 10 - 9) = (0, 1)$, le minimum exact.

Pour $f_2$, la Hessienne vaut $2I$ : chaque coordonnée de l’erreur est multipliée par $1 - 2\alpha$ à chaque pas. Avec $\alpha = 0{,}5 = 1/L$, ce facteur est nul, et l’on arrive au minimum en une itération. C’est d’ailleurs exactement le pas optimal : $d^T d / d^T A d = 1/2$ quand $A = 2I$.

En code

Python

import numpy as np

grad_f2 = lambda v: np.array([2 * v[0], 2 * v[1] - 2])
x0 = np.array([10.0, 10.0])
for pas in [0.1, 0.5]:
    print(pas, x0 - pas * grad_f2(x0))    # 0.1 [8.  8.2] ; 0.5 [0. 1.] = le minimum

R

grad_f2 <- function(v) c(2 * v[1], 2 * v[2] - 2)
x0 <- c(10, 10)
for (pas in c(0.1, 0.5)) print(x0 - pas * grad_f2(x0))
# 8 8.2 avec 0,1 ; 0 1 avec 0,5 : le minimum en une itération

Exercice · Calculer un pas optimal

moyen

Soit $f(x, y) = x^2 + 5y^2$. Depuis $(5, 1)$, calculez le pas optimal, le nouveau point, et vérifiez l’orthogonalité des deux premières directions. Quel est le conditionnement, et quel facteur de réduction peut-on en attendre ?

Voir la solution

On a $f = \tfrac12 x^T A x$ avec $A = \mathrm{diag}(2, 10)$. En $(5, 1)$, le gradient vaut $(10, 10)$, donc $d_0 = (-10, -10)$. Alors $d_0^T d_0 = 200$ et $d_0^T A d_0 = 2 \times 100 + 10 \times 100 = 1200$, d’où $\alpha_0 = 1/6$.

Nouveau point : $(5 - \tfrac{10}{6}, \; 1 - \tfrac{10}{6}) = (\tfrac{10}{3}, -\tfrac23)$. Le gradient y vaut $(\tfrac{20}{3}, -\tfrac{20}{3})$ et son produit scalaire avec $d_0$ est $-\tfrac{200}{3} + \tfrac{200}{3} = 0$ : les directions sont bien orthogonales.

Le conditionnement vaut $\kappa = 10/2 = 5$, d’où un facteur $\frac{5 - 1}{5 + 1} = \tfrac23$ par itération au pire : il faut environ 6 itérations pour diviser l’erreur par 10.

En code

Python

import numpy as np

A = np.diag([2.0, 10.0])                  # f = x² + 5y² = ½ x'Ax
x = np.array([5.0, 1.0])
d0 = -A @ x                               # direction : -gradient = (-10, -10)
alpha = d0 @ d0 / (d0 @ A @ d0)
x1 = x + alpha * d0
print(alpha, x1, (-A @ x1) @ d0)          # 0.1667 [ 3.333 -0.667] 2e-14 : orthogonales

kappa = 10 / 2
facteur = (kappa - 1) / (kappa + 1)
print(kappa, facteur, np.log(0.1) / np.log(facteur))   # 5.0 0.667 5.68 : environ 6 itérations

# Vérification : on itère jusqu'à diviser l'erreur (norme A) par 10
k, e0 = 0, np.sqrt(x @ A @ x)
while np.sqrt(x @ A @ x) > e0 / 10:
    d = -A @ x
    x, k = x + (d @ d / (d @ A @ d)) * d, k + 1
print(k)                                  # 6

R

A <- diag(c(2, 10))                        # f = x² + 5y² = ½ x'Ax
x <- c(5, 1)
d0 <- -A %*% x                             # direction : -gradient = (-10, -10)
alpha <- sum(d0^2) / sum(d0 * (A %*% d0))
x1 <- as.vector(x + alpha * d0)
alpha; x1; sum(-A %*% x1 * d0)             # 0.1667 ; 3.333 -0.667 ; 0 : orthogonales

kappa <- 10 / 2
facteur <- (kappa - 1) / (kappa + 1)
facteur; log(0.1) / log(facteur)           # 0.667 ; 5.68 : environ 6 itérations

Exercice · Le plus grand pas admissible

difficile

Pour $f_1(x, y) = 2x^2 + 3x + y^2 - 2$ et la descente à pas fixe :

1. Pour quelles valeurs de $\alpha$ la méthode converge-t-elle, quel que soit le point de départ ?
2. Que se passe-t-il exactement pour $\alpha = 0{,}5$ ?
3. Quel pas fixe minimise le plus lent des deux facteurs de réduction ?

Voir la solution

1. Les erreurs sur $x$ et $y$ sont multipliées par $1 - 4\alpha$ et $1 - 2\alpha$. Il faut $\lvert 1 - 4\alpha \rvert \lt 1$ et $\lvert 1 - 2\alpha \rvert \lt 1$, soit $0 \lt \alpha \lt 0{,}5$ (la première condition est la plus sévère). On retrouve $\alpha \lt 2/L$ avec $L = \lambda_{\max} = 4$.
2. Pour $\alpha = 0{,}5$, le facteur sur $x$ vaut $-1$ : l’erreur sur $x$ change de signe à chaque pas sans diminuer. Depuis $(10, 10)$, $x$ alterne indéfiniment entre $10$ et $-11{,}5$ (symétriques par rapport à $-0{,}75$), tandis que $y$ converge (facteur 0). La méthode ne converge pas.
3. On veut minimiser $\max(\lvert 1 - 4\alpha \rvert, \lvert 1 - 2\alpha \rvert)$. Le maximum est le plus petit quand les deux facteurs sont opposés : $4\alpha - 1 = 1 - 2\alpha$, soit $\alpha = \tfrac13$. Les deux facteurs valent alors $\tfrac13$ en valeur absolue, ce qui est bien $\frac{\kappa - 1}{\kappa + 1}$ avec $\kappa = 2$.

En code

Python

import numpy as np

# Facteurs de réduction sur x et sur y : 1 - 4α et 1 - 2α
pas = np.arange(10, 6000) / 10_000            # de 0,001 à 0,6
pire = np.maximum(abs(1 - 4 * pas), abs(1 - 2 * pas))
print(pas[pire < 1].max())                  # 0.4999 : convergence si 0 < α < 0,5
print(pas[pire.argmin()], pire.min())       # 0.3333 0.3334 : meilleur pas 1/3, facteur 1/3

# α = 0,5 depuis (10, 10) : x oscille sans converger
grad_f1 = lambda v: np.array([4 * v[0] + 3, 2 * v[1]])
v = np.array([10.0, 10.0])
for k in range(4):
    v = v - 0.5 * grad_f1(v)
    print(v)                                # [-11.5 0] [10 0] [-11.5 0] [10 0]

R

# Facteurs de réduction sur x et sur y : 1 - 4α et 1 - 2α
pas <- seq(0.001, 0.6, by = 1e-4)
pire <- pmax(abs(1 - 4 * pas), abs(1 - 2 * pas))
max(pas[pire < 1])                          # 0.4999 : convergence si 0 < α < 0,5
pas[which.min(pire)]; min(pire)             # 0.3333 et 0.3334 : meilleur pas 1/3, facteur 1/3

# α = 0,5 depuis (10, 10) : x oscille sans converger
grad_f1 <- function(v) c(4 * v[1] + 3, 2 * v[2])
v <- c(10, 10)
for (k in 1:4) { v <- v - 0.5 * grad_f1(v); cat(v, "\n") }
# -11.5 0 / 10 0 / -11.5 0 / 10 0