T-61.281 Luonnollisen kielen tilastollinen käsittely
Vastaukset 2, ti 3.2.2004, 8:30-10: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)

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 tarvitaa 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ä).

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 oletusarvo 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.

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

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