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.[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. H1 is geen goede scheiding; zij classificeert 5 instanties van de zwarte klasse als wit. Verder is H3 te prefereren boven H2; een nieuw object dat slechts een beetje rechts van de bestaande zwarte objecten ligt zou tot de witte klasse gerekend worden door H2, 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 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   bestaat dan uit n punten en hun labels:

 

waarin yi +1 of −1 is, om aan te geven tot welke klasse het punt   behoort. Elke   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   scheidt van de punten met  . Een hypervlak wordt bepaald door een vergelijking van de vorm

 

waarin   het inwendig product van twee vectoren is.   is de normaalvector die loodrecht op het hypervlak staat en   is de afstand van het hypervlak tot de oorsprong volgens de richting van de normaalvector (  is de norm van de 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:

 

Om dit optimale hypervlak te construeren moet een optimaliseringsprobleem opgelost worden, dat als volgt geformuleerd kan worden:

minimiseer met betrekking tot  
met als voorwaarden  

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   berekend zijn, kan de SVM in de beslissingsfase een nieuwe vector   klasseren door het berekenen van de beslissingsfunctie

 

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  :  ,
met als beperkingen  

We voeren dus voor elk trainingsvoorbeeld een extra variabele   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   geeft in dit verband aan welk belang we hechten aan de overschrijdingen.

Het duale probleem bewerken

We kunnen de normaalvector   als een lineaire combinatie van de trainingsvoorbeelden schrijven:

 

De variabelen   zijn Lagrange-multiplicators. De duale vorm is dan het maximiseringsprobleem:

maximiseer  
met betrekking tot  
en met als voorwaarden:
  en  .

Merk op dat de restvariabelen   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:

 

De trainingsvoorbeelden waarvan de Lagrangevariabelen   noemt men de support vectors. Deze liggen ofwel op de marge (wanneer  ) ofwel in de marge ( ). 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   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   te vervangen door  . Maar het algoritme gebruikt   enkel in inwendige producten  , die worden vervangen door  . Een (niet-lineaire) reële functie   in de invoerruimte die correspondeert met het inwendig product van   en   in de feature space, noemt men een kernelfunctie of kortweg kernel.

 

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   in de feature space niet expliciet hoeven te berekenen. Dergelijke berekeningen kunnen zeer veel rekentijd vragen, terwijl   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

 

correspondeert met de afbeelding van een invoerruimte met n dimensies naar een feature space met n2 dimensies, bijvoorbeeld met n=3:

 
 

Men kan gemakkelijk verifiëren dat hier  

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 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.[2]

Externe links bewerken