Arbres de décision et ensembles

Objectifs du chapitre

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

décrire un arbre de décision comme une partition récursive de l'espace des caractéristiques en rectangles, et lire sa prédiction sur un diagramme comme dans le plan;
calculer l'impureté de Gini, l'entropie en bits et le gain d'une coupure, démontrer que le Gini est maximal pour la loi uniforme et qu'une coupure ne l'augmente jamais;
faire pousser un arbre par l'algorithme glouton, sur le jeu B jusqu'à la pureté, puis le régulariser par une règle d'arrêt ou par l'élagage coût–complexité;
construire un arbre de régression par réduction de la somme des carrés, sur les loyers du jeu A, et le comparer à la droite des moindres carrés;
expliquer l'instabilité d'un arbre et la façon dont le bagging, les forêts aléatoires et l'erreur hors sac la transforment en avantage;
dérouler une itération d'AdaBoost sur des souches, décrire le gradient boosting, et interpréter avec prudence une importance de caractéristique.

Des questions en cascade

Un guichetier qui trie le courrier sans ordinateur ne calcule pas de combinaison linéaire. Il se pose une question, puis une autre, selon la réponse à la première: «Le message contient-il beaucoup de mots suspects? Non: je le garde. Oui: est-il écrit en grande partie en majuscules?» Chaque question ne porte que sur une caractéristique, chaque réponse oriente vers la question suivante, et la dernière réponse donne le verdict. Cette façon de décider s'écrit naturellement comme un arbre, et c'est l'un des modèles les plus anciens et les plus utilisés de l'apprentissage automatique.

Les modèles des chapitres 2 à 4 cherchaient une seule formule valable partout dans le plan: une droite, un hyperplan, une sigmoïde d'une combinaison linéaire. Les plus proches voisins du chapitre 7 renonçaient à toute formule et consultaient les exemples. Un arbre est entre les deux: il découpe l'espace en régions et attribue à chacune une prédiction constante, mais ces régions sont apprises, peu nombreuses, et se décrivent par des règles que l'on peut lire à voix haute.

Trois choix sont cachés dans cette définition. Les tests ne portent que sur une caractéristique à la fois, ce qui produit des frontières parallèles aux axes: une frontière oblique, comme celle de la régression logistique sur le jeu B, ne s'obtient qu'en escalier. Les tests sont binaires: une question à trois réponses s'écrit avec deux questions à deux réponses. Enfin, la prédiction est constante par région: un arbre ne sait pas qu'à l'intérieur d'une feuille le loyer augmente avec la surface. Ces trois choix font la force de l'arbre — il se lit, il ignore les unités, il traite les interactions entre caractéristiques sans qu'on les lui indique — et ils font aussi ses limites, que ce chapitre va mesurer.

Une propriété mérite d'être soulignée dès maintenant. Le test $x_{j} \leq s$ ne dépend que de l'ordre des valeurs de $x_{j}$ , pas de leur échelle: mesurer $x_{1}$ en pour mille ou en pour cent ne change ni les régions ni les prédictions, seulement l'écriture des seuils. C'est l'opposé exact des plus proches voisins, que la mise à l'échelle bouleversait (chapitre 7). Un arbre n'a pas besoin de standardisation.

