3
$\begingroup$

I am learning Soft Margin Classification (SVM) right now. In cases when the classes are non-separable by the usual hyperplane with a margin $M >0$, we modify the constraints and say that it is ok to misclassify some observations for more robustness and better results in the training data.

In Introduction to Stat Learning, the authors offered to modify the constraint from the case when the classification is separated by a hyperplane with a margin $M$.

There are two modifications to the constraint that are introduced:

First: $y_i(x_i^T\beta + \beta_0) \geq M - \xi_i$

Second: $y_i(x_i^T\beta + \beta_0) \geq M(1 - \xi_i)$

In this case, $M$ is the margin width, and $\xi_i$ is the 'slack' variable. These two modifications are very very different from each other, and understandbly would lead to two different results. I do not understand why the authors chose one over the other, and the explanation is rather unclear. It adds that the first results to a nonconvex optimization problem, while the second becomes a convex one.

Please send some insights why this is so. I do not understand the intuition why one is chosen over the other since they look the same to me.

Thanks

$\endgroup$

1 Answer 1

0
$\begingroup$

Actually, the first is convex, and the second is not.

Specifically, the first constraint is linear, as all of the variables $\beta, \beta_0, M, \xi_i$ appear with (data-dependent) constants. The second constraint is not convex as the term $M \xi_i$ appears when multiplying $M$ through on the right hand side.

The second formulation would represent a "relative" approach where $\xi_i$ indicates "how much" the point is misclassified on a 0-1 scale, and for >=1 is fully misclassified.

Note that the standard SVM formulation actually fixes $M=1$ and thus $\xi_i$ does indeed represent that "relative" approach.

$\endgroup$

Your Answer

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

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