Qual é a diferença entre Otimização Bayesiana (Processos Gaussianos) e Recozimento Simulado na prática

8

Ambos os processos parecem ser usados ​​para estimar o valor máximo de uma função desconhecida, e ambos obviamente têm maneiras diferentes de fazer isso.

Mas, na prática, um dos métodos é essencialmente intercambiável? Onde eu gostaria de usar um sobre o outro?

https://en.wikipedia.org/wiki/Simulated_annealing

http://www.iro.umontreal.ca/~bengioy/cifar/NCAP2014-summerschool/slides/Ryan_adams_140814_bayesopt_ncap.pdf

Pergunta semelhante
Otimização bayesiana ou descida de gradiente?

canyon289
fonte
Não acho que isso seja suficientemente exaustivo para ser uma resposta, mas o recozimento simulado geralmente requer um número maior de avaliações de funções para encontrar um ponto próximo ao ideal global. Por outro lado, a otimização bayesiana está construindo um modelo a cada iteração, mas requer relativamente poucas avaliações de funções. Portanto, dependendo de quão dispendiosa a função é avaliada, você prefere uma à outra, porque ela terá um tempo de parede menor: Otimização Bayesiana nos casos em que a função é muito cara e recozida quando a função é relativamente barata.
Sycorax diz Restabelecer Monica
@ Sycorax Bumping 10 posts sobre mais ou menos o mesmo tópico em 10 minutos - um pouco excessivo, você não acha? Aparentemente não, mas eu faço.
Mark L. Stone
@ MarkL.Stone É mais ou menos "tempo lento" (20h de uma sexta-feira, a partir das edições), que é o horário preferido para fazer isso. Há uma meta thread.
Sycorax diz Restabelecer Monica

Respostas:

8

O recozimento simulado (SA) é um algoritmo muito simples em comparação com a otimização bayesiana (BO). Nenhum dos métodos assume convexidade da função de custo e nenhum dos métodos se baseia fortemente em informações de gradiente.

A SA é, de certa forma, uma caminhada aleatória levemente educada. A solução candidata salta pelo espaço da solução, com uma programação de salto específica (o parâmetro de resfriamento). Você não se importa onde aterrissou antes, não sabe onde aterrará em seguida. É uma abordagem típica da cadeia de Markov. Você não modela nenhuma suposição forte sobre a superfície da solução subjacente. A otimização do MCMC percorreu um longo caminho desde o SA (veja, por exemplo, o Hamiltoniano Monte Carlo ), mas não expandiremos mais. Um dos principais problemas do SA é que você precisa avaliar muitas vezes "rapidamente". E faz sentido, você precisa de tantas amostras quanto possível para explorar o maior número possível de estados (ou seja, soluções candidatas). Você usa apenas um pouquinho de informações de gradiente (que quase sempre aceita soluções "melhores").

Olhe agora para BO. A regressão BO (ou simplisticamente Processo Gaussiano (GP)) sobre suas avaliações da função de custo) tenta fazer exatamente o oposto em termos de avaliação da função. Ele tenta minimizar o número de avaliação que você faz. Ele cria um modelo não paramétrico específico (geralmente um GP) para sua função de custo que geralmente assume ruído. Ele não usa informações de gradiente. O BO permite criar um modelo informativo da sua função de custo com um pequeno número de avaliações de funções. Depois, você "consulta" essa função ajustada por seus extremos. Novamente, o diabo está nos detalhes; você precisa provar de forma inteligente (e presumir que o seu prior também é meio razoável). Há um trabalho sobre onde avaliar sua função a seguir, especialmente quando você sabe que ela realmente evolui um pouco com o tempo (por exemplo, aqui ).

Uma vantagem óbvia do SA sobre o BO é que, no SA, é muito simples colocar restrições no espaço da sua solução. Por exemplo, se você deseja soluções não-negativas, basta limitar sua distribuição de amostras em soluções não-negativas. O mesmo não é tão direto no BO, porque mesmo você avalia suas funções de acordo com suas restrições (por exemplo, não negatividade), você também precisará restringir seu processo; esta tarefa, embora não seja impossível, está mais envolvida.

Em geral, é preferível a SA nos casos em que a função de custo é barata de avaliar e a BO nos casos em que a função de custo é cara de avaliar. Eu acho que o SA está lenta mas firmemente caindo em desuso; especialmente o trabalho de otimização sem gradiente (por exemplo , NEWQUA , BOBYQA ) tira uma de suas principais vantagens em comparação com os métodos padrão de descida com gradiente, que não precisam avaliar uma derivada. Da mesma forma, o trabalho no MCMC adaptável (por exemplo, consulte a referência acima) o torna um desperdício em termos de otimização do MCMC para quase todos os casos.

usεr11852
fonte
Obrigado pela resposta. Vejo que você provavelmente está certo sobre o recozimento cair em desuso. O scipy o substituiu em favor do basinhopping docs.scipy.org/doc/scipy-0.15.1/reference/generated/…
canyon289
Estou feliz por poder ajudar. Obrigado pela dica; Eu não estava ciente dessa mudança no SciPy.
usεr11852
A menos que as restrições sejam realmente difíceis, qual é o grande problema em restringir um ajuste de GP? Obviamente, quando você "consulta" a função ajustada, realiza uma otimização restrita. Não estou tentando ser sarcástico, quero muito saber quais dificuldades você vê. Por exemplo, restrições lineares de igualdade e desigualdade devem ser um pedaço de bolo. Se você tiver restrições não convexas, como restrições de igualdade não lineares ou restrições de números inteiros, elas podem se enquadrar na minha categoria gnarly.
Mark L. Stone
@ MarkL.Stone: Mesmo restrições lineares (e muito menos as retorcidas queridos) pode afetar a instalação em dimensões superiores severamente - mesmo se você se encaixa " algo " Eu duvido seriamente que este ajuste seria representação exata do que você quer. Além disso, a maioria dos resultados baseados em continuidade por trás da otimização de GPR desaparecem da janela ... Só para deixar claro: eu não usei o BO extensivamente porque sempre se mostrou abaixo do ideal para os problemas com os quais trabalho. Supondo que o método Quasi-Newton padrão falhe, eu sempre advogaria primeiro uma abordagem sem derivadas ou uma abordagem HMC.
usεr11852
Bem, se eu tenho restrições, o que eu quero é que a função ajustada satisfaça as restrições. Acredite, tenho minhas dúvidas de quão bem um ajuste de GP será uma representação precisa do que eu quero, com ou sem restrições. Boas restrições podem ajudá-lo - elas restringem as coisas para onde deveriam estar e evitam que você perca tempo em regiões ruins. Claro, isso é se eles forem bem implementados. Você pode dar um exemplo de um resultado baseado em continuidade por trás da otimização GPR que sai pela janela quando existem restrições lineares? Para ser um exemplo válido, é melhor ter estado na janela sem restrições.
Mark L. Stone