Co-occurrence Matrices › Statistical Properties of Co-occurrence Matrices

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.