\documentclass{myslides}

\usepackage{epic,eepic,figeepic,epsfig}
\usepackage{graphics}
\input{epsf}
\usepackage{amssymb}
\usepackage{array}

\newcommand{\showurl}[1]{\href{#1}{#1}}

\hypersetup{
  pdftitle={T-61.281 Luonnollisten kielten tilastollinen käsittely, kevät 2003},
  pdfsubject={Luentokalvot},
  pdfauthor={Krista Lagus, krista.lagus@hut.fi ja Timo Honkela, timo.honkela@hut.fi},
  }

%%Kun seuraava on päällä, kalvoista voi näyttää vain vähän kerrallaan 
%\dopause

\begin{document}

%======================================================================
%======================================================================
%======================================================================

\thispagestyle{empty}


\section*{%
  {\LARGE\textbf{Luonnollisen kielen \\tilastollinen käsittely}}
}

{\LARGE T-61.281 (3 ov) L}

\bigskip

{\LARGE Kevät 2003}

\bigskip
{\LARGE\makebox[60mm][l]{Luennot:} \textbf{Timo Honkela}}

{\LARGE\makebox[60mm][l]{Laskuharjoitukset:} \textbf{Vesa Siivola}}

\bigskip\bigskip

Luentokalvot: Krista Lagus ja Timo Honkela

%\emph{Kalvokopio \today}

\vspace{\fill}

%\hyperlink{yleista}{\textit{Yleistä kurssista}} 

\newpage
\mydominitoc
%\hypertarget{sisallys}{}
{\parskip=-1pt\mytableofcontents}

\newcommand{\ciseduurl}{http://www.cis.hut.fi/Opinnot}


%----------------------------------------------------------------------

\setcounter{section}{9}

\mynewpage
%----------------------------------------------------------------------
\myslide{Probabilistinen jäsentäminen ja PCFG:t}{}

%\mysubslide{CFG--context-free grammar}{}
%Kontekstivapaa kielioppi


PCFG=Probabilistic Context Free Grammar\\
Todennäköisyyksiin perustuva yhteysvapaa (kontekstivapaa) kielioppi 

\mytopic{Motivaatio}{}
\begin{myitemize}
  \item Tähän asti kielen säännönmukaisuuksia kuvattu vain sanatasolla  
	(n-grammimallit) tai sanakategoriatasolla (sanaluokat ja HMM)

  \item Sekventiaalisten riippuvuuksien lisäksi muunkinlaisia
	ilmiöitä, esim. rekursiivisia.

  \item Esim. 'The velocity of the seismic waves rises to\ldots'\\	
	P('waves rises') on hyvin pieni esim. sanaluokkiin perustuvalla 
	HMM-taggerilla, koska yksiköllistä verbimuotoa harvoin edeltää 
	monikollinen substantiivi (yleensä sitä edeltää yksiköllinen 
	substantiivi, verbin subjekti; ilmiötä kutsutaan nimellä
	 'verb agreement').
\end{myitemize}

\mynewpage
%----------------------------------------------------------------------

\mytopic{Motivaatio, jatkoa}{}

\begin{myitemize}

  \item Keskeinen havainto: yksittäisten sanojen sijaan riippuvuudet
        voidaan ehkä paremmin kuvata suurempien kokonaisuuksien välillä
       $\rightarrow$ oletetaan hierarkkinen rakenne myös lauseiden tai
       virkkeiden sisällä.  (Vastaava hierarkkisuus yleisemmällä tasolla: 
	dokumentti, kappale, lause, sana, kirjain, veto).

  \item Vastaavaa hierarkkisuutta myös muualla kuin kielessä,
  esim. konenäön hahmontunnistusongelmat, joihin myös voidaan soveltaa
  syntaktisia hahmontunnistusmenetelmiä.

%  \item Suomessa n-grammit ja muut sekventiaaliset mallit toimivat
%	kauttaaltaan huonommin (ei vain paikoitellen, kuten englannissa),
%	luultavasti johtuen suuremmista vapauksista sanajärjestyksen
%	valinnassa.
\end{myitemize}

\mynewpage
%----------------------------------------------------------------------

\mytopic{Lauseen hierarkkinen rakenne}{}

Seuraavassa on esimerkki 
lauseen sisäisestä hierarkkisesta rakenteesta (kirjan kuva
11.2). Voidaan ajatella että riippuvuus on tässä peräkkäiden
rakenne\-osien $NP_{SG}$ ja $VP_{SG}$ välillä.\\

\includegraphics[scale=0.8]{PCFG_1.png}

\mynewpage
%----------------------------------------------------------------------
\mysubslide{Mikä on PCFG}{}

CFG:n luonteva laajennus:  CFG, jonka sääntöihin on liitetty
laukeamistodennäköisyydet. [CFG = kontekstivapaa kielioppi]

PCFG on probabilististen kielioppien eräs alalaji, ts. vain eräs tapa
mallintaa hierarkkista rakennetta probabilistisesti. Tekemällä
erilaisia riippumattomuusoletuksia päädytään erilaiseen
malliperheeseen.

\mynewpage
%----------------------------------------------------------------------

\mytopic{PCFG:n osat}{}

PCFG koostuu seuraavista osista:

\begin{myitemize}

  \item terminaalisymbolien joukko,

  \item ei-terminaalisymbolien joukko, 

  \item joukko korvaussääntöjä $N^i \rightarrow \gamma^j$ jossa
  $\gamma^j$ on terminaali- ja\\
	 ei-terminaalisymboleista koostuva jono

  \item Kullekin säännölle ehdollinen laukeamistodennäköisyys:
        \begin{equation}
  	\sum_j P(N^i \rightarrow \gamma^j|N^i) = 1
	\end{equation}
\end{myitemize}

\mynewpage
%----------------------------------------------------------------------

\mytopic{Notaatiota}{}

\begin{tabular}{ll}
$G$          & kielioppi  \\
${\cal L}_G$  & kieli jonka kielioppi $G$ tuottaa\\
t	     & jäsennyspuu \\
tulostus(t)     & jäsennyspuun $t$ jäsentämä sanajono\\
$\{N^1,\ldots, N^n\}$ & ei-terminaalisymbolien aakkosto 
	($N^1$ on alkusymboli) \\
$\{w^1,\ldots, w^V\}$ & terminaalisymbolien aakkosto \\
$w_1\ldots w_m$       & jäsennettävä lause (sanajono) \\
$N_{pq}^j$  & ei-terminaalisymboli $N^j$ kattaa jonossa \\
            & positiot $p$:stä $q$:hun. \\
%$\alpha_j(p,q)$ & Ulkotodennäköisyydet \\
%$\beta_j(p,q)$ & Sisätodennäköisyydet \\
\end{tabular}

\mynewpage
%----------------------------------------------------------------------
\mytopic{Riippumattomuusoletukset}{}

PCFG:ssä korvaussäännön tn on ehdollinen ainoastaan sille,\\
missä ei-terminaalissa nyt ollaan, eli $N^i$.

Tarkastellaan tarkemmin riippumattomuusoletuksia, joita tässä
tehdään. 

\begin{myitemize}

  \item Rakenteellinen paikkariippumattomuus: 
	alipuun tn ei riipu siitä, missä osassa isompaa
	puuta alipuu sijaitsee (vrt. HMM:n ajallinen stationaarisuus).

  \item Leksikaalinen kontekstiriippumattomuus: alipuun tn ei
	riipu alipuuhun kuulumattomista kontekstin sanoista.

  \item Riippumattomuus esivanhemmista: Alipuun tn ei riipu siitä,
	mitä sääntöjä käyttäen alipuu generoitiin.

\end{myitemize}

\mynewpage
%----------------------------------------------------------------------
\mytopic{Huomioita probabilistisesta kieliopista}{}

\begin{myitemize}

  \item Antaa probabilistisen mallin kielen generoinnille.

  \item Arvioi kunkin jäsennyksen todennäköisyyden. Kattavissa
	kieliopeissa yhdelle lauseelle yleensä hyvin monta mahdollista
	jäsennystä, jopa tuhansia per lause.

  \item Prob. kielioppi (esim. PCFG-malliperhettä käyttäen opittu) ei
	yritäkään jakaa lauseita ei-kieliopillisiin ja
	kieliopillisiin. 'Virheelliset' lauseet vain ovat paljon
	epätodennäköisempiä.

  \item Jos dataa on riittävästi, PCFG:llä kieliopin oppiminen
	mahdollista ilman negatiivista evidenssiä (ei-kieliopillisia
	lauseita).

\end{myitemize}

\mynewpage
%----------------------------------------------------------------------
\mytopic{Peruskysymykset PCFG:lle}{}

\begin{myitemize}
  \item Lauseen todennäköisyyden laskeminen
  \item Todennäköisimmän jäsennyksen valinta lauseelle
  \item PCFG:n parametrien estimointi joko jäsennetystä (ohjattu
	oppiminen) tai jäsentämättömästä datasta (ohjaamaton oppiminen)
\end{myitemize}


\mynewpage
%----------------------------------------------------------------------
\mytopic{Chomskyn normaalimuoto}{}

Keskitytään tästedes kontekstivapaisiin kielioppeihin, jotka ovat
\emph{Chomskyn normaalimuodossa} eli säännöt ovat binäärisiä tai unaarisia:

$N^i \rightarrow N^j N^k$\\
$N^i \rightarrow w^j$

PCFG:n parametrien määrät ovat tällöin:\\

\begin{tabular}{ll}
$P(N^j \rightarrow N^r N^s| G)$   & Jos $n$ ei-terminaalia, $n^3$ parametria\\
$P(N^j \rightarrow w^k| G)$   & Jos $V$ terminaalia, $nV$ parametria
\end{tabular}

Kaikille $j$ pätee lisäksi:
\begin{equation}
\sum_{r,s} P(N^j \rightarrow N^r N^s) + \sum_k P(N^j \rightarrow w^j) = 1
\end{equation}
Tämä johtuu siitä että yo. parametrit ovat ehdollisia todennäköisyyksiä
ehdolla $N^j$.

\mynewpage
%----------------------------------------------------------------------
\mytopic{Chomskyn hierarkia kielille}{}

Yhteys-/kontekstivapaus on eräs kielen kompleksisuutta kuvaava taso. Chomsky
jakaa kielet seuraavanlaiseen kompleksisuushierarkiaan:
(Taulukko on kirjasta Jurafsky \& Martin, s. 479)

Tässä $A$ on yksittäinen ei-terminaalisymboli ja $\alpha,\beta$ ja
$\gamma$ ovat mitä tahansa terminaalien ja ei-terminaalien jonoja.

\begin{tabular}{|l|l|l|}
\hline
\bf Tyyppi & \bf Nimi & \bf Sääntörunko\\
\hline
0 & Turing-ekvivalentti & $\alpha \rightarrow \beta$ s.e. $\alpha \ne \epsilon$ \\
1 & Kontekstiherkkä     & $\alpha A \beta \rightarrow \alpha \gamma \beta$ s.e. $\gamma \ne \epsilon$ \\
2 & Kontekstivapaa      & $ A \rightarrow \gamma$                     \\
3 & Säännöllinen        & $ A \rightarrow x B$ tai  $A \rightarrow x$ \\
\hline
\end{tabular}

\mynewpage
%----------------------------------------------------------------------
\mytopic{Chomskyn hierarkia kielille, selitykset}{}

Tyyppi 0 vastaavat niitä
kieliä, joiden symbolijonot voidaan tuottaa (listata) Turing-koneella.
Ainoa rajoitus säännöille on, että ``tyhjästä ei voi nyhjästä''.

Kontekstiherkät kielet muuntavat symbolin toiseksi riippuen sen oikean-
ja vasemmanpuoleisesta kontekstista. Lisäksi nämä symbolit eivät voi
pelkästään vaan sääntöjen on myös tuotettava jotakin.

Kontekstivapaissa kielissä ei-terminaalisymboli voidaan korvata millä
tahansa ei-terminaalien ja terminaalien jonolla (mukaanlukien tyhjä
jono). Näitä toteuttavat esim. lauserakennekieliopit.

Säännölliset kielet ovat ekvivalentteja säännöllisten lausekkeiden
(regular expressions) kanssa. Ne voivat olla oikea- tai vasenkätisesti
lineaarisia. Niitä toteuttavat esim. äärelliset tilakoneet.

\mynewpage
%----------------------------------------------------------------------
\mytopic{Yhtäläisyys HMM:n ja PRG:n välillä}{}

PRG = probabilistic regular grammar, eli todennäköisyyksiä hyödyntävä
säännöllinen kielioppi.

Esimerkkilause \emph{P(John decided to bake a)} saisi luultavasti korkean
todennäköisyyden HMM:ssä (koska se on järkevä sanajono) mutta matalan
PRG:ssä (koska ei ole kokonainen lause).

PRG voidaan kuitenkin implementoida HMM:n avulla lisäämällä HMM:ään
alkutilan lisäksi lopputila, joka vastaa lauseen päättymistä.

\mynewpage
%----------------------------------------------------------------------
\mysubslide{Lauseen todennäköisyyden laskeminen}{}

\vspace{-3mm}
\begin{eqnarray}
P(w_{1m}|G) &=& \sum_t P(w_{1m},t|G)\\
	    &=& \sum_{t, tulostus(t)=w_{1m}} P(t|G)g
\end{eqnarray}
jossa $t$ on kieliopin $G$ säännöillä tuotettu jäsennyspuu lauseelle
$w_{1m}$.

\mynewpage
%----------------------------------------------------------------------
\mytopic{Esimerkki lauseen todennäköisyyden laskemisesta}{}

Oletetaan että $t$:n aikaansaamiseksi sovellettiin $G$:n sääntöjä
$s^i$,$s^k$, ja $s^a$ ja tulostuksena oli sanajono $w_{pq}$. Tällöin 
\begin{eqnarray*}
P(t|G) &= & P(s^i s^k s^a) = P(s^i, s^k, s^a) \\
       & = & P(s^a|s^i,s^k) P(s^k|s^i) P(s^i) \\
       & = & P(s^a) P(s^k) P(s^i)
\end{eqnarray*}

Ylläolevassa kaikki tn:t ovat ehdollisia kieliopille $G$, joten tämä
on jätetty merkitsemättä.

Eli $P(w_{pq}|G)$ on niiden $G$:n sääntöjen todennäköisyyksien tulo joita $t$:n
muodostamiseksi sovellettiin.

Yleisessä tapauksessa ei kannata (laskennallisista syistä) summata yli
kaikkien mahdollisten jäsennysten. Samoin kuin HMM:llä
mahdollisia 'polkuja' on liikaa. Ongelma voidaan
paloitella osaongelmiksi, ratkaista palat kerrallaan ja 
vierittää palojen tuloksia eteenpäin.

\mynewpage
%----------------------------------------------------------------------
\mysubslide{Inside-algoritmi}{}

Inside-algoritmi vastaa HMM:ien forward-algoritmia ja sillä
voidaan laskea lauseen todennäköisyys.

$b_j(p,q)$ tarkoittaa $N_j$:n alla olevan alipuun, 
joka kattaa sanajonon $w_{pq}$, tn:n laskemista

Perustapaus: lasketaan tn, kun muunnetaan ei-terminaali terminaaliksi:\\
$b_j(k,k) = (w_k |N^j_kk,G)\\$

Induktioaskel: tn, kun muunnetaan ei-terminaali kahdeksi ei-terminaaliksi: \\
oletetaan sääntö $N^j \rightarrow N^r N^s$ ja jonon 
jako $w_{pq} =w_{pd} w_{dq}$ 

Tällöin $b_j(p,q) = \sum_{r,s} \sum_{d=p}^{q-1} b_r(p,d) \times b_s(d+1,q) $ 

Eli samalla, kun puu jakautuu kahdeksi osapuuksi, jono $w_{pq}$
jaetaan kahtia, ja rekursiivisesti sovelletaan induktioaskelta
kumpaankin osapuuhun. 

Lisäksi summataan yli kaikkien mahdollisten jonon jakojen ja
kaikkien ei-terminaalisymbolien nimien, jotka voidaan muuntaa $N^j$:stä
kieliopissa $G$.

Inside-todennäköisyydet voidaan laskea tehokkaasti alhaalta ylös (bottom-up).

\mynewpage
%----------------------------------------------------------------------
\mysubslide{Todennäköisimmän jäsennyksen etsiminen}{}

Todennäköisimmän jäsennyksen etsimiseen (samoin kuin HMM:llä)
voidaan soveltaa Viterbi-tyypistä algoritmia.

Tämä on kompleksisuudeltaan ${\cal O}(n^3 m^3)$ jossa $m$ on jonon
pituus ja $n$ ei-terminaalien lukumäärä kieliopissa.

\mynewpage
%----------------------------------------------------------------------
\mysubslide{PCFG:n estimointi}{}

Annettuna sääntöjoukko:

Tapaus 1: Jokin olemassaoleva CFG, joka hyväksyy koko aineiston.

Tapaus 2: Kaikkien mahdollisten sääntöjen joukko.

Tapaus 3: Kaikkien mahdollisten sääntöjen joukko paitsi, että
	  oletetaan valmiiksi jotakin rakennetta, esim. jokin
	  ei-terminaalisymbolien osajoukko varattu generoimaan pelkästään
	  terminaalisymboleja.

\mynewpage
%----------------------------------------------------------------------
\mytopic{Estimointi, kun käytettävissä jäsennettyä aineistoa}{}

Annettuna sääntöjoukon Tapaus 1 sekä 'puupankki' (\textbf{treebank})
eli suuri määrä jäsennettyä aineistoa.

Lasketaan suoraan sääntöjen soveltamiskertoja ja normalisoidaan.\\
ML-estimaatti:
\begin{equation*}
P(\alpha \rightarrow \beta) = \frac{Count(\alpha \rightarrow \beta)}{Count(\alpha)}
\end{equation*}

\mynewpage
%----------------------------------------------------------------------
\mytopic{Estimointi, kun käytettävissä vain jäsentämätöntä aineistoa}{}

\textbf{Sääntöjoukon tapaus 1:}

Jäsennetään aineisto annetulla CFG:llä ja tämän jälkeen kuten edellä.

Käytännössä jäsennykset moniselitteisiä: yhden jäsennyksen sijaan
painotetaan eri jäsennyksiä niiden tn:llä.

\textbf{Sääntöjoukon tapaukset 2 ja 3:}

Kuten HMM:llä, sovelletaan erästä EM-algoritmia,
Inside-Outside-algoritmia, joka muistuttaa
forward-backward-algoritmia.

\mynewpage
%----------------------------------------------------------------------
\mytopic{Estimointialgoritmi}{}

Mallin ML-estimointi: maksimoidaan datan todennäköisyys. 

Parametreja ovat sääntöjen tn:t.

Perusperiaate:
\begin{myitemize}
  \item Initialisointi esim. satunnaisilla parametreilla.
  \item Vaihe 1: Sovelletaan tämänhetkistä mallia (PCFG:tä) 
        datan tn:n laskemiseen ja
	samalla pidetään kirjaa siitä, kuinka paljon mitäkin sääntöä
	käytettiin.
  \item Vaihe 2: Päivitetään sääntöjen tn:t vaiheen 1 kirjanpidon perusteella.
  \item Toistetaan vaiheita 1 ja 2.
\end{myitemize}

\mynewpage
%----------------------------------------------------------------------
\mytopic{Ongelmia probabilistisen kieliopin ei-ohjatussa oppimisessa}{}

\begin{myitemize}
  \item Ongelman kompleksisuus ja tästä johtuva estimoinnin
  hitaus. Jokaiselle lauseelle jokainen iteraatio on
  kompleksisuudeltaan ${\cal O}(m^3 n^3)$, jossa $m$ on lauseen pituus
  ja $n$ ei-terminaalien määrä lauseessa.

  \item Kustannusfunktion lokaalit minimit ovat hyvin
  todennäköisiä. Esim. yksinkertaisella keinotekoisella PCFG:stä
  generoidulla aineistolla estimoitaessa 300 eri ajolla päädyttiin
  jokaisella eri lokaaliin minimiin. Eli initialisoinnilla on hyvin
  suuri vaikutus.

  \item Mallien koko kasvaa helposti suureksi, koska mallin kokoa ei
  kustannusfunktiossa mitenkään huomioida. Ratkaisu: kustannusfunktion
  vaihto sellaiseksi, joka huomioi myös mallin koon. Perusteltuja
  lähestymistapoja tähän ovat MDL ja Bayesilainen estimointi.

  \item Ei-terminaaleilla, joita malli oppii, ei välttämättä ole mitään
  tekemistä lingvistisen teorian ei-terminaalien kanssa. 

\end{myitemize}

%Eli, vaikka PCFG:n estimointi jäsentämättömästä datasta on
%periaatteessa mahdollista, on se käytännössä toistaiseksi
%hankala ongelma.

\mynewpage
%----------------------------------------------------------------------
\mysubslide{(P)CFG:n ongelmia}{}

\begin{myitemize}

\item Säännön soveltamisen todennäköisyys ei riipu siitä, missä kohtaa
 koko puuta alipuu sijaitsee

\item PCFG ei huomioi leksikaalista kontekstia

\end{myitemize}

\mynewpage
%----------------------------------------------------------------------
\mytopic{Säännön soveltamisen todennäköisyys ei riipu siitä, missä kohtaa
 koko puuta alipuu sijaitsee.}{}

CFG:n riippumattomuusoletukset $\rightarrow$ säännön soveltaminen
riippuu vain senhetkisestä ei-terminaalisymbolista.
Kuitenkin esim. englannissa
pronominilausekkeen esiintymistn
riippuu voimakkaasti sijainnista koko lauseessa:

Väitelauseiden subjektina pronominin P=91\% (loput 9\%
leksikaalisia), kun taas objektina P=34\% (loput 66\% leksikaalisia).

Usein lauseen alkupäässä
viitataan siihen mitä jo tiedetään aiemman keskustelun pohjalta
ja loppupäässä tuodaan ilmi
ko. asiaa koskevaa uutta tietoa:

\emph{Presidentti Tarja Halonen} aloitti kautensa maakuntakierroksella. \\
\emph{Hän} tapasi ensin Joensuun kaupungin johtavia virkamiehiä ja jatkoi \ldots

Ongelma ratkeaisi, jos P(NP $\rightarrow$ Pronomini) ja P(NP
$\rightarrow$ Nomini) ehdollistettaisiin sillä, onko NP
subjekti- vai objektipositiossa. Mutta juuri tätä eivät PCFG:n
riippumattomuusoletukset salli.

\mynewpage
%----------------------------------------------------------------------
\mytopic{PCFG ei huomioi leksikaalista kontekstia}{}

Englannissa prepositiolausekkeen kiinnittymisongelma:\\
'I shot an elephant in my pyjamas'\\
'USA sent more than 10,000 soldiers into Afghanistan'\\

Sotilaiden lähettämisen tapauksessa leksikaalinen tieto eli että
kyseessä on send-verbi ja into-prepositio auttavat disambiguoimaan
esimerkin. Elefantti-esimerkkiin saatetaan tarvita maailmantietoa:
elefantit eivät yleensä käytä yöpukuja paitsi saduissa.

Suomessa vastaavanlainen monitulkintaisuus:

'Ammuin elefantin yöpuvussa'\\
\hspace{2cm} $\rightarrow$ Ammuin elefantin jolla oli päällään yöpuku. \\
\hspace{2cm} $\rightarrow$ Ammuin yöpukusillani elefantin. \\

Vastaava ilmiö: Koordinaatiomonitulkintaisuus:

'dogs in houses and cats' $\rightarrow$\\
 \hspace{2cm} 1. 'dogs in [NP houses and cats]'\\
 \hspace{2cm} 2. '[NP dogs in houses] and cats'

Semanttinen preferointi: koirat eivät mahdu kissoihin, 
joten 2. vaihtoehto olisi oikea.

PCFG:ssä kuitenkin ylläoleviin lukutapoihin sovellettavat säännöt ovat
rakenteisesti identtisiä, eli ei kykene preferoimaan vaihtoehtoja.

\mynewpage
%----------------------------------------------------------------------
\mytopic{Joitain havaintoja toimivuudesta englannille:}{}

\begin{myitemize}

  \item PCFG:n ennustuskyky tavallisesti parempi kuin HMM:n, kun sama määrä
	parametrejä.

  \item Englannille PCFG yleensä huonompi kielimalli kuin
        $n$-grammimalli. Johtuu siitä, ettei kontekstin leksikaalista tietoa
        huomioida (riippumattomuusoletukset).

  \item Puhdas PCFG ei hyvä, mutta ehdollistaminen leksikaalisella
	tiedolla tai puun rakennekontekstilla voi parantaa tulosta.

%  \item Jäsennys suosii ei-terminaalisymboleita joilla pieni määrä
%        vaihtoehtoisia laajennuksia suuresti haarautuvien yli, koska
%        suuresti haarautuvilla kunkin yksittäisen haaran tn on pieni.  (Tämä
%        bias johtuu osaksi siitä että jäsennettäessä etsitään yksi ainoa todennäköisin
%        polku ja valitaan se ko. lauseen jäsennykseksi).
\end{myitemize}

\mynewpage
%----------------------------------------------------------------------
\mytopic{Onko PCFG aito kielimalli?}{}

Jotta PCFG olisi aito kielimalli, täytyisi päteä:\\
	 $\sum_{w \in {\cal L}} =\sum_t P(t) =1 $\\
eli kieliopin tuottamien lauseiden saaman todennäköisyysmassan pitäisi
olla 1.

Kuitenkin tämän toteutuminen edellyttää, että mallissa ei ole
mahdollisuutta äärettömään rekursioon. Jos ääretön rekursio
on mahdollista, osa tn-massasta katoaa sinne, eikä päädy koskaan kielen
lauseiksi.

\mynewpage
%----------------------------------------------------------------------
\mytopic{Esimerkki}{}

Esimerkiksi kielioppi:\\
S $\rightarrow$ raparperi,  P=1/3\\
S $\rightarrow$ S S,   P = 2/3

\begin{equation*}
P(\text{raparperi}^n) = \sum_n (2/3)^{n-1} ( 1/3)^n = 1/2 \text{ kun } n \rightarrow \infty
\end{equation*}
Eli puolet jäsennysten tn-massasta katoaa äärettömään rekursioon.
Kyseessä on \emph{epäkonsistentti} tn-jakauma.

\mynewpage
%----------------------------------------------------------------------
\mytopic{Ongelmattomia tapauksia}{}

Todennäköisyysmassan 
katoaminen rekursiossa ei ole ongelma, kun

\begin{myitemize}

  \item etsitään todennäköisin jäsennys annetulle lauseelle,

  \item vertaillaan kahden lauseen tn:ää annetussa kieliopissa tai

  \item estimoidaan PCFG:n parametrit jäsennetystä 
        korpuksesta (Chi \& Geman, 1998)

\end{myitemize}

\mynewpage
%----------------------------------------------------------------------
\mytopic{Ongelmallisia tapauksia}{}

Todennäköisyysmassan katoaminen on ongelma,
kun tehdään vertailuja eri kielioppien/kielimallien välillä, siis kun:

\begin{myitemize}

  \item lasketaan jonkin lauseen tn  tässä kieliopissa ja verrataan 
        tn:ään jossain
	toisessa kieliopissa (jossa tn-massa kokonaan tai sen erisuuri osuus
	kieliopin lauseilla),

  \item estimoidaan PCFG:n parametrit ohjaamattomasti toisin
        sanoen jäsentämättömästä 
        korpuksesta, tai

  \item tehdään mallin valintaa eli vertaillaan eri CFG:n sääntöjoukkoja

\end{myitemize}

\mynewpage
%----------------------------------------------------------------------
\mysubslide{Probabilistinen leksikalisoitu CFG}{}

Leksikalisointi tarkoittaa sanatiedon ottamista huomioon.

Menetelmä:

\begin{myitemize}

   \item Jokaiseen ei-terminaalisymboli $N^i$ jäsennyspuussa $t$ liitetään
 	 ko. alipuun 'pääsana' (head)  (Charniak 1997, Collins 1999)

   \item CFG:ssä jokaisen säännön kohdalle merkitään, 
         mikä säännön oikealla puolella
	 olevista symboleista on 'päätytär' ts. sisältää pääsymbolin 
	 (esim. NN on NP:n päätytär).

   \item Päätyttären valinta suoraviivaista oppikirjalauseille, mutta
	 yleisesti ottaen hankalaa (lingvistiikan kirjat saattavat
	 spesifioida säännöt tämän tekemiseen kyseiselle kielelle).

\end{myitemize}


\mynewpage
%----------------------------------------------------------------------
\mytopic{Puuesimerkki}{}

\includegraphics[scale=0.45]{PCFG_2.png}


\mynewpage
%----------------------------------------------------------------------
\mytopic{Attribuuttikieliopeista}{}

\begin{myitemize}

   \item Kielioppia, jossa jokaisella ei-terminaalinoodilla on myös jokin 
	terminaalisymboliarvo, kutsutaan myös \emph{attribuuttikieliopiksi}.

   \item PCFG:ssä jokaista päätyttären mahdollista arvoa on varten oma
	 todennäköisyys (ts. oma sääntö). Periaatteessa siis esim:

$VP(dumped) \rightarrow VBD(dumped) NP(sacks) PP(into) [3\times 10^{-10}]$\\
$VP(dumped) \rightarrow VBD(dumped) NP(cats) PP(into) [8\times 10^{-11}]$\\
$VP(dumped) \rightarrow VBD(dumped) NP(hats) PP(into) [4\times 10^{-10}]$\\
$VP(dumped) \rightarrow VBD(dumped) NP(sacks) PP(above) [1\times 10^{-12}]$

   \item Käytännössä mikään aineisto ei riitä näin valtavan mallin estimointiin 
	$\rightarrow$ tehdään taas tiettyjä riippumattomuusoletuksia, joiden avulla
	ryhmitellään (sidotaan) osa todennäköisyyksistä samoiksi.

   \item Esim. voidaan käyttää leksikalisointia vain säännön vasemmalla puolella:\\
	$VP(dumped) \rightarrow VBD$ $ NP$ $PP$

   \item Eri tilastolliset jäsentimet eroavat toisistaan siinä, minkälaisia
	 riippumattomuusoletuksia niissä tehdään.

   \item Suuremmasta sääntömäärästä johtuen leksikalisoidun PCFG:n 
	estimointi ohjaamattomalla (ilman jäsennettyä dataa) 
 	oppimisella käytännössä mahdotonta, ainakin toistaiseksi.

\end{myitemize}
\end{document}
%----------------------------------------------------------------------



%%% Local Variables:
%%% eval: (ispell-minor-mode 0)
%%% eval: (flyspell-mode 0)
%%% mode: lazy-lock
%%% m<ode: fast-lock
%%% End:
