---
fontsize: 8pt
bibliography: 8_Referenzen.bib
citation_package: natbib
output:
  beamer_presentation:
    keep_tex: true
    includes:
      in_header: 8_header.tex
---


```{r, include = F}
source("8_R_common.R")
```

#  {.plain}
\center
```{r, echo = FALSE, out.width = "20%"}
knitr::include_graphics("8_Abbildungen/mvda_8_otto.png")
```

\vspace{2mm}

\Huge
Multivariate Datenanalyse
\vspace{6mm}

\Large
MSc Psychologie WiSe 2021/22

\vspace{6mm}
\large
Prof. Dr. Dirk Ostwald


#  {.plain}

\vfill
\center
\huge
\textcolor{black}{(8) Support Vektor Maschinen}
\vfill

#

Struktur der Prädiktiven Modellierung

\begin{minipage}{.6\textwidth}
```{r, echo = FALSE, out.width = "80%"}
knitr::include_graphics("8_Abbildungen/mvda_8_prädiktive_modellierung_1.pdf")
```
\end{minipage}
\begin{minipage}{.4\textwidth}
```{r, echo = FALSE, out.width = "90%"}
knitr::include_graphics("8_Abbildungen/mvda_8_prädiktive_modellierung_2.pdf")
```
\end{minipage}

\flushright
\tiny
nach @dwyer_2018
\vspace{3mm}

\flushleft
\small
Rhethorik der Prädiktiven Modellierung

\center
\begin{tabular}{ll}
Daten                     & Trainingsdaten und Testdaten                  \\
Statistisches Modell      & Modell, Machine Learning Algorithmus          \\
Schätzen von Parametern   & Trainieren des Modells, Lernen von Parametern, Supervised Learning
\end{tabular}

#
\small
\begin{definition}[Binärer Klassifikationstrainingdatensatz]
Ein \textit{binärer Klassifikationsdatensatz}
\begin{equation}
\mathcal{D} := \{(x^{(1)},y^{(1)}), (x^{(2)},y^{(2)}), ..., (x^{(n)},y^{(n)})\}
\end{equation}
ist eine Menge von $n$ \textit{Trainingsdatenpunkten}
\begin{equation}
(x^{(i)},y^{(i)}) \mbox{ mit } x^{(i)} \in \mathbb{R}^m
\mbox{ und }
y^{(i)} \in \{-1,1\}
\mbox{ für }
i = 1,...,n,
\end{equation}
wobei  $x^{(i)}$ \textit{$m$-dimensional Featurevektor} und $y^{(i)}$
\textit{Label} genannt wird
\end{definition}

Bemerkung

* $y^{(i)} \in \{-1,1\}$ bezeichnet die Klassenzugehörigkeit des Featurevektors $x^{(i)} \in \mathbb{R}^m$.
* Man beachte, dass hier $y^{(i)} \in \{-1,1\}$, wohingegen bei LDA/LR $y^{(i)} \in \{0,1\}$.


#
Welche lineare Diskriminanzfunktion (Hyperebene) soll hier man wählen ?
\vspace{5mm}

```{r, echo = F, out.width = "50%"}
knitr::include_graphics("8_Abbildungen/mvda_8_hyperebene.pdf")
```

#
Nach der Theorie der Maximum Margin Support Vektor Maschinen diese:
\vspace{5mm}

```{r, echo = F, out.width = "50%"}
knitr::include_graphics("8_Abbildungen/mvda_8_hyperebene_svm.pdf")
```

# {.plain}
\vfill
\setstretch{2.5}
\large
Geometrie linearer Diskriminanzfunktionen

Support Vektor Maschinen Training

SVM Training als quadratisches Optimierungsproblem

Kernelisierung der Maximum Margin SVM

Selbstkontrollfragen
\vfill

# {.plain}
\setstretch{2.5}
\large
**Geometrie linearer Diskriminanzfunktionen**

Support Vektor Maschinen Training

SVM Training als quadratisches Optimierungsproblem

Kernelisierung der Maximum Margin SVM

Selbstkontrollfragen


# Geometrie linearer Diskriminanzfunktionen
\footnotesize
\begin{definition}[Lineare Diskriminanzfunktion]
Eine \textit{Lineare  Diskriminanzfunktion} ist eine multivariate reellwertige
Funktion der Form
\begin{equation}
h : \mathbb{R}^m \to \{-1,+1\}, x \mapsto h(x) := g(f(x)),
\end{equation}
wobei
\begin{itemize}
\item $f$ eine multivariate reellwertige, parameterabhängige linear-affine Function
der Form
\begin{equation}
f : \mathbb{R}^m \to \mathbb{R}, x \mapsto f(x) := w^Tx + w_0,
\end{equation}
mit \textit{Parametervektor} $w \in \mathbb{R}^m$ und \textit{Biasparameter}
$w_0 \in \mathbb{R}$ ist und
\item $g$ eine univariate reellwertige, parameterunabhängige \textit{Klassifikationsfunktion}
der Form
\begin{equation}
g : \mathbb{R} \to \{-1,1\},
f(x) \mapsto g(f(x)) :=
\begin{cases}
-1, & f(x) < 0 \\
+1, & f(x) \ge 0
\end{cases}
\end{equation}
\end{itemize}
ist. Eine LDF induziert im Featurevektorenraum $\mathbb{R}^m$
\begin{itemize}
\item eine \textit{Entscheidungsgrenze} $H := \{x \in \mathbb{R}^m|f(x) = 0\}$, genannt \textit{Hyperebene},
\item eine \textit{Entscheidungsregion} $D_{-1} := \{x \in \mathbb{R}^m|f(x) < 0\}$, und
\item eine \textit{Entscheidungsregion} $D_{+1} := \{x \in \mathbb{R}^m|f(x) \ge 0\}$.
\end{itemize}
\end{definition}

# Geometrie linearer Diskriminanzfunktionen
\vspace{3mm}
```{r, echo = F, out.width = "90%"}
knitr::include_graphics("8_Abbildungen/mvda_8_ldf.pdf")
```

\small
Graphgleichungen für Hyperebenen in $\mathbb{R}^2$
\begin{equation}
f(x) = 0
\Leftrightarrow
w^T x + w_0 = 0
\Leftrightarrow
w_1 x_1 + w_2 x_2 + w_0 = 0
\Leftrightarrow
x_2 = - \frac{w_1}{w_2}x_1 - \frac{w_0}{w_2}
\end{equation}


# Geometrie linearer Diskriminanzfunktionen
\footnotesize
\setstretch{1.2}
\begin{theorem}[Geometrie linearer Diskriminanzfunktionen]
\normalfont
\begin{equation}
f : \mathbb{R}^m \to \mathbb{R}, x \mapsto f(x) := w^Tx + w_0
\end{equation}
sei eine multivariate reellwertige, parameterabhängige linear-affine Funktion und
\begin{equation}
H := \{x \in \mathbb{R}^m|f(x) = 0\} \subset \mathbb{R}^m
\end{equation}
sei die zugehörige Hyperebene. Weiterhin sei
\begin{equation}
||v||_2 := \sqrt{v^Tv}
\end{equation}
die Euklidische Länge von $v \in \mathbb{R}^m$. Dann gelten die folgenden geometrischen Beziehungen:
\begin{itemize}
\item[(1)] $w$ ist zu jedem Vektor, der in der Richtung von $H$ orientiert ist, orthogonal.
\item[(2)] Der minimale Euklidische Abstand $d$ zwischen $x \in \mathbb{R}^m$ und einem Punkt auf $H$ ist
\begin{equation}
d = \frac{1}{||w||_2}f(x).
\end{equation}
\item[(3)] Der minimale Euklidische Abstand $d_0$ zwischen dem Nullpunkt und einem Punkt auf $H$ ist
\begin{equation}
d_0 = \frac{w_0}{||w||_2}.
\end{equation}
\end{itemize}
\end{theorem}
Bemerkung

* $w$ bestimmt die Orientierung der Hyperebene im Featurevektorenraum.
* $w_0$ bestimmt die Lage der Hyperebene im Featurevektorenraum.

# Geometrie linearer Diskriminanzfunktionen

```{r, echo = F, out.width = "85%"}
knitr::include_graphics("8_Abbildungen/mvda_8_ldf_geometrie.pdf")
```

# Geometrie linearer Diskriminanzfunktionen
\footnotesize
\underline{Beweis von (1)}
\vspace{1mm}

$x_{a}\in H_{w}$ und $x_{b}\in H_{w}$ seien zwei beliebige Punkte auf der Hyperebene.
Dann gilt folgendes lineares Gleichungssystem:
\begin{equation}\label{eq:orth_proof_1}
w^{T}x_{a}+w_{0}=0
\end{equation}
\begin{equation}\label{eq:orth_proof_2}
w^{T}x_{b}+w_{0}=0.
\end{equation}
Subtraktion von \eqref{eq:orth_proof_2} von \eqref{eq:orth_proof_1} ergibt
\begin{equation}
w^{T}x_{a}-w^{T}x_{b}=0\Leftrightarrow w^{T}\left( x_{a}-x_{b} \right)=0.
\end{equation}
Also ist der Parametervektor orthogonal zu dem Vektor $y:=(x_{a}-x_{b})$,
welcher in Richtung der Hyperebene orientiert ist.

\underline{Beweis von (2)}
\vspace{1mm}

Wir betrachten die Zerlegung eines Punktes $x\in \mathbb{R}^{m}$ in seine orthogonale
Projektion auf eine Hyperebene $x_{p}\in \mathbb{R}^{m}$ und seinen Abstand von
der Hyperebene $d\frac{w}{\lVert w \rVert_{2}}$
\begin{equation}
x = x_{p}+d\frac{w}{\lVert w \rVert_{2}}.
\end{equation}
Diese Zerlegung ist möglich, weil  $w$ orthogonal zu jedem in Richtung der Hyperebene
orientiertem Vektor ist und
$\lVert \frac{w}{\lVert w \rVert_{2}} \rVert_{2} = 1$
gilt.

# Geometrie linearer Diskriminanzfunktionen
\footnotesize
Als nächstes betrachten wir die Transformation dieses so zerlegten
$x$ durch die lineare Diskriminanzfunktion:
\begin{equation}
f(x)= w^{T}x+w_{0}
= w^{T}\left(x_{p}+d\frac{w}{\lVert w \rVert_{2}} \right)+w_{0}
= w^{T}x_{p}+w_{0}+d\frac{w^{T}w}{\lVert w \rVert_{2}}.
\end{equation}
Dann gilt, weil  $x_{p}\in H_{w}$ und somit $w^{T}x_{p}+w_{0} = 0$, dass
\begin{equation}
f(x)=d\frac{w^{T}w}{\lVert w \rVert_{2}}=d\frac{\lVert w
\rVert_{2}^{2}}{\lVert w \rVert_{2}}=d\lVert w \rVert_{2}.
\end{equation}
Also folgt
\begin{equation}
d = \frac{1}{\lVert w \rVert_{2}}f(x).
\end{equation}

\underline{Beweis von (3)}
\vspace{1mm}

Für den minimalen Abstand des Nullpunktes $x_{0}=\left(0,... ,0 \right)^{T}\in \mathbb{R}^{m}$
zu Punkten auf der Hyperebene gilt
\begin{equation}
d_{0}
= \frac{1}{\lVert w \rVert_{2}}f\left( x_{0}\right)
= \frac{1}{\lVert w \rVert_{2}}(w^{T}x_{0}+w_{0})
= \frac{1}{\lVert w \rVert_{2}}w^{T}
\begin{pmatrix}
0\\
\vdots \\
0\\
\end{pmatrix}
+ \frac{w_{0}}{\lVert w \rVert_{2}}
= \frac{w_{0}}{\lVert w \rVert_{2}}.
\end{equation}

$\hfill \Box$



# Geometrie linearer Diskriminanzfunktionen
\footnotesize
\begin{definition}[Hyperebenenmargin und Support Vektoren]
\justifying
$\mathcal{D}$ sei ein Trainingsdatensatz,  $f$ sei eine multivariate reellwertige
linear-affine Funktion und $H$ sei die durch $f$ induzierte Hyperebene. Weiterhin
sei
\begin{equation}
\left\lvert d^{(i)} \right\rvert
:= \left\lvert\frac{1}{\lVert w \rVert_2}f\left(x^{(i)}\right)\right\rvert
= \frac{y^{(i)}}{\lVert w \rVert_2}f\left(x^{(i)}\right)
= \frac{y^{(i)}(w^Tx^{(i)} + w_0)}{\lVert w \rVert_2} \ge 0
\end{equation}
der absolute Wert des minimalen Euklidischen Abstands eines Featurevektors
$x^{(i)}, i = 1,...,n$  von  $H$. Dann ist der \textit{Margin} $d^*$ von $H$
hinsichtlich $\mathcal{D}$ definiert als das Minimum der absoluten minimalen
Euklidischen Abstände von Featurevektoren zur Hyperebene,
\begin{equation}
d^*
:= \min_{i=1,...,n}
\left\lbrace
\left\lvert d^{(i)} \right\rvert
\right\rbrace
= \min_{i=1,...,n}
\left\lbrace
\frac{y^{(i)}(w^Tx^{(i)} + w_0)}{\lVert w \rVert_2}
\right\rbrace.
\end{equation}
Ein Featurevektor  $x^{(i)}$ wird \textit{Support Vektor} genannt, wenn
$|d^{(i)}| = d^*$, d.h., wenn $x^{(i)}$ auf dem Margin der Hyperebene liegt.
\end{definition}


# Geometrie linearer Diskriminanzfunktionen
\vspace{3mm}
Hyperebenenmargin und Support Vektoren

```{r, echo = F, out.width = "65%"}
knitr::include_graphics("8_Abbildungen/mvda_8_margin.pdf")
```

# Geometrie linearer Diskriminanzfunktionen
\footnotesize
\begin{definition}[Äquivalente Hyperebenen und kanonische Hyperebene]
$f$ sei eine multivariate reellwertige linear-affine Funktion und
\begin{equation}
H := \{x \in \mathbb{R}^m |f(x) = 0\}
\end{equation}
sei die durch $f$ induzierte Hyperebene. Dann induzieren alle skalaren Vielfachen
von $f$ (und damit von  $w$ und $w_0$) die identische Hyperebene, denn aus $f(x) = 0$
folgt, dass  $af(x) = 0$ für jedes $a \in \mathbb{R} \setminus \{0\}$. Die
Hyperebenen
\begin{equation}
H_a :=  \{x \in \mathbb{R}^m |af(x) = 0, a \in \mathbb{R}\setminus \{0\} \}
\end{equation}
heißen die zu $H$ äquivalenten Hyperebenen. Zu einem Support Vektor  $x^*$ und
einer Menge äquivalenter Hyperebenen (und somit einer Menge Parametervektoren
und Biasparametern, welche die äquivalenten Hyperebenen induzieren) ist die
\textit{kanonische Hyperebene} definiert als die Hyperebene (und somit der spezifische
Parametervektor $w$ und Biasparameter $w_0$), für die gilt
\begin{equation}
|f(x^*)| = y^*(w^Tx^* + w_0) = 1.
\end{equation}
Aus der Definition der kanonischen Hyperebene folgt dann sofort, dass der Margin
der kanonischen Hyperebene durch
\begin{equation}
d^* = \frac{1}{\lVert w \rVert_2}.
\end{equation}
gegeben ist.
\end{definition}


