Übersicht über Gradientenmethoden bei mathematischen Optimierungsproblemen

Vorwort

Dieser Artikel konzentriert sich auf Methoden zur Lösung mathematischer Optimierungsprobleme basierend auf der Verwendung eines Funktionsgradienten. Das Hauptziel ist es, in dem Artikel alle wichtigen Ideen zu sammeln, die irgendwie mit dieser Methode und ihren verschiedenen Modifikationen zusammenhängen.





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

Anmerkung des Autors

Zum Zeitpunkt des Schreibens verteidigte ich eine Dissertation, deren Aufgabe es erforderte, ein tiefes Verständnis für grundsätzlich theoretische Methoden der mathematischen Optimierung zu haben. Trotzdem sind meine Augen (wie alle anderen auch) immer noch von unheimlichen langen Formeln verschwommen, so dass ich viel Zeit damit verbracht habe, Schlüsselideen zu isolieren, die verschiedene Variationen von Gradientenmethoden charakterisieren würden. Mein persönliches Ziel ist es, einen Artikel zu schreiben, der die Mindestmenge an Informationen enthält, die für ein mehr oder weniger detailliertes Verständnis des Themas erforderlich sind. Aber seien Sie vorbereitet, auf Formeln kann man sowieso nicht verzichten.

Erklärung des Problems

Bevor Sie die Methode beschreiben, müssen Sie zunächst das Problem beschreiben: „Gegeben sind viele $$$\ mathcal {K}$ und Funktion $$$f: \ mathcal {K} \ rightarrow \ mathbb {R}$ müssen einen Punkt finden $$$x ^ * \ in \ mathcal {K}$ so dass $$$f (x) \ geq f (x ^ *)$ für alle $$$x \ in \ mathcal {K}$ ", Was normalerweise so geschrieben ist

$$

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

Theoretisch wird das normalerweise angenommen $$$f$ Ist eine differenzierbare und konvexe Funktion, und $$$\ mathcal {K}$ - konvexer Satz (und noch besser, wenn überhaupt $$$\ mathcal {K} = \ mathbb {R} ^ n$ ), so können wir einige Garantien für den Erfolg der Anwendung des Gradientenabfalls geben. In der Praxis wird der Gradientenabstieg auch dann erfolgreich angewendet, wenn die Aufgabe keine der oben genannten Eigenschaften aufweist (ein Beispiel weiter unten in diesem Artikel).

Ein bisschen Mathe

Nehmen wir an, wir müssen vorerst nur ein Minimum einer eindimensionalen Funktion finden

$$

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

Bereits im 17. Jahrhundert hatte Pierre Fermat ein Kriterium entwickelt, das es ermöglichte, einfache Optimierungsprobleme zu lösen, nämlich wenn $$$x ^ *$ - Mindestpunkt $$$f ^ *$ dann

$$

$$f '(x ^ *) = 0$$

wo $$$f '$ - Derivat $$$f$ . Dieses Kriterium basiert auf einer linearen Näherung.

$$

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

Näher dran $$$x$ zu $$$x ^ *$ desto genauer ist diese Annäherung. Auf der rechten Seite ist ein Ausdruck, der, wenn $$$f '(x ^ *) \ neq 0$ vielleicht mehr $$$f (x ^ *)$ weniger ist das Wesentliche des Kriteriums. Im mehrdimensionalen Fall ähnlich aus der linearen Näherung $$$f (x) \ ungefähr f (x ^ *) + \ nabla f (x ^ *) ^ T (x-x ^ *)$ (im Folgenden $$$x ^ Ty = \ sum_ {i = 1} ^ nx_iy_i$ - Standard-Skalarprodukt, die Form des Schreibens beruht auf der Tatsache, dass das Skalarprodukt das gleiche ist wie das Matrixprodukt eines Zeilenvektors durch einen Spaltenvektor), das Kriterium wird erhalten

$$

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

