PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Dimensionality of Word Embedding

Zi Yin, Yuanyuan Shen

arXiv:1812.04224v1cs.LGcs.CLstat.ML

TL;DR

The paper asks how to select word-embedding dimensionality while balancing insufficient signal against excess noise and over-fitting. It introduces the unitary-invariant PIP loss and uses matrix perturbation theory to analyze this trade-off, yielding a theoretically justified dimensionality-selection procedure and conclusions about robustness.

  • Problem

    Embedding dimensionality lacks a universal selection criterion despite affecting representation quality, over-fitting, and computational cost.

  • Method

    The paper defines PIP loss and analyzes dimensionality using matrix perturbation theory, estimating and minimizing the loss between oracle and trained embeddings.

  • Results

    The analysis reveals a bias-variance trade-off in dimensionality selection, explains optimal dimensionality, and establishes robustness to over-fitting for algorithms including skip-gram and GloVe.

  • Takeaways & Limitations

    Minimizing PIP loss provides a theoretically justified, accurate, and fast procedure for selecting embedding dimensionality.

  • Takeaways & Limitations

    The theoretical setup includes assumptions such as symmetric iid zero-mean estimation noise with variance σ^2 entries and special-case orthonormal-column analysis.

Abstract

from arXiv · show

In this paper, we provide a theoretical understanding of word embedding and its dimensionality. Motivated by the unitary-invariance of word embedding, we propose the Pairwise Inner Product (PIP) loss, a novel metric on the dissimilarity between word embeddings. Using techniques from matrix perturbation theory, we reveal a fundamental bias-variance trade-off in dimensionality selection for word embeddings. This bias-variance trade-off sheds light on many empirical observations which were previously unexplained, for example the existence of an optimal dimensionality. Moreover, new insights and discoveries, like when and how word embeddings are robust to over-fitting, are revealed. By optimizing over the bias-variance trade-off of the PIP loss, we can explicitly answer the open question of dimensionality selection for word embedding.

1 Introduction

The paper addresses dimensionality selection as an open problem shaped by a trade-off between embedding quality, over-fitting, and computational cost. It introduces a PIP-loss framework and a mathematically grounded selection procedure, alongside a bias-variance account of optimal dimensionality and robustness.

  • Motivation: Dimensionality controls expressiveness, over-fitting, model complexity, training speed, and inferential latency.Small embeddings may fail to capture word relations, whereas large embeddings can over-fit and increase computational costs.
  • Motivation: Ad hoc choices and grid search make dimensionality selection costly, incomplete, and potentially inconsistent across functionality tests.Different tests, such as word relatedness and analogy, can produce conflicting results.
  • Contributions: The paper introduces PIP loss as a metric for embedding dissimilarity and develops a mathematical framework for dimensionality selection.The proposed procedure minimizes PIP loss and is cross-validated with grid search for LSA, skip-gram Word2Vec, and GloVe.
  • Contributions: The framework reveals a bias-variance trade-off that explains the commonly observed existence of an optimal embedding dimensionality.It also establishes that skip-gram and GloVe are robust to over-fitting using an exponent parameter α.

2 Preliminaries and Background Knowledge

The paper frames word embeddings through unitary invariance and low-rank matrix factorization. This background connects explicit and implicit embedding algorithms to matrix representations whose singular-value structure determines the resulting embeddings.

  • Matrix factorization: Most existing embedding algorithms can be formulated as explicit or implicit low-rank matrix approximations.This formulation supports analyzing diverse embedding methods within a common mathematical framework.
  • Unitary invariance: Word embeddings are unitary-invariant, so rotations preserve relative vector geometry and define equivalent embeddings.A unitary transformation multiplies vectors by a unitary matrix while preserving their relative geometry.
  • Explicit factorization: LSA obtains k-dimensional embeddings by truncating the SVD of a signal matrix and applying a power α to the truncated singular values.The signal matrix may be based on PMI, PPMI, or SPPMI co-occurrence statistics.
  • Exponent parameter: The exponent α controls embedding robustness against over-fitting, with α = 0.5 used in one factorization account to enforce symmetry.The paper later relates larger α to reduced sensitivity to excessively large dimensionality.
  • Implicit factorization: Skip-gram Word2Vec implicitly factorizes a PMI matrix, while negative sampling changes the associated signal matrix to shifted PMI.GloVe is described as an implicit symmetric factorization of a log-count matrix, potentially with bias vectors and exponent γ.

3 PIP Loss: a Novel Unitary-invariant Loss Function for Embeddings

