Kernel Principal Components

Thirty-six people, measured by height and weight. Twelve of them are of about one build, all within ten or so units of a hundred and sixty centimetres and sixty kilograms, and the other twenty-four differ from that build by about thirty units, each in a different direction, so on the plane they form a ring around the twelve.

The fact that separates the two groups is how far from the typical build someone is, and no straight line through the cloud carries it. Tick the ordinary PCA box in the playground and the right panel shows the ring turned a little, with the twelve still inside the twenty-four.

The numbers say why. Ordinary PCA gives the ring shares of 0.516 and 0.484, because a round cloud spreads almost evenly in every direction, and along its first axis the inner twelve overlap the outer twenty-four by 40.2 units, since an outer person on the left and an outer person on the right sit at opposite ends of any straight axis with the inner twelve between them.

Untick the box, with the radial kernel and gamma at 0.005, and every inner person sits to one side of every outer person along the first kernel direction, with a clear stretch of 0.634 between the nearest pair. The thirty-six are the same people; the direction was found in a different space, and the next three Parts build it.

The PCA page ended on twelve people along a curve and showed that a straight axis is a poor summary of them, with a first component claiming 68 percent of the variance and a reconstruction error of 3,316 from one number per person. It is worth being exact about what that axis did and did not do, because this page will measure the kernel’s answer against it.

The curve rises at both ends and dips in the middle, and nearly all of its spread runs along height, so the first component runs nearly along height too.

Read the twelve by height and their first coordinates fall from 39.1 to −40.9 without once turning back; the axis orders the people along the curve perfectly well. What it loses is the curve itself, the 301.5 of variance out of 942.9 that runs across the axis, which is why a person rebuilt from one coordinate lands on the line and the two ends of the arc rise off it.

So ordinary PCA orders the arc and loses its shape. Whether the kernel describes it better is a question this page answers by measurement, in section 17, and the answer is less tidy than the textbook picture.

A straight direction gives every person a score that is a weighted sum of their height and weight. A curved direction gives them a score that is some other function of the pair, the distance from the typical build for the ring, the position along the curve for the arc. The kernel trick page’s way to get one is to lift every person into a larger space of made-up features, squares and products and beyond, and choose a straight direction there; a straight direction in the lifted space is a curved one on the plane.

score(x) = w · φ(x)

PCA in the lifted space would then find the straight direction of most spread among the lifted people, which is the curved direction of most spread among the people as measured. The obstacle is the one that page counted. The lifted space of the radial kernel has no finite number of features, so the covariance matrix PCA decomposes cannot be written down at any size, and the method looks closed off before it starts.

Take the PCA page’s measured four, centred, with deviations (10, 10), (−10, −10), (5, −5) and (−5, 5). Their first component was the direction (0.707, 0.707). Here is the observation the whole method rests on. That direction can be written as a weighted sum of the four deviations themselves, since any direction through the middle of a centred cloud lies in the space the deviations span.

u = Σᵢ aᵢ dᵢ
(0.707, 0.707) = 0.0354 · (10, 10) − 0.0354 · (−10, −10) + 0 · (5, −5) + 0 · (−5, 5)

Once a direction is a recipe over the people, a person’s score along it is a sum of dot products between people, and the direction’s own coordinates never appear.

score of person j = dⱼ · u = Σᵢ aᵢ (dⱼ · dᵢ)

coordinate ≈ 0.0354 × 200 + (−0.0354) × (−200) ≈ 14.14

So write down every dot product between people once, in an n by n table with person i down the rows and person j across the columns. That table is the Gram matrix, and after this Part it is the only thing the fit reads. For the measured four, centred, it is two blocks and nothing else, because persons 1 and 2 lie along one diagonal and persons 3 and 4 along the other, and the two diagonals are perpendicular.

K_c =  200  −200     0     0
      −200   200     0     0
         0     0    50   −50
         0     0   −50    50

…

