5
$\begingroup$

I'm reading Introduction to Statistical Learning, James, G., et al. (2013), in which they describe the Boosted Regression Tree algorithm as following. What I do not understand is Eq 8.10 and 8.11. What do "adding the new tree to the old tree" & "update the residual", as signified by $\leftarrow$, mean mathematically?

enter image description here

The working guide to boosted regression tree by the same authors do not explain how exactly to add the trees either.

$\endgroup$
5
  • $\begingroup$ You don't actually "sum trees" -- the pseudocode you have there clearly indicates what you do sum. Are you clear on what $f$ and $f^b$ are? $\endgroup$ – Glen_b Jan 29 '15 at 1:09
  • $\begingroup$ You seem to be referring to James, G., et al. (2013) not Hastie, T., et al. (2011). I frequently confuse them myself. $\endgroup$ – Ellis Valentiner Jan 29 '15 at 1:09
  • $\begingroup$ @Glen_b Thanks for pointing out a detail I miss. So $f$ is the tree, but $\hat f(x)$ is the predicted value after plugging $x$ into the tree's decision rule. So (8.11) makes sense because $r_i$ and $\hat f^b(x_i)$ are both a number. But (8.10) is unclear: how am I updating the tree (a set of decision rules, not any particular value), while the pseudocode is saying $\text{a number} \leftarrow \text{a number} + \lambda \text{a number}$? $\endgroup$ – Heisenberg Jan 29 '15 at 3:01
  • $\begingroup$ @user12202013 Both James and Hastie are authors on the book, so while it would be unconventional to refer to the book as Hastie et al rather than James et al, I wouldn't say it's actually wrong since Hastie is an author. $\endgroup$ – Glen_b Jan 29 '15 at 3:03
  • 1
    $\begingroup$ Strictly speaking I wouldn't call "$f$" exactly a tree either. $f$ is the underlying function we're trying to fit by using a tree-model. When we speak of something being "a tree" we're usually using shorthand. $\endgroup$ – Glen_b Jan 29 '15 at 3:05
9
$\begingroup$

They assume that you're keeping track of a "current estimator" $\hat f$, which is a sum of all the trees you've seen so far. (In code you would just store this as an array of all the trees you've seen so far.) The $\leftarrow$ sign just means "takes the new value"--so when they say "add the new tree" they mean, basically, append the new tree to the array of trees you already store, so that where you previously would have computed $\hat f$ with that array, you now compute $\hat f + \lambda \hat f^b$. (The $\leftarrow$ sign just means "takes the new value".)

The residual is just the difference between the response and your current prediction $\hat f$. So if you add something to $\hat f$ you need to subtract it from the residual so that they continue to sum up to the target response. Again, the $\leftarrow$ sign just means "takes the new value"--so $r_i \leftarrow r_i - \lambda \hat f^b(x_i)$ would translate in code to r[i] -= lambda * tree_prediction[i] or something.

$\endgroup$
6
  • $\begingroup$ So that array of trees is my model? How do I make prediction with that array of trees? $\endgroup$ – Heisenberg Jan 28 '15 at 23:57
  • 1
    $\begingroup$ As the algorithm states, the final model is $\hat f = \sum \lambda \hat f^b$--in other words, you just sum the values that each individual tree gives (times the learning rate). $\endgroup$ – Ben Kuhn Jan 29 '15 at 0:49
  • $\begingroup$ @BenKuhn +1 great explanation. I have one grey point though: the Hastie 2009 (eq. 10.1 p.338) says that for AdaBoost, prediction is achieved through weigthed majority vote, so that more influence is given to the most accurate trees in the sequence. That is, the value that each individual tree gives is multiplied by some accuracy-based weight. Does that carry over for Gradient Boosted trees? Are there multiple lambdas that include some information about the accuracy of each tree, or just 1 lambda (the learning rate)? $\endgroup$ – Antoine Apr 25 '15 at 17:45
  • $\begingroup$ @user2835597: In gradient boosting, it isn't meaningful to think about the "accuracy" of the base learners. This is because the base learners of a GBM are being fit to the residual--that is, the gradient of the loss function, or "how incorrect the previous best estimate was." So you can't evaluate the performance of a tree except in the context of the approximation that it's a part of. Each tree learns to reduce a specific (different) loss function estimate as much as it can, so weighting them by performance after that wouldn't make sense. For this reason there's only one lambda. $\endgroup$ – Ben Kuhn Apr 27 '15 at 5:11
  • $\begingroup$ @BenKuhn. Thanks, that makes sense, but now, I am confused about AdaBoost. I thought the only difference with GBM was the absence of shrinkage (and the imposed exponential loss). But if this is true, given your explanation, how can weighted majority vote be achieved in AdaBoost? What you said for GBM also applies, so it shouldn't be possible? $\endgroup$ – Antoine Apr 27 '15 at 8:53

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.