Gradientförstärkning

Gradientförstärkning är en maskininlärningsteknik som används i bland annat regressions- och klassificeringsuppgifter . Det ger en prediktionsmodell i form av en ensemble av svaga prediktionsmodeller, som vanligtvis är beslutsträd . När ett beslutsträd är den svaga inläraren kallas den resulterande algoritmen för gradientförstärkta träd; den överträffar vanligtvis slumpmässig skog . En gradientförstärkt trädmodell är byggd på ett stegvis sätt som i andra förstärkningsmetoder , men den generaliserar de andra metoderna genom att tillåta optimering av en godtycklig differentierbar förlustfunktion .

Historia

Leo Breimans observation att förstärkning kan tolkas som en optimeringsalgoritm på en lämplig kostnadsfunktion. Explicita regressionsgradientförstärkande algoritmer utvecklades därefter av Jerome H. Friedman , samtidigt med Llew Masons, Jonathan Baxter, Peter Bartlett och Marcus Freans mer allmänna funktionella gradientförstärkningsperspektiv. De två sistnämnda artiklarna introducerade synen på förstärkande algoritmer som iterativa algoritmer för gradientnedstigning . Det vill säga algoritmer som optimerar en kostnadsfunktion över funktionsutrymme genom att iterativt välja en funktion (svag hypotes) som pekar i negativ gradientriktning. Denna funktionella gradientvy av förstärkning har lett till utvecklingen av förstärkningsalgoritmer inom många områden av maskininlärning och statistik bortom regression och klassificering.

Informell introduktion

(Det här avsnittet följer beskrivningen av gradientförstärkning av Cheng.)

Liksom andra förstärkningsmetoder kombinerar gradientförstärkning svaga "lärare" till en enda stark inlärare på ett iterativt sätt. Det är lättast att förklara i minsta kvadraters regression , där målet är att "lära" en modell $F$ att förutsäga värden av formen ${\hat {y }}=F(x)$ genom att minimera medelkvadratfelet ${\tfrac {1}{n}}\sum _{i}({\hat {y}}_{i}-y_{i})^{2}$ , där $i$ indexerar över någon träningsuppsättning av storlek $n$ av faktiska värden för utdatavariabeln ${\ displaystil y}$ :

• ${\hat {y}}_{i}=$ det förutsagda värdet $F(x_{i})$
• $y_{i}=$ det observerade värdet
• $n=$ antalet sampel i $y$

Låt oss nu överväga en gradientförstärkningsalgoritm med $M$ -steg. Vid varje steg $m$ ( $1\leq m\leq M$ ) av gradientförstärkning, anta att någon imperfekt modell $F_{m}$ (för låg ${ \displaystyle m}$ , denna modell kan helt enkelt returnera ${\displaystyle {\hat {y}}_{i}={\bar {y}}} ,$ där RHS är medelvärdet av ${\ displaystil y}$ ). För att förbättra $F_{m}$ bör vår algoritm lägga till någon ny estimator, $h_{m}(x)$ . Således,

$F_{m+1}(x_{i})=F_{m}(x_{i} )+h_{m}(x_{i})=y_{i}$

eller på motsvarande sätt

$h_{m}(x_{i})=y_{i}-F_{m}(x_{i})$ .

Därför kommer gradientförstärkning att passa $h_{m}$ till restvärdet $y_{i}-F_{m}(x_{i})$ . Liksom i andra förstärkningsvarianter försöker varje $F_{m+1}$ att korrigera felen i sin föregångare $F_{m}$ . En generalisering av denna idé till förlustfunktioner än kvadratfel, och till klassificerings- och rangordningsproblem , följer av observationen att residualer $h_{m}(x_{i})$ för en given modell är proportionella mot de negativa gradienterna för förlustfunktionen för medelkvadratfel (MSE) (med avseende på ${\displaystyle F(x_{i})} )$ :

$L_{\rm {MSE}}={\frac {1}{n}}\summa _{i =1}^{n}\left(y_{i}-F(x_{i})\right)^{2}$

$-{\frac {\partial L_{\rm {MSE}}}{\partial F(x_{i})}}={\frac { 2}{n}}(y_{i}-F(x_{i}))={\frac {2}{n}}h_{m}(x_{i})$ .

