What are the primary advantages of using Kernels in predicting continuous outcomes?

Question

Consider the linear model: $$y = X \theta + \epsilon $$ with $X$ inputs or features of inputs and $\theta$ a vector of parameters (and $\epsilon$ the error) with regularized error function $$ J(w)= \frac{1}{2} [X \theta - y]^T[X \theta - y] + \frac{\lambda}{2}\theta^T\theta.$$

The idea of kernels $k(x_i,x_j)$ is to define a similarity function between all observation pairs $i,j$ and summarize them in the Gram Matrix $K$. If we define $K=XX^T$, then $J(w)$ can be re-written as $$J(a)= \frac{1}{2}a^TKKa-a^TKt+\frac{1}{2}t^Tt+\frac{\lambda}{2}a^TKa$$ where $$a = (K + \lambda I_N)^{-1} t.$$

Finally a prediction for $y$ can be made as $$\hat{y}(x)=k(x)^T(K+\lambda I_N)^{-1}t.$$ I understand that, while it is amazing that we can eliminate the parameters completely from the prediction equation, the computational burden strongly increases because $K$ needs to be inverted and is of order $N \times N$.

What I do not understand is: what are the advantages of using a Kernel in this model?

Answer 1

The following is from Christopher M. Bishop's "Pattern Recognition and Machine Learning" page 294 where $M$ represents the feature dimension:

"In the dual formulation, we determine the parameter vector a by inverting an $N ×N$ matrix, whereas in the original parameter space formulation we had to invert an $M × M$ matrix in order to determine w. Because N is typically much larger than M, the dual formulation does not seem to be particularly useful. However, theadvantage of the dual formulation, as we shall see, is that it is expressed entirely interms of the kernel function $k(x, x)$. We can therefore work directly in terms of kernels and avoid the explicit introduction of the feature vector $\phi(x)$, which allows us implicitly to use feature spaces of high, even infinite, dimensionality."