Le boosting est une méthode d'apprentissage ensembliste en apprentissage automatique qui combine un ensemble de modèles moins précis, appelés apprenants faibles, pour créer un seul modèle très précis, connu sous le nom d'apprenant fort. Contrairement aux méthodes ensemblistes parallèles telles que le bagging, les algorithmes de boosting construisent les modèles de manière séquentielle. Chaque nouveau modèle de la séquence est entraîné pour corriger les erreurs commises par ses prédécesseurs. Ce processus itératif améliore la précision globale, notamment en réduisant le biais. Le boosting est une technique populaire et efficace utilisée dans l'apprentissage supervisé pour les tâches de classification et de régression.
Les fondements théoriques du boosting proviennent d'une question posée par Kearns et Valiant en 1988 et 1989 : savoir si un ensemble d'apprenants faibles peut créer un seul apprenant fort. Un apprenant faible est défini comme un classifieur qui ne performe que légèrement mieux qu'une supposition aléatoire, tandis qu'un apprenant fort est fortement corrélé à la véritable classification. La réponse affirmative de Robert Schapire dans un article de 1990 a conduit au développement d'algorithmes de boosting pratiques. Le premier de ces algorithmes a été développé par Schapire, Freund et Schapire développant ensuite AdaBoost, qui reste un exemple fondateur du boosting.
Mécanisme central
Bien que le boosting ne soit pas contraint algorithmiquement, la plupart des algorithmes de boosting consistent à apprendre itérativement des classifieurs faibles par rapport à une distribution et à les ajouter à un classifieur fort final. Lorsqu'ils sont ajoutés, ils sont pondérés d'une manière liée à la précision des apprenants faibles. Après l'ajout d'un apprenant faible, les poids des données sont réajustés, un processus connu sous le nom de re-pondération. Les données d'entrée mal classifiées gagnent un poids plus élevé, tandis que les exemples correctement classifiés perdent du poids. Ainsi, les futurs apprenants faibles se concentrent davantage sur les exemples que les apprenants faibles précédents ont mal classifiés.
Cette concentration séquentielle sur les exemples difficiles distingue le boosting des autres méthodes ensemblistes. Le mécanisme de re-pondération garantit que chaque modèle suivant de la séquence traite les erreurs résiduelles de l'ensemble combiné. Sur de nombreuses itérations, l'ensemble réduit progressivement son biais d'entraînement, atteignant souvent une grande précision même lorsque les apprenants faibles individuels ne sont que marginalement meilleurs qu'une supposition aléatoire.
Développement historique
Il existe de nombreux algorithmes de boosting. Les originaux, proposés par Robert Schapire (une formulation de porte majoritaire récursive) et Yoav Freund (boost par majorité), n'étaient pas adaptatifs et ne pouvaient pas tirer pleinement parti des apprenants faibles. Schapire et Freund ont ensuite développé AdaBoost, un algorithme de boosting adaptatif qui a remporté le prestigieux prix Gödel. AdaBoost a été le premier algorithme capable de s'adapter aux apprenants faibles, ce qui le rend historiquement significatif et souvent la base de la couverture introductive du boosting dans les cours universitaires d'apprentissage automatique.
Seuls les algorithmes qui sont des algorithmes de boosting prouvables dans la formulation d'apprentissage probablement approximativement correct peuvent être précisément appelés algorithmes de boosting. D'autres algorithmes d'esprit similaire sont parfois appelés algorithmes de levier, bien qu'ils soient aussi parfois incorrectement appelés algorithmes de boosting. La principale variation entre de nombreux algorithmes de boosting réside dans leur méthode de pondération des points de données d'entraînement et des hypothèses.
Algorithmes majeurs
AdaBoost reste le plus significatif historiquement, mais de nombreux algorithmes plus récents ont été développés. Ceux-ci incluent LPBoost, TotalBoost, BrownBoost, xgboost, MadaBoost, LogitBoost et CatBoost, entre autres. De nombreux algorithmes de boosting s'intègrent dans le cadre AnyBoost, qui montre que le boosting effectue une descente de gradient dans un espace de fonctions en utilisant une fonction de coût convexe.
Les implémentations modernes telles que xgboost et CatBoost sont devenues largement utilisées dans l'industrie et l'apprentissage automatique compétitif en raison de leur évolutivité et de leurs performances. Ces algorithmes intègrent la régularisation, des apprenants faibles efficaces basés sur des arbres et des optimisations pour les données éparses et les caractéristiques catégorielles. Ils sont couramment appliqués dans des domaines allant de la finance à la santé, surpassant souvent d'autres méthodes sur les données tabulaires.
Catégorisation d'objets en vision par ordinateur
Étant donné des images contenant divers objets connus dans le monde, un classifieur peut être appris à partir de celles-ci pour classer automatiquement les objets dans les images futures. Les classifieurs simples construits sur la base d'une caractéristique d'image de l'objet ont tendance à être faibles en performance de catégorisation. L'utilisation de méthodes de boosting pour la catégorisation d'objets est un moyen d'unifier les classifieurs faibles d'une manière spéciale pour améliorer la capacité globale de catégorisation.
Problème de la catégorisation d'objets
La catégorisation d'objets est une tâche typique de l'intelligence artificielle et de la vision par ordinateur qui consiste à déterminer si une image contient une catégorie spécifique d'objet. L'idée est étroitement liée à la reconnaissance, à l'identification et à la détection. La catégorisation d'objets basée sur l'apparence implique typiquement l'extraction de caractéristiques, l'apprentissage d'un classifieur et l'application du classifieur à de nouveaux exemples. Il existe de nombreuses façons de représenter une catégorie d'objets, de l'analyse de forme, des modèles de sac de mots ou des descripteurs locaux tels que SIFT. Des exemples de classifieurs supervisés sont les classifieurs naïfs de Bayes, les machines à vecteurs de support, les mélanges de gaussiennes et les réseaux neuronaux. Cependant, la recherche a montré que les catégories d'objets et leurs emplacements dans les images peuvent également être découverts de manière non supervisée.
Statu quo pour la catégorisation d'objets
La reconnaissance des catégories d'objets dans les images est un problème difficile en vision par ordinateur, surtout lorsque le nombre de catégories est important. Cela est dû à la grande variabilité intra-classe et à la nécessité de généraliser à travers les variations d'objets au sein de la même catégorie. Les objets d'une même catégorie peuvent sembler très différents. Même le même objet peut apparaître différent sous différents points de vue, échelles et éclairages. L'encombrement de l'arrière-plan et l'occlusion partielle ajoutent également des difficultés à la reconnaissance. Les humains sont capables de reconnaître des milliers de types d'objets, tandis que la plupart des systèmes de reconnaissance d'objets existants sont entraînés à n'en reconnaître que quelques-uns, comme les visages humains, les voitures ou les objets simples. La recherche a été très active sur le traitement d'un plus grand nombre de catégories et l'ajout incrémental de nouvelles catégories. Bien que le problème général reste non résolu, plusieurs détecteurs d'objets multi-catégories (pour des centaines ou des milliers de catégories) ont été développés, en partie grâce au partage de caractéristiques et au boosting.
Boosting pour la catégorisation binaire
AdaBoost peut être utilisé pour la détection de visages comme exemple de catégorisation binaire. Les deux catégories sont les visages par rapport à l'arrière-plan. L'algorithme général est le suivant : former un grand ensemble de caractéristiques simples ; initialiser les poids pour les images d'entraînement ; pour T itérations, normaliser les poids, entraîner un classifieur en utilisant une seule caractéristique de l'ensemble disponible, évaluer l'erreur d'entraînement, choisir le classifieur avec l'erreur la plus faible et mettre à jour les poids des images d'entraînement (augmenter si mal classifiées, diminuer si correctement classifiées) ; enfin, former le classifieur fort comme la combinaison linéaire des T classifieurs, avec des coefficients plus grands pour les classifieurs ayant une erreur d'entraînement plus faible. Après le boosting, un classifieur construit à partir de 200 caractéristiques pourrait produire un taux de détection de 95 pour cent avec un taux de faux positifs de 10 à la puissance moins 5.
Une autre application du boosting pour la catégorisation binaire est un système qui détecte les piétons en utilisant des motifs de mouvement et d'apparence. Ce travail a été le premier à combiner à la fois des informations de mouvement et d'apparence comme caractéristiques pour détecter une personne marchant. Il adopte une approche similaire au cadre de détection d'objets Viola-Jones.
Boosting pour la catégorisation multi-classes
Par rapport à la catégorisation binaire, la catégorisation multi-classes implique d'assigner une image à l'une de plusieurs catégories d'objets possibles. Les méthodes de boosting pour les problèmes multi-classes étendent généralement les approches binaires par des stratégies telles que la décomposition un-contre-tous ou un-contre-un, ou en modifiant directement l'algorithme de boosting pour gérer plusieurs classes. Ces méthodes ont permis aux systèmes de détection d'objets de reconnaître des centaines ou des milliers de catégories, bien qu'au prix d'un coût de calcul et d'une complexité accrus.
Applications et impact
Le boosting a été appliqué dans de nombreux domaines au-delà de la vision par ordinateur. Dans les contextes de apprentissage profond, les idées de boosting ont influencé les techniques ensemblistes et l'optimisation par descente de gradient. En traitement du langage naturel, le boosting a été utilisé pour la classification de textes et l'analyse de sentiments. En finance, il est utilisé pour la notation de crédit et la détection de fraude. En bioinformatique, le boosting aide à la classification de l'expression génique et à la prédiction de fonctions protéiques. La capacité de la méthode à combiner des modèles simples en prédicteurs très précis en a fait un pilier de la recherche académique et de la pratique industrielle.
Signification théorique
La signification théorique du boosting réside dans sa démonstration que l'apprenabilité faible implique l'apprenabilité forte. Ce résultat, prouvé par Schapire en 1990, a répondu à la question posée par Kearns et Valiant et a établi une base pour comprendre la puissance des méthodes ensemblistes. Le cadre d'apprentissage probablement approximativement correct fournit des garanties formelles pour les algorithmes de boosting, garantissant qu'avec suffisamment d'apprenants faibles, l'ensemble peut atteindre une erreur arbitrairement faible sur la distribution d'entraînement. Cette base théorique distingue le boosting de nombreuses méthodes ensemblistes heuristiques et a inspiré des recherches approfondies sur les conditions dans lesquelles le boosting réussit.
Limites et considérations
Le boosting n'est pas sans limites. Il peut être sensible aux données bruitées et aux valeurs aberrantes, car le mécanisme de re-pondération peut amener l'ensemble à surajuster les exemples mal étiquetés. La nature séquentielle du boosting le rend également moins adapté à la parallélisation que le bagging, bien que les implémentations modernes aient introduit des approximations pour accélérer l'entraînement. De plus, le choix de l'apprenant faible et le nombre d'itérations peuvent affecter considérablement les performances, nécessitant un réglage minutieux. Malgré ces défis, le boosting reste l'une des techniques les plus efficaces et les plus largement utilisées en apprentissage supervisé.