Généralisation et sélection de modèleGeneralization and Model Selection · Cours 8 (10/6)

Slides 5-model-selection (28 p.) PRML §1.3 Model Selection p.32 PRML §1.1 p.4–11 DL §9.3 Learning curves

Les chapitres 1 à 3 apprenaient à minimiser une erreur d'entraînement dans une classe de modèles fixée. Ce chapitre répond à une seule question : comment choisir la classe de modèles (degré, $\lambda$, $C$, noyau…) et annoncer honnêtement sa performance, alors que la vraie erreur sur de nouvelles données est inconnue ? Au début de chaque section, un encadré Où on en est fait le point.

Feuille de route

Slides p.2 (plan)

Plan des slides : (1) l'erreur de généralisation (§1–2) ; (2) sur-/sous-apprentissage et régularisation (§3) ; (3) sélection et évaluation : train / validation / test (§4) ; (4) la validation croisée (§5). La chaîne complète, cliquable :

① Question · §1degré 1, 3 ou 12 ?l'erreur d'entraînement choisit toujours le plus complexe

→

② Cible · §2l'erreur de généralisation $L(f)$$\hL_S(\hat f)$ est optimiste ; des données neuves sont sans biais

→

③ Diagnostic · §3complexité, $N$, $\lambda$sous- et sur-apprentissage

→

④ Méthode · §4train / validation / testla validation peut elle-même sur-apprendre

→

⑤ Peu de données · §5validation croisée à $K$ plischaque exemple sert une fois en validation

Le raisonnement, maillon par maillon

①Le problème. Trois polynômes ajustés aux mêmes points : le plus complexe a toujours la plus petite erreur d'entraînement (les classes sont emboîtées). Donc l'erreur d'entraînement ne peut pas servir à choisir. → Il faut dire précisément ce qu'on veut mesurer.
②La bonne cible. L'erreur de généralisation $L(f)$ : la perte moyenne sur un nouvel exemple tiré de la même loi $P$. On montre que l'erreur d'entraînement du modèle appris la sous-estime en moyenne (il a vu ces points), alors que l'erreur sur des données indépendantes est sans biais — avec une incertitude en $1/\sqrt m$.
③Comprendre l'écart. En faisant varier la complexité, la taille $N$ et la pénalité $\lambda$, on voit les deux modes d'échec : sous-apprentissage (les deux erreurs sont hautes) et sur-apprentissage (train bas, généralisation haute). Les bons réglages dépendent des données : il faut les choisir avec des données.
④La procédure. Paramètres appris sur l'entraînement, hyperparamètres choisis sur la validation, performance annoncée sur le test, mis de côté dès le début. Piège : choisir le minimum de plusieurs erreurs de validation bruitées donne un chiffre optimiste ; c'est pourquoi le test doit rester intact.
⑤Économiser les données. Avec peu d'exemples, une seule validation gaspille des données et donne un choix instable. La validation croisée fait tourner l'ensemble de validation et moyenne : plus coûteuse ($K$ entraînements par candidat), mais plus stable.

À la fin du chapitre, tu dois savoir…

définir $L(f)$, $\hL_S(f)$ et l'écart de généralisation, et dire lesquels sont aléatoires ;
prouver que $\E_S[\hL_S(f)] = L(f)$ pour $f$ fixé, et expliquer pourquoi c'est faux pour $\hat f = A(S)$ ;
reconnaître sous- et sur-apprentissage sur des courbes, et le rôle de $N$ et de $\lambda$ ;
distinguer paramètres et hyperparamètres, et décrire la procédure ajuster / sélectionner / réajuster / évaluer ;
expliquer pourquoi l'erreur de validation du modèle choisi est optimiste ;
écrire le score de validation croisée et comparer holdout et CV.

Où se trouve chaque question du HW4 dans ce chapitre

P1.(1)–(2) entraînement vs généralisation → §2, optimisme, courbes d'apprentissage · P1.(3) évaluation indépendante → §2 · P2.(1) scores de CV → §3, §5 · P2.(2) régularisation → §3 · P2.(3) minimum de CV → sur-apprendre la validation, test. Indices et corrigés : page Devoirs.

Notations du chapitre

