- Proportion et moyenne pondérée. Un nœud à n observations dont n+ positives a pour proportion p = n+/n. Si on le coupe en deux enfants de poids w et 1−w, la proportion du parent est la moyenne pondérée des proportions des enfants : p = w pL + (1−w)pR.
- Concavité. φ est strictement concave si sa corde est strictement sous sa courbe : φ(w a + (1−w)b) > w φ(a) + (1−w)φ(b) dès que a ≠ b (inégalité de Jensen, cas strict). Convexe : l'inégalité inverse.
- Gradient = signal. En descente de gradient, un paramètre bouge de −η·∂L/∂θ ; là où la dérivée est nulle, il ne bouge pas (p03-02).
- La loss est la trace du bruit (fil B, D4) : log-loss ← Bernoulli, MSE ← gaussienne. Ici on ne redérive pas les losses, on compare leur pente.
La chaîne
Le décor
Un nœud parent de 800 observations, moitié positives. Deux splits candidats, aucune contrainte de profondeur. La question de CART : lequel des deux est le meilleur ?
« Le critère doit ranger S1 et S2. S'il leur donne la même valeur, il ne sert à rien. »
Parent : 400 + / 400 −, p = 0,5.
| split | enfant gauche | enfant droit |
|---|---|---|
| S1 | 300 + / 100 − (pL = 0,75, n = 400) | 100 + / 300 − (pR = 0,25, n = 400) |
| S2 | 200 + / 400 − (pL = 1/3, n = 600) | 200 + / 0 − (pR = 1, n = 200) |
S2 produit une feuille pure. Intuitivement il sépare mieux. On va voir quel critère le voit.
Le critère naïf : l'accuracy
Chaque enfant prédit sa classe majoritaire ; son erreur est la proportion minoritaire. Le critère d'un nœud est donc
et le gain d'un split est e(p) − [w e(pL) + (1−w)e(pR)].
« L'erreur d'un nœud est sa proportion minoritaire, donc le gain compare l'erreur du parent à l'erreur pondérée des enfants. »
Parent : 400 erreurs sur 800, e = 0,5.
| split | erreurs gauche | erreurs droite | total | gain |
|---|---|---|---|---|
| S1 | 100 | 100 | 200 | 0,25 |
| S2 | 200 | 0 | 200 | 0,25 |
Égalité. Une feuille pure et deux feuilles à 75 % valent exactement pareil pour l'accuracy. Le critère ne départage pas.
Pourquoi l'accuracy est muette tronc
e(p) = min(p, 1−p) est une tente : affine de chaque côté de ½ (pente +1 puis −1), un seul angle au sommet. Sur un segment linéaire, la corde est sur la courbe : la moyenne pondérée des erreurs des enfants est exactement l'erreur du parent.
Conséquence : le gain n'est strictement positif que si un enfant traverse ½, c'est-à-dire change de classe majoritaire. Tout split qui purifie sans faire basculer une majorité a un gain exactement nul. C'est un critère en escalier : il ne voit que les basculements.
« L'erreur est linéaire de chaque côté de ½, donc la corde entre deux enfants du même côté passe par le parent, donc le gain est nul tant qu'aucune majorité ne bascule, donc l'accuracy ne voit pas une purification. »
Parent 7 + / 3 −. Split : (4 + / 2 −) et (3 + / 1 −). Les deux enfants restent majoritairement +.
Erreurs : parent 3 ; enfants 2 + 1 = 3. Gain = 0. Pourtant l'enfant droit est à 75 % contre 70 % au parent : le split a fait quelque chose, le critère dit « rien ».
Sur S1 et S2 : les enfants de S1 sont à 0,75 et 0,25, de part et d'autre de ½ ; ceux de S2 à 1/3 et 1. Dans les deux cas une majorité bascule et le gain vaut 0,25 — l'accuracy compte les basculements, pas l'ampleur.
Chaque critère est une fonction de la proportion p. Le point plein est le parent, les deux points vides sont les enfants, le pointillé rouge est la corde entre eux, et le segment vert est le gain : la hauteur entre la courbe et la corde, lue en p. Déplace pL, pR, w : tant que les deux enfants restent du même côté de ½, le gain en accuracy reste à zéro alors que Gini et entropie bougent.
Le critère sensible : un dôme tronc
Gini et entropie sont des dômes, strictement concaves sur ]0,1[ :
Lecture de Gini en deux tirages : tirer un individu du nœud, lui attribuer une étiquette tirée au hasard selon les proportions ; Gini = probabilité de se tromper = p(1−p) + (1−p)p. Entropie = surprise moyenne, −log de la probabilité de ce qu'on observe, en espérance.
Jensen strict : φ(w pL + (1−w)pR) > w φ(pL) + (1−w)φ(pR) dès que pL ≠ pR. Le membre de gauche est l'impureté du parent, le membre de droite celle des enfants : le gain est strictement positif pour tout split qui change les proportions, et il croît avec l'écartement des enfants.
« Gini et l'entropie sont strictement concaves, donc la corde entre deux enfants distincts passe sous la courbe, donc l'impureté pondérée des enfants est strictement sous celle du parent, donc tout split qui sépare est vu, et plus il sépare plus il est vu. »
Gini, parent : 2·0,5·0,5 = 0,5.
| split | gauche | droite | pondéré | gain |
|---|---|---|---|---|
| S1 | 2·0,75·0,25 = 0,375 | 0,375 | 0,375 | 0,125 |
| S2 | 2·(1/3)(2/3) = 0,444 | 0 | 0,75·0,444 + 0,25·0 = 0,333 | 0,167 |
Entropie (bits), parent 1 : S1 → 0,811, gain 0,189 ; S2 → 0,75·0,918 = 0,689, gain 0,311. Les deux critères préfèrent S2, celui qui produit la feuille pure.
Split 7/3 sans basculement : Gini 0,42 → 0,417, gain 0,003 > 0. Petit, mais non nul : l'arbre peut le ranger.
Pourquoi c'est légitime : un surrogate
On n'optimise pas l'impureté pour elle-même. Elle mesure le progrès intermédiaire vers une feuille pure, et chaque dôme est une loss connue lue au niveau du nœud : l'entropie d'un nœud est la log-loss moyenne de la prédiction « proportions du nœud », Gini est son score de Brier. Les deux sont indépendantes d'un seuil de décision — l'accuracy ne l'est pas.
« L'impureté est une loss de probabilité évaluée sur le nœud, donc elle mesure un progrès même quand la décision ne change pas, donc on la prend comme critère de split, et on garde le taux d'erreur pour évaluer et pour élaguer. »
Nœud à p = 0,75 prédisant (0,75 ; 0,25) : log-loss moyenne = −0,75 log 0,75 − 0,25 log 0,25 = H(0,75) ; Brier moyen = 0,75·(1−0,75)² + 0,25·(0−0,25)² = 0,1875 = G(0,75)/2.
Élagage et évaluation : le taux d'erreur (ou la métrique métier) convient, parce qu'on mesure, on n'apprend plus.
Le même argument, écrit en pente
Reformulé pour qu'il se transporte : la variation d'un critère sous une petite amélioration est sa dérivée. Une fonction en marches a une dérivée nulle presque partout — aucun signal entre deux marches. Une fonction strictement concave (ou convexe) et dérivable a une dérivée qui change continûment : chaque amélioration, même petite, déplace le critère.
Pour un split, l'objet qui bouge est p ; pour un classifieur, c'est β ; pour une pénalité, c'est θ ; pour une SVM, c'est la marge. Quatre habits, une règle.
« Un critère n'informe l'apprentissage que par sa pente, donc un critère en marches est muet presque partout, donc on optimise un critère strictement concave ou convexe même si la quantité qu'on rapporte à la fin est l'accuracy. »
| habit | ce qui bouge | critère en escalier | critère sensible |
|---|---|---|---|
| split d'arbre | p | accuracy | Gini, entropie |
| loss de classification | β | 0/1 loss | log-loss |
| pénalité | θ | L2 près de 0 | L1 |
| SVM | marge | hinge au-delà de 1 | hinge en deçà de 1 |
Lis la colonne « escalier » comme « là où la pente est nulle ». Pour L2 et la hinge, ce n'est pas partout : c'est une zone, et c'est exactement cette zone qui explique leur comportement.
Habit 2 — la loss d'un classifieur
Marge m = y·z avec z = β⊤x et y ∈ {−1,+1} : positive si bien classé, négative sinon.
La 0/1 loss compte les erreurs — c'est l'accuracy du côté des paramètres. Sa dérivée en β est nulle partout sauf sur la frontière : la descente de gradient ne reçoit rien. La log-loss a pour dérivée −σ(−m), jamais nulle, décroissante en |m| : un point mal classé pousse fort, un point bien classé pousse encore un peu.
« La 0/1 loss est en marches en β, donc son gradient est nul presque partout, donc rien n'apprend ; la log-loss est convexe et dérivable, donc chaque point envoie un gradient proportionnel à son degré d'erreur. »
Un point avec m = −2 (franchement mal classé) : 0/1 loss = 1, pente 0. Log-loss = log(1+e²) = 2,13, pente −σ(2) = −0,88. Le point tire fort.
m = +2 (bien classé) : 0/1 = 0, pente 0. Log-loss = 0,13, pente −σ(−2) = −0,12. Il tire encore, faiblement — c'est ce qui fait fuir β vers l'infini sous séparation parfaite (D4, exemple 2).
Deux étages. Par la chain rule, ∂loss/∂z = ∂loss/∂p × ∂p/∂z, et ∂p/∂z = p(1−p) écrase tout près de 0 et de 1. Log-loss, y = 1 : (−1/p) × p(1−p) = −(1−p) : le −1/p du log compense l'écrasement, gradient p − y, maximal quand l'erreur est maximale. MSE : 2(p−y) × p(1−p) : rien ne compense, le gradient meurt là où l'erreur est maximale (D4).
Signe. Le paramètre bouge de −η × pente. Pente négative en m ⇒ la marge augmente : on descend la loss en montant la marge.
Déplace la marge m d'un point. Les traits épais sont les pentes locales : nulles pour la 0/1 loss partout, nulle pour la hinge au-delà de m = 1, jamais nulle pour la log-loss. Là où la pente est nulle, ce point n'influence plus β.
Habit 3 — la pénalité
Minimiser L(θ) + λ·pen(θ) — la loss sans ½, la pénalité pesée par λ seul. La force de rappel vers 0 est la dérivée de la pénalité :
L2 est sensible partout sauf près de 0, où sa pente s'évanouit : le poids ralentit sans jamais arriver. L1 garde une pente constante jusqu'à 0 : le poids arrive. Et il y reste : en 0, |θ| a un coude, la pénalité tire vers 0 depuis les deux côtés avec la force λ — un mur des deux côtés. Le poids ne repart que si la loss pousse plus fort que λ : |L′(0)| > λ. C'est la même règle lue à l'envers : là où la pente de la loss est trop faible, c'est le mur qui gagne.
« La pénalité tire avec sa dérivée, donc L2 tire de moins en moins près de zéro et le poids n'y arrive jamais, donc L1 tire à force constante et le poids atteint exactement zéro dès que la loss ne pousse plus plus fort que λ. »
Loss L(θ) = (θ − 1)² : les données veulent θ = 1. Sa pente en 0 vaut L′(0) = −2, donc |L′(0)| = 2 — c'est le seuil que λ doit franchir.
| λ | L2 | L1 |
|---|---|---|
| 0,5 | 0,667 | 0,75 |
| 1 | 0,5 | 0,5 |
| 2 | 0,333 | 0 |
| 8 | 0,111 | 0 |
L2 tend vers 0 sans l'atteindre ; L1 y est exactement dès λ ≥ 2 — c'est-à-dire dès que le mur λ égale la poussée |L′(0)| = 2. Sur p paramètres, c'est la sélection de variables du Lasso.
Les deux critères pénalisés L(θ) + λ·pen(θ) en fonction de θ, avec leur minimum. Monte λ : le minimum L2 glisse vers 0 en ralentissant et n'y arrive jamais, le minimum L1 arrive en 0 à λ = 2 et s'y colle — c'est l'angle de |θ| qui le retient, dès que le mur égale la poussée |L′(0)| = 2.
Habit 4 — la marge (demi-chaîne SVM)
SVM linéaire : minimiser ½‖w‖² + C Σi max(0, 1 − yi(w⊤xi + b)). La marge géométrique vaut 2/‖w‖ : minimiser ‖w‖ l'élargit.
La hinge a une pente nulle pour m ≥ 1 : un point bien classé au-delà de la marge n'envoie aucun gradient. Seuls les points avec m ≤ 1 — sur la marge ou du mauvais côté — portent la solution : les vecteurs de support. La solution s'écrit w = Σ αiyixi avec αi = 0 hors support.
Kernel trick. Prédiction et entraînement ne touchent les x que par des produits scalaires xi⊤x ; on remplace chacun par K(xi, x) = ⟨φ(xi), φ(x)⟩ sans jamais calculer φ. RBF : frontière non linéaire en O(nsupport) par prédiction.
« La hinge est nulle au-delà de la marge, donc les points bien classés ne portent aucun gradient, donc la frontière ne dépend que des vecteurs de support ; et comme tout passe par des produits scalaires, un noyau les remplace et rend la frontière non linéaire. »
| logistique | SVM | |
|---|---|---|
| loss | log-loss, pente jamais nulle | hinge, nulle au-delà de la marge |
| qui décide de la frontière | tous les points, pondérés | les vecteurs de support seuls |
| probabilités | natives (à calibrer quand même) | non ; Platt après coup |
| non-linéaire | features explicites | noyau, sans expliciter φ |
| préférer quand | on veut des probas ; n grand | n petit/moyen, frontière courbe, marge claire |
Frontières souvent proches ; la différence est dans ce qui les porte. La question d'entretien est rarement « SVM ou logistique », c'est « pourquoi la hinge est-elle creuse ».
Deux classes, l'hyperplan et ses deux marges. Les points cerclés sont les vecteurs de support (m ≤ 1) ; retire un point hors support, la frontière ne bouge pas ; retire un vecteur de support, elle se recalcule.
Où ça casse casse
« Sensible » n'est pas « meilleur partout ».
« Un critère sensible transmet tout, donc il transmet aussi le bruit ; c'est pour cela qu'on borne parfois sa pente — Huber, hinge — et qu'on rapporte à la fin une métrique en marches. »
- La log-loss n'est pas bornée. Une erreur confiante (m = −10) coûte 10 et tire à pente presque 1 : un label bruité déplace la frontière. La hinge et Huber bornent l'influence d'un point. Sensible partout ⇒ sensible aux outliers.
- Séparation parfaite. Pente jamais nulle ⇒ ‖β‖ → ∞ (D4, ex. 2). La pénalité rend le minimum existant. Pas un défaut du critère, une conséquence de sa sensibilité.
- Gini vs entropie : même concavité, même ordre des splits dans presque tous les cas. Le choix entre les deux est un détail d'implémentation ; le choix accuracy vs concave est structurel.
- Le critère optimisé n'est pas la métrique rapportée. On entraîne sur la log-loss et on rapporte une accuracy, un F1, un rappel à un seuil : des fonctions en marches, parfaites pour évaluer, muettes pour apprendre. Ne pas confondre les deux rôles.
Résumé
- Un critère n'informe l'apprentissage que par sa pente. Pente nulle = pas de signal.
- Accuracy et 0/1 loss sont en marches : gain nul sans basculement de majorité, gradient nul presque partout.
- Gini, entropie, log-loss sont des dômes (strictement concaves / convexes) : tout écart se voit (Jensen strict). Légitimes comme surrogates : entropie = log-loss du nœud, Gini = Brier.
- La pente de L2 s'évanouit en 0 (jamais de zéro exact) ; celle de L1 est constante (zéros exacts).
- La hinge est plate au-delà de la marge : seuls les vecteurs de support portent la SVM ; le noyau remplace les produits scalaires.
- Sensible = transmet aussi le bruit : Huber, hinge bornent ; on évalue avec des métriques en marches, on n'apprend pas avec.
Chaîne verbalisée — une prise, à voix haute
- Pourquoi CART ne choisit-il pas ses splits à l'accuracy ?Erreur = min(p, 1−p), linéaire par morceaux : gain exactement nul tant qu'aucun enfant ne traverse ½.
- Pourquoi Gini et l'entropie voient-elles tout split, et pourquoi c'est légitime ?Dômes : corde sous la courbe (Jensen strict), impureté pondérée des enfants < parent dès que pL ≠ pR. Légitime : surrogate — entropie = log-loss du nœud, Gini = Brier ; on élague au taux d'erreur.
- Même argument côté loss : pourquoi la log-loss et pas la 0/1 loss ?La 0/1 loss a un gradient nul presque partout en β ; la log-loss a pour pente −σ(−m), jamais nulle, proportionnelle à l'erreur.
- Même argument côté pénalité : pourquoi L1 met des zéros exacts ?Pente de θ² → 0 près de 0 (le poids n'arrive jamais) ; pente de |θ| = ±1 constante (le poids arrive) ; coude en 0 = mur des deux côtés de force λ (il reste tant que |L′(0)| ≤ λ).
- Même argument côté SVM : qui porte la frontière ?Hinge plate pour m ≥ 1 ⇒ gradient nul pour les points bien classés ⇒ seuls les vecteurs de support (m ≤ 1) comptent.
Ponts et cartes
Cartes du 16/09 : Gini vs taux d'erreur, accuracy comme loss, cloze Gini/entropie (deux tirages, pont log-loss), MSE vs log-loss (Brier), L1 — le coude, Wilson.
ml::arbres (critère de split CART, Gini vs accuracy) · ml::logistique (pas de forme fermée, gradient de la BCE) · stats::regularisation (L1 zéros exacts, L2 ressort) · dl::cross-entropy (gradient p − y) · ml::svm (hinge, vecteurs de support, noyau — à créer).
Une carte qui résiste après cette chaîne est une carte à refondre, pas une section à relire.