Why do we use gradients instead of residuals in Gradient Boosting?

Question

I have found mentions of two advantages in using gradients instead of actual residuals:

1) Using gradients will allow us to plug in any loss function (not just mse) without having to change our base learners to make them compatible with the loss function.

2) It can be computationally infeasible (in the case of MAE, we would have to calculate the median in every split).

However, I don't understand these points, namely:

1) If we just calculate the residual and have the base learner fit on those values, how exactly would that be any more difficult than calculating the gradients and then fitting on those values?

2) Following on the above question, why exactly do we need to calculate the median in the MAE example instead of just getting the residuals?

Perhaps I don't understand the exact mechanism behind optimizing an individual loss function. It would be really great if someone could demonstrate exactly how MAE is done and in which step would using residuals have been infeasible.

Answer 1

Hmmm, I am little perplexed by your question.

In gradient boosting, we do use the residuals. The residuals are the gradients.

You can check my simple implementation of gradient boosting. This is where the magic happens:

def fit(self, X, y):
    self.fs = [self.first_estimator]
    # step 0
    f = self.first_estimator.fit(X, y)
    # step 1
    for m in range(self.M):
        f = self.predict(X)
        # step 2
        U = self.loss(y, f)
        # step 3
        g = clone(self.base_estimator).fit(X, U)
        # step 4
        self.fs.append(g)

You start by a dummy model $f$. Then you create a new model $g$ based on the errors of the existing ensemble $L(f(x),y)$. The code should be pretty straight-forward. Check the algorithm in the wikipedia page for a more formal presentation.

---

Why am I using residuals and gradients as interchangeable words?

You have discrete mathematics and continuous mathematics.

In neural networks, we use the definition of gradient from continuous mathematics. You have a loss function that is $C_1$ continuous (meaning that the loss must be differentiable at least once).

$$f'(x) = \lim_{h\to0} \frac{f(x+h)-f(x)}{h}$$

In gradient boosting, we use the definition of gradient from discrete mathematics. It's usually called fininite differences, instead of derivative or gradient.

$$f'(x) = f(x+1)-f(x)$$

Personally, I think gradient is a misnomer. But it's marketing. Gradient boosting sounds more mathematical and sophisticated than "differences boosting" or "residuals boosting".

By the way, the term boosting already existed when gradient boosting was invented. It was used for AdaBoost, which changes the weights of the observations based on the loss, rather than training in the residuals. AdaBoost only works for weak models (each model must commit errors), while gradient boosting can do resample and work for strong models.

---

Important point on gradient boosting

One important difference between gradient boosting (discrete optimization) and neural networks (continuous optimization) is that gradient boosting allows you to work with functions whose derivative is constant.

In gradient boosting, you can use "weird" functions like MAE or the Pinball function. In my code, you can see that you can choose between MSE, MAE and quantile (which is the pinball loss). These latter two do not work very well for neural networks.

The pinball loss is used for quantile predictions, like wind forecasts in energy systems. This is the reason why gradient boosting is much used in these systems.

Small point: many people think that the reason why MAE and Pinball functions work bad for neural networks is because they are not continuous. While it is true they are not continuous when $y=\hat y$, it's very easy to work-around that. This is not the reason why results are so poor with those losses. The reason why they don't work well is because the optimization steps use the gradient (in gradient descent), and the gradient is constant for the entire function $L'(y,\hat y)=1$ or $L'(y,\hat y)=-1$, so the magnitude of the gradient is always 1. The optimization will depend solely on the learning rate heuristic that you are using, which usually will not work out very well.

Answer 2

I know this is an old question, but it took me a while to get my head around it

The objective at each iteration of the gradient boosting algorithm is to find a base learner which gives the largest improvement to the loss function L, we can write this as follows

Here $L()$ is the loss function, $y_i$ is the target, $\hat{y}_i^{(t-1)}$ is the estimate from the previous iteration, $\nu$ is the learning rate and $f_t(x_i)$ is the base learner.

Gradient Boosting is a first-order approximation to the equation above, we take a first-order series expansion, the result is; find base learner $f_t$ which minimises $L(-g_i, f_t(x_i))$ where $g_i$ is the gradient of $L(y_i,\hat{y}_i)$ with respect to $\hat{y}$ at the current iteration $t$. In other words, fit each base learner to the -ve gradient of the loss function from the previous iteration.

