4
$\begingroup$

I am going through Elements of statistical Learning and trying to understand GBM algorithm.

The algorithm of GBM is shown below. enter image description here

I understand general gradient descent algorithm mentioned below very well.

enter image description here

Questions

  1. Which parameter (theta j in the above picture) of GBM is gradient descent updating using each new tree that is added to GBM? Can you explain the above GBM algorithm intuitive in this context?
  2. What is the gamma in the GBM algorithm and intuition behind it?
  3. Seems gamma is calculated for each terminal region per each tree. What does it mean/do?
  4. GBM does not use reweighing of training samples unlike Adaboost which does. True or False?
$\endgroup$
2
$\begingroup$
  1. GBM is gradient descent in the function space rather than the parameter space. GBM uses gradient descent to calculate the iteration residuals for tree construction. The residuals can be thought of as the step direction.
  2. The gamma is computing the gradient descent step which is the terminal node predictions for that iteration. This can be thought of as the step size.
  3. You are correct about gamma being computed for every terminal region. This is only because the base-learner in GBM is a decision tree.
  4. True, although GBM supports the exponential loss function which Friedman proved to be equivalent to adaboost.
$\endgroup$
  • $\begingroup$ Not sure what the function space points to, do you mind to point out. $\endgroup$ – Lily Long Aug 15 '17 at 1:51
  • $\begingroup$ It means that rather than optimizing parameters alone, GBM is optimizing a function. The function is the addition of each tree at each iteration. GBM builds this function using gradient descent. $\endgroup$ – Zelazny7 Aug 15 '17 at 1:53
  • $\begingroup$ Thanks for the answer, I think it's also okay to think it as just optimizing the function of the new tree, as gbm does not modify the previously constructed tress along its iteration. I'm just considering the exact form of "f(x)", as a constructed tree can just gives a terminal region, yet f(x) must be giving a predicted class to fit in the loss function, which can be done by logistic equation. I'm just lost in how to parametrize a tree to make it differentiable. $\endgroup$ – Lily Long Aug 15 '17 at 4:34
  • $\begingroup$ And I'm not sure how the differentiation can gives out rim, which I assume is the targeted region that a specific sample should goes to. $\endgroup$ – Lily Long Aug 15 '17 at 4:39
  • $\begingroup$ I agree that it's ok to think of it as optimizing the new tree. The tree doesn't need to be differentiable, just the loss function to optimize. The residuals of the current ensemble are used to train a regression tree. In other words, the tree is constructed to find terminal regions that minimize the residuals for the current iteration. $\endgroup$ – Zelazny7 Aug 15 '17 at 14:06

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.