Stützvektormaschine - Support-vector machine

Im maschinellen Lernen sind Support-Vektor-Maschinen ( SVMs , auch Support-Vektor-Netzwerke ) überwachte Lernmodelle mit zugehörigen Lernalgorithmen , die Daten zur Klassifizierung und Regressionsanalyse analysieren . Entwickelt bei AT & T Bell Laboratories von Vladimir Vapnik mit Kollegen (Boser et al., 1992, Guyon et al., 1993, Vapnik et al., 1997) SVMs sind eine der robustesten Vorhersagemethoden, basiert auf statistischen Lernumfeldern oder VC Theorie von Vapnik (1982, 1995) und Chervonenkis (1974). Ausgehend von einer Reihe von Trainingsbeispielen, von denen jedes als einer von zwei Kategorien zugehörig markiert ist, erstellt ein SVM-Trainingsalgorithmus ein Modell, das neue Beispiele der einen oder anderen Kategorie zuweist, wodurch es zu einem nicht- probabilistischen binären linearen Klassifikator wird (obwohl Methoden wie Platt Skalierung vorhanden ist, um SVM in einer probabilistischen Klassifizierungseinstellung zu verwenden). SVM bildet Trainingsbeispiele auf Punkte im Raum ab, um die Breite der Lücke zwischen den beiden Kategorien zu maximieren. Neue Beispiele werden dann in denselben Raum abgebildet und basierend darauf, auf welche Seite der Lücke sie fallen, als zu einer Kategorie gehörend vorhergesagt.

Neben der linearen Klassifizierung können SVMs effizient eine nichtlineare Klassifizierung mit dem sogenannten Kernel-Trick durchführen , indem sie ihre Eingaben implizit in hochdimensionale Merkmalsräume abbilden.

Wenn Daten nicht gekennzeichnet sind, ist überwachtes Lernen nicht möglich, und es ist ein Ansatz des unüberwachten Lernens erforderlich, der versucht, eine natürliche Clusterung der Daten zu Gruppen zu finden und dann neue Daten diesen gebildeten Gruppen zuzuordnen. Der von Hava Siegelmann und Vladimir Vapnik entwickelte Support-Vektor-Clustering- Algorithmus wendet die im Support-Vektor-Maschinen-Algorithmus entwickelte Statistik von Support-Vektoren an, um unbeschriftete Daten zu kategorisieren, und ist einer der am weitesten verbreiteten Clustering-Algorithmen in industriellen Anwendungen.

Motivation

H 1 trennt die Klassen nicht. H 2 tut es, aber nur mit geringem Spielraum. H 3 trennt sie mit dem maximalen Rand.

Das Klassifizieren von Daten ist eine häufige Aufgabe beim maschinellen Lernen . Angenommen, einige gegebene Datenpunkte gehören jeweils zu einer von zwei Klassen, und das Ziel ist es zu entscheiden, in welche Klasse ein neuer Datenpunkt aufgenommen wird. Im Fall von Support-Vektor-Maschinen wird ein Datenpunkt als ein -dimensionaler Vektor (a Liste der Zahlen), und wir wollen wissen , ob wir solche Punkte mit einer trennen können -dimensionale Hyperebene . Dies wird als linearer Klassifikator bezeichnet . Es gibt viele Hyperebenen, die die Daten klassifizieren könnten. Eine vernünftige Wahl als beste Hyperebene ist diejenige, die den größten Abstand zwischen den beiden Klassen darstellt. Wir wählen die Hyperebene also so, dass der Abstand von ihr zum nächsten Datenpunkt auf jeder Seite maximiert wird. Wenn eine solche Hyperebene existiert, wird sie als Maximum-Margin-Hyperebene bezeichnet und der von ihr definierte lineare Klassifikator wird als Maximum- Margin-Klassifikator bezeichnet ; oder äquivalent das Perzeptron der optimalen Stabilität .

Definition

Formaler ausgedrückt konstruiert eine Support-Vektor-Maschine eine Hyperebene oder einen Satz von Hyperebenen in einem hoch- oder unendlichdimensionalen Raum, die für die Klassifizierung , Regression oder andere Aufgaben wie die Erkennung von Ausreißern verwendet werden können. Intuitiv wird eine gute Trennung durch die Hyperebene erreicht, die den größten Abstand zum nächsten Trainingsdatenpunkt einer Klasse hat (sogenannter funktionaler Spielraum), denn im Allgemeinen ist der Generalisierungsfehler des Klassifikators umso geringer, je größer der Spielraum ist .

Kernelmaschine

