Überblick über Gradientenmethoden in mathematischen Optimierungsproblemen

Published on June 11, 2018

Überblick über Gradientenmethoden in mathematischen Optimierungsproblemen

Vorwort


In diesem Artikel werden Methoden zur Lösung mathematischer Optimierungsprobleme basierend auf der Verwendung der Gradientenfunktion behandelt. Das Hauptziel ist es, in dem Artikel alle wichtigen Ideen zu sammeln, die in irgendeiner Weise mit dieser Methode und ihren verschiedenen Modifikationen zusammenhängen.





UPD . In den Kommentaren heißt es, dass Formeln in einigen Browsern und in der Mobilanwendung nicht angezeigt werden. Leider weiß ich nicht, wie ich damit umgehen soll. Ich kann nur sagen, dass ich die "Inline" - und "Display" -Makros des Habrav-Editors verwendet habe. Wenn Sie plötzlich wissen, wie Sie das Problem beheben können, schreiben Sie bitte in die Kommentare.

Anmerkung des Autors


Zum Zeitpunkt des Schreibens verteidigte ich meine These, deren Aufgabe ein tiefes Verständnis der theoretischen Grundmethoden der mathematischen Optimierung erforderte. Trotzdem sind meine Augen (von allen anderen) immer noch durch gruselige lange Formeln verwischt, weshalb ich viel Zeit damit verbracht habe, die Schlüsselideen zu isolieren, die verschiedene Variationen von Verlaufsmethoden charakterisieren würden. Mein persönliches Ziel ist es, einen Artikel zu schreiben, der die minimale Menge an Informationen enthält, die für ein weniger detailliertes Verständnis des Themas erforderlich sind. Aber sei vorbereitet, auf Formeln kann man sowieso nicht verzichten.

Problemstellung


Bevor Sie eine Methode beschreiben, sollten Sie zunächst die Aufgabe beschreiben, nämlich: $ \ mathcal {K} $ und Funktion $ f: \ mathcal {K} \ rightarrow \ mathbb {R} $müssen Punkt finden $ x ^ * \ in \ mathcal {K} $so dass $ f (x) \ geq f (x ^ *) $ für alle $ x \ in \ mathcal {K} $"Was normalerweise so geschrieben wird

$ f (x) \ rightarrow \ min_ {x \ in \ mathcal {K}}. $


In der Theorie wird das normalerweise angenommen$ f $ - differenzierbare und konvexe Funktion und $ \ mathcal {K} $ - konvexe Menge (und noch besser, wenn überhaupt) $ \ mathcal {K} = \ mathbb {R} ^ n $Dies ermöglicht es uns, einige Garantien für den Erfolg der Anwendung des Gradientenabfalls zu geben. In der Praxis wird der Gradientenabstieg auch dann erfolgreich angewendet, wenn die Aufgabe keine der oben genannten Eigenschaften aufweist (das Beispiel befindet sich weiter unten im Artikel).

Ein bisschen Mathe


Angenommen, wir müssen vorerst nur ein Minimum an eindimensionaler Funktion finden.

$ f (x) \ rightarrow \ min_ {x \ in \ mathbb {R}}. $


Auch im 17. Jahrhundert von Pierre Fermat wurde Kriterien geprägt , die einfache Optimierungsproblem lösen lassen, nämlich ECLI$ x ^ * $ - Mindestpunktzahl $ f ^ * $dann

$ f '(x ^ *) = 0 $


wo $ f '$ - Ableitung $ f $. Dieses Kriterium basiert auf einer linearen Approximation.

$ f (x) \ ungefähr f (x ^ *) + f '(x ^ *) (xx ^ *). $