The PCA page decomposed the scatter matrix, which is two by two for two features. Decompose the four by four Gram matrix instead and the non-zero eigenvalues come out the same, 400 and 100, and the eigenvector for 400 is one on person 1, minus one on person 2 and zero elsewhere, which is the recipe of section 4 before its scaling.

The two routes reach the same variances, the same shares and the same coordinates, and the extra eigenvalues the larger matrix has are zero, because four people on a plane spread along two directions and no more.

…

The same holds on the arc, where the scatter matrix is [7054.7, 67.3; 67.3, 3317.7] and its eigenvalues are 7055.88 and 3316.45, the twelve by twelve Gram matrix gives 7055.88 and 3316.45 and then ten eigenvalues no larger than 4e−12, and the twelve people’s coordinates by the two routes agree to 1.35e−13 once each column’s sign is dropped.

…

A raw Gram eigenvalue and a sample variance differ by the sample covariance divisor. There are four people in this example.

sample variance = raw eigenvalue / (n − 1)
                = 400 / (4 − 1)
                ≈ 133.33

This is the variance reported by the ordinary PCA playground. The normalization of component coefficients still uses the raw eigenvalue.

variance along the direction = λ / (n − 1) = 400 / 3 = 133.33

The second scale is the direction’s own length. The eigenvector u has unit length, but the direction it names, X′u, has length √λ, which on the four is 20. A person’s coordinate has to be measured along a unit direction, so the recipe is u divided by the square root of the raw eigenvalue, and that is where section 4’s 0.0354 came from.

a = u / √λ = (1, −1, 0, 0) / √2 / √400 = (0.0354, −0.0354, 0, 0)

…

squared coefficient length ≈ 0.0354² + 0.0354² ≈ 0.0025
reciprocal eigenvalue = 1 / 400 = 0.0025
person 1 coordinate ≈ 200 × 0.0354 + 200 × 0.0354 ≈ 14.14

Everything in Part 2 used deviations from the mean. Build the Gram matrix from the people as measured instead, with person 1 at (180, 78) rather than (10, 10), and every entry is enormous, 38,484 for person 1 with themselves, 33,324 with person 2, because the whole cloud lies far from the origin and every dot product mostly measures that.

The largest eigenvalue of the uncentred table is 134,449.5, and it takes 0.9989 of the table’s trace. Its eigenvector is nearly the same weight on everyone, (−0.53, −0.46, −0.51, −0.49), which is the direction from the origin to the mean and describes no spread among the four at all.

…

The PCA page could show this by drawing the cloud and the origin on one picture, and section 4 there did. Here there is no picture to draw, because the points that need centring are the lifted ones, and the uncentred table’s first direction would be reported as a fit with a share of 0.9989 and nothing to warn anyone. On the arc the same share is 0.9896.

The lifted people cannot be shifted, since they cannot be written down, but their table can be corrected on their behalf. Write m for the mean of the n lifted people and expand the dot product of two centred ones.

(φ(a) − m) · (φ(b) − m)
  = K(a, b) − (1/n) Σₖ K(a, xₖ) − (1/n) Σₖ K(xₖ, b) + (1/n²) Σₖ Σₗ K(xₖ, xₗ)

Each term is a kernel value or an average of kernel values, so the centred entry is computable from the uncentred table alone. Read across every pair at once and the four terms are four matrices, where 1ₙ is the n by n matrix filled with 1/n.

K_c = K − 1ₙK − K1ₙ + 1ₙK1ₙ

A person who was not in the fit gets a row of kernel values against the n training people, and that row has to be shifted by the mean the fit learned rather than by anything of its own, exactly as the PCA page subtracted the training mean from a new observation. The same identity does it, with the query row’s own average and the training table’s averages in the four terms, and it is exact rather than approximate.

Send person 1 of the measured four back through as if new and their centred row comes out 200, −200, 0, 0, the first row of section 5’s table.

centred query row = k − 1_q K − k 1ₙ + 1_q K 1ₙ

