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 klassifikatorer. Support Vector Machines er spesielt nyttige for numerisk prediksjon, klassifikasjon 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 kort forklaring på hvordan Support Vector Machines (SVMs) opererer, men la oss ta noen tid til å dykke dyptere inn i hvordan SVMs opererer og forstå logikken bak deres operasjon.

Mål for Support Vector Machines

Forestall en graf med en rekke datapunkter på den, basert på egenskaper spesifisert av X- og Y-aksene. Datapunktene på grafen kan løst deles inn i to ulike klaster, og klyngen datapunktet tilhører, indikerer klassen datapunktet tilhører. La oss nå anta at vi ønsker å tegne en linje ned grafen som skiller de to klassene fra hverandre, med alle datapunktene i en klasse på en side av linjen og alle datapunktene som tilhører en annen klasse på den andre siden av linjen. Denne skillelinjen kalles en hyperplan.

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å en side 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ær 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 klassifikasjon betyr å tegne riktig hyperplan å velge en hyperplan som er midt imellom de to ulike klassene. Hvis avgjørelsesgrensen/hyperplanen er lenger unna en klasse, vil den være nærmere en annen. Derfor må hyperplanen balansere marginen mellom de to ulike klassene.

Regning 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 slope/linjeformelen:

Y = ax + b

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

SVMs tegner mange hyperplaner. For eksempel er grenselinjen en hyperplan, men datapunktene 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øyder og vekter 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 ulike “støttevektorene” (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 som datapunktene finnes på).

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

Flervalgsklassifikasjon

Prosessen beskrevet så langt gjelder for binære klassifikasjonsoppgaver. Imidlertid kan SVM-klassifikatorer også brukes til ikke-binære klassifikasjonsoppgaver. Når man gjør SVM-klassifikasjon på et datasett med tre eller flere klasser, brukes flere grenselinjer. For eksempel, hvis en klassifikasjonsoppgave har tre klasser i stedet for to, vil to grenselinjer brukes til å dele datapunkter inn i klasser, og området 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 betyr at når du bruker en SVM-klassifikator, vil du ofte måtte bruke to ulike teknikker: myk margin og kernel-triks. Vurdér en situasjon der datapunkter fra ulike klasser er blandet sammen, med noen eksempler som tilhører en klasse i “klyngen” av en annen klasse. Hvordan kan 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 datapunktene fra hverandre, som inneholder de fleste 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 betyr at jo større C-verdien er, jo færre støttevektorer klassifikatoren tar hensyn til, og jo smalere marginen er.

Kernel-trikset transformerer dataene 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-trikset opererer ved å bruke ikke-lineære matematiske funksjoner til å transformere egenskapene i datasettet. Kernel-trikset 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.