T-61.5020 Luonnollisen kielen tilastollinen käsittely
Ratkaisut 1, ke 24.1.2007, 12:15-14:00 -- Todennäköisyyslaskennan perusteita
Versio 1.0

1.
Todennäköisyyksistä ensimmäinen $ P(~\textrm{sana=lyhenne} ~\vert~ \textrm{sana=kolmikirjaiminen}~) = 0.8 $ kertoo, että jos me näemme kolmikirjaimisen sanan, se on todennäköisyydellä $ 0.8$ lyhenne ja todennäköisyydellä $ 0.2$ jotain muuta.

Toinen kaava $ P(~\textrm{sana=kolmikirjaiminen}~) = 0.0003 $ kertoo, että satunnainen sana on todennäköisyydellä $ 0.0003$ kolmikirjaiminen ja todennäköisyydellä $ 0.9997$ jotain muuta.

Todennäköisyys, että satunnainen sana on kolmikirjaiminen lyhenne saadaan kertomalla edellä annetut todennäköisyydet keskenään. Eli ensin katsotaan, kuinka todennäköistä on, että sana on kolmikirjaiminen ja sitten vielä kuinka todennäköistä on, että kolmikirjaiminen sana olisi lyhenne:

    $\displaystyle P(~\textrm{sana=lyhenne},\textrm{sana=kolmikirjaiminen}~)$  
  $\displaystyle =$ $\displaystyle P(~\textrm{sana=kolmikirjaiminen}~)\cdot P(~\textrm{sana=lyhenne} ~\vert~ \textrm{sana=kolmikirj.}~)$  
  $\displaystyle =$ $\displaystyle 0.0003*0.8=0.00024$  

Sivuhuomautuksena sanottakoon, että annetut todennäköisyydet eivät varmaankan päde todelliselle englannin kielelle.

2.
Merkitään kantamuotoa ``se'' $ C_1$:llä ja kantamuotoa ``siittää'' $ C_2$:lla. Tunnistustulos olkoon $ T$ ja oikea luokka $ O$. Kirjoitetaan tehtävässä annetut todennäköisyydet:
$\displaystyle P(T=C_1\vert O=C_1)$ $\displaystyle =$ $\displaystyle 0.95$  
$\displaystyle P(T=C_1\vert O=C_2)$ $\displaystyle =$ $\displaystyle 0.05$  
$\displaystyle P(T=C_2\vert O=C_1)$ $\displaystyle =$ $\displaystyle 0.05$  
$\displaystyle P(T=C_2\vert O=C_2)$ $\displaystyle =$ $\displaystyle 0.95$  
$\displaystyle P(O=C_1)$ $\displaystyle =$ $\displaystyle 0.999$  
$\displaystyle P(O=C_2)$ $\displaystyle =$ $\displaystyle 0.001$  

Nyt voimme laskea Bayesin kaavan

$\displaystyle P(B_j\vert A)=\frac{P(A\vert B_j)P(B_j)}{P(A)}=\frac{P(A\vert B_j)P(B_j)}{\sum_i P(A\vert B_i)P(B_i)}$    

avulla todennäköisyyden, että laiteen väittäessä sanan perusmuodoksi ``siittää'' se on myös oikeassa.
$\displaystyle P(O\!$ $\displaystyle =$ $\displaystyle C_2\vert T = C_2)$  
  $\displaystyle =$ $\displaystyle \frac{P(T\!=\!C_2\vert O\!=\!C_2)P(O\!=\!C_2)}{P(T\!=\!C_2\vert O\!=\!C_2)P(O\!=\!C_2) +
P(T\!=\!C_2\vert O\!=\!C_1)P(O\!=\!C_1)}$  
  $\displaystyle =$ $\displaystyle \frac{0.95 \cdot 0.001}{0.95 \cdot 0.001+ 0.05 * 0.999} \approx 0.019$  

Sanoista, joiden perusmuodoksi laite on ehdottanut ``siittää'' vain joka viideskymmenes on oikein jäsennetty. Vaikka Åke olikin saanut ihan hyvät tunnistustulokset sinänsä, käytännön testejen jälkeen hän päätti romuttaa tunnistimensa ja ryhtyä jazz-muusikoksi.

