Title: A COMPRESSED SENSING VIEW OF UNSUPERVISED TEXT EMBEDDINGS, BAG-OF-n-GRAMS, AND LSTMS

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. * Vocabulary sizes (i.e. BonC dimensions) vary by task; usually 10K-100K. 1 Arora et al. ( 2017) Reported performance of best hyperparameter using Amazon GloVe embeddings. 2,4,7 Pagliardini et al. (

1. INTRODUCTION:

Much attention has been paid to using LSTMs (Hochreiter & Schmidhuber, 1997) and similar models to compute text embeddings (Bengio et al., 2003; Collobert & Weston, 2008) . 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 (Joulin et al., 2017) . They continue to give better performance on many downstream supervised tasks such as IMDB sentiment classification (Maas et al., 2011) than purely unsupervised LSTM representations (Kiros et al., 2015; Hill et al., 2016; Pagliardini et al., 2017) . 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 (Radford et al., 2017) . 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; Arora et al., 2017) . These linear schemes consist of simply adding up, with a few modifications, standard pretrained word embeddings such as GloVe or word2vec (Mikolov et al., 2013; Pennington et al., 2014) .

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 (Candès & Tao, 2005) . Our approach also fits in the tradition of the older work on distributed representations of structured objects, especially the works of Plate (1995) and Kanerva (2009) . 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 (Radford et al., 2017) ). 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 (Calderbank et al., 2009) . 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 (Socher et al., 2013) . Since our document representations are fast, compositional, and simple to implement given standard word embeddings, they provide strong baselines for future work.

Text Transducer Embedding:



2. RELATED WORK:

Neural text embeddings are instances of distributed representations, long studied in connectionist approaches because they decay gracefully with noise and allow distributed processing. Hinton (1990) provided an early problem formulation, and Plate (1995) provided an elementary solution, the holographic distributed representation, which represents structured objects using circular vector convolution and has an easy and more compact implementation using the fast Fourier transform (FFT). Plate suggested applying such ideas to text, where "structure" can be quantified using parse trees and other graph structures. Our method is also closely related in form and composition to the sparse distributed memory system of Kanerva (2009) . In the unigram case our embedding reduces to the familiar sum of word embeddings, which is known to be surprisingly powerful (Wieting et al., 2016) , and with a few modifications even more so (Arora et al., 2017) .

Representations of BonG vectors have been studied through the lens of compression by Paskov et al. (2013) , who computed representations based on classical lossless compression algorithms using a linear program (LP). Their embeddings are still high-dimensional (d > 100K) and quite complicated to implement. In contrast, linear projection schemes are simpler, more compact, and can leverage readily available word embeddings. Pagliardini et al. (2017) also used a linear scheme, representing documents as an average of learned word and bigram embeddings. However, the motivation and benefits of encoding BonGs in low-dimensions are not made explicit. The novelty in the current paper is the connection to compressed sensing, which is concerned with recovering high-dimensional sparse signals x ∈ R N from low-dimensional linear measurements Ax, specifically by studying conditions on matrix A ∈ R d×N when this is possible (see Appendix A for some background on compressed sensing and the previous work of Calderbank et al. (2009) that we build upon).

3. DOCUMENT EMBEDDINGS:

In this section we define the two types of representations that our analysis will relate:

1. high-dimensional BonG vectors counting the occurrences of each k-gram for k ≤ n 2. low-dimensional embeddings, from simple vector sums to novel n-gram-based embeddings Although some of these representations have been previously studied and used, we define them so as to make clear their connection via compressed sensing, i.e. that representations of the second type are simply linear measurements of the first.

We now define some notation. Let V be the number of words in the vocabulary and V n be the number of n-grams (independent of word order), so that

V = V 1 . Furthermore set V sum n = k≤n V k and V max n = max k≤n V k .

We will use words/n-grams and indices interchangeably, e.g. if (a, b) is the ith of V 2 bigrams then the one-hot vector e (a,b) will be 1 at index i. Where necessary we will use {, } to denote a multi-set and (, ) to denote a tuple. For any m vectors v i ∈ R d for i = 1, . . . , m we define [v 1 , . . . , v m ] to be their concatenation, which is thus an element of R md . Finally, for any subset X ⊂ R N we denote by ∆X the set {x -x : x, x ∈ X }.

3.1. THE BAG-OF-n-GRAMS VECTOR:

Assigning to each word a unique index i ∈ [V ] we define the Bag-of-Words (BoW) representation x BoW of a document to be the V -dimensional vector whose ith entry is the number of times word i occurs in the document. The n-gram extension of BoW is the Bag-of-n-Grams (BonG) representation, which counts the number of times any k-gram for k ≤ n appears in a document. Linear classification over such vectors has been found to be a strong baseline (Wang & Manning, 2012) .

For ease of analysis we simplify the BonG approach by merging all n-grams in the vocabulary that contain the same words but in a different order. We call these features n-cooccurrences and find that the modification does not affect performance significantly (see Table 3 in Appendix F.1). Formally for a document w 1 , . . . , w T we define the Bag-of-n-Cooccurrences (BonC) vector as the concatenation (1) which is thus a V sum n -dimensional vector. Note that for unigrams this is equivalent to the BoW vector.

3.2. LOW-DIMENSIONAL n-GRAM EMBEDDINGS:

Now suppose each word w has a vector v w ∈ R d for some d V . Then given a document w 1 , . . . , w T we define its unigram embedding as z u = T t=1 v wt . While this is a simple and widely used featurization, we focus on the following straightforward relation with BoW: if A ∈ R d×V is a matrix whose columns are word vectors v w then Ax BoW = T t=1 Ae wt = T t=1 v wt = z u . Thus in terms of compressed sensing the unigram embedding of a document is a d-dimensional linear measurement of its Bag-of-Words vector.

We could extend this unigram embedding to n-grams by first defining a representation for each ngram as the tensor product of the vectors of its constituent words. Thus for each bigram b = (w 1 , w 2 ) we would have v b = v w1 v T w2 and more generally v g = n t=1 v wt for each n-gram g = (w 1 , . . . , w n ). The document embedding would then be the sum of the tensor representations of all n-grams.

