Démonstration6 min

Pourquoi cette direction, et pourquoi ce signe

Pourquoi on descend dans la direction opposée au gradient, et pas dans une autre.

Depuis deux cours nous écrivons la règle de mise à jour, et nous n'avons jamais prouvé ni pourquoi c'est cette direction, ni pourquoi c'est moins. Nous avons dit « on descend la pente », une formulation qui ne dit rien de vérifiable. Réglons cela.

\theta_{t+1} = \theta_{t} - \eta\,\operatorname{grad}_{\theta}\mathcal{L}(\theta_{t})

(1)

La question précise : parmi toutes les directions possibles, laquelle fait baisser la perte le plus vite ?

Il faut d'abord définir « direction » et « le plus vite ». Une direction est un vecteur $u$ de norme $1$ . La contrainte $\|u\|=1$ est indispensable : sans elle, il suffirait d'allonger $u$ pour faire baisser la perte davantage, et la question n'aurait pas de réponse.

Le signe, en une variable : les trois cas

Commençons par une seule variable, où tout se voit. Soit $f$ dérivable en $\theta$ , et le pas $\theta_{t+1}=\theta_t-\eta f'(\theta_t)$ avec $\eta>0$ . Trois cas, et trois seulement.

Cas	Où faut-il aller	Signe du pas	Verdict
$f'(\theta_t) > 0$	la fonction croît : vers la gauche	négatif	✓
$f'(\theta_t) < 0$	la fonction décroît : vers la droite	positif	✓
$f'(\theta_t) = 0$	nulle part	nul, l'algorithme s'arrête	✓

Le signe moins n'est pas une convention : il est imposé par l'exigence « aller là où f décroît », dans chacun des trois cas. Le troisième cas est aussi ce qui fait s'arrêter l'algorithme à un maximum ou à un point selle, ce qu'on ne veut pas.

La direction, en p variables

DérivationL'opposé du gradient est la direction de plus forte décroissance

Hypothèses

$f$ de $\mathbb{R}^p$ dans $\mathbb{R}$ est différentiable en $\theta$
$g=\operatorname{grad}f(\theta)$ est non nul
$u$ parcourt la sphère unité, c'est-à-dire $\|u\|=1$

Point de départ

D_{u}f(\theta) \;=\; \lim_{h\to 0^{+}}\frac{f(\theta+hu)-f(\theta)}{h}

Chaîne de dépendances

u → θ + h u → f(θ + h u)

Propriétés utilisées

La définition de la différentiabilité : $f(\theta+h)=f(\theta)+\langle g,h\rangle+o(\|h\|)$
L'inégalité de Cauchy-Schwarz et son cas d'égalité

Étapes

On applique la différentiabilité avec l'accroissement $h\,u$ , dont la norme vaut $h$ puisque $u$ est unitaire.
$f(\theta+hu)=f(\theta)+h\,\langle g,u\rangle+o(h)$
définition de la différentiabilité
On soustrait $f(\theta)$ , on divise par $h>0$ , et on fait tendre $h$ vers zéro. Le terme en $o(h)/h$ disparaît.
$D_{u}f(\theta)=\langle g,u\rangle$
passage à la limite
Cauchy-Schwarz encadre ce produit scalaire, pour tout $u$ de norme $1$ .
$-\|g\| \;=\; -\|g\|\,\|u\| \;\le\; \langle g,u\rangle \;\le\; \|g\|\,\|u\| \;=\; \|g\|$
Cauchy-Schwarz, avec la norme de u égale à 1
Le cas d'égalité exige $u$ colinéaire à $g$  ; comme $\|u\|=1$ , les deux seuls candidats sont $\pm g/\|g\|$ . On vérifie directement que la borne est atteinte.
$\left\langle g,\ \frac{g}{\|g\|}\right\rangle=\frac{\langle g,g\rangle}{\|g\|}=\frac{\|g\|^{2}}{\|g\|}=\|g\|$
cas d'égalité de Cauchy-Schwarz, puis calcul direct

Résultat

\arg\min_{\|u\|=1} D_{u}f(\theta) \;=\; -\frac{\operatorname{grad}f(\theta)}{\|\operatorname{grad}f(\theta)\|}, \qquad D_{u}f=-\|\operatorname{grad}f(\theta)\|

Interprétation

La direction opposée au gradient n'est pas une bonne direction : c'est la meilleure, et la borne qu'elle atteint vaut exactement $\|\operatorname{grad}f\|$ . Ce nombre est donc à la fois la pente maximale et la mesure de « à quel point on n'est pas à un point critique ».

Ce que ce résultat ne dit pas

La preuve est locale : elle ne dit rien au-delà d'un déplacement infinitésimal. Rien ne garantit qu'un pas fini fasse baisser la perte. C'est l'objet de la page 4.
Elle suppose $f$ différentiable. La ReLU ne l'est pas en zéro (page 7).
« Plus forte décroissance » est relatif à la norme euclidienne. Changer de norme change la direction optimale : c'est l'idée qui donnera plus tard le gradient naturel.

La borne est-elle serrée ?

