nucleation

NOTE-1329: Hashimoto et al. — Word embeddings as metric recovery

14 min read

Properties2
StatusRead
PaperLIT-1801 — Word Embeddings as Metric Recovery in Semantic Spaces

Graph View

Contribution

It recasts word embedding as estimating the metric of a latent “semantic space”, the object psychometricians since Rumelhart and Abrahamson (1973) had posited, rather than as producing features. Under a toy generative model, a metric random walk over words, it proves that log co-occurrences over a large window converge to squared latent distances (Lemma 1, Corollary 6), and reads GloVe as weighted multidimensional scaling, word2vec as stochastic neighbour embedding and PMI-SVD as classical MDS under a norm assumption, each with the true embedding at a global optimum. It adds a direct estimator (negative-binomial “metric regression”), a reduction of manifold learning to word embedding (random walks on a neighbourhood graph as sentences), and two small inductive-reasoning test sets (series completion and classification).

Key insight

A one-step co-occurrence can depend on distance through any unknown link function h; a co-occurrence over many steps forgets h and depends on distance through the heat kernel, whose logarithm is quadratic in distance. “Intuitively, this result is an analog of the central limit theorem for random walks. Note that, for this reason, we do not need to know the link function h” (p. 277). So what log co-occurrence statistics can identify is the metric, and the coordinates only up to the isometries that preserve it.

Assumptions

  • The generative model, eq. (1): P(Xt = j | Xt−1 = i) = h(‖xi − xj‖²/σ), with h “some unknown, sub-Gaussian function linking semantic similarity to co-occurrence” (p. 277). The authors: “while the random walk is introduced over the words, it is not intended as a model of language but rather as a tool to understand the recovery problem” (p. 277). “This toy model ignores the role of syntax and function words” (n. 4).
  • Appendix A’s setting: points drawn i.i.d. from a density p with bounded log-gradient and a strict lower bound p₀ on a compact Riemannian manifold; a “spatial graph” whose edge i → j is present with probability h(ρ(xi, xj)²/σn(xi)²) (Definition 2), which covers ε-ball and k-nearest neighbour graphs; scale functions converging after rescaling, with a polynomial number of points in each neighbourhood (p. 282).
  • An open conjecture for directed graphs. The marginal densities must be uniformly equicontinuous: “For undirected spatial graphs, this is always true (Croydon and Hambly, 2008), but for directed graphs it is an open conjecture from (Hashimoto et al., 2015b)” (n. 10, p. 282). A k-nearest-neighbour graph, used in §6.3, is directed.
  • A window growing with the vocabulary, tn, so that every pair co-occurs in the limit (n. 5), with corpus size m → ∞ and vocabulary n → ∞ (n. 6).
  • Norm assumptions for SVD and negative sampling: the true embedding’s norms must match the unigram frequencies (p. 279; Lemma 7). The two statements differ: σ⁻¹‖xi‖² = log(Ci/√∑Cj) in §5.1, and ‖xi‖/σ² = (Ci/∑Cj)^½ in Lemma 7.
  • Dimension known: GloVe “can recover the true metric provided that we set d correctly” (p. 278).

Key results

Embeddability of co-occurrence data (§3, pp. 275–276)

  • Normalized PMI against MEN similarity judgments: Pearson r = 0.75 (Fig. 2). The normalization, unigram frequency to the 3/4 power, was chosen because it “maximizes the linear correlation in Figure 2” (n. 2).
  • Tversky and Hutchinson’s nearest-neighbour statistics (Table 2): centrality C and reciprocity Rf. “Under the GS model … C ≤ 2 with high probability as the number of words n → ∞”, “typical non-asymptotic values of C range between 1 and 3, while non-embeddable hierarchical structures have C > 10”; Rf “should be greater than 0.5” (pp. 275–276).
sourceCRf
free association1.510.48
Wikipedia2.210.63
word2vec corpus2.240.73
GloVe corpus2.660.62

The text reports only the corpora, “C ∈ [2.21, 2.66] and Rf ∈ [0.62, 0.73]”, calls the agreement “surprisingly high … on all three statistics” (there are two), and does not remark that the free-association data’s Rf = 0.48 is below its own 0.5 criterion, or that every corpus’s C exceeds the asymptotic bound of 2 (p. 276). Including “the” raises Wikipedia’s C from 2.21 to 3.46.

