Batchgradientnedstigning versus stokastisk gradientnedstigning

Anvendeligheden af batch- eller stokastisk gradientnedstigning afhænger virkelig af den forventede fejlmanifold.

Batchgradientnedstigning beregner gradienten ved hjælp af hele datasættet. Dette er fantastisk til konvekse eller relativt glatte fejlmanifold. I dette tilfælde bevæger vi os noget hat direkte mod en optimal løsning, enten lokal eller global. Derudover vil batchgradientnedstigning, givet en udglødet indlæringshastighed, i sidste ende finde det minimum, der er placeret i dens tiltrækningsbassin.

Stokastisk gradientnedstigning (SGD) beregner gradienten ved hjælp af en enkelt prøve. De fleste anvendelser af SGD bruger faktisk en minibatch med flere prøver af grunde, der vil blive forklaret lidt senere. SGD fungerer godt (ikke godt, antager jeg, men bedre end batchgradientnedstigning) til fejlmanifold, der har masser af lokale maxima / minima. I dette I det tilfælde er den lidt mere støjende gradient beregnet ved hjælp af det reducerede antal prøver tendens til at rykke modellen ud af lokale minima i et område, der forhåbentlig er mere optimalt. Enkeltprøver er virkelig støjende, mens minibatches har en tendens til gennemsnitligt lidt af støj ud. , reduceres mængden af ryk, når man bruger minibatches. En god balance opnås, når minibatchstørrelsen er lille nok til at undgå nogle af de dårlige lokale minima, men stor nok til at den ikke undgår de globale minima eller bedre præstationer ocal minima. (I øvrigt antager dette, at de bedste minima har et større og dybere tiltrækningsbassin og derfor er lettere at falde ind i.)

En fordel ved SGD er, at det beregningsmæssigt er meget hurtigere. Stor datasæt kan ofte ikke holdes i RAM, hvilket gør vektorisering meget mindre effektiv. Snarere skal hver prøve eller batch af prøver indlæses, bearbejdes med, resultaterne gemmes osv. Minibatch SGD er på den anden side normalt bevidst gjort lille nok til at være beregningsmæssigt trækkbar.

Normalt udnyttes denne beregningsfordel ved at udføre mange flere iterationer af SGD, hvilket gør mange flere trin end konventionel batchgradientnedstigning . Dette resulterer normalt i en model, der er meget tæt på den, der findes via batchgradientnedstigning eller bedre.

Den måde, jeg kan lide at tænke på, hvordan SGD fungerer, er at forestille mig, at jeg har et punkt, der repræsenterer min inputfordeling. Min model forsøger at lære den inputfordeling. Omkring inputfordelingen er et skyggefuldt område, der repræsenterer inputfordelingerne for alle de mulige minibatcher, jeg kunne prøve. Det er normalt en rimelig antagelse om, at minibatch-inputfordelingen er tæt på den sande inputfordeling. Batchgradientnedstigning tager i alle trin den stejleste rute for at nå den sande inputfordeling. SGD vælger på den anden side en tilfældigt punkt inden for det skraverede område og tager den stejleste rute mod dette punkt. Ved hver iteration vælger det dog et nyt punkt. Gennemsnittet af alle disse trin vil tilnærme den sande inputfordeling, normalt ganske godt.

Kommentarer

• I praksis bruger ingen Batch Gradient Descent. Det ‘ er simpelthen for beregningsmæssigt dyrt til ikke så meget af en gevinst. (Gevinsten er, at du ‘ faktisk træder ned ” sand ” gradient.) Når du har en meget ikke-konveks tabsfunktion, skal du bare gå i den rigtige retning, og du ‘ vil til sidst konvergere o n et lokalt minimum. Således minibatch SGD.
• @Jason_L_Bens har du nogen reference (papirer eller onlinetekster), hvor jeg kan læse mere om disse algoritmer?
• @ user110320 Ikke over toppen af mit hoved, nej, selvom de ‘ er meget almindelige algoritmer, og derfor bør der være et ton ressourcer til rådighed om emnet med lidt søgning. Hvis du ‘ leder efter en generel tilgang, anbefaler jeg ‘ at læse noget af Yoshua Bengio ‘ s Learning Deep Architectures for AI. Det ‘ hvor jeg kom i gang.

Som andet svar antyder, er hovedårsagen til at bruge SGD at reducere beregningsomkostningerne ved gradient, mens man stadig i vid udstrækning opretholder gradientretningen, når den gennemsnitliggøres over mange mini-batches eller prøver – det hjælper helt sikkert med at bringe dig til de lokale minima.

1. Hvorfor minibatch fungerer .

