1
$\begingroup$

(Cross post from math.stackexchange.com because I just discovered this site)

In a Support Vector Machine, the margins are defined as $$\vec{w}\cdot\vec{x_i}+b\ge1\text{ for }x_i \text{ in class }+1$$ $$\vec{w}\cdot\vec{x_i}+b\le-1\text{ for }x_i \text{ in class }-1$$

I understand that minimizing $\Vert w \Vert$ will maximize the distance between the margins given the constraints, however I'm having a hard time with the following:

The margins are set in such a way that their y-intercepts (in 2D space) will always be 2 units apart. It's easy to see how, with this constraint, the distance between the margins will depend only on their angle, but why would we limit the vertical separation of the margins? Is there no situation in which the optimal margins would have greater vertical separation?

Edit: Horizontal margin lines come to mind. If the ideal margin lines (again, in 2D space) have a slope of zero, then the distance between them might need to be greater than (or perhaps less than) 2. Am I missing something fundamental?

$\endgroup$
0

1 Answer 1

3
$\begingroup$

Please refer to Andrew Ng's lecture note on SVM here for detailed derivation. The original optimization is to maximize $\gamma$ with the following constraints: $$y^{(i)}(w^{T}x^{(i)}+b) \geq \gamma$$ $$||w|| = 1$$ (see page 6 - 7 of the notes).

The second constraint, however, is hard to solve. So, in the derivation, the optimization is transformed from max $\gamma$ to max $\frac{\hat{\gamma}}{||w||}$ (by definition of functional and geometric margin) and the constraint becomes: $$y^{(i)}(w^{T}x^{(i)}+b) \geq \hat{\gamma}$$

Then, by introducing the scaling constraint for $w$ and $b$ such that $\hat{\gamma} = 1$, the constraint becomes $$y^{(i)}(w^{T}x^{(i)}+b) \geq 1$$

In short, the value 1 in the constraint is simply due to scaling constraint, but the geometric margin $\gamma$ is maximized and can have value greater than 1.

$\endgroup$
2
  • $\begingroup$ Those lecture notes are excellent and clear everything up and "In short, the value 1 in the constraint is simply due to scaling constraint" clears things up nicely. Thanks! $\endgroup$
    – Kyle G.
    Mar 1, 2017 at 0:41
  • $\begingroup$ After playing with some examples, I think I've found the source of my confusion: I was forgetting the fact that $\vec{w}$ scales $y$ as well, which ultimately affects the relationship between $b$ and the line's/hyperplane's y-intercept. $\endgroup$
    – Kyle G.
    Mar 2, 2017 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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