Self-Organising Maps

The crowd in the box above is eleven people measured twice over, once for height in centimetres and once for weight in kilograms, with whatever else was known about them thrown away. Three of them are short and light, three are tall and heavy, and five sit in between. Nothing here is a question with an answer to be predicted, so the only thing that can be found is whatever structure the two columns already have.

The k-means page took a crowd like this one and sorted it into a fixed number of groups, each group described by one point that is the average of its members. That answer is useful and it is incomplete in a particular way. It tells you who goes with whom, and it tells you nothing at all about how the groups sit relative to one another.

Suppose the grouping method hands back three groups numbered 0, 1 and 2. Is group 0 more like group 1 than it is like group 2? The numbers cannot say. Nothing in the method ever compared one group with another; each centre was moved only toward the people who chose it, and the numbering came from whichever order the starting centres happened to be drawn in. Run the same fit from a different seed and the same three groups come back wearing different numbers.

You could of course measure afterwards how far apart the three centres landed and rank them yourself. That is a fair thing to do and it is not what a map does. A map fixes the arrangement before it sees any data, as part of the model, and then arranges the answer to fit it.

So fix a small grid, say a row of four squares, and give each square a position in the height and weight plane. Call each square a cell. The grid never changes during the fit, so cell 1 is beside cell 2 and two steps from cell 3 for the whole run, whatever those cells are doing among the people. What the fit moves is where each cell sits in the plane.

Fitted to the crowd, the four cells come to rest at (177.0, 76.8), (160.3, 59.0), (144.1, 46.6) and (123.2, 28.5), reading along the row. Those are the same four prototypes a grouping would produce, except that this time the order they are stored in means something. Reading along the grid reads down through the crowd from the tallest and heaviest to the shortest and lightest, and a fifth person handed to the finished model would land somewhere on that row rather than in a group with no neighbours.

Start every cell somewhere sensible, on a randomly drawn person, and then show the people one at a time, in a fresh shuffled order each pass through the data. For each person, three things happen. First the cells compete, and the one nearest the person wins. Then they cooperate, and every cell is given a score for how near it sits to the winner on the grid. Then they all adapt, each moving toward the person by its score times a fraction called the step.

winner    = the cell u minimising ‖person − cell_u‖
score_u   = exp( −d(u, winner)² / (2 · reach²) )
cell_u    ← cell_u + step · score_u · (person − cell_u)

The letter d in the middle line is a distance counted on the grid, so a cell beside the winner is one away and a cell across a diagonal is the square root of two away. The winner is zero steps from itself, which makes its own score exactly one.

Take three cells in a row, placed by hand at (120, 30), (150, 50) and (180, 70), and show them the person at (156, 53). The middle cell is 6.708 away and the other two are 42.720 and 29.411 away, so the middle cell wins. At a step of a half its score of one gives it the full move, which closes half the gap and lands it at (153, 51.5), exactly 3.354 from the person.

gap    = (156, 53) − (150, 50) = (6, 3)
move   = 0.5 × 1 × (6, 3) = (3, 1.5)
cell   = (150, 50) + (3, 1.5) = (153, 51.5)

The two cells either side of the winner are one step away on the grid, so at a reach of one cell each of them scores exp of minus a half, which is 0.6065. They move that fraction of the step along their own gaps, and their gaps are much larger, because they started much further from the person.

gap   = (156, 53) − (120, 30) = (36, 23)
move  = 0.5 × 0.6065 × (36, 23) = (10.92, 6.98)
cell  = (120, 30) + (10.92, 6.98) = (130.92, 36.98)

So the left cell travelled 12.956 where the winner travelled 3.354, and it took the smaller share of the step. There is no contradiction in that, since the share scales a gap rather than a distance, and a cell far from the person has a large gap to take a small share of.

…

Drag the person and watch which cell wins change. Slide the reach down to zero and the two neighbours stop moving altogether while the winner moves exactly as far as before, which is section 15 in miniature. Slide the step up to one and the winner lands on the person and forgets everything it had learned from anybody else.

The three distances before the presentation are 42.720, 6.708 and 29.411, and after it they are 29.765, 3.354 and 20.492. Every cell is nearer the person than it was, and that holds for any step between zero and one, because the move is along the straight line from the cell to the person and stops short of arriving.

f(cell)      = ½ · ‖person − cell‖²
df / d cell  = −(person − cell)

