Das Gradientenverfahren ist ein allgemeiner Algorithmus zur Optimierung, der optimale Lösungen für eine Vielzahl von Fragestellungen ermitteln kann. Der Grundgedanke beim Gradientenverfahren ist, die Parameter iterativ so zu verändern, dass eine Kostenfunktion minimiert wird.
Stellen Sie sich einmal vor, Sie hätten sich in dichtem Nebel in den Bergen verlaufen; Sie können nur die Neigung des Bodens unter Ihren Füßen fühlen. Um schnell ins Tal zu gelangen, wäre eine geeignete Strategie, sich stets in Richtung der steilsten Neigung bergab zu bewegen. Genau dies tut das Gradientenverfahren: Es berechnet den lokalen Gradienten der Fehlerfunktion in Abhängigkeit vom Parametervektor θ und bewegt sich in Richtung eines abfallenden Gradienten. Sobald der Gradient null wird, haben Sie ein Minimum gefunden!
Zu Beginn befüllen Sie θ mit Zufallszahlen (dies nennt man zufällige Initialisierung). Dann verbessern Sie die Parameter nach und nach in ganz kleinen Schritten, wobei Sie bei jedem Schritt versuchen, die Kostenfunktion zu senken (z.B. den MSE), bis der Algorithmus bei einem Minimum konvergiert (siehe Abbildung 4-3).
Ein wichtiger Parameter beim Gradientenverfahren ist die Größe der Schritte, die durch die Lernrate, einen Hyperparameter, festgelegt wird. Ist die Lernrate zu klein, muss der Algorithmus viele Iterationen durchlaufen, bevor er konvergiert. Das dauert natürlich sehr lange (siehe Abbildung 4-4).
Abbildung 4-3: In dieser Darstellung des Gradientenverfahrens werden die Modellparameter mit Zufallswerten initialisiert und wiederholt angepasst, um die Kostenfunktion zu minimieren – die Größe der Lernschritte ist proportional zur Steigung der Kostenfunktion, sodass die Schritte nach und nach kleiner werden, wenn die Parameter auf das Minimum zusteuern.
Abbildung 4-4: Die Lernrate ist zu gering.
Wenn die Lernrate dagegen zu groß ist, kann es passieren, dass Sie die Täler überspringen und auf der anderen Seite landen, möglicherweise sogar höher als zuvor. Dadurch kann der Algorithmus divergieren, also immer größere Werte erzeugen und überhaupt keine gute Lösung finden (siehe Abbildung 4-5).
Abbildung 4-5: Die Lernrate ist zu groß.
Schließlich sehen nicht alle Kostenfunktionen wie hübsche, regelmäßige Schüsseln aus. Es kann Täler, Grate, Plateaus und alle möglichen Arten unregelmäßiger Landschaften geben, die das Konvergieren beim Minimum erschweren. Abbildung 4-6 zeigt die zwei wichtigsten Herausforderungen beim Gradientenverfahren: Wenn die zufällige Initialisierung den Algorithmus auf der linken Seite startet, wird er bei einem lokalen Minimum konvergieren, das weniger gut als das globale Minimum ist. Wenn Sie auf der rechten Seite starten, dauert es sehr lange, das Plateau zu überqueren. Wenn Sie den Algorithmus zu früh beenden, werden Sie nie das globale Minimum erreichen.
Abbildung 4-6: Fallstricke beim Gradientenverfahren
Glücklicherweise ist MSE als Kostenfunktion eines linearen Regressionsmodells eine konvexe Funktion. Das bedeutet, wenn Sie zwei beliebige Punkte auf der Kurve auswählen, schneidet die lineare Verbindung zwischen diesen beiden niemals die Kurve. Das impliziert, dass es keine lokalen Minima gibt, nur ein globales Minimum. Sie ist auch eine stetige Funktion mit einer Steigung, die sich niemals abrupt ändert.3 Diese zwei Umstände haben eine wichtige Konsequenz: Mit dem Gradientenverfahren kann man sich dem globalen Minimum beliebig annähern (wenn Sie lange genug warten und die Lernrate nicht zu groß ist).
Die Kostenfunktion hat also die Form einer Schüssel. Sind die Merkmale sehr unterschiedlich skaliert, kann es aber eine längliche Schüssel sein. Abbildung 4-7 illustriert das Gradientenverfahren für einen Trainingsdatensatz, bei dem die Merkmale 1 und 2 gleich skaliert sind (links), und für einen Trainingsdatensatz, bei dem die Beträge von Merkmal 1 sehr viel geringer sind als die von Merkmal 2 (rechts).4
Wie Sie sehen, bewegt sich auf der linken Seite das Gradientenverfahren direkt auf das Minimum zu und erreicht es schnell. Auf der rechten Seite bewegt es sich zunächst beinahe orthogonal zur Richtung des globalen Minimums. Hier muss der Algorithmus ein mehr oder weniger flaches Tal komplett durchwandern. Auch hier wird das Minimum erreicht, dies dauert aber seine Zeit.
Abbildung 4-7: Gradientenverfahren mit (links) und ohne (rechts) Skalierung von Merkmalen
|
|
Wenn Sie das Gradientenverfahren verwenden, sollten Sie sicherstellen, dass sämtliche Merkmale ähnlich skaliert sind (z.B. über die Klasse StandardScaler in Scikit-Learn). Andernfalls wird deutlich mehr Zeit vergehen, bis der Algorithmus konvergiert. |
Dieses Diagramm verdeutlicht außerdem, dass beim Trainieren eines Modells eine Kombination von Modellparametern gesucht wird, die eine Kostenfunktion (über die Trainingsdaten) minimieren. Es ist eine Suche im Parameterraum des Modells: Je mehr Parameter das Modell besitzt, desto mehr Dimensionen hat dieser Raum, und umso schwieriger ist die Suche: In einem 300-dimensionalen Heuhaufen nach einer Nadel zu suchen, ist viel komplizierter als in drei Dimensionen. Da die Kostenfunktion konvex ist, liegt die Nadel im Fall der linearen Regression glücklicherweise immer auf dem Boden einer Schüssel.
Batch-Gradientenverfahren
Um das Gradientenverfahren zu implementieren, müssen Sie den Gradienten der Kostenfunktion nach jedem Modellparameter θj berechnen. Anders ausgedrückt, Sie müssen berechnen, wie stark sich die Kostenfunktion ändert, wenn Sie θj ein wenig verändern. Dies nennt man eine partielle Ableitung. Sie verhält sich wie die Frage »Wie ist die Neigung des Bergs unter meinen Füßen, wenn ich mich nach Osten wende?«, um anschließend die gleiche Frage nach Norden gerichtet zu stellen (ebenso bei allen anderen Dimensionen, falls Sie sich ein Universum mit mehr als drei Dimensionen vorstellen können). Formel 4-5 berechnet die partielle Ableitung der Kostenfunktion nach dem Parameter θj, was sich auch als
Formel 4-5: Partielle Ableitung der Kostenfunktion
Anstatt partielle Ableitungen einzeln zu berechnen, können Sie Formel 4-6 verwenden, um alle zeitgleich zu berechnen. Der Gradientenvektor