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 v tem n-dimenzionalnem prostoru poiskati hiperravnino, 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 vsebovani v učni množici.

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 najbližjih vektorjev. Tem vektorjem rečemo podporni vektorji in tudi metoda ima ime od tod.

Hiperravnine ni možno »zvijati«, kar omejuje možnost čistega ločevanja, razen v primeru linearno ločljivih predmetov, ki pa so v praksi redki. V primeru, ko vektorji niso linearno ločljivi, se pogosto poslužuje po tehniki povečevanja razsežnosti vektorjev. V vektorskem prostoru s primero visoko dimenzijo (razsežnostjo) je možno linearno ločevanje vseh danih razredov. Vendar pa se ob tem pojavita 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.

Uporaba posebnih funkcij, imenovanih jedra, omogoča obvoz teh težav. 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 linearno, kot tudi nelinearno ločljive vektorje lahko nadgradimo. S tem postanejo bolj prilagodljivi. Dodatne spremenljivke zavestno omogočijo klasifikatorju napačno razvrstitev nekaj predmetov. Vsako tako napačno razvrstitev »kaznuje«. Na ta način se izognemo 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č.