Zum Inhalt
wannacode

Überanpassung: Das Modell, das auswendig lernt

Kurz gesagt: Überanpassung (Overfitting) heißt: Das Modell lernt die Trainingsdaten auswendig und versagt bei neuen; die Validierung entlarvt das, und ein einfacheres Modell oder Regularisierung heilt es.

Problem

Das perfekte Modell, das 5 Minuten verspricht

Der Shop sagt dem Kunden, wann die Bestellung ankommt. Die Zeit wird aus früheren Bestellungen gelernt, wie in der ersten Lektion über maschinelles Lernen: Das Merkmal ist die Entfernung zum Kunden, das Label sind die Minuten bis zur Tür.

Ein Kollege probiert zwei Modelle an 8 früheren Bestellungen aus. Die Gerade aus der linearen Regression liegt um ein paar Minuten daneben. Seine Kurve liegt nie daneben:

const line = fit(train, 1, 0);
const curve = fit(train, 7, 0);
console.log(`Gerade (Grad 1): MSE im Training ${mse(line, train).toFixed(2)}`);
console.log(`Kurve (Grad 7): MSE im Training ${mse(curve, train).toFixed(2)}`);
for (const km of [3.5, 21.5])
  console.log(`Bestellung ${km.toFixed(1)} km: Gerade ${predict(line, km).toFixed(0)} Min., Kurve ${predict(curve, km).toFixed(0)} Min.`);
Ausgabe
Gerade (Grad 1): MSE im Training 9.35
Kurve (Grad 7): MSE im Training 0.00
Bestellung 3.5 km: Gerade 24 Min., Kurve 5 Min.
Bestellung 21.5 km: Gerade 70 Min., Kurve 79 Min.

Die Kurve hat MSE 0,00: perfekt für die Vergangenheit. Dann kommt eine neue Bestellung, 3,5 km entfernt. Die Kurve verspricht 5 Minuten, die Gerade 24. Die echte Zeit sind 22 Minuten. Bei einer Bestellung in 21,5 km Entfernung sagt die Kurve 79, die Gerade 70, und die Wahrheit ist 68.

Das Modell, das sich bei der Vergangenheit nie irrt, ist das schlechteste für die Zukunft. Das ist Überanpassung (Overfitting): Das Modell hat die Beispiele samt Rauschen auswendig gelernt, statt den Zusammenhang zu lernen.

Sieh es dir an

Die Kurve vom Grad d

Die Gerade ist w₀ + w₁ · x. Die Kurve fügt Potenzen von x hinzu: w₀ + w₁ · x + w₂ · x² + … + w₇ · x⁷. Das ist ein Polynom vom Grad 7 mit 8 Gewichten. Grad 1 ist die Gerade.

Die Bestellungen sind ein Beispiel, sehen aber aus wie echte: Weiter heißt länger, mit ein paar Minuten Rauschen (Verkehr, Aufzug, Warten an der Tür). Außer den 8 fürs Training gibt es 8 weitere für die Validierung und 8 für den Test. Warum drei Gruppen, steht in der nächsten Karte.

// Training: km bis zum Kunden und Minuten bis zur Tür
const train = [[2, 19], [5, 23], [7, 38], [10, 42], [13, 52], [16, 54], [19, 63], [22, 69]];
// Validierung: andere Bestellungen, nur für die Auswahl
const val = [[3, 24], [6.5, 31], [9, 36], [12, 44], [15, 52], [18, 57], [21, 70], [4, 27]];
// Test: wird einmal ausgeführt, ganz am Ende
const test = [[3.5, 22], [8, 34], [11, 38], [14, 51], [17, 59], [20, 63], [6, 30], [21.5, 68]];

x ist die Entfernung, um 12 km verschoben und zehnmal kleiner gemacht. Sonst ist 22⁷ etwa 2,5 Milliarden, und die Rechnungen verlieren an Genauigkeit.

// x ist die Entfernung um 12 km, zehnmal kleiner
function powers(km, degree) {
  const x = (km - 12) / 10;
  const p = [1];
  for (let j = 1; j <= degree; j++) p.push(p[j - 1] * x);
  return p;
}


