-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path03_zdruzeno_predvidjanje.tex
125 lines (107 loc) · 6.99 KB
/
03_zdruzeno_predvidjanje.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
120
121
122
123
124
125
Združeno učenje i predviđanje \engl{joint learning and prediction} naziv je za
metode koje rade učenje i predviđanje jednog primjera mjereći ili minimizirajući
funkciju gubitka združeno. Naziv strukturnog učenja i predviđanja
\engl{structured learning and prediction} implicira da se funkcija gubitka
raspoređuje po komponentama strukture i da se na strukturi koja je razbijena u
svoje dijelove predviđa i uči -- rečenica u značke, slika u slikovne elemente
i dr. \citet{daume14lts} daju jednostavnu definiciju strukturnog predviđanja kao
donošenja niza združenih odluka računajući vrijednost funkcije gubitka združeno.
Ne postoji pretpostavka o tome kakav je ulaz i ima li specifičnu strukturu. U
\citep{daume14lts, daume15naacltalk} odustaju od naziva \emph{strukturno
predviđanje} i počinju probleme kategorizirati pod nazivom združeno predviđanje
upravo zbog toga što se vrši združeni niz odluka računajući vrijednost
funkcije gubitka združeno preko niza odluka i ona nema nužno dekompoziciju preko
tog niza (ne može za pojedinačnu odluku znati koliki je njen doprinos u
globalnom gubitku). Naziv onda može uključivati združene probleme poput
istovremenog označavanja vrste riječi u rečenici i ovisnosnog parsanja
rečenice, ali i svaki problem zasebno. Kako bi nastavak bio konzistentan sa
starijom literaturom koristi se staro ime, a definicija \ref{def:jointlearn} je
zapravo definicija združenog učenja.
U literaturi koja je koristila naziv za problem strukturnog predviđanja on
nije jasno bio definiran, nego je objašnjen kroz ilustrativne
primjere~\citep{mccallum2000maximum, punyakanok2001use, lafferty2001conditional,
collins2002discriminative, taskar2003maximum, mcallester2004case,
tsochantaridis2005large}. \citet{daume09searn} definiraju jasnije problem, ali
potrebno ga je pažljivije definirati razmatrajući dva uvjeta.
\begin{condition}\label{uvjet1}
U problemu strukturnog predviđanja izlazni elementi $y \in \mathcal{Y}$
dekomponiraju u vektore varijabilnih duljina preko konačnog skupa. Tj.,
postoji konačan $M \in \field{N}$ tako da je svaki $y \in \mathcal{Y}$ moguće
identificirati bar jednim vektorom $v_y \in M^{T_y}$, gdje je $T_y$ duljina
vektora.
\end{condition}
\noindent
\citeauthor{daume06thesis} navodi da ovaj uvjet nije dovoljan i da uključuje
probleme koje inače ne bi smatrali strukturnim predviđanjima poput binarne
klasifikacije. To vodi do drugog uvjeta koji počinje uključivati funkciju
gubitka. Želja je da funkciju gubitka nije moguće dekomponirati preko vektorskih
reprezentacija, a kako je uvijek moguće osmisliti vektorsku reprezentaciju preko
koje će funkcija gubitka dekomponirati slijedi uvjet.
\begin{condition}\label{uvjet2}
U problemu strukturnog predviđanja funkcija gubitka nema dekompoziciju preko
vektora $v_y$ za $y \in \mathcal{Y}$. Tj., $l(x, y, y\ssymbol{1})$ nije
invarijantna na identične permutacije $y$ i $y\ssymbol{1}$. Ne postoji
preslikavanje $y \mapsto v_y$ takvo da funkcija ima dekompoziciju za koju je
duljina vektora $|v_y|$ polinomijalna u broju izlaznih elemenata $|y|$.
\end{condition}
\noindent
Ovaj uvjet uspješno isključuje binarnu klasifikaciju i ostale klasifikacijske
probleme kao probleme strukturnog predviđanja, ali isključuje i problem
označavanja nizova koristeći Hammingovu funkciju gubitka (potonja je
invarijantna na permutacije). Razlika između ova dva uvjeta je taj što u prvom
značajke diktiraju strukturu, a u drugom funkcija gubitka. Problem koji se
rješava je uvijek definiran nekom funkcijom gubitka, a ne značajkama, stoga
\citeauthor{daume06thesis} tvrdi da je problem bolje definirati preko funkcije
gubitka. Pristupi koji slijede u nastavku ovog poglavlja ne mogu riješiti
generalan problem strukturnog predviđanja ako je za definiciju korišten drugi
uvjet. Prihvaćena definicija slijedi.
\begin{definition}[\citet{daume09searn}] \label{def:jointlearn}
Problem strukturnog predviđanja $\mathcal{D}$ je klasifikacijski problem
osjetljiv na trošak \engl{cost-sensitive classification problem}, gdje
$\mathcal{Y}$ ima strukturu, a elementi $y \in \mathcal{Y}$ imaju
dekompoziciju u vektore varijabilne duljine $(y_1, y_2, \ldots, y_T)$.
$\mathcal{D}$ je distribucija preko ulaza $x \in \mathcal{X}$ i vektora troška
$\mathbf{c}$, gdje je $|\mathbf{c}|$ varijabla u $2^T$.
\end{definition}
\noindent
Kao primjer može se uzeti označavanje vrste riječi koristeći Hammingovu funkciju
gubitka. Hammingov bi gubitak za niz odluka kreirao vektor troška $\mathbf{c}$
koji u sebi sadrži za svaku odluku (oznaku vrste riječi) njen trošak (ako je
riječ točno označena trošak je 0, inače 1). U ovom zadatku funkcija gubitka ima
dekompoziciju preko vektorske reprezentacije strukture $y \in \mathcal{Y}$ (za
svaku značku kojoj je dodijeljena oznaka moguće je zasebno odrediti gubitak).
Parsanje je primjer zadatka koji zadovoljava uvjet \ref{uvjet2}. Ako se koristi
funkcija gubitka \textunderscript{F}{1} (harmonijska sredina između preciznosti
i odziva), onda nije moguće za pojedinu odluku stvaranja brida stabla odrediti
parcijalan gubitak jer se \textunderscript{F}{1} računa na potpunim stablima. U
tom slučaju je $\mathcal{D}$ distribucija preko $(x, \mathbf{c})$, gdje je $x$
ulazni niz i za sva stabla $y$ s $|x|$ listova, $c_y$ je funkcija gubitka
\textunderscript{F}{1} izlaza $y$ na točnom izlazu $y\ssymbol{1}$. Cilj
strukturnog predviđanja je pronaći funkciju $h: \mathcal{X} \rightarrow
\mathcal{Y}$ koja minimizira očekivanu vrijednost funkcije gubitka
\ref{eq:funcloss}.
\begin{equation} \label{eq:funcloss}
L(\mathcal{D}, h) = \mathbb{E}_{(x, \mathbf{c}) \sim \mathcal{D}} \{c_{h(x)}\}
\end{equation}
\noindent
Sve metode strukturnog predviđanja u ovom poglavlju, nakon što je naučen vektor
težina $\mathbf{w}$, za predviđanje strukture trebaju riješiti $\argmax$-problem
\ref{eq:argmaxproblem}:
\begin{equation}\label{eq:argmaxproblem}
y\ssymbol{1} = \argmax_{y \in \mathcal{Y}} \mathbf{w}^\top \mathbf{\Phi}(x, y) \text{ ,}
\end{equation}
\noindent
gdje je $\mathbf{w}$ naučen vektor težina i $\mathbf{\Phi}$ funkcija značajki za
ulaz $x$ i mogući izlaz $y$ (ako se struktura predviđa inkrementalno, onda je
moguće koristiti elemente $y_i$ iz vektora dekompozicije kao značajke). Ovaj
problem u generalnom slučaju nije izračunljiv u dovoljno kratkom vremenu. Ako
postoji prikladan $\mathcal{Y}$ i prikladna funkcija značajki $\mathbf{\Phi}$,
onda se mogu primijeniti dinamičko programiranje \engl{dynamic programming} ili
cjelobrojno linearno programiranje \engl{integer linear programming} za
pronalaženje dobrih rješenja. Recimo, ako $\mathbf{\Phi}$ ima takvu
dekompoziciju preko vektorske reprezentacije $\mathcal{Y}$ da ni jedna značajka
ne ovisi o elementima $y$ koji su $k$ ili više pozicija udaljeni, onda se može
iskoristiti Viterbijev algoritam za rješenje \ref{eq:argmaxproblem}, a složenost će
biti $O(T M^k)$ -- gdje je $M$ broj mogućih oznaka, definiran u uvjetu
\ref{uvjet1}, a $T$ duljina vektora na koji se dekomponira $y$ iz definicije
\ref{def:jointlearn}.