Symbole	Se lit / signifie	Nature	Où
Données et loi
$P$	la vraie loi (inconnue) des couples $(x,y)$ ; $\mathcal D$ au chapitre 2, $p(x,y)$ au chapitre 1	loi	partout
$S\sim P^N$	l'échantillon d'entraînement : $N$ tirages indépendants de $P$. Aléatoire	ensemble de couples	§1 →
$(x,y)\sim P$	un nouvel exemple, indépendant de $S$	couple	§1 →
$S_{\text{train}},\ S_{\text{val}},\ S_{\text{test}}$	ensembles d'entraînement, de validation, de test	ensembles	§4
$S_{\text{eval}},\ m$	un ensemble d'évaluation indépendant ; sa taille	ensemble ; entier	§2
$S_{\text{dev}},\ S_k,\ K$	données de développement (tout sauf le test) ; $k$-ième pli ; nombre de plis	ensembles ; entier	§5
$f^\star,\ \sigma$	la vraie fonction de notre exemple ($= \E[y\mid x]$) ; l'écart-type du bruit	fonction ; réel	exemple
Modèles et algorithmes
$\mathcal H$	classe d'hypothèses (ex. polynômes de degré $\le d$)	ensemble de fonctions	§1
$d$	degré du polynôme ($M$ dans le HW1)	entier	exemple
$A,\ \hat f = A(S)$	algorithme d'apprentissage ; prédicteur appris sur $S$ (donc aléatoire)	procédure ; fonction	§2
$f^*_{\mathcal H}$	meilleur prédicteur de la classe : $\argmin_{f\in\mathcal H}L(f)$ (fixé)	fonction	§2 (preuve)
$\ell(y,\hat y)$	perte d'un exemple (carrée, 0-1, cross-entropy, hinge…)	réel $\ge0$	partout
$\lambda,\ \Omega(\bw)$	force et forme de la pénalité ($\Omega = \\|\bw\\|^2$ pour ridge)	réel ; fonction	§3
$\psi,\ \Psi$	un hyperparamètre ($d$, $\lambda$, $(C,\sigma)$…) ; la liste des candidats	valeur ; ensemble fini	§4 →
$\hat f_\psi,\ \hat\psi$	modèle entraîné avec $\psi$ ; hyperparamètre sélectionné	fonction ; valeur	§4 →
$\hat f_\psi^{(-k)}$	modèle entraîné sans le pli $k$	fonction	§5
$f_{\text{final}}$	modèle final (éventuellement réajusté sur train ∪ val)	fonction	§4
Erreurs
$L(f)$	erreur de généralisation $\E_{(x,y)\sim P}[\ell(y,f(x))]$ (sans chapeau = vraie, inconnue)	réel	§2 →
$\hL_S(f)$	erreur empirique de $f$ sur l'ensemble $S$ (avec chapeau = calculée sur des données)	réel	§1 →
$\hL_{\text{val}},\ \hL_{\text{test}},\ \hL_{\text{eval}}$	la même chose sur la validation, le test, un ensemble d'évaluation	réels	§2, §4
$L(\hat f)-\hL_S(\hat f)$	écart de généralisation (generalization gap)	réel	§2
$\hL_{\text{CV}}(\psi)$	score de validation croisée : moyenne des $K$ erreurs de validation	réel	§5
$\E_S[\cdot]$	moyenne sur les tirages possibles de l'échantillon $S$ (≠ $\E_{(x,y)\sim P}$, moyenne sur un nouvel exemple)	opérateur	§2

Pièges de notation

