O introducere delicată a algoritmului Gradient Boosting pentru învățare automată

Ultima actualizare la 15 august 2020

Gradient boosting este una dintre cele mai puternice tehnici de construire a modelelor predictive.

În această postare veți descoperi algoritmul de învățare automată gradient boosting și veți avea o introducere ușoară în locul de unde provine și cum funcționează.

După ce veți citi această postare, veți ști:

• Originea boosting-ului din teoria învățării și AdaBoost.
• Cum funcționează gradient boosting, inclusiv funcția de pierdere, învățătorii slabi și modelul aditiv.
• Cum se îmbunătățesc performanțele față de algoritmul de bază cu diferite scheme de regularizare.

Dă startul proiectului tău cu noua mea carte XGBoost With Python, care include tutoriale pas cu pas și fișierele de cod sursă Python pentru toate exemplele.

Să începem.

• Nevoie de ajutor cu XGBoost în Python?
• Originea stimulării
• AdaBoost the First Boosting Algorithm
• Generalizarea lui AdaBoost ca Gradient Boosting
• Cum funcționează Gradient Boosting
• Funcția de pierdere
• Weak Learner
• Model aditiv
• Ambunătățiri la Gradient Boosting de bază
• Constrângeri ale arborelui
• 2. Actualizări ponderate
• Stochastic Gradient Boosting
• Penalized Gradient Boosting
• Gradient Boosting Resources
• Gradient Boosting Videos
• Gradient Boosting in Textbooks
• Gradient Boosting Papers
• Gradient Boosting Slides
• Gradient Boosting Pagini web
• Summary
• Descoperiți algoritmul care câștigă competiții!
• Dezvoltați-vă propriile modele XGBoost în câteva minute
• Aduceți puterea XGBoost în propriile dumneavoastră proiecte

Nevoie de ajutor cu XGBoost în Python?

Faceți cursul meu gratuit de 7 zile prin e-mail și descoperiți xgboost (cu exemple de cod).

Click pentru a vă înscrie acum și primiți, de asemenea, o versiune gratuită în format PDF Ebook a cursului.

Începeți mini-cursul GRATUIT acum!

Originea stimulării

Ideea de stimulare a apărut din ideea dacă un cursant slab poate fi modificat pentru a deveni mai bun.

Michael Kearns a articulat obiectivul ca fiind „Hypothesis Boosting Problem” enunțând obiectivul din punct de vedere practic astfel::

… un algoritm eficient pentru convertirea ipotezelor relativ slabe în ipoteze foarte bune

– Thoughts on Hypothesis Boosting , 1988

O ipoteză slabă sau un învățăcel slab este definit ca fiind unul a cărui performanță este cel puțin puțin puțin mai bună decât cea a întâmplării.

Aceste idei s-au bazat pe munca lui Leslie Valiant privind învățarea fără distribuție sau probabil aproximativ corectă (PAC), un cadru pentru investigarea complexității problemelor de învățare automată.

Hypothesis boosting a fost ideea de filtrare a observațiilor, lăsând acele observații pe care învățarea slabă le poate gestiona și concentrându-se pe dezvoltarea de noi învățări slabe pentru a gestiona observațiile dificile rămase.

Ideea este de a utiliza metoda de învățare slabă de mai multe ori pentru a obține o succesiune de ipoteze, fiecare dintre ele reorientată pe exemplele pe care cele anterioare le-au găsit dificile și le-au clasificat greșit. … De notat, însă, că nu este deloc evident cum se poate face acest lucru

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

AdaBoost the First Boosting Algorithm

Prima realizare a metodei boosting care a cunoscut un mare succes în aplicații a fost Adaptive Boosting sau AdaBoost pe scurt.

Boosting-ul se referă la această problemă generală de a produce o regulă de predicție foarte precisă prin combinarea unor reguli de predicție aproximative și moderat inexacte.

– O generalizare teoretică de decizie a învățării on-line și o aplicație la boosting , 1995

Învățătorii slabi din AdaBoost sunt arbori de decizie cu o singură diviziune, numiți butuci de decizie pentru scurtimea lor.

