3
$\begingroup$

When we have linearly inseparable datasets and we are using machine learning algorithms such as SVMs, we use kernels to implicitly map datapoints into a feature space that makes them linearly separable.

But how do we know if a kernel has indeed, implicitly, been successful in making the datapoints linearly separable in the new feature space? What is the guarantee?

|improve this question
$\endgroup$
  • $\begingroup$ There's a great intuitive + mathematical answer available here (see "1. Achieving perfect separation"): stats.stackexchange.com/questions/80398/… $\endgroup$ – stmax Feb 25 '16 at 11:34
  • $\begingroup$ @stmax Let me simplify the question. Suppose we are working with a linear kernel SVM but our data is linearly inseparable. Assume all points are distinct. How will the SVM behave? Will it converge and produce a decision surface at all? $\endgroup$ – Ragnar Mar 5 '16 at 9:49
1
$\begingroup$

You cannot guarantee this. Some data is not separable by any kernel because of duplicates.

By trying too hard, you will cause overfitting. Essentially, you force the implicit mapping to be so complex it contains a copy of your training data (which is exactly what happens if you choose a too small bandwidth with RBF).

If you want a good generalization performance, you will have to tolerate some errors, and use e.g. soft-margin and such techniques.

Perfect separation is not something to aim for. Such a guarantee is just a guarantee of being able to overfit! Use cross-validation to reduce the risk of overfitting and find the right balance between being optimal on training data and actual performance.

|improve this answer
$\endgroup$
  • $\begingroup$ @Anony-Mouse But then if there is no guarantee, does that mean that we can't use hard-margin and kernels on linearly inseparable data? I know using soft-margin generalizes better and that in that case an imperfect separation is fine...I'm just wondering about the case when it is hard-margin. $\endgroup$ – Ragnar Feb 26 '16 at 0:29
  • $\begingroup$ There exists data that is impossible to separate. Example: (0,0,classA), (0,0,classB). No kernel ever can separate these classes, because the data is identical. Thus: no guarantee of making data linearly separable is possible on such data sets. $\endgroup$ – Has QUIT--Anony-Mousse Feb 26 '16 at 0:36
  • $\begingroup$ @Anony-Mouse Withstanding such examples (which is reasonable because it is a contradiction): But then if there is no guarantee, does that mean that we can't use hard-margin and kernels on linearly inseparable data? $\endgroup$ – Ragnar Feb 26 '16 at 6:48
  • $\begingroup$ @Anony-Mouse Let me simplify the question. Suppose we are working with a linear kernel SVM but our data is linearly inseparable. Assume all points are distinct. How will the SVM behave? Will it converge and produce a decision surface at all? $\endgroup$ – Ragnar Mar 5 '16 at 9:49
  • $\begingroup$ Convergence and result depend on your optimization procedure, this cannot be answered for the abstract SVM model. If e.g. your data is (0,0,+), (0,1,-), (1,0,-), (1,1,+) and you use the linear kernel, then there exists no SVM that has 100% accuracy. But what the program does that is responsible for finding the "optimal" SVM is an entirely different question. This is a nontrivial optimization problem. $\endgroup$ – Has QUIT--Anony-Mousse Mar 5 '16 at 11:53

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.