0 dní v řadě · 0 bodů

Strojové učení · 40 min

Gradient boosting

Stovky malých stromů, z nichž každý opravuje chyby těch předchozích. Postavíš boosting v NumPy a naučíš se ho ladit ve scikit-learn.

Hloubka
Úkoly
Lidsky řečeno

Krejčí šije oblek. První střih je hrubý. Při zkoušce uvidí, že rukávy jsou dlouhé a v pase to táhne, a opraví to. Při další zkoušce doladí menší odchylky. Nikdo nečeká, že první pokus bude dokonalý, každá zkouška řeší jen to, co ještě nesedí. Gradient boosting pracuje stejně, jen zkoušek jsou stovky a každou opravu provede malý, sám o sobě dost hloupý strom.

Oprava po opravě

Náhodný les staví hluboké stromy vedle sebe a průměruje je. Boosting je staví za sebou: každý další strom se učí to, co předchozím ještě chybí. Co chybí, měří zbytek (reziduum): skutečnost minus dosavadní předpověď.

text
předpověď_0 = průměr y
opakuj:
    zbytek   = y - předpověď
    strom    = nauč malý strom předpovídat zbytek
    předpověď = předpověď + krok · strom(x)

Stromy bývají maličké. Nejmenší možný má jedinou otázku a dva listy, říká se mu pahýl (stump). Čtyři byty, jeden příznak, cena v milionech. Tipni, co vypíše druhý a třetí řádek.

import numpy as np

x = np.array([40, 55, 90, 110])
y = np.array([3.0, 5.0, 10.0, 12.0])

predpoved = np.full(4, y.mean())
print("start:  ", predpoved)

zbytek = y - predpoved
print("zbytek: ", zbytek)

maly = x <= 70
oprava = np.where(maly, zbytek[maly].mean(), zbytek[~maly].mean())
predpoved = predpoved + oprava
print("po 1.:  ", predpoved)
print("zbytek: ", y - predpoved)
Výstup
start:   [7.5 7.5 7.5 7.5]
zbytek:  [-4.5 -2.5  2.5  4.5]
po 1.:   [ 4.  4. 11. 11.]
zbytek:  [-1.  1. -1.  1.]

Jedna otázka srazila zbytky z hodnot až 4,5 na 1. Další pahýl by se zaměřil na to, co zbylo.

Boosting od nuly

Pahýl hledá práh, po kterém jsou zbytky v každé polovině co nejpodobnější, tedy mají nejmenší součet čtverců odchylek od svého průměru. Zbytek už je jen cyklus ze schématu. Hlavní parametry jsou dva: kola je počet stromů a lr (learning rate) říká, jakou část opravy opravdu přijmeme.

import numpy as np

np.random.seed(0)
def data(n):
    x = np.random.uniform(0, 6, n)
    return x, 2 * np.sin(x) + 0.3 * x + np.random.normal(0, 0.35, n)

x_tr, y_tr = data(150)
x_te, y_te = data(500)
PRAHY = np.linspace(0.2, 5.8, 30)

def pahyl(x, r):
    nejlepsi = (np.inf, 0.0, 0.0, 0.0)
    for t in PRAHY:
        m = x <= t
        if m.all() or not m.any():
            continue
        vlevo, vpravo = r[m].mean(), r[~m].mean()
        sse = np.sum((r[m] - vlevo) ** 2) + np.sum((r[~m] - vpravo) ** 2)
        if sse < nejlepsi[0]:
            nejlepsi = (sse, t, vlevo, vpravo)
    return nejlepsi[1:]

def rmse(y, odhad):
    return np.sqrt(np.mean((y - odhad) ** 2))

F_tr = np.full(len(x_tr), y_tr.mean())
F_te = np.full(len(x_te), y_tr.mean())
print(f"kolo   0: trénink {rmse(y_tr, F_tr):.3f}  test {rmse(y_te, F_te):.3f}")

