Distributional Semantics

The distributional hypothesis states that words occurring in similar linguistic contexts tend to have similar meanings. This is often summarized by the slogan "you shall know a word by the company it keeps." It is not a claim that context is meaning in some philosophical sense; it is a working hypothesis that context is a reliable, measurable proxy for meaning, precise enough to build algorithms on. To operationalize this, define a context for a target word as the set of words (or documents) that surround it, within some window or unit of text. A co-occurrence matrix $M$ records how often each target word appears near each context word. If $V$ is the vocabulary, $M$ is a $|V| \times |V|$ matrix (word-word) or $|V| \times D$ matrix for $D$ documents (word-document, as in classic term-document matrices from information retrieval). Row $M_w$, the vector of counts for word $w$ across all contexts, is called the distributional vector or count vector of $w$. The central geometric claim is: if two words $w_1$ and $w_2$ have similar rows $M_{w_1}$ and $M_{w_2}$, they are used in similar ways and hence tend to be semantically related — synonyms ("happy"/"joyful"), co-hyponyms ("cat"/"dog"), or words in the same domain ("goalkeeper"/"referee"). This turns semantics into linear algebra: similarity of meaning becomes similarity of vectors, typically measured by cosine similarity,

Cosine similarity is preferred over raw dot product or Euclidean distance because it is insensitive to vector length, and vector length in raw count vectors mostly reflects word frequency rather than meaning.

Building a distributional model has four steps: choose the context definition, build the co-occurrence matrix, reweight the raw counts, and optionally reduce dimensionality. Each step is a design decision with consequences for what "similarity" ends up capturing.

Step 1 — Context definition. Two families dominate. In the document context model, the context of a word is the document it appears in; this yields the classic term-document matrix used for topic and document similarity (information retrieval, latent semantic analysis). In the window context model, the context of a word is the set of words within $k$ positions to its left and right in running text; this yields a term-term matrix and captures finer-grained, more syntactic/semantic similarity than topic-level similarity. Small windows (1–3 words) tend to capture syntactic and functional similarity; large windows (10+ words) tend to capture topical similarity.

Step 2 — Counting. Slide the window across a corpus and increment matrix entries for every (target, context) pair observed.

Step 3 — Reweighting. Raw counts are dominated by high-frequency function words ("the", "of", "a") that co-occur with everything and carry little discriminative meaning. Reweighting schemes discount this. The two classic schemes are:

• TF-IDF (term frequency–inverse document frequency), historically used for word-document matrices in IR.
• PPMI (positive pointwise mutual information), the standard choice for word-word matrices, defined below.

Step 4 — Dimensionality reduction (optional). Raw co-occurrence matrices are huge ($|V| \times |V|$, often tens of thousands squared) and sparse. Singular Value Decomposition (SVD) can compress each row into a dense, low-dimensional vector (e.g. 300 dimensions) that retains most of the distributional signal while being cheaper to store and compare. This step is the direct mathematical precursor to the dense embeddings produced by neural models.

Pointwise Mutual Information (PMI) and PPMI

PMI measures whether a target word $w$ and context word $c$ co-occur more or less often than chance, given their individual frequencies:

Here $P(w,c)$ is the empirical probability of $w$ and $c$ co-occurring (count divided by total co-occurrence count), and $P(w)$, $P(c)$ are their marginal probabilities. PMI is positive when $w$ and $c$ co-occur more than independence would predict, negative when they co-occur less. Negative PMI values are statistically unreliable for rare pairs (a single unseen co-occurrence swings the estimate wildly), so in practice we clip at zero:

This single design choice — throw away unreliable negative signal, keep reliable positive signal — is the single most impactful reweighting decision in classic distributional semantics.

Full pipeline pseudocode

