AdaBoost
AdaBoost
AdaBoost (eller adaptiv boosting ) er, i kunstig intelligens og maskinlæring , en boosting meta-algoritme introdusert av Yoav Freund og Robert Schapire . Den kan brukes sammen med mange andre typer læringsalgoritmer for å forbedre ytelsen. Utgangene til de andre algoritmene (kalt svake klassifikatorer ) kombineres til en vektet sum som representerer den endelige utgangen til den forsterkede klassifisereren . AdaBoost er tilpasningsdyktig i den forstand at påfølgende svake klassifiserere blir justert til fordel for prøver feilklassifisert av tidligere klassifikatorer.
AdaBoost er spesielt følsom for støyende eller dårlig korrelerte data. Imidlertid kan det i noen problemer være mindre utsatt for overmontering enn andre algoritmer. Underklassifiserene som brukes, kan være svake så lenge de presterer i det minste litt bedre enn en tilfeldig klassifikator, i så fall kan det være bevis for at den endelige modellen konvergerer til en sterk klassifikator.
Alle læringsalgoritmer har en tendens til å matche noen typer problemer mer enn andre, og har vanligvis mange forskjellige parametere og konfigurasjoner som må justeres for å oppnå optimal ytelse på et læringssett. AdaBoost (med beslutningstrær som svake arbeidsbøker) blir ofte referert til som den beste nøkkelferdige arbeidsboken.
Prinsipp
Adaboost er avhengig av iterativt utvalg av svak klassifikator basert på en distribusjon av treningseksempler. Hvert eksempel vektes i henhold til vanskeligheter med gjeldende klassifikator. Dette er et eksempel på multiplikativ vektmetode ( oppdateringsmetode for multipliserende vekter ).
Beskrivelse
La være et sett med observasjoner. Legg merke til dem: hvor skal egenskapene til individet og variabelen forutsies.
(x1,y1),...,(xm,ym){\ displaystyle (x_ {1}, y_ {1}), \ ldots, (x_ {m}, y_ {m})}xJeg∈X,{\ displaystyle x_ {i} \ i X,}Jeg{\ displaystyle i}yJeg∈Y={-1,+1}{\ displaystyle \, y_ {i} \ i Y = \ {- 1, + 1 \}}
Vi initialiserer vekten assosiert med ,Jeg{\ displaystyle i}Dt(Jeg)=1m,Jeg=1,...,m.{\ displaystyle D_ {t} (i) = {\ frac {1} {m}}, i = 1, \ ldots, m.}
For :
t=1,...,T{\ displaystyle t = 1, \ ldots, T}
- Finn funksjonen som minimerer klassifiseringsfeilen basert på vektene . Det vil si som bekrefter følgende minimeringsprogram:ht:X→{-1,+1}{\ displaystyle h_ {t}: X \ til \ {- 1, + 1 \}}ϵt{\ displaystyle \ epsilon _ {t}}Dt{\ displaystyle D_ {t}}ht{\ displaystyle h_ {t}}
ht=argminh∈H∑Jeg=1mDt(Jeg)[yJeg≠h(xJeg)]{\ displaystyle h_ {t} = \ arg \ min _ {h \ i {\ mathcal {H}}} \ sum _ {i = 1} ^ {m} D_ {t} (i) [y_ {i} \ neq h (x_ {i})]}
ϵt=∑Jeg=1mDt(Jeg)[yJeg≠h(xJeg)]{\ displaystyle \ epsilon _ {t} = \ sum _ {i = 1} ^ {m} D_ {t} (i) [y_ {i} \ neq h (x_ {i})]}
er modellfeilen.
- Hvis funksjonen er valgt, ellers stopper algoritmenϵmJegikke,t<0,5{\ displaystyle \ epsilon _ {min, t} <0.5}
- Vi beregner deretter trinnet for gradienten :, medαt∈R{\ displaystyle \ alpha _ {t} \ in \ mathbf {R}}αt=12ln1-ϵtϵt{\ displaystyle \ alpha _ {t} = {\ frac {1} {2}} {\ textrm {ln}} {\ frac {1- \ epsilon _ {t}} {\ epsilon _ {t}}}}
- Vi oppdaterer deretter vekten av eksemplene:
Dt+1(Jeg)=Dt(Jeg)e-αtyJeght(xJeg)Zt{\ displaystyle D_ {t + 1} (i) = {\ frac {D_ {t} (i) \, e ^ {- \ alpha _ {t} y_ {i} h_ {t} (x_ {i}) }} {Z_ {t}}}}
med en normaliseringsfaktor likZt{\ displaystyle Z_ {t}}2ϵt(1-ϵt){\ displaystyle 2 {\ sqrt {\ epsilon _ {t} (1- \ epsilon _ {t})}}
Når algoritmen stopper ved iterasjon , er klassifisereren som følger av utvelgelsesprosessen:
M{\ displaystyle M}
H(x)=skilt(∑t=1Mαtht(x)){\ displaystyle H (x) = {\ textrm {sign}} \ left (\ sum _ {t = 1} ^ {M} \ alpha _ {t} h_ {t} (x) \ right)}
Varianter
Varianter har blitt introdusert, og endringene gjelder hovedsakelig måten vektene oppdateres på. Blant disse variantene brukes Gentle AdaBoost og Real Adaboost ofte. Et annet eksempel er RankBoost .
Historie
Dette var en av de første fullt funksjonelle metodene for å implementere prinsippet om boosting. Forfatterne mottok den prestisjetunge Gödelprisen i 2003 for oppdagelsen.
Merknader og referanser
-
( Freund og Schapire 1997 )
-
Sanjeev Arora , Elad Hazan og Satyen Kale, “ The Multiplicative Weights Update Method: a Meta Algorithm and Applications ” .
-
“ The Multiplikative Weights Update method, ” på University of Washington .
-
Offisiell side av Gödelprisen i 2003
Bibliografi
- (en) Yoav Freund og Robert Schapire , " En beslutningsteoretisk generalisering av online læring og en applikasjon til boosting " , Journal of Computer and System Sciences , vol. 55, n o 1,1997, s. 119-139 ( les online )
Eksterne linker
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">