10
$\begingroup$

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.

$\endgroup$

3 Answers 3

8
$\begingroup$

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.

$\endgroup$
1
  • 6
    $\begingroup$ In gradient boosting, each weak learner is fit to the negative gradient of a loss function. When the loss function is a squared loss, e.g. $\frac{1}{2}(y - f(x))^2$, the negative gradient wrt. $f(x)$ happens also to be the residual $y-f(x)$. But this isn't always the case for other loss functions. So saying gradient and residual are the same isn't accurate. $\endgroup$
    – zyxue
    Jan 3, 2021 at 15:50
6
$\begingroup$

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

enter image description here

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.

$\endgroup$
1
  • 4
    $\begingroup$ I think this is the correct answer. It just happens that for square loss the derivative is the residual $\endgroup$
    – rapaio
    Jul 20, 2019 at 18:46
2
$\begingroup$

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".

$\endgroup$
4
  • 1
    $\begingroup$ When you go from a loss function to a loss functional, I don't understand how a program is supposed to implement the derivative of a functional with respect to a function. You say equivalently, the base learner learns the negative gradient or error of our current model, but how do we go from this result - a derivative of a functional with respect to a function - to something we can actually program? $\endgroup$
    – JoseOrtiz3
    Apr 13, 2023 at 2:59
  • $\begingroup$ In practice, we do: In each iteration, 1. compute the negative gradient $h_t$ which is doable as you have loss function as a function(al) of $\hat{y}$, then 2. fit a base learner to predict $h_t$. This is simply a step of applying any standard predictive model, e.g. a tree. 3. add the prediction to get your final prediction by $\hat{y}_{t+1} = \hat{y}_{t} + \hat{h}_{t}$. One of what I tried to emphasize is that the "ground truth" $h_t$ here is negative gradient instead of residual. (The negative gradient is often called pseudo-residual). $\endgroup$
    – chichi
    Apr 13, 2023 at 8:02
  • $\begingroup$ (Continue from my last comment) So I guess what you missed is probably that 1) we are able to compute the derivative of a functional (just following usual derivative rules), and 2) that negative gradient (or called pseudo-residual) serves as a "ground truth" for a base learner to predict. After you add this prediction to the current prediction $\hat{y}_t$, you get a better model. Then you compute the gradient again using your current prediction value which is now $\hat{y}_{t+1}$, and so on.. $\endgroup$
    – chichi
    Apr 13, 2023 at 8:08
  • $\begingroup$ So the gradient of the loss function we are fitting isn't an infinite-dimensional functional derivative, it's just the gradient of the loss function with respect to the prediction values, evaluated at the current prediction. Whereas the standard approach is to find the gradient of the loss function with respect to the model parameters $\theta$, here we are finding the gradient of the loss function with respect to the $N$ predictions ($N$ data points). It looks like an infinite-dimensional functional derivative, but in practice, it's finite-dimensional with as many terms as predictions. $\endgroup$
    – JoseOrtiz3
    Apr 13, 2023 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.