Chapter 1 · Section 1.4 · 60 min

You shall know a word by the company it keeps

We want vectors where similar words are close together. But "similar" according to whom? Nobody hands us a similarity score for every pair of the 100,000 words in English. That would be five billion pairs. We need a signal that comes for free from raw text.

That signal is one of the most productive ideas in all of AI, and it's older than computers doing language. This section turns it into vectors in three steps (count, reweight, compress), with no neural network anywhere, and the result is surprisingly good.

The distributional hypothesis

Read these sentences about a word you've never seen.

A bottle of zorbleflax is on the table. Everybody likes zorbleflax. Too much zorbleflax makes you dizzy. We make zorbleflax out of fermented corn.

You already know roughly what zorbleflax is, some kind of alcoholic drink. Nobody defined it. You inferred it from the words around it. (This is a remake of a classic example that Dekang Lin used in 1998, adapted from the linguist Eugene Nida, built around tezgüino, a real Mexican corn beer. Jurafsky and Martin's textbook does the same with ongchoi, a leafy vegetable.)

Linguists turned that observation into a principle in the 1950s.

"You shall know a word by the company it keeps." (J. R. Firth, 1957)

The distributional hypothesis (Harris, 1954) says that words that occur in similar contexts tend to have similar meanings. "Cat" and "kitten" both appear near purr, fur, pet, meow. "Carburetor" appears near engine, fuel, repair. So if we describe each word by the contexts it appears in, similar words automatically get similar descriptions.

Step 1. Count co-occurrences

Pick a window half-width $c$ (the number of words on each side that count as "nearby"). Slide the window over the corpus. Every time word $w$ appears within $c$ positions of another word, increment the counter for that pair. The result is the word–context co-occurrence matrix $\mathbf{C} \in \mathbb{R}^{V\times V}$ , where $V$ is the vocabulary size. From here on we follow the book's notation and write $c$ for a context word in a pair $(w, c)$ . The window size won't appear in another formula.

C_{wc} = \#\{\text{times context word } c \text{ appears within the window around an occurrence of } w\}.

In plain words, row $w$ of $\mathbf{C}$ counts, for every other word, how often it showed up near $w$ . That row is already a vector representation of word $w$ , its context profile. Let's build one from a tiny corpus of 93 tokens and 29 distinct words, split on spaces and numbered exactly as in §1.1.

Python · cell 1

Notice the problem right away. The biggest counts for cat are for a, ., and the. Those words co-occur with everything, so they tell us almost nothing about meaning. Raw counts reward frequency, not association.

Two design choices hide in this step. The window can be symmetric (as here) or only look left, and it can weight neighbors equally or by distance. GloVe, for instance, adds $1/k$ for a neighbor $k$ positions away, so adjacent words count most. The window size matters more, as we'll see at the end of the section.

Core

Build a co-occurrence matrix

Write cooccurrence(tokens, vocab, window) returning a (V, V) count matrix, where vocab is a list of words. Tokens not in vocab are skipped, but they still take up a position (they count toward distance). Count symmetrically, so if b is within window positions of a, increment C[a, b] (and, from b's point of view, C[b, a]). Avoid looping over tokens in pure Python. Loop over the offsets $1..c$ and use vectorized NumPy for each.

import numpy as np

def cooccurrence(tokens, vocab, window):
    raise NotImplementedError

Hidden tests, hints, and AI help, from $1.99 a month.

Step 2. Reweight with PMI

We want to ask not "how often do $w$ and $c$ co-occur?" but "do they co-occur more than we'd expect by chance?". If $w$ and $c$ were independent, the probability of seeing them together would be $p(w)\,p(c)$ . Pointwise mutual information compares what we observe to that baseline,

\operatorname{PMI}(w, c) \;=\; \log \frac{p(w, c)}{p(w)\,p(c)}, \qquad p(w,c) = \frac{C_{wc}}{\sum_{w',c'} C_{w'c'}}, \quad p(w) = \frac{\sum_{c'} C_{wc'}}{\sum_{w',c'} C_{w'c'}}, \quad p(c) = \frac{\sum_{w'} C_{w'c}}{\sum_{w',c'} C_{w'c'}}.

In plain words, PMI is the log of how many times more often the two words co-occur than they would if they were unrelated. PMI = 0 means "exactly chance", $\log 2 \approx 0.69$ means "twice as often as chance", and negative means "less than chance".

A worked example by hand

Take two words and two contexts with counts

\mathbf{C} = \begin{bmatrix} 4 & 0 \\ 1 & 5 \end{bmatrix}, \qquad \text{total} = 10 .

The marginals are $p(w_1) = 0.4$ , $p(w_2) = 0.6$ , $p(c_1) = 0.5$ , $p(c_2) = 0.5$ . Now each cell.

$\operatorname{PMI}(w_1, c_1) = \log\frac{0.4}{0.4 \times 0.5} = \log 2 \approx 0.693$ . They co-occur twice as often as chance.
$\operatorname{PMI}(w_2, c_1) = \log\frac{0.1}{0.6\times0.5} = \log\tfrac13 \approx -1.099$ . They avoid each other.
$\operatorname{PMI}(w_2, c_2) = \log\frac{0.5}{0.6\times0.5} = \log\tfrac53 \approx 0.511$ .
$\operatorname{PMI}(w_1, c_2) = \log 0 = -\infty$ . They never co-occurred.

PMI has a ceiling that explains its main weakness. Since $p(w, c) \le \min(p(w), p(c))$ , we get $\operatorname{PMI}(w,c) \le \min(-\log p(w), -\log p(c))$ . The maximum is reached when one word only ever appears with the other, and it is largest for rare words. A word seen twice, both times next to $w$ , can out-score a strong association between two common words.

PMI is also the per-pair piece of a familiar quantity. The mutual information between the word and context variables is the average PMI under the joint distribution, $I(W; C) = \sum_{w,c} p(w,c)\operatorname{PMI}(w,c)$ (§0.5 defines it). That is where the name comes from.

Two practical fixes are standard.

PPMI (positive PMI). Negative PMI values ("these words avoid each other") are unreliable unless the corpus is enormous, because estimating that something rarely co-occurs needs a lot of data. And $C_{wc} = 0$ gives $\log 0 = -\infty$ . So we clip, $\operatorname{PPMI}(w,c) = \max(\operatorname{PMI}(w,c), 0)$ . In the worked example, the PPMI matrix is $\begin{bmatrix}0.693 & 0\\ 0 & 0.511\end{bmatrix}$ .
Context distribution smoothing. To tame the rare-word bias, Levy, Goldberg and Dagan (2015) raise the context counts to a power $\alpha = 0.75$ before normalizing,

p_\alpha(c) = \frac{\left(\sum_{w'} C_{w'c}\right)^{\alpha}}{\sum_{c'} \left(\sum_{w'} C_{w'c'}\right)^{\alpha}}.

In plain words, rare contexts get a bigger share of probability than their raw count gives them, so a co-occurrence with a rare context is less surprising and earns a smaller PMI. A worked example shows how strong this is. Three words each co-occur 50 times with a common context, and word 1 also co-occurs twice with a rare context. With $\alpha = 1$ the rare context has $p(c) = 2/152 \approx 0.013$ and $\operatorname{PMI}(w_1, c_{\text{rare}}) \approx 1.07$ . With $\alpha = 0.75$ , $p_\alpha(c)$ rises to about 0.038 and the PMI drops to 0.02. Keep that $0.75$ in mind. It shows up again, for a closely related reason, in word2vec's negative sampling (§1.5).

Core

PPMI with context smoothing

Implement ppmi(C, alpha=1.0) for a count matrix C (rows are words, columns are contexts). Use $p(w,c)$ and $p(w)$ as defined above, and the smoothed $p_\alpha(c)$ . Return $\max(\operatorname{PMI}, 0)$ , with 0 wherever $C_{wc} = 0$ (no -inf, no NaN, no warnings).

import numpy as np

def ppmi(C, alpha=1.0):
    raise NotImplementedError

Hidden tests, hints, and AI help, from $1.99 a month.

Here is what PPMI does to the rows we printed before.

Python · cell 2

Now cat's strongest contexts are chases and milk, and car's are work, drive, and fuel. The function words haven't vanished (our corpus is tiny, so even a gets a small positive score), but they no longer dominate.

Documents as contexts, and tf-idf

A window is not the only choice of context. Take the whole document instead. Count how often word $w$ appears in document $D$ , its term frequency $\operatorname{tf}(w, D)$ , for each of $n$ documents. Row $w$ of this term–document matrix describes a word by the documents it appears in, and column $D$ describes a document by its words, which is how search engines represented documents for decades. The same problem appears at once, since the is in nearly every document and says nothing about any of them. The standard reweighting is tf-idf,

\operatorname{tfidf}(w, D) = \operatorname{tf}(w, D)\,\log\frac{n}{\operatorname{df}(w)},

where the document frequency $\operatorname{df}(w)$ is the number of documents that contain $w$ , and the log factor is the inverse document frequency (idf). In plain words, a word counts in proportion to how often it appears in this document, discounted by how common it is across all documents. A word found in every document gets $\log 1 = 0$ . The instinct is the one behind PMI, since $\log\frac{n}{\operatorname{df}(w)}$ is the surprise of finding $w$ in a random document, and common words carry little surprise.

Treat each of our 16 sentences as a document and check it.

Python · cell 3

the appears in 11 of the 16 documents, so its idf is $\log(16/11) \approx 0.37$ , while ball appears in one and gets $\log 16 \approx 2.77$ , about seven times more weight per occurrence. Latent Semantic Analysis, which we meet in the next step, factorizes a term–document matrix like this one, usually after a weighting like tf-idf. Documents behave like a very wide window, so their neighbors are topical (fuel near car) rather than substitutable, the trade-off we'll measure at the end of the section. §7.5 turns tf-idf into a ranking function for search and derives its stronger successor, BM25.

Step 3. Compress with SVD

The PPMI matrix is $V \times V$ , which makes it huge, sparse, and noisy. Row vectors of length 100,000 are clumsy, and two related words might share few exact contexts ("kitten" with meow, "cat" with purr). We want short, dense vectors that capture the main patterns of co-occurrence and smooth over the noise.

The tool for this is the singular value decomposition (SVD), which §0.10 develops from the geometry up. Here is the part we need. Any real matrix $\mathbf{M} \in \mathbb{R}^{V\times V}$ factors as

\mathbf{M} = \mathbf{U}_{\text{svd}}\boldsymbol{\Sigma}\mathbf{V}_{\text{svd}}^\top = \sum_{i=1}^{\text{rank}} \sigma_i\, \mathbf{a}_i \mathbf{b}_i^\top, \qquad \sigma_1 \ge \sigma_2 \ge \dots \ge 0,

where the columns $\mathbf{a}_i$ of $\mathbf{U}_{\text{svd}}$ and $\mathbf{b}_i$ of $\mathbf{V}_{\text{svd}}$ are orthonormal. (We add the subscript because $\mathbf{U}$ and $\mathbf{V}$ will mean other things in the next section.) In plain words, the matrix is a sum of rank-one patterns, each an outer product of a "word pattern" $\mathbf{a}_i$ and a "context pattern" $\mathbf{b}_i$ , and the singular value $\sigma_i$ says how much of the matrix that pattern explains.

A two-word example you can check by hand. Let word 1 have context counts $(3, 1)$ and word 2 have $(1, 3)$ , so

\mathbf{M} = \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix} = 4\,\mathbf{a}_1\mathbf{a}_1^\top + 2\,\mathbf{a}_2\mathbf{a}_2^\top, \qquad \mathbf{a}_1 = \tfrac{1}{\sqrt2}\begin{bmatrix}1\\1\end{bmatrix},\quad \mathbf{a}_2 = \tfrac{1}{\sqrt2}\begin{bmatrix}1\\-1\end{bmatrix}.

