Spørsmål:
Hvem oppfant stokastisk gradientnedstigning?
DaL
2017-11-14 19:49:20 UTC
view on stackexchange narkive permalink

Jeg prøver å forstå historien til Gradient avstamning og Stokastisk gradient avstamning.Gradientavstamning ble oppfunnet i Cauchy i 1847. Méthode générale pour la resolution des systèmes d'équations simultanées.s. 536–538 For mer informasjon om det, se her.

Siden da fortsatte metodene for å komme ned og jeg er ikke kjent med historien deres.Spesielt er jeg interessert i oppfinnelsen av stokastisk gradientnedstigning.

En referanse som kan brukes i en fagoppgave på mer enn velkomne.

Jeg lærte om SGD før maskinlæringen, så det må ha vært før hele denne greia
Vel, Cauchy oppfant helt sikkert GD før maskinlæring, så jeg vil ikke bli overrasket over at SGC også ble oppfunnet før.
Kiefer-Wolfowitz Stokastisk tilnærming https://en.wikipedia.org/wiki/Stochastic_approximation er mesteparten av veien dit, annet enn å ikke "simulere" direkte for gradienten.
"Stochastic Gradient Descent" fra ML er det samme som "Stochastic Subgradient Method" fra konveks optimalisering.Og metoder for undergradienter ble oppdaget i løpet av 1960-1970 i Sovjetunionen, Moskva.Kanskje også i USA.Jeg så en video der Boris Polyak (han er forfatter av heavy-ball-metoden) sa at han (og alle mennesker) begynner å tenke på undergradientmetoder i 1970. (https://www.youtube.com/watch?v=2PcidcPxvyk&t=1963-tallet) ....
To svar:
David Kozak
2017-11-18 07:14:20 UTC
view on stackexchange narkive permalink

Stokastisk gradientnedstigning innledes med stokastisk tilnærming som først beskrevet av Robbins og Monro i papiret, En stokastisk tilnærmingsmetode . Kiefer og Wolfowitz publiserte deretter oppgaven sin, Stochastic Estimation of the Maximum of a Regression Function , som er mer gjenkjennelig for folk som er kjent med ML-varianten av Stochastic Approximation (dvs. Stochastic Gradient Descent ), som Mark Stone påpekte i kommentarene. På 60-tallet så det mye forskning langs den veinen - Dvoretzky, Powell, Blum alle publiserte resultater som vi tar for gitt i dag. Det er et relativt lite sprang å komme fra Robbins and Monro-metoden til Kiefer Wolfowitz-metoden, og bare en omformulering av problemet for deretter å komme til Stochastic Gradient Descent (for regresjonsproblemer). Ovennevnte papirer er mye sitert som fortilfellene til Stochastic Gradient Descent, som nevnt i denne gjennomgangspapiret av Nocedal, Bottou og Curtis, som gir et kort historisk perspektiv fra et maskinlæringsperspektiv.

Jeg tror at Kushner og Yin i boken deres Stochastic Approximation and Recursive Algorithms and Applications antyder at forestillingen hadde blitt brukt i kontrollteori helt tilbake til 40-tallet, men jeg husker ikke om de hadde en sitering for det eller om det var anekdotisk, og jeg har heller ikke tilgang til boken deres for å bekrefte dette.

Herbert Robbins og Sutton Monro En stokastisk tilnærmingsmetode Annals of Mathematical Statistics, Vol. 22, nr. 3 (september 1951), s. 400-407.

J. Kiefer og J. Wolfowitz Stochastic Estimation of the Maximum of a Regression Function Ann. Matte. Statist. Volum 23, nummer 3 (1952), 462-466 ​​

Leon Bottou og Frank E. Curtis og Jorge Nocedal Optimaliseringsmetoder for maskinlæring i stor skala , teknisk rapport, arXiv: 1606.04838

Kan du gi eksakte referanser?Og for oppfinnelsen av SGD ser det ut til å være på 40-tallet, men det er ikke klart av hvem og hvor?
Det er absolutt antatt at det er Robbins og Monro i 1951 med * Stochastic Approximation Algorithms *.Jeg har hørt at noe lignende dukket opp i kontrollteorilitteraturen på 40-tallet (som sagt, jeg tror fra Kushner og Yin, men jeg har ikke den boken praktisk), men bortsett fra det ene stedet ser det ut til at alle siterer Robbins ogMonro, inkludert Nocedal et al.referanse jeg lenket til.
Så vår ledende kandidat nå er H. Robbins og S. Monro.En stokastisk tilnærmingsmetode.Annals of Mathematical Statistikk, 22 (3): 400–407, 1951., som skrevet i Nocedal, Bottou og Curtis i https://pdfs.semanticscholar.org/34dd/d8865569c2c32dec9bf7ffc817ff42faaa01.pdf
I så det blir referert til som opprinnelsen til SGD, men i sammendraget (faktisk abstrakt i dagens termer) står det skrevet "M (x) antas at han er en monotone funksjon av x, men er unkno ~ vn til eksperimentatoren, og det er ønsket å finne løsningen x = 0 av thc ligning M (x) = a, der a er en gitt konstant. "Hvis M (x) er ukjent, kan man ikke utlede den. Kanskje det er en annen eldgammel forfedre?
Avtalt, i noen forstand.Kiefer Wolfowitz brukte analysen av dette til å komme med papiret deres, som er mer gjenkjennelig i den formen vi ser i dag.Som nevnt ovenfor av Mark Stone.Deres papir kan bli funnet her: https://projecteuclid.org/download/pdf_1/euclid.aoms/1177729392.
Spranget fra Robbins-Monro til Kiefer-Wolfowitz er ikke stort, og fra Kiefer-Wolfowitz til ML-bruken er knapt verdt å nevne.Jeg ville være trygg på å sitere en (eller begge) av dem som begynnelsen, ettersom forskningen som har ført oss til vår nåværende forståelse, ble utlignet av dem.Selv om det var noen uklare tidligere referanser, nevner mesteparten av forskningen som har blitt gjort siden RM som grunnlaget.
Kul.Så neste referanse er J. Kiefer og J. Wolfowitz Stochastic Estimation of the Maximum of a Regression Function Ann.Matte.Statist. Volum 23, nummer 3 (1952), 462-466.(tilgjengelig på https://projecteuclid.org/euclid.aoms/1177729392)
Kan du redigere svaret ditt og legge til alle de nøyaktige referansene, så jeg gir deg belønningen.
Redigert, takk for at du hjelper til med å gjøre det til et bedre svar :)
user0
2017-11-14 20:14:04 UTC
view on stackexchange narkive permalink

Se

Rosenblatt F. Perceptron: En sannsynlig modell for informasjon lagring og organisering i hjernen.Psykologisk gjennomgang.1958 Nov; 65 (6): 386.

Jeg er ikke sikker på om SGD ble oppfunnet før dette i optimaliseringslitteraturen - sannsynligvis var det - men her tror jeg han beskriver en anvendelse av SGD for å trene en perseptron.

Hvis systemet er under en positiv forsterkning, så a positiv AV legges til verdiene til alle aktive A-enheter i kildesett med "på" -svar, mens en negativ A V blir lagt til aktive enheter i kildesettene av "av" -svar.

Han kaller disse "to typer forsterkninger".

Han refererer også til en bok med mer om disse "toverdige systemene".

Rosenblatt F. Perceptron: en teori om statistisk separasjon i kognitive systemer (Project Para).Cornell Aeronautical Laboratory; 1958.

Et godt skritt foran, takk!Jeg finner den første referansen online her http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.335.3398&rep=rep1&type=pdf Jeg skal gå gjennom den.Imidlertid forventer jeg å finne algoritmen mer eksplisitt og formell.
+1 for merknaden om optimalisering.Siden det ble brukt i maskinlæring for å gjøre optimalisering, og siden optimalisering ble en stor avtale 40 eller 50 år før ML - og datamaskiner også kom inn i bildet omtrent samtidig - virker det som en god ledelse.
Jeg forstår ikke hvorfor du sier at dette sitatet beskriver SGD.
@amoeba forhåpentligvis gjør jeg ikke en feil, bare skummet papiret, men jeg skjønt at han beskrev perceptron-oppdateringen som bare er SGD med konstant læringsrate.
Det er riktig.Jeg sier bare at det stokastiske aspektet ikke fremgår av sitatet du valgte.Jeg mener, "stokastisk" GD betyr ganske enkelt at oppdateringer gjøres en treningsprøve om gangen (i stedet for å beregne gradient ved å bruke alle tilgjengelige treningsprøver).Algoritmen gitt i https://en.wikipedia.org/wiki/Perceptron#Steps gjør dette "stokastiske" aspektet umiddelbart klart i trinn 2.


ⓘ
Denne spørsmålet ble automatisk oversatt fra engelsk.Det opprinnelige innholdet er tilgjengelig på stackexchange, som vi takker for cc by-sa 3.0-lisensen den distribueres under.
Loading...