Während das ursprüngliche Problem in einem endlichdimensionalen Raum gestellt werden kann, kommt es oft vor, dass die zu unterscheidenden Mengen in diesem Raum nicht linear trennbar sind. Aus diesem Grund wurde vorgeschlagen, den ursprünglichen endlichdimensionalen Raum in einen viel höherdimensionalen Raum abzubilden, was vermutlich die Trennung in diesem Raum erleichtert. Um die Rechenlast angemessen zu halten, sind die von SVM-Schemata verwendeten Abbildungen so ausgelegt, dass Punktprodukte von Paaren von Eingabedatenvektoren leicht in Bezug auf die Variablen im ursprünglichen Raum berechnet werden können, indem sie in Bezug auf eine ausgewählte Kernfunktion definiert werden um dem Problem zu entsprechen. Die Hyperebenen im höherdimensionalen Raum sind definiert als die Menge von Punkten, deren Skalarprodukt mit einem Vektor in diesem Raum konstant ist, wobei eine solche Menge von Vektoren eine orthogonale (und damit minimale) Menge von Vektoren ist, die eine Hyperebene definiert. Die die Hyperebenen definierenden Vektoren können als Linearkombinationen mit Parametern von Bildern von Merkmalsvektoren gewählt werden , die in der Datenbank vorkommen. Bei dieser Wahl einer Hyperebene werden die Punkte im Merkmalsraum , die in die Hyperebene abgebildet werden, durch die Beziehung definiert Beachten Sie, dass jeder Term in der Summe den Grad der Nähe des Testpunkts an . misst , wenn er mit zunehmender Entfernung von klein wird den entsprechenden Datenbankpunkt . Auf diese Weise kann die obige Summe der Kernel verwendet werden, um die relative Nähe jedes Testpunkts zu den Datenpunkten zu messen, die aus dem einen oder anderen der zu unterscheidenden Sätze stammen. Beachten Sie die Tatsache, dass die Menge von Punkten, die in jede Hyperebene abgebildet werden, als Ergebnis ziemlich verschachtelt sein kann, was eine viel komplexere Unterscheidung zwischen Mengen ermöglicht, die im ursprünglichen Raum überhaupt nicht konvex sind.

Anwendungen

SVMs können verwendet werden, um verschiedene reale Probleme zu lösen:

  • SVMs sind bei der Text- und Hypertext-Kategorisierung hilfreich , da ihre Anwendung den Bedarf an gekennzeichneten Trainingsinstanzen sowohl in den standardmäßigen induktiven als auch in den transduktiven Einstellungen erheblich reduzieren kann . Einige Methoden für das seichte semantische Parsing basieren auf Support-Vektor-Maschinen.
  • Die Klassifizierung von Bildern kann auch mit SVMs durchgeführt werden. Experimentelle Ergebnisse zeigen, dass SVMs nach nur drei bis vier Runden des Relevanz-Feedbacks eine deutlich höhere Suchgenauigkeit erreichen als herkömmliche Abfrageverfeinerungsschemata. Dies gilt auch für Bildsegmentierungssysteme , einschließlich solcher, die eine modifizierte Version von SVM verwenden, die den von Vapnik vorgeschlagenen privilegierten Ansatz verwendet.
  • Klassifizierung von Satellitendaten wie SAR- Daten mit überwachtem SVM.
  • Handgeschriebene Zeichen können mit SVM erkannt werden.
  • Der SVM-Algorithmus ist in der Biologie und anderen Wissenschaften weit verbreitet. Sie wurden verwendet, um Proteine ​​zu klassifizieren, wobei bis zu 90% der Verbindungen richtig klassifiziert wurden. Als Mechanismus zur Interpretation von SVM-Modellen wurden Permutationstests auf der Grundlage von SVM-Gewichten vorgeschlagen. In der Vergangenheit wurden auch Stützvektor-Maschinengewichtungen verwendet, um SVM-Modelle zu interpretieren. Die posthoc-Interpretation von Support-Vektor-Maschinenmodellen zur Identifizierung von Merkmalen, die vom Modell verwendet werden, um Vorhersagen zu treffen, ist ein relativ neues Forschungsgebiet mit besonderer Bedeutung in den biologischen Wissenschaften.

Geschichte

Der ursprüngliche SVM-Algorithmus wurde von Vladimir N. Vapnik und Alexey Ya erfunden . Chervonenkis im Jahr 1963. 1992 schlugen Bernhard Boser, Isabelle Guyon und Vladimir Vapnik einen Weg vor, nichtlineare Klassifikatoren zu erstellen, indem sie den Kernel-Trick auf Hyperebenen mit maximalem Rand anwenden . Die Inkarnation "Soft Margin" wurde 1993 von Corinna Cortes und Vapnik vorgeschlagen und 1995 veröffentlicht.

