Kto wynalazł stochastyczne zejście gradientu?

Staram się zrozumieć historię zejścia gradientowego i stochastycznego . Gradientowe zejście zostało wynalezione w Cauchy w 1847 roku. Méthode générale pour la résolution des systèmes d'équations symultanes . str. 536–538 Więcej informacji na ten temat można znaleźć tutaj .

Od tego czasu metody zejścia gradientowego ciągle się rozwijają i nie znam ich historii. W szczególności interesuje mnie wynalazek stochastycznego spadku.

Odniesienie, które może być wykorzystane w pracy naukowej w bardziej niż mile widziane.

— DaL
źródło

Dowiedziałem się o SGD przed uczeniem maszynowym, więc musiało to być przed tym wszystkim

— Aksakal

Cóż, Cauchy na pewno wymyślił GD przed uczeniem maszynowym, więc nie będę zaskoczony, że SGC również został wymyślony wcześniej.

— DaL

Kiefer-Wolfowitz Stochastic Approximation en.wikipedia.org/wiki/Stochastic_approximation jest tam w większości, poza bezpośrednim „symulowaniem” gradientu.

— Mark L. Stone

„Stochastic Gradient Descent” z ML jest taki sam jak „Stochastic Subgradient Method” z wypukłej optymalizacji. A metody podskładników odkryto w latach 1960–1970 w ZSRR w Moskwie. Może także w USA. Widziałem wideo, w którym Boris Polyak (autor metody ciężkiej kuli) powiedział, że (i wszyscy ludzie) zaczynają myśleć o metodach podporządkowania w 1970 r. ( Youtube.com/watch?v=2PcidcPxvyk&t=1963s ) ....

— bruziuz,

Odpowiedzi:

Stochastyczne zejście gradientu poprzedza Stochastic Approximation, jak po raz pierwszy opisali Robbins i Monro w swojej pracy A Stochastic Approximation Method . Kiefer i Wolfowitz opublikowali następnie swój artykuł, Stochastic Estimation of Maximum of a Regression Functionco jest bardziej rozpoznawalne dla osób zaznajomionych z wariantem ML aproksymacji stochastycznej (tj. stochastycznego spadku gradientu), jak zauważył Mark Stone w komentarzach. W latach sześćdziesiątych przeprowadzono wiele badań w tym zakresie - Dvoretzky, Powell, Blum - wszystkie opublikowane wyniki, które dzisiaj przyjmujemy za pewnik. Jest to stosunkowo niewielki skok z metody Robbinsa i Monro do metody Kiefera Wolfowitza, a jedynie zmiana definicji problemu, aby następnie przejść do stochastycznego spadku gradientu (w przypadku problemów z regresją). Powyższe artykuły są powszechnie cytowane jako poprzedniki Stochastic Gradient Descent, jak wspomniano w tym artykule przeglądowym Nocedal, Bottou i Curtis , który przedstawia krótką perspektywę historyczną z punktu widzenia uczenia maszynowego.

Uważam, że Kushner i Yin w swojej książce Stochastic Approximation oraz Recursive Algorytms and Applications sugerują, że pojęcie to było używane w teorii kontroli już w latach 40., ale nie pamiętam, czy mieli na to jakieś uzasadnienie, czy też był anegdotyczne, ani nie mam dostępu do ich książki, aby to potwierdzić.

Herbert Robbins i Sutton Monro Stochastyczna metoda aproksymacji The Annals of Mathematical Statistics, tom. 22, nr 3. (wrzesień 1951), str. 400–407.

J. Kiefer i J. Wolfowitz Stochastyczne oszacowanie maksimum funkcji regresji Ann. Matematyka Statystyk. Tom 23, Number 3 (1952), 462-466

Leon Bottou i Frank E. Curtis i Jorge Nocedal Metody optymalizacji uczenia maszynowego na dużą skalę , raport techniczny, arXiv: 1606.04838

— David Kozak
źródło

Czy możesz podać dokładne referencje? A jeśli chodzi o wynalazek SGD, wydaje się, że był w latach 40., ale nie jest jasne, kto i gdzie?

— DaL,

