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

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

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

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

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

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

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

В классической статистике задачи минимизации суммы возникают в методе наименьших квадратов и методе максимального правдоподобия (для независимых наблюдений). Общий класс оценок, возникающих в виде минимизации сумм, называется M-оценками[en]. Однако еще в конце XX века было замечено, что требование даже локальной минимизации слишком ограничительно для некоторых задач метода максимального правдоподобия[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] (размера шага): при большом шаге алгоритм может расходиться, а при маленьком — сходимость слишком медленная. Для решения этой проблемы можно использовать расписание скорости обучения[en], при котором скорость обучения убывает с увеличением номера итерации . При этом на первых итерациях значения параметров изменяются значительно, а на более поздних итерациях — только лишь уточняются. Такие расписания известны со времён работы Мак-Куина по кластеризации методом k-средних[13]. Некоторые практические рекомендации по выбору шага в некоторых вариантах SGD даны в секциях 4.4, 6.6 и 7.5 статьи Сполла (2003)[14].

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

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

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

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

где означает скалярное произведение.

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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