Optimierung stochastischer Computermodelle

11

Dies ist ein schwieriges Thema für mich, da die Wörter Optimierung und Stochastik in einer Suche fast automatisch standardmäßig nach stochastischer Optimierung suchen. Was ich aber wirklich wissen möchte, ist, welche Methoden zur Optimierung von Computermodellen existieren, wenn die Ausgabe des Computermodells stochastisch, dh nicht deterministisch ist?

Wenn Sie beispielsweise ein Computermodell betrachten, bei dem es eine unbekannte Funktion f(x) , die die Ausgabe des Computermodells darstellt, gibt es viele statistische Methoden zur Lösung von Problemen wie

minf(x)xX

wenn deterministisch ist. Aber was passiert, wenn stochastisch ist? Gibt es eine Lösung für das Problem oder können wir sie bestenfalls nur lösen?f(x)f(x)

minE[f(x)]xX

Dabei ist der übliche Erwartungsoperator.E()

RustyStatistician
quelle
1
Dies ist eine sehr interessante Frage. Die Optimierung von ist das einzige, was wirklich möglich ist. Eine statistische Anwendung im Zusammenhang mit dieser Frage ist der MCEM-Algorithmus, bei dem die volle Wahrscheinlichkeitsfunktion nur mit einem MCMC-Fehler beobachtet werden kann. In ähnlicher Weise haben MCMC-Partikelfilteralgorithmen das gleiche Problem. Ich habe in keiner Literatur genug gelesen, um zu wissen, wie die Methoden zur Beantwortung dieser Fragen auf dem neuesten Stand der Technik sind. E[f(x)]
Cliff AB
2
Es hängt von Ihrem Ziel ab. ist nur eine von vielen möglichen Möglichkeiten. In einigen Anwendungen möchten Sie möglicherweise eine "zuverlässige" Lösung, nicht nur eine, die "im Durchschnitt gut" ist. In diesem Szenario würden Sie wrt auf ein Quantil der Verteilung von f ( x ) optimieren . Die Bayes'sche Optimierung befasst sich mit kostspieligen (und manchmal verrauschten) Funktionsbewertungen. Überprüfen Sie zum Beispiel diese Frage . E[f(x)]f(x)
Lacerbi
1
@lacerbi sind einige dieser Beispiele laut? Ich denke, sie sind nur deterministisch.
RustyStatistician
@RustyStatistician: Sie haben Recht, die meisten Beispiele sind deterministisch oder sprechen allgemein über die Bayes'sche Optimierung. Siehe unten für Referenzen, die sich mehr auf den "lauten" Teil konzentrieren.
Lacerbi
Greifen Sie auf das Computerprogramm zu, damit Sie es selbst für ausgewählte Eingaben ausführen können ? Dann stehen Methoden zur Versuchsplanung zur Verfügung! Durchsuche diese Seite. x
kjetil b halvorsen

Antworten:

10

( Erweitern Sie meinen Kommentar zu einer richtigen Antwort. )

Wie ich bereits erwähnte, hängt es von Ihrem Ziel ab.

Der erwartete Wert ist nur eine von vielen möglichen Auswahlmöglichkeiten für das Optimierungsziel. Angenommen, die f ( x ) sind normal verteilt, könnten Sie Folgendes tun:E.[f(x)]]f(x)

für einigeκR, die die Risikosensitivität manipulieren. Wennκ>0ist, suchen Sie nach einerrobustenLösung, die wahrscheinlich am besten ist und große positive Schwankungen verhindert. Umgekehrtwürdeein negativesκeine "optimistische" Optimierung bevorzugen, die nach großen negativen Schwankungen sucht (negativ ist gut, da wir minimieren). Sie könnenκbasierend auf Quantilen der Normalverteilungauswählen(siehe Referenz 2 unten).

xopt=argminx{E[f(x)]+κVar[f(x)]}
κRκ>0κκ

Im Allgemeinen befasst sich die Bayes'sche Optimierung (BO, die mit Gaußschen Prozessen und Kriging zusammenhängt ) mit kostspieligen und manchmal verrauschten Funktionsbewertungen; obwohl der größte Schwerpunkt der Literatur auf dem ersteren Teil lag. Zu dieser Frage finden Sie Bewertungen zur Bayes'schen Optimierung .

