Stokastisk nedstigning av gradienten

Den stokastiske gradientnedstigningen ( SGD ) er en iterativ metode for optimalisering av differensierbare funksjoner , en stokastisk tilnærming av gradientnedstigningsmetoden ( GD) når kostnadsfunksjonen har form av en sum. SGD fungerer på samme måte som GD, men ved hver iterasjon erstatter den den nøyaktige verdien av gradienten til kostnadsfunksjonen med et estimat oppnådd ved å evaluere gradienten bare på en delmengde av tilleggene. Det er mye brukt for å trene en rekke sannsynlighetsmodeller og maskinlæringsmodeller , for eksempel støttevektormaskiner , logistisk regresjon og grafiske modeller . [1] I kombinasjon med feiltilbakeforplantningsmetoden er det de facto -standarden for trening av kunstige nevrale nettverk . [2]

Kontekst

I mange statistiske og maskinlæringsproblemer er det behov for å optimalisere en funksjon i parameterne [3] som har form av en sum ${\ displaystyle Q (w)}$ $w$

{\ displaystyle Q (w) = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} Q_ {i} (w),}

der hvert tillegg representerer kostnaden beregnet på den th observasjonen i et datasett . I sammenheng med klassisk statistikk dukker dette problemet typisk opp i applikasjoner av minste kvadraters metode eller maksimum sannsynlighet metoden , og estimatorene oppnådd som en løsning på slike problemer kalles M estimatorer . Gradientnedstigningsmetoden itererer gjennom formen ${\ displaystyle Q_ {i}}$ $de$

{\ displaystyle w: = w- \ eta \ nabla Q (w) = w- \ eta {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} \ nabla Q_ {i} ( w),}

hvor er en hyperparameter som kontrollerer amplituden til hvert trinn, og i sammenheng med maskinlæring kalles det læringshastigheten . I mange tilfeller har tilleggene et tilstrekkelig enkelt uttrykk, som tillater en rask evaluering av gradienten ved hver iterasjon (for eksempel i statistikk, funksjonene til den eksponentielle familien ). Men i andre sammenhenger kan evalueringen av hele summen være spesielt dyr, for eksempel når datasettet er spesielt stort og det ikke er noe elementært uttrykk for kostnaden, noe som krever evaluering av alle enkelttilleggene, noe som ofte forekommer, for eksempel , i dype læringsproblemer . Den stokastiske nedstigningen av gradienten adresserer dette problemet ved å tilnærme gradienten til hele summen, og evaluere den bare i en tilfeldig delmengde av tilleggene ved hver iterasjon. [4] $\alder$

Ordlyd

Den klassiske gradientnedstigningen kalles også batch GD, ettersom hele datasettet blir evaluert ved hver iterasjon. Når gradienten i stedet tilnærmes stokastisk, er det mulig å konstruere forskjellige metoder avhengig av antall tillegg som brukes ved hver iterasjon. En mulig tilnærming er den stokastiske nedstigningen av gradienten i linje ( on-line ), som bruker bare ett element av datasettet om gangen, og kalles såkalt fordi det kan brukes når datasettet ikke er fikset og nye data genereres på stedet ( on-line , eller on-the-fly ). Gradienten til er tilnærmet ved hver iterasjon med gradienten beregnet på et enkelt tillegg av kostnadsfunksjonen (tilsvarer et element i datasettet) ${\ displaystyle Q (w)}$

{\ displaystyle w: = w- \ eta \ nabla Q_ {i} (w).}

og parameterne oppdateres etter hver evaluering. Datasettet kan krysses flere ganger, inntil metoden konvergerer. Vanligvis er rekkefølgen av elementene randomisert ved hver kryssing av datasettet, og læringshastigheten kan varieres dynamisk, og reduseres typisk etter hvert som iterasjonene fortsetter ( annealing ). [5] $\alder$

1 2 3 til konvergens gjør :

{\ displaystyle w: = w_ {0}}

{\ displaystyle \ eta: = \ eta _ {0}}

4 datasett: = permutasjon (datasett) 5 for gjøre :

{\ displaystyle i: = 1, ... n}

6 7

{\ displaystyle \! w: = w- \ eta \ nabla Q_ {i} (w).}

{\ displaystyle \ eta: = {\ tekst {annealing}} (\ eta)}

Oppdatering av parametrene online, med iterasjon på enkeltelementene i datasettet, innebærer generelt en svært uregelmessig trend for kostnadsfunksjonen (figur på siden). En mye brukt variant, som representerer en mellomtilnærming mellom inline SGD og batch GD, er kjent som en mini-batch og innebærer å beregne gradienten på et undersett av elementer i datasettet ved hver iterasjon, i stedet for på et enkelt element. Størrelsen på hver mini-batch er generelt kontekstavhengig. Dette gjør utviklingen av kostnadsfunksjonen under iterasjonene mindre støyende, ettersom gradienten ved hver iterasjon blir gjennomsnittet av hver mini-batch, noe som resulterer i en utjevningseffekt , og reduserer beregningskostnadene, noe som tillater en bedre vektorisering av koden. . [5]

