Surapprentissage et régularisation

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

• reconnaître le surapprentissage et le sous-apprentissage sur les erreurs d'entraînement et de test d'une famille de modèles de complexité croissante, et expliquer pourquoi l'erreur d'entraînement ne peut que baisser quand le modèle s'enrichit;
• démontrer la décomposition biais–variance de l'erreur quadratique attendue en un point, et la calculer pour une régression polynomiale;
• lire une courbe d'apprentissage et dire si un modèle a besoin de plus de données ou d'un autre modèle;
• écrire la régression ridge avec un biais non pénalisé, démontrer sa forme close et son inversibilité pour $\lambda >0$, et calculer le rétrécissement qu'elle produit sur le jeu A;
• expliquer pourquoi le lasso annule des coefficients et la ridge ne le fait pas, par le calcul et par la géométrie des boules ${\ell }_1$ et ${\ell }_2$;
• choisir $\lambda$ par validation croisée sans toucher à l'ensemble de test, et reconnaître l'arrêt précoce de la descente de gradient comme une autre forme de régularisation.

Quand un modèle apprend trop bien

Le chapitre 1 a posé le problème sans le résoudre. Un modèle choisi pour minimiser son erreur sur les exemples d'entraînement finit par apprendre les accidents de ces exemples: la règle du plus proche voisin avait une erreur d'entraînement nulle sur le jeu B et se trompait pourtant sur trois courriels sur seize dès qu'on la testait honnêtement. La figure 1.2 montrait, de façon schématique, une erreur de test qui passe par un minimum puis remonte quand la flexibilité du modèle augmente. Ce chapitre calcule cette courbe sur un exemple complet, explique d'où vient sa forme, et donne les outils pour se placer au bon endroit.

L'exemple doit réunir trois conditions. Il nous faut une famille de modèles dont la flexibilité se règle par un seul nombre; les polynômes de degré $d$ en sont l'exemple type, et le chapitre 2 a montré qu'ils restent des modèles linéaires en leurs paramètres. Il nous faut ensuite des données dont on connaît la vraie loi, pour pouvoir comparer ce que le modèle apprend à ce qu'il aurait dû apprendre — ce qui est impossible avec les loyers du jeu A, dont personne ne connaît la «vraie» relation. Il nous faut enfin assez peu de données pour que le surapprentissage se voie: c'est quand les exemples sont rares que la tentation de les apprendre par cœur est la plus forte.

Des données dont on connaît la loi

Nous fabriquons donc nos données. Ce sont des données fictives, construites pour le cours, produites par une loi que nous choisissons et que nous énonçons entièrement:

• la caractéristique $x$ est tirée uniformément dans l'intervalle $[-1,1]$, puis arrondie au centième;
• l'étiquette vaut $y=\sin (\pi x)+\epsilon$, où le bruit $\epsilon$ suit une loi normale de moyenne $0$ et d'écart type $\sigma =0,25$ (Probabilités et statistique, chapitre 6), indépendamment d'un exemple à l'autre; $y$ est arrondi au centième;

La fonction $f(x)=\sin (\pi x)$ est la fonction de régression: c'est ce qu'un modèle parfait devrait prédire, $f(x)=\mathbb{E}[y\mid x]$. La variance du bruit, ${\sigma }^2=0,0625$, est l'erreur quadratique qu'aucun modèle ne peut éviter, puisque même $f$ elle-même se trompe en moyenne de sur un nouvel exemple. Gardez ce nombre en tête: c'est le plancher de toutes les erreurs de test de ce chapitre. Le choix d'une sinusoïde n'est pas original; c'est, à un changement de variable près, l'exemple par lequel Bishop ouvre son manuel, et il a l'avantage de ne pas être un polynôme, de sorte qu'aucun degré ne la reproduit exactement.

import math, random

