Bootstrap aggregating

Le bootstrap aggregating, également appelé bagging (de bootstrap aggregating), est un meta-algorithme d'apprentissage ensembliste conçu pour améliorer la stabilité et la précision des algorithmes d'apprentissage automatique. Il réduit la variance et permet d'éviter le surapprentissage. Bien qu'il soit généralement appliqué aux méthodes d'arbres de décision, il peut être utilisé avec n'importe quel type de méthode. Le bootstrap aggregating est un cas particulier de l'approche d'apprentissage ensembliste.

Description de la technique

Une illustration du concept de bootstrap aggregating

Étant donné un ensemble d'entraînement standard $D$ de taille $n$ , le bagging génère $m$ nouveaux ensembles d'entraînement $D_{i}$ , chacun de taille $n'\,$ , par échantillonnage uniforme et avec remise à partir de $D$ . En échantillonnant avec remplacement, certaines observations peuvent être répétées dans chaque $D_{i}$ . Si $n'\,=n$ , alors pour $n$ grand, l'ensemble $D_{i}$ tend à avoir la fraction $1-1/e$ (≈63,2%) d'exemples uniques de $D$ , le reste étant des doublons. [1] Ce type d'échantillon est appelé échantillon de bootstrap. Ensuite, $m$ modèles sont entraînés à l'aide des $m$ échantillons de bootstrap. Pour finir, la prédiction du meta-modèle est obtenue en faisant la moyenne de la sortie (pour la régression) ou par vote de majorité (pour la classification) des $m$ modèles.

Résultats et applications

Le bagging conduit à des «améliorations pour les procédures instables» (Breiman, 1996), qui incluent, par exemple, les réseaux de neurones artificiels, les arbres de décision et la sélection de sous-ensembles en régression linéaire (Breiman, 1994). Le bagging peut-être appliqué à la réduction de bruit au cours du pre-processing de données, avec une amélioration de l'apprentissage [2]^,[3] .

D'un autre côté, le bagging peut légèrement dégrader les performances de méthodes stables telles que les K-plus proches voisins (Breiman, 1996).

Exemple: données sur l'ozone

L'exemple suivant illustre les principes de base du principe de bagging, sur une analyse de la relation entre l'ozone et la température (données de Rousseeuw et Leroy (1986), analyse effectuée en R).

La relation entre la température et l'ozone dans cet ensemble de données est apparemment non linéaire. Pour décrire mathématiquement cette relation, des lisseurs LOESS (avec une bande passante de 0,5) sont utilisés. Au lieu de créer un seul lissage à partir de l'ensemble de données complet, 100 échantillons bootstrap des données ont été tirés. Chaque échantillon est différent de l'ensemble de données d'origine, mais lui ressemble en termes de distribution et de variabilité. Un lisseur LOESS est ajusté pour chaque échantillon de bootstrap. Des prédictions à partir de ces 100 lisseurs ont ensuite été faites sur l'ensemble des données. Les 10 premiers ajustements lisses prévus apparaissent sous forme de lignes grises dans la figure ci-dessous. On remarque que les lignes grises sont saccadées et sur-apprennent les données.

En prenant la moyenne de 100 lissages, chacun ajusté à un sous-ensemble de l'ensemble de données d'origine, on obtient un meta-estimateur (ligne rouge). Cet estimateur est plus stable et il y a moins de surapprentissage .

Histoire

Le bagging (bootstrap aggregating) a été proposé par Leo Breiman en 1994 [4] pour améliorer la classification en combinant des classifications d'ensembles d'entraînement générés aléatoirement.

Articles connexes

Boosting (méta-algorithme)
Bootstrapping (statistiques)
Validation croisée (statistiques)
Forêt aléatoire
Random subspace method (attribute bagging)

Notes et références

Aslam, Javed A.; Popa, Raluca A.; and Rivest, Ronald L. (2007); On Estimating the Size and Confidence of a Statistical Audit, Proceedings of the Electronic Voting Technology Workshop (EVT '07), Boston, MA, 6 Août 2007. Plus généralement, pour un tirage avec remplacement de $n'\,$ valeurs parmi $n$ , le nombre de tirages uniques attendu est $n(1-e^{-n'/n})$ .
Sahu, A., Runger, G., Apley, D., Image denoising with a multi-phase kernel principal component approach and an ensemble version, IEEE Applied Imagery Pattern Recognition Workshop, pp.1-7, 2011.
Shinde, Amit, Anshuman Sahu, Daniel Apley, and George Runger. "Preimages for Variation Patterns from Kernel PCA and Bagging." IIE Transactions, Vol.46, Iss.5, 2014
Breiman, « Bagging Predictors », Department of Statistics, University of California Berkeley, vol. Technical Report No. 421,‎ septembre 1994 (lire en ligne, consulté le 28 juillet 2019)

Voir aussi

(en) Leo Breiman, « Bagging predictors », Machine Learning, vol. 24, n^o 2,‎ 1996, p. 123–140 (DOI 10.1007/BF00058655).
(en) Sotiris Kotsiantis, « Bagging and boosting variants for handling classifications problems: a survey », Knowledge Eng. Review, vol. 29, n^o 1,‎ 2014, p. 78–100 (DOI 10.1017/S0269888913000313).

Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] Aslam, Javed A.; Popa, Raluca A.; and Rivest, Ronald L. (2007); On Estimating the Size and Confidence of a Statistical Audit, Proceedings of the Electronic Voting Technology Workshop (EVT '07), Boston, MA, 6 Août 2007. Plus généralement, pour un tirage avec remplacement de $n'\,$ valeurs parmi $n$ , le nombre de tirages uniques attendu est $n(1-e^{-n'/n})$ .

[2] Sahu, A., Runger, G., Apley, D., Image denoising with a multi-phase kernel principal component approach and an ensemble version, IEEE Applied Imagery Pattern Recognition Workshop, pp.1-7, 2011.

[3] Shinde, Amit, Anshuman Sahu, Daniel Apley, and George Runger. "Preimages for Variation Patterns from Kernel PCA and Bagging." IIE Transactions, Vol.46, Iss.5, 2014

[4] Breiman, « Bagging Predictors », Department of Statistics, University of California Berkeley, vol. Technical Report No. 421,‎ septembre 1994 (lire en ligne, consulté le 28 juillet 2019)