Chapter 7Count Vectors, PPMI, and SVD

Two repairs

Chapter 6 left us with a working idea and two complaints about it. The idea is to represent a word by a row of a co-occurrence matrix $M$ and read similarity of meaning as the cosine between rows. The complaints are that the raw counts in $M$ measure frequency more than association, and that the matrix is impossibly wide, with one column per vocabulary word and almost all entries zero.

This chapter is the classical repair of both, and 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

Raw counts are 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, so 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 altogether, 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 and the numerator is what we observe, so PMI takes the logarithm of their ratio, measured in bits.

The interpretation is clean. A PMI of $0$ means the words are exactly independent, since $p(w,c) = p(w)p(c)$, while a positive value means they co-occur more than chance and a negative value 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, and ten times as often gives $\log_2 10 \approx 3.32$ bits.

The estimate is a pure count computation, so 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, where 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, which is a strong and clearly above chance association.

The word the never contaminated the answer, because 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, because 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, and 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, which has a happy side effect: the matrix stays sparse and therefore storable, while now measuring association rather than frequency.

One bias survives the clipping, and it is worth naming because it returns in the next chapter in disguise. PMI is inflated for rare words, since 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 by raising its counts to a power less than one, $p_\alpha(c) \propto \operatorname{count}(c)^{\alpha}$ with $\alpha \approx 0.75$, which lifts the probability of rare contexts and so lowers their PMI.

Remember that exponent of $0.75$, because Chapter 9 introduces word2vec’s negative sampling, which draws negative examples from a distribution smoothed by exactly the same power. The two methods compute closely related things, and the shared exponent is the clue.

Two count models: HAL and COALS

Before neural embeddings, several complete systems were built on the ideas of this chapter, and two are worth knowing properly, because 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 (Lund and Burgess 1996) makes three decisions that set it apart, and the first of them concerns the window.

Plain counting treats every word in the window alike, so a neighbour ten words away counts as much as the word next door, whereas HAL weights by closeness instead. Slide a window of width $W$ along the corpus, and for a target at position $i$ with 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.

The second decision is to pass over the corpus twice, in opposite directions, keeping the two results apart. The left to right scan takes each word as the key and ramps weights onto the words that follow it, while the right to left scan reverses the corpus and 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$, whereas $M[b, a]$ counts $a$ before $b$, and 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, because horse precedes raced in this corpus and never follows it, so one cell holds 5 while 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, since it would average the two directions away and report only that the words occur near each other. Word order carries grammar, so that dog bites and bites dog are different facts and a symmetric window throws the difference away. HAL keeps it, and that is what the two scans are for.

To see the whole thing at once, 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, and in the same row the scores 4 because the first the sits two words before.

Row barn is the interesting one, since 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, and if you miss that then your matrix is wrong.

The asymmetry is also precisely why a word needs two vectors rather than one, which is HAL’s third decision. Take the word $a$, whose row $M[a, \cdot]$ says what came before it and whose column $M[\cdot, a]$ says what came after it, those being the two scans recovered from the one matrix. A symmetric model would have nothing to concatenate, because row and column would be identical, whereas HAL concatenates them and so gives $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, on the grounds that a column which is nearly constant across words cannot distinguish them. 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 below, since both cut dimensions, though the SVD builds new dimensions that capture variance while HAL merely selects existing dimensions that already carry it.

Why the raw numbers work

The mechanics are now settled, and what is not yet explained is the part that matters. Why should a column of weighted counts, containing no dictionary and no grammar, put dog next to puppy?

Start by reading one cell on its own, because a cell is a question rather than a count. $M[a, b]$ is the answer that word $a$ gives to a single fixed question:

Every column asks a different question, one per vocabulary word, so every row of the concatenated vector is one word’s completed answer sheet, $2|V|$ questions long, where the row half answers what comes before you and the column half answers what comes after you.

Nothing in a single cell knows anything about meaning, because the number 5 in a cell records where the word sat in a stream of text and nothing about dogs.

The meaning arrives only when two answer sheets are laid side by side. Two words used in the same way must have met the same neighbours at the same distances, so they must give the same answers, and the vectors agree because the usage agrees. The distributional hypothesis says that usage is what meaning is made of.

As for what the number itself measures, a cell value is a sum of proximity credits, one credit per occurrence, and because the ramp is linear the value separates cleanly into how often and how near:

$$\begin{equation} M[a, b] \;=\; \sum_{\text{each time } b \text{ precedes } a} \big(W - \text{distance} + 1\big). \label{eq:hal-credits} \quad\text{(7.7)} \end{equation}$$

One adjacent sighting scores $W$, while ten sightings at the far edge of the window also score $10$, since each of those is worth 1. With Lund and Burgess’s $W = 10$ the two situations produce the same cell value and the model cannot tell them apart, which is deliberate, because both say the same thing: that $b$ is a real part of $a$’s surroundings.

The horse corpus has no two similar words in it, so it cannot demonstrate any of this, and we need a second and still tiny corpus,

with $W = 2$, so a neighbour scores 2 and the word beyond it scores 1. Here dog and puppy are used identically by construction. The matrix is:

Check row dog by hand. Dog occurs twice and each time the word directly before it is the, worth 2, so the cell holds $2 + 2 = 4$, while two words before the second dog sits barked at distance 2, worth 1.

Concatenate each row with its column and the vectors come out as:

Now the question can be answered exactly, by squaring Equation (7.6) at $r = 2$:

$$\begin{equation} d(x, y)^2 \;=\; \sum_i \big(x_i - y_i\big)^2 . \label{eq:hal-contribution} \quad\text{(7.8)} \end{equation}$$

The distance is a sum with one term per cell, and three properties follow that together are the whole mechanism. Each term depends on that cell alone, so no cell needs to know what any other cell holds. Each term is non-negative, so a cell can only ever push two words apart and never pull them together. And a cell where the two words agree contributes exactly zero, however large the number it holds.

The distance is therefore a tally of disagreements, so run that tally for dog and puppy:

$$d(\mathit{dog}, \mathit{puppy}) \;=\; \sqrt{2} \;=\; \boxed{\mathbf{1.414}}$$

Eight cells out of ten stay silent, and the two that speak are worth 1 each, both coming from the seam where one sentence runs into the next rather than from any real difference in how the words are used. On a real corpus those seams average out.

Now run the same tally for dog and slept, a noun against a verb:

$$d(\mathit{dog}, \mathit{slept}) \;=\; \sqrt{22} \;=\; \boxed{\mathbf{4.690}}$$

Seven cells disagree instead of two, and they disagree by larger amounts, so the evidence piles up.

Rank every pair in this vocabulary by distance and the model turns out to have sorted the words without being told a thing about them:

The two nouns are the closest pair and the two verbs the second closest, then come the mixed pairs, while the sits far from everything because it is the only word with no fixed slot of its own.

Read the contribution tables again and three facts about count vectors fall out.

No single cell decides. Dog and puppy disagree in two cells and agree in eight. Any one cell could be an accident of the corpus. The verdict is a vote across thousands of them, so accidents cancel while real regularities accumulate.

Silence is not evidence. A cell where both words hold zero contributes zero, exactly like a cell where both hold 40. In a real vocabulary almost every cell is zero for both words, so almost every cell is inert. Only the few hundred cells where at least one word is nonzero decide the answer. This is why the sparsity of the matrix is a nuisance for storage rather than for accuracy.

The votes are not equally weighted. Look at where the large contributions come from in the second table, which is the cells for the, the most frequent word in the corpus, because frequent contexts carry big numbers and big numbers make big squared differences. A frequent context can outvote a dozen informative rare ones, which is a defect and the subject of everything that follows.

One further consequence justifies the pruning step described earlier. A column whose values barely change from word to word contributes nearly zero to every pair, because every difference taken across it is nearly zero, so such a column cannot separate anything and dropping it changes almost no distance. That is precisely the low variance column HAL discards, and the argument is now visible in the arithmetic rather than merely asserted.

The same argument without words

Nothing in the previous subsection is about language, because the argument is about cells, agreement and distance, so it should survive being taken out of language altogether, and it does. Teach this version first, since nobody has to accept a claim about meaning before seeing the arithmetic work.

Take one morning of canteen bills, where a bill is a short sentence and the items on it are the words, listed in the order they were served. The window never reaches from one bill into the next.

Use $W = 2$, so the item served immediately before scores 2 and the one before that scores 1. Equation (7.4) then gives the matrix, with each bill counted as often as it was rung up:

The asymmetry is visible without looking for it, since $M[\mathit{chai}, \mathit{chutney}]$ is 24 while its mirror is 0, because chutney always precedes the drink and never follows it. The order of an Indian breakfast is written into the matrix, and nobody described a breakfast to the model.

Four rows are empty, and the reason is worth stating. A tiffin opens the bill, so nothing is ever served before it and its row has nothing to record, which is an edge effect rather than a statement about idli, the same one that empties the column for fell in the horse corpus because fell ends the corpus.

An empty row is missing evidence rather than evidence of difference, and under Equation (7.8) two empty rows agree perfectly, since every term is zero. Trust that agreement and the model reports nonsense:

On the row alone all four tiffins sit at distance zero from each other, so idli and vada come out identical when they are nothing of the kind. Idli is followed by chutney and vada by sambar, and the column records exactly that, so read together the two halves put idli and vada 27.09 apart, the widest gap between any two tiffins.

This is the concrete answer to why HAL doubles the vector. A word whose row is thin still has a context, and that context sits on the other side.

Now for the point the whole section is making, which concerns chai and coffee. Nobody orders both, so the two cells joining them are zero and stay zero however long the canteen runs. Lay the answer sheets side by side:

$$d(\mathit{chai}, \mathit{coffee}) \;=\; \sqrt{5} \;=\; \boxed{\mathbf{2.24}}$$

That is the closest pair in the canteen, with the next being idli and dosa at 6.40, so two drinks that have never once shared a bill are placed on top of each other because the same four tiffins and the same two sides arrive around both.

Say that out loud, because it inverts what students expect. The surest sign that two things are interchangeable is that they never appear together, since you choose one or the other, as with chai and coffee, rice and chapati, or dog and puppy.

Raw counts fail on the next case. Green tea was ordered twice and keeps exactly the company chai keeps, namely idli and dosa and chutney, yet ask the matrix and it gives the wrong answer:

The model reports that green tea is more like sambar than like chai. Split the 21.98 and the reason is plain:

One cell carries 400 of the 483. Not one number in that table says green tea is served differently, and every number says it is served less often, so the vector has the right shape and the wrong size. A distance on raw counts cannot tell the two apart.

The repair arrives on the same plate. Divide the size out and compare direction alone, which is the cosine of Chapter 4 applied to this matrix unchanged:

Green tea snaps into place beside chai and coffee, and those two become its nearest neighbours, so two orders were enough once volume stopped drowning out shape.

Keep that plate in mind through the rest of the chapter, because three repairs follow: PPMI, the correlation of COALS, and the rescaling before the SVD. Each one divides the size out so that the rare item can be heard.

Try it yourself. code/worked_examples/hal.py --canteen builds this matrix, prints both contribution tables, and shows the tiffins collapsing when the column half is dropped. Change a count in BILLS and watch which distances move.

Run it in ColabNotebookSource

Lund and Burgess were clear about the weakness that HAL exposed, and it is the reason COALS exists, because raw weighted counts still track frequency.

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

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

Green tea was the second case met on a plate, related to chai, ordered a fraction as often, and thrown 21.98 away by the arithmetic. Lund and Burgess saw the same thing across 160 million words of Usenet.

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. And --contributions reproduces the two tallies above, cell by cell, then ranks every pair.

Run it in ColabNotebookSource

COALS

Correlated Occurrence Analogue to Lexical Semantics (Rohde et al. 2006) keeps the ramped window and changes almost everything else, and its central move is to use a correlation instead of a count.

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.9)} \end{equation}$$

The numerator is the same comparison PMI makes, where $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, because a frequent word now has a large margin in both numerator and denominator, so being common stops earning a large score.

For a worked matrix, the lectures use a deliberately silly corpus:

A ramped window of size 4 gives a count matrix whose grand total is $T = 560$. The vocabulary runs to 13 token types, which is ten words plus the comma, the full stop and the question mark, since the punctuation is kept and counted like anything else. The window reaches equally in both directions, so the matrix is symmetric and a word’s row sum and column sum are the same number. Three of those sums we will need: a comes to 80, if to 40 and woodchuck to 80.

Now compute three cells with Equation (7.9).

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

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

Two further steps finish the job, discarding the negatives and damping what survives:

$$\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.10)} \end{equation}$$

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

The square root then damps what survives, pulling in the large values so that a few strong pairings cannot dominate a vector. Applying it to our three cells, $-0.167$ becomes $0$, while $0.085$ becomes $0.291$ and $0.096$ becomes $0.310$, so those two sit far closer after the root than before it.

COALS also drops HAL’s direction distinction, so the matrix stays symmetric and half the size, and it 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 7.4 describes, to get dense vectors.

Rohde and colleagues reported that this beat both HAL and Latent Semantic Analysis on word similarity judgements, with the gain coming 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 enough.

Every one of them does the same four things: count co-occurrences, reweight them into association rather than frequency, optionally compress, then read similarity as an angle. They disagree about the statistic and about whether order matters, and they agree about the shape.

That shape is what the next chapter abandons, though not the distributional hypothesis, which survives untouched, but rather 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.11)} \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, so $\sigma_1$ names the single direction along which the data vary most, $\sigma_2$ names the next, and so on down the list. Because they decay, most of the structure lives in the first handful of dimensions while the long tail contributes mostly noise, which suggests an obvious compression: keep only the top $K$ singular values and their vectors, and discard the rest.

Choosing K by contribution

That raises the practical question of how large $K$ should be, and the singular values answer it themselves, because 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.12)} \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.13)} \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 else plot $r_i$ against $i$, look for the elbow where the curve flattens, and cut there.

A spectrum makes this readable. Take a small co-occurrence matrix over eight words and eight contexts, where four of the words are animals, four are vehicles, and the two groups share no context at all. This is what the SVD returns.

The share column holds two values near $39\%$, then falls off a cliff to $10.5\%$, then dwindles for a long while. The elbow is unmistakable and it sits 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\%$, after which every further dimension buys almost nothing.

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

The two criteria can disagree, though, so watch what a threshold does here. An $80\%$ rule would reject $K = 2$ because $77.6\%$ falls just short, and would take $K = 3$ instead, which means the elbow was right and the threshold was wrong by $2.4$ percentage points.

That is a warning about the thresholds themselves. $0.8$ and $0.9$ are conventions rather than 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 while the threshold is telling you about itself.

Real corpora rarely produce a cliff this clean, and 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 deserves watching. 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 gives larger numbers, since squaring exaggerates the lead of the top values, so the same spectrum reads $49.2\%$ for the first dimension and $94.9\%$ for the first two.

That matters more than it looks, because 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, so state which one you used.

The resulting rank-$K$ matrix has a strong guarantee behind it, because by the Eckart-Young theorem it is the best possible approximation of $M$ by a matrix of rank $K$, and 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, because throwing away the noisy tail forces words that behaved similarly to collapse onto shared latent dimensions, so the compressed vectors generalise and 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 (Deerwester et al. 1990), and 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, and the procedure is unsupervised, principled and effective.

It has a ceiling, though, because 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.

A natural question arises from that. 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, which turns out to be almost the same object seen from the other side, since 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, meaning a way to adjust parameters so as to reduce an error, which counting never required. Chapter 8 builds exactly that machine in the neural network, and then Chapter 9 turns it loose on the distributional hypothesis.

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

Further reading.

Deerwester et al. (1990) is the original Latent Semantic Analysis paper. Lund and Burgess (1996) on HAL and Rohde et al. (2006) on COALS are influential count based models with different weighting choices. The semantic space formalism underlying all of them is set out by Lowe (2001). Manning, Raghavan and Schütze (Manning et al. 2009) cover matrix decompositions for retrieval and their latent semantic interpretation. The decomposition itself is numpy.linalg.svd, and sklearn.decomposition.TruncatedSVD computes only the top $k$ dimensions, which is the version you need once the matrix is too large to hold.

Code for this chapter

Each one reproduces the tables above. Open it in Colab, change an input and watch which numbers move.

• weighting.pytf-idf and PMI, by hand

  The weighting arithmetic the chapters print, on the four document matrix.

  standard library only Run it in Colab Notebook Source
• hal.pyHAL, ramped and asymmetric

  The ramped window, the matrix it fills, and why the matrix is not symmetric.

  standard library only Run it in Colab Notebook Source
• coals.pyCOALS, all three steps

  The correlation matrix, reproducing the lecture tables on the woodchuck corpus.

  standard library only Run it in Colab Notebook Source
• svd_rank.pyChoosing K from the spectrum

  The singular value spectrum and the two criteria that read it, which do not always agree.

  pip install numpy Run it in Colab Notebook Source
• svd.pySVD, and what truncation costs

  The factorisation, the truncation, and the dense vectors that come out the other side.

  pip install numpy Run it in Colab Notebook Source

From Natural Language Processing: From Corpus Statistics to Grounded LLMs, by Ramaseshan Ramachandran.