Maximizando a função barulhenta desconhecida

Estou interessado em maximizar uma função , onde . $f(\mathbf \theta)$ $\theta \in \mathbb R^p$

O problema é que não conheço a forma analítica da função ou de suas derivadas. A única coisa que posso fazer é avaliar a função ponto a ponto, um valor e obtendo uma estimativa NOISY nesse ponto. Se eu quiser, posso diminuir a variabilidade dessas estimativas, mas tenho que pagar custos computacionais crescentes. $\theta_*$ $\hat{f}(\theta_*)$

Aqui está o que eu tentei até agora:

Descida mais acentuada estocástica com diferenças finitas: pode funcionar, mas requer muita sintonia (por exemplo, sequência de ganho, fator de escala) e geralmente é muito instável.
Recozimento simulado: funciona e é confiável, mas requer muitas avaliações de funções, então achei bastante lento.

Então, eu estou pedindo sugestões / idéias sobre um possível método de otimização alternativo que possa funcionar sob essas condições. Estou mantendo o problema o mais geral possível, a fim de incentivar sugestões de áreas de pesquisa diferentes das minhas. Devo acrescentar que estaria muito interessado em um método que me desse uma estimativa do Hessian na convergência. Isso ocorre porque eu posso usá-lo para estimar a incerteza dos parâmetros . Caso contrário, terei que usar diferenças finitas em torno do máximo para obter uma estimativa. $\theta$

optimization monte-carlo simulation Jugurtha
fonte

Se você não puder dizer nada mais específico sobre o ruído associado à saída da sua função, não tenho certeza de que algo mais sofisticado do que o recozimento simulado (você precisará ajustar isso, até certo ponto) será útil.

Aron Ahmadia 9/10/12

Infelizmente, não sei muito sobre o ruído aleatório associado a cada avaliação de função. Sua distribuição é desconhecida e pode ser uma função de

. Por outro lado, os ruídos que afetam sucessivas avaliações de funções são independentes. Obviamente, estou assumindo que a variação do ruído não é enorme, caso contrário a maximização seria impossível.

θ

$\theta$

Jugurta

Por outro lado supor que eu sei algo sobre a distribuição de ruído, por exemplo, que

. Esse conhecimento me ajudaria?

\hat{f} (θ_{*}) \sim N (f (θ_{*}), σ)

$\hat{f}(\theta_*) \sim N(f(\theta_*),\sigma)$

Jugurta

Parece que eu estou corrigido pelo Prof. Neumaier :)

Aron Ahmadia

Aqui, os físicos, usei o CMA-ES para modelar a fase óptica (otimizando a fase de um pulso de laser através de um modelador de pulsos), que é bastante barulhento.

tillsten

Respostas:

Nosso pacote Matlab SnobFit foi criado precisamente para esse fim. Nenhuma suposição sobre a distribuição do ruído é necessária. Além disso, os valores das funções podem ser fornecidos através de arquivos de texto, assim você pode aplicá-lo às funções implementadas em qualquer sistema capaz de gravar um arquivo de texto. Consulte
http://www.mat.univie.ac.at/~neum/software/snobfit/

O SnobFit havia sido desenvolvido para uma aplicação em que a função a ser otimizada nem existia, e os valores das funções (uma medida da qualidade de fabricação) foram obtidos por equipamentos especializados e caros, criando produtos de amostra e medindo-os manualmente, resultando em cerca de 50 funções. avaliações por dia.

Arnold Neumaier
fonte

Muito obrigado pela sua resposta. Comecei a ler seu artigo sobre o pacote SnobFit e acho realmente interessante. Além disso, ao ler a introdução do seu artigo, percebi que o problema com o qual estou lidando (em um contexto estatístico) é bastante frequente na matemática industrial. Existe uma vasta literatura da qual eu desconhecia completamente. Na verdade, a abordagem em que eu estava trabalhando é um pouco semelhante à aproximação quadrática de Powell (2002).

Jugurta

O snobfit funciona bem com 128 graus de liberdade? Só para saber que vale a pena experimentar o meu caso.

tillsten

@tillsten: Nenhum método para problemas ruidosos funciona bem com 128 dof, a menos que você possa gastar um grande número de valores de função. Você pode experimentar o nosso VXQR1, no entanto, que é para problemas não barulhentos, mas às vezes lida bem com problemas barulhentos.

Arnold Neumaier 11/11

O limite para o Snobfit é de cerca de 20 variáveis. se você tiver mais, precisará selecionar, por senso comum, grupos de 20 variáveis que você otimizará parcialmente. Ou você pode deslizar algumas variáveis simultaneamente para que a dimensão seja reduzida.

Arnold Neumaier 11/10/12

Existem várias técnicas de otimização bayesiana que você pode tentar. As mais fáceis são baseadas no processo gaussiano:

Harold J. Kushner. Um novo método para localizar o máximo de uma curva multipico arbitrária na presença de ruído. Journal of Basic Engineering, páginas 86: 97-106, março de 1964.
J. Mockus. A abordagem bayesiana da otimização global. Notas de aula em Ciências do Controle e da Informação, 38: 473–481, 1982.
Niranjan Srinivas, Andreas Krause, Sham Kakade e Matthias Seeger. Otimização do processo gaussiano no cenário de bandidos: sem arrependimentos e desenho experimental. Em Proc. Conferência Internacional sobre Aprendizado de Máquina (ICML), 2010.
Andreas Krause, Ajit Singh e Carlos Guestrin. Posicionamentos de sensores quase ótimos em processos gaussianos: teoria, algoritmos eficientes e estudos empíricos. J. Mach. Aprender. Res., 9: 235–284, junho de 2008.

Eles operam, formando funções posteriores a plausíveis, dando observações até agora e sugerindo o próximo ponto para aprender rapidamente a função e encontrar os máximos globais (veja meu post no blog ).

Outra vantagem é que você pode estimar o Hessian no máximo. No entanto, você precisa especificar um modelo de ruído.

Memming
fonte

O algoritmo SPSA de James Spall (abreviação de Recozimento Simulado de Perturbação Estocástica, se bem me lembro) foi projetado para exatamente esse tipo de problema. Ele tem alguns papéis em que o usa para problemas como o que você descreve.

Wolfgang Bangerth
fonte

Eu tentei a abordagem de Spall com base em uma versão estocástica de descida mais íngreme e Raphson Newton. Eu tentei o Simulated Annealing, mas não a versão sugerida por Spall, eu deveria experimentá-lo. Não estou realmente entusiasmado com o recozimento simulado, porque não consigo obter uma estimativa do Hessian na convergência (enquanto, por exemplo, com o estocástico Raphson Newton, posso obter uma aproximação ao Hessian "de graça").

Jugurta