Co-occurrence Matrices: Distributional Semantics in NLP

If you count how often words appear near each other across a large corpus, you capture something surprisingly deep about language. Words that frequently share context tend to share meaning. "Bank" appears near "river" in some documents and near "loan" in others. "Doctor" appears near "patient," "diagnosis," and "hospital." "Python" appears near "code," "script," and "programming." These co-occurrence patterns, summarized in a matrix, form one of the oldest and most powerful representations in computational linguistics.

A co-occurrence matrix turns text into numbers without throwing away the relational structure between words. Unlike simple word counts, it records not what words appear, but what words appear together. That distinction matters enormously. Two synonyms like "begin" and "start" may have different raw frequencies, but they share nearly the same co-occurrence neighborhood, which is what makes them semantically equivalent in this framework. Frequency tells you how common a word is. Co-occurrence tells you what world a word inhabits.

This representational shift, from individual word frequencies to relational statistics between words, was one of the most important transitions in the history of computational linguistics. It transformed semantics from a hand-crafted ontology problem into a statistical inference problem. You no longer needed to program in the meaning of words. You could read their meaning off the data by examining who their neighbors were.

This chapter covers the two primary forms of co-occurrence matrices (word-word and word-document), the decisions that shape them (window size, distance weighting, directionality), the statistical properties they exhibit (sparsity, power-law distributions, dominance of function words), and the efficient algorithms used to construct them at scale. Understanding these matrices in depth matters because every major advance in distributional word representations, from PMI-weighted matrices to LSA to Word2Vec to transformer attention, can be understood as a refinement of the ideas here.

There are two foundational ways to count co-occurrences, and they answer slightly different questions about language. The distinction is not merely technical. It reflects a fundamental choice about what "context" means: is it the local verbal neighborhood of a word, or the broader documentary environment in which the word appears?

A word-word co-occurrence matrix counts how many times each pair of words appears within a defined proximity in text. If the vocabulary has $V$ words, the matrix has shape $V \times V$. Entry $C_{ij}$ records how often word $j$ appears within the context window of word $i$.

Each row of this matrix is a vector representing a word in terms of its context neighbors. Two words that appear in similar contexts will have similar row vectors, making cosine similarity over these rows a natural measure of semantic relatedness. This is the matrix that directly operationalizes the distributional hypothesis from the previous chapter: "You shall know a word by the company it keeps."

The word-word matrix is the most natural instantiation of local distributional semantics. When linguists studied word meaning in the 1990s and observed that "surgeon" and "physician" had nearly identical row vectors even though they were not perfect synonyms, it was the word-word matrix that demonstrated this computationally for the first time. The vectors do not represent isolated words; they represent words in relation to all other words in the language.

An important property of word-word matrices is that they are approximately symmetric when built with a symmetric window. If "coffee" often appears near "drank," then "drank" often appears near "coffee," because these are the same co-occurrence events observed from different perspectives. The matrix is not perfectly symmetric due to boundary effects at sentence edges, but it is close, and many analyses exploit this symmetry.

A word-document co-occurrence matrix has a different shape: $V \times D$, where $D$ is the number of documents in the corpus. Entry $M_{id}$ records whether (or how many times) word $i$ appears in document $d$.

This matrix encodes a different kind of distributional signal. Instead of asking "which words appear near this word?" it asks "which documents contain this word?" Words that co-occur in the same documents tend to be topically related. "Surgery" and "anesthesia" both appear in medical articles. "Volatility" and "hedge" both appear in financial reports. Document-level co-occurrence captures topic coherence rather than local grammatical or semantic context.

The word-document matrix is also the foundation of information retrieval. When a search engine represents a document as a vector of word counts, it is constructing a column of this matrix. The classic TF-IDF representation, which we examined in Part 1, is simply a reweighted version of this matrix where raw counts are scaled by inverse document frequency. Latent Semantic Analysis (LSA), which we will cover in the SVD chapter, applies Singular Value Decomposition to this matrix to discover latent topics that cut across the raw count structure.

One practical advantage of the word-document matrix over the word-word matrix is that it scales more gracefully when the vocabulary is large but the document collection is modest. A corpus of 10,000 documents with a vocabulary of 100,000 words produces a $100{,}000 \times 10{,}000$ matrix, which is rectangular and often more tractable than the $100{,}000 \times 100{,}000$ word-word matrix.

The choice between word-word and word-document matrices is a modeling decision, and the right choice depends on the relationship you want to capture.

