GloVe

Everything on this page is fitted to one small corpus, and it is worth knowing exactly what is in it before any method touches it. Twenty-four sentences, twelve about a chef and twelve about an astronomer. The cooking half uses onion, garlic, flour, salt, soup, broth and the rest; the astronomy half uses moon, star, orbit, telescope, comet and nebula.

No content word appears in both halves. What the two halves do share is seven words that carry no topic at all, the, and, with, in, of, into and for, and those seven turn out to matter more here than anything else.

That comes to 216 word occurrences over 37 distinct words. The sentences are ordinary English rather than the nonsense a page about sliding a window can afford, and the reason is that this method reads a table rather than a stream of positions, so a corpus small enough to print is also small enough to check by hand, which is what Part 2 does.

The older way of using a corpus is to count it. Walk along every sentence once, and for each word write down which words turned up within a couple of positions of it. What comes out is a square table with a row and a column for every word, and a word’s row is a description of that word made entirely of company.

row(w)[v] = how often v occurred within reach of w, discounted by how far

The description is complete in a strong sense. Everything the corpus has to say about which words go with which is now in the table, and the corpus can be put away. What has gone is the order and the sentence boundaries, so nothing afterwards can tell which sentence a count came from or which of two words stood first, and the two halves of our corpus are now two shaded blocks with nothing between them.

The newer family never builds that table. It slides a window along the text and, at each position, corrects a few vectors so that a word predicts the words beside it, then starts again from the beginning and does it once more. What it buys is that nothing ever exists which is as wide as the vocabulary squared, so a corpus of billions of words can be walked where it could not be tabulated.

What it never sees is the whole. A correction at one position knows about that position and nothing else, and no step in the procedure asks how often two words co-occurred in all. On our corpus one walk of the text makes 720 readings of a neighbour against a table that has 281 entries; repeat the corpus eight times over and the first number reaches 5,760 while the second stays exactly where it was, since the words and the pairs they form have not changed.

GloVe is what happens when we keep the table and fit it directly. Give every word a short vector. Then ask that the vectors of two words, multiplied together coordinate by coordinate and added up, come out at the logarithm of how often those two words occurred near each other, with a spare number for each word to absorb how common that word is on its own.

w(i) · w̃(j) + b(i) + b̃(j)   should equal   log X(ij)

That is one equation for every pair that ever co-occurred, and the fit is a weighted least squares problem over those equations and nothing else. The name is Global Vectors, and the word global is the claim that the quantity being fitted was computed over the whole corpus rather than a window at a time.

Where the counts on the right come from is Part 2; why the logarithm rather than the count is Part 3; why the equations cannot all count the same is Part 4; and what a walk over them does is Part 5.

Two decisions turn a corpus into a table and neither of them has a right answer. The first is how far near reaches. Count only the word next door and hardly anything co-occurs with anything; count twenty positions away and every word in a sentence co-occurs with every other. The second is whether a neighbour five positions away should count for as much as one standing immediately alongside.

a neighbour d positions away adds 1 / d to the count

The usual answer to the second question, and the one this page uses throughout, is one over the distance, so the word next door counts once, the word two away counts a half and the word five away counts a fifth. That is why these counts are not whole numbers, and it matters much more than it looks, because a count of a half has a negative logarithm and a count of two does not. Part 5 measures what that does.

Take the sentence the chef stirs the soup on its own, with a reach of two. From the first the, at the front, chef is one away and adds a whole count and stirs is two away and adds a half. From chef, both the and stirs are one away and add a whole count each, and the second the is two away and adds a half. Carry on to the end of the sentence and every cell is settled.

…

The widget above starts on that sentence, so every cell in it can be checked against the paragraph. Add the second sentence and the count for the beside chef becomes 3.0, which is the same pair counted twice, while soup beside stirs stays at 0.5 because that pair occurred once. Switching to the whole corpus is the same rule again, thirty-seven words wide.

Thirty-seven words give a table of 1,369 cells, and 281 of them hold anything at all, so 79.5% of it is blank. The counts run from 0.5, whose logarithm is −0.6931, to 16.5, whose logarithm is 2.8034, and every count in the table adds to 552.0. Of the 281 filled cells, 86 are below one, which is 30.6%, and the mean logarithm of a count is +0.2617.

The largest count in the whole table is the beside and, at 16.5. Those two words tell nothing apart, they simply stand beside each other more often than any other pair does, and the equation for that pair would carry more of the objective than any other unless the weighting of Part 4 held it back.

Suppose we want to know what separates chef from astronomer. The obvious move is to ask how often each of them is found beside some probe word, and the raw figures do not answer it. A probe that stands beside both of them, like the, comes out common beside both and tells them apart in no way; a probe that stands beside neither comes out rare beside both and tells them apart in no way either.

What does tell them apart is the ratio of the two figures, since a probe belonging to one word and not the other gives a ratio far from one while a probe belonging to both, or to neither, gives a ratio near one.

P(k | i) / P(k | j)     far from one where k belongs to one word alone

The ratio cancels what the two words share and what neither has, and leaves what separates them. That is the observation the whole method is built backwards from, and it is worth seeing on the running corpus straight away, because on a corpus this small it runs into its own limit at once.

…

Of the 37 words in the vocabulary, exactly one, the, was seen beside both chef and astronomer. Its ratio is 0.7319, near one, which is the ratio correctly reporting that the separates nothing. Eight words were seen beside chef alone, so their ratios would divide by zero and do not exist; three were seen beside astronomer alone, so their ratios are zero; and twenty-five were seen beside neither word, so there is nothing to divide either way.

Asking that some function of the vectors reproduce that ratio, and asking that it depend on the two words only through the difference between their vectors, pins the form down almost completely. Nothing is chosen along the way except the two requirements themselves.

The two spare numbers are doing real work and it is easy to miss what. A word like the occurs beside almost everything, so every count in its row is large. Without a spare number to carry that fact, the dot products in that row would all have to be large, and the would end up close to every word in the table.

The spare number absorbs the part of a count that is explained by how common the two words are on their own, and leaves the dot product carrying only what is particular to the pair.

Each word therefore ends the fit with two vectors and two spare numbers, one of each for its role as the word of a pair and one for its role as the probe. Because the table is symmetric the two vector tables are asked the same question and differ only in where they started, and the published choice is to add them together and report the sum.

the vector reported for word i is w(i) + w̃(i)

If every equation counted the same, the fit would work as hard at reproducing a pair seen once as a pair seen a thousand times, and the pair seen once is mostly an accident of which sentences were collected. So each equation carries a weight, and the weight rises with the count until it stops.

weight(x) = (x ÷ the cap) ^ alpha   below the cap,   and exactly 1 at or above it

The exponent is three quarters in the published rule, which sits between counting in proportion to the count and counting every pair alike, and the paper reports it as the value that worked rather than one derived from anything. On our corpus at the published cap of 100, the smallest count of 0.5 earns a weight of 0.0188 and the largest of 16.5 earns 0.2589, so the commonest pair’s equation counts about fourteen times the rarest one’s.

The weight stops rising at a cap, and above it seeing a pair more often makes its equation no more important than it already was. The reason is the pair at the top of our own table. The commonest pair of words in a corpus is a pair of function words, which is the pair that separates the least, and without a cap it would carry the largest single share of the objective.

…

Slide the cap down and watch the tallest ticks pass under the flat part of the curve. At 7.5, ten pairs reach the cap, every one of them a pair involving the, and the share of the whole objective carried by the single commonest pair falls from 1.90% to 1.08% while the ten commonest fall from 12.65% to 10.77%.

The weighting has two jobs, holding back pairs seen too few times to be evidence and holding back pairs seen so often that they would decide the fit alone. On our corpus it only ever does the first, because the largest count in the table is 16.5 and the published cap is 100, so nothing is common enough to be held back.

Read the middle two rows together. Moving from a weight proportional to the count to the published three-quarter power takes the ten commonest pairs from 17.57% of the objective down to 12.65%, so the flattening is real and it is the whole of what the weighting achieves here. The cap contributes nothing until it is moved below the largest count, which is a setting the paper would never use.

A fit is a number of passes over the pairs. Each pass visits all 281 of them in an order shuffled afresh, and for each one computes how far the current vectors and spare numbers are from the logarithm of that pair’s count, squares it, weights it, and moves the four parameters involved a little way towards agreement.

At the settings this page uses, a width of eight and a reach of two, the summed pair terms fall from 18.9335 in the first pass to 0.5550 in the twenty-fifth. The playground at the top of the page draws that curve for whatever settings are chosen, and the useful habit is to watch the shape rather than the value, since a curve that flattens early usually means the corpus has run out of things to say rather than that the fit has finished.

There is a trap in that curve. Each pass’s total was accumulated while the parameters were moving, since a pair visited early in a pass is scored against different vectors from a pair visited late. So the recorded number is not the objective at any one set of parameters, and it cannot be, unless nothing moved.

Recomputed where the walk actually stopped, the objective on that fit is 0.5148, below the 0.5550 the last pass recorded, and the difference is the parameters having improved during the pass being measured. The two numbers can be made to agree exactly by making the fit stand still. Run one pass at a base step of a millionth of a millionth and the recorded total is 22.1272 and the recomputed objective differs from it by less than a billionth, which is the agreement test for the arithmetic and also the demonstration that the gap in an ordinary fit is entirely the movement.

How large a step should a parameter take? Word counts are so unevenly spread that no single answer suits both a word like the, which occurs sixty-one times here, and a word like oven, which occurs twice, so the published rule gives each parameter its own. Every parameter keeps a running sum of the squares of the slopes it has been handed, and its step is divided by the square root of that sum, so a parameter that has already moved a great deal moves less than one that has barely moved at all.

step = base rate × slope ÷ √(sum of that parameter’s squared slopes so far)

The program the authors released does it slightly differently. It starts every running sum at one rather than at zero, and it adds each new square after taking the step rather than before. On a corpus of billions of words that difference disappears within the first few thousand pairs, because the sums grow far past one and the starting value stops mattering. On a corpus of twenty-four sentences it never disappears at all.

…

The two curves come from one walk, with everything identical except those two lines, so the same counts, the same weights, the same starting vectors, the same shuffled order and the same arithmetic for one pair’s slopes. Measured at the end of all twenty-five passes, the largest amount any slope was divided by under the released rule is 1.0860 and the smallest is 1.0000, and since a running sum only ever grows those are also the extremes over the whole fit, so every step the released rule took was the base rate times the slope to within nine per cent, from the first pass to the last.

Under the accumulating rule the same two figures are 0.0049 and 1.2331, a factor of two hundred and fifty between one parameter and another.

What that costs is not subtle. The accumulating rule takes the objective to 0.5148 and the released rule leaves it at 4.9571, nine times higher, over the same twenty-five passes. At the wider reach and the published width of fifty the two are 0.0334 and 8.8708. And it reaches the answer rather than only the objective, since the accumulating rule separates the two halves of the corpus by 0.1966 and the released rule by 0.0306.

A count below one has a negative logarithm, and the objective asks the dot product and the two spare numbers to reproduce it. How many counts come out below one is decided entirely by the reach, because a neighbour further away contributes a smaller fraction and a pair needs several occurrences before its fractions add past one.

…

At a reach of one nothing is below one, because every neighbour is next door and contributes a whole count, and the fit still fails, since 158 pairs is too little of the corpus to see anything by. At a reach of five more than half the counts are below one and the mean logarithm has gone negative.

The spare numbers ought to absorb that mean and after twenty-five passes they have not. The mean spare number is −0.0169, an order of magnitude too small, and the mean dot product over the pairs that co-occurred is −0.1359, so the negative has ended up in the dot products, which is where the meaning was supposed to be.

At a reach of two the same mean dot product is +0.0510.

The last column is what that does to the answer. At a reach of two all three starts put words of one half nearer to each other than to words of the other, and by a wide margin. At three and at five one start in three comes out negative, which is a fit that has placed cooking words nearer to astronomy words than to each other. The reach that works on this corpus is the one where the fractions have had a chance to add past one and the logarithms are mostly positive.

Asked for the words nearest moon, the fit at this page’s settings answers orbits at 0.9826, then of, then planet, astronomer and orbit, so four of the five come from the astronomy half and the fifth is a function word. Asked for the words nearest chef it answers stirs, then of, then orbits, moon and eclipse, which is one word from the right half and three from the wrong one.

