-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path19_primjena_oznacavanje_vrste_rijeci.tex
119 lines (111 loc) · 7.01 KB
/
19_primjena_oznacavanje_vrste_rijeci.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
Označavanje vrste riječi jedan je od jednostavnijih problema u obradi prirodnog
jezika i shodno tome ima vrlo jednostavnu implementaciju u okviru učenja
pretraživanja. Problem je ilustriran na slici \ref{fig:postagging}. Za rečenicu
u nekom jeziku (na slici je hrvatski) potrebno je svakoj znački dodijeliti
oznaku vrste riječi kao što su imenica, glagol, pridjev i dr. Srednji redak
pokazuje oznake koje daju više detalja o gramatičkim značajkama riječi kao što
su rod i množina imenice, glagolsko vrijeme i dr. Algoritam \ref{alg:postagging}
pokazuje jednostavnost zadatka u okviru učenja pretraživanja.
\begin{figure}
\centering
\begin{dependency}
\begin{deptext}
\textsc{R} \& \textsc{V} \& \textsc{N} \& \textsc{R} \& \textsc{Z} \& \textsc{C} \& \textsc{C} \& \textsc{N} \& \textsc{V} \& \textsc{R} \& \textsc{Z} \\
\textsc{Rgc} \& \textsc{Vmn3pf} \& \textsc{Ncfpnn} \& \textsc{Rgp} \& \textsc{Z} \& \textsc{Cs} \& \textsc{Cs} \& \textsc{Ncfpnn} \& \textsc{Vmn3pf} \& \textsc{Rgp} \& \textsc{Z} \\
Gore \& gore \& gore \& gore \& , \& nego \& što \& gore \& gore \& dolje \& . \\
\end{deptext}
\end{dependency}
\caption[Rečenica s oznakama vrste riječi.]{Rečenica s oznakama vrste riječi. Za
ovu rečenicu ovo nije jedini mogući niz oznaka. Oznake R, V, N, Z i C su za
prilog, glagol, imenicu, znakove interpunkcije i veznike.}
\label{fig:postagging}
\end{figure}
\begin{algorithm}
\caption{Označavanje vrste riječi u radnom okviru \lts{}.}\label{alg:postagging}
\begin{algorithmic}[1]
\Function{\textsc{Izvrši}}{riječi}
\State $\textit{izlaz} \gets \text{[]}$
\For{$n \gets 1$ \textbf{do} \Call{Duljina}{riječi}}
\State \textit{ref} $\gets$ \text{riječi[n].točna\_oznaka}
\State \textit{izlaz[n]} $\gets$ \Call{Odluči}{riječi[n], ref, izlaz[:n-1]}
\EndFor
\State \Call{Gubitak}{\# izlaz[n] $\neq$ riječi[n].točna\_oznaka}
\Return izlaz
\EndFunction
\end{algorithmic}
\end{algorithm}
Algoritam je skoro jednak algoritmu koji provjerava koliko je riječi u rečenici
točno označeno. Točna oznaka je prisutna za svaku riječ u rečenici i proslijeđena
funkciji \textsc{Odluči}, koja vraća odluku trenutne politike -- politika može biti
naučena ili referentna. U slučaju da je politika referentna, funkcija vraća upravo
proslijeđenu oznaku. Nakon što je cijeli izlaz predviđen objavljuje se gubitak
koji je u ovom slučaju broj riječi koje su netočno označene. Algoritam tijekom
učenja u pozadini mijenja politike i pokreće funkciju \textsc{Izvrši} dovoljno puta
dok ne nauči referentnu politiku. Algoritam zaključivanja koristi istu funkciju,
ali u tom trenutku ne postoji pristup točnoj oznaci tj.~što god ona bila neće se
uzeti u obzir nego će se zvati naučena politika. Jedna je funkcija dovoljna za
algoritam učenja i zaključivanja, a to je slučaj za sve algoritme u \lts{}
okviru.
Zanimljivo je usporediti vremenske složenosti uobičajenih pristupa s ovim. Svi
pristupi opisani u poglavlju \ref{ch:pregled} za zaključivanje koriste
Viterbijev algoritam, čija je vremenska složenost $O(T M ^ k)$, gdje je $T$
duljina rečenice, $M$ broj mogućih oznaka i oznaka ne ovisi o prijašnjim
oznakama koje su $k$ ili više pozicija udaljene. U okviru \lts{} složenost
zaključivanja je $O(T M k)$ -- ovdje je $k$ broj prijašnjih odluka kojima
uvjetujemo trenutnu ($k$ je kod navedenih složenosti jednak, ali je kontekst
drugačiji). Iz algoritma \ref{alg:postagging} može se primijetiti da se u
funkciju \textsc{Odluči} prosljeđuju sve prijašnje oznake. One se pri izgradnji
primjera osjetljivog na trošak u algoritmu \textsc{LOLS} dodaju kao značajke.
Binarni klasifikatori koji omogućuju redukciju problema višerazredne
klasifikacije osjetljive na trošak predviđaju trošak svake pojedine oznake kojih
ima točno $M$. Složenost tog postupka je $O(M d)$ gdje je $d$ duljina vektora
značajki. U bilo kojem slučaju zaključivanje je puno brže od Viterbijevog
algoritma.
Prednost je što algoritam \ref{alg:postagging} ne treba mijenjati ako se
mijenjaju redukcije ispod apstrakcije. Recimo, moguće je koristiti redukciju
višerazredne klasifikacije osjetljive na trošak opisanu u
\citep{beygelzimer2009error, daume2016one}. Vremenska složenost određivanja
razreda opada s $O(M)$ na $O(\log M)$. To bi automatski ubrzalo označavanje
vrste riječi i vremenska složenost bi iznosila $O(k T \log M)$.
Vremenska složenost algoritma učenja ovisi o parametrima algoritma. U slučaju
algoritma \textsc{LOLS} (alg.~\ref{alg:lols}), funkcija \textsc{Izvrši} zove se u
liniji \ref{alg:lols:learned} i \ref{alg:lols:mixture}, što bi upućivalo da je
složenost učenja jednog primjera $O(T ^ 2 M k)$, ali raznim \textit{trikovima}
moguće je to smanjiti na $O(T M k)$ -- ako funkcija gubitka ima dekompoziciju
preko niza odluka, onda \textit{rollout} nije potrebno izvršavati. Za detaljniji
opis čitatelja se upućuje na \citep{daume14lts}.
\begin{algorithm}
\caption{Označavanje vrste riječi u radnom okviru \lts{} s više prolaza.}\label{alg:postagging:multipass}
\begin{algorithmic}[1]
\Function{\textsc{Izvrši}}{riječi, P}
\State $\textit{izlaz} \gets \text{[]}$
\For{$p \gets 1$ \textbf{do} P}
\For{$n \gets 1$ \textbf{do} \Call{Duljina}{riječi}}
\State \textit{ref} $\gets$ \Call{PravaOdluka}{riječi[n].točna\_oznaka, p, odluke[n,p$-$1]}
\State \textit{odluke[n,p]} $\gets$ \Call{Odluči}{riječi[i], ref, \textsc{IzvuciSusjede}(odluke)}
\EndFor
\EndFor
\State pravi\_izlaz $\gets$ \Call{RekonstruirajIzlaz}{odluke}
\State \Call{Gubitak}{\# pravi\_izlaz[n] $\neq$ riječi[n].točna\_oznaka}
\Return pravi\_izlaz
\EndFunction
\end{algorithmic}
\end{algorithm}
Algoritam \ref{alg:postagging:multipass} prikazuje alternativnu implementaciju
označivača vrste riječi. U ovom slučaju za jednu se rečenicu radi više prolaza u
nadi da će prvi prolaz otkriti novu informaciju kojom bi sljedeći mogao
popraviti napravljene pogreške. U tom slučaju odluke koje referentna politika vrši
nisu samo točne oznake nego i odluka promjene oznake dodijeljene u prošlom
prolazu. Funkcija \textsc{PravaOdluka} vraća za novije prolaze odluku koju
referentna politika vrši s obzirom na to koja je zapravo točna oznaka. U slučaju
da je trenutnoj riječi dodijeljena točna oznaka, odluka bi trebala biti takva da
očuva prijašnju odluku. Zbog više prolaza moguće je uključiti predviđanja koja
su lijevo i desno od trenutne riječi, a logika je prepuštena funkciji
\textsc{IzvuciSusjede}. Na samom kraju funkcija \textsc{RekonstruirajIzlaz} iz
donesenih odluka rekonstruira pravi izlaz i ostatak je identičan originalnom
algoritmu. Ovakav pristup gotovo je nemoguće napraviti bilo kojom drugom
metodom, a da $\argmax$-problem ostane izračunljiv. Sve odluke u navedenoj
inačici algoritma i dalje se vrše združeno u slučaju da se susjedi dodaju kao
značajke. Algoritam nije ekvivalentan pokretanju označivača vrste riječi više
puta gdje drugo i sva sljedeća pokretanja imaju značajku vrste riječi prošlog
prolaza.