• Projets00
  • AI Academy13
  • Veille07 entrées ces 7 derniers jours
  • Outils00
Profil
Déposer un projet
ProjetsAI AcademyVeilleOutilsProfilDéposer
Le cours
31/59
Démonstration15 min

Descendre, en dimension quelconque

Le gradient, le taux d'apprentissage, et l'algorithme de descente écrit en entier.

Sur une courbe, il n'y a que deux sens : la gauche et la droite. Dans un espace à cent mille dimensions, par où descend-on ?

Une barre horizontale en brique traverse presque toute la largeur ; elle porte à gauche la mention le gradient et à droite sa valeur. Sous elle, une seconde barre grise, si courte qu'elle n'est qu'un trait, porte la mention la meilleure des cent et sa valeur. Dessous se lisent trois lignes : ce qu'elle en atteint avec un pourcentage, la moyenne des cent, et combien dépassent avec le compte zéro sur cent.
Chaque barre est la vitesse à laquelle le coût monte quand on part dans une direction. Cent directions ont été tirées au hasard, et la meilleure des cent est la seconde barre.

En dimension 111, « la pente » est un nombre. En dimension ppp, un point a autant de directions de départ qu'on veut, et un seul nombre ne peut pas les décrire toutes : il faut l'objet qui remplace la dérivée quand θ\boldsymbol{\theta}θ a 101 770101\,770101770 coordonnées.

Trois objets, définis avant d'être employés

Dérivée partiellepartial derivative

Pour C:Rp→RC:\mathbb{R}^{p}\rightarrow\mathbb{R}C:Rp→R et i∈[ ⁣[1,p] ⁣]i\in[\![1,p]\!]i∈[[1,p]], la dérivée en 000 de la fonction d'une variable s↦C(θ+s ei)s\mapsto C(\boldsymbol{\theta}+s\,\mathbf{e}_{i})s↦C(θ+sei​), obtenue en gelant les p−1p-1p−1 autres coordonnées. C'est un scalaire, et il y en a ppp.

∂C∂θi(θ)=lim⁡s→0C(θ+s ei)−C(θ)s ∈R\frac{\partial C}{\partial\theta_{i}}(\boldsymbol{\theta})=\lim_{s\to 0}\frac{C(\boldsymbol{\theta}+s\,\mathbf{e}_{i})-C(\boldsymbol{\theta})}{s}\ \in\mathbb{R}∂θi​∂C​(θ)=s→0lim​sC(θ+sei​)−C(θ)​ ∈R
(8.1)
ei∈Rp\mathbf{e}_{i}\in\mathbb{R}^{p}ei​∈Rp est le iii-ième vecteur de la base canonique. iii désigne une composante, jamais une itération.
Gradientgradient

Le vecteur colonne des ppp dérivées partielles, de même dimension que θ\boldsymbol{\theta}θ. Il est défini quand CCC est de classe C1\mathcal{C}^{1}C1 sur un ouvert, c'est-à-dire quand ses ppp dérivées partielles existent et sont continues.

gradθ C(θ)=(∂C∂θ1(θ), …, ∂C∂θp(θ))T∈Rp\mathrm{grad}_{\boldsymbol{\theta}}\,C(\boldsymbol{\theta})=\left(\frac{\partial C}{\partial\theta_{1}}(\boldsymbol{\theta}),\ \ldots,\ \frac{\partial C}{\partial\theta_{p}}(\boldsymbol{\theta})\right)^{\mathsf{T}}\in\mathbb{R}^{p}gradθ​C(θ)=(∂θ1​∂C​(θ), …, ∂θp​∂C​(θ))T∈Rp
(8.2)
gradθ CD\mathrm{grad}_{\boldsymbol{\theta}}\,C_{\mathcal{D}}gradθ​CD​ est donc une fonction de Rp\mathbb{R}^{p}Rp dans Rp\mathbb{R}^{p}Rp : à chaque point de l'espace des paramètres, elle associe un vecteur de la même taille. Pour le réseau 784→128→10784\rightarrow 128\rightarrow 10784→128→10, c'est un vecteur de 101 770101\,770101770 nombres.
Dérivée directionnelledirectional derivative

