Kernels, part 1 of 10

What is a kernel?

The anatomy of inner products

That is the Euclidean inner product, or dot product, as many of you know it — defined for any pair of n-dimensional vectors x and y.

It is three symbols and a subscript, and it hides everything interesting. So we will do what the frontier-seminar spreadsheets do: set n = 5, write both vectors out as a grid, and compute every term by hand.

Running example

Two five-dimensional vectors. Every cell below is editable — change a number and the product row and the result recompute.

Five numbers in, five numbers in, one number out. The green cells are the five terms of the sum; the rust cell is the whole inner product. Widen the grid to 5,000 columns and the rust cell is still one number.

The calculation, written out

What the one number is telling you

Press Set y = x above. The result jumps, and it jumps for a reason you can read straight off the grid: every term became a square, and squares cannot cancel. Agreement piles up.

Now press Set y = −x. Same magnitudes, same positions, and the result is the same number with a minus sign. Every term is now a negative square. Disagreement piles up just as reliably, in the other direction.

Then press Make them orthogonal. The terms are not zero — look at the green row, several of them are large — but they cancel against each other and the rust cell lands on zero. Two vectors can have plenty of structure in common position by position and still return nothing.

So the inner product answers one question: how much do these two vectors agree? It answers in a single scalar, positive for alignment, negative for opposition, zero for indifference. That is the entire behaviour we care about.

The Euclidean product is only an example

You are also probably closely familiar with the formula at the top of this page. But that formula is not the inner product — it is merely an example. The most ubiquitous one, I admit, but still, the Euclidean product is just one of many.

In general, given a real vector space V, an inner product is a two-variable function taking a pair of vectors to a single real number, subject to the three properties above. Nothing in that definition mentions coordinates, sums, or multiplication. Any function that satisfies the three rules earns the name.

This is the pivot the whole article turns on. The definition is a behavioural spec, not a formula. That leaves room for other functions — ones that measure similarity in ways Σ x_i y_i cannot — to still be inner products in good standing. A kernel, when we finally name it, will be exactly such a function.

Rule 1 — linearity

The rule says two different orders of operation land on the same number. Rather than assert that, we run both orders side by side and show every intermediate row. Set the scalars and the third vector here — every panel below recomputes, as does the grid at the top of the page.

Route A — mix the vectors first, then take one inner product

Read it top to bottom. Scale x by a, scale y by b, add those two rows to get the mixed vector w. Only then does z enter, and only one inner product is taken.

Route B — take two inner products first, then mix the scalars

Here z enters immediately, twice, against the original vectors. Two inner products come out, and a and b are applied at the very end — to two numbers, not to vectors.

The two routes share no intermediate value. Route A's mixed row never appears in Route B; Route B's pair of inner products never appears in Route A. They agree anyway, for every a, b, and every vector you type. That is what linearity buys — permission to push an inner product through a weighted sum, which is why derivations involving inner products are free to rearrange themselves.

Rule 2 — symmetry

Compute both directions column by column and the reason sits in the cells themselves.

The two product rows are identical position by position, not merely equal in total, because each cell is a product of two real numbers and real multiplication commutes. Symmetry here is inherited from arithmetic — but it is still an assumption in the definition, and other similarity functions have to earn it.

Rule 3 — positive definiteness

Pair x with itself and every term becomes a square.

Press Flip x negative: every cell of x drops below zero and the squares do not care — the total is unchanged. Press Empty x and the total reaches zero, which is the only way it can get there. That is the ⇔ in the equation — a zero result forces a zero vector, so the inner product can tell "nothing there" apart from "something there that cancels."

A footnote worth carrying forward: because of symmetry, an inner product is also linear in its second variable. Rule 1 is stated for the left slot only, and rule 2 hands you the right slot for free.

A second example: weights on the coordinates

