<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Sveučilište u Zagrebu<br>
Fakultet elektrotehnike i računarstva
Strojno učenje
<a href="http
Step1:  Sadržaj
Step2:  (2) Funkcija gubitka (i njoj odgovarajuća funkcija pogreške)
Step3:  Funkcija koja generira podatke (i koju zapravo želimo naučiti)
Step4:  Skup primjera za učenje $\mathcal{D}=(\mathbf{X},\mathbf{y})$ dobiven je iz $f(x)$, uz dodatan šum
Step5:  Dvije hipoteze iz našeg modela
Step6:  Empirijske pogreške hipoteza na skupu $\mathcal{D}$
Step7:  (3) Optimizacijski postupak
Tražimo $h\in\mathcal{H}$ koja minimizira empirijsku pogrešku
$$
h^* = 
\mathrm{argmin}{h\in\mathcal{H}} E(h|\mathcal{D}) = 
\mathrm{argmin}{h\in\mathcal{H}} \frac{1}{2}
\sum_{i=1}^N\big(y^{(i)}-h(x^{(i)})\big)^2
$$
Hipoteza $h$ je indeksirana parametrima $(w_0, w_1)$, dakle zapravo tražimo
$$
(w_0,w_1)^* =
\mathrm{argmin}{w_0,w_1} \frac{1}{2} 
\sum{i=1}^N\big(y^{(i)}-(w_1 x^{(i)} + w_0)\big)^2
$$
U ovom slučaju postoji analitičko rješenje (rješenje u zatvorenoj formi)
\begin{eqnarray}
    && \nabla_{w_0,w_1} E(h|\mathcal{D})=0\
    &&\frac{\partial}{\partial w_0}\Big[
\frac{1}{2}\sum_i^N\big(y^{(i)}-(w_1 x^{(i)}+ w_0)\big)^2\Big] = 0 \
&&\frac{\partial}{\partial w_1}\Big[\frac{1}{2}\sum_i^N\big(y^{(i)}-(w_1 x^{(i)}+
w_0)\big)^2\Big] = 0\
&&\vdots\
&& w_0= \bar{y} - w_1\bar{x}\
&& w_1 = \frac{\sum_i^N x^{(i)}y^{(i)} - N\bar{x}\bar{y} }
{\sum_i^N(x^{(i)})^2 - N\bar{x}^2}
\end{eqnarray}
Step8:  U gornjem primjeru radili smo s modelom prvog stupnja
$$
h_1(x) = w_1 x + w_0
$$
Međutim, mogli smo odabrati i složeniji model, npr. polinom drugog stupnja
Step9:  Možemo očekivati da vrijedi
Step10:  Model koji odgovara pravoj funkciji koja je generirala podatke je $h_3$, tj. optimalan hiperparametar je $d=3$
Modeli $h_1$ i $h_2$ imaju veću pogrešku od $h_3$ i njih sigurno ne bismo uzeli
Međutim, modeli $h_4$ i $h_5$ imaju manju pogrešku od $h_3$
Očito, što je veći kapacitet modela $\mathcal{H}$, to je manja pogreška $E(h|\mathcal{D})$, $h\in\mathcal{H}$
Ali model mora moći generalizirati!
Preferiramo jednostavne modele
bolja generalizacija
lakše učenje/uporaba
lakše tumačenje
Occamova britva
<img src="http
<ASSISTANT_TASK:>
Python Code:
import scipy as sp
import scipy.stats as stats
import matplotlib.pyplot as plt
from numpy.random import normal
%pylab inline
Explanation: Sveučilište u Zagrebu<br>
Fakultet elektrotehnike i računarstva
Strojno učenje
<a href="http://www.fer.unizg.hr/predmet/su">http://www.fer.unizg.hr/predmet/su</a>
Ak. god. 2015./2016.
Bilježnica 2: Osnovni koncepti strojnog učenja
(c) 2015 Jan Šnajder
<i>Verzija: 0.7 (2015-10-21)</i>
End of explanation
def h(x, w): return w[1] * x + w[0]
Explanation: Sadržaj:
Tipični koraci primjene algoritma SU
Prostor primjera
Hipoteza i model
Empirijska pogreška
Prostor inačica
Složenost modela
Induktivna pristranost
Tri komponente svakog algoritma SU
Primjer: regresija
Problem šuma
Odabir modela
Tipični koraci primjene algoritma SU
Priprema podataka
(Označavanje podataka za učenje i ispitivanje)
(Redukcija dimenzionalnosti)
Odabir modela
Učenje modela
Vrednovanje modela
Dijagnostika i ispravljanje (debugging)
Instalacija (deployment)
Naš fokus su koraci 4-7
Prostor primjera
Prostor primjera (ulazni prostor): $\mathcal{X}$
Dimenzija ulaznog prostora: $n$
Primjer je vektor u ulaznom prostoru: $\mathbf{x} = (x_1, x_2, \dots, x_n)^T \in \mathcal{X}$
Oznaka (engl. label) klase (za klasifikaciju) ili ciljna vrijednost (za regresiju): $y$
Skup oznaka klase: $\mathcal{Y} = {0, \dots, K}$
Broj klasa: $K$
Binarna klasifikacija: $K=2$, $\mathcal{Y} = {0,1}$
Broj primjera: $N$
Skup označenih primjera za učenje: $\mathcal{D} = \big{(x^{(i)}, y^{(i)})\big}_{i=1}^N \subseteq \mathcal{X}\times\mathcal{Y}$
Matrično:
\begin{array}{lllll|l}
&x_1 & x_2 & \cdots & x_n & \mathbf{y}\
\hline
\mathbf{x}^{(1)} = & x_1^{(1)} & x_2^{(1)} & \cdots & x_n^{(1)} & y^{(1)}\
\mathbf{x}^{(2)} = & x_1^{(2)} & x_2^{(2)} & \cdots & x_n^{(2)} & y^{(2)}\
& \vdots\
\mathbf{x}^{(N)} = & x_1^{(N)} & x_2^{(N)} & \cdots & x_n^{(N)} & y^{(N)}\
\end{array}
Matrica $\mathcal{D}$ sastavljena je od matrice $\mathbf{X}{N\times n}$ i vektora $\mathbf{y}{N\times 1}$
Hipoteza i model
Hipoteza: $h : \mathcal{X} \to \mathcal{Y}$
Funkcija koja svakom primjeru (iz prostora primjera) dodjeljuje oznaku klase (iz skupa oznaka klase)
Binarna klasifikacija: $h : \mathcal{Y} \to {0, 1}$
Definicija: Primjer $\mathbf{x}\in\mathcal{X}$ zadovoljava hipotezu $h$ akko $h(\mathbf{x})=1$
Definicija: Hipoteza $h$ je konzistentna s primjerom $(\mathbf{x}, y)$ akko $h(\mathbf{x})=y$
Općenitije: $h(\mathbf{x} | \theta)$
Funkcija parametrizirana parametrima $\theta$ (vektor parametara)
Npr.:
Linearna regresija: $h(x) = \theta_1 x + \theta_0$
Linearan klasifikacijski model: $h(x_1,x_2|\theta_0,\theta_1,\theta_2) = \mathbf{1}{\theta_1 x_1 + \theta_2 x_2 + \theta_0 \geq 0}$
Model $\mathcal{H}$: skup hipoteza $h$
Formalno: $\mathcal{H} = \big{ h(\mathbf{x} | \theta)\big}_{\theta}$
Familija funkcija parametriziranih s $\theta$
Učenje (treniranje modela) svodi se na pretraživanje prostora hipoteza $\mathcal{H}$ i nalaženje najbolje hipoteze $h\in \mathcal{H}$
Najbolja hipoteza: ona koja najtočnije klasificira primjere (klasifikacija) odnosno daje vrijednosti najbliže ciljnim vrijednostima (regresija)
Optimizacijski problem!
[Primjer: Ulazni prostor + prostor parametara]
$\mathcal{H}$ je vrlo velik, pa nam često treba heuristička optimizacija
Empirijska pogreška
Iskazuje koliko točno hipoteza klasificira primjere (klasifikacija) ili koliko su vrijednosti blizu ciljnih vrijednosti (regresija)
Pogreška klasifikacija (engl. misclassification error):
$$
E(h|\mathcal{D}) 
= \frac{1}{N} \sum_{i=1}^N \mathbf{1}{h(\mathbf{x})^{(i)} \neq y^{(i)}}
$$
Specifično, za binarnu klasifikaciju s $\mathcal{Y}={0,1}$:
$$
E(h|\mathcal{D}) = \frac{1}{N} \sum_{i=1}^N |h(\mathbf{x})^{(i)} - y^{(i)}|
$$
[Primjer]
Vrijednost pogreške načinjene na pojedinačnom primjeru (funkcija unutar sume) zove se funkcija gubitka (engl. loss function)
Gubitak $\mathbf{1}{h(\mathbf{x})^{(i)} \neq y^{(i)}}$ zove se gubitak nula-jedan (engl. zero-one loss)
Prostor inačica (engl. version space)
$\mathit{VS}_{\mathcal{H},\mathcal{D}} \subseteq \mathcal{H}$
Skup hipoteza iz $\mathcal{H}$ koje su konzistentne s primjerima za učenje $\mathcal{D}$
$$
\mathit{VS}_{\mathcal{H},\mathcal{D}} =
\Big{h\in\mathcal{H} \mid \forall(\mathbf{x},y)\in\mathcal{D}.\ \big(h(\mathbf{x})=y\big)\Big}
$$
[Primjer]
Složenost modela
Idealno, u modelu $\mathcal{H}$ postoji hipoteza $h$ koja je konzistentna s $\mathcal{D}$, tj. hipoteza za koju vrijedi $E(h|\mathcal{D}) = 0$
No, moguće je da takva $h$ ne postoji, tj. $\forall h\in\mathcal{H}. E(h|\mathcal{D}) > 0$
Tada kažemo da model $\mathcal{H}$ nije dovoljne složenosti (ili kapaciteta)
[Primjer]
[Zadatak: 6 primjera]
Induktivna pristranost (engl. inductive bias)
Učenje hipoteze je loše definiran problem: $h$ ne slijedi deduktivno iz $\mathcal{D}$
Primjer 1: Učenje Booleove funkcije
\begin{array}{ccc|c}
x_1 & x_2 & x_3 & y\
\hline
0&0&0&\color{red}{\textbf{?}}\
0&0&1&\color{red}{\textbf{?}}\
0&1&0&1\
0&1&1&0\
1&0&0&1\
1&0&1&0\
1&1&0&\color{red}{\textbf{?}}\
1&1&1&1\
\end{array}
$N = |\mathcal{D}|=5$, $n=3$, $\mathcal{X} = {0,1}^3$, $|\mathit{VS}| = 2^{2^n - N} = 8$
Generalizacija - sposobnost klasifikacije još neviđenih primjera
Učenje i generalizacija nisu mogući bez dodatnih pretpostavki
Futility of bias-free learning
Induktivna pristranost (engl. inductive bias)
$\mathcal{L}$ - algoritam učenja
$h_\mathcal{L}$ - hipoteza inducirana pomoću $\mathcal{L}$ na $\mathcal{D}$
$h_\mathcal{L}(\mathbf{x})$ - klasifikacija primjera $\mathbf{x}\in\mathcal{X}$
Induktivna pristranost od $\mathcal{L}$ je bilo koji skup minimalnih pretpostavki $\mathcal{B}$ takvih da 
$$
  \forall \mathcal{D}.\,\forall\mathbf{x}\in \mathcal{X}.\,\big((\mathcal{B}\land\mathcal{D}\land\mathbf{x})\ \vdash\ h_\mathcal{L}(\mathbf{x})\big)
