Warum sind die Lagrange-Multiplikatoren für SVMs spärlich?

8

Ich habe gelesen, dass für den Maximal Margin Classifier SVM nach Lösung des dualen Problems die meisten Lagrange-Multiplikatoren Nullen sind. Nur diejenigen, die den Unterstützungsvektoren entsprechen, erweisen sich als positiv.

Warum ist das so?

Michael Litvin
quelle
1
Der Wikipedia-Artikel über Support Vector Machines antwortet darauf mit dem Hinweis, dass die Lagrange-Multiplikatoren ungleich Null Punkten am Rand entsprechen, von denen es normalerweise nur sehr wenige geben würde.
whuber

Antworten:

4

Die Lagrange-Multiplikatoren im Kontext von SVMs werden typischerweise als . Die Tatsache, dass man oft beobachtet, dass die meisten ist eine direkte Folge der dualen Komplementaritätsbedingungen von Karush-Kuhn-Tucker (KKT) :αiαi=0

Geben Sie hier die Bildbeschreibung ein

Da iff an der SVM-Entscheidungsgrenze liegt, ist dh ein Unterstützungsvektor unter der Annahme, dass in der Trainingssatz, und in den meisten Fällen sind nur wenige Trainingsvektoren Unterstützungsvektoren, wie in den Kommentaren ausgeführt, bedeutet dies, dass die meisten 0 oder .yich(wT.xich+b)=1xichxichαichC.


In den CS229-Vorlesungsunterlagen von Andrew Ng zu SVMs werden die Bedingungen der doppelten Komplementarität von Karush-Kuhn-Tucker (KKT) vorgestellt:

Geben Sie hier die Bildbeschreibung ein

Geben Sie hier die Bildbeschreibung ein

Geben Sie hier die Bildbeschreibung ein

Geben Sie hier die Bildbeschreibung ein

Beachten Sie, dass wir einen Fall erstellen können, in dem alle Vektoren im Trainingssatz Unterstützungsvektoren sind: siehe z. B. diese Frage zur Unterstützungsvektormaschine .

Franck Dernoncourt
quelle