function predict(w, km) {
  const p = powers(km, w.length - 1);
  let sum = 0;
  for (let j = 0; j < w.length; j++) sum += w[j] * p[j];
  return sum;
}


function mse(w, data) {
  let sum = 0;
  for (const [km, minutes] of data) {
    const e = predict(w, km) - minutes;
    sum += e * e;
  }
  return sum / data.length;
}

Die Gewichte könntest du mit dem Gradientenabstieg finden, aber bei Grad 7 braucht er Millionen Schritte. Es gibt eine Abkürzung: Die besten Gewichte sind die Lösung eines Gleichungssystems mit so vielen Gleichungen, wie es Gewichte gibt. Das System wird mit dem Gauß-Verfahren gelöst, wie in der Schule, nur mit 8 Unbekannten. Der Code steht hier, damit alles sichtbar ist. Du musst ihn nicht Zeile für Zeile verfolgen:

// die besten Gewichte direkt: ein Gleichungssystem
function fit(data, degree, lambda) {
  const m = degree + 1;
  const a = Array.from({ length: m }, () => new Array(m).fill(0));
  const b = new Array(m).fill(0);
  for (const [km, minutes] of data) {
    const p = powers(km, degree);
    for (let i = 0; i < m; i++) {
      b[i] += p[i] * minutes;
      for (let j = 0; j < m; j++) a[i][j] += p[i] * p[j];
    }
  }
  // die Strafe: λ auf der Diagonale, nicht auf dem Achsenabschnitt
  for (let i = 1; i < m; i++) a[i][i] += lambda;
  return solve(a, b);
}
// Gauß-Verfahren: löst a · w = b
function solve(a, b) {
  const n = b.length;
  for (let c = 0; c < n; c++) {
    let p = c;
    for (let r = c + 1; r < n; r++)
      if (Math.abs(a[r][c]) > Math.abs(a[p][c])) p = r;
    [a[c], a[p]] = [a[p], a[c]];
    [b[c], b[p]] = [b[p], b[c]];
    for (let r = c + 1; r < n; r++) {
      const f = a[r][c] / a[c][c];
      for (let k = c; k < n; k++) a[r][k] -= f * a[c][k];
      b[r] -= f * b[c];
    }
  }
  const x = new Array(n).fill(0);
  for (let r = n - 1; r >= 0; r--) {
    let s = b[r];
    for (let k = r + 1; k < n; k++) s -= a[r][k] * x[k];
    x[r] = s / a[r][r];
  }
  return x;
}

Die Zeile mit der Strafe bekommt vorerst 0. Dazu kommen wir noch.

Die Idee

Training, Validierung und Test

In der Lektion zur Auswertung hatten die Daten zwei Gruppen: Training und Test. Jetzt braucht es eine dritte. Der Grund: Wir wollen den Grad wählen. Wählen wir ihn nach dem Trainingsfehler, gewinnt immer 7, weil sein Fehler 0 ist. Wählen wir ihn nach dem Test, hat der Test an einer Entscheidung teilgenommen und ist am Ende nicht mehr ehrlich.

Die Daten sind also in drei Gruppen:

  • Trainingsdaten: Daraus werden die Gewichte gelernt;
  • Validierungsdaten: Darauf werden die Modelle verglichen und der Grad gewählt;
  • Testdaten: Einmal am Ende für das gewählte Modell ausgeführt.
console.log("MSE: Training / Validierung");
let best = 1;
let bestVal = Infinity;
for (let degree = 1; degree <= 7; degree++) {
  const w = fit(train, degree, 0);
  const trainErr = mse(w, train);
  const valErr = mse(w, val);
  console.log(`Grad ${degree}: ` +
    `${trainErr.toFixed(2)} / ${valErr.toFixed(2)}`);
  if (valErr < bestVal) {
    bestVal = valErr;
    best = degree;
  }
}
const testErr = mse(fit(train, best, 0), test);
console.log(`gewählter Grad: ${best}, ` +
  `Test: ${testErr.toFixed(2)}`);
