T-61.5020 Luonnollisen kielen tilastollinen käsittely
Vastaukset 2, ke 31.1.2007, 12:15-14:00 -- Entropia ja hämmentyneisyys
Versio 1.0

1.

a)

Sijoitetaan entropian kaavaan

$$H(X)=\sum_{x\in X}p(x)\log_2\frac{1}{p(x)}$$

tehtävässä annetut arvot:

$$H(X) = \frac{3}{32}\log_2\frac{32}{3}+ \frac{3}{16}\log_2\frac{16}{3} +\frac{7}{32}\log_2\frac{32}{7}$$

$$+ \frac{1}{8}\log_2 8 + \frac{1}{8}\log_2 8 +\frac{1}{4}\log_2 4$$

$$= 2.50 ~\textrm{bittiä}$$

b)

Tehtävän ratkaisuun tarvitaan todennäköisyyttä $P(S=s)$ (eli satunnainen substantiivi on $s$). Tämä todennäköisyys saadaan tehtävänannon taulukon oikeasta marginaalista. Lisäksi tarvitaan todennäköisyyttä

$$P(V=v \vert S=s) = \frac{P(S=s,V=v)}{P(S=s)}$$

Lähteen entropia, kun tiedetään, että edellinen symboli kuului joukkoon $S$ on

$$H(X_i\vert X_{i-1}\in S)=\sum_{S=\{\textrm{'kissa','tuuli','kiipeilijä'}\}}p(s=S)H(V\vert s=S)$$

Tämän laskemiseksi meidän pitää osata laskea ehdollinen entropia $H(V\vert s=S)$. Lasketaan tämä sanalle 'kissa':

$$H(V\vert s=\textrm{'kissa'}) = \hspace{-1.5cm} \sum_{V=\textrm{'naukaisi','tuivertaa','katosi'}}... ...cm} p(v=V\vert s=\textrm{'kissa'}) \log_2 (p(v=V\vert s=\textrm{'kissa'})^{-1})$$

$$= \hspace{-1.5cm} \sum_{V=\textrm{'naukaisi','tuivertaa','katosi'}}... ...extrm{'kissa'})} \log_2 \frac{P(s=\textrm{'kissa'})}{p(s=\textrm{'kissa'},v=V)}$$

$$= \frac 18 \frac {16}{3} \log_2 (8 \frac{3}{16} ) + \frac 1{16} \frac {16}{3} \log_2( 16 \frac{3}{16} )$$

$$= \frac23 \log_2 \frac 32 + \frac13 \log_2 3$$

Kun sijoitamme jokaista joukon $S$ sanaa vastaavat todennäköisyydet, saamme

$$H(X_i\vert X_{i-1}\in S) = \frac{3}{16} (\frac 23 \log_2 \frac 32 + \frac 13 \log_2 3) + \frac 38 (\frac 16 \log_2 6 + \frac 46 \log_2 \frac 64 +\frac16 \log_2 6)$$

$$+\frac 7{16} (\frac 17\log_2 7 + \frac67 \log_2 \frac76)$$

$$= 0.90 ~\textrm{bittiä}$$

Mikä on sitten todennäköisyys, että satunnainen sana on 'kissa'? Koska molemmat luokat $S$ ja $V$ ovat yhtä todennäköiset, tulos on

$$P(x=\textrm{'kissa'})=P(x\in S) P(S=x) = 0.5\cdot \frac{3}{16}=\frac 3{32}$$

Huomaamme, että a)-kohta on itseasiassa b)-kohdan marginaalijakauma.

Tästä voimme päätellä, että kun tunnemme lähteen toiminnan paremmin, sen tuottamat sanat ovat vähemmän yllättäviä ja voimme koodata ne vähemmällä määrällä bittejä (0.9 bittiä < 2.5 bittiä).

c)

Kielen lauseissa ensimmäinen sana on aina substantiivi ja toinen verbi. Substantiivi ei riipu edellisistä sanoista, mutta verbi riippuu edellisestä substantiivista.

Merkitään kielen lausetodennäköisyyksiä $P(S,V)$ ja mallin antamia todennäköisyyksiä $P_M(S,V)$. Haluamme laskea odotusarvon kielen lauseen koodauspituudelle mallin antamilla todennäköisyyksillä:

$$E(-\log P_M(S,V)) = - \sum_{s \in S, v \in V} P(S=s,V=v) \log P_M(S=s,V=v).$$

Tätä mittaa kutsutaan risti-entropiaksi (cross-entropy).

Mallin antamat verbien ja substantiivien todennäköisyydet ovat toisistaan riippumattomia, joten $P_M(S=s,V=v) = P_M(S=s) P_M(V=v)$. Sijoitetaan se lausekkeeseen, ja kirjoitetaan summaus auki ensin substantiivien ja sitten verbien osalta:

$$E(-\log P_M(S,V))$$

$$= - \sum_{s \in S, v \in V} P(S = s, V = v) \log P_M(S = s, V = v)$$

$$= - \sum_{s \in S} \sum_{v \in V} P(S = s) P(V = v \vert S = s) \log (P_M(s) P_M(v))$$

$$= - P(S = \textrm{kissa}) \sum_{v \in V} P(V = v \vert S = \textrm{kissa}) \log (P_M(\textrm{kissa}) P_M(v))$$

$$- P(S = \textrm{tuuli}) \sum_{v \in V} P(V = v \vert S = \textrm{tuuli}) \log (P_M(\textrm{tuuli}) P_M(v))$$

$$- P(S = \textrm{kiipelijä}) \sum_{v \in V} P(V = v \vert S = \textrm{kiipelijä}) \log (P_M(\textrm{kiipelijä}) P_M(v))$$

$$= - \frac{3}{16} \cdot \big[\frac{1}{8}\frac{16}{3} \log(\frac{3}{32} \frac{1}{8}) + \frac{1}{16}\frac{16}{3} \log(\frac{3}{32} \frac{1}{4}) \big]$$

$$- \frac{3}{8} \cdot \big[\frac{1}{16}\frac{8}{3} \log(\frac{3}{16... ...16} \frac{1}{8}) + \frac{1}{16}\frac{8}{3} \log(\frac{3}{16} \frac{1}{4}) \big]$$

$$- \frac{7}{16} \cdot \big[\frac{1}{16}\frac{16}{7} \log(\frac{7}{32} \frac{1}{8}) + \frac{3}{8}\frac{16}{7} \log(\frac{7}{32} \frac{1}{4}) \big]$$

$$= 5.01$$

Lauseden keskimääräinen koodauspituus (ts. risti-entropia lausetta kohti) on siis 5.01 bittiä.

Jokaisessa lauseessa on kaksi sanaa, joten keskimääräinen yhden sanan koodauspituus on 2.50 bittiä. Tulos on sama kuin a)-kohdassa, eikä se ole sattumaa: Kummassakin tapauksessa jakauma, jonka yli odotusarvo mallin antamille koodauspituuksille lasketaan, on sama.

2.

a)

Kunkin alkeistapauksen todennäköisyys on $\frac{1}{30}$. Alkeistapauksia on 30. Sijoitetaan entropian kaavaan:

$$H(X) = \sum_{x\in X}p(x)\log_2\frac{1}{p(x)}$$

$$= \sum_{i=1}^{30}\frac{1}{30}\log_2(30)$$

$$= \log_2(30) \approx 4.91 ~ \textrm{bittiä}$$

b)

Sanan, jossa on vain yksi merkki, sanotaan vaikka joukon ensimmäinen merkki, todennäköisyys on

$$P(s=t_1)=\frac{1}{30}\cdot \frac{1}{30}$$

sillä ensimmäisen merkin pitää olla joukon ensimmäinen ja sitten pitää tulla sanaväli. Tällaisia sanoja on 29 kappaletta.

Vastaavasti, tietyn kahden merkin pituisen sanan todennäköisyys on

$$P(s=t_1,t_1)=\frac{1}{30} \cdot \frac{1}{30} \cdot \frac{1}{30}$$

Tällaisia sanoja on $29^2$ kappaletta. Homma jatkuu samalla tavalla useammille sanoille.

Lasketaan tällaisen lähteen entropia:

$$H(X)\!\!\!\! = \sum_{x\in X}p(x)\log_2\frac{1}{p(x)}$$

$$ = 29*(\frac{1}{30})^2 \log_2(30^2) + 29^2*(\frac{1}{30})^3 \log_2(30^3) + 29^3*(\frac{1}{30})^4 \log_2(30^4) + \dots$$

