Wzmocnienie gradientu - Gradient boosting

Gradient pobudzanie jest uczenie maszynowe technika regresji , klasyfikacji i innych zadań, które produkuje modelu predykcji w postaci zespołu słabych modeli predykcyjnych, zwykle drzewa decyzyjne . Gdy drzewo decyzyjne jest słabym uczniem, powstały algorytm nazywa się drzewami wzmacnianymi gradientem, które zwykle przewyższają losowy las . Buduje model etapowo, tak jak robią to inne metody wzmacniające , i uogólnia je, umożliwiając optymalizację dowolnej różniczkowalnej funkcji straty .

Historia

Idea wzmacniania gradientu zrodziła się z obserwacji Leo Breimana, że wzmacnianie może być interpretowane jako algorytm optymalizacji odpowiedniej funkcji kosztu. Wyraźne algorytmy wzmacniania gradientem regresji zostały następnie opracowane przez Jerome'a H. Friedmana , jednocześnie z bardziej ogólną perspektywą funkcjonalnego wzmacniania gradientem Llew Masona, Jonathana Baxtera, Petera Bartletta i Marcusa Freana. W dwóch ostatnich artykułach przedstawiono pogląd na algorytmy wzmacniające jako iteracyjne algorytmy funkcjonalnego spadku gradientu . To znaczy algorytmy, które optymalizują funkcję kosztu w przestrzeni funkcji przez iteracyjne wybieranie funkcji (hipoteza słaba), która wskazuje w kierunku gradientu ujemnego. Ten funkcjonalny, gradientowy widok wzmacniania doprowadził do rozwoju algorytmów wzmacniania w wielu obszarach uczenia maszynowego i statystyki, poza regresją i klasyfikacją.

Nieformalne wprowadzenie

(Ta sekcja jest następująca po przedstawieniu zwiększania gradientu przez Li.)

Podobnie jak inne metody wzmacniania, wzmacnianie gradientem łączy słabych „uczących się” w jednego silnego ucznia w sposób iteracyjny. Najłatwiej to wyjaśnić w ustawieniu regresji najmniejszych kwadratów , gdzie celem jest „nauczenie” modelu przewidywania wartości formularza poprzez zminimalizowanie błędu średniokwadratowego , gdzie indeksy w pewnym zbiorze uczącym wielkości rzeczywistych wartości danych wyjściowych zmienna : ${\ Displaystyle F}$ ${\ Displaystyle {\ kapelusz {y}} = F (x)}$ ${\ Displaystyle {\ tfrac {1} {n}} \ suma _ {i} ({\ kapelusz {y}} _ {i}-y_ {i}) ^ {2}}$ $i$ ${\ Displaystyle n}$ $y$

${\ Displaystyle {\ kapelusz {y}} _ {i} =}$ przewidywana wartość ${\ Displaystyle F (x)}$
${\ Displaystyle y_ {i} =}$ obserwowana wartość
${\ Displaystyle n}$ liczba próbek w $y$

Rozważmy teraz algorytm zwiększania gradientu ze stopniami. Na każdym etapie ( ) wzmacniania gradientu, załóżmy jakiś niedoskonały model (dla low model ten może po prostu zwrócić , gdzie RHS jest średnią z ). Aby ulepszyć , nasz algorytm powinien dodać nowy estymator, . Zatem, ${\ Displaystyle M}$ ${\ Displaystyle m}$ $1\leq m\leq m$ ${\ Displaystyle F_ {m}}$ ${\ Displaystyle m}$ ${\ Displaystyle {\ kapelusz {y}} _ {i} = {\ bar {y}}}$ $y$ ${\ Displaystyle F_ {m}}$ ${\ Displaystyle h_ {m} (x)}$

{\ Displaystyle F_ {m + 1} (x) = F_ {m} (x) + h_ {m} (x) = Y}

lub równoważnie

{\ Displaystyle h_ {m} (x) = y-F_ {m} (x)}

.

