Atraminių vektorių klasifikatorius

Atraminių vektorių klasifikatorius (ang. support vector machine, SVM) http://web.vu.lt/mii/j.zilinskas/DzemydaKurasovaZilinskasDDVM.pdf - 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 
miniatiūra|243px|Skirtingi būdai nubrėžti sprendimo ribą tarp dviejų klasių. Intuityviai, tiesė  padalija duomenis geriau, nei tiesė .
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 
alt=|miniatiūra|243px|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  ir skaliaru  taip, jog galioja nelygybė 

 i-ajam duomenų taškui. 

Čia  yra i-ojo taško klasė ( arba ),  yra vektorius nukreiptas į i-ąjį tašką. Pagal šią formuluotę, kiekvienas naujas taškas nusakomas vektoriumi  yra klasifikuojamas surandant šio vektoriaus projekciją į  ir pridedant skaliarą . Jei , taškas priskiriamas klasei , jei , taškas priskiriamas klasei .

Žinoma, norint taikyti AVK, reikia nustatyti vektoriaus  ir skaliaro  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  Atraminių vektorių nustatymas susiveda į dydžio  minimizavimą. Šis uždavinys sprendžiamas Lagranžo daugiklių metodu, kuomet ieškoma funkcijos  ekstremumo daugiklių  atžvilgiu. Ši funkcija lygi

čia  - Lagranžo daugikliai lygūs 0 visiems i, išskyrus kai  yra atraminis vektorius. Šią išraišką įprasta perrašyti (remiantis Karush-Kuhn-Tucker sąlygomis) kaip http://www.cogsys.wiai.uni-bamberg.de/teaching/ss06/hs_svm/slides/SVM_Seminarbericht_Hofmann.pdf 

Apskaičiavus Lagranžo daugiklius , vektorius  ir skaliaras  išreiškiami pagal  ir   kur  yra atraminiai vektoriai.

 Netiesinis klasifikavimas transformacijos branduolių metodu 

miniatiūra|243px|Tiesiškai neatskiriami taškai paveikus juos transformacija  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ą , kuri kiekvieną tašką (nusakomą vektoriumi) transformuoja pagal . Tinkamai parinkus šią funkciją visi tiesiškai neatskiriami taškai įprastame atvaizdavime, taps tiesiškai atskiriamais funkcijos  atvaizdavime. Dažnai įvedama taip vadinama transformacijos branduolio funkcija , kuria pakeičiamos visos vektorių skaliarinės sandaugos Lagranžiane . Šis virsta  Transformacijos branduolio funkcijos gali būtų įvairių formų ir parenkamos pagal situaciją. Keletas pavyzdžių Bishop, Christopher M. (2006). Pattern Recognition and Machine Learning:

 kur  yra tam tikra matrica.

 kur  ir  yra tam tikri skaičiai.

 Šaltiniai 

Kategorija:Dirbtinis intelektas