Support Vector Machines – forelesning 2

Ikke-lineære grenser, kjerner og modellvurdering

Forfatter

Øystein Myrland

Om forelesningen

Pensum: James, Witten, Hastie, Tibshirani og Taylor, An Introduction to Statistical Learning, 2. utgave, avsnitt 9.3–9.5 og resten av laben i 9.6.
Videoer: 9.3 «Feature Expansion and the SVM» og 9.4 «Example and Comparison with Logistic Regression».
Kodeeksemplene bruker pakken e1071; kjør install.packages("e1071") én gang.

Fra videoene – dette skal du kunne fra før

Vi kan få en buet grense ved å utvide prediktorene med for eksempel $x_1^2$, $x_2^2$ og $x_1x_2$.
Klassifikatoren kan skrives med indre produkter mellom observasjoner, og en kjerne erstatter det indre produktet.
Radialkjernen har en parameter $\gamma$ som styrer hvor lokal modellen er.
ROC-kurver og AUC, «én mot alle» og «én mot én», og hengseltapet.

I dag skal vi teste påstandene i videoene på egne data.
Gir en mer fleksibel modell bedre prediksjoner?
Og hva skal vi med en SVM når vi allerede kan logistisk regresjon?

1 Læringsmål

Etter forelesningen skal du kunne vise hvordan nye variabler kan skape en buet (ikke-lineær) grense.
Du skal kunne forklare idéen bak kjernetrikset uten å utlede optimeringsalgoritmen.
Du skal kunne tolke radialkjernens $\gamma$ og cost og sammenligne modeller med holdt-ut testdata.
Og du skal kunne forklare forskjellen mellom en SVM-skår, ROC/AUC og en kalibrert sannsynlighet.

2 Repetisjon: hvorfor er ikke en rett linje nok?

Se for deg kunder med mellomstor aktivitet i sentrum av et diagram og kunder med både svært lav og svært høy aktivitet rundt dem.
Ingen rett linje kan skille sentrum fra ringen.
Endring av cost kan flytte en lineær grense, men ikke gjøre den buet.

Figur 1: FIGURE 9.8. Left: The observations fall into two classes, with a non-linear boundary between them. Right: The support vector classifier seeks a linear boundary, and consequently performs very poorly.

3 Utvidelse av prediktorene

En løsning er å legge til transformasjoner: $x_1^2$, $x_2^2$ og $x_1x_2$.
I det utvidede rommet kan en lineær grense være

\[ f(x)=\beta_0+\beta_1x_1+\beta_2x_2+ \beta_3x_1^2+\beta_4x_2^2+\beta_5x_1x_2. \]

I det opprinnelige $(x_1,x_2)$-planet er $f(x)=0$ en buet grense.
En ring kan for eksempel skilles ved et uttrykk av typen $x_1^2+x_2^2-r^2=0$.
Dette kjenner dere fra økonometrien: en regresjon med kvadratledd er fortsatt lineær i parameterne.

Figur 2: FIGURE 9.9. Left: An SVM with a polynomial kernel of degree 3 is applied to the non-linear data from Figure 9.8, resulting in a far more appropriate decision rule. Right: An SVM with a radial kernel is applied. In this example, either kernel is capable of capturing the decision boundary.

Stopp og tenk

Med $p$ prediktorer og alle ledd opp til grad $d$ får vi $\binom{p+d}{d}-1$ variabler.
Regn ut antallet for $p=2,\ d=2$ og for $p=50,\ d=3$.
Hvorfor blir eksplisitt polynomutvidelse raskt upraktisk?

Svar: Stopp og tenk

Med $p=2,\ d=2$:

\[ \binom{4}{2}-1 = 6-1 = 5. \]

De fem variablene er $x_1,\ x_2,\ x_1^2,\ x_2^2$ og $x_1x_2$, altså de samme som i ligningen over.
«$-1$» trekker fra konstantleddet, som ikke regnes som en variabel.

Med $p=50,\ d=3$:

\[ \binom{53}{3}-1 = \frac{53\cdot 52\cdot 51}{3\cdot 2\cdot 1}-1 = 23\,426-1 = 23\,425. \]

Fordelt på grad:

Grad	Type ledd	Antall
1	$x_j$	50
2	$x_j^2$ og $x_jx_k$	$50+1\,225=1\,275$
3	$x_j^3$, $x_j^2x_k$ og $x_jx_kx_l$	22 100
	Sum	23 425

Fra 50 prediktorer går vi altså til over 23 000 variabler.

Hvorfor dette blir upraktisk:
Antallet eksploderer. Det vokser omtrent som $p^d/d!$, så hver ekstra grad ganger antallet med omtrent $p/d$.
Mange flere variabler enn observasjoner. Med noen hundre eller tusen observasjoner og 23 425 variabler finnes det nesten alltid en grense som skiller treningsdataene perfekt. Det sier ingenting om prediksjonsevnen, og faren for overtilpasning er stor.
Regnebyrden. Vi må lage, lagre og regne med en $n\times 23\,425$-matrise.
Sterk multikollinearitet. Ledd som $x_j$, $x_j^2$ og $x_j^3$ er sterkt korrelerte.
Tolkningen forsvinner. Ingen kan tolke 22 100 tredjegradsledd hver for seg.

Fra økonometrien kjenner dere samme problem i en translog-funksjon med mange innsatsfaktorer, der antall andregradsledd vokser raskt.

En Cobb–Douglas-funksjon med to innsatsfaktorer kan skrives:

\[ y=A x^{\beta_x}z^{\beta_z}, \]

eller på logaritmisk form:

\[ \ln y=\ln A+\beta_x\ln x+\beta_z\ln z. \]

Translog-formen utvider denne med kvadrerte ledd og et samspillsledd:

\[ \ln y =\beta_0+\beta_x\ln x+\beta_z\ln z +\frac{1}{2}\beta_{xx}(\ln x)^2 +\beta_{xz}(\ln x)(\ln z) +\frac{1}{2}\beta_{zz}(\ln z)^2. \]

Med bare $x$ og $z$ får vi altså tre andregradsledd. Med $K$ innsatsfaktorer blir antallet $K(K+1)/2$; med ti innsatsfaktorer blir det 55. Cobb–Douglas er spesialtilfellet der alle koeffisientene til andregradsleddene er null.

Kjernetrikset er løsningen.
Polynomkjernen $(1+\langle x,z\rangle)^3$ krever bare ett indre produkt med 50 ledd, opphøyd i tredje.
Den gir likevel et indre produkt i det utvidede rommet med alle de 23 425 leddene, med bestemte vekter på hvert ledd.
Vi får fleksibiliteten uten å lage variablene.
Radialkjernen går enda lenger: den svarer til et uendelig-dimensjonalt rom, som det er umulig å lage eksplisitt.

4 Kjernetrikset: sammenlign par av observasjoner

Den lineære støttevektorklassifikatoren kan skrives ved indre produkter mellom observasjoner:

\[ f(x)=\beta_0+\sum_{i\in\mathcal S}\alpha_i\langle x,x_i\rangle, \qquad \langle x,x_i\rangle=\sum_{j=1}^{p}x_jx_{ij}. \]

$\mathcal S$ er mengden av støttevektorer; for alle andre observasjoner er $\hat\alpha_i=0$.
Ved å bytte ut det indre produktet med en kjernefunksjon $K(x,x_i)$ får vi

\[f(x)=\beta_0+\sum_{i\in\mathcal S}\alpha_i K(x,x_i).\]

Kjernen er et mål på likhet mellom to observasjoner som svarer til et indre produkt i et utvidet variabelrom.
Vi slipper å lage alle de nye variablene eksplisitt.
Polynomkjernen av grad $d$ er

\[K_{\mathrm{poly}}(x,z)=(1+\langle x,z\rangle)^d.\]

Grensen blir buet i de opprinnelige variablene, men klassifikatoren er lineær i det utvidede rommet.

Sparsomhet i observasjonene, ikke i variablene

Lasso setter mange koeffisienter lik null og velger dermed variabler.
SVM setter mange observasjonsvekter $\alpha_i$ lik null og «velger» dermed observasjoner.
En SVM bruker alle prediktorene, men bare støttevektorene.

5 Radialkjerne: hvor lokalt påvirker et punkt?

\[ K_{\mathrm{radial}}(x,z) =\exp\{-\gamma\lVert x-z\rVert^2\},\qquad \gamma>0. \]

Nære observasjoner får kjerneverdi nær 1, mens fjerne observasjoner får verdi nær 0.
Høy $\gamma$ gir svært lokal påvirkning og kan gi en urolig grense.
Lav $\gamma$ gir bredere påvirkning og glattere grense.
Også cost påvirker fleksibiliteten, så de to må velges sammen.
I e1071 er standardverdien gamma = 1/p.

Parameter i `e1071`	Lav verdi	Høy verdi
`gamma` for radialkjerne	Likhet avtar sakte med avstand: glatt grense	Likhet avtar raskt med avstand: urolig grense
`cost`	Marginbrudd straffes lite	Marginbrudd straffes mye

Radialkjernen svarer til et indre produkt i et uendelig-dimensjonalt rom (figuren under til høyre).
Hvorfor overtilpasser ikke modellen alltid?
Svaret i video 9.3 er at de mest «urolige» retningene i dette rommet får svært liten vekt, og straffen på marginen virker som regularisering.
Men som vi skal se, beskytter det ikke mot et dårlig valg av $\gamma$ og cost.

Figur 3: FIGURE 9.9. Left: An SVM with a polynomial kernel of degree 3 is applied to the non-linear data from Figure 9.8, resulting in a far more appropriate decision rule. Right: An SVM with a radial kernel is applied. In this example, either kernel is capable of capturing the decision boundary.

6 Kode: sirkeldata, lineær SVC og radial SVM

Her er sentrum én klasse og ringen den andre.
Dataene er simulert, slik at geometrien er synlig, og klassene overlapper litt.
Konklusjonene gjelder dette eksemplet og kan ikke overføres ukritisk til andre datasett.

Kode

if (!requireNamespace("e1071", quietly = TRUE)) {
  stop("Installer pakken med install.packages('e1071') før du gjengir dokumentet.")
}
library(e1071)

set.seed(93)
n2 <- 240
klasse <- rep(c("Sentrum", "Ring"), each = n2 / 2)
vinkel <- runif(n2, 0, 2 * pi)
radius <- c(runif(n2 / 2, 0, 1.2), runif(n2 / 2, 0.9, 2.1))
dat_ring <- data.frame(
  x1 = radius * cos(vinkel) + rnorm(n2, sd = 0.2),
  x2 = radius * sin(vinkel) + rnorm(n2, sd = 0.2),
  y  = factor(klasse, levels = c("Sentrum", "Ring"))
)
plot(dat_ring$x1, dat_ring$x2,
     col = ifelse(dat_ring$y == "Ring", "#cc583b", "#276ca6"),
     pch = 19, xlab = "x1", ylab = "x2", asp = 1)
legend("topright", legend = levels(dat_ring$y),
       col = c("#276ca6", "#cc583b"), pch = 19, bty = "n")

Figur 4: Et klassifikasjonsproblem med én klasse i sentrum og én rundt.

Før vi tilpasser modellene, legger vi til side et testsett.
Vi velger cost og gamma kun med kryssvalidering på treningsdata.

Kode

set.seed(94)
id_ring <- unlist(lapply(split(seq_len(nrow(dat_ring)), dat_ring$y),
                         function(ii) sample(ii, size = round(0.7 * length(ii)))))
train_ring <- dat_ring[id_ring, ]
test_ring  <- dat_ring[-id_ring, ]

set.seed(95)
cv_rett <- tune(
  svm, y ~ ., data = train_ring, kernel = "linear",
  ranges = list(cost = c(0.1, 1, 10)),
  tunecontrol = tune.control(cross = 5)
)
set.seed(95)
cv_radial <- tune(
  svm, y ~ ., data = train_ring, kernel = "radial",
  ranges = list(cost = c(0.01, 0.1, 1, 10, 100), gamma = c(0.05, 0.2, 1, 5)),
  tunecontrol = tune.control(cross = 5)
)

