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 Teil des Versionsraum $V$ ist. Es lässt sich allerdings auch die Frage stellen, ob die gefundene Lösung die beste Lösung im Versionsrraum ist.

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. Dazu können bei einer binären Klassifikation aus den beiden Teilbereichen die Datenpunkte herangezogen werden, die der Hyperebene am nächsten liegen. Die Summe ihres Abstands zur Trennebene wird als Margin bezeichnet. Ziel ist es, diesen möglichst gering zu machen. Werden die Klassen mit $Y=\{-1,+1\}$ bezeichnet und die beiden beschriebenen Punkte mit ${\vec {x}}_{-}$ und ${\vec {x}}_{+}$, so lassen sich bei passender Normierung von ${\vec {w}}$ für die optimale Hyperebene die beiden Gleichungen

${\vec {w}}\cdot {\vec {x}}_{-}+w_{0}=-1\quad \quad {\vec {w}}\cdot {\vec {x}}_{+}+w_{0}=+1$

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

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

${\vec {w}}\cdot {\vec {x}}+w_{0}\geq +1$

gilt, während er im Fall

${\vec {w}}\cdot {\vec {x}}+w_{0}\leq +1$

der Menge $M_{-}$ zugeordnet wird. Insgesamt werden alle Datenpunkte konsistent und vollständig klassifiziert, wenn für alle ${\vec {x}}_{i}\in \mathbb {R} ^{d}$ und $y_{i}\in \{-1,+1\}$ der Zusammenhang

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

gültig ist. Die breite des Margings kann in diesem Fall mit

$b={\frac {2}{|{\vec {w}}|}}$

bestimmt werden. 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.

Lagrange-Funktion und deren Optimierung

Die Lagrange-Funktion soll dazu dienen $|{\vec {w}}|$ zu minimieren. Eine der einfachsten und am besten differenzierbarsten Funktionen, die ein Minium aufweist, ist eine quadratische Funktion, womit sich der Ansatz

${\tilde {L}}={\frac {1}{2}}|{\vec {w}}|^{2}$

machen lässt. 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. 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". 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 resssourcen- und damit zeitintensiver. Stattdessen wird häufig eine sog. Kernelfunktion

$K:\mathbb {R} ^{d}\times \mathbb {R} ^{d}\to \mathbb {R} ,\,\,({\vec {x}}_{i},{\vec {x}}_{j})\mapsto K({\vec {x}}_{i},{\vec {x}}_{j})$

eingeführt. Mit ihr wird der Gradient der dualen 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}K({\vec {x}}_{i},{\vec {x}}_{j})$

durch

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

bestimmt.

Drei der am häufigsten KernelFunktionen sind durch

$K_{\mathrm {SP} ,1}({\vec {x}},{\vec {y}})=({\vec {x}}\cdot {\vec {y}})^{a}\quad \quad K_{\mathrm {Gauss} ,\sigma }({\vec {x}},{\vec {y}})=\mathrm {exp} \left(-{\frac {|{\vec {x}}-{\vec {y}}|^{2}}{2\sigma ^{2}}}\right)\quad \quad K_{\mathrm {sig} ,\kappa }({\vec {x}},{\vec {y}})=\mathrm {sig} (\kappa ({\vec {x}},{\vec {y}}))$

gegeben. Darin sind $a$ und $\sigma$ positive Konstanten und $\kappa ({\vec {x}},{\vec {y}})$ eine weiter festzulegende Funktion.