Strojové učení: kartičky

Učení s učitelem

klasifikace, regrese (základní typy úloh)

úloha klasifikace spočívá v přiřazení vhodné třídy (nebo sady tříd) konkrétní položce
- typická je binární klasifikace
při regresi přiřazujeme položce $x$ vhodnou funkční hodnotu $y$

Učení s učitelem

standardní evaluační metriky

regrese
- mean square error, $\mathrm{MSE}=\frac1N\sum_{i=1}^N (y_i-t_i)^2$ $MSE = \frac{1}{N} \sum_{i = 1}^{N} (y_{i} - t_{i})^{2}$
  - $y_i$ … predikce funkční hodnoty pro $x_i$
  - $t_i$ … reálná funkční hodnota pro $x_i$ (v trénovacích/testovacích datech)
klasifikace
- negative log likelihood, $\mathrm{NLL}=-\sum_{i=1}^N p_i(t_i)$ $NLL = - \sum_{i = 1}^{N} p_{i} (t_{i})$
  - $t_i$ … reálná třída $x_i$
  - $p_i$ … pravděpodobnostní rozdělení, které model vrací pro $x_i$ (pravděpodobnosti, že $x_i$ náleží jednotlivým třídám)
  - místo $p_i(t_i)$ lze také zapsat $p(t_i\mid x_i)$
- accuracy (přesnost)
  - počet správně klasifikovaných ÷ celkový počet
  - $\frac{tp+tn}{tp+tn+fp+fn}$ (u binární klasifikace)
  - nevhodná metrika, pokud jsou třídy nevyvážené (např. testujeme vzácné onemocnění)
- confusion matrix
  - řádky jsou označeny pravdivými hodnotami, sloupce predikovanými hodnotami (nebo naopak – je to potřeba uvést)
  - v každé buňce je počet testovacích dat s konkrétní kombinací targetu a predikce
  - na diagonále jsou tedy počty správně klasifikovaných testovacích dat
  - při binární klasifikaci buňky vlastně obsahují počty TP, FN, FP, TN
binární klasifikace (navíc)
- základní dělení výsledků klasifikace
  - predikce je pozitivní, realita (target) rovněž → true positive (TP)
  - predikce je pozitivní, realita je negativní → false positive (FP)
  - predikce je negativní, realita je pozitivní → false negative (FN)
  - predikce je negativní, realita také → true negative (TN)
- precision, $P=\frac{tp}{tp+fp}$
- recall, $R=\frac{tp}{tp+fn}$
- F-measure
  - vážený harmonický průměr precision a recallu
  - $F_\beta=\frac{(\beta^2+1)PR}{\beta^2P+R}=\frac{tp+\beta^2\cdot tp}{tp+fp+\beta^2(tp+fn)}$
  - $F_1=\frac{2PR}{P+R}=\frac{tp+tp}{tp+fp+tp+fn}$
  - je užitečné mít jednu hodnotu místo dvou ( $P,R$ )
- ROC (receiver operating characteristic) křivka
  - zachycuje, jak se mění vlastnosti binárního klasifikátoru, když posouváme práh (threshold, tzn. hodnotu, od níž výsledek prohlásíme za pozitivní – typicky uvažujeme 0.5)
  - na ose $x$ je false positive rate, $\mathrm{FPR}=\frac{fp}{fp+tn}$ (v čitateli jsou všechny negativní instance)
  - na ose $y$ je true positive rate (recall), $\mathrm{TPR}=\frac{tp}{tp+fn}$
  - každý bod na křivce odpovídá jinému thresholdu
  - pro náhodný „klasifikátor“ bude ROC křivka diagonála
  - pro dokonalý klasifikátor bude ROC křivka jeden bod vlevo nahoře
    - FPR = 0, TPR = 1
- AUC (area under curve)
  - plocha pod ROC křivkou
  - pro náhodný „klasifikátor“ je AUC = 0.5, pro dokonalý klasifikátor to bude AUC = 1

Učení s učitelem

ohodnocení modelu (testovací data, křížová validace, maximální věrohodnost)

testovací data slouží k ověření toho, jak dobře náš model generalizuje
- snažíme se zjistit, jak dobré výsledky model vrací pro data, která dosud neviděl
- testovací data nesmím použít v procesu trénování modelu a ladění hyperparametrů
pokud je potřeba ladit hyperparametry, používá se train-dev-test split
- parametry modelu trénujeme na trénovacích datech
- hyperparametry určujeme pomocí vývojových dat (zjistíme, pro které hodnoty hyperparametrů má model nejlepší výkon)
  - vývojová data se někdy označují jako validační (validation set)