Konvergensen til metoden ble studert i sammenheng med konveks optimalisering og stokastisk tilnærming . Oppsummert, hvis læringshastigheten avtar under iterasjonene i henhold til en passende funksjon av tid, og den objektive funksjonen er konveks eller pseudokonveks og tilfredsstiller noen svake hypoteser, konvergerer nedstigningen av den stokastiske gradienten nesten helt sikkert til et lokalt optimalt punkt. [6] [7] [8]

Utvidelser og varianter

Mange utvidelser av metoden har blitt foreslått, spesielt i sammenheng med maskinlæring , der den stokastiske nedstigningen av gradienten er en uunnværlig metode for å trene dype kunstige nevrale nettverk . I denne sammenhengen har objektivfunksjonen typisk titalls millioner parametere som skal optimaliseres, noe som gjør det vanskelig å rømme fra setepunktene . [9]

Et av de viktige aspektene ved å formulere metoder er tilstedeværelsen av hyperparametre som må optimaliseres selv, og evnen til en algoritme til ikke å være avhengig av eksplisitte hyperparametre er generelt et positivt aspekt. En grunnleggende hyperparameter i mange metoder er læringshastigheten, som spiller en avgjørende rolle da for høy verdi innebærer liten konvergenskapasitet, mens for lav verdi innebærer svært langsom konvergens. En elementær utvidelse innebærer å bruke en dynamisk læringshastighet med en avtagende funksjon i antall iterasjoner, et konsept som allerede er studert tidligere i andre algoritmer som simulert annealing eller i den adaptive utvidelsen av k- middelalgoritmen . [10]

Flere metoder med adaptiv læringsrate, automatisk justert i løpet av iterasjonene, er utviklet og har blitt utbredt i praktiske anvendelser. Men i noen maskinlæringsproblemer, som objektgjenkjenning eller maskinoversettelse, viser disse metodene dårlige generaliseringsferdigheter og er mindre robuste enn en enkel SGD med momentum. [11] [12] Dette er relatert til det faktum at disse metodene bruker et glidende gjennomsnitt med korttidshukommelse, utsatt for eksponentiell forfall, og siden noen minibatcher er rikere på informasjonsinnhold, men samtidig sjeldnere, har deres innflytelse er begrenset, noe som svekker robustheten til metoden. [1. 3]

Øyeblikk

Moment er et begrep som er avhengig av tidligere iterasjoner, som legges til gradienten i et forsøk på å regulere bevegelse i parameterrommet . Det ble beskrevet av Rumelhart , Hinton og Williams i deres banebrytende artikkel fra 1986 om tilbakespredning av feil . [14] Parameteroppdatering bruker en lineær kombinasjon av gradienten i gjeldende iterasjon og oppdateringen i forrige iterasjon [15] [16]

{\ displaystyle \ Delta w_ {t + 1} = \ alpha \ Delta w_ {t} - \ eta \ nabla Q_ {i} (w_ {t})}

{\ displaystyle w_ {t + 1} = w_ {t} + \ Delta w_ {t + 1}}

som resulterer i

{\ displaystyle w_ {t + 1} = w_ {t} - \ eta \ nabla Q_ {i} (w_ {t}) + \ alpha \ Delta w_ {t}}

Denne metoden introduserer en annen hyperparameter for å sjekke øyeblikkseffekten, som er viktigheten av forrige iterasjon. En empirisk verdi for denne parameteren er vanligvis fastsatt rundt . [17] $\ alfa$ ${\ displaystyle \ alpha = 0,9}$

Metoden har lenge vært brukt i trening av nevrale nettverk [18] og navnet stammer fra en ikke helt nøyaktig analogi med lineært momentum i fysikk, da parametervektoren kan sees på som en bevegelig partikkel i parametrenes rom, underlagt akselerasjon med en kraft hvis potensial uttrykkes av kostnadsfunksjonen.

NAG

NAG ( Nesterov accelerated gradient ), introdusert av Jurij Nesterov i 1983, er en utvidelse av momentmetoden som tilnærmer den fremtidige posisjonen til parameterne, og introduserer et korrekt uttrykk som tar hensyn til bevegelsen. [19] ${\ displaystyle w + \ alpha \ Delta w}$

{\ displaystyle \ Delta w_ {t + 1} = \ alpha \ Delta w_ {t} - \ eta \ nabla Q_ {i} (w_ {t} + \ alpha \ Delta w_ {t})}

{\ displaystyle w_ {t + 1} = w_ {t} + \ Delta w_ {t + 1}}

