AdaBoost

AdaBoost , kort för Adaptive Boosting , är en metaalgoritm för statistisk klassificering som formulerades av Yoav Freund och Robert Schapire 1995, som vann Gödelpriset 2003 för sitt arbete. Den kan användas tillsammans med många andra typer av inlärningsalgoritmer för att förbättra prestandan. Utdata från de andra inlärningsalgoritmerna ('svaga inlärare') kombineras till en viktad summa som representerar slutresultatet från den förstärkta klassificeraren. Vanligtvis presenteras AdaBoost för binär klassificering , även om den kan generaliseras till flera klasser eller avgränsade intervall på den verkliga linjen.

AdaBoost är adaptiv i den meningen att efterföljande svaga elever justeras till förmån för de fall som felklassificerats av tidigare klassificerare. I vissa problem kan det vara mindre mottagligt för överanpassningsproblemet än andra inlärningsalgoritmer. De individuella eleverna kan vara svaga, men så länge prestandan för var och en är något bättre än slumpmässiga gissningar, kan den slutliga modellen bevisas konvergera till en stark elev.

Även om AdaBoost vanligtvis används för att kombinera svaga basinlärare (som beslutsstumpar ), har det visat sig att det också effektivt kan kombinera starka basinlärare (som djupa beslutsträd ), vilket ger en ännu mer exakt modell.

Varje inlärningsalgoritm tenderar att passa vissa problemtyper bättre än andra, och har vanligtvis många olika parametrar och konfigurationer att justera innan den uppnår optimal prestanda på en datauppsättning. AdaBoost (med beslutsträd som de svaga lärarna) kallas ofta för den bästa klassificeraren direkt. När den används med beslutsträdsinlärning matas information som samlats in i varje steg av AdaBoost-algoritmen om den relativa "hårdheten" för varje träningsprov in i trädodlingsalgoritmen så att senare träd tenderar att fokusera på svårare att klassificera exempel.

Träning

AdaBoost hänvisar till en viss metod för att träna en förstärkt klassificerare. En förstärkt klassificerare är en klassificerare av formen

$F_{T}(x)=\summa _{t=1}^{T}f_{t}(x)\,\!$

där varje $f_{t}$ är en svag inlärare som tar ett objekt $x$ som indata och returnerar ett värde som anger objektets klass. Till exempel, i tvåklassproblemet identifierar tecknet för den svaga inlärarens resultat den förutsagda objektklassen och det absoluta värdet ger förtroendet för den klassificeringen. På liknande sätt $t$ -th klassificeraren positiv om provet är i en positiv klass och negativt annars.

Varje svag elev producerar en utmatningshypotes $h$ som fixar en förutsägelse $h(x_{i})$ för varje prov i träningsuppsättningen. Vid varje iteration $t$ väljs en svag elev och tilldelas en koefficient $\alpha _{t}$ så att det totala träningsfelet $E_{t}$ för den resulterande $t$ -stegsförstärkt klassificerare minimeras.

$E_{t}=\summa _{i}E[F_{t-1}(x_{i })+\alpha _{t}h(x_{i})]$

Här är $F_{t-1}(x)$ den förstärkta klassificeraren som har byggts upp till det föregående träningsstadiet och ${ \displaystyle f_{t}(x)=\alpha _{t}h(x)}$ är den svaga eleven som övervägs för tillägg till den slutliga klassificeraren.

Viktning

Vid varje iteration av träningsprocessen tilldelas en vikt $w_{i,t}$ till varje prov i träningsuppsättningen lika med det aktuella felet ${ \displaystyle E(F_{t-1}(x_{i}))}$ på det provet. Dessa vikter kan användas i träningen av den svaga eleven. Till exempel kan beslutsträd odlas som gynnar uppdelningen av uppsättningar av prover med stora vikter.

Härledning

Denna härledning följer Rojas (2009):