Lineare SVM

Hyperplane mit maximalem Rand und Ränder für eine SVM, die mit Stichproben aus zwei Klassen trainiert wurde. Stichproben am Rand werden Stützvektoren genannt.

Wir erhalten einen Trainingsdatensatz von Punkten der Form

wobei die entweder 1 oder –1 sind, wobei jede die Klasse anzeigt, zu der der Punkt gehört. Jeder ist ein -dimensionaler reeller Vektor. Wir wollen die "Maximum-Margin-Hyperebene" finden, die die Punktgruppe für die von der Punktgruppe für die trennt , die so definiert ist, dass der Abstand zwischen der Hyperebene und dem nächstgelegenen Punkt jeder Gruppe maximiert wird.

Jede Hyperebene kann als Menge von Punkten geschrieben werden, die

wo ist der (nicht unbedingt normalisierte) Normalenvektor zur Hyperebene. Dies ist der Hesse-Normalform sehr ähnlich , außer dass es sich nicht unbedingt um einen Einheitsvektor handelt. Der Parameter bestimmt den Versatz der Hyperebene vom Ursprung entlang des Normalenvektors .

Harter Rand

Wenn die Trainingsdaten linear trennbar sind , können wir zwei parallele Hyperebenen auswählen, die die beiden Datenklassen trennen, damit der Abstand zwischen ihnen so groß wie möglich ist. Der von diesen beiden Hyperebenen begrenzte Bereich wird als "Margin" bezeichnet, und die Hyperebene mit maximalem Rand ist die Hyperebene, die auf halbem Weg zwischen ihnen liegt. Mit einem normalisierten oder standardisierten Datensatz können diese Hyperebenen durch die Gleichungen beschrieben werden

(Alles auf oder über dieser Grenze ist von einer Klasse, mit Label 1)

und

(Alles auf oder unter dieser Grenze ist von der anderen Klasse mit dem Label −1).

Geometrisch ist der Abstand zwischen diesen beiden Hyperebenen , um den Abstand zwischen den Ebenen zu maximieren, möchten wir also minimieren . Die Entfernung wird unter Verwendung der Entfernung von einem Punkt zu einer Ebenengleichung berechnet. Wir müssen auch verhindern, dass Datenpunkte in den Rand fallen, wir fügen die folgende Einschränkung hinzu: für jedes entweder

, wenn ,

oder

, wenn .

Diese Einschränkungen besagen, dass jeder Datenpunkt auf der richtigen Seite des Randes liegen muss.

Dies kann umgeschrieben werden als

Wir können dies zusammensetzen, um das Optimierungsproblem zu erhalten:

" Betreff minimieren für ."

Die und die dieses Problem lösen bestimmen unseren Klassifikator, wo ist die Vorzeichenfunktion .

Eine wichtige Konsequenz dieser geometrischen Beschreibung ist, dass die Max-Margin-Hyperebene vollständig von denen bestimmt wird , die ihr am nächsten liegen. Diese werden Stützvektoren genannt .

Weicher Rand

Um SVM auf Fälle auszudehnen, in denen die Daten nicht linear trennbar sind, ist die Scharnierverlustfunktion hilfreich

Beachten Sie, dass dies das i- te Ziel ist (dh in diesem Fall 1 oder –1) und die i- te Ausgabe ist.

Diese Funktion ist null, wenn die Bedingung in (1) erfüllt ist, also auf der richtigen Seite des Randes liegt. Bei Daten auf der falschen Seite des Rands ist der Wert der Funktion proportional zum Abstand vom Rand.

Das Ziel der Optimierung ist dann die Minimierung

wobei der Parameter den Kompromiss zwischen der Erhöhung der Margin-Größe und dem Sicherstellen, dass der Wert auf der richtigen Seite der Margin liegt, bestimmt. Somit verhält es sich für ausreichend große Werte von ähnlich wie die SVM mit festem Rand, wenn die Eingabedaten linear klassifizierbar sind, lernt aber dennoch, ob eine Klassifizierungsregel praktikabel ist oder nicht. (Dieser Parameter wird auch C genannt, zB in LIBSVM .)

Nichtlineare Klassifizierung

Kernelmaschine

