Kurs:Maschinelles Lernen/Klassifikation mittels Support Vector Machines

Vorherige Seite: K3 - Klassifikation mittels Gradientenabstieg
Nächste Seite : K4 - Grundidee der Neuronalen Netze

Grundidee

Die Klassifikation mittels Gradientenabstieg sucht nach einer Lösung, die den Grundraum (Vektorraum) $V$ in Klassen zerlegt. Es lässt sich allerdings auch die Frage stellen, ob die gefundene Lösung die beste Klassifikationsmöglichkeit für die Trainingsdaten ist.

Optimierung und Klassifikation

Um dieser Frage nachzugehen, kann die Priorität der Optimierung geändert werden. Statt nach einer Lösung zu suchen, die vollständig und konsistent klassifiziert und das empirische Risiko minimiert, kann nach einer Lösung gesucht werden, die den Abstand zwischen den beiden Klassen maximiert und vollständig und konsistent klassifiziert.

Binäre Klassifikation

Bei einer binären Klassifikation gibt es genau 2 Klassen und Trainingsdaten $x^{(i)}\in \mathbb {R} ^{n}$ werden genau einer Klasse $y^{(i)}\in Y:=\{-1,+1\}$ zugeordnet.

Hyperebene zur Trennung der Klassen

Nach Möglichkeit soll bei dieser binären Klassifikation eine $n-1$ -dimensionale Hyperebene gefunden werden, wobei die Hyperebene den Grundraum $\mathbb {R} ^{n}$ in zwei Halbräume $H_{+}$ $H_{-}$ zerlegt. Die Hyperebene trennt die beiden Klassen vollständig, wenn für

$x^{(i)}\in \mathbb {R} ^{n}$ mit $y^{(i)}=+1$ gilt $x^{(i)}\in H_{+}$
$x^{(i)}\in \mathbb {R} ^{n}$ mit $y^{(i)}=-1$ gilt $x^{(i)}\in H_{-}$

Lineare Trennbarkeit

Zwei

Namensgebung - Support Vector bzw. Stützvektor

Da diese beiden Punkte sozusagen als Stützvektoren für das festlegen der gesuchten Hyperebene dienen wird diese Methode als Support Vector Machines bezeichnet.

Hyperebene

Darstellung eines affinen Unterraumes aus dem $\mathbb {R} ^{3}$ mit Stützvektor ${\vec {p}}$ .

Zerlegung in Klassen mit einer Hyperbene

Damit wird ein Punkt ${\vec {x}}$ der Menge $M_{+}$ über das Skalarprodukt zugeordnet, wenn

\langle {\vec {w}},{\vec {x}}-{\vec {p}}\rangle >0

gilt, während er im Fall

\langle {\vec {w}},{\vec {x}}-{\vec {p}}\rangle <0

der Menge $M_{-}$ zugeordnet wird.

Normalenvektor

${\vec {w}}$ ist der Normalenvektor zur Hyperebene,
${\vec {p}}$ ist der Stützvektor zu einem Punkt des affinen Unterraumes.

Vektoren aus der Hyperebene

Für den Fall $\langle {\vec {w}},{\vec {x}}-{\vec {p}}\rangle =0$ liegt der Vektor ${\vec {x}}$ genau in der durch den Normalenvektor ${\vec {w}}$ und den Stützvektor ${\vec {p}}$ definierten Hyperebene.

H_{0}:=\{{\vec {x}}\in \mathbb {R} ^{n}\ |\ T({\vec {x}})=0\}

Skalarprodukt als Maß für den Abstand zu Hyperebene

Die affine Abbildung $T({\vec {x}}):=\langle {\vec {w}},{\vec {x}}-{\vec {p}}\rangle$ stellt ein Messinstrument für Trennung in zwei Klassen durch eine Hyperbene dar:

mit $T({\vec {x}})=0$ liegt ${\vec {x}}$ in der Hyperebene
mit $T({\vec {x}})>0$ liegt ${\vec {x}}$ in der Klasse $M_{+}$
mit $T({\vec {x}})<0$ liegt ${\vec {x}}$ in der Klasse $M_{-}$