La preuve dit que $\langle g,u\rangle\le\|g\|$ . Une borne peut être vraie et molle. Mesurons : réseau $784\to128\to10$ , initialisation Xavier, graine 0, 512 exemples ; on calcule $g$ dans $\mathbb{R}^{101\,770}$ , puis on tire 2000 directions unitaires au hasard.

python cours/lecon3/experiences.py E1

  p = 101770          ||grad|| = 0.940183

  Derivee directionnelle <grad, u> pour 2000 directions unitaires tirees au hasard :
    maximum observe        0.012205
    minimum observe        -0.008903
    ecart-type             0.002975
    borne theorique +||g||  0.940183
    meilleure direction tiree / borne = 0.0130

  Direction u = grad/||grad||    <grad, u> = 0.940183   (= ||grad||)
  Direction u = -grad/||grad||   <grad, u> = -0.940183   (= -||grad||)

  Effet reel d'un pas de 0.0001 (perte de depart 2.414597) :
    direction           L(theta + eps u)     variation   prevue eps<g,u>
    +grad/||grad||            2.41469140      9.40e-05          9.40e-05
    -grad/||grad||            2.41450336     -9.40e-05         -9.40e-05
    aleatoire 1               2.41459749      1.28e-07          1.28e-07
    aleatoire 2               2.41459712     -2.49e-07         -2.49e-07
    aleatoire 3               2.41459727     -9.86e-08         -9.86e-08

Lecture

La meilleure des 2000 directions tirées atteint $0{,}012205$ , soit 1,30 % de la borne. Tirer au hasard dans $\mathbb{R}^{101\,770}$ ne trouve rien : c'est la concentration de la mesure en grande dimension, où deux vecteurs tirés indépendamment sont presque orthogonaux.
La direction du gradient atteint $0{,}940183$ , c'est-à-dire exactement $\|g\|$ , au chiffre près. La borne n'est pas molle : elle est atteinte.
Les deux dernières colonnes valident le développement limité : la variation mesurée et la variation prévue coïncident sur trois chiffres significatifs, pour les cinq directions.

Deux panneaux. À gauche, l'histogramme des produits scalaires de 4000 directions tirées au hasard avec le gradient : toutes tiennent entre moins 0,009 et plus 0,012, et une flèche indique que la direction du gradient, à 0,940, se trouve 77 fois plus loin, hors du cadre. À droite, la variation de la perte en fonction de la longueur du pas dans cinq directions : la droite montante est le gradient, la droite descendante son opposé, et les trois directions tirées au hasard sont plates à cette échelle. — La figure prolonge le même tirage jusqu'à 4000 directions, les 2000 premières étant celles du tableau ; la meilleure y vaut toujours $0{,}0122$ , soit 77 fois moins que la borne. (a) L'histogramme est à son échelle : le placer dans le même cadre que la borne l'écraserait à un pixel, et c'est justement l'information. (b) Seule la direction opposée au gradient fait baisser la perte ; les directions au hasard ont un effet plus de mille fois plus petit.

La même chose en deux dimensions, où le gradient se dessine : perpendiculaire à la ligne de niveau qu'il traverse, et d'autant plus long que les lignes sont serrées.

0:00 / 0:22

Vérification rapide n° 9

Dans la sortie ci-dessus, le produit scalaire $\langle g,u\rangle$ pour la direction aléatoire n° 2 vaut $-2{,}49\cdot10^{-3}$ , puisque la variation à $\varepsilon=10^{-4}$ vaut $-2{,}49\cdot10^{-7}$ .

a
Quelle est la valeur du cosinus de l'angle entre cette direction et le gradient ? Donne le calcul.
b
À quel angle en degrés cela correspond-il ? Que dis-tu de cet angle ?

Aucune réponse à cliquer : il y a un calcul à faire.

Le signe, en une variable : les trois cas

Commençons par une seule variable, où tout se voit. Soit $f$ dérivable en $\theta$ , et le pas $\theta_{t+1}=\theta_t-\eta f'(\theta_t)$ avec $\eta>0$ . Trois cas, et trois seulement.

Cas	Où faut-il aller	Signe du pas	Verdict
$f'(\theta_t) > 0$	la fonction croît : vers la gauche	négatif	✓
$f'(\theta_t) < 0$	la fonction décroît : vers la droite	positif	✓
$f'(\theta_t) = 0$	nulle part	nul, l'algorithme s'arrête	✓

La direction, en p variables

DérivationL'opposé du gradient est la direction de plus forte décroissance

Hypothèses

$f$ de $\mathbb{R}^p$ dans $\mathbb{R}$ est différentiable en $\theta$
$g=\operatorname{grad}f(\theta)$ est non nul
$u$ parcourt la sphère unité, c'est-à-dire $\|u\|=1$

Point de départ

D_{u}f(\theta) \;=\; \lim_{h\to 0^{+}}\frac{f(\theta+hu)-f(\theta)}{h}

Chaîne de dépendances

u → θ + h u → f(θ + h u)

Propriétés utilisées

La définition de la différentiabilité : $f(\theta+h)=f(\theta)+\langle g,h\rangle+o(\|h\|)$
L'inégalité de Cauchy-Schwarz et son cas d'égalité

