2.3.3 Support Vector Machines (SVM)

Diese noch relativ junge Methode wurde 1995 von Vapnik eingeführt [Vap95] und von Joachims für die automatische Klassifikation mit Trainingsdaten erstmals verwendet [Joa98].

Gesucht wird hierbei die Hyperebene (auch Entscheidungsgrenze (decision boundary) [DC00] oder Entscheidungsfläche (decision surface) [YL99] genannt) $\vec{w}\;\vec{x}-b=0$, die diejenigen Trainingsdokumente, die in eine Klasse c eingeordnet sind, von den Trainingsdokumenten, die nicht in dieser Klasse enthalten sind, optimal trennt. Optimal bedeutet hierbei, daß der euklidische Abstand aller Trainingsvektoren zu der Hyperebene maximiert werden soll. $\vec{x}$ ist der Feature-Vektor des zu klassifizierenden Dokuments, der Vektor $\vec{w}$ und die Konstante b werden über das Training der Beispieldokumente bestimmt.

Für eine Menge von bereits klassifizierten Trainingsdokumenten $(\vec{x_i},y_i)$ mit

$$\begin{array}{lll} y_i=+1 & falls & x_i \in c\\ y_i=-1 & falls & x_i \in \overline{c}\\ \end{array}$$

kann das Problem der Abstandsmaximierung als Optimierungsproblem wie folgt ausgedrückt werden:

Minimiere $\frac{1}{2}\vert\vec{w}\vert^2$

unter Nebenbedingung, daß

$$\begin{array}{llll} \vec{w}\;\vec{x_i}-b & \geq +1 & f\uml {... ...w}\;\vec{x_i}-b & \leq -1 & f\uml {u}r & y_1=-1\\ \end{array}$$

Die Vektoren, die genau den Abstand $\frac{1}{\vert\vec{w}\vert}$ von der Hyperebene haben, werden Stützvektoren genannt. Die trennende Hyperebene wird ausschließlich von diesen Vektoren bestimmt, so daß die gleiche Hyperebene bestimmt wird, wenn alle anderen Trainingsdaten entfernt würden.

Die Abbildungen 2 und 3 illustrieren die Maximierung des Abstandes für ein Beispiel im 2-dimensionalen Raum, in dem die Hyperebene eine Linie ist.

Abbildung 2: SVM: Nicht maximierter Abstand

Die durchgezogenen Linien in den Abbildungen sind mögliche trennende Linien zwischen den Dokumenten der Mengen c und $\overline{c}$, die gestrichelten Linien geben den ,,Rand`` der jeweiligen Dokumentenmenge wieder, dessen Abstand zur Trennlinie genau $\frac{1}{\vert\vec{w}\vert}$ beträgt. Die auf dieser Randlinie (bzw. Rand-Hyperebene im mehrdimensionalen Fall) liegenden Vektoren sind also die Stützvektoren.

Abbildung 3: SVM: maximierter Abstand

Natürlich sind die Mengen von positiven und negativen Beispielen für eine Klasse nicht immer linear zu separieren, wie es im gezeigten Beispiel der Fall ist. Hierfür muß ,,erlaubt`` werden, daß sich Trainings-Dokumente auf der falschen Seite der Entscheidungsgrenze befinden. Dafür werden ,,Schlupfvariablen`` in den entsprechenden Nebenbedingungen eingeführt, die dies jedoch gleichzeitig ,,bestrafen`` (vgl. [DC00]).