Numerische Optimierung für Deep Learning Algorithmen...die beste Wahl darstellen. Die Idee von adaptiven Algorithmen, die wir im Weiteren vorstellen, ist folgende: Man passt die Lernrate

Optimierung und Deep LearningWintersemester 2018/2019

Numerische Optimierung für Deep Learning AlgorithmenSeite 1/9

Numerische Optimierung für Deep Learning AlgorithmenLucas Plagwitz

29. November 2018

Das Lernen eines Deep-Learning-Netzes kann bei einer hohen Anzahl an Neuronen oder schwierigen Da-tensätzen sehr langsam sein. Um das Lernen zu beschleunigen gibt es mehrere Ansätze wie beispielsweisedie Wahl einer geeigneten Initialisierung aller Gewichte oder die Wahl der Aktivierungsfunktion. Im fol-genden Vortrag stellen wir eine Möglichkeit vor, die das Lernen durch Verwendung schnellerer Optimiererdeutlich verbessert. Wir beginnen mit dem gewöhnlichen Optimierer, dem Gradientenverfahren, welcheswir Schritt für Schritt weiter optimieren bis wir am Ende den Adam-Optimierer einführen können.

1 Motivation - Optimierung im Neuronalen Netz

Zunächst betrachten wir den Punkt im selbstlernenden Neuronalen Netz, an dem wir mittels geeignetemVerfahren die Gewichte jeder neuronalen Verbindung optimieren:

Bei jedem Trainingsdatenpunkt trifft der Backpropagation-Algorithmus zuerst eine Vorhersage (Vorwäts-durchlauf), bestimmt den Fehler, durchläuft dann rückwärts jede Schicht um den Fehlerbeitrag jeder Ver-bindung zu ermitteln (Rückwärtsdurchlauf). Anschließend verändert er die Gewichte der Verbindungen umden Fehler zu verringern (als Schritt im Optimierungsverfahren). Gängie Praxis für ein solches Optimie-rungsverfahren sind verschiedene Gradientenverfahren, welche in diesem Vortrag vorgestellt werden.

1.1 Gradientenverfahren

Wir haben nun gesehen an welcher Stelle im Deep Learning Netz wir den Optimierer benötigen. Als ers-tes betrachten wir kurz das gewöhnliche Gradientenverfahren, das meist die erste Wahl eines Optimieresdarstellt. Das Gradientenverfahren beschreibt einen Algorithmus, der für eine Funkion J(θ), im Weiterenauch Kostenfunktion genannt, den Eingabeparameter θ ∈ Rd in entgegengesetzter Richtung des Gradi-enten (steilsten Anstiegs) ∇θJ(θ) aktualisiert. Über die sogenannte Lernrate wird festgelegt wie weit derAlgorithmus sich in jeder Iteration vom Ausgangspunkt entfernen darf.

Algorithm 1 Gradientenverfahren1: Initialisiere θ0, η2: for k = 0; k ≤ n; k++ do3: θk+1 = θk − η∇θkJ(θk)4: END



2 Optimierer im Überblick

Im vorangegangenen Vortrag haben wir bereits gesehen, wie man über einzelne Batches des Datensatzesoptimieren kann. Dennoch führen wir alle Algorithmen für eine gleichbleibende Kostenfunktion ein. DieBatchoptimierung lässt sich allerdings ohne Umstände übertragen. Nun kommen wir zu den Verbesserun-gen des Gradientenverfahrens.

2.1 Momentum Optimierer

Der Momentum Optimierer erweiterter den Ansatz des Gradientenverfahrens. Während das Standardgra-dientenverfahren pro Iterationsschritt immer in entgegengesetzte Richtung des lokalen Gradientens ab-steigt, nimmt der Momentum Optimierer Rücksicht auf die Gradienten der vorherigen Iterationen, akku-muliert diese zu dem lokalen Gradienten und speichert das Ergebnis in den sogenannten Momentvektor.Vergleichbar mit einem Ball, der sich pro Iteration beschleunigt je stärker es bergab geht.

Algorithm 2 Momentum Optimierer1: Initialisiere m0, θ0, η2: for k = 0; k ≤ n; k++ do3: mk+1 = βmk − η∇θJ(θ)4: θk+1 = θk +mk+1

5: END

Uns liegen nun die Momentvektoren mk vor, die sich aus gewichteten Teilen früherer Gradienten und demlokalen Gradienten zusammensetzen. Anders ausgedrückt wird der lokale Gradient als Beschleunigung undnicht als Geschwindigkeit interpretiert. Der Hyperparameter β ∈ [0, 1] wird genutzt um Reibung nachzubil-den und ein zu großes Moment zu verhindern. Eine typische Wahl für β liegt bei 0.9

