Intuitive explanations of differences between Gradient Boosting Trees (GBM) & Adaboost

Question

I'm trying to understand the differences between GBM & Adaboost.

These are what I've understood so far:

• There are both boosting algorithms, which learns from previous model's errors and finally make a weighted sum of the models.
• GBM and Adaboost are pretty similar except for their loss functions.

But still it is difficult for me to grab an idea of differences between them. Can someone give me intuitive explanations?

Answer 1

I found this introduction which provides some intuitive explanations:

• In Gradient Boosting, ‘shortcomings’ (of existing weak learners) are identified by gradients.
• In AdaBoost, ‘shortcomings’ are identified by high-weight data points.

By means of an exponential loss function, AdaBoost gives more weights to those samples fitted worse in previous steps. Today, AdaBoost is regarded as a special case of Gradient Boosting in terms of loss function. Historically it preceded Gradient Boosting to which it was later generalized, as shown in the history provided in the introduction:

1. Invent AdaBoost, the first successful boosting algorithm [Freund et al., 1996, Freund and Schapire, 1997]
2. Formulate AdaBoost as gradient descent with a special loss function [Breiman et al., 1998, Breiman, 1999]
3. Generalize AdaBoost to Gradient Boosting in order to handle a variety of loss functions [Friedman et al., 2000, Friedman, 2001]

Answer 2

An intuitive explanation of AdaBoost algorithn

Let me build upon @Randel's excellent answer with an illustration of the following point

---

• In AdaBoost, ‘shortcomings’ are identified by high-weight data points

AdaBoost recap

Let $G_m(x) \ m = 1,2,...,M$ be the sequence of weak classifiers, our objective is to build the following:

$$G(x) = \text{sign} \left( \alpha_1 G_1(x) + \alpha_2 G_2(x) + ... \alpha_M G_M(x)\right) = \text{sign} \left( \sum_{m = 1}^M \alpha_m G_m(x)\right)$$

• The final prediction is a combination of the predictions from all classifiers through a weighted majority vote

• The coefficients $\alpha_m$ are computed by the boosting algorithm, and weight the contribution of each respective $G_m(x)$. The effect is to give higher influence to the more accurate classifiers in the sequence.

• At each boosting step, the data is modified by applying weights $w_1, w_2, ..., w_N$ to each training observation. At step $m$ the observations that were misclassified previously have their weights increased

• Note that at the first step $m=1$ the weights are initialized uniformly $w_i = 1 / N$

AdaBoost on a toy example

Consider the toy data set on which I have applied AdaBoost with the following settings: Number of iterations $M = 10$, weak classifier = Decision Tree of depth 1 with 2 leaf nodes. The boundary between red and blue data points is clearly non linear, yet the algorithm does pretty well.

Visualizing the sequence of weak learners and the sample weights

The first 6 weak learners $m = 1,2,...,6$ are shown below. The scatter points are scaled according to their respective sample weight at each iteration

First iteration:

• The decision boundary is very simple (linear) since these are weak learners
• All points are of the same size, as expected
• 6 blue points are in the red region and are misclassified

Second iteration:

• The linear decision boundary has changed
• The previously misclassified blue points are now larger (greater sample weight) and have influenced the decision boundary
• 9 blue points are now misclassified

Final result after 10 iterations

All classifiers have a linear decision boundary, at different positions. The resulting coefficients of the first 6 iterations $\alpha_m$ are :

1.041, 0.875, 0.837, 0.781, 1.04, 0.938...

As expected, the first iteration has largest coefficient as it is the one with the fewest misclassifications.

Next steps

An intuitive explanation of gradient boosting - to be completed

Sources and further reading:

• python code and original figures here
• https://www.cs.cmu.edu/~aarti/Class/10701/slides/Lecture10.pdf