+= lr
elif loss(X, Y, w - lr, b) < current_loss:
w -= lr
elif loss(X, Y, w, b + lr) < current_loss:
b += lr
elif loss(X, Y, w, b - lr) < current_loss:
b -= lr
else:
return w, b
raise Exception("Couldn't converge within %d iterations" % iterations)
Bei jeder Iteration modifiziert dieser Algorithmus entweder w oder b und sucht nach den Werten, bei denen der Verlust möglichst gering ist. Das allerdings kann schiefgehen, denn wenn wir w optimieren, kann das den durch b verursachten Verlust erhöhen und umgekehrt. Um dieses Problem zu vermeiden und so nah wie möglich an den kleinstmöglichen Verlust heranzukommen, könnten wir beide Parameter gleichzeitig modifizieren. Je mehr Parameter wir haben, umso wichtiger wird das.
Um w und b gemeinsam zu optimieren, müssen wir alle möglichen Kombinationen ausprobieren: sowohl w als auch b vergrößern, w vergrößern und b verkleinern, w vergrößern und b unverändert lassen, w verkleinern und … usw. usf. Die Gesamtzahl möglicher Kombinationen einschließlich des Falls, bei dem alle Parameter unverändert bleiben, ist 3 hoch die Anzahl der Parameter. Bei zwei Parametern sind das 32 gleich 9 Kombinationen.
Es hört sich nicht weiter schlimm an, loss() pro Iteration neunmal aufzurufen. Bei zehn Parametern haben wir es allerdings schon mit 310 Kombinationen zu tun, also fast 60.000 Aufrufen pro Iteration. Eine Anzahl von zehn Parametern ist auch alles andere als übertrieben. Weiter hinten in diesem Buch verwenden wir Modelle mit Hunderttausenden von Parametern. Bei solch riesigen Modellen käme ein Algorithmus, der jede Parameterkombination ausprobiert, nicht mehr von der Stelle. Wir sollten uns daher lieber gleich von diesem langsamen Code verabschieden.
Außerdem weist train() in der jetzigen Form ein noch gewichtigeres Problem auf: Die Funktion ändert die Parameter in Schritten, die genauso groß sind wie die Lernrate. Bei großer lr ändern sich die Parameter schnell, was zwar den Trainingsvorgang beschleunigt, das Endergebnis aber weniger genau macht, da jeder Parameter jetzt ein Vielfaches des großen lr betragen muss. Um die Genauigkeit zu verbessern, brauchen wir eine kleine lr, die allerdings zu einem langsameren Training führt. Geschwindigkeit und Genauigkeit gehen jeweils auf Kosten des anderen, wobei wir jedoch beides brauchen.
Aus diesen Gründen ist unser bisheriger Code nichts weiter als ein Hack. Wir müssen ihn durch einen besseren Algorithmus ersetzen – einen, der train() sowohl schnell als auch genau macht.
Das Gradientenverfahren
Wir brauchen einen besseren Algorithmus für train(). Die Aufgabe dieser Funktion besteht darin, die Parameter zu finden, bei denen der Verlust minimal wird. Schauen wir uns also loss() genauer an:
def loss(X, Y, w, b):
return np.average((predict(X, w, b) - Y) ** 2)
Betrachten Sie die Argumente dieser Funktion. X und Y enthalten die Eingabevariablen und die Labels, ändern sich also nicht von einem Aufruf von loss() zum nächsten. Zur Vereinfachung wollen wir b vorübergehend auch konstant auf 0 setzen. Unsere einzige Variable ist damit w.
Wie ändert sich nun der Verlust mit der Veränderung von w? Ich habe ein kleines Programm geschrieben, das den Verlauf von loss() für w im Bereich von –1 bis 4 ausgibt und das Minimum mit einem grünen Kreuz markiert. Das sehen Sie in der folgenden Abbildung. (Den Code finden Sie wie üblich im Begleitmaterial zu diesem Buch.)
Eine hübsche Kurve – nennen wir sie die Verlustkurve. Sinn und Zweck von train() besteht darin, die markierte Stelle unten in dieser Kurve zu finden, also den Wert von w, der zu einem minimalen Verlust führt. Bei diesem w nähert sich unser Modell den Datenpunkten am besten an.
Stellen Sie sich diese Kurve als ein Tal vor, an dessen Hang irgendwo eine Wanderin steht, die zu ihrem Lager an der gekennzeichneten Stelle unterwegs ist. Allerdings ist es so dunkel, dass sie nur den Boden in unmittelbarer Nähe ihrer Füße sehen kann. Um das Lager zu finden, kann sie sich eines ganz einfachen Verfahrens bedienen: Sie geht immer in die Richtung des steilsten Abstiegs. Sofern es in dem Gelände keine Löcher oder Klippen gibt – was bei unserer Verlustfunktion nicht der Fall ist –, führt jeder Schritt die Wanderin näher an ihr Lager heran.
Um dieses Prinzip in Code umsetzen zu können, müssen wir die Steigung der Verlustkurve bestimmen. Ein Maß dafür ist der Gradient. Vereinbarungsgemäß ist der Gradient an einem gegebenen Punkt der Kurve ein »Pfeil«, der bergauf weist.
Um den Gradienten zu bestimmen, verwenden wir ein mathematisches Werkzeug: die Ableitung des Verlusts nach dem Gewicht, geschrieben ∂L/∂w. Formal ausgedrückt, bestimmt die Ableitung an einem gegebenen Punkt, wie stark sich L an diesem Punkt bei kleinen Abweichungen von w ändert. Was geschieht mit dem Verlust, wenn wir das Gewicht ein winziges bisschen erhöhen? In dem vorstehenden Diagramm ist die Ableitung negativ, da der Verlust abnimmt. Bei positiver Ableitung dagegen steigt der Verlust. Am Minimum der Kurve, also an dem mit dem Kreuz markierten Punkt, ist die Kurve eben und die Ableitung damit null.
Beachten Sie, dass unsere Wanderin in die dem Gradienten entgegengesetzte Richtung gehen muss, um das Minimum zu erreichen. An einem Punkt mit negativer Ableitung wie in dem Bild muss sie sich also in positiver Richtung bewegen. Ihre Schrittweite muss proportional zum Betrag der Ableitung sein. Ist die Ableitung betragsmäßig groß, verläuft die Kurve steil. Das Lager ist dann noch weit entfernt. Daher kann die Wanderin vertrauensvoll große Schritte machen. Wenn sie sich dem Lager nähert, wird die Ableitung jedoch kleiner und damit auch ihre Schrittweite.
Dieser Algorithmus ist das Gradientenverfahren oder Verfahren des steilsten Abstiegs. Zu seiner Implementierung ist ein bisschen Mathematik gefordert.
Ein wenig Mathematik
Als Erstes übersetzen wir unsere Formel für den mittleren quadratischen Fehler in die gute, alte mathematische Schreibweise:
Falls Ihnen diese Schreibweise nicht bekannt vorkommt: Das Symbol S ist das Summenzeichen, und das m steht für die Anzahl der Beispiele. Diese Formel bedeutet: »Summiere die quadrierten Fehler aller Beispiele von Beispiel 1 bis Beispiel m und dividiere das Ergebnis durch die Anzahl der Beispiele.«
Bei den verschiedenen x und y handelt es sich um die Eingabevariablen und Labels, also um Konstanten. Auch m ist konstant, da sich die Anzahl der Beispiele nicht ändert. Da wir b vorübergehend auf 0 gesetzt haben, ist auch dieser Wert konstant. Wir werden b in Kürze wieder benutzen, aber vorläufig ist w der einzige Wert in der Formel, der sich ändert.
Nun müssen wir Betrag und Richtung des Gradienten bestimmen, also die Ableitung von L nach w. Wenn Sie sich noch an die Analysis in der Oberstufe erinnern, können Sie die Ableitung selbst berechnen. Wenn nicht, ist das aber auch kein Beinbruch. Jemand anderes hat die Arbeit schon für uns erledigt:
Die Ableitung des Verlusts sieht ähnlich aus wie der Verlust selbst, allerdings ist die Quadrierung verloren gegangen. Außerdem wird jeder Summand mit x und das Endergebnis mit 2 multipliziert. In diese Formel können wir nun beliebige Werte für w eingeben und erhalten den Gradienten an diesem Punkt als Ergebnis.
Im Code sieht diese Formel wie folgt aus. Auch hier ist b wieder auf 0 fixiert.
03_gradient/gradient_descent_without_bias.py