Descente de gradient

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

calculer le gradient de l'erreur quadratique moyenne d'un modèle linéaire sous forme matricielle, le démontrer, et écrire la règle de mise à jour de la descente de gradient;
prévoir l'effet du pas d'apprentissage — trop petit, raisonnable, trop grand — sur une fonction quadratique, et démontrer que la descente converge si et seulement si $0 < η < 2/ λ_{m a x}$ ;
reconnaître une fonction convexe par sa matrice hessienne, et expliquer pourquoi l'erreur quadratique moyenne d'un modèle linéaire en ses paramètres n'a pas de minimum local parasite;
relier la lenteur de la descente au conditionnement de la hessienne, et montrer sur les loyers que la standardisation des caractéristiques le fait passer d'environ 44 000 à 1;
programmer la descente stochastique et par mini-lots, compter en époques, et expliquer pourquoi la trajectoire est bruitée;
choisir un critère d'arrêt, en connaître la garantie et les limites, et situer les méthodes à moment, Adam et les minima locaux des problèmes non convexes.

Minimiser en suivant la pente

Au chapitre 2, la meilleure droite des moindres carrés pour les loyers du jeu A s'obtenait par un calcul direct: on écrit que les dérivées partielles de l'erreur quadratique moyenne s'annulent, on obtient les équations normales $\tilde{X}^{⊤} \tilde{X} w = \tilde{X}^{⊤} y$ , et on les résout. La pente vaut $w_{1} = 20, 1573$ CHF/m² et l'ordonnée à l'origine CHF. C'est une chance, et elle est rare. Dès le chapitre 4, la régression logistique conduit à des équations que l'on ne sait pas résoudre en une formule; au chapitre 10, un réseau de neurones a des milliers ou des millions de paramètres, et sa fonction de coût n'a aucune solution explicite. Même pour la régression linéaire, résoudre les équations normales coûte de l'ordre de opérations pour caractéristiques, et devient impraticable quand se compte en centaines de milliers.

Il faut donc une méthode qui cherche le minimum au lieu de le calculer. L'idée la plus simple est celle du randonneur dans le brouillard: il ne voit pas le fond de la vallée, mais il sent sous ses pieds dans quelle direction le terrain descend le plus fort, fait un pas dans cette direction, et recommence. En mathématiques, la direction de plus forte pente est donnée par le gradient (annexe A): pour une fonction $J : R^{p} \to R$ différentiable, c'est le vecteur

\nabla J (θ) = (\frac{\partial J}{\partial θ _{1}} (θ), \dots, \frac{\partial J}{\partial θ _{p}} (θ))^{⊤}

de ses dérivées partielles. Le résultat suivant justifie l'image du randonneur.

Démonstration. La dérivée de $J$ dans la direction $u$ est la dérivée en $t = 0$ de $t \mapsto J (θ + t u)$ ; par la règle de la chaîne (annexe A), elle vaut $\nabla J (θ)^{⊤} u$ . L'inégalité de Cauchy–Schwarz donne , d'où (3.1), avec égalité si et seulement si est colinéaire au gradient; le signe moins impose le sens opposé. Pour la seconde affirmation, posons . Par la règle de la chaîne, . Par définition de la dérivée, tend vers ce nombre négatif quand , donc est négatif pour assez petit, et .

Le théorème dit deux choses, et la seconde est plus modeste qu'on ne le croit. Aller dans la direction de $- \nabla J$ fait baisser $J$ — à condition de faire un pas assez petit. Il ne dit pas combien petit; tout ce chapitre tourne autour de cette question.

Trois remarques avant de calculer. D'abord, l'unité: si $J$ est en CHF² et $θ_{j}$ en CHF, la dérivée partielle est en CHF, et $η$ doit être un nombre pur pour que la mise à jour soit homogène — mais si $θ_{j}$ est en CHF/m², le pas devrait porter une unité différente pour chaque coordonnée. Un même $η$ pour des paramètres d'unités différentes est un compromis, et nous verrons qu'il coûte cher. Ensuite, la descente n'utilise que des dérivées premières: elle ne connaît de $J$ que sa pente locale, pas sa courbure. Enfin, la règle (3.2) s'arrête d'elle-même là où le gradient est nul — en un point critique, qui n'est pas forcément un minimum. Pour la régression linéaire, nous montrerons qu'il l'est toujours.

En Python, avec un vecteur représenté par une liste, la règle tient en une ligne de compréhension:

def pas_de_gradient(theta, gradient, eta):
    """Un pas de la règle (3.2): theta - eta * gradient(theta)."""
    g = gradient(theta)
    return [t - eta * gj for t, gj in zip(theta, g)]

Tout le reste — calculer le gradient, choisir $η$ , décider quand s'arrêter — est l'objet des sections suivantes.

Le gradient de l'erreur quadratique moyenne

Pour un modèle linéaire $f (x) = w_{0} + w_{1} x_{1} + \dots + w_{d} x_{d}$ , on range comme au chapitre 2 les exemples en lignes dans la matrice , dont la première colonne ne contient que des 1, et les paramètres dans . Les prédictions forment le vecteur , et le coût à minimiser est l'erreur quadratique moyenne

J (w) = \frac{1}{n} i = 1 \sum n (\tilde{x}_{i}^{⊤} w - y_{i})^{2} = \frac{1}{n} \tilde{X} w - y^{2}, (3.3)

où $\tilde{x}_{i} = (1, x_{i 1}, \dots, x_{i d})^{⊤}$ est la -ième ligne de écrite en colonne.