(Here $\mathbf{b}_i = \mathbf{a}_i$ because $\mathbf{M}$ is symmetric with positive eigenvalues.) Multiply it out to check, since $4\cdot\tfrac12\begin{bmatrix}1&1\\1&1\end{bmatrix} + 2\cdot\tfrac12\begin{bmatrix}1&-1\\-1&1\end{bmatrix} = \begin{bmatrix}3&1\\1&3\end{bmatrix}$ . The first pattern, with $\sigma_1 = 4$ , says "both words use both contexts". The second, with $\sigma_2 = 2$ , says "word 1 prefers context 1 and word 2 prefers context 2". Keeping only the first gives the rank-one approximation $\begin{bmatrix}2&2\\2&2\end{bmatrix}$ , which keeps what the words share and forgets how they differ.

Eckart–Young theorem. Keeping only the top $r$ terms, $\mathbf{M}_r = \sum_{i=1}^{r}\sigma_i\mathbf{a}_i\mathbf{b}_i^\top$ , gives the best possible rank- $r$ approximation of $\mathbf{M}$ , in both Frobenius norm (the square root of the sum of squared entries) and spectral norm (the largest factor by which the matrix stretches a unit vector),

\min_{\operatorname{rank}(\mathbf{B}) \le r} \lVert\mathbf{M}-\mathbf{B}\rVert_F = \lVert\mathbf{M}-\mathbf{M}_r\rVert_F = \sqrt{\textstyle\sum_{i > r}\sigma_i^2}, \qquad \min_{\operatorname{rank}(\mathbf{B}) \le r}\lVert\mathbf{M}-\mathbf{B}\rVert_2 = \sigma_{r+1}.

