Formulaire

Ce formulaire rassemble, chapitre par chapitre, ce qu'il faut avoir sous les yeux pour réviser ou pour écrire un programme: les modèles, les pertes, les gradients, les formes closes, les règles de mise à jour, les métriques et les algorithmes, chacun avec ses hypothèses et avec le bloc du chapitre qui l'énonce ou le démontre. Les démonstrations, les exemples chiffrés et les pièges sont là-bas, pas ici.

Comment lire les renvois. Dans chaque chapitre, les équations numérotées, les définitions et les théorèmes forment des séries distinctes: l'équation (6.4) et le théorème 6.4 sont deux objets différents. Ici, un numéro entre parenthèses désigne toujours une équation, un numéro précédé d'un mot («définition 5.4», «théorème 6.3», «exemple 3.3») toujours le bloc qui porte ce nom. Les rappels d'algèbre linéaire, de calcul différentiel et de probabilités — normes, projection, théorème spectral, gradients usuels, règle de la chaîne, espérance et covariance — sont rassemblés à l'annexe A et ne sont pas repris ici.

Une formule sans sa normalisation est un piège. Le même mot recouvre parfois deux échelles: l'erreur quadratique moyenne est une moyenne (division par $n$, sans facteur $\frac{1}{2}$) dans tout le cours, mais la ridge pénalise la somme des carrés; l'écart type de la standardisation est celui de population (division par $n$); la matrice de covariance de l'ACP divise aussi par $n$. Chaque ligne ci-dessous dit laquelle, et il faut la lire.

Notation, et les symboles qui servent deux fois

Selon les chapitres, $\mathbf{w}$ contient ou non le biais: au chapitre 2 et au chapitre 3, $\mathbf{w}=(w_0,w_1,\dots ,w_d)$ et $f(\mathbf{x})={\tilde{\mathbf{x}}}^{\top }\mathbf{w}$; ailleurs, ou , et ne contient que les poids. La ridge et le lasso ne pénalisent le biais.

Les réutilisations à connaître

Le cours suit la notation de chaque littérature plutôt qu'une notation uniforme. Un même symbole y désigne donc des objets différents selon le chapitre:

«Un contre tous» désigne seulement la classification multiclasse par $K$ classifieurs binaires (one-vs-rest, ch. 4); la validation croisée à $n$ plis (leave-one-out, ch. 5, 7 et 8) s'appelle validation croisée par exclusion. Et $\mathbf{w}$ contient ou non le biais selon le chapitre, comme dit plus haut.

1. Le cadre de l'apprentissage

Les trois pertes de la définition 1.6. Le résidu est $y-\hat{y}$ (au chapitre 3 le signe est inversé, $r_i={\tilde{\mathbf{x}}}_i^{\top }\mathbf{w}-y_i$, et le chapitre le dit). La perte carrée est dérivable et pénalise les grandes erreurs de façon disproportionnée; la perte absolue est robuste aux valeurs aberrantes; la perte 0–1 est constante par morceaux et ne guide aucune optimisation.

Risque empirique (1.2), définition 1.7, et risque réel (1.3), définition 1.8, sous l'hypothèse i.i.d. Avec la perte carrée, $\hat{R}$ est l'erreur quadratique moyenne (MSE) et $\sqrt{\hat{R}}$ la RMSE; avec la perte absolue, l'erreur absolue moyenne (MAE); avec la perte 0–1, le taux d'erreur. Le principe de minimisation du risque empirique (ERM) choisit, dans la famille $\{f_{\mathbf{\theta }}\}$ (définition 1.5), la fonction de plus petit .

Théorème 1.1, (1.4), pour un prédicteur $f$ choisi indépendamment des exemples: c'est l'hypothèse qui fait d'une erreur de test une estimation honnête, et que viole tout prédicteur entraîné sur ces mêmes exemples. Pour un taux d'erreur, ${\sigma }_f^2\le 1/4$ et $\mathbb{P}(|\hat{p}-p|\ge \epsilon )\le 1/(4n{\epsilon }^2)$: exemples de test pour à 95 % (exercice 1.5).

Identité (1.5), théorème 1.2: la constante qui minimise la perte carrée est la moyenne, unique, et le risque minimal est la variance empirique (division par $n$). Le théorème 1.3: la perte absolue est minimale en une médiane — le seul point $y_{(m+1)}$ si $n=2m+1$, tout l'intervalle $[y_{(m)},y_{(m+1)}]$ si . En classification avec la perte 0–1, la meilleure constante est la (exercice 1.4).

Règle du plus proche voisin (1.6), définition 1.9, distance euclidienne, égalités tranchées en faveur du premier exemple. Méthode non paramétrique: le jeu de données joue le rôle des paramètres. Son erreur d'entraînement est nulle sur des points distincts (théorème 7.1), ce qui ne dit rien de son erreur de test.