$$ = \frac{1}{29} \left( \left(\frac{29}{30}\right)^2 \!\!\! \cdot \! ... ...t(\frac{29}{30}\right)^4 \!\!\! \cdot \! 4 \!\cdot \!\log_2(30) + \dots \right)$$

$$ = \frac{\log_2(30)}{29} \left( -\frac{29}{30} + \sum_{i=0}^\infty i\cdot \left( \frac{29}{30} \right) ^i \right)$$

Nyt tarvitaan suluissa olevan summan arvoa. Ratkaistaan annettu sarja seuraavasti:

$$\sum_{i=0}^\infty i q^i = q + 2q^2 + 3q^3 + 4q^4 + \dots$$ (1)

Kerrotaan yhtälö $q$:lla.

$$q\sum_{i=0}^\infty i q^i = q^2 + 2q^3 + 3q^4 + 4q^5 + \dots$$ (2)

Vähennetään yhtälö 2 puolittain yhtälöstä 1

$$(1-q)\sum_{i=0}^\infty i q^i = q + q^2 + q^3 + q^4 + \dots$$ (3)

$$\sum_{i=0}^\infty i q^i = \frac{q + q^2 + q^3 + q^4 + \dots}{1-q}$$ (4)

Kerrotaan yhtälö 4 vielä kerran $q$:lla

$$q\sum_{i=0}^\infty i q^i = \frac{q^2 + q^3 + q^4 + q^5 + \dots}{1-q}$$ (5)

Nyt vähennetään yhtälöt 4 ja 5 toisistaan ja saadaan ratkaisu:

$$(1-q)\sum_{i=0}^\infty i q^i = \frac{q}{1-q}$$ (6)

$$\sum_{i=0}^\infty i q^i = \frac{q}{(1-q)^2}$$ (7)

Tässä ratkaisussa pitää vielä huomioda, että jotta yhtälö 2 voidaan vähentää yhtälöstä 1, pitää sarjojen olla suppenevia, eli $\vert q\vert<1$.

Kun tämä hässäkkä sijoitetaan alkuperäiseen ongelmaan, saadaan

$$\frac {\log_2(30)}{29}(-\frac{29}{30} + \frac{\frac{29}{30}}{(1-\frac{29}{30})^2})$$

$$= \log_2(30)(30-\frac{1}{30})$$

$$= 147 ~\textrm{bittiä}$$

Ensi silmäyksellä tämä tulos saattaa tuntua hämmentävältä, eikä tuloksen pitäis olla sama kuin a)-kohdassa? Pikainen tarkistuslasku ehkä hälventää hieman epäluuloja: Sanan pituuden odotusarvo on 29, eli entropia per merkki on n. $147/(29+1)=4.90$ bittiä.

On myös syy, miksi tulosten ei pitäisi olla aivan samat: Ensimmäinen lähde voi tuottaa sanan, jossa on kaksi välilyöntiä peräkkäin, kun taas toinen lähde ei voi annetun formuloinnin mukaan sitä tuottaa. Tästä johtuen pitäisi toisen lähteen entropia per merkki olla hieman alempi.

3.

Ensin hieman johdatusta aiheeseen: Haluamme tutkia kuinka hyvin luomamme malli ennustaa mallinnettavaa ilmiötä, tässä tapauksessa kieltä. Jos mallinnettavaan ilmiöön liittyvä todennäköisyysjakauma on tiedossa, voisimme laskea esimerkiksi mallin jakauman ja sen välisen risti-entropian (tehtävä 1c). Yleensä mallinnettavaa jakaumaa ei tietenkään tunneta. (Muutenhan olisi monesti turhaa edes tehdä toista mallia.) Tällöin evaluointimitan täytyy perustua johonkin ilmiön tuottamaan datajoukkoon. Datajoukolle $D$ voidaan esimerkiksi laskea luodun mallin $M$ antama uskottavuus (likelihood), $P(D\,\vert\,M)$. Helpommin käsiteltävä luku on yleensä uskottavuuden logaritmi normalisoituna datajoukon koolla:

$$\textrm{Average-Log-Likelihood}(D\,\vert\,M) = \frac{1}{n}\sum_{i=1}^n \log P(D_i \,\vert\,M)$$

