Régression linéaireLinear Regression — Basic Optimization · Cours 2 & 3 (9/10, 9/15)

Slides 2-linear-regression (47 p.) PRML ch. 3.1–3.3 DL ch. 4.1 DL ch. 7 (gradient descent) HW1 (dû le 29/09)

Ce chapitre répond à une seule question : comment prédire un nombre réel $y$ à partir d'une entrée $\bx$, en apprenant à partir d'exemples ? Il construit la réponse complète — le critère, le modèle, la formule, sa justification, ses limites et leurs remèdes — puis l'outil d'optimisation qui servira dans tous les chapitres suivants. Chaque section répond au problème laissé ouvert par la précédente ; au début de chacune, un encadré Où on en est fait le point.

Feuille de route

Slides p.2 (plan)

Les slides découpent le cours en cinq blocs : la régression (§1), la régression linéaire et les fonctions de base (§2–4), le ridge (§5–7), le lasso (§8), les méthodes de gradient (§9). La chaîne complète, cliquable :

① But · §1minimiser la MSE $\E[(y-f(\bx))^2]$meilleur $f$ : $\E[y\mid\bx]$, mais $p(\bx,y)$ inconnue

→

② Modèle · §2$f(\bx) = \bw\T\bphi(\bx)$linéaire en $\bw$, pas forcément en $\bx$

→

③ Apprentissage · §3MSE empirique ⇒ $\bw_{\text{LS}} = (\bPhi\T\bPhi)^{-1}\bPhi\T\by$une projection orthogonale

→

④ Justification · §4bruit gaussien ⇒ MLE = moindres carrésla perte carrée a une hypothèse cachée

→

⑤ Limite · §5trop de paramètres ⇒ sur-apprentissagetrain ↓, test ↑

→

⑥ Remèdes · §6–8pénaliser $\|\bw\|^2$ (ridge = MAP) ou $\|\bw\|_1$ (lasso)λ règle le compromis

→

⑦ Algorithme · §9pas de formule close ⇒ gradient, momentum, SGDl'outil de tous les chapitres suivants

Le raisonnement, maillon par maillon

①Fixer le critère. On veut que $f(\bx)$ soit proche de $y$ en moyenne : minimiser l'erreur quadratique moyenne $\E[(y-f(\bx))^2]$. On montre que le meilleur $f$ possible est l'espérance conditionnelle $\E[y\mid\bx]$. Mais elle dépend de la loi $p(\bx,y)$, qu'on ne connaît pas. → Il faut chercher $f$ dans une famille raisonnable, à partir d'exemples.
②Choisir la famille. $f(\bx) = \bw\T\bphi(\bx)$ : on transforme d'abord l'entrée par des fonctions de base $\bphi$ (puissances de $x$, gaussiennes…), puis on combine linéairement. Le modèle peut être une courbe en $\bx$, tout en restant linéaire en $\bw$ : c'est ce qui donnera une formule close.
③Apprendre $\bw$. On remplace la vraie MSE (inconnue) par sa moyenne sur les $N$ exemples, $\EMSE(\bw) = \frac1N\|\by-\bPhi\bw\|^2$, et on annule le gradient. On obtient les équations normales et $\bw_{\text{LS}}$. Géométriquement : $\bPhi\bw_{\text{LS}}$ est la projection orthogonale de $\by$ sur l'espace engendré par les colonnes de $\bPhi$. Si $\bPhi\T\bPhi$ n'est pas inversible, la pseudo-inverse choisit la solution de norme minimale.
④Justifier la perte carrée. Si $y = \bw\T\bphi(\bx) + \varepsilon$ avec un bruit gaussien, maximiser la vraisemblance des données revient exactement à minimiser la MSE empirique. Utiliser la perte carrée, c'est supposer un bruit gaussien.
⑤Constater la limite. Avec beaucoup de fonctions de base, la MSE d'entraînement tend vers 0 mais l'erreur sur de nouveaux points explose : le modèle apprend le bruit, avec des coefficients énormes. → Il faut contrôler la taille de $\bw$.
⑥Régulariser. Ajouter $\lambda\|\bw\|^2$ (ridge) : formule close toujours inversible. Vu de façon probabiliste, c'est un prior gaussien « $\bw$ est petit » (MAP). Avec $\lambda\|\bw\|_1$ (lasso), beaucoup de coefficients deviennent exactement nuls (sélection de variables) — mais il n'y a plus de formule close.
⑦Optimiser sans formule. La descente de gradient fait de petits pas dans la direction $-\nabla\hL$ ; le pas $\gamma$ est délicat, le momentum amortit les zigzags, et SGD remplace le gradient complet par celui d'un mini-batch (sans biais). C'est ce qu'on utilisera pour la régression logistique, les SVM, les réseaux…

À la fin du chapitre, tu dois savoir…

prouver que $\E[y\mid\bx]$ minimise la MSE (décomposition) ;
construire $\bPhi$, dériver les équations normales et $\bw_{\text{LS}}$, et expliquer le rôle de $\bPhi^\dagger\by$ ;
montrer MLE = moindres carrés sous bruit gaussien, et MAP = ridge avec $\bSigma = \frac{\sigma^2}{N\lambda}\bI$ ;
expliquer géométriquement pourquoi le lasso donne des solutions parcimonieuses ;
écrire la mise à jour de GD pour la régression linéaire, et prouver que le gradient de mini-batch est sans biais.

Où se trouve chaque question du HW1 dans ce chapitre

Q2.(1) → §1 · Q2.(2)(3) → §3 (et pseudo-inverse) · Q2.(4) → §5 · Q3.(1) → §4 · Q3.(2) → §7 · Q3.(3) → §6 · Q4.(1)–(3) → §9 · Q4.(4) → SGD. 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.

