Нужна помощь в понимании приблизительного предложения точек разделения xgboost

фон:

в xgboost в итерационным подгоняет дерево ф т по всему п примерам , которые сводят к минимуму следующей цели:$t$$f_t$$n$

$$\sum_{i=1}^n[g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)]$$

где сначала порядок и производные второго порядка над нашей предыдущей лучшей оценки у (от итерации т - 1 ):$g_i, h_i$$\hat{y}$$t-1$

• $g_i=d_{\hat{y}}l(y_i, \hat{y})$
• $h_i=d^2_{\hat{y}}l(y_i, \hat{y})$

и наша функция потерь.$l$

---

Вопрос (наконец):

При построении и рассмотрении конкретной функции k в определенном разбиении они используют следующую эвристику для оценки только некоторых кандидатов разделения: они сортируют все примеры по их x k , передают отсортированный список и суммируют свою вторую производную h i . Они считают разделенного кандидата только тогда, когда сумма меняется больше чем на ϵ . Почему это???$f_t$$k$$x_k$$h_i$$\epsilon$

Объяснение, которое они дают, ускользает от меня:

Они утверждают, что мы можем переписать предыдущее уравнение следующим образом:

$$\sum_{i=1}^n\frac{1}{2}h_i[f_t(x_i) - g_i/h_i]^2 + constant$$

и я не могу следовать алгебре - вы можете показать, почему она равна?

И затем они утверждают, что «это точно взвешенный квадрат с потерями с метками и весами h i » - с этим соглашением я согласен, но я не понимаю, как это связано с алгоритмом разделения кандидатов, который они используют. ..$gi/hi$$h_i$

Спасибо и извините, если это слишком долго для этого форума.

Я не буду вдаваться в подробности, но следующее должно помочь вам понять идею.

$\{x_1, \cdots, x_{100}\}$$10$$\{x_{10}, x_{20}, \cdots, x_{90}\}$$\epsilon$$\sim \epsilon N$$\epsilon = 0.01$$\sim 100$$\{1\%, 2\%, ..., 99\%\}$$\epsilon$$\epsilon$

$10$$10\%$$10\%$

Просто добавив алгебраическую часть к ответу @Winks:

Второе уравнение должно иметь обратный знак, как в:

$$\sum_{i=1}^n\frac{1}{2}h_i[f_t(x_i) - (-g_i/h_i)]^2 + constant = \sum_{i=1}^n\frac{1}{2}h_i[f_t^2(x_i) + 2\frac{f_t(x_i)g_i}{h_i} + (g_i/h_i)^2] = \sum_{i=1}^n[g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i) + \frac{gi^2}{2h_i}]$$

$g_i$$h_i$$f_t$

$-gi/hi$$h_i$

Авторы благодарны Ярону и Ави из моей команды за то, что они объяснили мне это.

И затем они утверждают, что «это точно взвешенный квадрат с потерями с метками gi / higi / hi и weights hihi» - с этим соглашением я согласен, но я не понимаю, как это связано с алгоритмом разделения кандидатов, который они используют .. ,

1. $w$$t-t_h$$w* = -gi/hi$$(ft - -(gi/hi))^2$

2. $w*$$-avg(gi)/const$$-sigma(gi)/sigma(hi)$$w*$$hi$$gi$$w*$$hi$

$hi$