Je näher $ x $ zu $ x ^ * $genauer diese Annäherung. Im rechten Teil - ein Ausdruck, der$ f '(x ^ *) \ neq 0 $ vielleicht mehr $ f (x ^ *) $und weniger - das ist das Wesentliche des Kriteriums. Im mehrdimensionalen Fall ähnlich aus der linearen Approximation$ f (x) \ ungefähr f (x ^ *) + \ nabla f (x ^ *) ^ T (xx ^ *) $ (im folgenden $ x ^ ty = \ sum_ {i = 1} ^ nx_iy_i $ - Standard-Skalarprodukt, die Form des Datensatzes ergibt sich aus der Tatsache, dass das Skalarprodukt das gleiche ist wie das Matrixprodukt der Vektorzeile (durch den Spaltenvektor), das wir als Kriterium erhalten

$ \ nabla f (x ^ *) = 0.  $


Größe $ \ nabla f (x ^ *) $- gradient Funktion$ f $ auf den Punkt $ x ^ * $. Die Gleichheit des Gradienten mit Null bedeutet auch die Gleichheit aller partiellen Ableitungen mit Null. Im mehrdimensionalen Fall können Sie dieses Kriterium also einfach erhalten, indem Sie das eindimensionale Kriterium für jede Variable konsistent separat anwenden.

Es ist erwähnenswert, dass diese Bedingungen notwendig, aber nicht ausreichend sind. Das einfachste Beispiel ist 0 für$ f (x) = x ^ 2 $ und $ f (x) = x ^ 3 $


Dieses Kriterium reicht bei einer konvexen Funktion weitgehend aus, so dass für konvexe Funktionen viele Ergebnisse erzielt wurden.

Quadratische Funktionen


Quadratische Funktionen in $ \ mathbb {R} ^ n $ Ist eine Ansichtsfunktion

$ f (x) = f (x_1, x_2, \ ldots, x_n) = \ frac {1} {2} \ sum_ {i, j = 1} ^ na_ {ij} x_ix_j- \ sum_ {i = 1} ^ n b_ix_i + c $


Um Platz zu sparen (und noch weniger, um mit Indizes herumzuspielen), wird diese Funktion normalerweise in Matrixform geschrieben:

$ f (x) = \ frac {1} {2} x ^ TAx-b ^ Tx + c, $


wo $ x = (x_1, \ ldots, x_n) ^ T $, $ b = (b_1, \ ldots, b_n) ^ T $, $ A $ - die Matrix, die an der Kreuzung $ i $ Streicher und $ j $ Spaltenwert ist
$ \ frac {1} {2} (a_ {ij} + a_ {ji}) $ ($ A $Gleichzeitig fällt es symmetrisch aus - das ist wichtig). Weiter. Wenn ich eine quadratische Funktion erwähne, werde ich die obige Funktion haben.

Warum spreche ich darüber? Tatsache ist, dass quadratische Funktionen aus zwei Gründen für die Optimierung wichtig sind:

  1. Sie finden sich beispielsweise auch in der Praxis, wenn eine lineare Regression nach der Methode der kleinsten Quadrate konstruiert wird
  2. Der Gradient einer quadratischen Funktion ist eine lineare Funktion, insbesondere für die obige Funktion

    $ \ frac {\ partial} {\ partial x_i} f (x_1, x_2, \ ldots, x_n) = a_ {ii} x_i + \ sum_ {j \ neq i} \ frac {1} {2} (a_ {ij } + a_ {ji}) x_j -b_i, $


    Oder in Matrixform

    $ \ nabla f (x) = Ax-b, $


    Also das System $ \ nabla f (x) = 0 $- lineares System. Das System, einfacher als linear, existiert einfach nicht. Die Idee, zu der ich gekommen bin, ist die Optimierung einer quadratischen Funktion - die einfachste Klasse von Optimierungsproblemen . Auf der anderen Seite die Tatsache, dass$ \ nabla f (x ^ *) = 0 $- Die notwendigen Mindestbedingungen ermöglichen es, lineare Systeme durch Optimierungsprobleme zu lösen. Wenig später werde ich versuchen, Sie davon zu überzeugen, dass es Sinn macht.

Nützliche Verlaufseigenschaften


Nun, wir scheinen herausgefunden zu haben, dass, wenn eine Funktion differenzierbar ist (sie hat Ableitungen in allen Variablen), der Gradient am minimalen Punkt Null sein sollte. Aber enthält der Gradient nützliche Informationen für den Fall, dass er nicht Null ist?

