12.4. Стохастический градиентный спуск¶
В предыдущих главах мы неоднократно использовали стохастический градиентный спуск в процессе обучения, однако не объясняли, почему он работает. Чтобы прояснить этот вопрос, мы уже описали основные принципы градиентного спуска в Section 12.3. В этом разделе мы подробнее обсудим стохастический градиентный спуск.
%matplotlib inline
import math
import torch
from d2l import torch as d2l
12.4.1. Стохастические обновления градиента¶
В глубоком обучении целевая функция обычно представляет собой среднее значение функций потерь для каждого примера в обучающем наборе данных. Пусть обучающий набор данных содержит \(n\) примеров. Обозначим через \(f_i(\mathbf{x})\) функцию потерь для примера с индексом \(i\), где \(\mathbf{x}\) — вектор параметров. Тогда целевая функция имеет вид
Градиент целевой функции в точке \(\mathbf{x}\) вычисляется как
Если используется градиентный спуск, вычислительная стоимость каждой итерации составляет \(\mathcal{O}(n)\), что линейно возрастает в зависимости от размера \(n\). Следовательно, при увеличении размера обучающего набора данных стоимость градиентного спуска для каждой итерации возрастает.
Стохастический градиентный спуск (SGD) снижает вычислительные затраты на каждой итерации. На каждой итерации стохастического градиентного спуска мы случайным образом выбираем индекс \(i\in\{1,\ldots, n\}\) среди примеров данных и вычисляем градиент \(\nabla f_i(\mathbf{x})\) для обновления \(\mathbf{x}\):
где \(\eta\) — скорость обучения. Мы видим, что вычислительная стоимость каждой итерации снижается с \(\mathcal{O}(n)\) при градиентном спуске до константы \(\mathcal{O}(1)\). Кроме того, хотим подчеркнуть, что стохастический градиент \(\nabla f_i(\mathbf{x})\) является несмещённой оценкой полного градиента \(\nabla f(\mathbf{x})\), поскольку
Это означает, что в среднем стохастический градиент является хорошей оценкой градиента.
Теперь мы сравним его с градиентным спуском, добавив к градиенту случайный шум со средним значением 0 и дисперсией 1, чтобы смоделировать стохастический градиентный спуск.
def f(x1, x2): # Objective function
return x1 ** 2 + 2 * x2 ** 2
def f_grad(x1, x2): # Gradient of the objective function
return 2 * x1, 4 * x2
def sgd(x1, x2, s1, s2, f_grad):
g1, g2 = f_grad(x1, x2)
# Simulate noisy gradient
g1 += torch.normal(0.0, 1, (1,)).item()
g2 += torch.normal(0.0, 1, (1,)).item()
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 # Constant learning rate
d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=50, f_grad=f_grad))
Как видно, траектория переменных в стохастическом градиентном спуске гораздо более зашумлена, чем в градиентном спуске из Section 12.3. Это связано со стохастической природой градиента. То есть, даже оказавшись вблизи минимума, мы всё ещё подвержены неопределённости, вносимой мгновенным градиентом через \(\eta \nabla f_i(\mathbf{x})\). Даже после 50 шагов качество остаётся невысоким. Хуже того, оно не улучшится при дополнительных шагах (мы рекомендуем вам поэкспериментировать с большим количеством шагов, чтобы убедиться в этом). Таким образом, остаётся лишь один вариант: изменить скорость обучения \(\eta\). Однако, если выбрать её слишком маленькой, мы изначально не добьёмся существенного прогресса. С другой стороны, если выбрать её слишком большой, мы не получим хорошее решение, как показано выше. Единственный способ разрешить эти противоречивые требования — динамически уменьшать скорость обучения по мере продвижения оптимизации.
Это также является причиной добавления функции скорости обучения lr
в функцию шага sgd. В приведённом выше примере любой функционал для
планирования скорости обучения остаётся неиспользованным, поскольку мы
установили соответствующую lr функцию равной константе.
12.4.2. Динамическая скорость обучения¶
Замена \(\eta\) на зависящую от времени скорость обучения \(\eta(t)\) усложняет контроль сходимости алгоритма оптимизации. В частности, нам нужно решить, насколько быстро \(\eta\) должно уменьшаться. Если это происходит слишком быстро, мы прекратим оптимизацию преждевременно. Если же мы уменьшаем её слишком медленно, то тратим слишком много времени на оптимизацию. Ниже приведены несколько базовых стратегий, используемых для изменения \(\eta\) со временем (более продвинутые стратегии мы обсудим позже):
В первом сценарии с кусочно-постоянной скоростью обучения мы уменьшаем скорость обучения, например, всякий раз, когда прогресс в оптимизации останавливается. Это распространенная стратегия для обучения глубоких сетей. В качестве альтернативы мы можем уменьшать её гораздо более агрессивно с помощью экспоненциального затухания. К сожалению, это часто приводит к преждевременной остановке до того, как алгоритм сойдется. Популярным выбором является полиномиальное затухание со \(\alpha = 0.5\). В случае выпуклой оптимизации существует ряд доказательств, показывающих, что такая скорость обучения ведет себя корректно.
Давайте посмотрим, как экспоненциальное затухание выглядит на практике.
def exponential_lr():
# Global variable that is defined outside this function and updated inside
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 variable that is defined outside this function and updated inside
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))
Существует гораздо больше вариантов настройки скорости обучения. Например, можно начать с малого значения, затем быстро увеличить его, а после — снова уменьшить, albeit более медленно. Можно даже чередовать меньшие и большие значения скорости обучения. Существует большое разнообразие таких расписаний. Пока же мы сосредоточимся на расписаниях скорости обучения, для которых возможен полный теоретический анализ, то есть на скоростях обучения в выпуклом случае. Для общих невыпуклых задач очень трудно получить значимые гарантии сходимости, поскольку в общем случае минимизация нелинейных невыпуклых задач является NP-трудной. Обзор см., например, в отличных лекционных материалах Tibshirani 2015 года.
12.4.3. Анализ сходимости для выпуклых функций¶
Следующий анализ сходимости стохастического градиентного спуска для выпуклых целевых функций является необязательным и служит прежде всего для формирования более глубокого понимания проблемы. Мы ограничимся одним из простейших доказательств (Nesterov and Vial, 2000). Существуют значительно более сложные методы доказательства, например, когда целевая функция обладает особыми свойствами.
Предположим, что целевая функция \(f(\boldsymbol{\xi}, \mathbf{x})\) выпукла по \(\mathbf{x}\) для всех \(\boldsymbol{\xi}\). Более конкретно, рассмотрим обновление стохастического градиентного спуска:
где \(f(\boldsymbol{\xi}_t, \mathbf{x})\) — целевая функция для обучающего примера \(\boldsymbol{\xi}_t\), выбранного из некоторого распределения на шаге \(t\), а \(\mathbf{x}\) — параметр модели. Обозначим через
ожидаемого риска и через \(R^*\) — его минимум по \(\mathbf{x}\). Далее пусть \(\mathbf{x}^*\) будет минимизатором (мы предполагаем, что он существует в области определения, где определена \(\mathbf{x}\)). В этом случае мы можем отслеживать расстояние между текущим параметром \(\mathbf{x}_t\) в момент времени \(t\) и минимизатором риска \(\mathbf{x}^*\), чтобы увидеть, улучшается ли оно со временем:
Мы предполагаем, что норма \(\ell_2\) стохастического градиента \(\partial_\mathbf{x} f(\boldsymbol{\xi}_t, \mathbf{x})\) ограничена некоторой константой \(L\), следовательно, имеем:
Нас в первую очередь интересует, как изменяется расстояние между \(\mathbf{x}_t\) и \(\mathbf{x}^*\) в математическом ожидании. На самом деле, для любой конкретной последовательности шагов расстояние может увеличиваться, в зависимости от того, какой градиент \(\boldsymbol{\xi}_t\) нам встретится. Следовательно, нам необходимо оценить скалярное произведение. Поскольку для любой выпуклой функции \(f\) выполняется неравенство \(f(\mathbf{y}) \geq f(\mathbf{x}) + \langle f'(\mathbf{x}), \mathbf{y} - \mathbf{x} \rangle\) для всех \(\mathbf{x}\) и \(\mathbf{y}\), из выпуклости следует, что
Подставляя неравенства (12.4.9) и (12.4.10) в (12.4.8), получаем оценку расстояния между параметрами на шаге \(t+1\):
Это означает, что мы достигаем прогресса до тех пор, пока разница между текущей и оптимальной функциями потерь превышает \(\eta_t L^2/2\). Поскольку эта разница неизбежно стремится к нулю, следует, что скорость обучения \(\eta_t\) также должна стремиться к нулю.
Далее берем математическое ожидание по (12.4.11). Это дает
Последний шаг заключается в суммировании неравенств для \(t \in \{1, \ldots, T\}\). Поскольку сумма телескопическая, отбрасывая нижний член, мы получаем
Заметим, что мы использовали тот факт, что \(\mathbf{x}_1\) задано, поэтому математическое ожидание можно опустить. В заключение определим
Поскольку
из неравенства Йенсена (с учётом \(i=t\), \(\alpha_i = \eta_t/\sum_{t=1}^T \eta_t\) в (12.2.3)) и выпуклости \(R\) следует, что \(E[R(\mathbf{x}_t)] \geq E[R(\bar{\mathbf{x}})]\), поэтому
Подставляя это в неравенство (12.4.13), получаем оценку
где \(r^2 \stackrel{\textrm{def}}{=} \|\mathbf{x}_1 - \mathbf{x}^*\|^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})\).
12.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\). Таким образом, вероятность выбрать его хотя бы один раз составляет
Аналогичные рассуждения показывают, что вероятность выбрать какой-либо пример (т. е. обучающий пример) ровно один раз равна
Выборка с возвращением приводит к увеличению дисперсии и снижению эффективности использования данных по сравнению с выборкой без возвращения. Поэтому на практике мы используем второй вариант (и это выбор по умолчанию во всей книге). Обратите внимание, что при повторных проходах по обучающему набору данных он обходится в другом случайном порядке.
12.4.5. Резюме¶
Для выпуклых задач можно доказать, что при широком выборе скоростей обучения стохастический градиентный спуск сходится к оптимальному решению.
В глубоком обучении это, как правило, не так. Однако анализ выпуклых задач дает нам полезное представление о том, как подходить к оптимизации, а именно — постепенно уменьшать скорость обучения, хотя и не слишком быстро.
Проблемы возникают, когда скорость обучения слишком мала или слишком велика. На практике подходящую скорость обучения часто удаётся найти лишь после множества экспериментов.
Когда в обучающем наборе данных больше примеров, вычисление каждой итерации градиентного спуска обходится дороже, поэтому в таких случаях предпочтителен стохастический градиентный спуск.
Гарантии оптимальности для стохастического градиентного спуска в общем случае не могут быть получены для невыпуклых задач, поскольку количество локальных минимумов, которые требуется проверить, может быть экспоненциальным.
12.4.6. Упражнения¶
Экспериментируйте с различными графиками изменения скорости обучения при стохастическом градиентном спуске и с разным количеством итераций. В частности, постройте график расстояния от оптимального решения \((0, 0)\) в зависимости от числа итераций.
Докажите, что для функции \(f(x_1, x_2) = x_1^2 + 2 x_2^2\) добавление нормального шума к градиенту эквивалентно минимизации функции потерь \(f(\mathbf{x}, \mathbf{w}) = (x_1 - w_1)^2 + 2 (x_2 - w_2)^2\), где \(\mathbf{x}\) выбирается из нормального распределения.
Сравните сходимость стохастического градиентного спуска при выборке \(\{(x_1, y_1), \ldots, (x_n, y_n)\}\) с возвращением и без.
Как бы вы изменили алгоритм стохастического градиентного спуска, если бы один из градиентов (а точнее, одна из координат, соответствующих ему) постоянно превышал все остальные градиенты?
Предположим, что \(f(x) = x^2 (1 + \sin x)\). Сколько локальных минимумов имеет \(f\)? Можно ли изменить \(f\) таким образом, чтобы для его минимизации потребовалось проверить все локальные минимумы?