- Le pas et sa condition. −∇L est la direction de plus forte descente ; sur une courbure a, l'écart au minimum est multiplié par (1 − η a) à chaque pas (p03-02 pas 2 et pas 3).
- La pente est le signal. Un critère n'informe l'apprentissage que par sa pente ; là où elle est nulle, rien ne bouge (p03-01).
- D'où vient ∂L/∂W. La loss est scalaire, donc on transporte un vecteur de la sortie vers l'entrée : c'est le VJP, et backprop n'est que cela (p08-01 pas 5–6).
- Boosting et k-means ne sont pas redérivés ici : ce pont les range sous le même pas. Leurs chaînes propres sont p07-03 et p07-04.
Le même pas, quatre habits
Le pas, écrit une fois tronc
Trois objets suffisent : un critère L, un objet θ qui bouge, un pas η.
Le signe : on avance à l'opposé du gradient, qui pointe vers la montée. La condition : sur une courbure a, l'écart au minimum est multiplié par (1 − ηa) à chaque pas, donc il faut η < 2/a.
« Le gradient donne la direction de plus forte montée, donc on prend son opposé, donc l'écart au minimum est multiplié par 1 − ηa à chaque pas, donc η reste sous 2 sur la courbure. »
L(θ) = (θ − 1)², courbure a = 2, départ θ0 = 3,5. Seuil : 2/a = 1.
| η | facteur 1 − ηa | trois premiers itérés | régime |
|---|---|---|---|
| 0,25 | +0,50 | 2,25 · 1,625 · 1,3125 | monotone |
| 0,9 | −0,80 | −1 · 2,6 · −0,28 | oscille, converge |
| 1,1 | −1,20 | −2 · 4,6 · −3,32 | diverge |
À η = 1,1 l'écart initial 2,5 est multiplié par 1,2 à chaque pas : 2,5 → 15,5 après 10 pas. Rien dans ce tableau ne dépend du domaine — c'est le point du pont.
Les quatre boutons changent le nom de l'axe et la légende — pas la courbe, pas la trajectoire, pas les chiffres. Fais glisser η : sous 0,5 la descente est monotone, entre 0,5 et 1 elle oscille en convergeant, au-dessus de 1 = 2/a elle diverge et sort du cadre. Le pas dessiné va toujours vers le bas, quel que soit l'onglet : c'est le signe −η∇.
Ce qui change : θ, et où l'on prend le gradient
Lire un algorithme de descente, c'est répondre à deux questions seulement : qu'est-ce qui bouge, et par rapport à quoi dérive-t-on L. Le reste du pas est déjà écrit au pas 1.
Trois lectures utiles : le boosting descend dans l'espace des fonctions, et son taux d'apprentissage s'appelle ν ; Lloyd descend par blocs, chaque bloc se résolvant en forme fermée (b06) ; backprop est le calcul du gradient, pas la descente.
« Le pas est écrit une fois pour toutes, donc il ne reste qu'à nommer l'objet qui bouge et le point où l'on dérive, donc chaque nouvel algorithme de descente se lit en deux lignes. »
| domaine | θ | gradient | le pas |
|---|---|---|---|
| Régression, logistique | le vecteur β | ∂L/∂β = Σ(p − y)x | β ← β − η∇ |
| Gradient boosting | la fonction F(x) | −∂L/∂F(xi) en chaque point | F ← F + ν·h, h = un arbre ajusté sur ce gradient |
| k-means (Lloyd) | centroïdes μj et affectations | deux gradients exacts en alternance | descente alternée, chaque demi-pas à son optimum |
| Réseau (backprop) | tous les poids W | ∂L/∂W par VJP depuis la sortie | W ← W − η∇, sur un minibatch |
| Bol allongé, 2 paramètres | β ∈ R² | Aβ − b | même pas, mais κ = 71 |
Où c'est écrit, ligne à ligne : p03-02 pas 2–3 et p05-02 · p07-03 · p07-04 · p08-01 pas 5–6 et p03-02 pas 7 · w03-01.
Habit 1 — θ est un vecteur
Régression logistique : θ = β ∈ Rp, zi = β⊤xi, pi = σ(zi).
Chaque observation tire β dans la direction de son propre xi, avec une force égale à son erreur. Annuler ce gradient ne donne pas de système linéaire : on itère (p03-02 pas 5).
« Le gradient de la log-loss est la somme des erreurs p − y pondérées par les x, donc chaque observation tire le vecteur dans la direction de son propre x, donc β ← β − η∇ est toute la mise à jour. »
x1 = (1 ; 2), y1 = 1 ; x2 = (1 ; −1), y2 = 0 ; départ β = (0 ; 0,5).
| z | p = σ(z) | p − y | (p − y)x | |
|---|---|---|---|---|
| obs. 1 | 1 | 0,731 | −0,269 | (−0,269 ; −0,538) |
| obs. 2 | −0,5 | 0,378 | +0,378 | (+0,378 ; −0,378) |
| somme | ∇L = (0,109 ; −0,915) |
β ← (0 ; 0,5) − 0,5·(0,109 ; −0,915) = (−0,054 ; 0,958). Loss totale : 0,787 → 0,455. Le deuxième coefficient monte parce que les deux observations poussent dans le même sens sur cette coordonnée.
Habit 2 — θ est une fonction tronc
Boosting : l'objet qui bouge n'est pas un vecteur de paramètres, c'est F. On dérive L par rapport à la valeur de F en chaque point d'entraînement, ce qui donne un nombre par observation :
Un arbre h ajuste ces ri : il rend le gradient négatif utilisable ailleurs qu'aux points d'entraînement. ν joue exactement le rôle de η. Le point qui se perd : le gradient est pris au modèle cumulé, jamais aux résidus laissés par le dernier arbre seul.
« L'objet qui bouge est la fonction F, donc on dérive L par rapport à sa valeur en chaque point d'entraînement, donc la cible de l'arbre suivant est le gradient négatif pris au modèle cumulé, donc ce n'est pas le résidu du dernier arbre. »
y = (1 ; 3 ; 4 ; 8) sur x = 1, 2, 3, 4. L = ½Σ(y − F)², donc ri = yi − Fi exactement.
Convention : ici le ½ est gardé pour que le pseudo-résidu soit le résidu ; le facteur est absorbé par ν sinon.
| x=1 | x=2 | x=3 | x=4 | |
|---|---|---|---|---|
| F0 = moyenne | 4 | 4 | 4 | 4 |
| cible y − F0 | −3 | −1 | 0 | +4 |
| souche h1 (coupe 2|3) | −2 | −2 | +2 | +2 |
| F1 = F0 + 0,5·h1 | 3 | 3 | 5 | 5 |
| cible de l'arbre 2 : y − F1 | −2 | 0 | −1 | +3 |
| le piège : r0 − h1 | −1 | +1 | −2 | +2 |
L : 13 → 7. Les deux dernières lignes diffèrent point par point, et diffèrent parce que ν = 0,5 : l'arbre 1 n'a été appliqué qu'à moitié, donc il reste du gradient là où le piège n'en voit plus. À ν = 1 elles coïncideraient — c'est ce qui rend la confusion durable.
Habit 3 — θ, ce sont des centroïdes
k-means : J = Σi ‖xi − μa(i)‖². Deux blocs d'inconnues : les affectations a et les centroïdes μ. Lloyd alterne, et chaque demi-pas minimise J exactement dans son bloc.
Le recentrage n'est donc pas autre chose qu'un pas de gradient : c'est le même pas, avec le η qui tombe pile sur le minimum. Avec un η plus petit on avance dans la même direction, moins loin.
« Le gradient de l'inertie en μj vaut −2nj fois l'écart à la moyenne du cluster, donc un pas de gradient avec η = 1/(2nj) pose le centroïde exactement sur la moyenne, donc le recentrage de Lloyd est ce pas-là pris à son η optimal. »
Points 1, 2, 3, 8, 9, 10 ; départ μ = (1 ; 6).
| demi-pas | résultat | J |
|---|---|---|
| affecter au plus proche | {1, 2, 3} → μ1 ; {8, 9, 10} → μ2 | 5 + 29 = 34 |
| recentrer | μ = (2 ; 9) | 2 + 2 = 4 |
Le recentrage lu comme un pas : n1 = 3, moyenne 2, ∂J/∂μ1 = −2·3·(2 − 1) = −6 ; avec η = 1/6 : 1 − (1/6)(−6) = 2, la moyenne. Avec η = 0,05 : 1,3 — même direction, pas jusqu'au bout. Idem à droite : ∂J/∂μ2 = −18, et 6 + 18/6 = 9.
L'itération suivante ne change aucune affectation : Lloyd s'arrête. J décroît à chaque demi-pas, donc l'algorithme termine — mais sur un minimum local, voir le pas 8.
Habit 4 — θ, ce sont des poids
Réseau : θ = tous les W, des millions. Rien de neuf sur le pas ; ce qui est neuf est comment on obtient ∇. La loss étant scalaire, la dernière jacobienne est une ligne : on transporte un vecteur de la sortie vers l'entrée (VJP) au lieu de fabriquer des matrices.
Backprop calcule le gradient ; la mise à jour qui suit est celle du pas 1, à la lettre. Le minibatch change seulement la qualité de l'estimation de ∇, pas le geste.
« Backprop rend ∂L/∂W, donc le pas qui suit est exactement W ← W − η∇, donc ce que la Phase 2 ajoutera — SGD, momentum, Adam — porte sur η et sur la direction, pas sur le geste. »
x = 2, w = 0,5, b = 0, y = 1. Aller : z = 1, p = 0,731, L = 0,313.
Retour : ∂L/∂p = −1/p = −1,368 ; ∂p/∂z = p(1 − p) = 0,197 ; produit = p − y = −0,269. Puis ∂L/∂w = (p − y)·x = −0,538 et ∂L/∂b = −0,269.
Le pas : w ← 0,5 + 0,5·0,538 = 0,769, b ← 0,134. Nouvelle loss : 0,313 → 0,172. C'est littéralement l'habit 1 avec une seule observation — la différence n'apparaît qu'avec les couches.
Le coût du retour. Trois couches de largeur 1 000 : depuis la sortie, 2·106 multiplications ; depuis l'entrée, 109. Facteur 500. C'est pour cela qu'on part de la sortie (p08-01 pas 5).
Ce qui ne change pas d'un habit à l'autre
Trois choses traversent les quatre lignes : le signe (−η∇, jamais +), la condition η < 2/courbure, et la lenteur quand les courbures sont hétérogènes (κ = λmax/λmin).
Le nom du pas change — η, ν, « learning rate », rien en k-means où il est implicite —, sa fonction non.
« La condition de convergence ne regarde que la courbure du critère, donc elle vaut pour β comme pour W, donc un bol allongé coûte cher dans tous les habits et se soigne au même endroit : l'échelle des variables. »
| critère | courbure | pas maximal | ce que ça coûte |
|---|---|---|---|
| (θ − 1)², 1D | a = 2 | η < 1 | facteur 0,5 par pas à η = 0,25 |
| ridge 2D de w03-01 | λ = 1 et 71, κ = 71 | η < 2/71 = 0,028 | 114 pas à η = 0,02 pour diviser l'écart par 10 |
| k-means, bloc μj | 2nj | η < 1/nj | rien : Lloyd prend η = 1/(2nj), l'optimum |
En boosting le seuil ne s'écrit pas ainsi (l'espace est celui des fonctions) mais il se voit : ν trop grand fait coller le modèle en quelques arbres. Même maladie, autre nom.
Où ça casse — de la même façon partout casse
Les trois pannes sont celles du pas, pas celles du domaine. Les reconnaître dans un habit suffit à les reconnaître dans les trois autres.
« Les pannes viennent du pas et de la forme du critère, donc elles ne changent pas d'un domaine à l'autre, donc on les cherche toujours aux trois mêmes endroits : la taille du pas, la convexité, la pente. »
- Pas trop grand ⇒ divergence. η > 2/courbure : le facteur (1 − ηa) sort de [−1 ; 1] et l'écart grossit — 2,5 → 15,5 en 10 pas à η = 1,1. En boosting, ν trop grand ne fait pas diverger la loss d'entraînement, il fait surapprendre vite : c'est la même absence de retenue.
- Non-convexité ⇒ optimum local. Un réseau n'a aucune garantie ; k-means non plus — J décroît à chaque demi-pas, donc Lloyd s'arrête, mais là où l'initialisation l'a mené (d'où k-means++). Le boosting sur arbres échappe à ce piège-là, chaque pas étant un ajustement local dans l'espace des fonctions ; il n'échappe pas au surapprentissage si l'on ne s'arrête pas.
- Gradient nul ⇒ rien n'apprend. C'est p03-01 vu du côté du pas. ∂L/∂w = (p − y)·x : une entrée nulle ne met à jour aucun poids. En k-means, un cluster vide n'a pas de moyenne : nj = 0, le gradient est nul, le centroïde reste où il est pour toujours.
Résumé
- Un seul pas : θ ← θ − η∇L. Ce qui change d'un domaine à l'autre est θ : vecteur, fonction, centroïdes, poids.
- Boosting = descente sur une fonction, gradient pris au modèle cumulé, ν = le pas ; Lloyd = descente alternée à demi-pas exacts (η = 1/(2nj)) ; backprop = le calcul du gradient, pas la descente.
- Même casse partout : pas trop grand, non-convexité, gradient nul.
Chaîne verbalisée — une prise, à voix haute
- Même argument, autre habit : dans le boosting, qu'est-ce qui bouge et qu'est-ce que le gradient ?La fonction F ; le gradient est −∂L/∂F(xi) en chaque point, pris au modèle cumulé — le résidu si la loss est quadratique.
- Et dans Lloyd ?Les centroïdes et les affectations, en alternance ; chaque demi-pas est exact — le recentrage est le pas de gradient à η = 1/(2nj).
- Et dans un réseau ?Les poids ; le gradient vient par VJP depuis la sortie (p08-01) ; la descente qui l'utilise est celle de p03-02, inchangée.
- Qu'ont-ils tous en commun quand ça casse ?Pas trop grand ⇒ divergence (ou surapprentissage éclair si c'est ν) ; non convexe ⇒ optimum local ; pente nulle ⇒ rien ne bouge.
Ponts et cartes
ml::optimisation (le pas, le seuil 2/courbure, κ) · ml::boosting (cible = gradient au modèle cumulé, ν) · ml::kmeans (Lloyd, demi-pas exacts, cluster vide) · dl::backprop (VJP, gradient puis pas).
Une carte qui résiste après ce pont est une carte à refondre, pas une section à relire.