Part 2 ended with a fit that reads one table of dot products and nothing else. The kernel trick page’s claim is that a kernel answers what the dot product of two lifted people would have been, without lifting them. Put the two together and the whole method is one substitution. Fill the table with kernel values instead of dot products, centre it by section 9, and decompose it by section 6.

K_ij = k(xᵢ, xⱼ)          linear:  a · b          radial:  exp(−γ ‖a − b‖²)

With the linear kernel the table is the Gram matrix and every number in Part 2 comes back unchanged, which is the control that says the machinery is right. With the radial kernel each entry is a similarity, one for a person with themselves and falling toward zero as two people separate, at a rate gamma sets. Here is the arc’s table under it at a gamma of 0.002, with the people read by height so that the bright band down the diagonal is the curve, one neighbour at a time.

…

The person at (120, 80), the short heavy end of the arc, scores 1 with themselves, 0.460 with their neighbour at (128, 62), 0.088 with the next, 0.002 with the fifth person along, and below 0.001 with everyone past them. The person at (160, 33), the bottom of the dip, scores 0.873 with each of their two neighbours and 0.969 with the twelfth person at (156, 33), who sits four centimetres away. Under this kernel the fit reads who is near whom, and a person’s height and weight enter only through those distances.

The PCA page’s first component was a statement about features, this direction leans on height by 0.71 and on weight by 0.71. Nothing of that kind exists here. The direction lives in the lifted space, whose coordinates have no names and, for the radial kernel, no finite count, so the only description a kernel component has is the recipe of section 4, one coefficient per training person.

On the ring at a gamma of 0.005 the first direction gives every one of the inner twelve a coefficient between 0.100 and 0.130 and every one of the outer twenty-four a coefficient between −0.068 and −0.048.

…

The coefficients describe a direction by the training people that contribute to it. With thirty-six people, convert its raw eigenvalue into a sample variance using a divisor of thirty-five.

sample variance ≈ 4.292 / 35 ≈ 0.123
squared coefficient length ≈ 1 / 4.292 ≈ 0.233

These are two different uses of the eigenvalue. Neither is an ordinary loading on an original input feature.

A person’s coordinate is section 4’s sum with the centred kernel row in place of the dot products. On the ring, person 1 at (169.7, 60.3) has a raw kernel row beginning 1, 0.864, 0.570 against the inner people and ending in values near 0.0003 against the far side of the outer ring, and after centring against the table that row summed against the first direction’s coefficients gives 0.513.

coordinate of x = Σᵢ aᵢ · K_c(x, xᵢ)

Two things are often said about these coefficient vectors, and one of them did not survive being measured. The first is that the directions are ordered by the variance along them, largest first, which is true and is checked at construction. The second is that the coefficient vectors of different components are not perpendicular to one another in the ordinary sense, only in the sense the kernel induces.

I measured it and found otherwise. On the ring the largest dot product between two directions’ coefficients is 2.7e−18, and on the arc it is 2.1e−17, which is zero to rounding, as it has to be, since they are eigenvectors of one symmetric table and were only scaled afterwards.

aᵢ · aⱼ = 0  for i ≠ j          aᵢ′ K_c aⱼ = 1 if i = j, else 0

What they are not is unit length. The scaling of section 7 leaves each with squared length one over its raw eigenvalue, 0.0025 and 0.01 on the measured four, and the thing that does come out as the identity is the coefficient matrix with the centred table in the middle, to 7.8e−16 on the ring. That second identity is the statement that the lifted directions have unit length, which is the fact the scaling was for.

Return to the playground with the ring, the radial kernel and gamma at 0.005. The first two directions have shares of 0.137 and 0.111 of a total lifted variance of 0.898, which is a small fraction against ordinary PCA’s 0.516 and 0.484, and along the first of them the two groups are 0.634 apart where ordinary PCA had them overlapping by 40.2.

Both readings are correct and they are answering different questions. The radial kernel spreads the thirty-six along thirty-five directions with any spread at all, one fewer than the count of people, so no two of them can hold most of it, and the first still happens to be the one the ring is arranged around.

