Hva er Support Vector Machines?

Hva er Support Vector Machines?

Support vector machines er en type maskinlæringsklassifikator, kanskje en av de mest populære typene klassifikatorer. Support vector machines er spesielt nyttige for numerisk prediksjon, klassifisering og mønstergjenkjenning.

Support vector machines opererer ved å tegne avgjørelsesgrenser mellom datapunkter, med mål om å finne avgjørelsesgrensen som best skiller datapunktene inn i klasser (eller er mest generell). Målet når man bruker en support vector machine er at avgjørelsesgrensen mellom punktene er så stor som mulig, så avstanden mellom et gitt datapunkt og grenselinjen er maksimalt. Dette er en rask forklaring på hvordan support vector machines (SVMs) opererer, men la oss ta noen tid til å grave dyptere inn i hvordan SVMs opererer og forstå logikken bak deres operasjon.

Mål for Support Vector Machines

Forestall en graf med et antall datapunkter på den, basert på egenskaper spesifisert av X- og Y-aksene. Datapunktene på grafen kan løst deles inn i to forskjellige klaster, og klyngen som et datapunkt tilhører, indikerer klassen til datapunktet. Nå anta at vi ønsker å tegne en linje ned grafen som skiller de to klassene fra hverandre, med alle datapunktene i en klasse på den ene siden av linjen og alle datapunktene som tilhører en annen klasse på den andre siden av linjen. Denne skillelinjen er kjent som en hyperplane.

Du kan tenke på en support vector machine som å lage “veier” gjennom en by, som skiller byen inn i distrikter på hver side av veien. Alle bygningene (datapunkter) som er på den ene siden av veien, tilhører en distrikt.

Målet for en support vector machine er ikke bare å tegne hyperplaner og dele datapunkter, men å tegne hyperplanen som skiller datapunkter med den største marginen, eller med mest plass mellom skillelinjen og et gitt datapunkt. Ved å returnere til “vei”-metaforen, hvis en byplanlegger tegner planer for en motorvei, ønsker de ikke at motorveien skal være for nærme hus eller andre bygninger. Jo større marginen mellom motorveien og bygningene på hver side, jo bedre. Jo større denne marginen er, jo mer “sikker” kan klassifikatoren være på sine prediksjoner. I tilfelle binær klassifisering, å tegne den riktige hyperplanen, betyr å velge en hyperplane som er rett i midten av de to forskjellige klassene. Hvis avgjørelsesgrensen/hyperplanen er lengre fra en klasse, vil den være nærmere en annen. Derfor må hyperplanen balansere marginen mellom de to forskjellige klassene.

Beregning av skillehyperplanen

Hvordan bestemmer en support vector machine den beste skillehyperplanen/avgjørelsesgrensen? Dette oppnås ved å beregne mulige hyperplaner ved hjelp av en matematisk formel. Vi kommer ikke til å dekke formelen for å beregne hyperplaner i ekstrem detalj, men linjen beregnes med den berømte skråning/linjeformelen:

Y = ax + b

I mellomtiden består linjer av punkter, noe som betyr at enhver hyperplane kan beskrives som: mengden av punkter som løper parallelt med den foreslåtte hyperplanen, bestemt av vekter fra modellen ganger mengden av egenskaper modifisert av en spesifisert offset/bias (“d”).

SVMs tegner mange hyperplaner. For eksempel er grenselinjen en hyperplane, men datapunktene som klassifikatoren tar hensyn til, er også på hyperplaner. Verdier for x bestemmes basert på egenskapene i datasettet. For eksempel, hvis du hadde et datasett med høyde og vekt for mange mennesker, ville “høyde” og “vekt” egenskapene være egenskapene som brukes til å beregne “X”. Marginene mellom den foreslåtte hyperplanen og de forskjellige “støttevektor” (datapunkter) som finnes på hver side av skillehyperplanen, beregnes med følgende formel:

W * X – b

Mens du kan lese mer om matematikken bak SVMs, hvis du søker en mer intuitiv forståelse av dem, bare vite at målet er å maksimere avstanden mellom den foreslåtte skillehyperplanen/grenselinjen og de andre hyperplanene som løper parallelt med den (og på hvilke datapunkter finnes).

