Chapter 7Count Vectors, PPMI, and SVD

Two repairs

Chapter 6 left us with a working idea and two complaints about it.

The idea is this. Represent a word by a row of a co-occurrence matrix $M$. Read similarity of meaning as the cosine between rows.

The complaints are these. The raw counts in $M$ measure frequency more than association. And the matrix is impossibly wide, with one column per vocabulary word and almost all entries zero.

This chapter is the classical repair of both. It is the pipeline that carried distributional semantics for two decades before neural embeddings. Reweight the counts so they measure genuine association. Then factor the matrix, so tens of thousands of sparse dimensions collapse into a few hundred dense ones.

From counts to association: PMI

Why are raw counts misleading? Because the most frequent words co-occur with everything.

The word the sits next to dog, car, idea and every other noun, thousands of times. A raw count credits the with enormous association to words it is merely adjacent to by grammatical accident.

What we want is a different quantity. Not how often two words co-occur, but how much more often than we would expect if they were independent.

That ratio is pointwise mutual information:

$$\begin{equation} \operatorname{PMI}(w, c) \;=\; \log_2 \frac{p(w, c)}{p(w)\,p(c)}, \label{eq:pmi} \quad\text{(7.1)} \end{equation}$$

where $p(w,c)$ is the probability that $w$ and $c$ co-occur, and $p(w)$ and $p(c)$ are their individual probabilities, all estimated by counting.

The denominator is what we would expect under independence. The numerator is what we observe. PMI takes the logarithm of their ratio, in bits.

The interpretation is clean. A PMI of $0$ means the words are exactly independent, since $p(w,c) = p(w)p(c)$. A positive value means they co-occur more than chance. A negative value means less than chance.

One number will fix the scale in your mind. Two words that co-occur twice as often as independence predicts have a PMI of $\log_2 2 = 1$ bit. Ten times as often gives $\log_2 10 \approx 3.32$ bits.

The estimate is a pure count computation. With a corpus of $N$ tokens,

$$\operatorname{PMI}(w,c) \;=\; \log_2 \frac{\operatorname{count}(w,c)\;N}{\operatorname{count}(w)\,\operatorname{count}(c)}.$$

Take a pair seen together $10$ times in a corpus of $10^{6}$ tokens. Each word occurs $1{,}000$ times on its own. The score is $\log_2\!\big(10 \cdot 10^{6} / (1000 \cdot 1000)\big) = \log_2 10 \approx 3.32$ bits. That is a strong, above chance association.

The word the never contaminated the answer. Its large marginal $p(c)$ sits in the denominator and cancels its large joint count.

Try it yourself. code/worked_examples/weighting.py pmi tabulates five pairs against what independence predicts. One is above chance, one is exactly at chance and scores zero, and one is below chance and gets clipped by PPMI.

Run it in ColabNotebookSource

Keep the positives: PPMI

PMI has a weakness at the other end. A negative PMI claims that two words co-occur less than chance.

To trust such a claim you need to have seen the pair often enough to trust its rarity. In a sparse matrix, most pairs are seen never or once. So negative values are mostly noise.

The standard remedy is to clip them:

$$\begin{equation} \operatorname{PPMI}(w, c) \;=\; \max\!\big(\operatorname{PMI}(w, c),\; 0\big), \label{eq:ppmi} \quad\text{(7.2)} \end{equation}$$

which is positive pointwise mutual information.

A PPMI weighted matrix keeps only the above chance associations and sets everything else to zero. That has a happy side effect. The matrix stays sparse, and so storable, while now measuring association rather than frequency.

One bias survives the clipping. It is worth naming, because it returns in the next chapter in disguise.

PMI is inflated for rare words. A word seen only a handful of times has a tiny marginal $p(w)$ in the denominator. So any co-occurrence at all produces a large PMI.

