Combinez des modèles pour mieux prédire

Au chapitre 4, vous avez construit des arbres de décision lisibles, mais instables : changez quelques patients du jeu d’apprentissage, et l’arbre peut changer du tout au tout. Que faire d’un modèle aussi capricieux ? En construire beaucoup, et les faire voter ! C’est l’idée des méthodes d’ensemble (aussi appelées méta-apprentissage), qui dominent aujourd’hui l’apprentissage sur données tabulaires.

Notre fil rouge reste le dépistage des maladies cardiaques (le jeu heart.csv des chapitres 3 et 4). Et nous regarderons, à la fin, ce qu’une forêt aléatoire nous a appris sur les absences aux rendez-vous médicaux.

Pourquoi plusieurs modèles valent mieux qu’un

Imaginez cinq médecins qui se trompent chacun dans 30 % des cas, indépendamment les uns des autres. Si l’on suit l’avis majoritaire, il faut qu’au moins trois d’entre eux se trompent en même temps pour que le groupe se trompe. La probabilité que la majorité ait raison vaut :

$$\sum_{k=3}^{5} \binom{5}{k} \, 0{,}7^k \, 0{,}3^{5-k} \approx 0{,}837$$

où $\binom{5}{k}$ est le nombre de façons de choisir les $k$ médecins qui ont raison. Le groupe atteint environ 84 % de bonnes réponses, contre 70 % pour chacun. Avec 25 médecins, on dépasserait 98 %.

Le calcul du texte, étendu de 1 à 25 médecins. Tant que leurs erreurs sont indépendantes, chaque paire de votants supplémentaire améliore le groupe ; des médecins qui se trompent ensemble restent à 70 %.

Tout repose sur un mot : indépendamment. Si les cinq médecins ont suivi la même formation et font les mêmes erreurs, le vote ne sert à rien. Pour qu’un ensemble soit utile, il faut des modèles à la fois bons et divers. Les deux grandes familles de méthodes d’ensemble fabriquent cette diversité de façons opposées.

	Bagging (et forêts aléatoires)	Boosting
Construction	en parallèle, modèles indépendants	en séquence, chaque modèle corrige les précédents
Modèles de base	forts et instables (arbres profonds)	faibles (arbres très peu profonds)
Ce qui est réduit	surtout la variance	surtout le biais
Combinaison	vote ou moyenne simple	vote ou somme pondérée

Le bagging et les forêts aléatoires

Le bagging

Le bagging (bootstrap aggregating) crée de la diversité en variant les données :

1. tirer $B$ échantillons bootstrap : chacun contient $m$ exemples tirés avec remise parmi les $m$ exemples d’apprentissage ;
2. entraîner un modèle sur chaque échantillon ;
3. faire voter les $B$ modèles (ou moyenner leurs prédictions en régression).

Chaque arbre voit un échantillon différent du même jeu : c'est ce qui crée la diversité. Les exemples hors sac, jamais vus par un arbre, servent à estimer son erreur gratuitement.

Avec un tirage avec remise, certains patients apparaissent plusieurs fois dans un échantillon, d’autres jamais. La probabilité qu’un exemple donné ne soit jamais tiré vaut $(1 - 1/m)^m$, qui tend vers $1/e \approx 0{,}368$. Chaque échantillon contient donc environ 63 % des exemples distincts. Les 37 % restants, dits hors sac (out-of-bag), n’ont pas servi à ce modèle : on peut les utiliser pour estimer son erreur, gratuitement, sans jeu de validation séparé.

Pourquoi cela réduit-il la variance ? Si l’on moyenne $B$ prédictions de variance $\sigma^2$ chacune, avec une corrélation $\rho$ entre deux prédictions, la variance de la moyenne vaut :

$$\rho \, \sigma^2 + \frac{1 - \rho}{B} \, \sigma^2$$

Le second terme disparaît quand $B$ grandit, mais pas le premier. Tant que les modèles sont corrélés ($\rho$ proche de 1), multiplier les arbres ne sert presque à rien. D’où l’idée suivante.

Ajouter des arbres ne fait descendre la variance que jusqu'au plancher ρσ². Pour aller plus bas, il faut décorréler les arbres (passer de ρ = 0,5 à 0,2), ce que fait la forêt aléatoire.

Les forêts aléatoires

Une forêt aléatoire (random forest) est un bagging d’arbres profonds, avec une source de hasard supplémentaire : à chaque nœud, l’arbre ne choisit sa question que parmi un sous-ensemble aléatoire de caractéristiques (typiquement $\sqrt{d}$ en classification, où $d$ est le nombre total de caractéristiques). Si une variable est très forte, elle ne peut plus dominer tous les arbres : ils deviennent décorrélés, et $\rho$ diminue.

