# Which data are used at each step of Stochastic Gradient Boosting? Subsample of the original training set or gradient of the loss function?

The bag.fraction parameter in SGB controls the size of the random subsample of the original training set on which each successive weak learner is fitted:

At each iteration a subsample of the training data is drawn at random (without replacement) from the full training data set. This randomly selected subsample is then used, instead of the full sample, to fit the base learner and compute the model update for the current iteration.

(Quote from the original SGB paper by Friedman).

What I don't get is how this is compatible with the fact that in Gradient Boosting, each successive base model is fitted directly on the residuals (or gradient of the loss function) of the current model.

In other words, how can we fit each new base model on the residuals of the current model and at the same time on a random subsample of the original training set? What is the link between these two key steps?

If someone with enough Python literacy could find the information from the code, that'd be great. Also, the R code is not useful as it is only a wrapper for a C implementation.

• I have met the two conditions on the link you provide (clear question + bounty). But I have not obtained a satisfying answer yet. This is why I am asking Boosting experts to have a look at my question. I don't see how that could be considered bad practice, but if it is I will stop of course. – Antoine Oct 7 '15 at 17:11
• I agree that it's a clear question (+1) and I applaud your decision to promote it with a bounty. However, comments--no matter what their subject or purpose may be--that are not relevant to a particular thread are unwelcome as a matter of course (which is why yours have been raising flags and had to be deleted, one by one). Boosting experts who frequent our site will already be well aware of your question, so attempting to contact them individually could backfire by annoying them. – whuber Oct 7 '15 at 17:18
• Thanks for your explanation and upvote. Since my question has been out for more than 20 days (including 3 days of bounty), there are two options: (1) Boosting experts are not aware of my question; (2) Boosting experts don't care. I was opting for (1) which explains (but don't excuse) my behavior, but in light of your comment Boosting experts who frequent our site will already be well aware of your question, it seems that (2) may actually be true; which is actually rather depressing. – Antoine Oct 7 '15 at 17:25
• I could always be wrong about that :-). Have you considered tweeting your post or otherwise drawing attention to it on social media? – whuber Oct 7 '15 at 17:58

I've implemented this here in a way that performs comparably to other implementations at least in my testing.

At each step you have a residual R calculated across the entire data set (before any base learners are fit its the residual from predicting the average).

You subsample without replacement and fit the learner to the values of R for the points in that subsample.

Then you apply that learner to get a prediction across the entire data set and update R using that prediction.

So you're still updating the residual across the entire data set, you're just randomizing the process of fitting each base learner a bit.

I tried to decipher the steps in the original Friedman 2002 paper. If I am not wrong, it appears that we actually both deal with the current residuals and the original training set. Especially, the algorithm is as follows:

Here is what I have understood, step by step. Please tell me if there is something amiss. See (*) below for some notation.

• line 1: $F_{0}(x)$ is just an initial guess (and that's not what I'm interested in here)
• line 4: we compute the current "pseudo-residuals" for a random subsample of the training set $(y_{\pi(i)},x_{\pi(i)})$ as the negative gradient of the loss function. By current, I mean that we want to add the $m^{th}$ base learner, and that the model so far is a sequence of $m-1$ base learners.
• line 5: the $m^{th}$ base learner is a regression tree that partitions the space of the $x_{\pi(i)}$'s into $L$ disjoint regions $R_{lm}$ so that the within-region variance in terms of pseudo-residuals (computed at line 4) is minimized (this is how a tree works). The predictions $\bar{y}_{lm}$ made by the tree are the means of the current pseudo-residuals in each region. This is what I was referring to in my question by: how can we fit each new base model on the residuals of the current model...
• line 6: within each region $R_{lm}$ found at line 5, we pick the expansion coefficient $\gamma_{lm}$ that minimizes the loss function (not its gradient, so we're not dealing with residuals here) evaluated on the random subsample of the target $y_{\pi(i)}$ and the corresponding predictions of the current model $F_{m-1}(x_{\pi(i)})$. This is what I was referring to in my question by: ...and at the same time on a random subsample of the original training set?
• line 7: we add the (contribution of) the new base learner to the sequence as its expansion coefficients for each region multiplied by the learning rate. This final step is still a bit weird to me, as we are not directly adding the new base learner itself (unlike what the widespread belief about Boosting might suggest). But I guess this is equivalent, since the $\gamma_{lm}$'s inherently encode the information about the new base learner (they were estimated within each leaf of the tree).

*Some notation:

• $(y_{i},x_{i})$ is the training set (target, predictor)
• the goal of Boosting (like any other ML algo) is to approximate the function $F(x)$ that maps $x$ to $y$
• The approximation of $F$ proposed by Boosting takes the form $F(x)=\sum_{m=0}^{M} \beta_{m}h(x,a_{m})$, where the $\beta$'s are expansion coefficients and the $a$'s are parameters of the base learners $h$'s (which are regression trees in Tree Boosting). So the $a$'s are the splits of the tree (optimizing the $a$'s=building the tree). $m$ is the number of base learners in the sequence. For trees, there is one $\beta_{m}$ per leaf, they are referred to as the $\gamma_{lm}$'s
• $\Psi$ is any differentiable loss function. We want the $F$ that minimizes the expected value of $\Psi(y,F(x))$.
• At each step, $F_{m}(x)=F_{m-1}(x)+\nu\beta_{m}h(x,a_{m})$

The concept of residuals makes sense on any set of data for which:

• You can use your model to make predictions and
• You have a true response value on each record

So, if you, for example, split your full training data in two halves and then train on the first half, you can still predict on the second half and compute the residuals there.

I want to note though, that each base learner is fit to residuals in only the gaussian case of a gradient booster. In the general case the weak learners are fit to the gradient of the loss function, which in the gaussian case turns out to be equivalent, but in all others are not. You make this note as well, but I thought it was worth repeating.

• Say I am adding a new tree to my current SGB model, in the regression case (squared error loss). It is clear that the fit should take into account the gradient of the loss function (=residuals here) somehow. My intuition would be that the tree is fitted on a subsample of the current residuals (squared diff between predictions of the current model and observations), but that can't be true per Friedman's quote in my question above (each weak learner is fitted on a subsample of full original training set). So on what data do we fit each new tree at each step? – Antoine Oct 7 '15 at 20:45

I think you are confusing the features with the dependent variable. In gradient boosting models you fit the tree on the current gradient (which coincides with residuals for Gaussian models) using already existing features. Features do not change, only the gradient is changing at each step, because of the updating. Gradient is computed for each observation in the training set, so when you randomly select half of the training set it is easy to track which gradients to use. See Figure 2 in R package gbm vignette for better explanation, or the gradient tree boosting algorithm in section 10 in Elements of Statistical Learning.

• so, to stay focused about my question, by confirming that each tree is fitted on the current residuals, you're implicitly saying that the training set is indeed the current residuals? So, at each step, half of the residuals are randomly selected to fit the tree? – Antoine Sep 16 '15 at 12:51
• Yes. At each step half of the residuals are randomly selected to fit the tree. – mpiktas Sep 16 '15 at 13:04
• From the original paper by Friedman, it is clear that each tree is fitted on (a random subsample) of the full original training set: At each iteration a subsample of the training data is drawn at random (without replacement) from the full training data set. This randomly selected subsample is then used, instead of the full sample, to fit the base learner and compute the model update for the current iteration. Which means that the steps in my question above are completely wrong. – Antoine Sep 16 '15 at 14:35