Gradientenabstieg in Java

1. Einleitung

In diesem Tutorial lernen wir den Gradientenabstiegsalgorithmus kennen. Wir werden den Algorithmus in Java implementieren und ihn Schritt für Schritt veranschaulichen.

2. Was ist Gradientenabstieg?

Gradient Descent ist ein Optimierungsalgorithmus, mit dem ein lokales Minimum einer bestimmten Funktion ermittelt wird. Es wird häufig in Algorithmen für maschinelles Lernen auf hoher Ebene verwendet, um Verlustfunktionen zu minimieren.

Steigung ist ein anderes Wort für Steigung, und Abstieg bedeutet Abstieg. Wie der Name schon sagt, geht der Gradientenabstieg die Steigung einer Funktion hinunter, bis er das Ende erreicht.

3. Eigenschaften des Gradientenabfalls

Gradient Descent findet ein lokales Minimum, das sich vom globalen Minimum unterscheiden kann. Der lokale Startpunkt wird als Parameter für den Algorithmus angegeben.

Es ist ein iterativer Algorithmus , der in jedem Schritt versucht, sich den Hang hinunter zu bewegen und näher an das lokale Minimum heranzukommen.

In der Praxis wird der Algorithmus zurückverfolgt . In diesem Tutorial werden wir den Backtracking-Gradientenabstieg veranschaulichen und implementieren.

4. Schritt-für-Schritt-Abbildung

Der Gradientenabstieg benötigt eine Funktion und einen Startpunkt als Eingabe. Definieren und zeichnen wir eine Funktion:

Wir können an jedem gewünschten Punkt beginnen. Beginnen wir bei x = 1:

Im ersten Schritt geht der Gradientenabstieg mit einer vordefinierten Schrittgröße den Hang hinunter:

Als nächstes geht es mit der gleichen Schrittgröße weiter. Diesmal endet es jedoch mit einem größeren y als im letzten Schritt:

Dies zeigt an, dass der Algorithmus das lokale Minimum überschritten hat, sodass er mit einer verringerten Schrittgröße rückwärts geht:

Anschließend wird die Schrittgröße verringert und negiert , wenn der Strom y größer als das vorherige y ist. Die Iteration wird fortgesetzt, bis die gewünschte Genauigkeit erreicht ist.

Wie wir sehen können, hat Gradient Descent hier ein lokales Minimum gefunden, aber es ist nicht das globale Minimum. Wenn wir bei x = -1 anstelle von x = 1 beginnen, wird das globale Minimum gefunden.

5. Implementierung in Java

Es gibt verschiedene Möglichkeiten, den Gradientenabstieg zu implementieren. Hier berechnen wir nicht die Ableitung der Funktion, um die Richtung der Steigung zu ermitteln, daher funktioniert unsere Implementierung auch für nicht differenzierbare Funktionen.

Definieren wir Präzision und stepCoefficient und geben ihnen Anfangswerte:

double precision = 0.000001; double stepCoefficient = 0.1;

Im ersten Schritt haben wir kein vorheriges y zum Vergleich. Wir können den Wert von x entweder erhöhen oder verringern, um zu sehen, ob y abnimmt oder erhöht. Ein positiver stepCoefficient bedeutet, dass wir den Wert von x erhöhen .

Führen wir nun den ersten Schritt aus:

double previousX = initialX; double previousY = f.apply(previousX); currentX += stepCoefficient * previousY;

Im obigen Code ist f eine Funktion und initialX ist ein Double , wobei beide als Eingabe bereitgestellt werden.

Ein weiterer wichtiger Punkt ist, dass die Konvergenz des Gradientenabfalls nicht garantiert ist. Um zu vermeiden, dass Sie in der Schleife hängen bleiben, sollten Sie die Anzahl der Iterationen begrenzen:

int iter = 100;

Später werden wir den Iter bei jeder Iteration um eins dekrementieren . Folglich verlassen wir die Schleife mit maximal 100 Iterationen.

Nachdem wir ein vorheriges X haben , können wir unsere Schleife einrichten:

while (previousStep > precision && iter > 0) { iter--; double currentY = f.apply(currentX); if (currentY > previousY) { stepCoefficient = -stepCoefficient/2; } previousX = currentX; currentX += stepCoefficient * previousY; previousY = currentY; previousStep = StrictMath.abs(currentX - previousX); }

In jeder Iteration berechnen wir das neue y und vergleichen es mit dem vorherigen y . Wenn currentY größer als previousY ist , ändern wir unsere Richtung und verringern die Schrittgröße.

Die Schleife wird fortgesetzt, bis unsere Schrittweite unter der gewünschten Genauigkeit liegt . Schließlich können wir currentX als lokales Minimum zurückgeben:

return currentX;

6. Fazit

In diesem Artikel haben wir den Gradientenabstiegsalgorithmus mit einer schrittweisen Darstellung durchgearbeitet.

Wir haben Gradient Descent auch in Java implementiert. Der Code ist auf GitHub verfügbar.