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

Как упомянуто ранее, классический стохастический градиентный спуск обычно чувствителен к скорости обучения ${\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 (адаптивный градиентный алгоритм, англ. 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}$[lower-alpha 1]

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

${\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 (от англ. 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[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}}$ являются коэффициентами забывания для градиентов и вторых моментов градиентов соответственно. Возведение в квадрат и квадратный корень вычисляются поэлементно.

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

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

(1) нечувствителен к числу условий задачи,[lower-alpha 2]

(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). В частности, оптимальность второго порядка асимптотически достижима без непосредственного вычисления матриц Гессе членов суммы в эмпирической функции риска.