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

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

Основная идея стохастической аппроксимации восходит к алгоритму Роббинса-Монро 1950-х годов. Сегодня стохастический градиентный спуск стал важным методом оптимизации в машинном обучении .

Предыстория

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

См. также: Уравнение оценки.

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

$$Q(w)={\frac {1}{n}}\sum _{i=1}^{n}Q_{i}(w),$$

где параметр $w$ что сводит к минимуму $Q(w)$подлежит оценке . Каждая слагаемая функция $Q_{i}$ обычно связано с $i$-е наблюдение в наборе данных (используется для обучения).

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

Проблема минимизации суммы также возникает при минимизации эмпирического риска . Там, $Q_{i}(w)$ значение функции потерь при $i$-й пример, и $Q(w)$ эмпирический риск.

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

$$w:=w-\eta \,\nabla Q(w)=w-{\frac {\eta }{n}}\sum _{i=1}^{n}\nabla Q_{i}(w).$$

Размер шага обозначается $\eta$ (иногда называемая скоростью обучения в машинном обучении) и здесь " $:=$«обозначает обновление переменной в алгоритме.

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

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

Итерационный метод

Флуктуации общей целевой функции принимаются в виде ступенек градиента по отношению к мини-партиям.

При стохастическом (или «онлайновом») градиентном спуске истинный градиент $Q(w)$ аппроксимируется градиентом на одной выборке:

$$w:=w-\eta \,\nabla Q_{i}(w).$$

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

В псевдокоде стохастический градиентный спуск можно представить как:

• Выберите исходный вектор параметров $w$ и скорость обучения $\eta$.
• Повторяйте до тех пор, пока не будет получен приблизительный минимум:
  • Случайным образом перетасуйте образцы в обучающем наборе.
  • Для $i=1,2,...,n$, делать:
    • $w:=w-\eta \,\nabla Q_{i}(w).$

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

Сходимость стохастического градиентного спуска анализировалась с использованием теорий выпуклой минимизации и стохастической аппроксимации . Кратко, когда скорость обучения $\eta$уменьшаться с соответствующей скоростью, и при относительно мягких предположениях стохастический градиентный спуск почти наверняка сходится к глобальному минимуму. когда целевая функция выпуклая или псевдовыпуклая , а в противном случае почти наверняка сходится к локальному минимуму. Фактически это следствие теоремы Роббинса-Зигмунда .

Пример

Предположим, мы хотим разместить прямую линию ${\hat {y}}=w_{1}+w_{2}x$ на обучающую выборку с наблюдениями $((x_{1},y_{1}),(x_{2},y_{2})\ldots ,(x_{n},y_{n}))$ и соответствующие предполагаемые ответы $({\hat {y}}_{1},{\hat {y}}_{2},\ldots ,{\hat {y}}_{n})$используя наименьшие квадраты . Целевая функция, которую необходимо минимизировать, равна

$$Q(w)=\sum _{i=1}^{n}Q_{i}(w)=\sum _{i=1}^{n}\left({\hat {y}}_{i}-y_{i}\right)^{2}=\sum _{i=1}^{n}\left(w_{1}+w_{2}x_{i}-y_{i}\right)^{2}.$$

Последняя строка приведенного выше псевдокода для этой конкретной проблемы будет выглядеть так:

$${\begin{bmatrix}w_{1}\\w_{2}\end{bmatrix}}:={\begin{bmatrix}w_{1}\\w_{2}\end{bmatrix}}-\eta {\begin{bmatrix}{\frac {\partial }{\partial w_{1}}}(w_{1}+w_{2}x_{i}-y_{i})^{2}\\{\frac {\partial }{\partial w_{2}}}(w_{1}+w_{2}x_{i}-y_{i})^{2}\end{bmatrix}}={\begin{bmatrix}w_{1}\\w_{2}\end{bmatrix}}-\eta {\begin{bmatrix}2(w_{1}+w_{2}x_{i}-y_{i})\\2x_{i}(w_{1}+w_{2}x_{i}-y_{i})\end{bmatrix}}.$$

Обратите внимание, что на каждой итерации или шаге обновления градиент оценивается только на одном этапе. $x_{i}$. В этом ключевое различие между стохастическим градиентным спуском и пакетным градиентным спуском.

История