Lemma 1 and Corollary 6 (pp. 277, 282–283)

  • Lemma 1: there are aᵢ, bⱼ with −log Cᵢⱼ(tn) − aᵢ − bⱼ → ‖xi − xj‖² simultaneously over all i, j as m, n → ∞ (p. 277).
  • Corollary 6 (the precise form): for any δ, γ, n₀ there exist t̂, n > n₀ and terms bⱼⁿ such that, with probability at least 1 − γ, |−t̂ log P(X at time t̂·gn⁻² = xj | X₀ = xi) − t̂bⱼⁿ − ρσ(xi, xj)²| ≤ δ uniformly over pairs, where ρσ is the geodesic under the local scale σ (pp. 282–283). It rests on convergence of the walk to an Itô diffusion (Theorem 3, from earlier work), convergence of marginal densities (Lemma 4) and Varadhan’s small-time formula (Theorem 5). So the limit is approximate in t̂ and probabilistic in n, and the recovered distance is geodesic, scaled by t̂, not the Euclidean ‖xi − xj‖² of Lemma 1’s statement unless the space is flat.
  • My check. On 1,500 uniform points in the unit square with an unweighted ε-ball graph (ε = 0.08), I computed exact t-step transition matrices and fitted −log Pᵗᵢⱼ = c·‖xi − xj‖² + aᵢ + bⱼ over pairs closer than 0.3. At t = 1 the fit explains nothing (R² = 0.00): one-step co-occurrence carries no metric beyond the ball. At t = 4 and 8 it explains 94% of the variance, with slope roughly ∝ 1/t (98, then 41). At t = 40, when the walk spans the square, it falls to 75%. That matches the corollary: the relation emerges over many steps and holds while the walk’s spread is small against the domain.

Embedding algorithms as metric recovery (§5.1, pp. 278–279; Appendix B)

  • GloVe is “a weighted multidimensional scaling (MDS) objective”, and under Lemma 1 the true embedding x̂ᵢ = ĉᵢ = xᵢ/σ with zero biases is a global minimum (p. 278).
  • word2vec (softmax skip-gram) is the stochastic neighbour embedding objective weighted by ∑ₖCᵢₖ, with the global optimum at x̂ᵢ = ĉᵢ = xᵢ(√2/σ) (p. 279; Theorem 8). For negative sampling the true embedding is a global minimum under a further norm assumption.
  • PMI-SVD (Levy and Goldberg) recovers the embedding under the norm assumption, since Mᵢⱼ → ⟨xi, xj⟩; “Centering the matrix Mij before obtaining the SVD would relax the norm assumption, resulting exactly in classical MDS (Sibson, 1979)” (p. 279). Lemma 7 states recovery “under the same equivalence class”, that is up to an orthogonal map A (p. 283).
  • What “consistent” means in Theorem 8. The proof shows that the objective value at the true embedding comes within nδ₀ of a lower bound on the global minimum, with high probability (p. 284). It does not show that minimizers are close to the true embedding. Only Lemma 7 bounds the embedding itself.

Metric regression (§5.2, pp. 279–280)

