- Tente vs dôme. L'erreur de classification e(p) = min(p, 1−p) est une tente : affine de chaque côté de ½, donc gain de split exactement nul tant qu'aucun enfant ne change de classe majoritaire. Gini G(p) = 2p(1−p) et l'entropie sont des dômes strictement concaves, donc tout split qui sépare se voit (p03-01, pas 3 et 4). On ne le redémontre pas ici : on l'utilise.
- Gini = deux tirages. Tirer un individu du nœud, lui coller une étiquette tirée selon les proportions du nœud : Gini est la probabilité de se tromper. Entropie = surprise moyenne.
- Surrogate. L'impureté sert à apprendre, le taux d'erreur à mesurer — entropie = log-loss du nœud, Gini = son score de Brier (p03-01, pas 5).
- Le tirage, c'est le dataset. Un modèle réentraîné sur un autre échantillon de la même population est un autre modèle ; l'ampleur de ce changement est sa variance (p06-01, pas 2), et le compromis se lit sur un U.
- Proportion et moyenne pondérée. La proportion d'un parent est la moyenne pondérée des proportions de ses enfants, poids = effectifs (p00-03, pas 6).
La chaîne
Le décor
Un arbre pose des questions « xj ≤ t ? » et range chaque point dans une feuille, qui prédit la classe majoritaire de ce qu'elle contient. Tout l'apprentissage se réduit à deux décisions locales — quelle feature, quel seuil — et à une décision globale : quand s'arrêter.
Les trois pas suivants traitent les deux premières, les pas 5 et 6 la troisième.
« Un arbre range chaque point dans une feuille par une suite de questions, donc tout ce qu'il apprend tient dans le choix d'un couple (feature, seuil) à chaque nœud, donc il lui faut un critère qui compare des coupures. »
Une seule feature x, huit points, huit valeurs distinctes :
| x | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| étiquette | + | + | − | + | − | − | + | − |
Parent : 4 + / 4 −, donc p = 0,5, Gini = 2·0,5·0,5 = 0,5 et erreur de classification = min(0,5 ; 0,5) = 0,5.
Huit valeurs distinctes ⇒ sept seuils candidats, un entre chaque paire de points consécutifs : 1,5 · 2,5 · 3,5 · 4,5 · 5,5 · 6,5 · 7,5.
Le critère : la baisse d'impureté tronc
Pour chaque couple (feature, seuil), on calcule l'impureté du parent moins l'impureté pondérée par les effectifs des deux enfants :
On garde le couple de gain maximal. Gini par défaut, entropie presque équivalente ; l'erreur de classification, elle, est une tente et ne départage pas (p03-01).
« L'arbre compare toutes les coupures par la baisse d'impureté, donc il lui faut un critère qui voit une purification sans basculement de majorité, donc un dôme strictement concave, donc Gini ou l'entropie. »
| seuil | gauche | droite | Gini pondéré | gain Gini | gain erreur |
|---|---|---|---|---|---|
| 1,5 | 1 + / 0 − | 3 + / 4 − | 0,429 | 0,071 | 0,125 |
| 2,5 | 2 + / 0 − | 2 + / 4 − | 0,333 | 0,167 | 0,250 |
| 3,5 | 2 + / 1 − | 2 + / 3 − | 0,467 | 0,033 | 0,125 |
| 4,5 | 3 + / 1 − | 1 + / 3 − | 0,375 | 0,125 | 0,250 |
| 5,5 | 3 + / 2 − | 1 + / 2 − | 0,467 | 0,033 | 0,125 |
| 6,5 | 3 + / 3 − | 1 + / 1 − | 0,500 | 0 | 0 |
| 7,5 | 4 + / 3 − | 0 + / 1 − | 0,429 | 0,071 | 0,125 |
CART coupe à 2,5 : gauche {1, 2} pure, droite 2 + / 4 −.
L'accuracy ne départage pas. Le gain en erreur de classification vaut 0,250 à 2,5 et à 4,5 : deux coupures ex æquo au sommet, alors que Gini les sépare nettement (0,167 contre 0,125). À 6,5, les deux enfants sont à 50/50 : les deux critères disent 0.
En bas, les huit points avec leur étiquette ; la barre verticale est la coupure. Les deux courbes sont le gain en fonction du seuil : violet pour Gini, ambre pour l'erreur de classification. Balaie le seuil : la courbe ambre a deux sommets à la même hauteur (2,5 et 4,5) — l'accuracy ne sait pas choisir ; la courbe violette a un sommet unique en 2,5, la coupure qui produit une feuille pure.
La recherche : trier, puis balayer
Par feature : trier les valeurs, puis balayer les seuils entre valeurs consécutives en mettant à jour deux compteurs (effectif à gauche, positifs à gauche). Chaque gain se lit alors en O(1) : O(n log n) par feature et par nœud, le tri domine.
Le gain ne dépend que de la façon dont les points se répartissent de part et d'autre du seuil — donc de leur ordre seul, jamais de leurs valeurs.
« Le gain ne dépend que du partage des points de part et d'autre du seuil, donc seul l'ordre des valeurs compte, donc aucune transformation monotone ne change l'arbre, donc standardiser ou passer au log avant un arbre ne sert à rien. »
Sur le fil rouge : 8 valeurs triées, 7 seuils, 7 évaluations de gain en O(1) chacune une fois les compteurs en place. À chaque pas du balayage, le compteur « positifs à gauche » fait +1 ou +0 ; rien d'autre n'est recalculé.
Invariance monotone, vérifiée. Remplacer x = 1…8 par log x, par x³, ou par les rangs 1…8 : les mêmes points restent de part et d'autre de chaque coupure, donc les sept gains sont inchangés, seul le nombre écrit dans le nœud change. C'est pourquoi un pipeline d'arbres n'a pas de StandardScaler.
Coût d'un nœud à d features : d·n log n. C'est ce coût, répété à chaque nœud, que les implémentations (histogrammes de LightGBM, pré-tri de XGBoost) attaquent.
Glouton et axe par axe tronc
Glouton (H2) : on prend la meilleure coupure maintenant. Une coupure médiocre qui préparerait une excellente suivante n'est jamais essayée — l'arbre ne regarde jamais deux coups plus loin.
Axe par axe (H1) : chaque coupure est parallèle à un axe. Une frontière diagonale n'est pas approchable par une coupure, seulement par un escalier de coupures.
« Chaque nœud choisit sa coupure sans regarder la suite, donc un arbre rate les structures qui n'apparaissent qu'à deux coupures, donc un XOR ou une diagonale lui coûtent cher. »
XOR : gain exactement nul. 40 points en quatre paquets de 10 aux coins d'un carré, étiquette = XOR des deux coordonnées. Parent 20 + / 20 −, Gini 0,5. Toute coupure sur x sépare les coins en deux groupes de 10 + et 10 − : Gini 0,5 à gauche, 0,5 à droite, pondéré 0,5.
Aucune première coupure ne gagne quoi que ce soit, alors que deux coupures séparent parfaitement. Le glouton est aveugle exactement là.
Diagonale : le prix de l'escalier. Frontière y = x sur le carré unité. Un escalier de k marches égales laisse k triangles d'aire ½(1/k)², soit une erreur d'aire 1/(2k). Pour 1 % d'erreur il faut k = 50 marches, donc au moins 51 feuilles — là où une seule droite suffirait.
Jusqu'où couper : la profondeur est la variance tronc
Sans limite, l'arbre coupe tant qu'une feuille est impure. Comme chaque coupure sépare, il finit par isoler les points : erreur d'entraînement 0, sauf si deux points ont les mêmes features et des étiquettes opposées — alors aucune question ne les sépare et le plancher est atteint.
Un tel arbre a mémorisé le tirage : sur un autre échantillon de la même population, ses coupures sont ailleurs et sa prédiction change entièrement. Profondeur maximale, taille minimale de feuille, nombre de feuilles : ce sont trois écritures du même bouton de variance (p06-01).
« Un arbre profond a une feuille par point, donc il reproduit le bruit du tirage, donc sa variance est maximale, donc limiter la profondeur ou la taille des feuilles est le réglage de variance. »
Fil rouge, sans doublon. Les huit valeurs de x sont distinctes, donc sept coupures isolent les huit points : erreur d'entraînement 0, huit feuilles, profondeur au plus 7.
Avec un doublon contradictoire. Ajouter un neuvième point en x = 3 étiqueté + — il y a déjà un − en x = 3. Aucun seuil ne passe entre deux points de même abscisse : ils tombent dans la même feuille quoi qu'il arrive, et cette feuille se trompe sur l'un des deux. Erreur d'entraînement minimale = 1/9 ≈ 0,111, jamais 0.
Sur le nuage de la figure 2 (40 points) : erreur d'entraînement 0,250 à profondeur 1 · 0,175 à 2 · 0,125 à 3 · 0,050 à 4 · 0 dès la profondeur 6. Ce zéro ne dit rien de la qualité du modèle — il dit seulement que l'arbre a fini de recopier.
40 points, deux classes (bleu plein = +, rouge creux = −), frontière vraie en pointillé et 12 % d'étiquettes retournées. Coupure suivante : à chaque clic l'arbre ajoute la coupure gloutonne de plus grand gain pondéré, et le pavage en rectangles se dessine. Jusqu'au bout : les feuilles deviennent pures et l'erreur d'entraînement tombe à zéro. Puis nouveau tirage : même population, même algorithme, autre échantillon — le pavage change du tout au tout. C'est cela, la variance.
Élagage : couper après coup, sur un autre critère
L'impureté décroît à chaque coupure par construction : elle ne peut donc pas dire quand s'arrêter. La recette est de faire pousser à fond puis de couper, en évaluant chaque sous-arbre au taux d'erreur (ou au RSS) sur des données non vues — on mesure, on n'apprend plus (p03-01, pas 5).
Le nom de la procédure est l'élagage coût-complexité : on pénalise le nombre de feuilles par un α choisi en validation. Ce que α parcourt est le U de p06-01.
« L'impureté sert à choisir une coupure, donc elle décroît à chaque coupure par construction, donc elle ne peut pas dire quand s'arrêter, donc on tranche au taux d'erreur mesuré sur des données non vues. »
Même population que la figure 2, 40 points d'entraînement, moyenne sur 40 tirages, erreur mesurée sur 2000 points non vus :
| profondeur | erreur train | erreur test |
|---|---|---|
| 1 | 0,229 | 0,292 |
| 2 | 0,118 | 0,182 |
| 3 | 0,078 | 0,218 |
| 4 | 0,036 | 0,235 |
| 6 | 0,009 | 0,243 |
| 12 | 0,000 | 0,244 |
L'erreur d'entraînement descend jusqu'à 0 sans jamais remonter : elle ne contient aucune information sur où s'arrêter. L'erreur test, elle, a un minimum net à la profondeur 2 et remonte de 0,182 à 0,244 ensuite — c'est la variance qu'on paie.
Le plancher. 12 % des étiquettes sont retournées au hasard : aucune profondeur ne descend sous ≈ 0,11 en test. Un gap train−test de 0,244 à profondeur 12 n'est donc pas « 24 % de progrès possible », c'est 13 points de variance et 11 points de bruit irréductible.
Erreur d'entraînement (bleu) et erreur de test (rouge) en fonction de la profondeur maximale, simulées sur le nuage de la figure 2. Déplace la profondeur : la courbe bleue ne remonte jamais, la rouge passe par un minimum puis remonte. La ligne horizontale est le plancher de bruit, que personne ne franchit. La profondeur est le bouton de variance ; l'élagage, c'est chercher le creux de la courbe rouge sur des données non vues.
Régression : le même geste, avec la variance
Même algorithme, une seule substitution : l'impureté d'un nœud devient la variance de ses y, et la feuille prédit leur moyenne.
La prédiction est donc constante par morceaux : une marche par feuille. Elle ne sort jamais de l'intervalle des y vus, et ne prolonge aucune tendance.
« La feuille prédit la moyenne de ses y, donc l'impureté qui minimise l'erreur quadratique est la variance du nœud, donc le même balayage marche, donc la prédiction est une marche constante et ne sort jamais du support des y vus. »
x = 1…6, y = 1, 2, 3, 10, 11, 12. Moyenne 6,5 ; variance du parent = 251/12 ≈ 20,917.
| seuil | gauche (moy · var) | droite (moy · var) | var pondérée | gain |
|---|---|---|---|---|
| 1,5 | 1 · 0 | 7,6 · 17,84 | 14,87 | 6,05 |
| 2,5 | 1,5 · 0,25 | 9 · 12,5 | 8,417 | 12,5 |
| 3,5 | 2 · 0,667 | 11 · 0,667 | 0,667 | 20,25 |
| 4,5 | 4 · 12,5 | 11,5 · 0,25 | 8,417 | 12,5 |
| 5,5 | 5,4 · 17,84 | 12 · 0 | 14,87 | 6,05 |
La coupure à 3,5 emporte tout : elle sépare le paquet bas du paquet haut, et il ne reste que 0,667 de variance intérieure.
Pas d'extrapolation. La feuille droite prédit 11 pour x = 5, pour x = 6 et pour x = 1000. Aucune valeur en dehors de [1 ; 12] n'est atteignable, quelle que soit la profondeur : un arbre de régression interpole en marches, il ne suit pas une tendance.
Ce qu'un arbre sait faire — et ce qu'il paie
Sans qu'on écrive quoi que ce soit : seuils et interactions (deux coupures sur deux features en descendance, c'est un produit croisé), features numériques et catégorielles mêlées, aucune standardisation (pas 3), valeurs manquantes traitées par coupures de substitution. À faible profondeur, l'arbre s'écrit en phrases — c'est le seul modèle de cette formation qu'on lit à voix haute.
Le prix est l'instabilité : déplacer un point change la première coupure, et tout ce qui en descend est recalculé.
« Un arbre ne suppose ni forme fonctionnelle ni échelle, donc il attrape seuils et interactions sans qu'on les écrive, donc ce qu'il paie est l'instabilité : un point qui bouge change la première coupure et tout l'arbre en dessous. »
Fil rouge, on retire le point x = 3 (le seul − au milieu des +). Il reste 4 + / 3 −, Gini du parent 0,490.
| meilleure coupure | gain Gini | feuille gauche | |
|---|---|---|---|
| 8 points | 2,5 | 0,167 | {1, 2} pure |
| sans le point 3 | 4,5 | 0,276 | {1, 2, 4} pure |
Un point sur huit retiré, et la racine change : tous les sous-arbres changent avec elle. L'arbre n'est pas légèrement différent, il est autre. Deux conséquences : ne pas sur-interpréter un arbre unique, et faire la moyenne de plusieurs arbres — c'est exactement ce que répare le bagging (p07-02).
Où ça casse casse
Les quatre limites viennent toutes des trois hypothèses : axe par axe, glouton, impureté.
« Les défauts d'un arbre sont ses hypothèses lues à l'envers, donc on les répare en changeant de représentation ou en moyennant, donc jamais en augmentant la profondeur. »
- XOR et diagonales (H1 + H2). Le glouton ne voit pas ce qui ne se révèle qu'à deux coupures : sur un XOR pur, gain nul partout (pas 4). Les ensembles compensent en partie parce qu'ils explorent d'autres premières coupures — mais aucune forêt ne tourne les axes : une frontière diagonale reste un escalier.
- Extrapolation impossible (H3, régression). Hors du support des x d'entraînement, la prédiction est la marche du bord. Un arbre ne prolonge jamais une tendance — pour une série temporelle qui dérive, il prédit le dernier palier et se trompe indéfiniment.
- Instabilité (H2). Un point retiré et la racine change (pas 8). L'importance des features d'un arbre unique, comme sa lecture « en phrases », est à prendre avec prudence : c'est une lecture de ce tirage, pas de la population.
- Classes déséquilibrées (H3). Sur 99 % / 1 %, un nœud à 1 % de positifs a une impureté Gini de 0,020 : presque pure, donc presque rien à gagner à le couper. Le critère de split lui-même défavorise la minorité, et le vote majoritaire de la feuille l'achève. Réponses : poids de classe dans l'impureté, ou seuil de décision déplacé après coup (p06-04).
Résumé
- Une coupure est un couple (feature, seuil) qui maximise la baisse d'impureté pondérée par les effectifs. Gini, un dôme — pas l'accuracy, une tente qui laisse 2,5 et 4,5 ex æquo.
- Recherche par tri puis balayage, O(n log n) par feature et par nœud : seul l'ordre des valeurs compte, donc aucune standardisation.
- Glouton et axe par axe : gain exactement nul sur un XOR, et 50 marches pour approcher une diagonale à 1 %.
- La profondeur est la variance. Sans limite : erreur train 0 (sauf doublons contradictoires, plancher 1/n) et mémorisation du tirage. Profondeur, taille de feuille, nombre de feuilles = un seul bouton.
- Élagage au taux d'erreur sur validation, jamais à l'impureté : elle décroît par construction. Coût-complexité = pénaliser le nombre de feuilles, α choisi en validation.
- Régression : impureté = variance du nœud, feuille = moyenne, prédiction en marches, aucune extrapolation hors de [min y ; max y].
Chaîne verbalisée — une prise, à voix haute
- Comment CART choisit-il une coupure ?Pour chaque feature et chaque seuil, la baisse d'impureté du parent à l'impureté pondérée des enfants ; il garde la plus grande.
- Pourquoi Gini et pas l'accuracy ?Dôme contre tente : sur les huit points, 2,5 et 4,5 sont à égalité en accuracy (0,250) alors que Gini les sépare (0,167 contre 0,125).
- Pourquoi ne pas standardiser avant un arbre ?Le gain ne dépend que du partage des points autour du seuil, donc seul l'ordre des valeurs compte : toute transformation monotone laisse l'arbre identique.
- Que rate un arbre glouton ?Ce qui ne se révèle qu'à deux coupures : XOR (gain exactement nul sur la première) et diagonales (1/(2k) d'erreur pour k marches).
- Quel est le bouton de variance ?La profondeur — ou la taille minimale de feuille, ou le nombre de feuilles. À fond, erreur train 0 et mémorisation du tirage.
- Sur quel critère élaguer ?Le taux d'erreur ou le RSS sur des données non vues : l'impureté décroît par construction, donc elle ne peut pas dire quand s'arrêter.
Ponts et cartes
ml::arbres (coupure = feature + seuil, glouton, axe par axe) · ml::gini (2p(1−p), deux tirages, gain pondéré) · ml::profondeur (bouton de variance, erreur train 0, élagage au taux d'erreur) · ml::cart (tri-balayage O(n log n), régression par la variance, pas d'extrapolation).
Une carte qui résiste après cette chaîne est une carte à refondre, pas une section à relire.