8. Arbres de décision et méthodes d'ensemble
Pourquoi faire confiance à un seul modèle quand un comité peut voter ? Ce module construit la boîte à outils des ensembles : le bootstrap et le bagging pour réduire la variance, AdaBoost pour transformer des apprenants faibles en un apprenant fort, les arbres de décision comme apprenant de base favori, et les forêts aléatoires comme la combinaison qui gagne en pratique.
8.1 Pourquoi un seul modèle ?
Chaque module jusqu'ici entraîne un modèle et le garde. Un comité de \(M\) modèles est presque toujours meilleur que n'importe lequel de ses membres. La combinaison est une moyenne en régression et un vote majoritaire en classification :
\[\boxed{ h_{\text{com}}(x) = \frac{1}{M}\sum_{i=1}^{M} h_i(x) \ \ \text{(régression)}, \qquad h_{\text{com}}(x) = \text{vote majoritaire sur } h_1(x), \dots, h_M(x) \ \ \text{(classification)} }\]Les membres peuvent venir de \(M\) algorithmes différents, d'un même algorithme lancé avec \(M\) réglages d'hyperparamètres, ou, cas le plus intéressant, d'un algorithme identique entraîné \(M\) fois. Deux familles dominent ce dernier cas, et elles sont complémentaires :
| Famille | Modèles de base | Construction | Réduit surtout |
|---|---|---|---|
| Bagging | forte capacité (arbres profonds) | en parallèle, sur données rééchantillonnées | la variance |
| Boosting | faible capacité (souches) | en séquence, sur données repondérées | le biais |
8.2 Le bootstrap : moyenner la variance
Pourquoi combiner aide-t-il ? Entraînez le même modèle flexible, un polynôme de degré 25, sur 100 ensembles d'entraînement différents et les ajustements individuels divergent violemment. Leur moyenne, elle, épouse la vraie courbe.
À gauche : 100 ajustements de degré 25, un par ensemble d'entraînement, chacun poursuivant son propre bruit. À droite : leur moyenne est bien plus proche de la vérité, les fluctuations s'annulent.
Le gain se quantifie. Si \(B\) modèles ont chacun une variance \(\sigma^2\) et une corrélation deux à deux \(\rho\), la variance de leur moyenne vaut
\[\boxed{ \rho\sigma^2+\frac{1-\rho}{B}\,\sigma^2 }\]Pour des modèles indépendants (\(\rho = 0\)) la variance décroît comme \(\sigma^2/B\). Le hic : il faut de nombreux ensembles d'entraînement, et hors données synthétiques on en a exactement un. Le bootstrap en fabrique d'autres en rééchantillonnant celui que l'on a, par \(N\) tirages avec remise :
\[\boxed{ D_{\text{boot}} = \left\{ \left(x^{(i_1)}, y^{(i_1)}\right), \dots, \left(x^{(i_N)}, y^{(i_N)}\right) \right\}, \qquad i_k \ \text{tiré uniformément dans} \ \{1, \dots, N\} }\]Le même exemple peut apparaître plusieurs fois dans un rééchantillon, et la probabilité qu'un exemple donné n'apparaisse jamais vaut \((1-\tfrac1N)^N\to e^{-1}\approx0{,}37\) : environ 37 % des données restent hors de chaque rééchantillon. Ce sont ses exemples hors-sac (OOB), que les forêts aléatoires mettront à profit plus bas.
8.3 Le bagging
Le bagging (Bootstrap AGGregating) est le comité construit sur le bootstrap : rééchantillonner \(m\) ensembles d'entraînement, entraîner un modèle sur chacun, combiner les votes.
Un jeu de données devient \(m\) rééchantillons bootstrap, chacun entraîne son propre modèle, et seuls les votes se rencontrent.
\[\boxed{ h_{\text{bag}}(x)=\frac{1}{m}\sum_{i=1}^{m} h_i(x) \ \ \text{(régression)}, \qquad h_{\text{bag}}(x)=\mathrm{sign}\!\left(\sum_{i=1}^{m} h_i(x)\right) \ \ \text{(2 classes)}, \qquad \hat{y}=\arg\max_c \ \text{votes pour } c \ \ \text{(K classes)} }\]Remarque : moyenner laisse le biais inchangé tout en réduisant la variance, le bagging convient donc aux modèles de base à faible biais et forte variance, exactement les arbres profonds de la section 8.5. Un modèle qui sous-apprend sous-apprend encore après bagging.
8.4 Le boosting : AdaBoost
Le boosting fait le pari inverse : combiner de nombreux apprenants faibles, à peine meilleurs que le hasard, en un apprenant fort. L'ensemble est une somme pondérée construite un apprenant à la fois :
\[\boxed{ H_T(x)=\sum_{t=1}^{T}\alpha_t\,h_t(x) }\]Trois différences avec le bagging :
- La combinaison est pondérée : un apprenant précis gagne un grand vote \(\alpha_t\), un apprenant médiocre un petit.
- Il n'y a pas de bootstrap : chaque exemple sert à entraîner chaque apprenant.
- Les données sont repondérées : les exemples mal classés par \(h_t\) gagnent du poids, donc \(h_{t+1}\) se concentre sur eux.
8.4.1 L'algorithme
Avec des étiquettes \(y\in\{-1,+1\}\), on garde un poids \(w^{(i)}\) par exemple, initialisé à \(1/N\). À chaque tour \(t = 1, \dots, T\) :
- Entraîner l'apprenant faible \(h_t\) sur les données pondérées.
- Calculer son erreur pondérée \(\varepsilon_t = \sum_{i \in \mathcal{M}_t} w^{(i)}\) sur l'ensemble mal classé \(\mathcal{M}_t\).
- Lui donner son vote, grand quand l'erreur est petite :
- Repondérer puis renormaliser, si bien que les exemples mal classés (\(y^{(i)}h_t(x^{(i)})<0\)) gagnent du poids :
Le classifieur final est le vote pondéré \(H_T(x) = \mathrm{sign}\big(\sum_t \alpha_t h_t(x)\big)\).
Chaque tour ajuste une souche aux données pondérées (taille des points = poids). Les points mal classés gonflent, orientant la souche suivante, et le vote pondéré de trois coupures alignées sur les axes dessine déjà une frontière crénelée, non linéaire.
Remarque : l'apprenant faible classique est la souche (stump), un arbre à une seule coupure perpendiculaire à un axe. Les souches sont très rapides, leur combinaison donne les frontières en escalier ci-dessus, et les \(\alpha_t\) appris servent aussi de classement des variables utiles : les variables dont les souches gagnent de grands votes sont les informatives.
8.4.2 Gradient boosting
Le gradient boosting généralise l'idée à toute perte différentiable \(L\). À l'étape \(t\), il ajuste l'apprenant suivant sur l'opposé du gradient de la perte évalué au modèle courant, le pseudo-résidu défini par
\[\boxed{ r^{(i)}_t=-\left[\frac{\partial L\big(y^{(i)},f(x^{(i)})\big)}{\partial f}\right]_{f=H_{t-1}} }\]Le modèle est ensuite mis à jour avec un taux d'apprentissage (rétrécissement) \(\nu\in(0,1]\) :
\[\boxed{ H_t=H_{t-1}+\nu\,\alpha_t\,h_t }\]Remarque : avec une perte quadratique, le pseudo-résidu est simplement le résidu ordinaire \(y^{(i)}-H_{t-1}(x^{(i)})\), donc chaque arbre ajuste ce que le modèle courant se trompe encore.
| propriété | bagging | boosting |
|---|---|---|
| entraînement | parallèle, indépendant | séquentiel, chacun sur les erreurs précédentes |
| apprenants de base | profonds, faible biais | peu profonds, fort biais |
| réduit surtout | la variance | le biais |
| repondération | aucune (bootstrap) | poids ou pseudo-résidus |
8.5 Arbres de décision
8.5.1 Des souches aux arbres
Une souche pose une question sur une variable. Enchaînez les questions, chaque réponse menant à la souche suivante, et vous obtenez un arbre de décision : une racine, des nœuds internes, et des feuilles qui pavent l'espace d'entrée.
Trois coupures découpent le plan en quatre régions (à gauche), et les trois mêmes coupures se lisent comme un arbre (à droite) : la racine et les nœuds internes testent des variables, les feuilles prédisent.
8.5.2 L'arbre comme partition
Un arbre CART partitionne l'espace d'entrée en \(M\) régions disjointes \(R_1,\dots,R_M\) (les feuilles) et prédit une constante \(c_m\) sur chacune. La prédiction est définie par
\[\boxed{ h(x)=\sum_{m=1}^{M} c_m\,\mathbf{1}\{x\in R_m\} }\]Chaque nœud interne teste une variable contre un seuil, \(x_j\le s\), envoyant un exemple à gauche ou à droite. Un chemin de la racine à une feuille est une conjonction de tels tests.
Remarque : les régions sont des boîtes alignées sur les axes, donc la frontière de décision est en escalier. Un arbre seul a un faible biais mais une forte variance : laissé libre, il coupe jusqu'à isoler chaque valeur aberrante.
Un arbre découpe l'espace en régions alignées sur les axes, chacune à prédiction constante.
8.5.3 Impureté et choix de la coupure
Quelle question un nœud doit-il poser ? Celle qui laisse les enfants aussi purs que possible. Pour une région de proportions de classes \(\hat p_k\), l'impureté mesure le mélange des étiquettes. L'indice de Gini est défini par
\[\boxed{ G = 1-\sum_{k}\hat p_k^{\,2} }\]et l'entropie par
\[\boxed{ H = -\sum_{k}\hat p_k\log_2\hat p_k }\]Une coupure candidate envoie \(N_-\) exemples vers l'enfant \(R_-\) et \(N_+\) vers \(R_+\) sur \(N\) au total. Son gain d'information est défini par
\[\boxed{ IG = I(\text{parent})-\frac{N_-}{N}\,I(R_-)-\frac{N_+}{N}\,I(R_+) }\]où \(I\) est l'impureté choisie. CART retient gloutonnement la variable et le seuil qui maximisent \(IG\) à chaque nœud, et un nœud dont l'impureté est déjà faible ne vaut pas la peine d'être coupé : c'est le cadran du surapprentissage.
| critère | formule | plage (binaire) | note |
|---|---|---|---|
| Gini | \(1-\sum_k\hat p_k^{2}\) | \([0,0.5]\) | moins coûteux, sans logarithme |
| entropie | \(-\sum_k\hat p_k\log_2\hat p_k\) | \([0,1]\) | théorie de l'information |
Remarque : les deux critères choisissent presque toujours la même coupure. Gini est le défaut de la plupart des implémentations car il évite le logarithme.
8.5.4 Arbres de régression
En régression, la valeur de la feuille est la moyenne des cibles dans la région, définie par
\[\boxed{ c_m=\frac{1}{N_m}\sum_{x^{(i)}\in R_m} y^{(i)} }\]et les coupures minimisent l'erreur quadratique intra-région plutôt qu'une impureté de classification.
8.5.5 Élagage
Un arbre non élagué ajuste exactement l'ensemble d'entraînement et surapprend. L'élagage à complexité coûteuse arbitre entre l'ajustement et la taille de l'arbre \(|T|\) (le nombre de feuilles) via une pénalité \(\alpha\ge0\) :
\[\boxed{ C_\alpha(T)=\sum_{m} N_m\,I(R_m)+\alpha\,|T| }\]
Augmenter \(\alpha\) effondre les coupures les plus faibles, produisant une suite emboîtée de sous-arbres. Le meilleur \(\alpha\) est choisi par la validation croisée de Concepts généraux.
8.6 Forêts aléatoires
Une forêt aléatoire est du bagging appliqué à des arbres profonds, plus une seconde source d'aléa. La formule de variance de la section 8.2 disait que le terme résiduel \(\rho\sigma^2\) survit à la moyenne, il faut donc décorréler les arbres : à chaque coupure, seul un sous-ensemble aléatoire de \(m_{\text{try}}\) variables est considéré comme candidat. Les choix usuels sont
\[\boxed{ m_{\text{try}}=\lfloor\sqrt{n}\,\rfloor\ \text{(classification)},\qquad m_{\text{try}}=\lfloor n/3\rfloor\ \text{(régression)} }\]Restreindre les variables candidates empêche tous les arbres de couper sur la même variable dominante, ce qui rend les erreurs des arbres aussi peu corrélées que possible et abaisse \(\rho\).
Remarque : l'erreur OOB moyenne l'erreur de chaque arbre uniquement sur les exemples qu'il n'a jamais vus (les 37 % de la section 8.2), donnant une estimation proche d'une validation croisée sans coût supplémentaire.
| propriété | bagging | forêt aléatoire |
|---|---|---|
| rééchantillonnage | bootstrap | bootstrap |
| variables candidates | les \(n\) variables | \(m_{\text{try}}\) variables aléatoires |
| corrélation des arbres \(\rho\) | plus élevée | plus faible |
| réduction de variance | modérée | plus forte |
(a) Un arbre profond seul surajuste avec une frontière en escalier. (b) Une forêt aléatoire moyenne de nombreux arbres pour une frontière plus lisse.
Ceci complète le cœur du cours sur l'apprentissage supervisé. Pour faire passer ces modèles d'un notebook à un service en production, poursuivez avec le cours MLOps.
Suivant : Vue d'ensemble du cours