\newtheorem{bsp}{Beispiel}
Dieser Abschnitt basiert auf dem Artikel, welcher unter \cite{Tsochantaridis/etal/2005a} zu finden ist.

\paragraph{Einleitung}
SVMstruct soll auch komplexe Ausgaben miteinbeziehen können. Es soll eine Zuordnung von einer Eingabe $x \in \mathcal{X}$ zu einer diskreten Ausgabe $y \in \mathcal{Y}$ gefunden werden, welche auf einer Trainingsmenge von Eingabe-Ausgabe Paaren $(x_1, y_1)$,...,$(x_n, y_n)$ $\in \mathcal{X} \times \mathcal{Y}$ basiert. $\mathcal{Y}$ ist dabei ein strukturierter Ausgaberaum. $y \in \mathcal{Y}$ können z.B. Sequenzen, Strings, Bäume, Gitter und Graphen sein. Derartige Probleme gibt es bei einer Vielzahl von Anwendungen. Durch eine Verallgemeinerung der Large Margin Methode (Standard Multi\-class-SVM) sollen nun strukturierte Antworten gefunden werden.

\paragraph{Diskriminanten und Verlustfunktionen}
Das Funktionenlernen $f: \mathcal{X} \rightarrow \mathcal{Y}$, basiert auf einer Trainingsmenge von Eingabe-Ausgabe Paaren. Es soll eine Diskriminanzfunktion $F: \mathcal{X} \times \mathcal{Y} \rightarrow \Re$, über die Eingabe/Ausgabe Paare gelernt werden, von der Vorhersagen abgeleitet werden können, indem F über die Rückgabevariable für die Eingabe x maximiert wird. Formal ist dies wie folgt zu notieren: f(x;w)= $\arg\max_{y \in \mathcal{Y}}$ F(x,y;w), mit w als ein Parameter-Vektor. F soll linear in seiner kombinierten Merkmalsrepräsentation von Ein- und Ausgaben $\Psi(x,y)$ sein, also soll gelten F(x,y;w) = $\langle w, \Psi(x,y) \rangle$. Die spezifische Form von $\Psi$ hängt allerdings von der Art des Problems ab.
		\begin{bsp}[natürlichsprachliche Syntaxanalyse]
				F soll so gewählt werden, dass ein Modell entsteht, dass einer kontextfreien Grammatik entspricht. Jeder Knoten, im Syntaxbaum y für einen Satz 				x, entspricht einer Grammatikregel $g_j$ mit den Kosten $w_j$. Alle gültigen Syntaxbäume y für den Satz x bekommen eine Punktzahl zugewiesen, 					die sich aus der Summe der $w_j$ seiner Knoten berechnen lässt, also F(x,y;w) = $\langle w, \Psi(x,y) \rangle$. $\Psi(x,y)$ ist ein 										Histogrammvektor, der die Vorkommen jeder Grammatikregel $g_j$ im Baum y zählt. f(x;w) kann effizient berechnet werden, indem die Struktur $y 					\in \mathcal{Y}$ gefunden wird, die F(x,y;w) maximiert.
		\end{bsp}
Das Lernen über strukturiereten Ausgaberäumen $\mathcal{Y}$, bezieht andere Verlustfunktionen mit ein als die Standard 0/1 - Klassifikationsverluste.
\begin{bsp}[natürlichsprachliche Syntaxanalyse]
		So ist es sinnvoll einen Syntaxbaum, der sich vom korrekten Syntaxbaum in nur wenigen Knoten unterscheidet, anders zu behandeln, als einen 							Syntaxbaum der sich von diesem vollkommen unterscheidet.
\end{bsp}
Deshalb wird auch davon ausgegangen, dass eine beschränkte Verlustfunktion $\Delta: \mathcal{Y} \times \mathcal{Y} \rightarrow \Re$ vorhanden ist. Dies bedeutet, wenn y der wahre Ausgabewert ist, misst $\Delta(y,\hat y$) den Verlust der mit der Vorhersage $\hat y$ verbunden ist.

