%\documentclass[ngerman]{book}
%\usepackage[ngerman]{babel}
%\usepackage[latin1]{inputenc}
%\usepackage{amssymb}
%\usepackage{graphicx}
%\usepackage{amsmath}
%\def\RR{\mathbb{R}} %reelle Zahlen
%\begin{document}

Eine Support Vector Machine löst ein binäres Klassifierungsproblem. Sie lernt auf einer bereits klassifizierten Menge von Trainigsbeispielen und entscheidet dann für Test-Elemente, zu welcher der zwei Klasse sie gehören. Das eigentliche Lernen besteht darin, eine Hyperebene $H$ zu berechnen, die die Beispiele beider Klassen trennt. Danach kann anhand der Lage der Test-Elemente zur Hyperebene eine Klassifizierung erfolgen. Zunächst gilt es aber unter den vielen möglichen trennden Ebenen die optimale zu finden. Optimal wird dabei so verstanden, dass der Abstand von der Ebene zum nahesten Beispiel beider Klassen maximiert wird. Es liegt also ein Optimierungsproblem vor, welches nachfolgend formalisiert werden soll.
\begin{figure}[ht]
	\centering
		\includegraphics[width=1.00\textwidth]{bilder_martin/trennendeEbene.png}		
	\caption{trennende Hyperebene}
	\label{fig:trennendeHyperebene}
\end{figure}
\\
Es sei o.B.d.A. angenommen, dass die Beispiele in positive und negative unterteilt seien. Vorerst wird vorrausgestzt, dass die Trainingsdaten linear trennbar sind, es also eine trennende Hyperebene gibt. Der Fall linear nicht trennbarer Daten wird nach aufbauend auf diesen Erkenntnissen betrachtet.

$(x_i, y_i)$ $(i = 1, ..., m)$ seien $m$ Trainingsbeispiele, bestehend aus einem Punkt $x_i\in\ RR^d$ und der Klassifizierung\footnote{Man verwendet als Klassifizierung die -1 und 1 statt z.B. 0 und 1, weil sich damit, wie wir sehen werden, besser rechnen lässt.} $y_i\in\{-1, 1\}$. $w\in\ RR ^d$ sei der zu bestimmende Normalenvektor der Hyperebene (siehe Abbildung \ref{fig:hyperebene}), $b\in\ RR$ ihr Bias. Als Ebenengleichung wird die Variante mit dem Skalarprodukt gewählt, so dass alle Punkte $x$ der Ebene die Gleichung $w \cdot x + b = 0$ erfüllen.
\begin{figure}[h]
	\centering
		\includegraphics{bilder_martin/hyperebene.png}
	\caption{Hyperebene}
	\label{fig:hyperebene}
\end{figure}
Per Definition sollen die nahesten positiven Beispiele auf der Ebene $H_1$: $w \cdot x_i + b = 1$ und die nahesten negativen Beispiele auf der Ebene $H_2$: $w \cdot x_i + b = -1$ liegen (siehe Abbildung \ref{fig:breiteHyperebene}). Dies kann durch eine entsprechende Skalierung von $w$ und $b$ sichergestellt werden.
\begin{figure}[h]
	\centering
		\includegraphics{bilder_martin/breiteHyperebene.png}
	\caption{Breite der Hyperebene}
	\label{fig:breiteHyperebene}
\end{figure}
Aus diesen Definitionen lassen sich direkt zwei Nebenbedingungen des Optimierungsproblems formulieren:
\begin{equation}
  \label{eq:opt1nb1}
	w \cdot x_i + b \geq 1, \hspace{1cm} \forall i: y_i = 1
\end{equation}
\begin{equation}
  \label{eq:opt1nb2}
	w \cdot x_i + b \leq -1, \hspace{1cm} \forall i: y_i = -1
\end{equation}
Die lässt sich zusammenfassen zu:
\begin{equation}
  \label{eq:opt1nb3}
	y_i (w \cdot x_i + b) - 1 = 0, \hspace{1cm} \forall i
