The Kernel Trick

Throughout our journey in regression, we have relied heavily on linear models—methods that express predictions as weighted combinations of input features. Linear regression, ridge regression, and lasso all share this fundamental assumption: the relationship between inputs and outputs can be captured by a linear function.

But here lies a profound limitation: the real world is rarely linear.

Consider these everyday phenomena:

• The trajectory of a thrown ball follows a parabola, not a straight line
• Drug dosage effects often follow sigmoidal curves with diminishing returns
• Economic relationships exhibit complex interactions and threshold effects
• Audio signals contain harmonic frequencies that multiply rather than add

When we attempt to model these nonlinear relationships with linear methods, we are fundamentally limited—not by our algorithmic prowess, but by our representation of the problem.

Let us formalize what we mean by 'linear' and understand precisely where this constraint binds us.

The Linear Model Structure

A linear model in its most general form predicts:

$$\hat{y} = f(\mathbf{x}) = \mathbf{w}^\top \mathbf{x} + b = \sum_{j=1}^{d} w_j x_j + b$$

where:

• $\mathbf{x} \in \mathbb{R}^d$ is the input feature vector
• $\mathbf{w} \in \mathbb{R}^d$ is the weight vector
• $b \in \mathbb{R}$ is the bias term

This model is called 'linear' because $f(\mathbf{x})$ is a linear function of $\mathbf{x}$—technically, an affine function since we include the bias. The crucial property is that the prediction changes proportionally and additively with each input feature.

Geometric Interpretation

Geometrically, a linear model in $d$ dimensions defines a hyperplane that separates or fits the data:

• In 2D: the model is a line $y = w_1 x_1 + w_2 x_2 + b$
• In 3D: the model is a plane $y = w_1 x_1 + w_2 x_2 + w_3 x_3 + b$
• In $d$ dimensions: a $(d-1)$-dimensional hyperplane

The fundamental limitation is clear: a hyperplane can only capture relationships that are themselves planar. When the true relationship curves, bends, or twists through space, no hyperplane—no matter how cleverly positioned—can adequately describe it.

The XOR Problem: A Classic Example

The limitations of linearity are starkly illustrated by the XOR problem—a pattern that is trivially simple for nonlinear methods but fundamentally impossible for any linear classifier:

• Points at $(0,0)$ and $(1,1)$ belong to class 0
• Points at $(0,1)$ and $(1,0)$ belong to class 1

No single line can separate these four points by class. This is because the XOR function is not linearly separable—there exists no hyperplane that places all class-0 points on one side and all class-1 points on the other.

This example, though simple, represents a fundamental barrier that appears throughout machine learning whenever the underlying relationship involves interactions, thresholds, or complex dependencies between features.

Here is the key insight that unlocks nonlinear modeling with linear methods:

If the data is not linearly separable in its current representation, perhaps it becomes linearly separable in a different representation.

This deceptively simple idea—transforming the data before applying a linear method—is the foundation of feature space mapping and, ultimately, kernel methods.

The Core Strategy

Instead of fitting a linear model to the original features $\mathbf{x}$, we:

1. Define a feature map $\phi: \mathbb{R}^d \rightarrow \mathbb{R}^D$ that transforms inputs into a new space
2. Fit a linear model in the transformed space: $f(\mathbf{x}) = \mathbf{w}^\top \phi(\mathbf{x})$
3. The model is linear in $\phi(\mathbf{x})$ but nonlinear in $\mathbf{x}$

Solving XOR with Feature Transformation

Let us return to the XOR problem. With original features $\mathbf{x} = (x_1, x_2)$, no linear separator exists. But consider this feature map:

$$\phi(x_1, x_2) = (x_1, x_2, x_1 \cdot x_2)$$

We have added a third dimension: the product of the two original features. Now let's examine the transformed points:

In the 3D transformed space, the class-0 points have $x_1 x_2 \in {0, 1}$ spanning both extremes, while class-1 points have $x_1 x_2 = 0$. A hyperplane like $x_1 x_2 = 0.5$ now separates the classes perfectly!

The XOR problem, unsolvable by any linear method in the original space, becomes trivially solvable after the right transformation.

The most natural and widely used feature transformation is polynomial expansion—constructing new features as polynomial combinations of the original features.

Univariate Polynomial Features

For a single input $x$, a polynomial feature map of degree $p$ is:

$$\phi_p(x) = (1, x, x^2, x^3, \ldots, x^p)$$

A linear model in this transformed space:

$$f(x) = w_0 + w_1 x + w_2 x^2 + \cdots + w_p x^p$$

is a polynomial of degree $p$ in $x$. By choosing $p$ large enough, we can approximate any continuous function arbitrarily well (by the Weierstrass approximation theorem).

Multivariate Polynomial Features

For $d$-dimensional inputs, polynomial features include all monomials up to degree $p$:

$$\phi_p(\mathbf{x}) = (1, x_1, x_2, \ldots, x_d, x_1^2, x_1 x_2, x_1 x_3, \ldots, x_d^p)$$

This includes:

• All individual features: $x_j$
• All pairwise products: $x_i x_j$
• All higher-order interactions: $x_i x_j x_k$, etc.
• All pure powers: $x_j^2, x_j^3, \ldots$

Dimension of Polynomial Feature Spaces

The dimensionality $D$ of the polynomial feature space is given by:

$$D = \binom{d + p}{p} = \frac{(d + p)!}{d! \cdot p!}$$

Some examples:

The exponential growth makes explicit feature computation infeasible for high degrees or high-dimensional inputs.

Why Polynomial Features Work

Polynomial features work because they capture:

1. Nonlinear effects: Powers like $x^2$ and $x^3$ model curvature
2. Interaction effects: Products like $x_1 x_2$ capture dependencies between features
3. Threshold effects: High-degree terms can approximate step-like functions

The Taylor series expansion tells us that any smooth function can be locally approximated by a polynomial. With enough polynomial features and appropriate regularization, we can model arbitrarily complex relationships.

While polynomial features are intuitive, they are just one family among infinitely many possible feature transformations. The concept of feature mapping is far more general.

The Abstract Perspective

A feature map (also called a basis function expansion) is any function:

$$\phi: \mathcal{X} \rightarrow \mathcal{H}$$

that transforms inputs from the original space $\mathcal{X}$ (often $\mathbb{R}^d$) into a feature space $\mathcal{H}$ (often $\mathbb{R}^D$ with $D > d$, or even infinite-dimensional).

The only requirement is that we can subsequently fit a linear model in $\mathcal{H}$:

$$f(\mathbf{x}) = \mathbf{w}^\top \phi(\mathbf{x}) = \sum_{j=1}^{D} w_j \phi_j(\mathbf{x})$$

Different choices of $\phi$ encode different inductive biases—assumptions about what kinds of functions are likely to fit the data well.

Radial Basis Function Features

RBF features are particularly important because they connect to the Gaussian kernel we will study later:

$$\phi_\text{RBF}(\mathbf{x}) = \left( \exp\left(-\gamma |\mathbf{x} - \mathbf{c}_1|^2\right), \ldots, \exp\left(-\gamma |\mathbf{x} - \mathbf{c}_m|^2\right) \right)$$

Each feature measures the similarity of $\mathbf{x}$ to a center point $\mathbf{c}_j$. Points near $\mathbf{c}_j$ activate that feature strongly; distant points activate it weakly.

The parameter $\gamma$ controls the bandwidth:

• Large $\gamma$: narrow, localized bumps (each center affects only nearby points)
• Small $\gamma$: broad, overlapping bumps (each center affects points far away)

With enough centers (potentially one per training point), RBF features can approximate any function.

To truly understand why feature mapping works, we must develop geometric intuition for what happens when we lift data into higher dimensions.

The Lifting Metaphor

Imagine you have points scattered on a sheet of paper (2D), and they cannot be separated by a straight line. Now imagine crumpling that paper into a ball (embedding it in 3D). Suddenly, a plane that cuts through the ball might separate the points that were inseparable on the flat sheet.

This is precisely what feature mapping does: it lifts data from a low-dimensional space where linear separation is impossible into a higher-dimensional space where it becomes possible.

Mathematical Intuition

Consider points on a circle: $\mathbf{x} = (\cos\theta, \sin\theta)$. In 2D, these points lie on a curve. But with the feature map:

$$\phi(x_1, x_2) = (x_1^2, \sqrt{2} x_1 x_2, x_2^2)$$

the transformed points satisfy:

$$|\phi(\mathbf{x})|^2 = x_1^4 + 2x_1^2 x_2^2 + x_2^4 = (x_1^2 + x_2^2)^2 = 1$$

All points on the unit circle in 2D lie on a specific manifold in feature space. The curved structure in the original space becomes a different (possibly simpler) structure in feature space.

The Inner Product Perspective

A crucial insight emerges when we consider inner products in feature space. The inner product between two transformed points is:

$$\langle \phi(\mathbf{x}), \phi(\mathbf{x}') \rangle = \sum_{j=1}^{D} \phi_j(\mathbf{x}) \phi_j(\mathbf{x}')$$

This inner product measures similarity in feature space. Points that are similar (in the transformed representation) have large inner products; dissimilar points have small ones.

Here is the key observation that leads to kernels:

For certain feature maps, the inner product $\langle \phi(\mathbf{x}), \phi(\mathbf{x}') \rangle$ can be computed directly from $\mathbf{x}$ and $\mathbf{x}'$, without ever computing $\phi(\mathbf{x})$ or $\phi(\mathbf{x}')$ explicitly.

This observation is the foundation of the kernel trick, which we will develop in the next page.

We have established that feature mapping enables linear methods to learn nonlinear patterns. However, this power comes with a severe computational burden.

The Explicit Feature Problem

Consider ridge regression with polynomial features of degree $p$. The algorithm requires:

1. Feature computation: Transform all $n$ training points: $O(n \cdot D)$
2. Gram matrix: Compute $\Phi^\top \Phi$ where $\Phi$ is $n \times D$: $O(n D^2)$ multiplications
3. Inversion: Solve the normal equations: $O(D^3)$
4. Prediction: For each test point, compute $D$-dimensional features: $O(D)$

When $D = \binom{d+p}{p}$ grows exponentially in $p$, even storing the feature matrix becomes infeasible, let alone computing with it.

A Concrete Example

With $d = 100$ input features and degree $p = 5$:

• Feature dimension: $D \approx 96$ million
• Feature matrix for $n = 10,000$ points: $10^4 \times 10^8 = 10^{12}$ elements
• Storage at 8 bytes/double: ~8 terabytes
• Matrix multiplication: $10^{24}$ operations

This is utterly impractical. Yet the underlying model—a degree-5 polynomial—might be exactly what we need.

Infinite-Dimensional Feature Spaces

Some of the most powerful feature maps are not just high-dimensional but infinite-dimensional. The Gaussian RBF feature map, for example, maps each input to an infinite-dimensional vector:

$$\phi_\text{Gaussian}(\mathbf{x}) \in \mathbb{R}^\infty$$

We cannot possibly compute or store infinite-dimensional vectors. Yet, as we will see, we can work with them through kernels.

The Dual Representation Hint

Recall from our study of ridge regression that the solution can be written in dual form:

$$\mathbf{w} = \Phi^\top \boldsymbol{\alpha} = \sum_{i=1}^{n} \alpha_i \phi(\mathbf{x}_i)$$

for some coefficients $\boldsymbol{\alpha} \in \mathbb{R}^n$. The weight vector is a linear combination of the training points in feature space.

This means that predictions become:

$$f(\mathbf{x}) = \mathbf{w}^\top \phi(\mathbf{x}) = \sum_{i=1}^{n} \alpha_i \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}) \rangle$$

The prediction depends only on inner products between the test point and training points in feature space—not on the features themselves!

This observation is the gateway to the kernel trick: if we can compute these inner products efficiently, we never need the features explicitly.

We have built up to a remarkable insight. Let us state it clearly before developing it fully in the next page.

The Key Observation

For certain feature maps $\phi$, there exists a kernel function $k$ such that:

$$k(\mathbf{x}, \mathbf{x}') = \langle \phi(\mathbf{x}), \phi(\mathbf{x}') \rangle$$

The kernel computes the inner product in feature space directly from the original inputs, without ever constructing the feature vectors.

Example: Polynomial Kernel

For the degree-2 polynomial feature map we saw earlier, the kernel is simply:

$$k(\mathbf{x}, \mathbf{x}') = (\mathbf{x}^\top \mathbf{x}')^2$$

Computing the left side: one inner product and one squaring — $O(d)$.

Computing the right side explicitly: construct $O(d^2)$ features, then take inner product — $O(d^2)$.

The kernel is quadratically faster, and this gap widens with polynomial degree.

Algorithms That Work With Kernels

Not all algorithms can exploit the kernel trick—only those whose computations can be expressed entirely in terms of inner products between data points. Fortunately, many important algorithms qualify:

• Ridge regression (kernel ridge regression)
• Support vector machines (kernel SVM)
• Principal component analysis (kernel PCA)
• Gaussian processes (built on kernels)
• Kernel k-means clustering

These algorithms can be "kernelized" to work in arbitrary feature spaces defined by the kernel.

What Comes Next

In the following pages, we will:

1. Formally define kernel functions and their properties
2. Prove that the kernel trick preserves computational correctness
3. State Mercer's theorem, which characterizes valid kernels
4. Survey common kernel families and their geometric interpretations
5. Apply kernels to regression (kernel ridge regression and Gaussian processes)

We have established the foundational concepts that motivate kernel methods:

The Problem: Linear models cannot capture nonlinear relationships in data. When the true function is curved, kinked, or involves interactions, linear predictions fail.

The Solution: Transform the data using a feature map $\phi$ into a new space where the relationship is linear. A model that is linear in $\phi(\mathbf{x})$ can be arbitrarily nonlinear in $\mathbf{x}$.

The Challenge: Explicit feature computation is infeasible when the feature dimension is very large or infinite.

The Insight: We only need inner products in feature space. If we can compute $\langle \phi(\mathbf{x}), \phi(\mathbf{x}') \rangle$ directly via a kernel $k(\mathbf{x}, \mathbf{x}')$, we bypass the explicit feature computation entirely.