Dans ce chapitre, la lettre $H$ désigne toujours cette matrice hessienne; au chapitre 2, elle désignait la matrice de projection $\tilde{X} (\tilde{X}^{⊤} \tilde{X})^{- 1} \tilde{X}^{⊤}$ (la matrice chapeau), qui n'a rien à voir avec elle.

Démonstration. Notons $r_{i} (w) = \tilde{x}_{i}^{⊤} w - y_{i} = \sum_{l = 0}^{d} \tilde{x}_{i l} w_{l} - y_{i}$ le résidu de l'exemple (au signe près de la convention du chapitre 1), et le vecteur des résidus. La dérivée partielle de par rapport à est . Par la règle de dérivation d'un carré,

\frac{\partial J}{\partial w _{j}} = \frac{1}{n} i = 1 \sum n 2 r_{i} (w) \frac{\partial r _{i}}{\partial w _{j}} = \frac{2}{n} i = 1 \sum n \tilde{x}_{ij} r_{i} (w) .

La somme $\sum_{i} \tilde{x}_{ij} r_{i}$ est le produit scalaire de la $j$ -ième colonne de $\tilde{X}$ avec , c'est-à-dire la -ième composante de . En rangeant les dérivées partielles en colonne, on obtient , qui est la première formule de (3.4). Dérivons encore: la dérivée de par rapport à vaut , qui est le coefficient de ; il ne contient plus . Enfin, équivaut à .

Le gradient a une lecture simple: c'est une combinaison des colonnes de caractéristiques pondérée par les résidus. Si le modèle surestime les loyers des grands appartements ( $r_{i} > 0$ là où $x_{i}$ est grand), la composante $\partial J / \partial w_{1}$ est positive, et la règle (3.2) diminue la pente. Le pas de descente corrige le modèle , en proportion de leur taille.

Pour la régression simple, $d = 1$ , les deux composantes s'écrivent sans matrice:

\frac{\partial J}{\partial w _{0}} = \frac{2}{n} i = 1 \sum n (w_{0} + w_{1} x_{i} - y_{i}), \frac{\partial J}{\partial w _{1}} = \frac{2}{n} i = 1 \sum n x_{i} (w_{0} + w_{1} x_{i} - y_{i}) . (3.5)

Les loyers en surface standardisée

Les exemples de ce chapitre utilisent les huit appartements du jeu A (données fictives, construites pour le cours), dans une version légèrement transformée dont la section sur le conditionnement expliquera la raison. Plutôt que la surface $x_{i}$ en m², on utilise la surface standardisée

z_{i} = \frac{x _{i} - x ˉ}{s _{x}}, \overset{x}{ˉ} = 68, 375 m^{2}, s_{x} = \frac{1}{n} i = 1 \sum n (x_{i} - \overset{x}{ˉ})^{2} = 25, 2930 m^{2},

où $s_{x}$ est l'écart type de population (division par $n$ , et non par $n - 1$ ). Les $z_{i}$ sont des nombres purs, de moyenne $0$ et de moyenne des carrés $\frac{1}{n} \sum_{i} z_{i}^{2} = 1$ . Le modèle devient , et les moindres carrés donnent dans ces coordonnées CHF et CHF — le loyer moyen, et le supplément de loyer pour un écart type de surface en plus.

Ces deux propriétés des $z_{i}$ simplifient tout. Dans (3.5), $\sum_{i} z_{i} = 0$ et $\sum_{i} z_{i}^{2} = n$ , donc

\frac{\partial J}{\partial w _{0}} = 2 (w_{0} - \overset{y}{ˉ}), \frac{\partial J}{\partial w _{1}} = 2 (w_{1} - \frac{1}{n} i = 1 \sum n z_{i} y_{i}) = 2 (w_{1} - w_{1}^{*}), (3.6)

autrement dit $\nabla J (w) = 2 (w - w^{*})$ : le gradient pointe tout droit à l'opposé du minimum, et sa longueur est le double de la distance qui nous en sépare. Par le théorème 3.2, la hessienne vaut $H = \frac{2}{n} \tilde{X}^{⊤} \tilde{X} = 2 I$ , puisque a pour coefficients , et .

Question 3.1

Sur les loyers en surface standardisée, on se trouve au point $w = (1000; 300)$ . Que vaut la composante $\partial J / \partial w_{1}$ du gradient de l'erreur quadratique moyenne, en CHF? Utilisez $w_{1}^{*} = 509, 838$ .

Question 3.2

Complétez gradient_mse(w0, w1, donnees), qui renvoie le couple des dérivées partielles (3.5) de l'erreur quadratique moyenne du modèle $w_{0} + w_{1} x$ sur une liste de couples (x, y). Le programme standardise la surface des loyers, puis effectue trois pas de descente avec $η = 0, 1$ depuis $(0, 0)$ : vous devez retrouver le tableau de l'exemple 3.1.

gradient.py

Le pas d'apprentissage

L'exemple 3.1 a montré que, sur les loyers standardisés, un pas de descente multiplie l'écart au minimum par $0, 8$ . Ce facteur vient du pas: avec un pas $η$ quelconque, (3.6) donne

w^{(k + 1)} - w^{*} = w^{(k)} - w^{*} - 2 η (w^{(k)} - w^{*}) = (1 - 2 η) (w^{(k)} - w^{*}),

d'où, par récurrence,

w^{(k)} - w^{*} = (1 - 2 η)^{k} (w^{(0)} - w^{*}) . (3.7)