Word-word matrices work better for capturing syntactic relationships and local semantic similarity. If you want to find words that behave grammatically alike, or words that appear in the same sentence-level constructions, the word-word matrix with a small window is the right tool. Words like "run" and "sprint," or "angry" and "furious," tend to show up in the same grammatical positions and thus accumulate similar word-word co-occurrence profiles.

Word-document matrices capture broader thematic associations. If you want to find words that belong to the same topic or domain, the word-document matrix is more appropriate. "Algorithm," "complexity," and "runtime" may not appear adjacent to each other often, but they co-occur in the same computer science articles, and that shared documentary environment marks them as thematically related.

There is a sense in which the word-document matrix is like a very wide word-word matrix. If you set the context window in a word-word matrix to span the entire document, you recover something close to the word-document matrix. The document is the limiting case of context window expansion.

For word-word matrices, the most important construction parameter is the context window. The window defines the neighborhood around each word that counts as "context." Getting this right, or at least understanding the consequences of different choices, is fundamental to building useful co-occurrence representations.

A symmetric window of size $k$ means that for each target word, we count co-occurrences with the $k$ words to its left and $k$ words to its right. Choosing $k$ is not arbitrary: it controls what kind of relationship the matrix captures.

Small windows ($k = 1$ or $2$) capture tight syntactic relationships. The words appearing immediately before or after a target word are often its grammatical neighbors: adjective-noun pairs, verb-object pairs, preposition-noun pairs. A window of 1 for "drank" will frequently find "he," "coffee," or "quickly." These are functional relationships that encode how a word behaves in sentences.

Large windows ($k = 5$ to $10$) capture semantic and topical relationships. Words appearing within a broader span tend to share the same topic or discourse. A window of 10 for "surgery" will capture "doctor," "hospital," "recovery," "anesthesia," and "patient." These are thematic relationships that encode what domain a word inhabits.

This window size effect is well-documented empirically. Levy and Goldberg (2014) showed that small windows produce vectors where nearest neighbors are words in the same syntactic role, while large windows produce vectors where nearest neighbors are topically similar words. Neither is wrong: they answer different questions about meaning.

To develop intuition, consider the word "bank." With a small window of 1-2, "bank" will co-occur with words like "river," "muddy," "steep" (in geographic contexts) and "loan," "branch," "account" (in financial contexts). The ambiguity is preserved because both senses occur, but the specific neighbors reveal which sense is active in each context. With a large window, "bank" in financial contexts will co-occur with a broad cloud of financial vocabulary, making the financial sense more statistically prominent if the corpus is business-heavy.

The window size also interacts with the genre and style of the corpus. In formal written prose, sentences tend to be long and informationally dense, so a window of 5 captures meaningful co-occurrences across clause boundaries. In conversational text or tweets, sentences are short and context is sparser, so even a window of 2 may span most of the sentence.

A practical consideration is whether context windows should cross sentence boundaries. Most implementations do not let context cross sentence boundaries. The sentence "The cat sat on the mat. The dog ran away." should not count "mat" as a context word for "dog," even though "mat" appears within a wide window if you naively count character positions.

Treating the sentence as a natural context unit is linguistically motivated. Sentences are coherent units of meaning, and co-occurrence within a sentence reflects semantic relationships better than co-occurrence across an arbitrary character span. The period between two sentences is a hard semantic break: the ideas being expressed are different, and the words on opposite sides of that break may have nothing to do with each other.

There are cases where crossing paragraph or section boundaries is useful, particularly for long-range coreference or topical coherence tasks. But for standard word-word co-occurrence construction, sentence-bounded windows are the norm.

Some implementations also discard stopwords from context counts. The idea is that "the" and "of" and "in" appear near almost everything and thus carry no discriminative information about word meaning. Including them creates massive counts for common words that dominate the matrix without contributing semantic signal. However, whether to remove stopwords is a design choice. In some tasks, the presence of function words in context is itself informative about grammatical structure, and removing them throws away that signal.

For each target word at position $t$ in a sentence of length $L$, with window size $k$, the context positions are:

For each context position $p$, we identify the word at that position and increment the matrix entry $C_{t\_\text{word},\ p\_\text{word}}$ by the appropriate weight (1 for uniform, $1/|t-p|$ for harmonic). This simple loop, applied to every token in the corpus, is all it takes to build the raw co-occurrence matrix.

The resulting matrix $C$ where $C_{ij}$ is large when word $j$ is a frequent context neighbor of word $i$. The row vector $\mathbf{c}_i$ for word $i$ is its distributional signature: the fingerprint of its verbal environment across the entire corpus.

