I've read that for the Maximal Margin Classifier SVM, after solving the dual problem, most of the lagrange multipliers turn out to be zeros. Only the ones corresponding to the support vectors turn out to be positive.
Why is that?
1
-
1$\begingroup$ The Wikipedia article on Support Vector Machines answers this by pointing out that the nonzero Lagrange multipliers correspond to points on the margin, of which ordinarily there would be very few. $\endgroup$– whuber ♦Commented Apr 30, 2014 at 21:41
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
The Lagrange multipliers in the context of SVMs are typically denoted $\alpha_i$. The fact that one often observes that most $\alpha_i=0$ is a direct consequence of the Karush-Kuhn-Tucker (KKT) dual complementarity conditions:
Since $y_i(\mathbf{w}^T\mathbf{x}_i+b) = 1$ iff $\mathbf{x}_i$ is on the SVM decision boundary, i.e. is a support vector assuming $\mathbf{x}_i$ is in the training set, and in most cases few training vectors are support vectors, as whuber pointed out in the comments, it means that most $\alpha_i$ are 0 or $C$.
Andrew Ng's CS229 Lecture notes on SVMs introduces the Karush-Kuhn-Tucker (KKT) dual complementarity conditions:
Note that we can create some case where all vectors in the training set are support vectors: e.g. see this Support Vector Machine Question.
answered Dec 29, 2016 at 0:10
-
$\begingroup$ According to the fifth (red box) constrained, $a_i = 0$ ONLY IF (not iff) $g_i(w) \neq 0$. This means that if $g_i(w) = 0$ (being on the margin) it doesn't guarantee that $a_i = 0$. So can some points on the margin have $a_i = 0$? $\endgroup$ Commented Dec 14, 2022 at 16:23
-
$\begingroup$ That is correct. Points on the margin may have $\alpha \in [0,C]$ - this is generally the "shadow price" of the constraint. $\endgroup$– MotiNKCommented Dec 20, 2022 at 13:15