word2vec as Implicit Matrix Factorization

Overview & Motivation

Train word2vec on the finance corpus with an eight-word window, five negative samples, and $25$ dimensions. Then take every pair of words that occurs together in the training text and compare the dot product of the first word’s vector with the second word’s context vector against the shifted pointwise mutual information of the distributional-semantics topic. For the $816$ pairs seen at least $100$ times, the two agree with correlation $0.985$ . For the $98{,}926$ pairs seen once, the correlation is $0.641$ . Word2vec never forms a co-occurrence matrix, yet it fits one, and how closely depends on how often the pair was seen.

Now take that trained model and change the basis of its vectors: replace the word vectors $W$ by $WA$ and the context vectors $C$ by $CA^{-\top}$ for an invertible matrix $A$ . Every word–context dot product, and therefore the training loss, is unchanged. The word–word similarities are not. Over five such factorizations of the one trained product, the score for grouping nouns by their planted sector ranges from $0.737$ to $0.901$ , and the nearest neighbors of strong change. The objective does not decide which words are similar.

This topic proves both halves of that picture.

The objective chooses the matrix. Skip-gram’s three training objectives, a full softmax, noise-contrastive estimation, and negative sampling, all have optima equal to pointwise mutual information (PMI) up to row and column offsets. Negative sampling’s is exactly $\operatorname{PMI}_\alpha - \log k$ on observed pairs, and unobserved pairs have no optimum (Levy and Goldberg 2014).
At low rank, negative sampling is a weighted logistic PCA. The loss is exactly a count-weighted sum of Bernoulli KL divergences, so frequent pairs are fitted closely and rare ones loosely. A truncated SVD of shifted PMI weights every entry alike.
The optimizer chooses the factorization. The loss sees only the product $WC^\top$ , so it fixes word similarity only up to a change of basis. Gradient flow conserves $W^\top W - C^\top C$ , and balanced factors are the square-root weighting of the distributional-semantics topic, with word plus context vectors equal to the positive part of a symmetric product.

Then we test what the factorization buys on the planted-sector benchmark, and the finance case study asks whether it finds a polarity direction that the window counts do not carry.

Three objectives, one matrix

Fix a window context, the two-word window L2 or the eight-word window L8, and write $\#(w, c)$ for the distributional-semantics topic’s pair counts (its Definition 1), $\#(w) = \sum_c \#(w, c)$ , and $N = \sum_{w, c} \#(w, c)$ . With L8 there are $N = 576{,}098$ pair occurrences over $143{,}345$ observed cells, $1.22\%$ of the $3{,}425^2$ possible pairs; with L2, $215{,}948$ over $53{,}293$ , $0.45\%$ . The smoothed context distribution is $P_\alpha(c) = \#(c)^\alpha / \sum_{c'} \#(c')^\alpha$ , with the context counts taken as column sums.

A word gets a vector $\mathbf{w}_w \in \mathbb{R}^d$ and, separately, every word gets a context vector $\mathbf{c}_c \in \mathbb{R}^d$ . They are the rows of two matrices $W, C \in \mathbb{R}^{V \times d}$ ; in this topic $C$ always means the context matrix. The score of a pair is $x_{wc} = \langle \mathbf{w}_w, \mathbf{c}_c \rangle$ , so the matrix of all scores is $X = W C^\top$ , a matrix of rank at most $d$ . Each objective below asks this matrix to predict the counts.

Definition 1 (Skip-gram with a full softmax).

The skip-gram model predicts each context from its word by a softmax over all contexts (Mikolov et al. 2013a), and is trained by minimizing

L_{\text{soft}}(X) = -\sum_{w, c} \#(w, c) \log \frac{e^{x_{wc}}}{\sum_{c'} e^{x_{wc'}}} .

The softmax needs a sum over the whole vocabulary for every training pair. Negative sampling replaces it with a few binary decisions.

Definition 2 (Skip-gram with negative sampling).

Let $\sigma(x) = 1/(1 + e^{-x})$ and $k \ge 1$ . Each observed pair $(w, c)$ is a positive example, and for each one we draw $k$ negative contexts $c_1, \dots, c_k$ independently from the noise distribution $P_n = P_\alpha$ . The sampled loss of the pair is $-\log \sigma(x_{wc}) - \sum_{i \le k} \log \sigma(-x_{wc_i})$ . Its expectation, summed over all $N$ pairs, is the negative-sampling objective

L_{\text{NS}}(X) = -\sum_{w, c} \Bigl[ a_{wc} \log \sigma(x_{wc}) + b_{wc} \log \sigma(-x_{wc}) \Bigr], \qquad a_{wc} = \#(w, c), \quad b_{wc} = k\, \#(w)\, P_\alpha(c).

Here $b_{wc}$ is the expected number of times the pair $(w, c)$ is drawn as a negative (Mikolov et al. 2013b; Goldberg and Levy 2014). Word2vec’s exponent is $\alpha = 0.75$ , the same smoothing the distributional-semantics topic studied in its Proposition 4.

Definition 3 (Noise-contrastive estimation).

