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.
- DisC (Distributed Cooccurrence): They introduce a simple linear embedding scheme that uses element-wise (Hadamard) products to "sketch" n-grams into low-dimensional vectors.
- 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).
- 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.
- 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.
- 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.
- 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