Så, gradientförstärkning kan specialiseras till en gradientnedstigningsalgoritm , och att generalisera den innebär att "plugga in" en annan förlust och dess gradient.

Algoritm

I många övervakade inlärningsproblem finns det en utdatavariabel y och en vektor av ingångsvariabler x , relaterade till varandra med en viss probabilistisk fördelning. Målet är att hitta någon funktion ${\hat {F}}(x)$ som bäst approximerar utdatavariabeln från värdena för indatavariabler. Detta formaliseras genom att införa någon förlustfunktion $L(y,F(x))$ och minimera den i förväntan:

${\hat {F}}={\underset {F}{\arg \min }}\,\mathbb {E} _{x,y}[L(y,F(x))]$ .

Gradientförstärkningsmetoden antar ett verkligt värde y . Den söker en approximation ${\hat {F}}(x)$ i form av en viktad summa av M funktioner $h_{m}(x)$ från några klass ${\mathcal {H}}$ , kallade bas- (eller svaga ) elever:

${\hat {F}}(x)=\summa _{m=1}^{M}\gamma _{ m}h_{m}(x)+{\mbox{const}}$ .

Vi får vanligtvis en träningsuppsättning $\{(x_{1},y_{1}),\dots ,(x_{n },y_{n})\}$ av kända exempelvärden för x och motsvarande värden för y . I enlighet med den empiriska riskminimeringsprincipen försöker metoden hitta en approximation ${\hat {F}}(x)$ som minimerar medelvärdet av förlustfunktionen på träningssetet, dvs. , minimerar den empiriska risken. Det gör det genom att börja med en modell, som består av en konstant funktion ${\displaystyle F_{0}(x)} ,$ och expanderar den stegvis på ett girigt sätt:

$F_{0}(x)={\underset {\gamma }{\arg \min }}{\sum _ {i=1}^{n}{L(y_{i},\gamma )}}$ ,

$F_{m}(x)=F_{m-1}(x) )+\left({\underset {h_{m}\in {\mathcal {H}}}{\operatörsnamn {arg\,min} }}\left[{\sum _{i=1}^{n} {L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}}\höger]\höger)(x)$ ,

för $m\geq 1$ , där $h_{m}\in {\mathcal {H}}$ är en basinlärarfunktion.

Att välja den bästa funktionen $h_{m}$ i varje steg för en godtycklig förlustfunktion L är tyvärr ett beräkningsmässigt omöjligt optimeringsproblem i allmänhet. Därför begränsar vi vårt tillvägagångssätt till en förenklad version av problemet.

Tanken är att tillämpa ett brantaste nedstigningssteg på detta minimeringsproblem (funktionell gradientnedstigning).

Grundidén bakom den brantaste nedstigningen är att hitta ett lokalt minimum av förlustfunktionen genom att iterera på $F_{m-1}(x)$ . Faktum är att förlustfunktionens lokala maximala sänkningsriktning är den negativa gradienten.

Flytta därför en liten mängd $\gamma$ så att den linjära approximationen förblir giltig:

$F_{m}(x)= F_{m-1}(x)-\gamma \sum _{i=1}^{n}{\nabla _{F_{m-1}}L(y_{i},F_{m-1}( x_{i}))}$

där $\gamma >0$ . För små $\gamma$ , innebär detta att $L(y_{i}, F_{m}(x_{i}))\leq L(y_{i},F_{m-1}(x_{i}))$ .

Bevis på funktionell form av derivat

För att bevisa följande, överväg målet $O=\summa _{i=1}^{n}{L(y_{ i},F_{m-1}(x_{i})+h_{m}(x_{i}))}$ Göra en Taylor-expansion till första ordningens $O=\sum _{i=1}^{n} {L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}\approx \summa _{i=1}^{n}{L( y_{i},F_{m-1}(x_{i}))+h_{m}(x_{i})\nabla _{F_{m-1}}L(y_{i},F_{m -1}(x_{i}))}+\ldots$ Om man nu differentierar med $h_{m}(x_{i})$ återstår bara derivatan av den andra termen $\nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))$ . Detta är riktningen för den brantaste uppstigningen och därför måste vi röra oss i motsatt (dvs negativ) riktning för att röra oss i riktningen för den brantaste nedstigningen.

