-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path11_rollin_rollout.tex
178 lines (171 loc) · 11.1 KB
/
11_rollin_rollout.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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
\citet*{daume15lols} uvode terminologiju \textit{rollin} i \textit{rollout} u
kontekst metoda učenja pretraživanja. Termin \textit{rollout} originalno je
naziv za tehniku analize pozicija i poteza u igri
\textit{backgammon}.\footnote{\url{https://en.wikipedia.org/wiki/Rollout_(backgammon)}}
Cilj je dovoljan broj puta krenuti od iste pozicije i odigravanjem (bacajući
kocku) dolaziti do kraja igre i bilježiti rezultat svakog ishoda. Broj pobjeda i
poraza daje procjenu o dobroti pozicije. U okviru podržanog učenja tehnika se
koristi tako da se iz nekog stanja nasumično odabiru sljedeći potezi -- odabir
može biti baziran na do tada naučenoj politici. Nakon što se izvrši jedan niz poteza i
dobije rezultat, cijeli postupak se ponavlja počinjanjem iz istog stanja tako da
je procjena o dobroti pozicije što bolja.
Termin \textit{rollin} nije bio prisutan kod podržanog učenja jer postoji samo
naučena politika, ali se podrazumijeva da se do željenog stanja dolazi koristeći
naučenu politiku -- ako su neka stanja nedostižna trenutnoj naučenoj politici, onda
bi bilo bespotrebno vrednovati odluke iz stanja do kojih se ne može doći. U
kontekstu metoda učenja pretraživanja \textit{rollin} je postupak dolaska do
određenog stanja, a kako je na raspolaganju naučena i referentna politika dobro je
vidjeti koja strategija vodi do brzog i konzistentnog učenja -- hoće li se
dolaziti do budućeg stanja referentnom ili naučenom politikom, a možda za svaki
korak odabrati nekom vjerojatnošću jednu ili drugu. Na slici \ref{fig:rollinout}
prikazan je postupak korištenja politika u postupku \textit{rollin} i \textit{rollout}
za vrednovanje odluka gdje su odluke predstavljene bridovima, a stanja čvorovima.
\begin{figure}
\centering
\begin{tikzpicture}[
>={Triangle[]},
b/.style = {lightblue,fill=lightblue!40},
g/.style = {darkgreen,fill=darkgreen!40}
]
\matrix[
matrix of nodes,column sep=1cm,row sep=.1cm,
nodes={
lightgray,draw,thick,fill=lightgray!40,circle,
minimum size=3ex, inner sep=1pt,anchor=south
}] (m) {
& & & & {}& {}\\
& & & & {}& {}\\
& {}& {}&|[g]|{}&|[g]|{}&|[g]|Z \\
& & & & {}& {}\\
|[b]|P &|[b]|{}&|[b]|R &|[b]|{}&|[b]|{}&|[b]|Z \\
& & & & {}& {}\\
& {}& {}&|[g]|{}&|[g]|Z & \\
& & & & {}& \\
& & & & {}& \\
};
% Green arrows
\draw[darkgreen,->, line width=1.2pt] (m-5-3.east) to[bend left] (m-3-4.west);
\draw[darkgreen,->, line width=1.2pt] (m-5-3.east) to[bend right] (m-7-4.west);
% Gray arrows
\foreach \i[evaluate=\i as \j using int(\i+1)] in {1,2} {
\foreach \row/\bend in {3/left, 7/right}
\draw[lightgray,->, line width=1.2pt] (m-5-\i.east) to[bend \bend] (m-\row-\j.west);
}
\foreach \i[evaluate=\i as \j using int(\i+1)] in {4,5} {
\foreach \row/\bend in {1/left, 2/left}
\draw[lightgray,->, line width=1.2pt] (m-3-\i.east) to[bend \bend] (m-\row-\j.west);
}
\foreach \i[evaluate=\i as \j using int(\i+1)] in {4,5} {
\foreach \row/\bend in {4/left, 6/right}
\draw[lightgray,->, line width=1.2pt] (m-5-\i.east) to[bend \bend] (m-\row-\j.west);
}
\foreach \row/\bend in {8/right, 9/right}
\draw[lightgray,->, line width=1.2pt] (m-7-4.east) to[bend \bend] (m-\row-5.west);
% Black arrows
\foreach \i [remember=\i as \lasti (initially 4)] in {5,6}
\draw[->, line width=1.2pt] (m-3-\lasti.east) to (m-3-\i.west);
\foreach \i [remember=\i as \lasti (initially 1)] in {2,...,6}
\draw[->, line width=1.2pt] (m-5-\lasti.east) to (m-5-\i.west);
\draw[->, line width=1.2pt] (m-7-4.east) to (m-7-5.west);
% Loss
\node[right=of m-3-6] (loss1) {$y_z \in \mathcal{Y}, l(y_z) = 0$};
\node[right=of m-5-6] (loss2) {$y_z \in \mathcal{Y}, l(y_z) = 1$};
\node[right=of m-7-5] (loss3) {$y_z \in \mathcal{Y}, l(y_z) = 2$};
\draw[->, line width=1.2pt] (m-3-6.east) to (loss1);
\draw[->, line width=1.2pt] (m-5-6.east) to (loss2);
\draw[->, line width=1.2pt] (m-7-5.east) to (loss3);
% Braces
\draw[decorate,decoration={brace,amplitude=10pt},black,thick]
(m-7-3 |- m-7-3.south) -- node[below=10pt] (rollin) {\textit{rollin}} (m-5-1 |- m-7-3.south);
\draw[decorate,decoration={brace,amplitude=10pt},black,thick]
(m-5-6 |- m-9-5.south) -- node[below=10pt] (rollout) {\textit{rollout}} (m-5-4 |- m-9-5.south);
\path (rollin) -- node[black,align=right,rotate=90] {odstupanja od \\ jednog koraka} (rollout);
\node[shape=rectangle,draw=black,thick, above=of m-5-1] (xinX) {$x \in \mathcal{X}$};
\draw[->, line width=1.2pt,out=-90,in=120] (xinX) to (m-5-1);
\end{tikzpicture}
\caption[Prikaz postupka \textit{rollin} i \textit{rollout} kod učenja
pretraživanja.]{Prikaz postupka \textit{rollin} i \textit{rollout} kod učenja
pretraživanja. Ulaz $x \in \mathcal{X}$ vodi pretragu svojim značajkama. Kreće
se iz stanja $P$ i dva se puta odabire srednja odluka od moguće tri koristeći
odabranu politiku za \textit{rollin}. Sivi čvorovi se ne pretražuju. U koraku
$R$ algoritam učenja odabire sve moguće odluke radeći odstupanje od jednog
koraka i primjenjuje odabranu politiku u postupku \textit{rollout} za svaku
moguću odluku dovoljno puta dok ne dođe do kraja. Odstupanje od jednog koraka
procjenjuje trošak za pojedinu odluku samo uzimajući tu odluku u obzir,
nastavljajući niz odluka postupkom \textit{rollout}. Odstupanje od dva koraka
bi iz stanja $R$ procjenjivalo trošak za odluku tako da nakon izvedene odluke
dolaskom u novo stanje izvrši sve moguće odluke u tom stanju i onda za svaku
izvrši ostatak postupkom \textit{rollout}. Inačica s odstupanjem od dva koraka
bi bolje aproksimirala trošak, ali bi vremenski bila zahtjevnija -- odstupanje
od jednog koraka zahtijeva izvršavanje postupka \textit{rollout} za svaku
odluku, odstupanje od dva koraka zahtijevalo bi izvršavanje postupka
\textit{rollout} za svaku moguću odluku nakon što se izvrši svaka moguća u
stanju $R$, što vodi do kvadratne vremenske složenosti u ovisnosti o broju
mogućih odluka. Na kraju izvršavanja postupka \textit{rollout} pomoću potpunog
niza odluka $y_z \in \mathcal{Y}$ dobiva se informacija o gubitku i ona se
koristi kao procjena dobrote svake odluke. Nakon postupka moguće je zaključiti
da se gornjom odlukom koja odstupa od odabranog srednjeg stanja može gubitak
smanjiti za 1. Primjer preuzet iz \citep[str.~3]{daume15lols}}
\label{fig:rollinout}
\end{figure}
\cite{daume15lols} pokazuju da korištenje višerazrednog klasifikatora
osjetljivog na trošak, koji ima dobre ograde žaljenja (žaljenje mora biti
konstantno tj.~neovisno o broju binarnih klasifikatora u redukciji), ne
garantira konzistentnu naučenu politiku za problem strukturnog predviđanja.
Ovisno o načinu na koji se radi \textit{rollin} i \textit{rollout} i
pretpostavci o tome kakva je referentna politika, moguće je dobiti
nekonzistentnu redukciju. Rezultat je priložen na slici \ref{fig:policyresult}.
Ovisno o tome koje se politike koriste u postupcima \textit{rollin} ili
\textit{rollout}, moguće je dobiti naučenu politiku koja nije konzistentna (ima
veliko strukturno žaljenje tj.~žaljenje nije konstantno nego ovisi o duljini
niza odluka) ili politiku koja nije lokalno optimalna. U slučaju korištenja
naučene politike za \textit{rollin} i \textit{rollout}, problem strukturnog
predviđanja reducira se na problem podržanog učenja koji je puno teži jer se za
učenje uopće ne koristi znanje referentne politike.
Jedini dobar pristup kojim se postiže lokalna optimalnost i konzistentna
redukcija je onaj u kojem se koristi mješovita politika za \textit{rollout} --
opis metode lokalno optimalnog učenja pretraživanja nalazi se u potpoglavlju
\ref{ch:LOLS}. Ako se pretpostavi da je referentna politika optimalna i to je
stvarno slučaj, onda će učenje koristeći \textit{rollin} s naučenom, a
\textit{rollout} s referentnom rezultirati s konzistentnom i lokalno optimalnom
naučenom politikom. Za mnoštvo problema nije lako definirati optimalnu politiku
(nije lako iz podataka znati koji je sljedeći korak najbolji, npr.~prisutnost
prijevoda nekog dokumenta nije dovoljna da znamo, u slučaju da dobijemo
parcijalan prijevod dokumenta, koja riječ slijedi) i zanimljiv je rezultat da
upravo \textit{rollout} s mješovitom politikom ima garancije da će, ako je u
prostoru odluka moguće raditi lokalno uspinjanje na vrh \engl{local hill
climbing}, naučena politika biti konstantno lošija od dane referentne politike
ili će biti bolja od referentne politike. Takvu garanciju pristupi prije
algoritma \textsc{LOLS} nisu imali. Problem postoji čak i kod metode učenja
pretraživanja \textsc{Searn} \citep{daume15lols}. Navedena karakteristika nije
pretjerano korisna ako je referentna politika loša, u tom slučaju učenje se
odvija kao da referenta politika ne postoji (informacija koju ona daje je
beskorisna). Ako je lako raditi uspinjanje na vrh u prostoru odluka, onda bi na
problemu jednako dobro radilo i podržano učenje.
% If you use beamer only pass "xcolor=table" option, i.e. \documentclass[xcolor=table]{beamer}
\begin{figure}
\centering
\begin{tabular}{|
>{\columncolor[HTML]{FFFFC7}}l |
>{\columncolor[HTML]{C0C0C0}}c |
>{\columncolor[HTML]{C0C0C0}}c |
>{\columncolor[HTML]{C0C0C0}}c |}
\hline
\multicolumn{1}{|c|}{\cellcolor[HTML]{C0C0C0}Rollout $\rightarrow$} & \cellcolor[HTML]{C0C0C0} & \cellcolor[HTML]{C0C0C0} & \cellcolor[HTML]{C0C0C0} \\
\multicolumn{1}{|c|}{\cellcolor[HTML]{FFFFC7}$\downarrow$ Rollin} & \multirow{-2}{*}{\cellcolor[HTML]{C0C0C0}\textbf{Referentna}} & \multirow{-2}{*}{\cellcolor[HTML]{C0C0C0}\textbf{Mješovita}} & \multirow{-2}{*}{\cellcolor[HTML]{C0C0C0}\textbf{Naučena}} \\ \hline
\textbf{Referentna} & \multicolumn{3}{c|}{\cellcolor[HTML]{FFCCC9}Nekonzistentna redukcija} \\ \hline
\textbf{Naučena} & \cellcolor[HTML]{FFCCC9}Nije lokalno optimalna & \cellcolor[HTML]{C5F7C5}Dobra & \cellcolor[HTML]{FFCCC9}Podržano učenje \\ \hline
\end{tabular}
\caption[Rezultati teoretske analize načina učenja koristeći \textit{rollin} i
\textit{rollout}.]{Rezultati teoretske analize načina učenja koristeći
\textit{rollin} i \textit{rollout}. Ovisno o odabiru \textit{rollin} i
\textit{rollout} para naučena politika može biti nekonzistentna ili bez svojstva
lokalne optimalnosti, problem učenja politike se može svesti na podržano učenje
ili naučena politika ipak može biti konzistentna i lokalno optimalna. Mješovita
politika je politika kod koje se nekom vjerojatnošću bira referentna ili
naučena. Tablica preuzeta iz \citep[str.~4]{daume15lols}}
\label{fig:policyresult}
\end{figure}
Da bi se izbjeglo ponavljanje nekih značajki, prednosti i ciljeva algoritama
učenja pretraživanja njihove karakteristike detaljnije su analizirane u zasebnim
potpoglavljima (\ref{ch:metodesearchlearn}).