The Kernel Trick

Imagine trying to separate two colours of beads on a tabletop with one straight ruler. If the colours occupy opposite ends of the table, we can place the ruler between them. But if one colour surrounds the other, turning or sliding the ruler will leave some beads on the wrong side.

This is the difficulty in our picture. A simple classifier uses a straight boundary to decide which group a point belongs to. It needs one group on one side and the other group on the other side. The original arrangement does not allow that.

So, we need to give the classifier a more useful arrangement to work with. In a model, moving a point means changing the numbers used to represent it. Its label stays the same.

A transformation is a rule for calculating new coordinates from the existing ones. Stretching increases distances along a direction. Compressing decreases them. Rotating turns all the positions by the same angle. These are useful first examples because we can see exactly what changes.

They can change the relative scales or orientation of a pattern. But in our picture, a wider ring, a flatter ring, and a rotated ring all still surround the middle group. None creates the separation we need.

There is a reason for this limit. If a straight divider worked after an ordinary stretch, compression, or rotation, undoing that transformation would turn it back into another straight divider. We could already have used that divider in the original picture.

Now imagine keeping every bead over its original spot on the table, but giving it a height. A bead near the centre stays low. A bead far from the centre rises higher. The new height represents distance from the centre, with larger distances exaggerated by squaring them.

This changes the arrangement in a useful way. The two colours were mixed when viewed only across the tabletop. Once height is available, the blue group sits below the amber group. There is now a vertical gap between them.

We applied the same rule to every point. We did not tell the rule to raise amber points and lower blue ones. It only used position. This matters because we will need to apply it to new observations whose labels we do not know.

With three coordinates, the equivalent of our straight divider is a plane: a flat surface, like a sheet of glass extending in both directions. We can place that sheet above the blue points and below the amber points.

Use Place a plane in the walkthrough. Move the sheet too low, and some blue points end up above it. Move it too high, and amber points end up below it. Between the groups, there is a range of positions that separate this example successfully.

This is what a useful transformation gives us: a representation in which a simple boundary can do the job. We are choosing the sheet's position by hand here. During training, a classifier uses the supplied labels to choose its boundary. Its learning objective determines which separating boundary it prefers, or how to handle mistakes when perfect separation is impossible.

Select Original view. A point near the centre would rise only a little, so it would remain below the sheet. A point far from the centre would rise above it. The points that would reach the sheet exactly form a circle in the original view.

The circle and the plane describe the same decision using different coordinates. The boundary is flat in the representation with height, even though it is circular in the original two-coordinate picture.

In another dataset, another transformation might help: it could change distances differently in different regions or introduce several additional coordinates. There is no promise that every transformation will produce a useful separation. The purpose is to make the relationships we care about easier for the model to use.

We have explained why transformed coordinates can help. But creating and storing those coordinates can become expensive when there are many of them.

Some learning algorithms only need particular comparisons between points in that transformed representation. A kernel supplies those comparisons directly from the original inputs, as though the transformation had been carried out. This is the computational shortcut we call the kernel trick.

Keep the two jobs separate as we continue: the representation makes a useful plane possible; the learning algorithm chooses the plane. The kernel gives a compatible algorithm a way to work with that representation without explicitly building every coordinate.

Next we will put numbers to the height picture. After that, we will work through one comparison both with and without explicitly transformed coordinates.

The original picture gave each point two coordinates. Each coordinate is a feature, a number supplied to the model about an observation. The point's colour represents its label, the answer supplied during training.

In an application, two features could be temperature and heart rate, and the supplied labels could be healthy or unwell. The later clinic playground uses that made-up example. For the calculation here, we will keep simple coordinates so that we can follow the height of each point.

Our original coordinates describe position along two directions. The pattern we want to express is distance from the middle, regardless of direction. That is the extra feature we are going to calculate.

We can change what the model receives. Being far below the usual temperature and being far above it have opposite signs, but both are departures from the middle. Squaring a departure gives us a number that grows in either direction.

Let the two coordinates measure departures from the centre on comparable scales. We will call those coordinates x₁ and x₂. The square of their distance from the centre is called r². This is the height used in the opening picture.

r² = x₁² + x₂²

A threshold is the dividing value we compare against. In the picture, it is the height of the sheet. A threshold on the new feature can put the middle observation in one class and both distant observations in the other. We will place the sheet at a height of one.

Score = 1 − r²

Near the middle:       1 − 0.5 = 0.5
Either distant point:  1 − 4   = −3

Predict the middle class when the score is nonnegative.

