Es hört sich so an, als wären Sie daran interessiert, stochastische Optimierungsmethoden zu studieren . Wenn Sie die Optimierung als eine Art Stichprobenproblem neu gestalten, erhalten Sie eine stochastische Optimierungsmethode, und diese letztere Methode ist nur dann von Vorteil, wenn sie gegenüber analogen deterministischen Optimierungsmethoden eine gewisse Verbesserung bietet .
Im Allgemeinen umfassen stochastische Optimierungsmethoden dieser Art die Erzeugung von Zufallswerten in einer Weise, die von der zu optimierenden Funktion abhängt, und daher ist sie wahrscheinlich mindestens genauso rechenintensiv (und wahrscheinlich rechenintensiver) als entsprechende deterministische Methoden . Stochastische Methoden sind im Allgemeinen auch komplizierter zu verstehen. Der einzige Vorteil, der sich wahrscheinlich aus (gut konstruierten) stochastischen Optimierungsmethoden ergibt, besteht darin, dass sie im Allgemeinen eine Wahrscheinlichkeit ungleich Null beibehalten, Bereiche der Domäne zu "durchsuchen", die von deterministischen Methoden möglicherweise übersehen werden, und das sind sie auch wohl robuster, wenn Sie bereit sind, sie für eine lange Zeit laufen zu lassen.
Die meisten standardmäßigen deterministischen Optimierungsmethoden umfassen iterative Schritte in Richtung der Optima durch Auswahl einer deterministischen Bewegungsrichtung und Bewegung in diese Richtung um einen bestimmten deterministischen Betrag (z. B. bewegen wir uns bei steilstem Aufstieg in Richtung des Gradientenvektors). Die Richtung und Länge der Schritte wird normalerweise durch Betrachten des Gradienten der Funktion bestimmt, der in der Praxis berechnet wird, indem die Steigung über ein kleines Bewegungsinkrement betrachtet wird. Indem Sie die Optimierung in ein Stichprobenproblem verwandeln, bewegen Sie sich effektiv nur um einen zufälligen Betrag in eine zufällige Richtung. Sie möchten jedoch weiterhin Informationen über die Steigung der Funktion verwenden, um das stochastische Verhalten dieser Bewegung zu bestimmen. Es ist wahrscheinlich, dass die letztere Methode die gleichen Informationen wie die erstere verwendet, nur in einer komplexeren (und damit komplexeren) Methode rechenintensiver) Weg. Im Folgenden werde ich anhand Ihrer Beschreibung eine Methode unter Verwendung des MH-Algorithmus erstellen.
Implementierung mit dem Metropolis-Hastings-Algorithmus: Angenommen, Sie haben es mit einem Maximierungsproblem bei einer Verteilung über eine Dimension zu tun und betrachten die Methode der Metropolis-Hasting-Abtastung unter Verwendung von Gaußschen Abweichungen. Dies ist eine bekannte Methode zur Probenahme, die durch die Probenahmedichte sehr robust gegen unangenehmes Verhalten ist.
Um den Algorithmus zu implementieren, generieren wir eine Sequenz ε1,ε2,ε3, . . . ∼ IID N ( 0 , 1 ) von zufälligen Abweichungen, die wir später mit dem Parameter "Bandbreite" multiplizieren werden λ > 0(Dieser Parameter repräsentiert also die Standardabweichung unserer vorgeschlagenen Schritte). Wir generieren auch eine SequenzU.1,U.2,U.3, . . . ∼ U ( 0 , 1 )von einheitlichen Zufallsvariablen. Wir wählen einen Startwertx0 willkürlich und erzeugen die Folge von Abtastwerten rekursiv als:
xt + 1=⎧⎩⎨xt+ λεt + 1xtwenn U.t + 1⩽ exp( k ( f(xt+ λεt + 1) - f(xt) ) ) ,sonst .
Der MH-Algorithmus hat eine stationäre Verteilung, die gleich der Zieldichte ist, also haben wir die ungefähre Verteilung für großes . Ein großer Wert für (relativ zum Bandbreitenparameter) wird verwendet bedeuten, dass Abweichungen in Richtung der Optima mit hoher Wahrscheinlichkeit akzeptiert werden und Abweichungen von den Optima (oder das Überschreiten der Optima) mit hoher Wahrscheinlichkeit zurückgewiesen werden. In der Praxis sollten die Stichprobenwerte daher in der Nähe des Maximierungspunkts konvergieren der Dichte . (Es würde immer noch Fälle geben, in denen dies nicht auftreten würde; z. B. wenn die Dichte bimodal ist und der Algorithmus die falsche Steigung erklimmt.) Wenn wir einen großen Wert von dann die VerteilungX.n∼ exp( k ( f( x ) )nkfkexp(k(f(x)) ist nahe dem Maximierungswert hoch konzentriert, daher sollte in diesem Fall der Stichprobenmittelwert der Stichprobenwerte (Verwerfen einiger Einbrennwerte) eine gute Schätzung des Maximierungswerts bei der Optimierung liefern .
Nehmen wir nun an, wir wirken dem großen Wert von indem wir die Bandbreite auf klein einstellen . In diesem Fall erhalten wir kleine Werte für die Abweichungen, sodass wir die ungefähren Akzeptanzwahrscheinlichkeiten haben:kλ
exp(k(f(xt+λεt+1)−f(xt)))≈exp(kλ⋅εt+1⋅f′(xt)).
Wir können sehen, dass in diesem Fall die Akzeptanzwahrscheinlichkeit durch die Ableitung der Dichte, der Größe und Richtung der Abweichung und des Wertes .εt+1kλ
Funktioniert dieser Algorithmus tatsächlich besser als anwendbare deterministische Optimierungsalgorithmen? Nun, wir können sehen, dass der Algorithmus erfordert, dass wir die Dichte bei jedem möglichen Schritt berechnen, und wenn der Bandbreitenparameter klein ist, ist dies gleichbedeutend mit der Berechnung der Ableitung der Funktion. Dies ist also einer Form des stochastischen Gradientenaufstiegs ziemlich ähnlich, mit mehr Rechenarbeit als die entsprechende deterministische Methode. Der Vorteil, falls vorhanden, besteht darin, dass die vorgeschlagenen Abweichungen zufällig sind und alle mit einer Wahrscheinlichkeit ungleich Null auftreten (wenn auch sehr schnell verschwinden), so dass der Algorithmus das Potenzial hat, Regionen mit hoher, aber nicht maximierender Dichte zu "entkommen" .