Word Embeddings and Dense Vectors

A sparse representation of a word, in the distributional tradition, is a vector indexed by every possible context feature — often every other word in the vocabulary — where entry $j$ records how often the word co-occurs with context word $j$ across a corpus. If the vocabulary has size $|V| \approx 50{,}000$ or more, each word vector has tens of thousands of dimensions, and almost all entries are zero, because most word pairs never co-occur. These raw counts are often reweighted, for example using Pointwise Mutual Information (PMI),

which measures how much more often $w$ and $c$ co-occur than chance would predict. Even after reweighting, the vectors remain high-dimensional and sparse. A dense embedding is a vector $\vec{v}_w \in \mathbb{R}^d$ for word $w$, where $d$ is small (commonly 50–300) and every dimension typically has a nonzero, real value. Crucially, the individual dimensions of a dense embedding usually have no fixed human-interpretable meaning — dimension 47 is not "co-occurs with dog." Instead, meaning is encoded in the overall geometric configuration: similar words are close together (small Euclidean distance, or equivalently high cosine similarity), and directions in the space can correspond to semantic or syntactic relationships. The move from sparse to dense is fundamentally a dimensionality reduction: dense embeddings are a compressed, low-rank approximation of the information contained in the full sparse co-occurrence statistics. This can be done explicitly, by factorizing a sparse PMI or count matrix with the truncated Singular Value Decomposition (SVD), or implicitly, by training a small neural network to predict context words from a target word (or vice versa), where the network's learned weight rows become the embeddings — this implicit route is the Word2Vec Skip-gram approach, foreshadowed here and detailed elsewhere. Either way, the resulting vectors inherit the distributional hypothesis's core assumption — words in similar contexts have similar meaning — but express it through smooth, dense geometry rather than exact, sparse counting.

There are two complementary ways to obtain dense embeddings from a corpus: count-then-reduce (explicit matrix factorization) and predict-directly (implicit neural training, previewed here). Understanding count-then-reduce first makes the predict-directly family easier to appreciate, since both ultimately approximate the same underlying co-occurrence structure.

Step 1 — Build the sparse co-occurrence matrix. Slide a context window of size $k$ (e.g., $k=4$) across the corpus. For each target word $w$ and each context word $c$ appearing within the window, increment a count $\#(w, c)$. This produces a matrix $M \in \mathbb{R}^{|V| \times |V|}$ (or $|V| \times |C|$ if contexts are restricted).

Step 2 — Reweight the counts. Raw counts overweight very frequent words (like "the"), so entries are typically transformed into Positive PMI (PPMI):

Clipping negative PMI to zero avoids unreliable, noisy estimates of negative association from sparse counts.

Step 3 — Reduce dimensionality. Apply truncated SVD to the PPMI matrix $M$:

keeping only the top $d$ singular values. The rows of $U_d \Sigma_d$ (or sometimes $U_d \Sigma_d^{1/2}$) become the dense word embeddings, one length-$d$ vector per word.

Step 4 — Use the vectors. Two words $w_1, w_2$ are considered similar when their embeddings have high cosine similarity:

This process is exactly what later, more scalable algorithms approximate without ever materializing the full $|V| \times |V|$ matrix — a key motivation for the predict-directly family. ``` ALGORITHM BuildDenseEmbeddings(corpus, vocab, window_size k, target_dim d) // Step 1: sparse co-occurrence counts let counts be a |vocab| x |vocab| sparse matrix, initialized to 0 for each position i in corpus: w := corpus[i] for j in (i-k) .. (i+k), j != i, j within corpus bounds: c := corpus[j] counts[w][c] += 1 // Step 2: reweight with PPMI total := sum of all entries in counts for each nonzero entry counts[w][c]: p_wc := counts[w][c] / total p_w := rowSum(counts, w) / total p_c := colSum(counts, c) / total pmi := log( p_wc / (p_w p_c) ) PPMI[w][c] := max(pmi, 0) // Step 3: low-rank factorization (U, Sigma, V) := TruncatedSVD(PPMI, rank = d) embeddings := U Sigma // |vocab| x d dense matrix return embeddings FUNCTION CosineSimilarity(v1, v2) return dot(v1, v2) / (norm(v1) norm(v2)) ``` The pseudocode is deliberately generic: swapping the SVD step for a neural predictor (trained with gradient descent to predict context words from a target word) yields the Word2Vec-style pipeline, while replacing raw PPMI factorization with a weighted least-squares objective over log co-occurrence counts yields GloVe. Both are covered in their own articles; the point here is that <strong>all of these methods share the same goal</strong> — compress sparse distributional statistics into dense vectors — and differ only in how* the compression is computed.

Space. A sparse co-occurrence matrix over vocabulary size $|V|$ nominally requires $O(|V|^2)$ storage in dense form, but since it is sparse (most word pairs never co-occur), it is stored with $O(N)$ nonzero entries, where $N$ is the number of distinct co-occurring pairs observed in the corpus — typically much smaller than $|V|^2$ but still large (millions to billions for big corpora). Dense embeddings require only $O(|V| \cdot d)$ space, with $d \ll |V|$. For $|V| = 50{,}000$ and $d = 300$, that is 15 million floats versus a sparse matrix that can easily have hundreds of millions of nonzero entries — a substantial and practically important reduction.

