25

Bei einer konvexen Kostenfunktion, bei der SGD für die Optimierung verwendet wird, haben wir zu einem bestimmten Zeitpunkt während des Optimierungsprozesses einen Gradienten (Vektor).

Meine Frage ist, angesichts des Punktes auf der Konvexen, zeigt der Gradient nur in die Richtung, in die die Funktion am schnellsten zunimmt / abnimmt, oder zeigt der Gradient immer auf den optimalen / extremen Punkt der Kostenfunktion ?

Ersteres ist ein lokales Konzept, letzteres ist ein globales Konzept.

SGD kann sich schließlich dem Extremwert der Kostenfunktion annähern. Ich wundere mich über den Unterschied zwischen der Richtung des Gradienten bei einem beliebigen Punkt auf der Konvexen und der Richtung, die auf den globalen Extremwert zeigt.

Die Richtung des Gradienten sollte die Richtung sein, in der die Funktion an diesem Punkt am schnellsten zunimmt / abnimmt, oder?

neural-networks optimization gradient-descent sgd convex Tyler 玉门十三归归
quelle

6

Sind Sie schon einmal von einem Bergrücken geradeaus bergab gegangen, nur um sich in einem Tal wiederzufinden, das sich bergab in eine andere Richtung fortsetzt? Die Herausforderung besteht darin, sich eine solche Situation mit einer konvexen Topographie vorzustellen: Stellen Sie sich eine Messerschneide vor, bei der der Kamm oben am steilsten ist.

Whuber

4

Nein, weil es sich um eine stochastische Gefälleabfahrt handelt, nicht um eine Gefälleabfahrt. Der springende Punkt bei SGD ist, dass Sie einen Teil der Gradienteninformationen als Gegenleistung für eine höhere Recheneffizienz wegwerfen. Wenn Sie jedoch einen Teil der Gradienteninformationen wegwerfen, erhalten Sie nicht mehr die Richtung des ursprünglichen Gradienten. Dies ignoriert bereits die Frage, ob der reguläre Gradient in die Richtung des optimalen Abstiegs zeigt oder nicht, aber der Punkt ist, selbst wenn der reguläre Gradientabstieg dies tat, es gibt keinen Grund, einen stochastischen Gradientenabstieg zu erwarten, um dies zu tun.

Chill2Macht

3

@ Tyler, warum ist deine Frage speziell nach dem stochastischen Gradientenabstieg ? Stellen Sie sich etwas anderes vor als eine normale Gefälleabfahrt?

Sextus Empiricus

2

Der Gradient zeigt immer in Richtung des Optimums, in dem Sinne, dass der Winkel zwischen dem Gradienten und dem Vektor zum Optimum einen Winkel von weniger als hat und ein infinitesimaler Betrag in Richtung des Gradienten geht Bringen Sie sich dem Optimum näher.

\frac{π}{2}

$\frac{\pi}{2}$

Setzen Sie Monica

5

Wenn der Verlauf direkt auf einen globalen Minimierer zeigt, ist die konvexe Optimierung denkbar einfach, da wir dann einfach eine eindimensionale Liniensuche durchführen könnten, um einen globalen Minimierer zu finden. Dies ist zu viel zu hoffen.

littleO

36

Ein Bild sagt mehr als tausend Worte. Im folgenden Beispiel (mit freundlicher Genehmigung von MS Paint, einem praktischen Tool für Amateur- und Profistatistiker) sehen Sie eine konvexe Funktionsfläche und einen Punkt, an dem die Richtung des steilsten Abfalls deutlich von der Richtung zum Optimum abweicht.

Im Ernst: Es gibt weit überlegene Antworten in diesem Thread, die ebenfalls eine Aufwertung verdienen.

Jan Kukacka
quelle

27

Und das heutige Gegenbeispiel ist ... eine Avocado!

JDL

11

Sie sehen, dass Sie beim Schneiden einer Avocado in die steilste Abstiegsrichtung schneiden sollten, um die Saat und eine mögliche Verletzung zu vermeiden .

Jan Kukacka

28

Gradientenabstiegsmethoden verwenden die Neigung der Oberfläche.
Dies wird nicht unbedingt (oder höchstwahrscheinlich auch nicht) direkt auf den Extrempunkt hinweisen.

Eine intuitive Ansicht ist, sich einen Abstiegsweg vorzustellen, der ein gekrümmter Weg ist. Siehe zum Beispiel die folgenden Beispiele.