3.
Jotta tällainen satunnainen kieli generoisi yksikirjaimisen sanan, sen pitää generoida kaksi merkkiä (joku muu kuin sanaväli ja sanaväli).

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

Tällaisia sanoja on 29 kappaletta.

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

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

Tällaisia sanoja on $ 29^2$ kappaletta. Kolmikirjaimiset sanat

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

ja näitä sanoja on siis $ 29^3$ kappaletta.

Koska sanan esiintymistodennäköisyys on suoraan verrannollinen sen odotettuun esiintymistiheyteen testiaineistossa, voimme tehdä kirjan taulukon 1.3 kaltaisen taulukon suoraan laskemalla todennäköisyyksiä. Koska samanpituiset sanat ovat yhtä todennäköisiä eikä niitä voi asettaa yleisyysjärjestykseen, laskemme $ k$:n arvon vain yhdelle samanpituisista sanoista. Tulokset on esitetty taulukossa 1 ja piirretty kuvaan 1.


Taulukko: Zipfin vakio. Taulukon vasempaan sarakkeeseen on merkitty kuinka monenneksi yleisin sana on kyseessä. Keskellä lukee, kuinka monta kertaa voimme odottaa näkevämme sanan 1000000 sanan pitusessa aineistossa. Oikealla on laskettu vakio $ k$, kahden ensimmäisen sarakkeen tulo.
$ r$ $ f$ $ k$
15 1111 16111
450 37.04 16648
13064 1.235 16129
378900 0.0412 15593
1098800 0.00137 15073
318660000 0.0000457 14570

Kuva: $ k$ $ r$:n funktiona
\begin{figure}\begin{center}
\epsfig{file=zipf.eps,width=0.5\linewidth}
\end{center}
\end{figure}
Huomataan, että satunnaisellakin kielellä $ k$ pysyttelee melko samansuuruisena hyvin suurella $ r$:n vaihteluvälilläkin. Zipfin löytö ei ehkä tunnu tämän faktan valossa aivan niin hämmästyttävltä.

4.
Tehtävän ratkaisussa oletetaan tunnetuksi seuraavat kaavat:
$\displaystyle E(x)$ $\displaystyle =$ $\displaystyle \int_{-\infty}^\infty xp(x)dx$  
$\displaystyle Var(x)$ $\displaystyle =$ $\displaystyle \int_{-\infty}^\infty (x-E(x))^2 p(x) dx$  

a)
Lasketaan odotusarvo yhden heiton silmäluvuksi. Noppa laskeutuu jokaiselle 101:lle sivustaan yhtä todennäköisesti, eli jokaisen tapahtuman todennäköisyys $ p(x)=\frac{1}{101}$.

Odotusarvo:


$\displaystyle E(x)$ $\displaystyle =$ $\displaystyle \sum_{i=0}^{100} ip(x=i)$  
  $\displaystyle =$ $\displaystyle \frac{1}{101}(1+2+3+4+\dots+100)$  
  $\displaystyle =$ $\displaystyle \frac{1}{101}\left((1+100)+(2+99)+(3+98)+\dots+(50+51)\right)$  
  $\displaystyle =$ $\displaystyle \frac{50*101}{101}=50$  

Varianssi voidaan laskea kaavalla:

$\displaystyle Var(x)$ $\displaystyle =$ $\displaystyle \sum_{i=0}^{100} (i-E(x))^2p(x=i)$  
  $\displaystyle =$ $\displaystyle \frac{1}{101}(50^2+49^2+\dots+1+0+1+2^2+\dots+49^2+50^2)$  
  $\displaystyle =$ $\displaystyle \frac{2}{101}(1+2^2+\dots+49^2+50^2)$  

Nyt voimme käyttää avuksemme seuraava kaavaa

$\displaystyle 1+2^2+3^2+4^2+\dots+n^2=\frac{n(n+1)(2n+1)}{6}$    