cv_rett$best.parameters

  cost
2    1

Kode

cv_radial$best.parameters

   cost gamma
10  100   0.2

Kode

# De seks beste kombinasjonene, sortert etter CV-feil
perf <- summary(cv_radial)$performances
head(perf[order(perf$error), ], 6)

    cost gamma     error dispersion
10 100.0   0.2 0.1611408 0.07034621
7    0.1   0.2 0.1672014 0.09248271
18   1.0   5.0 0.1787879 0.06445397
8    1.0   0.2 0.1789661 0.09628845
9   10.0   0.2 0.1848485 0.05099566
13   1.0   1.0 0.1909091 0.07645791

Vi bruker kryssvalidering (cross-validation, forkortet CV) til å velge cost.
Med CV-feil mener vi den gjennomsnittlige andelen feilklassifiserte observasjoner i valideringsfoldene.
Forkortelsen CV må ikke forveksles med variasjonskoeffisienten (coefficient of variation), som også ofte forkortes CV.

Diskuter:
Mange kombinasjoner av cost og gamma har nesten samme CV-feil, og forskjellene er små i forhold til dispersion.
Hva betyr det for hvor mye vi skal stole på akkurat den «beste» kombinasjonen?

Svar: Diskuter

Vi skal ikke stole mye på akkurat den «beste» kombinasjonen.
I vår kjøring vinner cost = 100 og gamma = 0,2 med CV-feil 0,161.
Rett bak ligger cost = 0,1 og gamma = 0,2 med 0,167, og deretter flere kombinasjoner mellom 0,179 og 0,191.
dispersion ligger rundt 0,05–0,10, så standardfeilen til gjennomsnittet er omtrent $0{,}07/\sqrt{5}\approx 0{,}03$.
Forskjellen mellom nummer én og nummer to er 0,006.
Treningsdelen har 168 observasjoner, så 0,006 svarer til én feilklassifisert observasjon.

Flere ting å legge merke til:

Toppen spenner over et enormt område.
cost varierer med en faktor 1000 (fra 0,1 til 100) blant de beste kombinasjonene.
Feilflaten er altså en flat dal, ikke en skarp topp.
Det betyr at mange modeller er omtrent like gode.
Det betyr også at CV ikke kan fortelle oss hvilken som er best.

cost og gamma kan erstatte hverandre.
Både høy cost og høy gamma gjør modellen mer fleksibel.
Ulike kombinasjoner kan derfor gi omtrent like fleksible grenser, og dermed omtrent samme feil.

Vinneren ligger i kanten av rutenettet.
cost = 100 er den største verdien vi prøvde.
Vanligvis er det et tegn på at rutenettet bør utvides.
Men når flaten er så flat, betyr det lite her.

Vinneren er avhengig av tilfeldighet.
Med et annet frø blir foldene annerledes, og en annen kombinasjon kan vinne.

Den laveste CV-feilen er for optimistisk.
Når vi velger minimum av 20 usikre tall, plukker vi delvis den som tilfeldigvis var heldig.
Det er en grunn til at vi trenger et separat testsett.
Her er CV-treffet $1-0{,}161=0{,}839$, mens testnøyaktigheten ble 0,806.

Hva gjør vi da?
Én-standardfeil-regelen sier at vi skal velge den glatteste modellen med CV-feil innenfor omtrent 0,03 av den beste.
For en radial SVM betyr det lav cost og lav gamma.
Her er det cost = 0,1 og gamma = 0,2, med CV-feil 0,167.
Den gir en mer stabil grense, og vi taper praktisk talt ingenting i CV-feil.

Det viktigste vi lærer av tabellen er ikke ett tall, men et område: lav gamma (0,2) fungerer godt for mange verdier av cost.

Kode

# Tegner beslutningsgrense og marginer ved å regne ut f(x) på et rutenett
tegn_grense <- function(mod, data, main = "") {
  x1 <- seq(min(data$x1), max(data$x1), length.out = 150)
  x2 <- seq(min(data$x2), max(data$x2), length.out = 150)
  rutenett <- expand.grid(x1 = x1, x2 = x2)
  f <- attr(predict(mod, rutenett, decision.values = TRUE), "decision.values")[, 1]
  plot(data$x1, data$x2, col = ifelse(data$y == "Ring", "#cc583b", "#276ca6"),
       pch = 19, asp = 1, xlab = "x1", ylab = "x2", main = main)
  contour(x1, x2, matrix(f, 150), levels = 0, add = TRUE, lwd = 2, drawlabels = FALSE)
  contour(x1, x2, matrix(f, 150), levels = c(-1, 1), add = TRUE, lty = 2, drawlabels = FALSE)
  points(data[mod$index, c("x1", "x2")], cex = 1.6)
}

par(mfrow = c(1, 2))
tegn_grense(cv_rett$best.model, train_ring, main = "Lineær SVC")
tegn_grense(cv_radial$best.model, train_ring, main = "Radial SVM (CV-valgt)")
par(mfrow = c(1, 1))

Figur 5: Treningsdata og tilpassede grenser. Heltrukken linje er f(x) = 0, stiplede linjer er f(x) = ±1, ringer markerer støttevektorer.

6.1 Hva skjer når vi skrur opp fleksibiliteten?

Vi legger til en bevisst overtilpasset modell med cost = 100 og gamma = 50, som i laben i boka.

Kode

mod_overtilp <- svm(y ~ ., data = train_ring, kernel = "radial",
                    cost = 100, gamma = 50)

modeller <- list("Lineær SVC"           = cv_rett$best.model,
                 "Radial SVM (CV-valgt)" = cv_radial$best.model,
                 "Radial SVM (gamma 50)" = mod_overtilp)
treff <- function(mod, data) mean(predict(mod, data) == data$y)

data.frame(
  modell                = names(modeller),
  stottevektorer        = sapply(modeller, function(m) m$tot.nSV),
  treningsnoyaktighet   = round(sapply(modeller, treff, data = train_ring), 3),
  testnoyaktighet       = round(sapply(modeller, treff, data = test_ring), 3),
  row.names = NULL
)

                 modell stottevektorer treningsnoyaktighet testnoyaktighet
1            Lineær SVC            158               0.637           0.639
2 Radial SVM (CV-valgt)             61               0.857           0.806
3 Radial SVM (gamma 50)            159               1.000           0.694

Kode

tegn_grense(mod_overtilp, train_ring, main = "Radial SVM (gamma 50)")

Figur 6: Radial SVM med cost = 100 og gamma = 50 på treningsdata.

Diskuter:
Hvorfor gir gamma = 50 perfekt treff på trening, men dårligere treff på test?
Hvorfor må vi la være å prøve stadig nye valg etter å ha sett testresultatet?

Svar: Diskuter

Hvorfor perfekt på trening, men dårligere på test?
Radialkjernen er $K(x,z)=\exp\{-\gamma\lVert x-z\rVert^2\}$.
Med gamma = 50 faller likheten svært raskt med avstanden, målt i standardiserte enheter:

Avstand $\lVert x-z\rVert$	$K(x,z)$ med $\gamma=50$
0,1	$e^{-0{,}5}\approx 0{,}61$
0,2	$e^{-2}\approx 0{,}14$
0,3	$e^{-4{,}5}\approx 0{,}01$

Hver treningsobservasjon påvirker altså bare et lite område rett rundt seg selv.
Sammen med cost = 100, der brudd er svært dyre, kan modellen tegne en egen liten «øy» rundt nesten hvert punkt.
Det ser vi i figuren.
Modellen husker treningsdataene i stedet for å lære mønsteret, omtrent som en nærmeste-nabo-regel med én nabo.
Derfor blir treningstreffet 100 %.

Et nytt testpunkt havner sjelden nøyaktig der en treningsobservasjon lå.
Det havner ofte i en øy som bare skyldes støy i ett enkelt treningspunkt, eller i tomrommet mellom øyene.
I tomrommet er alle kjerneverdier nær null, så prediksjonen bestemmes nesten bare av konstantleddet.
Resultatet er 69 % treff på test, mot 81 % for den CV-valgte modellen.
Det er overtilpasning: svært lav skjevhet, men svært høy varians.

Hva med antall støttevektorer?
Den overtilpassede modellen bruker 159 av 168 observasjoner som støttevektorer, mens den CV-valgte bruker 61.
I forelesning 1 ga færre støttevektorer høyere varians, men der var kjernen lineær, og det var smal margin som ga få støttevektorer.
Her trenger nesten hvert punkt sin egen øy, og da blir nesten alle punktene støttevektorer.
Antall støttevektorer er altså ikke et enkelt mål på hvor fleksibel modellen er; vi må se det sammen med kjernen og gamma.

Hvorfor ikke prøve nye valg etter å ha sett testresultatet?
Testsettet skal gi et ærlig anslag på hvordan modellen gjør det på data den aldri har sett.
Hvis vi justerer cost, gamma eller kjernen fordi testresultatet var skuffende, blir testsettet en del av modellvalget.
Da er det i praksis bare enda en valideringsfold.

Testsettet har 72 observasjoner, så én observasjon utgjør 1,4 prosentpoeng.
Prøver vi mange varianter, vil noen tilfeldigvis passe godt til akkurat disse 72.
Den beste testnøyaktigheten blir da for optimistisk, av samme grunn som den laveste CV-feilen er det.

Dette er det samme problemet som spesifikasjonssøk i økonometrien.
Hvis vi prøver mange modeller og rapporterer den med best resultat, er ikke standardfeil og $p$-verdier lenger til å stole på.

Riktig arbeidsflyt:
All prøving og feiling skjer på treningsdataene, med kryssvalidering eller et eget valideringssett.
Testsettet brukes én gang, til slutt, og resultatet rapporteres uansett hva det viser.
Trenger vi å endre modellen etter det, trenger vi i prinsippet nye testdata.

6.2 Kjernetrikset er ikke magi

e1071 lagrer støttevektorene (SV), vektene $\alpha_i$ (coefs) og konstantleddet (rho $=-\beta_0$).
Da kan vi regne ut $f(x)=\beta_0+\sum_{i\in\mathcal S}\alpha_iK(x,x_i)$ for hånd og sammenligne med predict().

Kode

mod <- cv_radial$best.model

# Skaler testdata med treningsskalaen, slik svm() gjør internt
x_ny <- scale(as.matrix(test_ring[, c("x1", "x2")]),
              center = mod$x.scale$`scaled:center`,
              scale  = mod$x.scale$`scaled:scale`)

# Kvadrerte avstander mellom hvert testpunkt og hver støttevektor
avstand2 <- outer(rowSums(x_ny^2), rowSums(mod$SV^2), "+") - 2 * x_ny %*% t(mod$SV)
K <- exp(-mod$gamma * avstand2)              # radialkjernen

f_for_haand <- drop(K %*% mod$coefs) - mod$rho
f_e1071 <- attr(predict(mod, test_ring, decision.values = TRUE), "decision.values")

c(antall_stottevektorer = nrow(mod$SV),
  storste_avvik = max(abs(f_for_haand - f_e1071[, 1])))

antall_stottevektorer         storste_avvik 
          6.10000e+01           5.82645e-13

Prediksjonen for et nytt punkt er altså en vektet sum av hvor likt punktet er hver støttevektor.
Observasjonene som ikke er støttevektorer, er ikke med i summen i det hele tatt.

7 Ulike mål svarer på ulike spørsmål

7.1 Forvekslingsmatrisen og de fire utfallene

En klassifikator med to klasser kan ta feil på to måter.
For å holde orden på dem velger vi én klasse som positiv.
I kredittvurdering er det vanlig å la mislighold være positiv klasse, fordi det er den hendelsen vi vil oppdage.
«Positiv» betyr altså «den klassen vi leter etter», ikke at utfallet er godt.