Matematikken bag dette er at ” true ” omkostningsfunktionens gradient (gradienten for generaliseringsfejlen eller for uendeligt store sæt af prøver) er forventningen af gradienten $ g $ over den ægte datagenererende distribution $ p_ {data} $ ; den aktuelle gradient $ \ hat {g} $ beregnet over en batch af prøver er altid en tilnærmelse til den sande gradient med den empiriske datafordeling $ \ hat {p} _ {data} $ . $$ \ hat {g} = E _ {\ hat {p} _ {data}} ({\ partial J (\ theta) \ over \ partial \ theta}) $$ Batchgradientnedstigning kan give dig den mulige ” optimal ” gradient givet alle dine dataprøver, det er ikke ” sand ” gradient dog. En mindre batch (dvs. en minibatch) er sandsynligvis ikke så optimal som den fulde batch, men de er begge tilnærmelser – det samme er single-sample minibatch (SGD).

Under forudsætning af at der ikke er nogen afhængighed mellem $ m $ prøver i en minibatch, den beregnede $ \ hat {g} (m) $ er en upartisk skøn over den sande gradient. (Kvadratiske) standardfejl i estimaterne med forskellige minibatchstørrelser er omvendt proportional med størrelsen på minibatchen. Det vil sige $$ {SE ({\ hat {g} (n)}) \ over SE ({\ hat {g} (m)})} = {\ sqrt { m \ over n}} $$ Dvs. reduktion af standardfejl er kvadratroden af stigningen i stikprøvestørrelse. Dette betyder, at hvis minibatchstørrelsen er lille, skal læringsgraden også være lille for at opnå stabilitet i forhold til den store variation. Når prøverne ikke er uafhængige, opretholdes ejendommen af upartisk skøn ikke længere. Det kræver, at du blander prøverne inden træningen, hvis prøverne ikke sekventeres tilfældigt nok.

2. Hvorfor minibatch kan være fungere bedre .

For det første gør minibatch nogle indlæringsproblemer fra teknisk umulig at kunne håndteres på grund af det reducerede beregningsbehov med mindre batchstørrelse.

For det andet betyder reduceret batchstørrelse ikke nødvendigvis reduceret gradientnøjagtighed. Uddannelsesprøverne har mange lyde eller afvigelser eller forspændinger. En tilfældigt stikprøvet minibatch kan afspejle den sande data, der genererer distribution bedre (eller ikke dårligere) end den oprindelige fulde batch. Hvis nogle gentagelser af minibatch-gradientopdateringer giver dig et bedre skøn, kan det gennemsnitlige resultat af en periode generelt være bedre end gradienten beregnet ud fra en fuld batch.

For det tredje hjælper minibatch ikke kun med at håndtere ubehagelige dataprøver, men hjælper også med at håndtere ubehagelige omkostningsfunktioner, der har mange lokale minima. Som Jason_L_Bens nævner, kan fejlmanifolden nogle gange være lettere at fange en regelmæssig gradient ind i et lokalt minima, mens det er sværere at fange den midlertidigt tilfældige gradient beregnet med minibatch. nå de globale minima i et trin, men gentage sig på fejlmanifolden. Gradient giver dig stort set kun retningen til at gentage. Med minibatch kan du gentage meget hurtigere. I mange tilfælde, jo flere iterationer, jo bedre punkt kan du nå. Du er ligeglad med noget vejr, punktet er optimalt globalt eller endda lokalt. Du vil bare nå en rimelig model, der giver dig acceptabel generaliseringsfejl. Minibatch gør det lettere.

Du kan finde bogen ” Deep learning ” af Ian Goodfellow, et al, har ret gode diskussioner om dette emne, hvis du læser det grundigt igennem.

Kommentarer

• For konvekse optimeringsproblemer er det, du sagde, fint.Men for at bruge gradientmetoder på ikke-konvekse funktioner savnede du en meget kritisk grund til, at SGD er bedre end batch GD. Se mit svar datascience.stackexchange.com/questions/16807/…
• @horaceT Tak for din kommentar. Da det punkt, du nævnte, er beskrevet af Jason_L_Bens ovenfor med detaljer, gik jeg ikke med at gentage men henviste hans svar i sidste tredje afsnit med behørig respekt. For at optimere problemet med gradientnedstigning reflekteres ikke-konveks af det lokale minima inklusive sadelpunkt (se sidste tredje afsnit); og af hensyn til beskrivelsen beskriver mit svar SGD som minibatch, men med en batchstørrelse på 1 (se tredje afsnit).
• Hvorfor har du sagt næsten i * endelig i en periode, er du næsten computere gennemsnittet af gradienterne baseret på alle de givne prøver. *? Don ‘ t du mener, at dette krav er forkert på grund af opdatering af vægten ved hvert trin?
• @ Media Du har ret. Jeg ‘ har fjernet det sidste afsnit. Tak.

For mig ligner batchgradient lean lean gradient. I lean gradient vælges batchstørrelsen, så alle parametre, der skal opdateres, varieres også uafhængigt, men ikke nødvendigvis ortogonalt, i batchen. For eksempel, hvis batchen indeholder 10 eksperimenter, 10 rækker, er det muligt at danne $ 2 ^ {10-1} = 512 $ uafhængige kolonner. 10 rækker muliggør uafhængig, men ikke ortogonal, opdatering af 512 parametre.