Pour u∈Rp\mathbf{u}\in\mathbb{R}^{p}u∈Rp avec ∥u∥=1\|\mathbf{u}\|=1∥u∥=1, la vitesse de variation de CCC quand on part de θ\boldsymbol{\theta}θ dans la direction u\mathbf{u}u : DuC(θ)=lim⁡t→0[C(θ+tu)−C(θ)]/tD_{\mathbf{u}}C(\boldsymbol{\theta})=\lim_{t\to 0}\big[C(\boldsymbol{\theta}+t\mathbf{u})-C(\boldsymbol{\theta})\big]/tDu​C(θ)=limt→0​[C(θ+tu)−C(θ)]/t. La dérivée partielle en est le cas u=ei\mathbf{u}=\mathbf{e}_{i}u=ei​.

Ce que le gradient a de particulier

Parmi toutes les directions unitaires de Rp\mathbb{R}^{p}Rp, et il y en a une infinité, une seule fait monter CCC le plus vite, et c'est celle du gradient. Son opposée fait descendre le plus vite. C'est l'énoncé qui justifie tout le procédé, et ce chapitre ne le démontre pas.

Proposition 3.C∈C1, ∥u∥=1 ⟹ DuC(θ)=⟨ gradθ C(θ), u ⟩ ≤ ∥gradθ C(θ)∥\textbf{Proposition 3.}\quad C\in\mathcal{C}^{1},\ \|\mathbf{u}\|=1\ \Longrightarrow\ D_{\mathbf{u}}C(\boldsymbol{\theta})=\big\langle\,\mathrm{grad}_{\boldsymbol{\theta}}\,C(\boldsymbol{\theta}),\ \mathbf{u}\,\big\rangle\ \leq\ \big\|\mathrm{grad}_{\boldsymbol{\theta}}\,C(\boldsymbol{\theta})\big\|Proposition 3.C∈C1, ∥u∥=1 ⟹ Du​C(θ)=⟨gradθ​C(θ), u⟩ ≤ ​gradθ​C(θ)​
(8.3)
L'énoncé suppose grad C(θ)≠0\mathrm{grad}\,C(\boldsymbol{\theta})\neq\mathbf{0}gradC(θ)=0, sans quoi toutes les directions se valent. L'égalité est atteinte quand u\mathbf{u}u est colinéaire au gradient et de même sens, donc la direction de plus forte croissance est celle du gradient. Appliquée à −u-\mathbf{u}−u, la même majoration donne DuC≥−∥grad∥D_{\mathbf{u}}C\geq-\|\mathrm{grad}\|Du​C≥−∥grad∥, avec égalité pour u\mathbf{u}u colinéaire au gradient et de sens opposé : c'est ce second pas, et lui seul, qui justifie le signe moins de l'algorithme.

Cette proposition est admise, et voici ce qui manque pour la démontrer

Deux outils, et aucun n'est disponible ici. L'approximation au premier ordre en plusieurs variables, qui donne C(θ+tu)=C(θ)+t⟨grad C,u⟩+o(t)C(\boldsymbol{\theta}+t\mathbf{u})=C(\boldsymbol{\theta})+t\langle\mathrm{grad}\,C,\mathbf{u}\rangle+o(t)C(θ+tu)=C(θ)+t⟨gradC,u⟩+o(t) et établit la première égalité. Et l'inégalité de Cauchy-Schwarz, ⟨v,u⟩≤∥v∥ ∥u∥\langle\mathbf{v},\mathbf{u}\rangle\leq\|\mathbf{v}\|\,\|\mathbf{u}\|⟨v,u⟩≤∥v∥∥u∥ avec égalité si et seulement si u\mathbf{u}u et v\mathbf{v}v sont colinéaires de même sens, qui donne la majoration et le cas d'égalité. Les deux appartiennent au cours d'optimisation. Ce chapitre les emprunte et le dit, plutôt que d'écrire une preuve qui s'appuierait sur ce qui n'a pas été posé.

Admettre n'oblige pas à croire sur parole, car l'énoncé se vérifie : on tire cent directions au hasard, on ramène chacune à la longueur 111, ce qu'on appelle la normaliser et qui revient à diviser un vecteur par sa norme, puis on mesure DuCD_{\mathbf{u}}CDu​C pour chacune et on compare à celle du gradient lui-même normalisé. Si la proposition est vraie, aucune ne doit la dépasser.