Der ursprüngliche Hyperplane-Algorithmus mit maximalem Spielraum, der 1963 von Vapnik vorgeschlagen wurde, konstruierte einen linearen Klassifikator . 1992 schlugen Bernhard Boser , Isabelle Guyon und Vladimir Vapnik jedoch einen Weg vor, nichtlineare Klassifikatoren zu erstellen, indem sie den Kernel-Trick (ursprünglich von Aizerman et al. vorgeschlagen) auf Hyperebenen mit maximalem Rand anwenden. Der resultierende Algorithmus ist formal ähnlich, außer dass jedes Punktprodukt durch eine nichtlineare Kernelfunktion ersetzt wird. Dadurch kann der Algorithmus die Hyperebene mit maximalem Rand in einen transformierten Merkmalsraum einpassen . Die Transformation kann nichtlinear und der transformierte Raum hochdimensional sein; Obwohl der Klassifikator im transformierten Featureraum eine Hyperebene ist, kann er im ursprünglichen Eingaberaum nichtlinear sein.

Es ist bemerkenswert, dass das Arbeiten in einem höherdimensionalen Merkmalsraum den Generalisierungsfehler von Support-Vektor-Maschinen erhöht , obwohl der Algorithmus bei genügend Samples immer noch gut funktioniert .

Einige gängige Kernel sind:

  • Polynom (homogen) : .
  • Polynom (inhomogen): .
  • Gaußsche radiale Basisfunktion : für . Manchmal parametrisiert mit .
  • Hyperbolischer Tangens : für einige (nicht alle) und .

Der Kernel hängt mit der Transformation durch die Gleichung zusammen . Der Wert w liegt auch im transformierten Raum, mit . Punktprodukte mit w zur Klassifikation können wieder mit dem Kernel-Trick berechnet werden, dh .

Berechnen des SVM-Klassifikators

Die Berechnung des (Soft-Margin-)SVM-Klassifikators läuft auf die Minimierung eines Ausdrucks der Form hinaus

Wir konzentrieren uns auf den Soft-Margin-Klassifikator, da, wie oben erwähnt, die Wahl eines ausreichend kleinen Wertes für den Hard-Margin-Klassifikator für linear klassifizierbare Eingabedaten ergibt. Der klassische Ansatz, bei dem (2) auf ein quadratisches Programmierproblem reduziert wird, wird unten detailliert beschrieben. Dann werden neuere Ansätze wie Subgradientenabstieg und Koordinatenabstieg diskutiert.

Primal

Das Minimieren von (2) kann wie folgt in ein eingeschränktes Optimierungsproblem mit einer differenzierbaren Zielfunktion umgeschrieben werden.

Für jedes führen wir eine Variable ein . Beachten Sie, dass die kleinste nichtnegative Zahl, die erfüllt

Damit können wir das Optimierungsproblem wie folgt umschreiben

Dies wird als Primärproblem bezeichnet.

Dual

Durch Auflösen nach dem Lagrange-Dual des obigen Problems erhält man das vereinfachte Problem

Dies wird als duales Problem bezeichnet. Da das duale Maximierungsproblem eine quadratische Funktion des Gegenstands linearer Beschränkungen ist, ist es effizient durch quadratische Programmieralgorithmen lösbar .

Hier sind die Variablen so definiert, dass

.

Außerdem genau, wann auf der richtigen Randseite und wann auf der Randgrenze liegt. Daraus folgt, dass dies als Linearkombination der Stützvektoren geschrieben werden kann.

Der Offset, , kann wiederhergestellt werden, indem man an der Randgrenze findet und löst

(Beachten Sie, dass seit .)

Kernel-Trick

Ein Trainingsbeispiel für SVM mit Kernel gegeben durch φ(( a , b )) = ( a , b , a 2 + b 2 )

Angenommen, wir möchten eine nichtlineare Klassifikationsregel lernen, die einer linearen Klassifikationsregel für die transformierten Datenpunkte entspricht. Außerdem erhalten wir eine Kernfunktion, die erfüllt .

Wir wissen, dass der Klassifikationsvektor im transformierten Raum erfüllt

wobei die durch Lösung des Optimierungsproblems erhalten werden

Die Koeffizienten können wie zuvor durch quadratische Programmierung gelöst werden. Wieder können wir einen Index finden, so dass , so dass auf dem Rand des Randes im transformierten Raum liegt, und dann lösen

Schließlich,

Moderne Methoden

