T-61.281 Luonnollisten kielten tilastollinen käsittely

Vastaukset 2, ti 4.2.2003, 16:15-18:00 - Entropia, hämmentyneisyys, kontekstivapaa kieli, Versio 1.1

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)

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)$. Jos $s=$''kissa'', todennäköisyys, että sitä seuraa sana ``naukaisi'' on $\frac23$ ja todennäköisyys, että sitä seuraa sana ``katosi'' on $\frac13$. Kaikkien vaihtoehtojen yli summattuna todennäköisyydenhän pitää olla yksi, eli taulukossa annettuja todennäköisyyksiä joudutaan hieman skaalaamaan, tässä tapauksessa vakiolla $\frac{16}3$. Tällaisen lähteen entropiahan on

$$H(V\vert s=\textrm{'kissa'})=\frac 23 \log_2 (\frac 32) + \frac 13 \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ä}$$

Huomataan, 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ä.

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.9 ~ \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)

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 likimainen matematiikka ehkä hälventää hieman epäluuloja: Sanan pituuden oletusarvo on 29, eli entropia per merkki on n. 147/29=5.0 bittiä. Korostettakoon vielä, että tämä viimeinen lasku on vain karkea approksimaatio.

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.

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. Hämmentyneisyydellä voidaan myös ilmoittaa lähes millaisia tuloksia tahansa, jos laskuja on haluttu rukata johonkin suuntaan tai ohi sanaston menevää osuutta ei ilmoiteta. Kannattaa olla tarkkana ainakin eri lähteistä saatujen tulosten vertailussa.

4.

Annetut lauseet on jäsennetty alhaalta ylöspäin. Kun säännöt eivät muuten sopineet, kokeiltiin, auttaisiko tyhjän symbolin ``e'' lisääminen jonnekin. Katso kuvat 1 ja 2. Järjetön lause, jonka kielioppi hyväksyy voisi olla: ``Hyppäsi rapistunut oven.'' Kieliopilla ei ole säännöstöä, millä se pystyisi jäsentämään monimutkaisempia lauseita. Hylätty lause voisi olla: ``Kieltolause ei onnistunut, kuten ei sivulausekaan.''

Kuva: Jäsennys 1

Kuva: Jäsennys 2