Bagging

Introduit par

  • deux ingredients clefs : bootstrap et aggregation

  • l’agregation de methode de prevision initiales independantes (base learners) mene à une reduction importante de l’erreur de prevision.

  • il faut donc oeuvrer dans le but d’obtenir des methodes initiales aussi independantes que possible.

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

  • Probleme : le nombre d’observations de l’ensemble d’entrainement n’est pas infini ! les “base learners” auront trop peu de donnees et de mauvaises performances.

Intuition

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

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

Le risque quadratique associe e chaque predicteur est: \[E_{\mathcal{L}} E_{X,Y} (Y-\phi(x,\mathcal{L})^2\]

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

Par l’inegalite 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 predicteur baggé est donc inferieur e celui des predicteurs individuels. De combien depend de l’inegalite:

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

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

Bagging

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

Pour creer un nouveau “base learner”:

  • on tire aleatoirement avec remise n observations de l’ensemble d’entrainement.
  • on entraine notre methode (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 forets aleatoires

Methode introduite par Leo Breiman en 2001, succède et unifie des idees plus anciennes : Bagging (1996), arbres de decisions CART (1984)

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

Les forets aleatoires

Les forets aleatoires consistent à faire tourner en parallele un grand nombre (plusieurs centaines) d’arbres de decisions construits aleatoirement, avant de les moyenner.

En termes statistiques, si les arbres sont decorreles, cela permet de reduire la variance des previsions.

 

 

Drawing

Les forets aleatoires: intuition

si \(K\) arbres \(Y_i\) sont identiquement distribues, de variance \(\sigma^2\), avec un coefficient de correlation deux e 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 forets aleatoires: 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')
abline(h=sigma^2)

Construire des arbres peu correles

  • Bootstrapping: Plutôt qu’utiliser toutes les donnees pour construire les arbres, on choisit pour chaque arbre aleatoirement un sous-ensemble (avec repetition possibles) des donnees.

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

 

Drawing

Construire des arbres peu correles

\(q\) : parametre contrelant l’aleatoire

Pour couper un noeud :

  • on choisit aleatoirement 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 critere de variabilite (cf CART: Variance, Entropie, Gini) parmis ce sous-emsemble.
  • si q = p : pas d’aleatoire. On retrouve le choix deterministe de CART
  • si q = 1 : aleatoire total dans le choix de la variable (mais pas dans le seuil de la coupe).

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

Notion de proximite

Intuition : Tomber souvent dans les meme 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{meme feuille de l'arbre } k) \]

On predit ensuite \(Y_t\) par:

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

Importance des variables

Les forets aleatoires permettent de classer les variables explicatives par ordre d’importance dans la prevision.

Tout d’abord, on construit la foret aleatoire, on calcule l’erreur E “out-of-bag” de la foret

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

  • on permute aleatoirement 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 difference avec E.
  • on renormalise les scores.

Avantages et inconvenients des random-forests

Avantages

  • pas de sur-apprentissage
  • en general : meilleure performance que les arbres de decision, calcul de l’erreur “Out-of-Bag” direct
  • effet 2 en 1: validation croisee non necessaire gràce aux echantillons oob
  • parametres faciles à calibrer
  • parallelisation possible
  • souvent utilisees comme benchmark dans les competition de machine learning

Inconvenients

  • boite noire : difficilement interpretable, difficilement ameliorable
  • entrainement plus lent

 

 

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

Implementations

en R:

  • package randomForest, fonction randomForest

  • package party, fonction cforest

  • Rborist

Autres:

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