Mehrere Personen haben BO auf verrauschte Funktionen angewendet. Als Einführung in das Thema hielt David Ginsbourger auf dem Workshop über Gaußsche Prozesse zur globalen Optimierung (Sheffield, 17. September 2015) einen schönen Vortrag mit dem Titel "Variationen über die erwartete Verbesserung". Sie finden seinen Vortrag hier und alle Vorträge sind auf dieser Seite verfügbar (ich empfehle auch alle anderen Vorträge als hervorragende allgemeine Einführung in BO.)

Als Referenz würde ich mit der Arbeit von Ginsbourger und Kollegen sowie Gramacy und Kollegen beginnen:

  1. Picheny, V. und Ginsbourger, D., 2014. "Noisy Kriging-basierte Optimierungsmethoden: eine einheitliche Implementierung innerhalb des DiceOptim-Pakets". Computational Statistics & Data Analysis , 71, S. 1035–1053. ( Link )

  2. Picheny, V., Ginsbourger, D., Richet, Y. und Caplin, G., 2013. "Quantilbasierte Optimierung von verrauschten Computerexperimenten mit einstellbarer Präzision". Technometrics , 55 (1), S. 2-13. ( Link )

  3. Gramacy, RB und Lee, HK, 2012. "Bayesianische Baum-Gauß-Prozessmodelle mit einer Anwendung auf die Computermodellierung". Zeitschrift der American Statistical Association . ( Link )

  4. Gramacy, RB und Apley, DW, 2015. "Lokale Gaußsche Prozessnäherung für große Computerexperimente". Journal of Computational and Graphical Statistics , 24 (2), S. 561-578. ( Link )

Sowohl Ginsburger und Gramacy haben R - Pakete , die ihre BO Methoden implementieren bzw. DiceOptim und TGP .

Lacerbi
quelle
1
Wo steht in deiner Antwort oder meinst du κ ? kκ
RustyStatistician
1
Ein weiterer Algorithmus, den ich nicht verwendet habe *, aber in der Abteilung für amüsante Namen gewinnt, ist SNOBFIT . (* Der Autor ist jedoch in der Optimierungs-Community bemerkenswert, und die Software hat einen deterministischen Benchmark in Ordnung gebracht , sodass die Empfehlung nicht nur auf dem coolen Namen basiert!)
GeoMatt22
4

Die aktuellen Antworten konzentrieren sich auf die richtige (mathematische) Definition eines stochastischen Optimierungsziels - ich möchte eine etwas angewandtere Perspektive bieten.

Dieses Problem tritt häufig auf, wenn stochastische Modelle angepasst werden, z. B. unter Verwendung informeller oder synthetischer Wahrscheinlichkeiten. Referenz (1) bietet Ihnen eine Liste von Optionen, mit denen Sie den Abstand zwischen einem stochastischen Modell und den Daten definieren können.

Nachdem Sie Ihr Ziel auf diese Weise definiert haben, bleibt das Problem, das Optimum eines Mittelwerts eines verrauschten Ziels zu finden. Es gibt zwei Wege: a) Optimierung und b) MCMC-Abtastung. Sie haben speziell nach der Optimierung gefragt, aber ich möchte die MCMCs einbeziehen, da sie sich für diese Aufgabe oft besser verhalten.

a) Wenn Sie bei der Optimierung bleiben, müssen Sie sicherstellen, dass Sie nicht stecken bleiben und dass der Optimierer mit einem stochastischen Ziel umgehen kann. Kapitel 4 der Doktorarbeit von Matteo Fasiolo gibt einige Hinweise, siehe (2).

b) Wie wir in (1) bemerken, sind MCMCs im Allgemeinen robuster gegenüber einem stochastischen Ziel - unter milden Bedingungen hinsichtlich der Verteilung des Rauschens mittelt das MCMC das Rauschen weg und das abgetastete Ziel ist nicht von einem nicht verrauschten Ziel zu unterscheiden Ziel mit Mittelwert des verrauschten Ziels. Allerdings können auch MCMCs stecken bleiben, wenn sie auf eine besonders gute Bewertung stoßen. Was Sie jetzt NICHT tun dürfen, ist die folgende "offensichtliche" Idee: Berechnen Sie einfach sowohl den aktuellen als auch den vorgeschlagenen Wert in jeder MCMC-Iteration. Das Schlüsselwort, das hier nachgeschlagen werden muss, ist "pseudo-marginal", siehe auch hier und hier .

