23
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ have a look here: $\endgroup$
    – user603
    Commented Jan 17, 2013 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
    Commented Feb 3, 2013 at 11:13
  • $\begingroup$ What about 3 classes problem? Are all 3+ classes problems are non-linear? $\endgroup$
    – Rosy
    Commented Aug 2, 2017 at 19:25

3 Answers 3

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 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
    Commented Jan 19, 2013 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
    Commented Jan 24, 2013 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
    Commented Apr 21, 2014 at 9:56
  • 2
    $\begingroup$ A "linear RBF kernel" doesn't exist. $\endgroup$
    – Marc Claesen
    Commented Apr 21, 2014 at 11:42
  • $\begingroup$ Of course ! What was meant is an RBF kernel that maps data into a linearly separable space. $\endgroup$
    – soufanom
    Commented Apr 22, 2014 at 21:07
17
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 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$
    – Marc Claesen
    Commented Apr 21, 2014 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
    Commented Apr 21, 2014 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
    Commented Aug 31, 2014 at 8:50
0
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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