Statistično strojno prevajanje (SMT), kot je definirano v \citep{alonazian1999}, predstavlja eno najbolj raziskanih področij CBMT v zadnjih letih. SMT temelji na statističnih modelih, katerih parametri so izpeljani iz opazovanja dvojezičnih vzporednih korpusov. Statistično strojno prevajanje na osnovi dreves izpeljav (\gls{statistical machine translation by parsing -- SMTbyP}), kot je opisano v \citep{melamed04a}, predstavlja podmnožico SMT, v kateri so parametri statističnih modelov naučeni s pomočjo skladenjsko označenih dvojezičnih vzporednih korpusov.

Najpomembnejša prednost sistemov SMTbyP v primerjavi s sistemi SMT je v zmožnosti obvladovanja rekurzivnih struktur v povedih; primer so vrinjeni stavki. Pri učenju modelov in pri samem prevajanju (uporabi modelov) so uporabljeni statistični modeli razčlenjevanja besedila (\gls{statistical parsing models}). Večina statističnih modelov razčlenjevanja besedila, primera sta \citep{collins03} in \citep{charniak00}, je naučena na skladenjsko označenih dvojezičnih poravnanih korpusih (\gls{treebank}s); primer takšnega korpusa je Penn treebank \citep{marcus94}. Manj uporabljeni jeziki (\gls{less used languages}) takšnih korpusov nimajo.

Metoda, predstavljena v nadaljevanju poglavja, omogoča izdelavo samostojnega sistema za strojno prevajanje tipa SMTbyP, medtem ko se ostala poglavja osredotočajo na hitro izdelavo sistemov za strojno prevajanje na osnovi pravil. Najpomembnejši razlog za predstavitev te metode je možnost uporabe takšnih sistemov v primeru nezmožnosti prevodov s pomočjo sistemov na osnovi pravil. Torej nov sistem uporabimo kot pomožni sistem.

\section{Motivacija}
\label{section:smtbyposnove}
Osnovna hipoteza, na kateri temelji predstavljena lastna metoda \citep{vicic2006}, je, da oznake besednih vrst, PoS del oznak MSD, vsebujejo dovolj skladenjskih informacij, ki omogočajo abstrakcijo besed iz učnega korpusa. Statistični model, naučen na besedah korpusa, je modeliran ločeno. Prostor iskanja se z uporabo oznak besednih vrst namesto pravih besed močno zmanjša; tako potrebujemo manj podatkov za učenje učinkovitih prevajalnih modelov. Niz oznak besednih vrst lahko sestavimo iz izvornega označenega besedila, tako da enostavno združimo dele MSD-oznak, ki so pripisane besedam povedi. Takšni nizi predstavljajo liste v drevesih izpeljav, če ne upoštevamo dejanskih besed.

SMTbyP gradi drevo izpeljav\index{drevo izpeljav} izvorne povedi in ga poravna z drevesom izpeljav v ciljnem jeziku. Poravnave so naučene na učni množici, ki je sestavljena iz skladenjsko označenih povedi. Učenje poravnav išče dele drevesnih struktur, ki se pogosto pojavljajo v parih \emph{izvorno skladenjsko označeno drevo -- ciljno skladenjsko označeno drevo}.

V svojem pristopu uporabljamo iste algoritme z eno razliko: predstavljena metoda uporablja poravnave med deli nizov oznak besednih vrst izvorne povedi in deli dreves izpeljav v ciljnem jeziku. Tako lahko metodo uporabimo tudi za manj uporabljene jezike. V učnem korpusu, ki vsebuje pare oblike \emph{poved v izvornem jeziku -- poved v ciljnem jeziku}, z oznakami MSD označimo izvorne povedi. Iz ciljnih povedi pa zgradimo skladenjsko označena drevesa. Poravnave gradimo s statističnim pristopom, dele nizov oznak besednih vrst poravnamo z deli skladenjsko označenih dreves, če se dovolj pogosto pojavljajo v učnih primerih. Slika \ref{fig:smtbypalignment} kaže primer takšne poravnave. 

\section{Predstavitev metode}
\label{section:smtbypmetoda}
Večina metod statističnega strojnega prevajanja \citep{brown1993,melamed04a} je jezikovno neodvisna, prevajalne metode delujejo dvosmerno, omogočajo prevajanje iz izvornega v ciljni jezik in obratno. Jezikovna neodvisnost je omogočena z indukcijo prevajalnega znanja iz vzporednih podatkov brez dodatnega jezikovnega znanja.