The major drawback of this approach is of course the blowup in dimension, which in practice prevents its use beyond n = 2. To combat this a low-dimensional sketch or projection of the tensor product can be used, such as the circular convolution operator of Plate (1995) . Since we are interested in representations that can also be constructed by an LSTM, we instead sketch this tensor product using the element-wise multiplication operation, which we find also usually works better than circular convolution in practice (see Table 4 in Appendix F.1). Thus for the n-cooccurrence g = {w 1 , . . . , w n }, we define the distributed cooccurrence (DisC) embedding ṽg = d n-1 2 n t=1 v wt . The coefficient is required when the vectors v w are random and unit norm to ensure that the product also has close to unit norm (see Lemma B.1). In addition to their convenient form, DisC embeddings have nice theoretical and practical properties: they preserve the original embedding dimension, they reduce to unigram (word) embeddings for n = 1, and under mild assumptions they satisfy useful compressed sensing properties with overwhelming probability (Lemma 4.1).

We then define the DisC document embedding to be the nd-dimensional weighted concatenation, over k ≤ n, of the sum of the DisC vectors of all k-grams in a document:

EQUATION

Here scaling factors C k are set so that all spans of d coordinates have roughly equal norm (for random embeddings C k = 1; for word embeddings C k = 1/k works well). Note that since ṽwt = v wt we have z (1) = z u in the unigram case. Furthermore, as with unigram embeddings by comparing (1) and

(2) one can easily construct a

n k=1 dn × V sum n matrix A (n) such that z (n) = A (n) x BonC .

3.3. LSTM REPRESENTATIONS:

As discussed previously, LSTMs have become a common way to apply the expressive power of RNNs, with success on a variety of classification, representation, and sequence-to-sequence tasks.

For document representation, starting with h 0 = 0 m an m-memory LSTM initialized with word vectors v w ∈ R d takes in words w 1 , . . . , w T one-by-one and computes the document representation

EQUATION

where h t ∈ R m is the hidden representation at time t, the forget gate f , input gate i, and input function g are a.e. differentiable nondecreasing elementwise "activation" functions R m → R m , and affine transformations T * (x, y) = W * x + U * y + b * have weight matrices W * ∈ R m×d , U * ∈ R m×m and bias vectors b * ∈ R m . The LSTM representation of a document is then the state at the last time step, i.e. z LSTM = h T . Note that we will follow the convention of using LSTM memory to refer to the dimensionality of the hidden states. Since the LSTM is initialized with an embedding for each word it requires O(m 2 + md + V d) computer memory, but the last term is just a lookup table so the vocabulary size does not factor into iteration or representation complexity.

From our description of LSTMs it is intuitive to see that one can initialize the gates and input functions so as to construct the DisC embeddings defined in the previous section. We state this formally and give the proof in the unigram case (the full proof appears in Appendix B.3): Proposition 3.1. Given word vectors v w ∈ R d , one can initialize an O(nd)-memory LSTM (3) that takes in words w 1 , . . . , w T (padded by an end-of-document token assigned vector 0 d ) and constructs the DisC embedding (2) (up to zero padding), i.e. such that for all documents z LSTM = z (n) . 1) .

