Qui a inventé la descente de gradient stochastique?

36

J'essaie de comprendre l'histoire de la descente de gradient et de la descente de gradient stochastique . La descente de gradient a été inventée à Cauchy en 1847. Méthode générale de résolution des systèmes d'équations simultanées . pp. 536–538 Pour plus d'informations à ce sujet, voir ici .

Depuis lors, les méthodes de descente sur gradient ont continué à se développer et je ne connais pas encore leur histoire. Je m'intéresse en particulier à l'invention de la descente à gradient stochastique.

Une référence qui peut être utilisée dans un article académique est plus que bien accueillie.

DaL
la source
3
J'ai appris l'existence de SGD avant l'apprentissage de la machine, donc ça devait être avant tout ça
Aksakal
2
Eh bien, Cauchy a certainement inventé GD avant l'apprentissage automatique, donc je ne serais pas surpris que SGC ait également été inventé auparavant.
DaL
3
Approximation stochastique de Kiefer-Wolfowitz fr.wikipedia.org/wiki/Stochastic_approximation est la plupart du temps, sauf que vous ne "simulez" pas directement le gradient.
Mark L. Stone
3
"Stochastic Gradient Descente" de ML est identique à "Stochastic Subgradient Method" de l'optimisation convexe. Et les méthodes de subgradients ont été découvertes au cours des années 1960-1970 en URSS, à Moscou. Peut-être aussi aux Etats-Unis. J'ai vu une vidéo dans laquelle Boris Polyak (il est l'auteur de la méthode heavy-ball) a déclaré qu'il (et toutes les personnes) commençaient à réfléchir aux méthodes de subgradients en 1970. ( youtube.com/watch?v=2PcidcPxvyk&t=1963s ) ....
Bruziuz

Réponses:

27

La descente de gradient stochastique est précédée de l’approximation stochastique telle que décrite pour la première fois par Robbins et Monro dans leur article, A Méthode d’approximation stochastique . Kiefer et Wolfowitz ont ensuite publié leur article, Estimation stochastique de la fonction de régression maximalece qui est plus reconnaissable par les personnes familiarisées avec la variante ML de l'approximation stochastique (c'est-à-dire la descente de gradient stochastique), comme l'a souligné Mark Stone dans les commentaires. Les années 60 ont été le théâtre de nombreuses recherches dans ce sens - Dvoretzky, Powell, Blum ont publié tous les résultats que nous prenons pour acquis aujourd'hui. Passer de la méthode de Robbins et Monro à la méthode de Kiefer Wolfowitz est un progrès relativement mineur, il ne s'agit que d'un recadrage du problème pour ensuite accéder à la descente de gradient stochastique (pour les problèmes de régression). Les documents ci-dessus sont largement cités comme étant les antécédents de la descente de gradient stochastique, comme mentionné dans ce document de synthèse de Nocedal, Bottou et Curtis , qui fournit une brève perspective historique du point de vue de l'apprentissage automatique.

Je crois que Kushner et Yin, dans leur livre Approximation stochastique et algorithmes et applications récursives, suggèrent que la notion avait été utilisée dans la théorie du contrôle dès les années 40, mais je ne me souviens pas s’ils en avaient cité une citation ou s’il en avait été question. anecdotique, je n'ai pas accès à leur livre pour le confirmer.

Herbert Robbins et Sutton Monro Une méthode d'approximation stochastique The Annals of Mathematical Statistics, Vol. 22, n ° 3. (septembre 1951), p. 400-407.

J. Kiefer et J. Wolfowitz Estimation stochastique du maximum d'une fonction de régression Ann. Math. Statist. Volume 23, numéro 3 (1952), 462-466

Leon Bottou et Frank E. Curtis et Jorge Nocedal Méthodes d'optimisation pour l'apprentissage automatique à grande échelle , Rapport technique, arXiv: 1606.04838

