Support Vector Machine

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Eine Support Vector Machine [səˈpɔːt ˈvektə məˈʃiːn] (SVM, die Übersetzung aus dem Englischen, „Stützvektormaschine“ oder Stützvektormethode, ist nicht gebräuchlich) ist ein Klassifikator (vgl. Klassifizierung). Eine Support Vector Machine unterteilt eine Menge von Objekten so in Klassen, dass um die Klassengrenzen herum ein möglichst breiter Bereich frei von Objekten bleibt; sie ist ein sogenannter Large Margin Classifier (engl. „Breiter-Rand-Klassifikator“). Support Vector Machines können sowohl zur Klassifizierung als auch zur Regression verwendet werden.

Support Vector Machines sind keine Maschinen im herkömmlichen Sinne, bestehen also nicht aus greifbaren Bauteilen. Es handelt sich um ein rein mathematisches Verfahren der Mustererkennung, das in Computerprogrammen umgesetzt wird. Der Namensteil machine weist dementsprechend nicht auf eine Maschine hin, sondern auf das Herkunftsgebiet der Support Vector Machines, das maschinelle Lernen.

Grundlegende Funktionsweise[Bearbeiten | Quelltext bearbeiten]

Zwei mögliche Trenngeraden mit verschiedenen Randgrößen

Ausgangsbasis für den Bau einer Support Vector Machine ist eine Menge von Trainingsobjekten, für die jeweils bekannt ist, welcher Klasse sie zugehören. Jedes Objekt wird durch einen Vektor in einem Vektorraum repräsentiert. Aufgabe der Support Vector Machine ist es, in diesen Raum eine Hyperebene einzupassen, die als Trennfläche fungiert und die Trainingsobjekte in zwei Klassen teilt. Der Abstand derjenigen Vektoren, die der Hyperebene am nächsten liegen, wird dabei maximiert. Dieser breite, leere Rand soll später dafür sorgen, dass auch Objekte, die nicht genau den Trainingsobjekten entsprechen, möglichst zuverlässig klassifiziert werden.

Beim Einsetzen der Hyperebene ist es nicht notwendig, alle Trainingsvektoren zu beachten. Vektoren, die weiter von der Hyperebene entfernt liegen und gewissermaßen hinter einer Front anderer Vektoren „versteckt“ sind, beeinflussen Lage und Position der Trennebene nicht. Die Hyperebene ist nur von den ihr am nächsten liegenden Vektoren abhängig – und auch nur diese werden benötigt, um die Ebene mathematisch exakt zu beschreiben. Diese nächstliegenden Vektoren werden nach ihrer Funktion Stützvektoren (engl. support vectors) genannt und verhalfen den Support Vector Machines zu ihrem Namen.

Lineare Trennbarkeit

Eine Hyperebene kann nicht „verbogen“ werden, sodass eine saubere Trennung mit einer Hyperebene nur dann möglich ist, wenn die Objekte linear trennbar sind. Diese Bedingung ist für reale Trainingsobjektmengen im Allgemeinen nicht erfüllt. Support Vector Machines verwenden im Fall nichtlinear trennbarer Daten den Kernel-Trick, um eine nichtlineare Klassengrenze einzuziehen.

Die Idee hinter dem Kernel-Trick ist, den Vektorraum und damit auch die darin befindlichen Trainingsvektoren in einen höherdimensionalen Raum zu überführen. In einem Raum mit genügend hoher Dimensionsanzahl – im Zweifelsfall unendlich – wird auch die verschachteltste Vektormenge linear trennbar. In diesem höherdimensionalen Raum wird nun die trennende Hyperebene bestimmt. Bei der Rücktransformation in den niedrigerdimensionalen Raum wird die lineare Hyperebene zu einer nichtlinearen, unter Umständen sogar nicht zusammenhängenden Hyperfläche, die die Trainingsvektoren sauber in zwei Klassen trennt.

