Gradient Descent

Intuition des Gradientenverfahrens

Unter Gradient Descent versteht man einen Optimierungsalgorithmus, der das Minimum einer Funktion findet, indem er sich schrittweise in Richtung des stärksten Gefälles bewegt. Dies kann man sich anschaulich wie eine blinde Person vorstellen, die auf einem Berg steht, und einen im Tal gelegenen See erreichen möchte. Die Person kennt die Beschaffenheit der Landschaft nicht und weiß daher auch nicht, wo genau sich der See (und damit der tiefste Punkt) befindet. Trotzdem kann sie zum See gelangen, indem sie sich immer in die Richtung bewegt, in die der Abstieg am steilsten ist.

Ablauf des Algorithmus

1. Initialisierung einer Startposition auf der Fehleroberfläche
   Der erste Parameterwert (bzw. bei mehreren Parametern die erste Kombination) kann zufällig gewählt werden. Jedoch ist es von Vorteil, wenn der Algorithmus in der Nähe des globalen Minimums seine Suche beginnt.
   
2. Berechnung des Fehlers
   Mit dem gegebenen Startwert werden nun Modelldaten berechnet. Anhand eines zuvor festgelegten Abweichungsmaßes wird der Fehler ermittelt.
3. Bestimmung des Gradienten
   Für den Punkt, an dem sich der Algorithmus gerade befindet, wird berechnet, wie stark sich der Fehler verkleinert oder vergrößert, wenn der Parameterwert sich in einem kleinen Schritt in verschiedene Richtungen ändert. Der Gradient bezeichnet den Vektor, der in Richtung des steilsten Abstiegs zeigt.
4. Bewegung zu einem neuen Punkt auf der Fehleroberfläche
   Der Gradient führt nun zu einem neuen Parameterwert, für den der Fehler kleiner ist als zuvor. Dieser Punkt ist das neue vorläufige Minimum.
5. Berechnung des Fehlers für den neuen Punkt
   Der neue Parameterwert wird genutzt, um neue Modelldaten vorherzusagen. Wieder kann zwischen Modelldaten und empirischen Daten die Abweichung ermittelt werden.
6. Wiederholung der Schritte 3 – 5 bis sich der Fehler nicht mehr wesentlich verkleinert

Mögliche Probleme des Gradientenverfahrens

Zwar ist Gradient Descent ein Algorithmus, der ohne hohen Rechenaufwand zum Ziel führt, jedoch besitzt er auch einige Nachteile. Zu den größten Schwierigkeiten zählen lokale Minima. Da der Algorithmus immer dem steilsten Gefälle folgt, kann ein lokales Minimum, nachdem es erreicht wurde, nicht mehr verlassen werden, um einen tiefergelegenen Punkt außerhalb dieses Minimums zu erreichen. Dieses Problem kann verringert werden, indem man verschiedene Startpunkte wählt.

Des Weiteren muss die Schrittweite des Algorithmus beachtet werden. Ist sie zu klein, dauert es sehr lang, bis das Minimum erreicht wird. Eine zu große Schrittweite hingegen kann schmale Tiefpunkte überspringen, sodass das Minimum nicht gefunden wird.

Ein Problem für den Algorithmus sind zudem Diskontinuitäten in der Fehleroberfläche. An solchen Stellen, die nicht glatt und kontinuierlich verlaufen, kann kein Gradient berechnet werden, da die Funktion dort nicht differenzierbar ist. Ist dies der Fall, muss auf ableitungsfreie Algorithmen wie zum Beispiel das Simplex-Verfahren zurückgegriffen werden.

kkk Das Verhalten des Gradient-Descent-Algorithmus kann in der R-Shiny-App "Fitting" beobachtet und untersucht werden.