Naturlig språkbehandling

En språkmodell (language model) gir hver ordsekvens en sannsynlighet. Den kan avgjøre at «trikken går i dag» er mer sannsynlig enn «dag i går trikken», og den kan foreslå neste ord. Modellen lærer av et korpus (corpus), en samling tekst.

Den enkleste modellen er en sekk med ord (bag of words), som bare teller hvilke ord som forekommer. Den ser ingen forskjell på «Kari ringer Ola» og «Ola ringer Kari». Til å sortere tekst etter emne holder det ofte, men ikke til å forutsi neste ord.

Kjederegelen fra sannsynlighetsregningen skriver sannsynligheten for en setning som et produkt der hvert ord er betinget av alle ordene foran. Så lange historier går nesten aldri igjen i et korpus, så de kan ikke telles. Markov-antagelsen (Markov assumption) kutter historien: neste ord avhenger bare av de $n-1$ siste ordene. Det gir en n-gram-modell (n-gram model) og ƒkjederegelen med n-gram-tilnærming:

For en bigrammodell ($n=2$) estimeres hvert ledd med tellinger, ƒbigramsannsynlighet fra tellinger:

Dette er maksimum-likelihood-estimatet (MLE). Vanligvis får hver setning et startsymbol <s> foran og et sluttsymbol </s> bak. Da blir også første ord betinget på <s>, og modellen må forutsi at setningen slutter. Nevneren $c(w_{i-1})$ er antall ganger $w_{i-1}$ står foran et annet token, </s> medregnet.

Korpuset i figuren har fire setninger om vær og trikk i en tenkt by. Spørresetningen står ikke i korpuset, men alle ordparene i den gjør det.

Spør du modellen fra figuren om «bussen står når det regner», blir svaret 0. Bigrammet «bussen står» finnes ikke i korpuset, og ett null-ledd gjør hele produktet null. Et korpus er alltid for lite: de fleste ordpar som er helt greie, er aldri sett. Løsningen er glatting (smoothing): flytt litt sannsynlighet fra det som er sett, til det som ikke er sett.

Den enkleste metoden er add-one-glatting (add-one smoothing, Laplace smoothing): legg 1 til hver bigramtelling. For at sannsynlighetene for alle mulige neste ord fortsatt skal summere til 1, må nevneren øke med vokabularstørrelsen $V$, ƒadd-one-glatting:

Med <s> og </s> regnes </s> med i $V$, siden modellen kan forutsi den, mens <s> ikke gjør det. Add-k-glatting legger til $k$ i stedet for 1 og $kV$ i nevneren.

Add-one tar altså for mye fra det som er sett. Med lineær interpolasjon (linear interpolation smoothing) blandes i stedet modeller av ulik orden, ƒlineær interpolasjon:

Vektene summerer til 1 og velges slik at modellen passer best på tekst den ikke er trent på. Er bigrammet usett, holder unigramleddet $P(w_i)$ sannsynligheten over null, så lenge ordet finnes i korpuset. I en bigrammodell faller trigramleddet bort.

Figuren bruker korpuset fra forrige steg og spør om setningen med det usette bigrammet.

Hvilken modell er best? Vi måler på en testtekst modellen ikke er trent på, og målet er perpleksitet (perplexity): den inverse sannsynligheten til testteksten, normalisert per token, ƒperpleksitet:

Gir en modell en testsetning med to ord og </s> sannsynligheten $\frac{1}{27}$, er perpleksiteten $27^{1/3}=3$: modellen er like usikker som om den valgte blant tre like sannsynlige ord i hvert steg. Lavere er bedre. Gir modellen ett token sannsynlighet 0, blir perpleksiteten uendelig, enda et argument for glatting.

from collections import Counter

k = 1.0  # @param 0.0..2.0 0.1
lam1 = 0.0  # @param 0.0..1.0 0.1

korpus = ["tåka ligger over byen", "tåka letter i kveld",
          "sola skinner over fjorden", "sola ligger lavt i kveld"]
test = "sola letter i kveld"

uni, bi, ctx = Counter(), Counter(), Counter()
for s in korpus:
    t = ["<s>"] + s.split() + ["</s>"]
    uni.update(t[1:])
    for a, b in zip(t, t[1:]):
        bi[a, b] += 1
        ctx[a] += 1
V, N = len(uni), sum(uni.values())


def p(w, forrige):
    p_bi = (bi[forrige, w] + k) / (ctx[forrige] + k * V) if ctx[forrige] + k > 0 else 0.0
    return lam1 * uni[w] / N + (1 - lam1) * p_bi


t = ["<s>"] + test.split() + ["</s>"]
p_setning = 1.0
for a, b in zip(t, t[1:]):
    p_setning *= p(b, a)
print(f"P(letter | sola): {p('letter', 'sola'):.4f}")
print(f"P(setning): {p_setning:.6f}")
if p_setning > 0:
    print(f"Perpleksitet: {p_setning ** (-1 / (len(t) - 1)):.2f}")
else:
    print("Perpleksitet: uendelig (en sannsynlighet er 0)")

En n-gram-modell ser bare noen få ord bakover. I «trikken som stod ved torget hele formiddagen, går nå» hører «går» sammen med «trikken», sju ord tidligere. En grammatikk beskriver slike strukturer direkte.

Et første steg er ordklassemerking (part-of-speech tagging): hvert ord får en ordklasse som substantiv, verb eller preposisjon. Samme ord kan høre til ulike klasser. «Går» er et verb i «trikken går», men en del av et tidsuttrykk i «i går». En merker bruker konteksten til å velge, ofte med en skjult Markov-modell eller en klassifikator.

