Démonstration6 min

Le pas d'apprentissage

Jusqu'où on peut allonger le pas avant que la descente cesse de descendre.

La page 2 n'a prouvé qu'une chose locale : la direction. Il ne dit rien du pas fini $\eta$ . Prenons donc la fonction la plus simple qui ait un minimum, et calculons tout.

DérivationLe seuil exact de convergence sur un quadratique

Hypothèses

$f(\theta)=\tfrac12\lambda\theta^{2}$ avec $\lambda>0$ , de minimum $\theta^{*}=0$
Le pas est constant : $\eta>0$ ne dépend pas de $t$

Point de départ

\theta_{t+1}=\theta_t-\eta f'(\theta_t), \qquad f'(\theta)=\lambda\theta

Propriétés utilisées

La caractérisation de la convergence d'une suite géométrique : $q^t\to0$ si et seulement si $|q|<1$

Étapes

On substitue la dérivée et on factorise :
$\theta_{t+1}=\theta_t-\eta\lambda\theta_t=(1-\eta\lambda)\,\theta_t$
substitution puis factorisation
C'est une suite géométrique de raison $q=1-\eta\lambda$ , dont le terme général s'écrit directement :
$\theta_t=(1-\eta\lambda)^{t}\,\theta_0$
récurrence immédiate
La convergence vers zéro équivaut donc à $|q|<1$ , qu'on résout :
$|1-\eta\lambda|<1 \iff -1<1-\eta\lambda<1 \iff 0<\eta\lambda<2$
définition de la valeur absolue, puis soustraction de 1 et changement de signe

Résultat

0<\eta<\frac{2}{\lambda}

Interprétation

Le seuil ne dépend ni du point de départ, ni du nombre d'itérations : c'est une propriété de la courbure $\lambda$ seule. Plus la fonction est courbée, plus le pas doit être court.

Les quatre régimes, calculés

         eta  1 - eta lambda   |facteur|   theta_0=1 -> theta_1..theta_5
        0.25            0.75        0.75   +0.7500  +0.5625  +0.4219  +0.3164  +0.2373
        0.50            0.50        0.50   +0.5000  +0.2500  +0.1250  +0.0625  +0.0312
        1.00            0.00        0.00   +0.0000  +0.0000  +0.0000  +0.0000  +0.0000
        1.50           -0.50        0.50   -0.5000  +0.2500  -0.1250  +0.0625  -0.0312
        2.00           -1.00        1.00   -1.0000  +1.0000  -1.0000  +1.0000  -1.0000
        2.10           -1.10        1.10   -1.1000  +1.2100  -1.3310  +1.4641  -1.6105

Lecture

$q$ entre 0 et 1 : décroissance monotone.
$q=0$ , soit $\eta=1/\lambda$ : le minimum est atteint en un seul pas. C'est le pas optimal, calculable ici parce que $\lambda$ est connu.
$q$ entre $-1$ et 0 : le signe alterne, on saute par-dessus le minimum à chaque fois, mais on s'en rapproche.
$|q|\ge1$ : à $\eta=2$ exactement, oscillation d'amplitude constante, jamais de convergence. Au-delà, l'écart est multiplié par $1{,}10$ à chaque pas.

En dimension p : la courbure devient un spectre

Généralisons au quadratique multivarié $f(\theta)=\tfrac12\theta^{\top}H\theta$ , avec $H$ symétrique définie positive. Alors $\operatorname{grad}f(\theta)=H\theta$ (vérification des dimensions : $(p\times p)(p\times1)=p\times1$ , et un gradient a bien la dimension de $\theta$ ).

En diagonalisant $H=Q\Lambda Q^{\top}$ et en posant $\tilde\theta=Q^{\top}\theta$ , chaque coordonnée évolue indépendamment selon $\tilde\theta_{i,t}=(1-\eta\lambda_i)^{t}\tilde\theta_{i,0}$ . Le problème se décompose en $p$ problèmes à une variable, chacun avec sa courbure. La convergence exige la condition pour toutes les coordonnées, donc pour la plus grande.

0<\eta<\frac{2}{\lambda_{\max}}, \qquad \kappa=\frac{\lambda_{\max}}{\lambda_{\min}}

(3)

