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.3 (2015-11-09)
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
Osnovni pojmovi
Model, funkcija gubitka i optimizacijski postupak
Postupak najmanjih kvadrata
Probabilistička interpretacija regresije
Poopćeni linearan model regresije
Odabir modela
Regularizirana regresija
Sažetak
Označen skup podataka: $\mathcal{D}=\{(\mathbf{x}^{(i)},y^{(i)})\},\quad \mathbf{x}\in\mathbb{R}^n,\quad y\in\mathbb{R}$
Hipoteza $h$ aproksimira nepoznatu funkciju $f:\mathbb{R}^n\to\mathbb{R}$
Idealno, $y^{(i)}=f(\mathbf{x}^{(i)})$, ali zbog šuma: $$y^{(i)}=f(\mathbf{x}^{(i)})+\varepsilon$$
$\mathbf{x}$ - ulazna varijabla (nezavisna, prediktorska)
$y$ - izlazna varijabla (zavisna, kriterijska)
Broj ulaznih (nezavisnih) varijabli:
Broj izlaznih (zavisnih) varijabli:
$\mathbf{w} = (w_0,\dots,w_n)$
Linearna regresija: $$h(\mathbf{x}|\mathbf{w}) = w_0 + w_1 x_1 + w_2 x_2 + \dots + w_n x_n$$
Polinomijalna regresija:
Općenite bazne funkcije: $$h(\mathbf{x}|\mathbf{w}) = w_0 + w_1\phi_1(\mathbf{x}) + \dots + w_m\phi_m(\mathbf{x})$$
Matricu primjera $\mathbf{X}$ zovemo dizajn-matrica
Vektor izlaznih vrijednosti:
odnosno $$ (\mathbf{x}^{(i)}, y^{(i)})\in\mathcal{D}.\ \mathbf{w}^\intercal \mathbf{x} = y^{(i)} $$
Međutim, rješenja nema ili ono nije jedinstveno ako:
(1) $\mathbf{X}$ nije kvadratna, pa nema inverz. U pravilu:
(2) $\boldsymbol{X}$ jest kvadratna (tj. $N=(n+1)$), ali ipak nema inverz (ovisno o rangu matrice)
$\Rightarrow$ sustav je nekonzistentan
Približno rješenje sustava $\mathbf{X}\mathbf{w}=\mathbf{y}$
Funkcija pogreške:
Jednakosti linearne algebre:
- $(A^\intercal)^\intercal = A$
- $(AB)^\intercal = B^\intercal A^\intercal$
Jednakosti linearne algebre:
- $\frac{\mathrm{d}}{\mathrm{d}x}x^\intercal A x=x^\intercal(A+A^\intercal)$
- $\frac{\mathrm{d}}{\mathrm{d}x}A x=A$
Matrica $\mathbf{X}^{+}=(\mathbf{X}^\intercal\mathbf{X})^{-1}\mathbf{X}^\intercal$ je pseudoinverz (Moore-Penroseov inverz) matrice $\mathbf{X}$
Q: Kojih je dimenzija matrica $(\mathbf{X}^\intercal\mathbf{X})^{-1}$?
Q: Što utječe na složenost izračuna inverza matrice: broj primjera $N$ ili broj dimenzija $n$?
odnosno $$ \color{red}{p(y|x)} = \mathcal{N}\big(f(x), \sigma^2\big) $$
Naš cilj je: $h(x|\mathbf{w}) = f(x)$
[Skica]
$p(y^{(i)}|x^{(i)})$ je vjerojatnost da je $f(x^{(i)})$ generirala vrijednost $y^{(i)}$
$\Rightarrow$ Probabilističko opravdanje za kvadratnu funkciju gubitka
Rješenje MLE jednako je rješenju koje daje postupak najmanjih kvadrata!
Zanima nas poopćenje na $n>1$ koje obuhvaća sve multivarijatne linearne modele regresije: univarijatna regresija, linearna regresija, polinomijalna regresija, ...
Uvodimo fiksan skup baznih funkcija (nelinearne funkcije ulaznih varijabli):
gdje $\phi_j:\mathbb{R}^n\to\mathbb{R}$
Dogovorno: $\phi_0(\mathbf{x}) = 1$
Svaki vektor primjera u $n$-dimenzijskom originalnom ulaznom prostoru (engl. input space) $\mathcal{X}$:
preslikavamo u nov, $m$-dimenzijski prostor, tzv. prostor značajki (engl. feature space): $$ \boldsymbol{\phi}(\mathbf{x}) = \big(\phi_0(\mathbf{x}), \phi_1(\mathbf{x}), \dots, \phi_m(\mathbf{x})\big) $$
Funkcija preslikavanja značajki $\mathbf{\phi} : \mathbb{R}^n \to \mathbb{R}^m $ preslikava primjere iz $n$-dimenzijskog ulaznog prostora u $m$-dimenzijski prostor značajki
Tipično je $m>n$
Tada je funkcija koja je linearna u prostoru značajki nelinearna u ulaznom prostoru
Dakle, možemo koristiti linearan model za nelinearne probleme
Imamo unificiran postupak, neovisno koju funkciju $\boldsymbol{\phi}$ odaberemo
def f(x) : return 3*(x - 2)**2 + 1
x1 = 1
x2 = 2
x3 = 3
xs = linspace(0, 4)
y = f(xs)
plt.ylim(0,5)
plt.plot(xs, y)
plt.plot(x1, f(x1), 'ro')
plt.plot(x2, f(x2), 'go')
plt.plot(x3, f(x3), 'bo')
plt.show()
def phi(x): return sp.array([1, x, x**2])
phi(x1)
array([1, 1, 1])
phi(x2)
array([1, 2, 4])
phi(x3)
array([1, 3, 9])
xs1 = linspace(0, 5)
xs2 = linspace(0, 10)
X1, X2 = np.meshgrid(xs1, xs2)
phi_X = 3*X2 - 12*X1 + 13
plt.contour(X, Y, phi_X, levels=[1,4])
plt.scatter(phi(x1)[1], phi(x1)[2], c='r')
plt.scatter(phi(x2)[1], phi(x2)[2], c='g')
plt.scatter(phi(x3)[1], phi(x3)[2], c='b')
plt.legend()
plt.show()
Ništa se ne mijenja u odnosu na ono što smo već izveli, samo umjesto $\mathbf{X}$ imamo dizajn-matricu $\boldsymbol{\Phi}$
Dizajn-matrica:
a sada imamo: $$ \mathbf{w} = (\boldsymbol{\Phi}^\intercal\boldsymbol{\Phi})^{-1}\boldsymbol{\Phi}^\intercal\mathbf{y} = \color{red}{\boldsymbol{\Phi}^{+}}\mathbf{y} $$ gdje $$ \boldsymbol{\Phi}^{+}=(\boldsymbol{\Phi}^\intercal\boldsymbol{\Phi})^{-1}\boldsymbol{\Phi}^\intercal $$
Poopćeni linearan model regresije ima jedan hiperparametar: funkciju preslikavanje $\boldsymbol{\phi}$
Alternativno, možemo reći da se radi o dva hiperparametra:
Hiperparametre treba namjestiti tako da odgovaraju podatcima, odnosno treba
dobro odabrati model
U suprotnom model može biti podnaučen ili prenaučen
Ako model ima mnogo parametra, lako ga je prenaučiti
Sprečavanje prenaučenosti:
Opažanje: kod linearnih modela, što je model složeniji, to ima veće vrijednosti parametara $\mathbf{w}$
Prenaučeni linearni modeli imaju:
Ideja: ograničiti rast vrijednosti parametara kažnjavanjem hipoteza s visokim vrijednostima parametara
Time ostvarujemo kompromis između točnosti i jednostavnosti modela i to već pri samom učenju modela
Efektivno se graničava složenost modela i sprečava se prenaučenost
Cilj: što više parametara (težina) pritegnuti na nulu $\Rightarrow$ rijetki modeli (engl. sparse models)
Rijetki modeli su:
$\lambda$ je regularizacijski faktor
[Skica: Regularizirana regresija]
Općenit regularizacijski izraz: p-norma vektora težina
ima rješenje u zatvorenoj formi
L1-regularizacija $\Rightarrow$ LASSO regularization (engl. least absolute shrinkage and selection operator)
nema rješenje u zatvorenoj formi!
L0-regularizacija
Iznos parametra $w_j$ odgovara važnosti značajke, a predznak upućuje na njezin utjecaj (pozitivan ili negativan) na izlaznu vrijednost
Regularizacija smanjuje složenost modela na način da prigušuje vrijednosti pojedinih značajki, odnosno efektivno ih izbacuje (kada $w_j\to0$)
Težinu $w_0$ treba izuzeti iz regularizacijskog izraza (jer ona definira pomak) ili treba centrirati podatke tako da $\overline{y}=0$, jer onda $w_0\to0$
L2-regularizacija kažnjava težine proporcionalno njihovom iznosu (velike težine više, a manje težine manje) Teško će parametri biti pritegnuti baš na nulu. Zato L2-regularizacija ne rezultira rijetkim modelima
L1-regularizirana regresija rezultira rijetkim modelima, ali nema rješenja u zatvorenoj formi (međutim mogu se koristiti iterativni optimizacijski postupci
Regularizacija je korisna kod modela s puno parametara, jer je takve modele lako prenaučiti
Regularizacija smanjuje mogućnost prenaučenosti, ali ostaje problem odabira hiperparametra $\lambda$
Q: Koju optimalnu vrijednost za $\lambda$ bismo dobili kada bismo optimizaciju radili na skupu za učenje?
Linearan model regresije linearan je u parametrima
Parametri linearnog modela uz kvadratnu funkciju gubitka imaju rješenje u zatvorenoj formi u obliku pseudoinverza dizajn-matrice
Nelinearnost regresijske funkcije ostvaruje se uporabom nelinearnih baznih funkcija (preslikavanjem ulaznog prostora u prostor značajki
Uz pretpostavku normalno distribuiranog šuma, MLE je istovjetan postupku najmanjih kvadrata, što daje probabilističko opravdanje za uporabu kvadratne funkcije gubitka
Regularizacija smanjuje prenaučenost ugradnjom dodatnog izraza u funkciju pogreške kojim se kažnjava složenost modela