Generalisering og modellvalg

Tenk deg at du har 30 målepunkter mellom $x=0$ og $x=10$ og skal predikere $y$ ved $x=15$. Uendelig mange funksjoner går gjennom eller nær alle de 30 punktene, og de kan gi helt forskjellige svar ved 15. Dataene alene kan ikke avgjøre hvem som har rett, så algoritmen må foretrekke noen funksjoner framfor andre. Disse innebygde preferansene kalles induktiv bias: antakelsene en læringsalgoritme gjør for å kunne generalisere fra endelige data til nye tilfeller.

Hver modellfamilie har sin egen induktive bias:

• •Lineær regresjon antar at $y$ endrer seg lineært med hver feature, og at effektene legges sammen. Utenfor dataene fortsetter den rette linjen.
• •k-nærmeste-naboer antar at punkter som ligger nær hverandre i featurerommet, har lignende verdi eller label. Langt utenfor dataene kopierer den bare de nærmeste kjente punktene.
• •Beslutningstrær antar at sammenhengen kan beskrives med aksevise ja–nei-spørsmål, altså konstante trappetrinn. Utenfor dataene blir prediksjonen flat.

Tre modeller trenes på de samme 30 punktene, alle med $x$ mellom 0 og 10.

import numpy as np
from sklearn.linear_model import LinearRegression
from sklearn.neighbors import KNeighborsRegressor
from sklearn.tree import DecisionTreeRegressor

rng = np.random.default_rng(7)
x = np.sort(rng.uniform(0, 10, 30)).reshape(-1, 1)   # treningsdata mellom 0 og 10
y = 2.0 * x.ravel() + 1 + rng.normal(0, 1.5, 30)
x_ny = 15.0  # @param 0..20 0.5

modeller = {
    "lineær": LinearRegression(),
    "5-NN": KNeighborsRegressor(n_neighbors=5),
    "tre, dybde 3": DecisionTreeRegressor(max_depth=3, random_state=0),
}
for navn, modell in modeller.items():
    print(f"{navn:13s} predikerer {modell.fit(x, y).predict([[x_ny]])[0]:6.2f}")
print(f"sann sammenheng gir {2.0 * x_ny + 1:6.2f}")

Ved $x=15$ fortsetter den lineære modellen trenden, mens k-NN og treet blir stående på nivået til de siste punktene. Inne i dataområdet er de nesten enige, fordi dataene der styrer svaret mer enn antakelsene gjør.

Ingen av antakelsene er «riktige» i seg selv. En antakelse som passer problemet, gir god generalisering med lite data; en som ikke passer, gir systematiske feil uansett datamengde. En algoritme helt uten induktiv bias kan ikke generalisere i det hele tatt, fordi den ikke har noen grunn til å foretrekke ett svar framfor et annet.

Hvor fleksibel bør modellen være? Polynomregresjon gjør spørsmålet konkret: grad 1 er en rett linje, grad 3 kan bøye seg to ganger, og grad 9 kan svinge nesten hvor som helst. Høyere grad gir større kapasitet, altså flere funksjoner modellen kan uttrykke.

Undertilpasning skjer når kapasiteten er for lav. En rett linje gjennom en bølgeformet sammenheng bommer systematisk, så feilen er høy både på treningsdata og valideringsdata, og de to ligger nær hverandre. Mer data hjelper ikke, for modellen kan rett og slett ikke uttrykke mønsteret.

Overtilpasning skjer når kapasiteten er for høy i forhold til datamengden. Modellen bøyer seg gjennom hvert treningspunkt, også gjennom støyen. Treningsfeilen blir svært lav, men valideringsfeilen stiger, fordi støyen ikke gjentar seg i nye data. Kjennetegnet er et stort generaliseringsgap, valideringsfeil minus treningsfeil.

Når kapasiteten øker, faller treningsfeilen nesten alltid. Valideringsfeilen faller først, når et minimum og stiger så igjen. Modellen vi vil ha, ligger ved minimumet av valideringsfeilen, ikke av treningsfeilen.

Kapasiteten vokser raskt med flere features. Med to features $a$ og $b$ gir grad $d$ alle ledd $a^p{b}^q$ med $p+q\le d$, i alt $(d+1)(d+2)/2$ ledd: 6 ved grad 2, men 55 ved grad 9. Kodeøvingen under bygger nettopp disse leddene.

Hvorfor overtilpasser fleksible modeller? Tenk deg at du kunne hente et nytt treningssett fra samme kilde mange ganger, trene modellen på hvert av dem og se på prediksjonen i ett fast punkt $x$. To ting kan gå galt.

Bias er hvor langt gjennomsnittet av prediksjonene ligger fra sannheten. En rett linje som skal følge en kurve, bommer på samme måte hver gang, uansett datasett. Det er systematisk feil.

Varians er hvor mye prediksjonene spriker mellom treningssettene. Et polynom av grad 9 følger støyen i hvert datasett og blir derfor forskjellig fra gang til gang.

For kvadratfeil kan forventet feil deles opp eksakt, ƒbias–varians-dekomponering:

Det siste leddet, ${\sigma }^2$, er støy i selve målingene, og den kan ingen modell fjerne. Mer kapasitet senker bias og øker varians. Dette er bias–varians-avveiingen: undertilpasning er høy bias, overtilpasning er høy varians, og den beste modellen minimerer summen.

Tegn på høy varians i praksis er lav treningsfeil, valideringsfeil som stiger når modellen gjøres mer kompleks, og prediksjoner som endrer seg mye når du trener på nytt med en annen splitt eller seed. Tegn på høy bias er at treningsfeilen selv er høy, og at valideringsfeilen ligger like over.

import numpy as np
import matplotlib.pyplot as plt
P = np.polynomial.polynomial

rng = np.random.default_rng(42)
n = 20  # @param 15..100 5
x0 = 1.2                                     # punktet vi studerer
f = lambda x: np.sin(2 * x)                  # den sanne sammenhengen
xs = rng.uniform(0, 3, (300, n))             # 300 nye treningssett fra samme kilde
ys = f(xs) + rng.normal(0, 0.3, (300, n))

def bias_varians(grad):
    pred = np.array([P.polyval(x0, P.polyfit(x, y, grad)) for x, y in zip(xs, ys)])
    return (pred.mean() - f(x0)) ** 2, pred.var()

grader = np.arange(1, 10)
bias2, varians = np.array([bias_varians(g) for g in grader]).T
total = bias2 + varians
print(f"n = {n}: lavest sum for grad {grader[total.argmin()]} (bias² {bias2[total.argmin()]:.4f} + varians {varians[total.argmin()]:.4f})")

plt.figure()
plt.plot(grader, bias2, label="bias²")
plt.plot(grader, varians, label="varians")
plt.plot(grader, total, label="sum")
plt.ylim(0, 0.3)
plt.xlabel("polynomgrad")
plt.ylabel("feil i x = 1,2")
plt.legend()
plt.tight_layout()
plt.show()

Å senke polynomgraden er én måte å redusere varians på. En annen er å beholde den fleksible modellen, men gjøre store vekter dyre. Det kalles regularisering. Intuisjonen er at et polynom som svinger vilt mellom treningspunktene, trenger enorme koeffisienter med vekslende fortegn. Straffer vi store koeffisienter, blir svingningene for dyre, og modellen velger en glattere kurve.

Ridge (L2-regularisering) legger til summen av kvadrerte vekter, ƒridge-tap (L2):

Ridge krymper alle vektene jevnt mot null, men gjør dem sjelden nøyaktig null.

Lasso (L1-regularisering) bruker absoluttverdier i stedet, $\text{MSE}+\lambda {\sum }_j|w_j|$, som i ƒlasso-tap (L1). Straffen vokser like raskt for små som for store vekter, så det lønner seg ofte å sette noen vekter nøyaktig til null. Lasso gjør derfor også featureutvalg.

Styrken $\lambda$ bestemmer avveiningen. Med $\lambda =0$ får vi vanlig minste kvadraters metode. Når $\lambda$ øker, krymper vektene, treningsfeilen og bias øker, og variansen synker. Med svært stor $\lambda$ presses alle vekter mot null, og modellen blir nesten konstant: undertilpasning. Valideringsfeilen er derfor ofte U-formet i $\lambda$. To praktiske detaljer: skjæringsleddet straffes vanligvis ikke, og featurene bør standardiseres først, ellers straffes features med små tallverdier, som trenger store vekter, urettferdig hardt.

Det finnes to slags tall i en modell. Parametre lærer modellen selv fra treningsdataene når den optimeres: vektene i lineær og logistisk regresjon, splittverdiene i et beslutningstre og sentroidene i k-means. En hyperparameter er derimot en innstilling vi velger før treningen, og den styrer hvordan læringen skjer: polynomgraden, $\lambda$, $k$ i k-NN, maksimal dybde i et tre, læringsraten og antall epoker.

Hyperparametre kan ikke velges ut fra treningsfeilen. Da ville vi alltid valgt høyest grad, lavest $\lambda$ og dypest tre, fordi det gir lavest treningsfeil. Vi trenger data modellen ikke har trent på, og derfor deler vi dataene i tre roller:

• •Treningssett: tilpasser parametrene.
• •Valideringssett: sammenligner hyperparametre, modelltyper, features og terskler.
• •Testsett: gir ett ærlig sluttestimat og røres én gang, helt til slutt.

Hvorfor så streng med testsettet? Hver gang et resultat påvirker et valg, har vi tilpasset oss akkurat de dataene. Prøver du 50 varianter og velger den beste på valideringssettet, er valideringsfeilen til vinneren litt for optimistisk, fordi noe av forspranget er flaks. Bruker du testsettet til å velge, har det blitt enda et valideringssett, og du har ikke lenger noe ærlig estimat igjen. Den vanlige oppskriften er å velge hyperparametre på validering, trene den valgte modellen på trening og validering sammen, og evaluere én gang på test.

Med bare 12 valideringspunkter avhenger valget av hvilke punkter som tilfeldigvis havnet der. Det er motivasjonen for kryssvalidering i neste steg.

