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

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

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

Предпосылки

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

См. также: Метод оценочных уравнений

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

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

где параметр ${\displaystyle w}$, минимизирующий ${\displaystyle Q(w)}$, следует оценить. Каждый член суммы ${\displaystyle Q_{i}}$ обычно ассоциируется с ${\displaystyle i}$-ым наблюдением^[англ.] в наборе данных, использованном для обучения.

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

Задача минимизации суммы возникает также при минимизации эмпирического риска. В этом случае ${\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 }$ является размером шага, называемым скоростью обучения^[англ.] в машинном обучении.

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

Однако в других случаях вычисление градиента суммы может потребовать дорогих расчетов градиентов для всех суммируемых функций. На большом тренировочном множестве в отсутствие простых формул вычисление сумм градиентов становится очень дорогим, поскольку вычисление градиента суммы требует вычисления градиентов отдельных членов суммы. Для уменьшения объема вычислений стохастический градиентный спуск отбирает подмножество суммируемых функций на каждой итерации алгоритма. Этот подход особенно эффективен для больших задач машинного обучения^[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).}$

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

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

Пример

Предположим, что мы хотим приблизить прямую ${\displaystyle {\hat {y}}=\!w_{1}+w_{2}x}$ тренировочным набором с множеством наблюдений ${\displaystyle (x_{1},x_{2},\ldots ,x_{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}}:={\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}}$ вместо вычисления на множестве всех выборок.

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

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

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

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

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

Разновидности и модификации

Существует множество модификаций алгоритма стохастического градиентного спуска. В частности, в машинном обучении проблемой является выбор скорости обучения^[англ.] (размера шага): при большом шаге алгоритм может расходиться, а при маленьком — сходимость слишком медленная. Для решения этой проблемы можно использовать расписание скорости обучения^[англ.], при котором скорость обучения ${\displaystyle \eta _{t}}$ убывает с увеличением номера итерации ${\displaystyle t}$. При этом на первых итерациях значения параметров изменяются значительно, а на более поздних итерациях — только лишь уточняются. Такие расписания известны со времён работы Мак-Куина по кластеризации методом k-средних^[13]. Некоторые практические рекомендации по выбору шага в некоторых вариантах SGD даны в секциях 4.4, 6.6 и 7.5 статьи Сполла (2003)^[14].

Не выраженные явно изменения (ISGD)

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

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

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

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

В качестве примера рассмотрим метод наименьших квадратов со свойствами ${\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}(y_{j}-x_{j}'w)^{2},}$

где ${\displaystyle x_{j}'w=x_{j1}w_{1}+x_{j,2}w_{2}+...+x_{j,p}w_{p}}$ означает скалярное произведение.

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

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

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

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

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

Хотя решение в аналитическом виде для ISGD возможно только в методе наименьших квадратов, процедуру можно эффективно реализовать в широкий ряд моделей. В частности, предположим, что ${\displaystyle Q_{i}(w)}$ зависит от ${\displaystyle w}$ только как линейная комбинация свойств ${\displaystyle x_{i}}$, так что мы можем записать ${\displaystyle \nabla _{w}Q_{i}(w)=-q(x_{i}'w)x_{i}}$, где вещественнозначная функция ${\displaystyle q}$ может зависеть от ${\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 легко реализовать следующим образом. Пусть ${\displaystyle f(\xi )=\eta q(x_{i}'w^{old}+\xi ||x_{i}||^{2})}$, где ${\displaystyle \xi }$ является числом. Тогда ISGD эквивалентен

${\displaystyle w^{new}=w^{old}+\xi ^{\ast }x_{i},\;\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))]}$.

Импульс

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

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

где параметр ${\displaystyle w}$, который минимизирует ${\displaystyle Q(w)}$, следует оценить, а ${\displaystyle \eta }$ является размером шага (иногда называется скоростью обучения^[англ.] в машинном обучении).

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

Усреднение

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

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

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

AdaGrad

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

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

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

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

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

${\displaystyle w:=w-\eta \,\mathrm {diag} (G)^{-{\frac {1}{2}}}\circ g}$^[a]

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

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

Каждый элемент ${\displaystyle \{G_{(i,i)}\}}$ даёт множитель для скорости обучения, применяемый к одному параметру ${\displaystyle w_{i}}$. Поскольку знаменатель в этом множителе, ${\displaystyle {\sqrt {G_{i}}}={\sqrt {\sum _{\tau =1}^{t}g_{\tau }^{2}}}}$, является нормой ℓ₂ предыдущей производной, большие изменения параметра ослабляются, в то время как параметры, получающие малые изменения получают более высокие скорости обучения^[19].

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