\end{equation}
Ziel des Optimierungproblems ist die erwähnte Maximierung des Abstandes zu den nahesten Beispielen. Man spricht hier auch von der Breite (\textit{margin}) der Ebene $H$, die bildlich den Abstand der Ebenen $H_1$ und $H_2$ aus Abbildung \ref{fig:breiteHyperebene} repräsentiert.
Dieser Abstand beträgt $\frac{2}{\left\|w\right\|}$, wobei $\left\|w\right\|$ die euklidische Länge von $w$ darstellt. Zur Maximierung der Breite muss also $\left\|w\right\|$ minimiert werden. Eine SVM lässt sich dann durch folgendes Optimierungsproblem beschreiben:
\begin{eqnarray*}
	\left\|w\right\|^2 \longrightarrow Min! \\
	y_i (w \cdot x_i + b) - 1 = 0, \hspace{1cm} \forall i
\end{eqnarray*}
Nun wird ersichtlich, warum die SVM \textit{Stützvektor}-Maschine heißt: Die Hyperebene $H$ wird durch Maximierung der Breite bestimmt. Die Breite hängt nur von den zur Ebene am nächsten gelegenen Beispielen ab, die ja die Ebenen $H_1$ und $H_2$ bestimmen. Die Bespiele, die auf einer dieser Ebenen liegen, stützen die Ebene $H$, da sich ohne sie die Lage (die Breite) von $H$ verändern würde, und werden daher Stützvektoren genannt.

Um den Fall nicht nicht linear separierbarer Daten besser handhaben zu können, ist eine Transformation des Problems in die duale Lagrange-Form nötig. Dazu werden die üblichen Lagrange-Multiplikatoren $\alpha_i \geq 0$ eingeführt und die Nebenbedingung in die Zielfunktion aufgenommen. Man erhält zunächst die Zielfunktion:
\begin{equation}
  \label{eq:op1ZfLagrange}
	L(w, b, \alpha) = \frac{1}{2}\left\|w\right\|^2
	                  - \sum^{m}_{i=1} \alpha_i y_i (w \cdot x_i + b)
	                  + \sum^{m}_{i=1} \alpha_i
\end{equation}
Jedes Optimum der Zielfunktion muss auch ein Minimum der Funktion sein. Dies ist die eine notwendige Bedinung für die Eigenschaft als Optimum. Die Karush-Kuhn-Tucker (KKT) Bedingungen setzten Tatsache in Gleicheungen um. Damit ein Minimum vorliegt, müssen die ersten partiellen Ableitungen in Richtung der Entscheidungsvariablen $w$ und $b$ null sein. Die KKT Bedingungen für das Optimierungsproblem der SVM mit der Lagrange-Zielfunktion (\ref{eq:op1ZfLagrange}) lauten:
\begin{eqnarray*}
	\frac{\partial}{\partial w}L(w,b,\alpha) = w - \sum^{m}_{i=1} \alpha_i y_i x_i = 0 \\
	\frac{\partial}{\partial b}L(w,b,\alpha) = - \sum^{m}_{i=1} \alpha_i y_i = 0 \\
	y_i (w \cdot x_i + b) - 1 = 0, \hspace{1cm} \forall i \\
	\alpha_i \geq 0, \hspace{1cm} \forall i \\
	\alpha_i (y_i (w \cdot x_i + b) - 1) = 0, \hspace{1cm} \forall i \\
\end{eqnarray*}
Durch Umstellen der ersten beiden Bedingungen erhält man:
\begin{equation}
  \label{eq:op1eq1}
	w = \sum^{m}_{i=1} \alpha_i y_i x_i
\end{equation}
\begin{equation}
  \label{eq:op1eq2}
	\sum^{m}_{i=1} \alpha_i y_i = 0
