Gradientenabstieg und die Lernrate

Alles, was aus Daten lernt, tut das durch kleine Schritte bergab. Die einzige wirkliche Frage ist, wie groß du den Schritt wählst, und die Antwort ist seltsamer als „so groß, wie du dich traust“: Es gibt eine Rate, die in einem Zug ankommt, und eine Rate, ab der die Sache niemals ankommt.

Rechenbeispiel — Gradientenabstieg und die Lernrate

Schrittmultiplikator r	0,9000
Was diese Rate bewirkt	Konvergiert direkt
Konvergenz stoppt bei	2,000
Ein-Schritt-Rate	1,000
Position nach 20 Schritten	0,3647
Verlust dort	0,0665
Anteil des Startverlusts	0,0148
Schritte, um \|x\| unter 10⁻⁶ zu bringen	142

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Gradientenabstieg und die Lernrate

Gradientenabstieg besteht aus einer einzigen, immer wiederholten Anweisung: Stell dich irgendwo hin, miss die Steigung und mach einen proportionalen Schritt bergab. x ← x − η f′(x). Die Schrittweite η gehört nicht zur Aufgabenstellung. Die Verlustkurve ist vorgegeben, der Gradient wird berechnet, und η ist die einzige Zahl, die du wählst. Bei einer quadratischen Funktion mit der Krümmung a ist die Rechnung exakt lösbar. Deshalb verwendet diese Seite eine solche Funktion: Jede spätere Aussage über Lernraten ist im Grunde eine Aussage über 1 − ηa.

Was die einzelnen Symbole bedeuten

η: die Lernrate, das Einzige, was du wählst
a: die Krümmung der Verlustfunktion, die das Problem für dich vorgibt

Setzt voraus: Eine Variable, eine feste Schrittweite und ein exakt bekannter Gradient. Reales Training bricht mit allen drei Bedingungen auf einmal. Du arbeitest mit Millionen Parametern, einer Schrittweite nach Plan und einem Gradienten, der aus einem kleinen Batch geschätzt wird. Das Einzige, was intakt bleibt, ist die Grenze bei 2/a. Sie stammt von der Krümmung in einer einzigen Richtung, und eine reale Verlustfläche besitzt genau eine davon pro Eigenvektor.

Die Grenze gehört zur Fläche, nicht zu deinem Durchlauf 🖖

Zieh den Startpunkt wohin du willst, hinaus bis zur 10 oder hinüber auf die andere Seite des Tals, und 2/a bewegt sich nicht. Es kümmert sich auch nicht darum, wie viele Schritte du machst. Die Grenze wird allein durch die Krümmung festgelegt, weil der Schrittmultiplikator r = 1 − aη weder x₀ noch irgendeine Schrittzahl enthält. Der gesamte Durchlauf besteht aus x₀, das so oft mit r multipliziert wird, wie du verlangt hast. Ob der Wert also schrumpft, hängt ganz allein von r ab. Näher am Grund zu starten, bringt dir keinen zusätzlichen Spielraum, sondern verzögert nur den Moment, in dem eine zum Scheitern verurteilte Rate offensichtlich wird. Setz die Krümmung auf 1,6 und die Rate auf 1,3, und dann zieh den Startpunkt über seinen gesamten Bereich: Die Tabelle zeigt an jeder Position Divergiert, selbst bei jenen, die eine halbe Einheit vom Minimum entfernt liegen.

Überschießen allein kostet nichts 🖖

Setz die Krümmung auf 1, was die Ein-Schritt-Rate auf η = 1 legt. Probier jetzt 0,9 aus und dann 1,1. Beide bringen |x| in sieben Schritten unter 10⁻⁶. Eine davon kriecht an einer einzelnen Talwand hinab; die andere springt bei jedem Schritt sauber über den Grund und landet abwechselnd auf beiden Seiten. Sie kosten dasselbe, weil der Multiplikator im einen Fall 1 − aη lautet und im anderen dessen Negatives. Ein negativer Multiplikator lässt eine Zahl exakt so schnell schrumpfen wie sein positiver Zwilling. Die Symmetrie ist nicht nur ungefähr. Versuch es mit 0,5 und 1,5: jeweils zweiundzwanzig Schritte. Ein Zickzack-Weg verrät dir also, auf welcher Seite der besten Rate du stehst, aber absolut nichts darüber, ob du zu weit gegangen bist. Dafür ist 2/a die einzige Zahl, die zählt.

Warum reale Lernraten immer noch geschätzt werden 🖖

Diese Seite hat eine Krümmung, weil sie eine Dimension besitzt. Ein echtes Netzwerk hat Millionen von Parametern, und seine Verlustfläche krümmt sich in jede Richtung unterschiedlich stark. Die Überlegung bleibt jedoch gültig, wenn du a durch die größte Krümmung irgendwo auf der Fläche ersetzt, den höchsten Eigenwert der Hesse-Matrix. Eine einzige Lernrate muss in alle Richtungen gleichzeitig sicher sein, also entscheidet die steilste Richtung, wann das Ganze explodiert. Die flachste Richtung bestimmt, wie lange du wartest, da der Fortschritt dort von ihrer eigenen kleinen Krümmung diktiert wird. Das Verhältnis zwischen beiden ist die Konditionszahl, und sie erklärt, warum sich eine auf ein Problem abgestimmte Rate so schlecht auf das nächste übertragen lässt. Nichts am Verlust kündigt einen der beiden Eigenwerte im Voraus an, und den größten für hundert Millionen Parameter zu berechnen, macht niemand mal eben vor dem Frühstück. Momentum und parameterweise Methoden wie Adam existieren, um die Lücke zwischen dem, was stabil ist, und dem, was schnell ist, zu vergrößern.

