Title: ANCHOR & TRANSFORM: LEARNING SPARSE REPRESENTATIONS OF DISCRETE OBJECTS

Abstract: Learning continuous representations of discrete objects such as text, users, and items lies at the heart of many applications including text and user modeling. Unfortunately, traditional methods that embed all objects do not scale to large vocabulary sizes and embedding dimensions. In this paper, we propose a general method, Anchor & Transform (ANT) that learns sparse representations of discrete objects by jointly learning a small set of anchor embeddings and a sparse transformation from anchor objects to all objects. ANT is scalable, flexible, end-to-end trainable, and allows the user to easily incorporate domain knowledge about object relationships (e.g. WordNet, co-occurrence, item clusters). ANT also recovers several task-specific baselines under certain structural assumptions on the anchors and transformation matrices. On text classification and language modeling benchmarks, ANT demonstrates stronger performance with fewer parameters as compared to existing vocabulary selection and embedding compression baselines.

1. INTRODUCTION:

Learning continuous representations of discrete objects such as text, users, and items lies at the heart of many applications including natural language processing, user modeling, and recommendation systems. The standard way to learn these continuous representations involves: 1) defining the vocabulary V = {e 1 , ..., e V } as the set of all objects, and 2) learning a V × d embedding matrix that defines a d dimensional continuous representation for each object. However, when V is large (e.g. million of words in language modeling or millions of users in user modeling), this embedding matrix does not scale elegantly and can constitute more than 90% of all trainable parameters in the model. As a result, there has been large interest in learning sparse representations of these discrete objects rather than the full embedding matrix for cheaper storage as well as faster training and inference.

In the following we outline the desiderata of methods to learn sparse representations of discrete objects: 1) General-purpose: Good representation learning methods should be as flexible, modular, and as general as possible to be easily adapted for various applications. 2) End-to-end trainable: It is advantageous to learn neural representations in an end-to-end manner to directly optimize for the task at hand (Liu et al., 2018) . Similarly, we would like to enforce sparsity in our representations via task-specific measures. 3) Domain knowledge: The user should be able to easily integrate domain knowledge about object relationships. Domain knowledge can include external sources such as WordNet (Miller, 1995) , ConceptNet (Liu & Singh, 2004) , and knowledge graphs (Pujara & Singh, 2018) for text modeling, as well as clusters of users and items for user modeling (Zhang et al., 2012) .

As a step towards the aforementioned desiderata, we propose a general method to learn sparse representations of discrete objects. Our approach, depicted in Figure 1 , consists of two steps: 1) ANCHOR: Learn embeddings of a small set of anchor objects that are representative of all objects ( §3.1). The user retains flexibility in defining these anchors and we show strong performance across a suite of initialization strategies including random, frequency, and clustering-based methods.

2) TRANSFORM: Learn a sparse transformation from anchors to all objects ( §3.2). Each of the non-anchors should be easily induced by some transformation from (a few) nearby anchors. Domain knowledge can be incorporated through transformations between related objects ( §3.3). The anchor embeddings and the sparse transformation are trained end-to-end for task specific learning.

We call the resulting method Anchor & Transform, or ANT for short. ANT is scalable, flexible, end-to-end trainable, and allows the user to easily incorporate domain knowledge about object relationships. We also show that ANT recovers several task-specific baselines under certain structural assumptions on the anchors and transformation matrices (Appendix D). In practice, ANT is easy / M i u g Q H a E q c t E F q q N b E B N R F G K n t E r e r O e r B f r f q Y t x a s f K a M / s D / A F Y Q J S Q < / l a t e x i t > (b) Transform < l a t e x i t s h a 1 _ b a s e 6 4 = " a C K P 7 v c Z N v 8 J s 1 6 V c P j W 1 v n 5 x Q w = " > A A A B / 3 i c b V A 9 S w N B E N 3 z M 8 a v U 8 H G Z j E I s Q l 3 K p g y Y G M Z I V + Q H G F v s 0 m W 7 O 4 d u 3 N i O F P 4 V 2 w s F L H 1 b 9 j 5 b 9 w k V 2 j i g 4 H H e z P M z A t j w Q 1 4 3 r e z s r q 2 v r G Z 2 8 p v 7 + z u 7 b s H h w 0 T J Z q y O o 1 E p F s h M U x w x e r A Q b B W r B m R o W D N c H Q z 9 Z v 3 T B s e q R q M Y x Z I M l C 8 z y k B K 3 X d 4 w 6 w B 9 A y L Y b n u K a J M v 1 I y 0 n X L X g l b w a 8 T P y M F F C G a t f 9 6 v Q i m k i m g A p i T N v 3 Y g h S o o F T w S b 5 T m J Y T O i I D F j b U k U k M 0 E 6 u 3 + C z 6 z S w 3 a x L Q V 4 p v 6 e S I k 0 Z i x D 2 y k J D M 2 i N x X / 8 9 o J 9 M t B y l W c A F N 0 v q i f C A w R n o a B e 1 w z C m J s C a G a 2 1 s x H R J N K N j I 8 j Y E f / H l Z d K 4 K P m X J e / u q l A p Z 3 H k 0 A k 6 R U X k o 2 t U Q b e o i u q I o k f 0 j F 7 R m / P k v D j v z s e 8 d c X J Z o 7 Q H z i f P / T G l g Y = < / l a t e x i t > Confidential + Proprietary "good" "the" pretrained space e.g. GloVe/co-occurrence to incorporate into existing models by replacing the EMBEDDING layers in PyTorch or TensorFlow with our newly designed ANTEMBEDDING layers. We demonstrate the effectiveness of ANT on text classification and language modeling tasks ( §4). ANT achieves better performance with fewer parameters as compared to existing vocabulary selection and embedding compression baselines. Code to replicate our experiments is publicly released at <anonymous>.

2. RELATED WORK:

Related work on learning sparse representations of discrete structures largely fall into three categories: General purpose matrix compression techniques have been used to reduce the embedding matrix E, such as low rank approximations (Acharya et al., 2018; Markovsky, 2011; Grachev et al., 2019) , quantizing (Han et al., 2016) , pruning (Wen et al., 2016; Dong et al., 2017; Anwar et al., 2015) , or hashing (Guo et al., 2017; Chen et al., 2015; Qi et al., 2017) . However, these methods do not allow the user to integrate domain knowledge about object relationships. Furthermore, their generality implies that they are complementary and can be combined with our proposed methods. Reducing representation size: These methods reduce the dimension d for different objects. For example, Chen et al. (2016a) divides the embedding into buckets which are assigned to objects in order of importance, Joglekar et al. ( 2019) learns d by solving a discrete optimization problem with reinforcement learning (RL), and Baevski & Auli (2018) gradually reduces dimensions for rarer words. These methods typically resort to RL or are difficult to tune with too many hyperparameters. Each object is also modeled independently without information sharing between objects. Task specific methods define sparse embeddings for specific applications. For example, learning representations for common words gives strong performance for language modeling (Luong et al., 2015; Chen et al., 2016b) , and performing dropout-based vocabulary selection retains performance on text classification (Chen et al., 2019) . Other methods aim to reconstruct pre-trained embeddings using codebook learning (Shu & Nakayama, 2018; Chen et al., 2018) or low rank tensors (Nam & Quoc, 2017; Sedov & Yang, 2018) . However, these methods are not general and end-to-end trainable, therefore preventing us from learning representations for general tasks. For example, methods that only model a subset of objects cannot be used for retrieval tasks because it would imply never retrieving the dropped objects. Rare objects might be highly relevant to a few users so it might not be ideal to completely ignore them, but rather use only a few parameters to model them. Similarly, subword (Bojanowski et al., 2016) and wordpiece (Wu et al., 2016) embeddings, while useful for text, do not generalize to general objects and applications such as item and query retrieval.

