# Strojové učení

## 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$
- standardní evaluační metriky
	- regrese
		- mean square error, $\mathrm{MSE}=\frac1N\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)$
			- $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
			- [![confusion matrix](https://cdn.prod.website-files.com/660ef16a9e0687d9cc27474a/662c42677529a0f4e97e4f9c_644aec2628bc14d83ca873a2_class_guide_cm10.png)](https://www.evidentlyai.com/classification-metrics/confusion-matrix#how-to-read-a-confusion-matrix)
	- 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
- 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)$
				- MLE … maximum likelihood estimation
- 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$ regularizace … $\lambda(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)
- 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$
		- 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$
		- 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$
			- $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$
- trénování pomocí stochastic gradient descent
	- gradient descent
		- snažíme se minimalizovat hodnotu chybové funkce $E(w)$ pro dané váhy $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)$
				- $\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$
				- 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$
				- 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)$
		- 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$ 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$
				- 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$
- 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 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$
		- 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$
				- 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$
		- 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_\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}$ 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
- 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$
				- 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$
- 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$
		- 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))$
		- 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$
		- 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
- 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$ (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$ (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
- 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)
- 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$ 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)$
				- kde $\Psi^{-1}_{n-1}$ je kvantilová funkce studentova t-rozdělení
			- vrátíme $[\hat\theta-\delta,\hat\theta+\delta]$
				- 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$ stupňů volnosti, když máme $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$ 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
- 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$ 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$
			- 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
- 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í
- 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$
			- $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$-té dimenze na základě datové matice $X$
		- spočteme SVD matice $(X-\bar 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$) 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
		- [![příklad](https://towardsdatascience.com/wp-content/uploads/2020/05/1ba0XpZtJrgh7UpzWcIgZ1Q-2048x1372.jpeg)](https://towardsdatascience.com/pca-clearly-explained-how-when-why-to-use-it-and-feature-importance-a-guide-in-python-7c274582c37e/)
		- PCA postupně hledá osy s největším rozptylem