AdaBoost funcționează prin ponderarea observațiilor, punând mai multă greutate pe cazurile greu de clasificat și mai puțină pe cele deja tratate bine. Se adaugă secvențial noi învățători slabi care își concentrează instruirea pe modelele mai dificile.

Aceasta înseamnă că eșantioanele care sunt dificil de clasificat primesc ponderi din ce în ce mai mari până când algoritmul identifică un model care clasifică corect aceste eșantioane

– Applied Predictive Modeling, 2013

Predicțiile se fac prin votul majorității predicțiilor învățătorilor slabi, ponderate în funcție de acuratețea lor individuală. Cea mai de succes formă a algoritmului AdaBoost a fost pentru probleme de clasificare binară și s-a numit AdaBoost.M1.

Puteți afla mai multe despre algoritmul AdaBoost în postarea:

• Boosting and AdaBoost for Machine Learning.

Generalizarea lui AdaBoost ca Gradient Boosting

AdaBoost și algoritmii înrudiți au fost reformulați într-un cadru statistic mai întâi de Breiman numindu-i algoritmi ARCing.

Arcing este un acronim pentru Adaptive Reweighting and Combining. Fiecare etapă într-un algoritm arcing constă într-o minimizare ponderată urmată de o recalculare a și .

– Prediction Games and Arching Algorithms , 1997

Acest cadru a fost dezvoltat în continuare de Friedman și denumit Gradient Boosting Machines. Mai târziu s-a numit doar gradient boosting sau gradient tree boosting.

Cadrul statistic a transformat boosting-ul într-o problemă de optimizare numerică în care obiectivul este de a minimiza pierderea modelului prin adăugarea de învățători slabi folosind o procedură asemănătoare cu cea de coborâre a gradientului.

Această clasă de algoritmi a fost descrisă ca un model aditiv în etape. Acest lucru se datorează faptului că un nou cursant slab este adăugat la un moment dat, iar cursanții slabi existenți în model sunt înghețați și lăsați neschimbați.

Rețineți că această strategie etapizată este diferită de abordările etapizate care reajustează termenii introduși anterior atunci când sunt adăugați termeni noi.

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

Generalizarea a permis utilizarea unor funcții de pierdere diferențiabile arbitrare, extinzând tehnica dincolo de problemele de clasificare binară pentru a sprijini regresia, clasificarea în mai multe clase și altele.

Cum funcționează Gradient Boosting

Gradient Boosting implică trei elemente:

1. O funcție de pierdere care trebuie optimizată.
2. Un învățător slab pentru a face predicții.
3. Un model aditiv pentru a adăuga învățători slabi pentru a minimiza funcția de pierdere.

Funcția de pierdere

Funcția de pierdere utilizată depinde de tipul de problemă care se rezolvă.

Trebuie să fie diferențiabilă, dar sunt acceptate multe funcții de pierdere standard și puteți să vă definiți propriile funcții.

De exemplu, regresia poate utiliza o eroare pătratică și clasificarea poate utiliza pierderea logaritmică.

Un beneficiu al cadrului de amplificare a gradientului este că nu trebuie derivat un nou algoritm de amplificare pentru fiecare funcție de pierdere care ar putea dori să fie utilizată, în schimb, este un cadru suficient de generic pentru ca orice funcție de pierdere diferențiabilă să poată fi utilizată.

Weak Learner

Arborii de decizie sunt utilizați ca învățător slab în amplificarea gradientului.

În mod specific, se utilizează arbori de regresie care produc valori reale pentru diviziuni și ale căror ieșiri pot fi adăugate împreună, permițând ca ieșirile modelelor ulterioare să fie adăugate și să „corecteze” reziduurile din predicții.

Arborii sunt construiți într-o manieră lacomă, alegând cele mai bune puncte de divizare pe baza scorurilor de puritate, cum ar fi Gini, sau pentru a minimiza pierderea.

Ințial, cum ar fi în cazul AdaBoost, au fost folosiți arbori de decizie foarte scurți care aveau doar o singură divizare, numită butuc de decizie. În general, pot fi utilizați arbori mai mari, cu 4 până la 8 niveluri.

Se obișnuiește să se constrângă învățătorii slabi în moduri specifice, cum ar fi un număr maxim de straturi, noduri, diviziuni sau noduri de frunze.