Denne korreksjonen forhindrer overdreven bevegelse i parameterrommet, og introduksjonen har resultert i betydelige forbedringer i ytelsen til rekursive nevrale nettverk . [20]

AdaGrad

AdaGrad ( adaptive gradient ) er en metode publisert i 2011 [21] [22] som bruker en uavhengig læringsrate for hver parameter. Intuitivt bruker denne metoden høyere læringsrater for parametere med en mer sparsom distribusjon, og langsommere læringshastigheter for parametere med en tettere distribusjon. AdaGrad konvergerer ofte raskere enn vanlig SGD, spesielt når datadistribusjonen er sparsom og spredte parametere har mer informasjonsinnhold, noe som forekommer for eksempel i naturlig språkbehandlingsproblemer eller automatisk gjenkjenning av bildeinnhold. [21]

Læringshastigheten multipliseres med en vektor hvis elementer representerer skalafaktorene for hver parameter. Denne vektoren er diagonalen til matrisen oppnådd som et eksternt produkt $\alder$ $G.$

{\ displaystyle G = \ sum _ {\ tau = 1} ^ {t} g _ {\ tau} g _ {\ tau} ^ {\ mathsf {T}}}

hvor er gradienten ved iterasjonen . De diagonale elementene til har formen ${\ displaystyle g _ {\ tau} = \ nabla Q_ {i} (w)}$ $\ tau$ $G.$

{\ displaystyle G_ {j, j} = \ sum _ {\ tau = 1} ^ {t} g _ {\ tau, j} ^ {2}}

Denne vektoren oppdateres ved hver iterasjon, og parameteroppdateringsuttrykket blir

{\ displaystyle w: = w- \ eta \, \ left (\ mathrm {diag} (G + \ epsilon I) \ høyre) ^ {- {\ frac {1} {2}}} \ circ g}

hvor er Hadamard-produktet og er et utjevningsbegrep, vanligvis med en verdi i størrelsesorden , lagt til for å forbedre numerisk stabilitet . [17] $\ circ$ $\epsilon$ $10 ^ {{- 8}}$

Hvert element er en skaleringsfaktor for læringsraten for en enkelt parameter som skal optimaliseres, og er normen ℓ 2 for en mengde som inkorporerer derivatene fra tidligere iterasjoner, slik at denne faktoren demper læringshastigheten til parametere som er utsatt for brå oppdateringer, og legger større vekt på læringshastigheten til parametere med små eller sjeldne oppdateringer. [18] Ved å uttrykke oppdateringen for hver enkelt parameter, blir formelen ${\ displaystyle G_ {i, i}}$ $w_ {i}$ ${\ displaystyle {\ sqrt {G_ {i}}} = {\ sqrt {\ sum _ {\ tau = 1} ^ {t} g _ {\ tau} ^ {2}}}}$

{\ displaystyle w_ {j}: = w_ {j} - {\ frac {\ eta} {\ sqrt {G_ {j, j} + \ epsilon}}} g_ {j}.}

Selv om det er designet for konvekse optimaliseringsproblemer , brukes AdaGrad også for ikke-konvekse optimaliseringsproblemer. [23] En av hovedfordelene med AdaGrad er dens evne til automatisk å tilpasse læringshastigheten, noe som i praksis gjør det til en metode uten hyperparametere, ettersom mange implementeringer bruker en forhåndsdefinert startverdi (rundt ). Den største ulempen er metodens tendens til å kansellere læringsraten under iterasjonene, noe som fører til en læringsstans, siden summen er positive og nevnerverdien øker strengt som en funksjon av iterasjonene. [17] ${\ displaystyle \ eta = 0,01}$

RMSProp

RMSProp ( Root Mean Square Propagation ) er en adaptiv læringsratemetode som tar opp problemet med å slette læringsraten i AdaGrad. Algoritmen ble ikke publisert i et fagfellevurdert tidsskrift av forfatteren Geoffrey Hinton , men ble opprinnelig foreslått i lysbildene hans for kurset Neural Networks for Machine Learning , holdt på Coursera , [24] som ofte er sitert som den opprinnelige kilden for dette. metode. [17] Gitt det glidende gjennomsnittet av gradientnormen ved hver iterasjon, beregnet i et vindu med tidligere iterasjoner $Og$

{\ displaystyle E [g ^ {2}] _ {t} = \ gamma E [g ^ {2}] _ {t-1} + (1- \ gamma) g ^ {2}}

hvor er en eksponentiell henfallsfaktor, vanligvis med en empirisk fast verdi rundt (også foreslått av Hinton), bestemmer parameteren viktigheten av minnet til tidligere iterasjoner i beregningen av det glidende gjennomsnittet: en verdi lik null betyr at fortiden iterasjoner ignoreres og bare gradienten ved gjeldende iterasjon brukes, og etter hvert som minnet om tidligere iterasjoner øker, blir det mer og mer viktig, på bekostning av den nåværende verdien av gradienten. $\ gamma \ i [0,1]$ ${\ displaystyle \ gamma = 0,9}$ $\område$ $\område$