Hver observasjon havner i én av fire ruter i forvekslingsmatrisen (engelsk confusion matrix):

	Predikert: mislighold	Predikert: ikke mislighold
Faktisk: mislighold	$TP$ – sann positiv	$FN$ – falsk negativ
Faktisk: ikke mislighold	$FP$ – falsk positiv	$TN$ – sann negativ

Forkortelsene kommer fra engelsk, og de er bygget opp på samme måte:
den første bokstaven sier om prediksjonen var riktig (True, T) eller feil (False, F), og den andre sier hva modellen predikerte (Positive, P, eller Negative, N).

$TP$ (True Positive, sann positiv): modellen sa mislighold, og kunden misligholdt. Riktig.
$TN$ (True Negative, sann negativ): modellen sa ikke mislighold, og kunden betalte. Riktig.
$FP$ (False Positive, falsk positiv): modellen sa mislighold, men kunden ville ha betalt. Banken avviser en god kunde. Kalles også falsk alarm eller type I-feil.
$FN$ (False Negative, falsk negativ): modellen sa ikke mislighold, men kunden misligholdt. Banken låner ut til en kunde som ikke betaler. Kalles også oversett tilfelle eller type II-feil.

Eksempel fra forelesning 1. Den lineære SVC-en ga denne matrisen på de 30 testsøknadene:

	Predikert: mislighold	Predikert: ikke mislighold	Sum
Faktisk: mislighold	$TP=8$	$FN=3$	11
Faktisk: ikke mislighold	$FP=2$	$TN=17$	19

7.2 Mål regnet ut fra matrisen

Alle de vanlige målene er andeler regnet ut fra disse fire tallene.
Poenget er at de deler på ulike totaler, og derfor svarer de på ulike spørsmål.

Mål	Andre navn	Formel	Spørsmål målet svarer på	Eksempel
Nøyaktighet	Accuracy	$\dfrac{TP+TN}{TP+TN+FP+FN}$	Hvor stor andel av alle ble riktig klassifisert?	$25/30=0{,}83$
Sensitivitet	$TPR$ (True Positive Rate), recall, treffrate	$\dfrac{TP}{TP+FN}$	Av dem som faktisk misligholdt, hvor mange fanget modellen?	$8/11=0{,}73$
Spesifisitet	$TNR$ (True Negative Rate)	$\dfrac{TN}{TN+FP}$	Av dem som faktisk betalte, hvor mange ble korrekt godkjent?	$17/19=0{,}89$
Falsk positiv-rate	$FPR$ (False Positive Rate)	$\dfrac{FP}{FP+TN}=1-\text{spesifisitet}$	Av dem som faktisk betalte, hvor mange ble feilaktig avvist?	$2/19=0{,}11$
Presisjon	$PPV$ (Positive Predictive Value)	$\dfrac{TP}{TP+FP}$	Av dem modellen flagget, hvor mange misligholdt faktisk?	$8/10=0{,}80$

Sensitivitet og spesifisitet deler på det faktiske utfallet (radene i matrisen).
Presisjon deler på det predikerte utfallet (kolonnen).
Sensitivitet er det banken bryr seg om når den vil unngå tap.
Presisjon er det banken bryr seg om når den lurer på hvor mange av de avviste som faktisk var dårlige kunder.

7.3 Hvorfor nøyaktighet alene kan lure oss

Anta at bare 5 % av kundene misligholder.
En «modell» som alltid sier «ikke mislighold», får da 95 % nøyaktighet.
Men sensitiviteten er 0: den oppdager ikke en eneste misligholder.
Når klassene er ubalanserte, må vi derfor alltid se på sensitivitet og spesifisitet, ikke bare nøyaktighet.

De to feiltypene koster dessuten svært forskjellig.
En $FN$ kan koste banken hele lånebeløpet.
En $FP$ koster renteinntektene fra en god kunde, og kanskje kunden.
Hvilken balanse mellom dem som er best, er et økonomisk spørsmål, ikke et statistisk.

7.4 Terskelen: én modell, mange klassifikasjonsregler

En SVM gir en skår $f(x)$, og standardregelen er å si «mislighold» når $f(x)>0$.
Men vi kan like gjerne bruke en annen terskel $c$ og si «mislighold» når $f(x)>c$:

Lavere terskel: flere kunder blir flagget. Sensitiviteten øker, men det gjør også antall falske positive, så spesifisiteten faller.
Høyere terskel: færre kunder blir flagget. Spesifisiteten øker, men flere misligholdere slipper gjennom.

Hver terskel gir altså sin egen forvekslingsmatrise.
Valg av terskel avhenger av beslutningen modellen skal støtte og av hva feilene koster.

7.5 ROC-kurven

ROC står for Receiver Operating Characteristic.
Navnet kommer fra radarteknikk under andre verdenskrig, der operatørene måtte balansere mellom å oppdage fly og å slå falsk alarm.

ROC-kurven tegner sensitiviteten ($TPR$) på den loddrette aksen mot falsk positiv-raten ($FPR$) på den vannrette, for alle mulige terskler $c$:

Med en svært høy terskel flagges ingen: $TPR=0$ og $FPR=0$, nederst til venstre.
Med en svært lav terskel flagges alle: $TPR=1$ og $FPR=1$, øverst til høyre.
Kurven mellom disse punktene viser hvilke kombinasjoner av treff og falske alarmer modellen kan gi.

En perfekt modell går rett opp til øvre venstre hjørne: alle misligholdere oppdages før én eneste god kunde avvises.
Diagonalen fra $(0,0)$ til $(1,1)$ svarer til å gjette tilfeldig.
Jo nærmere kurven går øvre venstre hjørne, desto bedre skiller skåren klassene.

7.6 AUC

AUC står for Area Under the Curve, arealet under ROC-kurven.
Det oppsummerer hele kurven i ett tall mellom 0 og 1.
AUC har en nyttig tolkning: det er sannsynligheten for at en tilfeldig valgt misligholder får høyere skår enn en tilfeldig valgt kunde som betaler.

AUC $\approx$ 0,5: skåren rangerer ikke bedre enn tilfeldig, som diagonalen.
AUC = 1: perfekt rangering; alle misligholdere får høyere skår enn alle som betaler.
AUC < 0,5: modellen rangerer motsatt vei, ofte et tegn på at fortegnet til skåren er snudd.

I kredittvurdering rapporteres ofte Gini-koeffisienten, som bare er en omskalering: $\text{Gini}=2\cdot\text{AUC}-1$.

To ting AUC ikke sier:
AUC måler bare rangering, ikke om skåren kan tolkes som en sannsynlighet.
Og AUC velger ingen terskel for oss; den sier hvor godt modellen kan skille klassene, ikke hvor godt en bestemt klassifikasjonsregel fungerer.

Vi lager ROC og AUC selv, slik at det er tydelig hva som beregnes.
SVM-skåren er beslutningsverdien $f(x)$.
e1071 setter fortegnet etter hvilken klasse som dukker opp først i dataene, så vi snur skåren slik at høy verdi alltid betyr «Ring».

Kode

skaar <- function(mod, data, positiv = "Ring") {
  f <- attr(predict(mod, data, decision.values = TRUE), "decision.values")
  forste_klasse <- strsplit(colnames(f), "/")[[1]][1]
  if (forste_klasse == positiv) f[, 1] else -f[, 1]
}
roc_punkter <- function(s, y, positiv = "Ring") {
  terskler <- sort(unique(c(Inf, s)), decreasing = TRUE)
  data.frame(
    fpr = sapply(terskler, function(t) mean(s[y != positiv] >= t)),
    tpr = sapply(terskler, function(t) mean(s[y == positiv] >= t))
  )
}
auc <- function(s, y, positiv = "Ring") {
  s_pos <- s[y == positiv]
  s_neg <- s[y != positiv]
  mean(outer(s_pos, s_neg, ">") + 0.5 * outer(s_pos, s_neg, "=="))
}

Kode

farger <- c("grey40", "#276ca6", "#cc583b")
par(mfrow = c(1, 2))
for (del in c("Treningsdata", "Testdata")) {
  d <- if (del == "Treningsdata") train_ring else test_ring
  plot(NULL, xlim = c(0, 1), ylim = c(0, 1), asp = 1, main = del,
       xlab = "Andel falske positive (FPR)", ylab = "Sensitivitet (TPR)")
  abline(0, 1, lty = 3)
  for (k in seq_along(modeller)) {
    lines(roc_punkter(skaar(modeller[[k]], d), d$y), col = farger[k], lwd = 2)
  }
  legend("bottomright", legend = names(modeller), col = farger,
         lwd = 2, bty = "n", cex = 0.8)
}
par(mfrow = c(1, 1))

data.frame(
  modell    = names(modeller),
  AUC_trening = round(sapply(modeller, function(m) auc(skaar(m, train_ring), train_ring$y)), 3),
  AUC_test    = round(sapply(modeller, function(m) auc(skaar(m, test_ring), test_ring$y)), 3),
  row.names = NULL
)

                 modell AUC_trening AUC_test
1            Lineær SVC       0.565    0.537
2 Radial SVM (CV-valgt)       0.947    0.910
3 Radial SVM (gamma 50)       1.000    0.674

Figur 7: ROC-kurver på treningsdata og testdata. Jf. video 9.4.

Dette er samme mønster som i hjertedataene i video 9.4: den mest fleksible modellen ser best ut på trening og dårligst ut på test.
En ROC-kurve på treningsdata er ikke et troverdig mål for framtidig ytelse.

8 SVM og logistisk regresjon

En lineær SVC kan skrives som «tap + straff» med hengseltap:

\[ \min_{\beta_0,\boldsymbol\beta} \sum_{i=1}^n\max\{0,1-y_i f(x_i)\} +\lambda\lVert\boldsymbol\beta\rVert^2. \]

Stor $\lambda$ svarer til stor $C_{\text{bok}}$ og liten cost.
Når $y_i f(x_i)\geq1$, er tapet null: slike observasjoner ligger på riktig side av marginen og påvirker ikke løsningen.
Logistisk regresjon bruker et glatt logaritmisk tap, $\log(1+e^{-y_if(x_i)})$, som aldri blir helt null.
Knekkpunktet i hengseltapet er grunnen til at SVM har støttevektorer.

Kode

z <- seq(-4, 3, length.out = 400)
plot(z, pmax(0, 1 - z), type = "l", lwd = 2, col = "#cc583b",
     xlab = expression(y[i] * f(x[i])), ylab = "Tap")
lines(z, log(1 + exp(-z)), lwd = 2, col = "#276ca6")
abline(v = 1, lty = 3)
legend("topright", legend = c("Hengseltap (SVM)", "Logistisk tap"),
       col = c("#cc583b", "#276ca6"), lwd = 2, bty = "n")

Figur 8: Hengseltap og logistisk tap som funksjon av y·f(x). Jf. figur 9.12 i boka.

Hvis logistisk regresjon får de riktige variablene, kan den gjøre jobben like godt.
Vi gir den kvadratleddene fra avsnittet om utvidelse av prediktorene:

Kode

logit_kv <- glm(y ~ x1 + x2 + I(x1^2) + I(x2^2) + I(x1 * x2),
                data = train_ring, family = binomial)
p_test <- predict(logit_kv, newdata = test_ring, type = "response")

data.frame(
  modell = c("Logit med kvadratledd", "Radial SVM (CV-valgt)"),
  testnoyaktighet = round(c(mean(ifelse(p_test > 0.5, "Ring", "Sentrum") == test_ring$y),
                            treff(cv_radial$best.model, test_ring)), 3),
  AUC_test = round(c(auc(p_test, test_ring$y),
                     auc(skaar(cv_radial$best.model, test_ring), test_ring$y)), 3)
)

                 modell testnoyaktighet AUC_test
1 Logit med kvadratledd           0.847    0.932
2 Radial SVM (CV-valgt)           0.806    0.910

