Une introduction douce à l'algorithme d'augmentation de gradient pour l'apprentissage automatique
L'augmentation du gradient est l'une des techniques les plus puissantes pour créer des modèles prédictifs.
Dans cet article, vous découvrirez l'algorithme d'apprentissage automatique d'amélioration du gradient et obtiendrez une introduction douce à son origine et à son fonctionnement.
Après avoir lu cet article, vous saurez :
- L'origine du boosting à partir de la théorie de l'apprentissage et d'AdaBoost.
- Comment fonctionne l'augmentation du gradient, 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 pas à pas et les fichiers code source Python pour tous les exemples .
Commençons.
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 formulé l'objectif sous la forme du « Problème de renforcement des hypothèses » en énonçant l'objectif d'un point de vue pratique comme suit :
… un algorithme efficace pour convertir des hypothèses relativement mauvaises en très bonnes hypothèses
— Réflexions sur la stimulation des hypothèses [PDF], 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 probablement à peu près correct (PAC), un cadre permettant d'étudier la complexité des problèmes d'apprentissage automatique.
Le renforcement des hypothèses consistait en 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 plusieurs fois la méthode d’apprentissage faible pour obtenir une succession d’hypothèses, chacune recentrée sur les exemples que les précédentes trouvaient difficiles et mal classés. … Notez cependant que la manière dont cela peut être fait n'est pas du tout évidente
— Probablement à peu près 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 connu un grand succès dans son application a été l'Adaptive Boosting ou AdaBoost en abrégé.
Le boosting fait référence à ce problème général consistant à produire une règle de prédiction très précise en combinant des règles empiriques approximatives et modérément inexactes.
— Une généralisation de la théorie de la décision de l'apprentissage en ligne et une application au boosting [PDF], 1995
Les apprenants faibles dans AdaBoost sont des arbres de décision avec une seule division, appelés souches de décision en raison de leur brièveté.
AdaBoost fonctionne en pondérant les observations, en accordant plus de poids aux instances difficiles à classer et moins à celles déjà bien gérées. De nouveaux apprenants faibles sont ajoutés séquentiellement et concentrent leur formation sur les modèles les plus difficiles.
Cela signifie que les échantillons difficiles à classer reçoivent des poids de plus en plus élevés jusqu'à ce que l'algorithme identifie un modèle qui classe correctement ces échantillons.
— Modélisation prédictive appliquée, 2013
Les prédictions sont faites par vote majoritaire des prédictions des apprenants faibles, pondérées par leur précision individuelle. La forme la plus réussie de l'algorithme AdaBoost était destinée aux problèmes de classification binaire et s'appelait AdaBoost.M1.
Vous pouvez en savoir plus sur l'algorithme AdaBoost dans l'article :
- Boosting et AdaBoost pour le Machine Learning.
Généralisation d'AdaBoost comme Gradient Boosting
AdaBoost et les algorithmes associés ont d'abord été refondus dans un cadre statistique par Breiman les appelant algorithmes ARCing.
Arcing est un acronyme pour Adaptive Reweighting and Combining. Chaque étape d'un algorithme d'arc consiste en une minimisation pondérée suivie d'un recalcul des [classificateurs] et de [l'entrée pondérée].
— Jeux de prédiction et algorithmes d'arc [PDF], 1997
Ce cadre a été développé par Friedman et appelé Gradient Boosting Machines. Plus tard, appelé simplement amélioration du dégradé ou amélioration de l'arbre de dégradé.
Le cadre statistique présente le boosting comme un problème d'optimisation numérique dont l'objectif est de minimiser la perte du modèle en ajoutant des apprenants faibles à l'aide d'une procédure de type descente de gradient.
Cette classe d'algorithmes a été décrite comme un modèle additif par étapes. En effet, un nouvel apprenant faible est ajouté à la fois et 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 étapes qui réajustent les termes précédemment saisis lorsque de nouveaux sont ajoutés.
— Approximation de la fonction gourmande : une machine à booster de gradient [PDF], 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 prendre en charge la régression, la classification multi-classes et bien plus encore.
Comment fonctionne l'augmentation du dégradé
L’augmentation du dégradé implique trois éléments :
- Une fonction de perte à optimiser.
- Un apprenant faible pour faire des prédictions.
- Un modèle additif pour ajouter des apprenants faibles afin de minimiser la fonction de perte.
1. 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 quadratique et la classification peut utiliser une perte logarithmique.
L'un des avantages du cadre d'amplification de gradient est qu'il n'est pas nécessaire de dériver un nouvel algorithme d'amplification pour chaque fonction de perte susceptible d'être utilisée. Il s'agit plutôt d'un cadre suffisamment générique pour que n'importe quelle fonction de perte différentiable puisse être utilisée.
2. Apprenti faible
Les arbres de décision sont utilisés comme apprenant faible dans l'amélioration du gradient.
Plus précisément, des arbres de régression sont utilisés pour générer des valeurs réelles pour les divisions et dont les résultats peuvent être additionnés, ce qui permet d'ajouter les résultats des modèles ultérieurs et de « corriger » les résidus dans les prédictions.
Les arbres sont construits de manière gourmande, en choisissant les meilleurs points de partage en fonction de scores de pureté comme Gini ou pour minimiser la perte.
Au départ, comme dans le cas d'AdaBoost, on utilisait des arbres de décision très courts, ne comportant qu'une seule division, appelée souche de décision. Les arbres plus grands peuvent généralement être utilisés avec 4 à 8 niveaux.
Il est courant de contraindre les apprenants faibles de manière spécifique, comme par exemple un nombre maximum de couches, de nœuds, de divisions ou de nœuds feuilles.
Il s'agit de garantir que les apprenants restent faibles, mais peuvent toujours être construits de manière avide.
3. 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 d'une équation de régression ou les poids d'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 de 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 modifions les paramètres de l'arbre et avançons 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 optimise [le coût] consiste à effectuer une descente de gradient dans l'espace des fonctions.
— Stimuler les algorithmes en tant que descente de gradient dans l'espace fonctionnel [PDF], 1999
La sortie du nouvel arbre est ensuite ajoutée à la sortie de la séquence d'arbres existante dans le but de corriger ou d'améliorer la sortie finale du modèle.
Un nombre fixe d'arbres est ajouté ou la formation s'arrête une fois que la perte atteint un niveau acceptable ou ne s'améliore plus par rapport à un ensemble de données de validation externe.
Améliorations de l'amélioration de base du dégradé
L'augmentation du gradient est un algorithme gourmand et peut rapidement surajuster un ensemble de données d'entraînement.
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 le surajustement.
Dans cette section, nous examinerons 4 améliorations apportées à l'amélioration de base du dégradé :
- Contraintes d'arbre
- Rétrécissement
- Échantillonnage aléatoire
- Apprentissage pénalisé
1. Contraintes de l'arbre
Il est important que les apprenants faibles possèdent des compétences mais restent faibles.
Il existe 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 inversement, où moins d'arbres individuels sont contraints, moins d'arbres seront nécessaires.
Ci-dessous quelques contraintes qui peuvent être imposées à la construction d’arbres de décision :
- Nombre d'arbres. En général, l'ajout de plus d'arbres au modèle peut être très lent à surajuster. Le conseil est de continuer à ajouter des arbres jusqu’à ce qu’aucune amélioration supplémentaire ne soit observée.
- Profondeur des arbres, 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.
- Le Nombre de nœuds ou nombre de feuilles, comme la profondeur, peut contraindre la taille de l'arbre, mais n'est pas contraint à une structure symétrique si d'autres contraintes sont utilisées.
- Le Nombre d'observations par division impose une contrainte minimale sur la quantité de données d'entraînement au niveau d'un nœud d'entraînement avant qu'une division puisse être envisagée.
- L'Amélioration minimale de la perte est une contrainte sur l'amélioration de toute division ajoutée à 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 retrait ou taux d’apprentissage.
Chaque mise à jour est simplement mise à l'échelle par la valeur du « paramètre de taux d'apprentissage v »
— Approximation de la fonction gourmande : une machine à booster de gradient [PDF], 1999
L'effet est que l'apprentissage est ralenti, ce qui nécessite à son tour d'ajouter davantage d'arbres au modèle, ce qui prend à son tour plus de temps à former, offrant un compromis de configuration entre le nombre d'arbres et le taux d'apprentissage.
Diminuer la valeur de v [le taux d'apprentissage] augmente la meilleure valeur pour M [le nombre d'arbres].
— Approximation de la fonction gourmande : une machine à booster de gradient [PDF], 1999
Il est courant d'avoir de petites valeurs comprises entre 0,1 et 0,3, ainsi que des valeurs inférieures à 0,1.
Semblable au taux d'apprentissage dans l'optimisation stochastique, le retrait réduit l'influence de chaque arbre individuel et laisse de la place aux futurs arbres pour améliorer le modèle.
— Augmentation du gradient stochastique [PDF], 1999
3. Augmentation du gradient stochastique
Un grand aperçu des ensembles d'ensachage et des forêts aléatoires a permis de créer avidement des arbres à partir de sous-échantillons de l'ensemble 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 d'amplification de gradient.
Cette variation de boosting est appelée boosting à gradient stochastique.
à chaque itération, un sous-échantillon des données d'entraînement est tiré au hasard (sans remplacement) de l'ensemble de données d'entraînement complet. Le sous-échantillon sélectionné au hasard est ensuite utilisé, au lieu de l’échantillon complet, pour correspondre à l’apprenant de base.
— Augmentation du gradient stochastique [PDF], 1999
Quelques variantes de boosting stochastique pouvant être utilisées :
- Sous-échantillonnez les lignes avant de créer chaque arbre.
- Sous-échantillonner les colonnes avant de créer chaque arborescence
- Sous-échantillonnez les colonnes avant d’envisager chaque division.
En général, un sous-échantillonnage agressif, tel que la sélection de seulement 50 % des données, s'est révélé bénéfique.
Selon les commentaires des utilisateurs, l'utilisation du sous-échantillonnage en colonnes empêche encore plus le surajustement que le sous-échantillonnage en ligne traditionnel.
— XGBoost : un système de boosting d'arbre évolutif, 2016
4. Boosting de dégradé pénalisé
Des contraintes supplémentaires peuvent être imposées sur les arbres paramétrés en plus de leur structure.
Les arbres de décision classiques comme CART ne sont pas utilisés en tant qu'apprenants faibles, mais 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 contenues dans les feuilles des arbres peuvent être appelées poids dans certains ouvrages.
Ainsi, les valeurs du poids des feuilles des arbres peuvent être régularisées à l'aide de fonctions de régularisation populaires, telles que :
- Régularisation L1 des poids.
- Régularisation L2 des poids.
Le terme de régularisation supplémentaire permet de 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 : un système de boosting d'arbre évolutif, 2016
Ressources d'amélioration du dégradé
L'augmentation du dégradé est un algorithme fascinant et je suis sûr que vous souhaitez aller plus loin.
Cette section répertorie diverses ressources que vous pouvez utiliser pour en savoir plus sur l'algorithme d'amélioration du gradient.
Vidéos d'amélioration du dégradé
- Apprentissage automatique améliorant le dégradé, Trevor Hastie, 2014
- Augmentation du dégradé, Alexander Ihler, 2012
- GBM, John Mount, 2015
- Apprentissage : Boosting, MIT 6.034 Intelligence artificielle, 2010
- xgboost : un package R pour une augmentation de dégradé rapide et précise, 2016
- XGBoost : un système de boosting d'arbres évolutif, Tianqi Chen, 2016
Augmentation du dégradé dans les manuels
- Section 8.2.3 Boosting, page 321, Introduction à l'apprentissage statistique : avec des applications dans R.
- Section 8.6 Boosting, page 203, Modélisation prédictive appliquée.
- Section 14.5 Amplification du gradient stochastique, page 390, Modélisation prédictive appliquée.
- Section 16.4 Boosting, page 556, Machine Learning : une perspective probabiliste
- Chapitre 10 Boosting et arbres additifs, page 337, Les éléments de l'apprentissage statistique : exploration de données, inférence et prédiction
Papiers améliorant le dégradé
- Réflexions sur la renforcement des hypothèses [PDF], Michael Kearns, 1988
- Une généralisation de la théorie de la décision de l'apprentissage en ligne et une application au boosting [PDF], 1995
- Arcer le bord [PDF], 1998
- Augmentation du gradient stochastique [PDF], 1999
- Stimuler les algorithmes en tant que descente de gradient dans l'espace fonctionnel [PDF], 1999
Diapositives améliorant le dégradé
- Introduction aux arbres boostés, 2014
- Une introduction douce à l'augmentation du dégradé, Cheng Li
Pages Web améliorant le dégradé
- Boosting (apprentissage automatique)
- Augmentation du dégradé
- Boostation de l'arbre de dégradé dans scikit-learn
Résumé
Dans cet article, vous avez découvert l'algorithme d'augmentation de gradient pour la modélisation prédictive dans l'apprentissage automatique.
Concrètement, vous avez appris :
- L'histoire du boosting dans la théorie de l'apprentissage et AdaBoost.
- Comment fonctionne l'algorithme d'augmentation du gradient avec une fonction de perte, des apprenants faibles et un modèle additif.
- Comment améliorer les performances de l'augmentation du gradient avec la régularisation.
Avez-vous des questions sur l'algorithme de boosting de gradient ou sur cet article ? Posez vos questions dans les commentaires et je ferai de mon mieux pour y répondre.