11.7 Алгоритм AdaGrad

Начнём с вопроса, который редко возникает при обучении признаков.

11.7.1 Разреженные признаки и скорость обучения

Предположим, мы обучаем языковую модель. Чтобы добиться хорошей точности, мы обычно хотим уменьшать скорость обучения по ходу обучения, примерно как $\mathcal{O}(t^{-\frac{1}{2}})$ или медленнее. Теперь рассмотрим обучение модели на разреженных признаках, то есть признаках, которые встречаются лишь изредка. Это типично для естественного языка. Например, слово «предобусловливание» встречается гораздо реже, чем слово «обучение». Однако такая ситуация характерна и для других областей, например, для компьютерной рекламы и персонализированной совместной фильтрации.

Параметры, связанные с редкими признаками, получают осмысленное обновление только тогда, когда эти признаки встречаются. При уменьшающейся скорости обучения может случиться так, что параметры частых признаков довольно быстро сходятся к оптимальным значениям, а для редких признаков мы всё ещё не накопили достаточно наблюдений, чтобы определить их оптимальные значения. Иными словами, скорость обучения либо снижается слишком медленно для частых признаков, либо слишком быстро для редких.

Один из способов решить эту проблему — подсчитывать, сколько раз мы видели конкретный признак, и использовать это число для корректировки скорости обучения. То есть вместо $\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, которое легче увидеть в контексте предобусловливания.

11.7.2 Предобусловливание