Wert $$$\ nabla f (x ^ *)$ - Funktionsgradient $$$f$ an der Stelle $$$x ^ *$ . Die Gleichheit des Gradienten mit Null bedeutet auch die Gleichheit aller partiellen Ableitungen mit Null. Daher kann man im mehrdimensionalen Fall dieses Kriterium erhalten, indem man das eindimensionale Kriterium für jede Variable einfach nacheinander separat anwendet.

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 ist bei einer konvexen Funktion ausreichend, vor allem deshalb konnten so viele Ergebnisse für konvexe Funktionen erzielt werden.

Quadratische Funktionen

Quadratische Funktionen in $$$\ mathbb {R} ^ n$ Ist eine Funktion der Form

$$

$$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 sich weniger um Indizes zu kümmern), 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$ Ist eine Matrix, an der an der Kreuzung $$$i$ Saiten und $$$j$ Spalte ist der Wert
$$$\ frac {1} {2} (a_ {ij} + a_ {ji})$ ( $$$A$ es stellt sich als symmetrisch heraus - das ist wichtig). Weiter. Wenn ich eine quadratische Funktion erwähne, werde ich die obige Funktion haben.

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

1. Sie treten auch in der Praxis auf, beispielsweise beim Aufbau einer linearen Regression kleinster Quadrate
2. Der Gradient einer quadratischen Funktion ist eine lineare Funktion, insbesondere für die obige Funktion
   

   $$

   $$\ frac {\ partiell} {\ partiell 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. Ein System, das einfacher als linear ist, existiert nicht. Der Gedanke, den ich erreichen wollte, 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 dies sinnvoll ist.
   

Nützliche Verlaufseigenschaften

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

Versuchen wir, ein einfacheres Problem zu lösen: Der Punkt ist gegeben $$$x$ Punkt finden $$$\ bar {x}$ so dass $$$f (\ bar {x}) <f (x)$ . Nehmen wir einen Punkt neben $$$x$ wieder mit linearer Approximation $$$f (\ bar {x}) \ ca. 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 wiederum nur für kleine $$$\ alpha$ . Um das Obige zusammenzufassen, wenn $$$\ nabla f (x) \ neq 0$ dann gibt der Gradient die Richtung der größten lokalen Funktionssteigerung an .

Hier sind zwei Beispiele für zweidimensionale Funktionen. Bilder dieser Art sind häufig in Demonstrationen des Gefälles zu sehen. Farbige Linien sind die sogenannten ebenen Linien . Dies ist 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, dass für eine Oberfläche durch eine Gleichung der Form definiert $$$f (x) = c$ , $$$\ nabla f (x)$ Setzt die Normale (bei gewöhnlichen Menschen - die Senkrechte) auf diese Oberfläche. Beachten Sie auch, dass der Verlauf zwar in Richtung der größten Zunahme der Funktion angezeigt wird, es jedoch keine Garantie dafür gibt, dass Sie in der dem Verlauf entgegengesetzten Richtung ein Minimum finden (z. B. das linke Bild).

Gefälle Abstieg

Es gab nur noch einen kleinen Schritt zur grundlegenden Gradientenabstiegsmethode: Wir haben aus dem Punkt gelernt $$$x$ Punkt bekommen $$$\ bar {x}$ mit niedrigerem Funktionswert $$$f$ . Was hindert uns daran, dies mehrmals zu wiederholen? Tatsächlich ist dies der Gradientenabstieg: Wir bauen die Sequenz auf

$$

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

Wert $$$\ alpha_k$ genannt die Schrittgröße (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 effizient macht; wenn $$$\ alpha_k$ sehr groß, dann wird die lineare Approximation schlecht und möglicherweise sogar falsch. In der Praxis wird die Schrittgröße häufig empirisch ausgewählt, theoretisch wird üblicherweise ein Lipschitz-Gradient angenommen, nämlich wenn

$$

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

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

Analyse für quadratische Funktionen

Wenn $$$A$ Ist eine symmetrische invertierbare Matrix, $$$Ax ^ * = b$ dann für die quadratische Funktion $$$f (x) = \ frac {1} {2} x ^ TAx-b ^ Tx + c$ Punkt $$$x ^ *$ ist der Mindestpunkt ( UPD . vorausgesetzt, dieser Mindestwert existiert überhaupt - $$$f$ kommt dem nicht nahe $$$- \ 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_k A) (x_k-x ^ *),$$

wo $$$I$ Ist die Identitätsmatrix, d.h. $$$Ix = x$ für alle $$$x$ . Wenn $$$\ alpha_k \ equiv \ alpha$ es wird sich herausstellen

$$

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

Der Ausdruck links ist der Abstand von der in Schritt erhaltenen Näherung $$$k$ Gradientenabstieg zum minimalen Punkt rechts - ein Ausdruck der Form $$$\ lambda ^ k \ beta$ was gegen Null konvergiert, wenn $$$| \ lambda | <1$ (Die Bedingung, über die ich geschrieben habe $$$\ alpha$ im vorherigen Absatz ist dies genau das, was garantiert). Diese grundlegende Schätzung stellt sicher, dass der Gradientenabstieg konvergiert.

Änderungen des Gefälles

Jetzt möchte ich ein wenig über die häufig verwendeten Modifikationen des Gradientenabstiegs sprechen, vor allem die sogenannten

Trägheits- 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 dieselbe „Trägheit“, der Algorithmus versucht bei jedem Schritt, sich gegen den Gradienten zu bewegen, bewegt sich jedoch gleichzeitig teilweise durch Trägheit in die gleiche Richtung wie in der vorherigen Iteration. Solche Methoden haben zwei wichtige Eigenschaften:

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

Eine der ersten derartigen Methoden erschien Mitte des 20. Jahrhunderts und wurde als Heavy-Ball-Methode bezeichnet , die die Art der Trägheit der Methode vermittelte: bei dieser Methode $$$\ alpha_k, \ beta_k$ unabhängig von $$$k$ und sorgfältig ausgewählt, abhängig von der Zielfunktion. Es ist erwähnenswert, dass $$$\ alpha_k$ kann alles andere als sein $$$\ beta_k$ - normalerweise nur etwas weniger als eins .

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

Chebyshev-Methode

Ja, ja, die erste Methode dieses Typs wurde von Chebyshev erfunden, um lineare Gleichungssysteme zu lösen. Irgendwann in 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$ Ist bis zu einem gewissen Grad polynomisch $$$k$ . Warum nicht versuchen, abzuholen? $$$\ alpha_k$ so dass $$$P_k (A) (x_0-x ^ *)$ war es kleiner? Ein Knoten universeller Polynome, die am wenigsten von Null abweichen, ist das Chebyshev-Polynom. Chebyshevs Methode besteht im Wesentlichen darin, die Abstiegsparameter so auszuwählen, dass $$$P_k$ war ein Polynom von Chebyshev. Es gibt wirklich ein kleines Problem: Bei einem normalen Gefälle ist dies einfach nicht möglich. Bei Trägheitsverfahren ist dies jedoch möglich. Dies ist hauptsächlich auf die Tatsache zurückzuführen, dass die 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 den Gradientenabstieg erstellt werden, bei dem ein neuer Wert nur aus einem vorherigen Wert berechnet wird, und für die Trägheit wird dies möglich, da die beiden vorherigen Werte verwendet werden. Es stellt sich heraus, dass die Komplexität der Berechnung $$$\ alpha_k, \ beta_k$ hängt nicht davon ab $$$k$ noch die Größe des Raumes $$$n$ .

Gradientenmethode konjugieren

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

$$

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

Wenn wir die Schrittgröße im Gradientenabstieg so wählen könnten, dass genau dieses Nullpunktpolynom erhalten wird, würde der Gradientenabstieg für eine feste Iterationszahl konvergieren, die nicht größer als die Dimension ist $$$A$ . Wie wir bereits herausgefunden haben, können wir dies nicht für den Gradientenabstieg tun. Glücklicherweise können wir für Trägheitsmethoden. Die Beschreibung und Begründung der Methode ist recht technisch, ich beschränke mich auf das Wesentliche: Bei jeder Iteration werden Parameter ausgewählt, die das beste Polynom ergeben, das unter Berücksichtigung aller vor dem aktuellen Schritt der Gradientenmessung durchgeführten Messungen erstellt werden kann . Dabei

1. Eine Iteration des Gradientenabfalls (ohne Berücksichtigung von Parameterberechnungen) enthält eine Matrixmultiplikation mit einem Vektor und 2-3 Vektoradditionen
2. Die Berechnung von Parametern erfordert auch 1-2 Matrixmultiplikation mit Vektor, 2-3 Skalarmektormultiplikation mit Vektor und mehrere Additionen von Vektoren.

Das Schwierigste im Rechenplan ist die Multiplikation der Matrix mit einem Vektor, dies erfolgt normalerweise zeitlich $$$\ mathcal {O} (n ^ 2)$ Für eine spezielle Implementierung kann dies jedoch in erfolgen $$$\ mathcal {O} (m)$ wo $$$m$ - die Anzahl der Elemente ungleich Null in $$$A$ . Angesichts der Konvergenz der konjugierten Gradientenmethode nicht mehr als $$$n$ Iterationen erhalten die Gesamtkomplexität des Algorithmus $$$\ mathcal {O} (nm)$ , was in allen Fällen nicht schlimmer ist $$$\ mathcal {O} (n ^ 3)$ für die Gauß- oder Cholesky-Methode, aber viel besser, wenn $$$m << n ^ 2$ das ist nicht so selten.

Die konjugierte Gradientenmethode funktioniert auch gut, wenn $$$f$ ist keine quadratische Funktion, konvergiert jedoch nicht in einer endlichen Anzahl von Schritten und erfordert häufig kleine zusätzliche Modifikationen

Nesterov-Methode

Für die Gemeinschaften der mathematischen Optimierung und des maschinellen Lernens ist der Name "Nesterov" seit langem ein bekannter Name. In den 80er Jahren des letzten Jahrhunderts hat Yu.E. Nesterov hat eine interessante Version 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 bedeutet keine komplizierte Berechnung $$$\ alpha_k, \ beta_k$ Wie bei der konjugierten Gradientenmethode ist das Verhalten der Methode im Allgemeinen ähnlich wie bei der Heavy-Ball-Methode, aber ihre Konvergenz ist in der Regel sowohl in der Theorie als auch in der Praxis viel zuverlässiger.

Stochastischer Gradientenabstieg

Der einzige formale Unterschied zum üblichen Gradientenabstieg besteht in der Verwendung einer Funktion anstelle eines Gradienten $$$g (x, \ theta)$ so dass $$$E_ \ theta g (x, \ theta) = \ nabla f (x)$ ( $$$E_ \ theta$ - zufällige Erwartung $$$\ theta$ ), so hat der stochastische Gradientenabstieg die Form

$$

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

$$$\ theta_k$ - Dies ist ein zufälliger Parameter, den wir nicht beeinflussen, aber gleichzeitig gehen wir im Durchschnitt gegen den Gradienten. 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 an $$$1, \ ldots, m$ ebenso wahrscheinlich nur durchschnittlich $$$g$ Ist ein Gefälle $$$f$ . Dieses Beispiel zeigt auch Folgendes: die Komplexität der Berechnung des Gradienten in $$$m$ mal mehr als rechnerische Komplexität $$$g$ . Dies ermöglicht den gleichzeitigen stochastischen Gradientenabstieg in $$$m$ mal mehr Iterationen. Trotz der Tatsache, dass der stochastische Gradientenabstieg aufgrund einer so starken 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 Trainieren der meisten neuronalen Netze, die in allen wichtigen ML-Bibliotheken implementiert sind: Tensorflow, Fackel, Kaffee, CNTK usw.

Es ist erwähnenswert, dass die Ideen von Trägheitsmethoden für den stochastischen Gradientenabstieg verwendet werden und in der Praxis häufig zu einem Anstieg führen. Theoretisch wird normalerweise angenommen, dass sich die asymptotische Konvergenzrate nicht ändert, da der Hauptfehler beim stochastischen Gradientenabstieg auf Dispersion zurückzuführen ist $$$g$ .

Subgradientabstieg

Diese Variante ermöglicht es Ihnen, mit nicht differenzierbaren Funktionen zu arbeiten. Ich werde sie genauer beschreiben. Wir müssen uns noch einmal an die lineare Approximation erinnern - Tatsache ist, dass es eine einfache Eigenschaft der Konvexität durch einen Gradienten gibt, eine differenzierbare Funktion $$$f$ genau dann konvex, wenn $$$f (y) \ geq f (x) + \ nabla f (x) ^ T (y-x)$ für alle $$$x, y$ . Es stellt sich heraus, dass eine konvexe Funktion nicht differenzierbar sein muss, sondern für jeden Punkt $$$x$ sicherlich gibt es einen solchen Vektor $$$g$ das $$$f (y) \ geq f (x) + g ^ T (y-x)$ für alle $$$y$ . Ein solcher Vektor $$$g$ allgemein als Subgradient bezeichnet $$$f$ an der Stelle $$$x$ , die Menge aller Subgradienten zu Punkten $$$x$ Subdifferential genannt $$$x$ und bezeichnen $$$\ partiell f (x)$ (trotz der Bezeichnung - es 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 über der Linie durch $$$(x, f (x))$ und eine Steigung haben $$$g$ (siehe Bilder unten). Ich stelle fest, dass es für einen Punkt mehrere Subgradienten geben kann, sogar eine unendliche Zahl.



Es ist normalerweise nicht sehr schwierig, mindestens einen Subgradienten für einen Punkt zu berechnen, bei einem Subgradientenabstieg wird im Wesentlichen ein Subgradient anstelle eines Gradienten verwendet. Es stellt sich heraus, dass dies ausreicht, theoretisch nimmt die Konvergenzrate jedoch beispielsweise in neuronalen Netzen eine undifferenzierbare Funktion ab $$$ReLU (x) = \ max (0, x)$ Sie verwenden es gerne, nur weil das Training damit schneller ist (dies ist übrigens ein Beispiel für eine nicht konvexe, nicht differenzierbare Funktion, bei der (Sub-) Gradientenabstieg erfolgreich angewendet wird. Die Funktion selbst $$$Relu$ konvexes aber mehrschichtiges neuronales Netzwerk mit $$$Relu$ nicht konvex und nicht differenzierbar). Als Beispiel für eine Funktion $$$f (x) = | x |$ Subdifferenz wird sehr einfach berechnet

$$

$$\ partielle f (x) = \ begin {Fälle} 1, & x> 0, \\ -1, & x <0, \\ [-1, 1], & x = 0. \ end {Fälle}$$

Vielleicht ist das Letzte, was zu wissen ist, dass der Subgradientenabstieg nicht bei 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 bricht die Konvergenz:

1. Nehmen wir an, wir haben von vorne angefangen $$$x_0$ .
2. Subgradienten-Abstiegsschritt:
   

   $$

   $$x_ {k + 1} = \ begin {Fälle} x_ {k} -1, & x> 0, \\ x_k + 1, & x <0, \\ ??? & x = 0. \ end {Fälle}$$
3. Wenn $$$x_0> 0$ dann werden wir in den ersten Schritten einen subtrahieren, wenn $$$x_0 <0$ dann hinzufügen. Auf die eine oder andere Weise werden wir uns irgendwann in der Pause befinden $$$[0, 1)$ von dem wir kommen $$$[- 1, 0)$ und dann springen wir zwischen zwei Punkten dieser Intervalle.

Theoretisch wird für den Subgradientenabstieg empfohlen, eine Abfolge von Schritten durchzuführen

$$

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

Wo $$$c$ in der Regel $$$1$ oder $$$\ frac {1} {2}$ . In der Praxis habe ich oft erfolgreiche Schritte gesehen $$$\ alpha_k = e ^ {- ck}$ , obwohl es für solche Schritte im Allgemeinen keine Konvergenz geben wird.

Proximale Methoden

Leider kenne ich keine gute Übersetzung für "proximal" im Zusammenhang mit der Optimierung. Deshalb werde ich diese Methode einfach aufrufen. Proximale Methoden erschienen als Verallgemeinerung projektiver Gradientenmethoden. Die Idee ist sehr einfach: Wenn es eine Funktion gibt $$$f$ als Summe dargestellt $$$f (x) = \ varphi (x) + h (x)$ wo $$$\ varphi$ Ist eine 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 beschreiben werde), dann die Konvergenzeigenschaften des Gradientenabfalls für $$$\ varphi$ bleiben und für Gefälle Abstieg für $$$f$ Wenn nach jeder Iteration dieser proximale Operator für den aktuellen Punkt angewendet wird $$$x_k$ Mit anderen Worten, die allgemeine Form der proximalen Methode sieht folgendermaßen aus:

$$

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

Ich denke bisher ist es völlig unverständlich, 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 eines konvexen Satzes $$$\ mathcal {K}$ , also
   

   $$

   $$h (x) = \ begin {Fälle} 0, & x \ in \ mathcal {K}, \\ + \ infty, & x \ notin \ mathcal {K}. \\ \ end {Fälle}$$
   
   In diesem Fall $$$prox _ {\ alpha_kh} (x)$ Ist eine Projektion auf das Set $$$\ mathcal {K}$ , das heißt, "am nächsten an $$$x$ Sollwert $$$\ mathcal {K}$ ". Daher beschränken wir den Gradientenabstieg nur auf die Menge $$$\ mathcal {K}$ Dies ermöglicht es uns, Probleme mit Einschränkungen zu lösen. Leider kann die Berechnung der Projektion im allgemeinen Fall noch schwieriger sein. Daher wird diese Methode normalerweise verwendet, wenn die Einschränkungen einfach sind, z. B. die sogenannten Box-Einschränkungen: 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 möchten diesen Begriff zu Optimierungsproblemen beim maschinellen Lernen hinzufügen, um eine Umschulung zu vermeiden. Eine solche Regularisierung neigt auch dazu, die am wenigsten signifikanten Komponenten aufzuheben. Für eine solche Funktion hat der proximale Operator die Form (ein Ausdruck für eine einzelne Koordinate wird unten beschrieben):
   

   $$

   $$[prox _ {\ alpha h} (x)] _ i = \ begin {case} x_i- \ alpha, & x_i> \ alpha, \\ x_i + \ alpha, & x_i <- \ alpha, \\ 0, & x_i \ in [- \ alpha, \ alpha], \ end {case}$$
   
   Das ist ziemlich einfach zu berechnen.

Fazit

Damit sind die mir bekannten Hauptvarianten der Gradientenmethode beendet. Vielleicht würde ich am Ende feststellen, dass all diese Modifikationen (außer vielleicht der konjugierten Gradientenmethode) leicht miteinander interagieren können. Ich habe die Newton-Methode und die Quasi-Newton-Methode (BFGS und andere) bewusst nicht in diese Liste aufgenommen: Obwohl sie einen Gradienten verwenden, sind sie komplexere Methoden und erfordern spezifische zusätzliche Berechnungen, die normalerweise rechenintensiver sind als die Berechnung eines Gradienten. Wenn dieser Text jedoch gefragt ist, werde ich gerne eine ähnliche Überprüfung durchführen.

Gebrauchte / empfohlene Literatur

Boyd. S, Vandenberghe L. Konvexe Optimierung
Shewchuk JR Eine Einführung in die konjugierte Gradientenmethode ohne den qualvollen Schmerz
Bertsekas DP Konvexe Optimierungstheorie

Nesterov Yu. E. Konvexe Optimierungsmethoden
Gasnikov A. V. Universeller Gradientenabstieg