pocet = int(kola)
for k in range(1, pocet + 1):
    t, vlevo, vpravo = pahyl(x_tr, y_tr - F_tr)
    F_tr += lr * np.where(x_tr <= t, vlevo, vpravo)
    F_te += lr * np.where(x_te <= t, vlevo, vpravo)
    if k % max(1, pocet // 4) == 0:
        print(f"kolo {k:>3}: trénink {rmse(y_tr, F_tr):.3f}  test {rmse(y_te, F_te):.3f}")
Výstup
kolo   0: trénink 1.076  test 1.110
kolo  25: trénink 0.576  test 0.636
kolo  50: trénink 0.477  test 0.531
kolo  75: trénink 0.418  test 0.469
kolo 100: trénink 0.381  test 0.432

Testovací data mají šum se směrodatnou odchylkou 0,35, takže pod tuhle hodnotu se RMSE trvale nedostane. Zkus lr na 1 s mnoha koly: trénink se zlepšuje dál, test ne. Malý krok se s velkým počtem kol chová klidněji.

Úkol

Najdi nejlepší pahýl

Napiš funkci pahyl(x, r, prahy). Pro každý práh rozděl data na x <= prah a zbytek (prahy s prázdnou stranou přeskoč). Spočítej součet čtverců odchylek od průměru v obou částech. Vrať trojici (prah, prumer_vlevo, prumer_vpravo) s nejmenším součtem.

import numpy as np

def pahyl(x, r, prahy):
    # doplň
    return None
Výstup
Najdi chybu

Boosting, který se nic nenaučí

Chyba má s přibývajícími koly klesat. Tady se po chvíli předpověď rozjede špatným směrem, protože každý krok opravuje pořád stejný zbytek.

Krok, počet stromů a včasné zastavení

Learning rate a počet kol jsou spojené nádoby. Malý krok potřebuje víc stromů, ale obvykle dojde k lepšímu výsledku. A protože každé další kolo se víc přizpůsobuje trénovacím datům, od jistého bodu se test začne zhoršovat. Boosting se přeučit umí, na rozdíl od lesa, kterému další stromy neškodí.

Pahýl tady počítáme maticově, výsledek je stejný jako s cyklem, jen rychleji. Data mají schválně více šumu.

import numpy as np

np.random.seed(1)
def data(n):
    x = np.random.uniform(0, 6, n)
    return x, 2 * np.sin(x) + 0.3 * x + np.random.normal(0, 0.8, n)

x_tr, y_tr = data(80)
x_te, y_te = data(1000)
PRAHY = np.linspace(0.1, 5.9, 60)
M = x_tr[:, None] <= PRAHY            # one column per threshold
n_l = M.sum(axis=0)
OK = (n_l > 0) & (n_l < len(x_tr))
PRAHY, M, n_l = PRAHY[OK], M[:, OK], n_l[OK]
n_r = len(x_tr) - n_l

def krivka(lr, kol):
    F_tr = np.full(len(x_tr), y_tr.mean())
    F_te = np.full(len(x_te), y_tr.mean())
    chyby = []
    for _ in range(kol):
        r = y_tr - F_tr
        s_l = r @ M
        s_r = r.sum() - s_l
        i = np.argmax(s_l ** 2 / n_l + s_r ** 2 / n_r)
        vlevo, vpravo = s_l[i] / n_l[i], s_r[i] / n_r[i]
        F_tr += lr * np.where(x_tr <= PRAHY[i], vlevo, vpravo)
        F_te += lr * np.where(x_te <= PRAHY[i], vlevo, vpravo)
        chyby.append(np.sqrt(np.mean((y_te - F_te) ** 2)))
    return np.array(chyby)

print("  lr   po 10   po 100  po 1000  nejlepší (kolo)")
for lr in [1.0, 0.3, 0.1, 0.03]:
    c = krivka(lr, 1000)
    print(f"{lr:>4}   {c[9]:.3f}   {c[99]:.3f}   {c[999]:.3f}    {c.min():.3f} ({c.argmin() + 1})")
Výstup
  lr   po 10   po 100  po 1000  nejlepší (kolo)
 1.0   0.905   0.946   1.013    0.892 (6)
 0.3   0.912   0.911   0.956    0.880 (26)
 0.1   1.025   0.882   0.933    0.881 (90)
0.03   1.178   0.927   0.908    0.882 (313)

Porovnej sloupec „po 1000“ se sloupcem „nejlepší“. Rozdíl je cena za příliš mnoho stromů a roste s velikostí kroku. Proto se nezkouší počet kol ručně. Používá se včasné zastavení (early stopping): po každém kole se změří chyba na validačních datech a trénink skončí, když se určitý počet kol nezlepšila. Tomu počtu se říká trpělivost (patience).

Úkol

Včasné zastavení

Napiš funkci kdy_stop(chyby, trpelivost). V seznamu chyby je validační chyba po jednotlivých kolech. Procházej ho od začátku. Když se chyba nezlepšila (neklesla pod dosavadní minimum) trpelivost kol za sebou, skonči. Vrať index dosud nejlepšího kola. Pokud k zastavení nedojde, vrať index nejlepšího kola z celého seznamu.

def kdy_stop(chyby, trpelivost):
    # doplň
    return -1
Výstup
Kvíz

Validační chyba přestala klesat po 80. kole z 500. Co je rozumné?

Proč „gradient“

Zatím jsme opravovali zbytky. Pro klasifikaci ale zbytek „třída minus číslo“ nedává smysl. Řešení je obecnější pohled: zbytek je záporný gradient chyby. U kvadratické chyby jsou to shodou okolností přímo rozdíly y - F. Boosting tak dělá gradientní sestup, jenže nemění váhy, ale přímo předpovědi, a krok do nových dat přenáší strom.

U klasifikace se pracuje ve skóre F z logistické regrese. Pravděpodobnost dá sigmoida a záporný gradient log loss je velmi jednoduchý:

text
p = sigmoida(F)
pseudo-zbytek = y - p
hodnota listu = Σ(y - p) / Σ p(1 - p)

Hodnota listu je Newtonův krok, který bere v úvahu i zakřivení chyby. Model startuje z logaritmu šance celé trénovací sady. Na kruhových datech, která by přímka neoddělila, to dopadá takto:

import numpy as np

def sigmoid(z):
    return 1 / (1 + np.exp(-z))

def log_loss(y, p):
    p = np.clip(p, 1e-12, 1 - 1e-12)
    return np.mean(-(y * np.log(p) + (1 - y) * np.log(1 - p)))

def data(n):
    X = np.random.normal(size=(n, 2))
    y = (np.sum(X ** 2, axis=1) < 1.4).astype(float)
    sum = np.random.random(n) < 0.1
    y[sum] = 1 - y[sum]
    return X, y

np.random.seed(0)
X_tr, y_tr = data(400)
X_te, y_te = data(2000)
PRAHY = np.linspace(-2.5, 2.5, 41)

def nejlepsi_pahyl(X, r):
    nejlepsi = (-np.inf, 0, 0.0)
    for j in range(X.shape[1]):
        M = X[:, j, None] <= PRAHY
        n_l = M.sum(axis=0)
        s_l = r @ M
        s_r = r.sum() - s_l
        with np.errstate(divide="ignore", invalid="ignore"):
            zisk = s_l ** 2 / n_l + s_r ** 2 / (len(r) - n_l)
        zisk[(n_l == 0) | (n_l == len(r))] = -np.inf
        i = int(np.argmax(zisk))
        if zisk[i] > nejlepsi[0]:
            nejlepsi = (zisk[i], j, PRAHY[i])
    return nejlepsi[1:]

zaklad = np.log(y_tr.mean() / (1 - y_tr.mean()))
F_tr = np.full(len(y_tr), zaklad)
F_te = np.full(len(y_te), zaklad)
lr = 0.2

for kolo in range(1, 201):
    p = sigmoid(F_tr)
    r = y_tr - p
    j, t = nejlepsi_pahyl(X_tr, r)
    m = X_tr[:, j] <= t
    h = p * (1 - p)
    vlevo = r[m].sum() / h[m].sum()
    vpravo = r[~m].sum() / h[~m].sum()
    F_tr += lr * np.where(X_tr[:, j] <= t, vlevo, vpravo)
    F_te += lr * np.where(X_te[:, j] <= t, vlevo, vpravo)
    if kolo in (1, 10, 50, 100, 200):
        p_te = sigmoid(F_te)
        print(f"kolo {kolo:>3}: log loss test {log_loss(y_te, p_te):.3f}, "
              f"přesnost {np.mean((p_te >= 0.5) == y_te):.3f}")
Výstup
kolo   1: log loss test 0.683, přesnost 0.582
kolo  10: log loss test 0.571, přesnost 0.835
kolo  50: log loss test 0.458, přesnost 0.840
kolo 100: log loss test 0.446, přesnost 0.840
kolo 200: log loss test 0.450, přesnost 0.838

Každý pahýl umí jen rozříznout rovinu kolmo na osu. Teprve jejich součet vytvoří uzavřenou oblast kolem středu.

Doplň

Doplň jádro boostingu

Doplň zbytek a aktualizaci předpovědi.

Roztřiď

Les, nebo boosting?

Zařaď vlastnosti k metodě.

scikit-learn

Klasická implementace je GradientBoostingClassifier. Metoda staged_predict_proba vrací předpovědi po každém kole, takže křivku získáš bez opakovaného tréninku. Počet kol vybíráme podle validační sady, test zůstává nedotčený až do konce.

import numpy as np
from sklearn.datasets import make_classification
from sklearn.ensemble import GradientBoostingClassifier
from sklearn.metrics import log_loss
from sklearn.model_selection import train_test_split

X, y = make_classification(n_samples=1000, n_features=12, n_informative=6,
                           flip_y=0.08, class_sep=0.8, random_state=0)
X_tr, X_zbytek, y_tr, y_zbytek = train_test_split(X, y, test_size=0.4, stratify=y, random_state=0)
X_val, X_te, y_val, y_te = train_test_split(X_zbytek, y_zbytek, test_size=0.5,
                                            stratify=y_zbytek, random_state=0)

model = GradientBoostingClassifier(n_estimators=200, learning_rate=0.1, max_depth=3,
                                   subsample=0.8, random_state=0).fit(X_tr, y_tr)

ztraty = np.array([log_loss(y_val, p) for p in model.staged_predict_proba(X_val)])
nejlepsi = int(ztraty.argmin()) + 1

for k in [10, 50, 100, 200]:
    print(f"{k:>3} stromů: validační log loss {ztraty[k - 1]:.3f}")
print("nejlepší počet:", nejlepsi)

for k, p in enumerate(model.staged_predict_proba(X_te), start=1):
    if k == nejlepsi:
        print(f"test při tomto počtu: {log_loss(y_te, p):.3f}")
Výstup
 10 stromů: validační log loss 0.512
 50 stromů: validační log loss 0.421
100 stromů: validační log loss 0.408
200 stromů: validační log loss 0.402
nejlepší počet: 194
test při tomto počtu: 0.370

Pro větší data je mnohem rychlejší HistGradientBoostingClassifier. Příznaky si předem rozdělí do nejvýše 255 přihrádek, sám zvládá chybějící hodnoty a umí včasné zastavení. Tady mu 10 % hodnot schválně vymažeme.

import numpy as np
from sklearn.datasets import make_classification
from sklearn.ensemble import HistGradientBoostingClassifier
from sklearn.metrics import roc_auc_score
from sklearn.model_selection import train_test_split

X, y = make_classification(n_samples=2000, n_features=15, n_informative=8,
                           flip_y=0.05, random_state=1)
rng = np.random.RandomState(0)
X[rng.random_sample(X.shape) < 0.1] = np.nan

X_tr, X_te, y_tr, y_te = train_test_split(X, y, stratify=y, random_state=0)

model = HistGradientBoostingClassifier(
    learning_rate=0.1, max_iter=300, max_leaf_nodes=15,
    early_stopping=True, validation_fraction=0.15, n_iter_no_change=10,
    random_state=0,
).fit(X_tr, y_tr)

print("chybějících hodnot:", int(np.isnan(X_tr).sum()))
print("použito kol:", model.n_iter_, "z 300")
print(f"ROC AUC na testu: {roc_auc_score(y_te, model.predict_proba(X_te)[:, 1]):.3f}")
Výstup
chybějících hodnot: 2298
použito kol: 68 z 300
ROC AUC na testu: 0.868

Hledej, jestli n_iter_ skončilo pod limitem 300. Pokud ano, zastavení zafungovalo. Pozor, výchozí early_stopping="auto" se zapne až nad 10 000 řádků.

Srovnání s tím, co už znáš. Na takhle malých syntetických datech nejde o vítěze, ale o postup: stejné rozdělení, stejné metriky.

from sklearn.datasets import make_classification
from sklearn.ensemble import (GradientBoostingClassifier, HistGradientBoostingClassifier,
                              RandomForestClassifier)
from sklearn.linear_model import LogisticRegression
from sklearn.metrics import log_loss, roc_auc_score
from sklearn.model_selection import train_test_split

X, y = make_classification(n_samples=800, n_features=12, n_informative=6,
                           flip_y=0.05, class_sep=0.8, random_state=3)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, stratify=y, random_state=0)