Why that one? Under this kernel the inner twelve all score high with one another, since they are all within about twenty units, while each outer person scores near zero with the far side of the ring and only modestly with their neighbours. In the lifted space the twelve are one tight bunch and the twenty-four are spread thin around it, and the direction from the bunch to the rest is the direction of most spread. The coefficients of section 12 are that direction written out.

Gamma is the radial kernel’s one setting, and the kernel trick page read it as a reach, one over its square root being roughly the distance at which two people stop scoring as alike. Sweep it across the ring and the split holds from a gamma of 0.003, a reach of about eighteen units, to 0.017, a reach of under eight, with the widest gap of 0.645 at 0.004.

At 0.002 the reach is twenty-two units, which is wider than the inner group itself, so an inner person and the nearest outer people score much alike, and the groups overlap by 0.966; at 0.02 the reach is seven units, every person resembles little more than their nearest neighbours, and they overlap again by 0.249.

…

The lines say what the bars cannot. The total lifted variance climbs from 0.292 at the widest reach to 0.998 at the sharpest, because a person who resembles nobody has a whole unit of spread to themselves, and the first share falls from 0.428 to 0.037 over the same sweep as that spread is dealt out one person at a time.

Neither line turns at the edges of the band where the split holds. The ideal case, a tighter eight inside a wider sixteen, holds its split from 0.0015 all the way to 0.1, with a widest gap of 0.981, because its eight are within about four units of one another and its sixteen about thirty-two units out, so there is a wide range of reaches that scores the eight alike and the sixteen unalike.

The textbook picture for a curved pattern is that the kernel unrolls it, so that the first kernel direction reads position along the curve and the curve is gone. I measured it on the arc and that is not what happens. At a gamma of 0.002 the first kernel coordinates of the twelve, read by height, run −0.49, −0.44, −0.07, 0.35, 0.58, 0.61, 0.58, 0.40, 0.05, −0.37, −0.63, −0.57.

Both ends of the arc land on the same side and the middle on the other. The axis turns back five times where ordinary PCA’s turned back not at all.

…

The second direction runs −0.36, −0.63, −0.66, −0.45, −0.15, 0.00, 0.14, 0.40, 0.59, 0.60, 0.40, 0.12, rising along the curve and turning down at each end, and the two together place the twelve on a curve again in the kernel plane. What the first direction found is the largest spread in the lifted space, and on a curve whose two ends are far from everything else, that is the ends against the middle.

Widen the reach and the fold loosens, one reversal at 0.0003 and two at 0.0005, but that is the kernel approaching a rotation, with shares of 0.526 and 0.370 against ordinary PCA’s 0.680 and 0.320. Nothing in this fit straightens the arc. A method that does, one that reads distances along the curve rather than across it, is a different method and is not on this site.

The squared kernel is worth one measurement of its own, because its lifted space contains the very feature the ring is arranged around. The kernel trick page expanded it by hand, and among its made-up columns are height squared and weight squared, whose sum is the squared distance from the origin, close to what separates the two groups. Yet at a gamma of 0.005 the squared kernel’s first two shares are 0.652 and 0.347 and along the first direction the groups overlap by 63.5.

The radius is in the space and the method did not choose it, because the largest spreads in that space are the outer ring’s swing in height squared and in weight squared, which are enormous in raw units, and the direction that separates the groups is the fifth on the list with a share too small to print. The method finds the largest spread, and the largest spread is not always the useful one, which the PCA page said of ordinary components and which the kernel does not repair.

The PCA page rebuilt every person from one coordinate, by scaling the retained direction and adding the mean back, and landed among heights and weights because the direction was made of heights and weights. This fit offers no such step, and the omission is a decision. A kernel coordinate is a position along a direction in the lifted space, so scaling the direction by the coordinate rebuilds a lifted point, and going back means finding the person on the plane whose lift that is.

