8
$\begingroup$

How AdaBoost is different than Gradient Boosting algorithm since both of them works on Boosting technique?

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

$\endgroup$
14
$\begingroup$

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 as 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, it can be approximated in an additive fashion by taking 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 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$ s.t. $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.

Second, AdaBoost can be interepted 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.
$\endgroup$
  • $\begingroup$ Nice description. I read more about sample distribution and have one doubt regarding it . AdaBoost change the sample distribution that means it re-creates the sample that can be fed to the subsequent model? is it so?? $\endgroup$ – CodeMaster GoGo Oct 5 '18 at 10:28
  • 1
    $\begingroup$ same samples but weighted differently at each step $\endgroup$ – oW_ Oct 5 '18 at 15:20
  • $\begingroup$ Hi, just to check: "iteratively minimizing one subproblem at a time" is basically an iplementation of the expectation maximisation algorithm? $\endgroup$ – par Sep 28 '19 at 18:43
  • $\begingroup$ No it’s more in the sense of a greedy search $\endgroup$ – oW_ Sep 29 '19 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.