modely = {
    "logistická regrese": LogisticRegression(max_iter=1000, random_state=0),
    "náhodný les": RandomForestClassifier(n_estimators=100, random_state=0),
    "gradient boosting": GradientBoostingClassifier(n_estimators=100, random_state=0),
    "hist. boosting": HistGradientBoostingClassifier(max_iter=100, random_state=0),
}
for nazev, model in modely.items():
    p = model.fit(X_tr, y_tr).predict_proba(X_te)[:, 1]
    print(f"{nazev:<20} AUC {roc_auc_score(y_te, p):.3f}   log loss {log_loss(y_te, p):.3f}")
Výstup
logistická regrese   AUC 0.834   log loss 0.510
náhodný les          AUC 0.882   log loss 0.447
gradient boosting    AUC 0.874   log loss 0.451
hist. boosting       AUC 0.872   log loss 0.556
Úkol

Včasné zastavení v praxi

Natrénuj HistGradientBoostingClassifier jako model s max_iter=200, early_stopping=True, n_iter_no_change=5 a random_state=0. Do kola ulož skutečný počet kol z atributu n_iter_.

from sklearn.datasets import make_classification
from sklearn.ensemble import HistGradientBoostingClassifier

X, y = make_classification(n_samples=800, n_features=10, flip_y=0.1, random_state=0)
model = None
kola = None
Výstup