Ausgabe
MSE: Training / Validierung
Grad 1: 9.35 / 3.64
Grad 2: 6.74 / 9.35
Grad 3: 6.61 / 9.09
Grad 4: 5.64 / 11.95
Grad 5: 3.75 / 18.81
Grad 6: 3.30 / 29.06
Grad 7: 0.00 / 121.20
gewählter Grad: 1, Test: 5.57

Der Trainingsfehler fällt mit jedem Grad: 9,35, 6,74, …, 0,00. Der Validierungsfehler wächst: 3,64, 9,35, …, 121,20. Je mehr Gewichte die Kurve hat, desto besser merkt sie sich die 8 Punkte und desto schlechter errät sie neue. Die Validierung wählt Grad 1, die Gerade, und ihr Testfehler ist 5,57 (die Wurzel aus 5,57 ist etwa 2,4 Minuten mittlerer Fehler).

Eines wirkt seltsam: Die Gerade hat auf der Validierung einen kleineren Fehler (3,64) als im Training (9,35). Bei 8 Bestellungen ist der Zufall groß: Die Validierung hat zufällig Bestellungen bekommen, die näher an der Geraden liegen. Deshalb gilt bei wenigen Daten: Traue der zweiten Ziffer nicht.

Sieh es dir an

Die Kurve verbiegt sich

console.log("MSE: Training / Validierung");
let best = 1;
let bestVal = Infinity;
for (let degree = 1; degree <= 7; degree++) {
  const w = fit(train, degree, 0);
  const trainErr = mse(w, train);
  const valErr = mse(w, val);
  console.log(`Grad ${degree}: ` +
    `${trainErr.toFixed(2)} / ${valErr.toFixed(2)}`);
  if (valErr < bestVal) {
    bestVal = valErr;
    best = degree;
  }
}
const testErr = mse(fit(train, best, 0), test);
console.log(`gewählter Grad: ${best}, ` +
  `Test: ${testErr.toFixed(2)}`);
Schritt für Schritt, in Worten
  1. 8 Trainingsbestellungen: die Entfernung in km und die Minuten bis zur Tür. Je weiter, desto länger, mit etwas Rauschen.
  2. Grad 1 ist eine Gerade. Sie verfehlt die meisten Punkte um ein paar Minuten: MSE im Training 9,35.
  3. Jeder Grad fügt ein Gewicht hinzu. Die Kurve biegt sich stärker und kommt jedem Trainingspunkt näher.
  4. Grad 7 hat 8 Gewichte für 8 Punkte und geht durch jeden: MSE im Training 0,00. Es sieht perfekt aus.
  5. Jetzt 8 andere Bestellungen, für die Validierung. Zwischen den Trainingspunkten schlägt die Kurve aus: MSE der Validierung 121,20.
  6. Für jeden Grad: Der Trainingsfehler fällt, der Validierungsfehler wächst. Die Validierung wählt Grad 1, die Gerade.
  7. Ein anderes Heilmittel: Grad 7 behalten, aber große Gewichte bestrafen. Mit λ = 0,1 beruhigt sich die Kurve: MSE der Validierung 9,55.
  8. Die Kurve, die die Trainingspunkte auswendig gelernt hat, ist bei neuen Bestellungen die schlechteste. Testfehler: 5,57 für die Gerade, 9,96 für die Kurve mit λ = 0,1.

Die Kurve vom Grad 7 trifft jeden blauen Punkt und verfehlt die orangen um Dutzende Minuten. Die Balken darunter sagen dasselbe für jeden Grad: Blau (Training) fällt, Orange (Validierung) wächst.

Probier es aus

Finde den Fehler

Ein Kollege wählt den Grad so. Sein Programm wählt immer 7. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Die Idee

Drei Heilmittel

1. Ein einfacheres Modell. Die Validierung hat es schon gewählt: die Gerade. Ist der Zusammenhang fast gerade, reicht die Gerade, und jedes zusätzliche Gewicht ist Platz für Rauschen.

