## Kernelové metody

- chtěli bychom mít model s polynomiálními features 0. až 3. řádu → měl by $O(D^3)$ vah
	- pro jednoduchost uvažujeme situaci, kdy $x_1x_2$ a $x_2x_1$ jsou dvě různé features
- váhy jsou ale lineárními kombinacemi trénovacích dat
	- nebudeme si pamatovat váhy, nýbrž koeficienty lineární kombinace
	- pro každý řádek dat $x_i$ vytrénujeme koeficient $\beta_i$
	- těch je $O(N)$, což může být méně než $O(D^3)$
	- tomu se říká duální formulace (místo vah máme koeficienty)
	- v duální formulaci se s biasem obvykle zachází samostatně
- při trénování spolu musíme často násobit $\varphi(x_i)^T\varphi(x_j)$ pro dvojice řádků trénovacích dat, takže si tyto hodnoty předpočítáme do matice $K$
	- $\varphi$ je zobrazení, které řádku dat přiřazuje polynomiální features
- v rámci trénování se těchto výpočtů provede $O(N^2)$ – každý s každým, ukládáme do $K$
- při predikci musíme predikovaný řádek $z$ pronásobit s $N$ řádky trénovacích dat (jeden z nich označíme jako $x$)
	- kdybychom vektory $\varphi(x)^T\varphi(z)$ násobili po složkách, tak to trvá dlouho – těch složek je $O(D^3)$
	- ale lze si všimnout toho, že $\varphi(x)^T\varphi(z)=1+x^Tz+(x^Tz)^2+(x^Tz)^3$
	- takže ten skalární součin spočítáme v $O(D)$
	- ani nemusíme vyrobit ty polynomiální features
- součinu těch features se říká kernel – je to funkce, které dám dva vektory a ona mi vyrobí součin features těch vektorů: $K(x,z)=\varphi(x)^T\varphi(z)$
	- už jsme si ukázali kernel pro kubické features
- kernely
	- 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“

## SVM

- jdeme dělat binární klasifikaci
- nelíbilo se nám, když perceptron našel špatnou nadrovinu (blízko k bodům)
- jdeme hledat takovou nadrovinu, aby trénovací data byla co nejdál (maximum margin)
- targety nechť jsou $\in\set{-1,1}$ jako u perceptronu
- chceme maximalizovat šířku marginu (= minimalizovat velikost vah) za podmínky, že každý prvek je na správné straně
	- abychom mohli jednoduše minimalizovat velikost vah, použili jsme trik, že pro body nejbližší k decision boundary bude platit $t_iy(x_i)=1$ (škálování je totiž na nás)
- použijeme lagrangián
- 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)
- hard-margin SVMs se používá pro lineárně separabilní data
- pro lineárně neseparabilní data potřebujeme soft-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$
	- do lagrangiánu musíme přidat další multiplikátory, které zajistí nezápornost $\xi_i$
	- lagrangián bude stejný jako minule, akorát $a_i$ budou 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
- klasifikace do více tříd
	- kombinujeme několik binárních klasifikátorů
	- 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 v SVM nedělá
	- 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