C'est la direction la plus courbée qui plafonne le pas, et la moins courbée qui fixe la vitesse. Le rapport des deux s'appelle le conditionnement.

Sur le réseau : la mesure, et ce qu'elle corrige

python cours/lecon3/experiences2.py E5 · 937 mises à jour, B = 64

           eta   perte finale   pire perte    ||theta||   precision test
         0.001         2.2312         2.56         11.8           0.3883   <- trop lent
      (depart)                                     11.8
         0.010         1.5757         2.47         12.2           0.7240   <- trop lent
         0.100         0.3919         2.39         16.6           0.8950
         0.500         0.2575         2.96         21.0           0.9208
         1.000         0.1958         4.74         25.3           0.9393
         3.000         0.1826         7.07         40.7           0.9410
        10.000         0.6677        17.44        105.2           0.7961   <- degrade
        30.000         5.2892        24.22        441.2           0.2051   <- pire que le hasard
       100.000        24.2415        27.20       2937.1           0.1032   <- pire que le hasard
       300.000        24.6940        27.63      15395.8           0.1010   <- pire que le hasard

Lecture

Une correction que la mesure impose. J'allais écrire « au-delà d'un seuil, la perte diverge ». C'est faux. À aucun $\eta$ testé, jusqu'à 300, la perte ne devient infinie ni indéfinie.
La raison est dans le code : la perte est calculée avec un plancher de $10^{-12}$ sur les probabilités, donc elle ne peut pas dépasser $-\ln(10^{-12})=12\ln10=27{,}63$ . Et l'on mesure exactement $27{,}63$ à $\eta=300$ . Le plafond observé est le plancher numérique, pas une propriété du réseau.
Le vrai témoin de la divergence est la norme des paramètres : $11{,}8 \to 105{,}2 \to 441{,}2 \to 2937{,}1 \to 15\,395{,}8$ , soit un facteur 1305. Les paramètres partent bien à l'infini ; c'est la perte qui ne peut pas les suivre.
Trop petit ( $\eta\le0{,}01$ ) : la norme bouge à peine, et la courbe de perte descend proprement. C'est l'échec difficile à voir, parce qu'il ressemble à un entraînement qui marche.
La plage utile couvre un facteur 30 ( $0{,}1$ à $3$ ). C'est ce qui rend le réglage par tâtonnement praticable.

Deux panneaux. À gauche, en échelle logarithmique, l'écart au minimum pour quatre valeurs du pas sur le quadratique : trois droites descendantes pour les pas convergents, une droite montante pour le pas de 2,10. À droite, les courbes de perte du réseau pour quatre valeurs du pas, avec la norme finale des paramètres en légende, et une ligne horizontale marquant le plafond de calcul à 27,63. — (a) Le seuil exact est visible : au-delà de 2 sur lambda, l'écart au minimum grandit. (b) Sur le réseau, la perte ne renvoie jamais l'infini ; elle plafonne au plancher numérique, pendant que la norme des paramètres passe de 11,8 à 15 396.

DémonstrationRégler le pas, et voir la trajectoire

Vue de dessus

Coût par itération

Pas d'apprentissage0,100Trop lent

Le coût baisse, mais la trajectoire s'arrête avant d'arriver. Rien n'indique l'erreur : c'est l'échec difficile à voir.

La surface est

f(x,y)=\tfrac12 x^{2}+3y^{2}

, de courbures

1

6

: le seuil exact vaut donc

2/6\approx0{,}333

. Descendez à 0,005, la trajectoire s'arrête avant d'arriver ; montez à 0,35, elle sort du cadre. Entre les deux, tout marche.

Vérification rapide n° 11

À $\eta=3$ , la précision est $0{,}9410$ , la meilleure de la table, et la pire perte rencontrée en cours de route est $7{,}07$ , bien au-dessus de $\ln 10=2{,}30$ , la perte d'un réseau qui répondrait au hasard.

a
Comment un entraînement peut-il passer par un état pire que le hasard et finir meilleur que tous les autres ? Donne l'explication en termes de trajectoire.
b
Quelle quantité faudrait-il tracer, en plus de la perte, pour distinguer cette situation d'un vrai début de divergence ?

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

