Why transforming the data to a high-dimensional feature space in which classes are linearly separable leads to overfitting?

Question

I read in my book (statistical pattern classification by Webb and Wiley) in the section about SVMs and linearly non-separable data:

In many real-world practical problems there will be no linear boundary separating the classes and the problem of searching for an optimal separating hyperplane is meaningless. Even if we were to use sophisticated feature vectors, $\Phi(x)$, to transform the data to a high-dimensional feature space in which classes are linearly separable, this would lead to an over-fitting of the data and hence poor generalization ability.

Why transforming the data to a high-dimensional feature space in which classes are linearly separable leads to overfitting and poor generalization ability?

Answer 1

@ffriend has a good post about it, but generally speaking, if you transform to a high dimensional feature space and train from there, the learning algorithm is 'forced' to take into account the higher-space features, even though they might have nothing to do with the original data, and offer no predictive qualities.

This means that you are not going to be properly generalizing a learning rule when training.

Take an intuitive example: Suppose you wanted to predict weight from height. You have all this data, corresponding to people's weights and heights. Let us say that very generally, they follow a linear relationship. That is, you can describe weight (W) and height (H) as:

$$ W = mH - b $$

, where $m$ is the slope of your linear equation, and $b$ is the y-intercept, or in this case, the W-intercept.

Let us say that you are a seasoned biologist, and that you know that the relationship is linear. Your data looks like a scatter plot trending upwards. If you keep the data in the 2-dimensional space, you will fit a line through it. It might not hit all the points, but thats ok - you know that the relationship is linear, and you want a good approximation anyway.

Now lets say that you took this 2-dimensional data and transformed it into higher dimensional space. So instead of only $H$, you also add 5 more dimensions, $H^2$, $H^3$, $H^4$, $H^5$, and $\sqrt{H^2 + H^7}$.

Now you go and find co-efficients of the polynomial to fit this data. That is, you want to find co-efficients $c_i$ for the this polynomial that 'best fits' the data:

$$ W = c_1H + c_2H^2 + c_3H^3 + c_4H^4 + c_5H^5 + c_6\sqrt{H^2+H^7} $$

If you do that, what kind of line would you get? You would get one that looked a lot like @ffriend 's far right plot. You have overfit the data, because you 'forced' your learning algorithm to take into account higher order polynomials that have nothing to do with anything. Biologically speaking, weight just depends on height linearly. It doesnt depend on $\sqrt{H^2 + H^7}$ or any higher order nonsense.

This is why if you transform the data to higher order dimensions blindly, you run a very bad risk of overfitting, and not generalizing.

Answer 2

Let's say we are trying to find function that approximates set of 2D points on the plain using linear regression (which is essentially pretty much what SVM does). At 3 images below red crosses are observations (training data) and 3 blue lines represent equations with different degree of polynomial used for regression.

First image is generated by linear equation. As you can see, it reflects points quite poorly. This is called underfitting, because we gave learning algorithm too little "degree of freedom" (polynomial of too small degree). Second image is much better - we used polynomial of second degree and it looks pretty good. However, if we further increase "degree of freedom" we get 3rd image. Blue line at it comes right through the crosses, but do you believe that this line really describes dependency? I don't think so. Yes, on training set learning error (distance between crosses and the line) is very small, but if we add one more observation (say, from real data), most probably error for it will be much larger than if we used equation from second image. This effect is called overfitting - we try to follow training data too closely and get to troubles. Using polynomials of a single variable is a simple example of kernel - instead of one dimension ($x$) we use several ($x$, $x^2$, $x^3$, etc.). You can see that translating data into higher-dimensional space may help to overcome underfit, but it can also lead to overfit. The real challenge is to find what is "just right". Couple of tips for your further research in this topic. You can detect overfitting with procedure called cross validation. In short, you split you data into, say, 10 parts, take 9 of them for training and 1 for validation. If error on validation set is much higher than on train set, then you've got overfit. Most machine learning algorithms use some parameters (e.g. parameters of kernels in SVM) that allow to overcome overfitting. Also, one popular keyword here is regularization - modification of algorithm that directly affects optimization process, literally saying it "don't follow training data too closely".

BTW, I'm not sure that DSP is the right site for this kind of questions, probably you will be interested in visiting CrossValidated too.

Answer 3

Did you read further?

In the end of 6.3.10 section:

"However, there are often parameters of the kernel that must be set and a poor choice can lead to poor generalisation. The choice of best kernel for a given problem is not resolved and special kernels have been derived for particular problems, for example document classification"

which leads us to section 6.3.3:

"Acceptable kernels must be expressible as an inner product in a feature space, which means that they must satisfy Mercer’s condition"

Kernel by their own quite difficult area, you can have large data where in different parts should apply different parameters, such as smoothing, but don't know exactly when. Therefore such thing is quite difficult to generalise.