# Support vector machine

Support vector machine (SVM) is een algoritme op het gebied van gecontroleerd machinaal leren. De methode is gebaseerd op de theorie van statistisch leren van de Russen Vapnik en Chervonenkis. Ze heeft vele uiteenlopende toepassingen in classificatie en regressie-analyse.

## Principe

Een SVM is een binaire classificeerder; ze wijst aan de hand van een aantal kenmerken objecten toe aan een van twee klassen. Daarvoor moet ze eerst een numeriek model van deze objecten maken als punten in een vectorruimte. In de trainingsfase brengt de SVM op basis van een verzameling van voorbeelden, waarvan is aangegeven tot welke klasse ze behoren, een lineaire scheiding aan die de twee klassen zo goed mogelijk van elkaar scheidt (die scheiding is een hypervlak; in twee dimensies is het een rechte lijn). Nadien kan de SVM dan voor een nieuw te klasseren object beslissen tot welke klasse het behoort door te kijken langs welke kant van het hypervlak het corresponderende punt in de ruimte ligt.
De "zo goed mogelijke" scheiding betekent dat de marge rond het scheidingsvlak, dit is de afstand tussen het scheidingsvlak en de dichtstbijgelegen voorbeelden van elke klasse, zo groot mogelijk is. Die dichtstbijgelegen voorbeelden noemt men de support vectors.
De methode is ook bruikbaar in gevallen waar een lineaire scheiding tussen de twee klassen niet mogelijk is (door een geschikte transformatie uit te voeren, de zogenaamde "kernel trick"), en ook in gevallen waar er ruis of fouten in de gegevens zitten waardoor sommige voorbeelden aan de verkeerde kant van het scheidingsvlak kunnen liggen. Computer-implementaties van SVM kunnen problemen met duizenden dimensies aan.

## Lineaire classificatie

De binaire lineaire classificeerder verdeelt objecten in twee klassen, een positieve en een negatieve die respectievelijk het label +1 en -1 dragen. De verzameling van trainingsgegevens ${\mathcal {D}}$ bestaat dan uit n punten en hun labels:
    ${\mathcal {D}}=\left\{(\mathbf {x} _{i},y_{i})\mid \mathbf {x} _{i}\in \mathbb {R} ^{p},\,y_{i}\in \{-1,1\},i=1,2,\dots n\right\}$
waarin y$_i$ +1 of −1 is, om aan te geven tot welke klasse het punt $\mathbf {x} _{i}$ behoort. Elke $\mathbf {x} _{i}$ is een p-dimensionale reële vector; elk van de p elementen in de vector beschrijft een kenmerk van een voorbeeldobject.
In de trainingsfase moet de SVM het scheidend hypervlak bepalen dat de punten met $y_{i}=1$ scheidt van de punten met $y_{i}=-1$. Een hypervlak wordt bepaald door een vergelijking van de vorm
    $\mathbf {w} \cdot \mathbf {x} -b=0,\,$
waarin $\cdot$ het inwendig product van twee vectoren is. ${\mathbf {w} }$ is de normaalvector die loodrecht op het hypervlak staat en ${\tfrac {b}{\|\mathbf {w} \|}}$ is de afstand van het hypervlak tot de oorsprong volgens de richting van de normaalvector ($\|\mathbf {w} \|$ is de norm van de vector ${\mathbf {w} }$).
Het scheidend hypervlak wordt bepaald zo dat de zogenaamde marge, dit is de kleinste afstand tot het hypervlak, voor beide klassen maximaal is om een zo breed mogelijke scheiding te garanderen. De meetkundige interpretatie hiervan is: het optimale hypervlak is orthogonaal ten opzichte van de kortste lijn tussen de convexe omhullingen van de twee klassen, en snijdt deze lijn precies halverwege.
| Voor een trainingset die lineair scheidbaar is zijn er oneindig veel scheidingsvlakken mogelijk. | Het beste scheidingsvlak (in rood) is dat met de grootste marge. De omcirkelde voorbeelden zijn de support vectors. |
Het optimale scheidend hypervlak voldoet aan de eis:
    $\max _{\mathbf {w} ,b}\min\{||\mathbf {x} -\mathbf {x_{i}} ||:\mathbf {w} \cdot \mathbf {x} +b=0,i=1,\dots n\}$
Om dit optimale hypervlak te construeren moet een optimaliseringsprobleem opgelost worden, dat als volgt geformuleerd kan worden:
    minimiseer met betrekking tot $\mathbf {w} ,b:{\frac {1}{2}}||\mathbf {w} ||^{2}$
    met als voorwaarden $y_{i}(\mathbf {w} \cdot \mathbf {x} _{i}+b)\geq 1,i=1,\dots n$
Dit is een convex kwadratisch (dus niet-lineair) programmeringsprobleem. Het wordt meestal opgelost via het Lagrangiaans duaal probleem, dat dezelfde oplossing heeft mits aan bepaalde voorwaarden voldaan is (de zogenaamde Kuhn-Tucker-voorwaarden). Het duale probleem is vaak eenvoudiger op te lossen dan het primale, met "off the shelf" software.
Merk op dat de ligging van het scheidend hypervlak slechts afhangt van een klein aantal voorbeelden, namelijk deze die er het dichtst bij liggen. Deze noemt men de support vectors (dit zijn de omcirkelde punten in bovenstaande figuur). Punten die verder weg liggen van het hypervlak kunnen uit de trainingset weggelaten worden zonder dat de ligging van het hypervlak verandert; als een support vector weggelaten wordt, verandert het scheidend hypervlak wel.
Eens de optimale waarden van $\mathbf {w} ,b$ berekend zijn, kan de SVM in de beslissingsfase een nieuwe vector $\mathbf {x} _{*}$ klasseren door het berekenen van de beslissingsfunctie
    $f(\mathbf {x} )=\operatorname {sgn}(\mathbf {w} \cdot \mathbf {x} _{*}+b)$
wat als resultaat +1 of -1 geeft (of 0 als de vector precies op het scheidingsvlak ligt).

## Niet-scheidbare klassen

In de meeste reële gevallen kunnen de trainingsvoorbeelden niet scherp lineair gescheiden worden in twee klassen. Dat kan bijvoorbeeld liggen aan meetfouten of ruis in de gegevens, of er is een grijze zone waarin beide klassen elkaar overlappen. Voor dit geval kan het optimaliseringsprobleem aangepast worden, door een bijkomende "strafterm" toe te voegen. Het heeft dan de volgende vorm:
    minimiseer met betrekking tot $\mathbf {w} ,b,\xi _{i},i=1,\dots n$: ${\frac {1}{2}}||\mathbf {w} ||^{2}+C\sum _{i=1}^{n}\xi _{i}$,
    met als beperkingen $y_{i}(\mathbf {w} \cdot \mathbf {x} _{i}+b)\geq 1-\xi _{i};\xi _{i}\geq 0,i=1,\dots n$
We voeren dus voor elk trainingsvoorbeeld een extra variabele $\xi _{i}$ in. Deze "restvariabele" (Engels: slack variable) is een maat voor de eventuele overschrijding van de beperkingen (de afstand aan de verkeerde kant van het scheidend hypervlak voor het i-de voorbeeld) en door deze in de doelfunctie in te voeren zorgen we dat deze overschrijdingen zo klein mogelijk gehouden worden. Er is ook een afweging te maken tussen enerzijds de wens om een zo groot mogelijke marge rond het scheidend vlak te hebben en anderzijds zo weinig mogelijk overschrijdingen. De te kiezen positieve constante $C$ geeft in dit verband aan welk belang we hechten aan de overschrijdingen.

## Het duale probleem

We kunnen de normaalvector $\mathbf {w}$ als een lineaire combinatie van de trainingsvoorbeelden schrijven:
    $\mathbf {w} =\sum _{i=1}^{n}\alpha _{i}y_{i}\mathbf {x} _{i}$
De variabelen $\alpha _{i}$ zijn Lagrange-multiplicators. De duale vorm is dan het maximiseringsprobleem:
    maximiseer $\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}\alpha _{i}\alpha _{j}y_{i}y_{j}(\mathbf {x} _{i}\cdot \mathbf {x} _{j})$
    met betrekking tot $\alpha _{i},i=1,\dots n$
    en met als voorwaarden:
    $0\leq \alpha _{i}\leq C$ en $\sum _{i=1}^{n}\alpha _{i}y_{i}=0$.
Merk op dat de restvariabelen $\xi _{i}$ hier niet meer voorkomen en de constante C niet meer in de doelfunctie staat maar als een beperking op de variabelen. De beslissingfunctie is dan:
    $f(\mathbf {x} )=\operatorname {sgn}(\mathbf {w} \cdot \mathbf {x} +b)=\operatorname {sgn} \left(\sum _{i=1}^{n}\alpha _{i}y_{i}(\mathbf {x} _{i}\cdot \mathbf {x} )+b\right)$
De trainingsvoorbeelden waarvan de Lagrangevariabelen $\alpha _{i}\neq 0$ noemt men de support vectors. Deze liggen ofwel op de marge (wanneer $y_{i}(\mathbf {w} \cdot \mathbf {x} )+b)=1$) ofwel in de marge ($\xi _{i}>0$). Enkel deze support vectors dragen bij aan de beslissingsfunctie.

## Niet-lineaire classificering