Symbole	Se lit / signifie	Nature	Où
Données et loi
$N$	nombre d'exemples d'entraînement	entier	partout
$\bx,\ \bx_n$	entrée (une observation), $n$-ième entrée. Souvent un scalaire $x$ dans les exemples (polynômes)	$\R^D$ (ou $\R$)	partout
$y,\ y_n$	sortie / cible réelle	réel	partout
$\by$	le vecteur $[y_1,\dots,y_N]\T$ de toutes les cibles	$\R^N$	§3 →
$\mathcal D$	le jeu de données $\{(\bx_n,y_n)\}_{n=1}^N$	ensemble	§3, §4
$p(\bx,y)$	la vraie loi jointe (inconnue) qui génère les couples	densité	§1
$\varepsilon,\ \sigma^2$	bruit (ce que $\bx$ n'explique pas) ; sa variance	v.a. ; réel $>0$	§1, §4, §7
Modèle
$\phi_\ell,\ \bphi(\bx)$	$\ell$-ième fonction de base ; le vecteur de features $[\phi_1(\bx),\dots,\phi_L(\bx)]\T$	$\R^D\to\R$ ; $\R^L$	§2 →
$L$	nombre de fonctions de base = nombre de paramètres	entier	§2 →
$M$	degré du polynôme dans le HW1 et PRML : $L = M+1$ paramètres	entier	§5, HW1
$\bw$ (ou $\btheta$)	vecteur de poids $[w_1,\dots,w_L]\T$	$\R^L$	§2 →
$f(\bx) = \bw\T\bphi(\bx)$	la prédiction du modèle	réel	§2 →
$\bPhi$	design matrix : ligne $n$ = $\bphi(\bx_n)\T$, colonne $\ell$ = $\phi_\ell$ évaluée sur tous les points	$\R^{N\times L}$	§3 →
$\bphi_n$	raccourci pour $\bphi(\bx_n)$ (une ligne de $\bPhi$)	$\R^L$	§9
Critères et estimateurs
$E(f)$	vraie MSE $\E[(y-f(\bx))^2]$ (espérance sur $p(\bx,y)$)	réel	§1
$\EMSE(\bw)$	MSE empirique $\frac1N\\|\by-\bPhi\bw\\|^2$ (le chapeau = calculé sur les données)	$\R^L\to\R_+$	§3 →
$\bw_{\text{LS}},\ \bPhi^\dagger$	estimateur des moindres carrés ; pseudo-inverse de Moore–Penrose	$\R^L$ ; $\R^{L\times N}$	§3
$\mathcal L(\bw;\mathcal D)$	vraisemblance $p(\by\mid\bPhi,\bw)$ vue comme fonction de $\bw$	$\R^L\to\R_+$	§4
$\lambda$	force de la régularisation	réel $>0$	§6 →
$\\|\bw\\|^2,\ \\|\bw\\|_1$	$\sum_\ell w_\ell^2$ (ridge) ; $\sum_\ell\|w_\ell\|$ (lasso)	réels $\ge0$	§6, §8
$p(\bw),\ \bSigma$	prior sur les poids $\N(\mathbf 0,\bSigma)$ ; sa matrice de covariance	densité ; $\R^{L\times L}$	§7
$\bw_{\text{MLE}},\ \bw_{\text{ridge}},\ \bw_{\text{MAP}}$	les estimateurs du chapitre ; MLE = LS, MAP = ridge	$\R^L$	§4, §6, §7
Optimisation (§9, notations des slides 31–46)
$\ell(y,\hat y)$, $\ell_i$	perte d'un exemple ; perte de l'exemple $i$	réel $\ge0$	§9
$L(\btheta),\ \hL(\btheta)$	risque attendu (espérance) ; risque empirique (moyenne sur les données)	réels	§9
$\nabla\hL$	gradient : vecteur colonne des dérivées partielles	vecteur	§9
$\btheta_t,\ \gamma_t,\ \bg_t$	itéré n° $t$ ; pas (learning rate) ; gradient utilisé au pas $t$	vecteur, réel, vecteur	§9
$\alpha,\ \Delta\btheta_i$	coefficient de momentum ; dernier déplacement $\btheta_i-\btheta_{i-1}$	$[0,1]$ ; vecteur	§9
$\mathcal B_t,\ \hL_{\mathcal B}$	mini-batch (indices tirés) ; risque empirique sur ce mini-batch	ensemble ; réel	§9 (SGD)

Pièges de notation (ils viennent des slides)

$\bw$ et $\btheta$ désignent la même chose : les slides écrivent $\btheta$ p.5, p.7 et dans toute la partie optimisation (p.31–46), $\bw$ ailleurs.
Beaucoup de « L » : $L$ = nombre de fonctions de base ; $L(\btheta)$ = risque attendu ; $\hL(\btheta)$ = risque empirique ; $\mathcal L(\bw;\mathcal D)$ = vraisemblance ; $\ell$ = perte d'un exemple. Et sur la slide 10, les étiquettes « $L = 0, 1, 3, 9$ » des figures désignent en fait le degré (comme $M$ dans PRML et le HW1).
Trois dimensions : $d$ (slide 7, entrées brutes, matrice $X\in\R^{N\times d}$), $D$ (dimension de $\bx$), $L$ (nombre de features, matrice $\bPhi\in\R^{N\times L}$). Et $\mathcal D$ est le jeu de données, pas une dimension.
$\sigma$ : écart-type du bruit (§4) ; mais aussi la largeur des bases gaussiennes (slide 11). Au chapitre 2, $\sigma$ sera la sigmoïde.
$E$ et $\E$ : $E(f)$ est la vraie MSE, $\EMSE$ sa version empirique, $\E[\cdot]$ l'opérateur d'espérance.
$\bSigma$ (§7) est une matrice de covariance, pas une somme.
Facteur $\frac1N$ et valeur de $\lambda$ : les slides minimisent $\frac1N\|\by-\bPhi\bw\|^2 + \lambda\|\bw\|^2$, d'où le $N\lambda\bI$ dans la formule du ridge ; PRML minimise $\frac12\sum_n(\cdot)^2 + \frac\lambda2\|\bw\|^2$, d'où $\lambda\bI$. Même famille de solutions, mais pas la même valeur de $\lambda$.
Indices : $n$ pour les exemples (p.12–17), $i$ dans la partie optimisation (p.31+), $t$ pour les itérations.

Mode d'emploi des scènes

3D : glisser = tourner · molette = zoom · clic droit (ou Maj + glisser) = déplacer.
2D : les points à halo sont déplaçables à la souris ; certaines scènes acceptent un clic pour ajouter un point (indiqué en bas à droite).
Preuves : clique sur « Preuve » pour la déplier, puis « Mode pas à pas » pour révéler une étape à la fois.
◉ Affichage (en haut à droite de chaque figure) : cases à cocher pour masquer / afficher la grille, les axes, les étiquettes et, selon la scène, ses éléments propres.

1Le problème de régression

Slides p.3–5 PRML §1.5.5 p.46 HW1 Q2.(1)

Où on en est

Acquis

Les probabilités du HW0 : espérance, espérance conditionnelle, variance.

Il manque

Que veut dire « bien prédire » un nombre réel $y$ à partir de $\bx$ ? Que faut-il minimiser ?

Cette partie

On fixe le critère (la MSE) et on trouve le meilleur prédicteur possible : $\E[y\mid\bx]$. Problème : il dépend de la loi $p(\bx,y)$, inconnue. Il faudra l'approcher avec des exemples et une famille de fonctions.

Définition — Régression

La régression modélise la relation entre une entrée $x$ (covariate, variable indépendante) et une sortie réelle $y$ (target, response) : $$y = f(x) + \varepsilon,$$ où $\varepsilon$ est un bruit (facteurs non observés) qui suit une certaine distribution. C'est $\varepsilon$ qui rend $y$ aléatoire sachant $x$.

On cherche le « meilleur » $f$. Le critère du cours est l'erreur quadratique moyenne (mean squared error) sous la vraie loi jointe $p(x,y)$ :

$$E(f) = \E\big[(y - f(x))^2\big] = \iint (y - f(x))^2\, p(x,y)\,dx\,dy.$$

Les objets en jeu

$x$: élément de $\mathcal X$ (souvent $\R^D$)L'entrée (input, covariate) : ce qu'on observe. Ex. slide 3 : $x = (\text{taille}, \text{poids})\in\R^2$.
$y$: réel $\in\R$ (ou $\R^K$)La sortie (target, response) qu'on veut prédire. Ex. la durée de vie.
$X,\ Y$: variables aléatoiresLes versions aléatoires de $x$ et $y$ : $(X,Y)$ est le couple « tiré par la nature », $(x,y)$ une valeur particulière. On écrit $\E[Y\mid X]$ pour insister sur l'aléa.
$p(x,y)$: densité sur $\mathcal X\times\R$La vraie loi jointe (data-generating distribution) : la loi de probabilité inconnue selon laquelle le monde produit des couples $(x,y)$. C'est une densité : $p(x,y)\ge0$ et $\iint p(x,y)\,dx\,dy = 1$ ; la probabilité qu'un couple tombe dans une région $A$ est $\iint_A p$. « Vraie » s'oppose à « notre modèle » : $p$ décrit la réalité, on ne la connaît jamais, on n'en voit que des échantillons (le jeu de données). Dans la scène ci-dessous, le relief 3D est $p(x,y)$.
$p(x)$: densité sur $\mathcal X$La loi marginale des entrées : $p(x) = \int p(x,y)\,dy$. Dit « quelles entrées on rencontre et à quelle fréquence » (ex. la répartition des tailles/poids dans la population). Dans la scène : uniforme sur $[0,1]$.
$p(y\mid x)$: densité sur $\R$, pour chaque $x$La loi conditionnelle : $p(y\mid x) = p(x,y)/p(x)$. Parmi toutes les personnes de mêmes $x$, comment se répartissent les $y$. Factorisation : $p(x,y) = p(x)\,p(y\mid x)$ ⇔ « la nature tire d'abord $x\sim p(x)$, puis $y\sim p(y\mid x)$ ». Géométriquement : la coupe verticale du relief en $x$, renormalisée.
$\varepsilon$: variable aléatoire réelleLe bruit : tout ce que $x$ n'explique pas (facteurs non observés, erreurs de mesure). Si $f(x) = \E[y|x]$, alors $\varepsilon = y - \E[y|x]$ vérifie $\E[\varepsilon\mid x] = 0$ par construction.
$f$: fonction $\mathcal X\to\R$Le prédicteur : à chaque entrée il associe une prédiction $f(x)$. C'est l'inconnue du problème ; on la cherche dans une classe (linéaires, réseaux…).
$\E[\,\cdot\,]$: opérateur : v.a. → nombreL'espérance = moyenne pondérée par la loi : $\E[g(X,Y)] = \iint g(x,y)\,p(x,y)\,dx\,dy$. Intuition : la moyenne de $g$ sur une infinité de nouveaux exemples tirés de $p$.
$E(f)$: nombre $\ge 0$ (une fonctionnelle de $f$)La MSE vraie (ou risque) de $f$ : erreur quadratique moyenne sur toute la population, y compris les exemples futurs jamais vus. C'est ce qu'on veut petit, mais on ne peut pas la calculer puisque $p$ est inconnue → on l'approche par une moyenne sur les données (§3).
$\E[y\mid x]$: fonction $\mathcal X\to\R$L'espérance conditionnelle : $\E[y\mid x] = \int y\,p(y\mid x)\,dy$, le centre de gravité de la coupe en $x$. Vue comme fonction de $x$, c'est la « fonction de régression » (courbe jaune).
$\Var(Y\mid X)$: fonction $\mathcal X\to\R_+$La variance conditionnelle $\E[(Y-\E[Y|X])^2\mid X]$ : la largeur de la coupe en $x$. Si elle est constante (= $\sigma^2$), le bruit est dit homoscédastique.

Théorème — l'estimateur MMSE est l'espérance conditionnelle

$$f^*_{\text{MSE}} = \argmin_f E(f) \quad\text{vérifie}\quad f^*_{\text{MSE}}(x) = \E[y \mid x].$$ Plus précisément, pour tout $f$ on a la décomposition $$\underbrace{\E\big[(Y-f(X))^2\big]}_{\text{MSE de } f} = \underbrace{\E\big[\Var(Y\mid X)\big]}_{\text{bruit irréductible}} + \underbrace{\E\big[(\E[Y\mid X]-f(X))^2\big]}_{\text{écart à la régression idéale}\ \ge 0}.$$

Géométrie. Imagine la densité jointe $p(x,y)$ comme un relief au-dessus du plan $(x,y)$. Couper ce relief par le plan vertical « $x = x_0$ » donne (à normalisation près) la densité conditionnelle $p(y\mid x_0)$ : une bosse. Pour chaque $x_0$ il faut choisir un seul nombre $f(x_0)$ ; le nombre qui minimise l'écart quadratique moyen à une bosse est son centre de gravité $\E[y\mid x_0]$. La courbe jaune (le « crête » moyenne du relief) est donc la meilleure fonction possible, et même elle garde une erreur : la largeur des bosses, $\Var(Y\mid X)$.

Preuve — décomposition de la MSE et optimalité de $\E[Y\mid X]$ HW1 Q2.(1)

Notons $m(X) := \E[Y\mid X]$. On ajoute et retranche $m(X)$ dans le carré : $$ (Y-f(X))^2 = \big(Y - m(X)\big)^2 + 2\big(Y-m(X)\big)\big(m(X)-f(X)\big) + \big(m(X)-f(X)\big)^2.$$

On prend l'espérance du terme croisé en conditionnant d'abord par $X$ (loi des espérances totales, tower property) : $m(X)-f(X)$ est une fonction de $X$ seulement, donc « sort » de l'espérance conditionnelle : $$\E\big[(Y-m(X))(m(X)-f(X))\big] = \E\Big[(m(X)-f(X))\ \underbrace{\E\big[Y - m(X)\mid X\big]}_{= m(X)-m(X) = 0}\Big] = 0.$$

Pour le premier terme, toujours par conditionnement : $\E\big[(Y-m(X))^2\big] = \E\big[\E[(Y-\E[Y|X])^2\mid X]\big] = \E\big[\Var(Y\mid X)\big]$.

D'où $\E[(Y-f(X))^2] = \E[\Var(Y\mid X)] + \E[(m(X)-f(X))^2]$. Le premier terme ne dépend pas de $f$ ; le second est $\ge 0$ et vaut $0$ ssi $f(X) = m(X)$ presque sûrement. Donc $f^* = m = \E[Y\mid X]$ minimise la MSE, et la MSE minimale vaut $\E[\Var(Y\mid X)]$.

Version « point par point » (sans espérances totales) : pour $x$ fixé, $g(c) = \E[(Y-c)^2\mid x] = c^2 - 2c\,\E[Y|x] + \E[Y^2|x]$ est une parabole en $c$, minimale en $c = \E[Y\mid x]$ ($g'(c) = 2c - 2\E[Y|x] = 0$). On minimise l'intégrande pour chaque $x$, donc l'intégrale.

∎

Question des slides — « Why? » (p.4)

Pourquoi le meilleur $f$ est-il $\E[y\mid x]$ ? → Parce que pour chaque $x$, la constante qui minimise l'écart quadratique moyen à une variable aléatoire est sa moyenne (parabole en $c$). La régression, c'est donc de l'approximation de fonction de $\E[y\mid x]$ dans une classe choisie (linéaire, réseaux de neurones…), cf. slide 5.

2Modèles linéaires et fonctions de base

Slides p.7–11 PRML §3.1 p.138–140 DL §4.1.1 p.111

Où on en est

Acquis

La cible idéale $\E[y\mid\bx]$, mais elle est inconnue.

Il manque

Une famille de fonctions où chercher : assez riche pour suivre des courbes, assez simple pour s'ajuster facilement.

Cette partie

Les modèles linéaires à fonctions de base, $f(\bx) = \bw\T\bphi(\bx)$ : non linéaires en $\bx$, mais linéaires en $\bw$. C'est cette linéarité qui donnera une formule close au §3.

Hypothèse de base : $y = \theta\T x$ avec $x\in\R^d$. Sur un jeu de données, en empilant les $x_n\T$ en lignes d'une matrice $X\in\R^{N\times d}$ : $\ \mathbf y = X\theta$.

« Linéaire » paraît trop pauvre (slide 7 : « Are linear models too simple? »). Le tour de passe-passe : on applique d'abord une transformation fixe $\phi$ à l'entrée.

Définition — Régression linéaire à fonctions de base

$$f(x) = \sum_{\ell=1}^{L} w_\ell\,\phi_\ell(x) = \bw\T\bphi(x),\qquad \bphi(x) = \big[\phi_1(x),\dots,\phi_L(x)\big]\T.$$ $f$ peut être non linéaire en $x$ mais reste linéaire en $\bw$. C'est la linéarité en $\bw$ qui donne une solution en forme close.

Les objets en jeu

$x\in\R^D$: vecteur (entrée brute)L'entrée à $D$ composantes (ex. $D=1$ dans le HW1).
$\theta\in\R^d,\ X\in\R^{N\times d}$: vecteur, matriceSlide 7 : modèle linéaire « brut » $y = \theta\T x$ ; $X$ empile les $N$ entrées en lignes, $\by = X\theta$.
$\phi_\ell:\R^D\to\R$: fonction fixe (choisie à la main)La $\ell$-ième fonction de base (basis function, feature) : elle extrait une caractéristique numérique de $x$ (une puissance, une bosse autour de $\mu_\ell$, une fréquence…). Elle n'est pas apprise.
$\bphi(x)\in\R^L$: vecteur de featuresL'empilement $[\phi_1(x),\dots,\phi_L(x)]\T$ : la représentation de $x$ dans « l'espace des features ». $\bphi$ envoie $\R^D$ dans $\R^L$ (souvent $L\gg D$).
$L$: entierNombre de fonctions de base = nombre de paramètres. Polynôme de degré $M$ : $L = M+1$ (avec la constante $\phi_1 = 1$).
$\bw\in\R^L$: vecteur de paramètres (appris)Les poids. $w_\ell$ dit combien de $\phi_\ell$ on met dans le mélange. $f(x) = \bw\T\bphi(x)$ est le produit scalaire entre les poids et les features.
$\mu_\ell,\ \sigma$: réels (hyperparamètres)Pour la base gaussienne : centre et largeur de la $\ell$-ième bosse. Fixés avant l'apprentissage.

Exemples (slide 11) : polynomiale $\phi_\ell(x) = x^{\ell-1}$ ; gaussienne $\phi_\ell(x) = \exp\!\big(-\frac{\|x-\mu_\ell\|^2}{2\sigma^2}\big)$ ; sigmoïdale ; Fourier ; splines ; ondelettes. Dans la scène ci-dessous, chaque courbe fine colorée est un terme $w_\ell\phi_\ell(x)$ et la courbe jaune est leur somme. Bouge les poids : une base locale (gaussiennes) ne modifie la courbe que près de $\mu_\ell$ ; une base globale (polynômes, Fourier) la modifie partout.

Le « relèvement » : une droite dans l'espace des features

Intuition géométrique clé. Avec $\bphi(x) = [1, x, x^2]\T$, chaque point $x$ est envoyé sur la parabole $(x, x^2)$ du plan des features. Un modèle $f(x) = w_0 + w_1 x + w_2 x^2$ est un plan $y = w_0 + w_1 u + w_2 v$ au-dessus de ce plan $(u,v)$. La courbe apprise dans l'espace d'origine est simplement l'intersection de ce plan avec le « mur » vertical posé sur la parabole. Ajuster une parabole aux données = ajuster un plan à des points en 3D : c'est un problème linéaire.

À retenir

Même idée plus tard : régression logistique avec features, puis le kernel trick des SVM (on relève les données dans un espace où une séparation linéaire suffit, sans jamais calculer $\bphi$).

3Moindres carrés (least squares)

Slides p.12–14 PRML §3.1.1 p.140–142 HW1 Q2.(2)(3)

Où on en est

Acquis

Le modèle $f(\bx) = \bw\T\bphi(\bx)$, avec $L$ poids inconnus.

Il manque

Une façon de choisir $\bw$ à partir des $N$ exemples (la vraie MSE est incalculable : $p(\bx,y)$ est inconnue).

Cette partie

On minimise la MSE empirique : équations normales, formule $\bw_{\text{LS}}$, interprétation comme une projection, et ce qui se passe quand $\bPhi\T\bPhi$ n'est pas inversible (pseudo-inverse).

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

StatQuestThe Main Ideas of Fitting a Line to Data (Least Squares and Linear Regression)Les moindres carrés en images : résidus, somme des carrés, pente et ordonnée optimales.▶

Stanford CS229 — Andrew NgLecture 2: Linear Regression and Gradient DescentCours complet : fonction de coût, gradient, équations normales — même niveau que les slides.

Objectif d'apprentissage — MSE empirique

Étant donné $\mathcal D = \{(x_n, y_n)\}_{n=1}^N$, on minimise $$\EMSE(\bw) = \frac1N\sum_{n=1}^N\big(y_n - \bw\T\bphi(x_n)\big)^2 = \frac1N\|\by - \bPhi\bw\|^2,\qquad \bPhi = \begin{bmatrix}\phi_1(x_1) & \cdots & \phi_L(x_1)\\ \vdots & & \vdots\\ \phi_1(x_N) & \cdots & \phi_L(x_N)\end{bmatrix}\in\R^{N\times L}.$$ La ligne $n$ de la design matrix $\bPhi$ est $\bphi(x_n)\T$ ; la colonne $\ell$ est la feature $\phi_\ell$ évaluée sur tous les points.

Les objets en jeu

$\mathcal D$: ensemble de $N$ couplesLe jeu d'entraînement $\{(x_n,y_n)\}_{n=1}^N$, supposé tiré i.i.d. (indépendamment, de même loi) selon la vraie loi $p(x,y)$ : ce sont les seuls morceaux de $p$ qu'on voit.
$N$: entierNombre d'exemples (HW1 : $N=15$).
$\by\in\R^N$: vecteur colonneToutes les cibles empilées : $\by = [y_1,\dots,y_N]\T$. Vu géométriquement (§3.2) : un seul point de $\R^N$.
$\bphi_n := \bphi(x_n)\in\R^L$: vecteurLes features du $n$-ième exemple = la $n$-ième ligne de $\bPhi$ (transposée).
$\bPhi\in\R^{N\times L}$: matrice (design matrix)$\Phi_{n\ell} = \phi_\ell(x_n)$. Ligne $n$ = un exemple ; colonne $\ell$ = une feature sur tous les exemples. $\bPhi\bw\in\R^N$ = vecteur de toutes les prédictions.
$\EMSE(\bw)$: fonction $\R^L\to\R_+$La MSE empirique : la MSE vraie $E(f)$ où l'on remplace l'espérance sous $p$ par la moyenne sur les $N$ exemples. Par la loi des grands nombres, pour $\bw$ fixé, $\EMSE(\bw)\to E(f_{\bw})$ quand $N\to\infty$.
$\|\mathbf v\|^2$: nombreNorme euclidienne au carré : $\|\mathbf v\|^2 = \mathbf v\T\mathbf v = \sum_n v_n^2$. Ici $\|\by-\bPhi\bw\|^2 = \sum_n r_n^2$, la somme des carrés des résidus $r_n = y_n - \bw\T\bphi_n$.
$\bw_{\text{LS}}$: vecteur de $\R^L$Le minimiseur de $\EMSE$ : l'estimateur des moindres carrés (least squares).
$\bPhi^\dagger\in\R^{L\times N}$: matriceLa pseudo-inverse de Moore–Penrose. Si $\bPhi\T\bPhi$ est inversible, $\bPhi^\dagger = (\bPhi\T\bPhi)^{-1}\bPhi\T$ ; sinon elle donne la solution de norme minimale.

Pourquoi « moindres carrés » ? Littéralement : chaque résidu $r_n = y_n - f(x_n)$ est le côté d'un carré d'aire $r_n^2$. La MSE empirique est l'aire moyenne de ces carrés. Déplace la droite (poignées) ou les points ; à droite, la même MSE vue comme une surface dans l'espace des paramètres $(w_1, w_2)$ : un paraboloïde (bol) dont le fond est $\bw_{\text{LS}}$.

Théorème — Estimateur des moindres carrés (Least-Squares Estimator)

La condition de stationnarité $\nabla_{\bw}\EMSE(\bw) = \frac2N\bPhi\T(\bPhi\bw - \by) = 0$ donne les équations normales $$\bPhi\T\bPhi\,\bw = \bPhi\T\by \qquad\Longrightarrow\qquad \bw_{\text{LS}} = (\bPhi\T\bPhi)^{-1}\bPhi\T\by = \bPhi^\dagger\by\quad\text{si } \bPhi\T\bPhi \text{ est inversible.}$$ Sinon, la pseudo-inverse de Moore–Penrose $\bPhi^\dagger$ existe toujours (ou on utilise la descente de gradient). We have a closed-form solution!

Preuve — gradient, équations normales et minimum global HW1 Q2.(2)(3)

Développons : $\|\by-\bPhi\bw\|^2 = (\by-\bPhi\bw)\T(\by-\bPhi\bw) = \by\T\by - 2\bw\T\bPhi\T\by + \bw\T\bPhi\T\bPhi\bw$.

On a utilisé $\by\T\bPhi\bw = (\by\T\bPhi\bw)\T = \bw\T\bPhi\T\by$ (un scalaire est égal à sa transposée).

Règles de calcul matriciel : $\nabla_{\bw}(\bw\T\bb) = \bb$ et $\nabla_{\bw}(\bw\T\bA\bw) = (\bA+\bA\T)\bw = 2\bA\bw$ si $\bA$ symétrique. Avec $\bA = \bPhi\T\bPhi$ (symétrique) et $\bb = \bPhi\T\by$ : $$\nabla_{\bw}\EMSE(\bw) = \frac1N\big(-2\bPhi\T\by + 2\bPhi\T\bPhi\bw\big) = \frac2N\bPhi\T(\bPhi\bw-\by).$$

Vérification composante par composante : $\partial_{w_k}\frac1N\sum_n(\bw\T\bphi_n - y_n)^2 = \frac2N\sum_n(\bw\T\bphi_n-y_n)\phi_k(x_n)$, c'est bien la $k$-ième composante de $\frac2N\bPhi\T(\bPhi\bw-\by)$.

Stationnarité : $\nabla = 0 \iff \bPhi\T\bPhi\bw = \bPhi\T\by$ (équations normales). Si $\bPhi\T\bPhi$ est inversible, $\bw_{\text{LS}} = (\bPhi\T\bPhi)^{-1}\bPhi\T\by$.

C'est bien un minimum global. La hessienne vaut $\nabla^2\EMSE = \frac2N\bPhi\T\bPhi$, et pour tout $\bv$ : $\bv\T\bPhi\T\bPhi\bv = \|\bPhi\bv\|^2 \ge 0$. La hessienne est semi-définie positive partout ⇒ fonction convexe ⇒ tout point stationnaire est un minimum global. Si $\bPhi$ est de rang plein en colonnes ($\bPhi\bv = 0 \Rightarrow \bv = 0$), elle est définie positive ⇒ minimum unique.

Quand $\bPhi\T\bPhi$ est-il inversible ? $\bPhi\T\bPhi$ est inversible $\iff$ $\operatorname{rang}(\bPhi) = L$ $\iff$ colonnes linéairement indépendantes. Nécessite $N \ge L$ : avec moins de points que de paramètres (ex. $M = 10$ et $N = 5$), il y a une infinité de solutions qui interpolent parfaitement les données.

∎

Géométrie des moindres carrés : une projection orthogonale

PRML §3.1.2 p.143 (Fig. 3.2) Hors slides

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

MIT OCW — Gilbert Strang15. Projections onto SubspacesProjection d'un vecteur sur un sous-espace : l'origine de $\bP = \bPhi(\bPhi\T\bPhi)^{-1}\bPhi\T$.▶

MIT OCW — Gilbert Strang16. Projection Matrices and Least SquaresStrang relie projection et moindres carrés : exactement la vue « un seul vecteur $\by\in\R^N$ ».

Changeons de point de vue : au lieu de voir $N$ points dans le plan $(x,y)$, voyons un seul vecteur $\by\in\R^N$. Chaque choix de $\bw$ produit un vecteur de prédictions $\bPhi\bw = w_1\boldsymbol\varphi_1 + \dots + w_L\boldsymbol\varphi_L$ : une combinaison des colonnes de $\bPhi$. L'ensemble de toutes les prédictions possibles est le sous-espace $\mathcal S = \operatorname{col}(\bPhi)$ (dimension $\le L$). Minimiser $\|\by - \bPhi\bw\|$, c'est trouver le point de $\mathcal S$ le plus proche de $\by$ : la projection orthogonale. Avec $N = 3$ points et $L = 2$ features, on peut le voir en 3D.

Principe d'orthogonalité

$\hby = \bPhi\bw_{\text{LS}}$ est la projection orthogonale de $\by$ sur $\operatorname{col}(\bPhi)$ : le résidu $\by - \hby$ est orthogonal à chaque colonne de $\bPhi$, $$\bPhi\T(\by - \bPhi\bw_{\text{LS}}) = 0 \quad\text{— ce sont exactement les équations normales.}$$ La matrice de projection (« hat matrix ») est $\bP = \bPhi(\bPhi\T\bPhi)^{-1}\bPhi\T$, avec $\bP^2 = \bP$ et $\bP\T = \bP$.

Preuve — pourquoi le point le plus proche est la projection orthogonale

Soit $\hby\in\mathcal S$ tel que $\by-\hby \perp \mathcal S$. Pour tout autre $\mathbf z\in\mathcal S$, $\hby-\mathbf z\in\mathcal S$ donc $(\by-\hby)\perp(\hby-\mathbf z)$.

« $\by-\bPhi\bw\perp\mathcal S$ » $\iff$ $\boldsymbol\varphi_\ell\T(\by-\bPhi\bw) = 0$ pour chaque colonne $\ell$ $\iff$ $\bPhi\T(\by-\bPhi\bw) = 0$ : on retrouve les équations normales, sans aucun calcul de dérivée.

$\bP^2 = \bPhi(\bPhi\T\bPhi)^{-1}\underbrace{\bPhi\T\bPhi(\bPhi\T\bPhi)^{-1}}_{\bI}\bPhi\T = \bP$ : projeter deux fois = projeter une fois. $\bP\T = \bP$ car $(\bPhi\T\bPhi)^{-1}$ est symétrique.

∎

Pseudo-inverse et cas dégénéré Hors slides HW1 Q2.(3)

Slides p.14 (« Moore–Penrose pseudoinverse Φ† still exists »)PRML éq. 3.17 p.142

La question à laquelle on répond

Le HW1 demande : « Explain the role of $\bPhi^\dagger\by$ when $\bPhi\T\bPhi$ is singular. » La formule $\hat\bw_{\text{LS}} = (\bPhi\T\bPhi)^{-1}\bPhi\T\by$ suppose qu'on peut inverser $\bPhi\T\bPhi$. Que se passe-t-il quand on ne peut pas ? Il faut comprendre, dans l'ordre : (1) quand ça arrive, (2) ce qui reste vrai, (3) ce qui casse, (4) comment on choisit quand même une solution — c'est le rôle de $\bPhi^\dagger\by$ —, (5) pourquoi c'est aussi utile quand la matrice est presque singulière.

Les objets en jeu

$\operatorname{rang}(\bPhi)$: entier $\le\min(N,L)$Le nombre de colonnes linéairement indépendantes de $\bPhi$ = la dimension de $\operatorname{col}(\bPhi)$. $\bPhi\T\bPhi$ ($L\times L$) est inversible ssi $\operatorname{rang}(\bPhi) = L$ (« rang plein en colonnes »).
$\operatorname{col}(\bPhi)\subseteq\R^N$: sous-espaceL'espace colonne : tous les vecteurs de prédictions $\bPhi\bw$ possibles (le plan bleu de la scène de projection).
$\ker\bPhi\subseteq\R^L$: sous-espace (noyau)$\{\bv : \bPhi\bv = 0\}$ : les directions dans lesquelles on peut bouger les poids sans changer aucune prédiction. Réduit à $\{0\}$ ssi rang plein.
$\operatorname{row}(\bPhi) = \operatorname{col}(\bPhi\T)$: sous-espace de $\R^L$L'espace des lignes, orthogonal à $\ker\bPhi$. Tout $\bw$ se décompose en une partie « utile » dans $\operatorname{row}(\bPhi)$ et une partie « invisible » dans $\ker\bPhi$.
SVD $\bPhi = \mathbf U\boldsymbol\Sigma\mathbf V\T$: décomposition$\mathbf V$ ($L\times L$) et $\mathbf U$ ($N\times N$) orthogonales, $\boldsymbol\Sigma$ « diagonale » de valeurs singulières $\sigma_1\ge\dots\ge\sigma_r>0$ (puis des zéros). Géométriquement : $\bPhi$ = tourner ($\mathbf V\T$), étirer chaque axe de $\sigma_i$ ($\boldsymbol\Sigma$), tourner ($\mathbf U$). Les $\sigma_i^2$ sont les valeurs propres de $\bPhi\T\bPhi$.
$\bPhi^\dagger\in\R^{L\times N}$: matrice (pseudo-inverse de Moore–Penrose)$\bPhi^\dagger = \mathbf V\boldsymbol\Sigma^+\mathbf U\T$ où $\boldsymbol\Sigma^+$ remplace chaque $\sigma_i>0$ par $1/\sigma_i$ et laisse les zéros à zéro. Existe toujours, pour n'importe quelle matrice.

1. Quand $\bPhi\T\bPhi$ est-elle singulière ?

Exactement quand les colonnes de $\bPhi$ sont linéairement dépendantes, c'est-à-dire qu'une feature est une combinaison des autres. Trois situations typiques :

Plus de paramètres que de points : $L>N$ (ex. $M = 20$ avec $N = 15$ points). $L$ colonnes dans $\R^N$ ne peuvent pas être indépendantes si $L>N$.
Des entrées répétées : avec une base polynomiale, s'il n'y a que $k$ valeurs distinctes parmi les $x_n$, le rang est au plus $k$. Cas extrême de la scène : $x_1 = x_2 = x_3$ ⇒ les colonnes $\mathbf 1$ et $\mathbf x$ sont proportionnelles.
Des features redondantes : la même mesure deux fois (taille en cm et en mètres), ou une feature égale à la somme de deux autres.

Preuve — $\bPhi\T\bPhi$ inversible $\iff$ colonnes de $\bPhi$ indépendantes $\iff\ker\bPhi = \{0\}$

Si $\bPhi\bv = 0$ alors $\bPhi\T\bPhi\bv = 0$ : $\ker\bPhi\subseteq\ker\bPhi\T\bPhi$.

Réciproquement, si $\bPhi\T\bPhi\bv = 0$ alors $0 = \bv\T\bPhi\T\bPhi\bv = \|\bPhi\bv\|^2$, donc $\bPhi\bv = 0$. Ainsi $\ker\bPhi\T\bPhi = \ker\bPhi$.

Une matrice carrée est inversible ssi son noyau est $\{0\}$. Et $\ker\bPhi = \{0\}$ signifie « aucune combinaison non nulle des colonnes ne donne 0 » : colonnes indépendantes.

∎

2. Ce qui reste vrai : la meilleure prédiction $\hby$ existe et est unique

Géométriquement, les moindres carrés projettent $\by$ sur $\operatorname{col}(\bPhi)$. Une projection sur un sous-espace existe toujours et est unique, que les colonnes soient indépendantes ou non : si elles sont dépendantes, $\operatorname{col}(\bPhi)$ est juste plus petit (un plan qui s'écrase en droite dans la scène de la section 3). Donc le vecteur de prédictions optimal $\hby$ et l'erreur minimale sont parfaitement définis. De plus, les équations normales $\bPhi\T\bPhi\bw = \bPhi\T\by$ ont toujours au moins une solution.

3. Ce qui casse : une infinité de $\bw$ donnent ce même $\hby$

L'ensemble des solutions

Si $\hat\bw$ minimise $\EMSE$, alors les minimiseurs sont exactement $\ \{\hat\bw + \bv : \bv\in\ker\bPhi\}$ — une droite, un plan… de solutions (« vallée plate »), toutes avec les mêmes prédictions $\bPhi\hat\bw = \hby$ et la même erreur.

Preuve

Si $\bv\in\ker\bPhi$ : $\bPhi(\hat\bw + \bv) = \bPhi\hat\bw + \bPhi\bv = \bPhi\hat\bw$. Mêmes prédictions ⇒ même MSE ⇒ aussi un minimiseur.

Réciproquement, deux minimiseurs $\bw_1,\bw_2$ donnent la même projection : $\bPhi\bw_1 = \bPhi\bw_2 = \hby$ (unicité de la projection), donc $\bw_1 - \bw_2\in\ker\bPhi$.

∎

Image du bol : la MSE en fonction de $\bw$ est un bol dont la courbure dans la direction $\bv$ vaut $\propto\|\bPhi\bv\|^2$ (voir la hessienne $\frac2N\bPhi\T\bPhi$). Dans les directions de $\ker\bPhi$ cette courbure est nulle : le bol devient une gouttière dont le fond est une droite horizontale. Il n'y a plus un point le plus bas, mais toute une ligne. C'est exactement ce que montre la scène ci-dessous quand $\varepsilon = 0$.

4. Choisir quand même : la solution de norme minimale $\bPhi^\dagger\by$

Parmi toutes les solutions de la vallée, on en choisit une de façon canonique : la plus proche de l'origine (norme $\|\bw\|$ minimale). Géométriquement, c'est la projection orthogonale de l'origine sur la droite (ou le plan) des solutions. C'est exactement ce que calcule la pseudo-inverse.

Rôle de $\bPhi^\dagger\by$

$\bw^\dagger := \bPhi^\dagger\by$ est l'unique minimiseur de $\EMSE$ de norme minimale. C'est aussi l'unique minimiseur situé dans $\operatorname{row}(\bPhi)$ (sans composante « invisible » dans $\ker\bPhi$). Ses prédictions sont $\bPhi\bw^\dagger = \hby$ (la projection). Si $\bPhi\T\bPhi$ est inversible, $\bPhi^\dagger = (\bPhi\T\bPhi)^{-1}\bPhi\T$ et on retrouve $\hat\bw_{\text{LS}}$.

Preuve — par la SVD, en changeant de coordonnées

Idée : dans la bonne base, $\bPhi$ devient diagonale et le problème se découple coordonnée par coordonnée. Écrivons $\bPhi = \mathbf U\boldsymbol\Sigma\mathbf V\T$ et posons $\bz = \mathbf V\T\bw$ (coordonnées de $\bw$ dans la base des $\bv_i$) et $\mathbf c = \mathbf U\T\by$ (coordonnées de $\by$ dans la base des $\bu_i$).

$\mathbf U$ est orthogonale, donc elle conserve les longueurs : $\|\by - \bPhi\bw\|^2 = \|\mathbf U\T\by - \boldsymbol\Sigma\mathbf V\T\bw\|^2 = \|\mathbf c - \boldsymbol\Sigma\bz\|^2 = \sum_{i=1}^r(c_i - \sigma_iz_i)^2 + \sum_{i>r}c_i^2$, où $r$ est le rang.

Pour $i\le r$ ($\sigma_i>0$) : le terme est minimal pour $z_i = c_i/\sigma_i$. Pour $i>r$ ($\sigma_i = 0$) : $z_i$ n'apparaît pas dans l'erreur — n'importe quelle valeur convient. Ce sont exactement les directions de $\ker\bPhi$ : la vallée plate. Le dernier terme $\sum_{i>r}c_i^2$ est l'erreur minimale, que rien ne peut réduire (la partie de $\by$ hors de $\operatorname{col}(\bPhi)$).

$\mathbf V$ est orthogonale donc $\|\bw\| = \|\bz\|$. Pour minimiser la norme parmi les solutions, on prend $z_i = 0$ pour les coordonnées libres. D'où $\bz^\dagger = \boldsymbol\Sigma^+\mathbf c$ et $\bw^\dagger = \mathbf V\bz^\dagger = \mathbf V\boldsymbol\Sigma^+\mathbf U\T\by = \bPhi^\dagger\by$, soit $\ \bw^\dagger = \sum_{i=1}^r\frac{\bu_i\T\by}{\sigma_i}\,\bv_i$.

Unicité : tout autre minimiseur a au moins un $z_i\ne0$ pour $i>r$, donc une norme strictement plus grande. Et $\bw^\dagger$ ne contient que des $\bv_i$ avec $\sigma_i>0$, qui engendrent $\operatorname{row}(\bPhi)$.

Rang plein ($r = L$) : aucune coordonnée libre, et $\mathbf V\boldsymbol\Sigma^+\mathbf U\T = (\bPhi\T\bPhi)^{-1}\bPhi\T$ (vérification : $(\bPhi\T\bPhi)^{-1}\bPhi\T = (\mathbf V\boldsymbol\Sigma^2\mathbf V\T)^{-1}\mathbf V\boldsymbol\Sigma\mathbf U\T = \mathbf V\boldsymbol\Sigma^{-2}\boldsymbol\Sigma\mathbf U\T$).

∎

5. Deux autres façons d'arriver à $\bPhi^\dagger\by$

Limite du ridge. $\bPhi^\dagger\by = \lim_{\lambda\to0^+}(\bPhi\T\bPhi + \lambda\bI)^{-1}\bPhi\T\by$. En base SVD, le ridge donne $z_i = \frac{\sigma_i}{\sigma_i^2+\lambda}c_i$ : pour $\sigma_i>0$ cela tend vers $c_i/\sigma_i$, et pour $\sigma_i = 0$ cela vaut exactement 0 pour tout $\lambda>0$. Le ridge avec un $\lambda$ infinitésimal choisit donc la solution de norme minimale (dans la scène : la courbe blanche du chemin ridge arrive sur le point jaune).
Descente de gradient depuis $\bw_0 = 0$. Le gradient $\frac2N\bPhi\T(\bPhi\bw-\by)$ est toujours dans $\operatorname{row}(\bPhi)$ : GD partant de 0 ne bouge jamais dans les directions de $\ker\bPhi$ et converge vers $\bw^\dagger$. (C'est pour cela que le HW impose $\bw_0 = 0$ en Q4.(2) : sinon, dans le cas dégénéré, GD pourrait converger vers une autre solution de la vallée.)

6. Le cas « presque singulier » : pourquoi c'est important pour $M = 10$

Avec $N = 15$ valeurs $x_n$ distinctes et $M\le10$, $\bPhi\T\bPhi$ est inversible en théorie. Mais les colonnes $x^0,\dots,x^{10}$ sur $[0,1]$ se ressemblent énormément : la plus petite valeur singulière est minuscule (conditionnement $\sim10^{15}$ dans le HW). Dans $\bw = \sum_i\frac{\bu_i\T\by}{\sigma_i}\bv_i$, diviser par un $\sigma_i\approx0$ amplifie énormément le bruit contenu dans $\bu_i\T\by$ : des coefficients gigantesques qui se compensent, instables d'un tirage à l'autre — c'est le sur-apprentissage vu du côté de l'algèbre. Remèdes :

pseudo-inverse tronquée : traiter comme nulles les $\sigma_i<\text{tol}\cdot\sigma_1$ (c'est le paramètre rcond de np.linalg.pinv) ⇒ on retombe sur une solution de norme raisonnable ;
ridge : remplacer $\frac1{\sigma_i}$ par $\frac{\sigma_i}{\sigma_i^2+\lambda}$, qui reste borné ;
numériquement, résoudre par QR/SVD plutôt qu'en inversant $\bPhi\T\bPhi$ (qui élève au carré le conditionnement).

Dans la scène : diminue $\varepsilon$ (les $x_n$ se rapprochent) — la solution exacte $\hat\bw_{\text{LS}}$ (rouge) part à l'infini le long de la vallée, alors que $\bPhi^\dagger$ tronquée (jaune) reste sage.

7. Exemple entièrement à la main

Trois points avec la même entrée : $x_1 = x_2 = x_3 = 1$, $\by = (1,2,3)$, modèle $f(x) = w_0 + w_1x$. Donc $\bPhi = \begin{bmatrix}1&1\\1&1\\1&1\end{bmatrix}$.

Calcul complet

$\bPhi\T\bPhi = \begin{bmatrix}3&3\\3&3\end{bmatrix}$, de déterminant $0$ : singulière. $\bPhi\T\by = (6, 6)$.

Équations normales : $3w_0 + 3w_1 = 6$ (deux fois la même) ⇔ $w_0 + w_1 = 2$ : une droite de solutions. Chacune prédit $f(1) = w_0 + w_1 = 2$ = la moyenne des $y$ — normal : avec une seule valeur de $x$, on ne peut rien dire de la pente, seulement de la valeur en $x = 1$.

$\ker\bPhi = \{t(1,-1)\}$ : augmenter $w_0$ de $t$ et baisser $w_1$ de $t$ ne change aucune prédiction.

Solution de norme minimale : le point de la droite $w_0+w_1 = 2$ le plus proche de l'origine est $(1,1)$ (projection orthogonale de 0 ; la droite a pour normale $(1,1)$). Donc $\bw^\dagger = (1,1)$, de norme $\sqrt2$.

Vérification SVD : $\bPhi$ est de rang 1, $\bPhi = \sigma\,\bu\bv\T$ avec $\bu = \frac1{\sqrt3}(1,1,1)$, $\bv = \frac1{\sqrt2}(1,1)$, $\sigma = \sqrt6$. $\bPhi^\dagger\by = \frac{\bu\T\by}{\sigma}\bv = \frac{6/\sqrt3}{\sqrt6}\cdot\frac{(1,1)}{\sqrt2} = (1,1)$ ✓.

∎

Réponse type pour HW1 Q2.(3) (deuxième partie)

Si $\bPhi\T\bPhi$ est singulière ($\operatorname{rang}\bPhiinfinité de solutions $\hat\bw + \ker\bPhi$, qui donnent toutes la même prédiction $\hby$ (projection de $\by$ sur $\operatorname{col}\bPhi$) et la même erreur minimale. La pseudo-inverse de Moore–Penrose fournit alors $\bPhi^\dagger\by = \mathbf V\boldsymbol\Sigma^+\mathbf U\T\by$, l'unique solution de norme minimale (celle sans composante dans $\ker\bPhi$), qui coïncide avec $(\bPhi\T\bPhi)^{-1}\bPhi\T\by$ dans le cas inversible et est la limite du ridge quand $\lambda\to0^+$. Numériquement, pour $M = 10$ où $\bPhi\T\bPhi$ est presque singulière, on préfère la SVD/pseudo-inverse (éventuellement tronquée) à l'inversion explicite.

4Interprétation par maximum de vraisemblance

Slides p.15–18 PRML §3.1.1 p.140–142 HW1 Q3.(1)

Où on en est

Acquis

$\bw_{\text{LS}}$ minimise la MSE empirique, et on sait le calculer.

Il manque

Pourquoi la perte carrée plutôt qu'une autre ? Quelle hypothèse cache-t-elle ?

Cette partie

Avec un bruit gaussien, maximiser la vraisemblance des données redonne exactement $\bw_{\text{LS}}$. Choisir la perte carrée, c'est supposer un bruit gaussien.

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

StatQuestMaximum Likelihood, clearly explained!!!L'idée de vraisemblance, sans formule, avec des cloches qu'on déplace.▶

StatQuestMaximum Likelihood For the Normal Distribution, step-by-step!!!Le calcul complet du MLE gaussien, étape par étape (log, dérivée, annulation).

Modèle d'observation gaussien

$y_n = \bw\T\bphi(x_n) + \varepsilon_n$ avec $\varepsilon_n \overset{\text{iid}}{\sim}\N(0,\sigma^2)$, c.-à-d. $\ p(y_n\mid\bphi(x_n),\bw) = \N\big(y_n\mid\bw\T\bphi(x_n),\sigma^2\big)$.
Vraisemblance (likelihood) : la densité des données observées vue comme fonction de $\bw$, $$\mathcal L(\bw;\mathcal D) = p(\by\mid\bPhi,\bw) = \prod_{n=1}^N p(y_n\mid\bphi(x_n),\bw),\qquad \bw_{\text{MLE}} = \argmax_{\bw} \mathcal L = \argmax_{\bw} \ln\mathcal L.$$

Les objets en jeu

$\sigma^2$: réel $>0$La variance du bruit ($\sigma$ = écart-type). Supposée connue ou estimée ; elle fixe la largeur des cloches.
$\N(y\mid\mu,\sigma^2)$: densité sur $\R$La densité gaussienne $\frac1{\sqrt{2\pi\sigma^2}}\exp\!\big(-\frac{(y-\mu)^2}{2\sigma^2}\big)$, lue « densité de $y$ sous une normale de moyenne $\mu$ et variance $\sigma^2$ ». Ici $\mu = \bw\T\bphi(x_n)$ : la cloche est centrée sur la prédiction.
$p(y_n\mid\bphi(x_n),\bw)$: nombre $\ge0$Densité du modèle évaluée à la valeur observée $y_n$ : hauteur de la cloche au point observé.
$\mathcal L(\bw;\mathcal D)$: fonction $\R^L\to\R_+$La vraisemblance : la densité des données observées, vue comme fonction du paramètre $\bw$ (les données sont fixées). Attention : ce n'est pas une densité en $\bw$ (elle ne s'intègre pas à 1 en $\bw$).
$\ln\mathcal L$: fonction $\R^L\to\R$La log-vraisemblance : transforme le produit en somme, ne change pas l'argmax ($\ln$ strictement croissant), évite les sous-dépassements numériques.
$\bw_{\text{MLE}}$: vecteur de $\R^L$L'estimateur du maximum de vraisemblance : le $\bw$ qui rend les données observées les plus plausibles.

Image mentale. Au-dessus de chaque $x_n$, le modèle pose une cloche gaussienne centrée sur la prédiction $\bw\T\bphi(x_n)$. La contribution du point $n$ à la vraisemblance est la hauteur de sa cloche à l'endroit où tombe $y_n$ (bâtons verticaux dans la scène). La vraisemblance est le produit de ces hauteurs : elle est grande quand toutes les cloches « attrapent » leurs points près de leur sommet. Et comme la cloche gaussienne décroît en $e^{-r^2/2\sigma^2}$, maximiser le produit = minimiser $\sum r_n^2$.

Théorème — MLE = moindres carrés (sous bruit gaussien)

$$\ln\mathcal L(\bw;\mathcal D) = -\frac N2\ln(2\pi\sigma^2) - \frac{N}{2\sigma^2}\,\EMSE(\bw)\qquad\Longrightarrow\qquad \bw_{\text{MLE}} = \bw_{\text{LS}}.$$

Preuve — vraisemblance, log-vraisemblance, MLE = LS HW1 Q3.(1)

Densité d'une observation : $p(y_n\mid x_n,\bw) = \dfrac{1}{\sqrt{2\pi\sigma^2}}\exp\!\Big(-\dfrac{(y_n-\bw\T\bphi(x_n))^2}{2\sigma^2}\Big)$.

Indépendance des bruits ⇒ la densité jointe se factorise : $\mathcal L(\bw) = \prod_n p(y_n\mid x_n,\bw) = (2\pi\sigma^2)^{-N/2}\exp\!\Big(-\dfrac1{2\sigma^2}\sum_n(y_n-\bw\T\bphi(x_n))^2\Big)$.

Le log transforme le produit en somme (et $\ln$ est strictement croissant, donc même argmax) : $$\ln\mathcal L(\bw) = -\frac N2\ln(2\pi\sigma^2) - \frac1{2\sigma^2}\sum_n(y_n-\bw\T\bphi_n)^2 = -\frac N2\ln(2\pi\sigma^2) - \frac N{2\sigma^2}\EMSE(\bw).$$

Le premier terme ne dépend pas de $\bw$ et $\frac N{2\sigma^2}>0$. Maximiser $\ln\mathcal L$ revient donc à minimiser $\EMSE$ : $\bw_{\text{MLE}} = \argmin_{\bw}\EMSE(\bw) = \bw_{\text{LS}}$. Remarque : le résultat ne dépend pas de $\sigma$.

Hors slides En dérivant aussi par rapport à $\sigma^2$ : $\partial_{\sigma^2}\ln\mathcal L = -\frac N{2\sigma^2} + \frac{N\,\EMSE}{2\sigma^4} = 0 \Rightarrow \sigma^2_{\text{ML}} = \EMSE(\bw_{\text{ML}})$ : la variance du bruit estimée est la MSE résiduelle (PRML éq. 3.21).

∎

Question des slides — « Does the Gaussian assumption always hold? » (p.17)

Non. Le choix de la loss encode une hypothèse sur le bruit. Bruit de Laplace $p(\varepsilon)\propto e^{-|\varepsilon|/b}$ ⇒ la log-vraisemblance devient $-\frac1b\sum|r_n|$ ⇒ MLE = régression L1 (médiane conditionnelle), bien plus robuste aux valeurs aberrantes (outliers). Essaie dans la scène : choisis le bruit « Laplace » et tire un point très loin — la droite L1 bouge beaucoup moins que la droite L2. Hors slides

5Sur-apprentissage (overfitting)

Slides p.10, 20–21 PRML §1.1 p.4–11 (même exemple) HW1 Q2.(4)

Où on en est

Acquis

Une méthode complète : modèle, perte justifiée, formule close.

Il manque

Plus de fonctions de base = MSE d'entraînement plus petite. Est-ce toujours mieux ?

Cette partie

Non : avec trop de paramètres le modèle apprend le bruit (sur-apprentissage). On le mesure en comparant erreur d'entraînement et de test, et on le décompose en biais et variance.

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

StatQuestMachine Learning Fundamentals: Bias and VarianceBiais, variance, sur-apprentissage : train vs test avec une courbe « squiggly ».

Données du HW1 : $x_n\sim\mathrm{Unif}[0,1]$, $y_n = \sin(2\pi x_n) + \varepsilon_n$, $\varepsilon_n\sim\N(0, 0.2^2)$, $N_{\text{train}} = 15$, $N_{\text{test}} = 400$, base polynomiale $\bphi_M(x) = [1, x, \dots, x^M]\T$. Un modèle avec beaucoup de paramètres peut mémoriser le bruit au lieu d'apprendre la tendance. On le détecte en comparant erreurs d'entraînement et de test.

Note sur la graine

Le HW demande seed 0 avec numpy. Ce générateur JavaScript n'est pas celui de numpy : les points ne sont pas identiques à ceux de ton notebook, mais le comportement (et les ordres de grandeur) le sont.

Ce qu'il faut observer

$M = 0, 1$ : sous-apprentissage (underfitting), erreurs train et test élevées : le modèle est trop rigide.
$M = 3, 4$ : bon compromis, l'erreur de test est minimale.
$M \ge 9$ : l'erreur d'entraînement → 0 (avec $N = 15$ et $M = 14$, $\bPhi$ est carrée : interpolation exacte), mais l'erreur de test explose. Les coefficients deviennent énormes (des $\pm 10^5$ qui se compensent) : c'est ce qu'observe la slide 21, « overfitting when parameter magnitudes are large ».
Augmente $N$ : à $M$ fixé, le sur-apprentissage diminue. Plus de données = on peut se permettre un modèle plus riche.

Décomposition biais–variance Hors slides PRML §3.2 p.147–152

Au programme de PRML 3.2 (lecture du planning), pas des slides. Imagine qu'on refait l'expérience avec beaucoup de jeux de données indépendants $\mathcal D$. Chaque jeu donne une fonction ajustée $f_{\mathcal D}$. En un point $x$ :

$$\E_{\mathcal D}\big[(f_{\mathcal D}(x) - h(x))^2\big] = \underbrace{\big(\E_{\mathcal D}[f_{\mathcal D}(x)] - h(x)\big)^2}_{\text{biais}^2} + \underbrace{\E_{\mathcal D}\big[(f_{\mathcal D}(x) - \E_{\mathcal D}[f_{\mathcal D}(x)])^2\big]}_{\text{variance}},\quad h(x) = \E[y\mid x].$$

Même astuce que la décomposition de la section 1 (ajouter/retrancher la moyenne, le terme croisé s'annule). Et l'erreur de test attendue $=$ biais² $+$ variance $+$ bruit. Régulariser fort ⇒ fonctions rigides, toutes pareilles (faible variance) mais fausses en moyenne (fort biais). Régulariser peu ⇒ bonnes en moyenne mais chacune colle à son bruit (forte variance).

6Régression ridge — régularisation $\ell_2$

Slides p.21–22 PRML §3.1.4 p.144 DL §9.2 weight decay HW1 Q3.(3)

Où on en est

Acquis

Le sur-apprentissage s'accompagne de coefficients $w_\ell$ énormes qui se compensent.

Il manque

Un moyen de garder un modèle riche sans qu'il colle au bruit.

Cette partie

Pénaliser $\|\bw\|^2$ : la régression ridge. Nouvelle formule close, toujours inversible, et un $\lambda$ qui règle le compromis entre ajustement et simplicité.

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

StatQuestRegularization Part 1: Ridge (L2) RegressionPourquoi pénaliser $\|\bw\|^2$ réduit la variance ; choix de $\lambda$.

Pour limiter le sur-apprentissage : restreindre l'espace des paramètres en préférant les petits $\|\bw\|$ (slide 21).

Ridge regression

$$E_{\text{ridge}}(\bw) = \underbrace{\frac1N\|\by-\bPhi\bw\|^2}_{\text{MSE empirique}} + \underbrace{\lambda\|\bw\|^2}_{\text{régulariseur}},\qquad \lambda > 0,$$ $$\bw_{\text{ridge}} = \big(N\lambda\bI + \bPhi\T\bPhi\big)^{-1}\bPhi\T\by\quad\text{— unique, car } N\lambda\bI + \bPhi\T\bPhi\succ 0\ \text{pour tout } \lambda>0.$$

Les objets en jeu

$\lambda$: réel $>0$ (hyperparamètre)Le paramètre de régularisation (ridge parameter) : prix payé par unité de $\|\bw\|^2$. Choisi à la main ou par validation, pas par minimisation de l'erreur d'entraînement (sinon on prendrait toujours $\lambda = 0$).
$\|\bw\|^2 = \sum_\ell w_\ell^2$: nombreLe régulariseur $\ell_2$ : carré de la distance de $\bw$ à l'origine. Ses lignes de niveau sont des cercles/sphères.
$\bI\in\R^{L\times L}$: matrice identité$N\lambda\bI$ ajoute $N\lambda$ sur la diagonale de $\bPhi\T\bPhi$ (le facteur $N$ vient du $\frac1N$ devant la MSE).
$\mathbf A\succ 0$: notation« $\mathbf A$ est définie positive » : $\bv\T\mathbf A\bv>0$ pour tout $\bv\ne0$ (toutes ses valeurs propres $>0$) ⇒ inversible. $\succeq 0$ = semi-définie positive (valeurs propres $\ge0$).
$E_{\text{ridge}}(\bw)$: fonction $\R^L\to\R_+$L'objectif régularisé : ajustement aux données + pénalité de complexité.

Preuve — forme close du ridge et définie-positivité

Gradient : $\nabla E_{\text{ridge}} = \frac2N\bPhi\T(\bPhi\bw-\by) + 2\lambda\bw$ (car $\nabla\|\bw\|^2 = 2\bw$).

Annulons et multiplions par $N/2$ : $\bPhi\T\bPhi\bw - \bPhi\T\by + N\lambda\bw = 0 \iff (N\lambda\bI + \bPhi\T\bPhi)\bw = \bPhi\T\by$.

Pour tout $\bv\ne 0$ : $\bv\T(N\lambda\bI + \bPhi\T\bPhi)\bv = N\lambda\|\bv\|^2 + \|\bPhi\bv\|^2 \ge N\lambda\|\bv\|^2 > 0$. La matrice est définie positive, donc inversible — même si $\bPhi\T\bPhi$ est singulière (ex. $N < L$). D'où l'unicité.

La hessienne $2(\frac1N\bPhi\T\bPhi + \lambda\bI)$ est définie positive ⇒ fonction strictement convexe ⇒ ce point stationnaire est l'unique minimum global.

Hors slides Géométriquement, ajouter $\lambda\bI$ décale toutes les valeurs propres de $\frac1N\bPhi\T\bPhi$ de $\lambda$ : les directions « plates » du bol (valeur propre ≈ 0, instables) deviennent courbées. Le conditionnement passe de $\frac{\mu_{\max}}{\mu_{\min}}$ à $\frac{\mu_{\max}+\lambda}{\mu_{\min}+\lambda}$.

∎

Ci-dessous, le polynôme $M = 10$ du HW1 avec la grille de $\lambda$ du devoir. Observe : $\|\bw\|$ s'effondre dès $\lambda \approx 10^{-7}$ ; l'erreur de test est en U en fonction de $\ln\lambda$ ; le troisième panneau montre le chemin de régularisation : chaque coefficient $w_j$ en fonction de $\ln\lambda$, qui tendent tous vers 0 (sans jamais l'atteindre exactement).

Géométrie du ridge : ellipses et cercle

Slides p.29 PRML Fig. 3.4 p.146

Dans l'espace des poids $(w_1,w_2)$, la MSE est un bol dont les lignes de niveau sont des ellipses centrées en $\bw_{\text{LS}}$ (leurs axes sont les vecteurs propres de $\bPhi\T\bPhi$). Le régulariseur $\lambda\|\bw\|^2$ est un bol rond centré en 0 (niveaux = cercles). La somme de deux bols est un bol dont le fond $\bw_{\text{ridge}}$ se situe là où une ellipse est tangente à un cercle : les deux gradients y sont opposés, $\nabla\text{MSE} = -\lambda\nabla\|\bw\|^2$. Quand $\lambda$ va de $0$ à $\infty$, $\bw_{\text{ridge}}$ glisse de $\bw_{\text{LS}}$ vers $0$ le long de la courbe blanche.

Forme contrainte équivalente Hors slides — revu au chapitre SVM (Lagrangien). Pour chaque $\lambda>0$ il existe un budget $t$ tel que $\bw_{\text{ridge}} = \argmin\{\EMSE(\bw) : \|\bw\|^2\le t\}$ ; $\lambda$ est le multiplicateur de Lagrange de la contrainte. Le point de tangence est exactement la condition « gradient de l'objectif ∝ gradient de la contrainte ».

Rétrécissement par direction propre. Si $\frac1N\bPhi\T\bPhi = \sum_i\mu_i\bu_i\bu_i\T$, alors la composante de $\bw_{\text{ridge}}$ sur $\bu_i$ vaut $\frac{\mu_i}{\mu_i+\lambda}$ fois celle de $\bw_{\text{LS}}$. Les directions peu informatives ($\mu_i$ petit, axe long de l'ellipse) sont écrasées ; les directions bien déterminées sont presque intactes. C'est visible dans la scène : le point glisse d'abord le long du grand axe.

7Interprétation MAP (maximum a posteriori)

Slides p.23–26 PRML §3.3.1 p.152–156 (Fig. 3.7) HW1 Q3.(2)

Où on en est

Acquis

Ridge = MSE empirique + $\lambda\|\bw\|^2$, mais le terme ajouté a été posé « à la main ».

Il manque

D'où vient ce terme ? (Le §4 a justifié la MSE ; on fait pareil pour la pénalité.)

Cette partie

Même modèle de bruit gaussien + une croyance a priori « $\bw$ est petit » (prior gaussien) ⇒ l'estimateur MAP est exactement le ridge.

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

Rich Radke (RPI)PB65: Maximum A Posteriori (MAP) EstimationPrior × vraisemblance → posterior, et le mode du posterior (MAP).

Même modèle d'observation gaussien $p(\by\mid\bPhi,\bw) = \N(\by\mid\bPhi\bw,\sigma^2\bI)$, plus une croyance a priori : les bons paramètres sont petits, $p(\bw) = \N(\bw\mid 0,\bSigma)$.

Estimateur MAP

$$\bw_{\text{MAP}} = \argmax_{\bw} p(\bw\mid\by,\bPhi) = \argmax_{\bw} \underbrace{p(\by\mid\bPhi,\bw)}_{\text{vraisemblance}}\ \underbrace{p(\bw)}_{\text{prior}},\qquad \bw_{\text{MAP}} = \big(\sigma^2\bSigma^{-1} + \bPhi\T\bPhi\big)^{-1}\bPhi\T\by.$$ Par Bayes, $p(\bw\mid\by,\bPhi) = p(\by\mid\bPhi,\bw)p(\bw)/p(\by\mid\bPhi)$ et le dénominateur ne dépend pas de $\bw$. Avec $\bSigma = \frac{\sigma^2}{N\lambda}\bI$ (HW : $\bSigma = \tau^2\bI$, $\lambda = \frac{\sigma^2}{N\tau^2}$) : $\bw_{\text{MAP}} = \bw_{\text{ridge}}$.

Les objets en jeu

$p(\bw)$: densité sur $\R^L$Le prior : ce qu'on croit sur $\bw$ avant de voir les données. Ici $\N(0,\bSigma)$ : « les poids sont probablement petits ».
$\bSigma\in\R^{L\times L}$: matrice de covariance, $\succ0$Forme et taille de la bosse du prior. $\bSigma = \tau^2\bI$ : bosse ronde de rayon typique $\tau$.
$\tau$: réel $>0$Écart-type a priori de chaque poids (HW1).
$p(\by\mid\bPhi,\bw)$: densité sur $\R^N$La vraisemblance (même modèle gaussien qu'au §4) : $\N(\by\mid\bPhi\bw,\sigma^2\bI)$.
$p(\bw\mid\by,\bPhi)$: densité sur $\R^L$Le posterior : croyance sur $\bw$ après avoir vu les données. Bayes : posterior $\propto$ vraisemblance × prior.
$p(\by\mid\bPhi)$: nombre (constante)L'évidence (marginal likelihood) $= \int p(\by\mid\bPhi,\bw)p(\bw)\,d\bw$ : normalise le posterior, indépendante de $\bw$ donc inutile pour l'argmax.
$\bw_{\text{MAP}}$: vecteur de $\R^L$Le mode (point le plus haut) du posterior.

Géométrie. Dans l'espace des poids : le prior est une bosse ronde centrée en 0 ; chaque point observé ajoute une vraisemblance en forme de « crête » (une bande : toutes les droites qui passent près de ce point) ; le posterior est le produit. Chaque nouvelle observation multiplie par une nouvelle crête, et la bosse du posterior se resserre autour de la vraie valeur. C'est la Fig. 3.7 de PRML, en interactif : clique « observer un point ».

Preuve — MAP gaussien et équivalence avec le ridge HW1 Q3.(2)

Log-posterior à constante près : $\ln p(\bw\mid\by) = \ln p(\by\mid\bw) + \ln p(\bw) + C = -\frac1{2\sigma^2}\|\by-\bPhi\bw\|^2 - \frac12\bw\T\bSigma^{-1}\bw + C'$.

Maximiser revient à minimiser $J(\bw) = \frac1{2\sigma^2}\|\by-\bPhi\bw\|^2 + \frac12\bw\T\bSigma^{-1}\bw$. Gradient : $\nabla J = \frac1{\sigma^2}\bPhi\T(\bPhi\bw-\by) + \bSigma^{-1}\bw$.

$\nabla J = 0 \iff (\bPhi\T\bPhi + \sigma^2\bSigma^{-1})\bw = \bPhi\T\by \iff \bw_{\text{MAP}} = (\sigma^2\bSigma^{-1} + \bPhi\T\bPhi)^{-1}\bPhi\T\by$. ($J$ est strictement convexe car $\bSigma^{-1}\succ0$.)

Avec $\bSigma = \tau^2\bI$ : $\sigma^2\bSigma^{-1} = \frac{\sigma^2}{\tau^2}\bI$. On compare avec $\bw_{\text{ridge}} = (N\lambda\bI + \bPhi\T\bPhi)^{-1}\bPhi\T\by$ : égalité ssi $N\lambda = \frac{\sigma^2}{\tau^2}$, soit $\lambda = \dfrac{\sigma^2}{N\tau^2}$. (Slides : $\bSigma = \frac{\sigma^2}{N\lambda}\bI$, c'est la même relation.)

Lecture : prior étroit ($\tau$ petit) ⇒ $\lambda$ grand ⇒ forte régularisation. Beaucoup de données ($N$ grand) à $\tau$ fixé ⇒ $\lambda$ effectif petit : les données « écrasent » le prior.

Hors slides Le posterior complet est gaussien : $p(\bw\mid\by) = \N(\bw\mid\mathbf m_N,\mathbf S_N)$ avec $\mathbf S_N^{-1} = \bSigma^{-1} + \frac1{\sigma^2}\bPhi\T\bPhi$ et $\mathbf m_N = \frac1{\sigma^2}\mathbf S_N\bPhi\T\by$ (PRML 3.50–3.51). Le MAP est sa moyenne (= son mode). Les droites de la scène sont des tirages de ce posterior.

∎

8Régression lasso — parcimonie $\ell_1$

Slides p.28–29 PRML §3.1.4 p.144–146 (Fig. 3.3, 3.4)

Où on en est

Acquis

Le ridge rétrécit tous les coefficients, mais aucun ne devient exactement nul.

Il manque

Et si on veut sélectionner les variables utiles (beaucoup de $w_\ell = 0$) ?

Cette partie

La pénalité $\ell_1$ (lasso) donne des solutions parcimonieuses, et on voit pourquoi géométriquement. Prix à payer : plus de formule close (non dérivable en 0), ce qui motive la partie suivante.

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

StatQuestRegularization Part 2: Lasso (L1) RegressionLe lasso et sa différence clé avec le ridge : des coefficients exactement nuls.▶

StatQuestRidge vs Lasso Regression, Visualized!!!Pourquoi le lasso met des poids à 0 et pas le ridge, en visualisant la pénalité.

Lasso regression

$$E_{\text{lasso}}(\bw) = \frac1N\|\by-\bPhi\bw\|^2 + \lambda\|\bw\|_1,\qquad \|\bw\|_1 = \sum_\ell|w_\ell|.$$ Pas de forme close ; l'objectif n'est pas différentiable en $w_\ell = 0$ → sous-gradient (subgradient) ou descente de coordonnées. Question des slides : « Does Lasso prefer a sparse solution? » — Oui, et la raison est géométrique.

Les objets en jeu

$\|\bw\|_1 = \sum_\ell|w_\ell|$: nombreLa norme $\ell_1$ (distance « Manhattan » à l'origine). Ses lignes de niveau sont des losanges (2D) / octaèdres (3D), avec des coins sur les axes.
$\|\bw\|_q = (\sum_\ell|w_\ell|^q)^{1/q}$: nombre ($q>0$)Famille qui contient $\ell_1$ ($q=1$) et $\ell_2$ ($q=2$). Pour $q<1$ ce n'est plus une norme (boule non convexe).
parcimonieux: propriété d'un vecteur(sparse) beaucoup de coordonnées exactement nulles ⇒ les features correspondantes sont éliminées (sélection de variables).
$\partial g(w)$: ensemble de réelsLe sous-différentiel d'une fonction convexe : l'ensemble des pentes des droites qui touchent $g$ en $w$ en restant dessous. Égal à $\{g'(w)\}$ là où $g$ est dérivable ; un intervalle aux plis (ex. $\partial|w|(0) = [-1,1]$).

La boule a des coins. En forme contrainte, on cherche le point le plus bas du bol MSE dans la boule $\{\|\bw\|_q\le t\}$. On fait grossir les ellipses de niveau depuis $\bw_{\text{LS}}$ jusqu'à toucher la boule. Le cercle ($q=2$) est lisse : le contact a lieu « n'importe où ». Le losange ($q=1$) a des pointes sur les axes ; une ellipse qui grossit touche très souvent une pointe en premier ⇒ une coordonnée exactement nulle. Pour $q<1$ (non convexe), c'est encore plus marqué.

En dimension 3, c'est encore plus parlant : l'octaèdre $\{\|\bw\|_1\le t\}$ a 6 sommets et 12 arêtes ; toucher un sommet ⇒ 2 zéros, une arête ⇒ 1 zéro. La sphère $\ell_2$ n'a ni l'un ni l'autre.

En 1D : le seuillage doux (soft thresholding)

Hors slides« subgradient method », slide 28

Prenons le problème scalaire $\min_w\ (w-a)^2 + \lambda|w|$ (c'est ce que résout la descente de coordonnées pour chaque $w_\ell$). La valeur absolue ajoute un pli en 0. Tant que $|a|$ est petit, le pli « retient » le minimum en 0 exactement ; le ridge, lui, ne fait que diviser par un facteur ($w^* = \frac{a}{1+\lambda}$), sans jamais donner 0.

Preuve — seuillage doux par sous-gradient

Sous-différentiel de $|w|$ : $\partial|w| = \{\operatorname{sign}(w)\}$ si $w\ne0$, et $[-1,1]$ en $w = 0$ (toutes les pentes des droites qui passent sous le pli). Pour une fonction convexe, $w^*$ est un minimum $\iff 0\in\partial g(w^*)$.

$\partial g(w) = 2(w-a) + \lambda\,\partial|w|$. Cas $w^*>0$ : $2(w^*-a)+\lambda = 0 \Rightarrow w^* = a - \frac\lambda2$, cohérent ssi $a > \frac\lambda2$. Cas $w^*<0$ : $w^* = a+\frac\lambda2$, cohérent ssi $a< -\frac\lambda2$.

Cas $w^* = 0$ : il faut $0\in -2a + \lambda[-1,1]$, i.e. $|a|\le\frac\lambda2$. Le pli est assez « ouvert » pour absorber la pente $-2a$ de la parabole.

Conclusion : $w^* = S_{\lambda/2}(a) := \operatorname{sign}(a)\max(|a|-\tfrac\lambda2, 0)$. Tout ce qui est plus petit que le seuil devient exactement 0 : c'est la sélection de variables (feature selection).

∎

Chemins de régularisation : ridge vs lasso

Données synthétiques : 8 features corrélées dont seulement 3 sont vraiment utiles. À gauche le ridge : tous les coefficients rétrécissent ensemble, aucun ne s'annule. À droite le lasso (résolu par descente de coordonnées) : les coefficients quittent zéro un par un quand $\lambda$ diminue — le lasso fait de la sélection de variables (interprétabilité) et produit des modèles parcimonieux qui généralisent souvent bien (slide 29).

9Apprendre = optimiser : descente de gradient

Slides p.31–36 DL §7.1–7.2 p.207–213

Où on en est

Acquis

Moindres carrés et ridge ont une formule close ; le lasso non, et la plupart des modèles (logistique, SVM, réseaux) non plus.

Il manque

Une méthode générale pour minimiser une perte sans résoudre $\nabla = 0$ à la main.

Cette partie

La descente de gradient : direction, choix du pas, momentum contre les zigzags, et SGD quand $N$ est grand. C'est l'outil de tous les chapitres suivants.

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

StatQuestGradient Descent, Step-by-StepLa descente de gradient pas à pas sur une régression : dérivées, pas, arrêt.▶

3Blue1BrownGradient descent, how neural networks learnLe gradient comme direction de descente dans un paysage de coût (animations 3Blue1Brown).

Learning as optimization

$$\argmin_{\btheta}\ \hL(\btheta) = \argmin_{\btheta}\frac1N\sum_{i=1}^N\ell\big(y_i, f(x_i,\btheta)\big)$$ $L(\btheta) := \E\,\ell(y, f(x,\btheta))$ est le risque espéré (expected risk) ; $\hL$ est le risque empirique. Les formes closes (comme la régression linéaire) sont l'exception.

Les objets en jeu

$\btheta$: vecteur de $\R^P$Tous les paramètres du modèle (notation générique ; $=\bw$ en régression linéaire).
$f(x,\btheta)$: prédiction (nombre)Sortie du modèle de paramètres $\btheta$ sur l'entrée $x$.
$\ell(y,\hat y)$: fonction $\to\R_+$La perte (loss) d'un exemple : coût de prédire $\hat y$ quand la vérité est $y$. Ex. $\ell = (y-\hat y)^2$.
$L(\btheta)$: nombre (fonction de $\btheta$)Le risque espéré (expected risk) $\E_{(x,y)\sim p}[\ell(y,f(x,\btheta))]$ : la perte moyenne sur la vraie loi. Ce qu'on veut minimiser, mais incalculable.
$\hL(\btheta)$: nombre (fonction de $\btheta$)Le risque empirique : moyenne des pertes sur les $N$ exemples. Ce qu'on minimise effectivement (principe d'empirical risk minimization).

Un exemple 1D des slides

$\hL(\theta) = \theta^4 + 7\theta^3 + 5\theta^2 - 17\theta + 3$ (slides p.32–36, figure de MML). On cherche $\frac{d\hL}{d\theta} = 0$ (polynôme de degré 3 ici, mais pas de formule générale en degré ≥ 5 : Abel–Ruffini) ; la dérivée seconde classe les points stationnaires. Numériquement : la descente de gradient $\theta_{t+1} = \theta_t - \gamma\,\hL'(\theta_t)$. Déplace le point de départ : à gauche de la bosse on tombe dans le minimum global, à droite dans le minimum local. Augmente $\gamma$ pour voir l'overshoot, puis la divergence.

Le gradient, géométriquement

Slides p.34Preuve de la plus forte pente : hors slides

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

Khan Academy (Grant Sanderson)Why the gradient is the direction of steepest ascentPourquoi $\nabla f$ pointe vers la plus forte montée (dérivée directionnelle).▶

Khan Academy (Grant Sanderson)Gradient and graphsLe gradient vu sur le graphe de la fonction et sur ses lignes de niveau.

Gradient

Pour $f:\R^D\to\R$, $\ \nabla f(\bx) = \big[\frac{\partial f}{\partial x_1},\dots,\frac{\partial f}{\partial x_D}\big]\T$ (vecteur colonne ; la dérivée $\frac{df}{d\bx}$ est sa transposée, un vecteur ligne).

Les objets en jeu

$f:\R^D\to\R$: fonction scalaireUne fonction de plusieurs variables à valeur réelle (ex. la loss en fonction des paramètres).
$\frac{\partial f}{\partial x_i}$: nombre (en chaque point)Dérivée partielle : pente de $f$ quand on ne bouge que $x_i$, les autres coordonnées étant gelées.
$\nabla f(\bx)\in\R^D$: vecteur colonneLe gradient : les $D$ pentes partielles empilées. Géométriquement : flèche perpendiculaire aux lignes de niveau, dans le sens de la montée la plus raide, de longueur = cette pente.
$D_\bu f(\bx) = \nabla f\T\bu$: nombre ($\|\bu\|=1$)Dérivée directionnelle : pente de $f$ quand on part de $\bx$ dans la direction unitaire $\bu$.
$\nabla^2 f(\bx)\in\R^{D\times D}$: matrice symétriqueLa hessienne (dérivées secondes) : la courbure. Vue au chapitre 2 (Newton).

Trois faits géométriques : (1) $\nabla f$ est perpendiculaire aux lignes de niveau ; (2) il pointe dans la direction de plus forte montée ; (3) sa norme est la pente dans cette direction. Survole la carte : la rose polaire montre la dérivée directionnelle $D_\bu f = \nabla f\cdot\bu = \|\nabla f\|\cos\angle(\nabla f,\bu)$ pour chaque direction $\bu$ — deux cercles tangents, maximum dans la direction du gradient, nulle le long de la ligne de niveau.

Preuve — $-\nabla f$ est la direction de plus forte descente

Taylor à l'ordre 1 : $f(\bx + h\bu) = f(\bx) + h\,\nabla f(\bx)\T\bu + o(h)$, donc la dérivée directionnelle est $D_\bu f(\bx) = \nabla f(\bx)\T\bu$ pour $\|\bu\| = 1$.

Le long d'une ligne de niveau $f$ est constante, donc $D_\bu f = 0$ pour $\bu$ tangent : $\nabla f\T\bu = 0$, le gradient est orthogonal à la ligne de niveau.

Conséquence pour GD : pour $\gamma$ assez petit, $f(\bx - \gamma\nabla f) = f(\bx) - \gamma\|\nabla f\|^2 + o(\gamma) < f(\bx)$ dès que $\nabla f\ne0$ : un petit pas fait toujours descendre.

∎

Descente de gradient sur une quadratique — zigzag, pas, momentum

Slides p.35, 38–42 DL §7.3 convergence, §7.3.1 momentum

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

DeepLearning.AI — Andrew NgGradient Descent With Momentum (C2W2L06)Le momentum comme moyenne des pas passés : moins de zigzag dans les vallées étroites.

Gradient descent · Momentum

$$\text{GD :}\quad \btheta_{t+1} = \btheta_t - \gamma_t\nabla\hL(\btheta_t)\qquad\qquad \text{Momentum :}\quad \btheta_{i+1} = \btheta_i - \gamma_i\nabla\hL(\btheta_i) + \alpha\,\Delta\btheta_i,\quad \Delta\btheta_i = \btheta_i - \btheta_{i-1},\ \alpha\in[0,1].$$

Les objets en jeu

$t$ (ou $i$): entierNuméro d'itération.
$\btheta_t$: vecteur de $\R^P$Les paramètres après $t$ pas : un point qui se déplace dans l'espace des paramètres (la « bille »).
$\gamma_t$: réel $>0$Le pas (step size, learning rate) : de combien on avance le long de $-\nabla\hL$. Trop petit : lent ; trop grand : oscillations puis divergence.
$\Delta\btheta_i = \btheta_i-\btheta_{i-1}$: vecteurLe dernier déplacement effectué (la « vitesse » de la bille).
$\alpha$: réel $\in[0,1]$Le coefficient de momentum : fraction du déplacement précédent qu'on garde. $\alpha = 0$ : GD simple ; $\alpha\to1$ : peu de frottement.

Exemple des slides (p.38) : $\hL(\bx) = \frac12\bx\T\begin{bmatrix}2&1\\1&20\end{bmatrix}\bx - \begin{bmatrix}5\\3\end{bmatrix}\T\bx$, départ $\bx_0 = [-3,-1]\T$, $\gamma = 0.085$. La vallée est longue et étroite (mal conditionnée) : le gradient pointe presque perpendiculairement à la direction du minimum ⇒ zigzag. Le momentum (mémoire du pas précédent) amortit l'oscillation dans la direction raide et accumule la vitesse dans la direction plate. Compare les trois billes, change $\gamma$, le conditionnement, $\alpha$.

Pourquoi $\gamma < 2/L$ ? Analyse exacte sur une quadratique Hors slides DL §7.3

La slide 39 (Murphy) mentionne « $\eta < 2/L$ ensures convergence ». Voici la preuve dans le cas quadratique, qui explique aussi le zigzag.

Preuve — convergence de GD sur $\frac12\bx\T\bA\bx - \bb\T\bx$

$\nabla\hL(\bx) = \bA\bx - \bb$, minimum $\bx^* = \bA^{-1}\bb$. Erreur $\be_t = \bx_t - \bx^*$ : $\be_{t+1} = \be_t - \gamma(\bA\bx_t - \bA\bx^*) = (\bI - \gamma\bA)\be_t$.

Diagonalisons $\bA = \sum_i\mu_i\bu_i\bu_i\T$ ($\mu_1\ge\dots\ge\mu_D>0$). Dans la base propre, chaque composante évolue indépendamment : $e^{(i)}_{t+1} = (1-\gamma\mu_i)\,e^{(i)}_t$, donc $e^{(i)}_t = (1-\gamma\mu_i)^t e^{(i)}_0$.

Convergence $\iff |1-\gamma\mu_i|<1$ pour tout $i$ $\iff 0\lt \gamma\lt \frac{2}{\mu_{\max}}$. Ici $L = \mu_{\max}$ est la constante de Lipschitz du gradient. Si $1 - \gamma\mu_i < 0$, la composante change de signe à chaque pas : c'est le zigzag dans la direction raide.

Le taux global est $\max_i|1-\gamma\mu_i|$, minimisé pour $\gamma^* = \frac{2}{\mu_{\max}+\mu_{\min}}$, qui donne $\frac{\kappa-1}{\kappa+1}$ avec $\kappa = \mu_{\max}/\mu_{\min}$ (conditionnement). Plus $\kappa$ est grand, plus GD est lent. Momentum (bien réglé) améliore en $\frac{\sqrt\kappa-1}{\sqrt\kappa+1}$.

Line search exacte (slide 39) : $\eta_t = \argmin_\eta\hL(\btheta_t + \eta\mathbf d_t) = -\frac{\mathbf d_t\T(\bA\btheta_t - \bb)}{\mathbf d_t\T\bA\mathbf d_t}$ (on annule la dérivée d'une parabole en $\eta$). Avec $\mathbf d_t = -\nabla\hL$, les directions successives sont orthogonales (zigzag à angle droit, bille rose).

∎

Descente de gradient stochastique (SGD)

Slides p.37, 43–46 PRML §3.1.3 (LMS) p.143 DL §7.2.3–7.2.4 HW1 Q4

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

StatQuestStochastic Gradient Descent, Clearly Explained!!!SGD et mini-batchs : même descente, un gradient estimé sur quelques points.

Pour la régression linéaire, $\nabla\hL(\bw_t) = \frac2N\sum_n(\bw_t\T\bphi_n - y_n)\bphi_n$ (slide 37) : chaque point « tire » sur $\bw$ avec une force proportionnelle à son résidu. Le gradient complet est la moyenne de ces $N$ flèches. SGD n'en tire qu'un mini-batch $\mathcal B_t$ :

$$\bw_{t+1} = \bw_t - \gamma_t\,\bg_t,\qquad \bg_t = \nabla\hL_{\mathcal B_t}(\bw_t) = \frac1{|\mathcal B_t|}\sum_{i\in\mathcal B_t}\nabla\ell_i(\bw_t).$$

Les objets en jeu

$\ell_i(\bw)$: fonction $\R^L\to\R_+$La perte du seul exemple $i$ : $\ell_i(\bw) = (y_i - \bw\T\bphi_i)^2$. Le risque empirique est leur moyenne : $\hL = \frac1N\sum_i\ell_i$.
$\nabla\ell_i(\bw)\in\R^L$: vecteurLe gradient d'un seul exemple $= 2(\bw\T\bphi_i - y_i)\bphi_i$ : direction $\bphi_i$, longueur proportionnelle au résidu.
$\mathcal B_t\subseteq\{1,\dots,N\}$: ensemble aléatoire d'indicesLe mini-batch tiré au pas $t$ ; $B = |\mathcal B_t|$ sa taille.
$\hL_{\mathcal B}$: fonctionLe risque empirique restreint au mini-batch : une version bruitée de $\hL$.
$\bg_t$: vecteur aléatoireLe gradient stochastique : estimateur de $\nabla\hL(\bw_t)$ calculé sur $B$ exemples seulement.
époque: unité de temps(epoch) un passage complet sur les $N$ exemples = $N/B$ pas de SGD.

$|\mathcal B| = 1$ : SGD classique (= algorithme LMS de PRML) ; $1<|\mathcal B|\lt N$ : mini-batch ; $|\mathcal B| = N$ : GD. Dans la scène : fines flèches = gradients individuels $\nabla\ell_i$, flèche bleue = leur moyenne (gradient complet), flèche rose = gradient du mini-batch tiré. En moyenne sur les tirages, la rose est la bleue (sans biais), mais elle fluctue (variance).

Justification de SGD — estimateur sans biais

Si $\mathcal B$ est tiré uniformément parmi les sous-ensembles de taille $B$ de $\{1,\dots,N\}$ : $\ \E_{\mathcal B}\big[\nabla\hL_{\mathcal B}(\btheta)\big] = \nabla\hL(\btheta)$.

Preuve — sans biais via variables indicatrices HW1 Q4.(4)

Écrivons la somme sur le batch avec des indicatrices : $\sum_{i\in\mathcal B}\nabla\ell_i = \sum_{i=1}^N\mathbb 1[i\in\mathcal B]\,\nabla\ell_i$.

Linéarité de l'espérance ($\nabla\ell_i(\btheta)$ est déterministe, seul $\mathcal B$ est aléatoire) : $\E\big[\frac1B\sum_i\mathbb 1[i\in\mathcal B]\nabla\ell_i\big] = \frac1B\sum_i P(i\in\mathcal B)\,\nabla\ell_i$.

$P(i\in\mathcal B)$ : parmi les $\binom NB$ sous-ensembles, ceux qui contiennent $i$ sont au nombre de $\binom{N-1}{B-1}$. Donc $P(i\in\mathcal B) = \binom{N-1}{B-1}/\binom NB = \frac BN$. (Intuition : $B$ places pour $N$ indices, par symétrie chacun a la même chance.)

D'où $\E_{\mathcal B}[\nabla\hL_{\mathcal B}] = \frac1B\sum_i\frac BN\nabla\ell_i = \frac1N\sum_i\nabla\ell_i = \nabla\hL(\btheta)$.

Hors slides Variance (tirage sans remise) : $\Var[\bg] = \frac{N-B}{N-1}\cdot\frac{\sigma_\ell^2}{B}$ où $\sigma^2_\ell$ est la variance des gradients individuels. Elle décroît en $1/B$ et s'annule pour $B = N$.

∎

Avantages / inconvénients (slide 46)

✓ économe en mémoire et en calcul par pas ; ✓ sans biais ; ✗ variance élevée si $B$ petit (d'où des pas $\gamma_t$ décroissants pour converger exactement) ; ✓ le bruit peut aider à s'échapper de mauvais minima locaux (bien visible sur l'exemple 1D : avec du bruit, on peut franchir la bosse).

10Résumé & questions de la slide 47

Tout le chapitre en une chaîne

$$\underbrace{\min_f\E[(y-f(\bx))^2]}_{\text{§1 : }f^* = \E[y\mid\bx]}\ \xrightarrow{\text{modèle}}\ \underbrace{f(\bx) = \bw\T\bphi(\bx)}_{\text{§2}}\ \xrightarrow{\text{données}}\ \underbrace{\bw_{\text{LS}} = (\bPhi\T\bPhi)^{-1}\bPhi\T\by}_{\text{§3 : moindres carrés} = \text{§4 : MLE}}$$ $$\xrightarrow{\text{sur-apprentissage (§5)}}\ \underbrace{\bw_{\text{ridge}} = (N\lambda\bI+\bPhi\T\bPhi)^{-1}\bPhi\T\by}_{\text{§6 : ridge} = \text{§7 : MAP}},\quad\underbrace{\lambda\|\bw\|_1}_{\text{§8 : lasso}}\ \xrightarrow{\text{pas de formule close}}\ \underbrace{\btheta_{t+1} = \btheta_t-\gamma_t\nabla\hL(\btheta_t)}_{\text{§9 : GD, momentum, SGD}}$$

Quel est le rôle des fonctions de base ?

Réponse

Elles transforment l'entrée pour qu'un modèle linéaire en $\bw$ capture des relations non linéaires en $x$. On garde la convexité et la forme close ; la difficulté est déplacée dans le choix (manuel) des features. Géométriquement : on relève les données dans un espace de features où une fonction linéaire (un hyperplan) suffit.

Quel est le rôle de la régularisation ?

Réponse

Limiter la complexité effective (préférer les petits $\|\bw\|$) pour réduire le sur-apprentissage : moins de variance au prix d'un peu de biais. Elle rend aussi le problème bien posé ($N\lambda\bI + \bPhi\T\bPhi\succ0$). Interprétation bayésienne : prior gaussien sur $\bw$ (MAP).

Quels avantages à utiliser la norme $\ell_1$ ?

Réponse

Solutions parcimonieuses (coefficients exactement nuls) : sélection de variables, interprétabilité, souvent bonne généralisation. Raison géométrique : la boule $\ell_1$ a des coins sur les axes ; raison analytique : le pli de $|w|$ en 0 (seuillage doux). Prix : objectif non différentiable, pas de forme close.

Quel est l'intérêt de SGD ?

Réponse

Coût par pas en $O(|\mathcal B|)$ au lieu de $O(N)$, mémoire réduite ; le gradient de mini-batch est un estimateur sans biais du gradient complet ; le bruit peut aider à éviter de mauvais optima. Inconvénient : variance → trajectoire bruitée, besoin de réduire $\gamma_t$.

Chapitre suivant : régression logistique · s'entraîner.