The paper proposes PIP loss to compare embeddings through pairwise inner products rather than coordinates, respecting unitary invariance. This metric also links embedding similarity to functionality and enables dimensionality analysis.

  • Motivation and definition: PIP loss provides a unitary-invariant metric for evaluating dissimilarity between word embeddings.Direct coordinate comparisons are unsuitable because equivalent embeddings may differ by a unitary transformation.
  • Motivation and definition: Each PIP-matrix entry is the inner product between two vocabulary-word vectors, and PIP loss is the norm of the difference between two PIP matrices.The comparison applies to embedding matrices defined over a common vocabulary.
  • Unitary invariance: PIP loss measures relative-position shifts among vectors while removing dependence on any specific coordinate system.If one embedding is a unitary transformation of the other, their PIP loss is zero.
  • Functional interpretation: Because relatedness and analogy depend on vector inner products, small PIP loss implies small differences in these functionalities.The paper presents PIP loss as both a theoretical metric and a functionality-dissimilarity measure.

4 How Does Dimensionality Affect the Quality of Embedding?

The paper uses PIP loss and matrix perturbation theory to explain how embedding dimensionality creates a bias-variance trade-off, yielding an optimal dimensionality.

  • PIP loss: PIP loss measures dissimilarity between oracle and trained embeddings through their pairwise inner products.The trained embedding is computed from a noisy estimated signal matrix, and its loss depends on the selected dimensionality.
  • Special case: α = 0: For α = 0, the PIP loss decomposes into bias from discarded dimensions and variance from noise-induced subspace perturbations.The decomposition is derived using matrix perturbation theory under orthonormal-column assumptions.
  • Special case: α = 0: The optimal dimensionality k* lies between 0 and d because increasing k reduces lost signal but increases sensitivity to perturbations.Singular vectors associated with smaller singular values are more prone to noise perturbation.
  • Generic case: α ∈ (0, 1]: In the generic case, the bias term reflects lost signal, while variance arises separately from errors in embedding magnitudes and directions.The generic theorem handles non-orthonormal embeddings using a telescoping application of the perturbation argument.
  • Signal-to-noise interpretation: The main theorem relates the bias-variance trade-off to the signal-to-noise ratio used in dimensionality selection.Too-small dimensionality discards signal and produces high bias, whereas too-large dimensionality includes noise and produces high variance.

5 Two New Discoveries

The paper explains over-fitting robustness and dimensionality selection through the PIP loss, whose bias-variance trade-off predicts when larger embeddings remain stable and identifies near-optimal dimensions.

  • Robustness to Over-Fitting: The bias term decreases with dimensionality, while variance terms grow with singular-gap-dependent rates, creating a fundamental bias-variance trade-off.For small λ_k, the variance rate increases as α decreases; when 0.5 ≤ α ≤ 1, it is bounded and sub-linear.
  • Robustness to Over-Fitting: When retained singular values contain more than half the spectrum’s total energy, increasing dimensionality has only a marginal effect on PIP loss.This explains why sufficiently large embeddings can remain robust to additional dimensions.
  • Robustness to Over-Fitting: Performance degradation from over-parametrization is more significant for smaller α in PPMI LSA evaluations on WordSim353 and MTurk771.The evaluations measure correlation between vector cosine similarity and human labels across dimensionalities.
  • Robustness to Over-Fitting: Skip-gram remains within 80% to 90% of optimal performance at k = 10000, and GloVe shows the same qualitative robustness to over-parametrization.The skip-gram result holds on analogy and relatedness tests; the GloVe observation is reported separately.
  • Optimal Dimensionality Selection: The PIP-loss-minimizing dimensionality k* can be estimated from the spectrum and noise variance, then used to define sub-optimal dimensionality intervals.A p% interval contains dimensions whose PIP loss is at most p% worse than the optimum.
  • Optimal Dimensionality Selection: Empirical optima closely match PIP-loss selections: LSA optima fall within the 5% interval except at α = 0, while skip-gram and GloVe optima fall within 5% or 10% intervals.For LSA, the exception falls within the 20% interval; skip-gram has one 5% and two 10% matches, while GloVe has two 5% and one 10% matches.

6 Conclusion

The paper presents a theoretically justified framework for selecting word-embedding dimensionality, centered on PIP loss and a bias-variance trade-off. It also reports robustness findings and validation on real datasets.

  • The framework uses PIP loss to analyze dimensionality selection through matrix perturbation theory.It applies to explicit or implicit matrix-factorization algorithms, including LSA, skip-gram, and GloVe.
  • The proposed procedure estimates and minimizes PIP loss to select dimensionality theoretically, accurately, and quickly.
  • The analysis links dimensionality selection to a bias-variance trade-off and explains the existence of an optimal dimensionality.
  • The paper finds that embeddings trained by the studied algorithms are robust to over-fitting and relates this robustness to exponent parameter α.
  • The paper validates its theoretical discoveries on real datasets.

