.. _sec_sgd: Gradiente Descendente Estocástico ================================= Nesta seção, apresentaremos os princípios básicos da gradiente descendente estocástico. .. raw:: html

.. raw:: html

.. code:: python %matplotlib inline import math from mxnet import np, npx from d2l import mxnet as d2l npx.set_np() .. raw:: html

.. raw:: html

.. code:: python %matplotlib inline import math import torch from d2l import torch as d2l .. raw:: html

.. raw:: html

.. code:: python %matplotlib inline import math import tensorflow as tf from d2l import tensorflow as d2l .. raw:: html

.. raw:: html

Atualizações de gradiente estocástico ------------------------------------- No aprendizado profundo, a função objetivo é geralmente a média das funções de perda para cada exemplo no conjunto de dados de treinamento. Assumimos que :math:`f_i(\mathbf{x})` é a função de perda do conjunto de dados de treinamento com :math:`n` exemplos, um índice de :math:`i` e um vetor de parâmetro de :math:`\mathbf{x}`, então temos o função objetiva .. math:: f(\mathbf{x}) = \frac{1}{n} \sum_{i = 1}^n f_i(\mathbf{x}). O gradiente da função objetivo em :math:`\mathbf{x}` é calculado como .. math:: \nabla f(\mathbf{x}) = \frac{1}{n} \sum_{i = 1}^n \nabla f_i(\mathbf{x}). Se o gradiente descendente for usado, o custo de computação para cada iteração de variável independente é :math:`\mathcal{O}(n)`, que cresce linearmente com :math:`n`. Portanto, quando o conjunto de dados de treinamento do modelo é grande, o custo da descida do gradiente para cada iteração será muito alto. A descida gradiente estocástica (SGD) reduz o custo computacional a cada iteração. A cada iteração de descida do gradiente estocástico, amostramos uniformemente um índice :math:`i\in\{1,\ldots, n\}` para exemplos de dados aleatoriamente e calculamos o gradiente :math:`\nabla f_i(\mathbf{x})` para atualizar :math:`\mathbf{x}`: .. math:: \mathbf{x} \leftarrow \mathbf{x} - \eta \nabla f_i(\mathbf{x}). Aqui, :math:`\eta` é a taxa de aprendizado. Podemos ver que o custo de computação para cada iteração cai de :math:`\mathcal{O}(n)` da descida do gradiente para a constante :math:`\mathcal{O}(1)`. Devemos mencionar que o gradiente estocástico :math:`\nabla f_i(\mathbf{x})` é a estimativa imparcial do gradiente :math:`\nabla f(\mathbf{x})`. .. math:: \mathbb{E}_i \nabla f_i(\mathbf{x}) = \frac{1}{n} \sum_{i = 1}^n \nabla f_i(\mathbf{x}) = \nabla f(\mathbf{x}). Isso significa que, em média, o gradiente estocástico é uma boa estimativa do gradiente. Agora, vamos compará-lo com a descida do gradiente adicionando ruído aleatório com uma média de 0 e uma variância de 1 ao gradiente para simular um SGD. .. raw:: html

mxnet pytorch tensorflow

.. raw:: html

.. code:: python f = lambda x1, x2: x1 ** 2 + 2 * x2 ** 2 # Objective gradf = lambda x1, x2: (2 * x1, 4 * x2) # Gradient def sgd(x1, x2, s1, s2): global lr # Learning rate scheduler (g1, g2) = gradf(x1, x2) # Simulate noisy gradient g1 += np.random.normal(0.0, 1, (1,)) g2 += np.random.normal(0.0, 1, (1,)) eta_t = eta * lr() # Learning rate at time t return (x1 - eta_t * g1, x2 - eta_t * g2, 0, 0) # Update variables eta = 0.1 lr = (lambda: 1) # Constant learning rate d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=50)) .. figure:: output_sgd_baca77_15_0.svg .. raw:: html

.. raw:: html