Bei diesem Vorgang stellen sich zwei Probleme: Die Hochtransformation ist enorm rechenlastig und die Darstellung der Trennfläche im niedrigdimensionalen Raum im Allgemeinen unwahrscheinlich komplex und damit praktisch unbrauchbar. An dieser Stelle setzt der Kernel-Trick an. Verwendet man zur Beschreibung der Trennfläche geeignete Kernelfunktionen, die im Hochdimensionalen die Hyperebene beschreiben und trotzdem im Niedrigdimensionalen „gutartig“ bleiben, so ist es möglich, die Hin- und Rücktransformation umzusetzen, ohne sie tatsächlich rechnerisch ausführen zu müssen. Auch hier genügt ein Teil der Vektoren, nämlich wiederum die Stützvektoren, um die Klassengrenze vollständig zu beschreiben.

Sowohl lineare als auch nichtlineare Support Vector Machines lassen sich durch zusätzliche Schlupfvariablen flexibler gestalten. Die Schlupfvariablen erlauben es dem Klassifikator, einzelne Objekte falsch zu klassifizieren, „bestrafen“ aber gleichzeitig jede derartige Fehleinordnung. Auf diese Weise wird zum einen Überanpassung vermieden, zum anderen wird die benötigte Anzahl an Stützvektoren gesenkt.

Mathematische Umsetzung[Bearbeiten | Quelltext bearbeiten]

Die SVM bestimmt anhand einer Menge von Trainingsbeispielen

eine Hyperebene, die beide Klassen so voneinander trennt, dass der kleinste Abstand zur Hyperebene, das so genannte Margin (von englisch margin, Marge), für die Beispiele beider Klassen maximiert wird, um eine möglichst gute Generalisierbarkeit des Klassifikators zu garantieren. Dabei gibt die Klassenzugehörigkeit für das Trainingsbeispiel an. Das sogenannte Training berechnet die Hyperebene, die die Trainingsbeispiele beider Klassen bestmöglich teilt. Sie wird dann als Entscheidungsfunktion benutzt. Sie ist gegeben durch einen Normalenvektor  und einen sogenannten Bias . Einem Entscheidungsobjekt  wird dabei das Vorzeichen der Entscheidungsfunktion als Klasse zugeordnet:

.

Je nachdem, wo sich die Objekte relativ zur Hyperebene befinden (oberhalb oder unterhalb), errechnet sich ein positiver oder negativer Wert, wo nach Anwendung der Vorzeichenfunktion nur noch verbleibt. Für Objekte, die genau auf der Trennebene liegen, wird dieser Wert zu .

Linear separierbare Daten[Bearbeiten | Quelltext bearbeiten]

Viele Lernalgorithmen arbeiten mit einer linearen Funktion in Form einer Hyperebene. Sind zwei Klassen von Beispielen durch eine Hyperebene voneinander trennbar, d.h. linear separierbar, gibt es jedoch in der Regel unendlich viele Hyperebenen, die die beiden Klassen voneinander trennen. Die SVM unterscheidet sich von anderen Lernalgorithmen dadurch, dass sie von allen möglichen trennenden Hyperebenen diejenige mit minimaler quadratischer Norm auswählt, so dass gleichzeitig für jedes Trainingsbeispiel gilt. Dies ist mit der Maximierung des kleinsten Abstands zur Hyperebene (dem Margin) äquivalent. Nach der statistischen Lerntheorie ist die Komplexität der Klasse aller Hyperebenen mit einem bestimmten Margin geringer als die der Klasse aller Hyperebenen mit einem kleineren Margin. Daraus lassen sich obere Schranken für den erwarteten Generalisierungsfehler der SVM ableiten.

Das Optimierungsproblem kann dann geschrieben werden als:

Minimiere den Term durch Anpassung der Variablen ,
so dass die Nebenbedingung für alle gilt.

Nicht-linear separierbare Daten[Bearbeiten | Quelltext bearbeiten]

In der Regel sind die Trainingsbeispiele nicht streng linear separierbar. Dies kann u.a. an Messfehlern in den Daten liegen, oder daran, dass die Verteilungen der beiden Klassen natürlicherweise überlappen. Für diesen Fall wird das Optimierungsproblem derart verändert, dass Verletzungen der Nebenbedingungen möglich sind, die Verletzungen aber so klein wie möglich gehalten werden sollen. Zu diesem Zweck wird eine positive Schlupfvariable für jede Nebenbedingung eingeführt, deren Wert gerade die Verletzung der Nebenbedingungen ist. bedeutet also, dass die Nebenbedingung verletzt ist. Da in der Summe die Verletzungen möglichst klein gehalten werden sollen, wird die Summe der Fehler der Zielfunktionen hinzugefügt und somit ebenso minimiert. Zusätzlich wird diese Summe mit einer positiven Konstante multipliziert, die den Ausgleich zwischen der Minimierung von und der korrekten Klassifizierung der Trainingsbeispiele regelt. Das Optimierungsproblem besitzt dann folgende Form:

Minimiere den Term durch Anpassung der Variablen ,
so dass die Nebenbedingung für alle gilt.

Duales Problem[Bearbeiten | Quelltext bearbeiten]

Beide Optimierungskriterien sind konvex und können mit modernen Verfahren effizient gelöst werden. Diese einfache Optimierung und die Eigenschaft, dass Support Vector Machines eine Überanpassung an die zum Entwurf des Klassifikators verwendeten Testdaten großteils vermeiden, haben der Methode zu großer Beliebtheit und einem breiten Anwendungsgebiet verholfen.

Beispiel für eine Klassifizierung mit einer SVM. Zu sehen ist die in den Eingangsraum abgebildete trennende Hyperebene (schwarze Linie) und die Support-Vektoren (dünn türkis umkreist).

Das oben beschriebene Optimierungsproblem wird normalerweise in seiner dualen Form gelöst. Diese Formulierung ist äquivalent zu dem primalen Problem, in dem Sinne, dass alle Lösungen des dualen auch Lösungen des primalen Problems sind. Die Umrechnung ergibt sich dadurch, dass der Normalenvektor als Linearkombination aus Trainingsbeispielen geschrieben werden kann:

Die duale Form wird mit Hilfe der Lagrange-Multiplikatoren und der Karush-Kuhn-Tucker-Bedingungen hergeleitet. Sie lautet:

maximiere für : ,
so dass die Nebenbedingungen und gelten.

Damit ergibt sich als Klassifikationsregel:

Ihren Namen hat die SVM von einer speziellen Untermenge der Trainingspunkte, deren Lagrangevariablen . Diese heißen Support-Vektoren und liegen entweder auf dem Margin (falls ) oder innerhalb des Margin ().

Nichtlineare Erweiterung mit Kernelfunktionen[Bearbeiten | Quelltext bearbeiten]

Der oben beschriebene Algorithmus klassifiziert die Daten mit Hilfe einer linearen Funktion. Diese ist jedoch nur optimal, wenn auch das zu Grunde liegende Klassifikationsproblem linear ist. In vielen Anwendungen ist dies aber nicht der Fall. Ein möglicher Ausweg ist, die Daten in einen Raum höherer Dimension abzubilden.

Dabei gilt . Durch diese Abbildung wird die Anzahl möglicher linearer Trennungen erhöht (Theorem von Cover [1]). SVMs zeichnen sich dadurch aus, dass sich diese Erweiterung sehr elegant einbauen lässt. In das dem Algorithmus zu Grunde liegende Optimierungsproblem in der zuletzt dargestellten Formulierung gehen die Datenpunkte nur in Skalarprodukten ein. Daher ist es möglich, das Skalarprodukt im Eingaberaum durch ein Skalarprodukt im zu ersetzen und stattdessen direkt zu berechnen. Die Kosten dieser Berechnung lassen sich sehr stark reduzieren, wenn eine positiv definite Kernelfunktion stattdessen benutzt wird:

Durch dieses Verfahren kann eine Hyperebene (d.h. eine lineare Funktion) in einem hochdimensionalen Raum implizit berechnet werden. Der resultierende Klassifikator hat die Form

mit . Durch die Benutzung von Kernelfunktionen können SVMs auch auf allgemeinen Strukturen wie Graphen oder Strings operieren und sind daher sehr vielseitig einsetzbar. Obwohl durch die Abbildung implizit ein möglicherweise unendlich-dimensionaler Raum benutzt wird, generalisieren SVM immer noch sehr gut. Es lässt sich zeigen, dass für Maximum-Margin-Klassifizierer der erwartete Testfehler beschränkt ist und nicht von der Dimensionalität des Raumes abhängt.

Geschichte[Bearbeiten | Quelltext bearbeiten]

