Boostning

Boosting er en  kompositionel maskinlæringsmetaalgoritme  , der hovedsageligt bruges til at reducere bias ( estimeringsfejl) samt varians [1] i overvåget læring . Også defineret som en familie af maskinlæringsalgoritmer, der transformerer svage indlæringsalgoritmer til stærke [2] .

Boosting er baseret på spørgsmålet rejst af Kearns og Valiant (1988, 1989) [3] [4] : "Kan et sæt af svage læringsalgoritmer producere en stærk læringsalgoritme?". En svag indlæringsalgoritme er defineret som en klassificering , der er svagt korreleret med den korrekte klassifikation (kan betegne eksempler bedre end tilfældig gæt). I modsætning til den svage algoritme er den stærke læringsalgoritme en klassificering, der korrelerer godt med den korrekte klassifikation.

Robert Shapires positive svar i et papir fra 1990 [5] på spørgsmålet om Kearns og Valiant var af stor betydning for maskinlæringsteori og statistik og førte til skabelsen af ​​en bred vifte af boostende algoritmer [6] .

Boosthypotesen refererede til processen med at tune en svag læringsalgoritme for at opnå stærk læring. Uformelt spørger man, om eksistensen af ​​en effektiv læringsalgoritme, hvis output er en hypotese, hvis ydeevne kun er lidt bedre end tilfældig gæt (dvs. svag læring) indebærer eksistensen af ​​en effektiv algoritme, der producerer en hypotese om vilkårlig nøjagtighed (dvs. stærk) læring) [3] . Algoritmer, der når frem til en sådan hypotese, bliver hurtigt kendt som "boosting". Freund og Shapires "arcing"-algoritme (Adaptive Resampling and Combining) [7] som generel teknik er mere eller mindre synonymt med boosting [8]

Boost algoritmer

Selvom boostning ikke er algoritmisk begrænset, består de fleste boostningsalgoritmer af iterativ træning af svage klassifikatorer for at samle dem til en stærk klassifikator. Når de tilføjes, tildeles de normalt vægte på en eller anden måde, som normalt er relateret til træningsnøjagtighed. Efter at den svage klassificering er tilføjet, genberegnes vægtene, hvilket er kendt som "vægtgenberegning" . Fejlklassificerede input tager mere vægt, mens korrekt klassificerede forekomster taber sig [nb 1] . Således fokuserer efterfølgende svag læring mere på eksempler, hvor tidligere svag læring har fejlklassificeret.

Der er mange boostningsalgoritmer. De originale algoritmer foreslået af Robert Shapire ( rekursiv majoritetsportformulering ) [5] og Yoav Freund (forøgelse af  dominans) [9] var ikke adaptive og kunne ikke give den fulde fordel af svag læring. Shapire og Freund udviklede derefter AdaBoost (Adaptive Boosting), en adaptiv boostingsalgoritme, der vandt den prestigefyldte Gödel-pris .

Kun algoritmer, for hvilke det kan bevises, at de er boostende algoritmer i formuleringen af ​​nogenlunde korrekt indlæring , kan præcist kaldes boostingalgoritmer . Andre algoritmer, der i ånden ligner boostende algoritmer, kaldes nogle gange løftestangsalgoritmer , selvom de nogle gange også forkert kaldes boostingsalgoritmer [ 9] . 

