Atraminių vektorių klasifikatorius

**Atraminių vektorių klasifikatorius** (ang. support vector machine, SVM)  - sistemos mokymosi (machine learning) algoritmas skirtas klasifikuoti duomenims. Tai prižiūrimo mokymosi (supervised learning) metodas, kuomet siekiama suklasifikuoti jau pažymėtus (t. y. skirtingų, iš anksto žinomų klasių) duomenis.

## Duomenų klasifikavimo problema

Dažnai duomenų analizėje sutinkama problema − žinant dvi skirtingas klases kurioms priklauso turimi duomenys, priskirti naują duomenų tašką kažkuriai iš klasių. Šią problemą galima nesunkiai išspręsti, jeigu duomenys yra vienmačiai arba dvimačiai. Tačiau esant daugiau matmenų bei siekiant automatizuoti procesą reikalingi sudėtingesni algoritmai. Šie algoritmai kiekvieną turimų duomenų tašką priskiria kuriai nors (prižiūrimo mokymosi atveju žinomai) klasei. Tarp skirtingų klasių atsiranda taip vadinama sprendimo riba (decision boundary), kuri visus duomenis suskaido į sritis, priklausančias skirtingoms klasėms (žr. paveikslą dešinėje). 
## Apibrėžimas
 Atraminių vektorių klasifikatorius (AVK) siekia surasti tiesę (sprendimo ribą) tokią, kad atstumas nuo jos iki dviejų taškų (tiesių einančių per juos), priklausančių skirtingoms klasėms būtų didžiausias (esant daugiau matmenų ši tiesė pavirsta hiperplokštuma). Šie ypatingi taškai nusako vektorius, vadinamus atraminiais vektoriais, nes jie vieninteliai daro įtaką sprendimo ribai. Formaliai sprendimo riba nusakoma vektoriumi \vec{\omega} ir skaliaru b taip, jog galioja nelygybė 

c_i (\vec{\omega} \cdot \vec{v_i} + b) > 1 i-ajam duomenų taškui. 

Čia c_i yra *i-*ojo taško klasė (+1 arba -1), \vec{v_i} = (x_i, y_i) yra vektorius nukreiptas į *i*-ąjį tašką. Pagal šią formuluotę, kiekvienas naujas taškas nusakomas vektoriumi \vec{v} yra klasifikuojamas surandant šio vektoriaus projekciją į \vec{w} ir pridedant skaliarą b. Jei \vec{w} \cdot \vec{c} + b > 0, taškas priskiriamas klasei +1, jei \vec{w} \cdot \vec{c} + b , taškas priskiriamas klasei -1.

Žinoma, norint taikyti AVK, reikia nustatyti vektoriaus \vec{w} ir skaliaro b reikšmes. Tam pasinaudojama jau turimais duomenimis, žinant kuriai klasei priklauso kiekvienas taškas. Atstumas tarp tiesių, einančių per atraminius vektorius (punktyrinės linijos paveiksle dešinėje) išreiškiamas dydžiu \frac{1}. Atraminių vektorių nustatymas susiveda į dydžio ||\vec{w}||^2/2 minimizavimą. Šis uždavinys sprendžiamas Lagranžo daugiklių metodu, kuomet ieškoma funkcijos \mathcal{L} ekstremumo daugiklių \alpha_i atžvilgiu. Ši funkcija lygi

\mathcal{L}(\alpha) = \frac{||\vec{w}||^2}{2} - \sum_i \alpha_i\cdot\left[c_i\left(\vec{w}\cdot\vec{v_i} + b\right) - 1\right],čia \alpha_i - Lagranžo daugikliai lygūs 0 visiems *i*, išskyrus kai \vec{v_i} yra atraminis vektorius. Šią išraišką įprasta perrašyti (remiantis Karush-Kuhn-Tucker sąlygomis) kaip 

\mathcal{L}(\alpha) = \sum_i \alpha_i \vec{v_i}\vec{v_i} - \sum_i \sum_j \alpha_i \alpha_j c_i c_j \vec{v_i} \vec{v_j}.

Apskaičiavus Lagranžo daugiklius \alpha_i, vektorius \vec{\omega} ir skaliaras b išreiškiami pagal \vec{\omega} = \sum_{i=1}^{N} \alpha_i c_i \vec{v_i} ir  b = \frac{1}{N_A}\sum_{i\in A}\left(c_i - \sum_{j\in A} \alpha_j c_j \vec{v_i} \vec{v_j}\right), kur \vec{v_i}\in A yra atraminiai vektoriai.

## Netiesinis klasifikavimas transformacijos branduolių metodu

Dažnai neįmanoma nubrėžti tiesės (hiperplokštumos) taip, kad visi taškai būtų padalinti į dvi atskiras grupes. Tokiu atveju AVK metodas modifikuojamas, įvedant transformacijos funkciją \phi(\vec{v}), kuri kiekvieną tašką (nusakomą vektoriumi) transformuoja pagal \vec{v} \rightarrow \phi({\vec{v}}). Tinkamai parinkus šią funkciją visi tiesiškai neatskiriami taškai įprastame atvaizdavime, taps tiesiškai atskiriamais funkcijos \phi(\vec{v}) atvaizdavime. Dažnai įvedama taip vadinama transformacijos branduolio funkcija \mathcal{k}(a,b) = \phi(a)\cdot\phi(b), kuria pakeičiamos visos vektorių skaliarinės sandaugos Lagranžiane \mathcal{L}(\alpha). Šis virsta \mathcal{L}(\alpha) = \sum_i \alpha_i \mathcal{k}(\vec{v_i},\vec{v_i}) - \sum_i \sum_j \alpha_i \alpha_j c_i c_j \mathcal{k}(\vec{v_i},\vec{v_j}). Transformacijos branduolio funkcijos gali būtų įvairių formų ir parenkamos pagal situaciją. Keletas pavyzdžių :

\mathcal{k}(a,b) = a^TMb, kur M yra tam tikra matrica.

\mathcal{k}(a,b) = \exp\left[d\cdot(a-b)^m\right], kur d ir m yra tam tikri skaičiai.

## Šaltiniai