.. code:: python f = lambda x1, x2: x1 ** 2 + 2 * x2 ** 2 # Objective gradf = lambda x1, x2: (2 * x1, 4 * x2) # Gradient def sgd(x1, x2, s1, s2): global lr # Learning rate scheduler (g1, g2) = gradf(x1, x2) # Simulate noisy gradient g1 += torch.normal(0.0, 1, (1,)) g2 += torch.normal(0.0, 1, (1,)) eta_t = eta * lr() # Learning rate at time t return (x1 - eta_t * g1, x2 - eta_t * g2, 0, 0) # Update variables eta = 0.1 lr = (lambda: 1) # Constant learning rate d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=50)) .. figure:: output_sgd_baca77_18_0.svg .. raw:: html

.. raw:: html

.. code:: python f = lambda x1, x2: x1 ** 2 + 2 * x2 ** 2 # Objective gradf = lambda x1, x2: (2 * x1, 4 * x2) # Gradient def sgd(x1, x2, s1, s2): global lr # Learning rate scheduler (g1, g2) = gradf(x1, x2) # Simulate noisy gradient g1 += tf.random.normal([1], 0.0, 1) g2 += tf.random.normal([1], 0.0, 1) eta_t = eta * lr() # Learning rate at time t return (x1 - eta_t * g1, x2 - eta_t * g2, 0, 0) # Update variables eta = 0.1 lr = (lambda: 1) # Constant learning rate d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=50)) .. figure:: output_sgd_baca77_21_0.svg .. raw:: html

.. raw:: html

Como podemos ver, a trajetória das variáveis no SGD é muito mais ruidosa do que a que observamos na descida do gradiente na seção anterior. Isso se deve à natureza estocástica do gradiente. Ou seja, mesmo quando chegamos perto do mínimo, ainda estamos sujeitos à incerteza injetada pelo gradiente instantâneo via :math:`\eta \nabla f_i(\mathbf{x})`. Mesmo após 50 passos, a qualidade ainda não é tão boa. Pior ainda, não melhorará após etapas adicionais (encorajamos o leitor a experimentar um número maior de etapas para confirmar isso por conta própria). Isso nos deixa com a única alternativa — alterar a taxa de aprendizagem :math:`\eta`. No entanto, se escolhermos isso muito pequeno, não faremos nenhum progresso significativo inicialmente. Por outro lado, se o escolhermos muito grande, não obteremos uma boa solução, como visto acima. A única maneira de resolver esses objetivos conflitantes é reduzir a taxa de aprendizado *dinamicamente* à medida que a otimização avança. Esta também é a razão para adicionar uma função de taxa de aprendizagem ``lr`` na função de passo\ ``sgd``. No exemplo acima, qualquer funcionalidade para o agendamento da taxa de aprendizagem permanece latente, pois definimos a função ``lr`` associada como constante, ou seja,\ ``lr = (lambda: 1)``. Taxa de aprendizagem dinâmica ----------------------------- Substituir :math:`\eta` por uma taxa de aprendizado dependente do tempo :math:`\eta(t)` aumenta a complexidade de controlar a convergência de um algoritmo de otimização. Em particular, é preciso descobrir com que rapidez :math:`\eta` deve decair. Se for muito rápido, pararemos de otimizar prematuramente. Se diminuirmos muito lentamente, perderemos muito tempo com a otimização. Existem algumas estratégias básicas que são usadas no ajuste de :math:`\eta` ao longo do tempo (discutiremos estratégias mais avançadas em um capítulo posterior): .. math:: \begin{aligned} \eta(t) & = \eta_i \text{ if } t_i \leq t \leq t_{i+1} && \mathrm{piecewise~constant} \\ \eta(t) & = \eta_0 \cdot e^{-\lambda t} && \mathrm{exponential} \\ \eta(t) & = \eta_0 \cdot (\beta t + 1)^{-\alpha} && \mathrm{polynomial} \end{aligned} No primeiro cenário, diminuímos a taxa de aprendizado, por exemplo, sempre que o progresso na otimização para. Esta é uma estratégia comum para treinar redes profundas. Alternativamente, poderíamos diminuí-lo de forma muito mais agressiva por uma redução exponencial. Infelizmente, isso leva a uma parada prematura antes que o algoritmo tenha convergido. Uma escolha popular é o decaimento polinomial com :math:`\alpha = 0.5`. No caso da otimização convexa, há uma série de provas que mostram que essa taxa é bem comportada. Vamos ver como isso se parece na prática. .. raw:: html