Anta att vi har en datamängd $\{(x_{1},y_{1}),\ldots ,(x_{N} ,y_{N})\}$ där varje objekt $x_{i}$ har en tillhörande klass $y_{i}\in \{-1,1 \}$ , och en uppsättning svaga klassificerare $\{k_{1},\ldots ,k_{L}\}$ som var och en ger en klassificering $k_{j}(x_{i})\in \{-1,1\}$ för varje objekt. Efter $(m-1)$ -te iterationen är vår förstärkta klassificerare en linjär kombination av formens svaga klassificerare:

$C_{(m-1)}(x_{i} )=\alpha _{1}k_{1}(x_{i})+\cdots +\alpha _{m-1}k_{m-1}(x_{i})$ ,

där klassen kommer att vara tecknet för $C_{(m-1)}(x_{i})$ . Vid $m$ -te iterationen vill vi utöka detta till en bättre förstärkt klassificerare genom att lägga till ytterligare en svag klassificerare ${\displaystyle k_{m}} ,$ med en annan vikt $\alpha _{m }$ :

$C_{m}(x_{i})=C_{(m-1)}(x_ {i})+\alpha _{m}k_{m}(x_{i})$

Så det återstår att bestämma vilken svag klassificerare som är det bästa valet för ${\displaystyle k_{m}} ,$ och vad dess vikt $\alpha _{m}$ ska vara. Vi definierar det totala felet $E$ av $C_{m}$ som summan av dess exponentiella förlust på varje datapunkt, givet enligt följande:

${ \displaystyle E=\sum _{i=1}^{N}e^{-y_{i}C_{m}(x_{i})}=\summa _{i=1}^{N}e^ {-y_{i}C_{(m-1)}(x_{i})}e^{-y_{i}\alpha _{m}k_{m}(x_{i})}}$

Låter $w_{i}^{(1)}=1$ och $w_{i} ^{(m)}=e^{-y_{i}C_{m-1}(x_{i})}$ för $m>1$ har vi:

$E=\sum _{i=1}^{N}w_{i}^{(m) }e^{-y_{i}\alpha _{m}k_{m}(x_{i})}$

Vi kan dela denna summering mellan de datapunkter som är korrekt klassificerade av $k_{m}$ (så $y_{i}k_{m}(x_{ i})=1$ ) och de som är felklassificerade (så $y_{i}k_{m}(x_{i})=-1$ ):

$E=\summa _{y_ {i}=k_{m}(x_{i})}w_{i}^{(m)}e^{-\alpha _{m}}+\summa _{y_{i}\neq k_{m }(x_{i})}w_{i}^{(m)}e^{\alpha _{m}}$

$=\sum _{i=1}^{N}w_{i}^{(m)}e^{- \alpha _{m}}+\summa _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}(e^{\alpha _{m}} -e^{-\alpha _{m}})$

Eftersom den enda delen av den högra sidan av denna ekvation som beror på $k_{m}$ är ${\displaystyle \sum _{y_ {i}\neq k_{m}(x_{i})}w_{i}^{(m)}} ,$ vi ser att k $\displaystyle k_{m}}$ som minimerar $E$ är den som minimerar $\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{ (m)}$ [förutsatt att $\alpha _{m}>0$ ], dvs den svaga klassificeraren med det lägsta viktade felet (med vikter ${\displaystyle w_{i}^{(m)}=e^{-y_{i}C_{m-1}(x_{i})}})$ .

För att bestämma den önskade vikten $\alpha _{m}$ som minimerar $E$ med $k_{m}$ som vi just bestämde, skiljer vi:

${\frac {dE}{d\alpha _{m}}}={\frac {d(\sum _{y_{i}=k_{m}(x_{i})}w_{i} ^{(m)}e^{-\alpha _{m}}+\summa _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}e ^{\alpha _{m}})}{d\alpha _{m}}}$

Att sätta detta till noll och lösa för $\alpha _{m}$ ger:

$\alpha _{m}={ \frac {1}{2}}\ln \left({\frac {\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}}{ \sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}}\right)$

Bevis

${\frac {dE}{d\alpha _{m}}}=-\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}e^ {-\alpha _{m}}+\summa _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}e^{\alpha _{m} }=0$

eftersom $e^{-\alpha _{m}}$ inte beror på $i$

$e^{-\alpha _{m }}\summa _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}=e^{\alpha _{m}}\summa _{y_{i }\neq k_{m}(x_{i})}w_{i}^{(m)}$

$-\alpha _{m}+\log \left(\sum _{y_{i}=k_{m} (x_{i})}w_{i}^{(m)}\right)=\alpha _{m}+\log \left(\summa _{y_{i}\neq k_{m}(x_{ i})}w_{i}^{(m)}\höger)$

$-2\alpha _{m}=\log \left({\dfrac {\sum _{y_{i}\neq k_{m}(x_{i})}w_ {i}^{(m)}}{\summa _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}}}\right)$

$\alpha _{m}=-{\ dfrac {1}{2}}\log \left({\dfrac {\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}{ \sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}}}\right)$

$\alpha _{m}={\dfrac {1}{2}}\log \left( {\dfrac {\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}}{\sum _{y_{i}\neq k_{m} (x_{i})}w_{i}^{(m)}}}\right)$

Vi beräknar den viktade felfrekvensen för den svaga klassificeraren till $\epsilon _{m} =\summa _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}/\summa _{i=1}^{N}w_{i}^ {(m)}$ , så det följer att:

$\alpha _{m}={\frac {1}{2}}\ln \left({\frac {1-\epsilon _{ m}}{\epsilon _{m}}}\right)$

vilket är den negativa logitfunktionen multiplicerad med 0,5. På grund av konvexiteten hos $E$ som en funktion av ${\displaystyle \alpha _{m}} , ger$ detta nya uttryck för $\alpha _{m}$ det globala minimum av förlustfunktion.

Obs: Denna härledning gäller endast när ${\displaystyle k_{m}(x_{i})\in \{-1,1\}} ,$ även om det kan vara en bra startgissning i andra fall, som när den svaga eleven är partisk ( $k_{m}(x)\i \{a,b\ },a\neq -b$ ), har flera blad ( $k_{m}(x)\i \{a,b,\dots , n\}$ ) eller är någon annan funktion $k_{m}(x)\in \mathbb {R}$ .

Således har vi härlett AdaBoost-algoritmen: Vid varje iteration, välj klassificeraren $k_{m}$ , vilket minimerar det totala viktade felet ${\displaystyle \sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}} , använd detta för att beräkna$ felfrekvensen ${\displaystyle \epsilon _{m}=\summa _{y_{i}\neq k_{m}(x_{i})} w_{i}^{(m)}/\sum _{i=1}^{N}w_{i}^{(m)}} , använd detta för att beräkna$ vikten $\alpha _{m}={\frac {1}{2}}\ln \left({\frac {1-\epsilon _{m}}{\epsilon _{m }}}\right)$ , och använd slutligen detta för att förbättra den förstärkta klassificeraren $C_{m-1}$ till $C_ {m}=C_{(m-1)}+\alpha _{m}k_{m}$ .

Statistisk förståelse av boosting

Boostning är en form av linjär regression där funktionerna i varje prov $x_{i}$ är utdata från någon svag elev $h$ applicerad på $x_{i}$ .

Medan regression försöker anpassa $F(x)$ till $y(x)$ så exakt som möjligt utan förlust av generalisering, vanligtvis med minsta kvadratfel $E(f)=(y(x)-f(x))^{2}$ , medan AdaBoost-felfunktionen $E(f)=e^{-y(x)f(x)}$ tar hänsyn till att endast tecknet för slutresultatet används, alltså $|F(x)|$ kan vara mycket större än 1 utan ökande fel. Den exponentiella ökningen av felet för prov $x_{i}$ som $-y(x_{i})f(x_{i})$ ökar. vilket resulterar i att överdrivna vikter tilldelas extremvärden.

En egenskap hos valet av exponentiell felfunktion är att felet i den slutliga additivmodellen är produkten av felet för varje steg, det vill säga $e^{\sum _{i}-y_{i}f(x_{i})}=\prod _{i}e^{-y_{i}f(x_{i} )}$ . Således kan det ses att viktuppdateringen i AdaBoost-algoritmen är likvärdig med omräkning av felet på $F_{t}(x)$ efter varje steg.