Ved å definere roten betyr kvadratet som ${\ displaystyle \ mathrm {RMS}}$

{\ displaystyle \ mathrm {RMS} [X] _ {t} = {\ sqrt {E [X] _ {t} + \ epsilon}}}

parameteroppdatering er definert som

{\ displaystyle \ Delta w_ {t} = - {\ frac {\ eta} {\ mathrm {RMS} [g ^ {2}] _ {t}}} g_ {t}.}

På denne måten styres læringsraten dynamisk av kvadratmiddelverdien av gradientnormen. [25] $\alder$

AdaDelta

AdaDelta , i likhet med RMSProp, er en variant av AdaGrad som motvirker kansellering av læringsraten. Den ble utviklet uavhengig av RMSProp, som den kan betraktes som en utvidelse av. Ved hver iterasjon beregnes et glidende gjennomsnitt av kvadratet til gradientnormen i løpet av iterasjonene $Og$

{\ displaystyle E [g ^ {2}] _ {t} = \ gamma E [g ^ {2}] _ {t-1} + (1- \ gamma) g ^ {2}}

og et glidende gjennomsnitt av parameterendringens vektor

{\ displaystyle E [\ Delta w ^ {2}] _ {t} = \ gamma E [\ Delta w ^ {2}] _ {t-1} + (1- \ gamma) \ Delta w_ {t} ^ {2}.}

Parameteroppdateringsvektoren er definert som [26]

{\ displaystyle \ Delta w_ {t} = - {\ frac {\ mathrm {RMS} [\ Delta w ^ {2}] _ {t-1}} {\ mathrm {RMS} [g ^ {2}] _ {t}}} g_ {t}.}

Læringshastigheten er helt automatisk, og AdaDeltas eneste hyperparameter er decay . $\område$

Adam

Adam ( Adaptive moment estimation ) er en utvidelse av RMSProp som tar hensyn til det bevegelige gjennomsnittet av de første ( ) og andre ( ) momentene i gradienten, ved å bruke korrekte estimatorer og , ettersom de er forspente mot verdier nær null, en fenomen som er spesielt tydelig i de første iterasjonene. Angir med parameterne ved iterasjonen , og med kostnadsfunksjonen som skal optimaliseres, har vi $m$ $v$ ${\ displaystyle {\ hat {m}}}$ ${\ displaystyle {\ hat {v}}}$ $m$ $v$ ${\ displaystyle w_ {t}}$ $t$ $Q$

{\ displaystyle m_ {t + 1} = \ beta _ {1} m_ {t} + (1- \ beta _ {1}) \ nabla Q (w_ {t})}

{\ displaystyle v_ {t + 1} = \ beta _ {2} v_ {t} + (1- \ beta _ {2}) (\ nabla Q (w_ {t})) ^ {2}}

{\ displaystyle {\ hat {m}} = {\ frac {m_ {t + 1}} {1- \ beta _ {1} ^ {t + 1}}}}

{\ displaystyle {\ hat {v}} = {\ frac {v_ {t + 1}} {1- \ beta _ {2} ^ {t + 1}}}}

{\ displaystyle w_ {t + 1} = w_ {t} - \ eta {\ frac {\ hat {m}} {{\ sqrt {\ hat {v}}} + \ epsilon}}}

hvor er en utjevningsterm lagt til for numerisk stabilitet , mens og er hyperparametre som kontrollerer eksponentiell forfall. Forfatterne foreslår , og . [27] $\epsilon$ $\ beta_1$ $\ beta _ {2}$ ${\ displaystyle \ epsilon = 10 ^ {- 8}}$ ${\ displaystyle \ beta _ {1} = 0,9}$ ${\ displaystyle \ beta _ {2} = 0,999}$

AdaMax

AdaMax er en variant av Adam som bruker gradient maksimumsnormen i stedet for ℓ 2 normen i momentestimat iht.

{\ displaystyle u_ {t + 1} = \ beta _ {2} u_ {t} + (1- \ beta _ {2}) | g_ {t + 1} | _ {\ infty} = \ max \ left \ {\ beta _ {2} u_ {t}, | g_ {t + 1} | \ høyre \}}

får oppdateringsformelen

{\ displaystyle w_ {t + 1} = w_ {t} - \ eta {\ frac {\ hat {m}} {u_ {t}}}}

der det verken krever korrigering eller utjevning. Forfatterne foreslår , og . [27] ${\ displaystyle u_ {t}}$ ${\ displaystyle \ age = 0,002}$ ${\ displaystyle \ beta _ {1} = 0,9}$ ${\ displaystyle \ beta _ {2} = 0,999}$