``` function BUILD_DISTRIBUTIONAL_VECTORS(corpus, window_size, vocab):

# Step 1-2: build raw co-occurrence counts C = zero matrix of size |vocab| x |vocab| for each position i in corpus: w = corpus[i] if w not in vocab: continue for j in range(max(0, i - window_size), min(len(corpus), i + window_size + 1)): if j == i: continue c = corpus[j] if c not in vocab: continue C[index(w)][index(c)] += 1

# Marginal counts total = sum of all entries in C row_sum[w] = sum over c of C[w][c] # how often w occurs as target col_sum[c] = sum over w of C[w][c] # how often c occurs as context

# Step 3: convert counts to PPMI PPMI = zero matrix of size |vocab| x |vocab| for w in vocab: for c in vocab: if C[w][c] == 0: continue P_wc = C[w][c] / total P_w = row_sum[w] / total P_c = col_sum[c] / total pmi = log2( P_wc / (P_w * P_c) ) PPMI[w][c] = max(pmi, 0)

# Step 4 (optional): dimensionality reduction via truncated SVD U, Sigma, V_T = TRUNCATED_SVD(PPMI, k = target_dim) embeddings = U * Sigma # each row is a dense k-dim word vector return embeddings # or return PPMI rows directly if no reduction desired

function COSINE_SIMILARITY(u, v): dot = sum(u[i] v[i] for i in range(len(u))) norm_u = sqrt(sum(u[i]^2 for i in range(len(u)))) norm_v = sqrt(sum(v[i]^2 for i in range(len(v)))) if norm_u == 0 or norm_v == 0: return 0 # guard against zero vectors return dot / (norm_u norm_v) ``` Edge cases handled explicitly: words outside the fixed vocabulary are skipped (`if w not in vocab`), zero counts are skipped before taking a logarithm (avoiding $\log(0)$), and cosine similarity guards against division by zero for all-zero rows (which occur for words absent from the corpus window entirely).

Time complexity of construction. Building the raw co-occurrence matrix requires one pass over the corpus of length $N$ tokens, with constant work per token per window position, giving $O(N \cdot k)$ time for window size $k$. This is linear in corpus size and window width — the dominant cost in practice for large corpora.

Space complexity. The naive dense matrix is $O(|V|^2)$ for word-word co-occurrence, which is prohibitive for realistic vocabularies ($|V| \sim 10^5$–$10^6$ gives $10^{10}$–$10^{12}$ entries). In practice the matrix is extremely sparse — most word pairs never co-occur — so a sparse representation (hash map or coordinate list) stores only $O(N \cdot k)$ nonzero entries, since each token contributes at most $2k$ new co-occurrence pairs.

PPMI computation cost. Computing PPMI for every nonzero entry is $O(\text{nnz})$ where $\text{nnz}$ is the number of nonzero cells, since it requires only the marginal sums (precomputed once in $O(\text{nnz})$) and a constant-time computation per cell.

SVD cost. Truncated SVD to rank $k$ on a sparse $|V| \times |V|$ matrix with $\text{nnz}$ nonzeros costs roughly $O(\text{nnz} \cdot k)$ per iteration using iterative methods (e.g. Lanczos/randomized SVD), rather than the $O(|V|^3)$ of a naive dense SVD — this is what makes dimensionality reduction tractable at vocabulary scale.

Why cosine similarity is the right measure — a justification. Consider two words $w_1, w_2$ that behave identically in every context except that $w_1$ is twice as frequent overall (a common phenomenon: "big" vs. a rarer synonym "huge" used in the same syntactic slots). Their raw count vectors satisfy $M_{w_1} \approx 2 M_{w_2}$ elementwise. Euclidean distance $\|M_{w_1} - M_{w_2}\|$ can be large simply due to this scale difference, misleadingly suggesting dissimilarity. Cosine similarity is scale-invariant:

correctly identifying such words as maximally similar in direction, which is what distributional theory claims corresponds to meaning — the pattern of contexts, not the absolute frequency of use.

Why PPMI is a principled correction, not an ad hoc trick. Raw co-occurrence count $C(w,c)$ conflates two effects: how informative the pairing is, and how frequent each word is individually. PMI factors these apart by normalizing by the marginals $P(w)P(c)$, the count expected under independence. A large $C(w,c)$ driven purely by both words being extremely frequent (e.g. "the" and "of") yields $P(w,c) \approx P(w)P(c)$ and hence PMI near 0 — correctly signaling "no special association." Clipping to PPMI is justified because for large but finite corpora, PMI estimates for rare pairs have high variance (a single co-occurrence of two rare words produces a large, unreliable PMI spike in either direction), and empirically negative PMI values correlate poorly with any usable semantic signal, while positive PMI values reliably indicate genuine association.

