For the primal form of the learning objective for the max-margin classifier, the minimum margin is 1 (e.g. $y^{(i)}(w^{T}x^{(i)} + b) \geq 1$).

I am looking to prove that when the dataset is linearly separable, replacing the 1 by an arbitrary $\hat{\gamma} > 0$ does not change the optimal hyperplane.

My intuition is that any change in the minimum margin would have to be to a value less than the current value of 1. Otherwise, $\hat{\gamma}$ could shoot up to $\infty$ which is nonsensical. And subsequently, decreasing the minimum margin when the dataset is linearly separable does not affect the optimal hyperplane. It lowers the margin requirement, but there is still only one optimal hyperplane - the one that maximizes the margins.

How do I formalize this intuition?

I considered an approach like this:

Assume $\hat{\gamma} > 0$ and $y^{(i)}(w^{T}x^{(i)} + b) \geq \hat{\gamma}$. We can also take the original decision boundary $y^{(i)}(w^{T}x^{(i)} + b) \geq 1$ and multiply by $\hat{\gamma}$ to obtain $\hat{\gamma}y^{(i)}(w^{T}x^{(i)} + b) \geq \hat{\gamma}$. Then we have the equality $y^{(i)}(w^{T}x^{(i)} + b) = \hat{\gamma}y^{(i)}(w^{T}x^{(i)} + b)$ which implies that $\hat{\gamma}$ must be 1 and that there is only one optimal decision boundary. I'm not too sure if this approach is correct, however.

Any advice would be greatly appreciated!

  • $\begingroup$ I think you are on the right track when you multiply both sides by gamma but then you lost it when you concluded that this implies that gamma must be equal to one. $\endgroup$ – Aaron Nov 8 '16 at 18:31

Your Answer

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

Browse other questions tagged or ask your own question.