# SVM, Overfitting, curse of dimensionality

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 ?

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.

• Are there any papers showing feature selection methods like Information Gain based ranking are more likely to overfit ? – user13420 Aug 29 '12 at 17:12
• Not that I know of, the point was that the SVM has some theoretical results that suggest that they are resistant to over-fitting due to the number of attributes, but feature selection methods don't even have that. FWIW, the monograph by Miller on "subset selection in regression" advises to use regularisation methods if predictive performance is all that is required. There have been some open challenges on feature selection, which suggest that regularisation tends to outperform feature selection (see nipsfsc.ecs.soton.ac.uk and causality.inf.ethz.ch/challenge.php). – Dikran Marsupial Aug 29 '12 at 18:11
• As stated in the first paragraph, SVMs tend to be resistant to over-fitting, is that it uses regularization (parameter C), so by default, svm has this regularization parameters C? And I'm not sure what variables controlled by this C, you mean those slack variables? – avocado Oct 19 '17 at 4:12
• ...feature selection algorithms tend to exhibit more over-fitting as the number of attributes increases.... This statement does not seem correct. Due to the curse of dimensionality, if the number of attributes increases, the algorithm will tend to overfit and feature selection, for obvious reasons, will try to decrease the number of attributes, which means less overfitting. – ARAT Feb 10 at 21:07
• @avocado C is not regularization parameter actually but it can be thought of a tradeoff between preferring large margin and preferring small number of misclassified data points. A small C prefers large margins but allow potentially large number of misclassified points (ignore errors/underfit the data). A large C prefers small number of misclassified examples at the expense of smaller margin (high tendency to overfit). Therefore, it is basically deciding between classifying the training data well (minimizing the empirical risk) and classifying the future examples well (generalization). – ARAT Feb 10 at 21:12

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.

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.

• But, how do we detect if we are overfitting ? If the models do pretty good in cross-validation, are they doing it because it is actually good or because of overfitting due to 1 or 2 ? Also with thousands of features, analyzing each feature by hand would be cumbersome. If it is not possible to identify overfitting, how can we trust any cross-validation result ? – user13420 Aug 29 '12 at 17:16
• Without additional data it is very difficult to know if you are overfitting against an undersampled population. You can divide the data into three sets using a a validation set to tune the model and then a separate test set to test it. Another approach is to modify the model complexity and see how the training and test set accuracies vary. A lift in the test set error will indicate some degree of model overfitting from the data. – image_doctor Aug 29 '12 at 17:33
• Applying repeated 50/50 holdout trials will give you some feel for if the training and test sets are balanced. They probably won't be. Some models, such as KNN, will achieve perfect accuracy on the training set so are inherently overfitted in some sense. But they may still achieve acceptable performance on the test set. So as with much in machine learning, in the end it all depends on the precise specifics of the data. – image_doctor Aug 29 '12 at 17:54
• @image_doctor Can you elaborate on "modify the model complexity"? – Keith Hughitt Mar 23 '19 at 16:28