Die Idee der Trennung durch eine Hyperebene hatte bereits 1936 Ronald A. Fisher.[2] Wieder aufgegriffen wurde sie 1958 von Frank Rosenblatt in seinem Beitrag[3] zur Theorie künstlicher neuronaler Netze. Die Idee der Support Vector Machines geht auf die Arbeit von Wladimir Wapnik und Aleksei Tscherwonenkis[4] zurück. Auf theoretischer Ebene ist der Algorithmus vom Prinzip der strukturellen Risikominimierung motiviert, welches besagt, dass nicht nur der Trainingsfehler, sondern auch die Komplexität des verwendeten Modells die Generalisierungsfähigkeit eines Klassifizierers bestimmen. In der Mitte der 1990er Jahre gelang den SVMs der Durchbruch, und zahlreiche Weiterentwicklungen und Modifikationen wurden in den letzten Jahren veröffentlicht.

Software[Bearbeiten | Quelltext bearbeiten]

Bibliotheken für SVMs

Software für Maschinelles Lernen und Data Mining, die SVMs implementieren

  • KNIME
  • LIONoso implementiert LIBSVM
  • MATLAB implementiert LIBSVM, SVMlight und Spider
  • GNU Octave implementiert SVMlight
  • PCP implementiert LIBSVM
  • RapidMiner implementiert LIBSVM und eine in Java implementierte SVM
  • Shogun implementiert LIBSVM und SVMlight
  • WEKA implementiert LIBSVM und Spider

Programmiersprachen, die SVMs implementieren (Auswahl)

  • Lush, eine Lisp-ähnliche Sprache, implementiert LIBSVM und beinhaltet LASVM (für große Datenmengen), SVQP1 und SVQP2 (für quadratische SVMs)
  • Perl implementiert LIBSVM und SVMlight
  • Python implementiert LIBSVM, SVMlight und scikit-learn
  • R, implementiert LIBSVM (Paket e1071[5]), SVMlight (Paket klaR[6]) und hat das Paket kernlab[7] für Kernel-Lernen mit SVMs
  • Ruby implementiert LIBSVM und SVMlight

Weblinks[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

  • Bernhard Schölkopf, Alex Smola: Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond (Adaptive Computation and Machine Learning), MIT Press, Cambridge, MA, 2002, ISBN 0-262-19475-9.
  • Ingo Steinwart, Andreas Christmann: Support Vector Machines, Springer, New York, 2008. ISBN 978-0-387-77241-7. 602 pp.
  • Nello Cristianini, John Shawe-Taylor: Kernel Methods for Pattern Analysis, Cambridge University Press, Cambridge, 2004, ISBN 0-521-81397-2
  • Christopher J. C. Burges: A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, 2(2):121-167, 1998.
  • Wladimir Wapnik: Statistical Learning Theory, Wiley, Chichester, GB, 1998.
  • Wladimir Wapnik: The Nature of Statistical Learning Theory, Springer Verlag, New York, NY, USA, 1995.

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Schölkopf, Smola: Learning with Kernels, MIT Press, 2001
  2. Fisher, R.A. (1936), "The use of multiple measurements in taxonomic problems", in Annals of Eugenics 7: 179-188
  3. Rosenblatt, F. (1958), "The Perceptron, a Probabilistic Model for Information Storage and Organisation in the Brain", in Psychological Review, 62/386
  4. Vapnik und Chervonenkis, Theory of Pattern Recognition,1974 (dt. Übersetzung: Wapnik und Tschervonenkis, Theorie der Mustererkennung, 1979)
  5. David Meyer et al.: R-Paket e1071. Misc Functions of the Department of Statistics, Probability Theory Group (Formerly: E1071), TU Wien. In: CRAN. The R Foundation, abgerufen am 14. Mai 2016 (englisch, aktuelle Version: 1.6-7).
  6. Uwe Ligges et al.: R-Paket klaR. Classification and visualization. In: CRAN. The R Foundation, abgerufen am 14. Mai 2016 (englisch, aktuelle Version: 0.6-12).
  7. Alexandros Karatzoglou, Alex Smola, Kurt Hornik: R-Paket kernlab. Kernel-Based Machine Learning Lab. In: CRAN. The R Foundation, abgerufen am 14. Mai 2016 (englisch, aktuelle Version: 0.9-24).