\end{equation}
Einsetzen von (\ref{eq:op1eq1}) und (\ref{eq:op1eq2}) in (\ref{eq:op1ZfLagrange}) liefert die Zielfunktion $L_D$ des dualen Optimierungsproblems:
\begin{equation}
  \label{eq:op2ZfLagrange}
	L_D(\alpha) = \sum^{m}_{i=1} \alpha_i
	              - \frac{1}{2} \sum^{m}_{i=1} \sum^{m}_{j=1} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j)
\end{equation}
Die Zielfunktion hängt damit nur noch von $\alpha$ ab und verwendet als einzige nicht elementare Rechenoperation das Skalarprodukt. Nun erhalten wir das (einfachere) duale Optimierungsproblem für eine SVM auf Basis linear trennbarer Trainingsdaten:
\begin{eqnarray*}
	\sum^{m}_{i=1} \alpha_i
	              - \frac{1}{2} \sum^{m}_{i=1} \sum^{m}_{j=1} \alpha_i
	              \alpha_j y_i y_j (x_i \cdot x_j) \longrightarrow Max! \\
	\sum^{m}_{i=1} \alpha_i y_i = 0, \hspace{1cm} \forall i \\
	\alpha_i \geq 0, \hspace{1cm} \forall i
\end{eqnarray*}
Nach Lösung des Problems sind alle $\alpha_i$ bestimmt und der Normalenvektor $w$ kann mit (\ref{eq:op1eq1}) berechnet werden. Den Bias erhält man, in dem man einen beliebigen Stützvektor ein die Ebenengleichung von $H$ einsetzt und nach $b$ umformt.
Normalenvektor, Bias und damit die Hyperebene sind also durch Linearkombinationen aus gerade den Beispielen $x_i$, für die $\alpha_i > 0$ ist, bestimmt. Diese Beispiele sind, wie wir schon gesehen haben, die Stützvektoren. Also gilt:
\begin{itemize}
	\item $\alpha_i > 0$: \hspace{0.5cm} $x_i$ ist Stützvektor
	\item $\alpha_i = 0$: \hspace{0.5cm} $x_i$ ist kein Stützvektor
\end{itemize}

Nun können die Elemente der Test-Menge klassifiziert werden. Dazu genügt die Auswertung der Funktion
\begin{equation}
	\label{eq:testFkt}
	f(x) = w \cdot x + b
\end{equation}
für ein Testelement $x$. Das Vorzeichen von $f(x)$ gibt dabei die Klassifizierung an, da nur folgende Fälle zu unterscheiden sind:
\begin{itemize}
	\item $f(x) > 0$: \hspace{0.5cm} x leigt im positiven Halbraum
	\item $f(x) < 0$: \hspace{0.5cm} x leigt im negativen Halbraum
	\item $f(x) = 0$: \hspace{0.5cm} x leigt auf $H$
\end{itemize}

\begin{figure}[ht]
	\centering
		\includegraphics{bilder_martin/nicht_linear_trennbar.png}
	\caption{Nicht linear trennbare Trainingsdaten}
	\label{fig:nicht_linear_trennbar}
\end{figure}
Betrachten wir jetzt den Fall nicht linear trennbarer Daten, den Abbildung \ref{fig:nicht_linear_trennbar} schematisch zeigt. Was kann man tun, um dieses Problem zu lösen?
\begin{itemize}
	\item Fehler zulassen \\
	Dies kann mit der Einführung einer \textit{weich trennenden} Ebene gelöst werden, die 
	fehlerhafte Klassifizierungen von Trainingsbeispielen bis zu einem gewissen Grad zulässt.
	\item Das Problem und die Daten so transformieren, dass sie linear trennbar werden.
\end{itemize}

Die eine SVM mit weich trennender Hyperebene erweitert die bekannte SVM um die 'Fehlerkosten' $\xi_i \geq 0$ für jedes Beispiel. Die Nebenbedingungen \ref{eq:opt1nb1} und \ref{eq:opt1nb2} ändern sich dann zu:
\begin{equation}
  \label{eq:opt3nb1}
	w \cdot x_i + b \geq 1 - \xi_i, \hspace{1cm} \forall i: y_i = 1