Dlatego zwiększanie gradientu będzie pasować $h$ do rezydualnego . Podobnie jak w innych wariantach dopalających, każdy próbuje poprawić błędy poprzednika . Uogólnienie tego pomysłu na funkcje straty inne niż błąd kwadratowy oraz problemy klasyfikacji i rankingu wynika z obserwacji, że reszty dla danego modelu są proporcjonalnie równoważne do ujemnych gradientów funkcji straty średniokwadratowego błędu (MSE) (w odniesieniu do do ): ${\ Displaystyle y-F_ {m} (x)}$ ${\ Displaystyle F_ {m+1}}$ ${\ Displaystyle F_ {m}}$ ${\ Displaystyle h_ {m} (x)}$ ${\ Displaystyle F (x)}$

{\ Displaystyle L_ {\ rm {MSE}} = {\ Frac {1} {n}} \ lewo (yF (x) \ prawo) ^ {2}}

{\ Displaystyle - {\ Frac {\ częściowy L_ {\ rm {MSE}}} {\ częściowy F}} = {\ Frac {2} {n}} (yF (x)) = {\ Frac {2} { n}}h_{m}(x)}

.

Tak więc zwiększanie gradientu może być wyspecjalizowane w algorytmie zniżania gradientu , a uogólnienie go pociąga za sobą „podłączenie” innej straty i jej gradientu.

Algorytm

W wielu nadzorowanych problemach uczenia się występuje zmienna wyjściowa $y$ oraz wektor zmiennych wejściowych $x$ , powiązane ze sobą pewnym rozkładem probabilistycznym. Celem jest znalezienie funkcji, która najlepiej przybliża zmienną wyjściową z wartości zmiennych wejściowych. Jest to sformalizowane poprzez wprowadzenie pewnej funkcji straty i jej minimalizację: ${\ Displaystyle {\ kapelusz {F}} (x)}$ ${\ Displaystyle L (y, F (x))}$

{\ Displaystyle {\ kapelusz {F}} = {\ underset {F} {\ arg \ min}} \ \ mathbb {E} _ {x, y} [L (y, F (x))]}

.

Metoda wzmacniania gradientu zakłada wartość rzeczywistą $y$ i szuka przybliżenia w postaci ważonej sumy funkcji z pewnej klasy , zwanych bazowymi (lub słabymi ) uczącymi się: ${\ Displaystyle {\ kapelusz {F}} (x)}$ ${\ Displaystyle h_ {i} (x)}$ ${\ Displaystyle {\ Mathcal {H}}}$

{\ Displaystyle {\ kapelusz {F}} (x) = \ suma _ {i = 1} ^ {M} \ gamma _ {i} h_ {i} (x) + {\ mbox {stała}}}

.

Zwykle otrzymujemy zestaw uczący znanych wartości próbek $x$ i odpowiadających im wartości $y$ . Zgodnie z empiryczną zasadą minimalizacji ryzyka metoda stara się znaleźć przybliżenie, które minimalizuje średnią wartość funkcji straty na zbiorze uczącym, czyli minimalizuje ryzyko empiryczne. Robi to, zaczynając od modelu składającego się ze stałej funkcji i stopniowo rozszerzając go w zachłanny sposób: ${\ Displaystyle \ {(x_ {1}, y_ {1}), \ kropki, (x_ {n}, y_ {n}) \}}$ ${\ Displaystyle {\ kapelusz {F}} (x)}$ $F_{0}(x)$

{\ Displaystyle F_ {0} (x) = {\ underset {\ gamma} {\ arg \ min}} {\ suma _ {i = 1} ^ {n} {L (y_ {i}, \ gamma)} }}

,

{\ Displaystyle F_ {m} (x) = F_ {m-1} (x) + {\ underset {h_ {m} \ w {\ mathcal {H}}} {\ operatorname {arg \, min}}} \left[{\sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}} \Prawidłowy]}

,

gdzie jest podstawowa funkcja ucznia. ${\ Displaystyle h_ {m} \ w {\ matematyka {H}}}$

Niestety, wybór najlepszej funkcji $h$ na każdym etapie dla dowolnej funkcji straty $L$ jest ogólnie niewykonalnym obliczeniowo problemem optymalizacji. Dlatego ograniczamy nasze podejście do uproszczonej wersji problemu.