Neuere Algorithmen zum Auffinden des SVM-Klassifikators umfassen Subgradientenabstieg und Koordinatenabstieg. Beide Techniken haben sich beim Umgang mit großen, spärlichen Datensätzen als deutliche Vorteile gegenüber dem herkömmlichen Ansatz erwiesen – Subgradient-Methoden sind besonders effizient, wenn viele Trainingsbeispiele vorhanden sind, und Koordinatenabstieg, wenn die Dimension des Merkmalsraums groß ist.

Subgradienter Abstieg

Subgradient-Abstiegsalgorithmen für die SVM arbeiten direkt mit dem Ausdruck

Beachten Sie, dass dies eine konvexe Funktion von und ist . Als solche können traditionelle Gradientenabstiegs- (oder SGD- )Verfahren angepasst werden, bei denen anstelle eines Schrittes in Richtung des Gradienten der Funktion ein Schritt in Richtung eines aus dem Untergradienten der Funktion ausgewählten Vektors gemacht wird . Dieser Ansatz hat den Vorteil, dass bei bestimmten Implementierungen die Anzahl der Iterationen nicht mit der Anzahl der Datenpunkte skaliert .

Abstieg koordinieren

Koordinatenabstiegsalgorithmen für die SVM-Arbeit aus dem dualen Problem

Für jede wird der Koeffizient iterativ in Richtung von angepasst . Dann wird der resultierende Koeffizientenvektor auf den nächsten Koeffizientenvektor projiziert, der die gegebenen Beschränkungen erfüllt. (Typischerweise werden euklidische Abstände verwendet.) Der Prozess wird dann wiederholt, bis ein nahezu optimaler Koeffizientenvektor erhalten wird. Der resultierende Algorithmus ist in der Praxis extrem schnell, obwohl nur wenige Leistungsgarantien nachgewiesen wurden.

Empirische Risikominimierung

Die oben beschriebene Soft-Margin Support Vector Machine ist ein Beispiel für einen empirischen Risikominimierungs- (ERM)-Algorithmus für den Scharnierverlust . So gesehen gehören Support Vector Machines zu einer natürlichen Klasse von Algorithmen für statistische Inferenz, und viele ihrer einzigartigen Eigenschaften sind auf das Verhalten des Scharnierverlusts zurückzuführen. Diese Perspektive kann weitere Erkenntnisse darüber liefern, wie und warum SVMs funktionieren, und es uns ermöglichen, ihre statistischen Eigenschaften besser zu analysieren.

Risikominimierung

In wachtes Lernen wird man einen Satz von Trainingsbeispielen gegeben mit Etikett und Wünschen zu sagen voraus gegeben . Dazu bildet man eine Hypothese , , also eine "gute" Näherung von . Eine „gute“ Annäherung ist in der Regel mit Hilfe einer definierten Verlustfunktion , , die charakterisiert , wie schlimm ist als eine Vorhersage . Wir möchten dann eine Hypothese wählen, die das erwartete Risiko minimiert :

In den meisten Fällen kennen wir die gemeinsame Verteilung von Outright nicht. In diesen Fällen besteht eine gängige Strategie darin, die Hypothese zu wählen, die das empirische Risiko minimiert :

Unter bestimmten Annahmen über die Folge von Zufallsvariablen (z. B. dass sie durch einen endlichen Markov-Prozess erzeugt werden) wird der Minimierer des empirischen Risikos, wenn die betrachtete Menge von Hypothesen klein genug ist, dem Minimierer des erwarteten Risikos sehr nahe kommen wie groß wird. Dieser Ansatz wird als empirische Risikominimierung oder ERM bezeichnet.

Regularisierung und Stabilität

Damit das Minimierungsproblem eine wohldefinierte Lösung hat, müssen wir die zu betrachtenden Hypothesen einschränken . Wenn es sich um einen normierten Raum handelt (wie es bei SVM der Fall ist), besteht eine besonders effektive Technik darin, nur die Hypothesen zu berücksichtigen, für die . Dies entspricht dem Auferlegen einer Regularisierungsstrafe und dem Lösen des neuen Optimierungsproblems

Dieser Ansatz wird als Tikhonov-Regularisierung bezeichnet .

Allgemeiner kann ein gewisses Maß für die Komplexität der Hypothese sein , so dass einfachere Hypothesen bevorzugt werden.

SVM und der Scharnierverlust

Denken Sie daran, dass der SVM-Klassifikator (mit weichem Rand) ausgewählt wird, um den folgenden Ausdruck zu minimieren:

Angesichts der obigen Diskussion sehen wir, dass die SVM-Technik äquivalent zur empirischen Risikominimierung mit Tikhonov-Regularisierung ist, wobei in diesem Fall die Verlustfunktion der Scharnierverlust ist

