Bagging

Introduit par Breiman (1996)

  • deux ingrédients clefs : bootstrap et aggregation

  • l’agrégation de méthode de prévision initiales indépendantes (base learners) mène à une réduction importante de l’erreur de prévision.

  • il faut donc oeuvrer dans le but d’obtenir des méthodes initiales aussi indépendantes que possible.

  • Idée naive : entrainer nos “base learners” (ex : CART) sur des sous-ensembles d’observations disjoints de l’ensemble d’entrainement.

  • Problème : le nombre d’observations de l’ensemble d’entrainement n’est pas infini ! les “base learners” auront trop peu de données et de mauvaises performances.

Intuition

Soit \((X,Y)\) de loi \(P\), un échantillon \(\mathcal{L}=(x_i,y_i)_{1\leq i \leq n}\) et un prédicteur individuel \(\widehat{y}=\phi(x,\mathcal{L})\).

Le prédicteur baggé associé est, en supposant qu’on effectue un grand nombre de tirage aléatoire: \[\phi_a (x,P)=E_{\mathcal{L}} (\phi(x,\mathcal{L}))\]

Le risque quadratique associé à chaque prédicteur est: \[E_{\mathcal{L}} E_{X,Y} (Y-\phi(x,\mathcal{L}))^2\]

Le risque quadratique associé prédicteur baggé est \[ E_{X,Y} (Y-\phi_a (x,P))^2 \]

Par l’inégalité de Jensen \([E(Z)]^2 \leq E(Z^2)\):

\[ E_{X,Y} (Y-\phi_a (x,P))^2 \leq E_{\mathcal{L}} E_{X,Y} (Y-\phi(x,\mathcal{L}))^2 \]

Le risque du prédicteur baggé est donc inférieur à celui des prédicteurs individuels. De combien dépend de l’inégalité:

\[ E_{\mathcal{L}}(\phi(x,\mathcal{L})^2)-[E_{\mathcal{L}}(\phi(x,\mathcal{L}))]^2 \geq 0 \]

d’autant plus vrai que les prédicteurs individuels sont instables (forte variance en fonction de \(\mathcal{L}\)).

Bagging

Le bagging crée des sous-ensembles d’entrainement à l’aide d’échantillonnage bootstrap [Elfron et Tibshirani, 1993].

Pour créer un nouveau “base learner”:

  • on tire aléatoirement avec remise n observations de l’ensemble d’entrainement.
  • on entraine notre méthode (ex : CART) sur cet ensemble d’observations
    • chaque base learner contient un sous ensemble des observations de l’ensemble d’entrainement.
    • la performance d’un “base learner” est obtenu par l’erreur out-of-bag.

Les forêts aléatoires

Méthode introduite par Leo Breiman en 2001, succède et unifie des idées plus anciennes : Bagging (1996), arbres de décisions CART (1984)

Preuves de convergences récentes (2006,2008), un site web utile : http://www.stat.berkeley.edu/breiman/RandomForests

Les forêts aléatoires

Les forêts aléatoires consistent à faire tourner en parallèle un grand nombre (plusieurs centaines) d’arbres de décisions construits aléatoirement, avant de les moyenner.

En termes statistiques, si les arbres sont décorrélés, cela permet de réduire la variance des prévisions.

 

 

Drawing

Les forêts aléatoires: intuition

si \(K\) arbres \(Y_i\) sont identiquement distribués, de variance \(\sigma^2\), avec un coefficient de corrélation deux à deux \(\rho\) la variance de leur moyenne \(\frac{1}{K} \sum_{i=1}^K Y_i\) est alors:

\[ \bar{\sigma}= \frac{1}{K^2} (K\sigma^2 +K(K-1) \rho \sigma^2) \]

\[ \bar{\sigma}= \rho \sigma^2 + \frac{\sigma^2 }{K}(1-\rho) \]

Les forêts aléatoires: intuition

sigma<-10
rho<-seq(0,1,length=100)
K<-1+100*rho^2
sigbar2<-rho*sigma^2+sigma^2*(1-rho)/K
plot(rho,sigbar2,type='b',pch=20,col='purple', ylim=c(20, 250))
abline(h=sigma^2, col='purple')

sigma<-15
sigbar2<-rho*sigma^2+sigma^2*(1-rho)/K
lines(rho,sigbar2,type='b',pch=20,col='red')
abline(h=sigma^2, col='red')

Construire des arbres peu corrélés

  • Bootstrapping: Plutôt qu’utiliser toutes les données pour construire les arbres. On choisit pour chaque arbre aléatoirement un sous-ensemble (avec répétition possibles) des données.

  • Choix aléatoire de la variable explicative à couper. Contrairement à CART pas d’élagage

 

Drawing

Construire des arbres peu corrélés

\(q\) : paramètre contrôlant l’aléatoire

Pour couper un noeud :

  • on choisit aléatoirement un sous-ensemble de \(q\) variables explicatives potentielles parmi les p disponibles
  • on choisit la variable à couper et le seuil de coupe en minimisant le critère de variabilité (cf CART: Variance, Entropie, Gini) parmis ce sous-emsemble.
  • si q = p : pas d’aléatoire. On retrouve le choix déterministe de CART
  • si q = 1 : aléatoire total dans le choix de la variable (mais pas dans le seuil de la coupe).

En pratique, Breiman (2001) propose \(q=log(p)\)

Notion de proximité

Intuition : Tomber souvent dans les même feuilles des arbres signifie expliquer la sortie Y de façon similaire.

Drawing

\[ prox(X_t,X_s)=\frac{1}{K} \sum_{k=1}^K 1(X_t, X_s \in \text{même feuille de l'arbre } k) \]

On prédit ensuite \(Y_t\) par:

\[ \frac{1}{C}\sum_{i=1}^n prox(X_t,X_i) Y_i \]

Importance des variables

Les forêts aléatoires permettent de classer les variables explicatives par ordre d’importance dans la prévision.

Tout d’abord, on construit la forêt aléatoire, on calcule l’erreur E “out-of-bag” de la forêt

Le score d’une variable explicative \(X_i\) est calculé comme suit:

  • on permute aléatoirement les valeurs de la variable explicative parmi les observations de l’ensemble d’entrainement
  • on calcule à nouveau l’erreur out-of-bag et on fait la différence avec E.
  • on renormalise les scores.

Avantages et inconvénients des random-forests

Avantages

  • pas de sur-apprentissage
  • en général : meilleure performance que les arbres de décision, calcul de l’erreur “Out-of-Bag” direct
  • effet 2 en 1: validation croisée non nécessaire grâce aux échantillons oob
  • paramètres faciles à calibrer
  • parallélisation possible
  • souvent utilisées comme benchmark dans les compétition de machine learning

Inconvénients

  • boite noire : difficilement interprétable, difficilement améliorable
  • entrainement plus lent

 

 

les random forest fonctionne tout le temps bien mais excellent plus rarement

Implémentations

en R:

  • package randomForest, fonction randomForest

  • package party, fonction cforest

  • Rborist

  • Ranger: temps de calcul optimisé

-xgboost: certaines paramétrisation donnent des forêts

Autres:

http://www.r-bloggers.com/benchmarking-random-forest-implementations/