Busting (mašinsko učenje)

U mašinskom učenju, bustovanje je ansambl meta-algoritama za smanjenje pristrasnosti, i varijanse u nadgledanom učenju, i porodice algoritama za mašinsko učenje koji pretvaraju slabe učenike u jake. Bustovanje je zasnivano na pitanju koje postavljenom od strane Kearns i Valiant (1988, 1989): „Da li može grupa slabih učenika da stvori jednog jakog učenika?“ Slab učenik je definisan kao klasifikator koji je u maloj korelaciji sa pravom klasifikacijom (može označiti primere bolje od slučajnog pogodka). Suprotno tome, jak učenik je klasifikator koji je proizvoljno dobro povezan sa pravom klasifikacijom.

Robert Šapireov potvrdan odgovor iz 1990. na pitanje postavljeno od strane Kearnsa i Valianta imao je značajne posledice u mašinskom učenju i statistici, što je dovelo do razvoja bustinga.

Algoritmi za pojačavanje

Pošto busting nije algoritamski ograničeno,mnogi algoritami za bustovanje sastoji se od iterativnog učenja slabih klasifikatora u odnosu na distribuciju i njihovog dodavanja jakom klasifikatoru. Kada se dodaju, oni se ponderišu na način koji je povezan sa preciznošću slabih učenika. Pošto se doda slab učenik, težine podataka se ponovo prilagođavaju, poznato kao "ponovno ponderisanje ". Pogrešno klasifikovani ulazni podaci dobijaju veću težinu, a primeri koji su pravilno klasifikovani gube težinu. Tako da se budući slabi učenici više fokusiraju na primere koji su prethodni slabi učenici pogrešno klasifikovali, od prethodnih.

Ilustracija koja predstavlja intuiciju koja stoji iza algoritma za pojačavanje, koji se sastoji od paralelnih učenika i ponderisanog skupa podataka.

Postoje mnogi algoritami za pojačavanje. Originalni algoritam za pojačanje, koje su predložili Robert Šapire ( formulacija rekurzivne većinske kapije) i Ioav Freund (pojačavanje većinom), nise bilo prilagodljiv i nisu mogli u celsti da iskoriste prednosti slabih učenika. Šapire i Frojnd su potom razvili AdaBoost, adaptivni algoritam za pojačavanje koji je osvojio Gedelovu nagradu .

Samo algoritmi koji su dokazivi algoritmi za pojačavanje u verovatno približno tačnoj formulaciji učenja se mogu nazvati algoritmima za pojačavanje . Ostali algoritmi koji su po slični algoritmima za pojačavanje se nekada nazivaju „algoritmi za povećanje“, iako se nekad nazivaju i algoritmi za povećanje, što je pogrešno.

Glavna razlika između algoritama za busting je njihov metod ponderisanja tačaka podataka i hipoteza za obuku. AdaBoost je veoma popularan,takođe i istorijski najznačajniji pošto je to prvi algoritam koji sto osnova uvodnog pokrivanja bustinga na univerzitetskim kursevima mašinskog učenja. Neki od novijih algoritama su LPBoost, TotalBoost, BrovnBoost, kgboost, MadaBoost, LogitBoost i drugi. Mnogi algoritmi za pojačavanje ulaze u AniBoost okvir, upravo to pokazuje da bustin vrši spuštanje gradijenta u funkcijskom prostoru koristeći konveksnu funkciju troškova .

Kategorizacija objekata u kompjuterskom vidu

Date slike sadrže različite poznate objekte u svetu, od njih klasifikator može da nauči automatski da klasifikuje objekte u budućim slikama. Jednostavni klasifikatori koji su izgrađeni na osnovu neke karakteristike slike objekta imaju sklonost da budu slabi u kategorizaciji. Korišćenje busting metode za kategorizaciju objekata je način da se ujedine slabi klasifikatori, i na osnovu togada se na poseban način poveća ukupna sposobnost kategorizacije.

Problem kategorizacije objekata

