Gradient Boosting: Bäume, die Fehler korrigieren

In Lektion 5.2 hat ein Random Forest viele unabhängig voneinander gebaute Bäume gemittelt, und mehr Bäume haben nicht geschadet. Gradient Boosting baut die Bäume nacheinander. Jeder neue Baum lernt die Residuen, also wie weit das Ensemble der Bäume vor ihm bei jedem Beispiel noch danebenliegt. Er addiert seine Korrektur, multipliziert mit der Lernrate, einer Zahl zwischen 0 und 1. Die Bäume sind klein, oft mit einer Frage (ein Stumpf) oder mit drei. Bei Tabellen mittlerer Größe schlagen Baummodelle, allen voran Boosting, meist neuronale Netze (Grinsztajn et al., 2022). Boosting hat aber eine Eigenschaft, die der Wald nicht hat: Spätere Korrekturen können anfangen, Rauschen zu korrigieren.

Probier es aus

• Beginne am Start: Lernrate 1, Tiefe 2, 200 Bäume. Wie viele Stufen hat die Funktion des Ensembles, und wie weit liegen die Trainings- und die Validierungskurve auseinander?
• Schiebe die Zahl der Bäume nach unten. Bei wie vielen Bäumen ist der Validierungsfehler am niedrigsten? Schau erst dann auf den Test.
• Senke die Lernrate auf 0,1 und nimm einen Stumpf. Wie sieht die Validierungskurve jetzt aus, wenn Bäume dazukommen?
• Vergleiche die beste Validierung des Boostings mit der gestrichelten Linie der Geraden. Welche liegt tiefer?

Wenn du es im Lab geprüft hast, geben wir dem, was du siehst, einen Namen.

Die Idee in einfachen Worten

Der erste Baum stellt ein paar Fragen zum BMI und sagt in jeder Gruppe den mittleren Krankheitsverlauf vorher. Er liegt daneben, also berechnen wir die Residuen: wie viel bei jedem Patienten zur Wahrheit fehlt. Der zweite Baum sagt nicht mehr die Krankheit vorher, sondern nur diese Residuen. Sein Ergebnis mal die Lernrate wird zum ersten addiert. Der dritte Baum lernt, was nach zweien übrig bleibt, und so weiter. Das Ensemble wächst aus kleinen Korrekturen.

Anfangs fangen die Korrekturen das echte Muster ein: höherer BMI, stärkerer Krankheitsverlauf. Ist das Muster erfasst, bleibt in den Residuen vor allem Rauschen, die zufälligen Abweichungen der Patienten, an denen das Modell lernt. Spätere Bäume lernen genau das. Mit Lernrate 1 und Bäumen mit drei Fragen fällt das Training von 3713 mit einem Baum auf 2287 mit 200, während der Test von 4319 auf 5944 steigt. Das ist Überanpassung, wie bei einem zu tiefen Baum, nur wächst sie diesmal mit der Zahl der Bäume. Im Random Forest sieht jeder Baum die Daten für sich, und das Mitteln löscht ihre Fehler aus. Beim Boosting setzt jeder Baum auf den Fehlern der vorigen auf.

Deshalb wählt die Validierung die Zahl der Bäume, die Lernrate und die Tiefe, nicht der Test. Das Lab berechnet den Validierungsfehler mit einer 5-fachen Kreuzvalidierung innerhalb der 309 Trainingspatienten. Am niedrigsten liegt ein Stumpf mit Lernrate 0,1 und 50 Bäumen: Validierung 3960. Die Gerade erreicht auf derselben Validierung 3823, also gewinnt allein mit dem BMI die Gerade. Der Test bestätigt das erst am Ende: 4154 für das Boosting gegen 4095 für die Gerade.

Jak to policzono

• Daten: Diabetes (Efron et al., 2004), in scikit-learn unter der Lizenz BSD-3-Clause. 442 Patienten, 10 Messungen, Krankheitsverlauf nach einem Jahr. Wir nehmen nur den BMI. Aufteilung: 309 Patienten zum Lernen, 133 für den Test.
• Modell: Gradient Boosting mit Regressionsbäumen der Tiefe 1 oder 2 allein auf dem BMI, quadratischer Verlust, Lernrate 0,05 bis 1, bis zu 200 Bäume; eine lineare Regression auf dem BMI zum Vergleich. Die Zahlen des Labors stimmen mit GradientBoostingRegressor aus scikit-learn überein.
• Validierung: 5-fache Kreuzvalidierung innerhalb der 309 Trainingspatienten, dieselben Teile für jede Einstellung und für die Gerade.

Warum es funktioniert

