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.
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
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.
\[ 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
, fonctionrandomForest
package
party
, fonctioncforest
Rborist
Autres:
http://www.r-bloggers.com/benchmarking-random-forest-implementations/