Two dimensions, and the second coordinate counts double. This is a proper inner product — it satisfies all three rules — and it is emphatically not the Euclidean one. Checking linearity, symmetry and positive definiteness by hand here is worth doing; it is not that hard.

The grid below computes it alongside the Euclidean product on the same two vectors, so the disagreement is visible in a single column. The weight is editable: the definition asks for 2, but try other values and watch which of the three rules survives.

Set the weight to 0 and positive definiteness dies: the vector (0, 1) is not zero, yet it now agrees with itself by nothing, so the function can no longer distinguish "empty" from "invisible to the weights." Set it negative and things get worse — ⟨x, x⟩ can be driven below zero. Every strictly positive weight, however, gives a perfectly good inner product. There are infinitely many of these, and the Euclidean one is just the case where all the weights happen to be 1.

A bundle of examples: any symmetric positive definite matrix

Back in ℝⁿ, with n-dimensional vectors. If K is a symmetric, positive definite n × n matrix, then the formula above is an inner product. Not one example — a bundle of them, one for every admissible K.

We drop to n = 3 so all nine entries of K fit on screen at once. Edit the upper triangle; the lower triangle mirrors automatically, because K has to stay symmetric.

The matrix K — upper triangle editable, lower triangle mirrored

Step 1 — K v, one row of K against v at a time

Step 2 — u against the result

Press K = I and the whole apparatus collapses back to the Euclidean product from the top of the page — the identity matrix weights every coordinate by one and mixes nothing. Press K = diag(1, 2, 1) and you get the weighted product from the previous section, extended to three dimensions. Both are members of this bundle. What the general K adds is the off-diagonal entries, which let coordinate 1 and coordinate 2 contribute jointly rather than separately.

That last point is the one to hold on to. Press Break definiteness: K stays symmetric, the formula still returns a number, and yet ⟨u, u⟩_K goes negative for some vectors, so it is no longer an inner product. The two conditions on K are not decoration. They are precisely what earns the formula the name.

If K is the identity matrix, ⟨·,·⟩_K is the good old Euclidean product.

And in case you are wondering: it is not a coincidence that for matrices, symmetry and positive definiteness are defined the way they are. But let us not get ahead of ourselves.

What does all of this have to do with kernels?

Taking inner products apart.

Back to our good old friend, the n-dimensional real vector space ℝⁿ, and select a basis e₁, e₂, …, e_n. Every vector is then a weighted sum of basis vectors, and the weights are what we have been calling its coordinates all along.

That sentence is easy to nod at and easy to skip past. So here it is as arithmetic, with n = 5 and the standard basis: five rows that are almost entirely zeros, scaled and stacked until they reproduce x exactly.

Step 1 — the basis vectors themselves

Each e_i carries a single one and nothing else. They hold no information about x; they are just the directions we agreed to measure along.

Step 2 — scale each basis vector by the matching coordinate, then add the rows

Only one cell in each scaled row is non-zero, so the column sums cannot interfere with one another. Add the five rows and x comes back unchanged. The decomposition is exact, not an approximation.

The coordinates are themselves inner products

This is the observation the rest of the article is built on. To find the coordinate x_i, you do not look it up. You take an inner product against e_i, and the zeros in e_i discard every other term.

The measured row is identical to x, which is the whole content of the claim. A vector's coordinates are what the inner product reports when you interrogate it one direction at a time.

Why it works: the basis is orthonormal

Take the inner product of every basis vector with every other and lay the results out as a grid.

Ones down the diagonal, zeros everywhere else — each direction agrees fully with itself and not at all with any other. That is the property doing the work above: the off-diagonal zeros are what let ⟨x, e_i⟩ isolate a single coordinate.

Keep this grid in mind, because it is the first one we will break. Fill those off-diagonal cells with something other than zero — let the directions overlap — and you get the matrix K from the previous section back again, which is the same thing as measuring similarity differently. A kernel, it will turn out, is nothing more than a grid like this one computed with a different rule.

The basis inner products determine everything