$$
Skup pretpostavki koje od indukcije čine dedukciju
Dvije vrste induktivne pristranosti:
Pristranost jezika (pristranost ograničenjem): odabiremo model $\mathcal{H}$ koji ograničava skup prikazivih hipoteza
Pristranost preferencijom (pristranost pretraživanja): definiramo način pretraživanja unutar $\mathcal{H}$
Većina aloritama SU kombinira obje vrste pristranosti
[Primjer 2: Ulazni prostor + prostor parametara]
Zadatak 3: 
Učenje Booleove funkcije u $\mathcal{X}={0,1}$, $\mathcal{H}$ je skup pravaca
Q: Koja je ovo vrsta pristranosti?
Q: Koliko različitih hipoteza postoji?
Q: Postoji li za svako označavanje konzistentna hipoteza u $\mathcal{H}$?
Razmotrimo opet Primjer 1, uz $\mathcal{H} = \text{skup ravnina u $\mathbb{R}^3$}$
Tri komponente svakog algoritma SU
(1) Model $\mathcal{H}$
$\mathcal{H} = \big{ h(\mathbf{x} | \theta)\big}_{\theta}$
(2) Funkcija gubitka $L(y, h(\mathbf{x}))$
Izračunava kolika je pogreška hipoteze (naučenog modela) na primjeru $\mathbf{x}^{(i)}$
Uobičajene funkcije gubitka:
Kvadratno odstupanje (regresija): $L\big(y,h(\mathbf{x}^{(i)}|\theta)\big)=(h(\mathbf{x}^{(i)}|\theta) - y^{(i)})^2$
Gubitak 0-1 (klasifikacija): $L\big(y,h(\mathbf{x}^{(i)}|\theta)\big) = \mathbf{1}{h(\mathbf{x})^{(i)} \neq y^{(i)}}$
Funkcija pogreške definirana je kao očekivana vrijednost funkcije gubitka na primjerima iz $\mathcal{X}\times\mathcal{Y}$
$$
E(h) = \mathbb{E}_{\mathbf{x},y}[L]
$$
Međutim, prava distribucija primjera i oznaka, $P(\mathbf{x}, y)$ je nepoznata, pa umjesto toga računamo empirijsku pogrešku (pogrešku na skupu označenih primjera $\mathcal{D}$)
$$E(h|\mathcal{D}) = \mathbb{E}{D}[L] = \frac{1}{N} \sum{i=1}^N L\big(y^{(i)}, h(\mathbf{x}^{(i)})\big)$$
Budući da su hipoteze indeksirane preko parametara $\theta$, možemo pisati
$$E(\color{red}{\theta}|\mathcal{D}) = \mathbb{E}{D}[L] = \frac{1}{N} \sum{i=1}^N L\big(y^{(i)}, h(\mathbf{x}^{(i)}|\color{red}{\theta})\big)$$
(3) Optimizacijski postupak
Postupak kojim nalazimo hipotezu $h^$ koja minimizira empirijsku pogrešku
$$
h^ = \mathrm{argmin}{h\in\mathcal{H}} E(h|\mathcal{D})
$$
tj. 
$$
\theta^* = \mathrm{argmin}{\theta} E(\theta|\mathcal{D})
$$
Optimizacija može biti analitička ili heuristička
Analitičke postupke koristimo kada postoji rješenje u zatvorenoj formi
Gornje tri komponente definiraju i induktivnu pristranost svakog algoritma
Q: Koja vrsta induktivne pristranosti je vezana uz koje komponente?
Primjer: regresija
$y \in \mathbb{R}$
Na temelju $\mathcal{D}={(\mathbf{x}^{(i)},y^{(i)})}$ učimo funkciju $h$ koja aproksimira nepoznatu funkciju $f:\mathcal{X}\to\mathbb{R}$
Idealno, $y^{(i)}=f(\mathbf{x}^{(i)})$, ali zbog šuma  $y=f(\mathcal{x}^{(i)})+\varepsilon$ 
[Primjeri: Box Office Revenue, prosjek ocjena, cijena automobila]
Funkcija gubitka je kvadratna:
$$
L(y, h(\mathbf{x})) = (y - h(\mathbf{x}))^2
$$
pa je empirijska pogreška hipoteze
$$
E(h|\mathcal{D})=\color{red}{\frac{1}{2}}\sum_{i=1}^N\big(y^{(i)}-h(\mathbf{x}^{(i)})\big)^2
$$
NB: Umjesto $1/N$, kod pogreške regresije koristimo $1/2$ zbog kasnije matematičke jednostavnosti. To međutim nema utjecaja na optimizaciju (radi se o konstanti)
Linearan model: hiperravnina u $\mathbb{R}^n$
$$
h(\mathbf{x}|\mathbf{w}) = w_1 x_1 + w_2 x_2 + \dots + w_n x_n + w_0 = 
\sum_{i=1}^n w_i x_i + w_0 = \mathbf{w}^T\mathbf{x} + w_0
$$
Za $n=2$ imamo $\mathcal{X}=\mathbb{R}$. Model je
$$
h(x|\mathbf{w}) = w_1 x + w_0
$$
funkcija gubitka je
$$
L(y^{(i)}, h(x^{(i)})) = \big(y^{(i)}-(w_1 x^{(i)} + w_0)\big)^2
$$
a pogreška je
$$
E(h|\mathcal{D})=\frac{1}{2}
\sum_{i=1}^N\big(y^{(i)}-(w_1 x^{(i)} + w_0)\big)^2
$$
(1) Model:
End of explanation
def quadratic_loss(y, hx):
    return (y - hx)**2
    
def error(h, X, y):
    err = 0
    for xi, yi in zip(X, y):
        err += quadratic_loss(yi, h(xi))
    return 0.5 * err
Explanation: (2) Funkcija gubitka (i njoj odgovarajuća funkcija pogreške):
End of explanation
def f(x): return 3 * x + 2
xs = sp.linspace(0, 10)
plt.plot(xs, f(xs));
Explanation: Funkcija koja generira podatke (i koju zapravo želimo naučiti):
End of explanation
X = linspace(0, 10)
y = f(X) + 2 * stats.norm.rvs(scale=3, size=50)
X
len(_)
y
plt.plot(xs, f(xs), '--')
plt.scatter(X, y)
plt.show()
Explanation: Skup primjera za učenje $\mathcal{D}=(\mathbf{X},\mathbf{y})$ dobiven je iz $f(x)$, uz dodatan šum:
End of explanation
def h1(x): return h(x, [0,1])
def h2(x): return h(x, [0,2])
weights = [[0,1], [0,2], [1,2]]
plt.plot(xs, f(xs), '--')
plt.scatter(X, y)
plt.plot(xs, h1(xs), 'r', label='h1')
plt.plot(xs, h2(xs), 'g', label='h2')
plt.legend();
Explanation: Dvije hipoteze iz našeg modela:
End of explanation
error(h1, X, y)
error(h2, X, y)
Explanation: Empirijske pogreške hipoteza na skupu $\mathcal{D}$:
End of explanation
N = len(X)
x_mean = sp.mean(X)
y_mean = sp.mean(y)
w1 = (np.dot(X, y) - N * x_mean * y_mean) / (sum(X**2) - N * (x_mean**2))
w0 = sp.mean(y) - w1 * sp.mean(X)
print w1, w0
def h_best(x): return h(x, [w0,w1])
plt.plot(xs, f(xs), '--')
plt.scatter(X, y)
plt.plot(xs, h_best(xs), 'r');
error(h_best, X, y)
Explanation: (3) Optimizacijski postupak
Tražimo $h\in\mathcal{H}$ koja minimizira empirijsku pogrešku
$$
h^* = 
\mathrm{argmin}{h\in\mathcal{H}} E(h|\mathcal{D}) = 
\mathrm{argmin}{h\in\mathcal{H}} \frac{1}{2}
\sum_{i=1}^N\big(y^{(i)}-h(x^{(i)})\big)^2
$$
Hipoteza $h$ je indeksirana parametrima $(w_0, w_1)$, dakle zapravo tražimo
$$
(w_0,w_1)^* =
\mathrm{argmin}{w_0,w_1} \frac{1}{2} 
\sum{i=1}^N\big(y^{(i)}-(w_1 x^{(i)} + w_0)\big)^2
$$
U ovom slučaju postoji analitičko rješenje (rješenje u zatvorenoj formi)
\begin{eqnarray}
    && \nabla_{w_0,w_1} E(h|\mathcal{D})=0\
    &&\frac{\partial}{\partial w_0}\Big[
\frac{1}{2}\sum_i^N\big(y^{(i)}-(w_1 x^{(i)}+ w_0)\big)^2\Big] = 0 \
&&\frac{\partial}{\partial w_1}\Big[\frac{1}{2}\sum_i^N\big(y^{(i)}-(w_1 x^{(i)}+
w_0)\big)^2\Big] = 0\
&&\vdots\
&& w_0= \bar{y} - w_1\bar{x}\
&& w_1 = \frac{\sum_i^N x^{(i)}y^{(i)} - N\bar{x}\bar{y} }
{\sum_i^N(x^{(i)})^2 - N\bar{x}^2}
\end{eqnarray}
End of explanation
from SU import PolyRegression
X1 = X.reshape((50,1))
h2 = PolyRegression(2).fit(X1, y)
h4 = PolyRegression(4).fit(X1, y)
plt.plot(xs, f(xs), '--')
plt.scatter(X, y)
plt.plot(X1, h2.predict(X1), 'r');
plt.plot(X1, h4.predict(X1), 'g');
error(h2, X, y)
error(h4, X, y)
Explanation: U gornjem primjeru radili smo s modelom prvog stupnja
$$
h_1(x) = w_1 x + w_0
$$
Međutim, mogli smo odabrati i složeniji model, npr. polinom drugog stupnja:
$$
h_2(x) = w_2 x^2 + w_1 x + w_0
$$
ili četvrtog stupnja:
$$
h_4(x) = w_4 x^4 + w_3 x^3 + w_2 x^2 + w_1 x + w_0
$$
Ovo je i dalje linearna regresija, i dalje ima analitičko rješenje
End of explanation
def g(x): return x**3 - 10 * x**2 + 2 * x - 2
xs = sp.linspace(0, 10)
plt.plot(xs, g(xs));
X = sp.linspace(0,10)
y = g(X) + 5 * stats.norm.rvs(scale=3, size=50)
plt.plot(xs, g(xs), '--')
plt.scatter(X, y)
plt.show()
plt.plot(xs, g(xs), '--')
plt.scatter(X, y)
X1 = X.reshape((50,1))
for degree in range(1, 8):
    h = PolyRegression(degree).fit(X1, y)
    plt.plot(X1, h.predict(X1), label="d=%d" % degree);
    print "error(h%d) = %.2f" % (degree, error(h, X, y))
