% Options for packages loaded elsewhere
\PassOptionsToPackage{unicode}{hyperref}
\PassOptionsToPackage{hyphens}{url}
%
\documentclass[
  8pt,
  ignorenonframetext,
]{beamer}
\usepackage{pgfpages}
\setbeamertemplate{caption}[numbered]
\setbeamertemplate{caption label separator}{: }
\setbeamercolor{caption name}{fg=normal text.fg}
\beamertemplatenavigationsymbolsempty
% Prevent slide breaks in the middle of a paragraph
\widowpenalties 1 10000
\raggedbottom
\setbeamertemplate{part page}{
  \centering
  \begin{beamercolorbox}[sep=16pt,center]{part title}
    \usebeamerfont{part title}\insertpart\par
  \end{beamercolorbox}
}
\setbeamertemplate{section page}{
  \centering
  \begin{beamercolorbox}[sep=12pt,center]{part title}
    \usebeamerfont{section title}\insertsection\par
  \end{beamercolorbox}
}
\setbeamertemplate{subsection page}{
  \centering
  \begin{beamercolorbox}[sep=8pt,center]{part title}
    \usebeamerfont{subsection title}\insertsubsection\par
  \end{beamercolorbox}
}
\AtBeginPart{
  \frame{\partpage}
}
\AtBeginSection{
  \ifbibliography
  \else
    \frame{\sectionpage}
  \fi
}
\AtBeginSubsection{
  \frame{\subsectionpage}
}
\usepackage{amsmath,amssymb}
\usepackage{lmodern}
\usepackage{iftex}
\ifPDFTeX
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{textcomp} % provide euro and other symbols
\else % if luatex or xetex
  \usepackage{unicode-math}
  \defaultfontfeatures{Scale=MatchLowercase}
  \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