Jak ladit a kdy po něm sáhnout

Gradient boosting je na tabulkových datech (řádky a sloupce, ne obrázky ani text) častá první volba. Rozumný postup:

  1. Nastav learning_rate na 0,05 až 0,1 a velký limit kol se včasným zastavením.
  2. Lad složitost stromů: max_leaf_nodes nebo max_depth, min_samples_leaf.
  3. Když se model přeučuje, přidej regularizaci (l2_regularization) nebo náhodu (subsample, max_features).
  4. Na závěr případně zmenši learning_rate a nech běžet víc kol.

Vyhodnocení dělej křížovou validací. Mimo scikit-learn se používají knihovny XGBoost, LightGBM a CatBoost. V prohlížeči tohoto kurzu nejsou, proto jen ukázka:

python
from xgboost import XGBClassifier

model = XGBClassifier(
    n_estimators=2000,
    learning_rate=0.05,
    max_depth=5,
    subsample=0.8,
    colsample_bytree=0.8,
    eval_metric="logloss",
    early_stopping_rounds=50,
)
model.fit(X_tr, y_tr, eval_set=[(X_val, y_val)])
print(model.best_iteration)
Spoj dvojice

Co který parametr dělá?

Spoj parametr s účinkem.

Pod kapotou · druhý řád, histogramy a růst po listech

Newtonův boosting. XGBoost rozvine ztrátu do druhého řádu. Pro list se součty gradientů G a hessiánů H je optimální hodnota -G / (H + λ) a zisk z řezu:

text
zisk = ½ · [ G_L²/(H_L+λ) + G_R²/(H_R+λ) - G²/(H+λ) ] - γ

Díky tomu stačí knihovně pro novou ztrátu dodat jen g a h. λ tlumí listy s malým hessiánem, γ je cena za další list. Náš vzorec Σ(y - p) / Σ p(1 - p) je stejný případ s λ = 0.

Histogramy. Přesné hledání řezu stojí řazení, tedy řádově n log n na příznak. S B přihrádkami stačí jednou zařadit hodnoty a v každém uzlu sečíst gradienty do histogramu: O(n + B). Histogram jednoho potomka vznikne odečtením od rodiče, takže se počítá jen ten menší. Ztráta přesnosti řezu bývá zanedbatelná:

import numpy as np

np.random.seed(0)
n = 20000
x = np.random.normal(size=n)
r = np.sin(2 * x) + np.random.normal(0, 0.5, n)

def zisk(s_l, n_l):
    s_r, n_r = r.sum() - s_l, n - n_l
    return s_l ** 2 / n_l + s_r ** 2 / n_r

