Na przykład, ma funkcję celu modelu XGBoost w sprawie $t$ „tą iterację procedury:

$$\mathcal{L}^{(t)}=\sum_{i=1}^n\ell(y_i,\hat{y}_i^{(t-1)}+f_t(\mathbf{x}_i))+\Omega(f_t)$$

gdzie $\ell$ jest utrata funkcji, $f_t$ jest $t$ -tym wyjście drzewa i $\Omega$ jest regularyzacji. Jednym z (wielu) kluczowych kroków do szybkiego obliczenia jest przybliżenie:

$$\mathcal{L}^{(t)}\approx \sum_{i=1}^n\ell(y_i,\hat{y}_i^{(t-1)})+g_tf_t(\mathbf{x}_i)+\frac{1}{2}h_if_t^2(\mathbf{x}_i)+\Omega(f_t),$$

w którym $g_i$ i $h_i$ są to pierwsze i drugie pochodne funkcji strat.

Pytam o przekonujące argumenty, które mają na celu wyjaśnienie, dlaczego powyższe przybliżenie działa:

1) Jak XGBoost z powyższym przybliżeniem wypada w porównaniu z XGBoost z pełną funkcją celu? Jakie potencjalnie interesujące zachowanie wyższego rzędu zostało utracone w przybliżeniu?

2) Trudno jest wizualizować (i zależy od funkcji straty), ale jeśli funkcja straty ma duży składnik sześcienny, przybliżenie prawdopodobnie się nie powiedzie. W jaki sposób nie powoduje to problemów dla XGBoost?

To bardzo interesujące pytanie. Aby w pełni zrozumieć, co się dzieje, musiałem przejść przez to, co XGBoost próbuje zrobić i jakie inne metody mieliśmy w naszym zestawie narzędzi, aby sobie z tym poradzić. Moja odpowiedź dotyczy tradycyjnych metod i tego, jak / dlaczego XGBoost jest ulepszeniem. Jeśli chcesz tylko punktorów, na końcu jest podsumowanie.

Tradycyjne wzmocnienie gradientu

Rozważ tradycyjny algorytm zwiększania gradientu (Wikipedia) :

• Oblicz model podstawowy $H_0$
• Dla $m \leftarrow 1:M$
  • Oblicz pseudo-reszty $r_{im} = -\frac{\partial \ell(y_i, H_{m-1}(x_i))}{\partial H_{m-1}(x_i)}$
  • Dopasuj podstawowego ucznia $h_m(x)$ do pseudo-reszty
  • $\gamma$$\gamma = \arg \min_\gamma \sum_{i=1}^N \ell(y_i, H_{m-1}(x_i) + \gamma h_m(x_i))$
  • Zaktualizuj model .$H_m(x) = H_{m-1}(x) + \gamma h_m(x)$
• Otrzymasz swój wzmocniony model .$H_M(x)$

Przybliżenie funkcji jest ważne dla następnej części,

Dopasuj podstawowego ucznia do pseudo-reszty.$h_m(x)$

Wyobraź sobie, jak naiwnie zbudować Algorytm wzmocnienia gradientu. Powyższy algorytm zbudowałbyś przy użyciu istniejących drzew regresji jako słabych uczniów. Załóżmy, że nie możesz poprawiać istniejącej implementacji słabych uczniów. W Matlabie domyślnym kryterium podziału jest średni błąd kwadratu. To samo dotyczy nauki scikit .

Próbujesz znaleźć najlepszy model który minimalizuje koszt . Aby to zrobić, dopasowujesz prosty model regresji do reszt za pomocą MSE jako funkcji celu. Zauważ, że nie minimalizujesz bezpośrednio tego, co chcesz, ale używasz do tego resztek i MSE. Złe jest to, że niekoniecznie daje to optymalne rozwiązanie. Najlepsze jest to, że działa.$h_m(x)$$\ell(y_i, H_{m-1}(x_i) + h_m(x_i))$

Tradycyjne zejście gradientowe