# {.plain}
\setstretch{3}
\large
Geometrie linearer Diskriminanzfunktionen

**Support Vektor Maschinen Training**

SVM Training als quadratisches Optimierungsproblem

Kernelisierung der Maximum Margin SVM

# Support Vektor Maschinen Training
\small
\begin{definition}[Linear separierbarer Trainingsdatensatz]
\justifying
Ein Trainingsdatensatz heißt \textit{linear separierbarer Trainingsdatensatz},
wenn eine lineare Diskriminanzfunktion existiert, so dass alle Trainingsdatenpunkte
korrekt klassifiziert werden können. Ein Trainingsdatensatz heißt nicht-linear
separierbarer Trainingsdatensatz, wenn keine solche lineare Diskriminanzfunktion
existiert.
\end{definition}

# Support Vektor Maschinen Training
\footnotesize
\begin{definition}[Maximum Margin-Klassifikation]
\justifying
$\mathcal{D}$ sei ein linear separierbarer Trainingsdatensatz. Dann ist das
Training einer Support Vektor Maschine für \textit{Maximum Margin-Klassifikation}
gegeben durch das Optimierungsproblem
\begin{equation}
\min_{w} \frac{1}{2}\lVert w  \rVert_2^2
\mbox{ mit den Nebenbedingungen }
y^{(i)}(w^Tx^{(i)} + w_0) \ge 1 \mbox{ für } i = 1,...,n.
\end{equation}
\vspace{1mm}
Speziell entsprechen hierbei
\begin{itemize}
\item das Ziel
\begin{equation}
\min_{w} \frac{1}{2}\lVert w \rVert_2^2 \Leftrightarrow \max_{w} \frac{1}{\lVert w \rVert_2}
\end{equation}
der Maximierung des Margins der von der SVM induzierten Hyperebene,
\item die Nebenbedingungen
\begin{equation}
y^{(i)}(w^Tx^{(i)} + w_0) \ge 1 \mbox{ für } i = 1,...,n
\end{equation}
dem Ziel, dass alle Featurevektoren auf der korrekten Seite der Hyperebene liegen
oder Support Vektoren sind.
\end{itemize}
\end{definition}

# Support Vektor Maschinen Training
\vspace{3mm}
Maximum Margin-Klassifikation

```{r, echo = F, out.width = "65%"}
knitr::include_graphics("8_Abbildungen/mvda_8_maximum_margin.pdf")
```

# Support Vektor Maschinen Training

\footnotesize
\begin{definition}[Soft Margin-Klassifikation]
\justifying
$\mathcal{D}$ sei ein nicht notwendigerweise linear separierbarer Trainingsdatensatz.
Dann ist das Training einer Support Vektor Maschine für \textit{Soft Margin-Klassifikation}
gegeben durch das Optimierungsproblem
\begin{equation}
\min_{w,\xi}
\frac{1}{2}\lVert w \rVert_2^2 + C\sum_{i=1}^n \xi_i^k
\mbox{ unter den Nebenbedingungen }
y^{(i)}(w^Tx^{(i)} + w_0) \ge 1 - \xi_i, \xi \ge 0
\end{equation}
wobei $\xi := (\xi_1,...,\xi_n)$ ein Vektor sogenannter
\textit{Schlupfvariablen (slack variables)} $\xi_i, i = 1,...,n$ ist, der
term $\sum_{i=1}^n \xi_i^k$  \textit{Loss} genannt wird, $k \in \mathbb{N}$ eine
Konstante ist, welche die genaue Form des Losses bestimmt (z.B. \textit{hinge loss}
für $k = 1$, \textit{quadratic loss} für $k = 2$), und $C \in \mathbb{R}$ eine
empirisch gewählte Konstante ist. Speziell entsprechen hierbei
\begin{itemize}
\item das Optimierungsziel dem Ziel, den Margin der durch die SVM induzierten
Hyperebene zu maximieren und gleichzeitig den Loss zu minimieren, wobei die
relative Gewichtung dieser beiden Ziele durch $C$ gegeben ist,
\item die Nebenbedingungen den Zielen
\begin{itemize}
\footnotesize
\item[(1)] der korrekten Trainingsdatenpunktklassifikation und der Maximierung
des Margins für $\xi_i = 0$,,
\item[(2)] der korrekten Trainingsdatenpunktklassifikation für $0 < \xi \le 1$, und
\item[(3)] inkorrekter Trainingsdatenpunktklassifikation für  $\xi > 1$.
\end{itemize}
\end{itemize}
\end{definition}

# Support Vektor Maschinen Training
\vspace{3mm}
Soft Margin-Klassifikation

```{r, echo = F, out.width = "80%"}
knitr::include_graphics("8_Abbildungen/mvda_8_soft_margin.pdf")
```

# Support Vektor Maschinen Training
Soft Margin SVM Training mit R Paket `e1071`
\vspace{2mm}

\footnotesize
\setstretch{1.2}
```{r, message = F}
# Einlesen der Studienerfolgdaten und Fokus auf binäre Klassifikation
library(foreign)
D         = read.spss(file.path(getwd(), "8_Daten", "studienerfolg.sav"),
                      to.data.frame = T)
D         = D[D[,1] != "befriedigend",]

# SVM Training und Trainingsdatenprädiktion
library(e1071)                                             # SVM Paket
acc = rep(NaN,4)                                           # Accuracyarray
for(i in 1:4){                                             # Featuresetiteration
    x         = D[,2:(2+i-1)]                              # Featurevektoren
    y         = D[,1]                                      # Labelvariable
    svm.train = svm(x,y, kernel = "linear")                # SVM Training
    svm.pred  = predict(svm.train, x, kernel = "linear")   # Vorhersage der Trainingsdatenlabel
    acc[i]    = mean(svm.pred == y)                        # Trainingsdatenvorhersageaccuracy
}
print(acc)
```
# Support Vektor Maschinen Training
Soft Margin SVM Leave-One-Out Cross-Validation, $m = 2$

\vspace{2mm}
\tiny
\setstretch{1}

```{r, message = F, results = F}
# Einlesen der Studienerfolgdaten und Fokus auf binäre Klassifikation
library(foreign)
D         = read.spss(file.path(getwd(), "8_Daten", "studienerfolg.sav"),
                      to.data.frame = T)
D         = D[D[,1] != "befriedigend",]
K         = nrow(D)
x         = D[,2:3]
y         = D[,1]

# K-fache Leave-One-Out Cross-Validation
library(e1071)
correct   = rep(NaN,K)
h         = rep(NaN,K)
for(k in 1:K){

    # Datensatzpartition
    x_train       = x[-k,]
    y_train       = y[-k]
    x_test        = x[k,]
    y_test        = y[k]

    # Trainingsdatensatz-basiertes Parameterlernen
    svm.train     = svm(x_train,y_train, kernel = "linear")

    # Testdatensatz-basierte Prädiktion
    svm.pred      = predict(svm.train, x_test, kernel = "linear")
    h[k]          = as.numeric(svm.pred)
    correct[k]    = svm.pred == y_test
}
cat("Accuracy: ", mean(correct))
```