poradi = np.argsort(x)
s_presne = np.cumsum(r[poradi])[:-1]
n_presne = np.arange(1, n)
z_presne = zisk(s_presne, n_presne)
i = z_presne.argmax()
print(f"přesně:    {n - 1} kandidátů, práh {x[poradi[i]]:.3f}, zisk {z_presne[i]:.1f}")

hranice = np.unique(np.quantile(x, np.linspace(0, 1, 256)[1:-1]))
kos = np.searchsorted(hranice, x, side="left")
s_hist = np.cumsum(np.bincount(kos, weights=r, minlength=len(hranice) + 1))[:-1]
n_hist = np.cumsum(np.bincount(kos, minlength=len(hranice) + 1))[:-1]
z_hist = zisk(s_hist, n_hist)
j = z_hist.argmax()
print(f"histogram: {len(hranice)} kandidátů, práh {hranice[j]:.3f}, zisk {z_hist[j]:.1f}")
Výstup
přesně:    19999 kandidátů, práh 0.024, zisk 5372.4
histogram: 254 kandidátů, práh 0.023, zisk 5369.7

Růst po listech. Klasický GradientBoosting* i XGBoost ve výchozím stavu rostou po úrovních. LightGBM a HistGradientBoosting* rozvíjejí vždy list s největším ziskem, proto se tam složitost řídí max_leaf_nodes. Stejný počet listů dá lepší ztrátu, ale strom může být hluboký a na malých datech se snáz přeučí.

Kategorie. One-hot u stromů tříští signál. HistGradientBoosting* umí nativní kategorie přes categorical_features (do 255 hodnot). CatBoost počítá target encoding uspořádaně, aby cíl daného řádku neprosákl do jeho vlastního příznaku.

Obchodní omezení. monotonic_cst vynutí, aby predikce s příznakem jen rostla nebo klesala. To se hodí u kreditního skóringu, kde by nemonotónní závislost nešlo obhájit.

Pravděpodobnosti a provoz. Silně boostovaný model může být špatně kalibrovaný, zvlášť s vahami tříd. Latence roste s počtem stromů, proto je včasné zastavení i provozní úspora. Data s časovou osou děl podle času, náhodné dělení vede k příliš krásným výsledkům.

Kartičky

Opakování

Vyzkoušej si: Přidávání slabých stromků

Přidávej po jednom malé stromky, které opravují zbytkovou chybu. Rychlost učení řídí, kolik každý z nich přispěje.