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

В предыдущих разделах мы использовали стохастический градиентный спуск в процессе обучения, но не объясняли, почему он работает. Чтобы прояснить это, в разделе 11.3 мы описали основные принципы градиентного спуска. В этом разделе подробнее рассмотрим стохастический градиентный спуск (stochastic gradient descent, SGD).

%matplotlib inline
from d2l import mxnet as d2l
import math
from mxnet import np, npx
npx.set_np()

%matplotlib inline
from d2l import torch as d2l
import math
import torch

%matplotlib inline
from d2l import tensorflow as d2l
import math
import tensorflow as tf

%matplotlib inline
from d2l import paddle as d2l
import warnings
warnings.filterwarnings("ignore")
import math
import paddle

11.4.1 Обновление по случайному градиенту

В глубоком обучении целевая функция обычно является средним значением функций потерь по каждому примеру обучающего набора данных. Пусть задан обучающий набор из $n$ примеров, и $f_i(\mathbf{x})$ — функция потерь для обучающего примера с индексом $i$, где $\mathbf{x}$ — вектор параметров. Тогда мы получаем целевую функцию

$$f(\mathbf{x})=\frac{1}{n}\sum _{i=1}^n{f}_i(\mathbf{x}).$$

Градиент целевой функции в точке $\mathbf{x}$ вычисляется как

$$\nabla f(\mathbf{x})=\frac{1}{n}\sum _{i=1}^n\nabla f_i(\mathbf{x}).$$

Если использовать градиентный спуск, то вычислительная стоимость каждой итерации обновления параметров составляет $\mathcal{O}(n)$ и линейно растёт с ростом $n$. Поэтому при большом обучающем наборе данных каждая итерация градиентного спуска обходится дорого.

Стохастический градиентный спуск (SGD) снижает вычислительную стоимость каждой итерации. На каждой итерации SGD равномерно и случайно выбирает индекс $i$ из $\{1,\dots ,n\}$ и вычисляет градиент $\nabla f_i(\mathbf{x})$, чтобы обновить $\mathbf{x}$:

$$\mathbf{x}\leftarrow \mathbf{x}-\eta \nabla f_i(\mathbf{x}),$$

где $\eta$ — скорость обучения. Видно, что стоимость каждой итерации снижается с $\mathcal{O}(n)$ у градиентного спуска до константы $\mathcal{O}(1)$. Кроме того, стоит подчеркнуть, что стохастический градиент $\nabla f_i(\mathbf{x})$ является несмещённой оценкой полного градиента $\nabla f(\mathbf{x})$, поскольку

$${\mathbb{E}}_i\nabla f_i(\mathbf{x})=\frac{1}{n}\sum _{i=1}^n\nabla f_i(\mathbf{x})=\nabla f(\mathbf{x}).$$

Это означает, что в среднем стохастический градиент — хорошая оценка градиента.

Теперь сравним его с градиентным спуском, добавив к градиенту случайный шум со средним $0$ и дисперсией $1$, чтобы смоделировать стохастический градиентный спуск.

def f(x1, x2):  # Целевая функция
    return x1 ** 2 + 2 * x2 ** 2

def f_grad(x1, x2):  # Градиент целевой функции
    return 2 * x1, 4 * x2

def sgd(x1, x2, s1, s2, f_grad):
    g1, g2 = f_grad(x1, x2)
    # Имитация зашумлённого градиента
    g1 += d2l.normal(0.0, 1, (1,)).item()
    g2 += d2l.normal(0.0, 1, (1,)).item()
    eta_t = eta * lr()
    return (x1 - eta_t * g1, x2 - eta_t * g2, 0, 0)

def sgd(x1, x2, s1, s2, f_grad):
    g1, g2 = f_grad(x1, x2)
    # Имитация зашумлённого градиента
    g1 += d2l.normal([1], 0.0, 1)
    g2 += d2l.normal([1], 0.0, 1)
    eta_t = eta * lr()
    return (x1 - eta_t * g1, x2 - eta_t * g2, 0, 0)

def constant_lr():
    return 1

eta = 0.1
lr = constant_lr  # Постоянная скорость обучения
d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=50, f_grad=f_grad))