Foto: ZackWeinberg via Wikimedia Commons, CC BY SA 3.0 (https://commons.wikimedia.org/wiki/File:Svm_separating_hyperplanes_(SVG).svg)

Flervalgsklassifisering

Prosessen beskrevet hittil gjelder for binære klassifiseringsoppgaver. Imidlertid kan SVM-klassifikatorer også brukes for ikke-binære klassifiseringsoppgaver. Når man gjør SVM-klassifisering på et datasett med tre eller flere klasser, brukes flere grenselinjer. For eksempel, hvis en klassifiseringsoppgave har tre klasser i stedet for to, vil to grenselinjer brukes til å dele datapunkter inn i klasser, og regionen som utgjør en enkelt klasse, vil falle mellom to grenselinjer i stedet for en. I stedet for å bare beregne avstanden mellom to klasser og en avgjørelsesgrense, må klassifikatoren nå vurdere marginene mellom avgjørelsesgrensene og de multiple klassene i datasettet.

Ikke-lineære skille

Prosessen beskrevet ovenfor gjelder for tilfeller der data er lineært skillebart. Merk at, i virkeligheten, er datasett nesten aldri fullstendig lineært skillebare, noe som betyr at når man bruker en SVM-klassifikator, vil man ofte måtte bruke to forskjellige teknikker: myk margin og kernel-tricks. Overvei en situasjon der datapunkter fra forskjellige klasser er blandet sammen, med noen eksempler som tilhører en klasse i “klyngen” til en annen klasse. Hvordan kunne klassifikatoren håndtere disse eksemplene?

En taktikk som kan brukes til å håndtere ikke-lineært skillebare datasett, er å bruke en “myk margin” SVM-klassifikator. En myk margin-klassifikator opererer ved å akseptere noen feil klassifiserte datapunkter. Den vil prøve å tegne en linje som best skiller klyngene av datapunkter fra hverandre, da de inneholder majoriteten av eksemplene som tilhører deres respektive klasser. Myk margin SVM-klassifikatoren prøver å lage en skillelinje som balanserer de to kravene til klassifikatoren: nøyaktighet og margin. Den vil prøve å minimere feilklassifiseringer samtidig som den maksimerer marginen.

SVMs toleranse for feil kan justeres gjennom manipulering av en hyperparameter kalt “C”. C-verdien kontrollerer hvor mange støttevektorer klassifikatoren tar hensyn til når den tegner avgjørelsesgrenser. C-verdien er en straff som pålegges feilklassifiseringer, noe som betyr at jo større C-verdi, jo færre støttevektorer klassifikatoren tar hensyn til, og jo smalere marginen.

Kernel-tricks transformerer dataene og transformerer dem på en ikke-lineær måte. Foto: Shiyu Ju via Wikmedia Commons, CC BY SA 4.0 (https://commons.wikimedia.org/wiki/File:Kernel_trick_idea.svg)

Kernel-tricks opererer ved å anvende ikke-lineære transformasjoner på egenskapene i datasettet. Kernel-tricks tar de eksisterende egenskapene i datasettet og lager nye egenskaper gjennom anvendelse av ikke-lineære matematiske funksjoner. Det som resulterer fra anvendelsen av disse ikke-lineære transformasjonene, er en ikke-lineær avgjørelsesgrense. Fordi SVM-klassifikatoren ikke lenger er begrenset til å tegne lineære avgjørelsesgrenser, kan den begynne å tegne kurvede avgjørelsesgrenser som bedre omfatter den sanne distribusjonen av støttevektorene og bringer feilklassifiseringer til et minimum. To av de mest populære SVM ikke-lineære kjerner er Radial Basis Function og Polynomial. Den polynomiske funksjonen lager polynomiske kombinasjoner av alle eksisterende egenskaper, mens Radial Basis Function genererer nye egenskaper ved å måle avstanden mellom et sentralt punkt/punkter til alle andre punkter.