# Is a polynomial kernel ridge regression really equivalent to performing a linear regression on those expanded features?

Say we have a dataset, X, which is Nx2 where N is the number of examples and 2 is the number of dimensions "features". If we were to run a kernel ridge regression (or SVM or whatever) on these features using a polynomial kernel of degree 2, it is my understanding that this would be equivalent to mapping your 2 dimensions to a feature space of all pairwise products and squares between the two dimensions, along with appropriate coefficients, and then performing linear regression in that space.

My question is: is what I said above true? My confusion lies in the fact that the feature mapping that the literature says to use is some fixed mapping x1,x2 -> 1 + x1^2 + x2^2 + sqrt(2) * x1x2, so the relative weights for each of those terms is fixed. However, if we were to run a linear regression based on those features, our model is free to learn any relative weighting that's optimal. In particular, it seems like the latter approach has more degrees of freedom (I'm not 100% clear on how to describe this confusion).

If we were to run a kernel ridge regression (or SVM or whatever) on these features using a polynomial kernel of degree 2, it is my understanding that this would be equivalent to mapping your 2 dimensions to a feature space of all pairwise products and squares between the two dimensions, along with appropriate coefficients, and then performing linear regression in that space.

That's correct. A kernel method is equivalent to the corresponding linear method operating on the feature space defined by the kernel function. In the case of the polynomial kernel with degree 2, the features consist of squared, linear, interaction, and constant terms. See this wikipedia page for details. Performing kernel ridge regression would be equivalent to performing ordinary (linear) ridge regression on these terms.

My confusion lies in the fact that the feature mapping that the literature says to use is some fixed mapping x1,x2 -> 1 + x1^2 + x2^2 + sqrt(2) * x1x2, so the relative weights for each of those terms is fixed. However, if we were to run a linear regression based on those features, our model is free to learn any relative weighting that's optimal.

There are multiple mappings involved, and it sounds like you might be confusing some with each other. First, let's forget about kernels. Say we want to learn a nonlinear function from an input space to an output space (e.g. the real numbers for a regression problem). One way to solve this problem would be to first map the inputs into some feature space using a fixed nonlinear function $$\Phi$$ (called the feature space mapping). Given an input, it outputs a vector of features. Next, we learn a linear function from feature space to output space (e.g. using linear regression). We now have a way to map inputs nonlinearly to outputs. For example, in a regression problem, this function would look like $$f(x) = \beta \cdot \Phi(x) + c$$ (where $$\beta$$ is a weight vector containing a coefficient for each feature and $$c$$ is a constant).

Now, say we define a function $$k$$ (called the kernel function) that takes two elements of input space and returns their dot product in feature space. That is: $$k(x,x') = \Phi(x) \cdot \Phi(x')$$. It turns out that a linear model can be expressed using dot products. And, using this fact, it's possible to implicitly compute (and learn) the same mapping from inputs to outputs using only the inputs and the kernel function. This is called the kernel trick. In this case, it's not necessary to explicitly construct the feature space representations, or to deal with coefficients of a linear model in feature space. For example, in a regression problem, the function would look like:

$$f(x) = \sum_{i=1}^n \alpha_i k(x, x_i) + c$$

where $$\{(x_i, y_i)\}$$ are the training inputs/outputs used to fit the model and $$\{\alpha_i\}$$ are coefficients that must be learned. The reason to use the kernel trick is that it can be more computationally efficient than operating explicitly in feature space in some circumstances.

It sounds like you might have confused the kernel function (which is fixed) with the linear function from feature space to outputs (which is learned implicitly when using the kernel trick).

• Thank you...so from what you say, if we have a 2 dimensional feature space initially, then the polynomial kernel would implicitly be nonlinear mapping our 2d space into a higher dimensional space, but this mapping is fixed- for example if the implicit mapping was phi(x1,x2) = 1 + x1^2 + sqrt2 x1x2 + x2^2, then we could use the kernel trick to take the dot in this space, but it wouldn’t be equivalent to concatenating each of these terms together into a feature vector and performing linear regression on it right? Feb 10, 2019 at 7:32
• No, the kernel function doesn't map from input to the higher dimensional space. That's the feature space mapping. The feature space mapping is fixed, and it is equivalent to concatenating the terms you listed into a vector (you also need $\sqrt{2} x_1$ and $\sqrt{2} x_2$ in there as well). The kernel trick is what lets you reformulate the model in terms of the kernel function. The kernelized model is equivalent to the linear model in feature space (e.g. concatenating the terms and doing linear regression). Feb 10, 2019 at 9:09
• Is there an easy way to explain how that works? Namely how you can have a fixed feature map but still retai the same representational degrees of freedom? Considering that we only have access to one fixed linear combination of the expanded terms when we use the kernel trick...does my question make sense? Thanks Feb 10, 2019 at 16:52
• Thank you user20160, that is an excellent answer. Do you know how to extract the coefficients in feature space. In sk learn, it is only possible for linear SVM. And it would be interesting to know these coefficients to understand the feature importance. Especially for poly kernel. What do you think? For RBF, we could also do something with the consideration of RBF as infinite dim Mar 20, 2023 at 14:02