Every vector is a linear combination of the e_i. And because an inner product is linear in both variables — rule 1 for the left slot, rule 1 plus rule 2 for the right — the two sums can be pulled straight out through the brackets. What is left behind is a double sum over pairs, in which the only thing the inner product still has to know is ⟨e_i, e_j⟩.

So the inner products of the basis vectors determine the whole thing completely. Check it out.

The coefficient grid — every product x_i y_j, all 25 pairs

Row i, column j holds x_i y_j. Nothing about the basis has entered yet — this grid is pure coefficient bookkeeping, and every one of its 25 cells is non-zero.

The basis grid — ⟨e_i, e_j⟩

The terms — x_i y_j ⟨e_i, e_j⟩, with each row summed

Multiply the two grids cell by cell, add everything up, and the result is the inner product — the same number the single-row grid at the top of this page produced. The double sum is not a different calculation; it is the same calculation with its internals exposed.

What the second button does

Press Overlapping basis. The coefficient grid does not move — x and y are untouched. The basis grid fills in: the directions now overlap, so ⟨e₁, e₂⟩ is no longer zero. Terms that were dead come alive, and the total changes.

Nothing illegal happened. The new grid is still symmetric and still positive definite, so all three rules survive and this is still an inner product — a different one, with a different notion of which vectors count as similar. This is the same object as the matrix K from earlier, arrived at from the other direction: K_ij = ⟨e_i, e_j⟩.

And now the promised payoff comes into view. To specify an inner product, you never needed the basis vectors themselves — only the grid of pairwise numbers. Supply a valid grid and you have supplied an inner product. That grid, computed by some rule that takes two objects and returns their similarity, is what a kernel is.

The kernel, as in the seed

Arrange those numbers into a matrix and you have what is called the inner product's kernel — as in the seed, the kernel of a nut, the thing at the centre from which the rest grows. Not a coincidence of terminology. Everything the inner product does is contained in this grid, and the vectors x and y are just the weights you press against it.

We have already been staring at this matrix for two sections. Here it is under its own name, with the numbers filled in, still switchable between the two bases.

K — the kernel matrix of this inner product

Pressing x and y against it — x^T K y in two steps

Three routes, one number. The single-row grid at the top of the page, the double sum over 25 pairs, and x^TKy all agree, because they are the same arithmetic written at three levels of magnification. That is worth pausing on: the matrix form is not a new definition of the inner product. It is the inner product with its seed made explicit.

Read it in the other direction and the door opens. Hand me a square grid of numbers that is symmetric and positive definite, and I can hand you back an inner product — without ever telling you what the basis vectors were, or whether there were any. The grid is sufficient. The vectors are optional.

Rewriting it as matrix multiplication

The kernel representation lets us do all kinds of useful things. The first is simply this: the inner product becomes a chain of matrix multiplications. A row vector, a square matrix, a column vector — the shapes line up, and what drops out the far end is a 1 × 1 object, which is a scalar wearing a matrix costume.

Written this way, a fact that was invisible in the summation notation becomes obvious: matrix multiplication is associative, so you may bracket the chain either way.

Bracketing left — (x^TK) y

First x sweeps across every column of K, producing a row vector of five numbers. Only then does y arrive, and it collapses that row to a scalar.

Bracketing right — x^T (K y)

Here K acts on y first, producing a column of five numbers, and x collapses that.

The two intermediate vectors are different objects — compare the middle rows of the two panels — and the final scalar is identical. This is associativity, and it is not a curiosity. Choosing where to put the brackets is how you control the cost of a computation, and in the attention machinery that closes this series, moving one pair of parentheses is the entire difference between quadratic and linear time.

Something else is now visible. The vectors x and y never touch each other in either route. They only ever touch K. Everything those two vectors know about their mutual similarity is routed through the kernel matrix, which is exactly the sense in which the kernel is the seed of the whole operation.

Reversing the arrow

