7. Arbres de décision et méthodes d'ensemble
Les modèles d'arbre partitionnent l'espace d'entrée en régions alignées sur les axes et ajustent une constante par région, ce qui donne des prédicteurs interprétables mais à forte variance. Les méthodes d'ensemble combinent plusieurs arbres : le bagging et les forêts aléatoires moyennent des arbres construits indépendamment pour réduire la variance, tandis que le boosting construit les arbres de façon séquentielle pour réduire le biais.
Objectifs
- Exprimer un arbre comme une fonction constante par morceaux et choisir les coupures avec un critère d'impureté.
- Contrôler le surapprentissage par l'élagage à complexité coûteuse.
- Réduire la variance par le bagging et décorréler les arbres via le sous-échantillonnage des variables.
- Estimer gratuitement l'erreur de généralisation avec les échantillons hors-sac.
- Construire un prédicteur fort comme somme additive d'apprenants faibles (AdaBoost, gradient boosting).
7.1 Arbres de décision CART
7.1.1 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.
7.1.2 Impureté et choix de la coupure
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.
| 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.
7.1.3 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.
7.1.4 É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 validation croisée.
graph TD A["x_j <= s ?"] -->|"oui"| B["x_k <= t ?"] A -->|"non"| C["feuille R3"] B -->|"oui"| D["feuille R1"] B -->|"non"| E["feuille R2"]
Un arbre découpe l'espace en régions alignées sur les axes, chacune à prédiction constante.
7.2 Forêts aléatoires
7.2.1 Bagging
Le bagging (bootstrap aggregating) entraîne \(B\) arbres sur \(B\) rééchantillons bootstrap des données et les moyenne. Le prédicteur agrégé est défini par
\[\boxed{ h_{\text{bag}}(x)=\frac{1}{B}\sum_{b=1}^{B} h_b(x) }\]En classification, la moyenne est remplacée par un vote majoritaire. Moyenner laisse le biais inchangé tout en réduisant la variance.
Un échantillon bootstrap tire \(N\) exemples avec remise parmi \(N\) exemples. La probabilité qu'un exemple donné ne soit jamais tiré vaut \((1-\tfrac1N)^N\to e^{-1}\approx0{,}37\), donc environ 37 % des données restent hors de chaque arbre. Ce sont ses exemples hors-sac (OOB).
7.2.2 Variance d'une moyenne
Si les \(B\) arbres 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 }\]Le second terme s'annule quand \(B\) croît, mais le premier, \(\rho\sigma^2\), persiste. Réduire la corrélation \(\rho\) entre les arbres est donc le levier clé, et c'est précisément ce que visent les forêts aléatoires.
7.2.3 Forêts aléatoires
Une forêt aléatoire est du bagging avec sous-échantillonnage des variables : à 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 décorrèle les arbres et abaisse \(\rho\).
Remarque : l'erreur OOB moyenne l'erreur de chaque arbre uniquement sur les exemples qu'il n'a jamais vus, 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 |
graph TD A["jeu d'entrainement"] --> B1["echantillon bootstrap 1"] A --> B2["echantillon bootstrap 2"] A --> B3["echantillon bootstrap B"] B1 --> T1["arbre 1"] B2 --> T2["arbre 2"] B3 --> T3["arbre B"] T1 --> AGG["agregation : moyenne ou vote"] T2 --> AGG T3 --> AGG
(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.
7.3 Boosting
7.3.1 Modèle additif
Le boosting construit un prédicteur comme une somme pondérée de \(T\) apprenants faibles \(h_t\) (typiquement des arbres peu profonds), ajustés un à un. Le modèle additif est défini par
\[\boxed{ H_T(x)=\sum_{t=1}^{T}\alpha_t\,h_t(x) }\]Chaque étape corrige les erreurs de la somme courante, donc l'ensemble est construit de façon séquentielle et réduit le biais plutôt que la variance.
7.3.2 AdaBoost
Avec des étiquettes \(y\in\{-1,+1\}\), AdaBoost conserve des poids d'exemples \(w^{(i)}\) qui se concentrent sur les points actuellement mal classés. Au tour \(t\), l'apprenant faible a une erreur pondérée \(\varepsilon_t\), et son coefficient est défini par
\[\boxed{ \alpha_t=\tfrac12\log\frac{1-\varepsilon_t}{\varepsilon_t} }\]ainsi un apprenant plus précis (\(\varepsilon_t\) petit) obtient un vote plus grand. Les poids sont ensuite mis à jour par
\[\boxed{ w^{(i)}\leftarrow w^{(i)}\exp\!\big(-\alpha_t\,y^{(i)}h_t(x^{(i)})\big) }\]puis renormalisés. Les exemples mal classés (\(y^{(i)}h_t(x^{(i)})<0\)) gagnent du poids, donc l'apprenant suivant se concentre sur eux.
7.3.3 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 |
graph LR A["apprenant faible 1"] --> B["apprenant faible 2"] B --> C["apprenant faible 3"] C --> D["apprenant faible T"] D --> E["somme ponderee H_T"]
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