L'astuce du noyau, les SVM, le ridge à noyau et les arbres de décision, avec des exemples calculés

Le classifieur à marge maximale

Parmi toutes les droites qui séparent deux classes sans erreur, le SVM garde celle qui reste le plus loin possible des points les plus proches de chaque côté.

Quand deux classes sont séparables par une droite, une infinité de droites le font avec zéro erreur d'apprentissage. La régression logistique en choisit une par la vraisemblance. La machine à vecteurs de support (support vector machine, SVM) pose plutôt une question géométrique : quelle frontière laisse la bande vide la plus large entre les classes ? Un nouveau client ressemble à un client connu, à un peu de bruit près ; une frontière qui frôle un point d'apprentissage classe mal ses voisins bruités.

On code les classes $y_i \in \{-1, +1\}$ et on écrit $f(x) = w^{\top}x + b$. Multiplier $w$ et $b$ ensemble ne change pas la frontière : on pose donc $|f| = 1$ aux points les plus proches. Un point étant à distance $|f(x)| / \lVert w \rVert$ de l'hyperplan, la bande mesure $2/\lVert w \rVert$, et l'élargir revient à réduire $\lVert w \rVert$. C'est le principe de la marge maximale (maximum margin), un problème quadratique convexe au minimum unique (Cortes et Vapnik, 1995) :

La solution, que SVC de scikit-learn retrouve avec un noyau linéaire et un $C$ très grand, a pour norme $\lVert w \rVert = 2\sqrt2/3 \approx 0.943$ : la bande mesure $2/\lVert w \rVert = 3/\sqrt2 \approx 2.12$, soit exactement l'écart entre les deux droites pointillées, mesuré le long de la normale $(1, 1)/\sqrt2$. Trois clients touchent la bande : ce sont les vecteurs de support (support vectors). Les trois autres pourraient bouger, ou disparaître, sans que la frontière change.

Retour au sommaire.

Marge souple, perte charnière et prix C

Les données réelles ne sont jamais parfaitement séparables : le SVM laisse donc certains points entrer dans la bande et fait payer un prix fixe par unité d'empiètement.

Sur des données de crédit, aucune droite ne sépare les défauts des clients sains. Cortes et Vapnik (1995) introduisent la marge souple (soft margin) : chaque point reçoit une variable d'écart (slack variable) $\xi_i \ge 0$, la quantité dont il viole la marge, et l'objectif gagne un terme $C \sum_i \xi_i$. À l'optimum, chaque écart vaut $\max(0, 1 - y_i f(x_i))$, si bien qu'on peut supprimer les contraintes :

Le terme de la somme est la perte charnière (hinge loss) : nulle pour un point du bon côté avec une avance d'au moins 1, puis linéaire quand le point entre dans la bande ou franchit la frontière. Vu ainsi, le SVM à marge souple est une perte plus une pénalité sur $\lVert w \rVert^{2}$, la même forme que le ridge, où $C$ joue le rôle de $1/\lambda$ : un $C$ petit donne une marge large et une forte régularisation (risque de sous-apprentissage), un $C$ grand une marge étroite et un risque de sur-apprentissage, comme le C de LogisticRegression.

Retour au sommaire.

Le problème dual : seuls les vecteurs de support comptent

Réécrit avec un prix par contrainte, le SVM montre que les points loin de la frontière reçoivent un prix nul : les retirer ne change rien.

On associe un multiplicateur de Lagrange $\alpha_i \ge 0$ à chaque contrainte et on retranche les contraintes de l'objectif. Annuler le gradient en $w$, puis la dérivée en $b$, donne deux identités. En les réinjectant, $w$ et $b$ disparaissent et il reste un problème en $\alpha$ seul :

Avec une marge souple, seule s'ajoute la borne $\alpha_i \le C$. Les écarts complémentaires, l'une des conditions de Karush-Kuhn-Tucker (KKT), donnent $\alpha_i\,[\,y_i f(x_i) - 1\,] = 0$ : soit le prix est nul, soit la contrainte est saturée. Un point bien classé et hors de la bande a $\alpha_i = 0$ et disparaît de $w$ comme de toute prédiction. Cette parcimonie explique pourquoi SVC ne garde que ses points support_ pour prédire.

