En blid introduktion til Gradient Boosting-algoritmen til maskinlæring

Tweet Share Share Share

Sidst opdateret den 15. august 2020

Gradient boosting er en af de mest effektive teknikker til opbygning af prædiktive modeller.

I dette indlæg vil du opdage gradient boosting-maskinindlæringsalgoritmen og få en blid introduktion til, hvor den kommer fra, og hvordan den fungerer.

Når du har læst dette indlæg, vil du vide:

Oprindelsen af boosting fra læringsteori og AdaBoost.
Hvordan gradient boosting fungerer, herunder tabsfunktionen, weak learners og den additive model.
Hvordan man forbedrer ydeevnen i forhold til basisalgoritmen med forskellige regulariseringsordninger.

Kick-start dit projekt med min nye bog XGBoost With Python, herunder trinvise vejledninger og Python-kildekodefilerne til alle eksempler.

Lad os komme i gang.

En blid introduktion til Gradient Boosting-algoritmen til maskinlæring
Foto af brando.n, some rights reserved.

Har du brug for hjælp til XGBoost i Python?

Tag mit gratis 7-dages e-mail-kursus, og opdag xgboost (med eksempelkode).

Klik for at tilmelde dig nu og få også en gratis PDF Ebook-version af kurset.

Start dit GRATIS minikursus nu!

Oprindelsen af boosting

Ideen om boosting opstod ud fra tanken om, hvorvidt en svag elev kan ændres til at blive bedre.

Michael Kearns formulerede målet som “Hypothesis Boosting Problem”, der angiver målet fra et praktisk synspunkt som:

… en effektiv algoritme til at konvertere relativt dårlige hypoteser til meget gode hypoteser

– Tanker om Hypothesis Boosting , 1988

En svag hypotese eller svag lærende defineres som en, hvis præstation er mindst en smule bedre end tilfældighederne.

Disse idéer byggede på Leslie Valiants arbejde om distributionsfri eller Probably Approximately Correct (PAC) læring, en ramme til undersøgelse af kompleksiteten af maskinlæringsproblemer.

Hypothesis boosting var ideen om at filtrere observationer, efterlade de observationer, som den svage lærer kan håndtere, og fokusere på at udvikle nye svage lærer til at håndtere de resterende vanskelige observationer.

Ideen er at bruge den svage læringsmetode flere gange for at få en række hypoteser, der hver især er fokuseret på de eksempler, som de foregående fandt vanskelige og fejlklassificerede. … Bemærk dog, at det slet ikke er indlysende, hvordan dette kan gøres

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

AdaBoost the First Boosting Algorithm

Den første realisering af boosting, der oplevede stor succes i anvendelsen, var Adaptive Boosting eller AdaBoost forkortet.

Boosting henviser til dette generelle problem med at fremstille en meget præcis forudsigelsesregel ved at kombinere grove og moderat upræcise tommelfingerregler.

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

De svage lærere i AdaBoost er beslutningstræer med en enkelt opdeling, kaldet decision stumps for deres korthed.

AdaBoost fungerer ved at vægte observationerne, idet der lægges mere vægt på svært klassificerbare forekomster og mindre vægt på dem, der allerede er håndteret godt. Nye svage lærere tilføjes sekventielt, som fokuserer deres træning på de vanskeligere mønstre.

Det betyder, at prøver, der er vanskelige at klassificere, får stadig større vægte, indtil algoritmen identificerer en model, der klassificerer disse prøver korrekt

– Applied Predictive Modeling, 2013

Forudsigelser foretages ved flertalsafstemning af de svage læreres forudsigelser, vægtet efter deres individuelle nøjagtighed. Den mest vellykkede form af AdaBoost-algoritmen var til binære klassifikationsproblemer og blev kaldt AdaBoost.M1.

Du kan lære mere om AdaBoost-algoritmen i indlægget:

Boosting and AdaBoost for Machine Learning.

Generalisering af AdaBoost som Gradient Boosting

