Стохастический градиентный спуск

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Стохастический градиентный спуск (англ. Stochastic gradient descent, SGD) — это метод итерации для оптимизации целевой функции с подходящими свойствами гладкости (например, дифференцируемость или субдифференцируемость). Его можно расценивать как стохастическую аппроксимацию оптимизации методом градиентного спуска, поскольку он заменяет реальный градиент (вычисленный из полного набора данных[en]) путём оценки такового (вычисленного из случайно выбранного подмножества данных)[1]. Особенно в приложениях обработки больших данных это сокращает вычислительные ресурсы, достигая более быстрые итерации в обмен на более низкую скорость сходимости[2].

Хотя базовую идею стохастической аппроксимации можно отследить назад к алгоритму Роббинса — Монро[en] 1950-х годов[3], стохастический градиентный спуск стал важным оптимизационном методом в машинном обучении[1].

Предпосылки[править | править код]

Основная статья: M-оценка

И статистическая оценка[en], и машинное обучение рассматривают задачу минимизации целевой функции, имеющей форму суммы

где параметр , минимизирующий , следует оценить. Каждый член суммы обычно ассоциируется с -ым наблюдением[en] в наборе данных[en] (использованном для обучения).

В классической статистике задачи минимизации суммы возникают в методе наименьших квадратов и методе максимального правдоподобия (для независимых наблюдений). Общий класс оценок, возникающих в виде минимизации сумм называется M-оценками[en]. Однако, в статистике давно признали, что требование даже локальной минимизации слишком ограничительно для некоторых задач метода максимального правдоподобия[4]. Поэтому современные теоретики-статистики часто рассматривают стационарные точки функции правдоподобия (или нули её производной, функцию количественной оценки[en] и другие методы оценочных уравнений[en]).

Задача минимизации суммы возникает также при минимизации эмпирического риска. В этом случае является значением функции потерь на -ом примере, а является эмпирическим риском.

Когда используется для минимизации вышеприведённой функции, стандартный (или «пакетный») метод градиентного спуска осуществляет следующие итерации

где является размером шага (называемого скоростью обучения[en] при обучении машин).

Во многих случаях суммируемые функции имеют простую форму, что позволяет осуществить малозатратные вычисления для суммы функций и градиента суммы. Например, в статистике однопараметрические экспоненциальные семейства[en] позволяют экономичное вычисление функции и градиента.

Однако, в других случаях, вычисление градиента суммы может потребовать дорогих вычислений градиентов для всех суммируемых функций. Когда тренировочное множество огромно и нет простых формул, вычисление сумм градиентов становится очень дорогим, поскольку вычисление градиента суммы требует вычисления градиентов отдельных членов суммы. Чтобы сэкономить на вычислениях на каждой итерации, стохастический градиентный спуск отбирает подмножество суммируемых функций на каждом шаге алгоритма. Это очень эффективный подход в случае больших задач при обучении машин[5].

Итеративный метод[править | править код]

Флуктуации целевой функции по мере работы алгоритма

В стохастическом (или «онлайновом») градиентном спуске истинный градиент аппроксимируется градиентом одного тренировочного примера

Пробегая через тренировочное множество, алгоритм осуществляет приведённый выше пересчёт для каждого тренировочного примера. Через тренировочный набор может быть осуществлено несколько проходов, прежде чем алгоритм сойдётся. Если такие проходы происходят, данные перетряхиваются перед каждым проходом, чтобы избежать зацикливания. Типичные реализации могут использовать адаптивную скорость обучения[en], чтобы алгоритм сходился.

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

  • Выбираем начальный вектор параметров и скорость обучения .
  • Повторяем пока не получим приблизительный минимум:
    • Случайным образом тасуем примеры в тренировочном множестве.
    • Для выполняем

Компромиссом между вычислением истинного градиента и градиента по одному тренировочному примеру может быть вычисление градиента по более чем одному тренировочному примеру (называемому «минипакетом») на каждом шаге. Это может быть существенно лучше, чем описанный «истинный» стохастический градиентный спуск, поскольку код может использовать библиотеки векторных форм[en], а не вычислять каждый шаг отдельно. Это может также привести к более гладкой сходимости, так как градиент, вычисляемый на каждом шаге, усредняется по большему числу тренировочных примеров.

