Bayes-klassifikasjon og Naive Bayes

En birøkter har sensorer i kubene og vil oppdage sverming før det skjer. Sverming betyr at dronningen og omtrent halvparten av biene forlater kuba for å finne et nytt bol. Vi har to klasser, $C\in \{\text{sverming},\text{normal}\}$, og én observasjon $x$: om summetonen er høy.

Tre størrelser bestemmer svaret:

• •Prioren $p(C)$ er hvor vanlig klassen er før vi ser på $x$. En gitt uke i sesongen forbereder 10 prosent av kubene sverming.
• •Likelihooden $p(x\mid C)$ er hvor sannsynlig observasjonen er hvis klassen er sann. 70 prosent av svermende kuber har høy summetone, mot 20 prosent av de normale.
• •Posterioren $p(C\mid x)$ er det vi egentlig vil vite: sannsynligheten for klassen gitt det vi så.

Bayes' regel knytter dem sammen, ƒBayes' regel for klassifikasjon:

Bayes-klassifikatoren velger klassen med størst posterior. Hvis sannsynlighetene er riktige, gir den færrest feilklassifiseringer av alle mulige regler.

Den vanligste feilen er å forveksle $p(x\mid C)$ og $p(C\mid x)$. At 70 prosent av de svermende kubene summer høyt, betyr ikke at 70 prosent av kubene som summer høyt, svermer. Normale kuber er ni ganger så mange, så selv 20 prosent av dem blir mange.

Nevneren i Bayes' regel er evidensen $p(x)$: den totale sannsynligheten for å observere $x$, summert over alle måtene det kan skje på, ƒevidens som sum over klassene:

To egenskaper er verdt å huske. For det første er $p(x)$ den samme for alle klassene, fordi summen allerede går over alle klassene. Å dele hver teller på samme positive tall endrer ikke hvilken som er størst, så for å velge klasse holder det å sammenligne $p(x\mid C)p(C)$:

For det andre er det nettopp $p(x)$ som får posteriorene til å summere til 1. Trenger du selve sannsynligheten, for eksempel fordi birøkteren vil ha varsel når $p(\text{sverming}\mid x)>0,2$, eller fordi feilene koster ulikt, må du normalisere.

Med flere klasser blir dette enda tydeligere. Legg til klassen «dronningløs», der kolonien har mistet dronningen. Den har prior $0,05$ og gir høy summetone i 80 prosent av tilfellene. Nå er det tre tellere å sammenligne, og $p(x)$ er summen av alle tre.

Birøkteren har flere sensorer: summetone, temperatur over 36 °C og om vekta faller. Med $d$ features trenger Bayes' regel $p(x_1,\dots ,x_d\mid C)$, sannsynligheten for hele kombinasjonen. Med $d$ binære features finnes $2^d$ kombinasjoner per klasse. Med 30 features er det over en milliard, og de fleste kombinasjonene finnes aldri i treningsdataene.

Naive Bayes løser dette med én antakelse, Naive Bayes-antakelsen: featurene er betinget uavhengige gitt klassen. Da faktoriserer likelihooden til et produkt, og hver feature trenger bare sin egen lille tabell, ƒNaive Bayes-beslutning:

Les antakelsen nøye. Den sier ikke at featurene er uavhengige av hverandre generelt. Høy summetone og høy temperatur henger sammen på tvers av kuber, nettopp fordi begge drives av sverming. Antakelsen sier at innenfor de svermende kubene, og innenfor de normale, forteller den ene featuren ingenting om den andre. Den sier heller ikke at featurene er uavhengige av klassen, for da ville de vært ubrukelige.

I praksis er antakelsen nesten alltid brutt, og vi bruker den likevel. Når to features er korrelert innen klassen, teller modellen den samme evidensen to ganger, og posteriorene blir for ekstreme. Klassifikatoren kan likevel treffe godt, fordi den bare trenger riktig rekkefølge mellom klassene, ikke riktige sannsynligheter.

En feature som er observert som usann, teller også: da brukes $1-p(x_j=1\mid C)$.

Å trene Naive Bayes er å telle. Prioren er andelen av treningseksemplene i klassen, $p(C)=n_C/n$. For en kategorisk feature er likelihooden andelen av klassens eksempler som har verdien: $p(x_j=v\mid C)=N_{j,v,C}/n_C$.

Problemet er nuller. Har en verdi aldri forekommet sammen med en klasse i treningsdataene, blir likelihooden 0, produktet blir 0, og klassen blir umulig uansett hvor sterkt resten av evidensen peker mot den. Med små datasett og mange verdier skjer det ofte.

Laplace-glatting legger til en liten pseudotelling $\alpha$, vanligvis 1, for hver mulige verdi, ƒLaplace-glattet estimat:

$K_j$ er antall mulige verdier for feature $j$, og nevneren får $\alpha K_j$ slik at sannsynlighetene over alle verdiene fortsatt summerer til 1. For ordmodeller i tekst er $K$ størrelsen på vokabularet og $n_C$ antall ordforekomster i klassen. Større $\alpha$ trekker estimatene mot den jevne fordelingen $1/K_j$, så $\alpha$ er en hyperparameter.

Et ferjeselskap vil forutsi innstillinger fra vind (svak, moderat, sterk) og sikt (god, dårlig). Ti dager gir disse tellingene:

• •Innstilt, 4 dager: vind sterk 3, moderat 1, svak 0. Sikt dårlig 3, god 1.
• •Ikke innstilt, 6 dager: vind svak 3, moderat 3, sterk 0. Sikt god 4, dårlig 2.