Een kenmerk van algoritmen als SVM is dat ze ook gebruikt kunnen worden wanneer de oorspronkelijke gegevens niet lineair scheidbaar zijn. We veronderstellen daarvoor dat er een afbeelding $\phi (\mathbf {x} )$ bestaat vanuit deze invoerruimte naar een andere, hogerdimensionale inwendig-productruimte. Deze ruimte heet in het Engels de feature space (merk op dat we niet eens eisen dat de invoerruimte een inwendig-productruimte is). We kunnen SVM dan toepassen in de feature space, door in het algoritme overal $\mathbf {x}$ te vervangen door $\phi (\mathbf {x} )$. Maar het algoritme gebruikt $\mathbf {x}$ enkel in inwendige producten $\mathbf {w} \cdot \mathbf {x}$, die worden vervangen door $\phi (\mathbf {w} )\cdot \phi (\mathbf {x} )$. Een (niet-lineaire) reële functie $K(\mathbf {x} ,\mathbf {z} )$ in de invoerruimte die correspondeert met het inwendig product van $\phi (\mathbf {x} )$ en $\phi (\mathbf {z} )$ in de feature space, noemt men een kernelfunctie of kortweg kernel.
    $K(\mathbf {x} ,\mathbf {z} )=\phi (\mathbf {x} )\cdot \phi (\mathbf {z} )$
We kunnen nu het inwendig product in het lineaire SVM-algoritme vervangen door de kernel. Het grote voordeel van deze kernel trick is dat we de vectoren $\phi (\mathbf {x} )$ in de feature space niet expliciet hoeven te berekenen. Dergelijke berekeningen kunnen zeer veel rekentijd vragen, terwijl $K(\mathbf {x} ,\mathbf {z} )$ vaak gemakkelijk te berekenen is. De feature space kan zeer veel dimensies hebben, in sommige gevallen zelfs oneindig veel. Met kernels wordt het potentieel toepassingsgebied van SVMs enorm groot. Er zijn bijvoorbeeld kernels geformuleerd voor grafen, strings en andere objecten. De uitdaging bestaat erin een geschikte kernel te vinden die de data lineair scheidbaar maakt in een feature space; het succes van een SVM hangt af van de keuze van de kernel, de parameters van de kernel en de constante C voor de overschrijdingen van het scheidingsvlak.
De lineaire classificeerder is slechts een bijzonder geval, waarbij de invoerruimte een inwendig-productruimte is die samenvalt met de feature space. Maar zelfs in dat geval is het soms nuttig om een kernelfunctie te gebruiken in plaats van het inwendig product.

### Voorbeeld

De kernelfunctie
    $K(\mathbf {x} ,\mathbf {z} )=(\mathbf {x} \cdot \mathbf {z} )^{2}$
correspondeert met de afbeelding van een invoerruimte met n dimensies naar een feature space met n$^2$ dimensies, bijvoorbeeld met n=3:
    $\mathbf {x} =(x_{1},x_{2},x_{3})$
    $\phi (\mathbf {x} )=(x_{1}x_{1},x_{1}x_{2},x_{1}x_{3},x_{2}x_{1},x_{2}x_{2},x_{2}x_{3},x_{3}x_{1},x_{3}x_{2},x_{3}x_{3})$
Men kan gemakkelijk verifiëren dat hier $K(\mathbf {x} ,\mathbf {z} )=(\mathbf {x} \cdot \mathbf {z} )^{2}=(x_{1}z_{1}+x_{2}z_{2}+x_{3}z_{3})^{2}=(\phi (\mathbf {x} )\cdot \phi (\mathbf {z} ))$

## Uitbreiding naar meerdere klassen

De eenvoudigste manier om data in meerdere klassen te classificeren met een SVM is door de opgave op te splitsen in afzonderlijke binaire problemen. In de "een-tegen-een"-benadering wordt een binaire SVM getraind voor elk paar klassen. Als er k klassen zijn verkrijgt men k(k-1)/2 beslissingsfuncties. In de beslissingsfase wordt elke beslissingsfunctie toegepast, wat resulteert in een "stem" voor een of andere klasse. De uiteindelijke keuze valt op de klasse die de meeste stemmen heeft vergaard. In de "een-tegen-allen"-benadering worden k beslissingsfuncties gemaakt die onderscheid maken tussen een bepaalde klasse en al de andere. In de beslissingsfase wordt niet alleen gekeken naar het teken maar ook naar de waarde van elke functie. De functie die de hoogste score geeft bepaalt de klasse (de functies van de klassificeerders moeten geijkt worden opdat de scores vergelijkbaar zijn; bij scalering veranderen de resultaten van een SVM niet).

## Toepassingen

SVM's zijn op vele gebieden bruikbaar, zoals:
* in tekstclassificatie (bijvoorbeeld bij spamfilters);
* het herkennen van handgeschreven tekens;
* het klasseren van afbeeldingen (bijvoorbeeld beslissen of een foto een gezicht voorstelt of niet);
* in biomedisch onderzoek, bijvoorbeeld voor het klasseren van weefselmonsters.