Kurs:Maschinelles Lernen/Klassifikation mittels Support Vector Machines
Vorherige Seite: K3 - Klassifikation mittels Gradientenabstieg
Nächste Seite : K4 - Grundidee der Neuronalen Netze
Grundidee[Bearbeiten]
Die Klassifikation mittels Gradientenabstieg sucht nach einer Lösung, die Teil des Versionsraum 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 bezeichnet und die beiden beschriebenen Punkte mit und , so lassen sich bei passender Normierung von für die optimale Hyperebene die beiden Gleichungen
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 der Menge zugeordnet, wenn
gilt, während er im Fall
der Menge zugeordnet wird. Insgesamt werden alle Datenpunkte konsistent und vollständig klassifiziert, wenn für alle und der Zusammenhang
gültig ist. Die breite des Margings kann in diesem Fall mit
bestimmt werden. Da es das Ziel ist, einen maximalen Margin zu finden, kann dies äquivalent umformuliert werden, zu dem Ziel ein minimales bzw. 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[Bearbeiten]
Die Lagrange-Funktion soll dazu dienen zu minimieren. Eine der einfachsten und am besten differenzierbarsten Funktionen, die ein Minium aufweist, ist eine quadratische Funktion, womit sich der Ansatz
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 eingeführt werden. Bei einer richtigen Klassifikation des Datenpaars ist der Ausdruck
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
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 Null werden. In diesem Fall wird die Lagrange-Funktion aber größer.
Des bedeutet, es wird von der Lagrange-Funktion ein Minimum bezüglich und gesucht, aber ein Maximum bezüglich der .
Um das Minimum bezüglich und zu finden, kann wieder die erste Ableitung gesucht und auf Null gesetzt werden, womit sich die beiden Bedingungen
und
ergeben. Damit zeigt sich, dass bei bekannten der Normalenvektor direkt aus den Datenpunkten bestimmt werden kann. die müssen dazu aber die Nebenbdeingung erfüllen. Aus den obigen Gleichungen für die Punkte und lässt sich auch herleiten, dass durch die Gleichung
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. unter der Nebenbedingung einer Minimierung von bzgl. und gesucht. Das bedeutet, in die obige Lagrange-Funktion können die gefundenen Bedingungen an und eingesetzt werden, um so eine Lagrange-Funktion bzgl. der zu erhalten. Auf diese Weise wird die duale Lagrange-Funktion
erhalten. Die Suche nach einer Extremstelle dieser führt auf die Bedingung
welche nur erfüllt werden kann, wenn nicht alle Null sind. Daneben müssen die die Nebenbedingung erfüllen, während gilt. In der Praxis werden die auch häufig nach oben beschränkt.
Feature Engineering und Kernel-Funktionen[Bearbeiten]
Auch hier lassen sich nicht linear separable Daten durch ein Feature Engineering mit einer passenden Feature Map
mit der oben beschriebenen Methode behandeln. Alerdings kann für die duale Lagrange-Funktion
so der Gradient
gefunden werden. Da es sich bei um ein Skalarprodukt im statt im handelt, ist dieses wesentlich resssourcen- und damit zeitintensiver. Stattdessen wird häufig eine sog. Kernelfunktion
eingeführt. Mit ihr wird der Gradient der dualen Lagrange-Funktion
durch
bestimmt.
Drei der am häufigsten KernelFunktionen sind durch
gegeben. Darin sind und positive Konstanten und eine weiter festzulegende Funktion.