Задачи выпуклой оптимизации полезны для анализа свойств алгоритмов. В самом деле, для большинства невыпуклых задач получить содержательные теоретические гарантии трудно, но интуиция и понимание часто переносятся на них. Рассмотрим задачу минимизации $f(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^{\top }\mathbf{Qx}+{\mathbf{c}}^{\top }\mathbf{x}+b$.

Как и в разделе 11.6, мы можем переписать задачу, используя её разложение по собственным значениям $\mathbf{Q}={\mathbf{U}}^{\top }\mathbf{\Lambda }\mathbf{U}$, и получить гораздо более простую задачу, в которой каждую координату можно найти отдельно:

$$f(\mathbf{x})=\bar{f}(\bar{\mathbf{x}})=\frac{1}{2}{\bar{\mathbf{x}}}^{\top }\mathbf{\Lambda }\bar{\mathbf{x}}+{\bar{\mathbf{c}}}^{\top }\bar{\mathbf{x}}+b.$$

Здесь мы использовали $\bar{\mathbf{x}}=\mathbf{Ux}$, а значит, и $\bar{\mathbf{c}}=\mathbf{Uc}$. Оптимум преобразованной задачи равен $\bar{\mathbf{x}}=-{\mathbf{\Lambda }}^{-1}\bar{\mathbf{c}}$, а минимальное значение — $-\frac{1}{2}{\bar{\mathbf{c}}}^{\top }{\mathbf{\Lambda }}^{-1}\bar{\mathbf{c}}+b$. Это легче вычислить, поскольку $\mathbf{\Lambda }$ — диагональная матрица с собственными значениями $\mathbf{Q}$.

Если немного возмутить $\mathbf{c}$, мы ожидаем лишь небольших изменений минимизатора $f$. К сожалению, это не так. Хотя малое изменение $\mathbf{c}$ приводит к такому же малому изменению $\bar{\mathbf{c}}$, минимизатор $f$ (а значит, и $\bar{f}$) ведёт себя иначе. Всякий раз, когда собственное значение ${\mathbf{\Lambda }}_i$ велико, мы видим лишь небольшие изменения ${\bar{x}}_i$ и минимального значения $\bar{f}$. Напротив, для малых ${\mathbf{\Lambda }}_i$ изменения ${\bar{x}}_i$ могут быть резкими. Отношение наибольшего собственного значения к наименьшему называют числом обусловленности (condition number) задачи оптимизации.

$$\kappa =\frac{{\mathbf{\Lambda }}_1}{{\mathbf{\Lambda }}_d}.$$

Если число обусловленности $\kappa$ велико, точно решить задачу оптимизации трудно. Нужно быть осторожным, когда диапазон собственных значений оказывается очень широким: нельзя ли просто «исправить» проблему, деформировав пространство так, чтобы все собственные значения стали равны $1$? Теоретически это несложно: достаточно собственных значений и собственных векторов $\mathbf{Q}$, чтобы привести задачу от $\mathbf{x}$ к $\mathbf{z}:={\mathbf{\Lambda }}^{\frac{1}{2}}\mathbf{Ux}$. В новой системе координат ${\mathbf{x}}^{\top }\mathbf{Qx}$ сводится к $\Vert \mathbf{z}{\Vert }^2$. К сожалению, эта идея малопригодна на практике: вычисление собственных значений и собственных векторов обычно гораздо дороже, чем решение исходной задачи.

Хотя точное вычисление собственных значений может быть дорогим, даже грубая оценка и последующее использование этих значений может быть значительно лучше, чем отсутствие каких-либо действий. В частности, можно взять диагональные элементы $\mathbf{Q}$ и соответствующим образом их перемасштабировать. Это обходится гораздо дешевле вычисления собственных значений.

$$\tilde{\mathbf{Q}}={\mathrm{diag}}^{-\frac{1}{2}}(\mathbf{Q})\mathbf{Q}{\mathrm{diag}}^{-\frac{1}{2}}(\mathbf{Q}).$$

В этом случае ${\tilde{\mathbf{Q}}}_{ij}={\mathbf{Q}}_{ij}/\sqrt{{\mathbf{Q}}_{ii}{\mathbf{Q}}_{jj}}$, и, в частности, для всех $i$ выполняется ${\tilde{\mathbf{Q}}}_{ii}=1$. В большинстве случаев это значительно упрощает число обусловленности. Например, в рассмотренном ранее примере это полностью устраняет проблему, поскольку задача выровнена по осям.

К сожалению, есть и другая проблема: в глубоком обучении мы обычно даже не можем вычислить вторые производные целевой функции. Для $\mathbf{x}\in {\mathbb{R}}^d$ даже на минибатче для вычисления вторых производных может понадобиться $\mathcal{O}(d^2)$ памяти, что делает подход практически невозможным. Остроумная идея AdaGrad состоит в том, чтобы использовать в качестве суррогата диагональ матрицы Гессе (Hessian), которую относительно легко вычислить и которая эффективна.

Чтобы понять, как это работает, посмотрим на $\bar{f}(\bar{\mathbf{x}})$. Имеем

$${\partial }_{\bar{\mathbf{x}}}\bar{f}(\bar{\mathbf{x}})=\mathbf{\Lambda }\bar{\mathbf{x}}+\bar{\mathbf{c}}=\mathbf{\Lambda }\left(\bar{\mathbf{x}}-{\bar{\mathbf{x}}}_0\right),$$

где ${\bar{\mathbf{x}}}_0$ — оптимизатор $\bar{f}$. Таким образом, величина градиента определяется $\mathbf{\Lambda }$ и разницей с оптимальным значением. Если бы $\bar{\mathbf{x}}-{\bar{\mathbf{x}}}_0$ не менялось, этого было бы достаточно. В самом деле, в таком случае величины градиента ${\partial }_{\bar{\mathbf{x}}}\bar{f}(\bar{\mathbf{x}})$ хватало бы для нахождения решения. Поскольку AdaGrad — это алгоритм стохастического градиентного спуска, мы будем видеть градиенты с ненулевой дисперсией даже в оптимальной точке. Поэтому можно смело использовать дисперсию градиента в качестве дешёвой замены масштабу матрицы Гессе. Подробный анализ (его объяснение заняло бы несколько страниц) выходит за рамки этого раздела; читателю стоит обратиться к работе (Duchi et al., 2011).

11.7.3 Алгоритм

Продолжим рассуждение и перейдём к формальному описанию. Введём переменную ${\mathbf{s}}_t$, которая накапливает дисперсии прошлых градиентов:

$$\begin{array}{rl}{\mathbf{g}}_t& ={\partial }_{\mathbf{w}}l(y_t,f({\mathbf{x}}_t,\mathbf{w})),\\ {\mathbf{s}}_t& ={\mathbf{s}}_{t-1}+{\mathbf{g}}_t^2,\\ {\mathbf{w}}_t& ={\mathbf{w}}_{t-1}-\frac{\eta }{\sqrt{{\mathbf{s}}_t+ϵ}}\cdot {\mathbf{g}}_t.\end{array}$$

Здесь все операции применяются поэлементно. То есть ${\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$ — скорость обучения, а $ϵ$ — константа, добавляемая для численной устойчивости, чтобы мы не делили на $0$. Наконец, инициализируем ${\mathbf{s}}_0=0$.

Так же, как в методе импульса нам нужна вспомогательная переменная, в алгоритме AdaGrad мы разрешаем каждой координате иметь собственную скорость обучения. По сравнению с SGD это заметно не увеличивает стоимость AdaGrad, поскольку основные вычисления приходятся на $l(y_t,f({\mathbf{x}}_t,\mathbf{w}))$ и её производные.

Заметим, что накопление квадратов градиентов в ${\mathbf{s}}_t$ означает, что ${\mathbf{s}}_t$ растёт в основном линейно (на самом деле чуть медленнее, поскольку градиенты с самого начала уменьшаются). Это даёт скорость обучения $\mathcal{O}(t^{-\frac{1}{2}})$, но настроенную отдельно для каждой координаты. Для выпуклых задач этого вполне достаточно. Однако в глубоком обучении может понадобиться уменьшать скорость обучения медленнее. Это привело к появлению многих вариантов AdaGrad, которые мы рассмотрим в следующих разделах. А пока посмотрим, как алгоритм работает на квадратичной выпуклой задаче. Используем ту же функцию:

$$f(\mathbf{x})=0.1x_1^2+2x_2^2.$$

Реализуем AdaGrad с той же скоростью обучения, что и раньше, $\eta =0.4$. Видно, что траектория аргумента получается более гладкой. Однако из-за накопления ${\mathbf{s}}_t$ скорость обучения непрерывно уменьшается, поэтому на поздних итерациях аргумент движется на небольшие расстояния.

%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

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))