Aus dieser Perspektive ist SVM eng verwandt mit anderen grundlegenden Klassifikationsalgorithmen wie Regularized Least Squares und Logistic Regression . Der Unterschied zwischen den dreien liegt in der Wahl der Verlustfunktion: Regularisierte kleinste Quadrate bedeuten empirische Risikominimierung mit dem quadratischen Verlust , ; logistische Regression verwendet den Log-Loss ,

Zielfunktionen

Der Unterschied zwischen dem Scharnierverlust und diesen anderen Verlustfunktionen lässt sich am besten anhand von Zielfunktionen beschreiben – der Funktion, die das erwartete Risiko für ein gegebenes Paar von Zufallsvariablen minimiert .

Insbesondere lassen bezeichnen Bedingung der Fall , dass . In der Klassifizierungseinstellung haben wir:

Der optimale Klassifikator ist daher:

Für den Quadratverlust ist die Zielfunktion die bedingte Erwartungsfunktion, ; Für den logistischen Verlust ist es die logit-Funktion, . Obwohl diese beiden Zielfunktionen den richtigen Klassifikator als liefern, liefern sie uns mehr Informationen, als wir benötigen. Tatsächlich geben sie uns genug Informationen, um die Verbreitung von .

Andererseits kann man überprüfen, ob die Zielfunktion für den Scharnierverlust genau ist . Somit konvergiert der SVM-Klassifizierer in einem ausreichend reichhaltigen Hypothesenraum – oder äquivalent für einen geeignet gewählten Kernel – zu der einfachsten Funktion (in Bezug auf ), die die Daten korrekt klassifiziert. Dies erweitert die geometrische Interpretation von SVM – bei linearer Klassifikation wird das empirische Risiko durch jede Funktion minimiert, deren Ränder zwischen den Stützvektoren liegen, und die einfachste davon ist der max-margin-Klassifikator.

Eigenschaften

SVMs gehören zu einer Familie von verallgemeinerten linearen Klassifikatoren und können als Erweiterung des Perzeptrons interpretiert werden . Sie können auch als Spezialfall der Tikhonov-Regularisierung betrachtet werden . Eine besondere Eigenschaft ist, dass sie gleichzeitig den empirischen Klassifikationsfehler minimieren und den geometrischen Spielraum maximieren ; daher werden sie auch als Maximum- Margin-Klassifikatoren bezeichnet .

Ein Vergleich des SVM mit anderen Klassifikatoren wurde von Meyer, Leisch und Hornik angestellt.

Parameterauswahl

Die Effektivität von SVM hängt von der Auswahl des Kernels, den Parametern des Kernels und dem Soft-Margin-Parameter ab . Eine gängige Wahl ist ein Gaußscher Kernel, der einen einzigen Parameter hat . Die beste Kombination von und wird oft durch eine Gittersuche mit exponentiell wachsenden Folgen von und ausgewählt , zum Beispiel ; . Typischerweise wird jede Kombination von Parameterauswahlen mittels Kreuzvalidierung überprüft , und die Parameter mit der besten Kreuzvalidierungsgenauigkeit werden ausgewählt. Alternativ können neuere Arbeiten zur Bayes-Optimierung verwendet werden, um und auszuwählen , was oft die Auswertung von weit weniger Parameterkombinationen als die Gittersuche erfordert. Das endgültige Modell, das zum Testen und zum Klassifizieren neuer Daten verwendet wird, wird dann mit den ausgewählten Parametern auf dem gesamten Trainingssatz trainiert.

Themen

Zu den möglichen Nachteilen der SVM gehören die folgenden Aspekte:

  • Erfordert vollständige Kennzeichnung der Eingabedaten
  • Unkalibrierte Klassenmitgliedschaftswahrscheinlichkeiten – SVM stammt aus Vapniks Theorie, die das Schätzen von Wahrscheinlichkeiten auf endlichen Daten vermeidet
  • Die SVM ist nur für Zweiklassenaufgaben direkt anwendbar. Daher müssen Algorithmen angewendet werden, die die Mehrklassenaufgabe auf mehrere binäre Probleme reduzieren; siehe den Abschnitt Mehrklassen-SVM .
  • Parameter eines gelösten Modells sind schwer zu interpretieren.

Erweiterungen

Support-Vektor-Clustering (SVC)

SVC ist eine ähnliche Methode, die ebenfalls auf Kernelfunktionen aufbaut, aber für unüberwachtes Lernen geeignet ist. Sie gilt als grundlegende Methode der Data Science .

Mehrklassen-SVM

