Gradientenabstieg in Java

Problem

Die beste Gerade, ohne Raten

Die Kollegen in der Lektion über lineare Regression haben eine Gerade nach Augenmaß gewählt. Jetzt soll das Programm die beste selbst finden. Eine genaue Formel gibt es nur für die Gerade, und die nächsten Modelle (neuronale Netze) haben keine. Wir brauchen einen Weg, der immer funktioniert.

Die Aufgabe ist vorerst kleiner: Das Lager ist bekannt (6 Stunden), und wir suchen nur, wie viele Stunden je 100 km dazukommen, also w. Die Entfernung steht in Hundert km, damit die Zahlen klein bleiben:

// Entfernung in Hundert km (0.3 sind 30 km) und Stunden bis zur Lieferung
static final double[] DIST = {0.3, 0.5, 0.8, 1.0, 1.3, 1.6, 2.0, 2.4, 2.7, 3.0};
static final double[] HOURS = {10, 11, 17, 17, 23, 24, 31, 33, 40, 44};
static final double B = 6; // das Lager: 6 Stunden, das ist bekannt
static final double NUDGE = 0.0001;

Der Verlust ist derselbe MSE wie in der linearen Regression, jetzt nur als Funktion von w:

// der MSE der Geraden Stunden = w · Entfernung + 6
static double loss(double w) {
    double sum = 0;
    for (int i = 0; i < DIST.length; i++) {
        double error = w * DIST[i] + B - HOURS[i];
        sum += error * error;
    }
    return sum / DIST.length;
}

Wir könnten w = 0, 1, 2, … bis 100 probieren und den kleinsten Verlust nehmen. Bei einem w klappt das. Bei 10 Gewichten sind das 100¹⁰ Versuche, und ein neuronales Netz hat Millionen Gewichte.

Die Idee

Anstupsen und schauen

Statt alles auszuprobieren, stellst du dich auf ein w und fragst: Wenn ich ein Stück nach rechts gehe, sinkt der Verlust oder wächst er?

double before = loss(0);
double after = loss(0.01);
System.out.printf("w = 0: Verlust %.2f%n", before);
System.out.printf("w = 0.01: Verlust %.2f%n", after);
System.out.printf("Steigung: %.2f%n", (after - before) / 0.01);

w = 0: Verlust 485.00
w = 0.01: Verlust 484.21
Steigung: -78.97

Der Stups um 0,01 hat den Verlust um 0,79 gesenkt. Geteilt durch den Stups ist das die Steigung: −78,97, wie stark sich der Verlust pro Einheit w ändert. Das Minus heißt „rechts geht es bergab“.

Mit einem kleineren Stups (0,0001) ist die Steigung genauer. Hier an vier Stellen:

// die Steigung: stups w an und sieh, wie stark sich der Verlust ändert
static double slope(double w) {
    return (loss(w + NUDGE) - loss(w)) / NUDGE;
}

for (double w : new double[] {0, 6, 12, 18}) {
    System.out.printf("w = %.0f: Verlust %.2f, Steigung %.2f%n", w, loss(w), slope(w));
}

w = 0: Verlust 485.00, Steigung -79.00
w = 6: Verlust 127.21, Steigung -40.26
w = 12: Verlust 1.83, Steigung -1.53
w = 18: Verlust 108.87, Steigung 37.21

Die Steigung sagt zwei Dinge. Das Vorzeichen ist die Richtung: Minus heißt, w muss wachsen, Plus heißt, w muss schrumpfen (bei w = 18 sind wir schon am Boden vorbei). Die Größe sagt, wie weit wir sind: −79 ist weit vom Boden, −1,53 ist fast am Boden.

Die Idee

Ein Schritt gegen die Steigung

Die Regel ist eine Zeile: w -= Lernrate · Steigung. Gegen die Steigung, weil die Steigung bergauf zeigt. Bei negativer Steigung wird w größer, bei positiver kleiner. Je steiler, desto größer der Schritt.

Ein Durchgang (Steigung berechnen, einen Schritt machen) ist eine Epoche. Wir wiederholen:

double w = 0;
double rate = 0.1;
for (int epoch = 1; epoch <= 10; epoch++) {
    w -= rate * slope(w);
    System.out.printf("Epoche %d: w = %.2f, Verlust %.2f%n", epoch, w, loss(w));
}

Epoche 1: w = 7.90, Verlust 62.36
Epoche 2: w = 10.70, Verlust 9.28
Epoche 3: w = 11.69, Verlust 2.61
Epoche 4: w = 12.04, Verlust 1.77
Epoche 5: w = 12.17, Verlust 1.67
Epoche 6: w = 12.21, Verlust 1.65
Epoche 7: w = 12.23, Verlust 1.65
Epoche 8: w = 12.23, Verlust 1.65
Epoche 9: w = 12.24, Verlust 1.65
Epoche 10: w = 12.24, Verlust 1.65

Der erste Schritt ist groß (von 0 auf 7,90), weil die Kurve steil ist. Zum Boden hin wird die Steigung kleiner, und mit ihr die Schritte: Ab Epoche 7 bewegt sich w kaum noch. Der Verlust von 1,65 ist kleiner als die 1,83 der Geraden, die die Kollegen nach Augenmaß gewählt haben.

Das ist der Gradientenabstieg: Schritt für Schritt die Steigung des Verlusts hinunter, bis du am Boden bist. „Gradient“ ist die Steigung, wenn es mehr als einen Parameter gibt.

Sieh es dir an

Die Kugel auf der Kurve

static double slope(double w) {
    return (loss(w + NUDGE) - loss(w)) / NUDGE;
}

double w = 0;
double rate = 0.1;
for (int epoch = 1; epoch <= 10; epoch++) {
    w -= rate * slope(w);
}

Schritt für Schritt, in Worten

Unten: der Verlust für jedes w; die Kugel startet bei w = 0. Oben: die Gerade mit diesem w.
Stups w ein Stück an: Der Verlust sinkt. Die Steigung ist -79,00: Bergab geht es nach rechts.
Ein Schritt: w -= 0,1 · (-79,00), also wird w zu 7,90. Gegen die Steigung, also bergab.
Jeder Durchgang ist eine Epoche. Zum Boden hin wird die Steigung kleiner, und mit ihr die Schritte. Nach 10: w = 12,24.
Lernrate 0,01: Die graue Kugel kriecht. Nach 10 Epochen steht sie erst bei w = 5,96.
Lernrate 0,35: Die rote Kugel springt über den Boden, jedes Mal höher. Der Verlust wächst: Sie divergiert.
Mit 0,1 liegt die Kugel am Boden: w = 12,24, Verlust 1,65. Niemand hat w geraten: Es wurde gefunden.

Unten steht der Verlust für jedes w, und die Kugel ist das aktuelle w. Oben ist die Gerade mit diesem w über den Bestellungen: Wenn die Kugel den Boden erreicht, geht die Gerade durch die Punkte. Die graue und die rote Kugel sind dieselbe Regel mit einer anderen Lernrate.

Die Idee

Die Lernrate

Die Zahl, mit der die Steigung multipliziert wird, ist die Lernrate. Sie bestimmt, wie lang der Schritt ist. Drei Lernraten, je 20 Epochen (w nach den ersten drei und nach der zwanzigsten):

for (double rate : new double[] {0.01, 0.1, 0.35}) {
    double w = 0;
    List<String> seen = new ArrayList<>();
    for (int epoch = 1; epoch <= 20; epoch++) {
        w -= rate * slope(w);
        if (epoch <= 3 || epoch == 20) seen.add(String.format("%.2f", w));
    }
    System.out.printf("Lernrate %.2f: w = %s, Verlust %.2f%n", rate, String.join(", ", seen), loss(w));
}

Lernrate 0.01: w = 0.79, 1.53, 2.22, 9.02, Verlust 35.14
Lernrate 0.10: w = 7.90, 10.70, 11.69, 12.24, Verlust 1.65
Lernrate 0.35: w = 27.65, -7.18, 36.69, -1224.61, Verlust 4938139.70