# Support Vektor Maschinen Training
Soft Margin SVM Leave-One-Out Cross-Validation, $m = 2$

\tiny
\setstretch{0.8}
```{r, echo = F}
# data tabulation with recoding for consistency
y_label                     = rep(1,K)
y_label[y == "ungenügend"]  = -1
h_label                     = rep(1,K)
h_label[h == "1"]           = -1
P  = data.frame(cbind(x, y_label, h_label))
colnames(P) =  c("x_1", "x_2", "y", "h(x)")
knitr::kable(P, "pipe", digits = 1)
```
\small
Prediction Accuracy = 0.77.

# Support Vektor Maschinen Training
Leave-One-Out Cross-Validation, $m = 3$

```{r, message = F, echo = F, results = F}
# Einlesen der Studienerfolgdaten und Fokus auf binäre Klassifikation
library(foreign)
D         = read.spss(file.path(getwd(), "8_Daten", "studienerfolg.sav"),
                      to.data.frame = T)
D         = D[D[,1] != "befriedigend",]
K         = nrow(D)
x         = D[,2:4]
y         = D[,1]

# K-fache Leave-One-Out Cross-Validation
library(e1071)
correct   = rep(NaN,K)
h         = rep(NaN,K)
for(k in 1:K){

    # Datensatzpartition
    x_train       = x[-k,]
    y_train       = y[-k]
    x_test        = x[k,]
    y_test        = y[k]

    # Trainingsdatensatz-basiertes Parameterlernen
    svm.train     = svm(x_train,y_train, kernel = "linear")

    # Testdatensatz-basierte Prädiktion
    svm.pred      = predict(svm.train, x_test, kernel = "linear")
    h[k]          = as.numeric(svm.pred)
    correct[k]    = svm.pred == y_test
}
cat("Accuracy: ", mean(correct))
```

\tiny
\setstretch{0.8}
```{r, echo = F}
# data tabulation with recoding for consistency
y_label                     = rep(1,K)
y_label[y == "ungenügend"]  = -1
h_label                     = rep(1,K)
h_label[h == "1"]           = -1
P  = data.frame(cbind(x, y_label, h_label))
colnames(P) =  c("x_1", "x_2", "x_3", "y", "h(x)")
knitr::kable(P, "pipe", digits = 1)
```
\small
Prediction Accuracy = 0.77.

# Support Vektor Maschinen Training
Soft Margin SVM Leave-One-Out Cross-Validation, $m = 4$

```{r, message = F, echo = F, results = F}
# Einlesen der Studienerfolgdaten und Fokus auf binäre Klassifikation
library(foreign)
D         = read.spss(file.path(getwd(), "8_Daten", "studienerfolg.sav"),
                      to.data.frame = T)
D         = D[D[,1] != "befriedigend",]
K         = nrow(D)
x         = D[,2:5]
y         = D[,1]

# K-fache Leave-One-Out Cross-Validation
library(e1071)
correct   = rep(NaN,K)
h         = rep(NaN,K)
for(k in 1:K){

    # Datensatzpartition
    x_train       = x[-k,]
    y_train       = y[-k]
    x_test        = x[k,]
    y_test        = y[k]

    # Trainingsdatensatz-basiertes Parameterlernen
    svm.train     = svm(x_train, y_train, kernel = "linear")

    # Testdatensatz-basierte Prädiktion
    svm.pred      = predict(svm.train, x_test, kernel = "linear")
    h[k]          = svm.pred
    correct[k]    = svm.pred == y_test
}
cat("Accuracy: ", mean(correct))
```

\tiny
\setstretch{0.8}
```{r, echo = F}
# data tabulation with recoding for consistency
y_label                     = rep(1,K)
y_label[y == "ungenügend"]  = -1
h_label                     = rep(1,K)
h_label[h == "1"]           = -1
P  = data.frame(cbind(x, y_label, h_label))
colnames(P) =  c("x_1", "x_2", "x_3", "x_4", "y", "h(x)")
knitr::kable(P, "pipe", digits = 1)
```
\small
Prediction Accuracy = 0.60.

# {.plain}
\setstretch{2.5}
\large

Geometrie linearer Diskriminanzfunktionen

Support Vektor Maschinen Training

**SVM Training als quadratisches Optimierungsproblem**

**Kernelisierung der Maximum Margin SVM**

Selbstkontrollfragen


# SVM Training als quadratisches Optimierungsproblem

\textcolor{darkblue}{Kernelisierung der Maximum Margin SVM}

\small
Kernelmethoden basieren auf dem dualen Problem des Maximum Margin SVM Trainingproblems.

Die zentrale Einsicht ist dabei, dass die Zielfunktion des dualen SVM Trainingproblems
\begin{equation}
q(\lambda) := \sum_{i=1}^n \lambda_i - \frac{1}{2} \sum_{i = 1}^n \sum_{j = 1}^n \lambda_i\lambda_j y^{(i)} y^{(j)} x^{(i)^T }x^{(j)}
\end{equation}
lediglich von den Skalarprodukten der Featurevektoren
\begin{equation}
x^{(i)^T }x^{(j)} \mbox{ für } i,j = 1,...,n.
\end{equation}
abhängt.

Die Projektion der Featurevektoren in einen "hochdimensionalen Featureraum",
in welchem auf lineare Separabilität gehofft wird, benötigt also nur
die Auswertung von Skalarprodukten.

Skalarprodukte in den Projektionsräumen werden *Kernel* genannt.



# {.plain}
\setstretch{2.5}
\large

Geometrie linearer Diskriminanzfunktionen

Support Vektor Maschinen Training

**SVM Training als quadratisches Optimierungsproblem**

Kernelisierung der Maximum Margin SVM

Selbstkontrollfragen



# {.plain}
\huge
\center
\vfill
\setstretch{3}
**Beginn Exkurs**

Grundlagen der

Optimierung mit Nebenbedingungen
\vfill

# Grundlagen der Optimierung mit Nebenbedingungen
\footnotesize
\begin{definition}[Optimierungsproblem mit Nebenbedingungen]
\justifying
Ein \textit{Optimierungsproblem mit Nebenbedingungen} hat die allgemeine Form
\begin{equation}
\min_{x \in \mathbb{R}^n} f(x) \mbox{ u.d.N. }
c_i(x) = 0, i \in E,
c_i(x) \ge 0, i \in I,
\end{equation}
wobei $f : \mathbb{R}^n \to \mathbb{R}$ und $c_i : \mathbb{R}^n \to \mathbb{R}, i \in E \cup I$
glatte multivariate reellwertige Funktions und $E,I$ endliche Indexmengen sind.
$f$ heißt \textit{Zielfunktion}, die $c_i, i \in E$ heißen \textit{Gleichungsnebenbedingungen} und
die $c_i, i \in I$ heißen \textit{Ungleichungsnebenbedingungen}. Die Menge
\begin{equation}
\mathcal{X} := \{x \in \mathbb{R}^n| c_i(x) = 0, i \in E \mbox{ und } c_i(x) \ge 0, i \in I \}
\end{equation}
heißt \textit{feasible set}.
\end{definition}

Bemerkung