- k finálnímu vyhodnocení modelu slouží testovací data
pokud mám dat málo a nelze z nich jednoduše vyčlenit testovací (nebo vývojová) data, používá se křížová validce (cross-validation)
- trénovací data rozdělím na $n$ dílů
- model natrénuju na datech z $n-1$ dílů
- na zbylých datech model vyhodnotím
- proces opakuju pro $n$ možných voleb
- jako výsledné skóre modelu použiju průměr průběžných hodnocení
maximální věrohodnost (maximum likelihood)
- máme-li fixní trénovací data, pak likelihood $L(w)$ (kde $w$ jsou váhy modelu) se rovná součinu pravděpodobností targetů trénovacích dat
- odhadujeme váhy modelu tak, aby byl likelihood (věrohodnost) trénovacích dat co největší
- přesněji
  - pro model s fixními vahami $w$ máme pravděpodobnostní distribuci $p_\text{model}(x;w)$ , že model vygeneruje $x$
  - pro model s fixními vahami $w$ a konkrétní řádek $x$ máme pravděpodobnostní distribuci $p_\text{model}(t\mid x;w)$ , jak model klasifikuje $x$
  - místo toho zafixujeme trénovací data a budeme měnit váhy → dostaneme $L(w)=p_\text{model}(X;w)=\prod_i p_\text{model}(x_i;w)$
  - $w_\text{MLE}=\text{arg max}_w\,p_\text{model}(X;w)$ $w_{MLE} = arg max_{w} p_{model} (X; w)$
    - MLE … maximum likelihood estimation

Učení s učitelem

přeučení a regularizace (generalizační chyba, včasné zastavení trénování, L2 a L1 regularizace)

underfitting – model je příliš slabý (příliš jednoduchý), plně jsme nevyužili jeho potenciál
overfitting (přeučení) – model špatně generalizuje, příliš se přizpůsobil trénovacím datům
generalizační chyba
- zachycuje, jak dobře model generalizuje
- typicky odpovídá výkonu modelu na testovacích datech (případně lze k jejímu určení použít křížovou validaci)
  - výkon = vhodná metrika (F-measure, accuracy, …)
generalizační chybu lze zachytit v grafu vedle trénovací chyby (výkonu modelu na trénovacích datech)
- pokud se testovací (generalizační) křivka přibližovala k trénovací a v určitý moment se začala vzdalovat, došlo k přetrénování (overfitting) modelu
  - je potřeba zesílit regularizaci nebo včas zastavit trénování
- pokud se testovací křivka ani nezačala přibližovat, je potřeba trénovat déle
regularizace
- intuice
  - penalizujeme modely s většími váhami
  - preferujeme menší změny modelu
  - omezujeme efektivní kapacitu modelu
  - čím je model složitější, tím větší má váhy
- ke ztrátové funkci (loss ~~:.|:;~~) přičteme normu vah vynásobenou parametrem $\lambda$ $λ$
  - $L^1$ regularizace … $\lambda(|w_1|+|w_2|+\dots+|w_n|)$
  - $L^2$ $L^{2}$ regularizace … $\lambda(w_1^2+w_2^2+\dots+w_n^2)$ $λ (w_{1}^{2} + w_{2}^{2} + \dots + w_{n}^{2})$
    - nebo také $\lambda\lVert w\rVert^2$ , případně $\frac\lambda2\lVert w\rVert^2$ , aby nám vyšla hezká derivace
jak bojovat s overfittingem
- $L^2$ regularizací
- early stoppingem (s trénováním přestaneme, když začne validační chyba růst)
- vhodným nastavením learning ratu $\alpha$ (případně volbou rozumného learning rate schedule)

Učení s učitelem

prokletí dimenzionality

s rostoucím počtem dimenzí (features) potřebujeme čím dál víc (exponenciálně) trénovacích dat, aby model rozumně generalizoval
chceme mít v trénovacích datech několik vzorků pro každou kombinaci features → s každou další dimenzí potřebujeme násobně víc vzorků
k redukci počtu dimenzí se obvykle používají následující přístupy
- filter
  - nezávislý na modelu, features vybírá na základě jejich vlastností
  - k hodnocení relevance features se používají statistické metody
    - konzistence – nemůžeme odstranit features, pokud bychom tak ztratili možnost odlišit prvky s různými targety (třídami)
    - korelace – dobré features korelují s třídami a nekorelují s jinými features
    - vzdálenost mezi třídami
    - metriky z teorie informace – např. vzájemná informace
- wrapper
  - závislý na modelu, features vybírá tak, aby optimalizoval jeho výsledky
  - model se natrénuje, pak se vyhodnotí pomocí standardních technik (accuracy, F-measure apod.)

Učení založené na příkladech

algoritmus k-nejbližších sousedů

regrese: $t=\sum_i\frac{w_i}{\sum_j w_j}\cdot t_i$ $t = \sum_{i} \frac{w _{i}}{\sum _{j} w _{j}} \cdot t_{i}$
- vážený průměr
klasifikace
- pro uniformní váhy můžeme hlasovat (nejčastější třída vyhrává, remízy rozhodujeme náhodně)
- jinak uvažujeme one-hot kódování $t_i$ opět můžeme použít predikci $t=\sum_i\frac{w_i}{\sum_j w_j}\cdot t_i$ (zvolíme třídu s největší predikovanou pravděpodobností)
volba vah (weighting)
- uniform: všech $k$ nejbližších sousedů má stejné váhy
- inverse: váhy jsou nepřímo úměrné vzdálenosti
- softmax: váhy jsou přímo úměrné softmaxu záporných vzdáleností
jak určit nejbližší sousedy / vzdálenosti?
- $p$ -norma: $\|x\|_p=\sqrt[p]{\sum_i|x_i|^p}$
- obvykle se používá $p\in\set{1,2,3,\infty}$
- vzdálenost $x$ a $y$ pak lze určit jako $\|x-y\|_p$

