Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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.

share|improve this question
1  
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

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
1  
+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
1  
@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:

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.