Noise-contrastive estimation (NCE) treats $x_{wc}$ as an unnormalized $\log P(c \mid w)$ and trains a classifier to tell data pairs from noise pairs, with logit $s_{wc} = x_{wc} - \log\bigl(k P_n(c)\bigr)$ (Gutmann and Hyvärinen 2010, 2012; Mnih and Teh 2012). Its objective $L_{\text{NCE}}$ is $L_{\text{NS}}$ with $x_{wc}$ replaced by $s_{wc}$ .

The difference between the two binary objectives is a single subtracted term. To see what it changes, we find each objective’s optimum when the scores are unconstrained, one free number per cell. The softmax comes first.

Proposition 1 (The softmax optimum).

For a word with $\#(w) \gt 0$ , the row’s loss $-\sum_c \#(w, c) \log \operatorname{softmax}(x_{w \cdot})_c$ attains its infimum exactly when $\#(w, c) \gt 0$ for every context $c$ . Its minimizers are then

x_{wc} = \log P(c \mid w) + \kappa_w = \operatorname{PMI}(w, c) + \log P(c) + \kappa_w

for an arbitrary constant $\kappa_w$ . If some $\#(w, c) = 0$ , the infimum is approached as $x_{wc} \to -\infty$ and never attained.

Proof.

With $P(c \mid w) = \#(w, c)/\#(w)$ , the row’s loss is $\#(w)$ times the cross-entropy of $P(\cdot \mid w)$ relative to $p = \operatorname{softmax}(x_{w\cdot})$ . That is at least $\#(w)$ times the entropy of $P(\cdot \mid w)$ , with equality exactly when $p = P(\cdot \mid w)$ (Gibbs’ inequality; formalML, KL Divergence, Propositions 1–3). The softmax takes every value in the open simplex and is unchanged by adding a constant to $x_{w\cdot}$ , so the infimum is attained exactly when $P(\cdot \mid w)$ has no zeros, at the stated $x$ . If $P(c \mid w) = 0$ , no softmax reaches it, and the loss decreases toward its infimum as $x_{wc} \to -\infty$ .

∎

An unseen context has no best score, only better and better ones. This is the neural-language-models topic’s Corollary 1, that a never-seen target has no maximum-likelihood fit, applied one context at a time. Negative sampling inherits the same phenomenon in a sharper form.

Theorem 1 (The negative-sampling optimum).

For $a, b \gt 0$ , the function $\varphi(x) = a \log \sigma(x) + b \log \sigma(-x)$ is strictly concave on $\mathbb{R}$ , with unique maximizer $x^\star = \log(a/b)$ . For $a = 0 \lt b$ , $\varphi$ increases strictly toward $0$ as $x \to -\infty$ and has no maximizer. Hence, for unconstrained scores, $L_{\text{NS}}$ separates into one such function per cell, it has a minimizer exactly when every pair is observed, and on observed pairs the minimizer is

