skip to content

What is the kernel trick in an SVM, and what does it avoid computing?

level: middleimportance: must knowfreq 72%

answer

  1. similarity score, not new columns
  2. the algorithm only sees pairwise inner products
  3. equals an inner product after a map
  4. 171,700 columns never materialised
  5. RBF's implicit space is infinite-dimensional

basics

~20 s

A kernel returns the inner product two points would have after being mapped into a high-dimensional feature space, computed straight from the original coordinates. An SVM needs only those inner products, so the lifted features are never built.

solid answer

~50 s

A linear separator is stuck with a flat boundary. You can bend it by lifting the points into a richer space of derived features and separating them there, but that space can be huge. A kernel `k(x, z)` is a function of two points that equals `<phi(x), phi(z)>`, the inner product of their images under some feature map `phi`, evaluated without ever applying `phi`. Because an SVM's training problem and its scoring rule touch the data only through inner products between pairs of points, you substitute `k` for every inner product and get the lifted model for the price of the original coordinates. A degree-3 polynomial kernel on 100 features gives you all three-way products of those features — 171,700 of them — from one dot product plus one cube. The RBF kernel goes further: its implicit space is infinite-dimensional, so no explicit column set exists at all.

code

python · 15 lines
python
# A degree-2 polynomial kernel vs. the explicit feature map it stands in for.
x = [1.0, 2.0, 3.0]
z = [0.5, -1.0, 2.0]

def dot(a, b):
    return sum(p * q for p, q in zip(a, b))

def phi(v):
    # the explicit lift: every pairwise product of the coordinates
    return [vi * vj for vi in v for vj in v]

kernel = dot(x, z) ** 2           # one dot product in the original 3-D space
explicit = dot(phi(x), phi(z))    # the 9-D lift, actually built and multiplied

print(kernel, explicit)           # 20.25 20.25 - the same number

go deeper

for a junior

Recall the one-sentence version: a kernel gives you the effect of adding lots of derived features without building them, which is how an SVM draws a curved boundary. Know that linear, polynomial and RBF are the usual choices.

for a middle

Be ready to write k(x, z) = <phi(x), phi(z)> and to expand a squared dot product by hand into its explicit feature map. Explain why an SVM in particular can use it: the algorithm sees the data only as pairwise inner products.

for a senior

Show you know what the trick costs in practice — memory that grows with rows rather than features, no readable per-feature coefficients, and a model that must carry its support vectors to score anything. Say when that trade is not worth taking.

for a principal

Own the framing that the kernel is a modelling assumption, not a computational convenience: it declares which pairs of points should count as similar. Be able to argue when encoding that prior beats letting a more flexible model learn it from data.