Tout le comportement de la descente est dans le nombre $1 - 2 η$ . S'il est compris entre $0$ et $1$ , l'écart diminue d'un facteur constant à chaque pas, toujours du même côté du minimum. S'il est compris entre $- 1$ et $0$ , l'écart diminue encore, mais change de signe à chaque pas: les itérés sautent par-dessus le minimum, d'un côté puis de l'autre. S'il vaut exactement $0$ , un seul pas suffit. Et si $∣ 1 - 2 η ∣ \geq 1$ , l'écart ne diminue plus, ou il grandit.

La figure 3.1 trace l'erreur quadratique moyenne au fil des itérations pour trois de ces pas, sur une échelle logarithmique. C'est le premier graphique à regarder quand on entraîne un modèle, et il faut savoir le lire. Une courbe d'apprentissage (learning curve, au sens de l'optimisation) qui descend en ligne droite sur une échelle logarithmique signale une convergence linéaire: le coût en excès est multiplié par un facteur constant à chaque pas — ici $(1 - 2 η)^{2}$ , puisque l'excès $J (w) - J (w^{*})$ vaut $∥ w - w^{*} ∥^{2}$ en surface standardisée. Une courbe qui descend à peine signale un pas trop petit; une courbe qui monte, un pas trop grand. Une courbe qui monte et descend alternativement, sans tendance, signale le cas limite.

Question 3.3

Sur les loyers standardisés, on compare les pas $η = 0, 1$ et $η = 0, 9$ , depuis le même point de départ. Lesquelles de ces affirmations sont vraies? (Plusieurs réponses possibles.)

Plusieurs réponses possibles

Ce qui rend les loyers standardisés si commodes est que la courbure est la même dans toutes les directions: la hessienne vaut $2 I$ . Le pas idéal $η = 0, 5$ est l'inverse de cette courbure. En général, la courbure dépend de la direction, et aucun pas unique ne peut convenir à toutes. Pour le comprendre, il faut d'abord s'assurer que le problème a bien un fond — c'est la convexité —, puis étudier une fonction quadratique quelconque.

Fonctions convexes

La définition ne fait intervenir que des points d'un même segment. Une fonction de plusieurs variables est donc convexe si et seulement si sa restriction à chaque droite, $φ (t) = J (θ + t v)$ , est une fonction convexe d'une variable — et ce dernier cas est celui d'Analyse I (chapitre 8), où l'on a vu qu'une fonction deux fois dérivable est convexe si et seulement si sa dérivée seconde est positive, et qu'elle reste alors au-dessus de ses tangentes. Ces deux faits se transportent en plusieurs variables.

