T-61.281 Luonnollisen kielen tilastollinen käsittely
Vastaukset 8, ti 16.3.2004, 8:30-10:00 Tilastolliset yhteydettömät kieliopit, Versio 1.0

1.
Jäsennyspuun todennäköisyys lasketaan paloittelemalla se säännöstön yksiköiden kokoisiin paloihin ja kertomalla näiden palojen todennäköisyydet yhteen. Esimerkiksi muunnoksen ( $ NP \rightarrow$ hän) todennäköisyys voidaan suoraan poimia säännöstöstä ja on 0.3. Samoin esimerkiksi muunnos ( $ SI \rightarrow REL ~ V$) on 0.5. Kuvaan 1 on poimittu taulukoidut todennäköisyydet.

Kuva: Jäsennykset
\begin{figure}\begin{center} \leavevmode \hfill \epsfig{file=puu1_vast.eps,wi... ...psfig{file=puu2_vast.eps,width=0.43\textwidth} \hfill \end{center} \end{figure}

Nyt voimmekin laskea kummankin jäsennyksen todennäköisyydet kertomalla kaikki kuvasta löytyvät todennäköisyydet

$\displaystyle P(\textrm{puu1})$ $\displaystyle =$ $\displaystyle 0.3 \cdot 0.3 \cdot 0.1 \cdot 0.5 \cdot 0.1 \cdot 0.5 \cdot 0.3 \cdot 0.5 \cdot 0.02\cdot 0.5 \cdot 0.1\cdot 0.7 \cdot 1.0$  
  $\displaystyle =$ $\displaystyle 2.4\cdot 10^{-8}$  


$\displaystyle P(\textrm{puu2})$ $\displaystyle =$ $\displaystyle 0.3 \cdot 0.3 \cdot 0.1 \cdot 0.5 \cdot 0.1 \cdot 0.5 \cdot 0.3 \cdot 0.5 \cdot 0.5 \cdot 0.1\cdot 0.7 \cdot 0.08\cdot 1.0$  
  $\displaystyle =$ $\displaystyle 9.5\cdot 10^{-8}$  

Huomataan, että mallin mukaan toinen jäsennys on todennäköisempi. Ilman muuta tietoa tai oikein pilkutettua tekstiä lienee mahdotonta päätellä, kumpi jäsennys on oikea.
2.
Sisäpuoli-algoritmi (inside algorithm) on hyvin samanlainen kuin eteenpäin algoritmi. Algoritmissa lasketaan puun todennäköisyyttä lähtemällä lehdistä ja kasaamalla koko ajan suurempia yksikköjä kunnes päästään juureen asti. Algoritmia läpikäydessä tullaan samalla kokeilleeksi kaikki mahdolliset jäsennykset.

Merkitään $ \beta_j(p,d)$ todennäköisyyttä, että puulla, joka kattaa sanat $ p$:stä $ d$:hen on juurena jäsennys $ j$. Nyt siis voimme alustaa algoritmin $ \beta_j(k,k)$ arvot lehdille. Koska suurin osa lauseen sanoista voi olla kotoisin vain yhdestä ei-terminaalisymbolista, alustus on helppoa:

$\displaystyle \begin{array}{lcll} \beta_{NP}(1,1) &=& 0.3 ~~~~ &\textrm{\script... ...xtrm{\scriptsize {5. sanan tila NP ja havainto \lq\lq kasvoillaan''}}\\ \end{array}$

Kaikki muut todennäköisyydet ovat nollia. Alustuksesta voidaan edetä puun juureen summaamalla kaikkien todennäköisyyksin yli seuraavan kaavan mukaisesti:

$\displaystyle \beta_j(p,q)= \displaystyle{\sum_{r,s} \sum_{d=p}^{q-1} P(N^j \rightarrow N^rN^s) \beta_r(p,d)\beta_s(d+1,q)}$    

Tässä siis summataan kaikkien mahdollisten sääntöjen ($ r,s$) ja kaikkien mahdollisten jakojen ($ d$:stä $ q$:hun) yli. Koska yleensä sekä transitio-, että havaintosäännöt ovat melko harvoja, on suurin osa summan termeistä nollia.

Lasketaanpa sitten seuraavat arvot. Nyt kukin alipuulla koostuu kahdesta lapsesta ja juuresta:

$\displaystyle \begin{array}{lcll} \beta_{x}(1,2) \!&=&\! \displaystyle \sum_{y,... ...P \rightarrow\! A ~ NP)\\ &=&\! 0.15\cdot0.15\cdot 1.0 = 0.023 \\ \end{array}$

Koskapa kieliopissa yhdellä solmulla olla vain kaksi lasta, saadaan seuraavalle kierrokselle todennäköisyydet summaamalla:

$\displaystyle \begin{array}{lll} \beta_{S}(1,3) &=& \beta_{NP}(1,1) \beta_{VP}(... ...arrow NP ~ PP)\\ &=& 0.15\cdot 0.023 \cdot 0.15 = 5.2\cdot 10^{-4} \end{array}$

Vielä on pari kierrosta jäljellä:

$\displaystyle \begin{array}{lll} \beta_{x}(1,4) &=& \displaystyle { \sum_{y,z} ... ...2 = 1.1 \cdot 10^{-4} + 1.4 \cdot 10^{-4} \\ &=& 2.43\cdot 10^{-4} \end{array}$

Tässä kohtaa kannattaa huomata, että laskettaessa $ \beta_{VP}(2,5)$, yhdistetään kahden erilaisen jäsennyksen todennäköisyydet. Jos nyt tehtäisi Viterbi-hakua, valittaisiin näistä kahdesta todennäköisempi ja merkattaisiin, kumpi jäsennys on parempi. Tässä tapauksessa siis on parempi jäsentää sanat ``tunsi'' ja ``tuulen'' verbilauseeksi ja sanat ``kalpeilla kasvoillaan'' liittolauseeksi. Toinen vaihtoehto olisi ollut jäsentää sana ``tunsi'' verbiksi ja ``tuulen kalpeilla kasvoillaan'' liitolauseeksi.

Lasketaanpa vielä homma loppuun ennen tarkempia pohdintoja.

$\displaystyle \begin{array}{lll} \beta_{S}(1,5) &=& \beta_{NP}(1,1)\cdot \beta_... ...htarrow NP ~ VP) \\ &=& 0.3*2.43\cdot 10^{-4}*1.0=7.2\cdot 10^{-5} \end{array}$

Kuvaan 2 on piirretty mahdolliset jäsennykset. Mallin mukaan hieman todennäköisempi jäsennys on väärä, johtunee siitä että alkuperäinen malli oli hihasta ravistettu.

Kuva: Mahdolliset jäsennykset. Vasen puu on hiukan todennäköisempi.
\begin{figure}\begin{center} \leavevmode \hfill \epsfig{file=jas1_vas.eps,wid... ...epsfig{file=jas2_vas.eps,width=0.43\textwidth} \hfill \end{center} \end{figure}

3.
Merkitään $ q=1-p$. Olkoon $ F(n)$ todennäköisyysmassa kaikissa $ n$-syvyisissä tai matalammissa puissa (katso kuva 3). Nyt huomataan, että $ F(n+1)$ voidaan ilmaista $ F(n)$:n avulla. Joko $ F(n+1)$ terminoituu suoraan todennäköisyydellä $ q$ tai sitten se jakautuu kahdeksi puuksi todennäköisyydellä $ p$. Näiden puiden maksimisyvyys on $ n$. Saadaan siis

$\displaystyle F(n+1)=q+pF(n)^2 = 1-p+pF(n)^2$    

Kuva: $ F(n)$ eli kaikkiin $ n$-syvyisiin tai matalampiin puihin uponnut todennäköisyysmassa.
\begin{figure}\begin{center} \leavevmode \epsfig{file=spuu.eps,width=0.3\textwidth} \end{center} \end{figure}

Oletetaan, että sarja konvergoi johonkin arvoon (todistetaan myöhemmin). Tällaisessa tilanteessa $ F(n+1)=F(n)$ eli

$\displaystyle F(n+1)=1-p+pF(n)^2$ $\displaystyle =$ $\displaystyle F(n)$  
$\displaystyle pF(n)^2-F(n)+1-p$ $\displaystyle =$ 0  

Toisen asteen yhtälön ratkaisukaavasta saadaan yhtälölle juuret

$\displaystyle F(n)=\left\{ \begin{array}{l}1\\ \frac1p-1\\ \end{array} \right. $

Jotta voidaan todistaa, että funktio konvergoi, pitää todistaa, että se on kasvava. Tutkitaan erotusta $ F(n+1)-F(n)$:
$\displaystyle F(n+1)-F(n)$ $\displaystyle >$ 0  
$\displaystyle 1-p+pF(n)^2-F(n)$ $\displaystyle >$ 0  

Toisen asteen yhtälön ratkaisukaavan avulla saadaan, että funktio on kasvava jos:
$\displaystyle 1$ $\displaystyle :$ $\displaystyle F(n)>1 ~\textrm{ja}~ p<0$  
$\displaystyle 2$ $\displaystyle :$ $\displaystyle F(n)<1 ~\textrm{ja}~ p>0$  

Näistä toinen alue on relevantti meille. Osoitetaan vielä, että funktio kasvaa asymptoottisesti kohti pienempää juurta $ (\min(1,\frac1p-1))$. Jos $ F(n+1)>1$, mitä ehtoja se asettaa $ F(n)$:lle ?
$\displaystyle F(n+1)=1-p+pF(n)^2$ $\displaystyle >$ $\displaystyle 1$  
$\displaystyle pF(n)^2$ $\displaystyle >$ $\displaystyle p$  
$\displaystyle F(n)<-1$ $\displaystyle \textrm{tai}$ $\displaystyle F(n)>1$  

Eli sarja voi saada yhtä suurempia arvoja vain, jos sarjan edellinen arvo oli jo suurempi kuin yksi. Nyt lähdemme liikkeelle nollasta $ F(1)=0$, joten yli yhden arvoja ei voida saada. Entäpä toinen juuri, mitä jos $ F(n+1)>\frac1p-1$ ?
$\displaystyle F(n+1)=1-p+pF(n)^2$ $\displaystyle >$ $\displaystyle \frac1p-1$  
$\displaystyle F(n)^2$ $\displaystyle >$ $\displaystyle \frac{1-2p+p^2}{p^2}$  
$\displaystyle F(n)^2$ $\displaystyle >$ $\displaystyle \left( \frac{1-p}p \right) ^2$  

Saadaan ehdot
$\displaystyle 1: F(n)>\frac1p-1$   $\displaystyle \hspace{-2mm}\textrm{edellinen arvo oli jo suurempi kuin juuri}$  
$\displaystyle 2: F(n)<1-\frac1p$   $\displaystyle \hspace{-2mm}\textrm{F kasvava ja }F(2)\!=\!1\!-\!p\!<\! 1\! - \! \frac1p \textrm{ kun } p\!<\!-1 \textrm{ tai } p\!>\! 1 \textrm{. Ehto ei täyty.}$  

Myöskään tämän juuren ohi ei voi päästä. Sarjan summa on siis $ \min(1,\frac1p -1)$. Todennäköisyysjakauma on siis oikea todennäköisyysjakauma, kun $ p\le0.5$. Kun $ p>0.5$, malli rupeaa generoimaan äärettömiä puita (missä generoidaan aina vaan uusia ei-terminaaleja) ja todennäköisyysmassaa katoaa näihin puihin.

Ovelampi matemaatikko pystynee ratkaisemaan muutamalla rivillä. Tarkastelemalla mallin generoimien ei-terminaalien määrän oletusarvoa verrattuna mallin generoimien terminaalien määrän oletusarvoon, päätynee samaan tulokseen.


vsiivola@cis.hut.fi