svm: kartičky | uvod-do-strojoveho-uceni

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

Kernelové metody

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ě

Kernelové metody

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

Kernelové metody

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

Kernelové metody

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

Kernelové metody

kernely

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“

SVM

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)

SVM

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)

SVM

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$ $ξ_{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))$ $ξ_{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)

SVM

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

SVM

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