Hebbian Principal Components

Everything on the PCA page came out of a matrix. The covariance matrix was built from every person at once and an eigensolver was asked for the directions it only stretches, a calculation in which the whole crowd is consulted before any answer appears. This page reaches the same directions by a route that never sees two people together. A single unit holds one weight for height and one for weight, reads a person, and fires by the dot product of the two.

y = w · x = w_height × (height − mean height) + w_weight × (weight − mean weight)

We measure the person relative to the average person, so the unit responds to variation around the mean. The measured four have a mean of (170, 68). Start with the person at (180, 78) and a unit whose weight vector points along height alone.

Centered input = (180 − 170, 78 − 68) = (10, 10)
Weight vector = (1, 0)
Output = (1 × 10) + (0 × 10) = 10

The output is one number, and it is exactly the score the PCA page computed along a direction, except that here the direction is not chosen by anyone. It is whatever the weights happen to be.

Hebb’s rule says that when the input and the output are active at the same moment, the connection between them should grow, and grow by more when both are more active. Written for the two weights it is one line. Each weight moves by a rate times the output times its own input, which is the outer product of the two ends of the connection and involves nothing else. There is no target in it and no loss, and nothing is carried back to the weight from anywhere else in a network.

w ← w + rate · y · x

response y = 1 × (−5) + 0 × 5 = −5
update = 0.0025 × (−5) × (−5, 5) = (0.0625, −0.0625)
new weights = (1, 0) + (0.0625, −0.0625)
            = (1.0625, −0.0625)

Two things in that step deserve a look. The update lies along the person, scaled by how hard the unit fired, so a person the unit already agrees with pushes it further the way it already leans. And the weights got longer. They will get longer on every person, and section 4 measures how much.

The rule multiplies by the row, so whatever the row is measured from is what the unit is pulled toward. Handed raw heights near 170 and raw weights near 68, every person is a long vector pointing from the origin to roughly the same place, and the weights turn to match that place rather than the shape of the cloud around it. The PCA page centred for the same reason, and the fit here centres itself, storing the two means so a new person can be read the same way later.

x = (height − 170, weight − 68)        on the measured four

Section 25 runs the rule on the raw positions to show what it learns instead, which on the measured four is a direction a twelfth of a degree from the line to the mean and twenty-three degrees from the answer. For everything between here and there the rows are deviations.

Let the plain rule run and watch the length of the weight vector rather than its direction. On the measured four, presented in the seeded order at the rate from section 12, one epoch takes the length from 1 to 1.064, then 1.326, then 1.779, then 1.825, and every step lengthened it. Hold the rate constant and the length after each of twenty epochs runs 1.83, 3.75, 8.18, 18.2, 40.8, 91.8, 206, 464, 1045, 2351 and on to 7.8 million by the twentieth.

Let the rate fall a hundredfold across the twenty epochs as the fit does and the growth slows to 42.0, though it never once reverses.

…

The length is on a logarithmic axis because the plain rule’s and the corrected rule’s have to be on one picture. The direction the plain rule takes is worth knowing too, because it is the right one. At the constant rate the weights after twenty epochs point 0.0006 degrees from the eigen direction while being seven million long. The rule finds the direction and then runs along it forever, which is what my own notes on it call exploding along a direction rather than converging to one.

The unit’s output times its own weights is the unit’s reconstruction of the person, the part of them it already accounts for. Oja’s correction subtracts that from the person before the update is formed, so the rule moves the weights toward only the part of each person the unit does not yet explain. Nothing else changes. The rate, the output and the locality are all as they were.

w ← w + rate · y · (x − y · w)

adjusted input = (−5, 5) − (−5) × (1, 0) = (0, 5)
update = 0.0025 × (−5) × (0, 5) = (0, −0.0625)
new weights = (1, 0) + (0, −0.0625) = (1, −0.0625)

The subtraction has removed exactly the part of the update that lay along the weights themselves, which is the part that was doing the lengthening, and left the part across them, which is the part that turns. Section 6 makes that exact.

Ask what one step does to the squared length of the weights and the answer is an identity with two terms, and no approximation in it. Write r for the bracket, the residual the update is built from.

|w′|² = |w|² + 2 · rate · y² · (1 − |w|²) + rate² · y² · |r|²

The first term is the subtraction at work. It is positive while the weights are shorter than one, negative while they are longer, and zero at length one exactly, so a vector that has grown is pulled back and one that has shrunk is pushed out, harder the further from one it is and harder the more strongly the unit fired.

The second term is the square of the step and is always positive, which is why a single step can still leave the length a little over one. It is smaller by a factor of the rate, so it loses as the rate falls.

first term ≈ 2 × 0.0025 × 144.06 × (1 − 1.0640) ≈ −0.0461
second term ≈ 0.0025² × 144.06 × 65.15 ≈ 0.0587
new squared length ≈ 1.0640 − 0.0461 + 0.0587 ≈ 1.0766
new length ≈ √1.0766 ≈ 1.0376

Over epochs the pull wins. At a constant rate the length at the end of each of the first five epochs on the measured four is 1.0372, 1.0084, 1.0009, 1.0001 and 1.0000, and by the thirteenth no weight moves more than a millionth in a whole pass, which is the test the fit stops on. At no point did anything divide by the norm.

…

The blunt way to keep a weight vector at unit length is to take the Hebbian step and then divide by the new length. For a small rate the new length is close to one, and expanding the division to first order in the rate, the calculus primer’s move of keeping the slope and dropping the curve, turns the division into a subtraction.

So the subtracted term is the piece that normalising would have removed, applied before the length has a chance to drift. That is why the rule reads as Hebb’s rule with a correction and why it keeps every property of Hebb’s rule that mattered, above all that the weight joining input to output is changed using only the values at its two ends.

Now ask where a unit obeying the corrected rule stops moving. Over many people the update averages, and the averages are quantities the PCA page built. The average of y times x is the average of (w · x) times x, which is the covariance matrix C applied to w, and the average of y squared is the variance along w, which that page wrote as wᵀCw.

average update = rate · (C w − (wᵀ C w) · w)

The unit rests where the average update is zero, which says that C w is a multiple of w. A direction the matrix only stretches is the linear algebra primer’s eigenvector, and the multiple, wᵀCw, is its eigenvalue, the variance along w. Every eigenvector is a resting point. Only the one with the largest eigenvalue is a stable one, and the argument is short enough to fold away.

perturbed weights: w = u + εv
first-order change in the perturbation ≈ rate × (μ − λ) × εv

C w = λ w,        λ = wᵀ C w

On the measured four the covariance matrix is the PCA page’s [62.5, 37.5; 37.5, 62.5], its eigenvectors run along (1, 1) and (1, −1), and the unit rests on the first. Nothing here built that matrix. The average of the updates is what the matrix would have said, and the unit reaches it one person at a time.

Step through one epoch on the measured four from the weights (1, 0). The seeded walk presents person 4, then 2, then 1, then 3, and the widget below is that walk, one person per press, with the eigen direction dashed behind the arrow. The arrow is drawn at the length the rule left it, so its length and its angle are both on the picture.

…

Forty-five degrees off at the start, twenty-four off after one epoch, and the whole of the turn came from four multiplications each involving one person and the weights as they stood. Press on through the second and third epochs and the angle falls to 8.3 and then 2.7 degrees.

The first step in that table went the wrong way. Person 4 turned the weights from 45 degrees off the answer to 48.6 degrees off, and it was the next two people who turned them back. That is not a mistake in the rule. A single person pulls the weights toward their own axis, whichever sign they lie on, and person 4 lies on the second eigen direction, so they pull toward it.

What decides the outcome is how hard each person pulls, which is the output times the part of the person that lies across the weights.

turn from one person  =  rate · y · (the part of x across w)

