Jacques Wainer
16/4/20
ache \(w\) que minimiza \(f(w)\) desde que \(w \in R\)
\(w \in R\) é a restrição
Para problemas onde \(f\) é convexo e \(R\) é convexo, só há um mínimo.
Usa-se diferentes nomes para diferentes formatos da restrição
bounded ou boxed a região \(R\) é um hiper-retângulo. Se \(w_i\) é a i-esima variável de \(w\) então essa restrição é
equality constraint a região \(R\) é uma superfície no espaço (tem menos dimensões que o espaço original.
restrições do tipo \(g_k(w) = 0\)
pode haver varias dessas restrições
inequality constriant \(R\) é uma região do espaço
A ideia do algoritmo de projected gradient é na linha do GD de passo grande.
é preciso achar o \(\alpha\) para dar o passo \(w_{i+1} = w_{i} - \alpha \nabla f (w_i)\)
vc precisa fazer um line search para achar o \(\alpha\)
garanta que o line search seja apenas na região \(R\). Assim \(w_{i+i}\) sempre satisfará a restrição \(w \in R\).
projected gradient é muito mais fácil em problemas bounded, pois é fácil achar quais são os limites do \(R\) para procurar o mínimo na direcão \(w_{i} - \alpha \nabla f (w_i)\)
essa computação pode ser bem mais complicada para inequality constraints genéricos,
eu acho que projected gradient não funciona com equalilty constraints.
eu acho que a ideia de projected gradient funciona também para o Nelder-Mead (é só garantir que o vértice do triângulo que se move esta dentro da região \(R\).
Vamos assumir que só há uma restrição por igualdade.
A ideia dos multiplicadores de Lagrange é acrescentar mais uma variável e modificar a função a ser minimizada.
O problema passa a ser:
ache \(w,\lambda\) que minimiza \(f(w) - \lambda g(w)\)
A função \(L(w,\lambda) = f(w) - \lambda g(w)\) é chama de função lagrangeana, e o \(\lambda\) é o multiplicador.
a primeira parte da pagina sobre Lagrange Multipliers da wikipedia da uma intuição porque minimizar o lagrangeano resolve o problema original.
Se houver mais restrições de igualdade, por exemplo \(g(w) = 0\) e \(h(w)=0\) então a lagrangeana terá 2 multiplicadores
O ideia vale também para inequality constraints, mas a explicação é mais complexa (Karush–Kuhn–Tucker (KKT) conditions).
Há um problema que na verdade, os pontos críticos (onde o gradiente é zero mas não necessariamente o mínimo) da Lagrangeana é que são as soluções do problema original. Por outro lado não há algoritmos para achar pontos críticos, apenas mínimos - não sei como essas 2 idéias se resolvem.
Suponha que você quer minimizar 2 funções \(f(w)\) e \(g(w)\) simultaneamente.
A solução é combinar as 2 funções em apenas 1
ache \(w\) que minimiza \(f(w) + \lambda g(w)\)
\(\lambda>0\) é um hiperparametro - você precisa decidir antes de rodar a otimização qual o valor desse parâmetro.
Um \(\lambda\) grande da mais importância ao \(g\), um \(\lambda\) pequeno da mais importância ao \(f\)
VOCE precisa decidir qual o valor de \(\lambda\) antes da otimização
O problema central em aprendizado de maquina é minimizar o erro de previsão \(\sum_k erro(y_k - g(x_k, w))\) (onde o erro pode ser quadratico,modulo ou outra medida de erro.
Mas também há boas razoes para minimizar os \(w\) também. Ou seja, quer-se duas minimizações
Há duas formas mais comuns para minimizar os \(w\).Se \(w_i\) é a componente \(i\) do vetor \(w\)
regularização L2: minimize \(\sum_i w_i^2\)
regularização L1: minimize \(\sum_i |w_i |\)
L2 minimiza a soma dos quadrados do \(w\), enquanto que L1 minimiza a soma dos módulos.
Juntando as duas minimizações.
L2: minimize \(\sum_k erro(y_k - g(x_k, w)) + \lambda \sum_i w_i^2\)
L1: minimize \(\sum_k erro(y_k - g(x_k, w)) + \lambda \sum_i w_i^2\)
\(\lambda\) grande da mais peso para a regularização, enquanto que \(\lambda\) pequeno da mais peso para a minimização do erro de previsão
A regularização L1 tende a zerar alguns dos componentes de \(w\) e portanto ela e útil se você acha que tem variável de mais - a regularização L1 via tentar zerar o máximo delas que a minimização permite.
L1 força a esparsidade do vetor \(w\) (muitos/alguns componentes são 0).
este link tem uma boa explicação porque a regularização L1 prefere zerar algumas variáveis.
Regularização é a tentativa de diminuir os valores de \(w\).
Mas podemos usar as fórmulas da regularização para o erro também:
erro L2 é a soma dos quadrados dos erros individuais: \(\sum_k (y_k - g(x_k, w))^2\)
erro L1 é a soma dos módulos dos erros individuais \(\sum_k | y_k - g(x_k, w) |\)
Para o erro, L1 é mais insensível a outliers. Ha várias paginas na internet que discutem erro L1 vs erro L2.