A uniform window treats all co-occurrences equally regardless of distance. A word 5 positions away gets the same weight as a word 1 position away. This is simple, but it discards information: words adjacent to the target are usually more semantically informative than words further away.

Think about what the immediate neighbors of a word tell you versus what distant context tells you. The word immediately to the left of a noun is often a determiner, adjective, or possessive, and the word immediately to the right is often a verb or preposition. These tight grammatical constraints are highly specific to the target word. A word 5 positions away is more loosely associated: it is in the same sentence, likely on the same topic, but not necessarily in a tight grammatical relationship.

By giving equal weight to near and far context, a uniform window blurs the distinction between tight semantic relationships and loose topical associations. Distance weighting restores this distinction by making the contribution of each co-occurrence inversely proportional to how far away the context word was.

Distance weighting addresses this by assigning co-occurrences a weight inversely proportional to the distance between the two words. The most common scheme is harmonic weighting:

where $d$ is the distance in tokens between the target word and the context word. So a word 1 position away contributes 1 to the co-occurrence count, a word 2 positions away contributes 0.5, a word 3 positions away contributes 0.33, and so on.

For a target word at position $t$ in a sentence, the weighted co-occurrence count with word $j$ is:

where the sum runs over all positions $p$ within the window where word $j$ appears, and $|t - p|$ is the distance from the target to that occurrence.

The harmonic function $1/d$ has a specific property that makes it appealing: it assigns weight 1 to the nearest context, then diminishes smoothly. The weights for distances 1 through 5 are: 1.0, 0.5, 0.33, 0.25, 0.20. The first neighbor gets five times the weight of the fifth neighbor. This is not arbitrary: it reflects the empirical observation that the first few context words are typically the most informative about the target word's meaning.

Harmonic weighting is not the only option. Researchers have explored several alternatives.

Linear weighting uses weights that decrease linearly with distance: $w(d) = (k + 1 - d) / k$ for a window of size $k$. This gives a fixed weight of $k/k = 1$ to distance 1 and a weight of $1/k$ to distance $k$. Linear weighting is simpler to reason about than harmonic weighting and works well in practice.

Exponential weighting uses $w(d) = e^{-\alpha d}$ for some decay parameter $\alpha$. This drops off more steeply than harmonic weighting for small $\alpha$ and can be tuned to emphasize very tight context more aggressively.

Binary weighting (the uniform window) is the simplest: all context words get weight 1 regardless of distance. While it ignores distance information, it is the default in many implementations and often works well enough that the added complexity of distance weighting is not justified.

The choice of weighting scheme matters less than the choice of window size, but distance weighting consistently improves word vector quality in downstream tasks, at the cost of slightly more complex construction. GloVe, which we will discuss later in the book, implicitly captures distance weighting through its training objective: the GloVe loss function weights co-occurrence events, and words that appear very frequently near each other (often because they are grammatically adjacent) receive higher weight in training.

Most implementations build symmetric matrices: if "coffee" appears 3 positions to the right of "drank," that counts just as much as "coffee" appearing 3 positions to the left. But some tasks benefit from tracking direction.

In a symmetric context window, the matrix entry $C_{ij}$ counts all occurrences of word $j$ near word $i$, regardless of whether $j$ came before or after $i$. This makes $C$ approximately symmetric: $C_{ij} \approx C_{ji}$. The matrix treats "before" and "after" contexts identically.

In a directional (or asymmetric) context, the matrix tracks whether word $j$ appeared to the left or to the right of word $i$. This doubles the effective vocabulary of context features: instead of one count per word pair, you get two: left-occurrence and right-occurrence. Alternatively, directionality can be used for dependency-based contexts, where context is defined by grammatical relationships rather than positional proximity.

Directional contexts capture linguistic asymmetry. In English, adjectives typically precede nouns ("red apple"), so the left context of "apple" frequently contains adjectives while the right context does not. A symmetric matrix blurs this distinction. A directional matrix preserves it, which can be useful for capturing part-of-speech or syntactic roles.

Consider the word "quickly." To its left, you typically find nouns or clause boundaries. To its right, you typically find nothing relevant (it often comes at the end of a verb phrase). The word "running," by contrast, frequently has a subject (noun) to its left and an object or complement to its right. These asymmetric profiles carry rich syntactic information that symmetric counting discards.

Directional contexts also help with discovering semantic relations that have a direction. "Paris is the capital of France" implies a directed relationship between "Paris" and "France" that is not symmetric. Dependency-based distributional models (Padó and Lapata, 2007; Levy and Goldberg, 2014) use grammatical parse trees to define context, where context words are those in specific syntactic relationships (subject, object, modifier) to the target word rather than mere positional neighbors. This produces more precise semantic representations but requires a dependency parser as a preprocessing step.

