Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva
http://www.fer.unizg.hr/predmet/su
Ak. god. 2015./2016.
(c) 2015 Jan Šnajder
Verzija: 0.7 (2015-10-21)
import scipy as sp
import scipy.stats as stats
import matplotlib.pyplot as plt
from numpy.random import normal
%pylab inline
Populating the interactive namespace from numpy and matplotlib
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
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)
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 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:
Matrica $\mathcal{D}$ sastavljena je od matrice $\mathbf{X}_{N\times n}$ i vektora $\mathbf{y}_{N\times 1}$
Hipoteza: $h : \mathcal{X} \to \mathcal{Y}$
Binarna klasifikacija: $h : \mathcal{Y} \to \{0, 1\}$
Općenitije: $h(\mathbf{x} | \theta)$
Model $\mathcal{H}$: skup hipoteza $h$
Formalno: $\mathcal{H} = \big\{ h(\mathbf{x} | \theta)\big\}_{\theta}$
Učenje (treniranje modela) svodi se na pretraživanje prostora hipoteza $\mathcal{H}$ i nalaženje najbolje hipoteze $h\in \mathcal{H}$
[Primjer: Ulazni prostor + prostor parametara]
$\mathcal{H}$ je vrlo velik, pa nam često treba heuristička optimizacija
Iskazuje koliko točno hipoteza klasificira primjere (klasifikacija) ili koliko su vrijednosti blizu ciljnih vrijednosti (regresija)
Pogreška klasifikacija (engl. misclassification error):
[Primjer]
Vrijednost pogreške načinjene na pojedinačnom primjeru (funkcija unutar sume) zove se funkcija gubitka (engl. loss function)
$\mathit{VS}_{\mathcal{H},\mathcal{D}} \subseteq \mathcal{H}$
Skup hipoteza iz $\mathcal{H}$ koje su konzistentne s primjerima za učenje $\mathcal{D}$
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]
Učenje hipoteze je loše definiran problem: $h$ ne slijedi deduktivno iz $\mathcal{D}$
Primjer 1: Učenje Booleove funkcije
$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
Induktivna pristranost (engl. inductive bias)
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:
Razmotrimo opet Primjer 1, uz $\mathcal{H} = \text{skup ravnina u $\mathbb{R}^3$}$
(1) Model $\mathcal{H}$
(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:
Funkcija pogreške definirana je kao očekivana vrijednost funkcije gubitka na primjerima iz $\mathcal{X}\times\mathcal{Y}$
(3) Optimizacijski postupak
tj. $$ \theta^* = \mathrm{argmin}_{\theta} E(\theta|\mathcal{D}) $$
Optimizacija može biti analitička ili heuristička
Gornje tri komponente definiraju i induktivnu pristranost svakog algoritma
$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:
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)
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:
def h(x, w): return w[1] * x + w[0]
(2) Funkcija gubitka (i njoj odgovarajuća funkcija pogreške):
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
Funkcija koja generira podatke (i koju zapravo želimo naučiti):
def f(x): return 3 * x + 2
xs = sp.linspace(0, 10)
plt.plot(xs, f(xs));
Skup primjera za učenje $\mathcal{D}=(\mathbf{X},\mathbf{y})$ dobiven je iz $f(x)$, uz dodatan šum:
X = linspace(0, 10)
y = f(X) + 2 * stats.norm.rvs(scale=3, size=50)
X
array([ 0. , 0.20408163, 0.40816327, 0.6122449 , 0.81632653, 1.02040816, 1.2244898 , 1.42857143, 1.63265306, 1.83673469, 2.04081633, 2.24489796, 2.44897959, 2.65306122, 2.85714286, 3.06122449, 3.26530612, 3.46938776, 3.67346939, 3.87755102, 4.08163265, 4.28571429, 4.48979592, 4.69387755, 4.89795918, 5.10204082, 5.30612245, 5.51020408, 5.71428571, 5.91836735, 6.12244898, 6.32653061, 6.53061224, 6.73469388, 6.93877551, 7.14285714, 7.34693878, 7.55102041, 7.75510204, 7.95918367, 8.16326531, 8.36734694, 8.57142857, 8.7755102 , 8.97959184, 9.18367347, 9.3877551 , 9.59183673, 9.79591837, 10. ])
len(_)
50
y
array([ 0.67064434, 7.31239169, 9.56400499, 0.2890283 , 6.96746129, 14.86178311, 12.60975181, -0.28934441, 6.44890713, 7.28992995, 13.72389263, 19.61341887, 15.62669111, 14.43066191, 8.76710654, 19.48489724, -1.27170224, 10.81539578, 21.36130674, 14.3632114 , 14.6825962 , 12.37886072, 5.04860612, 27.01349903, 14.15906195, 8.62295154, 16.36435167, 15.92878647, 12.01783068, 25.11064324, 24.71867488, 25.64192171, 21.53657671, 26.70048261, 30.36258764, 22.37268596, 27.29906374, 32.14498482, 12.14117217, 16.54494565, 32.29949169, 13.98599392, 26.27138558, 28.5969641 , 29.10679964, 26.91455084, 32.36537598, 31.40052367, 29.39580935, 23.59296505])
plt.plot(xs, f(xs), '--')
plt.scatter(X, y)
plt.show()
/usr/local/lib/python2.7/dist-packages/matplotlib/collections.py:590: FutureWarning: elementwise comparison failed; returning scalar instead, but in the future will perform elementwise comparison if self._edgecolors == str('face'):
Dvije hipoteze iz našeg modela:
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();
Empirijske pogreške hipoteza na skupu $\mathcal{D}$:
error(h1, X, y)
5025.9784792784731
error(h2, X, y)
2156.5878715137965
(3) Optimizacijski postupak
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
2.82127363032 2.57918900236
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)
892.91671935457725
ili četvrtog stupnja: $$ h_4(x) = w_4 x^4 + w_3 x^3 + w_2 x^2 + w_1 x + w_0 $$
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)
885.87751643487434
error(h4, X, y)
845.62372708741623
Q: Zašto?
Q: Koji model odabrati u ovom slučaju?
Q: Koji model općenito odabrati za neke podatke $\mathcal{D}$?
Šum je neželjena anomalija u podacima
Mogući uzroci:
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
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 **
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()
error(h1) = 45943.12 error(h2) = 12409.02 error(h3) = 4554.71 error(h4) = 4480.06 error(h5) = 4262.50 error(h6) = 3971.45 error(h7) = 3663.57
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
Occamova britva
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:
Pretpostavka induktivnog učenja
Metoda za procjenu sposobnosti generalizacije modela
$$ \mathcal{D} = \mathcal{D}_{\mathrm{train}} \cup \mathcal{D}_{\mathrm{test}} $$
Računamo dvije pogreške za $h\in\mathcal{H}$:
$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 $$
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)
(30, 20)
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_error(h1) = 29464.92; test_error(h1) = 17336.67 train_error(h2) = 7791.35; test_error(h2) = 4718.77 train_error(h3) = 3002.65; test_error(h3) = 1657.94 train_error(h4) = 2912.17; test_error(h4) = 1787.16 train_error(h5) = 2612.13; test_error(h5) = 1754.30 train_error(h6) = 2158.16; test_error(h6) = 2150.77 train_error(h7) = 1937.27; test_error(h7) = 1916.90
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()
Pogled na problem optimizacije modela iz statističke teorije učenja
Rizik = očekivanje gubitka = pogreška hipoteze
Empirijski rizik $R_{\mathrm{emp}}$ = procjena pogreške na skupu primjera, $E(h|\mathcal{D})$
Strukturni rizik $R_{\mathrm{struct}}$ = kvantifikacija složenosti modela
Želimo modele $\mathcal{H}$ koji (za naučenu $h\in\mathcal{H}$) minimiziraju i empirijski i strukturni rizik
gdje $\lambda$ definira važnost empirijskog rizika u odnosu na strukturni
[Grafikon: empirijska + strukturna pogreška]
Dakle, umjesto minimizacije
imamo $$ h^* = \mathrm{argmin}_{h\in\mathcal{H}} E(h|\mathcal{D}) + \lambda R_{\mathrm{struct}}(h) $$
Minimizacija strukturnog rizika je alternativa unakrsnoj provjeri
U praksi ipak koristimo unakrsnu provjeru (jer je pouzdanija)
Često kombiniramo unakrsnu provjeru s minimizacjom strukturnog rizika (tzv. regularizacija)
Hipoteza je funkcija koja klasificira primjere (kod klasifikcije) ili daje brojčanu vrijednost (kod regresije), a model je skup hipoteza
Različiti modeli imaju različite složenosti (kapacitete)
Učenje nije moguće bez induktivne pristranosti, koja može pristranost jezika ili pristranost preferencijom
Svaki algoritam SU ima tri komponente: model, funkciju gubitka i optimizacijski postupak
Empirijsku pogrešku hipoteze izračunavamo kao očekivanje funkcije gubitka na skupu primjera
Učenje modela svodi se na optimizaciju parametara modela s empirijskom pogreškom kao kriterijem
Model koji je podnaučen ili prenaučen loše generalizira
Odabir modela svodi se na optimiranje hiperparametara modela
Unakrsnom provjerom možemo procijeniti pogreška generalizacije i odabrati optimalan model