AdaBoost og beslægtede algoritmer blev omformet i en statistisk ramme først af Breiman, der kaldte dem ARCing-algoritmer.

Arcing er en forkortelse for Adaptive Reweighting and Combining (Adaptiv genvejning og kombination). Hvert trin i en arcing-algoritme består af en vægtet minimering efterfulgt af en genberegning af og .

– Prediction Games and Arching Algorithms , 1997

Denne ramme blev videreudviklet af Friedman og kaldt Gradient Boosting Machines. Senere kaldet bare gradient boosting eller gradient tree boosting.

Den statistiske ramme kastede boosting som et numerisk optimeringsproblem, hvor målet er at minimere tabet af modellen ved at tilføje svage lærere ved hjælp af en gradient descent-lignende procedure.

Denne klasse af algoritmer blev beskrevet som en trinvis additiv model. Dette skyldes, at der tilføjes en ny svag lærling ad gangen, og at eksisterende svage lærlinge i modellen fastfryses og forbliver uændrede.

Bemærk, at denne trinvise strategi adskiller sig fra trinvise tilgange, der efterjusterer tidligere indtastede termer, når der tilføjes nye.

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

Generaliseringen gjorde det muligt at anvende vilkårlige differentierbare tabsfunktioner, hvilket udvidede teknikken ud over binære klassifikationsproblemer til at understøtte regression, klassifikation af flere klasser og mere.

Hvordan Gradient Boosting fungerer

Gradient boosting involverer tre elementer:

En tabsfunktion, der skal optimeres.
En svag læringspartner, der skal foretage forudsigelser.
En additiv model til at tilføje svage lærere for at minimere tabsfunktionen.

Lossfunktion

Den anvendte tabsfunktion afhænger af den type problem, der skal løses.

Den skal være differentierbar, men mange standard tabsfunktioner understøttes, og du kan definere dine egne.

For eksempel kan regression bruge en kvadreret fejl, og klassifikation kan bruge logaritmisk tab.

En fordel ved gradient boosting-rammen er, at der ikke skal udledes en ny boosting-algoritme for hver tabsfunktion, der eventuelt ønskes anvendt, i stedet er det en ramme, der er generisk nok til, at enhver differentierbar tabsfunktion kan anvendes.

Weak Learner

Decision trees anvendes som weak learner i gradient boosting.

Specifikt anvendes regressionstræer, der udsender reelle værdier for opdelinger, og hvis output kan lægges sammen, så efterfølgende modellers output kan lægges sammen og “korrigere” residualerne i forudsigelserne.

Træer konstrueres på en grådig måde, hvor de bedste opdelingspunkter vælges ud fra renhedsscorer som Gini eller for at minimere tabet.

I første omgang, som f.eks. i tilfældet med AdaBoost, blev der anvendt meget korte beslutningstræer, der kun havde en enkelt opdeling, kaldet en beslutningsstump. Der kan generelt anvendes større træer med 4-8 niveauer.

Det er almindeligt at begrænse de svage lærere på bestemte måder, f.eks. et maksimalt antal lag, knuder, splits eller bladknuder.

Dette er for at sikre, at lærerne forbliver svage, men stadig kan konstrueres på en greedy-måde.

Additiv model

Træer tilføjes et ad gangen, og eksisterende træer i modellen ændres ikke.

Der anvendes en gradientafstigningsprocedure til at minimere tabet ved tilføjelse af træer.

Traditionelt anvendes gradientafstigning til at minimere et sæt parametre, f.eks. koefficienterne i en regressionsligning eller vægte i et neuralt netværk. Efter beregning af fejl eller tab opdateres vægtene for at minimere denne fejl.