David Kozak
la source
Pouvez-vous donner des références exactes? Et pour l'invention de SGD, il semble que ce soit dans les années 40 mais on ne sait pas par qui et où?
DaL
On pense généralement que Robbins et Monro sont connus en 1951 avec les algorithmes d’approximation stochastique . J'ai entendu dire que quelque chose de similaire apparaissait dans la littérature sur la théorie du contrôle dans les années 40 (comme je l'ai dit, je pense de Kushner et Yin mais je n'ai pas ce livre à portée de la main), mais en dehors de cet endroit, tout le monde semble citer Robbins et Monro, y compris le Nocedal et al. référence que j'ai liée à.
David Kozak
Donc, notre candidat principal est maintenant H. Robbins et S. Monro. Une méthode d'approximation stochastique. The Annals of Mathematical Statistics, 22 (3): 400-407, 1951., écrit dans Nocedal, Bottou et Curtis en pdfs.semanticscholar.org/34dd/…
DaL
Je parle donc de l'origine du SGD, mais dans le résumé (en réalité abstrait), il est écrit "M (x) est supposé être une fonction monotone de x mais inconnu de l'expérimentateur, et il on souhaite trouver la solution x = 0 de l'équation M (x) = a, où a est une constante donnée. " Si M (x) est inconnu, on ne peut pas le tirer. Peut-être est-ce un autre ancêtre ancien?
DaL
D'accord, dans un sens. Kiefer Wolfowitz s’est servi de l’analyse de cette question pour élaborer un document plus reconnaissable sous la forme que nous connaissons aujourd’hui. Comme mentionné ci-dessus par Mark Stone. Leur article peut être trouvé ici: projecteuclid.org/download/pdf_1/euclid.aoms/1177729392 .
David Kozak
14

Voir

Rosenblatt F. Le perceptron: un modèle probabiliste pour le stockage et l'organisation de l'information dans le cerveau. Examen psychologique. 1958 novembre; 65 (6): 386.

Je ne suis pas sûr que SGD ait été inventé avant cela dans la littérature sur l'optimisation - c'était probablement le cas - mais je crois qu'il décrit ici une application de SGD pour former un perceptron.

Si le système est dans un état de renforcement positif, un AV positif est ajouté aux valeurs de toutes les unités A actives dans les ensembles source de réponses "on", tandis qu'un AV négatif est ajouté aux unités actives du source. - ensembles de réponses "off".

Il appelle ces "deux types de renforcement".

Il fait également référence à un livre avec plus sur ces "systèmes bivalents".

Rosenblatt F. Le perceptron: une théorie de la séparabilité statistique dans les systèmes cognitifs (projet Para). Laboratoire aéronautique Cornell; 1958.

utilisateur0
la source
1
Un bon pas en avant, merci! Je trouve la première référence en ligne ici citeseerx.ist.psu.edu/viewdoc/… Je vais y revenir. Cependant, je pense que l’algorithme sera plus explicite et formel.
DaL
3
+1 pour la remarque sur l'optimisation. Depuis qu'il est utilisé dans Machine Learning pour faire de l'optimisation et que l'optimisation est devenue une grosse affaire 40 ou 50 ans avant ML - et les ordinateurs sont également apparus à peu près au même moment - cela semble être une bonne piste.
Wayne
Je ne comprends pas pourquoi vous dites que cette citation décrit SGD.
amibe dit de réintégrer Monica
@ amoeba, espérons que je ne me trompe pas, que je parcourais juste le papier, mais je pensais qu'il décrivait la mise à jour du Perceptron, qui est juste un SGD avec un taux d'apprentissage constant.
user0
3
C'est vrai. Je dis simplement que l'aspect stochastique n'est pas évident dans la citation que vous avez choisie. Je veux dire par "stochastique", GD signifie simplement que les mises à jour sont effectuées échantillon par apprentissage (au lieu de calculer le gradient en utilisant tous les échantillons d'apprentissage disponibles). L'algorithme donné dans en.wikipedia.org/wiki/Perceptron#Steps rend cet aspect "stochastique" immédiatement clair à l'étape 2.
amibe dit de réintégrer Monica