En försiktig introduktion till Gradient Boosting-algoritmen för maskininlärning

Tweet Share Share Share

Sist uppdaterad den 15 augusti 2020

Gradient Boosting är en av de mest kraftfulla teknikerna för att bygga prediktiva modeller.

I det här inlägget kommer du att upptäcka gradient boosting-algoritmen för maskininlärning och få en försiktig introduktion till varifrån den kommer och hur den fungerar.

När du har läst det här inlägget kommer du att veta:

Hur boosting kommer från inlärningsteorin och AdaBoost.
Hur gradient boosting fungerar, inklusive förlustfunktionen, svaga inlärare och den additiva modellen.
Hur man förbättrar prestandan jämfört med basalgoritmen med olika regleringsscheman.

Kickstart ditt projekt med min nya bok XGBoost With Python, inklusive steg-för-steg-handledning och Python-källkodfiler för alla exempel.

Vi sätter igång.

En mild introduktion till Gradient Boosting-algoritmen för maskininlärning
Foto av brando.n, some rights reserved.

Behövs hjälp med XGBoost i Python?

Tag min kostnadsfria 7-dagars e-postkurs och upptäck xgboost (med exempelkod).

Klicka på för att anmäla dig nu och få en kostnadsfri PDF-version av kursen i form av en e-bok.

Starta din kostnadsfria minikurs nu!

Uppkomsten av boosting

Idén om boosting kom ur tanken om huruvida en svag inlärare kan modifieras för att bli bättre.

Michael Kearns formulerade målet som ”Hypothesis Boosting Problem” och angav målet ur en praktisk synvinkel som:

… en effektiv algoritm för att omvandla relativt dåliga hypoteser till mycket bra hypoteser

– Thoughts on Hypothesis Boosting , 1988

En svag hypotes eller svag inlärare definieras som en hypotes vars resultat är åtminstone något bättre än slumpen.

Dessa idéer bygger på Leslie Valiants arbete med distributionsfri eller Probably Approximately Correct (PAC) inlärning, ett ramverk för att undersöka komplexiteten hos problem med maskininlärning.

Hypothesis boosting var idén om att filtrera observationer, lämna de observationer som den svaga inläraren kan hantera och fokusera på att utveckla nya svaga inlärare för att hantera de återstående svåra observationerna.

Idén är att använda den svaga inlärningsmetoden flera gånger för att få en följd av hypoteser, där var och en av dem är återfokuserad på de exempel som de tidigare fann svåra och felklassificerade. … Observera dock att det inte alls är uppenbart hur detta kan göras

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

AdaBoost the First Boosting Algorithm

Den första förverkligandet av boosting som såg stora framgångar i tillämpningen var Adaptive Boosting eller AdaBoost förkortat.

Boosting hänvisar till detta allmänna problem att ta fram en mycket exakt prediktionsregel genom att kombinera grova och måttligt felaktiga tumregler.

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

De svaga lärarna i AdaBoost är beslutsträd med en enda delning, som kallas decision stumps för att de är korta.

AdaBoost fungerar genom att väga observationerna och lägga mer vikt på svårklassificerade instanser och mindre vikt på de instanser som redan hanterats väl. Nya svaga inlärare läggs till sekventiellt som fokuserar sin träning på de svårare mönstren.

Detta innebär att prov som är svåra att klassificera får allt större vikt tills algoritmen identifierar en modell som korrekt klassificerar dessa prov

– Applied Predictive Modeling, 2013

Förutsägelser görs genom majoritetsomröstning av de svaga inlärarnas förutsägelser, viktade efter deras individuella noggrannhet. Den mest framgångsrika formen av AdaBoost-algoritmen var för binära klassificeringsproblem och kallades AdaBoost.M1.

Du kan lära dig mer om AdaBoost-algoritmen i inlägget:

Boosting and AdaBoost for Machine Learning.

Generalisering av AdaBoost som Gradient Boosting