Démarche d'un projet (section «Le déroulement d'un projet»): 1. poser le problème et la mesure de performance; 2. rassembler les données et mettre de côté l'ensemble de test (par unité indépendante: patient, immeuble, expéditeur); 3. construire les caractéristiques, avec des statistiques calculées sur l'entraînement seul; 4. choisir et entraîner le modèle; 5. évaluer — validation ou validation croisée pour les choix, puis le test une seule fois; 6. déployer et surveiller la dérive.

2. Régression linéaire

Droite des moindres carrés (2.3), théorème 2.1, pour des $x_i$ non tous égaux. Elle minimise $\mathrm{SCR}(\mathbf{w})={\sum }_i(y_i-w_0-w_1{x}_i{)}^2$ (2.2), ou de façon équivalente , et passe par le point moyen . Avec le coefficient de corrélation , la pente s'écrit (2.5).

Modèle linéaire (2.6)–(2.7), définition 2.2: $f_{\mathbf{w}}(\mathbf{x})=w_0+w_1{x}_1+\cdots +w_d{x}_d={\tilde{\mathbf{x}}}^{\top }\mathbf{w}$, avec et .

Équations normales (2.8), théorème 2.2: une solution existe toujours; elle est unique, et donnée par (2.9), si et seulement si $\tilde{X}$ est de rang $d+1$. Sinon l'ensemble des solutions est $\hat{\mathbf{w}}+\ker \tilde{X}$. Identité utile (2.10): $\mathrm{SCR}(\mathbf{w})=\mathrm{SCR}(\hat{\mathbf{w}})+\Vert \tilde{X}(\mathbf{w}-\hat{\mathbf{w}}){\Vert }^2$. En pratique on ne forme pas l'inverse: on résout le système (ou on passe par ).

Théorème 2.3, (2.11): les résidus sont orthogonaux aux colonnes de $\tilde{X}$; leur somme n'est nulle que grâce à la colonne de uns. Lecture géométrique: $\hat{\mathbf{y}}=H\mathbf{y}$ est la projection orthogonale de $\mathbf{y}$ sur l'espace engendré par les colonnes, avec la matrice chapeau $H=\tilde{X}({\tilde{X}}^{\top }\tilde{X}{)}^{-1}{\tilde{X}}^{\top }$ (2.12), définition 2.3, symétrique et idempotente.

Décomposition de la variance (2.14), théorème 2.4, et coefficient de détermination (2.13), définition 2.4, avec $\mathrm{SCT}={\sum }_i(y_i-\bar{y}{)}^2$ et $\mathrm{SCE}={\sum }_i({\hat{y}}_i-\bar{y}{)}^2$. La décomposition suppose les ; alors et, en régression simple, . Le d'entraînement ne diminue jamais quand on ajoute une caractéristique; un peut être négatif.

Modèle linéaire en ses paramètres (2.15), définition 2.5: toute la théorie précédente s'applique en remplaçant les colonnes par les ${\phi }_k(\mathbf{x})$. Régression polynomiale de degré $m$: $\phi (t)=(t,t^2,\dots ,t^m)$ — le chapitre 6 note ce degré .

Modèle linéaire gaussien (2.16), définition 2.6, et théorème 2.5: la log-vraisemblance (2.17) vaut $-\frac{n}{2}\ln (2\pi {\sigma }^2)-\frac{1}{2{\sigma }^2}\Vert \mathbf{y}-\tilde{X}\mathbf{w}{\Vert }^2$, donc , et l'estimateur (2.18) de la variance est la MSE. L'estimateur sans biais divise par . Un bruit de Laplace conduirait de même à la perte absolue.

Colinéarité (définition 2.7): s'il existe $\mathbf{v}\ne 0$ avec $\tilde{X}\mathbf{v}=0$, la matrice ${\tilde{X}}^{\top }\tilde{X}$ est singulière et les coefficients ne sont plus déterminés; une valeur propre presque nulle (quasi-colinéarité) les rend instables. Remède: la ridge du chapitre 6.

3. Descente de gradient

Descente de gradient (3.2), définition 3.1, de pas d'apprentissage $\eta >0$. Justification (théorème 3.1, (3.1)): $-\nabla J$ est la direction de plus forte descente, et $J(\mathbf{\theta }-\eta \nabla J)<J(\mathbf{\theta })$ pour $\eta$ assez petit dès que $\nabla J\ne 0$.

Erreur quadratique moyenne (3.3), son gradient et sa hessienne (3.4), théorème 3.2. La hessienne ne dépend pas de $\mathbf{w}$, et $\nabla J=0$ redonne les équations normales. En régression simple (3.5): $\partial J/\partial w_0=\frac{2}{n}{\sum }_i(w_0+w_1{x}_i-y_i)$ et .

Convexité (3.8), définition 3.2, et inégalité des tangentes (3.9), théorème 3.3: pour $J$ de classe ${\mathcal{C}}^2$, $J$ est convexe si et seulement si sa hessienne est semi-définie positive partout, et alors tout point critique est un minimum global. La MSE d'un modèle linéaire en ses paramètres est convexe, strictement si et seulement si les colonnes de $\tilde{X}$ sont indépendantes (théorème 3.4).

