Potrzebujesz pomocy w zrozumieniu przybliżonej propozycji punktów podziału xgboost

tło:

w xgboost z $t$ próbach iteracji w celu dopasowania do drzewa $f_t$ w stosunku do wszystkich $n$ przykładach minimalizuje obiektywnego:

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

gdzie są pochodnymi pierwszego i drugiego rzędu w stosunku do naszego poprzedniego najlepszego oszacowania (z iteracji ):r T - $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})$

i $l$ jest naszą funkcją utraty.

---

Pytanie (wreszcie):

Przy budowie i rozważa Specyfiką k w określonym ułamku, używają następujące heurystyki do oceny tylko niektóre kandydatów dzielone: ich do sortowania wszystkie przykłady przez ich x k , przejść przez listę posortowaną i podsumować ich druga pochodna h I . Rozważają podzielonego kandydata tylko wtedy, gdy suma zmienia się więcej niż ϵ . Dlaczego???$f_t$$k$$x_k$$h_i$$\epsilon$

Ustępują mi wyjaśnienia:

Twierdzą, że możemy przepisać poprzednie równanie w następujący sposób:

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

a ja nie podążam za algebrą - czy możesz pokazać, dlaczego jest równa?

A potem twierdzą, że „to jest dokładnie ważone squared stratę z etykietami i ciężary h ja ” - oświadczenie zgadzam się, ale nie rozumiem, jak to się odnosi do algorytmu Podział kandydata, z których korzystają. ..$gi/hi$$h_i$

Dzięki i przepraszam, jeśli to za długo na tym forum.

Nie będę wdawał się w szczegóły, ale poniższe powinny pomóc ci zrozumieć ten pomysł.

Używają Quantiles (Wikipedia), aby określić, gdzie podzielić. Jeśli masz 100 możliwych punktów podziału, $\{x_1, \cdots, x_{100}\}$ (posortowane), możesz wypróbować kwantylowe punkty podziału { x 10 , x 20 , ⋯ , x 90 } i mieć już dobre przybliżenie. Tak właśnie działa parametr ϵ . Rozważają punkt podziału, gdy pod nim znajduje się ∼ ϵ N więcej punktów niż ostatni punkt podziału. Jeśli ϵ = $10$$\{x_{10}, x_{20}, \cdots, x_{90}\}$$\epsilon$$\sim \epsilon N$$\epsilon = 0.01$Będziesz skończyć z punktów podziału, jest większy niż { 1 % , 2 % , . . . , 99 % } innych punktów. Nie rozważają nowego podziału, gdy „suma zmienia się bardziej niż ϵ ”, ale gdy liczba punktów pod bieżącym punktem jest większa o ϵ niż ostatni.$\sim 100$$\{1\%, 2\%, ..., 99\%\}$$\epsilon$$\epsilon$

Teraz, jeśli masz wiele ciągłych punktów, które są już dobrze sklasyfikowane, dzielenie się nimi może być bezużyteczne. Chcesz podzielić części zestawu danych, które są bardzo błędne, te trudne do nauczenia. Aby to zrobić, używają ważonych kwantyli. Tutaj odgrywają rolę wagi. Pierwszy kwantyl nie będzie pierwszym punktem, który jest większy niż 10 % punktów, ale pierwszym punktem, który jest większy niż 10 % wag.$10$$10\%$$10\%$

Wystarczy dodać część algebraiczną do odpowiedzi @Winks:

Drugie równanie powinno mieć odwrócony znak, jak w:

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

Podziękowania należą się Yaronowi i Avi z mojego zespołu za wyjaśnienie mi tego.

Następnie twierdzą, że „jest to dokładnie ważona kwadratowa strata z etykietami gi / higi / hi i waży hihi” - stwierdzenie, z którym się zgadzam, ale nie rozumiem, w jaki sposób odnosi się do algorytmu podzielonego kandydata, którego używają… .

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$

Myślę, że to wyjaśnia, dlaczego to działa, ponieważ jest ważone $hi$