Как видно, траектория переменных при стохастическом градиентном спуске гораздо более шумная, чем траектория при градиентном спуске, которую мы наблюдали в разделе 11.3. Это следствие случайной природы градиента. Иными словами, даже вблизи минимума мы всё ещё подвержены неопределённости, которую вносит мгновенный градиент $\eta \nabla f_i(\mathbf{x})$. Даже после 50 итераций качество решения остаётся невысоким. Хуже того, с дальнейшими шагами оно не улучшается. Остаётся единственный выход — менять скорость обучения $\eta$. Но если выбрать её слишком маленькой, то в самом начале мы не добьёмся никакого заметного прогресса; если же выбрать её слишком большой, мы не получим хорошего решения, как показано выше. Единственный способ примирить эти противоречивые цели — динамически уменьшать скорость обучения в процессе оптимизации.

Именно поэтому в функцию шага sgd добавлена функция скорости обучения lr. В приведённом выше примере функция планирования скорости обучения «спит», поскольку мы задали для lr постоянное значение.

11.4.2 Динамическая скорость обучения

Замена $\eta$ на зависящую от времени скорость обучения $\eta (t)$ усложняет управление сходимостью алгоритма оптимизации. В частности, нужно понять, с какой скоростью убывает $\eta$. Если убывание слишком быстрое, оптимизация остановится преждевременно; если слишком медленное — мы потратим на оптимизацию слишком много времени. Ниже приведены несколько базовых стратегий изменения $\eta$ во времени (более продвинутые стратегии мы обсудим позже):

$$\begin{array}{rlrl}\eta (t)& ={\eta }_i\text{ при }{t}_i\le t\le t_{i+1}& & \text{кусочно-постоянная}\\ \eta (t)& ={\eta }_0\cdot e^{-\lambda t}& & \text{экспоненциальное затухание}\\ \eta (t)& ={\eta }_0\cdot (\beta t+1{)}^{-\alpha }& & \text{полиномиальное затухание}\end{array}$$

В первом, кусочно-постоянном (piecewise constant), сценарии мы уменьшаем скорость обучения, например, каждый раз, когда прогресс оптимизации останавливается. Это распространённая стратегия при обучении глубоких сетей. Или же можно уменьшать её агрессивнее с помощью экспоненциального затухания (exponential decay). К сожалению, это часто приводит к преждевременной остановке алгоритма до его сходимости. Популярный выбор — полиномиальное затухание (polynomial decay) с $\alpha =0.5$. Для выпуклой оптимизации есть много свидетельств того, что такой темп убывания работает хорошо.

Посмотрим, как выглядит экспоненциальное затухание на практике.

def exponential_lr():
    # Глобальная переменная, которая определена вне функции и обновляется внутри неё
    global t
    t += 1
    return math.exp(-0.1 * t)

t = 1
lr = exponential_lr
d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=1000, f_grad=f_grad))

Как и ожидалось, дисперсия параметров значительно уменьшилась. Однако это произошло ценой того, что алгоритм не сошёлся к оптимальному решению $\mathbf{x}=(0,0)$. Даже после 1000 итераций мы всё ещё далеки от оптимума. По сути, алгоритм вообще не сходится. С другой стороны, если использовать полиномиальное затухание, при котором скорость обучения убывает обратно пропорционально квадратному корню из числа итераций, то уже после 50 итераций сходимость окажется лучше.

def polynomial_lr():
    # Глобальная переменная, которая определена вне функции и обновляется внутри неё
    global t
    t += 1
    return (1 + 0.1 * t) ** (-0.5)

t = 1
lr = polynomial_lr
d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=50, f_grad=f_grad))

Существует и много других вариантов выбора скорости обучения. Например, можно начать с небольшой скорости, затем быстро поднять её, а потом снова уменьшать, хотя это будет происходить медленнее. Можно даже переключаться между маленькими и большими значениями. Однако сейчас мы сосредоточимся на схемах скорости обучения, для которых можно провести полный теоретический анализ, то есть на скорости обучения в выпуклом случае. Для общих невыпуклых задач трудно получить содержательные гарантии сходимости, поскольку в целом минимизация нелинейных невыпуклых задач является NP-трудной. Обзор соответствующих исследований можно найти, например, в превосходных лекционных заметках Тибширани (Tibshirani) за 2015 год.

11.4.3 Анализ сходимости для выпуклых целей

Следующий анализ сходимости стохастического градиентного спуска для выпуклых целевых функций является необязательным и в основном служит для того, чтобы передать больше интуиции об этой задаче. Мы ограничимся одним из самых простых доказательств (Nesterov and Vial, 2000). Существуют заметно более продвинутые методы доказательства, например, для случаев, когда целевая функция ведёт себя особенно хорошо.