Théorème 3.5, (3.10)–(3.11), pour $J(\mathbf{\theta })=\frac{1}{2}{\mathbf{\theta }}^{\top }A\mathbf{\theta }-{\mathbf{b}}^{\top }\mathbf{\theta }+c$ avec symétrique définie positive (pour la MSE, ): la descente converge . Dans la base propre, chaque coordonnée est multipliée à chaque pas par ; le facteur global est .

Conditionnement (3.12), définition 3.3, et meilleur pas fixe (exercice 3.5): il faut environ $\frac{\kappa }{2}\ln 10$ itérations pour diviser l'erreur par dix. Le seuil de stabilité dépend de ${\lambda }_{\max }$, la vitesse de ${\lambda }_{\min }$. Les lignes de niveau sont des ellipses d'allongement .

Standardisation (3.13), définition 3.4, avec l'écart type de population, ${\bar{x}}_j$ et $s_j$ calculés sur l'ensemble d'entraînement seul. Pour une caractéristique standardisée, $H=2I$, $\kappa =1$, et l'itération (3.7) converge en un pas pour . Retour à l'échelle brute: pente , ordonnée .

Descente stochastique (3.14) et par mini-lots de taille $b$, définition 3.5. Une époque est un passage complet après mélange, soit $\lceil n/b\rceil$ pas. Pour la perte carrée, $\nabla {\ell }_i(\mathbf{w})=2r_i{\tilde{\mathbf{x}}}_i$. Le gradient stochastique est si l'indice est tiré uniformément (théorème 3.6), de variance pour des tirages avec remise (exercice 3.4). Pas décroissants de Robbins–Monro: , , par exemple .

Ce que garantit un petit gradient (3.15), théorème 3.7, sous les hypothèses du théorème 3.5 (quadratique, $A$ définie positive). Sur un problème mal conditionné, ${\lambda }_{\min }$ est petit et un gradient petit ne garantit presque rien; sur un réseau de neurones, il peut signaler un plateau ou un point selle (définition 3.6).

Critères d'arrêt (section «Quand s'arrêter»): 1. un nombre maximal d'itérations, toujours; 2. $\Vert \nabla J({\mathbf{\theta }}^{(k)})\Vert <\epsilon$; 3. une stagnation relative, $(J^{(k-1)}-J^{(k)})/J^{(k-1)}<10^{-6}$; 4. l'erreur de qui cesse de baisser — l'arrêt précoce, qui est aussi une régularisation (définition 6.7). Le moment et Adam ne sont que nommés au chapitre 3; leurs règles de mise à jour sont au chapitre 11.

4. Classification et régression logistique

Classifieur linéaire (4.1), définition 4.1: la frontière de décision est l'hyperplan $w_0+{\mathbf{w}}^{\top }\mathbf{x}=0$ (une droite $w_0+w_1{x}_1+w_2{x}_2=0$ dans le plan). La régresse les étiquettes 0/1 par les équations normales et classe en pourriel quand ; elle est fragile, parce qu'un point facile mais lointain fait pivoter la frontière (exemple 4.1).

Sigmoïde (4.2), définition 4.2, et ses propriétés, théorème 4.1: $\sigma$ est une bijection de $\mathbb{R}$ sur $]0,1[$, de réciproque $\mathrm{logit}(p)=\ln \frac{p}{1-p}$; sa dérivée vaut au plus $1/4$, atteint en $z=0$.

Régression logistique (4.3)–(4.4), définition 4.3: le logarithme de la cote est affine, et ${\mathrm{e}}^{w_j}$ est le facteur par lequel la cote est multipliée quand $x_j$ augmente d'une unité. Au seuil $1/2$, la frontière est celle de la définition 4.1.

Entropie croisée binaire (4.6) et son coût moyen (4.7), définition 4.4, avec la log-vraisemblance (4.5) $\ln \mathcal{L}={\sum }_i[y_i\ln {\hat{p}}_i+(1-y_i)\ln (1-{\hat{p}}_i)]$: .

Gradient (4.8), théorème 4.2 — par exemple, $\mathrm{d}\ell /\mathrm{d}z=\hat{p}-y$, «écart fois entrée» — et hessienne (4.9), théorème 4.3: $J$ est convexe, strictement si $\tilde{X}$ est de rang $d+1$. Il n'y a : on descend le gradient (définition 3.1) ou l'on applique la méthode de Newton, , qui converge en quelques itérations.

Choix du seuil (section «La frontière de décision et le choix du seuil»; justification au théorème 5.1): un seuil sur $\hat{p}$ est un seuil sur le score, et la frontière reste une droite, simplement déplacée parallèlement. Avec un faux positif cinq fois plus coûteux qu'un faux négatif (exercice 1.4): $\hat{p}>5/6⟺z>\ln 5=1,6094$. Le chapitre 4 note ce seuil , le chapitre 5 le note et réserve au score.

Données séparables (définition 4.5, théorème 4.4): s'il existe $\mathbf{\theta }$ qui sépare strictement les classes, $\inf J=0$ n'est pas atteint, $J(t\mathbf{\theta })$ décroît vers $0$ quand $t\to \infty$, et la descente fait diverger les poids. Une pénalité $\lambda \Vert \mathbf{w}{\Vert }^2$ rétablit un minimum.

Softmax (4.10) et entropie croisée catégorielle (4.11), définition 4.6, pour $K$ classes numérotées $0,\dots ,K-1$, avec un score $z_k=w_{k0}+{\mathbf{w}}_k^{\top }\mathbf{x}$ par classe. Pour , : on retrouve la régression logistique. Le gradient par rapport aux scores est (exercice 4.5), soit en forme matricielle. (): régressions logistiques binaires, et ; leurs probabilités ne somment pas à 1. Pour calculer une softmax sans débordement, on soustrait d'abord le plus grand score.

5. Évaluation des modèles

Matrice de confusion, définition 5.1: les lignes sont les classes prédites, les colonnes les classes vraies. La classe positive est celle que l'on cherche à détecter.

Exactitude (5.1), définition 5.2, égale à $1-$ le taux d'erreur, et précision (5.2), définition 5.3. Sur des classes déséquilibrées, l'exactitude trompe: le filtre qui déclare tout légitime atteint 80 % sur la matrice témoin.

Rappel (sensibilité, taux de vrais positifs TPR) et spécificité (5.2), définition 5.3; taux de faux positifs $\mathrm{FPR}=1-\text{speˊcificiteˊ}$. Score $F_1$ (5.3), définition 5.4: moyenne harmonique de la précision $P$ et du rappel $R$, nul si . Variante pondérée ; exactitude équilibrée = moyenne du rappel et de la spécificité.

Classifieur à score et seuil (5.4), définition 5.5, et seuil de coût minimal (5.5), théorème 5.1, si le score est la vraie probabilité $\mathbb{P}(y=1\mid \mathbf{x})$ — une sortie de modèle ne l'est pas automatiquement: elle doit être calibrée. Pour un faux positif cinq fois plus coûteux qu'un faux négatif, $t^{\ast }=5/6$. Au chapitre 4, le seuil est noté $s$ et la règle est stricte, $\hat{p}>s$.

Courbe ROC (5.6), définition 5.6, parcourue quand le seuil $t$ décroît de $+\infty$ à $-\infty$, et AUC (5.7), théorème 5.2: pour des scores distincts, l'aire sous la courbe est la probabilité qu'un positif tiré au hasard ait un score supérieur à celui d'un négatif tiré au hasard; en cas d'égalité, la paire compte pour un demi. Forme par les rangs (exercice 5.5): $\mathrm{AUC}=({\sum }_i{\rho }_i-n_1(n_1+1)/2)/(n_1{n}_0)$, la statistique de Mann–Whitney divisée par . Hasard: ; classement parfait: . La courbe précision–rappel (définition 5.7) a pour référence la proportion de positifs , et se résume par la précision moyenne.

Métriques de régression (5.8), définition 5.8, avec $e_i=y_i-{\hat{y}}_i$ et $\bar{y}$ la moyenne . Sur un ensemble de test, peut être négatif: le modèle fait alors moins bien que la moyenne.

Validation croisée à $k$ plis (5.9), définition 5.10: 1. découper les données en $k$ plis; 2. pour $j=1,\dots ,k$, entraîner sur les $k-1$ autres plis et mesurer l'erreur $e_j$ sur le pli $j$; 3. faire la moyenne des erreurs. Pour , c'est la (, LOO, définition 7.6), à ne pas confondre avec le «un contre tous» de la classification multiclasse (). Partage entraînement / validation / test (définition 5.9): l'ensemble de test sert .

Fuite de données (définition 5.11): toute information de l'ensemble d'évaluation qui entre dans la construction du modèle. Exemple canonique: standardiser, ou sélectionner les caractéristiques, avant de séparer les données. Toute statistique (moyenne, écart type, choix de variables) se calcule sur l'entraînement seul, à l'intérieur de chaque pli.

Précision et taux de base (5.10), théorème 5.3 (formule de Bayes), avec $r$ le rappel, $\mathrm{sp}$ la spécificité et $\pi$ la proportion de positifs. À rappel et spécificité fixés, la précision s'effondre quand $\pi$ devient petit: $0,8095$ pour $\pi =0,2$, $0,0167$ pour $\pi =0,001$, avec un rappel de et une spécificité de .

6. Surapprentissage et régularisation

Régression polynomiale de degré $d$ (6.1), définition 6.1 — le chapitre 2 notait ce degré $m$. L'erreur d'entraînement ne remonte jamais quand le degré augmente, et s'annule dès $d\ge n-1$ pour des $x_i$ distincts (théorème 6.1); l'erreur de test, elle, finit par remonter: c'est le surapprentissage (définition 6.2).

Décomposition biais–variance (6.2), théorème 6.2, en un point $\mathbf{x}$ fixé, pour $y=f(\mathbf{x})+\epsilon$ avec $\mathbb{E}[\epsilon ]=0$, $\mathrm{Var}[\epsilon ]={\sigma }^2$ et $\epsilon$ indépendant du jeu d'entraînement ; (définition 6.3). Le bruit est un plancher qu'aucune méthode ne franchit. Pour les moindres carrés à plan d'expérience fixé, . Une (définition 6.4) trace les erreurs d'entraînement et de validation en fonction de : elles convergent vers .

Ridge (6.3), définition 6.5, et sa forme close (6.4), théorème 6.3, avec $I^{\prime }=\mathrm{diag}(0,1,\dots ,1)$: le biais n'est pas pénalisé. La pénalité est ajoutée à la somme des carrés, ce qui équivaut à $\hat{R}+(\lambda /n)\Vert \mathbf{w}{\Vert }^2$; la matrice est inversible pour tout , quel que soit le rang de . Avec une seule caractéristique: et — la pente est divisée par deux pour .

Lasso (6.5), définition 6.6: pas de forme close, et des coefficients exactement nuls — la boule ${\ell }_1$ a des coins sur les axes, et les lignes de niveau de l'erreur la touchent souvent là.

Théorème 6.4, (6.6), pour des colonnes centrées et orthogonales, avec $s_j=\Vert {\mathbf{x}}_{\cdot j}{\Vert }^2$, $c_j={\mathbf{x}}_{\cdot j}^{\top }\mathbf{y}$ et : la ridge chaque coefficient d'un facteur, le lasso le et l'annule dès que . Ici n'est pas un écart type.

Choisir $\lambda$ (section «Choisir $\lambda$ par validation croisée»): 1. fixer une grille de valeurs, en progression géométrique; 2. pour chaque valeur, ajuster $k$ modèles, chacun sur $k-1$ plis, et mesurer chacun sur le pli laissé de côté; l'erreur de validation croisée est la moyenne des $k$ erreurs; 3. retenir la valeur de plus petite erreur; 4. réajuster le modèle sur tout l'ensemble d'entraînement avec ce $\lambda$; 5. mesurer l'erreur de test, une seule fois. Une statistique de prétraitement (standardisation) se calcule, elle aussi, sur les seuls plis d'entraînement (définition 5.11).

Arrêt précoce (6.7), définition 6.7, dans la base propre de la hessienne de la MSE (valeurs propres $h_j$), en partant de $0$: après $k$ pas, les directions de grande courbure sont apprises, celles de petite courbure à peine — comme avec une ridge de paramètre $\lambda \approx n/(2\eta k)$. Arrêter tôt, c'est régulariser.

7. Plus proches voisins

Règle des $k$ plus proches voisins en classification (7.1), définition 7.1, et en régression (7.2), définition 7.2, avec $V_k(\mathbf{x})$ l'ensemble des $k$ exemples les plus proches de $\mathbf{x}$ (à distance égale, le premier dans l'ordre du jeu de données). Égalité de votes: la classe du voisin le mieux classé l'emporte; à deux classes, on prend $k$ impair. La moyenne des voisins est le choix de la perte carrée (théorème 1.2); avec la perte absolue on prendrait leur médiane. Pour $k=1$, l'erreur d'entraînement est nulle sur des points distincts (théorème 7.1), et les régions de décision sont des réunions de cellules de Voronoi (définition 7.5).

