Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva
http://www.fer.unizg.hr/predmet/su
Ak. god. 2014./2015.
(c) 2014 Jan Šnajder
Verzija 0.1
Objavljeno: 11. siječnja 2015.
Rok za predaju: 22. siječnja 2015.
Treća se laboratorijska vježba bavi modelom stroja potpornih vektora, neparametarskim modelima, vrednovanjem klasifikatora i grupiranjem. Vježba dakle pokriva sljedeće teme obrađene na predavanjima: 1. Stroj potpornih vektora, 2. Stabla odluke, 3. Učenje na temelju primjera, 4. Vrednovanje klasifikatora, 5. Grupiranje i 6. Algoritam maksimizacije očekivanja. Općenita svrha vježbe jest bolje razumijevanja rada algoritama i njihove matematičke podloge te stjecanje iskustva rada s podatcima.
Prisjetite se rada u SciPy ekosustavu. Poveznice na relevantne resurse navedene su u uvodnome dijelu prve laboratorijske vježbe.
Pročitajte relevante materijale s predavanja i po potrebi konzultirajte dodatnu literaturu:
Vježba se sastoji od više zadataka grupiranih u tri teme. U nastavku slijedite upute navedene u ćelijama s tekstom. Rješavanje vježbe svodi se na dopunjavanje ove bilježnice: umetanja ćelije ili više njih ispod teksta zadatka, pisanja odgovarajućeg koda te evaluiranja ćelija.
Molim Vas, osigurajte se da u potpunosti razumijete kod koji ste napisali. Kod predaje vježbe, morate biti u stanju na zahtjev asistenta preinačiti i ponovno evaluirati Vaš kod. Nadalje, morate razumjeti teorijske osnove onoga što radite, u okvirima onoga što smo obradili na predavanju. Stoga se nemojte ograničiti samo na to da riješite zadatak, već slobodno eksperimentirajte. To upravo i jest svrha ovih vježbi.
Vježbe trebate raditi samostalno. Možete se konzultirati s drugima o načelnom načinu rješavanja, ali u konačnici morate sami odraditi vježbu. U protivnome vježba nema smisla.
# Učitaj osnovne biblioteke...
import scipy as sp
import sklearn
%pylab inline
Kao i u drugoj vježbi, definirat ćemo malen skup podataka seven
kako bismo na takvom manjem skupu lakše analizirali ponašanje SVM-a:
seven_X = sp.array([[2,1],[2,3],[1,2],[3,2],[5,2],[5,4],[6,3]])
seven_y = sp.array([1,1,1,1,-1,-1,-1])
Funkcija za iscrtavanje skupa podataka i granice između klasa (kao i u drugoj vježbi):
def plot_problem(X, y, h=None, surfaces=True) :
'''
Plots a two-dimensional labeled dataset (X,y) and, if function h(x) is given,
the decision boundaries (surfaces=False) or decision surfaces (surfaces=True)
'''
assert X.shape[1] == 2, "Dataset is not two-dimensional"
if h!=None :
# Create a mesh to plot in
r = 0.02 # mesh resolution
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, r),
np.arange(y_min, y_max, r))
XX=np.c_[xx.ravel(), yy.ravel()]
try:
Z_test = h(XX)
if shape(Z_test) == () :
# h returns a scalar when applied to a matrix; map explicitly
Z = sp.array(map(h,XX))
else :
Z = Z_test
except ValueError:
# can't apply to a matrix; map explicitly
Z = sp.array(map(h,XX))
# Put the result into a color plot
Z = Z.reshape(xx.shape)
if surfaces :
plt.contourf(xx, yy, Z, cmap=plt.cm.Pastel1)
else :
plt.contour(xx, yy, Z)
# Plot the dataset
scatter(X[:,0],X[:,1],c=y, cmap=plt.cm.Paired,marker='o',s=50);
plot_problem(seven_X, seven_y)
from sklearn.svm import SVC
Primijenite model SVC
s linearnom jezgrenom funkcijom (tj. bez preslikavanja primjera u prostor značajki) na skup podataka seven
. Prikažite dobivenu granicu između klasa, ispišite koeficijente $w_0$ i $\mathbf{w}$ te izračunajte širinu margine. Ispišite dualne koeficijente i potporne vektore.
Prisjetite se da $h(\mathbf{x})=\tilde{\mathbf{w}}^\intercal\tilde{\mathbf{x}}$ odgovara udaljenosti primjera $\mathbf{x}$ od granice definirane sa $h(\mathbf{x})=0$. Provjerite da je upravo to vrijednost koju izračunava funkcija svm.decision_function
. Preinačite funkciju plot_problem
tako da, uz granicu između klasa, prikazuje i marginu.
Q: Koliko iznosi širina margine i zašto?
Q: Koji su primjeri potporni vektori i zašto?
Izraz (7.7) u skripti opisuje vezu između predikcije modela u primarnoj i dualnoj formulaciji problema maksimalne margine:
\begin{equation} h(\mathbf{x})=\mathbf{w}^\intercal\mathbf{x}+w_0 = \sum_{i=1}^N \alpha_i y^{(i)}\mathbf{x}^\intercal\mathbf{x} + w_0 \end{equation}Definirajte funkcije h_primal(x,w,w0)
i h_dual(x,X,y,dc,sv)
koje implementiraju predikciju u primarnoj odnosno dualnoj formulaciji problema, pri čemu su (w,w0)
težine, (X,y)
označen skup primjera, dc
su dualni koeficijenti, sv
su indeksi potpornih vektora (koji su pohranjeni u svc.support_
), a x
je primjer za koji se radi predikcija. Također implementirajte funkciju w0(X,y,dc,sv)
koja izračunava težinu w_0
pomoću izraza (7.8) iz skripte. Uvjerite se da ove dvije funkcije na skupu seven
funkcije daju identične predikcije i da su one identične onima koje daje ugrađena funkcija svc.decision_function
.
NB: Dualni koeficijenti koje vraća svc.dual_coef_[0]
ne odgovaraju Lagrangeovim multiplikatorima $\alpha_i$ već vrijednostima $-\alpha_i y^{(i)}$.
Q: Jedan od triju potpornih vektora na skupu seven
je suvišan. Koji? Uvjerite se da h_dual
daje identične predikcije i bez tog vektora.
Trenirajte na skupu seven
tri linearna modela -- perceptron, logističku regresiju i linearni SVM -- te prikažite dobivenu granicu između klasa za sva tri modela.
from sklearn.linear_model import Perceptron, LogisticRegression
Zatim ponovite treniranje na skupu s dodatnim, osmim primjerom koji odskače te prikažite opet dobivene granice između klasa za sva tri modela.
X = sp.append(seven_X,[[12,8]],axis=0)
y = sp.append(seven_y,-1)
Definirajte funkciju hinge(model,x,y)
koja izračunava gubitak zglobnice modela SVM na primjeru x
. Izračunajte prosječni gubitak SVM-a na skupovima seven
i skupu s dodatnim primjerom. Uvjerite se da je rezultat identičan onome koji biste dobili primjenom ugrađene funkcije metrics.hinge_loss
.
from sklearn.metrics import hinge_loss
Q: Jesu li rezultati očekivani? Obrazložite.
Razmotrimo sljedeće dvije varijante problema seven
, svaka s osam primjera:
X1, y1 = sp.append(seven_X, [[3,3]], axis=0), sp.append(seven_y, -1)
X2, y2 = sp.append(seven_X, [[2,2]], axis=0), sp.append(seven_y, -1)
Na svakom od ova dva skupa trenirajte linearni SVM, mijenjajući parametar $C$ koji određuje složenost modela, $C\in\{10^{-2},1,10^2\}$. Za svaki naučeni model prikažite granicu između klasa, ispišite širinu margine, potporne vektore te prosječan gubitak zglobnice.
Q: Komentirajte dobivene rezultate.
Q: Zašto šira margina rezultira većim prosječnim gubitkom?
Trenirajte linearni SVM na skupu seven
te skupovima (X1,y1)
i (X2,y2)
iz prethodnoga zadatka, mijenjajući parametar $C$ po vrijednostima $C\in\{2^{-5},2^{-4},\dots,2^2,2^3\}$. Prikažite krivulju pogreške zglobnice i L2-normu vektora težina u ovisnosti o parametru $C$ na sva tri skupa podataka (tri grafikona).
Q: Koji dio grafikona odgovara prenaučenosti a koji podnaučenosti modela?
Na skupu (X2,y2)
iz zadatka A.4 trenirajte tri modela SVM s različitim jezgrenim funkcijama: linearna, polinomijalna i radijalna bazna (RBF) funkcija. Varirajte parametar $C$ po vrijednostima $C\in\{10^{-2},1,10^2\}$, dok za ostale parametre (stupanj polinoma za polinomijalnu jezgru odnosno parametar $\gamma$ za jezgru RBF) koristite podrazumijevane vijednosti. Prikažite granice između klasa (i margine) na grafikonu organiziranome u polje $3x3$, gdje su stupci različite jezgre, a retci različite vrijednosti parametra $C$.
Pored hiperparametra $C$, model SVM sa jezgrenom funkcijom RBF ima i dodatni hiperparametar $\gamma=\frac{1}{2\sigma^2}$ (preciznost). Taj parametar također određuje složenost modela: velika vrijednost za $\gamma$ znači da će RBF biti uska, primjeri će biti preslikani u prostor u kojem su (prema skalarnome produktu) međusobno vrlo različiti, što će rezultirati složenijim modelima. Obrnuto, mala vrijednost za $\gamma$ znači da će RBF biti široka, primjeri će biti međusobno sličniji, što će rezultirati jednostavnijim modelima. To ujedno znači da, ako odabremo veći $\gamma$, trebamo jače regularizirati model, tj. trebamo odabrati manji $C$, kako bismo spriječili prenaučenost. Zbog toga je potrebno zajednički optimirati hiperparametre $C$ i $\gamma$, što se tipično radi iscrpnim pretraživanjem po rešetci (engl. grid search).
Definirajte funkciju grid_search(model,X_train,X_validate,y_train,y_validate,(c1,c2),(g1,g2),error_surface=False)
koja optimizira parametre $C$ i $\gamma$ pretraživanjem po rešetci. Funkcija treba pretražiti parametre $C\in\{2^{c_1},2^{c_1+1},\dots,2^{c_2}\}$ i $\gamma\in\{2^{g_1},2^{g_1+1},\dots,2^{g_2}\}$. Funkcija treba vratiti optimalne parametre $(C^*,\gamma^*)$, tj. one koji na skupu za provjeru ostvaruju najmanju pogrešku. Dodatno, ako je surface=True
, funkcija treba vratiti dvije matrice (tipa ndarray
) koje pohranjuju pogreške modela (očekivanje gubitka 0-1) na skupu za učenje odnosno skupu za provjeru za svaku kombinaciju parametara $(C,\gamma)$. Svaka je matrica dimenzija $(c_2-c_1+1)\times(g_2-g_1+1)$ (retci odgovaraju različitim vrijednostima za $C$, a stupci različitim vrijednostima za $\gamma$).
Pomoću funkcije datasets.make_classification
generirajte dva skupa podataka od $N=200$ primjera: jedan s $n=2$ dimenzije i drugi s $n=1000$ dimenzija. Primjeri neka dolaze iz dviju klasa, s time da svakoj klasi odgovaraju dvije grupe (n_clusters_per_class=2
), kako bi problem bio nešto složeniji, tj. nelinearniji. Podijelite skup primjera na skup za učenje i skup za ispitivanje u omjeru 1:1.
from sklearn.datasets import make_classification
from sklearn.cross_validation import train_test_split
Na oba skupa optimirajte SVM s jezgrenom funkcijom RBF, u rešetci $C\in\{2^{-5},2^{-4},\dots,2^{15}\}$ i $\gamma\in\{2^{-15},2^{-14},\dots,2^{3}\}$. Prikažite površinu pogreške modela na skupu za učenje i skupu za provjeru, i to na oba skupa podataka (ukupno četiri grafikona) te ispišite optimalne kombinacije hiperparametra. Prikažite i granicu između klasa za dvodimenzijski skup. Za prikaz površine pogreške modela možete koristiti sljedeću funkciju:
def plot_error_surface(err,(c1,c2),(g1,g2)) :
xticks(range(0,g2-g1+1,5),range(g1,g2,5)); xlabel("gamma")
yticks(range(0,c2-c1+1,5),range(c1,c2,5)); ylabel("C")
p = contour(err);
imshow(1-err, interpolation='bilinear', origin='lower',cmap=cm.gray)
clabel(p, inline=1, fontsize=10);
show();
Q: Razlikuje li se površina pogreške na skupu za učenje i skupu za ispitivanje? Zašto?
Q: U prikazu površine pogreške, koji dio površine odgovara prenaučenosti a koji podnaučenosti? Zašto?
Q: Koliko su ovi rezultati stabilni s obzirom na skup podataka? Pokažite.
Q: Kako broj dimenzija $n$ utječe na površinu pogreške odnosno na optimalne hiperparametre $(C^*, \gamma^*)$?
Q: Preporuka je da povećanje vrijednosti za $\gamma$ treba biti popraćeno smanjenjem vrijednosti za $C$. Govore li vaši rezultati u prilog toj preporuci? Obrazložite.
Q: Podrazumijevana vrijednost parametara je $C=1$ i $\gamma=1/n$. Bi li te vrijednosti bile optimalne u ovom slučaju?
Model s jezgrenom funkcijom (pogotovo RBF) je nelinearan, pa je u praksi (uz propisnu optimizaciju hiperparametra) za većinu problema bolji izbor nego linearan model. Međutim, za probleme kod kojih je broj dimenzija $n$ znatno veći od broja primjera $N$, linearan model može biti jednako dobar, jer tada postaje razmjerno lako i hiperravninom razdvojiti primjere u ulaznome prostoru. S druge strane, kod problema kod kojih je broj značajki znatno manji od broja primjera, vjerojatnije je da je problem nelinearan, pa je bolje koristiti SVM s jezgrenom funkcijom. Svrha ovog zadatka jest empirijski provjeriti je li to stvarno slučaj.
Pomoću datasets.make_classification
generirajte dva dvoklasna skupa podataka: jedan sa $N=1000$ primjera i $n=2$ značajki te drugi sa $N=100$ primjera i $n=1000$ značajki. Svaki skup podijelite na skup za učenje i skup za provjeru u omjeru 1:1. Na skupovima za treniranje trenirajte dva modela: linearan SVM i SVM s jezgrenom funkcijom RBF. Na skupovima za provjeru napravite optimizaciju hiperparametra $C$ (za linearan model) odnosno hiperparametara $C$ i $\gamma$ (za nelinearan model), koristeći grid_search
i raspone pretraživanja iz prethodnog zadatka (za optimizaciju samo parametra $C$ stavite (g1,g2)=(1,1)
). Ispišite točnost obaju modela na skupu za učenje i na skupu za provjeru. Kako biste dobili robusnije procjene točnosti, eksperiment možete ponoviti više puta (npr. 5, 10 ili 30) te uprosječiti rezultate (u tom slučaju unutar petlje svaki puta nanovo generirajte oba skupa podataka).
NB: Ne zaboravite nanovo optimizirati hiperparametre na svakom generiranom skupu. Ako ponavljate postupak, imajte na umu da je zbog pretraživanja po rešetci on računalno zahtjevan, te da je treniranje modela s više značajki sporije.
from sklearn.datasets import make_classification
from sklearn.cross_validation import train_test_split
Q: Jesu li rezultati očekivani? Obrazložite.
Q: Prema Coverovom teoremu, preslikavanjem problema u prostor više dimenzije povećava se vjerojatnost da je problem linearno odvojiv. Ako je to doista tako, zašto linearan model u ovom eksperimentu za slučaj kada $n\gg N$ ostvaruje manju točnost nego za slučaj kada $N\gg n$?
Za mnoge je modele bitno prije treniranja skalirati značajke, kako bi se spriječilo da značajke s većim numeričkim rasponima dominiraju nad onima s manjim numeričkim rasponima. To vrijedi i za SVM, kod kojega skaliranje nerijetko može znatno poboljšati rezultate. Svrha ovog zadataka jest eksperimentalo utvrditi utjecaj skaliranja značajki na točnost SVM-a.
Generirat ćemo dvoklasni skup od $N=500$ primjera s $n=2$ značajke, tako da je dimenzija $x_1$ većeg iznosa i većeg raspona od dimenzije $x_0$, te ćemo dodati jedan primjer koji vrijednošću značajke $x_1$ odskače od ostalih primjera:
from sklearn.datasets import make_classification
X, y = make_classification(n_samples=500,n_features=2,n_classes=2,n_redundant=0,n_clusters_per_class=1)
X[:,1] = X[:,1]*100+1000
X[0,1] = 3000
plot_problem(X,y)
Proučite klase preprocessing.StandardScaler
i preprocessing.MinMaxScaler
. Proučite funkciju za iscrtavanje histograma hist
. Prikažite histograme vrijednosti značajki $x_0$ i $x_1$ i to za neskalirane (izvorne) značajke, značajke skalirane standardizacijom i značajke skalirane min-max skaliranjem (ukupno šest histograma).
from sklearn.preprocessing import StandardScaler, MinMaxScaler
Podijelite skup primjera na skup za učenje i skup za ispitivanje u omjeru 1:1. Trenirajte SVM s jezgrenom funkcijom RBF na skupu za učenje i ispitajte točnost modela na skupu za ispitivanje, koristeći tri varijante gornjeg skupa: neskalirane značajke, standardizirane značajke i min-max skaliranje. Koristite podrazumijevane vrijednosti za $C$ i $\gamma$. Izmjerite točnost svakog od triju modela na skupu za učenje i skupu za ispitivanje. Ponovite postupak više puta (npr. 30) te uprosječite rezultate.
NB: Kod skaliranja značajki treba paziti da ne dođe do "curenja informacija" sa skupa za učenje na skup za ispitivanje. Na skupu za učenje treba najprije izračunati parametre skaliranja te zatim primijeniti skaliranje (funkcija fit_transform
), dok na skupu za ispitivanje treba samo primijeniti skaliranje s parametrima koji su dobiveni na skupu za učenje (funkcija transform
).
Q: Jesu li rezultati očekivani? Obrazložite.
Q: Bi li bilo dobro kada bismo funkciju fit_transform
primijenili na cijelom skupu podataka? Zašto? Bi li bilo dobro kada bismo tu funkciju primijenili zasebno na skupu za učenje i zasebno na skupu za ispitivanje? Zašto?
Kao i sve binarne klasifikatore, SVM je moguće primijeniti na višeklasifikacijski problem transformacijom problema u skup binarnih problema te primjenom sheme OVO ili OVR. U slučaju da je problem višeklasan, standardna implementacija svm.SVC
to automatski prepoznaje i primjenjuje shemu OVO. Generirajte četveroklasni skup primjera, trenirajte SVM s rezgrenom funkcijom RBF i podrazumijevanim vrijednostima za $C$ i $\gamma$ te prikažite dobivene rezultate.
Q: Koliko je binarnih klasifikatora trenirano u ovom slučaju?
Q: Što su prednosti a što nedostatci sheme OVO nad shemom OVR? Što mislite, zašto je shema OVO bolji izbor za SVM od sheme OVR?
Preuzmite Glass Identification Data Set
, koji opisuje rezultate kemijske analize 214 stakala. Riječ je o klasifikacijskom problemu sa šest klase: na temelju 9 kemijskih značajki stakla potrebno je, u svrhu forenzičke analize, odrediti o kojoj se od šest vrsta stakla radi. Skup podataka možete učitati na sljedeći način:
data = sp.loadtxt("/home/jan/Downloads/glass.data", delimiter=",")
glass_X, glass_y = data[:,1:10], data[:,10]
Skup zatim podijelite na skup za učenje i skup za ispitivanje u omjeru 2:1, kako slijedi:
from sklearn import cross_validation
X_train, X_test, y_train, y_test = cross_validation.train_test_split(glass_X,glass_y,train_size=2.0/3,random_state=42)
print X_train.shape, X_test.shape
Na skupu za učenje trenirajte dva modela: SVM s linearnom jezgrenom funkcijom i SVM s jezgrenom funkcijom RBF. Optimizaciju hiperparametara načinite pretraživanjem po rešetci na skupu za provjeru, koji ćete dobiti dodatnom podjelom skupa za učenje, dok točnost modela ispitajte na skupu za ispitivanje. Napravite standardizaciju značajki uvažavajući spoznaje iz zadatka A.9. Ispišite točnost obaju modela na skupu za učenje i na skupu za ispitivanje.
Q: Možete li reći koliko značajki ima vaš najbolji model (u prostoru značajki)?
Q: Koliko potpornih vektora ima vaš najbolji model i koliki je to udio od ukupnog broja primjera?
Q: Usporedite točnost modela na skupu za učenje i na skupu za ispitivanje. Što možete zaključiti na temelju te usporedbe?
Q: Usporedite točnost najboljeg linearnog i najboljeg nelinearnog modela. Što možete zaključiti na temelju te usporedbe?
Q: Usporedite točnost najboljeg modela s točnoću linearne regresije (zadatak C.11 iz druge vježbe). Što možete zaključiti na temelju te usporedbe?
Q: Na koliko je primjera naučen klasifikator koji ste u konačnici ispitali? Vidite li problem u tome što nisu iskorišteni svi primjeri? Kako biste riješili taj problem?