\end{equation}
\begin{equation}
  \label{eq:opt3nb2}
	w \cdot x_i + b \leq -1 +  \xi_i, \hspace{1cm} \forall i: y_i = -1
\end{equation}
Die lässt sich wieder zusammenfassen zu:
\begin{equation}
  \label{eq:opt3nb3}
	y_i (w \cdot x_i + b) - 1 +  \xi_i = 0, \hspace{1cm} \forall i
\end{equation}
Zu der ursprünglichen Zielfunktion werden die 'Fehlerkosten' einfach hinzu addiert. Weiterhin wird noch eine vom Benutzer zu wählende Konstante $C$ eingeführt, die die Auswirkung der Fehlklassifikationen beeinflusst. Eine weich trenndende SVM wird dann durch folgendes Problem repräsentiert:
\begin{eqnarray*}
	\left\|w\right\|^2 + C \sum^{m}_{i=1} \xi_i \longrightarrow Min! \\
	y_i (w \cdot x_i + b) - 1 = 0, \hspace{1cm} \forall i \\
	0 \leq \alpha_i \leq C, \hspace{1cm} \forall i
\end{eqnarray*}
Die Zielfunktion des dualen Problem ist wieder (\ref{eq:op1ZfLagrange}), da die $\xi_i$ beim bilden des dualen Problems verschwinden. Das bekannte duale Problem für linear trennbare Daten wird für die weich trennende SVM also nur um die Nebenbedingungen $0 \leq \alpha_i \leq C$ erweitert. Abbildung \ref{fig:weich_trennende_ebene} verdeutlicht noch einmal die Bedeutung der $\alpha_i$ und $\xi_i$.
\begin{figure}[ht]
	\centering
		\includegraphics[width=1.00\textwidth]{bilder_martin/weich_trennende_ebene.png}
	\caption{Beispiele für $\alpha$-$\xi$ Kombinationen}
	\label{fig:weich_trennende_ebene}
\end{figure}

Die Transformation der linear nicht trennbaren Daten in linear trennbare gelingt ohne große Mühen, da in den entwickleten Formeln das Skalarprodukt die einzige nicht elementare Rechenoperation ist. Die Idee ist, die Beispiele durch eine Abbildung $\Phi: \ RR^m \longrightarrow \ RR^h$ mit $h > m$ in einen höherdimensionalen Raum zu transformieren, wo sie dann linear trennbar sind. Die Zielfunktion (\ref{eq:op2ZfLagrange}) wird dann einfach angepasst:
\begin{equation}
	L_D(\alpha) = \sum^{m}_{i=1} \alpha_i
	              - \frac{1}{2} \sum^{m}_{i=1} \sum^{m}_{j=1} \alpha_i
	              \alpha_j y_i y_j (\Phi(x_i) \cdot \Phi(x_j))
	\label{eq:opt4zf1}
\end{equation}
Sei $K(x, y) = \Phi(x) \cdot \Phi(y)$ eine Kernfunktion, die die das Skalarprodukt zweier transformierter Trainingsdaten direkt berechne. Eine solche Funktion muss die Abbildung $\Phi$ garnicht kennen. Abbildung \ref{fig:kern_trick} verdeutlicht diesen Gedanken, den man auch den Kern-Trick nennt.
\begin{figure}[ht]
	\centering
		\includegraphics[width=1.00\textwidth]{bilder_martin/kern_trick.png}
	\caption{Der Kern-Trick}
	\label{fig:kern_trick}
\end{figure}
\\
Ein Beispiel: \\
Seien $x,y \in \ RR^2$ und $K(x, y) = (x \cdot y)^2$ eine Kernfunktion. Um zu zeigen, dass $K$ das Skalarprodukt direkt berechnet, muss eine Abbildung $\Phi$ mit $\Phi(x) \cdot \Phi(y) = (x + y)^2$ gefunden werden. Wir nehmen an, dass die Funktion
\begin{equation}
	\Phi(x) = \begin{pmatrix} [x]^{2}_{1} \\ \sqrt{2} [x]_1 [x]_2 \\ [x]^2_2 \end{pmatrix}
	\label{eq:bspPhi}	
