What purpose does the kernel trick serve in SVMs?

Question

My understanding of SVMs is the following:

The kernel trick allows us to project data from a training set which isn't linearly separable into a higher dimensional space where it becomes linearly separable. This in turn makes it possible to find the optimal separating boundary between the two classes, hence improving the generalization capabilities of the SVM compared to other methods such as (single hidden layer) perceptrons and k-NN.

In a discussion with someone over SVMs, the other person pointed out that increasing the number of dimensions of the data (i.e the kernel trick) would actually lead to more overfitting, since with enough dimensions, any data set becomes linearly and perfectly separable - including noisy data sets. This would lead to the generalization accuracy deteriorating instead of improving.

His reasoning makes sense, but then what purpose does the kernel trick serve? Why doesn't the kernel trick lead to more overfitting?

Answer 1

The dimensions of your feature transform are hyperparameters. So yes, if you choose them to be really large, you'll risk overfitting. This is no different from any other machine learning model, like choosing a really high order polynomial for very few points or, a neural network where if you add too many layers it will also overfit. But, there should be a higher dimension with a reasonable tradeoff between accuracy and overfitting.

The kernel trick serves one very important purpose: it removes the need for calculating your feature transform, and relegates all calculations to be just in terms of inner products between your features. This is a vast speedup, and also implies you don't even need to worry about what your feature transform is. To clarify this point, imagine you would like to use a $d$ dimensional polynomial to transform your data. Lets say your data is $N$ dimensional. Then $\Phi:\mathbb{R}^N\rightarrow \mathbb{R}^D$, where $D=\binom{N+d}{d}$. For example, if $d=3$, then the polynomial has terms $\ x_i,\ x_{i}x_j$, $\ x_{i}x_jx_k$, where $i,j,k$ are in $\{1,2,\ldots,N\}$. You can work it out, but you'll see that $D$ grows like $N^d$, which is enormous even for small $N,d$. On the other hand, a dot product calculation can be much, much faster, and also not require you to store $\Phi(x)$ for each $x$ in memory.