# Test for linear separability

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.

-
have a look here: –  user603 Jan 17 '13 at 10:11
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.) –  denis Feb 3 '13 at 11:13

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. 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. –  Wayne Jan 19 '13 at 15:13
I know about SVMs. Just that I didn't know I could use them for testing linear separability without actually classifying each sample. –  Nik Jan 24 '13 at 20:08
@Wayne: Nik is actually not asking for SVMs. I explain in my answer why this is not the solution for his problem. –  Raffael Apr 21 at 9:56
A "linear RBF kernel" doesn't exist. –  Marc Claesen Apr 21 at 11:42
Of course ! What was meant is an RBF kernel that maps data into a linearly separable space. –  soufanom Apr 22 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:

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

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

"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 () is defining the separating plane.

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

-
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. –  Marc Claesen Apr 21 at 11:40
that's correct - though a lot (or maybe the far majority) of SVM libraries do not offer this choice –  Raffael Apr 21 at 11:49
@Raffael All SVM libraries can be used as hard margin classifiers. You simply select a high value for parameter $C$. –  iliasfl Aug 31 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

-