xgboost tayler expansion detail [duplicate]

Question

This is the objective function for Xgboost.
I have no idea where $g_{i}$ and $h_{i}$ came from
is some one explain how this two terms came form?
or direct me to the related tutorial page then I will search for it

Answer 1

First of all let us make it clear what the setup looks like. The ingredients are the following: Assume we are talking about regression (i.e. 'true' answers are elements of the set $\mathbb{R}$) and

• we have a training set consisting of $N$ data points as follows...
  • there are feature vectors $x_1, ..., x_N$ (i.e. each $x_i$ is probably again a vector $x_i = (x_{i,1}, ..., x_{i,d})$ but this is not important right now, it is just notation)
  • there are true answers $y_1, ..., y_N$
• additionally, there are (current) predictions $\hat{y}_1, ..., \hat{y}_N$
• we also have a loss function $l : \mathbb{R} \times \mathbb{R} \to \mathbb{R}_{>0}$

given a 'true' answer $y_i \in \mathbb{R}$ and a prediction $\hat{y}_i \in \mathbb{R}$, the loss function is applied like $l(y_i, \hat{y}_i)$ tells us how far the prediction $\hat{y}_i$ is away from the true answer $y_i$.

In the case above,

$$l(y_i, \hat{y}_i) = (y_i - \hat{y}_i)^2$$

The objective function 'Obj' that they present in the docs is rather confusing and complicated (I agree) because it does not depend on one single parameter but rather on $y, \hat{y}$, implicitly also on $x$, it takes the complicatedness of the model into account already ($\Omega$-term [which might not even be differentiable in any sense]) and so forth. So lets first simplify.

The training set is fixed so we cannot change that (i.e. $N$, $x$ and $y$ are actually not parameters but fixed!). The only thing we can play around with is $\hat{y}$: by changing the model slightly we move the prediction vector $\hat{y} = (\hat{y}_1, ..., \hat{y}_N)$ around in the space $\mathbb{R}^N$ and we can check whether it gets better or worse. Formalizing this means that we optimize the function

$$f : \mathbb{R}^N \to \mathbb{R}, f(\hat{y}) = \sum_{i=1}^{N} l(y_i, \hat{y}_i)$$

This makes sense: it calculates how far the predictions are away from the actual answers. Let us say that we have a prediction $\hat{y}$ already and that we want to produce a new, 'better' prediction $\hat{y}'$ from it and we construct $\hat{y}'$ from $\hat{y}$ by adding a vector $z$ (i.e. $z=\hat{y}'-\hat{y}$). We then wonder:

How do we need to construct $z$ such that $f(\hat{y} + z)$ is much smaller than $f(\hat{y})$?

The mathematics behind derivatives tells us that we form the so-called gradient $\nabla f$ of the function $f$ at $\hat{y}$ and within a (potentially VERY) small $\epsilon$, if we put $z = -\epsilon * \nabla f(\hat{y})$ then actually, $f(\hat{y} + z)$ is smaller than $f(\hat{y})$.

Remark: formally, the assertion is that (locally), the gradient points into the direction of the strongest ascend of the function so that '-gradient' points (locally) into the direction of the strongest descend of the function and the assumption is that $\hat{y}$ has not yet been a minimum.

The whole idea of gradient boosting now is: Given that we have computed $t$ trees $T_1, ..., T_t$ and formed 'current' predictions $\hat{y}_i = G_t(x_i) = \sum_{i=1}^t T_t(x_i)$, form the next tree $T_{t+1}$ so that it resembles that mathematical process, i.e. train the next tree to give $-\nabla f(\hat{y}_i)$ as an answer to $x_i$ so that $G_{t+1}(x_i) = G_t(x_i) + T_{t+1}(x_i) \approx \hat{y} -\nabla f(\hat{y}_i) = \hat{y} + z$ and the value of the function $f$ on that is hopefully much smaller than before.

In the case above, $g_i = \partial_{\hat{y}} l(y, \hat{y})$ is really just the $i$-th component of the thing we need: $\nabla f(\hat{y})$ and $h$ vanishes because differentiating a quadratic function two times gives zero. So first observation: the term above gives exactly what we want from a mathematical point of view for the setup above.

Why the hell do they formulate it in such a complicated way then and why do we even need the Tailor expansion when we can simply compute $g$ and $h$???

Answer:

1) Because due to different restrictions the loss function may be much more complicated than just $(y_i - \hat{y}_i)^2$. For example: in the case of classification it is the cross entropy function and this is harder to differentiate (but it is still possible). However, there may be situations in which the user wants to specify a custom loss function that XGBoost did not know about before... for example, we could use $l(y, y') = (2y^2 - 4{y'}^6)^8$ or even worse. Now XGBoost would need a whole mathematical library in order to implement all these custom functions (more precisely, their derivatives) in their C code. This would be extremely complicated for the user as well as for the XGBoost developers. Instead they are not at all using the derivative but let the user specify the derivative instead. That it what they need the $g$ for.

2) Ok, now that we know why they need the $g$, why do they need the $h$? The $h$ did not add anything new in the case above because the loss function was so simple. In the case $l(y, y') = (2y^2 - 4{y'}^6)^8$ the second derivative does indeed not vanish and makes the process even more complicated. Why? Well, the theorem above (gradient points into the direction of steepest ascend) can be extended to more than one derivative and this is basically what Tailor expansion is about: The more derivatives you know about the function, the better you can approximate it and the better and more informed you can make decisions about in which direction to go in order to make the value of the function smaller.

However, this is only heuristics: The theorem of Tailor states that there is a small area around the point $\hat{y}$ such that the expansion is valid (and we know an even better direction $z$ to go to instead of just 'minus the first derivative') but this could also make things worse: If the area for the first derivative is relatively large but due to the fact that the second derivative is very complicated, the area shrinks a lot when considering the second derivative we are basically introducing information that gives us a possible worse direction than just the first derivative...

Coming back to XGB: they do not exactly train the new tree $T_{t+1}$ with exactly this data ($x_i$ should give $-\nabla f(\hat{y}_i)$ as an answer) but in the same step (i.e. while training the tree for this temporary new dataset) they also use some mechanisms in order not to let $\Omega$ grow too much but you can find an exact description of that (pre-pruning, regularization of the structure, ...) in the docs so that they not only optimize $f$ but $f + \Omega(T_{t+1})$ (which is their 'Obj')

Again: As we have no mathematically precise description of how different actions in changing the model influence this term $\Omega$, we cannot really optimize 'Obj' using precise mathematics but we can use precise mathematics in order to optimize $f$ and then apply this heuristics of regularization in order to 'hopefully' also optimize 'Obj'...