Anchor & Transform: Learning Sparse Embeddings for Large Vocabularies
Authors: Paul Pu Liang
Manzil Zaheer
Yuan Wang
Amr Ahmed
Venue: ICLR 2021 Poster (2021)
Keywords: sparse embeddings
large vocabularies
text classification
language modeling
recommendation systems

Abstract: Learning continuous representations of discrete objects such as text, users, movies, and URLs lies at the heart of many applications including language and user modeling. When using discrete objects as input to neural networks, we often ignore the underlying structures (e.g., natural groupings and similarities) and embed the objects independently into individual vectors. As a result, existing methods do not scale to large vocabulary sizes. In this paper, we design a simple and efficient embedding algorithm that learns a small set of anchor embeddings and a sparse transformation matrix. We call our method Anchor & Transform (ANT) as the embeddings of discrete objects are a sparse linear combination of the anchors, weighted according to the transformation matrix. ANT is scalable, flexible, and end-to-end trainable. We further provide a statistical interpretation of our algorithm as a Bayesian nonparametric prior for embeddings that encourages sparsity and leverages natural groupings among objects. By deriving an approximate inference algorithm based on Small Variance Asymptotics, we obtain a natural extension that automatically learns the optimal number of anchors instead of having to tune it as a hyperparameter. On text classification, language modeling, and movie recommendation benchmarks, we show that ANT is particularly suitable for large vocabulary sizes and demonstrates stronger performance with fewer parameters (up to 40x compression) as compared to existing compression baselines.

