14/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 projetar o ponto w_{i+1} para um ponto v_{i+1} o mais perto de w_{i+1} mas v_{i+1} \in R
v_{i+1} = P_R(w_{i+1}
onde P_R é a operaçao de projeção para o conjunto R.
Se w_{i+1} \in R entao v_{i+1} = w_{i+1}
se nao, então v_{i+1} estará na fronteira de R.
a operação P_R é muito mais fácil em problemas boxed, pois é facil verificar se w_{i+1} \in R e é mais facil fazer a projeção. Essa computação pode ser bem mais complicada para inequality constraints genéricos,
O ponto novo w_{i+1} pode vir de qq algoritmo (decida do gradiente, decida do gradiente com passo grande, Nelder-Mead, etc).
Eu nao acho que há garantia que o projected gradient converge para a solução (veja a figura em https://math.stackexchange.com/questions/571068/what-is-the-difference-between-projected-gradient-descent-and-ordinary-gradient)
Boxed:
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 |
\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.