mxnet pytorch tensorflow

.. raw:: html

.. code:: python def exponential(): global ctr ctr += 1 return math.exp(-0.1 * ctr) ctr = 1 lr = exponential # Set up learning rate d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=1000)) .. figure:: output_sgd_baca77_27_0.svg .. raw:: html

.. raw:: html

Como esperado, a variância nos parâmetros é reduzida significativamente. No entanto, isso ocorre às custas de não convergir para a solução ótima :math:`\mathbf{x} = (0, 0)`. Mesmo depois de 1000 passos, ainda estamos muito longe da solução ideal. Na verdade, o algoritmo não consegue convergir. Por outro lado, se usarmos um decaimento polinomial onde a taxa de aprendizagem decai com a raiz quadrada inversa do número de passos, a convergência é boa. .. raw:: html

mxnet pytorch tensorflow

.. raw:: html

.. code:: python def polynomial(): global ctr ctr += 1 return (1 + 0.1 * ctr)**(-0.5) ctr = 1 lr = polynomial # Set up learning rate d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=50)) .. figure:: output_sgd_baca77_39_0.svg .. raw:: html

.. raw:: html

Existem muitas outras opções de como definir a taxa de aprendizagem. Por exemplo, poderíamos começar com uma taxa pequena, aumentar rapidamente e diminuí-la novamente, embora mais lentamente. Poderíamos até alternar entre taxas de aprendizagem menores e maiores. Existe uma grande variedade de tais horários. Por enquanto, vamos nos concentrar em tabelas de taxas de aprendizagem para as quais uma análise teórica abrangente é possível, ou seja, em taxas de aprendizagem em um cenário convexo. Para problemas não-convexos gerais é muito difícil obter garantias de convergência significativas, uma vez que, em geral, minimizar problemas não-convexos não lineares é NP difícil. Para uma pesquisa, consulte, por exemplo, as excelentes `notas de aula `__ de Tibshirani 2015. Análise de convergência para objetivos convexos ----------------------------------------------- O que segue é opcional e serve principalmente para transmitir mais intuição sobre o problema. Nos limitamos a uma das provas mais simples, conforme descrito por :cite:`Nesterov.Vial.2000`. Existem técnicas de prova significativamente mais avançadas, por exemplo, sempre que a função objetiva é particularmente bem comportada. :cite:`Hazan.Rakhlin.Bartlett.2008` mostra que para funções fortemente convexas, ou seja, para funções que podem ser limitadas de baixo por :math:`\mathbf{x}^\top \mathbf{Q} \mathbf{x}` , é possível minimizá-los em um pequeno número de etapas enquanto diminui a taxa de aprendizagem como :math:`\eta(t) = \eta_0/(\beta t + 1)`. Infelizmente, esse caso nunca ocorre realmente no aprendizado profundo e ficamos com uma taxa de diminuição muito mais lenta na prática. Considere o caso onde .. math:: \mathbf{w}_{t+1} = \mathbf{w}_{t} - \eta_t \partial_\mathbf{w} l(\mathbf{x}_t, \mathbf{w}). Em particular, assuma que :math:`\mathbf{x}_t` é retirado de alguma distribuição :math:`P(\mathbf{x})` e que :math:`l(\mathbf{x}, \mathbf{w})` é uma função convexa em :math:`\mathbf{w}` para todos os :math:`\mathbf{x}`. Última denotada por .. math:: R(\mathbf{w}) = E_{\mathbf{x} \sim P}[l(\mathbf{x}, \mathbf{w})] o risco esperado e por :math:`R^*` seu mínimo em relação a :math:`\mathbf{w}`. Por último, seja :math:`\mathbf{w}^*` o minimizador (assumimos que ele existe dentro do domínio que :math:`\mathbf{w}` está definido). Neste caso, podemos rastrear a distância entre o parâmetro atual :math:`\mathbf{w}_t` e o minimizador de risco :math:`\mathbf{w}^*` e ver se melhora com o tempo: .. math:: \begin{aligned} \|\mathbf{w}_{t+1} - \mathbf{w}^*\|^2 & = \|\mathbf{w}_{t} - \eta_t \partial_\mathbf{w} l(\mathbf{x}_t, \mathbf{w}) - \mathbf{w}^*\|^2 \\ & = \|\mathbf{w}_{t} - \mathbf{w}^*\|^2 + \eta_t^2 \|\partial_\mathbf{w} l(\mathbf{x}_t, \mathbf{w})\|^2 - 2 \eta_t \left\langle \mathbf{w}_t - \mathbf{w}^*, \partial_\mathbf{w} l(\mathbf{x}_t, \mathbf{w})\right\rangle. \end{aligned} O gradiente :math:`\partial_\mathbf{w} l(\mathbf{x}_t, \mathbf{w})` pode ser limitado de cima por alguma constante de Lipschitz :math:`L`, portanto, temos que .. math:: \eta_t^2 \|\partial_\mathbf{w} l(\mathbf{x}_t, \mathbf{w})\|^2 \leq \eta_t^2 L^2. Estamos principalmente interessados em como a distância entre :math:`\mathbf{w}_t` e :math:`\mathbf{w}^*` muda *na expectativa*. Na verdade, para qualquer sequência específica de passos, a distância pode muito bem aumentar, dependendo de qualquer :math:`\mathbf{x}_t` que encontrarmos. Portanto, precisamos limitar o produto interno. Por convexidade temos que .. math:: l(\mathbf{x}_t, \mathbf{w}^*) \geq l(\mathbf{x}_t, \mathbf{w}_t) + \left\langle \mathbf{w}^* - \mathbf{w}_t, \partial_{\mathbf{w}} l(\mathbf{x}_t, \mathbf{w}_t) \right\rangle. Usando ambas as desigualdades e conectando-as ao acima, obtemos um limite para a distância entre os parâmetros no tempo :math:`t+1` da seguinte forma: .. math:: \|\mathbf{w}_{t} - \mathbf{w}^*\|^2 - \|\mathbf{w}_{t+1} - \mathbf{w}^*\|^2 \geq 2 \eta_t (l(\mathbf{x}_t, \mathbf{w}_t) - l(\mathbf{x}_t, \mathbf{w}^*)) - \eta_t^2 L^2. Isso significa que progredimos enquanto a diferença esperada entre a perda atual e a perda ótima supera :math:`\eta_t L^2`. Como o primeiro tende a convergir para :math:`0`, segue-se que a taxa de aprendizado :math:`\eta_t` também precisa desaparecer. Em seguida, consideramos as expectativas sobre essa expressão. Isso produz .. math:: E_{\mathbf{w}_t}\left[\|\mathbf{w}_{t} - \mathbf{w}^*\|^2\right] - E_{\mathbf{w}_{t+1}\mid \mathbf{w}_t}\left[\|\mathbf{w}_{t+1} - \mathbf{w}^*\|^2\right] \geq 2 \eta_t [E[R[\mathbf{w}_t]] - R^*] - \eta_t^2 L^2. A última etapa envolve a soma das desigualdades para :math:`t \in \{t, \ldots, T\}`. Uma vez que a soma dos telescópios e diminuindo o termo inferior, obtemos .. math:: \|\mathbf{w}_{0} - \mathbf{w}^*\|^2 \geq 2 \sum_{t=1}^T \eta_t [E[R[\mathbf{w}_t]] - R^*] - L^2 \sum_{t=1}^T \eta_t^2. Observe que exploramos que :math:`\mathbf{w}_0` é dado e, portanto, a expectativa pode ser descartada. Última definição .. math:: \bar{\mathbf{w}} := \frac{\sum_{t=1}^T \eta_t \mathbf{w}_t}{\sum_{t=1}^T \eta_t}. Então, por convexidade, segue-se que .. math:: \sum_t \eta_t E[R[\mathbf{w}_t]] \geq \sum \eta_t \cdot \left[E[\bar{\mathbf{w}}]\right]. Conectar isso à desigualdade acima produz o limite .. math:: \left[E[\bar{\mathbf{w}}]\right] - R^* \leq \frac{r^2 + L^2 \sum_{t=1}^T \eta_t^2}{2 \sum_{t=1}^T \eta_t}. Aqui :math:`r^2 := \|\mathbf{w}_0 - \mathbf{w}^*\|^2` é um limite na distância entre a escolha inicial dos parâmetros e o resultado final. Em suma, a velocidade de convergência depende de quão rapidamente a função de perda muda por meio da constante de Lipschitz :math:`L` e quão longe da otimização o valor inicial está :math:`r`. Observe que o limite é em termos de :math:`\bar{\mathbf{w}}` em vez de :math:`\mathbf{w}_T`. Este é o caso, pois :math:`\bar{\mathbf{w}}` é uma versão suavizada do caminho de otimização. Agora vamos analisar algumas opções para :math:`\eta_t`. - **Horizonte de tempo conhecido**. Sempre que :math:`r, L` e :math:`T` são conhecidos, podemos escolher $\ :math:`\eta = r/L \sqrt{T}`. Isso resulta no limite superior :math:`r L (1 + 1/T)/2\sqrt{T} < rL/\sqrt{T}`. Ou seja, convergimos com a taxa :math:`\mathcal{O}(1/\sqrt{T})` para a solução ótima. - **Horizonte de tempo desconhecido**. Sempre que quisermos ter uma boa solução para *a qualquer* momento :math:`T`, podemos escolher :math:`\eta = \mathcal{O}(1/\sqrt{T})`. Isso nos custa um fator logarítmico extra e leva a um limite superior da forma :math:`\mathcal{O}(\log T / \sqrt{T})`. Observe que para perdas fortemente convexas :math:`l(\mathbf{x}, \mathbf{w}') \geq l(\mathbf{x}, \mathbf{w}) + \langle \mathbf{w}'-\mathbf{w}, \partial_\mathbf{w} l(\mathbf{x}, \mathbf{w}) \rangle + \frac{\lambda}{2} \|\mathbf{w}-\mathbf{w}'\|^2` podemos projetar agendas de otimização convergentes ainda mais rapidamente. Na verdade, um declínio exponencial em :math:`\eta` leva a um limite da forma :math:`\mathcal{O}(\log T / T)`. Gradientes estocásticos e amostras finitas ------------------------------------------ Até agora, fomos um pouco rápidos e soltos quando se trata de falar sobre a descida gradiente estocástica. Postulamos que desenhamos instâncias :math:`x_i`, normalmente com rótulos :math:`y_i` de alguma distribuição :math:`p(x, y)` e que usamos isso para atualizar os pesos :math:`w` de alguma maneira. Em particular, para um tamanho de amostra finito, simplesmente argumentamos que a distribuição discreta :math:`p(x, y) = \frac{1}{n} \sum_{i=1}^n \delta_{x_i}(x) \delta_{y_i}(y)` nos permite realizar SGD sobre ele. No entanto, não foi exatamente isso que fizemos. Nos exemplos de brinquedos na seção atual, simplesmente adicionamos ruído a um gradiente não estocástico, ou seja, fingimos ter pares :math:`(x_i, y_i)`. Acontece que isso se justifica aqui (veja os exercícios para uma discussão detalhada). Mais preocupante é que em todas as discussões anteriores claramente não fizemos isso. Em vez disso, iteramos em todas as instâncias exatamente uma vez. Para ver por que isso é preferível, considere o inverso, ou seja, estamos amostrando :math:`n` observações da distribuição discreta com substituição. A probabilidade de escolher um elemento :math:`i` aleatoriamente é :math:`N^{-1}`. Portanto, escolher pelo menos uma vez é .. math:: P(\mathrm{choose~} i) = 1 - P(\mathrm{omit~} i) = 1 - (1-N^{-1})^N \approx 1-e^{-1} \approx 0.63. Um raciocínio semelhante mostra que a probabilidade de escolher uma amostra exatamente uma vez é dada por :math:`{N \choose 1} N^{-1} (1-N^{-1})^{N-1} = \frac{N-1}{N} (1-N^{-1})^{N} \approx e^{-1} \approx 0.37`. Isso leva a um aumento da variância e diminuição da eficiência dos dados em relação à amostragem sem reposição. Portanto, na prática, fazemos o último (e esta é a escolha padrão em todo este livro). Por último, observe que passagens repetidas pelo conjunto de dados percorrem-no em uma ordem aleatória *diferente*. Sumário ------- - Para problemas convexos, podemos provar que, para uma ampla escolha de taxas de aprendizado, a Descida de Gradiente Estocástico convergirá para a solução ótima. - Geralmente, esse não é o caso para aprendizagem profunda. No entanto, a análise de problemas convexos nos dá uma visão útil sobre como abordar a otimização, nomeadamente para reduzir a taxa de aprendizagem progressivamente, embora não muito rapidamente. - Os problemas ocorrem quando a taxa de aprendizagem é muito pequena ou muito grande. Na prática, uma taxa de aprendizado adequada geralmente é encontrada somente após vários experimentos. - Quando há mais exemplos no conjunto de dados de treinamento, custa mais calcular cada iteração para a descida do gradiente, portanto, SGD é preferível nesses casos. - As garantias de otimização para SGD em geral não estão disponíveis em casos não convexos, pois o número de mínimos locais que requerem verificação pode ser exponencial. Exercícios ---------- 1. Experimente diferentes programações de taxa de aprendizagem para SGD e com diferentes números de iterações. Em particular, plote a distância da solução ótima :math:`(0, 0)` como uma função do número de iterações. 2. Prove que para a função :math:`f(x_1, x_2) = x_1^2 + 2 x_2^2` adicionar ruído normal ao gradiente é equivalente a minimizar uma função de perda :math:`l(\mathbf{x}, \mathbf{w}) = (x_1 - w_1)^2 + 2 (x_2 - w_2)^2` onde :math:`x` é extraído de uma distribuição normal. - Derive a média e a variância da distribuição de :math:`\mathbf{x}`. - Mostre que esta propriedade é geralmente válida para funções objetivo :math:`f(\mathbf{x}) = \frac{1}{2} (\mathbf{x} - \mathbf{\mu})^\top Q (\mathbf{x} - \mathbf{\mu})` para :math:`Q \succeq 0`. 3. Compare a convergência de SGD quando você faz a amostra de :math:`\{(x_1, y_1), \ldots, (x_m, y_m)\}` com substituição e quando você faz a amostra sem substituição. 4. Como você mudaria o solucionador SGD se algum gradiente (ou melhor, alguma coordenada associada a ele) fosse consistentemente maior do que todos os outros gradientes? 5. Suponha que :math:`f(x) = x^2 (1 + \sin x)`. Quantos mínimos locais :math:`f` tem? Você pode alterar :math:`f` de forma que, para minimizá-lo, seja necessário avaliar todos os mínimos locais? .. raw:: html

mxnet pytorch tensorflow

.. raw:: html

`Discussão `__ .. raw:: html

.. raw:: html

`Discussão `__ .. raw:: html

.. raw:: html

`Discussão `__ .. raw:: html

.. raw:: html