Osnovna učna množica naše metode \citep{vicic2006} je prav tako poravnan vzporedni dvojezični korpus. Metoda obe predstavljeni splošnosti oziroma neodvisnosti zanemarja, saj zahteva jezik s standardizirano drevesnico v ciljnem jeziku, tj. zbirko skladenjsko označenih povedi (\gls{treebank}), in jezik s solidnim označevalnikom MSD za izvorni jezik. V prvo skupino sodi le peščica največjih svetovnih jezikov oziroma jezikov, ki so dobro podprti z jezikovnimi tehnologijami, v drugo skupino pa veliko večja množica jezikov, saj je razvoj označevalnika MSD precej manjši problem. Metoda je razdeljena na dva dela, in sicer
\begin{itemize}
\item učenje povezav med deli nizov oznak besednih vrst izvornih povedi in deli izdelanih dreves izpeljav ciljnega jezika;
\item preiskovanje naučenih primerov iz prvega dela in izdelava množice fiksne velikosti najboljših kandidatov ciljnih prevodov\index{prevod} (n-best-set).
\end{itemize}

\subsection{Učenje povezav med oznakami in drevesi}
\label{section:smtbypucenjepovezav}
Prevajalni model je naučen na dvojezičnem vzporednem korpusu. Korpus je sestavljen iz povedno poravnanih delov izvornega in ciljnega jezika, kot je prikazano na sliki \ref{fig:smtbyptrainingdata}.

Standardni algoritem\index{algoritem} SMTbyP gradi drevo izpeljav\index{drevo izpeljav} iz izvorne povedi in ga poravna (poišče skupne točke) z ustreznim drevesom izpeljav v ciljem jeziku. Besede so modelirane v posebnem statističnem modelu, pri čemer lahko uporabimo praktično poljuben model poravnave posameznih besed (word-by-word alignment model).

Naš pristop je v primerjavi z osnovnim različen le v akcijah, ki vključujejo izvorno poved, saj metoda izhaja iz dejstva, da za izvorni jezik ne obstaja dovolj dober algoritem za skladenjsko razčlenjevanje povedi. Vsak par povedi iz učnega dela korpusa je obravnavan samostojno. Ciljna poved je razčlenjena s Collinsovim razčlenjevalnikom \citep{collins03}, ki je bil naučen na skladenjsko označenem korpusu ,,The Penn Treebank'' \citep{marcus94}; rezultat razčlenjevanja je drevo izpeljav\index{drevo izpeljav} z izračunano stopnjo zaupanja (\gls{confidence score}). Primer drevesa izpeljav je predstavljen na sliki \ref{fig:smtbyptrainingdata}.
\begin{figure}[ht]
\centering
\includegraphics[width=1\textwidth]{smtbyptrainingdata.eps}
\caption{\small Učni podatki: oblikoskladenjsko označen korpus in drevo izpeljav, izdelano na podlagi iste povedi. Drevo izpeljav je izdelano le za angleški del poravnanega para, pri slovenskem delu uporabimo le oznake besedilne vrste.}
\label{fig:smtbyptrainingdata}
\end{figure}

Drevesa izpeljav so sestavljena iz besed v listih, sledijo oznake besednih vrst na prvem nivoju. Oznake besednih vrst so združene v frazah, ki tvorijo preostale nivoje do vrhnjega. Izpuščanje besed v drevesih izpeljave na količino informacij s stališča skladnje skoraj ne vpliva. Notranja vozlišča predstavljajo simbole slovnice.

Skladenjski razčlenjevalnik za izvorni jezik ne obstaja; izvorna poved je oblikoskladenjsko označena, v našem testnem primeru smo uporabili že vnaprej pripravljen in označen korpus ,,1984'', oznake besednih vrst so bile pridobljene iz korpusa (prvi deli oznak MSD). Opisano zaporedje izdela pare oblike, razvidne iz primera a) na sliki \ref{fig:smtbypexamples}.

\begin{figure}[h!]
\begin{enumerate}
\item[a)] <izvorna poved, ciljna poved, izvorne oznake besednih vrst, ciljno drevo izpeljav, stopnja zaupanja za ciljno drevo izpeljav>
\item[b)] <izvorna poved, ciljna poved, izvorne oznake besednih vrst, ciljno drevo izpeljav, poravnava, stopnja zaupanja za ciljno drevo izpeljav, točkovanje poravnave>
\item[c)] <Tabla je umazana, the board is dirty, SGP, DSGP, (S (SF (D)(S))(GF (Gp)(P))), binarni podatki, 0.786, 0.354>
\end{enumerate}
\caption{\small Delni podatki po stopnjah učenja: a) začetni učni podatki; b) končni podatki s poravnavami, ki so točkovane; c) primer s slike \ref{fig:smtbyptrainingdata}, predstavljen kot končni podatki s primera b), povezave so v binarni obliki.}
\label{fig:smtbypexamples}
\end{figure}

