Finom bevezetés a Gradient Boosting algoritmusba a gépi tanulásban

Most Updated on Augusztus 15, 2020

A Gradient Boosting az egyik leghatékonyabb technika a prediktív modellek építéséhez.

Ebben a bejegyzésben felfedezheti a gradiens boosting gépi tanulási algoritmust, és kap egy gyengéd bevezetést abba, hogy honnan származik és hogyan működik.

A bejegyzés elolvasása után tudni fogja:

• A boosting eredete a tanuláselméletből és az AdaBoostból.
• Hogyan működik a gradiens boosting, beleértve a veszteségfüggvényt, a gyenge tanulókat és az additív modellt.
• Hogyan javítható a teljesítmény az alapalgoritmushoz képest különböző regularizációs sémákkal.

Kezdje el projektjét az új XGBoost With Python című könyvemmel, amely lépésről lépésre bemutató útmutatókat és az összes példa Python forráskódfájlját tartalmazza.

Kezdjük el.

• Segítségre van szüksége az XGBoosthoz Pythonban?
• A Boosting eredete
• AdaBoost the First Boosting Algorithm
• Az AdaBoost általánosítása Gradient Boostingként
• How Gradient Boosting Works
• Veszteségfüggvény
• Gyenge tanuló
• Additív modell
• Improvements to Basic Gradient Boosting
• Fa megkötések
• 2. Súlyozott frissítések
• Stochastic Gradient Boosting
• Penalized Gradient Boosting
• Gradient Boosting Resources
• Gradient Boosting videók
• Gradient Boosting in Textbooks
• Gradient Boosting Papers
• Gradient Boosting Diák
• Gradient Boosting Web Pages
• Summary
• Fedezd fel a versenyeket megnyerő algoritmust!
• Létrehozd saját XGBoost modelljeidet percek alatt
• Hozd az XGBoost erejét a saját projektjeidhez

Segítségre van szüksége az XGBoosthoz Pythonban?

Vegye fel ingyenes 7 napos e-mailes tanfolyamomat, és fedezze fel az xgboostot (mintakóddal).

Kattintson a feliratkozáshoz most, és a tanfolyam ingyenes PDF Ebook változatát is megkapja.

Kezdje el az ingyenes minitanfolyamot most!

A Boosting eredete

A boosting ötlete abból az elképzelésből indult ki, hogy vajon a gyenge tanuló módosítható-e, hogy jobbá váljon.

Michael Kearns a célt “Hypothesis Boosting Problem”-ként fogalmazta meg, gyakorlati szempontból a következőképpen fogalmazva meg a célt:

… egy hatékony algoritmus a viszonylag gyenge hipotézisek nagyon jó hipotézisekké való átalakítására

– Thoughts on Hypothesis Boosting , 1988

A gyenge hipotézist vagy gyenge tanulót úgy definiáljuk, mint amelynek teljesítménye legalább valamivel jobb a véletlennél.

Ezek az elképzelések Leslie Valiant munkájára épültek az eloszlásmentes vagy valószínűleg közelítően helyes (Probably Approximately Correct, PAC) tanulással kapcsolatban, amely egy keretrendszer a gépi tanulási problémák komplexitásának vizsgálatára.

A hipotézisnövelés a megfigyelések szűrésének ötlete volt, meghagyva azokat a megfigyeléseket, amelyeket a gyenge tanuló kezelni tud, és új gyenge tanulók kifejlesztésére összpontosítva a fennmaradó nehéz megfigyelések kezelésére.

Az ötlet az, hogy a gyenge tanulási módszert többször alkalmazzuk, hogy egymás után hipotéziseket kapjunk, amelyek mindegyike újra azokra a példákra összpontosít, amelyeket az előzőek nehéznek találtak és rosszul osztályoztak. … Megjegyzendő azonban, hogy egyáltalán nem nyilvánvaló, hogyan lehet ezt megvalósítani

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

AdaBoost the First Boosting Algorithm

A boosting első, az alkalmazásban nagy sikert aratott megvalósítása az Adaptive Boosting vagy röviden AdaBoost volt.

A boosting erre az általános problémára utal, amikor egy nagyon pontos előrejelzési szabályt állítunk elő durva és közepesen pontatlan ökölszabályok kombinálásával.

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

A weak learners in AdaBoost are decision trees with a single split, called decision stumps for their shortness.