Symmetric matrices are simpler to construct and work well for most semantic similarity tasks. Directional matrices are more common in specialized applications involving dependency parsing or syntactic role analysis. For the remainder of this chapter, we focus on the symmetric case, which is the standard choice in most distributional semantics work.

Before moving to construction algorithms, it is worth understanding the statistical structure of co-occurrence matrices, because this structure motivates every subsequent modification to the raw counts.

Co-occurrence counts follow a power law distribution with extreme skew. A small number of word pairs accumulate enormous counts while the vast majority of pairs have counts of 0 or 1. This mirrors Zipf's law for word frequencies: the most frequent word in a language is roughly twice as common as the second most frequent, three times as common as the third, and so on. Co-occurrence counts exhibit the same heavy-tailed behavior.

In practice, this means that a handful of function word pairs ("the of," "the in," "the and") dominate the matrix by raw counts. "The" co-occurs with almost every content word in the language, accumulating counts in the millions for large corpora. "Cat" appears near "the" far more often than it appears near any other word, simply because "the" is everywhere.

This function word dominance is a serious problem for semantic similarity. If two words are judged similar by their raw co-occurrence counts, the most similar word to almost anything will be a function word, because function words share high co-occurrence counts with almost everything. The representations become informationally degraded: there is so much noise from high-frequency words that the signal from semantically meaningful co-occurrences is buried.

This is why raw co-occurrence matrices are rarely used directly for semantic similarity. They are almost always reweighted using PMI (Pointwise Mutual Information) or TF-IDF or some similar measure that discounts frequent words and amplifies rare but meaningful associations. We cover PMI in the next chapter.

The critical practical challenge with co-occurrence matrices is sparsity. Real vocabulary sizes range from tens of thousands to hundreds of thousands of words. A $V \times V$ matrix with $V = 100{,}000$ has $10^{10}$ entries. But most word pairs never co-occur. In any realistic corpus, even a large one, only a tiny fraction of all possible word pairs appear near each other.

The sparsity is structural, not incidental. Most words are specialized: "photosynthesis" co-occurs with "chlorophyll" and "sunlight," not with "mortgage" or "carburetor." The distribution of co-occurrence counts follows a power law: a small number of highly common word pairs (function words like "the," "of," "in" appearing near almost everything) accumulate huge counts, while the vast majority of content word pairs have counts of 1 or 0.

Concretely, for a vocabulary of $V = 50{,}000$ words, the matrix has $2.5 \times 10^9$ entries. If the corpus contains 1 billion tokens with a window of size 5, the total number of observed co-occurrence events is roughly $10 \times 10^9 = 10^{10}$ (10 context positions per token), but many of these will repeat the same pairs. Empirically, only around 0.1% to 1% of all possible word pairs in a typical corpus have nonzero counts.

Storing a dense matrix of 2.5 billion entries at 4 bytes each requires 10 GB of RAM just for a $50{,}000 \times 50{,}000$ matrix. This is infeasible for most applications. The solution is sparse storage: represent only the nonzero entries explicitly using data structures like coordinate lists (COO), compressed sparse rows (CSR), or hash maps.

The choice of sparse format affects downstream operations. CSR format is best when you frequently need to retrieve all context words of a given target word (a row slice), which is the common case for computing word similarity. COO format is easiest to build incrementally as you stream through the corpus. In practice, most implementations build in COO or hash map format and then convert to CSR for computation.

A related challenge is deciding which words to include in the vocabulary. With a large enough corpus, even very rare words accumulate a few co-occurrence events. Including all of them makes the matrix enormous while adding mostly noise: the co-occurrence statistics of a word that appears only twice are statistically unreliable.

Common practice is minimum frequency thresholding. Any word appearing fewer than some cutoff (typically 5 to 20 times in the corpus) is discarded from the vocabulary. This has two benefits: it reduces the matrix size, and it improves the reliability of the remaining statistics. The remaining words have enough observations for their co-occurrence counts to reflect stable linguistic patterns rather than sampling noise.

After frequency thresholding, it is also common to remove high-frequency stopwords. These are words like "the," "a," "in," "of" that appear so often that their co-occurrence counts with almost every content word are high. Their presence in the vocabulary inflates the matrix without adding discriminative semantic information. Whether to remove them depends on the application: for syntax-focused tasks, keeping them is often beneficial; for semantic similarity tasks, removing them often improves the quality of the representations.

