Três famílias de variações

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

• no caso de redes neurais há dimensões com a derivadas muito baixa e outras com derivadas mais alta. Por exemplo mudar o peso de uma conexão perto da entrada de dados tem muito pouco efeito na saída (derivada muito pequena) mas mexer nos pesos na última camada tem um efeito maior (derivada alta).

Três famílias de variações

As tres familias de variações são

• momento

• stochastic gradient descent e minibatch

• algoritmos adaptativos para o learning rate (e o momento)

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)

SGD - batch

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

SGD

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.

Minibatch

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.

Algoritmos adaptativos para o l.r

Nesterov accelerated gradient

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

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 e outros

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