Étapes

On applique la différentiabilité avec l'accroissement $h\,u$ , dont la norme vaut $h$ puisque $u$ est unitaire.
$f(\theta+hu)=f(\theta)+h\,\langle g,u\rangle+o(h)$
définition de la différentiabilité
On soustrait $f(\theta)$ , on divise par $h>0$ , et on fait tendre $h$ vers zéro. Le terme en $o(h)/h$ disparaît.
$D_{u}f(\theta)=\langle g,u\rangle$
passage à la limite
Cauchy-Schwarz encadre ce produit scalaire, pour tout $u$ de norme $1$ .
$-\|g\| \;=\; -\|g\|\,\|u\| \;\le\; \langle g,u\rangle \;\le\; \|g\|\,\|u\| \;=\; \|g\|$
Cauchy-Schwarz, avec la norme de u égale à 1
Le cas d'égalité exige $u$ colinéaire à $g$  ; comme $\|u\|=1$ , les deux seuls candidats sont $\pm g/\|g\|$ . On vérifie directement que la borne est atteinte.
$\left\langle g,\ \frac{g}{\|g\|}\right\rangle=\frac{\langle g,g\rangle}{\|g\|}=\frac{\|g\|^{2}}{\|g\|}=\|g\|$
cas d'égalité de Cauchy-Schwarz, puis calcul direct

Résultat

\arg\min_{\|u\|=1} D_{u}f(\theta) \;=\; -\frac{\operatorname{grad}f(\theta)}{\|\operatorname{grad}f(\theta)\|}, \qquad D_{u}f=-\|\operatorname{grad}f(\theta)\|

Interprétation

Ce que ce résultat ne dit pas

La preuve est locale : elle ne dit rien au-delà d'un déplacement infinitésimal. Rien ne garantit qu'un pas fini fasse baisser la perte. C'est l'objet de la page 4.
Elle suppose $f$ différentiable. La ReLU ne l'est pas en zéro (page 7).
« Plus forte décroissance » est relatif à la norme euclidienne. Changer de norme change la direction optimale : c'est l'idée qui donnera plus tard le gradient naturel.

La borne est-elle serrée ?

python cours/lecon3/experiences.py E1

  p = 101770          ||grad|| = 0.940183

  Derivee directionnelle <grad, u> pour 2000 directions unitaires tirees au hasard :
    maximum observe        0.012205
    minimum observe        -0.008903
    ecart-type             0.002975
    borne theorique +||g||  0.940183
    meilleure direction tiree / borne = 0.0130

  Direction u = grad/||grad||    <grad, u> = 0.940183   (= ||grad||)
  Direction u = -grad/||grad||   <grad, u> = -0.940183   (= -||grad||)

  Effet reel d'un pas de 0.0001 (perte de depart 2.414597) :
    direction           L(theta + eps u)     variation   prevue eps<g,u>
    +grad/||grad||            2.41469140      9.40e-05          9.40e-05
    -grad/||grad||            2.41450336     -9.40e-05         -9.40e-05
    aleatoire 1               2.41459749      1.28e-07          1.28e-07
    aleatoire 2               2.41459712     -2.49e-07         -2.49e-07
    aleatoire 3               2.41459727     -9.86e-08         -9.86e-08

Lecture

La meilleure des 2000 directions tirées atteint $0{,}012205$ , soit 1,30 % de la borne. Tirer au hasard dans $\mathbb{R}^{101\,770}$ ne trouve rien : c'est la concentration de la mesure en grande dimension, où deux vecteurs tirés indépendamment sont presque orthogonaux.
La direction du gradient atteint $0{,}940183$ , c'est-à-dire exactement $\|g\|$ , au chiffre près. La borne n'est pas molle : elle est atteinte.
Les deux dernières colonnes valident le développement limité : la variation mesurée et la variation prévue coïncident sur trois chiffres significatifs, pour les cinq directions.

La figure prolonge le même tirage jusqu'à 4000 directions, les 2000 premières étant celles du tableau ; la meilleure y vaut toujours

0{,}0122

, soit 77 fois moins que la borne. (a) L'histogramme est à son échelle : le placer dans le même cadre que la borne l'écraserait à un pixel, et c'est justement l'information. (b) Seule la direction opposée au gradient fait baisser la perte ; les directions au hasard ont un effet plus de mille fois plus petit.

La même chose en deux dimensions, où le gradient se dessine : perpendiculaire à la ligne de niveau qu'il traverse, et d'autant plus long que les lignes sont serrées.

0:00 / 0:22

Vérification rapide n° 9

a
Quelle est la valeur du cosinus de l'angle entre cette direction et le gradient ? Donne le calcul.
b
À quel angle en degrés cela correspond-il ? Que dis-tu de cet angle ?

Aucune réponse à cliquer : il y a un calcul à faire.

Le signe, en une variable : les trois cas

La direction, en p variables

La borne est-elle serrée ?

Le signe, en une variable : les trois cas

La direction, en p variables

La borne est-elle serrée ?

La borne est-elle serrée ?

La borne est-elle serrée ?