Jest to analogiczne do tradycyjnego spadku gradientu (Wikipedia) , w którym próbujesz zminimalizować funkcję kosztu , postępując zgodnie z (ujemnym z) gradientem funkcji, na każdym kroku.$f(x)$$-\nabla f(x)$

$$x^{(i+1)} = x^{(i)} - \nabla f(x^{(i)})$$

Nie pozwala ci znaleźć dokładnego minimum po jednym kroku, ale każdy krok przybliża cię do minimum (jeśli funkcja jest wypukła). Jest to przybliżenie, ale działa bardzo dobrze i jest to algorytm, którego tradycyjnie używamy na przykład do regresji logistycznej.

Interludium

W tym momencie należy zrozumieć, że ogólny algorytm zwiększania gradientu nie oblicza funkcji kosztu dla każdego możliwego podziału, wykorzystuje funkcję kosztu słabego ucznia regresji, aby dopasować do reszt.$\ell$

Twoje pytanie wydaje się sugerować, że „prawdziwy XGBoost” powinien obliczyć funkcję kosztu dla każdego podziału i że „przybliżony XGBoost” używa heurystyki do przybliżenia go. Możesz to zobaczyć w ten sposób, ale historycznie mieliśmy ogólny algorytm zwiększania gradientu, który nie wykorzystuje informacji o funkcji kosztu, z wyjątkiem pochodnej w bieżącym punkcie. XGBoost jest rozszerzeniem do Gradient Boosting, które stara się być mądrzejszym w kwestii uprawy słabych drzew regresji, wykorzystując dokładniejsze przybliżenie niż tylko gradient.

Inne sposoby wyboru najlepszego modelu$h_m(x)$

Jeśli spojrzymy na AdaBoost jako szczególny przypadek wzmocnienia gradientu, nie wybiera on regresorów, ale klasyfikatorów jako słabych uczniów. Jeśli ustawimy , sposób AdaBoost wybiera najlepszy model, znajdując$h_m(x) \in \{-1,1\}$

$$h_m = \arg \max_{h_m} \sum_{i=1}^N w_i h_m(x_i)$$

gdzie są resztkami ( źródło, zaczyna się od slajdu 20 ). Powodem użycia tej funkcji celu jest to, że jeśli i idą w tym samym kierunku / mają ten sam znak, punkt przesuwa się we właściwym kierunku, a Ty próbujesz zmaksymalizować maksymalną ilość ruchu w właściwy kierunek.$w_i$w i h m ( x i )$w_i$$h_m(x_i)$

Ale jeszcze raz nie mierzy to bezpośrednio, który minimalizuje . Mierzy to, jak dobry jest ruch , w odniesieniu do ogólnego kierunku, w którym powinieneś zmierzać, mierzony za pomocą reszt , które są również przybliżeniem. Resztki mówią ci, w którym kierunku powinieneś poruszać się po ich znaku, a mniej więcej o ich wielkości, ale nie mówią ci dokładnie, gdzie powinieneś przestać.$h_m$$\ell(y_i, H_{m-1}(x_i) + h_m(x_i))$$h_m$$w_i$

Lepsze zejście gradientu

Kolejne trzy przykłady nie są niezbędne do wyjaśnienia i są tutaj tylko po to, aby przedstawić kilka sposobów na lepsze niż zejście gradientu waniliowego, aby poprzeć ideę, że to, co robi XGBoost, jest po prostu innym sposobem na poprawienie spadku gradientu. W tradycyjnym ustawieniu opadania gradientu, próbując zminimalizować , można zrobić coś lepszego niż tylko śledzenie gradientu. Zaproponowano wiele rozszerzeń (Wikipedia) . Oto niektóre z nich, aby pokazać, że można zrobić lepiej, biorąc pod uwagę dłuższy czas obliczeń lub więcej właściwości funkcji .$f(x)$f$f$

