Support Vector Machine - Eine Schritt für Schritt Erklärung wie dieser Machine Learning Algorithmus funktioniert
January 24, 2021
5 min
Machine Learning
Bevor wir uns intensiv mit dem Thema der künstlichen neuronalen Netze befassen, behandeln wir zunächst kurz die Algorithmen k-Nearest-Neighbor, Support Vector Machines (SVM) und Decision Trees. Da diese drei gängige Machine Learning Algorithmen sind, glauben wir, dass es sinnvoll ist grob zu wissen wie diese funktionieren, bevor wir das Gebiet der neuronalen Netze angehen. Nachdem wir uns im vorherigen Artikel mit dem k-Nearest-Neighbor Algorithmus befasst haben, behandelt dieser Beitrag das Thema der Support Vector Machines.
Eine SVM kann sowohl für die Aufgabe der Klassifikation als auch der Regression eingesetzt werden, wobei wir in diesem Artikel die Klassifikation behandeln. SVMs können eingesetzt werden, um eine Menge von Objekten einer bestimmten Klasse zuzuordnen. Wie immer kann ein Algorithmus am einfachsten an Hand eines Beispiels erläutert werden. Deshalb verwenden wir, wie bei dem k-Nearest-Neighbor Algorithmus auch, als Beispiel eine Pumpe, für die vorhergesagt werden soll, ob sie ausfällt oder nicht. Hierzu werden als Basis verschiedene Parameter, wie die durchschnittliche Drehzahl und Laufzeit, verwendet. Die Pumpe soll entweder der Klasse „Pumpe in Ordnung“ oder „Pumpenausfall steht bevor“ zugeordnet werden. Um diese Klassifikation durchführen zu können, werden die Daten von anderen Pumpen benötigt, die ausgefallen sind oder noch laufen.
Support Vector Machines können zur Klassifizierung von linear und insbesondere auch von nicht linear trennbaren Daten verwendet werden. Wir fangen hier mit linear trennbaren Daten an, und nähern uns Schritt für Schritt den nicht linear trennbaren Daten.
Klassifizierung von linear separierbaren Daten
Wir beginnen mit einem Beispiel im eindimensionalen Raum, da wir auf dieses Beispiel für die spätere Intuition bei nicht linear separierbaren Daten zurückkommen.
Eindimensionaler Raum
Stellen wir uns vor, der Ausfall einer Pumpe wird nur auf der Basis der bisherigen Laufzeit vorhergesagt. Weitere Parameter wie Schwingungen oder Drehzahl haben keinen Einfluss auf die Vorhersage. Da es sich um nur einen Parameter handelt, können die einzelnen Pumpen an Hand ihrer Laufzeit auf einer Linie aufgetragen werden, dargestellt in der folgenden Abbildung.
Die roten Punkte bedeuten, dass die Pumpe ausgefallen ist, die grünen, dass sie in Ordnung ist. Intuitiv ergibt es Sinn, dass Pumpen mit einer längeren Laufzeit eher ausfallen als Pumpen mit einer kurzen Laufzeit, was zu der Verteilung der Punkte in der Abbildung führt. Wird nun eine neue Pumpe, für die vorhergesagt werden soll ob sie ausfällt oder nicht, eingetragen, muss zunächst eine Grenze, im Machine Learning Bereich als decision boundary bezeichnet, zwischen den zwei Klassen gezogen werden. Auf Basis dieser Grenze kann die neue Pumpe dann entweder der Klasse „Pumpe in Ordnung“ oder „Pumpenausfall steht bevor“ zugeordnet werden. Doch wo soll die Grenze eingezeichnet werden? Die sinnvollste Variante wäre, die Grenze beim Mittelpunkt der beiden Grenzwerte der zwei Klassen einzuzeichnen. So wäre der Abstand von der Grenze zu den beiden Grenzwerten der Klassen gleich groß. Dieser Abstand, also der maximale Abstand der beiden Grenzwerte zur Grenze, wird als maximum-margin bezeichnet. Die eingezeichnete Grenze mit einer neuen Pumpe, in grün-gelb dargestellt, ist in der folgenden Abbildung zu sehen. Die neue Pumpe wird demnach der Klasse „Pumpe in Ordnung“ zugeordnet.
Der eingezeichnete Klassifizierer hat jedoch ein Problem: Die Ausreißer. Es kann immer sein, dass einzelne Daten sich nicht so verhalten wie der Großteil der anderen Daten. Bspw. kann eine Pumpe auf Grund eines Konstruktionsfehlers ungewöhnlich früh ausfallen, sodass sich folgendes Bild ergibt.
Klassifizierer, die Daten hart separieren, werden als hard-margin-classifier bezeichnet. Der Begriff der Margin lässt sich in diesem Kontext am ehesten mit dem Begriff des Bereichs oder der Spanne übersetzen. Für die verschiedenen Bezeichnungen der Klassifizierer gibt es keine passenden deutschen Übersetzungen, sodass wir im folgenden Verlauf die englischen Begriffe verwenden. Wird nun ein solcher hard-margin-classifier eingesetzt, kann es dazu kommen, dass neue Pumpen falsch klassifiziert werden. Und das nur auf Basis eines Ausreißers. Der Klassifizierer reagiert also super sensibel auf Ausreißer. Die Lösung dieses Problems besteht darin, eine bestimmte Anzahl an Missklassifizierungen in den Trainingsdaten zu erlauben. Hierdurch reagiert der Klassifizierer nicht mehr so sensibel auf Ausreißer. Diese Art der Klassifikation nennt sich soft-margin-classification [1]. Der Einsatz des soft-margin-classifiers ist in der folgenden Abbildung dargestellt.
Dies führt nun jedoch zu der nächsten Frage: Wie wird festgelegt wie viele Missklassifizierungen erlaubt sind? Eine, zwei, fünf oder vielleicht sogar zehn? Hierzu fügen wir eine weitere Dimension hinzu, sodass wir uns nun im zweidimensionalen Raum befinden.
Zweidimensionaler Raum
Zusätzlich zu der Laufzeit betrachten wir nun die durchschnittliche Drehzahl der Pumpe. Die einzelnen Pumpenkoordinaten zusammen mit einem soft-margin-classifier sind in der folgenden Abbildung zu sehen.
Die durchgezogene Linie stellt die Grenze, die decision boundary, dar. Diese wird, wie im Abschnitt zum eindimensionalen Raum beschrieben, durch die Grenzwerte der beiden Klassen definiert. Diese Grenzwerte sind die Stützvektoren, welche die Position der Grenze definieren. Diese Vektoren heißen im englischen Support Vectors, sodass wir nun auch wissen woher der Algorithmus seinen Namen hat. Die gestrichelten Linien sind die soft-margin, also der Bereich in dem Missklassifkationen erlaubt sind.
Das eigentliche Ziel des soft-margin-classifiers besteht darin, ein Gleichgewicht zwischen einer möglichst großen margin (Bereich) und der Anzahl der erlaubten Missklassifzierungen zu finden [2]. Hierdurch soll das Modell nicht zu stark auf Ausreißer reagieren, aber gleichzeitig die Gesetzmäßigkeiten der Daten hinreichend genau modellieren. Diese Problematik beide Ziele zu erreichen, wird als Verzerrung-Varianz-Dilemma (Bias-Variance-Tradeoff) bezeichnet. Diesem Thema widmen wir uns beim Thema der neuronalen Netze intensiver.
Nichtlineare Separierbarkeit
Bis hierhin konnten unsere Daten sehr gut voneinander getrennt werden, da sie linear separierbar waren. Im eindimensionalen Raum konnten die Daten der beiden Klassen durch einen Punkt, im zweidimensionalen Raum durch eine Gerade voneinander getrennt werden. Nun widmen wir uns jedoch den Daten, die nicht linear separierbar sind. Ein Beispiel ist in der folgenden Abbildung dargestellt.
Zu sehen sind wieder die beiden Klassen „Pumpe in Ordnung“ und „Pumpenausfall steht bevor“. Dieses Mal ist der einzig beobachtete Parameter die durchschnittliche Förderhöhe der jeweiligen Pumpe, über ihren Lebenszyklus verteilt. Pumpen werden auf eine bestimmte Förderhöhe ausgelegt: Ist diese für den Einsatzfall überdimensioniert worden, ist dies ebenso schädlich wie eine unterdimensionierte Pumpe. Nur Pumpen mit einer gut ausgelegten Förderhöhe sind langlebig, dies soll die Abbildung symbolisieren. Die Daten können nun nicht mehr durch einen einzelnen Punkt voneinander getrennt werden: Egal wo dieser eingezeichnet wird, viele Punkte werden der falschen Klasse zugeordnet. Um dieses Problem zu lösen wird bei Support Vector Machines ein Trick angewandt. Die Daten werden in einen höherdimensionalen Raum überführt. Aus unserem eindimensionalen wird nun ein zweidimensionaler Raum, wobei wir den Wert der Förderhöhe quadrieren. Das Ergebnis ist in der folgenden Abbildung dargestellt.
Durch die Überführung in einen höherdimensionalen Raum sind die Daten wieder linear separierbar und können gut klassifiziert werden. Dieser Trick wird als Kernel-Trick bezeichnet. Hierbei können verschiedene Algorithmen angewandt werden, um die Daten in einen höherdimensionalen Raum zu transferieren. Beispiele sind polynomiale oder RBF (raidale Basisfunktion) – Kernel [3]. Der Kernel-Trick erlaubt es uns Daten, die zunächst nicht linear trennbar waren, durch eine Überführung in einen höherdimensionalen Raum, linear trennbar zu gestalten. Natürlich ist das beschriebene Beispiel der Pumpe sehr einfach gehalten, da wir nun einen Paramater hatten. Zur besseren Veranschaulichung haben wir jedoch einen Raum mit niedriger Dimension gewählt.
Zusammenfassung
Support Vector Machines können sowohl für die Regression als auch die Klassifikation verwendet werden. Bei der Klassifikation kann der Algorithmus auf Daten die linear trennbar, aber insbesondere auf Daten, die nicht linear trennbar sind, angewendet werden. Hierzu wird der Kernel-Trick verwendet. Mit diesem Trick werden die Daten in einen höherdimensionalen Raum überführt, in dem sie linear trennbar sind und dadurch klassifiziert werden können.
In diesem Artikel haben wir eine Einführung in Support Vector Machines gegeben. Da wir uns hauptsächlich auf neuronale Netze fokussieren und zu anderen Algorithmen nur eine Intuition liefern möchten, haben wir auf mathematische Beschreibungen verzichtet. Während dies im nächsten Artikel zu Decision Trees ähnlich bleibt, widmen wir uns der Mathematik im Themenbereich der neuronalen Netze tiefer. Wer jedoch mehr über Support Vector Machines erfahren möchte, dem legen wir die beiden folgenden Artikel ans Herz.