Epsilonumgebung um eine Hyperebene

Im Allgemeinen würde man erwarten, dass für verrauschte Traingsdaten ${\vec {x}}$ , die $+1$ bzw. $-1$ klassifziert sind, eine falsche Zuordnung mit $T({\vec {x}})$ in der Nähe der Hyperebene $H_{0}$ häufiger auftritt. Man kann das durch eine $\varepsilon$ -Umgebung um die Hyperebene.

Damit wird ein Punkt ${\vec {x}}$ der Menge $H_{+}$ über das Skalarprodukt zugeordnet, wenn

\langle {\vec {w}},{\vec {x}}-{\vec {p}}\rangle >0

gilt, während er im Fall

\langle {\vec {w}},{\vec {x}}-{\vec {p}}\rangle <0

der Menge $H_{-}$ zugeordnet wird.

Signumfunktion für die Klassifizierung

Mit der reelle Vorzeichenfunktion (Signumfunktion) kann man nun die Klassifizierung aller Vektoren aus dem Grundraum $\mathbb {R} ^{n}$ über den Wert der $\operatorname {sgn}$ -Funktion aus $\{-1,0,1\}$ festlegen:

\operatorname {sign} (\lambda ):={\begin{cases}+1,&\;{\text{falls}}\quad \lambda >0,\\\;\;\,0,&\;{\text{falls}}\quad \lambda =0,\\-1,&\;{\text{falls}}\quad \lambda <0.\\\end{cases}}

Vorzeichen beim Skalarprodukt als Klassifizierungsmerkmal

Die Klassifizierung mit einer Maschine $M_{t}$ zum Zeitpunkt $t$ erfolgt dann über:

M_{t}({\vec {x}}):=\operatorname {sign} (\langle {\vec {w}},{\vec {x}}-{\vec {p}}\rangle )={\begin{cases}+1,&\;{\text{falls}}\quad \langle {\vec {w}},{\vec {x}}-{\vec {p}}\rangle >0,\\\;\;\,0,&\;{\text{falls}}\quad \langle {\vec {w}},{\vec {x}}-{\vec {p}}\rangle =0,\\-1,&\;{\text{falls}}\quad \langle {\vec {w}},{\vec {x}}-{\vec {p}}\rangle <0.\\\end{cases}}

Bemerkung - Zeitindex

Die Maschine $M_{t}$ hat einen Index $t$ , da sich die Klassifizierung mit der Zeit $t$ durch einen Lernprozess und zusätzliche Trainingsdaten veränder kann.

Hyperebenenvektoren eindeutig zuordnen

Mit der Signumfunktion werden Vektoren aus der trennenden Hyperebene $\langle {\vec {w}},{\vec {x}}-{\vec {p}}\rangle =0$ . Für diesen Fall sollte man noch eine Festlegung treffen, zu welcher Menge dann der Vektor ${\vec {x}}$ zugeordnet wird oder ob solche Vektoren keine Klasse zugeordnet werden.

Außerhalb einer Umgebung um die Hyperebene

Die folgende Gleichung beschreibt, das ein Vektor ${\vec {x}}$ dem Halbraum $H_{+}$ zugeordnet wird und mindestens einen euklischen Abstand von $\varepsilon >0$ von der Hyperebene besitzt. Dies beschreibt

\langle {\vec {v}},{\vec {x}}-{\vec {p}}\rangle =\langle {\vec {v}},{\vec {x}}\rangle +\underbrace {\langle {\vec {v}},-{\vec {p}}\rangle } _{s_{0}}=\langle {\vec {v}},{\vec {x}}\rangle +s_{0}\geq \varepsilon

Den analogen Fall für die Zuordnung eines Vektors ${\vec {x}}$ zu dem Halbraum $H_{-}$ erhält man folgende Gleichung:

\langle {\vec {v}},{\vec {x}}-{\vec {p}}\rangle =\langle {\vec {v}},{\vec {x}}\rangle +\underbrace {\langle {\vec {v}},-{\vec {p}}\rangle } _{s_{0}}=\langle {\vec {v}},{\vec {x}}\rangle +s_{0}\leq -\varepsilon

