Support-Vector-Machine

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

Eine Support-Vector-Machine (SVM, von engl. support vector machine, „Stützvektormaschine“, die dt. Übersetzung ist nicht gebräuchlich^[1]^[2]) ist ein Klassifikator. Eine Support-Vector-Machine teilt Objekte so in zwei Klassen auf, dass die Klassengrenze möglichst weit von allen Objekten entfernt liegt. Es entsteht ein leerer Rand um die Klassengrenze herum, dessen Breite maximiert wird; man spricht daher auch von einem large-margin-Klassifikationsverfahren (engl. „großer Rand“).

Die zum Verständnis notwendigen Grundbegriffe dieses Artikels werden im Artikel Klassifizierung erläutert.

[Bearbeiten] Grundlegende Funktionsweise

Die Support-Vector-Maschine (SVM) ist ein Lernalgorithmus zur Klassifizierung von Objekten. Die SVM bestimmt anhand einer Menge von Trainingsbeispielen

$\{( \mathbf x_1, y_1),..., ( \mathbf x_m, y_m )\}, \mathbf x_i\in \mathcal X, y_i \in \{-1,1\}$

eine Hyperebene, die beide Klassen so voneinander trennt, dass der kleinste Abstand zur Hyperebene, dem sogenannten Margin, für die Beispiele beider Klassen maximiert wird. Das sogenannte Label $y i$ gibt dabei die Klassenzugehörigkeit für das Trainingsbeispiel $\mathbf x_i$ 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 $\mathbf w$ und einen sogenanntes Bias $\mathbf b$ . Einem Trainingsbeispiel $\mathbf x_i$ wird dabei das Vorzeichen der Entscheidungsfunktion als Label zugeordnet:

$y_i = sgn(\langle \mathbf w, \mathbf x_i \rangle + \mathbf b )$ .

[Bearbeiten] Linear separierbare Daten

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, dann 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 $||\mathbf w||_2^2$ auswählt, so dass gleichzeitig $y_i ( \langle \mathbf w , \mathbf x \rangle + \mathbf b ) \ge 1$ für jedes Trainingsbeispiel $\mathbf x_i$ 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 bezüglich $\mathbf{w,b}$ : $\frac{1}{2} ||w||_2^2$ ,

so dass die Nebenbedingung $y_i ( \langle \mathbf w, \mathbf x \rangle + \mathbf b) \ge 1$ für alle $1\le i\le m$ gilt.

[Bearbeiten] Nicht-linear separierbare Daten

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 $m$ Nebenbedingungen möglich sind, die Verletzungen aber so klein wie möglich gehalten werden sollen. Zu diesem Zweck wird eine positive Schlupfvariable $ξ i$ für jede Nebenbedingung eingeführt, deren Wert gerade die Verletzung der Nebenbedingungen ist. $ξ i > 0$ 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 $C$ multipliziert, die den Ausgleich zwischen der Minimierung von $\frac{1}{2} ||w||_2^2$ und der korrekten Klassifizierung der Trainingsbeispiele regelt. Das Optimierungsproblem besitzt dann folgende Form:

minimiere bezüglich $\mathbf{w,b}$ : $\frac{1}{2} ||w||_2^2 + C \sum_{i=1}^m \xi_i$ ,

so dass die Nebenbedingung $y_i(\langle \mathbf w,x\rangle+b) \ge 1 - \xi_i$ für alle $1\le i\le m$ gilt.

[Bearbeiten] Duales Problem

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.