Сходимость стохастического градиентного спуска анализировалась с помощью теорий выпуклой минимизации и стохастической аппроксимации. Если коротко, когда скорости обучения[en] убывают с подходящей скоростью, с учётом относительно слабых предположений, стохастический градиентный спуск сходится почти наверняка к глобальному минимуму, если целевая функция выпукла или псевдовыпукла, в противном случае метод сходится почти наверняка к локальному минимуму[6][7]. Фактически, это следствие теоремы Роббинса — Сигмунда[8].

Пример[править | править код]

Предположим, что мы хотим подогнать прямую под тренировочный набор с множеством наблюдений и соответствующих ответов с помощью метода наименьших квадратов. Целевой функцией для минимизации будет

Последняя строка в вышеприведённом псевдокоде для задачи превращается в

Заметим, что на каждой итерации (которая называется также пересчётом), вычисляется только градиент в одной точке вместо вычисления на множестве всех выборок.

Ключевое различие по сравнению со стандартным (пакетным) градиентным спуском в том, что только одна часть данных из всего множества используется на каждом шаге и эта часть выбирается на каждом шаге случайно.

Известные приложения[править | править код]

Стохастический градиентный спуск является популярным алгоритмом для обучения широкого ряда моделей в обучении машин, в частности в (линейном) методе опорных векторов, в логистической регрессии (см. например, Vowpal Wabbit[en]) и в графовых вероятностных моделях[9]. Когда метод комбинируется с алгоритмом обратного распространения ошибки, он является де факто стандартным алгоритмом для обучения искусственных нейронных сетей[10]. Его применение было также замечено в геофизическом сообществе, особенно для приложений Full Waveform Inversion (FWI)[11].

Стохастический градиентный спуск конкурирует с алгоритмом L-BFGS[en], который также широко используется. Стохастический градиентный спуск использовался по меньшей мере с 1960 года для обучения моделей линейной регрессии под именем ADALINE[en][12].

Другой стохастический алгоритм градиентного спуска является адаптивным фильтром наименьших квадратов[en] (англ. least mean squares adaptive filter, LMS)]].

Расширения и варианты[править | править код]

Было предложено много улучшений для базового стохастического алгоритма градиентного спуска. В частности, при обучении машин необходимость установки скорости обучения[en] (размера шага) была признана проблематичной. Установка этого параметра слишком высоким может привести алгоритм к отсутствию сходимости. Установка же слишком низким приводит к медленной сходимости. Концептуально простое расширение стохастического градиентного спуска делает скорость обучения убывающей функцией от номера итерации t, что задаёт расписание скорости обучения, так что первые итерации вызывают большие изменения параметров, а более поздние приводят только к уточнениям. Такие расписания известны со времени работы Маккуина о кластеризации по k-средним[13]. Некоторые практические рекомендации по выбору шага в некоторых вариантах SGD даны в секциях 4.4, 6.6 и 7.5 статьи Спола (2003)[14].

Не выраженные явно изменения (ISGD)[править | править код]

Как упомянуто ранее, классический стохастический градиентный спуск обычно чувствителен к скорости обучения[en] . Быстрая сходимость требует быстрой большой скорости обучения, но это может вызвать численную нестабильность. Задача может быть главным образом решена[15] путём рассмотрения неявного изменения, когда стохастический градиент пересчитывается на следующей итерации, а не на текущей

Это равенство неявное, поскольку появляется на обеих сторонах равенства. Это стохастическая форма проксимального градиентного метода[en], поскольку пересчёт может быть выражен в виде

В качестве примера рассмотрим метод наименьших квадратов со свойствами и наблюдениями . Мы хотим решить:

где означает скалярное произведение. Заметим, что может иметь "1" в качестве первого элемента. Классический стохастический градиентный спуск работает следующим образом

