Unsupervised Sparse Vector Densification for Short Text Similarity

Yangqiu Song, Dan Roth

Introduction

Short text snippets, such as sentences or news headers, pose a significant challenge for traditional Natural Language Processing (NLP) techniques. Standard vector representations, like Bag-of-Words (BoW) or Explicit Semantic Analysis (ESA), rely on statistical overlap between documents. While effective for long-form text, these representations become extremely sparse for short documents. Two semantically related snippets may share no common words or Wikipedia concepts, resulting in a cosine similarity of zero. This "sparsity trap" severely degrades performance in tasks like document classification and semantic similarity measurement.

The Dense-ESA Framework

To address this, we introduce Dense-ESA, an unsupervised framework that densifies sparse vector representations by leveraging the relational information in dense word embeddings (e.g., word2vec). Unlike standard ESA, which only considers exact matches between concept dimensions, Dense-ESA "aligns" non-zero dimensions based on their semantic proximity.

The framework utilizes word2vec embeddings trained on Wikipedia to represent each ESA concept title as a dense 200-dimensional vector. We explore three distinct alignment mechanisms:

  1. Similarity Augmentation ($S_A$): A many-to-many approach averaging all pairwise similarities between terms, dampened by an RBF kernel.
  2. Maximum Matching ($S_M$): A many-to-one approach where each term in the source text is matched to its most similar counterpart in the target.
  3. Hungarian Method ($S_H$): A one-to-one approach using combinatorial optimization to find the globally optimal alignment between unique terms.

Experimental Results

The proposed methods were evaluated across three benchmarks: the 20-Newsgroups dataset for dataless classification, the Lee et al. (2005) document similarity set, and the ACE2005 event classification task.

Dataless Classification

In the "dataless" setting, documents are classified by comparing their vector representations directly to label vectors (e.g., the concept "Autos"). Dense-ESA significantly outperforms standard ESA, particularly on "difficult" pairs like Autos vs. Motorcycles, where vocabulary overlap is minimal.

Distribution of similarity scores for 'easy' (left) and 'difficult' (right) classification tasks, comparing ESA and Dense-ESA.

As shown in the box plots above, Dense-ESA provides a clearer separation of similarity scores compared to the baseline ESA, especially in the challenging Autos vs. Motorcycles task where standard ESA achieved only 46.64% accuracy compared to Dense-ESA's 59.65%.

Impact of Sparsity

A key finding is that Dense-ESA maintains high accuracy even as the number of available concepts decreases (increasing sparsity).

Accuracy across different NLP tasks as a function of the number of concepts, comparing Dense-ESA variants against the ESA baseline.

In the performance plots above, we observe that while standard ESA (blue line) requires a large number of concepts to achieve peak performance, Dense-ESA variants (particularly the "Average" and "Hungarian" versions) reach high accuracy much earlier. This demonstrates the robustness of densification in low-information scenarios.

Conclusion

Dense-ESA effectively bridges the gap between interpretable sparse representations and relational dense embeddings. By aligning concepts rather than relying on exact matches, the method significantly improves short-text similarity measurement without the need for labeled training data. Future work will explore the computational optimization of the Hungarian method and the integration of these densified features into supervised deep learning models.

Summary updated

Abstract

Sparse representations of text such as bag-ofwords models or extended explicit semantic analysis (ESA) representations are commonly used in many NLP applications. However, for short texts, the similarity between two such sparse vectors is not accurate due to the small term overlap. While there have been multiple proposals for dense representations of words, measuring similarity between short texts (sentences, snippets, paragraphs) requires combining these token level similarities. In this paper, we propose to combine ESA representations and word2vec representations as a way to generate denser representations and, consequently, a better similarity measure between short texts. We study three densification mechanisms that involve aligning sparse representation via many-to-many, many-to-one, and oneto-one mappings. We then show the effectiveness of these mechanisms on measuring similarity between short texts.
BibTeX
@inproceedings{song2015unsupervised,
  author = {Yangqiu Song and Dan Roth},
  title = {{Unsupervised Sparse Vector Densification for Short Text Similarity}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2015},
  doi = {10.3115/v1/n15-1138},
}
Figure