A Gentle Introduction to the Gradient Boosting Algorithm for Machine Learning

Last Updated on August 15, 2020

Gradient boosting is een van de krachtigste technieken voor het bouwen van voorspellende modellen.

In dit bericht ontdekt u het gradient boosting machine learning-algoritme en krijgt u een voorzichtige inleiding in waar het vandaan komt en hoe het werkt.

Na het lezen van dit bericht weet u:

• De oorsprong van boosting uit de leertheorie en AdaBoost.
• Hoe gradient boosting werkt, inclusief de verliesfunctie, zwakke lerenden en het additieve model.
• Hoe de prestaties te verbeteren ten opzichte van het basis algoritme met verschillende regularisatie schema’s.

Kick-start je project met mijn nieuwe boek XGBoost With Python, inclusief stap-voor-stap tutorials en de Python broncode bestanden voor alle voorbeelden.

Let’s get started.

• Hulp nodig met XGBoost in Python?
• De oorsprong van Boosting
• AdaBoost the First Boosting Algorithm
• Generalisatie van AdaBoost als Gradient Boosting
• Hoe Gradient Boosting werkt
• Verliesfunctie
• Weak Learner
• Additief model
• Verbetering van Basis Gradient Boosting
• Tree Constraints
• 2. Gewogen updates
• Stochastic Gradient Boosting
• Penalized Gradient Boosting
• Gradient Boosting Resources
• Gradient Boosting Video’s
• Gradient Boosting in Textbooks
• Gradient Boosting Papers
• Gradient Boosting Slides
• Gradient Boosting Web Pages
• Samenvatting
• Ontdek het algoritme dat wedstrijden wint!
• Ontwikkel uw eigen XGBoost-modellen in enkele minuten
• Breng de kracht van XGBoost naar uw eigen projecten

Hulp nodig met XGBoost in Python?

Doe mee aan mijn gratis 7-daagse email cursus en ontdek xgboost (met voorbeeld code).

Klik nu om in te schrijven en ontvang ook een gratis PDF Ebook versie van de cursus.

Start Uw GRATIS mini-cursus nu!

De oorsprong van Boosting

Het idee van boosting kwam voort uit het idee of een zwakke leerling kan worden aangepast om beter te worden.

Michael Kearns verwoordde het doel als het “Hypothesis Boosting Problem”, waarbij hij het doel vanuit praktisch oogpunt omschreef als:

… een efficiënt algoritme voor het omzetten van relatief slechte hypothesen in zeer goede hypothesen

– Thoughts on Hypothesis Boosting , 1988

Een zwakke hypothese of zwakke leerling wordt gedefinieerd als een hypothese of leerling waarvan de prestaties ten minste iets beter zijn dan het toeval.

Deze ideeën bouwden voort op het werk van Leslie Valiant over distributievrij of Probably Approximately Correct (PAC) leren, een raamwerk voor het onderzoeken van de complexiteit van machine-leerproblemen.

Hypothesis boosting was het idee van het filteren van waarnemingen, waarbij de waarnemingen die de zwakke lerende aankan, worden overgelaten en de aandacht wordt gericht op het ontwikkelen van nieuwe zwakke leren om de resterende moeilijke waarnemingen aan te kunnen.

Het idee is om de zwakke leermethode verschillende keren te gebruiken om een opeenvolging van hypothesen te krijgen, waarbij elke hypothese opnieuw wordt gericht op de voorbeelden die de vorige moeilijk vonden en verkeerd classificeerden. … Merk echter op dat het helemaal niet duidelijk is hoe dit kan worden gedaan

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

AdaBoost the First Boosting Algorithm

De eerste realisatie van boosting die veel succes zag in de toepassing was Adaptive Boosting of kortweg AdaBoost.

Boosting verwijst naar dit algemene probleem van het produceren van een zeer nauwkeurige voorspellingsregel door het combineren van ruwe en matig onnauwkeurige vuistregels.

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

De zwakke leerlingen in AdaBoost zijn beslisbomen met een enkele splitsing, beslissingsstompen genoemd vanwege hun kortheid.

AdaBoost werkt door de waarnemingen te wegen, waarbij meer gewicht wordt toegekend aan moeilijk te classificeren gevallen en minder aan die welke al goed zijn afgehandeld. Er worden achtereenvolgens nieuwe zwakke leerlingen toegevoegd die hun training richten op de moeilijkere patronen.