Lineární regrese

analytické řešení metodou nejmenších čtverců

sum of squares error: $\frac12\sum_{i}(x_i^Tw-t_i)^2$ $\frac{1}{2} \sum_{i} (x_{i}^{T} w - t_{i})^{2}$
- lze ho zapsat jako $\frac12\lVert Xw-t\rVert^2$
snažíme se ho minimalizovat → hledáme hodnoty, kde je derivace chybové funkce podle každé z vah nulová
- $\frac{\partial}{\partial w_j}\frac12\sum_{i}(x_i^Tw-t_i)^2=\sum_i x_{ij}(x_i^Tw-t_i)$
- chceme, aby $\forall j:\sum_i x_{ij}(x_i^Tw-t_i)=0$ $\forall j : \sum_{i} x_{ij} (x_{i}^{T} w - t_{i}) = 0$
  - $X^T(Xw-t)=0$
  - $X^TXw=X^Tt$
je-li $X^TX$ invertibilní, pak lze určit explicitní řešení jako $w=(X^TX)^{-1}X^Tt$

Lineární regrese

trénování pomocí stochastic gradient descent

gradient descent
- snažíme se minimalizovat hodnotu chybové funkce $E(w)$ $E (w)$ pro dané váhy $w$ $w$ volbou lepších vah
  - spočítáme $\nabla_wE(w)$ → tak zjistíme, jak váhy upravit
  - nastavíme $w\leftarrow w-\alpha\nabla_wE(w)$ $w \leftarrow w - α \nabla_{w} E (w)$
    - $\alpha$ … learning rate (hyperparametr), „délka kroku“
  - tomu se říká gradient descent
- standard gradient descent – používáme všechna trénovací data k výpočtu $\nabla_wE(w)$
- stochastic (online) gradient descent – používáme jeden náhodný řádek
- minibatch stochastic gradient descent – používáme $B$ náhodných nezávislých řádků
algoritmus pro trénink modelu lineární regrese (minibatch SGD)
- náhodně inicializujeme $w$ (nebo nastavíme na nulu)
- opakujeme, dokud to nezkonverguje nebo nám nedojde trpělivost
  - samplujeme minibatch řádků s indexy $\mathbb B$ $B$
    - buď uniformně náhodně, nebo budeme chtít postupně zpracovat všechna trénovací data (to se obvykle dělá, jednomu takovému průchodu se říká epocha), tedy je nasekáme na náhodné minibatche a procházíme postupně
  - $w\leftarrow w-\alpha\frac1{|\mathbb B|}\sum_{i\in \mathbb B}((x_i^Tw-t_i)x_i)-\alpha\lambda w$ $w \leftarrow w - α \frac{1}{∣ B ∣} \sum_{i \in B} ((x_{i}^{T} w - t_{i}) x_{i}) - α λ w$
    - jako $E$ se používá polovina MSE (s $L^2$ regularizací): $E(w)=\frac1{|\mathbb B|}\sum_{i\in\mathbb B}\frac12 (x_i^Tw-t_i)^2+\frac{\lambda}2 \lVert w\rVert^2$ (stačí to zderivovat)

Logistická regrese

binární klasifikace (sigmoid, metody trénování)

aktivační funkce sigmoid … $\sigma(x)=\frac1{1+e^{-x}}$
predikce $y(x;w)=\sigma(\bar y(x;w))=\sigma(x^Tw)$ $y (x; w) = σ (\overset{y}{ˉ} (x; w)) = σ (x^{T} w)$
- správnou třídu získáme zaokrouhlením
- přesná hodnota se rovná pravděpodobnosti, že je $x$ klasifikováno jako 1 (uvažujeme třídy 0 a 1)
- $\bar y$ … „lineární složka“ logistické regrese
velikost vektoru vah $w$ $w$ odpovídá počtu features
- nesmíme zapomenout také na bias, ten opět může být reprezentován jako další váha
při trénování se jako ztrátová funkce používá negative log likelihood (NLL)
- pravděpodobnost targetu $t$ pro položku $x$ lze vyjádřit jako $p(t\mid x;w)=\sigma(x^Tw)^{t}(1-\sigma(x^Tw))^{1-{t}}$
algoritmus trénování pomocí minibatch SGD
- klasifikujeme do tříd $\set{0,1}$ , na vstupu máme dataset $X$ a learning rate $\alpha\in\mathbb R^+$
- náhodně inicializujeme $w$ (nebo nastavíme na nulu)
- opakujeme, dokud to nezkonverguje nebo nám nedojde trpělivost
  - samplujeme minibatch řádků s indexy $\mathbb B$
  - $w\leftarrow w-\alpha\frac1{|\mathbb B|}\sum_{i\in \mathbb B}(\sigma(x^Tw)-t)x-\alpha\lambda w$ $w \leftarrow w - α \frac{1}{∣ B ∣} \sum_{i \in B} (σ (x^{T} w) - t) x - α λ w$
    - jako $E$ se používá NLL (s $L^2$ regularizací)
    - výsledek se překvapivě podobá lineární regresi
      - gradient je také $(y(x)-t)x$