где равномерно распределено между 1 и . Хотя теоретически эта процедура сходится при относительно мягких предположениях, на практике процедура может оказаться сильно нестабильной. В частности, если неверно задана, то имеют большие абсолютные собственные значения с большой вероятностью и процедура может расходиться за несколько итераций. Для контраста, явный стохастический градиентный спуск (англ. implicit stochastic gradient descent, ISGD) может быть выражен в виде формулы

Процедура будет оставаться численно стабильной виртуально для всех , поскольку скорость обучения[en] теперь нормализована. Такое сравнение между классическим и явным стохастическим градиентным спуском в методе наименьших квадратов очень похоже на сравнение между фильтром наименьших квадратов[en] (англ. least mean squares, LMS) и нормированным фильтром наименьших квадратов[en] (англ. normalized least mean squares filter, NLMS).

Хотя решение в аналитическом виде для ISGD возможно только в методе наименьших квадратов, процедуру можно эффективно реализовать в широкий ряд моделей. В частности, предположим, что зависит от только как линейная комбинация свойств , так что мы можем записать , где может зависеть от , но не от непосредственно, лишь через . Метод наименьших квадратов удовлетворяет этому условию, а потому удовлетворяют этому условию does логистическая регрессия и большинство обобщённых линейных моделей. Например, в методе наименьших квадратов , а в логистической регрессии , где является логистической функцией. В регрессии Пуассона[en] , и так далее.

В таких условия ISGD легко реализовать следующим образом. Пусть , где является числом. Тогда ISGD эквивалентен

Масштабный множитель можно найти методом деления отрезка пополам, поскольку в большинстве моделей, таких как вышеупомянутые обобщённые линейные модели, функция убывает, а тогда границами поиска для будут .

Импульс[править | править код]

Более поздние разработки включают метод импульса, который появился в статье Румельхарта, Хинтона и Уильямса об обучении с обратным распространением ошибки[16]. Стохастический градиентный спуск с импульсом запоминает изменение на каждой итерации и определяет следующее изменение в виде линейной комбинации градиента и предыдущего изменения[17][18]:

что приводит к

