Formel 4-6: Gradientenvektor der Kostenfunktion
|
|
Beachten Sie, dass diese Formel bei jedem Schritt im Gradientenverfahren Berechnungen über den gesamten Trainingsdatensatz X vornimmt. Daher bezeichnet man diesen Algorithmus auch als Batch-Gradientenverfahren: Dieses Verfahren verwendet bei jedem Schritt den gesamten Stapel Trainingsdaten (vollständiges Gradientenverfahren wäre eigentlich ein besserer Name) und ist daher bei sehr großen Trainingsdatensätzen auffällig langsam (wir werden aber gleich einen viel schnelleren Algorithmus für das Gradientenverfahren kennenlernen). Das Gradientenverfahren skaliert dafür gut mit der Anzahl Merkmale; das Trainieren eines linearen Regressionsmodells mit Hunderttausenden von Merkmalen ist mit dem Gradientenverfahren sehr viel schneller als mit der Normalengleichung oder der SVD-Zerlegung. |
Sobald Sie den Gradientenvektor ermittelt haben, der bergauf weist, gehen Sie einfach in die entgegengesetzte Richtung, um sich bergab zu bewegen. Dazu müssen Sie
Formel 4-7: Schritt im Gradientenverfahren
θ(nächster Schritt) = θ – η
Betrachten wir eine schnelle Implementierung dieses Algorithmus:
eta = 0.1 # Lernrate
n_iterations = 1000
m = 100
theta = np.random.randn(2,1) # zufällige Initialisierung
for iteration in range(n_iterations):
gradients = 2/m * X_b.T.dot(X_b.dot(theta) - y)
theta = theta - eta * gradients
Das war nicht allzu schwer! Schauen wir uns einmal das berechnete theta an:
>>> theta
array([[4.21509616],
[2.77011339]])
Hey, das entspricht exakt dem von der Normalengleichung gefundenen Ergebnis! Das Gradientenverfahren hat perfekt funktioniert. Aber was wäre passiert, wenn wir eine andere Lernrate eta verwendet hätten? Abbildung 4-8 zeigt die ersten zehn Schritte im Gradientenverfahren mit drei unterschiedlichen Lernraten (die gestrichelte Linie steht für den Ausgangspunkt).
Abbildung 4-8: Gradientenverfahren mit unterschiedlichen Lernraten
Auf der linken Seite ist die Lernrate zu gering: Der Algorithmus findet zwar irgendwann eine Lösung, aber es wird lange dauern. In der Mitte sieht die Lernrate recht gut aus: Innerhalb weniger Iterationen ist der Algorithmus auf der Lösung konvergiert. Auf der rechten Seite ist die Lernrate zu hoch: Der Algorithmus divergiert, springt von einer Seite zur anderen und entfernt sich dabei immer weiter von der Lösung. Um eine geeignete Lernrate zu finden, können Sie eine Gittersuche durchführen (siehe Kapitel 2). Allerdings sollten Sie dabei die Anzahl der Iterationen begrenzen, sodass die Gittersuche Modelle eliminieren kann, bei denen das Konvergieren zu lange dauert.
Sie fragen sich vielleicht, wie man die Anzahl Iterationen bestimmen soll. Wenn diese zu gering ist, werden Sie beim Anhalten des Algorithmus noch immer weit von der optimalen Lösung entfernt sein. Ist sie aber zu hoch, verschwenden Sie Zeit, während sich die Modellparameter nicht mehr verändern. Eine einfache Lösung ist, die Anzahl Iterationen auf einen sehr großen Wert zu setzen, aber den Algorithmus anzuhalten, sobald der Gradientenvektor winzig klein wird – denn das passiert, wenn das Gradientenverfahren das Minimum (beinahe) erreicht hat. Der Gradientenvektor wird dann so winzig, wenn sein Betrag kleiner als eine sehr kleine Zahl x wird, was man auch als Toleranz bezeichnet.
Konvergenzrate
Wenn die Kostenfunktion konvex ist und ihre Steigung sich nicht abrupt ändert (wie es bei der MSE-Kostenfunktion der Fall ist), konvergiert das Batch-Gradientenverfahren mit einer gegebenen Lernrate immer zur optimalen Lösung, aber Sie müssen eventuell ein Weilchen warten – es kann O(1/ε) Iterationen erfordern, um das Optimum in einem Bereich ε zu erreichen (abhängig von der Form der Kostenfunktion). Wenn Sie die Toleranz ε durch 10 teilen (um eine genauere Lösung erhalten), muss der Algorithmus etwa 10 Mal länger laufen.
Stochastisches Gradientenverfahren
Das Hauptproblem beim Batch-Gradientenverfahren ist, dass es bei jedem Schritt den gesamten Trainingsdatensatz zum Berechnen der Gradienten verwendet, wodurch es bei großen Trainingsdatensätzen sehr langsam wird. Das andere Extrem ist das stochastische Gradientenverfahren (SGD), das bei jedem Schritt nur einen Datenpunkt zufällig auswählt und nur für diesen Punkt die Gradienten berechnet. Natürlich wird dadurch der Algorithmus viel schneller, da in jeder Iteration nur sehr wenige Daten verändert werden müssen. Damit ist das Trainieren auf riesigen Datensätzen möglich, da pro Iteration nur ein Datenpunkt verändert werden muss (SGD lässt sich auch als Out-of-Core-Algorithmus implementieren, siehe Kapitel 1).
Andererseits ist dieser Algorithmus wegen seiner stochastischen (d.h. zufälligen) Arbeitsweise wesentlich unregelmäßiger als das Batch-Gradientenverfahren: Anstatt sanft zum Minimum hinabzugleiten, hüpft die Kostenfunktion auf und ab und sinkt nur im Mittel. Mit der Zeit landet sie sehr nah am Minimum, springt dort aber weiter umher und kommt nie zur Ruhe (siehe Abbildung 4-9). Sobald der Algorithmus anhält, werden die endgültigen Parameter also gut, aber nicht optimal sein.
Bei einer sehr unregelmäßigen Kostenfunktion (wie in Abbildung 4-6) kann dies dem Algorithmus helfen, aus lokalen Minima wieder herauszuspringen. Daher hat das stochastische Gradientenverfahren im Vergleich zum Batch-Gradientenverfahren eine höhere Chance, das globale Minimum zu finden.
Die Zufälligkeit ist also gut, um lokalen Minima zu entfliehen, aber schlecht, da der Algorithmus beim Minimum nie zur Ruhe kommt. Eine Lösung dieses Dilemmas ist, die Lernrate schrittweise zu verringern. Die Schritte sind zu Beginn groß (was zu schnellen Fortschritten führt und beim Verlassen lokaler Minima hilft) und werden dann immer kleiner, sodass der Algorithmus beim globalen Minimum zur Ruhe kommt. Diesen Prozess bezeichnet man als Simulated Annealing, inspiriert vom Ausglühen in der Metallurgie, bei dem geschmolzenes Metall langsam abkühlt. Die Funktion zum Festlegen der Lernrate bezeichnet man als Learning Schedule. Wenn die Lernrate zu schnell reduziert wird, bleiben Sie in einem lokalen Minimum stecken oder sogar auf halber Strecke