Wat zijn Ondersteuningsvector Machines?

Wat zijn Ondersteuningsvector Machines?

Ondersteuningsvector machines zijn een type machine learning classifier, mogelijk een van de meest populaire soorten classificatoren. Ondersteuningsvector machines zijn vooral nuttig voor numerieke voorspelling, classificatie en patroonherkenningstaken.

Ondersteuningsvector machines werken door beslissingsgrenzen tussen gegevenspunten te trekken, met als doel de beslissingsgrens die de gegevenspunten het beste in klassen verdeelt (of het meest generaliseerbaar is). Het doel bij het gebruik van een ondersteuningsvector machine is dat de beslissingsgrens tussen de punten zo groot mogelijk is, zodat de afstand tussen een gegeven gegevenspunt en de grenslijn gemaximaliseerd wordt. Dat is een korte verklaring van hoe ondersteuningsvector machines (SVM’s) werken, maar laten we wat dieper ingaan op hoe SVM’s werken en de logica achter hun werking begrijpen.

Doel van Ondersteuningsvector Machines

Stel je een grafiek voor met een aantal gegevenspunten erop, gebaseerd op kenmerken die zijn gespecificeerd door de X- en Y-as. De gegevenspunten op de grafiek kunnen losjes worden onderverdeeld in twee verschillende clusters, en het cluster waarin een gegevenspunt valt, geeft de klasse van het gegevenspunt aan. Stel nu dat we een lijn over de grafiek willen trekken die de twee klassen van elkaar scheidt, met alle gegevenspunten in een klasse aan één kant van de lijn en alle gegevenspunten die tot een andere klasse behoren aan de andere kant van de lijn. Deze scheidinglijn wordt een hyperplane genoemd.

Je kunt een ondersteuningsvector machine zien als een “weg” die door een stad loopt, waardoor de stad in districten aan weerszijden van de weg wordt verdeeld. Alle gebouwen (gegevenspunten) die aan één kant van de weg liggen, behoren tot één district.

Het doel van een ondersteuningsvector machine is niet alleen om hyperplanes te trekken en gegevenspunten te verdelen, maar om de hyperplane te trekken die de gegevenspunten met de grootste marge scheidt, of met de meeste ruimte tussen de scheidinglijn en een gegeven gegevenspunt. Terugkerend naar de “wegen” metafoor, als een stedenbouwkundige plannen maakt voor een snelweg, wil hij niet dat de snelweg te dicht bij huizen of andere gebouwen komt. Hoe groter de marge tussen de snelweg en de gebouwen aan weerszijden, hoe beter. Hoe groter deze marge, hoe “zekerder” de classificator kan zijn over zijn voorspellingen. In het geval van binaire classificatie betekent het trekken van de juiste hyperplane het kiezen van een hyperplane die precies in het midden van de twee verschillende klassen ligt. Als de beslissingsgrens/hyperplane verder van een klasse af ligt, zal deze dichter bij een andere klasse liggen. Daarom moet de hyperplane de marge tussen de twee verschillende klassen in evenwicht brengen.

Berekening van de Scheidingshyperplane

Hoe bepaalt een ondersteuningsvector machine de beste scheidingshyperplane/beslissingsgrens? Dit gebeurt door mogelijke hyperplanes te berekenen met een wiskundige formule. We zullen de formule voor het berekenen van hyperplanes niet in extreme details behandelen, maar de lijn wordt berekend met de beroemde hellings-/lijnformule:

Y = ax + b

Ondertussen bestaan lijnen uit punten, wat betekent dat elke hyperplane kan worden beschreven als: de verzameling punten die evenwijdig lopen aan de voorgestelde hyperplane, zoals bepaald door de gewichten van het model maal de verzameling kenmerken gewijzigd door een gespecificeerde offset/bias (“d”).

SVM’s trekken veel hyperplanes. Bijvoorbeeld, de grenslijn is één hyperplane, maar de datapunten die de classificator in overweging neemt, liggen ook op hyperplanes. De waarden voor x worden bepaald op basis van de kenmerken in de dataset. Als je bijvoorbeeld een dataset hebt met de lengte en het gewicht van veel mensen, zouden de “lengte” en “gewicht” kenmerken de kenmerken zijn die worden gebruikt om de “X” te berekenen. De marges tussen de voorgestelde hyperplane en de verschillende “ondersteuningsvectoren” (datapunten) die aan weerszijden van de scheidinghyperplane liggen, worden berekend met de volgende formule:

W * X – b

Terwijl je meer kunt lezen over de wiskunde achter SVM’s, als je op zoek bent naar een meer intuïtieve begrip van hen, weet dan dat het doel is om de afstand tussen de voorgestelde scheidinghyperplane/grenslijn en de andere hyperplanes die evenwijdig lopen aan deze (en waarop de datapunten liggen) te maximaliseren.

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

Meerklassenclassificatie

Het proces dat tot nu toe is beschreven, is van toepassing op binaire classificatie taken. Echter, SVM-classificatoren kunnen ook worden gebruikt voor niet-binaire classificatie taken. Wanneer een SVM-classificatie op een dataset met drie of meer klassen wordt uitgevoerd, worden meer grenslijnen gebruikt. Als een classificatie taak bijvoorbeeld drie klassen heeft in plaats van twee, worden twee scheidinglijnen gebruikt om de datapunten in klassen te verdelen en de regio die een enkele klasse omvat, valt tussen twee scheidinglijnen in plaats van één. In plaats van alleen de afstand tussen twee klassen en een beslissingsgrens te berekenen, moet de classificator nu de marges tussen de beslissingsgrenzen en de meerdere klassen in de dataset in overweging nemen.

Niet-lineaire Scheidingen

Het proces dat hierboven is beschreven, is van toepassing op gevallen waarin de gegevens lineair gescheiden zijn. Let op dat, in werkelijkheid, datasets bijna nooit volledig lineair gescheiden zijn, wat betekent dat bij het gebruik van een SVM-classificator je vaak twee verschillende technieken moet gebruiken: zachte marge en kernel trucs. Overweeg een situatie waarin datapunten van verschillende klassen gemengd zijn, met sommige instanties die tot een klasse behoren in de “cluster” van een andere klasse. Hoe kun je de classificator laten omgaan met deze instanties?

Een tactiek die kan worden gebruikt om niet-lineair gescheiden datasets te verwerken, is het toepassen van een “zachte marge” SVM-classificator. Een zachte marge classificator werkt door een paar misgeclassificeerde datapunten te accepteren. Het zal proberen een lijn te trekken die de clusters van datapunten het beste van elkaar scheidt, zoals deze de meeste instanties bevatten die tot hun respectievelijke klassen behoren. De zachte marge SVM-classificator probeert een scheidinglijn te creëren die de twee eisen van de classificator in evenwicht brengt: nauwkeurigheid en marge. Het zal proberen de misclassificatie te minimaliseren terwijl het tegelijkertijd de marge maximaliseert.

De tolerantie van de SVM voor fouten kan worden aangepast door manipulatie van een hyperparameter genaamd “C”. De C-waarde controleert hoeveel ondersteuningsvectoren de classificator in overweging neemt bij het trekken van beslissingsgrenzen. De C-waarde is een straf die wordt toegepast op misclassificaties, wat betekent dat hoe groter de C-waarde, hoe minder ondersteuningsvectoren de classificator in overweging neemt en hoe smaller de marge.

De kernel truc transformeert de gegevens op een niet-lineaire manier. Foto: Shiyu Ju via Wikmedia Commons, CC BY SA 4.0 (https://commons.wikimedia.org/wiki/File:Kernel_trick_idea.svg)

De Kernel Trick werkt door niet-lineaire transformaties toe te passen op de kenmerken in de dataset. De Kernel Trick neemt de bestaande kenmerken in de dataset en creëert nieuwe kenmerken door het toepassen van niet-lineaire wiskundige functies. Wat resulteert uit het toepassen van deze niet-lineaire transformaties is een niet-lineaire beslissingsgrens. Omdat de SVM-classificator niet langer beperkt is tot het trekken van lineaire beslissingsgrenzen, kan deze beginnen met het trekken van gebogen beslissingsgrenzen die de werkelijke verdeling van de ondersteuningsvectoren beter omvatten en misclassificaties tot een minimum beperken. Twee van de meest populaire niet-lineaire SVM-kernels zijn Radial Basis Function en Polynomial. De polynomial functie creëert polynomiale combinaties van alle bestaande kenmerken, terwijl de Radial Basis Function nieuwe kenmerken genereert door de afstand te meten tussen een centraal punt/punten en alle andere punten.