2. Mehr Daten. Die Kurve vom Grad 7 hat 8 Gewichte. Mit 8 Punkten kann sie genau durch jeden gehen. Mit 16 Punkten geht das nicht, sie muss zwischen ihnen hindurch, und das glättet das Rauschen:

const both = [...train, ...val];
for (const data of [train, both])
  console.log(`Grad 7, ${data.length} Bestellungen: Test ${mse(fit(data, 7, 0), test).toFixed(2)}`);
Ausgabe
Grad 7, 8 Bestellungen: Test 84.44
Grad 7, 16 Bestellungen: Test 9.41
[...train, ...val] ist ein neues Array mit den Zeilen beider.

Der Testfehler fällt von 84,44 auf 9,41. Hier wird die Validierung auch fürs Training benutzt, also bleibt nichts übrig, womit man den Grad wählen könnte. In einem echten Projekt nimmt man dafür die Kreuzvalidierung (siehe „Mehr“).

3. Eine Strafe für große Gewichte. Die sich windende Kurve hat riesige Gewichte: Das größte ist 571,59. Die Kurve trifft jeden Punkt, weil riesige Gewichte mit verschiedenen Vorzeichen sich fast aufheben und der Rest die Kurve verbiegt. Die Regularisierung addiert zum Fehler eine Strafe: λ mal die Summe der quadrierten Gewichte. Jetzt sucht das Training Gewichte, die die Punkte treffen und zugleich klein sind. Im Code ist das die einzige Strafzeile in fit. λ wird wie der Grad mit der Validierung gewählt:

// das größte Gewicht, ohne den Achsenabschnitt
function biggest(w) {
  return Math.max(...w.slice(1).map(Math.abs));
}
console.log("Training / Validierung, max |w|");
let bestLambda = 0;
let bestVal = Infinity;
for (const lambda of [0, 0.001, 0.01, 0.1, 1, 10]) {
  const w = fit(train, 7, lambda);
  const trainErr = mse(w, train);
  const valErr = mse(w, val);
  console.log(`λ ${lambda.toFixed(3)}: ` +
    `${trainErr.toFixed(2)} / ${valErr.toFixed(2)}, ` +
    `${biggest(w).toFixed(2)}`);
  if (valErr < bestVal) {
    bestVal = valErr;
    bestLambda = lambda;
  }
}
const testErr = mse(fit(train, 7, bestLambda), test);
console.log(`gewähltes λ: ${bestLambda.toFixed(3)}, ` +
  `Test: ${testErr.toFixed(2)}`);
Ausgabe
Training / Validierung, max |w|
λ 0.000: 0.00 / 121.20, 571.59
λ 0.001: 2.80 / 26.49, 36.79
λ 0.010: 3.59 / 17.08, 19.16
λ 0.100: 5.72 / 9.55, 20.21
λ 1.000: 19.95 / 16.71, 13.35
λ 10.000: 100.67 / 93.35, 4.92
gewähltes λ: 0.100, Test: 9.96

Die letzte Zahl jeder Zeile (max |w|) ist das betragsmäßig größte Gewicht, ohne den Achsenabschnitt. Mit λ = 0,1 fällt das größte Gewicht von 571,59 auf 20,21 und die Validierung von 121,20 auf 9,55. Eine zu starke Strafe (λ = 10) drückt die Kurve fast zu einer flachen Geraden: Der Fehler wird auch auf den Trainingsdaten groß (100,67). Das ist das Gegenteil der Überanpassung, die Unteranpassung: Das Modell ist zu eingeschränkt, um den Zusammenhang zu erfassen.

Der Testfehler für das gewählte λ ist 9,96: viel besser als 84,44, aber die Gerade (5,57) ist immer noch die beste. Die Regularisierung macht aus einer Kurve keine Gerade, sie hält sie nur davon ab, wild zu werden.

Probier es aus

Ergänze die Lücke

Die Strafe kommt auf die Diagonale des Systems, ohne den Achsenabschnitt (i beginnt bei 1). Was wird addiert?

// die Strafe: λ auf der Diagonale, nicht auf dem Achsenabschnitt
for (let i = 1; i < m; i++) a[i][i] += ;

Probier es aus

Sag die Ausgabe voraus

Ein Fehler mit Strafe: MSE ist 2, die Gewichte sind 3 und −4, λ ist 0,1. Was wird ausgegeben?

const mse = 2.0;
const w = [3, -4];
const lambda = 0.1;
let penalty = 0;
for (const x of w) penalty += x * x;
console.log((mse + lambda * penalty).toFixed(2));
Antwort

Die Idee

Der nächste Nachbar lernt auswendig

Die nächsten Nachbarn aus der ersten Lektion haben dieselbe Krankheit. Mit k = 1 gibt das Modell die Zeit der nächsten früheren Bestellung zurück. Bei einer Bestellung aus den Trainingsdaten ist die nächste die Bestellung selbst, also ist der Trainingsfehler 0:

// die mittlere Zeit der k nächsten Bestellungen
function knn(data, km, k) {
  const used = new Array(data.length).fill(false);
  let sum = 0;
  for (let t = 0; t < k; t++) {
    let best = -1;
    for (let i = 0; i < data.length; i++) {
      if (used[i]) continue;
      if (best < 0 || Math.abs(data[i][0] - km) < Math.abs(data[best][0] - km)) best = i;
    }
    used[best] = true;
    sum += data[best][1];
  }
  return sum / k;
}


function knnMse(train, data, k) {
  let sum = 0;
  for (const [km, minutes] of data) {
    const e = knn(train, km, k) - minutes;
    sum += e * e;
  }
  return sum / data.length;
}
console.log("MSE: Training / Validierung");
for (let k = 1; k <= 4; k++)
  console.log(`k = ${k}: ${knnMse(train, train, k).toFixed(1)} / ${knnMse(train, val, k).toFixed(1)}`);
Ausgabe
MSE: Training / Validierung
k = 1: 0.0 / 28.9
k = 2: 22.0 / 11.2
k = 3: 19.0 / 19.7
k = 4: 48.7 / 23.2

k = 1 ist Auswendiglernen in Reinform: 0,0 im Training, 28,9 auf der Validierung. Mit k = 2 glättet der Mittelwert zweier Nachbarn das Rauschen, und die Validierung fällt auf 11,2. Ein größeres k macht es wieder schlechter: Der Mittelwert weit entfernter Bestellungen verwischt den Zusammenhang. Hier ist k wie der Grad der Kurve: Es wird mit der Validierung gewählt.

Die Idee

Wann es wehtut

  • Validierung bei wenigen Daten. 8 Validierungsbestellungen geben verrauschte Zahlen. Die Wahl kann zufällig sein: Zwischen Grad 2 und 3 ist der Unterschied (9,35 und 9,09) Rauschen. Je weniger Daten du hast, desto einfacher sollte das Modell sein.
  • Validierung oft angefasst. Du probierst 100 Grade, λ-Werte und Merkmale aus und wählst das Beste auf der Validierung. Eines davon ist zufällig das Beste. Deshalb bleibt der Test beiseite, unberührt.
  • Regularisierung ohne Skala. Die Strafe ist für alle Gewichte gleich. Ist ein Merkmal in Kilometern und ein anderes in Metern, ist das Gewicht der Meter tausendmal kleiner und wird kaum bestraft. Merkmale werden zuerst skaliert, so wie hier x verkleinert wird.
  • Eine zu starke Strafe. λ = 10 gibt Unteranpassung: Das Modell erfasst nicht einmal die Trainingsdaten. Schau auf beide Fehler: Sind beide hoch, ist das Modell zu einfach.
  • Mehr Daten sind nicht umsonst. Jede Bestellung in den Trainingsdaten ist eine echte Bestellung, die gesammelt und geprüft werden muss. Manchmal ist das einfachere Modell das billigere Heilmittel.
Genauer, für Neugierige