En kontekstfri grammatikk (context-free grammar) har regler som $\text{VP}\to \text{V}\text{NP}$: en verbfrase kan bestå av et verb og en nominalfrase. Symbolene på venstre side kalles ikke-terminaler, og ordene er terminaler. En probabilistisk kontekstfri grammatikk (probabilistic context-free grammar) gir hver regel en sannsynlighet, og reglene med samme venstreside summerer til 1. Resten av kapitlet bruker denne grammatikken:

S  → NP VP     1,0      NP → Ola            0,3
VP → V NP      0,6      NP → Kari           0,3
VP → VP PP     0,4      NP → kamera         0,2
NP → NP PP     0,2      V  → filmer         1,0
PP → P NP      1,0      P  → med            1,0

Et parsetre (parse tree) viser hvordan setningen bygges av reglene, og sannsynligheten til treet er produktet av reglene det bruker, ƒsannsynligheten til et parsetre:

Setningen «Ola filmer Kari med kamera» har to trær. I treet under er det Ola som bruker kameraet.

Produktet for treet er $1,0\cdot 0,3\cdot 0,4\cdot 0,6\cdot 1,0\cdot 0,3\cdot 1,0\cdot 1,0\cdot 0,2=0,00432$.

Å parse er å finne treet, eller alle trærne, for en setning. Top-down-parsing starter i S og bruker regler til å ekspandere mot ordene. Bottom-up-parsing starter i ordene og slår sammen naboer til større ledd. Begge sløser: top-down prøver ekspansjoner som ikke passer ordene, og bottom-up bygger ledd som ikke passer inn i noen hel setning. Er setningen tvetydig, kan samme delstykke dessuten bli parset på nytt mange ganger.

Dynamisk programmering fjerner gjentakelsene ved å lagre resultatet for hvert delstykke én gang. CYK-algoritmen (CYK algorithm) krever at grammatikken står i Chomsky-normalform (Chomsky normal form, CNF), der hver regel er $A\to BC$ eller $A\to w$. Grammatikken fra forrige steg er allerede på denne formen. Cellen for ordene $i$ til $j$ holder alle ikke-terminaler som kan dekke akkurat de ordene:

1. 1.Lengde 1: skriv inn hver $A$ med en regel $A\to w$ for ordet.
2. 2.Lengde 2 til $n$: for hvert delepunkt $k$, legg inn $A$ når en regel $A\to BC$ har $B$ i cellen for ordene $i$ til $k$ og $C$ i cellen for ordene $k+1$ til $j$.
3. 3.Svar: setningen er grammatisk hvis S står i cellen for ordene 1 til $n$.

Med en PCFG lagrer cellen den høyeste sannsynligheten for hver ikke-terminal og en bakoverpeker til delepunktet som ga den, så det mest sannsynlige treet kan leses ut til slutt. ƒCYK-kompleksiteten er $O(n^{3}m)$ tid og $O(n^{2}m)$ minne for $n$ ord og $m$ ikke-terminaler: tabellen har omtrent $n^2/2$ celler, og hver celle prøver opptil $n$ delepunkter.

Tabellen viser CYK for setningen fra parsetreet. Rad $i$ og kolonne $j$ er cellen for ordene $i$ til $j$.

Tvetydigheten fra forrige steg ligger nå i én celle: VP-en for ordene 2–5 kan bygges på to måter.

En n-gram-modell behandler hvert ord som et symbol uten innhold. At «trikk» og «buss» ligner hverandre, vet den ikke, så det den lærer om det ene ordet, hjelper ikke for det andre. En ordvektor (word embedding) gir hvert ord en vektor med noen hundre tall, lært fra store tekstmengder slik at ord som brukes i like sammenhenger, havner nær hverandre. Vektorene fanger ofte også relasjoner: forskjellen mellom «Bergen» og «Vestland» ligner forskjellen mellom «Trondheim» og «Trøndelag».

Rekurrente nevrale nett (recurrent neural networks, RNN) leser setningen ord for ord og bærer med seg en skjult tilstand. I prinsippet husker de hele historien, men i praksis blekner informasjon over lange avstander, og ordene må behandles ett etter ett. To RNN-er, en koder og en dekoder, ble brukt til maskinoversettelse som sekvens-til-sekvens-modeller (sequence-to-sequence).

Med oppmerksomhet (attention) kan hver posisjon se direkte på alle andre posisjoner og hente informasjon fra de mest relevante. I selvoppmerksomhet lager hvert ord en spørring, en nøkkel og en verdi, samlet i matrisene $Q$, $K$ og $V$ (her er $V$ verdiene, ikke vokabularet), ƒskalert prikkprodukt-oppmerksomhet:

Hvert ord får en vektet sum av verdiene til alle ordene, med vekter som sier hvor godt spørringen passer hver nøkkel. En transformer (transformer) stabler lag med selvoppmerksomhet og små fremovernett. Uten rekurrens kan alle posisjoner regnes ut parallelt, og to ord er alltid bare ett steg fra hverandre.

Oppskriften bak dagens store språkmodeller er pretrening og finjustering (pretraining, fine-tuning). En transformer trenes først på enorme mengder umerket tekst til å forutsi neste ord eller et skjult ord. Deretter finjusteres modellen til en bestemt oppgave med lite merkede data, eller den styres med instruksjoner i teksten den får.