Her visste vi hvilken transformasjon som trengtes, fordi vi selv simulerte en ring.
Kjernen er nyttig når vi ikke vet hvilke transformasjoner som trengs.

Egenskap	SVC/SVM	Logistisk regresjon
Typisk output	Klasse og beslutningsskår	Modellert sannsynlighet og klasse ved valgt terskel
Fleksibel grense	Kjerner, for eksempel radial	Krever transformasjoner du må velge selv
Tolkning av enkeltkoeffisienter	Vanskelig, særlig med kjerner	Direkte i lineær modell
Sannsynlighet	Nei; `probability = TRUE` gir en etterjustert (Platt-)sannsynlighet som må kontrolleres	Ja, men kalibreringen må fortsatt kontrolleres
Variabelutvalg	Nei, bruker alle prediktorer	Ja, med lasso-straff

Video 9.4 gir en tommelfingerregel.
Når klassene nesten kan skilles, gjør SVM det ofte bedre enn logistisk regresjon; dere kjenner problemet fra økonometrien, der ML-estimatoren for logit ikke finnes ved perfekt separasjon.
Når klassene overlapper mye, gjør regularisert logistisk regresjon det omtrent like godt.
Når grensen er ikke-lineær og vi ikke vet formen, er kjerne-SVM et effektivt valg.

Skårverdien fra en SVM er ikke automatisk en misligholdssannsynlighet.
Det er særlig viktig når beslutningen trenger et sannsynlighetsanslag, for eksempel for å beregne forventet tap.

Fra video 9.4: flere enn to klasser

Ved $K$ klasser kan vi lage $K$ «én mot resten»-modeller eller $K(K-1)/2$ «én mot én»-modeller.
e1071::svm() bruker «én mot én» automatisk når y har flere enn to nivåer.
Laben i boka viser dette, og bruker også genuttrykksdata med $p\gg n$, der en lineær kjerne er nok.

9 Vurder påstanden

En KI-assistent skrev dette – hva er galt?

«Radial SVM-en har AUC på trening nær 1, og beslutningsverdien for kunde A er 2,3.
Det betyr at modellen er nesten perfekt, og at kunde A med svært høy sannsynlighet tilhører den positive klassen.»

Finn minst to feil.
Hva måtte du gjort for å kunne si noe om sannsynligheten for kunde A?

Svar: Hva er galt?

Feil 1: AUC på trening sier ikke at modellen er god.
Treningsdataene er de samme observasjonene modellen er tilpasset til.
I vårt eksempel hadde modellen med gamma = 50 AUC på trening lik 1,000, men bare 0,674 på test.
Den var altså den dårligste av de radiale modellene på nye data.
For å si noe om hvor god modellen er, må AUC beregnes på testdata eller med kryssvalidering.

Feil 2: En beslutningsverdi er ikke en sannsynlighet.
Verdien 2,3 er $f(x)$, en skår som sier hvilken side av grensen kunden ligger på og hvor langt unna.
I formuleringen med cost ligger marginene ved $f(x)=\pm 1$, så 2,3 betyr at kunde A ligger godt utenfor marginen.
Men skalaen er vilkårlig.
Den avhenger av cost, gamma og hvordan prediktorene er skalert.
Skåren er ikke begrenset til intervallet $[0,1]$, og den samme kunden kan få helt ulik skår i to modeller som klassifiserer likt.
Det finnes ingen regel som oversetter 2,3 til «svært høy sannsynlighet».

Feil 3: Positivt fortegn betyr ikke nødvendigvis positiv klasse.
e1071 setter fortegnet etter hvilken klasse som dukker opp først i dataene, ikke etter hva vi har kalt positiv.
Derfor måtte vi snu skåren i funksjonen skaar().
Uten å sjekke colnames() på beslutningsverdiene vet vi ikke engang hvilken klasse 2,3 peker mot.

Feil 4: AUC sier noe om rangering i en gruppe, ikke om én kunde.
AUC er sannsynligheten for at en tilfeldig positiv får høyere skår enn en tilfeldig negativ.
Selv AUC = 1 på testdata betyr bare at rekkefølgen er riktig.
Det sier ingenting om hvor sannsynlig det er at nettopp kunde A misligholder.
Og «nesten perfekt rangering» betyr ikke nesten perfekt klassifikasjon med den terskelen vi faktisk bruker.

Hva måtte vi gjort for å si noe om sannsynligheten for kunde A?

1. Kalibrere skåren på data modellen ikke er tilpasset til.
Den vanligste metoden er Platt-skalering: en logistisk regresjon der utfallet $y$ forklares av skåren $f(x)$:

\[ \hat P(y=\text{positiv}\mid x)=\frac{1}{1+\exp\{-(a+b\,f(x))\}}. \]

Parameterne $a$ og $b$ må estimeres på valideringsdata eller med kryssvalidering, ikke på de samme dataene som SVM-en ble tilpasset til.
I e1071 gjør probability = TRUE dette med intern kryssvalidering:

mod_p <- svm(y ~ ., data = train_ring, kernel = "radial",
             cost = 0.1, gamma = 0.2, probability = TRUE)
p <- attr(predict(mod_p, test_ring, probability = TRUE), "probabilities")
head(p)   # én kolonne per klasse, med klassenavn

2. Kontrollere kalibreringen på testdata.
Grupper kundene etter predikert sannsynlighet, for eksempel 0–10 %, 10–20 % og så videre.
Sammenlign så med den faktiske andelen mislighold i hver gruppe.
Blant kunder med predikert sannsynlighet rundt 30 % bør omtrent 30 % faktisk misligholde.

3. Sjekke at grunnraten stemmer.
Hvis andelen mislighold i treningsdataene er en annen enn i kundemassen, for eksempel fordi utvalget er balansert, blir sannsynlighetene feil nivå.
Da må de justeres til den faktiske grunnraten.
Det samme problemet kjenner dere fra logit på et utvalg som er stratifisert etter utfallet.

Alternativt: Bruk en modell som er laget for å gi sannsynligheter, som logistisk regresjon, og kontroller kalibreringen der også.
Det er nettopp sannsynligheter banken trenger for å regne ut forventet tap.

10 Praktisk sjekkliste og avslutning

Definer klasse og formål: skal modellen rangere, klassifisere eller gi en sannsynlighet?
Del data før tuning; bruk bare treningsdata i kryssvalidering og skalering.
Start med en lineær SVC eller en logistisk regresjon. Prøv radial SVM hvis mønsteret tilsier en buet grense.
Velg cost og eventuelt gamma med kryssvalidering, og se på usikkerheten i CV-feilen.
Sammenlign modellene én gang på holdt-ut testdata.
Rapporter forvekslingsmatrise og relevante mål, ikke bare treningsnøyaktighet.
Sjekk klasseubalanse, datalekkasjer og om skårene faktisk kan brukes til beslutningsformålet.

Avsluttende spørsmål: En bank får samme AUC fra logistisk regresjon og radial SVM.
Banken må også beregne forventet tap per kunde.
Hvilken tilleggsinformasjon trenger den før den kan bruke noen av modellene til dette formålet?

Svar: Avsluttende spørsmål

Utgangspunkt: forventet tap har tre deler.
I bank og i kapitalkravsregelverket (Basel) skrives forventet tap for en kunde som

\[ EL = PD\times LGD\times EAD, \]

der

$PD$ (Probability of Default) er sannsynligheten for at kunden misligholder innen en gitt periode, typisk ett år,
$LGD$ (Loss Given Default) er andelen av beløpet banken taper hvis kunden misligholder, etter at sikkerhet er realisert,
$EAD$ (Exposure at Default) er hvor mye kunden skylder på misligholdstidspunktet.

Begge modellene våre handler bare om den første faktoren.
Og lik AUC sier ikke engang at de gir en brukbar $PD$.

1. En kalibrert sannsynlighet, ikke bare en god rangering.
Lik AUC betyr at modellene rangerer kundene omtrent like godt.
Men $EL$ krever at $PD$ har riktig nivå: blant kunder med $PD=0{,}04$ skal omtrent 4 % faktisk misligholde.
- Radial SVM gir bare en skår $f(x)$. Den må først gjøres om til en sannsynlighet, for eksempel med Platt-skalering på data modellen ikke er tilpasset til.
- Logistisk regresjon gir en sannsynlighet direkte, men den kan også være feilkalibrert, for eksempel hvis modellen er feilspesifisert eller regularisert.

For begge trenger banken dokumentasjon på kalibreringen, med en kalibreringsplott eller tabell på testdata.

2. Riktig grunnrate og tidshorisont.
Hvis andelen mislighold i treningsdataene avviker fra andelen i kundemassen, for eksempel fordi utvalget er balansert eller bare inneholder innvilgede lån, blir sannsynlighetsnivået feil.
Det må være klart hva $PD$ gjelder for: mislighold innen 12 måneder, innen lånets løpetid, eller noe annet.

3. Stabilitet over tid.
En modell estimert i gode tider kan undervurdere $PD$ i en nedgangskonjunktur.
Banken bør teste modellen på data fra en senere periode enn treningsdataene (out-of-time-validering), ikke bare på et tilfeldig testsett.

4. Data om $LGD$ og $EAD$.
Dette er egne størrelser som krever egne data og ofte egne modeller: sikkerhet, pantets verdi, nedbetalingsplan og utnyttelse av kredittrammer.
Ingen av klassifikasjonsmodellene sier noe om dette.

5. Krav til forklaring.
Banken må kunne begrunne beslutninger overfor kunder og tilsynsmyndigheter.
En logistisk regresjon har koeffisienter som kan tolkes og dokumenteres.
En radial SVM er langt vanskeligere å forklare.

Konklusjon:
Med lik AUC og et mål om å beregne forventet tap har logistisk regresjon et klart fortrinn: den gir sannsynligheter direkte og er enklere å forklare.
SVM-en kan brukes, men bare etter et ekstra kalibreringssteg som må valideres.
Uansett modell trenger banken kalibrert $PD$, riktig grunnrate og tidshorisont, validering over tid, og egne anslag på $LGD$ og $EAD$.

Kilder og kobling til videoene

An Introduction to Statistical Learning, 2. utgave: §9.3 SVM og kjerner; §9.4 flerklasse; §9.5 sammenheng med logistisk regresjon; §9.6.2–9.6.5 lab.
Video 9.3 «Feature Expansion and the SVM»: utvidede variabler, indre produkter og kjerner.
Video 9.4 «Example and Comparison with Logistic Regression»: ROC, flerklasse og hengseltap.
R-koden bygger på kapittel 9-laben med e1071; ROC og AUC er skrevet i base R i stedet for med ROCR.

