Embeddings and Representation Learning

Formally, let $V = \{1, 2, \dots, |V|\}$ be a discrete vocabulary of entities (words, item IDs, graph nodes). An embedding is a function $f: V \to \mathbb{R}^d$ that is typically implemented as a matrix $E \in \mathbb{R}^{|V| \times d}$, where row $E_i$ is the vector for entity $i$. Unlike a hand-crafted feature map, $E$ is learned: its entries are parameters trained jointly with, or as a precursor to, a downstream task. The dimension $d$ (often 50–1024) is far smaller than $|V|$ (often $10^4$–$10^7$), so the embedding table performs a kind of compression analogous to the bottleneck of an autoencoder — except the "input" is a one-hot indicator rather than a rich signal, and the compression target is distributional co-occurrence rather than reconstruction of the input itself. The distributional hypothesis, articulated by linguists (Firth, Harris) well before deep learning, states that entities occurring in similar contexts tend to have similar meaning. This is the statistical principle that makes embeddings learnable at all: if the training objective rewards vectors that predict correct contexts (or co-occurrence statistics), then vectors for distributionally similar entities are pushed toward similar regions of space, purely as a byproduct of optimizing a predictive or reconstructive loss. No human ever labels "king" and "queen" as related; the geometry emerges from statistics. Two broad families realize this idea. Count-based methods (e.g., latent semantic analysis, GloVe) build an explicit co-occurrence matrix $X \in \mathbb{R}^{|V|\times|V|}$ (entries $X_{ij}$ = how often $i$ and $j$ co-occur) and factorize or regress on it directly, analogous to how an undercomplete autoencoder finds a low-rank code that best reconstructs high-dimensional input. Predictive methods (e.g., word2vec) never materialize the co-occurrence matrix; instead they train a lightweight neural network to predict context from target (or vice versa), and the learned weight matrix becomes the embedding table. Both families provably converge, under mild assumptions, toward embeddings whose inner products approximate a (shifted, scaled) pointwise mutual information matrix — this is the theoretical bridge connecting the two views, established rigorously by Levy & Goldberg (2014).

We walk through the skip-gram model with negative sampling (SGNS), the algorithm underlying word2vec, since it is the cleanest illustration of embedding mechanics and generalizes directly to non-textual entities (items, nodes, users).

Setup. Fix a window size $w$. For each position $t$ in a corpus, the target word $w_t$ and each context word $w_{t+j}$ for $j \in [-w, w] \setminus \{0\}$ form a training pair $(w_t, w_{t+j})$. Maintain two embedding matrices: $E \in \mathbb{R}^{|V|\times d}$ for target (input) vectors and $C \in \mathbb{R}^{|V|\times d}$ for context (output) vectors. The probability that word $c$ is a true context of word $t$ is modeled with a sigmoid of the dot product:

Negative sampling. Computing a softmax over the entire vocabulary for every pair is $O(|V|)$ per update — prohibitive when $|V|$ is millions. Instead, SGNS samples $k$ "negative" words from a noise distribution $P_n$ (typically unigram frequency raised to the power $0.75$, which smooths out very frequent words) and trains a binary classifier: is $(t,c)$ a real pair or a random pair? The loss for one true pair $(t,c)$ with negatives $n_1,\dots,n_k$ is:

This turns an expensive multi-class problem into $k+1$ cheap binary ones. ``` ALGORITHM SkipGramNegativeSampling(corpus, d, window, k, lr, epochs) Input: corpus sequence of tokens d embedding dimension window max context radius k number of negative samples per positive pair lr learning rate epochs number of passes over corpus Output: E, C |V| x d target and context embedding matrices V <- build_vocabulary(corpus) E <- random_init(|V|, d) # target embeddings C <- random_init(|V|, d) # context embeddings noise_dist <- unigram_freq(V) ** 0.75, normalized to sum to 1 for epoch in 1..epochs: for t in positions of corpus: window_size <- random_int(1, window) # dynamic window (as in word2vec) for j in -window_size..window_size, j != 0: if t + j out of corpus bounds: continue target <- corpus[t] context <- corpus[t + j]

# positive update score <- sigmoid(dot(E[target], C[context])) grad_common <- lr (1 - score) E[target] += grad_common C[context] C[context] += grad_common * E[target]

# negative updates for i in 1..k: neg <- sample(noise_dist) while neg == context: neg <- sample(noise_dist) score_neg <- sigmoid(dot(E[target], C[neg])) grad_neg <- lr (0 - score_neg) E[target] += grad_neg C[neg] C[neg] += grad_neg * E[target] return E, C ``` Notice the two update rules are gradient-ascent steps on $\log \sigma(\cdot)$ and $\log \sigma(-\cdot)$ respectively — each derived from differentiating $\mathcal{L}$ above with respect to $E_t$ and $C_c$ (or $C_{n_i}$). In production, the final word embedding is usually just $E$ (context vectors $C$ are discarded or averaged in). The same recipe generalizes immediately: replace "word" with "item" and "context" with "co-purchased items" to get item2vec; replace "word" with "graph node" and "context" with "nodes on a random walk" to get DeepWalk/node2vec — a direct bridge to Graph Neural Networks: An Introduction, where embeddings are refined further by aggregating neighbor information rather than relying solely on random-walk co-occurrence.

Space. An embedding table for vocabulary size $|V|$ and dimension $d$ requires $O(|V| \cdot d)$ parameters and memory. This is unavoidable — you need at least one $d$-dimensional vector per distinguishable entity — but it dominates model size in many systems: a 1M-word vocabulary with $d=300$ is 300 million floats (1.2 GB in float32), often larger than the rest of the network combined. Techniques like subword tokenization (byte-pair encoding), hashing tricks, and low-rank factorized embeddings (used in ALBERT) exist specifically to control this term.

Time, naïve softmax. A full softmax objective for predicting context word $c$ given target $t$,

requires summing over all $|V|$ vocabulary items for every single training pair, giving $O(|V| \cdot d)$ work per update — infeasible at web scale ($|V|$ in the millions, billions of training pairs).

Time, negative sampling. SGNS replaces this with $k+1$ binary decisions (one true pair, $k$ sampled negatives), each costing $O(d)$ for a dot product and its gradient. Total per-pair cost is $O(k \cdot d)$, independent of $|V|$. With $k$ typically 5–20, this is a $10^4$–$10^6$-fold speedup over full softmax for realistic vocabularies, at the cost of optimizing an approximate objective rather than the exact conditional log-likelihood.

Why the approximation is justified (correctness sketch). Negative sampling is not merely a heuristic hack — Levy & Goldberg (2014) showed that the SGNS objective, at its optimum (with the embedding dimension unconstrained), satisfies

where $\mathrm{PMI}(t,c) = \log \frac{P(t,c)}{P(t)P(c)}$ is the pointwise mutual information between $t$ and $c$ estimated from corpus co-occurrence counts. The derivation: differentiate the expected SGNS log-likelihood over the true joint distribution with respect to the free variable $x = E_t \cdot C_c$, set to zero, and solve — this reveals SGNS is implicitly performing a weighted, shifted matrix factorization of the PMI matrix. This is precisely what count-based methods like GloVe explicitly optimize for:

where $f$ is a weighting function that down-weights rare co-occurrences. The convergence of two independently derived algorithms — one predictive, one count-based — onto the same target quantity (a shifted, weighted PMI matrix) is strong theoretical evidence that embedding geometry is not an artifact of a particular training scheme but reflects a genuine statistical regularity in co-occurrence data.