Kun logaritmin kantaluku on 2, tämä on itse asiassa (etumerkkiä vaille) risti-entropian suurimman uskottavuuden estimaatti. Kun muokkaamme lauseketta hieman, huomaamme vielä että tämä risti-entropian estimaatti on hämmentyneisyyden (perplexity) logaritmi:

$$- \frac{1}{n} \sum_{i=1}^n \log P(D_i \,\vert\,M) = \sum_{i=1}^n ... ...{1}{n}} = \log \big[ ( \prod_{i=1}^n P(D_i \,\vert\,M) )^{-\frac{1}{n} } \big].$$

Huomattakoon, että näissä kaavoissa oletetaan että datapisteiden todennäköisyydet ovat toisistaan riippumattomia. Kielen mallinnuksessa näin ei yleensä ole, vaan tarkka lauseke todennäköisyyksille olisi tekstiä ennustavassa mallissa $P(D_i \,\vert\, D_1, \dots, D_{i-1}, M)$.

Seuraavaksi itse laskuihin:

a)

Merkitään mallin yksi antamaa hämmentyneisyyttä $Perp_1$, mallin 2 puolestaan $Perp_2$ ja niin edelleen.

$$Perp_1(\textrm{'kissa'},\textrm{'menee'},\textrm{'puuhun'})$$

$$=P_1(\textrm{sana$_1$='kissa'},\textrm{sana$_2$='menee'},\textrm{sana$_3$='puuhun'})^{-\frac13}$$

$$=\left( P_1(\textrm{sana='kissa'})P_1(\textrm{sana='menee'}) P_1(\textrm{sana='puuhun'})\right)^{-\frac13}$$

$$=(0.1\cdot 0.1 \cdot 0.1)^{-\frac 13} = 10$$

Malli 1 siis valitsee koko ajan keskimäärin kymmenestä eri sanasta. Tulos vaikuttaa oikealta. Entäpä malli 2?

$$Perp_2(\textrm{'kissa'},\textrm{'menee'},\textrm{'puuhun'})$$

$$= P_2(\textrm{sana$_1$=subjekti},\textrm{sana$_2$=verbi},\textrm{sana$_3$=kohde})^{-\frac13}$$

$$= \left( P_2(\textrm{sana=subjekti})P_2(\textrm{sana=verbi}) P_2(\textrm{sana=kohde})\right)^{-\frac13}$$

$$= (0.33\cdot 0.33 \cdot 0.33)^{-\frac 13} = 3$$

Malli 2 valitsee keskimäärin 3:sta eri vaihtoehdosta, tulos vaikuttaa järkevältä.

$$Perp_3(\textrm{'kissa'},\textrm{'menee'},\textrm{'puuhun'})$$

$$= P_3(\textrm{sana$_1$='kissa'},\textrm{sana$_2$='menee'},\textrm{sana$_3$='puuhun'})^{-\frac13}$$

$$= ( P_3(\textrm{sana='kissa'\vert sana=ensimmäinen})$$

$$\cdot P_3(\textrm{sana='menee' \vert edellinen\_sana = 'kissa'})$$

$$\cdot P_3(\textrm{sana='puuhun' \vert edellinen\_sana $=$\ 'menee'}) )^{-\frac13}$$

$$= (0.25\cdot 0.33 \cdot 0.33)^{-\frac 13} = 3.32$$

Tämä malli valitsee siis keskimäärin 3.32 sanasta koko ajan.

Tämän esimerkin valossa kielimallit 1 ja 3 ovat vertailukelpoiset. Kielimalli 3 vaikuttaa näistä selvästi paremmalta. Kielimalli 2 ei voi verrata muihin, sillä se operoi selvästi pienemmällä symbolijoukolla. Selvempi esimerkki olisi ehkä kielimalli, jonka mielestä kaikki sanat kuuluvat ryhmään 1 ja tämän ryhmän todennäköisyys on siis 1. Tämä kielimalli siis hämmentyneisyyden mukaan täydellinen, sillä se ei ole yhtään yllättynyt mistään sanasta.

b)

Tarkastellaanpa vielä toista testilausetta. Mallille 1

$$Perp_1(\textrm{'valas'},\textrm{'on'},\textrm{'kala'},\textrm{'paitsi'},\textrm{'ettei'})$$

