27/3/20
O gradiente de uma função é um vetor no espaço do domínio da função. Se a função f é uma função do R^3 e se chamamos de x_1 x_2 e x_3 as três dimensões do R^3 então
\def\arraystretch{1.5} gradiente f = \nabla f = \left[ \begin{array}{r} \frac{\partial f}{\partial x_1} \\ \frac{\partial f}{\partial x_2} \\ \frac{\partial f}{\partial x_3} \\ \end{array} \right]
O hermetiano é a extensão da ideia de 2a derivada para funções que recebem um vetor e retornam um escalar
\def\arraystretch{1.5} H f = \left[ \begin{array}{rrr} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & \frac{\partial^2 f}{\partial x_1 \partial x_3} \\ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \frac{\partial^2 f}{\partial x_2 \partial x_3} \\ \frac{\partial^2 f}{\partial x_3\partial x_1} & \frac{\partial^2 f}{\partial x_3 \partial x_2} & \frac{\partial^2 f}{\partial x_3^2} \\ \end{array} \right]
O H é simétrico já que, por exemplo \frac{\partial^2 f}{\partial x_3 \partial x_2} = \frac{\partial^2 f}{\partial x_2 \partial x_3}
Se a função \vec{f(x)} retorna um vetor para cada vetor de entrada então a extensão do gradiente é chamada de Jacobiano e é uma matriz onde cada coluna é o gradiente de f para cada uma das dimensões de saída de \vec{f}
Se w tem 3 dimensões x_1, x_2, x_3 e \vec{f} tem 2 dimensões f_1 e f_2 o Jacobiano sera
\def\arraystretch{1.5} J f = \left[ \begin{array}{rr} \frac{\partial f_1}{\partial x_1} & \frac{\partial f_2}{\partial x_1} \\ \frac{\partial f_1}{\partial x_2} & \frac{\partial f_2}{\partial x_2} \\ \frac{\partial f_1}{\partial x_3} & \frac{\partial f_2}{\partial x_3} \\ \end{array} \right]
O gradiente \nabla f(w_0) no ponto w_0 é a direção para onde a função mais cresce no ponto w_0. veja esse video
a direção - \nabla f é a direção onde a função mais decresce.
A derivada da função f na direção \vec{u} (|\vec{u}|=1) é \nabla_u f é igual a (\nabla f)^T \vec{u}
curvas de nível (superficies de nivel) são direções onde a função f não mudam https://mathinsight.org/level_sets
se a função nao muda naquela direção ($u$0 então \nabla_u f = 0 ou (\nabla f)^T u = 0 ou seja u é perpendicular ao gradiente.
Se eu estou no ponto w_0 e -\nabla f(w_0) é a direção que mais faz f diminuir, então eu devo andar um pouquinho naquela direção para o ponto w_1,
w_{i+1} = w_i - \epsilon \nabla f(w_i)
\epsilon é o learning rate e é um número pequeno.
Se a função é convexa, o procedimento converge para o ponto de minima, mas demora um tempo infinito - perto do minimo, o gradiente fica cada vez menor e o passo fica cada vez menor.
De forma geral, inicie num ponto aleatório w_0 e aplique a descida do gradiente até que haja pouca mudança entre um valor w_i e o próximo valor w_{i+1}.
Há varios critérios de parada
numero maximo de iterações
pequena diferença absoluta no w |w_{i+1}-w_i| < \delta
pequena diferença absoluta no f |f(w_{i+1})-f(w_i)| < \delta
pequena diferença relativa no w \frac{|w_{i+1}-w_i|}{|w_i|} < \delta
pequena diferença relativa no f \frac{|f(w_{i+1})-f(w_i)|}{|f(w_i)|} < \delta
pequena diferença absoluta para vários passos |f(w_{i+1})-f(w_i)| < \delta para pelo minimo de n passos.
Não sei escolher entre eles. Acho que as pequenas diferenças relativas são melhores que as absolutas. E acho que diferenças no f são mais interessantes que no w.
Voce não quer que o \epsilon seja muito pequeno pois pode demorar muito para convergir para o minimo
Voce não quer que o \epsilon seja muito grande pois a descida do gradiente pode divergir (fugir do mínimo). veja as figuras aqui
Controlar o learning factor é uma das principais tópicos em descida do gradiente.
Há politicas gerais como - learning rate mais alto no começo (para andar rápido para o minimo e pequeno no final (para não escapar do minimo). Até onde eu sei, quando de fala de politicas gerais de mudança do learning rate usa-se o termo de learning rate scheduling.
As variações mais modernas usadas em redes neurais controlam o learning rate por dimensão - ou seja há um \epsilon_j para cada dimensão do espaço x_j, baseado no comportamento da projeção do gradiente naquela dimensão.
Vamos detalhar esses algoritmos quando falarmos de otimização não convexa, ja que a maioria dos algoritmos leva in consideração coisas como escapar de mínimos locais, etc que não é relevante para otimização convexa (que não tem mínimo local). Até onde eu sei, quando se fala de mudanças do learning rate “dentro” do algoritmo usa-se o termo adaptative learning rate
veja esse blog sobre l.r. schedule e adaptative l.r.
Uma parte central da descida do gradiente é o calculo do gradiente. Ha 3 alternativas teóricas, mas apenas 2 na pratica
se voce tem a formula da função f então é possível fazer a diferenciação simbolica de f para obter cada uma das dimensões de \nabla f. Por exemplo \frac{\partial f}{\partial x_i}.
Ferramentas como WolframAlpha e outras fazem diferenciação simbólica
automatic differentiation: dado um programa (em alguma linguagem de programação) que computa f é possível gerar outro programa que computa o gradiente de f. Isso é o que o TensorFlow faz - o principal uso do Tensoflow é gerar automaticamente o programa que computa o gradiente dado o programa que gera o f. O pyTorch também tem diferenciação automática.
Computar o gradiente numericamente: computa f(w_0) e f(w_0 + \delta_i) onde \delta_i é um pequeno passo na direção x_i. Assim \frac{\partial f}{\partial x_i}(w_0) = \frac{f(w_0 + \delta_i) - f(w_0)}{\delta_i}
Na prática eu não conheço a literatura que use a aproximação numérica ao gradiente, Obviamente, se estamos trabalhando com n dimensões, para calculo do gradiente haverá n chamadas explícitas para a função f, mas isso não deve ser computacionalmente mais caro que chamar a implementação do gradiente obtida por diferenciação simbólica ou automática (eu acho).
Biblioteca da Google que faz diferenciação automática
Versão 2.0
Tensoflow vem normalmente associado ao Keras.
Keras monta redes neurais
Tensorflow é a parte mais baixo do Keras que faz a diferenciação automática, e sabe distribuir as computações para CPU e GPU
autodifferentiation https://www.tensorflow.org/guide/autodiff
import tensorflow as tf
x = tf.Variable(7.5)
with tf.GradientTape() as tape:
if x>5:
for i in range(3):
y+=x**2
else:
for i in range(4):
y+=x
dx = tape.gradient(y,x)
dx<tf.Tensor: id=39, shape=(), dtype=float32, numpy=45.0>\frac{dy}{dx} = 3*\frac{d x^2}{dx} = 3*2*x
x = 7.5
O Torch é uma biblioteca do Facebook que faz diferenciação automática
PyTorch é a interface python para a biblioteca.
diferenciação automatica https://pytorch.org/tutorials/beginner/blitz/autograd_tutorial.html
Há 3 famílias de variações de decida do gradiente (de passo pequeno). Mas 2 dessas três só fazem sentido para problemas não convexos (onde há mínimos locais e regiões dom derivadas perto de zero em varias ou todas as direções. Veremos essas três variações numa próxima aula
Modificação adaptativa do learning rate - isso faz o learning rate mudar diferentemente em cada direção dependendo da historia dos updates naquela direção.
Momento: a atualização do w_{I+1} não é apenas na direção do gradiente, mas tem um componente na direção da atualização anterior
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çao e normalmente esse número é grande (0.9 ou mesmo 0.99)
Note que não é preciso andar exatamente na direção oposta ao gradiente para fazer progresso. Se vc andar consistentemente numa direção que diminui a função, voce chegara ao mínimo num problema convexo.
Isso permite que o gradiente seja calculado apenas aproximadamente se for o caso. Subgradiente é uma técnica mais moderna para problemas (convexos) que não necessariamente tem derivada em todos os pontos.