Proof (Unigram Case). Set f (x) = i(x) = g(x) = x, T f (v wt , h t-1 ) = T i (v wt , h t-1 ) = 1 d , and T g (v wt , h t-1 ) = C 1 v wt . Then h t = h t-1 + C 1 v wt , so since h 0 = 0 d we have the final LSTM representation z LSTM = h T = C 1 t t=1 v wt = z (

By Proposition 3.1 we can construct a fixed LSTM that can compute compressed BonC representations on the fly and be further trained by stochastic gradient descent using the same memory.

4. LSTMS AS COMPRESSED LEARNERS:

Our main contribution is to provide the first rigorous analysis of the performance of the text embeddings that we are aware of, showing that the embeddings of Section 3.2 can provide performance on downstream classification tasks at least as well any linear classifier over BonCs. Before stating the theorem we make two mild simplifying assumptions on the BonC vectors:

1. The vectors are scaled by 1

T √

n , where T is the maximum document length. This assumption is made without loss of generality.

2. No n-cooccurrence contains a word more than once. While this is (infrequently) violated in practice, the problem can be circumvented by merging words as a preprocessing step. 

D ( ŵ) ≤ D (w 0 ) + O w 0 2 ε + 1 m log 1 δ (4)

The above theoretical bound shows that LSTMs match BonC performance as ε → 0, which can be realized by increasing the embedding dimension d (c.f. Figure 5 ).

4.1. COMPRESSED SENSING AND LEARNING:

Compressed sensing is concerned with recovering a high-dimensional k-sparse signal x ∈ R N from a few linear measurements; given a design matrix A ∈ R d×N this is formulated as

minimize w 0 subject to Aw = z (5)

where z = Ax is the measurement vector. As l 0 -minimization is NP-hard, research has focused on sufficient conditions for tractable recovery. One such condition is the Restricted Isometry Property (RIP), for which Candès & Tao (2005) proved that (5) can be solved by convex relaxation:

Definition 4.1. A ∈ R d×N is (X , ε)-RIP for some subset X ⊂ R N if ∀ x ∈ X (1 -ε) x 2 ≤ Ax 2 ≤ (1 + ε) x 2 (6)

We will abuse notation and say (k, ε)-RIP when X is the set of k-sparse vectors. This is the more common definition, but ours allows a more general Theorem 4.2 and a tighter bound in Theorem 4.1.

Following these breakthroughs, Calderbank et al. (2009) studied whether it is possible to use the low-dimensional output of compressed sensing as a surrogate representation for classification. They proved a learning-theoretic bound on the loss of an SVM classifier in the compressed domain compared to the best classifier in the original domain. In this work we are interested in comparing the performance of LSTMs with BonC representations, so we need to generalize the Calderbank et al. (2009) result to handle Lipschitz losses and an arbitrary set X ⊂ R N of high-dimensional signals:

Theorem 4.2. For any subset X ⊂ R N containing the origin let A ∈ R d×N be (∆X , ε)-RIP and let m samples S = {(x i , y i )} m i=1 ⊂ X × {-1, 1} be drawn i.i.d. from some distribution D over X with x 2 ≤ R. If is a λ-Lipschitz convex loss function and w 0 ∈ R N is its minimizer over D then w.p. 1 -2δ the linear classifier ŵA ∈ R d minimizing the 2 -regularized empirical loss function

S A (w) + 1 2C w 2 2 over the compressed sample S A = {(Ax i , y i )} m i=1 ⊂ R d × {-1, 1} satisfies D ( ŵA ) ≤ D (w 0 ) + O λR w 0 2 ε + 1 m log 1 δ (7) for appropriate choice of C. Recall that ∆X = {x -x : x, x ∈ X } for any X ⊂ R N .

While a detailed proof of this theorem is spelled out in Appendix C, the main idea is to compare the distributional loss incurred by a classifier ŵ in the original space to the loss incurred by A ŵ in the compressed space. We show that the minimizer of the regularized empirical loss in the original space ( ŵ) is a bounded-coefficient linear combination of samples in S, so its loss depends only on inner products between points in X . Thus using RIP and a generalization error result by Sridharan et al. (2008) we can bound the loss of ŵA , the regularized classifier in the compressed domain. Note that to get back from Theorem 4.2 the O( √ ε) bound for k-sparse inputs of Calderbank et al. (2009) we can set X to the be the set of k-sparse vectors and assume A is (2k, ε)-RIP.

4.2. PROOF OF MAIN RESULT:

To apply Theorem 4.2 we need the design matrix A (n) transforming BonCs into the DisC embeddings of Section 3.2 to satisfy the following RIP condition (Lemma 4.1), which we prove using a restricted isometry result for structured random sampling matrices in Appendix D: Lemma 4.1. Assume the setting of Theorem 4.1 and let A (n) be the nd × V sum n matrix relating DisC and BonC representations of any document by z

(n) = A (n) x BonC . If d = Ω T ε 2 log nV max n γ then A (n) is ∆X (n) T , ε -RIP w.p. 1 -γ, where X (n) T

is the set of BonCs of documents of length at most T .

Proof of Theorem 4.1.

Let Ŝ = {(A (n) x i , y i ) : (x i , y i ) ∈ S}, where A (n) is as in Lemma 4.1. Then by the same lemma A (n) is ∆X (n) T , ε -RIP w.p. 1 -γ, where X (n) T

is the set of BonC vectors of documents of length at most T . By BonC assumption (1) all BonCs lie within the unit ball, so we can apply Theorem 4.2 with the logistic loss, λ = 1, and R = 1 to get that a classifier ŵ trained using 2regularized logistic loss over Ŝ will satisfy the required bound (4). Since by Proposition 3.1 one can initialize an O(nd)-memory LSTM that takes in i.i.d. Rademacher word vectors

v w ∼ U d {±1/ √ d} such that z LSTM = z (n) = A (n) x ∀ x ∈ X (n)

T , this completes the proof.

5. SPARSE RECOVERY WITH PRETRAINED EMBEDDINGS:

Theorem 4.1 is proved using random vectors as the word embeddings in the scheme of Section 3. However, in practice LSTMs are often initialized with standard word vectors such as GloVe. Such embeddings cannot satisfy traditional compressed sensing properties such as RIP or incoherence. This follows essentially from the definition: word embeddings seek to capture word similarity, so similar words (e.g. synonyms) have embeddings with high inner product, which violates both properties. Thus the efficacy of real-life LSTMs must have some other explanation. But in this section we present the surprising empirical finding that pretrained word embeddings are more efficient than random vectors at encoding and recovering BoW information via compressed sensing. We further sketch a potential explanation for this result, though a rigorous explanation is left for subsequent work.

5.1. PRETRAINED EMBEDDINGS PRESERVE SPARSE INFORMATION:

In recent years word embeddings have been discovered to have many remarkable properties, most famously the ability to solve analogies (Mikolov et al., 2013) . Our connection to compressed sensing indicates that they should have another: preservation of sparse signals as low-dimensional linear measurements. To examine this we subsample documents from the SST (Socher et al., 2013) and IMDB (Maas et al., 2011) classification datasets, embed them as d-dimensional unigram embeddings z = Ax for d = 50, 100, 200, . . . , 1600 (where A ∈ R d×V is the matrix of word embeddings and x is a document's BoW vector), solve the following LP, known as Basis Pursuit (BP), which is the standard 1 -minimization problem for sparse recovery in the noiseless case (see Appendix A):

minimize w 1 subject to Aw = z (8)

Success is measured as the F 1 score of retrieved words. We use Squared Norm (SN) vectors (Arora et al., 2016) trained on a corpus of Amazon reviews (McAuley et al., 2015) and normalized i.i.d. Rademacher vectors as a baseline. SN is used due to similarity to GloVe and its formulation via an easy-to-analyze generative model that may provide a framework to understand the results (see Appendix F.2), while the Amazon corpus is used for its semantic closeness to the sentiment datasets. Figures 1 and 2 show that pretrained embeddings require a lower dimension d than random vectors to recover natural language BoW. This is surprising as the training objective goes against standard conditions such as approximate isometry and incoherence; indeed as shown in Figure 2 recovery is poor for randomly generated word collections. The latter outcome indicates that the fact that a document is a set of mutually meaningful words is important for sparse recovery using embeddings trained on co-occurrences. We achieve similar results with other objectives (e.g. GloVe/word2vec) and other corpora (see Appendix F.1), although there is some sensitivity to the sparse recovery method, as other 1 -minimization methods work well but greedy methods, such as Orthogonal Matching Pursuit (OMP), work poorly, likely due to their dependence on incoherence (Tropp, 2004) .

For the n-gram case (i.e. BonC recovery for n > 1), although we know by Lemma 4.1 that DisC embeddings composed from random vectors satisfy RIP, for pretrained vectors it is unclear how to reason about suitable n-gram embeddings without a rigorous understanding of the unigram case, and experiments do not show the same recovery benefits. One could perhaps do well by training on cooccurrences of word tuples, but such embeddings could not be used by a word-level LSTM.

5.2. UNDERSTANDING SPARSE RECOVERY OF NATURAL LANGUAGE DOCUMENTS:

As shown in Figure 2 , the success of pretrained embeddings for linear sensing is a local phenomenon; recovery is only efficient for naturally occurring collections of words. However, applying statistical RIP/incoherence ideas (Barg et al., 2015) to explain this is ruled out since they require collections to be incoherent with high probability, whereas word embeddings are trained to give high inner product to words appearing together. Thus an explanation must come from some other, weaker condition. The following geometric result then characterizes when solutions of BP+ recover the correct signal: Theorem 5.1 (Donoho & Tanner, 2005) . Consider a matrix A ∈ R d×N and an index subset S ⊂ [N ] of size k. Then any nonnegative vector x ∈ R N + with support supp(x) = S is recovered from Ax by BP+ iff the set A S of columns of A indexed by S comprise the vertices of a k-dimensional face of the convex hull conv(A) of the columns of A together with the origin. This theorem equates perfect recovery of a BoW vector via BP+ with the vectors of its words being the vertices of some face of the polytope conv(A). The property holds for incoherent columns since the vectors are far enough that no one vector is inside the simplex formed by any k others. On the other hand, pretrained embeddings satisfy it by having commonly co-occurring words close together and other words far away, making it easier to form a face from columns indexed by the support of a BoW. We formalize this intuition as the Supporting Hyperplane Property (SHP): SHP is a very weak property implied by NSP (Corollary E.1). However, it can be checked by using convex optimization to see if the hyperplane exists (Appendix E.2). Furthermore, we show (full proof in Appendix E.1) that this hyperplane is the supporting hyperplane of the face of conv(A) with vertices A S , from which it follows by Theorem 5.1 that SHP characterizes recovery using BP+: Corollary 5.1. BP+ recovers any x ∈ R N + with supp(x) = S from Ax iff A satisfies S-SHP.

Proof Sketch. By Theorem 5.1 it suffices to show equivalence of S-SHP with the column set A S comprising the vertices of a k-dimensional face of conv(A). A face F of polytope P is defined as its intersection with some hyperplane such that all points in P \F lie on one side of the hyperplane.

( =⇒ ) Let F be the face of conv(A) formed by the columns A S . Then there must be a supporting hyperplane H containing F . Since the columns of A are in general position, all columns A S = A\A S lie in conv(A)\F and hence must all be on one side of H, so H is the desired hyperplane.

( ⇐= ) Let H be the hyperplane supporting A S , with all other columns on one side of H. By convexity, H contains the simplex F of A S . Any point in conv(A)\F can be written as a convex combination of points in F and columns A S , with a positive coefficient on at least one of the columns, and so must lie on the same side of H as A S . Thus A S comprises the vertices of a face F .

Thus perfect recovery of a BoW via BP+ is equivalent to the existence of a hyperplane separating embeddings of words in the document from those of the rest of the vocabulary. Intuitively, words in the same document are trained to have similar embeddings and so will be easier to separate out, providing some justification for why pretrained vectors are better for sensing. We verify that SHP is indeed more likely to be satisfied by such designs in Figure 3 , which also serves as an empirical check of Corollary 5.1 since SHP satisfaction implies BP recovery as the latter can do no better than BP+. We further compare to recovery using OMP/OMP+ (the latter removes negative values and recomputes the set of atoms at each iteration); interestingly, while OMP+ recovers the correct signal from SN almost as often as BP/BP+, it performs quite poorly for GloVe, indicating that these embeddings may have quite different sensing properties despite similar training objectives.

As similarity properties that may explain these results also relate to downstream task performance, we conjecture a relationship between embeddings, recovery, and classification that may be understood under a generative model (see Appendix F.2). However, the Section 4 bounds depend on RIP, not recovery, so these experiments by themselves do not apply. They do show that the compressed sensing framework remains relevant even in the case of non-random, pretrained word embeddings. 

6. EMPIRICAL FINDINGS:

Our theoretical results show that simple tensor product sketch-based n-gram embeddings can approach BonG performance and be computed by a low-memory LSTM. In this section we compare these text representations and others on several standard tasks, verifying that DisC performance approaches that of BonCs as dimensionality increases and establishing several baselines for text classification. Code to reproduce results is provided at https://github.com/NLPrinceton/text_embedding.

Tasks: We test classification on MR movie reviews (Pang & Lee, 2005) , CR customer reviews (Hu & Liu, 2004) , SUBJ subjectivity dataset (Pang & Lee, 2004) , MPQA opinion polarity subtask (Wiebe et al., 2005) , TREC question classification (Li & Roth, 2002) , SST sentiment classification (binary and fine-grained) (Socher et al., 2013) , and IMDB movie reviews (Maas et al., 2011) . The first four are evaluated using 10-fold cross-validation, while the others have train-test splits. In all cases we use logistic regression with 2 -regularization determined by cross-validation. We further test DisC on the SICK relatedness and entailment tasks (Marelli et al., 2014) and the MRPC paraphrase detection task (Dolan & Brockett, 2005) . The inputs here are sentences pairs (a, b) and the standard featurization for document embeddings x a and x b of a and b is et al., 2015) . We use logistic regression for SICK entailment and MRPC and use ridge regression to predict similarity scores for SICK relatedness, with 2 -regularization determined by cross-validation. Since BonGs are not used for pairwise tasks our theory says nothing about performance here; we include these evaluations to show that our representations are also useful for other tasks.

[|x a -x b |, x a x b ] (Tai

Embeddings: In the main evaluation (Table 1 ) we use normalized 1600-dimensional GloVe embeddings (Pennington et al., 2014) trained on the Amazon Product Corpus (McAuley et al., 2015) , which are released at http://nlp.cs.princeton.edu/DisC. We also compare the SN vectors of Section 5 trained on the same corpus with random vectors when varying the dimension (Figure 5 ). Results: We find that DisC representation performs consistently well relative to recent unsupervised methods; among word-level approaches it is the top performer on the SST tasks and competes on many others with skip-thoughts and CNN-LSTM, both concatenations of two LSTM representations. While success may be explained by training on a large and in-domain corpus, being able to use so much text without extravagant computing resources is one of the advantages of a simple approach. Overall our method is useful as a strong baseline, often beating BonCs and many more complicated approaches while taking much less time to represent and train on documents than neural representations (Figure 4 ).

Finally, we analyze empirically how well our model approximates BonC performance. As predicted by Theorem 4.1, the performance of random embeddings on IMDB approaches that of BonC as dimension increases and the isometry distortion ε decreases (Figure 5 ). Using pretrained (SN) vectors, DisC embeddings approach BonC performance much earlier, surpassing it in the unigram case.

7. CONCLUSION:

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 Calderbank et al. (2009) 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 BACKGROUND

The 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

EQUATION

where 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):

EQUATION

Related approaches such as Basis Pursuit Denoising (LASSO) and the Dantzig Selector generalize BP to handle signal or measurement noise (Foucart & Rauhut, 2013) ; 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 ( 10) 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 (Tropp, 2004) .

A.1 SOME COMMON SPARSE RECOVERY CONDITIONS:

One condition through which recovery can be guaranteed is the Restricted Isometry Property (RIP):

Definition A.1. A ∈ R d×N is (k, ε)-RIP if for all k-sparse x ∈ R N (1 -ε) x 2 ≤ Ax 2 ≤ (1 + ε) x 2

A line of work started by Candès & Tao (2005) used the RIP property to characterize matrices A such that (10) and ( 11) have the same minimizer for any k-sparse signal x; this occurs with overwhelming probability when

d = Ω k log N k and √ dA ij ∼ N (0, 1) ∀ i, j or √ dA ij ∼ U{-1, 1} ∀ i, j.

Since the ability to recover a signal x from a representation Ax implies information preservation, a natural next step is to consider learning after compression. Calderbank et al. (2009) show that for m i.i.d. k-sparse samples {(x i , y i )} m i=1 and a (2k, ε)-RIP matrix A, the hinge loss of a classifier trained on {(Ax i , y i )} m i=1 is bounded by that of the best linear classifier over the original samples. Theorem 4.2 provides a generalization of this result to any convex Lipschitz loss function.

RIP is a strong requirement, both because it is not necessary for perfect, stable recovery of k-sparse vectors using Õ(k) measurements and because in certain settings we are interested in using the above ideas to recover specific signals -those statistically likely to occur-rather than all k-sparse signals.

The usual necessary and sufficient condition to recover any vector x ∈ R N with index support set S ⊂ [N ] is the local nullspace property (NSP), which is implied by RIP: Definition A.2 (Foucart & Rauhut, 2013) . A matrix A ∈ R d×N satisfies NSP for a set S ⊂ [N ] if w S 1 < w S 1 for all nonzero w ∈ ker(A) = {v : Av = 0 d }.

Theorem A.1 (Foucart & Rauhut, 2013) . BP (11) recovers any x ∈ R N + with supp(x) = S from Ax iff A satisfies NSP for S.

Model:

Representation In this section we compare the performance of several alternative representations with the ones presented in the main evaluation (Table 1 ). Table 3 provides a numerical justification for our use of unordered n-grams (cooccurrences) instead of n-grams, as the performance of the two featurizations are closely comparable. In Table 4 we examine the use of circular convolution instead of elementwise multiplication as linear measurements of BonC vectors Plate (1995) . To construct the former from a document w 1 , . . . , w T we compute

EQUATION

)