Предположим, что для всех $\mathbf{\xi }$ целевая функция $f(\mathbf{\xi },\mathbf{x})$ выпукла по $\mathbf{x}$. Более конкретно, рассмотрим обновление стохастического градиентного спуска:

$${\mathbf{x}}_{t+1}={\mathbf{x}}_t-{\eta }_t{\partial }_{\mathbf{x}}f({\mathbf{\xi }}_t,\mathbf{x}),$$

где $f({\mathbf{\xi }}_t,\mathbf{x})$ — целевая функция обучающего примера ${\mathbf{\xi }}_t$, который извлекается из некоторого распределения на шаге $t$, а $\mathbf{x}$ — параметры модели. Обозначим через

$$R(\mathbf{x})=E_{\mathbf{\xi }}[f(\mathbf{\xi },\mathbf{x})]$$

ожидаемый риск, а через $R^{\ast }$ — минимальный риск для $\mathbf{x}$. Наконец, пусть ${\mathbf{x}}^{\ast }$ — точка минимума (мы предполагаем, что она лежит в области определения $\mathbf{x}$). В этом случае мы можем отслеживать расстояние между текущими параметрами ${\mathbf{x}}_t$ в момент времени $t$ и минимизатором риска ${\mathbf{x}}^{\ast }$, чтобы проверить, улучшается ли оно со временем:

$$\begin{array}{rl}& \Vert {\mathbf{x}}_{t+1}-{\mathbf{x}}^{\ast }{\Vert }^2\\ =& \Vert {\mathbf{x}}_t-{\eta }_t{\partial }_{\mathbf{x}}f({\mathbf{\xi }}_t,\mathbf{x})-{\mathbf{x}}^{\ast }{\Vert }^2\\ =& \Vert {\mathbf{x}}_t-{\mathbf{x}}^{\ast }{\Vert }^2+{\eta }_t^2\Vert {\partial }_{\mathbf{x}}f({\mathbf{\xi }}_t,\mathbf{x}){\Vert }^2-2{\eta }_t⟨{\mathbf{x}}_t-{\mathbf{x}}^{\ast },{\partial }_{\mathbf{x}}f({\mathbf{\xi }}_t,\mathbf{x})⟩.\end{array}\text{\hspace{1em}(11.4.1)}$$

Предположим, что $L_2$-норма стохастического градиента ${\partial }_{\mathbf{x}}f({\mathbf{\xi }}_t,\mathbf{x})$ ограничена некоторой константой $L$, поэтому

$${\eta }_t^2\Vert {\partial }_{\mathbf{x}}f({\mathbf{\xi }}_t,\mathbf{x}){\Vert }^2\le {\eta }_t^2{L}^2.\text{\hspace{1em}(11.4.2)}$$

Нас больше всего интересует математическое ожидание того, как меняется расстояние между ${\mathbf{x}}_t$ и ${\mathbf{x}}^{\ast }$. На самом деле для любой конкретной последовательности шагов расстояние может увеличиться — это зависит от того, какие ${\mathbf{\xi }}_t$ нам встретятся. Поэтому нам нужна оценка для скалярного произведения. Поскольку для любой выпуклой функции $f$ и любых $\mathbf{x}$ и $\mathbf{y}$ выполнено $f(\mathbf{y})\ge f(\mathbf{x})+⟨f^{\prime }(\mathbf{x}),\mathbf{y}-\mathbf{x}⟩$, из выпуклости следует

$$f({\mathbf{\xi }}_t,{\mathbf{x}}^{\ast })\ge f({\mathbf{\xi }}_t,{\mathbf{x}}_t)+⟨{\mathbf{x}}^{\ast }-{\mathbf{x}}_t,{\partial }_{\mathbf{x}}f({\mathbf{\xi }}_t,{\mathbf{x}}_t)⟩.\text{\hspace{1em}(11.4.3)}$$

Подставив неравенства (11.4.2) и (11.4.3) в (11.4.1), мы получим оценку расстояния между параметрами на шаге $t+1$:

$$\Vert {\mathbf{x}}_t-{\mathbf{x}}^{\ast }{\Vert }^2-\Vert {\mathbf{x}}_{t+1}-{\mathbf{x}}^{\ast }{\Vert }^2\ge 2{\eta }_t(f({\mathbf{\xi }}_t,{\mathbf{x}}_t)-f({\mathbf{\xi }}_t,{\mathbf{x}}^{\ast }))-{\eta }_t^2{L}^2.\text{\hspace{1em}(11.4.4)}$$

Это означает, что прогресс мы получаем всякий раз, когда разница между текущими потерями и оптимальными потерями превышает ${\eta }_t{L}^2/2$. Поскольку эта разница обязательно стремится к нулю, скорость обучения ${\eta }_t$ тоже должна стремиться к нулю.

Далее возьмём математическое ожидание от (11.4.4). Получаем

$$E\left[\Vert {\mathbf{x}}_t-{\mathbf{x}}^{\ast }{\Vert }^2\right]-E\left[\Vert {\mathbf{x}}_{t+1}-{\mathbf{x}}^{\ast }{\Vert }^2\right]\ge 2{\eta }_t[E[R({\mathbf{x}}_t)]-R^{\ast }]-{\eta }_t^2{L}^2.$$

Последний шаг — сложить неравенства по $t\in \{1,\dots ,T\}$. При суммировании промежуточные члены сокращаются, а затем отбрасываем члены низших порядков, и получаем

$$\Vert {\mathbf{x}}_1-{\mathbf{x}}^{\ast }{\Vert }^2\ge 2\left(\sum _{t=1}^T{\eta }_t\right)[E[R({\mathbf{x}}_t)]-R^{\ast }]-L^2\sum _{t=1}^T{\eta }_t^2.\text{\hspace{1em}(11.4.5)}$$

Заметим, что поскольку ${\mathbf{x}}_1$ задано, математическое ожидание можно опустить. Наконец, определим

$$\bar{\mathbf{x}}\stackrel{\mathrm{def}}{=}\frac{{\sum }_{t=1}^T{\eta }_t{\mathbf{x}}_t}{{\sum }_{t=1}^T{\eta }_t}.$$

Поскольку

$$E\left(\frac{{\sum }_{t=1}^T{\eta }_{t}R({\mathbf{x}}_t)}{{\sum }_{t=1}^T{\eta }_t}\right)=\frac{{\sum }_{t=1}^T{\eta }_{t}E[R({\mathbf{x}}_t)]}{{\sum }_{t=1}^T{\eta }_t}=E[R({\mathbf{x}}_t)],$$

то по неравенству Йенсена (уравнение (11.2.1) при $i=t$, ${\alpha }_i={\eta }_t/{\sum }_{t=1}^T{\eta }_t$) и из выпуклости $R$, которая даёт $E[R({\mathbf{x}}_t)]\ge E[R(\bar{\mathbf{x}})]$, мы получаем

$$\sum _{t=1}^T{\eta }_{t}E[R({\mathbf{x}}_t)]\ge \sum _{t=1}^T{\eta }_{t}E\left[R(\bar{\mathbf{x}})\right].$$

Подставив это в (11.4.5), получаем оценку

$$\left[E[\bar{\mathbf{x}}]\right]-R^{\ast }\le \frac{r^2+L^2{\sum }_{t=1}^T{\eta }_t^2}{2{\sum }_{t=1}^T{\eta }_t},$$

где $r^2\stackrel{\mathrm{def}}{=}\Vert {\mathbf{x}}_1-{\mathbf{x}}^{\ast }{\Vert }^2$ — оценка расстояния между начальным выбором параметров и конечным результатом. Коротко говоря, скорость сходимости зависит от того, как ограничена норма стохастического градиента ($L$), и от расстояния между начальным значением параметров и оптимальным решением ($r$). Обратите внимание, что оценка выражена через $\bar{\mathbf{x}}$, а не через ${\mathbf{x}}_T$, потому что $\bar{\mathbf{x}}$ — это сглаженная версия траектории оптимизации. Зная $r$, $L$ и $T$, можно выбрать скорость обучения $\eta =r/(L\sqrt{T})$. Тогда верхняя оценка равна $rL/\sqrt{T}$. То есть мы сходимся к оптимальному решению со скоростью $\mathcal{O}(1/\sqrt{T})$.

11.4.4 Стохастический градиент и конечные выборки

