Kernel Methods: Working in Higher Dimensions

A telecom engineer is planning a new mobile tower. She sends field-test vans to sample locations around the proposed site and marks each one with two numbers — how far east of the tower it is, and how far north — plus a label: "usable signal" or "no signal." When she plots these points on graph paper, something inconvenient happens. The "usable signal" points cluster in a rough disc around the tower. The "no signal" points sit everywhere outside that disc. There is no straight line she can draw that puts all the usable-signal points on one side and all the no-signal points on the other, because the boundary between them is a circle, not a line. A linear classifier — the kind you meet first in machine learning, which draws one straight decision boundary — is mathematically incapable of solving this problem in its original two-dimensional form. This chapter is about the trick that fixes it: instead of struggling to bend a straight line into a circle, you change the space the line lives in.

Why a Straight Line Cannot Draw a Circle

Set up coordinates with the tower at the origin. A point at distance r from the tower has "usable signal" if r < R for some radius R, and "no signal" if r > R. Any linear classifier in two input variables x and y computes a score of the form w1·x + w2·y + b and checks its sign. The boundary where this score is exactly zero is always a straight line, because w1·x + w2·y + b = 0 is a first-degree (linear) equation in x and y — the same family of equations you graph in Class 10 coordinate geometry. A circle's equation, x² + y² = R², is second-degree. No choice of w1, w2, b can make a first-degree equation trace a second-degree curve. This is not a limitation of a particular algorithm; it is a fact about what linear equations can and cannot represent. To separate these two classes with a straight boundary, you need a space where the boundary becomes linear.

Here is the key move. Define a new coordinate: z = x² + y². Every data point now lives in three dimensions: (x, y, z). In this new space, "usable signal" points all satisfy z < R² and "no signal" points all satisfy z > R². The flat plane z = R² separates them perfectly — a linear boundary, in the lifted space, for what was a circular boundary in the original space. Nothing about the data changed; you simply gave the classifier one more coordinate to work with, computed as a fixed function of the coordinates you already had. This is the entire idea behind kernel methods, and everything else in this chapter is about making that idea precise, checkable, and computationally cheap.

Feature Maps and the Definition of a Kernel

Formalize the move you just made. A feature map is a function φ: ℝᵈ → ℝᴰ that sends each original data point to a (usually higher-dimensional) vector of new coordinates, D ≥ d. In the tower example, φ(x, y) = (x, y, x² + y²), taking d = 2 to D = 3. Once you apply φ, you run an ordinary linear classifier — a perceptron, a linear SVM, ridge regression — in the new space. Any boundary that is curved in the original coordinates but becomes flat after applying φ can now be found.

The catch is that many useful feature maps push D to be enormous, or even infinite, and you will meet an infinite-dimensional one later in this chapter. Computing and storing φ(x) directly then becomes impossible. The rescue is an observation about how these algorithms actually use the data: a linear SVM, a linear perceptron, and several other classical algorithms never need the individual vector φ(x) in isolation — they only ever need the dot product φ(x) · φ(y) between two data points, appearing inside a similarity or distance computation. This motivates the central definition of the chapter:

A function K(x, y) is a kernel if there exists some feature map φ such that K(x, y) = φ(x) · φ(y) for all x, y. If you can compute K(x, y) directly from x and y — without ever constructing φ(x) or φ(y) — you get the effect of working in the high-dimensional space φ maps into, at the computational cost of working in the low-dimensional space you started in. This substitution is called the kernel trick.

Worked Example: The Quadratic Kernel

Take two 2-dimensional points x = (x₁, x₂) and y = (y₁, y₂), and define K(x, y) = (x · y)². Expand it directly:

K(x, y) = (x₁y₁ + x₂y₂)² = x₁²y₁² + 2x₁x₂y₁y₂ + x₂²y₂²

Now compare this to the dot product of the vectors φ(x) = (x₁², √2·x₁x₂, x₂²) and φ(y) = (y₁², √2·y₁y₂, y₂²):

φ(x) · φ(y) = x₁²y₁² + (√2·x₁x₂)(√2·y₁y₂) + x₂²y₂² = x₁²y₁² + 2x₁x₂y₁y₂ + x₂²y₂²

The two expressions are identical, term for term. So K(x, y) = (x · y)² is genuinely a kernel: it equals a dot product in a 3-dimensional feature space, even though computing it never requires building that 3-dimensional vector. Verify it numerically:

import math

def K(x, y):
    return (x[0]*y[0] + x[1]*y[1]) ** 2

def phi(x):
    return (x[0]**2, math.sqrt(2) * x[0] * x[1], x[1]**2)