La mesure se fait au point de départ de la graine 0, celui de la page 4, et sur un échantillon de 2 0482\,0482048 images plutôt que sur les 60 00060\,00060000 : chacune des cent une dérivées demande deux évaluations du coût, et le faire sur le jeu entier coûterait cent fois plus pour un résultat de même forme. La page 9 dira ce qu'un échantillon coûte en exactitude ; ici, il ne sert qu'à comparer cent une directions entre elles, toutes sur le même échantillon.

Cent directions au hasard · cours/lecon3/mesures.py, mesure 8

    C est le coût sur les 2048 exemples de la mesure 4.
    différence finie CENTRÉE, epsilon = 1e-05

    direction du gradient normalisé   D_u C = +1.39887154
    cent directions unitaires tirées au hasard :
      maximum                         +0.02064745
      minimum                         -0.01105809
      moyenne                         -0.00058565
      combien dépassent le gradient   0 sur 100
      rapport max/gradient            0.0148

Lecture

  • ·

    Aucune des cent ne dépasse le gradient, et ce n'est pas juste : la meilleure des cent atteint 1,5 %1{,}5\,\%1,5% de sa valeur.

  • ·

    La moyenne des cent est quasiment nulle, et les valeurs se répartissent de part et d'autre de zéro : une direction tirée au hasard dans R101 770\mathbb{R}^{101\,770}R101770 est presque orthogonale au gradient, donc elle ne fait ni monter ni descendre.

  • ·

    C'est un effet de la dimension, et il se retrouvera page 11 : dans un espace à cent mille dimensions, deux directions tirées indépendamment sont presque toujours presque orthogonales.

La longueur du gradient dit autre chose que sa direction : elle dit la raideur de la pente. Là où cette longueur est grande, une petite modification de θ\boldsymbol{\theta}θ change beaucoup le coût ; là où elle est petite, le coût est plat. Comme la mise à jour est proportionnelle au gradient, les pas rétrécissent d'eux-mêmes quand la pente s'aplatit, à η\etaη constant. La table ci-dessous la suit sur trente époques, sur le jeu entier et sur un réseau qui apprend, et ses valeurs n'ont donc rien à voir avec le 1,39891{,}39891,3989 mesuré plus haut au point de départ sur 2 0482\,0482048 images.

Une courbe descendante sur un axe horizontal gradué de zéro à vingt-neuf, sous la mention époque. L'axe vertical est logarithmique. La courbe part d'une valeur portée en haut à gauche et descend, avec un léger ressaut au milieu, jusqu'à une valeur bien plus basse portée en bas à droite. En haut à droite se lit le rapport entre les deux, précédé d'un signe de division.
Le pas effectif vaut η\etaη fois cette longueur, et η\etaη n'a pas bougé de tout l'entraînement.

La norme du gradient pendant l'entraînement · cours/lecon3/mesures.py, mesure 7

    époque   L_train   acc_train    L_test   acc_test    ||grad||
         0    0.1055     0.9694    0.1195     0.9641    0.087878
         4    0.0329     0.9895    0.0743     0.9777    0.058533
         9    0.0130     0.9963    0.0743     0.9779    0.065720
        19    0.0011     1.0000    0.0729     0.9816    0.002535
        29    0.0006     1.0000    0.0761     0.9814    0.000833

Lecture

  • ·

    La norme du gradient est divisée par 105105105 entre la première et la dernière époque mesurée. Le pas effectif, η ∥grad∥\eta\,\|\mathrm{grad}\|η∥grad∥, rétrécit dans le même rapport alors que η\etaη n'a pas bougé : c'est le mécanisme annoncé, mesuré.

  • ·

    La précision d'entraînement atteint 1,00001{,}00001,0000 à l'époque 191919, donc le réseau ne se trompe plus sur aucune des 60 00060\,00060000 images qu'il a vues. Le coût d'entraînement continue pourtant de baisser, parce qu'il reste de la confiance à gagner.

  • ·

    Le coût de test, lui, atteint son plus bas à l'époque 191919, 0,07290{,}07290,0729, puis remonte à 0,07610{,}07610,0761. Le réseau continue de s'améliorer sur ce qu'il a vu et commence à se dégrader sur ce qu'il n'a pas vu. Ce chapitre le constate et n'en fait rien : c'est le sujet du chapitre d'évaluation.