Démonstration. Fixons $θ$ et une direction $v$ , et posons $φ (t) = J (θ + t v)$ . Par la règle de la chaîne (annexe A), $φ^{'} (t) = \nabla J (θ + t v)^{⊤} v$ et .

Point 1. Si $H$ est semi-définie positive partout, $φ^{''} \geq 0$ sur $R$ pour toute droite, donc chaque restriction est convexe (Analyse I, chapitre 8), donc $J$ est convexe, puisque (3.8) ne fait intervenir qu'une droite à la fois. Si $H$ est définie positive partout, $φ^{''} > 0$ dès que , chaque restriction est strictement convexe, et aussi. Réciproquement, si est convexe, chaque l'est, donc pour tous et .

Point 2. Prenons $v = θ^{'} - θ$ . La fonction $φ$ est convexe et dérivable, donc au-dessus de sa tangente en $0$ (Analyse I, chapitre 8): $φ (1) \geq φ (0) + φ^{'} (0)$ , c'est-à-dire . Si , (3.9) appliquée en donne pour tout .

C'est la propriété qui fait de la convexité la meilleure amie de l'optimisation: pour une fonction convexe, l'information locale est globale. Le randonneur qui ne sent plus de pente sous ses pieds est au fond de la vallée, et non dans une cuvette d'altitude. Aucune garantie de ce genre n'existe sans convexité.

Démonstration. Par le théorème 3.2, la hessienne vaut $H = \frac{2}{n} \tilde{X}^{⊤} \tilde{X}$ en tout point. Pour tout $v$ ,

v^{⊤} H v = \frac{2}{n} (\tilde{X} v)^{⊤} (\tilde{X} v) = \frac{2}{n} ∥ \tilde{X} v ∥^{2} \geq 0,

donc $H$ est semi-définie positive et $J$ est convexe (théorème 3.3). Si les colonnes de $\tilde{X}$ sont indépendantes, $\tilde{X} v \neq = 0$ pour tout $v \neq = 0$ , est définie positive et strictement convexe; une fonction strictement convexe a au plus un minimiseur, puisque le milieu de deux minimiseurs distincts aurait une valeur strictement plus petite. Si au contraire pour un , alors pour tout : est constante le long de cette droite et n'est pas strictement convexe, et tout minimum se prolonge en une droite de minima.

Deux remarques sur la portée de ce théorème. D'abord, «linéaire» s'entend en les paramètres: un modèle polynomial $w_{0} + w_{1} x + w_{2} x^{2}$ est linéaire en $(w_{0}, w_{1}, w_{2})$ , et son erreur quadratique moyenne est convexe — c'est la remarque du chapitre 2 sur les caractéristiques polynomiales. Ensuite, le cas non strict correspond exactement à la colinéarité du chapitre 2: si une caractéristique est une combinaison des autres, est singulière, il y a une infinité de solutions, et la descente de gradient converge vers l'une d'elles, qui dépend du point de départ. La régression ridge du chapitre 6 rétablit la stricte convexité en pénalisant les poids , . Le chapitre 6 ajoute la pénalité à la des carrés des résidus (définition 6.5); ajoutée à l'erreur quadratique moyenne (3.3), qui est cette somme divisée par , la même pénalité s'écrit , a le même minimiseur, et ajoute à la hessienne, où .

Convergence sur une fonction quadratique

L'erreur quadratique moyenne est une fonction quadratique des paramètres: en développant (3.3), $J (w) = w^{⊤} (\frac{1}{n} \tilde{X}^{⊤} \tilde{X}) w - \frac{2}{n} y^{⊤} \tilde{X} w + \frac{1}{n} ∥ y ∥^{2}$ . Étudions donc la descente sur une quadratique quelconque; le résultat vaudra pour la régression linéaire, et il décrit aussi, au voisinage d'un minimum, le comportement sur toute fonction assez régulière, que le développement de Taylor à l'ordre 2 approche par une quadratique.

Démonstration. Le gradient vaut $\nabla J (θ) = A θ - b = A (θ - θ^{*})$ , puisque $A θ^{*} = b$ . Notons l'écart au minimum. En retranchant des deux membres de (3.2),

e^{(k + 1)} = e^{(k)} - η A e^{(k)} = (I - η A) e^{(k)},

et (3.10) s'en déduit par récurrence. Comme $A$ est symétrique, le théorème spectral (Algèbre linéaire, chapitre 11) fournit une base orthonormée de vecteurs propres $q_{1}, \dots, q_{p}$ , avec $A q_{j} = λ_{j} q_{j}$ . Écrivons l'écart dans cette base, . Alors , donc

u_{j}^{(k + 1)} = (1 - η λ_{j}) u_{j}^{(k)} et u_{j}^{(k)} = (1 - η λ_{j})^{k} u_{j}^{(0)} .

Dans la base propre, la descente se découple en $p$ suites géométriques indépendantes, une par direction propre, de raisons $1 - η λ_{j}$ .

Condition suffisante. Si $0 < η < 2/ λ_{m a x}$ , alors pour tout $j$ , $0 < η λ_{j} \leq η λ_{m a x} < 2$ , donc . Le maximum des est donc strictement inférieur à 1, et, la base étant orthonormée,

∥ e^{(k)} ∥^{2} = j = 1 \sum p (1 - η λ_{j})^{2 k} (u_{j}^{(0)})^{2} \leq ρ^{2 k} j = 1 \sum p (u_{j}^{(0)})^{2} = ρ^{2 k} ∥ e^{(0)} ∥^{2},

qui tend vers $0$ . Comme $λ \mapsto ∣ 1 - η λ ∣$ est convexe, son maximum sur $[λ_{m i n}, λ_{m a x}]$ est atteint en une extrémité: c'est la formule annoncée pour $ρ$ .

Condition nécessaire. Partons de $θ^{(0)} = θ^{*} + q_{1}$ . Alors $e^{(k)} = (1 - η λ_{m a x})^{k} q_{1}$ , dont la norme est . Elle tend vers seulement si , c'est-à-dire .

Pour l'erreur quadratique moyenne, $A$ est la hessienne $H = \frac{2}{n} \tilde{X}^{⊤} \tilde{X}$ du théorème 3.2, définie positive quand les colonnes de $\tilde{X}$ sont indépendantes. Sur les loyers standardisés, : toutes les valeurs propres valent 2, la condition (3.11) s'écrit , et l'on retrouve exactement l'exemple 3.2 — convergence pour , oscillation sans fin en , divergence au-delà.

Le théorème a trois conséquences pratiques. Le seuil de stabilité ne dépend que de la plus grande courbure $λ_{m a x}$ : c'est la direction la plus raide qui interdit les grands pas. La vitesse dépend de la plus petite: même avec le pas maximal autorisé, la composante selon $q_{p}$ n'est multipliée que par $1 - η λ_{m i n}$ , proche de 1 si est petite devant . Et : c'est le zigzag caractéristique des vallées étroites, où les itérés rebondissent d'une paroi à l'autre tout en avançant lentement le long du fond. L'exercice 3.5 montre que le meilleur pas fixe, , donne le facteur , où .

Explorateur 3.1 · Descente de gradient sur une fonction quadratique

Les ellipses sont les courbes de niveau de $J (θ) = \frac{1}{2} (λ_{m a x} u_{1}^{2} + λ_{m i n} u_{2}^{2})$ , avec $λ_{m a x} = 2$ fixé; le conditionnement $κ = λ_{m a x} / λ_{m i n}$ les étire. Réglez le pas $η$ : au-delà de $η = 1/ λ_{m a x} = 0, 5$ , la descente zigzague à travers la vallée; au-delà de $2/ λ_{m a x} = 1$ , elle diverge — et ce seuil ne bouge pas quand vous changez $κ$ . Ce qui change avec $κ$ , c'est la lenteur le long de la vallée. Avec $κ = 1$ et $η = 0, 5$ , vous retrouvez la descente en un pas des loyers standardisés.

Conditionnement κ10

Pas d'apprentissage η0,90

Nombre d'itérations k20

λ_max et λ_min

2 et 0,200

Seuil de divergence 2/λ_max

Facteur par pas ρ = max |1 − ηλ|

0,820

Pas optimal 2/(λ_max + λ_min)

0,909

J(θ^(k)) / J(θ⁽⁰⁾)

2, 0 \cdot 1 0^{- 4}

Verdict

converge, en zigzag

L'explorateur 3.1 rend ces trois phénomènes visibles. Avec la valeur initiale $κ = 10$ et $η = 0, 9$ , la composante raide est multipliée par $1 - 0, 9 \times 2 = - 0, 8$ et zigzague, la composante lente par $1 - 0, 9 \times 0, 2 = 0, 82$ et rampe; le facteur affiché vaut , à peine plus que le meilleur possible, , obtenu avec . Faites varier en gardant : le seuil de divergence reste à 1, mais la descente devient de plus en plus lente le long de la vallée.

Conditionnement et standardisation

Avec $κ = 1$ , les courbes de niveau sont des cercles, le gradient pointe vers le centre, et le pas $1/ λ$ y mène en un coup: c'est la situation des loyers standardisés. Avec $κ$ grand, elles sont des ellipses très allongées, le gradient pointe presque perpendiculairement à la vallée au lieu de la suivre, et il faut de l'ordre de $κ$ pas pour progresser le long du fond. Les loyers en surface brute en sont un exemple frappant.

D'où vient un tel écart? Le déterminant vaut $λ_{m a x} λ_{m i n} = 4 (\overline{x^{2}} - \overset{x}{ˉ}^{2}) = 4 s_{x}^{2}$ , alors que la trace est dominée par . Deux défauts se cumulent. La surface est : ses valeurs sont toutes entre 30 et 110, loin de 0, si bien que la colonne des et la colonne des 1 de sont presque parallèles — augmenter d'un franc par m² et diminuer de CHF ne change presque aucune prédiction. Et la surface est que la colonne des 1: ses carrés valent des milliers. Le premier défaut produit la vallée oblique, le second l'écart de courbure entre les deux axes.

Le remède est de transformer les caractéristiques avant d'entraîner, de façon que la hessienne soit aussi proche que possible d'un multiple de l'identité.

Pour une seule caractéristique, la standardisation donne exactement $H = 2 I$ et $κ = 1$ , comme nous l'avons vu. Les deux opérations ont des rôles distincts: centrer (soustraire $\overset{x}{ˉ}$ ) rend la colonne des 1 orthogonale à la caractéristique et annule les termes hors diagonale de $H$ ; réduire (diviser par $s_{x}$ ) égalise les deux termes diagonaux. Centrer seulement laisserait , de conditionnement — bien mieux que 44 170, mais loin de 1 (problème guidé 3.1). Avec plusieurs caractéristiques, la standardisation égalise les diagonales mais ne supprime pas les corrélations entre caractéristiques: si deux d'entre elles sont fortement corrélées, la hessienne garde une petite valeur propre et le problème reste mal conditionné. C'est la colinéarité du chapitre 2 vue du côté de l'optimisation, et la régression ridge du chapitre 6 y répond en pénalisant les poids, sans le biais: avec la normalisation de (3.3), cela ajoute à la hessienne, ce qui relève les petites valeurs propres.

Standardiser ne change pas le modèle, seulement sa paramétrisation. De $f (z) = w_{0}^{*} + w_{1}^{*} z$ et $z = (x - \overset{x}{ˉ}) / s_{x}$ , on tire

f (x) = ordonn \overset{e}{ˊ} e \overset{a}{ˋ} l’origine (w_{0}^{*} - \frac{w _{1}^{*} x ˉ}{s _{x}}) + pente \frac{w _{1}^{*}}{s _{x}} x, \frac{509 , 838}{25 , 2930} = 20, 1573, 1902, 5 - 20, 1573 \times 68, 375 = 524, 245,

c'est-à-dire exactement la droite des moindres carrés du chapitre 2. Les prédictions sont identiques; seule la difficulté du chemin pour y arriver a changé.

Question 3.4

On entraîne les loyers en surface brute avec le pas $η = 1 0^{- 4}$ . Selon la direction propre lente ( $λ_{m i n} = 0, 2407$ ), l'écart au minimum est multiplié à chaque pas par $1 - η λ_{m i n}$ . Combien de pas faut-il pour diviser cet écart par 2? Donnez la valeur réelle $ln 2/ (- ln (1 - η λ_{m i n}))$ , sans arrondir à l'entier.

La standardisation avec une bibliothèque

Pour information, scikit-learn sépare les deux temps — apprendre les statistiques, puis les appliquer — et propose une descente stochastique pour la régression linéaire:

from sklearn.preprocessing import StandardScaler
from sklearn.linear_model import SGDRegressor

echelle = StandardScaler().fit(X_entr)          # moyennes et écarts types de l'entraînement
modele = SGDRegressor().fit(echelle.transform(X_entr), y_entr)
y_pred = modele.predict(echelle.transform(X_test))   # mêmes statistiques pour le test

sklearn.pipeline.make_pipeline(StandardScaler(), SGDRegressor()) enchaîne les deux étapes en une chaîne de traitement (pipeline) et garantit que les statistiques de standardisation ne viennent que des données passées à fit.

Descente de gradient stochastique et par mini-lots

Chaque pas de la descente (3.2) calcule le gradient (3.4), qui parcourt les $n$ exemples. Avec huit appartements, c'est instantané. Avec dix millions de courriels, chaque pas coûte dix millions d'évaluations, et il en faut des centaines. Or le gradient de l'erreur moyenne est lui-même une moyenne: $\nabla J (θ) = \frac{1}{n} \sum_{i} \nabla ℓ_{i} (θ)$ , où est la perte sur l'exemple . Et une moyenne s'estime très bien sur un échantillon.

Démonstration. L'indice prend chaque valeur $i$ avec probabilité $1/ n$ , donc $E [\nabla ℓ_{i} (θ)] = \sum_{i = 1}^{n} \frac{1}{n} \nabla ℓ_{i} (θ) = \nabla (\frac{1}{n} \sum_{i} ℓ_{i}) (θ) = \nabla J (θ)$ , par linéarité du gradient. Pour un mini-lot dont chaque élément suit la loi uniforme, la moyenne a pour espérance , par linéarité de l'espérance; l'indépendance des tirages n'est pas nécessaire.

En moyenne, un pas stochastique va donc dans la bonne direction. Mais chaque pas individuel est bruité: sa direction dépend de l'exemple tiré. Pour la régression, $\nabla ℓ_{i} (w) = 2 r_{i} \tilde{x}_{i}$ ne regarde qu'un appartement, et pousse le modèle à passer par ce seul point. L'exercice 3.4 montre que la variance du gradient moyen sur un lot de $b$ exemples tirés indépendamment est divisée par : les mini-lots sont un compromis réglable entre le coût d'un pas et son bruit. En pratique, des lots de quelques dizaines à quelques centaines d'exemples sont courants, notamment parce que le matériel de calcul traite efficacement plusieurs exemples à la fois.

Pourquoi la descente stochastique ne converge-t-elle pas? Au minimum $w^{*}$ , le gradient complet est nul, mais les gradients individuels ne le sont pas: chaque appartement voudrait que la droite passe par lui, et les résidus du chapitre 2 ne sont pas nuls. Chaque pas pousse donc l'itéré hors du minimum, d'une quantité proportionnelle à $η$ . Avec un pas constant, la descente stochastique converge vers un voisinage du minimum, d'autant plus petit que le pas est petit — l'écart quadratique moyen au minimum y est de l'ordre de $η$ —, et elle y erre. Deux remèdes existent. On peut diminuer le pas au fil des époques: si $η_{k} \to 0$ assez lentement — la condition classique est $\sum_{k} η_{k} = \infty$ et , satisfaite par —, la descente stochastique converge vers le minimum d'une fonction strictement convexe, sous des hypothèses de régularité que nous admettons; l'idée remonte à Robbins et Monro (1951). Ou l'on peut , ce qui réduit le bruit. Dans les deux cas, on retrouve que la précision finale se paie.

Le bruit n'est pas qu'un défaut. Sur un problème non convexe, il aide les itérés à quitter des régions plates ou des points selle où la descente ordinaire s'attarderait. Et sur un grand jeu de données, la précision au-delà d'un certain point ne sert à rien: le risque empirique n'est qu'une estimation bruitée du risque réel (chapitre 1), et l'optimiser à $1 0^{- 8}$ près quand l'estimation est incertaine au pourcent près est du travail perdu.

Question 3.5

Complétez epoque(w0, w1, donnees, eta, taille_lot, ordre), qui parcourt les indices de la liste ordre par tranches de taille_lot (la dernière tranche peut être plus courte) et fait, pour chaque tranche, un pas de gradient avec le gradient moyen sur les exemples correspondants. La fonction gradient_mse de la question 3.2 est fournie; elle accepte n'importe quelle liste d'exemples. Le programme entraîne les loyers standardisés par mini-lots de 2, avec $η = 0, 1$ , pendant cinq époques mélangées.

mini_lots.py

Question 3.6

Remettez dans l'ordre les opérations d'un entraînement par mini-lots, telles qu'elles s'exécutent pour la première fois.

Glissez les éléments pour les mettre dans le bon ordre

À la fin de l'époque, mesurer l'erreur de validation et décider s'il faut continuer

Mettre à jour les paramètres d'un pas dans la direction opposée au gradient

Mélanger les indices des exemples d'entraînement au début de l'époque

Séparer l'ensemble de test et calculer moyennes et écarts types sur l'entraînement seulement

Initialiser les paramètres et choisir le pas et la taille des lots

Prendre le mini-lot suivant et calculer le gradient moyen de la perte sur ce lot

Standardiser les caractéristiques d'entraînement avec ces statistiques

Quand s'arrêter

La règle (3.2) ne s'arrête jamais d'elle-même: elle produit une suite infinie. Il faut un critère d'arrêt, et il en existe plusieurs, qu'on combine en pratique.

Un nombre maximal d'itérations (ou d'époques). Il est indispensable, quel que soit le reste: c'est la seule garantie que le programme se termine, même si le pas est trop grand et que la descente diverge.
La norme du gradient: on s'arrête quand $∥ \nabla J (θ^{(k)})∥ < ε$ . C'est le critère naturel, puisque le gradient est nul au minimum, et le théorème 3.7 dit ce qu'il garantit.
La stagnation du coût: on s'arrête quand $J$ ne diminue plus que d'une fraction relative inférieure à un seuil, par exemple $(J^{(k - 1)} - J^{(k)}) / J^{(k - 1)} < 1 0^{- 6}$ . Ce critère est commode mais trompeur sur un problème mal conditionné: dans la vallée de l'exemple 3.3, le coût diminue très peu à chaque pas alors que l'on est encore loin du minimum.