Nadam

Nadam ( Nesterov-accelerated Adaptive Moment Estimation ) er en metode som inkorporerer NAG i Adam. Vi har utvidet Adams parameteroppdateringsformel, erstattet med dens definisjon, [28] ${\ displaystyle {\ hat {m_ {t}}}}$

{\ displaystyle w_ {t + 1} = w_ {t} - \ eta {\ frac {\ hat {m}} {{\ sqrt {\ hat {v}}} + \ epsilon}} = w_ {t} - {\ frac {\ eta} {{\ sqrt {\ hat {v}}} + \ epsilon}} \ venstre (\ beta _ {1} {\ hat {m}} _ {t-1} + {\ frac {(1- \ beta _ {1}) g_ {t}} {1- \ beta _ {1} ^ {t}}} \ høyre)}

Vi kan deretter bruke Nesterov-korreksjonen ved å erstatte den korrekte estimatoren for øyeblikket ved forrige iterasjon med estimatet ved gjeldende iterasjon , og oppnå Nadam-parameteroppdateringsformelen [29] ${\ displaystyle {\ hat {m}} _ {t-1}}$ ${\ displaystyle {\ hat {m}} _ {t}}$

{\ displaystyle w_ {t + 1} = w_ {t} - {\ frac {\ eta} {{\ sqrt {\ hat {v}}} + \ epsilon}} \ venstre (\ beta _ {1} {\ hat {m}} _ {t} + {\ frac {(1- \ beta _ {1}) g_ {t}} {1- \ beta _ {1} ^ {t}}} \ høyre).}

AMSGrad

AMSGrad er en Adam-variant som erstatter det bevegelige gjennomsnittet av kvadratet til gradientnormen i tidligere iterasjoner med maksimum, i et forsøk på å redusere korttidsminneeffekten som i noen problemer begrenser robustheten til mange ratemetoder. læring [13]

{\ displaystyle m_ {t + 1} = \ beta _ {1} m_ {t} + (1- \ beta _ {1}) \ nabla Q (w_ {t})}

{\ displaystyle v_ {t + 1} = \ beta _ {2} v_ {t} + (1- \ beta _ {2}) (\ nabla Q (w_ {t})) ^ {2}}

{\ displaystyle {\ hat {v}} _ {t + 1} = \ maks \ venstre \ {{\ hat {v}} _ {t}, v_ {t + 1} \ høyre \}}

{\ displaystyle w_ {t + 1} = w_ {t} - \ eta {\ frac {m_ {t + 1}} {{\ sqrt {{\ hat {v}} _ {t + 1}}} + \ epsilon}}}

kSGD

kSGD ( Kalman-basert Stochastic Gradient Descent ) [30] er en metode for å lære parametere i kvasi-likelihood- modeller , inkludert som spesielle tilfeller lineære og ikke- lineære regresjonsmodeller , generaliserte lineære modeller og nevrale nettverk med gjennomsnittlig kvadratfeil som kostnadsfunksjon. For nettbasert læring er kSGD et spesielt tilfelle av Kalman-filter i tilfelle av lineære regresjonsproblemer, eller et spesielt tilfelle av et utvidet Kalman-filter for ikke-lineære regresjonsproblemer, og utgjør en formelt streng utvidelse av nedstigningen av gradienten. [31] [32]

kSGD er ikke følsom for tilstandsnummeret til problemet, [33] har en stopptilstand og et robust valg av hyperparametre. Ulemper inkluderer det faktum at kSGD krever lagring av en tett kovariansmatrise , og krever beregning av et matrise-vektorprodukt ved hver iterasjon.

Gitt kostnadsfunksjonen , hvor parametrene er definert av en observasjon på en slik måte at ${\ displaystyle Q_ {i} (w)}$ ${\ displaystyle w \ in \ mathbb {R} ^ {p}}$ ${\ displaystyle (Y_ {i}, X_ {i}) \ in \ mathbb {R} \ ganger \ mathbb {R} ^ {d}}$

{\ displaystyle \ nabla _ {w} Q_ {i} (w) = {\ frac {Y_ {i} - \ mu (X_ {i}, w)} {V (\ mu (X_ {i}, w) )}} \ nabla _ {w} \ mu (X_ {i}, w)}

hvor er den forventede verdien av data og er variansen til data ). Oppdateringene av parameterne og kovariansmatrisen er gitt av ${\ displaystyle \ mu (X_ {i}, w)}$ $Y_ {i}$ $X_i$ ${\ displaystyle V (\ mu (X_ {i}, w))}$ $Y_ {i}$ $X_i$ ${\ displaystyle w (t + 1)}$ ${\ displaystyle M (t + 1)}$

{\ displaystyle p = \ nabla _ {w} \ mu (X_ {t + 1}, w (t))}