В 1951 году Герберт Роббинс и Саттон Монро представили самые ранние методы стохастической аппроксимации, предшествовавшие стохастическому градиентному спуску. Основываясь на этой работе год спустя, Джек Кифер и Джейкоб Вулфовиц опубликовали алгоритм оптимизации, очень близкий к стохастическому градиентному спуску, используя центральные разности в качестве аппроксимации градиента. Позже, в 1950-х годах, Фрэнк Розенблатт использовал SGD для оптимизации своей модели перцептрона , продемонстрировав первую применимость стохастического градиентного спуска к нейронным сетям.

Обратное распространение ошибки было впервые описано в 1986 году, когда стохастический градиентный спуск использовался для эффективной оптимизации параметров нейронных сетей с несколькими скрытыми слоями . Вскоре после этого было разработано еще одно усовершенствование: мини-пакетный градиентный спуск, при котором отдельные выборки заменяются небольшими пакетами данных. В 1997 году были впервые изучены практические преимущества векторизации, достижимые при работе с такими небольшими партиями. прокладывая путь к эффективной оптимизации в машинном обучении. По состоянию на 2023 год этот мини-пакетный подход остается нормой для обучения нейронных сетей, балансируя преимущества стохастического градиентного спуска с градиентным спуском .

К 1980-м годам импульс уже был введен и был добавлен к методам оптимизации SGD в 1986 году. Однако эти методы оптимизации предполагали постоянные гиперпараметры , то есть фиксированную скорость обучения и параметр импульса. В 2010-х годах адаптивные подходы к применению SGD со скоростью обучения по каждому параметру были представлены с помощью AdaGrad (от «Адаптивный градиент») в 2011 году. и RMSprop (для «среднеквадратического распространения») в 2012 году. В 2014 году была опубликована книга «Адам» («Адаптивная оценка момента»), в которой адаптивные подходы RMSprop были применены к импульсу; Затем было разработано множество улучшений и ветвей Адама, таких как Adadelta, Adagrad, AdamW и Adamax.

В рамках машинного обучения в подходах к оптимизации в 2023 году будут доминировать оптимизаторы, основанные на Адаме. TensorFlow и PyTorch, безусловно, самые популярные библиотеки машинного обучения. по состоянию на 2023 год в основном включают только оптимизаторы, производные от Adam, а также предшественников Adam, таких как RMSprop и классический SGD. PyTorch также частично поддерживает BFGS с ограниченной памятью , метод строкового поиска, но только для настроек одного устройства без групп параметров.

Известные приложения

Стохастический градиентный спуск — популярный алгоритм для обучения широкого спектра моделей в машинном обучении , включая (линейные) машины опорных векторов , логистическую регрессию (см., например, Vowpal Wabbit ) и графические модели . В сочетании с алгоритмом обратного распространения ошибки это стандартный алгоритм де-факто для обучения искусственных нейронных сетей . О его использовании также сообщалось в сообществе геофизиков , особенно в приложениях полной инверсии формы волны (FWI).

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

Другой алгоритм стохастического градиентного спуска — это наименьших средних квадратов (LMS) адаптивный фильтр .

Расширения и варианты

Было предложено и использовано множество улучшений базового алгоритма стохастического градиентного спуска. необходимость установки скорости обучения В частности, в машинном обучении проблематичной признана (размера шага). Установка слишком высокого значения этого параметра может привести к расхождению алгоритма; установка слишком низкого значения замедляет сходимость. Концептуально простое расширение стохастического градиентного спуска делает скорость обучения убывающей функцией η _t от номера итерации t , давая график скорости обучения , так что первые итерации вызывают большие изменения параметров, в то время как более поздние производят только точную настройку . Такие графики известны со времен работы МакКуина по k кластеризации -средних . Практическое руководство по выбору размера шага в нескольких вариантах СГД дано Споллом.

График, визуализирующий поведение выбранного набора оптимизаторов с использованием трехмерной перспективной проекции функции потерь f(x, y).

График, визуализирующий поведение выбранного набора оптимизаторов.

Неявные обновления (ISGD)

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

$$w^{\text{new}}:=w^{\text{old}}-\eta \,\nabla Q_{i}(w^{\rm {new}}).$$

Это уравнение является неявным, поскольку $w^{\rm {new}}$появляется в обеих частях уравнения. Это стохастическая форма метода проксимального градиента с момента обновления также можно записать как:

$$w^{\text{new}}:=\arg \min _{w}\left\{Q_{i}(w)+{\frac {1}{2\eta }}\left\|w-w^{\text{old}}\right\|^{2}\right\}.$$

В качестве примера, рассмотреть метод наименьших квадратов с функциями $x_{1},\ldots ,x_{n}\in \mathbb {R} ^{p}$ и наблюдения $y_{1},\ldots ,y_{n}\in \mathbb {R}$. Мы хотим решить:

$$\min _{w}\sum _{j=1}^{n}\left(y_{j}-x_{j}'w\right)^{2},$$

где $x_{j}'w=x_{j1}w_{1}+x_{j,2}w_{2}+...+x_{j,p}w_{p}$указывает на внутренний продукт. Обратите внимание, что $x$может иметь «1» в качестве первого элемента, включающего перехват. Классический стохастический градиентный спуск происходит следующим образом:

$$w^{\text{new}}=w^{\text{old}}+\eta \left(y_{i}-x_{i}'w^{\text{old}}\right)x_{i}$$

где $i$ выборка осуществляется равномерно между 1 и $n$. Хотя теоретическая сходимость этой процедуры происходит при относительно мягких предположениях, на практике процедура может быть весьма нестабильной. В частности, когда $\eta$ указано неверно, так что $I-\eta x_{i}x_{i}'$имеет большие абсолютные собственные значения с высокой вероятностью, процедура может численно расходиться в течение нескольких итераций. Напротив, неявный стохастический градиентный спуск (сокращенно ISGD) можно решить в замкнутой форме как:

$$w^{\text{new}}=w^{\text{old}}+{\frac {\eta }{1+\eta \left\|x_{i}\right\|^{2}}}\left(y_{i}-x_{i}'w^{\text{old}}\right)x_{i}.$$

Эта процедура останется численно стабильной практически для всех $\eta$поскольку скорость обучения теперь нормализована. Такое сравнение классического и неявного стохастического градиентного спуска в задаче наименьших квадратов очень похоже на сравнение между методом наименьших средних квадратов (LMS) и нормализованный фильтр наименьших квадратов (NLMS) .

Несмотря на то, что решение ISGD в замкнутой форме возможно только в методе наименьших квадратов, процедура может быть эффективно реализована в широком диапазоне моделей. В частности, предположим, что $Q_{i}(w)$ зависит от $w$ только за счет линейной комбинации с функциями $x_{i}$, чтобы мы могли написать $\nabla _{w}Q_{i}(w)=-q(x_{i}'w)x_{i}$, где $q()\in \mathbb {R}$ может зависеть от $x_{i},y_{i}$ тоже, но не на $w$ кроме как через $x_{i}'w$. Этому правилу подчиняется метод наименьших квадратов, а также логистическая регрессия и большинство обобщенных линейных моделей . Например, по методу наименьших квадратов $q(x_{i}'w)=y_{i}-x_{i}'w$и в логистической регрессии $q(x_{i}'w)=y_{i}-S(x_{i}'w)$, где $S(u)=e^{u}/(1+e^{u})$логистическая функция . В Пуассона регрессии $q(x_{i}'w)=y_{i}-e^{x_{i}'w}$, и так далее.

В таких условиях ISGD просто реализуется следующим образом. Позволять $f(\xi )=\eta q(x_{i}'w^{old}+\xi \|x_{i}\|^{2})$, где $\xi$является скалярным. Тогда ISGD эквивалентен:

$$w^{\text{new}}=w^{\text{old}}+\xi ^{\ast }x_{i},~{\text{where}}~\xi ^{\ast }=f(\xi ^{\ast }).$$

Масштабный коэффициент $\xi ^{\ast }\in \mathbb {R}$можно найти методом деления пополам , так как в большинстве регулярных моделей, таких как вышеупомянутые обобщенные линейные модели, функция $q()$уменьшается, и, таким образом, границы поиска для $\xi ^{\ast }$ являются $[\min(0,f(0)),\max(0,f(0))]$.

Важно

Дальнейшие предложения включают метод импульса или метод тяжелого шара , который в контексте машинного обучения появился в статье Румельхарта , Хинтона и Уильямса об обучении обратного распространения ошибки. и позаимствовал эту идею из статьи советского математика Бориса Поляка 1964 года о решении функциональных уравнений. Стохастический градиентный спуск с импульсом запоминает обновление Δ w на каждой итерации и определяет следующее обновление как линейную комбинацию градиента и предыдущего обновления:

$$\Delta w:=\alpha \Delta w-\eta \,\nabla Q_{i}(w)$$

$$w:=w+\Delta w$$

это приводит к:

$$w:=w-\eta \,\nabla Q_{i}(w)+\alpha \Delta w$$

где параметр $w$ что сводит к минимуму $Q(w)$ подлежит оценке , $\eta$ — это размер шага (иногда называемый скоростью обучения в машинном обучении) и $\alpha$ — это коэффициент экспоненциального затухания между 0 и 1, который определяет относительный вклад текущего градиента и более ранних градиентов в изменение веса.

Название «импульс» происходит от аналогии с импульсом в физике: весовой вектор. $w$, рассматриваемый как частица, путешествующая через пространство параметров, вызывает ускорение от градиента потерь (« силы »). В отличие от классического стохастического градиентного спуска, он имеет тенденцию продолжать движение в том же направлении, предотвращая колебания. успешно используется учеными-компьютерщиками при обучении искусственных нейронных сетей . Momentum уже несколько десятилетий тесно Метод импульса связан с недостаточно демпфированной динамикой Ланжевена и может сочетаться с моделированием отжига .

модифицировал метод, В середине 1980-х годов Юрий Нестеров чтобы использовать градиент, предсказанный в следующей точке, и полученный в результате так называемый ускоренный градиент Нестерова иногда использовался в машинном обучении в 2010-х годах.

Усреднение

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

$${\bar {w}}={\frac {1}{t}}\sum _{i=0}^{t-1}w_{i}.$$

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

АдаГрад

AdaGrad (алгоритм адаптивного градиента ) — это модифицированный алгоритм стохастического градиентного спуска со скоростью обучения по каждому параметру , впервые опубликованный в 2011 году. Неформально это увеличивает скорость обучения для более редких параметров. и снижает скорость обучения для тех, которые менее редки. Эта стратегия часто улучшает производительность сходимости по сравнению со стандартным стохастическим градиентным спуском в условиях, когда данные разрежены, а разреженные параметры более информативны. Примеры таких приложений включают обработку естественного языка и распознавание изображений.

У него все еще есть базовая скорость обучения η , но она умножается на элементы вектора { G _{j , j} } , который является диагональю внешней произведения. матрицы

$$G=\sum _{\tau =1}^{t}g_{\tau }g_{\tau }^{\mathsf {T}}$$

где $g_{\tau }=\nabla Q_{i}(w)$, градиент, на итерации τ . Диагональ определяется выражением

$$G_{j,j}=\sum _{\tau =1}^{t}g_{\tau ,j}^{2}.$$

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

$$w:=w-\eta \,\mathrm {diag} (G)^{-{\frac {1}{2}}}\odot g$$

или, записанный как обновления для каждого параметра,

$$w_{j}:=w_{j}-{\frac {\eta }{\sqrt {G_{j,j}}}}g_{j}.$$

Каждый { G _{( i , i )} } приводит к коэффициенту масштабирования для скорости обучения, который применяется к одному параметру w _i . Поскольку знаменатель в этом множителе ${\textstyle {\sqrt {G_{i}}}={\sqrt {\sum _{\tau =1}^{t}g_{\tau }^{2}}}}$ является ℓ ₂ нормой предыдущих производных, экстремальные обновления параметров подавляются, в то время как параметры, которые получают мало или небольшие обновления, получают более высокую скорость обучения.

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

РМСПроп

RMSProp (от Root Mean Square Propagation) — метод, изобретенный в 2012 году Джеймсом Мартенсом и Ильей Суцкевером , в то время аспирантами группы Джеффри Хинтона, в котором скорость обучения , как и в Адаграде, адаптирована для каждого из параметров. Идея состоит в том, чтобы разделить скорость обучения для веса на скользящее среднее величин недавних градиентов для этого веса. Необычно то, что оно не было опубликовано в статье, а просто описано в лекции на Coursera .

Итак, сначала рассчитывается скользящее среднее в терминах среднего квадрата,

$$v(w,t):=\gamma v(w,t-1)+\left(1-\gamma \right)\left(\nabla Q_{i}(w)\right)^{2}$$

где, $\gamma$является фактором забывания. Концепция хранения исторического градиента как суммы квадратов заимствована из Адаграда, но «забывание» введено для решения проблемы снижения скорости обучения Адаграда в невыпуклых задачах путем постепенного уменьшения влияния старых данных.

И параметры обновляются как,

$$w:=w-{\frac {\eta }{\sqrt {v(w,t)}}}\nabla Q_{i}(w)$$

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

Адам

Адам (сокращение от Adaptive Moment Estimation) — это обновление 2014 года оптимизатора RMSProp , объединяющее его с основной функцией метода Momentum . В этом алгоритме оптимизации используются текущие средние с экспоненциальным забыванием как градиентов, так и вторых моментов градиентов. Заданные параметры $w^{(t)}$ и функция потерь $L^{(t)}$, где $t$ индексирует текущую итерацию обучения (индексируется по адресу $0$), обновление параметра Адама определяется следующим образом:

$$m_{w}^{(t+1)}\leftarrow \beta _{1}m_{w}^{(t)}+\left(1-\beta _{1}\right)\nabla _{w}L^{(t)}$$

$$v_{w}^{(t+1)}\leftarrow \beta _{2}v_{w}^{(t)}+\left(1-\beta _{2}\right)\left(\nabla _{w}L^{(t)}\right)^{2}$$

$${\hat {m}}_{w}={\frac {m_{w}^{(t+1)}}{1-\beta _{1}^{t}}}$$

$${\hat {v}}_{w}={\frac {v_{w}^{(t+1)}}{1-\beta _{2}^{t}}}$$

$$w^{(t+1)}\leftarrow w^{(t)}-\eta {\frac {{\hat {m}}_{w}}{{\sqrt {{\hat {v}}_{w}}}+\epsilon }}$$

где $\epsilon$ небольшой скаляр (например, $10^{-8}$) используется для предотвращения деления на 0, и $\beta _{1}$ (например, 0,9) и $\beta _{2}$(например, 0,999) являются коэффициентами забывания для градиентов и вторых моментов градиентов соответственно. Возведение в квадрат и извлечение квадратного корня выполняется поэлементно.

Первоначальное доказательство, устанавливающее сходимость Адама, было неполным, и последующий анализ показал, что Адам не сходится для всех выпуклых целей. Несмотря на это, Адам продолжает использоваться на практике из-за его высоких показателей на практике. Более того, глубокое влияние этого алгоритма вдохновило множество новых, менее известных схем оптимизации на основе импульса с использованием градиентов, улучшенных Нестеровым (например: NAdam и ФАСФА ) и различные интерпретации информации второго порядка (например: Распространение мощности и АдаСкрт ). Однако наиболее часто используемые варианты — AdaMax , который обобщает Адама, используя норму бесконечности, и AMSGrad , который решает проблемы сходимости Адама, используя максимум прошлых квадратов градиентов вместо экспоненциального среднего. АдамВ — это более позднее обновление, которое смягчает неоптимальный выбор алгоритма уменьшения веса в Adam .

Знаковый

Несмотря на то, что знаковая оптимизация восходит к вышеупомянутому Rprop, в 2018 году исследователи попытались упростить Адама, исключив из учета величину стохастического градиента и рассматривая только его знак.

Поиск строки с возвратом

Поиск линии с возвратом — еще один вариант градиентного спуска. Все нижеприведенное взято из упомянутой ссылки. Он основан на условии, известном как условие Армихо – Гольдштейна. Оба метода позволяют изменять скорость обучения на каждой итерации; однако способ изменения различен. Поиск по строке с возвратом использует оценки функций для проверки состояния Армихо, и в принципе цикл в алгоритме определения скорости обучения может быть длинным и заранее неизвестным. Адаптивному SGD не нужен цикл определения скорости обучения. С другой стороны, адаптивный SGD не гарантирует «свойства спуска», которым обладает поиск по строке с возвратом, а именно: $f(x_{n+1})\leq f(x_{n})$для всех н. Если градиент функции стоимости является глобально липшицевым, с константой Липшица L, а скорость обучения выбрана порядка 1/L, то стандартная версия SGD является частным случаем поиска прямой с возвратом.

Методы второго порядка

Стохастический аналог стандартного (детерминированного) алгоритма Ньютона – Рафсона (метод «второго порядка») обеспечивает асимптотически оптимальную или почти оптимальную форму итеративной оптимизации в условиях стохастической аппроксимации. . Метод, использующий прямые измерения матриц Гессиана слагаемых эмпирической функции риска, был разработан Бердом, Хансеном, Носедалем и Сингером. Однако прямое определение необходимых для оптимизации матриц Гессе на практике может оказаться невозможным. Практические и теоретически обоснованные методы для версий SGD второго порядка, которые не требуют прямой информации о гессиане, предложены Споллом и другими. (Менее эффективный метод, основанный на конечных разностях, а не на одновременных возмущениях, предложен Рупертом. ) Другой подход к аппроксимации матрицы Гессе заключается в замене ее информационной матрицей Фишера, которая преобразует обычный градиент в естественный. Эти методы, не требующие прямой информации о гессиане, основаны либо на значениях слагаемых в приведенной выше эмпирической функции риска, либо на значениях градиентов слагаемых (т. е. входных данных SGD). В частности, оптимальность второго порядка асимптотически достижима без прямого вычисления матриц Гессе слагаемых эмпирической функции риска.

Приближения в непрерывном времени

Для небольшой скорости обучения ${\textstyle \eta }$ стохастический градиентный спуск ${\textstyle (w_{n})_{n\in \mathbb {N} _{0}}}$ можно рассматривать как дискретизацию градиентного потока ОДУ

$${\frac {d}{dt}}W_{t}=-\nabla Q(W_{t})$$

подвержен дополнительному стохастическому шуму. Это приближение справедливо только на конечном временном горизонте в следующем смысле: предположим, что все коэффициенты ${\textstyle Q_{i}}$достаточно гладкие. Позволять ${\textstyle T>0}$ и ${\textstyle g:\mathbb {R} ^{d}\to \mathbb {R} }$быть достаточно гладкой пробной функцией. Тогда существует константа ${\textstyle C>0}$ такой, что для всех ${\textstyle \eta >0}$

$$\max _{k=0,\dots ,\lfloor T/\eta \rfloor }\left|\mathbb {E} [g(w_{k})]-g(W_{k\eta })\right|\leq C\eta ,$$

где ${\textstyle \mathbb {E} }$ означает принятие математического ожидания относительно случайного выбора индексов в схеме стохастического градиентного спуска.

Поскольку это приближение не учитывает случайные колебания среднего поведения стохастического градиентного спуска, решения стохастических дифференциальных уравнений (СДУ) были предложены в качестве ограничивающих объектов. Точнее, решение СДУ

$$dW_{t}=-\nabla \left(Q(W_{t})+{\tfrac {1}{4}}\eta |\nabla Q(W_{t})|^{2}\right)dt+{\sqrt {\eta }}\Sigma (W_{t})^{1/2}dB_{t},$$

для

$$\Sigma (w)={\frac {1}{n^{2}}}\left(\sum _{i=1}^{n}Q_{i}(w)-Q(w)\right)\left(\sum _{i=1}^{n}Q_{i}(w)-Q(w)\right)^{T}$$

где ${\textstyle dB_{t}}$ обозначает интеграл Ито по броуновскому движению, является более точным приближением в том смысле, что существует постоянная ${\textstyle C>0}$ такой, что

$$\max _{k=0,\dots ,\lfloor T/\eta \rfloor }\left|\mathbb {E} [g(w_{k})]-\mathbb {E} [g(W_{k\eta })]\right|\leq C\eta ^{2}.$$

Однако это СДУ лишь аппроксимирует одноточечное движение стохастического градиентного спуска. Для аппроксимации стохастического потока приходится рассматривать СДУ с бесконечномерным шумом.

См. также

• Поиск строки с возвратом
• Нарушенный закон нейронного масштабирования
• Спуск по координатам — меняет по одной координате за раз, а не по одному примеру.
• Линейный классификатор
• Машинное обучение онлайн
• Стохастическое восхождение на холм
• Стохастическое уменьшение дисперсии

Дальнейшее чтение

• Ботту, Леон (2004), «Стохастическое обучение» , Лекции продвинутого уровня по машинному обучению , LNAI, vol. 3176, Спрингер, стр. 146–168, ISBN.  978-3-540-23122-6
• Будума, Нихил; Локасио, Николас (2017), «За пределами градиентного спуска» , «Основы глубокого обучения: разработка алгоритмов машинного интеллекта следующего поколения» , О'Рейли, ISBN  9781491925584
• ЛеКун, Янн А .; Ботту, Леон; Орр, Женевьева Б.; Мюллер, Клаус-Роберт (2012), «Эффективное BackProp» , «Нейронные сети: хитрости» , Springer, стр. 9–48, ISBN  978-3-642-35288-1
• Сполл, Джеймс К. (2003), Введение в стохастический поиск и оптимизацию , Wiley , ISBN  978-0-471-33052-3

Внешние ссылки

• Использование стохастического градиентного спуска в C++, Boost, Ublas для линейной регрессии
• Алгоритмы машинного обучения
• «Градиентный спуск, как обучаются нейронные сети» . 3Синий1Коричневый . 16 октября 2017 г. Архивировано из оригинала 22 декабря 2021 г. – на YouTube .
• Го (4 апреля 2017 г.). «Почему импульс действительно работает» . Дистиллировать . 2 (4). дои : 10.23915/distill.00006 . Интерактивный документ, объясняющий импульс.