Jemný úvod do algoritmu Gradient Boosting pro strojové učení

Poslední aktualizace 15. srpna 2020

Gradient boosting je jednou z nejvýkonnějších technik pro vytváření prediktivních modelů.

V tomto příspěvku objevíte algoritmus strojového učení gradient boosting a získáte jemný úvod do toho, odkud pochází a jak funguje.

Po přečtení tohoto příspěvku budete vědět:

• Původ boostingu z teorie učení a AdaBoost.
• Jak gradient boosting funguje včetně ztrátové funkce, slabých učících se a aditivního modelu.
• Jak zlepšit výkonnost oproti základnímu algoritmu pomocí různých regularizačních schémat.

Začněte svůj projekt s mou novou knihou XGBoost With Python, která obsahuje výukové programy krok za krokem a zdrojové soubory jazyka Python pro všechny příklady.

Začněme.

• Potřebujete pomoc s XGBoost v Pythonu?
• Původ boosterování
• AdaBoost the First Boosting Algorithm
• Zobecnění AdaBoostu jako Gradient Boostingu
• Jak funguje Gradient Boosting
• Ztrátová funkce
• Slabý učící se
• Aditivní model
• Vylepšení základního Gradient Boostingu
• Stromové omezení
• 2. Vážené aktualizace
• Stochastic Gradient Boosting
• Penalized Gradient Boosting
• Gradient Boosting Resources
• Gradient Boosting Videa
• Gradient Boosting in Textbooks
• Gradient Boosting Papers
• Gradient Boosting Slides
• Gradient Boosting Web Pages
• Souhrn
• Objevte algoritmus, který vyhrává soutěže!
• Vyvíjejte vlastní modely XGBoost během několika minut
• Přeneste sílu XGBoostu do svých vlastních projektů

Potřebujete pomoc s XGBoost v Pythonu?

Podílejte se na mém bezplatném 7denním e-mailovém kurzu a objevte xgboost (s ukázkovým kódem).

Klikněte pro registraci a získejte také bezplatnou verzi kurzu ve formátu PDF Ebook.

Začněte svůj bezplatný minikurz nyní!

Původ boosterování

Myšlenka boosterování vznikla z myšlenky, zda lze slabého žáka upravit tak, aby se stal lepším.

Michael Kearns formuloval cíl jako „Hypothesis Boosting Problem“ a uvedl cíl z praktického hlediska takto:

… efektivní algoritmus pro převod relativně slabých hypotéz na velmi dobré hypotézy

– Thoughts on Hypothesis Boosting , 1988

Slabá hypotéza nebo slabý učící se je definován jako takový, jehož výkon je alespoň o něco lepší než náhodný.

Tyto myšlenky vycházely z práce Leslieho Valianta o učení bez distribuce nebo pravděpodobně přibližně správném (PAC), což je rámec pro zkoumání složitosti problémů strojového učení.

Hypothesis boosting byla myšlenka filtrování pozorování, ponechání těch pozorování, která slabý učící se subjekt zvládne, a zaměření se na vývoj nových slabých učících se subjektů, které si poradí se zbývajícími obtížnými pozorováními.

Jde o to, že se metoda slabého učení použije několikrát, aby se získala posloupnost hypotéz, přičemž každá z nich se znovu zaměří na příklady, které ty předchozí shledaly obtížnými a špatně je klasifikovaly. … Všimněte si však, že není vůbec zřejmé, jak to lze provést

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

AdaBoost the First Boosting Algorithm

První realizací boostingu, která zaznamenala velký aplikační úspěch, byl Adaptive Boosting neboli zkráceně AdaBoost.

Boosting se týká tohoto obecného problému vytvoření velmi přesného predikčního pravidla kombinací hrubých a středně nepřesných pravidel palce.

– Rozhodovací teoretické zobecnění on-line učení a aplikace na boosting , 1995

Slabými učiteli v AdaBoostu jsou rozhodovací stromy s jedním rozdělením, kterým se pro jejich krátkost říká rozhodovací pahýly.