The score measures whether the point's height falls below or above our chosen sheet. A positive score puts it below; a negative score puts it above. This is a linear rule in the new feature: multiply it by a weight, then add a bias. We have now written down the flat divider from the picture.

Our horizontal sheet gave us a circle around a chosen centre. We may need more choices, such as an oval that is wider in one direction, or one whose long direction lies diagonally across the plot.

To allow that, we will now use a different transformation. Supply the two squared coordinates separately, together with a feature that multiplies the coordinates. The separate squares let the model treat the two directions differently. The product lets the rule also depend on how the coordinates vary together.

A feature map is the rule that builds this new list of numbers. We write the rule as φ, pronounced phi. Here is the particular map we will use throughout the worked kernel calculation.

φ(x₁, x₂) = (x₁², √2 × x₁ × x₂, x₂²)

The first and third entries measure squared departures along each coordinate. The middle entry describes the two coordinates together. It can be positive or negative. Its factor of √2 sets the scale of that feature; the next part shows why this factor is needed for our kernel identity.

Original observation: x = (1, 2)

First feature:  1² = 1
Second feature: √2 × 1 × 2 = 2√2
Third feature:  2² = 4

Expanded observation: φ(x) = (1, 2√2, 4)

We now have three inputs where we originally had two. We call the coordinates a model works with its feature space. Just as in the height picture, a plane in these transformed coordinates can describe a curved boundary in the original ones. This particular map is useful for our next example because its comparisons have a short, exact kernel formula.

A dot product combines two equal-length lists into one number. Multiply entries in matching positions, then add the products. For the vectors below, there are two matching pairs.

a = (1, 2)
b = (3, 4)

a · b = (1 × 3) + (2 × 4)
      = 3 + 8
      = 11

Why do we care about this operation? Some learning algorithms can express both their training calculations and their predictions using dot products between observations. If we give those algorithms expanded features, they ask for dot products between the expanded vectors.

That creates an opportunity. Perhaps we can calculate the number they need without first constructing both expanded vectors.

Change either vector below. Follow both calculation routes and compare their final values. The feature map stays fixed; only the input observations change.

φ(x₁, x₂) = (x₁², √2 × x₁ × x₂, x₂²)
k(a, b) = (a · b)²

The agreement is an algebraic identity, not a coincidence in our chosen example. Expanding the square shows why the mixed feature needs its factor of √2.

(a · b)² = (a₁b₁ + a₂b₂)²
         = a₁²b₁² + 2a₁a₂b₁b₂ + a₂²b₂²

φ(a) · φ(b) = a₁²b₁² + (√2a₁a₂)(√2b₁b₂) + a₂²b₂²
            = a₁²b₁² + 2a₁a₂b₁b₂ + a₂²b₂²

A kernel value alone does not decide which class an observation belongs to. A model must learn how to combine comparisons with training observations. In one common form, it stores a coefficient for each training observation and an offset for the final score.

1. Reference observations: the training inputs used in the comparisons.
2. Kernel values: the comparisons between a new input and those reference inputs.
3. Learned coefficients: the size and sign of each comparison's contribution.
4. Offset: a constant added to the combined contributions.

score(x) = c₁k(r₁, x) + c₂k(r₂, x) + … + cₙk(rₙ, x) + b

Here rᵢ names the i-th reference observation, cᵢ is its coefficient, and b is the offset. The training algorithm chooses the coefficients using its objective and the labels. Replacing the dot products does not remove the need to train the model.

During fitting, a kernel algorithm commonly compares each training input with every training input. We arrange the answers in a square table called the kernel matrix, or Gram matrix. A row identifies the first input, a column identifies the second, and their cell stores the kernel value.

Kᵢⱼ = k(rᵢ, rⱼ)

For n training observations, K has n rows and n columns.

Labels remain separate from this table. Two observations can receive a large kernel comparison even if their labels disagree. The learning objective determines what to do with that disagreement.

For a new input, compute a new set of comparisons against the stored training inputs, using the same preprocessing and kernel. Then apply the learned coefficients. An algorithm that requires explicit coordinates for other operations cannot automatically use this substitution.

We can now try a fitted classifier. Choose The clinic below, then compare Linear with Squared. Each dot's colour is its supplied label; the background colour is the model's prediction. Look for whether the predicted healthy region surrounds the middle group.

Linear shows one fitted straight boundary. Its accuracy measures this fit, rather than establishing the best accuracy of every possible straight boundary. An Ideal Case loads a different arrangement where a straight boundary can separate the groups.