The concept of using anchors to succinctly represent a large set of points on a manifold or space has been around for a while Mallat (1999) ; Aharon et al. (2006) . However, to best of our knowledge, they are mostly limited to cases when a distance or similarity function or a proxy thereof like ranked lists are provided (Guo et al., 2017; Xu et al., 2011; Liang et al., 2018) . The use of anchors simultaneously with a downstream learning task has been limited to well understood convex objectives with continuous inputs like in sparse Gaussian Process Regression (Snelson & Ghahramani, 2006) , where the kernel acts as the distance function. It is not evident from literature how to apply these anchor tricks to arbitrary learning problem over discrete objects in a flexible manner, like in deep networks. Our main contribution is to demonstrate how these anchors and sparse transformations can be trained jointly with neural models as a general input embedding layer, and how we can obtain better sparse representations using domain knowledge, e.g. if some notion of similarity is provided.

3. ANCHOR & TRANSFORM:

We present a general purpose method that is end-to-end trainable and allows us to integrate domain knowledge about object relationships. We suppose we are presented with data X ∈ R n× V , y ∈ R n×c drawn from some joint distribution p(X, y) where the support of X is over a discrete set V = {e 1 , ..., e V }. n is the size of the training set, V is typically known as the vocabulary, and V the vocabulary size. The entries in X are one-hot realizations of the discrete random variable X while the entries in y can be either discrete (classification with c classes) or continuous (regression with c targets). The goal is to learn a d-dimensional continuous representation {e 1 , ..., e V } for each discrete object by learning an embedding matrix E ∈ R V ×d where row i is the representation e i of object i. Learning this representation allows us to embed the discrete data into H = XE and define a neural model f θ with parameters θ to predict ŷ given representations

H, i.e. ŷ = f θ (H) = f θ (XE).

Instead of learning the large embedding matrix E directly, ANT consists of two components: 1) ANCHOR: Learn embeddings A ∈ R A ×d of a small set of anchor objects A = {a 1 , ..., a A }, A << V that are representative of all discrete objects. One is free to use different methods (e.g. random, frequency, or clustering-based initialization strategies) to initialize/select anchors based on the task. 2) TRANSFORM: Learn a sparse transformation T from A to the full embeddings E. In other words, each of the non-anchor objects should be easily induced by some transformation from (a few) nearby anchor objects. To ensure sparsity, we want nnz(T) << V × d. Furthermore, domain knowledge can be incorporated by defining the structure of these transformations between related objects. A and T are trained end-to-end for task specific representation learning. After training, we only store A × d + nnz(T) << V × d entries that define the complete embedding, which is much fewer than the V × d embedding traditionally used. We depict the overall algorithm in Figure 1 . In the following subsections, we explain how these anchor embeddings ( §3.1) and sparse transformations ( §3.2) are learned, before describing how the user can incorporate domain knowledge into ANT ( §3.3).

3.1. ANCHOR: LEARNING THE ANCHOR EMBEDDINGS A:

In the ANCHOR step, we would like to find a small set of anchor objects A = {a 1 , ..., a A }, A << V that are representative of all discrete objects. We describe several methods to select these anchors1 . Frequency and TF-IDF: For tasks where frequency or TF-IDF (Ramos, 1999) are useful for prediction, the objects can simply be sorted by frequency or TF-IDF and the most common objects selected as the anchor points. While this might make sense for tasks such as language modeling (Luong et al., 2015; Chen et al., 2016b) , only choosing the most frequent objects might not cover the space of all objects. As a result, certain rare objects might not be well represented by the common anchors. Clustering initialization: To ensure that all objects are close to some anchor in the representation space, we use k-means++ initialization (Arthur & Vassilvitskii, 2007) . Given a predefined metric space S consisting of n points x 1 , ..., x n ∈ R d with some distance function d(), k-means++ initialization is a randomized algorithm that picks cluster centers to span the entire space. In practice, S is usually a feature space representative of the relationships between objects, such as the Glove (Pennington et al., 2014) or Word2vec (Mikolov et al., 2013) embedding space for words or a co-occurrence matrix (Haralick et al., 1973) for more general objects. Using C to denote the set of cluster centers (C = {} initially), the k-means++ initialization alternates between two steps: 1. D(x i ) = min c∈C d(x i , c), and 2. add x i to C with probability ∝ D 2 (x i ). This clustering initial- ization method can also be used to augment other strategies, such as initializing anchors using frequent objects followed by clustering iterations to complete the remaining anchors (Figure 2 ). Dynamic basis vectors: Randomly initialize A to a set of basis vectors. This simple yet powerful method captures the general case where we have less knowledge about the objects. The random basis A can be viewed as a low-rank representation of the full embedding space E. Mixture of anchors: In general, different initialization strategies may bring about different advantages. For example, using a mixture of random basis vectors has been shown to help model multisense embeddings (Athiwaratkun et al., 2018; Nguyen et al., 2017) . One can define a set of M anchor embeddings A 1 , ..., A M each initialized by different strategies and of possibly different sizes.

3.2. TRANSFORM: LEARNING THE SPARSE TRANSFORMATION T:

We now describe how to TRANSFORM the anchor embeddings A to the full embedding matrix E, while enforcing sparsity in how these transformations are parametrized.

Linear transformation: We begin with a simple linear transformation T ∈ R V × A that maps the anchor embeddings to the entire embedding matrix: E = TA. The final embedding e i for object i is given by a linear combination of anchor embeddings whose weights are given by t i (row i of T). End-to-end training objective: Given the embedding matrix E which has now been implicitly defined by A and T, we add a model with parameters θ on top of the embedding matrix (e.g. fully connected layers or RNN/CNN/Transformer for sequential data) and define a loss function L which is a function of A, T, and θ (and X, y). Our end-to-end training objective is therefore

EQUATION

which directly optimizes for A and T for task-specific representation learning.

Making T sparse: As it is, T is still high-dimensional with V × A parameters. To enforce sparsity, we add an 1 penalty on transformation T, which transforms our overall objective function into:

EQUATION

where λ is a regularization factor. T 1 denotes sum of absolute values (not matrix nuclear norm). Most deep learning frameworks, would directly use subgradient descent to solve equation 2, but unfortunately such an approach will not yield sparsity. Instead, we perform optimization by proximal gradient descent (Parikh & Boyd, 2014) to ensure exact zero entries in T:

EQUATION

EQUATION

)

where η is the learning rate, GRADIENT STEP is a gradient update rule (e.g. SGD (Lecun et al., 1998) , ADAM (Kingma & Ba, 2014)), and PROX ηλ is the soft-thresholding operator (Beck & Teboulle, 2009) with threshold ηλ. This results in a transformation with few non-zero entries. Embedding e i for object i is now defined by a sparse combination of anchor embeddings with weights given by t i .

Connections to sparse dictionary learning, sparse recovery, compressive sensing: In Appendix B, we outline connections between ANT and sparse dictionary learning (Awasthi & Vijayaraghavan, 2018) . By using results from sparse recovery (Candes & Tao, 2005; Candès, 2008) , we can show that 1 -regularization (equation 2) results in provably sparse entries in T.

"good"

pretrained space e.g. GloVe/co-occurrence Reducing redundancy in representations: We additionally employ two methods to reduce redundancy in our sparse representations. Firstly, we perform orthogonal regularization of dynamic basis vectors A by adding the loss term L(A) = ∑ i≠j a ⊺ i a j to the loss function in equation 2. This ensures that different basis vectors a i and a j are orthogonal instead of being linear combinations of one another which would lead to redundancies across different learnt entries in T. Secondly, we employ a non-negative constraint on T by passing it through a Relu activation: T = RELU(T), which ensures that positive and negative entries along the same row in T do not effectively cancel each other out. Nonlinear mixture of transformations: In §3.1 we proposed to learn multiple sets of anchor embeddings A 1 , ..., A M . To truly exhibit the advantage of multiple anchors, we need to transform and combine them in a nonlinear fashion, e.g. E = ∑ M m=1 softmax(T m )A m (softmax over the rows of T m , Figure 3 ). There is a connection between nonlinear mixture of transformations with the multi-head attention mechanism used in the Transformer (Vaswani et al., 2017) , where softmax(T m ) can be viewed as softmax-activated (sparse) attention weights and A m the values to attend over.