$L$ a changé de sens : ici $L(f)$ est l'erreur attendue (vraie), et le chapeau $\hL$ marque l'erreur calculée sur des données. Au chapitre 2, $L(\bw)$ était la somme empirique des pertes.
Deux espérances : $\E_{(x,y)\sim P}$ moyenne sur un nouvel exemple ($f$ fixé) ; $\E_S$ moyenne sur les échantillons d'entraînement possibles (alors $\hat f$ change avec $S$).
Trois « meilleures » fonctions : $f^\star$ (vraie fonction de notre exemple, $= \E[y\mid x]$), $f^*_{\mathcal H}$ (la meilleure de la classe), $\hat f$ (celle qu'on apprend).
$K$ = nombre de plis (au chapitre 2 : nombre de classes). $m$ = taille d'un ensemble d'évaluation (chapitre 2 : la marge ; chapitre 3 : le nombre de contraintes).
$d$ = degré du polynôme (dans les slides du chapitre 1, $d$ était une dimension ; dans le HW1 le degré s'appelle $M$).
$\lambda$ et $C$ vont en sens inverse : grand $\lambda$ = forte régularisation ; grand $C$ = faible régularisation.

L'exemple qui court tout le chapitre

Comme dans les slides, on ajuste des polynômes $f_\bw(x) = \sum_{j=0}^dw_jx^j$ à $N = 24$ points. Notre version (pas exactement celle des slides, mais du même esprit) : $x\sim\mathrm{Unif}[-1,1]$, $y = f^\star(x) + \varepsilon$ avec $f^\star(x) = \sin(2.6x) + 0.4x$ et $\varepsilon\sim\N(0, 0.3^2)$. Comme on connaît la loi $P$, la scène peut calculer l'erreur de généralisation exacte $L(f)$ — ce qui est impossible en vrai, et c'est tout le sujet du chapitre.

1Quel modèle choisir ?

Slides p.3–5 PRML Fig. 1.4 p.7

Où on en est

Acquis

Chapitres 1 à 3 : pour une classe de modèles fixée, on sait trouver les paramètres qui minimisent une erreur d'entraînement.

Il manque

Comment choisir la classe elle-même (degré, $\lambda$, $C$, noyau…) ? Le modèle le plus complexe a toujours la plus petite erreur d'entraînement.

Cette partie

On pose le problème sur l'exemple des slides (degrés 1, 3, 12), puis on rappelle le cadre : ERM, classe $\mathcal H$, données i.i.d.

Trois polynômes (degrés 1, 3, 12), chacun minimisant la MSE d'entraînement dans sa classe. Le degré 12 a la plus petite erreur d'entraînement… mais on sent qu'il ne prédira pas bien un nouveau point. Quelle mesure utiliser pour choisir ?

Rappel — minimisation du risque empirique (ERM)

Étant donné un échantillon d'entraînement $S = \{(x_i,y_i)\}_{i=1}^N$, on choisit $$\hat f\in\argmin_{f\in\mathcal H}\hL_S(f),\qquad \hL_S(f) = \frac1N\sum_{i=1}^N\ell\big(y_i, f(x_i)\big).$$

Les objets en jeu

$\mathcal H$: ensemble de fonctionsLa classe d'hypothèses (hypothesis class) : par ex. tous les polynômes de degré $\le d$. Le choix de $\mathcal H$ est lui-même une décision — c'est le sujet du chapitre.
$\ell(y,\hat y)$: perte $\ge0$Carrée en régression (ch. 1), cross-entropy en logistique (ch. 2), hinge pour les SVM (ch. 3), 0-1 pour compter les erreurs.
$S$: échantillon aléatoireLe jeu d'entraînement. Point clé du chapitre : $S$ est aléatoire (un autre tirage donnerait d'autres points), donc $\hat f$ aussi.
$\hL_S(f)$: nombreLe risque empirique de $f$ mesuré sur $S$.
$\hat f = A(S)$: fonction appriseLe résultat de l'algorithme d'apprentissage $A$ appliqué à $S$ (moindres carrés, GD, SMO…).

Le cadre i.i.d.

$S = \{(x_i,y_i)\}_{i=1}^N\sim P^N$ et un nouvel exemple $(x,y)\sim P$, indépendant de $S$. Les exemples d'entraînement et le nouvel exemple suivent la même loi $P$, qui décrit à la fois les entrées et l'incertitude sur les étiquettes. En général $P$ est inconnue. (On suppose ici la même loi à l'entraînement et à l'évaluation — pas de distribution shift.)

Les objets en jeu

$P$: loi sur $\mathcal X\times\mathcal Y$La vraie loi des couples (entrée, étiquette) — la « vraie loi jointe $p(x,y)$ » du chapitre 1. Dans l'exemple : $x$ uniforme sur $[-1,1]$, puis $y$ gaussien autour de $f^\star(x)$.
$P^N$: loi d'un échantillon$N$ tirages indépendants de $P$ : c'est ce que signifie « i.i.d. ».
« indépendant de $S$ »: hypothèseLe nouvel exemple n'a pas servi à l'entraînement. Toute la difficulté de l'évaluation vient du fait que les données d'entraînement, elles, ne sont pas indépendantes de $\hat f$.

2Erreur de généralisation, erreur d'entraînement, écart

Slides p.6–9

Où on en est

Acquis

L'ERM choisit $\hat f$ en minimisant l'erreur d'entraînement $\hL_S$.

Il manque

Une mesure de ce qu'on veut vraiment : la performance sur des exemples nouveaux.

Cette partie

On définit l'erreur de généralisation $L(f)$, on montre que $\hL_S(\hat f)$ la sous-estime (optimisme), et qu'avec des données indépendantes on retrouve une estimation sans biais.

Erreur de généralisation (expected error, risk)

Pour un prédicteur $f$ : $$L(f) := \E_{(x,y)\sim P}\big[\ell(y, f(x))\big].$$ Régression avec perte carrée : $L(f) = \E[(y-f(x))^2]$ ; classification avec perte 0-1 : $L(f) = \Pr(f(x)\ne y)$. Le but de l'apprentissage est un $f$ de petit $L(f)$ — mais $P$ étant inconnue, on ne peut ni calculer ni minimiser $L$ directement.

Erreur empirique, erreur de généralisation, écart de généralisation

$$\text{empirique : } \hL_S(\hat f) = \frac1N\sum_{i=1}^N\ell\big(y_i,\hat f(x_i)\big),\qquad \text{généralisation : } L(\hat f) = \E_{(x,y)\sim P}\big[\ell(y,\hat f(x))\big],\qquad \text{écart : } L(\hat f) - \hL_S(\hat f).$$ Calculée sur l'ensemble d'entraînement, l'erreur empirique s'appelle erreur d'entraînement. Un grand écart positif signifie que l'erreur d'entraînement est optimiste. Un petit écart n'implique pas une petite erreur de généralisation (un modèle trop simple a un petit écart… et deux erreurs élevées).

Les objets en jeu

$L(f)$: nombre (pour $f$ fixé)Moyenne de la perte sur un nouvel exemple tiré de $P$. Pour $f$ fixé, l'espérance porte seulement sur $(x,y)$. Dans l'exemple : $L(f) = \E_x[(f^\star(x)-f(x))^2] + \sigma^2$ (ch. 1, décomposition de la MSE).
$L(\hat f)$: variable aléatoireSi $f = \hat f = A(S)$, alors $L(\hat f)$ dépend du tirage de $S$ : c'est un nombre aléatoire. $\E_S[L(A(S))]$ est sa moyenne sur les échantillons possibles.
$L(\hat f) - \hL_S(\hat f)$: écart de généralisation(generalization gap) De combien l'erreur d'entraînement sous-estime l'erreur sur de nouvelles données.

Pourquoi l'erreur d'entraînement est trop optimiste

Énoncé des slides (p.8)

Pour $\hat f = A(S)$ appris sur $S$, en général $$\E_S\big[\hL_S(A(S))\big]\ne\E_S\big[L(A(S))\big],$$ alors que pour un $f$ fixé, choisi indépendamment de $S$ : $\ \E_S[\hL_S(f)] = L(f)$.

Le prédicteur appris utilise les mêmes données pour s'ajuster et pour être évalué : il peut coller au bruit propre à cet échantillon. La scène tire 400 échantillons $S$ indépendants et, pour chacun, calcule l'erreur d'entraînement de $\hat f = A(S)$ et son erreur de généralisation exacte. À gauche : les deux nuages (et leurs moyennes) ; à droite : le même calcul pour un $f$ fixé à l'avance, où les deux moyennes coïncident.

Preuve — pour $f$ fixé, l'erreur empirique est sans biais

$f$ ne dépend pas de $S$ ; les $(x_i,y_i)$ suivent tous la loi $P$. Linéarité de l'espérance : $\E_S[\hL_S(f)] = \frac1N\sum_{i=1}^N\E\big[\ell(y_i,f(x_i))\big]$.

Chaque terme vaut $\E_{(x,y)\sim P}[\ell(y,f(x))] = L(f)$ (même loi). Donc $\E_S[\hL_S(f)] = \frac1N\cdot N\cdot L(f) = L(f)$.

Où ça casse pour $\hat f$ : si $f = A(S)$, le terme $\ell(y_i, A(S)(x_i))$ fait intervenir $(x_i,y_i)$ deux fois — dans la perte et dans le prédicteur. $(x_i,y_i)$ et $A(S)$ ne sont plus indépendants, et l'égalité « chaque terme vaut $L$ » n'est plus vraie.

∎

Preuve — pour l'ERM, l'erreur d'entraînement est en moyenne $\le$ l'erreur de généralisation hors slides

Soit $f_{\mathcal H}^* = \argmin_{f\in\mathcal H}L(f)$ le meilleur prédicteur de la classe : il est fixé (ne dépend pas de $S$).

$\hat f$ minimise l'erreur empirique sur $\mathcal H$, donc $\hL_S(\hat f)\le\hL_S(f_{\mathcal H}^*)$. En moyenne : $\E_S[\hL_S(\hat f)]\le\E_S[\hL_S(f_{\mathcal H}^*)] = L(f_{\mathcal H}^*)$ (preuve précédente).

$\hat f\in\mathcal H$ donc $L(\hat f)\ge L(f_{\mathcal H}^*)$, et $\E_S[L(\hat f)]\ge L(f_{\mathcal H}^*)$.

Conclusion : $\E_S[\hL_S(\hat f)]\le L(f_{\mathcal H}^*)\le\E_S[L(\hat f)]$. L'erreur d'entraînement de l'ERM est optimiste en moyenne, et ceci pour n'importe quelle perte et n'importe quelle classe.

∎

Exemple chiffré (réponse à « Can you give an example? », slide 8) Hors slides. Moindres carrés avec $p$ paramètres, entrées fixées, bruit de variance $\sigma^2$ et vraie fonction dans la classe : $\E[\text{MSE d'entraînement}] = \sigma^2\big(1 - \frac pN\big)$ alors que l'erreur sur de nouvelles sorties aux mêmes entrées vaut $\sigma^2\big(1 + \frac pN\big)$. Avec $p = N$ (interpolation) l'erreur d'entraînement vaut 0 quel que soit le bruit. Cas extrême encore plus simple : un modèle qui mémorise les étiquettes (« table de consultation ») a une erreur d'entraînement nulle et ne prédit rien de mieux que le hasard ailleurs.

Preuve — $\E[\text{MSE train}] = \sigma^2(1 - p/N)$

$\by = \bPhi\bw^\star + \boldsymbol\varepsilon$, $\E[\boldsymbol\varepsilon] = 0$, $\E[\boldsymbol\varepsilon\boldsymbol\varepsilon\T] = \sigma^2\bI$. Le résidu des moindres carrés est $\by - \bP\by = (\bI-\bP)\by$ avec $\bP = \bPhi(\bPhi\T\bPhi)^{-1}\bPhi\T$ (ch. 1, projection).

$(\bI-\bP)\bPhi = 0$ donc le résidu vaut $(\bI-\bP)\boldsymbol\varepsilon$, et $\|(\bI-\bP)\boldsymbol\varepsilon\|^2 = \boldsymbol\varepsilon\T(\bI-\bP)\boldsymbol\varepsilon$ ($\bI-\bP$ est un projecteur symétrique).

$\E[\boldsymbol\varepsilon\T\mathbf A\boldsymbol\varepsilon] = \tr(\mathbf A\,\E[\boldsymbol\varepsilon\boldsymbol\varepsilon\T]) = \sigma^2\tr(\mathbf A)$, et $\tr(\bI-\bP) = N - \tr(\bP) = N - p$ (la trace d'un projecteur = sa dimension).

Donc $\E[\text{MSE train}] = \frac1N\sigma^2(N-p) = \sigma^2(1-\frac pN)$ : en dessous du bruit $\sigma^2$, alors qu'aucun prédicteur ne peut faire mieux que $\sigma^2$ sur de nouvelles données.

∎

Estimer l'erreur de généralisation avec des données indépendantes

Slides p.9

Évaluation sur des données indépendantes

Soient $S\sim P^N$ et $S_{\text{eval}}\sim P^m$ indépendants, et $\hat f = A(S)$. L'erreur d'évaluation $\hL_{\text{eval}}(\hat f) = \frac1m\sum_{(x,y)\in S_{\text{eval}}}\ell(y,\hat f(x))$ vérifie $$\E_{S,S_{\text{eval}}}\big[\hL_{\text{eval}}(A(S))\big] = \E_S\big[L(A(S))\big].$$ Une évaluation donnée peut quand même s'écarter de $L(\hat f)$ car $m$ est fini (écart-type $\propto1/\sqrt m$). Pour une évaluation sans biais, les données d'évaluation ne doivent avoir servi ni à entraîner ni à choisir le modèle.

Preuve — sans biais, et variance en $1/m$

Conditionner par $S$. Une fois $S$ fixé, $\hat f$ est une fonction fixée, et $S_{\text{eval}}$ est indépendant de $S$ donc de $\hat f$. Par la preuve « $f$ fixé » : $\E\big[\hL_{\text{eval}}(\hat f)\mid S\big] = L(\hat f)$.

Moyenner sur $S$ (tower property) : $\E_{S,S_{\text{eval}}}[\hL_{\text{eval}}(\hat f)] = \E_S\big[\E[\hL_{\text{eval}}(\hat f)\mid S]\big] = \E_S[L(\hat f)]$.

Hors slides Précision : sachant $S$, $\hL_{\text{eval}}$ est une moyenne de $m$ pertes i.i.d., donc $\Var(\hL_{\text{eval}}\mid S) = \frac{\Var(\ell)}{m}$. Écart-type $\propto\frac1{\sqrt m}$ : pour diviser l'incertitude par 2, il faut 4 fois plus de données d'évaluation.

∎

3Complexité, sous- et sur-apprentissage

Slides p.11–13 PRML Fig. 1.5 p.8

Où on en est

Acquis

On sait ce qu'il faut viser ($L$) et comment l'estimer honnêtement (données indépendantes).

Il manque

Comprendre quand et pourquoi erreur d'entraînement et de généralisation s'écartent.

Cette partie

Les courbes en fonction de la complexité, de $N$ et de $\lambda$ : sous-apprentissage, sur-apprentissage, et la régularisation comme bouton de réglage.

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

Caltech — Yaser Abu-MostafaLecture 11 - OverfittingCe qu'est vraiment le sur-apprentissage : ajuster le bruit, rôle de N et de la complexité (cours au tableau).▶

StatQuestMachine Learning Fundamentals: Bias and VarianceSous- et sur-apprentissage vus comme biais et variance, en 6 minutes, sans équations.

Sous-apprentissage / sur-apprentissage

Sous-apprentissage (underfitting) : le modèle ajusté manque une structure importante des données (degré 1 trop rigide pour une fonction non linéaire).
Sur-apprentissage (overfitting) : le modèle s'adapte aux fluctuations propres à l'échantillon et fait moins bien sur de nouvelles données (degré 12 : erreur d'entraînement plus basse, prédictions sensibles à l'échantillon particulier).
Le sur-apprentissage ne dépend pas que de la complexité du modèle, mais aussi de la quantité de données et de la régularisation.

La courbe classique : l'erreur d'entraînement ne peut que baisser quand le degré augmente (classes emboîtées), l'erreur de généralisation descend puis remonte. Change $N$ : avec beaucoup plus de données ($N = 200$), le même degré 12 ne sur-apprend presque plus (slide 13).

Preuve — classes emboîtées : l'erreur d'entraînement minimale décroît avec $d$ (slide 11)

Un polynôme de degré $\le d$ est aussi un polynôme de degré $\le d+1$ (coefficient $w_{d+1} = 0$) : $\mathcal H_d\subseteq\mathcal H_{d+1}$.

Minimiser sur un ensemble plus grand donne un minimum plus petit ou égal : $\min_{f\in\mathcal H_{d+1}}\hL_S(f)\le\min_{f\in\mathcal H_d}\hL_S(f)$.

Rien de tel pour $L$ : $\hat f_{d+1}$ est choisi pour coller à $S$, pas pour minimiser $L$. Son erreur de généralisation peut augmenter.

∎

Courbes d'apprentissage Hors slides DL §9.3

Autre façon de lire le rôle de $N$ : fixer le degré et tracer erreurs d'entraînement et de généralisation en fonction de $N$ (moyennées sur de nombreux tirages). Les deux courbes convergent vers la même limite — l'erreur du meilleur modèle de la classe. Modèle simple : elles se rejoignent vite mais haut (biais). Modèle complexe : elles finissent plus bas, mais il faut beaucoup de données pour fermer l'écart (variance).

La régularisation contrôle le modèle ajusté

Slides p.14–15 Ridge, chapitre 1

Minimisation du risque empirique régularisé

$$\hat\bw_\lambda\in\argmin_\bw\Big\{\hL_{\text{train}}(f_\bw) + \lambda\,\Omega(\bw)\Big\},\qquad\lambda\ge0.$$ Ridge : $\Omega(\bw) = \|\bw\|^2$ (en général sans l'ordonnée à l'origine $w_0$). $\lambda$ grand : régularisation forte, coefficients petits, risque de manquer des motifs utiles (sous-apprentissage). $\lambda$ petit : ajustement plus fidèle aux données… et au bruit (sur-apprentissage). Pour la SVM, $\frac12\|\bw\|^2 + C\sum_i\ell_i$ : un $C$ plus grand met plus de poids sur l'ajustement aux données (c'est l'inverse de $\lambda$).

Les objets en jeu

$\Omega(\bw)$: pénalité $\ge0$Mesure de « complexité » des paramètres : $\|\bw\|^2$ (ridge), $\|\bw\|_1$ (lasso)…
$\lambda$: hyperparamètreRègle le compromis ajustement / simplicité. Il ne peut pas être choisi en minimisant l'erreur d'entraînement (on prendrait toujours $\lambda = 0$) — ni avec la courbe de population, inconnue. Quelles données doivent guider ce choix ? → section suivante.

Degré fixé à 12, $\lambda$ variable : la courbe de généralisation est en U en fonction de $\lambda$ (slide 15).

4Sélection de modèle et évaluation

Slides p.17–22 PRML §1.3 p.32

Où on en est

Acquis

Le bon degré ou le bon $\lambda$ dépend des données, et on ne peut pas utiliser $L$ (inconnue) pour le choisir.

Il manque

Une procédure honnête pour choisir les réglages, puis annoncer une performance.

Cette partie

Paramètres vs hyperparamètres, sélection sur un ensemble de validation, le piège du sur-apprentissage de la validation, et le rôle du test.

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

deeplizardTrain, Test, & Validation Sets explainedLe rôle de chacun des trois ensembles, en quelques minutes.▶

Caltech — Yaser Abu-MostafaLecture 13 - ValidationPourquoi l'erreur de validation est sans biais, puis optimiste dès qu'on s'en sert pour choisir ; introduit aussi la validation croisée.

Paramètres et hyperparamètres

Modèle	Paramètres (appris par l'entraînement)	Hyperparamètres (choisis par la sélection)
Régression polynomiale	coefficients $\bw$	degré $d$
Ridge	coefficients $\bw$	pénalité $\lambda$
SVM	$\bw, b$ ou coefficients duaux $\boldsymbol\alpha$	$C$, noyau, largeur $\sigma$ du noyau

Les objets en jeu

paramètres: ajustés par $A$Ce que l'entraînement calcule pour un modèle et une procédure donnés (le $\bw$ des moindres carrés, les $\alpha_i$ du dual…).
$\psi\in\Psi$: hyperparamètre, ensemble de candidatsCe qui définit la classe de modèles, la régularisation ou la procédure ($\psi = d$, $\lambda$, $(C,\sigma)$…). $\Psi$ est la liste finie de candidats qu'on compare.
$\hat f_\psi$: prédicteurLe modèle entraîné avec l'hyperparamètre $\psi$ : $\hat f_\psi = \mathrm{Train}(S_{\text{train}};\psi)$.

Les hyperparamètres sont aussi choisis à partir de données — donc leur sélection peut, elle aussi, sur-apprendre.

Sélection par un ensemble de validation

Ajuster chaque candidat, puis sélectionner

$$\hat f_\psi = \mathrm{Train}(S_{\text{train}};\psi),\qquad \hat\psi\in\argmin_{\psi\in\Psi}\hL_{\text{val}}(\hat f_\psi).$$ $S_{\text{train}}$ et $S_{\text{val}}$ sont indépendants ; tous les candidats sont ajustés sur l'entraînement et comparés sur la validation avec une même métrique.

Peut-on publier l'erreur de validation du modèle choisi comme évaluation finale ? Non : elle sous-estime l'erreur de généralisation, parce que le modèle a été choisi avec ces mêmes données de validation.

Sur-apprendre l'ensemble de validation

Slides p.19

Simulation des slides : 100 candidats tous aussi bons (vraie erreur 20 %), évalués chacun sur 100 exemples de validation. Le hasard seul fait apparaître un « meilleur » candidat à ~11 %. Un modèle peut être choisi parce qu'il a eu de la chance sur la validation — il faut des données fraîches pour l'évaluation finale.

Preuve — le minimum des erreurs de validation est biaisé vers le bas

Notons $V_k$ l'erreur de validation du candidat $k$. Pour un candidat fixé, $\E[V_k] = L(\hat f_k)$ (section 2 : sans biais).

Pour tout $j$ : $\min_kV_k\le V_j$. En prenant l'espérance : $\E[\min_kV_k]\le\E[V_j] = L(\hat f_j)$, pour tout $j$, donc $\E[\min_kV_k]\le\min_jL(\hat f_j)$.

L'inégalité est stricte dès que les $V_k$ fluctuent : le minimum d'estimations bruitées est en moyenne plus petit que le minimum des vraies valeurs. Plus il y a de candidats (et plus $m$ est petit), plus le biais est fort.

∎

Entraînement, validation, test

Ensemble	Rôle	Ce qu'il détermine
Entraînement (training)	ajuster chaque candidat	les paramètres
Validation	comparer les candidats	le modèle / les hyperparamètres
Test	évaluer le modèle final	la performance publiée

Mettre le test de côté avant d'ajuster ou de sélectionner quoi que ce soit.
La validation peut guider le développement du modèle, dont le choix des hyperparamètres.
Régler sur le test puis publier son score comme évaluation indépendante, c'est « tricher ». Ce qui compte est l'usage des données, pas le nom du fichier.

La procédure complète (slide 22)

$$\text{Ajuster : }\hat f_\psi = \mathrm{Train}(S_{\text{train}};\psi)\ \ \to\ \ \text{Sélectionner : }\hat\psi\in\argmin_\psi\hL_{\text{val}}(\hat f_\psi)\ \ \to\ \ \text{Réajuster (option) : }f_{\text{final}} = \mathrm{Train}(S_{\text{train}}\cup S_{\text{val}};\hat\psi)\ \ \to\ \ \text{Évaluer : }\hL_{\text{test}}(f_{\text{final}}).$$ Fixer les hyperparamètres et la procédure de réajustement avant de regarder le test. Sans réajustement, $f_{\text{final}} = \hat f_{\hat\psi}$.

Trainajuster chaque $\psi\in\Psi$

→

Validationchoisir $\hat\psi$

→

Réajuster(option) sur train ∪ val

→

Testune seule fois, à la fin

L'exemple de la slide 21 est exactement ce que fait la scène de validation ci-dessus : 24 exemples d'entraînement, 100 de validation, degré choisi par la MSE de validation, réajustement sur les 124, puis MSE sur 1000 exemples de test jamais touchés.

5Validation croisée

Slides p.24–27 PRML §1.3 (Fig. 1.18)

Où on en est

Acquis

La procédure train / validation / test.

Il manque

Avec peu de données, une seule validation gaspille des exemples et donne un choix instable.

Cette partie

Faire tourner l'ensemble de validation sur $K$ plis et moyenner : la validation croisée, et quand la préférer au holdout.

▶ Vidéosen anglais · s'ouvrent sur YouTube

▶

StatQuestMachine Learning Fundamentals: Cross ValidationLe principe des K plis, très visuel.▶

Stanford Online — Andrew NgStanford CS229 Lecture 8 - Data Splits, Models & Cross-ValidationTrain / dev / test, holdout, K-fold et leave-one-out, par Andrew Ng.

Pourquoi ? Avec peu de données, une grande validation laisse peu d'exemples pour l'entraînement, et une petite validation donne des estimations bruitées. Et le classement des modèles peut changer avec le découpage train/validation. L'idée : faire tourner l'ensemble de validation et moyenner.

Validation croisée à $K$ plis (K-fold cross-validation)

On découpe les données de développement $S_{\text{dev}}$ (tout sauf le test) en $K$ plis de même taille $S_1,\dots,S_K$. Pour chaque candidat $\psi$ : $$\hL_{\text{CV}}(\psi) = \frac1K\sum_{k=1}^K\hL_{S_k}\big(\hat f_\psi^{(-k)}\big),\qquad\hat f_\psi^{(-k)} = \mathrm{Train}(S_{\text{dev}}\setminus S_k;\psi),\qquad\hat\psi\in\argmin_{\psi\in\Psi}\hL_{\text{CV}}(\psi).$$ Puis on entraîne un modèle final sur toutes les données de développement, et on l'évalue sur le test intact. Le minimum du score CV sert à sélectionner et peut lui aussi être optimiste.

Les objets en jeu

$S_{\text{dev}}$: données de développementTout ce qui n'est pas le test. Le test reste en dehors de tous les plis.
$S_k$: $k$-ième pliSert de validation au tour $k$ ; les $K-1$ autres servent à l'entraînement.
$\hat f_\psi^{(-k)}$: prédicteurEntraîné sans le pli $k$ (« moins $k$ ») avec l'hyperparamètre $\psi$.
$\hL_{\text{CV}}(\psi)$: score de validation croiséeMoyenne des $K$ erreurs de validation. Chaque exemple est utilisé une fois en validation et $K-1$ fois en entraînement.
$K$: entierTypiquement 5 ou 10. $K = N$ : leave-one-out. Coût : $K$ entraînements par candidat.

Dans la scène : les points sont colorés par pli ; choisis le tour $k$ pour voir quel pli sert de validation ; les courbes fines sont les erreurs par pli, la courbe épaisse leur moyenne (le score CV). Bouton « nouveau découpage » : la courbe holdout (un seul découpage) saute beaucoup plus que la courbe CV.

Pour quantifier la stabilité : on répète 200 découpages aléatoires et on compte quel degré est choisi par une validation simple (holdout) et par la CV à 5 plis. La CV choisit de façon beaucoup plus régulière.

Remarque — preprocessing et fuite d'information (slide 25)

Toute étape qui « apprend » à partir des données (normalisation : moyenne et écart-type ; sélection de features…) fait partie de l'entraînement : elle doit être réajustée dans chaque pli, sur les seuls exemples d'entraînement de ce pli.

Sinon, des statistiques calculées avec le pli de validation « fuient » dans le modèle : l'erreur de validation devient optimiste, exactement comme quand on évalue sur ses données d'entraînement.

∎

Validation simple ou validation croisée ?

	Validation simple (holdout)	$K$-fold CV
Entraînements par candidat	1	$K$
Exemples de validation	un sous-ensemble mis de côté	chaque exemple de développement, une fois
Usage naturel	beaucoup de données / entraînement coûteux	peu de données / réentraînements abordables

Les deux approches ont besoin d'une évaluation finale indépendante (le test).

6Résumé & question de la slide 28

Tout le chapitre en une chaîne

$$\underbrace{\hL_S(\hat f)}_{\text{optimiste (§2)}}\ \ne\ \underbrace{L(\hat f) = \E_{(x,y)\sim P}[\ell(y,\hat f(x))]}_{\text{la cible}}\ \approx\ \underbrace{\hL_{\text{test}}(\hat f)}_{\text{sans biais si indépendant}}$$ $$\underbrace{\hat f_\psi = \mathrm{Train}(S_{\text{train}};\psi)}_{\text{paramètres}}\ \to\ \underbrace{\hat\psi = \argmin_\psi\hL_{\text{val}}(\hat f_\psi)\ \text{ou}\ \argmin_\psi\hL_{\text{CV}}(\psi)}_{\text{hyperparamètres (§4–5)}}\ \to\ \underbrace{\hL_{\text{test}}(f_{\text{final}})}_{\text{une seule fois, à la fin}}$$

Apprentissage et évaluation

But : petite erreur de généralisation $L(f)$ · Entraînement : ajuster les paramètres sur $S_{\text{train}}$ · Sélection : choisir les hyperparamètres par validation ou CV · Évaluation finale : estimer $L(f_{\text{final}})$ sur $S_{\text{test}}$.
Une faible erreur d'entraînement ne garantit pas de bonnes prédictions. Capacité du modèle, régularisation et taille d'échantillon gouvernent sous- et sur-apprentissage. Le test reste indépendant de toutes les décisions d'entraînement et de sélection.

Pour l'exemple polynomial : quelles données choisissent le degré, lesquelles évaluent le prédicteur final ?

Réponse

Le degré (hyperparamètre) est choisi avec les données de validation (ou par validation croisée sur les données de développement) : chaque degré est ajusté sur l'entraînement, comparé sur la validation. Le prédicteur final (éventuellement réajusté sur entraînement + validation) est évalué une seule fois sur le test, mis de côté dès le début et jamais utilisé pour ajuster ni choisir. Utiliser l'erreur de validation du degré choisi comme performance finale serait optimiste (scène « sur-apprendre la validation »).

Pour s'entraîner : exercices à trous (filtre « 4 · sélection »).