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

Skirtingi būdai nubrėžti sprendimo ribą tarp dviejų klasių. Intuityviai, tiesė $y_{2}$ padalija duomenis geriau, nei tiesė $y_{1}$.

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

Klasifikavimas atraminiais vektoriais. Algoritmas maksimizuoja atstumą tarp punktyrinių linijų. Taškai, per kuriuos eina šios linijos vadinami atraminiais vektoriais.

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<0$, 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}{||{\vec {w}}||}}.$ 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

Tiesiškai neatskiriami taškai paveikus juos transformacija $x\rightarrow \phi (x)$ tampa tiesiškai atskiriamais naujame atvaizdavime.

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^{T}Mb,$ 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.