Building a co-occurrence matrix from a large corpus requires careful design. A naive approach, iterating over all token pairs within windows, is $O(N \cdot k)$ for a corpus of $N$ tokens and window size $k$. That is manageable for modest corpora, but large corpora require attention to memory and parallelism.

The standard approach streams through the corpus one sentence at a time, maintaining a sliding window. For each token in the window, we emit a (target, context) pair and increment the corresponding matrix entry. Using a hash map to accumulate counts requires $O(1)$ amortized per update and avoids allocating a full $V \times V$ matrix.

The key insight in streaming construction is that you never need to hold the entire corpus in memory. You process it one sentence at a time, update the count map, and discard the sentence. The count map grows only as large as the number of distinct word pairs observed, which for realistic corpora is much smaller than $V^2$.

After processing the corpus, the hash map is converted to CSR format for efficient numerical operations. The construction cost is $O(N \cdot k)$ time and $O(|\text{nonzeros}|)$ space, where $|\text{nonzeros}|$ is the number of distinct co-occurrence pairs observed. For large corpora, this is typically in the hundreds of millions of pairs: far smaller than $V^2$ but large enough to require careful memory management.

Before building the matrix, you need a fixed vocabulary. Common practice is a two-pass approach:

1. First pass: Count all word frequencies, discard words below a minimum frequency threshold (typically 5-10 occurrences).
2. Second pass: Build the co-occurrence matrix using only the retained vocabulary.

Low-frequency words are discarded because their co-occurrence statistics are unreliable: a word appearing twice in the corpus will have co-occurrence counts that are essentially noise. Discarding rare words also dramatically reduces vocabulary size and matrix density.

The frequency threshold is a hyperparameter that trades off vocabulary coverage for statistical reliability. A lower threshold keeps more words but introduces more noisy rows into the matrix. A higher threshold keeps only well-attested words but excludes rare technical terms, proper nouns, and neologisms. For large corpora, a threshold of 5-20 is typical; for small corpora, even a threshold of 2 may be appropriate to preserve enough words for meaningful analysis.

For very large corpora, the construction can be parallelized by partitioning the corpus into chunks and processing each chunk independently. Each worker produces a partial co-occurrence map; these maps are merged at the end by summing counts for shared pairs. This scales linearly with the number of workers, making it possible to build co-occurrence matrices from billions of tokens in a matter of hours.

GloVe's original implementation (Pennington et al., 2014) uses this approach with multiple threads and efficient binary file formats to build co-occurrence counts from Wikipedia-scale corpora (billions of tokens) in hours rather than days. The implementation writes partial counts to disk in COO format, then merges and sorts them before converting to the final matrix representation. This external memory sorting approach allows corpora far larger than available RAM to be processed efficiently.

For the biggest corpora, such as C4 (750 GB of text) or the Pile (800 GB), even this approach requires careful engineering. Modern practice typically uses distributed computing frameworks (Spark, Dask) to partition the corpus across many machines, each building a local co-occurrence map, with a final reduce step that sums counts across partitions.

Let's trace through a small example to make the construction concrete. Consider this three-sentence corpus with a window of size 2:

1. "the cat sat on the mat"
2. "the cat ate the rat"
3. "the dog sat on the log"

The vocabulary (excluding stopwords for clarity, though real implementations usually include them) is: {cat, sat, mat, ate, rat, dog, log, on}.

For the word "sat" with window $k = 2$, the contexts are:

• In sentence 1: "cat" (distance 1 left), "on" (distance 1 right), "the" (distance 2 right)
• In sentence 3: "dog" (distance 1 left), "on" (distance 1 right), "the" (distance 2 right)

So the row for "sat" in the co-occurrence matrix will have counts: cat: 1, on: 2, dog: 1, and "the": 2 (within the vocabulary).

With harmonic distance weighting: cat gets weight 1.0 (distance 1), on gets 1.0 (distance 1), dog gets 1.0 (distance 1). For "the" at distance 2, it gets 0.5 in each sentence, total 1.0.

Now let's trace the row for "cat." In sentence 1, "cat" appears at position 1 (0-indexed). Context words within window 2 are: "the" at distance 1 (left), "sat" at distance 1 (right), "on" at distance 2 (right). In sentence 2, "cat" appears at position 1 again. Context words: "the" at distance 1 (left), "ate" at distance 1 (right), "the" at distance 2 (right).

Summing across sentences:

• "the": appears at distance 1 in sentences 1 and 2 (uniform count: 2), and at distance 2 in sentence 2 (uniform count: 1), giving uniform total 3.
• "sat": appears at distance 1 in sentence 1 (uniform count: 1).
• "ate": appears at distance 1 in sentence 2 (uniform count: 1).
• "on": appears at distance 2 in sentence 1 (uniform count: 1).

With harmonic weighting, the count for "the" would be $1.0 + 1.0 + 0.5 = 2.5$, compared to the uniform count of 3. The relative reduction for "the" is smaller here, but in a large corpus where "the" appears at all distances from many words, harmonic weighting substantially reduces its dominance.

The full matrix construction follows this same process for every token in the corpus, row by row, for every word in the vocabulary.

Let's implement co-occurrence matrix construction from scratch, then use it to demonstrate the key concepts.

We will start by building a simple corpus and vocabulary pipeline.

The word-word matrix tends to surface words that appear in the same immediate grammatical contexts (words that co-occur locally with "cat"), while the word-document matrix surfaces words that appear in the same documents (thematically related words). Both are valid and useful depending on the downstream task.

Let's visualize the co-occurrence matrix as a heatmap and the effect of window size on the captured relationships.

The comparison highlights the complementary strengths of each matrix type. In the word-word matrix, words that function similarly in sentences tend to cluster near each other, even if they appear in different documents. In the word-document matrix, words that populate similar topics and genres have high similarity, even if they rarely appear in the same sentence. For semantic search and information retrieval tasks, the word-document matrix is usually more appropriate. For semantic similarity at the word level, the word-word matrix is typically preferred.

Let's quantify how window size changes the semantic neighborhood of words.

The window size effect is clear: as the window grows, "dog" and "cat" accumulate more shared context words ("the," "park," "ran," "in"), which pushes their cosine similarity higher. This confirms the theoretical prediction: larger windows capture more of the topical similarity between semantically related words. A small window captures only the tightest syntactic patterns, where "dog" and "cat" might differ (because they appear in slightly different sentence frames), while a large window captures the broader distributional environment they share.

For real-scale corpora, we need sparse storage. Let's demonstrate building a sparse co-occurrence matrix using scipy's CSR format, and compare memory usage against dense storage.

The memory advantage of sparse storage scales quadratically with vocabulary size. A vocabulary of 50,000 words would require 20 GB of RAM in dense format but only hundreds of megabytes in sparse format, making large-scale co-occurrence matrices practically tractable. This quadratic scaling is the reason sparse storage is non-negotiable for real applications: the savings become astronomically large as vocabulary size grows.

One of the most instructive properties of co-occurrence matrices is the distribution of their nonzero counts. Let's visualize it to see the power law behavior in action.

The histogram confirms the heavy-tailed structure: most observed word pairs co-occur only once or twice, while a few pairs involving function words accumulate much higher counts. On a log scale, this distribution has a roughly linear shape, which is characteristic of power laws. The long tail of high counts is dominated by common grammatical patterns: "the" co-occurring with every noun, "in" co-occurring with every location noun, and so on. These patterns carry almost no discriminative semantic information, which is precisely why PMI weighting (coming in the next chapter) is essential.

The key parameters for co-occurrence matrix construction are:

• window_size: Controls the context window half-size $k$. Smaller values (1-2) capture syntactic relationships; larger values (5-10) capture semantic and topical relationships.
• weighted: Whether to apply harmonic distance weighting ($1/d$). Distance weighting reduces function word dominance and typically improves downstream word vector quality.
• min_frequency: Minimum word frequency for vocabulary inclusion. Rare words have unreliable statistics; values of 5-10 are common in practice.
• symmetric: Whether to treat left and right contexts equally (symmetric) or separately (directional). Symmetric is standard for most semantic similarity tasks.
• sentence_boundary: Whether context windows respect sentence boundaries. Enforcing sentence boundaries is linguistically motivated and standard practice.

Raw co-occurrence counts are only the starting point of distributional semantics. The matrix you build by counting co-occurrences is valuable, but it has well-known failure modes that make it unsuitable for direct use in most semantic tasks. Understanding these failure modes and how they are addressed is essential context for the chapters that follow.

The dominant failure mode of raw co-occurrence matrices is function word inflation. Words like "the," "of," "in," "and," and "a" appear near almost every content word in the language. Their co-occurrence counts with all words are high, not because they are semantically related to those words, but because they are grammatically pervasive. This means that if you measure the cosine similarity between any two words using raw co-occurrence counts, the similarity will be strongly inflated by the shared high counts with function words.