(a) SGD ohne Moment (b) SGD mit Moment

Abbildung 1: SGD Vergleich [RS17]

Bemerkung. Im Vergleich zum Standardgradientenverfahren kann dieser Optimierer ein wenig stärker überdas Ziel hinausschießen und mehrmals oszillieren bevor er sich beim Minimum stabilisiert. Aus diesemGrund ist es gut die Reibung β zu wählen, die die Oszillationen verringert.



2.2 Beschleunigter Gradient nach Nesterov

Eine erweiterte Variante der Momentum Optimierung stellt Nesterovs beschleunigter Gradient (kurz: NAGvon „Nesterov accelerated gradient“) dar. Das Verfahren aus dem Jahr 1983 bekam seinen Namen vom rus-sischen Mathematiker Juri (Yurii) Nesterov. Die Idee von Nesterov liegt darin, den Gradienten der Kosten-funktion nicht an der aktuelle Position, sondern ein wenig weiter in Richtung des Moments zu bestimmen.Somit besteht der einzige Unterschied an dem Ort des Gradienten, der nun anstatt bei θk bei θk + βmkberechnet wird.

Algorithm 3 NAG1: Initialisiere m0, θ02: for k = 0; k ≤ n; k++ do3: mk+1 = βmk − η∇θkJ(θk + βmk)4: θk+1 = θk +mk+1

5: END

Durch diese Modifikation ist der Algorithmus fast immer schneller als die reine Momentum Optimierung,da der Momentvektor im Allgemeinen in die Richtung zum Optimum hin zeigt.

Abbildung 2: Nesterovs beschleunigter Gradient im Vergleich zum normalen Moment (γ = β) [AG18]



2.3 AdaGrad

Für manche Probleme ist festzustellen, dass ein Abstieg wie in den momentbasierten Algorithmen nichtdie beste Wahl darstellen. Die Idee von adaptiven Algorithmen, die wir im Weiteren vorstellen, ist folgende:Man passt die Lernrate an die Parameter an und führt größere Aktualisierungen für seltene und kleinereAktualisierungen für häufige Parameter durch. Aus diesem Grund eignet sie sich besonders gut für denUmgang mit spärlichen Daten.

Der Hauptgedanken hinter Adagrad ist das Herunterskalieren des Gradientenvektors. Anders ausgedrücktwird die Lernrate pro Dimension nach und nach abgebaut, bei steilen Dimensionen erfolgt der Abbauschneller.

Algorithm 4 Adagrad1: Initialisiere s0, θ0, η2: for k = 0; k ≤ n; k++ do3: sk+1 = sk +∇θkJ(θk)⊗∇θkJ(θk)4: θk+1 = θk − η∇θkJ(θk)�

√sk+1 + ε

5: END

Mit ⊗ ist hier die elementweise Multiplikation gemeint. Ist die Kostenfunktion entlang der i-ten Dimensionsteil, wird die i-te Komponente des s von Iteration zu Iteration immer kleiner.

Bemerkung. In der Praxis wird AdaGrad selten genutzt, da die Lernrate oft zu schnell herunterskaliert wird,sodass der Algorithmus anhält bevor er das globale Optimum erreicht.

2.4 RMSProp

Eine kleine Veränderung des AdaGrad Alogrithmus bringt uns zur RMSProp Methode, eine unveröffent-lichte adaptive Methode aus einer Vorlesung des britischer Informatikers Geoff Hinton, einem Vater desBackpropagation-Algorithmus. Den einzigen Unterschied erhält man durch einen exponentiellen Verfallder sk . So ändert sich der Algorithmus zu:

Algorithm 5 RMSProp1: Initialisiere s0, θ0, β, η2: for k = 0; k ≤ n; k++ do3: sk+1 = βsk + (1− β)∇θkJ(θk)⊗∇θkJ(θk)4: θk+1 = θk − η∇θkJ(θk)�

√sk+1 + ε

5: END

Hier werden nun nur die Gradienten der letzten Iterationen und nicht sämtliche Gradienten seit Trainings-beginn akkumuliert. Die Zerfallsrate β wird meist auf 0.9 initialisiert. Insgesamt lässt sich sagen, dass imAllgemeinen RMSProp schneller konvergiert als AdaGrad.



3 Adam Optimierung

3.1 Überblick