Honesty about tradeoffs. This entire framework is a bag-of-contexts model: it discards word order within the window (except through window boundaries) and cannot represent polysemy — a word like "bank" gets one vector blending "riverbank" and "financial bank" senses, because counts are aggregated over all occurrences. It is also a static representation: the vector for a word never changes based on the sentence it appears in, unlike contextual embeddings from transformer models. Distributional semantics gives a correct and interpretable first-order theory of lexical similarity, but it is not the final word on meaning — it is the foundation that dense, learned, and later contextual embeddings build upon.

Consider a toy corpus (typical of how such examples are built for teaching): four short sentences. ``` 1. "tejano band played accordion music" 2. "conjunto band played accordion tunes" 3. "the sky was a clear blue" 4. "clouds filled the blue sky" ``` Use a window size of $k=2$ and restrict the vocabulary to content words {tejano, conjunto, band, accordion, music, sky, blue, cloud}. Raw window co-occurrence counts (word × word, symmetric window):

Marginals (row sums over this small table, total count $T = 20$ for illustration):

• $P(\text{tejano}) = 2/20$, $P(\text{conjunto}) = 2/20$
• $P(\text{band}) = 5/20$, $P(\text{accordion}) = 3/20$
• $P(\text{sky}) = 2/20$, $P(\text{blue}) = 2/20$

Compute PMI for (tejano, band): $C = 1$, so $P(\text{tejano, band}) = 1/20$.

This is positive: tejano and band co-occur more than chance predicts, so PPMI(tejano, band) $= 1.0$. Now compute PMI for (sky, blue): $C = 2$, $P(\text{sky, blue}) = 2/20 = 0.1$.

This large PPMI reflects that sky and blue almost always co-occur relative to their (low) individual frequencies — a strong, reliable association from a small sample. After PPMI weighting, compare `tejano` and `conjunto` by cosine similarity over their (mostly identical) PPMI rows — both vectors point almost exactly the same direction in the {band, accordion} subspace, giving cosine similarity near 1.0. Compare `tejano` and `sky` — their nonzero dimensions barely overlap, giving cosine similarity near 0. The distributional model has correctly inferred, purely from co-occurrence statistics and without any dictionary, that tejano and conjunto are semantically close while tejano and sky are not — because tejano and conjunto share almost identical distributional contexts (band, accordion), exactly the signature the distributional hypothesis predicts.

Distributional semantics underlies the earliest practical vector-space models in information retrieval, where term-document matrices (weighted by TF-IDF) power document similarity, clustering, and search ranking — the same mathematics used in search engines before neural re-ranking existed. Latent Semantic Analysis (LSA), built by applying SVD to term-document matrices, was deployed in essay-grading systems and synonym-detection tools, and its dimensionality-reduction step is the direct mathematical ancestor of dense embeddings. The word-word PPMI-plus-SVD pipeline described here is the classical baseline against which every learned embedding method — Word2Vec Skip-gram, GloVe, and their successors — is measured, and it can be shown that skip-gram with negative sampling implicitly factorizes a shifted PMI matrix, making the connection between counting-based and neural methods mathematically precise rather than merely historical. Modern large language models, whose token representations are learned end-to-end via gradient descent rather than counted explicitly, still rest on the same underlying assumption: that a token's role is determined by, and recoverable from, the contexts in which it appears. Every time a chatbot infers that "furious" is closer to "angry" than to "hungry," it is exploiting the distributional hypothesis, however many layers of transformation now separate the raw text from the final vector. This throughline connects Distributional Semantics directly to Word Embeddings and Dense Vectors and the broader architecture of neural language models.

Ask the tutor: How does skip-gram with negative sampling relate mathematically to the PPMI matrix factorization described here?