This is an old good question that has not received a complete answer.

I believe this is not only about the "kernel trick." I believe this is more about a theoretical result called "the Representer Theorem" [1; Theorem 16.1] of kernel methods which I find rather deep.

Is there an easy way to explain how that works? Namely how you can have a fixed feature map but still retain the same representational degrees of freedom?

Yes. There is this fun fact.

Let's say the input is two-dimensional: $$x = (x_1, x_2)$$ as in the question's example. Consider the linear model $$f(x) = \phi(x)\theta$$, where $$\phi(x) = (1, \sqrt{2} x_1, \sqrt{2} x_2, \sqrt{2}x_1x_2, x_1^2, x_2^2)$$, and $$\theta$$ is a column vector taking values in $$\Re^6$$. Then, the "optimal" parameter $$\hat \theta$$: $$\hat \theta \in {\arg \min}_\theta \sum_{i=1}^n (y_i - f(x_i))^2$$ turns out to take the form of $$\hat \theta = \sum_{i=1}^n w_i \phi(x_i)^\top$$ for some coefficients $$w \in \Re^n$$. That is, the "optimal $$\theta$$" is actually a weighted sum of just $$\phi(x_1)^\top, \ldots, \phi(x_n)^\top$$ (negative coefficients are allowed, of course).

Replacing this in the definition of $$f$$, the "optimal" function looks like $$\hat f(\cdot) = \phi(\cdot) \hat \theta = \sum_{i=1}^n w_i \phi(\cdot) \phi(x_i)^\top = \sum_{i=1}^n w_i k(\cdot, x_i),$$ where $$k(x, y) = \phi(x) \phi(y)^\top = (1 + x^\top y)^2$$.

So, even if we start from the usual linear model, as far as we are concerned with such an "optimal" function estimated by minimizing an objective function based on the data, the solution coincides with a kernel linear model.

This is an example of a theoretical result (rather deep, I think) called the "Representer Theorem" of reproducing kernel Hilbert spaces. The same holds in much more general setups, where $$\phi$$ may be infinite dimensional, the objective function maybe something else (it holds pretty much for any loss function, and it does not have to be a sum), and there may be a "regularization" term.

## Confirmation

Let us denote $$Y = \begin{pmatrix}y_1 \\ \vdots \\ y_n\end{pmatrix}, \quad \Phi = \begin{pmatrix} \phi(x_1) \\ \vdots \\ \phi(x_n)\end{pmatrix}.$$ The optimal parameter of a linear model $$f(x) = \phi(x)\theta$$ is $$\hat \theta \in {\arg \min}_\theta \|Y - \Phi \theta\|^2 \\ \qquad\qquad= {\arg \min}_\theta \left\|\begin{pmatrix}y_1 \\ \vdots \\ y_n\end{pmatrix} - \begin{pmatrix}\phi(x_1) \theta \\ \vdots \\ \phi(x_n)\theta\end{pmatrix}\right\|^2.$$ Now, from the first-order condition, $$\hat \theta = (\Phi^\top \Phi)^{-1}\Phi^\top Y.$$ Inserting $$(\Phi \Phi^\top)(\Phi \Phi^\top)^{-1}$$ (i.e., the identity matrix), $$\hat \theta = (\Phi^\top \Phi)^{-1} \Phi^\top [\Phi \Phi^\top (\Phi \Phi^\top)^{-1}] Y = \Phi^\top (\Phi\Phi^\top)^{-1}Y \\ = (\phi(x_1)^\top \cdots \phi(x_n)^\top) \begin{pmatrix}w_1 \\ \vdots \\ w_n\end{pmatrix} = \sum_{i=1}^n w_i \phi(x_i)^\top,$$ where $$(w_1, \ldots, w_n)^\top = (\Phi\Phi^\top)^{-1}Y$$.

[1] Shalev-Shwartz, S., & Ben-David, S. (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press.