Le pas, et le bord de la stabilité

Tous les modèles de ce site sont ajustés de la même façon. Régression linéaire, régression logistique, réseau de neurones, transformeur : chacun écrit un nombre qui dit à quel point il se trompe, demande dans quel sens ce nombre descend, et se déplace. Le modèle change ; la boucle, non.

Ce qui change en revanche, et ce qui décide si la boucle prend quarante pas ou explose en trois, c’est la géométrie autour d’elle. Cette leçon porte sur le plus petit morceau de cette géométrie : un pas.

Ce que la boucle minimise

L’entraînement minimise le risque empirique - la perte moyenne sur les données dont on dispose :

$$f(w) \;=\; \frac{1}{n}\sum_{i=1}^{n} \ell\!\left(w; x_i, y_i\right).$$

Les exemples de tout ce parcours utilisent un problème de moindres carrés à $n = 400$ points et deux paramètres, parce que tout y est calculable exactement et comparable à ce que la théorie prétend. Sa perte vaut $f(w) = \frac{1}{n}\lVert Xw - y\rVert^2$, son minimiseur est $w^\star = (1{,}973613 ; -2{,}947388)$, et la perte y vaut $f^\star = 0{,}233943$. Connaître la réponse à l’avance est le principe même : cela transforme chaque affirmation ci-dessous en mesure.

Un gradient sur mini-lot est le gradient complet plus du bruit

Calculer $\nabla f(w)$ suppose de toucher les $n$ exemples. Un mini-lot de taille $B$ en touche $B$ et les moyenne :

$$g_B(w) \;=\; \frac{1}{B}\sum_{i \in \mathcal{B}} \nabla \ell(w; x_i, y_i).$$

Comme $\mathcal{B}$ est un échantillon uniforme, $\mathbb{E}[g_B(w)] = \nabla f(w)$ exactement. Cela mérite d’être énoncé soigneusement, car la croyance inverse - qu’un petit lot pointe vers quelque chose de systématiquement différent - mène à de mauvaises conclusions sur la taille de lot.

À l’origine $w = (0, 0)$, le gradient complet vaut $(-3{,}416495 ; 0{,}179597)$. Moyenner 20 000 mini-lots indépendants en ce même point donne :

La première colonne tend vers zéro parce qu’elle est un résidu de Monte-Carlo dans la moyenne, pas un biais. La seconde raconte la véritable histoire : seize fois le lot achète $1{,}4382 / 0{,}3027 = 4{,}75$ fois la précision, proche du $\sqrt{16} = 4$ que prédit la moyenne de tirages indépendants. L’excédent de 19 % au-dessus de 4 n’est pas du bruit : ces lots sont tirés sans remise dans seulement $n = 400$ points, et le facteur de population finie $(n - B)/(n - 1)$ réduit un lot de 128 bien plus qu’un lot de 8. Cela prédit $4\sqrt{392/272} = 4{,}80$, et un tirage avec remise, réellement indépendant, donne 3,89 à la place. Ce taux de change explique pourquoi les entraînements utilisent de petits lots et beaucoup de pas plutôt que l’inverse. Le calcul achète la précision à la racine carrée, et il achète les pas linéairement.

Le facteur (1 − ηλ)

Venons-en au pas. Au voisinage d’un minimum la perte ressemble à une cuvette quadratique, et la forme de cette cuvette est la hessienne $H$. Écrivons l’erreur $e_t = w_t - w^\star$ ; un pas de gradient de taux $\eta$ donne

$$e_{t+1} \;=\; (I - \eta H)\, e_t .$$

Décomposons $e_t$ selon les vecteurs propres de $H$. Chaque composante est simplement multipliée par $1 - \eta\lambda$, où $\lambda$ est la courbure de cette direction, et les directions n’interagissent pas du tout. Un pas n’est donc pas un mouvement ; c’est autant de contractions indépendantes que la courbure a de directions, chacune à son rythme.

La composante décroît lorsque $\lvert 1 - \eta\lambda \rvert < 1$, soit exactement $\eta < 2/\lambda$. Toute direction doit décroître, donc la contrainte déterminante est la plus raide :

$$\eta \;<\; \frac{2}{L}, \qquad L = \lambda_{\max}(H).$$

La falaise, mesurée

Sur ce problème $L = 1{,}760627$, donc le seuil vaut $2/L = 1{,}135959$. Deux exécutions depuis le même point, deux cents pas chacune :

Deux pour cent d’écart sur le pas séparent une exécution convergée d’une autre à cinq ordres de grandeur. Ce n’est pas une dégradation douce avec une zone grise au milieu ; c’est un changement de signe dans $1 - \eta L$, et dès que ce facteur passe sous $-1$ la direction la plus raide est amplifiée d’un facteur constant à chaque pas, indéfiniment.

La forme pratique de ce phénomène est familière à quiconque a vu une courbe de perte partir en NaN en quelques dizaines de pas après un changement de taux d’apprentissage qui semblait anodin. Rien n’était stable avant de devenir instable : l’exécution a franchi un seuil qui était là depuis le début.

Stable n’est pas synonyme de rapide

Connaître $L$ ne signifie pas poser $\eta = 2/L$. Stabilité et vitesse sont deux questions séparées, et leurs réponses diffèrent.

L’erreur se contracte de $\max\big(\lvert 1 - \eta L\rvert, \lvert 1 - \eta\mu \rvert\big)$ par pas, où $\mu = \lambda_{\min}(H)$ est la direction la plus plate. Augmenter $\eta$ accélère la direction plate et ralentit la raide : le meilleur pas est donc là où les deux coûts se rejoignent,

$$\eta^\star \;=\; \frac{2}{L + \mu}.$$

Ici $\mu = 0{,}073849$, d’où $\eta^\star = 1{,}090230$ - nettement sous le seuil de divergence. Toute taille de pas entre $\eta^\star$ et $2/L$ est plus lente et plus proche de la falaise.

Cette formule mérite vérification plutôt que confiance. Exécuter les mêmes 200 pas pour chacune de 2000 tailles de pas et retenir celle qui finit au plus près de $w^\star$ donne un optimum empirique de 1,088582, contre 1,090230 pour la dérivation - un accord à $1{,}6 \times 10^{-3}$. Ce petit écart ne vient pas de la grille : sur 200 pas seulement, le meilleur pas se situe juste sous l’optimum asymptotique, et s’en rapproche à mesure que l’exécution s’allonge. Une dérivation et une recherche sur grille sont à trois lignes l’une de l’autre, et la grille attrape les erreurs de signe que l’algèbre dissimule.

Ce que cela n’explique pas encore

Deux faits se côtoient mal. Le meilleur pas sur ce problème vaut environ 1,09, et $\mu$ vaut 0,074 : la direction la plus plate ne se déplace donc que de $\eta\mu \approx 8\,\%$ de son erreur résiduelle par pas, même au taux optimal. C’est ce rapport, et non la taille du pas, qui rend l’entraînement lent, et il a un nom et un remède.

Le nom est le conditionnement, et le remède est la leçon suivante.