Was sind Support-Vektor-Maschinen?

Was sind Support-Vektor-Maschinen?

Support-Vektor-Maschinen sind eine Art von maschinellem Lernalgorithmus, der als einer der beliebtesten Klassifizierer gilt. Support-Vektor-Maschinen sind besonders nützlich für numerische Vorhersagen, Klassifizierungen und Mustererkennungsaufgaben.

Support-Vektor-Maschinen funktionieren, indem sie Entscheidungsgrenzen zwischen Datenpunkten zeichnen, wobei sie darauf abzielen, die Entscheidungsgrenze zu finden, die die Datenpunkte am besten in Klassen (oder am generalisierbarsten) trennt. Das Ziel bei der Verwendung einer Support-Vektor-Maschine ist, dass die Entscheidungsgrenze zwischen den Punkten so groß wie möglich ist, sodass der Abstand zwischen jedem gegebenen Datenpunkt und der Grenzlinie maximiert wird. Das ist eine kurze Erklärung, wie Support-Vektor-Maschinen (SVMs) funktionieren, aber lasst uns genauer betrachten, wie SVMs funktionieren und die Logik hinter ihrer Funktionsweise verstehen.

Ziel von Support-Vektor-Maschinen

Stellt euch ein Diagramm mit einer Anzahl von Datenpunkten vor, die auf der Grundlage von Merkmalen, die durch die X- und Y-Achsen angegeben sind, erstellt wurden. Die Datenpunkte auf dem Diagramm können lose in zwei verschiedene Cluster unterteilt werden, und der Cluster, zu dem ein Datenpunkt gehört, zeigt die Klasse des Datenpunkts an. Nehmt an, wir möchten eine Linie durch das Diagramm zeichnen, die die beiden Klassen voneinander trennt, mit allen Datenpunkten einer Klasse auf einer Seite der Linie und allen Datenpunkten, die zu einer anderen Klasse gehören, auf der anderen Seite der Linie. Diese trennende Linie wird als Hyperplane bezeichnet.

Man kann sich eine Support-Vektor-Maschine als eine “Straße” vorstellen, die durch eine Stadt verläuft und die Stadt in Bezirke auf beiden Seiten der Straße unterteilt. Alle Gebäude (Datenpunkte), die auf einer Seite der Straße liegen, gehören zu einem Bezirk.

Das Ziel einer Support-Vektor-Maschine ist es nicht nur, Hyperplanen zu zeichnen und Datenpunkte zu trennen, sondern auch, die Hyperplane zu zeichnen, die die Datenpunkte mit dem größten Abstand trennt, oder mit dem meisten Raum zwischen der Trennlinie und jedem gegebenen Datenpunkt. Wenn wir zur “Straßen”-Metapher zurückkehren, möchte ein Stadtplaner, der Pläne für eine Autobahn erstellt, nicht, dass die Autobahn zu nah an Häusern oder anderen Gebäuden liegt. Je größer der Abstand zwischen der Autobahn und den Gebäuden auf beiden Seiten, desto besser. Der größere dieser Abstand, desto “sicherer” kann der Klassifizierer bei seinen Vorhersagen sein. Im Falle der binären Klassifizierung bedeutet das Zeichnen der richtigen Hyperplane, eine Hyperplane zu wählen, die genau in der Mitte der beiden verschiedenen Klassen liegt. Wenn die Entscheidungsgrenze/Hyperplane weiter von einer Klasse entfernt ist, wird sie näher an eine andere Klasse heranrücken. Daher muss die Hyperplane den Abstand zwischen den beiden verschiedenen Klassen ausbalancieren.

Berechnung der trennenden Hyperplane

Wie bestimmt eine Support-Vektor-Maschine die beste trennende Hyperplane/Entscheidungsgrenze? Dies wird erreicht, indem mögliche Hyperplanen mit einer mathematischen Formel berechnet werden. Wir werden die Formel für die Berechnung von Hyperplanen nicht im Detail behandeln, aber die Linie wird mit der berühmten Steigungs-/Linienformel berechnet:

Y = ax + b

Während Linien aus Punkten bestehen, bedeutet dies, dass jede Hyperplane als die Menge von Punkten beschrieben werden kann, die parallel zur vorgeschlagenen Hyperplane verlaufen, wie durch die Gewichte des Modells multipliziert mit der Menge von Merkmalen modifiziert durch einen bestimmten Offset/Versatz (“d”) bestimmt.

SVMs zeichnen viele Hyperplanen. Zum Beispiel ist die Grenzlinie eine Hyperplane, aber die Datenpunkte, die der Klassifizierer berücksichtigt, liegen auch auf Hyperplanen. Die Werte für x werden auf der Grundlage der Merkmale im Datensatz bestimmt. Wenn man beispielsweise einen Datensatz mit den Körpergrößen und -gewichten vieler Menschen hätte, würden die “Körpergröße” und “Gewicht” die Merkmale sein, die zur Berechnung des “X” verwendet werden. Die Abstände zwischen der vorgeschlagenen Hyperplane und den verschiedenen “Support-Vektoren” (Datenpunkten), die auf beiden Seiten der Trennhyperplane liegen, werden mit der folgenden Formel berechnet:

W * X – b

Während man mehr über die Mathematik hinter SVMs lesen kann, wenn man ein intuitiveres Verständnis davon haben möchte, genügt es zu wissen, dass das Ziel darin besteht, den Abstand zwischen der vorgeschlagenen trennenden Hyperplane/Grenzlinie und den anderen Hyperplanen, die parallel dazu verlaufen (und auf denen die Datenpunkte liegen), zu maximieren.

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

Mehrklassifikation

Der bisher beschriebene Prozess gilt für binäre Klassifizierungsaufgaben. Allerdings können SVM-Klassifizierer auch für nicht-binäre Klassifizierungsaufgaben verwendet werden. Wenn man SVM-Klassifizierung auf einem Datensatz mit drei oder mehr Klassen durchführt, werden mehrere Trennlinien verwendet. Wenn beispielsweise eine Klassifizierungsaufgabe drei Klassen anstelle von zwei hat, werden zwei Trennlinien verwendet, um Datenpunkte in Klassen zu unterteilen, und die Region, die eine einzelne Klasse umfasst, liegt zwischen zwei Trennlinien anstelle von einer. Anstelle der Berechnung des Abstands zwischen nur zwei Klassen und einer Entscheidungsgrenze muss der Klassifizierer nun die Abstände zwischen den Entscheidungsgrenzen und den mehreren Klassen im Datensatz berücksichtigen.

Nicht-lineare Trennungen

Der bisher beschriebene Prozess gilt für Fälle, in denen die Daten linear trennbar sind. Beachten Sie, dass Datensätze in der Realität fast nie vollständig linear trennbar sind, was bedeutet, dass man bei der Verwendung eines SVM-Klassifizierers oft zwei verschiedene Techniken verwenden muss: weiche Margin und Kernel-Tricks. Betrachten Sie eine Situation, in der Datenpunkte verschiedener Klassen gemischt sind, wobei einige Instanzen einer Klasse in der “Gruppe” einer anderen Klasse liegen. Wie könnte man den Klassifizierer dazu bringen, diese Instanzen zu verarbeiten?

Eine Taktik, die verwendet werden kann, um nicht-linear trennbare Datensätze zu verarbeiten, ist die Anwendung eines “weichen Margin”-SVM-Klassifizierers. Ein weicher Margin-Klassifizierer funktioniert, indem er einige fehlklassifizierte Datenpunkte akzeptiert. Er wird versuchen, eine Linie zu zeichnen, die die Cluster von Datenpunkten am besten voneinander trennt, da sie die meisten Instanzen enthalten, die zu ihren jeweiligen Klassen gehören. Der weiche Margin-SVM-Klassifizierer versucht, eine Trennlinie zu erstellen, die die beiden Anforderungen des Klassifizierers ausbalanciert: Genauigkeit und Margin. Er wird versuchen, die Fehlklassifizierung zu minimieren, während er gleichzeitig den Abstand maximiert.

Die Toleranz des SVM-Klassifizierers für Fehler kann durch Manipulation eines Hyperparameters namens “C” angepasst werden. Der C-Wert kontrolliert, wie viele Support-Vektoren der Klassifizierer bei der Zeichnung von Entscheidungsgrenzen berücksichtigt. Der C-Wert ist eine Strafe, die auf Fehlklassifizierungen angewendet wird, was bedeutet, dass der größere C-Wert, desto weniger Support-Vektoren der Klassifizierer berücksichtigt und desto enger der Abstand.

Der Kernel-Trick transformiert die Daten nicht-linear und transformiert sie in eine nicht-lineare Form. Foto: Shiyu Ju via Wikmedia Commons, CC BY SA 4.0 (https://commons.wikimedia.org/wiki/File:Kernel_trick_idea.svg)

Der Kernel-Trick funktioniert, indem er nicht-lineare Transformationen auf die Merkmale im Datensatz anwendet. Der Kernel-Trick nimmt die vorhandenen Merkmale im Datensatz und erstellt neue Merkmale durch die Anwendung nicht-linearer mathematischer Funktionen. Was durch die Anwendung dieser nicht-linearen Transformationen entsteht, ist eine nicht-lineare Entscheidungsgrenze. Da der SVM-Klassifizierer nicht mehr auf das Zeichnen linearer Entscheidungsgrenzen beschränkt ist, kann er beginnen, gekrümmte Entscheidungsgrenzen zu zeichnen, die die tatsächliche Verteilung der Support-Vektoren besser umschließen und Fehlklassifizierungen minimieren. Zwei der beliebtesten nicht-linearen SVM-Kernel sind die Radial-Basis-Funktion und die Polynom-Funktion. Die Polynom-Funktion erstellt polynomische Kombinationen aller vorhandenen Merkmale, während die Radial-Basis-Funktion neue Merkmale durch Messen des Abstands zwischen einem zentralen Punkt/Punkten und allen anderen Punkten generiert.