Konvergiert der Gefälleverlauf immer zu einem Optimum?

20

Ich frage mich, ob es ein Szenario gibt, in dem der Gefälle nicht auf ein Minimum konvergiert.

Mir ist bewusst, dass der Gradientenabstieg nicht immer garantiert zu einem globalen Optimum konvergiert. Mir ist auch bewusst, dass es von einem Optimum abweichen kann, wenn beispielsweise die Schrittgröße zu groß ist. Es scheint mir jedoch, dass, wenn es von einem Optimum abweicht, es irgendwann zu einem anderen Optimum übergeht.

Daher würde ein Gradientenabstieg garantiert zu einem lokalen oder globalen Optimum konvergieren. Ist das richtig? Wenn nicht, geben Sie bitte ein grobes Gegenbeispiel an.

wit221
quelle
1
Hoffe, dieser Link wird in Zukunft helfen .. datascience.stackexchange.com/a/28417/35644
Aditya
1
In dieser Antwort finden Sie 3 konkrete und einfache Beispiele, darunter Beweise, Bilder und Code, mit denen eine Animation des Gefälleverlaufs erstellt wird
Oren Milman

Antworten:

26

Gradient Descent ist ein Algorithmus, mit dem die optimalen Punkte ermittelt werden. Diese optimalen Punkte sind jedoch nicht unbedingt global. Und ja, wenn es von einem lokalen Ort abweicht, kann es zu einem anderen optimalen Punkt konvergieren, aber seine Wahrscheinlichkeit ist nicht zu groß. Der Grund dafür ist, dass die Schrittgröße möglicherweise zu groß ist, um einen optimalen Punkt zu erreichen, und dass die Wahrscheinlichkeit, dass sie schwingt, viel größer ist als die Konvergenz.

Über den Gradientenabstieg gibt es zwei Hauptperspektiven: das Zeitalter des maschinellen Lernens und das Zeitalter des tiefen Lernens. Während der Ära des maschinellen Lernens wurde angenommen, dass der Gradientenabstieg das lokale / globale Optimum findet, aber in der Tiefenlernära, in der die Dimension der Eingabemerkmale zu groß ist, wird in der Praxis gezeigt, dass die Wahrscheinlichkeit, dass sich alle Merkmale in diesem optimalen Wert befinden An einem Punkt ist es nicht zu viel und da die Kostenfunktionen optimale Positionen aufweisen, werden die meisten Sattelpunkte beobachtet. Dies ist einer der Gründe, warum das Training mit vielen Daten und Trainingsepochen dazu führt, dass Deep-Learning-Modelle andere Algorithmen übertreffen. Wenn Sie also Ihr Modell trainieren, wird es einen Umweg finden oder den Weg finden, bergab zu fahren und nicht in Sattelspitzen zu stecken, aber Sie müssen entsprechende Schrittgrößen haben.

Für mehr Intuitionen empfehle ich Ihnen, hier und hier zu verweisen .

Medien
quelle
3
Genau. Diese Probleme tauchen in der Theorie immer auf, in der Praxis jedoch selten. Bei so vielen Dimensionen ist dies kein Problem. Sie haben ein lokales Minimum in einer Variablen, aber nicht in einer anderen. Darüber hinaus hilft ein Minibatch- oder stochastischer Gefälle-Abstieg auch dabei, lokale Minima zu vermeiden.
Ricardo Cruz
3
@ RicardoCruz Ja, ich bin einverstanden, Sir
Media
12

Abgesehen von den Punkten, die Sie erwähnt haben (Konvergenz zu nicht-globalen Minimums und große Schrittgrößen, die möglicherweise zu nicht-konvergenten Algorithmen führen), könnten auch "Flexionsbereiche" ein Problem sein.

Betrachten Sie den folgenden Funktionstyp "Liegestuhl".

Bildbeschreibung hier eingeben

Offensichtlich kann dies so konstruiert werden, dass es einen Bereich in der Mitte gibt, in dem der Gradient der 0-Vektor ist. In diesem Bereich kann der Algorithmus auf unbestimmte Zeit stecken bleiben. Wendepunkte werden in der Regel nicht als lokale Extreme betrachtet.

Ami Tavory
quelle
4

x=0f(x)=x3

Herbert Knieriem
quelle
3

[Anmerkung 5 April 2019: Eine neue Version des Papiers wurde auf arXiv mit vielen neuen Ergebnissen aktualisiert. Wir führen auch Backtracking-Versionen von Momentum und NAG ein und beweisen die Konvergenz unter den gleichen Voraussetzungen wie für Backtracking Gradient Descent.

Quellcodes sind auf GitHub unter folgendem Link verfügbar: https://github.com/hank-nguyen/MBT-optimizer

Wir haben die Algorithmen für die Anwendung auf DNN verbessert und erzielen eine bessere Leistung als moderne Algorithmen wie MMT, NAG, Adam, Adamax, Adagrad, ...

Das Besondere an unseren Algorithmen ist, dass sie automatisch ablaufen. Sie müssen die Lernraten nicht wie üblich manuell anpassen. Unsere automatische Feinabstimmung unterscheidet sich von Adam, Adamax, Adagrad usw. Weitere Details finden Sie in der Zeitung.

]

Basierend auf den jüngsten Ergebnissen: In meiner gemeinsamen Arbeit in diesem Artikel https://arxiv.org/abs/1808.05160

f

Auf dieser Grundlage haben wir eine neue Methode für das Tiefenlernen vorgeschlagen, die dem aktuellen Stand der Technik entspricht und keine manuelle Feinabstimmung der Lernraten erfordert. (Auf den Punkt gebracht , besteht die Idee darin, dass Sie eine gewisse Zeit lang einen Rückverfolgungsgradientenabstieg ausführen, bis Sie feststellen, dass sich die Lernraten, die sich mit jeder Iteration ändern, stabilisieren. Wir erwarten diese Stabilisierung, insbesondere an einem kritischen Punkt, der ist C ^ 2 und ist aufgrund des oben erwähnten Konvergenzergebnisses nicht entartet. Zu diesem Zeitpunkt wechseln Sie zur Standardmethode für die Gradientenabnahme. Weitere Informationen finden Sie in der zitierten Veröffentlichung. Diese Methode kann auch auf andere optimale Algorithmen angewendet werden .)

PS: Bezüglich Ihrer ursprünglichen Frage zur Standardmethode der Gradientenabnahme, meines Wissens nur für den Fall, dass die Ableitung der Karte global Lipschitz ist und die Lernrate klein genug ist, dass die Standardmethode der Gradientenabnahme nachweislich konvergiert. [Wenn diese Bedingungen nicht erfüllt sind, gibt es einfache Gegenbeispiele, die zeigen, dass kein Konvergenzergebnis möglich ist, siehe den zitierten Aufsatz für einige.] In dem oben zitierten Aufsatz haben wir argumentiert, dass auf lange Sicht die Methode des Rückverfolgungsgradientenabfalls angewendet wird die Standardmethode zur Gradientenabnahme, die erklärt, warum die Standardmethode zur Gradientenabnahme in der Praxis normalerweise gut funktioniert.

Tuyen
quelle