Exemple calculé : quatre clients sur une droite

1. Données. Clients sains en $x = -3$ et $x = -1$, défauts en $x = 2$ et $x = 4$. Les deux points intérieurs sont les plus proches de l'autre classe.
2. Supports sur le bord. Écrire $y\,f(x) = 1$ en $x = -1$ et en $x = 2$ donne $w - b = 1$ et $2w + b = 1$. En additionnant, $3w = 2$, donc $w = 2/3$, $b = -1/3$, et la frontière passe en $x = 1/2$.
3. Points extérieurs. En $x = -3$ et $x = 4$, l'avance vaut $7/3 > 1$ : la contrainte n'est pas saturée, donc leur prix est nul par les écarts complémentaires.
4. Prix. La condition $\sum_i \alpha_i y_i = 0$ impose l'égalité des deux prix restants, notés $a$. Alors $w = a(-1)(-1) + a(+1)(2) = 3a = 2/3$, d'où $a = 2/9$.
5. Vérification. La valeur primale $\tfrac12 w^{2} = 2/9$ égale la valeur duale $\sum_i \alpha_i - \tfrac12 w^{2} = 4/9 - 2/9$, et la marge $2/w = 3$ est la distance de $-1$ à $2$. Déplacer le point de $-3$ à $-10$ ne change rien ; déplacer le point en $-1$ change tout.

Retour au sommaire.

L'astuce du noyau : noyaux polynomial et RBF

Le dual ne voit les données qu'à travers des ressemblances entre paires de points : remplacer le produit scalaire par une ressemblance plus riche courbe la frontière sans travail supplémentaire.

Regardons à nouveau le dual : l'apprentissage ne demande que le tableau $n \times n$ des produits scalaires $x_i^{\top}x_j$, la matrice de Gram (Gram matrix), et la prédiction que $x_i^{\top}x$. Des points sur une droite, une classe aux deux bouts et l'autre au milieu, ne se séparent pas par un seul seuil ; après $x \mapsto (x, x^{2})$, une droite horizontale suffit. Une frontière courbe devient plate après une transformation $\varphi$, l'application de plongement (feature map). L'astuce du noyau (kernel trick) calcule $\varphi(x)^{\top}\varphi(z)$ directement à partir de $x$ et $z$, sans construire $\varphi$ (Boser, Guyon et Vapnik, 1992).

Pour le noyau polynomial de degré 2 en dimension 2, développer le carré et couper le terme croisé en $\sqrt2 \cdot \sqrt2$ fait apparaître le plongement caché :

Vérifions avec $x = (1, 2)$ et $z = (3, -1)$. Côté noyau, deux produits, une somme et un carré : $x^{\top}z = 1$, donc $k = 1$. Côté plongement, $\varphi(x) = (1, 2\sqrt2, 4)$ et $\varphi(z) = (9, -3\sqrt2, 1)$, dont le produit scalaire vaut $9 - 12 + 4 = 1$. Le noyau général $(x^{\top}z + c)^{d}$ contient toutes les interactions jusqu'au degré $d$, pour le prix d'un produit scalaire et d'une puissance.

Le noyau gaussien, ou noyau RBF (radial basis function), vaut 1 pour deux points identiques et s'efface avec la distance ; $\gamma$ règle la portée de chaque point d'apprentissage. Pour deux points à distance au carré 5, il vaut $e^{-0.5} \approx 0.607$ avec $\gamma = 0.1$ et environ 0,082 avec $\gamma = 0.5$. Développer l'exponentielle en série entière montre que son plongement a une infinité de coordonnées. Avec $\gamma$ petit, la frontière est presque droite ; avec $\gamma$ grand, elle dessine des îlots autour de points isolés.

Retour au sommaire.

Le ridge à noyau, et les noyaux en pratique

Le ridge à noyau est la régression ridge réécrite avec un poids par point d'apprentissage, ce qui permet de remplacer le produit scalaire par un noyau tout en gardant une forme fermée.