Time. Building the co-occurrence counts is $O(T \cdot k)$, where $T$ is corpus length in tokens and $k$ is window size, since each token contributes $O(k)$ increments. Computing PPMI over the nonzero entries is $O(N)$. Truncated SVD to rank $d$ on a sparse matrix with $N$ nonzeros costs roughly $O(N \cdot d)$ per iteration using iterative methods (e.g., randomized SVD or Lanczos), which is far cheaper than the $O(|V|^3)$ cost of a naive full-matrix SVD. This efficiency is what makes explicit factorization tractable at all — a naive dense SVD on a 50,000-dimensional matrix would be computationally prohibitive.

Why dense vectors generalize better (a correctness argument). Sparse vectors treat every vocabulary dimension as an independent, orthogonal feature: the cosine similarity between two words is nonzero only if they share literal context words in the raw count vector. Two words can be perfectly synonymous yet share almost no exact contexts in a finite corpus (data sparsity), so sparse cosine similarity systematically underestimates true semantic similarity. The truncated SVD step is a rank-$d$ approximation that provably minimizes the Frobenius-norm reconstruction error among all rank-$d$ matrices (the Eckart–Young theorem):

This means the dense approximation retains the dominant, statistically reliable co-occurrence patterns (the top singular directions, which capture the strongest, most consistent distributional regularities) while discarding directions dominated by sampling noise (weak, idiosyncratic co-occurrences that occur too rarely to be trustworthy). Two words that are synonyms but never literally co-occur with the exact same rare context words will still end up with similar reconstructed profiles, because their sparse rows are both well-approximated by combinations of the same dominant latent directions. This is the formal sense in which dimensionality reduction lets semantically related words "share" dimensions instead of being confined to disjoint sparse coordinates.

Tradeoffs to be honest about. Dense embeddings sacrifice interpretability: no single dimension of a learned embedding has a clean meaning, unlike a sparse PPMI vector whose dimension $j$ literally means "co-occurs with context word $c_j$." Dense embeddings also require choosing $d$ and other hyperparameters, and different training runs (even of the same algorithm) can produce embeddings with different, non-comparable coordinate systems (only relative geometry — distances and directions — is meaningful, not absolute coordinate values). Explicit SVD-based approaches also still require building the full sparse co-occurrence matrix at least once, which is memory-intensive for very large corpora; this is precisely the practical bottleneck that motivates predict-directly neural methods like Word2Vec, which never materialize the co-occurrence matrix explicitly.

Consider a toy corpus with the sentences: ``` the cat sat on the mat the dog sat on the rug the car and the automobile are both vehicles ``` With a symmetric window of size 2, we tally raw co-occurrence counts for a few target words against a small context vocabulary. Below is a simplified sparse count table (rows are target words, columns are selected context words):

Notice: cat and dog already have identical sparse count rows here (both co-occur with "the" and "sat" the same number of times, and with nothing else in this tiny table), so sparse cosine similarity happens to detect their similarity in this toy case. But car and automobile — arguably even more similar in meaning — have disjoint nonzero columns aside from "the": car never co-occurs with "vehicles" in this excerpt, and automobile never co-occurs with "car" directly. Their raw sparse cosine similarity is low, computed directly from the table:

This is not terrible in this tiny toy example, but in a realistic corpus with tens of thousands of context columns, "car" and "automobile" would share only a handful of exact contexts by chance, and PPMI-based sparse cosine similarity would substantially underestimate their true semantic closeness, since most of their individual (sparse) co-occurrence partners would not literally overlap. Now apply the dimensionality-reduction idea. Suppose after PPMI weighting and truncated SVD to $d = 2$, the four words are mapped to dense vectors (illustrative values consistent with the qualitative pattern SVD would recover from richer real data):

Now cosine similarity between car and automobile in this dense space:

The dense representation pulls "car" and "automobile" much closer together — near-identical — because both words' sparse rows, despite having few literal overlapping columns, are well-approximated by the same dominant latent direction (something like a "vehicle" concept direction) once weak individual context signals are aggregated by the SVD. This illustrates concretely why dense vectors generalize: the compression step lets words share statistical strength through shared latent structure rather than requiring identical literal contexts.

Dense word embeddings became the default input layer for essentially all neural NLP systems following their popularization: text classifiers, part-of-speech taggers, named-entity recognizers, and machine translation systems all began by mapping input tokens to dense vectors before any further computation. Search engines and recommendation systems use embedding similarity to match queries to semantically related documents even when no exact keyword overlap exists, directly exploiting the generalization advantage described above. Modern large language models still rely on the same fundamental idea at their input layer — an embedding matrix mapping each token to a dense vector — though the vectors are now typically learned jointly with a much larger downstream network rather than pretrained separately. Understanding dense embeddings is therefore a prerequisite for understanding Word2Vec Skip-gram, GloVe, and the broader geometric phenomena studied in Embedding Geometry and Analogies, as well as the token-embedding layers found at the base of every modern transformer-based system.

Ask the tutor: How does the Word2Vec skip-gram objective implicitly perform a factorization similar to the PPMI/SVD pipeline described here?