Metoda podpornih vektorjev

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

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 (meja) čim širši. Support Vector Machine ni običajni stroj, kot bi lahko sklepali iz angleškega imena in ni sestavljen oprijemljivih sestavin. Gre za matematični postopek prepoznavanja vzorcev. Beseda Machine nam sporoča, da SVM sodi na podroćje strojnega učenja.

Temelji delovanja[uredi | uredi kodo]

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[uredi | uredi kodo]

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č.