AdaBoost Illustrated

AdaBoost (short for Adaptive Boosting) is a powerful boosting algorithm that can boost the performance of any machine learning model. It was introduced in 1995 by Freund and Shapira [1], who won the 2003 Gödel Prize (one of the most prestigious prizes in Computer Science) for their work. It is still one of the most popular boosting algorithms used today.

This article explains the AdaBoost algorithm in detail, demonstrates its usage on a toy example, and shows you how to run it using Scikit-Learn.

Background: Boosting Methods

Boosting is an ensemble method (see this article for an introduction on ensemble methods), where the base models are trained in sequence. Each model focuses on correcting the errors made by the previous models.

In AdaBoost, samples that are misclassified by one model are assigned greater weight when used to train the next model. Each model is thereby forced to concentrate on examples that were misclassified by the previous ones.

The predictions of the models are then combined using a weighted majority vote, where the weights are based on how well each model performed on the training set.

The base learners used in boosting are usually weak learners, i.e., models whose accuracy is only slightly better than a random guesser (50% + ϵ, for a small ϵ). The advantage of weak learners is that they are fast to train and they suffer less from overfitting.