* \justifying Die notwendigen Bedingungen für Minimalstellen bei Optimierungsproblem
ohne Nebenbedingungen sind für $n = 1$: $f'(x^*) = 0$ und
für $n > 1$: $\nabla f(x^*) = 0_n$. Im Folgenden führen wir analoge notwendige
Bedingungen erster Ordnung für  Minimalstellen bei Optimierungsproblemen mit
Nebenbedingungen ein.


# Grundlagen der Optimierung mit Nebenbedingungen
Beispiel

\footnotesize
\begin{definition}[Quadratisches Programm]
\justifying
Ein \textit{Quadratisches Programm} ist das konvexe Optimierungsproblem mit den
Nebenbedingungen
\begin{equation}
\min_{x \in \mathbb{R}^n} \frac{1}{2}x^T P x + q^T x
\mbox{ u.d.N. }
Ax = b
\mbox{ und }
-Gx + h \ge 0,
\end{equation}
wobei
\begin{itemize}
\item $P \in \mathbb{R}^{n \times n}$ eine positiv definite Matrix ist,
\item $q \in \mathbb{R}^n$, $A \in \mathbb{R}^{p\times n}$, $b \in \mathbb{R}^p$ sind und
\item $G \in \mathbb{R}^{m \times n}$, und  $h \in \mathbb{R}^m$ sind.
\end{itemize}
\end{definition}

Bemerkungen

* Quadratische Programme sind Optimierungsprobleme mit Nebenbedingungen.
* Parameterlernen bei Support Vektor Maschinen  führt auf ein Quadratisches Programm.
* Optimierungstoolboxen enhalten Funktionen zur Lösung Quadratischer Programme.
* In R bietet sich das Paket `quadprog` an.

# Grundlagen der Optimierung mit Nebenbedingungen
\footnotesize
\begin{definition}[Lagrange Funktion, Lagrange Multiplikatoren]
\justifying
Es sei
\begin{equation}
\min_{x \in \mathbb{R}^n} f(x) \mbox{ u.d.N. }
c_i(x) = 0, i \in E,
c_i(x) \ge 0, i \in I,
\end{equation}
ein Optimierungsproblem mit Nebenbedingungen. Dann ist die \textit{Lagrange Funktion}
dieses Problems definiert als
\begin{equation}
L: \mathbb{R}^n \times \mathbb{R}^{|E\cup I|} \to \mathbb{R},
(x,\lambda) \mapsto L(x,\lambda) :=
f(x) - \sum_{i \in E \cup I}\lambda_ic_i(x).
\end{equation}
Hierbei wird $\lambda \in \mathbb{R}^{|E\cup I|}$ \textit{Lagrange-Multiplikatoren Vektor}
genannt und die einzelnen $\lambda_i \in \mathbb{R}$ mit $i \in E\cup I$ werden
\textit{Lagrange Multiplikatoren}genannt.
\end{definition}

Bemerkung

* \justifying Die Lagrange Funktion und die Lagrange Multiplikatoren nehmen in den
notwendigen Bedingungen der Optimierung mit Nebenbedingungen eine zentrale Rolle ein.


# Grundlagen der Optimierung mit Nebenbedingungen
\footnotesize
\begin{definition}[Notwendige Bedingungen erster Ordnung]
\justifying
$x^*$ sei eine lokale Lösung des Optimierungsproblems
\begin{equation}
\min_{x \in \mathbb{R}^n} f(x) \mbox{ u.d.N. }
c_i(x) = 0, i \in E,
c_i(x) \ge 0, i \in I.
\end{equation}
Dann gibt es einen Lagrange-Multiplikatoren Vektor $\lambda^* \in \mathbb{R}^{|E\cup I|}$
mit den Komponenten $\lambda_i^*, i \in E \cup I$, so dass die folgenden Bedingungen
an der Stelle $(x^*,\lambda^*) \in \mathbb{R}^{n + |E\cup I|}$ gelten
\begin{align*}
\nabla_x L(x^*,\lambda^*) 	  & =   0 								\\
c_i(x^*) 					            & =   0 \mbox{ für alle } i \in E 		\\
c_i(x^*) 					            & \ge 0 \mbox{ für alle } i \in I 		\\
\lambda_i^* 				          & \ge 0 \mbox{ für alle } i \in I 		\\
\lambda_i^*c_i(x^*)			      & = 0 \mbox{ für alle } i \in E\cup I
\end{align*}
\end{definition}

Bemerkungen

* Die Bedingungen werden auch \textit{Karush-Kuhn-Tucker (KKT)} Bedingungen genannt.
* Für einen Beweis und Reguläritätsbedingungen, siehe @nocedal_2006 Section 12.4.
* Die letzte Bedingung impliziert $\lambda_i^* > 0 \Rightarrow c_i(x^*) = 0$.

# Grundlagen der Optimierung mit Nebenbedingungen
\footnotesize
\begin{definition}[Duales Problem]
\justifying
Es sei
\begin{equation}
\min_{x \in \mathbb{R}^n} f(x) \mbox{ u.d.N. } c(x) \ge 0,
\end{equation}
ein Optimierungsproblem ohne Gleichungsnebenbedingungen, $c(x) := (c_1(x),c_2(x),...,c_m(x))^T$
sei die multivariate vektorwertige Funktion der Ungleichungsnebenbedingungen
und die zugehörige Lagrange Funktion und der Lagrange Multiplikatoren Vektoren $\lambda \in \mathbb{R}^m$
seien durch
\begin{equation}
L: \mathbb{R}^n \times \mathbb{R}^m \to \mathbb{R},
(x,\lambda) \mapsto L(x,\lambda) :=
f(x) - \lambda^T c(x).
\end{equation}
gegeben. Dann ist die \textit{duale Zielfunktion} (auch \textit{duale Lagrange Funktion genannt})
definiert als
\begin{equation}
q : \mathbb{R}^m \to \mathbb{R}, \lambda \mapsto q(\lambda) := \min_x L(x,\lambda),
\end{equation}
und das  \textit{duale Problem} ist definiert als
\begin{equation}
\max_{\lambda \in \mathbb{R}^m} q(\lambda) \mbox{ u.d.N. } \lambda \ge 0.
\end{equation}
\end{definition}
Bemerkung

* Duale Probleme sind manchmal einfacher zu lösen als die (primären) Ausgangsprobleme.
* Duale Probleme sind für das Parameterlernen von Support Vektor Maschinen zentral.

# Grundlagen der Optimierung mit Nebenbedingungen
\footnotesize
\begin{theorem}[Schwache Dualität]
\justifying
\normalfont
Für jede Lösung $\bar{x}$ von
\begin{equation}
\min_{x \in \mathbb{R}^n} f(x) \mbox{ u.d.N. } c(x) \ge 0,
\end{equation}
und jedes $\bar{\lambda} \ge 0$ gilt, dass
\begin{equation}
q(\bar{\lambda}) \le f(\bar{x}).
\end{equation}
\end{theorem}

\footnotesize
\underline{Beweis}

Mit den Definitionen von $q$, $\bar{\lambda} \ge 0$, und $c(\bar{x}) \ge 0$,  gilt, dass
\begin{equation}
q(\bar{\lambda})
= \min_x f(x) - \bar{\lambda}^T c(x)
\le f(\bar{x}) - \bar{\lambda}^T c(\bar{x})
\le f(\bar{x}).
\end{equation}

$\hfill \Box$

Bemerkung

* \justifying Das Theorem besagt, dass der optimierte Wert des dualen Problems eine
untere Grenze für den optimalen Wert der Zielfunktion des Ausgangsproblems ist.