AdaBoost works by weighting the observations, putting more weight on difficult to classify instances and less on those already handled well. Az új gyenge tanulók egymás után kerülnek hozzáadásra, amelyek képzésük során a nehezebb mintákra összpontosítanak.

Ez azt jelenti, hogy a nehezen osztályozható minták egyre nagyobb súlyokat kapnak, amíg az algoritmus nem talál olyan modellt, amely helyesen osztályozza ezeket a mintákat

– Applied Predictive Modeling, 2013

Az előrejelzések a gyenge tanulók előrejelzéseinek többségi szavazásával készülnek, az egyéni pontosságukkal súlyozva. Az AdaBoost algoritmus legsikeresebb formája bináris osztályozási problémákra készült, és az AdaBoost.M1 nevet kapta.

Az AdaBoost algoritmusról többet megtudhat a következő bejegyzésben:

• Boosting and AdaBoost for Machine Learning.

Az AdaBoost általánosítása Gradient Boostingként

Az AdaBoost és a kapcsolódó algoritmusokat először Breiman formálta át statisztikai keretbe, ARCing algoritmusoknak nevezve őket.

AzArcing az Adaptive Reweighting and Combining rövidítése. Egy arcing algoritmus minden lépése egy súlyozott minimalizálásból áll, amelyet a és újraszámítása követ.

– Prediction Games and Arching Algorithms , 1997

Ezt a keretrendszert Friedman fejlesztette tovább, és Gradient Boosting Machines-nak nevezte el. Később csak gradiens boostingnak vagy gradiens fa boostingnak nevezték.

A statisztikai keretrendszer a boostingot numerikus optimalizálási problémaként vetette fel, ahol a cél a modell veszteségének minimalizálása gyenge tanulók hozzáadásával egy gradiens ereszkedéshez hasonló eljárás segítségével.

Az algoritmusok ezen osztályát fokozatos additív modellként írták le. Ennek az az oka, hogy egyszerre egy új gyenge tanulót adunk hozzá, és a modellben meglévő gyenge tanulókat befagyasztjuk és változatlanul hagyjuk.

Megjegyezzük, hogy ez a szakaszos stratégia különbözik a lépcsőzetes megközelítésektől, amelyek új feltételek hozzáadásakor a korábban beírt feltételeket újra beállítják.

– Mohó függvényapproximáció: A Gradient Boosting Machine , 1999

Az általánosítás lehetővé tette tetszőleges differenciálható veszteségfüggvények használatát, kiterjesztve a technikát a bináris osztályozási problémákon túl a regresszió, a többosztályos osztályozás és egyéb problémák támogatására.

How Gradient Boosting Works

A Gradient Boosting három elemet foglal magában:

1. Egy optimalizálandó veszteségfüggvény.
2. Egy gyenge tanuló, amely előrejelzéseket készít.
3. Egy additív modell, amely gyenge tanulókat ad hozzá a veszteségfüggvény minimalizálásához.

Veszteségfüggvény

A használt veszteségfüggvény a megoldandó probléma típusától függ.

Differenciálhatónak kell lennie, de számos szabványos veszteségfüggvény támogatott, és definiálhatunk sajátot is.

A regresszió például használhat négyzetes hibát, az osztályozás pedig logaritmikus veszteséget.

A gradiens boosting keretrendszer előnye, hogy nem kell új boosting algoritmust levezetni minden egyes veszteségfüggvényhez, amelyet esetleg használni szeretnénk, hanem ez egy elég általános keretrendszer ahhoz, hogy bármilyen differenciálható veszteségfüggvény használható legyen.

Gyenge tanuló

A gradiens boostingban gyenge tanulóként a döntési fákat használjuk.

Kifejezetten olyan regressziós fákat használnak, amelyek valós értékeket adnak ki a felosztásokhoz, és amelyek kimenetei összeadhatók, lehetővé téve a későbbi modellek kimeneteinek hozzáadását és a maradékok “korrekcióját” az előrejelzésekben.

A fákat mohó módon építik fel, a legjobb felosztási pontokat tisztasági pontszámok, például a Gini alapján választják ki, vagy a veszteség minimalizálása érdekében.

Eredetileg, például az AdaBoost esetében, nagyon rövid döntési fákat használtak, amelyeknek csak egyetlen felosztásuk volt, amit döntési csonknak neveznek. Általában nagyobb fákat lehet használni 4-8 szinttel.

A gyenge tanulófákat szokás bizonyos módon korlátozni, például a rétegek, csomópontok, osztások vagy levélcsomópontok maximális számával.