In plain words, the truncated SVD is the optimal way to compress the matrix to $r$ patterns, and the error is exactly the "energy" in the patterns you threw away. In the two-word example, the error of the rank-one approximation is $\begin{bmatrix}1&-1\\-1&1\end{bmatrix}$ , whose Frobenius norm is $\sqrt{4} = 2 = \sigma_2$ , as promised. For our corpus's PPMI matrix the top singular values are 7.71, 5.44, 5.23, 4.56, 4.00, 3.89, and keeping $r = 6$ of the 29 patterns retains 63% of the squared Frobenius norm.

The word vectors are then the rows of $\mathbf{U}_{\text{svd},r}\boldsymbol{\Sigma}_r^{\,p}$ , each word's coordinates in the space of the top $r$ patterns, where $\mathbf{U}_{\text{svd},r}$ keeps the first $r$ columns and $\boldsymbol\Sigma_r$ the top $r$ singular values. The exponent $p$ is a hyperparameter. $p = 1$ is the textbook choice, but Levy et al. (2015) found that $p = 0.5$ or even $p = 0$ often works better for similarity tasks, because it stops the first few patterns from dominating every cosine. This approach is the heart of Latent Semantic Analysis (LSA; Deerwester et al., 1990), which originally applied it to term–document matrices like the one in the previous subsection.

∂ Why SVD vectors put similar words close together

Suppose two words $w_1, w_2$ have nearly identical PPMI rows, meaning they keep the same company. Since $\mathbf{M} = \mathbf{U}_{\text{svd}}\boldsymbol\Sigma\mathbf{V}_{\text{svd}}^\top$ , row $w$ of $\mathbf{M}$ is $\mathbf{M}_{w,:} = (\mathbf{U}_{\text{svd}})_{w,:}\,\boldsymbol\Sigma\mathbf{V}_{\text{svd}}^\top$ . The matrix $\boldsymbol\Sigma\mathbf{V}_{\text{svd}}^\top$ is the same for every word, and multiplying a row vector by $\mathbf{V}_{\text{svd}}^\top$ (orthonormal rows) preserves its length, so

\lVert \mathbf{M}_{w_1,:} - \mathbf{M}_{w_2,:} \rVert = \lVert \big((\mathbf{U}_{\text{svd}})_{w_1,:} - (\mathbf{U}_{\text{svd}})_{w_2,:}\big)\boldsymbol\Sigma \rVert.

Similar rows in $\mathbf{M}$ give similar rows in $\mathbf{U}_{\text{svd}}\boldsymbol\Sigma$ , exactly, for the full SVD. Truncating to $r$ dimensions keeps the coordinates along the largest- $\sigma$ directions, where the strongest shared patterns live, and drops the small, noisy ones. Words that share contexts only indirectly (cat with purr, kitten with meow, while purr and meow co-occur with similar things) get pulled together, because they load on the same dominant patterns.

Core

Truncated-SVD embeddings (and verify Eckart–Young)

Write svd_embeddings(M, r, p=1.0) that returns the (V, r) matrix $\mathbf{U}_{\text{svd},r}\boldsymbol\Sigma_r^p$ and also the rank- $r$ reconstruction $\mathbf{M}_r$ . The tests verify the Eckart–Young error formula on your output.

import numpy as np

def svd_embeddings(M, r, p=1.0):
    """returns (W, M_r): W is (V, r) = U_r * s_r**p ; M_r is the rank-r reconstruction"""
    raise NotImplementedError

Hidden tests, hints, and AI help, from $1.99 a month.

The whole pipeline, end to end

Counts, then PPMI, then SVD, then nearest neighbors by cosine. The code below uses the corpus and the PPMI matrix from the cells above.

Python · cell 4

With 93 tokens, this already discovers that cat's nearest neighbors are dog, puppy, and kitten, and that car's nearest is truck. Look closely at the odd ones too. "drive → ball" is noise from a tiny corpus. But "milk → drinks" is telling. Counting words in a window captures two different kinds of similarity.

Substitutable words (called paradigmatic, like cat/kitten and car/truck) appear in the same contexts and could replace each other in a sentence.
Associated words (called syntagmatic, like milk/drinks and fuel/needs) appear next to each other.

Small windows ( $c = 1$ or 2 words on each side) tend to emphasize substitutability and syntactic role. Large windows ( $c = 5$ to 10) emphasize topic and association. Change window in the first cell and rerun to see the shift. Bullinaria and Levy (2007) mapped these choices systematically and found small windows with PPMI best for most semantic tasks.

At real scale the method holds up. Levy, Goldberg and Dagan (2015) trained on English Wikipedia and found that, once the same tricks are applied to both, PPMI and its SVD match word2vec on word-similarity benchmarks, while word2vec keeps an edge on analogies.

Interview

Count-based embeddings end to end

Put the three steps together. Implement ppmi_svd_embeddings(tokens, window, r, alpha=0.75, p=0.5) that returns (vocab, W), where vocab is the sorted list of distinct tokens and W is the (V, r) matrix of unit-length rows of $\mathbf{U}_{\text{svd},r}\boldsymbol\Sigma_r^p$ computed from the smoothed PPMI of the symmetric co-occurrence counts (exactly the conventions of Exercises 1.4a to 1.4c, with every token in the vocabulary).

The tests train on a synthetic corpus of four categories (animals, fruit, vehicles, tools) and require that every noun's nearest other noun is in its own category. They also compare your Gram matrix $\mathbf{W}\mathbf{W}^\top$ (which is unaffected by the sign ambiguity of the SVD) with a reference, so the window, $\alpha$ , and $p$ must all be right.

import numpy as np

def ppmi_svd_embeddings(tokens, window, r, alpha=0.75, p=0.5):
    """-> (sorted vocab list, W of shape (V, r) with unit-norm rows)"""
    raise NotImplementedError

Hidden tests, hints, and AI help, from $1.99 a month.

Scaling up, sparse counts and randomized SVD

For $V = 100{,}000$ words, a dense $V\times V$ matrix of float64 would take 80 GB, and a full SVD costs $O(V^3)$ , about $10^{15}$ operations. Neither is necessary. Most word pairs never co-occur, so the PPMI matrix is sparse (PPMI keeps zeros as zeros), and we only want the top $r \approx 300$ singular vectors.

Randomized SVD (Halko, Martinsson & Tropp, 2011) gets them by multiplying the matrix by a few hundred random vectors. The idea has three steps.

Sketch the range. Draw a Gaussian matrix $\boldsymbol\Omega \in \mathbb{R}^{V\times(r+q)}$ with a small oversampling $q$ (say 10) and form $\mathbf{Y} = \mathbf{M}\boldsymbol\Omega$ . Each column of $\mathbf{Y}$ is a random combination of $\mathbf{M}$ 's columns, so it is dominated by the top singular directions, the same random-projection idea as Johnson–Lindenstrauss in §1.3.
Sharpen with power iterations. If the spectrum decays slowly, replace $\mathbf{Y}$ by $(\mathbf{M}\mathbf{M}^\top)^{t}\mathbf{M}\boldsymbol\Omega$ for $t = 1$ or 2. This raises every singular value to the power $2t+1$ , so the top ones stand out much more. Re-orthonormalize with a QR decomposition between multiplications to avoid losing precision.
Solve a small problem. With $\mathbf{Q}$ an orthonormal basis of $\mathbf{Y}$ 's columns, $\mathbf{M} \approx \mathbf{Q}\mathbf{Q}^\top\mathbf{M}$ . Take the exact SVD of the small $(r+q)\times V$ matrix $\mathbf{B} = \mathbf{Q}^\top\mathbf{M}$ , as $\mathbf{B} = \tilde{\mathbf{U}}\boldsymbol\Sigma\mathbf{V}_{\text{svd}}^\top$ , and set $\mathbf{U}_{\text{svd}} = \mathbf{Q}\tilde{\mathbf{U}}$ .

In plain words, random vectors find the subspace where the matrix does most of its work, and the exact SVD is only ever computed inside that small subspace. The cost is a few sparse matrix products, $O\big(\operatorname{nnz}(\mathbf{M})\,(r+q)(2t+1)\big)$ , where $\operatorname{nnz}$ counts the nonzeros, instead of $O(V^3)$ .

Research

Randomized SVD from scratch

Implement randomized_svd(M, r, oversample=10, n_iter=2, seed=0) returning (U, s, Vt) with shapes (m, r), (r,), (r, n), following the three steps above. Use np.linalg.qr to orthonormalize after every multiplication in the power iterations.

The tests use a matrix whose singular values decay slowly ( $\sigma_i \propto i^{-1/2}$ ), which is where the power iterations matter. With two iterations your top 10 singular values must be within 3% of the exact ones and your reconstruction error within 1% of the Eckart–Young optimum. Without power iterations the singular values come out more than 30% too small.

import numpy as np

def randomized_svd(M, r, oversample=10, n_iter=2, seed=0):
    raise NotImplementedError

Hidden tests, hints, and AI help, from $1.99 a month.

	count-based (PPMI + SVD)	predict-based (word2vec, §1.5)
training	one big matrix factorization	streaming SGD over the corpus
memory	sparse $V\times V$ matrix, plus SVD workspace	only the two $V\times d$ tables
adding data	recount and refactorize	just keep training
scale	randomized SVD on sparse matrices handles large $V$	scales to billions of tokens easily
interpretability	explicit, since you can read the PPMI rows	implicit
quality	competitive when tuned (Levy et al. 2015)	strong, robust defaults

In PyTorch

At real scale you keep $\mathbf{C}$ as a sparse matrix, compute PPMI only on its nonzeros, and use a randomized low-rank SVD. PyTorch's torch.svd_lowrank implements the Halko algorithm and accepts sparse input.

🔥 In PyTorchfor a machine with PyTorch

🎯 Interview questions on this section

State the distributional hypothesis, and say why it matters so much for ML.

Words that appear in similar contexts tend to have similar meanings (Harris 1954; Firth 1957). It matters because it turns similarity, which nobody labels, into co-occurrence, which raw text provides for free. Every self-supervised objective in this book (word2vec, masked language modeling, next-token prediction, masked image modeling, contrastive learning) is a version of "predict something from its context".

What is PMI, compute it for a small table, and say why people use PPMI.

$\operatorname{PMI}(w,c) = \log\frac{p(w,c)}{p(w)p(c)}$ , the log ratio of observed co-occurrence to what independence predicts. For counts $\begin{bmatrix}4&0\\1&5\end{bmatrix}$ the cell (1,1) has $\log\frac{0.4}{0.4\cdot0.5} = \log 2$ . Negative values need huge corpora to estimate reliably, and unseen pairs give $-\infty$ , so PPMI clips at 0, which also keeps the matrix sparse.

Why is PMI biased toward rare words, and how do you fix it?

$\operatorname{PMI}(w,c) \le \min(-\log p(w), -\log p(c))$ , so rare words can reach the largest values, and with small counts a single chance co-occurrence produces a huge ratio. Fixes are context-distribution smoothing ( $p_\alpha(c) \propto \#(c)^{0.75}$ , which in a worked example dropped a rare context's PMI from 1.07 to 0.02), add- $k$ smoothing of the counts, and minimum-count thresholds.

Why does a truncated SVD produce good embeddings? What does Eckart–Young say exactly?

The rank- $r$ truncation is the best rank- $r$ approximation in Frobenius and spectral norm, with errors $\sqrt{\sum_{i>r}\sigma_i^2}$ and $\sigma_{r+1}$ . It keeps the dominant co-occurrence patterns and drops low-energy noise. Since $\mathbf{M}_{w,:} = (\mathbf{U}_{\text{svd}})_{w,:}\boldsymbol\Sigma\mathbf{V}_{\text{svd}}^\top$ and $\mathbf{V}_{\text{svd}}$ is orthonormal, words with similar PPMI rows get similar coordinates, and words that share contexts only indirectly are pulled together through shared patterns.

Why use

\mathbf{U}\boldsymbol\Sigma^{p}

with

p \lt 1

instead of

\mathbf{U}\boldsymbol\Sigma

With $p = 1$ the first few singular directions, which often encode frequency and generic co-occurrence, dominate every cosine. Smaller $p$ flattens the weighting so more patterns contribute. It is an empirical finding (Caron 2001; Levy et al. 2015) that $p = 0.5$ or $0$ often helps similarity tasks. Note that $p$ changes only the embedding, never the reconstruction $\mathbf{M}_r$ .

How would you build PPMI and SVD embeddings for a 1M-word vocabulary?

Count co-occurrences in a streaming pass into a sparse matrix (or shard by word and merge), apply a minimum count and smoothing, compute PPMI only on nonzeros (PPMI preserves sparsity), then run randomized SVD with a few hundred random vectors and one or two power iterations. Cost is a handful of sparse products, $O(\operatorname{nnz}\cdot r)$ , instead of $O(V^3)$ for a dense SVD that would need terabytes of memory.

How does the window size change what the vectors capture?

Small windows (1 or 2 words) capture substitutability and syntax, so neighbors are words of the same type that could replace each other (cat and dog). Large windows (5 to 10 words, or whole documents as in LSA) capture topic and association (doctor and hospital). Benchmarks that reward similarity, like SimLex-999, prefer small windows, and relatedness benchmarks prefer larger ones.

🧭 What to remember

The distributional hypothesis says meaning is approximated by the company a word keeps. Context gives free supervision.
Co-occurrence counts are dominated by frequent words. PMI measures association instead, as observed over expected-under-independence in log space. Use PPMI with $\alpha = 0.75$ context smoothing in practice, because PMI favors rare words. With documents as contexts, tf-idf plays the same role.
Truncated SVD compresses the sparse $V\times V$ PPMI matrix into dense $r$ -dimensional vectors, optimally by Eckart–Young. The weighting exponent $p$ is a real hyperparameter.
Small windows capture substitutable words, and large windows capture topical association.
Randomized SVD with power iterations makes this practical at scale, at the cost of a few sparse matrix products.
Properly tuned, count-based vectors rival neural ones. Next, §1.5 takes the neural, predictive route of word2vec, and reveals that it ends up factorizing (shifted) PMI too.

Harris (1954). Distributional Structure. The distributional hypothesis.
Church & Hanks (1990). Word Association Norms, Mutual Information, and Lexicography. PMI for word association.
Deerwester et al. (1990). Indexing by Latent Semantic Analysis. Truncated SVD for meaning.
Turney & Pantel (2010). From Frequency to Meaning. The classic survey of count-based vector spaces.
Levy, Goldberg & Dagan (2015). Improving Distributional Similarity with Lessons Learned from Word Embeddings. Why tuned counts rival word2vec. Read it alongside Baroni et al. (2014), Don't count, predict!
Bullinaria & Levy (2007). Extracting Semantic Representations from Word Co-occurrence Statistics. A systematic study of windows, weightings, and distance measures, with PPMI and small windows coming out on top.
Halko, Martinsson & Tropp (2011). Finding Structure with Randomness. The randomized SVD, with error bounds and the power-iteration trick.

Zero to Frontier is made for larger screens

You shall know a word by the company it keeps

The distributional hypothesis

Step 1. Count co-occurrences

Build a co-occurrence matrix

Step 2. Reweight with PMI

A worked example by hand

PPMI with context smoothing

Documents as contexts, and tf-idf

Step 3. Compress with SVD

Truncated-SVD embeddings (and verify Eckart–Young)

The whole pipeline, end to end

Count-based embeddings end to end

Scaling up, sparse counts and randomized SVD

Randomized SVD from scratch

In PyTorch

Read more

Watch next