Abb. 1. Beispiel für eine Klassifizierung mit einer SVM. Zu sehen ist die trennende gekrümmte Hyperebene (schwarze Linie) und die Support-Vektoren (blau 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 $\mathbf w$ als Linearkombination aus Trainingsbeispielen geschrieben werden kann:

$\mathbf w = \sum_{i=1}^m \alpha_i y_i \mathbf x_i$

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

maximiere für $\mathbf \alpha$ : $\sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{j=1}^m \alpha_i \alpha_j y_i y_j \langle \mathbf x_i, \mathbf x_j \rangle$ ,

so dass die Nebenbedingungen $0 \le \alpha_i \le C$ und $\sum_{i=1}^m \alpha_i y_i = 0$ gelten.

Damit ergibt sich als Klassifikationsregel:

$f(x)= sgn (\langle w,x\rangle +b) = sgn\left(\sum_{i=1}^m \alpha_i y_i \langle x_i, x\rangle +b \right)$

Ihren Namen hat die SVM von einer speziellen Untermenge der Trainingspunkte, deren Lagrangevariablen $\alpha_i \neq 0$ . Diese heißen Support-Vektoren und liegen entweder auf dem Margin (falls $y_i(\langle \mathbf w,x\rangle+b) = 1$ ) oder innerhalb des Margin ( $ξ i > 0$ ).

[Bearbeiten] Nichtlineare Erweiterung mit Kernelfunktionen

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.

$\phi: \mathbb{R}^{d_1} \rightarrow \mathbb{R}^{d_2}, x\rightarrow \phi(x)$

Dabei gilt $d 1 < d 2$ . Durch diese Abbildung wird die Anzahl möglicher linearer Trennungen erhöht (Theorem von Cover ^[3]). SVMs zeichnen sich dadurch aus, dass sich diese Erweiterung sehr elegant einbauen lässt. In das dem Algorithmus zu Grunde liegende Optimierungsproblem in der zu letzt dargestellten Formulierung gehen die Datenpunkte $x i$ nur in Skalarprodukten ein. Daher ist es möglich, das Skalarprodukt $\langle x_i,x_j\rangle$ im Eingaberaum $\mathbb{R}^{d_1}$ durch ein Skalarprodukt im $\mathbb{R}^{d_2}$ zu ersetzen und $\langle \phi(x_i),\phi(x_j)\rangle$ stattdessen direkt zu berechnen. Die Kosten dieser Berechnung lassen sich sehr stark reduzieren, wenn eine positiv definite Kernelfunktion stattdessen benutzt wird:

$k(x_i,x_j)=\langle \phi(x_i),\phi(x_j)\rangle$

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

$f(x)= sgn (\langle w,x\rangle +b) = sgn\left(\sum_{i=1}^m \alpha_i y_i k(x_i, x) +b \right)$

mit $w=\sum_{i=1}^m \alpha_i \phi(x_i)$ . 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.

[Bearbeiten] Geschichte

Die Idee der Trennung durch eine Hyperebene wurde erstmals 1958 von Frank Rosenblatt veröffentlicht ^[4]. Die Idee der Support-Vector-Machines geht auf die Arbeit von Vladimir Vapnik und Aleksei Chervonenkis^[5] 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 Klassifizieres bestimmen. In der Mitte der 1990er Jahre gelang den SVMs der Durchbruch und zahlreiche Weiterentwicklungen und Modifikationen wurden in den letzten Jahren veröffentlicht.

[Bearbeiten] 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.
Nello Cristianini, John Shawe-Taylor: Kernel Methods for Pattern Analysis, Cambridge University Press, Cambridge, 2004, ISBN 0521813972
Christopher J. C. Burges: A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, 2(2):121-167, 1998.
Vladimir Vapnik: Statistical Learning Theory, Wiley, Chichester, GB, 1998.
Vladimir Vapnik: The Nature of Statistical Learning Theory, Springer Verlag, New York, NY, USA, 1995.

[Bearbeiten] Weblinks

http://www.learning-with-kernels.org/ (3 Kapitel aus Learning with Kernels)
http://research.microsoft.com/copyright/accept.asp?path=http://research.microsoft.com/~cburges/papers/SVMTutorial.pdf&pub=1 (Chris Burges Tutorial)
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 (B. Schölkopfs Seite über SVMs)
http://diwww.epfl.ch/mantra/tutorial/english/svm/html/index.html

[Bearbeiten] Software

libSVM - Häufig benutzte SVM Implementierung mit vielen Extras
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
SVMlight Implementation einer SVM in C (Bindings für Perl und Java verfügbar)
Torch Machine Learning Bibliothek in C++

[Bearbeiten] Quellen

↑ LEO - dictForum - Diskussion über die Übersetzung von support vector machine.
↑ S. Bickel, U. Brefeld, M. Brückner. Text Mining und Anwendungen: Einführung. Präsentation am Institut für Informatik der Humboldt Universität Berlin, 2005.
↑ Schölkopf, Smola: Learning with Kernels, MIT Press, 2001
↑ Rosenblatt, F. (1958), "The Perceptron, a Probabilistic Model for Information Storage and Organisation in the Brain", in Psychological Review, 62/386
↑ Vapnik und Chervonenkis, Theory of Pattern Recognition,1979

Von „http://de.wikipedia.org../../../s/u/p/Support-Vector-Machine_70ee.html“

Kategorien: Klassifikation | Maschinelles Lernen | Statistik