Le problème est de choisir les tests. Le nombre d'arbres possibles croît de façon combinatoire avec la profondeur, et trouver l'arbre de taille donnée qui minimise l'erreur d'entraînement est un problème NP-difficile (Hyafil et Rivest l'ont montré en 1976 pour une version de ce problème). On procède donc de façon gloutonne: on choisit le meilleur test à la racine, sans regarder plus loin, puis on recommence dans chacune des deux parties. Pour cela, il faut savoir mesurer ce qu'est un «bon» test.

Mesurer le désordre d'un nœud

Un bon test sépare les classes: après la coupure, chaque côté devrait contenir surtout des exemples d'une même classe. On mesure donc le désordre d'un ensemble d'exemples par un nombre, nul quand toutes les étiquettes sont identiques et maximal quand elles sont mélangées à parts égales.

Les deux mesures ont une lecture probabiliste. Tirez un exemple au hasard dans le nœud et prédisez sa classe en tirant une étiquette au hasard selon les proportions du nœud: la probabilité de vous tromper est $\sum_{k} p_{k} (1 - p_{k})$ , l'impureté de Gini. L'entropie, elle, est le nombre moyen de bits nécessaires pour coder l'étiquette d'un exemple du nœud avec le meilleur code possible; elle vient de la théorie de l'information de Shannon, et le chapitre 4 y a déjà fait allusion à propos de l'entropie croisée. Le logarithme est en base 2 pour que l'unité soit le bit: un nœud moitié pourriels, moitié légitimes a une entropie d'exactement 1 bit. C'est le seul endroit du cours où le logarithme n'est pas népérien.

La figure 8.1 montre que le Gini et l'entropie ont presque la même forme: l'entropie divisée par deux est très proche du Gini, et en pratique les deux mesures choisissent le plus souvent les mêmes coupures. Le taux d'erreur, lui, a un défaut que nous verrons: étant linéaire de part et d'autre de $1/2$ , il ne récompense pas une coupure qui rend les deux côtés plus purs sans changer leur classe majoritaire. Le Gini est la mesure par défaut de la méthode CART, l'entropie celle des algorithmes ID3 et C4.5 de Quinlan.

Démonstration. Chaque terme $p_{k} (1 - p_{k})$ est positif puisque $0 \leq p_{k} \leq 1$ , donc $G \geq 0$ , avec égalité si et seulement si chaque vaut 0 ou 1, c'est-à-dire si une seule classe a la proportion 1. Pour la borne supérieure, il suffit de minorer . Écrivons , où les écarts sont de somme nulle puisque . Alors

k = 1 \sum K p_{k}^{2} = k = 1 \sum K (\frac{1}{K ^{2}} + \frac{2 e _{k}}{K} + e_{k}^{2}) = \frac{1}{K} + \frac{2}{K} k = 1 \sum K e_{k} + k = 1 \sum K e_{k}^{2} = \frac{1}{K} + k = 1 \sum K e_{k}^{2} \geq \frac{1}{K},

avec égalité si et seulement si tous les $e_{k}$ sont nuls. Donc $G = 1 - \sum_{k} p_{k}^{2} \leq 1 - \frac{1}{K}$ , avec égalité si et seulement si la loi est uniforme.

Pour deux classes, la borne vaut $1/2$ , ce que la figure 8.1 montre. L'entropie a la même propriété, avec le maximum $lo g_{2} K$ bits; la démonstration demande l'inégalité de Jensen et nous l'admettrons.

On juge une coupure non par l'impureté de ses deux côtés séparément, mais par leur moyenne pondérée par les effectifs: un côté minuscule et pur ne doit pas compter autant qu'un côté énorme et mélangé.

Il reste à préciser quels seuils essayer. Entre deux valeurs consécutives observées d'une caractéristique, tous les seuils donnent la même partition des exemples; il suffit donc d'en essayer un par intervalle, et la convention est de prendre le milieu des deux valeurs. Une caractéristique qui prend $m$ valeurs distinctes dans le nœud offre $m - 1$ seuils candidats.

Exemple 8.1 · La coupure racine du jeu B

Reprenons le jeu B, ses seize courriels E1 à E16 et ses deux caractéristiques: $x_{1}$ , le taux de mots suspects (‰), et $x_{2}$ , la part de majuscules (%). Ce sont des données fictives, construites pour le cours, celles du chapitre 1:

	E1	E2	E3	E4	E5	E6	E7	E8
$x_{1}$ (‰)

Question 8.1

Un nœud contient quatre courriels, dont un seul pourriel. Calculez son entropie, en bits.

Une coupure ne dégrade jamais l'impureté

Le gain d'une coupure de Gini est-il toujours positif? Sur le tableau de l'exemple 8.1, oui: les seize gains sont positifs, même ceux des coupures qui n'isolent qu'un seul courriel. Ce n'est pas une coïncidence.

Démonstration. Notons $w_{G} = n_{G} / n$ et $w_{D} = n_{D} / n$ , de somme 1, et , les proportions de la classe à gauche et à droite. Le nombre d'exemples de classe dans le parent est la somme de ceux des deux côtés, , d'où

p_{k} = w_{G} p_{G k} + w_{D} p_{D k} .

La fonction $t \mapsto t^{2}$ est convexe (Analyse I): pour $w_{G} + w_{D} = 1$ et $w_{G}, w_{D} \geq 0$ , , car la différence vaut . Appliquée à chaque classe,

p_{k}^{2} \leq w_{G} p_{G k}^{2} + w_{D} p_{D k}^{2},

avec égalité si et seulement si $p_{G k} = p_{D k}$ (les deux poids sont strictement positifs). En sommant sur $k$ et en utilisant $w_{G} + w_{D} = 1$ ,

G_{coupure} = w_{G} (1 - k \sum p_{G k}^{2}) + w_{D} (1 - k \sum p_{D k}^{2}) = 1 - k \sum (w_{G} p_{G k}^{2} + w_{D} p_{D k}^{2}) \leq 1 - k \sum p_{k}^{2} = G_{parent} .

L'égalité exige l'égalité pour chaque $k$ , donc des proportions identiques des deux côtés, qui sont alors aussi celles du parent. $□$

La démonstration n'a utilisé qu'une chose: $G$ est une fonction concave des proportions. Le même argument, avec l'inégalité de Jensen, vaut pour l'entropie. Il ne vaut pas strictement pour le taux d'erreur, qui n'est que concave au sens large: une coupure peut améliorer la pureté des deux côtés sans changer le taux d'erreur. C'est le cas, sur le jeu B, de $x_{1} \leq 4, 5$ à la racine: la gauche (7 légitimes, 2 pourriels) et la droite (1 légitime, 6 pourriels) commettent 3 erreurs, comme la coupure $x_{1} \leq 2, 5$ , alors que leurs Gini diffèrent. Avec le taux d'erreur comme critère, l'algorithme glouton serait souvent aveugle; c'est pourquoi on le réserve à l'élagage.

Le théorème a une conséquence moins rassurante: puisque couper ne coûte jamais rien en impureté d'entraînement, rien n'arrête un arbre qui pousse tant qu'un nœud contient deux classes et deux points distincts. Un arbre poussé jusqu'au bout a une erreur d'entraînement nulle sur des points distincts — exactement comme le plus proche voisin, et pour la même mauvaise raison.

Question 8.2

Complétez gini(etiquettes), l'impureté de Gini d'une liste d'étiquettes 0 et 1 (0 pour une liste vide), et meilleure_coupure(donnees), qui renvoie le triplet (j, seuil, impurete) de la coupure d'impureté pondérée minimale: j vaut 0 pour $x_{1}$ et 1 pour $x_{2}$ , et le seuil est un milieu entre deux valeurs consécutives. À impureté égale, la première coupure rencontrée l'emporte ( $x_{1}$ avant $x_{2}$ , petit seuil avant grand): comparez avec une inégalité stricte. La fonction seuils est fournie. Le programme cherche la coupure racine du jeu B, puis la meilleure coupure du nœud de droite.

coupure.py

courriels = [
  ((1, 0), 0), ((2, 1), 0), ((0, 2), 0), ((3, 0), 0),
  ((1, 3), 0), ((4, 2), 0), ((2, 5), 0), ((6, 3), 0),
  ((7, 5), 1), ((5, 6), 1), ((8, 4), 1), ((4, 5), 1),
  ((9, 7), 1), ((6, 7), 1), ((3, 2), 1), ((7, 3), 1),
]

def seuils(donnees, j):
  """Milieux entre valeurs consecutives distinctes de la caracteristique j."""
  valeurs = sorted(set(x[j] for x, _ in donnees))
  return [(a + b) / 2 for a, b in zip(valeurs, valeurs[1:])]

def gini(etiquettes):
  # A completer: 1 - p0^2 - p1^2, avec p1 la proportion de 1.
  return 0.0

def meilleure_coupure(donnees):
  # A completer: pour j dans (0, 1) et chaque seuil s de seuils(donnees, j),
  # partager les exemples (x[j] <= s a gauche), calculer
  # n_g/n * gini(gauche) + n_d/n * gini(droite), garder le minimum strict.
  return (0, 0.0, 1.0)

j, s, imp = meilleure_coupure(courriels)
print("racine: x%d <= %.1f, impurete ponderee %.4f" % (j + 1, s, imp))
droite = [(x, y) for x, y in courriels if x[j] > s]
j2, s2, imp2 = meilleure_coupure(droite)
print("droite: x%d <= %.1f, impurete ponderee %.4f" % (j2 + 1, s2, imp2))

Faire pousser l'arbre

L'algorithme qui construit l'arbre est récursif, et il tient en quelques lignes. On le doit, sous cette forme, à Breiman, Friedman, Olshen et Stone, dont le livre Classification and Regression Trees (1984) a donné son nom à la méthode CART.

Si le nœud est pur, ou si une règle d'arrêt s'applique (profondeur maximale atteinte, trop peu d'exemples), en faire une feuille.
Sinon, essayer toutes les coupures $x_{j} \leq s$ candidates et retenir celle d'impureté pondérée minimale.
Partager les exemples selon ce test, et appliquer la procédure à chacune des deux parties.

def pousser(donnees, profondeur=0, profondeur_max=99):
    etiquettes = [y for _, y in donnees]
    if gini(etiquettes) == 0 or profondeur == profondeur_max:
        return ("feuille", 1 if 2 * sum(etiquettes) > len(etiquettes) else 0)
    j, s, _ = meilleure_coupure(donnees)
    gauche

Le test gini(etiquettes) == 0 compare un réel à zéro, mais sans risque ici: le Gini d'un nœud pur est calculé exactement ( $1 - 1^{2} - 0^{2}$ ). La feuille prédit la classe majoritaire; à égalité, elle prédit 0, ce qui sur le jeu B revient à la règle «le premier exemple de la feuille», puisque les courriels légitimes viennent en premier.

Le diagramme de la figure 8.2 et la partition du plan sont deux dessins du même objet. L'explorateur 8.1 montre la partition: chaque feuille est un rectangle, teinté selon sa prédiction, et les traits sont les seuils. En faisant varier la profondeur maximale, vous voyez l'arbre se construire étage par étage, et vous voyez surtout deux nombres évoluer de façon très différente.

Explorateur 8.1 · La profondeur d'un arbre de décision

Augmentez la profondeur maximale et regardez l'arbre découper le plan en rectangles de plus en plus petits, jusqu'à isoler E15 dans une case à lui et loger E8 avec E6 dans une enclave légitime au milieu des pourriels. L'erreur d'entraînement descend de 8 à 0; l'erreur LOO de la validation croisée par exclusion, où chaque courriel est prédit par un arbre grandi sans lui, reste bloquée à 7 sur 16 dès la profondeur 1. Les coupures ajoutées après la première n'apprennent que les exceptions.

Profondeur maximale5

Feuilles

6 (profondeur atteinte 5)

Erreur d'entraînement

0 sur 16

Erreur LOO (par exclusion)

7 sur 16

Prédiction en (2,5; 2)

légitime

Voici ces deux nombres pour chaque profondeur maximale. L'erreur LOO est celle de la validation croisée par exclusion (leave-one-out, LOO) du chapitre 7 (définition 7.6): chaque courriel est prédit par un arbre poussé, à la même profondeur maximale, sur les quinze autres.

Profondeur maximale	0	1	2	3	4	5
Feuilles	1	2	3	4	5	6
Erreur d'entraînement	8 sur 16	3 sur 16	2 sur 16	1 sur 16	1 sur 16	0 sur 16
Erreur LOO	16 sur 16	7 sur 16	7 sur 16	7 sur 16	7 sur 16	7 sur 16

La première colonne est une curiosité classique: à la profondeur 0, l'arbre est une constante, et retirer un courriel donne la majorité à l'autre classe — chaque courriel est donc prédit faux. Ensuite, l'erreur d'entraînement descend régulièrement jusqu'à zéro, tandis que l'erreur LOO reste bloquée à 7 sur 16, soit $43, 75$ %. Les quatre coupures ajoutées après la première font disparaître trois erreurs d'entraînement et ne corrigent aucune erreur de validation: elles n'apprennent que les exceptions de l'échantillon. C'est le surapprentissage du chapitre 6, sous sa forme la plus nette.

Le chiffre de 7 sur 16 est mauvais, et il faut le dire: sur les mêmes données, la règle 1-PPV commettait 5 erreurs LOO, et dès $k = 7$ les plus proches voisins descendaient à 2 (chapitre 7). Un arbre unique, avec ses frontières en escalier et ses décisions abruptes, est un classifieur médiocre sur un nuage dont la frontière naturelle est oblique. Les sections sur les ensembles montreront comment on en fait l'un des meilleurs.

Question 8.3

L'arbre complet du jeu B (figure 8.2) est appliqué à trois nouveaux courriels: $(5, 1)$ , $(3; 1, 5)$ et $(2, 8; 0, 5)$ . Quelles affirmations sont vraies? (Plusieurs réponses possibles.)

Plusieurs réponses possibles

Arrêter ou élaguer

Il faut donc empêcher l'arbre de tout apprendre. Deux familles de remèdes existent: arrêter la croissance avant la fin, ou laisser pousser puis couper.

Les règles d'arrêt (pre-pruning) sont des hyperparamètres: une profondeur maximale, un nombre minimal d'exemples par feuille (une coupure qui laisserait moins de, disons, cinq exemples d'un côté est interdite), un gain minimal (on ne coupe pas si $Δ G$ est trop petit). Elles sont simples et rapides, et toutes se choisissent par validation croisée (chapitre 5). Elles ont un défaut connu: elles sont myopes. Une coupure de faible gain peut ouvrir la voie à une coupure suivante excellente, et une règle de gain minimal l'interdit. L'exemple d'école est le «ou exclusif»: sur des données en damier, aucune coupure unique ne réduit l'impureté, alors que deux coupures successives séparent tout.

L'élagage (pruning) évite cette myopie: on fait pousser l'arbre jusqu'au bout, puis on remonte en supprimant les sous-arbres qui ne rapportent pas assez. La version de CART pénalise la taille de l'arbre.

Le rapport $g (t)$ est le prix d'une feuille: il dit combien d'erreur d'entraînement chaque feuille du sous-arbre $T_{t}$ fait gagner. Tant que $α < g (t)$ , garder le sous-arbre est rentable; au-delà, on le remplace par une feuille. Le paramètre $α$ joue le rôle du $λ$ de la régression ridge (chapitre 6): à $α = 0$ , on garde l'arbre complet; quand grandit, l'arbre se réduit jusqu'à la racine seule. Sur l'arbre du jeu B, le calcul est fait au problème guidé 8.1: la suite des arbres élagués a 6, 4, 2 puis 1 feuille, et les seuils de valent , et . On choisit ensuite par validation croisée — et sur le jeu B, puisque toutes les profondeurs de 1 à 5 ont la même erreur LOO, on prend le plus simple des arbres qui l'atteignent: la souche de profondeur 1.

Arbres de décision dans scikit-learn

Pour information, l'équivalent d'une ligne, que vous n'avez pas à exécuter ici. Le paramètre ccp_alpha est le $α$ de (8.3), et cost_complexity_pruning_path renvoie la suite de ses seuils.

from sklearn.tree import DecisionTreeClassifier, export_text
arbre = DecisionTreeClassifier(criterion="gini", max_depth=None, ccp_alpha=0.0).fit(X, y)
print(export_text(arbre, feature_names=["x1", "x2"

Les arbres de régression

Rien dans la croissance d'un arbre ne suppose que l'étiquette soit une classe. Pour une étiquette réelle, la feuille prédit la moyenne de ses exemples — la constante qui minimise la perte carrée (théorème 1.2) —, et l'impureté naturelle d'un nœud est la somme des carrés des écarts à cette moyenne.

Le théorème 8.2 a son analogue: une coupure ne peut jamais augmenter la somme des carrés, puisque la moyenne de chaque côté fait au moins aussi bien, de son côté, que la moyenne du parent (exercice 8.3).

Exemple 8.3 · Un arbre de régression pour les loyers

Reprenons le jeu A, huit appartements de Lausanne — données fictives, construites pour le cours:

Logement	1	2	3	4	5	6	7	8
Surface $x$ (m²)	30	45	50	62	70	85	95	110
Loyer $y$ (CHF)	1 200	1 550	1 380	1 840	1 750	2 350	2 250	2 900

À la racine, la moyenne est $\overset{y}{ˉ} = 1902, 5$ CHF et la somme des carrés vaut CHF² (huit fois la variance CHF² du chapitre 1). Les sept seuils candidats sont les milieux des surfaces consécutives:

L'exemple dit l'essentiel des arbres de régression. Ils n'extrapolent pas: au-delà de 110 m², l'arbre prédira toujours CHF 2 900, quelle que soit la surface, puisque aucune feuille ne connaît d'appartement plus grand. Ils gaspillent leurs données sur une relation lisse, qu'un modèle linéaire capture avec deux paramètres. Ils sont en revanche à l'aise quand la relation est faite de seuils et d'interactions — «au-dessus de tel revenu et en dessous de tel âge» — qu'un modèle linéaire ne voit pas sans qu'on construise les bonnes caractéristiques à la main.

Question 8.4

Complétez sce(valeurs), la somme des carrés des écarts à la moyenne (0 pour une liste vide), et coupure_regression(donnees), qui renvoie le couple (seuil, total) de la coupure $x \leq s$ minimisant $SCE_{G} + SCE_{D}$ sur une liste de couples (x, y) à une caractéristique, les seuils étant les milieux des valeurs consécutives distinctes de $x$ . À égalité, le plus petit seuil l'emporte. Le programme cherche la coupure racine des loyers.

arbre_loyers.py

Un modèle instable

Les arbres ont une réputation qu'il faut comprendre avant de les utiliser: ils sont instables. Une petite modification des données d'entraînement peut changer la coupure de la racine, et comme toute la suite de l'arbre dépend de cette coupure, l'arbre entier peut changer.

L'expérience est simple sur le jeu B. Retirons un seul courriel et refaisons le calcul de l'exemple 8.1 sur les quinze autres. Pour onze des seize courriels retirés, la racine reste $x_{1} \leq 2, 5$ . Mais pour cinq d'entre eux, elle change:

Courriel retiré	E7	E8	E12	E15	E16
Nouvelle racine	$x_{2} \leq 3, 5$	$x_{1} \leq 4, 5$	$x_{1} \leq 4, 5$

Retirer E7, un courriel légitime ordinaire en haut à gauche, fait passer la racine de $x_{1}$ à $x_{2}$ : les deux arbres n'ont plus une seule coupure en commun au premier étage, et leurs partitions du plan diffèrent largement. La raison est visible dans le tableau de l'exemple 8.1: la meilleure coupure ( $0, 2727$ ) ne devance la deuxième ( $0, 3016$ ) que de $0, 029$ , et un seul exemple suffit à inverser l'ordre. Cette sensibilité est une forme extrême de variance, au sens du chapitre 6: l'arbre appris dépend beaucoup de l'échantillon qui l'a produit. C'est aussi ce qui explique l'erreur LOO de 7 sur 16 de la profondeur 1: les cinq courriels dont l'absence change la racine sont tous mal classés par l'arbre poussé sans eux, et les deux autres erreurs, E4 et E6, sont des courriels légitimes du mauvais côté de .

L'instabilité a une conséquence pratique qui va au-delà de la précision. On aime les arbres parce qu'ils se lisent: «un courriel est suspect s'il dépasse 2,5 ‰ de mots suspects». Mais si la règle lue sur l'arbre change quand on retire un exemple sur seize, il faut se garder d'en tirer une interprétation causale ou même descriptive solide. Un arbre lisible n'est pas pour autant un arbre fiable.

Question 8.5

On retire un seul courriel du jeu B et l'on recalcule la coupure racine sur les quinze autres. Lesquels de ces retraits changent la racine $x_{1} \leq 2, 5$ ? (Plusieurs réponses possibles.)

Plusieurs réponses possibles

Le bagging: moyenner des arbres instables

L'instabilité d'un arbre est une variance élevée. Or il existe un remède universel contre la variance: moyenner. Si l'on disposait de $B$ jeux de données indépendants, on pourrait faire pousser un arbre sur chacun et moyenner leurs prédictions; l'erreur due à la variance serait divisée par $B$ . On ne dispose que d'un jeu de données. L'idée de Leo Breiman (1996) est de fabriquer les $B$ jeux à partir du seul dont on dispose, par rééchantillonnage.

Pourquoi moyenner des arbres tirés du même jeu de données aide-t-il, alors qu'ils ne sont pas indépendants? Le résultat suivant dit exactement ce qu'on gagne, et ce qu'on ne peut pas gagner.

Démonstration. La variance d'une somme est la somme de toutes les covariances (Probabilités et statistique, chapitre 7): $Var [\sum_{b} T_{b}] = \sum_{b} Var [T_{b}] + \sum_{b \neq = b^{'}} Cov [T_{b}, T_{b^{'}}]$ . Il y a variances égales à et covariances égales à , d'où

Var [\frac{1}{B} b \sum T_{b}] = \frac{1}{B ^{2}} (B σ^{2} + B (B - 1) ρ σ^{2}) = \frac{σ ^{2}}{B} + \frac{B - 1}{B} ρ σ^{2} = ρ σ^{2} + \frac{1 - ρ}{B} σ^{2} . □

Lisez (8.4) avec $T_{b}$ la prédiction en un point $x$ de l'arbre poussé sur le $b$ -ième échantillon bootstrap. Le second terme disparaît quand $B$ grandit: ajouter des arbres ne fait jamais de mal, et à partir d'un certain nombre ne fait plus de bien. Le premier terme, $ρ σ^{2}$ , reste: la corrélation entre les arbres fixe un plancher que le bagging ne franchit pas. Avec $ρ = 0, 3$ et , la variance vaut pour , pour , et jamais moins de . Le biais, lui, n'est pas touché: la moyenne de arbres a le même biais qu'un arbre. C'est pourquoi on fait pousser les arbres du bagging : un arbre profond a un biais faible et une variance forte, et c'est la variance que la moyenne réduit.

L'erreur hors sac

Le bagging offre en prime une estimation de son erreur de test qui ne coûte aucune donnée.

Un exemple donné est absent d'un échantillon bootstrap avec probabilité $(1 - 1/ n)^{n}$ : il faut qu'aucun des $n$ tirages ne le choisisse. Pour $n = 16$ , cette probabilité vaut $(15/16)^{16} = 0, 3561$ ; pour $n = 100$ , ; et quand , elle tend vers (exercice 8.4). Chaque arbre laisse donc de côté environ un tiers des exemples, qui n'ont joué aucun rôle dans sa construction.

Chaque prédiction hors sac est faite par des arbres qui n'ont pas vu l'exemple: c'est une forme de validation croisée, obtenue gratuitement au cours de l'entraînement. Elle est un peu pessimiste, parce qu'elle n'agrège qu'environ un tiers des arbres, mais avec quelques centaines d'arbres la différence est faible.

Question 8.6

On tire un échantillon bootstrap des seize courriels du jeu B. Quelle est la probabilité que E15 n'y figure pas, c'est-à-dire qu'il soit hors sac?

Les forêts aléatoires

La formule (8.4) indique la voie suivante: pour aller sous le plancher $ρ σ^{2}$ , il faut décorréler les arbres. Ceux du bagging se ressemblent beaucoup, parce qu'ils voient presque les mêmes données et que la même caractéristique dominante gagne presque toujours la coupure de la racine. Breiman (2001) a ajouté un second tirage au hasard.

Restreindre le choix à chaque nœud rend chaque arbre un peu moins bon — son biais augmente légèrement, sa variance aussi — mais il force des arbres différents à exploiter des caractéristiques différentes, et la corrélation $ρ$ baisse. Le gain sur le plancher l'emporte souvent sur la perte individuelle. Le paramètre $m$ règle ce compromis, et c'est presque le seul qu'il faille régler: une forêt aléatoire avec ses réglages par défaut est l'une des méthodes les plus robustes de l'apprentissage sur des données tabulaires.

Sur le jeu B, avec seize courriels et deux caractéristiques, l'expérience tourne court. Avec 501 arbres, des échantillons bootstrap tirés par random.choices après random.seed(0) et des arbres poussés jusqu'à la pureté, l'erreur hors sac vaut 7 sur 16 pour le bagging et 6 sur 16 pour la forêt avec $m = 1$ , à comparer aux 7 sur 16 de l'arbre seul en validation par exclusion. Sur seize points, une différence d'un courriel est dans le bruit. Pour voir l'effet, il faut plus de données.

Construisons donc un problème dont on connaît la loi, comme au chapitre 6. Chaque exemple a quatre caractéristiques tirées uniformément dans $[0, 10]$ ; seules les deux premières comptent: la probabilité d'un pourriel vaut $σ (1, 5 (x_{1} + x_{2} - 10))$ , et $x_{3}$ , sont du pur bruit. On tire 200 exemples d'entraînement et 1 000 de test avec , puis on fait pousser les ensembles avec . La meilleure règle possible, «pourriel si », se trompe sur 8,1 % du test: c'est le plancher que fixe le bruit des étiquettes.

Modèle	Erreur de test	Erreur hors sac
un arbre poussé jusqu'au bout	14,8 %	—
bagging, $B = 10$	12,6 %	15,2 %
bagging, $B = 50$	11,3 %	11,5 %
bagging, $B = 200$	10,3 %	12,5 %
forêt, $m = 2$ , $B = 200$

Trois leçons, toutes chiffrées. Moyenner des arbres fait passer l'erreur de test de 14,8 % à 10,3 %, soit plus de la moitié du chemin vers le plancher de 8,1 %. L'erreur hors sac suit l'erreur de test à moins de trois points près, sans qu'un seul exemple de test ait été consulté. Et la forêt ne fait pas mieux que le bagging ici: avec deux caractéristiques utiles sur quatre, tirer $m = 1$ ou $m = 2$ caractéristiques par nœud force souvent l'arbre à couper sur du bruit. Les forêts aléatoires brillent quand beaucoup de caractéristiques sont informatives et corrélées entre elles; sur un problème où deux caractéristiques portent tout, la décorrélation coûte autant qu'elle rapporte. Un écart d'un point sur 1 000 exemples de test est de plus trop petit pour départager sûrement deux modèles: à cette taille, l'incertitude sur chaque taux d'erreur est elle-même de l'ordre d'un point.

Bagging et forêts dans scikit-learn

Pour information:

from sklearn.ensemble import RandomForestClassifier
foret = RandomForestClassifier(n_estimators=500, max_features="sqrt",
                               oob_score=True, random_state=0).fit(X, y)
print(foret.oob_score_)   # exactitude hors sac, le complément de l'erreur hors sac

Avec max_features=None, toutes les caractéristiques sont candidates à chaque nœud: c'est le bagging de la définition 8.6.

Le boosting: corriger ses erreurs

Le bagging fait pousser des arbres profonds en parallèle et réduit leur variance. Le boosting fait l'inverse: il fait pousser des modèles très simples, au biais élevé, en série, chacun concentré sur les erreurs des précédents. La question à l'origine du boosting était théorique — peut-on transformer un classifieur à peine meilleur que le hasard en un classifieur aussi précis qu'on veut? — et Freund et Schapire y ont répondu en 1997 par un algorithme, AdaBoost.

Le modèle simple est une souche (decision stump): un arbre de profondeur 1, une seule coupure et deux feuilles. AdaBoost attribue un poids à chaque exemple d'entraînement; chaque souche est choisie pour minimiser le taux d'erreur pondéré, puis les poids des exemples mal classés augmentent, et ceux des exemples bien classés diminuent.

La version la plus répandue est écrite avec des étiquettes $\pm 1$ , et le vote final y est le signe de $\sum_{t} α_{t} h_{t} (x)$ ; la définition ci-dessus en est la traduction exacte pour des classes 0 et 1, que ce cours garde jusqu'au chapitre 9. Le poids de vote $α_{t}$ est positif dès que , d'autant plus grand que la souche est précise, et nul pour une souche qui ne fait pas mieux que le hasard. La souche choisie à l'étape minimise l'erreur pondérée, pas le Gini: les souches d'AdaBoost ne sont pas les racines de CART.

Que donne la suite? Après trois souches, le vote pondéré ne se trompe plus que sur un courriel d'entraînement, et la validation par exclusion tombe à 3 sur 16, contre 7 sur 16 pour un arbre unique. Mais si l'on continue, la validation remonte à 5 ou 6 sur 16 dès la quatrième souche, tandis que l'erreur d'entraînement hésite entre 1 et 0 de 9 à 12 souches, puis reste nulle à partir de 13: le nombre d'itérations $T$ est un hyperparamètre, à choisir par validation croisée comme une profondeur. Sur seize courriels, ces chiffres bougent d'un ou deux courriels d'une valeur de $T$ à la suivante; ils illustrent le mécanisme plus qu'ils ne départagent des méthodes.

Le gradient boosting

AdaBoost a été réinterprété par Friedman (2001) comme une descente de gradient, menée non pas dans l'espace des paramètres mais dans l'espace des fonctions. Le gradient boosting construit le modèle par ajouts successifs, $F_{t} = F_{t - 1} + ν h_{t}$ , où $h_{t}$ est un petit arbre ajusté au en chaque exemple, et un (, ou ), l'analogue du du chapitre 3. Pour la perte carrée, le gradient négatif de par rapport à est simplement le : chaque arbre apprend ce que les précédents n'ont pas expliqué.

Sur les loyers, avec des souches et $ν = 0, 5$ , on part de la constante $F_{0} = \overset{y}{ˉ} = 1902, 5$ CHF. Les résidus sont les écarts à la moyenne, et la souche qui les ajuste le mieux est la coupure de l'exemple 8.3, $x \leq 77, 5$ , de feuilles et CHF. Le modèle devient CHF pour les cinq petits appartements et CHF pour les trois grands — la moitié seulement du pas complet —, et son erreur quadratique moyenne d'entraînement vaut CHF². La deuxième souche, ajustée aux nouveaux résidus, coupe en . Après 10 souches, l'erreur d'entraînement vaut CHF², après 50 souches CHF², et elle continue de descendre. La validation par exclusion atteint son minimum, CHF², à 10 souches, puis remonte ( CHF² à 50): le boosting surapprend s'il tourne trop longtemps, et le petit ne fait que ralentir ce moment. Il reste, sur ces données presque linéaires, loin derrière les CHF² de la droite.

Le boosting d'arbres, sous ses implémentations modernes (XGBoost, LightGBM, HistGradientBoostingClassifier de scikit-learn), est l'une des méthodes de référence sur les données tabulaires, où il rivalise souvent avec les réseaux de neurones des chapitres 10 et 11. Son réglage demande plus de soin que celui d'une forêt: taux d'apprentissage, nombre et profondeur des arbres interagissent, et l'arrêt précoce sur un ensemble de validation (chapitre 6) est la règle.

Question 8.7

Complétez etape_adaboost(poids, correct): poids est une liste de poids positifs (pas forcément de somme 1), correct une liste de booléens qui dit si la souche classe bien chaque exemple. La fonction renvoie le couple (alpha, nouveaux): l'erreur pondérée $ε$ est la part du poids total portée par les exemples mal classés, $α = \frac{1}{2} ln \frac{1 - ε}{ε}$ , et les nouveaux poids sont les anciens multipliés par $e^{α}$ (mal classés) ou $e^{- α}$ (bien classés), puis divisés par leur somme. Le programme déroule les deux premières itérations de l'exemple 8.4.

adaboost.py

L'importance des caractéristiques

Une forêt de cinq cents arbres ne se lit plus comme un arbre. On veut pourtant savoir quelles caractéristiques elle utilise, et les bibliothèques fournissent pour cela une importance par caractéristique. Il y en a deux sortes, et elles ne mesurent pas la même chose.

Sur l'arbre complet du jeu B, la diminution d'impureté se calcule nœud par nœud. Les trois coupures sur $x_{1}$ (la racine, $x_{1} \leq 6, 5$ et $x_{1} \leq 3, 5$ ) apportent $\frac{5}{22} + \frac{9}{160} + \frac{1}{32} = \frac{277}{880}$ ; les deux coupures sur apportent . Leur somme vaut , toute l'impureté de la racine, puisque l'arbre finit pur. Normalisées, les importances sont pour et pour . Mais un tiers de l'importance de vient de la dernière coupure, , qui ne sert qu'à séparer E4 de E15:

Le problème synthétique de la section précédente rend ce défaut visible, puisqu'on y sait que $x_{3}$ et $x_{4}$ ne servent à rien. Sur l'arbre unique poussé jusqu'au bout, la diminution d'impureté attribue $0, 481$ à $x_{1}$ , $0, 434$ à , mais aussi à et à : plus de 8 % de l'importance totale va à du bruit, parce qu'un arbre profond finit toujours par trouver, dans un petit nœud, un seuil de bruit qui sépare deux exemples. L'importance par permutation, mesurée sur l'ensemble de test pour le bagging de 200 arbres, est plus honnête: permuter fait passer l'erreur de 10,3 % à 33,4 %, permuter à 33,2 %, alors que permuter ou ne l'augmente que de 0,5 et 1,2 point.

Une importance n'est pas un effet

Une importance dit combien le modèle s'appuie sur une caractéristique, pas ce que la caractéristique fait dans le monde. Trois pièges reviennent. La diminution d'impureté favorise les caractéristiques qui offrent beaucoup de seuils (une variable continue ou un identifiant battent une variable binaire, à information égale), et elle est calculée sur les données d'entraînement, donc gonflée par le surapprentissage. Deux caractéristiques fortement corrélées se partagent l'importance, si bien que chacune paraît secondaire alors qu'ensemble elles portent tout; l'importance par permutation souffre du même défaut, puisque le modèle retrouve dans l'une l'information qu'on a détruite dans l'autre. Enfin, comme pour un coefficient de régression (chapitre 2), une caractéristique importante peut n'être qu'un substitut d'une cause absente du tableau.

Synthèse

Un arbre de décision partitionne l'espace en rectangles par des tests $x_{j} \leq s$ et prédit une constante par feuille: la classe majoritaire en classification, la moyenne en régression. Il se lit, ignore les unités et traite les interactions, mais ses frontières sont en escalier et il n'extrapole pas.
On choisit les coupures de façon gloutonne en minimisant l'impureté pondérée (8.2): le Gini $1 - \sum_{k} p_{k}^{2}$ , maximal pour la loi uniforme, ou l' en bits. Une coupure n'augmente jamais le Gini pondéré (théorème 8.2), donc rien n'arrête la croissance. Sur le jeu B, la racine est , de gain .

Série d'exercices du chapitre 8Exercice 1 sur 5

Question 8.8

Le nœud de droite de la coupure racine du jeu B contient 3 courriels légitimes et 8 pourriels. Quelle est son impureté de Gini?

Exercices

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

Exercice 8.1 · Deux critères pour une coupure concurrente

À la racine du jeu B, on considère la coupure $x_{2} \leq 3, 5$ .

Quels courriels vont à gauche? Combien de pourriels de chaque côté?
Calculez son impureté de Gini pondérée et son gain, et comparez avec $x_{1} \leq 2, 5$ .

Exercice 8.2 · L'arbre, la logistique et le nouveau courriel

On compare sur le jeu B l'arbre complet (figure 8.2), la souche $x_{1} \leq 2, 5$ et la régression logistique du chapitre 4 ( $w_{0} = - 5, 1758$ , $w_{1} = 0, 67656$ , ).

Exercice 8.3 · Deuxième étage d'un arbre de régression

On reprend l'arbre de régression de l'exemple 8.3 sur les loyers (données fictives).

La partie gauche contient les logements de 30, 45, 50, 62 et 70 m². Calculez sa somme des carrés des écarts, puis $SCE_{G} + SCE_{D}$ pour ses quatre seuils candidats, et retrouvez le seuil 56.
Faites de même pour la partie droite (85, 95 et 110 m²).
Vérifiez l'erreur quadratique moyenne d'entraînement de $8789, 58$ CHF² de l'arbre de profondeur 2.
Montrez que, pour toute coupure d'un nœud, .

Exercice 8.4 · Combien d'exemples un échantillon bootstrap laisse-t-il de côté?

On tire un échantillon bootstrap de taille $n$ dans un jeu de $n$ exemples distincts.

Montrez que la probabilité qu'un exemple donné soit hors sac vaut $(1 - 1/ n)^{n}$ , et calculez-la pour $n = 16$ et $n = 100$ .

Exercice 8.5 · Le poids de vote d'AdaBoost (démonstration)

À l'itération $t$ d'AdaBoost, les poids $w_{i}$ sont de somme 1 et la souche $h_{t}$ a l'erreur pondérée $ε \in (0, 1/2)$ . Pour un poids de vote quelconque, on multiplie les poids des exemples mal classés par , ceux des bien classés par , et l'on note la somme des poids obtenus.

Références

Hastie, T., Tibshirani, R. et Friedman, J., The Elements of Statistical Learning, Springer, 2ᵉ éd., 2009, chap. 9 (arbres, CART, élagage coût–complexité), chap. 10 (boosting, AdaBoost et gradient boosting), chap. 15 (forêts aléatoires) et chap. 8 (bagging).
James, G., Witten, D., Hastie, T. et Tibshirani, R., An Introduction to Statistical Learning, Springer, 2ᵉ éd., 2021, chap. 8 (arbres de décision, bagging, forêts aléatoires, boosting).
Breiman, L., «Random Forests», Machine Learning, 45, 2001 (forêts aléatoires, erreur hors sac, importance par permutation).
Shalev-Shwartz, S. et Ben-David, S., Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, chap. 10 (boosting et AdaBoost) et chap. 18 (arbres de décision).
Azencott, C.-A., Introduction au Machine Learning, Dunod, 2ᵉ éd., 2022 (arbres et méthodes ensemblistes, en français).

	E9	E10	E11	E12	E13	E14	E15	E16
$x_{1}$ (‰)	7	5	8	4	9	6	3	7
$x_{2}$ (%)	5	6	4	5	7	7	2	3
$y$	1	1	1	1	1	1	1	1

Coupure	Gauche	Droite	$G_{coupure}$	Gain
$x_{1} \leq 0, 5$	0 sur 1	8 sur 15	$0, 4667$	$0, 0333$
$x_{1} \leq 1, 5$	0 sur 3	8 sur 13	$0, 3846$	$0, 1154$
$x_{1} \leq 2, 5$	0 sur 5	8 sur 11	$0, 2727$	$0, 2273$
$x_{1} \leq 3, 5$	1 sur 7	7 sur 9	$0, 3016$	$0, 1984$
$x_{1} \leq 4, 5$	2 sur 9	6 sur 7	$0, 3016$	$0, 1984$
$x_{1} \leq 5, 5$	3 sur 10	5 sur 6	$0, 3667$	$0, 1333$
$x_{1} \leq 6, 5$	4 sur 12	4 sur 4	$0, 3333$	$0, 1667$
$x_{1} \leq 7, 5$	6 sur 14	2 sur 2	$0, 4286$	$0, 0714$
$x_{1} \leq 8, 5$	7 sur 15	1 sur 1	$0, 4667$	$0, 0333$
$x_{2} \leq 0, 5$	0 sur 2	8 sur 14	$0, 4286$	$0, 0714$
$x_{2} \leq 1, 5$	0 sur 3	8 sur 13	$0, 3846$	$0, 1154$
$x_{2} \leq 2, 5$	1 sur 6	7 sur 10	$0, 3667$	$0, 1333$
$x_{2} \leq 3, 5$	2 sur 9	6 sur 7	$0, 3016$	$0, 1984$
$x_{2} \leq 4, 5$	3 sur 10	5 sur 6	$0, 3667$	$0, 1333$
$x_{2} \leq 5, 5$	5 sur 13	3 sur 3	$0, 3846$	$0, 1154$
$x_{2} \leq 6, 5$	6 sur 14	2 sur 2	$0, 4286$	$0, 0714$

Seuil (m²)	Moyenne gauche	Moyenne droite	$SCE_{G} + SCE_{D}$ (CHF²)
37,5	1 200,00	2 002,86	1 669 942,86
47,5	1 375,00	2 078,33	1 491 933,33
56	1 376,67	2 218,00	906 746,67
66	1 492,50	2 312,50	889 150,00
77,5	1 544,00	2 500,00	520 320,00
90	1 678,33	2 575,00	1 027 933,33
102,5	1 760,00	2 900,00	1 096 800,00

Seuil (m²)	Moyennes (CHF)	$SCE_{G} + SCE_{D}$ (CHF²)
37,5	1 200 et 1 630	127 400,00
47,5	1 375 et 1 656,67	180 116,67
56	1 376,67 et 1 795	65 316,67
66	1 492,50 et 1 750	222 275,00

Objectifs du chapitre

Des questions en cascade

Mesurer le désordre d'un nœud

Une coupure ne dégrade jamais l'impureté

Faire pousser l'arbre

Arrêter ou élaguer

Les arbres de régression

Un modèle instable

Le bagging: moyenner des arbres instables

L'erreur hors sac

Les forêts aléatoires

Le boosting: corriger ses erreurs

Le gradient boosting

L'importance des caractéristiques

Synthèse

Exercices

Références

Le maillon le plus faible

Le deuxième élagage

Le coût–complexité pour $α = 0, 1$

Choisir $α$

Objectifs du chapitre

Des questions en cascade

Mesurer le désordre d'un nœud

Une coupure ne dégrade jamais l'impureté

Faire pousser l'arbre

Arrêter ou élaguer

Les arbres de régression

Un modèle instable

Le bagging: moyenner des arbres instables

L'erreur hors sac

Les forêts aléatoires

Le boosting: corriger ses erreurs

Le gradient boosting

L'importance des caractéristiques

Synthèse

Exercices

Références

Le maillon le plus faible

Le deuxième élagage

Le coût–complexité pour α=0,1

Choisir α

Le coût–complexité pour $α = 0, 1$

Choisir $α$