Pointwise Mutual Information

Everything on this page is measured on one corpus, and it is worth knowing what is in it before any score touches it. Twenty-four notes of six words each, twelve about cooking and twelve about sailing. The cooking half is spelled from flour, sugar, butter, eggs, oven, bake, stir, whisk, dough and pan; the sailing half from sail, wind, boat, harbour, anchor, tide, mast, rope, deck and crew.

No word of one half ever appears in the other. What the two halves do share is three words that carry no topic at all, and, the and we, and those three turn out to matter more here than any of the twenty.

That comes to 144 word occurrences over 23 distinct words. The notes are arranged rather than written, so that each note uses five of its topic’s ten words in a rotating order and every topic word therefore keeps the same company as every other. The arrangement matters because it removes any structure inside a half that might be stronger than the difference between the halves, which is what would otherwise be found first and reported as a success.

A second, much smaller corpus turns up wherever the arithmetic has to be followed by hand. It is three sentences, the cat sat, the dog sat and the cat ran, and it has five words and twelve counted neighbourings in all, so every number on the page can be checked with a pencil.

Take the word flour and ask what it keeps company with. Walking the notes and counting every word that falls within five positions of it gives a row of counts, and reading that row from the top is the obvious way to answer the question. It is also wrong in a way that a small corpus makes easy to see.

The word and stood beside flour three times, and so did dough. The word the stood beside flour twice, and so did whisk. By count alone the four are two ties, and there is nothing in the counts to prefer one member of each tie to the other. But and and the served as company 40 times each across the whole corpus, where dough and whisk served as company 25 times each, so a function word had far more chances to fall beside flour and took them.

Suppose the two words had nothing whatever to do with each other. They would still fall near each other sometimes, and how often is a question with an answer. If one word takes a fifth of all the company handed out in the corpus and the other takes a tenth, then a fiftieth of all the pairings would involve both of them by accident alone. Compare what actually happened against that number, and what is left is what the two words have to do with each other.

score(w, c) = log( rate of the pair ÷ (rate of w × rate of c) )

The rate of the pair is how many times the two were counted together over how many pairings were counted in all; the rate of a word is how much of that same total the word took on its own. The division cancels the part of the count that is explained by either word being common, which is precisely the part that let and tie with dough.

The logarithm is what makes the result a quantity you can add and subtract rather than a ratio you have to multiply, and it puts the value at zero exactly where the ratio is one.

The three sentences are the cat sat, the dog sat and the cat ran, and near means the word immediately next door, on either side. From the first sentence, the and cat are neighbours and cat and sat are neighbours. Every pair is counted from both ends, so the row for the records cat and the row for cat records the, and the resulting square is symmetric.

…

The widget above opens on those three sentences, so every cell in it can be checked against the paragraph, and clicking one shows the four numbers behind it. Switch to the twenty-four notes and the same rule is applied at a reach of five, 23 words wide.

Take the and cat. They were counted together twice out of twelve counted neighbourings in all. The word the took three of those twelve on its own, and cat took four. So chance alone, with the two words having nothing to do with each other, would put them together a quarter of a third of the time.

A positive score says the two words were found together more often than their separate rates predict, a negative score says less often, and zero says exactly as often. That last statement is stronger than it sounds. Most quantities on this site have a zero that is a convention or an artefact of where a scale was put; this one has a zero that is a statement about the corpus, namely that the rate of the pair is the product of the two rates, to the last decimal place.

score > 0  more often than chance      score = 0  exactly chance      score < 0  less often

On the twenty-four notes three pairs make the three regions legible. Crew beside deck scores +1.5278, which is the highest score in the corpus, shared with five other pairs of topic words; the two were counted together four times and both are among the words that served as company least. And beside anchor scores +0.0282, which is as close to chance as anything here gets, and it is exactly the reading you would want for a function word against a topic word.

And beside bake scores −0.5108, the lowest in the corpus, which says the two occurred together about three fifths as often as their rates alone would have predicted.

Two questions are worth asking of a whole corpus at once. How many pairs come out above chance and how many below, and how far does the scale reach in each direction? Both are visible when every score is placed on one line.

…

Of the 529 pairs 23 words can form, 280 were actually seen together and have a score. Of those, 224 are above chance and 56 below, so four fifths of what the corpus said is a statement that two words seek each other out. The positive side reaches +1.5278 and the negative side only −0.5108, and that lopsidedness is in the arithmetic rather than in this corpus.

The smallest count a pair can carry and still be on the picture at all is one, so the furthest a score can fall below zero is fixed by how common its two words are, and on a corpus where nothing is very common that is not far. Above zero there is no such squeeze, and two rare words that always occur together can reach a ratio of hundreds.

How high can a score go? The pair can never be counted more often than the rarer of its two words was counted at all, since every one of that word’s occurrences is available for the pair and no more. So the ratio can never exceed one over the larger of the two rates, and the score has a ceiling set by whichever of the two words is commoner.

score(w, c) ≤ −log( the larger of the two rates )

The ceiling is reached exactly when the rarer word occurs nowhere except beside the commoner one. In the three sentences, ran appears once and its only neighbour is cat, so the pair cat and ran attains its ceiling of 1.098612 precisely, and the same ceiling applies to cat and sat, which reaches only 0.405465 because sat also stands beside dog.

The name causes trouble and it is worth spending a paragraph on. Mutual information is a single number describing two whole distributions, and it is the average of the quantity on this page taken over every pair, weighted by how likely each pair is. The score here is one term of that average, before it is averaged, which is what the word pointwise is doing in the name.

mutual information = Σ over every pair of  rate(w, c) × score(w, c)

Two consequences follow. Mutual information cannot be negative, because it is an average that the arithmetic of probability keeps at or above zero, whereas a single term of it can be negative and 56 of them are here. And mutual information is one number for a corpus where this page needs one number for every pair, since the whole purpose is to tell pairs apart.

Church and Hanks warned about the negative side of the scale in the paper that introduced the score, and the argument is about evidence rather than about arithmetic. To observe that two words occur together far more often than chance, you need to see them together a few times, which a modest corpus provides. To observe that two words avoid each other, you need to have seen enough of both words that their absence together is surprising, and that takes far more text.

The lowest score in the whole of the twenty-four notes is −0.5108, and every pair sitting at it was seen together exactly once. That is the shape of the problem. A pair below chance is by definition a pair with few observations, so the very score that says the two words avoid each other is the score computed from the least evidence.

The usual response is to keep the positive half and set everything else to zero, which is what the rest of this page does and what almost every published use of the score does.

kept(w, c) = the larger of  score(w, c)  and  0

On this corpus the clip discards 56 scores. That is a fifth of everything the corpus actually observed, and the values thrown away average −0.2562, so they are not all sitting close to zero where the loss would be small.

…

The bar above splits all 529 pairs three ways. What matters is the middle block and the right one. Both end up holding zero, and after the clip 305 of the 529 cells are zero, which is 57.7% of a table that is about to be handed to something that reads every cell of it.

There is a second cost, and it is not a quantity. After the clip, a cell holding zero can have arrived there two ways. Either the two words were seen together and scored below chance, which is the corpus saying something, or they were never seen together at all, which is the corpus saying nothing. Nothing downstream can tell the 56 from the 249.

That distinction is real and it points in opposite directions. A pair below chance is evidence, however thin, that the two words keep apart. A pair never seen together is the absence of evidence, and on a corpus of 24 notes almost half of every possible pair is in that state, including flour and bake, which are both cooking words and simply never landed within five positions of each other.

Once the clip is in place, a natural knob appears. Subtract a constant from every score before clipping and more of the table goes to zero, so the amount subtracted controls how sparse the result is. This is not an arbitrary invention; word2vec trained against a certain number of drawn negatives is, in effect, factorising this matrix with the logarithm of that number taken off, which is what Levy and Goldberg showed in 2014.

kept(w, c) = the larger of  score(w, c) − s  and  0

The rows under the bar in step 11 are what that costs here. At nothing subtracted, 224 entries survive and the two halves of the corpus come apart by 0.6646. Taking off the logarithm of two leaves 96 entries and 0.5789; taking off 1.0 leaves 64 and 0.4901; and taking off the logarithm of five, which is 1.6094 and larger than every score in the table, leaves nothing at all, so every word ends up pointing nowhere and there is no angle between two words to report.

Look again at where the two rates sit. Both are in the denominator, so a word with a small rate makes the whole ratio large, and the rarest words in a corpus therefore produce the largest scores whatever they do. That is the ceiling of step 8 seen from the other side, and it is a genuine problem, because a word counted twice has an estimated rate that is mostly an accident of which text was collected.

The published repair is to raise every context count to a power below one before turning the counts into rates. Raising to a power below one pulls large numbers down towards small ones, and after everything is renormalised the rare contexts hold a larger share than they did and the common ones a smaller share. The power used is three quarters, which is the same three quarters word2vec uses when it draws its negative samples.

flattened rate of c = count(c)^0.75 ÷ Σ over every word of count^0.75

Here is where I got it wrong, and where writing down the direction before computing it would have left a plausible sentence in place of a true one. Flattening lifts a rare context’s rate. It is easy to read that as lifting a rare context’s score, and I did. The rate is in the denominator, so lifting it pushes the score down.

…

The lines are measured on the twenty-four notes. Flour and whisk, where whisk served as company 25 times, scores +0.6523 unflattened and falls to +0.5933 at the published three quarters. Sugar and the, where the served as company 40 times, scores +0.4336 unflattened and rises to +0.4922. The rare context lost and the frequent one gained, which is the direction the adjustment exists for and the opposite of the one the word lifted suggests.

The same reasoning applies below zero and the widget draws that too. And beside bake was already at −0.5108, and flattening takes it to −0.5242, further below chance, because bake is another of the rarer contexts.

Every count in this table is made from both ends, so the counts are symmetric, and while nothing is flattened the scores are symmetric too. The score of a word given a context and the score of the context given the word are the same number, because the same three quantities appear in both. Flatten one of the two rates and that stops being true.

Measured at the published three quarters, 88 pairs of words come out with two different scores depending on which of the two is read as the word and which as the context, which is 176 of the 224 surviving entries. The largest disagreement is and beside crew, which keeps 0.3057 in one direction and 0.4232 in the other, a gap of 0.1175.

The 2015 paper reported this as the single most useful of its adjustments. On the twenty-four notes it makes things very slightly worse, and both halves of that are worth reporting.

The interesting column is the third rather than the last. Words of different topics come out at 0.0016 with nothing flattened and drift up to 0.0264 as the flattening is pushed, so flattening is pulling the two halves of this corpus together. The reason it can is the three shared words. They are the commonest contexts, so flattening lowers their rates and therefore raises the score of every pair whose context is one of them, and those three columns are the only company a cooking word and a sailing word have in common, so raising them is raising exactly the part of two rows that makes words of different topics look alike.

Nothing so far has produced a position for a word, and yet a description is already there. The row of the table belonging to flour holds one number for every word in the vocabulary, saying how much more than chance flour was found beside that word, and two words can be compared by the angle between their two rows without any further machinery.

That description is 23 numbers wide here and would be four hundred thousand wide on a real vocabulary, which is the first reason to squeeze it. The second is that the row is mostly zero. Flour was never seen beside twelve of the 23 words, so twelve of its 23 numbers carry nothing, and two cooking words that never happened to fall near each other have no direct evidence connecting them at all.

The square of kept scores is broken into directions, each with a size attached, ordered so the first direction accounts for as much of the table as any single direction can. Keeping the first few and discarding the rest gives every word a short list of numbers, and the discarded directions are the ones the table leans on least.

the numbers for word w = (its part of each kept direction) × (that direction’s size)^p

On this corpus the four largest sizes are 6.6440, 6.1406, 2.8430 and 2.8325, so two directions stand well clear of the rest, which is what a table made of two blocks with almost nothing between them would be expected to give. The power p is a choice with no derivation behind it. At p of one, the products of two words’ numbers reproduce the table’s own entries; at p of zero the directions are kept at equal strength; the 2015 paper reports a half as consistently best on word similarity and that is the value the rest of this page uses.

With four numbers a word, the nearest words to flour are bake, sugar, oven, eggs and butter, all five from the cooking half. Averaged across every pair, two words of one topic come out at 0.6732 and a word of each at 0.0086, so the two halves of the corpus have been told apart by something that was never told they existed.

The first of those neighbours is worth pausing on. Flour and bake never once fell within five positions of each other in the whole corpus, so their cell in the table is one of the 249 that never had a score. Four numbers a word place them at a cosine of 1.0000, which is to say the squeeze has concluded they are the same word from the company they each keep separately.

The whole argument for this page is that a count is a poor measure of association and a score is a good one. On a corpus this size that argument loses, on one of the two questions, and it would be dishonest to leave it out.

…

Compare the first row with the third. Reading a word’s raw counts puts two words of one topic at 0.6629 and a word of each at 0.1192, a gap of 0.5438. Scoring those same counts drops the second figure to 0.0292, which is the score doing exactly what it was invented for, since the three shared words are what made the two halves look alike and dividing by their rates removed most of it.

But it drops the first figure as well, from 0.6629 to 0.5228, and the gap narrows to 0.4936. The counts win, at the same width of 23 numbers a word.

What recovers it is the squeeze. Four numbers a word give 0.6732 and 0.0086, a gap of 0.6646, better than either 23-wide reading, and the same ordering holds without the flattening, where the scores alone reach 0.5015 against the counts’ 0.5438.

Three costs are worth naming and all three are numbers. The first is what is lost from the table. The kept scores are 529 numbers, the fitted vectors are 92, and at a width of four the reconstruction misses the table by 0.5668 of its own size. At a width of two it misses by 0.6579, at eight by 0.4542, and only at the full 23 does it reproduce the table exactly.

The second is the collapse. Five pairs of cooking words and five pairs of sailing words come out at a cosine of exactly 1.0000 under four numbers, which means the fit cannot tell them apart at all. Flour and bake are one such pair, and their full rows of scores sit at a cosine of 0.5356, so the squeeze has taken two words that were half alike and declared them identical. That is the price of describing 23 words with four directions, and it is paid whether or not the collapse is noticed.

The third is what it costs to compute. The table is as wide as the vocabulary on both sides, so it holds the square of the vocabulary size whether or not the cells are filled, and breaking it into directions costs the cube. At 23 words that is 529 numbers and no time worth measuring; at four hundred thousand words, which is the vocabulary a published set of vectors covers, the same square would hold a hundred and sixty billion cells, and every implementation at that size holds the filled cells alone and asks a solver for a few directions rather than all of them.

Read those two columns together. A wider fit reproduces the table more faithfully and separates the two halves less well, and at the full width, where the table is reproduced exactly, the halves are barely apart at all. Reproducing the table is not the goal, since the table is mostly substituted zeros; the narrow fits do better precisely because they are unable to reproduce them.

The score is the logarithm of a ratio whose numerator is the rate of the pair. If the two words were never seen together, that rate is zero, the ratio is zero, and the logarithm of zero is not a number. It does not fall off towards a large negative value in any useful sense either; it is undefined, and every implementation has to decide something in its place.

There are three honest choices and each costs something. Put zero there, which is what almost everybody does, and the cell then says the two words are independent, which is a claim the corpus never made and is the same value a pair scoring slightly below chance receives. Leave the cell out, keeping only the pairs that occurred, which is what GloVe does, and the objective then makes no claim about those pairs at all, though nothing downstream that wants a square table can be handed the result.

Add a small count to every cell before dividing, which makes every score defined and makes the rarest pairs the ones the added count moves most.

The size of the decision is what makes it worth stating. On the twenty-four notes, 249 of the 529 cells have no score, so 47.1% of the table is whatever was substituted, and the shortfall grows with the vocabulary rather than shrinking, since the number of possible pairs grows as the square while the number of observed ones grows roughly with the amount of text.

The score rewards rarity, and it does so by design rather than by accident. Both words’ rates sit in the denominator, so two words counted once each that happened to fall beside each other produce the largest score the corpus can express, and no amount of evidence about a common pair can match it.

On the three sentences, cat and ran were counted together once and score 1.098612, while the and cat were counted together twice and score 0.693147. On the twenty-four notes, stir and whisk were counted together four times and score 1.5278, while eggs and oven were counted together six times and score 1.2603. In both cases the pair with fewer observations scores higher, and in both cases the arithmetic is correct.

It is correct and it is not what anyone wants, because a pair seen once is mostly an accident of which text was collected. The usual responses are to drop words below a count threshold before scoring anything, which declines to answer for a rare word rather than answering badly, and to flatten the context rates as Part 4 does, which holds back the pairs whose only distinction is rarity. Neither removes the effect and neither is derived from the definition.

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