Logistická regrese

klasifikace do více tříd (softmax, metody trénování)

klasifikujeme do jedné z $K$ tříd
parametry modelu: váhová matice $W$ (sloupce odpovídají třídám, řádky featurám), vektor biasů (jeden bias za každou třídu)
aktivační funkce … $\text{softmax}(z)_i=\frac{e^{z_i}}{\sum_je^{z_j}}$ $softmax (z)_{i} = \frac{e ^{z_{i}}}{\sum _{j} e ^{z_{j}}}$
- softmax je invariantní k přičtení konstanty $\text{softmax}(z+c)_i=\text{softmax}(z)_i$
- $\sigma(x)=\text{softmax}([x,0])_0=\frac{e^x}{e^x+e^0}=\frac1{1+e^{-x}}$
klasifikace: $p(C_i\mid x;W)=y(x;W)_i=\text{softmax}(\bar y(x;W))_i=\text{softmax}(x^TW)_i$ $p (C_{i} ∣ x; W) = y (x; W)_{i} = softmax (\overset{y}{ˉ} (x; W))_{i} = softmax (x^{T} W)_{i}$
- softmax zajišťuje normalizaci (aby se pravděpodobnosti sečetly na jedničku)
z linearity $\bar y$ lze dokázat, že oblasti tříd jsou konvexní – nemůže se stát, že by na úsečce mezi dvěma body v jedné třídě byl bod v jiné třídě
algoritmus trénování pomocí minibatch SGD
- klasifikujeme do tříd $\set{0,\dots,K-1}$ , na vstupu máme dataset $X$ a learning rate $\alpha\in\mathbb R^+$
- náhodně inicializujeme $w$ (nebo nastavíme na nulu)
- opakujeme, dokud to nezkonverguje nebo nám nedojde trpělivost
  - samplujeme minibatch řádků s indexy $\mathbb B$
  - $w\leftarrow w-\alpha\frac1{|\mathbb B|}\sum_{i\in \mathbb B}\left((\text{softmax}(x^TW)-1_t)x^T\right)^T-\alpha\lambda w$ $w \leftarrow w - α \frac{1}{∣ B ∣} \sum_{i \in B} ((softmax (x^{T} W) - 1_{t}) x^{T})^{T} - α λ w$
    - jako $E$ se používá NLL (s $L^2$ regularizací)
    - srovnání gradientu logistické regrese
      - binary: $(y(x)-t)x$
      - multiclass: $((y(x)-1_t)x^T)^T$
    - přičemž $1_t$ je one-hot reprezentace targetu $t$ (tedy vektor s jedničkou na $t$ -té pozici a nulami všude jinde)

Rozhodovací stromy

algoritmus učení a kritéria větvení

v každém vnitřním vrcholu je uložena feature, podle které dělíme, a konkrétní hodnota, která určuje rozhraní
každému vrcholu náleží podmnožina trénovacích dat
- predikce listu odpovídá tomu, jaká data v něm jsou (při regresi průměrujeme, při klasifikaci volíme největší třídu = většinové hlasování / majority vote)
možná kritéria větvení ve vrcholu $\mathcal T$ $T$
- squared error criterion (používá se při regresi)
  - squared error criterion říká, jak homogenní je podmnožina trénovacích dat, která náleží vrcholu $\mathcal T$
  - $c_\text{SE}(\mathcal T)=\sum_{i\in I_\mathcal T}(t_i-\hat t_{\mathcal T})^2$
  - $I_\mathcal T$ jsou indexy řádků trénovacích dat, které náleží danému vrcholu
  - $\hat t_\mathcal T$ je průměr targetů v daném vrcholu
- Gini index / Gini impurity (používá se při klasifikaci)
  - $c_\text{Gini}(\mathcal T)=|I_\mathcal T|\sum_kp_\mathcal T(k)(1-p_\mathcal T(k))$
  - jak často by byl náhodně vybraný prvek špatně klasifikován, kdyby byl klasifikován náhodně podle rozdělení $p_\mathcal T$ $p_{T}$
    - $p_\mathcal T(k)$ … pravděpodobnost, že vybereme prvek ze třídy $k$
    - $(1-p_\mathcal T(k))$ … pravděpodobnost, že mu přiřadíme jinou třídu než $k$
  - v binární klasifikaci Gini odpovídá squared error ztrátové funkci (skoro MSE)
- entropy criterion (používá se při klasifikaci)
  - $c_\text{entropy}(\mathcal T)=|I_\mathcal T|\cdot H(p_\mathcal T)=-|I_\mathcal T|\sum_k p_\mathcal T(k)\log p_\mathcal T(k)$
  - ze součtu vynecháme třídy s nulovou pravděpodobností, aby nám nerozbily logaritmus
  - entropy criterion lze odvodit ze ztrátové funkce negative log likelihood (NLL)