Pomysł polega na zastosowaniu najbardziej stromego stopnia zejścia do tego problemu minimalizacji (funkcjonalne zejście gradientowe).

Podstawową ideą najbardziej stromego zejścia jest znalezienie lokalnego minimum funkcji straty przez iterację na . W rzeczywistości można udowodnić, że kierunek maksymalizacji (najsilniejsza ujemna pochodna) funkcji straty do lokalnego minimum wzdłuż tej funkcji jest odejmowany przez sam gradient funkcji straty. Stąd: ${\ Displaystyle F_ {m} (x)}$ ${\ Displaystyle F_ {m} (x)}$

${\ Displaystyle F_ {m} (x) = F_ {m-1} (x) - \ gamma \ suma _ {i = 1} ^ {n} {\ nabla _ {F_ {m-1}} L (y_ {i},F_{m-1}(x_{i}))}}$

Gdzie . Oznacza to: . ${\ Displaystyle \ gamma > 0}$ ${\ Displaystyle L (y_ {i}, F_ {m} (x_ {i})) \ leq L (y_ {i}, F_ {m-1} (x_ {i}))}$

Ponadto możemy zoptymalizować , znajdując wartość, dla której Funkcja Straty ma minimum: ${\ Displaystyle \ gamma}$ ${\ Displaystyle \ gamma}$

${\ Displaystyle \ gamma _ {m} = {\ underset {\ gamma} {\ arg \ min}} {\ suma _ {i = 1} ^ {n} {L \ lewo (y_ {i}, F_ {m })\right)}}={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L\left(y_{i},F_{m-1 }(x_{i})-\gamma \nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))\right)}},}$

Gdybyśmy rozważyli przypadek ciągły, tj. gdzie jest zbiór dowolnych funkcji różniczkowalnych na , zaktualizowalibyśmy model zgodnie z następującymi równaniami ${\ Displaystyle {\ Mathcal {H}}}$ ${\ Displaystyle \ mathbb {R}}$

{\ Displaystyle F_ {m} (x) = F_ {m-1} (x) - \ gamma _ {m} \ suma _ {i = 1} ^ {n} {\ nabla _ {F_ {m-1} }L(y_{i},F_{m-1}(x_{i}))}}

Gdzie:

{\ Displaystyle \ gamma _ {m} = {\ underset {\ gamma} {\ arg \ min}} {\ suma _ {i = 1} ^ {n} {L \ lewo (y_ {i}, F_ {m -1}(x_{i})-\gamma \nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))\right)}},}

gdzie pochodne są brane w odniesieniu do funkcji dla , i jest długością kroku. Jednak w przypadku dyskretnym, tj. gdy zbiór jest skończony, wybieramy funkcję kandydującą $h$ najbliższą gradientowi $L,$ dla której współczynnik $γ$ można następnie obliczyć za pomocą wyszukiwania liniowego na powyższych równaniach. Zauważ, że to podejście jest heurystyczne i dlatego nie daje dokładnego rozwiązania danego problemu, ale raczej przybliżenie. W pseudokodzie ogólna metoda zwiększania gradientu to: ${\ Displaystyle F_ {i}}$ ${\ Displaystyle i \ w \ {1, .., m \}}$ ${\ Displaystyle \ gamma _ {m}}$ ${\ Displaystyle {\ Mathcal {H}}}$

Dane wejściowe: zestaw uczący różniczkowalną funkcję straty liczba iteracji $M$ . ${\ Displaystyle \ {(x_ {i}, y_ {i}) \} _ {i = 1} ^ {n},}$ ${\ Displaystyle L (y, F (x)),}$

Algorytm:

Zainicjuj model ze stałą wartością:
${\ Displaystyle F_ {0} (x) = {\ underset {\ gamma} {\ arg \ min}} \ suma _ {i = 1} ^ {n} L (y_ {i} \ gamma).}$
Dla m = 1 do M :
1. Oblicz tzw. pseudoreszt :
  ${\ Displaystyle R_ {im} = - \ lewo [{\ Frac {\ częściowy L (y_ {i}, F (x_ {i}}))} {\ częściowy F (x_ {i})}} \ prawej] _ {F(x)=F_{m-1}(x)}\quad {\mbox{dla }}i=1,\ldots ,n.}$