Multiclass-SVM zielt darauf ab, Instanzen Labels zuzuweisen, indem Support-Vektor-Maschinen verwendet werden, wobei die Labels aus einer endlichen Menge mehrerer Elemente gezogen werden.

Der vorherrschende Ansatz dafür besteht darin, das einzelne Mehrklassenproblem in mehrere binäre Klassifikationsprobleme zu reduzieren . Zu den üblichen Methoden für eine solche Reduzierung gehören:

  • Erstellen von binären Klassifikatoren, die zwischen einem der Labels und dem Rest ( one-versus-all ) oder zwischen jedem Klassenpaar ( one-versus-one ) unterscheiden. Die Klassifikation neuer Instanzen für den Eins-gegen-Alle-Fall erfolgt durch eine Winner-takes-All-Strategie, bei der der Klassifikator mit der höchsten Ausgabefunktion die Klasse zuweist (es ist wichtig, dass die Ausgabefunktionen kalibriert sind, um vergleichbare Ergebnisse zu erzielen ). Beim Eins-gegen-Eins-Ansatz erfolgt die Klassifizierung durch eine Max-Wins-Abstimmungsstrategie, bei der jeder Klassifizierer die Instanz einer der beiden Klassen zuordnet, dann die Stimme für die zugewiesene Klasse um eine Stimme erhöht wird und schließlich die Klasse mit den meisten Stimmen bestimmt die Instanzklassifizierung.
  • Gerichteter azyklischer Graph SVM (DAGSVM)
  • Fehlerkorrigierende Ausgabecodes

Crammer und Singer schlugen ein Mehrklassen-SVM-Verfahren vor, das das Mehrklassen-Klassifikationsproblem in ein einzelnes Optimierungsproblem umwandelt , anstatt es in mehrere binäre Klassifikationsprobleme zu zerlegen. Siehe auch Lee, Lin und Wahba und Van den Burg und Groenen.

Transduktive Stützvektormaschinen

Transduktive Support-Vektor-Maschinen erweitern SVMs dahingehend, dass sie auch teilweise markierte Daten beim semi-überwachten Lernen behandeln können, indem sie den Prinzipien der Transduktion folgen . Hier erhält der Lernende neben dem Trainingsset auch ein Set

von zu klassifizierenden Testbeispielen. Formal wird eine transduktive Stützvektormaschine durch das folgende primäre Optimierungsproblem definiert:

Minimieren (in )

vorbehaltlich (für alle )

und

Transduktive Stützvektormaschinen wurden 1998 von Vladimir N. Vapnik eingeführt.

Strukturierte SVM

SVMs wurden zu strukturierten SVMs verallgemeinert , bei denen der Etikettenraum strukturiert und möglicherweise unendlich groß ist.

Rückschritt

Support-Vektor-Regression (Vorhersage) mit unterschiedlichen Schwellenwerten ε . Wenn ε ansteigt, wird die Vorhersage weniger fehleranfällig.

Eine Version von SVM zur Regression wurde 1996 von Vladimir N. Vapnik , Harris Drucker, Christopher JC Burges, Linda Kaufman und Alexander J. Smola vorgeschlagen. Diese Methode wird als Support-Vektor-Regression (SVR) bezeichnet. Das durch die Unterstützungsvektorklassifizierung (wie oben beschrieben) erzeugte Modell hängt nur von einer Teilmenge der Trainingsdaten ab, da die Kostenfunktion für den Aufbau des Modells sich nicht um Trainingspunkte kümmert, die außerhalb des Spielraums liegen. Analog hängt das von SVR erzeugte Modell nur von einer Teilmenge der Trainingsdaten ab, da die Kostenfunktion zum Erstellen des Modells alle Trainingsdaten in der Nähe der Modellvorhersage ignoriert. Eine andere SVM-Version, die als Least -Squares Support-Vector Machine (LS-SVM) bekannt ist, wurde von Suykens und Vandewalle vorgeschlagen.

Den ursprünglichen SVR zu trainieren bedeutet, zu lösen

minimieren
unterliegt

wobei ist eine Trainingsstichprobe mit Zielwert . Das innere Produkt plus Achsenabschnitt ist die Vorhersage für diese Stichprobe und ein freier Parameter, der als Schwellenwert dient: Alle Vorhersagen müssen innerhalb eines Bereichs der wahren Vorhersagen liegen. Slack-Variablen werden in der Regel in den obigen hinzugefügt, um Fehler zu berücksichtigen und eine Annäherung zu ermöglichen, falls das obige Problem nicht durchführbar ist.

Bayes-SVM