Two distances appear in the rule and they are not the same kind of thing. The competition asks how far a person is from a cell, which is measured in centimetres and kilograms and changes at every presentation. The cooperation asks how far one cell is from another on the grid, which is measured in cells and never changes at all.

Putting the second quantity where the first belongs gives a model that runs without complaint and reports plausible figures, and two things then go wrong that were found by writing it that way and running it. The grid stops mattering, so a row of eight cells and a two by four block fit identically. And the cells collapse onto one point, because cells that already agree pull each other closer, which makes them agree more.

So far the step and the reach have been two fixed numbers. In a real fit both of them fall as the run goes on, and neither falls the same way. The step falls geometrically, from a half to a hundredth, because what matters about a step is its order of magnitude and a geometric fall spends most of the run at small values.

The reach falls in a straight line, from half the grid’s longest side down to a quarter of a cell, because a reach is counted in cells and the middle of the run should be the middle of its range.

step(t)   = 0.5 · (0.01 / 0.5)^((t − 1) / (T − 1))
reach(t)  = r₀ + (0.25 − r₀) · (t − 1) / (T − 1),   r₀ = half the longest side

…

Both are written against T, the number of passes the run is given, so the epoch slider on the playground does not add passes to the end of a run. It stretches the whole run, every stage of it lasting proportionally longer, which is section 14.

On a three by three grid the reach begins at 1.5 cells. A cell one step from the winner then takes 0.8007 of the winner’s move and a cell across a diagonal takes 0.6412, so almost the whole grid travels together and the arrangement is settled early, while every cell is still being dragged by everybody else’s people. By the last pass the reach is a quarter of a cell, the neighbour’s share is 0.000335 and the diagonal’s is about a ten-millionth.

A quarter of a cell is not an arbitrary stopping place. At that width a cell one step away moves by a third of a thousandth of the winner’s move, which is below anything a picture of the map could show, so for practical purposes the run has finished arranging and is refining each cell alone.

The step is a fraction of the remaining gap rather than a distance in centimetres and kilograms. A step of a half halves the gap, a step of a hundredth closes a hundredth of it, and a step of one lands the cell exactly on the person. That last case is worth naming, because a cell that lands on the person has forgotten every other person it ever won.

Since the step is a fraction rather than a distance, it does not shrink because the map is getting better. A cell already well placed is dragged just as far by the next person as a badly placed one, so if the step never falls, the map never settles, and what you read at the end is a fact about which person happened to arrive last.

The reach is a width, and a width is hard to picture. Count cells instead. Ask how many of them take at least a thousandth of the winner’s move, which is the smallest share that could show up in a drawing of the map. On a three by three grid over a hundred passes the answer is nine for the first eighty-nine passes, five from pass 90, and one from pass 99.

On a row of six cells it is six, then five from pass 80, three from pass 90 and one at pass 100.

The lower chart in section 9 draws that count. It is a staircase rather than a curve, since a cell is either taking a visible share or it is not, and the staircase says the same thing the reach does in a form that can be counted, since the run begins by moving the whole grid at once and ends by moving the winner alone.

Two decays, two claims about what they are for, and the way to test them separately is to hold each one still in turn and refit. The people below are eighteen along a gentle arch, the ideal case for a map, since a row of cells can follow a curve and no straight line can. The same eighteen, the same six cells, the same seed, the same hundred passes, four times over.

…

With both shrinking, the map settles, moving 0.2703 on its last pass, describes the people at a mean distance of 7.9669 and arranges itself at 0.9860. Hold the step at a half and the map is still travelling 13.5400 per pass at the end, roughly a fifth of the 74.7 that the settled fit’s own six cells span, so it is being dragged a fifth of the way across the map by whoever arrived most recently.

Hold the reach wide instead and the map settles beautifully, at 0.0278, and arranges itself better than anything else here, at 0.9979, while describing nobody. Its six cells span 31.2 of the arch rather than 74.7, so they rest in a knot near the middle and the mean distance from a person to their own cell is 22.7539.

Because both curves are written against the pass budget, a run of twenty passes is not the first twenty passes of a run of a hundred. Its tenth pass is already halfway down both curves where the longer run’s tenth has barely begun to fall, and its last pass holds exactly the step and the reach the longer run’s hundredth holds.

Take the reach to zero. The score is then one at the winner and zero everywhere else, so only the winner ever moves, and the whole rule is one line.

