Wzmocnienie gradientu

Wzmocnienie gradientu to technika uczenia maszynowego wykorzystywana między innymi w zadaniach regresji i klasyfikacji . Daje model predykcyjny w postaci zespołu słabych modeli predykcyjnych, które zazwyczaj są drzewami decyzyjnymi . Kiedy drzewo decyzyjne jest słabym uczniem, wynikowy algorytm nazywany jest drzewami wzmocnionymi gradientem; zwykle przewyższa losowy las . Model drzew wzmocnionych gradientem jest budowany etapami, podobnie jak w przypadku innych wzmocnień metod, ale uogólnia inne metody, umożliwiając optymalizację dowolnej różniczkowalnej funkcji straty .

Historia

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

Nieformalne wprowadzenie

(Ta sekcja jest zgodna z opisem wzmacniania gradientu przez Chenga).

Podobnie jak inne metody wzmacniania, wzmacnianie gradientowe łączy słabych „uczniów” w jednego silnego ucznia w iteracyjny sposób. Najłatwiej to wyjaśnić w regresji metodą ${\ displaystyle {\ kapelusz {y} }}=F(x)}$ kwadratów , gdzie celem „nauczenie” modelu przewidywania wartości postaci $x$ minimalizując błąd średniokwadratowy ${\ Displaystyle {\ tfrac {1} {n}} \ suma _ {i} ({\ kapelusz {y}} _ {i} -y_ {i}) ^ {2}},$ gdzie ${ \ displaystyle i}$ indeksy na pewnym zbiorze treningowym rzeczywistych wartości zmiennej wyjściowej ${\ displaystyle$ $n {\ displaystyle y}$ :

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

Rozważmy teraz algorytm zwiększania gradientu $etapami$ . Na każdym etapie zwiększania gradientu załóżmy, że jakiś niedoskonały model (dla niskiego m {\ Displaystyle M}} $równoważnik m \ równoważnik$ 1 $≤$ M $M$ $} \ displaystyle m}$ , ten model może po prostu zwrócić , gdzie ${\ Displaystyle {\ hat {y}} _ {i} = {\ bar {y}}}$ RHS jest średnią ${\ Displaystyle y}$ ). Aby $,$ $_$ nowy _ Zatem,

{\ Displaystyle F_ {m + 1} (x_ {i}) = F_ {m} (x_ {i} )+h_{m}(x_{i})=y_{i}}

lub równoważnie,

{\ Displaystyle h_ {m} (x_ {i}) = y_ {i} -F_ {m} (x_ {i})}

.

Dlatego wzmocnienie gradientu będzie pasować $x_ {i})$ { \ $}$ . Podobnie jak w innych wariantach wzmacniania, każdy ${m}$ poprawić błędy swojego poprzednika. $+ 1 {$ } Uogólnienie tego pomysłu na funkcje strat inne niż błąd kwadratowy i na problemów klasyfikacji i rankingu $wynika$ z obserwacji, że reszty modelu są proporcjonalne do ujemnych gradientów (MSE funkcja (w odniesieniu do ${\ Displaystyle F (x_ {i})}$ ):

{\ Displaystyle L _ {\ rm {MSE}} = {\ Frac {1} {n}} \ suma _ {i =1}^{n}\left(y_{i}-F(x_{i})\right)^{2}}

{\ Displaystyle - {\ Frac {\ częściowe L _ {\ rm {MSE}}} {\ częściowe F (x_ {i})}} = {\ Frac {2} n}}(y_{i}-F(x_{i}))={\frac {2}{n}}h_{m}(x_{i})}

.

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

Algorytm

W wielu problemach uczenia nadzorowanego istnieje zmienna wyjściowa $y$ i wektor zmiennych wejściowych $x$ , powiązanych ze sobą pewnym rozkładem probabilistycznym. Celem $która najlepiej$ znalezienie jakiejś funkcji zmienną wyjściową z wartości zmiennych Jest to sformalizowane przez wprowadzenie pewnej funkcji straty ${\ Displaystyle L (y, F (x))}$ i minimalizując go w oczekiwaniu:

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

.

Metoda wzmacniania gradientu zakłada wartość rzeczywistą $y$ . Poszukuje przybliżenia w postaci sumy ważonej $}$ $x$ ) $h_$ x niektóre klasy , zwane podstawowymi (lub słabymi ) uczniami: ${\ displaystyle {\ mathcal {H}}}$

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

.