Démonstration. Écrivons $e = θ - θ^{*} = \sum_{j} u_{j} q_{j}$ dans la base propre de . Le gradient vaut , donc , ce qui donne la première inégalité. Pour la seconde, développons autour de son minimum: comme , on vérifie que . Or pour tout , puisque . Donc .

La garantie est faible exactement là où on en aurait besoin: elle est divisée par $λ_{m i n}$ . Sur les loyers standardisés, $λ_{m i n} = 2$ et un gradient de norme $1 0^{- 3}$ garantit une distance au minimum inférieure à $5 \cdot 1 0^{- 4}$ . Sur les loyers bruts, , et après 2 000 pas de pas le gradient a encore une norme de : la borne (3.15) donne une distance au plus , et c'est bien la distance réelle, à quelques millionièmes près, parce que l'écart restant est presque entièrement dans la direction lente. Un critère d'arrêt n'est jamais meilleur que le conditionnement du problème.

Question 3.7

Complétez descente(gradient, theta0, eta, tolerance, max_iter), qui applique la règle (3.2) à une fonction gradient recevant et renvoyant une liste. Elle part d'une copie de theta0, s'arrête dès que la norme du gradient au point courant est inférieure à tolerance, ne fait jamais plus de max_iter pas, et renvoie le couple (theta, nombre de pas effectues). Le programme l'applique aux loyers standardisés, puis aux loyers bruts.

