T-61.5020 Luonnollisten kielten tilastollinen käsittely
Vastaukset 8, ke 21.3.2007, 12:15-14:00 -- N-grammikielimallit
Versio 1.0

1.

Alla on erään henkilön ja tilaston estimaatit sille, miten todennäköistä on, että alla annetut sanat seuraavat sanoja ``tuntumaan jo'':

Taulukko: Ihminen vs tilasto, trigrammiestimaatit

sana	tilasto trig	ihminen trig	ihminen lause
ja	0.00	0.00	0.00
hyvältä	1.00	0.18	0.40
kumisaapas	0.00	0.00	0.00
keväältä	0.00	0.23	0.50
ilman	0.00	0.05	0.05
päihtyneeltä	0.00	0.20	0.00
turhalta	0.00	0.23	0.05
koirineen	0.00	0.00	0.00
öljyiseltä	0.00	0.11	0.00
Turku	0.00	0.00	0.00

Tarkemmalla tukimisilla huomataan, että taulukossa ihmisen antamat trigrammiestimaatit ovat jonkin verran pielessä ja tilastolliset pehmentämättömät trigrammiestimaatit aivan pielessä.

Tilastollisten estimaattien laskuun käytettiin n. 30 miljoonan sanan aineistoa. Tässä aineistossa ei yksikään annetuista taivutetuista trigrammeista esiintynyt kertaakaan. Trigrammit perusmuotoistamalla löydettiin 11 lausetta, joissa esiintyi ``tuntua jo hyvä''. Estimaatti kaipaa siis selvästi tasoittamista, eikä senkään jälkeen ole kovin luotettava.

Myös esimerkki-ihmisen antamaa estimaattia voi epäillä, aivan mahdollisille lauseille on annettu nollatodennäköisyys, esim. ``Kyllä alkaa tuntumaan jo kumisaapas jalassa'', lause joka voidaan tokaista vaikka pitkän vaelluksen päätteeksi. Toisaalta annetulla 2 desimaalin tarkkuudella estimaatit lienevät hyviä.

Kun testihenkilölle annettiin koko lause nähtäväksi, saatiin jo varsin laadukkaat estimaatit. Jotta tilastollisesti pystyttäisiin pääsemään samaan tulokseen, tarvitsisi mallin ymmärtää suomen kielen syntaksia (miten sanoja voidaan taivuttaa ja laittaa peräkkäin) sekä myös sanojen semanttista merkitystä (``helmikuu'' on lopputalvea, melkein kevättä).

2.

a)

Suurimman uskottavuuden estimaatit voidaan laskea kaavasta

$$P(w_i\vert w_{i-1},w_{i-2},\dots) = \frac {C(w_i,w_{i-1},w_{i-2},\dots)} {C(w_{i-1},w_{i-2},\dots)},$$

missä funktio $C$ kertoo opetusjoukossa nähtyjen näytteiden määrän.

Unigrammiestimaatissa unohdetaan riippuvuus kaikista edellisistä sanoista, bigrammiestimaatti riippuu vain edellisestä sanasta ja trigrammiestimaatissa käytetään historiana kahta edellistä sanaa.

Unigrammiestimaatit voidaan siis laskea

$$P(w_i)=\frac{C(w_i)}{C(0)},$$

missä $C(0)$ on opetusjoukon näytteiden lukumäärä. Estimaatit ovat siis samat kummallekin tehtävänannon historialle.

$$P(\textrm{'olla'}) = \frac 5 {98} = 0.051$$

$$P(\textrm{'leuto'}) = \frac 1 {98} = 0.001$$

$$P(\textrm{'gorilla'}) = \frac 0 {98} = 0.000$$

Bigrammiestimaatit saadaan ottamalla yksi sana historiasta käyttöön:

$$P(w_i \vert w_{i-1}) = \frac{C(w_i,w_{i-1})} {C(w_{i-1})}$$

$$P(\textrm{'olla'} \vert \textrm{'olla'}) = \frac{0}{5}=0.000$$