AdaBoost och relaterade algoritmer omarbetades i en statistisk ram först av Breiman som kallade dem ARCing-algoritmer.

Arcing är en akronym för Adaptive Reweighting and Combining. Varje steg i en arcing-algoritm består av en viktad minimering följt av en ny beräkning av och .

– Prediction Games and Arching Algorithms , 1997

Denna ram utvecklades vidare av Friedman och kallades Gradient Boosting Machines. Senare kallad bara gradient boosting eller gradient tree boosting.

Den statistiska ramen kastade boosting som ett numeriskt optimeringsproblem där målet är att minimera modellens förlust genom att lägga till svaga inlärare med hjälp av ett gradient descent-liknande förfarande.

Denna klass av algoritmer beskrevs som en stegvis additiv modell. Detta beror på att en ny svag inlärare läggs till i taget och befintliga svaga inlärare i modellen fryses och lämnas oförändrade.

Bemärk att denna stegvisa strategi skiljer sig från stegvisa tillvägagångssätt som återjusterar tidigare inmatade termer när nya läggs till.

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

Generaliseringen gjorde det möjligt att använda godtyckliga differentierbara förlustfunktioner, vilket utvidgade tekniken bortom binära klassificeringsproblem för att stödja regression, klassificering av flera klasser med mera.

Hur Gradient Boosting fungerar

Gradient Boosting innefattar tre delar:

En förlustfunktion som ska optimeras.
En svag inlärare som ska göra förutsägelser.
En additiv modell för att lägga till svaga inlärare för att minimera förlustfunktionen.

Förlustfunktion

Förlustfunktionen som används beror på vilken typ av problem som ska lösas.

Den måste vara differentierbar, men många standardförlustfunktioner stöds och du kan definiera en egen.

Till exempel kan regression använda ett kvadrerat fel och klassificering kan använda logaritmisk förlust.

En fördel med gradient boosting-ramverket är att en ny boosting-algoritm inte behöver härledas för varje förlustfunktion som kanske vill användas, istället är det ett tillräckligt generiskt ramverk för att vilken differentierbar förlustfunktion som helst kan användas.

Weak Learner

Det är beslutsträd som används som den svaga inläraren i gradient boosting.

Specifikt används regressionsträd som ger ut verkliga värden för uppdelningar och vars utdata kan adderas, vilket gör att efterföljande modellers utdata kan läggas till och ”korrigera” residualerna i förutsägelserna.

Träden konstrueras på ett girigt sätt och väljer de bästa delningspunkterna baserat på renhetsvärden som Gini eller för att minimera förlusten.

I början, till exempel i fallet AdaBoost, användes mycket korta beslutsträd som bara hade en enda delning, en så kallad beslutsstump. Större träd kan användas i allmänhet med 4-8 nivåer.

Det är vanligt att begränsa de svaga lärarna på särskilda sätt, t.ex. genom ett maximalt antal lager, noder, delningar eller bladnoder.

Detta är för att se till att lärarna förblir svaga, men att de fortfarande kan konstrueras på ett girigt sätt.

Additiv modell

Träden läggs till ett i taget och befintliga träd i modellen ändras inte.

En gradientnedgångsprocedur används för att minimera förlusten när träd läggs till.

Traditionsenligt används gradientnedgång för att minimera en uppsättning parametrar, t.ex. koefficienter i en regressionsekvation eller vikter i ett neuralt nätverk. Efter beräkning av felet eller förlusten uppdateras vikterna för att minimera felet.

