Les arbres de décision et les ensembles

Tous les modèles vus jusqu’ici ajustent une formule globale unique sur tout l’espace des prédicteurs. Les arbres de décision font l’inverse : ils partitionnent l’espace en régions rectangulaires et prédisent une constante dans chacune. Cela gère interactions et non-linéarités sans que personne ne les spécifie, et produit un modèle qu’on peut lire à voix haute - au prix d’être, seul, nettement peu fiable.

Cette dernière faiblesse se révèle réparable d’une manière qui fait des arbres l’ossature de certaines des méthodes généralistes les plus puissantes qui soient.

A. Comment un arbre prédit

Un arbre pose une suite de questions oui/non sur les prédicteurs. Chaque nœud interne teste un prédicteur contre un seuil ; chaque feuille porte une prédiction - la moyenne des réponses d’entraînement de cette région en régression, la classe majoritaire en classification.

Prédire, c’est marcher de la racine à une feuille. Rien n’est calculé ; on suit les branches. C’est pourquoi les arbres sont présentés comme interprétables : le chemin est l’explication.

B. Faire pousser l’arbre

Trouver la partition optimale est infaisable en calcul, si bien que les arbres sont construits par une procédure gloutonne appelée division binaire récursive.

À chaque étape, on considère chaque prédicteur $X_j$ et chaque point de coupe possible $s$, divisant la région courante en $\{X_j < s\}$ et $\{X_j \ge s\}$. On retient le couple $(j, s)$ qui améliore le plus le critère, on effectue la division, puis on répète indépendamment dans chaque nouvelle région.

C’est glouton parce qu’on prend la meilleure division disponible maintenant, sans vérifier si une division moins bonne maintenant permettrait bien mieux plus tard. C’est descendant parce qu’on part de la racine et qu’on ne revient jamais sur une décision.

En régression, le critère est la RSS, sommée sur les deux régions filles :

$$\sum_{i \in R_1}(y_i - \hat y_{R_1})^2 + \sum_{i \in R_2}(y_i - \hat y_{R_2})^2 .$$

C. Critères de division en classification

Le critère évident est le taux de mauvaise classification. Il se révèle être un mauvais choix, et comprendre pourquoi vaut le détour.

Les deux solutions de rechange standard, pour une région de proportions de classe $\hat p_{mk}$ :

$$G = \sum_{k=1}^{K}\hat p_{mk}\big(1 - \hat p_{mk}\big) \qquad\text{(Gini index)},$$ $$D = -\sum_{k=1}^{K}\hat p_{mk}\log \hat p_{mk} \qquad\text{(cross-entropy)} .$$

Toutes deux mesurent la pureté du nœud : proches de zéro quand une classe domine, maximales quand les classes sont équitablement mélangées. Toutes deux sont en outre sensibles aux variations de proportions partout, alors que le taux de mauvaise classification ne remarque que le basculement de la classe majoritaire. Une division qui redistribue les observations sans faire basculer la classe majoritaire d’aucune région laisse inchangé le taux d’erreur de la prédiction par vote majoritaire, mais Gini et l’entropie croisée enregistrent l’amélioration réelle - d’où de meilleurs arbres.

La figure prend vingt observations, dix par classe, un échantillon différent de la division à dix points déroulée plus bas. Faites glisser Seuil de coupure : le taux d’erreur reste à 0,2000 sur les cinq seuils du milieu, tandis que l’indice de Gini bouge.

D. Dérouler une division à la main

Dix observations, cinq dans chaque classe. Une division candidate envoie 6 observations à gauche (4 de classe 1, 2 de classe 0) et 4 à droite (1 de classe 1, 3 de classe 0).

Pour deux classes, $G = 2p(1-p)$ où $p$ est la proportion de classe 1.

Le nœud parent. $p = 5/10 = 0.5$, donc

$$G_{\text{parent}} = 2(0.5)(0.5) = 0.5 ,$$

le maximum possible pour deux classes - un nœud parfaitement mélangé.

Enfant gauche. $p = 4/6 = 0.6667$ :

$$G_L = 2\left(\tfrac{4}{6}\right)\left(\tfrac{2}{6}\right) = 2 \times \tfrac{8}{36} = 0.4444 .$$

Enfant droit. $p = 1/4 = 0.25$ :

$$G_R = 2(0.25)(0.75) = 0.375 .$$

Pondérés par la taille des régions, puisque la valeur d’une division dépend du nombre d’observations qu’elle touche :

$$G_{\text{split}} = \frac{6}{10}(0.4444) + \frac{4}{10}(0.375) = 0.2667 + 0.15 = 0.4167 .$$

L’amélioration :