Epsilonumgebung der Hyperebene

Gilt $\|{\vec {v}}\|=1$ , so entsteht eine $\varepsilon$ -Umgebung durch Parallelverschiebung der Hyperebene $H_{0}$ in Richtung des Normalenvektors $H_{-\varepsilon }$ und $H_{+\varepsilon }$ . Die eingeschlossenen Punkte der Umgebung um die Hyperebene können algebraisch wie folgt dargestellt werden:

x\in {\mathcal {U}}_{\varepsilon }(H_{0})\Longleftrightarrow |\langle {\vec {v}},{\vec {x}}-{\vec {p}}\rangle |<\varepsilon

Umformung mit Skalarprodukt als Bilinearform

Mit Anpassung des Normalenvektors und den Eigenschaften des Skalarproduktes als Bilinearform kann man die Gleichung auch wie folgt ausdrücken:

x\in {\mathcal {U}}_{\varepsilon }(H_{0})\Longleftrightarrow {\Bigg |}\left\langle \underbrace {{\frac {1}{\varepsilon }}\cdot {\vec {v}}} _{=v_{\varepsilon }},{\vec {x}}-{\vec {p}}\right\rangle {\Bigg |}<1

Korrektheit der Klassifizierung

Werden insgesamt alle Datenpunkte korrekt und vollständig klassifiziert, wenn für alle ${\vec {x}}_{i}\in \mathbb {R} ^{d}$ und $y_{i}\in \{-1,+1\}$ , wenn das Vorzeichen von ${sign}{\big (}\langle {\vec {v}},x_{i}\rangle {\big )}$ und das Vorzeichen von $y_{i}$ übereinstimmen.

Korrektheit - unvollständig

Die Korrektheit der Klassifizierung trifft im Allgemeinen nur für Datenpunkte außerhalb von eine $\varepsilon$ -Umgebung ${\mathcal {U}}_{\varepsilon }(H_{0})$ der Hyperebene zu. Dies wird durch den folgenden Zusammenhang beschrieben.

{\begin{array}{rcl}{\bigg \langle }\underbrace {{\frac {1}{\varepsilon }}\cdot {\vec {v}}} _{={\vec {v}}_{\varepsilon }},{\vec {x_{i}}}-{\vec {p}}{\bigg \rangle }\cdot y_{i}&=&{\big (}\langle {\vec {v}}_{\varepsilon },{\vec {x_{i}}}\rangle +\underbrace {\langle {\vec {v}}_{\varepsilon },-{\vec {p}}\rangle } _{=s_{\varepsilon }}{\big )}\cdot y_{i}\\&=&{\big (}\langle {\vec {v}}_{\varepsilon },{\vec {x_{i}}}\rangle +s_{\varepsilon }{\big )}\cdot y_{i}\\&\geq &1\end{array}}

Parameterreduktion

Der Stützvektor ${\vec {p}}\in \mathbb {R} ^{n}$ besitzt $n$ unbekannte Parameter. Durch die Nutzung der Linearität in der zweiten Komponente des Skalarproduktes kann man die Anzahl der Parameter bei Ersetzung durch $s_{\varepsilon }:=\langle v,-p\rangle \in \mathbb {R}$ um $n-1$ reduzieren.

Korrektheitsüberprüfung - Skalarprodukt und Klassenzuordnung

Durch die Multiplikation mit $y_{i}$ entsteht bei einer korrekten Zuordnung von ${\vec {x_{i}}}$ zu den Halbräumen $H_{+}$ bzw. $H_{-}$ ein positiver Wert und bei falscher Zuordnung einer negatives Produkt.

Breite der Umgebung

Die Breite der $\varepsilon$ -Umgebung um die Trennebene, in der man falsch zugeordneten $x$ findet, sollte auf der einen Seite möglichst klein sein. Betrachtet man die $\varepsilon$ -Umgebung um die Trennebene, in der man keine Trainingsdaten $x$ einer Klasse zugeordnet werden, sollte möglichst groß sein, da bei minimaler Veränderung der $x$ zu ${\widehat {x}}$ in $\mathbb {R} ^{n}$ in der Nähe der Hyperebene bereits die Zuordnung zur Klasse verändern kann. Das macht die Klassifikation weniger robust gegenüber verrauschten Daten.