I tekstklassifisering kan et dokument ha hundrevis av ord, og hvert ord bidrar med en faktor kanskje mellom $0,001$ og $0,02$. Produktet av 400 slike faktorer er rundt $10^{-800}$. Det minste normale positive tallet en vanlig flyttallsvariabel (float64) kan holde, er omtrent $10^{-308}$, og subnormale tall strekker det bare ned mot $10^{-324}$. Alt mindre blir 0. Da får alle klassene score 0, sammenligningen blir meningsløs, og normaliseringen deler 0 på 0.

Løsningen er å regne med logaritmer. Logaritmen er voksende, så klassen med størst produkt har også størst log-produkt, og produktet blir en sum:

Summen av 400 tall rundt $-5$ er omtrent $-2000$, og det er helt uproblematisk. For å velge klasse holder det å sammenligne disse log-scorene.

Trenger du posteriorene, må du tilbake fra logaritmene uten å havne i samme felle, for $e^{-2000}$ er også 0. Trikset er å trekke fra den største log-scoren $m$ før du tar eksponentialen:

Faktoren $e^{-m}$ står i både teller og nevner og forkortes bort, så svaret er det samme, men nå er den største eksponentialen $e^0=1$. Dette er log-sum-exp-trikset, det samme som gjør softmax stabil i kapittel 4.

import numpy as np

rng = np.random.default_rng(5)
n_ord = 400  # @param 10..600 10
lik_a = rng.uniform(0.001, 0.02, n_ord)         # p(ord | A)
lik_b = lik_a * rng.uniform(0.8, 1.2, n_ord)    # p(ord | B), litt annerledes
prior = np.array([0.5, 0.5])

produkt = prior * np.array([np.prod(lik_a), np.prod(lik_b)])
print(f"rett produkt: {produkt}")

logscore = np.log(prior) + np.array([np.log(lik_a).sum(), np.log(lik_b).sum()])
vekter = np.exp(logscore - logscore.max())      # trekk fra maks før exp
print(f"log-score:    {np.round(logscore, 1)}")
print(f"posterior:    {np.round(vekter / vekter.sum(), 4)}")

Hva med kontinuerlige features, som en temperatur på $35,8$ °C? Telling virker ikke når nesten hver verdi er unik. Gaussisk Naive Bayes antar i stedet at hver feature er normalfordelt innen hver klasse, med egen middelverdi ${\mu }_{j,C}$ og varians ${\sigma }_{j,C}^2$. Begge estimeres fra treningsdataene i klassen, og likelihooden er tettheten, ƒGaussisk likelihood:

Dette er en tetthet, ikke en sannsynlighet, så den kan være større enn 1 når $\sigma$ er liten. Det er greit, siden bare forholdet mellom klassene betyr noe, og normaliseringen tar seg av resten. Kategoriske og kontinuerlige features kan blandes i samme produkt.

Naive Bayes er en generativ modell: den beskriver hvordan dataene ser ut innen hver klasse, $p(x\mid C)$, og hvor vanlig hver klasse er, $p(C)$. I prinsippet kan den lage nye, kunstige målinger. Logistisk regresjon er diskriminativ: den modellerer $p(C\mid x)$ direkte og lærer bare grensen mellom klassene.

• •Den generative modellen har få parametere og trenes ved telling og gjennomsnitt. Den klarer seg med lite data og kan hoppe over en manglende feature ved å droppe faktoren. Men den står og faller på antakelsene, og sannsynlighetene blir dårlig kalibrert når de brytes.
• •Den diskriminative modellen antar ingenting om fordelingen til $x$, kompenserer for korrelerte features gjennom vektene og vinner oftest når det finnes mye data. Til gjengjeld må den trenes iterativt.

Med binære features gir Naive Bayes faktisk log-odds som er lineær i $x$, samme form som logistisk regresjon. Forskjellen ligger i hvordan parameterne tilpasses.

import numpy as np
from sklearn.linear_model import LogisticRegression
from sklearn.naive_bayes import GaussianNB

rng = np.random.default_rng(11)
temp = np.concatenate([rng.normal(36.5, 0.5, 40), rng.normal(35.0, 1.0, 160)])
y = np.concatenate([np.ones(40), np.zeros(160)])      # 1 = sverming
kopi = 0  # @param 0..1
X = temp[:, None]
if kopi:   # legg til en nesten-kopi av temperaturen som feature nummer to
    X = np.column_stack([temp, temp + rng.normal(0, 0.05, 200)])

def gauss(x, mu, var):
    return np.exp(-(x - mu) ** 2 / (2 * var)) / np.sqrt(2 * np.pi * var)

x_ny = np.full(X.shape[1], 36.0)                      # ny måling: 36,0 °C
uskalert = [np.mean(y == c) * np.prod(gauss(x_ny, X[y == c].mean(0), X[y == c].var(0)))
            for c in [0, 1]]
print(f"{X.shape[1]} feature(r), P(sverming) for en måling på 36,0 °C:")
print(f"Naive Bayes for hånd: {uskalert[1] / sum(uskalert):.3f}")
print(f"GaussianNB:           {GaussianNB().fit(X, y).predict_proba([x_ny])[0, 1]:.3f}")
print(f"logistisk regresjon:  {LogisticRegression().fit(X, y).predict_proba([x_ny])[0, 1]:.3f}")