Les forêts aléatoires sont robustes, marchent bien sans grand réglage, sont parallélisables et fournissent une estimation hors sac de l’erreur. Leur prix : on perd la lisibilité d’un arbre unique, et le modèle est plus lourd en mémoire.

import pandas as pd
from sklearn.ensemble import RandomForestClassifier

df = pd.read_csv("heart.csv")
X, y = df.drop(columns=["target"]), df["target"]

foret = RandomForestClassifier(
    n_estimators=500,      # nombre d'arbres
    max_features="sqrt",   # caractéristiques candidates à chaque nœud
    oob_score=True,        # estimation hors sac de l'exactitude
    random_state=0,
).fit(X, y)
print(f"exactitude hors sac : {foret.oob_score_:.3f}")

À retenir

Le bagging moyenne des modèles instables entraînés sur des échantillons bootstrap : il réduit la variance. La forêt aléatoire ajoute un tirage de caractéristiques à chaque nœud pour décorréler les arbres, ce qui rend la moyenne bien plus efficace.

Le boosting : apprendre de ses erreurs

AdaBoost

Le boosting adopte la logique inverse : des modèles faibles (à peine meilleurs que le hasard), entraînés les uns après les autres, chacun se concentrant sur ce que les précédents ont raté. Le plus souvent, ce sont des souches (stumps), des arbres réduits à une seule question.

L’algorithme AdaBoost, pour deux classes codées $-1$ et $+1$, fonctionne ainsi :

1. donner à chaque exemple le même poids $w_i = 1/m$ ;
2. à chaque tour $t$ : entraîner un modèle faible $h_t$ sur les données pondérées, et calculer son erreur pondérée $\varepsilon_t$ (la somme des poids des exemples mal classés) ;
3. calculer le poids du modèle : $\alpha_t = \frac{1}{2} \ln \frac{1 - \varepsilon_t}{\varepsilon_t}$ ;
4. mettre à jour les poids des exemples : $w_i \leftarrow w_i \, e^{-\alpha_t y_i h_t(x_i)}$, puis les renormaliser pour qu’ils somment à 1.

La prédiction finale est $\text{signe}\left(\sum_t \alpha_t h_t(x)\right)$ : un vote pondéré, où les modèles les plus fiables pèsent le plus.

Décortiquons l’étape 4. Si l’exemple est bien classé, $y_i h_t(x_i) = +1$ et son poids est multiplié par $e^{-\alpha_t} < 1$ : il pèse moins. S’il est mal classé, $y_i h_t(x_i) = -1$ et son poids est multiplié par $e^{\alpha_t} > 1$ : le modèle suivant devra y faire attention. Quant à $\alpha_t$, il est d’autant plus grand que l’erreur $\varepsilon_t$ est petite, et il s’annule quand $\varepsilon_t = 0{,}5$ (un modèle qui répond au hasard ne vote pas).

Chaque souche, à elle seule, est faible. Les exemples ratés grossissent d'un tour à l'autre et attirent la souche suivante ; le vote pondéré par les α construit une frontière qu'aucune souche ne sait tracer (données simulées).

Exemple

Au premier tour, une souche se trompe sur 20 % du poids total : $\varepsilon_1 = 0{,}2$. Alors $\alpha_1 = \frac{1}{2} \ln \frac{0{,}8}{0{,}2} = \frac{1}{2} \ln 4 \approx 0{,}693$. Les poids des exemples mal classés sont multipliés par $e^{0{,}693} = 2$, ceux des bien classés par $e^{-0{,}693} = 0{,}5$. Avant normalisation, les mal classés pèsent $0{,}2 \times 2 = 0{,}4$ et les bien classés $0{,}8 \times 0{,}5 = 0{,}4$ : après normalisation, la moitié du poids total repose sur les exemples ratés. Le modèle suivant ne peut plus les ignorer.

On montre qu’AdaBoost minimise la perte exponentielle $e^{-y \, s(x)}$ (chapitre 7). Revers de la médaille : il accorde de plus en plus de poids aux exemples difficiles, y compris aux exemples mal étiquetés, ce qui le rend sensible au bruit.

Le gradient boosting, et au-delà

Le gradient boosting généralise l’idée à n’importe quelle perte dérivable. Au lieu de repondérer les exemples, chaque nouvel arbre $h_t$ est entraîné à prédire ce qui manque au modèle actuel, c’est-à-dire le gradient négatif de la perte ; pour la MSE, ce sont simplement les résidus $y_i - F_{t-1}(x_i)$. Le modèle avance à petits pas :

