Les informations pratiques concernant le déroulement de l’unité d’enseignement RCP209 « Apprentissage, réseaux de neurones et modèles graphiques » au Cnam se trouvent dans ce préambule.

Cours - Forêts Aléatoires

« Statistics is the grammar of science. »

(Karl Pearson)

[Diapositives du cours]

Dans cette séance nous examinons plusieurs stratégies pour construire (ou assembler) des classifieurs performants à partir de classifieurs de base plus modestes. Ce sont les « méthodes d’agrégation ». Nous allons commencer par une discussion des avantages et des défauts des arbres de décision, surtout le problème des estimateurs de variance élevée. Ensuite nous présenterons les deux approches classiques conçues pour répondre à ce problème : le « Bagging » et les « Forêts aléatoires » et nous finirons par une courte introduction au Boosting, qui permet de combiner la sortie de plusieurs classifieurs simples pour en obtenir un meilleur résultat.

Estimateurs de variance élevée

Avantages des arbres de décision

Les arbres de décision ont un nombre de propriétés qui font d’eux un outil précieux, surtout quand il s’agit de faire l’analyse rapide d’un jeu de données ou d’élaborer un prototype de classifieur :

  • Modèle white box : le résultat est facile à conceptualiser, à visualiser et a interpréter.

  • Ils nécessitent peu de préparation de données (e.g. normalisation, etc.).

  • Le coût d’utilisation des arbres est logarithmique (classification d’une nouvelle donnée très rapide).

  • Ils sont capables d’utiliser des données catégorielles et continues.

  • Ils sont capables de gérer des problèmes multi-classes.

  • Ils ont un bon comportement par rapport aux valeurs extrêmes (outliers).

  • Ils gèrent bien les données manquantes.

Défauts des arbres de décision

  • Parfois les arbres générés ne sont pas équilibrés (ce qui implique que le temps de parcours n’est plus logarithmique). Il est donc recommandé d’équilibrer la base de données avant la construction, pour éviter qu’une classe domine (en termes de nombre d’exemples d’apprentissage).

  • Sur-apprentissage : parfois les arbres générés sont trop complexes et généralisent mal (solution : élagage, le contrôle de la profondeur de l’arbre et de la taille des feuilles).

  • Ils sont instables : des changements légers dans les données produisent des arbres très différents. Les changements des nœuds proches de la racine affectent beaucoup l’arbre résultant. On dit que les arbres produisent des estimateurs de variance élevée.

Le besoin de répondre à ce troisième problème, qui n’admet pas de solution par optimisation algorithmique, a conduit aux approches de type Bagging et « Forêts aléatoires ».

L’idée derrière et celle de la Réduction de variance : on utilise pour cela la moyenne de plusieurs estimateurs, calculés sur des données légèrement différentes, en somme utiliser le hasard pour améliorer les performances des algorithmes de base (qui sont les arbres de décision CART ici).

Ces améliorations ont été proposées par Breiman et al. dans [Bre96], [Bre01] et ont été beaucoup étudiées.

Bagging

Nous commençons par le Bagging (Bootstrap Agregating). Soit la base d’apprentissage décrite comme suit :

  • Les données sont décrites par les attributs : \(A_1, ..., A_p\), classe : \(C\),

  • Données d’apprentissage : \((x_i, y_i), x_i\in \mathbb{R}^p, y_i\in \mathbb{R}, i=1,...,N\),

  • \(y_i\) peuvent être des valeurs continues ou discrètes (étiquettes des classes),

  • \(x_i = (a_1^{(i)}, ..., a_p^{(i)})\).

On considère \(G(x)\) un modèle de prédiction appris sur un échantillon de données \(z = \{(x_i, y_i)\}_{i=1}^n\) (e.g. arbre de décision CART).

Algorithme bagging :

  • On tire au hasard dans la base d’apprentissage \(B\) échantillons avec remise \(z_i, i = 1, \dots, B\) (chaque échantillon ayant \(n\) points) — appelés échantillons bootstrap ;

  • Pour chaque échantillon \(i\) on calcule le modèle \(G_i(x)\) ;

  • Régression : agrégation par la moyenne \(G(x) = \frac{1}{B}\sum_{i=1}^BG_i(x)\) ;

  • Classement : agrégation par vote \(G(x) = \mathrm{Vote\,majoritaire\,}(G_1(x), \dots, G_B(x))\).

