Wie man das Tal zähmt - Hessisch-freie Hacks zur Optimierung großer #NeuralNetworks

Nehmen wir an, Sie haben die Gabe des Fliegens (oder Sie fahren mit einem Hubschrauber). Sie sind auch ein Spion (wie in James Bond-Filmen). Sie erhalten die Topografie eines langen, schmalen Tals, wie im Bild gezeigt, und Sie erhalten einen Treffpunkt, um einen potenziellen Adjutanten zu treffen, der über Informationen verfügt, die für Ihr Ziel hilfreich sind. Die einzigen Informationen, die Sie über den Treffpunkt haben, lauten wie folgt:

"Triff mich auf der niedrigsten Koordinate dieses langen Tals in 4 Stunden."

Wie gehen Sie vor, um den niedrigsten Koordinatenpunkt zu finden? Mehr noch, wie wollen Sie es in einem festgelegten Zeitraum finden?

Nun, für komplexe neuronale Netze mit sehr großen Parametern ist die Fehlerfläche des neuronalen Netzes dem langen engen Tal der Arten sehr ähnlich. Das Auffinden eines „Minimums“ im Tal kann recht schwierig sein, wenn die Topographie solche pathologischen Krümmungen aufweist.

Hinweis: Es gibt viele Beiträge zu Optimierungshacks zweiter Ordnung für Neural Network. Der Grund, warum ich mich dazu entschlossen habe, noch einmal darüber zu schreiben, ist, dass das meiste davon ohne viel Erklärung direkt in die komplexe Mathematik springt.
Stattdessen habe ich versucht, Mathe so kurz wie möglich zu erklären und hauptsächlich auf detaillierte Quellen zu verweisen, um zu erfahren, ob Sie nicht in dem speziellen Gebiet Mathe ausgebildet sind.
Dieser Beitrag wird deshalb etwas länger dauern.

In den letzten Beiträgen haben wir beim Backpropagieren Gradient-Descent-Algorithmen verwendet, um die Fehler zu minimieren. Sie finden die Techniken im Beitrag "Backpropagation - Wie neuronale Netze komplexe Verhaltensweisen erlernen".

Einschränkungen des Gefälleverlaufs

An einem Gradientenabstiegsalgorithmus (oder genauer gesagt Stochastic Gradient Descent (SGD)) ist nichts grundlegend Falsches. In der Tat haben wir bewiesen, dass es für einige der Feed Forward-Beispiele, die wir in der Vergangenheit verwendet haben, recht effizient ist. Das Problem von SGD entsteht, wenn wir "tiefe" neuronale Netze haben, die mehr als eine verborgene Schicht haben. Besonders wenn das Netzwerk ziemlich groß ist.

Hier einige Abbildungen einer nicht monotonen Fehleroberfläche eines Deep Neural Network, um sich ein Bild zu machen.

Fehleroberfläche - 2Fehleroberfläche - 2

Beachten Sie, dass die Abbildung viele Minima und Maxima enthält. Lassen Sie uns kurz auf die Gewichtsaktualisierung in SGD eingehen

SGD Gewichtsupdates

Das Problem bei der Verwendung von SGD für die Abbildungen ist wie folgt:

  • Da SGD Optimierungsverfahren erster Ordnung verwendet, wird davon ausgegangen, dass die Fehlerfläche immer wie eine Ebene aussieht (in Abstiegsrichtung) und die Krümmung nicht berücksichtigt.
  • Wenn eine quadratische Krümmung vorliegt, wenden wir einige Tricks an, um sicherzustellen, dass SGD nicht einfach von der Oberfläche abprallt, wie in der Gewichtsaktualisierungsgleichung gezeigt.
  • Wir steuern den Impulswert mit einem vorgegebenen Alpha und steuern die Geschwindigkeit durch Anwenden einer Lernrate epsilon.
  • Das Alpha und das Epsilon puffern die Geschwindigkeit und Richtung von SGD und verlangsamen die Optimierung, bis wir konvergieren. Wir können diese Hyperparameter nur so einstellen, dass ein ausgewogenes Verhältnis von Geschwindigkeit und Wirksamkeit von SGD erreicht wird. Aber sie verlangsamen uns trotzdem.
  • In großen Netzwerken mit pathologischen Krümmungen (siehe Abbildung) ist die Optimierung dieser Hyperparameter eine große Herausforderung.
  • Der Fehler in SGD kann plötzlich ansteigen, wenn Sie sich in Richtung des Gefälles bewegen, wenn Sie ein langes, schmales Tal durchqueren. Tatsächlich kann SGD fast zum Stillstand kommen, bevor es überhaupt Fortschritte machen kann.