def dot(a, b):
    return sum(ai * bi for ai, bi in zip(a, b))

x = (1, 2)
y = (3, 1)

print(K(x, y))                 # 25
print(dot(phi(x), phi(y)))     # 25.0

Both lines print the value 25 (the second as a float, 25.0, since math.sqrt forces floating-point arithmetic) — an exact match, confirming the algebraic identity you derived above. A side note worth remembering when you write numerical code of your own: because √2 has no exact binary floating-point representation, computing φ(x) · φ(y) can in general differ from a directly-computed K(x, y) by a rounding error of roughly 10⁻¹⁵ to 10⁻¹⁶. This particular example happens to round back to an exact result, but as a rule you should compare floating-point values with a tolerance (Python's math.isclose) rather than ==.

Now notice the computational asymmetry that makes this trick worth learning. For d = 1000 input features (a realistic count for, say, a bag-of-words representation of an SMS message being classified as spam), the exact-degree-2 feature map φ has one coordinate for every pair of input features plus one for every squared feature — a count given by C(d+1, 2) = d(d+1)/2, which works out to 500,500 dimensions. Building and dotting two half-a-million-dimensional vectors for every pair of training points would be crippling. Computing K(x, y) = (x · y)² directly costs one 1000-dimensional dot product and one multiplication — a few thousand operations, regardless of how large the implied feature space is. The kernel trick did not just save some computation; it made an otherwise infeasible model tractable.

Not Every Function Is a Kernel: The Gram Matrix Test

You cannot just invent a formula K(x, y) and assume it corresponds to some dot product in some space. Some formulas do; some don't. The check that separates them uses the Gram matrix: given any finite set of points x₁, ..., xₙ, the Gram matrix is the n × n matrix with entries Mᵢⱼ = K(xᵢ, xⱼ).

Here is why this matrix matters. If K really is φ(x) · φ(y) for some feature map, then M is exactly the matrix of pairwise dot products of the vectors φ(x₁), ..., φ(xₙ). A basic fact from linear algebra is that any matrix of pairwise dot products of real vectors is automatically symmetric positive semi-definite (PSD) — every eigenvalue is greater than or equal to zero. This is not an extra assumption; it follows from K(xᵢ,xᵢ) = ||φ(xᵢ)||² ≥ 0 and the geometry of dot products. Mercer's theorem provides the converse, which is what makes this a genuine two-way test: if K is symmetric and its Gram matrix is PSD for every possible finite set of points, then some feature map φ (possibly infinite-dimensional) exists with K(x,y) = φ(x)·φ(y), even if you never construct it. So checking the Gram matrix for a handful of sample points is a genuine way to catch a broken candidate kernel — if you find even one negative eigenvalue, K is disqualified outright.

For a 2 × 2 symmetric matrix M = [[a, b], [b, d]], you can test the eigenvalues' signs without computing them, using a fact you already know from Class 10 quadratic equations. The eigenvalues are the roots of the characteristic equation λ² − (a+d)λ + (ad − b²) = 0, a quadratic in λ. From the standard result "sum of roots = −B/A, product of roots = C/A" applied to this equation:

• sum of the two eigenvalues = trace(M) = a + d
• product of the two eigenvalues = det(M) = ad − b²

If det(M) < 0, the product of the eigenvalues is negative, which is only possible if one eigenvalue is positive and the other negative — so M cannot be PSD, and K is not a valid kernel. This single check, using arithmetic you already have, is enough to disprove validity.

Apply it to a plausible-looking but broken candidate, K(u, v) = −uv, using the two distinct points a = 1, b = 2:

M = [[K(1,1), K(1,2)], [K(2,1), K(2,2)]] = [[−1, −2], [−2, −4]]

trace(M) = −1 + (−4) = −5, and det(M) = (−1)(−4) − (−2)(−2) = 4 − 4 = 0. The characteristic equation is λ² + 5λ = 0, giving λ(λ+5) = 0, so the eigenvalues are exactly 0 and −5. One of them is negative, so M is not PSD, and K(u,v) = −uv is not a valid kernel — despite looking like an innocent, dot-product-shaped formula. The single minus sign is enough to break it, because it forces K(u,u) = −u², which is negative for any nonzero u — and a valid kernel must always give K(x,x) = ||φ(x)||² ≥ 0, since a squared length can never be negative. You can verify the eigenvalues numerically too:

import numpy as np

def K(u, v):
    return -u * v

pts = [1, 2]
M = [[K(a, b) for b in pts] for a in pts]

print(M)                            # [[-1, -2], [-2, -4]]
print(np.linalg.eigvalsh(np.array(M, dtype=float)))   # [-5.  0.]

Common Kernels You Will Actually Use

The linear kernel, K(x, y) = x · y, is the trivial case: φ is the identity, and you simply run a linear classifier on the raw data. The polynomial kernel, K(x, y) = (x · y + c)^p for a constant c ≥ 0 and positive integer p, generalizes the worked example above: it corresponds to a feature map whose coordinates are every monomial of degree up to p in the input coordinates, scaled by specific binomial coefficients (the c allows lower-degree terms to appear alongside the pure degree-p ones). It is a genuine kernel because a sum, product, and positive scaling of valid kernels is again a valid kernel — you do not need to re-derive the feature map by hand each time to trust it.

The kernel most worth understanding deeply is the RBF (radial basis function) kernel, also called the Gaussian kernel, because it is the cleanest example of a feature map with infinitely many dimensions — the case where the kernel trick stops being a convenience and becomes the only way the method could work at all.

Deriving the Infinite-Dimensional RBF Kernel

Take the simplest version, for scalar inputs x, y: K(x, y) = e^{-(x-y)²}. Expand the exponent:

−(x−y)² = −x² + 2xy − y² = −x² − y² + 2xy

so K(x, y) = e^{-x²} · e^{-y²} · e^{2xy}. Now use the Taylor series for the exponential function, which you know from Class 12 calculus: eᵗ = Σₖ₌₀^∞ tᵏ/k!, valid for every real t. Substituting t = 2xy:

e^{2xy} = Σₖ₌₀^∞ (2xy)ᵏ/k! = Σₖ₌₀^∞ (2ᵏ/k!)·xᵏyᵏ

Substitute this back in and split each term:

K(x,y) = Σₖ₌₀^∞ e^{-x²}e^{-y²}·(2ᵏ/k!)·xᵏyᵏ = Σₖ₌₀^∞ [e^{-x²}xᵏ·√(2ᵏ/k!)] · [e^{-y²}yᵏ·√(2ᵏ/k!)]

which is exactly the form Σₖ φₖ(x)·φₖ(y), i.e., a dot product, with the k-th coordinate of the feature map defined as:

φₖ(x) = e^{-x²} · √(2ᵏ/k!) · xᵏ,   k = 0, 1, 2, 3, ...

Write out the first few coefficients √(2ᵏ/k!): for k=0 it is √(1/1) = 1; for k=1 it is √(2/1) = √2; for k=2 it is √(4/2) = √2 again; for k=3 it is √(8/6) = √(4/3) ≈ 1.155 — no longer √2, so do not assume the first two coefficients set a lasting pattern. Each k contributes its own term computed from the general formula, and the sum runs forever: φ(x) is a vector with infinitely many coordinates, one for every non-negative integer k. No computer could ever store this vector in full, let alone dot two of them together term by term. And yet K(x, y) = e^{-(x-y)²} is a single subtraction, a square, a sign flip, and one call to exp — computable in microseconds. This is the kernel trick at its most powerful: genuine, provable access to an infinite-dimensional feature space, at the cost of evaluating one elementary function.

(The vector version used in practice, K(x, y) = e^{-γ||x-y||²} for x, y ∈ ℝᵈ and a bandwidth parameter γ > 0, follows the same expansion applied coordinate-by-coordinate; the derivation above is the essential idea in its cleanest form.)

Where This Shows Up: Kernel SVMs

A trained support vector machine classifies a new point x using a decision rule of the form:

f(x) = sign( Σᵢ αᵢ yᵢ K(xᵢ, x) + b )

where x₁, ..., xₙ are the training points, yᵢ ∈ {−1, +1} are their labels, and αᵢ, b are learned during training. Notice that the training points never appear as raw feature vectors dotted against a weight vector — they appear only inside kernel evaluations against the new point. Swap the kernel formula, and the entire boundary the model can represent changes, from a straight line (linear kernel) to a curved surface of arbitrary flexibility (RBF kernel), without touching the training algorithm at all.

This power has a real cost. Training a kernel SVM requires computing the full n × n Gram matrix over all pairs of training points — that is n² kernel evaluations before optimization even begins. A kernel SVM is therefore indifferent to how large or even infinite the feature space is, but it is sensitive to how many training examples you have: doubling your dataset roughly quadruples the Gram-matrix cost. This is why, on datasets with a few thousand carefully chosen examples, a kernel SVM with an RBF kernel routinely outperforms simpler models — but on datasets with millions of examples, practitioners typically fall back to models built on explicit (if approximate) features, because the n² cost becomes the bottleneck long before the feature-space richness does. Knowing which regime you are in — dimension-hungry or sample-hungry — is the practical judgment call that decides whether to reach for a kernel method at all.

Common Misconception, Corrected

It is tempting to think: "so a kernel method first transforms every data point into its high-dimensional φ(x), and then trains an ordinary linear model on those transformed vectors." This is not what a kernel method does, and believing it defeats the entire purpose of learning this technique. The worked examples above computed φ(x) explicitly only to prove that K matches some dot product — a one-time act of verification, done on paper. In an actual kernel SVM, ridge regression, or kernel PCA implementation, φ is never evaluated. Every single place the algorithm would need φ(x) or φ(x)·φ(y), it substitutes a direct call to K(x, y) instead. For the RBF kernel, this distinction is not just an efficiency trick — it is the only reason the method can run at all, since φ(x) for the RBF kernel has infinitely many coordinates and literally cannot be computed or stored. If your mental model requires materializing φ(x), your mental model does not extend to kernels like RBF, and you have not yet understood the trick.

Active Recall

1. Q: For the scalar feature map φ(x) = (x, x²), write K(x, y) = φ(x) · φ(y) as a formula in x and y, and evaluate K(2, 3).
   A: K(x, y) = xy + x²y². At x=2, y=3: xy = 6, x²y² = 4 × 9 = 36, so K(2,3) = 6 + 36 = 42.
2. Q: Test whether K(u, v) = uv − 1 is a valid kernel using the Gram-matrix method, with the two distinct points a = 0, b = 1.
   A: K(0,0) = 0·0−1 = −1, K(0,1) = K(1,0) = 0·1−1 = −1, K(1,1) = 1·1−1 = 0. So M = [[−1, −1], [−1, 0]]. trace(M) = −1, det(M) = (−1)(0) − (−1)(−1) = 0 − 1 = −1. Since det(M) < 0, the eigenvalues have opposite signs, so M is not PSD — K(u,v) = uv − 1 is not a valid kernel.
3. Q: Why does the polynomial kernel (x·y)² matter more as d (the number of input features) grows, rather than less?
   A: The implied feature space has dimension d(d+1)/2, which grows quadratically in d. Computing K directly still costs one d-dimensional dot product (linear in d) plus a squaring. As d grows, the gap between the two costs widens — the kernel trick's saving gets larger, not smaller.
4. Q: Using the general RBF coefficient formula √(2ᵏ/k!), compute the coefficient for k = 4, and confirm it is not √2.
   A: 2⁴/4! = 16/24 = 2/3, so the coefficient is √(2/3) ≈ 0.8165 — noticeably smaller than √2 ≈ 1.4142, confirming the coefficients only coincide at k=1 and k=2.
5. Q: True or false: "To use a kernel SVM, you must first explicitly compute the high-dimensional feature vector for every training point, then train a plain linear SVM on those vectors." Justify your answer.
   A: False. The kernel trick exists precisely to avoid this. The algorithm calls K(xᵢ, xⱼ) directly wherever a dot product in feature space is needed, and never constructs φ(x). For kernels like RBF, whose feature space is infinite-dimensional, explicit construction is not just inefficient — it is impossible.

Summary

• A linear classifier can only draw straight (or flat, in higher dimensions) decision boundaries. A feature map φ sends data into a higher-dimensional space where a boundary that was curved becomes flat.
• A kernel K(x,y) is a function equal to φ(x)·φ(y) for some feature map. The kernel trick computes K(x,y) directly, without ever forming φ(x), giving the modeling power of the high-dimensional space at the computational cost of the original one.
• The quadratic kernel (x·y)² was derived and numerically verified to match φ(x)·φ(y) exactly for an explicit 3-dimensional φ.
• Not every formula is a valid kernel. The Gram matrix Mᵢⱼ = K(xᵢ,xⱼ) must be symmetric positive semi-definite for every possible set of points (Mercer's theorem); for a 2×2 Gram matrix, this can be checked using the sum-and-product-of-roots relations from Class 10 quadratics: if det(M) < 0, the kernel is immediately disqualified.
• The RBF kernel e^{-(x-y)²} was derived via the Taylor expansion of eᵗ to correspond to an explicit, infinite-dimensional feature map with k-th coefficient √(2ᵏ/k!) — proof that the kernel trick is sometimes not a convenience but the only way the method can be run at all.
• In a trained kernel SVM, f(x) = sign(Σᵢ αᵢyᵢK(xᵢ,x) + b): training points appear only inside kernel evaluations. This buys flexibility in feature-space dimension at the cost of an n² Gram-matrix computation over the number of training points — the trade-off that decides when a kernel method is the right tool.

Think About It

Think about this: How would you explain kernel methods: working in higher dimensions to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.