algoritmus CART (Classification and Regression Trees)
- trénovací data jsou uložena v listech
- začneme s jedním listem
- list můžeme rozdělit (stane se z něj vnitřní vrchol a pod něj připojíme dva nové listy)
- list dělíme tak, aby rozdíl $c_{\mathcal T_L}+c_{\mathcal T_R}-c_{\mathcal T}$ $c_{T_{L}} + c_{T_{R}} - c_{T}$ byl co nejmenší
  - $c_\mathcal T$ … criterion současného vrcholu
  - $c_{\mathcal T_L}$ … criterion nového levého syna
  - $c_{\mathcal T_R}$ … criterion nového pravého syna
- někdy stanovujeme omezení: maximální hloubku stromu, minimální počet dat v děleném listu (abychom nedělili zbytečně listy, co mají málo dat), maximální počet listů
  - obvykle se listy dělí prohledáváním do hloubky
  - pokud je stanoven maximální počet listů, je vhodnější je dělit ty s nejmenším rozdílem $c_{\mathcal T_L}+c_{\mathcal T_R}-c_{\mathcal T}$
dosud nás vždycky zajímaly parametry, které minimalizují ztrátovou funkci
tím, že minimalizujeme dělicí kritérium, minimalizujeme minimální dosažitelnou hodnotu ztrátové funkce pro daný strom

Rozhodovací stromy

prořezávání

prořezávání (pruning) lze použít ke zjednodušení rozhodovacího stromu, tím je možné omezit overfitting
prořezávat lze shora dolů nebo zespoda nahoru (bottom-up pruning × top-down pruning)
příklad: reduced error pruning
- bottom-up přístup
- na testovacích datech ověřujeme přesnost (accuracy)
- postupně zkoušíme rušit větvení ve vnitřních vrcholech – pokud tím nedojde ke snížení přesnosti, tak změnu provedeme
  - tedy se z vnitřního vrcholu stane list, který predikuje třídu s největším počtem položek

Metoda podpůrných vektorů

klasifikátor pro lineárně separabilní třídy

hard-margin SVM (support-vector machine)
je to kernelová (jádrová) metoda strojového učení
- model má k dispozici spoustu polynomiálních features, aniž bychom je museli explicitně počítat
- používáme jádrovou funkci $K$
model je neparametrický – využívá se duální formulace
- nemáme váhy, ale koeficienty u trénovacích dat
- duální formulace vychází z pozorování, že klasické váhy jsou lineárními kombinacemi trénovacích dat
princip je podobný jako u perceptronu
- jedná se o binární klasifikaci do tříd $\set{-1,1}$
- tentokrát ale chceme zajistit, aby byla dělicí nadrovina (decision boundary) co nejlepší – aby byl margin (mezera mezi nadrovinou a body) co největší
jak se odvozuje
- uvažujeme váhy $w$ a bias $b$ , dále mapování $\varphi$ do prostoru features, predikci označíme $y(x)=\varphi(x)^Tw+b$
- pro všechny body chceme maximalizovat vzdálenost od decision boundary
  - váhy i bias můžeme libovolně škálovat, proto určíme, že pro body nejbližší k decision boundary bude platit $t_iy(x_i)=1$
  - díky tomu nám stačí „minimalizovat váhy“ takto: $\mathrm{argmin}_{w,b}\,\frac12\|w\|^2$ $argmin_{w, b} \frac{1}{2} ∥ w ∥^{2}$
    - za předpokladu, že $t_iy(x_i)\geq 1$
- tuhle minimalizaci s omezující podmínkou provádíme pomocí lagrangiánu a KKT podmínek
  - místo multiplikátorů $\lambda_i$ se tradičně používají $a_i$
- díky KKT podmínkám víme, že nás při maximalizaci lagrangiánu zajímají jenom některá trénovací data – ta, která leží na okraji (support vektory)
  - je tam podmínka $a_i(t_iy(x_i)-1)=0$
  - z toho vyplývá, že pro každé $x_i$ platí $t_iy(x_i)=1$ (bod je na marginu) nebo $a_i=0$ (bod se nepoužívá k predikci)
predikce … $y(x)=\sum_i a_it_iK(x,x_i)+b$

Metoda podpůrných vektorů

klasifikátor pro lineárně neseparabilní třídy