3.3. INCORPORATING DOMAIN KNOWLEDGE:

Another benefit of our approach is its generality in incorporating domain knowledge about object relationships. Suppose we are given some relationship graph G = (V, E) where each object is represented by a vertex v ∈ V and an edge (u, v) ∈ E exists between objects u and v if they are related. Real-world instantiations of such a graph include 1) WordNet (Miller, 1995) or ConceptNet (Liu & Singh, 2004) where an edge exists between two words if they are related through semantic relations (e.g. synonym, antonym, hypernym, hyponym), 2) word co-occurrence matrices (Haralick et al., 1973) where an edge exists between two words if they frequently co-occur, and 3) Movie Clustering datasets (Leskovec & Krevl, 2014) where edges exist between two movies if they belong in the same cluster. From the relevant relationship graphs, we extract positive pairs P = {(u, v) ∶ (u, v) ∈ E} (which is the set of all related object pairs) and the unrelated negative pairs

N = {(u, v) ∶ (u, v) ∉ E}.

We incorporate the domain information from positive and negative pairs as follows: Positive pairs: To incorporate a positive pair (u, v), we do not enforce sparsity on the entries in the transformation matrix T which correspond to row u and column v (and vice versa). This allows ANT to freely learn the transformation between related objects u and v without being penalized for sparsity. On the other hand, transformations between negative pairs will be sparsely penalized. In other words, we element-wise multiply T with a domain sparsity matrix S(G) where S(G) u,v = 0 for (u, v) ∈ P (entries not 1 -penalized) and S(G) u,v = 1 otherwise (entries are 1 -penalized).

EQUATION

Since we perform proximal GD this is equivalent to only soft-thresholding the regularized entries between unrelated objects, i.e. T = PROX ηλ (T ⊙ S(G)) + T ⊙ (1 -S(G)) (Kim & Xing, 2008) .

Negative pairs: To incorporate information about negative pairs, we add an additional constraint that unrelated pairs should not share entries in their linear combination coefficients of the anchor embeddings. In other words, we add the loss term L(T, N ) = ∑ (u,v)∈N t u ⊺ t v to the loss function in equation 2. where each inner sum discourages t u and t v from sharing similar entries.

Algorithm 1 Anchor & Transform algorithm for learning sparse representations of discrete objects.

Ensure: ANCHOR & TRANSFORM::

1: Anchor: initialize anchor objects A and their embeddings A 1 , ..., A M . 2: Transform: initialize linear transformations T 1 , ..., T M as sparse matrices.

3: Optionally + domain info: initialize domain sparsity matrix S(G) as a sparse matrix. 4: for (X, y) in each batch do 5:

Construct embedding matrix E = ∑ M m=1 softmax(T m )A m . 6:

Embed input data tokens X with embeddings E.

7::

Compute predictions ŷ = f θ (X, A, T).

8::

Compute loss L = L(f (X; A, T, θ), y) + L(A) + L(T, N ) (optionally + domain info).

9::

A, T, θ = GRADIENT STEP (∇L, η).

10:

T = RELU(PROX ηλ (T ⊙ S(G)) + T ⊙ (1 -S(G))

). 11: end for 12: return anchor embeddings A and sparse transformations nnz(T).

3.4. EFFICIENT TRAINING AND INFERENCE:

The overall algorithm is given in Algorithm 1. We take advantage of sparse matrices during training and inference. Specifically, T is implemented as a sparse matrix by only storing its non-zero entries and indices. From our experiments, we observe that nnz(T) << V × d which makes storage of T extremely efficient as compared to traditional approaches of computing and storing the entire V × d embedding matrix. We also provide some implementation tips to further speedup training in Appendix C and ways to incorporate ANT with existing speedup techniques like softmax sampling (Bengio & Senecal, 2008; Mikolov et al., 2013) or noise-contrastive estimation (Gutmann & Hyvrinen, 2010; Mnih & Teh, 2012) . After training, we only store A × d + nnz(T) << V × d entries that completely define the complete embedding matrix, thereby using fewer parameters than the traditional V × d embedding matrix. Furthermore, we emphasize that general purpose matrix compression techniques such as hashing (Qi et al., 2017) , pruning (Dong et al., 2017) , and quantizing (Han et al., 2016) are compatible with our method: the resulting matrices A and nnz(T) can be further compressed and stored.

3.5. GENERALITY OF ANT:

In Appendix D, we show that under certain structural assumptions on the anchors and transformation matrices, ANT reduces to several established task-specific methods for learning sparse representations: 1) Frequency (Luong et al., 2015; Chen et al., 2016b) , TF-IDF (Ramos, 1999) , Group Lasso (Wen et al., 2016) , and variational dropout (Chen et al., 2019) based vocabulary selection, 2) Low-rank factorization (Acharya et al., 2018; Grachev et al., 2019) , and 3) Compositional code learning (Shu & Nakayama, 2018; Chen et al., 2018) . Hence, ANT is general and unifies some of the work on sparse representation learning done independently in different areas.

4. EXPERIMENTS:

To evaluate the effectiveness of ANT in learning sparse representations of discrete objects, we evaluate performance on text classification and language modeling tasks.

4.1. TEXT CLASSIFICATION:

Setup: We follow the setting in Chen et al. (2019) with four datasets: AG-News ( V = 62K) (Zhang et al., 2015) , DBPedia ( V = 563K) (Lehmann et al., 2015) , Sogou-News ( V = 254K) (Zhang et al., 2015) , and Yelp-review ( V = 253K) (Zhang et al., 2015) . We use a CNN for classification (Kim, 2014) . ANT is used to replace the input embedding and domain knowledge is derived from WordNet and co-occurrence in the training set. We record test accuracy and number of parameters used in the embedding only (excluding CNN). For ANT, num params is computed as A × d + nnz(T). Baselines: In addition to the CNN, we compare to the following compression approaches. Vocabulary selection: 1) Frequency where only embeddings for most frequent words are learnt (Luong et al., 2015; Chen et al., 2016b) , 2) TF-IDF which only learns embeddings for words with high TF-IDF score (Ramos, 1999) , 3) GL (group lasso) which aims to find underlying sparse structures in the embedding matrix via row-wise 2 regularization (Park et al., 2016; Liu et al., 2015; Wen et al., 2016) , 4) VVD (variational vocabulary dropout) which performs variational dropout for vocabulary selection (Chen et al., 2019) , 5) SparseVD (sparse variational dropout) which performs variational Table 1 : Text classification results on AG-News. Domain knowledge is derived from WordNet and co-occurrence statistics. Our approach with different initializations and domain knowledge achieves within 0.5% accuracy with 40× fewer parameters, outperforming the published baselines. Init: initialization method, Acc: accuracy, # Emb: # (non-zero) embedding parameters.

Method:

A Init A Sparse T RELU(T) Domain Acc (%) # Emb (M) CNN (Zhang et al., 2015) 61, 673 All 91.6 15.87 Frequency (Chen et al., 2019) 5, 000 Frequency 91.0 1.28 TF-IDF (Chen et al., 2019) 5, 000 TF-IDF 91.0 1.28 GL (Chen et al., 2019) 4, 000 Group lasso 91.0 1.02 VVD (Chen et al., 2019) 3, 000 Var dropout 91.0 0.77 SparseVD (Chirkova et al., 2018) 5, 700 Mult weights 88.8 1.72 SparseVD-Voc (Chirkova et al., 2018) dropout on all parameters (Chirkova et al., 2018) , and 6) SparseVD-Voc which additionally uses multiplicative weights for vocabulary sparsification (Chirkova et al., 2018) . 7) We also compare to a Sparse Code model that learns a sparse code to reconstruct pretrained word representations (Chen et al., 2016b) . All CNN architectures are the same throughout these baselines, details in Appendix E.1.

Results on AG-News are presented in Table 1 and we provide results for other text classification datasets in Appendix F. We observe that passing T through a RELU function is important in reducing redundancy in the linear combination entries. Domain knowledge from WordNet and co-occurrence statistics also succeeded in reducing the total (non-zero) embedding parameters to 0.40M, a compression of 40× the baseline and outperforming the existing approaches. Using a mixture of anchors and transformations also achieves stronger performance than the baselines using 5 anchors per mixture, although the larger number of transformations leads to an increase in parameters.

