Hvad er Support Vector Machines?

Hvad er Support Vector Machines?

Support Vector Machines er en type maskinlæringsklassifikator, der kan siges at være en af de mest populære klassifikatorer. Support Vector Machines er særligt nyttige til numerisk prædiktions-, klassifikations- og mønstergenkendelsesopgaver.

Support Vector Machines fungerer ved at tegne beslutningsgrænser mellem datapunkter, med målet om at finde den beslutningsgrænse, der bedst adskiller datapunkterne i klasser (eller er den mest generelle). Målet ved brug af en Support Vector Machine er, at beslutningsgrænsen mellem punkterne er så stor som muligt, så afstanden mellem ethvert datapunkt og grænselinjen er maksimeret. Det er en kort forklaring af, hvordan Support Vector Machines (SVM) fungerer, men lad os tage lidt tid til at dykke dybere i, hvordan SVM fungerer, og forstå logikken bag deres funktion.

Målet for Support Vector Machines

Forestil dig et diagram med et antal datapunkter på det, baseret på funktioner specificeret af x- og y-aksen. Datapunkterne på diagrammet kan løst deles op i to forskellige klaser, og den klasse, som et datapunkt tilhører, indikerer datapunktets klasse. Antag, at vi ønsker at tegne en linje gennem diagrammet, der adskiller de to klasser fra hinanden, med alle datapunkter i en klasse på den ene side af linjen og alle datapunkter, der tilhører en anden klasse, på den anden side af linjen. Denne adskilningslinje kaldes en hyperplan.

Du kan betragte en Support Vector Machine som en, der skaber “veje” gennem en by, der adskiller byen i distrikter på hver side af vejen. Alle bygningerne (datapunkter) på den ene side af vejen tilhører en distrikt.

Målet for en Support Vector Machine er ikke kun at tegne hyperplaner og adskille datapunkter, men at tegne hyperplanen, der adskiller datapunkter med den største margin, eller med det mest rum mellem den adskilningslinje og ethvert datapunkt. Ved at vende tilbage til “vej”-metaforen, hvis en byplanlægger tegner planer for en motorvej, ønsker de ikke, at motorvejen skal være for tæt på huse eller andre bygninger. Jo større marginen mellem motorvejen og bygningerne på hver side, desto bedre. Jo større denne margin er, desto mere “sikker” kan klassifikatoren være på sine prædiktionsmuligheder. I tilfælde af binær klassifikation betyder det at tegne den korrekte hyperplan at vælge en hyperplan, der er lige midt mellem de to forskellige klasser. Hvis beslutningsgrænsen/hyperplanen er fjernere fra en klasse, vil den være tættere på en anden. Derfor skal hyperplanen balancere marginen mellem de to forskellige klasser.

Beregning af den adskilningshyperplan

Så hvordan bestemmer en Support Vector Machine den bedste adskilningshyperplan/beslutningsgrænse? Dette opnås ved at beregne mulige hyperplaner ved hjælp af en matematisk formel. Vi kommer ikke til at dække formelen for beregning af hyperplaner i ekstrem detalje, men linjen beregnes med den berømte skrånings-/linjeformel:

Y = ax + b

Imens er linjer lavet af punkter, hvilket betyder, at enhver hyperplan kan beskrives som: Mængden af punkter, der løber parallelt med den foreslåede hyperplan, som bestemmes af modellens vægte gange mængden af funktioner modificeret af en specificeret offset/bias (“d”).

SVM’er tegner mange hyperplaner. For eksempel er grænselinjen en hyperplan, men datapunkterne, som klassifikatoren betragter, er også på hyperplaner. Værdierne for x bestemmes på baggrund af funktionerne i datasset. For eksempel, hvis du havde et datasset med højder og vægte for mange mennesker, ville “højde”- og “vægt”-funktionerne være de funktioner, der bruges til at beregne “X”. Marginerne mellem den foreslåede hyperplan og de forskellige “supportvektorer” (datapunkter) på hver side af den adskilningshyperplan beregnes med følgende formel:

W * X – b

mens du kan læse mere om matematikken bag SVM’er, hvis du søger en mere intuitiv forståelse af dem, så ved blot, at målet er at maksimere afstanden mellem den foreslåede adskilningshyperplan/grænselinje og de andre hyperplaner, der løber parallelt med den (og på hvilke datapunkterne findes).

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

Flerklassifikation

Processen, der er beskrevet hidtil, gælder for binære klassifikationsopgaver. Imidlertid kan SVM-klassifikatorer også bruges til ikke-binære klassifikationsopgaver. Når SVM-klassifikation udføres på et datasset med tre eller flere klasser, bruges flere grænselinjer. For eksempel, hvis en klassifikationsopgave har tre klasser i stedet for to, bruges to grænselinjer til at adskille datapunkter i klasser, og området, der udgør en enkelt klasse, falder mellem to grænselinjer i stedet for en. I stedet for kun at beregne afstanden mellem to klasser og en beslutningsgrænse, skal klassifikatoren nu betragte marginerne mellem beslutningsgrænserne og de multiple klasser i datasset.

Ikke-lineære adskillinger

Processen, der er beskrevet ovenfor, gælder for tilfælde, hvor data er lineært adskilbart. Bemærk, at i virkeligheden er datasæt næsten aldrig fuldstændigt lineært adskilbare, hvilket betyder, at når du bruger en SVM-klassifikator, skal du ofte bruge to forskellige teknikker: soft margin og kernel-tricks. Betragt en situation, hvor datapunkter fra forskellige klasser er blandet sammen, med nogle eksempler, der tilhører en klasse i “klumpen” af en anden klasse. Hvordan kan klassifikatoren håndtere disse eksempler?

En taktik, der kan bruges til at håndtere ikke-lineært adskilbare datasæt, er anvendelsen af en “soft margin”-SVM-klassifikator. En soft margin-klassifikator fungerer ved at acceptere nogle misklassificerede datapunkter. Den vil forsøge at tegne en linje, der bedst adskiller datapunktsklumperne fra hinanden, da de indeholder de fleste eksempler, der tilhører deres respektive klasser. Soft margin-SVM-klassifikatoren forsøger at skabe en adskilningslinje, der balancerer klassifikatorens to krav: nøjagtighed og margin. Den vil forsøge at minimere misklassificering, mens den maksimerer marginen.

SVM’ens tolerance for fejl kan justeres gennem manipulation af en hyperparameter kaldet “C”. C-værdien kontrollerer, hvor mange supportvektorer klassifikatoren betragter, når den tegner beslutningsgrænser. C-værdien er en straf, der pålægges misklassificeringer, hvilket betyder, at jo større C-værdi, desto færre supportvektorer klassifikatoren tager i betragtning, og desto smallere er marginen.

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

Kernel-tricket fungerer ved at anvende ikke-lineære transformationer på funktionerne i datasset. Kernel-tricket tager de eksisterende funktioner i datasset og skaber nye funktioner gennem anvendelsen af ikke-lineære matematiske funktioner. Det, der resulterer fra anvendelsen af disse ikke-lineære transformationer, er en ikke-lineær beslutningsgrænse. Fordi SVM-klassifikatoren ikke længere er begrænset til at tegne lineære beslutningsgrænser, kan den begynde at tegne kurvede beslutningsgrænser, der bedre indkapsler den sande fordeling af supportvektorerne og bringer misklassificeringer til et minimum. To af de mest populære SVM ikke-lineære kernel er Radial Basis Function og Polynomial. Den polynomiske funktion skaber polynomiske kombinationer af alle eksisterende funktioner, mens Radial Basis Function genererer nye funktioner ved at måle afstanden mellem et centralt punkt/punkter til alle andre punkter.