Stochastischer Gradientenabstieg (oft als SGD abgekürzt) ist ein iteratives Verfahren zur Optimierung einer Zielfunktion mit geeigneten Glattheitseigenschaften, wie Differenzierbarkeit oder Subdifferenzierbarkeit. Es kann als stochastische Approximation der Gradientenabstiegs-Optimierung betrachtet werden, da es den tatsächlichen Gradienten, der aus dem gesamten Datensatz berechnet wird, durch eine Schätzung ersetzt, die aus einer zufällig ausgewählten Teilmenge der Daten berechnet wird. Besonders bei hochdimensionalen Optimierungsproblemen reduziert dies den sehr hohen Rechenaufwand und ermöglicht schnellere Iterationen, allerdings auf Kosten einer geringeren Konvergenzrate. Die grundlegende Idee hinter der stochastischen Approximation lässt sich auf den Robbins-Monro-Algorithmus aus den 1950er Jahren zurückführen. Heute ist der stochastische Gradientenabstieg zu einer wichtigen Optimierungsmethode im maschinellen Lernen und verwandten Bereichen geworden.
Sowohl die statistische Schätzung als auch das maschinelle Lernen betrachten das Problem der Minimierung einer Zielfunktion, die die Form einer Summe hat: Q(w) = (1/n) Σ Q_i(w), wobei der Parameter w, der Q(w) minimiert, geschätzt werden soll. Jede Summandenfunktion Q_i ist typischerweise mit der i-ten Beobachtung im für das Training verwendeten Datensatz verbunden. In der klassischen Statistik treten Summenminimierungsprobleme bei der Methode der kleinsten Quadrate und bei der Maximum-Likelihood-Schätzung für unabhängige Beobachtungen auf. Die allgemeine Klasse von Schätzern, die als Minimierer von Summen entstehen, werden M-Schätzer genannt. In der Statistik wurde jedoch schon lange erkannt, dass die Forderung nach sogar lokaler Minimierung für einige Probleme der Maximum-Likelihood-Schätzung zu restriktiv ist. Daher betrachten zeitgenössische statistische Theoretiker oft stationäre Punkte der Likelihood-Funktion oder Nullstellen ihrer Ableitung, der Score-Funktion, sowie andere Schätzgleichungen. Das Summenminimierungsproblem tritt auch bei der empirischen Risikominimierung auf, wobei Q_i(w) der Wert der Verlustfunktion am i-ten Beispiel ist und Q(w) das empirische Risiko darstellt.
Wenn es zur Minimierung der obigen Funktion verwendet wird, würde ein standardmäßiges (oder "Batch-") Gradientenabstiegsverfahren die folgenden Iterationen durchführen: w := w - η ∇Q(w) = w - (η/n) Σ ∇Q_i(w). Die Schrittweite wird mit η bezeichnet, manchmal auch als Lernrate im maschinellen Lernen bezeichnet, und ":=" bezeichnet die Aktualisierung einer Variablen im Algorithmus. In vielen Fällen haben die Summandenfunktionen eine einfache Form, die kostengünstige Auswertungen der Summenfunktion und des Summengradienten ermöglicht. Zum Beispiel erlauben in der Statistik einparametrige Exponentialfamilien wirtschaftliche Funktions- und Gradientenauswertungen. In anderen Fällen kann die Auswertung des Summengradienten jedoch teure Auswertungen der Gradienten aller Summandenfunktionen erfordern. Wenn der Trainingssatz enorm ist und keine einfachen Formeln existieren, wird die Auswertung der Gradientensummen sehr teuer, da die Auswertung des Gradienten die Auswertung der Gradienten aller Summandenfunktionen erfordert. Um die Rechenkosten bei jeder Iteration zu sparen, sampelt der stochastische Gradientenabstieg bei jedem Schritt eine Teilmenge der Summandenfunktionen. Dies ist bei groß angelegten Problemen des maschinellen Lernens sehr effektiv.
Iteratives Verfahren
Beim stochastischen (oder "Online-") Gradientenabstieg wird der wahre Gradient von Q(w) durch einen Gradienten an einer einzelnen Stichprobe approximiert: w := w - η ∇Q_i(w). Während der Algorithmus den Trainingssatz durchläuft, führt er die obige Aktualisierung für jede Trainingsstichprobe durch. Es können mehrere Durchläufe über den Trainingssatz gemacht werden, bis der Algorithmus konvergiert. Wenn dies getan wird, können die Daten für jeden Durchlauf gemischt werden, um Zyklen zu verhindern. Typische Implementierungen können eine adaptive Lernrate verwenden, damit der Algorithmus konvergiert. In Pseudocode kann der stochastische Gradientenabstieg wie folgt dargestellt werden:
- Wähle einen anfänglichen Parametervektor w und eine Lernrate η.
- Wiederhole bis zur Konvergenz:
- Mische die Trainingsstichproben.
- Für jede Trainingsstichprobe i:
- Berechne den Gradienten ∇Q_i(w).
- Aktualisiere die Parameter: w := w - η ∇Q_i(w).
Ein Kompromiss zwischen der Berechnung des wahren Gradienten und des Gradienten an einer einzelnen Stichprobe besteht darin, den Gradienten gegen mehr als eine Trainingsstichprobe zu berechnen, die als "Mini-Batch" bezeichnet wird, bei jedem Schritt. Dies kann deutlich besser abschneiden als der beschriebene "echte" stochastische Gradientenabstieg, da der Code Vektorisierungsbibliotheken nutzen kann, anstatt jeden Schritt separat zu berechnen, wie erstmals in einem Papier von 1986 gezeigt wurde, wo es als "Bunch-Mode-Backpropagation-Algorithmus" bezeichnet wurde. Es kann auch zu einer glatteren Konvergenz führen, da der bei jedem Schritt berechnete Gradient über mehr Trainingsstichproben gemittelt wird.
Die Konvergenz des stochastischen Gradientenabstiegs wurde mit den Theorien der konvexen Minimierung und der stochastischen Approximation analysiert. Kurz gesagt, wenn die Lernraten η mit einer angemessenen Rate abnehmen und unter relativ milden Annahmen, konvergiert der stochastische Gradientenabstieg fast sicher zu einem globalen Minimum, wenn die Zielfunktion konvex oder pseudokonvex ist, und andernfalls fast sicher zu einem lokalen Minimum. Dies ist tatsächlich eine Folge des Robbins-Siegmund-Theorems.
Lineare Regression
Angenommen, wir wollen eine gerade Linie y = w^T x an eine Menge von Trainingsbeispielen (x_i, y_i) anpassen. Die Zielfunktion ist der mittlere quadratische Fehler: Q(w) = (1/n) Σ (y_i - w^T x_i)^2. Der Gradient für ein einzelnes Beispiel ist ∇Q_i(w) = -2 (y_i - w^T x_i) x_i. Beim stochastischen Gradientenabstieg wird die Aktualisierungsregel zu w := w + 2η (y_i - w^T x_i) x_i. Dies ist äquivalent zum Algorithmus der kleinsten mittleren Quadrate (LMS), auch bekannt als Widrow-Hoff-Regel, eingeführt von Bernard Widrow und Ted Hoff im Jahr 1960. Der LMS-Algorithmus ist ein klassisches Beispiel für stochastische Approximation und wurde in der adaptiven Signalverarbeitung weit verbreitet eingesetzt.
Anwendungen im maschinellen Lernen
Der stochastische Gradientenabstieg ist der Kernoptimierungsalgorithmus für das Training von neuronalen Netzen, einschließlich Deep-Learning-Modellen. Im modernen Deep Learning werden SGD und seine Varianten verwendet, um Verlustfunktionen wie Kreuzentropie für Klassifikation oder mittleren quadratischen Fehler für Regression zu minimieren. Die Effizienz des Algorithmus bei der Verarbeitung großer Datensätze macht ihn für das Training von Modellen auf massiven Korpora, wie sie in großen Sprachmodellen verwendet werden, unerlässlich. Zum Beispiel stützt sich das Training von Transformer-basierten Modellen, wie im Papier "Attention Is All You Need" von 2017 von Jakob Uszkoreit, Lukasz Kaiser und anderen eingeführt, auf SGD oder seine adaptiven Varianten wie Adam.
SGD wird auch in anderen Bereichen der künstlichen Intelligenz verwendet, einschließlich Computer Vision, Verarbeitung natürlicher Sprache und Reinforcement Learning. Im Reinforcement Learning wird SGD verwendet, um Parameter von Politik- und Wertfunktionen zu aktualisieren, wie bei Policy-Gradient-Methoden. Die stochastische Natur des Algorithmus ermöglicht es ihm, lokale Minima in nicht-konvexen Optimierungsproblemen zu verlassen, was besonders wichtig für das Training tiefer Netzwerke mit komplexen Verlustlandschaften ist.
Varianten und Verbesserungen
Mehrere Varianten des stochastischen Gradientenabstiegs wurden entwickelt, um Konvergenz und Stabilität zu verbessern. Eine häufige Verbesserung ist die Verwendung von Momentum, das einen Geschwindigkeitsvektor akkumuliert, um Gradienten in konsistenten Richtungen zu beschleunigen und Oszillationen zu dämpfen. Eine andere ist der Nesterov-beschleunigte Gradient, der den Gradienten an einer Vorausschauposition berechnet. Adaptive Lernratenmethoden wie Adam passen die Lernrate pro Parameter basierend auf Schätzungen der ersten und zweiten Momente der Gradienten an. Diese Methoden werden in der Praxis häufig verwendet und gelten oft als Standard-Optimierer für das Training neuronaler Netze.
Weitere verwandte Techniken umfassen Lernratenpläne, die die Lernrate im Laufe der Zeit anpassen, und Gradienten-Clipping, das explodierende Gradienten verhindert, indem große Gradienten herunterskaliert werden. Batch-Normalisierung und Schichtnormalisierung werden oft in Verbindung mit SGD verwendet, um das Training zu stabilisieren und höhere Lernraten zu ermöglichen. Darüber hinaus sind Gewichtsinitialisierungs-Strategien wie Xavier- oder He-Initialisierung entscheidend für ein effektives SGD-Training.
Herausforderungen und Überlegungen
Eine der Hauptherausforderungen beim stochastischen Gradientenabstieg ist die Auswahl der Lernrate. Wenn die Lernrate zu hoch ist, kann der Algorithmus divergieren; wenn sie zu niedrig ist, kann die Konvergenz langsam sein. In der Praxis werden Lernratenpläne oder adaptive Methoden verwendet, um dieses Problem zu mildern. Eine weitere Herausforderung ist das Rauschen, das durch die Verwendung einer Teilmenge von Daten entsteht, was dazu führen kann, dass der Verlust schwankt. Dieses Rauschen kann jedoch auch vorteilhaft sein, da es dem Algorithmus helfen kann, scharfe Minima zu verlassen und flachere Minima zu finden, die besser generalisieren.
SGD ist empfindlich gegenüber der Skalierung von Merkmalen, daher wird oft eine Merkmalsnormalisierung empfohlen. Die Wahl der Mini-Batch-Größe beeinflusst ebenfalls die Leistung: Kleinere Batches führen zu mehr Rauschen, benötigen aber weniger Speicher, während größere Batches glattere Gradienten liefern, aber möglicherweise zu schlechterer Generalisierung führen. Beim verteilten Training kann SGD mit Techniken wie synchronen oder asynchronen Aktualisierungen parallelisiert werden, wie in Frameworks wie TensorFlow und PyTorch implementiert.
Historischer Kontext
Die Wurzeln des stochastischen Gradientenabstiegs reichen bis zum Robbins-Monro-Algorithmus zurück, der 1951 von Herbert Robbins und Sutton Monro entwickelt wurde und die Idee der stochastischen Approximation zur Nullstellensuche einführte. In den 1960er Jahren wandten der LMS-Algorithmus von Bernard Widrow und Ted Hoff ähnliche Prinzipien auf die adaptive Filterung an. Die Verbindung zum Training neuronaler Netze wurde in den 1980er Jahren mit der Popularisierung der Backpropagation hergestellt. 1986 veröffentlichten David Rumelhart, Geoffrey Hinton und Ronald Williams ein Papier, das die Wirksamkeit von Backpropagation mit SGD für das Lernen interner Repräsentationen demonstrierte. Seitdem ist SGD zu einem Eckpfeiler des maschinellen Lernens geworden und ermöglichte Durchbrüche in Bereichen wie Bilderkennung, Spracherkennung und Verarbeitung natürlicher Sprache.
In den 2010er Jahren beschleunigten der Aufstieg des Deep Learning und die Verfügbarkeit großer Datensätze sowie leistungsfähiger Hardware wie GPUs von Nvidia und AMD die Einführung von SGD. Forschungseinrichtungen wie Stanford AI Lab, Berkeley AI Research und University of Toronto trugen zu theoretischen und praktischen Fortschritten bei. Heute bleibt SGD ein aktives Forschungsgebiet, mit laufender Arbeit zum Verständnis seiner Generalisierungseigenschaften und zur Entwicklung neuer Varianten.