Régression logistiqueLogistic Regression for Classification — Advanced Optimization · Cours 4 & 5 (9/17, 9/22)
Slides 3-logistic-regression (35 p.)
PRML §4.3 p.203–212
DL §5.4 p.156–163
PRML §4.2 (modèles génératifs)
Ce chapitre répond à une seule question : comment apprendre un classifieur à partir de données, alors que le critère qu'on veut vraiment rendre petit — le taux d'erreur — ne se laisse pas optimiser ? Chaque section répond au problème laissé ouvert par la précédente. Au début de chaque partie, un encadré Où on en est rappelle ce qui est acquis, ce qui manque encore, et ce que la section apporte.
Feuille de route
Les slides découpent le cours en trois blocs : le problème (§1), la classe de modèles et sa perte (§2–5), l'algorithme (§6–7), puis l'extension multiclasse (§8). La chaîne complète, cliquable :
① But · §1minimiser le taux d'erreur $P(h(\bx)\ne y)$obstacle : perte en escalier, gradient nul
→
② 1ᵉʳ essai · §2moindres carrés sur $y = \pm1$défaut : punit les points trop bien classés→
③ Outil · §3la sigmoïde $\sigma:\R\to(0,1)$transforme un score en probabilité→
④ Modèle · §4$P(y = 1\mid\bx) = \sigma(\bw\T\bx)$frontière : l'hyperplan $\bw\T\bx = 0$→
⑤ Perte · §5max. de vraisemblance ⇒ cross-entropy $L(\bw)$convexe, lisse, majore l'erreur 0-1→
⑥ Algorithme · §6–7pas de formule close ⇒ gradient, puis Newton$\nabla L$ et $\nabla^2L$→
⑦ Extension · §8$K$ classes : softmax$K = 2$ redonne la sigmoïde
Le raisonnement, maillon par maillon
- ①Le but est clair, mais inutilisable tel quel. On veut un $h$ qui se trompe rarement : minimiser $\E\,\mathbb 1(h(\bx)\ne y)$. Problème : en fonction des paramètres, cette perte est un escalier (elle vaut 0 ou 1 par exemple) ; son gradient est nul partout où il existe. La descente de gradient du chapitre 1 ne peut rien en faire. → Il faut une autre perte, lisse, qui « pousse dans le bon sens ».
- ②Réutiliser les moindres carrés ? Coder les classes $\pm1$ et faire une régression. En écrivant la perte en fonction de la marge $m = y\,f(\bx)$ (positive = bien classé), on voit que $(1-m)^2$ remonte pour $m>1$ : un point très bien classé est puni. → Il faut une perte qui décroît avec $m$. La bonne idée : ne plus prédire $\pm1$ mais une probabilité.
- ③De score à probabilité : la sigmoïde. $\sigma(t) = 1/(1+e^{-t})$ envoie $\R$ sur $(0,1)$. Ses propriétés ($\sigma(-t) = 1-\sigma(t)$, $\sigma' = \sigma(1-\sigma)$, inverse = logit) font tous les calculs des sections suivantes.
- ④Le modèle. On dit que le log-odds est linéaire : $\ln\frac{p}{1-p} = \bw\T\bx$, c.-à-d. $p = \sigma(\bw\T\bx)$. Seuiller $p$ à $\frac12$ = seuiller le score à 0 : la frontière reste un hyperplan, comme pour un classifieur linéaire. Reste à choisir $\bw$.
- ⑤La perte. Puisque le modèle donne une probabilité à chaque étiquette, on choisit le $\bw$ qui rend les étiquettes observées les plus probables (maximum de vraisemblance). Son $-\ln$ est la cross-entropy : convexe, lisse, décroissante en la marge, et elle majore l'erreur 0-1 (à un facteur $1/\ln2$ près). On a répondu à ① : minimiser la cross-entropy fait baisser un majorant du taux d'erreur.
- ⑥L'algorithme. $\nabla L(\bw) = 0$ n'a pas de solution explicite (contrairement aux moindres carrés). On itère : descente de gradient avec $\nabla L = \sum_n(\hat y_n - y_n)\bx_n$ (§6). Pour aller plus vite on utilise aussi la courbure $\nabla^2L$ : méthode de Newton (§7), qui montre au passage que $L$ est convexe.
- ⑦Plus de deux classes. Un score par classe, softmax à la place de $\sigma$, même cross-entropy. Pour $K = 2$ on retombe exactement sur la régression logistique.
À la fin du chapitre, tu dois savoir…
- écrire le modèle $P(y = 1\mid\bx,\bw) = \sigma(\bw\T\bx)$, sa frontière, et dire pourquoi $\|\bw\|$ règle la « raideur » ;
- passer de la vraisemblance à la cross-entropy, dans les deux conventions d'étiquettes ($\{0,1\}$ et $\{-1,+1\}$) ;
- prouver $\mathbb 1(yf\le0)\le\frac1{\ln2}\ln(1+e^{-yf})$ ;
- dériver $\nabla L$ et $\nabla^2L$, montrer que $\nabla^2L\succeq0$ (convexité) ;
- faire un pas de Newton à la main sur un petit exemple ;
- montrer que softmax à 2 classes = sigmoïde.
Où se trouve chaque question du HW2 dans ce chapitre
P1.(1) softmax → §8 · P1.(2) hessienne et convexité → §7 · P1.(3) cross-entropy → §5 · P1.(4) borne 0-1 → §5 · P2 Newton à la main → §6 et §7. Indices et corrigés : page Devoirs.
Notations du chapitre
Toutes les lettres utilisées dans la page (et dans les slides), au même endroit. Garde cet onglet ouvert en relisant les slides.
| Symbole | Se lit / signifie | Nature | Où |
|---|---|---|---|
| Données | |||
| $N,\ D$ | nombre d'exemples ; dimension des entrées | entiers | partout |
| $\bx_n$ | entrée du $n$-ième exemple (en §1, $x$ non gras = exemple abstrait : un e-mail, une image…) | vecteur de $\R^D$ | partout |
| $y_n$ | étiquette du $n$-ième exemple — deux conventions, voir l'encadré plus bas | $\{-1,+1\}$ ou $\{0,1\}$ | partout |
| $Z$ | le jeu de données $\{(\bx_n,y_n)\}_{n=1}^N$ | ensemble | §5 |
| $\mathcal X,\ \mathcal Y,\ \mathcal D$ | ensemble des entrées ; des étiquettes ; vraie loi (inconnue) des couples $(\bx,y)$ | ensembles, loi | §1 |
| Modèle | |||
| $\bw,\ b$ | vecteur de poids (orientation de la frontière) ; biais (sa position) | $\R^D$, $\R$ | §2, §4 |
| $\tilde\bx,\ \tilde\bw$ | vecteurs augmentés $[\bx\T,1]\T$, $[\bw\T,b]\T$ pour écrire $\bw\T\bx+b = \tilde\bw\T\tilde\bx$. Après §4, les slides écrivent simplement $\bx$, $\bw$ | $\R^{D+1}$ | §4 → |
| $f_\bw(\bx)$ | le score linéaire $\bw\T\bx$ (aussi appelé logit, activation) | réel | §2 → |
| $\sigma(t)$ | sigmoïde (fonction logistique) $1/(1+e^{-t})$ | $\R\to(0,1)$ | §3 → |
| $\eta(\bx),\ p_\bw(\bx),\ \hat y_n$ | la même quantité sous trois noms : probabilité prédite de la classe positive, $\sigma(\bw\T\bx)$ ; $\hat y_n$ est sa valeur en $\bx_n$. Ce n'est pas une étiquette | $(0,1)$ | §4, §5 → |
| $h(\bx)$ | classifieur : la classe prédite (seuil $\frac12$ sur la probabilité, 0 sur le score) | étiquette | §1, §4 |
| $H$ | la frontière de décision $\{\bx : \bw\T\bx+b = 0\}$ | hyperplan | §4 |
| $m = y\,f_\bw(\bx)$ | marge fonctionnelle (convention $y = \pm1$) : $>0$ ⇔ bien classé | réel | §2, §5 |
| Pertes | |||
| $\mathbb 1(A)$ | indicatrice : 1 si $A$ est vrai, 0 sinon | $\{0,1\}$ | §1, §5 |
| $\ell_{01},\ \ell_{\text{CE}}$ | perte 0-1 $\mathbb 1(yf\le0)$ ; perte logistique (cross-entropy) $\ln(1+e^{-yf})$ d'un exemple | $\ge0$ | §5 |
| $L(\bw)$ | la somme des pertes sur les données = log-vraisemblance négative. Slide 33 l'appelle $J(\bw)$. Le HW2 utilise la moyenne $L_{\text{CE}} = L/N$ | $\R^{D+1}\to\R_+$ | §5 → |
| $H(r,q)$ | cross-entropy entre la loi cible $r$ et la loi prédite $q$ (les slides écrivent aussi $p$ pour $r$) | $\ge0$ | §5 |
| $r_n,\ q_{\bw,n}$ | loi « one-hot » sur la vraie étiquette $y_n$ ; loi prédite $p(\cdot\mid\bx_n,\bw)$ | lois sur $\mathcal Y$ | §5 |
| Optimisation | |||
| $\nabla L(\bw)$ | gradient : vecteur colonne des $\partial L/\partial w_i$ (slide 33 l'écrit en ligne, avec $\bx_n\T$) | $\R^{D+1}$ | §6 → |
| $\nabla^2L(\bw),\ \bm H$ | hessienne : matrice des $\partial^2L/\partial w_i\partial w_j$ (courbure) | matrice symétrique | §7 |
| $\gamma$ | pas (learning rate) de la descente de gradient | réel $>0$ | §6 |
| $\bw^{(k)},\ \bw^{\text{old}},\ \bw^{\text{new}}$ | itéré numéro $k$ ; avant / après une mise à jour | vecteurs | §6, §7 |
| $\mathbf X,\ \hat\by,\ \mathbf R$ | matrice $N\times(D{+}1)$ des entrées en lignes ; vecteur des $\hat y_n$ ; $\operatorname{diag}(\hat y_n(1-\hat y_n))$ | matrices | §7 |
| Multiclasse | |||
| $K,\ \bw_k,\ y_{kn}$ | nombre de classes ; poids de la classe $k$ ; $\mathbb 1[y_n = k]$ (codage one-hot) | entier, vecteurs, $\{0,1\}$ | §8 |
Pièges de notation (ils viennent des slides)
- Deux conventions d'étiquettes, pour le même modèle.
- $y\in\{-1,+1\}$ quand on parle de marge et de perte logistique $\ln(1+e^{-yf})$ : §2, la frontière en §4, l'interprétation cross-entropy et la majoration de l'erreur 0-1 en §5.
- $y\in\{0,1\}$ quand on écrit la vraisemblance $\hat y^{\,y}(1-\hat y)^{1-y}$ et le gradient $\sum_n(\hat y_n-y_n)\bx_n$ : §5, §6, §7 et le HW2.
- Trois « H » différents : l'hyperplan $H$ (§4), la cross-entropy $H(r,q)$ (§5), la hessienne $\bm H = \nabla^2L$ (§7).
- $\bx$ et $\bw$ deviennent silencieusement augmentés après §4 : $\bw\T\bx$ contient alors le biais.
- Somme ou moyenne ? Les slides minimisent la somme $L(\bw)$ ; le HW2 la moyenne $L_{\text{CE}} = L/N$. Même minimiseur ; gradient et hessienne sont divisés par $N$, et le pas de Newton est identique (le $N$ se simplifie).
- Mêmes objets, noms différents : $J = L$ (slide 33), $p_n = r_n$ (slide 16), $\eta = p_\bw = \hat y$.
1Le problème de classification
Où on en est
Acquis
Chapitre 1 (régression) : prédire un réel $y$ avec un modèle linéaire, perte carrée, solution par moindres carrés.
Il manque
Et si $y$ est une catégorie (spam / pas spam, chiffre 0–9) ? Que veut dire « bien prédire », et que faut-il minimiser ?
Cette partie
On écrit le but (minimiser le taux d'erreur) et on voit pourquoi on ne peut pas l'optimiser directement. Tout le reste du chapitre sert à contourner cet obstacle.
Objectif — classification supervisée hors-ligne
Trouver un classifieur $h:\mathcal X\to\mathcal Y$ dont la prédiction $h(x)$ coïncide avec la vraie étiquette $y$ :
$$\min_{h\in\mathcal F}\ \E_{(x,y)\sim\mathcal D}\ \mathbb 1\big(h(x)\ne y\big).$$
Les exemples d'entraînement sont supposés i.i.d. selon $\mathcal D$. Exemples : reconnaissance d'écriture, de parole, filtrage de spam, prédiction du prochain token (un LLM est un classifieur à ~100 000 classes !).
Les objets en jeu
- $\mathcal X$
- ensembleL'ensemble des exemples possibles (entrées) : ex. $\R^D$ pour des vecteurs de features, les e-mails pour le spam.
- $\mathcal Y$
- ensemble finiL'ensemble des étiquettes (labels, classes). Binaire : $\{0,1\}$ ou $\{-1,+1\}$ (les deux conventions apparaissent dans les slides) ; multiclasse : $\{1,\dots,K\}$.
- $\mathcal D$
- loi sur $\mathcal X\times\mathcal Y$La vraie loi (inconnue) des couples (exemple, étiquette) — l'analogue de $p(x,y)$ du chapitre 1, mais $y$ est maintenant discret : $\mathcal D$ = « loi marginale $p(x)$ » × « probabilités de classes $P(y\mid x)$ ».
- $h$
- fonction $\mathcal X\to\mathcal Y$Le classifieur (hypothèse) : il rend une classe, pas un nombre réel.
- $\mathcal F$
- ensemble de fonctionsLa classe d'hypothèses dans laquelle on cherche $h$ (ex. tous les classifieurs linéaires). Question des slides p.6 : How should we define $\mathcal F$?
- $\mathbb 1(A)$
- 0 ou 1Indicatrice : vaut 1 si l'événement $A$ est vrai, 0 sinon. $\mathbb 1(h(x)\ne y)$ = « perte 0-1 » d'un exemple.
- $\E\,\mathbb 1(h(x)\ne y)$
- nombre dans $[0,1]$$= P_{\mathcal D}(h(x)\ne y)$ : le taux d'erreur (vrai risque 0-1) de $h$. L'espérance d'une indicatrice est une probabilité.
Notation : ici $x$ (non gras) est un exemple abstrait (un e-mail, une image…). Dès le §2 on représente chaque exemple par un vecteur de features, $\mathcal X = \R^D$, et on écrit $\bx$ en gras.
Pourquoi ne pas minimiser directement l'erreur ? La perte 0-1 est une fonction en escalier des paramètres : son gradient est nul presque partout (et infini aux sauts) — impossible à optimiser par descente de gradient, et le problème est NP-difficile en général. Toute la suite du chapitre consiste à remplacer $\mathbb 1$ par une perte de substitution (surrogate) lisse et convexe.
2Pourquoi pas les moindres carrés ?
Où on en est
Acquis
Le but : minimiser l'erreur 0-1 $\E\,\mathbb 1(h(\bx)\ne y)$, mais elle est en escalier, donc inoptimisable par gradient.
Il manque
Une perte lisse à la place. Le réflexe : réutiliser les moindres carrés du chapitre 1. Est-ce que ça marche ?
Cette partie
On écrit la perte carrée en fonction de la marge $m = y\,f_\bw(\bx)$ et on trouve son défaut. On en déduit ce qu'il faut à la place : une perte qui décroît avec $m$, et une façon de parler de probabilité.
Extension directe (slide 8) : coder les classes $y_n\in\{-1,+1\}$, ajuster le score linéaire $f_{\bw}(\bx) = \bw\T\bx$ par moindres carrés, $$\hat\bw_{\text{LS}} = \argmin_\bw\frac1N\sum_{n=1}^N\big(y_n - f_\bw(\bx_n)\big)^2,$$ puis prédire $h(\bx) = \operatorname{sign}(f_{\hat\bw}(\bx))$ ($+1$ si le score est positif, $-1$ sinon). Pas de biais pour l'instant : il sera ajouté au §4 par l'astuce des vecteurs augmentés.
Marge fonctionnelle (margin)
$$m := y\,f_{\bw}(\bx).\qquad m>0 \iff \text{bien classé};\quad |m| \text{ grand} \iff \text{confiant}.$$
Avec $y\in\{-1,+1\}$ : $(y - f)^2 = y^2(1 - yf)^2 = (1-m)^2$ car $y^2 = 1$. La perte carrée ne dépend que de la marge.
Les objets en jeu
- $f_{\bw}(\bx) = \bw\T\bx$
- réelLe score linéaire. Son signe donne la classe, sa valeur absolue une mesure de confiance.
- $m = y f_{\bw}(\bx)$
- réelLa marge (fonctionnelle) de l'exemple : positive si le score a le bon signe. À ne pas confondre avec la marge géométrique du chapitre SVM ($m/\|\bw\|$).
- $(1-m)^2$
- perte ≥ 0La perte carrée vue comme fonction de la marge : une parabole de minimum en $m = 1$.
Le problème : la parabole $(1-m)^2$ remonte pour $m>1$. Un point très bien classé ($m = 5$) est pénalisé comme un point mal classé ($m = -3$) ! Les moindres carrés « tirent » la frontière vers ces points trop corrects, au détriment des autres. Dans la scène, clique « + points très corrects » : la frontière des moindres carrés (bleue) bascule et se met à faire des erreurs, la logistique (jaune) ne bouge presque pas.
3La fonction logistique (sigmoïde)
Où on en est
Acquis
Un score linéaire $f_\bw(\bx) = \bw\T\bx\in\R$ dont le signe donne la classe ; mais l'ajuster par moindres carrés est une mauvaise idée.
Il manque
On voudrait sortir une probabilité $P(y = +1\mid\bx)\in(0,1)$, pas un score dans $\R$.
Cette partie
L'outil qui convertit un score en probabilité : la sigmoïde $\sigma$, et les quatre propriétés qui serviront dans tous les calculs suivants.
▶ Vidéosen anglais · s'ouvrent sur YouTube
Fonction logistique
$$\sigma(t) = \frac{1}{1+e^{-t}},\qquad \sigma:\R\to(0,1).$$
- $\sigma(t)\to0$ quand $t\to-\infty$, $\ \sigma(t)\to1$ quand $t\to+\infty$ ;
- symétrie : $\sigma(-t) = 1-\sigma(t)$ ;
- inverse (logit) : $\sigma^{-1}(p) = \ln\frac{p}{1-p}$ pour $p\in(0,1)$ ;
- dérivée : $\frac{d}{dt}\sigma(t) = \sigma(t)\sigma(-t) = \sigma(t)(1-\sigma(t))$.
Les objets en jeu
- $t$
- réelUn score quelconque, typiquement $t = \bw\T\bx$. Aussi appelé activation ou logit.
- $\sigma(t)$
- probabilité $\in(0,1)$« Écrase » tout $\R$ dans $(0,1)$ de façon lisse et croissante. $\sigma(0) = \frac12$.
- $\frac{p}{1-p}$
- réel $>0$La cote (odds) : « combien de fois plus probable que l'inverse ». $p = 0.8$ ⇒ cote 4 (« 4 contre 1 »).
- $\ln\frac{p}{1-p}$
- réelLe log-odds ou logit, qui parcourt tout $\R$ quand $p$ parcourt $(0,1)$ : c'est pourquoi on peut le modéliser par une fonction linéaire.
Preuve — symétrie, logit et dérivée de $\sigma$
Symétrie. $1-\sigma(t) = \frac{1+e^{-t}-1}{1+e^{-t}} = \frac{e^{-t}}{1+e^{-t}} = \frac{1}{e^{t}+1} = \sigma(-t)$ (on a multiplié haut et bas par $e^t$). Géométriquement : le graphe est symétrique par rapport au point $(0,\frac12)$.
Logit. $p = \frac1{1+e^{-t}} \iff 1+e^{-t} = \frac1p \iff e^{-t} = \frac{1-p}{p} \iff t = \ln\frac{p}{1-p}$.
Dérivée. $\sigma'(t) = \frac{d}{dt}(1+e^{-t})^{-1} = \frac{e^{-t}}{(1+e^{-t})^2} = \underbrace{\frac1{1+e^{-t}}}_{\sigma(t)}\cdot\underbrace{\frac{e^{-t}}{1+e^{-t}}}_{\sigma(-t) = 1-\sigma(t)}$.
Conséquence : $\sigma'$ est maximale en $t=0$ où elle vaut $\frac12\cdot\frac12 = \frac14$ (slide p.9 : « 1/4 »), et tend vers 0 aux extrémités : la sigmoïde est presque plate pour les grands $|t|$ (saturation).
∎
4Le modèle de régression logistique
Où on en est
Acquis
$\sigma$ envoie $\R$ sur $(0,1)$ ; son inverse, le logit $\ln\frac{p}{1-p}$, envoie $(0,1)$ sur $\R$.
Il manque
Comment fabriquer un modèle de probabilité à partir d'un modèle linéaire ?
Cette partie
On modélise linéairement le log-odds ⇒ $P(y = +1\mid\bx) = \sigma(\bw\T\bx+b)$. On étudie la frontière qu'il définit. Le modèle est alors fixé ; ses paramètres $\bw, b$ restent à apprendre.
▶ Vidéosen anglais · s'ouvrent sur YouTube
Pourquoi « régression » logistique ? (slide 10). Un modèle linéaire sort une valeur dans $\R$ ; une probabilité vit dans $(0,1)$. Mais le log-odds vit dans $\R$ : on régresse linéairement le log-odds.
$$\ln\frac{p_{\bw}(\bx)}{1-p_{\bw}(\bx)} = f_{\bw}(\bx)\quad\iff\quad p_{\bw}(\bx) = \sigma\big(f_{\bw}(\bx)\big),\qquad p_{\bw}(\bx) := p(y=+1\mid\bx,\bw).$$Modèle de régression logistique (binaire)
$$\eta(\bx) = \sigma(\bw\T\bx + b) = \sigma(\tilde\bw\T\tilde\bx),\qquad \tilde\bw = [\bw\T, b]\T,\ \tilde\bx = [\bx\T, 1]\T,$$
$$h(\bx) = \begin{cases}+1 & \text{si } \sigma(\tilde\bw\T\tilde\bx)\ge 0.5\\ -1 & \text{sinon}\end{cases} = \begin{cases}+1 & \text{si } \tilde\bw\T\tilde\bx\ge 0\\ -1&\text{sinon.}\end{cases}$$
Les objets en jeu
- $\bx\in\R^D$
- vecteurL'entrée (ou ses features $\bphi(\bx)$ : tout le chapitre 1 sur les fonctions de base s'applique, PRML §4.3.1).
- $\bw\in\R^D,\ b\in\R$
- paramètresLe vecteur de poids (orientation de la frontière) et le biais (bias, intercept : position de la frontière).
- $\tilde\bx,\ \tilde\bw\in\R^{D+1}$
- vecteurs augmentésAstuce d'écriture : on ajoute une coordonnée constante 1 à $\bx$ et $b$ à $\bw$ pour écrire $\bw\T\bx+b = \tilde\bw\T\tilde\bx$. Les slides réutilisent la même lettre ($\bw$, $\bx$) pour les versions augmentées.
- $\eta(\bx) = p_{\bw}(\bx)$
- probabilitéLa probabilité prédite de la classe $+1$ en $\bx$. Le modèle décrit donc toute une loi de Bernoulli $P(y\mid\bx)$ en chaque point.
- $h(\bx)$
- classeLe classifieur obtenu en seuillant la probabilité à $\frac12$ ⇔ en seuillant le score à 0.
- $H$
- hyperplan de $\R^D$La frontière de décision $\{\bx : \bw\T\bx + b = 0\}$ : une droite en 2D, un plan en 3D.
Convention à partir d'ici
Comme les slides, on écrit désormais simplement $\bx$ et $\bw$ pour les vecteurs augmentés $\tilde\bx = [\bx\T,1]\T$ et $\tilde\bw = [\bw\T,b]\T$ : $\bw\T\bx$ contient le biais. Et $\eta(\bx)$, $p_\bw(\bx)$, $\hat y_n = \sigma(\bw\T\bx_n)$ désignent la même chose : la probabilité prédite de la classe positive.
Géométrie de la frontière
Le vecteur $\bw$ est perpendiculaire à la frontière $H$ et pointe vers la région $\bw\T\bx+b>0$ (classe $+1$). La quantité $\frac{\bw\T\bx+b}{\|\bw\|}$ est la distance signée de $\bx$ à $H$ (prouvé au chapitre SVM). Donc $p_{\bw}(\bx) = \sigma\big(\|\bw\|\cdot\text{distance signée}\big)$ : la probabilité dépend seulement de la distance à la frontière, et $\|\bw\|$ règle la raideur de la transition. Multiplier $\bw$ et $b$ par 10 ne change pas la frontière (ni les prédictions), mais rend le modèle 10 fois plus « sûr de lui ». En 3D ci-dessous : la surface $\sigma(\bw\T\bx+b)$ est une « marche » lisse posée sur le plan, orientée selon $\bw$.
D'où vient la sigmoïde ? Le point de vue génératif Hors slides PRML §4.2 p.196–200
On a choisi de modéliser le log-odds linéairement. Ce choix n'est pas arbitraire : dans un cas classique, la vraie probabilité a posteriori est exactement de cette forme. Le meilleur classifieur possible (classifieur de Bayes) prédit la classe la plus probable : $h^*(x) = \argmax_k P(y = k\mid x)$ (PRML §1.5.1). Supposons que chaque classe produise ses exemples selon une gaussienne, de même covariance $\bSigma$ : $p(\bx\mid y=k) = \N(\bx\mid\bmu_k,\bSigma)$, avec probabilités a priori $\pi_k$. Alors par Bayes :
$$P(y=1\mid\bx) = \frac{\pi_1\N(\bx|\bmu_1,\bSigma)}{\pi_1\N(\bx|\bmu_1,\bSigma)+\pi_0\N(\bx|\bmu_0,\bSigma)} = \sigma\big(a(\bx)\big),\qquad a(\bx) = \ln\frac{\pi_1\N(\bx|\bmu_1,\bSigma)}{\pi_0\N(\bx|\bmu_0,\bSigma)} = \bw\T\bx + b,$$avec $\bw = \bSigma^{-1}(\bmu_1-\bmu_0)$ : les termes quadratiques $\bx\T\bSigma^{-1}\bx$ se simplifient dans le rapport. Le log-rapport des probabilités (log-odds) est exactement linéaire, et la probabilité a posteriori est exactement une sigmoïde d'une fonction linéaire. La régression logistique modélise directement cette forme sans supposer les gaussiennes (approche discriminative). Si les covariances diffèrent, les termes quadratiques ne s'annulent plus : frontière courbe.
Preuve — le log-odds de deux gaussiennes de même covariance est affine
$\ln\N(\bx|\bmu,\bSigma) = -\frac12(\bx-\bmu)\T\bSigma^{-1}(\bx-\bmu) + c$ où $c = -\frac D2\ln 2\pi - \frac12\ln|\bSigma|$ ne dépend pas de la classe.
Développons : $-\frac12\bx\T\bSigma^{-1}\bx + \bmu\T\bSigma^{-1}\bx - \frac12\bmu\T\bSigma^{-1}\bmu + c$.
Dans $a(\bx) = \ln\pi_1 + \ln\N(\bx|\bmu_1,\bSigma) - \ln\pi_0 - \ln\N(\bx|\bmu_0,\bSigma)$, les termes $-\frac12\bx\T\bSigma^{-1}\bx$ et $c$ apparaissent avec des signes opposés et s'annulent.
Il reste $a(\bx) = (\bmu_1-\bmu_0)\T\bSigma^{-1}\bx\ -\ \frac12\bmu_1\T\bSigma^{-1}\bmu_1 + \frac12\bmu_0\T\bSigma^{-1}\bmu_0 + \ln\frac{\pi_1}{\pi_0}$, de la forme $\bw\T\bx + b$.
Enfin $\frac{A}{A+B} = \frac{1}{1+B/A} = \frac1{1+e^{-\ln(A/B)}} = \sigma(\ln\frac AB)$ : la probabilité a posteriori est $\sigma(a(\bx))$.
∎
5Apprentissage : maximum de vraisemblance
Où on en est
Acquis
Le modèle $P(y = 1\mid\bx,\bw) = \sigma(\bw\T\bx)$ (avec $\bx,\bw$ augmentés : le biais est dedans).
Il manque
Un critère pour choisir $\bw$ à partir des données $Z$.
Cette partie
Maximum de vraisemblance ⇒ une perte $L(\bw)$, la cross-entropy. On vérifie ensuite qu'elle répond au problème du §1 : elle majore l'erreur 0-1. Attention : on passe ici aux étiquettes $y_n\in\{0,1\}$ (puis on fait le lien avec $\pm1$).
▶ Vidéosen anglais · s'ouvrent sur YouTube
Maximisation de la log-vraisemblance
$$\hat\bw = \argmax_{\bw} p(Z\mid\bw),\qquad p(Z\mid\bw) = \prod_{n=1}^N p(\bx_n,y_n\mid\bw) = \prod_{n=1}^N p(y_n\mid\bx_n,\bw)\,p(\bx_n\mid\bw) = \prod_{n=1}^N p(y_n\mid\bx_n,\bw)\,p(\bx_n).$$
La dernière égalité suppose que la loi des entrées ne dépend pas de $\bw$ : seul le terme conditionnel compte. Convention $y_n\in\{0,1\}$ (1 = classe positive) et $\hat y_n = \sigma(\bw\T\bx_n)$ :
$$p(y_n\mid\bx_n,\bw) = \hat y_n^{\,y_n}(1-\hat y_n)^{1-y_n},\qquad
\hat\bw = \argmin_{\bw}L(\bw),\qquad L(\bw) := -\ln\prod_{n=1}^Np(y_n\mid\bx_n,\bw) = -\sum_{n=1}^N\Big[y_n\ln\hat y_n + (1-y_n)\ln(1-\hat y_n)\Big].$$
Le $\ln$ transforme le produit en somme et ne change pas l'optimum (fonction croissante) ; le signe $-$ transforme le max en min. Les facteurs $p(\bx_n)$ deviennent une constante additive $-\sum_n\ln p(\bx_n)$, ignorée : c'est le « $\propto$ » de la slide 15. Le HW2 utilise la moyenne $L_{\text{CE}} = L/N$ : même minimiseur.
Les objets en jeu
- $Z$
- jeu de données$Z = \{(\bx_n,y_n)\}_{n=1}^N$, i.i.d. selon la vraie loi cachée $\mathcal D$.
- $p(Z\mid\bw)$
- fonction de $\bw$La vraisemblance du jeu de données complet sous le modèle de paramètre $\bw$ ; l'i.i.d. la factorise en produit.
- $p(\bx_n)$
- densité des entréesNe dépend pas de $\bw$ (on modélise seulement $P(y|\bx)$ : modèle discriminatif) ⇒ constante pour l'optimisation.
- $\hat y_n = \sigma(\bw\T\bx_n)$
- probabilitéLa probabilité prédite que $y_n = 1$. Attention : ce n'est pas une étiquette mais un nombre dans $(0,1)$.
- $\hat y^{\,y}(1-\hat y)^{1-y}$
- probabilité de BernoulliÉcriture compacte : vaut $\hat y$ si $y=1$, $1-\hat y$ si $y=0$ (l'exposant « sélectionne » le bon facteur). C'est la probabilité que le modèle attribue à l'étiquette effectivement observée.
- $L(\bw)$
- fonction $\R^{D+1}\to\R_+$La log-vraisemblance négative (NLL) : somme des $-\ln(\text{proba de la bonne étiquette})$. Une prédiction sûre et juste coûte ≈ 0 ; sûre et fausse coûte → ∞.
Image mentale (scène ci-dessous, données 1D) : chaque point est posé à hauteur 0 ou 1 selon sa classe ; la sigmoïde prédit une probabilité ; le segment vertical entre la courbe et l'étiquette mesure l'erreur, et la barre rouge est son coût $-\ln p(y_n|x_n)$. À droite, la NLL comme surface au-dessus du plan des paramètres $(w, b)$ : un bol convexe, mais pas une parabole.
Où on va maintenant. On a une perte $L(\bw)$. Deux questions : (1) a-t-elle un sens indépendant de la vraisemblance ? → oui, c'est une cross-entropy ; (2) répond-elle au problème du §1 (faire baisser l'erreur 0-1) ? → oui, elle la majore. Ce sont les deux sous-parties suivantes, où l'on repasse en convention $y\in\{-1,+1\}$ pour faire apparaître la marge.
Interprétation : entropie croisée
▶ Vidéosen anglais · s'ouvrent sur YouTube
Entropie croisée (cross-entropy)
Pour deux lois $r$ et $q$ sur un ensemble fini $\mathcal Y$ :
$$H(r,q) := -\sum_{y\in\mathcal Y} r(y)\ln q(y).$$
Avec la loi cible « one-hot » $r_n(y) = \mathbb 1(y = y_n)$ et la loi du modèle $q_{\bw,n}(y) = p(y\mid\bx_n,\bw)$ : $\ H(r_n,q_{\bw,n}) = -\ln p(y_n\mid\bx_n,\bw)$. Pour $y_n\in\{-1,+1\}$ :
$$H(r_n,q_{\bw,n}) = -\ln\sigma\big(y_nf_{\bw}(\bx_n)\big) = \ln\big(1+e^{-y_nf_{\bw}(\bx_n)}\big)\qquad\text{(la « logistic loss »).}$$
La NLL de chaque exemple est exactement sa perte d'entropie croisée.
Les objets en jeu
- $r$ (ou $p$ dans les slides)
- loi sur $\mathcal Y$La loi « cible » (vérité). Ici un Dirac sur l'étiquette observée : $r_n = (0,\dots,1,\dots,0)$ (vecteur one-hot).
- $q$
- loi sur $\mathcal Y$La loi prédite par le modèle, $q(+1) = \sigma(f)$, $q(-1) = 1-\sigma(f) = \sigma(-f)$.
- $H(r,q)$
- nombre $\ge0$Nombre moyen de « nats » nécessaires pour coder des symboles tirés de $r$ avec un code optimisé pour $q$. Minimal (= entropie de $r$) quand $q = r$ ; ici l'entropie d'un one-hot est 0.
Preuve — de la NLL en $\{0,1\}$ à la logistic loss en $\{-1,+1\}$
Pour un exemple, la NLL vaut $-\ln\hat y$ si l'étiquette est « positive » et $-\ln(1-\hat y)$ sinon, avec $\hat y = \sigma(f)$.
Par symétrie, $1-\sigma(f) = \sigma(-f)$. Donc en codant la classe positive par $y=+1$ et la négative par $y=-1$, les deux cas s'écrivent $-\ln\sigma(yf)$.
$-\ln\sigma(yf) = -\ln\frac{1}{1+e^{-yf}} = \ln(1+e^{-yf})$. Avec la marge $m = yf$ : $\ell_{\text{CE}}(m) = \ln(1+e^{-m})$, décroissante, convexe, $\approx -m$ pour $m\ll0$ et $\approx e^{-m}\to0$ pour $m\gg0$.
Correspondance des étiquettes : $y^{\{0,1\}} = \frac{1+y^{\{\pm1\}}}{2}$. Les deux écritures (slide 15 et slide 16) définissent le même problème d'optimisation.
∎
Pertes de substitution : la cross-entropy majore l'erreur 0-1
Majoration de la perte 0-1
Avec $h(\bx) = \operatorname{sign}(f(\bx))$, $y\in\{-1,+1\}$, $\ell_{01}(\bx,y,f) = \mathbb 1(yf(\bx)\le0)$ et $\ell_{\text{CE}}(\bx,y,f) = \ln(1+e^{-yf(\bx)})$ :
$$\mathbb 1(h(\bx)\ne y) \le C\cdot\ell_{\text{CE}}(\bx,y,f)\quad\text{avec } C = \frac1{\ln 2},\qquad\text{donc}\qquad \frac1N\sum_n\mathbb 1(h(\bx_n)\ne y_n) \le \frac CN\sum_n\ell_{\text{CE}}(\bx_n,y_n,f).$$
Minimiser la cross-entropy moyenne minimise un majorant de l'erreur empirique de classification.
Preuve — $\mathbb 1(m\le0)\le\frac{1}{\ln2}\ln(1+e^{-m})$
Posons $g(m) = \frac{\ln(1+e^{-m})}{\ln 2}$. $g$ est positive et décroissante (car $e^{-m}$ décroît).
Si $m>0$ : $\mathbb 1(m\le0) = 0\le g(m)$ car $g>0$.
Si $m\le0$ : $e^{-m}\ge1$ donc $1+e^{-m}\ge2$ donc $\ln(1+e^{-m})\ge\ln2$, soit $g(m)\ge1 = \mathbb 1(m\le 0)$.
En sommant sur les exemples on obtient la majoration de l'erreur empirique ; $C = 1/\ln2$ est la plus petite constante possible (égalité en $m = 0$).
∎
6Descente de gradient pour la régression logistique
Où on en est
Acquis
La perte à minimiser : $L(\bw) = -\sum_n\big[y_n\ln\hat y_n + (1-y_n)\ln(1-\hat y_n)\big]$ avec $\hat y_n = \sigma(\bw\T\bx_n)$, $y_n\in\{0,1\}$.
Il manque
Contrairement aux moindres carrés, $\nabla L(\bw) = 0$ n'a pas de solution explicite : $\hat y_n$ dépend de $\bw$ à travers $\sigma$, non linéaire.
Cette partie
On minimise par étapes avec la descente de gradient du chapitre 1. Le seul travail : calculer $\nabla L$.
Gradient de la NLL et règle de mise à jour
$$\nabla_{\bw} L(\bw) = -\sum_{n=1}^N\big(y_n - \hat y_n\big)\bx_n,\qquad \bw^{\text{new}}\leftarrow\bw^{\text{old}} + \gamma\sum_{n=1}^N\Big[y_n - \sigma\big(\bw^{\text{old}\top}\bx_n\big)\Big]\bx_n.$$
Même forme que pour la régression linéaire (« erreur × entrée ») : c'est une propriété des canonical link functions (PRML §4.3.6). Pas de forme close : $\hat y_n$ dépend de $\bw$ de façon non linéaire.
Les objets en jeu
- $y_n - \hat y_n$
- réel $\in(-1,1)$L'erreur de probabilité du point $n$ ($y_n\in\{0,1\}$). Proche de 0 si le point est bien et sûrement classé ⇒ il ne pousse presque plus.
- $(y_n - \hat y_n)\bx_n$
- vecteurLa « force » exercée par le point $n$ sur $\bw$ : dans la direction de $\bx_n$ (ou de $-\bx_n$), d'intensité = l'erreur.
- $\gamma$
- réel $>0$Le pas, comme au chapitre 1.
- $\nabla_\bw L$
- vecteur colonneLe gradient : la liste des dérivées partielles $\partial L/\partial w_i$ (slide 26). L'indice $\bw$ précise par rapport à quoi on dérive ; la slide 23 écrit $\frac{\partial L}{\partial\bw}$ pour la même chose.
- $\hat y_n'$
- réelNotation abrégée de la slide 23 pour $\sigma'(\bw\T\bx_n) = \hat y_n(1-\hat y_n)$. Avec la règle de la chaîne : $\nabla_{\bw}\hat y_n = \hat y_n'\,\bx_n = \hat y_n(1-\hat y_n)\bx_n$.
Preuve — dérivation du gradient (slide 23)
Posons $\hat y_n = \sigma(\bw\T\bx_n)$. Règle de la chaîne + dérivée de $\sigma$ : $\nabla_{\bw}\hat y_n = \sigma'(\bw\T\bx_n)\,\bx_n = \hat y_n(1-\hat y_n)\,\bx_n$.
$\nabla_{\bw} L = -\sum_n\Big[y_n\frac{\nabla\hat y_n}{\hat y_n} + (1-y_n)\frac{-\nabla\hat y_n}{1-\hat y_n}\Big]$ (dérivée de $\ln u$ = $u'/u$).
On substitue : $= -\sum_n\Big[y_n\frac{\hat y_n(1-\hat y_n)}{\hat y_n} - (1-y_n)\frac{\hat y_n(1-\hat y_n)}{1-\hat y_n}\Big]\bx_n = -\sum_n\big[y_n(1-\hat y_n) - (1-y_n)\hat y_n\big]\bx_n$.
On développe le crochet : $y_n - y_n\hat y_n - \hat y_n + y_n\hat y_n = y_n - \hat y_n$. D'où $\nabla_{\bw} L = -\sum_n(y_n-\hat y_n)\bx_n$. Les facteurs $\hat y(1-\hat y)$ se simplifient exactement : c'est pour ça que la sigmoïde et la cross-entropy « vont ensemble ».
Version $\{-1,+1\}$ : $\nabla_{\bw}\ln(1+e^{-y\bw\T\bx}) = -\sigma(-y\bw\T\bx)\,y\,\bx$ : poids $\sigma(-m)$, la probabilité d'erreur du modèle.
∎
Dans la scène : chaque flèche est la force $(y_n-\hat y_n)\tilde\bx_n$ (projetée dans le plan), la frontière se déplace pendant l'entraînement. Coche « données séparables » : la NLL n'a plus de minimum fini, $\|\bw\|$ croît sans fin et la sigmoïde devient une marche — il faut régulariser.
Données linéairement séparables Hors slides PRML p.206. Si un hyperplan sépare parfaitement les classes, alors $L(c\bw)\to0$ quand $c\to\infty$ (toutes les marges $\to+\infty$). L'infimum n'est pas atteint : le MLE « n'existe pas », les poids divergent. Remède : ajouter $\lambda\|\bw\|^2$ (MAP avec prior gaussien, comme au chapitre 1), ou arrêter tôt.
7Méthode de Newton (second ordre)
Où on en est
Acquis
La descente de gradient fonctionne, avec $\nabla L = \sum_n(\hat y_n - y_n)\bx_n$.
Il manque
GD n'utilise que la pente : beaucoup d'itérations, et un pas $\gamma$ à régler.
Cette partie
Utiliser aussi la courbure (hessienne) : approcher $L$ par une parabole (Taylor à l'ordre 2) et sauter à son minimum. Appliqué à la logistique, cela demande $\nabla^2L$, qui prouve au passage que $L$ est convexe. C'est le cœur du HW2.
▶ Vidéosen anglais · s'ouvrent sur YouTube
La courbure apporte une information que le gradient n'a pas. Plan de la section, comme dans les slides : rappels (hessienne, Taylor) → la règle de Newton → pourquoi elle marche → application à la logistique. Gradient = direction et vitesse de variation locale ; hessienne = variation du gradient (courbure).
Hessienne · Série de Taylor
$$\bm H := \nabla^2 f(\bx) = \Big[\frac{\partial^2 f(\bx)}{\partial x_i\partial x_j}\Big]_{i,j}\in\R^{D\times D},\qquad \bm H = \frac{\partial}{\partial\bx}\nabla f(\bx).$$
Pour $f$ lisse sur $\R$ : $T_\infty(x) = \sum_{k=0}^\infty\frac{f^{(k)}(x_0)}{k!}(x-x_0)^k$ ; la troncature $T_k$ approche $f$ près de $x_0$. En dimension $D$, à l'ordre 2 :
$$f(\bx)\approx\tilde f(\bx) = f(\bx_k) + \nabla f(\bx_k)\T(\bx-\bx_k) + \tfrac12(\bx-\bx_k)\T\nabla^2 f(\bx_k)(\bx-\bx_k).$$
Les objets en jeu
- $\frac{\partial^2 f}{\partial x_i\partial x_j}$
- réelDérivée seconde croisée : comment la pente selon $x_j$ change quand on bouge $x_i$. Symétrique ($i\leftrightarrow j$) sous hypothèse de régularité (Schwarz).
- $\nabla^2 f(\bx)$
- matrice symétrique $D\times D$La hessienne. Ses valeurs propres = courbures le long de ses vecteurs propres. Toutes $>0$ : cuvette (minimum local) ; signes mêlés : selle.
- $f^{(k)}(x_0)$
- réel$k$-ième dérivée en $x_0$.
- $\tilde f$
- fonction quadratiqueL'approximation quadratique (parabole / paraboloïde tangent) de $f$ en $\bx_k$ : même valeur, même pente et même courbure en $\bx_k$.
Méthode de Newton
$$\bw^{\text{new}}\leftarrow\bw^{\text{old}} - \big[\nabla^2L(\bw^{\text{old}})\big]^{-1}\nabla L(\bw^{\text{old}})\qquad\text{(à comparer avec GD : } \bw^{\text{new}}\leftarrow\bw^{\text{old}}-\gamma\nabla L\text{)}.$$
Pas de pas $\gamma$ explicite : l'inverse de la hessienne redimensionne le gradient selon la courbure locale. Convergence beaucoup plus rapide (quadratique près de l'optimum), mais chaque itération coûte plus cher : former $\nabla^2L$ ($O(ND^2)$) et la résoudre ($O(D^3)$).
Idée géométrique (slides p.29, 32) : en $\bw^{(k)}$, remplacer $L$ par sa parabole tangente $\tilde L$ et sauter directement au fond de cette parabole. Si $L$ est presque quadratique, on tombe presque sur le vrai minimum en un pas. Attention : si la courbure locale est négative, le fond de la parabole est un maximum — Newton peut monter (scène 1D, départ près de la bosse).
Preuve — justification de la mise à jour de Newton (slide 31)
Taylor à l'ordre 2 en $\bw^{(k)}$ : $L(\bw)\approx\tilde L(\bw) = L(\bw^{(k)}) + \nabla L(\bw^{(k)})\T(\bw-\bw^{(k)}) + \frac12(\bw-\bw^{(k)})\T\nabla^2L(\bw^{(k)})(\bw-\bw^{(k)})$.
Gradient de la quadratique (règles du chapitre 1 avec la hessienne symétrique) : $\nabla\tilde L(\bw) = \nabla L(\bw^{(k)}) + \nabla^2L(\bw^{(k)})(\bw-\bw^{(k)})$.
On l'annule : $\nabla^2L(\bw^{(k)})(\bw - \bw^{(k)}) = -\nabla L(\bw^{(k)})$, d'où $\bw = \bw^{(k)} - [\nabla^2L(\bw^{(k)})]^{-1}\nabla L(\bw^{(k)})$.
C'est le minimum de $\tilde L$ si $\nabla^2L(\bw^{(k)})\succ0$. Si $L$ est fortement convexe, sa hessienne est définie positive en tout itéré (slide 30) : chaque pas vise bien un minimum.
Hors slides Sur une quadratique exacte $L = \frac12\bw\T\bA\bw - \bb\T\bw$, $\nabla^2L = \bA$ et Newton donne $\bw^{(k)} - \bA^{-1}(\bA\bw^{(k)}-\bb) = \bA^{-1}\bb$ : l'optimum en un seul pas, quel que soit le conditionnement (pas de zigzag, contrairement à GD au chapitre 1).
∎
Newton pour la régression logistique
Il ne reste qu'à calculer les deux ingrédients de la règle de Newton pour notre $L$. Sur la slide 33, $J(\bw)$ désigne le même $L(\bw)$, et le gradient y est écrit en ligne (avec $\bx_n\T$, convention « dérivée = vecteur ligne » de la slide 26) ; ici on l'écrit en colonne, ce qui donne la même hessienne.
Gradient et hessienne de la NLL logistique
$$\nabla L(\bw) = -\sum_n(y_n-\hat y_n)\bx_n = \mathbf X\T(\hat\by-\by),\qquad \nabla^2L(\bw) = \sum_{n=1}^N\hat y_n(1-\hat y_n)\,\bx_n\bx_n\T = \mathbf X\T\mathbf R\mathbf X,$$
où $\mathbf R = \operatorname{diag}\big(\hat y_n(1-\hat y_n)\big)$. La hessienne est semi-définie positive ⇒ $L$ est convexe : pas de minimum local parasite.
Les objets en jeu
- $\mathbf X\in\R^{N\times(D+1)}$
- matriceLes entrées augmentées en lignes (la design matrix du chapitre 1).
- $\bx_n\bx_n\T$
- matrice $(D{+}1)\times(D{+}1)$ de rang 1Produit extérieur : la courbure apportée par le point $n$ est concentrée dans la direction $\bx_n$.
- $\hat y_n(1-\hat y_n)$
- poids $\in(0,\frac14]$= $\sigma'$ : les points incertains ($\hat y\approx\frac12$) courbent beaucoup la NLL, les points sûrs presque pas.
- $\mathbf R$
- matrice diagonaleLes poids de chaque point. Newton = moindres carrés pondérés par $\mathbf R$, répétés : d'où le nom IRLS (iteratively reweighted least squares).
Preuve — hessienne et convexité
Ce qu'on dérive. La hessienne est la dérivée du gradient $\nabla L = \sum_n\bg_n$ avec $\bg_n := -(y_n-\hat y_n)\bx_n = (\hat y_n-y_n)\bx_n$. Dans $\bg_n$, $y_n$ et $\bx_n$ sont des constantes (des données) ; seul le nombre $\hat y_n = \sigma(t_n)$, avec $t_n := \bw\T\bx_n$, dépend de $\bw$.
Ingrédient : $\nabla_{\bw}\hat y_n$. Pour une composante, règle de la chaîne : $\frac{\partial\hat y_n}{\partial w_j} = \sigma'(t_n)\,\frac{\partial t_n}{\partial w_j}$. Or $t_n = \sum_kw_kx_{n,k}$, dont seul le terme $w_jx_{n,j}$ dépend de $w_j$ : $\frac{\partial t_n}{\partial w_j} = x_{n,j}$. En empilant les composantes, le facteur commun $\sigma'(t_n)$ sort : $\nabla_{\bw}\hat y_n = \sigma'(t_n)\,\bx_n = \hat y_n(1-\hat y_n)\,\bx_n$ (car $\sigma' = \sigma(1-\sigma)$ et $\sigma(t_n) = \hat y_n$).
C'est un nombre fois un vecteur : bouger $\bw$ change $\hat y_n$ surtout dans la direction $\bx_n$, avec une intensité $\hat y_n(1-\hat y_n)\le\frac14$, maximale quand le modèle hésite ($\hat y_n = \frac12$) et presque nulle quand il est sûr.
Dériver un vecteur par un vecteur. $\bg_n\in\R^{D+1}$ et $\bw\in\R^{D+1}$ : le résultat est une matrice dont l'entrée $(i,j)$ est $\frac{\partial g_{n,i}}{\partial w_j}$ (ligne = composante dérivée, colonne = variable). Avec $g_{n,i} = (\hat y_n-y_n)\,x_{n,i}$ : la constante $x_{n,i}$ sort, $y_n$ a une dérivée nulle, et il reste $\frac{\partial g_{n,i}}{\partial w_j} = x_{n,i}\,\frac{\partial\hat y_n}{\partial w_j}$.
Ranger en matrice. « (composante $i$ de $\bx_n$) × (composante $j$ de $\nabla\hat y_n$) » est exactement l'entrée $(i,j)$ du produit d'une colonne par une ligne : $\frac{\partial\bg_n}{\partial\bw} = \bx_n\,(\nabla_{\bw}\hat y_n)\T$ ($\bx_n$ fournit l'indice de ligne, $(\nabla\hat y_n)\T$ celui de colonne). En remplaçant : $\bx_n\big(\hat y_n(1-\hat y_n)\bx_n\big)\T = \hat y_n(1-\hat y_n)\,\bx_n\bx_n\T$. En sommant sur $n$ : $\nabla^2L = \sum_n\hat y_n(1-\hat y_n)\bx_n\bx_n\T$.
Convexité. Pour tout $\bv$ : $\bv\T\bx_n\bx_n\T\bv = (\bx_n\T\bv)(\bx_n\T\bv) = (\bx_n\T\bv)^2$, donc $\bv\T\nabla^2L\,\bv = \sum_n\hat y_n(1-\hat y_n)(\bx_n\T\bv)^2\ge0$ car chaque poids $\hat y_n(1-\hat y_n)$ est $>0$ ($\hat y_n\in(0,1)$). Semi-définie positive partout ⇒ $L$ convexe. Définie positive si les $\bx_n$ engendrent $\R^{D+1}$.
Hors slides Newton s'écrit $\bw^{\text{new}} = (\mathbf X\T\mathbf R\mathbf X)^{-1}\mathbf X\T\mathbf R\,\mathbf z$ avec $\mathbf z = \mathbf X\bw^{\text{old}} - \mathbf R^{-1}(\hat\by-\by)$ : les équations normales d'un problème de moindres carrés pondérés (PRML 4.99–4.100).
∎
La scène ci-dessous : NLL d'un problème 1D en fonction de $(w,b)$. Bleu : GD ; jaune : Newton. Les ellipses violettes (2D) et le paraboloïde violet (3D) sont l'approximation quadratique $\tilde L$ au point courant de Newton : le pas suivant va exactement en son centre.
Question des slides — avantages et inconvénients de Newton (p.30, 35)
Réponse
✓ Convergence quadratique près de l'optimum, très peu d'itérations ; ✓ aucun pas à régler ; ✓ invariant aux changements d'échelle linéaires des paramètres (insensible au mauvais conditionnement). ✗ Coût par itération : calculer la hessienne $O(ND^2)$, la stocker $O(D^2)$, la résoudre $O(D^3)$ — inenvisageable pour un réseau de neurones à $10^9$ paramètres ; ✗ si la hessienne n'est pas définie positive (non convexe), le pas peut viser un maximum ou une selle ; ✗ loin de l'optimum, le pas plein peut être trop grand (on ajoute alors une line search, « Newton amorti »).
8Multiclasse : régression softmax
Où on en est
Acquis
Toute la recette binaire : modèle $\sigma(\bw\T\bx)$ → cross-entropy → gradient / Newton.
Il manque
Et avec $K>2$ classes ?
Cette partie
Même recette : un score par classe, la softmax à la place de $\sigma$, la même cross-entropy. Pour $K = 2$ on retombe exactement sur la sigmoïde.
▶ Vidéosen anglais · s'ouvrent sur YouTube
Softmax regression
$$p(y = k\mid\bx) = \frac{\exp(\bw_k\T\bx)}{\sum_{j=1}^K\exp(\bw_j\T\bx)},\qquad L(\bw) = -\sum_{n=1}^N\sum_{k=1}^K y_{kn}\ln p(y_n = k\mid\bx_n),\quad y_{kn} = \mathbb 1[y_n = k].$$
Les objets en jeu
- $K$
- entier ≥ 2Nombre de classes.
- $\bw_k\in\R^{D+1}$
- vecteurUn vecteur de poids par classe ; $\bw_k\T\bx$ est le score (logit) de la classe $k$.
- softmax
- $\R^K\to$ simplexeExponentie les scores (tout devient positif) puis normalise (somme 1). « Soft » argmax : la plus grande entrée domine d'autant plus que les écarts sont grands.
- $y_{kn}$
- 0 ou 1Codage one-hot de l'étiquette $n$ : la double somme ne garde que $-\ln p(y_n\mid\bx_n)$, la cross-entropy multiclasse.
Géométrie : la classe prédite est $\argmax_k\bw_k\T\bx$. Chaque score est un plan au-dessus de l'espace d'entrée ; la prédiction est le plan le plus haut (l'enveloppe supérieure en 3D) ; les frontières sont les droites où deux plans se croisent, $(\bw_j - \bw_k)\T\bx = 0$. Pour $K = 2$, softmax = sigmoïde de $(\bw_1-\bw_0)\T\bx$ : on retrouve le cas binaire. Seules les différences de $\bw_k$ comptent (ajouter le même vecteur à tous ne change rien).
Preuve — softmax à 2 classes = sigmoïde ; invariance par translation
$p(y=1|\bx) = \frac{e^{a_1}}{e^{a_0}+e^{a_1}} = \frac{1}{1+e^{-(a_1-a_0)}} = \sigma(a_1-a_0)$ avec $a_k = \bw_k\T\bx$ (diviser haut et bas par $e^{a_1}$).
Si $\bw_k\to\bw_k+\mathbf c$ pour tout $k$, chaque exponentielle est multipliée par $e^{\mathbf c\T\bx}$, qui se simplifie : les probabilités sont inchangées. Le modèle a donc $(K-1)(D+1)$ degrés de liberté effectifs.
Hors slides Gradient : $\nabla_{\bw_k}L = \sum_n(p(y=k|\bx_n) - y_{kn})\bx_n$, encore « erreur × entrée » (PRML 4.109).
∎
9Résumé & questions de la slide 35
Tout le chapitre en une chaîne
$$\underbrace{\min_h\E\,\mathbb 1(h(\bx)\ne y)}_{\text{§1 : le but}}\ \xrightarrow{\text{inoptimisable}}\ \underbrace{P(y=1\mid\bx) = \sigma(\bw\T\bx)}_{\text{§3–4 : le modèle}}\ \xrightarrow{\text{max. vraisemblance}}\ \underbrace{L(\bw) = -\sum_n\big[y_n\ln\hat y_n+(1-y_n)\ln(1-\hat y_n)\big]}_{\text{§5 : cross-entropy, majore l'erreur 0-1}}$$
$$\xrightarrow{\text{pas de formule close}}\ \underbrace{\nabla L = \sum_n(\hat y_n-y_n)\bx_n}_{\text{§6 : gradient}},\quad\underbrace{\nabla^2L = \sum_n\hat y_n(1-\hat y_n)\bx_n\bx_n\T\succeq0}_{\text{§7 : convexe}},\quad\underbrace{\bw\leftarrow\bw-[\nabla^2L]^{-1}\nabla L}_{\text{§7 : Newton}}$$
Quel lien entre minimiser l'erreur de classification et minimiser la cross-entropy ?
Réponse
L'erreur 0-1 n'est pas optimisable par gradient (constante par morceaux). La cross-entropy est une perte de substitution convexe et lisse qui la majore à une constante près : $\mathbb 1(yf\le0)\le\frac1{\ln2}\ln(1+e^{-yf})$. Minimiser la cross-entropy moyenne abaisse donc un majorant de l'erreur empirique. Et c'est aussi la NLL d'un modèle probabiliste (Bernoulli + sigmoïde) : on obtient des probabilités calibrées en prime.
Avantages et inconvénients de Newton ?
Réponse
Voir la section 7 : très peu d'itérations, pas de pas à régler, insensible au conditionnement ; mais hessienne coûteuse ($O(ND^2 + D^3)$ par itération), mémoire $O(D^2)$, et fiable seulement si la hessienne est définie positive.
Chapitre suivant : machines à vecteurs de support.