0
$\begingroup$

I understand that SVM is about solving the constrained optimization such that

$$\min_{\mathbf{w}} \dfrac{1}{2} \mathbf{w}^T\mathbf{w}$$ subject to $$y_i(\mathbf{w}^T\mathbf{x_i}+b)\geq{1}, i=1, 2, ...,n$$


And this is handled using nonlinear optimization method Karush–Kuhn–Tucker approach where one step is based on the necessary complementary slackness condition such that

$${\alpha}_i\left(y_i(\mathbf{w}^T\mathbf{x_i}+b)-1\right)=0, i=1, 2, ...,n$$ has to be satified.


Because for non-gutter dots (i.e., the points not on the edge of the separating hyperplane), we have

$$y_i(\mathbf{w}^T\mathbf{x_i}+b)-1 > 0$$

the corresponding multiplier $\alpha_i$ then must be $0$. But my question is for gutter points, because

$$y_i(\mathbf{w}^T\mathbf{x_i}+b)-1 = 0$$

we know that the corresponding multiplier $\alpha_i$ should be non-negative, but are they necessarily positive? In other words, if I define support vector as any $\mathbf{x_i}$ on the gutter, then is this the same as if I define support vector as any $\mathbf{x_i}$ whose multiplier is positive?

$\endgroup$
1
  • $\begingroup$ Note that your SVM formulation is for data that can be separated, and that $b$ is an optimization variable. $\endgroup$ – LinAlg Nov 5 '16 at 22:31
2
$\begingroup$

Complementary slackness doesn't require that one of the two values must be non-zero. It simply requires that one of the multiplier or the corresponding slack variables is 0. It's certainly possible that both could be 0.

$\endgroup$
3
  • $\begingroup$ Appreciate the theoretical part, but in the context of SVM, do you know if it's possible that a gutter point has a $0$ multiplier? Just to make sure. $\endgroup$ – Nicholas Nov 5 '16 at 20:08
  • $\begingroup$ Yes- I believe you can construct an example in which there are multiple points on the separating hyperplane that does this. $\endgroup$ – Brian Borchers Nov 5 '16 at 20:57
  • 2
    $\begingroup$ An example is when the same point occurs twice. Then the multipliers are not uniquely defined. If they are both nonzero, you can reduce one to zero and increase the other one so that the sum remains constant. $\endgroup$ – LinAlg Nov 5 '16 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.