.. _sec_adagrad:
Adagrad
=======
Vamos começar considerando os problemas de aprendizado com recursos que
ocorrem com pouca frequência.
Recursos esparsos e taxas de aprendizado
----------------------------------------
Imagine que estamos treinando um modelo de linguagem. Para obter uma boa
precisão, normalmente queremos diminuir a taxa de aprendizado à medida
que continuamos treinando, normalmente a uma taxa de
:math:`\mathcal{O}(t^{-\frac{1}{2}})` ou mais lenta. Agora, considere um
treinamento de modelo em recursos esparsos, ou seja, recursos que
ocorrem raramente. Isso é comum para a linguagem natural, por exemplo, é
muito menos provável que vejamos a palavra *précondicionamento* do que
*aprendizagem*. No entanto, também é comum em outras áreas, como
publicidade computacional e filtragem colaborativa personalizada.
Afinal, existem muitas coisas que interessam apenas a um pequeno número
de pessoas.
Os parâmetros associados a recursos pouco frequentes recebem apenas
atualizações significativas sempre que esses recursos ocorrem. Dada uma
taxa de aprendizado decrescente, podemos acabar em uma situação em que
os parâmetros para características comuns convergem rapidamente para
seus valores ideais, enquanto para características raras ainda não
podemos observá-los com frequência suficiente antes que seus valores
ideais possam ser determinados. Em outras palavras, a taxa de
aprendizado diminui muito lentamente para recursos freqüentes ou muito
rapidamente para recursos pouco frequentes.
Um possível hack para corrigir esse problema seria contar o número de
vezes que vemos um determinado recurso e usar isso como um relógio para
ajustar as taxas de aprendizagem. Ou seja, em vez de escolher uma taxa
de aprendizagem da forma :math:`\eta = \frac{\eta_0}{\sqrt{t + c}}`
poderiamos usar :math:`\eta_i = \frac{\eta_0}{\sqrt{s(i, t) + c}}` conta
o número de valores diferentes de zero para o recurso :math:`i` que
observamos até o momento :math:`t`. Na verdade, isso é muito fácil de
implementar sem sobrecarga significativa. No entanto, ele falha sempre
que não temos esparsidade, mas apenas dados em que os gradientes são
frequentemente muito pequenos e raramente grandes. Afinal, não está
claro onde se traçaria a linha entre algo que se qualifica como uma
característica observada ou não.
Adagrad by :cite:`Duchi.Hazan.Singer.2011` aborda isso substituindo o
contador bastante bruto :math:`s(i, t)` por um agregado de quadrados de
gradientes previamente observados. Em particular, ele usa
:math:`s(i, t+1) = s(i, t) + \left(\partial_i f(\mathbf{x})\right)^2`
como um meio de ajustar a taxa de aprendizagem. Isso tem dois
benefícios: primeiro, não precisamos mais decidir apenas quando um
gradiente é grande o suficiente. Em segundo lugar, ele é dimensionado
automaticamente com a magnitude dos gradientes. As coordenadas que
normalmente correspondem a grandes gradientes são reduzidas
significativamente, enquanto outras com pequenos gradientes recebem um
tratamento muito mais suave. Na prática, isso leva a um procedimento de
otimização muito eficaz para publicidade computacional e problemas
relacionados. Mas isso oculta alguns dos benefícios adicionais inerentes
ao Adagrad que são mais bem compreendidos no contexto do
pré-condicionamento.
Precondicionamento
------------------
Problemas de otimização convexa são bons para analisar as
características dos algoritmos. Afinal, para a maioria dos problemas
não-convexos, é difícil derivar garantias teóricas significativas, mas a
*intuição* e o *insight* geralmente são transmitidos. Vejamos o problema
de minimizar
:math:`f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^\top \mathbf{Q} \mathbf{x} + \mathbf{c}^\top \mathbf{x} + b`.
Como vimos em :numref:`sec_momentum`, é possível reescrever este
problema em termos de sua composição automática
:math:`\mathbf{Q} = \mathbf{U}^\top \boldsymbol{\Lambda} \mathbf{U}`
para chegar a um problema muito simplificado onde cada coordenada pode
ser resolvida individualmente:
.. math:: f(\mathbf{x}) = \bar{f}(\bar{\mathbf{x}}) = \frac{1}{2} \bar{\mathbf{x}}^\top \boldsymbol{\Lambda} \bar{\mathbf{x}} + \bar{\mathbf{c}}^\top \bar{\mathbf{x}} + b.
Aqui usamos :math:`\mathbf{x} = \mathbf{U} \mathbf{x}` e
consequentemente :math:`\mathbf{c} = \mathbf{U} \mathbf{c}`. O problema
modificado tem como minimizador
:math:`\bar{\mathbf{x}} = -\boldsymbol{\Lambda}^{-1} \bar{\mathbf{c}}` e
valor mínimo
:math:`-\frac{1}{2} \bar{\mathbf{c}}^\top \boldsymbol{\Lambda}^{-1} \bar{\mathbf{c}} + b`.
Isso é muito mais fácil de calcular, pois :math:`\boldsymbol{\Lambda}` é
uma matriz diagonal contendo os autovalores de :math:`\mathbf{Q}`.
Se perturbarmos :math:`\mathbf{c}` ligeiramente, esperaríamos encontrar
apenas pequenas mudanças no minimizador de $ f $. Infelizmente, esse não
é o caso. Embora pequenas mudanças em :math:`\mathbf{c}` levem a
mudanças igualmente pequenas em :math:`\bar{\mathbf{c}}`, este não é o
caso para o minimizador de :math:`f` (e de :math:`\bar{f}`
respectivamente). Sempre que os autovalores
:math:`\boldsymbol{\Lambda}_i` forem grandes, veremos apenas pequenas
mudanças em :math:`\bar{x}_i` e no mínimo de :math:`\bar{f}`. Por outro
lado, para pequenas :math:`\boldsymbol{\Lambda}_i`, as mudanças em
:math:`\bar{x}_i` podem ser dramáticas. A razão entre o maior e o menor
autovalor é chamada de número de condição de um problema de otimização.
.. math:: \kappa = \frac{\boldsymbol{\Lambda}_1}{\boldsymbol{\Lambda}_d}.
Se o número de condição :math:`\kappa` for grande, será difícil resolver
o problema de otimização com precisão. Precisamos garantir que somos
cuidadosos ao acertar uma ampla faixa dinâmica de valores. Nossa análise
leva a uma questão óbvia, embora um tanto ingênua: não poderíamos
simplesmente “consertar” o problema distorcendo o espaço de forma que
todos os autovalores sejam :math:`1`. Em teoria, isso é muito fácil:
precisamos apenas dos autovalores e autovetores de :math:`\mathbf{Q}`
para redimensionar o problema de :math:`\mathbf{x}` para um em
:math:`\mathbf{z} := \boldsymbol{\Lambda}^{\frac{1}{2}} \mathbf{U} \mathbf{x}`.
No novo sistema de coordenadas
:math:`\mathbf{x}^\top \mathbf{Q} \mathbf{x}` poderia ser simplificado
para :math:`\|\mathbf{z}\|^2`. Infelizmente, esta é uma sugestão pouco
prática. O cálculo de autovalores e autovetores é em geral muito mais
caro do que resolver o problema real.
Embora o cálculo exato dos autovalores possa ser caro, adivinhá-los e
computá-los de forma aproximada já pode ser muito melhor do que não
fazer nada. Em particular, poderíamos usar as entradas diagonais de
:math:`\mathbf{Q}` e redimensioná-las de acordo. Isso é *muito* mais
barato do que calcular valores próprios.
.. math:: \tilde{\mathbf{Q}} = \mathrm{diag}^{-\frac{1}{2}}(\mathbf{Q}) \mathbf{Q} \mathrm{diag}^{-\frac{1}{2}}(\mathbf{Q}).
Neste caso, temos
:math:`\tilde{\mathbf{Q}}_{ij} = \mathbf{Q}_{ij} / \sqrt{\mathbf{Q}_{ii} \mathbf{Q}_{jj}}`
e especificamente :math:`\tilde{\mathbf{Q}}_{ii} = 1` para todo
:math:`i`. Na maioria dos casos, isso simplifica consideravelmente o
número da condição. Por exemplo, nos casos que discutimos anteriormente,
isso eliminaria totalmente o problema em questão, uma vez que o problema
está alinhado ao eixo.
Infelizmente, enfrentamos ainda outro problema: no aprendizado profundo,
normalmente nem mesmo temos acesso à segunda derivada da função
objetivo: para :math:`\mathbf{x} \in \mathbb{R}^d` a segunda derivada,
mesmo em um minibatch pode exigir :math:`\mathcal{O}(d^2)` espaço e
trabalho para computar, tornando-o praticamente inviável. A ideia
engenhosa do Adagrad é usar um proxy para aquela diagonal indescritível
do Hessian que é relativamente barato para calcular e eficaz— a
magnitude do gradiente em si.
Para ver por que isso funciona, vamos dar uma olhada em
:math:`\bar{f}(\bar{\mathbf{x}})`. Nós temos isso
.. math:: \partial_{\bar{\mathbf{x}}} \bar{f}(\bar{\mathbf{x}}) = \boldsymbol{\Lambda} \bar{\mathbf{x}} + \bar{\mathbf{c}} = \boldsymbol{\Lambda} \left(\bar{\mathbf{x}} - \bar{\mathbf{x}}_0\right),
onde :math:`\bar{\mathbf{x}}_0` é o minimizador de :math:`\bar{f}`.
Portanto, a magnitude do gradiente depende tanto de
:math:`\boldsymbol{\Lambda}` quanto da distância da otimalidade. Se
:math:`\bar{\mathbf{x}} - \bar{\mathbf{x}}_0` não mudou, isso seria tudo
o que é necessário. Afinal, neste caso, a magnitude do gradiente
:math:`\partial_{\bar{\mathbf{x}}} \bar{f}(\bar{\mathbf{x}})` é
suficiente. Como o AdaGrad é um algoritmo descendente de gradiente
estocástico, veremos gradientes com variância diferente de zero mesmo em
otimização. Como resultado, podemos usar com segurança a variância dos
gradientes como um proxy barato para a escala de Hessian. Uma análise
completa está além do escopo desta seção (seriam várias páginas).
Recomendamos ao leitor :cite:`Duchi.Hazan.Singer.2011` para detalhes.
O Algoritmo
-----------
Vamos formalizar a discussão de cima. Usamos a variável
:math:`\mathbf{s}_t` para acumular a variância do gradiente anterior
como segue.
.. math::
\begin{aligned}
\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 + \epsilon}} \cdot \mathbf{g}_t.
\end{aligned}
Aqui, as operações são aplicadas de acordo com as coordenadas. Ou seja,
:math:`\mathbf{v}^2` tem entradas :math:`v_i^2`. Da mesma forma,
:math:`\frac{1}{\sqrt{v}}` tem entradas :math:`\frac{1}{\sqrt{v_i}}` e
:math:`\mathbf{u} \cdot \mathbf{v}` tem entradas :math:`u_i v_i`. Como
antes, :math:`\eta` é a taxa de aprendizagem e :math:`\epsilon` é uma
constante aditiva que garante que não dividamos por :math:`0`. Por
último, inicializamos :math:`\mathbf{s}_0 = \mathbf{0}`.
Assim como no caso do momentum, precisamos manter o controle de uma
variável auxiliar, neste caso para permitir uma taxa de aprendizagem
individual por coordenada. Isso não aumenta o custo do Adagrad
significativamente em relação ao SGD, simplesmente porque o custo
principal normalmente é calcular
:math:`l(y_t, f(\mathbf{x}_t, \mathbf{w}))` e sua derivada.
Observe que o acúmulo de gradientes quadrados em :math:`\mathbf{s}_t`
significa que :math:`\mathbf{s}_t` cresce essencialmente a uma taxa
linear (um pouco mais lento do que linearmente na prática, uma vez que
os gradientes inicialmente diminuem). Isso leva a uma taxa de
aprendizado :math:`\mathcal{O}(t^{-\frac{1}{2}})`, embora ajustada por
coordenada. Para problemas convexos, isso é perfeitamente adequado. No
aprendizado profundo, porém, podemos querer diminuir a taxa de
aprendizado um pouco mais lentamente. Isso levou a uma série de
variantes do Adagrad que discutiremos nos capítulos subsequentes. Por
enquanto, vamos ver como ele se comporta em um problema convexo
quadrático. Usamos o mesmo problema de antes:
.. math:: f(\mathbf{x}) = 0.1 x_1^2 + 2 x_2^2.
Vamos implementar o Adagrad usando a mesma taxa de aprendizado anterior,
ou seja, :math:`\eta = 0.4`. Como podemos ver, a trajetória iterativa da
variável independente é mais suave. No entanto, devido ao efeito
cumulativo de :math:`\boldsymbol{s}_t`, a taxa de aprendizado diminui
continuamente, de modo que a variável independente não se move tanto
durante os estágios posteriores da iteração.
.. raw:: html
.. raw:: html
.. code:: python
%matplotlib inline
import math
from mxnet import np, npx
from d2l import mxnet as d2l
npx.set_np()
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))
.. figure:: output_adagrad_2fb0ed_3_0.svg
.. raw:: html
.. raw:: html
.. code:: python
%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))
.. figure:: output_adagrad_2fb0ed_6_0.svg
.. raw:: html
.. raw:: html
.. code:: python
%matplotlib inline
import math
import tensorflow as tf
from d2l import tensorflow 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))
.. figure:: output_adagrad_2fb0ed_9_0.svg
.. raw:: html
.. raw:: html
.. raw:: html
.. code:: python
eta = 2
d2l.show_trace_2d(f_2d, d2l.train_2d(adagrad_2d))
.. figure:: output_adagrad_2fb0ed_15_0.svg
.. raw:: html
.. raw:: html
.. code:: python
eta = 2
d2l.show_trace_2d(f_2d, d2l.train_2d(adagrad_2d))
.. figure:: output_adagrad_2fb0ed_18_0.svg
.. raw:: html
.. raw:: html
.. code:: python
eta = 2
d2l.show_trace_2d(f_2d, d2l.train_2d(adagrad_2d))
.. figure:: output_adagrad_2fb0ed_21_0.svg
.. raw:: html
.. raw:: html
.. raw:: html
.. code:: python
def init_adagrad_states(feature_dim):
s_w = np.zeros((feature_dim, 1))
s_b = np.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)
.. raw:: html
.. raw:: html
.. code:: python
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_()
.. raw:: html
.. raw:: html
.. code:: python
def init_adagrad_states(feature_dim):
s_w = tf.Variable(tf.zeros((feature_dim, 1)))
s_b = tf.Variable(tf.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))
.. raw:: html
.. raw:: html
.. raw:: html
.. code:: python
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);
.. parsed-literal::
:class: output
loss: 0.242, 0.165 sec/epoch
.. figure:: output_adagrad_2fb0ed_39_1.svg
.. raw:: html
.. raw:: html
.. code:: python
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);
.. parsed-literal::
:class: output
loss: 0.244, 0.012 sec/epoch
.. figure:: output_adagrad_2fb0ed_42_1.svg
.. raw:: html
.. raw:: html
.. code:: python
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);
.. parsed-literal::
:class: output
loss: 0.242, 0.081 sec/epoch
.. figure:: output_adagrad_2fb0ed_45_1.svg
.. raw:: html
.. raw:: html
.. raw:: html
.. code:: python
d2l.train_concise_ch11('adagrad', {'learning_rate': 0.1}, data_iter)
.. parsed-literal::
:class: output
loss: 0.243, 0.429 sec/epoch
.. figure:: output_adagrad_2fb0ed_51_1.svg
.. raw:: html
.. raw:: html
.. code:: python
trainer = torch.optim.Adagrad
d2l.train_concise_ch11(trainer, {'lr': 0.1}, data_iter)
.. parsed-literal::
:class: output
loss: 0.243, 0.013 sec/epoch
.. figure:: output_adagrad_2fb0ed_54_1.svg
.. raw:: html
.. raw:: html
.. code:: python
trainer = tf.keras.optimizers.Adagrad
d2l.train_concise_ch11(trainer, {'learning_rate' : 0.1}, data_iter)
.. parsed-literal::
:class: output
loss: 0.244, 0.079 sec/epoch
.. figure:: output_adagrad_2fb0ed_57_1.svg
.. raw:: html
.. raw:: html
.. raw:: html
`Discussão `__
.. raw:: html
.. raw:: html
`Discussão `__
.. raw:: html
.. raw:: html
`Discussão `__
.. raw:: html
.. raw:: html