L'algorithme, en entier

θt+1=θt−η gradθ CD(θt),η∈R>0\boldsymbol{\theta}_{t+1}=\boldsymbol{\theta}_{t}-\eta\,\mathrm{grad}_{\boldsymbol{\theta}}\,C_{\mathcal{D}}(\boldsymbol{\theta}_{t}),\qquad \eta\in\mathbb{R}_{>0}θt+1​=θt​−ηgradθ​CD​(θt​),η∈R>0​
(8.4)
ttt est une itération, pas une composante. Les deux membres sont des vecteurs de Rp\mathbb{R}^{p}Rp, et la soustraction se fait coordonnée par coordonnée : les 101 770101\,770101770 paramètres sont modifiés en même temps, chacun de sa propre quantité.
TexteLa descente de gradient
1ENTREE   D          le jeu, fixe2         eta        le taux d'apprentissage, dans R_{>0}3         T          le nombre d'iterations4SORTIE   theta      un vecteur de R^p5 61.  theta <- tirage au hasard dans R^p72.  pour t de 0 a T-1 :83.        g <- grad_theta C_D(theta)        un vecteur de R^p94.        theta <- theta - eta * g          p soustractions105.  rendre theta

Cinq lignes. La ligne 333 est celle que ce chapitre ne sait pas exécuter efficacement, et la ligne 444 est celle dont η\etaη décide.

Vérification rapide n° 27

Le gradient a la dimension de ce qu'il dérive.

  1. a

    Quelle est la dimension de gradθ CD(θ)\mathrm{grad}_{\boldsymbol{\theta}}\,C_{\mathcal{D}}(\boldsymbol{\theta})gradθ​CD​(θ) pour le réseau 784→128→10784\rightarrow 128\rightarrow 10784→128→10 ?

  2. b

    Et pour 784→32→32→10784\rightarrow 32\rightarrow 32\rightarrow 10784→32→32→10 ?

  3. c

    La dimension du gradient dépend-elle du nombre d'images du jeu ? Justifier à partir de (6.1)(6.1)(6.1).

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

Le taux d'apprentissage

η\etaη est le taux d'apprentissage : la longueur dont on recule à chaque pas, une fois la direction choisie. C'est le η\etaη que le chapitre 1 appelait le pas d'apprentissage, et le seul nombre de tout le procédé qu'un humain fixe encore à la main.

La proposition 2 de la page 7 garantit que le coût baisse pour η\etaη assez petit, sans dire ce que « assez petit » veut dire. Elle a été écrite en dimension un, et elle vaut mot pour mot en dimension ppp : il suffit de remplacer C′(θt)2C'(\theta_{t})^{2}C′(θt​)2 par ∥grad∥2\|\mathrm{grad}\|^{2}∥grad∥2, et le développement au premier ordre d'une variable par celui de plusieurs, c'est-à-dire par le premier des deux outils que la proposition 3 emprunte au cours d'optimisation. On ne peut donc pas davantage prédire le bon réglage en dimension ppp : on le cherche, sur sept valeurs, cinq époques chacune, à graine égale.

Trois graphes côte à côte montrent la même parabole grise, et les trois partent du même point. Sur le premier, intitulé il remonte, les points brique sautent d'une paroi à l'autre en s'écartant du fond un peu plus à chaque fois ; il porte êta égale un virgule zéro huit. Sur le deuxième, intitulé il descend, les points atteignent le fond en quelques pas ; il porte êta égale zéro virgule trente-cinq. Sur le troisième, intitulé il n'a pas fini, les points restent groupés près du point de départ, très loin du fond ; il porte êta égale zéro virgule zéro deux.
Tracé sur C(θ)=θ2C(\theta)=\theta^{2}C(θ)=θ2, une fonction posée par le cours et non mesurée, parce que c'est celle où le seuil se calcule à la main : la suite y est multipliée par 1−2η1-2\eta1−2η à chaque pas, et elle diverge exactement quand η\etaη dépasse 111.