Im Jahr 2011 wurde es von Polson und Scott gezeigt , dass die SVM eine zugibt Bayesian Interpretation durch die Technik der Daten Augmentation . Bei diesem Ansatz wird die SVM als grafisches Modell betrachtet (bei dem die Parameter über Wahrscheinlichkeitsverteilungen verbunden sind). Diese erweiterte Ansicht ermöglicht die Anwendung von Bayes- Techniken auf SVMs, wie flexible Feature-Modellierung, automatische Hyperparameter- Abstimmung und prädiktive Unsicherheitsquantifizierung . Vor kurzem wurde von Florian Wenzel eine skalierbare Version der Bayesian SVM entwickelt , die die Anwendung von Bayesian SVMs auf Big Data ermöglicht . Florian Wenzel hat zwei verschiedene Versionen entwickelt, ein Variational Inference (VI)-Schema für die Bayesian Kernel Support Vector Machine (SVM) und eine stochastische Version (SVI) für die lineare Bayesian SVM.

Implementierung

Die Parameter der Hyperebene mit maximalem Rand werden durch Lösen der Optimierung abgeleitet. Es gibt mehrere spezialisierte Algorithmen zur schnellen Lösung des Problems der quadratischen Programmierung (QP), das sich aus SVMs ergibt, die sich hauptsächlich auf Heuristiken zum Aufteilen des Problems in kleinere, besser handhabbare Teile verlassen.

Ein anderer Ansatz besteht darin, eine Methode mit inneren Punkten zu verwenden , die Newton- ähnliche Iterationen verwendet, um eine Lösung der Karush-Kuhn-Tucker-Bedingungen des primären und des dualen Problems zu finden. Anstatt eine Abfolge von aufgeschlüsselten Problemen zu lösen, löst dieser Ansatz das Problem direkt insgesamt. Um die Lösung eines linearen Systems mit der großen Kernel-Matrix zu vermeiden, wird im Kernel-Trick oft eine niederrangige Approximation an die Matrix verwendet.

Eine weitere gängige Methode ist der sequentielle Minimaloptimierungsalgorithmus (SMO) von Platt , der das Problem in zweidimensionale Teilprobleme zerlegt, die analytisch gelöst werden, wodurch ein numerischer Optimierungsalgorithmus und eine Matrixspeicherung überflüssig werden. Dieser Algorithmus ist konzeptionell einfach, leicht zu implementieren, im Allgemeinen schneller und hat bessere Skalierungseigenschaften für schwierige SVM-Probleme.

Der Spezialfall der linearen Support-Vektor-Maschinen kann effizienter durch die gleiche Art von Algorithmen gelöst werden, die verwendet werden, um seine nahe verwandte logistische Regression zu optimieren ; diese Klasse von Algorithmen umfasst Subgradientenabstieg (zB PEGASOS) und Koordinatenabstieg (zB LIBLINEAR). LIBLINEAR hat einige attraktive Trainingszeiteigenschaften. Jede Konvergenziteration benötigt eine lineare Zeit in der Zeit, die zum Lesen der Zugdaten benötigt wird, und die Iterationen haben auch eine Q-lineare Konvergenzeigenschaft , was den Algorithmus extrem schnell macht.

Die allgemeinen Kernel-SVMs können auch mit Subgradient Descent (zB P-packSVM) effizienter gelöst werden , insbesondere wenn Parallelisierung erlaubt ist.

Kernel-SVMs sind in vielen Machine-Learning-Toolkits verfügbar, darunter LIBSVM , MATLAB , SAS , SVMlight, kernlab , scikit-learn , Shogun , Weka , Shark , JKernelMachines , OpenCV und andere.

Die Vorverarbeitung der Daten (Standardisierung) wird dringend empfohlen, um die Genauigkeit der Klassifizierung zu verbessern. Es gibt einige Standardisierungsmethoden, wie Min-Max, Normalisierung durch Dezimalskalierung, Z-Score. Die Subtraktion des Mittelwerts und die Division durch die Varianz jedes Merkmals wird normalerweise für SVM verwendet.

Siehe auch

Verweise

Weiterlesen

Externe Links

  • libsvm , LIBSVM ist eine beliebte Bibliothek von SVM-Lernern
  • liblinear ist eine Bibliothek für große lineare Klassifikationen einschließlich einiger SVMs
  • SVM light ist eine Sammlung von Softwaretools zum Lernen und Klassifizieren mit SVM
  • Die SVMJS-Live-Demo ist eine GUI-Demo für die JavaScript- Implementierung von SVMs