Förstärkning

Boosting är en  sammansatt maskininlärningsmetaalgoritm  som främst används för att minska bias ( uppskattningsfel) samt varians [1] i övervakat lärande . Också definierad som en familj av maskininlärningsalgoritmer som omvandlar svaga inlärningsalgoritmer till starka [2] .

Boosting baseras på frågan som ställdes av Kearns och Valiant (1988, 1989) [3] [4] : "Kan en uppsättning svaga inlärningsalgoritmer producera en stark inlärningsalgoritm?". En svag inlärningsalgoritm definieras som en klassificerare som är svagt korrelerad med den korrekta klassificeringen (kan märka exempel bättre än slumpmässig gissning). Till skillnad från den svaga algoritmen är den starka inlärningsalgoritmen en klassificerare som korrelerar bra med den korrekta klassificeringen.

Robert Shapires positiva svar i en uppsats från 1990 [5] på frågan om Kearns och Valiant var av stor betydelse för teori och statistik för maskininlärning och ledde till skapandet av ett brett spektrum av ökande algoritmer [6] .

Förstärkningshypotesen hänvisade till processen att ställa in en svag inlärningsalgoritm för att få stark inlärning. Informellt frågar man sig om förekomsten av en effektiv inlärningsalgoritm vars utdata är en hypotes vars prestanda bara är något bättre än slumpmässig gissning (dvs. svag inlärning) innebär att det finns en effektiv algoritm som producerar en hypotes om godtycklig noggrannhet (dvs. stark lärande) [3] . Algoritmer som kommer fram till en sådan hypotes blir snabbt kända som "boosting". Freund och Shapires "bågbildande" algoritm (Adaptive Resampling and Combining) [7] som generell teknik är mer eller mindre synonymt med boosting [8]

Förstärkningsalgoritmer

Även om förstärkning inte är algoritmiskt begränsad, består de flesta förstärkningsalgoritmer av iterativ träning av svaga klassificerare för att sätta ihop dem till en stark klassificerare. När de läggs till tilldelas de oftast vikter på något sätt, som vanligtvis är relaterade till träningsnoggrannhet. Efter att den svaga klassificeraren har lagts till räknas vikterna om, vilket är känt som "viktomräkning" . Felklassificerade indata ökar i vikt, medan korrekt klassificerade instanser går ner i vikt [anm 1] . Således fokuserar efterföljande svag inlärning mer på exempel där tidigare svag inlärning har felklassificerats.

Det finns många förstärkningsalgoritmer. De ursprungliga algoritmerna som föreslagits av Robert Shapire ( rekursiv majoritetsportformulering ) [ 5] och Yoav Freund (förstärkning av dominans) [9] var inte adaptiva och kunde inte ge den fulla fördelen av svag inlärning. Shapire och Freund utvecklade sedan AdaBoost (Adaptive Boosting), en adaptiv boostingsalgoritm som vann det prestigefyllda Gödelpriset .  

Endast algoritmer för vilka det kan bevisas att de är boostande algoritmer i formuleringen av ungefär korrekt inlärning kan exakt kallas för boostingalgoritmer . Andra algoritmer som till sin anda liknar förstärkningsalgoritmer kallas ibland hävstångsalgoritmer , även om de ibland felaktigt också kallas för ökande algoritmer [ 9] . 

