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

1.
Otetaan pieni kieli johon kuuluu kuusi sanaa:
W P(W)
'kissa' $ \frac{3}{32}$
'tuuli' $ \frac{3}{16}$
'kiipeilijä' $ \frac{7}{32}$
'naukaisi' $ \frac{1}{8}$
'tuivertaa' $ \frac{1}{8}$
'katosi' $ \frac{1}{4}$
a)
Oletetaan että lähde tuottaa satunnaismuuttujan $ X$ arvoja yo. taulukon todennäköisyyksien mukaan. Mikä on lähteen entropia $ H(X)$?
b)
Tarkemmin asiaa tutkittaessa käykin ilmi että kielessä on lauserakenne 'SV' jossa kategoriat S $ \in$ {'kissa', 'tuuli', 'kiipeilijä'} ja V $ \in$ {'naukaisi', 'tuivertaa', 'katosi'}. Satunaismuuttujien yhteistodennäköisyysjakauma P(S,V) on:

  'naukaisi' 'tuivertaa' 'katosi'  
'kissa' $ \frac{1}{8}$ 0 $ \frac{1}{16}$ $ \frac{3}{16}$
'tuuli' $ \frac{1}{16}$ $ \frac{1}{4}$ $ \frac{1}{16}$ $ \frac{3}{8}$
'kiipeilijä' $ \frac{1}{16}$ 0 $ \frac{3}{8}$ $ \frac{7}{16}$
  $ \frac{1}{4}$ $ \frac{1}{4}$ $ \frac{1}{2}$  


Mikä on lähteen entropia, kun tiedetään, että edellinen symboli kuului joukkoon S, eli mikä on $ H(X_i\vert X_{i-1}\in S)$?

c)
Oletetaan että kieli noudattaa b)-kohdan todennäköisyyksiä. Mallinnetaan tämän kielen substantiivilla alkavia kaksisanaisia lauseita a)-kohdan mallilla. Laske kuinka monta bittiä keskimäärin lausetta kohti on käytettävä lauseiden koodamiseen mallin antamilla optimaalisilla koodinpituuksilla.

2.
Tarkastellaan edellisesta laskarista tuttua satunnaista kieltä: 30 symbolia, jotka kukin ovat yhtä todennäköisiä. Yksi symboleista on sanaväli.
a)
Lähde generoi merkkejä yhden kerrallaan. Mikä on lähteen entropia?
b)
Lähde generoi yhden sanan kerrallaan (eli merkki/merkkejä + sanaväli). Kutakin sanaa kohdellaan yhtenä omana kokonaisuutenaan. Mikä on tällaisen lähteen entropia?

3.
Meillä on kolme kielioppia, jotka on esitetty seuraavan sivun taulukoissa. Testimateriaalina meillä on kaksi lausetta:
a)
Kissa menee puuhun.
b)
Valas on kala paitsi ettei.

Laske kunkin mallin hämmentyneisyys (perplexity) molemmille testilauseille. Ovatko tulokset keskenään vertailukelpoisia?

Hämmentyneisyys voidaan määritellä testijoukon sanojen todennäköisyyksien geometrisen keskiarvon käänteislukuna:

$\displaystyle Perp(w_1,w_2,\dots,w_n)=P(w_1,w_2,\dots,w_n)^{-\frac1n}$    


Malli 1 Malli 2
P(sana='kissa')=0.1 P(sana=subjekti)=0.33
P(sana='koira')=0.1 P(sana=verbi)=0.33
P(sana='valas')=0.1 P(sana=kohde)=0.33
P(sana='kala')=0.1  
P(sana='istui')=0.1  
P(sana='menee')=0.1  
P(sana='on')=0.1  
P(sana='puuhun')=0.1  
P(sana='kuuhun')=0.1  
P(sana='suuhun')=0.1  




Malli 3  
P(sana='kissa' | sana=ensimmäinen) =0.25
P(sana='koira' | sana=ensimmäinen) =0.25
P(sana='valas' | sana=ensimmäinen) =0.25
P(sana='kala' | sana=ensimmäinen) =0.25
P(sana='istui' | edellinen_sana $ \in$ {'kissa','koira','valas','kala'}) =0.33
P(sana='menee' | edellinen_sana $ \in$ {'kissa','koira','valas','kala'}) =0.33
P(sana='on' | edellinen_sana $ \in$ {'kissa','koira','valas','kala'}) =0.33
P(sana='puuhun' | edellinen_sana $ \in$ {'istui','menee','on'}) =0.33
P(sana='kuuhun' | edellinen_sana $ \in$ {'istui','menee','on'}) =0.33
P(sana='suuhun' | edellinen_sana $ \in$ {'istui','menee','on'}) =0.33



svirpioj@cis.hut.fi