AdaBoost pracuje tak, že váží pozorování, přičemž větší váhu přikládá obtížně klasifikovatelným případům a menší těm, které již byly dobře zpracovány. Postupně se přidávají nové slabé učitele, které se při tréninku zaměřují na obtížnější vzorky.

To znamená, že vzorky, které se obtížně klasifikují, dostávají stále větší váhy, dokud algoritmus neidentifikuje model, který tyto vzorky správně klasifikuje

– Applied Predictive Modeling, 2013

Předpovědi se provádějí většinovým hlasováním předpovědí slabých učitelů, vážených podle jejich individuální přesnosti. Nejúspěšnější podoba algoritmu AdaBoost byla určena pro problémy binární klasifikace a byla nazvána AdaBoost.M1.

Více o algoritmu AdaBoost se můžete dozvědět v příspěvku:

• Boosting and AdaBoost for Machine Learning.

Zobecnění AdaBoostu jako Gradient Boostingu

AdaBoost a příbuzné algoritmy přetvořil do statistického rámce nejprve Breiman a nazval je algoritmy ARCing.

Arcing je akronym pro Adaptive Reweighting and Combining. Každý krok algoritmu arcing se skládá z vážené minimalizace, po níž následuje přepočet a .

– Prediction Games and Arching Algorithms , 1997

Tento rámec dále rozvinul Friedman a nazval jej Gradient Boosting Machines. Později se nazýval jen gradient boosting nebo gradient tree boosting.

Statistický rámec obsadil boosting jako numerický optimalizační problém, kde je cílem minimalizovat ztrátu modelu přidáváním slabých učících se pomocí postupu podobného gradient descentu.

Tato třída algoritmů byla popsána jako stupňovitý aditivní model. Je to proto, že se přidává vždy jeden nový slabý učící se a stávající slabé učící se v modelu jsou zmrazeny a ponechány beze změny.

Všimněte si, že tato etapová strategie se liší od postupných přístupů, které při přidávání nových členů znovu upravují dříve zadané členy.

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

Zobecnění umožnilo použít libovolné diferencovatelné ztrátové funkce, což rozšířilo tuto techniku mimo problémy binární klasifikace na podporu regrese, klasifikace více tříd a další.

Jak funguje Gradient Boosting

Gradient Boosting zahrnuje tři prvky:

1. Ztrátová funkce, která má být optimalizována.
2. Slabý učící se subjekt, který provádí předpovědi.
3. Aditivní model pro přidání slabých učících se k minimalizaci ztrátové funkce.

Ztrátová funkce

Použitá ztrátová funkce závisí na typu řešeného problému.

Musí být diferencovatelná, ale je podporováno mnoho standardních ztrátových funkcí a můžete si definovat vlastní.

Například regrese může používat kvadratickou chybu a klasifikace může používat logaritmickou ztrátu.

Výhodou rámce gradientního posilování je, že není nutné odvozovat nový algoritmus posilování pro každou ztrátovou funkci, kterou lze chtít použít, místo toho je to dostatečně obecný rámec, aby bylo možné použít jakoukoli diferencovatelnou ztrátovou funkci.

Slabý učící se

V gradientním posilování se jako slabý učící se používají rozhodovací stromy.

Konkrétně se používají regresní stromy, které dávají reálné hodnoty pro rozdělení a jejichž výstupy lze sčítat, což umožňuje sčítat výstupy následných modelů a „opravovat“ rezidua v predikcích.

Stromy se konstruují nenasytným způsobem, kdy se vybírají nejlepší body rozdělení na základě skóre čistoty, například Giniho, nebo aby se minimalizovala ztráta.

Původně se, například v případě AdaBoost, používaly velmi krátké rozhodovací stromy, které měly pouze jedno rozdělení, tzv. rozhodovací pahýl. Obecně lze použít větší stromy se 4 až 8 úrovněmi.

Obvykle se slabé učitele omezují určitým způsobem, například maximálním počtem vrstev, uzlů, rozdělení nebo listových uzlů.