{\ displaystyle m = \ mu (X_ {t + 1}, w (t))}

{\ displaystyle v = M (t) p}

{\ displaystyle s = \ min \ lbrace \ gamma _ {1}, \ max \ lbrace \ gamma _ {2}, V (m) \ rbrace \ rbrace + v ^ {\ mathsf {T}} p}

{\ displaystyle w (t + 1) = w (t) + {\ frac {Y_ {t + 1} -m} {s}} v}

{\ displaystyle M (t + 1) = M (t) - {\ frac {1} {s}} vv ^ {\ mathsf {T}}}

hvor er hyperparametrene til metoden. Oppdatering av kan resultere i en udefinert kovariansmatrise, og dette kan unngås på bekostning av å beregne et ekstra matriseprodukt. det kan være en hvilken som helst positiv bestemt symmetrisk matrise, og initialiseres vanligvis med identitet. I en relatert ikke-lineær regresjonsmetode brukes en henfallsfaktor for å oppdatere kovariansmatrisen for å demonstrere konvergens. [34] ${\ displaystyle \ gamma _ {1}, \ gamma _ {2}}$ ${\ displaystyle M (t)}$ ${\ displaystyle M (0)}$

Parallell implementering

Mens den stokastiske gradientnedstigningsalgoritmen er iboende sekvensiell, kan den parallelliseres til å kjøre på distribuerte systemer , typisk ved å operere flere minibatcher parallelt og bruke en delt parameterarray som oppdateres ved å kombinere resultatene. [35] [36] [37] Hvis dataene er tilstrekkelig spredt, det vil si at hvert element i datasettet kun påvirker et begrenset antall parametere, er det mulig å implementere SGD parallelt ved å dele parameterne uten synkronisering , og unngå ekstrakostnadene ved sistnevnte, ettersom sannsynligheten for å kjøre inn i kritiske kjøringer er svært lav og det samme, mens det introduserer støy i prosessen, ser ut til å ha en ubetydelig effekt på konvergensen til algoritmen. [38]

Noen rammeverk bruker en serverprosess som lagrer parametere, og en samling av arbeidsprosesser som beregner gradienter og manipulerer parametere via synkroniseringsprimitiver. TensorFlow fra versjon 0.8 gir naturlig modelltrening med optimalisering fordelt på flere GPUer . [39]

Optimaliseringer

I komplekse problemer, for eksempel ved optimalisering av parametrene til svært dype nevrale nettverk , kan det være nyttig å introdusere støy ved hver iterasjon, og legge til gradienten en gaussisk støykomponent med null gjennomsnitt og varians , underlagt utglødning som en funksjon av antall iterasjoner . Denne tilnærmingen gjør prosessen mindre avhengig av startverdien til parameterne som skal optimaliseres, og øker algoritmens evne til å unnslippe suboptimale lokale minima. [40] ${\ displaystyle \ sigma ^ {2} = {\ frac {\ eta} {(1 + t) ^ {\ gamma}}}}$ $t$

Generelt er det nyttig å randomisere rekkefølgen til datasettet ved hver travers for å unngå å introdusere en skjevhet . I noen tilfeller, for eksempel i maskinlæringsproblemer , kan det imidlertid være nyttig i stedet å krysse datasettet i rekkefølge med økende vanskelighetsgrad for postene, der vanskeligheten avhenger av problemets art (for eksempel vanskeligheter med å klassifisere en post i et problem med klassifisering). Denne tilnærmingen kalles curriculum learning [ 41] og flere bestillingsstrategier er studert. [42]

Merknader