soft-margin SVM
v mnohém se podobá hard-margin SVM
dovolíme některým bodům, aby porušily pravidlo (aby byly uvnitř marginu nebo na opačné straně decision boundary)
pořídíme si slack variables $\xi_i\geq 0$ $ξ_{i} \geq 0$
- pro body, které porušují $t_iy(x_i)\geq1$ bude platit $\xi_i=|t_i-y(x_i)|$
- jinak $\xi_i=0$
takže podmínku $t_iy(x_i)\geq1$ nahradíme $t_iy(x_i)\geq1-\xi_i$
úpravy lagrangiánu
- musíme tam přidat další multiplikátory, které zajistí nezápornost $\xi_i$
- výsledný lagrangián bude stejný jako minule, akorát $a_i$ (odpovídají lambdám) budou navíc omezeny shora nějakým $C$
support vektory teďka nebudou jenom body na okrajích marginu, ale i všechny, které mají kladné $\xi_i$ (jsou divné)
pozorování: $\xi_i=\max(0,1-t_iy(x_i))$ $ξ_{i} = max (0, 1 - t_{i} y (x_{i}))$
- téhle funkci se říká hinge loss
soft-margin SVM lze vlastně formulovat jako $\text{argmin}_{w,b}\,C\sum_i\mathcal L_\mathrm{hinge}(t_i,y(x_i))+\frac12\|w\|^2$ $argmin_{w, b} C \sum_{i} L_{hinge} (t_{i}, y (x_{i})) + \frac{1}{2} ∥ w ∥^{2}$
- to nám hodně připomíná klasický vzorec pro logistickou regresi apod.
- akorát místo regularizační konstanty $\lambda$ tady máme $C$ , které hraje opačnou roli (čím větší $C$ , tím slabší regularizace)
k trénování se používá sequential minimal optimization
- bereme řádky po jednom, k tomu $a_i$ , náhodně $a_j$ a taky bias, postupně zlepšujeme lagrangián

Metoda podpůrných vektorů

jádrové funkce

idea
- uvažujeme duální formulaci modelu (místo vah máme koeficienty, kterými přispívají řádky trénovacích dat)
- máme polynomiální features (pomocí zobrazení $\varphi$ )
- při predikci bychom museli $N$ -krát počítat $\varphi(x_i)^T\varphi(z)$
- když si ale například představíme features 0. až 3. řádu, tak si můžeme všimnout toho, že $\varphi(x)^T\varphi(z)=1+x^Tz+(x^Tz)^2+(x^Tz)^3$
zobecnění
- budeme uvažovat kernelové funkce (kernely), které mají všechny následující vzorec (pro různé $\varphi$ ): $K(x,z)=\varphi(x)^T\varphi(z)$
- kernel je tedy funkce, která dostane dva vektory a ona mi vrátí součin features těch vektorů
- výše jsme si jeden takový kernel ukázali
polynomiální kernel stupně $d$ $d$ (homogenní polynomiální kernel)
- vyrábí kombinace $d$ vstupních features
- $K(x,z)=(\gamma x^Tz)^d$
- $\gamma$ je hyperparametr, který škáluje features
polynomiální kernel stupně nejvýše $d$ $d$ (nehomogenní polynomiální kernel)
- $K(x,z)=(\gamma x^Tz+1)^d$
Gaussian Radial basis function (RBF) kernel
- obsahuje polynomiální features všech řádů
- $K(x,z)=e^{-\gamma\|x-z\|^2}$
- je to funkce vzdálenosti
  - pro stejné vektory vrací jedničku, pro hodně vzdálené vektory vrací nulu, pro ostatní něco mezi tím
  - dá se to interpretovat jako rozšířenou verzi algoritmu $k$ nejbližších sousedů ( $k$ -NN)
  - $\gamma$ ovlivňuje, co už je „moc daleko“
- polynomiální features vysokých řádů mají nízké váhy
kernely se typicky používají tam, kde potřebujeme lineárně separabilní data (například v SVM) – transformují nám původní data do více dimenzí, tam už je pak obvykle můžeme rozumně separovat

Metoda podpůrných vektorů

klasifikace do více tříd

kombinujeme několik binárních klasifikátorů
první možný (nepoužívaný!) přístup: one-versus-rest (ovr) schéma
- natrénuju $K$ nezávislých binárních klasifikátorů (patří prvek konkrétní třídě? ano/ne)
- při predikci vyberu třídu, které její klasifikátor přisuzuje největší pravděpodobnost
- je potřeba klasifikátory kalibrovat, aby se ty pravděpodobnosti daly porovnávat!
- takhle se to u SVM nedělá
alternativní přístup: one-versus-one schéma
- klasifikátor na každou dvojici tříd, které existují
- většinové hlasování (každý klasifikátor hlasuje pro jednu třídu)
- klasifikátorů je víc, ale trénujeme je na méně datech

Kombinace více modelů

bagging a boosting

jedná se o dva různé přístupy k trénování více modelů
bagging
- modely se trénují nezávisle
- pro každý model náhodně vybereme vzorek trénovacích dat, na nichž se učí (typicky samplujeme s opakováním = bootstrapping)
boosting
- modely se trénují sekvenčně
- snažíme se postupně opravovat chyby předchozích modelů
- princip algoritmu AdaBoost
  - postupně trénujeme slabé klasifikátory (např. mělké rozhodovací stromy/pařezy) na vážených trénovacích datech
  - v každé iteraci upravujeme váhy trénovacích dat, aby špatně klasifikovaná data měla větší váhy
  - rovněž přiřazujeme váhy klasifikátorům podle jejich přesnosti (accuracy)

Kombinace více modelů

metoda náhodných lesů

trénování
- pro každý strom náhodně (s opakováním) vybereme sample trénovacích dat (= bagging)
- pro každý vrchol náhodně vybereme podmnožinu features, které při dělení bereme v úvahu
predikce
- u regrese průměrujeme hodnoty jednotlivých stromů
- u klasifikace hlasujeme
les vs. strom
- strom se dá rychle natrénovat, jeho predikci lze snadno interpretovat (jako sérii rozhodnutí)
- les je obvykle přesnější a lépe generalizuje

