Anchor & Transform: Learning Sparse Representations of Discrete Objects
Authors: Paul Pu Liang
Manzil Zaheer
Yuan Wang
Amr Ahmed
Venue:  (2020)
Keywords: sparse representation learning
discrete inputs
natural language processing

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.

Under review as a conference paper at ICLR 2020
ANCHOR & TRANSFORM: LEARNING SPARSE REPRESENTATIONS OF DISCRETE OBJECTS
Anonymous authors Paper under double-blind review
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. Unfor- tunately. 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 small 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 relation- ships (e.g. WordNet, co-occurrence, item clusters). ANT also recovers several task-specific baselines under certain structural assumptions transformation matrices. On text classification and language modeling benchmarks, ANT demonstrates stronger performance with fewer parameters compared to existing vocabulary selection and embedding compression baselines.
the anchors and
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 sys- tems. The standard way to learn these continuous representations involves: 1) defining the vocabulary V= - fiv) } as the set of all objects, and 2) learning [V] d embedding matrix that defines 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 result, there has been large interest in learning sparse representations of these discrete objects rather than the full embedding matrix for cheaper storage 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 be easily adapted for various applications. 2) End-to-end trainable: is advantageous to learn neural representations in an end-to-end manner to directly optimize for the task 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] (0044) and knowledge graphs (Pujara & Singh 2018) for text modeling, 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 I consists of two steps:
1) ANCHOR: Learn embeddings of small set of anchor objects that are representative of all objects (..1) The user retains flexibility in defining these anchors and we show strong performance across suite of initialization strategies including random, frequency, and clustering- 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 the anchors and transformation matrices (Appendix D). In practice, ANT is easy

---

Under review as a conference paper at ICLR 2020
Frequency Clustering
1he
"good"
[A]
MI]
IAI
A
M
eg. frequency, clustering
protrained space e.p. GloVekco occurrance
(a) Anchor
(b) Trausform
Figure I: Anchor & Transform (ANT) is a general method to learn sparse representations of discrete objects consisting of two steps: 1) Anchor: Learn embeddings A of small set of anchor objects A = (ei...., 9,1 |A| << [V] that are representative of all discrete objects (e.g. frequency and clustering based initialization methods). 2) Transform: Learn 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.
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 ( ANT achieves better performance with fewer parameters compared to existing vocabulary selection and embedding compression baselines. Code to replicate our experiments is publicly released at <anonymous>
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 al. 2016), pruning (Wen al. [2166] Dong et al.) 2017: Anwar al. | 2015). or hashing (Guo et al. 2017 et al. 2015 Qi et al. 2017). However, these methods do not allow the user 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 al. (2019) learns d by solving 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 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.) 5015]Chen et al.) 20166)), and performing dropout-based vocabulary selection retains performance on text classification (Chen al. 2019). Other methods aim 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
general and end-to-end trainable, therefore preventing us from learning representations for general tasks. For example, methods that only model 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 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 succinetly represent a large set of points on a manifold or space has been around for a while Mallat (1999); Ahharn et al. (2006). However, to best of our knowledge, they are mostly limited to cases when a distance or similarity function or 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 well understood convex objectives with continuous inputs like in sparse Gaussian Process Regression (Snelson & Ghahramani 2006). where the kernel acts the distance function. It is not evident from literature how apply these anchor tricks to arbitrary learning problem over discrete objects a flexible manner, like in deep networks. Our main contribution to demonstrate how these anchors and sparse transformations
2

---

