6/4/20
Fazem sentido em otimização não convexa
há mínimos locais pequenos
ha regiões com derivadas zero (em todas ou várias direções) que não são pontos de mínimo.
É preciso escapar desses dois tipos de regiões - nesses casos o gradiente = 0 e portanto a descida do gradiente para (\(w_{i+1} = w_i\)) e não há avanço (ou ele é pequeno).
Esta é uma boa fonte para esses assuntos
As tres familias de variações são
momento
stochastic gradient descent e minibatch
algoritmos adaptativos para o learning rate (e o momento)
metáfora: uma bola descendo o morro - ela mantem o momento (direção e velocidade) como um componente importante do novo passo.
momento: \(V_i = w_{i} - w_{i-1}\)
\[w_{i+1} = w_i - \epsilon \nabla f(w_{i}) + \beta V_i\]
onde \(\beta\) é o quanto o momento velho \(V_i\) influencia na nova direção e normalmente esse número é grande (0.9 ou mesmo 0.99)
Escapa de mínimos locais pequenos (onde o \(V\) se mantem ainda grande)
Quando estamos falando de aprendizado de maquina normalmente estamos falando em minimizar algum erro sobre varios dados.
Queremos minimizar algo como:
\[min f(w) = \sum_k erro(y_k - g(w, x_k))\]
onde \(k\) anda pelos dados e \(erro\) é alguma medida de erro (quadrático, modulo, e outros) e \(g\) é a função de estamos tentando aprender (com parâmetros \(w\))
A descida do gradiente normal seria:
\[w_{i+1} = w_{i} - \epsilon \nabla (\sum_k erro(y_k - g(w_i, x_k)))\]
Isso é igual a:
\[w_{i+1} = w_{i} - \sum_k \epsilon \nabla erro(y_k - g(w_i, x_k))\]
ou seja, acumula-se o gradiente do erro para cada dado e só depois atualiza o \(w_{i+1}\).
Isso é o a descida do gradiente tradicional e é chamado de batch GD
A ideia do stochasic gradient descent é atualizar o \(w\) com o gradiente do erro de um só dado.
\[ w_{i+1} = w_{i} - \epsilon \nabla erro(y_k - g(w_i, x_k))\]
para algum \(k\).
Note que a direção de \(\nabla erro(y_k - g(w_i, x_k))\) pode ser totalmente contraria a direção “correta” de \(\nabla (\sum_k erro(y_k - g(w_i, x_k)))\). Mas os outros dados vão acabar puxando o \(w\) na “direção certa”.
O SGD faz um caminho muito mais ruidoso para o mínimo (ver figura aqui )
O SGD é útil para escapar de regiões com derivada perto de zero (em todas ou algumas direções). Se \(\nabla (\sum_k erro_k)\) é zero, \(\nabla erro_k\) não deve ser zero.
O SGD é útil tambem conceitualmente para coisas como online learning onde voce não pode guardar os dados (por exemplo dados de sensores) e voce precisa utilizar o dado no aprendizado assim que ele aparece.
Na prática, para SGC é preciso alterar a ordem em que os dados \(k\) são apresentados ao algoritmo.
O SGD é muito ruidoso - o caminho para o minimo é muito ruidoso. A ideia do minibatch é combinar o batch com o SGC e fazer a atualizacao do \(w\) assim que um grupo de \(M\) dados for apresentado:
\[ w_{i+1} = w_{i} - \epsilon \nabla \sum_k^M erro(y_k - g(w_i, x_k))\]
Esse é um minibatch de \(M\) dados. Ele deve ter uma vantagem similar ao SGD em termos de fugir de regioes onde o gradiente é 0, mas faz um percurso menos ruidoso.
Este não é um algoritmo de l.r. adaptativo. Mas é parte dos outros algoritmos.
A formula do momento é onde \(\beta\) é 0.9 ou maior
\[w_{i+1} = w_i - \epsilon \nabla f(w_{i}) + \beta V_i\]
A ideia do NAG é que \(w_{i+1}\) vai ser perto de \(w_i + \beta V_i\) que são vetores que computamos na volta passada. Vamos chamar este ponto de \(\hat{w}_{i}\)
\[\hat{w}_{i} = w_i + \beta V_i\]
Em vez de calcular o gradiente em \(w_i\) vamos calcula-lo em \(\hat{w}_i\). Assim a formula de atualização do \(w_{i+1}\) no NAG é
\[w_{i+1} = w_i - \epsilon \nabla f(\hat{w}_{i}) + \beta V_i\]
Adagrad, como uma boa introdução a algoritmos adaptativos, tem um l.r para cada dimensão do vetor \(w\). Em redes neurais profundas, o gradiente tem valores muito baixos para as primeiras camadas (mexer nos pesos das primeiras camadas tem muito pouca influencia no resultado final) e muito maiores para as últimas.
\[w_{i+1,j} = w_{i,j} - \epsilon_j \nabla_j f (w_{i})\]
onde o indice \(j\) indica a dimensão
no adagrad:
\[\epsilon_j = \frac{\epsilon}{\sqrt{G_{i,j}+ \delta}}\]
onde \(\delta\) é um numero pequeno so para que a divisão não seja por 0 (se \(G_{i,j}\) é 0). \(G_{i,j}\) é a soma dos quadrados do gradiente na direção \(j\) até agora.
Se os gradientes na direção \(j\) são grandes, o passo naquela direção é pequeno (para evitar divergencias). E se são pequenos, o passo é grande.
Mas o AdaGrad sempre vai diminuindo o passo (ja que \(G_{i,j}\) sempre cresce).
Adadelta modifica o Adagrad para que o l.r. de cada direção não diminua continuamente. O termo \(G_{i,j}\) só soma \(k\) dos últimos gradientes (na direção \(j\)).
Adam usa a ideia de momento em cada direção, que tambem é adaptado com a soma dos quadrados do gradiente.
RMSprop, Adamax, Nadam, AMSGrad são outros algoritmos.
Veja outros algoritmos em https://ruder.io/optimizing-gradient-descent/index.html#nesterovacceleratedgradient