$$P(\textrm{'leuto'} \vert \textrm{'olla'}) = \frac{1}{5}=0.200$$

$$P(\textrm{'gorilla'} \vert \textrm{'olla'}) = \frac{0}{5}=0.000$$

$$P(\textrm{'olla'} \vert \textrm{'vaikuttaa'}) = \frac{0}{1}=0.000$$

$$P(\textrm{'leuto'} \vert \textrm{'vaikuttaa'}) = \frac{0}{1}=0.000$$

$$P(\textrm{'gorilla'} \vert \textrm{'vaikuttaa'}) = \frac{0}{1}=0.000$$

Huomataan, että tämän mallin mielestä mikään sanayhdistelmä, jota se ei ole nähnyt, ei ole mahdollinen.

b)

Laplacen estimaatissa aikaisemmin havaitsemattomille sanoille annetaan hieman todennäköisyyttä. Estimaatti vastaa prioria, että kaikki sanat ovat yhtä todennäköisiä. Käytännössä se lasketaan niin, että kuvitellaan että kaikkia sanoja on jo nähty kerran:

$$P(w_i\vert w_{i-1},w_{i-2},\dots) = \frac {C(w_i,w_{i-1},w_{i-2},\dots)+1} {C(w_{i-1},w_{i-2},\dots)+N},$$

missä $N$ on mallin sanaston koko.

Lasketaan siis estimaatit:

$$P(\textrm{'olla'}) = \frac {5+1} {98+64000} = 9.3\cdot10^{-5}$$

$$P(\textrm{'leuto'}) = \frac {1+1} {98+64000} = 3.1\cdot10^{-5}$$

$$P(\textrm{'gorilla'}) = \frac {0+1} {98+64000} = 1.6\cdot10^{-5}$$

Bigrammeille:

$$P(\textrm{'olla'} \vert \textrm{'olla'}) = \frac{1}{5+64000}=1.6\cdot10^{-5}$$

$$P(\textrm{'leuto'} \vert \textrm{'olla'}) = \frac{1+1}{5+64000}=3.1\cdot10^{-5}$$

$$P(\textrm{'gorilla'} \vert \textrm{'olla'}) = \frac{1}{5+64000}=1.6\cdot10^{-5}$$

$$P(\textrm{'olla'} \vert \textrm{'vaikuttaa'}) = \frac{1}{1+64000}=1.6\cdot10^{-5}$$

$$P(\textrm{'leuto'} \vert \textrm{'vaikuttaa'}) = \frac{1}{1+64000}=1.6\cdot10^{-5}$$

$$P(\textrm{'gorilla'} \vert \textrm{'vaikuttaa'}) = \frac{1}{1+64000}=1.6\cdot10^{-5}$$

Huomataan, että tässä priorioletus, että kaikki sanat ovat yhtä todennäköisiä ohjaa estimaatteja vahvasti, kaikki sanat ovat toisaan mallien mielestä lähes yhtä todennäköisiä.

c)

Lidstonen estimaatissa voidaan säätää sitä, kuinka paljon uskotaan siihen, että sanat ovat yhtä todennäköisiä. Siinä kuvitellaan, että sanat on jo nähty $\lambda$ kertaa ennen opetusaineistoa:

$$P(w_i\vert w_{i-1},w_{i-2},\dots) = \frac {C(w_i,w_{i-1},w_{i-2},\dots)+\lambda} {C(w_{i-1},w_{i-2},\dots)+\lambda N},$$

Valitaan tässä $\lambda=0.01$. Lasketaan estimaatit:

$$P(\textrm{'olla'}) = \frac {5+0.01} {98+0.01\cdot64000} = 6.8\cdot10^{-3}$$

$$P(\textrm{'leuto'}) = \frac {1+0.01} {738} = 1.4\cdot10^{-4}$$

$$P(\textrm{'gorilla'}) = \frac {0.01} {738} = 1.4\cdot10^{-5}$$

Bigrammeille:

$$P(\textrm{'olla'} \vert \textrm{'olla'}) = \frac{0.01}{645}=1.6\cdot10^{-5}$$

$$P(\textrm{'leuto'} \vert \textrm{'olla'}) = \frac{1+0.01}{645}=1.6\cdot10^{-3}$$

$$P(\textrm{'gorilla'} \vert \textrm{'olla'}) = \frac{0.01}{641}=1.6\cdot10^{-5}$$

$$P(\textrm{'olla'} \vert \textrm{'vaikuttaa'}) = \frac{0.01}{641}=1.6\cdot10^{-5}$$

$$P(\textrm{'leuto'} \vert \textrm{'vaikuttaa'}) = \frac{0.01}{641}=1.6\cdot10^{-5}$$

$$P(\textrm{'gorilla'} \vert \textrm{'vaikuttaa'}) = \frac{0.01}{641}=1.6\cdot10^{-5}$$

Tässä tapauksessa opetusdata ohjaa selkeämmin estimaatteja. Sopiva $\lambda$ voidaan valita laittamalla opetusjoukosta pieni osa sivuun ja testaamalla tällä sivuun laitetulla tekstillä, mikä $\lambda$ toimii parhaiten.

3.

Absoluuttisessa vähennyksessä havaituista n-grammien esiintymien määrästä vähennetään vakioarvo (tässä siis $D = 0.5$). Vähennys voidaan luonnollisesti tehdä vain silloin esiintymiä oli vähintään yksi. Kun vähennys tehdään bigrammijakauman estimaatteihin, jäljelle jää todennäköisyysmassaa, joka voidaan käyttää interpoloimiseen unigrammitodennäköisyyksien kanssa (tai vaihtoehtoisesti perääntymiseen). Bigrammimallille absoluuttisen vähennyksen ja interpoloinnin yhdistäminen antaa siis estimaatin:

$$P(w_i\vert w_{i-1}) = \frac {\max(C(w_i,w_{i-1})-D,0)} {C(w_{i-1})} + \gamma(w_{i-1}) \frac {C(w_i)} {C(0)}$$

Tässä $\gamma(w_{i-1})$ on bigrammihistoriasta riippuva kerroin, joka normalisoi todennäköisyysjakauman summautumaan ykköseen. Sen arvo voidaan laskea siitä kuinka monta erilaista seuraajaa historialla opetusaineistossa oli:

$$\gamma(w_{i-1}) = \vert \{ (w_{i-1}, w_i): C(w_i,w_{i-1}) > 0 \} \vert \cdot \frac {D} {C(w_{i-1})}$$

Aloitetaan laskemalla historioille ``olla'' ja ``vaikuttaa'' nämä interpolointikertoimet. Historialla ``olla'' on esiintynyt viisi erilaista seuraajaa ja se on yhteensä esiintynyt viisi kertaa. Historialla ``vaikuttaa'' on yksi esiintynyt seuraaja, ja esiintymiä myös yksi. Siispä:

$$\gamma(\textrm{olla}) = 5 \cdot \frac{0.5}{5} = 0.5$$

$$\gamma(\textrm{vaikuttaa}) = 1 \cdot \frac{0.5}{1} = 0.5$$

Nyt voidaan laskea interpoloidut bigrammitodennäköisyydet:

$$P(\textrm{'olla'} \vert \textrm{'olla'}) = \frac{0}{5} + 0.5 \frac{5}{98} = 0.025$$

$$P(\textrm{'leuto'} \vert \textrm{'olla'}) = \frac{1}{5} + 0.5 \frac{1}{98} = 0.205$$

$$P(\textrm{'gorilla'} \vert \textrm{'olla'}) = \frac{0}{5} + 0.5 \frac{0}{98} = 0.0$$

$$P(\textrm{'olla'} \vert \textrm{'vaikuttaa'}) = \frac{0}{1} + 0.5 \frac{5}{98} = 0.025$$