# Grundlagen der Optimierung mit Nebenbedingungen
\footnotesize
\begin{theorem}[Starke Dualität]
\normalfont
\justifying
Gegeben seien das Optimierungsproblem
\begin{equation}
\min_{x \in \mathbb{R}^n} f(x) \mbox{ u.d.N. } c(x) \ge 0
\end{equation}
und seine zugehörigen notwendigen Bedingungen erster Ordnung
\begin{align}
\begin{split}
\nabla f(\bar{x}) - \nabla c(\bar{x})\bar{\lambda} & = 0, \\
c(\bar{x}) & \ge 0, \\
\bar{\lambda} & \ge 0, \\
\bar{\lambda}_i c_i(\bar{x}) & = 0, i = 1,2,...,m,
\end{split}
\end{align}
mit $\nabla c(x) = \left(\nabla c_1(x), \nabla c_2(x), ...,\nabla c_m(x)\right) \in \mathbb{R}^{n \times m}$.
$\bar{x}$ sei eine Lösung des Ausgangsproblems und $f$ sowie $-c_i, i = 1,2,...,m$
konvexe Funktionen auf  $\mathbb{R}^n$, die in $\bar{x}$ differenzierbar sind.
Dann ist jedes $\bar{\lambda}$, für das $(\bar{x},\bar{\lambda})$ die notwendigen
Bedingungen des Ausgangsproblem erfüllt, eine Lösung des dualen Problems
\end{theorem}

Bemerkungen

* Die optimalen Lagrange Multiplikatoren des Ausgangsproblems sind Lösungen des dualen Problems.
* SVM Training als Quadratisches Programm benötigt das Konzept der starken Dualität.

# Grundlagen der Optimierung mit Nebenbedingungen
\footnotesize
\underline{Beweis}
\vspace{1mm}

Wir nehmen an, dass  $(\bar{x}, \bar{\lambda})$ die notwendigen Bedingungen erster
Ordnung für ein Minimum des Ausgangsproblem erfüllen und dass $L(\cdot ,\bar{\lambda})$
konvex und differenzierbar ist. Dann gilt für jedes  $x \in \mathbb{R}^n$, dass
\begin{equation}
L(x,\bar{\lambda})
\ge L(\bar{x},\bar{\lambda}) + \nabla_x L(\bar{x},\bar{\lambda})(x - \bar{x})
= L(\bar{x},\bar{\lambda}),
\end{equation}
weil $\nabla_x L(\bar{x},\bar{\lambda}) = 0$. Also gilt für die duale Zielfunktion
\begin{equation}
q(\bar{\lambda}) = \inf_{x} L(x,\bar{\lambda}) = L(\bar{x},\bar{\lambda}).
\end{equation}
Mit der letzten der notwendigen Bedingungen erster Ordnung folgt weiterhin
\begin{equation}
q(\bar{\lambda})
= L(\bar{x},\bar{\lambda})
= f(\bar{x}) - \bar{\lambda}^T c(\bar{x})
= f(\bar{x})
\end{equation}
Schließlich gilt mit dem Theorem zur Schwachen Dualität, dass  $q(\lambda) \le f(\bar{x})$
für alle $\lambda \ge 0$. Also folgt mit  $q(\bar{\lambda}) = f(\bar{x})$, dass
$\bar{\lambda}$ eine Lösung des dualen Problems ist.
$\hfill \Box$


# {.plain}
\huge
\center
\vfill
\setstretch{3}
**Ende Exkurs**

Grundlagen der

Optimierung mit Nebenbedingungen
\vfill

# SVM Training als quadratisches Programmierungsproblem

\footnotesize
\begin{theorem}[SVM Training als quadratisches Programmierungsproblem I]
\normalfont
\justifying
Das duale Problem des Maximum Margin SVM Trainingproblems
\begin{equation}
\min_{w} \frac{1}{2}\lVert w \rVert_2^2
\mbox{ mit den Nebenbedingungen } y^{(i)}(w^Tx^{(i)} + w_0) \ge 1
\mbox{ für } i = 1,...,n
\end{equation}
ist gegeben als
\begin{equation}
\max_{\lambda \in \mathbb{R}^n} q(\lambda)
:= \sum_{i=1}^n \lambda_i
- \frac{1}{2} \sum_{i = 1}^n \sum_{j = 1}^n \lambda_i\lambda_j y^{(i)} y^{(j)} x^{(i)^T }x^{(j)}
\end{equation}
unter den Nebenbedingungen
\begin{equation}
\lambda \ge 0 \mbox{ and } \sum_{i = 1}^n \lambda_i y^{(i)} = 0.
\end{equation}
Basierend auf einer Lösung $\bar{\lambda}$ des dualen Problems sind alle $x^{(i)}$
mit $\bar{\lambda}_i > 0, i = 1,...,n$ Support Vektoren und die Lösungen für den
Parametervektor und den Biasparameter des primären Problems sind
\begin{equation}
\bar{w} = \sum_{i=1}^n \bar{\lambda_i} y^{(i)}x^{(i)}
\mbox{ and }
\bar{w}_0 = \frac{1}{n} \sum_{i = 1}^n \left(y^{(i)} -  \bar{w}^T x^{(i)}\right),
\end{equation}
respective.
\end{theorem}


# SVM Training als quadratisches Programmierungsproblem

\footnotesize
\begin{theorem}[SVM Training als quadratisches Programmierungsproblem II]
\normalfont
\justifying
Weiterhin gilt, dass bei Definition von
\begin{equation}
y := \left(y^{(i)}\right)_{i = 1,...,n} \in \mathbb{R}^n \mbox{ and }
K := \left(x^{(i)^T} x^{(j)}\right)_{i,j = 1,...,n} \in \mathbb{R}^{n \times n},
\end{equation}
as well as
\begin{equation}
P := yy^TK \in \mathbb{R}^{n \times n},
q := - 1_n,
G := -I_n,
h := 0_n,
A := y^T,
\mbox{ and } b := 0
\end{equation}
das duale Problem des Maximum Marging SVM Trainingproblems als quadratisches
Programmierproblem der Form
\begin{equation}
\min_{\lambda \in \mathbb{R}^n} \frac{1}{2}\lambda^T P \lambda + q^T \lambda
\mbox{ mit den Nebenbedingungen }
-G\lambda + h \ge 0_n
\mbox{ and }
A\lambda = b
\end{equation}
geschrieben werden kann, und somit mit allen Standardalgorithmen der quadratischen
Programmierung gelöst werden kann.
\end{theorem}

Bemerkungen

* Einerseits führt die QP Formulierung von Maximum Margin SVM Problem auf ein Standardproblem.
* Andererseits motiviert die QP Formulierung des Maximum Margin SVM Problems auch Kernelmethoden


# SVM Training als quadratisches Programmierungsproblem

\underline{Beweis}
\vspace{1mm}

\footnotesize
\noindent (1) Lagrangefunktion des primären Problems
\vspace{1mm}

Per definition ist die Lagrangefunktion des primären Problems
\begin{equation}
\min_{w, w_0} \frac{1}{2}\lVert w \rVert_2^2
\mbox{ mit den Nebenbedingungen } y^{(i)}(w^Tx^{(i)} + w_0) \ge 1
\mbox{ für } i = 1,...,n
\end{equation}
gegeben durch
\begin{equation}
L(w,w_0,\lambda) :=
\frac{1}{2}w^Tw -
\sum_{i=1}^n \lambda_i(y^{(i)}(w^Tx^{(i)} + w_0) - 1).
\end{equation}