Published as a conference paper at ICLR 2021
ANCHOR & TRANSFORM:
LEARNING SPARSE EMBEDDINGS FOR LARGE VOCABULARIES
Paul Pu Liang Manzil Zaheer Yuan , Amr Ahmed
" "Google Research, CCaneeiie Mellon University pliangecs cmu. cmu.edu, (manzi 1 zaheer,
, yuanwang, amra) l @ggogle
ABSTRACT
Learning continuous representations of discrete objects such as text, users, movies, and URLs lies at the heart of many applications including language and user modeling. When using discrete objects as input neural networks, we often ignore the underlying structures (e.g., natural groupings and similarities) and embed the objects independently into individual vectors. As result, existing methods do not scale to large vocabulary sizes. In this paper, we design a simple and efficient embedding algorithm that learns small set of anchor embeddings and a sparse transformation matrix. We call our method ANCHOR & TRANSFORM (ANT) as the embeddings of discrete objects are a sparse linear combination of the anchors, weighted according to the transformation matrix. ANT scalable, flexible, and end-to-end trainable. We further provide statistical interpretation of our algorithm as Bayesian nonparametric prior for embeddings that encourages sparsity and leverages natural groupings among objects. By deriving an approximate inference algorithm based on Small Variance Asymptotics, we obtain natural extension that automatically learns the optimal number of anchors instead of having to tune as hyperparameter. On text classification, language modeling, and movie recommendation benchmarks, we show that ANT is particularly suitable for large vocabulary sizes and demonstrates stronger performance with fewer parameters (up to 40x compression) as compared to existing compression baselines. Code for our experiments can be found at ht /ttp::://giihbb com wwt.cc/o/ccc.eeeee hoompplanggg9. sparse discrete
INTRODUCTION
Most machine learning models, including neural networks, operate on vector spaces. Therefore, when working with discrete objects such as text, we must define a method of converting objects into vectors. The standard way to map objects to continuous representations involves: 1) defining the vocabulary V= (w), ] as the set of all objects, and 2) learning a [V| x embedding matrix that defines a d dimensional continuous representation for each object. This method has two main shortcomings. Firstly, when |V is large (c.g., million of words/users/URRss) this embedding matrix does not scale elegantly and may constitute up to 80% of all trainable parameters (Jozefowicz et al. 2016). Secondly, despite being discrete, these objects usually have underlying structures such as natural groupings and similarities among them. Assigning each object an individual vector assumes independence and foregoes opportunitics for statistical strength sharing. As a result, there has been a large amount of interest in learning sparse interdependent representations for large vocabularies rather than the full embedding matrix for cheaper training, storage, and inference.
In this paper, we propose a simple method to leam sparse representations that uses global set of vectors, which we call the anchors, and expresses the embeddings of discrete objects as sparse linear combination of these anchors, as shown in Figure I One can consider these anchors to represent latent topics or concepts. Therefore, call the resulfing method ANCHOR & TRANSFORM (ANT). The approach is reminiscent low-rank and sparse coding approaches, however, surprisingly in the literature these methods were not elegantly integrated with deep networks. Competitive attempts are often complex (e.g., optimized with RI. (Joglekar et al. (201)). involve multiple training stages (Ginart al. 2019 Liu et al. (017). or require post- processing (Svenstrup et al., 2017 Guo et al., 2017] Aharon et al. 2006) Awasthi & Vijayaraghavan 2018). We derive a simple optimization objective which learns these anchors and sparse transtormations in end-to-end manner. ANT is
work done during an internship Google.

---

Published as a conference paper at ICLR 2021
Frequency Clustaring
"the"
"good"
|A]
A
IVI
IAI
I
frequency.
clustering
pretrained GicVeloo-ocoureeee
1. ANCHOR
TRANSFORM
Figure I: ANCHOR TRANSFORM (ANT) consists of two components: 1) ANCHOR: Learn embeddings A of a small set of anchor vectors A = [a1,..., ). ||| << [V] that are representative of all discrete objects, and 2) TRANSFORM: Learn sparse transformation T from the anchors to the full embedding matrix E. A and T are trained end-to-end for specific tasks. ANT is scalable, flexible, and allows the user to easily incorporate domain knowledge about object relationships. We further derive Bayesian nonparametric view of ANT that yields an extension NBANT which automatically tunes |A] achieve balance between performance and compression.
scalable, flexible, and allows the user flexibility in defining these anchors and adding more constraints on the transformations, possibly in domain/task specific manner. We find that proposed method demonstrates stronger performance with fewer parameters (up to 40x compression) on multiple tasks (text classification, language modeling, and recommendation) as compared to existing baselines.
We further provide a statistical interpretation of our algorithm as a Bayesian nonparametric (BNP) prior for neural embeddings that encourages sparsity and leverages natural groupings among objects. Specifically, we show its equivalence Indian Buffet Process (IBP: Griffths Grifhthss Ghahramani (2005)
prior for embedding matrices. While such BNP priors have proven to be a flexible tools in graphical models to encourage hierarchies (Teh & Jordan| 2010). sparsity (Knowles & Ghahraman] 2011).
and other structural constraints (Roy et al.) 2016). these inference methods are usually complex, hand designed for each setup, and non- conn-ifferrntiable. Our proposed method opens the door towards integrating priors (e.g.. IBP) with neural representation learning. These theoretical connections leads practical insights by asymptotically analyzing the likelihood of model in the small variance limit using Small Variance Asymptotics (SVA; (Ao:i[[eiis](99) (1998)), we obtain a natural extension, NRANT, that automatically learns the optimal number of anchors achieve balance between performance and compression instead of having to tune as a hyperparameter.
RELATED WORK
Prior work in learning sparse embeddings of discrete structures falls into three categories:
Matrix compression techniques such low rank approximations (Acharya al. 2019 Grachev
eet al. 2019: Markovsky (2011). quantizing (Han et al. [2016), pruning (Anwar et al. [201 Dong et al. 2017 Wen et al. 2016 or hashing (Chen et al.) 2015| Guo et al.) 2017] Qi al. 2017 have been applicd to embedding matrices. However, is not trivial to learn sparse low-rank representations of large matrices, especially in conjunction with neural networks. To the best of our knowledge, we are the first to present the integration of sparse low-rank representations, their non-parametric extension, and demonstrate its effectiveness sparsity. We also outperform many baselines based on low-rank compression (Grachev et al. 2019). sparse coding (Chen et al. 2016b), and pruning (Liu et al. (017).
many tasks in balancing the tradeoffs between performance &
Reducing representation size: These methods reduce the dimension d for different objects. Chen et al. 20) divides the embedding into buckets which are assigned to objects in order of impor- tance, Joglekar et al. (2019) learns d by solving discrete optimization problem with RL, and Baevski & Auli (2019) reduces dimensions for rarer words. These methods resort to RL or are difficult to tune with many hyperparameters. Each object is also modeled independently without information sharing.
Task specific methods include learning embeddings of only common words for language model- ing (Chen et al. [20 Luong et al. 2015), and vocabulary selection for text classification (Chen ct al. 2019). Other methods reconstruct pre-trained embeddings using codebook learning (Chen et al. 2018: Shu & Nakayama] 2018) or low rank tensors (Sedov & Yang. 2018). However, these methods cannot work for general tasks. For example, methods that only model a subset of objects cannot be used for retrieval because it would never retrieve the dropped objects. Rare objects might be highly relevant to a few users so might not be ideal to completely ignore them. Similarly, task specifc methods such as subword (Bojanowski et al. (017)) and wordpiece (Wu et al. (0166) embeddings, while useful for text, do not generalize to general applications such as item and query retrieval.
2

---

Published as a conference paper at ICLR 2021
3 ANCHOR & TRANSFORM
Suppose we are presented with data X E V., Y NR drawn from some joint distribution p(a, y), where the support of is set. The entries in can be either discrete (classification) or continuous (regression). The goal is to learn d-dimensional representation {c1, (c 9v]) for each object by learning an embedding matrix E gl/dd where row i is the representation e, of object i. A model fe with parameters 0 is then used to predict y, i... Ds (x,;; E) fo(E [)
discrete set V (the vocabulary) and N is the size of the training
At a high level, to encourage statistical sharing between objects, we assume that the embedding of each object is obtained by linearly superimposing a small set of anchor objects. For example, when the objects considered are words, the anchors may represent latent abstract concepts (of unknown cardinality) and each word is a weighted mixture of different concepts. More generally, the model assumes that there are some unknown number of anchors, A {a1, ..., 8 | The embedding e; for object is generated by first choosing whether the object possesses each anchor a E RR The selected anchors then cach contribute some weight to the representation of object i. Therefore, instead of learning the large embedding matrix E directly, ANT consists of two components:
1) ANCHOR: Learn embeddings A R Aix of small set of anchor objects A fai. .... } | << [V] that are representative of all discrete objects.
Algorithm ANCHOR TRANSFORM algorithm for learn- ing sparse representations of discrete objects.
A ANCHOR & TRANSFORM:
Anchor: initialize anchor embeddings A.
2) TRANSFORM: Learn sparse trans- formation T from A to E. Each of the discrete objects is induced by some transformation from (a few) anchor objects. To ensure sparsity, we want nnz( << [V| x d.
2: Transform: initialize T as a sparse matrix.
3: Optionally domain info: initialize domain sparsity ma-
trix S(G) as a sparse matrix (see Appendix F.
4: for each batch (X, Y) do
5: Compute loss L = Σ, (yr (o;;;; TA))
6: T, UPDATE (VL, 7).
7: T= max ((T 7222) @ S(G) To (1- ((-S()))
A and T are trained end-to-end for task specific representations. To en- force sparsity, we use an & penalty on T and constrain its domain to be non-negative to reduce redundancy in transformations (positive and negative entries canceling out).
8: end for
9: return anchor embeddings A and transformations T.
min Te0, A,
(et (2;;; TA)) (TA: A2|
where D& is suitable Bregman divergence between predicted and true labels, and [T] denotes the sum of absolute values. Most deep learning frameworks directly use subgradient descent to solve eq I but unfortunately, such an approach will not yield sparsity. Instead, we perform optimiza- tion by proximal gradient descent (rather than approximate subgradient methods which have poorer convergence around non-smooth regions, e.g., sparse regions) to ensure exact zero entries in T:
A I+1 T 1+ 0²+1 UPDATE
V Dolvi T' T'A))')'''')))
T PROX n2 (T* max (T -22, n2.. 0).
where 17 is the learning rate, and UPDATE is gradient update rule (e.g.. SGD (Leuun al. 1998). ADAM (Kingma & Ba 2015). YOGI (Zaheer et al. 2018)). PROX is a composition of two proximal operators: 1) soft-thresoolding (Beck & Teboulle 2009) at 7/2 which results from subgradient descent on A2l / and 2) max(-,0) due to the non non-negative domain for T. We implement this proximal operator on top of the YOGI optimizer for our experiments.
Together, equations (2) and (3) give us an iterative process for end-to-end learning of A and T along with 0 for specific tasks (Algorithm []. T is implemented as a sparse matrix by only storing its non-zero entries and indices. Since nnz( (T) << [V] x d, this makes storage of T extremely efficient as compared to traditional approaches of computing the entire V embedding matrix. We also provide implementation tips to further speedup training and ways incorporate ANT with existing speedup techniques like softmax sampling (Mikolov et al. 2013) or noise-contrastive estimation (Mnih & Teh 2012) in Appendix H After training, we only store A d nnz(T) << [V] entries that define the complete embedding matrix, thereby using fewer parameters than the traditional [V] d matrix. General purpose matrix compression techniques such as hashing (Qi et al. 2017), pruning (Dong
3

---

Published as a conference paper at ICLR 2021
al. 2017), and quantizing (Han et al., (0166) compatible with method: the matrices A and nnz( T) can be further compressed and stored.
We first discuss practical methods for anchor selection ($3.1) In Appendix F we describe several ways to incorporate domain knowledge into the anchor selection and transform process. We also provide a statistical interpretation of ANT sparsity promoting generative process using an IBP prior and derive approximate inference based on SVA ($3.2). This gives rise nonparametric version of ANT that automatically learns the optimal number of anchors.
3.1 ANCHOR: SELECTING THE ANCHORS A
Inspired by research integrating initialization strategies based on clustering (Teh et al. 2007) and Coresets (Bachem et al., 2015) with Bayesian nonparametrics, we describe several practical methods to select anchor objects that are most representative of all objects (refer to Appendix D for comparison of initialization strategies.).
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 and the most common objects selected as the anchor points. While this might make sense for tasks such as language modeling (Luong et al. 2015 Chen al. 2016b), choosing the most frequent objects might not cover rare objects that are not well represented by common anchors.
Clustering: To ensure that all objects close to some anchor, we use k-means++ initializa- tion (Arthur & Vassilvitskii, 2007). Given feature space representative
inits frequent
"the"
the relationships between ob- jects, such as Glove (Pennington et al. 2014) for words or co-occurrence matrix (Haralick et al. 1973) for more general objects, k-means++ initial- ization picks cluster centers to span the entire space. This can augment other strategies, such as initializing anchors using frequency followed by clustering to complete remaining anchors (see Figure 2)
pretral Giotbico
Figure 2: An illustration initialization strategies for anchors combining idcas from frequency and k-means+ + clustering initialization. Clustering ini- tialization picks anchors to span the space of all objects after frequent objects have been selected.
Initialize A to set of random basis vectors. This simple yet powerful method captures the case where we have less knowledge about the objects (i.e., without access to any pretrained represeetaaiion/smilaaii space).
Random basis vectors:
3.2 STATISTICAL INTERPRETATION AS A BAYESIAN NONPARAMETRIC PRIOR
To provide statistical interpretation of ANT, we first analyze a generative process for discrete representations that is consistent with our algorithm. Given a set of anchors, A (ai.... a/41). we use a binary latent variable 2 {0, 1} to indicate whether object i possesses anchor k and a positive latent variable W/s lEzo denote the weight that anchor A contributes towards object Therefore, the representation e; is given by e; = Σσ Wik Z1 Ideally, we want the vector 2; to be sparse for efficient learning and storage. More formally, suppose there are K == |A] anchors, then:
Z IRVV IBP(a, b); A R Kxd_ ~ P(A) N W e VixK P(W) Exp(1) for i I....NN fe(z; (Zo W)A) p(up=, W, = (-Ds 0.) (v:)
In this generative process, the selection matrix Z follows a wwopparameter Indian Buffet Process (BB::GGrifitth & Ghahramani (2005)) prior (Ghahramani al., 2007). Not only does this BNP prior allow for potentially infinite number of anchors, but it also encourages each object to only select small subset of anchors, resulting in a sparse z; (see Appendix A for details). We place a standard Gaussian prior on the continuous anchors embeddings a and an exponential prior on the weights W which give the actual non non-negative transformation weights for the non-zero entries defined in Z. E (Z o A is the final embedding learnt by our model which represents a d-dimensional continuous representation (ei,..., elp for each discrete object where row is the representation e; of object i. Finally, a neural model fo with parameters is used to predict yi given the embedded representations, i.e., 0 (a (Z W)A) ) fo( W) A ([x:))
4

---

Published as a conference paper at ICLR 2021
Likelihood Model/Loss: We assume that the final emission model y:lū: belongs to the exponential family. Since exponential family distributions have a corresponding Bregman divergence (Banerjee et al. (2005); see Appendix
C for examples), we choose Do( Di as the corresponding Bregman divergence between predicted and true labels. Appropriate choices for D& recover cross-entropy and MSE losses. (v((v) does not depend on any learnable parameter or variable and can be ignored.
Joint likelihood: Under the generative model as defined above, the joint likelihood is given by:
Y,, Yy, < Elogr(ulae Z, W, log (Z) + logp log ((A)
: - (1- fo (Z W) + bo (v:) log + log W) log)(A).
However, calculating the posterior or MAP estimate is hard, especially due to the presence of the non-linear deep network fo. Approximate inference methods such as MCMC, variational inference, or probabilistic programming would be computationally and statistically inefficient since would involve sampling, evaluating, training the model multiple times. To tackle this problem, we perform approximate inference via Small Variance Asymptotics (SVA), which captures the benefits of rich varial- models while providing framework for scalable optimization (Broderick et al. 201 3a Jiang et al.) 2012; Roychowdhury et al. 2013).
Approximate Inference via SVA: To use SVA, we introduce a scaling variable / and shrink the variance of the emission probability by taking 3 co. The scaled probability emission becomes
(4) Following Broderick et al. (2013a) we modulate the number of features in the large-B limit by choosing constants A > X2 > and setting the IBP hyperparameters a = exp(-3X1) and exp(3X2). This prevents a limiting objective function that favors trivial cluster assignment (every data point assigned to its own separate feature). Maximizing the asymptotic joint likelihood (after taking limits, i.c., limg-oo 1/2 OY Z. W, A(X) results in the following objective function:
p(u m;; 2, W, = exp (-3Do 0:)) (ua(
min T20, A,
Do (x TA)) Ay T (A1 (A1->2)K >2)
where we have combined the variables Z and W with their constraints into one variable T. The exponential prior for W results in non non-negative domain for T. Please refer to Appendix B for derivations. Note that eq (5) suggests a natural objective function in learning representations that minimize the prediction loss D& (z,; TA)) while ensuring sparsity of T as measured by the lo-norm and using few anchors as possible (K). Therefore, optimizing eq (5) gives rise nonparametric version of ANT, which we call NBANT, that automatically learns the optimal numher of anchors. To perform optimization
the number of anchors, our algorithm starts with small |A| = 10 and either adds anchors (i.e., adding a new row to A and a new column to T) or deletes anchors to minimize eq (5) at every epoch depending
the trend of the objective evaluated on validation set. We outline the exact algorithm in Appendix [appendixGalooo Glong with more implementation details.
Analogously, we can derive the finite case objective function for fixed number of anchors K:
min T20, 0,0 - Ed fe (I,; TA)) >2
(6)
which, together with a penalty on T as a convex relaxation for the Eg penalty, recovers the objective function in eq (I) The solution for this finite version along with K yields the Pareto front. Different values of X₁ in eq (5) can be used for model selection along the front as elucidated in Appendix L
4 EXPERIMENTS
To evaluate ANT, we experiment on text classification, language modeling, and movie recommenda- tion tasks. Experimental details are in Appendix J and full results are in Appendix K
4.1 TEXT CLASSIFICATION
Setup: We follow the setting in Chen et al. (2019) with four datasets: AG-News (V = 62K) (Zhang
al. 2015). DBPedia (V 563K) (Lehmann et al. 2015). Sogou-News (V 254K) (Zhang et al.
2015). and Yelp-review (V = 253K) Zhang et al. 2015). We use a CNN for classification (Kim 2014). ANT is used to replace the input embedding and domain knowledge is derived from NerdNet and co-occurrence in the training set. We record test accuracy and number of parameters used in the embedding only. For ANT, num params is computed as |A| d nnz(T).
5

---

Published as a conference paper at ICLR 2021
Table I: Text classification results on AG-News. Our approach with different initializations achieves within 0.5% accuracy with 10x fewer parameters, outperforming the published compression baselines. Init: initialization method, Acc: accuracy. # Emb: number of (non-zero) embedding parameters.
Method
A
Init A
Sparse T
T 2 0
Acc (%)
# Emb (M)
CNN Zhang
2015
673
All
K
X
91.6
15.87
FREQUENCY (Chen et a
2019
5,000
Frequency
X
X
91.0
1.28
TF-IDF (Chen al. 2019
5, 0.00
TF-IDF
X
X
91.0
1.28
GL CChen et al. 2019)
4,000
Group lasso
X
X
91.0
1.02
VVD Chen et al. 2019
0.000
Var dropout
X
X
91.0
0.77
SPARSEVD (Chirkova et al.
2018
5. 700
Mult weights
X
X
88.8
1.72
SPARSEVD- Voc (Chirkova al.
2018
2,400
Mult weights
X
X
89.2
0.73
SPARSE CODE (Chen et al.
2016b)
100
Frequency
X
89.5
2.03
50
Frequency
89.5
1.01
ANT
10
Frequency
91.0
0.40
10
Random
90.5
0.40
Baselines: On top of the CNN, we compare to the following compression approaches. Vocabulary
selection methods: 1) FREQUENCY where only embeddings for most frequent words are learnt (Chen et al. 2016b Luong et al. 2015), 2) TF-IDF which only learns embeddings for words with high TF-IDF score [Ramos| 1999). 3) GL (group lasso) which aims to find underlying sparse structures in the embedding matrix via row-wise & regularization (Liu et al., 2015 Park et al. 2016 Wen et al. 2016). 4) VVD (variational vocabulary dropout) which performs variational dropout for vocabulary selection (Chen et al.) 2019). We also compare to 5) SPARSEVD (sparse variational dropout) which performs variational dropout on all parameters (Chirkova al. 2018), , 6) PPARSEV-VVc which uses multiplicatiie weights for vocabulary sparsification (Chirkova et al. 2018), and 7) a SPARSE CODE model that learns a sparse code to reconstruct pretrained word representations (Chen et al. 2016b). All CNN architectures are the same for all baselines with details in Appendix [.]
Results on AG-News are in Table T and results for other datasets are in Appendix K.
We observe
that restricting 2 0 using an exponential prior important in reducing redundancy the entries. Domain knowledge from WordNet and co-occurrence also succeeded in reducing the total (non-zero) embedding parameters to 0.40M, a compression of 40x and outperforming the existing approaches.
4.2 LANGUAGE MODELING
Setup: We perform experiments on word-level Penn Treebank (PTB) (V 10K) (Marcus et al. 1993) and WikiText- 103 (V = 267K) (Merity et al. (017) with LSTM (Hochreiter & Schmidhuber 1997 and AWD-LSTM (Merity et al. 2018). We use ANT as the input embedding tied to the output embedding. Domain knowledge is derived from WordNet and co-occurrence on the training set. We record the test perplexity and the number of (non-zero) embedding parameters.
We compare to SPARSEVD and SPARSE VDDVDCC. as well as low-rank (LR) and tensor- train (TT) model compression techniques (Grachev et al.. 2019). Note that the application of variational vocabulary selection to language modeling with tied weights is non-trivial since one is unable predict next words when words are dynamically dropped out. We also compare against methods that compress the trained embedding matrix as a post-processing step before evaluation: POST-SPARSE HASH (post-processing using sparse hashing) (Guo al. 2017) and POST-SPARSH RSE HASH+K-SVD (Awasthi & Vijayaraghavan, 2018 Guo et al. (017) which uses k-SVD (which is the basis of dictionary learnin//sparse coding) (Aharon et al. 2006) to solve for sparse embedding matrix, instead of adhoc- sithoc-rrojcction in (Guo et al.) 2017). Comparing to these post- post-processing methods demonstrates that end-to-end training of sparse embeddings is superior to post-compression.
Baselines:
Results: On PTB (Table 2). we improve the perplexity and compression as compared to previously proposed methods. We observe that sparsity is important: baseline methods that only perform lower- rank compression with dense factors (e.g., LR LSTM) tend to suffer performance and use many parameters, while ANT retains performance with much better compression. ANT also outperforms post-processing methods (POST-SPARSE HASH), we hypothesize this is because these post- post-processing methods accumulate errors in both language modeling as well as embedding reconstruction. Using an anchor size of 500/1, 000 reaches good perplexitycoompresion trade-off: we reach within points perplexity with 5x reduction in parameters and within 7 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 us to further compress the parameters by onother 10x and achieve 70.0 perplexity, which results in 100x total compression.

---

Published as a conference paper at ICLR 2021
Table 2: Language modeling on PTB (top) and WikiText- 103 (bottom). We outperform existing vocabulary
selection, low-rank, tensor-train, and post-compression (hashing) baselines on performance and compression metries. Ppl: perplexity, # Emb: number of (non-zero) embedding parameters.
Method (PTB)
A
Init A
Sparse TT 2
0
Ppl
iF Emb (M)
LSTM (Chirkova et al.
2018)
10, 000
All
X
70.3
2.56
LR LSTM Grachev et al.
2019
10, 000
All
X
X
112.1
1.26
TT LSTM Grachev et al.
2019
10, 000
All
X
116.6
1.16
AWD-LSTM (Merity et al
2018
10,000 000
All
X
X
59.0
4.00
SPARSEVD (Chirkova et
2018
9,985
Mult weights
X
109.2
1.34
SPARSEVD- Voc (Chirkova ct al.
201 8
4,353
Mult weights
X
X
120.2
0.52
POST-SPARSE HASHI (Guo
2017
1,000
Post-processing
V
X
118.8
0.60
POST-SPARSE HASH+*ESVD
1,000
Post-processing
V
X
78.0
0.60
2,000
Random
71.5
0.78
1,000
Random
73.1
0.49
ANT
100
Random
96.5
0.05
100
Frequency
70.0
0.05
Method (WikiText- 103)
[A]
Init A
Sparse
T T
0
Ppl
# Emb (M)
AWD-LSTM (Merity et al.
2018
267, 735
All Frequency
X
35.2
106.8
HASH EMBED
Svenstrup al.
2017)
10, 000
x
x
70.2
4.4
POST-SPARSE HASH (Guo et al.
2017
1,000
Post-processing
/
x
764.7
5.7
POST-SPARSE HVSH+I-SVD
1,000
Post-processing
x
73.7
5.7
1,000
Random (A2 = x 10
38.4
6.5
ANT
500
Random (22 10
54.2
0.4
On WikiText- 103, we train using sampled softmax (Bengio & Senecal 2008) (due to large vocabulary) for 500, 000 steps. To best of our knowledge, we could not find literature on compressing language models on WikiText-103, We tried general compression techniques like low rank tensor and tensor train factorization (Grachev et al. 2019), but these did not scale. As an alternative, we consider a HASH EMBED baseline that retains the frequent & words and hashes the remaining words into 1, 000 OOV buckets (Svenstrup al. 2017). We vary k ε (1x 10 5 10 1 x 10*) (details in Appendix J.3). bottom), we reach within 3 perplexity with ~ 16x reduction in parameters and within 13 perplexity with 80x reduction, outperforming the frequency and hashing baselines. We observe that ANT's improvement over post-compression methods (POST-SPARE HASH) is larger on WikiText than PTB, suggesting that ANT is particularly suitable for large vocabularies.
From T (botto))
4.3
RECOMMENDER SYSTEMS
Setup: We perform experiments on both movie and product recommendation tasks. For movie recommendations, we follow Ginart et al. (2019) and we experiment on Movielens 25M (Harper & Konstan| 2015) with 126K users and 59K movies. We also present results for Movielenns 1M Appendix K. On product recommendation, we show that ANT scales to Amazon Product reviews (Ni et al. 2019). the largest existing dataset for recommender systems with 233M reviews spanning 43.5M users and 15.2M products. Following Wan al. (020), we ensured that the users and products in the test set have appeared in the training data for generalization.
Baselines: We compare
baseline Matrix Factorization (MF) model (Koren et al.] (209)) with full embedding matri- for movies and users and to Mixed Dimension (MIxDIM) embeddings (Ginart et al. 2019). a compression technique that assigns different dimension to different users/items based on popularity. We also compare to SPARSE CBOW (Sun et al.
ANT
80
NBANT
Equation
75
2016) which learns sparse E by placing E penalty over all entries of E and optimizing using online subgradient descent, and SLIMMING (Liu et al. 2017). which performs subgradi- ent descent before pruning small weights by setting them to 0. Such methods learn embeddings for objects independently without statistical strength sharing among related objects. We also test NEANT using the algorithm derived from the Bayesian nonparametric interpretation of ANT.
70
10"
10
10a
10
Number of anchors
Figure 3: NBANT accurately selects the optimal |A] minimize eq (5), thereby achieving a balance between perfor- mance and compression.
Results: From T ANT outperforms standard matrix factorization and dense mixed dimensional embeddings for performance and compression. NBANT is also able to automatically select optimal
7

---

Published as a conference paper at ICLR 2021
Table 3: On Movielens 25M, ANT outperforms MF and mixed dimensional embeddings. NBANT automatically tunes [4| (" denotes |A] discovered by NBANT) to achieve a halance between performance and compression.
Method
user A
item A
Init A
MSE
Emb (M)
MF (Koren et al.
2009)
162K
59K
All
0.665
3.55
MIXDIM Ginart el al.
2019
162K
59K
All
0.662
0.89
SPARSE CBOW (Sun et al.
2016
162K
59K
Random (A = 1 10 9)
0.695
2.44
SPARSE CBOW (Sun ct al.
2016
162K
59K
Random (A = 2 10-b)
0.757
1.45
SLIMMING (Liu 2017
162K
59K
Random (A 2 10
0.735
1.89
SLIMMING Jiu al.
2017)
5
5
Random (A = 2 10
0.656
0.97
10
15
Random (A2 = =2 10
0.617
1.76
ANT
5
5
Random (A2 22 10
0.651
0.89
Auto + 8" Auto + 8" Random (A1 = A2 2 10
0.637
1.29
NBANT
Auto Auto
Random (A1 0.01, = 2 10 "
0.649
1.09
Table 4: ANT scales to Amazon Product reviews, the largest existing dataset for recommender systems with 233M reviews spanning 43.5M users and 15.2M products, and is able to perform well under compression.
Data Method
user A item [A]
Init A
MSE
# Emb (M)
MF (d 10. Wan et al. 2020
9.84M
0.76M
All
1.590
105
Electronics
MF
9.84M
0.76M
All
1.524
170
20
8
Random (A2 = x 10"
1.422
25.8
ANT
8
3
Random (A2 = 1 10
1.529
7.10
Random (A2 = 10
1.591
3.89
MF
43.5M
15.2M
All
1.164
939
All
15
10
Random (A2 = 1 10-3)
1.099
201
ANT
8
8
Random (A2 = 1 10
1.167
95.9
number of anchors (6/8) to achieve solutions along the performaace-cooprrssiirr Pareto front. In
Figure 3 we plot the value of eq (5) across values of |A| after comprehensive hyperparameter sweep on ANT across 1000 settings. In comparison, NBANT optimizes |A| and reaches a good value of eq (5) in single run without having to tune |A| as hyperparameter, thereby achieving best balance between performance and compression. Please refer to Appendix K.3 for more results and discussion on NBANT.
For product recommendation, we first experiment on commonly used subset of the data, Amazon Electronics (with 9.84M users and 0.76M products), to ensure that our results match published baselines (Wan al.) 2020), before scaling our experiment to the entire dataset. From Table 4 we find that ANT compresses embeddings by 25x on Amazon Electronics while maintaining performance, and 10x the full Amazon reviews dataset.
Online NEANT: Since NBANT automatically grows/contracts |A] during training, we can further extend NBANT to online version that sees stream of batches without revisiting previous ones (Bryant& & Sudderth 2012). We treat each batch as a new set of data coming and train on that batch until convergence, modify |A] as in Algorithm 2 before moving onto the next batch. In this significantly more challenging online setting, NBANT's is still able to learn well and achieve a MSE of 01.855 with 1.25M non zero parameters. Interestingly this online version of NBANT settled on a similar range of final user (8) and item (8) anchors as compared the non-online version (see Table 3. which confirms the robustness of NBANT in finding relevant anchors automatically. In Appendix K.3 we discuss more observations around online NBANT including ways of learning [A].
4.4 DISCUSSION AND OBSERVATIONS
Here we list some general observations regarding the importance of various design decisions in ANT:
1) Sparsity is important: Baselines that compress with dense factors (e.g., LR, TT) suffer in performance while using many parameters, while ANT retains performance with better compression.
2) Choice of A: We provide results on more clustering initializations in Appendix D In general, performance is robust w.r.t. choice of A. While frequency and clustering work better, using a dynamic basis also performs well. Thus, it is beneficial to use any extra information about the discrete objects (e.g., e.g.. domain knowledge having good representation space like Glo Ve perform clustering).
8

---

Published as a conference paper at ICLR 2021
Table 5: Word association results after training language models with ANT on the word-level PTB dataset. Left: the non-anchor words most induced by a given anchor word. Right: the largest (non-anchor, anchor) entries learnt in T after sparse & f--regularization. Bottom: movie clusters obtained by sorting movies with the highest coefficients with each anchor embedding.
Largest word pains trading, brokerage stock, junk year, summer
york, angeles
Anchor words
Non-anchor words
year, month government, administration
year
august, night, week, month, monday, summer, spring bonds, certificates, deht, notes, securities, morigages
stock
Movies
Genre
God's Not Dead, Sex and the City, Sex and the City 2, The Twilight Saga: Breaking Dawn- Part I, The Princess Diaries 2: Royal Engagement, The Last Song, Legally Blonde 2: Red, White & Blonde, The Twilight Saga: Eclipse, Maid in Manhattan, The Twilight Saga: Breaking Dawn Part 2 Nostalghia, Last Days, Chimes at Midnight, Lessons of Darkness, Sonatine, Band of Outsiders, Gerry, Cyclo, Mishima: A Life in Four Chapters, George Washington
romance, comedy
drama,
indie
3) Anchors and sparse transformations learned: We visualize the important transformations (large entries) learned between anchors and non-anchors in Table Left, we show the most associated non-anchors for a given anchor word and find that the induced non-anchors are highly plausible: stock accurately contributes to bonds, certificates, securities, and so on. Right, we show the largest (non-anchor, anchor) pairs learned, where we find related concepts such as (billion, trillion) and (goverument, administration). On MovieLens, for each anchor, we sort the movies according to the magnitude of their transformation coefficients which automatically discovers movie clusters based on underlying genres. We obtain a genre purity ratio of 61.7% by comparing automatically discovered movie clusters with the true genre tags provided in MovieLens.
4) Zero transformations learned:
For MovieLens, we find that ANT assigns 2673 out of 59047 movies to an entire zero row, of which 84% only had 1 rating (i.e., very rare movies). Therefore, compression automatically discovers very rare objects (1 labeled point). On WikiText-103, rare words (e.g., Anarky, Perl, Voorhis, Gaudi, Lat, Bottomley, Nescopeck) are also automatically assigned zero rows when performing high compression (54.2 ppl with 0.4M params). Certain rare words that might be predictive, however, are assigned non-zero rows in T, such as: sociologists, deadlines, indestructible, causeways, outsourced, glacially, heartening, unchallenging, roughest.
5) Choice of A2; Tuning Å allows us to perform model selection by controlling the trade-off between |A] (model complexity) and performance. By applying eq (5) on our trained models in Table 2 choosing a small A 2 x 10 prefers more anchors ((A) = 1, 000) and better performance (ppl 79.4), while larger X 1 10 selects fewer anchors (IA| 100) with compromise
in performance (ppl- = 106.6). Tuning 22 allows us to control the tradeoff between sparsity and
performance (see details in Appendix L
6) Convergence: In Figure 4 we plot the empirical conver- gence of validation loss across epochs. ANT converges as fast as the (non-sparse) MF baseline, and faster than compression baselines MixDim (Ginart et al.] 2019) and Sparse CBOW (Sun) et al. 2016). ANT also converges to the best validation loss.
1.1
MF
1.0
MixDim
validation MSE
Sparse CBOW
0.9
ANT
7) Scalability: In addition to fast convergence, ANT also works effectively on large datasets such as Movielens 25M (162K users, 59K movies, 25M examples) and WikiText-1033 (267K unique words, 103M tokens). For each epoch on Movielens 25M, standard MF takes 165s on a GTX 980 Ti GPU while ANT takes 176s for |A| 5 and 180s for |A| 20. ANT also scales to the largest recommendation dataset, Amazon reviews, with 25M users and 9M products.
0.7
0.6
10
30
40
50
num epochs
Figure 4: ANT converges faster and to a better validation loss than the basclines.
CONCLUSION
This paper presented ANCHOR & TRANSFORM to learn sparse embeddings of large vocabularies using a small set of anchor embeddings and sparse transformation from anchors all objects. We also showed a statistical interpretation via integrating IBP priors with neural representation learning. Asymptotic analysis of the likelihood using SVA yields extension that automatically learns the optimal number of anchors. On text classification, language modeling, and recommender systems, ANT outperforms existing approaches with respect to accuracy and sparsity.

---

Published as a conference paper at ICLR 2021
REFERENCES
Anish Acharya, Rahul Goel, Angeliki Metallinou, and Inderjit Dhillon. Online embedding compression for text classification using low rank matrix factorization. Proceedings of the AAAI Conference on Artificial Intelligence, 33:6196 1966669666 6203, 07 2019. doi: 10.1 w..16609aaiivv33300 333.3.33110.0003311661666 .33016196.
M. Aharon, M. Flad, and A. Bruckstein. K-svd: An algorithm for designing overcomplete dictionaries for sparse representation. Trans. Sig. Proc., 54(1 (4(11))4311 1-422,, November 2006. ISSN 1053-587X.
Sajid Anwar, Kyuyeon Hwang, and Wonyong Sung. Structured pruning of deep convolutional neural networks.
Emerg. Technol. Comput. Syst. 13(3). February 2017. ISSN 1550-4832. doi: 10.1 10/1144/300 URL
https: erg/ 10. 11 /141//300550 3005348
David Arthur and Sergei Vassilvitskii. K-means++: the advantages of careful seeding. In In Proceedings of the 18th Annual ACM SIAM Symposium on Discrete Algoritimms 2007.
Ben Athiwaratkun, Andrew Wilson, and Anima Anandkumar. Probabilistic FastText for multi-sense word embeddings. ACL, pp. 1-11, Melbourne, Australia, July 2018. Association for Computational Linguistics.
P. Awasthi and A. Vijayaraghavan. Towards learning sparsely used dictionaries with arbitrary supports. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), Oct 2018.
Olivier Bachem, Mario Lucic, and Andreas Krause. Coresets for nonparametric estimation the case of dp- means. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 209-217, Lille, France, 07-09 Jul 2015. PMLR. URL URL htt.t:::pppooceeddngge mi wwwpspresssse........p /v3/ /acc///aaaemmml 5. html
Olivier Bachem, Mario Lucic, and Andreas Krause. Practical coresct constructions for machine learning. 2017.
Alexci Baevski and Michael Auli. Adaptive input representations for neural language modeling. In Interna- tional Conference on Leurning Representutions. 2019. URL https://openzeviiee net met//foummt id=
Byx2X20qE Q
Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon, and Joydeep Ghosh. Clustering with bregman diver- gences. J. Mach. Learn. Res., 6:17 December 2005. ISSN 1532-4435.
Amir Beck and Marc Teboulle. A fast iterative shrinkage-ttressoolding algorithm for linear inverse problems. SIAM J. Img. Sci., 2(1):183 202, March 2009. ISSN 1936-4954, doi: 10.1 10/0007.00771644. URL http
//dx. d/x.ioi.... doi. orgg (.....117/0001100
Y. Bengio and J. S. Senecal. Adaptive importance sampling to accelerate training of a neural probabilistic language model. Trans. Neur. Netw., 19(4):713-72, April 2008. ISSN 1045-9227.
Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. Enriching word vectors with subword information. Transactions of the Association for Computational Linguistics, 5: 5:165-146, 2017. doi: 10.1162.
mec__a_00051, htR.:ttts://///
www.. acl web org/ aothoooogo/11111000000
L.M. Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, USSR Computational Mathematies and Mathematical Physics, 7(3):200 217, 1967. ISSN 004 15553. doi: https://doi.org org/11. wew.////...../////....1 (01660041-5553677990000
Tamara Broderick, Brian Kulis, and Michael Jordan. Mad-bayes: Map-based asymptotic derivations from bayes. In Sanjoy Dasgupta and David McAllester (eds.), ICML, Proceedings of Machine Learning Research, pp. 226 234, Atlanta, Georgia, USA, 17-19 Jun 2013a. PMLR
Tamara Broderick, Jim Pitman, Michael I Jordan, et al. Feature allocations, probability functions, and paintboxes. Bayesian Analyvis, 8(4):801-836, 2013b.
Michael Bryant and Erik Sudderth. Truly nonparametric online variational inference for hierarchical dirichlet processes. Advances in Neural Information Processing Systems, 25:2699 2012.
Ting Chen, Martin Renqiang Min, and Yizhou Sun. Learning k- k-way d-dimensional discrete codes for compact embedding representations. In Jennifer Dy and Andreas Krause (cds.), Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pp. 853-863, PMIR,, 10-15 Jul 2018. http /ttpcceedpppo//eiiiieeeoo ngs. m1 press/ / vv00
c/0//cen11 chen 8g. hhmll
Wenhu Chen, Yu Su, Yilin Shen, Zhiyu Chen, Xifeng Yan, and William Yang Wang. How large a vocabulary does text classification need? a variational approach to vocabulary selection. In Proceedings of the 2019 Conference the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), 2019.
10

---

Published as a conference paper at ICLR 2021
Wenlin Chen, James T. Wilson, Stephen Tyree. Kilian Q. Weinberger, and Yixin Chen. Compressing neural networks with the hashing trick. Proceedings of the 32nd International Conference on Machine Learning- Volume 37, ICML'11, 15. pp. 2285-2294, JMgR. 2015.
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), Association for Computational Linguisties, 2016a.
Yunchuan Chen, Lili Mou, Yan Xu, Ge Li, and Zhi Jin. Compressing neural language models by sparse word representations. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 226 235, Berlin, Germany, August 2016b. Association for Computational Linguistics.
Nadezhda Chirkova, Ekaterina Lobacheva, and Dmitry Vetrov. Bayesian compression for natural language processing. In Proceedings of the 2018 Conference on Empirical Methods Natural Language Processing, pp. 2910-2915, Brussels, Belgium, October-November 2018. Association for Computational Linguistics.
Xin Dong, Shangyu Chen, and Sinno Pan. Learning to prune deep neural networks via layer-wise optimal hrain surgeon. In I. Cuyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus. S. Vishwanathan, and R. Garnett (cds.), Advances in Neural Information Processing Systems 30, pp. 4857-4867, Curran Associates, Inc., 2017.
Z. Ghahramani, P. Sollich, and T. L. Griffiths, P:: Bayesian nonparametric latent feature models. In In: Bayesion Statistics 8. University Press, 2007.
Antonio Ginart, Maxim Naumov, Dheevatsa Mudigere, Jiyan Yang, and James Zou. Mixed dimension beddings with application memory-esficiee recommendation systems. arXiv preprini arXiv:1909.11810 2019.
Artem Grachev, Dmitry I. Ignatov, and Andrey V. Savehenko. Compression of recurrent neural networks for efficient language modeling. CoRR, abs/1902.023800 2019. URL htKKhtttpp///raav.rr/////// 1902
02380
Thomas L. Griffiths and Zoubin Ghahramani. Infinite latent feature models and the indian buffet process. In Proceedings of the 18th International Conference on Neural Information Processing Syxtems, NIPS' 05, pp. 475-482, Cambridge, MA, USA, 2005. MIT Press.
Thomas L. Griffiths and Zoubin Ghahramani. The indian buffet process: An introduction and review. J. Mach. Learn Res., 12(null): 1224, July 2011. ISSN 1532-4435.
Y. Guo, G. Ding. L. Liu, J. Han, and L. Shao. Leaminn hash with optimized anchor embedding for scalable retrieval. IEEE Transactions on Image Processing, 1344-13344 March 2017.
Michael Gutmann and Aapo Hyvarinen. Noise-contrastive estimation: estimation principle for unnormal- ized statistical models. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, 2010.
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.
Sariel Har-Peled and Soham Mazumdar, On corescts for k-means and k-median clustering. In Proceedings of the Thitty-Sixth Annual ACM Symposium on Theory of Computing, STOC '04. Association for Computing Machinery, 2004.
ACM
R. Haralick, K. Shanmugam, and I. Dinstein. Texture features for image classification. IEEE Transactions on Systems, Man, and Cybernetics, 3(6), 1973.
Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5(4), December 2015. ISSN 2160-6455. doi: 10. 14/1222//27777 URRpsttts:////i..oo 10.1145/2827877
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Comput., 98)::7335- November 1997. ISSN 0899-7667. doi: 10.1 10.1162heco.1197....7773
htlhhttp://dx doi. org/00
1162/neco. 1997. 9.8 1733
Ke Jiang, Brian Kulis, and Michael Jordan. Small-variance asymptotics for exponential family dirichlet process mixture models. In Proceedings the 25th International Conference on Neural Information Processing Systems Volume NIPS' 12, pp. 3158-3166, Red Hook, NY, USA, 2012. Curran Associates Inc.
11

---

Published as a conference paper at ICLR 2021
Manas R. Joglekar, Cong Li, Jay K. Adams, Pranav Khaitan, and Quoc Le. Neural imput search for large scale recommendation models. CoRR, abs/ 00471,44111 2019. BRR.Atttp//aax...orrg. httpg///bb//117// 04471
Rafal Jozefowicz, Oriol Vinyals, Mike Schuster, Noam Shazeer, and Yonghui Wu. Exploring the limits of language modeling. arXiv preprint arXiv: 1602.02410 2016.
Yoon Kim. Convolutional neural networks for sentence classification. In Proceedings the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1746-1751, Doha, Qatar, October 2014. Association for Computational Linguistics.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
David Knowles and Zoubin Ghahramani. Nonparametric bayesian sparse factor models with application to gene expression modeling. Ann. Appl. Stat., 5(2B):1534 1552, 06 2011. doi: 111214410-A0A443 URL
sttpss//ddc org/ 10. 1214/ 0-A0A44-5555
Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 32 37, August 2009.
Yann Lecun, Leon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. In Proceedings of the IELE, pp. 2278-2324, 1998.
Jens Lehmann, Robert Isele, Max Jakoh, Anja Jentzsch, Dimitris Kontokostas, Pablo N. Mendes, Sehastian Hellmann, Mohamed Morsey, Patrick van Kleef, Sören Auer, and Christian Bizer. DBpedia large-scale, multilingual knowledge base extracted from wikipedia. Semantic Web Journal, 6(2):167-195, 2015.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snat stanford. www.ddt.t...eeeeee June 2014.
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- 978-1-4673-696440
H. Liu and P. Singh. Conceptnet &mdash; practical commonsense reasoning tool-kit. BT Technology Journal, 22(4):211 (12)2211-226, October 2004. ISSN 1358-3948
Zhuang Liu, Jianguo Li, Zhiqiang Shen, Gao Huang. Shoumeng Yan, and Changshui Zhang. Learning efficient convolutional networks through network slimming. In Proceedings of the IEEE International Conference on Computer Vision, pp. 2736 2744, 2017.
Thang Luong, Hieu Pham, and Christopher Manning. Effective approaches to aitention-based neural machine translation. In Proceedings of the 2015 Conference on Empirical Methods Natural Language Processing, pp. 1412-1421, Lisbon, Portugal, September 2015. Association for Computational Linguistics.
Mitchell Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. Building large annotated corpus of english: The penn treebank. Comput. Linguist. 19(2)313-330, June 1993. ISSN 0891-2017. URI. http::/ali acm. org/ http://aatto..cmmaaa//222222.2.. 99227
Ivan Markovsky, Low Rank Approximation: Algorithms, Implementation, Applications. Springer Publishing Company, Incorporated, 2011. ISBN 1447122267, 9781447122265.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing L.STM language models. In International Conference on Learning Representations, 2018.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems 26. 2013.
George A. Miller, Wordnet: A lexical database for english. Commun. ACM, 38(1))28111)))91111 1):39441, November 1995. ISSN 0001-0782.
Andriy Mnih and Yee Whye Tch. A fast and simple algorithm for training neural probabilistic language models. In Proceedings of the 29th International Conference Machine Learning, ICML'11, pp. 419-426. USA. 2012. Omnipress. ISBN 178-1-5503-1285..0 URL http:/ (LL, acm. org/citation cfm?id= 3042573 3042630
12

---

Published as a conference paper at ICLR 2021
Dai Quoc Nguyen, Dat Quoc Nguyen, Ashutosh Modi, Stefan Thater, and Manfred Pinkal. A mixture model for learning multi-sense word embeddings. Proceedings of the 6th Joint Conference on Lexical and Computational Semantics (*SEM 2017), 2017.
Jianmo Ni. Jiacheng Li, and Julian McAuley. Justifying recommendations using distantly-lbelled reviews and fine-grained aspects. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-JJCNLP), pp. 188-197, 2019.
John Paisley, Aimee Zaas, Christopher W. Woods. Geoffrey S. Ginsburg, and Lawrence Carin. A stick-breaking construction of the beta process. In Proceedings of the 27th International Conference Machine Learning, ICML'10, pp. 447-854, Madison, WI, USA, 2010. Omnipress. ISBN 978 10558897777
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.00 00480, 2016. URL /ttpttp://arxi....// org/ abs/
1608. 01409
Jeffrey Pennington, Richard Socher, and Christopher Manning. Glove: Global vectors for word representation. In EMNLP, October 2014.
Jeff M. Phillips. Coresets and sketches. CoRR, abs/1601.00617,, 2016. URL http::///aaaxi abs/ 601 006617
Ofir Press and Lior Wolf. Using the output embedding to improve language modcls. In Proceedings of the 15th Conference the European Chapter of the Association for Computational Linguistics: Volume 2, Short Papers, April 2017.
Heng Qi, Wu Liu, and Liang Liu. An efficient deep learning hashing neural network for mobile visual search. 2017. URL
CoRR,
07750
Juan Ramos. Using tf-idf to determine word relevance in document queries, 1999.
Sam Roweis. Em algorithms for pea and spea. In Proceedings of the 1997 Conference Advances in Neural Information Processing Systems 10, NIPS '97, pp. 626-633 632, Cambridge, MA, USA, 1998. MIT Press. ISBN 0262100762.
Jason Roy, Kirsten J. Lum, and Michael J. Daniels. A Bayesian nonparametric approach to marginal structural models for point treatments and continuous or survival outcome. Biostatistics, 2016.
Anirban Roychowdhury. Ke Jiang, and Brian Kulis. Small- variance asymptotics for hidden markov models. In Advances in Neural Information Processing Systems 26. 2013.
Denis Sedov and Zhirong Yang. Word embedding based on low-rank doubly stochastic matrix decomposition. In Long Cheng, Andrew Chi Sing Leung, and Seichhi Ozawa (eds.), Neural Information Processing, pp. 90-100, Cham, 2018. Springer International Publishing. ISBN 778-3-330004182-1
Raphael Shu and Hideki Nakayama. Compressing word embeddings via deep compositional code learning. In International Conference on Learning Representations, 2018
Fei Sun, Jiafeng Guo, Yanyan Lan, Jun Xu, and Xueqi Cheng. Sparse word embeddings using 11 regularized online learning. In Proceedings of the Twenty- International Joint Conference on Artificial Intelligence, pp. 2915-2921. AAAI Press, 2016.
Dan Svenstrup. Jonas Meinertz Hansen, and Ole Winther. Hash embeddings for efficient word representations. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 4935 4953, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 1781510860944.
Yee Whye Teh and Michael Jordan. Hierarchical Bayesian nonparametric models with applications, pp- 158-207. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2010. doi: 10. 10110//89997805 18004788.000 006.
Yee Whye Teh, Kenichi Kurihara, and Max Welling. Collapsed variational inference for hdp. Proceedings of the 20th International Conference on Neural Information Processing Systems, 2007.
Ashish Vaswani, Noam Shazeen, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems 30. 2017.
Mengting Wan, Jianmo Ni, Rishabh Misra, and Julian McAuley. Addressing marketing bias in product recommendations. In Proceedings of the 13th International Conference on Web Search and Data Mining, pp. 618-626, 2020.
13

---

Published as a conference paper at ICLR 2021
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. In Advances in Neural Information Processing Systems 29, 2016.
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoe V. Lec 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 's neural machine translation system: Bridging the gap between human and machine translation. CoRR, htss//69..00 144, 2016.
Manzil Zahcer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In Advances in neural information processing systems, pp. 9793-980S, 2018.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character- convolutional networks text classification, Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 1, NIPS' 15, 2015.
14

---

Published as a conference paper at ICLR 2021
APPENDIX
A INDIAN BUFFET PROCESS WITH TWO PARAMETERS
In this section provide more detailed treatment of the Indian Buffet Process (IBP) (Grifhtths & 2011 Paisley et al. 2010) as well its two-parameter generalization (Ghahramani et a 2007). We begin with describing the single parameter version, which essentially defines probability distribution over sparse binary matrices with finite number of rows and an unbounded number of columns. Under IBP prior with hyperparameter a, to generate such a sparse binary random matrix Z with [V] rows, we have the following process:
Ghahramani 2005
Vy Beta(a, 1)
k
by I b J-1
24k ~ (ernoulli(bs), 1= 1..... |V
can be shown from this construction that a given matrix will have non-zen on-zerro probability under the IBP prior if and only if the number of columns containing non-zen entries is finite, albeit a random quantity (Griffiths & Ghahramani 2005). Also note that by keeps diminishing as Uj < 1, thus most Zik will be 0, thereby giving rise to the desired sparsity. Moreover, it can be shown that number of number of non-empty columns would be O(log [V) in expectation.
Like most Bayesian nonparametric models, it is hest understood with an analogy. Consider of a set of customers (objects) queued up to take dishes (features/anchors) from a buffet arranged in line. The first customer starts at beginning of the buffet and takes a serving of all of the first Poisson(a (a) dishes. The remaining customers are more picky. The ith customer samples dishes in proportion to their popularity (i.e., with probability mz)i), where my is the number of previous customers who have sampled a dish. Having reached the end of all previous sampled dishes, the ith customer then tries Poisson a/i) new dishes. The result of this process for the entire vocabulary V is binary matrix Z with [V] rows and infinitely many columns where 2μz= 1 if the ith customer sampled the keth dish.
Using either description of the IBP, we can find the distribution of the sparse binary matrix Z with V rows and K non-empty columns to be given by (Griffiths & Ghahramani 2005 Broderick et al. 2013b):
K
exp(-aHlv)) II ma)(mm= 1)!
K. ((V)
P()) TiM KP!
[V]
k=1
where my denotes number of customers (objects) who selected dish (anchor) k, Hl is the |V|-th Harmonic number Hıv = Σ} J. and K₁, is the number of occurrences of the non-zero binary vector among the columns in Z.
However, the number of features per object and the total number of features are directly coupled through the single parameter a. The two wvo-parameter generalization of the IBP allows one to inde- pendently tune the average number of features for each object and the overall number of features used across all V objects (Ghahramani et al. 2007 particular, we now have an additional hyper- parameter b along with The first customer, as before, samples Poisson(a) dishes. However, the i-th customer now samples in proportion to their popularity with probability mş/(i- + b). where mg is the number of previous customers who have sampled a dish. Having reached the end of all previously sampled dishes, the ith customer tries Poisson (ab/(i+ (i+ b)) new dishes. The parameter is introduced in such a way as to preserve the expected number of features per object to be still a, but the expected overall number of features is now O(ab log [V).. The total number of features used thus increases as b increases, thus providing more control on sparsity of Z. This two parameter IBP prior for a binary matrices Z with [V] rows and K non-empty columns is given by:
(ab)K K
K.
('(m))((V -m 6)
p( ())=
exp(-abHlv)
II A=1
2 K₂!
T((V++b)
where my denotes number of customers (objects) who selected dish (anchor) i and Hiv = Σ 2j=1 b+j-1' This distribution is suitable for use as a prior for Z in models that represent objects using sparse but potentially infinite array of features.
Historically, IBP has been used as a prior in latent feature models, where the binary entries 2₁ of random matrix encode whether feature & is used explain observation i. The IBP can be further
15

---

Published as a conference paper at ICLR 2021
combined with simple observation model p 2g... 8) from the exponential family like the Gaussian distribution (see e.g. Griffiths & Ghahramani (201T). The complexity of inference, using MCMC or variational methods, for such binary factor analysis models has limited the adoption of more complicated observation models. In this work, we break this barrier and, the best of our knowledge, are the first to integrate IBP with deep representation learning of discrete objects by employing an efficient SVA based inference. Thus, our approach combines the representation capabilities of neural networks with desirable sparsity properties.
B DERIVATION OF OBJECTIVE FUNCTION VIA SVA
In this section derive our objective function using Small Variance Asymptotics (SVA) (Jiang et al. 2012). Recall that the generative process in our model is given by:
Z x (a, b)
A A P(A)= ()
W RiVK P(W) Exponential(1)
for = I..,.N
-i fo (Zo W)
p(ylar;; Z, W, exp (-Ds 9:)3 by (v:)
The joint log likelhoodh under our generative model above is therefore:
logp(Y, Z, W.
Σ log Z. W. A) + log log W) log A)
= - fa (Z W) log (3:) log pZ) log (W) + logp(A).
(10)
To use SVA, an approximate objective function for finding point estimates is obtained by taking the limit of the emission probability variances down to zero. We begin by introducing scaling variable B and shrinking the variance the emission probability by taking 3 + oo. The scaled probability emission becomes
p(n Z, W, A) exp (-3Da D() (v)
(11)
Following Broderick et al. 2a). modulate the number of features in the large-8 limit by choosing constants A A2 > and setting the IBP hyperparameters with as follows:
exp(-3X1)
exp(322)
(12)
This prevents limiting objective function that favors trivial cluster assignment (every data point assigned its own separate feature).
We now take the limit of the log-likelihood term by term:
lim logo(> A, W, Z() 8-000
(13)
lim logp(ui/o, Z. W, A) lim logr(Z)= lim 1 f000 B
1 log p( A).
log W) lim
8
8-00
B
8000
B
(14)
lim
logp(y Z, W,WA A)
limg- (-3D (3), 9.) log (3:))
=-D (vi, (i) O(1).
lim log =-X2 Z - (h1 A2) K, see box below.
lim log () =0, if W 0 else -00.
limg-
log as logp (A) A) 0(1).
16

---

Published as a conference paper at ICLR 2021
For convenience, we re-write the limit of the IBP prior as
1 lim logp( (.) lim 8-000
(ab)
log
9
3
3 7 K
+
lim
logexp (aap((abHH)
8
(15)
K
I [(m;) [ my b)
log
B
T([V+ +b)
For part @):
(ab) K
exp(-3(A1 - K)
lim
log
lim g
log
8000
B
h
Kn.
B
1 21 Kn
1
(16)
lim
-B(1i - -22) - lim 0(1)
9-
90000 B
= (A1 - A
For part (D):
lim 1 x -abHIv IM
lim log exp(-abHly)
8000
80000
B
exp( -3(11-((1-11 - K)
(17)
lim 80000
exp (Bx +
For part C
((m=))(()) m2 +
1 mc
lim
log
lim 3
log [mm))
lim
Σ
log([V|-3 -j +b
f000 3
T([[++) +
B
me
log((V] -j exp(312)) (A22))
0
Σ
lim
1=1
3
(18)
mg Σ
A2
j-1
-
We know that my is the number of objects which uses anchor & which counts the number of non-zero entries the k-th column Z. When we sum over all k. just becomes the number of non-zero entries in Z, which is equivalent to the Lo norm of Z, i.e. |||o.
Therefore, the MAP estimate under SVA as given by
max lim Bo
logp(Y,A, W,
(19)
equivalent optimizing the following objective function:
max Ze0,1
-Dohhh fola;, w)A)) 12 -A1- A2)
(20)
W20
A.B.K
where the exponential prior for W resulted in a limiting domain for W to be positive. Note that we combine the optimizing variables Z and W with their constraints into one variable T 0. Also
17

---

Published as a conference paper at ICLR 2021
can switch from maximization problem to minimization problem by absorbing the negative sign. Finally we arrive at the desired objective:
min
Σ (Ju, fo (zi, TA)) X2 TT/TT + (A1 - K.
(21)
Tz0
A,8,K
C EXPONENTIAL FAMILY DISTRIBUTIONS AS BREGMAN DIVERGENCES
In this section provide some results that relate exponential families distributions and Bregman divergences. As a result, we can relate likelihood models from Sec. 3.2 to appropriate Bregman divergences. Thus, probabilistic observation model can be translated to a loss functions minimizing the Bregman divergence, which are more amenable to deep network training using gradient based methods. We begin by defining the Bregman divergence below and stating the relationship formally in Theorem
Definition 1. (Bregman 1967| d R, S dom( be strictly convex function defined on convex set S c RRd such that Φi is differentiable on ri(S), assumed to be non-emply. The Bregman divergence DØ S ri(S) [0, oo) is defined as
y) = 0xx) - <(y) vx
(22)
where v Vo(y) represents the gradient vector of ④ evaluated y.
Theorem 1. (Banerjee et al.) 2005) There is bijection between regular exponential families and regular Bregman divergences. In particular, for any exponential family distribution p(x(0)) po(x) exp( (xx, 0) g(0)) can be written as p(x|p) exp( (x, 41 (x((x where & is the Legen-
dre dual of the log- log-partition function g()) and l Veg 0
From Theorem I we can see that maximizing lig-likeldhood log px((( is same as minimizing the Bregman divergence Dx μ)) Note that we can ignore (x) as it depends only on observed data and does not depend on any parameters. We now illustrate some common examples of exponential families (like Gaussian and categorical), derive their corresponding Bregman divergences, and connect to usual loss functions used in deep networks (like MSE and cross-entropy).
Example 1: Gaussian distribution. (Banerjee al., 2005) We start with the unit variance spherical Gaussian distributions with with mean μu, which have densities the form:
p(); ((2m)d exp (-2 [ m13)
(23)
Using the log-partition function for Gaussian distribution, we can calculate that (xx) } _||a=11 which yields Bregman divergence equal to:
Dz(x, 1)= d(x) ((1)) (x 14, Vo()))
(24)
1
2 xx|2= :11111 (x m.
(25)
2
2 |x - 11122
(26)
mean squared error
Thus, Dx(x, 11) along with constant by (x) given by
bs (x) = v(
(27)
recovers the Gaussian density p(x)= exp(-Dx(>> (x). Therefore, when we assume that labels
have a Gaussian emmission model, the corresponding Bregman divergence Dø 11) recovers the squared loss commonly used for regression.
+|x |
Example 2: Multinomial distribution. (Banerjee et al. 2005 Another exponential family that is widely used is the family of multinomial distributions:
N
p(x 9)
1
(28)
IT xzg j=1
where 2y E z are frequencies of events, Σj= 22 = N and qj 2 0 are probabilities of events, Σ Øj 1. The multinomial density be expressed the density of exponential distribution
18

---

Published as a conference paper at ICLR 2021
d-1
in x= ( with natural parameter 0 log
1
cumulant function g(0) -N log qd. and
qa
j-1
expectation parameter μ Vg(()) = [No, 1 The Legendre dual Φ of g is given by
<(v)= = =
log
N
4 log
(29)
As a result, the multinomial density can be expressed as a Bregman divergence equal to:
Dx u)
Σ
2 log 2,
Σ
log
(30)
j-1
cross-entropy
and constant (x) given by
2j 1-1 2
N
(x(x)=
(31)
N
which recovers the multinomial density pxx) exp( Do S (x. u1 (x).. Therefore, when the labels are generated from a multinomial distribution, the corresponding Bregman divergence (x(x, 14)
j-1 Ty log + constant recovers the cross-entropy loss commonly used for classification.
D 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, it would be interesting 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 as proxy for the full data set, with provable guarantees such that the same algorithm on the coreset and the full data set gives approximately similar results (Phillips) 2016 Har-Peled & Mazumdar, (004). 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 trade-off between how quickly we can choose the anchor objects and their performance. Randomly picking anchor objects (which equivalent to initializing the anchor em- beddings with dynamic basis vectors) becomes similar to learning a low-rank factorization of the embedding matrix (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-oocurren information works well while ensuring that the preprocessing and training stages relatively quick.
In Appendix K we provide more results for different initialization strategies including those based on clustering initralizations. 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 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.
E TRANSFORM: LEARNING A SPARSE T
In addition to simple sparse linear transformation, we describe some extensions that improve sparsity and expressitivity of the learned representations.
Reducing redundancy in representations: To further reduce redundancy in our sparse represen- tations, we perform orthogonal regularization of dynamic basis vectors A by adding the loss term
19

---

Published as a conference paper at ICLR 2021
AA
freq ennyy cuaterig beas
softmax(
XM
M
M
Figure 5: Generalized nonlinear mixture of anchors At,... AM and transformations Ti. TM, E IM softmax ( (T )m (softmax across rows of Tm). Different sparse transformations can be learned for different initializations of anchor embeddings.
((A) = Eiz) a ayl to the loss function in eq 11 This ensures that different basis vectors and aj are orthogonal instead of being linear combinations of one another which would lead redundancies across different learnt entries in T.
Míxture of anchors: In general, different initialization strategies may bring about different advan- lages. For example, using a mixture of random basis vectors has been shown to help model multisense embeddings (Athiwaratkun al. 2018 Nguyen al., 2017). One can define a set of M anchor embeddings AI,..., Am each initialized by different strategies and of possibly different sizes.
Nonlinear mixture of transformationss To complement learning multiple sets of anchor embed- dings A,..,, AM.....M.. the straightforward extension the TRANSFORM step would be to learn a separate linear transformation for each anchor embedding and summing the result: E Em-= Tm Am However, the expressive power of this linear combination is equivalent to set of anchor embeddings equal to concatenating A and one linear transformation. To truly exhibit the advantage of multiple anchors, transform and combine them in nonlinear fashion, e.g.. E -EM softmax AT,) (softmax over the rows of Tm. Figure 5). Different transformations can be learned for different initializations of anchors. This is connected with the multi-head attention mechanism in the Transformer (Vaswani al. 2017). where softmax (T are the softmax-activated (sparse) attention weights and A. the values to attend over. The result is an embedding matrix formed via nonlinear mixture of anchors (each initialized with different strategies) and sparse transformations.
F INCORPORATING DOMAIN KNOWLEDGE
ANT also allows incorporating domain knowledge about object relationships. Suppose we are given some relationship graph G (V, E) where each object vertex V and an edge (u, v) e 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) for semantic relations between words,
2) word co-occurrence matrices (Haralick et al. 1973). and 3) Movic Clustering datasets (Leskoved & Krevi 2014). From these graphs, we extract related positive pairs P = {(u, v) F} and unrelated negative pairs N {(u, r) & F). We incorporate domain information as follows (see Figure 6 for
visual example):
To incorporate a positive pair (u, v),, we do not enforce sparsity on Tu. This allows ANT to freely Iearn the transformation between related objects and without being penalized for sparsity. On the other hand, transformations between negative pairs will be sparsely penalized. In other words, before computing the é --enallyy we element-wise multiply T with a domain sparsity matrix S(G) where S(G),,. u., for (u, v) E (entries not é penallized) and S(G)... n,, otherwise (entries are (-peeallizdd), resulting in the following modified objective:
Positive pairs:
min Ts0. 0,O Do fe(x,, TA)) + A2 T S(G)
(32)
Since we perform proximal GD, this is equivalent to only soft-thresholding the entries between unrelated objects, i.c., T= max ((T-
- m)A2) ) o S(G)= T o LLG()))), (G))),); 0}. Note that this strategy is applicable when anchors are selected using the frequency method.
Negative pairs: For 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,
20

---

Published as a conference paper at ICLR 2021
bird
Positive pairs P
(bird, canary)
(animal, bird)
abooe
(deep, learning)
M
WordNet
(food, table) (star wars, trek)
canary
don't penalize this entry!
[A]
Negative pairs N
co-occurrence
(enimal, bank)
(food, learning)
M
animal
(table, california) (tuesday, dollar) (star wars, love actually)
these rows should be unrelated!
bank
movie clusters
JAI
Figure 6: Incorporating domain knowledge into ANT given object relationship graphs (left) with extracted positive pairs P and negative pairs N. Transformations between negative (unrelated) pairs sparsely é penalized while those between positive (related) pairs are not. The linear transformation coefficicnts t, and t. of negative pairs (u, u) are also discouraged from sharing similar entries.
add the loss term
C(T,N) =
Ettul Ityl (u.F)EN
(33)
to the loss eq [ where each inner sum discourages fu and t, from sharing similar entries. This strategy can used regardless of the way anchors are selected. We acknowledge that there are other ways to incorporate domain knowledge as well into the general ANT framework, and we only serve to give some initial examples of such methods.
G NONPARAMETRIC ANCHOR & TRANSFORM
In this section we provide details for our non-parametric extension of ANT. Recall that our full objective function derived via small variance asymptotics is given by:
min T20
Do fol;;; TA)) Au Tlo (A1 - A2)
(34)
A.
which suggests natural objective function in learning representations that minimize the prediction loss (14,, fe fe(x;: (z,; TA)) while ensuring sparsity of T as measured by the to fo-norm and using as few anchors as possible (K). Therefore. optimizing eq (5) gives rise a nonparametric version of ANT, which we call NBANT, that automatically learns the optimal number of anchors. To perform optimization over the number of anchors, our algorithm starts with a small initial number of anchors K -A|A|-= 10 and either adds AK K anchors (i.e., adding A new rows to A and A new sparse columns T) or deletes AK anchors minimize eq (34) every epoch depending the trend of the objective evaluated on the training set. We detail the full Algorithm 2 and highlight the main changes as compared to ANT.
Practically, this algorithm involves the same number of training epochs and batches through each training epoch as the vanilla ANT method. To enable sharing of trained anchors, we change the indices from where and are read from so that the partially trained removed anchors are still stored in case more anchors need to be added again.
H EFFICIENT LEARNING AND INFERENCE
The naive method for learning E from anchor embeddings A and the sparse transformations T still scales linearly with [V] d. Here we describe some tips on how to perform efficient learning and inference of the anchor embeddings A and the sparse transformations T:
Store as sparse matrix by only storing its non-zero entries and indices. From our experiments, we have shown that nT) << [V] x d which makes storage efficient. For inference, use sparse matrix multiply supported in TensorFlow and PyTorch to compute E = TA (or its non-linear extensions). This decreases the running time from scaling by [V| d to only scaling function of nnz( T). For training, using inbuilt sparse
21

---

Published as a conference paper at ICLR 2021
Algorithm 2 NBANT: Nonparametric Bayesian ANT. Differences from ANT are highlighted in red.
ANCHOR & TRANSFORM:
1: Anchor: initialize initial K = |A| and corresponding anchor embeddings IR Kxd
2: Transform: initialize
BR as a sparse matrix.
3: for each each epoch do
4: for each batch (X, Y) do
5: Compute loss L = Σ, Do (o TA))
6: 0, UPDATE (V..n).
7:
T max [ - 7222 0}.
8:
end for
9:
Compute eq (34 using current value of K,A, A, T on the validation set.
10:
if eq 34 is decreasing trend then
11:
K = K + K, add A rows to A and A K (sparse) columns to T.
12:
else if eq 34 is an increasing trend then
13:
K K
K, remove A rows from A and AK (sparse) columns from T.
14: else
15: keep current values of K, A,
16:
end if
17:
end for
18:
return anchor embeddings A and transformations T.
representation of most deep learning frameworks like PyTorch or Tensorflow is not optimal, as they do not support changing non-zero locations in sparse matrix and apriori its not easy to find optimal set of non-zero locations.
During training. instead, implicitly construct E from anchors and transformations. In fact, we can do better: instead of constructing the entire E matrix to embed a single datapoint x R IIM] matrix multiplication with A, i.e., (xT) A xd We are essentially taking advantage of the associative property of matrix multiplication and the fact that xT is simple indexing step and (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 as well due to the 1.1-prox operator.
we can instead first index x into T, i.c., xT e IR 1x|A|] before performing a sparse
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. 2013) or noise-contrastive estimation (Gutmann & Hyvarimen 2010; Mnih & Teh 2012). which will be anyway used for large vocabulary sizes. To elaborate, consider the case of sampled softmax (Bengio & Senecal 20088. We normally generate the negative sample indices, and then we can first index into T using the true and negative indices before performing sparse matrix multiplication with A. This way we do not have to instantiate entire E by expensive matrix multiplication.
When training is completed, only store the non-zero entries of T or store T as a sparse matrix to reconstruct E for inference.
To save time when initializing the anchor embeddings and incorporating domain knowledge, precompute the necessary statistics such as frequency statistics, co-occurrence statistics, and object relation statistics. We use a small context size of 10 to measure co- co-occurrence two words to save time. When using WordNet to discover word relations, we only search for immediate relations between words instead of propagating relations across multiple steps (although this could further improve performance).
In order to incorporate domain knowledge in the sparsity structure, we again store 1 S(G) using sparse matrices. Recall that S(G) has an entry equal to 1 for entries representing unrelated objects that should be f--penalized, which makes S(G) quite dense since most anchor and non-anchor objects are unrelated. Hence we store 1-S(G) instead which consists few non-zero entries only at (non-anchor, anchor) entries for related objects. Element-wise multiplications are also replaced by sparse element-wiss wise multiplications when computing T o S(G) and T @ (1-SSc S(G)).
22

---

Published as a conference paper at ICLR 2021
Table Table of hhperpaaaaeeeers for classification experiments AG-News, DBPedia. Sogou-News, and Yelp-review datasets. All text classification experiments use the same hase CNN model with the exception of different output dimensions (classes in dataset): AG-News, for DBPedia, Sogou-News, and for Yelp-review.
Model
Parameter
Value
Embedding 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
entropy
CNN
Dropout
0.5
Batch size
256
Max seq length
100
Num epochs
200
Activation
ReI.U
Optimizer
Adam
Learning rate
5 x 10
Learning rate decay
1 10
Start decay
40
Finally, even if want is possible without blowing up memory requirements. In particular, let e R |x|V| be the incoming gradient from cross-entropy loss and h R be the vector coming from layers below, like LSTM. The gradient update then
ANT framework with full softmax in language model, it
T ,ROX, (T 7g( (Ah())
(35)
The main issue is computing the huge [V] |A] outer product as intermediate step which will be dense. However, note that incoming gradient g is basically a softmax minus an offset corresponding correct label. This should only have large values for small set of words and small for others. If we carefully apply the fa-prox operator earlier, which is nothing but soft-thres ooftthhresholding, to only calculate much smaller sized outer product and touch a small number of rows in T. Thus, making the approach feasible.
make this incoming gradient sparse very sparse. Thus need
I GENERALITY OF ANT
We show that under certain structural assumptions the anchor embeddings and transformation ma- trices, ANT reduces to the following task-specific methods for learning sparse representations: 1) Fre- quency (Chen et al. 2016b). TF-IDF Group Lasso (Wen et al., 2016), and variational dropout (Chen al. 2019) based vocabulary selection, 2) Low-rank factorization (Grachev et al.) 2019), and 3) Compositional code learning (Shu & Nakayama 2018 Chen et al. (018). Hence, ANT is general and unifies some of the work on sparse representation learning done independently in different research areas.
Frequency-based vocabulary selection (Luong et al.) 2015 Chen et al. 2016b): Initialize A with the |A] most frequent objects and set Ta,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 but not T (i.e., only embeddings for frequent objects are learned). By changing the selection of A, ANT also reduces 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. 2019 Markovsky 2011 Grachev et al. 2019 Initialize
A by mixture of random basis embeddings (just I anchor per set) Ai.....A,
R glxa and do not
enforce any sparsity on the transformations Ti,.., TM E IR! x If we further restrict ourselves to only linear combinations E = ΣM- Tm, Am, this is equivalent to implicitly learning the M low rank factors . aM, f,,... ... ty that reconstruct embedding matrices of rank at most M.
23

---

Published as a conference paper at ICLR 2021
Table 7: Table of hyperparameters for language modeling experiments using LSTM PTB dataset.
Model
Parameter
Value
Embedding dim
200
Num hidden layers
2
Hidden layer size
200
Output dim
10, 000
Loss
cross entropy
Dropout
0.4
Word embedding dropout
Input emhedding dropout
0.4
LSTTM layers dropout
0.25
Weight dropout
0.5
LSTM
Weight decay
1.2 10
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
x 10-5
Start decay
40
2018): Initialize A by a mixture Compositional code learning (hhu & Nakayama, 2018 Chen et al.
of random basis embeddings A A A M. initialize transformations T Ti..... TM. and apply linear combination E = ΣM T m. A For sparsity regularization, set row of S(G) za vector with entry d 0 and all else In other words, index dm; of row row Tm; is not regularized, and all other entries are f rregularized with extremely high X2 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.
one-hot
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.
J EXPERIMENTAL DETAILS
Here we provide more details for our experiments including hyperparameters used, design decisions, and comparison with baseline methods. We also include the anonymized code in the supplementary material.
J.1 TEXT CLASSIFICATION
Base CNN model: For all text classification experiments, the base model a CNN Le et al. 1998) with layers of 2D convolutions and 2D max pooling, before dense layer to the output softmax. The code was adapted from https:: /gtttuu com/ wwwhh/henhhhe////ee Variationn wow.onaaallaaaaaaa-aaeeeeeeee
ion and the architecture hyperparameters provided in Table 6 The only differences are the output dimensions which is for AG-News, 14 for DBPedia, 5 for Sogou-News, and 5 for Yelp-review.
Anchor: We experiment with dynamic, frequency, and clustering initialization strategies. The number of anchors |A| is a hyperparameter that is selected using (10, 20, 50, 80, 100, 500, 1, 0000. Smaller values of [A] allows to control for fewer anchors and smaller transformation matrix T at the expense of performance.
the validation set. The range of |A] is in
Transformation:
We experiment with sparse linear transformations for T. A2 is hyperparameter that is selected using the validation set. Larger values of X2 allows us to control for more sparse entries softmax based
in T at the expense of performance. For experiments dynamic mixtures,
nonlinear combination E M softmax (T,,, Am where softmax is performed over the rows of
24

---

Published as a conference paper at ICLR 2021
Table 8: Table of hyperparameters for language modeling experiments using AWD-LSTM PTB dataset.
Model
Parameter
Value
Embedding
400
Num hidden layers
Hidden layer size
1, 150
Output dim
10, 000
Loss
cross entropy
Dropout
0.4
Word embedding dropout
Input embedding dropout
0.4
1.STM layers dropout
0.25
Weight dropout
0.5
AWD-LSTM
Weight decay
1.2 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 decay
10-5
Ty. Note that applying a softmax activation to the rows of Tm makes entries dense so during training, we store Tmm as sparse matrices (which is efficient since Tm has few non-zero entries) and implicitly reconstruct E.
When incorporating domain knowledge in ANT, we use both WordNet and co- occurrence statisties. For WordNet, we use the public WordNet interface provided by NLTK ht 7/www. //www.nltk. nltk. org hww.h//wwooooo/ooooooo...o o/ h/toowt/wwooddoe wwt.etoww..et..ooooo.ooo........ htt.o.ttetttmm html For each word we search for its immediate related words among its hypernyms, hyponyms, synonyms, and antonyms. This defines the relationship graph. For co-occurrence statistics, we define a co-occurrence context size of 10 on the training data. Two words are defined to be related if they co-occur within this context size.
Domain knowledge:
note on baselines: Note that the reported results on SPARSEVD and SPARSEVD Voc (Chirkoval al. 2018) have different embedding size: 300 instead of 256. This is because they use pre-trained word2vec or GloVe embeddings to initialize their model before compression is performed.
J.2 LANGUAGE MODELING ON PTB
Base LSTM model: Our base model is a layer LSTM with an embedding size of 200 and hidden layer size of 200. The code was adapted from /stps://github com com/salesforce/ awd 1stm 1m and the full table of hyperprrameters is provided Table
Base AWD-LSTM model: In addition to experiments on an vanilla LSTTM model as presented in the main text, also performed experiments using a 3 layer AWD-LSTM with embedding size of 400 and hidden layer size of 1, 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 a hyperparameter that is selected using the validation set. The range of [A] is in {10, 20, 50, 80, 100, 500, 1, 000). Smaller values of |A] allows to control for fewer anchors and smaller transformation matrix T the expense performance.
Domain knowledge: When incorporating domain knowledge in ANT, we use both WordNet and co- occurrence statisties. For WordNet. we use the public WordNet interface provided by NLTK http: 7/www. www.w.nlta. nllk. wttp///wtt////o////ooooooo words among its hypernyms, hyponyms, synonyms, and antonyms. This defines the relationship graph. For co-occurrence statistics, we define a co-occurrence context size of 10 on the training data. Two words defined to be related if they co-occur within this context size.
ltml For each word we search for its immediate related
25

---

Published as a conference paper at ICLR 2021
Table 9: Table of thyperparameters for language modeling experiments using AWD-LSTM WikiText- dataset.
Model
Parameter
Value
Embedding dim
400
Num hidden layers
Hidden layer size
2, 200
Output dim
267, 735
Loss
cross entropy
Dropout
0.1
Word embedding dropout
Input embedding dropout
0.1
LSTM layers dropout
0.1
Weight dropout
0.0
AWD-LSTM
Weight decay
Activation regularization
0.0
Temporal activation regularization
Batchsize
32
Max seq length
140
Num epuchs
14
Activation
ReLU
Optimizer
SGD
Learning rate
30
Gradient clip Leaming rate decay Start decay
0.25
x 10-5
A note on baselines: We also used some of the baseline results as presented in Grachev et al. (2019). Their presented results differ from our computations two aspects: they include the LSTM parameters on top of the embedding parameters, and they also count the embedding parameters twice since they do not perform weight tying (Press & Wolf 2017) (see equation (6) of Grachev al.) (2019)). To account for this, the results of SPARSEVD and SPARSE Voc (Chirkova et al. 2018). as well as the results of various LR and TT low rank compression methods (Grachev et 2019) were modified by subtracting off the LSTM parameters (200 x 200 x 16). This is derived since each of the 8 weight matrices W ff ft. in L.STM layer is 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 reported in Grachev et al. (2019): these were the methods that performed low rank decomposition on both the input embedding (V) x d), output embedding (d x [V), and intermediate hidden layers of the model. For full results, please refer to Grachev et al. 2019)
Note that the reported results on SPARSEVD and SPARSE VOC (Chirkova et al. 2018 have different embedding size and hidden layer size of 256 instead of 200, although these numbers are close enough for fair comparison. In our experiments we additionally implemented an LSTT with an embedding size of 256 and hidden layer size of 256 so that we can directly compare with their reported numbers.
For baselines that perform post-processing compression of the embedding matrix, POST-SPARE HASH ppost-processing using sparse hashing) (Guo al. 2017) and POST-SPARSE HASH+K-SVD
(improving sparse hashing using k-SVD) (Guo et al.) 2017 Awasthi & Vijayaraghavan 2018), we choose two settings: the first using 500 anchors and 10 nearest neighbors these anchor points, and the second using 1, 000 anchors and 20 nearest neighbors. The first model uses 500 d [V] x 10 non-zero embedding parameters while the second model uses 1, 000 d [V] 20 parameters. For AWD-LSTM on PTB, this equivalent to 0.3M and 0.6M embedding parameters respectively which comparable the number of non-zero parameters used by method.
J.3 LANGUAGE MODELING ON WIKITEXT-103
Base AWD-LSTM model: Our base model is 4 layer AWD-LSTM with an embedding size of 400 and hidden layer size of 2, 500. The code was adapted from https: :itps://Ae :ttos///ittt htg.thubb.u... com/ sa les force//ce//eooo awdd 1 sstmm11 1m and the hyperparameters used be found in Table 9
26

---

Published as a conference paper at ICLR 2021
Table 10: Table of hyperparameters for movie recommendation experiments Movielens 1M (top) and Moviclens 25M (hottom). Initial K and AK are used for NEANT experiments.
Model
Parameter Embedding dim
Value
16
Initial K
10
AK
1
Loss
mse
Batch size
32
MF
Num epochs
50
Optimizer
Yogi
Learning rate
0.01
Learning rate decuy
Decay step size
100, 000
Model
Parameter
Value
Emhedding dim
16
Initial K
20
AK
2
Loss
Batch size
1, 020
MF
Num epochs
50
Optimizer
Yogi
Learning rate
0.01
Learning rate decay
0.5
Decay step size
200,000 000
note on baselines: While Baevski & Auli (209)) adapt embedding dimensions according to word frequencies, their goal is not to compress embedding parameters and they 44.9M (dense) parameters in their adaptive embedding layer, while we use only 2M. Their embedding parameters calculated by their reported bucket sizes and embedding sizes (three bands of size 20K (d = 1024), 40K (d 256) and 200K (d = 64)). Their perplexity results are also obtained using a Transformer model with 250M params while AWD-LSTM model uses 130M params.
For the HASH EMBED baseline that retains the frequent words and hashes the remaining words into 1, 000 OOV buckets (Svenstrup et al. 2017). We vary & E {1 10 5 10 1 x 10*) to obtain results across various parameter settings.
J.4 MOVIE RECOMMENDATION ON MOVIELENS
Base MF model: We show the hyperparamters used for the MF model in Table TO We use the Yogi optimizer (Zaheer et al. 2018) to learn the parameters.
We build ANT top of the MF model while keeping the base hyperparamters constant, For ANT, we apply compression to both movic and user embedding matrices individually. NBANT involves defining the starting value of K = |A], and AK value which determines the rate of increase or decrease in K. For Movielens 25M we use a larger initial [A] and AK since it is larger dataset and also takes longer to train, so we wanted the increase and decrease in anchors to be faster (see Table TOP. Beyond this initial setting, we found that performance is robust with respect to the initial value of K and AK, so we did not tune these parameters. In practice, we tie the updates of the number of user anchors and movie anchors instead of optimizing over both independently. Therefore, we start with the same number of initial user and movie anchors before incrementing or decrementing them by the same AK at the same time. We found that this simplification did affect performance and NBANT was still able to find an optimal number of anchors for a good trade-off between performance and compression.
ANT and NEANT:
K
MORE RESULTS
In the following sections, we provide additional results on learning sparse representations of discrete objects using ANT.
27

---

Published as a conference paper at ICLR 2021
Table 11: More text classification results (from top bottom) AG-News, DBPedia, Sogou-News, and Yelp-review. Domain knowledge is derived from WordNet and co-oceurrence statistics. Our approach with different initializations
domain knowledge achieves within 1% 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 on Yelp-review. Acc: accuracy, Emb: (non-zerv) embedding parameters.
Methods on AG-News
A
Init A
Sparse
T 2 0 Domain Acc (%)
Emb (M)
CNN (Zhang al 2015
61, 673
All
91.6
15.87
FREQUENCY (Chen
2019
5, 000
Frequency
91.0
1.28
TF-IDF (Chnn et 2019)
5, 000
TF-IDF
X
91.0
1.28
(Chen et al. 2019)
4,000
Group lasso
91.0
VVD CCen et al. 2019)
3, 000
Var dropout
X
91.0
0.77
SPARSE (Chirkova
2018
5, 700
Mult weights
88.8
SPARSEVD- Voc (Chirkova et al.
2018
2, 400
Mult weights
X
X
89.2
0.73
SPARSE CODE (Chen 2016b
100
Frequeney
89.5
2.03
50
Frequency
89.5
1.01
Frequency
91.0
ANT
10
Random
90.5
0.40
Random mixture
90.5
0.70
Methods on DBPedia CNN (Zhang et al. 2015
|
Sparse
T 0
Domain
Acc (%)
Emb (M)
563,355
All
X
X
X
98.3
144.0
SPARSE CODE (Chen et al.
2016h)
100
Frequency
x
96.7
39.0
80
Cluster
/
X
98.1
30,0
100
Random
98.2
28.0
ANT
50
Frequency
v
97.3
18.0
20
Frequency
97.2
7.0
Methods on Sogou-News CNN (Zhang al. 2015)
A
Init A
Sparse
T 2 0
Domain
Acc (%)
Emb (M)
254,499 495
All
X
X
94.0
65.0
SPARSE CODE (Chen hen et al. 2016b
100
Frequency
x
X
92.0
6.0
50
Cluster
1
/
X
93.0
5.0
80
Cluster
/
x
93.1
9.0
ANT
100
Random
93.2
6.0
50
Frequency
92.0
5.0
Methods on Yelp-review CNN (Zhang et al. 2015)
A
Init A
Sparse T T 720
Domain
Acc (%)
Emb (M)
252,
712
All
56.2
65.0
SPARSE CODE CChn hen et al. 2016b
100
Frequency /
x
X
54.0
14.0
80
Cluster
/
56.2
8.0
ANT
50
Random
x
56.0
6.0
50
Frequency
54.7
3.0
K.1 TEXT CLASSIFICATION
Extra results: We report additional text classification results AG-News, DBPedia, Sogou-News, and Yelp-review in Table II For AG-News, using mixture anchors and transformations also achieves stronger performance than the baselines using 5 anchors per mixture, although the larger number transformations leads to an increase in parameters. Our approach with different initializa- tions and domain knowledge achieves within 1% accuracy with 21x x 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.
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 a set of dynamic basis embeddings still gives strong performance, especially when combined with domain knowledge from WordNet and co-occurrence statisties. This implies that when the user has more information about the discrete objects (e.g., having good representation space perform clustering),
28

---

Published as a conference paper at ICLR 2021
Table 12: Language modeling using LSTM (top) and AWD-LSTM (bottom) PTB. We outperform the existing
vocahulary selection, low-rank, tensor-train, and post-compression (hashing) haselines. 200/ 256 represents the embedding dimension. Incorporating domain knowledge further reduces parameters. Ppl: perplexity. Emb: number of (non-zero) embedding parameters.
Method
A
Sparse
T20 Domain
Ppl
Emb (M)
LSTM 200
Grachev 2019)
10, 000
All
X
X
77.1
2.00
LSTM 256
Chirkova et al. 2018
10, 000
X
X
70.3
2.56
LR LSTM 200
(Grachey et al.
2019
10, 000
All
X
X
X
112.1
1.26
LSTM 200
Grachev et
2019)
10, 000
All
X
X
116.6
1.16
SPARSEVD 256
CCirkova et al.
2018
9,985
Mult weights
X
X
X
109.2
1.34
SPARSEVD- Voc 256
(Chirkova al.
2018
4,353
Mult weights
X
X
120.2
0.52
2,000
Random
J
X 77.7
0.65
1,000
Random
X 79.4
0.41
ANT 200
500
Random
X
84.5
0.27
100
Random
X
106.6
0.05
2, 000
Random
X
71.5
0.78
000
Random
X
73.1
0.49
ANT 256
500
Random
77.2
0.31
100
Random
X
96.5
0.05
Method
A
Init
Sparse T T
Domain
Ppl
# Emb (M)
AWD-LSTM (Merity al. 2018
10, 000
All
59.0
4.00
POST-SPARSE HASH (uo et al.
2017
1,000
Post Processing
X
118.8
0.60
POST-SPARSE HASH Guo et al.
2017
500
Post Processing
/
X
X
166.8
0.30
POST-SPARSE HASH+*-SVD
1,000
Post Processing
78.0
0.60
POST-SPARSE HASH+*-SVD
500
Post Processing
X
X
103.5
0.30
1,000
Random
72.0
0.44
500
Random
X
74.0
0.26
ANT
1,000
Frequency
77.0
0.45
100
Frequency
70.0
0.05
Table 13: Language modeling results on WikiText-103. We reach within 3 points perplexity with reduction and within 13 points perplexity with ~ 80x reduction, outperforming the frequency (HASH EMBED) and post-processing hashing (SPARSE HASH) baselines.
Method
AA
Init A
Sparse T T O Domain
Ppl
Emb (M)
AWD-LSTM MMrity
2018
267, 735
All Frequency
35.2
106.8
HASH EMBED Svenstrup ct al. 2017
100, 000
X
x
X
40.6
40.4
HASH EMBED Svenstrup ct
2017
50, 000
Frequency
X
52.5
20.4
HASH EMBED Svenstrup et al.
2017
10,000 000
Frequency
X
X
70.2
4.4
POST-SPARSE HASH (Goo al.
2017
1,000
Post Processing
V
X
764.7
5.7
POST-SPARSE HASH Guo et al.
2017
500
Post Processing
X
X
926.8
2.9
POST-SPARSE HVSH+7-SVD
1,000
Post Processing
X
73.7
5.7
POST-SPARSE HASH+K-SVD
500
Post Processing
X
X
148.3
2.9
1, 1,000
Random (Aę 1 10
V
38.4
6.5
1,000
Random (A₂ 1 10
V
X
39.7
3.1
ANT
500
Random (A2 10-9)
48.8
1.4
500
Random (Az 1 10-5)
V
X
54.2
0.4
then the user should do However, for completely new of discrete objects, simply using low-rank basis embeddings with sparsity also work well.
Incorporating domain knowledge: We find that from WordNet and co-occurrence helps to further reduce the total embedding parameters while maintaining task performance.
K.2 LANGUAGE MODELING
Extra results PTB: We report additional language modeling results using AWD-LSTM PTB in T2 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
29

---

Published as a conference paper at ICLR 2021
Table 14: On Movielens 1M. ANT outperforms MF and mixed dimensional embeddings. NBANT automatically
tunes |A| (" denotes |A| discovered by NBANT) to achieve a balance between performance and compression.
Method
user A
item A
Init A
Sparse TT
T 0
MSE
# Emb (K)
MF
6K
3.7K
All
X
0.771
155.2
6K
3.7K
All (d 16, a= ==
X
X
1.113
66,6
6K
3.7K
All (d a 00,,==1111=16))
X
1.084
66.2
6K
3.7K
All (d
X
X
1.098
47.0
MIXDIM
6K
3.7K
All (d =.6
X
1.073
42.9
6K
3.7K
All (d a2 0-
X
X
1.163
91.0
6K
3.7K
All (d 32, 0.6, 16)
1.130 X
84.6
120
8
Random (A₂ = = 10
V
V
0.772
59.4
ANT
Random (A2
10
0.786
29.2
10
Random (A2 1 10
0.836
10.8
Auto - 11" Auto - 11" Random (A1 = 0.01, 1x 10
0.795
27.7
NBANT
Auto 11" Auto 11" Random (A: 0.01, 2 10
0.837
10.6
Moun
Plowe Mara
Figure 7: A version of the plot shown Figure 3 where we simplified the plot by only showing grid points with an equal number of user and movie anchors for Movielens 25M. Here we provide several orientation views of the full 3D plot across user anchors (z-axis), movie anchors (y-axis), and objective value of (34) (z-axis). NBANT reaches the objective value indicated by the shaded red plane which is close to the optimal objective value computed over all grid search experiments for user and movie anchors. Therefore, NBANT efficiently optimize |A] to achieve balance between performance and compression, eventually reaching good value of eq (5) from just one run.
the embedding parameters by another 10x and achieve 70.0 test perplexity, which results in 100x total compression as compared to the baseline. We also perform more controlled experiments with different embedding dimension sizes 200 and 250 where we also outperform the baselines.
Extra results WikiText- 103: We also report full results using AWD-LSTM WikiText- in Table 13 where we reach within points perplexity with 16x reduction and within 13 points perplexity with 80x reduction, outperforming the frequency (HASH EMBED) and post-processing hashing (SPARSE HASH) baselines.
K.3 MOVIE RECOMMENDATION
Extra results on Mov 1M: We also report results on Moviel Lens 1M in Table 14 where we also observe improvements in accuracy and compression. We also run NBANT Movielens 1M. Despite the small size of the dataset, NBANT is able to optimize for |A] quickly and achieve good trade-off between performance and compression.
Finally, we provide a version of the 2D plot shown in Figure where we simplified the plot by showing grid points with equal number of user and movie anchors. We provide several orientation views of the full 3D plot across user anchors (æ-axis), movie anchors (y-axis), and objective value of eq (34) (z-axis) in Figure / NBANT reaches the objective value indicated by the shaded red plane which is close the optimal objective value as computed over all grid search experiments for user and movie anchors. Therefore, NBANT can efficiently optimize [A] and reach good value of eq (5) from just run.
Extra results on MovieLens 25M:
Online NBAN NT: Since NBANT automatically extend NEANT to online version that grows/contracts |A] during training, we can further stream of batches without revisiting previous ones Bryant & Sudderth (2012). This further enables NBANT to scale to large datasets that cannot all fit in memory. We treat each batch
set of data coming in and train on that batch until convergence, modify |A] as in Algorithm 2 before moving onto the next batch. In this significantly more challenging online setting, NBANT i8 still able to learn well and achieve MSE of 0.875 with 1.25M non zero parameters.
30

---

Published as a conference paper at ICLR 2021
From Figure 8 we found that initially |A| grew steadily from 10 up 26 as online batches were seen. As even more batches were seen, the number of clusters decreased steadily from 26 to 10, and oscillated between and 10. This means initially some commecions/groupingg between online batches were not clear, but with more data, natural clusters merged together. Interestingly this online version of NBANT settled on similar range of final user (8) and item (8) anchors as compared the non-online version (see Table 3}. which confirms the robustness of NBANT in finding relevant anchors automatically.
26
3
12
10
10
20 30
50
online batches
Figure 8: Using NBANT for online learning increases |A] with before natural clusters emerge, and decreases to similar value (8) as non-online version in Table
L EFFECT OF L AND X2
data
[4]
In this section we further study the effect of the hyperparameters a and A2. Recall that our full objective function derived via small variance asymptotics is given by:
min Dalus (A)) + 22
(AI 22)
(36)
A.O.K
The role of hhper-paramedee parameter 22 is clear: For a fixed A and integer valued variable K, tuning 22 controls the trade-off between sparsity of 'T and model performance (see Table
The role of hyper- parameter Å is more subtle. It can be considered as a weighing fraction for scalarizing underlying multi-objective optimization problem. To elaborate, one consider our goal as multi-objective problem of minimizing the predictive loss while simultaneously using minimal number of anchors (K)). Then the hyperparameter Å can be used to select solution along the Pareto front. In other words, tuning the hyperparameter A allows to perform model selection by controlling the trade-off between the number of anchors used and prediction performance. We apply eq (36) on the trained models in Table and report these results Table [5| Choosing a small A1 = x 10 selects a model with more anchors ([A] 1. 000) and better performance (ppl 79.4), while larger Å 1 10-1 selects the model with fewest anchors (IA) 100) with compromise in performance (ppl 106.6).
Table 15: An example model selection on the trained language models using LSTM trained on PTB. Tuning the hyperparameter λı and evaluating eq (36) allows us to perform model selection by controlling the trade-off between sparsity as determined by the number of anchors used and prediction performance.
Method
[
Init A
Ppl
mnz
A1
A
eq 36)
000
Dynamic
77.7
245K
2x 10
1 10
4.64
1, 0.000
Dynamic
79.4
214K
2x 10-6
1 10-6
4.61
ANCHOR TRANSFORM 200
500
Dynamic
84.5
171K
10
10
100
Dynamic
106.6
25K
2x 10
1x
4.92
2, 0000
Dynamic
77.7
245K
1x 10
1x
4.80
0000
Dynamic
79.1
214K
1x 10
1x
4.69
ANCHOR & TRANSFORM 200
500
Dynamic
84.5
171K
1x 10
1x
4.66
100
Dynamic
106.6
25K
10
1x
4.93
2, 000
Dynamic
77.7
245K
1 10
1x 10
204.6
1, 1,000
Dynamic
79.4
214K
1 10
1x
104.6
ANCHOR & TRANSFORM 200
500
Dynamic
84.5
171K
1x 10
10
54.6
100
Dynamic
106.6
25K
1x 10
1x
14.9
31


Reviews:
[{"review_id": "p_vAr3LMMHS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "In this paper, the authors proposed a method to learn efficient representations of discrete tokens. They took a two step approach: in step 1, they learn \"full fledged\" embeddings for a subset of anchor tokens. In step 2, they learn a sparse matrix that is used to relate all tokens to the set of chosen anchors. This two-step approach reduced the overall number of parameters. The sparse matrix T can also encode domain knowledge (e.g. knowledge graphs). In the experiment section, the authors showed that their approach has good performance on several language tasks, with far fewer parameters.\n\nIn general the paper is well written and the flow is easy to follow. I find the main idea plausible and ingenious. For language tasks and word embeddings, anchoring method has been shown to be effective in several tasks already (e.g. [1] http://papers.nips.cc/paper/8152-the-global-anchor-method-for-quantifying-linguistic-shifts-and-domain-adaptation). The authors took two steps forward: 1) instead of in [1] where the entire vocab is used for anchoring purposes, the authors used a subset of tokens which reduces the amount of parameters. 2) they use a sparse T matrix to relate other tokens to anchors which again has reasonable prior: the meaning of a word can be efficiently defined by a few good chosen anchors. Although this paper is probably related to other strains of research (e.g. leaning manifolds for IR/NLP where anchoring is also a key concept, which the authors could have admittedly surveyed more), I particularly liked the fact that the two-step procedure decomposes two tasks that are often mixed together for embedding tasks: learning representation vs learning relations.\n\nWhile the authors claimed that they can further impose domain knowledge in the learning process (which I think this is at least a good attempt), this part in general feels a bit less convincing. To be specific, there can be a variety of knowledge (like related, is a subset of, analogy, etc.). It is not clear how the distinction of different types of knowledge can be incorporated. What the authors proposed is lumping them into the notion of \"positive pair\" and relax constraints on them. This may or may not suffice (for the purpose of adding domain knowledge), but on paper, there is a chance that some finer structures of the domain knowledge may get lost. It's not clear how much gain (especially the experiment section, for fair comparison purposes where other methods do know use domain knowledge in particular) is from incorporating domain knowledge; an ablation study might help.\n\nAnother question is about training. It's not obvious to me how to guarantee that for every row of T, there is at least 1 non-zero element. Is some specific tuning needed for rows corresponding to rare words? How the regularization strength $\\lambda$ on T is selected?\n\nThe reduction of parameters is while keeping task performance is illustrated quite well in the experiment section. Their method does not reduce the theoretical complexity (still linear w.r.t. vocab size, as T must have at least one element per row), but in practice the reduction (which mostly comes from savings of dimensionality) is quite obvious.", "extra_scores": {}, "extra_text": {}}, {"review_id": "AUkrQXKVb2f", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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 introduces a row-rank approximation of embeddings using “anchors”. It also proposes a probabilistic interpretation of their method as a non-parametric Bayesian dictionary learning model, which can be inferred by optimizing the small-variance asymptotic objective.\n\nWhat I agree with the authors are:\ni) Using properly chosen basis vectors may greatly reduce the memory cost for embeddings, especially for huge vocabulary sizes (e.g. over 100 million).\nii) The initialization for basis vectors is extremely important and should be updated through training.\niii) Experimental results look reasonable in this paper.\n\nWhat I feel confused about are:\ni) Why interpret this method in a Bayesian non-parametric way? To be more specific:\ni.1) The final objective function (5) does not involve Bayesian posterior inference. If you want a point estimation of sparse representation + learnable anchors, you don’t need a Bayesian model.\ni.2) Bayesian non-parametric is useful because it can automatically learn the model size. In your case, |A|. You mention this point in Figure 3, but there is no online learning result showing that your model has the capacity to grow the model through training. One example is “Truly Nonparametric Online Variational Inference for Hierarchical Dirichlet Processes” by M. Bryant and E. Sudderth.\n\nii) The vocabulary size in your experiment is decent, but not very big. Normally in a recommendation system, the vocabulary size can be the number of users, which is at least 100M. Normally the embedding size is around 16 to 64 in real systems. The proposed method could be a huge gain in storing such a huge embedding table. But I cannot see an experiment at this vocabulary level. Even rough results at this level could make this paper much stronger.\n\niii) This is a minor point, but AUC results in MovieLens besides MSE can reflect the ranking quality in recommendations.\n\nOverall, this paper proposes a practical solution to cut embedding storage. But the Bayesian interpretation is not persuasive and there are still missing pieces in the experiments.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "1riDEfR6CT", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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 ANT to solve the problem of learning Sparse embeddings instead of dense counterparts for tasks like Text Classification, Language Modeling and Recommendation Systems. When the vocabulary size |V| runs into several 100Ks or millions, it is impractical to store one dense vector per label. Hence the paper proposes to only store a few anchor/latent vectors (the matrix is A with |A|<<|V|). All label vectors are expressed as linear combinations of a 'few' anchor vectors. To train this end-to-end, we need a transformation matrix T such that T*A = E (E is V\\times d embedding matrix). T has to be structured, i.e., each row of T has to be sparse and positive only (although negative weights are also fine, I'm not sure if weight redundancy is that important). \n\nThis pipeline is trained end to end using YOGI optimizer for regular gradient updates and 'proximal gradient descent' for T which does soft thresholding with a lower bound of 0 (accomplishing both sparsity and positivity part).\n\nThis design admits multiple ways of initializing the anchors A. And the authors perform experiments with both frequent token vectors and random anchor vectors (both have their merits, random seems to be a robust choice).\n\nThe authors provide a statistical interpretation of their approach using a generative formulation to the embedding vectors in terms of the latent vectors (using a Indian Buffet Process membership matrix Z).\n\nThe experiments span two major domains, NLP and Information Retrieval. Across multiple NLP datasets, ANT outperforms Sparse-Coding (Chen et. al. 2016)  and Post-Sparse-Hash (Guo et.al. 2017). On the IR task with MovieLens dataset, the primary comparison is against SLIMMING (Liu et.al. 2017). While gains are substantial on the NLP tasks, they seem minimal on the MovieLens task.\n\nI've listed most pros above. The cons are here:\n1. The idea seems a little similar to Compositional Embeddings (Shi et. al. 2020, Ginart et. al.2019). It might warrant a discussion or comparison.\n2. There are other sparse embedding methods like SNRM (Zamani et.al. 2018) and SOLAR-Sparse Orthogonal ...(Medini et.al. 2020) which might be comparison candidates at-least for IR tasks.\n3.  The precision in table 1 for ANT anomalously increases when |A| is reduced. ANy explanation as to why this happens? The information bottleneck is supposed to reduce precision right?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a method to cope with large vocabulary sizes. The idea is to find a small number of anchor words and to express every other word as a sparse nonnegative linear combination of them. They give an end-to-end method for training, and give a statistical interpretation of their algorithm as a Bayesian nonparametric prior (in particular an Indian restaurant process). They give extensions that allow them to deduce the optimal number of anchors which allows them to avoid needing to tune this hyperparameter. Finally they give a variety of experiments, particularly in language and recommendation tasks. The results on language are particularly impressive, and in the author response period, at the behest of a reviewer, they were able to extend the experiments to the Amazon Review dataset which contains 233M reviews on 43.5 M items by 15.2 M users. 

This paper is a nice combination of a simple but powerful idea, and a range of experiments demonstrating its utility. Other papers have proposed related ideas, but here the main novelty is in (1) using a small number of anchors that can incorporate domain knowledge and (2) using a sparse linear transformation to express other words in this basis. One reviewer did not find the Bayesian nonparametric interpretation to be fruitful, since it does not lead to techniques for handling growing datasets (e.g. if the ideal number of anchors changes over time). 
Decision: Accept (Poster)