Sept taux d'apprentissage, 5 époques · cours/lecon3/mesures.py, mesure 3

         eta      L_test    acc_test
       10.000      2.4654    0.0892
        3.000      2.3246    0.1009
        1.000      0.1128    0.9709
        0.500      0.0743    0.9777
        0.100      0.1094    0.9677
        0.010      0.2731    0.9217
        0.001      0.6331    0.8523

Lecture

  • ·

    Trois régimes. Au-dessus de 333, le réseau reste au niveau du hasard, 0,08920{,}08920,0892 et 0,10090{,}10090,1009, à comparer au seuil de 11,35 %11{,}35\,\%11,35% du chapitre 2. Les pas sont si grands qu'ils ne descendent rien : chacun traverse la vallée et remonte plus haut de l'autre côté.

  • ·

    Entre 111 et 0,10{,}10,1, le réseau apprend vite, et le meilleur réglage est η=0,5\eta=0{,}5η=0,5 avec 0,97770{,}97770,9777 en cinq époques.

  • ·

    En dessous de 0,010{,}010,01, il apprend mais n'a pas fini : 0,85230{,}85230,8523 à η=0,001\eta=0{,}001η=0,001, ce qui n'est pas une divergence, c'est une lenteur.

  • ·

    η=10\eta=10η=10 et η=0,001\eta=0{,}001η=0,001 sont tous deux mauvais pour des raisons opposées. Le premier ne converge pas, le second n'a pas eu le temps. Confondre les deux échecs conduirait à corriger dans le mauvais sens.

La même coupe, et cette fois le point de la règle de mise à jour : sans inertie, il s'arrête au premier creux que la bille passait.

La même courbe à deux vallons occupe l'écran, avec ses deux axes nommés. Un point plein de brique se pose sur la pente de gauche, exactement là où la bille avait été lâchée. Un segment de droite vient s'appuyer contre la courbe sous le point, dans le sens de la pente, puis s'efface, et le point saute vers la droite d'une longueur nette. La même chose recommence : une tangente, un saut. Les sauts sont d'abord longs, là où la courbe est raide, puis de plus en plus courts à mesure que la pente s'aplatit, et le point finit par ne plus bouger du tout. Il s'est arrêté au fond du PREMIER vallon, celui que la bille avait traversé sans s'y arrêter, et un trait pointillé descend de lui jusqu'à l'axe pour le marquer. Le second vallon, plus profond, est resté là-bas, intact. Le point se reporte alors sur la paroi de ce second vallon et recommence avec des sauts beaucoup plus longs : cette fois il enjambe le fond au lieu de l'atteindre, se retrouve sur la pente d'en face, repart dans l'autre sens et l'enjambe encore. Cinq sauts durant, il passe d'une paroi à l'autre sans jamais toucher le creux qu'il traverse, et il finit plus haut qu'il n'était parti.

0:00 / 0:18

Dette du chapitre 2 réglée : $\eta=0{,}05$ contre $\eta=0{,}5$

Le chapitre 2 employait η=0,5\eta=0{,}5η=0,5 pour son réseau à ReLU\mathrm{ReLU}ReLU et η=0,05\eta=0{,}05η=0,05 pour son réseau sans activation, qui divergeait à 0,50{,}50,5, sans dire pourquoi. La réponse est dans la table ci-dessus, et elle tient en une phrase : le bon η\etaη dépend de la fonction qu'on descend, il n'y a pas de valeur universelle, et on le cherche par balayage. Le seuil exact au-delà duquel une descente diverge se calcule, mais il demande la courbure de CCC au point courant : c'est une dette vers le chapitre d'optimisation.

Vérification rapide n° 28

Le taux 101010 et le taux 0,0010{,}0010,001 donnent tous deux un mauvais résultat.

  1. a

    Les deux échecs sont-ils de même nature ? Répondre à partir des deux colonnes de la table.

  2. b

    Que se passerait-il si l'on entraînait dix fois plus longtemps avec η=0,001\eta=0{,}001η=0,001 ? Et avec η=10\eta=10η=10 ?

  3. c

    Le seuil de bascule est entre 111 et 333. Ce seuil est-il une propriété de la descente de gradient, ou de cette fonction-là ?

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

Comment on obtient ce vecteur, et pourquoi ce n'est pas comme ça