\noindent (2) Bestimmung der Zielfunktion des dualen Problems
\vspace{1mm}

Per definition ist die Zielfunktion des dualen Problems gegeben durch
\begin{equation}
q : \mathbb{R}^n \to \mathbb{R}, \lambda \mapsto q(\lambda) := \min_{w,w_0} L(w,w_0,\lambda).
\end{equation}
Die analytische Bestimmung des Minimums der Lagrangefunktion $L$ hinsichtlich $w$
und $w_0$ entspricht der Bestimmung der partiellen Ableitungen von $L$ hinsichtlich
$w$ und $w_0$, Nullsetzen, und lösen. Wir definieren
\begin{equation}
\bar{w} := \argmin_{w \in \mathbb{R}^m} L(w,w_0,\lambda)
\mbox{ and }
\bar{w_0} := \argmin_{w_0 \in \mathbb{R}} L(w,w_0,\lambda).
\end{equation}


# SVM Training als quadratisches Programmierungsproblem

\footnotesize
\underline{Beweis (fortgeführt)}
\vspace{2mm}

Für die Minimierung von $L$ hinsichtlich $w$ ergibt sich
\begin{align}
\begin{split}
\nabla_w L(w,w_0,\lambda)
& = \nabla_w
\left(\frac{1}{2}w^Tw - \sum_{i=1}^n \lambda_i(y^{(i)}(w^Tx^{(i)} + w_0) - 1)\right) \\
& = w -
\nabla_w \left(\sum_{i=1}^n
\lambda_iy^{(i)}w^T x^{(i)} +
\lambda_iy^{(i)}w_0 -
\lambda_i\right) \\
& = w - \sum_{i=1}^n \lambda_iy^{(i)} x^{(i)}
\end{split}
\end{align}
und somit
\begin{equation}
\bar{w} = \sum_{i=1}^n \lambda_iy^{(i)} x^{(i)}.
\end{equation}


# SVM Training als quadratisches Programmierungsproblem

\footnotesize
\underline{Beweis (fortgeführt)}
\vspace{2mm}

In ähnlicher Weise ergibt sich für die Minimierung von $L$ bezüglich $w_0$
\begin{align}
\begin{split}
\nabla_{w_0} L(w,w_0,\lambda)
& = \nabla_{w_0}
\left(\frac{1}{2}w^Tw - \sum_{i=1}^n \lambda_i(y^{(i)}(w^Tx^{(i)} + w_0) - 1)\right) \\
& =
\nabla_{w_0} \left(\sum_{i=1}^n
\lambda_iy^{(i)}w^T x^{(i)} +
\lambda_iy^{(i)}w_0 -
\lambda_i\right) \\
& = - \sum_{i=1}^n \lambda_iy^{(i)}.
\end{split}
\end{align}
An der Minimalstelle von $L$ hinsichtlich $w_0$ ergibt sich also
\begin{equation}
- \sum_{i=1}^n \lambda_iy^{(i)} = 0.
\end{equation}
Man beachte, dass wir hier lediglich die Bedingung $-\sum_{i=1}^n \lambda_iy^{(i)} = 0$
an der Minimalstelle von $L$ hinsichtlich $w_0$ erhalten, nicht aber die Minimalstelle $\bar{w}_0$ selbst.


# SVM Training als quadratisches Programmierungsproblem

\footnotesize
\underline{Beweis (fortgeführt)}

Für die Zielfunktion des dualen Problems ergibt sich also
\begin{tiny}
\begin{align*}
\begin{split}
& q(\lambda) \\
& = \min_{w,w_0} L(w,w_0,\lambda) \\
& = L(\bar{w},\bar{w}_0,\lambda) \\
& = \frac{1}{2}\bar{w}^T\bar{w} - \sum_{i=1}^n \lambda_i \left(y^{(i)}(\bar{w}^Tx^{(i)} + \bar{w}_0) - 1 \right) \\
& = \frac{1}{2}\left(\sum_{i=1}^n \lambda_iy^{(i)} x^{(i)} \right)^T \left(\sum_{j=1}^n \lambda_iy^{(j)} x^{(j)} \right)
 - \sum_{i=1}^n \lambda_i \left(y^{(i)}\left(\left(\sum_{j=1}^n \lambda_jy^{(j)} x^{(j)} \right)^T x^{(i)} + \bar{w}_0 \right) - 1 \right) \\
& = \frac{1}{2}\sum_{i=1}^n \sum_{j = 1}^n  \lambda_i \lambda_j y^{(i)}y^{(j)} x^{(i)^T} x^{(j)}
- \sum_{i=1}^n \lambda_i y^{(i)}\left(\left(\sum_{j=1}^n \lambda_jy^{(j)} x^{(j)} \right)^T x^{(i)} + \bar{w}_0 \right) + \sum_{i=1}^n \lambda_i \\
\end{split}
\end{align*}
\end{tiny}

# SVM Training als quadratisches Programmierungsproblem
\footnotesize
\underline{Beweis (fortgeführt)}
\vspace{2mm}

und weiterhin

\begin{tiny}
\begin{align*}
\begin{split}
q(\lambda)
& = \frac{1}{2}\sum_{i=1}^n \sum_{j = 1}^n  \lambda_i \lambda_j y^{(i)}y^{(j)} x^{(i)^T} x^{(j)}
- \sum_{i=1}^n \lambda_i \lambda_j y^{(i)} y^{(j)}  x^{(i)^T}  x^{(j)} - \bar{w}_0\sum_{i=1}^n \lambda_i y^{(i)}  + \sum_{i=1}^n \lambda_i \\
& = \sum_{i=1}^n \lambda_i
- \frac{1}{2} \sum_{i=1}^n \sum_{j = 1}^n  \lambda_i \lambda_j y^{(i)}y^{(j)} x^{(i)^T} x^{(j)}
- \bar{w}_0\sum_{i=1}^n \lambda_i y^{(i)} \\
& = \sum_{i=1}^n \lambda_i
- \frac{1}{2} \sum_{i=1}^n \sum_{j = 1}^n  \lambda_i \lambda_j y^{(i)}y^{(j)} x^{(i)^T} x^{(j)}.
\end{split}
\end{align*}
\end{tiny}
Hierbei folgt die letzte Gleichung mit der Tatsache, dass an der Stelle $\bar{w}_0$
gilt, dass $\sum_{i=1}^n \lambda_i y^{(i)} = 0$.

# SVM Training als quadratisches Programmierungsproblem

\footnotesize
\underline{Beweis (fortgeführt)}
\vspace{2mm}

Wir haben also gezeigt, dass die Zielfunktion des dualen Problems des Maximum
Margin SVM Trainingsproblems von der Form
\begin{equation}
q : \mathbb{R}^n \to \mathbb{R},
\lambda \to q(\lambda)
= \sum_{i=1}^n \lambda_i
- \frac{1}{2} \sum_{i=1}^n \sum_{j = 1}^n  \lambda_i \lambda_j y^{(i)}y^{(j)} x^{(i)^T} x^{(j)}.
\end{equation}
ist.

\vspace{2mm}

\noindent (3) Formulierung des dualen Problems
\vspace{3mm}

