01_uvod.tex

Metode učenja pretraživanja \engla{learning to search}{\lts{}} novija su
pojava u strojnom učenju. U zadnjih deset godina istraživači su metode
primijenili na probleme u različitim granama računarske znanosti, uključujući i
obradu prirodnog jezika. Vrlo uspješna primjena vezana je uz probleme gdje se
učenje i zaključivanje odvija na primjerima koji sadrže određenu strukturu.
Učenje pretraživanja spada u metode strukturnog učenja \engl{structured
learning} ili predviđanja strukturiranog izlaza \engl{structured output
prediction}. U obradi prirodnog jezika neki od problema koji uključuju
predviđanje strukturiranog izlaza su označavanje vrste riječi
\engl{part-of-speech tagging}, ovisnosno parsanje \engl{dependency parsing},
prepoznavanje imenovanih entiteta \engl{named entity recognition}, prepoznavanje
i praćenje entiteta \engl{entity detection and tracking}, razrješavanje
koreference \engl{coreference resolution}, izlučivanje relacija između entiteta
\engl{entity relation extraction}, inkrementalno prevođenje \engl{incremental
translation}, inkrementalno odgovaranje na pitanja \engl{incremental question
answering} i mnoštvo drugih. Ostale primjene metoda učenja pretraživanja su
aktivno i interaktivno učenje \engl{active and interactive learning}, algoritmi
grananja i granice \engl{branch-and-bound}, problemi u robotici, segmentacija
slike \engl{image segmentation}, predviđanje sekundarne strukture proteina
\engl{protein secondary structure prediction} i dr.

Postojanost razvijenog matematičkog formalizma za te metode jedan je od razloga
raznolike primjene. Metode učenja pretraživanja vuku inspiraciju iz područja
podržanog učenja \engl{reinforcement learning} \citep{sutton1998reinforcement},
gdje je zadatak sustava naučiti dobru \emph{politiku}. Politika se uči
opetovanim izvršavanjem zadatka i ažuriranjem modela s obzirom na pojedinačni
ishod. Kod učenja pretraživanja cilj je dodatno iskoristiti prisutne podatke,
dok su ti podaci zanemareni ili se postepeno izgrađuju kod primjene podržanog
učenja. Matematički aparat koji je iskorišten da bi objasnio podržano učenje i
redukcije u strojnom učenju \engl{machine learning reductions} omogućava otkriće
dobrih teoretskih jamstava metoda učenja pretraživanja. U ovom radu obrađuje se
pitanje kako reducirati združeno učenje i predviđanje \engl{joint learning and
prediction} na jednostavniji problem. Redukcije u području strojnog učenja
slične su redukcijama u drugim područjima računarske znanosti. Naposljetku,
glavni je razlog široke primjene vrlo jednostavna implementacija koja
iskorištava svojstvo modularnosti koje je prirodno u procesu redukcija (za
implementaciju višerazredne klasifikacije potreban je dobar binarni
klasifikator). Implementacija je ostvarena u brzom sustavu za strojno učenje
zvanom Vowpal
Wabbit,\footnote{\url{https://github.com/JohnLangford/vowpal_wabbit/wiki}} a
radni okvir \lts{} omogućava da u vrlo malo linija programskog koda
istraživač može napisati algoritam učenja i zaključivanja za specifičan problem.
Slični sustavi koji implementiraju algoritme učenja i zaključivanja za
vjerojatnosne grafičke modele zahtijevaju puno više linija programskog koda i
vjerojatnija je pojava pogrešaka, a nemodularna priroda onemogućuje njihovo
izbjegavanje. Pokušaj generalizacije i iskorištavanja programskog koda
općenitijim metodama učenja i zaključivanja kod vjerojatnosnih grafičkih modela
rezultirao je pojavom vjerojatnosnih programskih jezika \engl{probabilistic
programming languages}, ali brzina učenja i zaključivanja nije ni blizu
algoritama \lts{}.

Ovaj rad nudi sažet pregled metoda učenja pretraživanja i njihovu
primjenu na probleme obrade prirodnoga jezika. Uz njihovu matematičku podlogu
obrađene su i usporedbe s ostalim metodama strojnog učenja koje se uspješno
primjenjuju na istim problemima. Dani su i odgovori na prijašnja postavljena
pitanja te opisi konkretne implementacije koji pažljivije argumentiraju
prednosti nad ostalim pristupima.
U poglavlju \ref{ch:pregled} dan je pregled glavnih pristupa strukturnom
učenju i predviđanju te su opisane njihove prednosti i mane.
U poglavlju \ref{ch:l2s} dan je pregled glavnih metoda učenja pretraživanja
u koji je uključen osvrt na redukcije u strojnom učenju te su definirani
potrebni pojmovi vezani uz okvir učenja pretraživanja.
U poglavlju \ref{ch:applications} dan je opis primjena metoda učenja
pretraživanja na konkretne probleme u obradi prirodnog jezika. Odabrani problemi
služe za razvijanje osjećaja o tome što je moguće raditi u okviru učenja
pretraživanja. Dane su i usporedbe s drugim modelima koji su primijenjeni na
iste zadatke da bi se istaknula superiornost metoda \lts{}.
U poglavlju \ref{ch:evaluation} dano je vrednovanje modela za zadatke
razvijene u ovom radu te opis implementacije algoritama učenja i zaključivanja.
Tri različita zadatka:
\begin{inlinelist}
  \item označavanje vrste riječi,
  \item ovisnosno parsanje i
  \item združeno označavanje i parsanje.
\end{inlinelist}
Uz tri osnovna zadatka obrađene su njihove varijante i različiti pristupi na
istom problemu.