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ěď.
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)
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}")
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.
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
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})")
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).
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
Validační chyba přestala klesat po 80. kole z 500. Co je rozumné?
Další kola už jen přizpůsobují model šumu. Menší krok často najde lepší minimum, ale stojí víc stromů.
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ý:
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}")
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ň jádro boostingu
Doplň zbytek a aktualizaci předpovědi.
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}")
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}")
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}")
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
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
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:
- Nastav
learning_ratena 0,05 až 0,1 a velký limit kol se včasným zastavením. - Lad složitost stromů:
max_leaf_nodesnebomax_depth,min_samples_leaf. - Když se model přeučuje, přidej regularizaci (
l2_regularization) nebo náhodu (subsample,max_features). - Na závěr případně zmenši
learning_ratea 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:
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)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:
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}")
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.
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.