Source-linked AI summary
Sparse Overcomplete Word Vector Representations
Manaal Faruqui, Yulia Tsvetkov, Dani Yogatama, Chris Dyer, Noah Smith
TL;DR
Dense word vectors do not resemble interpretable lexical-semantic theories. The paper transforms them into sparse, optionally binary overcomplete vectors, finding improved benchmark performance and greater human interpretability, while the binarization optimization is computationally intractable at large scale.
Problem
Dense distributed word vectors differ from lexical-semantic theories centered on interpretable word classes and meaning relations.
Method
A principled method transforms dense word vectors from state-of-the-art models into sparse, optionally binary overcomplete representations.
Results
Sparse and binarized overcomplete vectors outperform corresponding initial vectors across benchmark tasks, while sparse vectors improve human word-intrusion interpretability from 57% to 71% agreement.
Takeaways & Limitations
The transformed vectors combine automatically discovered, interpretable sparsity with improved performance on semantic and syntactic evaluation benchmarks.
Takeaways & Limitations
The binarization transformation is an NP-hard mixed integer bilinear program with approximately KV variables, reaching 100 million when V = 100,000 and K = 1,000.
Abstract
from arXiv · showhide
Current distributed representations of words show little resemblance to theories of lexical semantics. The former are dense and uninterpretable, the latter largely based on familiar, discrete classes (e.g., supersenses) and relations (e.g., synonymy and hypernymy). We propose methods that transform word vectors into sparse (and optionally binary) vectors. The resulting representations are more similar to the interpretable features typically used in NLP, though they are discovered automatically from raw corpora. Because the vectors are highly sparse, they are computationally easy to work with. Most importantly, we find that they outperform the original vectors on benchmark tasks.
1 Introduction
The paper addresses the mismatch between dense word vectors and interpretable lexical-semantic theories by introducing sparse transformations that preserve corpus-derived learning while improving utility and interpretability.
- Motivation: Lexical-semantic theories emphasize word classes and meaning relations, whereas distributed word vectors do not resemble these interpretable representations.This mismatch matters for theoretical understanding and computational models where interpretability is desired.
- Contribution: The authors introduce a principled sparse coding method that transforms any distributed word representation into sparse, optionally binary vectors without external information.The resulting vectors are longer and sparser, forming an overcomplete representation.
- Evaluation: Sparse vectors show consistent benefits on a suite of standard benchmark evaluation tasks across multiple state-of-the-art input word-vector models.The paper evaluates both semantic and syntactic benchmarks.
- Evaluation: Human word-intrusion experiments find that the sparse vectors are more interpretable than the original vectors.Interpretability is assessed by how coherently humans identify intruder words among dimension-ranked examples.
- Implications: The authors anticipate that sparse, binary vectors can serve as interpretable features in statistical NLP models and provide a public implementation.Their interpretability is intended to support error analysis and continued model development.
2 Sparse Overcomplete Word Vectors
The paper transforms dense word vectors into sparse overcomplete representations, optionally binarizing them, using optimization-based methods designed for interpretable NLP features.
- Sparse Coding: Method A converts dense input vectors into sparse overcomplete vectors by learning a dictionary and sparse coefficient matrix.The input matrix X has vector length L, while the learned representation A has length K with K > L.
- Sparse Nonnegative Vectors: Nonnegative sparse coding constrains representation vectors to be nonnegative, a property associated with interpretability.The constraint is applied to the representation vectors rather than the dictionary in this formulation.
- Optimization: The optimization uses AdaGrad-based regularized dual averaging and asynchronous updates to obtain sparse solutions efficiently.Regularized dual averaging is used because direct stochastic subgradient descent does not produce sparse solutions in bounded time.
- Binarizing Transformation: The direct binary optimization is NP-hard and involves approximately KV variables, reaching 100 million when V = 100,000 and K = 1,000.The reported variable count makes standard solution techniques intractable for that setting.
- Binarizing Transformation: Method B obtains binary sparse overcomplete vectors by projecting nonzero entries of nonnegative representations to 1 while preserving zeros.This relaxation avoids directly solving the mixed integer bilinear optimization problem.
3 Experiments
The experiments evaluate sparse overcomplete and binarized transformations against initial word vectors across benchmark tasks, finding consistent performance gains and a best vector-length ratio for method A.
- Experimental Setup: The evaluation uses one word-similarity benchmark for hyperparameter tuning and seven other tasks to assess the representations.The similarity task uses correlation with human judgments; the remaining tasks use classification accuracy from ℓ2-regularized logistic regression.
- Effects of Transforming Vectors: 4.2 points: sparse overcomplete vectors outperform corresponding initializers on average across all vector types and tasks.Improvements are consistent, except on SimLex, where sparse vectors underperform the skip-gram initializer and match the multilingual initializer.
- Effects of Transforming Vectors: 4.8 points: binarized overcomplete vectors outperform initializers on average across all vector types and tasks.They also exceed continuous sparse vectors by 0.6 points on average, although Glove is an exception to their usual advantage over sparsified variants.
- Effect of Vector Length: For Glove vectors with L = 300, K = 3,000, or K/L = 10, gives the best average performance across tasks.Performance gains increase monotonically with the ratio through 10, after which they begin to diminish.
- Alternative Transformations: Method A produces sparse overcomplete vectors, while the alternatives preserve the original length and include a binary transformation.The study subsequently focuses on method A and leaves binarization aside for deeper analysis.
4 Interpretability
The paper evaluates whether sparse overcomplete vectors are more interpretable than dense vectors using human word-intrusion judgments and qualitative dimension analysis.
- 4.1 Word Intrusion: Word intrusion experiments measure whether learned representation dimensions are coherent to humans.Judges identify an intruder among words ranked by a single dimension.
- 4.1 Word Intrusion: 100 instances per condition were evaluated by three judges for initial and sparse overcomplete vectors.The experiment used 25 selected dimensions for each of four initializer combinations.
- 4.1 Word Intrusion: 57% to 71%: inter-annotator agreement increased substantially for sparse vectors, with Fleiss’ κ rising from fair to moderate agreement.Table 5 reports accuracy, average inter-annotator agreement, and Fleiss’ κ.
- 4.2 Qualitative Evaluation of Interpretability: Top-ranked words formed better semantic groupings in sparsified GC dimensions than in initial GC dimensions.The qualitative comparison examined five dimensions with the highest variance in each representation.
- 4.2 Qualitative Evaluation of Interpretability: 102 common active dimensions out of 500 total were shared by the animal-related words in the sparsified GC visualization.The figure compares six words, with dimensions sorted by average value across the three animal vectors.
5 Related Work
The work builds on overcomplete feature learning, interpretable matrix factorization, and prior uses of sparsity in NLP, while presenting a sparse categorical word-vector representation.
- 5 Related Work: Overcomplete features have been widely used in image processing, computer vision, and signal processing.The paper states that no prior work obtained overcomplete word vectors that were both sparse and categorical.
- 5 Related Work: Nonnegative matrix factorization is often used for interpretable coding of information.The paper situates its approach alongside established interpretable coding methods.
- 5 Related Work: Sparsity constraints have been useful in NLP tasks including POS tagging, dependency parsing, text classification, and representation learning.Sparse Dirichlet priors in Bayesian lexical-semantic models are also cited as useful for downstream tasks.
- 5 Related Work: Figure 3 encodes negative values in red, positive values in blue, and zeroes in white.The visualization shows sparsified GC vectors.
6 Conclusion
The paper concludes that its transformation produces sparse, optionally binary vectors that outperform their source vectors and are more interpretable to humans.
- 6 Conclusion: The method converts word vectors from any state-of-the-art model into sparse and optionally binary word vectors.The transformed vectors are intended to resemble features used in NLP tasks.
- 6 Conclusion: The transformed vectors outperform their source vectors on semantic and syntactic benchmark evaluations.The conclusion reports this outcome across a suite of evaluation benchmarks.
- 6 Conclusion: Human word-intrusion detection finds sparse vectors more interpretable than dense vectors.This conclusion is based on the reported word-intrusion test.
A Initial Vector Representations (X)
The experiments start from four publicly available pretrained word-vector collections that differ in training data and estimation method.
- A Initial Vector Representations (X): Four publicly available pretrained word-vector collections serve as initial representations.The collections vary in the amount of data used and the estimation method.
- A Initial Vector Representations (X): Glove vectors have length 300 and were trained on 6 billion words from Wikipedia and English Gigaword.Glove uses aggregated global word-word co-occurrence statistics.
- A Initial Vector Representations (X): Skip-Gram vectors have length 300 and were trained on 100 billion words of Google News data.The model predicts words within a context window using a continuous projection layer.
- A Initial Vector Representations (X): Global Context vectors have length 50 and were trained on the first 1 billion words of English Wikipedia.The model incorporates local and document-level context features through a recursive neural network.
- A Initial Vector Representations (X): Multilingual vectors have length 48 and were trained on the 360-million-word WMT-2011 news corpus.They were learned using SVD followed by canonical correlation analysis on aligned words.
B Evaluation Benchmarks
The evaluation compares word-vector quality across five benchmark tasks, covering similarity, sentiment, question and document classification, and noun-phrase bracketing.
- The evaluation suite contains five benchmark tasks for assessing word-vector quality.
- Word Similarity: Word similarity is evaluated with WS-353 and SimLex-999, using human ratings and Spearman’s rank correlation between model and human rankings.WS-353 is also used to tune sparse-vector learning hyperparameters, while the remaining tasks are held out.
- Sentiment Analysis (Senti): Sentiment classification uses averaged sentence word vectors to predict positive or negative labels in a movie-review treebank.The dataset contains 6,920 training, 872 development, and 1,821 test sentences.
- Question Classification (TREC): TREC question classification assigns questions to six types, using the average of their word vectors as features.The dataset contains 5,452 labeled training questions and 500 test questions.
- 20 Newsgroup Dataset: The 20 Newsgroups evaluation includes binary classification of Sports, Computer, and Religion document pairs using averaged word-vector features.The tasks distinguish baseball from hockey, IBM from Mac, and atheism from christian.
- NP bracketing (NP): NP bracketing predicts the parse-tree structure of three-word noun phrases from concatenated word vectors.Examples distinguish right bracketing in local (phone company) from left bracketing in (blood pressure) medicine.