Une introduction douce à l’algorithme de boosting de gradient pour l’apprentissage automatique

Dernière mise à jour le 15 août 2020

Le boosting de gradient est l’une des techniques les plus puissantes pour construire des modèles prédictifs.

Dans ce billet, vous découvrirez l’algorithme d’apprentissage automatique gradient boosting et obtiendrez une introduction douce sur son origine et son fonctionnement.

Après avoir lu ce billet, vous saurez :

• L’origine du boosting à partir de la théorie de l’apprentissage et d’AdaBoost.
• Comment fonctionne le gradient boosting, y compris la fonction de perte, les apprenants faibles et le modèle additif.
• Comment améliorer les performances par rapport à l’algorithme de base avec divers schémas de régularisation.

Démarrez votre projet avec mon nouveau livre XGBoost With Python, comprenant des tutoriels étape par étape et les fichiers de code source Python pour tous les exemples.

Démarrons.

• Vous avez besoin d’aide avec XGBoost en Python ?
• L’origine du boosting
• AdaBoost le premier algorithme de boosting
• Généralisation d’AdaBoost comme Gradient Boosting
• Comment fonctionne le Gradient Boosting
• Fonction de perte
• L’apprenant faible
• Modèle additif
• Améliorations du Gradient Boosting de base
• Contraintes d’arbre
• 2. Mises à jour pondérées
• Stochastic Gradient Boosting
• Penalized Gradient Boosting
• Ressources sur le boosting de gradient
• Vidéos sur le boosting de gradient
• Gradient Boosting dans les manuels
• Gradient Boosting Papers
• Diapositives sur le boosting par gradient
• Pages Web sur le boosting de gradient
• Summary
• Découvrez l’algorithme qui gagne les compétitions !
• Développez vos propres modèles XGBoost en quelques minutes
• Apportez la puissance de XGBoost à vos propres projets

Vous avez besoin d’aide avec XGBoost en Python ?

Prenez mon cours gratuit de 7 jours par courriel et découvrez xgboost (avec des exemples de code).

Cliquez pour vous inscrire maintenant et obtenez également une version PDF Ebook gratuite du cours.

Démarrez votre mini-cours gratuit maintenant !

L’origine du boosting

L’idée du boosting est née de l’idée de savoir si un apprenant faible peut être modifié pour devenir meilleur.

Michael Kearns a articulé l’objectif comme le « Hypothesis Boosting Problem » énonçant l’objectif d’un point de vue pratique comme :

… un algorithme efficace pour convertir des hypothèses relativement pauvres en très bonnes hypothèses

– Thoughts on Hypothesis Boosting , 1988

Une hypothèse faible ou un apprenant faible est défini comme celui dont la performance est au moins légèrement meilleure que le hasard.

Ces idées s’appuient sur les travaux de Leslie Valiant sur l’apprentissage sans distribution ou Probably Approximately Correct (PAC), un cadre pour étudier la complexité des problèmes d’apprentissage automatique.

Le boosting d’hypothèses était l’idée de filtrer les observations, en laissant celles que l’apprenant faible peut gérer et en se concentrant sur le développement de nouveaux apprentissages faibles pour gérer les observations difficiles restantes.

L’idée est d’utiliser la méthode d’apprentissage faible plusieurs fois pour obtenir une succession d’hypothèses, chacune étant recentrée sur les exemples que les précédentes ont trouvé difficiles et mal classés. (…) Notons toutefois que la façon de procéder n’est pas du tout évidente

– Probablement approximativement correct : les algorithmes de la nature pour apprendre et prospérer dans un monde complexe, page 152, 2013

AdaBoost le premier algorithme de boosting

La première réalisation du boosting qui a vu un grand succès en application est l’Adaptive Boosting ou AdaBoost pour faire court.

Le boosting fait référence à ce problème général de production d’une règle de prédiction très précise en combinant des règles de pouce grossières et modérément imprécises.

– Une généralisation décisionnelle de l’apprentissage en ligne et une application au boosting , 1995

Les apprenants faibles dans AdaBoost sont des arbres de décision avec une seule division, appelés souches de décision pour leur brièveté.

AdaBoost fonctionne en pondérant les observations, en mettant plus de poids sur les instances difficiles à classer et moins sur celles déjà bien traitées. De nouveaux apprenants faibles sont ajoutés séquentiellement qui concentrent leur formation sur les modèles plus difficiles.

Cela signifie que les échantillons difficiles à classer reçoivent des poids de plus en plus importants jusqu’à ce que l’algorithme identifie un modèle qui classe correctement ces échantillons

