Gradient boosting: drzewa, które poprawiają błędy

W lekcji 5.2 las losowy uśredniał wiele drzew zbudowanych niezależnie od siebie i dokładanie drzew nie szkodziło. Gradient boosting buduje drzewa po kolei. Każde nowe drzewo uczy się reszt, czyli tego, o ile zespół drzew przed nim wciąż się myli przy każdym przykładzie. Do wyniku dokłada swoją poprawkę pomnożoną przez krok uczenia, liczbę od 0 do 1. Drzewa są małe, często z jednym pytaniem (taki pień) albo z trzema. Na tabelach średniej wielkości modele z drzew, z boostingiem na czele, zwykle wygrywają z sieciami neuronowymi (Grinsztajn i in., 2022). Boosting ma jednak cechę, której las nie ma: kolejne poprawki mogą zacząć poprawiać szum.

Spróbuj

• Zacznij od startu: krok 1, głębokość 2, 200 drzew. Ile schodków ma funkcja zespołu i jak daleko leżą krzywe treningu i walidacji?
• Przesuń liczbę drzew w dół. Przy ilu drzewach błąd walidacji jest najniższy? Dopiero potem spójrz na test.
• Zmniejsz krok do 0,1 i weź pień. Jak teraz wygląda krzywa walidacji, gdy drzew przybywa?
• Porównaj najlepszą walidację boostingu z przerywaną linią prostej. Która jest niżej?

Gdy już sprawdzisz to w labie, nazwijmy, co widzisz.

Pomysł w prostych słowach

Pierwsze drzewo zadaje kilka pytań o BMI i przewiduje średni postęp choroby w każdej grupie. Myli się, więc liczymy reszty: ile brakuje do prawdy u każdego pacjenta. Drugie drzewo nie przewiduje już choroby, tylko te reszty. Jego wynik razy krok uczenia dokładamy do pierwszego. Trzecie drzewo uczy się tego, co zostało po dwóch, i tak dalej. Zespół rośnie z małych poprawek.

Na początku poprawki łapią prawdziwy wzór: większe BMI, większy postęp choroby. Gdy wzór jest już złapany, w resztach zostaje głównie szum, czyli przypadkowe odchylenia pacjentów, na których model się uczy. Kolejne drzewa uczą się właśnie jego. Przy kroku 1 i drzewach z trzema pytaniami trening spada z 3713 przy jednym drzewie do 2287 przy 200, a test rośnie z 4319 do 5944. To przeuczenie, tak jak przy zbyt głębokim drzewie, tylko tym razem rośnie z liczbą drzew. W lesie losowym każde drzewo widzi dane osobno, a uśrednianie gasi ich błędy. W boostingu każde drzewo dokłada się do błędów poprzednich.

Dlatego liczbę drzew, krok i głębokość wybiera walidacja, a nie test. Lab liczy błąd walidacji w walidacji krzyżowej na 5 części wewnątrz 309 pacjentów treningowych. Najniżej wypada pień z krokiem 0,1 i 50 drzewami: walidacja 3960. Prosta ma na tej samej walidacji 3823, więc na samym BMI wygrywa prosta. Test potwierdza to dopiero na końcu: 4154 dla boostingu wobec 4095 dla prostej.

Jak to policzono

• Dane: Diabetes (Efron i in., 2004), w scikit-learn na licencji BSD-3-Clause. 442 pacjentów, 10 pomiarów, postęp choroby po roku. Bierzemy tylko BMI. Podział: 309 pacjentów do nauki, 133 do testu.
• Model: gradient boosting z drzewami regresji głębokości 1 albo 2 na samym BMI, strata kwadratowa, krok 0,05 do 1, do 200 drzew; prosta regresja na BMI dla porównania. Liczby z labu zgadzają się z GradientBoostingRegressor z scikit-learn.
• Walidacja: walidacja krzyżowa na 5 części wewnątrz 309 pacjentów treningowych, te same części dla każdego ustawienia i dla prostej.

Dlaczego to działa

Reszta y − F(x) to kierunek, w którym trzeba poprawić przewidywanie, żeby błąd kwadratowy najszybciej spadał. Każde drzewo robi więc mały krok spadku gradientu, tyle że w przestrzeni funkcji, a nie wag. Stąd nazwa: gradient boosting. Mały krok oznacza, że jedno drzewo poprawia tylko część błędu. Potrzeba więcej drzew, ale każde dokłada mniej szumu. Na 20 innych podziałach 200 drzew z trzema pytaniami i krokiem 0,1 ma na teście od 3747 do 4802, za każdym razem mniej niż te same drzewa z krokiem 1 (od 4617 do 6983).

Nie znaczy to, że boosting zawsze bije prostą. Na samym BMI związek z chorobą jest prawie liniowy, a drzewa umieją tylko naśladować prostą schodkami. Na 20 innych podziałach boosting wybrany walidacją wygrywa z prostą na teście w 7. Boosting błyszczy tam, gdzie cech jest wiele, a ich wpływ jest progowy i splątany. Wtedy kolejne drzewa łapią zależności, których prosta nie umie wyrazić.

Starszy krewny, AdaBoost, zamiast reszt zmienia wagi przykładów. Przykłady, które zespół myli, ważą w następnej rundzie więcej. W haśle Atlasu o AdaBoost pierwszy pień na guzach piersi myli 10,3% guzów treningowych. Przed drugą rundą te pomylone guzy niosą dokładnie 50% całej wagi, więc drugi pień uczy się głównie na nich.

Częsty błąd

Prawda czy fałsz: „więcej rund boostingu zawsze pomaga”. Fałsz. Każda runda poprawia trening, ale test tylko do pewnego momentu. Przy kroku 1 i drzewach z trzema pytaniami najlepiej na walidacji wypada 1 drzewo, a 200 drzew daje na teście 5944 zamiast 4319. W kodzie niżej test rośnie z 4079 po jednym drzewie do 6437 po 200, choć trening spada z 3827 do 2044.

Bezpieczna droga to mały krok, dużo drzew i wczesne zatrzymanie z lekcji 3.6: przestań dokładać drzewa, gdy błąd walidacji przestaje spadać. W kodzie niżej zatrzymanie zostawia 83 z 1000 drzew.

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()  # walidacja tylko wewnątrz treningu
    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