Details zur praktischen Implementierung der Bayes'schen Optimierung

8

Ich probiere Bayesian Optimization aus und folge Snoek, Larochelle und Adams [ http://arxiv.org/pdf/1206.2944.pdf] mit GPML [ http://www.gaussianprocess.org/gpml/code/matlab / doc /] . Ich habe die auf Seite 3 beschriebene Erfassungsfunktion für erwartete Verbesserungen implementiert und gehe davon aus, dass ich richtig bin. Um zu entscheiden, wo ich mein Ziel als nächstes abfragen soll, sollte ich das , das maximiert:x

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

Aber ich kann anscheinend keine Anleitung finden, welche Gruppe von Kandidaten zu berücksichtigen ist. Theoretisch möchte ich das beste x über die gesamte Domäne finden, und das Papier ist so geschrieben, dass dies möglich erscheint ("[EI] hat auch nach dem Gaußschen Prozess eine geschlossene Form"). In der Praxis muss ich jedoch die posterioren Vorhersagemittel und Varianzen für jedes x berechnen, das ich in Betracht ziehen könnte, bevor ich ein E I ( x ) berechnen kann, und obwohl diese Posterioren eine geschlossene Form haben, muss ich sie dennoch mit berechnen Matrixalgebra, daher sehe ich keinen Weg, um ein paar x zu finden.xxxaEI(x)x

Die Frage: Was ist eine praktische Methode zur Auswahl des großen (mittleren? Kleinen?) Satzes von Kandidaten , über den ich den EI (oder eine andere Erfassungsfunktion) maximiere? (Ist das irgendwo in der Zeitung und ich habe es einfach verpasst?)x

Im Moment nehme ich nur meinen aktuellen Satz , probiere ihn 2000 Mal durch Ersetzen aus und füge dann jedem Punkt etwas Gaußsches Rauschen hinzu. Scheint in Ordnung zu sein, denke ich.xi

stackoverflax
quelle
Ich habe dieses Papier noch nicht gelesen, aber haben Sie darüber nachgedacht, mit einem lateinischen Hypercube-Design eine Stichprobe aus dem interessierenden Bereich zu erstellen? en.wikipedia.org/wiki/Latin_hypercube_sampling
RustyStatistician
Eine Alternative wäre, die Domain zu gittern (falls möglich) und dann jeden Punkt auf dieser gerasterten Domain zu bewerten.
RustyStatistician
Dies sind beide vernünftige Vorschläge, danke! Ich weiß nicht viel über lateinische Hyperwürfel, aber reguläre Gitterdomänen würden bedeuten, dass Toeplitz- und Kronecker-Algebra verwendet werden könnte, was die Dinge selbst mit einem sehr großen Gitter schön und effizient machen würde.
Stackoverflax

Antworten:

6

Normalerweise verwenden Sie einen beliebigen globalen Optimierer. Das Problem ist, dass die EI-Oberfläche stark multimodal und nicht verbunden ist. Die Optimierung dieser Erfassungsfunktion ist an sich kein triviales Problem.

Eine häufige Wahl, die ich in verschiedenen Veröffentlichungen gesehen habe, ist der DIRECT- Algorithmus. Manchmal habe ich CMA-ES gesehen , eine Methode auf dem neuesten Stand der nichtlinearen Optimierung. Nach meiner Erfahrung für andere Formen der Optimierung funktioniert MCS ( Multi-Level Coordinate Search ) in der Regel relativ gut. Eine Übersicht über derivatfreie globale Optimierer finden Sie hier :

  • Rios und Sahinidis, "Derivatfreie Optimierung: eine Überprüfung der Algorithmen und ein Vergleich der Software-Implementierungen", Journal of Global Optimization (2013).

Übrigens ist die EI analytisch. Wenn Sie möchten, können Sie auch den Gradienten berechnen, um die Optimierung zu steuern. Dies ist jedoch nicht erforderlich. Eine effektive Technik ist es, einen globalen Optimierer lief ersten vielversprechende Lösungen zu finden und dann einen lokalen Optimierer führen Sie es zu verfeinern (zB ein Quasi-Newton - Verfahren wie BFGS, das ist fminunc in MATLAB oder fmincon wenn Sie Einschränkungen haben).

Wenn schließlich die Geschwindigkeit der Optimierung der Erfassungsfunktion ein Faktor ist (was nicht das "traditionelle" BO-Szenario ist), habe ich anständige Ergebnisse gefunden, indem ich mit einem lateinischen Hypercube-Design oder einem quasi zufälligen Sobol-Sequenzdesign begonnen und dann mit verfeinert habe ein paar Schritte eines lokalen Optimierers von den besten Punkten; Siehe auch @ user777 Kommentar. Da dies nicht das Standard-BO-Szenario ist, habe ich keine spezifische Referenz, die diese Methode tatsächlich verwendet.


Beispiele für Artikel, die sich auf DIRECT oder CMA-ES beziehen:

  • R. Calandra, A. Seyfarth, J. Peters & MP Deisenroth (2015). Bayesianische Optimierung zum Lernen von Gängen unter Unsicherheit. Annalen der Mathematik und künstlichen Intelligenz, 1-19 ( Link ).
  • N. Mahendran, Z. Wang, F. Hamze & ND Freitas (2012). Adaptives MCMC mit Bayes'scher Optimierung. In der Internationalen Konferenz über künstliche Intelligenz und Statistik (S. 751-760) ( Link ).
  • T. Gunter, MA Osborne, R. Garnett, P. Hennig & SJ Roberts (2014). Inferenzstichprobe in probabilistischen Modellen mit schneller Bayes'scher Quadratur. In Fortschritte in neuronalen Informationsverarbeitungssystemen (S. 2789-2797) ( Link ).

Sie können einfach "Bayesianische Optimierung" + den gewünschten globalen Optimierungsalgorithmus googeln und finden eine Reihe von Artikeln. Außerdem finden Sie in so ziemlich jedem anderen Artikel über BO einen Satz wie :

[...] BO benötigt normalerweise in jeder Iteration einen zusätzlichen globalen Optimierer, um die Erfassungsfunktion zu optimieren. In der BO-Literatur ist es üblich, DIvided RECTangles (DIRECT) zu verwenden, um eine solche Aufgabe zu erfüllen. Andere globale Optimierungsalgorithmen wie CMA-ES könnten ebenfalls angewendet werden.

Lacerbi
quelle
Das ist eigentlich etwas überraschend für mich! Können Sie mich auf ein repräsentatives Bayes'sches Optimierungspapier verweisen, das DIRECT oder CMA-ES verwendet? Vielen Dank.
Stackoverflax
Warum ist es überraschend? Dies ist die Norm - in so ziemlich jedem BO-Artikel finden Sie Verweise auf DIRECT oder andere globale Optimierer. Es ist wahrscheinlich in der Community so bekannt, dass einige Artikel es nicht einmal erwähnen - es ist nur eine Selbstverständlichkeit. Ich habe in meinem Hauptkommentar oben einige Referenzen hinzugefügt.
Lacerbi
Dies ist nicht unbedingt eine gute Lösung, aber ich habe festgestellt, dass es billiger sein kann, die EI nur an einer Reihe von Punkten zu bewerten, die mit Latin Hypercubes abgetastet wurden, wenn Sie nur in der Nähe des Minimums sein müssen, aber nicht unbedingt darüber.
Sycorax sagt Reinstate Monica
@ user777: Ja, wenn es um Geschwindigkeit geht, habe ich sowohl LH- als auch Sobol-Quasi-Zufallssequenzen als anfängliches Design verwendet ( bei letzterem einen kleinen Vorteil gefunden, aber möglicherweise problemabhängig) und dann einen lokalen Optimierer ausgeführt wie BFGS von den besten Punkten. Ich werde dies dem Hauptkommentar hinzufügen.
Lacerbi
Eine Möglichkeit, die Ad-hoc-Natur des LHS-Ansatzes zu rechtfertigen, besteht darin, dass das Finden des Minimums einer stochastischen Funktion (Oberfläche) nicht erforderlich ist, da der Fehler bei der Schätzung des Minimums die Genauigkeitsgewinne von Minuten überschwemmt. Dies ist jedoch eine sehr gute Antwort. Ich bin froh, dass sich hier jemand anderes um BO kümmert. :-)
Sycorax sagt Reinstate Monica