Fehlerfunktion

Wenn die Hyperbene den Raum in zwei Halbräume zerlegt. Wenn sich ein falsch zugeordneten Vektor der Hyperebene annähern, soll eine Fehlerfunktion kleiner werden. Wenn sich ein korrekt zugeordneter Vektor auf die Hyperbene zuberewegt (also der Abstand in Richtung des Normalenvektor) annimmt, soll der Fehler größer werden, da die Annäherung für Trennungseigenschaft in Halbräume ungünstiger ist. Mit einer sigmoiden Funktion mit Werten zwischen 0 und +1 kann man diesen Fehler umsetzen in einer Fehlerfunktion.

Einzelfehler

Die Werte des Skalarproduktes von Datenvektoren mit dem Normalen geben über das Vorzeichen an, wie das Skalarprodukt die Klasse $H_{-}$ bzw. $H_{+}$ . Für Trainingsdaten $({\vec {x^{(i)}}},y^{(i)})\in \mathbb {R} ^{n}\times \{-1,+1\}$ kand man Produkt aus Skalarprodukt und der Klasszuordnung $y^{(i)}\in \{-1,+1\}$ bestimmt. Bei korrekter Zugeordnung der Daten durch das Skalarprodukt ist der folgende Ausdruck positiv (bei falscher negativ).

\langle {\vec {v}},{\vec {x^{(i)}}}-{\vec {p}}\rangle \cdot y^{(i)}

.

Beispiel - Klassifizierung Datenpaar

Trainingsdaten der Form $({\vec {x^{(i)}}},y^{(i)})\in \mathbb {R} ^{n}\times \{-1,+1\}$ bestehen aus einem Vektor ${\vec {x^{(i)}}}\in \mathbb {R} ^{n}$ und Klassfizierung zu $y^{(i)}\in \{-1,+1\}$ .

(korrekte Zuordnung 1) $\langle {\vec {v}},{\vec {x^{(1)}}}-{\vec {p}}\rangle =3,1\qquad y^{(1)}=+1$ mit $\langle {\vec {v}},{\vec {x^{(1)}}}-{\vec {p}}\rangle \cdot y^{(1)}>0$ .
(korrekte Zuordnung 2) $\langle {\vec {v}},{\vec {x^{(2)}}}-{\vec {p}}\rangle =-1,5\qquad y^{(2)}=-1$ mit $\langle {\vec {v}},{\vec {x^{2)}}}-{\vec {p}}\rangle \cdot y^{(2)}>0$ .
(falsche Zuordnung 3) $\langle {\vec {v}},{\vec {x^{(3)}}}-{\vec {p}}\rangle =-1,5\qquad y^{(3)}=+1$ mit $\langle {\vec {v}},{\vec {x^{3)}}}-{\vec {p}}\rangle \cdot y^{(3)}<0$ .

Sigmoide Funktion

Die folgende sigmoide Funktion hat folgende Eigenschaften

\operatorname {sig} (t)={\frac {1}{1+e^{-t}}}\qquad \lim _{t\to +\infty }\operatorname {sig} (t)=1\quad \lim _{t\to -\infty }\operatorname {sig} (t)=0

Man für große positive Werte von soll der Fehler allerdings sehr klein sein und für eine Datenpaar mit negativen Werten soll der Wert pro Datenpaar nahe bei 1 liegen und eine Fehler für einen einzelnen Wert erzeugen.

Sigmoide Funktion für den Fehler

Geht man zur Funktion $\operatorname {sig} _{_{SVM}}(t):=1-\operatorname {sig} (t)$ über, erhält man

\operatorname {sig} _{_{SVM}}(t)=1-{\frac {1}{1+e^{-t}}}={\frac {(1+e^{-t})-1}{1+e^{-t}}}={\frac {e^{-t}}{1+e^{-t}}}={\frac {1}{e^{t}+1}}

und es gilt $\lim _{t\to -\infty }\operatorname {sig} _{_{SVM}}(t)=1$ und $\lim _{t\to +\infty }\operatorname {sig} _{_{SVM}}(t)=0$ .