plt.legend()
plt.show()
Explanation: Možemo očekivati da vrijedi:
$$
E(h_4|\mathcal{D}) \leq E(h_2|\mathcal{D}) \leq E(h_1|\mathcal{D})
$$
Q: Zašto?
Q: Koji model odabrati u ovom slučaju?
Q: Koji model općenito odabrati za neke podatke $\mathcal{D}$?
Problem šuma
Šum je neželjena anomalija u podacima
Mogući uzroci:
Nepreciznost pri mjerenju značajki
Pogreške u označavanju (engl. teacher noise)
Postojanje skrivenih značajki (latentnih varijabli)
Nejasne granice klasa (subjektivnost)
Zbog šuma je granica između pozitivnih i negativnih primjera složenija nego što bi idealno bila!
[Primjer 1: binarna klasifikacija po značajkama dobi i prihoda]
Jednostavni modeli ne mogu doseći $E(h|\mathcal{D})=0$
S druge strane, složeni modeli uče šum, a ne pravu klasifikaciju!
[Primjer 2]
Šum u načelu nije moguće odvojiti od pravih podataka
Moguće je samo za stršeće vrijednosti (engl. outliers)
Odabir modela
Moramo odabrati model $\mathcal{H}$ (učenje bez pristranosti je uzaludno)!
Često radimo odabir modela unutar neke familije modela (npr. kod regresije: odabir stupnja polinoma)
Stupanj polinoma je hiperparametar modela ($w_i$ su parametri)
 Odabir modela = optimizacija modela, optimizacija hiperparametara 