Partons du ridge en forme fermée. L'identité $(X^{\top}X + \lambda I_p)X^{\top} = X^{\top}(XX^{\top} + \lambda I_n)$ montre que $\hat\beta = X^{\top}\alpha$, avec un poids par point d'apprentissage. Les prédictions ne font plus intervenir que des produits scalaires $x_i^{\top}x$, qu'un noyau remplace : c'est le ridge à noyau (kernel ridge regression), conséquence du théorème du représentant (Kimeldorf et Wahba, 1971) :

Contrairement au SVM, il n'y a pas de parcimonie : la perte est quadratique, donc en général tous les $\alpha_i$ sont non nuls et tout le jeu d'apprentissage est conservé. En échange, l'ajustement est un seul système linéaire, résolu avec np.linalg.solve plutôt qu'en inversant la matrice ; avec un noyau linéaire, il doit retrouver le ridge à la précision machine. Dans scikit-learn, KernelRidge appelle $\lambda$ alpha et n'ajuste pas de constante.

Les deux points de cible 0 reçoivent des poids négatifs : ils tirent l'ajustement vers le bas autour d'eux. En $x = 1$, la cible vaut 1, mais la pénalité ramène l'ajustement à 0,576.

Augmenter $C$ pousse dans le même sens qu'augmenter $\gamma$ ; les deux se choisissent par validation croisée sur une grille en puissances de 10. Standardisez d'abord : un noyau RBF additionne des écarts au carré dans l'unité de chaque variable, si bien qu'un plafond de crédit en dizaines de milliers de dollars écrase un âge en années et que $K$ s'effondre sur l'identité. Le scaler se place dans le pipeline, ajusté sur les plis d'apprentissage.

Le prix de l'astuce est la matrice $n \times n$ : 32 Mo en double précision pour 2 000 lignes, 2,6 Go pour les 18 000 lignes d'apprentissage du jeu de crédit, et une résolution en environ $n^{3}$ opérations. Pour $n$ grand, les variables de Fourier aléatoires (random Fourier features, Rahimi et Recht, 2007) construisent $D$ colonnes cosinus tirées au hasard dont les produits scalaires approchent le noyau RBF ; une régression logistique sur ces colonnes passe à l'échelle en $O(nD)$ et, contrairement à SVC ou KernelRidge, donne des probabilités.

Retour au sommaire.

Arbres de décision : la coupe qui purifie le plus

Un arbre de décision pose une suite de questions fermées, une variable à la fois, en choisissant chaque question pour que les groupes obtenus soient aussi homogènes que possible.

Un arbre de décision (decision tree) joue au jeu du portrait : le client a-t-il eu au moins deux mois de retard le mois dernier ? Puis une question sur le plafond de crédit, et ainsi de suite, jusqu'à une feuille qui prédit la part de défauts parmi les clients d'apprentissage qui y arrivent. CART (Breiman, Friedman, Olshen et Stone, 1984) fait pousser l'arbre de façon gloutonne depuis le haut : à chaque nœud, il essaie toutes les variables et tous les seuils (les milieux entre valeurs triées), garde la coupe qui fait le plus baisser l'impureté pondérée des enfants, puis recommence.

L'impureté de Gini (Gini impurity) $G$ mesure le mélange d'un nœud : tirez deux de ses clients au hasard, avec remise, elle donne la chance que leurs classes diffèrent ; à deux classes, elle vaut $2p(1-p)$, nulle sur un nœud pur et au plus $1/2$. L'entropie de Shannon $H$, en bits, vient d'ID3 (1986) et de C4.5 (1993), de Quinlan ; sa baisse est le gain d'information (information gain). Les deux courbes ont la même forme et choisissent presque toujours la même coupe. scikit-learn utilise Gini par défaut.

Exemple calculé : le gain de chaque coupe

