Stochastischer Gradientenabstieg (oft mit SGD abgekürzt) ist ein iteratives Verfahren zur Optimierung einer Zielfunktion mit geeigneten Glattheitseigenschaften, wie Differenzierbarkeit oder Subdifferenzierbarkeit. Es kann als stochastische Approximation des Gradientenabstiegs zur Optimierung betrachtet werden, da es den tatsächlichen Gradienten, der aus dem gesamten Datensatz berechnet wird, durch eine Schätzung desselben ersetzt, die aus einer zufällig ausgewählten Teilmenge der Daten berechnet wird. Besonders bei hochdimensionalen Optimierungsproblemen reduziert dies die sehr hohe Rechenlast und ermöglicht schnellere Iterationen bei 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 allgemeiner in der künstlichen Intelligenz geworden.
Hintergrund
Sowohl die statistische Schätzung als auch das maschinelle Lernen befassen sich mit dem Problem der Minimierung einer Zielfunktion, die die Form einer Summe hat: Q(w) = (1/n) * sum_{i=1}^{n} Q_i(w), wobei der Parameter w, der Q(w) minimiert, zu schätzen ist. Jede Summandenfunktion Q_i ist typischerweise mit der i-ten Beobachtung im Trainingsdatensatz 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 ist jedoch seit langem bekannt, dass selbst die Forderung nach 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. Dort ist Q_i(w) der Wert der Verlustfunktion am i-ten Beispiel, und Q(w) ist das empirische Risiko. Wenn sie zur Minimierung der obigen Funktion verwendet wird, führt eine standardmäßige (oder „Batch“-)Gradientenabstiegsmethode Iterationen der Form w := w - eta nabla Q(w) = w - (eta/n) sum_{i=1}^{n} nabla Q_i(w) durch. Die Schrittweite wird mit eta bezeichnet, im maschinellen Lernen manchmal auch Lernrate genannt, und das Symbol ":=" bezeichnet die Aktualisierung einer Variablen im Algorithmus.
In vielen Fällen haben die Summandenfunktionen eine einfache Form, die eine kostengünstige Auswertung der Summenfunktion und des Summengradienten ermöglicht. In der Statistik ermöglichen beispielsweise einparametrische Exponentialfamilien wirtschaftliche Funktions- und Gradientenauswertungen. In anderen Fällen kann die Auswertung des Summengradienten jedoch teure Auswertungen der Gradienten aller Summandenfunktionen erfordern. Wenn der Trainingsdatensatz enorm groß 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 senken, wählt der stochastische Gradientenabstieg bei jedem Schritt eine Teilmenge der Summandenfunktionen aus. Dies ist bei großen Problemen des maschinellen Lernens sehr effektiv.
Iterative Methode
Beim stochastischen (oder „Online-") Gradientenabstieg wird der wahre Gradient von Q(w) durch einen Gradienten an einem einzelnen Stichprobenpunkt angenähert: w := w - eta * nabla Q_i(w). Während der Algorithmus den Trainingsdatensatz durchläuft, führt er die obige Aktualisierung für jedes Trainingsbeispiel durch. Mehrere Durchläufe über den Trainingsdatensatz werden durchgeführt, bis der Algorithmus konvergiert. Um Zyklen zu vermeiden, können die Daten bei jedem Durchlauf gemischt werden. Typische Implementierungen können eine adaptive Lernrate verwenden, damit der Algorithmus konvergiert.
Ein Kompromiss zwischen der Berechnung des wahren Gradienten und des Gradienten an einem einzelnen Beispiel besteht darin, den Gradienten gegen eine Teilmenge von Beispielen, einen sogenannten "Mini-Batch", zu berechnen. Dies kann deutlich besser abschneiden als der echte stochastische Gradientenabstieg, da der Code Vektorisierungsbibliotheken nutzen kann, anstatt jeden Schritt separat zu berechnen. Es kann auch zu einer glatteren Konvergenz führen, da der Gradient bei jedem Schritt über mehr Trainingsbeispiele gemittelt wird.
Die Konvergenz des stochastischen Gradientenabstiegs wurde mit den Theorien der konvexen Minimierung und der stochastischen Approximation analysiert. Kurz gesagt: Wenn die Lernraten eta mit einer geeigneten Rate abnehmen und relativ milde Annahmen erfüllt sind, 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 Konsequenz des Robbins-Siegmund-Theorems.
Lineare Regression
Angenommen, wir möchten eine Gerade y = a + bx an eine Menge von Trainingsbeispielen (x_i, y_i) mithilfe der Methode der kleinsten Quadrate anpassen. Die Zielfunktion ist Q(a, b) = (1/n) sum_{i=1}^{n} (y_i - (a + bx_i))^2. Der Batch-Gradientenabstieg würde den Gradienten von Q bezüglich a und b unter Verwendung aller n Beispiele berechnen. Der stochastische Gradientenabstieg wählt im Gegensatz dazu ein zufälliges Beispiel i und aktualisiert a und b nur unter Verwendung des Gradienten des quadratischen Fehlers für dieses Beispiel: a := a - eta (-2)(y_i - (a + bx_i)) und b := b - eta (-2x_i)(y_i - (a + bx_i)). Dies ist pro Iteration wesentlich kostengünstiger, insbesondere wenn n groß ist.
Anwendungen im maschinellen Lernen
Der stochastische Gradientenabstieg ist der Eckpfeiler des Trainings von neuronalen Netzen und Deep-Learning-Modellen. In diesen Kontexten ist die Zielfunktion das empirische Risiko, und die Verlustfunktion misst die Abweichung zwischen vorhergesagten und tatsächlichen Ausgaben. Beispielsweise werden beim Training eines Transformator-Modells für die Verarbeitung natürlicher Sprache SGD oder seine Varianten verwendet, um die Gewichte des Netzwerks auf der Grundlage von Minibatches von Daten zu aktualisieren. Die Methode ist besonders effektiv für groß angelegte Probleme, wie sie bei großen Sprachmodellen auftreten, bei denen die Anzahl der Token in den Trainingsdaten in die Milliarden gehen kann.
SGD wird auch in anderen Bereichen eingesetzt, darunter Computersehen und bestärkendes Lernen. Bei generativer KI werden stochastische Optimierungstechniken für Modelle wie die GPT-Serie von OpenAI verwendet. Varianten wie Momentum oder Adam sind in der Praxis weit verbreitet.
Varianten und Verbesserungen
Es wurden mehrere Varianten des stochastischen Gradientenabstiegs entwickelt, um seine Einschränkungen zu adressieren, wie z. B. die Empfindlichkeit gegenüber der Lernrate und das mögliche Feststecken in lokalen Minima. Dazu gehören SGD-Varianten wie Momentum, Nesterov-beschleunigter Gradient, AdaGrad, RMSProp und insbesondere Adam. Momentum hilft, Oszillationen zu dämpfen und die Konvergenz zu beschleunigen, indem ein Teil des vorherigen Updates zum aktuellen Update hinzugefügt wird. Adam passt die Lernrate für jeden Parameter basierend auf den ersten und zweiten Momenten der Gradienten an.
Die Wahl der Lernrate ist entscheidend für die Leistung von SGD. Zu große Lernraten können zu Divergenz führen, während zu kleine Lernraten die Konvergenz verlangsamen. Daher werden häufig Lernratenpläne verwendet, um die Lernrate während des Trainings anzupassen. Übliche Pläne umfassen das schrittweise Verringern der Lernrate nach einer bestimmten Anzahl von Epochen, das exponentielle Abklingen oder Methoden wie das Cosinus-Annealing.
Varianten und Verbesserungen
Mehrere Varianten von SGD wurden entwickelt, um seine Einschränkungen zu beheben, wie langsame Konvergenz oder die Empfindlichkeit gegenüber der Wahl der Lernrate. Dazu gehören SGD-Varianten wie Momentum, Nesterov beschleunigter Gradient, AdaGrad, RMSProp und Adam. Momentum beispielsweise akkumuliert einen gleitenden Durchschnitt der Gradienten, um Oszillationen zu reduzieren und die Konvergenz in relevanten Richtungen zu beschleunigen. Adam, das für Adaptive Moment Estimation steht, passt die Lernraten pro Parameter basierend auf Schätzungen der ersten und zweiten Momente der Gradienten an. Diese Varianten adressieren häufig die Wahl der Lernrate und die Varianz der Gradientenschätzungen.
Zusätzlich werden Lernratenpläne verwendet, um die Lernrate während des Trainings anzupassen. Übliche Pläne sind Schrittverfall, exponentieller Verfall und kosinusförmiges Abklingen. Diese Pläne helfen dem Algorithmus, zu konvergieren, indem sie die Schrittweite im Verlauf der Optimierung verringern.
Konvergenz und Herausforderungen
Die Konvergenz des stochastischen Gradientenabstiegs wurde mit den Theorien der konvexen Minimierung und der stochastischen Approximation analysiert. Unter relativ milden Annahmen, wenn die Lernraten eta mit einer geeigneten Rate abnehmen, 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 folgt aus dem Robbins-Siegmund-Theorem.
SGD führt jedoch aufgrund der zufälligen Auswahl von Minibatches Rauschen in die Gradientenschätzung ein, was zu einer langsameren Konvergenz in Bezug auf die Anzahl der Iterationen führen kann. Die Wahl der Minibatch-Größe ist ein kritischer Hyperparameter: Kleinere Batches führen zu mehr Rauschen, benötigen aber weniger Speicher und können zu einer besseren Generalisierung führen, während größere Batches glattere Gradienten liefern, aber möglicherweise zu schärferen Minima konvergieren, die schlechter generalisieren.
SGD kann in nicht-konvexen Problemen wie dem Deep Learning in Sattelpunkten oder lokalen Minima stecken bleiben. Strategien wie das Neustarten, die Verwendung von Impuls oder adaptiven Lernraten sowie Techniken wie Gradienten-Clipping und Batch-Normalisierung helfen, diese Probleme zu mildern. In der Praxis hat sich SGD trotz dieser Herausforderungen als äußerst erfolgreich beim Training tiefer neuronaler Netze erwiesen.
Historischer Kontext
Die Wurzeln des stochastischen Gradientenabstiegs liegen im Robbins-Monro-Algorithmus, der 1951 von Herbert Robbins und Sutton Monro für die stochastische Approximation eingeführt wurde. In den 1980er Jahren wurde das Verfahren im Zusammenhang mit der Backpropagation für neuronale Netze populär, und der Begriff „stochastischer Gradientenabstieg" wurde mit dem Wachstum des maschinellen Lernens weithin gebräuchlich. Heute ist es ein grundlegendes Werkzeug, das in allen wichtigen Frameworks für tiefes Lernen implementiert ist und von Unternehmen wie openai, google, und [[microsoft-azure] für das Training groß angelegter Modelle verwendet wird.