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

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?

svm lagrange-multipliers Michael Litvin
quelle

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:

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) : $\alpha_i$ $\alpha_i=0$

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 . $y_i(\mathbf{w}^T\mathbf{x}_i+b) = 1$ $\mathbf{x}_i$ $\mathbf{x}_i$ $\alpha_i$ $C$

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

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