Batchgradientnedstigning kontra stokastisk gradientnedstigning

Tillämpningen av nedgång i satsvis eller stokastisk gradient beror verkligen på det förväntade felröret.

Batchgradientnedstigning beräknar lutningen med hela datasetet. Det här är bra för konvexa eller relativt smidiga felgrenrör. I det här fallet flyttar vi något hatt direkt mot en optimal lösning, antingen lokal eller global. Dessutom kommer nedgång i satsvis gradient, med tanke på en glödgad inlärningshastighet, så småningom att hitta det lägsta beloppet i dess attraktionsbassäng. SGD använder faktiskt en minibatch av flera prover, av skäl som kommer att förklaras lite senare. SGD fungerar bra (inte bra, antar jag, men bättre än batchgradientnedstigning) för felgrenrör som har massor av lokala maxima / minima. I detta I det fallet tenderar den något bullrigare gradienten som beräknas med hjälp av det minskade antalet prover att rycka ut modellen från lokala minima till en region som förhoppningsvis är mer optimal. Enstaka prover är riktigt bullriga, medan minibatcher tenderar att genomsnitta lite av bullret. minskar mängden ryck vid användning av minibatcher. En bra balans uppnås när minibatchstorleken är tillräckligt liten för att undvika några av de dåliga lokala minima, men tillräckligt stor för att den inte undviker de globala minima eller bättre presterande l okala minima. (För övrigt förutsätter detta att de bästa minima har en större och djupare attraktionsbassäng och därför är lättare att hamna i.)

En fördel med SGD är att den beräknar mycket snabbare. Stor datauppsättningar kan ofta inte hållas i RAM, vilket gör vektorisering mycket mindre effektiv. Snarare måste varje prov eller parti prover laddas, bearbetas, resultaten lagras och så vidare. Minibatch SGD, å andra sidan, görs vanligtvis avsiktligt tillräckligt små för att vara beräkningsförmåga.

Vanligtvis utnyttjas denna beräkningsfördel genom att utföra många fler iterationer av SGD, vilket gör många fler steg än konventionell batchgradientnedstigning . Detta resulterar vanligtvis i en modell som ligger mycket nära den som skulle hittas via batchgradientnedstigning, eller bättre.

Det sätt jag vill tänka på hur SGD fungerar är att föreställa mig att jag har en punkt som representerar min ingångsfördelning. Min modell försöker lära sig den ingångsfördelningen. Runt ingångsfördelningen finns ett skuggat område som representerar ingångsfördelningarna för alla möjliga minibatcher jag kan prova. Det är vanligtvis ett rimligt antagande att minibatchingångsfördelningarna ligger nära den verkliga ingångsfördelningen. Batchgradientnedstigning, vid alla steg, tar den brantaste vägen för att nå den verkliga ingångsfördelningen. SGD, å andra sidan, väljer en slumpmässig punkt inom det skuggade området och tar den brantaste vägen mot den här punkten. Vid varje iteration väljer den dock en ny punkt. Genomsnittet av alla dessa steg kommer att approximera den sanna inmatningsfördelningen, vanligtvis ganska bra.

Kommentarer

• I praktiken använder ingen Batch Gradient Descent. Det ’ är helt enkelt för beräkningsmässigt dyrt för inte så mycket (en vinst är att du ’ faktiskt går ner ” sant ” gradient.) När du har en mycket icke-konvex förlustfunktion behöver du bara gå i mestadels rätt riktning och du ’ så småningom konvergerar o n ett lokalt minimum. Således minibatch SGD.
• @Jason_L_Bens har du någon referens (papper eller onlinetexter) där jag kan läsa mer om dessa algoritmer?
• @ user110320 Inte överst på mitt huvud, nej, även om de ’ är mycket vanliga algoritmer, och det bör därför finnas massor av resurser tillgängliga om ämnet med lite sökning. Om du ’ letar efter ett allmänt tillvägagångssätt, rekommenderar jag ’ att läsa några av Yoshua Bengio ’ s Learning Deep Architectures for AI. Det ’ där jag kom igång.

Som andra svar antyder är den främsta anledningen till att använda SGD att sänka beräkningskostnaden för lutning medan man fortfarande till stor del bibehåller lutningsriktningen i genomsnitt över många minibatcher eller prover – vilket säkert hjälper dig att komma till lokala minima.

1. Varför minibatch fungerar .