RMSProp

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

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

где, ${\displaystyle \gamma }$ является коэффициентом забывания.

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

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

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

Adam

Adam^[26] (сокращение от «метод адаптивной оценки моментов», англ. Adaptive Moment Estimation) — это обновление оптимизатора RMSProp. В этом оптимизационном алгоритме используются скользящие средние как градиентов, так и вторых моментов градиентов. Если даны параметры ${\displaystyle w^{(t)}}$, а функция потерь ${\displaystyle L^{(t)}}$, где ${\displaystyle t}$ отражает индекс текущей итерации (отчёт начинается с ${\displaystyle 0}$), пересчёт параметра алгоритмом Adam задаётся формулами

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

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

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

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

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

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

Естественный градиентный спуск и kSGD

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

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

(1) нечувствителен к числу условий задачи,^[b]

(2) имеет робастный выбор гиперпараметров,

(3) имеет условие останова.

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

Для описания алгоритма предположим, что функция ${\displaystyle Q_{i}(w)}$, где ${\displaystyle w\in \mathbb {R} ^{p}}$, определена с помощью ${\displaystyle (Y_{i},X_{i})\in \mathbb {R} \times \mathbb {R} ^{d}}$ так, что

${\displaystyle \nabla _{w}Q_{i}(w)={\frac {Y_{i}-\mu (X_{i},w)}{V(\mu (X_{i},w))}}\nabla _{w}\mu (X_{i},w)}$

где ${\displaystyle \mu (X_{i},w)}$ функция усреднения (то есть ожидаемое значение ${\displaystyle Y_{i}}$ от ${\displaystyle X_{i}}$), а ${\displaystyle V(\mu (X_{i},w))}$ является функцией дисперсии (то есть дисперсия ${\displaystyle Y_{i}}$ для ${\displaystyle X_{i}}$). Тогда пересчёт параметра ${\displaystyle w(t+1)}$ и пересчёт ковариантной матрицы ${\displaystyle M(t+1)}$ задаются следующими выражениями

${\displaystyle p=\nabla _{w}\mu (X_{t+1},w(t))}$

${\displaystyle m=\mu (X_{t+1},w(t))}$

${\displaystyle v=M(t)p}$

${\displaystyle s=\min \lbrace \gamma _{1},\max \lbrace \gamma _{2},V(m)\rbrace \rbrace +v^{\mathsf {T}}p}$

${\displaystyle w(t+1)=w(t)+{\frac {Y_{t+1}-m}{s}}v}$

${\displaystyle M(t+1)=M(t)-{\frac {1}{s}}vv^{\mathsf {T}}}$

где ${\displaystyle \gamma _{1},\gamma _{2}}$ являются гиперпараметрами. Пересчёт ${\displaystyle M(t)}$ может привести к тому, что ковариантная матрица станет неопределённой, что можно избежать за счёт умножения матрицы на матрицу. ${\displaystyle M(0)}$ может быть любой положительно определённой симметричной матрицей, но обычно берётся единичная матрица. Как заметил Патель^[27], для всех задач, не считая линейной регрессии, требуются повторные прогоны для обеспечения сходимости алгоритма, но не приведены теоретические детали или детали реализации. В тесно связанном офлайновом мультипакетном методе для нелинейной регрессии, проанализированным Бертсекасом^[30], для доказательства сходимости использовался коэффициент забывания при пересчёте ковариантной матрицы.

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

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

Комментарии

1. ${\displaystyle \circ }$ является поэлементным произведением.
2. Для задачи линейной регрессии, kSGD's отклонение целевой функции (то есть полная ошибка и дисперсия) на итерации ${\displaystyle k}$ равно ${\displaystyle {\frac {1+\epsilon }{k}}p\sigma ^{2}}$ с вероятностью, стремящейся к 1 со скоростью, зависящей от ${\displaystyle \epsilon \in (0,1)}$, где ${\displaystyle \sigma ^{2}}$ является дисперсией остатков. Более того, для конкретного выбора ${\displaystyle \gamma _{1},\gamma _{2}}$, может быть показано, что kSGD's отклонение целевой функции на итерации ${\displaystyle k}$ равно ${\displaystyle {\frac {(1+\epsilon )^{2}}{2k^{2}}}\Vert w(0)-w_{*}\Vert _{2}^{2}}$ с вероятностью, стремящейся к 1 со скоростью, зависящей от ${\displaystyle \epsilon \in (0,1)}$, где ${\displaystyle w_{*}}$ является оптимальным параметром.