Versuchen wir zunächst, ein einfacheres Problem zu lösen: Es wird ein Punkt angegeben$ x $Punkt finden $ \ bar {x} $ so dass $ f (\ bar {x}) <f (x) $. Nehmen wir einen Punkt neben$ x $wieder mit linearer Näherung $ f (\ bar {x}) \ ungefähr f (x) + \ nabla f (x) ^ T (\ bar {x} -x) $. Wenn du nimmst$ \ bar {x} = x- \ alpha \ nabla f (x) $, $ \ alpha> 0 $ dann bekommen wir

$ f (\ bar {x}) \ ungefähr f (x) - \ alpha \ | \ nabla f (x) \ | ^ 2 <f (x).  $


Ebenso, wenn $ \ alpha <0 $dann $ f (\ bar {x}) $ wird mehr sein $ f (x) $ (im folgenden $ || x || = \ sqrt {x_1 ^ 2 + x_2 ^ 2 + \ ldots + x_n ^ 2} ~ $). Da wir die Näherung verwendet haben, gelten diese Überlegungen wieder nur für kleine$ \ alpha $. Zusammenfassend gesagt, wenn$ \ nabla f (x) \ neq 0 $Der Gradient gibt die Richtung des größten lokalen Anstiegs der Funktion an .

Hier sind zwei Beispiele für zweidimensionale Funktionen. Solche Bilder sind häufig in Demonstrationen von Gefälle zu sehen. Farbige Linien - die sogenannten ebenen Linien - sind eine Menge von Punkten, für die die Funktion feste Werte annimmt, in meinem Fall sind dies Kreise und Ellipsen. Ich habe die blauen Linien des Levels mit einem niedrigeren Wert markiert, rot - mit einem höheren.



Beachten Sie dies für eine Fläche, die durch eine Typgleichung gegeben ist$ f (x) = c $, $ \ nabla f (x) $Legt die Normale (gemeinsam - senkrecht) zu dieser Fläche fest. Beachten Sie auch, dass der Verlauf zwar in Richtung der größten Zunahme der Funktion zeigt, es jedoch keine Garantie dafür gibt, dass Sie ein Minimum in der Richtung finden, die dem Verlauf entgegengesetzt ist (z. B. das linke Bild).

Gefälle


Vor der grundlegenden Methode des Gefälleabstiegs gab es nur einen kleinen Schritt: Wir haben aus dem Punkt gelernt $ x $ einen Punkt bekommen $ \ bar {x} $ mit einem kleineren Funktionswert $ f $. Was hindert uns daran, dies mehrmals zu wiederholen? Im Wesentlichen handelt es sich hierbei um einen Gradientenabstieg: Erstellen einer Sequenz

$ x_ {k + 1} = x_k- \ alpha_k \ nabla f (x_k).  $


Größe $ \ alpha_k $genannt die Schrittweite (beim maschinellen Lernen - die Lerngeschwindigkeit ). Ein paar Worte zur Wahl$ \ alpha_k $wenn $ \ alpha_k $- sehr klein, die Sequenz ändert sich langsam, was den Algorithmus nicht sehr effektiv macht; wenn$ \ alpha_k $Sehr groß, die lineare Approximation wird schlecht und möglicherweise sogar falsch. In der Praxis wird die Schrittweite häufig empirisch gewählt, theoretisch wird üblicherweise der Lipschitz-Gradient angenommen, nämlich wenn

$ \ | \ nabla f (x) - \ nabla f (y) \ | \ leq L \ | xy \ |  $


für alle $ x, y $dann $ \ alpha_k <\ frac {2} {L} $ garantiert eine Abnahme $ f (x_k) $.

Analyse für quadratische Funktionen


Wenn $ A $ - symmetrische reversible Matrix, $ Ax ^ * = b $, dann für eine quadratische Funktion $ f (x) = \ frac {1} {2} x ^ TAx-b ^ Tx + c $ der Punkt $ x ^ * $ist ein Minimum ( UPD ., sofern dieses Minimum überhaupt existiert -$ f $ nicht annähernd $ - \ infty $ Werte nur wenn $ A $ positiv definitiv), und für die Gradientenabstiegsmethode können wir folgendes erhalten

$ x_ {k + 1} -x ^ * = x_k- \ alpha_k \ nabla f (x_k) -x ^ * = x_k- \ alpha_k (Ax_k-b) -x ^ * = $


$ (x_k-x ^ *) - \ alpha_kA (x_k-x ^ *) = (I- \ alpha_kA) (x_k-x ^ *), $


wo $ I $ - Einheitsmatrix, d.h. $ Ix = x $ für alle $ x $. Wenn$ \ alpha_k \ equiv \ alpha $es wird klappen

$ \ | x_ {k} -x ^ * \ | = \ | (I- \ alpha A) ^ k (x_0-x ^ *) \ | \ leq \ | I- \ alpha A \ | ^ k \ | x_0 -x ^ * \ |.  $


Der Ausdruck auf der linken Seite ist der Abstand von der in Schritt erhaltenen Näherung $ k $ Gefälle bis zum kleinsten Punkt rechts - der Ausdruck $ \ lambda ^ k \ beta $was gegen Null konvergiert, wenn $ | \ lambda | <1 $ (Bedingung, die ich geschrieben habe $ \ alpha $Dies ist im vorherigen Absatz garantiert. Diese Basisschätzung stellt sicher, dass der Gradientenabfall konvergiert.

Gradient Descent Modifikationen


Jetzt möchte ich Ihnen ein wenig über häufig verwendete Änderungen des Gefälleverlaufs erzählen, vor allem die sogenannten

Inertiale oder beschleunigte Gradientenmethoden


Alle Methoden dieser Klasse werden wie folgt ausgedrückt.

$ x_ {k + 1} = x_k- \ alpha_k \ nabla f (x_k) + \ beta_k (x_k-x_ {k-1}).  $


Der letzte Term kennzeichnet genau diese „Trägheit“. Der Algorithmus versucht bei jedem Schritt, sich gegen den Gradienten zu bewegen, aber gleichzeitig bewegt er sich durch Trägheit teilweise in dieselbe Richtung wie in der vorherigen Iteration. Solche Methoden haben zwei wichtige Eigenschaften:

  1. Sie erschweren den üblichen Gradientenabstieg praktisch nicht rechnerisch.
  2. Mit vorsichtiger Auswahl $ \ alpha_k, \ beta_k $ Solche Methoden sind um eine Größenordnung schneller als ein gewöhnlicher Gradientenabstieg, selbst bei einem optimal ausgewählten Schritt.

Eine der ersten Methoden dieser Art tauchte Mitte des 20. Jahrhunderts auf und wurde als Heavy-Ball-Methode bezeichnet , die die Art der Trägheit der Methode verdeutlichte: in dieser Methode$ \ alpha_k, \ beta_k $ hängen Sie nicht von ab $ k $und sorgfältig ausgewählt in Abhängigkeit von der Zielfunktion. Es ist erwähnenswert, dass$ \ alpha_k $ vielleicht was auch immer $ \ beta_k $- normalerweise nur etwas weniger als eins .

Die Heavy-Ball-Methode ist die einfachste Trägheitsmethode, aber nicht die erste. In diesem Fall ist meiner Meinung nach die allererste Methode sehr wichtig, um das Wesen dieser Methoden zu verstehen.

Chebyshev-Methode


Ja, ja, die erste Methode dieser Art wurde von Chebyshev erfunden, um lineare Gleichungssysteme zu lösen. Zu einem bestimmten Zeitpunkt der Analyse des Gradientenabfalls wurde die folgende Gleichheit erhalten

$ x_ {k + 1} -x ^ * = (I- \ alpha_k A) (x_k-x ^ *) = \ ldots = $


$ (I- \ alpha_kA) (I- \ alpha_ {k-1} A) \ ldots (I- \ alpha_1A) (x_0-x ^ *) = P_k (A) (x_0-x ^ *), $


wo $ P_k $ - ein gewisses Polynom $ k $. Warum nicht versuchen, aufzuheben$ \ alpha_k $ so das $ P_k (a) (x_0-x ^ *) $war es kleiner Eine Bindung universeller Polynome, die am wenigsten von Null abweicht, ist das Chebyshev-Polynom. Chebyshevs Methode besteht im Wesentlichen darin, die Abstiegsparameter so zu wählen, dass$ P_k $war ein Chebyshev Polynom. Es gibt wirklich ein kleines Problem: Bei einem normalen Gefälle ist dies einfach unmöglich. Für Inertialmethoden ist dies jedoch möglich. Dies ist hauptsächlich auf die Tatsache zurückzuführen, dass Chebyshev-Polynome die Wiederholungsrelation zweiter Ordnung erfüllen

$ T_ {n + 1} (x) = 2xT_n (x) -T_ {n-1} (x), $


Daher können sie nicht für einen Gefälle-Abstieg konstruiert werden, der nur aus einem vorherigen Wert einen neuen Wert berechnet, und für Trägheit wird es möglich, weil zwei vorherige Werte verwendet werden. Es stellt sich heraus, dass die Komplexität der Berechnung$ \ alpha_k, \ beta_k $ ist nicht abhängig von $ k $noch auf die Größe des Raumes $ n $.

Conjugate Gradient Method


Eine weitere sehr interessante und wichtige Tatsache (eine Konsequenz des Hamilton-Cayley-Theorems): Für jede quadratische Matrix$ A $ Größe $ n \ times n $ es gibt ein Polynom $ P $ keine grad mehr $ n $für welche $ P (A) = 0 $. Was ist interessant? Es geht um Gleichheit.

$ x_ {k + 1} -x ^ * = P_k (A) (x_0-x ^ *).  $


Wenn wir die Schrittweite beim Gradientenabstieg so wählen könnten, dass wir dieses Nullpolynom erhalten, würde der Gradientenabstieg in einer festen Anzahl von Iterationen konvergieren, die nicht größer als die Dimension ist $ A $. Wie sich bereits herausgestellt hat - für den Gefälleabstieg können wir das nicht tun. Zum Glück für Trägheitsmethoden - wir können. Die Beschreibung und Begründung der Methode ist recht technisch, ich werde mich auf das Wesentliche beschränken: Bei jeder Iteration werden Parameter ausgewählt, die das beste Polynom ergeben, das unter Berücksichtigung aller vor dem aktuellen Schritt durchgeführten Gradientenmessungen konstruiert werden kann . Dabei

  1. Eine Iteration des Gradientenabfalls (ohne Berücksichtigung der Parameterberechnungen) enthält eine Multiplikation der Matrix mit dem Vektor und 2-3 Vektoradditionen
  2. Die Berechnung der Parameter erfordert auch 1-2 Multiplikationen der Matrix mit dem Vektor, 2-3 skalare Multiplikationen des Vektors mit dem Vektor und mehrere Additionen der Vektoren.

Die schwierigste rechnerische Methode ist die Multiplikation der Matrix mit dem Vektor, normalerweise erfolgt dies in der Zeit. $ \ mathcal {O} (n ^ 2) $Mit einer speziellen Implementierung kann dies jedoch für durchgeführt werden $ \ mathcal {O} (m) $wo $ m $ - die Anzahl der Elemente ungleich Null in $ A $. Angesichts der Konvergenz der konjugierten Gradientenmethode für nicht mehr als$ n $ Iteration erhalten wir die Gesamtkomplexität des Algorithmus $ \ mathcal {O} (nm) $das ist in allen fällen nicht schlimmer $ \ mathcal {O} (n ^ 3) $ für die Gauß- oder Cholesky-Methode, aber viel besser für den Fall $ m << n ^ 2 $das ist nicht so selten.

Die konjugierte Gradientenmethode funktioniert auch dann gut, wenn$ f $ ist keine quadratische Funktion, aber sie konvergiert nicht in einer endlichen Anzahl von Schritten und erfordert häufig geringfügige zusätzliche Modifikationen

Nesterov-Methode


Für die Communities der mathematischen Optimierung und des maschinellen Lernens ist der Nachname „Nesterov“ seit langem ein Begriff. In den 80ern des letzten Jahrhunderts hat Yu.E. Nesterov hat eine interessante Variante der Trägheitsmethode entwickelt, die die Form hat

$ x_ {k + 1} = x_k- \ alpha_k \ nabla f (x_k + \ beta_k (x_k-x_ {k-1})) + \ beta_k (x_k-x_ {k-1}), $


es wird keine komplexe Zählung vorausgesetzt $ \ alpha_k, \ beta_k $ Wie bei der konjugierten Gradientenmethode ähnelt das Gesamtverhalten der Methode der Heavy-Ball-Methode, jedoch ist ihre Konvergenz sowohl in der Theorie als auch in der Praxis in der Regel viel zuverlässiger.

Stochastischer Gradientenabstieg


Der einzige formale Unterschied zum üblichen Gefälle besteht darin, die Funktion anstelle des Gefälles zu verwenden. $ g (x, \ theta) $ so dass $ E_ \ theta g (x, \ theta) = \ nabla f (x) $ ($ E_ \ theta $ - Erwartung nach dem Zufallsprinzip $ \ theta $), so ist der stochastische Gradientenabstieg

$ x_ {k + 1} = x_k- \ alpha_kg (x_k, \ theta_k).  $


$ \ theta_k $- Dies ist ein zufälliger Parameter, den wir nicht beeinflussen, der jedoch im Durchschnitt gegen den Gradienten verstößt. Betrachten Sie als Beispiel die Funktionen

$ f (x) = \ frac {1} {2m} \ sum_ {j = 1} ^ m \ | x-y_j \ | ^ 2, ~~ \ nabla f (x) = \ frac {1} {m} \ sum_ {j = 1} ^ m (x-y_j) $


und

$ g (x, i) = x-y_i.  $


Wenn $ i $ nimmt Werte $ 1, \ lPunkte, m $ dann nur durchschnittlich gleich wahrscheinlich $ g $ Ist ein Gefälle $ f $. Dieses Beispiel zeigt Folgendes: Die Komplexität der Berechnung des Gradienten in$ m $ mal mehr als die Komplexität der Berechnung $ g $. Dies ermöglicht es, den stochastischen Gradientenabstieg gleichzeitig in durchzuführen$ m $mal mehr Iterationen. Trotz der Tatsache, dass der stochastische Gradientenabfall aufgrund einer so großen Zunahme der Anzahl von Iterationen normalerweise langsamer als gewöhnlich konvergiert, ist es möglich, die Konvergenzrate pro Zeiteinheit zu verbessern. Soweit ich weiß, ist der stochastische Gradientenabstieg derzeit die grundlegende Methode zum Erlernen der meisten neuronalen Netze, die in allen wichtigen ML-Bibliotheken implementiert ist: Tensorflow, Torch, Caffe, CNTK usw.

Es ist erwähnenswert, dass die Ideen der Trägheitsmethoden für den stochastischen Gradientenabstieg verwendet werden und in der Praxis häufig zu einer Erhöhung führen. In der Theorie wird normalerweise angenommen, dass sich die asymptotische Konvergenzrate nicht ändert, da der Hauptfehler beim stochastischen Gradientenabstieg auf Streuung beruht$ g $.

Gefälle


Diese Variante ermöglicht es Ihnen, mit nicht differenzierbaren Funktionen zu arbeiten, ich werde es genauer beschreiben. Wir müssen uns noch einmal an die lineare Approximation erinnern - Tatsache ist, dass es eine einfache Eigenschaft der Konvexität in Form eines Gradienten gibt, eine differenzierbare Funktion$ f $ genau dann konvex, wenn sie ausgeführt wird $ f (y) \ geq f (x) + \ nabla f (x) ^ T (yx) $ für alle $ x, y $ . Es zeigt sich, dass eine konvexe Funktion nicht differenzierbar sein muss, sondern für jeden Punkt$ x $ Es wird definitiv einen solchen Vektor geben $ g $das $ f (y) \ geq f (x) + g ^ T (yx) $ für alle $ y $. Ein solcher Vektor$ g $Er rief Subgradienten $ f $ auf den Punkt $ x $, die Menge aller Subgradienten in Punkten $ x $genannt subdifferential $ x $ und bezeichnen $ \ partial f (x) $(Trotz der Bezeichnung - hat nichts mit partiellen Ableitungen zu tun). Im eindimensionalen Fall$ g $ Ist eine Zahl, und die obige Eigenschaft bedeutet einfach, dass das Diagramm $ f $ liegt oberhalb der durchgehenden Geraden $ (x, f (x)) $ und einen Hang haben $ g $(siehe Bilder unten). Ich stelle fest, dass es für einen Punkt mehrere Subgradienten geben kann, sogar eine unendliche Zahl.



Das Berechnen von mindestens einem Gradienten für einen Punkt ist normalerweise nicht sehr schwierig, der Gradientenabstieg verwendet im Wesentlichen einen Gradienten anstelle eines Gradienten. Es stellt sich heraus, dass dies ausreicht: Theoretisch nimmt die Konvergenzrate ab, aber zum Beispiel in neuronalen Netzen gibt es eine nicht differenzierbare Funktion$ ReLU (x) = \ max (0, x) $ Sie nutzen es gerne, nur weil das Lernen damit schneller geht (dies ist übrigens ein Beispiel für eine nichtkonvexe undifferenzierbare Funktion, bei der (Sub-) Gradientenabstieg erfolgreich eingesetzt wird. Die Funktion selbst $ Relu $ ist konvex aber ein mehrschichtiges neuronales Netzwerk enthaltend $ Relu $nicht konvex und nicht differenzierbar). Als Beispiel für die Funktion$ f (x) = | x | $ Subdifferential ist sehr einfach

$ \ partial f (x) = \ begin {cases} 1, & x> 0, \\ -1, & x <0, \\ [-1, 1], & x = 0.  \ end {cases} $



Vielleicht ist das Letzte, was zu wissen ist, dass der Gradientenabstieg nicht mit einer konstanten Schrittgröße konvergiert . Dies ist für die obige Funktion am einfachsten zu erkennen.$ f (x) = | x | $. Sogar das Fehlen einer Ableitung an einem Punkt unterbricht die Konvergenz:

  1. Angenommen, wir haben von einem Punkt aus begonnen $ x_0 $.
  2. Gefälleabstiegsstufe:

    $ x_ {k + 1} = \ begin {cases} x_ {k} -1, & x> 0, \\ x_k + 1, & x <0, \\ ???  & x = 0.  \ end {cases} $

  3. Wenn $ x_0> 0 $In den ersten Schritten werden wir die Einheit subtrahieren, wenn $ x_0 <0 $dann hinzufügen. So oder so, irgendwann werden wir in der Pause landen$ [0, 1) $von dem wir kommen in $ [- 1, 0) $und dann springen wir zwischen zwei Punkten dieser Intervalle.

Theoretisch wird für eine Gefällestufe eine Abfolge von Schritten empfohlen

$ \ alpha_k = \ frac {1} {(k + 1) ^ c}.  $


Wo $ c $ gewöhnlich $ 1 $ oder $ \ frac {1} {2} $. In der Praxis habe ich oft die erfolgreiche Anwendung von Schritten gesehen.$ \ alpha_k = e ^ {- ck} $obwohl für solche Schritte es im Allgemeinen keine Konvergenz geben wird.

Proximale Methoden


Leider kenne ich im Zusammenhang mit der Optimierung keine gute Übersetzung für "proximal", daher nenne ich diese Methode einfach. Proximale Methoden haben sich als eine Verallgemeinerung projektiver Gradientenmethoden erwiesen. Die Idee ist sehr einfach: Wenn es eine Funktion gibt$ f $als Summe darstellbar $ f (x) = \ varphi (x) + h (x) $wo $ \ varphi $ - differenzierbare konvexe Funktion und $ h (x) $ - konvex, für die es einen speziellen proximalen Operator gibt $ prox_h (x) $ (In diesem Artikel beschränke ich mich nur auf Beispiele, die ich nicht allgemein beschreibe), dann die Eigenschaften der Konvergenz der Gradientenabnahme für $ \ varphi $ bleiben für Gefälle für $ f $, wenn nach jeder Iteration dieser Proximal-Operator für den aktuellen Punkt angewendet werden soll $ x_k $Mit anderen Worten sieht die allgemeine Form der proximalen Methode folgendermaßen aus:

$ x_ {k + 1} = prox _ {\ alpha_kh} (x_k- \ alpha_k \ nabla \ varphi (x_k)) $


Ich denke, dass es vorerst völlig unverständlich ist, warum dies notwendig sein kann, insbesondere angesichts der Tatsache, dass ich nicht erklärt habe, was ein proximaler Operator ist. Hier sind zwei Beispiele:
  1. $ h (x) $ - Anzeigefunktion einer konvexen Menge $ \ mathcal {K} $, also

    $ h (x) = \ begin {cases} 0, & x \ in \ mathcal {K}, \\ + \ infty, & x \ notin \ mathcal {K}. \\ \ end {cases} $


    In diesem Fall $ prox _ {\ alpha_kh} (x) $ - Dies ist eine Projektion von vielen $ \ mathcal {K} $das heißt, "am nächsten an $ x $ Sollwert $ \ mathcal {K} $". Daher begrenzen wir den Gradientenabstieg auf nur viele$ \ mathcal {K} $Damit können Sie Probleme mit Einschränkungen lösen. Leider kann die Berechnung der Projektion im Allgemeinen sogar noch schwieriger sein. Daher wird diese Methode normalerweise verwendet, wenn die Bedingungen einfach sind, z. B. die sogenannten Box-Bedingungen: für jede Koordinate

    $ l_i \ leq x_i \ leq r_i $


  2. $ h (x) = \ lambda \ | x \ | _1 = \ lambda \ sum_ {i = 1} ^ n | x_i | $ - $ \ ell_1 $-regelmäßigkeit. Sie ergänzen Optimierungsaufgaben im maschinellen Lernen gerne um diesen Begriff, um eine Umschulung zu vermeiden. Eine Regularisierung dieses Typs setzt auch die am wenigsten signifikanten Komponenten zurück. Für eine solche Funktion hat der proximale Operator die Form (der Ausdruck für eine Koordinate wird unten beschrieben):

    $ [prox _ {\ alpha h} (x)] _ i = \ begin {cases} x_i- \ alpha, & x_i> \ alpha, \\ x_i + \ alpha, & x_i <- \ alpha, \\ 0, & x_i \ in [- \ alpha, \ alpha], \ end {cases} $


    Das ist ziemlich einfach zu berechnen.

Fazit


Damit sind die mir bekannten Hauptvarianten der Gradientenmethode beendet. Vielleicht würde ich am Ende bemerken, dass alle diese Modifikationen (außer vielleicht die konjugierte Gradientenmethode) leicht miteinander interagieren können. Ich habe die Newtonsche Methode und die Quasi-Newtonschen Methoden (BFGS und andere) nicht speziell in diese Liste aufgenommen: Sie verwenden zwar einen Gradienten, sind jedoch komplexer, erfordern jedoch spezifische zusätzliche Berechnungen, die in der Regel rechenintensiver sind als die Berechnung des Gradienten. Sollte dieser Text dennoch beansprucht werden, werde ich gerne eine ähnliche Bewertung abgeben.

Verwendete / empfohlene Literatur


Boyd. S, L. Vanden Convex Optimization
Shewchuk JR Eine Einführung in die Conjugate Gradient Methode ohne die quälende Schmerzen
Bertsekas DP Convex Optimierungstheorie

Nesterov J. E. Methods konvexen Optimierung
Gasnikov AV Universeller Gradientenabstieg