3
$\begingroup$

Going through the documentation of XGBoost I came across the following two lines in the derivation of the objective function.

\begin{split}Obj^{(t)} &\approx \sum_{i=1}^n [g_i w_{q(x_i)} + \frac{1}{2} h_i w_{q(x_i)}^2] + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^T w_j^2\\ &= \sum^T_{j=1} [(\sum_{i\in I_j} g_i) w_j + \frac{1}{2} (\sum_{i\in I_j} h_i + \lambda) w_j^2 ] + \gamma T \end{split}

I can follow the documentation up this point. From my understanding the first equation above is an approximation of the original objective function, dervied from a second order Taylor Series expansion. Here $n$ is the number of training instances, $g_i $ and $h_i $ are first and second order derivatives of the loss function, $w_j $ is the score of the $j_{th} $ node in a decision tree, $\gamma $ and $\lambda $ are regularization weights, $q(x_i)$ is a function mapping the $i_{th} $ training instance to a leaf $j$, $I_j $ is the set of all training instances that are mapped to leaf $j$, and $T$ is the number of leaves in the decision.

My question is simple. Can anyone show me how the first equation equals the second. I apologize if there is something obvious here that I'm missing, but my algebra seems to be failing me in arriving at the second equation from the first. In the first equation, the last term is a summation over the squared scores of all leaves multiplied $\frac{1}{2} \lambda$. However in the second equation it appears that the regularization term would be
\begin{split} &= \sum^T_{j=1}[\frac{1}{2} \sum_{i\in I_j} \lambda w^2_j ] + \gamma T \\ &= \frac{1}{2} \lambda \sum^T_{j=1}|I_j| w^2_j +\gamma T \\ &\neq \gamma T + \frac{1}{2}\lambda \sum_{j=1}^T w_j^2 \end{split}

Where $|I_j|$ is the size of the set $I_j$. Please correct me if my math is wrong.

$\endgroup$
3
$\begingroup$

I see my error now. I was thinking that in the term \begin{split} &\frac{1}{2} (\sum_{i\in I_j} h_i + \lambda) w_j^2 \end{split}

That the summation was over both $h_i$ and $\lambda$. However the summation is just over $h_i$

| cite | improve this answer | |
$\endgroup$

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.