4.2. LANGUAGE MODELING Setup::

We perform experiments on word-level Penn Treebank (PTB) ( V = 10K) (Marcus et al., 1993) and WikiText-103 ( V = 267K) (Merity et al., 2016) . We experiment with both vanilla LSTMs (Hochreiter & Schmidhuber, 1997) and AWD-LSTM (Merity et al., 2017) for language modeling. We use ANT to replace the input embedding and the output embedding is tied to the input. Domain knowledge is derived from both WordNet and co-occurrence statistics on the training set. We record the test perplexity and the number of (non-zero) embedding parameters.

Baselines: We compare to SparseVD and SparseVD-Voc, as well as low-rank (LR) and tensor-train (TT) model compression techniques (Grachev et al., 2019) . Since Grachev et al. ( 2019) train LSTM models with different embedding sizes (200 and 256), we experiment with both as well (details in Appendix E.2). Note that the application of variational vocabulary selection to language modeling with tied weights is non-trivial since one is unable to predict next words when words are dynamically dropped out. We also compare against methods that compress the trained embedding matrix as a postprocessing step before evaluating using the compressed embedding matrix: Post-SH (post-processing using sparse hashing) (Guo et al., 2017) and Post-SH+k-SVD (improving sparse representation using k-SVD) (Guo et al., 2017; Awasthi & Vijayaraghavan, 2018) which additionally uses k-SVD (Aharon et al., 2006) to solve for a sparse representation of the embedding matrix, instead of adhoc-projection in Guo et al. (2017, eq 8-9 ). Comparing to these post-processing methods will demonstrate that end-to-end joint training of sparse embedding matrices is beneficial over post-processing compression.

We also note that while these post-processing methods reduce the number of (non-zero) parameters required for storage and evaluation, the full embedding matrix still needs to be learned during training.

Results: On PTB (Table 2 ), we improve the perplexity and compression as compared to both previously proposed methods that use variational dropout and matrix compression techniques. We observe that sparsity is important: baseline methods that only perform lower-rank compression with dense factors (e.g. LR LSTM) tend to suffer in performance while using many parameters, while ANT retains performance with much better compression. ANT also outperforms post-processing methods (Post-SH and Post-SH+k-SVD), we hypothesize this is because these post-processing accumulate errors in both language modeling as well as embedding reconstruction. Using an anchor size of 500 1000 reaches a good perplexity/compression trade-off: we reach within 2 points perplexity with 5× reduction in parameters and within 7 points perplexity with 10× reduction. Using AWD-LSTM, ANT with 1, 000 dynamic basis vectors is able to compress parameters by 10× while achieving 72.0 perplexity. Incorporating domain knowledge allows us to further compress the parameters by another 10× and achieve 70.0 perplexity, which results in 100× total compression. On WikiText-103, we train all approaches using sampled softmax (Bengio & Senecal, 2008) (as the vocabulary is relatively large) for 500, 000 steps. To best of our knowledge, we could not find existing literature on compressing language models on WikiText-1032 . We tried general compression techniques like low rank tensor and tensor train factorization (Grachev et al., 2019) , but these did not scale. As an alternative, we consider a Hash Embed baseline that retains the frequent k words and hashes the remaining words into 1, 000 OOV buckets (Svenstrup et al., 2017) . We vary k ∈ {1 × 10 5 , 5 × 10 4 , 1 × 10 4 }. The results in Table 3 show that we can reach within 3 points perplexity with ∼ 16× reduction in parameters and within 10 points perplexity with 100× reduction, outperforming the frequency and hashing baselines. We observe that the performance improvement of ANT over post-processing compression methods (Post-SH and Post-SH+k-SVD) is larger on WikiText-103 as compared to PTB, demonstrating that our end-to-end sparse embedding method is particularly suitable for tasks with large vocabularies.

Sparse transformations learned: We can visualize the important transformations (large entries) learned between anchors and non-anchors. Using anchors initialized by frequency and using domain knowledge from WordNet and co-occurrence, we show the learnt associations in Table 4 after training AWD-LSTM on PTB. On the left we show the most associated non-anchor words for a given anchor word such as year or stock and we find that the induced non-anchor words are highly plausible: stock accurately contributes to the representations for bonds, certificates, securities, and so on. On the right, we show the largest (non-anchor, anchor) pairs learned. Again, we find related concepts such as (when, how), (billion, trillion), and (government, administration) (more examples in Table 4 ). 

4.3. DISCUSSION:

Here we list some general observations regarding the importance of various design decision in ANT: 1) Sparsity is important: Baseline methods that only perform low-rank compression with dense factors (e.g. LR) tend to suffer in performance while using many parameters, while ANT with sparsity regularization retains performance with much better compression.

2) Proximal GD is essential: To achieve desired sparsity when training with mini-batches, the use of proximal GD was crucial. With default subgradient descent we did not observe sparsification of T.

3) Choice of A: Performance is robust wrt choice of A. We give a detailed discussion in Appendix A and provide results on clustering initializations. In general, while frequency and clustering work better, using a dynamic basis still performs well, especially when combined with domain knowledge. This implies that when the user has more information about the discrete objects (e.g. having a good representation space like GloVe to perform clustering), then the user should do so. However, for a new set of discrete objects, using random basis embeddings with sparsity also works well. 4) RELU: Passing T through RELU is important to reduce redundancy in each row entry. 5) Mixture: Using a mixture of anchors and transformations also achieves stronger performance than existing baselines, although the larger number of transformations increases the parameters. 6) Incorporating domain knowledge (DK): DK from WordNet and co-occurrence statistics help to further reduce the total (non-zero) embedding parameters while maintaining performance.

5. CONCLUSION:

This paper presented Anchor & Transform (ANT) to learn sparse representations of discrete objects by 1) learning a small set of anchor embeddings and 2) learning a sparse transformation from anchors to all objects. ANT is scalable, flexible, end-to-end trainable, and allows the user to easily incorporate domain knowledge about object relationships. On experiments spanning text classification and language modeling, ANT demonstrates strong performance with respect to accuracy and sparsity, outperforming existing compression approaches.

APPENDIX A LEARNING THE ANCHOR EMBEDDINGS A:

Here we provide several other strategies for initializing the anchor embeddings:

• Sparse lasso and variational dropout (Chen et al., 2019) . Given the strong performance of sparse lasso and variational dropout as vocabulary selection methods (Chen et al., 2019) , it would be interesting to use sparse lasso/variational dropout to first select the important task-specific words before jointly learning their representations and their transformations to other words. However, sparse lasso and variational dropout require first training a model to completion unlike frequency and clustering based vocabulary selection methods that can be performed during data preprocessing. • Coresets involve constructing a reduced data set which can be used as proxy for the full data set, with provable guarantees such that the same algorithm run on the coreset and the full data set gives approximately similar results (Phillips, 2016; Har-Peled & Mazumdar, 2018) .

Coresets can be approximately computed quickly (Bachem et al., 2017) and can be used to initialize the set of anchors A.

In general, there is a trade-off between how quickly we can choose the anchor objects and their performance. Randomly picking anchor objects (which is equivalent to initializing the anchor embeddings with dynamic basis vectors) becomes similar to learning a low-rank factorization of the embedding matrix (Nam & Quoc, 2017; Sedov & Yang, 2018) , which works well for general cases but can be improved for task-specific applications or with domain knowledge. Stronger vocabulary selection methods like variational dropout and group lasso would perform better but takes significantly longer time to learn. We found that intermediate methods such as frequency, clustering, with WordNet/cooccurrence information works well while ensuring that the preprocessing and training stages are relatively quick.

