SVM, Overfitting, curse of dimensionality

Question

My dataset is small (120 samples), however the number of features are large varies from (1000-200,000). Although I'm doing feature selection to pick a subset of features, it might still overfit.

My first question is, how does SVM handle overfitting, if at all.

Secondly, as I study more about overfitting in case of classification, I came to the conclusion that even datasets with small number of features can overfit. If we do not have features correlated to the class label, overfitting takes place anyways. So I'm now wondering what's the point of automatic classification if we cannot find the right features for a class label. In case of document classification, this would mean manually crafting a thesaurus of words that relate to the labels, which is very time consuming. I guess what I'm trying to say is, without hand-picking the right features it is very difficult to build a generalized model ?

Also, if the experimental results don't show that the results have low/no overfitting it becomes meaningless. Is there a way to measure it ?

Answer 1

In practice, the reason that SVMs tend to be resistant to over-fitting, even in cases where the number of attributes is greater than the number of observations, is that it uses regularization. They key to avoiding over-fitting lies in careful tuning of the regularization parameter, $C$, and in the case of non-linear SVMs, careful choice of kernel and tuning of the kernel parameters.

The SVM is an approximate implementation of a bound on the generalization error, that depends on the margin (essentially the distance from the decision boundary to the nearest pattern from each class), but is independent of the dimensionality of the feature space (which is why using the kernel trick to map the data into a very high dimensional space isn't such a bad idea as it might seem). So in principle SVMs should be highly resistant to over-fitting, but in practice this depends on the careful choice of $C$ and the kernel parameters. Sadly, over-fitting can also occur quite easily when tuning the hyper-parameters as well, which is my main research area, see

G. C. Cawley and N. L. C. Talbot, Preventing over-fitting in model selection via Bayesian regularisation of the hyper-parameters, Journal of Machine Learning Research, volume 8, pages 841-861, April 2007. (www)

and

G. C. Cawley and N. L. C. Talbot, Over-fitting in model selection and subsequent selection bias in performance evaluation, Journal of Machine Learning Research, 2010. Research, vol. 11, pp. 2079-2107, July 2010. (www)

Both of those papers use kernel ridge regression, rather than the SVM, but the same problem arises just as easily with SVMs (also similar bounds apply to KRR, so there isn't that much to choose between them in practice). So in a way, SVMs don't really solve the problem of over-fitting, they just shift the problem from model fitting to model selection.

It is often a temptation to make life a bit easier for the SVM by performing some sort of feature selection first. This generally makes matters worse, as unlike the SVM, feature selection algorithms tend to exhibit more over-fitting as the number of attributes increases. Unless you want to know which are the informative attributes, it is usually better to skip the feature selection step and just use regularization to avoid over-fitting the data.

In short, there is no inherent problem with using an SVM (or other regularised model such as ridge regression, LARS, Lasso, elastic net etc.) on a problem with 120 observations and thousands of attributes, provided the regularisation parameters are tuned properly.

Answer 2

I will start with the second and last questions.

The problem of generalization is obviously important, because if the results of machine learning cannot be generalized, then they are completely useless.

The methods of ensuring generalization come from statistics. We usually assume, that data is generated from some probability distribution that originates in reality. For example if you're a male born in year 2000, then there is a probability distribution of what is your weight / height / eye colour when you reach 10, which results from available gene pool at year 2000, possible environmental factors etc. If we have lots of data, we can say something about those underlying distributions, for example that with high probability they are gaussian or multinomial. If we have accurate picture of distributions, then given height , weight and eye colour of a 10 year old kid in 2010, we can get a good approximation of the probability of the kid being male. And if the probability is close to 0 or 1 we can get a good shot at what the kids sex really is. The most important part of this whole thing is: we assume there is some probability distribution that generates both training data, test data, and the real world data we would like to use our algorithm on.

More formally, we usually try to say that if the training error is $k$ then with high probability ($\delta$) the error on some data generated from the same distribution will be less than $k + \epsilon$. There are known relations between size of the training set, epsilon and the probability of test error exceeding $k+ \epsilon$. The approach I introduced here is known as Probably Approximately Correct Learning, and is an important part of computational learning theory which deals with the problem of generalization of learning algorithms. There are also number of other factors that can lower epsilon and increase delta in those bounds, ie. complexity of hypothesis space.

Now back to SVM. If you don't use kernels, or use kernels that map into finite dimensional spaces, the so called Vapnik-Chervonenkis dimension which is a measure of hypothesis space complexity, is finite, and with that and enough training examples you can get that with high probability the error on the test set won't be much bigger than the error on training set. If you use kernels that map into infinite-dimensional feature spaces, then the Vapnik-Chervonenkis dimension is infinite as well, and what's worse the training samples alone cannot guarantee good generalization, no matter the number of them. Fortunately, the size of the margin of an SVM turn out to be a good parameter for ensuring generalization. With big margin and training set, you can guarantee that the test error won't be much bigger than training error as well.

Answer 3

There are at least two major sources of overfitting you might wish to consider.

1. Overfitting from an algorithm which has inferred too much from the available training samples. This is best guarded against empirically by using a measure of the generalisation ability of the model. Cross validation is one such popular method.

2. Overfitting because the underlying distribution is undersampled. Usually there is little that can be done about this unless you can gather more data or add domain knowledge about the problem to your model.

With 120 samples and a large number of features you are very likely to fall foul of 2 and may also be prone to 1.

You can do something about 1 by careful observation of the effect of model complexity on the test and training errors.