2
$\begingroup$

In Friedman's paper on Gradient Boosting, he states the motivation for the gradient boosting algorithm is that it provides a framework of boosting for arbitrary loss functions. He then steps through a motivating example of gradient boosting using the MAE or L1 loss with regression trees as follows:

enter image description here

To add more motivation, he states the following:

enter image description here

There are two things I don't understand:

  • Why is using least squares to fit the regression tree on the gradient of the L1 loss function faster than directly minimizing the L1 loss directly? It seems straightforward to iterate through your data to find the best splitting point and variable using L1 loss rather than the traditional L2 loss. I don't see how "Squared-error loss is updated much more rapidly" in this case.
  • Also I don't think inducing/fitting a tree on the gradient of L1 loss is equivalent to fitting the tree directly with the L1 loss function. For example, if I have the data set ${(-1, -1), (0,0), (1, 1000)}$ with $F_0(x) = 0$. Then on my first step if I use the GBM algorithm, I'm fitting onto the signed vectors (-1,0,1). My tree split would then be $R_1 = (x < 0)$ and $R_2 = (x >= 0)$ where the values of $R_1(x) = -1$ and $R_2(x) = 500$. The MAE in this case would be 500.

However if I fit the tree by directly minimizing the L1 loss, I would make the split $R_1 = (x <=0)$ and $R_2 = (x > 0)$ with values $R_1(x) = -0.5$ and $R_2(x) = 1000$ with a MAE of 1. Fitting the tree by directly minimizing the L1 loss rather than fitting on the gradients seems strictly better in this example.

Thus I'm struggling to understand the benefits of doing the "intermediate" step of fitting on the gradient rather than utilizing the "alternative approach" of fitting a tree to directly minimize the loss function of your choice (L1 loss in this particular example).

EDIT:

To address my first question, it is more efficient to calculate the L2 loss because it first involves taking the average for each region in the tree vs. taking the median. Taking the average should have complexity $O(n)$ vs $O(n * lg(n))$ for the median b/c you have to sort the data in each region to calculate the median. So to follow up on my uncertainty: Is this the sole motivation for fitting to the gradients (with L2 error) rather than optimizing for the arbitrary loss function?

$\endgroup$
5
  • $\begingroup$ Have you looked at the Delta rule? It has a connection to the splitting of the tree, and gradient descent. $\endgroup$ – EngrStudent Jan 4 at 0:23
  • 1
    $\begingroup$ @EngrStudent I took a look at the Wikipedia article for the Delta rule but I am missing how this addresses the question of fitting gradients vs a direct optimization of the loss function. $\endgroup$ – JYCXYZ Jan 4 at 14:29
  • $\begingroup$ Welcome to CV. Adaboost in gbm's doesn't operate on the raw data. It looks at the errors, and changes the weight so that bigger errors get more engagement. You can think of a single CART as piecewise constant approximation with "cuts" perpendicular to the axes. The best place for a cut is not in a relatively flat region, but in steeper regions. Variance can be approximated using square of slope, so shrink parcels in areas of high variance. $\endgroup$ – EngrStudent Jan 4 at 18:01
  • $\begingroup$ @EngrStudent Thanks for the welcome! I understand that GBM is minimizing loss by using previous iterations of the model along with the raw data. I do not understand the point about the Delta rule or the high level description of what the CART model is doing with regards to my original question. My confusion is the motivation behind "fitting the gradient/gradient descent" in the GBM method vs. a method where we minimize the loss function directly in each iteration. $\endgroup$ – JYCXYZ Jan 4 at 19:14
  • $\begingroup$ I'm wanting to make plots and images, so perhaps I'm at a point to make an actual answer instead of a comment. It might take just a bit to do so. $\endgroup$ – EngrStudent Jan 5 at 2:57

Your Answer

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

Browse other questions tagged or ask your own question.