Support Vector Machine

Das Prinzip der Klassifikation bzw. Mustererkennung mit Support-Vector-Maschinen (SVM) beruht auf dem Finden einer optimal trennenden Hyperebene in einem hochdimensionalen Merkmalsraum - typischerweise mit wesentlich höherer Dimension als der ursprüngliche Merkmalsraum (letzterer wird auch als Eingaberaum bezeichnet). Die Idee dahinter besteht darin, dass mit einer passenden nichtlinearen Abbildung $\phi (\cdot )$ in eine ausreichend hohe Dimension, Daten aus zwei Kategorien stets mit Hilfe einer Hyperebene getrennt werden können. Dieser hochdimensionale Merkmalsraum hat potentiell unendlich viele Dimensionen. Dennoch ist die Berechnung einer Hyperebene möglich, da die SVM so formuliert werden kann, dass die Trainingsdaten nur in Skalarprodukten auftreten. Dieses Skalarprodukt kann durch eine Funktion $\kappa :{\mathcal {X}}\times {\mathcal {X}}\rightarrow \mathbb {R}$ ersetzt werden. Diese Funktion wird als Kernel bezeichnet und gibt den Wert des Skalarprodukt $\langle \phi (x),\phi (y)\rangle$ an. ${\mathcal {X}}$ bezeichnet hierbei die Menge, aus der die Trainingsdaten entstammen. Diese muss nun nicht mehr $\mathbb {R}$ sein, sondern kann bei geeignetem Kernel aus beliebigen Objekten (z.B. Graphen, Zeichenketten etc.) bestehen.

Die SVM hat nicht zuletzt deswegen eine große Popularität erlangt, da das zugrunde liegende Optimierungsproblem konvex ist und trotz der großen Flexibilität der Abbildung $\phi (\cdot )$ eine Überanpassung (Overfitting) an den Trainingsdatensatz verhindert und damit eine gute Generalisierung auf neue Daten garantiert wird. Dies wird als strukturelle Risiko-Minimierung bezeichnet. Die Lösung einer SVM ist der Normalenvektor auf die Hyperebene im Merkmalsraum. Dieser ist eine Linearkombination von in den Merkmalsraum abgebildeten Trainingsbeispielen, d.h. $\psi =\sum _{i=1}^{n}\alpha _{i}\cdot \phi (x_{i})$, wobei die $\alpha$-Koeffizienten durch das Optimierungsproblem bestimmt werden. Die Eingabebeispiele, für die gilt $\alpha _{i}>0$ heißen Support-Vektoren. Der Klassifikator hat dann die Form: $\langle \psi ,\phi (x)\rangle +b=\sum _{i=1}^{n}\alpha _{i}k(x_{i},x)+b$.

2d-Toybeispiel für eine trainierte SVM mit polynomiellen Kernel. Alle Punkte mit blauem Kreis sind Support-Vektoren.

Es handelt sich um eine überwachte Lernmethode aus dem Bereich Maschinelles Lernen.

Die Methodik geht auf Vladimir Vapnik zurück, der 1974 ein Paper über die Prinzipien der Hyperebenentrennung veröffentlichte (Vapnik, V.; Chervonenkis, A. 1974. Theory of Pattern Recognition [auf russisch]. Nauka, Moscow. (Deutsche Übersetzung: Wapnik, W.; Tscherwonenkis, A. 1979. Theorie der Zeichenerkennung, Akademie-Verlag, Berlin.)

Literatur

• 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 0262194759.
  • http://www.learning-with-kernels.org/ - 3 Kapitel daraus in PDF-Format
• Nello Cristianini, John Shawe-Taylor: Kernel Methods for Pattern Analysis, Cambridge University Press, Cambridge, 2004, ISBN 0521813972
  • http://www.kernel-methods.net

Weblinks

• http://lectures.molgen.mpg.de/statistik/docs/Kapitel_16.pdf
• http://www.kernel-machines.org/
• http://www.kyb.tuebingen.mpg.de/bu/people/bs/svm.html - Schölkopfs Seite über SVMs

Software

• http://www.kyb.tuebingen.mpg.de/bs/people/spider/main.html - Machine Learning Toolbox für Matlab, in der auch die SVM implementiert ist
• YALE ist ein einfach zu bedienenes und frei erhältliches Tool für Maschinelles Lernen und Data Mining, in der auch die SVM implementiert ist