Fiches › Carte › Partie 03 · Critère et descente › déroulé 01

Descente sur un bol allongé

Un seul exemple, suivi du début à la fin : le jeu colinéaire de D4 passé en ridge à λ = 1. Chaque marche pose une règle de p03-02 à gauche et la chiffre à droite sur la même matrice A = [[15, 28], [28, 57]]. Deux valeurs propres, 1 et 71, décident de tout : de la direction du premier pas, du pas maximal 2/71, du nombre d'itérations, et de la raison pour laquelle on préfère ici résoudre d'un coup.

Ce que ce déroulé suppose acquis
  • La chaîne qu'on applique (p03-02) : direction −∇L, pas η < 2/courbure, convexité, conditionnement κ. Rien n'est redémontré ici : chaque marche pose la règle et la chiffre.
  • D'où viennent A et b (p02-02, exemple 1 de D4) : jeu colinéaire, X⊤X de valeurs propres 0 et 70, le +λI du MAP gaussien qui translate le spectre.
  • Quadratique et gradient. Pour L(β) = ½β⊤Aβ − b⊤β avec A symétrique, ∇L = Aβ − b. C'est la seule dérivation utilisée.
  • Base propre d'une symétrique. Avi = λivi, vecteurs orthogonaux : un système couplé de deux équations y devient deux équations indépendantes.
Hypothèses du déroulé
H1La loss est exactement quadratique : les chiffres sont exacts, pas approchés. C'est le ridge, pas une linéarisation locale. H2Le pas η est fixe : aucune recherche linéaire, aucune mémoire de direction, gradient exact à chaque itération. H3λ = 1, fixé une fois pour toutes. Tous les nombres du déroulé en dépendent : c'est lui qui pose la valeur propre plate à 1 plutôt qu'à 0. H4Le départ est β0 = (0 ; 0) sauf mention contraire. La marche 5 montre que ce choix n'est pas neutre.

Les six marches, sur le même bol

Le décor

Trois observations, deux features dont la seconde vaut le double de la première. Sans pénalité, X⊤X a une valeur propre nulle et la solution n'est pas unique. Ridge à λ = 1 ajoute I, et la loss devient une quadratique à minimum unique :

L(β) = ½β⊤Aβ − b⊤β  ·  A = X⊤X + I  ·  b = X⊤y

« Le jeu est colinéaire et X⊤X a une valeur propre nulle, donc le +λI du prior gaussien la relève à 1, donc la loss pénalisée est une quadratique définie positive dont on peut descendre le bol. »

Au tableau — marche 1

Données de D4 : x1 = (1, 2, 3), x2 = (2, 4, 6) = 2x1, y = (1, 2, 3).

X⊤X = [[14, 28], [28, 56]]  →  A = [[15, 28], [28, 57]]  ·  b = X⊤y = (14 ; 28)

Vérification à la main : 1² + 2² + 3² = 14, 1·2 + 2·4 + 3·6 = 28, 2² + 4² + 6² = 56 ; et X⊤y = (14 ; 28) parce que y = x1.

Un seul objet à descendre pour tout le déroulé : A = [[15, 28], [28, 57]], b = (14 ; 28). Le minimum vaudra L = −6,901.

Le gradient, et où il pointe

Sur une quadratique, ∇L(β) = Aβ − b. Évalué en (0 ; 0) il se réduit à −b, ce qui dit d'un coup d'œil où pointe la pente. La direction de plus forte descente est −∇L normalisé.

∇L(0) = −(14 ; 28)  ·  ‖∇L‖ = √980 = 31,30  ·  u = (14 ; 28)/31,30 = (0,447 ; 0,894)

« Le gradient d'une quadratique vaut Aβ − b, donc en zéro il vaut −b = (−14 ; −28), donc la pente y pointe exactement dans la direction (1 ; 2)/√5, celle où vit tout le signal X⊤y. »

Au tableau — marche 2

(0,447 ; 0,894) est (1 ; 2)/√5 : √5 = 2,236, 1/2,236 = 0,447. Depuis l'origine, la descente viserait donc la droite β1 + 2β2 = 1 — la droite des solutions OLS de D4 — perpendiculairement, en (0,2 ; 0,4), le point de norme minimale de cette droite.

Et c'est un piège. (1 ; 2) est un vecteur propre de A, celui de λ = 71 : partir de l'origine, c'est partir pile sur l'axe raide du bol, celui où la vallée n'existe pas. Ce déroulé part donc de β0 = (1 ; 0), une solution OLS de D4 — un point sans privilège. Le gradient y vaut ∇L(1 ; 0) = (15 − 14 ; 28 − 28) = (1 ; 0). La marche 5 et la troisième limite disent ce que ce choix change.

Les deux courbures tronc

La courbure de L dans une direction est la valeur propre de A associée. Pour une 2×2, trace et déterminant suffisent : λ1 + λ2 = 72 et λ1λ2 = 71.

λ² − 72λ + 71 = 0  ⇒  λ = 1 et 71  ·  κ = 71  ·  ηmax = 2/λmax = 2/71

« La trace vaut 72 et le déterminant 71, donc les valeurs propres sont racines de λ² − 72λ + 71, donc elles valent 1 et 71, donc le conditionnement vaut 71 et le pas admissible s'arrête à 2/71 = 0,028. »

Au tableau — marche 3

Déterminant : 15·57 − 28·28 = 855 − 784 = 71. Trace : 15 + 57 = 72. Les deux vecteurs propres se vérifient en une multiplication :

directionAvλnom
(1 ; 2)(15 + 56 ; 28 + 114) = (71 ; 142)71le mur
(−2 ; 1)(−30 + 28 ; −56 + 57) = (−2 ; 1)1la vallée

La vallée est la direction de colinéarité : sa courbure valait 0 avant pénalisation, c'est λI qui l'a portée à 1 (p02-02). Le bol est 71 fois plus raide en travers qu'en long.

ηmax = 2/71 = 0,0282. Au-delà, la coordonnée raide est multipliée par un facteur de module > 1 à chaque pas.

Trois pas à la main, η = 0,02

Un pas, c'est β ← β − η(Aβ − b). Rien d'autre. Sur l'écart e = β − β, chaque coordonnée propre suit ei ← (1 − ηλi)ei, indépendamment de l'autre.

1 − 0,02 × 71 = −0,42  (raide)  ·  1 − 0,02 × 1 = 0,98  (plate)

« L'écart de départ se décompose sur les deux axes propres, donc chaque composante est multipliée par son propre facteur, donc la raide est ramenée à 42 % à chaque pas quand la plate n'en perd que 2 %, donc c'est la plate qui décide du temps que ça prend. »

Au tableau — marche 4, chiffré

Écart de départ e0 = (1 ; 0) − β = (57/71 ; −28/71), de norme 0,8944. Sa décomposition est le fait central de ce déroulé :

sur la vallée (−2 ; 1)/√5 : −2/√5 = −0,8944  ·  sur le mur (1 ; 2)/√5 : 1/(71√5) = 0,0063

Le rapport vaut exactement 142 : presque tout l'écart est dans la direction que la descente traite le plus mal.

β1 = (1 ; 0) − 0,02·(1 ; 0) = (0,98 ; 0).

∇L(β1) = (15·0,98 − 14 ; 28·0,98 − 28) = (14,7 − 14 ; 27,44 − 28) = (0,7 ; −0,56), donc β2 = (0,98 ; 0) − 0,02·(0,7 ; −0,56) = (0,966 ; 0,0112).

∇L(β2) = (14,49 + 0,3136 − 14 ; 27,048 + 0,6384 − 28) = (0,8036 ; −0,3136), donc β3 = (0,9499 ; 0,0175).

kβkécart à βdont vallée
0(1 ; 0)0,89440,8944
1(0,9800 ; 0)0,87650,8765
2(0,9660 ; 0,0112)0,85900,8590
3(0,9499 ; 0,0175)0,84180,8418

0,8944 × 0,98 = 0,8765, puis × 0,98 = 0,8590 : le facteur plat se lit directement dans la colonne des écarts. Trois pas ont grignoté 6 %. La composante raide, elle, est déjà tombée de 0,0063 à 0,00047 — réglée, et invisible.

Combien de pas, et pourquoi la forme fermée gagne tronc

La composante raide est réglée en une dizaine de pas : elle ne compte pas. Tout le temps part dans la vallée, qui ne se contracte que de 0,98 par pas.

Pour la diviser par dix : ln 0,1 / ln 0,98 = 113,97, soit 114 pas. Par cent : 228. Et le système ∇L = 0 est linéaire — une résolution 2×2 donne la réponse exacte, sans η à régler.

« La direction plate ne perd que 2 % par pas, donc il en faut 114 pour un facteur dix, donc le nombre d'itérations est fixé par le conditionnement et non par l'optimiseur ; et comme le gradient est linéaire en β, annuler ∇L est un système 2×2, donc ici on le résout au lieu de l'itérer. »