2. Dopasuj uczącego się podstawowego (lub uczącego słabego, np. drzewo) zamkniętego pod skalowaniem do pseudoreszt, tj. wytrenuj go za pomocą zestawu uczącego . ${\ Displaystyle h_ {m} (x)}$ ${\ Displaystyle \ {(x_ {i}, r_ {im}) \} _ {i = 1} ^ {n}}$
3. Oblicz mnożnik , rozwiązując następujący problem optymalizacji jednowymiarowej : ${\ Displaystyle \ gamma _ {m}}$
  ${\ Displaystyle \ gamma _ {m} = {\ underset {\ gamma} {\ operatorname {arg \, min}}} \ suma _ {i = 1} ^ {n} L \ lewo (y_ {i}, F_ {m-1}(x_{i})+\gamma h_{m}(x_{i})\prawo).}$
4. Zaktualizuj model:
  ${\ Displaystyle F_ {m} (x) = F_ {m-1} (x) + \ gamma _ {m} h_ {m} (x).}$
Wyjście ${\ Displaystyle F_ {M} (x).}$

Wzmocnienie drzewa gradientowego

Wzmacnianie gradientowe jest zwykle stosowane z drzewami decyzyjnymi (zwłaszcza drzewami CART ) o ustalonym rozmiarze jako podstawami uczącymi się. W tym szczególnym przypadku Friedman proponuje modyfikację metody wzmacniania gradientu, która poprawia jakość dopasowania każdego podstawowego ucznia.

Wzmocnienie gradientu ogólnego na m -tym kroku dopasuje drzewo decyzyjne do pseudoreszt. Niech będzie liczba jego liści. Drzewo dzieli przestrzeń wejściową na rozłączne regiony i przewiduje stałą wartość w każdym regionie. Używając notacji wskaźnikowej , wynik dla wejścia x można zapisać jako sumę: ${\ Displaystyle h_ {m} (x)}$ ${\ Displaystyle J_ {m}}$ ${\ Displaystyle J_ {m}}$ ${\ Displaystyle R_ {1 m}, \ ldots, R_ {J_ {m} m}}$ ${\ Displaystyle h_ {m} (x)}$

{\ Displaystyle h_ {m} (x) = \ suma _ {j = 1} ^ {J_ {m}} b_ {jm} \ mathbf {1} _ {R_ {jm}} (x),}

gdzie jest przewidywana wartość w regionie . $b_{jm}$ ${\ Displaystyle R_ {jm}}$

Następnie współczynniki są mnożone przez pewną wartość , wybraną metodą wyszukiwania liniowego tak, aby zminimalizować funkcję straty, a model jest aktualizowany w następujący sposób: $b_{jm}$ ${\ Displaystyle \ gamma _ {m}}$

{\ Displaystyle F_ {m} (x) = F_ {m-1} (x) + \ gamma _ {m} h_ {m} (x), \ quad \ gamma _ {m} = {\ underset {\ gamma }{\nazwa operatora {arg\,min} }}\sum _{i=1}^{n}L(y_{i},F_{m-1}(x_{i})+\gamma h_{m} (x_{i})).}

Friedman proponuje zmodyfikowanie tego algorytmu tak, aby wybierał osobną optymalną wartość dla każdego z regionów drzewa, zamiast jednej dla całego drzewa. Zmodyfikowany algorytm nazywa „TreeBoost”. Współczynniki z procedury dopasowywania drzewa można wtedy po prostu odrzucić, a reguła aktualizacji modelu staje się: ${\ Displaystyle \ gamma _ {jm}}$ ${\ Displaystyle \ gamma _ {m}}$ $b_{jm}$

{\ Displaystyle F_ {m} (x) = F_ {m-1} (x) + \ suma _ {j = 1} ^ {J_ {m}} \ gamma _ {jm} \ mathbf {1} _ {R_ {jm}}(x),\quad \gamma _{jm}={\underset {\gamma }{\nazwa operatora {arg\,min} }}\sum _{x_{i}\in R_{jm}} L(y_{i},F_{m-1}(x_{i})+\gamma ).}