Eine Kombination aus der Idee des Momentum Optimierers und RMSProp ergibt die Adam-Optimierung.Adam ist dabei die Abkürzung für Adaptive Moment Estimation. Bei der Kombination betrachtet das Ver-fahren nun sowohl den Durchschnitt der vorigen Gradienten (Momentum Optimierer) als auch den Durch-schnitt der quadrieten Gradienten (RMSProp), beide unter exponentiellem Zerfall.

Algorithm 6 Adam1: Initialisiere m0 = 0, s0 = 0, θ0, β1, β2, η2: for k = 0; k ≤ n; k++ do3: mk+1 = β1mk + (1− β1)∇θkJ(θk)4: sk+1 = β2sk + (1− β2)∇θkJ(θk)⊗∇θkJ(θk)5: mk+1 = mk+1/(1− βk+11 )

6: sk+1 = sk+1/(1− βk+12 )

7: θk+1 = θk − ηmk+1 �√sk+1 + ε

8: END

Betrachten wir nun jede Zeile für sich erkennen wir, dass Zeile 3,4,7 die logische Kombination des Momentsmit RMSProp ist. Die Zeilen 3 und 4 erhalten ein technisches Detail. Weil m0 und s0 mit dem Nullvektorinitialisiert wurden, erhalten sie zu Beginn des Trainierens eine Biaskorrektur. Somit findet am Anfang eineAufwertung der Vektoren statt.

3.2 Konvergenzanalyse

Stellen wir uns vor, wir hätten anstatt einer gleichbleibenden Kostenfunktion eine Funktion, die sich proIteration ändert (beispielsweise durch das Implementieren des Stochastik oder Mini-Batch Gradientenver-fahrens). So erhielten wir eine Funktionenfolge von J0(θ), . . . , Jn(θ). Sei θ∗ das Minimum der Argumenteüber die Summe all diese Funktion bis zur n-ten Iteration, also θ∗ = argminθ

∑nk=0 Jk(θ) und θk der Para-

meter zur Iteration k . So erhalten wir eine mögliche Regretgleichung durch:

R(n) =

n∑k=0

(Jk(θk)− Jk(θ∗))



Bemerkung. Die Form der Regretgleichung wurde in [KD17] vorgestellt und ist nicht komplett schlüssig. ImWeiteren werden wir anreißen, dass der Regret unter bestimmten Voraussetzungen beschränkt ist. Aller-dings muss das nicht viel bedeuten, da der Regret nicht zwangsweise positiv ist, was die zu zeigende obereSchranke trivial und bedeutungslos gestaltet. Man stelle sich vor θk minimiert jedes Jk , so gilt R(n) ≤ 0.Würde man jeden Summanden des Regrets im Absolutbetrag betrachten, ergebe dies in der Interpretationmehr Sinn, allerdings ist dies nicht mit dem vorhandenen Beweis in [KD17] vereinbar.

Trotz dieser Beobachtung stellen wir kurz das aus [KD17] folgende Theorem vor, das den Regret R(n) nachoben beschränkt.

Theorem 1. Sei (Jk)k∈N eine Folge von konvexen Funktionen für den Adam-Algorithmus mit folgendenEigenschaften:

1) ||∇Jk(θ)||2 ≤ G und ||∇Jk(θ)||∞ ≤ G∞ für alle θ ∈ Rd und k ∈ {1, · · · , n} mit G,G∞ ∈ R

2) ||θn − θm||2 ≤ D und ||θn − θm||∞ ≤ D∞ für alle m, n ∈ {1, · · · , n} mit D,D∞ ∈ R

3) β1, β2 ∈ [0, 1) mit β21√β2< 1

Dann erreicht Adam für alle n ≥ 1:

R(n)

n= O

(1√n

)⇒ lim

n→∞

R(n)

n= 0

Für den Beweis wird auf [KD17] verwiesen.

3.3 Erweiterungen zu AdaMax und Nadam

