Why use RBF kernel if less is needed?

Question

I have seen online theorem's such as Cover's theorem Wikipedia which prove how given $p$ points in $\mathbb{R}^N$ the linear separability is almost certain as the fraction $\dfrac{p}{N}$ is kept close to $1$ (and also a little further actually). It is possible to check the graph in the proof cited below for a quick understanding. My question is, given this, why would we map to an infinite dimensional feature space if a $p$ dimensional feature space is sufficient? Is it because it is faster to compute the RBF kernel rather than a $p$ dimensional one? Is it because it is more difficult to design it? Or is it because I completely missed my understanding of the statement?

A proof for the theorem implementing the notation I am using can be found here Proof Cover's Theorem

Answer 1

One way of looking at it is to say that the RBF kernel dynamically scales the feature space with the number of points. As we know from geometry, for $p$ points you can always draw an at most $(p-1)$-dimensional hyperplane through them. That's the inherent dimensionality of the space implied by the RBF kernel. But, as you add more points, the dimensionality of the space rises accordingly. That makes the RBF kernel quite flexible. It gives you linear separability irrespective the number of points.

Update in response to comment:

I cannot give you a link to a formal proof, but I assume it shouldn't be too hard to construct. We know that:

• a kernel is the dot product in a feature space,
• $k(x, y) = \| \varphi(x) \| \cdot \| \varphi(y) \| \cdot \cos(\angle(\varphi(x), \varphi(y)))$, and, consequently
• $k(x, x) = \| \varphi(x) \|^2$
• RBF is a kernel,
• for the RBF kernel, $k(x, x) = e^0 = 1$, and
• $k(x, \infty) = e^{-\infty} = 0$

Geometrically, the RBF kernel projects the points onto a segment of a hypersphere with a radius of $1$ in a $p$-dimensional space. Points which are close to each other in the input space are mapped onto nearby points in the feature space. Points which are far from each other in the input space are mapped on (close to) orthogonal points on the hypersphere.

Theoretically, points in the RBF-induced feature space are always linearly separable, irrespective of $\gamma$. It's just a numerical issue that for a small $\gamma$ it could become hard to find the separating hyperplane.

On the other hand, if you choose $\gamma$ very large, you will push all the projections into corners of the hypercube enclosing the hypersphere: $(1, 0, 0, \ldots), (0, 1, 0, \ldots), (0, 0, 1, \ldots)$ etc. This will give you a trivially simple separability on the training set, but very bad generalisation.

Update (graphical example):

To get some intuition, observe this trivially simple, one-dimensional dataset. It is obvious that no linear boundary can separate the two classes, blue and red:

But, the RBF kernel transforms the data into a 3D feature space where they become linearly separable. If we denote $k_{ij} = k(x_i, x_j)$, it is easy to see that the transformation $$ \begin{array}{rrrrrrr} \textbf{z}_1 = \varphi(x_1) & = & [ & 1, & 0, & 0 & ]^T \\ \textbf{z}_2 = \varphi(x_2) & = & [ & k_{12}, & z_{22}, & 0 & ]^T \\ \textbf{z}_3 = \varphi(x_3) & = & [ & k_{13}, & (k_{23} - k_{12}k_{13}) / z_{22}, & z_{33} & ]^T \\ \end{array} $$ reproduces the RBF kernel, $k(x_i, x_j) = \varphi(x_i) \cdot \varphi(x_j)$, where $z_{22} = \sqrt{1 - k_{12}^2}$ and $z_{33} = \sqrt{1 - z_{31}^2 - z_{32}^2}$. The kernel parameter $\gamma$ controls how far the points get in the feature space:

As you can see, as $\gamma \rightarrow 0$, the points get very close to each other. But this is only a part of the problem. If we zoom in for a small $\gamma$, we see that the points still lie on an almost straigt line:

True, the line is not exactly straight, but slightly bent, so there exists a plane to separate the two classes, but the margin is very thin and numerically hard to satisfy. You may say that $\gamma $ controls the non-linearity of the transformation: The smaller the $\gamma$, the closer the transformation to the linear one.

Answer 2

While the points are notionally mapped into an infinite-dimensional space, they will necessarily lie within an at-most $p$-dimensional sub-space (as there are only $p$ points). Note that the (notionally infinite-dimensional) primal weight vector is a linear combination of the images of the support vectors in the feature space,

$\vec{w} = \sum_{i=1}^\ell y_i\alpha_i\phi(\vec{x}_i)$

which means that the vector is also required to lie within that $p$-dimensional sub-space. The additional dimensions are essentially irrelevant and do not affect the resulting model in any way.

This is why the ``kernel trick'' allows us to represent a notionally infinite-dimensional space using only finite dimensional quantities (such as the Gram matrix).

However, there are other reasons for using the RBF kernel, which is that the problem may be non-linearly separable. Consider the case where the $p=N$ points in the dataset all co-linear, lying along a straight line in N dimensions. For most labeling of the points, there will be no decision boundary that classifies the data points without error. However, if we take those same points and use an RBF kernel, the points will be mapped onto the positive orthant of an infinite-dimensional unit hyper-sphere (as shown by @IgorF. +1), and the points will be no longer co-linear and any labelling of the points can be linearly separated (provided none of the points of different labels are exact duplicates)