Statistické testy

studentův t-test (jednovýběrový a dvouvýběrový)

jednovýběrový t-test
- způsob, jak získat intervalový odhad pro $\theta$ , neznáme-li rozptyl $\sigma^2$
- uvažujeme statistiku $T=\frac{\overline{X_n}-\theta_0}{\bar\sigma/\sqrt n}$ , která má t-rozdělení s $n-1$ stupni volnosti, pokud $H_0$ platí
- intervalový odhad
  - najdeme bodový odhad $\hat\theta$ $\hat{θ}$ pro $\theta$ $θ$
    - třeba pokud nás zajímá $\mu$ , tak prostě použijeme výběrový průměr
  - máme $n$ hodnot
  - $\delta=\frac{\bar\sigma}{\sqrt n}\cdot \Psi^{-1}_{n-1}(1-\alpha/2)$ $δ = \frac{σ ˉ}{n} \cdot Ψ_{n - 1}^{- 1} (1 - α /2)$
    - kde $\Psi^{-1}_{n-1}$ je kvantilová funkce studentova t-rozdělení
  - vrátíme $[\hat\theta-\delta,\hat\theta+\delta]$ $[\hat{θ} - δ, \hat{θ} + δ]$
    - v tomto intervalu bude pravděpodobně reálná hodnota $\theta$ pro populaci, z níž jsme data vybrali
- testování hypotézy
  - např. pokud ověřujeme, že se střední hodnota rovná nějaké konstantě, tak konstantu i výběrový průměr dosadíme do vzorce pro $T$
  - $H_0$ … $T$ má t-rozdělení s $n-1$ stupni volnosti
  - $H_0$ zamítáme, když je spočítaná hodnota statistiky větší než kritická hodnota
- poznámka: proč uvažujeme $n-1$ $n - 1$ stupňů volnosti, když máme $n$ $n$ hodnot?
  - z $n-1$ hodnot můžu $n$ -tou hodnotu dopočítat
dvouvýběrový t-test
- můžeme testovat třeba to, jestli se rovnají střední hodnoty parametru $\theta$ u dvou různých populací (samplujeme nezávisle, vzorků může být různý počet)
- např. $H_0$ … $\mu_X=\mu_Y$
- opět uvažujeme testovou statistiku $T$ $T$ s t-rozdělením
  - $T=\frac{\overline{X_n}-\overline{Y_m}}{\mathrm{SE}}$
  - přičemž $\mathrm{SE}$ je směrodatná chyba (vzorec je komplikovaný)
bonus: párový test
- data jsou ve dvojicích, dvojice dat spolu nějak souvisí
- např. $H_0$ … $\mu_X=\mu_Y$
- uvažuju $R_i=Y_i-X_i$ (rozdíl dvojice), použiju jednovýběrový test

Statistické testy

chí-kvadrát test (test dobré shody)

Pearsonův chí-kvadrát test dobré shody
$O_i$ … pozorovaná četnost kategorie $i$
$E_i$ … očekávaná četnost kategorie $i$
testová statistika: $\sum_i\frac{(E_i-O_i)^2}{E_i}$
typická úloha: je kostka spravedlivá?
- použijeme $\chi^2$ $χ^{2}$ distribuci pro 5 stupňů volnosti
  - pokud $\chi^2$ pro naši konkrétní kostku náleží kritickému oboru $W$ , prohlásíme, že kostka není spravedlivá
$H_0$ … pozorované četnosti jednotlivých kategorií odpovídají jejich očekávaným četnostem
pokud $H_0$ platí, má testová statistika rozdělení $\chi^2$ rozdělení s $n-1$ stupni volnosti, přičemž $n$ je počet kategorií
$H_0$ zamítáme, když je spočítaná hodnota statistiky větší než kritická hodnota

Učení bez učitele

shlukování (algoritmus k-means)

algoritmus
- na vstupu máme body $x_1,\dots,x_N$ , počet clusterů $K$
- inicializujeme středy clusterů $\mu_1,\dots,\mu_K$ $μ_{1}, \dots, μ_{K}$
  - buď náhodně (ze vstupních bodů)
  - nebo pomocí kmeans++
    - první střed se vybere náhodně (ze vstupních bodů)
    - každý další střed vybereme z nepoužitých bodů tak, že pravděpodobnost výběru každého bodu úměrně roste s druhou mocninou vzdálenosti jeho nejbližšího středu (clusteru)
- opakujeme, dokud to nezkonverguje nebo nám nedojde trpělivost
  - body přiřadíme clusterům (každý bod přiřadíme tomu clusteru, k jehož středu má nejblíž)
  - aktualizujeme středy clusterů (vždy zprůměrujeme body, které jsme danému clusteru přiřadili)
