Random Indexing

Everything on this page is fitted to one of two collections, and it is worth knowing what is in them before any method touches them. The larger one is twenty-four documents, twelve about cooking and twelve about sailing. The cooking half is written from ten words, flour, sugar, butter, eggs, oven, bake, stir, whisk, dough and pan; the sailing half from ten of its own, sail, wind, boat, harbour, anchor, tide, mast, rope, deck and crew.

No subject word appears in both halves. What the halves share is three words carrying no subject at all, and, the and we, and each document uses exactly one of them.

Each document is six words long, five consecutive words of its own half taken in a cycle and one of the three shared words, which comes to 144 word occurrences over 23 distinct words. The arrangement is deliberate, since it makes every word of a half keep the same company as every other word of that half, and so makes the two numbers this page keeps reporting mean something.

The smaller collection is three sentences of three words each, the cat sat, the dog sat and the cat ran. Five distinct words, and every number it produces can be checked by hand, which is what Part 2 uses it for.

The starting point for every counting method is the same table. Write down one row for each distinct word and one column for each distinct word, and in the cell where a row and a column meet, put how often those two words turned up within a few positions of each other. How few is the window, and five positions on each side is the usual choice; a sentence boundary stops the reach, so nothing outside a document is ever company for anything inside it.

Every pair is counted from both ends, so the table is the same read either way round, and a word’s row and its column hold the same numbers. On the twenty-four documents the row of flour totals 30 and the rows of and, the and we total 40 each, which is a fact Part 4 comes back to.

It would be reasonable to expect a table of who appeared beside whom to be useful only for pairs that did appear beside each other. It is not, and the reason is the whole point of counting. Two words that never met can still be recognised as alike, because what is compared is not the cell where they meet but their two rows, and two words that keep the same company have similar rows whether or not they ever shared a document.

On the twenty-four documents, 110 of the 190 pairs made of two subject words never once appeared in the same document. Flour and bake are one such pair, and their cell in the table holds exactly 0. Compare their rows and the answer is 0.7551, which is higher than any pair flour actually did meet. The nearest word to flour, by the table, is a word it was never once seen beside.

A row per word and a column per word means the table has as many numbers as the square of the vocabulary. On the twenty-four documents that is 23 by 23, or 529 numbers. But nobody wants 23 numbers a word. The whole family of counting methods squeezes that row down to a handful of coordinates before anybody uses it, and at 16 numbers a word the answer holds 368.

numbers in the table = V × V

numbers in the answer = V × d

Constructing the full co-occurrence representation before reducing it allocates more coordinates than the final vectors retain.

temporary-to-final width ratio = vocabulary size / embedding width
example ratio = 23 / 16 ≈ 1.44

The ratio is small on this toy corpus. It grows when the vocabulary grows while the requested embedding width stays fixed.

The trick starts somewhere that looks unpromising. Give every word in the vocabulary a fixed list of numbers of exactly the width the answer is wanted at, drawn at random, and having nothing whatever to do with what that word means or where it appeared. Almost all of the entries are zero. A few positions are picked at random without repeating, half of them are set to +1 and the other half to −1.

At the width this page works in, that is 16 numbers of which 4 are anything at all. The direction drawn for flour is non-zero at positions 5, 7, 8 and 9 and zero at the other twelve. Draw again with a different starting point and every one of those numbers changes, and nothing about the collection has moved.

…

Now read the collection once, straight through. Every time a word appears, look at the words within the window on either side of it, and add each of their directions onto a running total kept for the word in the middle. When the reading finishes, the running total is that word’s position, and it is as wide as a direction was, which is the width that was asked for.

position(word) = Σ over every occurrence  Σ over every neighbour  weight(distance) × direction(neighbour)

Two words that keep the same company add up the same directions and land near each other, and neither of them ever needed a row of its own in anything. That is the whole of the method, and the rest of this page is spent on why the sum does not turn into a smear and on how far its answer falls from the one the table of counts would have given.

…

It is worth pausing on what is absent. There is no objective being minimised, so there is no learning rate and no question of whether the walk has converged. There are no eigenvectors, so no decomposition has to be run and nothing has to be reordered by how much it accounts for. There is no second pass over the collection.

The only randomness in the whole procedure is the draw of the directions, and that happens before the first word is read. Fix the draw and the answer is fixed, exactly, down to the last bit, however many times it is run.

The work is easy to count. On the twenty-four documents there are 144 word occurrences, and at a window of five positions each side there are 720 occasions where one word is inside another’s window. Each of those adds a direction with 4 non-zero entries, so the whole reading is 2,880 updates to a single number, and nothing else happens.

There is a second route to the same positions, and it is the route that says what the method actually is. Instead of walking the collection, build the table of counts from Part 1, stack the drawn directions into a block with a row per word, and multiply the two together. A word’s row of counts says how many of each other word’s direction to add, so the multiplication and the walk are the same additions in a different order.

positions = counts × directions

So a position is a word’s row of the table, projected from as many numbers as there are words down to as many numbers as were asked for, by a random map. That is what makes this a projection of the table rather than a rule of thumb that happens to work, and it is why the geometry in Part 3 applies to it at all.

…

Measured on the three sentences, and on the twenty-four documents as well, the two routes agree exactly and the largest disagreement anywhere in the answer is 0, since every weight involved is a number binary holds exactly. Move to the twenty-four documents and let a neighbour further away count less, so that a weight of a third appears, and the largest disagreement becomes 8.88 × 10⁻¹⁶ in a table whose largest entry is 11.25, which is rounding and not a difference of method.

Sixteen numbers a word, four of them non-zero in each drawn direction, one reading of the collection. Two words of one subject come out at 0.6399 on average and a word of each subject at 0.1247, and the two halves were never named to it. The whole table of counts, read directly and never squeezed, answers 0.6629 and 0.1192 to the same two questions.

Asked which words are nearest to flour, the fit answers eggs at 0.7909, butter at 0.7285, bake at 0.7130, whisk at 0.7017, pan at 0.7003 and sugar at 0.6270. All six are cooking words, and the six words it puts furthest away, anchor, tide, wind, boat, harbour and sail, are all sailing words. The playground at the top of this page is that fit, with the width, the draw and the counting rule left open.

The obvious objection to Part 2 is that the additions must interfere. Twenty-three words are being added into positions only sixteen numbers wide, so there is not enough room for each word to have a place of its own, and every position ought to end up as a smear of everything.

The reason it does not is a fact about high-dimensional space that is hard to believe from low-dimensional experience. Two directions drawn at random are nearly at right angles to each other almost all of the time, and the more numbers they have the more nearly. Being at a right angle is exactly the condition for one to contribute nothing to a reading of the other, so adding a great many of them together leaves each one still recoverable, up to a little interference.

Drawing two hundred directions at once and measuring all 19,900 pairs of them, at 50 numbers each the mean size of the overlap is 0.0744 and 71.8% of the pairs are at exactly a right angle. At 500 numbers it is 0.0077 and 96.9%. Neither is a bound or an average over some assumption, it is what the draw produced.

The rule behind those numbers is short. Two directions with n non-zero entries scattered over d positions share about n squared over d positions on average. Each shared position contributes plus or minus one to a reading whose natural size is n, so the expected size of the overlap is about n over d.

expected overlap ≈ n / d

At four non-zero entries in fifty positions that says 0.0800 and the measurement is 0.0744; at five hundred positions it says 0.0080 and the measurement is 0.0077. Those are close enough that the rule is worth carrying around.

It stops being worth carrying at both ends, and I would rather report where than let it be quoted where it fails. At eight positions it predicts 0.5000 and the measurement is 0.2994, which is a ratio of 0.5988, so it overstates the interference by nearly half at the narrow end. And if the directions are allowed to fill up instead of staying sparse, it collapses entirely. At fifty positions with all fifty filled it predicts 1.0000, meaning every pair should lie on top of every other, and the measurement is 0.1162.

…

The reason for both failures is the same. The rule counts the shared positions and then treats each one as contributing its full weight, when in fact the sign of a shared position is a coin toss and the shared positions cancel each other. Once there are many of them the cancelling dominates, which is why the measurement falls further and further below the prediction as the directions fill.

It is worth being precise about what near-perpendicularity is buying, because there is a clean statement available and it is stronger than the usual hand-wave. Suppose for a moment the drawn directions really were exactly at right angles to each other and all of the same length. Then multiplying the table of counts by them would be a rotation of the space the rows live in, and a rotation changes no angle between any two rows at all.

Every question anybody wanted to ask of the table would come back identical, and the narrowing would have cost nothing at all.

Nothing so far said the directions had to be mostly zeros. The original statements of this geometry drew every entry from a bell curve, and that works. The reason for four non-zero entries and nothing else is arithmetic in the inner loop. Adding a direction with four non-zero entries touches four numbers, and it touches four whatever the width is, so the reading of the collection does not get more expensive when the positions get wider.

A dense direction touches every position, so the same reading at 2048 numbers a word would cost five hundred times what it costs at four.

The entries being only −1, 0 and +1 removes the multiplication as well. Adding a direction becomes adding and subtracting ones at a handful of addresses, with no floating-point multiply anywhere in the reading.

The question that decides whether this is a compromise is what the sparsity costs in accuracy, and measured over twelve draws at each setting, it costs almost nothing.

Reading across a row, the widest and narrowest settings differ by 0.0056 at 16 numbers and by 0.0055 at 256, which is inside the swing one draw makes. Reading down a column, the same setting goes from 0.1714 to 0.0393 as the width grows. The width is doing all the work, so two non-zero entries can be chosen for the two slot updates they cost per neighbour rather than defended as a compromise.

The honest way to price the shortcut is to build the table it avoids, ask it the same questions, and report the difference. Ask both which words are nearest to flour and the two answers hold the same words in a different order. Five of the fit’s six nearest are among the table’s six nearest, and the two disagree about which is first. The fit says eggs, which the table ranks third; the table says bake, which the fit ranks third.