def generer(n, sigma=0.25):
    """n tirages: x uniforme sur [-1, 1], y = sin(pi x) + bruit gaussien."""
    points = []
    for _ in range(n):
        x = round(random.uniform(-1, 1), 2) + 0.0   # + 0.0 change -0.0 en 0.0
        y = round(math.sin(math.pi * x) + random.gauss(0, sigma), 2

Les douze exemples d'entraînement sont les suivants; c'est sur eux seuls que les modèles seront ajustés.

Pour les programmes du chapitre, ils s'écrivent ainsi; la liste test, de soixante couples, est recopiée dans les exercices qui en ont besoin.

# Données fictives: random.seed(351), y = sin(pi x) + bruit N(0; 0,25^2).
entrainement = [
    (0.72, 0.57), (-0.46, -1.09), (1.0, -0.08), (-0.56, -0.72),
    (-0.06, -0.14), (0.32, 1.25), (0.71, 0.74), (0.52, 0.39),

Le degré $d$ est un hyperparamètre: il n'est pas appris par les moindres carrés, il est fixé avant eux, et il règle à lui seul la flexibilité du modèle. Le degré 0 est le prédicteur constant du chapitre 1; le degré 1 est la droite du chapitre 2; chaque degré supplémentaire ajoute une colonne à $\tilde{X}$ et un paramètre à $\mathbf{\theta }$. Nous gardons $x$ dans $[-1,1]$ précisément pour que les puissances $x^j$ restent du même ordre de grandeur que $x$; sur une surface en m², dépasserait et les équations normales seraient numériquement inutilisables — c'est le problème de conditionnement du chapitre 3, en pire.

La figure 6.1 est la version calculée de la figure 1.2. L'échelle logarithmique est indispensable: les erreurs de test couvrent plus de deux décades, et une échelle linéaire écraserait toute la zone intéressante contre l'axe. On y voit aussi ce que le tableau suggérait: le segment des degrés 3 à 6 est presque plat. Plusieurs modèles sont aussi bons les uns que les autres, et rien n'impose de choisir le plus complexe d'entre eux; en cas d'égalité, on préfère le plus simple.

Sur nos données, les degrés 0 à 2 sont en sous-apprentissage: leur erreur d'entraînement, entre $0,21$ et $0,44$, est déjà très au-dessus du plancher, et leur erreur de test l'est un peu plus. À partir du degré 7, le modèle surapprend: l'erreur d'entraînement continue de baisser, l'erreur de test monte. L'écart entre les deux erreurs est le signal à surveiller; au degré 3 il vaut $0,0775-0,0563=0,0212$, au degré 9 il dépasse $4,4$.

Démonstration. Un polynôme de degré au plus $d$ est aussi un polynôme de degré au plus $d+1$, dont le coefficient de $x^{d+1}$ est nul. La famille des modèles de degré $d+1$ contient donc celle des modèles de degré $d$, et le minimum du risque empirique sur une famille plus grande est inférieur ou égal au minimum sur la plus petite: $E_{d+1}\le E_d$. Pour la seconde affirmation, prenons : la matrice est alors carrée, de taille , et c'est une matrice de Vandermonde, dont le déterminant est non nul quand les sont distincts (Algèbre linéaire, chapitre 3). Le système a donc une solution, qui annule tous les résidus: le polynôme les données, et . Pour , la monotonie donne .

Le théorème dit pourquoi l'erreur d'entraînement ne peut pas servir à choisir $d$: elle désignerait toujours le plus grand degré disponible. Il le dit sans aucune hypothèse sur les données — c'est une propriété de l'optimisation, pas du monde. Et il ne dit rien de l'erreur de test, qui dépend de ce que le modèle fait entre les points d'entraînement, là où il n'a reçu aucune information.

Le compromis biais–variance

Pourquoi l'erreur de test remonte-t-elle? Le polynôme de degré 9 n'est pas «mauvais» en soi: la sinusoïde est très bien approchée par un polynôme de degré 9 sur $[-1,1]$. Le problème est que, avec douze points bruités, les moindres carrés ne trouvent pas ce bon polynôme; ils en trouvent un qui dépend fortement du bruit particulier de ces douze points. Tiré avec d'autres graines, le même procédé donnerait des polynômes très différents. Pour rendre cette intuition précise, il faut regarder le prédicteur appris comme une variable aléatoire: il dépend de l'échantillon d'entraînement, lui-même aléatoire.

Fixons le cadre. Les exemples suivent le modèle

où $f$ est la fonction de régression, inconnue. Une méthode d'apprentissage — par exemple «moindres carrés sur les polynômes de degré 9» — associe à tout ensemble d'entraînement $\mathcal{D}$ un prédicteur ${\hat{f}}_{\mathcal{D}}$. Comme $\mathcal{D}$ est aléatoire, la prédiction ${\hat{f}}_{\mathcal{D}}(\mathbf{x})$ en un point fixé est une variable aléatoire, dont on peut calculer l'espérance et la variance.

Le biais mesure une erreur systématique: même avec une infinité d'ensembles d'entraînement dont on ferait la moyenne des prédictions, une droite ne suivra jamais une sinusoïde. La variance mesure une erreur d'instabilité: un modèle très flexible suit le bruit de chaque échantillon, et ses prédictions changent d'un échantillon à l'autre même si, en moyenne, elles visent juste.

Démonstration. Allégeons l'écriture: $\hat{f}={\hat{f}}_{\mathcal{D}}(\mathbf{x})$, $\bar{f}=\bar{f}(\mathbf{x})$ et ; seuls et sont aléatoires. Écrivons l'erreur comme une somme de trois termes, en ajoutant et retranchant et :

Le carré d'une somme de trois termes est la somme des trois carrés et des trois doubles produits. Prenons l'espérance de chacun des six termes.

• $\mathbb{E}[{\epsilon }^2]=\mathrm{Var}[\epsilon ]+\mathbb{E}[\epsilon {]}^2={\sigma }^2$.
• $(f-\bar{f}{)}^2$ n'est pas aléatoire: son espérance est lui-même, le biais au carré.

Il reste exactement les trois termes de (6.2). $\square$

La démonstration ressemble à celle du théorème 1.2, et ce n'est pas un hasard: dans les deux cas on décompose un écart quadratique autour d'une moyenne, et les doubles produits s'annulent parce que les écarts à la moyenne sont, en moyenne, nuls. Le premier terme, ${\sigma }^2$, est l'erreur irréductible: aucune méthode ne peut descendre en dessous. Les deux autres dépendent de la méthode, et ils tirent en sens contraires. Un modèle rigide a un biais élevé et une variance faible: il se trompe toujours de la même façon. Un modèle flexible a un biais faible et une variance élevée: il vise juste en moyenne mais se disperse. Réduire l'un augmente en général l'autre, et le meilleur modèle est celui qui minimise leur somme — d'où le nom de compromis biais–variance (bias–variance trade-off).

Pour calculer ces termes, il faut connaître $f$, ce qui n'arrive jamais en pratique — et c'est pourquoi nous avons fabriqué nos données. Pour la régression polynomiale, le calcul est même exact, sans simulation, si l'on fixe les abscisses d'entraînement et que seul le bruit est redessiné: c'est le cadre du plan fixe (fixed design). La prédiction en un point $x_0$ s'écrit

une fonction linéaire de $\mathbf{y}$. Avec $\mathbf{y}=\mathbf{f}+\mathbf{\epsilon }$, où $\mathbf{f}=(f(x_1),\dots ,f(x_n))$ et de covariance , la linéarité de l'espérance donne — c'est le polynôme qu'on ajusterait aux valeurs —, et la règle (Probabilités et statistique, chapitre 7) donne

Courbes d'apprentissage

La figure 6.1 fait varier la complexité du modèle à données fixées. On peut aussi faire l'inverse: fixer le modèle et faire varier la quantité de données. Cette seconde lecture répond à une question très pratique, que tout projet finit par poser: vaut-il la peine de collecter plus d'exemples?

Le calcul suivant les produit pour les degrés 1, 3 et 7, sur des données tirées selon la même loi que celles du chapitre. Le générateur est initialisé par random.seed(2026); on tire d'abord un ensemble de test de 2 000 points, puis, pour chaque taille $n$, deux cents ensembles d'entraînement indépendants de taille $n$, dont on fait la moyenne des erreurs.

Pour le degré 7, la dernière colonne donne la médiane des deux cents erreurs de test, et non leur moyenne: avec douze points, quelques ensembles d'entraînement laissent de grands trous dans $[-1,1]$, le polynôme s'y envole, et la moyenne des deux cents erreurs de test atteint environ $2,19$ millions. Une seule valeur extrême suffit à rendre la moyenne inutilisable; c'est l'exemple 1.2 sur la robustesse de la médiane, à une autre échelle.

Les deux colonnes de chaque degré convergent l'une vers l'autre. L'erreur d'entraînement monte avec $n$: plus il y a de points, plus il est difficile de tous les suivre. L'erreur de test descend: plus il y a de points, moins le modèle dépend du bruit de chacun. Et les deux tendent vers une même limite, qui est l'erreur du meilleur modèle de la famille: ${\sigma }^2$ plus le biais au carré de la meilleure approximation de $\sin (\pi x)$ par un polynôme de ce degré. Un calcul d'intégrales (exercice 6.3) donne $0,0625+0,19604=0,2585$ pour le degré 1; le même calcul fait numériquement donne $0,0669$ pour le degré 3 et pour le degré 7, dont le biais est négligeable.

Ces courbes servent au diagnostic.

• Le degré 1 est limité par son biais. Dès $n=48$, ses deux erreurs sont proches l'une de l'autre et proches de leur limite $0,2585$, quatre fois le plancher. Doubler, quadrupler les données ne servira presque à rien: l'erreur de test passe de $0,2749$ à $0,2648$ entre 48 et 192 exemples. Il faut un modèle plus flexible.
• Le degré 7 est limité par sa variance quand les données sont rares. Avec douze points, l'écart entre entraînement et test est énorme; avec 192 points, son erreur de test ($0,0663$) est la meilleure des trois. Pour lui, plus de données est exactement le bon remède.
• Le degré 3 est au milieu: un écart de $0,0872$ à $n=12$, de à , et une limite à peine au-dessus du plancher.

La régularisation ridge

L'exemple 6.1 a montré le symptôme du surapprentissage sur les coefficients: au degré 9, des termes de plusieurs centaines de signes opposés qui se compensent aux points d'entraînement et s'emballent entre eux. L'exemple 6.2 en a donné le diagnostic: une variance énorme. On pourrait réduire le degré, mais c'est un réglage grossier — on passe de 10 paramètres à 4 d'un coup. La régularisation propose un réglage continu: garder le modèle riche, mais lui interdire les grands coefficients, en ajoutant au critère des moindres carrés un terme qui les pénalise.

Deux remarques sur cette définition. La première porte sur l'échelle. Le premier terme est une somme de carrés, et non la moyenne $\hat{R}$: on a $J_{\lambda }=n\hat{R}+\lambda \Vert \mathbf{w}{\Vert }^2$, et minimiser $J_{\lambda }$ revient à minimiser . Les deux conventions existent dans la littérature et dans les bibliothèques; elles ne diffèrent que par un facteur sur , mais ce facteur change la valeur numérique du «bon» . Nous gardons la somme, qui donne la forme close la plus simple.

La seconde porte sur le biais. Pénaliser $w_0$ tirerait toutes les prédictions vers $0$, ce qui n'a aucun sens: un loyer de CHF 1 902,50 ou une température de 280 kelvins n'ont aucune raison d'être «petits». Ce que l'on veut contrôler, c'est la sensibilité du modèle aux caractéristiques — la pente, l'ondulation —, pas son niveau moyen. D'ailleurs, si l'on pénalisait $w_0$, déplacer toutes les étiquettes de 1 000 changerait la forme de l'ajustement, ce qui serait absurde.

Démonstration. Posons $M={\tilde{X}}^{\top }\tilde{X}+\lambda I^{\prime }$. Elle est symétrique, comme somme de deux matrices symétriques. Pour tout $\mathbf{v}=(v_0,v_1,\dots ,v_d)\in {\mathbb{R}}^{d+1}$,

Supposons ${\mathbf{v}}^{\top }M\mathbf{v}=0$. Les deux termes sont positifs, donc nuls tous les deux. Comme $\lambda >0$, le second impose $v_1=\cdots =v_d=0$. Le premier impose alors ; or , puisque seule la colonne de uns subsiste, et force . Donc pour tout : est définie positive (Algèbre linéaire, chapitre 11). Elle est inversible, car entraînerait , donc .

Développons maintenant le coût. Avec $\Vert \mathbf{y}-\tilde{X}\mathbf{\theta }{\Vert }^2={\mathbf{y}}^{\top }\mathbf{y}-2{\mathbf{\theta }}^{\top }{\tilde{X}}^{\top }\mathbf{y}+{\mathbf{\theta }}^{\top }{\tilde{X}}^{\top }\tilde{X}\mathbf{\theta }$, on obtient

Soit $\hat{\mathbf{\theta }}=M^{-1}{\tilde{X}}^{\top }\mathbf{y}$, de sorte que $M\hat{\mathbf{\theta }}={\tilde{X}}^{\top }\mathbf{y}$. En complétant le carré, et en utilisant la symétrie de ,

Le dernier terme ne dépend pas de $\mathbf{\theta }$, et le premier est strictement positif sauf en $\mathbf{\theta }=\hat{\mathbf{\theta }}$, puisque $M$ est définie positive. Le minimum est donc atteint en $\hat{\mathbf{\theta }}$ et seulement là. On retrouve la même équation en annulant le gradient $\nabla J_{\lambda }(\mathbf{\theta })=-2{\tilde{X}}^{\top }(\mathbf{y}-\tilde{X}\mathbf{\theta })+2\lambda I^{\prime }\mathbf{\theta }$ (annexe A).

Le chapitre 2 avait laissé une question ouverte: que faire quand ${\tilde{X}}^{\top }\tilde{X}$ est singulière, parce que deux caractéristiques sont colinéaires ou qu'il y a plus de paramètres que d'exemples? La ridge y répond. Pour $\lambda =0$, les moindres carrés ont alors une infinité de solutions; pour tout $\lambda >0$, il y en a exactement une. Nous en aurons besoin à la section sur la validation croisée: un polynôme de degré 9 a dix paramètres, et une validation croisée à quatre plis ne lui laissera que neuf exemples pour l'ajuster.

La ridge sur les loyers

Sur une seule caractéristique, la forme close se lit sans inverser de matrice. Écrivons $\bar{x}$ et $\bar{y}$ les moyennes, et

Annuler la dérivée de $J_{\lambda }$ par rapport à $w_0$ donne ${\sum }_i(y_i-w_0-w_1{x}_i)=0$, soit — exactement la même condition que pour les moindres carrés, puisque n'est pas pénalisé: . En reportant, devient , minimal en

La pente des moindres carrés est multipliée par le facteur de rétrécissement (shrinkage) $S_{xx}/(S_{xx}+\lambda )$, compris entre $0$ et $1$. Quand $\lambda \to \infty$, la pente tend vers $0$ et la droite vers la constante : le prédicteur constant du chapitre 1.

Cette dernière observation a une conséquence pratique importante. La pénalité $\lambda w_1^2$ dépend de l'unité de $x$: mesurer la surface en dm² plutôt qu'en m² divise $w_1$ par 100 et sa pénalité par 10 000, à $\lambda$ fixé. Avec plusieurs caractéristiques d'unités différentes, une même valeur de $\lambda$ pénaliserait donc très inégalement les poids: une caractéristique exprimée en grandes unités prend de petites valeurs numériques, demande un grand poids pour avoir un effet, et ce grand poids est lourdement pénalisé; une caractéristique exprimée en petites unités s'en tire à bon compte. Le remède est de les caractéristiques avant de régulariser, comme on le faisait au chapitre 3 pour la descente de gradient.

La ridge sur les polynômes

Revenons au degré 9, celui dont l'erreur de test valait $4,4147$. Gardons ce degré et faisons varier $\lambda$, avec la forme close (6.4); comme $x\in [-1,1]$, les caractéristiques $x^j$ ont des échelles comparables, et nous ne les standardisons pas.

Une pénalité minuscule, $\lambda =10^{-6}$, suffit à diviser l'erreur de test par près de quatre: les coefficients géants du degré 9 coûtaient très peu en erreur d'entraînement, et il suffit d'un rien pour qu'ils ne vaillent plus la peine. À $\lambda =0,001$, l'erreur de test vaut $0,0810$, presque celle du meilleur degré non régularisé ($0,0775$), avec un polynôme de degré 9 dont la norme des poids a été divisée par plus de soixante. Au-delà, la pénalité écrase le modèle: à $\lambda =100$, l'erreur de test, , approche celle du prédicteur constant, , et les poids sont presque nuls. L'erreur d'entraînement, elle, augmente à chaque colonne: c'est l'image miroir du théorème 6.1, puisque augmenter restreint le modèle.

La figure 6.2 refait le calcul exact de l'exemple 6.2, mais cette fois en faisant varier $\lambda$ au lieu du degré. Pour la ridge, la prédiction reste linéaire en $\mathbf{y}$: avec $M_{\lambda }={\tilde{X}}^{\top }\tilde{X}+\lambda I^{\prime }$, on a et . Le compromis y est lisible d'un seul coup d'œil: la régularisation une baisse de variance en un peu de biais. Tant que la variance baisse plus vite que le biais ne monte, l'erreur attendue diminue. L'erreur attendue minimale vaut à sur la grille de la figure, contre sans régularisation. La ridge introduit délibérément un biais — c'est un estimateur — et c'est précisément ce qui la rend meilleure.

L'explorateur rend ce compromis visible sur la courbe elle-même. Avec le degré 9 et $\lambda =0$, le polynôme passe tout près des douze disques et part en oscillations entre eux et vers les bords, là où les points d'entraînement manquent; les croix de test, qui tombent justement dans ces zones, ne sont pas suivies. Faites glisser $\lambda$ d'un ou deux crans: les oscillations disparaissent, la courbe rejoint la sinusoïde, et l'erreur de test chute alors que l'erreur d'entraînement monte un peu. Poussez $\lambda$ jusqu'à 100: la courbe s'aplatit sur la moyenne des étiquettes, $-0,0525$. Essayez aussi le degré 11 avec $\lambda =0$, qui interpole exactement les douze points, puis avec $\lambda =0,001$.

Le lasso et la parcimonie

La ridge rétrécit tous les poids, mais elle n'en annule aucun: dans la formule $S_{xy}/(S_{xx}+\lambda )$, la pente ne vaut zéro que si $S_{xy}=0$, c'est-à-dire si elle était déjà nulle. Or on aimerait souvent un modèle qui ses caractéristiques: sur deux cents mesures possibles d'un patient, dire lesquelles comptent. Il suffit pour cela de changer de norme.

Le coût du lasso est convexe, mais il n'est pas dérivable là où un poids s'annule, et il n'a pas de forme close en général: on le minimise par des méthodes itératives, la plus courante étant la descente par coordonnées (coordinate descent), qui optimise un poids à la fois. Dans un cas particulier, pourtant, tout se calcule, et ce cas suffit à voir d'où viennent les zéros.

Démonstration. Développons la somme des carrés. Avec $r_i=y_i-w_0$,

Comme les colonnes sont centrées, ${\sum }_i{x}_{ij}{r}_i={\sum }_i{x}_{ij}{y}_i-w_0{\sum }_i{x}_{ij}=c_j$. Comme elles sont orthogonales, les doubles produits du dernier terme disparaissent: . Le coût se donc en une somme de termes qui ne dépendent chacun que d'un paramètre:

avec $\text{peˊn}(w)=\lambda w^2$ pour la ridge et $\lambda |w|$ pour le lasso. On minimise chaque terme séparément. Le premier est minimal en $w_0=\bar{y}$ (théorème 1.2). Pour la ridge, est une parabole de sommet .

Pour le lasso, supposons d'abord $c_j>\lambda /2$. Sur $]0,\infty [$, $g_j^{\prime }(w)=2s_{j}w-2c_j+\lambda$ s'annule en , minimum de la parabole restreinte à ce demi-axe; sur , , donc y décroît vers , et . Le minimum est . Le cas est symétrique et donne . Enfin, si , alors pour , , et pour , : décroît jusqu'en puis croît, et son minimum est . Les trois cas s'écrivent ensemble comme dans (6.6).

La différence entre les deux formules est toute la leçon. La ridge divise $c_j$ par un nombre plus grand: le poids diminue mais ne s'annule jamais. Le lasso retranche $\lambda /2$ à $|c_j|$ et s'arrête à zéro: c'est un seuillage doux (soft thresholding). Toute caractéristique dont la corrélation avec $\mathbf{y}$, mesurée par $|c_j|$, est inférieure au seuil est éliminée, et les autres sont toutes diminuées de la même quantité.

Sur le jeu A en $z$ standardisé, la seule colonne est centrée, donc trivialement orthogonale à elle-même; $s={\sum }_i{z}_i^2=8$ et $c={\sum }_i{z}_i{y}_i=4078,70$. Le lasso donne

La pente baisse linéairement en $\lambda$, au lieu du déclin en $1/(8+\lambda )$ de la ridge, et elle atteint zéro en un $\lambda$ fini: à partir de $\lambda =2c=8157,40$, le lasso déclare que la surface n'apporte rien et prédit le loyer moyen. La ridge, elle, ne le déclarerait jamais.

La géométrie des boules

Il existe une seconde lecture, plus visuelle, de la même différence. Admettons — c'est un résultat d'optimisation sous contrainte, la dualité de Lagrange, que nous ne démontrons pas ici — que minimiser $\Vert \mathbf{y}-\tilde{X}\mathbf{\theta }{\Vert }^2+\lambda \Vert \mathbf{w}\Vert$ revient, pour un certain rayon $t$ qui dépend de $\lambda$, à minimiser $\Vert \mathbf{y}-\tilde{X}\mathbf{\theta }{\Vert }^2$ . La pénalité devient une boule dont le poids n'a pas le droit de sortir.

La solution contrainte est le point de la boule où l'on touche la plus basse ligne de niveau du coût: on part du minimum sans contrainte $\hat{\mathbf{w}}$, qui est hors de la boule, et l'on dilate les ellipses de niveau jusqu'à ce que l'une d'elles touche la boule. Le disque ${\ell }_2$ est lisse et rond; l'ellipse le touche presque toujours en un point quelconque de son bord, dont aucune coordonnée n'est nulle. Le losange ${\ell }_1$ a des sommets pointus sur les axes; une ellipse qui vient de loin a toutes les chances de le toucher par un sommet, et en un sommet, toutes les coordonnées sauf une sont nulles. En dimension $d$, la boule ${\ell }_1$ a sommets et des arêtes et des faces de toutes dimensions sur lesquelles une partie des coordonnées s'annule: c'est là que se posent les solutions du lasso, et c'est pourquoi elles sont parcimonieuses.

Le lasso n'est pas pour autant toujours préférable. Quand plusieurs caractéristiques sont fortement corrélées, il tend à en garder une et à éliminer les autres, de façon assez arbitraire et instable d'un échantillon à l'autre, là où la ridge répartit le poids entre elles. Et un poids mis à zéro par le lasso ne prouve pas que la caractéristique est sans effet dans le monde: il dit seulement que, sur ces données et avec ce $\lambda$, elle n'apportait pas assez pour payer sa pénalité. Comme pour tout coefficient de régression, en tirer une conclusion causale serait une erreur (chapitre 2).

Choisir $\lambda$ par validation croisée

Le tableau de la ridge de degré 9 donne la meilleure erreur de test pour $\lambda =0,001$. Mais nous l'avons trouvé en regardant l'erreur de test, et le chapitre 1 a dit pourquoi c'est interdit: un hyperparamètre choisi sur le test fait de l'ensemble de test un ensemble de validation, et l'erreur annoncée devient optimiste. Il faut choisir $\lambda$ — comme le degré, comme tout hyperparamètre — sans toucher au test. Avec douze exemples d'entraînement, on ne peut pas se permettre d'en mettre quatre de côté une fois pour toutes; la validation croisée à $k$ plis du chapitre 5 recycle chacun d'eux.

La procédure est la suivante. On découpe l'ensemble d'entraînement en $k$ plis (folds) disjoints de même taille (définition 5.10). Pour chaque valeur candidate de $\lambda$, on ajuste $k$ modèles, chacun sur $k-1$ plis, et l'on mesure chacun sur le pli laissé de côté; l'erreur de validation croisée de $\lambda$ est la moyenne des $k$ erreurs. On retient le $\lambda$ de plus petite erreur de validation croisée, puis l'on réajuste le modèle sur tout l'ensemble d'entraînement avec ce $\lambda$. Ce n'est qu'à la toute fin, une fois, que l'on mesure l'erreur de test.

L'arrêt précoce

Il existe une forme de régularisation que l'on pratique souvent sans le savoir. Au lieu de résoudre les équations normales, minimisons l'erreur quadratique moyenne du polynôme de degré 9 par descente de gradient (chapitre 3), en partant de ${\mathbf{\theta }}^{(0)}=0$. La plus grande valeur propre de la hessienne de la MSE, que nous notons $h_{\max }$ pour ne pas la confondre avec le $\lambda$ de la régularisation, vaut ici $2,78$; un pas $\eta =0,5$ est donc inférieur à et la descente converge, d'après le chapitre 3. Mais la plus petite valeur propre vaut environ — sur , des puissances comme , et se ressemblent beaucoup —, et le conditionnement dépasse : le long de cette direction, chaque pas ne réduit l'écart à la solution des moindres carrés que d'un facteur , et il faudrait des dizaines de millions d'itérations pour s'en approcher. Suivons les erreurs au fil des itérations, numérotées par comme au chapitre 3 — la lettre comptait les plis à la section précédente, et comptera les voisins au chapitre 7; le contexte lève toujours l'ambiguïté. (Nous regardons ici l'erreur de test ; en pratique, ce serait une erreur de validation, comme on va le dire.)

L'erreur d'entraînement baisse sans cesse, vers les $0,0082$ des moindres carrés, qu'elle n'atteint pas même après un million d'itérations. L'erreur de test baisse jusqu'à environ 9 000 itérations, où elle vaut $0,0810$, puis remonte. Pendant ce temps, la norme des poids grandit régulièrement: la descente explore d'abord les directions «faciles», où la donnée est riche, et ne construit que tardivement les grands coefficients qui font osciller le polynôme. Arrêter tôt, c'est empêcher les poids de devenir grands — exactement ce que fait la ridge par une pénalité.

La parenté avec la ridge peut être rendue précise sur un coût quadratique. Le chapitre 3 a montré que, dans la base des vecteurs propres de la hessienne $H$ de la MSE, de valeurs propres $h_j$, chaque pas de descente multiplie l'écart à la solution $\hat{\mathbf{\theta }}$ des moindres carrés par $1-\eta h_j$. En partant de , la composante de l'itéré vaut donc

Dans la version simplifiée de la ridge où tous les paramètres sont pénalisés, le même calcul (annuler le gradient $nH(\mathbf{\theta }-\hat{\mathbf{\theta }})+2\lambda \mathbf{\theta }$ de $J_{\lambda }$) donne ${\theta }_j=\frac{n{h}_j}{n{h}_j+2\lambda }{\hat{\theta }}_j$. Les deux facteurs se comportent de la même façon: proches de 1 dans les directions de grande courbure , où les données déterminent bien le paramètre, et proches de 0 dans les directions de faible courbure, où elles le déterminent mal. Pour petit, le premier vaut environ et le second environ ; ils coïncident quand

Avec $n=12$, $\eta =0,5$ et $k=9000$, cela donne $\lambda \approx 0,0013$ — et c'est bien à $\lambda =0,001$ que la ridge de degré 9 avait sa meilleure erreur de test, $0,0810$, la même qu'ici. Ce n'est qu'une correspondance approximative, mais elle dit l'essentiel: . Plus on itère, moins on régularise.

La régularisation reviendra presque à chaque chapitre, sous des noms différents. Le nombre $k$ de voisins des $k$ plus proches voisins (chapitre 7) règle un compromis biais–variance: $k=1$ a une variance maximale. La profondeur d'un arbre de décision et son élagage (chapitre 8) jouent le même rôle, et les forêts aléatoires réduisent la variance en moyennant des arbres. Le paramètre $C$ des machines à vecteurs de support (chapitre 9) est l'inverse d'un $\lambda$, et la régression ridge à noyau du même chapitre est la ridge sans biais, sur étiquettes centrées et avec la matrice $\lambda I$ au lieu de $\lambda I^{\prime }$, écrite dans un espace de caractéristiques implicite. Partout, la même question se pose: combien de liberté laisser au modèle, et comment le décider sans regarder le test.

Synthèse

• Quand la capacité d'un modèle augmente, son erreur d'entraînement ne remonte jamais (familles emboîtées) et finit par s'annuler; son erreur de test passe par un minimum. Sur nos données fictives ($y=\sin (\pi x)+\epsilon$, $\sigma =0,25$, graine 351), le polynôme de degré 3 a une erreur de test de $0,0775$, celui de degré 11 interpole les douze points et a une erreur de test de $14,4$.
• L'erreur quadratique attendue en un point se décompose en bruit + biais² + variance (théorème 6.2). Les modèles rigides souffrent de leur biais, les modèles flexibles de leur variance; sur nos données, la variance représente $95,8$ % de l'erreur attendue au degré 9.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Références

• Hastie, T., Tibshirani, R. et Friedman, J., The Elements of Statistical Learning, Springer, 2ᵉ éd., 2009, chap. 3 (ridge, lasso, chemin de régularisation) et chap. 7 (biais, variance, validation croisée, optimisme de l'erreur d'entraînement).
• James, G., Witten, D., Hastie, T. et Tibshirani, R., An Introduction to Statistical Learning, Springer, 2ᵉ éd., 2021, chap. 5 (rééchantillonnage et validation croisée) et chap. 6 (sélection de modèles et régularisation).
• Bishop, C. M., Pattern Recognition and Machine Learning, Springer, 2006, chap. 1 (ajustement polynomial d'une sinusoïde bruitée) et chap. 3 (décomposition biais–variance).
• Goodfellow, I., Bengio, Y. et Courville, A., Deep Learning, MIT Press, 2016, chap. 7 (régularisation, pénalités sur les poids, arrêt précoce).
• Azencott, C.-A., Introduction au Machine Learning, Dunod, 2ᵉ éd., 2022 (régularisation et sélection de modèles, en français).