Welche Beziehung besteht zwischen der Anzahl der Unterstützungsvektoren und den Trainingsdaten und der Leistung der Klassifizierer? [geschlossen]

Ich verwende LibSVM, um einige Dokumente zu klassifizieren. Die Dokumente scheinen etwas schwierig zu klassifizieren, wie die Endergebnisse zeigen. Beim Training meiner Modelle ist mir jedoch etwas aufgefallen. und das heißt: Wenn mein Trainingssatz zum Beispiel 1000 ist, werden ungefähr 800 von ihnen als Unterstützungsvektoren ausgewählt. Ich habe überall gesucht, um herauszufinden, ob dies eine gute oder eine schlechte Sache ist. Ich meine, gibt es einen Zusammenhang zwischen der Anzahl der Unterstützungsvektoren und der Leistung der Klassifikatoren? Ich habe diesen vorherigen Beitrag gelesen, führe aber eine Parameterauswahl durch und bin mir auch sicher, dass die Attribute in den Merkmalsvektoren alle geordnet sind. Ich muss nur die Beziehung kennen. Vielen Dank. ps: Ich benutze einen linearen Kernel.

Support Vector Machines sind ein Optimierungsproblem. Sie versuchen, eine Hyperebene zu finden, die die beiden Klassen mit dem größten Spielraum trennt. Die Unterstützungsvektoren sind die Punkte, die innerhalb dieses Randes liegen. Es ist am einfachsten zu verstehen, wenn Sie es von einfach zu komplex aufbauen.

Hard Margin Linear SVM

In einem Trainingssatz, in dem die Daten linear trennbar sind und Sie einen harten Rand verwenden (kein Durchhang zulässig), sind die Unterstützungsvektoren die Punkte, die entlang der unterstützenden Hyperebenen liegen (die Hyperebenen parallel zur teilenden Hyperebene an den Rändern des Randes )

Alle Unterstützungsvektoren liegen genau am Rand. Unabhängig von der Anzahl der Dimensionen oder der Größe des Datensatzes kann die Anzahl der Unterstützungsvektoren nur 2 betragen.

Soft-Margin Linear SVM

Was aber, wenn unser Datensatz nicht linear trennbar ist? Wir führen SVM mit weichem Rand ein. Wir verlangen nicht mehr, dass unsere Datenpunkte außerhalb des Randes liegen, wir lassen einige von ihnen über die Linie in den Rand streuen. Wir verwenden den Slack-Parameter C, um dies zu steuern. (nu in nu-SVM) Dies gibt uns einen größeren Spielraum und einen größeren Fehler im Trainingsdatensatz, verbessert jedoch die Verallgemeinerung und / oder ermöglicht es uns, eine lineare Trennung von Daten zu finden, die nicht linear trennbar ist.

Die Anzahl der Unterstützungsvektoren hängt nun davon ab, wie viel Spiel wir zulassen und wie die Daten verteilt werden. Wenn wir eine große Menge an Spiel zulassen, haben wir eine große Anzahl von Unterstützungsvektoren. Wenn wir nur sehr wenig Spiel zulassen, haben wir nur sehr wenige Unterstützungsvektoren. Die Genauigkeit hängt davon ab, ob der richtige Durchhang für die zu analysierenden Daten gefunden wird. Bei einigen Daten ist es nicht möglich, ein hohes Maß an Genauigkeit zu erzielen. Wir müssen einfach die bestmögliche Anpassung finden.

Nichtlineare SVM

Dies bringt uns zu nichtlinearer SVM. Wir versuchen immer noch, die Daten linear zu teilen, aber wir versuchen jetzt, dies in einem höherdimensionalen Raum zu tun. Dies geschieht über eine Kernelfunktion, die natürlich einen eigenen Parametersatz hat. Wenn wir dies zurück in den ursprünglichen Feature-Space übersetzen, ist das Ergebnis nicht linear:

Die Anzahl der Unterstützungsvektoren hängt immer noch davon ab, wie viel Spiel wir zulassen, aber auch von der Komplexität unseres Modells. Für jede Drehung und Drehung im endgültigen Modell in unserem Eingaberaum müssen ein oder mehrere Unterstützungsvektoren definiert werden. Letztendlich ist die Ausgabe einer SVM die Unterstützungsvektoren und ein Alpha, was im Wesentlichen definiert, wie viel Einfluss dieser spezifische Unterstützungsvektor auf die endgültige Entscheidung hat.

Hier hängt die Genauigkeit vom Kompromiss zwischen einem hochkomplexen Modell, das möglicherweise zu den Daten passt, und einem großen Spielraum ab, der einige der Trainingsdaten im Interesse einer besseren Verallgemeinerung falsch klassifiziert. Die Anzahl der Unterstützungsvektoren kann von sehr wenigen bis zu jedem einzelnen Datenpunkt reichen, wenn Sie Ihre Daten vollständig überanpassen. Dieser Kompromiss wird über C und durch die Auswahl von Kernel- und Kernel-Parametern gesteuert.