Den huvudsakliga skillnaden mellan många förstärkningsalgoritmer ligger i metoderna för att bestämma vikter av träningsdatapunkter [ och hypoteser . AdaBoost-algoritmen är mycket populär och historiskt sett den mest betydelsefulla eftersom det var den första algoritmen som kunde anpassa sig till svag inlärning. Algoritmen används ofta som en grundläggande introduktion till att boosta algoritmer i maskininlärningskurser vid universitet [10] . Det finns många nyligen utvecklade algoritmer som LPBoost [ , TotalBoost , BrownBoost , xgboost , MadaBoost, LogitBoost et al.[ i funktionsutrymme med en konvex förlustfunktion .

Klassificering av funktioner i datorseende

Med tanke på bilder som innehåller olika kända objekt i världen, kan en klassificerare tränas utifrån dem att automatiskt klassificera objekt i framtida okända bilder. Enkla klassificerare, byggda på basis av vissa funktioner i objektbilden, visar sig vanligtvis vara ineffektiva vid klassificering. Att använda förstärkningsmetoder för att klassificera objekt är ett sätt att kombinera svaga klassificerare på ett specifikt sätt för att förbättra den övergripande klassificeringsförmågan.

Uppgiften att klassificera objekt

Funktionsklassificering är en typisk uppgift för datorseende , där det bestäms om en bild innehåller en viss kategori av objekt eller inte. Idén är nära relaterad till igenkänning, identifiering och upptäckt. Klassificering genom objektdetektering innehåller vanligtvis funktionsextraktion , träning av en klassificerare och tillämpning av klassificeraren på ny data. Det finns många sätt att representera en kategori av objekt, till exempel att analysera formen , använda bag of words- modellen , använda lokala deskriptorer som SIFT , och så vidare. Exempel på övervakade klassificerare är naiva bayes-klassificerare , stödvektormaskiner , blandning av gausser och nätverk . Studier har dock visat att objektkategorier och deras position i bilder också kan detekteras med hjälp av oövervakad inlärning [11] .

Status quo för att klassificera objekt

Att känna igen kategorier av objekt i bilder är en svår uppgift i datorseende , särskilt om antalet kategorier är stort. Detta är en konsekvens av klassernas höga interna variabilitet och behovet av att generalisera olika begrepp inom en klass. Objekt i samma kategori kan se helt olika ut. Även samma föremål kan se annorlunda ut från olika utsiktspunkter, skala eller belysning . Bakgrundsbrus och partiella överlappningar bidrar också till komplexiteten i igenkänningen [12] . Människor är kapabla att känna igen tusentals typer av objekt, medan de flesta befintliga objektigenkänningssystem är tränade att känna igen endast ett fåtal, såsom mänskliga ansikten , bilar , enkla föremål, etc. [13] . Forskning om att öka antalet kategorier och möjligheten att lägga till nya kategorier bedrivs aktivt, och även om det generella problemet ännu inte är löst, har detektorer för ett stort antal kategorier (upp till hundratals och tusentals [14] ) utvecklats. . Detta uppnås i synnerhet genom att dela funktionerna och öka.

Boosting för binär klassificering

AdaBoost-paketet kan användas för ansiktsigenkänning som ett exempel på binär klassificering . De två kategorierna är ansikten och bakgrund. Den allmänna algoritmen ser ut så här:

  1. Vi bildar en stor uppsättning funktioner
  2. Initiera vikterna för träningsuppsättningen med bilder
  3. Att göra T-körningar
    1. Normalisera vikter
    2. För de tillgängliga funktionerna från setet tränar vi klassificeraren med hjälp av en av funktionerna och beräknar träningsfelet
    3. Att välja en klassificerare med det minsta felet
    4. Uppdatera träningsbildens vikter: öka om den klassificeras felaktigt och minska om den är korrekt
  4. Vi bildar den slutliga starka klassificeraren som en linjär kombination av T-klassificerare (koefficienten är större om träningsfelet är mindre)

Efter förstärkning kan en klassificerare byggd av 200 funktioner nå 95 % av framgångsrika igenkänningar med positiva igenkänningsfel [15] .

En annan tillämpning av förstärkning för binär klassificering är ett system som känner igen fotgängare med hjälp av rörelsemönster och utseende [16] . Detta arbete kombinerar rörelseinformation och utseende som funktioner för att upptäcka en rörlig person för första gången. Vi använder ett tillvägagångssätt som liknar Viola-Jones objektdetekteringsmodell .

Multiclass classification boosting

Jämfört med binär klassificering söker efter gemensamma funktioner som kan delas mellan kategorier samtidigt. De visar sig vara mer allmänna, som funktionen " gräns " . Under träningen kan klassificerare för varje kategori tränas gemensamt. Jämfört med separat träning har sådan träning bättre generalisering , kräver mindre träningsdata och färre funktioner behövs för att uppnå önskat resultat.

Den grundläggande operationen av algoritmen liknar det binära fallet. Skillnaden är att måttet på ledträningsfel kan bestämmas i förväg. Under varje iteration väljer algoritmen en enda funktionsklassificerare (funktioner som kan klassificeras gemensamt uppmuntras). Detta kan göras genom att konvertera flerklassklassificeringen till binär (uppsättning av kategorier/andra kategorier) [17] eller genom att straffa kategorier som inte har funktioner som känns igen av klassificeraren [18] .

I Sharing visual features for multiclass and multiview object detection, använde A. Torralba et al. GentleBoost för att öka och visade att om träningsdata är begränsad, gör inlärning med delade använda egenskaper jobbet mycket bättre än utan att dela. För en given prestandanivå växer också det totala antalet funktioner som krävs (och därför klassificerarens körtid) för att detektera funktionsdelning ungefär logaritmiskt med antalet klasser, dvs. långsammare än den linjära som inträffar i fallet med ingen delning. Liknande resultat visas i artikeln "Inkrementell inlärning av objektdetektion med hjälp av alfabetet av visuella bilder", men författarna använde AdaBoost för att öka .

Konvexa och icke-konvexa förstärkningsalgoritmer

Boostalgoritmer kan baseras på konvexa eller icke-konvexa optimeringsalgoritmer. Konvexa algoritmer som AdaBoost och LogitBoost kan krascha på grund av slumpmässigt brus eftersom de inte kan lära ut grundläggande och lärbara kombinationer av svaga hypoteser [19] [20] . Denna begränsning påpekades av Long och Servedo 2008. Men 2009 visade flera författare att förstärkningsalgoritmer baserade på icke-konvex optimering som BrownBoost kan tränas från bullriga data och den underliggande Long-Servedio-klassificeraren för datasetet kan tränas .

Se även

Implementering

Anteckningar

  1. ↑ . Vissa förstärkningsbaserade klassificeringsalgoritmer minskar faktiskt vikten av omklassificerade instanser. Till exempel dominanshöjning ( engelska  boost by majoritet ) och BrownBoost
  1. ↑ Breiman, 1996 .
  2. ↑ Zhi-Hua, 2012 , sid. 23.
  3. ↑ 12 Kearns , 1988 .
  4. ↑ Kearns, Valiant, 1989 , sid. 433–444.
  5. ↑ 1 2 Schapire, 1990 , sid. 197–227.
  6. ↑ Breiman, 1998 , sid. 801–849.
  7. ↑ Freund och Schapire 1997 , sid. 119-139.
  8. ↑ Leo Briman ( Breiman 1998 ) skriver: ”Begreppet svagt lärande introducerades av Kearns och Valiant ( 1988 , Kearns, Valiant, 1989 ), som tog upp frågan om huruvida svag och stark inlärning är likvärdiga. Frågan har kallats ett ökande problem , eftersom lösningen är att öka den svaga noggrannheten hos svag inlärning till den höga noggrannheten hos stark inlärning. Shapire (1990) bevisade att boostning är möjlig. Boostalgoritmen är en metod som tar en svag inlärningsmetod och omvandlar den till en stark metod. Freund och Shapire (1997) bevisade att en algoritm som arc-fs ökar."
  9. ↑ 1 2 3 Mason, Baxter, Bartlett, Frean, 2000 , sid. 512-518.
  10. ↑ Emer, Eric Boosting (AdaBoost-algoritm) (länk ej tillgänglig) . MIT . Hämtad 10 oktober 2018. Arkiverad från originalet 15 februari 2020. 
  11. ↑ Sivic, Russell, Efros, Zisserman, Freeman, 2005 , sid. 370-377.
  12. ↑ Opelt, Pinz, Fussenegger, Auer, 2006 , sid. 416-431.
  13. ↑ Marszalek, Schmid, 2007 .
  14. ↑ Storskalig Visual Recognition Challenge (december 2017). Hämtad 6 november 2018. Arkiverad från originalet 2 november 2018.
  15. ↑ Viola, Jones, 2001 .
  16. ↑ Viola, Jones, Snow, 2003 .
  17. ↑ Torralba, Murphy, Freeman, 2007 , sid. 854-869.
  18. ↑ Opelt, Pinz, Zisserma, 2006 , sid. 3-10.
  19. ↑ Long, Servedio, 2008 , sid. 608-615.
  20. ↑ Long, Servedio, 2010 , sid. 287–304.

Litteratur

Länkar