Why the resulting geometry supports analogy arithmetic. The famous result $\vec{king} - \vec{man} + \vec{woman} \approx \vec{queen}$ follows heuristically from the PMI-factorization view: if "king" and "queen" differ from "man" and "woman" by a roughly consistent shift in co-occurrence log-odds with a set of "royalty" context words, and the mapping from PMI differences to embedding differences is approximately linear (guaranteed locally by the factorization objective), then vector offsets transfer between analogous pairs. This is an empirical regularity with a plausible linear-algebraic explanation, not a theorem — it holds well for frequent, well-separated relations and degrades for rare words or polysemous terms.

Tradeoffs. Predictive methods (word2vec) are cheaper per update and stream well over huge corpora without ever materializing $X$; count-based methods (GloVe) can exploit fast matrix factorization solvers and are more sample-efficient on smaller corpora since they use aggregate statistics rather than one context pair at a time. Both produce static embeddings: one vector per word type regardless of context, which cannot disambiguate "bank" (river) from "bank" (finance) — a limitation resolved by later contextual models (ELMo, BERT) that recompute embeddings per-token conditioned on the surrounding sequence.

Consider a toy corpus with vocabulary $V = \{\text{king, queen, man, woman, apple, banana}\}$ and $d = 2$ for visualizability. Suppose after training on a corpus rich in royalty and fruit contexts, we obtain (illustrative, rounded) embeddings:

Trace the analogy computation $\vec{king} - \vec{man} + \vec{woman}$ step by step: 1. $\vec{king} - \vec{man} = (2.0-1.9,\ 3.1-0.4) = (0.1, 2.7)$. 2. Add $\vec{woman}$: $(0.1 + 2.2,\ 2.7 + 0.3) = (2.3, 3.0)$. 3. Compare to $\vec{queen} = (2.3, 3.0)$ — an exact match in this illustrative table, and in real trained embeddings typically the nearest neighbor by cosine similarity among all vocabulary vectors. Now trace why the geometry separates royalty from fruit. Cosine similarity between "king" and "queen":

extremely close, reflecting that "king" and "queen" appear in overlapping royal contexts (crown, throne, palace). Cosine similarity between "king" and "banana":

near zero/negative, reflecting near-disjoint context distributions. This mirrors the underlying training dynamic: "king" and "banana" almost never co-occur with the same context words, so negative sampling repeatedly pushes their dot product down (toward $\sigma(\cdot) \to 0$), while "king" and "queen" share many true context pairs, repeatedly pushing their dot product up. The geometry is the accumulated residue of millions of such small pairwise nudges — exactly the gradient updates traced in the pseudocode above.

Distributional semantics predates deep learning by decades, rooted in structural linguistics, but its computational realization as trainable dense vectors is a product of the neural-network era. The person most associated with popularizing scalable neural word embeddings is Tomáš Mikolov, whose word2vec (2013) made the technique practical and famous through the analogy demonstrations that captured public imagination.

Embeddings are now the substrate on which most large-scale machine learning systems operate. Search engines and recommender systems embed queries, documents, users, and items into shared vector spaces so that relevance and similarity reduce to nearest-neighbor search — the technology behind approximate nearest neighbor libraries (FAISS, ScaNN) that power retrieval at billion-item scale. Large language models begin every forward pass with a learned embedding lookup that converts token IDs into dense vectors before any transformer computation occurs; the embedding table is frequently among the largest single parameter blocks in the model. Graph-structured domains — social networks, molecule graphs, knowledge graphs — use node embeddings (DeepWalk, node2vec) as either standalone features or as the initialization layer feeding into Graph Neural Networks: An Introduction, where message passing further refines embeddings using explicit graph topology rather than co-occurrence statistics alone. Categorical features in tabular deep learning (user IDs, zip codes, product categories) are routinely embedded rather than one-hot encoded, dramatically shrinking both memory and the effective input dimensionality that downstream layers must process.

Ask the tutor: How does negative sampling's noise distribution exponent (0.75) affect which words get treated as "hard negatives" during training?