Consider asking: are "dog" and "cat" more similar to each other than "dog" is to "algorithm"? Intuitively yes, obviously. But in the raw co-occurrence matrix, both "cat" and "algorithm" will have high counts with "the," "in," "a," and other function words. These shared high counts can dominate the cosine similarity computation and obscure the semantic differences. The signal from meaningful co-occurrences (dog-cat sharing "pet," "animal," "chase") is buried under the noise from function word co-occurrences that both words share with every other word.

The solution is Pointwise Mutual Information (PMI), which rescales co-occurrence counts to measure statistical association rather than raw frequency. PMI asks: how much more often do words $i$ and $j$ co-occur than you would expect if they were independent? Words that co-occur only as often as expected by chance get a PMI of zero; words that co-occur more than expected get a positive PMI; words that co-occur less than expected get a negative PMI. We cover this in detail in the next chapter.

Even with PMI weighting, the word vectors produced by co-occurrence matrices are in a very high-dimensional space. Each word is represented as a vector of length $V$, where $V$ might be 50,000 or 100,000. Most of these dimensions are zero or very small. Computing cosine similarity in such high-dimensional spaces is computationally expensive, and the curse of dimensionality means that distances become increasingly concentrated as dimensionality grows.

The geometric intuition breaks down in high dimensions. In 2D or 3D, most points are well-separated. In 50,000 dimensions, nearly all pairs of random vectors have approximately the same cosine similarity (close to zero), which means the similarity measure becomes uninformative for most pairs.

The solution is Latent Semantic Analysis (LSA), which applies Singular Value Decomposition (SVD) to the PMI-weighted co-occurrence matrix to compress it into a dense, low-dimensional representation (typically 100-300 dimensions). The SVD extracts the most important directions of variation in the matrix, discarding the noise and keeping the signal. Words that share similar semantic contexts end up close together in this compressed space, even if their raw co-occurrence profiles differed in detail.

The classical pipeline for distributional word representations works as follows. You start with a co-occurrence matrix built from raw counts, apply PMI weighting to correct for function word inflation, apply SVD to reduce dimensionality and remove noise, and end up with dense vector representations for words. This is the LSA pipeline, and it was the dominant approach to distributional word representations from the mid-1990s through approximately 2013.

When Word2Vec appeared in 2013 (Mikolov et al.), it seemed to bypass this pipeline entirely, learning dense word vectors directly from raw text through a neural network prediction objective. But subsequent analysis by Levy and Goldberg (2014) showed that Word2Vec's skip-gram model with negative sampling is implicitly performing a factorization of a shifted PMI matrix. The neural approach and the matrix factorization approach are mathematically related; Word2Vec is not doing something entirely different from LSA, it is doing something subtly different in a much more computationally efficient way.

This connection matters because it means the concepts you are learning in this chapter, the co-occurrence matrix, PMI weighting, and SVD, are not obsolete classical techniques. They are the foundational substrate from which all subsequent word representation methods are derived. Transformer-based contextual embeddings differ from static distributional representations, but the distributional hypothesis that motivates co-occurrence counting is still the conceptual foundation. The transformer learns which context to attend to dynamically, but the notion that context determines meaning is unchanged from Firth's original insight.

Co-occurrence matrices made distributional semantics computationally tractable for the first time, but they also introduced several limitations that shaped subsequent research.

The most pressing limitation is scalability. Even with sparse storage, a $V \times V$ matrix for a vocabulary of 500,000 words requires billions of nonzero entries to be handled. The construction itself requires a full pass through the corpus for every vocabulary size configuration, and modifying the window size or weighting scheme requires rebuilding the matrix from scratch. For research applications that need to explore many configurations, this computational cost adds up.

The matrix is also static: once built, it does not update as new text arrives. In a production search system that needs to incorporate new documents continuously, a static co-occurrence matrix becomes outdated and requires periodic full rebuilds. This is one of the practical motivations for moving toward online learning methods like Word2Vec, which can be updated incrementally.

The raw counts are also poor representations on their own: function words like "the," "of," and "in" co-occur with almost every content word, creating massive count imbalances that flood the signal from meaningful associations. This motivated post-processing with TF-IDF weighting in the document context, and with PMI (Pointwise Mutual Information) in the word-word context. We cover PMI in the next chapter.

The dominance of function words is a symptom of a deeper issue about what the raw matrix is measuring. Co-occurrence counts conflate two distinct types of association: grammatical co-occurrence (words that appear together because of syntactic constraints, like "the" appearing before nouns) and semantic co-occurrence (words that appear together because they refer to related things). Function words primarily create grammatical co-occurrences, while content words primarily create semantic co-occurrences. PMI weighting cleanly separates these two types by normalizing for each word's marginal frequency.