Both factors grow with the person’s distance from the mean, so the pull grows with its square. On the measured four the two people on the first axis are ten root two from the mean and the two on the second are five root two, so the first axis pulls four times as hard per person, and over an epoch the weights turn toward it. That is the covariance matrix acting in instalments. Every person’s pull is one term of the average section 8 wrote down, and the average is what wins.

Because one person can turn the weights the wrong way, the order the people arrive in matters, and a fixed order would let the last person of every epoch have the final say every time. So the fit reshuffles the order at every epoch, from a seeded generator that also draws the starting weights. The seed is what makes a fit reproducible, and the widgets on this page all use the same one, which is why the numbers in the prose are the numbers on the screen.

Whether the seed changes the answer is a measurement, and on the measured four it does not. Five seeds start the unit in five different directions and every one of them lands within a ten thousandth of a degree of the diagonal, in between fourteen and twenty-two epochs. The sign differs, since a direction and its negative are the same direction and the rule lands on either.

…

The update multiplies the rate by the output and by the person, and the output is itself the person times the weights, so the update carries the square of whatever unit the people are measured in. A rate that behaves on data spread about one is a hundred times too large on data spread about ten, and the default rate of 0.05, which suits data spread about one, overflows on the measured four in centimetres on the third epoch. So the endpoint sets the rate from the cloud rather than fixing it.

starting rate = 0.5 / (longest deviation)²        = 0.5 / 200 = 0.0025 on the measured four

The half comes from section 6. The subtraction moves the squared length toward one by twice the rate times the output squared, and the output squared is at most the squared length of the longest person, so at a half the largest single kick lands on length one rather than carrying past it. Scaling every rate alike moves no direction and no share, which is what lets the eigensolver be run on the raw people and still be the right comparison.

Write the heights in millimetres and the starting rate becomes 0.0000495, the first direction still lands within a hundredth of a degree, and nothing else about the answer moves.

Multiply the starting rate and watch the length. At twice the rate, held constant, the walk from (1, 0) settles in three epochs at a length of 0.9994. At three times it never settles, and the length at the end of each epoch bounces between 0.24 and 1.25 for all twenty. At eight times the first four presentations leave the length at 1.12, 1.68, 9.48 and 210, and on the third epoch a weight stops being a finite number.

…

The mechanism is the second term of section 6. Past a certain rate the square of the step outgrows the pull back toward one, so a kick meant to shrink the weights grows them instead, and the next kick is larger. The fit refuses a walk like that by name rather than completing it, and where the line falls depends on the cloud.

On the measured four the fit at four times the rate is refused on the fourth epoch; on the crowd four times the rate runs the full two hundred epochs and it is eight times that is refused, on the first.

…

Vary the epoch budget instead, with the rate falling a hundredfold across whatever budget is given. On the measured four the first direction is 23.1 degrees off after one epoch, 16.4 after five, 6.9 after ten, 1.0 after twenty and three thousandths after fifty; a budget of two hundred stops itself at epoch 91, because no weight moved more than a millionth in a pass, with the direction a millionth of a degree off. That is 364 presentations of one of four people.

…

Every row of that table is a fresh fit rather than a frame of one, because the rate falls across the budget, so a walk of ten epochs is a walk with a steeper decay and not the first ten epochs of a walk of two hundred. On the crowd the first direction is 1.8 degrees off after one epoch, half a degree after five and hundredths after ten, and the walk never stops itself within two hundred, for a reason section 18 gets to.

The textbook argument, from Robbins and Monro, is that a constant rate can never settle. Each person moves the weights by a fixed amount, so the weights keep chasing whichever person arrived last, and the fit becomes a fact about presentation order. I measured it, and on the measured four the claim does not hold.

Every one of those four lies exactly on an eigen direction, so at the answer the bracket is exactly zero for each of them, and a constant rate settles at epoch 46 where the falling one takes 91, and lands on the diagonal just as exactly.

On the crowd the claim holds. Nobody there lies on an axis, so at the answer each person’s update is small but not zero, and the constant-rate walk never settles in two hundred epochs. Within its twentieth epoch the direction wobbles between 0.12 and 0.77 degrees off as the eleven people go past, where the falling rate holds it within a hundredth throughout.

