Kernel Methods

Introduction

A linear model makes predictions using:

For squared-error regression, a batch gradient descent update is:

The problem is that a linear model can only represent linear relationships in the features we give it.

If the relationship is nonlinear, we can create new features using a feature map:

Instead of using $x$ directly, we replace it with $\phi(x)$. The update becomes:

The model is still linear in the transformed features $\phi(x)$, but it can now represent a nonlinear relationship in the original input space.

The same idea applies to classification.

For example, mapping $(x_1,x_2)$ to $(x_1^2,x_2^2)$ turns a boundary of the form

into a linear boundary in the transformed feature space.

The drawback is that the transformed feature vector can become very large.

For example, suppose $\phi(x)$ contains all ordered products of the original features up to degree $3$. The number of features is:

So explicitly constructing $\phi(x)$ and storing $\theta$ can require $\Theta(d^3)$ values.

The Kernel Trick

The key observation is that gradient descent never needs $\theta$ to point outside the span of the transformed training examples.

If we start with:

then every update adds a linear combination of the vectors $\phi(x^{(i)})$. Therefore, every later value of $\theta$ can be written as:

Instead of storing $\theta$ directly, we can therefore store the coefficients $\beta_i$.

Substituting this representation into the gradient update gives an update for those coefficients.

Therefore:

For a batch gradient step, all $\beta_i$ are updated simultaneously using the current parameter values.

Now substitute:

into the prediction term.

This is the important result: the algorithm only needs inner products between transformed examples.

We define a kernel as this feature-space inner product:

If $K(x,z)$ can be computed directly from $x$ and $z$, we never need to explicitly construct $\phi(x)$.

This is the kernel trick.

The coefficient update becomes:

For a fixed training set, we can store all pairwise kernel values in the Gram matrix:

This avoids recomputing the same kernel values on every iteration.

A feature-map example

Suppose our feature map contains all ordered products of degrees $0$ through $3$.

Computing the inner product explicitly would require $\Theta(d^3)$ work. However, the same inner product can be simplified to a function of the original dot product $\langle x,z\rangle$.

So instead of constructing $\Theta(d^3)$ features, we compute one ordinary dot product in $O(d)$ time and evaluate:

The kernel trick avoids the cost of explicitly constructing a large feature vector, but it introduces a different cost: kernel methods often scale poorly with the number of training examples.

Storing the full Gram matrix requires:

memory.

Prediction also requires only kernel evaluations. For a new input $x$:

So both training and prediction can be carried out without explicitly computing $\phi(x)$.

Common Kernels

A kernel determines how two inputs are compared in feature space.

Common choices include:

The linear kernel is just the ordinary dot product, so it does not introduce nonlinear features.

The polynomial kernel allows the model to use interactions between features up to degree $p$ when $c>0$.

The RBF kernel gives high similarity to nearby points and low similarity to distant points. It corresponds to an infinite-dimensional feature space.

The polynomial degree $p$ and RBF length scale $\sigma$ control how flexible the model is. These should usually be chosen using validation data.

Feature scaling is especially important for polynomial and RBF kernels because both depend strongly on feature magnitudes or distances.

Kernel Ridge Regression

The kernel trick is not a learning algorithm by itself. It is a way to rewrite algorithms so that they depend only on kernel evaluations.

Kernel ridge regression is one example.

It fits the training data using squared error while penalizing overly complex functions:

The representer theorem tells us that the solution can always be written using the training examples:

Let $K\in\mathbb{R}^{n\times n}$ be the Gram matrix:

and let:

The optimal coefficients satisfy:

We solve this linear system for $\alpha$.

For a new input $x$, define:

Prediction is then:

The parameter $\lambda$ controls regularization.

A larger $\lambda$ penalizes complex functions more strongly, while a smaller $\lambda$ places more emphasis on fitting the training data.

Because $\lambda>0$, the matrix:

is positive definite even when $K$ is only positive semidefinite, so the linear system has a unique solution.

A direct solve takes:

time, while storing the Gram matrix requires:

memory.

This motivates approximate kernel methods for large datasets.

Validity of Kernels

Not every similarity function can be used as a kernel.

A valid kernel must behave like an inner product in some feature space.

More formally, $K(x,z)$ must be symmetric, and for any finite set of inputs:

the Gram matrix:

must be positive semidefinite.

Equivalently, there must exist a feature map $\phi$ such that:

One way to prove that a kernel is valid is to explicitly construct such a feature map.

Consider the quadratic kernel:

For $x\in\mathbb{R}^3$, one possible feature map is:

Its inner product reproduces the kernel.

Therefore, this is a valid kernel.

More generally, every valid kernel must produce a positive-semidefinite Gram matrix for every finite set of inputs.

For any coefficient vector $a$:

To see why, suppose:

Then:

The final expression is a sum of squares, so it can never be negative. This is why any kernel that corresponds to an inner product produces a positive-semidefinite Gram matrix.