См. также

• Координатный спуск — изменяет одну координату за раз
• Линейный классификатор
• Онлайновое машинное обучение

Примечания

1. 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. 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. Архивировано (PDF) 28 февраля 2020. Дата обращения: 1 марта 2020.
19. Matthew D. Zeiler (2012). "ADADELTA: An adaptive learning rate method". arXiv:1212.5701 [cs.LG].
20. Polyak, Juditsky, 1992, с. 838–855.
21. 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". arXiv:1412.6980 [cs.LG].
27. Patel, 2016, с. 2620–2648.
28. Cichocki, Chen, Amari, 1997, с. 1345–1351.
29. Ollivier Yann (2017). "Online Natural Gradient as a Kalman Filter". arXiv: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.

Литература

• Léon Bottou, Olivier Bousquet. The Tradeoffs of Large Scale Learning // Optimization for Machine Learning / Suvrit Sra, Sebastian Nowozin, Stephen J. Wright (ed.). — Cambridge: MIT Press, 2012. — ISBN 978-0-262-01646-9.
• Song Mei. A mean field view of the landscape of two-layer neural networks (англ.) // Proceedings of the National Academy of Sciences. — National Academy of Sciences, 2018. — Vol. 115, iss. 33. — doi:10.1073/pnas.1806579115. — PMID 30054315. — PMC 6099898.
• Matt Taddy. Stochastic Gradient Descent // Business Data Science: Combining Machine Learning and Economics to Optimize, Automate, and Accelerate Business Decisions. — New York: McGraw-Hill, 2019. — ISBN 978-1-260-45277-8.
• Thomas S. Ferguson. An inconsistent maximum likelihood estimate // Journal of the American Statistical Association. — 1982. — Т. 77, вып. 380. — doi:10.1080/01621459.1982.10477894. — JSTOR 2287314.
• Léon Bottou, Olivier Bousquet. The Tradeoffs of Large Scale Learning // Advances in Neural Information Processing Systems. — 2008. — Т. 20.
• Léon Bottou. Online Algorithms and Stochastic Approximations // Online Learning and Neural Networks. — Cambridge University Press, 1998. — ISBN 978-0-521-65263-6.
• Krzysztof C. Kiwiel. Convergence and efficiency of subgradient methods for quasiconvex minimization // Mathematical Programming, Series A. — Berlin, Heidelberg: Springer, 2001. — Т. 90, вып. 1. — P. 1–25. — ISSN 0025-5610. — doi:10.1007/PL00011414.
• Herbert Robbins, David O. Siegmund. A convergence theorem for non negative almost supermartingales and some applications // Optimizing Methods in Statistics / Jagdish S. Rustagi (ed.). — Academic Press, 1971.
• Jenny Rose Finkel, Alex Kleeman, Christopher D. Manning. Efficient, Feature-based, Conditional Random Field Parsing // Proc. Annual Meeting of the ACL. — 2008.
• Yann A. LeCun, Leon Bottou, Genevieve B. Orr, Klaus-Robert Muller. Efficient backprop // Neural networks: Tricks of the trade / Grégoire Montavon, Geneviève B. Orr, Klaus-Robert Müller (Eds.). — Berlin Heidelberg: Springer, 2012. — Т. 7700. — (Lecture Notes in Computer Science). — ISBN 978-3-642-35288-1.
• Esteban Díaz, Antoine Guitton. Fast full waveform inversion with random shot decimation // SEG Technical Program Expanded Abstracts. — 2011.
• Christian Darken, John Moody. Int'l Joint Conf. on Neural Networks (IJCNN) // Fast adaptive k-means clustering: some empirical results. — IEEE, 1990.
• Spall J. C. Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control. — Hoboken, NJ: Wiley, 2003. — ISBN 0-471-33052-3.
• Panos Toulis, Edoardo Airoldi. Asymptotic and finite-sample properties of estimators based on stochastic gradients // Annals of Statistics. — 2017. — Т. 45, вып. 4. — doi:10.1214/16-AOS1506. — arXiv:1408.2923.
• Spall J. C. Adaptive Stochastic Approximation by the Simultaneous Perturbation Method // IEEE Transactions on Automatic Control. — 2000. — Т. 45, вып. 10. — doi:10.1109/TAC.2000.880982.
• Spall J. C. Feedback and Weighting Mechanisms for Improving Jacobian Estimates in the Adaptive Simultaneous Perturbation Algorithm // IEEE Transactions on Automatic Control. — 2009. — Т. 54, вып. 6. — doi:10.1109/TAC.2009.2019793.
• Bhatnagar S., Prasad H. L., Prashanth L. A. Stochastic Recursive Algorithms for Optimization: Simultaneous Perturbation Methods. — London: Springer, 2013. — ISBN 978-1-4471-4284-3.
• Ruppert D. A Newton-Raphson Version of the Multivariate Robbins-Monro Procedure // Annals of Statistics. — 1985. — Т. 13, вып. 1. — doi:10.1214/aos/1176346589.
• David E. Rumelhart, Geoffrey E. Hinton, Ronald J. Williams. Learning representations by back-propagating errors (англ.) // Nature. — 1986. — October (vol. 323, iss. 6088). — doi:10.1038/323533a0. — Bibcode: 1986Natur.323..533R.
• Ilya Sutskever, James Martens, George Dahl, Geoffrey E. Hinton. On the importance of initialization and momentum in deep learning // In Proceedings of the 30th international conference on machine learning (ICML-13) / Sanjoy Dasgupta, David Mcallester (ed.). — Atlanta, GA, 2013. — Т. 28.
• Boris T. Polyak, Anatoli B. Juditsky. Acceleration of stochastic approximation by averaging // SIAM J. Control Optim.. — 1992. — Т. 30, вып. 4. — doi:10.1137/0330046.
• John Duchi, Elad Hazan, Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization // JMLR. — 2011. — Т. 12.
• Maya R. Gupta, Samy Bengio, Jason Weston. Training highly multiclass classifiers // JMLR. — 2014. — Т. 15, вып. 1.
• Patel V. Kalman-Based Stochastic Gradient Method with Stop Condition and Insensitivity to Conditioning // SIAM Journal on Optimization. — 2016. — Т. 26, вып. 4. — ISSN 1052-6234. — doi:10.1137/15M1048239. — arXiv:1512.01139.
• Cichocki A., Chen T., Amari S. Stability Analysis of Learning Algorithms for Blind Source Separation // Neural Networks. — 1997. — Ноябрь (т. 10, вып. 8). — doi:10.1016/S0893-6080(97)00039-7. — PMID 12662478.
• Byrd R. H., Hansen S. L., Nocedal J., Singer Y. A Stochastic Quasi-Newton method for Large-Scale Optimization // SIAM Journal on Optimization. — 2016. — Т. 26, вып. 2. — doi:10.1137/140954362. — arXiv:1401.7020.
• Bertsekas D. Incremental Least Squares Methods and the Extended Kalman Filter // SIAM Journal on Optimization. — 1996. — Т. 6, вып. 3. — С. 807—822. — ISSN 1052-6234. — doi:10.1137/S1052623494268522.