arret.py

import math

loyers = [(30, 1200), (45, 1550), (50, 1380), (62, 1840),
        (70, 1750), (85, 2350), (95, 2250), (110, 2900)]
n = len(loyers)
moyenne = sum(x for x, y in loyers) / n
ecart = math.sqrt(sum((x - moyenne) ** 2 for x, y in loyers) / n)
standardises = [((x - moyenne) / ecart, y) for x, y in loyers]

def gradient_mse(w0, w1, exemples):
  g0, g1 = 0.0, 0.0
  for x, y in exemples:
      r = w0 + w1 * x - y
      g0 += 2 * r
      g1 += 2 * r * x
  return [g0 / len(exemples), g1 / len(exemples)]

def norme(v):
  return math.sqrt(sum(c * c for c in v))

def descente(gradient, theta0, eta, tolerance, max_iter):
  # A completer: partir d'une COPIE de theta0; avant chaque pas,
  # s'arreter si la norme du gradient est inferieure a tolerance;
  # ne jamais faire plus de max_iter pas. Renvoyer (theta, nombre de pas).
  return theta0, 0

theta, k = descente(lambda t: gradient_mse(t[0], t[1], standardises),
                  [0.0, 0.0], 0.1, 1e-3, 10000)
print("standardise: %d pas, w0 = %.3f, w1 = %.3f" % (k, theta[0], theta[1]))
theta, k = descente(lambda t: gradient_mse(t[0], t[1], loyers),
                  [0.0, 0.0], 1.8e-4, 1e-3, 2000)