$$= (P_1(\textrm{sana='valas'})P_1(\textrm{sana='on'}) P_1(\textrm{sana='kala'})$$

$$\cdot P_1(\textrm{sana='paitsi'})P_1(\textrm{sana='ettei'}))^{-\frac15}$$

$$= (0.1\cdot 0.1 \cdot 0.1 \cdot 0 \cdot 0 )^{-\frac 15}$$

$$= \frac{1}{0^\frac 15} = \infty$$

Huomataan, ettei hämmentyneisyyttä voida laskea, jos malli asettaa testijoukon sanalle todennäköisyyden nolla. Usein nämä sanat jätetään huomiotta ja saadaan siis

$$Perp_1(\textrm{'valas'},\textrm{'on'},\textrm{'kala'})$$

$$= \left( P_1(\textrm{sana='valas'})P_1(\textrm{sana='on'}) P_1(\textrm{sana='kala'})\right)^{-\frac13} =10$$

Jotta tulos olisi mielekäs, on nyt myös ilmoitettava ohi kieliopin menneet sanat, tässä tapauksessa siis $\frac25\cdot 100\%=40\%$ sanoista ei osunut kielioppiin. Mallille 2 sadaan vastaavasti

$$Perp_2(\textrm{'valas'},\textrm{'on'})$$

$$= \left( P_2(\textrm{sana=subjekti})P_2(\textrm{sana=verbi}) \right)^{-\frac13}$$

$$= (0.33\cdot 0.33)^{-\frac 12} = 3$$

Ohi kieliopin menee myös 60% sanoista.

Malliin kolme sopii vain kaksi ensimmäistä sanaa:

$$Perp_3(\textrm{'valas'},\textrm{'on'})$$

$$= ( P_3(\textrm{sana='valas'\vert sana=ensimmäinen})$$

$$\cdot P_3(\textrm{sana='on' \vert edellinen\_sana = 'valas'})) )^{-\frac13}$$

$$= (0.25\cdot 0.33)^{-\frac 12} = 3.5$$

Tässä siis 60% sanoista menee ohi kieliopin.

Ovatko b)-kohdan tulokset vertailukelpoisia? Malli 2 voidaan diskata samoilla perusteilla kuin a)-kohdassakin. Malleja 1 ja 3 voidaan vertailla, kun otetaan myös huomioon ohi kieliopin menneet sanat. Malli 1 kattaa sanaston paremmin, mutta malli 3 antaa paremman hämmentyneisyyden. Usein kielimallin laatiminen on tasapainottelua näiden kahden ominaisuuden välillä.

Mikä siis on tarinan opetus? Hämmentyneisyydellä voidaan verrata kahta kielimallia, jos tulokset lasketaan samalla tavalla ja myös ohi kieliopin menneitten sanojen osuus ilmoitetaan. Eri lähteissä olevia tuloksia verratessa kannattaa kuitenkin kiinnittää huomiota siihen, miten laskut tarkalleen ottaen on tehty, jottei vedä vääriä johtopäätöksiä.

Loppuyhteenvetona lista erilaisista entropiamitoista:

• Entropia (entropy)
  $H(X) = E(-\log P(X)) = \sum_x P(x) \log \frac{1}{P(x)}$
  Tulkinta: Lähteen itseinformaatio eli keskimääräinen koodauspituus, joka tarvitaan viestin lähettämiseen optimaalisella koodauksella

• Risti-entropia (cross-entropy)
  $H_M(X) = E(-\log P_M(X)) = \sum_x P(x) \log \frac{1}{P_M(x)}$
  Tulkinta: Keskimääräinen koodauspituus, joka tarvitaan viestin lähettämiseen mallilla $M$

• Suhteellinen entropia (relative entropy) / Kullback-Leibler divergenssi
  $D(P(X) \vert\vert P_M(X)) = E(-\log \frac{P(X)}{P_M(X)}) = \sum_x P(x) \log \frac{P(x)}{P_M(x)} = H_M(X) - H(X)$
  Tulkinta: Kuinka monta bittiä hävitään, jos koodataan lähteen viestejä mallilla $M$

• Hämmentyneisyys (perplexity)
  $Perp_M(X) = 2^{H_M(X)} = \prod_{x} (\frac{1}{P_M(x)})^{P(x)}$
  Tulkinta: Keskimääräinen mallin $M$ haarautumiskerroin lähteen datalle