1. Parent. Quatre défauts sur dix, $p = 0.4$ : $G = 1 - 0.16 - 0.36 = 0.48$.
2. Enfants de A. Trois défauts sur quatre à gauche, $G = 1 - 9/16 - 1/16 = 6/16 = 0.375$ ; un sur six à droite, $G = 10/36 \approx 0.278$.
3. Moyenne pondérée. Selon les effectifs, $0.4 \times 0.375 + 0.6 \times 0.278 \approx 0.317$, donc la coupe A gagne $0.48 - 0.317 = 0.163$. Avec l'entropie, le gain vaut $0.971 - (0.4 \times 0.811 + 0.6 \times 0.650) \approx 0.256$ : A l'emporte selon les deux critères.
4. Coupe B. Chaque côté compte deux défauts sur cinq, la proportion du parent : les deux enfants ont l'impureté du parent et le gain est nul. Une question qui reproduit le mélange du parent n'apprend rien, quelle que soit la variable.
5. Vérification. DecisionTreeClassifier(max_depth=1) choisit PAY_0 au seuil 1,5, milieu entre 1 et 2, et affiche les trois mêmes impuretés.

Retour au sommaire.

Profondeur, élagage, instabilité et biais de la MDI

Livré à lui-même, un arbre pousse jusqu'à apprendre par cœur le jeu d'apprentissage : il faut l'arrêter ou l'élaguer, et lire avec méfiance ses scores d'importance intégrés.

Par défaut (max_depth=None), scikit-learn fait pousser l'arbre jusqu'à ce que chaque feuille soit pure. Une profondeur maximale, une taille minimale de feuille (min_samples_leaf) ou un gain minimal l'arrêtent plus tôt ; les petites feuilles donnent aussi des probabilités grossières.

La simulation du deck le montre : une variable binaire fixe la probabilité de défaut à 0,7 ou 0,3, deux autres sont du bruit, 1 000 lignes pour apprendre et 1 000 pour tester, donc aucun classifieur ne peut dépasser 0,70. Un arbre de profondeur 1 ou 2 atteint 0,683 en test ; un arbre sans limite obtient 1,000 en apprentissage avec 397 feuilles et 0,549 en test, à peine mieux qu'une pièce. C'est un pur cas de sur-apprentissage (overfitting).

Plutôt que d'arrêter tôt, CART fait pousser l'arbre complet puis l'élague : c'est l'élagage coût-complexité (cost-complexity pruning), où $R(T)$ est l'erreur d'apprentissage, $|T|$ le nombre de feuilles et $\alpha$ un prix par feuille, choisi par validation croisée (ccp_alpha dans scikit-learn). Les sous-arbres optimaux sont emboîtés : il suffit d'en tester une poignée.

Au prix le plus élevé, il reste deux feuilles : une seule coupe, sur la seule variable utile. Un arbre court se lit à voix haute comme une règle qu'un client peut contester, ce que le crédit réglementé apprécie. Il est aussi instable : réajustez un arbre de profondeur 3 après avoir retiré au hasard 5 % des lignes, et le deuxième niveau saute vers des variables de bruit et de nouveaux seuils. Le bagging de Breiman (1996) part de ce constat et mène aux forêts aléatoires et au boosting de la séance suivante.

Le feature_importances_ de scikit-learn est l'importance par impureté (mean decrease in impurity, MDI) : les gains des coupes sur chaque variable, pondérés par les effectifs, normalisés à 1. Elle est gratuite mais doublement biaisée. Elle se mesure sur le jeu d'apprentissage, donc les coupes qui ont appris du bruit comptent aussi ; et une variable continue offre des centaines de seuils là où une variable binaire n'en offre qu'un, donc bien plus de coupes chanceuses. Sur l'arbre sans limite de la simulation, la MDI met le bruit continu en tête (0,754) et la variable utile ensuite (0,206) ; l'importance par permutation sur des données tenues à l'écart rétablit l'ordre (Strobl et al., 2007).

Retour au sommaire.

À retenir