That is the typical damage and it is mild. The sharper case is a pair the two readings disagree about in kind rather than in degree. Flour and anchor come out at 0.1208 in the table, a small positive number saying the two have a little in common through the words both halves share. In the fit they come out at −0.2437. Nothing about the collection made anchor the opposite of flour; the interference from a few directions that happened to share positions did.

The measurement that prices the width is the same comparison applied to every pair of two subject words at once. Take all 190 of them, read the angle from the whole table, read it from the fit, and average how far apart the two answers are. At 8 numbers a word that gap is 0.3959, which is larger than most of the angles being compared. At 16 it is 0.1441, at 64 it is 0.0542, and at 2048 it is 0.0109.

…

Flour’s whole list of six nearest words is recovered at 64 numbers and not before, which is a more demanding test than the average gap and turns over at a definite place. Below that, at 8 numbers, only two of the six survive.

The line running across that picture is the count of pairs of drawn directions that still share a position, and the reason it is drawn beside the gap is that they fall together. At 16 numbers, 155 of the 253 pairs share one; at 2048, two pairs do, and the gap has fallen by a factor of thirteen.

There is a place where the shortcut is plainly worse than the alternative, and it is not about the projection at all. It is about what gets projected. The sum in Part 2 adds a neighbour’s direction once per occurrence, so a word that turns up beside everything contributes its direction to everything, and the positions of two words that share nothing but their function-word company are pulled together.

On the twenty-four documents the three words carrying no subject have the largest rows in the collection, 40 each against 35 for the largest subject word, and three rows out of twenty-three account for 16.7% of the whole table. A word carrying no subject comes out 0.5064 alike to a word that does, under the fit, where the whole table of raw counts says 0.5173 and a reading that first divides out what frequency alone would explain says 0.2207.

…

The fit inherits the raw table’s number almost exactly, which is what a faithful projection of the raw table should do. The method that builds the table has somewhere to put a repair and this one does not, because there is no moment at which the counts exist as counts to be reweighted. The usual answer is to discard the frequent words before reading, or to let a neighbour further away count less, and both are decisions taken before the reading rather than corrections applied after it.

It would be easy to leave the impression that the shortcut is always the cheap route. On this collection it is not, and the numbers say so.

Building the table needs 529 numbers to exist at once, and the answer needs 368, so the saving in memory is a factor of 1.44 and not worth the trouble. What decides it is how each figure grows. The 2,880 grows with how long the collection is and with how many non-zero entries a direction carries, and stops there. The 529 grows with the square of the vocabulary and the 8,464 grows with the square of the vocabulary times the width, and neither depends on how much or how little text there was.

Part 3 said the interference is exactly the pairs of directions that share a position. That has a consequence worth stating on its own, because it makes this error a different kind of thing from most of the errors on this site.

Which pairs share a position is settled by the draw, before any text is read. So the error it causes is not an error of estimation and does not shrink as the evidence accumulates. Write the same twenty-four documents out twice, and every count doubles; the positions all double with them; and an angle between two positions is unchanged by a common scale.

Measured, the gap against the whole table is 0.14412102749793634 with the collection written once, and at 0.14412102749793634 with it written eight times, and one pair of words comes out at 0.6270095706410385 in both, identical to the last bit.

Reading more text of course changes the counts, and better counts do give better answers. What does not change is the distortion the projection adds on top of whatever those counts say. That is a fixed function of the draw and the width, and the only two things that move it are drawing again and asking for more numbers.

A method that builds the table and squeezes it has a diagnostic built into the squeeze. The directions come out ordered by how much of the table each accounts for, so a reader can look at where those figures fall away and cut there. The rule is a rough one, and it is at least a quantity the fit itself produced.

Here there is nothing of the kind. The width is fixed before the first word is read, every coordinate is as good as every other by construction, and the reading produces no figure that says whether the width was enough. Measured across the widths on this collection the gap falls from 0.3959 to 0.0109 without turning anywhere, so there is no elbow to find even if somebody went looking.

What can be done instead is to fit twice at different widths and see whether the answers agree, which is an external check rather than a reading of the fit. That is worth saying plainly, since it is the practical answer and it costs a second reading of the collection.

Two fits of one collection at one width, differing in nothing but which positions the draw picked, are two different answers. How different is a measurable quantity and it is larger than it is comfortable to admit at the narrow end.

…

Over twenty draws at 8 numbers a word, one pair of cooking words comes back anywhere between 0.0189 and 0.9646, a spread of 0.9457 on a scale that runs from −1 to 1. The same pair over twenty draws at 16 numbers spreads by 0.4032, at 50 by 0.2853 and at 200 by 0.1182. Not one of those differences has anything to do with the collection.

The separation between the two halves holds up much better than any individual pair, which is worth knowing and is the reason the method is usable at all. At 16 numbers the smallest separation any of the twenty draws produced was 0.1735 and the largest 0.8430, and every one of them had the two halves the right way round.

Several inputs leave this method with nothing to work out rather than something approximate to work out, and a few more leave it with a genuine choice whose cost is worth knowing. The table gathers both, with what the mathematics says in each case.