\footnotesize
Das duale Problem zum Maximum Margin SVM Trainingsproblem ergibt sich also zu
\begin{equation}
\max_{\lambda \in \mathbb{R}} q(\lambda)
= \sum_{i=1}^n \lambda_i
- \frac{1}{2} \sum_{i=1}^n \sum_{j = 1}^n  \lambda_i \lambda_j y^{(i)}y^{(j)} x^{(i)^T} x^{(j)}
\end{equation}
unter den Nebenbedingunge
\begin{equation}
\lambda_i \ge 0, i = 1,...,n \mbox{ and } \sum_{i = 1}^n \lambda_i y^{(i)} = 0,
\end{equation}
wobei die letzte Nebenbedingung das Minimum der Lagrangefunktion hinsichtlich
$w_0$ sicherstellt.


# SVM Training als quadratisches Programmierungsproblem

\footnotesize
\underline{Beweis (fortgeführt)}
\vspace{2mm}

Lösen des dualen Problems mithilfe eines Standardalgorithmus ergibt einen Vektor
optimaler Lagrangemultiplikatoren
\begin{equation}
\bar{\lambda}
= \argmax_{\lambda \in \mathbb{R}^n} q(\lambda)
= \argmax_{\lambda \in \mathbb{R}^n} L(\bar{w}, \bar{w}_0, \lambda).
\end{equation}
Basierend auf der Minimierung von $L$ hinsichtlich von $w$ ergibt sich also
\begin{equation}
\bar{w} = \sum_{i=1}^n \bar{\lambda}_i y^{(i)}x^{(i)}.
\end{equation}
Schließlich ergibt sich für den optimalen Biasparameter $\bar{w}_0$ zunächst mit
den KKT Bedingungen, dass für alle $\hat{\lambda}_i > 0, i = 1,...,n$ gilt, dass
\begin{align}
\begin{split}
y^{(i)}(\bar{w}^T x^{(i)} + w_0) - 1 & = 0 							\\
\Leftrightarrow y^{(i)}(\bar{w}^T x^{(i)} + w_0) & = 1 				\\
\Leftrightarrow y^{(i)}y^{(i)}(\bar{w}^T x^{(i)} + w_0) & = y^{(i)}	\\
\Leftrightarrow \bar{w}^T x^{(i)} + w_0 & = y^{(i)}.
\end{split}
\end{align}


# SVM Training als quadratisches Programmierungsproblem

\footnotesize
\underline{Beweis (fortgeführt)}

Dies impliziert, erstens, dass alle $x^{(i)}$ mit $\bar{\lambda}_i > 0$ Support
Vektoren sind, weil ihre Distanz zur optimalen Hyperebene gleich 1 ist, und zweitens, dass
\begin{align}
\sum_{i = 1}^n \bar{w}^T x^{(i)} + n w_0 = \sum_{i = 1}^n y^{(i)}
\Leftrightarrow
w_0  = \frac{1}{n} \sum_{i = 1}^n \left(y^{(i)} -  \bar{w}^T x^{(i)}\right).
\end{align}

\noindent (4) Standardform eines QP Problems
\vspace{1mm}

\footnotesize
Die Äquivalenzen
\begin{align}
\begin{split}
\sum_{i=1}^n \sum_{j = 1}^n  \lambda_i \lambda_j y^{(i)}y^{(j)} x^{(i)^T} x^{(j)}
\Leftrightarrow \lambda^T yy^TK \lambda
& \Leftrightarrow \lambda^T P \lambda  	\\
\sum_{i=1}^n \lambda_i  \Leftrightarrow 1_n^T \lambda  & \Leftrightarrow  q^T \lambda 						\\
\lambda \ge 0  \Leftrightarrow I_n \lambda + 0_n \ge 0_n  & \Leftrightarrow - G\lambda + h \le 0_n 								\\
\sum_{i=1}^n \lambda_i y^{(i)} = 0 \Leftrightarrow y^T\lambda = 0 & \Leftrightarrow A\lambda = b
\end{split}
\end{align}
ergeben sich direkt mit den Regeln der Matrixmultiplikation.

# {.plain}
\setstretch{2.5}
\large

Geometrie linearer Diskriminanzfunktionen

Support Vektor Maschinen Training

SVM Training als quadratisches Optimierungsproblem

**Kernelisierung der Maximum Margin SVM**

Selbstkontrollfragen

# Kernelisierung der Maximum Margin SVM

\small
Kernelmethoden basieren auf dem dualen Problem des Maximum Margin SVM Trainingproblems.

Die zentrale Einsicht ist dabei, dass die Zielfunktion des dualen SVM Trainingproblems
\begin{equation}
q(\lambda) := \sum_{i=1}^n \lambda_i - \frac{1}{2} \sum_{i = 1}^n \sum_{j = 1}^n \lambda_i\lambda_j y^{(i)} y^{(j)} x^{(i)^T }x^{(j)}
\end{equation}
lediglich von den Skalarprodukten der Featurevektoren
\begin{equation}
x^{(i)^T }x^{(j)} \mbox{ für } i,j = 1,...,n.
\end{equation}
abhängt.

Die Projektion der Featurevektoren in einen "hochdimensionalen Featureraum",
in welchem auf lineare Separabilität gehofft wird, benötigt also nur
die Auswertung von Skalarprodukten.

Skalarprodukte in den Projektionsräumen werden *Kernel* genannt.

# {.plain}
\setstretch{2.5}
\large

Geometrie linearer Diskriminanzfunktionen

Support Vektor Maschinen Training

SVM Training als quadratisches Optimierungsproblem

Kernelisierung der Maximum Margin SVM

**Selbstkontrollfragen**

# Selbstkontrollfragen
\footnotesize
\setstretch{1.3}
\begin{enumerate}
\justifying
\itemsep0mm
\item Wie unterscheiden sich binäre Klassifikationsdatensätze für Support Vektor Maschinen
von binären Klassifikationsdatensätzen für Lineare Diskriminanzanalyse und Logistische Regression?
\item Definieren Sie den Begriff der linearen Diskriminanzfunktion.
\item Definieren Sie in Bezug zum Begriff der linearen Diskriminanzfunktion  die Begriffe der Entscheidungsgrenze, der Hyperebene und der Entscheidungsregion.
\item Geben Sie das Theorem zur Geometrie linearer Diskriminanzfunktionen wieder.
\item Erläutern Sie die Bedeutung des Theorems zur Geometrie linearer Diskriminanzfunktionen bei der Bestimmung von Hyperebenen.
\item Definieren Sie den Begriff des Hyperebenenmargins.
\item Definieren Sie den Begriff des Support Vektors.
\item Definieren Sie den Begriff der kanonischen Hyperebene.
\item Definieren Sie den Begriff des linear separierbaren Trainingsdatensatzes.
\item Definieren und erläutern Sie das Optimierungsproblem zur Maximum Margin Klassifikation bei SVMs.
\item Definieren und erläutern Sie das Optimierungsproblem zur Soft Margin Klassifikation bei SVMs.
\item Lesen Sie den Datensatz \href{http://www3.hogrefe.de/fileadmin/redakteure/hogrefe_de/Psychlehrbuchplus/Multivariate_Verfahren_2Aufl/Diskriminanzanalyse/Studienerfolg.sav}{studienerfolg.sav} 
mit R ein und bestimmen Sie den Trainingsdatenprädiktionsfehler nach Trainieren einer Support Vektor Maschine mithilfe des R Pakets e1071
zur prädiktiven Modellierung des Studienerfolgs (gut, ungenügend) basierend auf (1) den Intelligenztestdaten,
(2) den Intelligenz- und Mathematiktestdaten und (3) den Intelligenztest-, Mathematiktest-, und Gewissenhaftigkeitsdaten.
\end{enumerate}

# References
\footnotesize