jolloin saamme tulokseksi
$\displaystyle Var(x)$ $\displaystyle =$ $\displaystyle \frac{2}{101}\frac{50\cdot 51\cdot 101}{6}=850$  

b)
Ratkaistaksemme tämän tehtävä, tarvitsemme muutamia todennäköisyyslaskun peruskaavoja. Kaavat on tässä johdettu, mutta niiden johtamisen osaaminen ei ole olennaista kurssin kannalta.

Riippumattomien satunnaismuuttujien summan oletusarvo

Olkoon satunnaismuuttujat x ja y riippumattomia. Lasketaan näiden satunnaismuuttujien summan oletusarvo.

$\displaystyle E(x+y)$ $\displaystyle =$ $\displaystyle \int (x+y)p(x,y)dxdy$  
  $\displaystyle =$ $\displaystyle \int (x+y)p(x)p(y)dxdy$  
  $\displaystyle =$ $\displaystyle \int xp(x)p(y)dxdy + \int yp(x)p(y)dxdy$  
  $\displaystyle =$ $\displaystyle \int p(y)dy \int xp(x) dx +\int p(x)dx \int yp(y) dy$  
  $\displaystyle =$ $\displaystyle 1\cdot \int xp(x) dx +1\cdot \int yp(y) dy$  
  $\displaystyle =$ $\displaystyle E(x)+E(y)$  

Vakiolla kerrotun satunnaismuuttujan varianssi


$\displaystyle Var(ax)$ $\displaystyle =$ $\displaystyle \int (ax-E(ax))^2p(x)dx$  
  $\displaystyle =$ $\displaystyle \int(ax-aE(x))^2p(x)dx$  
  $\displaystyle =$ $\displaystyle a^2\int(x-E(x))^2p(x)$  
  $\displaystyle =$ $\displaystyle a^2Var(x)$  

Riippumattomien satunnaismuuttujien summan varianssi

Olkoon satunnaismuuttujat x ja y riippumattomia. Lasketaan näiden satunnaismuuttujien summan varianssi.

$\displaystyle Var(x+y)$ $\displaystyle =$ $\displaystyle \int\int(x+y-E(x+y))^2p(x,y)dxdy$  
  $\displaystyle =$ $\displaystyle \int\int(x+y)^2p(x,y)dxdy-2\int\int(x+y)E(x+y)p(x,y)dxdy$  
    $\displaystyle +\int\int
E(x+y)^2p(x,y)dxdy$  
  $\displaystyle =$ $\displaystyle E((x+y)^2)-2E(x+y)^2+E(x+y)^2$  
  $\displaystyle =$ $\displaystyle E((x+y)^2)-E(x+y)^2$  
  $\displaystyle =$ $\displaystyle E(x^2+2xy+y^2)-(E(x)+E(y))^2$  
  $\displaystyle =$ $\displaystyle E(x^2)+E(2xy)+E(y^2)-E(x)^2-2E(x)E(y)-E(y)^2$  
  $\displaystyle =$ $\displaystyle E(x^2)-E(x)^2 + E(y^2)-E(y)^2$  
    $\displaystyle +\int\int 2xyp(x)p(y)dxdy -2\int xp(x)dx\int yp(y)dy$  
  $\displaystyle =$ $\displaystyle E(x^2)-E(x)^2 + E(y^2)-E(y)^2$  
  $\displaystyle =$ $\displaystyle Var(x)+Var(y)$  

Tämän pakerruksen jälkeen päästään itse asiaan. Nyt halutaan laskea oletusarvo lauseelle $ (x+y)/2$, missä $ x$ on ensimmäiseen heittoon liittyvä satunnaismuuttuja ja $ y$ on toiseen heittoon liittyvä satunnaismuuttuja.

$\displaystyle E(\frac{x+y}{2})=\frac{1}{2}(E(x)+E(y))=\frac 12 (50 +50 ) = 50$    