Kategorizacija objekata je klasičan zadatak kompjuterskog vida koji se zasniva na određivanju da li slika sadrži neku karakterističnu kategoriju objekta ili ne. Zamisao kategorizacije objekta je usko povezana sa raspoznavanjem, identifikacijom i detekcijom. Kategorizacija objekata se zasnova na izgledu, obično sadrži ekstrakciju karakteristika, učenje klasifikatora i primenu klasifikatora na neke nove primere. Postoji više načina da se prikaže kategorija objekata, npr. iz analize oblika, modela vrećice reči ili lokalnih deskriptora kao što je SIFT, i drugi. Neki od primera nadgledanih klasifikatora su naivni Bajesovi klasifikatori, mašine za podršku vektorima, mešavine Gausovih i neuronske mreže. Istraživanje pokazuje da se lokacije na slikama i kategorija objekata na slikama mogu otkriti i na nenadgledan način .

Status kuo za kategorizaciju objekata

Prepoznavanje kategorija objekata na slikama je zahtevan problem u kompjuterskom vidu, pogotovo kada je broj kategorija dosta veliki. To je zbog velike varijabilnosti unutar klase i potrebe za generalizacijom između varijacija objekata unutar iste kategorije. Objekti unutar jedne kategorije mogu izgledati drugačije. Isti objekat može izgledati drugačije pod drugačijim gledištima, razmerama i osvetljenjem. Pozadina i delimična okluzija između ostalog otežavaj prepoznavanje. Ljudi mogu da prepoznaju hiljade tipova objekata, a većina postojećih sistema za prepoznavanje objekata može da prepoznaje samo nekoliko,  npr. ljudska lica, automobili, jednostavni objekti, itd. Istraživanja su bila veoma aktivna u bavljenju više kategorija i omogućavanju inkrementalnog dodavanja novih kategorija, i iako opšti problem ostaje nerešen. Jedno od načina je deljenje i unapređenje funkcija.

Busting za binarnu kategorizaciju

AdaBoost može da se koristiti za prepoznavanje lica kao primer binarne kategorizacije . Dve kategorije su lica u odnosu na pozadinu. Opšti algoritam je sledeći:

1. Formirajte veliki skup prostih karakteristika
2. Inicijalizirajte težine za slike treninga
3. Za T runde
   1. Normalizovati težine
   2. Za dostupne funkcije iz skupa, obučite klasifikator koristeći jednu karakteristiku i procenite grešku u obučavanju
   3. Izaberite klasifikator greškom najmanje težine
   4. Ažurirajte težine slika treninga: povećajte ako su pogrešno klasifikovane ovim klasifikatorom, smanjite ako su ispravno klasifikovane
4. Formirajte konačni jaki klasifikator kao linearnu kombinaciju T klasifikatora (koeficijent je veći ako je greška u treningu mala)

Posle bustovanja, klasifikator napravljen od 200 karakteristika može dati stopu otkrivanja od 95% pod $10^{-5}$ lažno pozitivna stopa .

Primer pojačanja za binarnu kategorizaciju je sistem koji detektuje pešake primenjujući obrasce kretanja i izgleda. Ovaj rad je prvi koji kombinuje i informacije o kretanju i informacije o izgledu kao karakteristike za otkrivanje osobe koja hoda. Primnjujući sličan pristup Viola-Jones okviru za otkrivanje objekata .

Pojačavanje za višeklasnu kategorizaciju

U poređenju sa binarnom kategorizacijom, višeklasna kategorizacija traži zajedničke karakteristike koje se mogu deliti u kategorijama u isto vreme. Ispostavilo se da su generičke karakteristike poput ivica. Tokom učenja, detektori za svaku kategoriju mogu se zajedno obučavati. U poređenju sa odvojenim treningom, on bolje generalizuje, potrebno je manje podataka o obuci i zahteva manje funkcija da bi se dobio isti rezultat.

Glavni tok algoritma je sličan binarnom slučaju. Ono što je različito je da se mera zajedničke greške u treningu definiše unapred. Tokom svake iteracije algoritam bira klasifikator jedne karakteristike (podsticaće se karakteristike koje se mogu deliti sa više kategorija). Ovo se može uraditi pretvaranjem višeklasne klasifikacije u binarnu (skup kategorija naspram ostalih), ili uvođenjem kaznene greške iz kategorija koje nemaju obeležje klasifikatora.