The display below applies our three-feature map to the clinic after standardizing its measurements. Its three axes are the three expanded features. The green plane is a linear decision boundary fitted using those features.

The API also fits the same classifier using the squared dot-product kernel on the standardized original inputs. The reported gaps compare the two fits. Small rounding differences are expected because the calculations take different routes.

Rotate the plot to inspect how the plane separates the observations. A flat boundary in these expanded coordinates corresponds to a quadratic boundary in the original plot. The model did not need to store the three-feature representation on the kernel route.

Explicit-map comparison: k(a, b) = (a · b)²
Playground Squared:      k(a, b) = (a · b + 1)²

For two inputs and a few derived features, explicitly building the features may be the simplest choice. The shortcut becomes more useful as the expansion grows. With many original inputs, a polynomial map can contain a very large number of powers and products.

A polynomial kernel can obtain the corresponding comparison from the original dot product, an added constant, and a power. It avoids constructing those millions of entries for each observation.

Polynomial kernel: k(a, b) = (a · b + c)ᵈ
Use a nonnegative constant c and a positive integer degree d.

That does not make every kernel model cheap. Storing a full Gram matrix grows with the square of the number of training observations. Predicting also requires comparisons with the reference observations the fitted model retains.

10,000 training observations
Full Gram matrix: 10,000 × 10,000 = 100,000,000 entries
At 8 bytes per entry: 800,000,000 bytes, about 800 MB
This excludes the solver's other arrays.

A support vector classifier is one algorithm that can use this arrangement. Kernel ridge regression learns coefficients for a regression prediction. Kernel PCA uses the comparison matrix to describe variation in the feature space.

Each method still has its own training objective and limitations. Choosing a kernel does not turn those methods into the same algorithm. The shared operation is replacing feature-space inner products with kernel evaluations.

The squared kernel is one comparison rule. Another useful choice asks how far apart two inputs are. The Gaussian radial basis kernel gives identical inputs a value of one, then decreases smoothly as their squared distance grows.

It needs the two inputs, a distance calculation, and a positive setting called gamma. Gamma controls how quickly the kernel value decreases with distance.

Squared distance = Σⱼ (aⱼ − bⱼ)²
Radial kernel: k(a, b) = exp(−γ × squared distance)

Squared distance = 2² = 4

At γ = 0.5: k(a, b) = exp(−0.5 × 4) = exp(−2) ≈ 0.1353
At γ = 2:   k(a, b) = exp(−2 × 4)   = exp(−8) ≈ 0.0003

The graph holds one input fixed and moves the other along a line. Compare how the radial curves decrease away from the reference with how the polynomial and linear comparisons behave. Kernel values need not all lie between zero and one; an ordinary dot product can also be negative.

Small gamma makes comparisons change slowly with distance. Large gamma makes them much more local. In this clinic, overly broad comparisons miss the pattern, while overly local comparisons fit the training observations but predict the second clinic poorly.

The dashed curve below is training accuracy. The green curve measures predictions on another 21 observations excluded from fitting. Compare the curves as gamma increases. The smaller plots show what the corresponding boundaries look like.

…

Once we use the second clinic to choose gamma, it is validation data. Its best score is no longer an untouched test of the whole selection procedure. A final evaluation needs another independent test set or an appropriate nested evaluation.

Feature scales matter here: a difference of one degree and a difference of one heartbeat are not interchangeable. The API fits a standardizer on the training clinic and uses those stored means and scales for subsequent inputs.

The Gaussian kernel is also an inner product in a feature space. For inputs over a continuous Euclidean domain, its exact representation generally needs infinitely many coordinates. We can still calculate the kernel value with a finite distance calculation.

exp(−γ‖a − b‖²) = exp(−γ‖a‖²) exp(−γ‖b‖²) exp(2γ a · b)

exp(2γ a · b) = Σₘ₌₀∞ [(2γ)ᵐ / m!] (a · b)ᵐ

Finite feature approximations are possible, but they introduce approximation error. Direct kernel evaluation avoids truncating that feature expansion. It still leaves the costs of the comparison matrix and the learning algorithm.

A support vector classifier balances two goals: keep a margin around the decision boundary and penalize observations that violate it. The margin describes the gap between two score levels, one on each side of the boundary.

On a separable example, maximizing this gap gives a particular separating boundary. It can encourage useful generalization, but does not guarantee it. The widget uses the fever-only clinic, where a straight separator is possible.

For the standard formulation, let xᵢ be a training observation, yᵢ its class label encoded as negative or positive one, w the feature weights, b a separate unpenalized offset, and ξᵢ a nonnegative margin violation. C controls the cost of violations relative to the weight penalty.