In Appendix F we provide more results for different initialization strategies including those based on clustering initializations. In general, performance is robust with respect to the choice of A among the ones considered (i.e. random, frequency, and clustering). While frequency and clustering work better, using a set of dynamic basis embeddings still gives strong performance, especially when combined with domain knowledge from WordNet and co-occurrence statistics. This implies that when the user has more information about the discrete objects (e.g. having a good representation space to perform clustering), then the user should do so. However, for a completely new set of discrete objects, simply using low-rank basis embeddings with sparsity also work well.

B CONNECTION TO SPARSE DICTIONARY LEARNING AND SPARSE RECOVERY:

Consider the modified subproblem where instead of jointly optimizing over both A and T, we assume that the anchor embeddings A * are given. In practice, this could imply that we first select an important subset of anchor words and then embed them with a pretrained representation space such as GloVe embeddings (Pennington et al., 2014) . Then, the problem is to learn a sparse transformation T from these pretrained anchor embeddings to the remaining embeddings (conceptually similar to recent work on reconstructing pretrained word embeddings using low rank tensors (Nam & Quoc, 2017; Sedov & Yang, 2018) or codebook learning (Shu & Nakayama, 2018; Chen et al., 2018) ).

Formally, the problem becomes

EQUATION

which is connected to the sparse dictionary learning problem (Awasthi & Vijayaraghavan, 2018) where we aim to learn an unknown dictionary A * and a sparse representation T that generated data E = TA * . As with existing results on recovering dictionaries in the over-complete setting, we assume that matrix A * satisfies the Restricted Isometry Property (RIP) condition: Definition 1. A matrix Φ satisfies the Restricted Isometry Property (RIP) with isometry constant δ k if for all k-sparse vectors x, we have

(1 -δ k ) x 2 2 ≤ Φx 2 2 ≤ (1 + δ k ) x 2 2 .

Suppose (i) A * T obeys the Restricted Isometry Property (RIP), (ii) the true transformation matrix T * is k-row sparse (each row of T * has at most k non-zero entries), and (iii) the true embedding E * was known, then recovering T * from A and E * is possible by using the 1 regularization (similar to equation 2).

Then, a classical result by Candes & Tao (2005) ; Candès (2008) states if y = Φx * for some k-sparse vector x * , then the solution to

min x x 0 subject to y = Φx (7)

is equivalent to the solution given by the 1 problem

min x x 1 subject to y = Φx (8) when δ 2k ≤ √ 2 -1.

In our setting, we aim to solve the constrained optimization problem

EQUATION

where each row in T may be minimized independently of the rest. Assuming that E * = T * A for some k-row sparse matrix T * , applying the result by Candes & Tao (2005) ; Candès (2008) to each row and exploiting the assumption that A * T is RIP gives

EQUATION

)

which is equivalent to 1 regularization in equation 2 when written in Lagrange form. Therefore, 1 -regularization (like equation 2) provably results in sparse entries in T.

C EFFICIENT LEARNING AND INFERENCE:

The naive method for learning E from anchor embeddings A and the sparse transformations T still scales linearly with V × d. Here we describe some tips on how to perform efficient learning and inference of the anchor embeddings A and the sparse transformations T:

• Store T as a sparse matrix by only storing its non-zero entries and indices. From our experiments, we have shown that nnz(T) << V × d which makes storage efficient. • For inference, use sparse matrix multiply as supported in TensorFlow and PyTorch to compute E = TA (or its non-linear extensions). This decreases the running time from scaling by V × d to only scaling as a function of nnz(T). For training, using inbuilt sparse representation of most deep learning frameworks like PyTorch or Tensorflow is not optimal, as they do not support changing non-zero locations in sparse matrix and apriori its not easy to find optimal set of non-zero locations. • During training, instead, implicitly construct E from its anchors and transformations. In fact, we can do better: instead of constructing the entire E matrix to embed a single datapoint x ∈ R 1× V , we can instead first index x into T, i.e. xT ∈ R 1× A before performing a sparse matrix multiplication with A, i.e. (xT)A ∈ R 1×d . We are essentially taking advantage of the associative property of matrix multiplication and the fact that xT is a simple indexing step and (xT)A is an effective sparse matrix multiplication. To enable fast row slicing into sparse matrix, we just storing the matrix in adjacency list or CSOO format. (We move away from CSR as adding/deleting a non-zero location is very expensive.) When gradient comes back, only update the corresponding row in T. The gradient will be sparse as well due to the L1-prox operator. • Above trick solves the problem for tasks where embedding is used only at the input, e.g. classification. For tasks like language model, where embedding is used at output as well one can also use above mentioned trick with speedup techniques like various softmax sampling techniques (Bengio & Senecal, 2008; Mikolov et al., 2013) or noise-contrastive estimation (Gutmann & Hyvrinen, 2010; Mnih & Teh, 2012) , which will be anyway used for large vocabulary sizes. To elaborate, consider the case of sampled softmax (Bengio & Senecal, 2008) . We normally generate the negative sample indices, and then we can first index into T using the true and negative indices before performing sparse matrix multiplication with A. This way we do not have to instantiate entire E by expensive matrix multiplication. • When training is completed, only store the non-zero entries of T or store T as a sparse matrix to reconstruct E for inference.

• To save time when initializing the anchor embeddings and incorporating domain knowledge, precompute the necessary statistics such as frequency statistics, co-occurrence statistics, and object relation statistics. We use a small context size of 10 to measure co-occurrence of two words to save time. When using WordNet to discover word relations, we only search for immediate relations between words instead of propagating relations across multiple steps (although this could further improve performance). • In order to incorporate domain knowledge in the sparsity structure, we again store 1 -S(G) using sparse matrices. Recall that S(G) has an entry equal to 1 for entries representing unrelated objects that should be 1 -penalized, which makes S(G) quite dense since most anchor and non-anchor objects are unrelated. Hence we store 1-S(G) instead which consists few non-zero entries only at (non-anchor, anchor) entries for related objects. Element-wise multiplications are also replaced by sparse element-wise multiplications when computing T ⊙ S(G) and T ⊙ (1 -S(G)). • Finally, even if we want to utilize our ANTframework with full softmax in language model, it is possible without blowing up memory requirements. In particular, let g ∈ R 1× V be the incoming gradient from cross-entropy loss and h ∈ R d×1 be the vector coming from layers below, like LSTM. The gradient update is then

EQUATION

The main issue is computing the huge V × A outer product as an intermediate step which will be dense. However, note that incoming gradient g is basically a softmax minus an offset corresponding to correct label. This should only have large values for a small set of words and small for others. If we carefully apply the L1-prox operator earlier, which is nothing but a soft-thresholding, we can make this incoming gradient sparse very sparse. Thus we need to only calculate a much smaller sized outer product and touch a small number of rows in T. Thus, making the approach feasible.

D GENERALITY OF ANT:

We show that under certain structural assumptions on the anchor embeddings and transformation matrices, ANT reduces to the following task-specific methods for learning sparse representations. This implies that ANT is indeed a general framework that unifies some of the work on sparse representation learning done independently in different research areas.

Frequency-based vocabulary selection (Luong et al., 2015; Chen et al., 2016b) : Initialize A with the A most frequent objects and set T a,a = 1 for all a ∈ A, T = 0 otherwise. Then E = TA consists of embeddings of the A most frequent objects with zero embeddings for all others. During training, gradients are used to update A but not T (i.e. only embeddings for frequent objects are learned). By changing the selection of A, ANT also reduces to other vocabulary selection methods such as TF-IDF (Ramos, 1999) , Group Lasso (Wen et al., 2016) , and variational dropout (Chen et al., 2019) Low-rank factorization (Acharya et al., 2018; Markovsky, 2011; Grachev et al., 2019) : Initialize A by a mixture of random basis embeddings (just 1 anchor per set) A 1 , ..., A M ∈ R 1×d and do not enforce any sparsity on the transformations T 1 , ..., T M ∈ R V ×1 . If we further restrict ourselves to only linear combinations E = ∑ M m=1 T m A m , this is equivalent to implicitly learning the M low rank factors a 1 , ..., a M , t 1 , ..., t M that reconstruct embedding matrices of rank at most M .