Es gibt von diesem Punkt an noch weiter Anpassungen des Adam-Algorithmus. So lässt sich der adaptiveTeil durch die `p-Norm verallgemeinern. Damit wird aus Zeile 4:

sk+1 = βp2sk + (1− β

p2)∇θkJ(θk)

p ∇θkJ(θk)p = ∇θkJ(θk)⊗ · · · ⊗ ∇θkJ(θk)

Üblich sind Werte von p ∈ {1, 2,∞}, da die Berechnung der `p-Norm für großes p schnell instabil werdenkann. Allerdings treten diese Schwierigkeiten bei der `∞-Norm nicht auf, da sich das sk+1 wie folgt ändert:

limp→∞

s1/pk+1 = limp→∞

((1− βp2)

k∑i=1

βp(k−i)2 |∇θi J(θi)|p

)1/p= max(β2sk , |∇θkJ(θk)|)



Durch diese Änderung erhalten wir den sogenannten AdaMax-Algorithmus:

Algorithm 7 AdaMax1: Initialisiere m0 = 0, s0 = 0, θ0, β1, β22: for k = 0; k ≤ n; k++ do3: mk+1 = β1mk + (1− β1)∇θkJ(θk)4: sk+1 = max(β2sk , |∇θkJ(θk)|)5: mk+1 = mk+1/(1− βk+11 )

6: θk+1 = θk − ηmk+1 � sk+17: END

Eine weiter Veränderung von Adam erhält man indem man den Anteil des Momentum Optimierers durchden von Nesterov ersetzt. Diese nennt sich dann Nadam („Nesterovs Adaptive Moment Estimation“):

Algorithm 8 Nadam1: Initialisiere m0 = 0, s0 = 0, θ0, β1, β22: for k = 0; k ≤ n; k++ do3: mk+1 = β1mk + (1− β1)∇θkJ(θk − β1mk)4: sk+1 = β2sk + (1− β2)∇θkJ(θk)⊗∇θkJ(θk)5: mk+1 = mk+1/(1− βk+11 )

6: sk+1 = sk+1/(1− βk+12 )

7: θk+1 = θk − ηmk+1 �√sk+1 + ε

8: END

4 Zusammenfassung

Alle bisher besprochenen Optimierungstechniken beruhen lediglich auf den partiellen Ableitungen ersterOrdnung (Jacobians). Die Literatur zu Optimierungsverfahren enthält faszinierende Algorithmen, die mitden partiellen Ableitungen zweiter Ordnung (Hessians) arbeiten. Leider lassen sich diese Algorithmen sehrschwer auf neuronale Netze anwenden, da es pro Ausgabe n2 partielle Ableitungen zweiten Grades gibt(wobei n die Anzahl der Parameter ist). Im Gegensatz dazu gibt es sonst nur n partielle Ableitungen erstenGrades pro Ausgabe. Da Neuronale Netze normalerweise tausende Parameter enthalten, wird die Spei-chergröße dieser Algorithmen zu groß. Selbst wenn die Berechnung möglich ist, ist sie in der praktischenAnwendung deutlich zu langsam.

4.1 Wahl des Optimierers

In welcher Situation sollte man nun welchen der vorgestellten Optimierer wählen?Eine generelle Aussage dazu ist schwierig, doch lässt sich im Allgemein zur Tendenz der adaptiven Algo-rithmen raten. Während wir gesehen haben, dass AdaGrad die Lernrate noch zu schnell herunterskaliert,



bekommt man schon ab RMSProp gerade für dünn besetzte Dimensionen relativ gute Ergebnisse, welchemittels Adam nochmal verbessert werden kann [RS17].Auch wenn es in vielen Bereichen reicht das normale Gradientenverfahren zu benutzen, hilft alleine dasHinzufügen des Moments die Suche nach dem Minimum signifikant zu beschleunigen.

4.2 Visualisierung

Im Folgenden betrachten wir zwei Grafiken, die das Verhalten der verschiedenen Optimierer in unterschied-lichen Szenarios darstellen sollen. Anzumerken ist noch, dass im Vortrag der AdaDelta Algorithmus nichtvorgestellt wurde. Dieser ist ein zum RMSProp sehr verwandter Algorithmus, der ebenfalls die Problemedes AdaGrad verbessert.

(a) SGD an steilem Hang (b) SGD um Sattelpunkt

Abbildung 3: SGD Vergleich [RS17]



Literatur

Sebastian Ruder [RS17] (2017): An overview of gradient descent optimization algorithms

Diederik P. Kingma, Jimmy Lei Ba [KD17] (2017): ADAM: A METHOD FOR STOCHASTIC OPTIMIZATION

Aurélien Géron [GA18] (2018): Praxiseinstieg Machine Learning mit Scikit-Learn und TensorFlow

Sebastian Ruder (2017): An overview of gradient descent optimization algorithms (Abbildung 1)Aurélien Géron (2018): Praxiseinstieg Machine Learning mit Scikit-Learn und TensorFlow (Abbildung 2)Sebastian Ruder (2017): An overview of gradient descent optimization algorithms (Abbildung 3)

Documents

Numerische Optimierung für Deep Learning Algorithmen...die beste Wahl darstellen. Die Idee von adaptiven Algorithmen, die wir im Weiteren vorstellen, ist folgende: Man passt die Lernrate