$$F_t(x) = F_{t-1}(x) + \eta \, h_t(x)$$

où $F_t$ est le modèle après $t$ arbres et $\eta$ le taux d’apprentissage (learning rate), typiquement entre 0,01 et 0,1. Un petit $\eta$ demande plus d’arbres mais généralise mieux. On arrête l’ajout d’arbres quand l’erreur de validation cesse de baisser (arrêt précoce, early stopping).

Le quatrième arbre n'apprend pas y mais ce qui manque au modèle, les résidus ; on n'en ajoute qu'une fraction η. Au bout de 50 petits pas, le modèle colle aux données, d'où l'intérêt de l'arrêt précoce (données simulées).

Pour aller plus loin que ce cours, trois bibliothèques ont fait du gradient boosting la référence sur données tabulaires : XGBoost (régularisation des feuilles, approximation au second ordre), LightGBM (arbres construits feuille par feuille sur des histogrammes, très rapide sur de gros volumes) et CatBoost (traitement soigné des variables catégorielles). scikit-learn propose une version proche de LightGBM, HistGradientBoostingClassifier.

from sklearn.ensemble import HistGradientBoostingClassifier
from sklearn.model_selection import cross_val_score

gb = HistGradientBoostingClassifier(
    learning_rate=0.05,
    max_iter=500,             # nombre maximal d'arbres
    max_depth=3,              # arbres peu profonds
    early_stopping=True,      # arrêt quand la validation interne stagne
    random_state=0,
)
print(cross_val_score(gb, X, y, cv=5, scoring="roc_auc").mean())

Piège

Inverser les rôles donne de mauvais ensembles. Faire du bagging de souches, c’est moyenner des modèles trop simples : la moyenne de modèles biaisés reste biaisée. Faire du boosting d’arbres profonds sans arrêt précoce, c’est empiler des modèles qui apprennent déjà le bruit : on surapprend, et c’est long.

Quelles variables comptent ? L’importance des variables

Un ensemble de 500 arbres ne se lit plus. Mais on peut encore demander quelles caractéristiques il utilise le plus.

• L’importance par impureté (MDI, mean decrease in impurity) additionne, pour chaque variable, la baisse d’impureté apportée par toutes les questions qui l’utilisent, dans tous les arbres. Elle est gratuite (feature_importances_), mais biaisée : elle favorise les variables continues ou à nombreuses valeurs, qui offrent beaucoup de seuils possibles, et elle est calculée sur les données d’apprentissage.
• L’importance par permutation mélange au hasard les valeurs d’une variable dans un jeu de validation et mesure la baisse du score. Si le score s’effondre, la variable comptait. Plus coûteuse, elle est plus fiable.

En TP, sur le projet des rendez-vous médicaux manqués (chapitre 10), l’importance par impureté d’une forêt aléatoire plaçait en tête le délai entre la prise du rendez-vous et le rendez-vous (26,32 %), une variable que nous avions créée, suivi de la date de prise du rendez-vous (24,66 %) et de l’âge (17,22 %). Avec le recul, ce classement mérite prudence : la date de prise était un horodatage à la seconde près, qui prend un très grand nombre de valeurs différentes : exactement le type de variable que la MDI surestime. Une importance par permutation aurait permis de le vérifier.

from sklearn.inspection import permutation_importance
from sklearn.model_selection import train_test_split

X_app, X_val, y_app, y_val = train_test_split(X, y, test_size=0.3, stratify=y, random_state=0)
foret = RandomForestClassifier(n_estimators=500, random_state=0).fit(X_app, y_app)

resultat = permutation_importance(foret, X_val, y_val, n_repeats=20, random_state=0)
classement = pd.Series(resultat.importances_mean, index=X.columns).sort_values(ascending=False)
print(classement.head())

En entretien

« Le bagging entraîne des arbres profonds en parallèle sur des échantillons bootstrap et réduit la variance ; le boosting entraîne des arbres peu profonds en séquence, chacun corrigeant les erreurs des précédents, et réduit le biais. Le gradient boosting (XGBoost, LightGBM) est souvent le meilleur sur données tabulaires, mais il demande plus de réglages. »

En résumé