Compositional code learning (Shu & Nakayama, 2018; Chen et al., 2018) : Initialize A by a mixture of random basis embeddings A 1 , ..., A M , initialize transformations T 1 , ..., T M , and apply a linear combination E = ∑ M m=1 T m A m . For sparsity regularization, set row i of S(G) mi as a reverse one-hot vector with entry d mi = 0 and all else 1. In other words, index d mi of row row T mi is not regularized, and all other entries are 1 -regularized with extremely high λ such that row T mi essentially becomes an one-hot vector with dimension d mi = 1. This results in learning a codebook where each object in V is mapped to only one anchor in each mixture.

Therefore, ANT encompasses several popular methods for learning sparse representations, and gives further additional flexibility in defining various initialization strategies, applying nonlinear mixtures of transformations, and incorporating domain knowledge via object relationships. Base LSTM model: Our base model is a 2 layer LSTM with an embedding size of 200 and hidden layer size of 200. The code was adapted from https://github.com/salesforce/ awd-lstm-lm and the full table of hyperparameters is provided in Table 6 .

Base AWD-LSTM model: In addition to experiments on an vanilla LSTM model as presented in the main text, we also performed experiments using a 3 layer AWD-LSTM with an embedding size of 400 and hidden layer size of 1, 150. The full hyperparameters used can be found in Table 7 .

Anchor: We experiment with dynamic, frequency, and clustering initialization strategies. The number of anchors A is a hyperparameter that is selected using the validation set. The range of A is in {10, 20, 50, 80, 100, 500, 1, 000}. Smaller values of A allows us to control for fewer anchors and smaller transformation matrix T at the expense of performance. Domain knowledge: When incorporating domain knowledge in ANT, we use both WordNet and cooccurrence statistics. For WordNet, we use the public WordNet interface provided by NLTK http: //www.nltk.org/howto/wordnet.html. For each word we search for its immediate related words among its hypernyms, hyponyms, synonyms, and antonyms. This defines the relationship graph. For co-occurrence statistics, we define a co-occurrence context size of 10 on the training data. Two words are defined to be related if they co-occur within this context size.

A note on baselines: We also used some of the baseline results as presented in Grachev et al. (2019) . Their presented results differ from our computations in two aspects: they include the LSTM parameters on top of the embedding parameters, and they also count the embedding parameters twice since they do not perform weight tying (Press & Wolf, 2016) (see equation ( 6) of Grachev et al. ( 2019)). To account for this, the results of SparseVD and SparseVD-Voc (Chirkova et al., 2018) , as well as the results of various LR-and TR-low rank compression methods (Grachev et al., 2019) were modified by subtracting off the LSTM parameters (200 × 200 × 16) . This is derived since each of the 8 weight matrices W i,f,o,c , U i,f,o,c in an LSTM layer is of size 200 × 200, and there are a 2 LSTM layers. We then divide by two to account for weight tying. In the main text, we compared with the strongest baselines as reported in Grachev et al. ( 2019): these were the methods that performed low rank decomposition on both the input embedding ( V × d), output embedding (d × V ), and intermediate hidden layers of the model. For full results, please refer to Grachev et al. (2019) .

Note that the reported results on SparseVD and SparseVD-Voc (Chirkova et al., 2018) have a different embedding size and hidden layer size of 256 instead of 200, although these numbers are close enough In our experiments we additionally implemented an LSTM with an embedding size of 256 and hidden layer size of 256 so that we can directly compare with their reported numbers.

For baselines that perform post-processing compression of the embedding matrix, Post-SH (postprocessing using sparse hashing) (Guo et al., 2017) and Post-SH+k-SVD (improving sparse hashing using k-SVD) (Guo et al., 2017; Awasthi & Vijayaraghavan, 2018) , we choose two settings: the first using 500 anchors and 10 nearest neighbors to these anchor points, and the second using 1, 000 anchors and 20 nearest neighbors. The first model uses 500 × d + V × 10 non-zero embedding parameters while the second model uses 1, 000 × d + V × 20 parameters. For AWD-LSTM on PTB, this is equivalent to 0.3M and 0.6M embedding parameters respectively which is comparable to the number of non-zero parameters used by our method.

E.3 LANGUAGE MODELING ON WIKITEXT-103:

Base AWD-LSTM model: Our base model is a 4 layer AWD-LSTM with an embedding size of 400 and hidden layer size of 2, 500. The code was adapted from https://github.com/ salesforce/awd-lstm-lm and the hyperparameters used can be found in Table 8 .

A note on baselines: While Baevski & Auli (2018) adapt embedding dimensions according to word frequencies, their goal is not to compress embedding parameters and they use 44.9M (dense) parameters in their adaptive embedding layer, while we use only 2M. Their embedding parameters are calculated by their reported bucket sizes and embedding sizes (three bands of size 20K (d = 1024), 40K (d = 256) and 200K (d = 64)). Their perplexity results are also obtained using a Transformer model with 250M params while our AWD-LSTM model uses 130M params.

For the Hash Embed baseline that retains the frequent k words and hashes the remaining words into 1, 000 OOV buckets (Svenstrup et al., 2017) , We vary k ∈ {1 × 10 5 , 5 × 10 4 , 1 × 10 4 }.

F MORE RESULTS:

In the following sections we provide additional results on learning sparse representations of discrete objects using ANT.

F.1 TEXT CLASSIFICATION Results: We report additional text classification results on DBPedia, Sogou-News, and Yelp-review in Table 9 . Our approach with different initializations and domain knowledge achieves within 1% Table 9 : More text classification results on DBPedia (top), Sogou-News (middle), and Yelp-review (bottom). Domain knowledge is derived from WordNet and co-occurrence statistics. Our approach with different initializations and domain knowledge achieves within 1% accuracy with 21× fewer parameters on DBPedia, within 1% accuracy with 10× fewer parameters on Sogou-News, and within 2% accuracy with 22× fewer parameters on Yelp-review. Acc: accuracy, # Emb: # (non-zero) embedding parameters.

A Init A Sparse T RELU(T) Domain Acc (%) # Emb (M) CNN (Zhang et al., 2015) 563, 355 All 98.3 144.0 Sparse Code (Chen et al., 2016b) 

:

Please refer to Appendix A for more strategies and a comparison of various initialization strategies.

While Baevski & Auli (2018) adapt embedding dimensions according to word frequencies, their goal is not compression and use 44.9M (dense) parameters in their adaptive embedding layer, while we use as less as 0.4M (100x less). Also they obtained results using a Transformer with 250M params while AWD-LSTM uses 130M.

Figures and Tables:

t e x i t s h a _ b a s e = " K A p N e G q j R lV C c e Q T R q l H C f M = " > A A A B / H i c b V B N S N A E N U r q / o j W S x C v Z R E B T W v X i s Y D + g D W W z b R L N u w O x F D q H / F i w d F v P p D v P l v L Y a O u D g c d M z M P B N T j O t V Y W V b y h u l r a d b P D l o S R V m T R i J S H Z o J r h k T e A g W C d W j I S + Y G / f D P w M a R J e h j o V k K H n A K Q E j e y D g j q D C r k h N J e k o U p O + X X F q z g x m b g q a A c j b R t E N A m Z B C q I l X i c H L i A J O B Z u U e o l m M a F j M m R d Q y U J m f a y f E T f G y U A Q i Z U o C n q m / J z I S a p G v u k M C Y z o j c V / / O C Q S X X s Z l n A C T d L o S A S G C E + T w A O u G A W R G k K o u Z W T E d E E Q o m r I J w V e Z m T m v u W c O / U r

Figure 1: Anchor & Transform (ANT) is a general method to learn sparse representations of discrete objects consisting of two steps: 1) Anchor: Learn embeddings A of a small set of anchor objects A = {a 1 , ..., a A }, A << V that are representative of all discrete objects (e.g. frequency and clustering based initialization methods). 2) Transform: Learn a sparse transformation T from the anchor embeddings to the full embedding matrix E. A and T are trained end-to-end for task specific representation learning. ANT is scalable, flexible, end-to-end trainable, and allows the user to easily incorporate domain knowledge about object interactions.