I stedet for parametre har vi svage lærende undermodeller eller mere specifikt beslutningstræer. Efter beregning af tabet skal vi, for at udføre gradientafstigningsproceduren, tilføje et træ til modellen, der reducerer tabet (dvs. følger gradienten). Det gør vi ved at parametrisere træet, hvorefter vi ændrer træets parametre og bevæger os i den rigtige retning ved at (reducere resttabet.

Generelt kaldes denne fremgangsmåde for funktionel gradientafstigning eller gradientafstigning med funktioner.

En måde at fremstille en vægtet kombination af klassifikatorer, der optimerer, er ved gradientafstigning i funktionsrummet

– Boosting Algorithms as Gradient Descent in Function Space , 1999

Outputtet for det nye træ tilføjes derefter til outputtet for den eksisterende sekvens af træer i et forsøg på at korrigere eller forbedre modellens endelige output.

Et fast antal træer tilføjes, eller træningen stopper, når tabet når et acceptabelt niveau eller ikke længere forbedres på et eksternt valideringsdatasæt.

Forbedringer af grundlæggende Gradient Boosting

Gradient Boosting er en grådig algoritme og kan hurtigt overpasse et træningsdatasæt.

Den kan drage fordel af reguleringsmetoder, der straffer forskellige dele af algoritmen og generelt forbedrer algoritmens ydeevne ved at reducere overtilpasning.

I dette dette afsnit vil vi se på 4 forbedringer af den grundlæggende gradient boosting:

Tree Constraints
Shrinkage
Random sampling
Penalized Learning

Tree Constraints

Det er vigtigt, at de svage lærere har færdigheder, men forbliver svage.

Der er en række måder, hvorpå træerne kan begrænses.

En god generel heuristik er, at jo mere begrænset træoprettelsen er, jo flere træer har man brug for i modellen, og omvendt, hvor mindre begrænsede enkelte træer, jo færre træer er der brug for.

Nedenfor er nogle begrænsninger, der kan pålægges konstruktionen af beslutningstræer:

Antal træer, generelt kan tilføjelse af flere træer til modellen være meget langsom til at overpasse. Rådet er at blive ved med at tilføje træer, indtil der ikke observeres nogen yderligere forbedring.
Trædybde, dybere træer er mere komplekse træer, og kortere træer er at foretrække. Generelt ses bedre resultater med 4-8 niveauer.
Antal knuder eller antal blade, ligesom dybden kan dette begrænse træets størrelse, men er ikke tvunget til en symmetrisk struktur, hvis der anvendes andre begrænsninger.
Antal observationer pr. split pålægger en minimumsbegrænsning på mængden af træningsdata ved et træningsknudepunkt, før en split kan overvejes
Minimumsforbedring af tab er en begrænsning på forbedringen af enhver split, der tilføjes til et træ.

2. Vægtede opdateringer

Prædiktionerne for hvert træ lægges sammen i rækkefølge.

Det enkelte træs bidrag til denne sum kan vægtes for at bremse algoritmens indlæring. Denne vægtning kaldes en krympning eller en indlæringshastighed.

Hver opdatering skaleres simpelthen med værdien af “indlæringshastighedsparameteren v”

– Greedy Function Approximation: Effekten er, at indlæringen bliver langsommere, hvilket igen kræver, at der tilføjes flere træer til modellen, hvilket igen tager længere tid at træne, hvilket giver en konfiguration af kompromiset mellem antallet af træer og indlæringshastigheden.

Den bedste værdi for M øges ved at sænke værdien af v.

– Greedy Function Approximation: Greedy Function Approximation: En gradient boosting machine , 1999

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

Det er almindeligt at have små værdier i intervallet 0,1 til 0,3 samt værdier mindre end 0,1.

Som en læringshastighed i stokastisk optimering reducerer krympning indflydelsen af hvert enkelt træ og efterlader plads til fremtidige træer til at forbedre modellen.

– Stochastic Gradient Boosting , 1999

Stochastic Gradient Boosting

En stor indsigt i bagging ensembler og random forest var at give mulighed for at oprette træer på grådig vis fra delprøver af træningsdatasættet.

Denne samme fordel kan bruges til at reducere korrelationen mellem træerne i sekvensen i gradient boosting-modeller.

Denne variation af boosting kaldes stochastic gradient boosting.

I hver iteration trækkes en delprøve af træningsdataene tilfældigt (uden erstatning) fra det fulde træningsdatasæt. Den tilfældigt udvalgte delprøve bruges derefter i stedet for den fulde prøve til at tilpasse basislæreren.

– Stochastic Gradient Boosting , 1999

Et par varianter af stochastic boosting, der kan anvendes:

Subprøve rækker, før hvert træ oprettes.
Subprøve kolonner, før hvert træ oprettes
Subprøve kolonner, før hvert split overvejes.

Generelt har aggressiv underprøvetagning, f.eks. ved kun at vælge 50 % af dataene, vist sig at være gavnlig.

I henhold til brugerfeedback forhindrer brugen af kolonneunderprøvetagning overpasning i endnu højere grad end den traditionelle rækkeunderprøvetagning

– XGBoost: A Scalable Tree Boosting System, 2016

Penalized Gradient Boosting

Der kan pålægges yderligere begrænsninger på de parameteriserede træer ud over deres struktur.

Klassiske beslutningstræer som CART anvendes ikke som weak learners, i stedet anvendes en modificeret form kaldet et regressionstræ, der har numeriske værdier i bladknuderne (også kaldet terminalknuder). Værdierne i træernes blade kan i noget litteratur kaldes vægte.

Som sådan kan træernes bladvægtværdier reguleres ved hjælp af populære reguleringsfunktioner, såsom:

L1 regulering af vægte.
L2 regulering af vægte.

Den ekstra reguleringsterm hjælper med at udjævne de endelige lærte vægte for at undgå overtilpasning. Intuitivt vil det regulerede mål have en tendens til at vælge en model, der anvender enkle og forudsigelige funktioner.

– XGBoost: A Scalable Tree Boosting System, 2016

Gradient Boosting Resources

Gradient boosting er en fascinerende algoritme, og jeg er sikker på, at du ønsker at gå dybere ned i dybden.

Dette afsnit indeholder en liste over forskellige ressourcer, som du kan bruge til at lære mere om gradient boosting-algoritmen.

Gradient Boosting-videoer

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, side 321, An Introduction to Statistical Learning: with Applications in R.
Afsnit 8.6 Boosting, side 203, Applied Predictive Modeling.
Afsnit 14.5 Stochastic Gradient Boosting, side 390, Applied Predictive Modeling.
Afsnit 16.4 Boosting, side 556, Machine Learning: A Probabilistic Perspective
Kapitel 10 Boosting and Additive Trees, side 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
Stokastisk gradientforstærkning , 1999
Boosting-algoritmer som gradientafstamning i funktionsrummet , 1999

Gradient Boosting Slides

Introduktion til boostede træer, 2014
A Gentle Introduction to Gradient Boosting, Cheng Li

Gradient Boosting Web Pages

Boosting (machine learning)
Gradient boosting
Gradient Tree Boosting in scikit-learn

Summary

I dette indlæg opdagede du gradient boosting-algoritmen til prædiktiv modellering i machine learning.

Specifikt har du lært:

Historien om boosting i læringsteori og AdaBoost.
Hvordan gradient boosting-algoritmen fungerer med en tabsfunktion, svage lærere og en additiv model.
Hvordan man forbedrer gradient boosting’s ydeevne med regularisering.

Har du spørgsmål om gradient boosting-algoritmen eller om dette indlæg? Stil dine spørgsmål i kommentarerne, og jeg vil gøre mit bedste for at svare.

Opdag algoritmen, der vinder konkurrencer!

Udvikle dine egne XGBoost-modeller på få minutter

…med blot et par linjer Python

Opdag hvordan i min nye E-bog:
XGBoost With Python

Den dækker selvstuderende tutorials som:
Algoritmens grundprincipper, skalering, hyperparametre og meget mere…

Bring kraften i XGBoost til dine egne projekter

Skip det akademiske. Just Results.

Se hvad der er inde i