1. Le SVM garde la frontière de marge la plus large, $2/\lVert w \rVert$, en minimisant $\tfrac12 \lVert w \rVert^{2}$ sous une contrainte par point ; la marge souple ajoute une perte charnière au prix $C$.
2. Dans le dual, $w = \sum_i \alpha_i y_i x_i$ et les points hors de la bande ont $\alpha_i = 0$ : seuls les vecteurs de support dessinent la frontière.
3. Comme le dual ne voit les données qu'à travers des produits scalaires, tout noyau dont les matrices de Gram sont semi-définies positives peut les remplacer ; le $\gamma$ du noyau RBF règle la portée de chaque point.
4. Le ridge à noyau résout $\alpha = (K + \lambda I)^{-1} y$ en un seul système linéaire mais garde tous les points d'apprentissage : standardiser d'abord, et approcher le noyau quand $n$ est grand.
5. Un arbre choisit chaque coupe par la plus forte baisse d'impureté pondérée ; une coupe qui recopie les proportions du parent ne gagne rien.
6. Un arbre sans limite apprend le bruit, un arbre court est lisible mais instable, et l'importance par impureté favorise les variables qui offrent beaucoup de seuils.

Glossaire

machine à vecteurs de support (support vector machine, SVM)

Classifieur qui garde la frontière de marge la plus large, assouplie par un prix sur les violations.

vecteurs de support (support vectors)

Les points d'apprentissage sur le bord de la marge ou à l'intérieur ; les seuls dont le poids dual est non nul.

perte charnière (hinge loss)

La perte $\max(0, 1 - y f(x))$, nulle pour un point du bon côté avec une avance d'au moins 1.

astuce du noyau (kernel trick)

Remplacer chaque produit scalaire par un noyau, produit scalaire dans un espace plus grand calculé sans le construire.

matrice de Gram (Gram matrix)

La matrice $n \times n$ des valeurs du noyau sur toutes les paires, semi-définie positive pour un noyau valide.

ridge à noyau (kernel ridge regression)

Le ridge sous forme duale avec un noyau, un poids par point d'apprentissage.

arbre de décision (decision tree)

Modèle de questions de seuil emboîtées sur une variable à la fois ; chaque feuille est une boîte de l'espace des entrées.

impureté de Gini (Gini impurity)

La quantité $1 - \sum_k p_k^{2}$, probabilité que deux points tirés dans un nœud soient de classes différentes.

élagage coût-complexité (cost-complexity pruning)

Faire pousser l'arbre complet, puis garder le sous-arbre qui minimise l'erreur d'apprentissage plus un prix par feuille.

importance par impureté (mean decrease in impurity, MDI)

L'importance intégrée d'un arbre, biaisée vers les variables qui offrent beaucoup de seuils.

Les autres fiches du cours

Un résumé public par deck, dans l'ordre du cours.

Précédent : Un modèle de référence défendableSuivant : Forêts, boosting, comparaison honnête

1. IntroductionHivers de l'IA, emploi et méthode
2. OutilsKaggle, GitHub, Python : les outils
3. Séance 1Cadrage de projet et moindres carrés
4. Séance 2Vraisemblance et régression logistique
5. Séance 3Descente de gradient, ridge et lasso
6. Séance 4Seuil de décision et ML reproductible
7. DevoirUn modèle de référence défendable
8. Séance 5Noyaux, SVM et arbres de décision
9. Séance 6Forêts, boosting, comparaison honnête
10. Séance 7SHAP, équité, ACP et partitionnement
11. DevoirUn modèle champion documenté
12. Séance 8Réseaux de neurones, dérive, prédiction conforme
13. DevoirUn projet de machine learning livré
14. Séance 9Soutenir un projet de machine learning
15. RéférenceProjet de score de défaut de crédit
16. RéférenceRendements boursiers : XGBoost et sentiment
17. RéférenceLe code Python de chaque modèle
18. RéférenceDeep learning, l'essentiel
19. RéférenceDonnées ouvertes et projets par secteur
20. RéférenceManuel de l'expert data et IA
21. RéférenceData engineering, SRE et cloud
22. RéférencePanorama des modèles de machine learning

Toutes les fiches, en liste de lecture

L'attention et le transformer, pas à pas

À propos de ces fiches

Écrites par l'enseignant à partir des slides du deck, comme un résumé public : les idées clés, les formules et un exemple calculé. Les exercices, leurs corrigés, les contrôles et la notation restent dans le deck, pour les élèves du cours.

Révision : 16 octobre 2026.