eta 1 - eta lambda |facteur| theta_0=1 -> theta_1..theta_5 0.25 0.75 0.75 +0.7500 +0.5625 +0.4219 +0.3164 +0.2373 0.50 0.50 0.50 +0.5000 +0.2500 +0.1250 +0.0625 +0.0312 1.00 0.00 0.00 +0.0000 +0.0000 +0.0000 +0.0000 +0.0000 1.50 -0.50 0.50 -0.5000 +0.2500 -0.1250 +0.0625 -0.0312 2.00 -1.00 1.00 -1.0000 +1.0000 -1.0000 +1.0000 -1.0000 2.10 -1.10 1.10 -1.1000 +1.2100 -1.3310 +1.4641 -1.6105

En dimension p : la courbure devient un spectre

0<\eta<\frac{2}{\lambda_{\max}}, \qquad \kappa=\frac{\lambda_{\max}}{\lambda_{\min}}

(3)

C'est la direction la plus courbée qui plafonne le pas, et la moins courbée qui fixe la vitesse. Le rapport des deux s'appelle le conditionnement.

Sur le réseau : la mesure, et ce qu'elle corrige

python cours/lecon3/experiences2.py E5 · 937 mises à jour, B = 64

           eta   perte finale   pire perte    ||theta||   precision test
         0.001         2.2312         2.56         11.8           0.3883   <- trop lent
      (depart)                                     11.8
         0.010         1.5757         2.47         12.2           0.7240   <- trop lent
         0.100         0.3919         2.39         16.6           0.8950
         0.500         0.2575         2.96         21.0           0.9208
         1.000         0.1958         4.74         25.3           0.9393
         3.000         0.1826         7.07         40.7           0.9410
        10.000         0.6677        17.44        105.2           0.7961   <- degrade
        30.000         5.2892        24.22        441.2           0.2051   <- pire que le hasard
       100.000        24.2415        27.20       2937.1           0.1032   <- pire que le hasard
       300.000        24.6940        27.63      15395.8           0.1010   <- pire que le hasard

Lecture

Une correction que la mesure impose. J'allais écrire « au-delà d'un seuil, la perte diverge ». C'est faux. À aucun $\eta$ testé, jusqu'à 300, la perte ne devient infinie ni indéfinie.
La raison est dans le code : la perte est calculée avec un plancher de $10^{-12}$ sur les probabilités, donc elle ne peut pas dépasser $-\ln(10^{-12})=12\ln10=27{,}63$ . Et l'on mesure exactement $27{,}63$ à $\eta=300$ . Le plafond observé est le plancher numérique, pas une propriété du réseau.
Le vrai témoin de la divergence est la norme des paramètres : $11{,}8 \to 105{,}2 \to 441{,}2 \to 2937{,}1 \to 15\,395{,}8$ , soit un facteur 1305. Les paramètres partent bien à l'infini ; c'est la perte qui ne peut pas les suivre.
Trop petit ( $\eta\le0{,}01$ ) : la norme bouge à peine, et la courbe de perte descend proprement. C'est l'échec difficile à voir, parce qu'il ressemble à un entraînement qui marche.
La plage utile couvre un facteur 30 ( $0{,}1$ à $3$ ). C'est ce qui rend le réglage par tâtonnement praticable.

(a) Le seuil exact est visible : au-delà de 2 sur lambda, l'écart au minimum grandit. (b) Sur le réseau, la perte ne renvoie jamais l'infini ; elle plafonne au plancher numérique, pendant que la norme des paramètres passe de 11,8 à 15 396.

DémonstrationRégler le pas, et voir la trajectoire

Vue de dessus

Coût par itération

Pas d'apprentissage0,100Trop lent

Le coût baisse, mais la trajectoire s'arrête avant d'arriver. Rien n'indique l'erreur : c'est l'échec difficile à voir.

La surface est

f(x,y)=\tfrac12 x^{2}+3y^{2}

, de courbures

1

6

: le seuil exact vaut donc

2/6\approx0{,}333

. Descendez à 0,005, la trajectoire s'arrête avant d'arriver ; montez à 0,35, elle sort du cadre. Entre les deux, tout marche.

Vérification rapide n° 11

a
Comment un entraînement peut-il passer par un état pire que le hasard et finir meilleur que tous les autres ? Donne l'explication en termes de trajectoire.
b
Quelle quantité faudrait-il tracer, en plus de la perte, pour distinguer cette situation d'un vrai début de divergence ?

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