For the radial kernel there usually is none. The lifted space has no finite number of dimensions and the plane maps onto a thin curved sheet inside it, so a point rebuilt from two coordinates almost never lies on the sheet, and the question has no answer to approximate.

What a fit can say instead is how much of each person’s distance from the lifted mean the kept directions carry, which is the analogue of the PCA page’s stubs. Every person’s squared lifted deviation is the diagonal of the centred table, and the kept part is the sum of their squared coordinates.

kept share of person i = Σⱼ zᵢⱼ² / K_c(xᵢ, xᵢ)

…

On the ring with two directions kept, the fit holds 0.248 of the total, and per person it holds between 0.057 and 0.537, more for the inner twelve than for the outer twenty-four, because the first direction is largely about them. The linear kernel is the one case where a way back would exist, and the fit does not offer one there either, since a method that answers exactly for one kernel and not at all for the rest is worse than one that refuses, and the exact case is the PCA page.

Nothing inside the fit chooses gamma. The total lifted variance and the top shares move monotonically across the whole sweep of section 16 and say nothing about where the ring comes apart, and the fit reports no error to minimise since there is no reconstruction. The usual rule of thumb is to set gamma to one over the median squared distance between pairs of people, and on the ring that median is 1051.5, so the rule gives 0.00095.

I measured it, and at that reach the groups overlap by 0.992; the split needs a gamma at least three times larger. On the ideal case the rule gives 0.00088 and the split begins at 0.0015, so the rule falls short there too, by less.

Ordinary PCA on two features has two directions to keep or drop. Here the ceiling is the number of people, less one for centring, and on the ring the radial kernel at 0.005 finds spread along thirty-five directions. Their cumulative shares climb slowly, five directions to pass half the total, thirteen to pass nine tenths, all thirty-five to reach the whole of it. The PCA page’s rule of thumb, keep enough for 95 percent, would keep sixteen or more, and the ring came apart along the first one alone.

So the cumulative share is the wrong yardstick when the coordinates are for separating groups, and it is the right one when they are for holding as much of each person’s lifted deviation as possible, which the ladder in section 19 shows climbing with the count. The two purposes want different counts from the same fit, as they did on the PCA page, and the count is a choice made by naming the purpose.

The radial kernel measures distance, and the distance here mixes centimetres with kilograms, so a gamma is a number in those mixed units. Write height in metres instead of centimetres and refit the arc at the same gamma of 0.002, and the first share is 0.680 where centimetres gave 0.315. The heights have shrunk to a hundredth, so the distances are almost entirely weight now, and with the first share back at ordinary PCA’s 0.680 the kernel’s answer has the shape of a rotation again.

The kernel trick page’s remedy holds here. Standardise the features first, so a unit of distance means one standard deviation in either, and then choose gamma. This page keeps raw units because the ring and the arc were drawn with their two spreads already comparable, thirty units either way on the ring and eighty against forty-seven on the arc, and the choice is stated rather than hidden.

A complete implementation states the kernel and its parameters in full, that the table is centred by the identity of section 9 and new rows by section 10’s, how many directions are kept and that the ceiling is the row count, that eigenvalues are reported over n − 1 as variances while the eigenvectors are normalised by the square root of the raw eigenvalue, that the total variance is summed before any truncation, the threshold below which an eigenvalue is treated as the zero that centring created rather than divided by, that a negative eigenvalue is clamped rather than refused, the order of the directions, that a sign is the solver’s, that there is no inverse transform, and that the training rows and the training table are part of the fitted state.

Every row below was run through this page’s own endpoints, and the behaviour recorded is what came back rather than what the documentation promises. Where a number appears it was read from the probe.

The sigmoid row and the strangers row deserve the most care, because both are quiet. A negative eigenvalue means the table did not come from any lifted space at all, and the fit discards that spread and reports a share near one as if it had found something; kernel ridge on this site refuses the same table through its solve, and this fit does not.

And a person the kernel scores at zero against everyone is placed at one fixed spot, whoever they are, which is the right arithmetic and a useless answer, and the only sign of it is that every stranger lands there.