Distance de Minkowski (7.3), définition 7.3 — euclidienne pour $p=2$, de Manhattan pour $p=1$, ${\max }_j|x_j-x_j^{\prime }|$ quand — et standardisation (7.4), définition 7.4, avec l'écart type de population et les statistiques de l'entraînement; mise à l'échelle min–max: . : multiplier par 10 change les voisins.

Biais et variance des $k$-PPV en régression (7.6), théorème 7.2, à points ${\mathbf{x}}_i$ fixés et bruit indépendant de variance ${\sigma }^2$: la variance décroît en ${\sigma }^2/k$, le biais croît avec $k$. On choisit $k$ par validation croisée, souvent par exclusion (, LOO, définition 7.6): chaque exemple est prédit à partir des autres.

Vote pondéré par la distance (7.7), définition 7.7 (le vote de classe somme les $w_i$ par classe). Un voisin à distance nulle décide seul. Variante gaussienne: $w_i=\exp (-\mathrm{dist}(\mathbf{x},{\mathbf{x}}_i{)}^2/(2h^2))$, de largeur de bande — la même que celle du noyau gaussien du chapitre 9.

Malédiction de la dimension (7.8), théorème 7.3, pour $0<\epsilon <\frac{1}{2}$: la fraction tend vers 1 quand $d$ croît — $19$ % du cube en dimension 2, $99,997$ % en dimension 100 pour $\epsilon =0,05$. Un sous-cube qui contient une fraction des points a pour côté , et le rapport des distances au plus proche et au plus lointain voisin tend vers 1: «proche» perd son sens.