Aceasta pentru a se asigura că învățătorii rămân slabi, dar pot fi construiți în continuare într-o manieră lacomă.

Model aditiv

Arborii sunt adăugați unul câte unul, iar arborii existenți în model nu sunt modificați.

Se utilizează o procedură de coborâre a gradientului pentru a minimiza pierderea atunci când se adaugă arbori.

În mod tradițional, coborârea gradientului este utilizată pentru a minimiza un set de parametri, cum ar fi coeficienții într-o ecuație de regresie sau ponderile într-o rețea neuronală. După calcularea erorii sau a pierderii, ponderile sunt actualizate pentru a minimiza eroarea respectivă.

În loc de parametri, avem submodele de învățare slabe sau, mai precis, arbori de decizie. După calcularea pierderii, pentru a efectua procedura de coborâre a gradientului, trebuie să adăugăm un arbore la model care reduce pierderea (adică urmează gradientul). Facem acest lucru prin parametrizarea arborelui, apoi modificăm parametrii arborelui și ne deplasăm în direcția corectă prin (reducerea pierderii reziduale.

În general, această abordare se numește coborâre funcțională a gradientului sau coborâre a gradientului cu funcții.

O modalitate de a produce o combinație ponderată de clasificatori care se optimizează este prin coborârea gradientului în spațiul funcțiilor

– Boosting Algorithms as Gradient Descent in Function Space , 1999

Lovitura pentru noul arbore este apoi adăugată la ieșirea secvenței existente de arbori într-un efort de a corecta sau îmbunătăți ieșirea finală a modelului.

Se adaugă un număr fix de arbori sau antrenamentul se oprește odată ce pierderea atinge un nivel acceptabil sau nu se mai îmbunătățește pe un set de date de validare externă.

Ambunătățiri la Gradient Boosting de bază

Gradient boosting este un algoritm lacom și poate supraadapta rapid un set de date de antrenament.

Acesta poate beneficia de metode de regularizare care penalizează diferite părți ale algoritmului și care, în general, îmbunătățesc performanța algoritmului prin reducerea supraajustării.

În această secțiune vom examina 4 îmbunătățiri aduse la stimularea gradientului de bază:

1. Constrângeri ale arborelui
2. Shrinkage
3. Eșantionare aleatorie
4. Învățare penalizată

Constrângeri ale arborelui

Este important ca cei care învață slab să aibă abilități, dar să rămână slabi.

Există o serie de moduri în care arborii pot fi constrânși.

O bună euristică generală este că, cu cât crearea de arbori este mai constrânsă, cu atât mai mulți arbori vor fi necesari în model, și invers, în cazul în care arborii individuali mai puțin constrânși, cu atât mai puțini arbori vor fi necesari.

Mai jos sunt câteva constrângeri care pot fi impuse asupra construcției arborilor de decizie:

• Numărul de arbori, în general adăugarea mai multor arbori în model poate fi foarte lentă pentru supraajustare. Sfatul este de a continua să adăugați arbori până când nu se mai observă nicio îmbunătățire.
• Adâncimea arborelui, arborii mai adânci sunt arbori mai complecși și sunt de preferat arborii mai scurți. În general, se observă rezultate mai bune cu 4-8 niveluri.
• Numărul de noduri sau numărul de frunze, ca și adâncimea, acesta poate constrânge dimensiunea arborelui, dar nu este constrâns la o structură simetrică dacă se folosesc alte constrângeri.
• Numărul de observații per divizare impune o constrângere minimă asupra cantității de date de instruire la un nod de instruire înainte de a se lua în considerare o divizare
• Îmbunătățirea minimă a pierderilor este o constrângere asupra îmbunătățirii oricărei divizări adăugate la un arbore.

2. Actualizări ponderate

Predicțiile fiecărui arbore sunt adunate secvențial.

Contribuția fiecărui arbore la această sumă poate fi ponderată pentru a încetini învățarea de către algoritm. Această ponderare se numește micșorare sau rată de învățare.

Care actualizare este pur și simplu scalată cu valoarea „parametrului v al ratei de învățare”

– Aproximarea funcției Greedy: A Gradient Boosting Machine , 1999

Efectul este că învățarea este încetinită, la rândul său necesită mai mulți arbori care trebuie adăugați la model, la rândul său necesitând mai mult timp pentru instruire, oferind un compromis de configurare între numărul de arbori și rata de învățare.

Diminuarea valorii lui v crește cea mai bună valoare pentru M .

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

Este obișnuit să avem valori mici în intervalul de la 0,1 la 0,3, precum și valori mai mici de 0,1.

Similară unei rate de învățare în optimizarea stocastică, micșorarea reduce influența fiecărui arbore individual și lasă spațiu pentru arborii viitori pentru a îmbunătăți modelul.

– Stochastic Gradient Boosting , 1999

Stochastic Gradient Boosting

O mare intuiție a ansamblurilor de bagging și a pădurii aleatoare a fost aceea de a permite crearea cu lăcomie a arborilor din subeșantioane ale setului de date de instruire.

Același beneficiu poate fi folosit pentru a reduce corelația dintre arborii din secvență în modelele de amplificare a gradientului.

Această variantă de amplificare se numește amplificare stocastică a gradientului.

La fiecare iterație, un subeșantion de date de instruire este extras la întâmplare (fără înlocuire) din întregul set de date de instruire. Subeșantionul selectat aleatoriu este apoi utilizat, în locul eșantionului complet, pentru a se potrivi învățătorului de bază.

– Stochastic Gradient Boosting , 1999

Câteva variante de stochastic boosting care pot fi utilizate:

• Subeșantionarea rândurilor înainte de a crea fiecare arbore.
• Subeșantionarea coloanelor înainte de a crea fiecare arbore
• Subeșantionarea coloanelor înainte de a lua în considerare fiecare divizare.

În general, o subeșantionare agresivă, cum ar fi selectarea a doar 50% din date, s-a dovedit a fi benefică.

Potrivit feedback-ului utilizatorilor, utilizarea subeșantionării coloanelor previne supraadaptarea chiar mai mult decât subeșantionarea tradițională a rândurilor

– XGBoost: A Scalable Tree Boosting System, 2016

Penalized Gradient Boosting

Se pot impune constrângeri suplimentare asupra arborilor parametrizate în plus față de structura lor.

Arborii de decizie clasici, cum ar fi CART, nu sunt utilizați ca învățători slabi, în schimb se utilizează o formă modificată numită arbore de regresie care are valori numerice în nodurile frunzelor (numite și noduri terminale). Valorile din frunzele arborilor pot fi numite ponderi în unele lucrări de specialitate.

Ca atare, valorile ponderilor din frunzele arborilor pot fi regularizate folosind funcții de regularizare populare, cum ar fi:

• L1 regularizarea ponderilor.
• L2 regularizarea ponderilor.

Termenul suplimentar de regularizare ajută la netezirea ponderilor învățate finale pentru a evita supraadaptarea. Intuitiv, obiectivul regularizat va tinde să selecteze un model care utilizează funcții simple și predictive.

– XGBoost: A Scalable Tree Boosting System, 2016

Gradient Boosting Resources

Gradient boosting este un algoritm fascinant și sunt sigur că doriți să aprofundați mai mult.

Această secțiune enumeră diverse resurse pe care le puteți utiliza pentru a afla mai multe despre algoritmul 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

• Secțiunea 8.2.3 Boosting, pagina 321, An Introduction to Statistical Learning: with Applications in R.
• Secțiunea 8.6 Boosting, pagina 203, Applied Predictive Modeling.
• Secțiunea 14.5 Stochastic Gradient Boosting, pagina 390, Applied Predictive Modeling.
• Secțiunea 16.4 Boosting, pagina 556, Machine Learning: A Probabilistic Perspective
• Capitolul 10 Boosting and 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 Pagini web

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

Summary

În acest post ați descoperit algoritmul gradient boosting pentru modelarea predictivă în machine learning.

În mod specific, ați învățat:

• Istoria boosting-ului în teoria învățării și AdaBoost.
• Cum funcționează algoritmul gradient boosting cu o funcție de pierdere, învățători slabi și un model aditiv.
• Cum se îmbunătățesc performanțele gradient boosting-ului cu regularizare.

Aveți întrebări despre algoritmul gradient boosting sau despre această postare? Puneți întrebările dvs. în comentarii și voi face tot posibilul să vă răspund.