Batch gradient nedstigning versus stokastisk gradient nedstigning

Bruken av batch- eller stokastisk gradientavstengning avhenger egentlig av feilmanifolden som forventes.

Batchgradientnedstigning beregner gradienten ved hjelp av hele datasettet. Dette er flott for konvekse eller relativt glatte feilmanifold. I dette tilfellet beveger vi oss noe hatt direkte mot en optimal løsning, enten lokal eller global. I tillegg vil gradvis nedstigning i batch, gitt en glødet læringsgrad, til slutt finne minimumet som ligger i det tiltrekkingsbassenget.

Stokastisk gradientnedstigning (SGD) beregner gradienten ved hjelp av en enkelt prøve. De fleste applikasjoner av SGD bruker faktisk en minibatch på flere prøver, av grunner som vil bli forklart litt senere. SGD fungerer bra (ikke vel, antar jeg, men bedre enn batch gradient nedstigning) for feilmanifold som har mange lokale maksima / minima. I dette I tilfelle, har den noe mer støyende gradienten beregnet ved hjelp av redusert antall prøver en tendens til å rykke modellen ut av lokale minima til en region som forhåpentligvis er mer optimal. Enkeltprøver er veldig støyende, mens minibatcher har en tendens til å gjennomsnittlig litt av støyen. , reduseres mengden rykk når du bruker minibatcher. En god balanse oppnås når minibatchstørrelsen er liten nok til å unngå noen av de dårlige lokale minimaene, men stor nok til at den ikke unngår de globale minimaene eller bedre ytende l okale minima. (For øvrig antar dette at de beste minimaene har et større og dypere tiltrekningsbasseng, og derfor er lettere å falle i.)

En fordel med SGD er at det beregningsmessig er mye raskere. datasett kan ofte ikke holdes i RAM, noe som gjør vektorisering mye mindre effektiv. Snarere må hver prøve eller gruppe prøver lastes, jobbes med, resultatene lagres og så videre. Minibatch SGD, derimot, blir vanligvis med vilje gjort liten nok til å være beregningsmessig gjennomførbar. . Dette resulterer vanligvis i en modell som er veldig nær den som ville bli funnet via batch gradient nedstigning, eller bedre.

Måten jeg liker å tenke på hvordan SGD fungerer, er å forestille seg at jeg har ett poeng som representerer min innspillfordeling. Min modell prøver å lære den inngangsfordelingen. Rundt inngangsfordelingen er et skyggelagt område som representerer inngangsfordelingene til alle mulige minibatcher jeg kunne prøve. Det er vanligvis en rimelig antagelse om at minibatch-inngangsfordelingen er nær den sanne inngangsfordelingen. Batchgradientnedstigning, i alle trinn, tar den bratteste ruten for å nå den sanne inngangsfordelingen. SGD, derimot, velger en tilfeldig punkt innenfor det skyggelagte området, og tar den bratteste ruten mot dette punktet. Ved hver iterasjon velger det imidlertid et nytt punkt. Gjennomsnittet av alle disse trinnene vil tilnærme seg den sanne inngangsfordelingen, vanligvis ganske bra.

Kommentarer

• I praksis bruker ingen Batch Gradient Descent. Det ‘ er rett og slett for beregningsdyr for ikke så mye (en gevinst er at du ‘ faktisk trapper ned » sant » gradient.) Når du har en svært ikke-konveks tapfunksjon, trenger du bare å gå i mest riktig retning, og du ‘ vil til slutt konvergere o n et lokalt minimum. Dermed minibatch SGD.
• @Jason_L_Bens har du noen referanse (papirer eller elektroniske tekster) der jeg kan lese mer om disse algoritmene?
• @ user110320 Ikke utenfor toppen av hodet mitt, nei, selv om de ‘ er veldig vanlige algoritmer, og det bør derfor være massevis av ressurser tilgjengelig på emnet med litt søk. Hvis du ‘ leter etter en generell tilnærming, anbefaler jeg ‘ å lese noe av Yoshua Bengio ‘ s Learning Deep Architectures for AI. Det var ‘ der jeg kom i gang.

Som andre svar antyder, er hovedårsaken til å bruke SGD å redusere beregningskostnadene for gradient, mens du fremdeles i stor grad opprettholder gradientretningen når den gjennomsnittes over mange mini-batcher eller prøver – noe som helt sikkert hjelper deg med å komme til de lokale minimumene.

1. Hvorfor minibatch fungerer .

Matematikken bak dette er at » true » kostnadsfunksjonen (gradienten for generaliseringsfeilen eller for uendelig store prøvesett) er forventningen av gradienten $ g $ over den sanne datagenererende distribusjonen $ p_ {data} $ ; den faktiske gradienten $ \ hat {g} $ beregnet over en serie prøver er alltid en tilnærming til den sanne gradienten med den empiriske datafordelingen $ \ hat {p} _ {data} $ . $$ \ hat {g} = E _ {\ hat {p} _ {data}} ({\ partial J (\ theta) \ over \ partial \ theta}) $$ Nedgang i batchgradient kan gi deg den mulige » optimal » gradienten gitt alle dataeksemplene dine, det er ikke » true » gradient skjønt. En mindre batch (dvs. en minibatch) er sannsynligvis ikke like optimal som hele batchen, men de er begge tilnærminger – det samme er minipartiet med en prøve (SGD).

