Decida do gradiente (de passo pequeno)

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$ $y$ e $z$ as três dimensões do $R^3$ então

$gradiente f = \nabla f = \left[ \begin{array}{r} \frac{\partial f}{\partial x} \\ \frac{\partial f}{\partial y} \\ \frac{\partial f}{\partial z} \\ \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.

Descida do 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}$.

taxa de convergência

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.

1. 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 gerias de mudança do learning rate usa-se o termo de learning rate scheduling.

2. 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.

Calculo do gradiente

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).

Tensorflow

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

• Antes havia outra infraestrutura Theano alem de TensorFlow para fazer a diferenciação automática (embora não tenho 100% de certeza que ele fazia diferenciação automática e não simbólica - o site do Theano fala em diferenciação simbólica)

Até onde eu entendi, a diferenciação automática em Tensorflow é feito pela classe GradentTape

O Tensorflow tem também sua própria implementação de Descida do gradiente GradientDescentOptimizer que implementa um passo da descida do gradiente.

Variações da descida do gradiente

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)

• Stocastic gradient descent e minibatch - a ser vista na próxima aula

Subgradiente e aproximações ao gradiente

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.