TL;DR
This paper introduces a novel "squashed shifted PMI" (oSPMI) matrix derived from word co-occurrence data. They demonstrate that this oSPMI matrix, when factorized, yields word embeddings comparable in quality to traditional methods, but with a surprising connection to complex networks and hyperbolic geometry. This work bridges the gap between static word embeddings and the emerging field of hyperbolic representation learning.
What Problem Does This Paper Address?
Modern natural language processing often relies on word embeddings to represent words as dense vectors. While contextualized embeddings (like those from BERT) have become dominant, static embeddings (like Word2Vec) still hold advantages in training speed and resource efficiency. A key theoretical underpinning of static embeddings is their connection to Pointwise Mutual Information (PMI) matrices. However, the exact relationship and potential for alternative matrix formulations remain areas of exploration. This paper investigates whether a modified PMI matrix, specifically a "squashed shifted PMI" (oSPMI), can also effectively generate high-quality word embeddings and, more importantly, uncover deeper structural connections between word representations, complex networks, and hyperbolic spaces.
Methods
The core of the paper lies in introducing and analyzing the Squashed Shifted PMI (oSPMI) matrix. The authors propose a modified Skip-Gram with Negative Sampling (SGNS) objective function, termed "Nonsigmoid SGNS," which, when optimized, directly leads to a low-rank approximation of this oSPMI matrix. This is a key departure from standard SGNS, which implicitly approximates a shifted PMI matrix.
The authors then explore the properties of the oSPMI matrix:
- Connection to Random Graphs: They show that the entries of the oSPMI matrix can be interpreted as connection probabilities for generating a random graph.
- Complex Network Properties: Empirically, these oSPMI-induced graphs exhibit characteristics of "complex networks," specifically strong clustering and scale-free degree distributions.
- Hyperbolic Geometry Connection: Building on prior work that establishes a duality between complex networks and hyperbolic spaces, the paper argues that the oSPMI matrix provides a direct link. They hypothesize that the distribution of oSPMI values is related to hyperbolic distances.
- Direct Matrix Factorization: Beyond the optimization approach, they also demonstrate that direct factorization of the oSPMI matrix using Singular Value Decomposition (SVD) can yield competitive word embeddings.
Datasets
The paper uses the following datasets for training and evaluation:
- text8: A standard corpus for word embedding evaluation.
- enwik9: Another corpus used for evaluating the properties of the oSPMI-induced graphs.
The authors filtered words appearing less than 5 times (for graph analysis) or 5 times (for embedding evaluation) to create their vocabularies.
Key Insights and Ideas
- Sigmoid is Not Essential for Quality: Removing the sigmoid function from the SGNS objective doesn't significantly degrade word embedding quality, suggesting that the underlying matrix factorization is more critical than the specific activation function.
- oSPMI as a Bridge: The oSPMI matrix acts as a crucial intermediary, connecting the seemingly disparate fields of word embeddings, complex network theory, and hyperbolic geometry.
- Hyperbolic Structure in Language: The paper provides empirical evidence that the structure of language, as captured by word co-occurrences, inherently possesses properties that can be modeled using hyperbolic geometry. This suggests that hyperbolic spaces might be a more natural fit for representing certain linguistic relationships than Euclidean spaces.
- Complex Networks as a Manifestation: The complex network properties observed in oSPMI-induced graphs are not just an abstract finding but are presented as a consequence of the underlying hyperbolic structure.
Key Results
- Competitive Word Embeddings: Word embeddings derived from the oSPMI matrix (either through Nonsigmoid SGNS optimization or SVD factorization) achieve performance comparable to standard SGNS and PMI+SVD methods on word similarity and analogy tasks (Table 1). For instance, OSPMI+SVD achieves a WordSim score of .657, close to SGNS's .678.
- Complex Network Properties Confirmed: The oSPMI-induced graphs exhibit high clustering coefficients (e.g., .1341 ±.0006 for text8, window=2) and scale-free degree distributions (Figure 3), characteristic of complex networks.
- Spectral Similarity: The spectral distributions of the oSPMI-induced graphs show similarities to those of known complex networks, deviating from the Wigner semicircle law (Figure 2).
- Distributional Similarity: The distribution of oSPMI values is found to be similar to, though shifted from, the distribution of hyperbolic distances (Figure 5), supporting the paper's core hypothesis.
Limitations and Future Work
- Binarization Degrades Performance: While a binarized version of the SPMI matrix (BSPMI) shows some information retention, it significantly degrades word embedding quality compared to the oSPMI matrix. This suggests that the continuous nature of the oSPMI values is important.
- Shift in Hyperbolic Distance: The primary difference between the oSPMI distribution and the hyperbolic distance distribution is a shift. The authors suggest this implies that PMI can be reinterpreted as the negative of hyperbolic distance, up to scaling and shifting.
- Novel Objects for Future Study: The paper introduces "Nonsigmoid SGNS" and the "Squashed Shifted PMI matrix" as novel objects that warrant further independent investigation.
- Hyperbolic Embeddings: While the paper establishes a connection, it doesn't explicitly train hyperbolic word embeddings using the oSPMI matrix. This could be a direct avenue for future research, potentially leading to more efficient and expressive hyperbolic models.
Summary updated