Coût d'une requête (section «Le coût d'une requête»): $O(nd)$ pour calculer les distances, plus $O(n\log k)$ avec un tas pour garder les $k$ meilleures. Un arbre $k$-d (définition 7.8) coupe à la médiane d'une coordonnée, à tour de rôle, en $O(n\log n)$; une requête descend jusqu'à une feuille puis remonte en élaguant tout sous-arbre dont l'hyperplan de coupe est plus loin que le meilleur voisin trouvé. Il perd son avantage en grande dimension.

8. Arbres de décision et ensembles

Impureté de Gini et entropie en bits (8.1), définition 8.2, avec $0{\log }_{2}0=0$; à deux classes, $G(p)=2p(1-p)$. Le Gini est nul pour un nœud pur et maximal, égal à $1-1/K$, pour la loi uniforme (théorème 8.1); le maximum de l'entropie est ${\log }_{2}K$. Taux d'erreur d'un nœud: .

Impureté pondérée et gain (8.2), définition 8.3; avec l'entropie, $\Delta I$ est le gain d'information. Les seuils candidats sont les milieux entre valeurs observées consécutives. Une coupure n'augmente jamais le Gini pondéré (théorème 8.2), avec égalité si et seulement si les deux parties ont les proportions du parent — d'où un arbre poussé jusqu'à la pureté, qui surapprend.

Faire pousser l'arbre (CART, section «Faire pousser l'arbre»): 1. si le nœud est pur ou qu'une règle d'arrêt s'applique (profondeur, effectif minimal), en faire une feuille, qui prédit la classe majoritaire ou la moyenne; 2. sinon, essayer toutes les coupures $x_j\le s$ et retenir celle d'impureté pondérée minimale; 3. partager le nœud et recommencer sur chaque partie.

Élagage coût–complexité (8.3), définition 8.4: $\hat{R}(T)$ est la proportion d'exemples mal classés, $|T|$ le nombre de feuilles; on élague d'abord le «maillon le plus faible», le nœud $t$ de plus petit $g(t)$, et l'on choisit $\alpha$ par validation croisée.

Arbre de régression (définition 8.5): une feuille prédit la moyenne de ses exemples, et l'on choisit la coupure qui minimise ${\text{SCE}}_G+{\text{SCE}}_D$, avec $\text{SCE}={\sum }_{i\in \text{nœud}}(y_i-{\bar{y}}_{\text{nœud}}{)}^2$ — c'est la . Le gain s'écrit (exercice 8.3).

Variance d'une moyenne de $B$ prédicteurs de même variance ${\sigma }^2$ et de corrélation deux à deux $\rho$ (8.4), théorème 8.3: moyenner fait disparaître le second terme, jamais le premier. Bagging (définition 8.6): $B$ échantillons bootstrap de taille $n$, tirés avec remise, un arbre profond par échantillon, vote ou moyenne. Un exemple est absent d'un échantillon avec probabilité $(1-1/n{)}^n\to {\mathrm{e}}^{-1}\approx 0,368$, d'où l' (définition 8.7), estimée sans ensemble de validation. (définition 8.8): à chaque nœud, on ne considère que caractéristiques tirées au hasard — souvent en classification, en régression — pour les arbres et faire baisser ; redonne le bagging. Ajouter des arbres ne fait jamais de mal.

AdaBoost, définition 8.9 (classes 0 et 1): 1. poids initiaux $w_i=1/n$; 2. pour $t=1,\dots ,T$: choisir la souche $h_t$ d'erreur pondérée ${\epsilon }_t$ minimale, calculer , multiplier les poids des exemples mal classés par et ceux des autres par , puis normaliser; 3. prédire la classe dont la somme des est la plus grande. Après repondération, les exemples mal classés pèsent exactement (exercice 8.5). (section «Le gradient boosting»): , où est ajusté aux résidus — le gradient négatif de la perte — et joue le rôle du pas .

Importance des caractéristiques (définition 8.10): par diminution d'impureté (somme des $\frac{n_{\text{nœud}}}{n}\Delta G$ sur les nœuds qui utilisent la caractéristique, normalisée à 1), ou par permutation (hausse de l'erreur quand on permute la colonne). La première favorise les caractéristiques à nombreuses valeurs et attribue une part au bruit; aucune des deux n'est causale.

9. Machines à vecteurs de support

Ici $y\in \{-1,+1\}$, et non $\{0,1\}$: c'est la seule exception du cours.

Classifieur $\hat{y}=\mathrm{signe}(f(\mathbf{x}))$ et marge fonctionnelle $m_i=y_{i}f({\mathbf{x}}_i)$ (9.1), définition 9.1; distance d'un point à l'hyperplan (9.2), théorème 9.1. Marge géométrique (définition 9.2): — le biais n'entre pas dans la norme. En , , d'où et une bande de marge de largeur (théorème 9.2).