Huomaamme siis, että odotusarvo ei muutu. Entä miten käykään varianssin?
    $\displaystyle Var(\frac{x+y}{2})=Var(\frac x2)+Var(\frac y2)=\frac 14 Var(x)+ \frac
14 Var(y)$  
    $\displaystyle = \frac 14 ( 850 +850) = 425$  

c)
Heitämme kymmentä noppaa, sovellamme edelle opittuja tuloksia. Odotusarvo

$\displaystyle E(\frac{x_1+x_2+\dots+x_{10}}{10})=\frac{1}{10}\cdot10\cdot 50= 50$    

Varianssi

$\displaystyle Var(\frac{x_1+x_2+\dots+x_{10}}{10})= \frac {1}{100}\cdot 10 \cdot850 = 85$    

d)
Kun heitämme yhä useampaa noppaa, tarkentuu jakauma odotusarvon ympärille. Rajalla odotusarvo on 50 ja varianssi 0 eli saamme aina varmasti tulokseksi 50.

Odotusarvo ja varianssi eivät suinkaan kerro kaikkea jakaumasta. Kuvassa 2 on simuloitu matlabilla erilaisia määriä nopanheittoa. Huomaamme että jakauman muoto muuttuu, mitä useampaa nopaa heitetään. Muoto tulee lähemmäksi ja lähemmäksi normaalijakaumaa. Tämän takia useita luonnollisia ilmiöitä mallinnetaan normaalijakaumalla: Jos tulokseen vaikuttaa monta pientä satunnaista asiaa, tulos on normaalisti jakautunut. Tämä on myös hyvä tekosyy käyttää normaalijakaumaa, jolla saadaan laskut usein helppoon muotoon.

Formaalimpi todistelu siitä, että jakauma lähestyy normaalijakaumaa löytyy http:// mathworld.wolfram.com/CentralLimitTheorem.html

Kuva: Nopanheittoa. Kutakin kuvaa varten on koe toistettu miljoona kertaa.
\begin{figure}\begin{center}
\epsfig{file=noppa.eps,width=\textwidth}
\end{center}
\end{figure}

5.
Tarkoitus on siis minimoida kokonaiskuvauspituutta

$\displaystyle L(x, \theta) = L(\theta) + L(x\,\vert\,\theta).$    

Merkitään lausekkeen minimoivaa parametrijoukkoa $ \hat{\theta}$:lla. Saadaan

$\displaystyle \hat{\theta} = \argmin_{\theta} L(x, \theta) = \argmin_{\theta} \{L(\theta) + L(x\,\vert\,\theta) \}.$    

Sijoitetaan tähän optimaaliset kuvauspituudet $ L(\theta) = -\log p(\theta)$ ja $ L(x\,\vert\,\theta) = -\log p(x\,\vert\,\theta)$:

$\displaystyle \hat{\theta} = \argmin_{\theta} \{-\log p(\theta) - \log p(x\,\vert\,\theta) \}$    

Yhdistetään termit logaritmien laskusääntöä käyttäen:

$\displaystyle \hat{\theta} = \argmin_{\theta} \{-\log( p(\theta) p(x\,\vert\,\theta) ) \}$    

Logaritmi on monotonisesti kasvava funktio, ja sen vastaluku siten monotonisesti laskeva, joten sama arvo saadaan maksimoimalla todennäköisyyksien tuloa:

$\displaystyle \hat{\theta} = \argmax_{\theta} \{ p(\theta) p(x\,\vert\,\theta) \}$    

Lopuksi muistetaan Bayesin kaavasta $ p(x, \theta) = p(x) p(\theta\,\vert\,x) = p(\theta) p(x\,\vert\,\theta)$:

$\displaystyle \hat{\theta} = \argmax_{\theta} \{ p(x) p(\theta\,\vert\,x) \}$    

Jakauma $ p(x)$ ei riipu parametreista, joten se voidaan tiputtaa pois. Näin ollen samaan lopputulokseen päästään mallin posteriorijakauman maksimoinnilla:

$\displaystyle \hat{\theta} = \argmax_{\theta} p(\theta\,\vert\,x)$    



svirpioj@cis.hut.fi