• Wyszukiwanie linii / Cofanie: po obliczeniu gradientu, po obliczeniu gradientu , następnym punktem powinien być$-\nabla f(x^{(i)})$

  $$x^{(i+1)} = x^{(i)} - \nabla f(x^{(i)})$$

  Ale gradient podaje tylko kierunek, w którym należy się poruszać, nie tak naprawdę „o ile”, więc można zastosować inną procedurę, aby znaleźć najlepsze takie, że$c > 0$

  $$x_c^{(i+1)} = x^{(i)} - c \nabla f(x^{(i)})$$

  minimalizuje funkcję kosztów. Dokonuje się tego, oceniając dla jakiegoś , a ponieważ funkcja powinna być wypukła, stosunkowo łatwo jest to zrobić za pomocą przeszukiwania linii (Wikipedia) lub przeszukiwania linii wyszukiwania (Wikipedia) . Tutaj głównym kosztem jest ocena . To rozszerzenie działa najlepiej, jeśli jest łatwe do obliczenia. Zauważ, że ogólny algorytm zwiększania gradientu wykorzystuje wyszukiwanie linii, jak pokazano na początku mojej odpowiedzi.$f(x_c^{(i+1)})$$c$$f$f ( x ) f$f(x)$$f$

• Szybka metoda gradientu proksymalnego: Jeśli funkcja minimalizacji jest silnie wypukła, a jej gradient jest gładki ( Lipschitz (Wikipedia) ), istnieje pewna sztuczka przy użyciu tych właściwości, które przyspieszają konwergencję.

• Stochastyczne zejście gradientu i metoda pędu: W stochastycznym spadku gradientu nie oceniasz gradientu we wszystkich punktach, ale tylko w podzbiorze tych punktów. Zrób krok, a następnie oblicz gradient na innej partii i kontynuuj. Można zastosować Stochastic Descent Gradient, ponieważ obliczenia dla wszystkich punktów są bardzo drogie, a może wszystkie te punkty nawet nie mieszczą się w pamięci. Pozwala to robić więcej kroków, szybciej, ale mniej dokładnie.

  W takim przypadku kierunek gradientu może się zmieniać w zależności od tego, które punkty są próbkowane. Aby przeciwdziałać temu efektowi, metody pędu utrzymują średnią ruchomą kierunku dla każdego wymiaru, zmniejszając wariancję w każdym ruchu.

Najistotniejszym rozszerzeniem opadania gradientu w naszej dyskusji na temat XGBoost jest metoda Newtona (Wikipedia) . Zamiast po prostu obliczać gradient i podążać za nim, wykorzystuje pochodną drugiego rzędu, aby zebrać więcej informacji o kierunku, w którym powinien zmierzać. Jeśli używamy opadania gradientu, mamy to przy każdej iteracji, aktualizujemy nasz punkt w następujący sposób,$x^{(i)}$

$$x^{(i+1)} = x^{(i)} - \nabla f(x^{(i)})$$

A ponieważ gradient wskazuje kierunek najwyższego wzrostu , jego ujemne punkty w kierunku najwyższego spadku, i mamy nadzieję, że . Może się to nie udać, ponieważ możemy posunąć się zbyt daleko w kierunku gradientu (stąd rozszerzenie wyszukiwania linii), ale jest to dobre przybliżenie. W metodzie Newtona aktualizujemy w następujący sposób,$\nabla f(x^{(i)})$$f$$f(x^{(i+1)}) < f(x^{(i)})$$x^{(i)}$

$$x^{(i+1)} = x^{(i)} - \frac{\nabla f(x^{(i)})}{\text{Hess} f(x^{(i)})}$$

Gdzie to hesian w . Ta aktualizacja uwzględnia informacje drugiego rzędu, więc kierunek nie jest już kierunkiem największego spadku, ale powinien wskazywać bardziej precyzyjnie w kierunku tak aby (lub punkt, w którym jest minimalne, jeśli nie ma zera). Jeśli jest wielomianem drugiego rzędu, to metoda Newtona w połączeniu z wyszukiwaniem linii powinna być w stanie znaleźć minimum w jednym kroku.$\text{Hess} f(x)$$f$$x$$x^{(i+1)}$$f(x^{(i+1)}) = 0$$f$$f$

