3
$\begingroup$

When finding the maximum margin separator in the primal form we have the quadratic program

$$min\frac{1}{2}||\theta||^2$$ $$\text{ subject to: } y^{(t)}(\theta \cdot x^{(t)} + \theta_0) \geq 1, \ t=1,...,n,$$

saying basically to find the maximum margin separator. The margin size will be:

$$\frac{1}{||\theta||}.$$

Does the size of the margin change if we change the constants of the constraint?

That is, if we have

$$\text{ subject to: } y^{(t)}(\theta \cdot x^{(t)} + \theta_0) \geq k, \ t=1,...,n,$$

instead of 1?

If it does not matter, why doesn't this matter? How is it an equivalent formulation regardless of the exact constants for the constraint?

$\endgroup$
2
$\begingroup$

I think that the size of the margin will change, but we care about the direction more than the absolute size.

Suppose we solved the problem with $1$ as the lower bound and came up with $\theta$ and $\theta_0$. Then if we consider $k \theta$, $k \theta_0$ with $k \geq 0$ we satisfy the primal constraints with $k$ as a lower bound and the margin size will be $\frac 1 {k \| \theta \|}$. But this change isn't really meaningful, since we're still pointing in the same direction and have just made the vector a bit bigger or smaller.

In Andrew Ng's course notes he refers to two kinds of margins, functional, where we care about the absolute distance of our points from the hyperplanes, and geometric, where we scale $\theta$ and $\theta_0$ by $\| \theta \|$ and then find the maximum distance under this constraint. One usually formulates the problem in terms of geometric margins but, through some transformations, you can show that a functional margin constrained to be 1, or really anything positive, is equivalent.

So by choosing $1$ as the functional margin we've just chosen a scaling of the direction that separates the points the best.

$\endgroup$

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.