Think about what we now have on each side. The inner product is a bivariate function: feed it any two vectors out of an uncountable continuum and it returns a number. The kernel is a matrix. A finite set of values. A discrete object. n × n numbers, and that is the whole of it.

But hold on. We have seen x^TKy before. Can we reverse our thinking? Instead of obtaining the kernel from the inner product, what if we define the inner product in terms of the kernel? For any matrix K, we can define the bivariate function above — and ask afterwards whether it deserves the name.

Twenty-five numbers, unlimited questions

The sampler below asks the function about pairs of vectors it has never seen. Nothing is stored between samples except the matrix.

Keep pressing. The tally on the left climbs without limit; the number on the right never moves. Every answer the function will ever give is already present in those 25 cells — the sampler is not consulting a lookup table of vector pairs, because no such table exists. It is pressing new vectors against an old seed.

Which matrices are allowed?

Defining a function is free; earning the name is not. Rule 1 holds for any K whatsoever, because matrix multiplication distributes over addition. The other two rules are exactly the two conditions on the matrix, which is the answer to the question we deferred earlier — it is no coincidence that symmetry and positive definiteness are defined for matrices the way they are. They are named after the properties they buy.

Roll the dice a few times. The random matrices are symmetric by construction, so rule 2 always survives; positive definiteness is the fragile one, and roughly a third of rolls clear it. When a roll fails, the function is still perfectly well defined — it still returns a number for every pair of vectors — it simply is not an inner product. Note that the panels further up the page recompute against whichever matrix is selected here.

So the arrow now runs the other way. We began with an inner product and extracted its seed. We can instead start from the seed. Choose a valid grid of numbers, and an inner product comes into existence, complete with all three rules, with nobody ever having named a basis or a vector space.

Which raises the question the rest of this series answers. If the grid is all that matters, why should its entries have to come from vectors at all? Why not compute K_ij from a pair of sentences, or molecules, or photographs, using any rule that yields a symmetric positive definite grid? Nothing above forbids it.

Two sides of the same coin

Depending on the properties of K, the function we just defined is an inner product — and the condition is exactly the one the panel above tests. If K is symmetric and positive definite, then ⟨·,·⟩_K is an inner product.

So kernels and inner products are two sides of the same coin. Mathematically speaking, the set of inner products and the set of symmetric positive definite matrices are in one-to-one correspondence with each other. Every inner product has exactly one kernel; every admissible kernel defines exactly one inner product. Nothing is lost travelling in either direction, which is why we are allowed to stop thinking about one and start thinking about the other.

But again, we are here to do machine learning. Why is this kernel thing useful for us?

Kernels in machine learning

A dream scenario in data science: linearly separable datasets.

Here is the situation every practitioner hopes for. Two classes, and a straight line that puts all of one on one side and all of the other on the other. Nothing clever required.

Look closely at what the classifier actually computes, though. It takes an inner product. The vector w is a direction, and ⟨w, x⟩ asks how much each data point agrees with that direction. The entire decision rule is one similarity measurement and a threshold.

Drag either slider. The line is not drawn directly — it is the set of points where the inner product with w exactly cancels b. Rotating w swings the boundary; changing b slides it. When every point lands on the correct side, the dataset is linearly separable under that w.

Three points, classified by hand

Two multiplications, one addition, one sign. That is the whole classifier. The ringed points in the plot are these three — one from each class, plus the point sitting closest to the boundary, which is the first to change its mind as you move the sliders.

Hold on to the shape of this computation, because the next section breaks it. Everything here rests on the data being separable by a straight line in the space it already lives in. When it is not — and it usually is not — the inner product at the heart of f is precisely the piece we will replace.

Whatever falls on one side of the boundary is predicted yellow, whatever falls on the other is predicted blue. All we want is a linearly separable dataset in Euclidean space, so that a decision can be as simple as reading the sign of w^Tx — the good old Euclidean product of the data sample and the weight vector.