Wir brauchen eine bessere Methode, um mit großen oder tiefen neuronalen Netzen zu arbeiten.

Optimierung zweiter Ordnung zur Rettung

SGD ist ein Optimierungsproblem erster Ordnung. Methoden erster Ordnung sind Methoden mit linearen lokalen Kurven. Dabei nehmen wir an, dass wir lineare Näherungen anwenden können, um Gleichungen zu lösen. Einige Beispiele für Methoden erster Ordnung sind:

  • Gradientenabstieg
  • Subgradient
  • Gradient konjugieren
  • Zufälliger Koordinatenabstieg

Es gibt Methoden zweiter Ordnung, die die Konvexität oder Krümmung der Gleichung berücksichtigen und quadratische Approximationen durchführen. Quadratische Approximationen sind eine Erweiterung der linearen Approximationen, bieten jedoch eine zusätzliche Variable, mit der eine quadratische Fläche erstellt werden kann, mit der ein Punkt auf der Fehlerfläche behandelt werden kann.

Der Hauptunterschied zwischen den Annäherungen erster und zweiter Ordnung besteht darin, dass die lineare Annäherung eine "Ebene" liefert, die tangential zu einem Punkt auf einer Fehlerfläche ist, während die Annäherung zweiter Ordnung eine quadratische Fläche liefert, die die Krümmung von umgibt die Fehleroberfläche.

Wenn Sie mit quadratischen Näherungen noch nicht vertraut sind, empfehlen wir Ihnen, diese Vorlesung der Khan Academy über quadratische Näherungen zu lesen.

Der Vorteil einer Methode zweiter Ordnung besteht darin, dass die Krümmung der Fehlerfläche nicht ignoriert wird. Aufgrund der Tatsache, dass die Krümmung berücksichtigt wird, wird angenommen, dass Methoden zweiter Ordnung eine bessere schrittweise Leistung aufweisen.

  • Der vollständige Schrittsprung einer Methode zweiter Ordnung zeigt direkt auf die Minima einer Krümmung (im Gegensatz zu Methoden erster Ordnung, die mehrere Schritte mit mehreren Gradientenberechnungen in jedem Schritt erfordern).
  • Da eine Methode zweiter Ordnung in einem Schritt auf die Minima einer quadratischen Krümmung hinweist, müssen Sie sich nur darum kümmern, wie gut die Kurve tatsächlich die Fehleroberfläche umschließt. Dies ist eine genug gute Heuristik, um damit umzugehen.
  • Das Arbeiten mit den Hyperparametern unter Berücksichtigung der Heuristik wird sehr effizient.

Im Folgenden sind einige Methoden zweiter Ordnung aufgeführt

  • Newtons Methode
  • Quasi-Newton, Gauß-Newton
  • BFGS, (L) BFGS

Werfen wir einen Blick auf die Newton-Methode, die eine Basismethode ist und im Vergleich zu anderen Methoden etwas intuitiver ist.

Yo! Newton, was ist deine Methode?

Die Newton'sche Methode, auch Newton-Raphson-Methode genannt, ist eine iterative Methodennäherungstechnik an den Wurzeln einer reellen Wertfunktion. Dies ist eine der Basismethoden, die bei konvexen Optimierungsproblemen zweiter Ordnung zur Approximation von Funktionen verwendet wird.

Lassen Sie uns zunächst Newtons Methode mit first-derivate einer Funktion betrachten.

Nehmen wir an, wir haben eine Funktion f (x) = 0 und wir haben eine Anfangslösung x_0, die wir für suboptimal halten. Dann schlägt Newtons Methode Folgendes vor

  1. Finden Sie die Gleichung für die Tangente bei x_0
  2. Suchen Sie den Punkt, an dem die Tangente die x-Achse schneidet, und nennen Sie diesen neuen Punkt x_1.
  3. Finden Sie die Projektion von x_1 auf die Funktion f (x) = 0, die sich auch bei x_1 befindet.
  4. Wiederholen Sie den Vorgang ab Schritt 1, indem Sie x_0 durch x_1 ersetzen.

Wirklich so einfach. Die Einschränkung ist, dass die Methode Ihnen nicht sagt, wann Sie anhalten sollen. Deshalb fügen wir einen fünften Schritt wie folgt hinzu:

5. Wenn x_n (der aktuelle Wert von x) kleiner oder gleich einem Schwellenwert ist, stoppen wir.

Hier ist das Bild, das das Obige zeigt:

Ermitteln des optimalen Wertes von X nach der Newton'schen Methode.

Hier ist eine Animation, die dasselbe zeigt:

Animationsguthaben

Polynom 1. Grades, eindimensional:

Hier ist die Mathematik für eine Funktion, die ein Polynom ersten Grades mit einer Dimension ist.

Polynom 2. Grades, eindimensional

Jetzt können wir an der Newton-Approximation für eine Polynomfunktion zweiten Grades (Optimierungen zweiter Ordnung) mit einer Dimension arbeiten (bevor wir zu mehreren Dimensionen gelangen). Ein Polynom zweiten Grades ist quadratischer Natur und würde eine Ableitung zweiter Ordnung benötigen, um damit zu arbeiten. Um an der zweiten Ableitung einer Funktion zu arbeiten, verwenden wir die Taylor-Näherung wie folgt:

Polynom 2. Grades, mehrdimensional

Angenommen, wir arbeiten an einem Polynom zweiten Grades mit mehreren Dimensionen, dann arbeiten wir mit demselben Newtonschen Ansatz wie oben, ersetzen jedoch die ersten Ableitungen durch einen Gradienten und die zweiten Ableitungen durch einen Hessischen wie folgt:

Eine Hessische Matrix ist eine quadratische Matrix aus partiellen Ableitungen zweiter Ordnung eines Skalars, die die lokale Krümmung einer mehrvariablen Funktion beschreibt.

Insbesondere im Falle eines Neuronalen Netzes ist das Hessische eine quadratische Matrix mit der Anzahl der Zeilen und Spalten, die der Gesamtanzahl der Parameter im Neuronalen Netz entspricht.

Das Hessische für Neuronales Netz sieht folgendermaßen aus:

Hessische Matrix eines Neuronalen Netzes

Warum ist der hessische Ansatz theoretisch besser als der SGD?

Nun ist die Optimierung zweiter Ordnung unter Verwendung der Newton-Methode zum iterativen Finden des optimalen 'x' ein geschickter Hack zum Optimieren der Fehleroberfläche, da im Gegensatz zu SGD, bei dem Sie eine Ebene am Punkt x_0 anpassen und dann den schrittweisen Sprung bestimmen, Bei der Optimierung zweiter Ordnung finden wir eine eng anliegende quadratische Kurve bei x_0 und finden direkt die Minima der Krümmung. Dies ist äußerst effizient und schnell.

Aber !!! Können Sie sich nun empirisch vorstellen, einen Hessischen Wert für ein Netzwerk mit Millionen von Parametern zu berechnen? Natürlich wird es sehr ineffizient, da der Speicher- und Rechenaufwand für die Berechnung des Hessischen ebenfalls quadratisch ist. Also, obwohl theoretisch, ist das fantastisch, in der Praxis saugt es.

Wir brauchen einen Hack für den Hack! Und die Antwort scheint in Conjugate Gradients zu liegen.

Gradienten konjugieren, cleverer Trick.

Tatsächlich gibt es mehrere quadratische Approximationsmethoden für eine konvexe Funktion. Die Conjugate Gradient Method funktioniert jedoch sehr gut für eine symmetrische Matrix, die positiv-definit ist. Tatsächlich sollen konjugierte Verläufe mit sehr großen, spärlichen Systemen arbeiten.

Beachten Sie, dass ein Hessischer Wert um die Diagonale symmetrisch ist, die Parameter eines Neuronalen Netzwerks in der Regel spärlich sind und der Hessische Wert eines Neuronalen Netzwerks positiv-definit ist (dh nur positive Eigenwerte). Junge, haben wir Glück?

Wenn Sie eine gründliche Einführung in die Conjugate-Gradient-Methode benötigen, lesen Sie den Artikel „Eine Einführung in die Conjugate-Gradient-Methode ohne die quälenden Schmerzen“ von Jonathan Richard Shewchuk. Ich finde das ziemlich gründlich und nützlich. Ich würde vorschlagen, dass Sie die Arbeit in Ihrer Freizeit studieren, um ein detailliertes Verständnis von Conjugate Gradients zu erhalten.

Der Conjugate Gradient (CG) lässt sich am einfachsten wie folgt erklären:

  • Der CG-Abstieg ist auf jede quadratische Form anwendbar.
  • CG verwendet einen Schrittgrößen-Alpha-Wert, der SGD ähnelt, aber anstelle eines festen Alphas wird das Alpha über einen Zeilensuchalgorithmus ermittelt.
  • CG benötigt auch ein Beta, einen skalaren Wert, mit dessen Hilfe die nächste Richtung ermittelt werden kann, die mit der ersten Richtung konjugiert ist.