## The problem the trick solves A linear classifier can only cut the input space with a flat boundary — a line in two dimensions, a plane in three, a hyperplane in general. Plenty of real data refuses to cooperate. Picture two concentric rings of readings, one class on the inner ring and one on the outer: no straight line separates them, however you rotate it, yet the classes are perfectly distinguishable. The classical fix is to invent new features. Add squares, products and cross-terms, fit a flat boundary in that enlarged space, and the boundary looks curved when you project it back. It works, and it has a price: the enlarged space can be enormous. Take 100 input features and ask for every three-way product of them (repetitions allowed, so `x1*x1*x7` counts): that is 171,700 new columns. Every training row becomes a 171,700-long vector that you must build, hold and multiply out. ## What a kernel actually is A kernel is a function of two points, `k(x, z)`, that equals an inner product in some feature space: ``` k(x, z) = <phi(x), phi(z)> ``` for some map `phi` from the input space into that feature space. The point is that you evaluate the left-hand side using only the original coordinates, and never touch `phi`. The smallest honest example: take two-dimensional inputs and the kernel `k(x, z) = (x . z)^2`. Expanding, ``` (x1*z1 + x2*z2)^2 = x1^2*z1^2 + 2*x1*x2*z1*z2 + x2^2*z2^2 ``` which is exactly the inner product of `phi(x) = (x1^2, sqrt(2)*x1*x2, x2^2)` with `phi(z)`. One multiplication and one square on the left; a three-dimensional lift on the right. Scale that from 2 inputs to 100 and from degree 2 to degree 3 and the right-hand side is the 171,700-column monster while the left-hand side is unchanged in cost. ## Why the SVM in particular can use it A margin classifier's training problem and its scoring rule reach the data only through inner products between pairs of points — never through an individual coordinate on its own. That is the structural property the trick exploits. Replace every occurrence of `x . z` with `k(x, z)` and you have fitted the model in the feature space without visiting it. The trained model keeps a subset of the training points (the support vectors) with a weight on each, and scores a new point `x` as a weighted sum of `k(support_vector, x)` plus an offset; the sign of that sum is the predicted class. The same property is what makes the trick portable: any method expressible purely in pairwise inner products can be kernelised. A method that needs individual coordinates cannot. ## The standard kernels - **Linear**: `k(x, z) = x . z`. The identity map — no lift at all, the honest baseline. - **Polynomial**: `k(x, z) = (x . z + c)^d`. With `c = 0` the implicit features are the monomials of degree exactly `d`; with `c > 0` they are all monomials up to degree `d`, weighted. `d` sets the highest order of feature interaction the model can express. - **RBF / Gaussian**: `k(x, z) = exp(-gamma * ||x - z||^2)`. It equals 1 when the points coincide and decays smoothly towards 0 as they separate. Its implicit feature space is infinite-dimensional, which is the sharpest demonstration that the trick buys you something you could not have written down by hand. ## What you give up You trade an explicit column space for an n-by-n table of pairwise kernel values, so memory now scales with the number of training rows rather than the number of derived features. You lose per-feature coefficients: there is no weight vector in the original space to read off, so the fitted model is not directly interpretable feature by feature. And the model is not self-contained arithmetic on a weight vector — it must carry its support vectors around and evaluate the kernel against each of them to score anything. ## The boundary of the idea Two limits are worth stating out loud. First, the trick is not free capacity: a lift into a space that rich makes overfitting easy, which is why kernel SVMs come with a regularisation dial and why the kernel's own hyperparameters need tuning. Second, not every symmetric similarity function you can dream up is a kernel — it has to correspond to a genuine inner product, which is a checkable condition on the matrix of pairwise values, not an assumption you get for free.

  • Which algorithms can be kernelised, and which cannot?
    Any method whose training and prediction rules touch the data only through inner products between pairs of points. If you can write the whole procedure with `x . z` and never with an individual coordinate, you can swap in a kernel. Methods that need coordinates directly — anything that thresholds or scales a single named feature, for instance — have no inner-product form to substitute into.
  • The RBF kernel corresponds to an infinite-dimensional feature space. Why doesn't that guarantee perfect separation on any data?
    It very nearly does on the training set, and that is the problem. Enough capacity to separate any labelled sample means the model can fit noise as easily as signal, so training error stops being evidence of anything. What keeps an RBF SVM useful is the regularisation that limits how hard it fights for each point, plus tuning the kernel's own width parameter on held-out data.
  • If a kernel model gives no per-feature weights, how do you explain its predictions?
    Not by reading coefficients — there are none in the original space. You fall back on model-agnostic explanation: perturb inputs and observe the score, or attribute a prediction across features using an additive attribution method. You can also inspect which support vectors dominate a given prediction, which tells you which training examples the model considers this point similar to.

Two people can agree on how similar their music tastes are without either of them writing out a full list of every song they have ever heard. The kernel is the agreed similarity score; the lists are the features you never build.

saying these in an interview costs you the question

  • Says the kernel maps the data into a higher-dimensional space and stores it
  • Thinks the trick is a speed optimisation of an otherwise identical explicit computation
  • Claims any similarity function can be used as a kernel
  • Believes the kernel trick reduces overfitting rather than increasing capacity
  • Cannot say what quantity the kernel returns for a pair of points

context

resolving links…