Ezzel biztosítható, hogy a tanulófák gyengék maradjanak, de mégis mohón konstruálhatók legyenek.

Additív modell

A fákat egyesével adjuk hozzá, és a modellben meglévő fákat nem változtatjuk meg.

A fák hozzáadásakor a veszteség minimalizálására gradiens ereszkedési eljárást használunk.

A gradiens ereszkedést hagyományosan egy paraméterkészlet, például egy regressziós egyenlet együtthatóinak vagy egy neurális hálózat súlyainak minimalizálására használjuk. A hiba vagy veszteség kiszámítása után a súlyokat úgy frissítjük, hogy minimalizáljuk ezt a hibát.

A paraméterek helyett gyenge tanuló almodellekkel, pontosabban döntési fákkal rendelkezünk. A veszteség kiszámítása után a gradiens ereszkedési eljárás végrehajtásához egy olyan fát kell hozzáadnunk a modellhez, amely csökkenti a veszteséget (azaz követi a gradienst). Ezt úgy tesszük, hogy paraméterezzük a fát, majd módosítjuk a fa paramétereit, és a megfelelő irányba haladunk (csökkentve a maradék veszteséget.

Azt a megközelítést általában funkcionális gradiens süllyedésnek vagy függvényekkel történő gradiens süllyedésnek nevezik.

Az osztályozók súlyozott kombinációjának előállításának egyik módja, amely optimalizál, a függvénytérben történő gradiens ereszkedés

– Boosting Algorithms as Gradient Descent in Function Space , 1999

Az új fa kimenete ezután hozzáadódik a meglévő fák sorozatának kimenetéhez, hogy a modell végső kimenetét korrigálni vagy javítani lehessen.

Fixált számú fát adunk hozzá, vagy a képzés leáll, ha a veszteség elér egy elfogadható szintet, vagy már nem javít egy külső validációs adathalmazon.

Improvements to Basic Gradient Boosting

A Gradient Boosting egy mohó algoritmus, és gyorsan túlillesztheti a képzési adathalmazt.

Az algoritmus különböző részeit büntető regularizációs módszerek előnyösek lehetnek számára, és általában javítják az algoritmus teljesítményét a túlillesztés csökkentésével.

Ebben a fejezetben az alapvető gradiens boosting 4 továbbfejlesztését nézzük meg:

1. Fa megkötések
2. Shrinkage
3. Véletlenszerű mintavétel
4. Büntetett tanulás

Fa megkötések

Nagyon fontos, hogy a gyenge tanulóknak legyen képessége, de maradjon gyenge.

A fákat többféleképpen lehet korlátozni.

Egy jó általános heurisztika az, hogy minél jobban korlátozzuk a fák létrehozását, annál több fára lesz szükség a modellben, és fordítva, ahol kevésbé korlátozzuk az egyes fákat, annál kevesebb fára lesz szükség.

Az alábbiakban bemutatunk néhány olyan korlátozást, amelyet a döntési fák létrehozására lehet alkalmazni:

• A fák száma, általában több fa hozzáadása a modellhez nagyon lassan vezethet túlillesztéshez. A tanács az, hogy addig adjunk hozzá fákat, amíg nem figyelhető meg további javulás.
• Fa mélysége, a mélyebb fák összetettebb fák, és a rövidebb fák előnyösebbek. Általában 4-8 szint esetén jobb eredményeket kapunk.
• A csomópontok vagy levelek száma, a mélységhez hasonlóan ez is korlátozhatja a fa méretét, de nem kényszerül szimmetrikus szerkezetre, ha más megkötéseket használunk.
• A felosztásonkénti megfigyelések száma egy minimális korlátot szab a képzési adatok mennyiségére egy képzési csomópontnál, mielőtt egy felosztás figyelembe vehető
• Minimális javulás a veszteséghez egy korlát a fához hozzáadott bármely felosztás javulására.

2. Súlyozott frissítések

Az egyes fák előrejelzéseit egymás után összeadjuk.

Az egyes fák hozzájárulása ehhez az összeghez súlyozható, hogy az algoritmus lassítsa a tanulást. Ezt a súlyozást zsugorításnak vagy tanulási aránynak nevezzük.

Minden frissítés egyszerűen a “tanulási arány paraméter v”

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

A hatás az, hogy a tanulás lelassul, viszont több fát kell hozzáadni a modellhez, ami viszont hosszabb időt vesz igénybe a képzéshez, így a fák száma és a tanulási sebesség közötti konfigurációs kompromisszumot biztosít.

A v értékének csökkentése növeli az M legjobb értékét.

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

A 0,1 és 0,3 közötti kis értékek, valamint a 0,1-nél kisebb értékek gyakoriak.

A sztochasztikus optimalizálásban a tanulási arányhoz hasonlóan a zsugorítás csökkenti az egyes fák befolyását, és teret hagy a jövőbeli fáknak a modell javítására.

– Stochastic Gradient Boosting , 1999

Stochastic Gradient Boosting

A bagging ensembles és a random forest nagy felismerése az volt, hogy a fák mohón létrehozhatók a képzési adathalmaz almintáiból.

Ez az előny a gradiens boosting modellekben ugyanezt az előnyt lehet kihasználni a szekvenciában lévő fák közötti korreláció csökkentésére.

A boosting ezen variációját sztochasztikus gradiens boostingnak nevezzük.

Minden egyes iterációban a teljes képzési adathalmazból véletlenszerűen (csere nélkül) húzunk egy részmintát a képzési adatokból. Ezután a véletlenszerűen kiválasztott részmintát használjuk a teljes minta helyett az alaptanuló illesztésére.

– Stochastic Gradient Boosting , 1999

A sztochasztikus boosting néhány használható változata:

• A sorok részmintázása minden egyes fa létrehozása előtt.
• A oszlopok részmintázása minden egyes fa létrehozása előtt
• A oszlopok részmintázása minden egyes osztás figyelembevétele előtt.

Az agresszív almintavételezés, például az adatoknak csak 50%-ának kiválasztása általában előnyösnek bizonyult.

A felhasználói visszajelzések szerint az oszlop-almintavételezés használata még inkább megakadályozza a túlillesztést, mint a hagyományos sor-almintavételezés

– XGBoost: A Scalable Tree Boosting System, 2016

Penalized Gradient Boosting

A paraméterezett fákra a szerkezetükön kívül további megkötéseket is lehet szabni.

A klasszikus döntési fákat, mint a CART, nem használják gyenge tanulóként, hanem egy módosított, regressziós fának nevezett formát használnak, amely a levélcsomópontokban (más néven terminális csomópontokban) numerikus értékeket tartalmaz. A fák leveleiben lévő értékeket egyes szakirodalmakban súlyoknak nevezhetjük.

A fák leveleinek súlyértékei így regularizálhatók népszerű regularizációs függvényekkel, például:

• L1 súlyok regularizációja.
• L2 súlyok regularizációja.

A kiegészítő regularizációs kifejezés segít a végső tanult súlyok simításában a túlillesztés elkerülése érdekében. Intuitív módon a regularizált célkitűzés hajlamos lesz egyszerű és előrejelző függvényeket alkalmazó modellt választani.

– XGBoost: A Scalable Tree Boosting System, 2016

Gradient Boosting Resources

A gradient boosting egy lenyűgöző algoritmus, és biztos vagyok benne, hogy szeretne mélyebbre menni.

Ez a szakasz különböző forrásokat sorol fel, amelyek segítségével többet tudhat meg a gradient boosting algoritmusról.

Gradient Boosting videók

• Gradient Boosting Machine Learning, Trevor Hastie, 2014
• Gradient Boosting, Alexander Ihler, 2012
• GBM, John Mount, 2015
• Learning: Mesterséges intelligencia, MIT 6.034, 2010
• xgboost: 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.
• Section 8.6 Boosting, page 203, Applied Predictive Modeling.
• Section 14.5 Stochastic Gradient Boosting, page 390, Applied Predictive Modeling.
• Section 16.4 Boosting, page 556, Machine Learning: A Probabilistic Perspective
• Chapter 10 Boosting and Additive Trees, page 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 Diák

• 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

Summary

Ebben a bejegyzésben felfedezted a gradient boosting algoritmust a gépi tanulás prediktív modellezéséhez.

Közelebbről megtanultad:

• A boosting történetét a tanuláselméletben és az AdaBoostban.
• Hogyan működik a gradiens boosting algoritmus egy veszteségfüggvény, gyenge tanulók és egy additív modell segítségével.
• Hogyan javítható a gradiens boosting teljesítménye regularizációval.

Kérdése van a gradiens boosting algoritmussal vagy ezzel a bejegyzéssel kapcsolatban? Tedd fel a kérdéseidet a hozzászólásokban, és én mindent megteszek, hogy válaszoljak.