\paragraph{Von der SVM zur SVMstruct}
Zunächst wird der separierbare Fall betrachtet, dass der Trainingsfehler gleich null ist. Angenommen, dass $\Delta(y,y') > 0$ ist, wenn $y \neq y'$, und dass $\Delta (y,y)=0$ ist. Die Bedingung, dass der Trainingsfehler null ist, soll nun kompakt dargestellt werden, als die Menge der nicht linearen Bedingungen $\forall i: \max_{y \in \mathcal{Y} \setminus y_i}$ $\{ \langle w, \Psi(x_i,y) \rangle \} < \langle w, \Psi(x_i,y_i) \rangle$. Jede dieser nicht linearen Ungleichheiten, kann durch	$\left| \mathcal{Y} \right| - 1$ lineare Ungleichheiten ersetzt werden. Insgesamt gibt es also $n\left| \mathcal{Y} \right| - n$ lineare Bedingungen der Form	$\forall i, \forall y \in \mathcal{Y} \setminus y_i$: $ \langle w, \delta\Psi_i(y) \rangle > 0$, mit $\delta\Psi_i(y) \equiv \Psi(x_i,y_i) - \Psi(x_i,y)$. Wenn die Menge dieser Ungleichheiten zulässig ist, dann gibt es typischerweise mehr als eine Lösung $w^*$. Um eine einzige Lösung zu erhalten, muss das w gewählt werden, für das sich die Punktzahl des korrekten Labels $y_i$ konstant am meisten von dem nahesten zweitplatzierten unterscheidet, also $\hat y_i(w) = \arg\max_{y \neq y_i} \langle w, \Psi(x_i,y) \rangle$. Dies ist die Generalisierung des Maximum-Margin-Prinzips welches in der SVM angewandt wird. Das resultierende Hard-Margin-Optimierungsproblem, ist die SVM für linear trennbare Daten. $SVM^{linear}: \min_{w} \frac{1}{2} \| w \|^2$ , mit den Nebenbedingungen $\forall i, \forall y \in \mathcal{Y} \setminus	y_i: \langle w, \delta\Psi_i(y) \rangle \geq 1$. Um nun aber einen Fehler in der Trainingsmenge zu erlauben, wird eine Schlupfvariable eingeführt und zwar für jede nicht lineare Bededingung eine Schlupfvariable. Diese ist die obere Grenze des Trainingsfehlers. Das Einfügen einer Strafbedingung zu den Zielergebnissen die linear in den Schlupfvariablen ist, führt nun zur SVM für nicht lineare Daten. $SVM^{nonlinear}: \min_{w, \xi} \frac{1}{2} \| w \|^2 + \frac{C}{n} \sum_{i=1}^n \xi_i$, so dass $\forall i, \xi_i \geq 0$, mit den Nebenbedingungen $\forall i, \forall y \in \mathcal{Y} \setminus y_i: \langle w, \delta\Psi_i(y) \rangle \geq 1 - \xi_i$. 

Bisher gibt es aber noch keine neuen Erkenntnisse, welche es nicht schon im Kapitel \ref{svm} über SVM gab. Diese Formulierung soll jetzt aber für beliebige Verlustfunktionen $\Delta$ generalisiert werden. Dafür muss zunächst den Maßstab der Schlupfvariablen geändert werden und zwar gemäß des Verlustes der in jeder linearen Bedingung angefallen ist. Das Verletzen einer Margin-Bedingung die einen Ausgabewert mit hohem Verlust $\Delta(y_i,y)$ zur Folge hat, soll strenger bestraft werden, als ein Verstoß aus dem ein kleiner Verlust folgt. Dies wird erreicht, indem die Schlupfvariablen mit dem inversen Verlust skaliert werden. Dies führt nun endlich zur SVMstruct, $SVM^{struct}: \min_{w, \xi} \frac{1}{2} \| w \|^2 + \frac{C}{n} \sum_{i=1}^n \xi_i$, so dass $\forall i, \xi_i \geq 0$, mit den Nebenbedingungen $\forall i, \forall y \in \mathcal{Y} \setminus y_i: \langle w, \delta\Psi_i(y) \rangle \geq 1 - \frac{\xi_i}{\Delta(y_i,y)}$.

\paragraph{SVMstruct Algorithmus}
Die Hauptaufgabe beim Lösen dieser verallgemeinerten SVM - Formulierung, liegt in der großen Anzahl der Margin-Bedingungen, denn die Gesamtanzahl der Bedingungen beträgt $n \left| \mathcal{Y} \right|$. Wobei $\left| \mathcal{Y} \right|$ in vielen Fällen extrem groß ist (z.B. beim Grammatik-Lernen). Daher sind Stan\-dard\-lö\-sun\-gen eher ungeeignet. Der SVMstruct-Algorithmus soll nun die Struktur des Maxi\-mum-\-Mar\-gin-Problems ausnutzen, also nur noch eine kleine Teilmenge von Bedingungen detailiert betrachten. Er soll eine kleine Menge von aktivierten Bedingungen finden, die eine ausreichend fehlerfreie Lösung garantieren. Dies ergibt eine gute und gültige Lösung, da es immer eine polynomiell große Teilmenge von Bedingungen gibt, so dass die zugehörige Lösung alle Bedingungen mit einer Genauigkeit von mindestens $\epsilon$ erfüllt. Alle anderen Bedingungen werden garantiert durch nicht mehr als $\epsilon$ verletzt, ohne dass sie dafür genauer betrachtet werden müssen. Der folgende Algorithmus kann auf alle $SVM^{struct}$-Formulierungen angewandt werden, die in \cite{Tsochantaridis/etal/2005a} vorgestellt werden. Es muss nur die Kostenfunktion in Schritt 5 angepasst werden.
		\begin{Code}
					1  	\hspace{0.5cm}Input: ($x_1,y_1$), ..., ($x_n,y_n$), C, $\epsilon$
		
					2	 	\hspace{0.5cm}$S_i \leftarrow \emptyset$ for all i = 1, ..., n
					
					3	 	\hspace{0.5cm}{\bf repeat}
					
					4	 	\hspace{1.0cm}{\bf for} i = 1, ..., n {\bf do}
					
					5	 	\hspace{1.5cm}set up cost function [\textit{z.B: $SVM^{s}$: H(y) $\equiv	(1 - \langle \delta \Psi_i(y),w \rangle) \Delta(y_i,y)$}]
					
					6	 	\hspace{1.5cm}compute $\hat y = \arg\max_{y \in \mathcal{Y}} H(y)$
		
					7	 	\hspace{1.5cm}compute $\xi_i = \max\{0, \max_{y \in S_i} H(y)\}$
					
					8	 	\hspace{1.5cm}{\bf if} $H(\hat y) > \xi_i + \epsilon$ {\bf then}
					
					9	 	\hspace{1.5cm}$S_i \leftarrow S_i \cup \{\hat y\}$
					
					10	\hspace{1.3cm}$\alpha_S \leftarrow$ optimize dual over S, S = $\cup_i S_i$
					
					11	\hspace{1.3cm}{\bf end if}
					
					12	\hspace{0.8cm}{\bf end for}
					
					13	\hspace{0.3cm}{\bf until} no $S_i$ has changed during iteration\caption{Undercuts-Algorithmus}
		\label{code:svmstruct}
		\end{Code}
Es gibt eine Arbeitsmenge $S_i$ für jedes Trainingsbeispiel ($x_i,y_i$), welche in Zeile 2 definiert wird. Sie hält die aktuell ausgewählten Bedingungen fest. Beim abarbeiten der Trainingsbeispiele wird die Bedingung gesucht, die den größten Verlust zur Folge hat (siehe Zeile 6). Wenn dessen Margin-Überschreitung den in Zeile 7 errechneten Wert von $\xi_i$, mit mehr als $\epsilon$ überschreitet (diese Abfrage ist in Zeile 8 zu finden), dann soll die Bedingung $\hat y$ zur Arbeitsmenge hinzufügt werden (vgl. Zeile 9). Dies entspricht einer sukzessiven Verstärkung des grundlegenden Problems, durch eine Schnittebene, die die aktuelle Lösung von der zulässigen Menge entfernt. Die gewählte Schnittebene entspricht der Bedingung, die den kleinsten zulässigen Wert für $\xi_i$ bestimmt. Nachdem eine Bedingung zur Arbeitsmenge hinzugefügt wurde, muss die Lösung, in Zeile 10 (in Bezug auf S), neu errechnet werden. Der Algorithmus stoppt, wenn, wie in Zeile 13 gefordert, keine Bedingung durch mehr als $\epsilon$ verletzt wird und sich somit kein $S_i$ geändert hat. Es ist leicht zu zeigen, dass der Algorithmus eine Lösung hat die nahe am Optimum liegt. Für eine große Klasse von Problemen konvergiert der Algorithmus in polynomieller Zeit und das trotz eventuell exponentiellen oder unendlichen $\left| \mathcal{Y} \right|$. Das liegt daran, dass die Anzahl der Bedingungen in S nicht von $\left| \mathcal{Y} \right|$ abhängig ist. Wenn die Zeile 6 des Codes \ref{code:svmstruct} also polynomiell ist, dann ist der ganze Algorithmus polynomiell.

\paragraph{Anwendungen und Experimente}
Dieser Ansatz ist effektiv und vielseitig. Er kann auf eine breite Klasse von Aufgaben angewandt werden, z.B. auf Multiclass Klassifikation, Klassifikation mit Taxonomien, Label Sequence Learning, Sequence Alignment und Natural Language Parsing. Um den Algorithmus an das neue Problem anzupassen muss lediglich eine Implementierung der Merkmalsabbildung $\Psi(x,y)$, der Verlustfunktion $\Delta (y_i,y)$ und der Maximierung des Verlusts (Zeile 6 des Codes \ref{code:svmstruct}) erfolgen.

\begin{bsp}[Label Sequence Learning]
Es soll eine Sequenz von Labeln y = $(y^1, ..., y^n), y^k \in \Sigma$, gegeben einer Sequenz von Eingaben x = $(x^1, ..., x^m)$, vorhergesagt werden. Diese Art der Klassifizierung wird z.B. bei der optischen Zeichenerkennung, der natürlichsprachlichen Syntaxanalyse, der Informationsgewinnung und der Bioinformatik angewandt. Hier wird das Label Sequence Learning am Beispiel NER betrachtet, welches bereits aus Kapitel \ref{ner} bekannt sein sollte. Es wird eine Sammlung von 300 Sätzen betrachtet. Die Zeichenmenge besteht aus Bezeichnungslosen und zusätzlich aus dem Anfang und der Weiterführung von Personennamen, Organisationen, Orten und diversen Namen. Insgesamt gibt es also 9 verschiedene Labels. $\Psi(x,y)$ ist in diesem Fall ein Histogramm der Zustandsübergänge und eine Menge von Merkmalen die die Ausgaben	beschreiben. Tabelle \ref{tab:methodenvergleich} zeigt wie die unterschiedlichen Methoden bei diesem Datensatz abschneiden.
\begin{table}[h]
			\label{tab:methodenvergleich}
			\centering
			\begin{tabular}[c]{|c|c|c|c|c|}
					\hline
					Methode & HMM & CRF & Perceptron & SVM \\
					\hline
					Fehler & 9.36 & 5.17 & 5.94 & 5.08 \\
					\hline
			\end{tabular}
			\vspace{-0.2cm}
			\caption{Methodenvergleich}
			\vspace{-0.3cm}
		\end{table}
Die Standard Hidden Markov Model Methode, welche bereits aus Kapitel \ref{hmm} bekannt ist, wird von allen Lernmethoden deutlich übertroffen. Die Methoden Conditional Random Fields (welche bereits aus Kapitel \ref{crf} bekannt ist), Perceptron und SVM, schneiden fast gleich ab, wobei schon hier die SVM etwas besser ist als die anderen zwei Methoden. Die folgende Tabelle zeigt wie die SVM für nicht lineare Daten gegen die SVMstruct abschneidet.
		\begin{table}[h]
			\label{tab:methodenvergleich}
			\centering
			\begin{tabular}[c]{|c|c|c|c|c|}
					\hline
					Methode & Train Fehler & Test Fehler & Const & Verlust \\
					\hline
					$SVM^{nonlinear}$ & 0.2 $\pm$ 0.1 & 5.1 $\pm$ 0.6 & 2824 $\pm$ 106 & 1.02 $\pm$ 0.01 \\
					$SVM^{struct}$ & 0.4 $\pm$ 0.4 & 5.1 $\pm$ 0.8 & 2626 $\pm$ 225 & 1.10 $\pm$ 0.08 \\
					\hline
			\end{tabular}
			\vspace{-0.2cm}
			\caption{Vergleich der SVM Methoden}	
		\end{table}
Die Ergebnisse der unterschiedlichen SVM Methoden sind im großen und ganzen vergleichbar. Der Trainingsfehler ist für die $SVM^{nonlinear}$ etwas besser, der Testfehler hingegen ist nahezu identisch. Weniger Bedingungen werden bei der $SVM^{struct}$ hinzugefügt und der durchschnittliche Verlust ist bei der $SVM^{nonlinear}$ etwas besser. Aber diese Unterschiede sind alle kaum nennenswert.
\end{bsp}

\paragraph{Ergebnis}
Als Resultat ist eine SVM für überwachtes Lernen mit strukturierten und voneinander abhängigen Ausgaben entstanden. Diese basiert auf einer Merkmalsabbildung über Eingabe/Ausgabe - Paare und deckt damit eine breite Klasse von Modellen ab. Das wären z.B. gewichtete kontextfreie Grammatiken, Hidden Markov Models und Sequence Alignment, um nur einige wichtige zu nennen. Dieser Ansatz ist flexibel im Umgang mit methodenspezifischen Verlustfunktionen und eine sehr positive Eigenschaft ist, dass nur einem allgemeingültigen Algorithmus an sämtliche Aufgaben herangehen kann. Was die Präzision des Ansatzes angeht, so ist diese für einen weiten Bereich mindestens vergleichbar mit den üblichen Ansätzen und oft sogar besser. Was durch den Algorithmus aber garantiert wird ist, dass dieser nutzbar ist um komplexe Modelle zu trainieren, die ansonsten nur schwer im üblichen Rahmen behandelbar wären.
		
			
		