Sind Optimierungstechniken Stichprobenverfahren zugeordnet?

18

Aus jedem generischen Abtastalgorithmus kann ein Optimierungsalgorithmus abgeleitet werden.

In der Tat genügt es, um eine beliebige Funktion zu maximieren , Abtastwerte aus g ∼ e f / T zu ziehen . Für klein genug ist, fallen diese Abtastwerte in die Nähe des globalen Maximums (oder der lokalen Maxima in der Praxis) der Funktion .f:x→f(x)G∼ef/TfTf

Mit "Abtastung" meine ich, eine Pseudozufallsstichprobe aus einer Verteilung zu ziehen, wenn eine logarithmische Wahrscheinlichkeitsfunktion gegeben ist, die bis zu einer Konstanten bekannt ist. Zum Beispiel MCMC-Abtastung, Gibbs-Abtastung, Strahlabtastung usw. Mit "Optimierung" meine ich den Versuch, Parameter zu finden, die den Wert einer gegebenen Funktion maximieren.

Ist das umgekehrt möglich? Können wir bei einer gegebenen Heuristik, um das Maximum einer Funktion oder eines kombinatorischen Ausdrucks zu finden, ein effizientes Stichprobenverfahren extrahieren?

Die HMC scheint beispielsweise die Gradienteninformationen zu nutzen. Können wir ein Stichprobenverfahren konstruieren, das eine BFGS-ähnliche Approximation des Hessischen nutzt? (edit: anscheinend ja: http://papers.nips.cc/paper/4464-quasi-newton-methods-for-markov-chain-monte-carlo.pdf ) Wir können MCTS bei kombinatorischen Problemen verwenden, können wir das übersetzen? in ein Stichprobenverfahren?

Kontext: Eine Schwierigkeit bei der Stichprobe besteht häufig darin, dass der größte Teil der Masse der Wahrscheinlichkeitsverteilung in einem sehr kleinen Bereich liegt. Es gibt interessante Techniken, um solche Regionen zu finden, aber sie lassen sich nicht direkt in unvoreingenommene Stichprobenverfahren übersetzen.

Bearbeiten: Ich habe jetzt das anhaltende Gefühl, dass die Antwort auf diese Frage in etwa der Gleichheit der Komplexitätsklassen #P und NP entspricht, was die Antwort wahrscheinlich zu einem "Nein" macht. Es erklärt, warum jede Abtasttechnik eine Optimierungstechnik ergibt, aber nicht umgekehrt.

sampling optimization Arthur B.
quelle
Obwohl ich denke, dass ich die meisten Wörter in dieser Frage konventionell verstehe, bin ich mir nicht sicher, worauf es ankommt. Könnten Sie etwas genauer sagen, was Sie unter "Sampling" verstehen und was genau "optimiert" wäre? Sie scheinen implizit anzunehmen, dass Ihre Leser eine bestimmte Umgebung im Auge haben, in der eine "Distribution" (oder eine Familie davon?) Involviert ist und in der ein bestimmtes Ziel angenommen wird, aber man kann nur raten, was Sie wirklich beabsichtigen, wenn Sie machen solche allgemeinen Aussagen wie die im letzten Absatz.
Whuber
Mit "Abtastung" meine ich, eine Pseudozufallsstichprobe aus einer Verteilung zu ziehen, wenn eine logarithmische Wahrscheinlichkeitsfunktion gegeben ist, die bis zu einer Konstanten bekannt ist. Zum Beispiel MCMC-Abtastung, Gibbs-Abtastung, Strahlabtastung usw. Mit "Optimierung" meine ich den Versuch, Parameter zu finden, die den Wert einer gegebenen Funktion maximieren. Beispielsweise sind Gradientenabstieg, der Simplex-Algorithmus und simuliertes Tempern Optimierungstechniken.
Arthur B.
Es gibt eine natürliche Zuordnung zwischen simuliertem Tempern und MCMC-Probenahme. Es gibt eine weniger direkte Zuordnung zwischen HMC und Gefälle (wenn Sie blinzeln). Meine Frage ist, ob dies systematischer gestaltet werden kann. Eine Schwierigkeit bei der Abtastung besteht häufig darin, dass der größte Teil der Masse der Wahrscheinlichkeitsverteilung in einem sehr kleinen Bereich liegt. Es gibt interessante Techniken, um diese Region zu finden, aber sie lassen sich nicht direkt in unvoreingenommene Stichprobenverfahren übersetzen.
Arthur B.
Bitte bearbeiten Sie Ihre Frage, um diese Klarstellungen aufzunehmen. Dies ist von entscheidender Bedeutung, da sich Ihre (etwas spezialisierte) Verwendung des Wortes "Sampling" von dem unterscheidet, was viele Leser vielleicht verstehen, obwohl dies in Ihrem Kontext angemessen ist. Auch wenn Ihre Erklärung von "Optimierung" richtig ist, scheint sie nicht hilfreich zu sein, um ihre Bedeutung hier hinreichend genau zu machen: Die Charakterisierung der "gegebenen Funktion" und ihre mögliche Beziehung zu "Abtastung" wäre eine sinnvolle Ergänzung.
whuber
Ist es jetzt besser?
Arthur B.

Antworten:

0

Eine Möglichkeit besteht darin, die CDF der Heuristik zu finden. Dann von Monte - Carlo - Theorie wissen wir , dass für , dass F - 1 ( U ) ~ FU∼unichf[0,1]F-1(U)∼F wobei F die CDF der Verteilung Du nach. Wenn Sie die PDF-Datei nicht genau finden können, können Sie eine einfache Heuristik verwenden, die auf Akzeptanz und Ablehnung basiert.

Sid
quelle