Adaboost vs Gradient Boosting

Question

How is AdaBoost different from a Gradient Boosting algorithm since both of them use a Boosting technique?

I could not figure out actual difference between these both algorithms from a theory point of view.

Answer 1

Both AdaBoost and Gradient Boosting build weak learners in a sequential fashion. Originally, AdaBoost was designed in such a way that at every step the sample distribution was adapted to put more weight on misclassified samples and less weight on correctly classified samples. The final prediction is a weighted average of all the weak learners, where more weight is placed on stronger learners.

Later, it was discovered that AdaBoost can also be expressed in terms of the more general framework of additive models with a particular loss function (the exponential loss). See e.g. Chapter 10 in (Hastie) ESL.

Additive modeling tries to solve the following problem for a given loss function $L$:

$ \min_{\alpha_{n=1:N},\beta_{n=1:N}} L\left(y, \sum_{n=1}^N \alpha_n f(x,\beta_n) \right)$

where $f$ could be decision tree stumps. Since the sum inside the loss function makes life difficult, the expression can be approximated in a linear fashion, effectively allowing to move the sum in front of the loss function iteratively minimizing one subproblem at a time:

$ \min_{\alpha_n,\beta_n} L\left(y, f_{n-1}((x) + \alpha_n f_n(x,\beta_n) \right)$

For arbitrary loss functions this is still a tricky problem, so we can further approximate this by applying a steepest descent with line search, i.e. we update $f_n$ by taking a step into the direction of the negative gradient.

In order to avoid overfitting on the gradient, the gradient is approximated with a new weak learner. This gives you the gradient boosting algorithm:

1. Start with a constant model $f_0$
2. Fit a weak learner $h_n$ to the negative gradient of the loss function w.r.t. $f_{n-1}$
3. Take a step $\gamma$ so that $f_n= f_{n-1} + \gamma h_n$ minimizes the loss $L\left(y, f_n(x) \right)$

The main differences, therefore, are that Gradient Boosting is a generic algorithm to find approximate solutions to the additive modeling problem, while AdaBoost can be seen as a special case with a particular loss function. Hence, Gradient Boosting is much more flexible.

On the other hand, AdaBoost can be interpreted from a much more intuitive perspective and can be implemented without the reference to gradients by reweighting the training samples based on classifications from previous learners.

See also this question for some further references (quote):

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