Wo genau

7

Ich habe verstanden, dass SVMs binäre, lineare Klassifizierer sind (ohne den Kernel-Trick). Sie haben Trainingsdaten(xi,yi) wo xi ist ein Vektor und yi{1,1}ist die Klasse. Da es sich um binäre lineare Klassifikatoren handelt, besteht die Aufgabe darin, eine Hyperebene zu finden, die die Datenpunkte mit der Bezeichnung trennt1 von den Datenpunkten mit dem Etikett +1.

Nehmen wir vorerst an, dass die Datenpunkte linear trennbar sind und wir keine Slack-Variablen benötigen.

Jetzt habe ich gelesen, dass das Trainingsproblem nun das folgende Optimierungsproblem ist:

  • minw,b12w2
  • st yi(w,xi+b)1

Ich glaube, ich habe verstanden, dass das Minimieren von w2 das Maximieren des Spielraums bedeutet (ich verstehe jedoch nicht, warum es hier das Quadrat ist. Würde sich etwas ändern, wenn man versuchen würde, \ | w \ | zu minimieren w?).

Ich habe auch verstanden, dass yi(w,xi+b)0 bedeutet, dass das Modell in den Trainingsdaten korrekt sein muss. Es gibt jedoch eine 1 und keine 0 . Warum?

Martin Thoma
quelle
In der Mathematik minimieren (Ableitung = 0) stellt sich heraus, dass das Quadrat wahrscheinlich eine einfachere Gleichung ist
Paparazzo
Siehe auch: Alexander Ihler: Support Vector Machines (1): Lineare SVMs, Urform auf YouTube. 25.01.2015.
Martin Thoma

Antworten:

10

Erstes Problem: Minimierung vonoder :ww2

Es ist richtig, dass man die Marge maximieren möchte. Dies geschieht tatsächlich durch Maximieren von . Dies wäre der "richtige" Weg, aber es ist ziemlich unpraktisch. Lassen Sie uns zuerst die , da es sich nur um eine Konstante handelt. Wenn nun maximal ist,muss so klein wie möglich sein. Wir können also die identische Lösung finden, indem wir minimieren .2w21ww w

wkann mit berechnet werden . Da die Quadratwurzel eine monotone Funktion ist, maximiert jeder Punkt der maximiert, auch . Um diesen Punkt zu finden, müssen wir also nicht die Quadratwurzel berechnen und können minimieren .wTwxf(x)f(x)xwTw=w2

Schließlich multiplizieren wir, da wir häufig Ableitungen berechnen müssen, den gesamten Ausdruck mit einem Faktor . Dies geschieht sehr oft, denn wenn wir und damit ableiten . So erhalten wir das Problem: Minimieren Sie .12ddxx2=2xddx12x2=x12w2

tl; dr : ja, minimieren anstelle von würde funktionieren.w12w2

Zweites Problem: oder :01

Wie bereits in der Frage angegeben, bedeutet , dass sich der Punkt auf der richtigen Seite der Hyperebene befinden muss. Dies reicht jedoch nicht aus: Wir möchten, dass der Punkt mindestens so weit wie der Rand entfernt ist (dann ist der Punkt ein Unterstützungsvektor) oder sogar noch weiter entfernt.yi(w,xi+b)0

Denken Sie an die Definition der Hyperebene.

H={xw,x+b=0} .

Diese Beschreibung ist jedoch nicht eindeutig: Wenn wir und mit einer Konstanten skalieren , erhalten wir eine äquivalente Beschreibung dieser Hyperebene. Um sicherzustellen, dass unser Optimierungsalgorithmus und nicht nur um konstante Faktoren skaliert , um einen höheren Rand zu erhalten, definieren wir, dass der Abstand eines Unterstützungsvektors von der Hyperebene immer beträgt , dh der Rand ist . Ein Unterstützungsvektor ist somit gekennzeichnet durch .wbcwb11wyi(w,xi+b)=1

Wie bereits erwähnt, möchten wir, dass alle Punkte entweder ein Unterstützungsvektor oder sogar weiter von der Hyperebene entfernt sind. Im Training fügen wir daher die Einschränkung , die genau dies sicherstellt.yi(w,xi+b)1

tl; dr : Trainingspunkte müssen nicht nur korrekt sein, sie müssen am Rand oder weiter entfernt sein.

hbaderts
quelle
Nur um zu überprüfen, ob ich es verstanden habe: Anstatt schreiben, könnten wir auch eine beliebige Konstante und schreiben , wobei ? 1ϵϵϵ>0
Martin Thoma
Im Prinzip ja. ZB in Soft-Marge SVMs (wo man für einige Fehlklassifikationen oder Punkte innerhalb des Randes erlauben), verwenden Sie , so dass Sie sein können vom Rand. Natürlich brauchen Sie dann eine Strafe, die die meisten dazu , Null oder zumindest sehr niedrig zu sein. 1ξiξiξi
Hbaderts
1
Ich denke, im obigen Kommentar hat Martin nicht nach dem Fall von weichen Rändern gefragt, bei denen Sie ein hinzufügen , um einige Punkte zu lassen, sondern nur nach dem, was passiert, wenn Sie durch eine andere positive Konstante ersetzen . Ich glaube , das Ergebnis in diesem Fall wäre das gleiche (dh Sie die gleiche Trennebene finden würde) , aber würde so skaliert werden , dass die Marge wäre statt vonξi1ϵw2ϵw2w
Tim Goodman
Dies liegt daran, dass eine Ebene senkrecht zu und vom Ursprung um in Richtung versetzt ist. Und ebenso definiert eine Ebene orthogonal zu und versetzt vom Ursprung um . Der Abstand zwischen den beiden Ebenen beträgt alsow,x+b=ϵwϵbww(w,x+b)=ϵwϵbwϵbwϵbw=2ϵw
Tim Goodman