Jacques Wainer
15/4/20
GD com passo pequeno:
\[w_{i+1} = w_i - \epsilon \nabla f(w_{i})\]
Passo pequeno é o \(\epsilon\).
Para o passo grande, uma vez que eu sei que vou andar na direção \(- \nabla f(w_{i})\), porque eu não ando bastante (passo grande) nessa direção até achar um mínimo.
Esse vai ser o meu novo \(w_{i+1}\).
Assim: \[w_{i+1} = w_i - \alpha \nabla f(w_{i})\]
onde \(\alpha\) minimiza \(f(w_{i}- \alpha \nabla f(w_{i}))\)
\(minimize f(x)\) x é 1D
também chamado de line search
sem usar a derivada. mas é preciso definir o intervalo onde o algoritmo procurará o minimo (bracket)
usando a derivada
Na pratica, não se deve gastar muita computação para achar o minimo, uma aproximação já é o suficiente.
O conjugado gradiente é um GD de passo grande, que assume que a função \(f\) a ser minimizada é uma função quadrática,
assumindo isso (que pode não ser verdade) define não só o passo ótimo (o \(\alpha\) acima) mas tambem define que a cada update a direção a ser seguida não é exatamente a direção do gradiente.
o conjugado gradiente é essa nova direção que é perpendicular aos gradientes computados ate agora.
se a função é realmente quadrática, o CG só faz \(n\) (numero de dimensões) passos até chegar no minimo (só há \(n\) direções perpendiculares no espaço de \(n\) dimensões
Metodos quadraticos assumem que a função \(f\) localmente pode ser aproximada como uma função quadrática. Para isso precisamos do gradiente (como na descida do gradiente) e da matriz Hessiana que é a versão multidimensional da segunda derivada.
\(H\) é o Hessiano da função e a entrada \(i\) \(j\) da matriz é \(\frac{\partial f}{\partial w_i \partial w_j}\).
A matriz H é simétrica.
Se voce tem o H então o passo ótimo a ser dado na GD é
\[w_{i+1} = w_i - H^{-1}(w_i) \nabla f (w_i)\]
Como no conjugado gradiente a direção do passo nao é \(\nabla f (w_i)\) mas sim \(H^{-1}(w_i) \nabla f (w_i)\) (lembre-se \(H\) é uma matriz que pode mudar a direção de \(\nabla f\)).
Métodos de quasi-Newton não usam uma função explicita para o \(H\) (e portanto o \(H^{-1}\)) mas aproximam o \(H^{-1}\) com uma computação interativa baseada nos \(w_i\) e nos \(\nabla f (w_i)\)
Há vários algoritmos de aproximações para o \(H^{-1}\), mas o mais usado é o BFGS que são as iniciais dos 4 autores. Em particular usa-se a versão L-BFGS (que usa menos memória).
Métodos least square são métodos quadráticos (como os quasi Newton) mas que só funcionam para problemas onde a função \(f\) a ser minimizada é uma soma de erros quadrados, ou seja:
\[f(w) = \sum_k (y_k - g(x_k,w))^2\]
onde \(x_k\) é um dado de entrada, e \(y_k\) a sua saida correspondente. O erro tem que ser quadratico (e nao modulo ou outros).
Exemplos de metodos least square são
Em particular o Levemberg-Marquardt era usado (de vez em quando) nos anos 90 para redes neurais (dos anos 90). Eu não tenho ouvido mais falar no Levenberg-Marquardt recentemente.
Metodos que não usam o gradiente (ou o Hessiano). Dois exemplos:
O Nelder-Mead usa o equivalente a triângulos no espaço n-dimensional (chamados de simplex) e gera um novo ponto para substituir o vertice do “triangulo” que tem o maior valor para \(f\). Se \(w\) é o vertice com maior valor de \(f\), o novo ponto \(w^*\) estará entre o \(w\) e o centro geométrico do triangulo (contração - o triangulo diminui). Também pode estar nessa mesma direção mas além do ponto \(w\) (expansão - o triangulo cresce). Uma animação
O NEWUOA gera de \(2n\) a \(n^2/2\) pontos aleatórios e aproxima uma função quadrática usando os valores do \(f\) nesses pontos. Ele vai para o mínimo dessa função quadrática (aproximada) e usa esse novo ponto para gerar outra aproximação.