where F is the discrete Fourier transform and F -1 its inverse. Note that for n = 1 this is equivalent to the simple unigram embedding (and thus also to the DisC embedding in (2)). Proof.

E ṽg 2 2 = d i=1 E d n-1 2 n k=1 v w k i 2 = d n-1 d i=1 E n k=1 v 2 w k i = d n-1 d i=1 n i=1 1 d = 1 B.3 PROOF OF PROPOSITION 3.1 Let f (x) = i(x) = g(x) = x with T f (v wt , h t-1 ) = 1 nd 0 (n-1)d T i (v wt , h t-1 ) =          0 d×nd • • • 0 d×d . . . I (n-2)d 0 (n-2)d×d . . . . . . I d . . . . . . 0 d×d 0 (n-2)d×nd I (n-2)d 0 (n-2)d×d          h t-1 +    1 d 0 (n-1)d 1 d 0 (n-2)d    T g (v wt , h t-1 ) =          C 1 I d . . . C n d n-1 2 I d I d . . . I d          v wt

Substituting these parameters into the LSTM update (3) and using h 0 = 0 we have ∀ t > 0 that

h t =               C 1 t τ =1 v wτ . . . C n d n-1 2 t-n+1 τ =1 n k=1 v w τ +k-1 v wt . . . n-1 k=1 v w t+k-n+1               =               C 1 t τ =1 ṽwτ . . . C n d n-1 2 t-n+1 τ =1 ṽ{wτ ,...,wτ+n-1} ṽwt . . . ṽ{wt-n+2,...,wt}               Thus h T =               C 1 T t=1 ṽwt . . . C n d n-1 2 T -n+1 t=1 ṽ{wt,...,wt+n-1} ṽw T . . . ṽ{w T -n+2 ,...,w T }               =     z(n) ṽw T . . . ṽ{w T -n+2 ,...,w T }    