winner ← winner + step · (person − winner)

Each person that a cell wins nudges it a fraction of the way toward them, which is a running average of the people that cell has won, assembled one at a time. The grouping method computes the same average in a single jump, by assigning everybody and then moving each centre onto its group’s mean. The quantity being computed is the same one, and so are the places it comes to rest; what differs is the arithmetic that gets there.

So run both on the crowd and compare. Three cells with no reach against three groups, and the two put the same people together, with the furthest-separated pair of prototypes 0.0233 apart. The mean distance from a person to their prototype is 5.1887 one way and 5.1912 the other.

What they do not agree about is any label. The chain answers 0 0 0 0 0 2 2 2 1 1 1 and the grouping method answers 1 1 1 1 1 2 2 2 0 0 0, which is the same partition written in different numbers, and it is why the comparison in the readout is about who shares a group rather than about who was given which number.

The agreement is not a promise, and two differences survive switching the reach off. This rule visits one person at a time under a step that decays toward something small, so a run with a pass budget can stop short of a resting place; the grouping method reassigns everybody at once and jumps each centre onto the mean, which reaches a resting place in a handful of passes. Neither difference has anywhere to bite when the groups are well separated, which is why they agreed at three cells.

Slide the count up to four in the widget above and the agreement stops. On these eleven people the two methods put different people together, the furthest prototype pair sits 8.0623 apart, and the chain describes its people at a mean distance of 3.5932 against the grouping method’s 3.6373. The online walk found the better arrangement of the two here, which is luck about which local resting place each one reached rather than a general fact about the methods.

Ask the grouping method for twelve groups over these eleven people and it refuses by name, since a group that nobody chose has no mean to move to. Ask a map for thirty six cells over the same eleven and it fits, and ten of the thirty six win somebody. The other twenty six are not wasted and they are not errors.

They came to rest along the ways between the cells that did win, because their grid neighbours dragged them there, so a person handed to the finished map who falls between two of the winners has a cell of their own to land on.

This is also why the starting positions matter less here than they do for a grouping. There, a centre only ever moves toward people who already chose it, so two centres landing in one clump can never separate, and a careful spreading procedure is worth its cost. Here a cell that has never won anything is still pulled about by its neighbours, so two cells starting in one clump are pushed out of it over the wide-reach passes whether or not either of them has won a single person.

Here is the finished chain of four over the crowd, drawn twice. On the left is the grid in the arrangement the fit never changed, with the people each cell won written inside it. On the right is where those same four cells actually came to rest among the people.

…

Reading the left panel from one end to the other reads the same order as following the net across the right panel, which is the arrangement claim in a picture. Switch the reach away with the button and the left panel stops reading in any order at all, since the cell holding the three tallest people now sits between a cell holding one of the middling people and the cell holding the three shortest, while the right panel still places every person on a reasonable prototype.

Make that measurable. Every pair of cells has two numbers, how many steps apart the two sit on the grid and how far apart they came to rest among the people, and if the map arranged itself the two rise together.

…

With the reach the two correlate at 0.9902 across the six pairs of a chain of four. With the reach taken away they correlate at −0.1773, which is no relationship, and the sign of that number changes from seed to seed because there is nothing there to have a sign. That second fit is the control the claim needs, since it describes the crowd rather better than the arranged one does and carries no arrangement whatever, so the two properties can be seen apart.

Now the qualification the claim is misleading without. Cells that are neighbours hold people who are alike, and it does not follow that a cell two steps away holds people twice as different. On the chain of four the three pairs sitting one step apart came to rest 20.407, 24.364 and 27.717 from each other, so the widest of them is 1.358 times the narrowest for the same reading on the grid. The pair three steps apart rests 72.332 from each other, against three times the middle one-step reading, which would be about 73.

On a three by three grid over the same eleven people it is far worse than that, and it is worth seeing how much worse. The two pairs of cells at opposite corners of the grid are the furthest apart anything can be there, 2.83 steps, and one of those pairs came to rest 78.831 apart while the other came to rest 11.344 apart.

A pair one step apart came to rest 28.622 apart, further than the second of those corner pairs. The closest pair of all, 4.757, sits across a diagonal rather than side by side.

Why is the three by three so much worse than the chain? Because these eleven people run essentially along one direction, taller people being heavier, and a two-dimensional sheet laid over a one-dimensional cloud has nowhere to put its second dimension except folded back on itself. The correlation on that fit is 0.5308 against the chain’s 0.9902, and the fold is exactly what the difference measures.

