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

Алгоритм оптимизации

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

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

Фон

Как статистическая оценка, так и машинное обучение рассматривают задачу минимизации целевой функции , которая имеет форму суммы: где параметр , который минимизируется, должен быть оценен . Каждая функция слагаемого обычно связана с -ым наблюдением в наборе данных (используется для обучения). $${\displaystyle Q(w)={\frac {1}{n}}\sum _{i=1}^{n}Q_{i}(w),}$$ ${\displaystyle w}$ ${\displaystyle Q(w)}$ ${\displaystyle Q_{i}}$ ${\displaystyle i}$

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

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

При использовании для минимизации вышеуказанной функции стандартный (или «пакетный») метод градиентного спуска будет выполнять следующие итерации: Размер шага обозначается (иногда называется скоростью обучения в машинном обучении), а здесь « » обозначает обновление переменной в алгоритме. $${\displaystyle w:=w-\eta \,\nabla Q(w)=w-{\frac {\eta }{n}}\sum _{i=1}^{n}\nabla Q_{i}(w).}$$ ${\displaystyle \eta }$ ${\displaystyle :=}$

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

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

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

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

В стохастическом (или «онлайн») градиентном спуске истинный градиент аппроксимируется градиентом в одной выборке: По мере того, как алгоритм проходит по обучающему набору, он выполняет указанное выше обновление для каждого обучающего образца. Можно сделать несколько проходов по обучающему набору, пока алгоритм не сойдется. Если это сделано, данные можно перемешивать для каждого прохода, чтобы предотвратить циклы. Типичные реализации могут использовать адаптивную скорость обучения , чтобы алгоритм сходился. ^[5] ${\displaystyle Q(w)}$ $${\displaystyle w:=w-\eta \,\nabla Q_{i}(w).}$$

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

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

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

Сходимость стохастического градиентного спуска была проанализирована с использованием теорий выпуклой минимизации и стохастической аппроксимации . Вкратце, когда скорости обучения уменьшаются с соответствующей скоростью и при условии относительно мягких предположений, стохастический градиентный спуск почти наверняка сходится к глобальному минимуму, когда целевая функция выпукла или псевдовыпукла , и в противном случае почти наверняка сходится к локальному минимуму. ^{[2] [7]} Это на самом деле является следствием теоремы Роббинса–Зигмунда. ^[8] ${\displaystyle \eta }$

Линейная регрессия

Предположим, мы хотим подогнать прямую линию к обучающему набору с наблюдениями и соответствующими оценочными ответами с использованием наименьших квадратов . Целевая функция, которая должна быть минимизирована, — это Последняя строка в приведенном выше псевдокоде для этой конкретной задачи станет: Обратите внимание, что на каждом шаге итерации или обновления градиент оценивается только на одном . Это ключевое различие между стохастическим градиентным спуском и пакетным градиентным спуском. ${\displaystyle {\hat {y}}=w_{1}+w_{2}x}$ ${\displaystyle ((x_{1},y_{1}),(x_{2},y_{2})\ldots ,(x_{n},y_{n}))}$ ${\displaystyle ({\hat {y}}_{1},{\hat {y}}_{2},\ldots ,{\hat {y}}_{n})}$ $${\displaystyle 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}.}$$ $${\displaystyle {\begin{bmatrix}w_{1}\\w_{2}\end{bmatrix}}\leftarrow {\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}}.}$$ ${\displaystyle x_{i}}$

В общем случае, если задана задача линейной регрессии , стохастический градиентный спуск ведет себя по-разному при (недопараметризованном) и (перепараметризованном). В случае перепараметризации стохастический градиентный спуск сходится к . То есть SGD сходится к интерполяционному решению с минимальным расстоянием от начального . Это верно даже тогда, когда скорость обучения остается постоянной. В случае недопараметризации SGD не сходится, если скорость обучения остается постоянной. ^[9] ${\displaystyle {\hat {y}}=\sum _{k\in 1:m}w_{k}x_{k}}$ ${\displaystyle m<n}$ ${\displaystyle m\geq n}$ ${\displaystyle \arg \min _{w:w^{T}x_{k}=y_{k}\forall k\in 1:n}\|w-w_{0}\|}$ ${\displaystyle w_{0}}$

История

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

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

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

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

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