• Un vote de modèles est meilleur que chacun d’eux si les modèles sont bons et divers (erreurs peu corrélées).
• Le bagging entraîne des modèles instables sur des échantillons bootstrap (environ 63 % d’exemples distincts) et les fait voter ; les exemples hors sac donnent une estimation gratuite de l’erreur.
• La forêt aléatoire tire aussi les caractéristiques candidates à chaque nœud pour décorréler les arbres.
• AdaBoost enchaîne des modèles faibles en repondérant les exemples mal classés ; chaque modèle vote avec un poids $\alpha_t$ qui dépend de son erreur.
• Le gradient boosting ajuste chaque nouvel arbre sur les résidus (le gradient de la perte), avec un taux d’apprentissage et un arrêt précoce ; XGBoost, LightGBM et CatBoost en sont les implémentations de référence.
• L’importance par impureté est biaisée vers les variables à nombreuses valeurs ; l’importance par permutation sur un jeu de validation est plus fiable.

Exercices

Exercice · Le vote de trois modèles

facile

Trois classifieurs indépendants ont chacun 70 % de bonnes réponses. Quelle est l’exactitude de leur vote majoritaire ? Et si les trois classifieurs étaient identiques ?

Voir la solution

La majorité a raison si au moins deux des trois ont raison :

$$P = \binom{3}{2} 0{,}7^2 \times 0{,}3 + \binom{3}{3} 0{,}7^3 = 3 \times 0{,}147 + 0{,}343 = 0{,}784$$

Le vote atteint 78,4 %. Si les trois classifieurs étaient identiques, ils se tromperaient toujours ensemble, et le vote aurait exactement 70 % : sans diversité, l’ensemble n’apporte rien.

En code

Python

import numpy as np
from scipy.stats import binom

# Au moins 2 bonnes réponses sur 3, chaque modèle ayant raison avec probabilité 0,7
print(round(binom.sf(1, 3, 0.7), 3))              # 0.784

# Simulation : trois modèles indépendants, puis trois modèles identiques
rng = np.random.default_rng(0)
correct = rng.random((100_000, 3)) < 0.7          # une colonne par modèle
print(round((correct.sum(axis=1) >= 2).mean(), 3))            # 0.785
identiques = np.repeat(correct[:, :1], 3, axis=1) # trois copies du même modèle
print(round((identiques.sum(axis=1) >= 2).mean(), 3))         # 0.698 : pas mieux qu'un seul modèle

R

# Au moins 2 bonnes réponses sur 3, chaque modèle ayant raison avec probabilité 0,7
round(1 - pbinom(1, 3, 0.7), 3)                      # 0.784

# Simulation : trois modèles indépendants, puis trois modèles identiques
set.seed(0)
correct <- matrix(runif(3e5) < 0.7, ncol = 3)        # une colonne par modèle
round(mean(rowSums(correct) >= 2), 3)                # 0.784
identiques <- correct[, c(1, 1, 1)]                  # trois copies du même modèle
round(mean(rowSums(identiques) >= 2), 3)             # 0.699 : pas mieux qu'un seul modèle

Exercice · Un tour d'AdaBoost

moyen

On dispose de 8 exemples de poids égaux ($1/8$). Une souche classe mal 2 d’entre eux. Calculez $\varepsilon_1$, $\alpha_1$, puis les nouveaux poids des exemples bien et mal classés après normalisation.

Voir la solution

L’erreur pondérée vaut $\varepsilon_1 = 2 \times 1/8 = 0{,}25$. Le poids du modèle vaut $\alpha_1 = \frac{1}{2} \ln \frac{0{,}75}{0{,}25} = \frac{1}{2} \ln 3 \approx 0{,}549$.

Les mal classés sont multipliés par $e^{0{,}549} = \sqrt{3} \approx 1{,}732$, les bien classés par $e^{-0{,}549} = 1/\sqrt{3} \approx 0{,}577$. Avant normalisation :

• chaque mal classé : $0{,}125 \times 1{,}732 \approx 0{,}2165$ ;
• chaque bien classé : $0{,}125 \times 0{,}577 \approx 0{,}0722$.

La somme vaut $2 \times 0{,}2165 + 6 \times 0{,}0722 \approx 0{,}866$. Après normalisation, chaque mal classé pèse $0{,}2165 / 0{,}866 = 0{,}25$ et chaque bien classé $0{,}0722 / 0{,}866 \approx 0{,}083$. Les deux exemples ratés portent ensemble la moitié du poids total, comme dans l’exemple du cours : c’est une propriété générale d’AdaBoost.

En code

Python

import numpy as np

poids = np.full(8, 1 / 8)
mal_classe = np.array([True, True] + [False] * 6)     # la souche rate 2 exemples

epsilon = poids[mal_classe].sum()
alpha = 0.5 * np.log((1 - epsilon) / epsilon)
print(epsilon, round(alpha, 3))                       # 0.25  0.549

# y_i h(x_i) vaut -1 si mal classé, +1 sinon
poids = poids * np.exp(-alpha * np.where(mal_classe, -1, 1))
print(poids.round(4)[[0, 2]], round(poids.sum(), 3))  # [0.2165 0.0722]  0.866
poids = poids / poids.sum()
print(poids.round(3)[[0, 2]], round(poids[mal_classe].sum(), 3))  # [0.25 0.083]  0.5

R

poids <- rep(1 / 8, 8)
mal_classe <- c(TRUE, TRUE, rep(FALSE, 6))          # la souche rate 2 exemples

epsilon <- sum(poids[mal_classe])
alpha <- 0.5 * log((1 - epsilon) / epsilon)
c(epsilon, round(alpha, 3))                          # 0.25  0.549

# y_i h(x_i) vaut -1 si mal classé, +1 sinon
poids <- poids * exp(-alpha * ifelse(mal_classe, -1, 1))
round(c(poids[1], poids[3], sum(poids)), 4)          # 0.2165  0.0722  0.866
poids <- poids / sum(poids)
round(c(poids[1], poids[3], sum(poids[mal_classe])), 3)   # 0.25  0.083  0.5

Exercice · Plus d'arbres, toujours mieux ?

difficile

Un collègue entraîne un bagging d’arbres profonds sur heart.csv. Il constate que passer de 50 à 500 arbres n’améliore presque plus le score, alors que la formule de la variance d’une moyenne semble promettre une amélioration continue. Expliquez ce qu’il observe à l’aide de la formule $\rho \sigma^2 + \frac{1 - \rho}{B} \sigma^2$, et proposez un changement.

Voir la solution

Avec $B = 50$, le second terme vaut déjà $(1 - \rho)\sigma^2 / 50$, soit au plus 2 % de $\sigma^2$ : il reste très peu à gagner en augmentant $B$. Ce qui limite la variance de l’ensemble, c’est le premier terme, $\rho \sigma^2$, qui ne dépend pas du nombre d’arbres. Or des arbres entraînés sur des échantillons bootstrap d’un même jeu sont très corrélés, surtout si une ou deux variables dominent : ils posent tous à peu près les mêmes premières questions.

Pour progresser, il faut réduire $\rho$ : passer à une forêt aléatoire, qui ne propose à chaque nœud qu’un sous-ensemble aléatoire de caractéristiques (max_features="sqrt", ou même moins). Les arbres deviennent plus différents, la corrélation baisse, et la moyenne devient plus efficace. Ajouter des arbres ne fait jamais de mal au score d’une forêt, mais au-delà de quelques centaines, cela coûte surtout du temps de calcul.

En code

Python

import numpy as np

sigma2, rho = 1.0, 0.5
for B in [1, 50, 500]:
    print(B, round(rho * sigma2 + (1 - rho) / B * sigma2, 3))   # 1.0, 0.51, 0.501

# Simulation : B prédictions de variance 1, corrélées à rho (une part commune à tous les arbres)
rng = np.random.default_rng(0)
for B in [50, 500]:
    commun = rng.normal(size=(5_000, 1))
    propre = rng.normal(size=(5_000, B))
    predictions = np.sqrt(rho) * commun + np.sqrt(1 - rho) * propre
    print(B, round(predictions.mean(axis=1).var(), 3))          # 0.508 puis 0.513 : pas de gain

# Réduire rho (forêt aléatoire) fait bien plus baisser la variance que multiplier les arbres
print(round(0.2 * sigma2 + (1 - 0.2) / 50 * sigma2, 3))         # 0.216

R

variance_moyenne <- function(B, rho, sigma2 = 1) rho * sigma2 + (1 - rho) / B * sigma2
round(variance_moyenne(c(1, 50, 500), rho = 0.5), 3)      # 1, 0.51, 0.501

# Simulation : B prédictions de variance 1, corrélées à rho (une part commune à tous les arbres)
set.seed(0)
rho <- 0.5
for (B in c(50, 500)) {
  commun <- rnorm(5000)
  propre <- matrix(rnorm(5000 * B), ncol = B)
  predictions <- sqrt(rho) * commun + sqrt(1 - rho) * propre
  cat(B, round(var(rowMeans(predictions)), 3), "\n")     # 0.505 puis 0.502 : pas de gain
}

# Réduire rho (forêt aléatoire) fait bien plus baisser la variance que multiplier les arbres
variance_moyenne(50, rho = 0.2)                           # 0.216