7 Appendix

The appendix proves that small PIP loss implies two embeddings are approximately related by a unitary transformation, and establishes a principal-angle identity used in the analysis.

  • Unitary alignment: Small PIP loss implies F ≈ ET for some unitary matrix T.The proof compares the singular vectors and singular values of E and F.
  • Unitary alignment: The argument uses SVDs, induction over singular pairs, and the Courant-Fischer minimax characterization.The proof assumes simple singular values while extending the comparison across the remaining singular pairs.
  • Principal-angle lemma: Lemma 4 characterizes the SVD of an inner product of orthogonal matrices through the principal angles between their subspaces.The resulting singular values involve sin(Θ), connecting the inner product to subspace separation.
  • Principal-angle lemma: The lemma yields spectral- and Frobenius-norm identities for differences between orthogonal projectors.These identities express projector discrepancies through the cross-subspace inner product.
  • Proof conventions: The appendix omits identity and zero sub-blocks for simplicity and refers readers to classical CS-decomposition treatments for full details.The cited treatments include Stewart and Sun, Paige and Wei, Davis and Kahan, and Kato.

7.4 Proof of Theorem 2

The proof approximates the PIP discrepancy by decomposing it into telescoping terms after matching the dimensions of the reference and trained embeddings.

  • Telescoping decomposition: The diagonal signal matrix is written as a telescoping sum of successive singular-value contributions.The construction uses descending singular values and adopts λd+1 = 0.
  • Dimension matching: The reference embedding is partitioned into leading and trailing blocks so its dimensions match the trained embedding matrix.The corresponding diagonal blocks separate the first k singular values from λk+1 through λd.
  • Termwise approximation: The PIP discrepancy is split into three terms, which are then approximated separately.The proof computes the first term directly and bounds the second using the telescoping observation and Lemma 1.

7.5 Proof of Lemma 2

This section develops a perturbation analysis for random noise, replacing loose worst-case subspace bounds with a sharper bound that accounts for every singular-value gap.

  • Problem with worst-case bounds: Classical sine Θ bounds can become extremely loose when the smallest spectral separation δk is small.The minimax bound remains tight for the maximum possible discrepancy, but does not reflect the random-noise setting considered here.
  • Perturbation approximation: The proof models subspace perturbation with block matrices and a linear operator T acting on the off-diagonal correction P.Dropping second-order terms yields the approximation P ≈ T^-1(E21) when T is invertible.
  • Invertibility condition: T is invertible when the spectra of D0 and D1 do not overlap, equivalently when δk > 0.Its eigenvalues are differences between singular values from the two spectral blocks.
  • Sharper random-noise bound: The resulting bound is sharper than the sine Θ theorem because it incorporates every singular-value gap rather than only the smallest gap.The passage reports that this advantage appears in both simulations and real data.

7.7 Growth Rate Analysis of the Variance Terms

The variance terms grow with dimensionality at related rates, while singular-value gaps influence the dominant contribution. The smallest non-zero singular value can offset a first-order effect through its gap to zero.

  • The last variance term increases at the same rate as the second term.
  • When r≤k<s, the square-root term is dominated by (λ_k −λ_k+1)^−1 as the relevant gap changes.
  • The gap of the smallest non-zero singular value λ_d to zero can potentially offset the first-order effect.

7.8 Experimentation Setting for Dimensionality Selection Time Comparison

The experiments compare PIP-loss minimization with empirical dimensionality selection across LSA, skip-gram, and GloVe. The PIP procedure sweeps all dimensionalities efficiently using one SVD, while empirical methods evaluate candidate dimensions on test sets or trained embeddings.

  • PIP-loss minimization estimates the spectrum of M and noise standard deviation σ before evaluating each dimensionality k.The signal embedding is generated with a random orthogonal matrix because orthogonal choices are equivalent under unitary invariance.
  • One full sweep over dimensionalities is equivalent to a single SVD of the noisy matrix M + Z.This makes evaluating the PIP loss across all k efficient.
  • The same PIP-based method is applied to LSA, skip-gram, and GloVe using PPMI, PMI, and log-count signal matrices, respectively.
  • For LSA, truncating a full SVD at k produces the embedding, whose dimensionality is evaluated on test sets that may report different optima.The cited test sets are from Halawi et al. (2012) and Finkelstein et al. (2001).
Loading 1812.04224v1…