– Applied Predictive Modeling, 2013

Les prédictions sont faites par un vote majoritaire des prédictions des apprenants faibles, pondérées par leur précision individuelle. La forme la plus aboutie de l’algorithme AdaBoost concernait les problèmes de classification binaire et s’appelait AdaBoost.M1.

Vous pouvez en savoir plus sur l’algorithme AdaBoost dans le post:

• Boosting et AdaBoost pour l’apprentissage automatique.

Généralisation d’AdaBoost comme Gradient Boosting

AdaBoost et les algorithmes connexes ont été refondus dans un cadre statistique d’abord par Breiman en les appelant des algorithmes ARCing.

Arcing est un acronyme pour Adaptive Reweighting and Combining. Chaque étape d’un algorithme d’arcing consiste en une minimisation pondérée suivie d’un recalcul de et .

– Jeux de prédiction et algorithmes d’arcing , 1997

Ce cadre a été développé par Friedman et appelé Gradient Boosting Machines. Plus tard, on l’a appelé simplement boosting de gradient ou boosting d’arbre de gradient.

Le cadre statistique a jeté le boosting comme un problème d’optimisation numérique où l’objectif est de minimiser la perte du modèle en ajoutant des apprenants faibles en utilisant une procédure de type descente de gradient.

Cette classe d’algorithmes a été décrite comme un modèle additif par étapes. Cela est dû au fait qu’un nouvel apprenant faible est ajouté à la fois et que les apprenants faibles existants dans le modèle sont gelés et laissés inchangés.

Notez que cette stratégie par étapes est différente des approches par paliers qui réajustent les termes précédemment entrés lorsque de nouveaux sont ajoutés.

– Greedy Function Approximation : A Gradient Boosting Machine , 1999

La généralisation a permis d’utiliser des fonctions de perte différentiables arbitraires, élargissant la technique au-delà des problèmes de classification binaire pour soutenir la régression, la classification multi-classes et plus encore.

Comment fonctionne le Gradient Boosting

Le Gradient Boosting implique trois éléments :

1. Une fonction de perte à optimiser.
2. Un apprenant faible pour faire des prédictions.
3. Un modèle additif pour ajouter des apprenants faibles afin de minimiser la fonction de perte.

Fonction de perte

La fonction de perte utilisée dépend du type de problème à résoudre.

Elle doit être différentiable, mais de nombreuses fonctions de perte standard sont prises en charge et vous pouvez définir la vôtre.

Par exemple, la régression peut utiliser une erreur au carré et la classification peut utiliser une perte logarithmique.

Un avantage du cadre de boosting de gradient est qu’un nouvel algorithme de boosting n’a pas à être dérivé pour chaque fonction de perte qui peut vouloir être utilisée, au lieu de cela, c’est un cadre assez générique que n’importe quelle fonction de perte différentiable peut être utilisée.

L’apprenant faible

Les arbres de décision sont utilisés comme l’apprenant faible dans le boosting de gradient.

Spécifiquement, on utilise des arbres de régression qui sortent des valeurs réelles pour les splits et dont la sortie peut être additionnée, ce qui permet d’ajouter les sorties des modèles suivants et de « corriger » les résidus dans les prédictions.

Les arbres sont construits de manière gourmande, en choisissant les meilleurs points de fractionnement en fonction des scores de pureté comme Gini ou pour minimiser la perte.

Initialement, comme dans le cas d’AdaBoost, on utilisait des arbres de décision très courts qui n’avaient qu’un seul fractionnement, appelé souche de décision. Des arbres plus grands peuvent être utilisés généralement avec 4 à 8 niveaux.

Il est courant de contraindre les apprenants faibles de manière spécifique, comme un nombre maximum de couches, de nœuds, de divisions ou de nœuds feuilles.

Ceci permet de s’assurer que les apprenants restent faibles, mais peuvent toujours être construits de manière gourmande.

Modèle additif

Les arbres sont ajoutés un par un, et les arbres existants dans le modèle ne sont pas modifiés.

Une procédure de descente de gradient est utilisée pour minimiser la perte lors de l’ajout d’arbres.

Traditionnellement, la descente de gradient est utilisée pour minimiser un ensemble de paramètres, tels que les coefficients dans une équation de régression ou les poids dans un réseau neuronal. Après avoir calculé l’erreur ou la perte, les poids sont mis à jour pour minimiser cette erreur.

