# Overfitting with Linear Classifiers

Today our professor stated in class that "overfitting with linear classifiers is not possible". I hold that to be wrong, since even linear classifiers can be sensitive to outliers in the training set - take for instance a hard margin Support Vector Machine: One single noisy datapoint can alter which hyperplane will be used to separate datasets. Or am I wrong? Obviously, linearity will probably prevent rather from overfitting due to lower model complexity, still I do not see why overfitting should be impossible. One additional point is that when I tried to think about this problem I realized that "overfitting" does not seem to be formally defined. Why is that? Wouldn't some distance measure between training and test set performance allow for such a formalisation? Thanks

• Why do you say linear classifier? Most linear models are for prediction, not classification. And you are right - linear models can be very prone to overfitting. Not as much as machine learning methods, but still overfitting can be a problem. – Frank Harrell Oct 6 '15 at 22:07
• It is very easy to overfit the linear classifier. Just fit the model to some dataset (noisy, real-world) and do not use any regularization. – Vladislavs Dovgalecs Oct 6 '15 at 22:27
• Beware of classification - usually no need to set your sights that low. – Frank Harrell Oct 6 '15 at 23:04
• @FrankHarrell ...and why? – Pegah Oct 6 '15 at 23:08
• Yes, if $Y$ was originally binary. If $Y$ was originally continuous then classification is even more problematic. – Frank Harrell Oct 7 '15 at 12:43

A linear regression / classifier can absolutely be overfit if used without proper care.

Here's a small example. Let's create two vectors, the first is simply $5000$ random coin flips:

set.seed(154)
N <- 5000
y <- rbinom(N, 1, .5)


The second vector is $5000$ observations, each randomly assigned to one of $500$ random classes:

N.classes <- 500
rand.class <- factor(sample(1:N.classes, N, replace=TRUE))


There should be no relation between our flips y and our random classes rand.class, they were determined completely independently.

Yet, if we attempt to predict the random flip with the random class using logistic regression (a linear classifier), it sure thinks there is a relationship

M <- glm(y ~ rand.class, family="binomial")
hist(coef(M), breaks=50)


The true value of every one of these coefficients is zero. But as you can see, we have quite a spread. This linear classifier is for sure overfit.

Note: The extremes in this histogram, where the coefficients have wandered to $-15$ and $15$, are cases where a class had either no observations with y == 1 or no values with y == 0. The actual estimated values for these coefficients are plus and minus infinity, but the logistic regression algorithm is hard coded with a bound of $15$.

"overfitting" does not seem to be formally defined. Why is that?

Overfitting may be best understood within the context of a class of models which has some complexity parameter. In this case, a model could be said to be overfit when decreasing the complexity slightly results in better expected out of sample performance.

It would be very difficult to precisely define the concept in a model independent way. A single model is just fit, you need something to compare it to for it to be over or under fit. In my example above this comparison was with the truth, but you usually don't know the truth, hence the model!

Wouldn't some distance measure between training and test set performance allow for such a formalisation?

There is such a concept, it's called the optimism. It's defined by:

$$\omega = E_{\text{test}} - E_{\text{train}}$$

where $E$ stands for error, and each term is averaged over all possible training and testing sets for your learning algorithm.

It doesn't quite get at the essence of overfitting though, because the performance on a test set can be quite a bit worse than the train, even though a model of higher complexity decreases both.

• wow, what a good answer, many thanks. one question: are linear SVMs less prone to overfitting than e.g. log. regression you've mentioned (due to the different ways of optimizing for the linear decision boundary)? – Pegah Oct 6 '15 at 22:53
• I must admit, I am no expert on SVMs, and lack practical experience in their use. I don't really want to venture an answer and risk being very wrong. If you can formulate it precisely, it's probably worth a question of it's own. – Matthew Drury Oct 6 '15 at 23:32
• SVMs are regularized, and therefore less prone to overfit. In order to realize that you only need to look at the function you are minimizing: it includes either the l1 norm or l2 norm of the weights, shrinking them in the optimization and therefore prefering "simple" models to "complex" models. The parameter controling this is the C hyper parameter. In the limiting case (C = infinity), the SVM fits "perfectly" the training set and thus it is probably overfit (note that I said probably, you need a test set to be sure!). Also note that i used a lot of quotes, but this can be properly defined. – skd Oct 8 '15 at 23:29

In the 70-ties, experiments with pattern recognition algorithms on large datasets revealed that adding extra features did in some cases increase the test-set error rates. This is counter intuitive because one would expect that adding an extra feature always increases classifier performance, or in case that the added feature is 'white noise', its addition does not influence classifier performance at all. The effect of adding still more extra features to a classifier, eventually leading to a decrease in test-set performance became known as the peaking phenomenon [1].

Feature peaking is caused by over-generalization during learning. The extra features cause the inclusion of so many additional parameters that the classifier begins to overfit the data. Hence, the peaking point is passed.

In general, we face a bias-variance trade-off when training classifiers. The more feature-variables we use, the better will the (unknown) underlying classifier mechanism possibly be modelled by our classifier. Hence, the systematic deviation between fitted model and 'truth' will lessen, i.e. a smaller bias results. On the other hand, increasing the feature space of the classifier necessarily implies the addition of parameters (those that fit the added features). Thus, the variance of the fitted classifier increases too.

So the classifier exeeding the peaking point is just one stochastic realization of a high-dimensional classification problem, and a new fit will result in a highly different parameter vector. This fact reflects the increased variance.

[1. G. V. Trunk, "A Problem of Dimensionality: A Simple Example," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-1, no. 3, pp. 306-307, July 1979]

I think that overfitting refers to model complexity rather than generalization ability. I understand the quote "a linear classifier cannot be overfitted" since its complexity is small, and there is no other simpler classifier providing a better performance.

The example is linked to the generalization ability of linear classifiers (and complex ones). Even in this second part, linear classifiers usually provide less variance than complex ones, thus the "overfitting" value for linear classifiers, following this concept, is also smaller (although the empirical risk of them could be so large). atb

Like @match-maker-ee said, Linear classifiers can over-fit depending on the input features.

The following model f is linear in its parameters a, b and c, but can be fitted to a quadratic curve in the feature space of x:

$$f(x) = ax^2+bx+c$$

SVM's can also over-fit, for example when they use the kernel trick, despite being basically a linear model in an augmented feature space.