I have some news. The bad one is that this is almost never possible for real datasets. The good one is that the entire field of machine learning is about finding — excuse me, learning — feature transformations that make the data linearly separable.

Let me show you a simple example.

Lifting the data instead of bending the boundary

Ten points on a line. The yellow ones sit in the middle, the blue ones at both ends. In one dimension a linear boundary is a single threshold — one point on the line, everything below it one class, everything above it the other. Try to find one.

Original — one dimension, one threshold to place

Slide it anywhere. The best any threshold manages is seven out of ten, because yellow is surrounded — a single cut cannot isolate a middle. No amount of learning helps here, since the failure is in the shape of the space, not in the choice of parameters.

Transformed — each point lifted to (x, x² − 1)

The horizontal axis is unchanged — the points have not moved sideways. The new second coordinate lifts the ends of the line and drops the middle below zero, and the data falls onto a parabola. Now a straight line does separate them, and there is a whole interval of heights that work.

The transformation, computed by hand

One column per point. The third row is the new coordinate, and its sign already is the classification — which is the entire trick. We did not find a cleverer boundary. We gave the data a coordinate in which the obvious boundary works.

Notice what ϕ costs. It invented a coordinate that was not in the data, and the classifier now operates in ℝ² rather than ℝ. For this example that is free. For the transformations that make real data separable, the target space can be enormous — hundreds of dimensions, or infinitely many — and writing down ϕ(x) becomes impossible long before the classifier ever gets to use it.

Which is where everything we built earlier comes back. The classifier never needed ϕ(x) itself. It only ever needed inner products ⟨ϕ(x), ϕ(y)⟩ — a grid of pairwise numbers. And a rule that produces such a grid without constructing ϕ is precisely a kernel.

The model in the lifted space is as simple as it gets

The extremely simple linear model w^Tϕ(x) with w = (0, 1) works perfectly on our toy dataset. There is nothing to tune. The weight vector picks out the second coordinate and discards the first, and the sign of what remains is the answer.

The w₁ϕ₁ row is entirely zeros — that is the model declining to look at the original coordinate. All the work is done by the coordinate ϕ invented, and the classifier itself stays a plain inner product with a threshold.

Inner products in the transformed space

In the general case, let ϕ : ℝⁿ → ℝ^m be a data transformation that supposedly straightens out the dataset and makes it linearly separable. How can we calculate the inner product of two transformed data points? Simple. The transformed space is an ordinary Euclidean space, so we use the Euclidean product there.

Pick any two points from the toy dataset and watch it happen.

Two coordinates in, one number out — the same collapse as the very first grid on this page, only now the coordinates are manufactured rather than measured. Choosing two points from the same end of the line gives a large positive number; choosing one from each end gives something quite different.

Every pair at once — the kernel matrix of the toy dataset

One hundred cells, symmetric about the diagonal, each one an inner product of two transformed points. This is the same kind of object as the basis grid from earlier in the article, and it carries everything a classifier needs to know about this dataset. The points themselves are no longer required.

Which sets up the question the next part answers. Computing this grid the honest way means building ϕ(x) for every point and taking m-dimensional dot products — fine when m = 2, hopeless when m is in the thousands, impossible when it is infinite. But the grid is just a hundred numbers. If some formula could produce those numbers directly from the original x values, without ever constructing ϕ, the size of the target space would stop mattering.

What a kernel function means in machine learning

This is what a kernel function means in machine learning, and it is slightly different from what a kernel is in mathematics, though the two are closely related. The mathematical kernel was a finished matrix of basis inner products. The machine learning kernel is a rule — give it two data points and it returns their similarity in some transformed space. Evaluate that rule on every pair in your dataset and you get back a matrix, at which point the two notions coincide.

Why is this beneficial? Because sometimes we can rewrite models entirely in terms of k(x, y), which makes the problem easier to handle. When a model only ever touches the data through inner products, we can swap in a kernel and never handle feature maps explicitly at all.