Under review as a conference paper at ICLR 2020
inttializo with frequent words
Clustering step1 1
Clustering g step
Clustering step
'pood'
'good'
'pood'
og. Govialo
GloVeko
pretrained space eg
Glolokco occurrance
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.
can be trained jointly with neural models as 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 e R=x|V] y e Ra drawn from some joint distribution v(,, where the support of X is over discrete set V (e1,...9911}
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 e classes) or continuous (regression with e targets). The goal is to learn d d-dimensional continuous representation {ei..... (vr] for each discrete object by learning an embedding matrix E E R VVpdd where row i is the representation e; of object i. Learning this representation allows us to embed the discrete data into H = XE and define a neural model fo with parameters 0 to predict y given representations H, i.e. y [H( = (XEE)
Instead of learning the large embedding matrix E directly, ANT consists of two components:
1) ANCHOR: Learn embeddings A E R| of a small set of anchor objects A {a1.... a a1): |A| << |V| that are representative of all discrete objects. One free to use different methods (e.g. random, frequency, or clustering- based initialization strategies) to initialize/select anchors based on the task.
2) TR AN 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 nTT << [V] x 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] x d nnz(T) << [V| x entries that define the complete embedding, which is much fewer than the [V| x d embedding traditionally used. We depict the overall algorithm in Figure [ In the following subsections, we explain how these anchor embeddings ($3.1) and sparse transformations (3.22) 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 find a small set of anchor objects A {ai,..., a |A << V that are representative of all discrete objects. We describe several methods to select these anchor
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 al. 20155 Chen et al. 20166), 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 met- ric space consisting of n points Xj...., Xn, é Rd with some distance function d(), k-means++ initialization is randomized algorithm that picks cluster centers to span the entire space. In prac- tice, S is usually a feature space representative of the relationships between objects, such as the Glove (Pennington al. (014)) or Word2vec (Mikolov et al.) 2013) embedding space for words or a co-occurennce 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:
D(x) mineec d( Xx c), and 2. add x, to C' with probability o (x,). This clustering initial-
Please refer to Appendix A for more strategies and comparison of various initialization strategics.
3

---

Under review as a conference paper at ICLR 2020
A3
A4
durerng basis posi
softmax()
x M
M
Figure 3: Generalized nonlinear mixture of anchors A,,... Aas and transformations Ti..., Tas- E Em=1 softmax Am (softmax across rows of m.). Different sparse transformations can be learned for different initializations of anchor embeddings.
ization method can also be used 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 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 low-rank representation of the full embedding space E.
Mixture of anchors: In general, different initialization strategies may bring about different advan- tages. For example, using a mixture of random basis vectors has been shown to help model multisense embeddings (Athiwaratkun et al. 2018: Nguyen et al., (017). One can define a set of M anchor embeddings A1, AM each initialized by different strategies and of possibly different sizes.
3.2 TRANSFORM: LEARNING THE SPARSE TRANSFORMATION T
We now describe how TRANSFORM the anchor embeddings A the full embedding matrix E. while enforcing sparsity in how these transformations are parametrized.
Linear transformation: We begin with a simple linear transformation
VH|AA that maps the anchor embeddings the entire embedding matrix: E TA. The final embedding e; for object i is given by a linear combination of anchor embeddings whose weights are given by t; (row i of T).
End-to-end training objective: Given the embedding matrix E which has defined by A and T, we add a model with parameters 0 on top of the embedding matrix (e.g. fully connected layers or RNN/CNN/Transformn a function A, T, and (and X, y). Our end-to-end training objective is therefore
been implicitly
for sequential data) and define loss function L which
A' T 8" arg -arg min ((
A,T,0
which directly optimizes for A and T for task sask-fpc representation learning.
Making T sparse: As it is, is still high-dimensional with |V| x |Al parameters. To enforce sparsity, we add an é penalty on transformation T, which transforms our overall objective function into:
A' aarg aaggminn((((.AAATTT. A.T
+ A|T||1,
where À is regularization factor. | denotes of absolute values (not matrix nuclear norm). Most deep learning frameworks, would directly use subgradient descent to solve equation 2 but unfortunately such approach will not yield sparsity. Instead, perform optimization by proximal gradient descent (Parikh & Boyd| 2014) to ensure exact zero entries in T:
A 1+1 Tht11 gx+1
-GRADIENT STEP (VLU((:A''T' ()),)) t = FROXXXXTT*)]
(3)
where is the learning rate, GRADIENT STEP is gradient update rule (e.g. SGD (Lecun et al. 1998
ADAM (Kingma & Bal 2014), and PROX,A the ooftthhresolding operator (Beck & Teboulle 2009) with threshold 7 This results in transformation with few non-zero entries. Embedding e; for object now defined by a sparse combination anchor embeddings with weights given by t..
Connections to sparse dictionary learning, sparse recovery, compressive sensing: In Ap- pendix B outline connections between ANT and sparse dictionary learning (Awasthi & Vi- jayaraghavan, 2018). By using results from sparse recovery (Candes Tao 2005) Candès) (2008), we can show that /rregularizztion (equation 2 results in provably sparse entries in T.
4

---

Under review as a conference paper at ICLR 2020
bird
Positive pairs P
(birdl cenary)
(animal, bird)
(deep, learning)
M
WordNet
(food. table)
cansry
don't penalize this entry!
(stor star trek)
|A]
Negative pairs N
occurrence
(animal, bank) (food, learnin) (table, california (tuesdaay dollar)
M
animal
these rows should be unrelated!
bank
(star wars, love actually)
movie clusters
[A]
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. and t, of negative pairs also discouraged from sharing similar entries.
Reducing redundancy in representations: We additionally employ two methods to reduce redun- dancy in our sparse representations. Firstly, we perform orthogonal regularization of dynamic basis vectors A by adding the loss term ((A)= = Σizj a a that different basis vectors a, and a, are orthogonal instead of being linear combinations of one another which would lead to redundancies across different learnt entries in T. Secondly, we employ 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.
to the loss function in equation 2 This ensures
Nonlinear mixture of transformations. In $3.1 we proposed learn multiple sets of anchor embeddings ,.,..., A To truly exhibit the advantage of multiple anchors, we need to transform and combine them in a nonlinear fashion, e.g. E Σm= softmax (T. Am (softmax over the rows of 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 ( mm) can be viewed as softmax-activated (sparse) attention weights and A,, m the values to attend over.
3.3 ATTORPORATING DOMAIN KNOWLEDGE
Another benefit of our approach is its generality in incorporating domain knowledge about object relationships. Suppose
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 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, 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 row and column v (and vice versa). This allows ANT to freely learn the transformation between related objects u and u 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) for (u, v) P (entries not & f1-penalized) and S(G) u.v = otherwise (entries are 4 pennealli
A T 00 arg min (( + & A,T,
(5)
Since perform proximal GD this is equivalent only tort-hhresholding the regularized entries between unrelated objects, i.e. T PROXX,X(T o S(G)) + T (1 (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, = Σ(u,))eN |t,] [ty] to the loss function in equation where each inner sum discourages t. and t. from sharing similar entries.
5

---

Under review as a conference paper at ICLR 2020
Algorithm 1 Anchor & Transform algorithm for learning sparse representations of discrete objects.
EnsureA & TRANSFORM:
1: Anchor: initialize anchor objects A and their embeddings A1....,M..
2: Transform: initialize linear transformations T.,...; Ta 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 == 1m softmax (
6: Embed input data tokens X with embeddings E. Compute predictions y fo fX, A. T).
7:
8:
Compute loss C (f (X; A, T, (). [(A) ((T,,N) (optionally + domain info).
9:
A, T, 0- GRADIENT STEP (VL, n).
10:
T RELU((ROX, (T o S(G)) + To (1-S()))).
11: end for
12: return anchor embeddings A and sparse transformations (T).
3.4 EFFICIENT TRAINING AND INFERENCE
The overall algorithm is given in Algorithm T 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) (T) << [V] x d which makes storage of T extremely efficient as compared traditional approaches of computing and storing the entire [V| d embedding matrix. We also provide some implementation tips to further speedup training in Appendix and ways to incorporate ANT with existing speedup techniques like softmax sam- pling (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] x entries that completely define the complete embedding matrix, thereby using fewer parameters than the traditional [V] x d embedding matrix. Furthermore, compression techniques such as hashing (Qi et al. 2017), pruning (Dong et al.) (2017). and quantiz- ing (Han et al. 2016) are compatible with our method: the resulting matrices A and nnz (T) can be further compressed and stored.
emphasize that general purpose matrix
3.5 GENERALITY OF ANT
In Appendix D we show that under certain structural assumptions the anchors and transformation matrices, ANT reduces to several established task-specific methods for learning sparse represen- tations: 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.
EXPERIMENTS
To evaluate the effectiveness of ANT in learning sparse representations of discrete objects, we evaluate performance text classification and language modeling tasks.
4.1
TEXT CLASSIFICATION
Sctup: We follow the setting in Chen et al. 2019) with four datasets: AG-News (V|= = 62K) (Zhang
let al. 2015), DBPedia ([V)= = 563K) (Lehmann et al. 2015). Sogou-News (V) | 254K) (Zhang et al. 2015). and Yelp-review (VI = 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 parameters used the embedding only (excluding CNN). For ANT, num params is computed as |A] x xd mnz T))
Baselines: In addition the CNN, we compare the following compression approaches. Vocabulary selection: 1) Frequency where only embeddings for most frequent words are learnt (Luong et al. 2015 Chen al. 2016b), 2) TF-IDF which only learns embeddings for words with high IDF score [Ramos] 1999), 3) GL (group lasso) which aims to find underlying sparse structures in the embedding matrix via row-wise &a regularization (Park et al. 2016 Liu al. 2015 Wen al. 2016), 4) VVD (variational vocabulary dropout) which performs variational dropout for vocabulary selection (Chen al. 2019), 5) Sparse (sparse variational dropout) which performs variational

---

Under review as a conference paper at ICLR 2020
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 40x 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 (%)
f Emb (M)
CNN (Zhang al. 2015)
673
X
91.6
15.87
Frequency (Chen ct all 2019
5, 000
Frequeney
X
X
X
91.0
1.28
TF-IDF (Chen
(2019)
000
TF-IDF
X
X
91.0
1.28
GI. CCen ct al.
2019)
4, 000
Group lasso
X
X
X
91.0
1.02
VVD Chen 2019)
000
Var dropout
X
X
91.0
0.77
Vp Chirkova et al.
2018)
5, 700
Mult weights
X
X
88.8
1.72
Sparse Voe (Chirkova al.
2018
2, 2,400
Mult weights
X
X
89.2
0.73
Sparse Code (Chen et al.
2016b
100
Frequency
X
X
89.5
2.03
50
Frequency
X
89.5
1.01
10
Frequency
91.0
0.40
Anchor & Transform
10
Dynamic
90.5
0.40
5
Dynamic mixture
90.5
0.70
dropout on all parameters (Chirkova et al. 2018). and 6) Sparse VD- Voc which additionally uses multiplicative weights for vocabulary sparsification (Chirkova et al. (0018). 7) We also compare to Sparse Code model that learns a sparse code to reconstruct pretrained word representations (Chen al. 2016b). All CNN architectures are the same throughout these baselines, details in Appendix E.
Results on AG-News are presented in Table T 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, compres- sion of 40x the baseline and outperforming the existing approaches. Using mixture of anchors and transformations also achieves stronger performance than the baselines using anchors per mixture, although the larger number of transformations leads an increase in parameters.
4.2 LANGUAGE MODELING
Setup: We perform experiments word-level Penn Treebank (PTB) (VI 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 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.
We compare to Sparse and Sparse VD- Voc, as well as low-rank (LR) and tensor-train (TT) model compression techniques (Grachev 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 H.2p. Note that the application of variational vocabulary selection 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 a post- processing step before evaluating using the compressed embedding matrix: Post-SH (post-proce prost-processing (improving sparse representation using k-SVD) [uuo et al. 2017] |] Awasthi & Vijayaraghavan, 2018) which additionally uses k-SVD (Aharon al. (006) solve for sparse representation of the embedding matrix, instead of adhooc-prjecttin 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.
Baselines:
using sparse hashing) (Guo al. 2017) and
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 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 Soat-SH+--VDDD. we hypothesize this is because these post-processing accumulate emror in both language modeling well as embedding reconstruction. Using an anchor size of
7

---

Under review as a conference paper at ICLR 2020
Table 2: 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.
Method
[
Init A
Sparse T RELU(T) Domain
Ppl
# Emb (M)
LSTM 200
(Grahhvv al.
2019)
10, 000
All
X
77.1
2.00
LSTM 256
(Chirovva et al.
2018)
10,000
All
X
X
X
70.3
2.56
LR 200
Grachev al.
2019)
10,000
All
112.1
1.26
TT 200
Grachey ct al.
2019)
10,
All
X
X
X
116.6
1.16
Sparse VD 256 (Chirkova al.
2018
9, 985
Mult weights
109.2
1.34
Sparse Virse Voc 256 (Chirkova et al.
2018
4, 353
Mult weights
X
120.2
0.52
0.000
Dynamic
77.7
0.65
1,000
Dynamic
X
79.4
0.41
Anchor Transform 200
500
Dynamic
X
84.5
0.27
100
Dynamic
X
106.6
0.05
000
Dynamic
X 71.5
0.78
1, 000
Dynamic
73.1
0.49
Anchor & Transform 256
500
Dynamic
X
77.2
0.31
100
Dynamic
96.5
0.05
Method
[
Init A
Sparse T RELU(T) Domain
Ppl
# Emb (M)
AWD-LISTM (Merity
2017
10, 000
All
59.0
4.00
Post-SH (Guo et al.
2017)
1,000
Post Processing
X
X
118.8
0.60
Post-SH Guo et
2017)
500
Post Processing
166.8
0.30
Post-SH-K-SVD
1,000
Post Processing
X
X
78.0
0.60
Post-SH+k-SVD
500
Post Processing
103.5
0.30
1,000
Dynamic
72.0
0.44
500
Dynamic
74.0
0.26
Anchor & Transform
1, 0000
Frequency
77.0
0.45
100
Frequency
70.0
0.05
500/1000 reaches a good perplexity/compressio trade-off: we reach within 2 points perplexity with 5x reduction in parameters and within points perplexity with 10x reduction. Using AWD-LSTM, ANT with 1, 000 dynamic basis vectors is able to compress parameters by 10x while achieving 72.0 perplexity. Incorporating domain knowledge allows to further compress the parameters by another 10x and achieve 70.0 perplexity, which results in 100x total compression.
On WikiText- 103, 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-10FF 1033 We tried general compression techniques like low rank tensor and tensor train factorization (Grachev et al., 2019). but these did not scale. As alternative, words and hashes the remaining words into 1, 0000 OOV buckets (Svenstrup et al. 2017). We vary k x 10², 5 10 x 10*). The results in Table 3 show that we can reach within 3 points perplexity with 16x reduction parameters and within 10 points perplexity with 100x reduction, outperforming the frequency and hashing baselines. We observe that the performance improvement of ANT over post-pree poss-proessiig compression methods (Post-SH and Post-SH+k Saas-SHH--VVVI -VD) larger on WikiTeext 103 as compared to PTB, demonstrating that our end-to-end sparse embedding method is particularly suitable for tasks with large vocabularies.
consider Hash Embed baseline that retains the frequent k
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[]after training AWD-LSTM PTB. On the left we show the most associated non-anchor words for 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 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).
"Wille Baevski & Auli 2018 adapt embedding dimensions according word frequencies, their goal is not compression and 44.9M (dense) parameters in their adaptive embedding layer. while we as less as 0.4M (100x less). Also they obtained results using Transformer with 250M params while AWD-I STM 130M.
8

---

Under review as a conference paper at ICLR 2020
Table 3: Language modeling on WikiText- 103. We reach within 3 perplexity with ~ 16x reduction
and within 10 perplexity with 100x reduction, outperforming frequency and hashing baselines.
Method
Init
Sparse T RELUCT) Domain Ppl
* Emb (M)
AWD-LSTM Mcrity ct al.
2017)
267, 735
All
X
35.2
106.8
Hash Emhed Svenstrup
2017
100, 000
Frequency
X
40.6
40.4
Hash Emhed (Svenstrup ct al.
2017 7
50, 000
Frequency
X
52.5
20.4
Hash Emhed (Svenstrup
2017
10, 000
Frequency
X
70.2
4.4
Post-SH (Guo et al.
2017)
1,000
Post Processing
V
764.7
5.7
Post-SH Guo et
2017)
500
Post Processing
926.8
2.9
Post-SH-k-SVD
1,000
Post Processing
73.7
5.7
Post-SH+k-SVD
500
Post Processing
148.3
2.9
1,000
Dynamic (A 10
38.4
6.5
1, 1,000
Dynamic (A 10
39.7
3.1
Anchor & Transform
500
Dynamic (A = 10
X
48.8
1.4
500
Dynamic (A= 10-
54.2
0.4
Table 4: Word association results after training language models with ANT on the word-level PTB dataset. Left: the non-anchor words most induced by given anchor word. Right: the largest (non-anchor, anchor) entries learnt after sparse regularization.
Largest word pairs trading, brokerage stock, junck year, summer
york, angeles year, month government, administration two, nine
Anchor words
Non-anchor words
year stock
august, night, week, month, monday, summer, spring bonds, certificates, debt, notes, securities, mortgages
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- mati-b the use of proximal GD was crucial. With default subgradient descent did not observe sparsification of T.
3) Choice of A: Performance is robust wrt choice of We give detailed discussion in Appendix A and provide results on clustering initializations. In general, while frequency and clustering work better, using 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 good representation space like GloVe to perform clustering), then the user should do so. However, for new set of discrete objects, using random basis embeddings with sparsity also works well.
RELU: Passing T through RELU important to reduce redundancy in each row entry.
Using a mixture of anchors and transformations also achieves stronger performance than existing baselines, although the larger number of transformations increases the parameters.
5) Mixture:
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.
CONCLUSION
This paper presented Anchor Transform (ANT) to learn sparse representations discrete objects by 1) learning small set of anchor embeddings and 2) learning sparse transformation from anchors all objects. ANT scalable, flexible, end-to-end trainable, and allows 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.
REFERENCES
Anish Acharya, Rahul Goel, Angeliki Metallinou, and Inderjit S. Dhillon. Online embedding compression for text classification using low rank matrix factorization. CoRR, abs/1811.00641, 2018. URL Ittpp
//arxiv. wwwp:iivwrggabb///eee 00641

---

Under review as a conference paper at ICLR 2020
M. Aharon, M. Elad, and A. Bruckstein. K-svd: An algorithm for designing overcomplete dictionaries for sparse representation. Trans. Sig. Proc., 54(11):4311-4333 4322, November 2006. ISSN 1053-587X.
doi:
10.11099/S9.2000.88811
/tL.attta.///6.....r0000001111/0 200..
Sajid Anwar, Kyuyeon Hwang, and Wonyong Sung. Structured prumiin of deep convolutional neural networks. CoRR, abs/ 1b1/1512, 2015. URL http://aaxwv..rrgap/a////
David Arthur and Sergei Vassilvitskii. K-means++: the advantages careful seeding. In In Proceedings of the 18th Annual ACM- MMMM Symposium on Discrete Algorithms, 2007.
Ben Athiwaratkum, Andrew Wilson, and Anima Anandkumar, Probabilistic FastText for multi-sense word embed- dings. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers). pp. 1-11. Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10.18653/v1/P18 1001. URL //ww:::::/ww/w../ acl web. org/ http://anhhllooyPP1-oooo
Pranjal Awasthi and Aravindan Vijayaraghavan Towards learning sparsely used dictionaries with arbitrary supports. CoRR, abs/1804.08603, 2018. URL. http:tttp////xi..rrtt/
08603
Olivier Bachem, Mario Lucic, and Andreas Krause. Practical coreset constructions for machine learning. 2017.
Alexei Baevski and Michael Auli. Adaptive input representatiins for neural language modeling. CoRR, abs/1809.10853, 2018. URL
10853
Amir Beck and Marc Teboulle. A fast iterative taankagg-ttresholddig algorithm for linear inverse problems. SIAM J. Img. Sci., 2(1):183-200 202, March 2009, ISSN 1936-4954, doi: 10. 0377000716542. URL http
//dx. doi. org 10. 1100.11151 111703007165155
Y. Bengio and J. S. Senecal, Adaptive importance sampling to accelerate training of neural probabilistic language model. Trans, Neur. Netw., 19(4):713 722, April 2008 ISSN 1045-9227. doi: 10.1 10.1109/TNN.0077. 912312. URL. http://xx// doi org/ 109 NN 2007. 912312
Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. Enriching word vectors with subword information. CoRR, 0hhs/160..044 04606, 2016. URL/:ttp://azzet http://wwwww.o//////a//o/oo abs /17. 0660664607666666 04606
Emmanuel Candes and Terence Tao. Decoding by linear programming. arXiv preprint mathv0503327, 2005.
Emmanuel Candès. The restricted isometry property and its implications for compressed sensing. 2008
Ting Chen, Martin Renqiang Min, and Yizhou Sun. Learning k-way d-dimensional discrete codes for compact embedding representations. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pp. 854 853.863, Stockholmsmssan, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http:: http:://oocceeiiec m1 prress/v00 chtS0//ccheeecc
Wenhu Chen, Yu Su, Yilin Shen, Zhiyu Chen, Xifeng Yan, and William Wang. How large vocabulary does text classification need? A variational approach to vocabulary selection. CoRR, abs/1902. 2019. URL
http: wwtp///ggg//////ee//ee 10339
Wenlin Chen, James Wilson, Stephen Tyree, Kilian Q. Weinberger, and Yixin Chen. Compressing neural networks with the hashing trick. CoRR, abs/1504.04788. 2015. http:: ptatt://arxiiee ottp///riiv..rr///////// 04788
Wenlin Chen, David Grangier, and Michael Auli. Strategies for training large vocabulary neural language models. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics ( (Volume I: Long Papers), pp. 1975-1985. Berlin, Germany, August 2016a. Association for Computational Linguisties. doi: 10. 10.18653/v1/P166 1186. Utt./ttss::////// www www.:ee....o.................... www..orgggnnooogyyolooooooo
Yunchuan Chen, Lili Mou, Yan Xu, Ge and Zhi Jin. Compressing neural language models by sparse word representations. CoRR, abs/1610.03350,, 2016b. URL
wttp:///....//a/......... 03950
Nadezhda Chirkova, Ekaterina Lobacheva, and Dmitry Vetrov. Bayesian compression for natural language processing. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 2910-2915, Brussels, Belgium, October- November 2018. Association for Computational Linguistics. doi: 10. 1..18853/1/DDS. 13119919111111111111111111111111 URL https: www. wwwweb...wbb....... wwwwwwwwwwwwww..e.eee....e.....e wttp//antoooggg/leeeeeeoee
Xin Dong, Shangyu Chen, and Sinno Pan. Learning to prune deep neural networks via layer-wise optimal brain surgeon. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp- 4857-4867. Curran Associates, Inc., 2017.
10

---

Under review as a conference paper at ICLR 2020
Artem M. Grachev, Dmitry I. Ignatov, and Andrey V. Savchenko. Compression of recurrent neural networks for efficient language modeling. CoRR, abs/1902.02280, 2019. URL.ttt:://azxxi..or///////
02380
Guo, Ding, L. Liu, Han, Shao. Learning hash with optimized anchor embedding scalable retrieval, IEEE Transactions on Image Processing, 26(3):1344-135)) March 2017. doi: 10. 10.1.07/ 2652730.
Michael Gutmann and Aapo Hyvrinen. Noise-contrastive estimation: A new estimation principle for unnor- malized statistical models. In Yee Whye Teh and Mike Titterington (eds.). Proceedings of the Thirteenth International Conference Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pp. 297-304, Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. PMLR. URL http://proceeddngg ml www.s/essss..... v9/ w.t.res//////uuuammmm gutmann Da html
Song Han, Huizi Mao, and William J. Dally, Deep compression:
Compressing deep neural network with pruning. trained quantization and huffman coding. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http
// //arxiv. www.//rg/oo. abs/ 1510 251100111999 00149
Sariel Har-Peled and Soham Mazumdar. Coresets for Sk5-mcans and SkS-median clustering and their applica- tions. CoRR, abs/ 18108.18288 2018. /ttttt/p://axxii httpp///aaaiiv.ooraa/////111111 12826
R. Haralick, K. Shanmugam, and I. Dinstein. Texture features for image classification. IEEE Transactions on Systems, Man, and Cyhernetics, 3(6), 1973.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Comput. 98):11335-7780 November 1997. ISSN 0899-7667. doi: (tt.////eco.999..9.. 1735.. URL/pttp://dxx.dd.oor [162/neco. 997 8.1.5135
Manas R. Joglekar, Cong Li, Jay Adams, Pranav Khaitan, and Qune Le. Neural input search for large seale recommendation models. CoRR, 197.04471,,, 2019. URI httttttt///rree www.wwwwwwwo.oooooo....o 907. 44471
Seyoung Kim and Eric Xing. Feature selection via block-regularized regression. Proceedings of the Twenty- Fourth Conference on Uncertainty in Artificial Intelligence, UAI'08, pp. 325 332, Arlington, Virginia, United States, 2008 AUAI Press. ISBN 0-9749039-4-9, URL http:tt::/// //dl acm. org/ tat cfm? id=
3023476. 3023476.3023515 3023515
Yoon Kim. Convolutional neural networks for sentence classification. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1746-1751, Doha, Qatar, October 2014. Association for Computational Linguistics. doi: 10.3115//1/D14411111. | https: /ww.. aclweb
oxg/anntccccgy/D44-11
Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization, 2014. URL lattp: //
arxiv. wwx.vvorr///oooo abs/ 412. 6980 cite arxiv: 1412. 6980CCmmeet: Published as conference paper at the 3rd International Conference for Learning Representations, San Diego, 2015.
Yann Lecun, Lon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient based learning applied to document recognition. In Proceedings of the IEEE, pp. 2278-2324, 1998.
Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Dimitris Kontokostas, Pablo N. Mendes, Schastian
Hellmann, Mohamed Morsey, Patrick van Kleef, Sören Auer, and Christian Bizer. DBpedia a large-scale, multilingual knowledge base extracted from wikipedia. Semantic Web Journal, 6(2):167-195, 2015. URL
http:: jens-
lehnann wwgg fel.elll////.e. sttp://0d1/ssecdpdpiiiaaoao..
Jure Leskovee and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap sstaforrd edu data June 2014.
Shangsong Liang, Ilya Markov, Zhaochun Ren, and Maarten de Rijke. Manifold learning for rank aggregation. In Proceedings of the 2018 World Wide Web Conference, pp. 1735-1744. International World Wide Web Conferences Steering Committee, 2018.
Baoyuan Liu, Min Wang, Hassan Foroosh. Marshall F. Tappen, and Marianna Pensky. Sparse convolutional neural networks. In CVPR, pp. 806-814, IEEE Computer Society, 2015. ISBN 978- 1778--1673-666444 URL http: dblp. uni trierrrirr.e de/ /b/ db http//on///v///eeeeeeee
H. Liu and P. Singh. Conceptnet &mdash; practical commonsense reasoning tool-kit. BT Technology
Jourmal, 22(4):211 226, October 2004, ISSN 1358-3948 doi: http: /top://dx.cco doi org/ 10. 1023/ BTTJ. 0ww.00000000000000 45421.6
URL

---

Under review as a conference paper at ICLR 2020
Qian Liu, Heyan Huang, Yang Gao, Xiaochi Wei, Yuxin Tian, and Luyang Liu. Task-oriented word embedding for text classification. In Proceedings of the 27th International Conference on Computational Linguistics. pp. 2023-2032, Santa Fe, New Mexico, USA, August 2018. Association for Computational Linguistics. URL
htttps:7wwws www. org htt.ooggoocococooooooo
Minh-Thang Luong, Hieu Pham, and Christopher D. Manning, Effective approaches to attention bassed neural machine translation. CoRR, abs/1 508.04005, 2015. URLpttt:: //tp://aaaivvvv/aa www.wwwwwwww.aaaaaaaa.aaao abs 100.. 04025
Stéphane Mallat. A wavelet tour of signal processing. Elsevier, 1999.
Mitchell P. Marcus, Mary Ann Marcinkiewicz. and Beatrice Santorini. Building large annotated corpus of english: The penn treebank. Comput. Linguist., 19(2)3113-300 June 1993. ISSN 0891-2017. URL
htttp://al.cm acm. org/ http://c................aaaa....
Ivan Markovsky. Low Rank Approximation: Algorithms, Implementation, Applications. Springer Publishing Company, Incorporated, 2011. I. ISBN 1447122267, 9781447122266
Stephen Merity, Caiming Xiong, James Bradburr, and Richard Socher. Pointer sentinel mixture models. CoRR, abs/1609.07883, 2016. URL
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing LSTM language models. CoRR, abs/1708.02 02182, 2017. URL httttttt:///atttt htt.t::://aaiii.rrrrtt/. abs/1700 02182
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q Curran Associates,
Weinberger (eds.), Advances in Neural Information Processing Systems 26, pp. 3111-3119, Inc., 2013.
George A. Miller. Wordnet: A lexical database for english. Commun, ACM, 38( 38(11)339 41, November 1995, ISSN 0001-0782. doi: 10. 00.114//21917.229922 URL /ttetp://dcil http//ccccc...c...../oo/oo org/ 10. 1ww.1/1111991.....
Andriy Mnih and Yee Whye Teh. A fast and simple algorithm for training neural probabilistic language models. In Proceedings of the 29th International Coference on International Conference on Machine Learning. ICML'11, pp. 419-426, USA, 2012. Omnipress. ISBN 1778-1-4500-128-11 (ttt:/tt::///. acm. org/
citation wwde 2id -0 30425 3042630
Le Nguyen Hoai Nam and Ho Bao Quoe. Integrating low-rank approximation and word embedding for feature transformation in the high-dimenssoonal text classification. Procedia Computer Science, 12:437-4444 2017. ISSN 1877-0509, doi: https://doi.org/ 11tg:///...01111//ooo.ooo. 2017c. 05.8. URL/http: //www /www. sciencedirect com/ sc ence/ art i cle/pi p1 / 87705091 7711331400 40233 Knowledge- Based and Intelligent Information
& Engineering Systems: Proceedings of the 21st International Conference, KES-20176-8 September 2017,
Marseille, France.
Dai Quae Nguyen, Dat Quoc Nguyen, Ashutosh Modi, Stefan Thater, and Manfred Pinkal. A mixture model learning multi-sense word embeddings. Proceedings of 6th Joint Conference on Lexical and Computational Semantics ( (*SEM 2017), pp. 121-127, Vancouver, Canada, August 2017. Association for Com- putational Linguistics. doi: 10. 11118663/11/1111111 1015. URL wtt.tttss://////ttt http:s:///wwww..e. www. www.wwlwww........... org/ www.ooggggantloggyg...
SS7-100 1015
Neal Parikh and Stephen Boyd. Proximal algorithms. Found. Trends Optim., 1(3): January 2014. 20144 ISSN 2167-3888. doi: 10.1561 1561/2400000003. /ttp:/// doi. wtt.:/oooo...ggg.//.... wtt.or///1011111//00000000000000
Jongsoo Park. Sheng R. Li, Wei Wen, Hai Li. Yiran Chen, and Pradeep Dubey. Holistic sparseenn: Forging the trident of accuracy, speed, and size. CoRR, abs/1608.0140% 2016. URL/ittt:://rxxi..ree cbs/
1608. 01409
Jeffrey Pennington, Richard Socher, and Christopher Manning. Glove: Global vectors for word representation.
In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP). pp. 15332-153,, Doha, Qatar, October 2014. Association for Computational Linguisties. doi: 10.3115/v1/
116- URL lnttps::/wwwwt www.:wwwwwwbbbc.m wwtp://.ww........ogoooooooooote
Jeff M. Phillips. Coresets and sketches. CoRR, abs/1600.00011,, 2016. URL
601 00617
Ofrr Press and Lior Wolf. Using the output emwedding improve language models. CoRR, aws// 2016. URL.ttt:://axtvv.oo/////
Jay Pujara and Sameer Singh. Mining knowledge graphs from text. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, WSDM '18, pp. 789-790, New York, NY, USA, 2018. ACM. ISBN 978-1-4500 1-4503-5588 5581-0.
doi: 00.1145531599622.122211 URLhttp: coi acm. org/
10. N0.11155315555 .1
12

---

Under review as a conference paper at ICLR 2020
Heng Qi. Wu Liu, and Liang Liu. An efficient deep learning hashing neural network for mobile visual search. CoRR, abs/1710.07750, 2017. URL httphtttp//araw..rr///aaa wttp://gggbbbaaoooo//////. 07750
Juan Ramos. Using rf-idf to determine word relevance in document queries, 1999.
Denis Sedov and Zhirong Yang. Word embedding based on low-rank doubly stochastic matrix decomposition. In Long Cheng, Andrew Chi Sing Leung, and Seiichi Ozawa (eds.). Neural Information Processing, pp. 90- 90-100, Cham, 2018. Springer International Publishing. ISBN 978-3-030-04 182-3..
Raphael Shu and Hideki Nakayama. Compressing word embeddings via deep compositional code learning. In International Conference on Learning Representations, 2018. URL https::/ net Corum?id=BJRRa
Edward Snelson and Zoubin Ghahramani. Sparse gaussian processes using pseudo-inputs. In Advances in neural information processing syslems, pp. 1257-1264, 2006.
Dan Svenstrup. Jonas Meinertz Hansen, and Ole Winther. Hash emheddings for efficient word representations. CoRR, abs/1709.03933, 2017. URL http: http/aaaiiivv..e/.ee/eeeeeaeeevt org. aaapgg//a//// 739. 03933
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 5998-6008. Curran Associates, Inc., 2017.
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp. 2074 2082. Curran Associates, Inc., 2016.
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoe V. Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin Johnson, Xiaobing Liu, Lukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, Nishant Patil, Wei Wang. Cliff Young, Jason Smith, Jason Riesa, Alex Rudnick, Oriol Vinyals, Greg Corrado, Macduff Hughes, and Jeffrey Dean. Google's ' neural machine translation system: Bridging the gap between human and machine translation. CoRR, abs/1609 08 08144,222 2016. /tth:tt::/// 08144
org/ absp//bbb///99/
Bin Xu, Jiajun Bu, Chun Chen, Deng Cai, Xiaofei He, Wei Liu, and Jiebo Luo.. Efficient manifold ranking for image retrieval. In Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval, pp. 525-534. ACM, 2011.
Amy Zhang, Nadia Fawaz, Stratis loannidis, and Andrea Montanari. Guess who rated this movic: Identifying users through subspace clustering. CoRR, abs/ 1544, 2012.
1544
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. In Proceedings of the 28th International Conference on Neural Information Processing Systems Vol- ume 1, NIPS' 15, pp. 649 657, Cambridge, MA, USA, 2015. MIT Press, URL http: //l. acm. org/ citation 2ww.:cc2222222222222222529 2969239
13

---

Under review as a conference paper at ICLR 2020
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 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 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 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) [0066] HHar-Plled & 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 perfor- mance. 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 & Quoe 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/co- occurrence information works well while ensuring that the preprocessing and training stages are relatively quick.
In Appendix Fe 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 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 & Quoe 2017, Sedov & Yang. 2018) or codebook learning (Shu & Nakayama 2018 Chen et al.) 2018)).
Formally, the problem becomes
min Tlo subject E" TAA
which is connected to the sparse dictionary learning problem (Awasthi & Vijayaraghavan 2018 a 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:
where we aim to learn an unknown dictionary A" and sparse representation T that generated data
Definition 1. A matrix tb satisfies the Restricted Isometry Property (RIP) with isometry constant 8g if for all k-sparse vectors x, we have
(1 (1-82)11x12 1x S (1+ (1+
Suppose (i) A TT' obeys the Restricted Isometry Property (RIP), (ii) the true transformation matrix T is k-row sparse (each row of T has most l non-zero entries), and (iii) the true embedding E*
14

---

Under review as a conference paper at ICLR 2020
was known, then recovering T from A and E" is possible by using the & regularization (similar to equation 2
Then, classical result by Candes & Tao 2005) Candès 2008 states if xxx for some s-spase
vector x", then the solution to
min |x]|o
subject to y Øx
is equivalent to the solution given by the & problem
min
||*||] subject to y = 4x
(8)
when 62* 5 / 1.
In our setting, we aim to solve the constrained optimization problem
min || subject to E* =TA"
(9)
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 is RIP gives
min |||]| T
subject to T"=TAA.
(10)
which is equivalent to & regularization in equation when written in Lagrange form. Therefore, e-rreuularizttion (like equation 2 provably results sparse entries in T.
C EFFICIENT LEARNING AND INFERENCE
The naive method for learning 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 = 'A (or its non-linear extensions). This decreases the running time from scaling by [V] x d to only scaling as a function nnz (T). For training, using inbuilt sparse representation of most deep learning frameworks like PyTorch 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 anchors and transformations. In fact, we can do better: instead of constructing the entire E matrix to embed a single datapoint x R I* we can instead first index x into T, i.e. xT II*A before performing a sparse matrix multiplication with A, i.e. (xT) E IR Lxd We are essentially taking advantage of the associative property of matrix multiplication and the fact that xT is simple indexing step and (x (xT)) A is an effective sparse matrix multiplication. To enable fast row slicing into sparse matrix, 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 well due to the Ll-prox operator.
just storing the matrix in adjacency list or CSOO format. (We move away
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 al. (013) 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 sparse matrix reconstruct E for inference.
15

---

Under review as a conference paper at ICLR 2020
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 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 1 S(G) using sparse matrices. Recall that S(G) has an entry equal to 1 for entries representing unrelated objects that should be fi-penalized, which makes S()) quite dense since most anchor and non-anchor objects are unrelated. Hence we store 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 o S(G) and T @ (1 -(G)),
Finally, even if we want utilize ANTframework with full softmax in language model, it is possible without blowing up memory requirements. In particular, let g R be the incoming gradient from cross-entropy loss and h R dx1 be the vector coming from layers below, like LSTM. The gradient update then
T - PROX,A nA (T (Ah)
(1I)
The main issue is computing the huge [V x |A| outer product as an intermediate step which will be dense. However, note that incoming gradient g is basically 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 carefully apply the L1-prox operator earlier, which is nothing but a soft-thresooddig, we can make this incoming gradient sparse very sparse. Thus we need to only calculate much smaller sized outer product and touch 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 general framework that unifies some of the work on sparse representation learning done independently in different research areas.
Trequency-based vocabulary selection (Luong et al., 2015 Chen et al. 2016b): Initialize A with the |A| most frequent objects and set To.a for all a A, T O 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 mixture of random basis embeddings (just I anchor per set) A AM e glxd and do not enforce any sparsity on the transformations
TM E [R| If we further restrict ourselves to only linear combinations E = ΣM- Tm Am this is equivalent to implicitly learning the M low rank factors a,, t,, .... tM 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 A1,..., A, initialize transformations Ti.... TAs, and apply linear combination E = ΣM Tm, Am. For sparsity regularization, set row of S(G) ma as reverse one-hot vector with entry dm, = 0 and all else In other words, index dm; of row row T m² is not regularized, and all other entries are é fgregularized with extremely high À such that row T essentially becomes an one-hot vector with dimension dm = 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.
16

---

Under review as a conference paper at ICLR 2020
Table Table of hyperparameterss for classification experiments on AG-News, DBPedia, Sogou- News, and Yelp-review datasets. All text classification experiments use the same base CNN model with the exception of different output dimensions (classes in the dataset): 4 for AG-News, 14 for DBPedia, for Sogou-News, and 5 for Yelp-review.
Model
Parameter
Value
Emibeddig dim
256
Filter sizes
[3,4, 5]
Num filters
100
Filter strides
[1, 1]
Filter padding
valid
Pooling strides
[1.1]
Pooling padding
valid
Loss
cross entropy
model
Dropout
0.5
Batch size
256
Max seq length
100
Num epochs
200
Activation
ReLU
Optimizer
Adam
Learning rate
x 10
Leurning rate decay
10-3
Start decay
40
E EXPERIMENTAL DETAILS
Here we provide more details for our experiments including hyperparameters used, design decisions, and comparison with baseline methods.
E. TEXT CLASSIFICATION
Base CNN model: For all text classification experiments, the base model a CNN (Le cun et al.) 1998) with layers of 2D convolutions and 2D max pooling, before a dense layer the output softmax. The code
adapted from httpp:://gits -oooaaabll - Select lect on and the architecture hyperparameters are provided in Table The only differences the output dimensions which is for AG-News, 14 for DBPedia, 5 for Sogou-News, and 5 for Yelp-review.
com wwnhuchen/
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, (10,20,35 50, 80, 100, 500, 1, 0003. Smaller values of [A] allows to control for fewer anchors and smaller transformation matrix T at the expense performance.
We experiment with sparse linear transformations for T. is a hyperparameter that is selected using the validation set. Larger values allows to control for more sparse entries in T at the expense of performance. For experiments on dynamic mixtures, we use a softmax based nonlinear combination E = ΣM-1 softmax (T ) Am where softmax is performed over the rows of Tm. Note that applying a softmax activation to the rows of T,, makes all entries dense during training, we store T,, as sparse matrices (which is efficient since T. has few non-zero entries) and implicilly reconstruct E.
Transformation:
When incorporating domain knowledge in ANT, we use both WordNet and co- occurrence statisties. For WordNet, 7/www. nltk. org hhtp:/hooooooooooooooooooooo wordnet. htmi For each word we search for its immediate related words among its hypemnyss, 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.
Domain knowledge:
the public WordNet interface provided by NLTK http:
note on baselines: Note that the reported results on Sparse and Sparse Voc (Chirkova et 2018) have a different embedding size: 300 instead of 256. This is because they use pre-trained word2vee or GloVe embeddings to initialize their model before compression is performed.
17

---

Under review as a conference paper at ICLR 2020
Table 6: Table of hyperparameters for language modcling experiments using LSTM on PTB dataset.
Model
Parameter
Value
Embedding dim
200
Num hidden layers
2
Hidden layer size Output dim
200
10, 000
Loss
cross entropy
Dropout
0.4
Word emhedding dropout
0.1
Input embedding dropout
0.4
L.TTM layers dropout
0.25
Weight dropout
0.5
model
Weight decay
1.2 x 10-6
Activation regularization
2.0
Temporal activation regularization
1.0
Batchsize
20
Max seq length
70
Num epochs
500
Activation
ReLU
Optimizer
SGD
Learning rate
30
Gradient clip
0.25
Learning rate decay Start decay
1 10-5
40
E.2 LANGUAGE MODELING ON PTB
Base LSTM model: Our base model is 2 layer LSTM with an embedding size of 200 and hid- den layer size of 200. The code was adapted from https://gitts thu.. com/ sa force/ awd- 1stm- 1m and the full table of hyperparameters is provided in Table
Base AWD-LSTM model: In addition to experiments on vanilla LSTM model 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 150. The full hyperparameters used can be found in Table
Anchor: We experiment with dynamic, frequency, and clustering initialization strategies. The number of anchors |A| is hyperparameter that is selected using the validation set. The range of |A] is in {10,20, 20, 50, 80, 100, 500, 1, 0000. 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 co- occurrence statistics. For WordNet, we use the public WordNet interface provided by NLTK ht 7/www. //www.nltk. nltk. org wwwptwwwt///oooottootttott.t..tt wwt./wt..dddeeeeoooe html For each word we search for immediate related words among its hypernyms, hyponyms, synonyms, and antonyms. This defines the relationship graph. For co-occurrence statistics, we define 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 baselines:
We also used some of the bascline results presented in Grachev al. (2019). Their presented results differ from our computations in two aspects: they include the LSTM parameters top of the embedding parameters, and they also count the embedding parameters twice since they do not perform weight tying (Press & Wolf (0166) (see equation (6) of Grachev et al. (2019)). To account for this, the results of Sparse VD and SparseVD-Vol (Chirkova et al. 2018) as well as the results various LR- and TR- low rank compression methods (Grachev et al. 2019) were modified by subtracting off the LSTM parameters (200 x 200 x 16). This is derived since each of the weight matrices Wiff.o.c. Ui.f.o. in an L.STM layer of size 200 200, and there are 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 x [V), and intermediate hidden layers of the model. For full results, please refer to Grachev al. 2019).
Note that the reported results on Sparse VD and SparseVDD VD-Voe (Chirkova et al. 2018) have a different embedding size and hidden layer size of 256 instead of 200, although these numbers close enough
18

---

Under review as a conference paper at ICLR 2020
Table Table of hyperparameters for language modeling experiments using AWD-LSTM on PTB dataset.
Model
Parameter
Value
Embedding dim
400
Num hidden layers
3
Hidden layer size
150
Output dim
10, 000
Loss
cross entropy
Dropout
0.4
Word emhedding dropout
Input embedding dropout
0.4
LSTM layers dropout
0.25
Weight dropout
0.5
model
Weight decay
1.2 10-6
Activation regularization
2.0
Temporal activation regularization
1.0
Batchsize
20
Max length
70
Num epochs
500
Activation
ReLU
Optimizer
SGD
Learning rate
30
Gradient clip learning rate decay Start decay
0,25
x 10-5
40
for fair comparison. In experiments we additionally implemented an LSTM with embedding size 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 (post- processing using sparse hashing) (Guo et al., 2017) and Post-SH+k-SSY (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 these anchor points, and the second using 1, 000 anchors and 20 nearest neighbors. The first model uses 500 x d |V| x 10 non-zero embedding parameters while the second model uses 1, 000 [V] x 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 method.
E.3 LANGUAGE MODELING WIKITEXT-103
Base AWD-LSTM model: Our base model is layer AWD-LSTM with embedding size of 400 and hidden layer size 2, 500. The code was adapted from https: htt.ttb......g.g com/
sa les www.soorre//eeeoe awdd/aadlllaa 1stml 1m and the hyperparameters used can be found in Table
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 Transformer model with 250M params while our AWD-LSTM model uses 130M params.
For the Hash Embed baseline that retains the frequent ls words and hashes the remaining words into 1, 1,000 OOV buckets (Svenstrup et al. 2017). We vary k (1 [1x(] 10 10ah 104).
F MORE RESULTS
In the following sections we provide additional results on learning sparse representations of discrete objects using ANT.
F.1 TEXT CLASSIFICATIIN
Results: We report additional text classification results on DBPedia, Sogou-News, and Yelp-review in Table Our approach with different initializations and domain knowledge achieves within 1%
19

---

Under review as a conference paper at ICLR 2020
Table 8: Table of hyperparameters for language modeling experiments using AWD-LSTM on
WikiText- dataset.
Model
Parameter
Value
Embedding dim
400
Num hidden layers
4
Hidden layer
500
Output dim
267, 735
Loss
cross entropy
Dropout
0.1
Word emhedding dropout
0.0
Input embedding dropout
0.1
LSTM layers dropout
0.1
Weight dropout
0.0
model
Weight decay
0.0
Activation regularization
0.0
Temporal activation regularization
0.0
Batchsize
32
Max length
140
Num epochs
14
Activation
ReLU
Optimizer
SGD
Learning rate
30
Gradient clip learning rate decay Start decay
0,25
x 10-5
40
accuracy with 21x fewer parameters on DBPedia, within 1% accuracy with 10x fewer parameters on Sogou-News, and within 2% accuracy with 22x fewer parameters Yelp-review.
Different initialization strategies: Here we also presented results across different initialization strategies and find that while those based on frequency and clustering work better, using 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 good representation space perform clustering). then the user should do so. However, for completely new set of discrete objects, simply using low-rank basis embeddings with sparsity also work well.
F.2 LANGUAGE MODELING
Results: We report additional language modeling results using AWD-LSTM PTB in Table 1O ANT with 1, 000 dynamic basis vectors is able to compress the embedding parameters by 10x while achieving 72.0 test perplexity. By incorporating domain knowledge, further compress the embedding parameters by another 10x and achieve 70.0 test perplexity, which results in 100x total compression as compared to the baseline.
20

---

Under review as a conference paper at ICLR 2020
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 statisties. Our approach with different initializations and domain knowledge achieves within 1% accuracy with 21 fewer parameters on DBPedia, within 1% accuracy with 10x fewer parameters on Sogou-News, and within 2% accuracy with 22x fewer parameters on Yelp-review. Acc: accuracy, # Emb: (non-zero) embedding parameters.
Method
A
Init A Sparse T RELU Domain Acc (%)
Emb (M)
CNN (Zhang al.
2015
563, 355
All
x
98.3
144.0
Sparse Code (Chen ct al.
2016b
100
Frequency
96.7
39.0
80
Cluster
/
X
98.1
30.0
100
Dynamic
98.2
28.0
Anchor & Transform
50
Frequency
97.3
18.0
20
Frequency
97.2
7.0
Method
A
Init A Sparse T RELUU(T) Domain Acc (%)
# Emb (M)
CNN (Zhang
2015
254, 495
All
94.0
65.0
Sparse Code (Chen et al.
2016b
100
Frequency
92.0
6.0
50
Cluster
93.0
5.0
80
Cluster
X
93.1
9.0
Anchor & Transform
100
Dynamic
93.2
6.0
50
Frequency
92.0
5.0
Method CNN Zhang et al. 2015
[A|
Init A
Sparse T RELU(T) Domain
Acc (%)
Emb (M)
252, 712
x
X
56.2
65.0
Sparse Code (Chen et al.
2016b)
100
Frequency
x
X
54.0
14.0
Cluster
/
X
56.2
50
Dynamic
/
x
55.7
6.0
Anchor & Transform
50
Dynamic
5
x
56.0
6.0
50
Frequency
V
54.7
3.0
Table 10: More language modeling results using AWD-LSTM on Penn Treebank. Using domain
knowledge to infer sparse structures helps to reduce the embedding parameters by 100x. Ppl: per- plexity, Emb: (non-zero) embedding parameters.
Method
[
Init A
Sparse T (RELU(T) Domain
Ppl
Emb (M)
AWD-LSTM Merity et al. 2017
10,000 000
All
x
x
59.0
4.00
1,000
Dynamic /
/
X
72.0
0.44
Anchor & Transform
1,000
Frequency
/
/
77.0
0.45
100
Frequency /
70.0
0.05
21


Reviews:
[{"review_id": "S1eBeeATKS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nFirst of all, the paper is well written, and the description is very detailed and understandable. It was a pleasure to read such a paper!  \n\nOne 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). \n\nOne 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.\n\nThe 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. \n\nConcerning 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 ? \n\nThe 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)\n\nThe 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. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "HyxrQW3foH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a general embedding 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 the others.\n\nStrengths of the paper:\n1. The paper is well-written and easy to be followed.\n2. The research problem is of great value to be investigated.\n\nWeaknesses of the paper:\n1. The idea of utilizing anchors to reduce the size of features (in your case, the total embeddings of discrete objects to be inferred) has been widely studied in related fields in computer science. For instance, there are a number of papers in the field of manifold learning using anchors to reduce the size. The inherent connections and relationships between the proposed methods and other algorithms using anchors should be carefully discussed.\n2. The contribution of the paper seems not significant, as the idea of utilizing anchors to reduce the number of parameters to be inferred has been widely studies in the related work. There are a number of papers utilizing anchors, such as the followings (just list some of them):\nB. Xu et al., Efficient manifold ranking for image retrieval, in SIGIR 2011.\nS. Liang et al., Manifold learning for rank aggregation, in WWW 2018.\nY. Guo et al., Learning to hash with optimized anchor embedding for scalable retrieval, in TIP, 2017.\nIn the last reference aforementioned above, both anchors and embeddings are jointly taken into account. \n3. Baselines should include some manifold learning algorithms that take anchors into account.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "B1l9VtzZqB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This manuscript proposed to represent the embedding matrix as a small set of anchor embedding and sparse transformation. The paper is trying to be general-purpose, end-to-end trainable, and able to incorporate domain knowledge. Experimental results show that it is possible to compress the embedding in the proposed way without much loss of accuracy.\n \nThe authors propose to find anchor embedding by several methods, such as frequency, clustering, or random sampling. The sparsity on the transform is imposed by L_1. Although I get the basic idea and I am familiar with many of the techniques, it is unclear to me what is the main focus of this paper, and the technical contribution is quite vague. Why is the large embedding matrix a problem? Besides the low-rank form proposed, are there any other ways to compress it? This paper is not well motivated at all. Therefore, I think this manuscript is not ready to publish in its current form.\n\n#####\nThank you for the response! I've increased my score to 3: Weak Reject. Although the idea of compressing the (word) embedding layer using low-rank structures is not new (even with the end-to-end training), the main technical contribution in this paper is to jointly learn the anchor embedding (anchor pre-selected with multiple schemes) and sparse transformation (sparsity achieved via Proximal GD). Moreover, domain knowledge can be incorporated by adding specialized constraints such as orthogonality and selective penalization. \n\nAt first glance, the idea presented in this paper seems not new, and I doubt many people are doing similar stuffs already in practice. I find the explanations on the technical points in Appendix C helpful. The empirical study in this paper looks strong. The authors considered experiments in text classification and language modeling with a number of baselines, which demonstrates the advantages of anchor and joint training in the proposed way. This paper presents several useful heuristics around, but I share the concern with other reviewers about whether the main point is compelling enough, given the existing body of work along with this line. \n\n\n  \n\n\n  ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a method to produce embeddings of discrete objects, jointly learning a small set of anchor embeddings and a sparse transformation from anchor objects to all the others. While the paper is well written, and proposes an interesting solution, the contribution seems rather incremental (as noted by several reviewers), considering the existing literature in the area.  Also, after discussions the usefulness of the method remains a bit unclear - it seems some engineering (related to sparse operations) is still required to validate the viability of the approach.

Decision: Reject