Istället för parametrar har vi undermodeller med svag inlärare eller mer specifikt beslutsträd. Efter beräkning av förlusten måste vi, för att utföra gradientnedgångsproceduren, lägga till ett träd till modellen som minskar förlusten (dvs. följer gradienten). Vi gör detta genom att parametrisera trädet, sedan ändrar vi trädets parametrar och rör oss i rätt riktning genom att (minska den kvarvarande förlusten.

Generellt kallas detta tillvägagångssätt för funktionell gradientdescent eller gradientdescent med funktioner.

Ett sätt att producera en viktad kombination av klassificerare som optimerar är genom gradient descent in function space

– Boosting Algorithms as Gradient Descent in Function Space , 1999

Utfallet för det nya trädet läggs sedan till utfallet för den befintliga sekvensen av träd i ett försök att korrigera eller förbättra modellens slutresultat.

Ett fast antal träd läggs till eller så upphör träningen när förlusten når en acceptabel nivå eller när den inte längre förbättras på ett externt valideringsdataset.

Förbättringar av grundläggande Gradient Boosting

Gradient Boosting är en girig algoritm och kan snabbt överanpassa ett träningsdataset.

Den kan dra nytta av regulariseringsmetoder som straffar olika delar av algoritmen och generellt sett förbättrar algoritmens prestanda genom att minska överanpassning.

I det här avsnittet kommer vi att titta på 4 förbättringar av grundläggande gradient boosting:

Tree Constraints
Shrinkage
Random sampling
Penalized Learning

Tree Constraints

Det är viktigt att de svaga inlärarna har färdigheter men förblir svaga.

Det finns ett antal sätt att begränsa träden.

En bra allmän heuristik är att ju mer begränsat trädskapandet är, desto fler träd kommer du att behöva i modellen, och tvärtom, där mindre begränsade enskilda träd, desto färre träd kommer att behövas.

Nedan följer några begränsningar som kan införas vid skapandet av beslutsträd:

Antal träd, generellt sett kan det vara mycket långsamt att lägga till fler träd i modellen för att överanpassa den. Rådet är att fortsätta att lägga till träd tills ingen ytterligare förbättring observeras.
Träddjup, djupare träd är mer komplexa träd och kortare träd är att föredra. Generellt sett ses bättre resultat med 4-8 nivåer.
Antal noder eller antal blad, liksom träddjupet kan detta begränsa trädets storlek, men är inte begränsat till en symmetrisk struktur om andra begränsningar används.
Antal observationer per delning innebär en minsta begränsning av mängden träningsdata vid en träningsnod innan en delning kan övervägas
Minsta förbättring av förlust är en begränsning av förbättringen av varje delning som läggs till ett träd.

2. Viktade uppdateringar

Prediktionerna för varje träd adderas sekventiellt.

Bidraget från varje träd till denna summa kan viktas för att sakta ner algoritmens inlärning. Denna viktning kallas krympning eller inlärningshastighet.

Varje uppdatering skalas helt enkelt med värdet av ”inlärningshastighetsparametern v”

– Greedy Function Approximation: Effekten är att inlärningen saktas ner, vilket i sin tur kräver att fler träd läggs till i modellen, vilket i sin tur tar längre tid att träna, vilket ger en konfigurationsmässig avvägning mellan antalet träd och inlärningshastigheten.

Den som minskar värdet på v ökar det bästa värdet för M.

– Greedy Function Approximation: Greedy Function Approximation: A Gradient Boosting Machine, 1999

– Greedy Function Approximation: A Gradient Boosting Machine: A Gradient Boosting Machine, 1999

A Gradient Boosting Machine , 1999

Det är vanligt att ha små värden i intervallet 0,1 till 0,3, samt värden mindre än 0,1.

Som liknar en inlärningshastighet i stokastisk optimering minskar krympning inflytandet av varje enskilt träd och lämnar utrymme för framtida träd för att förbättra modellen.

– Stochastic Gradient Boosting , 1999

Stochastic Gradient Boosting

En stor insikt i bagging ensembles och random forest var att låta träd skapas girigt från delprov av träningsdatamängden.

Den här fördelen kan användas för att minska korrelationen mellan träden i sekvensen i gradient boosting-modeller.

Denna variant av boosting kallas stochastic gradient boosting.

Vid varje iteration dras ett delprov av träningsdatan slumpmässigt (utan ersättning) från den fullständiga träningsdatasatsen. Det slumpmässigt utvalda delprovet används sedan, i stället för det fullständiga provet, för att anpassa basläraren.

– Stochastic Gradient Boosting , 1999

Flera varianter av stochastic boosting som kan användas:

Subsampling av rader före skapandet av varje träd.
Subsampling av kolumner före skapandet av varje träd.
Subsampling av kolumner innan man överväger varje uppdelning.

Generellt sett har aggressiv underprovtagning, t.ex. att välja endast 50 % av data, visat sig vara fördelaktigt.

Enligt användarnas återkoppling förhindrar användningen av underprovtagning av kolumner överanpassning i ännu högre grad än den traditionella underprovtagningen av rader

– XGBoost: A Scalable Tree Boosting System, 2016

Penalized Gradient Boosting

Det går att införa ytterligare begränsningar för de parametriserade träden utöver deras struktur.

Klassiska beslutsträd som CART används inte som svaga inlärare, i stället används en modifierad form som kallas regressionsträd som har numeriska värden i bladnoderna (även kallade terminala noder). Värdena i trädens blad kan i viss litteratur kallas för vikter.

Som sådan kan trädens bladviktsvärden regleras med hjälp av populära regleringsfunktioner, till exempel:

L1 reglering av vikter.
L2 reglering av vikter.

Den extra regleringstermen hjälper till att utjämna de slutliga inlärda vikterna för att undvika överanpassning. Intuitivt sett tenderar det reglerade målet att välja en modell som använder enkla och förutsägbara funktioner.

– XGBoost: A Scalable Tree Boosting System, 2016

Gradient Boosting Resources

Gradient Boosting är en fascinerande algoritm och jag är säker på att du vill fördjupa dig.

Detta avsnitt listar olika resurser som du kan använda för att lära dig mer om gradient boosting-algoritmen.

Gradient Boosting Videos

Gradient Boosting Machine Learning, Trevor Hastie, 2014
Gradient Boosting, Alexander Ihler, 2012
GBM, John Mount, 2015
Learning: Förstärkning, MIT 6.034 Artificiell intelligens, 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

Avsnitt 8.2.3 Boosting, sida 321, An Introduction to Statistical Learning: with Applications in R.
Avsnitt 8.6 Boosting, sidan 203, Applied Predictive Modeling.
Avsnitt 14.5 Stochastic Gradient Boosting, sidan 390, Applied Predictive Modeling.
Avsnitt 16.4 Boosting, sidan 556, Machine Learning: A Probabilistic Perspective
Kapitel 10 Boosting and Additive Trees, sidan 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

Introduktion till boostade träd, 2014
En mild introduktion till Gradient Boosting, Cheng Li

Gradient Boosting Web Pages

Boosting (maskininlärning)
Gradient boosting
Gradient Tree Boosting in scikit-learn

Summary

I det här inlägget har du upptäckt gradient boosting-algoritmen för prediktiv modellering inom maskininlärning.

Specifikt har du lärt dig:

Historien om boosting i inlärningsteori och AdaBoost.
Hur gradient boosting-algoritmen fungerar med en förlustfunktion, svaga inlärare och en additiv modell.
Hur man förbättrar prestanda för gradient boosting med reglering.

Har du några frågor om gradient boosting-algoritmen eller om det här inlägget? Ställ dina frågor i kommentarerna så ska jag göra mitt bästa för att svara.

Upptäck algoritmen som vinner tävlingar!

Utveckla dina egna XGBoost-modeller på några minuter

…med bara några få rader Python

Upptäck hur i min nya Ebook:
XGBoost With Python

Det täcker självstudier som:
Algoritmens grunder, skalning, hyperparametrar och mycket mer…

Bring kraften i XGBoost till dina egna projekt

Skippa det akademiska. Bara resultat.

Se vad som finns inuti