--- title: "Support Vector Machines – forelesning 2" subtitle: "Ikke-lineære grenser, kjerner og modellvurdering" author: "Øystein Myrland" lang: nb format: html: theme: cosmo toc: true toc-depth: 3 number-sections: true code-fold: show code-tools: true embed-resources: true fig-width: 7 fig-height: 5 execute: warning: false message: false echo: true --- ## Om forelesningen {.unnumbered} **Pensum:** James, Witten, Hastie, Tibshirani og Taylor, *An Introduction to Statistical Learning*, 2. utgave, avsnitt 9.3–9.5 og resten av laben i 9.6. **Videoer:** 9.3 «Feature Expansion and the SVM» og 9.4 «Example and Comparison with Logistic Regression». Kodeeksemplene bruker pakken `e1071`; kjør `install.packages("e1071")` én gang.  ::: {.callout-note title="Fra videoene – dette skal du kunne fra før"} - Vi kan få en buet grense ved å utvide prediktorene med for eksempel $x_1^2$, $x_2^2$ og $x_1x_2$. - Klassifikatoren kan skrives med indre produkter mellom observasjoner, og en kjerne erstatter det indre produktet. - Radialkjernen har en parameter $\gamma$ som styrer hvor lokal modellen er. - ROC-kurver og AUC, «én mot alle» og «én mot én», og hengseltapet. I dag skal vi teste påstandene i videoene på egne data. Gir en mer fleksibel modell bedre prediksjoner? Og hva skal vi med en SVM når vi allerede kan logistisk regresjon? ::: # Læringsmål Etter forelesningen skal du kunne vise hvordan nye variabler kan skape en buet (ikke-lineær) grense. Du skal kunne forklare idéen bak kjernetrikset uten å utlede optimeringsalgoritmen. Du skal kunne tolke radialkjernens $\gamma$ og `cost` og sammenligne modeller med holdt-ut testdata. Og du skal kunne forklare forskjellen mellom en SVM-skår, ROC/AUC og en kalibrert sannsynlighet. # Repetisjon: hvorfor er ikke en rett linje nok? Se for deg kunder med mellomstor aktivitet i sentrum av et diagram og kunder med både svært lav og svært høy aktivitet rundt dem. Ingen rett linje kan skille sentrum fra ringen. Endring av `cost` kan flytte en lineær grense, men ikke gjøre den buet.  ![FIGURE 9.8. Left: The observations fall into two classes, with a non-linear boundary between them. Right: The support vector classifier seeks a linear boundary, and consequently performs very poorly.](figures/9_8_p1.png){#fig-9-8 width=85%} # Utvidelse av prediktorene En løsning er å legge til transformasjoner: $x_1^2$, $x_2^2$ og $x_1x_2$. I det utvidede rommet kan en *lineær* grense være $$ f(x)=\beta_0+\beta_1x_1+\beta_2x_2+ \beta_3x_1^2+\beta_4x_2^2+\beta_5x_1x_2. $$ I det opprinnelige $(x_1,x_2)$-planet er $f(x)=0$ en *buet* grense. En ring kan for eksempel skilles ved et uttrykk av typen $x_1^2+x_2^2-r^2=0$. Dette kjenner dere fra økonometrien: en regresjon med kvadratledd er fortsatt lineær i parameterne.  ![FIGURE 9.9. Left: An SVM with a polynomial kernel of degree 3 is applied to the non-linear data from Figure 9.8, resulting in a far more appropriate decision rule. Right: An SVM with a radial kernel is applied. In this example, either kernel is capable of capturing the decision boundary.](figures/9_9_p1.png){#fig-9-9 width=85%} ::: {.callout-tip title="Stopp og tenk"} Med $p$ prediktorer og alle ledd opp til grad $d$ får vi $\binom{p+d}{d}-1$ variabler. Regn ut antallet for $p=2,\ d=2$ og for $p=50,\ d=3$. Hvorfor blir eksplisitt polynomutvidelse raskt upraktisk? ::: ::: {.callout-note collapse="true" title="Svar: Stopp og tenk"} **Med $p=2,\ d=2$:** $$ \binom{4}{2}-1 = 6-1 = 5. $$ De fem variablene er $x_1,\ x_2,\ x_1^2,\ x_2^2$ og $x_1x_2$, altså de samme som i ligningen over. «$-1$» trekker fra konstantleddet, som ikke regnes som en variabel. **Med $p=50,\ d=3$:** $$ \binom{53}{3}-1 = \frac{53\cdot 52\cdot 51}{3\cdot 2\cdot 1}-1 = 23\,426-1 = 23\,425. $$ Fordelt på grad: | Grad | Type ledd | Antall | |:--|:--|--:| | 1 | $x_j$ | 50 | | 2 | $x_j^2$ og $x_jx_k$ | $50+1\,225=1\,275$ | | 3 | $x_j^3$, $x_j^2x_k$ og $x_jx_kx_l$ | 22 100 | | | **Sum** | **23 425** | Fra 50 prediktorer går vi altså til over 23 000 variabler. **Hvorfor dette blir upraktisk:** *Antallet eksploderer.* Det vokser omtrent som $p^d/d!$, så hver ekstra grad ganger antallet med omtrent $p/d$. *Mange flere variabler enn observasjoner.* Med noen hundre eller tusen observasjoner og 23 425 variabler finnes det nesten alltid en grense som skiller treningsdataene perfekt. Det sier ingenting om prediksjonsevnen, og faren for overtilpasning er stor. *Regnebyrden.* Vi må lage, lagre og regne med en $n\times 23\,425$-matrise. *Sterk multikollinearitet.* Ledd som $x_j$, $x_j^2$ og $x_j^3$ er sterkt korrelerte. *Tolkningen forsvinner.* Ingen kan tolke 22 100 tredjegradsledd hver for seg. Fra økonometrien kjenner dere samme problem i en translog-funksjon med mange innsatsfaktorer, der antall andregradsledd vokser raskt. En Cobb–Douglas-funksjon med to innsatsfaktorer kan skrives: $$ y=A x^{\beta_x}z^{\beta_z}, $$ eller på logaritmisk form: $$ \ln y=\ln A+\beta_x\ln x+\beta_z\ln z. $$ **Translog-formen** utvider denne med kvadrerte ledd og et samspillsledd: $$ \ln y =\beta_0+\beta_x\ln x+\beta_z\ln z +\frac{1}{2}\beta_{xx}(\ln x)^2 +\beta_{xz}(\ln x)(\ln z) +\frac{1}{2}\beta_{zz}(\ln z)^2. $$ Med bare $x$ og $z$ får vi altså **tre andregradsledd**. Med $K$ innsatsfaktorer blir antallet $K(K+1)/2$; med ti innsatsfaktorer blir det 55. Cobb–Douglas er spesialtilfellet der alle koeffisientene til andregradsleddene er null. **Kjernetrikset er løsningen.** Polynomkjernen $(1+\langle x,z\rangle)^3$ krever bare ett indre produkt med 50 ledd, opphøyd i tredje. Den gir likevel et indre produkt i det utvidede rommet med alle de 23 425 leddene, med bestemte vekter på hvert ledd. Vi får fleksibiliteten uten å lage variablene. Radialkjernen går enda lenger: den svarer til et uendelig-dimensjonalt rom, som det er umulig å lage eksplisitt. ::: # Kjernetrikset: sammenlign par av observasjoner Den lineære støttevektorklassifikatoren kan skrives ved indre produkter mellom observasjoner: $$ f(x)=\beta_0+\sum_{i\in\mathcal S}\alpha_i\langle x,x_i\rangle, \qquad \langle x,x_i\rangle=\sum_{j=1}^{p}x_jx_{ij}. $$ $\mathcal S$ er mengden av støttevektorer; for alle andre observasjoner er $\hat\alpha_i=0$. Ved å bytte ut det indre produktet med en **kjernefunksjon** $K(x,x_i)$ får vi $$f(x)=\beta_0+\sum_{i\in\mathcal S}\alpha_i K(x,x_i).$$ Kjernen er et mål på likhet mellom to observasjoner som svarer til et indre produkt i et utvidet variabelrom. Vi slipper å lage alle de nye variablene eksplisitt. Polynomkjernen av grad $d$ er $$K_{\mathrm{poly}}(x,z)=(1+\langle x,z\rangle)^d.$$ Grensen blir buet i de opprinnelige variablene, men klassifikatoren er lineær i det utvidede rommet. ::: {.callout-note title="Sparsomhet i observasjonene, ikke i variablene"} Lasso setter mange *koeffisienter* lik null og velger dermed variabler. SVM setter mange *observasjonsvekter* $\alpha_i$ lik null og «velger» dermed observasjoner. En SVM bruker alle prediktorene, men bare støttevektorene. ::: # Radialkjerne: hvor lokalt påvirker et punkt? $$ K_{\mathrm{radial}}(x,z) =\exp\{-\gamma\lVert x-z\rVert^2\},\qquad \gamma>0. $$ Nære observasjoner får kjerneverdi nær 1, mens fjerne observasjoner får verdi nær 0. Høy $\gamma$ gir svært lokal påvirkning og kan gi en urolig grense. Lav $\gamma$ gir bredere påvirkning og glattere grense. Også `cost` påvirker fleksibiliteten, så de to må velges sammen. I `e1071` er standardverdien `gamma = 1/p`. | Parameter i `e1071` | Lav verdi | Høy verdi | |:--|:--|:--| | `gamma` for radialkjerne | Likhet avtar sakte med avstand: glatt grense | Likhet avtar raskt med avstand: urolig grense | | `cost` | Marginbrudd straffes lite | Marginbrudd straffes mye | Radialkjernen svarer til et indre produkt i et *uendelig*-dimensjonalt rom (figuren under til høyre). Hvorfor overtilpasser ikke modellen alltid? Svaret i video 9.3 er at de mest «urolige» retningene i dette rommet får svært liten vekt, og straffen på marginen virker som regularisering. Men som vi skal se, beskytter det ikke mot et dårlig valg av $\gamma$ og `cost`. ![FIGURE 9.9. Left: An SVM with a polynomial kernel of degree 3 is applied to the non-linear data from Figure 9.8, resulting in a far more appropriate decision rule. Right: An SVM with a radial kernel is applied. In this example, either kernel is capable of capturing the decision boundary.](figures/9_9_p1.png){#fig-9-9 width=85%}  # Kode: sirkeldata, lineær SVC og radial SVM Her er sentrum én klasse og ringen den andre. Dataene er simulert, slik at geometrien er synlig, og klassene overlapper litt. Konklusjonene gjelder dette eksemplet og kan ikke overføres ukritisk til andre datasett. ```{r} #| label: fig-sirkeldata #| fig-cap: "Et klassifikasjonsproblem med én klasse i sentrum og én rundt." if (!requireNamespace("e1071", quietly = TRUE)) { stop("Installer pakken med install.packages('e1071') før du gjengir dokumentet.") } library(e1071) set.seed(93) n2 <- 240 klasse <- rep(c("Sentrum", "Ring"), each = n2 / 2) vinkel <- runif(n2, 0, 2 * pi) radius <- c(runif(n2 / 2, 0, 1.2), runif(n2 / 2, 0.9, 2.1)) dat_ring <- data.frame( x1 = radius * cos(vinkel) + rnorm(n2, sd = 0.2), x2 = radius * sin(vinkel) + rnorm(n2, sd = 0.2), y = factor(klasse, levels = c("Sentrum", "Ring")) ) plot(dat_ring$x1, dat_ring$x2, col = ifelse(dat_ring$y == "Ring", "#cc583b", "#276ca6"), pch = 19, xlab = "x1", ylab = "x2", asp = 1) legend("topright", legend = levels(dat_ring$y), col = c("#276ca6", "#cc583b"), pch = 19, bty = "n") ``` Før vi tilpasser modellene, legger vi til side et testsett. Vi velger `cost` og `gamma` *kun* med kryssvalidering på treningsdata. ```{r} #| label: tune-ring set.seed(94) id_ring <- unlist(lapply(split(seq_len(nrow(dat_ring)), dat_ring$y), function(ii) sample(ii, size = round(0.7 * length(ii))))) train_ring <- dat_ring[id_ring, ] test_ring <- dat_ring[-id_ring, ] set.seed(95) cv_rett <- tune( svm, y ~ ., data = train_ring, kernel = "linear", ranges = list(cost = c(0.1, 1, 10)), tunecontrol = tune.control(cross = 5) ) set.seed(95) cv_radial <- tune( svm, y ~ ., data = train_ring, kernel = "radial", ranges = list(cost = c(0.01, 0.1, 1, 10, 100), gamma = c(0.05, 0.2, 1, 5)), tunecontrol = tune.control(cross = 5) ) cv_rett$best.parameters cv_radial$best.parameters ``` ```{r} #| label: cv-flate # De seks beste kombinasjonene, sortert etter CV-feil perf <- summary(cv_radial)$performances head(perf[order(perf$error), ], 6) ``` Vi bruker **kryssvalidering** (*cross-validation*, forkortet CV) til å velge `cost`. Med **CV-feil** mener vi den gjennomsnittlige andelen feilklassifiserte observasjoner i valideringsfoldene. Forkortelsen CV må ikke forveksles med variasjonskoeffisienten (*coefficient of variation*), som også ofte forkortes CV. **Diskuter:** Mange kombinasjoner av `cost` og `gamma` har nesten samme CV-feil, og forskjellene er små i forhold til `dispersion`. Hva betyr det for hvor mye vi skal stole på akkurat den «beste» kombinasjonen? ::: {.callout-note collapse="true" title="Svar: Diskuter"} **Vi skal ikke stole mye på akkurat den «beste» kombinasjonen.** I vår kjøring vinner `cost = 100` og `gamma = 0,2` med CV-feil 0,161. Rett bak ligger `cost = 0,1` og `gamma = 0,2` med 0,167, og deretter flere kombinasjoner mellom 0,179 og 0,191. `dispersion` ligger rundt 0,05–0,10, så standardfeilen til gjennomsnittet er omtrent $0{,}07/\sqrt{5}\approx 0{,}03$. Forskjellen mellom nummer én og nummer to er 0,006. Treningsdelen har 168 observasjoner, så 0,006 svarer til én feilklassifisert observasjon. **Flere ting å legge merke til:** *Toppen spenner over et enormt område.* `cost` varierer med en faktor 1000 (fra 0,1 til 100) blant de beste kombinasjonene. Feilflaten er altså en flat dal, ikke en skarp topp. Det betyr at mange modeller er omtrent like gode. Det betyr også at CV ikke kan fortelle oss hvilken som er best. *`cost` og `gamma` kan erstatte hverandre.* Både høy `cost` og høy `gamma` gjør modellen mer fleksibel. Ulike kombinasjoner kan derfor gi omtrent like fleksible grenser, og dermed omtrent samme feil. *Vinneren ligger i kanten av rutenettet.* `cost = 100` er den største verdien vi prøvde. Vanligvis er det et tegn på at rutenettet bør utvides. Men når flaten er så flat, betyr det lite her. *Vinneren er avhengig av tilfeldighet.* Med et annet frø blir foldene annerledes, og en annen kombinasjon kan vinne. *Den laveste CV-feilen er for optimistisk.* Når vi velger minimum av 20 usikre tall, plukker vi delvis den som tilfeldigvis var heldig. Det er en grunn til at vi trenger et separat testsett. Her er CV-treffet $1-0{,}161=0{,}839$, mens testnøyaktigheten ble 0,806. **Hva gjør vi da?** Én-standardfeil-regelen sier at vi skal velge den *glatteste* modellen med CV-feil innenfor omtrent 0,03 av den beste. For en radial SVM betyr det lav `cost` og lav `gamma`. Her er det `cost = 0,1` og `gamma = 0,2`, med CV-feil 0,167. Den gir en mer stabil grense, og vi taper praktisk talt ingenting i CV-feil. Det viktigste vi lærer av tabellen er ikke ett tall, men et område: lav `gamma` (0,2) fungerer godt for mange verdier av `cost`. ::: ```{r} #| label: fig-modeller-ring #| fig-cap: "Treningsdata og tilpassede grenser. Heltrukken linje er f(x) = 0, stiplede linjer er f(x) = ±1, ringer markerer støttevektorer." #| fig-width: 10 #| fig-height: 5 # Tegner beslutningsgrense og marginer ved å regne ut f(x) på et rutenett tegn_grense <- function(mod, data, main = "") { x1 <- seq(min(data$x1), max(data$x1), length.out = 150) x2 <- seq(min(data$x2), max(data$x2), length.out = 150) rutenett <- expand.grid(x1 = x1, x2 = x2) f <- attr(predict(mod, rutenett, decision.values = TRUE), "decision.values")[, 1] plot(data$x1, data$x2, col = ifelse(data$y == "Ring", "#cc583b", "#276ca6"), pch = 19, asp = 1, xlab = "x1", ylab = "x2", main = main) contour(x1, x2, matrix(f, 150), levels = 0, add = TRUE, lwd = 2, drawlabels = FALSE) contour(x1, x2, matrix(f, 150), levels = c(-1, 1), add = TRUE, lty = 2, drawlabels = FALSE) points(data[mod$index, c("x1", "x2")], cex = 1.6) } par(mfrow = c(1, 2)) tegn_grense(cv_rett$best.model, train_ring, main = "Lineær SVC") tegn_grense(cv_radial$best.model, train_ring, main = "Radial SVM (CV-valgt)") par(mfrow = c(1, 1)) ``` ## Hva skjer når vi skrur opp fleksibiliteten? Vi legger til en bevisst overtilpasset modell med `cost = 100` og `gamma = 50`, som i laben i boka. ```{r} #| label: overtilpasning mod_overtilp <- svm(y ~ ., data = train_ring, kernel = "radial", cost = 100, gamma = 50) modeller <- list("Lineær SVC" = cv_rett$best.model, "Radial SVM (CV-valgt)" = cv_radial$best.model, "Radial SVM (gamma 50)" = mod_overtilp) treff <- function(mod, data) mean(predict(mod, data) == data$y) data.frame( modell = names(modeller), stottevektorer = sapply(modeller, function(m) m$tot.nSV), treningsnoyaktighet = round(sapply(modeller, treff, data = train_ring), 3), testnoyaktighet = round(sapply(modeller, treff, data = test_ring), 3), row.names = NULL ) ``` ```{r} #| label: fig-overtilpasset #| fig-cap: "Radial SVM med cost = 100 og gamma = 50 på treningsdata." #| fig-width: 5 #| fig-height: 5 tegn_grense(mod_overtilp, train_ring, main = "Radial SVM (gamma 50)") ``` **Diskuter:** Hvorfor gir `gamma = 50` perfekt treff på trening, men dårligere treff på test? Hvorfor må vi la være å prøve stadig nye valg etter å ha sett testresultatet? ::: {.callout-note collapse="true" title="Svar: Diskuter"} **Hvorfor perfekt på trening, men dårligere på test?** Radialkjernen er $K(x,z)=\exp\{-\gamma\lVert x-z\rVert^2\}$. Med `gamma = 50` faller likheten svært raskt med avstanden, målt i standardiserte enheter: | Avstand $\lVert x-z\rVert$ | $K(x,z)$ med $\gamma=50$ | |:--|:--| | 0,1 | $e^{-0{,}5}\approx 0{,}61$ | | 0,2 | $e^{-2}\approx 0{,}14$ | | 0,3 | $e^{-4{,}5}\approx 0{,}01$ | Hver treningsobservasjon påvirker altså bare et lite område rett rundt seg selv. Sammen med `cost = 100`, der brudd er svært dyre, kan modellen tegne en egen liten «øy» rundt nesten hvert punkt. Det ser vi i figuren. Modellen husker treningsdataene i stedet for å lære mønsteret, omtrent som en nærmeste-nabo-regel med én nabo. Derfor blir treningstreffet 100 %. Et nytt testpunkt havner sjelden nøyaktig der en treningsobservasjon lå. Det havner ofte i en øy som bare skyldes støy i ett enkelt treningspunkt, eller i tomrommet mellom øyene. I tomrommet er alle kjerneverdier nær null, så prediksjonen bestemmes nesten bare av konstantleddet. Resultatet er 69 % treff på test, mot 81 % for den CV-valgte modellen. Det er overtilpasning: svært lav skjevhet, men svært høy varians. **Hva med antall støttevektorer?** Den overtilpassede modellen bruker 159 av 168 observasjoner som støttevektorer, mens den CV-valgte bruker 61. I forelesning 1 ga færre støttevektorer høyere varians, men der var kjernen lineær, og det var smal margin som ga få støttevektorer. Her trenger nesten hvert punkt sin egen øy, og da blir nesten alle punktene støttevektorer. Antall støttevektorer er altså ikke et enkelt mål på hvor fleksibel modellen er; vi må se det sammen med kjernen og `gamma`. **Hvorfor ikke prøve nye valg etter å ha sett testresultatet?** Testsettet skal gi et ærlig anslag på hvordan modellen gjør det på data den aldri har sett. Hvis vi justerer `cost`, `gamma` eller kjernen fordi testresultatet var skuffende, blir testsettet en del av modellvalget. Da er det i praksis bare enda en valideringsfold. Testsettet har 72 observasjoner, så én observasjon utgjør 1,4 prosentpoeng. Prøver vi mange varianter, vil noen tilfeldigvis passe godt til akkurat disse 72. Den beste testnøyaktigheten blir da for optimistisk, av samme grunn som den laveste CV-feilen er det. Dette er det samme problemet som spesifikasjonssøk i økonometrien. Hvis vi prøver mange modeller og rapporterer den med best resultat, er ikke standardfeil og $p$-verdier lenger til å stole på. **Riktig arbeidsflyt:** All prøving og feiling skjer på treningsdataene, med kryssvalidering eller et eget valideringssett. Testsettet brukes én gang, til slutt, og resultatet rapporteres uansett hva det viser. Trenger vi å endre modellen etter det, trenger vi i prinsippet nye testdata. ::: ## Kjernetrikset er ikke magi `e1071` lagrer støttevektorene (`SV`), vektene $\alpha_i$ (`coefs`) og konstantleddet (`rho` $=-\beta_0$). Da kan vi regne ut $f(x)=\beta_0+\sum_{i\in\mathcal S}\alpha_iK(x,x_i)$ for hånd og sammenligne med `predict()`. ```{r} #| label: kjerne-for-haand mod <- cv_radial$best.model # Skaler testdata med treningsskalaen, slik svm() gjør internt x_ny <- scale(as.matrix(test_ring[, c("x1", "x2")]), center = mod$x.scale$`scaled:center`, scale = mod$x.scale$`scaled:scale`) # Kvadrerte avstander mellom hvert testpunkt og hver støttevektor avstand2 <- outer(rowSums(x_ny^2), rowSums(mod$SV^2), "+") - 2 * x_ny %*% t(mod$SV) K <- exp(-mod$gamma * avstand2) # radialkjernen f_for_haand <- drop(K %*% mod$coefs) - mod$rho f_e1071 <- attr(predict(mod, test_ring, decision.values = TRUE), "decision.values") c(antall_stottevektorer = nrow(mod$SV), storste_avvik = max(abs(f_for_haand - f_e1071[, 1]))) ``` Prediksjonen for et nytt punkt er altså en vektet sum av hvor *likt* punktet er hver støttevektor. Observasjonene som ikke er støttevektorer, er ikke med i summen i det hele tatt. # Ulike mål svarer på ulike spørsmål ## Forvekslingsmatrisen og de fire utfallene En klassifikator med to klasser kan ta feil på to måter. For å holde orden på dem velger vi én klasse som **positiv**. I kredittvurdering er det vanlig å la **mislighold** være positiv klasse, fordi det er den hendelsen vi vil oppdage. «Positiv» betyr altså «den klassen vi leter etter», ikke at utfallet er godt. Hver observasjon havner i én av fire ruter i **forvekslingsmatrisen** (engelsk *confusion matrix*): | | **Predikert: mislighold** | **Predikert: ikke mislighold** | |:--|:--|:--| | **Faktisk: mislighold** | $TP$ – sann positiv | $FN$ – falsk negativ | | **Faktisk: ikke mislighold** | $FP$ – falsk positiv | $TN$ – sann negativ | Forkortelsene kommer fra engelsk, og de er bygget opp på samme måte: den første bokstaven sier om prediksjonen var **riktig** (*True*, T) eller **feil** (*False*, F), og den andre sier hva modellen **predikerte** (*Positive*, P, eller *Negative*, N). - **$TP$ (True Positive, sann positiv):** modellen sa mislighold, og kunden misligholdt. Riktig. - **$TN$ (True Negative, sann negativ):** modellen sa ikke mislighold, og kunden betalte. Riktig. - **$FP$ (False Positive, falsk positiv):** modellen sa mislighold, men kunden ville ha betalt. Banken avviser en god kunde. Kalles også *falsk alarm* eller type I-feil. - **$FN$ (False Negative, falsk negativ):** modellen sa ikke mislighold, men kunden misligholdt. Banken låner ut til en kunde som ikke betaler. Kalles også *oversett tilfelle* eller type II-feil. **Eksempel fra forelesning 1.** Den lineære SVC-en ga denne matrisen på de 30 testsøknadene: | | **Predikert: mislighold** | **Predikert: ikke mislighold** | **Sum** | |:--|:--|:--|:--| | **Faktisk: mislighold** | $TP=8$ | $FN=3$ | 11 | | **Faktisk: ikke mislighold** | $FP=2$ | $TN=17$ | 19 | ## Mål regnet ut fra matrisen Alle de vanlige målene er andeler regnet ut fra disse fire tallene. Poenget er at de deler på *ulike* totaler, og derfor svarer de på ulike spørsmål. | Mål | Andre navn | Formel | Spørsmål målet svarer på | Eksempel | |:--|:--|:--|:--|:--| | Nøyaktighet | *Accuracy* | $\dfrac{TP+TN}{TP+TN+FP+FN}$ | Hvor stor andel av alle ble riktig klassifisert? | $25/30=0{,}83$ | | Sensitivitet | $TPR$ (*True Positive Rate*), *recall*, treffrate | $\dfrac{TP}{TP+FN}$ | Av dem som faktisk misligholdt, hvor mange fanget modellen? | $8/11=0{,}73$ | | Spesifisitet | $TNR$ (*True Negative Rate*) | $\dfrac{TN}{TN+FP}$ | Av dem som faktisk betalte, hvor mange ble korrekt godkjent? | $17/19=0{,}89$ | | Falsk positiv-rate | $FPR$ (*False Positive Rate*) | $\dfrac{FP}{FP+TN}=1-\text{spesifisitet}$ | Av dem som faktisk betalte, hvor mange ble feilaktig avvist? | $2/19=0{,}11$ | | Presisjon | $PPV$ (*Positive Predictive Value*) | $\dfrac{TP}{TP+FP}$ | Av dem modellen flagget, hvor mange misligholdt faktisk? | $8/10=0{,}80$ | Sensitivitet og spesifisitet deler på det *faktiske* utfallet (radene i matrisen). Presisjon deler på det *predikerte* utfallet (kolonnen). Sensitivitet er det banken bryr seg om når den vil unngå tap. Presisjon er det banken bryr seg om når den lurer på hvor mange av de avviste som faktisk var dårlige kunder. ## Hvorfor nøyaktighet alene kan lure oss Anta at bare 5 % av kundene misligholder. En «modell» som alltid sier «ikke mislighold», får da 95 % nøyaktighet. Men sensitiviteten er 0: den oppdager ikke en eneste misligholder. Når klassene er ubalanserte, må vi derfor alltid se på sensitivitet og spesifisitet, ikke bare nøyaktighet. De to feiltypene koster dessuten svært forskjellig. En $FN$ kan koste banken hele lånebeløpet. En $FP$ koster renteinntektene fra en god kunde, og kanskje kunden. Hvilken balanse mellom dem som er best, er et økonomisk spørsmål, ikke et statistisk. ## Terskelen: én modell, mange klassifikasjonsregler En SVM gir en skår $f(x)$, og standardregelen er å si «mislighold» når $f(x)>0$. Men vi kan like gjerne bruke en annen terskel $c$ og si «mislighold» når $f(x)>c$: - **Lavere terskel:** flere kunder blir flagget. Sensitiviteten øker, men det gjør også antall falske positive, så spesifisiteten faller. - **Høyere terskel:** færre kunder blir flagget. Spesifisiteten øker, men flere misligholdere slipper gjennom. Hver terskel gir altså sin egen forvekslingsmatrise. Valg av terskel avhenger av beslutningen modellen skal støtte og av hva feilene koster. ## ROC-kurven **ROC** står for *Receiver Operating Characteristic*. Navnet kommer fra radarteknikk under andre verdenskrig, der operatørene måtte balansere mellom å oppdage fly og å slå falsk alarm. ROC-kurven tegner sensitiviteten ($TPR$) på den loddrette aksen mot falsk positiv-raten ($FPR$) på den vannrette, for *alle* mulige terskler $c$: - Med en svært høy terskel flagges ingen: $TPR=0$ og $FPR=0$, nederst til venstre. - Med en svært lav terskel flagges alle: $TPR=1$ og $FPR=1$, øverst til høyre. - Kurven mellom disse punktene viser hvilke kombinasjoner av treff og falske alarmer modellen kan gi. En perfekt modell går rett opp til øvre venstre hjørne: alle misligholdere oppdages før én eneste god kunde avvises. Diagonalen fra $(0,0)$ til $(1,1)$ svarer til å gjette tilfeldig. Jo nærmere kurven går øvre venstre hjørne, desto bedre skiller skåren klassene. ## AUC **AUC** står for *Area Under the Curve*, arealet under ROC-kurven. Det oppsummerer hele kurven i ett tall mellom 0 og 1. AUC har en nyttig tolkning: det er sannsynligheten for at en tilfeldig valgt misligholder får høyere skår enn en tilfeldig valgt kunde som betaler. - **AUC $\approx$ 0,5:** skåren rangerer ikke bedre enn tilfeldig, som diagonalen. - **AUC = 1:** perfekt rangering; alle misligholdere får høyere skår enn alle som betaler. - **AUC < 0,5:** modellen rangerer *motsatt* vei, ofte et tegn på at fortegnet til skåren er snudd. I kredittvurdering rapporteres ofte **Gini-koeffisienten**, som bare er en omskalering: $\text{Gini}=2\cdot\text{AUC}-1$. To ting AUC *ikke* sier: AUC måler bare **rangering**, ikke om skåren kan tolkes som en sannsynlighet. Og AUC velger ingen terskel for oss; den sier hvor godt modellen *kan* skille klassene, ikke hvor godt en bestemt klassifikasjonsregel fungerer. Vi lager ROC og AUC selv, slik at det er tydelig hva som beregnes. SVM-skåren er beslutningsverdien $f(x)$. `e1071` setter fortegnet etter hvilken klasse som dukker opp først i dataene, så vi snur skåren slik at høy verdi alltid betyr «Ring». ```{r} #| label: roc-funksjoner skaar <- function(mod, data, positiv = "Ring") { f <- attr(predict(mod, data, decision.values = TRUE), "decision.values") forste_klasse <- strsplit(colnames(f), "/")[[1]][1] if (forste_klasse == positiv) f[, 1] else -f[, 1] } roc_punkter <- function(s, y, positiv = "Ring") { terskler <- sort(unique(c(Inf, s)), decreasing = TRUE) data.frame( fpr = sapply(terskler, function(t) mean(s[y != positiv] >= t)), tpr = sapply(terskler, function(t) mean(s[y == positiv] >= t)) ) } auc <- function(s, y, positiv = "Ring") { s_pos <- s[y == positiv] s_neg <- s[y != positiv] mean(outer(s_pos, s_neg, ">") + 0.5 * outer(s_pos, s_neg, "==")) } ``` ```{r} #| label: fig-roc #| fig-cap: "ROC-kurver på treningsdata og testdata. Jf. video 9.4." #| fig-width: 10 #| fig-height: 5 farger <- c("grey40", "#276ca6", "#cc583b") par(mfrow = c(1, 2)) for (del in c("Treningsdata", "Testdata")) { d <- if (del == "Treningsdata") train_ring else test_ring plot(NULL, xlim = c(0, 1), ylim = c(0, 1), asp = 1, main = del, xlab = "Andel falske positive (FPR)", ylab = "Sensitivitet (TPR)") abline(0, 1, lty = 3) for (k in seq_along(modeller)) { lines(roc_punkter(skaar(modeller[[k]], d), d$y), col = farger[k], lwd = 2) } legend("bottomright", legend = names(modeller), col = farger, lwd = 2, bty = "n", cex = 0.8) } par(mfrow = c(1, 1)) data.frame( modell = names(modeller), AUC_trening = round(sapply(modeller, function(m) auc(skaar(m, train_ring), train_ring$y)), 3), AUC_test = round(sapply(modeller, function(m) auc(skaar(m, test_ring), test_ring$y)), 3), row.names = NULL ) ``` Dette er samme mønster som i hjertedataene i video 9.4: den mest fleksible modellen ser best ut på trening og dårligst ut på test. En ROC-kurve på treningsdata er ikke et troverdig mål for framtidig ytelse. # SVM og logistisk regresjon En lineær SVC kan skrives som «tap + straff» med **hengseltap**: $$ \min_{\beta_0,\boldsymbol\beta} \sum_{i=1}^n\max\{0,1-y_i f(x_i)\} +\lambda\lVert\boldsymbol\beta\rVert^2. $$ Stor $\lambda$ svarer til stor $C_{\text{bok}}$ og liten `cost`. Når $y_i f(x_i)\geq1$, er tapet null: slike observasjoner ligger på riktig side av marginen og påvirker ikke løsningen. Logistisk regresjon bruker et glatt logaritmisk tap, $\log(1+e^{-y_if(x_i)})$, som aldri blir helt null. Knekkpunktet i hengseltapet er grunnen til at SVM har støttevektorer. ```{r} #| label: fig-tapsfunksjoner #| fig-cap: "Hengseltap og logistisk tap som funksjon av y·f(x). Jf. figur 9.12 i boka." #| fig-height: 4 z <- seq(-4, 3, length.out = 400) plot(z, pmax(0, 1 - z), type = "l", lwd = 2, col = "#cc583b", xlab = expression(y[i] * f(x[i])), ylab = "Tap") lines(z, log(1 + exp(-z)), lwd = 2, col = "#276ca6") abline(v = 1, lty = 3) legend("topright", legend = c("Hengseltap (SVM)", "Logistisk tap"), col = c("#cc583b", "#276ca6"), lwd = 2, bty = "n") ``` Hvis logistisk regresjon får de *riktige* variablene, kan den gjøre jobben like godt. Vi gir den kvadratleddene fra avsnittet om utvidelse av prediktorene: ```{r} #| label: logit-ring logit_kv <- glm(y ~ x1 + x2 + I(x1^2) + I(x2^2) + I(x1 * x2), data = train_ring, family = binomial) p_test <- predict(logit_kv, newdata = test_ring, type = "response") data.frame( modell = c("Logit med kvadratledd", "Radial SVM (CV-valgt)"), testnoyaktighet = round(c(mean(ifelse(p_test > 0.5, "Ring", "Sentrum") == test_ring$y), treff(cv_radial$best.model, test_ring)), 3), AUC_test = round(c(auc(p_test, test_ring$y), auc(skaar(cv_radial$best.model, test_ring), test_ring$y)), 3) ) ``` Her visste vi hvilken transformasjon som trengtes, fordi vi selv simulerte en ring. Kjernen er nyttig når vi *ikke* vet hvilke transformasjoner som trengs. | Egenskap | SVC/SVM | Logistisk regresjon | |:--|:--|:--| | Typisk output | Klasse og beslutningsskår | Modellert sannsynlighet og klasse ved valgt terskel | | Fleksibel grense | Kjerner, for eksempel radial | Krever transformasjoner du må velge selv | | Tolkning av enkeltkoeffisienter | Vanskelig, særlig med kjerner | Direkte i lineær modell | | Sannsynlighet | Nei; `probability = TRUE` gir en etterjustert (Platt-)sannsynlighet som må kontrolleres | Ja, men kalibreringen må fortsatt kontrolleres | | Variabelutvalg | Nei, bruker alle prediktorer | Ja, med lasso-straff | Video 9.4 gir en tommelfingerregel. Når klassene nesten kan skilles, gjør SVM det ofte bedre enn logistisk regresjon; dere kjenner problemet fra økonometrien, der ML-estimatoren for logit ikke finnes ved perfekt separasjon. Når klassene overlapper mye, gjør regularisert logistisk regresjon det omtrent like godt. Når grensen er ikke-lineær og vi ikke vet formen, er kjerne-SVM et effektivt valg. Skårverdien fra en SVM er **ikke** automatisk en misligholdssannsynlighet. Det er særlig viktig når beslutningen trenger et sannsynlighetsanslag, for eksempel for å beregne forventet tap. ::: {.callout-note title="Fra video 9.4: flere enn to klasser"} Ved $K$ klasser kan vi lage $K$ «én mot resten»-modeller eller $K(K-1)/2$ «én mot én»-modeller. `e1071::svm()` bruker «én mot én» automatisk når `y` har flere enn to nivåer. Laben i boka viser dette, og bruker også genuttrykksdata med $p\gg n$, der en lineær kjerne er nok. ::: # Vurder påstanden ::: {.callout-caution title="En KI-assistent skrev dette – hva er galt?"} «Radial SVM-en har AUC på trening nær 1, og beslutningsverdien for kunde A er 2,3. Det betyr at modellen er nesten perfekt, og at kunde A med svært høy sannsynlighet tilhører den positive klassen.» ::: Finn minst to feil. Hva måtte du gjort for å kunne si noe om sannsynligheten for kunde A? ::: {.callout-note collapse="true" title="Svar: Hva er galt?"} **Feil 1: AUC på *trening* sier ikke at modellen er god.** Treningsdataene er de samme observasjonene modellen er tilpasset til. I vårt eksempel hadde modellen med `gamma = 50` AUC på trening lik 1,000, men bare 0,674 på test. Den var altså den *dårligste* av de radiale modellene på nye data. For å si noe om hvor god modellen er, må AUC beregnes på testdata eller med kryssvalidering. **Feil 2: En beslutningsverdi er ikke en sannsynlighet.** Verdien 2,3 er $f(x)$, en skår som sier hvilken side av grensen kunden ligger på og hvor langt unna. I formuleringen med `cost` ligger marginene ved $f(x)=\pm 1$, så 2,3 betyr at kunde A ligger godt utenfor marginen. Men skalaen er vilkårlig. Den avhenger av `cost`, `gamma` og hvordan prediktorene er skalert. Skåren er ikke begrenset til intervallet $[0,1]$, og den samme kunden kan få helt ulik skår i to modeller som klassifiserer likt. Det finnes ingen regel som oversetter 2,3 til «svært høy sannsynlighet». **Feil 3: Positivt fortegn betyr ikke nødvendigvis positiv klasse.** `e1071` setter fortegnet etter hvilken klasse som dukker opp først i dataene, ikke etter hva *vi* har kalt positiv. Derfor måtte vi snu skåren i funksjonen `skaar()`. Uten å sjekke `colnames()` på beslutningsverdiene vet vi ikke engang hvilken klasse 2,3 peker mot. **Feil 4: AUC sier noe om rangering i en gruppe, ikke om én kunde.** AUC er sannsynligheten for at en tilfeldig positiv får høyere skår enn en tilfeldig negativ. Selv AUC = 1 på testdata betyr bare at rekkefølgen er riktig. Det sier ingenting om hvor sannsynlig det er at nettopp kunde A misligholder. Og «nesten perfekt rangering» betyr ikke nesten perfekt klassifikasjon med den terskelen vi faktisk bruker. **Hva måtte vi gjort for å si noe om sannsynligheten for kunde A?** *1. Kalibrere skåren på data modellen ikke er tilpasset til.* Den vanligste metoden er **Platt-skalering**: en logistisk regresjon der utfallet $y$ forklares av skåren $f(x)$: $$ \hat P(y=\text{positiv}\mid x)=\frac{1}{1+\exp\{-(a+b\,f(x))\}}. $$ Parameterne $a$ og $b$ må estimeres på valideringsdata eller med kryssvalidering, ikke på de samme dataene som SVM-en ble tilpasset til. I `e1071` gjør `probability = TRUE` dette med intern kryssvalidering: ```r mod_p <- svm(y ~ ., data = train_ring, kernel = "radial", cost = 0.1, gamma = 0.2, probability = TRUE) p <- attr(predict(mod_p, test_ring, probability = TRUE), "probabilities") head(p) # én kolonne per klasse, med klassenavn ``` *2. Kontrollere kalibreringen på testdata.* Grupper kundene etter predikert sannsynlighet, for eksempel 0–10 %, 10–20 % og så videre. Sammenlign så med den faktiske andelen mislighold i hver gruppe. Blant kunder med predikert sannsynlighet rundt 30 % bør omtrent 30 % faktisk misligholde. *3. Sjekke at grunnraten stemmer.* Hvis andelen mislighold i treningsdataene er en annen enn i kundemassen, for eksempel fordi utvalget er balansert, blir sannsynlighetene feil nivå. Da må de justeres til den faktiske grunnraten. Det samme problemet kjenner dere fra logit på et utvalg som er stratifisert etter utfallet. *Alternativt:* Bruk en modell som er laget for å gi sannsynligheter, som logistisk regresjon, og kontroller kalibreringen der også. Det er nettopp sannsynligheter banken trenger for å regne ut forventet tap. ::: # Praktisk sjekkliste og avslutning 1. Definer klasse og formål: skal modellen rangere, klassifisere eller gi en sannsynlighet? 2. Del data før tuning; bruk bare treningsdata i kryssvalidering og skalering. 3. Start med en lineær SVC eller en logistisk regresjon. Prøv radial SVM hvis mønsteret tilsier en buet grense. 4. Velg `cost` og eventuelt `gamma` med kryssvalidering, og se på usikkerheten i CV-feilen. 5. Sammenlign modellene én gang på holdt-ut testdata. 6. Rapporter forvekslingsmatrise og relevante mål, ikke bare treningsnøyaktighet. 7. Sjekk klasseubalanse, datalekkasjer og om skårene faktisk kan brukes til beslutningsformålet. **Avsluttende spørsmål:** En bank får samme AUC fra logistisk regresjon og radial SVM. Banken må også beregne forventet tap per kunde. Hvilken tilleggsinformasjon trenger den før den kan bruke noen av modellene til dette formålet? ::: {.callout-note collapse="true" title="Svar: Avsluttende spørsmål"} **Utgangspunkt: forventet tap har tre deler.** I bank og i kapitalkravsregelverket (Basel) skrives forventet tap for en kunde som $$ EL = PD\times LGD\times EAD, $$ der - **$PD$** (*Probability of Default*) er sannsynligheten for at kunden misligholder innen en gitt periode, typisk ett år, - **$LGD$** (*Loss Given Default*) er andelen av beløpet banken taper *hvis* kunden misligholder, etter at sikkerhet er realisert, - **$EAD$** (*Exposure at Default*) er hvor mye kunden skylder på misligholdstidspunktet. Begge modellene våre handler bare om den første faktoren. Og lik AUC sier ikke engang at de gir en brukbar $PD$. **1. En kalibrert sannsynlighet, ikke bare en god rangering.** Lik AUC betyr at modellene *rangerer* kundene omtrent like godt. Men $EL$ krever at $PD$ har riktig *nivå*: blant kunder med $PD=0{,}04$ skal omtrent 4 % faktisk misligholde. - *Radial SVM* gir bare en skår $f(x)$. Den må først gjøres om til en sannsynlighet, for eksempel med Platt-skalering på data modellen ikke er tilpasset til. - *Logistisk regresjon* gir en sannsynlighet direkte, men den kan også være feilkalibrert, for eksempel hvis modellen er feilspesifisert eller regularisert. For begge trenger banken dokumentasjon på kalibreringen, med en kalibreringsplott eller tabell på testdata. **2. Riktig grunnrate og tidshorisont.** Hvis andelen mislighold i treningsdataene avviker fra andelen i kundemassen, for eksempel fordi utvalget er balansert eller bare inneholder innvilgede lån, blir sannsynlighetsnivået feil. Det må være klart hva $PD$ gjelder for: mislighold innen 12 måneder, innen lånets løpetid, eller noe annet. **3. Stabilitet over tid.** En modell estimert i gode tider kan undervurdere $PD$ i en nedgangskonjunktur. Banken bør teste modellen på data fra en *senere* periode enn treningsdataene (*out-of-time*-validering), ikke bare på et tilfeldig testsett. **4. Data om $LGD$ og $EAD$.** Dette er egne størrelser som krever egne data og ofte egne modeller: sikkerhet, pantets verdi, nedbetalingsplan og utnyttelse av kredittrammer. Ingen av klassifikasjonsmodellene sier noe om dette. **5. Krav til forklaring.** Banken må kunne begrunne beslutninger overfor kunder og tilsynsmyndigheter. En logistisk regresjon har koeffisienter som kan tolkes og dokumenteres. En radial SVM er langt vanskeligere å forklare. **Konklusjon:** Med lik AUC og et mål om å beregne forventet tap har logistisk regresjon et klart fortrinn: den gir sannsynligheter direkte og er enklere å forklare. SVM-en kan brukes, men bare etter et ekstra kalibreringssteg som må valideres. Uansett modell trenger banken kalibrert $PD$, riktig grunnrate og tidshorisont, validering over tid, og egne anslag på $LGD$ og $EAD$. ::: # Kilder og kobling til videoene {.unnumbered} - *An Introduction to Statistical Learning*, 2. utgave: §9.3 SVM og kjerner; §9.4 flerklasse; §9.5 sammenheng med logistisk regresjon; §9.6.2–9.6.5 lab. - Video 9.3 «Feature Expansion and the SVM»: utvidede variabler, indre produkter og kjerner. - Video 9.4 «Example and Comparison with Logistic Regression»: ROC, flerklasse og hengseltap. - R-koden bygger på kapittel 9-laben med `e1071`; ROC og AUC er skrevet i base R i stedet for med `ROCR`.

