20/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 estocástica)
Funcionam para problemas suaves de vários mínimos.
descida do gradiente e momento evita mínimos pequenos
re inicialize o algoritmo em outros pontos iniciais e se lembre da melhor solução
Não sei se funciona para problemas com ondinhas (o gradiente varia muito de ponto em ponto)
Não funcionam para problemas mais comuns em aprendizado de maquina pois
pode não haver derivadas em algumas dimensões (valores inteiros e categóricos)
a função pode ser degrau (acurácia - taxa de acerto)
Algoritmos sem gradiente da aula passada devem funcionar
Noa sei nada sobre otimização estocástica
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 paralelizavel
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 distribuição uniforme no expoente.
há possibilidades de outras distribuições
trivialmente paralelizavel
mais fácil de controlar o número de pontos a serem explorados
há um paper famoso que argumenta que random search é melhor que grid search para busca de hiperparametros
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 partícula i inicia numa posição aleatória x_i e com uma “velocidade” (modulo e direção) aleatória V_i.
o grupo se lembra da melhor posição explorada até agora (g)
cada partícula tem um grupo de “amigos” ou vizinhos
o novo ponto da partícula é 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 mínimo global (até agora) u_2 é um numero aleatório 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 simétrica) 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 só f nos pontos onde voce sabe o valor de f(x) mas também a distribuição de probabilidade dos possíveis valores de f nos pontos onde voce não sabe. 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
há outros aquisition functions
um pagina bem detalhada sobre aquisition functions https://towardsdatascience.com/shallow-understanding-on-bayesian-optimization-324b6c1f7083
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