Elamur Research⌕
☰
home / papers / 2015 / Sparse Overcomplete Word Vector Representations

Sparse Overcomplete Word Vector Representations

Paper · 2015 · Manaal Faruqui, Yulia Tsvetkov, Dani Yogatama et al.

Summary

Dense word embeddings work well in practice, but they look nothing like the discrete classes and relations of lexical semantic theory, and their dimensions are hard to interpret. Faruqui et al. propose a post-processing step that turns any pre-trained embedding matrix into longer ("overcomplete") vectors in which most entries are zero.

  • Method A uses sparse coding. Each word vector is reconstructed from a learned dictionary of basis vectors, with an ℓ1 penalty on the codes. Optimization uses an AdaGrad variant of regularized dual averaging with asynchronous parallel updates.
  • Method B additionally forces the codes to be nonnegative, then sets every nonzero value to 1, which yields binary features.

The approach needs no external lexicon or resource. The authors applied it to four embedding sets: Glove, Skip-Gram, Global Context and Multilingual. The resulting vectors are over 90% sparse and, on average, outperform their dense sources across these tasks:

  • word similarity;
  • sentiment;
  • question classification;
  • newsgroup categorization;
  • NP bracketing.

In a word intrusion study, humans also found their dimensions more interpretable. This matters because sparse binary features fit naturally into classic feature-based NLP models and make error analysis easier.

Key points

  • Input vectors and settings:
    • Glove (300d, 6B words), Skip-Gram (300d, 100B words of Google News), Global Context (50d) and Multilingual (48d, from WMT-2011).
    • The output length K is 10× or 20× the input length: 3000, 3000, 500 and 960 respectively.
    • Sparsity ranges from 91% to 98%.
  • Hyperparameters were tuned only on WS-353:
    • grid search over λ ∈ {0.1, 0.5, 1.0} and K ∈ {10L, 20L}, with at least 90% sparsity required;
    • τ was set so that dictionary atoms stay near unit norm.
  • The seven held-out evaluations are:
    • SimLex-999 (Spearman correlation);
    • Senti (Stanford sentiment treebank, binary);
    • TREC question types;
    • three 20 Newsgroups binary tasks;
    • NP bracketing from the Penn Treebank.
    • The classification tasks use ℓ2-regularized logistic regression.
  • Average gains over the dense initializers:
    • sparse vectors (A): +4.2 points;
    • binarized vectors (B): +4.8 points, which is also 0.6 points above the sparse intermediate vectors.
    • Exceptions: on SimLex, sparse vectors are worse than Skip-Gram and only on par with Multi. Binarization does not help for Glove.
  • Code is released at github.com/mfaruqui/sparse-coding.

Interesting ideas

  • I1. Embeddings as a post-hoc transform. Sparsity is applied after training, so it works on top of any existing embedding without retraining. This makes it cheap to try on embeddings for other languages, including Ukrainian, or other domains.
  • I2. Overcompleteness plus sparsity. Expanding to many more dimensions while keeping only a few active per word increases separability. It also yields individual dimensions that behave like interpretable features or clusters.
  • I3. Cheap binarization by relaxation. Exact binary coding is an NP-hard mixed-integer problem. The authors instead solve a nonnegative sparse problem and threshold the nonzeros to 1. The same relaxation trick could be reused whenever discrete features are needed from continuous models.
  • I4. Dual averaging for real zeros. Plain stochastic subgradient descent rarely produces exact zeros under an ℓ1 penalty. Regularized dual averaging truncates small average gradients, which yields truly sparse solutions, and each word can be optimized in parallel.
  • I5. Strict evaluation design. Tuning on a single development benchmark (WS-353) and keeping all other tasks fully held out is a disciplined setup. Adding a human word intrusion test measures interpretability directly, not just accuracy.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Carnegie Mellon UniversityPittsburgh · United States365 works · 158,048 citations

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 9,085 worksArtificial Intelligence · 8,888 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 works

Cite

Cite as Manaal Faruqui, Yulia Tsvetkov, Dani Yogatama, Chris Dyer and Noah A. Smith. 2015. Sparse Overcomplete Word Vector Representations. Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.3115/v1/p15-1144

@inproceedings{faruqui2015sparse,
  title = {{Sparse Overcomplete Word Vector Representations}},
  author = {Manaal Faruqui, Yulia Tsvetkov, Dani Yogatama, Chris Dyer and Noah A. Smith},
  booktitle = {Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)},
  year = {2015},
  doi = {10.3115/v1/p15-1144},
  url = {https://doi.org/10.3115/v1/p15-1144}
}

References

