12.7. Adagrad¶
Начнем с рассмотрения задач обучения, в которых признаки встречаются редко.
12.7.1. Разреженные признаки и скорости обучения¶
Представьте, что мы обучаем языковую модель. Чтобы достичь высокой точности, мы обычно хотим уменьшать скорость обучения по мере продолжения обучения, обычно со скоростью \(\mathcal{O}(t^{-\frac{1}{2}})\) или медленнее. Теперь рассмотрим модель, обучающуюся на разреженных признаках, то есть на признаках, которые встречаются лишь изредка. Это характерно для естественного языка, например, вероятность встретить слово preconditioning гораздо ниже, чем learning. Однако это также часто встречается в других областях, таких как вычислительная реклама и персонализированная коллаборативная фильтрация. В конце концов, существует множество вещей, которые интересны лишь небольшому числу людей.
Параметры, связанные с редкими признаками, получают значимые обновления только тогда, когда эти признаки встречаются. При использовании убывающей скорости обучения может возникнуть ситуация, когда параметры для частых признаков быстро сходятся к своим оптимальным значениям, тогда как для редких признаков мы ещё не наблюдали их достаточно часто, чтобы определить их оптимальные значения. Иными словами, скорость обучения либо убывает слишком медленно для частых признаков, либо слишком быстро для редких.
Один из возможных способов решения этой проблемы — подсчитывать количество наблюдений конкретного признака и использовать этот счётчик как «часы» для настройки скорости обучения. То есть вместо выбора скорости обучения вида \(\eta = \frac{\eta_0}{\sqrt{t + c}}\) можно использовать \(\eta_i = \frac{\eta_0}{\sqrt{s(i, t) + c}}\). Здесь \(s(i, t)\) обозначает количество ненулевых значений признака \(i\), которые мы наблюдали до момента времени \(t\). Это довольно легко реализовать без каких-либо существенных накладных расходов. Однако этот подход не работает, если данные не являются строго разреженными, а просто содержат градиенты, которые часто очень малы и лишь изредка бывают большими. В конце концов, неясно, где именно следует проводить границу между признаком, который считается наблюдаемым, и тем, который таковым не является.
Adagrad, описанный в Duchi et al. (2011), решает эту проблему, заменяя довольно грубый счётчик \(s(i, t)\) суммой квадратов ранее наблюдавшихся градиентов. В частности, он использует \(s(i, t+1) = s(i, t) + \left(\partial_i f(\mathbf{x})\right)^2\) для настройки скорости обучения. Это даёт два преимущества: во-первых, нам больше не нужно решать, когда именно градиент становится достаточно большим. Во-вторых, масштабирование происходит автоматически в зависимости от величины градиентов. Координаты, для которых градиенты обычно велики, существенно уменьшаются, тогда как координаты с малыми градиентами обрабатываются гораздо мягче. На практике это приводит к очень эффективной процедуре оптимизации для задач вычислительной рекламы и смежных областей. Однако при этом скрываются некоторые дополнительные преимущества, присущие Adagrad, которые лучше всего понимаются в контексте преусловливания.
12.7.2. Предобусловливание¶
Выпуклые задачи оптимизации удобны для анализа характеристик алгоритмов. В конце концов, для большинства невыпуклых задач трудно вывести содержательные теоретические гарантии, однако интуиция и понимание часто переносятся. Рассмотрим задачу минимизации \(f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^\top \mathbf{Q} \mathbf{x} + \mathbf{c}^\top \mathbf{x} + b\).
Как мы видели в Section 12.6, эту задачу можно переписать через её спектральное разложение \(\mathbf{Q} = \mathbf{U}^\top \boldsymbol{\Lambda} \mathbf{U}\), чтобы получить значительно упрощённую задачу, где каждая координата может быть решена отдельно:
Здесь мы использовали \(\bar{\mathbf{x}} = \mathbf{U} \mathbf{x}\) и, следовательно, \(\bar{\mathbf{c}} = \mathbf{U} \mathbf{c}\). Минимизатором модифицированной задачи является \(\bar{\mathbf{x}} = -\boldsymbol{\Lambda}^{-1} \bar{\mathbf{c}}\), а минимальное значение равно \(-\frac{1}{2} \bar{\mathbf{c}}^\top \boldsymbol{\Lambda}^{-1} \bar{\mathbf{c}} + b\). Это вычисляется гораздо проще, поскольку \(\boldsymbol{\Lambda}\) — это диагональная матрица, содержащая собственные значения \(\mathbf{Q}\).
Если мы слегка возмутим \(\mathbf{c}\), мы хотели бы обнаружить лишь незначительные изменения в точке минимума \(f\). К сожалению, это не так. Хотя небольшие изменения в \(\mathbf{c}\) приводят к столь же незначительным изменениям в \(\bar{\mathbf{c}}\), это не относится к точке минимума \(f\) (и, соответственно, к \(\bar{f}\)). Когда собственные значения \(\boldsymbol{\Lambda}_i\) велики, мы наблюдаем лишь малые изменения в \(\bar{x}_i\) и в минимальном значении \(\bar{f}\). Напротив, при малых \(\boldsymbol{\Lambda}_i\) изменения в \(\bar{x}_i\) могут быть драматическими. Отношение наибольшего и наименьшего собственного значения называется числом обусловленности задачи оптимизации.
Если число обусловленности \(\kappa\) велико, точно решить задачу оптимизации сложно. Необходимо обеспечить точность при работе с широким диапазоном значений. Наш анализ приводит к очевидному, хотя и несколько наивному вопросу: не могли бы мы просто «исправить» проблему, преобразовав пространство так, чтобы все собственные значения стали \(1\). Теоретически это довольно просто: нам нужны только собственные значения и собственные векторы \(\mathbf{Q}\), чтобы привести задачу из \(\mathbf{x}\) к задаче в \(\mathbf{z} \stackrel{\textrm{def}}{=} \boldsymbol{\Lambda}^{\frac{1}{2}} \mathbf{U} \mathbf{x}\). В новой системе координат \(\mathbf{x}^\top \mathbf{Q} \mathbf{x}\) можно упростить до \(\|\mathbf{z}\|^2\). Однако это предложение довольно непрактично. Вычисление собственных значений и собственных векторов в целом намного дороже, чем решение самой задачи.
Хотя точное вычисление собственных значений может быть дорогостоящим, их приближённая оценка, пусть и не очень точная, уже может оказаться гораздо лучше, чем полное отсутствие действий. В частности, мы можем использовать диагональные элементы \(\mathbf{Q}\) и соответствующим образом масштабировать их. Это намного дешевле, чем вычисление собственных значений.
В этом случае мы имеем \(\tilde{\mathbf{Q}}_{ij} = \mathbf{Q}_{ij} / \sqrt{\mathbf{Q}_{ii} \mathbf{Q}_{jj}}\) и, в частности, \(\tilde{\mathbf{Q}}_{ii} = 1\) для всех \(i\). В большинстве случаев это значительно улучшает число обусловленности. Например, в рассмотренных ранее случаях это полностью устраняет рассматриваемую проблему, поскольку задача выровнена по осям.
К сожалению, мы сталкиваемся с ещё одной проблемой: в глубоком обучении мы обычно даже не имеем доступа ко второй производной целевой функции: для \(\mathbf{x} \in \mathbb{R}^d\) вторая производная даже по мини-батчу может требовать \(\mathcal{O}(d^2)\) памяти и вычислений, что делает её практическое вычисление невозможным. Гениальная идея Adagrad заключается в использовании прокси-величины для этой труднодоступной диагонали гессиана, которая относительно дешева в вычислении и эффективна — это величина самого градиента.
Чтобы понять, почему это работает, рассмотрим \(\bar{f}(\bar{\mathbf{x}})\). У нас есть
где \(\bar{\mathbf{x}}_0\) — это минимум функции \(\bar{f}\). Следовательно, величина градиента зависит как от \(\boldsymbol{\Lambda}\), так и от расстояния до оптимума. Если бы \(\bar{\mathbf{x}} - \bar{\mathbf{x}}_0\) не менялось, этого было бы достаточно. В конце концов, в этом случае величины градиента \(\partial_{\bar{\mathbf{x}}} \bar{f}(\bar{\mathbf{x}})\) вполне достаточно. Поскольку AdaGrad — это алгоритм стохастического градиентного спуска, мы будем наблюдать градиенты с ненулевой дисперсией даже в точке оптимума. В результате мы можем безопасно использовать дисперсию градиентов в качестве дешевой аппроксимации масштаба гессиана. Тщательный анализ выходит за рамки этого раздела (он занял бы несколько страниц). Подробности можно найти в (Duchi et al., 2011).
12.7.3. Алгоритм¶
Давайте формализуем обсуждение, приведённое выше. Мы используем переменную \(\mathbf{s}_t\) для накопления дисперсии градиента из прошлых шагов следующим образом.
Здесь операции применяются покомпонентно. То есть \(\mathbf{v}^2\) состоит из элементов \(v_i^2\). Аналогично, \(\frac{1}{\sqrt{v}}\) состоит из элементов \(\frac{1}{\sqrt{v_i}}\), а \(\mathbf{u} \cdot \mathbf{v}\) — из элементов \(u_i v_i\). Как и прежде, \(\eta\) — это скорость обучения, а \(\epsilon\) — аддитивная константа, которая гарантирует, что мы не будем делить на \(0\). Наконец, инициализируем \(\mathbf{s}_0 = \mathbf{0}\).
Как и в случае с импульсом, нам необходимо отслеживать вспомогательную переменную, чтобы обеспечить индивидуальную скорость обучения для каждой координаты. Это не увеличивает вычислительные затраты алгоритма Adagrad по сравнению с SGD, поскольку основные затраты обычно связаны с вычислением \(l(y_t, f(\mathbf{x}_t, \mathbf{w}))\) и его производной.
Обратите внимание, что накопление квадратов градиентов в \(\mathbf{s}_t\) означает, что \(\mathbf{s}_t\) растёт по сути линейно (на практике немного медленнее линейно, поскольку градиенты изначально уменьшаются). Это приводит к снижению скорости обучения \(\mathcal{O}(t^{-\frac{1}{2}})\), хотя и с учётом каждой координаты отдельно. Для выпуклых задач этого вполне достаточно. Однако в глубоком обучении мы, возможно, захотим уменьшать скорость обучения более плавно. Это привело к появлению ряда вариантов Adagrad, которые мы обсудим в последующих главах. А пока давайте посмотрим, как он ведёт себя на квадратичной выпуклой задаче. Мы используем ту же задачу, что и раньше:
Мы собираемся реализовать алгоритм Adagrad, используя ту же скорость обучения, что и ранее, т. е. \(\eta = 0.4\). Как мы видим, траектория изменения независимой переменной становится более плавной. Однако из-за кумулятивного эффекта \(\boldsymbol{s}_t\) скорость обучения непрерывно уменьшается, поэтому на поздних этапах итераций независимая переменная изменяется не так сильно.
%matplotlib inline
import math
import torch
from d2l import torch as d2l
def adagrad_2d(x1, x2, s1, s2):
eps = 1e-6
g1, g2 = 0.2 * x1, 4 * x2
s1 += g1 ** 2
s2 += g2 ** 2
x1 -= eta / math.sqrt(s1 + eps) * g1
x2 -= eta / math.sqrt(s2 + eps) * g2
return x1, x2, s1, s2
def f_2d(x1, x2):
return 0.1 * x1 ** 2 + 2 * x2 ** 2
eta = 0.4
d2l.show_trace_2d(f_2d, d2l.train_2d(adagrad_2d))
По мере увеличения скорости обучения до \(2\) мы наблюдаем значительно лучшее поведение. Это уже указывает на то, что уменьшение скорости обучения может быть слишком агрессивным, даже в случае отсутствия шума, и нам необходимо обеспечить корректную сходимость параметров.
eta = 2
d2l.show_trace_2d(f_2d, d2l.train_2d(adagrad_2d))
12.7.4. Реализация с нуля¶
Как и метод импульса, Adagrad требует хранения переменной состояния той же формы, что и параметры.
def init_adagrad_states(feature_dim):
s_w = torch.zeros((feature_dim, 1))
s_b = torch.zeros(1)
return (s_w, s_b)
def adagrad(params, states, hyperparams):
eps = 1e-6
for p, s in zip(params, states):
with torch.no_grad():
s[:] += torch.square(p.grad)
p[:] -= hyperparams['lr'] * p.grad / torch.sqrt(s + eps)
p.grad.data.zero_()
По сравнению с экспериментом в Section 12.5 мы используем большую скорость обучения для обучения модели.
data_iter, feature_dim = d2l.get_data_ch11(batch_size=10)
d2l.train_ch11(adagrad, init_adagrad_states(feature_dim),
{'lr': 0.1}, data_iter, feature_dim);
12.7.5. Краткая реализация¶
Используя объект Trainer алгоритма adagrad, мы можем вызвать
алгоритм Adagrad в Gluon.
trainer = torch.optim.Adagrad
d2l.train_concise_ch11(trainer, {'lr': 0.1}, data_iter)
12.7.6. Итоги¶
Adagrad динамически уменьшает скорость обучения для каждой координаты в отдельности.
Он использует величину градиента для регулировки скорости достижения прогресса: координаты с большими градиентами корректируются с использованием меньшей скорости обучения.
Вычисление точной второй производной обычно невыполнимо в задачах глубокого обучения из-за ограничений памяти и вычислительных ресурсов. Градиент может служить полезной аппроксимацией.
Если задача оптимизации имеет достаточно неравномерную структуру, Adagrad может помочь смягчить искажения.
Adagrad особенно эффективен для разреженных признаков, где скорость обучения должна уменьшаться медленнее для редко встречающихся терминов.
На задачах глубокого обучения алгоритм Adagrad иногда слишком агрессивно снижает скорость обучения. Мы обсудим стратегии смягчения этого эффекта в контексте Section 12.10.
12.7.7. Упражнения¶
Докажите, что для ортогональной матрицы \(\mathbf{U}\) и вектора \(\mathbf{c}\) выполняется следующее: \(\|\mathbf{c} - \mathbf{\delta}\|_2 = \|\mathbf{U} \mathbf{c} - \mathbf{U} \mathbf{\delta}\|_2\). Почему это означает, что величина возмущений не изменяется при ортогональном преобразовании переменных?
Попробуйте использовать Adagrad для \(f(\mathbf{x}) = 0.1 x_1^2 + 2 x_2^2\), а также для целевой функции, повернутой на 45 градусов, то есть для \(f(\mathbf{x}) = 0.1 (x_1 + x_2)^2 + 2 (x_1 - x_2)^2\). Ведёт ли он себя иначе?
Докажите теорему о кругах Гершгорина, которая утверждает, что собственные значения \(\lambda_i\) матрицы \(\mathbf{M}\) удовлетворяют условию \(|\lambda_i - \mathbf{M}_{jj}| \leq \sum_{k \neq j} |\mathbf{M}_{jk}|\) хотя бы для одного выбора \(j\).
Что говорит теорема Гершгорина о собственных значениях предварительно нормированной по диагонали матрицы \(\textrm{diag}^{-\frac{1}{2}}(\mathbf{M}) \mathbf{M} \textrm{diag}^{-\frac{1}{2}}(\mathbf{M})\)?
Попробуйте использовать Adagrad для полноценной глубокой сети, например, Section 7.6, обученной на Fashion-MNIST.
Как нужно изменить Adagrad, чтобы добиться менее агрессивного уменьшения скорости обучения?