A Gentle Introduction to the Gradient Boosting Algorithm for Machine Learning

Last Updated on August 15, 2020

Gradient boosting jest jedną z najpotężniejszych technik budowania modeli predykcyjnych.

W tym poście odkryjesz algorytm uczenia maszynowego gradient boosting i otrzymasz delikatne wprowadzenie do tego, skąd pochodzi i jak działa.

Po przeczytaniu tego postu będziesz wiedział:

• Pochodzenie boostingu z teorii uczenia się i AdaBoost.
• Jak działa gradient boosting, w tym funkcja straty, słabe uczące i model addytywny.
• Jak poprawić wydajność w stosunku do algorytmu bazowego za pomocą różnych schematów regularyzacji.

Rozpocznij swój projekt dzięki mojej nowej książce XGBoost With Python, zawierającej samouczki krok po kroku oraz pliki z kodem źródłowym Pythona dla wszystkich przykładów.

Zacznijmy.

• Need help with XGBoost in Python?
• Pochodzenie boostingu
• AdaBoost the First Boosting Algorithm
• Generalizacja AdaBoost jako Gradient Boosting
• How Gradient Boosting Works
• Funkcja straty
• Słaby uczący
• Model addytywny
• Ulepszenia podstawowego Gradient Boosting
• Wężenia drzewa
• 2. Aktualizacje ważone
• Stochastic Gradient Boosting
• Penalized Gradient Boosting
• Gradient Boosting Resources
• Gradient Boosting Videos
• Gradient Boosting in Textbooks
• Gradient Boosting Papers
• Gradient Boosting Slides
• Gradient Boosting Web Pages
• Podsumowanie
• Odkryj algorytm wygrywający konkursy!
• Develop Your Own XGBoost Models in Minutes
• Podnieś moc XGBoost do własnych projektów

Need help with XGBoost in Python?

Take my free 7-day email course and discover xgboost (with sample code).

Click to sign-up now and also get a free PDF Ebook version of the course.

Start Your FREE Mini-Course Now!

Pochodzenie boostingu

Pomysł boostingu wziął się z idei, czy słaby uczeń może zostać zmodyfikowany, aby stać się lepszym.

Michael Kearns wyartykułował cel jako „Hypothesis Boosting Problem” określając go z praktycznego punktu widzenia jako:

… efektywny algorytm przekształcania stosunkowo słabych hipotez w bardzo dobre hipotezy

– Thoughts on Hypothesis Boosting , 1988

Słaba hipoteza lub słaby uczący się jest definiowany jako taki, którego wydajność jest przynajmniej nieznacznie lepsza od przypadkowej.

Pomysły te opierają się na pracy Leslie Valiant’a nad uczeniem bez dystrybucji lub Prawdopodobnie W przybliżeniu Poprawnym (PAC), ramą do badania złożoności problemów uczenia maszynowego.

Hypothesis boosting był pomysłem filtrowania obserwacji, pozostawiając te obserwacje, z którymi słaby uczący się może sobie poradzić i skupiając się na rozwijaniu nowych słabych uczących się, aby poradzić sobie z pozostałymi trudnymi obserwacjami.

Pomysł polega na użyciu metody słabego uczenia się kilka razy, aby uzyskać sukcesję hipotez, z których każda jest ponownie skoncentrowana na przykładach, które poprzednie uznały za trudne i źle sklasyfikowały. … Zauważ jednak, że wcale nie jest oczywiste, jak można to zrobić

– Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World, strona 152, 2013

AdaBoost the First Boosting Algorithm

Pierwszą realizacją boostingu, która odniosła wielki sukces w zastosowaniu, był Adaptive Boosting lub w skrócie AdaBoost.

Boosting odnosi się do tego ogólnego problemu produkcji bardzo dokładnej reguły predykcji przez połączenie szorstkich i umiarkowanie niedokładnych rules-of-thumb.

– A decision-theoretic generalization of on-line learning and an application to boosting , 1995

Słabe uczące w AdaBoost są drzewami decyzyjnymi z pojedynczym rozszczepieniem, nazywanymi pniakami decyzyjnymi ze względu na ich krótkość.

AdaBoost działa poprzez ważenie obserwacji, kładąc większą wagę na trudne do sklasyfikowania przypadki, a mniejszą na te, które już zostały dobrze potraktowane. Nowe słabe uczące są dodawane sekwencyjnie, które koncentrują swój trening na trudniejszych wzorcach.

To oznacza, że próbki, które są trudne do sklasyfikowania, otrzymują coraz większe wagi, aż algorytm zidentyfikuje model, który poprawnie klasyfikuje te próbki

