Is there a way to test linear separability of a two-class dataset in high dimensions? My feature vectors are 40-long.

I know I can always run logistic regression experiments and determine hitrate vs false alarm rate to conclude whether the two classes are linearly separable or not but it would be good to know if there already exists a standard procedure to do that.

  • 2
    $\begingroup$ have a look here: $\endgroup$
    – user603
    Jan 17 '13 at 10:11
  • $\begingroup$ It's useful to plot separabiity: x = misclassified points $\cdot$ normal-to-separating-plane, y = cumulative loss(x). (For a sample plot, try a new question with tags svm and data-visualization.) $\endgroup$
    – denis
    Feb 3 '13 at 11:13
  • $\begingroup$ What about 3 classes problem? Are all 3+ classes problems are non-linear? $\endgroup$
    – Rosy
    Aug 2 '17 at 19:25

Well, support vector machines (SVM) are probably, what you are looking for. For example, SVM with a linear RBF kernel, maps feature to a higher dimenional space and tries to separet the classes by a linear hyperplane. This is a nice short SVM video illustrating the idea.

You may wrap SVM with a search method for feature selection (wrapper model) and try to see if any of your features can linearly sparate the classes you have.

There are many interesting tools for using SVM including LIBSVM, MSVMPack and Scikit-learn SVM.

  • 1
    $\begingroup$ +1. It's almost as if Nik were describing SVM's, not having heard of them. In R, you could use the (mysteriously-named) e1071 package's svm with kernel="linear" and look at the prediction versus actual. $\endgroup$
    – Wayne
    Jan 19 '13 at 15:13
  • 1
    $\begingroup$ I know about SVMs. Just that I didn't know I could use them for testing linear separability without actually classifying each sample. $\endgroup$
    – Nik
    Jan 24 '13 at 20:08
  • 4
    $\begingroup$ @Wayne: Nik is actually not asking for SVMs. I explain in my answer why this is not the solution for his problem. $\endgroup$
    – Raffael
    Apr 21 '14 at 9:56
  • 2
    $\begingroup$ A "linear RBF kernel" doesn't exist. $\endgroup$ Apr 21 '14 at 11:42
  • $\begingroup$ Of course ! What was meant is an RBF kernel that maps data into a linearly separable space. $\endgroup$
    – soufanom
    Apr 22 '14 at 21:07

Computationally the most effective way to decide whether two sets of points are linearly separable is by applying linear programming. GLTK is perfect for that purpose and pretty much every highlevel language offers an interface for it - R, Python, Octave, Julia, etc.

With respect to the answer suggesting the usage of SVMs:

Using SVMs is a sub-optimal solution to verifying linear separability for two reasons:

  1. SVMs are soft-margin classifiers. That means a linear kernel SVM might settle for a separating plane which is not separating perfectly even though it might be actually possible. If you then check the error rate it is going to be not 0 and you will falsely conclude that the two sets are not linearly separable. This issue can be attenuated by choosing a very high cost coefficient C - but this comes itself at a very high computational cost.

  2. SVMs are maximum-margin classifiers. That means the algorithm will try to find a separating plane that is separating the two classes while trying to stay away from both as far as possible. Again this is a feature increasing the computational effort unnecessarily as it calculates something that is not relevant to answering the question of linear separability.

Let's say you have a set of points A and B:

enter image description here

Then you have to minimize the 0 for the following conditions:

(The A below is a matrix, not the set of points from above)

enter image description here

"Minimizing 0" effectively means that you don't need to actually optimize an objective function because this is not necessary to find out if the sets are linearly separable.

In the end (enter image description here) is defining the separating plane.

enter image description here

In case you are interested in a working example in R or the math details, then check this out.

  • 3
    $\begingroup$ SVMs are soft-margin classifiers ... except when you use hard margin SVM. That said, using SVMs would be like shooting a fly with a cannon. $\endgroup$ Apr 21 '14 at 11:40
  • $\begingroup$ that's correct - though a lot (or maybe the far majority) of SVM libraries do not offer this choice $\endgroup$
    – Raffael
    Apr 21 '14 at 11:49
  • 2
    $\begingroup$ @Raffael All SVM libraries can be used as hard margin classifiers. You simply select a high value for parameter $C$. $\endgroup$
    – iliasfl
    Aug 31 '14 at 8:50

Linear Perceptron is guaranteed to find a solution if one exists. This approach is not efficient for large dimensions. Computationally the most effective way to decide whether two sets of points are linearly separable is by applying linear programming as mentioned by @Raffael.

A quick solution would be to solve a perceptron. A code with an example to solve using Perceptron in Matlab is here


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.