Литература для дальнейшего чтения

• Dimitri P. Bertsekas. Nonlinear Programming. — 2nd. — Cambridge, MA.: Athena Scientific, 1999. — ISBN 978-1-886529-00-7..
• Dimitri P. Bertsekas. Convex Analysis and Optimization. — Athena Scientific, 2003.
• Léon Bottou. Stochastic Learning // Advanced Lectures on Machine Learning. — Springer, 2004. — Т. 3176. — С. 146—168. — (LNAI). — ISBN 978-3-540-23122-6.
• Davidon W.C. [187–197 New least-square algorithms] // Journal of Optimization Theory and Applications. — 1976. — Т. 18, № 2. — doi:10.1007/BF00935703.
• Richard O. Duda, Peter E. Hart, David G. Stork. Pattern Classification. — 2nd. — Wiley, 2000. — ISBN 978-0-471-05669-0.
• Krzysztof C. Kiwiel. Convergence of approximate and incremental subgradient methods for convex optimization // SIAM Journal on Optimization. — 2004. — Т. 14, № 3. — С. 807—840. — doi:10.1137/S1052623400376366.
• Jan A. Snyman, Daniel N. Wilke. Practical Mathematical Optimization - Basic Optimization Theory and Gradient-Based Algorithms. — 2. — Springer, 2018. — С. xxvi+372. — (Springer Optimization and Its Applications Vol. 133). — ISBN 978-3-319-77585-2.
• James C. Spall. Introduction to Stochastic Search and Optimization. — Wiley, 2003. — ISBN 978-0-471-33052-3..

Ссылки

• Using stochastic gradient descent in C++, Boost, Ublas for linear regression
• Machine Learning Algorithms
• Gradient Descent, How Neural Networks Learn  (неопр.). 3Blue1Brown (16 октября 2017).