Ableitung der sigmoiden Funktion

Die Ableitung der sigmoiden Funktion ist für die partielle Ableitung der Fehlerfunktion $E_{SVM}$ relevant.

\operatorname {sig} _{_{SVM}}'(t)=-{{e^{t}} \over {\left(e^{t}+1\right)^{2}}}

Einzelfehler für einen Datensatz - 1

Der Einzelfehler für eine Datensatz wird über die sigmoide Funktion $\operatorname {sign} _{_{SVM}}$ . Diese sorgt dafür, dass weit von der Hyperebene entfernte korrekt zugeordnete Datensätze nahe bei 0 Fehler gewichtet werden und weit von der Hyperebene entfernte falsch zugeordnete Datensätze eine Fehler gegen 1 konvergiert.

{\frac {\partial e_{_{SVM}}}{\partial v_{i}}}(x,y,v,p)=-(x_{i}-p_{i})\cdot y\cdot {\frac {e^{\langle v,x-p\rangle \cdot y}}{\left(e^{\langle v,x-p\rangle \cdot y}+1\right)^{2}}}

{\frac {\partial e_{_{SVM}}}{\partial p_{i}}}(x,y,v,p)=v_{i}\cdot y\cdot {\frac {e^{\langle v,x-p\rangle \cdot y}}{\left(e^{\langle v,x-p\rangle \cdot y}+1\right)^{2}}}

Einzelfehler für einen Datensatz - 2

Wenn man den initiale Supportvektor nicht Konvexkombination der Clustermitten setzt und den angepassten Supportvektor $p$ nicht für weitere Verarbeitungsschritte benötigt, kann man die freien Parameter für den Gradienten über die sigmoide Funktion $\operatorname {sign} _{_{SVM}}$ auch wie folgt berechnen, in dem man die Parameter $p=(p_{1},\ldots ,p_{n})\in \mathbb {R} ^{n}$ durch eine Parameter $s\in \mathbb {R}$ ersetzt.

{\frac {\partial e_{_{SVM}}}{\partial v_{i}}}(x,y,v,s)=-x_{i}\cdot y\cdot {\frac {e^{(\langle v,x\rangle +s)\cdot y}}{\left(e^{(\langle v,x\rangle +s)\cdot y}+1\right)^{2}}}

{\frac {\partial e_{_{SVM}}}{\partial s}}(x,y,v,s)=-y\cdot {\frac {e^{(\langle v,x\rangle +s)\cdot y}}{\left(e^{(\langle v,x\rangle +s)\cdot y}+1\right)^{2}}}

Graph der sigmoiden Funktion

Definition der Fehlerfunktion

Für die Berechnung des Gesamtfehlers der muss man die Einzelfehler über alle Datenpunkte aggregieren. Die Daten $\mathbb {D}$ für die mehrdimensionale lineare Regression bestehen aus Datenpunkten der Form $(x^{(i)},y^{(i)})\in \mathbb {R} ^{n}\times \mathbb {R} ^{m}$ :

\mathbb {D} :=\left\{(x^{(i)},y^{(i)})\in \mathbb {R} ^{n}\times \mathbb {R} ^{m}\ \colon \ i\in \{1,\ldots ,d\}\right\}

Berechnung für die Komponenten Funktion

Durch die Zerlegung in Komponentenfunktionen minimiert man den Fehler für jeden Zeile der Matrix separat. Der folgende Gesamtfehler bezieht sich daher auf die Funktion $f_{a}(x):=\langle a,x\rangle$ für ein gesuchtes $a\in \mathbb {R} ^{n}$ mit minimalem Gesamtfehler für die Daten $\mathbb {D}$ .

Berechnung des Gesamtfehlers - 1

Für die Berechnung des Gesamtfehlers $E_{_{SVM}}(v,p,x_{\mathbb {D} },y_{\mathbb {D} })$ werden die quadratischen Fehler für einzelne Datenpunkte $(x^{(i)},y^{(i)})\in \mathbb {D}$ aufsummiert mit $x_{\mathbb {D} }:=(x^{(1)},\ldots ,x^{(d)})\in \mathbb {R} ^{d\cdot n}$ und $y_{\mathbb {D} }:=(y^{(1)},\ldots ,y^{(d)})\in \{-1,+1\}^{d}$ .