Across every content word in the corpus, 67.3% of the five nearest content words come from the same half. The function words crowd those lists because they occur beside everything and therefore end up near everything, which is the effect the spare numbers exist to remove and only partly do; try the buttons in the playground and the, of and and turn up in most of the lists.

The argument for reading a summary is that the summary stops growing before the corpus does. To see that separately from everything else, repeat the corpus whole, one copy then two then four then eight, which leaves the vocabulary and the set of pairs exactly where they were while doubling how much text there is to walk.

…

What the repetition hides is that on real text the number of distinct pairs does keep growing, only far more slowly than the text does, and that the table itself grows as the square of the vocabulary whether or not the cells are filled. Here it is 1,369 numbers, of which 1,088 are zero, against the 296 numbers of the fitted vectors.

Thirty-seven words is small enough that holding a square array is the obvious thing to do; four hundred thousand words is not, and every implementation at that size holds the filled cells alone.

There is an obvious alternative to fitting the table, which is reading it. Two words can be compared by taking their whole rows of counts and measuring the cosine between them, which needs no fit, no starting draw, no step rule and no seed. On this corpus that alternative wins one of the two questions the page has been asking, and it would be dishonest to leave that out.

…

Asked for the five words nearest onion, the raw rows answer salt, garlic, butter, pepper and flour, all five from the cooking half. The fitted vectors answer gravity, flour, into, garlic and oven, so the nearest word of all comes from the wrong half. Asked of every content word in turn, and counting only content words on either side so that the seven shared words cannot muddy it, the raw rows put 74.7% of the five nearest in the same half against the fit’s 67.3%, and they do it with 37 numbers per word where the fit uses 8.

On the other question the ordering reverses. Averaged over all pairs, the fit puts words of one half 0.1966 further apart from words of the other than from each other, and the raw rows manage 0.1404. The raw rows lose there because every row is dominated by the seven shared words, so all thirty-seven rows already point broadly the same way and the mean cosine across the halves comes out at 0.4756 rather than near zero.

The objective is a sum over pairs, and the quantity each term compares against is the logarithm of a count. The logarithm of zero is not a number. So a pair that never co-occurred has no term at all, the sum runs over the pairs that were seen, and it says nothing whatever about the rest.

That is a different kind of silence from a term whose target is zero. A term with a target of zero would be a statement, namely that those two words should have a dot product cancelling their two spare numbers; a missing term is no statement, and the fit is free to place those two words anywhere the other terms leave room for.

On this corpus 1,088 of the 1,369 cells are empty, so 79.5% of the pairs the vocabulary can form are pairs the objective never mentions, and every judgement a fitted table makes about one of them is a side effect of the pairs it did mention.

The weight is what makes the omission consistent rather than ad hoc. The weight of a count of zero is zero, so writing the sum over all pairs of words and writing it over the filled cells give the same number, and the missing logarithms are never evaluated. That is a tidy way of stating the omission rather than a way of repairing it, since the objective still has 281 terms however it is written down.

Two decisions are made before the first equation exists, how far near reaches and what a neighbour at a distance is worth, and after that the fit reads their consequences rather than the corpus. Nothing computed during the fit can revisit either one, and no quantity the fit produces turns over as the reach passes a good value.

Both are genuine choices with something measurable turning on them. The reach settles what fraction of the counts fall below one and so the sign of most of the logarithms, which Part 5 measured as none of them at a reach of one and 51.9% of them at a reach of five, with the answer failing at both ends.

The distance rule settles whether a count is a whole number at all, and a rule giving every position one full count would remove every fraction and with it every negative logarithm, at the cost of treating a word five away as the equal of a word next door.

The objective is a sum of squares in quantities that multiply each other, so it is not convex, and the walk visits the pairs in a shuffled order and arrives at a local answer. A fit therefore inherits two kinds of arbitrariness at once, the draw it started from and the table it was handed, and neither is visible in the answer it returns.

Worse for anyone hoping to compare two fits, the objective cannot distinguish a set of vectors from a rotation of it. Turn every vector in both tables by the same rotation and every dot product is unchanged, so every term of the objective is unchanged, so the rotated answer is exactly as good. Individual coordinates therefore carry no meaning at all, and the third coordinate of one fit has no relation to the third coordinate of another.

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