Forutsatt at det ikke er noen avhengighet mellom $ m $ eksempler i en minibatch, er den beregnede $ \ hat {g} (m) $ en objektiv estimat av den sanne gradienten. (Kvadratiske) standardfeil i estimatene med forskjellige minibatchstørrelser er omvendt proporsjonal med størrelsen på minibatchen. Det vil si $$ {SE ({\ hat {g} (n)}) \ over SE ({\ hat {g} (m)})} = {\ sqrt { m \ over n}} $$ Det vil si at reduksjonen av standardfeil er kvadratroten av økningen i prøvestørrelsen. Dette betyr at hvis minibatchstørrelsen er liten, må læringsgraden også være liten for å oppnå stabilitet over den store variansen. Når prøvene ikke er uavhengige, opprettholdes ikke eiendommen til upartisk estimat lenger. Det krever at du blander prøvene før treningen, hvis prøvene ikke blir sekvensert tilfeldig.

2. Hvorfor minibatch kan være fungerer bedre .

For det første gjør minibatch noen læringsproblemer fra teknisk vanskelig å kunne gjennomføres på grunn av redusert beregningskrav med mindre batchstørrelse.

For det andre betyr redusert batchstørrelse ikke nødvendigvis redusert gradientnøyaktighet. Treningsprøvene har mange lyder eller avvik eller skjevheter. En tilfeldig samplet minibatch kan gjenspeile den sanne data som genererer distribusjon bedre (eller ikke verre) enn den opprinnelige hele batchen. Hvis noen iterasjoner av minibatchgradientoppdateringene gir deg et bedre estimat, kan det gjennomsnittlige resultatet av en epoke generelt være bedre enn gradienten beregnet fra en full batch.

For det tredje hjelper minibatch ikke bare med å håndtere ubehagelige dataprøver, men hjelper også med å håndtere ubehagelig kostnadsfunksjon som har mange lokale minima. Som Jason_L_Bens nevner, kan det hende at feilmanifoldene er lettere å fange en vanlig gradient inn i et lokalt minima, mens det er vanskeligere å fange den midlertidige tilfeldige gradienten beregnet med minibatch. nå de globale minimumene i ett trinn, men det gjentas på feilmanifolden. Gradient gir deg stort sett bare retningen til å gjenta. Med minibatch kan du gjenta mye raskere. I mange tilfeller, jo flere iterasjoner, jo bedre punkt kan du nå. Du bryr deg ikke i det hele tatt, punktet er optimalt globalt eller til og med lokalt. Du vil bare nå en fornuftig modell som gir deg akseptabel generaliseringsfeil. Minibatch gjør det lettere.

Du finner kanskje boka » Deep learning » av Ian Goodfellow, et al, har ganske gode diskusjoner om dette emnet hvis du leser det nøye gjennom.

Kommentarer

• For konvekse optimaliseringsproblemer er det du sa greit.Men for å bruke gradientmetoder på ikke-konvekse funksjoner, savnet du en veldig kritisk grunn til at SGD er bedre enn batch GD. Se svaret mitt datascience.stackexchange.com/questions/16807/…
• @horaceT Takk for kommentaren. Siden poenget du nevnte er beskrevet av Jason_L_Bens ovenfor med detaljer, gadd jeg ikke å gjenta, men henviste svaret hans i siste tredje ledd, med respekt. For å optimalisere problem med gradientnedstigning reflekteres ikke-konveks av det lokale minimaet inkludert sadelpunkt (se siste tredje avsnitt); og av hensyn til beskrivelsen beskriver mitt svar SGD som minibatch, men med en batchstørrelse på 1 (se tredje ledd).
• Hvorfor har du sagt praktisk talt i * endelig i en epoke, er du praktisk talt databehandling gjennomsnittet av stigningene basert på alle gitte prøver. *? Ikke ‘ t du mener at dette påstanden er feil på grunn av oppdatering av vektene ved hvert trinn?
• @ Media Du har rett. Jeg ‘ har fjernet det siste avsnittet. Takk.

For meg ligner batchgradient mager gradient. I lean gradient blir batchstørrelsen valgt slik at hver parameter som skal oppdateres, også varieres uavhengig, men ikke nødvendigvis ortogonalt, i batchen. For eksempel, hvis batchen inneholder 10 eksperimenter, 10 rader, er det mulig å danne $ 2 ^ {10-1} = 512 $ uavhengige kolonner. 10 rader muliggjør uavhengig, men ikke ortogonal, oppdatering av 512 parametere.