12.6. Импульс¶
В разделе Section 12.4 мы рассмотрели, что происходит при выполнении стохастического градиентного спуска, то есть при оптимизации, когда доступен лишь зашумленный вариант градиента. В частности, мы заметили, что при наличии шума в градиентах необходимо проявлять особую осторожность при выборе скорости обучения. Если уменьшать её слишком быстро, сходимость замедляется. Если же мы слишком снисходительны, то не достигаем достаточно хорошего решения, поскольку шум продолжает отклонять нас от оптимума.
12.6.1. Основы¶
В этом разделе мы рассмотрим более эффективные алгоритмы оптимизации, особенно для определённых типов задач оптимизации, часто встречающихся на практике.
12.6.1.1. Утекающие средние¶
В предыдущем разделе мы обсуждали использование стохастического градиентного спуска на мини-батчах (minibatch SGD) для ускорения вычислений. Это также имело приятный побочный эффект: усреднение градиентов снижало дисперсию. Вычисление стохастического градиентного спуска на мини-батчах выполняется по формуле:
Чтобы упростить обозначения, здесь мы использовали \(\mathbf{h}_{i, t-1} = \partial_{\mathbf{w}} f(\mathbf{x}_i, \mathbf{w}_{t-1})\) как стохастический градиентный спуск для примера \(i\) с весами, обновленными в момент времени \(t-1\). Было бы полезно использовать эффект снижения дисперсии даже за пределами усреднения градиентов в рамках мини-батча. Одним из способов решения этой задачи является замена вычисления градиента на «утечку среднего»:
для некоторого \(\beta \in (0, 1)\). Это эффективно заменяет мгновенный градиент на усреднённый по нескольким прошлым градиентам. \(\mathbf{v}\) называется скоростью. Она аккумулирует прошлые градиенты подобно тому, как тяжелый шар, скатывающийся по ландшафту целевой функции, интегрирует прошлые силы. Чтобы понять, что происходит более детально, раскроем \(\mathbf{v}_t\) рекурсивно в
Большие значения \(\beta\) соответствуют усреднению на длинном горизонте, тогда как малые значения \(\beta\) дают лишь незначительную коррекцию по сравнению с градиентным методом. Новая замена градиента больше не указывает направление наискорейшего спуска для конкретного объекта, а направлена в сторону взвешенного среднего прошлых градиентов. Это позволяет нам реализовать большинство преимуществ усреднения по батчу, не неся затрат на его фактический вычислительный проход. Мы вернёмся к этому процессу усреднения чуть позже и рассмотрим его более подробно.
Вышеизложенные рассуждения легли в основу того, что сейчас известно как ускоренные методы градиентной оптимизации, такие как градиентный спуск с импульсом. Они обладают дополнительным преимуществом: значительно большей эффективностью в случаях, когда задача оптимизации плохо обусловлена (то есть существуют направления, в которых прогресс значительно медленнее, чем в других, что напоминает узкое ущелье). Кроме того, они позволяют усреднять последовательные градиенты для получения более стабильных направлений спуска. Действительно, аспект ускорения, даже для задач выпуклой оптимизации без шума, является одной из ключевых причин того, почему импульс работает и почему он работает так хорошо.
Как и следовало ожидать, благодаря своей эффективности импульс является хорошо изученным объектом в оптимизации для глубокого обучения и за его пределами. См., например, прекрасную обзорную статью работы Goh (2017), содержащую углубленный анализ и интерактивную анимацию. Он был предложен в работе Polyak (1964). В работе Nesterov (2018) приведено подробное теоретическое обсуждение в контексте выпуклой оптимизации. О пользе импульса в глубоком обучении известно уже давно. См., например, обсуждение в работе Sutskever et al. (2013) для получения подробностей.
12.6.1.2. Задача с плохой обусловленностью¶
Чтобы лучше понять геометрические свойства метода импульса, мы вновь обратимся к градиентному спуску, хотя и с гораздо менее удобной целевой функцией. Напомним, что в Section 12.3 мы использовали \(f(\mathbf{x}) = x_1^2 + 2 x_2^2\), то есть умеренно искажённую эллипсоидальную целевую функцию. Мы ещё больше исказим эту функцию, растянув её в направлении \(x_1\) с помощью
Как и ранее \(f\) имеет минимум в точке \((0, 0)\). Эта функция очень плоская в направлении \(x_1\). Давайте посмотрим, что произойдет, если мы выполним градиентный спуск, как и раньше, на этой новой функции. Мы выберем скорость обучения \(0.4\).
%matplotlib inline
import torch
from d2l import torch as d2l
eta = 0.4
def f_2d(x1, x2):
return 0.1 * x1 ** 2 + 2 * x2 ** 2
def gd_2d(x1, x2, s1, s2):
return (x1 - eta * 0.2 * x1, x2 - eta * 4 * x2, 0, 0)
d2l.show_trace_2d(f_2d, d2l.train_2d(gd_2d))
По конструкции градиент в направлении \(x_2\) намного больше и изменяется гораздо быстрее, чем в горизонтальном направлении \(x_1\). Таким образом, мы оказываемся в ситуации выбора между двумя нежелательными вариантами: если мы выберем малую скорость обучения, то обеспечим, чтобы решение не расходилось в направлении \(x_2\), но будем страдать от медленной сходимости в направлении \(x_1\). И наоборот, при большой скорости обучения мы быстро продвигаемся в направлении \(x_1\), но расходимся в направлении \(x_2\). Приведённый ниже пример иллюстрирует, что происходит даже при незначительном увеличении скорости обучения с \(0.4\) до \(0.6\). Сходимость в направлении \(x_1\) улучшается, но общее качество решения становится значительно хуже.
eta = 0.6
d2l.show_trace_2d(f_2d, d2l.train_2d(gd_2d))
12.6.1.3. Метод импульса¶
Метод импульса позволяет решить проблему градиентного спуска, описанную выше. Если посмотреть на траекторию оптимизации, то интуитивно кажется, что усреднение градиентов за прошлые шаги будет эффективным. Ведь в направлении \(x_1\) это позволит аккумулировать хорошо согласованные градиенты, увеличивая тем самым расстояние, проходимое за каждый шаг. И наоборот, в направлении \(x_2\), где градиенты осциллируют, усреднённый градиент уменьшит размер шага из-за взаимного погашения осцилляций. Использование \(\mathbf{v}_t\) вместо градиента \(\mathbf{g}_t\) даёт следующие уравнения обновления:
Заметим, что при \(\beta = 0\) мы получаем обычный градиентный спуск. Прежде чем углубляться в математические свойства, давайте кратко рассмотрим, как алгоритм ведёт себя на практике.
def momentum_2d(x1, x2, v1, v2):
v1 = beta * v1 + 0.2 * x1
v2 = beta * v2 + 4 * x2
return x1 - eta * v1, x2 - eta * v2, v1, v2
eta, beta = 0.6, 0.5
d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
Как мы видим, даже при той же скорости обучения, что и раньше, метод импульса всё равно сходится хорошо. Давайте посмотрим, что произойдёт, если мы уменьшим параметр импульса. Уменьшение его вдвое до \(\beta = 0.25\) приводит к траектории, которая практически не сходится. Тем не менее, это значительно лучше, чем без импульса (когда решение расходится).
eta, beta = 0.6, 0.25
d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
Заметим, что метод импульса можно комбинировать со стохастическим градиентным спуском и, в частности, со стохастическим градиентным спуском по мини-батчам. Единственное изменение заключается в том, что в этом случае мы заменяем градиенты \(\mathbf{g}_{t, t-1}\) на \(\mathbf{g}_t\). Наконец, для удобства инициализируем \(\mathbf{v}_0 = 0\) в момент времени \(t=0\). Давайте посмотрим, что именно делает затухающее усреднение с обновлениями.
12.6.1.4. Эффективный вес примера¶
Вспомним, что \(\mathbf{v}_t = \sum_{\tau = 0}^{t-1} \beta^{\tau} \mathbf{g}_{t-\tau, t-\tau-1}\). В пределе эти слагаемые дают в сумме \(\sum_{\tau=0}^\infty \beta^\tau = \frac{1}{1-\beta}\). Иными словами, вместо шага размера \(\eta\) в градиентном спуске или стохастическом градиентном спуске мы делаем шаг размера \(\frac{\eta}{1-\beta}\), одновременно работая с потенциально более корректным направлением спуска. Это два преимущества в одном. Чтобы проиллюстрировать, как ведёт себя взвешивание при различных значениях \(\beta\), рассмотрим диаграмму ниже.
d2l.set_figsize()
betas = [0.95, 0.9, 0.6, 0]
for beta in betas:
x = torch.arange(40).detach().numpy()
d2l.plt.plot(x, beta ** x, label=f'beta = {beta:.2f}')
d2l.plt.xlabel('time')
d2l.plt.legend();
12.6.2. Практические эксперименты¶
Давайте посмотрим, как работает импульс на практике, то есть в контексте использования с подходящим оптимизатором. Для этого нам потребуется несколько более масштабируемая реализация.
12.6.2.1. Реализация с нуля¶
В отличие от стохастического градиентного спуска по мини-батчам, метод
импульса требует хранения набора вспомогательных переменных, а именно
скоростей. Они имеют ту же форму, что и градиенты (и переменные задачи
оптимизации). В приведённой ниже реализации мы называем эти переменные
states.
def init_momentum_states(feature_dim):
v_w = torch.zeros((feature_dim, 1))
v_b = torch.zeros(1)
return (v_w, v_b)
def sgd_momentum(params, states, hyperparams):
for p, v in zip(params, states):
with torch.no_grad():
v[:] = hyperparams['momentum'] * v + p.grad
p[:] -= hyperparams['lr'] * v
p.grad.data.zero_()
Давайте посмотрим, как это работает на практике.
def train_momentum(lr, momentum, num_epochs=2):
d2l.train_ch11(sgd_momentum, init_momentum_states(feature_dim),
{'lr': lr, 'momentum': momentum}, data_iter,
feature_dim, num_epochs)
data_iter, feature_dim = d2l.get_data_ch11(batch_size=10)
train_momentum(0.02, 0.5)
Когда мы увеличиваем гиперпараметр импульса momentum до 0,9,
эффективный размер примера становится значительно больше
\(\frac{1}{1 - 0.9} = 10\). Мы немного уменьшаем скорость обучения
до \(0.01\), чтобы держать ситуацию под контролем.
train_momentum(0.01, 0.9)
Дальнейшее уменьшение скорости обучения решает любые проблемы, связанные с негладкими задачами оптимизации. Установка её значения в \(0.005\) обеспечивает хорошие свойства сходимости.
train_momentum(0.005, 0.9)
12.6.2.2. Краткая реализация¶
В Gluon практически ничего настраивать не нужно, поскольку стандартный
sgd оптимизатор уже включает в себя импульс. Задание соответствующих
параметров даёт очень похожую траекторию.
trainer = torch.optim.SGD
d2l.train_concise_ch11(trainer, {'lr': 0.005, 'momentum': 0.9}, data_iter)
12.6.3. Теоретический анализ¶
До сих пор двумерный пример \(f(x) = 0.1 x_1^2 + 2 x_2^2\) казался довольно искусственным. Мы сейчас увидим, что он на самом деле достаточно хорошо отражает тип задач, с которыми можно столкнуться, по крайней мере в случае минимизации выпуклых квадратичных целевых функций.
12.6.3.1. Выпуклые квадратичные функции¶
Рассмотрим функцию
Это общая квадратичная функция. Для положительно определённых матриц \(\mathbf{Q} \succ 0\), то есть для матриц с положительными собственными значениями, она имеет минимум в точке \(\mathbf{x}^* = -\mathbf{Q}^{-1} \mathbf{c}\) со значением \(b - \frac{1}{2} \mathbf{c}^\top \mathbf{Q}^{-1} \mathbf{c}\). Следовательно, мы можем переписать \(h\) как
Градиент задаётся выражением \(\partial_{\mathbf{x}} h(\mathbf{x}) = \mathbf{Q} (\mathbf{x} - \mathbf{Q}^{-1} \mathbf{c})\). То есть он равен расстоянию между \(\mathbf{x}\) и точкой минимума, умноженному на \(\mathbf{Q}\). Следовательно, скорость также является линейной комбинацией членов \(\mathbf{Q} (\mathbf{x}_t - \mathbf{Q}^{-1} \mathbf{c})\).
Поскольку \(\mathbf{Q}\) положительно определена, её можно разложить на собственный базис с помощью \(\mathbf{Q} = \mathbf{O}^\top \boldsymbol{\Lambda} \mathbf{O}\) для ортогональной (поворотной) матрицы \(\mathbf{O}\) и диагональной матрицы \(\boldsymbol{\Lambda}\) положительных собственных значений. Это позволяет выполнить замену переменных с \(\mathbf{x}\) на \(\mathbf{z} \stackrel{\textrm{def}}{=} \mathbf{O} (\mathbf{x} - \mathbf{Q}^{-1} \mathbf{c})\), чтобы получить гораздо более простое выражение:
Здесь \(b' = b - \frac{1}{2} \mathbf{c}^\top \mathbf{Q}^{-1} \mathbf{c}\). Поскольку \(\mathbf{O}\) — это лишь ортогональная матрица, это не искажает градиенты значимым образом. Если выразить это через \(\mathbf{z}\), градиентный спуск принимает вид
Важно отметить, что градиентный спуск не смешивает различные собственные подпространства. Иными словами, если выразить задачу оптимизации через собственную систему \(\mathbf{Q}\), то она решается покомпонентно. Это также верно для
Таким образом, мы доказали следующую теорему: градиентный спуск с импульсом и без него для выпуклой квадратичной функции распадается на координатную оптимизацию в направлении собственных векторов квадратичной матрицы.
12.6.3.2. Скалярные функции¶
Исходя из вышеизложенного, рассмотрим, что происходит при минимизации функции \(f(x) = \frac{\lambda}{2} x^2\). Для градиентного спуска получаем
Как только \(|1 - \eta \lambda| < 1\) эта оптимизация сходится с экспоненциальной скоростью, поскольку после \(t\) шагов мы получаем \(x_t = (1 - \eta \lambda)^t x_0\). Это показывает, как скорость сходимости изначально возрастает при увеличении скорости обучения \(\eta\), пока не будет достигнуто значение \(\eta \lambda = 1\). За этим пределом происходит расходимость, и для \(\eta \lambda > 2\) задача оптимизации расходится.
lambdas = [0.1, 1, 10, 19]
eta = 0.1
d2l.set_figsize((6, 4))
for lam in lambdas:
t = torch.arange(20).detach().numpy()
d2l.plt.plot(t, (1 - eta * lam) ** t, label=f'lambda = {lam:.2f}')
d2l.plt.xlabel('time')
d2l.plt.legend();
Для анализа сходимости в случае импульса мы начинаем с переписывания уравнений обновления через две скалярные величины: одну для \(x\) и одну для скорости \(v\). Это даёт:
Мы использовали \(\mathbf{R}\) для обозначения \(2 \times 2\), определяющего поведение сходимости. После \(t\) шагов первоначальный выбор \([v_0, x_0]\) превращается в \(\mathbf{R}(\beta, \eta, \lambda)^t [v_0, x_0]\). Следовательно, именно от собственных значений \(\mathbf{R}\) зависит скорость сходимости. См. публикацию в Distill от Goh (2017) для отличной анимации и Flammarion and Bach (2015) для подробного анализа. Можно показать, что скорость \(0 < \eta \lambda < 2 + 2 \beta\) сходится. Это более широкий диапазон допустимых параметров по сравнению с \(0 < \eta \lambda < 2\) для градиентного спуска. Это также указывает на то, что в целом желательны большие значения \(\beta\). Дальнейшие детали требуют значительного объёма технических подробностей, и мы рекомендуем заинтересованному читателю обратиться к первоисточникам.
12.6.4. В этом разделе мы ввели скалярные функции и обсудили их производные.¶
Импульс заменяет градиенты затухающим средним по прошлым градиентам. Это значительно ускоряет сходимость.
Это желательно как для градиентного спуска без шума, так и для (зашумленного) стохастического градиентного спуска.
Импульс предотвращает застой процесса оптимизации, который гораздо чаще возникает при стохастическом градиентном спуске.
Эффективное число градиентов определяется как \(\frac{1}{1-\beta}\) из-за экспоненциального понижения весов прошлых данных.
В случае выпуклых квадратичных задач это можно проанализировать подробно и явно.
Реализация довольно проста, но требует хранения дополнительного вектора состояния (скорости \(\mathbf{v}\)).
12.6.5. Упражнения¶
Используйте другие комбинации гиперпараметров импульса и скоростей обучения, наблюдайте и анализируйте различные результаты экспериментов.
Попробуйте применить градиентный спуск и метод импульса к квадратичной задаче с несколькими собственными значениями, например, \(f(x) = \frac{1}{2} \sum_i \lambda_i x_i^2\), таким как \(\lambda_i = 2^{-i}\). Постройте график, показывающий, как уменьшаются значения \(x\) при начальной инициализации \(x_i = 1\).
Выведите минимальное значение и точку минимума для \(h(\mathbf{x}) = \frac{1}{2} \mathbf{x}^\top \mathbf{Q} \mathbf{x} + \mathbf{x}^\top \mathbf{c} + b\).
Что изменится при выполнении стохастического градиентного спуска с импульсом? Что произойдет при использовании мини-батча стохастического градиентного спуска с импульсом? Поэкспериментируйте с параметрами.