A deeper limitation is dimensionality. A word's representation is a vector of length $V$, often 50,000 or more dimensions. Most of these dimensions are zero or nearly zero. Operations like cosine similarity are computationally expensive in such high-dimensional sparse spaces, and the curse of dimensionality means that cosine distances become increasingly uninformative as dimensionality grows. This limitation motivated Latent Semantic Analysis (LSA), which applies Singular Value Decomposition to compress co-occurrence matrices into dense, low-dimensional representations. LSA is covered in the SVD chapter.

Another fundamental limitation of co-occurrence matrices, one that persists even after PMI weighting and SVD compression, is their inability to handle polysemy. Every word gets a single vector, regardless of how many senses it has. "Bank" in the financial sense and "bank" in the river sense collapse into a single point in the vector space. The vector ends up in an awkward intermediate position that is not fully representative of either sense.

This context blindness extends beyond polysemy to all forms of contextual variation. The meaning of "good" in "a good actor" and "a good person" is subtly different, but a static co-occurrence matrix assigns both usages to the same vector. This motivated the shift toward contextual word embeddings, where the representation of a word depends on its specific context. ELMo (2018) and BERT (2018) are the first systems to produce such contextual representations at scale, and the transformer architecture that enables them can be understood as a learned, dynamic context weighting mechanism. Instead of a fixed window, the transformer learns to weight context positions differently for each occurrence of a word, effectively learning a different vector for each context.

Despite these limitations, the impact of co-occurrence matrices was foundational. They provided the first systematic way to compute word similarity from distributional evidence, without any hand-crafted rules or semantic ontologies. The computational linguists of the 1990s and 2000s used these matrices to demonstrate that meaningful semantic relationships like synonymy, antonymy, and topical relatedness could be discovered automatically from text statistics. This was a conceptual breakthrough that opened the door to Word2Vec, GloVe, and eventually transformer-based representations.

The question "can computers understand meaning?" had always been answered with skepticism or appeals to philosophical difficulty. Co-occurrence matrices gave a concrete, empirically grounded answer: not full understanding, but a measurable approximation of semantic similarity that correlates strongly with human judgments. When you showed researchers in 1995 that a co-occurrence matrix could correctly identify "surgeon" as more similar to "physician" than to "carpenter," without any built-in knowledge of medicine, it changed how the field thought about the relationship between text statistics and meaning.

Co-occurrence matrices also made explicit the fundamental tradeoff that persists throughout distributional semantics: the choice of context definition determines what kind of similarity the representation captures. This insight, that there is no single correct definition of "context," continues to influence how we design contextual representations in modern language models. Transformer attention, in some sense, is a learned context weighting mechanism: instead of a fixed window, the model learns to weight context positions dynamically based on content. The co-occurrence matrix is not a primitive predecessor of the transformer; it is the same idea expressed more simply.

Co-occurrence matrices transform the distributional hypothesis into a concrete data structure. The key ideas are:

• Word-word matrices count how often words appear in each other's context window, capturing local semantic and syntactic relationships. Each row is a distributional signature for a word in terms of its context neighbors.
• Word-document matrices count word occurrences across documents, capturing topical and thematic relationships. They form the basis of TF-IDF and Latent Semantic Analysis.
• Window size controls the type of relationship captured: small windows (1-2) emphasize syntactic patterns; large windows (5-10) emphasize semantic and topical similarity.
• Distance weighting (typically $1/d$) reduces the influence of distant context words, amplifies signal from adjacent words, and improves the quality of downstream word vectors.
• Symmetric vs. directional contexts determine whether the position of context words relative to the target is tracked. Symmetric is standard for semantic similarity; directional contexts are used in dependency-based distributional models.
• Sparsity is unavoidable: most word pairs never co-occur, so sparse matrix formats (COO, CSR, hash maps) are essential for tractable storage and computation.
• Efficient construction streams through the corpus once, building a hash map of (word, context) counts before converting to sparse matrix format. Parallelization allows Wikipedia-scale corpora to be processed in hours.
• Function word dominance and the power law structure of counts motivate statistical reweighting. Raw counts alone are poor semantic representations.

The limitations of raw co-occurrence matrices, particularly the dominance of high-frequency words and the curse of dimensionality, motivated two important extensions: PMI weighting (next chapter) to rescale counts by statistical association, and SVD (a later chapter) to compress the matrix into dense, informative representations. Together, these three techniques form the classical pipeline for distributional word representations, and they remain the conceptual foundation on which every subsequent advance in word embeddings was built.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about co-occurrence matrices.