5. Support Vector Machines Flashcards
Für was SVM?
Eines der bekanntesten Verfahren für die binäre Klassifikation
Bester Klassifikator für Textklassifizierung
Welche Art Inputattribute für SVM?
SVM kann nur numerische Attribute in zwei Klassen verarbeiten. Mehr als zwei müssen nacheinander abgearbeitet werden.
Lineare SVM (hyperplane) Grundlage
- Es werden zwei Inputattribute in einem Scatter-Plot bei dem jedes Element als Kästchen/Kringel ist dargestellt. Durch diese Punktwolke soll nun eine Gerade gezogen werden, die beide Klassen voneinander trennt.
- Die optimale Hyperebene ist diejenige, die den größten Abstand (Margin) zwischen den nächstgelegenen Punkten beider Klassen hat, um die Klassifikation zu maximieren
Linear trennbare SVM, Gleichung Support Vectoren?
- Betrachtet man einen positiven Datenpunkt (x+, 1) und einen negativen (x-, -1), die der Hyperebene am nächsten liegen (Unterstützungsvektoren).
- In der Gleichung für die Gerade ist w der Vektor mit Gewichten (für jede Dimension also jedes Attribut) und x der Vektor mit allen Attributwerten. Der Output-Wert dieser Formel gibt nun an, ob ein Punkt zu der einen oder der anderen Klasse gehört. Ist der Wert > 0 so liegt die eine Klasse vor, bei < 0 die andere. Setzen wir die Gleichung gleich Null so erhalten wir die Gerade.
- Man erkennt leicht, dass b die Gerade vertikal verschiebt und das Verhältnis der Gewichte der beiden Attribute die Neigung der Geraden verändert.
- Natürlich gibt es jetzt beliebig viele Geraden, die die beiden Klassen trennen (wie die Abbildung rechts zeigt).
- Wir suchen daher die Gerade, die die beiden Klassen so trennt, dass der Abstand von der Geraden zu den am nächsten dranliegenden Punkten möglichst groß ist, damit wir bei unserer Klassifikation einen möglichst großen “Sicherheitsabstand” haben.
- Diese nächsten Punkte bestimmen also die Lage der Geraden und heißen daher auch Support-Vektoren.
Wie wird also die Klassifikation mit SVM gelöst?
- Wir wollen den Abstand maximieren oder anders ausgedrückt den Reziprokwert minimieren
- Die Punkte sollen jeweils auf der richtigen Seite liegen, was sich durch zwei Bedingungen ausdrücken lässt
- Und was ergibt das Ganze dann? Ein Problem der linearen Optimieren.
- Wir haben also das Problem der Klassifikation auf ein Problem der linearen Optimierung oder linearen Programmierung zurückgeführt.
- Und für dieses Problem gibt es bekannte Algorithmen, z.b. der Simplex-Algorithmus.
- Prinzipiell ist das Problem der Klassifikation damit gelöst.
Nebenbedingungen SVM?
- Für alle Datenpunkte, die zur positiven Klasse gehören der Ausdruck mindestens 1 sein muss. Dadurch wird sichergestellt, dass diese Punkte auf der “richtigen” Seite der Hyperebene liegen.
- Für alle Datenpunkte, die zur negativen Klasse gehören der Ausdruck höchstens -1 sein muss. Dadurch wird sichergestellt, dass diese Punkte ebenfalls auf der “richtigen” Seite der Hyperebene liegen.
Ergebnis: ist ein Problem der linearen Optimierung. Also wurde das Problem der Klassifikation auf ein Problem der linearen Optimierung zurückgeführt. Und um dieses Problem anschließend zu lösen, gibt es bekannte Algorithmen, zum Beispiel der Simplex-Algorithmus.
Nicht linear trennbare SVM?
Was, wenn die Punkte nicht linear trennbar sind? Wenn einige Punkte immer auf der falschen Seite liegen?
Wir bauen in unsere Nebenbedingungen, die ja immer erfüllt sein müssen, einfach eine Korrekturgröße ein (sog. Slack-Variablen), die dazu führen, dass die Bedingung erfüllt ist. Wir verschieben den Punkt einfach so weit, dass er auf der richtigen Seite der Gerade liegt.
Aber so könnte man ja Punkte beliebig rumverschieben, egal wie falsch die Punkte vorher waren?
Ja, daher vernünftige Lösung noch fordern, dass die Summe aller Slack-Variaben möglichst klein sein soll
Und wo passt diese Forderung gut hinein? In die Zielfunktion der linearen Optimieren. Nun soll also nicht nur der Reziprokwert des Abstands der Punkte zur Gerade sondern zusätzlich auch noch die Summe der Slack-Variablen minimal werden
SVM Einschränkungen
Real-Valued Space: SVM geht nur in einem Real-Valued Space, also müssen kategorische Attribute in numerische Werte konvertiert werden.
Two-Class Klassifikation: SVM führt nur Zweiklassenklassifizierung durch. Mehrklassenprobleme können durch spezifische Strategien angegangen werden, z. B.
One-against-rest (für jede Klasse ein separater SVM-Classifier, jeder SVM-Classifier eine Klasse als positive Klasse und alle anderen Klassen zusammen als negative Klasse behandelt. Im Einsatz wird ein neuer Datenpunkt durch jeden dieser Classifier getestet und der Classifier mit der höchsten Ausgabewahrscheinlichkeit bestimmt die Klassenzugehörigkeit des Datenpunkts)
Beispiel SVM Werte
- function value: gibt das Ergebnis der Gleichung an.
o Linear Trennbar: sollten alle Werte entweder größer gleich 1 oder kleiner gleich -1 sein. Alle Vektoren mit Ergebnis 1 oder -1 sind dann Support Vektoren.
o Nicht linear Trennbar: kommen auch Werte innerhalb des Intervals von -1 bis 1 vor. Alle Werte kleiner 0 gehören dann zur negativen Klasse und alle Werte größer 0 zur positiven Klasse. Alle Vektoren mit einem Wert zwischen -1 und 1 sind dann Support-Vektoren. - Alpha: gibt an, ob und wie stark ein Vektor in die Berechnung einfließt (alpha ungleich 0 = Support Vektoren)
Nichtlineare SVM
Was machen wir nun aber, wenn die beiden Klassen grundsätzlich nicht linear trennbar sind (und das Problem folglich auch nicht mit Slack-Variablen gelöst werden kann)?
–> Wir transformieren die Eingabedaten meist in eine höheren Dimension, sodass eine lineare Entscheidungsgrenze positive & negative Beispiele im transformierten Raum trennen kann
Der transformierte Space wird als Feature-Space bezeichnet, der ursprüngliche Data-Space als Input-Space.
Beispiel: Wir transformieren unsere Fläche in den dreidimensionalen Raum in Form eines Zuckerhuts. Die eine Klasse (die sich in der Mitte befand) ist dann die Spitze des Zuckerhuts und kann mit einer Ebene linear abgetrennt werden (so wie wenn sie ein Ei köpfen).
Kann auch funktionieren, ohne dass der “feature space” also der transformierte Raum mehr Dimensionen hat
Die Wahrscheinlichkeit, dass sich die beiden Klassen linear trennen lassen nimmt aber zu, wenn wir in den höherdimensionalen Raum transformieren.
Nichtlineare SVM Problem und Lösung?
Eigentlich ist das Problem nun gelöst, doch durch die Lösung dieses Problems haben wir uns eventuell ein neues Problem geschaffen.
Der Rechenaufwand für die lineare Optimierung wird durch die vielen Dimensionen extrem hoch. Um wiederum dann dieses Problem zu lösen wird der Kernel-Trick angewandt.
Durch die Kernel Funktion ist es nicht nötig, die den Merkmalsvektor selbst zu kennen
Kernel Funktion?
Der Kernel-Trick dient nur zur Laufzeitoptimierung und verändert nichts and der prinzipiellen Vorgehensweise. Beim Kernel-Trick wird die Kernel-Funktion angewandt. Diese transformiert das Skalarprodukt (Vektoren miteinander multipliziert Produkte summiert Eine eindimensionale Zahl bleibt übrig). Diese liefert dann direkt die eindimensionale Zahl, welche für das Verfahren benötigt wird. Hierfür existieren schon einige gute Kernelfunktionen, welche gute Wahrscheinlichkeiten liefern. (z.B. die polynominale Kernelfunktion)
Woher wissen wir, dass eine Kernel-Funktion tatsächlich ein Punktprodukt in irgendeinem Feature-Space ist?
- Symmetrie: Die Kernel-Funktion muss symmetrisch sein. Reihenfolge der Punkte spielen keine Rolle
- Nichtnegativität: Der Wert der Kernel-Funktion muss immer größer oder gleich Null sein. Das bedeutet, dass die Ähnlichkeit eines Punktes mit sich selbst immer positiv ist.
- Definiertheit: Eine Kernel-Funktion wird als positiv definit betrachtet. Für eine beliebige endliche Anzahl von verschiedenen Punkten ist die quadratische Summe der Produkte größer oder gleich Null.