The common fix is to smooth the context distribution. Raise its counts to a power less than one, $p_\alpha(c) \propto \operatorname{count}(c)^{\alpha}$ with $\alpha \approx 0.75$. This lifts the probability of rare contexts and so lowers their PMI.

Remember that exponent, $0.75$. Chapter 9 introduces word2vec’s negative sampling. It draws negative examples from a distribution smoothed by exactly the same power. That is not a coincidence. It is a sign that the two methods compute closely related things.

Two count models: HAL and COALS

Before neural embeddings, several complete systems were built on the ideas of this chapter. Two are worth knowing properly. Their design choices are the choices anyone building a count model has to make. And the second was the strongest count based model of its era.

HAL

Hyperspace Analogue to Language makes three decisions that set it apart.

A ramped window.

Plain counting treats every word in the window alike. A neighbour ten words away then counts as much as the word next door. HAL weights by closeness instead.

Slide a window of width $W$ along the corpus. For a target at position $i$ and a context word at position $j$, the weight is

$$\begin{equation} \operatorname{w}(i, j) \;=\; W - |i - j| + 1 . \label{eq:hal-ramp} \quad\text{(7.3)} \end{equation}$$

The adjacent word scores the full $W$, and the weight ramps down to $1$ at the edge of the window. Lund and Burgess used $W = 10$, so the neighbour scored 10 and the tenth word away scored 1.

Two scans, and why the matrix is asymmetric.

HAL passes over the corpus twice, in opposite directions, and keeps the two results apart.

The left to right scan takes each word as the key and ramps weights onto the words that follow it. The right to left scan reverses the corpus and does the same, which ramps weights onto the words that precede it.

Both passes write into one matrix, under the convention that $M[a, b]$ holds the weight of $b$ occurring before $a$:

$$\begin{equation} M[a, b] \;=\; \sum_{\substack{i \,:\, s_i = a}} \; \sum_{\substack{j < i \,:\, s_j = b \\ i - j \le W}} \big(W - (i - j) + 1\big). \label{eq:hal-matrix} \quad\text{(7.4)} \end{equation}$$

Now read that definition carefully. $M[a, b]$ counts $b$ before $a$. But $M[b, a]$ counts $a$ before $b$. Those are different events, so in general

$$\begin{equation} M[a, b] \;\neq\; M[b, a]. \label{eq:hal-asym} \quad\text{(7.5)} \end{equation}$$

The matrix is asymmetric, and deliberately so. Here is the same pair read in both directions, taken from the worked matrix below:

The first two pairs are lopsided to the point of being one sided. Horse precedes raced in this corpus and never follows it, so one cell holds 5 and its mirror holds 0. The third pair is nonzero both ways and still unequal, because the and horse occur near each other at different distances depending on which comes first.

A symmetric matrix could not record any of that. It would average the two directions away and report only that the words occur near each other.

Word order carries grammar. Dog bites and bites dog are different facts, and a symmetric window throws the difference away. HAL keeps it, which is what the two scans are for.

The worked matrix.

Take the corpus used in the lectures,

with $W = 5$. The scan is a ramp descending from each key word:

Apply Equation (7.4) everywhere and the full matrix is:

Two cells check by hand. Row raced says horse scores 5, because horse sits one word before it. In the same row the scores 4, because the first the sits two words before.

Row barn is the interesting one. The occurs twice in the window, once at distance 1 and once at distance 5, so it collects $5 + 1 = 6$. A repeated context word accumulates every time it appears. Miss that and your matrix is wrong.

A doubled vector, then pruned.

The asymmetry is precisely why a word needs two vectors, not one.

Take the word $a$. Its row $M[a, \cdot]$ says what came before it. Its column $M[\cdot, a]$ says what came after it. Those are the two scans, recovered from the one matrix.

A symmetric model would have nothing to concatenate, because row and column would be identical. HAL concatenates them, giving $2|V|$ dimensions for a vocabulary of $|V|$.

That is enormous and mostly uninformative, so HAL keeps only the columns with the highest variance, typically a few hundred. A column that is nearly constant across words cannot distinguish them, so it goes.

Similarity is then a Minkowski distance rather than a cosine,

$$\begin{equation} d(x, y) \;=\; \Big(\textstyle\sum_i |x_i - y_i|^{\,r}\Big)^{1/r}, \label{eq:minkowski} \quad\text{(7.6)} \end{equation}$$

with $r = 2$ giving ordinary Euclidean distance.

That pruning step is a crude ancestor of the SVD above. Both cut dimensions. The SVD builds new dimensions that capture variance. HAL merely selects existing dimensions that already carry it.

The flaw HAL exposed.

Lund and Burgess were clear about the weakness, and it is the reason COALS exists. Raw weighted counts still track frequency.

Take two unrelated words $t_1$ and $t_2$ with $p(t_1) \approx p(t_2)$. Their vectors will hold entries of similar magnitude simply because both words are about as common, and any distance measure will call them close. Now take two genuinely related words with $p(t_1) \ll p(t_2)$. Their magnitudes differ wildly, and the measure will call them far apart.

Similar frequency does not mean similar meaning. That is the problem a normalised statistic has to solve.

Try it yourself. code/worked_examples/hal.py builds the matrix above and lists the most lopsided pairs, so you can see the asymmetry rather than take it on trust. --vectors shows why a word needs its row and its column, and --window shortens the ramp.

Run it in ColabNotebookSource

COALS

Correlated Occurrence Analogue to Lexical Semantics keeps the ramped window and changes almost everything else.

Correlation instead of counts.

This is the central move, and it is the answer to the flaw HAL exposed.

COALS converts each raw count into a correlation between the word and the context, computed over the whole matrix. Write $w_{a,b}$ for the count in row $a$ and column $b$, and let $T$ be the grand total of every entry. Then

$$\begin{equation} r_{a,b} \;=\; \frac{T\,w_{a,b} \;-\; \sum_{j} w_{a,j} \, \sum_{i} w_{i,b}} {\sqrt{\;\sum_{j} w_{a,j}\Big(T - \sum_{j} w_{a,j}\Big)\; \sum_{i} w_{i,b}\Big(T - \sum_{i} w_{i,b}\Big)}} , \qquad T = \sum_{i}\sum_{j} w_{i,j}. \label{eq:coals-corr} \quad\text{(7.7)} \end{equation}$$

The numerator is the same comparison PMI makes. $T\,w_{a,b}$ is what we observed, scaled up, and the product of the two margins is what independence predicts. The denominator normalises by how much each margin could vary, which puts every entry on the same $[-1, 1]$ scale no matter how common the words are.

That last part is what HAL lacked. A frequent word now has a large margin in both numerator and denominator, so being common stops earning a large score.

The worked matrix.

The lectures use a deliberately silly corpus:

A ramped window of size 4 over 13 word types gives a count matrix whose grand total is $T = 537$. Four row and column sums we will need: a sums to 80, if to 31, woodchuck to 75, and wood to 81 down its column and 71 across its row.

Now compute three cells with Equation (7.7).

The first cell is the instructive one. A never sits next to itself, so $w_{a,a} = 0$, and the correlation goes firmly negative. The statistic has noticed an avoidance, not merely an absence.

The second and third are positive, and they say that a genuinely attracts if and woodchuck. A is the most frequent word in the corpus. Under raw counts it would have dominated every row. Here it does not.

Negatives discarded, positives damped.

Two steps finish the job:

$$\begin{equation} \operatorname{COALS}(a,b) \;=\; \begin{cases} \sqrt{r_{a,b}} & \text{if } r_{a,b} > 0 \\ 0 & \text{otherwise.} \end{cases} \label{eq:coals-clip} \quad\text{(7.8)} \end{equation}$$

Negatives go to zero for the same reason PPMI clips negative PMI. There is rarely enough evidence to trust an avoidance claim, and zeros keep the matrix sparse.

The square root damps what survives. It pulls in the large values, so a few strong pairings cannot dominate a vector. Applying it to our three cells, $-0.175$ becomes $0$, while $0.121$ becomes $0.347$ and $0.103$ becomes $0.321$. Those two are far closer after the root than before it.

Symmetric, then optionally reduced.

COALS drops HAL’s direction distinction, so the matrix stays symmetric and half the size. It also discards all but the $m$ columns for the most common open class words, with $m = 14{,}000$ in the original paper. It can then be run through an SVD, as Section 1.4 describes, to get dense vectors.

Rohde and colleagues reported that this beat both HAL and Latent Semantic Analysis on word similarity judgements. The gain came mostly from the correlation step and the square root. The reweighting mattered more than the reduction, which is a useful thing to know.

Try it yourself. code/worked_examples/coals.py prints all three steps on this corpus, reproducing the tables above. --cell a a shows the arithmetic for one cell the long way, which is the quickest route to believing the formula.

Run it in ColabNotebookSource

What they share

Set the three models side by side and the family resemblance is plain.

Every one of them does the same four things. Count co-occurrences. Reweight them into association rather than frequency. Optionally compress. Read similarity as an angle. They disagree about the statistic and about whether order matters. They agree about the shape.

That shape is what the next chapter abandons. Not the distributional hypothesis, which survives untouched, but the idea that you must build the matrix at all.

From sparse to dense: SVD

The reweighted matrix is better but no smaller. It is still as wide as the vocabulary.

The second repair compresses it, using the workhorse of linear algebra, the singular value decomposition. Any real matrix $M$ can be factored as

$$\begin{equation} M \;=\; U\,\Sigma\,V^{\!\top}, \label{eq:svd} \quad\text{(7.9)} \end{equation}$$

where $U$ and $V$ have orthonormal columns, and $\Sigma$ is diagonal with non negative entries $\sigma_1 \geq \sigma_2 \geq \cdots \geq 0$ in descending order. Those entries are the singular values.

The singular values measure how much of the matrix’s variance each new dimension accounts for. $\sigma_1$ names the single direction along which the data vary most. $\sigma_2$ names the next. And so on.

Because they decay, most of the structure lives in the first handful of dimensions. The long tail contributes mostly noise.

That suggests an obvious compression. Keep only the top $K$ singular values and their vectors. Discard the rest.

Choosing K by contribution

Which raises the practical question. How large should $K$ be?

The singular values answer it themselves. Each one carries a share of the total, and that share is its contribution ratio:

$$\begin{equation} r_i \;=\; \frac{\sigma_i}{\sum_{j} \sigma_j}. \label{eq:contribution} \quad\text{(7.10)} \end{equation}$$

What you actually want is the running total. The cumulative contribution of the first $K$ dimensions is

$$\begin{equation} R_K \;=\; \frac{\sum_{i=1}^{K} \sigma_i}{\sum_{j} \sigma_j}. \label{eq:cumcontribution} \quad\text{(7.11)} \end{equation}$$

Now $K$ is a decision you can make on evidence. Pick the smallest $K$ whose $R_K$ crosses a threshold you are willing to state, commonly $0.8$ or $0.9$. Or plot $r_i$ against $i$, look for the elbow where the curve flattens, and cut there.

A spectrum you can read.

Take a small co-occurrence matrix over eight words and eight contexts. Four of the words are animals, four are vehicles, and the two groups share no context at all. Here is what the SVD returns.

The share column holds two values near $39\%$, then a fall off a cliff to $10.5\%$, then a long dwindle. The elbow is unmistakable, and it is between rows 2 and 3.

So the elbow says $K = 2$, holding $77.6\%$ of the total. Push to $K = 3$ and you buy another $10.5\%$. Every dimension after that buys almost nothing.

Now notice what $K = 2$ means. The matrix really does have two hidden groups, animals and vehicles. Nobody told the decomposition that. It read the number of underlying themes off the data, and the contribution ratio let us see it without ever looking at the words.

The criteria can disagree.

Watch what a threshold does here. An $80\%$ rule would reject $K = 2$, because $77.6\%$ falls just short, and take $K = 3$ instead. The elbow was right and the threshold was wrong, by $2.4$ percentage points.

That is not an argument against thresholds. It is a warning that $0.8$ and $0.9$ are conventions, not findings, and the spectrum should be consulted before either is trusted. When the two criteria disagree, the elbow is usually telling you something about the data and the threshold is telling you about itself.

Real corpora rarely produce a cliff this clean. There the threshold earns its keep, because there is no elbow to see. The point is to make the choice on a stated criterion rather than a hunch, and to say which criterion you used.

One convention to watch.

Some authors define contribution with squared singular values, $\sigma_i^2 / \sum_j \sigma_j^2$, because $\sigma_i^2$ is the variance along that direction. It is the same idea and it gives larger numbers, since squaring exaggerates the lead of the top values. The same spectrum reads $49.2\%$ for the first dimension and $94.9\%$ for the first two.

That matters more than it looks. Under the squared convention an $80\%$ threshold now picks $K = 2$, agreeing with the elbow, where the unsquared one picked $K = 3$. The convention you choose changes the $K$ you get. Both are in use. State which one you used.

The resulting rank-$K$ matrix has a strong guarantee behind it. By the Eckart-Young theorem it is the best possible approximation of $M$ by a matrix of rank $K$. No other $K$-dimensional representation loses less.

Each word is now a dense vector of $K$ numbers. A few hundred, say, in place of tens of thousands.

The truncation is not merely thrift. Throwing away the noisy tail forces words that behaved similarly to collapse onto shared latent dimensions. So the compressed vectors generalise. Two words can end up close even when their raw rows overlapped only partially.

A term matrix with a truncated SVD is Latent Semantic Analysis . For years, that was how one turned a corpus into usable word and document vectors.

Try it yourself. Two scripts cover this section. code/worked_examples/svd_rank.py prints the spectrum table above; --squared switches convention and --threshold moves the cut, so you can watch the two criteria agree and disagree. code/worked_examples/svd.py then shows what the chosen $K$ buys. Run it with --k 2 and dog scores $1.000$ against cat and $0.000$ against car, in two dimensions.

Run it in ColabNotebookSourceRun it in ColabNotebookSource

The ceiling of counting

Step back and see what the pipeline achieves. From nothing but a corpus and some counting, PPMI plus SVD produces dense, low dimensional vectors whose geometry encodes real semantic similarity. The procedure is unsupervised and principled, and it works.

But it has a ceiling. At bottom it is still a count and factor procedure over a fixed matrix.

Three consequences follow. The matrix must be built in full before it can be decomposed. Adding fresh text means rebuilding and re-factoring. And the SVD is one global linear compression, blind to anything that is not a direction of variance in the count statistics.

So a natural question arises. Could we get the same dense vectors without ever building the giant matrix, by learning each word’s vector directly from its contexts?

Chapter 9 answers it with word2vec. word2vec turns out to be almost the same object, seen from the other side. It can be shown to be implicitly factorising a shifted PMI matrix. The learning of the next chapters and the counting of this one are two routes to one destination.

Learning needs a learning machine, though. It needs a way to adjust parameters to reduce an error, which counting never required. Chapter 8 builds exactly that machine, the neural network. Then Chapter 9 turns it loose on the distributional hypothesis.

From here on, meaning as geometry is fixed. What changes is that we stop computing the geometry and start training it.

Further reading.

is the original Latent Semantic Analysis paper. on HAL and on COALS are influential count based models with different weighting choices. The semantic space formalism underlying all of them is set out by . Manning, Raghavan and Schütze cover matrix decompositions for retrieval and their latent semantic interpretation.