nonseparable case of classification problem (SVM)

Question

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

Answer 1

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.