On Extending NLP Techniques from the Categorical to the Latent Space: KL Divergence, Zipf's Law, and Similarity Search

Adam Hare, Yu Chen, Yinan Liu, Zhenming Liu, Christopher G. BrintonarXiv 2020 · OpenReview

Abstract

Despite the recent successes of deep learning in natural language processing (NLP), there remains widespread usage of and demand for techniques that do not rely on machine learning. The advantage of these techniques is their interpretability and low cost when compared to frequently opaque and expensive machine learning models. Although they may not be as performant in all cases, they are often sufficient for common and relatively simple problems. In this paper, we aim to modernize these older methods while retaining their advantages by extending approaches from categorical or bag-of-words representations to word embeddings representations in the latent space. First, we show that entropy and Kullback-Leibler divergence can be efficiently estimated using word embeddings and use this estimation to compare text across several categories. Next, we recast the heavy-tailed distribution known as Zipf's law that is frequently observed in the categorical space to the latent space. Finally, we look to improve the Jaccard similarity measure for sentence suggestion by introducing a new method of identifying similar sentences based on the set cover problem. We compare the performance of this algorithm against several baselines including Word Mover's Distance and the Levenshtein distance.

Introduction

In the contemporary NLP landscape, practitioners often face a dichotomy. On one side, traditional frequency-based models (such as Bag-of-Words) are computationally efficient and highly interpretable but lack semantic depth—failing, for instance, to recognize the relationship between "king" and "queen." On the other side, massive Deep Learning (DL) models like BERT or GPT capture nuanced semantics but operate as "black boxes." These models are expensive to train, computationally intensive to deploy, and often represent overkill for tasks like document indexing or basic statistical analysis.

This research seeks a "middle ground" by generalizing statistical tools designed for discrete categorical data to the continuous, high-dimensional latent space of word embeddings. By treating documents as continuous "point clouds" rather than discrete bags of words, we develop efficient, statistically sound tools for text comparison and similarity search that offer semantic depth with the transparency of traditional methods.

Methodology

Conceptual framework for extending NLP techniques from discrete frequency models to continuous embedding models.

We propose three primary "remastered" toolkits to bridge the gap between discrete and continuous representations:

  1. Divergence Estimation: To compare documents without requiring exact word matches, we employ a non-parametric $k$-Nearest Neighbor ($k$-NN) estimator. Instead of counting word frequencies, we treat words as samples from a continuous distribution and estimate the Kullback-Leibler (KL) divergence based on the Euclidean distances between word embeddings. We utilize the faiss library to ensure this remains computationally scalable.
  2. Latent Zipfian Analysis: To determine if Zipf’s Law—the observation that a few words appear very frequently while most appear rarely—persists in the latent space, we perform $k$-means clustering on sentence embeddings. We then analyze the distribution of cluster sizes to identify power-law structures.
  3. Set-Cover Similarity Search: We replace standard Jaccard similarity with a Greedy Set Cover algorithm. A query sentence is viewed as a set of "concepts" (defined by the neighborhood around its word embeddings). The algorithm selects sentences from a database that "cover" these concepts most efficiently, penalizing redundancy to ensure a diverse set of results.

Latent Space Characteristics

A key finding of this work is the relationship between the latent space and linguistic structure. Our analysis reveals that word embeddings naturally cluster by Part of Speech (POS). On average, approximately 70% of a word's nearest neighbors in the latent space share its POS. This supports the theory that POS acts as a "latent variable" that explains why Zipf’s Law emerges in natural language.

t-SNE visualizations across Brown, Gutenberg, and RACE corpora, demonstrating that word embeddings naturally cluster by Part of Speech (POS).

Results and Discussion

Our evaluation across five diverse corpora (Gatsby, Reuters, Brown, Gutenberg, and RACE) yielded several significant insights:

  • Classification Accuracy: The $k$-NN KL divergence estimator outperformed traditional frequency-based baselines in labeling books by genre and reading level as sample sizes increased (e.g., at 32,000 words).
  • Persistence of Zipf’s Law: Even when moving from discrete words to clustered "semantic regions," the heavy-tailed distribution remains. Log-log plots of cluster sizes showed slopes very close to -1 (the Zipfian ideal), particularly for the Gatsby and Brown datasets.
  • Recommendation Diversity: In a quantitative test of 5,000 queries, the Set Cover approach produced significantly more unique suggestions (89% unique) compared to the Jaccard baseline (57%). Unlike standard measures that return variations of the same sentence, Set Cover explicitly seeks different ways to cover the query's meaning.
  • User Preference: In a head-to-head questionnaire with 107 students, the Set Cover algorithm was preferred approximately 44% of the time over all other baselines combined, as it provided greater variety and "flavor" in its suggestions.

Conclusion

This work demonstrates that classic NLP techniques can be effectively modernized for the era of embeddings without sacrificing interpretability or efficiency. While our KL divergence estimator can occasionally produce negative values if sample sizes differ by orders of magnitude, the overall framework provides a robust alternative to expensive deep learning models for many tasks. Future work will focus on optimizing these algorithms for GPU architectures and extending these tools to multi-lingual settings and creative writing assistance applications.

Summary updated

Abstract

Despite the recent successes of deep learning in natural language processing (NLP), there remains widespread usage of and demand for techniques that do not rely on machine learning. The advantage of these techniques is their interpretability and low cost when compared to frequently opaque and expensive machine learning models. Although they may not be be as performant in all cases, they are often sufficient for common and relatively simple problems. In this paper, we aim to modernize these older methods while retaining their advantages by extending approaches from categorical or bag-of-words representations to word embeddings representations in the latent space. First, we show that entropy and Kullback-Leibler divergence can be efficiently estimated using word embeddings and use this estimation to compare text across several categories. Next, we recast the heavy-tailed distribution known as Zipf's law that is frequently observed in the categorical space to the latent space. Finally, we look to improve the Jaccard similarity measure for sentence suggestion by introducing a new method of identifying similar sentences based on the set cover problem. We compare the performance of this algorithm against several baselines including Word Mover's Distance and the Levenshtein distance.
BibTeX
@misc{hare2020extending,
  author = {Adam Hare and Yu Chen and Yinan Liu and Zhenming Liu and Christopher G. Brinton},
  title = {{On Extending NLP Techniques from the Categorical to the Latent Space: KL Divergence, Zipf's Law, and Similarity Search}},
  year = {2020},
  eprint = {2012.01941},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2012.01941},
}
Figure