Primjer: regresija
End of explanation
XY = np.column_stack((X1, y))
np.random.shuffle(XY)
X_train, y_train = XY[:30,0:1], XY[:30,1]
X_test, y_test = XY[30:,0:1], XY[30:,1]
len(X_train), len(X_test)
plt.plot(xs, g(xs), '--')
plt.scatter(X_train, y_train, c='b')
plt.scatter(X_test, y_test, c='r');
plt.plot(xs, g(xs), '--')
plt.scatter(X_train, y_train, c='b')
plt.scatter(X_test, y_test, c='r');
for degree in range(1, 8):
    h = PolyRegression(degree).fit(X_train, y_train)
    plt.plot(X1, h.predict(X1), label="d=%d" % degree);
    print "train_error(h%d) = %.2f; test_error(h%d) = %.2f" % (degree, error(h, X_train, y_train), degree, error(h, X_test, y_test))
plt.legend()
plt.show()
train_errors = []
test_errors = []
degrees = range(1,8)
for degree in degrees:
    h = PolyRegression(degree).fit(X_train, y_train)
    train_error = error(h, X_train, y_train)
    test_error = error(h, X_test, y_test)
    train_errors.append(train_error)
    test_errors.append(test_error)
plt.plot(list(degrees), train_errors, label="train_error")
plt.plot(list(degrees), test_errors, label="test_error")
plt.legend()
plt.show()
Explanation: Model koji odgovara pravoj funkciji koja je generirala podatke je $h_3$, tj. optimalan hiperparametar je $d=3$
Modeli $h_1$ i $h_2$ imaju veću pogrešku od $h_3$ i njih sigurno ne bismo uzeli
Međutim, modeli $h_4$ i $h_5$ imaju manju pogrešku od $h_3$
Očito, što je veći kapacitet modela $\mathcal{H}$, to je manja pogreška $E(h|\mathcal{D})$, $h\in\mathcal{H}$
Ali model mora moći generalizirati!
Preferiramo jednostavne modele
bolja generalizacija
lakše učenje/uporaba
lakše tumačenje
Occamova britva
<img src="http://muslimsi.com/wp-content/uploads/2014/12/quote-occam-s-razor-no-more-things-should-be-presumed-to-exist-than-are-absolutely-necessary-i-e-the-william-of-occam-372636-846x398.jpg" width="70%" align="left">
Trebamo odabrati model koji točno odgovara pravoj složenosti funkcije koju nastojimo naučiti
Dvije krajnosti:
Podnaučenost (engl. underfitting) - $\mathcal{H}$ je prejednostavan u odnosu na stvarnu funkciju $\Rightarrow$ loša klasifikacija na viđenim i neviđenim primjerima
Prenaučenost (engl. overfitting) - $\mathcal{H}$ je previše složen u odnosu na stvarnu funkciju $\Rightarrow$ loša klasifikacija na neviđenim primjerima (loša generalizacija)
[Primjer: Podnaučenost/prenaučenost kod klasifikacije]
Drugi pogled: 
Jednostavan model ima visoku pristranost (engl. high bias)
Složen model ima visoku varijancu (engl. high variance)
Odabir modela $\Rightarrow$ kompromis između pristranosti i varijance (engl. bias-variance tradeoff)
Optimalan model minimizira zajednički pristranost i varijancu
Pretpostavka induktivnog učenja
Ako je (1) pogreška hipoteze na dovoljno velikom skupu primjera za učenje mala i (2) ako model nije suviše složen, hipoteza će dobro klasificirati i nove, (3) slične primjere
Unakrsna provjera (engl. cross-validation)
Metoda za procjenu sposobnosti generalizacije modela
Skup primjera dijelimo na skup za učenje i skup za ispitivanje
 $$
    \mathcal{D} = \mathcal{D}{\mathrm{train}} \cup \mathcal{D}{\mathrm{test}}
 $$
