Metoda podpornih vektorjev

Metoda podpornih vektorjev (angleško support vector machine s kratico SVM, nemško Stützvektormaschine) je metoda razvrščanja. SVM razdeli množico predmetov v razrede tako, da je prostor brez predmetov med razredi oz. ločitvena meja čim širša. SVM ni običajni stroj, kot bi lahko sklepali iz angleškega imena vendar gre za matematični postopek na področju strojnega učenja za prepoznavanje vzorcev.

Temelji delovanja

Izhodišče za nastanek SVM je množica učnih predmetov, za katere je znano kateremu razredu pripadajo. Vsak predmet predstavimo z vektorjem v vektorskem prostoru. Naloga SVM je poiskati v tem n dimenzionalnem prostoru hiperravnino (hiperploskev), ki ločuje predmete iz različnih razredov. Razdaljo vektorjev, ki ležijo najbližje hiperravnini, pri tem maksimiramo. To široko prazno območje med razredi nam kasneje omogoča, da lahko čim bolj zanesljivo razvrščamo tudi predmete, ki niso čisto enaki učnim predmetom.

Pri postavljanju hiperravnine ni nujno upoštevati vseh učnih vektorjev. Vektorji, ki so daleč od hiperravnine oz. so skriti za fronto ostalih ne vplivajo na lego hiperravnine. Torej je lega hiperravnine odvisna le od njej najbljižnjih vektorjev. Tem vektorjem rečemo podporni vektorji in tudi metoda ima ime od tod.

Hiperravnine ni možno »zviti«, zato je možno izvesti čisto ločitev le takrat, ko so predmeti linearno ločljivi. To pa v resnični uporabi običajno ni slučaj. Ko vektorji niso linearno ločljivi uporabimo zvijačo. Vektorje transformiramo tako, da jim povečamo dimenzijo. Če dimenzijo dovolj povečamo postanejo vsi razredi vektorjev linearno ločljivi. Pri tem nastaneta dve težavi:

1. Transformiranje vektorjev v prostor z višjo dimenzijo je računsko zahtevna operacija.
2. Inverzna transformacija hiperravnino v prostoru z višjo dimenzijo spremeni v zelo zapleteno hiperploskev v prostoru z nižjo dimenzijo.

Če za transformacijo uporabiš posebne funkcije, ki se jim reče jedro, se tem težavam izogneš. Transformacijo in inverzno transformacijo lahko opravimo ne da bi jo dejansko računsko izvedli. Tudi tukaj zadošča uporaba le enega dela učnih vektorjev (podporni vektorji) za popolni opis meje med razredi.

Tako linerno, kot tudi nelinearno ločljive vektorje lahko nadgradimo. S tem postanejo bolj prilagodljivi. Dodatne spremenjlivke zavestno omogočijo klasifikatorju napačno razvrstitev nekaj predmetov. Vsako tako napačno razvrstitev »kaznuje«. Na ta način se izognemu prekomernemu učenju in zmanjšamo število potrebnih podpornih vektorjev.

Matematični opis

SVM je opisan z množico učnih primerov:

$\{(\mathbf {x} _{1},y_{1}),...,(\mathbf {x} _{m},y_{m})\},\mathbf {x} _{i}\in {\mathcal {X}},y_{i}\in \{-1,1\}$

Hiperravnina, ki ločuje razreda med sabo tako da je najmanjša razdalja do hiperravnine, tako imenovani rob, za primerke obeh razredov maksimirana, da bi dosegli čimboljšo generalizacijo razvrščanja.

Pri tem je $y_{i}$ pripadnost razredu za učni primerek $\mathbf {x} _{i}$. Tako imenovano učenje izračuna hiperravnino, ki učne primerke obeh razredov čim bolje loči. Ta ravnina se kasneje uporablja kot odločitvena funkcija. Podana je z normalnim vektorjem $\mathbf {w}$ in tako imenovanim pragom (angleško Bias) $\mathbf {b}$.

Učnemu vzorcu $\mathbf {x} _{i}$ se pri tem priredi predznak odločitvene funkcije kot razred:

$y_{i}=sgn(\langle \mathbf {w} ,\mathbf {x} _{i}\rangle +\mathbf {b} )$.

Od tega, kje se primerek nahaja glede na hiperravnino (nad ali pod njo), je odvisen rezultat (pozitiven ali negativen). Mejni primerek ima rezultat nič.