2
$\begingroup$

I was trying to understand the derivation of SVM decision boundary. Suppose my decision boundary is y-x-1=0.

Now in the book it was written that (y-x-1) = +/-(1), are the equation of the maximum margins.

But my question is why are we choosing a distance of 1 from the decision boundary ? How do we even know that we would be able to hit the support vectors just at the distance of +/-(1) from the decision boundary ?

Moreover how can we say, that if we are able to hit a support vector at a distance of +1 from decision boundary then it will be there exactly at -1 (and not at -3, -5, -10... etc for that matter) ? i.e. how are we so sure that at exactly +/-(1) "on both sides" from decision boundary we will be able to hit support vectors.

$\endgroup$
2
$\begingroup$

You seem to misunderstand support vectors. Support vectors are not at distance exactly 1 to the separating hyperplane.

Support vectors arise as a result from the constraints in the optimization problem. The constraints basically require that every data instance should be out of the classification margin and on the right side of the separating hyperplane defined by $\mathbf{w}$ and $b$. The following Wikipedia image illustrates this idea nicely:

wikipedia explanation of SVM margin

For positive instances $\mathbf{x}_p$, we require that $\mathbf{w}^T\mathbf{x}_p - b \geq 1$ and for negative instances $\mathbf{x}_n$ this means $\mathbf{w}^T\mathbf{x}_n - b \leq -1$. Through clever use of the binary class labels (e.g. $y_i \in \{-1, +1\}$) we can write this in a single form. For notational simplicity, these constraints can be written as follows for linear SVM:

$$y_i\big(\mathbf{w}^T\mathbf{x}_i - b\big) \geq 1 - \xi_i, \quad \forall i$$

where $\mathbf{y}$ is the vector of training labels, $\mathbf{w}$ is the separating hyperplane, $\phi(\cdot)$ is the embedding function and $b$ is the bias. $\xi$ is a vector of slack variables which allow soft margin classification. These slack variables are positive when the constraint is violated and zero otherwise. Such a constraint exists for every training instance.

Support vectors are those instances for which $\xi_i$ is necessarily nonzero, e.g. $\mathcal{S} = \{i : y_i\big(\mathbf{w}^T\mathbf{x}_i - b\big) < 1\}$. This occurs for instances that are either misclassified or those close to the separating hyperplane (distance less than 1). For example: if there were positive instances (black dots) below the dashed line $\mathbf{w}^T\mathbf{x}-b = 1$ on the figure, those instances would also be support vectors.

$\endgroup$
  • $\begingroup$ Thanks Marc, but Im not able to follow that heavy notation stuff you have written. Thats why I put up my question in simple mathematical equations. Is there a simpler version of your answer, which is more of an intuitive version , with perhaps simpler maths notations. $\endgroup$ – sunita Apr 6 '14 at 19:06
  • $\begingroup$ @sunita it should be more clear now. $\endgroup$ – Marc Claesen Apr 6 '14 at 19:15
  • $\begingroup$ Thanks Marc. Im really sorry but how are we so sure that we will find the +ve class(black circles) and -ve class support vectors(white circles) at exactly the same distance from the decision boundary( wx-b=0) $\endgroup$ – sunita Apr 6 '14 at 19:23
  • $\begingroup$ @sunita we aren't. They don't have to be at distance 1 to the separating hyperplane. Support vectors are all "hard" training instances that are either misclassified (e.g. on the wrong side of the hyperplane) or within the margin (e.g. distance to the separating hyperplane smaller than 1). Such points are not shown on the figure I included but this does happen in practice. The SVs only lie on the margin boundaries in the cases of perfect training classification and hard margin SVM. $\endgroup$ – Marc Claesen Apr 6 '14 at 19:25
  • $\begingroup$ Did not explain why it is 1 or -1 in the dashed line boundary. $\endgroup$ – Belter Apr 15 '18 at 3:35

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.