Posilování

Boosting je kompoziční meta-algoritmus strojového učení ,   který se používá hlavně ke snížení zkreslení (chyby odhadu) a také rozptylu [1] při učení pod dohledem . Také definováno jako rodina algoritmů strojového učení, které transformují slabé algoritmy učení na silné [2] .

Posilování je založeno na otázce, kterou položili Kearns a Valiant (1988, 1989) [3] [4] : ​​„Může sada slabých učebních algoritmů vytvořit silný algoritmus učení?“. Algoritmus slabého učení je definován jako klasifikátor , který slabě koreluje se správnou klasifikací (může označit příklady lépe než náhodné hádání). Na rozdíl od slabého algoritmu je algoritmus silného učení klasifikátor, který dobře koreluje se správnou klasifikací.

Pozitivní odpověď Roberta Shapira v článku z roku 1990 [5] na otázku Kearnse a Valianta měla velký význam pro teorii a statistiku strojového učení a vedla k vytvoření široké škály posilovacích algoritmů [6] .

Posilující hypotéza odkazovala na proces ladění slabého algoritmu učení k získání silného učení. Neformálně se ptáme, zda existence účinného algoritmu učení, jehož výstupem je hypotéza, jejíž výkon je jen o málo lepší než náhodné odhadování (tj. slabé učení), implikuje existenci účinného algoritmu, který vytváří hypotézu libovolné přesnosti (tj. učení) [3] . Algoritmy, které dospějí k takové hypotéze, se rychle stanou známými jednoduše jako „posílení“. Freundův a Shapireův algoritmus „arcing“ (Adaptive Resampling and Combining) [7] jako obecná technika je víceméně synonymem pro posílení [8].

Posilovací algoritmy

I když zesilování není algoritmicky omezeno, většina zesilovacích algoritmů sestává z iterativního trénování slabých klasifikátorů za účelem jejich sestavení do silného klasifikátoru. Když se sčítají, většinou jim jsou nějakým způsobem přiřazeny váhy, které většinou souvisí s přesností tréninku. Po přidání slabého klasifikátoru se váhy přepočítají, což je známé jako "přepočet váhy" . Špatně klasifikované vstupy nabývají na váze, zatímco správně klasifikované případy ztrácejí váhu [nb 1] . Následné slabé učení se tedy více zaměřuje na příklady, kdy předchozí slabé učení bylo špatně klasifikováno.

Existuje mnoho posilovacích algoritmů. Původní algoritmy navržené Robertem Shapirem ( formulace rekurzivní většinové brány ) [5] a Yoavem Freundem (posílení dominance) [9] nebyly adaptivní a nemohly poskytnout plnou výhodu slabého učení. Shapire a Freund poté vyvinuli AdaBoost (Adaptive Boosting), adaptivní posilovací algoritmus, který získal prestižní Gödelovu cenu .  

Pouze algoritmy, u kterých lze prokázat, že jsou posilovacími algoritmy při formulaci přibližně správného učení , lze přesně nazvat posilovacími algoritmy . Jiné algoritmy, které jsou v duchu podobné posilovacím algoritmům, se někdy nazývají pákové algoritmy , i když se někdy také nesprávně nazývají posilovací algoritmy [ 9] . 

Hlavní rozdíl mezi mnoha posilovacími algoritmy spočívá v metodách určování vah trénovacích datových bodů a hypotézách . Algoritmus AdaBoost je velmi populární a historicky nejvýznamnější, protože to byl první algoritmus, který se dokázal přizpůsobit slabému učení. Algoritmus se často používá jako základní úvod do posilovacích algoritmů v kurzech strojového učení na univerzitách [10] . Existuje mnoho nedávno vyvinutých algoritmů, jako je LPBoost [ , TotalBoost, BrownBoost , xgboost , MadaBoost, LogitBoost a další[ v prostoru funkcí pomocí konvexní ztrátové funkce .

Klasifikace vlastností v počítačovém vidění

Vzhledem k obrázkům obsahujícím různé známé objekty na světě lze na jejich základě natrénovat klasifikátor, aby automaticky klasifikoval objekty do budoucích neznámých obrázků. Jednoduché klasifikátory, postavené na základě některých vlastností obrazu objektu, se obvykle při klasifikaci ukážou jako neúčinné. Použití metod zesílení ke klasifikaci objektů je způsob, jak specifickým způsobem kombinovat slabé klasifikátory, aby se zlepšila celková schopnost klasifikace.

Úkol klasifikace objektů

Klasifikace jevů je typickým úkolem počítačového vidění , kde se zjišťuje, zda obrázek obsahuje určitou kategorii objektů či nikoli. Myšlenka úzce souvisí s rozpoznáváním, identifikací a detekcí. Klasifikace pomocí detekce objektů obvykle obsahuje extrakci funkcí , trénování klasifikátoru a aplikaci klasifikátoru na nová data. Existuje mnoho způsobů, jak reprezentovat kategorii objektů, jako je analýza formuláře , použití modelu pytle slov , použití místních deskriptorů, jako je SIFT a tak dále. Příklady kontrolovaných klasifikátorů jsou naivní bayesovy klasifikátory , podpůrné vektorové stroje ,směs Gaussiánů neuronové sítě . Studie však ukázaly, že kategorie objektů a jejich pozice v obrazech mohou být také detekovány pomocí učení bez dozoru [11] .

Status quo pro klasifikaci objektů

Rozpoznávání kategorií objektů na obrázcích je v počítačovém vidění obtížným úkolem , zvláště pokud je počet kategorií velký. Je to důsledek vysoké vnitřní variability tříd a potřeby zobecňovat různé pojmy v rámci třídy. Objekty ve stejné kategorii mohou vypadat úplně jinak. I stejný objekt může vypadat odlišně z různých pohledů, měřítka nebo osvětlení . Složitost rozpoznávání také zvyšuje šum pozadí a částečné překrývání [12] . Lidé jsou schopni rozpoznávat tisíce typů objektů, zatímco většina existujících systémů rozpoznávání objektů je trénována tak, aby rozpoznávala pouze několik, jako jsou lidské tváře , auta , jednoduché objekty atd. [13] . Výzkum navyšování počtu kategorií a možnosti přidávání nových kategorií se aktivně provádí, a přestože obecný problém dosud není vyřešen, byly vyvinuty detektory pro velké množství kategorií (až stovky a tisíce [14] ) . . Toho je dosaženo zejména sdílením funkcí a posílením.

Posílení pro binární klasifikaci

Balíček AdaBoost lze použít pro rozpoznávání obličeje jako příklad binární klasifikace . Dvě kategorie jsou tváře a pozadí. Obecný algoritmus vypadá takto:

  1. Tvoříme velkou sadu funkcí
  2. Inicializace vah pro tréninkovou sadu obrázků
  3. Tvorba T běží
    1. Normalizujte váhy
    2. Pro dostupné funkce ze sady trénujeme klasifikátor pomocí jedné z funkcí a vypočítáme chybu tréninku
    3. Výběr klasifikátoru s nejmenší chybou
    4. Aktualizace vah tréninkového obrázku: zvýšení, pokud je klasifikováno nesprávně, a snížení, pokud je správné
  4. Výsledný silný klasifikátor tvoříme jako lineární kombinaci T klasifikátorů (koeficient je větší, pokud je chyba tréninku menší)

Po posílení může klasifikátor sestavený z 200 prvků dosáhnout 95 % úspěšných rozpoznání s pozitivními chybami rozpoznávání [15] .

Další aplikací posilování pro binární klasifikaci je systém, který rozpoznává chodce pomocí vzorců pohybu a vzhledu [16] . Tato práce kombinuje informace o pohybu a vzhled jako funkce pro první detekci pohybující se osoby. Využíváme přístup podobný modelu detekce objektů Viola-Jones .

Posílení vícetřídní klasifikace

Ve srovnání s binární klasifikací vícetřídní klasifikace společné rysy, které mohou být sdíleny mezi kategoriemi současně. Ukázalo se, že jsou obecnější, jako je funkce „ ohraničení “ . Během tréninku mohou být klasifikátoři pro každou kategorii trénováni společně. Ve srovnání se samostatným školením má takové školení lepší zobecnění , vyžaduje méně školicích dat a k dosažení požadovaného výsledku je potřeba méně funkcí.

Základní operace algoritmu je podobná binárnímu případu. Rozdíl je v tom, že míru chyby společného tréninku lze určit předem. Během každé iterace algoritmus vybere jeden klasifikátor prvků (podporují se prvky, které lze klasifikovat společně). Toho lze dosáhnout převedením vícetřídní klasifikace na binární (soubor kategorií/jiných kategorií) [17] nebo penalizací kategorií, které nemají znaky rozpoznávané klasifikátorem [18] .

Ve Sdílení vizuálních funkcí pro detekci vícetřídních a vícepohledových objektů použili A. Torralba a kol. Pro danou výkonnostní úroveň také celkový počet funkcí potřebných (a tedy i doba běhu klasifikátoru) k detekci sdílení funkcí roste přibližně logaritmicky s počtem tříd, tj. pomaleji než lineární , ke kterému dochází v případě žádné sdílení. Podobné výsledky jsou uvedeny v článku „Incremental learning of object detection using the alphabet of visual images“, nicméně autoři použili AdaBoost pro posílení .

Konvexní a nekonvexní posilovací algoritmy

Posilovací algoritmy mohou být založeny na konvexních nebo nekonvexních optimalizačních algoritmech. Konvexní algoritmy jako AdaBoost a LogitBoost mohou selhat kvůli náhodnému šumu, protože nemohou naučit základní a naučitelné kombinace slabých hypotéz [19] [20] . Na toto omezení poukázali Long a Servedo v roce 2008. V roce 2009 však několik autorů prokázalo, že zesilovací algoritmy založené na nekonvexní optimalizaci, jako je BrownBoost , lze trénovat z hlučných dat a lze natrénovat základní klasifikátor Long-Servedio pro datovou sadu. .

Viz také

Implementace

Poznámky

  1. ↑ . Některé klasifikační algoritmy založené na posílení ve skutečnosti snižují váhu znovu chybně klasifikovaných instancí. Například posílení dominance ( anglicky  posílení většinou ) a BrownBoost
  1. ↑ Breiman, 1996 .
  2. ↑ Zhi-Hua, 2012 , str. 23.
  3. ↑ 12 Kearns , 1988 .
  4. ↑ Kearns, Valiant, 1989 , str. 433–444.
  5. ↑ 1 2 Schapire, 1990 , str. 197–227.
  6. ↑ Breiman, 1998 , s. 801–849.
  7. ↑ Freund a Schapire 1997 , str. 119-139.
  8. ↑ Leo Briman ( Breiman 1998 ) píše: „Koncept slabého učení zavedli Kearns a Valiant ( 1988 , Kearns, Valiant, 1989 ), kteří položili otázku, zda jsou slabé a silné učení rovnocenné. Tato otázka byla nazvána jako posilující problém , protože řešením je zvýšit slabou přesnost slabého učení na vysokou přesnost silného učení. Shapire (1990) dokázal, že boostování je možné. Algoritmus zesílení je metoda, která využívá slabou metodu učení a transformuje ji na silnou metodu. Freund a Shapire (1997) prokázali, že algoritmus, jako je arc-fs, posiluje."
  9. ↑ 1 2 3 Mason, Baxter, Bartlett, Frean, 2000 , str. 512-518.
  10. ↑ Emer, Eric Boosting (algoritmus AdaBoost) (odkaz není k dispozici) . MIT . Získáno 10. října 2018. Archivováno z originálu 15. února 2020. 
  11. ↑ Sivic, Russell, Efros, Zisserman, Freeman, 2005 , str. 370-377.
  12. ↑ Opelt, Pinz, Fussenegger, Auer, 2006 , str. 416-431.
  13. ↑ Marszálek, Schmid, 2007 .
  14. ↑ Velká výzva pro vizuální rozpoznávání (prosinec 2017). Staženo 6. listopadu 2018. Archivováno z originálu 2. listopadu 2018.
  15. ↑ Viola, Jones, 2001 .
  16. ↑ Viola, Jones, Snow, 2003 .
  17. ↑ Torralba, Murphy, Freeman, 2007 , str. 854-869.
  18. ↑ Opelt, Pinz, Zisserma, 2006 , str. 3-10.
  19. ↑ Long, Servedio, 2008 , str. 608-615.
  20. ↑ Long, Servedio, 2010 , str. 287–304.

Literatura

Odkazy