Matematiken bakom detta är att ” true ” kostnadsfunktionen (gradienten för generaliseringsfelet eller för oändligt stora uppsättningar av prover) är förväntningen av lutningen $ g $ över den verkliga datagenererande distributionen $ p_ {data} $ ; den faktiska lutningen $ \ hat {g} $ beräknad över ett parti av prover är alltid en approximation till den verkliga lutningen med den empiriska datafördelningen $ \ hat {p} _ {data} $ . $$ \ hat {g} = E _ {\ hat {p} _ {data}} ({\ partial J (\ theta) \ over \ partial \ theta}) $$ Batchgradientnedstigning kan ge dig den möjliga ” optimal ” gradient med tanke på alla dina dataprov, det är inte ” true ” lutning dock. En mindre sats (dvs en minibatch) är förmodligen inte lika optimal som hela satsen, men de är båda ungefärliga – så är minibatchen med ett enda prov (SGD).

Förutsatt att det inte finns något beroende mellan $ m $ prover i en minibatch, den beräknade $ \ hat {g} (m) $ är en opartisk uppskattning av den verkliga lutningen. (Kvadrat) standardfel för uppskattningarna med olika minibatchstorlekar är omvänt proportionell mot storleken för minibatchen. Det vill säga $$ {SE ({\ hat {g} (n)}) över SE ({\ hat {g} (m)})} = {\ sqrt { m \ over n}} $$ Dvs. minskningen av standardfelet är kvadratroten av ökningen av provstorleken. Detta innebär att om minibatchstorleken är liten måste inlärningshastigheten också vara liten för att uppnå stabilitet över den stora variansen. När proverna inte är oberoende bibehålls egenskapen för opartisk uppskattning inte längre. Det kräver att du blandar proverna innan träningen, om proverna inte sekvenseras slumpmässigt.

2. Varför minibatch kan fungerar bättre .

För det första gör minibatch vissa inlärningsproblem från tekniskt svåråtkomliga för att vara smidiga på grund av minskat beräkningskrav med mindre batchstorlek.

För det andra betyder minskad satsstorlek inte nödvändigtvis minskad gradvis noggrannhet. Träningsproverna har många ljud eller avvikelser eller fördomar. En slumpmässigt samplad minibatch kan återspegla den sanna datagenererande distributionen bättre (eller inte sämre) än den ursprungliga hela batchen. Om vissa iterationer av minibatch-gradientuppdateringar ger dig en bättre uppskattning, kan det genomsnittliga resultatet av en epok totalt sett vara bättre än gradienten beräknat från en hel sats.

För det tredje hjälper minibatch inte bara att hantera obehagliga dataprov, men hjälper också till att hantera obehaglig kostnadsfunktion som har många lokala minima. Som Jason_L_Bens nämner kan felgrenarna ibland vara lättare att fånga en vanlig lutning i ett lokalt minima, medan det är svårare att fånga den tillfälligt slumpmässiga lutningen beräknad med minibatch.

Slutligen, med lutande nedstigning, är du inte nå de globala minima i ett steg, men itera på felgrenröret. Gradient ger dig till stor del bara riktningen att itera. Med minibatch kan du iterera mycket snabbare. I många fall, ju fler iterationer, desto bättre poäng kan du nå. Du bryr dig inte riktigt alls, punkten är optimal globalt eller till och med lokalt. Du vill bara nå en rimlig modell som ger dig acceptabelt generaliseringsfel. Minibatch gör det lättare.

Du kan hitta boken ” Deep learning ” av Ian Goodfellow, et al, har ganska bra diskussioner om det här ämnet om du läser igenom det noggrant.

Kommentarer

• För konvexa optimeringsproblem är det du sa bra.Men för att använda gradientmetoder på icke-konvexa funktioner saknade du en mycket kritisk anledning till att SGD är bättre än batch GD. Se mitt svar datascience.stackexchange.com/questions/16807/…
• @horaceT Tack för din kommentar. Eftersom den punkt du nämnde har beskrivits av Jason_L_Bens ovan med detaljer, brydde jag mig inte om att upprepa men hänvisade hans svar i sista tredje stycket, med vederbörlig respekt. För att optimera problem med gradientnedstigning reflekteras icke-konvex av lokala minima inklusive sadelpunkt (se sista tredje stycket); och för beskrivningens skull beskriver mitt svar SGD som minibatch men med en batchstorlek på 1 (se tredje stycket).
• Varför har du sagt praktiskt taget i * äntligen i en epok, du beräknar praktiskt taget medelvärdet av lutningarna baserat på alla givna prover. *? Tycker du att iv id = ”e8a6769ea7”

För mig liknar batchgradient mager gradient. I lean gradient väljs batchstorleken så att alla parametrar som ska uppdateras också varieras oberoende, men inte nödvändigtvis ortogonalt, i batchen. Om batchen till exempel innehåller 10 experiment, 10 rader, är det möjligt att bilda $ 2 ^ {10-1} = 512 $ oberoende kolumner. 10 rader möjliggör oberoende, men inte ortogonal, uppdatering av 512 parametrar.