Support Vector Machines und Kernel-Methoden

Support Vector Machines finden die Entscheidungsgrenze, die den Abstand zwischen den Klassen maximiert, und der Kernel-Trick ermöglicht es solchen linearen Methoden, implizit in reichhaltigen nichtlinearen Merkmalsräumen zu operieren.

Definition

Eine Support Vector Machine ist ein Klassifikator, der die trennende Hyperebene wählt, die den Abstand zu den nächsten Trainingspunkten maximiert; Kernel-Methoden verallgemeinern dies, indem sie innere Produkte durch eine Kernel-Funktion berechnen, wodurch lineare Algorithmen nichtlineare Grenzen anpassen können, ohne den hochdimensionalen Merkmalsraum explizit zu konstruieren.

Scope

Dieses Thema behandelt die Maximum-Margin-Klassifikation, die primale und duale Formulierung der Support Vector Machine, die Rolle von Support-Vektoren und Slack-Variablen für nicht trennbare Daten, den Kernel-Trick, der innere Produkte durch Kernel-Funktionen ersetzt, gängige Kernel wie Polynom- und radiale Basisfunktionen sowie die Erweiterung der Kernelisierung auf Regression und andere lineare Methoden.

Core questions

• Warum verbessert die Maximierung des Abstands tendenziell die Generalisierung?
• Wie drückt die duale Formulierung die Lösung in Bezug auf Support-Vektoren aus?
• Was bewirkt der Kernel-Trick und warum ist er effizient?
• Wie werden Soft Margins und Slack-Variablen verwendet, wenn sich Klassen überlappen?

Key theories

Maximum-Margin-Trennung

Unter den trennenden Hyperebenen liefert diejenige, die den Abstand zu den nächsten Punkten maximiert, eine eindeutige Lösung, die durch wenige Support-Vektoren bestimmt wird und mit guten Generalisierungs-Grenzen verbunden ist.

Der Kernel-Trick

Da die Optimierung nur über innere Produkte von Daten abhängt, bewertet das Ersetzen dieser durch eine Kernel-Funktion implizit eine nichtlineare Merkmalsabbildung, wodurch nichtlineare Grenzen zu den Kosten einer linearen Methode angepasst werden können.

Soft-Margin und Slack-Variablen

Das Zulassen kontrollierter Margin-Verletzungen durch Slack-Variablen und einen Regularisierungsparameter macht die Support Vector Machine auf überlappende, verrauschte Klassen anwendbar, während ein Kompromiss zwischen Margin-Breite und Trainingsfehlern eingegangen wird.

Clinical relevance

Support Vector Machines und Kernel-Methoden waren vor dem Deep Learning die führenden hochpräzisen Klassifikatoren und bleiben eine gute Wahl für mittelgroße Probleme, insbesondere in der Text- und Bioinformatik; die Kernel-Idee verallgemeinert sich auch weit über die Klassifikation hinaus und findet sich in der Kernel-Regression, Gaußschen Prozessen und der kernelisierten Hauptkomponentenanalyse wieder.

History

Die Maximum-Margin-Idee und der Kernel-Trick wurden um 1992 von Boser, Guyon und Vapnik kombiniert, und die Soft-Margin Support Vector Machine wurde 1995 von Cortes und Vapnik formalisiert. In den späten 1990er und 2000er Jahren wurden Kernel-Methoden im Bereich der Mustererkennung dominant, bevor sie bei groß angelegten Wahrnehmungsaufgaben weitgehend durch Deep Learning verdrängt wurden.

Key figures

• Vladimir Vapnik
• Corinna Cortes
• Bernhard Scholkopf

Seminal works

• cortes1995
• vapnik1995
• bishop2006

Frequently asked questions

Was ist ein Support-Vektor?

Ein Support-Vektor ist ein Trainingspunkt, der auf oder innerhalb des Abstands liegt und somit die Position der Entscheidungsgrenze bestimmt. Der angepasste Klassifikator hängt nur von diesen Punkten ab, sodass der Rest der Trainingsdaten verworfen werden kann.

Warum wird die Verwendung von Kernels als „Trick“ bezeichnet?

Der Kernel-Trick ermöglicht es einem Algorithmus, sich so zu verhalten, als hätte er die Daten in einen sehr hochdimensionalen oder sogar unendlich-dimensionalen Merkmalsraum abgebildet, während er nur Kernel-Werte zwischen Punktpaaren berechnet. Er vermeidet die Kosten für den expliziten Aufbau dieses Raums.