Hence for a general loss function, gradient boosting requires that we fit the gradients at each step, and for mean squared loss, the gradient just happens to be the residuals so whilst is seems somewhat intuitive it is also slightly misleading to think of gradient boosting as fitting residuals (or even pseudo residuals as the gradients are often named), it is actually gradient descent in function space.

Answer 3

Trying to directly answer your question and articulate the use of gradient in boosting machine.

Answer to your question

1. The goal of your predictive model is actually trying to minimize your loss function. Intuitively the minimization of the loss function should bring your predicted target values $\hat{y}$ close to true target value $y$ but we do this via minimizing a loss function. If you have your base learners fit residuals, then you are correctly doing the optimization only for the case of squared error loss function as mentioned in other answers and comments.
2. The answer is that median minimizes MAE loss, you can see for example the reference: https://gennadylaptev.medium.com/median-and-mae-3e85f92df2d7 So if you fit residuals with MAE loss function, you are computing median and use it as a guide to split if the base learner is tree-based.

Gradient in boosting machine

1. Usual gradient descent. We want to minimize the expectation value of a loss function $\mathcal{L}$ and we usually compute it by the empirical mean from a collected dataset: \begin{equation} \theta^* = \text{argmin}_{\theta}\frac{1}{N} \sum_{i=1}^N \mathcal{L}(y_i, \hat{y}_i(\theta)) =: \text{argmin}_{\theta} L(\theta), \end{equation} where $\theta$ is a collection or a vector of parameters to learn. $N$ is the number of data points. $y_i$ is the ground truth of the $i$-th data point and $\hat{y}_i$ is the estimate. We want to solve this optimization iteratively by \begin{equation} \theta_t = \theta_{t-1} + \Delta\theta. \end{equation} Now, Taylor expand the loss function to first order, \begin{equation} L_t := L(\theta_t) = L(\theta_{t-1} + \Delta\theta) = L_{t-1} + \left.\frac{\partial L}{\partial\theta}\right|_{\theta=\theta_{t-1}} \Delta\theta. \end{equation} Recall the geometric meaning of the gradient, it is easy to see that the best choice of $\Delta\theta$ is to align it with the negative gradient: \begin{equation} \Delta\theta = - \eta \left.\frac{\partial L}{\partial\theta}\right|_{\theta=\theta_{t-1}}, \end{equation} where $\eta$ is the step size we want to take, a.k.a. learning rate. Indeed, the above choice of $\Delta\theta$ leads to \begin{equation} L_t := L_{t-1} - \eta \left( \left.\frac{\partial L}{\partial\theta}\right|_{\theta=\theta_{t-1}} \right)^2 < L_{t-1}. \end{equation} This is the magic to iteratively decrease the loss function.

Now, come back to boosting machine. We will do something very similar here. The only difference is that we will be in the functional space. We write the loss function \begin{equation} \hat{y}^* = \text{argmin}_{\hat{y}}\frac{1}{N} \sum_{i=1}^N \mathcal{L}(y_i, \hat{y}_i) =: \text{argmin}_{\hat{y}} L[\hat{y}], \end{equation} where instead of viewing the loss function as a function of parameters, we view it as a functional of the prediction. Now, we also solve this iteratively (boosting), \begin{equation} \hat{y}_t = \hat{y}_{t-1} + h_t, \end{equation} where we have omitted the data label subscript $i$ for simplicity but it is understood that $h_t$ is a function as $h_t(x_i)$. Taylor expansion of the functional gives us \begin{equation} L_t := L[\hat{y}_{t}] = L[\hat{y}_{t-1}+h_t] = L_{t-1} + \left.\frac{\delta L}{\delta\hat{y}} \right|_{\hat{y} = \hat{y}_{t-1}} h_t. \end{equation} Similar to what we did in gradient descent section, we choose \begin{equation} h_t = - \eta \left.\frac{\delta L}{\delta\hat{y}} \right|_{\hat{y}_{t-1}}. \end{equation} Equivalently, we may say that the base learner $h_t$ at iteration $t$ learns the negative gradient or error of our current model. This greedy choice decreases loss function iteratively: \begin{equation} L_t := L_{t-1} - \eta \left( \left.\frac{\delta L}{\delta\hat{y}} \right|_{\hat{y} = \hat{y}_{t-1}} \right)^2 < L_{t-1}. \end{equation} So, in gradient boosting machine, we still follow the gradient descent approach but in a functional space. You can easily check that there are many choices of loss functions which do not satisfy "residual = gradient".