Dessutom kan vi optimera $\gamma$ genom att hitta värdet $\gamma$ för vilket förlustfunktionen har ett minimum:

$\gamma _{m}={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L(y_{i},F_{m}( x_{i}))}}={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L\left(y_{i},F_{m- 1}(x_{i})-\gamma \nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))\right)}}.$

Om vi ​​betraktade det kontinuerliga fallet, dvs där ${\mathcal {H}}$ är uppsättningen av godtyckliga differentierbara funktioner på $\mathbb {R}$ , skulle vi uppdatera modellen i enlighet med följande ekvationer

$F_{m}(x) =F_{m-1}(x)-\gamma _{m}\summa _{i=1}^{n}{\nabla _{F_{m-1}}L(y_{i},F_{ m-1}(x_{i}))}$

där $\gamma _{m}$ är steglängden, definierad som

$$\gamma _{m}={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L\left(y_{i},F_{m -1}(x_{i})-\gamma \nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))\right)}}.$$

I det diskreta fallet dock, dvs när mängden ${\mathcal {H}}$ är finit, väljer vi kandidatfunktionen h närmast gradienten av L för vilken koefficienten γ sedan kan beräknas med hjälp av linjesökning på ovanstående ekvationer. Observera att detta tillvägagångssätt är en heuristik och därför inte ger en exakt lösning på det givna problemet, utan snarare en approximation. I pseudokod är den generiska gradientförstärkningsmetoden:

Indata: träningsuppsättning ${\displaystyle \{(x_{i},y_{i})\}_{i=1}^{n},} en$ differentierbar förlustfunktion $L(y,F(x)),$ antal iterationer M .

Algoritm:

1. Initiera modellen med ett konstant värde:

   $F_{0}(x)={\underset {\gamma }{\arg \min }}\summa _{i=1}^{n}L(y_{i},\gamma ).$

2. För m = 1 till M :
   1. Beräkna så kallade pseudo-rester :

      $r_{im}=-\left[{\frac {\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})}}\right]_ {F(x)=F_{m-1}(x)}\quad {\mbox{for }}i=1,\ldots ,n.$

   2. Anpassa en basinlärare (eller svag inlärare, t.ex. träd) stängd under skalning $h_{m}(x)$ till pseudo-rester, dvs träna den med träningsuppsättningen $\{(x_{i},r_{im})\}_{i=1}^{n}$ .
   3. Beräkna multiplikatorn $\gamma _{m}$ genom att lösa följande endimensionella optimeringsproblem :

      $\gamma _{m}={\underset {\gamma }{\operatörsnamn {arg\,min} }}\summa _{i=1}^{n}L\left(y_{i},F_ {m-1}(x_{i})+\gamma h_{m}(x_{i})\höger).$

   4. Uppdatera modellen:

      $F_{m}(x)=F_{m-1}(x)+\gamma _{m}h_{m}(x).$

3. Utgång $F_{M}(x).$

Gradient trädförstärkning

Gradientförstärkning används vanligtvis med beslutsträd (särskilt CARTs ) av en fast storlek som basinlärare. För detta speciella fall föreslår Friedman en modifiering av gradientförstärkningsmetoden som förbättrar passformen för varje basinlärare.

Generisk gradientförstärkning vid det m -:te steget skulle passa ett beslutsträd $h_{m}(x)$ till pseudo-rester. Låt $J_{m}$ vara antalet av dess blad. Trädet delar upp inmatningsutrymmet i $J_{m}$ disjunkta regioner $R_{1m},\ldots ,R_{J_{m}m}$ och förutspår ett konstant värde i varje region. Med hjälp av indikatornotationen kan utmatningen av $h_{m}(x)$ för input x skrivas som summan:

$h_{m}(x)=\summa _{j=1}^{J_{m}}b_ {jm}\mathbf {1} _{R_{jm}}(x),$

där $b_{jm}$ är värdet som förutspås i regionen $R_{jm}$ .

multipliceras koefficienterna ${\displaystyle b_{jm}} med något värde$${\displaystyle \gamma _{m}} ,$ vald med hjälp av radsökning för att minimera förlustfunktionen, och modellen uppdateras som följer:

$F_{m}(x)=F_{m-1}(x)+\gamma _{m}h_{m}(x),\quad \gamma _{m}={\underset {\gamma }{\operatörsnamn {arg\,min} }}\sum _{i=1}^{n}L(y_{i},F_{m-1}(x_{i})+\gamma h_{m} (x_{i})).$

Friedman föreslår att denna algoritm ska modifieras så att den väljer ett separat optimalt värde $\gamma _{jm}$ för var och en av trädets regioner, istället för en enda $\gamma _{m}$ för hela trädet. Han kallar den modifierade algoritmen för "TreeBoost". Koefficienterna $b_{jm}$ från trädanpassningsproceduren kan sedan helt enkelt kasseras och modelluppdateringsregeln blir:

$F_{m}(x)=F_{m-1}(x)+\summa _{j=1}^{J_{m}}\gamma _{jm}\mathbf {1} _{R_ {jm}}(x),\quad \gamma _{jm}={\underset {\gamma }{\operatörsnamn {arg\,min} }}\summa _{x_{i}\in R_{jm}} L(y_{i},F_{m-1}(x_{i})+\gamma ).$

Storlek på träd

$J$ , antalet terminalnoder i träd, är metodens parameter som kan justeras för en datauppsättning till hands. Den styr den maximalt tillåtna nivån av interaktion mellan variabler i modellen. Med $J=2$ ( beslutsstumpar ) tillåts ingen interaktion mellan variabler. Med $J=3$ kan modellen inkludera effekter av interaktionen mellan upp till två variabler, och så vidare.

Hastie et al. kommentera att typiskt $4\leq J\leq 8$ fungerar bra för att öka och resultaten är ganska okänsliga för valet av $J$ i detta intervall, $J= 2$ är otillräckligt för många applikationer, och $J>10$ kommer sannolikt inte att krävas.

Regularisering

Att anpassa träningsuppsättningen för nära kan leda till försämring av modellens generaliseringsförmåga. Flera så kallade regulariseringstekniker minskar denna överanpassningseffekt genom att begränsa anpassningsproceduren.

En naturlig regulariseringsparameter är antalet gradientförstärkande iterationer M (dvs antalet träd i modellen när basinläraren är ett beslutsträd). Att öka M minskar felet på träningssetet, men om man ställer in det för högt kan det leda till överanpassning. Ett optimalt värde på M väljs ofta genom att övervaka prediktionsfel på en separat valideringsdatauppsättning. Förutom att kontrollera M , används flera andra regleringstekniker.

En annan regleringsparameter är trädens djup. Ju högre detta värde är desto mer sannolikt kommer modellen att överpassa träningsdatan.

Krympning

En viktig del av metoden för gradientförstärkning är regularisering genom krympning som består i att modifiera uppdateringsregeln enligt följande:

$F_{m}(x)=F_{m-1}(x)+ \nu \cdot \gamma _{m}h_{m}(x),\quad 0<\nu \leq 1,$

där parametern $\nu$ kallas "inlärningshastigheten".

Empiriskt har det visat sig att användning av små inlärningshastigheter (som $\nu <0.1$ ) ger dramatiska förbättringar i modellers generaliseringsförmåga över gradientförstärkning utan att krympa ( $\nu =1$ ). Det kommer dock till priset av ökad beräkningstid både under utbildning och förfrågning : lägre inlärningshastighet kräver fler iterationer.

Stokastisk gradientförstärkning

föreslog Friedman en mindre modifiering av algoritmen, motiverad av Breimans bootstrap-aggregation ("bagging")-metod. Specifikt föreslog han att en basinlärare vid varje iteration av algoritmen skulle passa på ett delprov av träningsuppsättningen som dragits slumpmässigt utan ersättning. Friedman observerade en avsevärd förbättring av gradientförstärkningens noggrannhet med denna modifiering.

Delprovstorlek är en konstant bråkdel $f$ av storleken på träningsuppsättningen. När $f=1$ är algoritmen deterministisk och identisk med den som beskrivs ovan. Mindre värden på $f$ introducerar slumpmässighet i algoritmen och hjälper till att förhindra överanpassning , vilket fungerar som en slags regularisering . Algoritmen blir också snabbare, eftersom regressionsträd måste anpassas till mindre datamängder vid varje iteration. Friedman fick fram att $0,5\leq f\leq 0,8$ leder till bra resultat för små och medelstora träningsuppsättningar. Därför $f$ vanligtvis satt till 0,5, vilket betyder att hälften av träningsuppsättningen används för att bygga upp varje basinlärare.