Det tillåts mycket flexibilitet i valet av förlustfunktion. Så länge förlustfunktionen är monoton och kontinuerligt differentierbar , drivs klassificeraren alltid mot renare lösningar. Zhang (2004) tillhandahåller en förlustfunktion baserad på minsta kvadrater, en modifierad Huberförlustfunktion :

$\phi (y,f(x))={\begin{cases}-4yf(x)&{\mbox{if }}yf(x)<-1,\ \(yf(x)-1)^{2}&{\mbox{if }}-1\leq yf(x)\leq 1.\\0&{\mbox{if }}yf(x)>1\ slut{cases}}$

Denna funktion är mer väluppfostrad än LogitBoost för $f(x)$ nära 1 eller -1, straffar inte "översäkra" förutsägelser ( $yf(x) )>1$ ), till skillnad från omodifierade minsta kvadrater, och straffar endast prover som är felklassificerade med konfidens större än 1 linjärt, i motsats till kvadratiskt eller exponentiellt, och är därför mindre mottagliga för effekterna av extremvärden.

Förstärkning som gradientnedstigning

Huvudartikel: Gradientförstärkning

Boostning kan ses som minimering av en konvex förlustfunktion över en konvex uppsättning funktioner. Specifikt är förlusten som minimeras av AdaBoost den exponentiella förlusten

$\sum _{i}\phi (i,y,f)=\sum _{i}e^{ -y_{i}f(x_{i})}$ ,

medan LogitBoost utför logistisk regression, vilket minimerar

$\sum _{i}\phi (i,y,f)=\summa _ {i}\ln \left(1+e^{-y_{i}f(x_{i})}\right)$ .

I gradient descent-analogin betraktas utsignalen från klassificeraren för varje träningspunkt som en punkt $\left(F_{t}(x_{1) }),\dots ,F_{t}(x_{n})\right)$ i n-dimensionellt utrymme, där varje axel motsvarar ett träningsprov, varje svag elev $h(x)$ motsvarar en vektor med fast orientering och längd, och målet är att nå målpunkten $(y_{1},\dots ,y_{n})$ (eller någon region där värdet på förlustfunktionen $E_{T}(x_{1},\dots ,x_{n})$ är mindre än värdet vid den punkten), i de minsta stegen. Således utför AdaBoost-algoritmer antingen Cauchy (hitta $h(x)$ med den brantaste gradienten, välj $\alpha$ för att minimera testfel) eller Newton (välj någon målpunkt, hitta $\alpha h(x)$ som bringar $F_{t}$ närmast den punkten) optimering av träningsfel.

Exempelalgoritm (Discrete AdaBoost)

Med:

• Exempel $x_{1}\dots x_{n}$
• Önskade utgångar $y_{1}\dots y_{n},y\in \{-1,1\}$
• Initialvikter $w_{1,1}\dots w_{n,1}$ satt till ${\frac {1}{n}}$
• Felfunktion $E(f(x),y,i)=e^{-y_{i}f(x_{ i})}$
• Svaga elever $h\colon x\rightarrow \{-1,1\}$

För $t$ i $1\dots T$ :

• Välj $h_{t}(x)$ :
  • Hitta svag elev $h_{t}(x)$ som minimerar $\epsilon _{t}$ , det viktade summafelet för felklassificerade punkter $\epsilon _{t}=\summa _{\stackrel {i=1}{h_{t}(x_{i})\neq y_{i} }}^{n}w_{i,t}$
  • Välj $\alpha _{t}={\frac {1}{2}}\ln \left({\frac {1-\epsilon _ {t}}{\epsilon _{t}}}\right)$
• Lägg till i ensemblen:
  • $F_{t}(x)=F_{t-1}(x)+\alpha _{ t}h_{t}(x)$