Aufgabe vollständig gelöst

Deine Lernrate von 0,4 funktioniert. Finde die exakte Krümmung, bei der sie aufhört zu funktionieren, und beschreibe, wie das Scheitern auf beiden Seiten dieses Punktes aussieht. Starte im Tool bei η = 0,4, a = 1, x₀ = 8, wo die Zeile Schrittmultiplikator 0,6000 anzeigt und der Weg ruhig an einer Wand hinabläuft.

Öffne diese Aufgabe im Tool
1. Jede Frage auf dieser Seite ist eine Frage über |r| < 1, wobei r = 1 − aη gilt. Die Rate ist auf 0,4 fixiert und die Krümmung ist das, was du verändern darfst. Schreib die Bedingung also in Abhängigkeit von a statt von η.
  
  $x_{n + 1} = x_{n} - η f^{'} (x_{n}) = (1 - a η) x_{n} ⟹ r = 1 - a η$
2. |1 − 0,4a| < 1 entfaltet sich zu −1 < 1 − 0,4a < 1, dann zu 0 < 0,4a < 2, also a < 5. Die Rate übersteht jede Krümmung unter 5 und keine darüber. Das ist das vertraute η < 2/a andersherum gelesen, als a < 2/η. Dieselbe Ungleichung, und die zweite Umstellung ist diejenige, die beantwortet, was gefragt war.
  
  $∣1 - 0.4 a ∣ < 1 ⟺ 0 < 0.4 a < 2 ⟺ a < 5 = \frac{2}{η}$
3. Setz a exakt auf 5 und lies die Tabelle. r = −1,0000, und Position nach 20 Schritten gibt 8,000 aus, die Zahl, bei der es anfing. Der Anteil des Startverlusts beträgt 1,000. Das ist die Grenze selbst: Jeder Schritt landet genauso weit vom Minimum entfernt wie der letzte, auf der gegenüberliegenden Seite. Der Weg springt also zwischen 8 und −8 hin und her, solange du ihn laufen lässt.
  
  $a = 5 : r = - 1, x_{20} = x_{0} = 8$
4. Nun schieb a auf 5,1. r = −1,0400, und nach zwanzig Schritten liegt x bei 17,529 statt bei 8. Das ist echte Divergenz, und es lohnt sich zu sehen, wie mild sie aussieht: Zwanzig Schritte haben die Distanz grob verdoppelt. Ein Durchlauf knapp auf dieser Seite der Grenze kann lange Zeit als bloßes Rauschen durchgehen, bevor die Zahlen offensichtlich absurd werden.
  
  $a = 5.1 : r = - 1.04, x_{20} = 17.529$
5. In die andere Richtung konvergiert a = 4,9 noch. r = −0,9600, |r| liegt unter 1, und die Tabelle sagt Schießt über, konvergiert. Aber Schritte, um |x| unter 10⁻⁶ zu bringen zeigt nun 390, im Gegensatz zu 32 bei a = 4. Fast-stabil ist beinahe nutzlos.
  
  $a 14 4.9 5 5.1 r 0.6000 - 0.6000 - 0.9600 - 1.0000 - 1.0400 behaviour direct overshoots overshoots neither diverges steps to 1 0^{- 6} 3232390 \infty \infty$
Antwort

a = 5, was 2/η entspricht. Darunter konvergiert die Rate, genau dort ändert sich der Verlust nie, darüber wächst der Verlust grenzenlos. Der teure Teil ist die Annäherung. Nahe der Grenze ist |r| gleich 1 − a·g, wenn du g für die Lücke 2/a − η schreibst. Daher gilt log|r| ≈ −a·g, und die Schrittzahl ist ungefähr log(|x₀|/Toleranz) geteilt durch a·g. Sie verhält sich wie eins geteilt durch den Abstand zur Grenze: Halbiere die Lücke, und du verdoppelst die Arbeit. Bei a = 5 von x₀ = 8 benötigen Lücken von 0,05, 0,025 und 0,0125 exakt 56, 120 und 247 Schritte. Multiplizierst du jede Anzahl mit ihrer eigenen Lücke, erhältst du 2,8, 3,0 und 3,1, was sich log(8 × 10⁶)/5 = 3,18 nähert. Das ist der Grund, warum eine gut abgestimmte Lernrate nie am Rand der Stabilität liegt. Der letzte sichere Streifen vor der Grenze gehört gleichzeitig zum langsamsten Terrain auf der gesamten Achse, und die schnellste Rate von allen ist die in der Mitte bei 1/a.

$a^{*} = \frac{2}{η} = 5$

Lernpfad

Eine Gerade an Daten anpassen

Quellen (3)

Where the method comes from. Two pages, and the idea is already complete: follow the gradient downhill in steps. A.-L. Cauchy, “Méthode générale pour la résolution des systèmes d’équations simultanées.” Comptes Rendus de l’Académie des Sciences 25, 536–538, 1847.
The tool's central claim, in the form it takes for a real network: with a as the largest eigenvalue of the Hessian, the fastest single learning rate is 1/a and anything past 2/a diverges. This is the source for insight block 3. Y. LeCun, L. Bottou, G. B. Orr and K.-R. Müller, “Efficient BackProp.” In Neural Networks: Tricks of the Trade, Lecture Notes in Computer Science, 9–50. Springer, 1998.
The convergence analysis behind the step count: why the work needed grows with the ratio of the largest curvature to the smallest, which is the condition number named in insight block 3. S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004.

Vom 42Math-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.