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
Question similaire
Optimisation bayésienne ou descente de gradient?
optimization
maximum
bayesian-optimization
canyon289
la source
la source
Réponses:
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.
la source