Minimize:  ½‖w‖² + C Σᵢ ξᵢ
Subject to: yᵢ(w · φ(xᵢ) + b) ≥ 1 − ξᵢ
            ξᵢ ≥ 0

Distance between the score levels −1 and +1 = 2 / ‖w‖

A larger C gives violations more influence in this objective. A violation can be an observation on the correct side but inside the margin, as well as a misclassification. C and gamma control different things: the fitting tradeoff and the kernel's distance scale.

Introduce one nonnegative multiplier αᵢ for each margin constraint. Eliminating the feature weights gives an equivalent optimization problem in these multipliers, called the dual.

Substituting the same expression for w into the prediction score gives the coefficient form used earlier. Each coefficient is a multiplier combined with its training label.

score(x) = Σᵢ αᵢyᵢ k(xᵢ, x) + b
cᵢ = αᵢyᵢ

Training observations with nonzero multipliers are the support vectors. Observations with zero multipliers contribute nothing to this sum. The number retained depends on the data, settings, and fitted solution; it can include every training observation.

…

The refitting experiment compares the full clinic with reduced versions. Its reported gap measures the change in decision values. Numerical optimization can leave small differences even when the retained observations support the same boundary.

Stanford's CS229 notes on support vector machines develop the standard margin and dual derivation in more detail.

The SDK makes a different choice from the standard formulation above. It appends an always-one feature implicitly by adding one to the selected kernel. The offset becomes the weight on that constant feature and is penalized along with the other weights.

k̃(a, b) = k(a, b) + 1
         = (φ(a), 1) · (φ(b), 1)

SDK score(x) = Σᵢ αᵢyᵢ [k(xᵢ, x) + 1]

This removes the equality constraint needed for a separate free offset. The implementation uses projected gradient ascent with box constraints. It is a model with a penalized offset, so it need not match the usual SVM with an unpenalized offset.

This extra one is outside the chosen kernel. In particular, it is separate from the constant inside the playground's Squared kernel.

Selected Squared kernel: (a · b + 1)²
SDK classifier uses:     (a · b + 1)² + 1

…

The four-reading example shows the boundary changing with C. The unpenalized hard-margin midpoint would lie halfway between the middle two readings. Penalizing the offset can shift the result, especially when the penalty dominates.

The score's sign selects a class. Multiplying the score by a known label gives the functional margin: positive when correctly classified and negative when misclassified. The score is not automatically a geometric distance or a calibrated probability. For a nonzero feature-weight vector, signed distance requires dividing by its norm.

Functional margin of a labeled example = y × score(x)
Geometric signed distance = (w · φ(x) + b) / ‖w‖

The SDK also exposes a sigmoid of the decision score. That places the value between zero and one, but does not fit a probability model. If probabilities are needed, calibration must be learned and evaluated separately.

A real-valued kernel must be symmetric and produce a positive-semidefinite Gram matrix on every finite set of inputs. Positive semidefinite means that a certain quadratic combination of its entries can never be negative. Equivalently, its eigenvalues are nonnegative in exact arithmetic.

k(a, b) = k(b, a)
For every finite input set and every real vector v: vᵀKv ≥ 0

This is a condition on the function across possible input sets. Passing one numerical check does not prove that a function is valid everywhere. Finding a substantially negative eigenvalue gives a counterexample.

The table below shows one kernel value per pair of clinic observations. The first ten rows and columns are the healthy group. Inspect Linear and Radial first, then compare the Sigmoid option with its negative eigenvalues.

A negative matrix entry is allowed: ordinary dot products can be negative. A negative eigenvalue is a different issue. It means this table cannot be an inner-product Gram matrix. Small negatives near numerical precision need a tolerance-aware interpretation.

The ridge check here attempts Cholesky factorization after adding a small diagonal penalty. It rejects this particular indefinite example. That is not a proof that every accepted kernel function is valid: regularization can make some indefinite matrices positive definite.

The classifier can return a result on an indefinite table, but the usual concavity guarantee for its dual is lost. A reported prediction score alone does not establish that the intended optimization problem was solved.

The Stanford kernel notes connect these matrix conditions with the feature-space interpretation.

• Check that the algorithm can use pairwise inner products for the operations being replaced.
• Fit preprocessing on training data and apply the same transformation to later inputs.
• Choose kernel settings with validation data, then keep the final test separate.
• Inspect convergence as well as accuracy. Reaching an iteration limit can leave a fit unfinished.
• Budget for stored reference inputs, kernel comparisons, and any full Gram matrix.