Die Beziehung zwischen der Anzahl der Unterstützungsvektoren und der Anzahl der Merkmale

12

Ich habe eine SVM für einen bestimmten Datensatz ausgeführt und Folgendes festgestellt: Wenn ich die Anzahl der Features zum Erstellen des Klassifikators ändere, wird auch die Anzahl der resultierenden Unterstützungsvektoren geändert.

Ich würde gerne wissen, wie man ein solches Szenario erklärt.

machine-learning classification svm kernel-trick user3269
quelle
Was war der Typ und Stil dieser zusätzlichen Funktionen? Wo sehen sie aus wie Varianten der vorhandenen Features oder wie einige neue Features, von denen Sie dachten, dass sie zusätzliches Auflösungsvermögen haben?
Philip Oakley
Dies ist ein Dokumentklassifizierungsproblem, und die zusätzlichen Funktionen sind nur Wörter. Ich habe Unigramm verwendet, um Feature-Space zu erstellen.
User3269
Bei der Antwort von @ marc, die die Änderung bewirkt hat, ist die Anzahl der Vektoren mit der Anzahl der Merkmale gestiegen, oder umgekehrt.
Philip Oakley
@Phillip, meine ursprüngliche Antwort war falsch. Ich denke, die bearbeitete Antwort ist jetzt genau.
Marc Shivers

Antworten:

13

Wenn Sie sich das Optimierungsproblem ansehen, das SVM löst:

minw,ξ,b{12‖w‖2+C∑i=1nξi}

st für alle i = 1 , ... nyi(w⋅xi−b)≥1−ξi,    ξi≥0,i=1,…n

die Stützvektoren sind diejenigen denen das entsprechende ξ i > 0 ist . Mit anderen Worten, es handelt sich um Datenpunkte, die entweder falsch klassifiziert sind oder sich in der Nähe der Grenze befinden.xiξi>0

wj=0j

Wenn Sie diese beiden Optimierungsprobleme vergleichen und die Mathematik durcharbeiten, stellt sich heraus, dass zwischen der Anzahl der Features und der Anzahl der Unterstützungsvektoren keine harte Beziehung besteht. Es könnte in beide Richtungen gehen.

Es ist nützlich, über einen einfachen Fall nachzudenken. Stellen Sie sich einen zweidimensionalen Fall vor, in dem Ihre negativen und positiven Merkmale um (-1, -1) bzw. (1,1) gruppiert sind und mit einer diagonalen Trennhyperebene mit 3 Stützvektoren getrennt werden können. Stellen Sie sich nun vor, Sie lassen die y-Achsen-Funktion fallen, damit Ihre Daten jetzt auf die x-Achse projiziert werden. Wenn die Daten noch trennbar sind, z. B. bei x = 0, bleiben wahrscheinlich nur zwei Support-Vektoren übrig, einer auf jeder Seite. Wenn Sie also das y-Merkmal hinzufügen, erhöht sich die Anzahl der Support-Vektoren. Wenn die Daten jedoch nicht mehr trennbar sind, erhalten Sie mindestens einen Stützvektor für jeden Punkt, der auf der falschen Seite von x = 0 liegt. In diesem Fall würde das Hinzufügen des y-Merkmals die Anzahl der Stützvektoren verringern.

Wenn diese Intuition korrekt ist, wenn Sie in sehr hochdimensionalen Merkmalsräumen arbeiten oder einen Kernel verwenden, der einem hochdimensionalen Merkmalsraum zugeordnet ist, sind Ihre Daten mit größerer Wahrscheinlichkeit trennbar, sodass das Hinzufügen eines Merkmals dazu neigt um nur einen weiteren Support-Vektor hinzuzufügen. Wenn Ihre Daten derzeit nicht trennbar sind und Sie eine Funktion hinzufügen, die die Trennbarkeit erheblich verbessert, ist es wahrscheinlicher, dass die Anzahl der Unterstützungsvektoren abnimmt.

Marc Shivers
quelle