– Applied Predictive Modeling, 2013

Predykcje są dokonywane większością głosów predykcji słabych uczących, ważonych ich indywidualną dokładnością. Najbardziej udana forma algorytmu AdaBoost dotyczyła problemów klasyfikacji binarnej i nosiła nazwę AdaBoost.M1.

Więcej o algorytmie AdaBoost możesz dowiedzieć się w poście:

• Boosting and AdaBoost for Machine Learning.

Generalizacja AdaBoost jako Gradient Boosting

AdaBoost i pokrewne algorytmy zostały przekształcone w ramy statystyczne najpierw przez Breimana nazywając je algorytmami ARCing.

Arcing jest akronimem od Adaptive Reweighting and Combining. Każdy krok w algorytmie Arcing składa się z ważonej minimalizacji, po której następuje ponowne obliczenie i .

– Prediction Games and Arching Algorithms , 1997

Te ramy zostały dalej rozwinięte przez Friedmana i nazwane Gradient Boosting Machines. Później nazwano je po prostu gradientowym boostingiem lub gradientowym drzewem boostingowym.

Ramy statystyczne traktują boosting jako numeryczny problem optymalizacyjny, w którym celem jest minimalizacja straty modelu poprzez dodawanie słabych uczących się przy użyciu procedury gradientowego zejścia.

Ta klasa algorytmów została opisana jako stage-wise additive model. Dzieje się tak dlatego, że jeden nowy słaby uczący jest dodawany na raz, a istniejące słabe uczące w modelu są zamrożone i pozostawione bez zmian.

Zauważ, że ta strategia stopniowego dodawania różni się od podejścia stopniowego, które ponownie dostosowuje wcześniej wprowadzone terminy, gdy dodawane są nowe.

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

Uogólnienie pozwoliło na użycie dowolnie różnicowalnych funkcji straty, rozszerzając technikę poza problemy klasyfikacji binarnej w celu obsługi regresji, klasyfikacji wieloklasowej i innych.

How Gradient Boosting Works

Gradient boosting obejmuje trzy elementy:

1. Funkcja straty do zoptymalizowania.
2. Słaby uczący się do przewidywań.
3. Model addytywny do dodawania słabych uczących, aby zminimalizować funkcję straty.

Funkcja straty

Używana funkcja straty zależy od typu rozwiązywanego problemu.

Musi być różniczkowalna, ale obsługiwanych jest wiele standardowych funkcji straty i można zdefiniować własną.

Na przykład regresja może używać błędu kwadratowego, a klasyfikacja może używać straty logarytmicznej.

Zaletą ram gradientowego boostingu jest to, że nowy algorytm boostingu nie musi być wyprowadzany dla każdej funkcji straty, która może chcieć być użyta, zamiast tego, jest to wystarczająco ogólny framework, że każda różniczkowalna funkcja straty może być użyta.

Słaby uczący

Drzewa decyzyjne są używane jako słaby uczący w gradientowym boostingu.

Szczególnie używane są drzewa regresyjne, które wyprowadzają prawdziwe wartości dla podziałów i których dane wyjściowe mogą być sumowane, pozwalając na dodawanie kolejnych danych wyjściowych modeli i „korygowanie” reszt w przewidywaniach.

Drzewa są konstruowane w sposób zachłanny, wybierając najlepsze punkty podziału na podstawie wyników czystości, takich jak Gini lub w celu zminimalizowania straty.

Początkowo, tak jak w przypadku AdaBoost, używano bardzo krótkich drzew decyzyjnych, które miały tylko jeden podział, zwany pniakiem decyzyjnym. Większe drzewa mogą być używane na ogół z 4 do 8 poziomami.

Powszechne jest ograniczanie słabych uczących w specyficzny sposób, taki jak maksymalna liczba warstw, węzłów, podziałów lub węzłów liści.

Jest to zapewnienie, że uczące pozostają słabe, ale nadal mogą być konstruowane w sposób zachłanny.

Model addytywny

Drzewa są dodawane pojedynczo, a istniejące drzewa w modelu nie są zmieniane.

Procedura zstępowania gradientowego jest używana do minimalizacji straty podczas dodawania drzew.

Tradycyjnie, zstępowanie gradientowe jest używane do minimalizacji zestawu parametrów, takich jak współczynniki w równaniu regresji lub wagi w sieci neuronowej. Po obliczeniu błędu lub straty, wagi są aktualizowane, aby zminimalizować ten błąd.

