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
    Commented Nov 5, 2016 at 22:31

1 Answer 1

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
    Commented Nov 5, 2016 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$ Commented Nov 5, 2016 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
    Commented Nov 5, 2016 at 22:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .