What happens when we train a basic support vector machine (linear kernel and no soft-margin) on non-linearly separable data? The optimisation problem is not feasible, so what does the minimisation algorithm return?


I think basic support vector machine means hard-margin SVM. So, let's review:

What is a Hard-Margin SVM

In short, we want to find a hyperplane with the largest margin which be able to separate all observations correctly in our training sample space.

The optimisation problem in hard-margin SVM

Given the above definition, what is the optimisation problem which we need to solve?

  1. The largest margin hyperplane: We want max(margin)
  2. Be able to separate all observations correctly: We need to optimise margin and also satisfy the constraint: No in-sample errors

What happens when we train a linear SVM on non-linearly separable data?

Back to your question, since you mentioned the training data set is not linearly separable, by using hard-margin SVM without feature transformations, it's impossible to find any hyperplane which satisfies "No in-sample errors".

Normally, we solve SVM optimisation problem by Quadratic Programming, because it can do optimisation tasks with constraints. If you use Gradient Descent or other optimisation algorithms which without satisfying the constraints of hard-margin SVM, you should still get a result, but that's not a hard-margin SVM hyperplane.

By the way, with non-linearly separable data, usually we choose

  • hard-margin SVM + feature transformations
  • use soft-margin SVM directly (In practical, soft-margin SVM usually get good results)
  • $\begingroup$ thanks for your answer. So the SVM packages in eg R or Python do not use quadratic programming methods when the data is non-linearly separable? $\endgroup$ – SVM Jan 25 '15 at 10:07
  • $\begingroup$ Not sure about what svm libraries you use. I use libsvm and different svm tools may use different svm solvers. To find better svm solvers is another research topic. QP is the basic way to solve svm. $\endgroup$ – fansia Jan 25 '15 at 10:37

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.