…

Three of the nine cells there won nobody, and the shape of the grid is a modelling choice rather than a detail. A row of cells suits data with one dominant direction, a square suits data that genuinely spreads two ways, and a square over a line fits and predicts perfectly well while reporting an arrangement whose weaker half is the fold rather than anything about the people.

The arrangement is paid for and the price is visible. On the chain of four, the arranged map puts every person a mean of 5.1435 from their cell and the same chain with the reach taken away puts them 3.5932 away, which is thirty percent closer. On the three by three the two figures are 2.8341 and 0.7117.

The reason is in Part 2. For as long as the reach lasted, every cell was dragged toward people its grid neighbours had won, so each of them ended somewhere between its own people and its neighbours’. Afterwards the step is already small, and the cell walks toward its own average in strides too short to arrive.

The seed here decides two things, which people the cells start on and the order the people are shown in on each pass, so a differently seeded fit is genuinely a different walk rather than the same walk relabelled. Here are six of them on the crowd.

…

All six put the same people together and all six arrange the chain about equally well, correlating between 0.9901 and 0.9904, and describing the people at between 5.1435 and 5.1520. Each of the six is exactly reproducible on its own, since asking the same question twice gives back the identical numbers, and that is what fixing a seed buys; none of the other five reproduces the first.

What varies is the direction, since four of the six lay the chain out with the shortest people at one end and two lay it out the other way round.

That reversal is the same warning the grouping method carries, with one extra wrinkle. There, nothing ever told the method which group deserved which number, so two correct fits can agree completely about who goes with whom and disagree about every number. Here, cell 3 is a place as well as a number, and a fit that lays the identical arrangement out backwards has produced the same map read right to left.

Most of the iterative methods on this site have a number that falls as they run and can be watched. This one has none. Each cell is walking downhill on its own squared distance to whichever person is in front of it, weighted by its share, and the person changes at every presentation while the winners change underneath as the cells move. For a continuous spread of inputs there is no single quantity whose slope this rule is following, which is a result about the algorithm rather than a gap in this implementation.

So the readouts on this page report two things instead. How far the furthest-moving cell travelled during the last pass, which says whether the map has settled, and the mean distance from each person to their own cell, which says whether it describes anybody. Both are needed, as section 13 measured, since a run can score well on either alone.

A description of this method is incomplete until it states the shape of the grid and how many cells it holds, how grid distance is counted, the shape of the neighbourhood and the schedule its reach follows, the schedule the step follows, whether both schedules are written against the pass budget or against the pass number, how many passes are allowed and what else may stop the run early, how the cells are started, whether the people are reshuffled each pass, what the metric in the competition is and whether it can be changed, what a label means, and which of the cell positions, the winners and the two diagnostics it hands back.

This implementation answers all of those. The grid is a rectangle and grid distance is straight-line across it, so a diagonal neighbour is the square root of two away rather than one or two, which is chosen because the reach is stated as a radius, and counting a diagonal as one step would let the same radius reach further across the grid on the diagonal than along a row.

The neighbourhood is a bell curve in grid distance. Both schedules are fractions of the pass budget. The cells start on randomly drawn people, the people are reshuffled every pass, and the metric is fixed at straight-line distance for the reason section 7 derives.

Each row below is a request that was actually made while this page was served, and the sentence beside it is either the refusal’s own words or a description of what the fit answered.

…

Three of those deserve a sentence each. A reach that never shrinks is accepted rather than refused, and it produces a map that has settled, arranges itself almost perfectly and describes nobody, which no guard can catch because it is a legitimate answer to a badly chosen setting. A column that never changes is kept exactly, every cell resting at 60 along it, because the gap along a flat column is zero at every presentation and no step in the fit divides by a spread.

And a query is matched to the fit by column name rather than by position, so the same columns in the other order answer identically while a missing or unknown column is refused.

One caution that a measurement did not support belongs here too. A method built on distances is usually said to follow whichever column carries the larger numbers, so I rewrote the crowd’s heights in millimetres and expected the map to be dragged onto the height axis. It was not. The same four cells won the same people and the arrangement moved from 0.9902 to 0.9892, because on this crowd height and weight run together so closely that stretching one barely changes which cell is nearest.

On data where the columns are less related the caution would bite, and the honest report is that it did not bite here.