Liksom vid packning tillåter subsampling en att definiera ett out-of-bag-fel för förbättringen av prediktionsprestanda genom att utvärdera förutsägelser på de observationer som inte användes i byggnaden av nästa basinlärare. Out-of-bag-uppskattningar hjälper till att undvika behovet av en oberoende valideringsdatauppsättning, men underskattar ofta faktisk prestandaförbättring och det optimala antalet iterationer.

Antal observationer i blad

Implementeringar för ökning av gradientträd använder ofta också regularisering genom att begränsa det minsta antalet observationer i trädens terminalnoder. Det används i trädbyggeprocessen genom att ignorera eventuella uppdelningar som leder till noder som innehåller färre än detta antal träningsuppsättningsinstanser.

Att införa denna gräns hjälper till att minska variansen i förutsägelser vid bladen.

Bestraffa trädets komplexitet

En annan användbar regulariseringsteknik för gradientförstärkta träd är att straffa den inlärda modellens modellkomplexitet. Modellens komplexitet kan definieras som det proportionella antalet löv i de inlärda träden. Den gemensamma optimeringen av förlust och modellkomplexitet motsvarar en efterbeskärningsalgoritm för att ta bort grenar som inte lyckas minska förlusten med en tröskel. Andra typer av regularisering som $\ell _{2}$ straff på bladvärdena kan också läggas till för att undvika överanpassning .

Användande

Gradientförstärkning kan användas inom området för att lära sig rangordna . De kommersiella webbsökmotorerna Yahoo och Yandex använder varianter av gradientförstärkning i sina maskininlärda rankningsmotorer. Gradientförstärkning används också i högenergifysik i dataanalys. Vid Large Hadron Collider (LHC) lyckades varianter av gradientförstärkande Deep Neural Networks (DNN) reproducera resultaten av icke-maskininlärningsmetoder för analys på datamängder som användes för att upptäcka Higgs- bosonen . Gradientförstärkande beslutsträd användes också i jord- och geologiska studier – till exempel kvalitetsutvärdering av sandstensreservoar.

Namn

Metoden går under en mängd olika namn. Friedman introducerade sin regressionsteknik som en "Gradient Boosting Machine" (GBM). Mason, Baxter et al. beskrev den generaliserade abstrakta klassen av algoritmer som "funktionell gradientförstärkning". Friedman et al. beskriva en utveckling av gradientförstärkta modeller som Multiple Additive Regression Trees (MART); Elith et al. beskriv det tillvägagångssättet som "Boostade Regression Trees" (BRT).

En populär implementering med öppen källkod för R kallar det en "Generalized Boosting Model", men paket som utökar detta arbete använder BRT. Ännu ett namn är TreeNet, efter en tidig kommersiell implementering från Salford Systems Dan Steinberg, en av forskare som banade väg för användningen av trädbaserade metoder. XGBoost är en annan populär modern implementering av metoden med vissa tillägg, som andra ordningens optimering.

Nackdelar

Även om boosting kan öka noggrannheten hos en basinlärare, såsom ett beslutsträd eller linjär regression, offrar det förståelighet och tolkningsbarhet . Till exempel är det trivialt och självförklarat att följa vägen som ett beslutsträd tar för att fatta sitt beslut, men att följa hundratals eller tusentals träds vägar är mycket svårare. För att uppnå både prestanda och tolkningsbarhet tillåter vissa modellkompressionstekniker att transformera en XGBoost till ett enda "pånyttfödd" beslutsträd som approximerar samma beslutsfunktion. Dessutom kan implementeringen vara svårare på grund av det högre beräkningsbehovet.

Se även

• AdaBoost
• Slumpmässig skog
• Catboost
• LightGBM
• XGBoost
• Beslutsträdsinlärning

Vidare läsning

•   Boehmke, Bradley; Greenwell, Brandon (2019). "Gradient Boosting". Hands-on maskininlärning med R . Chapman & Hall. s. 221–245. ISBN 978-1-138-49568-5 .

externa länkar

• Hur man förklarar gradientförstärkning
• Gradientförstärkta regressionsträd
• LightGBM