Figure 2: Initialization strategies for anchor objects combining ideas from frequency and k-means++ clustering algorithms. Clustering initialization picks anchors to span the space of all objects.

Figure 3: Generalized nonlinear mixture of anchors A 1 , ..., A M and transformations T 1 , ..., T M , E = ∑ M m=1 softmax(T m )A m (softmax across rows of T m ). Different sparse transformations can be learned for different initializations of anchor embeddings.

Figure 4: Incorporating domain knowledge via given relationship graphs (left) and extracting positive and pairs (P) and negative pairs (N). Transformations between negative (unrelated) pairs are sparsely penalized while those between positive (related) pairs are not. The linear combination coefficients t u and t v of negative pairs are also discouraged from sharing similar entries.

Language modeling using LSTM (top) and AWD-LSTM (bottom) on PTB. We outperform vocab selection and compression baselines. 200 256 is embedding dimension. Incorporating domain knowledge further reduces params. Ppl: perplexity, # Emb: # (non-zero) embedding parameters.

Table content: <table><tr><td>Method</td><td/><td>A</td><td colspan="2">Init A</td><td>Sparse T RELU(T) Domain Ppl # Emb (M)</td></tr><tr><td>LSTM 200 (Grachev et al., 2019)</td><td colspan="2">10, 000</td><td>All</td><td/><td>77.1</td><td>2.00</td></tr><tr><td>LSTM 256 (Chirkova et al., 2018)</td><td colspan="2">10, 000</td><td>All</td><td/><td>70.3</td><td>2.56</td></tr><tr><td>LR 200 (Grachev et al., 2019)</td><td colspan="2">10, 000</td><td>All</td><td/><td>112.1</td><td>1.26</td></tr><tr><td>TT 200 (Grachev et al., 2019)</td><td colspan="2">10, 000</td><td>All</td><td/><td>116.6</td><td>1.16</td></tr><tr><td colspan="2">SparseVD 256 (Chirkova et al., 2018)</td><td colspan="3">9, 985 Mult weights</td><td>109.2</td><td>1.34</td></tr><tr><td colspan="5">SparseVD-Voc 256 (Chirkova et al., 2018) 4, 353 Mult weights</td><td>120.2</td><td>0.52</td></tr><tr><td/><td/><td colspan="3">2, 000 Dynamic</td><td>77.7</td><td>0.65</td></tr><tr><td>Anchor &amp; Transform 200</td><td/><td colspan="3">1, 000 Dynamic 500 Dynamic</td><td>79.4 84.5</td><td>0.41 0.27</td></tr><tr><td/><td/><td>100</td><td colspan="2">Dynamic</td><td>106.6 0.05</td></tr><tr><td/><td/><td colspan="3">2, 000 Dynamic</td><td>71.5</td><td>0.78</td></tr><tr><td>Anchor &amp; Transform 256</td><td/><td colspan="3">1, 000 Dynamic 500 Dynamic</td><td>73.1 77.2</td><td>0.49 0.31</td></tr><tr><td/><td/><td>100</td><td colspan="2">Dynamic</td><td>96.5</td><td>0.05</td></tr><tr><td>Method</td><td>A</td><td colspan="2">Init A</td><td colspan="2">Sparse T RELU(T) Domain Ppl # Emb (M)</td></tr><tr><td colspan="3">AWD-LSTM (Merity et al., 2017) 10, 000</td><td>All</td><td/><td>59.0</td><td>4.00</td></tr><tr><td>Post-SH (Guo et al., 2017)</td><td colspan="3">1, 000 Post Processing</td><td/><td>118.8</td><td>0.60</td></tr><tr><td>Post-SH (Guo et al., 2017)</td><td colspan="3">500 Post Processing</td><td/><td>166.8</td><td>0.30</td></tr><tr><td>Post-SH+k-SVD</td><td colspan="3">1, 000 Post Processing</td><td/><td>78.0</td><td>0.60</td></tr><tr><td>Post-SH+k-SVD</td><td colspan="3">500 Post Processing</td><td/><td>103.5</td><td>0.30</td></tr><tr><td/><td>1, 000</td><td colspan="2">Dynamic</td><td/><td>72.0</td><td>0.44</td></tr><tr><td>Anchor &amp; Transform</td><td>500 1, 000</td><td colspan="2">Dynamic Frequency</td><td/><td>74.0 77.0</td><td>0.26 0.45</td></tr><tr><td/><td>100</td><td colspan="2">Frequency</td><td/><td>70.0</td><td>0.05</td></tr></table>

Language modeling on WikiText-103. We reach within 3 perplexity with ∼ 16× reduction and within 10 perplexity with 100× reduction, outperforming frequency and hashing baselines.

Table content: <table><tr><td>Method</td><td>A</td><td>Init A</td><td colspan="2">Sparse T RELU(T) Domain Ppl # Emb (M)</td></tr><tr><td colspan="2">AWD-LSTM (Merity et al., 2017) 267, 735</td><td>All</td><td>35.2</td><td>106.8</td></tr><tr><td colspan="2">Hash Embed (Svenstrup et al., 2017) 100, 000</td><td>Frequency</td><td>40.6</td><td>40.4</td></tr><tr><td colspan="2">Hash Embed (Svenstrup et al., 2017) 50, 000</td><td>Frequency</td><td>52.5</td><td>20.4</td></tr><tr><td colspan="2">Hash Embed (Svenstrup et al., 2017) 10, 000</td><td>Frequency</td><td>70.2</td><td>4.4</td></tr><tr><td>Post-SH (Guo et al., 2017)</td><td>1, 000</td><td>Post Processing</td><td>764.7</td><td>5.7</td></tr><tr><td>Post-SH (Guo et al., 2017)</td><td>500</td><td>Post Processing</td><td>926.8</td><td>2.9</td></tr><tr><td>Post-SH+k-SVD</td><td>1, 000</td><td>Post Processing</td><td>73.7</td><td>5.7</td></tr><tr><td>Post-SH+k-SVD</td><td>500</td><td>Post Processing</td><td>148.3</td><td>2.9</td></tr><tr><td/><td colspan="2">1, 000 Dynamic (λ = 10 -6 )</td><td>38.4</td><td>6.5</td></tr><tr><td>Anchor &amp; Transform</td><td colspan="2">1, 000 Dynamic (λ = 10 -5 ) 500 Dynamic (λ = 10 -6 )</td><td>39.7 48.8</td><td>3.1 1.4</td></tr><tr><td/><td colspan="2">500 Dynamic (λ = 10 -5 )</td><td>54.2</td><td>0.4</td></tr></table>

Word association results after training language models with ANT on the word-level PTB dataset. Left: the non-anchor words most induced by a given anchor word. Right: the largest (non-anchor, anchor) entries learnt in T after sparse regularization.

Table content: <table><tr><td/><td/><td>Largest word pairs</td></tr><tr><td/><td/><td>trading, brokerage</td></tr><tr><td/><td/><td>stock, junk</td></tr><tr><td/><td/><td>year, summer</td></tr><tr><td/><td/><td>york, angeles</td></tr><tr><td>Anchor words</td><td>Non-anchor words</td><td>year, month</td></tr><tr><td>year</td><td>august, night, week, month, monday, summer, spring</td><td>government, administration</td></tr><tr><td>stock</td><td>bonds, certificates, debt, notes, securities, mortgages</td><td>two, nine</td></tr></table>

Table of hyperparameters for language modeling experiments using LSTM on PTB dataset.