Zwykle otrzymujemy zbiór uczący ${\ Displaystyle \ {(x_ {1}, y_ {1}), \ kropki, (x_ {n },y_{n})\}}$ znanych przykładowych wartości $x$ i odpowiadających im wartości $y$ . Zgodnie z empiryczną zasadą minimalizacji ryzyka , metoda próbuje znaleźć przybliżenie ${\ displaystyle {\ hat {F}} (x)}$ minimalizuje średnią wartość funkcji straty na zbiorze treningowym, tj. minimalizuje ryzyko empiryczne. Robi to, zaczynając od modelu składającego się ze stałej funkcji i stopniowo rozszerza ją w zachłanny sposób: ${\ displaystyle 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)+\left({\underset {h_{m}\in {\mathcal {H}}}{\operatorname {arg\,min} }}\left[{\sum _{i=1}^ {n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i})}}}\prawo]\prawo)(x)}

,

dla , gdzie jest podstawową funkcją uczącą $1$ $}$

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

Chodzi o to, aby zastosować najbardziej stromy krok zejścia do tego problemu minimalizacji (funkcjonalne zejście gradientu).

Podstawową ideą najbardziej stromego spadku jest znalezienie lokalnego minimum funkcji straty przez iterację po . ${\ Displaystyle F_ {m-1} (x)}$ . W rzeczywistości lokalny kierunek maksymalnego spadku funkcji strat jest gradientem ujemnym.

Stąd przesunięcie o niewielką wartość tak, aby przybliżenie liniowe pozostało ważne: ${\ displaystyle \ gamma}$

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

gdzie ${\ Displaystyle \ gamma > 0}$ . γ ${\ Displaystyle \ gamma}$ oznacza to, że $\ Displaystyle L (y_ {i}, F_{m}(x_{i}))\równoważnik L(y_{i},F_{m-1}(x_{i}))}$ .

Dowód postaci funkcjonalnej pochodnej

Aby udowodnić następujące twierdzenie, rozważ cel

${\ Displaystyle O = \ suma _ {i = 1} ^ {n} {L (y_ { i},F_{m-1}(x_{i})+h_{m}(x_{i}))}}$

Dokonywanie rozwinięcia Taylora do pierwszego rzędu ${\ Displaystyle O = \ suma _ {i = 1} ^ {n} {L (y_ {i },F_{m-1}(x_{i})+h_{m}(x_{i}))}\około \sum _{i=1}^{n}{L(y_{i},F_ {m-1}(x_{i}))+h_{m}(x_{i})\nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{ i}))}+\ldkropki}$

Teraz różnicując $m$ ${\ Displaystyle \ nabla _ {F_ {m-1}} L (y_ {i}, F_ {m-1} (x_ {i}))}$ drugiego . Jest to kierunek najbardziej stromego wzniesienia, dlatego musimy poruszać się w przeciwnym (tj. ujemnym) kierunku, aby poruszać się w kierunku najbardziej stromego zejścia.

Ponadto możemy zoptymalizować , znajdując wartość, dla której funkcja straty ma minimum: ${$ $\ displaystyle \ gamma$

${\ Displaystyle \ gamma _ {m} = {\ underset {\ gamma}} {\ arg \ min}}} {\ suma _ {i = 1} ^ {n} {L (y_ {i}, F_ {m} ( x_{i})}}}={\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 zbiorem dowolnych funkcji różniczkowalnych na $,$ zaktualizowalibyśmy model zgodnie z ${\ displaystyle \ mathbb {R}$ następujące równania

{\ 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 jest długością kroku, zdefiniowaną jako. ${\ displaystyle \ gamma _ {m}}$

{\ 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)}}.}

Jednak w przypadku dyskretnym, tj. Gdy zbiór jest skończony, wybieramy kandydującą funkcję

h

najbliższą gradientowi

L

, dla którego można następnie obliczyć współczynnik

γ

za pomocą H

\ displaystyle {\ mathcal {H}}}

wyszukiwanie linii 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 wzmacniania gradientu to:

Wejście: zestaw treningowy ${\ Displaystyle \ {(x_ {i}, y_ {i}) \} _ {i = 1} ^ {n},}$ różniczkowalna funkcja straty ${\ Displaystyle L (y, F (x))}$ liczba iteracji $M$ .

Algorytm:

Zainicjuj model 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. Obliczamy tak zwane pseudoreszty :
  ${\ Displaystyle r_ {im} = - \ lewo [{\ Frac {\ częściowe L (y_ {i}, F (x_ {i}})}} {\ częściowe F (x_ {i})}} \ prawo] _ {F(x)=F_{m-1}(x)}\quad {\mbox{for}}i=1,\ldots, rz.}$