Note that h t ∈ R (2n-1)d so as desired the LSTM has O(nd)-memory. Although h T contains (n-1)d more dimensions than z(n) , by padding the end of the document with an end-of-document token whose word vector is 0 d the entries in those dimensions will be set to zero by the update at the last step. Thus up to zero padding we will have z LSTM = h T = z(n) .

C PROOF OF THEOREM 4.2

Throughout this section we assume the setting described in Theorem 4.2. Furthermore for some positive constant C define the 2 -regularization of the loss function as

EQUATION

)

where |α i | ≤ λC m ∀ i. This result holds in the compressed domain as well.

Proof. If is an λ-Lipschitz function, its sub-gradient at every point is bounded by λ. So by convexity, the unique optimizer is given by taking first-order conditions:

0 = ∂ w L S (w) = w C + 1 m m i=1 ∂ w T xi (w T x i , y i )x i =⇒ ŵ = C m m i=1 -y i ∂ ŵT xi ( ŵT x i , y i )y i x i (15) Since is Lipschitz, |∂ w T xi (w T x i , y i )| ≤ λ.

Therefore the first-order optimal solution (15) of ŵ can be expressed as ( 14) for some α 1 , . . . , α m satisfying |α i | ≤ λC m ∀ i, which is the desired result.

Lemma C.2. x, x ∈ X =⇒ (1 + ε)x T x -2R 2 ε ≤ (Ax) T (Ax ) ≤ (1 -ε)x T x + 2R 2 ε Proof. Since A is (∆X , ε)-RIP we have (1 -ε) x -x 2 ≤ A(x -x ) 2 ≤ (1 + ε) x -x 2 .

Also since 0 N ∈ X , A is also (X , ε)-RIP and the result then follows by the same argument as in (Calderbank et al., 2009, Lemma 4.2-3) .

Corollary C.1. ŵ 2 2 ≤ λ 2 C 2 R 2 and ŵA 2 2 ≤ λ 2 C 2 (1 + ε) 2 R 2 .

Proof. The first bound follows by expanding ŵ 2 2 and using x 2 ≤ R; the second follows by expanding ŵA 2 2 , applying Lemma C.2 to bound inner product distortion, and using x 2 ≤ R. Lemma C.3. Let ŵ be the linear classifier minimizing L S . Then

L D (A ŵ) ≤ L D ( ŵ) + O(λ 2 CR 2 ε)

Proof. By Lemma C.1 we can re-express ŵ using Equation 14 and then apply the inequality from Lemma C.2 to get

