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?
 A: 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.
A: 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:

*

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


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


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


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


*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
A: 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.
