AdaGrad (kurz für Adaptive Gradient) ist ein Optimierungsalgorithmus, der im maschinellen Lernen und Deep Learning eingesetzt wird und die Lernrate für jeden Parameter individuell anpasst. Im Gegensatz zum standardmäßigen stochastischen Gradientenabstieg, der eine einzige Lernrate auf alle Parameter anwendet, skaliert AdaGrad das Update für jeden Parameter basierend auf den historischen quadrierten Gradienten dieses Parameters. Diese parameterweise Anpassung ermöglicht es dem Algorithmus, größere Updates für seltene Parameter und kleinere Updates für häufige Parameter durchzuführen, was besonders in Umgebungen mit spärlichen Daten nützlich ist. AdaGrad wurde 2011 von John Duchi, Elad Hazan und Yoram Singer eingeführt und ist zu einer grundlegenden Methode in der Entwicklung späterer adaptiver Optimierer wie RMSProp und Adam geworden.
Die Kernidee von AdaGrad besteht darin, eine laufende Summe der Quadrate vergangener Gradienten für jeden Parameter zu führen. Bei jeder Iteration wird die Lernrate für einen Parameter durch die Quadratwurzel dieser akkumulierten Summe dividiert. Dies bedeutet, dass Parameter mit großen historischen Gradienten kleinere effektive Lernraten erhalten, während Parameter mit kleinen oder seltenen Gradienten größere effektive Lernraten erhalten. Die Akkumulation der quadrierten Gradienten ist monoton steigend, was dazu führt, dass die effektive Lernrate im Laufe der Zeit abnimmt. Diese Eigenschaft kann für die Konvergenz in konvexen Umgebungen vorteilhaft sein, kann aber in nicht-konvexen Problemen zu einer übermäßig aggressiven Abnahme führen, eine Einschränkung, die spätere Algorithmen motivierte.
Hintergrund
Optimierung im maschinellen Lernen beinhaltet oft die Minimierung einer Zielfunktion, die eine Summe von Verlustfunktionen pro Beispiel ist. Für einen Trainingssatz von n Beispielen ist das empirische Risiko gegeben durch Q(w) = (1/n) Σ Q_i(w), wobei w der Parametervektor und Q_i der Verlust für das i-te Beispiel ist. Der standardmäßige Gradientenabstieg berechnet den Gradienten der vollständigen Summe bei jedem Schritt, was rechenintensiv sein kann, wenn n groß ist. Der stochastische Gradientenabstieg (SGD) approximiert stattdessen den Gradienten mit einer einzelnen Stichprobe oder einem Mini-Batch, was die Rechenkosten pro Iteration reduziert, aber Rauschen einführt. Der Robbins-Monro-Algorithmus aus den 1950er Jahren legte den Grundstein für die stochastische Approximation, und SGD wurde aufgrund seiner Effizienz bei großen Datensätzen zu einem Standardwerkzeug im maschinellen Lernen.
Bei SGD lautet die Update-Regel w := w - η ∇Q_i(w), wobei η die Lernrate ist. Die Wahl einer festen Lernrate ist oft suboptimal: Eine zu große Rate kann zu Divergenz führen, während eine zu kleine Rate die Konvergenz verlangsamt. Adaptive Methoden wie AdaGrad zielen darauf ab, dies zu beheben, indem sie die Lernrate basierend auf der Geometrie der Optimierungslandschaft anpassen. Die Motivation für AdaGrad kam aus der Beobachtung, dass verschiedene Parameter unterschiedliche Schrittgrößen erfordern können, insbesondere bei Problemen mit spärlichen Merkmalen, bei denen einige Parameter selten aktualisiert werden.
Algorithmus
AdaGrad modifiziert das SGD-Update, indem es eine Diagonalmatrix G_t führt, wobei jedes Diagonalelement die Summe der Quadrate der vergangenen Gradienten für den entsprechenden Parameter ist. Zum Zeitpunkt t lautet das Update für Parameter w_i:
w_i := w_i - (η / sqrt(G_{t,ii} + ε)) ∇Q_i(w_i),
wobei ε eine kleine Konstante (z. B. 1e-8) ist, um eine Division durch Null zu vermeiden. Die akkumulierten Gradientenquadrate G_{t,ii} = Σ_{τ=1}^{t} (∇Q_i(w_τ))^2. Dies kann in Vektorform geschrieben werden als:
w := w - η * diag(G_t + εI)^{-1/2} ∇Q(w).
In der Praxis wird der Algorithmus oft auf Mini-Batches angewendet, wobei der Gradient über eine Teilmenge der Trainingsbeispiele berechnet wird. Die parameterweise Lernrate ist somit η_t,i = η / sqrt(G_{t,ii} + ε). Da G_t im Laufe der Zeit wächst, nimmt die effektive Lernrate ab, was sicherstellt, dass der Algorithmus mit fortschreitender Zeit kleinere Schritte macht. Dies steht im Gegensatz zu SGD mit Momentum, das Gradienten akkumuliert, um in konsistenten Richtungen zu beschleunigen.
Mathematische Eigenschaften
AdaGrad wurde ursprünglich im Kontext der konvexen Optimierung analysiert. Die Autoren zeigten, dass AdaGrad für konvexe Funktionen eine Bedauernsgrenze erreicht, die asymptotisch optimal für Online-Lernen ist. Insbesondere wächst das Bedauern, das die kumulative Differenz zwischen dem Verlust des Algorithmus und dem besten festen Parameter im Nachhinein misst, für AdaGrad als O(√T), was der unteren Grenze für Online-konvexe Optimierung entspricht. Dies ist eine Verbesserung gegenüber standardmäßigem SGD mit fester Lernrate, das möglicherweise eine sorgfältige Abstimmung des Lernratenplans erfordert.
Die zentrale Erkenntnis ist, dass AdaGrad sich automatisch an die Geometrie des Merkmalsraums anpasst. In spärlichen Umgebungen, in denen viele Merkmale für die meisten Beispiele Null sind, bleiben die akkumulierten Gradienten für diese Merkmale klein, was größere Updates ermöglicht, wenn sie auftreten. Dies macht AdaGrad besonders effektiv für die Verarbeitung natürlicher Sprache und andere Bereiche mit hochdimensionalen spärlichen Eingaben.
Allerdings ist die Akkumulation der quadrierten Gradienten monoton steigend, was bedeutet, dass die Lernrate im Laufe der Zeit auf Null abfällt. In nicht-konvexen Problemen, wie dem Training tiefer neuronaler Netze, kann dies dazu führen, dass der Algorithmus vorzeitig aufhört zu lernen. Diese Einschränkung führte zur Entwicklung von Varianten wie RMSProp, das einen gleitenden Durchschnitt der quadrierten Gradienten anstelle einer Summe verwendet, und Adam, das adaptive Lernraten mit Momentum kombiniert.
Anwendungen
AdaGrad wurde in verschiedenen Aufgaben des maschinellen Lernens angewendet, insbesondere bei solchen mit spärlichen Daten. In der Verarbeitung natürlicher Sprache wurde es zum Training von Modellen auf Bag-of-Words-Merkmalen verwendet, bei denen jedes Dokument durch einen spärlichen Vektor von Wortzahlen dargestellt wird. Die parameterweise Anpassung ermöglicht es seltenen Wörtern, größere Updates zu erhalten, was die Fähigkeit des Modells verbessert, aus seltenen, aber informativen Merkmalen zu lernen.
In Empfehlungssystemen wurde AdaGrad zur Optimierung von Matrixfaktorisierungsmodellen verwendet, bei denen Benutzer- und Artikel-Embeddings basierend auf spärlichen Interaktionsdaten aktualisiert werden. Die Fähigkeit des Algorithmus, mit unterschiedlichen Häufigkeiten von Benutzer-Artikel-Paaren umzugehen, macht ihn für solche Umgebungen geeignet. Darüber hinaus wurde AdaGrad in Online-Lernszenarien eingesetzt, in denen Daten sequenziell eintreffen und das Modell sich schnell anpassen muss.
Obwohl es in vielen Deep-Learning-Anwendungen durch fortschrittlichere Optimierer ersetzt wurde, bleibt AdaGrad ein Benchmark für Vergleiche und wird in einigen Bereichen weiterhin verwendet, in denen seine Eigenschaften vorteilhaft sind. Sein Einfluss ist im Design späterer adaptiver Methoden offensichtlich, die auf der Idee parameterweiser Lernraten aufbauen.
Einschränkungen und Erweiterungen
Die Hauptbeschränkung von AdaGrad ist die monoton abnehmende Lernrate. Im Deep Learning, wo die Verlustlandschaft nicht-konvex ist, kann dies zu langsamer Konvergenz oder zum Feststecken in schlechten lokalen Minima führen. Um dies zu beheben, haben Forscher mehrere Erweiterungen vorgeschlagen:
- RMSProp: Eingeführt von Geoffrey Hinton in seinen Vorlesungsnotizen, verwendet RMSProp einen exponentiell abklingenden Durchschnitt der quadrierten Gradienten, was eine flexiblere Anpassung der Lernrate ermöglicht.
- Adam: Vorgeschlagen von Diederik Kingma und Jimmy Ba im Jahr 2014, kombiniert Adam den gleitenden Durchschnitt von RMSProp mit Momentum und bietet sowohl adaptive Lernraten als auch Momentum.
- AdaDelta: Entwickelt von Matthew Zeiler, eliminiert AdaDelta die Notwendigkeit eines Lernraten-Hyperparameters, indem es ein Fenster vergangener Gradienten verwendet.
Diese Algorithmen sind zu den Standardoptionen für das Training tiefer neuronaler Netze geworden, aber sie alle führen ihre Wurzeln auf das adaptive Gradientenkonzept zurück, das von AdaGrad eingeführt wurde.
Einfluss und Vermächtnis
AdaGrad hat einen nachhaltigen Einfluss auf das Gebiet der Optimierung im maschinellen Lernen gehabt. Es war einer der ersten weit verbreiteten Algorithmen, der parameterweise Lernraten verwendete, und ebnete den Weg für eine Familie adaptiver Optimierer. Seine theoretischen Garantien in konvexen Umgebungen boten eine solide Grundlage für das Verständnis adaptiver Methoden. Der Algorithmus wird oft in Lehrbüchern und Forschungsarbeiten als eine Schlüsselentwicklung in der Geschichte der Optimierung zitiert.
In der Praxis wird AdaGrad heute weniger häufig für das Training großer Deep-Learning-Modelle verwendet, da Adam und seine Varianten tendenziell besser abschneiden. Es bleibt jedoch ein nützliches Werkzeug für spezifische Probleme, wie solche mit spärlichen Merkmalen, und wird in Kursen zum maschinellen Lernen weiterhin als wichtiger konzeptioneller Schritt gelehrt.
Siehe auch
- Stochastischer Gradientenabstieg
- Adam-Optimierer
- RMSProp
- Deep Learning