Кто изобрел стохастический градиентный спуск?

36

Я пытаюсь понять историю градиентного спуска и стохастического градиентного спуска . Градиентный спуск был изобретен в Коши в 1847 году. Общий метод решения проблем симуляций . С. 536–538. Подробнее об этом см. здесь .

С тех пор методы градиентного спуска продолжали развиваться, и я не знаком с их историей. В частности меня интересует изобретение стохастического градиентного спуска.

Ссылка, которая может быть использована в академической статье более чем приветствуется.

references gradient-descent history sgd Dal
источник
3
Я узнал о SGD до машинного обучения, так что, должно быть, до всего этого
Аксакал
2
Ну, Коши наверняка изобрел GD до машинного обучения, поэтому я не удивлюсь, что SGC был изобретен и раньше.
DaL
3
Стохастическая аппроксимация Кифера-Вулфовица en.wikipedia.org/wiki/Stochastic_approximation - это большая часть пути, за исключением прямой «симуляции» градиента.
Марк Л. Стоун
3
«Стохастический градиентный спуск» из ML такой же, как «Стохастический субградиентный метод» из выпуклой оптимизации. А субградиентные методы были открыты в 1960-1970 гг. В СССР, г. Москва. Возможно также в США. Я видел видео, где Борис Поляк (он является автором метода тяжелых мячей) сказал, что он (и все люди) начинает думать о методах субградиентов в 1970 году. ( Youtube.com/watch?v=2PcidcPxvyk&t=1963s ) ....
bruziuz

Ответы:

27

Стохастическому градиентному спуску предшествует стохастическая аппроксимация, впервые описанная Роббинсом и Монро в их статье «Метод стохастической аппроксимации» . Кифер и Вулфовиц впоследствии опубликовали свою статью « Стохастическая оценка максимума функции регрессии».что более узнаваемо для людей, знакомых с ML-вариантом стохастической аппроксимации (т.е. стохастическим градиентным спуском), как отметил Марк Стоун в комментариях. В 60-х годах было проведено множество исследований в этом направлении - Дворецкий, Пауэлл, Блум - все опубликованные результаты, которые мы принимаем сегодня как должное. Переход от метода Роббинса и Монро к методу Кифера Вулфовица является относительно небольшим скачком, и это просто переосмысление проблемы, чтобы затем перейти к стохастическому градиентному спуску (для задач регрессии). Вышеупомянутые статьи широко цитируются как предшественники Стохастического градиентного спуска, как упомянуто в этом обзоре Nocedal, Bottou и Curtis , который дает краткую историческую перспективу с точки зрения машинного обучения.

Я полагаю, что Кушнер и Инь в своей книге « Стохастическая аппроксимация и рекурсивные алгоритмы и приложения» предполагают, что это понятие использовалось в теории управления еще в 40-х годах, но я не помню, ссылались ли они на это или это было анекдотично, и у меня нет доступа к их книге, чтобы подтвердить это.

Герберт Роббинс и Саттон Монро . Метод стохастической аппроксимации . Анналы математической статистики. 22, No. 3. (Sep., 1951), pp. 400-407.

Дж. Кифер и Дж. Вулфовиц Стохастическая оценка максимума регрессионной функции Ann. Математика Statist. Том 23, № 3 (1952), 462-466

Леон Ботту и Фрэнк Э. Кертис и Хорхе Ноцедал Методы оптимизации для крупномасштабного машинного обучения , Технический отчет, arXiv: 1606.04838

Дэвид Козак
источник
Можете ли вы дать точные ссылки? А для изобретения SGD, похоже, это в 40-х годах, но не понятно, кто и где?
DaL
Конечно, широко распространено мнение, что это Роббинс и Монро в 1951 году с алгоритмами стохастической аппроксимации . Я слышал, что нечто подобное обнаружилось в литературе по теории управления в 40-х годах (как я уже сказал, я думаю, что у Кушнера и Инь, но у меня нет этой книги под рукой), но кроме этого единственного места, кажется, все цитируют Роббинса и Monro, включая Nocedal et al. ссылка, с которой я связан.
Дэвид Козак
Таким образом, наш ведущий кандидат сейчас - Х. Роббинс и С. Монро. Метод стохастической аппроксимации. Анналы математической статистики, 22 (3): 400–407, 1951 г., как написано в «Носедал», «Ботту» и «Кертис» в pdfs.semanticscholar.org/34dd/…
DaL
Я так называю происхождение SGD, но в кратком изложении (на самом деле абстрактном в современных терминах) написано: «M (x) предполагается, что он является монотонной функцией x, но неизвестен экспериментатору, и это желательно найти решение x = 0 уравнения M (x) = a, где a - заданная постоянная. " Если M (x) неизвестно, его нельзя вывести. Может быть, это еще один древний предок?
Даль
Договорились, в каком-то смысле. Кифер Вулфовиц использовал анализ этого, чтобы придумать свою статью, которая более узнаваема в той форме, которую мы видим сегодня. Как уже упоминалось выше, Марк Стоун. Их документ можно найти здесь: projecteuclid.org/download/pdf_1/euclid.aoms/1177729392 .
Дэвид Козак
14

Видеть

Розенблатт Ф. Перцептрон: вероятностная модель для хранения и организации информации в мозге. Психологический обзор. 1958 ноябрь; 65 (6): 386.

Я не уверен, что SGD был изобретен до этого в литературе по оптимизации - возможно, так и было, - но здесь я полагаю, что он описывает применение SGD для обучения персептрона.

Если система находится в состоянии положительного усиления, то положительные значения AV добавляются к значениям всех активных единиц A в наборах источников «включенных» ответов, тогда как отрицательные значения AV добавляются к активным единицам в источнике. - наборы «выключенных» ответов.

Он называет это «двумя типами подкрепления».

Он также ссылается на книгу об этих "двухвалентных системах".

Розенблатт Ф. Перцептрон: теория статистической отделимости в когнитивных системах (Project Para). Корнельская Авиационная Лаборатория; 1958.

Пользователь0
источник
1
Хороший шаг вперед, спасибо! Я нахожу первую ссылку онлайн здесь citeseerx.ist.psu.edu/viewdoc/… Я пойду по ней. Тем не менее, я ожидаю найти алгоритм более явным и формальным.
DaL
3
+1 за замечание по поводу оптимизации. Поскольку он используется в машинном обучении для оптимизации, а оптимизация стала большой проблемой за 40 или 50 лет до ML - и компьютеры также вошли в картину примерно в то же время - это кажется хорошим лидером.
Уэйн
Я не понимаю, почему вы говорите, что эта цитата описывает SGD.
говорит амеба: восстанови
@amoeba, надеюсь, я не ошибаюсь, просто просматривал статью, но мне показалось, что он описывал обновление персептрона, которое представляет собой SGD с постоянной скоростью обучения.
user0
3
Это верно. Я просто говорю, что стохастический аспект не очевиден из цитаты, которую вы выбрали. Я имею в виду, что «стохастический» GD просто означает, что обновления выполняются по одной обучающей выборке за раз (вместо вычисления градиента с использованием всех доступных обучающих выборок). Алгоритм, приведенный в en.wikipedia.org/wiki/Perceptron#Steps, сразу же проясняет этот «стохастический» аспект на шаге 2.
говорит амеба: восстанови