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.1 (2015-11-11)
import scipy as sp
import scipy.stats as stats
import matplotlib.pyplot as plt
import pandas as pd
%pylab inline
Populating the interactive namespace from numpy and matplotlib
Uvod
Poopćeni linearni model
Geometrija linearnog modela
Višeklasna klasifikacija
Klasifikacija regresijom
Gradijentni spust
Perceptron
Sažetak
$ P(\mathcal{C}_j|\mathbf{x})\ \propto\ P(\mathbf{x}|\mathcal{C}_j) P(\mathcal{C}_j) $, modeliramo:
izravno aposteriornu vjerojatnost klase, $P(\mathcal{C}_j|\mathbf{x})$, ili
izravno diskriminacijsku (klasifikacijsku) funkciju $h(\mathbf{x})$
Linearan modeli: Granica je linearna (hiperravnina):
prostoru
Granica je hiperravnina za koju $h(\mathbf{x})=0$ ili $h(\mathbf{x})=0.5$ (ovisno o modelu)
Granicu zovemo diskriminativna funkcija (engl. discriminative functions) ili granica odluke, decizijska granica (engl. decision boundary)
def h(x, w): return sp.dot(x, w)
def plot_decision_boundary(h, boundary=0, margins=None):
x = linspace(-10, 10)
y = linspace(-10, 10)
X1, X2 = np.meshgrid(x, y)
XX = sp.dstack((sp.ones((50, 50)), X1, X2))
plt.contour(X1, X2, h(XX), linecolor='red', levels=[boundary])
if margins!=None:
CS = plt.contour(X1, X2, h(XX), colors=['gray', 'gray'], levels=[margins[0],margins[1]])
plt.clabel(CS, fontsize=9, inline=1)
w = [-2, 1, -0.5]
plot_decision_boundary(lambda x : h(x, w), margins=(-1,1))
w = [2, -1, 0.5]
plot_decision_boundary(lambda x : h(x, w), margins=(-1,1))
w = [2, -1.5, 0.3]
plot_decision_boundary(lambda x : h(x, w), margins=(-1,1))
ili $$ f:\mathbb{R}\to[-1,1] $$
$\Rightarrow$ Linearna granica u ulaznom prostoru (premda je $f$ nelinearna)
$\Rightarrow$ Model je nelinearan u parametrima (jer je $f$ nelinearna)
xs = sp.linspace(-5,5, 100)
plt.plot(xs, xs);
def sigm(x): return 1 / (1 + sp.exp(-x))
plt.plot(xs, sigm(xs));
plt.plot(xs, sign(xs));
w = [-4, 2, -1]
plot_decision_boundary(lambda x : h(x, w), margins=(-1,1))
plot_decision_boundary(lambda x : sigm(sp.dot(x, w)), boundary=0.5, margins=(0.1,0.9))
Kao i kod regresije, možemo koristiti preslikavanje $\boldsymbol{\phi}:\mathbb{R}^n\to\mathbb{R}^m$ iz ulaznog prostora u prostor značajki:
$$ h(\mathbf{x}) = f\big(\mathbf{w}^\intercal\mathbf{\phi}(\mathbf{x})\big) $$$\Rightarrow$ Linearna granica u prostoru značajki
$\Rightarrow$ Nelinearna granica u ulaznom prostoru
$\Rightarrow$ Model je nelinearan u parametrima (jer je $f$ nelinearna)
def h2(x, w):
x2 = sp.dstack((x, x[:,:,1]*x[:,:,2], x[:,:,1]**2, x[:,:,2]**2))
return sp.dot(x2, w)
w = [-0.05 , -0.15 , -0.5 , 0.15 , -0.08 , 0.05]
plot_decision_boundary(lambda x : h2(x, w), margins=[-1, 1])
[Skica]
Za točke $\mathbf{x}_1$ i $\mathbf{x}_2$ na hiperravnini:
$\Rightarrow$ $\mathbf{w}$ je normala hiperravnine
NB: U iduće dvije točke $\mathbf{w}$ ne uključuje $w_0$
Za točku $\mathbf{x}$ na hiperravnini:
$\Rightarrow$ udaljenost ravnine od ishodišta je $-w_0/\|\mathbf{w}\|$
$\Rightarrow$ udaljenost točke $\mathbf{x}$ od ravnine je $d=h(\mathbf{x})/\|\mathbf{w}\|$
w = sp.array([-4, 2, -1])
X = sp.array([[1, 5, -1],
[1, -5, 5]])
plot_decision_boundary(lambda x : h(x, w), margins=(-1, 1))
plt.scatter(X[:,1],X[:,2]);
h(X[0], w)
7
h(X[1], w)
-19
sp.linalg.norm(w[1:])
2.2360679774997898
def distance(x,w): return sp.dot(x, w) / sp.linalg.norm(w[1:])
distance(X[0], w)
3.1304951684997055
distance(X[1], w)
-8.4970583144992009
w2 = w/10.0
plot_decision_boundary(lambda x : h(x, w2), margins=(-1,1))
plt.scatter(X[:,1],X[:,2]);
h(X[0], w2)
0.69999999999999996
h(X[1], w2)
-1.8999999999999999
sp.linalg.norm(w2[1:])
0.223606797749979
distance(X[0], w2)
3.1304951684997051
distance(X[1], w2)
-8.4970583144991991
gdje $h_{ji}(\mathbf{x})=- h_{ij}(\mathbf{x})$
[Skica: OVO]
Shema jedan-naspram-ostali (engl. one-vs-rest, OVR, one-vs-all)
[Skica: OVR]
Prednost OVR nad OVO je da imamo manje modela, međutim OVR lako rezultira neuravnoteženim brojem primjera kroz klase
h1 = lambda x: h(x, [0, 2, 1])
plot_decision_boundary(h1)
h2 = lambda x: h(x, [-0.2, 0.7, -0.8])
plot_decision_boundary(h2)
h3 = lambda x: h(x, [-1.5, 0.1, 0.5])
plot_decision_boundary(h3)
plt.scatter(X[:,1],X[:,2]);
print h1(X[0]), h2(X[0]), h3(X[0])
9 4.1 -1.5
print h1(X[1]), h2(X[1]), h3(X[1])
-5 -7.7 0.5
def ovr(x): return sp.argmax([h1(x), h2(x), h3(x)])
ovr(X[0])
0
ovr(X[1])
2
x = linspace(-10, 10)
y = linspace(-10, 10)
X1, X2 = np.meshgrid(x, y)
XX = sp.dstack((sp.ones((50, 50)), X1, X2))
n, m, _ = shape(XX)
YY = sp.zeros((n,m))
for i in range(0,n):
for j in range(0,m):
YY[i,j] = ovr(XX[i, j])
plt.contourf(X1, X2, YY);
[Skica]
Funkcija pogreške (empirijsko očekivanje kvadratnog gubitka):
Ideja: regresijska funkcija $h(\mathbf{x})$ koja za primjere iz klase $\mathcal{C}_1$ daje $h(\mathbf{x})=1$, a za primjere iz klase $\mathcal{C}_2$ daje $h(\mathbf{x})=0$
Primjer $\mathbf{x}$ klasificiriamo u klasu $\mathcal{C}_j$ za koju je $h(\mathbf{x})$ najveći
Granica između $\mathcal{C}_1$ i $\mathcal{C}_2$ je na $h(\mathbf{x})=0.5$
Primjer za $n=1$
Primjer za $n=2$
Alternativno, model možemo trenirati tako da za primjere iz klase $\mathcal{C_2}$ bude ciljana vrijednost bude $y=-1$
Shema jedan-naspram-ostali (OVR)
Treniramo po jedan model $h_j$ za svaku klasu $\mathcal{C}_j$
[Primjer]
Rješenje koje minimizira kvadratnu pogrešku:
Prednosti:
Nedostatci:
[Primjer]
Diskriminativni linearni modeli modeliraju granicu između klasa, ali ne i način generiranja primjera
Poopćeni linearan model je linearan model s aktivacijskom funkcijom
Klasifikacija regresijom je jednostavan postupak, ali nije robusan
Konveksna optimizacija važna je za strojno učenje jer je funkcija gubitka (a time i funkcija pogreške) tipično konveksna
Ako minimizacija pogreške nema rješenje u zatvorenoj formi, a možemo izračunati gradijent, onda možemo primijeniti gradijentni spust
Perceptron je linearan klasifikacijski model koji gradijentnim spustom mimimizira aproksimaciju broja pogrešnih klasifikacija
Perceptron ne konvergira za linearno nedvojive probleme, dok za linearno odvojive rješenje ovisi o inicijalizaciji i redoslijedu primjera
Niti regresija niti perceptron ne daju probabilistički izlaz