Dit betekent dat monsters die moeilijk te classificeren zijn steeds grotere gewichten krijgen totdat het algoritme een model identificeert dat deze monsters correct classificeert

– Applied Predictive Modeling, 2013

Voorspellingen worden gedaan door meerderheidsstemming van de voorspellingen van de zwakke leerlingen, gewogen naar hun individuele nauwkeurigheid. De meest succesvolle vorm van het AdaBoost-algoritme was voor binaire classificatieproblemen en heette AdaBoost.M1.

U kunt meer te weten komen over het AdaBoost-algoritme in de post:

• Boosting en AdaBoost voor Machine Learning.

Generalisatie van AdaBoost als Gradient Boosting

AdaBoost en verwante algoritmen werden eerst door Breiman in een statistisch kader geherformuleerd, waarbij ze ARCing-algoritmen werden genoemd.

Arcing is een acroniem voor Adaptive Reweighting and Combining. Elke stap in een arcing-algoritme bestaat uit een gewogen minimalisering gevolgd door een herberekening van en .

– Prediction Games and Arching Algorithms , 1997

Dit kader werd verder ontwikkeld door Friedman en Gradient Boosting Machines genoemd. Later gewoon gradient boosting of gradient tree boosting genoemd.

Het statistische raamwerk giet boosting als een numeriek optimalisatieprobleem waarbij het doel is om het verlies van het model te minimaliseren door het toevoegen van zwakke lerenden met behulp van een gradient descent-achtige procedure.

Deze klasse van algoritmen werd beschreven als een fase-gewijs additief model. Dit komt omdat één nieuwe zwakke leerling per keer wordt toegevoegd en bestaande zwakke leerlingen in het model worden bevroren en ongewijzigd worden gelaten.

Merk op dat deze stapsgewijze strategie verschilt van stapsgewijze benaderingen die eerder ingevoerde termen opnieuw aanpassen wanneer nieuwe worden toegevoegd.

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

De veralgemening stond toe dat willekeurig differentieerbare verliesfuncties konden worden gebruikt, waardoor de techniek werd uitgebreid van binaire classificatieproblemen tot ondersteuning van regressie, multi-class classificatie en meer.

Hoe Gradient Boosting werkt

Gradient boosting omvat drie elementen:

1. Een verliesfunctie die moet worden geoptimaliseerd.
2. Een zwakke lerende om voorspellingen te doen.
3. Een additief model om zwakke lerenden toe te voegen om de verliesfunctie te minimaliseren.

Verliesfunctie

De gebruikte verliesfunctie hangt af van het type probleem dat wordt opgelost.

Het moet differentieerbaar zijn, maar veel standaard verliesfuncties worden ondersteund en u kunt uw eigen definiëren.

Voor regressie kan bijvoorbeeld een gekwadrateerde fout worden gebruikt en voor classificatie kan logaritmisch verlies worden gebruikt.

Een voordeel van het gradient boosting raamwerk is dat er geen nieuw boosting algoritme hoeft te worden afgeleid voor elke verliesfunctie die mogelijk wil worden gebruikt, in plaats daarvan is het een generiek genoeg raamwerk dat elke differentieerbare verliesfunctie kan worden gebruikt.

Weak Learner

Decision trees worden gebruikt als de weak learner in gradient boosting.

Specifiek worden regressiebomen gebruikt die reële waarden voor splitsingen geven en waarvan de output kan worden opgeteld, zodat de output van volgende modellen kan worden toegevoegd en de residuen in de voorspellingen kunnen worden “gecorrigeerd”.

Bomen worden op een hebzuchtige manier geconstrueerd, waarbij de beste splitsingspunten worden gekozen op basis van zuiverheidsscores zoals Gini of om het verlies te minimaliseren.

In eerste instantie, zoals in het geval van AdaBoost, werden zeer korte beslisbomen gebruikt die slechts een enkele splitsing hadden, een beslissingsstomp genoemd. Over het algemeen kunnen grotere bomen worden gebruikt met 4 tot 8 niveaus.

Het is gebruikelijk om de zwakke lerenden op specifieke manieren te beperken, zoals een maximum aantal lagen, knooppunten, splitsingen of bladknooppunten.