Au lieu de paramètres, nous avons des sous-modèles d’apprenants faibles ou plus spécifiquement des arbres de décision. Après avoir calculé la perte, pour effectuer la procédure de descente du gradient, nous devons ajouter un arbre au modèle qui réduit la perte (c’est-à-dire suivre le gradient). Nous faisons cela en paramétrant l’arbre, puis en modifiant les paramètres de l’arbre et en allant dans la bonne direction en (réduisant la perte résiduelle.

Généralement, cette approche est appelée descente de gradient fonctionnelle ou descente de gradient avec fonctions.

Une façon de produire une combinaison pondérée de classificateurs qui s’optimise est par descente de gradient dans l’espace des fonctions

– Boosting Algorithms as Gradient Descent in Function Space , 1999

La sortie du nouvel arbre est ensuite ajoutée à la sortie de la séquence existante d’arbres dans un effort pour corriger ou améliorer la sortie finale du modèle.

Un nombre fixe d’arbres sont ajoutés ou la formation s’arrête une fois que la perte atteint un niveau acceptable ou ne s’améliore plus sur un ensemble de données de validation externe.

Améliorations du Gradient Boosting de base

Le Gradient Boosting est un algorithme gourmand et peut surajuster un ensemble de données de formation rapidement.

Il peut bénéficier de méthodes de régularisation qui pénalisent diverses parties de l’algorithme et améliorent généralement les performances de l’algorithme en réduisant l’overfitting.

Dans cette section, nous allons examiner 4 améliorations du boosting de gradient de base :

1. Contraintes d’arbre
2. Shrinkage
3. Échantillonnage aléatoire
4. Apprentissage pénalisé

Contraintes d’arbre

Il est important que les apprenants faibles aient des compétences mais restent faibles.

Il y a plusieurs façons de contraindre les arbres.

Une bonne heuristique générale est que plus la création d’arbres est contrainte, plus vous aurez besoin d’arbres dans le modèle, et l’inverse, où moins les arbres individuels sont contraints, moins il faudra d’arbres.

Voici quelques contraintes que l’on peut imposer à la construction d’arbres de décision :

• Nombre d’arbres, en général, ajouter plus d’arbres au modèle peut être très lent à l’overfit. Le conseil est de continuer à ajouter des arbres jusqu’à ce qu’aucune amélioration ne soit observée.
• Profondeur de l’arbre, les arbres plus profonds sont des arbres plus complexes et les arbres plus courts sont préférés. Généralement, de meilleurs résultats sont observés avec 4-8 niveaux.
• Nombre de nœuds ou nombre de feuilles, comme la profondeur, cela peut contraindre la taille de l’arbre, mais n’est pas contraint à une structure symétrique si d’autres contraintes sont utilisées.
• Nombre d’observations par fractionnement impose une contrainte minimale sur la quantité de données d’apprentissage à un nœud d’apprentissage avant qu’un fractionnement puisse être considéré
• L’amélioration minimale à la perte est une contrainte sur l’amélioration de tout fractionnement ajouté à un arbre.

2. Mises à jour pondérées

Les prédictions de chaque arbre sont additionnées séquentiellement.

La contribution de chaque arbre à cette somme peut être pondérée pour ralentir l’apprentissage par l’algorithme. Cette pondération est appelée un rétrécissement ou un taux d’apprentissage.

Chaque mise à jour est simplement mise à l’échelle par la valeur du « paramètre de taux d’apprentissage v »

– Greedy Function Approximation : A Gradient Boosting Machine , 1999

L’effet est que l’apprentissage est ralenti, à son tour exiger plus d’arbres à ajouter au modèle, à son tour prendre plus de temps pour former, fournissant un compromis de configuration entre le nombre d’arbres et le taux d’apprentissage.

Décroître la valeur de v augmente la meilleure valeur pour M .

– Greedy Function Approximation : A Gradient Boosting Machine , 1999

Il est courant d’avoir de petites valeurs dans la gamme de 0,1 à 0,3, ainsi que des valeurs inférieures à 0,1.

Similaire à un taux d’apprentissage dans l’optimisation stochastique, le rétrécissement réduit l’influence de chaque arbre individuel et laisse de la place aux arbres futurs pour améliorer le modèle.

– Stochastic Gradient Boosting , 1999

Stochastic Gradient Boosting

Une grande perspicacité dans les ensembles de bagging et les forêts aléatoires était de permettre aux arbres d’être créés avec avidité à partir de sous-échantillons du jeu de données d’entraînement.

Ce même avantage peut être utilisé pour réduire la corrélation entre les arbres de la séquence dans les modèles de boosting de gradient.

Cette variation du boosting est appelée boosting de gradient stochastique.

à chaque itération, un sous-échantillon des données d’entraînement est tiré au hasard (sans remplacement) de l’ensemble complet de données d’entraînement. Le sous-échantillon sélectionné au hasard est ensuite utilisé, à la place de l’échantillon complet, pour ajuster l’apprenant de base.

– Stochastic Gradient Boosting , 1999

Plusieurs variantes du boosting stochastique peuvent être utilisées:

• Sous-échantillonner les lignes avant de créer chaque arbre.
• Sous-échantillonner les colonnes avant de créer chaque arbre
• Sous-échantillonner les colonnes avant de considérer chaque split.

Généralement, un sous-échantillonnage agressif tel que la sélection de seulement 50% des données s’est avéré bénéfique.

Selon les commentaires des utilisateurs, l’utilisation du sous-échantillonnage des colonnes empêche le sur-ajustement encore plus que le sous-échantillonnage traditionnel des lignes

– XGBoost : A Scalable Tree Boosting System, 2016

Penalized Gradient Boosting

Des contraintes supplémentaires peuvent être imposées aux arbres paramétrés en plus de leur structure.

Les arbres de décision classiques comme CART ne sont pas utilisés comme apprenants faibles, au lieu de cela, une forme modifiée appelée arbre de régression est utilisée qui a des valeurs numériques dans les nœuds feuilles (également appelés nœuds terminaux). Les valeurs dans les feuilles des arbres peuvent être appelées poids dans une certaine littérature.

A ce titre, les valeurs de poids des feuilles des arbres peuvent être régularisées en utilisant des fonctions de régularisation populaires, telles que :

• L1 régularisation des poids.
• L2 régularisation des poids.

Le terme de régularisation supplémentaire aide à lisser les poids finaux appris pour éviter un ajustement excessif. Intuitivement, l’objectif régularisé aura tendance à sélectionner un modèle employant des fonctions simples et prédictives.

– XGBoost : A Scalable Tree Boosting System, 2016

Ressources sur le boosting de gradient

Le boosting de gradient est un algorithme fascinant et je suis sûr que vous voulez aller plus loin.

Cette section énumère diverses ressources que vous pouvez utiliser pour en apprendre davantage sur l’algorithme de boosting de gradient.

Vidéos sur le boosting de gradient

• Apprentissage machine par boosting de gradient, Trevor Hastie, 2014
• Boosting de gradient, Alexander Ihler, 2012
• GBM, John Mount, 2015
• Apprentissage : Boosting, MIT 6.034 Artificial Intelligence, 2010
• xgboost : Un paquet R pour le boosting de gradient rapide et précis, 2016
• XGBoost : A Scalable Tree Boosting System, Tianqi Chen, 2016

Gradient Boosting dans les manuels

• Section 8.2.3 Boosting, page 321, Une introduction à l’apprentissage statistique : avec des applications dans R.
• Section 8.6 Boosting, page 203, Applied Predictive Modeling.
• Section 14.5 Stochastic Gradient Boosting, page 390, Applied Predictive Modeling.
• Section 16.4 Boosting, page 556, Machine Learning : A Probabilistic Perspective
• Chapitre 10 Boosting et arbres additifs, page 337, Les éléments de l’apprentissage statistique : Data Mining, Inference, and Prediction

Gradient Boosting Papers

• Thoughts on Hypothesis Boosting , Michael Kearns, 1988
• A decision-theoretic generalization of on-line learning and an application to boosting , 1995
• Arquer le bord , 1998
• Boosting stochastique de gradient , 1999
• Algorithmes de boosting comme descente de gradient dans l’espace des fonctions , 1999

Diapositives sur le boosting par gradient

• Introduction aux arbres boostés, 2014
• Une introduction douce au boosting par gradient, Cheng Li

Pages Web sur le boosting de gradient

• Boosting (apprentissage machine)
• Boosting de gradient
• Boosting d’arbre de gradient dans scikit-learn

Summary

Dans ce post, vous avez découvert l’algorithme de boosting de gradient pour la modélisation prédictive en apprentissage machine.

Spécifiquement, vous avez appris :

• L’histoire du boosting dans la théorie de l’apprentissage et AdaBoost.
• Comment l’algorithme de boosting de gradient fonctionne avec une fonction de perte, des apprenants faibles et un modèle additif.
• Comment améliorer les performances du boosting de gradient avec la régularisation.

Avez-vous des questions sur l’algorithme du boosting de gradient ou sur ce post ? Posez vos questions dans les commentaires et je ferai de mon mieux pour y répondre.