x^\star_{wc} = \log \frac{\#(w, c)}{k\, \#(w)\, P_\alpha(c)} = \operatorname{PMI}_\alpha(w, c) - \log k .

Proof.

Since $\tfrac{d}{dx} \log \sigma(x) = \sigma(-x)$ , we get $\varphi'(x) = a \sigma(-x) - b \sigma(x)$ and $\varphi''(x) = -(a + b)\, \sigma(x) \sigma(-x) \lt 0$ . The equation $\varphi'(x) = 0$ says $\sigma(-x)/\sigma(x) = e^{-x} = b/a$ , so $x^\star = \log(a/b)$ . For $a = 0$ , $\varphi'(x) = -b \sigma(x) \lt 0$ everywhere, and $\varphi(x) \to 0$ as $x \to -\infty$ . Finally, with $P(w, c) = \#(w, c)/N$ and $P(w) = \#(w)/N$ , $\log\bigl(a/b\bigr) = \log \frac{P(w, c)}{P(w) P_\alpha(c)} - \log k$ , which is the distributional-semantics topic’s Definition 2.

∎

This is Levy and Goldberg’s (2014) theorem, and its matrix is the one the distributional-semantics topic named and did not prove anything about: the unclipped shifted PMI. The theorem has a reading in terms of classifiers. $\sigma(x^\star) = a/(a + b)$ is the probability that a pair with these counts came from the data rather than from the noise, when the prior odds of data to noise are $1/k$ . So the optimal score is the log density ratio of data pairs to noise pairs plus the log prior odds, the identity of formalML’s Density Ratio Estimation (its Theorem 4). That page states the identity for the Bayes classifier; Theorem 1 is the proof that the logistic loss reaches it, cell by cell. Each cell is a logistic regression with a canonical link (formalStatistics, Generalized Linear Models, Theorem 1), which is why the optimum is unique.

Proposition 2 (NCE and negative sampling fit one matrix up to offsets).

Under Theorem 1’s hypotheses, NCE’s optimum is $x^\star_{\text{NCE}} = \log P(c \mid w)$ , with no free row constant, and

x^\star_{\text{NCE}}(w, c) - x^\star_{\text{NS}}(w, c) = \log\bigl(k P_n(c)\bigr),

an offset that depends on the context alone. Every optimum is $\operatorname{PMI}$ (with $\alpha = 1$ ) plus a matrix constant along rows plus a matrix constant along columns:

objective	row offset	column offset
full softmax	$\kappa_w$ (any)	$\log P(c)$
noise-contrastive estimation	$0$	$\log P(c)$
negative sampling	$0$	$\log P(c) - \log P_\alpha(c) - \log k$

So every optimum has rank at most $\operatorname{rank}(\operatorname{PMI}) + 2$ .

Proof.

Theorem 1 applied to the logit $s$ gives $s^\star = \log(a/b)$ , so $x^\star_{\text{NCE}} = \log(a/b) + \log\bigl(k P_n(c)\bigr) = \log\bigl(\#(w, c)/\#(w)\bigr) = \log P(c \mid w)$ . Subtracting $x^\star_{\text{NS}} = \log(a/b)$ gives the offset. The table follows from $\log P(c \mid w) = \operatorname{PMI}(w, c) + \log P(c)$ and $\operatorname{PMI}_\alpha = \operatorname{PMI} + \log P(c) - \log P_\alpha(c)$ , and a row-constant or column-constant matrix has rank one.

∎

Negative sampling is NCE with the noise correction $\log(k P_n(c))$ dropped (Dyer 2014). The two do not estimate the same thing: NCE recovers the conditional distribution $P(c \mid w)$ itself (Mnih and Kavukcuoglu 2013), and negative sampling recovers an association score. But they differ by a context offset, and a model with a bias term per context could absorb it. This is the neural-language-models topic’s Theorem 6 in another guise: a log-bilinear model with biases has a score matrix of rank at most $d + 2$ , and all three objectives ask for PMI in that form, which is the third part of the distributional-semantics topic’s Theorem 3.

The binary objective also differs from the softmax contrastive loss that formalRAG studies. There, the optimal critic of InfoNCE is PMI only up to a constant per query (formalRAG, InfoNCE and the Contrastive Objective, the proof of Theorem 1). Negative sampling’s logit is pinned: its constant is $-\log k$ , and nothing else.

What negative sampling minimizes at low rank

Theorem 1 describes a model with one free number per cell. Word2vec has $2Vd$ numbers for $V^2$ cells, with $d = 25$ against $V = 3{,}425$ , and $98.8\%$ of the cells at the eight-word window have no optimum at all. So what does it fit?

Theorem 2 (Negative sampling is a weighted logistic PCA).

Let $y_{wc} = a_{wc}/(a_{wc} + b_{wc})$ , and let $H(y) = -y \log y - (1 - y) \log(1 - y)$ be the Bernoulli entropy. For every score matrix $X$ ,

L_{\text{NS}}(X) - \sum_{w, c} (a_{wc} + b_{wc})\, H(y_{wc}) = \sum_{w, c} (a_{wc} + b_{wc})\, \operatorname{KL}\bigl(\operatorname{Bern}(y_{wc}) \,\Vert\, \operatorname{Bern}(\sigma(x_{wc}))\bigr).

So $\inf L_{\text{NS}} = \sum (a + b) H(y)$ , and fitting a rank- $d$ matrix $X = WC^\top$ is a weighted KL projection of the target $x^\star = \log(a/b)$ onto the rank- $d$ matrices. On an observed cell, each term is $(a + b)$ times the Bregman divergence of the softplus $A(x) = \log(1 + e^x)$ ,

D_A(x, x^\star) = A(x) - A(x^\star) - \sigma(x^\star)(x - x^\star),

and the cell’s loss has curvature $(a + b)\, \sigma(x^\star) \sigma(-x^\star) = ab/(a + b)$ at its optimum.

Proof.

Factor $a + b$ out of one cell: $-a \log \sigma(x) - b \log \sigma(-x) = (a + b)\bigl[-y \log \sigma(x) - (1 - y) \log\bigl(1 - \sigma(x)\bigr)\bigr]$ , a Bernoulli cross-entropy, which equals $H(y) + \operatorname{KL}\bigl(\operatorname{Bern}(y) \Vert \operatorname{Bern}(\sigma(x))\bigr)$ (formalML, KL Divergence, Proposition 1). The Bernoulli family in its natural parameter $x$ has log-partition $A$ and mean $A' = \sigma$ , and for an exponential family the KL divergence between members is the Bregman divergence of the log-partition (formalML, Information Geometry, Definition 8, in the natural coordinates of its Theorem 5), with $\sigma(x^\star) = y$ . The curvature is $(a + b) A''(x^\star) = (a + b)\sigma(x^\star)\sigma(-x^\star)$ , and $\sigma(x^\star) = a/(a + b)$ .

∎

An exponential-family PCA (Collins, Dasgupta, and Schapire 2001) is a low-rank fit of natural parameters under the family’s own divergence. With the Bernoulli family it is logistic PCA, and Landgraf and Bellay (2017) observed that negative sampling is exactly this, with a weight $a + b$ on every cell. The weights are what separate it from the distributional-semantics topic’s SVD.

Corollary 1 (Against the truncated SVD).

A truncated SVD of $\operatorname{SPPMI}_{\alpha,k}$ minimizes $\sum_{w, c} \bigl(\max(x^\star_{wc}, 0) - x_{wc}\bigr)^2$ over rank- $d$ matrices, with equal weight on every cell (Eckart and Young 1936; formalML, Singular Value Decomposition, Theorem 2). Negative sampling minimizes $\sum (a + b)\, D_A(x, x^\star)$ , and it differs in three ways.

It weights by counts. Near the optimum, $(a + b) D_A(x, x^\star) = \tfrac12 \tfrac{ab}{a + b} (x - x^\star)^2 + O\bigl((x - x^\star)^3\bigr)$ , a least-squares fit with weight $\tfrac{ab}{a + b}$ , and $\tfrac12 \min(a, b) \le \tfrac{ab}{a + b} \le \min(a, b)$ .
It pushes unobserved cells down instead of clipping them. An unobserved cell has $y = 0$ and pays $b \log(1 + e^{x})$ , which keeps decreasing as $x \to -\infty$ .
It keeps negative targets. An observed pair with $x^\star \lt 0$ is fitted at $x^\star$ , not at $0$ .

Proof.

Part 1 is the second-order Taylor expansion of the cell’s loss at its optimum (formalCalculus, The Hessian, Theorem 3), with Theorem 2’s curvature; that theorem gives a remainder of $o\bigl((x - x^\star)^2\bigr)$ , and since the cell’s loss is infinitely differentiable, Taylor’s theorem with the third derivative bounds it by $O\bigl((x - x^\star)^3\bigr)$ . The bounds follow from $ab/(a + b) = \min(a, b) \cdot \max(a, b)/(a + b)$ and $\max(a, b) \le a + b \le 2 \max(a, b)$ . Parts 2 and 3 are Definition 2 with $a = 0$ , and Theorem 1.

∎

So a pair seen once can count for no more than once, however large its PMI, while the SVD weighs its clipped PMI like any other entry. The corpus shows the predicted ordering. Train the model described in the overview (L8, $k = 5$ , $\alpha = 0.75$ , $d = 25$ , $40$ epochs) and compare $x_{wc} = \langle \mathbf{w}_w, \mathbf{c}_c \rangle$ with $x^\star_{wc} = \operatorname{PMI}_{0.75}(w, c) - \log 5$ on every observed pair, grouped by count.

times the pair was seen	pairs	correlation of $x$ with $x^\star$	mean $\lvert x - x^\star \rvert$
once	$98{,}926$	$0.641$	$1.297$
$2$ to $4$	$27{,}994$	$0.818$	$0.537$
$5$ to $19$	$12{,}200$	$0.940$	$0.291$
$20$ to $99$	$3{,}409$	$0.979$	$0.198$
$100$ or more	$816$	$0.985$	$0.139$

The correlation rises and the error falls with every band. The ordering is Corollary 1’s; the levels are partly unfinished training, since the correlation for pairs seen once was $0.478$ after $10$ epochs. Most observed pairs, $69\%$ , are seen once, so most of the matrix is fitted loosely. The unobserved cells, which have no target, are pushed far down: over all $11.6$ million of them the mean score is $-5.18$ , against $-0.63$ for observed pairs, and $97.8\%$ of them score below the median observed pair.

Training has not finished: the loss was still falling when it stopped, from $1.826$ per pair after $10$ epochs to $1.6514$ after $40$ . It ends $0.176$ per pair above Theorem 2’s floor of $1.4752$ , but not all of that gap is unfinished training. The floor is an infimum that no finite score attains: the unobserved cells reach it only at $-\infty$ , and $0.091$ of the gap sits on them; a rank- $25$ matrix cannot reach every observed target either.

Where does $-5.18$ come from? The product’s top singular vectors have one sign on every word and the opposite sign on every context, so the leading term $\sigma_1 u_1 v_1^\top$ is negative in every entry. It carries $87.4\%$ of $\lVert WC^\top \rVert_F^2$ , its leading singular value is $6.3$ times the next, and its mean entry is $-5.15$ , the level of the unobserved cells. Word2vec has no bias terms, but Proposition 2 says its optimum wants offsets, and Theorem 1 says the $98.8\%$ of cells that were never observed want $-\infty$ . The model spends one of its $25$ dimensions on a near-constant offset, negative in every entry, that pushes everything down.

The algorithm

So far the objective has been the expectation of what word2vec computes. Here is what it computes.

Definition 4 (Word2vec's stochastic gradient descent).

Each epoch visits the $N$ observed pairs in a fresh random order, in minibatches of $512$ . Each pair draws $k = 5$ negatives from $P_\alpha$ , and the parameters take one gradient step on the minibatch’s summed sampled loss. The step size decays linearly from $\eta_0 = 0.05$ to $10^{-4}\eta_0$ over training. Initialization follows the word2vec C code: the entries of $W$ are uniform on $[-\tfrac{1}{2d}, \tfrac{1}{2d}]$ , and $C = 0$ .

The sampled loss is an unbiased estimate of $L_{\text{NS}}$ , by linearity of expectation over the negatives, so its gradient is an unbiased estimate of the objective’s gradient. Two departures from the C code are worth stating. The code updates after every pair, from several threads without locks, while we sum the gradients of a minibatch; and we train for $40$ epochs (the comparison grid below, $20$ ), many more than the C code’s default of five, because our corpus is small.

Remark.

The shipped word2vec also samples each window’s width uniformly from $1$ to $L$ and discards frequent words at random before forming windows. Both change the counts $\#(w, c)$ , the first by weighting a pair at distance $\delta$ by $(L - \delta + 1)/L$ , and leave the form of the objective alone. Levy, Goldberg, and Dagan (2015) showed that both transfer to count-based methods. We train on the distributional-semantics topic’s unweighted counts so that Theorem 1’s target is exactly that topic’s matrix.

Gauge and balance

Every objective above is a function of the product $X = W C^\top$ . That leaves something undetermined.

Proposition 3 (Every factorization of one product).

If $W' C'^\top = W C^\top$ and all four matrices have full column rank $d$ , then $W' = WA$ and $C' = C A^{-\top}$ for a unique invertible $A$ . Consequently every objective of Definitions 1–3 determines the matrix of word–word dot products only up to $W M W^\top$ with $M = A A^\top$ an arbitrary positive definite matrix, and word–word dot products are preserved exactly when $A$ is orthogonal.

Proof.

The columns of $W'$ and of $W$ both span the column space of the product, so $W' = WA$ for some $A$ , invertible because both have rank $d$ . Then $W A C'^\top = W C^\top$ , and multiplying by a left inverse of $W$ gives $A C'^\top = C^\top$ , so $C' = C A^{-\top}$ . Finally, $W M W^\top = W W^\top$ with $W$ of full column rank forces $M = I$ .

∎

The same freedom appears in every model whose score is an inner product of two learned embeddings, including the dual encoders of retrieval (formalRAG, Dense Retrieval and Dual Encoders, Theorem 2, for the rank ceiling such scores share). For word vectors it matters, because word similarity is a cosine between rows of $W$ , which no part of the loss sees. The trained model shows how much it matters. Take its product, with singular value decomposition $U \Sigma V^\top$ , and refactor it four ways: the distributional-semantics topic’s eigenvalue weights $W = U\Sigma^p$ , $C = V \Sigma^{1 - p}$ for $p = 0, \tfrac12, 1$ , and a random $A$ with condition number $100$ . All five have the same product to ten digits, and so the same loss.

factorization of the one product	test AUC	test nearest neighbor	nearest neighbors of strong
as trained	$0.886$	$0.852$	weak, unfavorable, solid, soft, healthy
$p = 0$	$0.849$	$0.878$	unfavorable, weak, soft, resilient, disappointing
$p = \tfrac12$	$\mathbf{0.901}$	$0.852$	weak, unfavorable, solid, resilient, soft
$p = 1$	$0.890$	$0.843$	weak, unfavorable, solid, healthy, efficient
random $A$ , condition number $100$	$0.737$	$0.670$	adverse, healthy, unfavorable, solid, confident

The scores are those of the planted-sector benchmark of the next section. So which factorization does training produce? The answer comes from the optimizer, and it is cleanest for gradient flow, the limit of gradient descent with infinitesimal steps (formalCalculus, First-Order ODEs), where a conservation law found for deep linear networks applies verbatim (Du, Hu, and Lee 2018; Arora, Cohen, and Hazan 2018).

Theorem 3 (Gradient flow conserves the imbalance).

Let $L(W, C) = f(W C^\top)$ for a differentiable $f$ , and write $G = \nabla f(X)$ . Along the gradient flow $\dot W = -G C$ , $\dot C = -G^\top W$ , the $d \times d$ matrix

D = W^\top W - C^\top C

is constant. A gradient step of size $\eta$ , with $\nabla_W = \hat G C$ and $\nabla_C = \hat G^\top W$ for any matrix $\hat G$ , including a minibatch’s sampled gradient, changes it by exactly

D_{t+1} - D_t = \eta^2 \bigl( \nabla_W^\top \nabla_W - \nabla_C^\top \nabla_C \bigr).

Proof.

$\tfrac{d}{dt} W^\top W = \dot W^\top W + W^\top \dot W = -C^\top G^\top W - W^\top G C$ , and $\tfrac{d}{dt} C^\top C = -W^\top G C - C^\top G^\top W$ , the same matrix. For the step, expand $(W - \eta \nabla_W)^\top (W - \eta \nabla_W) - (C - \eta \nabla_C)^\top(C - \eta \nabla_C)$ : the first-order terms are $-\eta(C^\top \hat G^\top W + W^\top \hat G C)$ from both products and cancel, and the second-order terms are as stated.

∎

If training starts balanced, with $W^\top W = C^\top C$ , gradient flow keeps it balanced. Balance determines the factorization up to a rotation.

Lemma 1 (Balanced factorizations).

Let $X = U \Sigma V^\top$ have rank $d$ and distinct singular values, and let $W C^\top = X$ with $W^\top W = C^\top C$ . Then $W = U \Sigma^{1/2} R$ and $C = V \Sigma^{1/2} R$ for an orthogonal matrix $R$ .

Proof.

Let $B = W^\top W = C^\top C$ , which is positive definite since $W$ has rank $d$ . Then $X X^\top = W C^\top C W^\top = W B W^\top$ . Write the thin SVD $W = P S Q^\top$ ; then $B = Q S^2 Q^\top$ and $W B W^\top = P S^4 P^\top$ , which must equal $X X^\top = U \Sigma^2 U^\top$ . Both are eigendecompositions of one matrix with distinct eigenvalues, so $S = \Sigma^{1/2}$ and $P = U E$ for a diagonal sign matrix $E$ , and $W = U \Sigma^{1/2} R_W$ with $R_W = E Q^\top$ orthogonal. The same argument with $X^\top X = C B C^\top$ gives $C = V \Sigma^{1/2} R_C$ . Then $X = U \Sigma^{1/2} R_W R_C^\top \Sigma^{1/2} V^\top = U \Sigma V^\top$ forces $\Sigma^{1/2} R_W R_C^\top \Sigma^{1/2} = \Sigma$ , so $R_W R_C^\top = I$ .

∎

Corollary 2 (Balanced word vectors are the square-root weighting).

For balanced factors of $X$ :

$W W^\top = U \Sigma U^\top$ , the distributional-semantics topic’s Definition 3 with $p = \tfrac12$ , applied to the matrix negative sampling fitted. Cosines between word vectors are those of $U \Sigma^{1/2}$ .
If $X = Q \Lambda Q^\top$ is symmetric, then $\tfrac14 (W + C)(W + C)^\top = [X]_+$ , the positive part of $X$ .

Proof.

Part 1: by Lemma 1, $W W^\top = U \Sigma^{1/2} R R^\top \Sigma^{1/2} U^\top$ . Part 2: for symmetric $X$ the singular vectors can be taken as $u_i = q_i$ and $v_i = \operatorname{sign}(\lambda_i)\, q_i$ , so $W + C = (U + V)\Sigma^{1/2} R = 2\, Q [\Lambda]_+^{1/2} R$ , as in the distributional-semantics topic’s Corollary 1, and $R$ cancels in $(W + C)(W + C)^\top$ .

∎

This is the precise sense of that topic’s promise. Adding context vectors to word vectors, the heuristic of Levy, Goldberg, and Dagan (2015), is the projection onto the positive eigenspace, exactly for balanced factors of a symmetric product, and only up to a rotation that no cosine can see. We check the whole chain on a small symmetric instance. Gradient descent at full rank, started balanced, fits the optimum to $2 \cdot 10^{-14}$ , and $\tfrac14 (W + C)(W + C)^\top$ misses $[X^\star]_+$ by at most $0.0042$ with step $0.02$ and $0.0024$ with step $0.01$ : the error shrinks with the step, as Theorem 3 predicts.

The corpus is less tidy, and the page should say how. Word2vec’s initialization is nearly balanced: $\lVert D_0 \rVert$ is $1.3 \times 10^{-4}$ of the final $\lVert W^\top W \rVert$ . But minibatch SGD with word2vec’s step sizes is not gradient flow. Theorem 3’s second-order terms add up: $D$ grows $1{,}819$ -fold in the first epoch, keeps growing, and ends at $0.80$ of $\lVert W^\top W \rVert$ . What cosines depend on, though, is the basis change $A$ in $W = U \Sigma^{1/2} A$ , which is orthogonal exactly for balanced factors. Its singular values lie in $[0.800, 1.206]$ after the first epoch, in $[0.788, 1.204]$ after the last, and in $[0.786, 1.215]$ at every checkpoint, so it is nearly orthogonal throughout, and its smallest singular value lies mostly along the offset direction found above. The trained vectors score $0.886$ against $0.901$ for the exactly balanced $U \Sigma^{1/2}$ . The balanced reading holds, approximately. With $\alpha = 0.75$ the target is not symmetric, so the corpus can check part 1 of Corollary 2 but not part 2.

Recovering the planted sectors

The distributional-semantics topic built a benchmark with a known answer: $227$ nouns that the corpus generator drew from exactly one of six sector vocabularies, split into $112$ dev nouns for choosing settings and $115$ test nouns for scoring (its Definition 4). The pair AUC is the probability that a same-sector pair of nouns has a higher cosine than a cross-sector pair, and the nearest-neighbor accuracy is the share of nouns whose nearest other noun shares their sector; chance for the latter is $0.262$ . That topic’s best setting was a truncated SVD of $\operatorname{SPPMI}_{0.75,5}$ at the eight-word window with $d = 25$ , which is the matrix negative sampling with $k = 5$ and $\alpha = 0.75$ fits. So the first comparison holds the matrix and the rank fixed and changes only the method.

the same matrix, $d = 25$	dev AUC	dev nearest neighbor	test AUC	test nearest neighbor
negative sampling, $40$ epochs	$0.870$	$0.866$	$\mathbf{0.886}$	$0.852$
truncated SVD, $p = 0$ (that topic’s selection)	$0.951$	$0.946$	$\mathbf{0.973}$	$0.965$
truncated SVD, $p = \tfrac12$	$0.944$	$0.929$	$0.966$	$0.965$

On the test nouns, negative sampling trails the SVD by $0.087$ in AUC, with a jackknife standard error of $0.017$ , and by $0.113$ in nearest-neighbor accuracy, with a paired standard error of $0.034$ . Averaging word and context vectors changes nothing here ( $0.886$ either way). The $396$ rarer sector nouns, seen two to four times and never used for any choice, give the same verdict: AUC $0.652$ for negative sampling against $0.728$ for the SVD, and nearest-neighbor accuracy $0.593$ against $0.657$ .

Corollary 1 predicts the direction. On the benchmark nouns’ rows, pairs seen at most four times are $92.3\%$ of the observed pairs, and they carry $98.7\%$ of the squared mass of $\operatorname{SPPMI}_{0.75,5}$ , which the SVD fits with equal weight. They carry only $54.8\%$ of negative sampling’s weight $ab/(a + b)$ . A noun’s sector shows mostly in rare pairs with other sector words: pairs with a noun of the same sector carry $56.2\%$ of that squared mass, and $99.7\%$ of their share sits in pairs seen at most four times. Negative sampling, by design, trusts rare pairs less. Training longer helps: the same configuration trained for $20$ epochs instead of $40$ scores $0.859$ .

A small grid gives negative sampling its own choice of window and dimension, selected on dev nouns by the same rule as before, with $20$ epochs each.

window, dimension	dev AUC	dev nearest neighbor	test AUC	test nearest neighbor
L2, $d = 25$	$0.720$	$0.634$	$0.709$	$0.591$
L2, $d = 100$	$0.697$	$0.643$	$0.723$	$0.652$
L8, $d = 25$ (selected)	$\mathbf{0.863}$	$0.848$	$0.859$	$0.765$
L8, $d = 100$	$0.830$	$0.920$	$0.833$	$0.887$

The wider window wins, as it did for counts, because sector is a property of whole documents. The selected model beats the distributional-semantics topic’s best sparse matrix ( $0.813$ ) in AUC and trails its SVD by $0.114$ (standard error $0.021$ ). On this corpus, at this budget, the count-based method with a truncated SVD is the better reader of planted sectors.

One cell, and the factorization training picks

The laboratory makes both halves of the topic concrete. Panel A shows one cell of the objective: pick one of six contexts of revenue, its most associated context in each count band, from a pair seen once to a pair seen $129$ times, plus the most frequent context it never meets, and the curve is that cell’s loss. Its minimum sits at $\operatorname{PMI}_\alpha - \log k$ and moves by $\log 3$ when you change $k$ from $5$ to $15$ ; its width is set by the weight $ab/(a + b)$ ; and the dot marks what the trained model actually learned. The pair seen once, revenue with plantline, has weight $0.34$ and is fitted badly (learned $-0.91$ , target $0.66$ ); revenue with fiscal, seen $53$ times, is fitted almost exactly. The context outlook, never seen with revenue, has no minimum at all. Panel B follows training: drag the epoch slider and watch frequent pairs reach the diagonal first while rare pairs stay scattered and unobserved cells sink. Its second view shows the five factorizations of one product, with their scores and the neighbors of strong and loans.

A · One cell of the objective — the loss of one (word, context) pair as a function of its score

times seen, a

expected negative draws, b

0.52

optimum x* = PMI_α − log k

0.662

local weight ab/(a + b)

0.340

trained score (k = 5, α = 0.75)

-0.913

Changing k slides the minimum by −log k; the curve's width falls as the weight grows, so frequent pairs are pinned and rare ones are not. The dot is the score the trained model learned (filled at the setting it was trained with): close to x* for a pair seen dozens of times, far from it for a pair seen once. A context never seen with revenue has no minimum, only a push toward −∞.

B · Training and the gauge — what SGD fits, and the factorization it picks

epoch 40

times seen:1 (r = 0.641)2–4 (r = 0.818)5–19 (r = 0.940)20–99 (r = 0.979)100+ (r = 0.985)· dashed: learned = target

loss per pair (floor)

1.6514 (1.4752)

r, pairs seen once

0.641

r, pairs seen 100+

0.985

gauge A's singular values

0.788 – 1.204

‖WᵀW − CᵀC‖ / ‖WᵀW‖

0.799

revenue·plantline is not among the sampled pairs; its count band is highlighted. At epoch 0 every score is 0, since the context vectors start at zero. Frequent pairs reach the diagonal first; pairs seen once stay scattered, as their small weight predicts, and unobserved cells sink. The imbalance grows well above zero, because SGD is not gradient flow, but the gauge stays near orthogonal from the first epoch on.

Finance case study: polarity isn’t a direction

§ Finance case study: polarity isn't a direction

The distributional-semantics topic found two things about the corpus’s polarity words, the $18$ positive and $17$ negative words of a hand-written stand-in lexicon (never the Loughran–McDonald dictionary itself). Antonyms keep the same company in a window, because the generator’s templates put both polarities in the same slots. And Turney’s (2002) semantic orientation finds no polarity evidence within four positions, backwards evidence within eight, and the right answer only from whole documents ( $0.829$ ). Negative sampling factorizes the same window counts. Does the factorization find anything more?

Antonyms are still neighbors. With the two-word window, the seven nearest neighbors of strong among the word vectors of the grid’s $d = 25$ , $20$ -epoch model are disappointing ( $0.974$ ), improved, stronger, weak ( $0.956$ ), robust, unfavorable, and favorable. With the eight-word window, weak comes first ( $0.960$ ).

No polarity direction beats chance. If polarity were a direction in the embedding, the difference between the mean positive and the mean negative word vector would point along it. We hold out each lexicon word in turn, compute that difference on unit-length vectors of the other $34$ , and ask on which side of the midpoint between the two means the held-out word falls. Because it compares class means of unit-length vectors, a shift shared by those unit vectors cancels; a shared offset in the raw vectors, such as the direction found in the low-rank section, changes how each vector is normalized and can still move it. On random vectors with a planted polarity offset it scores at least $0.95$ , and on pure noise it averages within $0.06$ of one half.

window	negative sampling, $W$	negative sampling, $(W + C)/2$	that topic’s SVD	sparse PPMI	that topic’s semantic orientation (no evidence counts $\tfrac12$ )
L2	$0.571$	$0.600$	$0.543$	$0.629$	$0.500$
L8	$0.571$	$0.600$	$0.514$	$0.629$	$0.343$

The negative-sampling columns use the grid’s $d = 25$ , $20$ -epoch models. Chance is $0.5$ with a standard error of $0.085$ for $35$ words. The best probe is $1.52$ standard errors above chance, and none reaches two. A factorization reorganizes the evidence in its counts; it cannot add evidence the counts do not contain, and in this corpus polarity shows only at the level of a document, which no window model sees. For finance text that is the practical lesson of the last two topics together: a type-level embedding trained on windows knows that strong and weak are used alike, and nothing about which is good news. The lexicon-sentiment topic takes up polarity with a dictionary, and the contextual-embedding topic gives each occurrence its own vector.

Where this goes next

GloVe. GloVe fits $\log \#(w, c)$ by weighted least squares with explicit biases and a weight that grows with the count, the same structure as Corollary 1’s local fit with a different weight. The next topic compares the two and takes up the linear structure behind word analogies, which is a statement about word–word geometry and so, by Proposition 3, about the gauge.
Contextual embeddings. One vector per word type cannot tell strong from weak by their windows. Contextual embeddings give each token its own vector, trained by a masked-language-model objective that is again a softmax over the vocabulary.
Knowledge-graph embeddings. TransE and its successors train with negative sampling over corrupted triples, and Theorem 1’s per-cell analysis applies to their scores as well.
Contrastive retrieval. formalRAG’s hard-negative mining asks which negatives to draw for a dual encoder; here the noise distribution decides what the optimum factorizes.

Honest caveats

⚠ Rigor flag

Theorem 1 is exact only at full rank and only on observed pairs. Unobserved pairs, $98.8\%$ of cells at the eight-word window, have no optimum, and at word2vec’s rank the objective is a count-weighted logistic PCA (Theorem 2), not a factorization of shifted PMI. Rare pairs are fitted loosely.
The trained models are not converged. The loss was still falling when training stopped, and it stays $0.176$ per pair above Theorem 2’s floor, an infimum that no finite score attains.
Minibatch SGD is not gradient flow. The quantity Theorem 3 conserves grows over a thousandfold during training, so the balanced, square-root reading of Corollary 2 holds only approximately: after training, the basis change’s singular values lie in $[0.79, 1.20]$ .
The corpus target is not symmetric. With $\alpha = 0.75$ , Corollary 2’s statement about word plus context vectors is checked on small instances only.
We departed from the shipped algorithm. Gradients are summed over minibatches instead of applied pair by pair, and the dynamic window and subsampling are omitted.
The ground truth is planted, as in the distributional-semantics topic, and its caveats carry over: the benchmark is $227$ nouns, $115$ of them for testing.
The comparison is at one budget. Negative sampling trains for $40$ epochs in the controlled comparison and $20$ in a four-setting grid; longer training narrows the gap with the SVD, by how much at convergence we did not measure.
The polarity probe uses a stand-in lexicon of $35$ hand-written words, not the Loughran–McDonald dictionary.

Implementation

The companion notebook (notebookPath) imports word2vec_implicit_factorization.py, which owns every number on this page. It imports the distributional-semantics topic’s module for the co-occurrence counts, the PMI matrices, the SVD baselines, the benchmark, and the semantic-orientation scores, and the neural-language-models topic’s module for its log-softmax and gradient checkers. Running it as a script trains five negative-sampling models in NumPy and executes a harness of $14$ assertion-based tests in under a minute on a laptop CPU. The tests cover:

Proposition 1, Theorem 1, and Proposition 2 against unconstrained L-BFGS (scipy.optimize) on random instances, and Theorem 1 exactly on every observed pair of the corpus; the hand-written gradients against complex-step and central differences; the unbiasedness of the sampled loss.
Theorem 2 on random instances, against scipy.stats.entropy, with its curvature and weight bounds; the fit by count band and the offset direction on the corpus.
Proposition 3 on random instances and on the trained model; Theorem 3’s step identity on real minibatches and its drift as the step shrinks; Lemma 1 and Corollary 2 on random instances and end to end from a balanced start; the near-balance of the trained model.
The controlled comparison, the grid and its selection, the weight mechanism, and the finance case study.

The laboratory reads its data from a JSON file that one of those tests requires to equal the module’s viz_payload() exactly, so the figure cannot drift from the code.

Overview & Motivation

Three objectives, one matrix

What negative sampling minimizes at low rank

The algorithm

Gauge and balance

Recovering the planted sectors

One cell, and the factorization training picks

Finance case study: polarity isn’t a direction

Where this goes next

Honest caveats

Implementation

References & Further Reading