До сих пор, говоря о стохастическом градиентном спуске, мы действовали несколько поверхностно. Мы предполагали, что примеры $x_i$ (обычно вместе с метками $y_i$) выбираются из распределения $p(x,y)$, и использовали их для обновления параметров модели определённым образом. В частности, для конечного числа примеров мы рассматривали только дискретное распределение $p(x,y)=\frac{1}{n}{\sum }_{i=1}^n{\delta }_{x_i}(x){\delta }_{y_i}(y)$, состоящее из функций ${\delta }_{x_i}$ и ${\delta }_{y_i}$, которые позволяют выполнять по нему стохастический градиентный спуск.

Однако на самом деле мы так не поступали. В простом примере этого раздела мы просто добавляли шум к другому, нестохастическому градиенту, то есть делали вид, будто у нас есть пары $(x_i,y_i)$. Оказывается, для данного случая такой подход оправдан (подробное обсуждение см. в упражнениях). Но во всех предыдущих рассуждениях мы явно так не поступали. Вместо этого мы проходили по всем примерам ровно один раз. Чтобы понять, почему это предпочтительнее, рассмотрим обратную ситуацию: мы с возвращением выбираем $n$ наблюдений из дискретного распределения. Вероятность выбрать элемент $i$ при каждом выборе равна $1/n$. Поэтому вероятность выбрать его хотя бы один раз равна

$$P(\mathrm{choose}i)=1-P(\mathrm{omit}i)=1-(1-1/n{)}^n\approx 1-e^{-1}\approx \mathrm{0.63.}$$

Аналогичные рассуждения показывают, что вероятность выбрать какой-то пример ровно один раз равна

$$\left(\genfrac{}{}{0ex}{}{n}{1}\right)\frac{1}{n}{\left(1-\frac{1}{n}\right)}^{n-1}=\frac{n}{n-1}{\left(1-\frac{1}{n}\right)}^n\approx e^{-1}\approx \mathrm{0.37.}$$

Это приводит к увеличению дисперсии и снижению эффективности использования данных по сравнению с выборкой без возвращения. Поэтому на практике мы используем последнюю (это выбор по умолчанию в этой книге). И последнее замечание: при повторном проходе по обучающему набору данных его обходят в другом случайном порядке.

Резюме

• Для выпуклых задач можно доказать, что при широком выборе скорости обучения стохастический градиентный спуск сходится к оптимальному решению.
• В глубоком обучении это обычно не так. Однако анализ выпуклых задач даёт представление о том, как следует проводить оптимизацию: постепенно уменьшать скорость обучения, но не слишком быстро.
• Проблемы возникают, если скорость обучения слишком мала или слишком велика. На практике подходящую скорость обучения обычно находят только после многочисленных экспериментов.
• Когда в обучающем наборе данных много примеров, каждая итерация градиентного спуска обходится дороже, поэтому в таких случаях предпочтителен стохастический градиентный спуск.
• Гарантии оптимальности стохастического градиентного спуска в невыпуклом случае, как правило, недоступны, поскольку число локальных минимумов, которые нужно проверить, может быть экспоненциальным.

Упражнения

1. Поэкспериментируйте с различными графиками скорости обучения для стохастического градиентного спуска и с разным числом итераций. В частности, постройте график зависимости расстояния до оптимального решения $(0,0)$ от числа итераций.
2. Докажите, что для функции $f(x_1,x_2)=x_1^2+2x_2^2$ добавление к градиенту нормального шума эквивалентно минимизации функции потерь $f(\mathbf{x},\mathbf{w})=(x_1-w_1{)}^2+2(x_2-w_2{)}^2$, где $\mathbf{x}$ извлекается из нормального распределения.
3. Сравните сходимость стохастического градиентного спуска при выборке из $\{(x_1,y_1),\dots ,(x_n,y_n)\}$ с возвращением и без возвращения.
4. Как изменится решатель стохастического градиентного спуска, если некоторые градиенты (точнее, связанные с ними координаты) всегда больше всех остальных?
5. Пусть $f(x)=x^2(1+\sin x)$. Сколько у $f$ локальных минимумов? Попробуйте изменить $f$ так, чтобы для минимизации потребовалось вычислить все локальные минимумы.

MXNet: Обсуждение

PyTorch: Обсуждение

TensorFlow: Обсуждение

PaddlePaddle: Обсуждение

Литература

• Nesterov, Y., & Vial, J.-P. (2000). Confidence level solutions for stochastic programming. Stochastic Programming E-Print Series.