Pointwise mutual information and PPMI

Start with numbers. In the small Term-context matrix used throughout this part, the word information accounts for 7703 of the N = 11716 counted word-context pairs, and the context data for 5673 of them. If the two words had nothing to do with each other, how often would you expect to see them together? The full table, with every row and column sum, is in the counts-to-probabilities section below.

Independence answers that. If knowing one word tells you nothing about the other, the probability of the pair is just the product of the separate probabilities: P(information) × P(data) = .6575 × .4842 = .3184. So about 31.8% of all pairs should be (information, data) by chance alone. The observed share is 3982 / 11716 = .3399. The ratio of observed to expected is 1.0676: the pair occurs only 6.8% more often than chance, and log2 1.0676 = .0944 bits. Compare cherry and pie: there the ratio is 20.8, and the log is 4.38 bits. That number is pointwise mutual information.

Read the fraction one piece at a time. The numerator is what actually happened: how often the pair appeared together. The denominator is what independence predicts, because under independence P(x, y) = P(x) P(y). The ratio therefore says how many times more often the pair occurs than chance, and the base-2 logarithm turns that ratio into bits. A ratio of 1 gives 0 bits (independent), a ratio above 1 gives a positive score (attraction), and a ratio below 1 gives a negative score (avoidance). Each extra bit means the pair is twice as over-represented.

Where the measure comes from

Church and Hanks (1989, journal version 1990) brought the measure to lexicography. They estimated P(x, y) by counting how often x is followed by y within a window of w = 5 words, and they read the score exactly as above: well above zero for genuine association, near zero for no relation, well below zero for words in complementary distribution. Their rough rule of thumb was that pairs with a score above 3 tend to be interesting, and they ignored pairs seen 5 times or fewer because the ratio was unstable, an early sign of the rare-event problem later in this part. One subtlety a PhD reader should notice: because their count encoded word order (x before y), their association ratio was not symmetric. The term-context version on these slides counts a symmetric window, so PMI(w, c) depends only on which pair you pick.

Suppose two words each have probability 10^-6, which is typical of most of the vocabulary. Independence predicts that they appear together with probability 10^-12. To say with confidence that they appear together less than that, you must be able to estimate probabilities well below 10^-12, which takes a corpus on the order of trillions of pairs. With a corpus of a few million tokens you will simply never see them together, and you cannot tell "these words avoid each other" apart from "these words never happened to meet".

That is the first reason negative PMI is unreliable: the evidence needed to estimate below-chance co-occurrence grows with the rarity of the words, and for most word pairs it is never available. The second reason is about evaluation: it is not clear that people can even judge "unrelatedness" reliably, so there is no good gold standard to check negative scores against. The practical answer, used since Church and Hanks and later Dagan and colleagues (1993) and Niwa and Nitta (1994), is to keep only the positive side.

Positive PMI keeps the attraction signal and floors everything else at zero. It has a welcome side effect. A pair that never co-occurs has P(w, c) = 0, so its Pointwise mutual information is log2 0 = -∞, a value that would wreck any later arithmetic. Clipping maps it cleanly to 0. In the slide table this is exactly what happens to strawberry/computer and strawberry/data, both with count 0. The result is a sparse vector per word: long, mostly zero, with a few positive entries for the contexts that really characterise it.

Empirically the choice pays off. Levy, Goldberg and Dagan (2015) report that Bullinaria and Levy (2007) found PPMI outperforms plain PMI on semantic similarity tasks, and PPMI became the default count-based baseline against which neural embeddings were later compared.

Everything so far needs three probabilities per cell: the joint P(w, c) and the two marginals P(w) and P(c). All three come from one count matrix F. Here is the matrix the slides use, taken from SLP3, whose counts come from Wikipedia: four target words as rows, five context words as columns, with the row and column sums added.

Add every cell and you get the grand total N = 11716. Each probability is then a share of that one total. The joint probability of a cell is the cell divided by N. The marginal probability of a target word is its row sum divided by N, and the marginal probability of a context is its column sum divided by N.

Because the joint and both marginals come from the same matrix and the same N, they are consistent: each row of joint probabilities sums to its row marginal, each column to its column marginal, and everything sums to 1. SLP3 is candid that this "pretends" the five listed contexts are the only ones in the world. In a real system the matrix has tens of thousands of columns and the same recipe applies unchanged.

With the three probabilities in hand, one cell of the Pointwise mutual information matrix is a division and a log. Work it once by hand for information/data, then notice a shortcut that skips the rounding entirely.

Repeat for every cell and you get the full PMI matrix below. Every Positive PMI value on slide 58 is this matrix after clipping; SLP3 quotes PMI(cherry, computer) = -6.7 in its figure caption as an example of a large negative value that PPMI discards.

Now read the PPMI matrix as a set of word vectors. The fruit rows light up only on pie and sugar; the technology rows only on computer, data and result. The two groups share no non-zero dimension, so the cosine similarity between cherry and digital is exactly 0, while cherry and strawberry have a cosine of about 0.96. The raw counts were noisier: cherry co-occurs with computer and data a few times, and in a full-size matrix such incidental counts, scaled by frequent contexts, blur every row. PPMI vectors are still long and sparse; the second half of this lecture learns short dense vectors instead.

Add one more row and one more column to the slide table: a word w and a context c, each seen exactly once, and that once together. The shortcut gives PMI = log2(1 × 11716 / (1 × 1)) = log2 11716 = 13.5 bits. That is more than double strawberry/sugar (5.51), from a single observation that may be a typo or a coincidence. One accident beats thousands of genuine co-occurrences.

The mechanism is the denominator. When a context is rare, P(c) is tiny, so even one co-occurrence produces a large ratio. Levy, Goldberg and Dagan (2015) call this Pointwise mutual information's Achilles' heel, citing Turney and Pantel (2010): a word's highest-scoring dimensions become obscure contexts it met once or twice, and since similar words rarely share those accidents, their vectors look less alike under cosine than they should. Clipping does not help, because Positive PMI only touches negative values and this bias inflates positive ones.

Two fixes

1. Give rare contexts a little more probability. If P(c) for a rare context is nudged upward, its PMI falls. This is the alpha weighting of the next concept.
2. Add-k smoothing. Add a small constant k to every count before computing probabilities, exactly as in the n-gram language models of Lecture 03. Slide 59 names the simplest case, add-one smoothing, which is k = 1 and lowers strawberry/sugar from 5.51 to 5.41. SLP3 gives k = 0.1 to 3 as common choices, and notes that the larger the k, the more the non-zero counts are discounted. A count of 1 becomes 3 with k = 2, tripling, while a count of 442 barely moves. On the slide table, add-2 lowers strawberry/sugar from 5.51 to 5.31 and leaves the overall pattern intact.

The oldest fix is the bluntest. Church and Hanks simply discarded pairs seen 5 times or fewer. Frequency cut-offs of that kind are still common in collocation tools.

Take two contexts with P(a) = .99 and P(b) = .01. Raising both to 0.75 and renormalising roughly triples the rare one, so every Pointwise mutual information involving b falls by about 1.6 bits. The worked example below shows each step.

The exponent Alpha-weighted context probability flattens the context distribution. Because 0 < α < 1 shrinks large counts proportionally more than small ones, after renormalising P_alpha(c) > P(c) for rare contexts and P_alpha(c) < P(c) for frequent ones. A larger denominator means a lower PMI, so rare contexts lose exactly the inflated advantage the previous concept described, and Positive PMI computed with P_alpha(c) keeps fewer spurious rare dimensions. Only P(c) changes; P(w, c) and P(w) stay as before.

On the slide table the effect is easy to predict. Sugar, with only 61 counts, goes from P = .0052 to .0148, so strawberry/sugar drops from 5.51 to 4.01 and cherry/sugar from 3.30 to 1.80. The frequent context computer goes from .4265 to .4019, so digital/computer actually rises from 0.18 to 0.27. Result goes from .0404 to .0686, which pushes information/result from 0.28 to a PMI of -0.48, so its PPMI becomes 0.

Why 0.75, and the road to word2vec

The number is borrowed. Mikolov and colleagues (2013) found that drawing negative samples for word2vec from the unigram distribution raised to the 3/4 power, U(w)^(3/4) / Z, worked significantly better than either the plain unigram or the uniform distribution. Levy, Goldberg and Dagan (2015) carried the trick over to count-based PMI as "context distribution smoothing", tested α ∈ {1, 0.75}, and found that it alleviates PMI's bias toward rare words and consistently improves performance across tasks, methods and configurations.

The connection runs deeper than a shared constant. Levy and Goldberg (2014) showed that Skip-gram with negative sampling with k negative samples implicitly factorizes a word-context matrix whose cells are PMI(w, c) - log k. The sparse analogue is shifted PPMI, max(PMI(w, c) - log k, 0), which they found competitive on word similarity. So PPMI and word2vec are close relatives: Negative sampling is, in a precise sense, a smoothed and compressed way of estimating the same quantity you just computed by hand. Keep this in mind for the skip-gram parts that follow.