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-31)
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
Bayesovska klasifikacija
Naivan Bayesov klasifikator
Primjer: 101 Questions
Polunaivan Bayesov klasifikator*
Bayesov klasifikator za kontinuirane značajke
Bayesov klasifikator: komponente algoritma
Sažetak
Apriorna vjerojatnost klase $\mathcal{C}_j$:
Izglednost klase $p(\mathbf{x}|\mathcal{C}_j)$:
Ovo je parametarski i generativni model
Pretpostavimo da primjeri u stvarnosti dolaze iz dva područja:
Vjerojatnost pogrešne klasifikacije:
[Skica]
Pogreška je minimizirana kada $\mathcal{C}_j = \mathrm{argmax}_{\mathcal{C}\in\{\mathcal{C_1},\mathcal{C_2}\}} P(\mathbf{x},\mathcal{C}_j) $
$L_{kj}$ - gubitak uslijed pogrešne klasifikacije primjera iz klase $\mathcal{C}_k$ u klasu $\mathcal{C}_j$
Očekivani gubitak (funkcija rizika):
0.15$
$$ L = {\small \begin{pmatrix} 0 & 1 & 5 \\ 1 & 0 & 5 \\ 10 & 100 & 0 \end{pmatrix}} $$$\mathcal{D}=\{(\mathbf{x}^{(i)},y^{(i)})\}_{i=1}^N$
$y^{(i)}\in\{\mathcal{C}_1,\dots,\mathcal{C}_K\}$
Model:
Procjena parametara za $P(x_1,\dots,x_n|\mathcal{C}_j)$?
Tretirati $\mathbf{x} = (x_1,\dots,x_n)$ kao kategoričku varijablu (njezine vrijednosti su sve kombinacije vrijednosti $x_i$) ?
Pravilo lanca (uz uvjetnu varijablu $\mathcal{C}_j$):
Broj parametara: $\sum_{k=1}^n(K_k-1)K$
Binarne značajke: $nK$
Vrijedi li općenito nezavisnost $x_i\bot x_k|\mathcal{C}_j\ (i\neq k)$?
Primjer: Klasifikacija teksta
q101 = pd.read_csv("http://www.fer.unizg.hr/_download/repository/questions101-2014.csv", comment='#')
q101[:20]
Q1 | Q2 | Q3 | Q4 | Q5 | Q6 | Q7 | Q8 | Q9 | Q10 | ... | Q92 | Q93 | Q94 | Q95 | Q96 | Q97 | Q98 | Q99 | Q100 | Q101 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | More | Zagreb | Sok | Psi | Europa | Televizija | Messi | Gibonni | FER | Friends | ... | Elektronska glazba | Virus | Kuba | Smartphone | Finska | Tenisice | Gospodar prstenova | Čokolada | Burek s mesom | Batman |
1 | More | Zagreb | Voda | Psi | Europa | Televizija | Messi | Gibonni | FER | Big Bang Theory | ... | Rock | Virus | USA | Smartphone | Italija | Tenisice | Gospodar prstenova | Čokolada | Burek s mesom | Batman |
2 | More | Zagreb | Voda | Psi | Europa | Televizija | Messi | Gibonni | FER | Friends | ... | Rock | Virus | USA | Smartphone | Italija | Tenisice | Gospodar prstenova | Vanilija | Burek s mesom | Batman |
3 | More | Split | Voda | Psi | Europa | Televizija | Ronaldo | Oliver | FER | Friends | ... | Elektronska glazba | Bakterija | USA | Smartphone | Finska | Tenisice | Harry Potter | Čokolada | Burek s mesom | Batman |
4 | More | Zagreb | Voda | Psi | Europa | Televizija | Ronaldo | Oliver | FER | Friends | ... | Rock | Virus | Kuba | Smartphone | Italija | Cipele | Gospodar prstenova | Čokolada | Burek s mesom | Batman |
5 | More | Zagreb | Sok | Psi | USA | Televizija | Ronaldo | Gibonni | FER | Friends | ... | Rock | Bakterija | USA | Smartphone | Italija | Tenisice | Harry Potter | Vanilija | Burek sa sirom | Superman |
6 | More | Zagreb | Voda | Psi | Europa | Televizija | Ronaldo | Gibonni | FER | Friends | ... | Rock | Virus | Kuba | Smartphone | Finska | Tenisice | Gospodar prstenova | Vanilija | Burek s mesom | Superman |
7 | More | Zagreb | Voda | Psi | Europa | Televizija | Messi | Oliver | FER | Big Bang Theory | ... | Rock | Bakterija | Kuba | Obični mobitel | Finska | Tenisice | Gospodar prstenova | Čokolada | Burek sa sirom | Superman |
8 | Planina | Zagreb | Voda | Psi | Europa | Televizija | Ronaldo | Oliver | FER | Big Bang Theory | ... | Rock | Virus | Kuba | Smartphone | Finska | Tenisice | Gospodar prstenova | Čokolada | Burek s mesom | Superman |
9 | More | Zagreb | Sok | Psi | Europa | Televizija | Ronaldo | Gibonni | FER | Friends | ... | Elektronska glazba | Virus | Kuba | Smartphone | Finska | Tenisice | Gospodar prstenova | Čokolada | Burek s mesom | Batman |
10 | More | Zagreb | Voda | Psi | Europa | Televizija | Messi | Gibonni | FER | Big Bang Theory | ... | Rock | Virus | USA | Smartphone | Finska | Tenisice | Harry Potter | Čokolada | Burek s mesom | Superman |
11 | More | Zagreb | Voda | Psi | Europa | Televizija | Ronaldo | Gibonni | FER | Friends | ... | Rock | Bakterija | USA | Obični mobitel | Finska | Tenisice | Harry Potter | Čokolada | Burek s mesom | Batman |
12 | More | Zagreb | Voda | Mačke | USA | Televizija | Ronaldo | Gibonni | FER | Big Bang Theory | ... | Rock | Virus | USA | Smartphone | Finska | Tenisice | Gospodar prstenova | Čokolada | Burek sa sirom | Batman |
13 | More | Zagreb | Voda | Psi | Europa | Radio | Ronaldo | Oliver | FER | Friends | ... | Elektronska glazba | Virus | USA | Smartphone | Italija | Tenisice | Gospodar prstenova | Vanilija | Burek sa sirom | Batman |
14 | More | Zagreb | Voda | Psi | USA | Televizija | Messi | Gibonni | FER | Big Bang Theory | ... | Rock | Virus | Kuba | Smartphone | Finska | Tenisice | Harry Potter | Čokolada | Burek s mesom | Batman |
15 | More | Zagreb | Voda | Psi | Europa | Radio | Messi | Gibonni | FER | Friends | ... | Rock | Bakterija | USA | Smartphone | Finska | Cipele | Gospodar prstenova | Čokolada | Burek s mesom | Batman |
16 | Planina | Zagreb | Voda | Mačke | Europa | Televizija | Messi | Oliver | FER | Friends | ... | Rock | Bakterija | Kuba | Obični mobitel | Finska | Tenisice | Gospodar prstenova | Vanilija | Burek s mesom | Batman |
17 | More | Zagreb | Sok | Psi | Europa | Televizija | Messi | Oliver | FER | Friends | ... | Rock | Virus | USA | Smartphone | Finska | Tenisice | Harry Potter | Vanilija | Burek sa sirom | Batman |
18 | More | Zagreb | Voda | Psi | Europa | Radio | Messi | Gibonni | FER | Big Bang Theory | ... | Rock | Bakterija | USA | Smartphone | Finska | Tenisice | Harry Potter | Čokolada | Burek sa sirom | Batman |
19 | More | Zagreb | Sok | Psi | Europa | Televizija | Messi | Oliver | FER | Friends | ... | Elektronska glazba | Bakterija | USA | Smartphone | Finska | Tenisice | Gospodar prstenova | Čokolada | Burek s mesom | Batman |
20 rows × 101 columns
q101[['Q7','Q101','Q97','Q4']][:20]
Q7 | Q101 | Q97 | Q4 | |
---|---|---|---|---|
0 | Messi | Batman | Tenisice | Psi |
1 | Messi | Batman | Tenisice | Psi |
2 | Messi | Batman | Tenisice | Psi |
3 | Ronaldo | Batman | Tenisice | Psi |
4 | Ronaldo | Batman | Cipele | Psi |
5 | Ronaldo | Superman | Tenisice | Psi |
6 | Ronaldo | Superman | Tenisice | Psi |
7 | Messi | Superman | Tenisice | Psi |
8 | Ronaldo | Superman | Tenisice | Psi |
9 | Ronaldo | Batman | Tenisice | Psi |
10 | Messi | Superman | Tenisice | Psi |
11 | Ronaldo | Batman | Tenisice | Psi |
12 | Ronaldo | Batman | Tenisice | Mačke |
13 | Ronaldo | Batman | Tenisice | Psi |
14 | Messi | Batman | Tenisice | Psi |
15 | Messi | Batman | Cipele | Psi |
16 | Messi | Batman | Tenisice | Mačke |
17 | Messi | Batman | Tenisice | Psi |
18 | Messi | Batman | Tenisice | Psi |
19 | Messi | Batman | Tenisice | Psi |
X = q101[['Q7','Q101','Q97']][:20].as_matrix()
y = q101['Q4'][:20].as_matrix()
# Apriorna vjerojatnost klase: P(C_j)
def class_prior(y, label):
N = len(y)
return len(y[y==label]) / float(len(y))
# Izglednost klase: P(x_i|C_j)
def class_likelihood(X, y, feature_ix, value, label):
N = len(X)
y_ix = y==label
Nj = len(y[y_ix])
Nkj = len(X[sp.logical_and(y_ix, X[:,feature_ix]==value)])
return (Nkj + 1) / (float(Nj) + 2) # Laplace smoothed
p_Psi = class_prior(y, 'Psi')
p_Psi
0.9
p_Macke = class_prior(y, 'Mačke')
p_Macke
0.1
p_Messi_Psi = class_likelihood(X, y, 0, 'Messi', 'Psi')
p_Messi_Psi
0.55
p_Ronaldo_Psi = class_likelihood(X, y, 0, 'Ronaldo', 'Psi')
p_Ronaldo_Psi
0.45
class_prior(y, 'Psi') \
* class_likelihood(X, y, 0, 'Messi', 'Psi') \
* class_likelihood(X, y, 1, 'Batman', 'Psi') \
* class_likelihood(X, y, 2, 'Tenisice', 'Psi') \
0.29452500000000004
class_prior(y, 'Mačke') \
* class_likelihood(X, y, 0, 'Messi', 'Mačke') \
* class_likelihood(X, y, 1, 'Batman', 'Mačke') \
* class_likelihood(X, y, 2, 'Tenisice', 'Mačke') \
0.028125000000000004
faktorizirati kao: $$ P(\mathcal{C}_j|x_1,x_2,x_3)\ \propto\ P(x_1|\mathcal{C}_j)P(\color{red}{x_2,x_3}|\mathcal{C}_j)P(\mathcal{C}_j) $$ što je jednako: $$ P(\mathcal{C}_j|x_1,x_2,x_3)\ \propto\ P(x_1|\mathcal{C}_j)P(x_2|\mathcal{C}_j)P(\color{red}{x_3|x_2},\mathcal{C}_j)P(\mathcal{C}_j) $$
Q: Prednosti?
Q: Broj parametara?
Bellov broj: $B_3=5, B_{4} = 15, B_{5} = 52, \dots, B_{10} = 115975, \dots$
Treba nam heurističko pretraživanje koje će naći optimalno združivanje (broj stanja = broj particija)
Kriterij združivanja varijabli? Dvije mogućnosti:
Q: Veza s odabirom modela?
Mjera uzajamne informacije (uzajamnog sadržaja informacije) (engl. mutual information)
Entropija
$\Rightarrow$ Kullback-Leiblerova divergencija
from sklearn.metrics import mutual_info_score
X = stats.bernoulli.rvs(0.5, size=100)
Y = stats.bernoulli.rvs(0.2, size=100)
mutual_info_score(X, Y)
0.0015583988584468855
mutual_info_score(X, X)
0.69134609900173971
X = stats.bernoulli.rvs(0.5, size=100)
Y = [(sp.random.randint(2) if x==1 else 0) for x in X ]
mutual_info_score(X, Y)
0.23063664054386707
likelihood_c1 = stats.norm(110, 5)
likelihood_c2 = stats.norm(150, 20)
likelihood_c3 = stats.norm(180, 10)
xs = linspace(70, 200, 200)
plt.plot(xs, likelihood_c1.pdf(xs), label='p(x|C_1)')
plt.plot(xs, likelihood_c2.pdf(xs), label='p(x|C_2)')
plt.plot(xs, likelihood_c3.pdf(xs), label='p(x|C_3)')
plt.legend()
plt.show()
NB: Pretpostavljamo da je razdioba primjera unutar svake klase unimodalna (modelirana jednom Gaussovom razdiobom)
Model:
gdje je vektor parametara jednak $$ \boldsymbol{\theta}_j=(\mu_j, \sigma_j, P(\mathcal{C}_j)) $$
likelihood_c1 = stats.norm(100, 5)
likelihood_c2 = stats.norm(150, 20)
plt.plot(xs, likelihood_c1.pdf(xs), label='p(x|C_1)')
plt.plot(xs, likelihood_c2.pdf(xs), label='p(x|C_2)')
plt.legend()
plt.show()
p_c1 = 0.3
p_c2 = 0.7
def joint_x_c1(x) : return likelihood_c1.pdf(x) * p_c1
def joint_x_c2(x) : return likelihood_c2.pdf(x) * p_c2
plt.plot(xs, joint_x_c1(xs), label='p(x, C_1)')
plt.plot(xs, joint_x_c2(xs), label='p(x, C_2)')
plt.legend()
plt.show()
def p_x(x) : return joint_x_c1(x) + joint_x_c2(x)
plt.plot(xs, p_x(xs), label='p(x)')
plt.legend()
plt.show()
def posterior_c1(x) : return joint_x_c1(x) / p_x(x)
def posterior_c2(x) : return joint_x_c2(x) / p_x(x)
plt.plot(xs, posterior_c1(xs), label='p(C_1|x)')
plt.plot(xs, posterior_c2(xs), label='p(C_2|x)')
plt.legend()
plt.show()
Interpretacija za $\boldsymbol{\mu}$ i $\boldsymbol{\Sigma}$:
Q: Broj parametara?
ML-procjene parametara:
$\boldsymbol{\Sigma}$ je simetrična
$\boldsymbol{\Sigma}$ uvijek pozitivno semidefinitna
Ali, da bi PDF bila dobro definirana, $\boldsymbol{\Sigma}$ mora biti pozitivno definitna:
$\boldsymbol{\Sigma}$ je pozitivno definitna $\Rightarrow$ $\boldsymbol{\Sigma}$ je nesingularna: $|\boldsymbol{\Sigma}|>0$ i postoji $\boldsymbol{\Sigma}^{-1}$ (obrat ne vrijedi!)
Ako $\boldsymbol{\Sigma}$ nije pozitivno definitna, najčešći uzroci su
mu_1 = [-2, 1]
mu_2 = [2, 0]
covm_1 = sp.array([[1, 1], [1, 3]])
covm_2 = sp.array([[2, -0.5], [-0.5, 1]])
p_c1 = 0.4
p_c2 = 0.6
likelihood_c1 = stats.multivariate_normal(mu_1, covm_1)
likelihood_c2 = stats.multivariate_normal(mu_2, covm_2)
x = np.linspace(-5, 5)
y = np.linspace(-5, 5)
X, Y = np.meshgrid(x, y)
XY = np.dstack((X,Y))
plt.contour(X, Y, likelihood_c1.pdf(XY) * p_c1)
plt.contour(X, Y, likelihood_c2.pdf(XY) * p_c2);
tj. $$ h_1(\mathbf{x}) - h_2(\mathbf{x}) = 0 $$
plt.contour(X, Y, likelihood_c1.pdf(XY) * p_c1, cmap='gray_r')
plt.contour(X, Y, likelihood_c2.pdf(XY) * p_c2, cmap='gray_r')
plt.contour(X, Y, likelihood_c1.pdf(XY) * p_c1 - likelihood_c2.pdf(XY) * p_c2, levels=[0], colors='r', linewidths=2);
Kvadratni model ima previše parametara: $\mathcal{O}(n^2)$
Pojednostavljenja $\Rightarrow$ dodatne induktivne pretpostavke?
Član $\mathbf{x}^\mathrm{T}\boldsymbol{\Sigma}^{-1}\mathbf{x}$ isti je za svaki $h_j$, pa iščezava kada računamo granicu između klasa
Dakle, dobivamo linearan model!
Broj parametara?
mu_1 = [-2, 1]
mu_2 = [2, 0]
covm_1 = sp.array([[1, 1], [1, 3]])
covm_2 = sp.array([[2, -0.5], [-0.5, 1]])
p_c1 = 0.4
p_c2 = 0.6
covm_shared = (p_c1 * covm_1 + p_c2 * covm_2) / 2
likelihood_c1 = stats.multivariate_normal(mu_1, covm_shared)
likelihood_c2 = stats.multivariate_normal(mu_2, covm_shared)
plt.contour(X, Y, likelihood_c1.pdf(XY) * p_c1, cmap='gray_r')
plt.contour(X, Y, likelihood_c2.pdf(XY) * p_c2, cmap='gray_r')
plt.contour(X, Y, likelihood_c1.pdf(XY) * p_c1 - likelihood_c2.pdf(XY) * p_c2, levels=[0], colors='r', linewidths=2);
Dobili smo umnožak univarijatnih Gaussovih distribucija
NB: Ovo je naivan Bayesov klasifikator (za kontinuirane značajke)!
Model:
NB: Računamo normirane euklidske udaljenosti (normirane sa $\sigma_i$)
Q: Broj parametara?
mu_1 = [-2, 1]
mu_2 = [2, 0]
p_c1 = 0.4
p_c2 = 0.6
covm_shared_diagonal = [[2,0],[0,1]]
likelihood_c1 = stats.multivariate_normal(mu_1, covm_shared_diagonal)
likelihood_c2 = stats.multivariate_normal(mu_2, covm_shared_diagonal)
plt.contour(X, Y, likelihood_c1.pdf(XY) * p_c1, cmap='gray_r')
plt.contour(X, Y, likelihood_c2.pdf(XY) * p_c2, cmap='gray_r')
plt.contour(X, Y, likelihood_c1.pdf(XY) * p_c1 - likelihood_c2.pdf(XY) * p_c2, levels=[0], colors='r', linewidths=2);
mu_1 = [-2, 1]
mu_2 = [2, 0]
p_c1 = 0.4
p_c2 = 0.6
covm_shared_diagonal = [[1,0],[0,1]]
likelihood_c1 = stats.multivariate_normal(mu_1, covm_shared_diagonal)
likelihood_c2 = stats.multivariate_normal(mu_2, covm_shared_diagonal)
plt.contour(X, Y, likelihood_c1.pdf(XY) * p_c1, cmap='gray_r')
plt.contour(X, Y, likelihood_c2.pdf(XY) * p_c2, cmap='gray_r')
plt.contour(X, Y, likelihood_c1.pdf(XY) * p_c1 - likelihood_c2.pdf(XY) * p_c2, levels=[0], colors='r', linewidths=2);
Možemo staviti $\mathbf{w}_j=\boldsymbol{\mu}_j$
Broj parametara?
Q: Koji model od navedenih pet odabrati? Model s punom kovarijacijskom matricom ili jedno od četiri pojednostavljenja?
generativan - diskriminativan ?
parametarski - neparametarski ?
linearan - nelinearan ?
pristanost jezika - pristranost pretraživanja ?
(3) Optimizacijski postupak
Bayesov klasifikator je generativan parametarski model koji primjere klasificira na temelju MAP-hipoteze
Učenje Bayesovog klasifikatora za kontinuirane ulaze svodi se na procjenu parametara (MLE, MAP)
Naivan Bayesov klasifikator koristi pretpostavku o nezavisnosti značajki za zadanu klasu, koja omogućuje generalizaciju i pojednostavljuje model (broj parametara je linearan s $n$)
Kod diskretnog Bayesovog klasifikatora izglednosti klasa modeliramo Bernoullijevom/kategoričkom razdiobom, a kod kontinuiranog Gaussovom razdiobom (modelira šum)
Naivan Bayesov klasifikator (diskretan ili kontinuiran) je linearan model
Polunaivan klasifikator modelira zavisnost između odabranih varijabli, čime dobivamo složeniji model