Au tableau — marche 5

La forme fermée. Annuler le gradient, c'est résoudre [[15, 28], [28, 57]]β = (14 ; 28), système 2×2 de déterminant 71 :

β1 = (57·14 − 28·28)/71 = 14/71 = 0,197  ·  β2 = (15·28 − 28·14)/71 = 28/71 = 0,394

C'est (0,2 ; 0,4) × 70/71 : le point de norme minimale de la droite OLS, rétréci d'un facteur 70/(70 + λ).

Le prix de l'itération, à η = 0,02 depuis (1 ; 0) :

k0,98kécart restantchemin parcouru
100,8170,730818 %
300,5450,487945 %
600,2980,266170 %
1140,1000,089490 %

Après 60 itérations il reste encore 30 % du chemin. La résolution 2×2, elle, tient en une ligne et donne 0,197 et 0,394 exactement.

Figure 1 — le bol vu de dessus, et ce que le pas y fait

Lignes de niveau de L : des ellipses huit fois et demie plus longues que larges (√71), d'axe long la vallée. Le point bleu creux est la forme fermée (0,197 ; 0,394), le trait ambre la droite des solutions OLS de D4, le point violet le départ (1 ; 0) et la ligne rouge les 60 itérations : elle rampe le long de la vallée et n'arrive pas — après 60 pas il reste 30 % du chemin. Clique départ (0 ; 0) pour voir le mirage : la trajectoire s'y réduit à un segment sur l'axe raide, converge en six pas, et le bol allongé ne se voit plus. Monte η : à 0,0282 = 2/71 le facteur raide passe sous −1 et la trajectoire finit par quitter le cadre.

Un pas par direction : préconditionner

Le pas unique est un compromis entre deux courbures. Dans la base propre, les deux coordonnées sont indépendantes : rien n'oblige à leur donner le même η. Avec ηi = 1/λi, le facteur 1 − ηiλi vaut zéro : la coordonnée est réglée en une itération.

β1 = β0 − A−1∇L(β0) = A−1b = β

« Dans la base propre les deux coordonnées sont indépendantes, donc un pas de 1/λi annule chacune d'un coup, donc multiplier le gradient par A−1 fait les deux à la fois et retombe sur la forme fermée en une itération. »

Au tableau — marche 6
ηfacteur raidefacteur platlecture
1/71 = 0,014100,9859le mur réglé, la vallée figée
1/1 = 1−700la vallée réglée, le mur explose
les deux à la fois : A−1 à la place de ηun seul pas
A−1 = (1/71)·[[57, −28], [−28, 15]]  ⇒  A−1b = (1/71)·(798 − 784 ; −392 + 420) = (14/71 ; 28/71)

C'est Newton sur une quadratique : A est la hessienne, et un pas de Newton depuis n'importe quel point tombe sur β. Le prix est A entière — O(p³) et p² coefficients.

Adam fait la même chose au rabais : un pas par coordonnée, dans la base canonique et non dans la base propre, estimé par la taille récente des gradients. Aucune matrice n'est formée. Standardiser les features poursuit le même but encore plus en amont, en rapprochant les valeurs propres de A.

Où ça casse casse

Deux valeurs propres, deux façons de se faire piéger : par le haut, la divergence ; par le bas, l'attente. Et une troisième, plus sournoise, quand le point de départ cache les deux.

« Une seule direction suffit à faire diverger, donc le pas est borné par la plus raide ; la plus plate n'est alors contractée au mieux que de 70/72, donc le nombre d'itérations suit le conditionnement, donc un seul essai de learning rate depuis un seul point de départ ne prouve rien. »

Trois limites
  • η au-delà de 2/λmax diverge. À η = 0,03, le facteur raide vaut 1 − 0,03·71 = −1,13. Depuis (1 ; 0) l'écart raide ne pèse que 0,0063 au départ : la divergence met une soixantaine de pas à se voir, puis β60 = (4,64 ; 8,95) est onze fois plus loin de β que le point de départ — pendant que la coordonnée plate, elle, converge sagement. Une direction sur deux suffit à faire exploser la loss, et c'est toujours la plus raide qui fixe le plafond, même quand elle porte un millième de l'erreur.
  • κ = 71 rend la vallée interminable. Même avec le meilleur pas fixe, η = 2/(1 + 71) = 0,0278, la contraction plate ne descend pas sous (κ − 1)/(κ + 1) = 70/72 = 0,9722 : il faut encore 82 pas pour diviser l'écart par dix. Le nombre d'itérations est proportionnel à κ, et κ vient des données, pas de l'optimiseur.
  • Un départ chanceux masque tout. Depuis (0 ; 0), b étant colinéaire à (1 ; 2), la composante sur la vallée est exactement nulle : la descente reste sur l'axe raide et converge en six pas. On mesurerait κ = 1 sans le savoir. C'est pour cela que ce déroulé part de (1 ; 0) et non de l'origine — et pour cela qu'un seul essai de η depuis un seul point de départ ne mesure pas le conditionnement. Le bouton « départ (0 ; 0) » de la figure montre le mirage.