Dit is om ervoor te zorgen dat de lerenden zwak blijven, maar nog steeds op een hebzuchtige manier kunnen worden geconstrueerd.

Additief model

Bomen worden één voor één toegevoegd, en bestaande bomen in het model worden niet gewijzigd.

Een gradient descent procedure wordt gebruikt om het verlies bij het toevoegen van bomen te minimaliseren.

Traditioneel wordt gradient descent gebruikt om een set parameters te minimaliseren, zoals de coëfficiënten in een regressievergelijking of de gewichten in een neuraal netwerk. Na het berekenen van de fout of het verlies, worden de gewichten bijgewerkt om die fout te minimaliseren.

In plaats van parameters, hebben we zwakke leerling sub-modellen of meer specifiek beslissingsbomen. Na de berekening van het verlies moeten wij, om de gradiënt-afdalingsprocedure uit te voeren, een boom aan het model toevoegen die het verlies vermindert (d.w.z. de gradiënt volgt). Wij doen dit door de boom te parametriseren, vervolgens de parameters van de boom te wijzigen en in de goede richting te bewegen door (het resterende verlies te verminderen.

In het algemeen wordt deze aanpak functionele gradiëntafdaling of gradiëntafdaling met functies genoemd.

Een manier om een gewogen combinatie van classificeerders te produceren die optimaliseert, is door middel van gradiëntafdaling in de functieruimte

– Boosting Algorithms as Gradient Descent in Function Space , 1999

De output voor de nieuwe boom wordt vervolgens toegevoegd aan de output van de bestaande reeks bomen in een poging om de uiteindelijke output van het model te corrigeren of te verbeteren.

Een vast aantal bomen wordt toegevoegd of de training stopt zodra het verlies een aanvaardbaar niveau bereikt of niet langer verbetert op een externe validatiedataset.

Verbetering van Basis Gradient Boosting

Gradient boosting is een hebzuchtig algoritme en kan een trainingsdataset snel overfitten.

Het kan profiteren van regularisatiemethoden die verschillende delen van het algoritme bestraffen en in het algemeen de prestaties van het algoritme verbeteren door overfitting te verminderen.

In dit gedeelte kijken we naar 4 verbeteringen van basis gradient boosting:

1. Tree Constraints
2. Shrinkage
3. Random sampling
4. Penalized Learning

Tree Constraints

Het is belangrijk dat de zwakke lerenden vaardigheid hebben, maar zwak blijven.

Er zijn een aantal manieren waarop de bomen kunnen worden ingeperkt.

Een goede algemene heuristiek is dat hoe meer ingeperkt het maken van bomen is, hoe meer bomen je nodig zult hebben in het model, en omgekeerd, waar minder ingeperkte individuele bomen, hoe minder bomen er nodig zullen zijn.

Hieronder staan enkele beperkingen die aan de constructie van beslisbomen kunnen worden opgelegd:

• Aantal bomen, over het algemeen kan het toevoegen van meer bomen aan het model zeer langzaam tot overfit leiden. Het advies is bomen te blijven toevoegen tot geen verdere verbetering meer wordt waargenomen.
• Boomdiepte, diepere bomen zijn complexere bomen en kortere bomen verdienen de voorkeur. Over het algemeen worden betere resultaten gezien met 4-8 niveaus.
• Aantal knooppunten of aantal bladeren, net als diepte, kan dit de grootte van de boom beperken, maar is niet beperkt tot een symmetrische structuur als andere beperkingen worden gebruikt.
• Aantal waarnemingen per splitsing legt een minimumrestrictie op aan de hoeveelheid trainingsgegevens bij een trainingsknooppunt voordat een splitsing kan worden overwogen
• Minimale verbetering tot verlies is een restrictie op de verbetering van elke splitsing die aan een boom wordt toegevoegd.

2. Gewogen updates

De voorspellingen van elke boom worden sequentieel bij elkaar opgeteld.

De bijdrage van elke boom aan deze som kan worden gewogen om het leren door het algoritme te vertragen. Deze weging wordt een krimp of een leersnelheid genoemd.

Elke update wordt eenvoudigweg geschaald met de waarde van de “leersnelheidsparameter v”

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

Het effect is dat het leren wordt vertraagd, waardoor meer bomen aan het model moeten worden toegevoegd, waardoor het langer duurt om te trainen, waardoor een configuratie wordt verkregen die een compromis vormt tussen het aantal bomen en de leersnelheid.

Daling van de waarde van v verhoogt de beste waarde voor M.

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

Het is gebruikelijk om kleine waarden te hebben in het bereik van 0,1 tot 0,3, evenals waarden lager dan 0,1.

Gelijk aan een leersnelheid in stochastische optimalisatie, vermindert krimpen de invloed van elke individuele boom en laat ruimte voor toekomstige bomen om het model te verbeteren.

– Stochastic Gradient Boosting , 1999

Stochastic Gradient Boosting

Een groot inzicht in bagging ensembles en random forest was het toestaan van bomen om gulzig te worden gecreëerd uit deelmonsters van de trainingsdataset.

Ditzelfde voordeel kan worden gebruikt om de correlatie tussen de bomen in de reeks in gradient boosting-modellen te verminderen.

Deze variatie van boosting wordt stochastische gradient boosting genoemd.

Bij elke iteratie wordt een deelmonster van de trainingsgegevens willekeurig (zonder vervanging) getrokken uit de volledige trainingsdataset. De willekeurig geselecteerde deelsteekproef wordt dan gebruikt, in plaats van de volledige steekproef, om de basisleerder te passen.

– Stochastic Gradient Boosting , 1999

Een paar varianten van stochastische boosting die kunnen worden gebruikt:

• Subsample rijen vóór het maken van elke boom.
• Subsample kolommen vóór het maken van elke boom
• Subsample kolommen vóór het overwegen van elke splitsing.

In het algemeen heeft agressieve substeekproeftrekking, zoals het selecteren van slechts 50% van de gegevens, voordelen opgeleverd.

Volgens de feedback van gebruikers voorkomt het gebruik van kolomsubsteekproeftrekking over-fitting nog meer dan de traditionele rijsubsteekproeftrekking

– XGBoost: A Scalable Tree Boosting System, 2016

Penalized Gradient Boosting

Aan de geparametriseerde bomen kunnen naast hun structuur extra beperkingen worden opgelegd.

Klassieke beslisbomen zoals CART worden niet gebruikt als zwakke leerders, in plaats daarvan wordt een aangepaste vorm gebruikt die een regressieboom wordt genoemd en die numerieke waarden heeft in de bladknopen (ook eindknopen genoemd). De waarden in de bladeren van de bomen worden in sommige literatuur gewichten genoemd.

Zo kunnen de bladgewichten van de bomen worden geregulariseerd met behulp van populaire regularisatiefuncties, zoals:

• L1 regularisatie van gewichten.
• L2 regularisatie van gewichten.

De extra regularisatieterm helpt om de uiteindelijk geleerde gewichten glad te strijken om over-fitting te voorkomen. Intuïtief zal de geregulariseerde doelstelling de neiging hebben een model te selecteren dat eenvoudige en voorspellende functies gebruikt.

– XGBoost: A Scalable Tree Boosting System, 2016

Gradient Boosting Resources

Gradient boosting is een fascinerend algoritme en ik weet zeker dat u er dieper op in wilt gaan.

Dit gedeelte bevat een lijst met verschillende bronnen die u kunt gebruiken om meer te leren over het gradient boosting-algoritme.

Gradient Boosting Video’s

• 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.
• Sectie 8.6 Boosting, pagina 203, Applied Predictive Modeling.
• Sectie 14.5 Stochastic Gradient Boosting, pagina 390, Applied Predictive Modeling.
• Sectie 16.4 Boosting, pagina 556, Machine Learning: A Probabilistic Perspective
• Hoofdstuk 10 Boosting en Additive Trees, pagina 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 (machine learning)
• Gradient boosting
• Gradient Tree Boosting in scikit-learn

Samenvatting

In deze post ontdekte je het gradient boosting algoritme voor voorspellende modellering in machine learning.

In het bijzonder hebt u geleerd:

• De geschiedenis van boosting in leertheorie en AdaBoost.
• Hoe het gradient boosting-algoritme werkt met een verliesfunctie, zwakke lerenden en een additief model.
• Hoe de prestaties van gradient boosting te verbeteren met regularisatie.

Heeft u vragen over het gradient boosting algoritme of over deze post? Stel uw vragen in de commentaren en ik zal mijn best doen om ze te beantwoorden.