$$\Delta G = 0.5 - 0.4167 = 0.0833 .$$

L’algorithme de croissance calcule exactement cela pour chaque couple $(j, s)$ et retient le plus grand $\Delta G$.

E. Pourquoi un arbre isolé est peu fiable

Poussé assez loin, un arbre peut isoler chaque observation d’entraînement dans sa propre feuille et atteindre une erreur d’entraînement nulle. C’est du surajustement pur. Mais même un arbre bien élagué a un problème plus profond : une forte variance.

Comme la division est gloutonne et hiérarchique, un petit changement dans les données peut changer la division racine - et toutes les divisions en dessous sont alors choisies sur des données partitionnées autrement. Deux moitiés aléatoires du même jeu de données peuvent produire des arbres qui ne se ressemblent en rien. Dans le langage du compromis biais-variance, les arbres siègent à l’extrême faible biais, forte variance.

F. Le bagging : moyenner la variance

Si une méthode a une forte variance, moyennez-en de nombreuses instances. Pour $B$ ajustements indépendants de variance $\sigma^2$ chacun, la moyenne a une variance $\sigma^2/B$.

Nous n’avons qu’un jeu de données, alors le bagging (agrégation bootstrap) en fabrique beaucoup : tirez $B$ échantillons bootstrap - $n$ observations tirées avec remise - faites pousser sur chacun un arbre profond non élagué, et moyennez les prédictions (ou prenez un vote majoritaire).

Les arbres profonds sont exactement ce qu’il faut ici. Chacun a un faible biais et une forte variance, et le moyennage attaque la variance en laissant le faible biais intact.

Le bagging offre en prime un ensemble de validation gratuit. Chaque échantillon bootstrap omet environ un tiers des observations - la probabilité qu’une observation donnée soit manquée est $(1 - 1/n)^n \to e^{-1} \approx 0.368$. Prédire chaque observation à l’aide des seuls arbres qui ne l’ont pas vue donne l’estimation d’erreur out-of-bag, sans coût de calcul supplémentaire.

G. Les forêts aléatoires : décorréler les arbres

Le bagging a une limite. Si un prédicteur est fortement dominant, il sera la division racine dans presque tous les échantillons bootstrap, si bien que les arbres sont très corrélés - et moyenner des quantités corrélées réduit bien moins la variance que moyenner des quantités indépendantes. (Le même fait expliquait pourquoi la LOOCV est plus bruitée que le 10-fold dans La validation croisée et le rééchantillonnage.)

Les forêts aléatoires ajoutent un handicap délibéré : à chaque division, seul un sous-ensemble aléatoire de $m$ prédicteurs est même considéré, typiquement $m \approx \sqrt{p}$ en classification. La plupart des divisions ne peuvent pas utiliser le prédicteur dominant, les autres prédicteurs ont donc leur tour, les arbres deviennent réellement différents et la moyenne est bien plus efficace.

C’est une idée frappante : chaque arbre est rendu moins bon à dessein, et l’ensemble s’en trouve meilleur.

H. Ce que vous cédez

L’interprétabilité qui motivait les arbres disparaît dès que vous en moyennez des centaines. Les mesures d’importance des variables - de combien chaque prédicteur a réduit Gini dans la forêt - récupèrent un résumé, mais pas le chemin si-alors lisible.

Les scores d’importance ne sont pas causals. Un prédicteur peut être bien classé parce qu’il est corrélé au véritable moteur, et l’importance fondée sur l’impureté est biaisée vers les prédicteurs à forte cardinalité. Traitez-les comme une description de ce que le modèle a utilisé, non de ce qui compte dans le monde.

À retenir

• Les arbres partitionnent l’espace des prédicteurs et prédisent une constante par région, construits par division binaire récursive gloutonne.
• Gini et l’entropie croisée battent le taux de mauvaise classification comme critères, car ils réagissent aux changements de pureté qui ne font pas basculer la majorité.
• Notre division : Gini parent $0.5$, enfants $0.4444$ et $0.375$, pondéré $0.4167$, gain $0.0833$.
• Les arbres isolés sont à faible biais et forte variance - instables sous de petits changements de données.
• Le bagging moyenne des arbres profonds sur des échantillons bootstrap, avec l’erreur out-of-bag en prime ; les forêts aléatoires restreignent en outre chaque division à $m \approx \sqrt p$ prédicteurs pour décorréler les arbres.
• L’ensemble achète de l’exactitude avec de l’interprétabilité.

La suite

Les arbres découpent l’espace d’entrée par des coupes alignées sur les axes. Une autre famille construit des fonctions souples en composant des transformations non linéaires simples, et les apprend en suivant le gradient de l’erreur. C’est La rétropropagation et la descente de gradient.