60 references, 14 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Faiz A. Al-Khayyal and James E. Falk. 1983. Jointly constrained biconvex programming. Mathematics of Operations Research, pages 273–286. find
  2. Ron Artstein and Massimo Poesio. 2008. Inter-coder agreement for computational linguistics. Computational Linguistics, 34(4):555–596. find
  3. Collin F. Baker, Charles J. Fillmore, and John B. Lowe. 1998. The Berkeley FrameNet project. In Proc. of ACL.
  4. Mohit Bansal, Kevin Gimpel, and Karen Livescu. 2014. Tailoring continuous word representations for dependency parsing. In Proc. of ACL.
  5. Yoshua Bengio, Aaron Courville, and Pascal Vincent. 2013. Representation learning: A review and new perspectives. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8):1798–1828.
  6. Jonathan Chang, Sean Gerrish, Chong Wang, Jordan L. Boyd-Graber, and David M. Blei. 2009. Reading tea leaves: How humans interpret topic models. In NIPS.
  7. Andrzej Cichocki, Rafal Zdunek, Anh Huy Phan, and Shun-ichi Amari. 2009. Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multi-way Data Analysis and Blind Source Separation. John Wiley & Sons. find
  8. Mark Davies and Joseph L Fleiss. 1982. Measuring agreement for multinomial data. Biometrics, pages 1047–1051. find
  9. David L. Donoho, Michael Elad, and Vladimir N. Temlyakov. 2006. Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Transactions on Information Theory, 52(1). find
  10. John Duchi, Elad Hazan, and Yoram Singer. 2010. Adaptive subgradient methods for online learning and stochastic optimization. Technical Report EECS-2010-24, University of California Berkeley. find
  11. John C. Duchi, Alekh Agarwal, and Martin J. Wainwright. 2012. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic Control, 57(3):592–606. find
  12. Manaal Faruqui and Chris Dyer. 2014. Improving vector space word representations using multilingual correlation. In Proc. of EACL.
  13. Manaal Faruqui, Jesse Dodge, Sujay K. Jauhar, Chris Dyer, Eduard Hovy, and Noah A. Smith. 2015. Retrofitting word vectors to semantic lexicons. In Proc. of NAACL. find
  14. Lev Finkelstein, Evgeniy Gabrilovich, Yossi Matias, Ehud Rivlin, Zach Solan, Gadi Wolfman, and Eytan Ruppin. 2001. Placing search in context: the concept revisited. In Proc. of WWW. find
  15. Jerome Friedman, Trevor Hastie, and Robert Tibshirani. 2008. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 9(3):432– 441. find
  16. Alona Fyshe, Partha P. Talukdar, Brian Murphy, and Tom M. Mitchell. 2014. Interpretable semantic vectors from a joint model of brain- and text- based meaning. In Proc. of ACL. find
  17. Alona Fyshe, Leila Wehbe, Partha P. Talukdar, Brian Murphy, and Tom M. Mitchell. 2015. A compositional and interpretable semantic space. In Proc. of NAACL. find
  18. Kuzman Ganchev, Ben Taskar, Fernando Pereira, and João Gama. 2009. Posterior vs. parameter sparsity in latent variable models. In NIPS. find
  19. Xavier Glorot, Antoine Bordes, and Yoshua Bengio. 2011. Domain adaptation for large-scale sentiment classification: A deep learning approach. In Proc. of ICML. find
  20. Joshua Goodman. 2004. Exponential priors for maximum entropy models. In Proc. of NAACL. find
  21. E. Grefenstette. 2013. Towards a formal distributional semantics: Simulating logical calculi with tensors. arXiv:1304.5823. find
  22. Jiang Guo, Wanxiang Che, Haifeng Wang, and Ting Liu. 2014. Revisiting embedding features for simple semi-supervised learning. In Proc. of EMNLP. find
  23. Georg Heigold, Erik McDermott, Vincent Vanhoucke, Andrew Senior, and Michiel Bacchiani. 2014. Asynchronous stochastic optimization for sequence training of deep neural networks. In Proc. of ICASSP. find
  24. Felix Hill, Roi Reichart, and Anna Korhonen. 2014. Simlex-999: Evaluating semantic models with (genuine) similarity estimation. CoRR, abs/1408.3456.
  25. Patrik O. Hoyer. 2002. Non-negative sparse coding. In Neural Networks for Signal Processing, 2002. Proc. of IEEE Workshop on. find
  26. Eric H. Huang, Richard Socher, Christopher D. Manning, and Andrew Y. Ng. 2012. Improving word representations via global context and multiple word prototypes. In Proc. of ACL.
  27. Jun’ichi Kazama and Jun’ichi Tsujii. 2003. Evaluation and extension of maximum entropy models with inequality constraints. In Proc. of EMNLP. find
  28. Douwe Kiela and Stephen Clark. 2013. Detecting compositionality of multi-word expressions using nearest neighbours in vector space models. In Proc. of EMNLP. find
  29. J. Richard Landis and Gary G. Koch. 1977. The measurement of observer agreement for categorical data. Biometrics, 33(1):159–174. find
  30. Angeliki Lazaridou, Eva Maria Vecchi, and Marco Baroni. 2013. Fish transporters and miracle homes: How compositional distributional semantics can help NP parsing. In Proc. of EMNLP. find
  31. Daniel D. Lee and H. Sebastian Seung. 1999. Learning the parts of objects by non-negative matrix factorization. Nature, 401(6755):788–791. find
  32. Honglak Lee, Alexis Battle, Rajat Raina, and Andrew Y. Ng. 2006. Efficient sparse coding algorithms. In NIPS. find
  33. Honglak Lee, Rajat Raina, Alex Teichman, and Andrew Y. Ng. 2009. Exponential family sparse coding with application to self-taught learning. In Proc. of IJCAI. find
  34. Beth Levin. 1993. English Verb Classes and Alternations: A Preliminary Investigation. University of Chicago Press. find
  35. Michael Lewicki and Terrence Sejnowski. 2000. Learning overcomplete representations. Neural Computation, 12(2):337–365. find
  36. Mike Lewis and Mark Steedman. 2013. Combined distributional and logical semantics. Transactions of the ACL, 1:179–192. find
  37. Mike Lewis and Mark Steedman. 2014. Combining formal and distributional models of temporal and intensional semantics. In Proc. of ACL. find
  38. Xin Li and Dan Roth. 2002. Learning question classifiers. In Proc. of COLING.
  39. Weixiang Liu, Nanning Zheng, and Xiaofeng Lu. 2003. Non-negative matrix factorization for visual coding. In Proc. of ICASSP. find
  40. Mitchell P. Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. 1993. Building a large annotated corpus of english: The penn treebank. Computational Linguistics, 19(2):313–330.
  41. André F. T. Martins, Noah A. Smith, Pedro M. Q. Aguiar, and Mário A. T. Figueiredo. 2011. Structured sparsity in structured prediction. In Proc. of EMNLP. find
  42. Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Efficient estimation of word representations in vector space.
  43. George A. Miller. 1995. WordNet: a lexical database for English. Communications of the ACM, 38(11):39–41.
  44. Brian Murphy, Partha Talukdar, and Tom Mitchell. 2012. Learning effective and interpretable semantic models using non-negative sparse embedding. In Proc. of COLING. find
  45. Jerome L. Myers and Arnold D. Well. 1995. Research Design & Statistical Analysis. Routledge. find
  46. Bruno A. Olshausen and David J. Field. 1997. Sparse coding with an overcomplete basis set: A strategy employed by v1? Vision Research, 37(23):3311 – 3325. find
  47. Denis Paperno, Nghia The Pham, and Marco Baroni. 2014. A practical and linguistically-motivated approach to compositional distributional semantics. In Proc. of ACL. find
  48. Michael Paul and Mark Dredze. 2012. Factorial LDA: Sparse multi-dimensional text models. In NIPS. find
  49. Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. Glove: Global vectors for word representation. In Proc. of EMNLP.
  50. Karin Kipper Schuler. 2005. Verbnet: A Broad-coverage, Comprehensive Verb Lexicon. Ph.D. thesis, University of Pennsylvania. find
  51. Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Y. Ng, and Christopher Potts. 2013. Recursive deep models for semantic compositionality over a sentiment treebank. In Proc. of EMNLP. find
  52. Kristina Toutanova and Mark Johnson. 2007. A bayesian lda-based model for semi-supervised part-of-speech tagging. In NIPS. find
  53. Peter D. Turney and Patrick Pantel. 2010. From frequency to meaning : Vector space models of semantics. JAIR, 37(1):141–188.
  54. Peter D. Turney. 2001. Mining the web for synonyms: PMI-IR versus LSA on TOEFL. In Proc. of ECML. find
  55. Eva Maria Vecchi, Roberto Zamparelli, and Marco Baroni. 2013. Studying the recursive behaviour of adjectival modification with compositional distributional semantics. In Proc. of EMNLP. find
  56. Lin Xiao. 2009. Dual averaging methods for regularized stochastic learning and online optimization. In NIPS. find
  57. Chang Xu, Yalong Bai, Jiang Bian, Bin Gao, Gang Wang, Xiaoguang Liu, and Tie-Yan Liu. 2014. Rc-net: A general framework for incorporating knowledge into word representations. In Proc. of CIKM. find
  58. Dani Yogatama and Noah A Smith. 2014. Linguistic structured sparsity in text categorization. In Proc. of ACL. find
  59. Mo Yu and Mark Dredze. 2014. Improving lexical embeddings with semantic knowledge. In Proc. of ACL.
  60. Jun Zhu and Eric P Xing. 2012. Sparse topical coding. arXiv:1202.3778. — [arXiv:1202.3778](https://arxiv.org/abs/1202.3778) find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/faruqui-2015-sparse-overcomplete-word-vector-representations/