7/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 - (1- \beta)\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
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.
https://medium.com/analytics-vidhya/gradient-descent-vs-stochastic-gd-vs-mini-batch-sgd-fbd3a2cb4ba4
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 - (1- \beta)\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 - (1- \beta) \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 só 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).
O RMSprop tambem limita o crescimento de G_{i,j} fazendo um desconto do valor velho de G_{i-1,j} (multiplicando por um numero < 1 antes de somar com o quadrado do gradiente atual \nabla_j^2 f(w_i).
Adam usa a ideia de momento em cada direção, que tambem é adaptado com a soma dos quadrados do gradiente.
Adamax, Nadam, AMSGrad são outros algoritmos.
Veja outros algoritmos em https://ruder.io/optimizing-gradient-descent/index.html#nesterovacceleratedgradient