Tím se zajistí, že učitele zůstanou slabé, ale přesto je lze konstruovat chamtivým způsobem.

Aditivní model

Stromy se přidávají po jednom a stávající stromy v modelu se nemění.

K minimalizaci ztráty při přidávání stromů se používá postup gradientního sestupu.

Tradičně se gradientní sestup používá k minimalizaci souboru parametrů, jako jsou koeficienty v regresní rovnici nebo váhy v neuronové síti. Po výpočtu chyby nebo ztráty se váhy aktualizují tak, aby tuto chybu minimalizovaly.

Místo parametrů máme slabé učící se podmodely nebo přesněji rozhodovací stromy. Po výpočtu ztráty, abychom mohli provést postup gradientního sestupu, musíme do modelu přidat strom, který ztrátu snižuje (tj. sleduje gradient). To provedeme tak, že strom parametrizujeme, poté upravíme parametry stromu a pohybujeme se správným směrem tím, že (snižujeme zbytkovou ztrátu.

Zpravidla se tento přístup nazývá funkční gradientní sestup nebo gradientní sestup s funkcemi.

Jedním ze způsobů, jak vytvořit váženou kombinaci klasifikátorů, která se optimalizuje, je gradientní sestup v prostoru funkcí

– Boosting Algorithms as Gradient Descent in Function Space , 1999

Výstup pro nový strom se pak přidá k výstupu stávající posloupnosti stromů ve snaze opravit nebo zlepšit konečný výstup modelu.

Přidá se pevný počet stromů nebo se trénování zastaví, jakmile ztráta dosáhne přijatelné úrovně nebo se již nezlepší na externí validační datové sadě.

Vylepšení základního Gradient Boostingu

Gradient Boosting je nenasytný algoritmus a může rychle přebít trénovací datovou sadu.

Může těžit z regularizačních metod, které penalizují různé části algoritmu a obecně zlepšují výkonnost algoritmu tím, že snižují overfitting.

V této části se budeme zabývat 4 vylepšeními základního gradientního posilování:

1. Stromové omezení
2. Shrinkage
3. Náhodné vzorkování
4. Penalizované učení

Stromové omezení

Důležité je, aby slabí žáci měli dovednosti, ale zůstali slabí.

Existuje řada způsobů, jak stromy omezit.

Dobrou obecnou heuristikou je, že čím více je tvorba stromů omezena, tím více stromů budete v modelu potřebovat, a naopak, čím méně jsou jednotlivé stromy omezeny, tím méně stromů bude potřeba.

Níže jsou uvedena některá omezení, která lze na konstrukci rozhodovacích stromů uvalit:

• Počet stromů, obecně platí, že přidáním většího počtu stromů do modelu může dojít k velmi pomalému nadměrnému přizpůsobení. Doporučuje se přidávat stromy tak dlouho, dokud nedojde k dalšímu zlepšení.
• Hloubka stromů, hlubší stromy jsou složitější a upřednostňují se kratší stromy. Obecně jsou lepší výsledky pozorovány u 4-8 úrovní.
• Počet uzlů nebo počet listů, podobně jako hloubka může omezovat velikost stromu, ale není omezen na symetrickou strukturu, pokud jsou použita jiná omezení.
• Počet pozorování na jedno rozdělení ukládá minimální omezení na množství trénovacích dat v trénovacím uzlu, než lze uvažovat o rozdělení
• Minimální zlepšení na ztrátu je omezení na zlepšení jakéhokoli rozdělení přidaného do stromu.

2. Vážené aktualizace

Předpovědi každého stromu se sčítají postupně.

Příspěvek každého stromu k tomuto součtu může být vážen, aby algoritmus zpomalil učení. Toto vážení se nazývá smršťování nebo míra učení.

Každá aktualizace se jednoduše zváží hodnotou „parametru míry učení v“

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

Důsledkem je, že učení je zpomaleno, což zase vyžaduje přidání více stromů do modelu, což zase vyžaduje delší dobu trénování, což poskytuje konfigurační kompromis mezi počtem stromů a rychlostí učení.

Snižování hodnoty v zvyšuje nejlepší hodnotu pro M .

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

Obvyklé jsou malé hodnoty v rozmezí 0,1 až 0,3 a také hodnoty menší než 0,1.

Podobně jako míra učení ve stochastické optimalizaci zmenšování snižuje vliv každého jednotlivého stromu a ponechává prostor pro budoucí stromy, které mohou model zlepšit.

– Stochastic Gradient Boosting , 1999

Stochastic Gradient Boosting

Velkým poznatkem při vytváření pytlových souborů a náhodných lesů bylo umožnění chamtivého vytváření stromů z dílčích vzorků trénovacího souboru dat.

Stejnou výhodu lze využít ke snížení korelace mezi stromy v posloupnosti v modelech s gradientním boostingem.

Tato varianta boostingu se nazývá stochastický gradientní boosting.

v každé iteraci se náhodně (bez náhrady) vybere podvzorek trénovacích dat z celého trénovacího souboru. Náhodně vybraný podvzorek se pak použije namísto úplného vzorku k dosazení základního učitele.

– Stochastic Gradient Boosting , 1999

Několik variant stochastického posilování, které lze použít:

• Podvzorek řádků před vytvořením každého stromu.
• Podvzorek sloupců před vytvořením každého stromu
• Podvzorek sloupců před uvažováním každého rozdělení.

Všeobecně se ukázalo, že agresivní podvzorkování, například výběr pouze 50 % dat, je přínosné.

Podle zpětné vazby uživatelů použití podvzorkování sloupců zabraňuje nadměrnému přizpůsobení ještě více než tradiční podvzorkování řádků

– XGBoost: A Scalable Tree Boosting System, 2016

Penalized Gradient Boosting

Na parametrizované stromy lze kromě jejich struktury uvalit další omezení.

Klasické rozhodovací stromy jako CART se nepoužívají jako slabé učící se stromy, místo toho se používá upravená forma zvaná regresní strom, která má v listových uzlech (nazývaných také terminální uzly) číselné hodnoty. Hodnoty v listech stromů lze v některé literatuře nazývat vahami.

Jako takové lze hodnoty vah listů stromů regularizovat pomocí populárních regularizačních funkcí, například:

• L1 regularizace vah.
• L2 regularizace vah.

Přídavný člen regularizace pomáhá vyhladit konečné naučené váhy, aby se zabránilo přílišnému přizpůsobení. Intuitivně bude mít regularizovaný cíl tendenci vybrat model využívající jednoduché a prediktivní funkce.

– XGBoost: A Scalable Tree Boosting System, 2016

Gradient Boosting Resources

Gradient Boosting je fascinující algoritmus a určitě se chcete dostat hlouběji.

Tato část uvádí různé zdroje, které můžete použít k získání dalších informací o algoritmu gradient boosting.

Gradient Boosting Videa

• 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: 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.
• Rodíl 8.6 Boosting, strana 203, Applied Predictive Modeling.
• Rodíl 14.5 Stochastic Gradient Boosting, strana 390, Applied Predictive Modeling.
• Rodíl 16.4 Boosting, strana 556, Machine Learning: A Probabilistic Perspective
• Kapitola 10 Boosting a aditivní stromy, strana 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

Souhrn

V tomto příspěvku jste objevili algoritmus gradient boosting pro prediktivní modelování ve strojovém učení.

Konkrétně jste se dozvěděli:

• Historii boostingu v teorii učení a AdaBoost.
• Jak algoritmus gradient boostingu pracuje se ztrátovou funkcí, slabými učiteli a aditivním modelem.
• Jak zlepšit výkon gradient boostingu pomocí regularizace.

Máte nějaké dotazy k algoritmu gradient boostingu nebo k tomuto příspěvku? Ptejte se v komentářích a já se vám pokusím odpovědět.

.