print("brut: %d pas, w0 = %.3f, w1 = %.3f" % (k, theta[0], theta[1]))

Au-delà de la descente simple

Moment et méthodes adaptatives

La descente de gradient de ce chapitre est la brique de base, mais on l'utilise rarement telle quelle pour entraîner de grands modèles. Deux familles d'améliorations sont si répandues qu'il faut en connaître les noms; leurs règles de mise à jour sont écrites au chapitre 11, et nous n'en donnons ici que l'idée.

La méthode du moment (momentum, aussi appelée méthode de la boule pesante, heavy ball) donne une inertie aux itérés: chaque pas ajoute au gradient courant une fraction du pas précédent. Dans une vallée étroite, les composantes du zigzag, de signes alternés, se compensent d'un pas à l'autre, tandis que la composante le long du fond, toujours de même signe, s'accumule. La méthode accélère donc précisément là où la descente simple est lente, sur les problèmes mal conditionnés.

Les méthodes adaptatives donnent à chaque paramètre son propre pas, d'autant plus petit que les gradients récents de ce paramètre ont été grands. La plus utilisée est Adam (adaptive moment estimation, Kingma et Ba, 2015), qui combine cette adaptation avec un moment. Elle répond à la remarque sur les unités faite après la définition 3.1: un même $η$ pour des paramètres d'échelles différentes est un mauvais compromis, et Adam rééchelonne chaque coordonnée. Elle ne dispense pas de standardiser les caractéristiques, mais elle rend l'entraînement moins sensible au choix du pas, ce qui explique son succès pour les réseaux de neurones.

Minima locaux et problèmes non convexes

Tout ce qui précède s'appuie sur la convexité. Sans elle, la descente de gradient peut s'arrêter en un point qui n'est pas le meilleur.

Le plus petit exemple tient en une variable. La fonction $J (θ) = θ^{4} - 4 θ^{2} + θ$ a trois points critiques, que l'on trouve en résolvant $J^{'} (θ) = 4 θ^{3} - 8 θ + 1 = 0$ par dichotomie: un minimum global en , où ; un maximum local en ; et un minimum local en , où seulement. Avec le pas et deux cents itérations, la descente partie de atteint le minimum global; partie de , elle s'arrête au minimum local. Les deux points de départ sont de part et d'autre du maximum, et c'est tout ce qui compte: , et rien dans le gradient au point d'arrivée — nul dans les deux cas — ne signale le moins bon.

Ce n'est pas une curiosité. La fonction de coût d'un réseau de neurones à couches cachées n'est pas convexe (chapitre 10): elle a de nombreux points critiques, et deux entraînements partis de deux initialisations aléatoires aboutissent à des poids différents. L'algorithme des $K$ -moyennes du chapitre 12, qui n'est pas une descente de gradient mais minimise lui aussi une fonction non convexe, peut s'arrêter sur une partition trois fois moins bonne que la meilleure selon les centres de départ. Les remèdes pratiques — relancer depuis plusieurs initialisations, initialiser intelligemment, utiliser le bruit de la descente stochastique — sont présentés dans ces chapitres. Pour les grands réseaux, l'expérience accumulée suggère que les minima locaux médiocres posent moins de problèmes en pratique que les régions plates et les points selle, où le gradient est petit sans que l'on soit près d'un minimum; c'est un constat empirique, que la théorie n'explique encore que partiellement.