{\begin{array}{rcl}E_{_{SVM}}(v,p,x_{\mathbb {D} },y_{\mathbb {D} })&:=&\displaystyle \sum _{i=1}^{d}e(v,p,x^{(i)},y^{(i)})\\&=&\displaystyle \sum _{i=1}^{d}\operatorname {sig} _{_{SVM}}\left(\langle v,x^{(i)}-p\rangle \cdot y^{(i)}\right)\\\end{array}}

Lagrange-Funktion und deren Optimierung

Die Lagrange-Funktion soll dazu dienen $|{\vec {w}}|$ zu minimieren. Eine einfache und (wegen Gradientenabstieg) auch differenzierbare Funktion, ist eine quadrierte Länge des Vektors:

{\tilde {L}}({\vec {w}})={\frac {1}{2}}\|{\vec {w}}\|^{2}={\frac {1}{2}}\langle {\vec {w}},{\vec {w}}\rangle

Ziel - maximale Margin

Da es das Ziel ist, einen maximalen Margin zu finden, kann dies äquivalent umformuliert werden, zu dem Ziel ein minimales $|{\vec {w}}|$ bzw. $|{\vec {w}}|^{2}$ zu finden, während alle Datenpunkte vollständig und konsistent klassifiziert werden. Dies kann durch ein Optimierungsproblem mittels einer Lagrange-Funktion gelöst werden.

Nebenbedingung - Langrangemultiplikatoren

Allerdings sollen noch Nebenbedingungen erfüllt werden. Nämlich die vollständige und konsistente Klassifikation der Datenpunkte. Dazu können für jede Nebenbedingung die nicht negativen Lagrange-Multiplikatoren

\alpha _{i}\geq 0

eingeführt werden.

Multiplikatoren für richtige und falsche Klassifikationen

Bei einer richtigen Klassifikation des Datenpaars $({\vec {x}}_{i},y_{i})$ ist der Ausdruck

\alpha _{i}(y_{i}({\vec {w}}\cdot {\vec {x}}_{i}+w_{0})-1)

positiv. Es lässt sich motivieren, dass eine richtige Klassifikation "belohnt" werden muss. Da ein Minimum gesucht werden soll, sollte dieser Ausdruck bei einem richtig klassifizierten Ausdruck also abgezogen werden. Bei einer falschen Klassifikation ist dieser Ausdruck negativ und der Betrag des Ausdrucks sollte addiert werden, um die Fehlklassifkation zu "bestrafen".

Bemerkung - Fehlerfunktion

Auf diese weise lässt sich die Lagrange-Funktion in der Form

L({\vec {w}},w_{0},\alpha _{i})={\frac {1}{2}}|{\vec {w}}|^{2}-\sum _{i=1}^{N}\alpha _{i}(y_{i}({\vec {w}}\cdot {\vec {x}}_{i}+w_{0})-1)

finden. Die Größe der Lagrange-Multiplikatoren hängt damit zusammen, wie stark ein bestimmter Datenpunkt ins Gewicht fällt. Da die Hyperebene durch möglichst wenig Datenpunkte, am besten durch die zwei, die der Hyperebene am nächsten liegen, bestimmt werden soll, werden viele der $\alpha _{i}$ Null werden. In diesem Fall wird die Lagrange-Funktion aber größer.

Des bedeutet, es wird von der Lagrange-Funktion ein Minimum bezüglich ${\vec {w}}$ und $w_{0}$ gesucht, aber ein Maximum bezüglich der $\alpha _{i}$ .

Um das Minimum bezüglich ${\vec {w}}$ und $w_{0}$ zu finden, kann wieder die erste Ableitung gesucht und auf Null gesetzt werden, womit sich die beiden Bedingungen

 ${\vec {w}}=\sum _{i=1}^{N}\alpha _{i}y_{i}{\vec {x}}_{i}$