C’est l’estimateur moyenne qui aide a réduire la variance :

  • \(X_1, X_2, \dots, X_n\) variables aléatoires i.i.d. de moyenne \(\mu\) et variance \(\sigma^2\),

  • La moyenne \(\frac{1}{n}(X_1 + X_2 + \dots + X_n)\) est de variance \(\sigma^2/n\).

Le critère de performance pour le calcul de \(B\) est l’erreur OOB (Out Of Bag) :

  • Au lieu de faire un découpage classique test/validation de la base d’apprentissage, pour chaque \(x_k\) de la base d’apprentissage l’erreur OOB de prédiction est donné par la moyenne des erreurs des classifieurs \(G_i\) tel que \(x_i \notin z_i\) (donc \(x_i\) ne fait pas partie de leur échantillon de bootstrap de \(G_i\)).

  • On choisit \(B\) ou l’erreur se stabilise et ne descend plus.

Les défauts du bagging :

Les estimateurs \(G_i\) ne sont pas en réalité indépendants. En effet, \(G_i\) sont calculés sur des échantillons qui se recouvrent fortement (tirage avec remise) et donc ils sont corrélés.

Si \(X_1, X_2, \dots, X_B\) sont issus de variables aléatoires identiquement distribuées (mais pas indépendantes) de moyenne \(\mu\), variance \(\sigma^2\) et corrélation \(\rho = Corr(X_i, X_j), \forall i\neq j\), alors \(Y = \frac{1}{B}(X_1 + X_2 + \dots + X_B)\) est de variance

\[Var(Y) = \rho \sigma^2 + \frac{1-\rho}{B} \sigma^2\]

Quand \(B\) est grand le 2ème terme est négligeable mais le 1er non.

L’amélioration proposée par les forêts aléatoires est de baisser la corrélation entre les \(G_i\) à l’aide d’une étape supplémentaire de randomisation.

Forêts aléatoires

Les forêts aléatoires sont donc une amélioration du bagging pour les arbres de décision CART dans le but de rendre les arbres utilisés plus indépendants (moins corrélés).

Caractéristiques :

  • Elles donnent de bons résultats surtout en grande dimension,

  • Elles sont très simples à mettre en œuvre,

  • Elles ont peu de paramètres.

Algorithme « forêts aléatoires » [Bre01] :

  • On tire au hasard dans la base d’apprentissage \(B\) échantillons avec remise \(z_i, i = 1, \dots, B\) (chaque échantillon ayant \(n\) points).

  • Pour chaque échantillon \(i\) on construit un arbre CART \(G_i(x)\) selon un algorithme légèrement modifié : a chaque fois qu’un nœud doit être coupé (étape “split”) on tire au hasard une partie des attributs (\(q\) parmi les \(p\) attributs) et on choisit le meilleur découpage dans ce sous-ensemble.

  • Régression : agrégation par la moyenne \(G(x) = \frac{1}{B}\sum_{i=1}^BG_i(x)\).

  • Classement : agrégation par vote \(G(x) = \mathrm{Vote\,majoritaire\,}(G_1(x), \dots, G_B(x))\).

Les arbres sont moins corrélés car :

  • Ils sont appris sur un ensemble différent d’attributs.

  • Ils sont construits sur des échantillons différents.

Commentaires :

  • On se limite en général à des arbres pas très profonds (pour le Bagging il faut des arbres profonds pour réduire leur corrélation, mais les arbres très profonds souffrent de sur-apprentissage).

  • Chaque arbre est petit donc moins performant, mais l’agrégation compense pour ce manquement (chaque attribut se retrouve typiquement dans plusieurs arbres).

  • Comme pour le Bagging on utilise l’erreur OOB pour prévenir le sur-apprentissage (on choisit \(B\) là où l’erreur se stabilise et ne descend plus).

Paramètres (valeurs par défaut) :

  • Classement : \(q=\sqrt{p}\), taille nœud minimale 1 ;

  • Régression : \(q=p/3\), taille nœud minimale 5.

