Boosting (strojové učení) - Boosting (machine learning)

Část série na
Strojové učení a dolování dat
Problémy Klasifikace Shlukování Regrese Detekce anomálií Čištění dat AutoML Pravidla asociace Posílení učení Strukturovaná predikce Funkce inženýrství Funkce učení Online učení Učení pod dohledem Učení bez dozoru Naučit se řadit Gramatická indukce
Učení pod dohledem ( klasifikace  • regrese ) Rozhodovací stromy Soubory Pytlování Posílení Náhodný les k -NN Lineární regrese Naivní Bayes Umělé neuronové sítě Logistická regrese Perceptron Relevantní vektorový stroj (RVM) Podpora vektorového stroje (SVM)
Shlukování BŘÍZA LÉK Hierarchický k -znamená Očekávání – maximalizace (EM) DBSCAN OPTIKA Střední posun
Redukce rozměrů Faktorová analýza CCA ICA LDA NMF PCA PGD t-SNE
Strukturovaná predikce Grafické modely Bayesova síť Podmíněné náhodné pole Skrytý Markov
Detekce anomálií k -NN Faktor lokálních odlehlých hodnot
Umělá neurální síť Autoencoder Kognitivní výpočetní technika Hluboké učení DeepDream Vícevrstvý perceptron RNN LSTM GRU ESN Omezený stroj Boltzmann GAN SOM Konvoluční neurální síť U-Net Transformátor Rozšíření neuronové sítě Memtranzistor Elektrochemická RAM (ECRAM)
Posílení učení Q-učení SARSA Časový rozdíl (TD)
Teorie Kompromis předpojatosti a rozptylu Teorie počítačového učení Empirická minimalizace rizik Occam učení Učení PAC Statistické učení VC teorie
Místa strojového učení NeurIPS ICML ML JMLR ArXiv: cs.LG
Související články Glosář umělé inteligence Seznam datových sad pro výzkum strojového učení Nástin strojového učení
proti t E

Ve strojovém učení , posílení je soubor meta-algoritmus pro v první řadě snížení zkreslení , a také rozptyl v učení s učitelem , a rodina strojové učení algoritmy, které přeměňují slabé studenty, aby ty silné. Boosting je založen na otázce, kterou položili Kearns a Valiant (1988, 1989): „Může skupina slabých žáků vytvořit jediného silného žáka?“ Slabý žák je definován jako klasifikátor, který jen mírně koreluje se skutečnou klasifikací (může označovat příklady lépe než náhodné hádání). Silný žák je naproti tomu klasifikátor, který je libovolně dobře korelován se skutečnou klasifikací.

Kladná odpověď Roberta Schapira v dokumentu z roku 1990 na otázku Kearns a Valiant má významné důsledky ve strojovém učení a statistice , zejména vede k rozvoji posilování.

Když byl problém s hypotézou poprvé představen, jednoduše odkazoval na proces přeměny slabého žáka na silného žáka. „Neformálně se problém [hypotéza zvyšující] ptá, zda efektivní algoritmus učení […], který produkuje hypotézu, jejíž výkon je jen o málo lepší než náhodné hádání [tj. Slabý žák], naznačuje existenci účinného algoritmu, který produkuje hypotézu libovolného přesnost [tj. silný žák]. “ Algoritmy, které dosahují posílení hypotéz, se rychle staly jednoduše známé jako „posílení“. Freundův a Schapirův oblouk (Adapt [at] ive Resampling and Combining), jako obecná technika, je víceméně synonymem posilování.

Posilovací algoritmy

I když posilování není algoritmicky omezeno, většina posilujících algoritmů spočívá v iterativním učení slabých klasifikátorů s ohledem na distribuci a jejich přidání do konečného silného klasifikátoru. Když jsou přidány, jsou váženy způsobem, který souvisí s přesností slabých žáků. Poté, co se přidá slabý žák, jsou datové váhy znovu seřízeny, známé jako „ vážení “. Nesprávně klasifikovaná vstupní data získávají vyšší váhu a příklady, které jsou klasifikovány správně, hubnou. Budoucí slabí žáci se tedy více zaměřují na příklady, které předchozí slabí žáci špatně klasifikovali.

Ilustrace představující intuici za posilujícím algoritmem, skládající se z paralelních studentů a vážené datové sady.

Existuje mnoho posilujících algoritmů. Původní návrhy, které navrhli Robert Schapire ( formulace rekurzivní většinové brány) a Yoav Freund (posílení většinou), nebyly adaptivní a nemohly plně využít výhod slabých studentů. Schapire a Freund poté vyvinuli AdaBoost , adaptivní posilovací algoritmus, který získal prestižní Gödelovu cenu .