Den største divergens mellem mange boostningsalgoritmer ligger i metoderne til at bestemme vægten af træningsdatapunkter [ og hypoteser . AdaBoost-algoritmen er meget populær og historisk set den mest betydningsfulde, da det var den første algoritme, der var i stand til at tilpasse sig svag indlæring. Algoritmen bruges ofte som en grundlæggende introduktion til at booste algoritmer i maskinlæringskurser på universiteter [10] . Der er mange nyligt udviklede algoritmer såsom LPBoost [ , TotalBoost, BrownBoost , xgboost , MadaBoost, LogitBoost et al.[ i feature space ved hjælp af en konveks tabsfunktion .

Klassificering af funktioner i computervision

Givet billeder, der indeholder forskellige kendte objekter i verden, kan en klassifikator trænes baseret på dem til automatisk at klassificere objekter i fremtidige ukendte billeder. Simple klassifikatorer, bygget på basis af nogle funktioner i objektbilledet, viser sig normalt at være ineffektive til klassificering. Brug af boosting-metoder til at klassificere objekter er en måde at kombinere svage klassifikatorer på en specifik måde for at forbedre den overordnede klassificeringsevne.

Opgaven med at klassificere objekter

Funktionsklassifikation er en typisk opgave for computersyn , hvor det bestemmes, om et billede indeholder en bestemt kategori af objekter eller ej. Idéen er tæt forbundet med genkendelse, identifikation og detektion. Klassificering efter objektdetektering indeholder typisk funktionsudtræk , træning af en klassifikator og anvendelse af klassifikator på nye data. Der er mange måder at repræsentere en kategori af objekter på, såsom at analysere formen , bruge posen med ord- modellen , bruge lokale deskriptorer såsom SIFT , og så videre. Eksempler på overvågede klassifikatorer er naive bayes-klassifikatorer , støttevektormaskiner , blanding af gaussere og netværk . Undersøgelser har dog vist, at objektkategorier og deres placering i billeder også kan detekteres ved hjælp af uovervåget læring [11] .

Status quo for klassificering af objekter

At genkende kategorier af objekter i billeder er en vanskelig opgave i computersyn , især hvis antallet af kategorier er stort. Dette er en konsekvens af klassernes høje interne variabilitet og behovet for at generalisere forskellige begreber inden for en klasse. Objekter i samme kategori kan se helt anderledes ud. Selv det samme objekt kan se anderledes ud fra forskellige udsigtspunkter, skala eller belysning . Baggrundsstøj og delvise overlapninger øger også kompleksiteten af ​​genkendelsen [12] . Mennesker er i stand til at genkende tusindvis af typer objekter, mens de fleste eksisterende objektgenkendelsessystemer er trænet til kun at genkende nogle få, såsom menneskeansigter , biler , simple objekter osv. [13] . Der forskes aktivt i at øge antallet af kategorier og muligheden for at tilføje nye kategorier, og selvom det generelle problem endnu ikke er løst, er der udviklet detektorer for en lang række kategorier (op til hundreder og tusinder [14] ) . Dette opnås især ved at dele funktionerne og booste.

Boosting for binær klassificering

AdaBoost-pakken kan bruges til ansigtsgenkendelse som et eksempel på binær klassificering . De to kategorier er ansigter og baggrund. Den generelle algoritme ser således ud:

  1. Vi danner et stort sæt funktioner
  2. Initialisering af vægtene til træningssættet af billeder
  3. At lave T-løb
    1. Normaliser vægte
    2. For de tilgængelige funktioner fra sættet træner vi klassificereren ved hjælp af en af ​​funktionerne og beregner træningsfejlen
    3. At vælge en klassificering med den mindste fejl
    4. Opdater træningsbilledvægte: øg, hvis de er klassificeret forkert, og reducer, hvis de er korrekte
  4. Vi danner den endelige stærke klassifikator som en lineær kombination af T-klassifikatorer (koefficienten er større, hvis træningsfejlen er mindre)

Efter boosting kan en klassificeringsanordning bygget af 200 funktioner nå 95 % af succesrige genkendelser med positive genkendelsesfejl [15] .

En anden anvendelse af boosting til binær klassificering er et system, der genkender fodgængere ved hjælp af bevægelsesmønstre og udseende [16] . Dette værk kombinerer bevægelsesinformation og udseende som funktioner til at opdage en person i bevægelse for første gang. Vi tager en tilgang, der ligner Viola-Jones objektdetektionsmodellen .

Multiclass klassifikationsforøgelse

Sammenlignet med binær klassifikation multiklasseklassifikation efter fælles funktioner, der kan deles mellem kategorier på samme tid. De viser sig at være mere generelle, som " grænse " -funktionen . Under træningen kan klassificerere for hver kategori trænes i fællesskab. Sammenlignet med separat træning har sådan træning bedre generalisering , kræver færre træningsdata, og færre funktioner er nødvendige for at opnå det ønskede resultat.

Den grundlæggende operation af algoritmen ligner det binære tilfælde. Forskellen er, at målet for fælles træningsfejl kan bestemmes på forhånd. Under hver iteration vælger algoritmen en enkelt funktionsklassifikator (funktioner, der kan klassificeres i fællesskab, opmuntres). Dette kan gøres ved at konvertere multi-class klassifikationen til binær (sæt af kategorier/andre kategorier) [17] eller ved at straffe kategorier, der ikke har funktioner, der genkendes af klassificeringen [18] .

I Deling af visuelle funktioner til multiclass- og multiview-objektdetektion brugte A. Torralba et al. GentleBoost til at booste og viste, at hvis træningsdata er begrænset, gør læring med fælles brugte egenskaber arbejdet meget bedre end uden deling. For et givet præstationsniveau vokser det samlede antal funktioner, der kræves (og derfor klassifikationens køretid) for at detektere funktionsdeling tilnærmelsesvis logaritmisk med antallet af klasser, dvs. langsommere end den lineære , der forekommer i tilfælde af ingen deling. Lignende resultater er vist i artiklen "Inkrementel læring af objektdetektion ved hjælp af alfabetet af visuelle billeder", men forfatterne brugte AdaBoost til at booste .

Konvekse og ikke-konvekse boostningsalgoritmer

Boostalgoritmer kan være baseret på konvekse eller ikke-konvekse optimeringsalgoritmer. Konvekse algoritmer som AdaBoost og LogitBoost kan gå ned på grund af tilfældig støj, fordi de ikke kan lære grundlæggende og lærbare kombinationer af svage hypoteser [19] [20] . Denne begrænsning blev påpeget af Long og Servedo i 2008. Men i 2009 demonstrerede flere forfattere, at boostningsalgoritmer baseret på ikke-konveks optimering såsom BrownBoost kan trænes ud fra støjende data, og den underliggende Long-Servedio klassifikator for datasættet kan trænes .

Se også

Implementering

Noter

  1. ↑ . Nogle boost-baserede klassifikationsalgoritmer reducerer faktisk vægten af ​​omklassificerede forekomster. For eksempel dominansboosting ( engelsk  boost by majoritet ) og BrownBoost
  1. ↑ Breiman, 1996 .
  2. ↑ Zhi-Hua, 2012 , s. 23.
  3. ↑ 12 Kearns , 1988 .
  4. ↑ Kearns, Valiant, 1989 , s. 433-444.
  5. ↑ 1 2 Schapire, 1990 , s. 197-227.
  6. ↑ Breiman, 1998 , s. 801-849.
  7. ↑ Freund og Schapire 1997 , s. 119-139.
  8. ↑ Leo Briman ( Breiman 1998 ) skriver: “Begrebet svag læring blev introduceret af Kearns og Valiant ( 1988 , Kearns, Valiant, 1989 ), som rejste spørgsmålet om, hvorvidt svag og stærk læring er ækvivalente. Spørgsmålet er blevet kaldt et boostningsproblem , da løsningen er at øge den svage nøjagtighed af svag læring til den høje nøjagtighed af stærk læring. Shapire (1990) beviste, at boosting er muligt. Boost-algoritmen er en metode, der tager en svag indlæringsmetode og transformerer den til en stærk metode. Freund og Shapire (1997) beviste, at en algoritme som arc-fs øger."
  9. ↑ 1 2 3 Mason, Baxter, Bartlett, Frean, 2000 , s. 512-518.
  10. ↑ Emer, Eric Boosting (AdaBoost-algoritme) (link ikke tilgængeligt) . MIT . Hentet 10. oktober 2018. Arkiveret fra originalen 15. februar 2020. 
  11. ↑ Sivic, Russell, Efros, Zisserman, Freeman, 2005 , s. 370-377.
  12. ↑ Opelt, Pinz, Fussenegger, Auer, 2006 , s. 416-431.
  13. ↑ Marszalek, Schmid, 2007 .
  14. ↑ Storskala visuel genkendelsesudfordring (december 2017). Hentet 6. november 2018. Arkiveret fra originalen 2. november 2018.
  15. ↑ Viola, Jones, 2001 .
  16. ↑ Viola, Jones, Snow, 2003 .
  17. ↑ Torralba, Murphy, Freeman, 2007 , s. 854-869.
  18. ↑ Opelt, Pinz, Zisserma, 2006 , s. 3-10.
  19. ↑ Long, Servedio, 2008 , s. 608-615.
  20. ↑ Long, Servedio, 2010 , s. 287-304.

Litteratur

Links