Als Analogie: Stellen Sie sich vor, ich verbinde Ihnen die Augen und stelle Sie irgendwo auf einen Berg mit der Aufgabe, zum äußersten (Tief-) Punkt zurückzukehren. Wenn Sie auf dem Hügel nur lokale Informationen haben, wissen Sie nicht , in welche Richtung sich der Grund des Sees befindet.

Wenn Sie von Konvexität ausgehen können

Dann wissen Sie, dass es nur einen extremen Punkt gibt.
Dann wissen Sie, dass Sie mit Sicherheit den äußersten Punkt erreichen werden, solange Sie sich nach unten bewegen.
Und dann wissen Sie auch, dass der Winkel zwischen der steilsten Abstiegsrichtung und der optimalen Richtung immer höchstens beträgt $\pi/2$ , wie in den Kommentaren von Solomonoffs Geheimnis erwähnt.

Ohne Konvexität

Der Winkel kann $\pi/2$ überschreiten . Im Bild unten wird dies durch Zeichnen eines Pfeils in Abstiegsrichtung für einen bestimmten Punkt hervorgehoben, bei dem die endgültige Lösung hinter der Linie senkrecht zur Abstiegsrichtung liegt.

Bei dem konvexen Problem ist dies nicht möglich. Sie könnten dies auf die Isolinien für die Kostenfunktion beziehen, die eine Krümmung in derselben Richtung aufweisen, wenn das Problem konvex ist.

In Stochastic Gradient Descent

Sie folgen der steilsten Richtung für einen einzelnen Punkt (und Sie machen wiederholt einen Schritt für einen anderen Punkt). Im Beispiel ist das Problem konvex, es kann jedoch mehrere Lösungen geben. Im Beispiel befinden sich die Extremwerte auf einer Linie (anstelle eines einzelnen Punkts), und von diesem bestimmten Standpunkt aus könnte man sagen, dass die steilste Abstiegsrichtung direkt auf das "Optimum" zeigen kann (obwohl es nur das Optimum für die Funktion ist des jeweiligen Trainingsbeispielpunktes)

Unten sehen Sie eine weitere Ansicht für vier Datenpunkte . Jedes der vier Bilder zeigt die Oberfläche für einen anderen einzelnen Punkt. Für jeden Schritt wird ein anderer Punkt ausgewählt, entlang dessen der Gradient berechnet wird. Dies bedeutet, dass es nur vier Richtungen gibt, in denen ein Schritt ausgeführt wird, die Schrittgröße jedoch abnimmt, wenn wir uns der Lösung nähern.

Die obigen Bilder beziehen sich auf 4 Datenpunkte, die von der Funktion generiert wurden:

y_{i} = e^{- 0.4 x_{i}} - e^{- 0.8 x_{i}} + ϵ_{i}

$y_i = e^{-0.4x_i}-e^{-0.8 x_i} + \epsilon_i$

x = 0      2      4      6           
y = 0.006  0.249  0.153  0.098

was in ... endet:

$S (a, b) = \sum_{i = 1} {(y_{i} - (e^{- a x_{i}} - e^{- b x_{i}}))}^{2}$ $S(a,b) = \sum_{i=1} \left( y_i - (e^{-ax_i}-e^{-b x_i}) \right)^2$ $\nabla S (a, b) = [\begin{matrix} \sum_{i = 1} 2 x_{i} e^{- a x_{i}} (y_{i} - e^{- a x_{i}} - e^{- b x_{i}}) \\ \sum_{i = 1} - 2 x_{i} e^{- b x_{i}} (y_{i} - e^{- a x_{i}} - e^{- b x_{i}}) \end{matrix}]$ $\nabla S(a,b) = \begin{bmatrix} \sum_{i=1} 2 x_i e^{-a x_i}\left( y_i - e^{-ax_i}-e^{-b x_i} \right) \\ \sum_{i=1} -2 x_i e^{-b x_i}\left( y_i - e^{-ax_i}-e^{-b x_i} \right) \end{bmatrix}$
$S (a, b) = \sum_{i = 1} {(y_{i} - (a e^{- 0.4 x_{i}} - b e^{- 0.8 x_{i}}))}^{2}$ $S(a,b) = \sum_{i=1} \left( y_i - (a e^{-0.4 x_i}- b e^{-0.8 x_i} )\right)^2$ $\nabla S (a, b) = [\begin{matrix} \sum_{i = 1} - 2 e^{- 0.4 x_{i}} (y_{i} - a e^{- 0.4 x_{i}} - b e^{- 0.8 x_{i}}) \\ \sum_{i = 1} 2 e^{- 0.8 x_{i}} (y_{i} - a e^{- 0.4 x_{i}} - b e^{- 0.8 x_{i}}) \end{matrix}]$ $\nabla S(a,b) = \begin{bmatrix} \sum_{i=1} -2 e^{-0.4x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \\ \sum_{i=1} 2 e^{-0.8x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \end{bmatrix}$
$i$
$S (a, b) = {(y_{i} - (a e^{- 0.4 b x_{i}} - b e^{- 0.8 x_{i}}))}^{2}$ $S(a,b) = \left( y_i - (a e^{-0.4 b x_i}- b e^{-0.8 x_i}) \right)^2$ $\nabla S (a, b) = [\begin{matrix} - 2 e^{- 0.4 x_{i}} (y_{i} - a e^{- 0.4 x_{i}} - b e^{- 0.8 x_{i}}) \\ 2 e^{- 0.8 x_{i}} (y_{i} - a e^{- 0.4 x_{i}} - b e^{- 0.8 x_{i}}) \end{matrix}]$ $\nabla S(a,b) = \begin{bmatrix} -2 e^{-0.4x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \\ 2 e^{-0.8x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \end{bmatrix}$ $a$ $b$ $S = 0$

Geschrieben von StackExchangeStrike

Sextus Empiricus
quelle

17

Der steilste Abstieg kann ineffizient sein, selbst wenn die Zielfunktion stark konvex ist.

Normaler Gefälle-Abstieg

Ich meine "ineffizient" in dem Sinne, dass der steilste Abstieg Schritte unternehmen kann, die wild vom Optimum abweichen, auch wenn die Funktion stark konvex oder sogar quadratisch ist.

$f(x)=x_1^2 + 25x_2^2$ $x=[0,0]^\top$

\nabla f (x) = [\begin{matrix} 2 x_{1} \\ 50 x_{2} \end{matrix}]

$\nabla f(x)= \begin{bmatrix} 2x_1 \\ 50x_2 \end{bmatrix}$

$\alpha=0.035$ $x^{(0)}=[0.5, 0.5]^\top,$

x^{(1)} = x^{(0)} - α \nabla f (x^{(0)})

$x^{(1)} =x^{(0)}-\alpha \nabla f\left(x^{(0)}\right)$

das zeigt diesen wild oszillierenden Fortschritt in Richtung des Minimums.

$\theta$ $(x^{(i)}, x^*)$ $(x^{(i)}, x^{(i+1)})$

$x_2$ $x_1$ $\nabla^2 f(x)$

Der direkte Weg zum Minimum wäre, sich "diagonal" statt auf diese Weise zu bewegen, die stark von vertikalen Schwingungen dominiert wird. Allerdings enthält der Gradientenabstieg nur Informationen über die lokale Steilheit, sodass er "nicht weiß", dass die Strategie effizienter ist, und unterliegt den Launen des Hessischen mit Eigenwerten auf verschiedenen Skalen.

Stochastische Gefälleabfahrt

SGD hat die gleichen Eigenschaften, mit der Ausnahme, dass die Aktualisierungen verrauscht sind, was bedeutet, dass die Konturoberfläche von einer Iteration zur nächsten unterschiedlich aussieht und daher auch die Farbverläufe unterschiedlich sind. Dies impliziert, dass der Winkel zwischen der Richtung des Gradientenschritts und dem Optimum ebenfalls Rauschen aufweist - stellen Sie sich dieselben Diagramme mit etwas Jitter vor.

Mehr Informationen:

Diese Antwort leiht dieses Beispiel und diese Figur aus Neural Networks Design (2. Aufl.), Kapitel 9 von Martin T. Hagan, Howard B. Demuth, Mark Hudson Beale und Orlando De Jesús.

Sycorax sagt Reinstate Monica
quelle

13

Die lokal steilste Richtung stimmt nicht mit der globalen optimalen Richtung überein. Wenn dies der Fall wäre, würde sich Ihre Gradientenrichtung nicht ändern. Denn wenn Sie sich immer Ihrem Optimum nähern, zeigt Ihr Richtungsvektor immer auf das Optimum. Das ist aber nicht der Fall. Wenn ja, warum sollten Sie sich dann die Mühe machen, Ihren Gradienten bei jeder Iteration zu berechnen?

gunes
quelle

3

Die anderen Antworten heben einige lästige Probleme mit der Konvergenzrate für GD / SGD hervor, aber Ihr Kommentar "SGD kann irgendwann konvergieren ..." ist nicht immer korrekt (ignorieren Sie pedantische Verwendungsbemerkungen zum Wort "can", da es so aussieht, als ob Sie es gemeint hätten "werden").

(x_{0}, y_{0}) = (1, 0)

$(x_0,y_0)=(1,0)$

α

$\alpha$

f (x, α) = \sqrt{α^{2} - α x} .

$f(x,\alpha)=\sqrt{\alpha^2-\alpha x}.$

(f (x_{0}, α) - y_{0})^{2} = α^{2} - α,

$(f(x_0,\alpha)-y_0)^2=\alpha^2-\alpha,$

β

$\beta$

α_{n + 1} = α_{n} - β (2 α_{n} - 1) = α_{n} - (2 α_{n} - 1) = 1 - α_{n} .

$\alpha_{n+1}=\alpha_n-\beta(2\alpha_n-1)=\alpha_n-(2\alpha_n-1)=1-\alpha_n.$

α = \frac{1}{2}

$\alpha=\frac12$ $p=\frac12$

p

$p$

1 - p

$1-p$

Ich bin mir nicht sicher, ob Konvexität ausreicht, um ein für allgemeine SGD-Zustände übliches schlechteres Verhalten zu verhindern. Wenn Sie jedoch Funktionen zulassen, die für Ihre Kostenfunktion sogar so komplex sind wie Kubikwerte, kann SGD auf einer dichten Teilmenge der Domäne herumspringen und nirgendwo konvergieren oder nähern Sie sich einem beliebigen Zyklus.

$\infty$ $\pm\infty$

Das Interessante an der gesamten Situation ist, dass es unzählige Funktionen gibt (wie SGD), die willkürliche konvexe Funktionen als Eingaben verwenden und dann eine Aktualisierungsregel ausgeben, die immer schnell zum globalen Minimum konvergiert (falls vorhanden). Auch wenn es konzeptionell eine Menge davon gibt, haben unsere besten Versuche zur konvexen Optimierung alle pathologische Gegenbeispiele. Irgendwie widerspricht die Idee einer einfachen / intuitiven / performanten Update-Regel der Idee einer nachweislich korrekten Update-Regel.

Hans Musgrave
quelle

1

β = 1

$\beta=1$

1

Beachten Sie, dass der SGD-Konvergenznachweis eine abnehmende Schrittgröße voraussetzt ...

Jan Kukacka

@ MartijnWeterings Gute Beobachtung. Ich denke, mein Beispiel zeigt tatsächlich die richtige Richtung. Sollte ich es mit einem 2D-Beispiel aktualisieren, das niemals in die richtige Richtung weist und auseinander läuft?

Hans Musgrave

β = 1

$\beta=1$

β > 0

$\beta>0$

β

$\beta$

f (x, α) = \sqrt{\frac{α^{2} - α x}{β}} .

$f(x,\alpha)=\sqrt{\frac{\alpha^2-\alpha x}{\beta}}.$

f

$f$

β

$\beta$

2

Vielleicht müssen die Antworten auf diese Frage schnell aktualisiert werden. Es scheint, dass SGD auch im nicht-konvexen Fall ein globales Minimum ergibt (konvex ist nur ein Sonderfall davon):

SGD erreicht globales Minimum beim Deep Learning über den Star-Convex-Pfad, anonyme Autoren , Artikel im Doppelblind-Review beim ICLR 2019

https://openreview.net/pdf?id=BylIciRcYQ

Die Autoren stellen die Konvergenz von SGD zu einem globalen Minimum für nicht konvexe Optimierungsprobleme fest, die üblicherweise beim Training von neuronalen Netzen auftreten. Das Argument nutzt die folgenden zwei wichtigen Eigenschaften aus: 1) Der Trainingsverlust kann (ungefähr) den Wert Null erreichen. 2) SGD folgt einem sternkonvexen Pfad. In einem solchen Kontext zeigt sich, dass SGD, obwohl es lange Zeit als randomisierter Algorithmus galt, auf intrinsisch deterministische Weise zu einem globalen Minimum konvergiert.

Dies sollte jedoch mit einem Körnchen Salz eingenommen werden. Das Papier wird noch geprüft.

Der Begriff des sternenkonvexen Pfades gibt einen Hinweis darauf, wohin der Gradient bei jeder Iteration weisen würde.

Tolga Birdal
quelle

Zeigt der Gradient in Stochastic Gradient Descent (SGD) bei konvexen Problemen immer auf den globalen Extremwert?

Antworten:

Wenn Sie von Konvexität ausgehen können

Ohne Konvexität

In Stochastic Gradient Descent

Normaler Gefälle-Abstieg

Stochastische Gefälleabfahrt