\end{equation}
dieses tut. $[x]_i$ bezeichnet dabei die i-te Komponente von $x$. Beweis:
\begin{eqnarray*}
	\Phi(x) \cdot \Phi(y) &=&
	\begin{pmatrix} [x]^{2}_{1} \\ \sqrt{2} [x]_1 [x]_2 \\ [x]^2_2 \end{pmatrix}
	\cdot \begin{pmatrix} [y]^{2}_{1} \\ \sqrt{2} [y]_1 [y]_2 \\ [y]^2_2 \end{pmatrix} \\
	&=& [x]^{2}_{1} [y]^{2}_{1} + 2 [x]_1 [x]_2 [y]_1 [y]_2 + [x]^2_2 [y]^2_2 \\
	&=& ([x]_{1} [y]_{1})^2 + 2 [x]_1 [y]_1 [x]_2 [y]_2 + ([x]_2 [y]_2)^2 \\
	&=& ([x]_1 [y]_1 + [x]_2 [y]_2)^2 \\
	&=& (x \cdot y)^2
\end{eqnarray*}
Wir sehen also, dass $K$ das Skalarprodukt von $x$ und $y$ direkt berechnet, ohne dabei erst in den höherdimensionalen Raum abzubilden.

Setzt man die Kernfunktion in in die Zielfunktion (\ref{eq:opt4zf1}) ein, erhält man zusammen mit den bekannten Nebenbedingungen das Optimierungsproblem für eine SVM mit nicht linear trennbaren Daten:
\begin{eqnarray*}
	\sum^{m}_{i=1} \alpha_i
	              - \frac{1}{2} \sum^{m}_{i=1} \sum^{m}_{j=1} \alpha_i
	              \alpha_j y_i y_j K(x_i, x_j) \longrightarrow Max! \\
	\sum^{m}_{i=1} \alpha_i y_i = 0, \hspace{1cm} \forall i \\
	0 \leq \alpha_i \leq C, \hspace{1cm} \forall i