Metoda Newtona kontrastuje ze stochastycznym spadkiem gradientu. W Stochastic Gradient Descent, używamy mniejszej ilości punktu, aby poświęcić mniej czasu na obliczenie kierunku, w którym powinniśmy iść, aby zrobić więcej z nich, w nadziei, że pójdziemy tam szybciej. W metodzie Newtona poświęcamy więcej czasu na obliczenie kierunku, w którym chcemy iść, w nadziei, że musimy podjąć mniej kroków, aby się tam dostać.

Powód, dla którego metoda Newtona działa, jest taki sam, jak w przypadku przybliżenia XGBoost, i opiera się na ekspansji Taylora (Wikipedia) i twierdzeniu Taylora (Wikipedia) . Rozwinięcie Taylora (lub szereg Taylora) funkcji w punkcie wynosi$f(x + a)$

$$f(x) + \frac{\partial f(x)}{\partial x}a + \frac{1}{2}\frac{\partial^2 f(x)}{\partial x^2}a^2 + \cdots = \sum_{n=0} ^\infty \frac{1}{n!} \frac{\partial^n f(x)}{\partial x^n}a^n.$$

Zwróć uwagę na podobieństwo między tym wyrażeniem a przybliżeniem używanym przez XGBoost. Twierdzenie Taylora stwierdza, że ​​jeśli zatrzymasz ekspansję w kolejności , to błąd lub różnica między a , co najwyżej , gdzie jest funkcją z właściwością dobrze, że dojdzie do zera dąży do zera.$k$$f(x+a)$$\sum_{n=0}^k \frac{1}{n!}\frac{\partial^n f(x)}{\partial x^n}a^n$$h_k(x) a^k$$h_k$$a$

Jeśli chcesz mieć wizualizację tego, jak dobrze przybliża niektóre funkcje, zajrzyj na strony wikipedii, mają one wykresy przybliżające funkcje niepolomianowe, takie jak , .$e^x$$\log(x)$

Należy zauważyć, że aproksymacja działa bardzo dobrze, jeśli chcesz obliczyć wartość w sąsiedztwie , to znaczy dla bardzo małych zmian . Właśnie to chcemy robić w trybie wzmocnienia. Oczywiście chcielibyśmy znaleźć drzewo, które wprowadza największą zmianę. Jeśli budowani przez nas słabi uczniowie są bardzo dobrzy i chcą dokonać bardzo dużej zmiany, możemy dowolnie to utrudnić, stosując jedynie lub$f$$x$$a$$0.1$$0.01$jego efektu. Jest to wielkość kroku lub szybkość uczenia się spadku gradientu. Jest to do przyjęcia, ponieważ jeśli nasi słabi uczniowie dostają bardzo dobre rozwiązania, oznacza to, że albo problem jest łatwy, w którym to przypadku i tak skończymy z dobrym rozwiązaniem, albo przepracowujemy się, więc pójdziemy trochę lub bardzo wiele w tym złym kierunku nie zmienia podstawowego problemu.

Co robi XGBoost i dlaczego działa?

XGBoost jest algorytmem Gradient Boosting, który buduje drzewa regresji jako słabe osoby uczące się. Tradycyjny algorytm wzmocnienia gradientu jest bardzo podobny do spadku gradientu z wyszukiwaniem linii, gdzie kierunek, w którym należy podążać, jest wyznaczany przez dostępnych słabych uczniów. Naiwne wdrożenie Gradient Boosting wykorzystałoby funkcję kosztu słabego ucznia, aby dopasować go do pozostałych. Jest to serwer proxy, aby zminimalizować koszt nowego modelu, którego obliczenie jest kosztowne. XGBoost buduje niestandardową funkcję kosztu, aby dopasować ją do drzew, używając serii drugiego rzędu Taylora jako przybliżenia rzeczywistej funkcji kosztu, dzięki czemu można mieć większą pewność, że drzewo, które wybiera, jest dobre. Pod tym względem, i dla uproszczenia, XGBoost ma na celu zwiększenie gradientu, czym jest metoda Newtona dla spadku gradientu.

