1
$\begingroup$

As I understand the idea of gradient boosting in the (m+1)-th step we take the partial derivatives of the loss with respect to our new parameters $f^{[m]}(x^{(i)})$: $\tilde{y}^{(i)}=-\frac{\partial (\sum_{i=1}^nL(y^{(i)}, f^{[m]}(x^{(i)})))}{\partial f^{[m]}(x^{(i)})}$

and afterwards approximate this gradient step with a function $f_\theta$ from our hypothesis space that comes close to this gradient step, i.e. $\tilde{f}= \text{argmin}_{f \in H}\sum_{i=1}^n\left[\tilde{y}^{(i)}- f_{\theta}(x^{(i)}) \right] ^2$

we then multiply $\tilde{f}$ by some constant (depending on the learning rate) to get $f^{[m+1]}$

Now my question is about the scenario in which our loss is not $0.5(y-f(x))^2$ but some other arbitrary loss function $L^*$. Then $\tilde{y}^{(i)} \neq (y^{(i)}-f^{[m]}(x^{(i)}))$. According to algorithm 1 in the Friedman paper (page 1193) we would then still minimize $\sum_{i=1}^n\left[\tilde{y}^{(i)}- f_{\theta}(x^{(i)}) \right] ^2$ in order to get our new function.

My question is why we would not simply minimize $\sum_{i=1}^nL(y^{(i)}-f^{[m]}(x^{(i)}), f_\theta(x^{(i)}))$

Is this only because the approach as in algorithm 1 by Friedman is cheaper or is there another reason?

$\endgroup$
1
  • $\begingroup$ xgboost.readthedocs.io/en/latest/tutorials/model.html In the case of a classification problem, xgboost uses cross-entropy loss as a default. The derivation of how to update weights is a straightforward application of Taylor approximations; you can use the same strategy to optimize arbitrary loss functions. $\endgroup$ – Sycorax Oct 1 '19 at 11:31
1
$\begingroup$

First of all, I think your question should be formulated this way: \begin{equation} \sum_{i=1}^n L(\tilde{y}^{(i)},f_\theta(x^{(i)})) \end{equation}

Since the perk of Gradient Boosting Machines is precisely to allow the optimisation (by gradient descent) of any kind of Loss we decide to consider. Writing the formula your way, you're already committing yourself to the gradient of the Squared Loss, instead we want to minimise the gradient of our chosen Loss, i.e. $\tilde{y}^{(i)}$.

Said so, we shall consider now the problem at hand just as an optimisation problem: we just care about finding the best parameters $\hat{\theta}$ to achieve good properties (in an optimisation perspective) for the function $f_\theta(x^{(i)})$, across the $n$ units of the dataset.

The problem resembles very much the regression setting: on a $n$ points dataset, find the line which best approximates the points. Based on what desiderata we want to achieve, there are many options how to find the best parameters. In Statistics the usual solution is given by Ordinary Least Squares (OLS), i.e. minimising the squared difference between each point and its prediction obtained through the regression line.
Notice that the OLS minimisation technique is the same used in Gradient Boosting, on which you ask for clarification.

The reason why OLS is used in Regression is (paraphrasing Greene, W. H. (2003). Econometric analysis. Pearson Education India):

  1. it obtains unbiased estimates;
  2. across the unbiased estimators, it is the one with least variance.

Moving to the Gradient Boosting optimisation setting, the properties stated above may be translated into:

  1. When two points in the dataset have exactly the same values of the $X$ variables, but different $y$ values, gradient boosting should return the mean of the two $y$ as prediction for those $x$ values;
  2. Given the first property, we are guaranteed the prediction function is the one with minimum variance. Formally, we shall regard the variance as a dispersion measure on the overall dataset. Giving an intuitive interpretation: minimum variance is achieved when the prediction is the least distant from all the points in the dataset (This is neither formally rigorous nor accurate, it is just to give an intuition).
$\endgroup$
1
  • $\begingroup$ Regarding point 1 about gradient boosting: the squared loss is only used when fitting a tree to the negative gradient. This step is used only to find the final regions, not the leaf values. The resulting 'intermediate' leaf values are discarded. The final leaf values are found in the next step of the algorithm (line search) where the prediction is not necessarily the mean (e.g. it is the median for absolute loss). $\endgroup$ – PaulG Nov 22 '20 at 16:59

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.