En pratique les valeurs « idéales » dépendent beaucoup de la base (et il faut les trouver par validation croisée).

image1
OOB vs erreur de test sur la base « Spambase ». On voit que le comportement de l’erreur OOB est similaire à celui de l’erreur de test.

L’importance des attributs :

Les attributs peuvent être évalués pour voir leur impact dans la construction de l’arbre (mesure de Gini) ou la robustesse aux erreurs de capteurs et/ou bruit sur la classification (erreur OOB) :

  • Gini : Le changement dans l’impureté (ou gain d’information) dans chaque nœud cumulé sur tous les arbres de la forêt.

  • Erreur OOB : tous les échantillons OOB sont évalués par l’arbre et l’erreur mesurée. Ensuite on permute aléatoirement les valeurs sur chaque attribut \(j\) et on mesure le taux d’erreur à nouveau. La valeur finale est la dégradation moyenne (changement du taux d’erreurs) sur tous les arbres.

image2
L’importance des attributs : Gini (gauche) vs erreur OOB (droite) sur « Spambase ».

Boosting

Le principe du boosting est de combiner les sorties de plusieurs classifieurs faibles (weak classifier) pour obtenir un résultat plus fort (strong classifier). Le classifieur faible doit avoir un comportement de base un peu meilleur que l’aléatoire : taux d’erreurs infénieur à 0.5 pour une classification binaire (c’est-à-dire qu’il ne se trompe pas plus d’une fois sur deux en moyenne, si la répartition des classes est équilibrée). Chaque classifieur faible est pondéré par la qualité de sa classification : mieux il classe, plus il sera important. Les exemples mal classés aurons un poids plus important (on dit qu’ils sont boostés) vis-à-vis de l’apprenant faible au prochain tour, afin qu’il pallie le manque.

Un des algorithmes les plus utilisés en boosting s’appelle AdaBoost, abréviation de adaptative boosting, proposé dans [FS97].

Algorithme AdaBoost

  • Données d’apprentissage : \((x_1, y_1), \dots, (x_n, y_n), x_i \in X, y_i \in \{-1, 1\}\).

  • Une famille \(\mathcal{G}\) de classifieurs faibles (appelés aussi parfois « règles faibles »).

image3

Au départ tous les exemples d’apprentissage ont un même poids (\(w_i=1/n\)). A chaque itération (supposons que \(m\) désigne le numéro de l’itération courante) on choisit dans \(\mathcal{G}\) le classifieur \(G_m\) qui minimise l’erreur de classement sur les données d’apprentissage pondérées par les \(w_i\). Ensuite on calcule \(\alpha_m\), la pondération de \(G_m\) dans le mélange final, on met à jour le poids \(w_i\) pour booster les éléments qui ont été mal classés et on passe à l’itération suivante. L’algorithme détaillé est donné ci-dessous.

image4

Boosting :

  • Étape 2(a) : \(g_m(x)\) est le classifieur qui minimise l’erreur pondérée sur la base d’apprentissage \(\operatorname*{arg\,min}_{g_m\in\mathcal{G}}\sum_{i=1}^n w_i \mathbf{1}_{y_i\neq g_m(x_i)}\).

  • L’erreur \(e_m\) doit être inférieure à 0.5, sinon \(\alpha_m\) devient négative.

  • L’algorithme minimise l’espérance de la fonction perte « naturelle » \(l(y, g(x))= \mathbf{1}_{y_i\neq g(x_i)}\).

image5 Comparaison entre Bagging, forêts aléatoires et Gradient Boosting sur la base « Spambase ».

Références : livres et articles

Bre96

Breiman et al. Bagging predictors, Machine Learning, 24(2), 1996.

Bre01(1,2)

Breiman et al. Random forests, Machine Learning, 45, 2001.

FS97

Freund et Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, vol. 55, no 1,‎ 1997, p. 119-139.

HTF06

Hastie, Tibshirani, Friedman, The elements of statistical learning : data mining, inference, and prediction, New York, Springer Verlag, 2006.

Rou

Rouvière, L., Introduction aux méthodes d’agrégation : boosting, bagging et forêts aléatoires, polycopié cours, https://perso.univ-rennes2.fr/laurent.rouvier).