Ich nehme an, als Sie Leistung sagten, bezogen Sie sich auf Genauigkeit, aber ich dachte, ich würde auch in Bezug auf die Komplexität der Berechnungen mit Leistung sprechen. Um einen Datenpunkt mit einem SVM-Modell zu testen, müssen Sie das Punktprodukt jedes Unterstützungsvektors mit dem Testpunkt berechnen. Daher ist die rechnerische Komplexität des Modells in der Anzahl der Unterstützungsvektoren linear. Weniger Unterstützungsvektoren bedeuten eine schnellere Klassifizierung der Testpunkte.

Eine gute Ressource: Ein Tutorial zur Unterstützung von Vektormaschinen für die Mustererkennung

800 von 1000 sagen Ihnen im Grunde, dass die SVM fast jedes einzelne Trainingsbeispiel verwenden muss, um den Trainingssatz zu codieren. Das sagt Ihnen im Grunde, dass Ihre Daten nicht sehr regelmäßig sind.

Klingt so, als hätten Sie große Probleme mit zu wenig Trainingsdaten. Denken Sie vielleicht auch an einige spezifische Funktionen, die diese Daten besser trennen.

Sowohl die Anzahl der Stichproben als auch die Anzahl der Attribute können die Anzahl der Unterstützungsvektoren beeinflussen, wodurch das Modell komplexer wird. Ich glaube, Sie verwenden Wörter oder sogar Ngramme als Attribute, daher gibt es ziemlich viele davon, und Modelle in natürlicher Sprache sind selbst sehr komplex. 800 Unterstützungsvektoren von 1000 Proben scheinen also in Ordnung zu sein. (Beachten Sie auch die Kommentare von @ karenu zu C / nu-Parametern, die ebenfalls einen großen Einfluss auf die SV-Anzahl haben.)

Um sich ein Bild von dieser SVM-Hauptidee zu machen. SVM arbeitet in einem mehrdimensionalen Merkmalsraum und versucht, eine Hyperebene zu finden , die alle angegebenen Stichproben trennt. Wenn Sie viele Beispiele und nur 2 Features (2 Dimensionen) haben, sehen die Daten und die Hyperebene möglicherweise folgendermaßen aus:

Hier gibt es nur 3 Unterstützungsvektoren, alle anderen stehen dahinter und spielen somit keine Rolle. Beachten Sie, dass diese Unterstützungsvektoren nur durch 2 Koordinaten definiert sind.

Stellen Sie sich nun vor, Sie haben einen dreidimensionalen Raum und somit werden Unterstützungsvektoren durch 3 Koordinaten definiert.

Dies bedeutet, dass ein weiterer Parameter (Koordinate) angepasst werden muss. Für diese Anpassung sind möglicherweise mehr Stichproben erforderlich, um die optimale Hyperebene zu finden. Mit anderen Worten, im schlimmsten Fall findet SVM nur 1 Hyperebenenkoordinate pro Probe.

Wenn die Daten gut strukturiert sind (dh Muster recht gut enthalten), werden möglicherweise nur mehrere Unterstützungsvektoren benötigt - alle anderen bleiben hinter diesen zurück. Aber Text ist sehr, sehr schlecht strukturierte Daten. SVM gibt sein Bestes, versucht, die Probe so gut wie möglich anzupassen, und verwendet daher noch mehr Proben als Tropfen als Unterstützungsvektoren. Mit zunehmender Anzahl von Abtastwerten wird diese "Anomalie" verringert (es treten unbedeutendere Abtastwerte auf), aber die absolute Anzahl von Unterstützungsvektoren bleibt sehr hoch.

Die SVM-Klassifizierung ist in Bezug auf die Anzahl der Unterstützungsvektoren (SVs) linear. Die Anzahl der SVs entspricht im schlimmsten Fall der Anzahl der Trainingsmuster, daher ist 800/1000 noch nicht der schlimmste Fall, aber es ist immer noch ziemlich schlecht.

Andererseits sind 1000 Schulungsunterlagen ein kleines Schulungsset. Sie sollten überprüfen, was passiert, wenn Sie Dokumente auf 10000s oder mehr skalieren. Wenn sich die Situation nicht verbessert, sollten Sie lineare SVMs verwenden, die mit LibLinear trainiert wurden , um Dokumente zu klassifizieren. Diese skalieren viel besser (Modellgröße und Klassifizierungszeit sind in der Anzahl der Merkmale linear und unabhängig von der Anzahl der Trainingsmuster).

Es gibt einige Verwirrung zwischen den Quellen. In dem Lehrbuch ISLR 6th Ed wird C beispielsweise als "Budget für Grenzverletzungen" beschrieben, woraus folgt, dass ein höheres C mehr Grenzverletzungen und mehr Unterstützungsvektoren ermöglicht. In SVM-Implementierungen in R und Python wird der Parameter C jedoch als "Verstoßstrafe" implementiert, was das Gegenteil ist, und dann werden Sie feststellen, dass es für höhere Werte von C weniger Unterstützungsvektoren gibt.