detalhes práticos da implementação da Otimização Bayesiana

8

Estou testando a otimização bayesiana, seguindo Snoek, Larochelle e Adams [ http://arxiv.org/pdf/1206.2944.pdf] , usando GPML [ http://www.gaussianprocess.org/gpml/code/matlab / doc /] . Eu implementei a função de aquisição de melhoria esperada descrita na página 3, e estou assumindo que estou certo de que para decidir onde próxima consulta meu objetivo devo levar o que maximiza:x

aEI(x;(xn,yn,θ))

Mas eu não consigo encontrar orientação sobre o conjunto de candidatos 's considerar. Teoricamente, eu gostaria de encontrar o melhor em todo o domínio, e o artigo foi escrito de uma maneira que parece sugerir que isso é possível ("[AE] também tem uma forma fechada no processo gaussiano" ) Mas, como uma questão prática, preciso calcular as médias e variações preditivas posteriores a qualquer eu possa considerar antes de poder calcular e enquanto essas posteriores têm como um formulário fechado, ainda preciso calculá-los usando álgebra matricial, portanto não consigo encontrar uma maneira de escolher um monte de 's.x xa E I ( x ) xxxxaEI(x)x

A questão: qual é um método prático para escolher o conjunto grande (médio? Pequeno?) De candidatos sobre os quais eu maximizo EI (ou qualquer outra função de aquisição)? (Isso está no jornal em algum lugar e eu perdi isso?)x

No momento, estou apenas pegando meu conjunto atual , amostrando-o com substituição 2000 vezes e adicionando algum ruído gaussiano a cada ponto. Parece bom, eu acho.xi

stackoverflax
fonte
Ainda não li este artigo, mas você considerou a amostragem do domínio de interesse usando um Latin Hypercube Design? en.wikipedia.org/wiki/Latin_hypercube_sampling
RustyStatistician
Uma alternativa seria organizar o domínio em grade (se possível) e depois avaliar todos os pontos desse domínio em grade.
RustyStatistician
Ambas são sugestões sensatas, obrigado! Não sabemos muito sobre hipercubos em latim, mas domínios com grade regulares significariam que a álgebra de Toeplitz e Kronecker poderia ser usada, o que tornaria as coisas agradáveis ​​e eficientes, mesmo com uma grade muito grande.
Stackoverflax

Respostas:

6

A norma é usar qualquer otimizador global que você desejar. O problema é que a superfície da EI é altamente multimodal e desconectada; otimizar essa função de aquisição é um problema não trivial em si.

Uma escolha comum que eu já vi em vários artigos é o algoritmo DIRECT ; às vezes eu vi o CMA-ES, que é um método de ponta em otimização não linear. Na minha experiência com outras formas de otimização, o MCS ( pesquisa de coordenadas em vários níveis ) tende a funcionar relativamente bem. Você pode encontrar uma revisão dos otimizadores globais sem derivativos aqui :

  • Rios e Sahinidis, "Otimização sem derivadas: uma revisão de algoritmos e comparação de implementações de software", Journal of Global Optimization (2013).

A propósito, a EI é analítica. Se você quiser, também pode calcular seu gradiente para orientar a otimização, mas isso não é necessário. Uma técnica eficaz é executar um otimizador global primeiro para encontrar soluções promissoras e, em seguida, executar um otimizador local para refiná-lo (por exemplo, um método quase-Newton como o BFGS, que é fminunc no MATLAB; ou fmincon, se você tiver restrições).

Finalmente, se a velocidade da otimização da função de aquisição é um fator (que não é o cenário BO "tradicional"), eu encontrei resultados decentes iniciando com um design Latin Hypercube ou um design de seqüência quase aleatória de Sobol, depois refinado com algumas etapas de um otimizador local a partir dos melhores pontos; veja também o comentário @ user777. Como esse não é o cenário de BO padrão, não tenho nenhuma referência específica que realmente use esse método.


Exemplos de trabalhos que se referem ao DIRECT ou CMA-ES:

  • Calandra, R., Seyfarth, A., Peters, J., & Deisenroth, MP (2015). Otimização bayesiana para aprender marcha sob incerteza. Anais de Matemática e Inteligência Artificial, 1-19 ( link ).
  • Mahendran, N., Wang, Z., Hamze, F., & Freitas, ND (2012). MCMC adaptável com otimização bayesiana. Na Conferência Internacional sobre Inteligência Artificial e Estatística (pp. 751-760) ( link ).
  • Artilheiro, T., Osborne, MA, Garnett, R., Hennig, P. e Roberts, SJ (2014). Amostragem para inferência em modelos probabilísticos com quadratura bayesiana rápida. In Advances in neural information processing systems (pp. 2789-2797) ( link ).

Você pode pesquisar no Google "otimização bayesiana" + o algoritmo de otimização global desejado e encontrará vários papéis. Além disso, em praticamente todos os outros artigos sobre BO, você encontraria uma frase como :

[...] o BO geralmente requer um otimizador global auxiliar em cada iteração para otimizar a função de aquisição. É habitual na literatura da BO usar os RETANGULARES DIRIGIDOS (DIRETO) para realizar essa tarefa. Outros algoritmos de otimização global como o CMA-ES também podem ser aplicados.

lacerbi
fonte
Isso é realmente surpreendente para mim! Você pode me indicar um documento de otimização bayesiano representativo que você tem em mente que usa DIRECT ou CMA-ES? Obrigado.
stackoverflax
Por que isso é surpreendente? Essa é a norma - você encontrará referências ao DIRECT ou a outros otimizadores globais em praticamente todos os artigos da BO. Provavelmente, é tão conhecido na comunidade que alguns jornais nem se dão ao trabalho de mencionar - isso é dado como certo. Eu adicionei algumas referências no meu comentário principal acima.
lacerbi
Esta não é necessariamente uma boa solução, mas eu achei que pode ser mais barato avaliar a EI em um conjunto de pontos amostrados usando o Hypercubes Latinos nos casos em que você só precisa estar próximo ao mínimo, mas não necessariamente em cima dele.
Sycorax diz Restabelecer Monica
@ user777: Sim, se houver velocidade, estou usando as sequências quase aleatórias do LH e Sobol como design inicial (encontrando uma pequena vantagem com o último, mas pode ser dependente do problema) e executando um otimizador local como BFGS a partir dos melhores pontos. Vou adicionar isso ao comentário principal.
lacerbi
Uma maneira de justificar a natureza ad hoc da abordagem LHS é que não é necessário encontrar o mínimo de uma função estocástica (superfície) porque o erro na estimativa do mínimo irá inundar os ganhos minuciosos de precisão. Esta é uma resposta muito boa, no entanto. Fico feliz que alguém aqui se importe com BO. :-)
Sycorax diz Restabelecer Monica