3
$\begingroup$

I am following the paper on xgboost and got stuck at equation 6 ($3^{rd}$ page), where the authors say that for a given tree, "we can compute the optimal weight $w_j^*$ of leaf $j$ by" \begin{split}w_j^\ast = -\frac{G_j}{H_j+\lambda}\end{split} Here, $G_j$ and $H_j$ are the first and second derivatives of a loss function $l$ of the previous ($t-1$) prediction for the set of examples ($I_j$) ending in the given leaf $j$: \begin{split}G_i &= \sum_{i \in I_j}\partial_{\hat{y}_i^{(t-1)}} l(y_i, \hat{y}_i^{(t-1)})\\ h_i &= \sum_{i \in I_j}\partial_{\hat{y}_i^{(t-1)}}^2 l(y_i, \hat{y}_i^{(t-1)}) \end{split}

My question really is, what makes the weight defined in such a way optimal? Does it follow in some obvious way (since it is not explained in the paper) from the general definition of the loss function? \begin{split} \mathcal{L}^{(t)} = \sum_{j=1}^T [G_jw_j + \frac{1}{2}(H_j + \lambda)w_j^2] + \gamma T \end{split} Particularly, I am struggling with the $H_j$ in the denominator. The general gradient boosting algorithm is supposed to fit new functions to the gradient of the loss function, but the second derivative confuses me).

$\endgroup$
1
  • 1
    $\begingroup$ My guess is that it comes from one iteration of newtons method. $\endgroup$ Apr 28, 2017 at 14:28

1 Answer 1

2
$\begingroup$

Ok, this is embarrassing. The expression comes from minimizing the loss function analytically by taking the derivative of the relevant part and setting it to zero: \begin{split} (G_jw_j + \frac{1}{2}(H_j + \lambda)w_j^2)' &= 0 \\ G_j + (H_j + \lambda)w_j &= 0 \\ w_j &= -\frac{G_j}{H_j + \lambda} \end{split}

I still don't have good intuition for the denominator (it would be appreciated) but at least now I can see where it came from.

$\endgroup$
1
  • $\begingroup$ As Matthew Drury commented, the second derivative is similar to Newton's method which is an application of the Taylor expansion of the function to optimize. While not the same question as yours, you might like this question for more details. $\endgroup$
    – Winks
    May 3, 2017 at 9:28

Your Answer

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

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