Jacques Wainer
se \(f(w)\) é:
então vc quer minimizar \(f\)
se \(f(w)\) é:
voce quer maximizar \(f\)
minimizar : Obtenha \(w_0\) tal que \(f(w_0) \le f(w)\) para \(w \in A\)
maximizar : Obtenha \(w_0\) tal que \(f(w_0) \ge f(w)\) para \(w \in A\)
\(A\) é a restrição nos valores de \(w\)
\(A\) pode não ser restrição alguma. Se \(w\) tem \(n\) dimensões, \(A = R^n\) - problemas sem restrições
mínimo global: \(w_0\) tal que \(f(w_0) \le f(w)\) para \(w \in A\)
mínimo local: \(w_0\) tal que \(f(w_0) \le f(w)\) para \(|w_0 - w| < \epsilon\) para algum \(\epsilon >0\).
\[arg \min_{w \in A} f(w)\]
ache \(w\) que minimize \(f(w)\)
subject to \(w \in A\)
ou programação linear
\[f(w) = \alpha_1 w_1 + \alpha_2 w_2 + ... + \alpha_n w_n\]
ou
\[f(w) = \alpha^T w\]
para
\[w \in A\]
\[\beta_1^T w + c_1 \le 0\]
\[\beta_2^T w +c_2\le 0\]
\[\beta_3^T w +c_3\le 0\]
Solução esta nos vértices do politopo (politopo é a extensão multidimensional de um poliedro - que é a extensão 3D de uma figura geometrica 2D)
minimizar: convexa
maximizar: côncava
função \(f()\) é convexa se:
\[f(\theta w + (1-\theta) v) \le \theta f(w) + (1-\theta) f(v)\]
se \(f()\) é convexo e \(A\) é convexo então só existe um mínimo local e ele é o mínimo global!
Não vale se \(A\) não é convexo.
para a solução de problemas convexos sem restrições
vamos converter problemas com restrições para um outro problema (com mais variáveis) sem restrições.
há mínimos locais e poucos (ou apenas 1) mínimo global
ha pontos críticos - derivada em todas as direções = 0 mas não são pontos de minimo ou maximo
pontos de sela e ponto de inflexão texto e imagens da khan academy figura de um ponto de sela
pontos de sela são minimo em uma direção e maximo em outra. Pode haver uma combinação qualquer de maximo/minimo e inflexao: num espaco de 40 dimensões um ponto critico (derivada = 0) pode ser maximo para 12 direcoes, minimo para 18 direções e inflexao para as restantes 20!.
assume que é convexo - acha um minimo local, e recomeça
algoritmos de descida do gradiente que são mais insensíveis a pequenos mínimos locais (momento)
busca em força bruta/cegos: grid e aleatório
algoritmos tipo genético - PSO e CMA
otimização bayesiana
\[\frac{\partial f}{\partial w_i} = 0 \quad e \quad \frac{\partial^2 f}{\partial w_i} > 0\]
Se voce sabe que \(f\) é convexa, então a segunda parte não é importante, o unico ponto com derivadas 0 é o minimo global.
É difícil dizer se uma função é convexa ou não só olhando para a formula.
Dado \(N\) \(x_i\), um dado, e \(y_i\), a saída associada a \(x_i\)
Encontre \(\alpha\) e \(\beta\) tal que
\[y = \alpha x + \beta\]
quando aplicada a cada \(x_i\) e \(y_i\) tenha o menor erro possível.
\(\hat{y}_i\) é o valor predito pela equação quando \(x = x_i\) e \(y_i\) é o valor correto.
erro quadrado \(e_i = (y_i - \hat{y}_i)^2\), ou \(e_i = (y_i -\alpha x_i -\beta)^2\)
erro absoluto \(e_i = |y_i - \alpha x_i - \beta |\)
o que vc não quer é algo como \(e_i = y_i -\alpha x_i -\beta\) que pode ser negativo ou positivo. Não queremos erros negativos compensando erros positivos.
vamos usar o erro quadrado.
erro medio (MSE) = \(\frac{1}{N} \sum_i e_i^2\)
\(x_i\) e \(y_i\) não são variáveis, \(\alpha\) e \(\beta\) são
\(\langle \alpha, \beta \rangle\) é o vetor de variáveis \(w\).
ache \(\alpha, \beta\) que minimiza \(MSE(\alpha,\beta) = \frac{1}{N} \sum e_i^2\)
= \(-\frac{2}{N} \sum y_i x_i + \frac{2 \alpha}{N} \sum x_i^2 - \frac{2 \beta}{N} \sum x_i = 0\)
etc
Veja que \(\sum x_i\), \(\sum x_i y_i\), \(\sum y_i\) e \(\sum x^2_i\) são constantes. E \(\frac{\sum x_i}{N}\) é na verdade a média dos \(x_i\).
No final haverá 2 equações e duas incognitas. A solução é
\[\alpha = \frac{N \sum x_i y_i - \sum x_i \sum y_i}{N \sum x^2_ i - (\sum x_i)^2}\]
\[\beta = \frac{\sum y_i}{N}-\alpha \frac{\sum x_i}{N}\]
É possivel fazer as derivações das derivadas para mais de uma dimensão dos dados, mas ai a notação matricial é util. Eu acho que o texto abaixo faz isso. So para voce ver alguma vez derivações algebricas usando matrizes e vetores. texto em ingles
Eu mencionei em aula que o SVD truncado (nos primeiros k valores singulares) é a soluçao de otimizacao de reduzir a dimensionalidade de uma matrix de m colunas para k colunas. Isso é chamado do teorema de Eckart-Young
Voce pode ver a demostração disso e principalmente a formulacao do problema de otimizacao nessa pagina da wikipedia. Vale a pena passar algum tempo entendendo a formulação (nao necessariamente a demonstração).
