A Compressed Sensing View of Unsupervised Text Embeddings, Bag-of-n-Grams, and LSTMs

Sanjeev Arora, Mikhail Khodak, Nikunj Saunshi, Kiran VodrahalliICLR 2018 · OpenReview

In the world of Natural Language Processing (NLP), we often treat LSTMs and pre-trained word embeddings like GloVe or word2vec as "black boxes" that somehow distill the meaning of text into compact vectors. While they work brilliantly in practice, a rigorous theoretical explanation for why these low-dimensional representations are so effective has been elusive.

In this ICLR 2018 paper, Sanjeev Arora and his colleagues from Princeton and Columbia Universities provide a bridge between deep learning and Compressed Sensing (CS). They demonstrate that text embeddings aren't just arbitrary features—they are information-preserving "measurements" of the high-dimensional structure of language.

TL;DR

This paper proves that LSTMs and simple linear embedding schemes are theoretically as powerful as linear classifiers trained on full "Bag-of-n-Grams" (BonG) models. Surprisingly, it also reveals that pre-trained embeddings like GloVe are actually better at "sensing" and preserving text information than the random matrices typically used in compressed sensing theory.

What Problem Does This Paper Address?

For years, a tension existed in NLP: simple, high-dimensional baselines like Bag-of-n-Grams (BonG)—which simply count occurrences of words and phrases—often outperformed sophisticated, low-dimensional unsupervised LSTMs on classification tasks.

There was no formal proof that a low-dimensional vector (a few hundred dimensions) could actually capture all the relevant information contained in the massive, sparse BonG space (millions of dimensions). The authors set out to provide this missing theoretical link: can we prove that these compact embeddings preserve enough information to match the performance of the "gold standard" BonG models?

Methods

The authors approach the problem by treating the embedding process as a linear measurement in the style of Compressed Sensing.

  1. DisC (Distributed Cooccurrence): They introduce a simple linear embedding scheme that uses element-wise (Hadamard) products to "sketch" n-grams into low-dimensional vectors.
  2. The CS Framework: They model the document embedding $z$ as a product $Ax$, where $x$ is a sparse high-dimensional BonG vector and $A$ is a "sensing matrix" (the word embeddings).
  3. Theoretical Generalization: They extend a result from Calderbank et al. (2009) to prove that if the matrix $A$ satisfies the Restricted Isometry Property (RIP)—meaning it preserves the distances between sparse vectors—then a linear classifier trained on the compressed embeddings will perform nearly as well as one trained on the original high-dimensional data.
  4. The LSTM Connection: Crucially, they show that a standard LSTM can be initialized to exactly compute these DisC embeddings, effectively proving that LSTMs are "compressed learners."

Datasets

The authors evaluated their DisC embeddings against several state-of-the-art unsupervised models across a wide array of benchmarks:

  • Sentiment Analysis: SST (binary and fine-grained), IMDB, CR (customer reviews), and MR (movie reviews).
  • Classification: SUBJ (subjectivity), MPQA (opinion polarity), and TREC (question types).
  • Pairwise Tasks: SICK (sentence relatedness) and MRPC (paraphrase detection).
  • Pre-training Corpora: They used word embeddings trained on the Amazon Review Corpus, Google News (word2vec), and Common Crawl (GloVe).

Key Insights and Ideas

  • LSTMs as Sensors: The "aha moment" is that we can view the hidden state of an LSTM as a compressed version of the document's n-gram counts. This provides the first rigorous proof that low-memory LSTMs are provably at least as powerful as linear BonG classifiers.
  • The Surprising Efficiency of GloVe: In traditional compressed sensing, researchers use random Gaussian or Rademacher matrices. However, this paper finds that pre-trained word embeddings are significantly more efficient at recovering natural language than random matrices.
Recovery performance on real vs. random documents
  • The Supporting Hyperplane Property (SHP): Why are pre-trained vectors better? The authors suggest it's because word embeddings are trained to put similar words (which often co-occur in the same document) close together. This makes it easier for the "sensing" process to separate the words present in a document from the rest of the vocabulary.

Key Results

  • State-of-the-Art Performance: Among unsupervised word-level representations, DisC achieved state-of-the-art results on both binary and fine-grained SST sentiment tasks.
  • Dimensionality Efficiency: Pre-trained embeddings (like those trained on Amazon reviews) required only half the dimensionality of random vectors to achieve near-perfect recovery of Bag-of-Words information.
Pretrained vs Random Vectors for Document Recovery
  • Speed: Because DisC is a simple linear scheme, it is orders of magnitude faster to train and evaluate than neural models like the "byte mLSTM," while remaining competitive in accuracy.

Limitations and Future Work

  • The Gap Between Theory and Practice: The main proof for LSTMs relies on random word embeddings to satisfy the RIP condition. However, in practice, we use pre-trained embeddings. While the authors propose the "Supporting Hyperplane Property" to explain why pre-trained vectors work, a full, rigorous theory for this specific case is still a work in progress.
  • n-gram Recovery: While the paper shows that pre-trained embeddings are great for recovering unigrams (single words), the empirical benefits were less clear for higher-order n-grams (like trigrams).
  • Generative Modeling: The authors suggest that future work could involve a generative model of text to more deeply explain why natural language is so "compressible" using these specific embedding structures.

Summary updated

Abstract

Low-dimensional vector embeddings, computed using LSTMs or simpler techniques, are a popular approach for capturing the “meaning” of text and a form of unsupervised learning useful for downstream tasks. However, their power is not theoretically understood. The current paper derives formal understanding by looking at the subcase of linear embedding schemes. Using the theory of compressed sensing we show that representations combining the constituent word vectors are essentially information-preserving linear measurements of Bag-of-n-Grams (BonG) representations of text. This leads to a new theoretical result about LSTMs: low-dimensional embeddings derived from a low-memory LSTM are provably at least as powerful on classification tasks, up to small error, as a linear classifier over BonG vectors, a result that extensive empirical work has thus far been unable to show. Our experiments support these theoretical findings and establish strong, simple, and unsupervised baselines on standard benchmarks that in some cases are state of the art among word-level methods. We also show a surprising new property of embeddings such as GloVe and word2vec: they form a good sensing matrix for text that is more efficient than random matrices, the standard sparse recovery tool, which may explain why they lead to better representations in practice.
BibTeX
@inproceedings{arora2018compressed,
  author = {Sanjeev Arora and Mikhail Khodak and Nikunj Saunshi and Kiran Vodrahalli},
  title = {{A Compressed Sensing View of Unsupervised Text Embeddings, Bag-of-n-Grams, and LSTMs}},
  booktitle = {International Conference on Learning Representations},
  year = {2018},
  url = {https://openreview.net/forum?id=B1e5ef-C-},
}
Figure