$$P(\textrm{'leuto'} \vert \textrm{'vaikuttaa'}) = \frac{0}{1} + 0.5 \frac{1}{98} = 0.005$$

$$P(\textrm{'gorilla'} \vert \textrm{'vaikuttaa'}) = \frac{0}{1} + 0.5 \frac{0}{98} = 0.0$$

Huomataan että menelmä ei tälläisenään anna yhtään todennäköisyyttä opetusaineiston ulkopuoliselle sanastolle (gorilla). Tämä voitaisiin korjata käyttämällä unigrammitodennäköisyyksille vielä jotain tasoitusmenetelmää. Mahdollista olisi myös jatkaa interpolointia niin sanoittuihin nollagrammeihin, mikä tarkoittaa tasajakauman kanssa interpolointia.

Interpolointi tai peräytyminen matalamman asteen n-grammeihin ei kuitenkaan aina ole täysin luotettavaa. Esimerkkinä voidaan tarkastella bigrammia ``San Francisco''. Koska paikannimi on hyvin tunnettu, estimaatti $P(\textrm{'Francisco'} \vert \textrm{'San'})$ on todennäköisesti luotettava. Eli jos edellinen sana on ``San'', ei tule ongelmia. Mutta entä jos edellinen sana ei ollut ``San''? Tällöin Fanciscon todennäköisyyden pitäisi olla selvästi pienempi kuin silloin, kun tarkastellaan unigrammijakaumaa ilman tietoa edellisestä sanasta. Tähän ideaan pohjautuu Kneser-Ney -tasoitus, jossa alemman asteen n-grammien todennäköisyydet estimoidaan arvioimalla kuinka todennäköistä sanan on esiintyä uudessa kontekstissa. Tällä hetkellä parhaaksi todettu tasoitusmenetelmä on juuri modifioitu Kneser-Ney -interpolointi, joka käyttää näiden tyyppiestimaattien lisäksi absoluuttista vähennystä kolmella erikseen optimoitavalla vakiolla.

4.

Muutetaan hämmentyneisyyden (perplexity) kaavaa niin, että voidaan suoraan käyttää log-todennäköisyyksiä:

$$perp(w_1,w_2,\dots,w_N) = \prod_{i=0}^NP(w_i\vert w_{i-1},\dots,w_1)^{-\frac1N}$$

$$= \prod_{i=0}^N 10^{-\frac1N \log(P(w_i\vert w_{i-1},\dots,w_1))}$$

$$= 10^{-\frac1N \sum_{i=0}^N \log(P(w_i\vert w_{i-1},\dots,w_1))}$$

Lasketaan summa erikseen:

$$\sum_{i=0}^N \log(P(w_i\vert w_{i-1},\dots,w_1))$$

$$= \overbrace{-4.1763}^{\textrm{kielen}} ~\overbrace{-2.1276}^{\text... ...verbrace{-0.8876}^{\textrm{ja}} ~\overbrace{+0.0495-4.1804}^{\textrm{huonosti}}$$

$$~\overbrace{-0.1415-0.1652-5.2195}^{\textrm{ymmärretty}}$$

$$= -21.5644$$

Niille sanoille, joille ei löytynyt trigrammimallia, jouduttiin käyttämään sekä perääntymiskerrointa että todennäköisyyttä. Jos myöskään bigrammimallia ei löytynyt, jouduttiin vielä kerran perääntymään.

Sijoitetaan vielä luvut hämmentyneisyyden lausekkeeseen

$$perp(w_1,w_2,\dots,w_N)=10^{\frac{-21.5644}{-7}}\approx 1200$$

Tulosta voi ajatella vaikka niin, että kielimalli vastaa sellaista kielimallia, joka joutuu valitsemaan 1200 yhtä todennäköisen sanan väliltä (ei ihan eksaktisti paikkansapitävä väite).

Sana ``tapahtumaketju'' ei ollut 64000 yleisimmän sanan joukossa ja ei sisältynyt siis kielimalliin. Kielimallin ohi meni siis $\frac18\approx13\%$ sanoista.