Pouze algoritmy, které jsou prokazatelně posilujícími algoritmy ve pravděpodobně přibližně správné formulaci učení, lze přesně nazvat zesilovací algoritmy . Jiné algoritmy, které jsou v duchu podobné zesilovacím algoritmům, se někdy nazývají „pákové algoritmy“, ačkoli se jim někdy také nesprávně říká zesilující algoritmy.

Hlavní variací mezi mnoha posilovacími algoritmy je jejich metoda vážení tréninkových datových bodů a hypotéz . AdaBoost je velmi populární a historicky nejvýznamnější, protože to byl první algoritmus, který se dokázal přizpůsobit slabým studentům. Často je základem úvodního pokrytí posilování v univerzitních kurzech strojového učení. Existuje mnoho novějších algoritmů, jako jsou LPBoost , TotalBoost, BrownBoost , xgboost , MadaBoost, LogitBoost a další. Mnoho zesilujících algoritmů zapadá do rámce AnyBoost, což ukazuje, že posílení provádí klesání ve funkčním prostoru pomocí konvexní nákladové funkce .

Kategorizace objektů v počítačovém vidění

Vzhledem k obrázkům obsahujícím různé známé objekty na světě se z nich lze naučit klasifikátor, který objekty automaticky zařadí do budoucích obrázků. Jednoduché klasifikátory postavené na základě nějaké vlastnosti obrázku objektu bývají slabé ve výkonu kategorizace. Použití metod zesílení pro kategorizaci objektů je způsob, jak zvláštním způsobem sjednotit slabé klasifikátory, aby se zvýšila celková schopnost kategorizace.

Problém kategorizace objektů

Kategorizace objektů je typickým úkolem počítačového vidění, který zahrnuje určení, zda obrázek obsahuje určitou specifickou kategorii objektu. Tato myšlenka úzce souvisí s rozpoznáváním, identifikací a detekcí. Kategorizace objektů podle vzhledu obvykle obsahuje extrakci funkcí , učení se klasifikátoru a použití klasifikátoru na nové příklady. Existuje mnoho způsobů, jak reprezentovat kategorii objektů, např. Z analýzy tvaru , modelů sáčků slov nebo lokálních deskriptorů, jako je SIFT atd. Příkladem kontrolovaných klasifikátorů jsou klasifikátory Naive Bayes , podpůrné vektorové stroje , směsi Gaussovců a neuronové sítě . Výzkum však ukázal, že kategorie objektů a jejich umístění v obrazech lze také objevit bez dozoru .

Status quo pro kategorizaci objektů

Rozpoznání kategorií objektů v obrazech je náročným problémem počítačového vidění , zvláště když je počet kategorií velký. Důvodem je vysoká variabilita uvnitř třídy a potřeba generalizace napříč variacemi objektů ve stejné kategorii. Objekty v jedné kategorii mohou vypadat docela odlišně. I stejný objekt se může zdát nepodobný pod jiným úhlem pohledu, měřítkem a osvětlením . Nepořádek na pozadí a částečná okluze také zhoršují rozpoznávání. Lidé jsou schopni rozpoznat tisíce typů objektů, zatímco většina stávajících systémů rozpoznávání objektů je vyškolena tak, aby rozpoznala pouze několik, např. Lidské tváře , auta , jednoduché předměty atd. Výzkum byl velmi aktivní při řešení více kategorií a umožnění přírůstkových přírůstky nových kategorií, a přestože obecný problém zůstává nevyřešen, bylo vyvinuto několik vícekategorových detektorů objektů (až pro stovky nebo tisíce kategorií). Jedním z prostředků je sdílení funkcí a posílení.

Posílení pro binární kategorizaci

AdaBoost lze použít k detekci obličeje jako příklad binární kategorizace . Dvě kategorie jsou tváře versus pozadí. Obecný algoritmus je následující:

1. Vytvořte velkou sadu jednoduchých funkcí
2. Inicializujte závaží pro tréninkové obrázky
3. Pro T kola
   1. Normalizujte váhy
   2. Pro dostupné funkce ze sady vycvičte klasifikátor pomocí jediné funkce a vyhodnoťte chybu školení
   3. Vyberte klasifikátor s nejnižší chybou
   4. Aktualizujte váhy tréninkových obrázků: zvyšujte, pokud tento klasifikátor klasifikuje špatně, snižte, pokud správně
4. Vytvořte konečný silný klasifikátor jako lineární kombinaci klasifikátorů T (koeficient větší, pokud je chyba tréninku malá)

Po posílení by klasifikátor vytvořený z 200 funkcí mohl poskytnout 95% míru detekce při falešně pozitivním kurzu . ${\ displaystyle 10^{-5}}$