Résumé

À retenir
  1. Le bol. A = X⊤X + I = [[15, 28], [28, 57]], b = (14 ; 28), ∇L = Aβ − b. Trace 72, déterminant 71.
  2. Les deux courbures. λ = 71 sur (1 ; 2) — le mur — et λ = 1 sur (−2 ; 1) — la vallée, la colinéarité relevée de 0 par λI. κ = 71, ηmax = 2/71 = 0,0282.
  3. Trois pas à η = 0,02 depuis (1 ; 0) : (0,98 ; 0), (0,966 ; 0,0112), (0,9499 ; 0,0175). L'écart 0,8944 est porté à 142 contre 1 par la vallée, et s'y contracte de 0,98 par pas.
  4. La forme fermée. Une résolution 2×2 : β = (14/71 ; 28/71) = (0,197 ; 0,394), soit (0,2 ; 0,4) × 70/71.
  5. Le coût de l'itération. Facteur plat 0,98 ⇒ 114 pas pour diviser l'écart par dix ; 82 pas même au meilleur pas fixe 2/72. Après 60 pas il reste encore 30 % du chemin.
  6. Préconditionner. ηi = 1/λi règle chaque coordonnée en un pas ; les deux à la fois, c'est A−1∇L, c'est-à-dire Newton, et Adam l'approche par coordonnée.
« Sur le ridge colinéaire, A a pour valeurs propres 1 et 71 : le pas est plafonné à 2/71 par la direction raide, et la direction plate ne se contracte alors que de 0,98 par itération — 114 pas pour un facteur dix. Le système ∇L = 0 étant linéaire, je le résous en une fois et j'obtiens (0,197 ; 0,394). Quand je ne peux pas résoudre, je donne un pas par direction : c'est le conditionnement que Newton annule et qu'Adam approche. »

Chaîne verbalisée — le déroulé à voix haute

5 maillons · clique pour révéler après avoir dit
  1. Écris la loss ridge du jeu colinéaire de D4 et son gradient.
    L(β) = ½βᵀAβ − bᵀβ avec A = XᵀX + I = [[15, 28], [28, 57]] et b = Xᵀy = (14, 28). ∇L = Aβ − b : en (0, 0) il vaut −b = (−14, −28), et au départ retenu (1 ; 0) il vaut (1 ; 0).
  2. Quelles sont les courbures de ce bol, et quel pas maximal en découle ?
    Trace 72, déterminant 71 ⇒ λ = 1 et 71. Le mur (1, 2) à 71, la vallée (−2, 1) à 1 — celle que λI a relevée de 0. κ = 71, η_max = 2/71 = 0,0282.
  3. Fais le premier pas à η = 0,02, et dis ce que devient l'écart.
    β₁ = (1 ; 0) − 0,02·(1 ; 0) = (0,98 ; 0). L'écart 0,8944 est à 142 contre 1 sur la vallée, de facteur 1 − 0,02×1 = 0,98 : il passe à 0,8765. β₂ = (0,966 ; 0,0112), β₃ = (0,9499 ; 0,0175).
  4. Combien d'itérations, et pourquoi préfère-t-on résoudre ?
    Facteur plat 0,98 ⇒ ln0,1/ln0,98 = 114 pas par facteur dix. La forme fermée est un système 2×2 de déterminant 71 : β̂ = (14/71 ; 28/71) = (0,197 ; 0,394), soit (0,2 ; 0,4) × 70/71.
  5. Que ferait un pas par direction propre ?
    η = 1/λᵢ annule le facteur 1 − ηλᵢ : une itération par coordonnée. Les deux ensemble, c'est β − A⁻¹∇L = A⁻¹b = β̂ — Newton. Adam en fait une version diagonale dans la base canonique.