Was ist der Unterschied zwischen der Bayes'schen Optimierung (Gauß'sche Prozesse) und dem simulierten Tempern in der Praxis?

8

Beide Prozesse scheinen verwendet zu werden, um den Maximalwert einer unbekannten Funktion zu schätzen, und beide haben offensichtlich unterschiedliche Möglichkeiten, dies zu tun.

Aber in der Praxis ist eine der beiden Methoden im Wesentlichen austauschbar? Wo würde ich eins über das andere verwenden wollen?

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

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

Ähnliche Frage
Bayes'sche Optimierung oder Gradientenabstieg?

canyon289
quelle
Ich denke nicht, dass dies erschöpfend genug ist, um eine Antwort zu sein, aber simuliertes Tempern erfordert im Allgemeinen eine größere Anzahl von Funktionsbewertungen, um einen Punkt nahe dem globalen Optimum zu finden. Andererseits erstellt die Bayes'sche Optimierung bei jeder Iteration ein Modell, erfordert jedoch relativ wenige Funktionsbewertungen. Abhängig davon, wie teuer die Bewertung der Funktion ist, würden Sie eine der anderen vorziehen, da eine Wandzeit kürzer ist: Bayes'sche Optimierung in Fällen, in denen die Funktion sehr teuer ist, und Tempern, wenn die Funktion relativ billig ist.
Sycorax sagt Reinstate Monica
@Sycorax 10 Posts zu mehr oder weniger demselben Thema in 10 Minuten - ein bisschen übertrieben, findest du nicht? Anscheinend nicht, aber ich tue es.
Mark L. Stone
@ MarkL.Stone Es ist mehr oder weniger "langsame Zeit" (20 Uhr an einem Freitag, zum Zeitpunkt der Bearbeitung), die bevorzugte Zeit, um dies zu tun. Es gibt einen Meta-Thread.
Sycorax sagt Reinstate Monica

Antworten:

8

Simulated Annealing (SA) ist ein sehr einfacher Algorithmus im Vergleich zur Bayesian Optimization (BO). Keine der beiden Methoden geht von einer Konvexität der Kostenfunktion aus, und keine der beiden Methoden stützt sich stark auf Gradienteninformationen.

SA ist in gewisser Weise ein leicht gebildeter Zufallsspaziergang. Die Kandidatenlösung springt mit einem bestimmten Sprungplan (dem Kühlparameter) über den Lösungsraum. Es ist dir egal, wo du vorher gelandet bist, du weißt nicht, wo du als nächstes landen wirst. Dies ist ein typischer Markov-Kettenansatz. Sie modellieren keine starken Annahmen über die Oberfläche der darunter liegenden Lösung. Die MCMC-Optimierung hat einen langen Weg von SA zurückgelegt (siehe zum Beispiel Hamiltonian Monte Carlo ), aber wir werden nicht weiter expandieren. Eines der Hauptprobleme bei SA ist, dass Sie häufig "schnell" bewerten müssen. Und es ist sinnvoll, dass Sie so viele Beispiele wie möglich benötigen, um so viele Zustände (dh Kandidatenlösungen) wie möglich zu untersuchen. Sie verwenden nur ein kleines Stück Gradienteninformationen (die Sie fast immer als "bessere" Lösungen akzeptieren).

Schau dir jetzt BO an. Die BO-Regression (oder einfach die Gaußsche Prozess-Regression (GP) über Ihre Kostenfunktionsbewertungen) versucht genau das Gegenteil in Bezug auf die Funktionsbewertung zu tun. Es wird versucht, die Anzahl der von Ihnen durchgeführten Bewertungen zu minimieren. Es erstellt ein bestimmtes nicht parametrisches Modell (normalerweise ein GP) für Ihre Kostenfunktion, das häufig Rauschen voraussetzt. Es werden überhaupt keine Gradienteninformationen verwendet. Mit BO können Sie mit einer kleinen Anzahl von Funktionsbewertungen ein informatives Modell Ihrer Kostenfunktion erstellen. Anschließend "fragen" Sie diese angepasste Funktion nach ihren Extrema ab. Wieder steckt der Teufel im Detail; Sie müssen intelligent probieren (und davon ausgehen, dass Ihr Prior auch halbwegs vernünftig ist). Es wird daran gearbeitet, wo Sie Ihre Funktion als nächstes bewerten können, insbesondere wenn Sie wissen, dass sich Ihre Funktion im Laufe der Zeit tatsächlich geringfügig weiterentwickelt (z. B. hier ).

