Some data is hopelessly non-linear in its own coordinates — concentric rings, XOR — and no straight line will ever split it. The textbook fix is to map each point into a higher-dimensional feature space φ(x) where the classes separate with a flat boundary. But φ can be enormous, even infinite-dimensional, so building it explicitly is impossible. The kernel trick is the sleight of hand that sidesteps that entirely, and once you see it the magic evaporates. I built a from-scratch kernel perceptron — real Gram matrix, real decision boundary computed live in JS — to show exactly why. Here it is.
Algorithms only ever touch data through dot products
This is the whole insight. A large family of linear algorithms — the perceptron, SVM, PCA — never look at raw coordinates; they only ever compute xᵢ · xⱼ. So replace every dot product with a kernel K(x,y) = φ(x)·φ(y) that you can evaluate directly, and you get the exact same answer as if you had lifted to φ, for the price of one cheap function call. You never form φ.
def k_linear(x, y): # phi = (1, x1, x2, ...)
return 1.0 + x @ y
def k_poly(x, y, d=2): # phi = all monomials up to degree d
return (1.0 + x @ y) ** d
def k_rbf(x, y, gamma=4.0): # phi lives in an INFINITE-dim space
diff = x - y
return np.exp(-gamma * (diff @ diff))
Prove it — don't believe it
For 2-D inputs the degree-2 polynomial kernel corresponds to an explicit 6-D feature map φ(x) = (1, √2·x₁, √2·x₂, x₁², √2·x₁x₂, x₂²). Build φ by hand, take the honest dot product, and it matches the one-line kernel to machine precision — while in real life you skip the left-hand side entirely.
def phi_poly2(x):
x1, x2 = x; r2 = np.sqrt(2.0)
return np.array([1.0, r2*x1, r2*x2, x1*x1, r2*x1*x2, x2*x2])
explicit = phi_poly2(x) @ phi_poly2(y) # dot product in 6-D feature space
kernel = (1.0 + x @ y) ** 2 # the trick: never build phi
assert abs(explicit - kernel) < 1e-12 # identical
The RBF (Gaussian) kernel is the punchline: its feature map is infinite-dimensional — you literally cannot write down φ — yet K(x,y) is still one exp of a squared distance. Infinite features, one function call.
Which functions are legal kernels? Mercer's condition
Not every similarity function is a kernel. Collect K over every pair of points into the n×n Gram matrix Kᵢⱼ = K(xᵢ, xⱼ). K is a valid kernel — it equals φ(x)·φ(y) for some feature map — if and only if that matrix is symmetric and positive semi-definite (all eigenvalues ≥ 0) for any points. That is exactly the condition for it to be an inner product in some space.
In the demo I compute the eigenvalues from scratch with a cyclic Jacobi rotation solver over nine fixed points. The linear, polynomial and RBF kernels all pass. A tempting-looking "distance kernel" ‖x−y‖ produces a negative eigenvalue and fails — so no feature space can ever realise it, no matter how much it feels like a similarity.
The kernel perceptron draws the curve
The perceptron in dual form is the payoff. Keep one coefficient αᵢ per training point, predict with f(x) = Σᵢ αᵢ K(xᵢ, x), and on a mistake nudge α for that point by its label. There is no weight vector at all — the model touches the data only through the kernel.
def train_kernel_perceptron(X, y, kernel, epochs=60):
n = len(X); G = gram(X, kernel); alpha = np.zeros(n)
for _ in range(epochs):
errors = 0
for t in range(n):
score = np.dot(alpha, G[:, t]) # f(x_t) = sum_i alpha_i K(x_i, x_t)
if np.sign(score) != y[t]:
alpha[t] += y[t]; errors += 1 # dual update, no weight vector
if errors == 0: break
return alpha
Swap the kernel and the same loop learns a curved boundary. On concentric rings the linear kernel is stuck around 55% — a straight line can't split classes that wrap around each other. Flip to the polynomial (1+x·y)² or the RBF and accuracy jumps to 100%: the boundary is linear in feature space but bends into a circle back in the input plane. The demo makes this literal — a side panel re-plots each point at (x₁², x₂²), where a plain linear separator u+v=c is exactly the circle x₁²+x₂²=c in the original coordinates. Separation for free.
The points with αᵢ ≠ 0 are the support vectors, and this same trick powers the SVM, kernel PCA, and Gaussian processes.
Drag the kernel knobs and watch the boundary curve live:
https://dev48v.infy.uk/ml/day42-kernel-trick.html
Top comments (0)