použití
- $K$ -means se používá ke clusteringu, tedy k dělení dat do skupin, clusterů
- je to technika učení bez učitele (unsupervised), neznáme targety
- konkrétní příklady: seskupení pixelů podobné barvy, určení skupin zákazníků
ztrátová funkce, kterou algoritmus optimalizuje
- $J=\sum_{i=1}^N\sum_{k=1}^Kz_{i,k}\|x_i-\mu_k\|^2$
- kde $z_{i,k}$ je indikátor přiřazení bodu $x_i$ do clusteru $k$
konvergence
- aktualizace přiřazení bodů ke clusterům nezvyšuje loss
- aktualizace středů clusterů nezvyšuje loss
- takže $K$ -means konverguje k lokálnímu optimu

Učení bez učitele

hierarchické shlukování

dva přístupy: postupné spojování menších shluků (aglomerativní shlukování) nebo naopak dělení velkých shluků na menší (divisivní shlukování) podle zadaných pravidel
algoritmus spojování menších clusterů/shluků
- na začátku je každý cluster singleton (patří tam jeden bod)
- slučujeme nejpodobnější clustery, dokud nezískáme cílový počet clusterů
dají se používat různé metriky podobnosti shluků (např. vzdálenost mezi centroidy shluků nebo přímo mezi jejich body, průměry vzdáleností, …)
příklady algoritmů divisivního shlukování
- DIANA (divisive analysis)
  - na začátku jsou všechny body v jednom clusteru
  - v něm najdeme bod, který se nejvíc liší od všech ostatních a oddělíme ho do samostatného clusteru
  - do téhož (nového) clusteru po jednom přidáváme i další body z původního clusteru, pokud se více hodí do nového clusteru (jsou mu blíže než původnímu)
- principal directions divisive partitioning (PDDP)
  - používá princip PCA – dělí clustery pomocí projekce na hlavní komponenty
většinou se jedná o hladové algoritmy → nelze zaručit, že je řešení optimální

Učení bez učitele

redukce dimenzionality (analýza hlavních komponent)

singulární rozklad (SVD, singular value decomposition)
- mějme matici $X\in\mathbb R^{m\times n}$ s hodností $r$
- $X=U\Sigma V^T$ $X = U Σ V^{T}$
  - $U\in\mathbb R^{m\times m}$ ortonormální
  - $\Sigma\in\mathbb R^{m\times n}$ diagonální matice s nezápornými hodnotami (tzv. singulárními čísly) zvolenými tak, aby byly uspořádány sestupně
  - $V\in\mathbb R^{n\times n}$ ortonormální
- možný pohled na dekompozici
  - $X=\sigma_1u_1v_1^T+\sigma_2u_2v_2^T+\dots+\sigma_ru_rv_r^T$
  - $\sigma_i$ … $i$ -té singulární číslo
  - $u_i$ … $i$ -tý sloupec matice $U$
  - $v_i^T$ … $i$ -tý řádek matice $V^T$
- redukovaná verze SVD
  - $\sigma$ označme vektor singulárních čísel
  - pro matici $X$ s hodností $r$ bude v tom vektoru nejvýše $r$ nenulových hodnot
  - tedy matici $\Sigma$ můžeme redukovat na rozměry $r\times r$ , podobně $U$ můžeme redukovat na $m\times r$ a $V^T$ na $r\times n$ , touto kompresí nepřijdeme o žádné informace
- dokonce můžeme $\Sigma$ $Σ$ zmenšit ještě víc
  - zvolíme $k\lt r$
  - necháme jenom $k$ největších singulárních čísel, všechny ostatní zahodíme
  - tím už se nějaké informace ztratí
  - budeme mít aproximaci původní matice $X$ , ta aproximace bude mít hodnost $k$
algoritmus určení PCA (principal component analysis) $M$ $M$ -té dimenze na základě datové matice $X$ $X$
- spočteme SVD matice $(X-\bar x)$ $(X - \overset{x}{ˉ})$
  - kde $\bar x$ je průměr řádků matice (vektor průměrných hodnot jednotlivých features)
  - k určení SVD (respektive nalezení $V$ $V$ ) lze použít algoritmus power iteration
    - do proměnné $S$ uložíme kovarianční matici $\text{cov}(X)=\frac 1N(X-\bar x)^T(X-\bar x)$
    - pro každou komponentu hledáme vektor $v_i$ (sloupec matice $V$ ) tak, že začneme s náhodným vektorem a poté ho zleva násobíme maticí $S$ a normalizujeme (dělíme vlastní normou), dokud to nezkonverguje
    - od matice $S$ na konci každého kroku odečteme $\lambda_iv_iv_i^T$ , kde $\lambda_i$ je norma vektoru $v_i$ před poslední normalizací
- necháme prvních $M$ řádků $V^T$ , ostatní zahodíme (takže $V$ bude mít $M$ sloupců)
- pokud chceme získat hodnoty nových $M$ komponent, tak stačí vynásobit $XV$ , tak dostaneme matici $N\times M$
- funguje to díky tomu, že pomocí SVD matice $(X-\bar x)$ získáváme vlastní vektory kovarianční matice $\text{cov}(X)=\frac 1N(X-\bar x)^T(X-\bar x)$
aplikace PCA
- aproximace matic
- snížení šumu v datech
- redukce dimenzí dat, extrakce features
- vizualizace dat
- praktické použití: doporučovací systémy
příklad použití PCA
- PCA postupně hledá osy s největším rozptylem