Dlaczego tak to zbudowali

Twoje pytanie, dlaczego użycie tego przybliżenia sprowadza się do kompromisu koszt / wydajność. Ta funkcja kosztów służy do porównywania potencjalnych podziałów dla drzew regresji, więc jeśli nasze punkty mają powiedzmy 50 cech, ze średnio 10 różnymi wartościami, każdy węzeł ma 500 potencjalnych podziałów, więc 500 oceny funkcji. Jeśli upuścisz funkcję ciągłą, liczba podziałów eksploduje, a ocena podziału jest nazywana coraz większą (XGBoost ma inną sztuczkę radzenia sobie z ciągłymi funkcjami, ale jest to poza zakresem). Ponieważ algorytm spędza większość czasu na ocenie podziałów, sposobem na przyspieszenie algorytmu jest przyspieszenie oceny drzewa.

Jeśli oceniłeś drzewo za pomocą funkcji pełnego kosztu, , jest to nowe obliczenie dla każdego nowego podziału. Aby przeprowadzić optymalizację w obliczeniach funkcji kosztu, trzeba mieć informacje o funkcji kosztu, która stanowi sedno funkcji Gradient Boost: powinna działać dla każdej funkcji kosztu.$\ell$

Przybliżenie drugiego rzędu jest przyjemne obliczeniowo, ponieważ większość terminów jest taka sama w danej iteracji. Dla danej iteracji większość wyrażeń można obliczyć jeden raz i użyć ponownie jako stałej dla wszystkich podziałów:

$$\mathcal{L}^{(t)}\approx \sum_{i=1}^n \underbrace{\ell(y_i,\hat{y}_i^{(t-1)})}_{\text{constant}}+\underbrace{g_i}_{\text{constant}}f_t(\mathbf{x}_i)+\frac{1}{2}\underbrace{h_i}_{\text{constant}}f_t^2(\mathbf{x}_i)+\Omega(f_t),$$

Tak więc jedyne, co musisz obliczyć, to i , a wtedy pozostały głównie dodatki i niektóre multiplikacje. Co więcej, jeśli spojrzysz na artykuł XGBoost (arxiv) , zobaczysz, że wykorzystują fakt, że budują drzewo, aby jeszcze bardziej uprościć wyrażenie aż do szeregu podsumowań indeksów, co jest bardzo, bardzo szybkie.$f_t(x_i)$$\Omega(f_t)$

Podsumowanie

Możesz zobaczyć XGBoost (z przybliżeniem) jako regresję z dokładnego rozwiązania, przybliżenie „prawdziwego XGBoost”, z dokładną oceną. Ale ponieważ dokładna ocena jest tak kosztowna, innym sposobem, aby to zobaczyć, jest to, że w przypadku ogromnych zestawów danych przybliżenie jest wszystkim, co możemy realistycznie zrobić, i to przybliżenie jest dokładniejsze niż przybliżenie pierwszego rzędu, które zrobiłby algorytm „naiwnego” zwiększania gradientu .

Przybliżenie w użyciu jest podobne do Metody Newtona i jest uzasadnione przez Taylor Series (Wikipedia) i Taylor Theorem (Wikipedia) .

Informacje o wyższym zamówieniu rzeczywiście nie są w pełni wykorzystywane, ale nie są konieczne, ponieważ chcemy dobrego przybliżenia w pobliżu naszego punktu początkowego .

Aby uzyskać wizualizację, sprawdź stronę Wikipedii Taylora Series / Taylora Theorem , Khan Academy on Taylor Series aproksymacji lub stronę MathDemo na temat aproksymacji wielomianowej niepolomianów