La ligne 333 de l'algorithme demande 101 770101\,770101770 dérivées partielles. Il existe un procédé qui les donne toutes, qui ne demande que des propagations avant, et qui ne suppose rien sur la forme de CCC : remplacer la limite de (8.1)(8.1)(8.1) par un quotient à ε\varepsilonε fini.

Différence finie centréecentral finite difference

L'approximation ∂C∂θi(θ)≈C(θ+εei)−C(θ−εei)2ε\dfrac{\partial C}{\partial\theta_{i}}(\boldsymbol{\theta})\approx\dfrac{C(\boldsymbol{\theta}+\varepsilon\mathbf{e}_{i})-C(\boldsymbol{\theta}-\varepsilon\mathbf{e}_{i})}{2\varepsilon}∂θi​∂C​(θ)≈2εC(θ+εei​)−C(θ−εei​)​, pour ε>0\varepsilon>0ε>0 petit. Centrée parce qu'elle évalue de part et d'autre du point ; l'erreur y est en ε2\varepsilon^{2}ε2 au lieu de ε\varepsilonε pour la version décentrée.

Une courbe en cuvette. Deux ronds brique y sont posés de part et d'autre d'un même point, sous les mentions thêta moins epsilon et thêta plus epsilon, et un trait brique joint les deux ronds. À droite du graphe, une colonne donne le compte : par composante, deux fois cent un mille sept cent soixante-dix, soit deux cent trois mille cinq cent quarante propagations ; puis, sous la mention au chapitre 4, une propagation.
Le tracé est posé par le cours ; les deux comptes de propagations, eux, sont ceux du réseau.
∂C∂θi(θ) ≈ C(θ+εei)−C(θ−εei)2ε,ε=10−5\frac{\partial C}{\partial\theta_{i}}(\boldsymbol{\theta})\ \approx\ \frac{C(\boldsymbol{\theta}+\varepsilon\mathbf{e}_{i})-C(\boldsymbol{\theta}-\varepsilon\mathbf{e}_{i})}{2\varepsilon},\qquad \varepsilon=10^{-5}∂θi​∂C​(θ) ≈ 2εC(θ+εei​)−C(θ−εei​)​,ε=10−5
(8.5)
Toutes les mesures de ce chapitre emploient ce procédé, et il est exact à la précision voulue : la mesure 8 ci-dessus l'a utilisé pour les cent une dérivées directionnelles.

Ce que coûte un gradient par différences finies · cours/lecon3/mesures.py, mesure 9

    une propagation avant sur 2048 exemples     26.3 ms
    UNE composante par différence centrée      50.2 ms   (2 propagations)
    p                                          101770 composantes
    propagations avant pour UN gradient        203540
    temps estimé pour UN gradient             5113 s, soit 1.42 h
    l'algorithme du chapitre 4 en demande      1 propagation avant
    rapport                                    203 540

    Un entraînement de 30 époques compte 28 140 mises à jour.
    Par différences finies, il demanderait     5 années de calcul.

Lecture

  • ·

    Un seul gradient demande 203 540203\,540203540 propagations avant, soit une heure et demie sur ce poste, pour un pas parmi 28 14028\,14028140. Ces 28 14028\,14028140 pas ne sont pas ceux de l'algorithme écrit plus haut, qui n'en ferait que trente en trente époques : ce sont ceux de l'entraînement réel, qui découpe chaque époque en lots de 646464 images et fait donc 938938938 pas par époque. La page 9 dit pourquoi.

  • ·

    L'entraînement complet demanderait environ cinq années de calcul, quand le même entraînement avec l'algorithme du chapitre 4 prend une minute.

  • ·

    Le procédé n'est pas faux, puisque c'est celui qui a produit toutes les vérifications de ce chapitre. Il est correct et inutilisable, et c'est une distinction qu'il faut savoir faire.

Ce chiffre est le sujet du chapitre suivant

203 540203\,540203540 contre 111. Il existe un algorithme qui obtient les 101 770101\,770101770 composantes en une seule propagation avant et une seule passe en sens inverse, exactement et non approximativement. Tout ce chapitre l'a utilisé sans le nommer : c'est lui qui a entraîné les réseaux dont les mesures sortent. Le chapitre 4 dit ce qu'il fait, et le chapitre 5 le calcule.

Leçon suivante
PrécédenteDescendre, en dimension unSuivantePourquoi on n'utilise pas tout le jeu