V naslednji fazi so povezane oznake besednih vrst za vsako poved izvornega jezika z notranjimi vozlišči drevesa izpeljav. Algoritem \ref{alg:alignmentalgorithm} poišče pokritje ujemanj med izvornim nizom besednih vrst in najnižjim nivojem drevesa izpeljav, primer poravnave je prikazan na sliki \ref{fig:smtbypalignment}.

\begin{algorithm}[h!]
\begin{quote}
\begin{algorithmic}
\ForAll{$par$ \emph{in} $povedi$} \Comment{vsak par povedi <izvorna,ciljna>}
 \State $izvorneOznake \gets par.izvorna.MSD$;
 \State $ciljnoDrevoIzpeljav \gets par.ciljna.drevo$;
 \While {$izvorneOznake.length \ge 0$}
  \State $a \gets najdaljši podniz izvorneOznake$
  \State poišči ujemanje med $a$ in najnižjim nivojem $ciljnoDrevoIzpeljav$
  \State plezaj po $ciljnoDrevoIzpeljav$ do vozlišča $v$, ki še vključuje celotno ujemanje
  \State $ujemanja \gets a + v$
 \EndWhile
\EndFor
\end{algorithmic}
\label{alg:alignmentalgorithm}
\end{quote}
\caption{\small Algoritem poišče pokritje ujemanj med izvornim nizom besednih vrst in najnižjim nivojem drevesa izpeljav, v katerem so prav tako zapisane besedne vrste. Po drevesu se sprehajamo proti korenu, dokler je še zadoščeno kriterijem poravnave ter dokler vozlišče drevesa ne naslavlja celotnega podniza besednih vrst ciljnega jezika, ki je poravnan s trenutnim izvornim podnizom. Postopek ponavljamo do celotnega pokritja izvornega niza besednih vrst.}
\end{algorithm}

Poravnave so točkovane glede na izbrana pravila\index{pravilo}, ki so uporabljena pri izdelavi poravnav (vsaka skupina pravil\index{pravilo} ima svojo težo). Končni izdelek je par, prikazan na sliki \ref{fig:smtbypalignment}.

\begin{figure}[h!]
\centering
\includegraphics[width=1\textwidth]{smtbypalignment.eps}
\caption{\small Primer poravnave oznak besednih vrst z drevesom izpeljav.}
\label{fig:smtbypalignment}
\end{figure}

\subsection{Prevajanje}
\label{section:smtbypprevajanje}
V tej fazi se odvija prevod\index{prevod} vhodne izvorne povedi v poved v ciljnem jeziku. Vhodna poved, poved, ki jo prevajamo, je oblikoskladenjsko označena. Iz teh oznak izberemo le besedne vrste in sestavimo iskalni niz. Algoritem poišče niz oznak besednih vrst v izvornem delu učnih podatkov (za vsako poved). Rezultati so ocenjeni v skladu z uporabljeno iskalno metodo:
\begin{itemize}
\item \emph{točno ujemanje}; popolno ujemanje izvornega niza s ciljnim nizom. Ta metoda je ocenjena brez penalizacije.
\item \emph{ujemanje podobnih nizov}; izvorni in ciljni niz se lahko razlikujeta le za vnaprej določeno uteženo Levenshteinovo razdaljo \citep{levenshtein1965}. Penalizacija je odvisna od utežene Levenshteinove razdalje.
\item \emph{ujemanje podnizov}; ujemanje izvornega niza z več nizi ciljnega korpusa oziroma ujemanje izvornega dela s podnizom ciljnega niza. Penalizacija je odvisna od števila podnizov in je bila določena le na osnovi majhnega empiričnega testiranja.
\end{itemize} 

Metode so točkovane; osnovno točkovanje je bilo empirično določeno, uporabnik ga lahko spreminja s parametri. Rezultat iskanja je množica najboljših n-teric.

V zadnjem koraku metode se za izdelavo kandidata za prevod\index{prevod} samostojno uporablja vsak zapis. Besede ciljnega drevesa izpeljave so napolnjene prek poravnav z izvornimi oznakami besednih vrst in posredno z izvornimi besedami. Izvorne besede so prevedene s pomočjo modela za neposredni prevod\index{prevod} besed (word-by-word model).

Prevodi so točkovani s pomočjo točkovanj posameznih faz prevajalnega procesa in pomnoženi z verjetnostjo, da kandidat za prevod\index{prevod} sodi v ciljni jezik po statističnem jezikovnem modelu ciljnega jezika; v našem primeru smo uporabili jezikovni model \citep{clarkson1}. Kot končni prevod\index{prevod} je izbran najbolje točkovan kandidat.