(A ŵ) T (Ax) = m i=1 α i y i (Ax i ) T (Ax) ≤ i:αiyi≥0 α i y i (1 -ε)x T i x + 2R 2 ε + i:αiyi<0 α i y i (1 + ε)x T i x -2R 2 ε = ŵT x -ε m i=1 |α i y i |x T i x + 2R 2 ε m i=1 |α i y i | ≤ ŵT x + 3λCR 2 ε (A ŵ) T (Ax) = m i=1 α i y i (Ax i ) T (Ax) ≥ i:αiyi≥0 α i y i (1 + ε)x T i x -2R 2 ε + i:αiyi<0 α i y i (1 -ε)x T i x + 2R 2 ε = ŵT x + ε m i=1 |α i y i |x T i x -2R 2 ε m i=1 |α i y i | ≥ ŵT x -3λCR 2 ε for any x ∈ R N . Since is λ-Lipschitz taking expectations over D implies D (A ŵ) ≤ D ( ŵ) + 3λ 2 CR 2 ε (16)

Substituting Equation 14applying Lemma C.2 also yields

A ŵ 2 2 = m i=1 m j=1 α i α j y i y j (Ax i ) T (Ax j ) ≤ i,j:αiαj yiyj ≥0 α i α j y i y j (1 -ε)x T i x j + 2R 2 ε + i,j:αiαj yiyj <0 α i α j y i y j (1 + ε)x T i x j -2R 2 ε ≤ i,j α i α j y i y j x T i x j + i,j -|α i α j y i y j |εx T i x j + 2R 2 |α i α j y i y j |ε ≤ ŵ 2 2 + 3λ 2 C 2 R 2 ε which implies 1 2C A ŵ 2 2 ≤ 1 2C ŵ 2 2 + 3 2 λ 2 CR 2 ε (17)

Together the inequalities bounding the loss term ( 16) and the regularization term (17) imply the result.

Lemma C.4. Let ŵ be the linear classifier minimizing L S and let w * be the linear classifier minimizing L D . Then with probability 1 -γ

L D ( ŵ) ≤ L D (w * ) + O λ 2 CR 2 m log 1 γ

This result holds in the compressed domain as well.

Proof. By Corollary C.1 we have that ŵ is contained in a closed convex subset independent of S. Therefore since is λ-Lipschitz, L is 1 C -strongly convex, and x 2 ≤ O(R), we have by (Sridharan et al., 2008 Substituting the C that minimizes the r.h.s. of this inequality completes the proof.

E DETAILS OF THE SUPPORTING HYPERPLANE PROPERTY:

In Section 5.2, Definition 5.1 we introduced the Supporting Hyperplane Property (SHP), which by Corollary 5.1 characterizes when BP+ perfectly recovers a nonnegative signal. Together with Lemmas A.1 and A.2 this fact also shows that SHP is a weaker condition than the well-known nullspace property (NSP): Corollary E.1. If a matrix A ∈ R d×N with columns in general position satisfies NSP for some S ⊂ [N ] then it also satisfies S-SHP.

In this section we give the entire proof of Corollary 5.1 and describe how to verify SHP given a design matrix and a set of support indices.

E.1 PROOF OF COROLLARY 5.1

Recall that it suffices to show equivalence of A being S-SHP with the columns A S forming the vertices of a k-dimensional face of conv(A), where we can abuse notation to set A ∈ R d×(N +1) , with the extra column being the origin 0 d , so long as we constrain N + 1 ∈ S.

( =⇒ ): The of the forward direction appeared in full in the proof sketch Section 5.2). The constraint enforces the property that the hyperplane contains all support embeddings, while the optimal objective value is zero iff SHP is satisfied (this follows from the fact that scaling h does not affect the constraint so if the minimal objective is zero for any single ε > 0 it is zero for all ε > 0). The problem can be solved via using standard first or second-order equality-constrained convex optimization algorithms. We set ε = 1 and p = 3 (to get a C 2 objective) and adapt the second-order method from Boyd & Vandenberghe (2004, Chapter 10) . Our implementation can be found at https://github.com/NLPrinceton/sparse_recovery.

:



Figures and Tables:

Theorem 4.1. Let S = {(x i , y i )} m i=1 be drawn i.i.d. from a distribution D over BonC vectors of documents of length at most T satisfying assumptions 1 and 2 above and let w 0 be the linear classifier minimizing the logistic loss D . Then for dimension d = Ω T ε 2 log nV max n γ and appropriate choice of regularization coefficient one can initialize an O(nd)-memory LSTM over i.i.d. word embeddings v w ∼ U d {±1/ √ d} such that w.p. (1 -γ)(1 -2δ) the classifier ŵ minimizing the 2 -regularized logistic loss over its representations satisfies

Figure 1: Average F 1 -score of 200 recovered BoW vectors from SST (left) and IMDB (right) compared to dimension. Pretrained word embeddings (SN trained on Amazon reviews) need half the dimensionality of normalized Rademacher vectors to achieve near-perfect recovery. Note that IMDB documents are on average more than ten times longer than SST documents.

Figure 2: F 1 -score of 1000 recovered BoWs compared to number of unique words. Real documents (left) are drawn from the SST and IMDB corpora; random signals (right) are created by picking words at random. For d = 200, pretrained embeddings are better than Rademacher vectors as sensing vectors for natural language BoW but are worse for random sparse signals.

Figure 3: Proportion of 500 randomly sampled documents from SST (top) and IMDB (bottom) that are perfectly recovered from linear measurements.

estimated

Figure 4: Time needed to initialize model, construct document representations, and train a linear classifier on a 16-core compute node.

Figure 5: IMDB performance of unigram (left) and bigram (right) DisC embeddings compared to the original dimension.

Figure 6: IMDB performance compared to training sample size.

SCALING FACTOR FOR DISC EMBEDDINGS Lemma B.1. If word vectors v w ∈ R d are drawn i.i.d. from U d {±1/ √ d} then for any n-gram g = (w 1 , . . . , w n ) we have E ṽg 2 2 = 1. The same result holds true with the additional assumption that all words in g are distinct if the word vectors are i.i.d. d-dimensional spherical Gaussians.

, Theorem 1) that with probability 1 -γL D ( ŵ) -L D (w * ) ≤ 2 [L S ( ŵ) -L S (w * )] + + O λ 2 CR 2 m log 1 γThen since by definition ŵ minimizes L S (w) we have that L S ( ŵ) ≤ L S (w * ), which substituted into the previous equation completes the proof.Proof of Theorem 4.2. Applying Lemma C.4 in the compressed domain yieldsD ( ŵA ) ≤ D ( ŵA ) A minimizes L D . By definition of w * A , L D (w * A ) ≤ L D (A ŵ),so together with Lemma C.3 and the previous inequality we have D ( ŵA ) ≤ L D (A ŵ) + O We now apply Lemma C.4 in the sparse domain to get D ( ŵA ) ≤ L D (w * ) + O λ 2 CR 2 ε + 1 m log 1 γ where w * minimizes L D . By definition of w * , L D (w * ) ≤ L D (w 0 ) = D (w 0 ) + 1 2C w 0 2 2 , so by the previous inequality we have D ( ŵA ) ≤ D (w 0 )

⇐= ): A subset F ⊂ R d is a face of if for some hyperplane H = {v : a v -b = 0} we have F = conv(A) ∩ H and conv(A)\F ⊆ H -= {v : a T v -b < 0}, where H -is the negative halfspace of H. Define the simplex ∆ m = {λ ∈ [0, 1] m m i=1 λ i = 1}. Since A is S-SHP we have a hyperplane H = {v : a T v -b = 0} containing the columns A S such that A S ⊂ H -Thus a T A i -b = 0 ∀ i ∈ S and a T A i -b < 0 i / ∈ S. We also know that F = { i∈S λ i A i : λ ∈ ∆ |S| } ⊆ H by convexity of H. Since any point y ∈ conv(A)\F can be written as y = N +1 i=1 λ i A i for some λ ∈ ∆ N +1 such that ∃ j /∈ S such that λ j = 0, we have thata T y -b = i∈S λ i (a T A i -b) + j / ∈S λ j (a T A j -b) = j / ∈S λ j (a T A j -b) < 0This implies that conv(A)\F ⊆ H -and F = conv(A) ∩ H, so since the columns of A are in general position F is a k-dimensional face of conv(A) whose vertices are the columns A S .E.2 VERIFYING SHPRecall that a matrix R d×N satisfies S-SHP for S ⊂ [N ] if there is a hyperplane containing the set of all columns of A indexed by S and the set of all other columns together with the origin are on one side of it. Due to Corollary 5.1, checking S-SHP allows us to know whether all nonnegative signals with index support S will be recovered by BP+ without actually running the optimization on any one of them. The property can be checked by solving a convex problem of the form min

The usual necessary and sufficient requirement for recovering all signals with support S ⊂ [N ] is the local nullspace property (NSP), which stipulates that vectors in the kernel of A not have too much mass on S (see Definition A.2). While NSP and related properties such as restricted eigenvalue (see Definition A.3) are hard to check, we can impose some additional structure to formulate an intuitive, verifiable perfect recovery condition for our setting. Specifically, since our signals (BoW vectors) are nonnegative, we can improve upon solving BP (8) by instead solving nonnegative BP (BP+): minimize w 1 subject to Aw = z, w ≥ 0 d (9)

Table content: <table/>

Evaluation of DisC and recent unsupervised word-level approaches on standard classification tasks, with the character LSTM ofRadford et al. (2017) shown for comparison. The top three results for each dataset are bolded, the best is italicized, and the best word-level performance is underlined.

Table content: <table><tr><td colspan="2">Representation n</td><td>d  *</td><td>MR</td><td>CR</td><td colspan="6">SUBJ MPQA TREC SST (±1) SST IMDB</td></tr><tr><td/><td>1</td><td>V1</td><td colspan="2">77.1 77.0</td><td>91.0</td><td>85.1</td><td>86.8</td><td>80.7</td><td>36.8</td><td>88.3</td></tr><tr><td>BonC (1)</td><td>2 3</td><td>V sum 2 V sum 3</td><td colspan="2">77.8 78.1 77.8 78.3</td><td>91.8 91.4</td><td>85.8 85.6</td><td>90.0 89.8</td><td>80.9 80.1</td><td>39.0 42.3</td><td>90.0 89.8</td></tr><tr><td/><td>1</td><td>1600</td><td colspan="2">79.6 81.0</td><td>92.4</td><td>87.8</td><td>85.2</td><td>84.6</td><td>45.7</td><td>89.2</td></tr><tr><td>DisC (2)</td><td>2</td><td>3200</td><td colspan="2">80.1 81.5</td><td>92.6</td><td>87.9</td><td>89.6</td><td>85.5</td><td>46.4</td><td>89.4</td></tr><tr><td/><td>3</td><td>4800</td><td colspan="2">80.0 81.3</td><td>92.6</td><td>87.9</td><td>90.0</td><td>85.2</td><td>46.7</td><td>89.6</td></tr><tr><td>SIF 1</td><td>1</td><td>1600</td><td colspan="2">79.6 81.1</td><td>92.5</td><td>87.7</td><td>85.6</td><td>84.4</td><td>45.8</td><td>89.2</td></tr><tr><td>Sent2Vec 2</td><td>1</td><td>700</td><td colspan="2">76.2 78.7</td><td>91.2</td><td>87.2</td><td>85.8</td><td>80.2</td><td>31.0</td><td>85.5</td></tr><tr><td>Sent2Vec 2</td><td>2</td><td>700</td><td colspan="2">76.3 79.1</td><td>91.1</td><td>86.6</td><td>84.2</td><td>80.0</td><td>30.7</td><td>85.3</td></tr><tr><td>CFL 3</td><td colspan="2">5 100K+</td><td/><td/><td/><td/><td/><td/><td/><td>90.4</td></tr><tr><td colspan="2">Paragraph Vec. 4</td><td/><td colspan="2">74.8 78.1</td><td>90.5</td><td>74.2</td><td>91.8</td><td/><td/></tr><tr><td>skip-thoughts 4</td><td/><td>4800</td><td colspan="2">80.3 83.8</td><td>94.2</td><td>88.9</td><td>93.0</td><td>85.1</td><td>45.8</td></tr><tr><td>SDAE 5</td><td/><td>2400</td><td colspan="2">74.6 78.0</td><td>90.8</td><td>86.9</td><td>78.4</td><td/><td/></tr><tr><td>CNN-LSTM 6</td><td/><td>4800</td><td colspan="2">77.8 82.0</td><td>93.6</td><td>89.4</td><td>92.6</td><td/><td/></tr><tr><td>byte mLSTM 7</td><td/><td>4096</td><td colspan="2">86.8 90.6</td><td>94.7</td><td>88.8</td><td>90.4</td><td>91.7</td><td>54.6</td><td>92.2</td></tr></table>

Performance of DisC and other recent approaches on pairwise similarity and classification tasks. The top three results for each task are bolded and the best is underlined.

Table content: <table/>

Sida Wang and Christopher D. Manning. Baselines and bigrams: Simple, good sentiment and topic classification. In Proceedings of the 50th Annual Meeting of the ACL, 2012. Janyce Wiebe, Theresa Wilson, and Claire Cardie. Annotating expressions of opinions and emotions in language. Language Resources and Evaluation, 39:165-210, 2005. John Wieting, Mohit Bansal, Kevin Gimpel, and Karen Livescu. Towards universal paraphrastic sentence embeddings. In Proceedings of the International Conference on Learning Representations, 2016.

Table content: <table/>

The performance of an l 2 -regularized logit classifier over Bag-of-n-Grams (BonG) vectors is generally similar to that of Bag-of-n-Cooccurrences (BonC) vectors for n = 2, 3 (largest differences bolded). Evaluation settings are the same as in Section 6. Note that for unigrams the two representations are equivalent.

Table content: <table><tr><td/><td/><td>MR</td><td colspan="6">CR SUBJ MPQA TREC SST (±1) SST IMDB</td></tr><tr><td>Bigram</td><td>BonG BonC</td><td colspan="2">78.3 78.2 91.9 77.8 78.1 91.8</td><td>85.7 85.8</td><td>90.0 90.0</td><td>80.8 80.9</td><td>39.1 39.0</td><td>90.0 90.0</td></tr><tr><td>Trigram</td><td>BonG BonC</td><td colspan="2">77.9 78.3 91.5 77.8 78.3 91.4</td><td>85.6 85.6</td><td>89.2 89.8</td><td>80.2 80.1</td><td>39.1 42.3</td><td>90.2 89.8</td></tr><tr><td>Model</td><td colspan="2">Representation MR</td><td colspan="6">CR SUBJ MPQA TREC SST (±1) SST IMDB</td></tr><tr><td>Bigram</td><td>DisC (2) Conv. (13)</td><td colspan="2">80.1 81.5 92.6 79.8 81.4 92.6</td><td>87.9 87.9</td><td>89.6 89.4</td><td>85.5 84.3</td><td>46.4 45.5</td><td>89.4 89.5</td></tr><tr><td>Trigram</td><td>DisC (2) Conv. (13)</td><td colspan="2">80.0 81.3 92.6 79.7 81.6 92.8</td><td>87.9 87.9</td><td>90.0 89.8</td><td>85.2 84.2</td><td>46.7 45.8</td><td>89.6 89.5</td></tr></table>

Performance comparison of element-wise product (DisC) and circular convolution for encoding local cooccurrences (best result for each task is bolded). Evaluation settings are the same as in Section 6. Note that for unigrams the two representations are equivalent.

Table content: <table><tr><td>B DOCUMENT EMBEDDINGS</td></tr><tr><td>B.1 PERFORMANCE COMPARISON OF ALTERNATIVE REPRESENTATIONS</td></tr></table>

Peer review (iclr2018):
 My review reflects more from the compressive sensing perspective, instead that of deep learners. In general, I find many of the observations in this paper interesting. However, this paper is not strong enough as a theory paper; rather, the value lies perhaps in its fresh perspective. The paper studies text embeddings through the lens of compressive sensing theory. The authors proved that, for the proposed embedding scheme, certain LSTMs with random initialization are at least as good as the linear classifiers; the theorem is almost a direction application of the RIP of random Rademacher matrices. Several simplifying assumptions are introduced, which rendered the implication of the main theorem vague, but it can serve as a good start for the hardcore statistical learning-theoretical analysis to follow. The second contribution of the paper is the (empirical) observation that, in terms of sparse recovery of embedded words, the pretrained embeddings are better than random matrices, the latter being the main focus of compressive sensing theory. Partial explanations are provided, again using results in compressive sensing theory. In my personal opinion, the explanations are opaque and unsatisfactory. An alternative route is suggested in my detailed review. Finally, extensive experiments are conducted and they are in accordance with the theory. My most criticism regarding this paper is the narrow scope on compressive sensing, and this really undermines the potential contribution in Section 5. Specifically, the authors considered only Basis Pursuit estimators for sparse recovery, and they used the RIP of design matrices as the main tool to argue what is explainable by compressive sensing and what is not. This seems to be somewhat of a tunnel-visioning for me: There are a variety of estimators in sparse recovery problems, and there are much less restrictive conditions than RIP of the design matrices that guarantee perfect recovery. In particular, in Section 5, instead of invoking [Donoho&Tanner 2005], I believe that a more plausible approach is through [Chandrasekaran et al. 2012]. There, a simple deterministic condition (the null space property) for successful recovery is proved. It would be of direct interest to check whether such condition holds for a pretrained embedding (say GloVe) given some BoWs. Furthermore, it is proved in the same paper that Restricted Strong Convexity (RSC) alone is enough to guarantee successful recovery; RIP is not required at all. While, as the authors argued in Section 5.2, it is easy to see that pretrained embeddings can never possess RIP, they do not rule out the possibility of RSC. Exactly the same comments above apply to many other common estimators (lasso, Dantzig selector, etc.) in compressive sensing which might be more tolerant to noise. Several minor comments: 1. Please avoid the use of “information theory”, especially “classical information theory”, in the current context. These words should be reserved to studies of Channel Capacity/Source Coding `a la Shannon. I understand that in recent years people are expanding the realm of information theory, but as compressive sensing is a fascinating field that deserves its own name, there’s no need to mention information theory here. 2. In Theorem 4.1, please be specific about how the l2-regularization is chosen. 3. In Section 4.1, please briefly describe why you need to extend previous analysis to the Lipschitz case. I understood the necessity only through reading proofs. 4. Can the authors briefly comment on the two assumptions in Section 4, especially the second one (on n- cooccurrence)? Is this practical? 5. Page 1, there is a typo in the sentence preceding [Radfors et al., 2017]. 6. Page 2, first paragraph of related work, the sentence “Our method also closely related to ...” is incomplete. 7. Page 2, second paragraph of related work, “Pagliardini also introduceD a linear ...” 8. Page 9, conclusion, the beginning sentence of the second paragraph is erroneous. [1] Venkat Chandrasekaran, Benjamin Recht, Pablo A. Parrilo, Alan S. Willsky, “The Convex Geometry of Linear Inverse Problems”, Foundations of Computational Mathematics, 2012.