где параметр , который минимизирует , следует оценить, а является размером шага (иногда называемая скоростью обучения[en] при обучении машин.

Название «импульс» берёт начало от импульса в физике — вектор весов , понимаемый как трасса частицы по пространству параметров[16], испытывает ускорение от градиента функции потерь («силы»). В отличие от классического стохастического градиентного спуска, метод пытается сохранить продвижение в том же направлении, предотвращая колебания. Импульс использовался успешно специалистами по информатике для обучения искусственных нейронных сетей в течение нескольких десятилетий[19].

Усреднение[править | править код]

Усреднённый стохастический градиентный спуск, разработанный независимо Руппертом и Поляком в конце 1980-х годов, является обычным стохастическим градиентным спуском, который записывает среднее вектора параметров. То есть пересчёт тот же, что и в обычном методе стохастического градиентного спуска, но алгоритм также отслеживает[20].

.

Когда оптимизация завершена, вектор средних параметров занимает место w.

AdaGrad[править | править код]

AdaGrad (адаптивный градиентный алгоритм, англ. adaptive gradient algorithm) является модификацией стохастического алгоритма градиентного спуска с отдельной для каждого параметра скоростью обучения[en]. Алгоритм был опубликован в 2011[21][22]. Неформально, это увеличивает скорость обучения для параметров с редкими данными и уменьшает скорость обучения для параметров с менее редкими. Эта стратегия увеличивает скорость сходимости по сравнению со стандартным стохастическим методом градиентного спуска в условиях, когда данные редки и соответствующие параметры более информативны. Примерами таких приложения являются обработка естественных языков и распознавание образов[21]. Алгоритм имеет базовую скорость обучения , но она умножается на элементы вектора , который является диагональю матрицы внешнего произведения

где , градиент на итерации . Диагональ задаётся выражением

.

Этот вектор обновляется после каждой итерации. Формула пересчёта

[a]

или, записывая как пересчёт по параметрам,

Каждый элемент даёт множитель для скорости обучения, применяемый к одному параметру . Поскольку знаменатель в этом множителе, , является нормой 2 предыдущей производной, большие изменения параметра ослабляются, в то время как параметры, получающие малые изменения получают более высокие скорости обучения[19].

Хотя алгоритм разрабатывался для выпуклых задач, AdaGrad успешно применяется для невыпуклой оптимизации[23].

RMSProp[править | править код]

RMSProp (от англ. Root Mean Square Propagation) — это метод, в котором скорость обучения[en] настраивается для каждого параметра. Идея заключается в делении скорости обучения для весов на сгруппированные средние значения недавних градиентов для этого веса[24]. Таким образом, первое сгруппированное среднее вычисляется в терминах среднеквадратичного

где, является коэффициентом забывания.

Параметры обновляются как

RMSProp показал прекрасную адаптацию скорости обучения в различных приложениях. RMSProp можно рассматривать как обобщение Rprop[en] и метод способен работать с минипакетами, а не только с полными пакетами [25].

Adam[править | править код]

Adam[26] (сокращение от «метод Адаптивной Оценки Моментов», англ. Adaptive Moment Estimation) — это обновление RMSProp оптимизатора. В этом оптимизационном алгоритме используются сгруппированные средние как градиентов, так и вторых моментов градиентов. Если даны параметры , а функция потерь , где отражает индекс текущей итерации (отчёт начинается с ), пересчёт параметра алгоритмом Adam задаётся формулами

где является малой добавкой, используемой для предотвращения деления на 0, а и являются коэффициентами забывания для градиентов и вторых моментов градиентов соответственно. Возведение в квадрат и квадратный корень вычисляются поэлементно.

Естественный градиентный спуск и kSGD[править | править код]

Основанный на фильтре Калмана стохастический градиентный спуск (англ. Kalman-based Stochastic Gradient Descent, kSGD)[27] является онлайновым и офлайновым алгоритмом для параметров обучения для статистических задач для моделей квазиправдоподобия[en], куда входят линейные модели, нелинейные модели, обобщённые линейные модели, и нейронные сети с среднеквадратичными потерями[en] как специальный случай. Для онлайновых задач обучения kSGD является специальным случаем фильтра Калмана для задач линейной регрессии, специальный случай расширенного фильтра Калмана[en] для задач нелинейной регрессии и может рассматриваться как инкрементальный метод Гаусса — Ньютона. Более того, ввиду связи kSGD с фильтром Калмана и связи естественного градиентного спуска[28] с фильтром Калмана[29], kSGD является серьёзным улучшение популярного естественного метода градиентного спуска.

Преимущества kSGD по сравнению с другими методами

(1) Он нечувствителен к числу условий задачи,[b]
(2) он имеет робастный выбор гиперпараметров
(3) он имеет условие останова.

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

Для описания алгоритма предположим, что , где , определена так что

где функция усреднения (то есть ожидаемое значение от ), а является функцией дисперсии (то есть дисперсия для ). Тогда, пересчёт параметра и пересчёт ковариантной матрицы задаётся следующими выражениями

где являются гиперпараметрами. Пересчёт может привести к тому, что ковариантная матрица станет неопределённой, что можно избежать за счёт умножения матрицы на матрицу. может быть любой положительно определённой симметричной матрицей, но обычно берётся единичная матрица. Как заметил Патель[27], для всех задач, не считая линейной регрессии, требуются повторные прогоны для обеспечения сходимости алгоритма, но не приведены теоретические детали или детали реализации. В тесно связанном офлайновом мультипакетном методе для нелинейной регрессии, проанализированным Бертсекасом[30], для доказательства сходимости использовался коэффициент забывания при пересчёте ковариантной матрицы.

Методы второго порядка[править | править код]

Известно, что стохастический аналог стандартного (детерминированного) алгоритма Ньютона — Рэпсона (метод «второго порядка») даёт асимптотически оптимальное или почти оптимальный вид итеративной оптимизации в условиях стохастической аппроксимации. Метод, который использует прямое вычисление матриц Гессе членов суммы в эмпирической функции риска, разрабатывали Бёрд, Хансен, Носедаль и Сингер[31]. Однако, прямое определение требующихся матриц Хессе для оптимизации может оказаться невозможным на практике. Практические и теоретически выглядящие методы для версии второго порядка алгоритма SGD, который не требует прямой информации о гессиане, дали Сполл и другие[32][33][34] (Менее эффективный метод, основанный на конечных разностях вместо одновременного пересчёта, дал Рупперт[35]). Эти методы, не требуя напрямую информацию о гессиане, базируются либо на значениях членов суммы в эмпирической функции риска, приведённой выше, либо значениях градиентов членов суммы (то есть ввода SGD). В частности, оптимальность второго порядка асимптотически достижима без непосредственного вычисления матриц Гессе членов суммы в эмпирической функции риска.

Комментарии[править | править код]

  1. является поэлементным произведением.
  2. Для задачи линейной регрессии, kSGD's отклонение целевой функции (то есть полная ошибка и дисперсия) на итерации равно с вероятностью, стремящейся к 1 со скоростью, зависящей от , где является дисперсией остатков. Более того, для конкретного выбора , может быть показано, что kSGD's отклонение целевой функции на итерации равно с вероятностью, стремящейся к 1 со скоростью, зависящей от , где является оптимальным параметром.

См. также[править | править код]

Примечания[править | править код]

  1. 1 2 Taddy, 2019, с. 303–307.
  2. Bottou, Bousquet, 2012, с. 351–368.
  3. Mei, 2018, с. E7665–E7671.
  4. Ferguson, 1982, с. 831–834.
  5. Bottou, Bousquet, 2008, с. 161–168.
  6. Bottou, 1998.
  7. Kiwiel, 2001, с. 1–25.
  8. Robbins, Siegmund, 1971.
  9. Finkel, Kleeman, Manning, 2008.
  10. LeCun и др., 2012, с. 9-48.
  11. Díaz, Guitton, 2011, с. 2804-2808.
  12. Avi Pfeffer. CS181 Lecture 5 — Perceptrons (Harvard University). (недоступная ссылка)
  13. Darken, Moody, 1990.
  14. Spall, 2003.
  15. Toulis, Airoldi, 2017, с. 1694–1727.
  16. 1 2 Rumelhart, Hinton, Williams, 1986, с. 533–536.
  17. Sutskever, Martens, Dahl, Hinton, 2013, с. 1139–1147.
  18. Sutskever, Ilya (2013). Training recurrent neural networks (PDF) (Ph.D.). University of Toronto.
  19. 1 2 Matthew D. Zeiler (2012), ADADELTA: An adaptive learning rate method, arΧiv:1212.5701 [cs.LG] 
  20. Polyak, Juditsky, 1992, с. 838–855.
  21. 1 2 Duchi, Hazan, Singer, 2011, с. 2121–2159.
  22. Joseph Perla (2014). Notes on AdaGrad (недоступная ссылка). Дата обращения: 1 марта 2020. Архивировано 30 марта 2015 года.
  23. Gupta, Bengio, Weston, 2014, с. 1461–1492.
  24. Tieleman, Tijmen and Hinton, Geoffrey (2012). Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning
  25. Hinton, Geoffrey Overview of mini-batch gradient descent 27–29. Дата обращения: 27 сентября 2016.
  26. Kingma Diederik, Jimmy Ba (2014), Adam: A method for stochastic optimization, arΧiv:1412.6980 [cs.LG] 
  27. 1 2 Patel, 2016, с. 2620–2648.
  28. Cichocki, Chen, Amari, 1997, с. 1345–1351.
  29. Ollivier Yann (2017), Online Natural Gradient as a Kalman Filter, arΧiv:1703.00209 [stat.ML] 
  30. Bertsekas, 1996, с. 807–822.
  31. Byrd, Hansen, Nocedal, Singer, 2016, с. 1008–1031.
  32. Spall, 2000, с. 1839−1853.
  33. Spall, 2009, с. 1216–1229.
  34. Bhatnagar, Prasad, Prashanth, 2013.
  35. Ruppert, 1985, с. 236–245.

Литература[править | править код]

Литература для дальнейшего чтения[править | править код]

Ссылки[править | править код]