SVM à marge dure (9.3), définition 9.3, pour des données séparables: un problème convexe, de solution unique en $\mathbf{w}$. Les vecteurs de support (définition 9.4) sont les exemples où la contrainte est active, $y_i({\mathbf{w}}^{\top }{\mathbf{x}}_i+b)=1$: eux seuls déterminent la solution.

Problème dual (9.4), théorème 9.3 (admis: la dualité forte relève de l'optimisation convexe). Conditions de Karush–Kuhn–Tucker: admissibilité; stationnarité $\mathbf{w}={\sum }_i{\alpha }_i{y}_i{\mathbf{x}}_i$ (9.5) et ${\sum }_i{\alpha }_i{y}_i=0$; complémentarité , donc seulement pour les vecteurs de support. Ensuite pour tout vecteur de support , et (exercice 9.5).

Marge souple (9.6), définition 9.5 — $\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C{\sum }_i{\xi }_i$ sous , — et sa forme sans contrainte (9.7), théorème 9.4, avec la (définition 9.6). Le dual garde la forme (9.4) avec . Un grand tolère peu de violations (marge étroite, variance), un petit beaucoup (marge large, biais).

Lecture de (9.7) comme risque empirique régularisé (théorème 9.4). Attention à la normalisation: ici le $\lambda$ multiplie le risque moyen, alors que la ridge (6.3) et la ridge à noyau (9.12) l'ajoutent à la somme des pertes; dans la convention du chapitre 6, la SVM aurait $\lambda =1/(2C)$. Avec des étiquettes $\pm 1$, l'entropie croisée (4.6) s'écrit $\ln (1+{\mathrm{e}}^{-yf(\mathbf{x})})$: la charnière en est une version «à bord franc», nulle dès que la marge dépasse 1.

Sous-gradient de (9.7) (9.8), pour la descente ${\mathbf{\theta }}^{(k+1)}={\mathbf{\theta }}^{(k)}-{\eta }_k{\mathbf{g}}^{(k)}$ avec des pas décroissants , sur des données centrées.

Noyau et matrice de Gram $K_{ij}=k({\mathbf{x}}_i,{\mathbf{x}}_j)$ (9.9), définition 9.7, et fonction de décision à noyau (9.10). L'astuce du noyau: le dual et la décision ne font intervenir que des produits scalaires, que l'on remplace par $k$ sans jamais calculer $\phi$. Une matrice de Gram est symétrique semi-définie positive (théorème 9.6).

Noyau polynomial de degré $m$ et noyau gaussien de largeur $h$ (9.11), définition 9.8; les bibliothèques écrivent $\exp (-\gamma \Vert \mathbf{x}-{\mathbf{x}}^{\prime }{\Vert }^2)$ avec $\gamma =1/(2h^2)$, un sans rapport avec la marge. Le noyau polynomial correspond à monômes; le noyau gaussien à une infinité de caractéristiques (théorème 9.5). XOR, impossible pour tout classifieur linéaire (théorème 10.2), devient séparable avec la caractéristique : sur les coins , (exemple 9.3).

Régression ridge à noyau (9.12), définition 9.9 et théorème 9.7: la ridge ${\sum }_i(y_i-{\mathbf{w}}^{\top }\phi ({\mathbf{x}}_i){)}^2+\lambda \Vert \mathbf{w}{\Vert }^2$ , dont la solution est une combinaison des exemples (). La largeur règle le compromis biais–variance: petite, la fonction passe par les points; grande, elle s'aplatit. Coût: la matrice de Gram occupe nombres et sa résolution coûte de l'ordre de opérations.

10. Réseaux de neurones

Perceptron (10.1), définition 10.1, avec la fonction de Heaviside $H(z)=1$ si $z\ge 0$ et $0$ sinon — la frontière est rangée du côté de la classe 1, alors que la définition 4.1 écrit une inégalité stricte. Règle d'apprentissage (10.2), définition 10.2: 1. partir de $\mathbf{\theta }=0$; 2. parcourir les exemples dans un ordre fixe, cycliquement; 3. pour chacun, calculer ${\hat{y}}_i$ et appliquer (10.2), qui ne modifie qu'en cas d'erreur; 4. s'arrêter à la fin de la première époque sans erreur. C'est un pas de gradient stochastique où serait remplacé par .

Théorème de Novikoff (10.3), théorème 10.1: si les données sont séparables avec une marge $\gamma >0$ par un ${\mathbf{\theta }}^{\ast }$ de norme 1 (condition $s_i{\mathbf{\theta }}^{\ast \top }{\tilde{\mathbf{x}}}_i\ge \gamma$ avec ), la règle s'arrête, quel que soit . Cette marge se mesure sur les vecteurs augmentés , biais compris: ce n'est pas la marge géométrique du chapitre 9. Sur des données non séparables, la règle : XOR n'est pas linéairement séparable (théorème 10.2), et aucun classifieur linéaire ne le réalise.

Propagation avant (10.4) du perceptron multicouche, définition 10.3, avec ${\mathbf{a}}^{[0]}=\mathbf{x}$, $W^{[\ell ]}\in {\mathbb{R}}^{n_{\ell }\times n_{\ell -1}}$, et nombre de paramètres (10.5): 9 pour un réseau 2–2–1, pour 784–100–10. Couche de sortie: identité et erreur quadratique moyenne en régression; sigmoïde et entropie croisée (définition 4.4) en classification binaire; softmax et entropie croisée catégorielle (définition 4.6) pour classes. Le coût (10.6) est la , et il .

Fonctions d'activation, définition 10.4: $\tanh z=2\sigma (2z)-1$; ${\mathrm{ReLU}}^{\prime }(z)=1$ pour $z>0$, $0$ pour $z<0$, et l'on convient . (théorème 10.3).

Signal d'erreur, en sortie sigmoïde ou softmax avec l'entropie croisée (théorème 10.4 pour une couche cachée, (10.7), où ${\delta }^{[2]}=\hat{p}-y$; théorème 10.5 en général). Avec la perte carrée $(\hat{y}-y{)}^2$ et une sortie identité, (exercice 10.5).

Rétropropagation (10.8)–(10.9), théorème 10.5, démontrée par la règle de la chaîne (théorème 10.4, exercice 10.5; règle de la chaîne au théorème A.8). Le symbole $\ell$ désigne à la fois la perte et l'indice de couche: c'est l'argument qui les distingue. Un pas sur un mini-lot: 1. propagation avant de chaque exemple, en gardant tous les ${\mathbf{z}}^{[\ell ]}$ et ${\mathbf{a}}^{[\ell ]}$; 2. calcul de ${\mathbf{\delta }}^{[L]}$; 3. propagation arrière par (10.8) et gradients par (10.9); 4. moyenne des gradients sur le mini-lot; 5. mise à jour $\mathbf{\theta }\leftarrow \mathbf{\theta }-\eta \nabla J$.

Différences finies centrées (10.10), pour vérifier un gradient: erreur en $O(h^2)$, pas optimal $h\approx 6\cdot 10^{-6}$ en double précision. Écart relatif $|g-\tilde{g}|/\max (|g|,|\tilde{g}|,10^{-8})$: vers le gradient est juste, au-delà de il est faux.

Initialisations, définition 10.5 (biais à zéro). En loi uniforme sur $[-a,a]$, de variance $a^2/3$: $a=\sqrt{6/(n_{\text{entreˊe}}+n_{\text{sortie}})}$ pour Xavier, pour He. Xavier convient à la sigmoïde et à , He à ReLU, qui annule la moitié du signal: . Les dérivées de la sigmoïde ne dépassant pas , le gradient à travers les couches.

Approximation universelle, théorème 10.6 (admis): pour $g$ continue et non polynomiale, $f$ continue et $K$ compact, une couche cachée suffit, avec $N$ assez grand. Le théorème ne dit ni combien d'unités il faut, ni que la descente de gradient les trouvera, ni que l'approximation généralisera hors des données.

Pénalité sur les poids (weight decay) (10.11), définition 10.6, biais exclus. Attention à la normalisation: la pénalité est ajoutée ici au risque moyen $\hat{R}$, alors que la ridge du chapitre 6 l'ajoute à la somme des carrés; le $\lambda$ de (10.11) correspond donc à $\lambda /n$ dans (6.3). L'arrêt précoce (définition 6.7) est l'autre régularisation de base.

11. Apprentissage profond

Convolution discrète (11.1), définition 11.2 — en fait une corrélation croisée: la vraie convolution retourne le noyau — de noyau $k\times k$, pas $s$ et marge $p$ (padding); taille de sortie (11.2), théorème 11.1, pour $k\le n+2p$. Cas usuels: $n-k+1$ sans marge ni pas; marge «same» $p=(k-1)/2$ avec qui conserve la taille. Une image est un tableau (définition 11.1): ici , et sont la hauteur, la largeur et le nombre de canaux.

Couche convolutive (11.3), définition 11.3: un même noyau par canal de sortie, appliqué en toute position — c'est le partage des poids.

Nombre de paramètres (11.4), théorème 11.2: celui d'une convolution ne dépend pas de la taille de l'image. Sur une image $28\times 28$ avec six noyaux $5\times 5$ et une marge de 2: $156$ paramètres contre $3692640$. Une couche dense de $784$ entrées vers $100$ unités en a $78500$.

Équivariance par translation (11.5), théorème 11.3, pour un pas $s=1$; le sous-échantillonnage par maximum (définition 11.4, en général $k=s=2$, sans paramètre) la change en une invariance approximative. Champ récepteur (11.6), définition 11.5, avec $r_0=j_0=1$: la pile convolution , convolution , maximum de pas , convolution donne .

Méthode du moment (momentum) (11.7), définition 11.6, avec ${\mathbf{g}}^{(k)}$ le gradient du mini-lot et $0\le \beta <1$ (souvent $0,9$). Cette forme n'a pas de facteur $1-\beta$ devant $\mathbf{g}$.