Sie können den größten Teil der haarigen Mathematik überprüfen, um zu einer CG-Gleichung zu gelangen. Ich werde direkt zu dem Abschnitt des Algorithmus des konjugierten Gradienten springen:

Zum Lösen einer Gleichung Ax = b können wir den folgenden Algorithmus verwenden:

Bildnachweis
  • Hier ist r_k der Restwert,
  • p_k ist der konjugierte Vektor und
  • x_k + 1 wird iterativ mit dem vorherigen Wert x_k und dem Punktprodukt der Schrittgröße alpha_k und des konjugierten Vektors p_k aktualisiert.

Da wir wissen, wie der Konjugationsgradient berechnet wird, schauen wir uns die hessische Optimierungstechnik an.

Hessischer Optimierungsalgorithmus

Nachdem wir den CG-Algorithmus verstanden haben, schauen wir uns den letzten cleveren Hack an, mit dem wir uns vom Hessischen befreien können.

ZITATION: Hessische Optimierung ist eine Technik, die von James Marten an der Universität von Toronto in einem Artikel mit dem Titel "Deep-Learning Via Hessian Free Optimization" für Neuronale Netze übernommen wurde.

Beginnen wir mit einer Taylor-Erweiterung zweiter Ordnung einer Funktion:

Hier müssen wir das beste delta_x finden und dann zu x + delta_x gehen und weiter iterieren, bis wir konvergieren. Mit anderen Worten, die Schritte zur hessischen Optimierung lauten wie folgt:

Algorithmus:

  1. Beginnen Sie mit i = 0 und iterieren Sie
  2. Sei x_i ein anfängliches suboptimales x_0, das zufällig ausgewählt wird.
  3. Bei der oben gezeigten Taylor-Erweiterung wird zum aktuellen Zeitpunkt x_n der Gradient von f (x_n) und der Hessische von f (x_n) berechnet.
  4. Berechnen Sie unter Berücksichtigung der Taylor-Erweiterung das nächste x_n + 1 (das nichts anderes als delta_x ist) unter Verwendung des Conjugate Gradient-Algorithmus.
  5. Wiederholen Sie die Schritte 2 bis 4, bis das aktuelle x_n konvergiert.

Die entscheidende Erkenntnis: Beachten Sie, dass im Gegensatz zur Newton-Methode, bei der ein Hessischer Algorithmus zur Berechnung von x_n + 1 benötigt wird, der Hessische Algorithmus nicht zur Berechnung von x_n + 1 benötigt wird. Stattdessen verwenden wir den Konjugationsgradienten.

Clever Hack: Da das Hessische zusammen mit einem Vektor x_n verwendet wird, brauchen wir nur eine Annäherung des Hessischen zusammen mit dem Vektor und wir brauchen NICHT das genaue Hessische. Die Approximation des Hessischen mit einem Vektor ist weitaus schneller als die Berechnung des Hessischen. Überprüfen Sie die folgenden Überlegungen.

Schauen Sie sich das Hessische noch einmal an:

Hessische Matrix eines Neuronalen Netzes

Hier enthält die i-te Zeile teilweise Ableitungen des Formulars

Wobei "i" der Zeilenindex und "j" der Spaltenindex ist. Daher das Skalarprodukt einer Hessischen Matrix und eines Vektors:

Das Obige gibt die Richtungsableitung von "e" in Bezug auf "w" in der Richtung "v" an.

Mit Hilfe endlicher Differenzen können wir das Obige wie folgt optimieren:

Eine ausführliche Erklärung und Technik für die schnelle Multiplikation eines Hessischen mit einem Vektor finden Sie in der Veröffentlichung „Fast Exact Multiplication of the Hessian“ von Barak A. Pearlmutter von Siemens Corporate Research.

Mit dieser Einsicht können wir die Berechnung eines Hessischen vollständig überspringen und uns nur auf die Annäherung des Hessischen an eine Vektormultiplikation konzentrieren, was die Berechnungs- und Speicherkapazität enorm reduziert.

Überprüfen Sie die folgende Abbildung, um die Auswirkungen der Optimierungstechnik zu verstehen.

Beachten Sie, dass Sie sich bei diesem Ansatz, anstatt wie bei SGD von der Bergseite abzuprallen, tatsächlich entlang des Talabhangs bewegen können, bevor Sie ein Minimum in der Krümmung finden. Dies ist sehr effektiv für sehr große neuronale Netze oder tiefe neuronale Netze mit Millionen von Parametern.

Anscheinend ist es nicht einfach, ein Spion zu sein ...