0,01 ist zu klein. Die Richtung stimmt, aber nach 20 Epochen ist w erst 9,02. Es erreicht den Boden, aber nach Hunderten Epochen.
0,1 ist richtig. Drei Schritte, und w ist nah dran, dann pendelt es sich bei 12,24 ein.
0,35 ist zu groß. Der erste Schritt schießt über den Boden hinaus auf 27,65. Dort ist die Steigung noch größer, der nächste Schritt ist noch länger, und w fliegt auf −7,18, dann auf 36,69. Der Verlust wird zu Millionen: Der Abstieg divergiert.

Eine gute Lernrate wird nicht berechnet, sondern ausprobiert. Üblich ist, mit 0,1 oder 0,01 anzufangen und den Verlust pro Epoche zu beobachten: Wenn er wächst oder springt, ist die Lernrate zu groß; wenn er kaum sinkt, ist sie zu klein.

Die Idee

w und b zusammen

Bisher war b bekannt. Jetzt suchen wir es auch: Jeder Parameter hat seine eigene Steigung (du stupst nur ihn an), und jeder macht in derselben Epoche seinen eigenen Schritt.

// der MSE der Geraden Stunden = w · Entfernung + b
static double loss(double w, double b) {
    double sum = 0;
    for (int i = 0; i < DIST.length; i++) {
        double error = w * DIST[i] + b - HOURS[i];
        sum += error * error;
    }
    return sum / DIST.length;
}

double w = 0, b = 0, rate = 0.1;
for (int epoch = 1; epoch <= 1000; epoch++) {
    double slopeW = (loss(w + NUDGE, b) - loss(w, b)) / NUDGE;
    double slopeB = (loss(w, b + NUDGE) - loss(w, b)) / NUDGE;
    w -= rate * slopeW;
    b -= rate * slopeB;
    if (epoch == 1 || epoch == 10 || epoch == 100 || epoch == 1000)
        System.out.printf("Epoche %d: w = %.2f, b = %.2f, Verlust %.2f%n", epoch, w, b, loss(w, b));
}

Epoche 1: w = 9.77, b = 5.00, Verlust 29.77
Epoche 10: w = 12.21, b = 6.03, Verlust 1.66
Epoche 100: w = 12.41, b = 5.65, Verlust 1.62
Epoche 1000: w = 12.41, b = 5.64, Verlust 1.62

Nach 1.000 Epochen ist w = 12,41 Stunden pro 100 km und b = 5,64 Stunden. Die Formel für die beste Gerade aus der linearen Regression ergibt 0,1241 Stunden pro km und 5,64 Stunden: dieselbe Gerade. Der Abstieg kennt die Formel nicht; er geht einfach bergab.

Die Idee

Die Skala der Merkmale

Warum stand die Entfernung in Hundert km? Hier sind dieselben Bestellungen in km:

// dieselben Bestellungen, aber die Entfernung ist in km
static final double[] KM = {30, 50, 80, 100, 130, 160, 200, 240, 270, 300};
static final double[] HOURS = {10, 11, 17, 17, 23, 24, 31, 33, 40, 44};
static final double NUDGE = 0.0001;

Bei einer Lernrate von 0,1 divergiert der Abstieg schon in der ersten Epoche:

double w = 0, b = 0, rate = 0.1;
for (int epoch = 1; epoch <= 3; epoch++) {
    double slopeW = (loss(w + NUDGE, b) - loss(w, b)) / NUDGE;
    double slopeB = (loss(w, b + NUDGE) - loss(w, b)) / NUDGE;
    w -= rate * slopeW;
    b -= rate * slopeB;
    System.out.printf("Lernrate 0.1, Epoche %d: w = %.0f%n", epoch, w);
}

Lernrate 0.1, Epoche 1: w = 977
Lernrate 0.1, Epoche 2: w = -6304921
Lernrate 0.1, Epoche 3: w = 40699231079

Die Steigung für w wächst mit der Größe des Merkmals: Jedes w wird mit 300 statt mit 3 multipliziert, und bei w = 0 ist die Steigung fast −10.000. Also senken wir die Lernrate, bis es nicht mehr divergiert:

double w = 0, b = 0, rate = 0.00002;
for (int epoch = 1; epoch <= 1000; epoch++) {
    double slopeW = (loss(w + NUDGE, b) - loss(w, b)) / NUDGE;
    double slopeB = (loss(w, b + NUDGE) - loss(w, b)) / NUDGE;
    w -= rate * slopeW;
    b -= rate * slopeB;
    if (epoch == 10 || epoch == 100 || epoch == 1000)
        System.out.printf("Epoche %d: w = %.4f, b = %.4f, Verlust %.2f%n", epoch, w, b, loss(w, b));
}

Epoche 10: w = 0.1513, b = 0.0013, Verlust 9.44
Epoche 100: w = 0.1513, b = 0.0063, Verlust 9.42
Epoche 1000: w = 0.1510, b = 0.0563, Verlust 9.28

Jetzt divergiert es nicht mehr, aber b bewegt sich kaum: Nach 1.000 Epochen ist es 0,06 statt 5,64, und w steht bei 0,151 statt bei 0,124. Für b ist der Schritt zu klein. Eine Lernrate passt nicht für beide. Die Lösung ist die Skala: Die Merkmale werden vor dem Training auf einen ähnlichen Bereich gebracht (hier durch 100 geteilt; oft zieht man den Mittelwert ab und teilt durch die Streuung). Ohne das schafft keine Lernrate die Aufgabe.

Probier es aus

Sag die Ausgabe voraus

w ist 2, die Steigung dort ist −20, und die Lernrate ist 0,1. Was gibt ein Schritt aus?

double w = 2;
double slope = -20;
double rate = 0.1;
w -= rate * slope;
System.out.printf("%.1f%n", w);

Antwort

-18.0

0.0

4.0

Probier es aus

Ergänze

Welche Operation macht den Schritt gegen die Steigung?

for (int epoch = 1; epoch <= 10; epoch++) {
    w  rate * slope(w);
}

Probier es aus

Finde den Fehler

Ein Kollege schreibt einen Abstieg, aber der Verlust pro Epoche wächst immer schneller. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Die Idee

Wenn der Abstieg wehtut

Die falsche Lernrate. Zu groß divergiert, zu klein kriecht. Wenn der Verlust pro Epoche wächst oder springt, senke zuerst die Lernrate.
Merkmale auf verschiedenen Skalen. km und die Zahl der Pakete in einer Zeile: Die Steigungen unterscheiden sich um das Hundertfache, und keine Lernrate passt. Skaliere die Merkmale vor dem Training.
Nicht nur ein Tal. Der Verlust einer Geraden ist eine glatte Schüssel mit einem Boden. Bei neuronalen Netzen hat die Kurve viele Täler und Plateaus: Der Abstieg erreicht irgendeinen Boden, nicht unbedingt den tiefsten, und das Ergebnis hängt vom Start-w ab.
Wann man aufhört. Hier sind die Epochen fest. In der Praxis hörst du auf, wenn der Verlust nicht mehr sinkt, und ob das Modell für neue Bestellungen gut ist, misst man getrennt (das Modell auswerten).
Die Kosten. Jede Epoche geht durch alle Daten. Bei Millionen Beispielen und Millionen Gewichten läuft das Training Stunden auf speziellen Servern; diese Infrastruktur (Maschinen für das Training, das Modell in Produktion betreiben) wird im DevOps-Kurs ZeroToOps gelehrt.

Genauer, für Neugierige

Die Steigung per Formel. Das Anstupsen ist eine Näherung. Für den MSE hat die Steigung eine exakte Formel (die Ableitung): 2 · Mittelwert von Fehler · Entfernung. Hier beide Wege nebeneinander:

// die Steigung per Formel: 2 · Mittelwert von Fehler · Entfernung
static double slopeByFormula(double w) {
    double sum = 0;
    for (int i = 0; i < DIST.length; i++) {
        double error = w * DIST[i] + B - HOURS[i];
        sum += error * DIST[i];
    }
    return 2 * sum / DIST.length;
}

for (double w : new double[] {0, 12}) {
    System.out.printf("bei w = %.0f: mit Zahlen %.2f, per Formel %.2f%n", w, slope(w), slopeByFormula(w));
}

bei w = 0: mit Zahlen -79.00, per Formel -79.00
bei w = 12: mit Zahlen -1.53, per Formel -1.53