^ Jenny Rose Finkel, Alex Kleeman, Christopher D. Manning (2008). Effektiv, funksjonsbasert, betinget tilfeldig feltanalyse. Pros. Årsmøte i ACL.
^ LeCun, Yann A., et al. "Effektiv ryggstøtte." Nevrale nettverk: Triks. Springer Berlin Heidelberg, 2012. 9-48
^ I denne sammenhengen er parametrene til den statistiske modellen de frie variablene som skal optimaliseres, mens parametrene til optimaliseringsmetoden kalles hyperparametre .
^ Léon Bottou og Olivier Bousquet, The Tradeoffs of Large Scale Learning , Advances in Neural Information Processing Systems , vol. 20, 2008, s. 161–168.
^ a b Ruder , s. 3 .
^ Léon Bottou , Online Algorithms and Stokastical Approximations , in Online Learning and Neural Networks , Cambridge University Press, 1998, ISBN 978-0-521-65263-6 .
^ Krzysztof C. Kiwiel, Konvergens og effektivitet av subgradientmetoder for kvasikonveks minimering , i Matematisk programmering (serie A) , vol. 90, n. 1, Berlin, Heidelberg, Springer, 2001, s. 1–25, DOI : 10.1007 / , ISSN 0025-5610 .
^ Herbert Robbins og David O. Siegmund , A convergence theorem for non negative near supermartingales and some applications , i Jagdish S. Rustagi (red.), Optimizing Methods in Statistics , Academic Press, 1971.
^ Yann Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli og Yoshua Bengio, Identifisering og angrep på setepunktproblemet i høydimensjonal ikke-konveks optimalisering , 10. juni 2014.
^ Sitert av Christian Darken og John Moody, Fast adaptive k-betyr clustering: some empirical results , Int'l Joint Conf. On Neural Networks (IJCNN) , IEEE, 1990.
^ G. Huang, Z. Liu, KQ Weinberger og L. van der Maaten, Densely Connected Convolutional Networks , i Proceedings of CVPR , 2017.
^ T. Dozat, Incorporating Nesterov Momentum into Adam , i ICLR Workshop , 2016.
^ a b Sashank J. Reddi, Satyen Kale og Sanjiv Kumar, On the Convergence of Adam and Beyond , i Proceedings of ICLR , 2018.
^ David E. Rumelhart, Hinton, Geoffrey E. og Williams, Ronald J., Learning representations by back-propagating errors , i Nature , vol. 323, n. 6088, 8. oktober 1986, s. 533-536, DOI : 10.1038 / 323533a0 .
^ Ilya Sutskever, Martens, James, Dahl, George og Hinton, Geoffrey E., On the important of initialization and momentum in deep learning ( PDF ), redigert av Sanjoy Dasgupta og David Mcallester, In Proceedings of the 30th international conference on machine learning (ICML-13) , vol. 28, Atlanta, GA, juni 2013, s. 1139–1147. Hentet 14. januar 2016 .
^ Ilya Sutskever, Trening av tilbakevendende nevrale nettverk ( PDF ) (Ph.D.), University of Toronto, 2013, s. 74.
^ a b c d En oversikt over optimaliseringsalgoritmer for gradientnedstigning , på ruder.io .
^ a b Matthew D. Zeiler, ADADELTA: An adaptive learning rate method , 2012.
^ Nesterov, Yuri (1983). En metode for ubegrenset konveks minimeringsproblem med konvergenshastigheten o (1 / k2). ANSSSR vol. 269, s. 543–547.
^ Bengio, Y., Boulanger-Lewandowski, N. og Pascanu, R, Advances in Optimizing Recurrent Networks , 2012.
^ a b John Duchi, Elad Hazan og Yoram Singer, Adaptive subgradient-metoder for online læring og stokastisk optimalisering ( PDF ), i JMLR , vol. 12, 2011, s. 2121-2159. Hentet 10. juni 2018 (Arkiveret fra originalen 28. mai 2019) .
^ Joseph Perla, Notes on AdaGrad ( PDF ), på seed.ucsd.edu , 2014 (arkivert fra originalen 30. mars 2015) .
^ Maya R. Gupta, Samy Bengio og Jason Weston, Training very multiclass classifiers ( PDF ), i JMLR , vol. 15, nei. 1, 2014, s. 1461–1492. Hentet 10. juni 2018 (arkivert fra originalen 25. oktober 2018) .
^ Tieleman, Tijmen og Hinton, Geoffrey (2012). Forelesning 6.5-rmsprop: Del gradienten med et løpende gjennomsnitt av dens siste størrelse. KURS: Nevrale nettverk for maskinlæring
^ Geoffrey Hinton , Oversikt over mini-batch gradient descent ( PDF ), su cs.toronto.edu , s. 27–29. Hentet 27. september 2016 (arkivert fra originalen 23. november 2016) .
^ Zeiler, MD, ADADELTA: An Adaptive Learning Rate Method , 2012.
^ a b Kingma Diederik og Jimmy Ba, Adam: En metode for stokastisk optimalisering , 2014.
^ For enkelhets skyld ignoreres forskjellen mellom og når du erstatter . ${\ displaystyle {\ hat {m}} _ {t-1}}$ ${\ displaystyle 1- \ beta _ {1} ^ {t}}$ ${\ displaystyle 1- \ beta _ {1} ^ {t-1}}$
^ Timothy Dozat, Incorporating Nesterov Momentum into Adam . 18. februar 2016.
^ V. Patel, Kalman-basert stokastisk gradientmetode med stopptilstand og ufølsomhet for kondisjonering , i SIAM Journal on Optimization , vol. 26, n. 4, 1. januar 2016, s. 2620–2648, DOI : 10.1137 / 15M1048239 , ISSN 1052-6234 , arXiv : .
^ A Cichocki, T Chen og S Amari, Stabilitetsanalyse av læringsalgoritmer for blindkildeseparasjon. , i Nevrale nettverk: det offisielle tidsskriftet til International Neural Network Society , vol. 10, nei. 8, november 1997, s. 1345-1351, PMID 12662478 .
^ Ollivier Yann, Online Natural Gradient as a Kalman Filter , 1. mars 2017 , arXiv : 1703.00209 .
^ I det lineære regresjonsproblemet er avviket til den objektive funksjonen til kSGD (summen av skjevhet og varians) ved iterasjonen gitt ved at det med sannsynlighet konvergerer til 1 med en hastighet avhengig av , hvor er variansen til residualene. Dessuten, for passende verdier på , kan det vises at skjevheten til objektivfunksjonen ved iterasjonen er gitt ved at den med sannsynlighet konvergerer til 1 med en hastighet avhengig av , hvor er den optimale parameteren. $k$ ${\ displaystyle {\ frac {1+ \ epsilon} {k}} p \ sigma ^ {2}}$ ${\ displaystyle \ epsilon \ in (0,1)}$ ${\ displaystyle \ sigma ^ {2}}$ ${\ displaystyle \ gamma _ {1}, \ gamma _ {2}}$ $k$ ${\ displaystyle {\ frac {(1+ \ epsilon) ^ {2}} {2k ^ {2}}} \ Vert w (0) -w _ {*} \ Vert _ {2} ^ {2}}$ ${\ displaystyle \ epsilon \ in (0,1)}$ ${\ displaystyle w _ {*}}$
^ D. Bertsekas, Incremental Least Squares Methods and the Extended Kalman Filter , i SIAM Journal on Optimization , vol. 6, nei. 3, 1. august 1996, s. 807–822, DOI : 10.1137 / , ISSN 1052-6234 .
^ Zinkevich, Martin, Markus Weimer, Lihong Li og Alex J. Smola. "Parallellisert stokastisk gradientnedstigning." I Fremskritt i nevrale informasjonsbehandlingssystemer, s. 2595-2603. 2010
^ Dekel, Ofer, Ran Gilad-Bachrach, Ohad Shamir og Lin Xiao. "Optimal distribuert online prediksjon ved bruk av minibatcher." Journal of Machine Learning Research 13, nr. Jan (2012): 165-202.
^ Chen, J., Pan, X., Monga, R., Bengio, S., & Jozefowicz, R. (2016). Besøker distribuert synkron SGD på nytt. arXiv preprint arXiv: 1604.00981.
^ Recht, Benjamin, Christopher Re, Stephen Wright og Feng Niu. "Hogwild: En låsefri tilnærming til parallellisering av stokastisk gradientnedstigning." I Fremskritt i nevrale informasjonsbehandlingssystemer, s. 693-701. 2011.
^ Derek Murray, kunngjør TensorFlow 0.8 - nå med distribuert databehandling! , på ai.googleblog.com , 13. april 2016.
^ Arvind Neelakantan, Luke Vilnis, Quoc V. Le, Ilya Sutskever, Lukasz Kaiser, Karol Kurach og James Martens, Adding Gradient Noise Improves Learning for Very Deep Networks , i arXiv: 1511.06807 [cs, stat] , 20. november 2015.
^ Yoshua Bengio, Jérôme Louradour, Ronan Collobert og Jason Weston, Curriculum learning , ACM, 14. juni 2009, s. 41–48, DOI : 10.1145 / 1553374.1553380 , ISBN 978-1-60558-516-1 .
^ Wojciech Zaremba og Ilya Sutskever, Learning to Execute , i arXiv: 1410.4615 [cs] , 16. oktober 2014.

