- Un minimum intérieur annule le gradient, et la descente suit −∇L (p03-02 pas 2). Ce pont ne redérive ni l'un ni l'autre : il les met face à face.
- Convexité : tout minimum local est global ; stricte, il est unique (p03-02 pas 4). Le fait est acquis ; ce pont en fait une colonne de table.
- +λI translate le spectre de λ sans rien annuler (p04-02 pas 7, p02-02 pas 5). C'est le seul fait d'algèbre dont ce pont se sert.
- Conditionnement κ = μmax/μmin, et ne pas former X⊤X (p04-03 pas 6–7). Repris tel quel.
- Les domaines ne sont pas redéfinis : OLS (p05-01), logistique (p05-02), k-means (p07-04), ridge et Lasso (p02-02), réseaux (p08-01).
Un geste, deux questions, six habits
Le geste, et les deux questions qu'il ouvre tronc
Minimiser L, c'est chercher un θ où le gradient s'annule : p équations, p inconnues. Tout se joue sur la nature de ce système, jamais sur l'allure de L.
non linéaire ⇒ on itère
Une seconde question, indépendante : le point trouvé est-il le minimum ? C'est la convexité qui répond, et elle répond séparément — un problème peut être convexe sans forme fermée (logistique), ou avoir une forme fermée sans être convexe globalement (le demi-pas de k-means).
« Un minimum intérieur annule le gradient, donc minimiser revient à résoudre ∇L(θ) = 0, donc si ce système est linéaire en θ la solution s'écrit d'un coup, donc c'est la linéarité du gradient — pas l'allure de L — qui décide entre résoudre et itérer. »
| problème | ∇L = 0 | linéaire ? | convexe ? |
|---|---|---|---|
| Moyenne | Σ(xi − m) = 0 | oui | stricte |
| OLS | X⊤Xβ = X⊤y | oui | stricte ssi X⊤X inversible |
| Ridge | (X⊤X + λI)β = X⊤y | oui | stricte dès λ > 0 |
| Centroïde (Lloyd) | Σ(xi − μ) = 0 sur le cluster | oui | oui à affectation figée, non globalement |
| Logistique | Σ(σ(xi⊤β) − yi)xi = 0 | non (σ) | oui, sans forme fermée |
| Lasso | sous-gradient, coude en 0 | non (signe) | oui, non lisse |
| Réseau | ∇ par backprop | non | non : local |
Où chaque ligne est écrite : moyenne l08 notion 2 · OLS p05-01 et p04-03 pas 7 · ridge p02-02 pas 5 et p04-02 pas 7 · centroïde p07-04 · logistique p05-02 et p03-02 pas 4–5 · Lasso p02-02 pas 7 et p03-01 pas 8 · réseau p08-01 et p03-02 casse.
Le mot juste : c'est la solution qui est en forme fermée, jamais le système. Le système, lui, est linéaire. Dire « système en forme fermée » mélange les deux étages et fait perdre la seule question qui compte : linéaire en θ, oui ou non.
Les quatre paysages de la table, en un seul paramètre. Clique sur les quatre boutons, et sur le dernier déplace le curseur. Bol quadratique : L(β) = 5β² − 8β + 5, l'objectif du fil rouge une fois centré ; sa dérivée 10β − 8 est affine, donc le minimum s'écrit : β = Sxy/Sxx = 4/5 = 0,8. Bol non quadratique : la même donnée en logistique, intercept figé à sa valeur optimale ; convexe, un seul creux, mais la dérivée contient σ — aucune formule ne donne 0,908, il faut l'atteindre. Coude : le même bol plus 10|β|, convexe et non lisse ; le minimum est exactement en 0 et la dérivée n'y existe pas. Deux creux : non convexe ; les deux trajectoires partent de θ0 et de θ0 + 0,2, même pas, même règle — et à partir de θ0 = 0 elles finissent dans deux creux différents, à L = 3,56 contre 8,35. C'est la figure de k-means, en une dimension.
Habit 1 — le système est linéaire : moyenne, OLS, ridge
Une loss quadratique a un gradient affine : chaque dérivée partielle est une combinaison linéaire des θ. L'annuler donne donc p équations linéaires — les équations normales.
La moyenne en est le cas p = 1 avec X = 1 : 1⊤1·m = 1⊤x, soit n·m = Σxi. La ridge ajoute λI à gauche et rien à droite.
« Une loss quadratique a un gradient affine, donc l'annuler donne un système linéaire, donc la solution s'écrit en une ligne — moyenne, OLS, ridge — et la seule chose qui reste à décider est la façon de résoudre : QR ou SVD, jamais l'inverse explicite. »
Moyenne : n·m = 14, donc m = 3,5. Contrôle : Σ(yi − 3,5) = 0 exactement.
OLS avec constante, X = [1 | x] :
Une seule ligne d'algèbre, aucune itération. RSS = 1,80. Sur données centrées, Sxx = 5, Sxy = 4, pente = 4/5 = 0,8.
Ridge : (Sxx + λ)β = Sxy, soit β = 4/(5 + λ) — forme fermée elle aussi.
| λ | 0 | 1 | 5 | 10 |
|---|---|---|---|---|
| β ridge | 0,800 | 0,667 | 0,400 | 0,267 |
Résoudre, oui ; inverser, non. Écrire β = (X⊤X)−1X⊤y est correct sur le papier et fautif au clavier : former X⊤X carre le conditionnement (p04-03 pas 7). On passe par QR ou SVD sur X, qui donnent le même β = (1,5 ; 0,8) sans jamais construire la matrice carrée.
Habit 2 — le même argument déguisé : le demi-pas de Lloyd
À affectation figée, la SSE de k-means est une somme de Σ(xi − μk)² indépendantes. Chaque gradient est linéaire en μk : c'est la moyenne du pas 2, une fois par cluster.
Mais l'affectation dépend des centroïdes. Le critère complet est un minimum de morceaux quadratiques, un par découpage : convexe sur chaque morceau, non convexe sur l'ensemble. Lloyd descend, il n'arrive pas forcément.
« À affectation figée le critère est une somme de carrés en μ, donc son gradient est linéaire et le centroïde est la moyenne du cluster, donc chaque demi-pas de Lloyd est une forme fermée, donc l'algorithme ne fait jamais d'erreur locale — et se trompe pourtant de creux, l'affectation rendant le critère global non convexe. »
Points : 0, 1, 10, 11, 20, 21. Deux initialisations, le même algorithme, deux points fixes.
| init des centroïdes | clusters obtenus | centroïdes finaux | SSE |
|---|---|---|---|
| 0 · 10 · 20 | {0,1} {10,11} {20,21} | 0,5 · 10,5 · 20,5 | 1,5 |
| 5,5 · 20 · 21 | {0,1,10,11} {20} {21} | 5,5 · 20 · 21 | 101 |
Le second est un vrai point fixe : réaffecter ne bouge personne (0, 1, 10 et 11 sont tous plus près de 5,5 que de 20), recalculer les moyennes non plus. Chaque demi-pas est exact, chaque itération fait décroître la SSE — et le résultat est 67 fois pire.
Aucune quantité observable ne signale l'échec : Lloyd s'arrête avec la même sérénité dans les deux cas. D'où k-means++ et les restarts multiples — on relance, on garde la plus basse SSE. C'est le seul recours quand la convexité manque, et c'est un recours statistique, pas une garantie.
Habit 3 — quand ∇L = 0 cesse d'être linéaire : logistique, Lasso
La logistique donne exactement la même forme que les équations normales — X⊤p = X⊤y — mais p = σ(Xβ) dépend de β à travers une sigmoïde. Non linéaire : rien à isoler.
Le Lasso échoue pour une autre raison : le gradient n'existe pas en 0. On passe au sous-gradient, et le seuil doux remplace la division (p02-02 pas 7). Les deux restent convexes : l'itération arrive au bon endroit, elle met seulement du temps.
« La condition d'optimalité de la logistique a la forme d'une équation normale, donc on cherche à isoler β, donc on bute sur σ qui enferme β dans une non-linéarité, donc il n'y a pas de forme fermée — et comme la loss reste convexe, itérer suffit à atteindre le minimum global. »
Optimum : β = (−2,2705 ; 0,9082), L = 2,34749. Aucune formule ne le produit ; deux chemins l'atteignent.
| méthode | pas | β1 | L | ‖∇L‖ |
|---|---|---|---|---|
| Newton | 1 | 0,8000 | 2,35260 | 9,6·10−2 |
| Newton | 3 | 0,90818 | 2,34749 | 5,8·10−6 |
| gradient, η = 0,120 | 100 | 0,7206 | 2,36526 | 6,4·10−2 |
| gradient, η = 0,120 | 1 000 | 0,90818 | 2,34749 | 7,1·10−7 |
Le contrôle qui rassure : à l'optimum, Σpi = 2 = Σyi et Σpixi = 6 = Σyixi — deux égalités exactes, la même structure que X⊤Xβ = X⊤y. La condition est identique ; c'est sa résolubilité qui diffère.
L'écart 3 contre 1 000 n'est pas un détail d'implémentation : Newton utilise la courbure locale et devient quadratique près de l'optimum, le gradient ne voit que la pente et paie le conditionnement de la hessienne (κ ≈ 63 ici). Avec p grand, la hessienne coûte p³ à inverser et l'arbitrage se renverse.
Lasso sur le fil rouge : L(β) + λ|β|, avec L′(0) = −2Sxy = −8. Le zéro exact arrive à λ = |L′(0)| = 8 et tient au-delà — c'est le coude de la figure 1, et le mur de p03-01 pas 8.
Ce que garantit la convexité, et ce que +λI y ajoute tronc
Convexe : tout minimum local est global — la question « suis-je au bon endroit » cesse de se poser. Strictement convexe : ce minimum est en plus unique, donc la solution est un objet, pas un ensemble.
Pour une quadratique tout se lit dans le spectre de X⊤X : μi ≥ 0 toujours (convexe), μi > 0 pour toutes (stricte). Ajouter λI translate le spectre :
C'est le nom général de « la pénalité rend le minimum existant, ou unique » : elle rend le problème strictement convexe. Rien à redémontrer, rien à retenir en plus.
« La convexité rend tout minimum local global, donc la stricte convexité le rend unique, donc pour une quadratique elle équivaut à des valeurs propres toutes strictement positives, donc +λI, qui translate le spectre de λ, rend n'importe quelle ridge strictement convexe et son système inversible. »
Gram normalisée X⊤X/n = [[1, r], [r, 1]]. Spectre exact : μ = 1 + r et 1 − r. Convexe (les deux ≥ 0), et strictement — de justesse.
| λ | μmin | μmax | κ |
|---|---|---|---|
| 0 | 0,0001 | 1,9999 | 19 999 |
| 0,01 | 0,0101 | 2,0099 | 199 |
| 0,1 | 0,1001 | 2,0999 | 21,0 |
| 1 | 1,0001 | 2,9999 | 3,0 |
Ce que +λI achète, en une ligne : la stricte convexité (unicité), l'inversibilité (la forme fermée existe), et un κ divisé par 100 pour λ = 0,01. Un seul geste, trois effets — et le troisième est ce qui rend la forme fermée calculable et pas seulement écrite.
Le prix est du biais : β = 4/(5 + λ) s'éloigne de 0,8 dès que λ > 0. La ridge échange de la variance contre du biais (b03) ; ici on lit le même λ du côté numérique.
Le bol du problème à deux colonnes corrélées, vu dans ses deux directions propres : la raide (μmax + λ) et la fragile (μmin + λ). L'échelle verticale est taillée pour la fragile ; la raide sort du cadre dès |t| > 1,1, et cet écart d'échelle est κ. Déplace λ. À λ = 0 la courbe fragile est couchée sur l'axe : le long de cette direction le critère ne varie quasiment pas, donc l'optimum n'y est pas déterminé — c'est κ = 19 999, et c'est ce qui fait qu'une forme fermée exacte en théorie sort fausse en flottant. À λ = 0,01 le chiffre a déjà tout dit (κ = 199) avant que l'œil ne voie quoi que ce soit ; vers λ = 0,1 la courbe décolle pour de bon. Le pas maximal d'une descente, 2/(μmax + λ), est fixé par la direction raide tandis que le nombre d'itérations est fixé par la fragile : c'est tout le conditionnement, en une image (p03-02 pas 6).
Où ça casse casse
La forme fermée existe plus souvent qu'on ne l'utilise, et la convexité promet moins qu'on ne croit. Les quatre ratés se rangent en deux paires : la formule est là mais inutilisable, ou la garantie est absente.
« Une solution en forme fermée est exacte au sens de l'algèbre, donc elle peut rester fausse en flottant ou trop chère à former, donc l'existence d'une formule ne dicte pas la méthode, donc le choix se fait sur le conditionnement et sur le coût — la convexité, elle, ne répond qu'à la question du bon endroit. »
- Forme fermée, mais mal conditionnée. Avec κ = 19 999 on perd déjà quatre chiffres significatifs ; former X⊤X le carre et en coûte huit. La solution est exacte sur le papier et fausse à l'écran. Recours : QR ou SVD sur X, ou λ > 0 (p04-03 pas 6–7).
- Forme fermée, mais trop chère. Résoudre un système p × p coûte de l'ordre de p³ : 106 opérations à p = 100, 1012 à p = 10 000. Passé quelques milliers de colonnes on itère l'OLS lui-même — gradient conjugué, ou descente stochastique. La formule existe et on ne s'en sert pas.
- Convexe mais non lisse. Le coude du Lasso n'a pas de gradient ; une descente ordinaire y zigzague sans jamais poser le poids exactement à zéro. Il faut des méthodes proximales — seuil doux, descente par coordonnées, ISTA — qui traitent le coude analytiquement au lieu de le dériver.
- Non convexe : la question reste sans réponse. « Le point trouvé est-il le minimum ? » — on ne sait pas, et aucune quantité calculable ne le dit. k-means en donne le cas propre (1,5 contre 101 sur six points), les réseaux le cas général. Les recours sont empiriques : initialisation soignée (k-means++), restarts, et pour les réseaux l'aveu que le minimum global n'est ni atteint ni souhaité.
Résumé
- Poser ∇L = 0, puis une seule question : le système est-il linéaire en θ ? Oui ⇒ la solution s'écrit (moyenne, OLS, ridge, centroïde) ; non ⇒ on itère (logistique, Lasso, réseaux).
- Deux questions indépendantes. La linéarité dit comment on trouve, la convexité dit si c'est le bon endroit. Convexe sans forme fermée : logistique. Forme fermée sans convexité globale : le demi-pas de Lloyd.
- Le mot juste : la solution est en forme fermée, le système est linéaire.
- +λI translate le spectre de λ : stricte convexité, unicité, inversibilité, et κ qui s'effondre — 19 999 → 199 pour λ = 0,01. C'est le nom général de « la pénalité rend le minimum unique ».
- Les chiffres qui ancrent : OLS (1,5 ; 0,8) en une ligne · logistique 3 pas de Newton contre 1 000 de gradient pour le même (−2,27 ; 0,908) · k-means 1,5 contre 101 · Lasso à zéro exact dès λ = |L′(0)| = 8.
- Une formule n'oblige à rien : κ trop grand (précision) ou p trop grand (p³) et l'on itère quand même. Et jamais (X⊤X)−1 explicitement — QR ou SVD.
- Sans convexité, « est-ce le minimum ? » n'a pas de réponse calculable : restarts et k-means++, pas une garantie.
Chaîne verbalisée — une prise, à voix haute
- Pourquoi l'OLS a-t-il une forme fermée et pas la logistique ? (la réponse complète, telle quelle, en entretien)Les deux annulent le gradient et arrivent à la même forme : X⊤Xβ = X⊤y d'un côté, X⊤σ(Xβ) = X⊤y de l'autre. La première est linéaire en β : on résout, une fois. La seconde enferme β dans une sigmoïde : rien à isoler. Sur quatre points, l'OLS sort (1,5 ; 0,8) en une ligne ; la logistique demande 3 pas de Newton, ou 1 000 pas de gradient, pour (−2,27 ; 0,908). Elle reste convexe, donc l'itération atteint le minimum global — c'est une question de résolubilité, pas de garantie. Et l'on résout par QR ou SVD, jamais en formant (X⊤X)−1.
- Même argument, autre habit : le demi-pas de Lloyd.À affectation figée, la SSE est une somme de Σ(xi − μ)² : gradient linéaire, centroïde = moyenne du cluster, forme fermée. Mais l'affectation dépend des centroïdes, donc le critère global est un minimum de morceaux quadratiques : non convexe. Six points — 0, 1, 10, 11, 20, 21 — en k = 3 : une initialisation donne SSE 1,5, une autre 101, et les deux sont des points fixes exacts. D'où k-means++ et les restarts.
- Que garantit la convexité, et que fait exactement +λI ?Convexe : tout minimum local est global. Strictement convexe : il est unique. Pour une quadratique, cela se lit dans le spectre de X⊤X — μi ≥ 0 donne la convexité, μi > 0 la stricte. +λI translate le spectre de λ, donc rend toutes les valeurs propres strictement positives : c'est le nom général de « la pénalité rend le minimum unique ». Bonus : κ passe de 19 999 à 199 pour λ = 0,01. Prix : du biais, β = 4/(5 + λ).
- La forme fermée existe — pourquoi itérer quand même ?Deux raisons, et elles n'ont rien à voir avec la convexité. Précision : à κ = 19 999 on perd quatre chiffres, et former X⊤X le carre ; la formule est exacte et le résultat faux. Coût : résoudre un système p × p vaut de l'ordre de p³ — 1012 opérations à p = 10 000. On itère alors l'OLS lui-même. Une formule dit qu'une solution s'écrit, jamais qu'il faut s'en servir.
Ponts et cartes
ml::optimisation (∇L = 0 linéaire ou non, convexe vs strictement convexe, Newton vs gradient) · ml::regression-lineaire (équations normales, QR/SVD plutôt qu'inverse) · ml::ridge (+λI, unicité, biais) · ml::kmeans (demi-pas en forme fermée, non convexité globale, restarts) · algebre::conditionnement (κ, spectre translaté, chiffres perdus).
Une carte qui résiste après ce pont est une carte à refondre, pas une section à relire.