Sie stimmen auf die zweite Stelle überein. Die Formel ist schneller (ein Durchgang statt zwei pro Parameter), deshalb berechnen Bibliotheken Ableitungen automatisch aus dem Code des Modells. Das ist Backpropagation, aus der Lektion über das Training eines Netzes.

Der Gradient. Bei vielen Parametern sind ihre Steigungen zusammen der Gradient (ein Vektor). Der Schritt ist für jeden derselbe: Parameter -= Lernrate · seine Steigung.

Teile der Daten. Bei Millionen Beispielen ist eine Epoche langsam. Deshalb wird die Steigung auf einem kleinen zufälligen Teil berechnet (einem Mini-Batch), und es gibt viel mehr Schritte. Das ist der stochastische Gradientenabstieg (SGD). Seine verbesserten Versionen (zum Beispiel Adam) behalten außerdem einen „Schwung“ der vorherigen Schritte.

Übung

Der Kurier, selbst gelernt

Löse die Aufgabe in deinem Editor.

In der Lektion über lineare Regression haben die Kollegen drei Geraden für den Preis des Kuriers verglichen. Jetzt soll das Programm die beste selbst finden:

// Pakete: Gewicht in kg und Preis des Kuriers in €
static final double[] KG = {0.5, 1.0, 1.5, 2.0, 3.0, 4.0, 5.0, 6.0};
static final double[] EUR = {4.10, 4.60, 5.00, 5.60, 6.40, 7.50, 8.30, 9.40};
static final double NUDGE = 0.0001;

Schreibe die Verlustfunktion (MSE) für Preis = w · kg + b, dann 1.000 Epochen Gradientenabstieg für w und b zusammen, ab w = 0 und b = 0, mit einer Lernrate von 0,05 und einem Stups von 0,0001. Gib w, b und den Verlust mit je 4 Stellen aus.

w = 0.9538, b = 3.6204, MSE 0.0038

Weitere Aufgaben

Die Lernrate. Lass es mit einer Lernrate von 0,1 laufen. Was passiert? Finde die größte Lernrate, bei der der Verlust noch sinkt.
Aufhören. Statt 1.000 Epochen hörst du auf, wenn beide Steigungen betragsmäßig kleiner als 0,001 sind. Nach wie vielen Epochen?
Vergleich. Um wie viel ist der Verlust kleiner als bei der besten Geraden der Kollegen (A, MSE 0,0144)?

Test

Teste dich

1. Die Steigung des Verlusts beim aktuellen w ist −40. In welche Richtung muss w sich bewegen?Nirgendwohin: Die Steigung ist zu großNach unten: gegen die Zahl −40Nach oben: Eine negative Steigung heißt, der Verlust sinkt, wenn w wächst

2. Bei einer Lernrate von 0,35 springt w auf 27,65, −7,18, 36,69, und der Verlust wächst. Was tust du?Die Lernrate senken: Die Schritte schießen immer weiter über den Boden hinausDie Lernrate erhöhen, damit es schneller ankommtMehr Epochen laufen lassen

3. Bei einer Lernrate von 0,01 ist w nach 10 Epochen 5,96, und der Boden liegt bei etwa 12. Ist die Lernrate falsch?Nein, 5,96 ist das beste wJa: w muss bei jeder Lernrate 12 seinEs geht in die richtige Richtung, aber langsam: Es braucht viel mehr Epochen oder eine größere Lernrate

4. Warum läuft der Abstieg mit der Entfernung in km (30 bis 300) davon, und zwar bei einer Lernrate, die mit Hundert km (0,3 bis 3) funktioniert?Weil die Gerade in km eine andere Gerade istWeil km keine Zahl sindDie Steigung für w wächst mit der Größe des Merkmals: In km ist sie hundertmal größer, und der Schritt auch

5. Der Abstieg für die Lieferzeit-Gerade erreicht w = 12,41 und b = 5,64. Die Formel aus der linearen Regression ergibt 0,1241 h/km und 5,64 h. Wozu dann überhaupt der Abstieg?Weil der Abstieg genauer ist als die FormelEine Formel gibt es nur für einfache Modelle; der Abstieg funktioniert für jedes Modell, dessen Verlust du berechnen kannstWeil die Formel falsch ist

Gradientenabstieg

Cookies