4
$\begingroup$

I need some help please with the derivation of xgboost objective function. I am following this online tutorial (Math behind GBM and XGBoost)

How do you go from here $$ loss = \sum_{i=1}^{n} \left( g_i \sum_{j=1}^{T} b_{jm}I_{Rjm}(x_i) + \frac{1}{2} k_i \left( \sum_{j=1}^{T} b_{jm}I_{Rjm}(x_i) \right)^2 \right) + \gamma T + \frac{ \lambda }{2} \sum_{j=1}^{T} b_{jm}^2 $$

to here $$ loss = \sum_{j=1}^{T} \left( \sum_{i\in I_{jm}} g_i \right) b_{jm} + \frac{1}{2} \left( \sum_{i\in I_{jm}} (k_i + \lambda) \right) b_{jm} + \gamma T $$

where as I understand, $I_j$ is the set of all training instances that are mapped to leaf $j$

I tried swapping the sums; however, since the second sum is squared I was not sure if they can be swapped.

Example, this is true

$$ \sum_{i=1}^{n} \sum_{j=1}^{m} x_{ij} = \sum_{j=1}^{m} \sum_{i=1}^{n} x_{ij} $$

but not sure if this can be swapped

$$ \sum_{i=1}^{n} \left(\sum_{j=1}^{m} x_{ij} \right)^2 $$

Also, it may be the case that I don't fully understand the $I_{jm}$ function and how it works.

Thank you

$\endgroup$
0
$\begingroup$

The quick answers to your question are:

  1. You are absolutely right: it is not generally valid to swap the order of summation when the interior sum is squared. It's not even true when $n=1$ and $m=2$:

$$ \sum_{i=1}^{1} \left(\sum_{j=1}^{2} x_{ij} \right)^2 = (x_{11} + x_{12})^2 = x_{11}^2 + 2x_{11}x_{12} + x_{12}^2 $$

$$ \sum_{j=1}^{2} \left(\sum_{i=1}^{1} x_{ij} \right)^2 = x_{11}^2 + x_{12}^2 $$

  1. The blog post has a few mistakes in it, and you would be better working through the (quite nicely written and much better type-scripted) introduction in the XGBoost docs.
| 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.