AdaBoost Explained

In this series, I’m going to go through a number of tree based learning algorithms. Before we can dive into XGBoost, LightGBM, CatBoost we will need to cover the foundational method AdaBoost.

In a forest of trees that’s made with AdaBoost algorithm, the trees are usually composed of just a node a 2 leaves. These trees are also called stumps because of their short structure. Stumps are not really good at making decisions because they use one variable to make the predictions. However, this is not a problem as AdaBoost uses many stumps to make a final prediction. Each of the stumps that AdaBoost builds becomes a weak learner, and collectively these weak learners are able to make a much better prediction.

Photo by Blanka Novotná on Unsplash

If you are familiar with random forests, this probably sounds very similar. However, there are a few differences between the two algorithms. First, in a random forests, each tree affects the final decision equally. In AdaBoost, we actually weigh the stumps and allow some stumps to have more weigh in the decision. Second, in AdaBoost, the errors that the first stump make, influences how the second stump is built, and the errors the second stump make, influences how the third stump is built. This process is repeated until some condition. However, in random forests, each decision tree is built independent of the other trees. Lastly, decision trees can use multiple variables within a tree, whereas in AdaBoost we use stumps making the weak learner quite weak.

To sum up the ideas behind AdaBoost:

• AdaBoost uses a number of weak learners, that are structurally stumps.
• AdaBoost weighs the stumps, making some stumps more important than others.
• Each stump is made by taking into account the errors of the previous stump.

Ok, let’s go through an example to see how this is done.

We have the following toy data where given 3 features, we are trying to predict whether the patient is going to have a heart failure. Looking at this toy data, we can see that if the patient had a bypass surgery in the past, they are more likely to have heart failure. The other two features we can use for predicting the heart failure are arm pain and weight of the patient. The last column in this table is the sample weight, which AdaBoost uses to signify the importance of the sample. When we are starting, all the samples are weighed equally. However, during multiple iterations of the AdaBoost algorithm, the weight column will be used to pass information from one stump to another so that the new stumps put more emphasis on the incorrectly classified examples.

Toy Data

We now want to find the first stump in the forest. We are going to find that stump by finding which of the three variables (arm pain, bypass, weight) can classify the samples best. Let’s start with Arm Pain. Using the Arm Pain feature, our stump can correctly predict 3 out of the 5 heart failures and out of the 3 cases it classified as no heart failure it made only 1 mistake.

Arm Pain As a Stump

We try out all the other features, previous bypass surgery and the weight of the patient and perform a similar analysis.

Out of these three possible stumps, the best classifier is the one that’s using the weight feature. We could calculate the Gini index to chose our stump, very much like how the decision trees are trained.

Up until now, the training didn’t look much different from random forests, with the exception of building just a stump. This is where things get interesting. Total error that a stump makes is all the sum of all the weights of incorrectly classified samples. In our particular case, since we have only one error and the corresponding error for that sample is 1/8, the total error that our stump made is 1/8. Note that, the best stump would achieve an error of 0 when it classifies all the samples correctly and the worst stump would achieve an error of 1 since all the sample weights sum up to 1. The total error that the stump made, is used as the total_say of the stump. A stump that made a lot of errors would have less total_say and a stump that correctly classified every sample would have a very high total_say.

Total Say of a Stump

Plugging our total_error of 1/8 for this stump, we calculate the total_say to be 0.97. Note the high value that this stump is getting. This is because we made only 1 mistake during the classification.