Ett valideringssett gir et støyete estimat, særlig når datasettet er lite. Kryssvalidering bruker dataene bedre. I k-fold kryssvalidering deles dataene i $k$ like store, ikke-overlappende folder. Modellen trenes $k$ ganger, og hver gang er én fold validering og de $k-1$ andre trening. Hvert punkt brukes altså til validering nøyaktig én gang. Resultatet er gjennomsnittet ƒgjennomsnittlig kryssvalideringsscore,

og spredningen mellom foldene sier hvor stabilt estimatet er. Med $n$ punkter har hver fold $n/k$ punkter og hvert treningssett $n(k-1)/k$. Vanlige valg er $k=5$ eller $k=10$, og $k=n$ kalles leave-one-out. For klassifikasjon brukes ofte stratifiserte folder som bevarer klasseandelene, og for tidsserier må valideringsdataene ligge etter treningsdataene i tid.

Den store fella er lekkasje. Alt som tilpasses til data, må tilpasses bare på treningsdelen i hver fold: skalering, imputering, featureutvalg og resampling. Skalerer du hele datasettet før kryssvalideringen, har valideringsfolden påvirket tallene som brukes til å transformere den, og estimatet blir for optimistisk. Løsningen i scikit-learn er en Pipeline. Preprocessing og modell pakkes i ett objekt, og cross_val_score tilpasser hele pipelinen på nytt i hver fold.

Dataene i koden er ren støy, så en ærlig modell bør treffe rundt 0,5.

import numpy as np
from sklearn.feature_selection import SelectKBest, f_classif
from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import StratifiedKFold, cross_val_score
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

rng = np.random.default_rng(4172)
X = rng.normal(size=(100, 500))   # 500 features med ren støy
y = rng.integers(0, 2, size=100)  # labels uten sammenheng med X
k = 10  # @param 1..100
folder = StratifiedKFold(n_splits=5, shuffle=True, random_state=0)

# Riktig: skalering og utvalg tilpasses på nytt i hver treningsfold
modell = make_pipeline(StandardScaler(), SelectKBest(f_classif, k=k),
                       LogisticRegression(max_iter=1000))
riktig = cross_val_score(modell, X, y, cv=folder)

# Galt: featurene velges med ALLE labels før kryssvalideringen
X_lekk = SelectKBest(f_classif, k=k).fit_transform(X, y)
galt = cross_val_score(LogisticRegression(max_iter=1000), X_lekk, y, cv=folder)

print(f"pipeline (riktig):    {riktig.mean():.2f}")
print(f"utvalg før CV (galt): {galt.mean():.2f}")

Bootstrap er en annen måte å lage mange trenings- og valideringssett på. Fra $n$ punkter trekker vi $n$ punkter med tilbakelegging: hvert trekk velger et tilfeldig punkt, og punktet legges tilbake før neste trekk. Utvalget får samme størrelse som originalen, men noen punkter kommer med flere ganger og andre ikke i det hele tatt.

Hvor mange blir aldri trukket? Sannsynligheten for at et bestemt punkt bommes i ett trekk er $1-1/n$, og i alle $n$ trekk blir den ƒout-of-bag-andel:

Omtrent 36,8 % av punktene havner altså utenfor utvalget. De kalles out-of-bag (OOB) og fungerer som valideringssett for modellen som ble trent på utvalget. De resterende 63,2 % er de unike punktene i treningssettet, og duplikater fyller opp til $n$. Gjentar vi dette mange ganger, får vi en hel fordeling av scorer, og spredningen gir et mål på usikkerheten.

Forskjellene mot k-fold er verdt å kunne presist:

• •Trekning: k-fold deler uten tilbakelegging i disjunkte folder; bootstrap trekker med tilbakelegging.
• •Validering: i k-fold er hvert punkt validering nøyaktig én gang; i bootstrap er et punkt OOB i omtrent 37 % av rundene.
• •Treningssett: i k-fold består det av $n(k-1)/k$ unike punkter uten duplikater; i bootstrap av $n$ trekk, men bare rundt $0,632n$ unike punkter.

Fordi bootstrap-modellen bare ser rundt 63 % unike punkter, blir OOB-estimatet ofte litt pessimistisk. Bootstrap er særlig nyttig for å anslå usikkerhet, og det er motoren i bagging og random forest i kapittel 10.

import numpy as np

rng = np.random.default_rng(10)
n = 1000  # @param 2..2000
gjentak = 200                                  # antall bootstrap-utvalg

trekk = rng.integers(0, n, size=(gjentak, n))  # hver rad: n trekk MED tilbakelegging
antall = np.array([np.bincount(rad, minlength=n) for rad in trekk])   # ganger hvert punkt ble trukket

print(f"aldri trukket (out-of-bag):  {np.mean(antall == 0):.3f}")
print(f"trukket nøyaktig én gang:    {np.mean(antall == 1):.3f}")
print(f"trukket to ganger eller mer: {np.mean(antall >= 2):.3f}")
print(f"teori for out-of-bag: (1 - 1/n)^n = {(1 - 1 / n) ** n:.3f}, grensen 1/e = {np.exp(-1):.3f}")