2. Dopasuj podstawowego ucznia (lub słabego ucznia, np. Drzewo) zamkniętego pod skalowaniem $do$ . wytrenuj go za pomocą zestawu ${\ Displaystyle \ {(x_ {i}, r_ {im}} \} _ {i = 1} ^ {n}}$ .
3. Oblicz mnożnik $,$
  ${\ Displaystyle \ gamma _ {m} = {\ underset {\ gamma}} {\ nazwa operatora {arg \, min}}} \ suma _ {i = 1} ^ {n} L \ lewo (y_ {i}, F_ {m-1}(x_{i})+\gamma h_{m}(x_{i})\right).}$
  następujący problem optymalizacji :
4. Zaktualizuj model:
  ${\ Displaystyle F_ {m} (x) = F_ {m-1} (x) + \ gamma _ {m} h_ {m} (x).}$
Wyjście ${\ Displaystyle F_ {M} (x).}$

Wzmocnienie drzewa gradientu

Wzmocnienie gradientu jest zwykle używane z drzewami decyzyjnymi (zwłaszcza CART ) o stałym rozmiarze jako podstawowymi uczniami. W tym szczególnym przypadku Friedman proponuje modyfikację metody wzmacniania gradientu, która poprawia jakość dopasowania każdego podstawowego ucznia.

$Ogólne$ na m -tym kroku pasowałoby do drzewa decyzyjnego -reszt Niech $.$ liczbą jego Drzewo dzieli przestrzeń wejściową na rozłączne regiony $Displaystyle$ ${J_ {m} m}}$ i przewiduje stałą wartość w każdym regionie. Używając notacji wskaźnika , wynik dla wejścia x można zapisać jako sumę: ${\ displaystyle h_ {m} (x)}$

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

gdzie ${\ displaystyle b_ {jm}}$ jest wartością przewidywaną w regionie $\ displaystyle R_ {jm}}$ {

Następnie współczynniki $}}$ się przez pewną wartość, $\ displaystyle b_ {$ liniowego, aby zminimalizować funkcję straty, a model jest aktualizowany jako b jot m co następuje:

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

$Displaystyle$ $\ gamma _ {m}}$ tak, aby wybierał oddzielną optymalną wartość dla każdego z regionów drzewa, zamiast pojedynczego dla całego drzewa. Zmodyfikowany algorytm nazywa „TreeBoost”. Współczynniki z procedury dopasowywania drzewa można następnie po prostu odrzucić, a reguła aktualizacji modelu przyjmuje postać: ${\ displaystyle 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}}{\operatorname {arg\,min}}}\sum _{x_{i}\in R_{jm}} L(y_{i},F_{m-1}(x_{i})+\gamma ).}

Rozmiar drzew

${\ displaystyle J}$ , liczba węzłów końcowych w drzewach, to parametr metody, który można dostosować do dostępnego zestawu danych. Kontroluje maksymalny dozwolony poziom interakcji między zmiennymi w modelu. Z $) nie jest$ pniaki decyzyjne między zmiennymi . W przypadku $modelu$ obejmować efekty interakcji między maksymalnie dwiema zmiennymi i tak dalej

Hastie i in. skomentuj $=$ że zazwyczaj $2}$ na wybór w tym zakresie, $Displaystyle$ $J$ $jest$ niewystarczający dla wielu zastosowań i jest mało , aby był

Regularyzacja

Zbyt ścisłe dopasowanie zbioru uczącego może prowadzić do pogorszenia zdolności generalizacji modelu. Kilka tak zwanych technik regularyzacji zmniejsza ten efekt nadmiernego dopasowania poprzez ograniczenie procedury dopasowania.

Jednym z naturalnych parametrów regularyzacji jest liczba iteracji wzmacniania gradientu M (tj. liczba drzew w modelu, gdy podstawowym uczniem jest drzewo decyzyjne). Zwiększenie M zmniejsza błąd na zbiorze treningowym, ale ustawienie go zbyt wysoko może prowadzić do przeuczenia. Optymalna wartość M jest często wybierana przez monitorowanie błędu przewidywania na oddzielnym zbiorze 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 przetrenuje dane treningowe.

Kurczenie się

Ważną częścią metody wzmacniania gradientu jest regularyzacja przez skurcz, która polega na zmodyfikowaniu 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 \leq 1,}

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

Empirycznie stwierdzono, że stosowanie małych współczynników uczenia się (takich jak ) daje radykalną poprawę $1$ uogólniania modeli w porównaniu ze zwiększaniem gradientu bez kurczenia się ( ${ \ displaystyle \ nu$ ). Jednak odbywa się to kosztem wydłużenia czasu obliczeń zarówno podczas szkolenia, jak i zapytań : niższy wskaźnik uczenia wymaga większej liczby iteracji.

Wzmocnienie gradientu stochastycznego

Wkrótce po wprowadzeniu wzmacniania gradientu Friedman zaproponował niewielką modyfikację algorytmu, motywowaną metodą agregacji bootstrap Breimana („bagging”). W szczególności zaproponował, aby w każdej iteracji algorytmu podstawowy uczeń pasował do losowo wylosowanej bez zwracania podpróby zestawu szkoleniowego. Dzięki tej modyfikacji Friedman zaobserwował znaczną poprawę dokładności zwiększania gradientu.

Wielkość podpróbki to pewien stały ułamek wielkości zbioru $uczącego$ Kiedy $deterministyczny i identyczny$ algorytmem opisanym powyżej. Mniejsze wartości $nadmiernemu$ do algorytmu i pomagają zapobiegać dopasowaniu , działając jako rodzaj regularyzacji . Algorytm staje się również szybszy, ponieważ drzewa regresji muszą być dopasowane do mniejszych zbiorów danych w każdej iteracji. Friedman uzyskał, że ${\ Displaystyle 0,5 \ równoważnik f \ równoważnik 0,8}$ prowadzi do dobrych wyników dla małych i średnich zestawów treningowych. Dlatego $0,5$ , co oznacza, że połowa zestawu szkoleniowego jest używana do zbudowania każdego podstawowego ucznia

Podobnie jak w przypadku workowania, podpróbkowanie umożliwia zdefiniowanie błędu out-of-bag poprawy wydajności prognozy poprzez ocenę prognoz dotyczących tych obserwacji, które nie zostały wykorzystane w budowaniu następnego podstawowego ucznia. Gotowe oszacowania pomagają uniknąć konieczności posiadania niezależnego zbioru danych do walidacji, ale często niedoszacują faktycznej poprawy wydajności i optymalnej liczby iteracji.

Liczba obserwacji w liściach

Implementacje wzmacniające drzewa gradientowe często również wykorzystują regularyzację, ograniczając minimalną liczbę obserwacji w węzłach końcowych drzew. Jest używany w procesie budowania drzewa poprzez ignorowanie wszelkich podziałów, które prowadzą do węzłów zawierających mniej niż ta liczba instancji zbioru uczącego.

Nałożenie tego limitu pomaga zmniejszyć wariancję prognoz na liściach.

Penalizuj złożoność drzewa

Inną użyteczną techniką regularyzacji dla drzew wzmocnionych gradientem 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 w celu usunięcia gałęzi, które nie zmniejszają strat o próg. Można również dodać inne rodzaje regularyzacji, takie jak kara za wartości $,$ aby przeuczenia .

Stosowanie

Gradient boosting może być wykorzystany w nauce rangowania . Komercyjne wyszukiwarki internetowe Yahoo i Yandex wykorzystują warianty zwiększania gradientu w swoich silnikach rankingowych uczących się maszynowo. Wzmocnienie gradientu jest również wykorzystywane w fizyce wysokich energii w analizie danych. W Wielkim Zderzaczu Hadronów (LHC) warianty głębokich sieci neuronowych (DNN) ze wzmacnianiem gradientu z powodzeniem odtwarzały wyniki metod analizy niezwiązanych z uczeniem maszynowym na zestawach danych używanych do odkrywania bozonu Higgsa . Drzewo decyzyjne wzmacniające gradient znalazło również zastosowanie w badaniach ziemnych i geologicznych – np. ocena jakości złoża piaskowcowego.

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 wzmacnianie gradientu”. Friedmana i in. opisać postęp modeli wzmocnionych gradientem jako drzewa regresji wielokrotnej addytywnej (MART); Elith i in. opisują to podejście jako „Boosted Regression Trees” (BRT).

Popularna implementacja open source dla języka R nazywa to „uogólnionym modelem wspomagania”, 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 drzewach. XGBoost to kolejna popularna nowoczesna implementacja metody z pewnymi rozszerzeniami, takimi jak optymalizacja drugiego rzędu.

Niedogodności

Podczas gdy wzmacnianie może zwiększyć dokładność podstawowego elementu uczącego, takiego jak drzewo decyzyjne lub regresja liniowa, poświęca zrozumiałość i interpretowalność . Na przykład podążanie ścieżką, którą podąża drzewo decyzyjne, aby podjąć decyzję, jest trywialne i oczywiste, ale podążanie ścieżkami setek lub tysięcy drzew jest znacznie trudniejsze. Aby osiągnąć zarówno wydajność, jak i interpretowalność, niektóre techniki kompresji modeli umożliwiają przekształcenie XGBoost w pojedyncze drzewo decyzyjne „narodzone na nowo”, które przybliża tę samą funkcję decyzyjną. Ponadto jego implementacja może być utrudniona ze względu na większe zapotrzebowanie obliczeniowe.

Zobacz też

Dalsza lektura

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

Linki zewnętrzne