Maximierung unbekannter Rauschfunktionen

Ich bin daran interessiert, eine Funktion maximieren , wobei . $f(\mathbf \theta)$ $\theta \in \mathbb R^p$

Das Problem ist, dass ich die analytische Form der Funktion oder ihrer Ableitungen nicht kenne. Das einzige , was ich tun kann , ist die Funktion punktweise zu bewerten, indem sie in einem Wert Aufstecken und eine verrauschten Schätzung erhalten an diesem Punkt. Wenn ich möchte, kann ich die Variabilität dieser Schätzungen verringern, muss aber steigende Rechenkosten zahlen. $\theta_*$ $\hat{f}(\theta_*)$

Folgendes habe ich bisher versucht:

Stochastisch steilster Abstieg mit endlichen Unterschieden: Es kann funktionieren, erfordert jedoch viel Abstimmung (z. B. Verstärkungssequenz, Skalierungsfaktor) und ist oft sehr instabil.
Simuliertes Tempern: Es funktioniert und es ist zuverlässig, aber es erfordert viele Funktionsbewertungen, so dass ich es ziemlich langsam fand.

Daher bitte ich um Vorschläge / Ideen zu möglichen alternativen Optimierungsmethoden, die unter diesen Bedingungen funktionieren können. Ich halte das Problem so allgemein wie möglich, um Vorschläge aus anderen Forschungsbereichen als meinen anzuregen. Ich muss hinzufügen, dass ich sehr an einer Methode interessiert wäre, die mir eine Schätzung des Hessischen bei der Konvergenz geben könnte. Dies liegt daran, dass ich damit die Unsicherheit der Parameter abschätzen kann . Andernfalls muss ich endliche Differenzen um das Maximum verwenden, um eine Schätzung zu erhalten. $\theta$

optimization monte-carlo simulation Jugurtha
quelle

Wenn Sie nichts Spezifischeres über das Rauschen sagen können, das mit der Ausgabe Ihrer Funktion verbunden ist, bin ich mir nicht sicher, ob etwas Anspruchsvolleres als simuliertes Tempern (Sie müssen dies bis zu einem gewissen Grad sogar abstimmen) hilfreich sein wird.

Aron Ahmadia

θ

$\theta$

\hat{f} (θ_{*}) \sim N (f (θ_{*}), σ)

$\hat{f}(\theta_*) \sim N(f(\theta_*),\sigma)$

Sieht so aus, als würde ich von Prof. Neumaier korrigiert :)

Aron Ahmadia

Physiker hier habe ich CMA-ES für die optische Phasenformung (Optimierung der Phase eines Laserpulses über einen Pulsformer) verwendet, was ziemlich verrauscht ist.

Tillsten

Antworten:

Genau dafür wurde unser Matlab-Paket SnobFit entwickelt. Es ist keine Annahme über die Verteilung des Rauschens erforderlich. Darüber hinaus können Funktionswerte über Textdateien bereitgestellt werden, sodass Sie sie auf Funktionen anwenden können, die in jedem System implementiert sind, das eine Textdatei schreiben kann. Siehe
http://www.mat.univie.ac.at/~neum/software/snobfit/

SnobFit wurde für eine Anwendung entwickelt, bei der die zu optimierende Funktion nicht einmal existierte und Funktionswerte (ein Maß für die Herstellungsqualität) von speziellen, teuren Geräten erhalten wurden, die Musterprodukte herstellten und diese von Hand maßen, was zu etwa 50 Funktionen führte Bewertungen pro Tag.

Arnold Neumaier
quelle

Ich danke Ihnen sehr für Ihre Antwort. Ich habe angefangen, Ihren Artikel über das SnobFit-Paket zu lesen, und finde ihn wirklich interessant. Als ich die Einleitung zu Ihrem Artikel las, stellte ich fest, dass das Problem, mit dem ich mich befasse (in einem statistischen Kontext), in der industriellen Mathematik ziemlich häufig ist. Es gibt eine umfangreiche Literatur, von der ich nichts wusste. Tatsächlich ähnelt der Ansatz, an dem ich gearbeitet habe, der quadratischen Approximation von Powell (2002).

Jugurtha

Funktioniert Snobfit gut mit 128 Freiheitsgraden? Nur um zu wissen, dass es sich lohnt, es für meinen Fall auszuprobieren.

Tillsten

@tillsten: Keine Methode für verrauschte Probleme funktioniert gut mit 128 dof, es sei denn, Sie können eine große Anzahl von Funktionswerten ausgeben. Sie können jedoch unseren VXQR1 ausprobieren, der nicht für laute Probleme geeignet ist, aber manchmal für laute Probleme gut geeignet ist.

Arnold Neumaier

Das Limit für Snobfit liegt bei ca. 20 Variablen. Wenn Sie mehr haben, müssen Sie nach dem gesunden Menschenverstand Gruppen von 20 Variablen auswählen, die Sie teilweise nacheinander optimieren. Sie können auch einige Variablen gleichzeitig verschieben, um die Bemaßung zu verringern.

Arnold Neumaier

Es gibt verschiedene Bayes'sche Optimierungstechniken , die Sie ausprobieren können. Die einfachsten basieren auf dem Gaußschen Prozess:

Harold J. Kushner. Eine neue Methode zum Lokalisieren des Maximums einer beliebigen Multipeak-Kurve bei Vorhandensein von Rauschen. Journal of Basic Engineering, Seiten 86: 97–106, März 1964.
J. Mockus. Der Bayes'sche Ansatz zur globalen Optimierung. Lecture Notes in Control and Information Sciences, 38: 473–481, 1982.
Niranjan Srinivas, Andreas Krause, Sham Kakade und Matthias Seeger. Gaußsche Prozessoptimierung in der Banditeneinstellung: Kein Bedauern und experimentelles Design. In Proc. Internationale Konferenz über maschinelles Lernen (ICML), 2010.
Andreas Krause, Ajit Singh und Carlos Guestrin. Nahezu optimale Sensorplatzierungen in Gaußschen Prozessen: Theorie, effiziente Algorithmen und empirische Studien. J. Mach. Lernen. Res., 9: 235–284, Juni 2008.

Sie arbeiten, indem sie einen posterioren über plausiblen Funktionen bilden, die bisher Beobachtungen geben und den nächsten Punkt vorschlagen, um die Funktion schnell zu lernen und die globalen Maxima zu finden (siehe meinen Blog-Beitrag ).

Ein weiterer Vorteil ist, dass Sie den Hessischen an den Maxima schätzen können. Sie müssen jedoch ein Rauschmodell angeben.

Memming
quelle

Der SPSA-Algorithmus von James Spall (kurz für Stochastic Perturbation Simulated Annealing, wenn ich mich richtig erinnere) wurde für genau diese Art von Problem entwickelt. Er hat ein paar Papiere, in denen er sie für Probleme wie das von Ihnen beschriebene verwendet.

Wolfgang Bangerth
quelle

Ich habe Spalls Ansatz ausprobiert, der auf einer stochastischen Version des steilsten Abstiegs und Raphson Newton basiert. Ich habe Simulated Annealing ausprobiert, aber nicht die von Spall vorgeschlagene Version, ich sollte es versuchen. Ich bin nicht wirklich begeistert von simuliertem Tempern, weil ich bei Konvergenz keine Schätzung des Hessischen erhalten kann (während ich zum Beispiel mit dem stochastischen Raphson Newton "kostenlos" eine Annäherung an das Hessische erhalten kann).

Jugurtha