Wielkość drzew

${\ Displaystyle J}$ , liczba węzłów końcowych w drzewach, jest parametrem metody, który można dostosować do danego zestawu danych. Kontroluje maksymalny dozwolony poziom interakcji między zmiennymi w modelu. W przypadku ( kikutów decyzyjnych ) nie jest dozwolona żadna interakcja między zmiennymi. Z modelu może obejmować efekty oddziaływania między maksymalnie dwóch zmiennych, i tak dalej. ${\ Displaystyle J = 2}$ ${\ Displaystyle J = 3}$

Hastie i in. komentarz, który zwykle działa dobrze w przypadku wzmocnienia, a wyniki są dość niewrażliwe na wybór w tym zakresie, są niewystarczające dla wielu zastosowań i jest mało prawdopodobne, aby były wymagane. $4\leq J\leq 8$ ${\ Displaystyle J}$ ${\ Displaystyle J = 2}$ $J>10$

Regularyzacja

Zbyt ścisłe dopasowanie zestawu szkoleniowego może prowadzić do degradacji zdolności uogólniania modelu. Kilka tak zwanych technik regularyzacji zmniejsza ten efekt nadmiernego dopasowania , ograniczając procedurę dopasowania.

Jednym z naturalnych parametrów regularyzacji jest liczba iteracji zwiększających gradient M (tj. liczba drzew w modelu, gdy bazowy uczący się jest drzewem decyzyjnym). Zwiększenie M zmniejsza błąd na serii treningowej, ale ustawienie go zbyt wysoko może prowadzić do overfittingu. Optymalna wartość M jest często wybierana przez monitorowanie błędu predykcji na oddzielnym zestawie danych walidacyjnych. Oprócz kontrolowania M stosuje się kilka innych technik regularyzacji.

Kolejnym parametrem regularyzacji jest głębokość drzew. Im wyższa ta wartość, tym większe prawdopodobieństwo, że model przepełni dane uczące.

Kurczenie się

Ważną częścią metody wzmacniania gradientu jest regularyzacja przez kurczenie polegająca na modyfikacji reguły aktualizacji w następujący sposób:

{\ Displaystyle F_ {m} (x) = F_ {m-1} (x) + \ nu \ cdot \ gamma _ {m} h_ {m} (x), \ quad 0 < \ nu \ równa 1,}

gdzie parametr nazywany jest „szybkością uczenia się”. $\nu$

Empirycznie stwierdzono, że stosowanie małych szybkości uczenia się (takich jak ) daje radykalną poprawę zdolności uogólniania modeli w stosunku do zwiększania gradientu bez zmniejszania ( ). Jednak odbywa się to za cenę wydłużenia czasu obliczeniowego zarówno podczas uczenia, jak i wykonywania zapytań : niższy wskaźnik uczenia wymaga większej liczby iteracji. ${\ Displaystyle \ nu <0,1}$ ${\ Displaystyle \ nu =1}$

Stochastyczne zwiększanie gradientu

Wkrótce po wprowadzeniu gradientu przypominającej, Friedman zaproponowano modyfikację drobnej algorytmu motywowane Breiman jest agregacji ładujący metodą ( «workowania»). W szczególności zaproponował, aby w każdej iteracji algorytmu podstawowy uczący się był dopasowany do podpróbki zbioru uczącego wylosowanego bez zastępowania. Friedman zaobserwował znaczną poprawę dokładności wzmocnienia gradientu dzięki tej modyfikacji.

Rozmiar podpróbki to pewien stały ułamek rozmiaru zbioru uczącego. Gdy , algorytm jest deterministyczny i identyczny z opisanym powyżej. Mniejsze wartości wprowadzają do algorytmu losowość i zapobiegają przeuczeniu , działając jako swego rodzaju regularyzacja . Algorytm staje się również szybszy, ponieważ drzewa regresji muszą być dopasowane do mniejszych zestawów danych w każdej iteracji. Friedman uzyskał, co prowadzi do dobrych wyników dla małych i średnich zestawów treningowych. Dlatego zwykle jest ustawiony na 0,5, co oznacza, że połowa zestawu szkoleniowego jest używana do budowania każdego podstawowego ucznia. $f$ $f=1$ $f$ ${\ Displaystyle 0,5 \ równoważnik f \ równoważnik 0,8}$ $f$