\end{eqnarray*}
Mit der \textit{Mercer's Condition} lässt sich überprüfen, ob eine Funktion $K(x, y)$ eine Kernfunktion ist: \\
Es gibt Abbildungen $K$ und $\Phi$ mit $K(x, y) = \Phi(x) \cdot \Phi(y) = \sum^{}_{i} [\Phi(x)]_i [\Phi(y)]_i \Leftrightarrow \text{ für jedes } g(x) \text{ mit finitem} \int{g(x)^2}dx \text{ gilt }$
\begin{equation*}
	\int{K(x, y)g(x)g(y)}dxdy \geq 0
\end{equation*}

Die Lösung des Optimierungsproblems gestaltet sich als schwerig. Zwar liegt ein quadratisches, konvexes Optimierungsproblem vor, welches in $O(m^3)$ gelöst werden kann, jedoch ist dies in praktischen Anwendungen für eine sehr große Menge an Trainingsdaten langwierig. Erschwerend kommt hinzu, dass die Ungleichungen für große $m$ nur mit numerischen Methoden gelöst werden können. Ein numerischer Solver muss als Unterprogramm aufgerufen werden.
Im Folgenden werden zwei Lösungsalgorithmen vorgestellt, die das Optimierungsproblem heuristisch lösen. \\
Ein Verfahren ist das \textit{Chunking}, bei dem der zentrale Gedanke darin liegt, Trainingsbeispiele, die keine Stützvektoren sind, aus der Berechnung auszuschließen, da sie, wir wir gesehen haben, die Lage der Hyperebene nicht beeinflussen. Eine Iteration läuft wie folgt ab:
\begin{enumerate}
	\item Löse das Problem auf Basis einer Teilmenge der Trainingsdaten
	\item Betrachte die berechnten $\alpha_i$-Werte: \\
	Ist $\alpha_i = 0$ ist $x_i$ kein Stütuvektor und wird von der weiteren Berechnung ausgeschlossen.
	\item Nimm $M$ Trainiungsbeispiele in die Berechnungsmenge auf, die die KTT-Bedingungen am schlechtesten erfüllen.
\end{enumerate}
Über die Iterationen wird also versucht, die Stützvektoren zu identifizieren. In der letzten Iteration sind dann nur noch Stützvektoren in der Berechnungsmenge, so dass dann das gesamte Probmlem gelöst wird. Damit reduziert Chunking den Aufwand auf die quadrierte Anzahl der Stützvektoren. Dies kann erhebliche Vorteile bringen, aber auch genauso schlecht wie die Lösung ohne die Heuristik sein, wenn nahezu alle Trainingsdaten Stützvektoren sind. Definitv nachteilig ist aber, dass Chunking weiterhin nicht ohne Numerik-Solver auskommt. Genau diesem Nachteil nimmt sich das zweite Verfahren an: Die \textit{Sequential Minimal Optimization} (\cite{Platt/99a}), kurz \textit{SMO}.

Während das Chunking immer mehrere $\alpha_i$ optimiert, beschränkt sich die SMO auf die Optimierung von genau zwei $\alpha_i$ in jeder Iteration. Der Vorteil ist, dass sich dies analytisch lösen lässt. Somit kann auf das Unterprogramm zur numerischen Lösung einer Gleichung verzichtet werden. Insgesamt sind natürlich weit mehr Optimierungen nötig als beim Chunking, da ja alle $\alpha_i$ paarweise optimiert werden müssen. Trotzdem ist die Laufzeit besser als die des Chunking, da die Numerik-Solver Aufrufe schwerer wiegen als das Mehr an Optimierungsiterationen (die alle in $O(1)$ gelöst werden können). \\
Der SMO-Algorithmus verwendet eine äußere und eine innere Schleife zur Auswahl der $\alpha_i$-Paare. In der äußeren Schleife werden zunächst alle Beispiele durchlaufen und alle nicht gebundenen (non bound, d.h. $\alpha_i$ ist weder $0$ noch $C$) Beispiele gesucht, die die KKT-Bedingungen verletzten. Das dazugehörige Alpha sei jeweils $\alpha_I$, welches für die innere Schleife fest ist. Die innere Schleife findet nun unter den übrigen Beispielen ein $\alpha_{II}$ als Optimierungspartner. Als Auswahlkriterium wird der momentane Fehler
\begin{equation}
	E_i = f(x_i) - y_i
	\label{eq:smo_error}
\end{equation}
genutzt. $E_I$ sei der Fehler des Beispiels aus der äußeren Schleife. Die Fehler der übrigen Beispiele werden berechnet und das Beispiel, welches $\alpha_{II}$ liefert, wie folgt gewählt:
\begin{itemize}
	\item $E_I > 0$: Wähle Beispiel mit kleinstem $E_i$
	\item $E_I < 0$: Wähle Beispiel mit größtem $E_i$
\end{itemize}
Für die genaue Vorgehensweise zur Optimierung des Paares $(\alpha_I, \alpha_{II})$ sei auf \cite{Platt/99a} verwiesen. Nach der Optimierung wird die Ebene neu berechnet. Damit ändern sich auch die Ergebnisse von $f(x_i)$ bei der Fehlerberechnung aus (\ref{eq:smo_error}).
Die äußere Schleife läuft, bis kein Beispiel mehr die KKT-Bedingungen verletzt. Danach werden noch einmal alle Beispiele durchlaufen und paarweise optimiert.
Die Suche in der äußeren Schleife beginnt immer an einer Zufallsposition, damit sich die SVM nicht den ersten Trainingsdaten annähert.

%\end{document}