Fast PMI-Based Word Embedding with Efficient Use of Unobserved Patterns

Behrouz Haji Soleimani, Stan MatwinAAAI 2019 · DOI

Abstract

Traditional word embedding models often suffer from a "concentration effect" in high-dimensional spaces, where unrelated words are pushed too close together. We present KUBWE (Kernelized Unit Ball Word Embedding), a count-based algorithm that leverages unobserved word pairs—"negative patterns"—to improve representation quality. By employing a polynomial kernel and an efficient Vantage Point tree search, KUBWE achieves state-of-the-art performance on word similarity tasks while maintaining $O(|V| \log |V|)$ computational complexity.

Addressing the Curse of Dimensionality

Most contemporary word embedding models, such as Word2vec and GloVe, primarily focus on "positive" co-occurrences. While effective, this approach often leads to a concentration effect where clusters of unrelated words are insufficiently separated. Furthermore, as the dimensionality of embeddings increases, standard measures like cosine similarity lose their discriminative power—a phenomenon known as the "curse of dimensionality."

Distribution of cosine similarities as dimensionality increases, illustrating the concentration effect where values cluster around zero.

In high-dimensional spaces, random vectors tend to become nearly orthogonal, making it difficult for models to distinguish between varying degrees of relatedness. KUBWE addresses this by explicitly modeling the absence of co-occurrences as informative signals.

Methodology: KUBWE

KUBWE operates on a smoothed Positive Pointwise Mutual Information (PPMI) matrix, mapping words onto the surface of a hypersphere (unit ball). The objective function balances two primary forces:

  • Attractive Forces: Pull together words with high PPMI values.
  • Repulsive Forces: Push apart words that do not co-occur (zero PPMI).

To combat the curse of dimensionality, KUBWE applies a polynomial kernel $K(w_i, w_j) = (w_i \cdot w_j + 1)^p$ to the repulsive force. This kernel acts as a "contrast knob," amplifying the separation between words that are mistakenly close in high-dimensional space. To ensure scalability, the authors utilize a modified Vantage Point (VP) Tree to approximate repulsive forces, reducing computational complexity from $O(|V|^2)$ to $O(|V| \log |V|)$.

Experimental Setup and Results

The model was trained on a 2016 English Wikipedia dump (2.1 billion tokens). Evaluation spanned eight standard similarity datasets (e.g., WordSim353, SimLex-999, MEN) and Google’s analogy dataset.

KUBWE outperformed established models like SGNS, GloVe, and FastText on 7 out of 8 similarity benchmarks using 100-dimensional embeddings.

Qualitative Semantic Separation

PCA visualizations demonstrate that KUBWE creates significantly cleaner gaps between distinct semantic clusters compared to traditional models. For instance, the separation between "animals" and "food" categories is markedly more pronounced, reducing the number of unrelated words lingering near cluster boundaries.

PCA visualization of KUBWE embeddings showing clear separation between semantic clusters like food (blue) and animals (red).

Key Insights

  • Negative Patterns are Informative: The absence of a co-occurrence is a strong signal. By weighting these "negative examples," the latent space is utilized more efficiently.
  • Kernelization as a Buffer: The polynomial kernel allows the model to differentiate between points that standard cosine similarity would treat as equally distant in high dimensions.
  • Hyperparameter Heuristics: The authors suggest that the kernel degree $p$ should be roughly proportional to the log of the dimensionality ($p \approx \log d$).

Conclusion

KUBWE demonstrates that efficient use of unobserved patterns, combined with kernelization, can significantly enhance word representations. While highly effective for similarity tasks, GloVe remains superior in analogy tasks, suggesting that different objectives favor different linguistic properties. Future work will focus on automated kernel parameter selection and deeper theoretical analysis of repulsive forces.

Summary updated

BibTeX
@inproceedings{soleimani2019fast,
  author = {Behrouz Haji Soleimani and Stan Matwin},
  title = {{Fast PMI-Based Word Embedding with Efficient Use of Unobserved Patterns}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33017031},
}
Figure