Bagging et boostrap
Nous avons donc plusieurs prédictions (pour chacun de nos arbres) et allons choisir une prédiction finale en prenant la moyenne des prédiction ou la prédiction la plus commune.
Cette méthode, s'appelle le bagging ou bootstrap aggregating. Rappelons que si l'on s’entraîne sur un groupe de données, nous avons un risque de variance (surentraînement) en se spécialisant sur ces données. avec le bagging, on va utiliser un grand nombre d'ensemble de données différente, on réduit donc le risque de variance puisque l'on utilise non plus un seul mais plusieurs jeux de données.
Bootstraping
 |
| Le baron de Münchhausen |
Le bagging utilise une méthode particulière pour choisir les ensembles de données sur lesquels nous allons nous entraîner appelée bootstrap.
Un boostrap correspond à une variation avec remplacement d'un échantillon original. "Avec remplacement" signifie que lorsque l'on créé une variation de notre échantillon, on s'autorise à réutiliser plusieurs fois le même élément.
Imaginons que notre échantillon original soit la suite de chiffres :
2 3 7 5 1
Il suffit pour créer un boostrap de remplacer un ou plusieurs chiffre de l'échantillon original, par un des chiffres de l'échantilon original, par exemple :
2 2 7 5 1
ou
2 3 3 3 3
ou
5 3 7 5 2
Maintenant que nous savons créer des boostraps, nous allons pouvoir non pas étudier ces boostraps, mais nous aider de ceux-ci pour étudier l'échantillon original.
Car lorsque nous utilisons un nombre suffisant de boostraps, alors il va y avoir une convergence entre leur caractéristiques statistiques et notre échantillon original.
Le baron de Münchhausen avait réussi à se dépêtrer d'un marécage en tirant sur ces lacets (boostrap en anglais : anneau en cuir pour enfiler ses lacets). Ce qui est bien entendu impossible mais le boostrap nous permet de réaliser l'impossible : améliorer nos calculs en utilisant les mêmes données (et non pas de nouvelles données) : on simule de nouveaux échantillon en utilisant seulement notre échantillon original
Pourquoi ca marche ?
L'inventeur du Bagging, Leo Breiman, l'explique mathématiquement dans son article original. Concrètement, plus nos prédicteurs sont instables, plus le bagging fonctionne. Un algorithme d'apprentissage est considéré comme instable si une petite variation dans nos données peut donner des résultats grandement différents. Et c'est le cas de nos arbres !
Le preuve mathématique de l'intuition sur la variance est assez 'courte' mais non nécessaire à comprendre pour la suite. Vous la trouverez plus bas ou vous pouvez directement passer à la prochaine partie.
Preuve de la baisse de la variance
Un arbre prédit un résultat p (par exemple le type d'iris) en fonction de variables x (par exemple, les tailles des pétales et sépales), c'est donc comparable à une fonction.
f(x) = p
Si notre arbre est parfait alors il prévoit toujours le bon résultat, qu'on va appeler y. Pour un arbre parfait, sa prévision p est toujours le bon résultat y
f(x) = p = y
y-f(x) = 0
Si il n'est pas parfait, il y a une erreur et le rapport y-f(x) est donc différent de 0. Pour éviter les nombres négatifs, on passe généralement le tout au carré :
Erreur au carré = [y-f(x)]2
Considérons maintenant nos différents échantillons boostrap comme un ensemble L, on prédit donc depuis des données x tirées de L. Un arbre est un prédicteur a ( on va utiliser a plutôt que f pour le nom de notre fonction)
Prédicteur arbre : a(x,L) (ou simplement a)
Erreur arbre : y-a(x,L)
Erreur arbre : y-a(x,L)
On considère alors notre forêt comme un 'super-prédicteur' F qui englobe tous les arbres et qui quand on va lui donner des données x de L va prévoir un p qui est la moyenne de la prévision de tous nos arbres. Cette moyenne des prévisions est appelée espérance E.
Prédicteur forêt : F =E(a(x,L)) (ou simplement E(a))
L'espérance, ou la moyenne, des erreurs au carré des arbres est :
Erreur de tous les arbres: E ( y - a(x,L))2
Si on développe :
E (y - a)2
E (y - a)2 = E(y2) - E(2*y*a) + E(a2) (en utilisant la formule (a-b) 2 = a 2-2ab +b 2)
E (y - a)2 = y2 - 2*y*E(a) + E(a2) ( 2 et y sont des constantes, on utilise la règle E(yX)=yE(X) "y Î R)
E (y - a)2 = y2 - 2*y*F + E(a2) (on réutilise notre définition F=E(a))
Maintenant, on utilise une règle qui dit que : E(a2 ) ≥ (Ea)2
E (y - a)2 ≥ y2 - 2*y*F + E(a)2
E (y - a)2 ≥ y2 - 2*y*F + F2
E (y - a)2 ≥ (y-F)2
On voit donc que l'erreur que produit notre forêt (y-F)2 est inférieure à l'erreur moyenne que produisent nos arbres.
Et cette infériorité dépend de la règle que l'on a posée :
E(a2 ) ≥ (Ea)2
Plus a(x,L) - l'algorithme de notre arbre qui dépend des échantillon L- est instable (donne des résultat différents selon les échantillon de L) plus son E(a2 ) va être grand par rapport (Ea)2
Et plus a est est stable plus E(a2 ) et (Ea)2 seront égaux !