Avstand \(\lVert x-z\rVert\)	\(K(x,z)\) med \(\gamma=50\)
0,1	\(e^{-0{,}5}\approx 0{,}61\)
0,2	\(e^{-2}\approx 0{,}14\)
0,3	\(e^{-4{,}5}\approx 0{,}01\)

Grad	Type ledd	Antall
1	\(x_j\)	50
2	\(x_j^2\) og \(x_jx_k\)	\(50+1\,225=1\,275\)
3	\(x_j^3\), \(x_j^2x_k\) og \(x_jx_kx_l\)	22 100
	Sum	23 425

	Predikert: mislighold	Predikert: ikke mislighold
Faktisk: mislighold	\(TP\) – sann positiv	\(FN\) – falsk negativ
Faktisk: ikke mislighold	\(FP\) – falsk positiv	\(TN\) – sann negativ

	Predikert: mislighold	Predikert: ikke mislighold	Sum
Faktisk: mislighold	\(TP=8\)	\(FN=3\)	11
Faktisk: ikke mislighold	\(FP=2\)	\(TN=17\)	19

Mål	Andre navn	Formel	Spørsmål målet svarer på	Eksempel
Nøyaktighet	Accuracy	\(\dfrac{TP+TN}{TP+TN+FP+FN}\)	Hvor stor andel av alle ble riktig klassifisert?	\(25/30=0{,}83\)
Sensitivitet	\(TPR\) (True Positive Rate), recall, treffrate	\(\dfrac{TP}{TP+FN}\)	Av dem som faktisk misligholdt, hvor mange fanget modellen?	\(8/11=0{,}73\)
Spesifisitet	\(TNR\) (True Negative Rate)	\(\dfrac{TN}{TN+FP}\)	Av dem som faktisk betalte, hvor mange ble korrekt godkjent?	\(17/19=0{,}89\)
Falsk positiv-rate	\(FPR\) (False Positive Rate)	\(\dfrac{FP}{FP+TN}=1-\text{spesifisitet}\)	Av dem som faktisk betalte, hvor mange ble feilaktig avvist?	\(2/19=0{,}11\)
Presisjon	\(PPV\) (Positive Predictive Value)	\(\dfrac{TP}{TP+FP}\)	Av dem modellen flagget, hvor mange misligholdt faktisk?	\(8/10=0{,}80\)