21/4/20
Funções não convexas tem:
Talvez seja útil em distinguir mínimos locais de “ruídos” ou “ondinhas” por exemplo esta figura
Voce não vai poder evita os mínimos locais “grandes” mas voce quer evitar os mínimos devido a ondinhas.
Em aprendizado de maquina, achar o mínimo global não é tão importante. Normalmente o que você quer é um mínimo local (ou mesmo um ponto que não é o mínimo) mas com o valor da função baixo o suficiente.
Em outras áreas de engenharia e economia voce quer o mínimo global mesmo.
otimização de redes neurais
busca de hiperparametros em algoritmos
todos os algoritmos de ML tem hiperparametros (números ou valores que voce precisa definir antes de rodar o algoritmo.
como o \(\lambda\) da aula passada em otimização de 2 funções ao mesmo tempo
voce quer escolher os hiperparametros que minimizam o erro do algoritmo num conjunto de teste
esse problema tem baixa dimensão (3 ou 4 hiperparametros normalmente)
nem todas as variáveis são continuas: profundidade máxima de uma arvore de decisão é um numero inteiro; alguns hiperparametros são a escolha de um em poucos valores (algoritmo para calcular a impureza numa arvore de decisão, ou tipo de kernel num SVM)
não há mínimos muito difíceis (estreitos e profundos) na minha experiencia, mas há regiões que a função é alta e outras ela é mais baixa
a função pode ser por degraus: mexer no hiperparametro muito pouco não muda a taxa de acerto do classificador (num conjunto de teste particular) e
a função pode ter um ruído aleatório (mesma chamada da função pode retornar 2 valores diferentes) se estamos testando em conjuntos diferentes. (neste caso eu acho que a função é chamada de stocastic)
descida do gradiente que seja insensível ao “ruído” - momento.
acha um mínimo local “grande” - se houver tempo reinicie a descida de outro ponto inicial aleatório
lembre-se da melhor solução
é/era a técnica tradicional em redes neurais (agora não sei se usa-se o recomeço aleatório)
isso funciona com qualquer método para problemas convexos. Inicie de um ponto aleatório, acha uma solução, reinicie de outro ponto.
busca cega: sem informação do valor da função - apenas se lembre do menor valor
grid search - escolha um grid para cada dimensão.
grid em cada dimensão
busque o valor da função nos pontos do grid de todas dimensões
trivialmente paralelizável
escolha os valores para cada dimensão aleatoriamente, segundo uma distribuição
grid uniforme equivale a uma distribuição uniforme
grid exponencial equivale a uma ditribuição uniforme no expoente.
há possibilidades de outras distribuições
trivialmente paralelizavel
mais fácil de controlar o numero de pontos a serem explorados
há um paper famoso que argumenta que random search é melhor que grid search
Usam o resultado da função nos pontos explorados anteriormente para propor novos pontos de exploração.
Lembre-se do melhor ponto visto ate agora, e reporte ele ao final do tempo
Tem que balançar exploration - buscar regiões novas nunca vistas - com explotitation - procurar cuidadosamente em volta de pontos que parecem bons. Em portugues as duas palavras são traduzidas por exploração
Particle swarm optimization (PSO)
Simulated annealing (SA)
covariance matrix adaptation evolution strategy (CMA-ES)
Bayesian optimization
outras:
há N partículas explorando o espaço das variáveis
cada particula \(i\) inicia numa posição aleatória \(x_i\) e com uma “velocidade” (modulo e direção) aleátoria \(V_i\).
o grupo se lembra da melhor posição explorada até agora (g)
cada particula tem um grupo de “amigos” ou vizinhos
o novo ponto da particula é \(x_{i+1} = x_i + V_i\)
a nova velocidade é atualizada para cada dimensão \(V_{i+1,d}\) e leva em consideração a velocidade anterior do ponto (“momento”), a posição do melhor ponto encontrado até agora (“componente cognitivo”) e o melhor ponto encontrado pelos seus vizinhos \(p_i\) (“componente social”)
\(\omega, \phi_1\) e \(\phi_2\) são hiperparametros do PSO (alem de N: número de partículas)
\[ \omega * v_{i,d} + \phi_1 * u_1 * (p_{i,d} - x_{i,d}) + \phi_2 * u_2 * (g_d - x_{i,d})\]
\(\omega*v_{i,d}\) é o momento, tende a continuar com a mesma intensidade na dimensão \(d\)
\(\phi_1 * u_1 * (p_{i,d} - x_{i,d})\) a partícula também tende a ir para o mínimo encontrado pelos seus vizinhos. \(u_1\) é um numero aleatório ente 0 e 1
\(\phi_2 * u_2 * (g_d - x_{i,d})\) a partícula também tende a ir em direção o minimo global (até agora) \(u_2\) é um numero aleatorio ente 0 e 1
É mais ou menos claro o balanço entre exploration (momento) e exploitation (social e cognitivo)
mantem um ponto (estado) \(x\)
verifica um estado “vizinho” \(y\) (pode ser um ponto aleatório no espaço todo ou apenas em volta do \(x\))
se \(f(y)<f(x)\) então \(y\) é o novo estado
senão aceita \(y\) como o novo estado com probabilidade \(P(f(y)-f(x),T)\) onde T é a "temperatura.
uma função comum para \(P\) é \(P = e^{-(f(y)-f(x))/T}\)
T alta: aumenta a probabilidade de aceitar o ponto. Se T é infinito \(P=e^0 = 1\)
T baixa: diminui a probabilidade. Com T=0 a probabilidade é 0.
T começa alta e vai diminuindo com o tempo - cooling schedule
exploration no começo, e exploitation no final
Se baseia em distribuições gaussianas em n dimensões (n a dimensão do espaço de busca). A gaussiana tem uma media (que a um ponto no espaço) e uma matriz de covariância (quadrada e simetrica) que é a extensão da ideia de desvio padrão de uma gaussiana tradicional.
dados N pontos, ajusta uma gaussiana aos pontos de tal forma que a probabilidade de cada ponto é proporcional a \(1/f(x)\). Pontos com menores valores de \(f\) tem maior probabilidade.
gera novos pontos amostrados da gaussiana (maior probabilidade na região de pontos com menores valor).
ha formulas e algoritmos/truques para aproximar a matriz de covariância que precisariam de muitos pontos para serem estimada com precisão.
tenta montar uma função que aproxima não so \(f\) nos pontos onde voce sabe o valore de \(f(x)\) mas tambem a distribuição de probabilidade dos possivies valores de \(f\) nos pontos onde voce não sabe. figura e outra figura
as funções que aproximam essa distribuição de probabilidade são chamados de Surrogate Function. Tradicionalmente usa-se gaussian process (GP) para gerar essa distribuição, mas há outras alternativas mais rápidas (GP é bem lento).
uma vez que temos essa distribuição do nosso desconhecimento sobre \(f\), podemos decidir qual ponto \(x\) explorar. Usa-se uma medida aquisition function para decidir. Uma aquisition function é o expected improvement: o valor esperado de melhorar o valor do mínimo da função ate agora
\[EI(x) = E[max(f^* - \hat{f}(x)]\]
onde \(f^*\) é o mínimo até agora, e \(\hat{f}(x)\) é a distribuição de valores possíveis (segundo a surrogate function) para \(f(x)\).
escolha o próximo ponto o que tem o maior expected improvement figura
ha alguns outros aquisition functions (eu acho que EI faz mais exploitation que exploration)
AutoML é a ideia de automaticamente buscar os hiperparametros de um conjunto de classificadores.
A parte central de AutoML é uma busca pelos melhores hiperparametros usando algum algoritmo de otimização no convexa pagina sobre AutoML
Otimização bayesiana parece ser a técnica mas comum para essa busca.
Na minha experiencia (1s2019), GP como surrogate function é muito lento.
Uma parte quente de autoML é a busca automática por arquiteturas de redes deep