11.7.4 Реализация с нуля

Как и в методе импульса, AdaGrad требует хранения переменной состояния для каждого параметра, имеющей ту же форму, что и сам параметр.

def init_adagrad_states(feature_dim):
    s_w = d2l.zeros((feature_dim, 1))
    s_b = d2l.zeros(1)
    return (s_w, s_b)

def adagrad(params, states, hyperparams):
    eps = 1e-6
    for p, s in zip(params, states):
        s[:] += np.square(p.grad)
        p[:] -= hyperparams['lr'] * p.grad / np.sqrt(s + eps)

def init_adagrad_states(feature_dim):
    s_w = d2l.zeros((feature_dim, 1))
    s_b = d2l.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_()

def init_adagrad_states(feature_dim):
    s_w = tf.Variable(d2l.zeros((feature_dim, 1)))
    s_b = tf.Variable(d2l.zeros(1))
    return (s_w, s_b)

def adagrad(params, grads, states, hyperparams):
    eps = 1e-6
    for p, s, g in zip(params, states, grads):
        s[:].assign(s + tf.math.square(g))
        p[:].assign(p - hyperparams['lr'] * g / tf.math.sqrt(s + eps))

def init_adagrad_states(feature_dim):
    s_w = d2l.zeros((feature_dim, 1))
    s_b = d2l.zeros(shape=(1, ))
    return (s_w, s_b)

def adagrad(params, states, hyperparams):
    a = []
    eps = 1e-6
    for p, s in zip(params, states):
        with paddle.no_grad():
            s[:] += paddle.square(p.grad)
            p[:] -= hyperparams['lr'] * p.grad / paddle.sqrt(s + eps)
        p.grad.zero_()
        a.append(p)
    return a

По сравнению с экспериментами из раздела 11.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);

11.7.5 Краткая реализация

Мы можем использовать алгоритм AdaGrad, уже реализованный во фреймворке глубокого обучения, для обучения модели.

d2l.train_concise_ch11('adagrad', {'learning_rate': 0.1}, data_iter)

trainer = torch.optim.Adagrad
d2l.train_concise_ch11(trainer, {'lr': 0.1}, data_iter)

trainer = tf.keras.optimizers.Adagrad
d2l.train_concise_ch11(trainer, {'learning_rate' : 0.1}, data_iter)

trainer = paddle.optimizer.Adagrad
d2l.train_concise_ch11(trainer, {'learning_rate': 0.1}, data_iter)

Резюме

• Алгоритм AdaGrad динамически уменьшает скорость обучения на уровне отдельных координат.
• AdaGrad использует величину градиента как инструмент для регулировки темпа: координаты с большими градиентами компенсируются меньшей скоростью обучения.
• В задачах глубокого обучения из-за ограничений памяти и вычислений точное вычисление вторых производных обычно невозможно. Градиент может служить эффективной заменой.
• Если структура задачи оптимизации существенно неоднородна, AdaGrad может помочь смягчить искажения.
• AdaGrad особенно эффективен для разреженных признаков, когда скорость обучения для редко встречающихся признаков должна уменьшаться медленнее.
• В задачах глубокого обучения AdaGrad иногда слишком сильно снижает скорость обучения. Стратегии борьбы с этим мы обсудим в разделе 11.10.

Упражнения

1. Докажите, что для ортогональной матрицы $\mathbf{U}$ и вектора $\mathbf{c}$ выполняется равенство $\Vert \mathbf{c}-\delta {\Vert }_2=\Vert \mathbf{Uc}-\mathbf{U}\delta {\Vert }_2$. Почему это означает, что после ортогонального преобразования переменных величина возмущения не меняется?
2. Попробуйте применить AdaGrad к функции $f(\mathbf{x})=0.1x_1^2+2x_2^2$ и к той же функции, повёрнутой на 45 градусов, то есть $f(\mathbf{x})=0.1(x_1+x_2{)}^2+2(x_1-x_2{)}^2$. Будет ли поведение различаться?
3. Докажите теорему о кругах Гершгорина, которая утверждает, что собственное значение ${\lambda }_i$ матрицы $\mathbf{M}$ удовлетворяет условию $|{\lambda }_i-{\mathbf{M}}_{jj}|\le {\sum }_{k\ne j}|{\mathbf{M}}_{jk}|$ хотя бы для одного $j$.
4. Что теорема Гершгорина говорит о собственных значениях диагонально предобусловленной матрицы ${\mathrm{diag}}^{-\frac{1}{2}}(\mathbf{M})\mathbf{M}{\mathrm{diag}}^{-\frac{1}{2}}(\mathbf{M})$?
5. Попробуйте применить AdaGrad к подходящей глубокой сети, например, к сети из раздела 6.6, которую мы использовали для Fashion-MNIST.
6. Как нужно изменить алгоритм AdaGrad, чтобы снижение скорости обучения было менее агрессивным?

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

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

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

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

Литература

• Duchi, J., Hazan, E., & Singer, Y. (2011). Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12, 2121–2159.