Стохастический градиентный спуск — популярный алгоритм для обучения широкого спектра моделей в машинном обучении , включая (линейные) опорные векторные машины , логистическую регрессию (см., например, Vowpal Wabbit ) и графические модели . ^[22] В сочетании с алгоритмом обратного распространения он является фактическим стандартным алгоритмом для обучения искусственных нейронных сетей . ^[23] Его использование также было отмечено в сообществе геофизиков , в частности, для приложений полной инверсии формы волны (FWI). ^[24]

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

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

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

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

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

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

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

Как упоминалось ранее, классический стохастический градиентный спуск, как правило, чувствителен к скорости обучения η . Быстрая сходимость требует больших скоростей обучения, но это может вызвать численную нестабильность. Проблема может быть в значительной степени решена ^[29] путем рассмотрения неявных обновлений , при которых стохастический градиент оценивается на следующей итерации, а не на текущей: $${\displaystyle w^{\text{new}}:=w^{\text{old}}-\eta \,\nabla Q_{i}(w^{\text{new}}).}$$

Это уравнение неявное, поскольку появляется на обеих сторонах уравнения. Это стохастическая форма метода проксимального градиента , поскольку обновление также можно записать как: ${\displaystyle w^{\text{new}}}$ $${\displaystyle w^{\text{new}}:=\arg \min _{w}\left\{Q_{i}(w)+{\frac {1}{2\eta }}\left\|w-w^{\text{old}}\right\|^{2}\right\}.}$$

В качестве примера рассмотрим наименьшие квадраты с признаками и наблюдениями . Мы хотим решить: где указывает на внутренний продукт. Обратите внимание, что может иметь "1" в качестве первого элемента, включающего отсекаемый элемент. Классический стохастический градиентный спуск выполняется следующим образом: ${\displaystyle x_{1},\ldots ,x_{n}\in \mathbb {R} ^{p}}$ ${\displaystyle y_{1},\ldots ,y_{n}\in \mathbb {R} }$ $${\displaystyle \min _{w}\sum _{j=1}^{n}\left(y_{j}-x_{j}'w\right)^{2},}$$ ${\displaystyle x_{j}'w=x_{j1}w_{1}+x_{j,2}w_{2}+...+x_{j,p}w_{p}}$ ${\displaystyle x}$ $${\displaystyle w^{\text{new}}=w^{\text{old}}+\eta \left(y_{i}-x_{i}'w^{\text{old}}\right)x_{i}}$$

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

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

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

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

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

Импульс

Другие предложения включают метод импульса или метод тяжелого шара , который в контексте МО появился в статье Румельхарта , Хинтона и Уильямса об обучении методом обратного распространения ^[30] и заимствовал идею из статьи советского математика Бориса Поляка 1964 года о решении функциональных уравнений. ^[31] Стохастический градиентный спуск с импульсом запоминает обновление Δ w на каждой итерации и определяет следующее обновление как линейную комбинацию градиента и предыдущего обновления: ^{[32] [33]} что приводит к: $${\displaystyle \Delta w:=\alpha \Delta w-\eta \,\nabla Q_{i}(w)}$$ $${\displaystyle w:=w+\Delta w}$$ $${\displaystyle w:=w-\eta \,\nabla Q_{i}(w)+\alpha \Delta w}$$

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

Название импульс происходит от аналогии с импульсом в физике: вектор веса , рассматриваемый как частица, движущаяся через пространство параметров, ^[30] подвергается ускорению из-за градиента потерь (« силы »). В отличие от классического стохастического градиентного спуска, он имеет тенденцию продолжать движение в том же направлении, предотвращая колебания. Импульс успешно использовался компьютерными учеными при обучении искусственных нейронных сетей в течение нескольких десятилетий. ^[34] Метод импульса тесно связан с недодемпфированной динамикой Ланжевена и может быть объединен с имитацией отжига . ^[35] ${\displaystyle w}$

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

Усреднение

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

$${\displaystyle {\bar {w}}={\frac {1}{t}}\sum _{i=0}^{t-1}w_{i}.}$$После завершения оптимизации этот усредненный вектор параметров занимает место w .

АдаГрад

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

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

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

где , градиент, на итерации τ . Диагональ задается как ${\displaystyle g_{\tau }=\nabla Q_{i}(w)}$

$${\displaystyle G_{j,j}=\sum _{\tau =1}^{t}g_{\tau ,j}^{2}.}$$Этот вектор по сути хранит историческую сумму квадратов градиента по измерению и обновляется после каждой итерации. Формула для обновления теперь ^[a] или, записанная как обновления по параметрам, Каждый { G _{( i , i )} } дает масштабирующий коэффициент для скорости обучения, которая применяется к одному параметру w _i . Поскольку знаменатель в этом коэффициенте является ℓ 2 нормой предыдущих производных, экстремальные обновления параметров затухают, в то время как параметры, которые получают мало или небольшие обновления, получают более высокие скорости обучения. ^[34] $${\displaystyle w:=w-\eta \,\mathrm {diag} (G)^{-{\frac {1}{2}}}\odot g}$$ $${\displaystyle w_{j}:=w_{j}-{\frac {\eta }{\sqrt {G_{j,j}}}}g_{j}.}$$ ${\textstyle {\sqrt {G_{i}}}={\sqrt {\sum _{\tau =1}^{t}g_{\tau }^{2}}}}$

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

RMSProp

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

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

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

где, — фактор забывания. Концепция хранения исторического градиента как суммы квадратов заимствована из Adagrad, но «забывание» введено для решения проблемы убывающих скоростей обучения Adagrad в невыпуклых задачах путем постепенного уменьшения влияния старых данных. ^{[ необходима цитата ]} ${\displaystyle \gamma }$

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

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

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

Адам

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

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

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

$${\displaystyle w^{(t+1)}:=w^{(t)}-\eta {\frac {{\hat {m}}_{w}}{{\sqrt {{\hat {v}}_{w}}}+\varepsilon }}}$$где — небольшой скаляр (например, ), используемый для предотвращения деления на 0, а (например, 0,9) и (например, 0,999) — коэффициенты забывания для градиентов и вторых моментов градиентов соответственно. Возведение в квадрат и извлечение квадратного корня выполняется поэлементно. ${\displaystyle \varepsilon }$ ${\displaystyle 10^{-8}}$ ${\displaystyle \beta _{1}}$ ${\displaystyle \beta _{2}}$

Первоначальное доказательство, устанавливающее сходимость Адама, было неполным, и последующий анализ показал, что Адам не сходится для всех выпуклых целей. ^{[43] [44]} Несмотря на это, Адам продолжает использоваться на практике из-за его высокой производительности на практике. ^[45]

Варианты

Популярность Адама вдохновила на множество вариантов и усовершенствований. Вот некоторые примеры:

• Градиенты, усиленные Нестеровым: NAdam , ^[46] FASFA ^[47]
• различные интерпретации информации второго порядка: Powerpropagation ^[48] и AdaSqrt . ^[49]
• Использование бесконечной нормы : AdaMax ^[41]
• AMSGrad ^[50], который улучшает сходимость по сравнению с Adam , используя максимум прошлых квадратов градиентов вместо экспоненциального среднего. ^[51] AdamX ^[52] дополнительно улучшает сходимость по сравнению с AMSGrad .
• AdamW , ^[53], который улучшает снижение веса .

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

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

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

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

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

Стохастический аналог стандартного (детерминированного) алгоритма Ньютона-Рафсона (метод «второго порядка») обеспечивает асимптотически оптимальную или близкую к оптимальной форму итеративной оптимизации в условиях стохастического приближения ^{[ требуется ссылка ]} . Метод, который использует прямые измерения матриц Гессе слагаемых в эмпирической функции риска, был разработан Бердом, Хансеном, Нокедалем и Сингером. ^[56] Однако прямое определение требуемых матриц Гессе для оптимизации может быть невозможно на практике. Практические и теоретически обоснованные методы для версий SGD второго порядка, которые не требуют прямой информации Гессе, приведены Споллом и другими. ^{[57] [58] [59]} (Менее эффективный метод, основанный на конечных разностях вместо одновременных возмущений, приведен Руппертом. ^[60] ) Другой подход к аппроксимационной матрице Гессе заключается в ее замене информационной матрицей Фишера, которая преобразует обычный градиент в естественный. ^[61] Эти методы, не требующие прямой информации Гессе, основаны либо на значениях слагаемых в указанной выше эмпирической функции риска, либо на значениях градиентов слагаемых (т. е. входных данных SGD). В частности, оптимальность второго порядка асимптотически достижима без прямого вычисления матриц Гессе слагаемых в эмпирической функции риска. Когда целью является нелинейная потеря наименьших квадратов , где — предиктивная модель (например, глубокая нейронная сеть ), структура цели может быть использована для оценки информации второго порядка с использованием только градиентов. Полученные методы просты и часто эффективны ^[62] $${\displaystyle Q(w)={\frac {1}{n}}\sum _{i=1}^{n}Q_{i}(w)={\frac {1}{n}}\sum _{i=1}^{n}(m(w;x_{i})-y_{i})^{2},}$$ ${\displaystyle m(w;x_{i})}$

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

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

$${\displaystyle {\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}$

$${\displaystyle \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} }$

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

$${\displaystyle 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},}$$

для , где обозначает интеграл Ито относительно броуновского движения, является более точным приближением в том смысле, что существует константа такая, что $${\displaystyle \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}$

$${\displaystyle \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}.}$$

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

Смотрите также

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

Примечания

1. обозначает поэлементное произведение . ${\displaystyle \odot }$

Ссылки

1. Bottou, Léon ; Bousquet, Olivier (2012). «Торговли крупномасштабным обучением». В Sra, Suvrit; Nowozin, Sebastian; Wright, Stephen J. (ред.). Оптимизация для машинного обучения . Cambridge: MIT Press. стр. 351–368. ISBN 978-0-262-01646-9.
2. Bottou, Léon (1998). "Онлайн-алгоритмы и стохастические аппроксимации". Онлайн-обучение и нейронные сети . Cambridge University Press. ISBN 978-0-521-65263-6.
3. Фергюсон, Томас С. (1982). «Несогласованная оценка максимального правдоподобия». Журнал Американской статистической ассоциации . 77 (380): 831–834. doi :10.1080/01621459.1982.10477894. JSTOR  2287314.
4. Ботту, Леон ; Буске, Оливье (2008). Компромиссы крупномасштабного обучения. Достижения в области нейронных систем обработки информации . Т. 20. С. 161–168.
5. Мерфи, Кевин (2021). Вероятностное машинное обучение: введение. MIT Press . Получено 10 апреля 2021 г.
6. Билмес, Джефф; Асанович, Крсте ; Чин, Чи-Уай; Деммел, Джеймс (апрель 1997 г.). «Использование PHiPAC для ускорения обучения методом обратного распространения ошибок». Международная конференция IEEE по акустике, речи и обработке сигналов 1997 г. ICASSP. Мюнхен, Германия: IEEE. стр. 4153–4156, том 5. doi :10.1109/ICASSP.1997.604861.
7. Kiwiel, Krzysztof C. (2001). «Сходимость и эффективность субградиентных методов для квазивыпуклой минимизации». Математическое программирование, Серия A. 90 ( 1). Берлин, Гейдельберг: Springer: 1–25. doi :10.1007/PL00011414. ISSN  0025-5610. MR  1819784. S2CID  10043417.
8. Роббинс, Герберт ; Зигмунд, Дэвид О. (1971). "Теорема сходимости для неотрицательных почти супермартингалов и некоторые приложения". В Rustagi, Джагдиш С. (ред.). Оптимизирующие методы в статистике . Academic Press. ISBN 0-12-604550-X.
9. Белкин, Михаил (май 2021 г.). «Fit without fear: wonderful matrix phenoms of deep learning through the prism of interpolation». Acta Numerica . 30 : 203–248. arXiv : 2105.14368 . doi : 10.1017/S0962492921000039. ISSN  0962-4929.
10. Роббинс, Х.; Монро, С. (1951). «Метод стохастической аппроксимации». Анналы математической статистики . 22 (3): 400. doi : 10.1214/aoms/1177729586 .
11. Кифер, Дж.; Вулфовиц, Дж. (1952). «Стохастическая оценка максимума функции регрессии». Анналы математической статистики . 23 (3): 462–466. doi : 10.1214/aoms/1177729392 .
12. Розенблатт, Ф. (1958). «Персептрон: вероятностная модель хранения и организации информации в мозге». Psychological Review . 65 (6): 386–408. doi :10.1037/h0042519. PMID  13602029. S2CID  12781225.
13. Билмес, Джефф; Асанович, Крсте ; Чин, Чи-Уай; Деммел, Джеймс (апрель 1997 г.). «Использование PHiPAC для ускорения обучения методом обратного распространения ошибок». Международная конференция IEEE по акустике, речи и обработке сигналов 1997 г. ICASSP. Мюнхен, Германия: IEEE. стр. 4153–4156, том 5. doi :10.1109/ICASSP.1997.604861.
14. Пэн, Синьюй; Ли, Ли; Ван, Фэй-Юэ (2020). «Ускорение мини-пакетного стохастического градиентного спуска с использованием типичной выборки». Труды IEEE по нейронным сетям и системам обучения . 31 (11): 4649–4659. arXiv : 1903.04192 . doi : 10.1109/TNNLS.2019.2957003. PMID  31899442. S2CID  73728964. Получено 02.10.2023 .
15. Rumelhart, David E.; Hinton, Geoffrey E.; Williams, Ronald J. (октябрь 1986 г.). «Изучение представлений с помощью обратного распространения ошибок». Nature . 323 (6088): 533–536. Bibcode :1986Natur.323..533R. doi :10.1038/323533a0. ISSN  1476-4687. S2CID  205001834.
16. Дучи, Джон; Хазан, Элад; Сингер, Йорам (2011). «Адаптивные субградиентные методы для онлайн-обучения и стохастической оптимизации» (PDF) . JMLR . 12 : 2121–2159.
17. Хинтон, Джеффри . "Лекция 6e rmsprop: Разделите градиент на скользящее среднее его недавней величины" (PDF) . стр. 26. Получено 19 марта 2020 г.
18. Кингма, Дидерик; Ба, Джимми (2014). «Адам: Метод стохастической оптимизации». arXiv : 1412.6980 [cs.LG].
19. "torch.optim — документация PyTorch 2.0". pytorch.org . Получено 2023-10-02 .
20. Нгуен, Джанг; Длуголинский, Стефан; Бобак, Мартин; Тран, Вьетнам; Гарсиа, Альваро; Эредиа, Игнасио; Малик, Питер; Глучый, Ладислав (19 января 2019 г.). «Среды и библиотеки машинного обучения и глубокого обучения для крупномасштабного анализа данных: обзор» (PDF) . Обзор искусственного интеллекта . 52 : 77–124. doi : 10.1007/s10462-018-09679-z. S2CID  254236976.
21. "Модуль: tf.keras.optimizers | TensorFlow v2.14.0". TensorFlow . Получено 2023-10-02 .
22. Дженни Роуз Финкель, Алекс Клееман, Кристофер Д. Мэннинг (2008). Эффективный, основанный на признаках, условный случайный анализ полей. Труды Ежегодного собрания ACL.
23. ЛеКун, Янн А. и др. «Эффективное обратное распространение ошибки». Нейронные сети: секреты торговли. Springer Berlin Heidelberg, 2012. 9-48
24. Джером Р. Кребс, Джон Э. Андерсон, Дэвид Хинкли, Рамеш Ниламани, Санвунг Ли, Анатолий Баумштейн и Мартин-Даниэль Лакасс (2009), «Быстрая инверсия сейсмических данных по всему волновому полю с использованием кодированных источников», GEOPHYSICS 74: WCC177-WCC188.
25. Ави Пфеффер. "CS181 Лекция 5 — Персептроны" (PDF) . Гарвардский университет.^{[ постоянная мертвая ссылка ]}
26. Гудфеллоу, Ян ; Бенджио, Йошуа; Курвилль, Аарон (2016). Глубокое обучение. MIT Press. стр. 291. ISBN 978-0262035613.
27. Цитируется по Darken, Christian; Moody, John (1990). Быстрая адаптивная кластеризация k-средних: некоторые эмпирические результаты . Int'l Joint Conf. on Neural Networks (IJCNN). IEEE. doi :10.1109/IJCNN.1990.137720.
28. Сполл, Дж. К. (2003). Введение в стохастический поиск и оптимизацию: оценка, моделирование и управление . Хобокен, Нью-Джерси: Wiley. стр. Разделы 4.4, 6.6 и 7.5. ISBN 0-471-33052-3.
29. Тулис, Панос; Айролди, Эдоардо (2017). «Асимптотические и конечно-выборочные свойства оценщиков, основанных на стохастических градиентах». Annals of Statistics . 45 (4): 1694–1727. arXiv : 1408.2923 . doi : 10.1214/16-AOS1506. S2CID  10279395.
30. Rumelhart, David E.; Hinton, Geoffrey E.; Williams, Ronald J. (8 октября 1986 г.). «Изучение представлений с помощью обратного распространения ошибок». Nature . 323 (6088): 533–536. Bibcode :1986Natur.323..533R. doi :10.1038/323533a0. S2CID  205001834.
31. «Градиентный спуск и импульс: метод тяжелого шара». 13 июля 2020 г.
32. Sutskever, Ilya; Martens, James; Dahl, George; Hinton, Geoffrey E. (июнь 2013 г.). Sanjoy Dasgupta и David McAllester (ред.). On the important of initialization and momentum in deep learning (PDF) . В трудах 30-й международной конференции по машинному обучению (ICML-13). Том 28. Атланта, Джорджия. С. 1139–1147 . Получено 14 января 2016 г.
33. Суцкевер, Илья (2013). Обучение рекуррентных нейронных сетей (PDF) (Ph.D.). Университет Торонто. стр. 74.
34. Zeiler, Matthew D. (2012). "ADADELTA: Метод адаптивной скорости обучения". arXiv : 1212.5701 [cs.LG].
35. Борисенко, Александр; Бышкин, Максим (2021). "CoolMomentum: метод стохастической оптимизации с помощью динамики Ланжевена с имитацией отжига". Scientific Reports . 11 (1): 10705. arXiv : 2005.14605 . Bibcode :2021NatSR..1110705B. doi :10.1038/s41598-021-90144-3. PMC 8139967 . PMID  34021212. 
36. «Документы с кодом — объяснение ускоренного градиента Нестерова».
37. Поляк, Борис Т.; Юдицкий, Анатолий Б. (1992). «Ускорение стохастической аппроксимации путем усреднения» (PDF) . SIAM J. Control Optim . 30 (4): 838–855. doi :10.1137/0330046. S2CID  3548228. Архивировано из оригинала (PDF) 2016-01-12 . Получено 2018-02-14 .
38. Duchi, John; Hazan, Elad; Singer, Yoram (2011). «Адаптивные субградиентные методы для онлайн-обучения и стохастической оптимизации» (PDF) . JMLR . 12 : 2121–2159.
39. Гупта, Майя Р.; Бенджио, Сами; Уэстон, Джейсон (2014). «Обучение высокомультиклассовых классификаторов» (PDF) . JMLR . 15 (1): 1461–1492.
40. Hinton, Geoffrey . "Lecture 6e rmsprop: Разделите градиент на скользящее среднее его недавней величины" (PDF) . стр. 26. Получено 19 марта 2020 г.
41. Kingma, Diederik; Ba, Jimmy (2014). «Адам: Метод стохастической оптимизации». arXiv : 1412.6980 [cs.LG].
42. "4. За пределами градиентного спуска - Основы глубокого обучения [Книга]".
43. Редди, Сашанк Дж.; Кейл, Сатьен; Кумар, Санджив (2018). О конвергенции Адама и за его пределами. 6-я Международная конференция по представлениям обучения (ICLR 2018). arXiv : 1904.09237 .
44. Рубио, Дэвид Мартинес (2017). Анализ сходимости адаптивного метода градиентного спуска (PDF) (магистерская диссертация). Оксфордский университет . Получено 5 января 2024 г.
45. Чжан, Юйшунь; Чэнь, Конлян; Ши, Найчен; Сан, Жоюй; Ло, Чжи-Цюань (2022). «Адам может сходиться без каких-либо изменений в правилах обновления». Достижения в области нейронных систем обработки информации 35 . Достижения в области нейронных систем обработки информации 35 (NeurIPS 2022). arXiv : 2208.09632 .
46. Дозат, Т. (2016). «Включение импульса Нестерова в Адама». S2CID  70293087. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
47. Навин, Филип (2022-08-09). "FASFA: новый оптимизатор обратного распространения ошибки следующего поколения". doi :10.36227/techrxiv.20427852.v1 . Получено 2022-11-19 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
48. Уай, Шварц, Джонатан Джаякумар, Сиддхант М. Паскану, Разван Латам, Питер Э. Тех, Йи (01 октября 2021 г.). Распространение мощности: разреженность, вызывающая перепараметризацию веса. ОСЛК  1333722169.{{cite book}}: CS1 maint: multiple names: authors list (link)
49. Ху, Юйчжэн; Линь, Ликонг; Тан, Шаньгэ (2019-12-20). «Информация второго порядка в методах оптимизации первого порядка». arXiv : 1912.09926 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
50. Редди, Сашанк Дж.; Кале, Сатьен; Кумар, Санджив (2018). «О сближении Адама и за его пределами». arXiv : 1904.09237 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
51. "Обзор алгоритмов оптимизации градиентного спуска". 19 января 2016 г.
52. Тран, Фыонг Тхи; Фонг, Ле Трие (2019). «О доказательстве сходимости AMSGrad и новой версии». IEEE Access . 7 : 61706–61716. arXiv : 1904.03590 . Bibcode : 2019IEEEA...761706T. doi : 10.1109/ACCESS.2019.2916341. ISSN  2169-3536.
53. Лощилов, Илья; Хаттер, Франк (4 января 2019 г.). «Регуляризация распадающегося веса». arXiv : 1711.05101 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
54. Баллес, Лукас; Хенниг, Филипп (15 февраля 2018 г.). «Рассечение Адама: знак, величина и дисперсия стохастических градиентов».
55. «SignSGD: Сжатая оптимизация для невыпуклых задач». 3 июля 2018 г. С. 560–569.
56. Берд, Р. Х.; Хансен, С. Л.; Нокедаль, Дж.; Сингер, И. (2016). «Стохастический квазиньютоновский метод для крупномасштабной оптимизации». Журнал SIAM по оптимизации . 26 (2): 1008–1031. arXiv : 1401.7020 . doi : 10.1137/140954362. S2CID  12396034.
57. Сполл, Дж. К. (2000). «Адаптивная стохастическая аппроксимация методом одновременного возмущения». Труды IEEE по автоматическому управлению . 45 (10): 1839−1853. doi :10.1109/TAC.2000.880982.
58. Сполл, Дж. К. (2009). «Механизмы обратной связи и взвешивания для улучшения оценок Якобиана в адаптивном алгоритме одновременного возмущения». Труды IEEE по автоматическому управлению . 54 (6): 1216–1229. doi :10.1109/TAC.2009.2019793. S2CID  3564529.
59. Бхатнагар, С.; Прасад, Х. Л.; Прашант, Л. А. (2013). Стохастические рекурсивные алгоритмы оптимизации: методы одновременного возмущения . Лондон: Springer. ISBN 978-1-4471-4284-3.
60. Руперт, Д. (1985). «Версия Ньютона-Рафсона многомерной процедуры Роббинса-Монро». Анналы статистики . 13 (1): 236–245. дои : 10.1214/aos/1176346589 .
61. Амари, С. (1998). «Естественный градиент эффективно работает в обучении». Neural Computation . 10 (2): 251–276. doi :10.1162/089976698300017746. S2CID  207585383.
62. Бруст, Дж. Дж. (2021). «Нелинейные наименьшие квадраты для крупномасштабного машинного обучения с использованием стохастических оценок Якобиана». Семинар: Beyond First Order Methods in Machine Learning . ICML 2021. arXiv : 2107.05598 .
63. Ли, Цяньсяо; Тай, Чэн; Э, Вэйнань (2019). «Стохастические модифицированные уравнения и динамика стохастических градиентных алгоритмов I: математические основы». Журнал исследований машинного обучения . 20 (40): 1–47. arXiv : 1811.01558 . ISSN  1533-7928.
64. Гесс, Бенджамин; Кассинг, Себастьян; Конаровский, Виталий (14 февраля 2023 г.). «Стохастические модифицированные потоки, пределы среднего поля и динамика стохастического градиентного спуска». arXiv : 2302.07125 [math.PR].

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

• Ботту, Леон (2004), «Стохастическое обучение», Advanced Lectures on Machine Learning , LNAI, т. 3176, Springer, стр. 146–168, ISBN 978-3-540-23122-6
• Будума, Нихил; Локасио, Николас (2017), «За пределами градиентного спуска», Основы глубокого обучения: разработка алгоритмов машинного интеллекта следующего поколения , O'Reilly, ISBN 9781491925584
• LeCun, Yann A .; Bottou, Léon; Orr, Genevieve B.; Müller, Klaus-Robert (2012), «Эффективное обратное распространение ошибки», Neural Networks: Tricks of the Trade , Springer, стр. 9–48, ISBN 978-3-642-35288-1
• Сполл, Джеймс С. (2003), Введение в стохастический поиск и оптимизацию , Wiley , ISBN 978-0-471-33052-3

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

• «Градиентный спуск, как обучаются нейронные сети». 3Blue1Brown . 16 октября 2017 г. Архивировано из оригинала 22.12.2021 – через YouTube .
• Goh (4 апреля 2017 г.). «Почему Momentum действительно работает». Distill . 2 (4). doi : 10.23915/distill.00006 .Интерактивная статья, объясняющая импульс.