…

Give the cloud a second unit with its own weights, obeying Oja’s rule on its own, and it solves the same problem the first unit solved. On the measured four the two units are 76 degrees apart after the first epoch and 5.3 degrees apart after twenty, closing every epoch; on the crowd they coincide to a thousandth of a degree, so the second unit has repeated the first unit’s answer and found nothing of its own.

…

Sanger’s extension hands the second unit the person with the first unit’s reconstruction removed, so the second unit can only lean on what the first left unexplained. The bracket for unit i subtracts the reconstructions of every earlier unit and of unit i itself, and the last of those is Oja’s own normalisation.

w₂ ← w₂ + rate · y₂ · (x − y₁ · w₁ − y₂ · w₂)

The sum running up to and including the unit’s own term is the whole of it. Drop that term and the second unit loses its normalisation; drop the earlier terms and it loses its reason to differ from the first. The part of the second unit along the first direction is driven toward zero, which is what perpendicular means, and its own subtraction keeps its length near one. On the measured four the two units are 83 degrees apart after one epoch, 76.5 after twenty, and 89.998 after the full walk of 91 epochs.

…

The cost of deflation is that a unit chasing a small variance is pushed by small outputs, and its updates are small in proportion. On the crowd the second direction holds one percent of the spread, and after two hundred epochs of the falling rate it is 8.2 degrees off its twin at a length of 0.43, nowhere near one.

On the ideal case, where it holds seven hundredths of a percent, it is 20.5 degrees off at a length of 0.18. The first direction on both is within a few thousandths of a degree.

…

What starves the second unit is the falling rate, and I measured that too. Hold the rate constant on the crowd and the second direction reaches 0.07 degrees at a length of 1.003, while the first wobbles as section 15 showed; run the falling rate at four times its size and the second reaches 0.14 degrees at 0.995. The length is the diagnostic for all of this. A slow unit comes back with a length well under one, and that is how the readout reports it.

…

An eigensolver’s directions are perpendicular to the last bit and its variances add to the total exactly. The rule’s are neither, and the fit reports rather than pretends. The worst orthogonality is the largest dot product between two learned unit directions, 0.000043 on the measured four after the full walk and 0.14 on the crowd, where the second direction was left short.

The variances along the two directions add to 166.66666685 against a total of 166.66666667, a little over, because two directions that overlap slightly count the overlap twice. After one epoch, with the directions 0.12 from perpendicular, they add to 176.3.

kept variance = variance along w₁ + variance along w₂  ≥  total, when w₁ · w₂ ≠ 0

The claim of the page is one number, the angle between the direction a unit learned and the direction an eigensolver computed, taken modulo a half turn because the rule lands on either sign. On the measured four after the full walk it is 0.0000012 degrees for the first direction and 0.0024 for the second.

On the crowd it is 0.0031 for the first and 8.2 for the second, for the reason section 18 gave, and on the ideal case 0.001 for the first. The playground at the top of the page draws both directions over any cloud you build, and its angle readouts are these numbers.

The variance along each learned unit direction is measured from the people, by projecting them onto it and taking the sample variance, which is the same quantity an eigenvalue reports. On the measured four the two come back 133.3333333 and 33.3333335 against eigenvalues of 133.3333 and 33.3333, and the shares 0.8 and 0.2 agree with the PCA page’s to six decimals. On the crowd the first share is 0.9897 by both routes.

variance along w = sample variance of (x · w / |w|) over the people

A fitted rule transforms people the way a fitted PCA does, by centring with the stored means and projecting onto the unit directions, and it names the output columns as the PCA page does so one can be swapped for the other downstream. On the measured four person 1 scores 14.1421 on the first direction by both routes and person 3 scores 7.0711 on the second by both, with the cross terms at six ten-thousandths and six quadrillionths where the eigensolver has exact zeros.