U radu „Sharing visual features for multiclass and multiviev object detection“, A. Torralba et al. koristio GentleBoost za pojačavanje i pokazao da kada su podaci o obuci ograničeni, učenje putem funkcija za deljenje radi mnogo bolje nego bez deljenja, s obzirom na iste runde povećanja. Takođe, za dati nivo performansi, ukupan broj potrebnih karakteristika (a samim tim i trošak vremena rada klasifikatora) za detektore deljenja karakteristika, primećuje se da približno logaritamski skalira sa brojem klasa, tj. sporije od linearnog rasta u slučaj nedeljenja. Slični rezultati su prikazani u radu „Inkrementalno učenje detektora objekata korišćenjem abecede vizuelnog oblika“, ali su autori koristili AdaBoost za pojačavanje.

Konveksni protiv nekonveksnih algoritama za pojačavanje

Algoritmi za pojačavanje mogu biti zasnovani na konveksnim ili nekonveksnim optimizacijskim algoritmima. Konveksni algoritmi, kao što su AdaBoost i LogitBoost, mogu biti „poraženi“ nasumičnim šumom tako da ne mogu da nauče osnovne kombinacije slabih hipoteza koje se mogu naučiti. Na ovo ograničenje ukazao je Long & Servedio 2008. godine. Međutim, do 2009. godine, više autora je pokazalo da algoritmi za pojačavanje zasnovani na nekonveksnoj optimizaciji, kao što je BrovnBoost, mogu da uče iz skupova podataka sa bukom i mogu posebno da nauče osnovni klasifikator skupa podataka Long–Servedio.

Vidi još

• AdaBoost
• Random forest
• Alternating decision tree
• Bootstrap aggregating (bagging)
• Cascading
• BrownBoost
• CoBoosting
• LPBoost
• Logistic regression
• Maximum entropy methods
• Neural networks
• Support vector machines
• Gradient boosting
• Margin classifiers
• Cross-validation
• Machine learning
• List of datasets for machine learning research

Implementacije

• Scikit-learn, biblioteka otvorenog koda za mašinsko učenje za Pithon
• Orange, besplatni softverski paket za rudarenje podataka, modul Orange.ensemble
• Veka je skup alata za mašinsko učenje koji nudi različite implementacije algoritama za pojačavanje kao što su AdaBoost i LogitBoost
• R paket GBM (Generalized Boosted Regression Models) implementira proširenja za Frojndov i Šapireov AdaBoost algoritam i Fridmanovu mašinu za podizanje gradijenta.
• jboost ; AdaBoost, LogitBoost, RobustBoost, Boostekter i naizmenična stabla odlučivanja
• R paket adabag : Primenjuje Multiclass AdaBoost. M1, AdaBoost-SAMME i Bagging
• R paket kgboost : Implementacija povećanja gradijenta za linearne i modele zasnovane na stablu.

 

 

Dodatna literatura

• Ioav Freund i Robert E. Schapire (1997); Teorijska generalizacija on-line učenja i primena za unapređenje, Journal of Computer and Sistem Sciences, 55(1):119-139
• Robert E. Šapire i Joram Singer (1999); Poboljšani algoritmi za pojačavanje pomoću prediktora sa ocenjivanjem poverenja, Mašinsko učenje, 37(3):297-336

Spoljašnje veze

• Robert E. Šapire (2003); Pojačavajući pristup mašinskom učenju: Pregled, MSRI (Institut za matematičke nauke) Radionica o nelinearnoj proceni i klasifikaciji
• Zhou Zhi-Hua (2014) Boosting 25 iears Arhivirano na sajtu Wayback Machine (20. avgust 2016), CCL 2014 Keinote.
• Zhou, Zhihua (2008). „On the margin explanation of boosting algorithm.” (PDF). In: Proceedings of the 21st Annual Conference on Learning Theory (COLT'08): 479—490. 
• Zhou, Zhihua (2013). „On the doubt about margin explanation of boosting.” (PDF). Artificial Intelligence. 203: 1—18. arXiv:1009.3613 . doi:10.1016/j.artint.2013.07.002.