Z pewnością powszechnie uważa się Robbins i Monro w 1951 r. Z algorytmami aproksymacji Stochastic . Słyszałem, że coś podobnego pojawiło się w literaturze teorii kontroli w latach 40. (tak jak powiedziałem, myślę, że Kushner i Yin, ale nie mam tej książki pod ręką), ale poza tym jednym miejscem wydaje się, że wszyscy cytują Robbinsa i Monro, w tym Nocedal i in. odnośnik, do którego linkowałem.

— David Kozak,

Więc naszym wiodącym kandydatem jest teraz H. Robbins i S. Monro. Stochastyczna metoda aproksymacji. The Annals of Mathematical Statistics, 22 (3): 400–407, 1951., jak napisano w Nocedal, Bottou i Curtis w pdfs.semanticscholar.org/34dd/…

— DaL

I tak jest to określane jako pochodzenie SGD, ale w podsumowaniu (właściwie abstrakcyjnym w dzisiejszych terminach) jest napisane: „M (x) przyjmuje się, że jest on funkcją monotoniczną x, ale jest nieznane eksperymentatorowi, i to pożądane jest znalezienie rozwiązania x = 0 równania thc M (x) = a, gdzie a jest daną stałą. " Jeśli M (x) jest nieznane, nie można go wyprowadzić. Może to kolejny starożytny przodek?

— DaL

Zgoda, w pewnym sensie. Kiefer Wolfowitz wykorzystał tę analizę do opracowania swojej pracy, która jest bardziej rozpoznawalna w dzisiejszej postaci. Jak wspomniano powyżej Mark Stone. Ich artykuł można znaleźć tutaj: projecteuclid.org/download/pdf_1/euclid.aoms/1177729392 .

— David Kozak,

Widzieć

Rosenblatt F. Perceptron: model probabilistyczny do przechowywania i organizacji informacji w mózgu. Przegląd psychologiczny. 1958 listopada; 65 (6): 386.

Nie jestem pewien, czy SGD został wynaleziony wcześniej w literaturze optymalizacyjnej - prawdopodobnie tak było - ale tutaj sądzę, że opisuje zastosowanie SGD do trenowania perceptronu.

Jeśli system znajduje się w stanie dodatniego wzmocnienia, wówczas dodatnie AV jest dodawane do wartości wszystkich aktywnych jednostek A w zestawach źródłowych odpowiedzi „on”, podczas gdy ujemne AV jest dodawane do aktywnych jednostek w źródle - zestawy odpowiedzi „wyłączonych”.

Nazywa te „dwoma rodzajami wzmocnienia”.

Odwołuje się także do książki o tych „systemach biwalentnych”.

Rosenblatt F. Perceptron: teoria statystycznej separowalności w systemach poznawczych (Project Para). Cornell Aeronautical Laboratory; 1958.

— użytkownik0
źródło

Dobry krok do przodu, dzięki! Znajduję tutaj pierwsze odniesienie citeseerx.ist.psu.edu/viewdoc/ ... Omówię je. Spodziewam się jednak, że algorytm będzie bardziej wyraźny i formalny.

— DaL

+1 za uwagę na temat optymalizacji. Ponieważ jest wykorzystywany w uczeniu maszynowym do optymalizacji i odkąd optymalizacja stała się wielką sprawą 40 lub 50 lat przed ML - a komputery pojawiły się na obrazie mniej więcej w tym samym czasie - wydaje się to dobrym tropem.

— Wayne

Nie rozumiem, dlaczego mówisz, że ten cytat opisuje SGD.

— ameba mówi Przywróć Monikę

@amoeba mam nadzieję, że nie popełniam błędu, po prostu przeglądałem gazetę, ale myślałem, że opisuje aktualizację perceptronu, która jest po prostu SGD ze stałą szybkością uczenia się.

— użytkownik0

Zgadza się. Mówię tylko, że aspekt stochastyczny nie jest oczywisty z wybranego przez ciebie cytatu. Mam na myśli, że „stochastyczny” GD oznacza po prostu, że aktualizacje są wykonywane po jednej próbce treningowej na raz (zamiast obliczania gradientu przy użyciu wszystkich dostępnych próbek treningowych). Algorytm podany w en.wikipedia.org/wiki/Perceptron#Steps sprawia, że ten „stochastyczny” aspekt jest natychmiast jasny w kroku 2.

— ameba mówi Przywróć Monikę