The radial basis function kernel

The RBF kernel encodes an infinite-dimensional feature mapping which we would otherwise be unable to handle. Note what the formula asks for: a distance, a division, an exponential. No feature vectors are constructed, and none could be — the space they would live in has no finite coordinate list.

Here it is evaluated on two points from the toy dataset, one step at a time.

Every pair — the RBF kernel matrix

Ones on the diagonal, because every point is at zero distance from itself, and a smooth decay away from it. Shrink σ and the matrix approaches the identity: every point becomes similar only to itself. Grow it and every cell approaches one: everything resembles everything. The width is the only thing there is to choose.

Where the infinite dimensions hide

Expand the exponential and the feature map falls out. Each term in the series is a product of something depending only on x and something depending only on y, which is exactly the shape of a coordinate in an inner product. The series never terminates, so the feature vector has no last entry.

The partial sums climb towards the value the closed form produced in one line. Truncating at eight terms is already close; no truncation is ever exact. This is the trade the kernel makes on our behalf — it returns the limit of an infinite computation at the cost of one exponential.

So: is a linear operation on the input a kernel?

We can finally answer the question we started with. To the best of my understanding: yes. Linear operations are feature maps, so they determine a kernel. If A is the matrix encoding the linear transformation, then its corresponding machine learning kernel is k(x, y) = x^TA^TAy.

Worth working through in full, because it closes the loop on everything above — the feature map route and the kernel route meet at the same number, and the matrix in the middle is the K we have been carrying since the beginning.

Below, A maps three dimensions down to two. It is editable, as are the two input vectors u and v from earlier in the page.

The feature map A — 2 × 3

Route A — build the features, then take their inner product

Each input is pushed through A into the two-dimensional feature space, and the Euclidean product is taken there. This is the honest route: the feature vectors genuinely exist and you can read them off.

Route B — build the kernel matrix K = A^TA, then never mention features again

Same number, two routes. Route A lives in feature space and its intermediate vectors have two entries. Route B never leaves the original three-dimensional space and its intermediate vector has three. Neither knows the other exists.

One caveat worth stating

The quantity x^TA^TAx is the squared length of Ax, so it can never be negative. That gives positive semi-definiteness for free, whatever A is. But strict positive definiteness — the condition we needed for a genuine inner product — requires that Ax = 0 only when x = 0, and a matrix that maps three dimensions into two must flatten some direction to nothing.

Press the buttons above and watch this panel. With the default 2 × 3 matrix there is a whole direction that A annihilates, so some non-zero vector has ⟨x, x⟩_K = 0 and rule 3 fails by a hair. Make A square and invertible and definiteness is restored. This is the usual situation in machine learning, where kernels are required to be positive semi-definite rather than definite — the weaker condition is enough for the algorithms, and it is what dimension-reducing feature maps can actually deliver.

Where this leaves us

We started with a formula most readers already knew and took it apart. The inner product turned out to be a behavioural spec rather than a formula; its behaviour turned out to be captured entirely by a grid of pairwise numbers; the grid turned out not to need any vectors behind it; and a rule that produces such a grid directly turned out to be what machine learning calls a kernel.

Every classifier on this page did the same thing at bottom: measure similarity, then threshold it. What changed from section to section was only which similarity was being measured — and that choice, it turns out, is a choice of grid.

What it cannot do

Agreement measured this way is strictly linear. The inner product can only reward matching coordinates as they are given to it. If the thing that makes two points similar is a product of their coordinates rather than a coordinate itself — if similarity lives in x₁x₂ and not in x₁ or x₂ — then no amount of editing the grid above will surface it. The grid has five columns, and the pattern is not in any of them.

The next section takes that failure seriously, with four points in two dimensions that no straight line can separate. The fix will look like cheating: we add columns that were never in the data. And the section after that shows you can get the answer without ever adding them — which is the moment the word kernel becomes necessary.