max-margin linear separator using libsvm

Question

I have a set of N data points X with +/- labels for which I'd like to calculate the max-margin linear separator (aka classifier, hyperplane) or fail if no such linear separator exist.

I do not want to avoid overfitting in the context of this question, as I do so elsewhere. So no slack variables ; no cross-validation ; no limits on the number of support vectors ; just find max-margin separator or fail.

How to I use libsvm to do so? I believe you can't give c=0 in C-SVM and you can't give nu=1 in nu-svm.

Related question (which I think didn't provide an answer): Which of the parameters in LibSVM is the slack variable?

Answer 1

In the case of C-SVM, you should use a linear kernel and a very large C value (or nu = 0.999... for nu-SVM). If you still have slacks with this setting, probably your data is not linearly separable.

Quick explanation: the C-SVM optimization function tries to find the hyperplane having maximum margin and lowest misclassification costs at the same time. The misclassification costs in the C-SVM formulation is defined by: distance from the misclassified point to its correct side of the hyperplane, multiplied by C. If you increase the C value (or nu value for nu-SVM), every misclassified point will be too costly and an hyperplane that separates the data perfectly will be preferable for the optimization function.