• Uppdatera vikter:
  • $w_{i,t+1}=w_{i,t}e^{-y_{i}\ alfa _{t}h_{t}(x_{i})}$ för $i$ i $1\dots n$
  • Renormalisera $w_{i,t+1}$ så att $\sum _{i}w_{i,t+1}=1$
  • (Notera: Det kan visas att ${\frac {\sum _{h_{t+1}(x_{i})=y_{i }}w_{i,t+1}}{\sum _{h_{t+1}(x_{i})\neq y_{i}}w_{i,t+1}}}={\frac { \summa _{h_{t}(x_{i})=y_{i}}w_{i,t}}{\summa _{h_{t}(x_{i})\neq y_{i}}w_ {i,t}}}$ vid varje steg, vilket kan förenkla beräkningen av de nya vikterna.)

Varianter

Äkta AdaBoost

Utdata från beslutsträd är en klasssannolikhetsuppskattning $p(x)=P(y=1|x)$ , sannolikheten att $x$ är i positiv klass. Friedman, Hastie och Tibshirani härleder en analytisk minimering för $e^{-y\left(F_{t-1}(x) )+f_{t}(p(x))\right)}$ för vissa fasta $p(x)$ (vanligtvis vald med viktat minsta kvadraters fel):

$f_{t}(x)={\frac {1}{2}}\ln \left({\frac {x}{1 -x}}\right)$ .

I stället för att multiplicera utmatningen från hela trädet med något fast värde, ändras alltså varje lövnod till att mata ut halva logittransformen av dess tidigare värde.

LogitBoost

Huvudartikel: LogitBoost

LogitBoost representerar en tillämpning av etablerade logistiska regressionstekniker till AdaBoost-metoden. Istället för att minimera felet med avseende på y, väljs svaga elever för att minimera (viktade minsta kvadraters) felet för $f_{t}(x)$ med avseende på

$z_{t}={\frac {y^{*}-p_{t}( x)}{2p_{t}(x)(1-p_{t}(x))}},$

var

$p_{t}(x)={\frac {e^ {F_{t-1}(x)}}{e^{F_{t-1}(x)}+e^{-F_{t-1}(x)}}},$

$w_{t}=p_{t}(x)(1-p_{t}(x))$

$y^{*}={\frac {y+1}{2}}.$

Det vill säga $z_{t}$ är Newton–Raphson- approximationen av minimeraren av log-sannolikhetsfelet i steg $t$ , och den svaga inläraren $f_{t}$ väljs som den elev som bäst approximerar $z_{t}$ med viktade minsta kvadrater.

När p närmar sig antingen 1 eller 0, värdet av $p_{t}(x_{i})(1-p_{t}(x_{ i}))$ blir mycket liten och z -termen, som är stor för felklassificerade sampel, kan bli numeriskt instabil på grund av maskinprecisionsavrundningsfel. Detta kan övervinnas genom att upprätthålla en viss gräns för det absoluta värdet av z och minimivärdet för w

Mild AdaBoost

Medan tidigare förstärkningsalgoritmer girigt väljer ${\displaystyle f_{t}},$ vilket minimerar det övergripande testfelet så mycket som möjligt vid varje steg, har GentleBoost en begränsad stegstorlek. $f_{t}$ är vald för att minimera $\sum _{i}w_{t,i}(y_{ i}-f_{t}(x_{i}))^{2}$ , och ingen ytterligare koefficient tillämpas. Således, i fallet där en svag elev uppvisar perfekt klassificeringsprestanda, väljer GentleBoost $f_{t}(x)=\alpha _{t}h_{t} (x)$ exakt lika med $y$ , medan de brantaste nedstigningsalgoritmerna försöker sätta $\alpha _{t}=\infty$ . Empiriska observationer om GentleBoosts goda prestanda tycks stödja Schapire och Singers anmärkning om att att tillåta för stora värden på $\alpha$ kan leda till dålig generaliseringsprestanda.

Tidig uppsägning

En teknik för att påskynda bearbetningen av förstärkta klassificerare, tidig avslutning avser att endast testa varje potentiellt objekt med så många lager av den slutliga klassificeraren som krävs för att möta ett visst konfidensgränsvärde, vilket påskyndar beräkningen för fall där objektets klass lätt kan bestämmas. Ett sådant schema är ramverket för objektdetektering som introducerats av Viola och Jones: i en applikation med betydligt fler negativa prov än positiva tränas en kaskad av separata boostklassificerare, varvid utsignalen från varje steg är förspänd så att en acceptabel liten del av positiva prover är felmärkt som negativt, och alla prover markerade som negativa efter varje steg kasseras. Om 50 % av negativa prover filtreras bort vid varje steg, skulle endast ett mycket litet antal objekt passera genom hela klassificeraren, vilket minskar beräkningsansträngningen. Denna metod har sedan dess generaliserats, med en formel tillhandahållen för att välja optimala trösklar i varje steg för att uppnå en viss önskad falsk positiv och falsk negativ frekvens.

Inom statistikområdet, där AdaBoost är mer vanligt förekommande på problem med måttlig dimensionalitet, används tidig stopp som en strategi för att minska överanpassning . En valideringsuppsättning prover separeras från träningsuppsättningen, klassificerarens prestanda på proven som används för träning jämförs med prestanda på valideringsproverna och träningen avslutas om prestandan på valideringsprovet ses minska även när prestanda på träningsuppsättningen fortsätter att förbättras.

Helt korrigerande algoritmer

För de brantaste nedstigningsversionerna av AdaBoost, där $\alpha _{t}$ väljs vid varje lager t för att minimera testfel, sägs nästa lager som läggs vara maximalt oberoende av lager t : det är osannolikt att välja en svag inlärare t+1 som liknar inlärare t . Emellertid kvarstår möjligheten att t+1 producerar liknande information som något annat tidigare lager. Helt korrigerande algoritmer, såsom LPBoost , optimerar värdet av varje koefficient efter varje steg, så att nya lager som läggs alltid är maximalt oberoende av varje tidigare lager. Detta kan åstadkommas genom backfitting, linjär programmering eller någon annan metod.

Beskärning

Beskärning är processen att ta bort dåligt presterande svaga klassificerare för att förbättra minnet och kostnaden för exekveringstid för den förstärkta klassificeraren. De enklaste metoderna, som kan vara särskilt effektiva i samband med totalt korrigerande träning, är vikt- eller marginaltrimning: när koefficienten, eller bidraget till det totala testfelet, för någon svag klassificerare faller under en viss tröskel, är den klassificeraren tappade. Margineantu & Dietterich föreslog ett alternativt kriterium för trimning: svaga klassificerare bör väljas så att mångfalden i ensemblen maximeras. Om två svaga elever producerar mycket lika resultat kan effektiviteten förbättras genom att ta bort en av dem och öka koefficienten för den återstående svaga eleven.

Se även

• Bootstrap aggregering
• CoBoosting
• BrownBoost
• Gradientförstärkning
• Multiplikativ viktuppdateringsmetod § AdaBoost-algoritm

Vidare läsning

•   Freund, Yoav; Schapire, Robert E (1997). "En beslutsteoretisk generalisering av on-line-lärande och en tillämpning för att öka". Tidskrift för data- och systemvetenskap . 55 : 119–139. CiteSeerX 10.1.1.32.8918 . doi : 10.1006/jcss.1997.1504 : originaltidning av Yoav Freund och Robert E. Schapire där AdaBoost introduceras först.
• Zhou, Zhihua (2008). "På marginalen förklaring av ökande algoritm" (PDF) . I: Proceedings of the 21st Annual Conference on Learning Theory (COLT'08) : 479–490. På marginalen förklaring av ökande algoritm.
•   Zhou, Zhihua (2013). "Om tvivel om marginalförklaring av förstärkning" (PDF) . Artificiell intelligens . 203 (2013): 1–18. arXiv : 1009.3613 . Bibcode : 2010arXiv1009.3613G . doi : 10.1016/j.artint.2013.07.002 . S2CID 2828847 . På tvivel om marginalförklaring av förstärkning.