Podobnie jak w przypadku baggingu, podpróbkowanie pozwala na zdefiniowanie poza-bagowego błędu poprawy wydajności predykcji poprzez ocenę predykcji na tych obserwacjach, które nie zostały wykorzystane w budowaniu następnego podstawowego ucznia. Szacunki out-of-bag pomagają uniknąć potrzeby niezależnego zestawu danych walidacyjnych, ale często nie doceniają rzeczywistej poprawy wydajności i optymalnej liczby iteracji.

Liczba obserwacji w liściach

Implementacje wzmacniania drzew gradientowych często wykorzystują również regularyzację, ograniczając minimalną liczbę obserwacji w węzłach końcowych drzew. Jest używany w procesie budowania drzewa przez ignorowanie wszelkich podziałów, które prowadzą do węzłów zawierających mniej niż ta liczba instancji zestawu treningowego.

Nałożenie tego limitu pomaga zmniejszyć rozbieżności w przewidywaniach na liściach.

Ukarać złożoność drzewa

Inną użyteczną techniką regularyzacji drzew ze wzmocnieniem gradientowym jest karanie złożoności modelu wyuczonego. Złożoność modelu można określić jako proporcjonalną liczbę liści w wyuczonych drzewach. Łączna optymalizacja strat i złożoności modelu odpowiada algorytmowi post-przycinania, który usuwa gałęzie, które nie zmniejszają strat o próg. Inne rodzaje regularyzacji, takie jak kara na wartości liścia, mogą być również dodane, aby uniknąć overfittingu . $\ell_{2}$

Stosowanie

Gradient boosting może być wykorzystany w dziedzinie nauki rangowania . Komercyjne wyszukiwarki internetowe Yahoo i Yandex używają wariantów zwiększania gradientu w swoich uczących się maszynowo silnikach rankingowych. Wzmocnienie gradientowe jest również wykorzystywane w fizyce wysokich energii w analizie danych. W Wielkim Zderzaczu Hadronów (LHC) warianty wzmacniania gradientu Deep Neural Networks (DNN) z powodzeniem odtwarzały wyniki analizy metodami non-machine learning na zbiorach danych wykorzystywanych do odkrycia bozonu Higgsa .

Nazwy

Metoda ma różne nazwy. Friedman przedstawił swoją technikę regresji jako „Gradient Boosting Machine” (GBM). Mason, Baxter i in. opisał uogólnioną abstrakcyjną klasę algorytmów jako „funkcjonalne wzmocnienie gradientu”. Friedman i in. opisać postęp modeli ze wzmocnieniem gradientowym jako drzewa regresji wielokrotnej addytywnej (MART); Elith i in. opisz to podejście jako "Drzewa Regresji Wzmocnionej" (BRT).

Popularna implementacja open-source dla języka R nazywa go „Generalized Boosting Model”, jednak pakiety rozszerzające tę pracę używają BRT. Jeszcze inna nazwa to TreeNet, po wczesnej komercyjnej implementacji Dana Steinberga z Salford System, jednego z badaczy, którzy byli pionierami w stosowaniu metod opartych na drzewie. XGBoost to kolejna popularna nowoczesna implementacja metody z pewnymi rozszerzeniami, takimi jak optymalizacja drugiego rzędu.

Niedogodności

Chociaż wzmacnianie może zwiększyć dokładność podstawowego ucznia, takiego jak drzewo decyzyjne lub regresja liniowa, poświęca to zrozumiałość i interpretację . Ponadto jego implementacja może być utrudniona ze względu na większe wymagania obliczeniowe.

Zobacz też

Bibliografia

Dalsza lektura

Boehmkego, Bradleya; Greenwell, Brandon (2019). „Wzmocnienie gradientu”. Praktyczne uczenie maszynowe z R . Chapmana i Halla. s. 221-245. Numer ISBN 978-1-138-49568-5.

Languages

In other projects