Support vector machine

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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.[1] Ze heeft vele uiteenlopende toepassingen in classificatie en regressie-analyse.

Principe[bewerken]

In dit voorbeeld zijn H2 en H3 twee acceptabele lineaire scheidingen tussen de twee klassen. Maar H1 is geen goede scheiding; een nieuw object dat slechts een beetje rechts van de bestaande zwarte objecten ligt zou tot de witte klasse gerekend worden, wat intuïtief gezien niet juist is. H3 is de optimale scheiding omdat de marge tussen de lijn en de twee klassen maximaal is.

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 meerdere duizenden dimensies aan.

Lineaire classificatie[bewerken]

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 yi +1 of −1 is, om aan te geven tot welke klasse het punt \mathbf{x}_i behoort. Elke  \mathbf{x}_i is a 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 een vector.

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) \ge 1, i = 1, \dots n

Dit is een niet-lineair optimaliseringsprobleem, meer bepaald een convex kwadratisch 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) = \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[bewerken]

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) \ge 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[bewerken]

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 \le \alpha_i \le 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)= \sgn ( \mathbf w \cdot \mathbf x + b) = \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[bewerken]

Transformatie van niet-lineaire naar lineaire scheiding

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[bewerken]

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 n2 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[bewerken]

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[bewerken]

SVM's zijn op vele gebieden bruikbaar, zoals:

  • in tekstclassificatie (bijvoorbeeld om nieuwe e-mail-berichten te klasseren als "spam" of "geen spam");
  • 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.[2]

Externe links[bewerken]

Bronnen, noten en/of referenties
  1. Vladimir Vapnik. The Nature of Statistical Learning Theory. Springer-Verlag, 1995. ISBN 0-387-98780-0
  2. Terrence S. Furey, Nello Cristianini, Nigel Duffy, David W. Bednarski, Michèl Schummer, David Haussler. "Support vector machine classification and validation of cancer tissue samples using microarray expression data." Bioinformatics (2000), vol. 16 nr. 10, blz. 906-914. DOI:10.1093/bioinformatics/16.10.906