Další aplikací posilování pro binární kategorizaci je systém, který detekuje chodce pomocí pohybových a vzhledových vzorců . Tato práce je první, která kombinuje informace o pohybu a informace o vzhledu jako funkce pro detekci chodící osoby. Má podobný přístup jako rámec pro detekci objektů Viola-Jones .

Posílení pro kategorizaci více tříd

Ve srovnání s binární kategorizací hledá kategorizace ve více třídách společné funkce, které lze sdílet napříč kategoriemi současně. Obracejí být obecnější hrana jako rysy. Během učení lze detektory pro každou kategorii trénovat společně. Ve srovnání s tréninkem samostatně lépe generalizuje , potřebuje méně tréninkových dat a k dosažení stejného výkonu vyžaduje méně funkcí.

Hlavní tok algoritmu je podobný binárnímu případu. Rozdíl je v tom, že míra chyby společného školení bude definována předem. Během každé iterace zvolí algoritmus klasifikátor jedné funkce (podporují se funkce, které lze sdílet ve více kategoriích). To lze provést převedením klasifikace více tříd na binární (sada kategorií versus ostatní), nebo zavedením chyby trestu z kategorií, které nemají funkci klasifikátoru.

V příspěvku „Sdílení vizuálních funkcí pro detekci více tříd a více pohledů“ A. Torralba a kol. použil GentleBoost k posílení a ukázal, že když jsou tréninková data omezená, učení prostřednictvím funkcí sdílení dělá mnohem lepší práci než žádné sdílení, vzhledem ke stejným vylepšovacím kolům. Rovněž je pro danou úroveň výkonu pozorováno, že celkový počet požadovaných funkcí (a tedy náklady na dobu klasifikace klasifikátoru) pro detektory sdílení funkcí se přibližně logaritmicky škálovaly s počtem tříd, tj. Pomaleji než lineární růst v případ sdílení. Podobné výsledky jsou uvedeny v příspěvku „Přírůstkové učení detektorů objektů pomocí abecedy vizuálních tvarů“, přesto autoři pro posílení použili AdaBoost .

Konvexní vs. nekonvexní zesilující algoritmy

Algoritmy posílení mohou být založeny na konvexních nebo nekonvexních optimalizačních algoritmech. Konvexní algoritmy, jako jsou AdaBoost a LogitBoost , lze „porazit“ náhodným šumem, takže se nemohou naučit základní a naučitelné kombinace slabých hypotéz. Na toto omezení upozornila společnost Long & Servedio v roce 2008. Do roku 2009 však několik autorů prokázalo, že posilovací algoritmy založené na nekonvexní optimalizaci, jako je například BrownBoost , se mohou učit z hlučných datových sad a mohou se konkrétně naučit základní klasifikátor Long- Datová sada Servedio.

Viz také

Implementace

• Scikit-learn , open source knihovna strojového učení pro python
• Orange , bezplatná softwarová sada pro dolování dat, modul Orange.ensemble
• Weka je sada nástrojů strojového učení, která nabízí různé implementace posilujících algoritmů, jako jsou AdaBoost a LogitBoost
• Balíček R GBM (Generalized Boosted Regression Models) implementuje rozšíření Freundova a Schapireova algoritmu AdaBoost a Friedmanova gradientu.
• jboost ; AdaBoost, LogitBoost, RobustBoost, Boostexter a střídavé rozhodovací stromy
• Balíček R adabag : Aplikuje Multiclass AdaBoost.M1, AdaBoost-SAMME a Bagging
• Balíček R xgboost : Implementace posílení gradientu pro lineární a stromové modely.

Poznámky

Reference

Další čtení

• Yoav Freund a Robert E. Schapire (1997); Rozhodovací teoretická generalizace on-line učení a aplikace pro posílení , Journal of Computer and System Sciences, 55 (1): 119-139
• Robert E. Schapire a Yoram Singer (1999); Vylepšené posilovací algoritmy pomocí prediktorů s hodnocením spolehlivosti , Machine Learning, 37 (3): 297-336

externí odkazy

• Robert E. Schapire (2003); Posilovací přístup ke strojovému učení: Přehled , workshop MSRI (Mathematical Sciences Research Institute) o nelineárním odhadování a klasifikaci
• Zhou Zhi-Hua (2014) Posílení o 25 let , CCL 2014 Keynote.
• Zhou, Zhihua (2008). „Na okraj vysvětlení zesilujícího algoritmu“ (PDF) . In: Sborník z 21. výroční konference o teorii učení (COLT'08) : 479–490.
• Zhou, Zhihua (2013). „Na pochybách o marži vysvětlení posílení“ (PDF) . Umělá inteligence . 203 : 1–18. arXiv : 1009,3613 . doi : 10,1016/j.artint.2013.07.002 . S2CID  2828847 .