Cᵢⱼ ~ NegBin with E[Cᵢⱼ] = exp(−½‖xi − xj‖² + aᵢ + bⱼ) and Var = E²/θ + E, fitted by SGD. Its second-order Taylor expansion resembles GloVe, with the weight Cᵢⱼθ/(2(Cᵢⱼ + θ)) playing the part of GloVe’s f (p. 280). The paper writes GloVe’s weight as min(Cᵢⱼ, 100)^{3/4} on p. 278 and as max(Cᵢⱼ, xmax)^{3/4}, said to converge to xmax, on p. 280; the second is a misprint (min, and the limit is xmax

Experiments (§6, pp. 280–281; Appendix C)

  • Corpora of 2.4B, 6.4B and 5.8B tokens; 100K-word vocabularies; 300 dimensions, window 5, unweighted windows for all methods (p. 280; Appendix C). Window 5 is far from the growing window the theory needs.
  • Table 3 (GloVe corpus), L2 / cosine accuracy: on Google analogies overall, regression 72.6 / 73.7, GloVe 69.6 / 73.7, SVD 51.2 / 54.3, word2vec 71.1 / 73.3; on SAT, word2vec is best (42.0 / 42.0), regression next (39.2 / 37.8); on classification regression leads with L2 (87.6); on sequence completion regression leads narrowly (58.3 / 59.0). The differences among the three good methods are a few points.
  • Table 4: Isomap on a free-association graph (4,845 words) solves semantic Google analogies at 83.3% against 70.7% for the corpus embedding, and syntactic ones at 8.2% against 76.9% (p. 281). The corpus figures differ from Table 3’s regression results (75.5 semantic) and the paper does not say on which subset they were computed.
  • MNIST (4,000 images, 20-NN graph, 10 walks of 200 steps per vertex): 5-NN label purity t-SNE 91.4, regression 75.3, SNE 72.8, word2vec 68.7, SVD 68.0, GloVe 64.3, Isomap 49, PCA 48 (Fig. 3; p. 281). The text says “reducing from D = 256 to two dimensions”; MNIST images have 784 pixels, so a downsampled version was presumably used, and it is not described.
  • New datasets: 215 classification and 220 series-completion questions, built from WordNet relations and pruned by PMI (p. 280). PMI was used to build them, which may favour co-occurrence methods; the authors note only that they were built before training.

Claims

idclaimstrengthsupport
C1Under a metric random walk on a manifold, log co-occurrence over a growing window, less per-word terms, converges to squared geodesic distancestrong, conditionalCorollary 6 with proof (pp. 282–283), built on Theorem 3 and Varadhan’s formula; directed graphs depend on an open conjecture (n. 10); my numerical check agrees
C2Under that model, the true embedding is a global optimum of GloVe, softmax word2vec and (under a norm assumption) PMI-SVDmoderate to strongreparameterization arguments (pp. 278–279); Lemma 7 recovers the embedding up to an orthogonal map; Theorem 8 bounds only the objective value
C3Corpus co-occurrences are consistent with a Euclidean semantic spaceweak to moderater = 0.75 with MEN after a normalization chosen to maximize it (Fig. 2, n. 2); C and Rf in a non-asymptotic range for corpora; free association fails Rf; these are necessary conditions, not a test with power against alternatives
C4Metric regression is competitive with word2vec and GloVe on analogy, classification and series tasksmoderateTable 3, one configuration per method, no variance across runs
C5Word embedding methods applied to random walks on a neighbourhood graph do manifold learningmoderateMNIST, one subset, one metric (Fig. 3)
C6A metric built from human free-association responses solves semantic analogies better than corpus embeddings and syntactic ones hardly at allmoderateTable 4; subset unexplained

Concepts

  • Semantic space — “vector spaces over concepts where Euclidean distances between points are assumed to indicate semantic similarities” (p. 273).
  • Metric recovery — estimating the latent distances (and coordinates up to isometry) rather than optimizing an embedding for a task (p. 274).
  • Geometric sampling (GS) model — points drawn independently from a continuous density in a Euclidean space (Tversky and Hutchinson 1986, p. 275).
  • Centrality C and reciprocity Rf — (1/n)∑ᵢ(∑ⱼNᵢⱼ)² and (1/n)∑ᵢ∑ⱼNᵢⱼNⱼᵢ, with Nᵢⱼ = 1 iff i is j’s nearest neighbour (pp. 275–276).
  • Spatial graph — Definition 2 (p. 282).
  • Ideal point — the point a reasoning task asks for: B − A + C for an analogy, the centroid for a category, wₙ + (1/n)(wₙ − w₁) for a series (Appendix C.2, p. 284).

Connections

  • Levy and Goldberg (2014a, b): linear regularities beyond word2vec, and skip-gram with negative sampling as shifted-PMI factorization; the SVD case here extends the latter.
  • Arora et al. (2015): random walks and embeddings under isotropy assumptions; contrasted on p. 274 as not taking metric recovery as the object.
  • Rumelhart and Abrahamson (1973) and Sternberg and Gardner (1983): the psychometric semantic space and the ideal-point account of analogy, series and classification (Fig. 1, Table 1). Gentner (LIT-1810, p. 166) cites the same Rumelhart and Abrahamson model as unable to express higher-order relations.
  • Tenenbaum et al. (2000) (Isomap) and Hinton and Roweis (2002) (SNE): the manifold-learning side.
  • Hashimoto, Sun and Jaakkola (2015a, b): the random-walk-to-distance results Appendix A relies on. The broader preprint arXiv 1509.05808 is not this work (LIT-1801).
  • Alvarez-Melis and Jaakkola (2018), LIT-1818, by two of the same authors, aligns embedding spaces by Gromov–Wasserstein; this paper does not discuss alignment.

Bearing on the record

  • LIT-1818: the exchange’s “precursor” reading is right, and this paper supplies its reason. If embeddings recover a metric, two embeddings of one semantic space agree only up to an isometry (Lemma 7’s orthogonal map) and per-word normalizers. An alignment that uses only within-space distances, as GW does, asks for exactly what such embeddings can share. The paper itself never compares two spaces, and in its model the isometry would be found by Procrustes as well; GW’s advantage needs spaces whose metrics differ, which is outside this paper.
  • CLAIM-046: support, and a fit with A6’s caution. What the co-occurrence observables identify here is the metric; the coordinates are fixed only up to isometry. That is CLAIM-046’s point that different internal states can produce identical observations, in a worked case. A6’s caution is borne out by the paper’s own numbers. The link from co-occurrence to similarity judgment is a correlation of 0.75 after a tuned normalization (Fig. 2), and a metric built from people’s responses (free association, Table 4) behaves differently from the corpus metric: better on semantic analogies, near zero on syntactic ones. That is the kind of response-derived distance CLAIM-046 points to, though free association is a judgment of similarity, not a receiver’s response to a communicative act.
  • CLAIM-135: this paper reaches identification, under a model the authors disown as a model of language. Reconstruction is shown on benchmarks; identification up to isometry is proved for the random-walk model (Lemma 7; Corollary 6); nothing addresses whether the semantic space is the right kind. Theorem 8 is weaker than identification: it bounds the objective, not the embedding.
  • CLAIM-113 and THEORY-002: an instance of identification up to a symmetry group. What is recovered is the class of embeddings under the isometries of the latent space, the invariants of that group being the distances.
  • THEORY-183: a complement, through the logarithm. THEORY-183 finds that a spectral embedding of co-occurrences that depend only on separation on a continuum yields Fourier modes, circles and ripples. This paper works with the logarithm of the co-occurrences, which under its model is quadratic in distance, and with classical MDS on that, which recovers the coordinates. The two results agree once it is seen which matrix is factorized; the record should not read them as rival accounts of the same embedding.
  • THEORY-1154 (Gentner): the parallelogram rule is single-relation analogy. The ideal point B − A + C treats a relation as one displacement vector; nothing in this paper represents a relation among relations, so its analogy results test Gentner’s first two rules at most.
  • Should produce: THEORY-1128 (log co-occurrence under a metric random walk recovers the metric, and only the metric; Active) and THEORY-1124 (corpus co-occurrences fit a Euclidean semantic space; Proposed).
  • Machine-learning practice. The metric-regression method and its benchmark comparison (§§5.2, 6) are method evaluation for embeddings; the LIT carries the anthology-candidate flag for that part.

Limitations

  • The generative model is a tool, not language (p. 277), and the experiments use a window of 5 (Appendix C), not a window growing with the vocabulary.
  • The Euclidean-space evidence tests necessary conditions. C and Rf are nearest-neighbour statistics that tree-like data violate; passing them does not rule out other non-Euclidean structure, and the free-association data fail Rf.
  • Theorem 8 bounds objective values only. The word2vec “consistency” is weaker than recovery.
  • Directed graphs rest on an open conjecture (n. 10).
  • Single runs, no error bars in Tables 3–4 and Fig. 3, with fixed hyperparameters; GloVe’s step sizes had to be reduced to avoid NaNs (Appendix C.1).
  • Unexplained details: the MNIST dimension (256), the subset for Table 4, and the two norm assumptions. The series ideal point uses 1/n where the average step over n words is 1/(n − 1) (p. 284).
  • Published date. The paper’s first page says “Published 7/2016”; Crossref gives December 2016 (print). See LIT-1801.

Open questions

  • Does the log-quadratic relation hold for real corpora at the windows used in practice, or only for the theory’s growing windows? A measure of how −log Cᵢⱼ scales with window size on a real corpus would say.
  • Is the semantic space Euclidean, hyperbolic, or neither? A comparison of fit across geometries, with hierarchical vocabularies included, would test the hypothesis rather than its necessary conditions.
  • Does Theorem 8 extend to recovery of the embedding itself, for example by a strong-convexity argument on the SNE objective near the truth?

Backlinks