Synthèse

La descente de gradient $θ^{(k + 1)} = θ^{(k)} - η \nabla J (θ^{(k)})$ minimise une fonction de coût sans formule close, en suivant la direction de plus forte descente; pour l'erreur quadratique moyenne, $\nabla J (w) = \frac{2}{n} \tilde{X}^{⊤} (\tilde{X} w - y)$ et la hessienne vaut .

Série d'exercices du chapitre 3Exercice 1 sur 5

Question 3.8

On minimise $J (θ) = 4 θ^{2} + 3$ par descente de gradient. Quel est le plus grand pas $η$ en dessous duquel la descente converge pour tout point de départ?

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Exercice 3.1 · Un pas de descente à la main

On considère trois exemples $(x, y)$ : $(0, 1)$ , $(1, 2)$ et $(2, 6)$ , et le modèle $f (x) = w_{0} + w_{1} x$ avec l'erreur quadratique moyenne.

Exercice 3.2 · Cinq pas sur une parabole

On minimise $J (θ) = 5 (θ - 2)^{2}$ en partant de $θ^{(0)} = 0$ .

Montrez que $θ^{(k + 1)} - 2 = (1 - 10 η) (θ^{(k)} - 2)$ .

Exercice 3.3 · Changer d'unité ne suffit pas

On exprime la surface des loyers en centaines de m², $u_{i} = x_{i} /100$ , sans la centrer.

Calculez la hessienne de l'erreur quadratique moyenne du modèle $w_{0} + w_{1} u$ , à l'aide de et .

Exercice 3.4 · Le bruit d'un mini-lot

On note $g_{i} = \nabla ℓ_{i} (θ)$ le gradient de la perte de l'exemple $i$ en un point $θ$ fixé, $\overset{ˉ}{g} = \frac{1}{n} \sum_{i} g_{i} = \nabla J (θ)$ , et l'on s'intéresse à une composante réelle de ces vecteurs, de moyenne et de variance .

Exercice 3.5 · Le meilleur pas fixe (démonstration)

Sous les hypothèses du théorème 3.5, on note $ρ (η) = max (∣ 1 - η λ_{m a x} ∣, ∣ 1 - η λ_{m i n} ∣)$ et .

Références

Goodfellow, I., Bengio, Y. et Courville, A., Deep Learning, MIT Press, 2016, chap. 4 (optimisation par le gradient, conditionnement) et chap. 8 (descente stochastique, moment, méthodes adaptatives).
Shalev-Shwartz, S. et Ben-David, S., Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, chap. 14 (descente de gradient stochastique et ses garanties pour les problèmes convexes).
Murphy, K. P., Probabilistic Machine Learning: An Introduction, MIT Press, 2022, chap. 8 (optimisation: convexité, descente de gradient, méthodes stochastiques).
Azencott, C.-A., Introduction au Machine Learning, Dunod, 2ᵉ éd., 2022 (la descente de gradient et la régression linéaire, en français).
Robbins, H. et Monro, S., «A Stochastic Approximation Method», The Annals of Mathematical Statistics, 1951 (l'article fondateur de l'approximation stochastique et des pas décroissants).

Itéré $k$	$w_{0}^{(k)}$ (CHF)	$w_{1}^{(k)}$ (CHF)	$J (w^{(k)})$ (CHF²)
0	0	0	3 898 750,00
1	380,50	101,968	2 502 151,30
2	684,90	183,542	1 608 328,14
3	928,42	248,801	1 036 281,31
10	1 698,22	455,094	64 036,08
30	1 900,14	509,207	19 315,12

$η$	$1 - 2 η$	$w_{0}^{(1)}$	$w_{0}^{(10)}$	$w_{0}^{(30)}$	$J (w^{(30)})$ (CHF²)
$0, 01$	$0, 98$	38,05	348,02	864,72	1 173 648,98
$0, 1$	$0, 8$	380,50	1 698,22	1 900,14	19 315,12
$0, 5$	$0$	1 902,50	1 902,50	1 902,50	19 309,17
$0, 9$	$- 0, 8$	3 424,50	1 698,22

$k$	1	100	1 000	10 000	100 000
$w_{0}^{(k)}$ (CHF)	0,68	2,61	22,56	184,55	517,36
$w_{1}^{(k)}$ (CHF/m²)	51,47	26,87	26,61	24,53	20,25

$0, 05$	$0, 5$	1	1,5	1,75	converge, d'un seul côté
$0, 1$	$0$	2	2	2	un seul pas
$0, 15$	$- 0, 5$	3	1,5	2,25	converge en oscillant
$0, 2$	$- 1$	4	0	4	oscille sans fin
$0, 25$	$- 1, 5$	5	−2,5	8,75	diverge en oscillant

Objectifs du chapitre

Minimiser en suivant la pente

Le gradient de l'erreur quadratique moyenne

Les loyers en surface standardisée

Le pas d'apprentissage

Fonctions convexes

Convergence sur une fonction quadratique

Conditionnement et standardisation

Descente de gradient stochastique et par mini-lots

Quand s'arrêter

Au-delà de la descente simple

Moment et méthodes adaptatives

Minima locaux et problèmes non convexes

Synthèse

Exercices

Références

Un modèle sans ordonnée à l'origine

Le pas maximal et la vitesse

Ajouter l'ordonnée à l'origine, en centrant

Le bilan