How to know whether the data is linearly separable?

The data has many features (e.g. 100) and the number of instances is like 100,000. The data is sparse. I want to fit the data using logistic regression or svm. How do I know whether features are linear or non-linear so that I can use kernel trick if non-linear?

• You try logistic regression and see how it works. If it doesn't work out, there are infinitely many kernels you can try, and it still might not work out. Nov 18 '15 at 7:01

There are several methods to find whether the data is linearly separable, some of them are highlighted in this paper (1). With assumption of two classes in the dataset, following are few methods to find whether they are linearly separable:

1. Linear programming: Defines an objective function subjected to constraints that satisfy linear separability. You can find detail about implementation here.

2. Perceptron method: A perceptron is guaranteed to converge if the data is linearly separable.

3. Quadratic programming: Quadratic programming optimisation objective function can be defined with constraint as in SVM.

4. Computational geometry: If one can find two disjoint convex hulls then the data is linearly separable

5. Clustering method: If one can find two clusters with cluster purity of 100% using some clustering methods such as k-means, then the data is linearly separable.

(1): Elizondo, D., "The linear separability problem: some testing methods," in Neural Networks, IEEE Transactions on , vol.17, no.2, pp.330-344, March 2006 doi: 10.1109/TNN.2005.860871

• Please give a reference (links may rot) & at least a little explanation of what methods are covered. Nov 18 '15 at 13:10
• Thanks. Good answer (+1). The R package safeBinaryRegression also implements the linear programming approach. Nov 19 '15 at 9:09
• Which (the LP approach) is readily interpreted geometrically, computationally efficient and generally available (as LP routines are). Jul 14 '18 at 20:55
• For the perceptron method, how long should I wait to say the data is not linearly separable? I may be just one loop behind before I reach a solution? I just learned the perceptron.
– JOHN
May 26 '20 at 5:41
• And with the assumption of more then 2 classes? May 28 '20 at 9:41

I assume you talk about a 2-class classification problem. In this case there's a line that separates your two classes and any classic algorithm should be able to find it when it converges.

In practice, you have to train and test on the same data. If there's such a line then you should get close to 100% accuracy or 100% AUC. If there isn't such a line then training and testing on the same data will result at least some errors. Based on the volume of the errors it may or may not worth trying a non-linear classifier.

Consider the hard margin SVM formulation, which tries to find a hyperplane that strictly separates the data. $$min_{w,b} \space ||w||^2$$ $$s.t \space \forall i, (w'x_{i} + b)y_{i} \ge 1$$

If our data is linearly seperable, all the inequality constraints will be satisfied. Notice that $$w'x + b$$ simply indicates which side of a plane a point lies on. Knowing the feasibility of the SVM problem is equivalent to knowing if our data is linearly separable. However, we don't actually care much about the objective for simply checking linear seperability. Can we solve a simpler feasibility problem, maybe a linear program?

The following LP can be solved to check the feasibility. $$min_{s,b, w} \space s$$ $$s.t \space \forall i, (w'x_{i} + b)y_{i} \ge 1 - s$$ $$s \ge 0$$

If optimal $$s$$ for this problem is zero, we know that the original inequality constraints can be satisfied. This means our data was linearly separable in the original space. Using separate $$s_i$$ for each training example can tell us which data-points cause linearly in-separability.

• +1 this is the geometric intuition behind the method implemented in the R package safeBinaryRegression Jul 14 '18 at 20:57