\fi
% Use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
\IfFileExists{microtype.sty}{% use microtype if available
  \usepackage[]{microtype}
  \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\makeatletter
\@ifundefined{KOMAClassName}{% if non-KOMA class
  \IfFileExists{parskip.sty}{%
    \usepackage{parskip}
  }{% else
    \setlength{\parindent}{0pt}
    \setlength{\parskip}{6pt plus 2pt minus 1pt}}
}{% if KOMA class
  \KOMAoptions{parskip=half}}
\makeatother
\usepackage{xcolor}
\newif\ifbibliography
\usepackage{color}
\usepackage{fancyvrb}
\newcommand{\VerbBar}{|}
\newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
\DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
% Add ',fontsize=\small' for more characters per line
\usepackage{framed}
\definecolor{shadecolor}{RGB}{248,248,248}
\newenvironment{Shaded}{\begin{snugshade}}{\end{snugshade}}
\newcommand{\AlertTok}[1]{\textcolor[rgb]{0.94,0.16,0.16}{#1}}
\newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.77,0.63,0.00}{#1}}
\newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.00,0.00,0.81}{#1}}
\newcommand{\BuiltInTok}[1]{#1}
\newcommand{\CharTok}[1]{\textcolor[rgb]{0.31,0.60,0.02}{#1}}
\newcommand{\CommentTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textit{#1}}}
\newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.00,0.00,0.00}{#1}}
\newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.13,0.29,0.53}{\textbf{#1}}}
\newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.13,0.29,0.53}{#1}}
\newcommand{\DecValTok}[1]{\textcolor[rgb]{0.00,0.00,0.81}{#1}}
\newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\newcommand{\ErrorTok}[1]{\textcolor[rgb]{0.64,0.00,0.00}{\textbf{#1}}}
\newcommand{\ExtensionTok}[1]{#1}
\newcommand{\FloatTok}[1]{\textcolor[rgb]{0.00,0.00,0.81}{#1}}
\newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.00,0.00,0.00}{#1}}
\newcommand{\ImportTok}[1]{#1}
\newcommand{\InformationTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.13,0.29,0.53}{\textbf{#1}}}
\newcommand{\NormalTok}[1]{#1}
\newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.81,0.36,0.00}{\textbf{#1}}}
\newcommand{\OtherTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{#1}}
\newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textit{#1}}}
\newcommand{\RegionMarkerTok}[1]{#1}
\newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.00,0.00,0.00}{#1}}
\newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.31,0.60,0.02}{#1}}
\newcommand{\StringTok}[1]{\textcolor[rgb]{0.31,0.60,0.02}{#1}}
\newcommand{\VariableTok}[1]{\textcolor[rgb]{0.00,0.00,0.00}{#1}}
\newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.31,0.60,0.02}{#1}}
\newcommand{\WarningTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\usepackage{longtable,booktabs,array}
\usepackage{calc} % for calculating minipage widths
\usepackage{caption}
% Make caption package work with longtable
\makeatletter
\def\fnum@table{\tablename~\thetable}
\makeatother
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{-\maxdimen} % remove section numbering
\newlength{\cslhangindent}
\setlength{\cslhangindent}{1.5em}
\newlength{\csllabelwidth}
\setlength{\csllabelwidth}{3em}
\newlength{\cslentryspacingunit} % times entry-spacing
\setlength{\cslentryspacingunit}{\parskip}
\newenvironment{CSLReferences}[2] % #1 hanging-ident, #2 entry spacing
 {% don't indent paragraphs
  \setlength{\parindent}{0pt}
  % turn on hanging indent if param 1 is 1
  \ifodd #1
  \let\oldpar\par
  \def\par{\hangindent=\cslhangindent\oldpar}
  \fi
  % set entry spacing
  \setlength{\parskip}{#2\cslentryspacingunit}
 }%
 {}
\usepackage{calc}
\newcommand{\CSLBlock}[1]{#1\hfill\break}
\newcommand{\CSLLeftMargin}[1]{\parbox[t]{\csllabelwidth}{#1}}
\newcommand{\CSLRightInline}[1]{\parbox[t]{\linewidth - \csllabelwidth}{#1}\break}
\newcommand{\CSLIndent}[1]{\hspace{\cslhangindent}#1}
% type setting
% ------------------------------------------------------------------------------
\usepackage[german]{babel}     

% fonts
% ------------------------------------------------------------------------------
\usefonttheme{professionalfonts}

% slide title and horizontal line
% ------------------------------------------------------------------------------
\setbeamertemplate{frametitle}{%
    \vskip-30pt \color{black}\large%
    \begin{minipage}[b][23pt]{120mm}%
    \flushleft\insertframetitle%
    \end{minipage}%
}

\setbeamertemplate{headline}										
{
\vskip10pt\hfill\hspace{3.5mm} 										 
\vskip15pt\color{black}\rule{\textwidth}{0.4pt} 					 
}

% slide number
% ---------------------------------------------------------------
\setbeamertemplate{navigation symbols}{}
\setbeamertemplate{footline}
{
\vskip5pt
\vskip2pt
\makebox[123mm]{\hspace{7.5mm}
\hfill Multivariate Datenanalyse $\vert$ 
\copyright $ $ 2022 Dirk Ostwald CC BY-NC-SA 4.0 $\vert$ 
Folie \insertframenumber}
\vskip4pt
}

% block color scheme
% ------------------------------------------------------------------------------
% colors
\definecolor{white}{RGB}{255,255,255}
\definecolor{grey}{RGB}{235,235,235}
\definecolor{lightgrey}{RGB}{245,245,245}
\definecolor{LightBlue}{RGB}{220,220,255}
\definecolor{darkblue}{RGB}{51, 51, 153}

% definitions and theorems
\setbeamercolor{block title}{fg = black, bg = grey}
\setbeamercolor{block body}{fg = black, bg = lightgrey}

% general line spacing 
% ------------------------------------------------------------------------------
\linespread{1.3}

% local line spacing
% ------------------------------------------------------------------------------
\usepackage{setspace}

% colors
% -----------------------------------------------------------------------------
\usepackage{color}

% justified text
% ------------------------------------------------------------------------------
\usepackage{ragged2e}
\usepackage{etoolbox}
\apptocmd{\frame}{}{\justifying}{}

% bullet point lists
% -----------------------------------------------------------------------------
\setbeamertemplate{itemize item}[circle]
\setbeamertemplate{itemize subitem}[circle]
\setbeamertemplate{itemize subsubitem}[circle]
\setbeamercolor{itemize item}{fg = black}
\setbeamercolor{itemize subitem}{fg = black}
\setbeamercolor{itemize subsubitem}{fg = black}
\setbeamercolor{enumerate item}{fg = black}
\setbeamercolor{enumerate subitem}{fg = black}
\setbeamercolor{enumerate subsubitem}{fg = black}
\setbeamerfont{itemize/enumerate body}{}
\setbeamerfont{itemize/enumerate subbody}{size = \normalsize}
\setbeamerfont{itemize/enumerate subsubbody}{size = \normalsize}

% color links
% ------------------------------------------------------------------------------
\usepackage{hyperref}
\definecolor{urls}{RGB}{204,0,0}
\hypersetup{colorlinks, citecolor = darkblue, urlcolor = urls}


% additional math commands
% ------------------------------------------------------------------------------
\usepackage{bm}                                         % bold math symbols
\newcommand{\niton}{\not\owns}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}

% text highlighting
% ------------------------------------------------------------------------------
\usepackage{soul}
\makeatletter
\let\HL\hl
\renewcommand\hl{%
  \let\set@color\beamerorig@set@color
  \let\reset@color\beamerorig@reset@color
  \HL}
\makeatother

% equation highlighting
% -----------------------------------------------------------------------------
\newcommand{\highlight}[2][yellow]{\mathchoice%
  {\colorbox{#1}{$\displaystyle#2$}}%
  {\colorbox{#1}{$\textstyle#2$}}%
  {\colorbox{#1}{$\scriptstyle#2$}}%
  {\colorbox{#1}{$\scriptscriptstyle#2$}}}%
  
\ifLuaTeX
  \usepackage{selnolig}  % disable illegal ligatures
\fi
\IfFileExists{bookmark.sty}{\usepackage{bookmark}}{\usepackage{hyperref}}
\IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
\urlstyle{same} % disable monospaced font for URLs
\hypersetup{
  hidelinks,
  pdfcreator={LaTeX via pandoc}}

\author{}
\date{\vspace{-2.5em}}

\begin{document}

\begin{frame}[plain]{}
\protect\hypertarget{section}{}
\center

\begin{center}\includegraphics[width=0.2\linewidth]{8_Abbildungen/mvda_8_otto} \end{center}

\vspace{2mm}

\Huge

Multivariate Datenanalyse \vspace{6mm}

\Large

MSc Psychologie WiSe 2021/22

\vspace{6mm}
\large

Prof.~Dr.~Dirk Ostwald
\end{frame}

\begin{frame}[plain]{}
\protect\hypertarget{section-1}{}
\vfill
\center
\huge

\textcolor{black}{(8) Support Vektor Maschinen} \vfill
\end{frame}

\begin{frame}{}
\protect\hypertarget{section-2}{}
Struktur der Prädiktiven Modellierung

\begin{minipage}{.6\textwidth}

\begin{center}\includegraphics[width=0.8\linewidth]{8_Abbildungen/mvda_8_prädiktive_modellierung_1} \end{center}
\end{minipage}
\begin{minipage}{.4\textwidth}

\begin{center}\includegraphics[width=0.9\linewidth]{8_Abbildungen/mvda_8_prädiktive_modellierung_2} \end{center}
\end{minipage}

\flushright
\tiny

nach Dwyer, Falkai, and Koutsouleris (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}
\end{frame}

\begin{frame}{}
\protect\hypertarget{section-3}{}
\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

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

\begin{frame}{}
\protect\hypertarget{section-4}{}
Welche lineare Diskriminanzfunktion (Hyperebene) soll hier man wählen ?
\vspace{5mm}

\begin{center}\includegraphics[width=0.5\linewidth]{8_Abbildungen/mvda_8_hyperebene} \end{center}
\end{frame}

\begin{frame}{}
\protect\hypertarget{section-5}{}
Nach der Theorie der Maximum Margin Support Vektor Maschinen diese:
\vspace{5mm}

\begin{center}\includegraphics[width=0.5\linewidth]{8_Abbildungen/mvda_8_hyperebene_svm} \end{center}
\end{frame}

\begin{frame}[plain]{}
\protect\hypertarget{section-6}{}
\vfill
\setstretch{2.5}
\large

Geometrie linearer Diskriminanzfunktionen

Support Vektor Maschinen Training

SVM Training als quadratisches Optimierungsproblem

Kernelisierung der Maximum Margin SVM

Selbstkontrollfragen \vfill
\end{frame}

\begin{frame}[plain]{}
\protect\hypertarget{section-7}{}
\setstretch{2.5}
\large

\textbf{Geometrie linearer Diskriminanzfunktionen}

Support Vektor Maschinen Training

SVM Training als quadratisches Optimierungsproblem

Kernelisierung der Maximum Margin SVM

Selbstkontrollfragen
\end{frame}

\begin{frame}{Geometrie linearer Diskriminanzfunktionen}
\protect\hypertarget{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}
\end{frame}

\begin{frame}{Geometrie linearer Diskriminanzfunktionen}
\protect\hypertarget{geometrie-linearer-diskriminanzfunktionen-1}{}
\vspace{3mm}

\begin{center}\includegraphics[width=0.9\linewidth]{8_Abbildungen/mvda_8_ldf} \end{center}

\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}
\end{frame}

\begin{frame}{Geometrie linearer Diskriminanzfunktionen}
\protect\hypertarget{geometrie-linearer-diskriminanzfunktionen-2}{}
\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

\begin{itemize}
\tightlist
\item
  \(w\) bestimmt die Orientierung der Hyperebene im Featurevektorenraum.
\item
  \(w_0\) bestimmt die Lage der Hyperebene im Featurevektorenraum.
\end{itemize}
\end{frame}

\begin{frame}{Geometrie linearer Diskriminanzfunktionen}
\protect\hypertarget{geometrie-linearer-diskriminanzfunktionen-3}{}
\begin{center}\includegraphics[width=0.85\linewidth]{8_Abbildungen/mvda_8_ldf_geometrie} \end{center}
\end{frame}

\begin{frame}{Geometrie linearer Diskriminanzfunktionen}
\protect\hypertarget{geometrie-linearer-diskriminanzfunktionen-4}{}
\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.
\end{frame}

\begin{frame}{Geometrie linearer Diskriminanzfunktionen}
\protect\hypertarget{geometrie-linearer-diskriminanzfunktionen-5}{}
\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\)
\end{frame}

\begin{frame}{Geometrie linearer Diskriminanzfunktionen}
\protect\hypertarget{geometrie-linearer-diskriminanzfunktionen-6}{}
\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}
\end{frame}

\begin{frame}{Geometrie linearer Diskriminanzfunktionen}
\protect\hypertarget{geometrie-linearer-diskriminanzfunktionen-7}{}
\vspace{3mm}

Hyperebenenmargin und Support Vektoren

\begin{center}\includegraphics[width=0.65\linewidth]{8_Abbildungen/mvda_8_margin} \end{center}
\end{frame}

\begin{frame}{Geometrie linearer Diskriminanzfunktionen}
\protect\hypertarget{geometrie-linearer-diskriminanzfunktionen-8}{}
\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}
\end{frame}

\begin{frame}[plain]{}
\protect\hypertarget{section-8}{}
\setstretch{3}
\large

Geometrie linearer Diskriminanzfunktionen

\textbf{Support Vektor Maschinen Training}

SVM Training als quadratisches Optimierungsproblem

Kernelisierung der Maximum Margin SVM
\end{frame}

\begin{frame}{Support Vektor Maschinen Training}
\protect\hypertarget{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}
\end{frame}

\begin{frame}{Support Vektor Maschinen Training}
\protect\hypertarget{support-vektor-maschinen-training-1}{}
\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}
\end{frame}

\begin{frame}{Support Vektor Maschinen Training}
\protect\hypertarget{support-vektor-maschinen-training-2}{}
\vspace{3mm}

Maximum Margin-Klassifikation

\begin{center}\includegraphics[width=0.65\linewidth]{8_Abbildungen/mvda_8_maximum_margin} \end{center}
\end{frame}

\begin{frame}{Support Vektor Maschinen Training}
\protect\hypertarget{support-vektor-maschinen-training-3}{}
\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}
\end{frame}

\begin{frame}{Support Vektor Maschinen Training}
\protect\hypertarget{support-vektor-maschinen-training-4}{}
\vspace{3mm}

Soft Margin-Klassifikation

\begin{center}\includegraphics[width=0.8\linewidth]{8_Abbildungen/mvda_8_soft_margin} \end{center}
\end{frame}

\begin{frame}[fragile]{Support Vektor Maschinen Training}
\protect\hypertarget{support-vektor-maschinen-training-5}{}
Soft Margin SVM Training mit R Paket \texttt{e1071} \vspace{2mm}

\footnotesize
\setstretch{1.2}

\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{\# Einlesen der Studienerfolgdaten und Fokus auf binäre Klassifikation}
\FunctionTok{library}\NormalTok{(foreign)}
\NormalTok{D         }\OtherTok{=} \FunctionTok{read.spss}\NormalTok{(}\FunctionTok{file.path}\NormalTok{(}\FunctionTok{getwd}\NormalTok{(), }\StringTok{"8\_Daten"}\NormalTok{, }\StringTok{"studienerfolg.sav"}\NormalTok{),}
                      \AttributeTok{to.data.frame =}\NormalTok{ T)}
\NormalTok{D         }\OtherTok{=}\NormalTok{ D[D[,}\DecValTok{1}\NormalTok{] }\SpecialCharTok{!=} \StringTok{"befriedigend"}\NormalTok{,]}

\CommentTok{\# SVM Training und Trainingsdatenprädiktion}
\FunctionTok{library}\NormalTok{(e1071)                                             }\CommentTok{\# SVM Paket}
\NormalTok{acc }\OtherTok{=} \FunctionTok{rep}\NormalTok{(}\ConstantTok{NaN}\NormalTok{,}\DecValTok{4}\NormalTok{)                                           }\CommentTok{\# Accuracyarray}
\ControlFlowTok{for}\NormalTok{(i }\ControlFlowTok{in} \DecValTok{1}\SpecialCharTok{:}\DecValTok{4}\NormalTok{)\{                                             }\CommentTok{\# Featuresetiteration}
\NormalTok{    x         }\OtherTok{=}\NormalTok{ D[,}\DecValTok{2}\SpecialCharTok{:}\NormalTok{(}\DecValTok{2}\SpecialCharTok{+}\NormalTok{i}\DecValTok{{-}1}\NormalTok{)]                              }\CommentTok{\# Featurevektoren}
\NormalTok{    y         }\OtherTok{=}\NormalTok{ D[,}\DecValTok{1}\NormalTok{]                                      }\CommentTok{\# Labelvariable}
\NormalTok{    svm.train }\OtherTok{=} \FunctionTok{svm}\NormalTok{(x,y, }\AttributeTok{kernel =} \StringTok{"linear"}\NormalTok{)                }\CommentTok{\# SVM Training}
\NormalTok{    svm.pred  }\OtherTok{=} \FunctionTok{predict}\NormalTok{(svm.train, x, }\AttributeTok{kernel =} \StringTok{"linear"}\NormalTok{)   }\CommentTok{\# Vorhersage der Trainingsdatenlabel}
\NormalTok{    acc[i]    }\OtherTok{=} \FunctionTok{mean}\NormalTok{(svm.pred }\SpecialCharTok{==}\NormalTok{ y)                        }\CommentTok{\# Trainingsdatenvorhersageaccuracy}
\NormalTok{\}}
\FunctionTok{print}\NormalTok{(acc)}
\end{Highlighting}
\end{Shaded}

\begin{verbatim}
> [1] 0.767 0.800 0.767 0.900
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Support Vektor Maschinen Training}
\protect\hypertarget{support-vektor-maschinen-training-6}{}
Soft Margin SVM Leave-One-Out Cross-Validation, \(m = 2\)

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

\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{\# Einlesen der Studienerfolgdaten und Fokus auf binäre Klassifikation}
\FunctionTok{library}\NormalTok{(foreign)}
\NormalTok{D         }\OtherTok{=} \FunctionTok{read.spss}\NormalTok{(}\FunctionTok{file.path}\NormalTok{(}\FunctionTok{getwd}\NormalTok{(), }\StringTok{"8\_Daten"}\NormalTok{, }\StringTok{"studienerfolg.sav"}\NormalTok{),}
                      \AttributeTok{to.data.frame =}\NormalTok{ T)}
\NormalTok{D         }\OtherTok{=}\NormalTok{ D[D[,}\DecValTok{1}\NormalTok{] }\SpecialCharTok{!=} \StringTok{"befriedigend"}\NormalTok{,]}
\NormalTok{K         }\OtherTok{=} \FunctionTok{nrow}\NormalTok{(D)}
\NormalTok{x         }\OtherTok{=}\NormalTok{ D[,}\DecValTok{2}\SpecialCharTok{:}\DecValTok{3}\NormalTok{]}
\NormalTok{y         }\OtherTok{=}\NormalTok{ D[,}\DecValTok{1}\NormalTok{]}

\CommentTok{\# K{-}fache Leave{-}One{-}Out Cross{-}Validation}
\FunctionTok{library}\NormalTok{(e1071)}
\NormalTok{correct   }\OtherTok{=} \FunctionTok{rep}\NormalTok{(}\ConstantTok{NaN}\NormalTok{,K)}
\NormalTok{h         }\OtherTok{=} \FunctionTok{rep}\NormalTok{(}\ConstantTok{NaN}\NormalTok{,K)}
\ControlFlowTok{for}\NormalTok{(k }\ControlFlowTok{in} \DecValTok{1}\SpecialCharTok{:}\NormalTok{K)\{}

    \CommentTok{\# Datensatzpartition}
\NormalTok{    x\_train       }\OtherTok{=}\NormalTok{ x[}\SpecialCharTok{{-}}\NormalTok{k,]}
\NormalTok{    y\_train       }\OtherTok{=}\NormalTok{ y[}\SpecialCharTok{{-}}\NormalTok{k]}
\NormalTok{    x\_test        }\OtherTok{=}\NormalTok{ x[k,]}
\NormalTok{    y\_test        }\OtherTok{=}\NormalTok{ y[k]}

    \CommentTok{\# Trainingsdatensatz{-}basiertes Parameterlernen}
\NormalTok{    svm.train     }\OtherTok{=} \FunctionTok{svm}\NormalTok{(x\_train,y\_train, }\AttributeTok{kernel =} \StringTok{"linear"}\NormalTok{)}

    \CommentTok{\# Testdatensatz{-}basierte Prädiktion}
\NormalTok{    svm.pred      }\OtherTok{=} \FunctionTok{predict}\NormalTok{(svm.train, x\_test, }\AttributeTok{kernel =} \StringTok{"linear"}\NormalTok{)}
\NormalTok{    h[k]          }\OtherTok{=} \FunctionTok{as.numeric}\NormalTok{(svm.pred)}
\NormalTok{    correct[k]    }\OtherTok{=}\NormalTok{ svm.pred }\SpecialCharTok{==}\NormalTok{ y\_test}
\NormalTok{\}}
\FunctionTok{cat}\NormalTok{(}\StringTok{"Accuracy: "}\NormalTok{, }\FunctionTok{mean}\NormalTok{(correct))}
\end{Highlighting}
\end{Shaded}
\end{frame}

\begin{frame}{Support Vektor Maschinen Training}
\protect\hypertarget{support-vektor-maschinen-training-7}{}
Soft Margin SVM Leave-One-Out Cross-Validation, \(m = 2\)

\tiny
\setstretch{0.8}

\begin{longtable}[]{@{}lrrrr@{}}
\toprule()
& x\_1 & x\_2 & y & h(x) \\
\midrule()
\endhead
1 & 54 & 44 & -1 & -1 \\
2 & 60 & 20 & -1 & -1 \\
3 & 67 & 36 & -1 & 1 \\
4 & 41 & 39 & -1 & -1 \\
5 & 66 & 57 & -1 & 1 \\
6 & 51 & 28 & -1 & -1 \\
7 & 51 & 46 & -1 & -1 \\
8 & 37 & 46 & -1 & -1 \\
9 & 57 & 54 & -1 & -1 \\
10 & 47 & 12 & -1 & -1 \\
11 & 50 & 67 & -1 & -1 \\
12 & 42 & 63 & -1 & -1 \\
13 & 60 & 64 & -1 & 1 \\
14 & 36 & 64 & -1 & -1 \\
15 & 60 & 71 & -1 & 1 \\
31 & 71 & 41 & 1 & 1 \\
32 & 65 & 28 & 1 & -1 \\
33 & 67 & 76 & 1 & 1 \\
34 & 68 & 54 & 1 & 1 \\
35 & 75 & 33 & 1 & 1 \\
36 & 71 & 82 & 1 & 1 \\
37 & 68 & 64 & 1 & 1 \\
38 & 63 & 72 & 1 & 1 \\
39 & 48 & 54 & 1 & -1 \\
40 & 53 & 86 & 1 & -1 \\
41 & 62 & 71 & 1 & 1 \\
42 & 69 & 25 & 1 & 1 \\
43 & 67 & 72 & 1 & 1 \\
44 & 74 & 92 & 1 & 1 \\
45 & 76 & 75 & 1 & 1 \\
\bottomrule()
\end{longtable}

\small

Prediction Accuracy = 0.77.
\end{frame}

\begin{frame}{Support Vektor Maschinen Training}
\protect\hypertarget{support-vektor-maschinen-training-8}{}
Leave-One-Out Cross-Validation, \(m = 3\)

\tiny
\setstretch{0.8}

\begin{longtable}[]{@{}lrrrrr@{}}
\toprule()
& x\_1 & x\_2 & x\_3 & y & h(x) \\
\midrule()
\endhead
1 & 54 & 44 & 31 & -1 & -1 \\
2 & 60 & 20 & 33 & -1 & -1 \\
3 & 67 & 36 & 26 & -1 & 1 \\
4 & 41 & 39 & 31 & -1 & -1 \\
5 & 66 & 57 & 34 & -1 & 1 \\
6 & 51 & 28 & 42 & -1 & -1 \\
7 & 51 & 46 & 34 & -1 & -1 \\
8 & 37 & 46 & 36 & -1 & -1 \\
9 & 57 & 54 & 28 & -1 & -1 \\
10 & 47 & 12 & 34 & -1 & -1 \\
11 & 50 & 67 & 27 & -1 & -1 \\
12 & 42 & 63 & 26 & -1 & -1 \\
13 & 60 & 64 & 29 & -1 & 1 \\
14 & 36 & 64 & 36 & -1 & -1 \\
15 & 60 & 71 & 42 & -1 & 1 \\
31 & 71 & 41 & 37 & 1 & 1 \\
32 & 65 & 28 & 33 & 1 & -1 \\
33 & 67 & 76 & 38 & 1 & 1 \\
34 & 68 & 54 & 34 & 1 & 1 \\
35 & 75 & 33 & 25 & 1 & 1 \\
36 & 71 & 82 & 32 & 1 & 1 \\
37 & 68 & 64 & 34 & 1 & 1 \\
38 & 63 & 72 & 32 & 1 & 1 \\
39 & 48 & 54 & 41 & 1 & -1 \\
40 & 53 & 86 & 27 & 1 & -1 \\
41 & 62 & 71 & 31 & 1 & 1 \\
42 & 69 & 25 & 32 & 1 & 1 \\
43 & 67 & 72 & 31 & 1 & 1 \\
44 & 74 & 92 & 35 & 1 & 1 \\
45 & 76 & 75 & 37 & 1 & 1 \\
\bottomrule()
\end{longtable}

\small

Prediction Accuracy = 0.77.
\end{frame}

\begin{frame}{Support Vektor Maschinen Training}
\protect\hypertarget{support-vektor-maschinen-training-9}{}
Soft Margin SVM Leave-One-Out Cross-Validation, \(m = 4\)

\tiny
\setstretch{0.8}

\begin{longtable}[]{@{}lrrrrrr@{}}
\toprule()
& x\_1 & x\_2 & x\_3 & x\_4 & y & h(x) \\
\midrule()
\endhead
1 & 54 & 44 & 31 & 60 & -1 & -1 \\
2 & 60 & 20 & 33 & 31 & -1 & -1 \\
3 & 67 & 36 & 26 & 54 & -1 & 1 \\
4 & 41 & 39 & 31 & 26 & -1 & -1 \\
5 & 66 & 57 & 34 & 56 & -1 & 1 \\
6 & 51 & 28 & 42 & 23 & -1 & -1 \\
7 & 51 & 46 & 34 & 40 & -1 & -1 \\
8 & 37 & 46 & 36 & 31 & -1 & -1 \\
9 & 57 & 54 & 28 & 49 & -1 & -1 \\
10 & 47 & 12 & 34 & 41 & -1 & -1 \\
11 & 50 & 67 & 27 & 53 & -1 & -1 \\
12 & 42 & 63 & 26 & 36 & -1 & -1 \\
13 & 60 & 64 & 29 & 40 & -1 & 1 \\
14 & 36 & 64 & 36 & 21 & -1 & -1 \\
15 & 60 & 71 & 42 & 40 & -1 & 1 \\
31 & 71 & 41 & 37 & 30 & 1 & 1 \\
32 & 65 & 28 & 33 & 38 & 1 & -1 \\
33 & 67 & 76 & 38 & 28 & 1 & 1 \\
34 & 68 & 54 & 34 & 53 & 1 & -1 \\
35 & 75 & 33 & 25 & 54 & 1 & -1 \\
36 & 71 & 82 & 32 & 49 & 1 & 1 \\
37 & 68 & 64 & 34 & 33 & 1 & 1 \\
38 & 63 & 72 & 32 & 36 & 1 & 1 \\
39 & 48 & 54 & 41 & 34 & 1 & -1 \\
40 & 53 & 86 & 27 & 35 & 1 & -1 \\
41 & 62 & 71 & 31 & 53 & 1 & -1 \\
42 & 69 & 25 & 32 & 25 & 1 & 1 \\
43 & 67 & 72 & 31 & 28 & 1 & 1 \\
44 & 74 & 92 & 35 & 50 & 1 & 1 \\
45 & 76 & 75 & 37 & 12 & 1 & 1 \\
\bottomrule()
\end{longtable}

\small

Prediction Accuracy = 0.60.
\end{frame}

\begin{frame}[plain]{}
\protect\hypertarget{section-9}{}
\setstretch{2.5}
\large

Geometrie linearer Diskriminanzfunktionen

Support Vektor Maschinen Training

\textbf{SVM Training als quadratisches Optimierungsproblem}

\textbf{Kernelisierung der Maximum Margin SVM}

Selbstkontrollfragen
\end{frame}

\begin{frame}{SVM Training als quadratisches Optimierungsproblem}
\protect\hypertarget{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 \emph{Kernel} genannt.
\end{frame}

\begin{frame}[plain]{}
\protect\hypertarget{section-10}{}
\setstretch{2.5}
\large

Geometrie linearer Diskriminanzfunktionen

Support Vektor Maschinen Training

\textbf{SVM Training als quadratisches Optimierungsproblem}

Kernelisierung der Maximum Margin SVM

Selbstkontrollfragen
\end{frame}

\begin{frame}[plain]{}
\protect\hypertarget{section-11}{}
\huge
\center
\vfill
\setstretch{3}

\textbf{Beginn Exkurs}

Grundlagen der

Optimierung mit Nebenbedingungen \vfill
\end{frame}

\begin{frame}{Grundlagen der Optimierung mit Nebenbedingungen}
\protect\hypertarget{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

\begin{itemize}
\tightlist
\item
  \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.
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Grundlagen der Optimierung mit Nebenbedingungen}
\protect\hypertarget{grundlagen-der-optimierung-mit-nebenbedingungen-1}{}
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

\begin{itemize}
\tightlist
\item
  Quadratische Programme sind Optimierungsprobleme mit Nebenbedingungen.
\item
  Parameterlernen bei Support Vektor Maschinen führt auf ein
  Quadratisches Programm.
\item
  Optimierungstoolboxen enhalten Funktionen zur Lösung Quadratischer
  Programme.
\item
  In R bietet sich das Paket \texttt{quadprog} an.
\end{itemize}
\end{frame}

\begin{frame}{Grundlagen der Optimierung mit Nebenbedingungen}
\protect\hypertarget{grundlagen-der-optimierung-mit-nebenbedingungen-2}{}
\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

\begin{itemize}
\tightlist
\item
  \justifying Die Lagrange Funktion und die Lagrange Multiplikatoren
  nehmen in den notwendigen Bedingungen der Optimierung mit
  Nebenbedingungen eine zentrale Rolle ein.
\end{itemize}
\end{frame}

\begin{frame}{Grundlagen der Optimierung mit Nebenbedingungen}
\protect\hypertarget{grundlagen-der-optimierung-mit-nebenbedingungen-3}{}
\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

\begin{itemize}
\tightlist
\item
  Die Bedingungen werden auch \textit{Karush-Kuhn-Tucker (KKT)}
  Bedingungen genannt.
\item
  Für einen Beweis und Reguläritätsbedingungen, siehe Nocedal and Wright
  (2006) Section 12.4.
\item
  Die letzte Bedingung impliziert
  \(\lambda_i^* > 0 \Rightarrow c_i(x^*) = 0\).
\end{itemize}
\end{frame}

\begin{frame}{Grundlagen der Optimierung mit Nebenbedingungen}
\protect\hypertarget{grundlagen-der-optimierung-mit-nebenbedingungen-4}{}
\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

\begin{itemize}
\tightlist
\item
  Duale Probleme sind manchmal einfacher zu lösen als die (primären)
  Ausgangsprobleme.
\item
  Duale Probleme sind für das Parameterlernen von Support Vektor
  Maschinen zentral.
\end{itemize}
\end{frame}

\begin{frame}{Grundlagen der Optimierung mit Nebenbedingungen}
\protect\hypertarget{grundlagen-der-optimierung-mit-nebenbedingungen-5}{}
\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

\begin{itemize}
\tightlist
\item
  \justifying Das Theorem besagt, dass der optimierte Wert des dualen
  Problems eine untere Grenze für den optimalen Wert der Zielfunktion
  des Ausgangsproblems ist.
\end{itemize}
\end{frame}

\begin{frame}{Grundlagen der Optimierung mit Nebenbedingungen}
\protect\hypertarget{grundlagen-der-optimierung-mit-nebenbedingungen-6}{}
\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

\begin{itemize}
\tightlist
\item
  Die optimalen Lagrange Multiplikatoren des Ausgangsproblems sind
  Lösungen des dualen Problems.
\item
  SVM Training als Quadratisches Programm benötigt das Konzept der
  starken Dualität.
\end{itemize}
\end{frame}

\begin{frame}{Grundlagen der Optimierung mit Nebenbedingungen}
\protect\hypertarget{grundlagen-der-optimierung-mit-nebenbedingungen-7}{}
\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\)
\end{frame}

\begin{frame}[plain]{}
\protect\hypertarget{section-12}{}
\huge
\center
\vfill
\setstretch{3}

\textbf{Ende Exkurs}

Grundlagen der

Optimierung mit Nebenbedingungen \vfill
\end{frame}

\begin{frame}{SVM Training als quadratisches Programmierungsproblem}
\protect\hypertarget{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}
\end{frame}

\begin{frame}{SVM Training als quadratisches Programmierungsproblem}
\protect\hypertarget{svm-training-als-quadratisches-programmierungsproblem-1}{}
\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

\begin{itemize}
\tightlist
\item
  Einerseits führt die QP Formulierung von Maximum Margin SVM Problem
  auf ein Standardproblem.
\item
  Andererseits motiviert die QP Formulierung des Maximum Margin SVM
  Problems auch Kernelmethoden
\end{itemize}
\end{frame}

\begin{frame}{SVM Training als quadratisches Programmierungsproblem}
\protect\hypertarget{svm-training-als-quadratisches-programmierungsproblem-2}{}
\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}
\end{frame}

\begin{frame}{SVM Training als quadratisches Programmierungsproblem}
\protect\hypertarget{svm-training-als-quadratisches-programmierungsproblem-3}{}
\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}
\end{frame}

\begin{frame}{SVM Training als quadratisches Programmierungsproblem}
\protect\hypertarget{svm-training-als-quadratisches-programmierungsproblem-4}{}
\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.
\end{frame}

\begin{frame}{SVM Training als quadratisches Programmierungsproblem}
\protect\hypertarget{svm-training-als-quadratisches-programmierungsproblem-5}{}
\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}
\end{frame}

\begin{frame}{SVM Training als quadratisches Programmierungsproblem}
\protect\hypertarget{svm-training-als-quadratisches-programmierungsproblem-6}{}
\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\).
\end{frame}

\begin{frame}{SVM Training als quadratisches Programmierungsproblem}
\protect\hypertarget{svm-training-als-quadratisches-programmierungsproblem-7}{}
\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.
\end{frame}

\begin{frame}{SVM Training als quadratisches Programmierungsproblem}
\protect\hypertarget{svm-training-als-quadratisches-programmierungsproblem-8}{}
\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}
\end{frame}

\begin{frame}{SVM Training als quadratisches Programmierungsproblem}
\protect\hypertarget{svm-training-als-quadratisches-programmierungsproblem-9}{}
\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.
\end{frame}

\begin{frame}[plain]{}
\protect\hypertarget{section-13}{}
\setstretch{2.5}
\large

Geometrie linearer Diskriminanzfunktionen

Support Vektor Maschinen Training

SVM Training als quadratisches Optimierungsproblem

\textbf{Kernelisierung der Maximum Margin SVM}

Selbstkontrollfragen
\end{frame}

\begin{frame}{Kernelisierung der Maximum Margin SVM}
\protect\hypertarget{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 \emph{Kernel} genannt.
\end{frame}

\begin{frame}[plain]{}
\protect\hypertarget{section-14}{}
\setstretch{2.5}
\large

Geometrie linearer Diskriminanzfunktionen

Support Vektor Maschinen Training

SVM Training als quadratisches Optimierungsproblem

Kernelisierung der Maximum Margin SVM

\textbf{Selbstkontrollfragen}
\end{frame}

\begin{frame}{Selbstkontrollfragen}
\protect\hypertarget{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}
\end{frame}

\begin{frame}{References}
\protect\hypertarget{references}{}
\footnotesize

\hypertarget{refs}{}
\begin{CSLReferences}{1}{0}
\leavevmode\vadjust pre{\hypertarget{ref-dwyer_2018}{}}%
Dwyer, Dominic B., Peter Falkai, and Nikolaos Koutsouleris. 2018.
{``Machine {Learning Approaches} for {Clinical Psychology} and
{Psychiatry}.''} \emph{Annual Review of Clinical Psychology} 14 (1):
91--118. \url{https://doi.org/10.1146/annurev-clinpsy-032816-045037}.

\leavevmode\vadjust pre{\hypertarget{ref-nocedal_2006}{}}%
Nocedal, Jorge, and Stephen J. Wright. 2006. \emph{Numerical
Optimization}. 2nd ed. Springer Series in Operations Research. {New
York}: {Springer}.

\end{CSLReferences}
\end{frame}

\end{document}
