5
$\begingroup$

The right-hand-side of Equation (3) in the XGBoost paper is $$\sum_{i=1}^n [g_i f_t(\mathbf{x}_i)+\frac{1}{2}h_if_t^2(\mathbf{x}_i)]+\Omega(f_t) \tag{3}$$

In the Section 3.3 "Weighted Quantile Sketch" it is stated this can be re-written (See just after equation (9)) $$ \sum_{i=1}^n \frac{1}{2} h_i \left( f_t(\mathbf{x}_i)- \frac{g_i}{h_i} \right)^2 + \Omega(f_t)+const $$ and I don't see how they get this.

Equation (3) obviously equals $$ \sum_{i=1}^n \frac{1}{2} h_i[2 \frac{g_i}{h_i} f_t(\mathbf{x}_i)+f_t^2(\mathbf{x}_i)]+\Omega(f_t) $$ Straightforward completing-the-square in this however yields a term $ (f_t(\mathbf{x}_i)+ \frac{g_i}{h_i})^2$ which doesn't agree with the re-written squared loss form.

To generate the squared loss and match the re-written form it seems one would get $$ \sum_{i=1}^n \frac{1}{2} h_i [ \left( f_t(\mathbf{x}_i)- \frac{g_i}{h_i} \right)^2 - \frac{{g_i}^2}{{h_i}^2} +4 \frac{g_i}{h_i}f_t ]+\Omega(f_t) $$ but this does not appear to add a constant due to the $f_t$.

How is this explained?

$\endgroup$

1 Answer 1

4
$\begingroup$

They most likely have a typo in the sign. It should be $\sum_i\frac12 h_i(f_t(x_i) +g_i/h_i)^2$ instead of $\sum_i\frac12 h_i(f_t(x_i) - g_i/h_i)^2$. It is a weighted square loss between $f_t(x_i)$ and labels $-g_i/h_i$.

You can see the negative sign in the solution of the optimization problem in (5).

In general the minimizer of $w \mapsto \sum_i \alpha_i (w - \beta_i)^2$ is $w^* = \sum_i \alpha_i \beta_i / (\sum_i \alpha_i)$.

In this problem, ignoring the regularizer, and assuming all the data are at the same leaf node, we are minimizing $w \mapsto \sum_i h_i(w + g_i/h_i)^2$ whose solution is $$ w^* = \frac{\sum_i h_i(-g_i/h_i)}{\sum_i h_i} = - \frac{\sum_i g_i}{\sum_i h_i}. $$

$\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.