Wie wird der Gradientenabstiegsalgorithmus ausgeführt, wenn der Parameterraum beschränkt ist?

Question

Ich möchte maximieren eine Funktion mit einem Parameter.

Also ich Gradientenabstieg (oder, tatsächlich Aufstieg): Ich beginne mit einem Anfangsparameter und fügen Sie den Gradienten (mal ein Lernfaktor, der immer kleiner wird), neu bewerten den Gradienten mit dem neuen Parameter, und so weiter bis zur Konvergenz.

Aber es gibt ein Problem: Mein Parameter muss positiv bleiben, so dass es nicht < = 0 werden soll, weil meine Funktion nicht definiert ist. Meine Farbverlaufssuche wird jedoch manchmal in solche Regionen gehen (wenn es positiv war, sagte der Gradient, dass es etwas niedriger geht und es überschwingt).

Und um die Sache noch schlimmer zu machen, könnte der Gradient an einem solchen Punkt negativ sein, was die Suche in Richtung noch negativerer Parameterwerte treibt. (Der Grund ist, dass die Zielfunktion Protokolle enthält, aber der Gradient nicht.)

Was sind einige gute (einfache) Algorithmen, die mit diesem eingeschränkten Optimierungsproblem umgehen? Ich hoffe auf eine einfache Lösung für meinen Algorithmus. Oder vielleicht den Verlauf ignorieren und eine Art Suche nach dem optimalen Parameter durchführen?

Answer 1

Ohne mehr über Ihr Problem zu wissen, ist es schwierig, spezifische Ratschläge zu geben. Ihr Algorithmus für den Gradientenanstieg ist möglicherweise nicht besonders für Ihren Funktionsbereich geeignet. Aber wenn du das hier verwendest, gibt es hier eine Verbesserung, die dir helfen würde.

Sie folgen, was Sie glauben, ist ein aufsteigender Gradient. Aber wenn Sie sich in Richtung des Gradienten bewegen, entdecken Sie, dass Sie in eine Grube mit negativem Wert gefallen sind. Dies impliziert, dass es ein nahegelegenes lokales Maximum gab, aber auch eine sehr scharfe negative Gradientenklippe. Die offensichtliche Lösung besteht darin, zu Ihrer vorherigen Position zurückzukehren und einen kleineren Schritt (z. B. die halbe Größe) zu machen. Wenn Sie immer noch hineinfallen, wiederholen Sie mit einem noch kleineren Schritt. Dies wird wiederholt, bis Sie das lokale Maximum am Rand der Klippe finden.

Das Problem ist, es gibt keine Garantie, dass Ihr lokales Maximum tatsächlich global ist (es sei denn, Sie wissen mehr über Ihre Funktion als Sie teilen). Dies ist die Hauptbeschränkung des naiven Gradientenanstiegs - er fixiert sich immer auf dem ersten lokalen Maximum und konvergiert zu ihm. Wenn Sie nicht zu einem robusteren Algorithmus wechseln möchten, besteht ein einfacher Ansatz darin, die Iterationen Ihres Codes zu starten, wobei Sie jedes Mal von zufälligen Positionen im Funktionsbereich aus beginnen und das beste Maximum behalten, das Sie insgesamt finden . Dieser Monte-Carlo-Ansatz erhöht die Wahrscheinlichkeit, dass Sie auf dem globalen Maximum stolpern, auf Kosten der Verlängerung Ihrer Laufzeit um einen Faktor n. Wie effektiv dies ist, hängt von der "Unebenheit" Ihrer Zielfunktion ab.

Answer 2

Ein einfacher Trick, um einen Parameter als positiv zu definieren, besteht darin, das Problem anhand seines Logarithmus neu zu parametrisieren (stellen Sie sicher, dass Sie den Gradienten entsprechend ändern). Natürlich ist es möglich, dass das Optimum bei dieser Transformation zu hoch ist, und die Suche konvergiert nicht.

Answer 3

1. Jedes Mal, wenn Sie Ihren Parameter aktualisieren, prüfen Sie, ob er negativ ist, und falls ja, klemmen Sie ihn auf Null.
2. Wenn die Klemmung auf Null nicht akzeptabel ist, versuchen Sie eine "Logbarriere" hinzuzufügen (Google it). Im Grunde fügt es Ihrer Zielfunktion eine glatte "weiche" Wand hinzu (und ändert Ihren Farbverlauf), um sie von Regionen fernzuhalten, in die Sie nicht möchten. Sie führen dann die Optimierung wiederholt durch, indem Sie die Wand zu einer unendlichen Vertikalen verhärten, jedoch ausgehend von der zuvor gefundenen Lösung.Im Limit (in der Praxis werden nur ein paar Iterationen benötigt) ist das Problem, das Sie lösen, identisch mit dem ursprünglichen Problem mit einer harten Einschränkung.

Answer 4

Bei jedem Schritt den Parameter als positiv definieren. Dies ist (kurz) der projizierte Gradientenverfahren Sie können über google.

Answer 5

Ich habe drei Vorschläge, in der Reihenfolge, wie viel Denken und Arbeit Sie tun möchten.

Zuerst, in Gradient Sinkflug/Aufstieg, bewegen Sie jedes Mal um die Steigung mal einen Faktor, den Sie als "Lernrate Faktor" bezeichnen. Wenn, wie Sie beschreiben, diese Bewegung bewirkt, dass x negativ wird, gibt es zwei natürliche Interpretationen: Entweder war der Gradient zu groß oder der Lernratenfaktor war zu groß. Da Sie den Verlauf nicht steuern können, nehmen Sie die zweite Interpretation. Überprüfen Sie, ob Ihre Bewegung dazu führt, dass x negativ wird. Wenn dies der Fall ist, reduzieren Sie den Lernfaktor um die Hälfte und versuchen Sie es erneut.

Zweitens, um Anikos Antwort zu vertiefen, sei x dein Parameter und f (x) sei deine Funktion. Dann definiert eine neue Funktion g (x) = f (e^x), und beachten, dass, obwohl die Domäne von f (0, unendlich), die Domäne von g (-Infinity, unendlich). So kann man nicht die Probleme erleiden, die f erleiden. Verwenden Sie den Gradientenabstieg, um den Wert x_0 zu finden, der g maximiert. Dann maximiert e^(x_0), was positiv ist, f. Um Gradientenabstieg auf g anzuwenden, benötigen Sie die Ableitung, die f '(e^x) * e^x ist, durch die Kettenregel.

Drittens klingt es so, als ob Sie versuchen, nur eine Funktion zu maximieren, schreiben Sie keine allgemeine Maximierungsroutine. Sie könnten Regale Gradientenabfallsaktualisierung betrachten, und die Optimierungsverfahren auf die Eigenschaften Ihrer spezifischen Funktion zuzuschneiden. Wir müssten viel mehr über das erwartete Verhalten von f wissen, um Ihnen dabei zu helfen.

Answer 6

Sie bekommen hier gute Antworten. Reparametrisieren ist was ich empfehlen würde. Haben Sie auch eine andere Suchmethode in Betracht gezogen, wie Metropolis-Hastings? Es ist eigentlich ganz einfach, wenn Sie einmal durch die unheimlich aussehende Mathematik gehen, und es gibt Ihnen Standardfehler sowie ein Optimum.

Answer 7

Verwenden Sie einfach Brent's method for minimization. Es ist stabil und schnell und das Richtige, wenn Sie nur einen Parameter haben. Es ist, was die R Funktion optimize verwendet. Der Link enthält auch eine einfache C++ - Implementierung. Und ja, Sie können ihm MIN- und MAX-Parameterwertgrenzen geben.