Ein offensichtlicher Vorteil von SA gegenüber BO besteht darin, dass es innerhalb von SA sehr einfach ist, Ihren Lösungsraum einzuschränken. Wenn Sie beispielsweise nicht negative Lösungen wünschen, beschränken Sie Ihre Stichprobenverteilung einfach auf nicht negative Lösungen. Dasselbe ist in BO nicht so direkt, da Sie selbst dann, wenn Sie Ihre Funktionen anhand Ihrer Einschränkungen (z. B. Nicht-Negativität) bewerten, Ihren Prozess tatsächlich einschränken müssen. Diese Aufgabe ist zwar nicht unmöglich, aber mehr involviert.

Im Allgemeinen würde man SA in Fällen bevorzugen, in denen die Kostenfunktion billig zu bewerten ist, und BO in Fällen, in denen die Kostenfunktion teuer zu bewerten ist. Ich denke, SA gerät langsam aber stetig in Ungnade; Insbesondere die Arbeit der gradientenfreien Optimierung (z. B. NEWQUA , BOBYQA ) nimmt einen ihrer Hauptvorteile im Vergleich zu den Standardmethoden für den Gradientenabstieg weg, bei denen keine Ableitung bewertet werden muss. In ähnlicher Weise macht die Arbeit an adaptiven MCMC (z. B. siehe Referenz oben) sie in Bezug auf die MCMC-Optimierung in fast allen Fällen verschwenderisch.

usεr11852
quelle
Danke für die Antwort. Ich sehe, dass Sie wahrscheinlich Recht haben, wenn es darum geht, in Ungnade zu fallen. scipy hat es zugunsten von basinhopping docs.scipy.org/doc/scipy-0.15.1/reference/generated/…
canyon289
Ich bin froh, dass ich helfen konnte. Danke für den Tipp; Diese Änderung in SciPy war mir nicht bekannt.
usεr11852
Was ist die große Sache bei der Einschränkung einer GP-Anpassung, es sei denn, die Einschränkungen sind wirklich knorrig? Wenn Sie die angepasste Funktion "abfragen", führen Sie natürlich eine eingeschränkte Optimierung durch. Ich versuche nicht sarkastisch zu sein, ich möchte wirklich wissen, welche Schwierigkeiten Sie sehen. Zum Beispiel sollten lineare Gleichheits- und Ungleichheitsbeschränkungen ein Kinderspiel sein. Wenn Sie nicht konvexe Einschränkungen haben, wie z. B. nichtlineare Gleichheitsbeschränkungen oder ganzzahlige Einschränkungen, fallen diese möglicherweise in meine knorrige Kategorie.
Mark L. Stone
@ MarkL.Stone: Selbst lineare Einschränkungen (geschweige denn die knorrigen ) können die Anpassung in höheren Dimensionen stark beeinflussen - selbst wenn Sie " etwas " anpassen, würde ich ernsthaft bezweifeln, dass diese Anpassung eine genaue Darstellung dessen ist, was Sie wollen. Darüber hinaus gehen die meisten auf Kontinuität basierenden Ergebnisse hinter der GPR-Optimalität aus dem Fenster ... Nur um klar zu sein: Ich habe BO nicht ausgiebig verwendet, da es sich für die Probleme, mit denen ich arbeite, immer als suboptimal erwiesen hat. Unter der Annahme, dass die Standard-Quasi-Newton-Methode fehlschlägt, würde ich immer zuerst einen derivatfreien oder einen HMC-Ansatz befürworten.
usεr11852
Nun, wenn ich Einschränkungen habe, möchte ich, dass die angepasste Funktion die Einschränkungen erfüllt. Glauben Sie mir, ich habe meine Zweifel, wie gut eine GP-Passform eine genaue Darstellung dessen ist, was ich will, Einschränkungen oder nicht. Gute Einschränkungen können Ihnen helfen - sie beschränken die Dinge auf den Ort, an dem sie sein sollten, und ersparen Ihnen Zeitverschwendung in schlechten Regionen. Das ist natürlich, wenn sie gut umgesetzt sind. Können Sie ein Beispiel für ein auf Kontinuität basierendes Ergebnis hinter der GPR-Optimalität geben, das bei linearen Einschränkungen aus dem Fenster geht? Um ein gültiges Beispiel zu sein, war es besser, ohne Einschränkungen im Fenster zu sein.
Mark L. Stone