Zamiast parametrów, mamy słabe uczące się submodele lub bardziej szczegółowo drzewa decyzyjne. Po obliczeniu straty, aby wykonać procedurę zejścia gradientowego, musimy dodać do modelu drzewo, które zmniejsza stratę (czyli podąża za gradientem). Robimy to poprzez sparametryzowanie drzewa, następnie modyfikujemy parametry drzewa i poruszamy się we właściwym kierunku poprzez (zmniejszenie straty rezydualnej.

Ogólnie takie podejście nazywane jest funkcjonalnym zejściem gradientowym lub zejściem gradientowym z funkcjami.

Jednym ze sposobów na wyprodukowanie ważonej kombinacji klasyfikatorów, która optymalizuje, jest zejście gradientowe w przestrzeni funkcji

– Boosting Algorithms as Gradient Descent in Function Space , 1999

Wyjście dla nowego drzewa jest następnie dodawane do wyjścia istniejącej sekwencji drzew w celu skorygowania lub poprawienia ostatecznego wyjścia modelu.

Stała liczba drzew jest dodawana lub szkolenie zatrzymuje się, gdy strata osiągnie akceptowalny poziom lub nie poprawia się już na zewnętrznym zbiorze danych walidacyjnych.

Ulepszenia podstawowego Gradient Boosting

Gradient boosting jest algorytmem zachłannym i może szybko przepasać zbiór danych szkoleniowych.

Może on korzystać z metod regularyzacji, które penalizują różne części algorytmu i ogólnie poprawiają wydajność algorytmu poprzez redukcję przepasowania.

W tej sekcji przyjrzymy się 4 ulepszeniom podstawowego gradient boosting:

1. Wężenia drzewa
2. Shrinkage
3. Próbkowanie losowe
4. Uczenie penalizowane

Wężenia drzewa

Ważne jest, aby słabi uczący się mieli umiejętności, ale pozostali słabi.

Istnieje wiele sposobów, na które drzewa mogą być ograniczone.

Dobrą ogólną heurystyką jest to, że im bardziej ograniczone jest tworzenie drzew, tym więcej drzew będzie potrzebnych w modelu i odwrotnie, gdzie mniej ograniczone są poszczególne drzewa, tym mniej drzew będzie potrzebnych.

Poniżej znajdują się pewne ograniczenia, które można nałożyć na konstrukcję drzew decyzyjnych:

• Liczba drzew, generalnie dodawanie większej liczby drzew do modelu może być bardzo powolne do overfit. Zaleca się dodawanie drzew do momentu, gdy nie obserwuje się dalszej poprawy.
• Głębokość drzewa, głębsze drzewa są bardziej złożonymi drzewami i preferowane są krótsze drzewa. Generalnie, lepsze wyniki obserwuje się przy 4-8 poziomach.
• Liczba węzłów lub liczba liści, podobnie jak głębokość, może to ograniczyć rozmiar drzewa, ale nie jest ograniczone do symetrycznej struktury, jeśli używane są inne ograniczenia.
• Liczba obserwacji na podział nakłada minimalne ograniczenie na ilość danych szkoleniowych w węźle szkoleniowym, zanim podział może być rozważony
• Minimalna poprawa do straty jest ograniczeniem na poprawę każdego podziału dodanego do drzewa.

2. Aktualizacje ważone

Prognozy każdego drzewa są kolejno sumowane.

Wkład każdego drzewa do tej sumy może być ważony, aby spowolnić uczenie się przez algorytm. Waga ta nazywana jest kurczeniem lub współczynnikiem uczenia.

Każda aktualizacja jest po prostu skalowana przez wartość „parametru współczynnika uczenia v”

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

Efekt jest taki, że uczenie jest spowolnione, z kolei wymagają więcej drzew, aby być dodane do modelu, z kolei trwa dłużej do szkolenia, zapewniając konfigurację kompromisu między liczbą drzew i szybkość uczenia.

Zmniejszanie wartości v zwiększa najlepszą wartość dla M .

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

Powszechne są małe wartości w zakresie od 0,1 do 0,3, jak również wartości mniejsze niż 0,1.

Podobnie do współczynnika uczenia w optymalizacji stochastycznej, kurczenie zmniejsza wpływ każdego pojedynczego drzewa i pozostawia przestrzeń dla przyszłych drzew w celu poprawy modelu.

– Stochastic Gradient Boosting , 1999

Stochastic Gradient Boosting

Dużym wglądem w zespoły baggingowe i las losowy było umożliwienie chciwego tworzenia drzew z podpróbek zbioru danych treningowych.

Tę samą zaletę można wykorzystać do zmniejszenia korelacji między drzewami w sekwencji w modelach gradient boosting.

Ta odmiana boostingu nazywana jest stochastycznym gradient boosting.

przy każdej iteracji losowana jest podpróba danych treningowych (bez zastępowania) z pełnego zbioru danych treningowych. Losowo wybrana podpróba jest następnie używana, zamiast pełnej próbki, do dopasowania uczącego bazowego.

– Stochastic Gradient Boosting , 1999

Kilka wariantów stochastycznego boostingu, które mogą być użyte:

• Próbkowanie wierszy przed utworzeniem każdego drzewa.
• Próbkowanie kolumn przed utworzeniem każdego drzewa
• Próbkowanie kolumn przed rozważeniem każdego podziału.

Ogólnie, agresywne podpróbkowanie, takie jak wybranie tylko 50% danych, okazało się korzystne.

Zgodnie z opiniami użytkowników, użycie podpróbkowania kolumn zapobiega nadmiernemu dopasowaniu nawet bardziej niż tradycyjne podpróbkowanie wierszy

– XGBoost: A Scalable Tree Boosting System, 2016

Penalized Gradient Boosting

Dodatkowe ograniczenia mogą być nałożone na sparametryzowane drzewa oprócz ich struktury.

Klasyczne drzewa decyzyjne, takie jak CART, nie są używane jako słabe uczące, zamiast tego używana jest zmodyfikowana forma zwana drzewem regresyjnym, która ma wartości liczbowe w węzłach liści (zwanych również węzłami końcowymi). Wartości w liściach drzew mogą być nazywane wagami w niektórych literaturach.

Jako takie, wartości wag liści drzew mogą być regularyzowane przy użyciu popularnych funkcji regularyzacji, takich jak:

• L1 regularyzacja wag.
• L2 regularyzacja wag.

Dodatkowy termin regularyzacji pomaga wygładzić końcowe wyuczone wagi, aby uniknąć nadmiernego dopasowania. Intuicyjnie, uregulowany cel będzie miał tendencję do wyboru modelu wykorzystującego proste i predykcyjne funkcje.

– XGBoost: A Scalable Tree Boosting System, 2016

Gradient Boosting Resources

Gradient boosting jest fascynującym algorytmem i jestem pewien, że chcesz zagłębić się w ten temat.

W tej sekcji wymieniono różne zasoby, z których możesz skorzystać, aby dowiedzieć się więcej o algorytmie gradient boosting.

Gradient Boosting Videos

• Gradient Boosting Machine Learning, Trevor Hastie, 2014
• Gradient Boosting, Alexander Ihler, 2012
• GBM, John Mount, 2015
• Learning: Boosting, MIT 6.034 Artificial Intelligence, 2010
• xgboost: An R package for Fast and Accurate Gradient Boosting, 2016
• XGBoost: A Scalable Tree Boosting System, Tianqi Chen, 2016

Gradient Boosting in Textbooks

• Section 8.2.3 Boosting, page 321, An Introduction to Statistical Learning: with Applications in R.
• Sekcja 8.6 Boosting, strona 203, Applied Predictive Modeling.
• Sekcja 14.5 Stochastic Gradient Boosting, strona 390, Applied Predictive Modeling.
• Sekcja 16.4 Boosting, strona 556, Machine Learning: A Probabilistic Perspective
• Rozdział 10 Boosting and Additive Trees, strona 337, The Elements of Statistical Learning: Data Mining, Inference, and Prediction

Gradient Boosting Papers

• Thoughts on Hypothesis Boosting , Michael Kearns, 1988
• A decision-theoretic generalization of on-line learning and an application to boosting , 1995
• Arcing the edge , 1998
• Stochastic Gradient Boosting , 1999
• Boosting Algorithms as Gradient Descent in Function Space , 1999

Gradient Boosting Slides

• Introduction to Boosted Trees, 2014
• A Gentle Introduction to Gradient Boosting, Cheng Li

Gradient Boosting Web Pages

• Boosting (uczenie maszynowe)
• Gradient boosting
• Gradient Tree Boosting in scikit-learn

Podsumowanie

W tym poście odkryłeś algorytm gradient boosting do modelowania predykcyjnego w uczeniu maszynowym.

W szczególności, dowiedziałeś się:

• Historia boostingu w teorii uczenia i AdaBoost.
• Jak algorytm gradient boosting działa z funkcją straty, słabymi uczącymi i modelem addytywnym.
• Jak poprawić wydajność gradient boosting za pomocą regularizacji.

Masz jakieś pytania dotyczące algorytmu gradient boosting lub tego wpisu? Zadaj pytania w komentarzach, a ja dołożę wszelkich starań, aby na nie odpowiedzieć.