Quelle est la différence entre l'optimisation bayésienne (processus gaussiens) et le recuit simulé dans la pratique

8

Les deux processus semblent être utilisés pour estimer la valeur maximale d'une fonction inconnue, et les deux ont évidemment des façons différentes de le faire.

Mais dans la pratique, l'une ou l'autre méthode est-elle essentiellement interchangeable? Où voudrais-je utiliser l'un sur l'autre?

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

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

Question similaire
Optimisation bayésienne ou descente de gradient?

canyon289
la source
Je ne pense pas que cela soit suffisamment exhaustif pour être une réponse, mais le recuit simulé nécessite généralement un plus grand nombre d'évaluations de fonctions pour trouver un point proche de l'optimum global. D'un autre côté, l'optimisation bayésienne construit un modèle à chaque itération mais nécessite relativement peu d'évaluations de fonctions. Ainsi, en fonction du coût de l'évaluation de la fonction, vous préféreriez l'un à l'autre car l'un aura un temps de paroi plus petit: optimisation bayésienne dans les cas où la fonction est très chère et recuit lorsque la fonction est relativement bon marché.
Sycorax dit Réintégrer Monica le
@Sycorax Bumper 10 posts sur plus ou moins le même sujet en 10 minutes - un peu excessif ne pensez-vous pas? Apparemment non, mais je le fais.
Mark L. Stone
@ MarkL.Stone C'est plus ou moins un "temps lent" (20h un vendredi, au moment des modifications) qui est le moment préféré pour le faire. Il y a un fil méta.
Sycorax dit Réintégrer Monica

Réponses:

8

Le recuit simulé (SA) est un algorithme très simple en comparaison avec l'optimisation bayésienne (BO). Aucune des méthodes ne suppose la convexité de la fonction de coût et aucune des méthodes ne s'appuie fortement sur les informations de gradient.

SA est en quelque sorte une marche aléatoire légèrement éduquée. La solution candidate saute dans l'espace de la solution avec un programme de saut particulier (le paramètre de refroidissement). Vous ne vous souciez pas de l'endroit où vous avez atterri auparavant, vous ne savez pas où vous atterrirez ensuite. Il s'agit d'une approche typique de la chaîne de Markov. Vous ne modélisez aucune hypothèse forte concernant la surface de la solution sous-jacente. L'optimisation MCMC a fait beaucoup de chemin depuis SA (voir par exemple Hamiltonian Monte Carlo ) mais nous ne nous étendrons pas davantage. L'un des problèmes clés avec SA est que vous devez évaluer beaucoup de fois "rapidement". Et cela a du sens, vous avez besoin d'autant d'échantillons que possible pour explorer autant d'états (ie. Solutions candidates) que possible. Vous n'utilisez qu'une infime partie du gradient (que vous acceptez presque toujours de «meilleures» solutions).

Regardez maintenant BO. BO (ou régression simpliste du processus gaussien (GP) sur vos évaluations de fonction de coût) essaie de faire exactement le contraire en termes d'évaluation de fonction. Il essaie de minimiser le nombre d'évaluations que vous faites. Il construit un modèle non paramétrique particulier (généralement un GP) pour votre fonction de coût qui suppose souvent du bruit. Il n'utilise pas du tout d'informations sur le gradient. BO vous permet de construire un modèle informatif de votre fonction de coût avec un petit nombre d'évaluations de fonction. Ensuite, vous "interrogez" cette fonction ajustée pour ses extrema. Encore une fois, le diable est dans les détails; vous devez échantillonner intelligemment (et supposer que votre a priori est également à moitié raisonnable). Il y a du travail sur où évaluer votre fonction ensuite, surtout quand vous savez que votre fonction évolue en fait légèrement au fil du temps (par exemple ici ).

Un avantage évident de SA par rapport à BO est qu'au sein de SA, il est très simple d'imposer des contraintes à votre espace de solution. Par exemple, si vous voulez des solutions non négatives, vous limitez simplement votre distribution d'échantillons dans des solutions non négatives. La même chose n'est pas si directe dans BO car même si vous évaluez vos fonctions en fonction de vos contraintes (disons non-négativité), vous devrez également contraindre votre processus; ce taske alors qu'il n'est pas impossible est plus impliqué.

En général, on préférerait SA dans les cas où la fonction de coût est peu coûteuse à évaluer et BO dans les cas où la fonction de coût est coûteuse à évaluer. Je pense que SA tombe lentement mais régulièrement en disgrâce; en particulier, le travail d'optimisation sans gradient (par exemple , NEWQUA , BOBYQA ) enlève l'un de ses principaux avantages par rapport aux méthodes de descente de gradient standard qui n'ont pas à évaluer une dérivée. De même, le travail sur MCMC adaptatif (par exemple, voir référence ci-dessus) le rend inutile en termes d'optimisation MCMC pour presque tous les cas.

usεr11852
la source
Merci d'avoir répondu. Je vois que vous avez probablement raison que le recuit tombe en disgrâce. scipy l'a déconseillé au profit de bassinhopping docs.scipy.org/doc/scipy-0.15.1/reference/generated/…
canyon289
Je suis content d'avoir pu aider. Merci pour le conseil; Je n'étais pas au courant de ce changement dans SciPy.
usεr11852
À moins que les contraintes ne soient vraiment noueuses, quel est le problème avec la contrainte d'un ajustement GP? Bien sûr, lorsque vous "interrogez" la fonction ajustée, vous effectuez une optimisation contrainte. Je n'essaie pas d'être sarcastique, je veux vraiment savoir quelles difficultés vous voyez. Par exemple, les contraintes linéaires d'égalité et d'inégalité devraient être un jeu d'enfant. Si vous avez des contraintes non convexes, telles que des contraintes d'égalité non linéaires ou des contraintes entières, celles-ci pourraient tomber dans ma catégorie noueuse.
Mark L. Stone,
@ MarkL.Stone: Même les contraintes linéaires (sans parler des noueuses ) peuvent gravement affecter l'ajustement dans les dimensions supérieures - même si vous ajustez " quelque chose ", je doute sérieusement que cet ajustement soit une représentation précise de ce que vous voulez. De plus, la plupart des résultats basés sur la continuité derrière l'optimalité GPR sortent de la fenêtre ... Juste pour être clair: je n'ai pas beaucoup utilisé BO car il s'est toujours avéré sous-optimal pour les problèmes avec lesquels je travaille. En supposant que la méthode Quasi-Newton standard échoue, je préconiserais toujours d'abord une approche sans dérivé ou une approche HMC.
usεr11852
Eh bien, si j'ai des contraintes, ce que je veux, c'est que la fonction ajustée satisfasse les contraintes. Croyez-moi, j'ai des doutes sur la façon dont un ajustement GP sera une représentation précise de ce que je veux, des contraintes ou non. De bonnes contraintes peuvent vous aider - elles contraignent les choses là où elles devraient être et vous évitent de perdre du temps dans de mauvaises régions. Bien sûr, c'est s'ils sont bien mis en œuvre. Pouvez-vous donner un exemple de résultat basé sur la continuité derrière l'optimalité GPR qui sort par la fenêtre lorsqu'il y a des contraintes linéaires? Pour être un exemple valide, il vaut mieux avoir été dans la fenêtre sans contraintes.
Mark L. Stone