Model učimo na skupu za učenje, a ispitujemo na skupu za ispitivanje
Primjeri iz skupa za ispitivanje model dosad nije vidio, pa na tom skupu dobivamo dobru (pravednu) procjenu pogreške generalizacije
Računamo dvije pogreške za $h\in\mathcal{H}$:
Pogreška učenja (engl. train error): empirijska pogreška hipoteze na skupu za učenje, $P(h|\mathcal{D}_{\mathrm{train}})$
Ispitna pogreška (engl. test error): empirijska pogreška hipoteze na skupu za ispitivanje, $P(h|\mathcal{D}_{\mathrm{test}})$ 
$P(h|\mathcal{D}{\mathrm{train}})$ pada sa složenošću modela, dok $P(h|\mathcal{D}{\mathrm{test}})$ tipično prvo opada a zatim raste
Optimalan model je onaj koji minimizira $P(h|\mathcal{D}_{\mathrm{test}})$
[Graf: Pogreške s obzirom na složenost modela]
Što ako želimo optimirati parametre modela?
Ne možemo to raditi na skupu za provjeru!
Trebamo još jedan skup: skup za provjeru (engl. validation set)
Tročlana particija skupa primjera:
    $$
        \mathcal{D} = \mathcal{D}{\mathrm{train}} \cup \mathcal{D}{\mathrm{val}} \cup \mathcal{D}{\mathrm{test}}
    $$
    $$
        \mathcal{D}{\mathrm{train}} \cap \mathcal{D}{\mathrm{val}} = 
        \mathcal{D}{\mathrm{train}} \cap \mathcal{D}{\mathrm{test}} =
        \mathcal{D}{\mathrm{val}} \cap \mathcal{D}_{\mathrm{test}} = \emptyset
    $$
Primjer: Regresija
End of explanation
<END_TASK>