1) Hartig, F.; Calabrese, JM; Reineking, B.; Wiegand, T. & Huth, A. (2011) Statistische Inferenz für stochastische Simulationsmodelle - Theorie und Anwendung . Ecol. Lett., 14, 816 & ndash; 827.

2) Fasiolo, M. (2016) Statistische Methoden für die komplexe Populationsdynamik . Universität von Bath

Florian Hartig
quelle
4

Nehmen wir an, wir befinden uns in einem diskreten Wahrscheinlichkeitsraum, so dass . Intuitiv benötigen Sie eine Funktion U : R nR, damit Sie U ( f ( x ) ) optimieren können . Sie können nur ein einziges Ziel optimieren!f(x)RnU:RnRU(f(x))

Die Optimierung einer einzelnen Zielfunktion mag recht einschränkend klingen, ist es aber nicht ! Vielmehr kann ein einzelnes Ziel unglaublich unterschiedliche Präferenzen darstellen, die Sie möglicherweise gegenüber einer besseren oder schlechteren Lösung haben.

Wenn Sie weiterspringen, können Sie einfach eine Zufallsvariable auswählen und dann Folgendes lösen:λ

Dies ist eine einfache lineare Neugewichtung vonE[f(x)]. Wie auch immer, hier ist ein Argument dafür, warum es normalerweise in Ordnung ist, mehrere Ziele zu einem einzigen Ziel zusammenzufassen.

minimize (over x)E[λf(x)]subject toxX
E[f(x)]

Grundeinstellung:

  • Sie haben die Auswahl Variable und eine zulässige Menge X .xX
  • Ihre Wahl von führt zu einem zufälligen Ergebnis ˜ y = f ( x )xy~=f(x)
  • Sie haben rationale Präferenzen gegenüber dem zufälligen Ergebnis. (Grundsätzlich können Sie sagen, ob Sie ein zufälliges Ergebnis ˜ y einem anderen vorziehen .)y~

Ihr Problem ist , wählen , so dass:xX

Im Englischen möchten Sie x wählen,damit keine realisierbare Wahl x zu einem Ergebnis führt, das f ( x ) vorgezogen wird.

xXf(x)f(x)
xxf(x)

Gleichwertigkeit mit der Maximierung des Nutzens (unter bestimmten technischen Bedingungen)

Der technischen Einfachheit halber werde ich sagen, dass wir uns in einem diskreten Wahrscheinlichkeitsraum mit Ergebnissen befinden, damit ich zufällige Ergebnisse ˜ y mit einem Vektor yR n darstellen kann .ny~yRn

Unter bestimmten technischen Bedingungen (die im praktischen Sinne nicht einschränkend sind) entspricht das obige Problem der Maximierung einer Nutzfunktion . (Die Utility-Funktion weist mehr bevorzugten Ergebnissen eine höhere Zahl zu.)U(y)

Diese Logik würde für jedes Problem gelten, bei dem Ihre Auswahl zu mehreren Ergebnisvariablen führt.

maximize (over x)U(f(x))subject toxX

U

U

U(y)=E[u(yi)]=ipiu(yi)
piiuuU

maximize (over x)ipiu(yi)subject toxXy=f(x)

u(yi)=yi

λ

maximize (over x)iλiyisubject toxXy=f(x)

λipi

λU(f(x))

Matthew Gunn
quelle
Aber in diesem Setup führen nicht alle Dienstprogrammfunktionen zur gleichen Antwort richtig?
RustyStatistician
Und gibt es typische Optionen für Dienstprogrammfunktionen? Mein Problem ist ein stochastischer Computersimulator, der eigentlich ein Blackbox-Simulator ist. Ich kenne also keine Informationen über die zugrunde liegende Mechanik. Kann ich ihm möglicherweise sogar eine Dienstprogrammfunktion zuweisen?
RustyStatistician
Sie müssen die Logik Ihres Problems durchdenken, was ein gutes Ergebnis ausmacht, und dann eine objektive Funktion finden, die besseren Ergebnissen eine höhere Zahl zuweist. (Oder äquivalent dazu können Sie dies als Minimierungsproblem einrichten und schlechteren Ergebnissen eine höhere Zahl zuweisen, z. B. eine Vorstellung von quadratischem Fehler usw. minimieren.)
Matthew Gunn