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. Much attention has been paid to using LSTMs BID15 and similar models to compute text embeddings BID3 BID7 . Once trained, the LSTM can sweep once or twice through a given piece of text, process it using only limited memory, and output a vector with moderate dimensionality (a few hundred to a few thousand), which can be used to measure text similarity via cosine similarity or as a featurization for downstream tasks.The powers and limitations of this method have not been formally established. For example, can such neural embeddings compete with and replace traditional linear classifiers trained on trivial Bag-of-n-Grams (BonG) representations? Tweaked versions of BonG classifiers are known to be a surprisingly powerful baseline (Wang & Manning, 2012) and have fast implementations BID17 . They continue to give better performance on many downstream supervised tasks such as IMDB sentiment classification BID21 than purely unsupervised LSTM representations BID19 BID13 BID25 . Even a very successful character-level (and thus computation-intensive, taking a month of training) approach does not reach BonG performance on datasets larger than IMDB BID31 . Meanwhile there is evidence suggesting that simpler linear schemes give compact representations that provide most of the benefits of word-level LSTM embeddings (Wieting et al., 2016; BID1 . These linear schemes consist of simply adding up, with a few modifications, standard pretrained word embeddings such as GloVe or word2vec BID24 BID29 .The current paper ties these disparate threads together by giving an information-theoretic account of linear text embeddings. We describe linear schemes that preserve n-gram information as lowdimensional embeddings with provable guarantees for any text classification task. The previous linear schemes, which used unigram information, are subcases of our approach, but our best schemes can also capture n-gram information with low additional overhead. Furthermore , we show that the original unigram information can be (approximately) extracted from the low-dimensional embedding using sparse recovery/compressed sensing BID6 . Our approach also fits in the tradition of the older work on distributed representations of structured objects, especially the works of BID30 and BID18 . The following are the main results achieved by this new world-view:1. Using random vectors as word embeddings in our linear scheme (instead of pretrained vectors) already allows us to rigorously show that low-memory LSTMs are provably at least as good as every linear classifier operating on the full BonG vector. This is a novel theoretical result in deep learning, obtained relatively easily. By contrast, extensive empirical study of this issue has been inconclusive (apart from character-level models, and even then only on smaller datasets BID31 ). Note also that empirical work by its nature can only establish performance on some available datasets, not on all possible classification tasks. We prove this theorem in Section 4 by providing a nontrivial generalization of a result combining compressed sensing and learning BID5 ). In fact, before our work we do not know of any provable quantification of the power of any text embedding.2. We study theoretically and experimentally how our linear embedding scheme improves when it uses pretrained embeddings (GloVe etc.) instead of random vectors. Empirically we find that this improves the ability to preserve Bag-of-Words (BoW) information, which has the following restatement in the language of sparse recovery: word embeddings are better than random matrices for "sensing" BoW signals (see Section 5). We give some theoretical justification for this surprising finding using a new sparse recovery property characterizing when nonnegative signals can be reconstructed by 1 -minimization.3. Section 6 provides empirical results supporting the above theoretical work, reporting accuracy of our linear schemes on multiple standard classification tasks. Our embeddings are consistently competitive with recent results and perform much better than all previous linear methods. Among unsupervised word-level representations they achieve state of the art performance on both the binary and fine-grained SST sentiment classification tasks BID33 . Since our document representations are fast, compositional , and simple to implement given standard word embeddings, they provide strong baselines for future work. In this paper we explored the connection between compressed sensing, learning, and natural language representation. We first related LSTM and BonG methods via word embeddings, coming up with simple new document embeddings based on tensor product sketches. Then we studied their classification performance, proving a generalization of the compressed learning result of BID5 to convex Lipschitz losses and a bound on the loss of a low-dimensional LSTM classifier in terms of its (modified) BonG counterpart, an issue which neither experiments nor theory have been able to resolve. Finally, we showed how pretrained embeddings fit into this sparse recovery framework, demonstrating and explaining their ability to efficiently preserve natural language information. A COMPRESSED SENSING BACKGROUNDThe field of compressed sensing is concerned with recovering a high-dimensional k-sparse signal x ∈ R N from few linear measurements. In the noiseless case this is formulated as minimize w 0 subject to Aw = zwhere A ∈ R d×N is the design matrix and z = Ax is the measurement vector. Since 0 -minimization is NP-hard, a foundational approach is to use its convex surrogate, the 1 -norm, and characterize when the solution to (10) is equivalent to that of the following LP, known as basis pursuit (BP): DISPLAYFORM0 Related approaches such as Basis Pursuit Denoising (LASSO) and the Dantzig Selector generalize BP to handle signal or measurement noise BID11 ; however, the word embeddings case is noiseless so these methods reduce to BP. Note that throughout Section 5 and the Appendix we say that an 1 -minimization method recovers x from Ax if its optimal solution is unique and equivalent to the optimal solution of (10).An alternative way to approximately solve FORMULA1 is to use a greedy algorithm such as matching pursuit (MP) or orthogonal matching pursuit (OMP), which pick basis vectors one at a time by multiplying the measurement vector by A T and choosing the column with the largest inner product BID36 .
We use the theory of compressed sensing to prove that LSTMs can do at least as well on linear text classification as Bag-of-n-Grams.
{"src": "scitldr-AIC_train", "paper_id": "B1e5ef-C-"}