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
há também o problema de achar o zero em uma função 1D (root finding). Root finding é relacionado com minimização em 1D pois o minimo é or zero da derivada.
sem usar a derivada. mas é preciso definir o intervalo onde o algoritmo procurará o minimo (bracket)
golden ratio method https://en.wikipedia.org/wiki/Golden-section_search
Brent method https://en.wikipedia.org/wiki/Brent%27s_method
usando a derivada
secant method https://en.wikipedia.org/wiki/Secant_method
bissection method
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,
o conjugado gradiente foi inventado para obter soluçoes de um sistema de equações lineares A x = b que equivale a achar um minimo para a função f(x) = 1/2 x^T A x - x^T b
neste caso A = H f o Hessaino de f
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
ate onde eu sei, o CG não computa o Hessiano explicitamente (quem faz isso são os metodos quadráticos abaixo).
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)
(veja a derivação em https://en.wikipedia.org/wiki/Quasi-Newton_method
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)
A intuição é que o H não muda muito e portanto H^{-1}(w_{i}) \approx H^{-1}(w_{i-1}) com alguma nova informação vinda de \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.