Bibliografi

Dimitri P. Bertsekas , ikke- lineær programmering , 2nd, Cambridge, MA., Athena Scientific, 1999, ISBN 1-886529-00-0 .
Dimitri Bertsekas , konveks analyse og optimalisering , Athena Scientific, 2003.
Léon Bottou , Stokastisk læring , i avanserte forelesninger om maskinlæring , LNAI, vol. 3176, Springer, 2004, s. 146–168, ISBN 978-3-540-23122-6 .
WC Davidon , Nye minste-kvadrat-algoritmer , i Journal of Optimization Theory and Applications , vol. 18, nei. 2, 1976, s. 187–197, DOI : 10.1007 / BF00935703 .
Richard O. Duda, Peter E. Hart og David G. Stork, Pattern Classification , 2nd, Wiley , 2000, ISBN 978-0-471-05669-0 .
Krzysztof C. Kiwiel, Convergence of approximate and incremental subgradient methods for convex optimization , i SIAM Journal of Optimization , vol. 14, n. 3, 2004, s. 807–840, DOI : 10.1137 / S1052623400376366 . (Omfattende referanseliste)
Sebastian Ruder, En oversikt over optimaliseringsalgoritmer for gradientnedstigning , 2017, arXiv : 1609.04747 .
James C. Spall, Introduction to Stochastic Search and Optimization , Wiley , 2003, ISBN 978-0-471-33052-3 .