und

 $\sum _{i=1}^{N}\alpha _{i}y_{i}=0$

ergeben. Damit zeigt sich, dass bei bekannten $\alpha _{i}$ der Normalenvektor ${\vec {w}}$ direkt aus den Datenpunkten bestimmt werden kann. die $\alpha _{i}$ müssen dazu aber die Nebenbdeingung $\sum _{i=1}^{N}\alpha _{i}y_{i}=0$ erfüllen. Aus den obigen Gleichungen für die Punkte ${\vec {x}}_{+}$ und ${\vec {x}}_{-}$ lässt sich auch herleiten, dass $w_{0}$ durch die Gleichung

 $w_{0}=-{\frac {1}{2}}{\vec {w}}\cdot ({\vec {x}}_{+}+{\vec {x}}_{-})$

bestimmt werden können muss. Das bedeutet, alles was bleibt, ist die Lagrange-Multiplikatoren zu bestimmen.

Dazu wird das sog. Duale Problem formuliert. Bei diesem wird nach einem Extremum bzgl. $\alpha _{i}$ unter der Nebenbedingung einer Minimierung von $L$ bzgl. ${\vec {w}}$ und $w_{0}$ gesucht. Das bedeutet, in die obige Lagrange-Funktion können die gefundenen Bedingungen an ${\vec {w}}$ und $w_{0}$ eingesetzt werden, um so eine Lagrange-Funktion bzgl. der $\alpha _{i}$ zu erhalten. Auf diese Weise wird die duale Lagrange-Funktion

 $L_{\mathrm {D} }(\alpha _{i})=\sum _{i=1}^{N}\alpha _{i}-{\frac {1}{2}}\sum _{i,j=1}^{N}\alpha _{i}\alpha _{j}y_{i}y_{j}({\vec {x}}_{i}\cdot {\vec {x}}_{j})$

erhalten. Die Suche nach einer Extremstelle dieser führt auf die Bedingung

 ${\frac {\partial L_{\mathrm {D} }}{\partial \alpha _{k}}}=1-\sum _{i=1}^{N}\alpha _{i}y_{i}y_{k}({\vec {x}}_{i}\cdot {\vec {x}}_{k})=0\quad \quad \forall _{k\in \{1,\cdots ,N\}},$

welche nur erfüllt werden kann, wenn nicht alle $\alpha _{i}$ Null sind. Daneben müssen die $\alpha _{i}$ die Nebenbedingung $\sum _{i=1}^{N}\alpha _{i}y_{i}=0$ erfüllen, während $\alpha _{i}\geq 0$ gilt. In der Praxis werden die $\alpha _{i}$ auch häufig nach oben beschränkt.

Feature Engineering und Kernel-Funktionen

Auch hier lassen sich nicht linear separable Daten durch ein Feature Engineering mit einer passenden Feature Map

 $\phi :\mathbb {R} ^{d}\to \mathbb {R} ^{m},\,\,{\vec {x}}\mapsto \phi ({\vec {x}})\quad \quad m\gg d$

mit der oben beschriebenen Methode behandeln. Alerdings kann für die duale Lagrange-Funktion

 $L_{\mathrm {D} }(\alpha _{i})=\sum _{i=1}^{N}\alpha _{i}-{\frac {1}{2}}\sum _{i,j=1}^{N}\alpha _{i}\alpha _{j}y_{i}y_{j}(\phi ({\vec {x}}_{i})\cdot \phi ({\vec {x}}_{j}))$

so der Gradient

{\frac {\partial L_{\mathrm {D} }}{\partial \alpha _{k}}}=1-\sum _{i=1}^{N}\alpha _{i}y_{i}y_{k}(\phi ({\vec {x}}_{i})\cdot \phi ({\vec {x}}_{k}))

gefunden werden. Da es sich bei $\phi ({\vec {x}}_{i})\cdot \phi ({\vec {x}}_{j})$ um ein Skalarprodukt im $\mathbb {R} ^{m}$ statt im $\mathbb {R} ^{d}$ handelt, ist dieses wesentlich ressourcen- und damit zeitintensiver. Stattdessen wird häufig eine sog. Kernelfunktion