Stochastischer Gradientenabstieg (häufig als SGD abgekürzt) ist ein iteratives Verfahren zur Optimierung einer Zielfunktion mit geeigneten Glattheitseigenschaften, wie Differenzierbarkeit oder Subdifferenzierbarkeit. Es kann als eine 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. Insbesondere bei hochdimensionalen Optimierungsproblemen reduziert dies die sehr hohe Rechenlast und erreicht 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 geworden, insbesondere zum Training von neuronalen Netzen und anderen Deep-Learning-Modellen.
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) Σᵢ Qᵢ(w), wobei der Parameter w, der Q(w) minimiert, geschätzt werden soll. Jede Summandenfunktion Qᵢ 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, wird als M-Schätzer bezeichnet. Es ist jedoch seit langem bekannt, dass die Forderung nach sogar lokaler Minimierung für einige Maximum-Likelihood-Probleme zu restriktiv ist, daher betrachten zeitgenössische statistische Theoretiker oft stationäre Punkte der Likelihood-Funktion oder Nullstellen ihrer Ableitung, der Score-Funktion.
Das Summenminimierungsproblem tritt auch bei der empirischen Risikominimierung auf. Dort ist Qᵢ(w) der Wert der Verlustfunktion am i-ten Beispiel, und Q(w) ist das empirische Risiko.
Wenn es zur Minimierung der obigen Funktion verwendet wird, würde eine Standardmethode (oder "Batch"-Methode) des Gradientenabstiegs Iterationen der folgenden Form durchführen: w := w - η ∇Q(w) = w - (η/n) Σᵢ ∇Qᵢ(w). Die Schrittweite η wird im maschinellen Lernen manchmal als Lernrate bezeichnet. In vielen Fällen haben die Summandenfunktionen eine einfache Form, die kostengünstige Auswertungen der Summenfunktion und des Summengradienten ermöglicht, wie zum Beispiel bei einparametrigen Exponentialfamilien. Wenn der Trainingsdatensatz jedoch enorm ist und keine einfachen Formeln existieren, wird die Auswertung der Gradientensummen sehr teuer, da sie die Gradienten aller Summandenfunktionen erfordert. Um Rechenkosten zu sparen, sampelt der stochastische Gradientenabstieg bei jedem Schritt eine Teilmenge der Summandenfunktionen, was bei großen maschinellen Lernproblemen sehr effektiv ist.
Iterative Methode
Beim stochastischen (oder "Online-") Gradientenabstieg wird der wahre Gradient von Q(w) durch einen Gradienten an einer einzelnen Stichprobe approximiert: w := w - η ∇Qᵢ(w). Während der Algorithmus den Trainingsdatensatz durchläuft, führt er das obige Update für jedes Trainingsbeispiel durch. Es können mehrere Durchläufe über den Trainingsdatensatz gemacht werden, bis der Algorithmus konvergiert. Wenn dies geschieht, 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:
- Initialisiere Parameter w und Lernrate η.
- Wiederhole bis zur Konvergenz:
- Mische die Trainingsdaten.
- Für jedes Trainingsbeispiel i:
- Berechne den Gradienten ∇Qᵢ(w).
- Aktualisiere w := w - η ∇Qᵢ(w).
Ein Kompromiss zwischen der Berechnung des wahren Gradienten und des Gradienten an einer einzelnen Stichprobe besteht darin, den Gradienten gegen mehr als ein Trainingsbeispiel, genannt "Mini-Batch", bei jedem Schritt zu berechnen. Dies kann deutlich besser abschneiden als der echte stochastische Gradientenabstieg, da der Code Vektorisierungsbibliotheken nutzen kann, anstatt jeden Schritt separat zu berechnen, wie erstmals im Kontext der Backpropagation gezeigt wurde. Es kann auch zu einer glatteren Konvergenz führen, da der bei jedem Schritt berechnete Gradient ü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 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 eine Konsequenz des Robbins-Siegmund-Theorems.
Lineare Regression
Angenommen, wir wollen eine gerade Linie ŷ = w·x an eine Menge von Trainingsbeispielen (xᵢ, yᵢ) anpassen. Ein häufiges Ziel ist die Minimierung des mittleren quadratischen Fehlers: Q(w) = (1/n) Σᵢ (ŷᵢ - yᵢ)². Der Gradient für ein einzelnes Beispiel ist ∇Qᵢ(w) = 2(ŷᵢ - yᵢ)xᵢ. Beim stochastischen Gradientenabstieg wird das Update zu w := w - η(ŷᵢ - yᵢ)xᵢ. Dieses einfache Beispiel veranschaulicht, wie SGD jeweils eine Stichprobe verwendet, was es für große Datensätze rechnerisch effizient macht.
Anwendungen im maschinellen Lernen
Der stochastische Gradientenabstieg ist der Kernoptimierungsalgorithmus für das Training vieler Modelle des maschinellen Lernens, einschließlich Deep-Learning-Modellen wie Transformatoren und großen Sprachmodellen. Er wird beim Training von neuronalen Netzen für Aufgaben wie Bilderkennung, Verarbeitung natürlicher Sprache und generative KI verwendet. Varianten wie Adam und andere SGD-Varianten wurden entwickelt, um Konvergenz und Stabilität zu verbessern. Die Wahl des Lernratenplans ist entscheidend für ein effektives Training.
Herausforderungen und Erweiterungen
SGD steht vor Herausforderungen wie der Wahl einer angemessenen Lernrate, dem Umgang mit verrauschten Gradienten und der Vermeidung schlechter lokaler Minima. Zu den Erweiterungen gehören Impuls (Momentum), adaptive Lernraten (z. B. Adam) und Techniken wie Gradienten-Clipping, um explodierende Gradienten zu verhindern. Im Deep Learning werden Methoden wie Batch-Normalisierung und Dropout oft in Verbindung mit SGD verwendet, um das Training zu verbessern.
Historischer Kontext
Der Robbins-Monro-Algorithmus aus den 1950er Jahren legte den Grundstein für die stochastische Approximation. In den 1980er und 1990er Jahren wurde SGD beim Training neuronaler Netze populär, insbesondere mit Backpropagation. Heute bleibt es ein grundlegendes Werkzeug in der Forschung und Industrie der künstlichen Intelligenz, das von großen KI-Labors und Unternehmen verwendet wird.
Siehe auch
- Gradientenabstieg (nicht in der Liste, aber verwandt)
- Verlustfunktionen
- Daten-Augmentierung
- Modellbeschneidung