Das Residuum y − F(x) ist die Richtung, in die sich die Vorhersage bewegen muss, damit der quadratische Fehler am schnellsten fällt. Jeder Baum macht also einen kleinen Schritt des Gradientenabstiegs, nur im Raum der Funktionen statt der Gewichte. Daher der Name: Gradient Boosting. Eine kleine Lernrate heißt, dass ein Baum nur einen Teil des Fehlers behebt. Es braucht mehr Bäume, aber jeder bringt weniger Rauschen hinein. Bei 20 anderen Aufteilungen haben 200 Bäume mit drei Fragen und Lernrate 0,1 im Test einen MSE von 3747 bis 4802, jedes Mal weniger als dieselben Bäume mit Lernrate 1 (von 4617 bis 6983).

Das heißt nicht, dass Boosting eine Gerade immer schlägt. Allein mit dem BMI ist der Zusammenhang mit der Krankheit fast linear, und Bäume können eine Gerade nur mit Stufen nachahmen. Bei 20 anderen Aufteilungen schlägt das per Validierung gewählte Boosting die Gerade im Test in 7. Boosting glänzt dort, wo es viele Merkmale gibt und ihre Wirkung schwellenartig und verflochten ist. Dann fangen spätere Bäume Abhängigkeiten ein, die eine Gerade nicht ausdrücken kann.

Ein älterer Verwandter, AdaBoost, ändert statt der Residuen die Gewichte der Beispiele. Beispiele, bei denen das Ensemble danebenliegt, wiegen in der nächsten Runde mehr. Im Atlas-Eintrag zu AdaBoost klassifiziert der erste Stumpf bei Brusttumoren 10,3 % der Trainingstumoren falsch. Vor der zweiten Runde tragen diese falsch klassifizierten Tumoren genau 50 % des Gesamtgewichts, also lernt der zweite Stumpf vor allem an ihnen.

Ein häufiger Fehler

Richtig oder falsch: „Mehr Boosting-Runden helfen immer.“ Falsch. Jede Runde verbessert das Training, den Test aber nur bis zu einem Punkt. Mit Lernrate 1 und Bäumen mit drei Fragen ist in der Validierung 1 Baum am besten, und 200 Bäume ergeben im Test 5944 statt 4319. Im Code unten steigt der Test von 4079 nach einem Baum auf 6437 nach 200, während das Training von 3827 auf 2044 fällt.

Der sichere Weg ist eine kleine Lernrate, viele Bäume und das frühe Stoppen aus Lektion 3.6: Hör auf, Bäume hinzuzufügen, wenn der Validierungsfehler nicht mehr fällt. Im Code unten behält das frühe Stoppen 83 von 1000 Bäumen.

from sklearn.datasets import load_diabetes
from sklearn.model_selection import train_test_split, cross_val_score, KFold
from sklearn.ensemble import GradientBoostingRegressor
from sklearn.linear_model import LinearRegression
from sklearn.metrics import mean_squared_error as mse

X, y = load_diabetes(return_X_y=True, as_frame=True)
x_tr, x_te, y_tr, y_te = train_test_split(X[["bmi"]], y, test_size=0.3, random_state=0)
big = GradientBoostingRegressor(n_estimators=200, max_depth=2, learning_rate=1.0, random_state=0).fit(x_tr, y_tr)
for m, (p_tr, p_te) in enumerate(zip(big.staged_predict(x_tr), big.staged_predict(x_te)), start=1):
    if m in (1, 10, 50, 200):
        print(f"step 1, depth 2, {m:3d} trees: train MSE {mse(y_tr, p_tr):.0f}, test MSE {mse(y_te, p_te):.0f}")
cv = KFold(5, shuffle=True, random_state=0)
models = {"line": LinearRegression(), "step 1, 200 trees": big,
          "step 0.1, 50 stumps": GradientBoostingRegressor(n_estimators=50, max_depth=1, learning_rate=0.1, random_state=0)}
for name, model in models.items():
    val = -cross_val_score(model, x_tr, y_tr, cv=cv, scoring="neg_mean_squared_error").mean()  # Validierung nur innerhalb des Trainings
    print(f"{name}: validation MSE {val:.0f}")
stop = GradientBoostingRegressor(n_estimators=1000, max_depth=1, learning_rate=0.1, validation_fraction=0.2, n_iter_no_change=10, random_state=0).fit(x_tr, y_tr)
print(f"early stopping kept {stop.n_estimators_} of 1000 trees; test MSE {mse(y_te, stop.predict(x_te)):.0f}, line {mse(y_te, models['line'].fit(x_tr, y_tr).predict(x_te)):.0f}")

step 1, depth 2,   1 trees: train MSE 3827, test MSE 4079
step 1, depth 2,  10 trees: train MSE 3013, test MSE 4798
step 1, depth 2,  50 trees: train MSE 2122, test MSE 6233
step 1, depth 2, 200 trees: train MSE 2044, test MSE 6437
line: validation MSE 3956
step 1, 200 trees: validation MSE 5728
step 0.1, 50 stumps: validation MSE 4030
early stopping kept 83 of 1000 trees; test MSE 4062, line 3921