On the crowd the first scores agree to two thousandths for every person and the second do not, because the second direction is eight degrees off. Person 5 scores 2.98 on it by the rule and 1.19 by the eigensolver, which is what an eight-degree error looks like on a person thirteen units from the mean.

Two things, and they are narrow. The covariance matrix of p features holds p squared numbers; k units hold k times p weights, so at ten thousand features and ten directions the matrix is a thousand times the size of the weights, and the rule never builds it. And the update reads one person and forgets them, so a fit can be driven by people arriving over time from a source too large to hold, tracking a cloud that drifts underneath it.

Against that, it is slow, and for anything that fits in memory the eigensolver wins outright. On the crowd, two hundred epochs of two units is 2,200 presentations through a Python loop, and I measured the fit at 28 milliseconds against 0.38 for the eigensolver, a ratio of 76. It is also less exact, by the residual a finite walk leaves, which on the measured four is millionths of a degree and on the crowd’s second direction is eight degrees.

The failure a reader is likeliest to meet is the one section 13 measured, a rate that behaves on one dataset and overflows on the same data in different units. The fit does not complete and answer with a non-finite direction. It stops on the epoch the weights overflowed and refuses, naming the epoch and the cause, and the endpoint passes the refusal through as it stands.

DivergenceError: the weights overflowed on epoch 4; the learning rate is too large
for this data’s scale, so lower it or standardize the features first

That is the measured four at four times the endpoint’s rate. The repairs are the two the message names, a smaller rate or features standardised first, and the second is the honest one for columns measured in different things, exactly as it is for the PCA page’s standardised variant, with the difference that there it changes which matrix is decomposed and here it also decides whether the walk survives.

Run the rule on the raw positions rather than the deviations and it still settles at length one, on a direction that is wrong. On the measured four the weights come to rest 0.08 degrees from the line joining the origin to the mean at (170, 68) and 23.1 degrees from the eigen direction, which is the angle between those two lines.

On the crowd it is 0.74 and 22.1 degrees. The rate for this walk is set from the longest position rather than the longest deviation, 0.000013 rather than 0.0025, or it would overflow on the first person.

…

The average update on raw rows is the second-moment matrix rather than the covariance matrix, and its leading eigenvector is dominated by where the mean is when the mean is far from the origin, as it is for heights in centimetres. The unit did what the rule says on the rows it was given, and those rows carried the origin’s position as well as the people’s shape.

Put eight people evenly round a circle about the mean and the two eigenvalues tie, at half the variance each. The eigensolver still answers, with the height axis and the weight axis, and that answer is an arbitrary choice, since every direction through a circle carries the same spread. The rule answers too. It settles at length 1.0005 on a direction 80 degrees from the eigensolver’s, with a share of exactly a half, and five seeds send it 21, 9, 57 and 39 degrees from where the page’s own seed sent it.

None of those is wrong, and the walk never stops itself, because a flat objective gives it no reason to.

…

Hold height constant and let weight vary and the first direction is pure weight, (0, 1) to the last bit, in agreement with the eigensolver. The second unit is then handed a residual of zero on every person, since the first explains everything, and its only remaining term is its own subtraction, so it can only shrink. After two hundred epochs it is 0.24 long and 22 degrees from the axis the eigensolver assigns a variance of zero, and the length is again the report that nothing was found there.

A complete implementation states how many directions it learns, that it centres and stores the means, what schedule the rate follows and against what count it decays, the epoch cap, the tolerance on movement that stops the walk, how the starting weights are drawn and how the order is shuffled, that the weights are never normalised during learning, that the variance is measured along the unit direction, which of length, orthogonality and ordering it checks and which it reports, and that it has no inverse transform.

Every row of that table was probed, on this page’s own people where an endpoint reaches the case and against the model directly where none does. The two that deserve the most care are the refusals that are not refusals. A constant rate is accepted because a walk that never settles is worth being able to demonstrate, and a second direction left short is accepted because the length reports it, and refusing it would turn every under-converged fit into an error where the honest answer is that it under-converged.