Die Formel. Das Programm sucht die Gewichte, bei denen die Summe der quadrierten Fehler plus λ · (w₁² + w₂² + … + w₇²) am kleinsten ist. MSE ist dieselbe Summe, geteilt durch die Anzahl der Bestellungen, also ist es vor dem MSE, als wäre λ 8-mal kleiner. Das ist die L2-Regularisierung (Ridge). Ist die Strafe die Summe der Beträge, |w₁| + |w₂| + …, ist es L1 (Lasso): Sie macht manche Gewichte genau 0 und wählt damit auch Merkmale aus.

Warum auf der Diagonale. Die besten Gewichte liegen dort, wo die Steigung des Fehlers für jedes Gewicht 0 ist. Jedes Gewicht gibt eine Gleichung. Die Steigung von λ · w² ist 2 · λ · w, und alle anderen Terme der Steigung haben ebenfalls eine 2 davor. Nach der Division durch 2 ist die Strafe λ · w in der Gleichung desselben Gewichts, also auf der Diagonale des Systems.

Kreuzvalidierung. Bei wenigen Daten: Du teilst die Trainingsdaten in 5 Teile, lernst auf 4 und misst auf dem fünften, fünfmal, und nimmst den Mittelwert. Jede Bestellung ist einmal Validierung, und die Wahl hängt nicht von einer zufälligen Gruppe ab.

Andere Heilmittel. Beim Gradientenabstieg: aufhören, wenn der Validierungsfehler zu wachsen beginnt (Early Stopping). Bei neuronalen Netzen: Dropout, das in jedem Schritt zufällige Neuronen abschaltet. Die Idee ist dieselbe: Das Modell soll sich nicht auf gemerkte Einzelheiten verlassen können.

Im echten Code. In scikit-learn sind das PolynomialFeatures, Ridge (λ heißt alpha), Lasso, KNeighborsRegressor, cross_val_score und GridSearchCV, das die Werte durchprobiert und mit Kreuzvalidierung wählt. In ML.NET ist die Regularisierung ein Parameter der Trainer (L2Regularization). Das Gauß-Verfahren wird dort durch stabilere Verfahren ersetzt, weil das System bei hohem Grad empfindlich auf Rundung reagiert.

for (const [km, minutes] of data) zerlegt jedes Paar. [a[c], a[p]] = [a[p], a[c]] vertauscht zwei Zeilen.

Übung

Wähle k

Löse das in deinem Editor.

Vervollständige das k-NN-Programm: Wähle k mit der Validierung (der kleinste Validierungsfehler), dann führe den Test nur für das gewählte k aus.

Ausgabe
MSE: Training / Validierung
k = 1: 0.0 / 28.9
k = 2: 22.0 / 11.2
k = 3: 19.0 / 19.7
k = 4: 48.7 / 23.2
gewähltes k: 2, Test: 16.9

Die Validierung wählt k = 2, und der Testfehler ist 16,9. Vergleiche mit der Geraden: 5,57. Bei diesem fast geraden Zusammenhang schlägt die Gerade auch die Nachbarn.

Weitere Aufgaben

  • Die Grade mit mehr Daten. Lerne die Grade 1 bis 7 auf 16 Bestellungen (Training und Validierung) und gib den Trainings- und den Testfehler aus. Ab welchem Grad beginnt der Testfehler zu wachsen?
  • Ein Raster von λ. Probiere λ von 0,02 bis 0,5 in Schritten von 0,02 für Grad 7. Welches λ wählt die Validierung, und wie groß ist sein Testfehler?

Test

Teste dich

1. Ein Modell hat auf den Trainingsdaten den Fehler 0 und auf neuen Daten einen großen Fehler. Wie heißt das?
2. Warum wird der Grad mit der Validierung gewählt und nicht mit dem Test?
3. Was macht die Regularisierung?
4. k-NN mit k = 1 hat auf den Trainingsdaten den Fehler 0. Warum ist das keine gute Nachricht?
5. Was heilt die Überanpassung NICHT?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·