Table content: <table><tr><td>Model</td><td>Parameter</td><td>Value</td></tr><tr><td colspan="2">Embedding dim</td><td>200</td></tr><tr><td colspan="2">Num hidden layers</td><td>2</td></tr><tr><td colspan="2">Hidden layer size</td><td>200</td></tr><tr><td/><td>Output dim</td><td>10, 000</td></tr><tr><td/><td>Loss</td><td>cross entropy</td></tr><tr><td/><td>Dropout</td><td>0.4</td></tr><tr><td colspan="2">Word embedding dropout</td><td>0.1</td></tr><tr><td colspan="2">Input embedding dropout</td><td>0.4</td></tr><tr><td colspan="2">LSTM layers dropout</td><td>0.25</td></tr><tr><td colspan="2">Weight dropout</td><td>0.5</td></tr><tr><td>model</td><td>Weight decay</td><td>1.2 × 10 -6</td></tr><tr><td colspan="2">Activation regularization</td><td>2.0</td></tr><tr><td colspan="2">Temporal activation regularization</td><td>1.0</td></tr><tr><td/><td>Batchsize</td><td>20</td></tr><tr><td colspan="2">Max seq length</td><td>70</td></tr><tr><td/><td>Num epochs</td><td>500</td></tr><tr><td/><td>Activation</td><td>ReLU</td></tr><tr><td/><td>Optimizer</td><td>SGD</td></tr><tr><td/><td>Learning rate</td><td>30</td></tr><tr><td/><td>Gradient clip</td><td>0.25</td></tr><tr><td colspan="2">Learning rate decay</td><td>1 × 10 -5</td></tr><tr><td/><td>Start decay</td><td>40</td></tr><tr><td>E.2 LANGUAGE MODELING ON PTB</td><td/><td/></tr></table>

Table of hyperparameters for language modeling experiments using AWD-LSTM on PTB dataset.

Table content: <table><tr><td>Model</td><td>Parameter</td><td>Value</td></tr><tr><td/><td>Embedding dim</td><td>400</td></tr><tr><td/><td>Num hidden layers</td><td>3</td></tr><tr><td/><td>Hidden layer size</td><td>1, 150</td></tr><tr><td/><td>Output dim</td><td>10, 000</td></tr><tr><td/><td>Loss</td><td>cross entropy</td></tr><tr><td/><td>Dropout</td><td/></tr><tr><td>model</td><td/><td/></tr></table>

More language modeling results using AWD-LSTM on Penn Treebank. Using domain knowledge to infer sparse structures helps to reduce the embedding parameters by 100×. Ppl: perplexity, # Emb: # (non-zero) embedding parameters.

Table content: <table><tr><td/><td colspan="3">100 Frequency</td><td>96.7</td><td>39.0</td></tr><tr><td/><td>80</td><td/><td>Cluster</td><td>98.1</td><td>30.0</td></tr><tr><td>Anchor &amp; Transform</td><td colspan="3">100 Dynamic 50 Frequency</td><td>98.2 97.3</td><td>28.0 18.0</td></tr><tr><td/><td colspan="3">20 Frequency</td><td>97.2</td><td>7.0</td></tr><tr><td>Method</td><td>A</td><td/><td colspan="3">Init A Sparse T RELU(T) Domain Acc (%) # Emb (M)</td></tr><tr><td>CNN (Zhang et al., 2015)</td><td>254, 495</td><td/><td>All</td><td>94.0</td><td>65.0</td></tr><tr><td colspan="4">Sparse Code (Chen et al., 2016b) 100 Frequency</td><td>92.0</td><td>6.0</td></tr><tr><td/><td>50</td><td/><td>Cluster</td><td>93.0</td><td>5.0</td></tr><tr><td>Anchor &amp; Transform</td><td colspan="3">80 100 Dynamic Cluster</td><td>93.1 93.2</td><td>9.0 6.0</td></tr><tr><td/><td colspan="3">50 Frequency</td><td>92.0</td><td>5.0</td></tr><tr><td>Method</td><td>A</td><td/><td colspan="3">Init A Sparse T RELU(T) Domain Acc (%) # Emb (M)</td></tr><tr><td>CNN (Zhang et al., 2015)</td><td>252, 712</td><td/><td>All</td><td>56.2</td><td>65.0</td></tr><tr><td colspan="4">Sparse Code (Chen et al., 2016b) 100 Frequency</td><td>54.0</td><td>14.0</td></tr><tr><td/><td>80</td><td/><td>Cluster</td><td>56.2</td><td>8.0</td></tr><tr><td>Anchor &amp; Transform</td><td>50 50</td><td colspan="2">Dynamic Dynamic</td><td>55.7 56.0</td><td>6.0 6.0</td></tr><tr><td/><td colspan="3">50 Frequency</td><td>54.7</td><td>3.0</td></tr><tr><td>Method</td><td>A</td><td/><td colspan="3">Init A Sparse T RELU(T) Domain Ppl # Emb (M)</td></tr><tr><td colspan="3">AWD-LSTM (Merity et al., 2017) 10, 000</td><td>All</td><td>59.0</td><td>4.00</td></tr><tr><td/><td colspan="3">1, 000 Dynamic</td><td>72.0</td><td>0.44</td></tr><tr><td>Anchor &amp; Transform</td><td colspan="3">1, 000 Frequency</td><td>77.0</td><td>0.45</td></tr><tr><td/><td colspan="3">100 Frequency</td><td colspan="2">70.0 0.05</td></tr></table>

Peer review (iclr2020):
The paper describes a *layer* that aims at producing embeddings for discrete objects by using fewer parameters than classical embeddings layers. Indeed, the model proposes, instead of learning an embedding matrix of size VxN, to learn a matrix of embeddings of anchors (AxN) and a transformation matrix (VxA) such that the embedding of any object can be found by multiplying A with T. On top of that, they propose different regularization techniques to improve the quality of the learned embeddings, and particularly a proximal gradient method over a L1 normalization on T to reduce the number of parameters. They propose also different ways to initialize A and also a method for incorporating a priori information (e.g knowledge) into the model. They evaluate this model on different tasks: text classification and language modeling and show that they can achieve good performance while using fewer parameters than Sota methods. First of all, the paper is well written, and the description is very detailed and understandable. It was a pleasure to read such a paper! One point which is unclear is the interest of using such a method, and more precisely in which cases, this method can be useful. Indeed, the overall number of parameters of ANT is AxN + VxA (N being the size of the embeddings, A the number of anchors and V the size of the vocabulary) while classical methods are VxN parameters. Said otherwise, we need to have V<N to really have less parameters to train in the model -- knowing that classical embeddings spaces size is usually between 256 and 1024, it means that we have to target a task where the number of anchors is quite low. I agree that the sparsity term on T is here to encourage to decrease the number of parameters but first, the same sparsity could be applied on the original VxN embedding matrix, and also, even if, at the end, the T matrix is sparse, during learning one has to maintain a large matrix in memory. I would like the authors to discuss more on this point which is crucial? Particularly, I am not sure to understand what the #Emb value is in the table (AxN + AxV or just AxN), and how to compare the models. (There is a discussion in Section 3, but the argumentation does not explain why having so many parameters at train time is not a problem). Also, since this is the crucial point in the paper, I would be interested in having a discussion about the use of neural models compression techniques after learning that could also *do the job* (even if they are not trained end-to-end). One other remark concerns the different *components* added into the model (e.g sparsity, orthogonality, Relu...). It is difficult to measure the interest of each of them, and I would recommend the authors to provide an ablation study to make the effect of the different choices more understandable by the reader. The notion of anchors also is misleading since it gives the impression that the A matrix will store embeddings for particular objects, while there is no constraint of that type. Each line of the A matrix is an embedding, but this embedding is not associated with one of the objects seen at train time (no direct mapping from anchors to words in the vocabulary). This has to be made more clear at the beginning of the paper. Concerning the initialization of A by K-means, it assumes that the space of objects has a particular metric. The authors say that this metric can come from a pretrained embedding space, but in that case, the problem in the number of parameters (which is the main justification of this work) is invalid (i.e if you already have an embedding matrix, then just let us fine-tune it). Could you clarify ? The fact that the method would allow incorporating knowledge is certainly the most interesting point. The way it is done has to be better explained (I do not understand why positive pairs are taken into account by not enforcing sparsity on T at this particular point, the way negative pairs are handled seem more natural) The paper is interesting and proposes a new simple model that could be used to keep good performance while reducing the number of parameters of the final model. Discussions have to be added to discuss the relevance of the approach since it still needs a large number of parameters at train time, and the role of each component could be studied more in depth.