SVM: non-linear versus linear models

Question

In the context of classification on somewhat large datasets (say at least 50Kx50K), I am wondering in which cases non-linear models are superior to linear ones to warrant the added complexity. I often see in my own research that for these larger datasets, non-linear datasets cannot outperform linear ones (say for a linear kernel SVM and an RBF kernel SVM). But this might be biased due to my 'repository selection' of datasets which are all sparse and drawn from transactional data.

My intuition says that specifically for an RBF kernel, a linear kernel should be a lower-bound for the performance that you can achieve with an RBF kernel, but my hope of attaining higher performance than this lower bound is not fullfilled because in the end they all achieve more or less the same performance.

Specifically my question is this: have you encountered situations in which non-linear models were worth the effort? Or do you perhaps know about research confirming/rejecting my own observations?

Answer 1

In the case of high dimensional problems, linear SVMs tend to perform very well, like in the case of text classification (see for example the classic paper Text Categorization with Support Vector Machines: Learning with Many Relevant Features). It is shown how in the case of a high dimensional, sparse problem with few irrelevant features, linear SVMs achieve great performance.

Also, Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition shows how the higher the dimensionality, the more likely it is to find a separating hyperplane.

Non-linear kernel machines tend to dominate when the number of dimensions is smaller. In general, non-linear SVMs will achieve better performance, but in the circumstances referred above, that difference might not be significant, and linear SVMs are much faster to train.

Another interesting point to consider is correlation. Both, linear and non-linear are affected by highly correlated features (see this answer).

Answer 2

There are no hard and fast rules, in terms of a priori rules. The methodology generally is:

• try a linear model. how well does it work? does it meet your requirements?
• try a low-capacity non-linear model. measure the results. How well does it work? To what extent does it meet your requirements?
• iteratively increase the capacity of your non-linear model

What does it mean 'how well does it work'? Well, look at the loss on training data:

• if the loss on training data shows the model cannot even fit well to training data, you might consider a higher capacity model.
• 'higher capacity' means:
  • 'if you were using a linear model, try a non-linear
  • if you were using a low-capacity non-linear model, try a higher capacity model'.

On the other hand, if your training loss is low, and your test loss is significantly higher (using 'significantly' in a fairly hand-waving, non-technical sense; like eg your accuracy on training is 99%, but your accuracy on test is eg 80%), then your network is overfitting. This can indicate an over-capacity network, or you could simply add regularization.

• to reduce capacity, you can change from non-linear to linear, for example
• to add regularization, you can add things like: L2 regularization, L1 regularization, dropout, batch-normalization (last 2 only apply to highly non-linear multilayer neural nets, but if you have enough data...)

The number of training examples doesnt really tell you much a priori, since it really depends on the shape of the high dimensional manifold on which they lie etc. If the manifold is relatively simple, then linear models will work well. If the manifold is complex, you might need higher capacity models, but you will also need a ton of training data (again, 'ton' is a hand-waving non-technical term).

Answer 3

I am sure you looked at ways of choosing classifiers online (Cross Validation and Model Selection). I think that obviously if the data is linearly separable it is better to stick with the good old linear kernel SVMs. But this is difficult to determine and I think that the question that you should ask yourself: is the data is likely to be linearly separable (not: is the data not likely to be linearly separable?) if not then you might want to perform Cross Validation with both types of SVMs (maybe different types of kernels).