SOLAR: Sparse Orthogonal Learned and Random Embeddings
Authors: Tharun Medini
Beidi Chen
Anshumali Shrivastava
Venue: ICLR 2021 Poster (2021)
Keywords: Sparse Embedding
Inverted Index
Learning to Hash
Embedding Models

Abstract: Dense embedding models are commonly deployed in commercial search engines, wherein all the document vectors are pre-computed, and near-neighbor search (NNS) is performed with the query vector to find relevant documents. However, the bottleneck of indexing a large number of dense vectors and performing an NNS hurts the query time and accuracy of these models. In this paper, we argue that high-dimensional and ultra-sparse embedding is a significantly superior alternative to dense low-dimensional embedding for both query efficiency and accuracy. Extreme sparsity eliminates the need for NNS by replacing them with simple lookups, while its high dimensionality ensures that the embeddings are informative even when sparse. However, learning extremely high dimensional embeddings leads to blow up in the model size. To make the training feasible, we propose a partitioning algorithm that learns such high dimensional embeddings across multiple GPUs without any communication. This is facilitated by our novel asymmetric mixture of Sparse, Orthogonal, Learned and Random (SOLAR) Embeddings. The label vectors are random, sparse, and near-orthogonal by design, while the query vectors are learned and sparse. We theoretically prove that our way of one-sided learning is equivalent to learning both query and label embeddings. With these unique properties, we can successfully train 500K dimensional SOLAR embeddings for the tasks of searching through 1.6M books and multi-label classification on the three largest public datasets. We achieve superior precision and recall compared to the respective state-of-the-art baselines for each task with up to 10 times faster speed.

Published as a conference paper at ICLR 2021
SOLAR: SPARSE ORTHOGONAL LEARNED AND RAN- DOM EMBEDDINGS
Tharun Medini' Beidi Chen", Anshumali Shrivastava' Rice University, Stanford University
tharun. mediniiii @ricee edu, beidi www..ceennstaforr...c.. anshumaliérice. edu
ABSTRACT
Dense embedding models are commonly deployed in commercial search engines, wherein all the document vectors are pre-computed, and near-neighbor search (NNS) is performed with the query vector to find relevant documents. However, the bottleneck of indexing large number of dense vectors and performing an NNS hurts the query time and accuracy of these models. In this paper, we argue that high- dimensional and ultra-sparse embedding is significantly superior alternative dense low-dimensional embedding for both query efficiency and accuracy. Extreme sparsity climinates the need for NNS by replacing them with simple lookups, while its high dimensionality ensures that the embeddings are informative even when sparse. However, learning extremely high dimensional embeddings leads to blow up in the model size. To make the training feasible, propose partitioning algorithm that learns such high dimensional embeddings across multiple GPUs without any communication. This is facilitated by our novel asymmetric mixture of Sparse, Orthogonal, Learned and Random (SOLAR) Embeddings. The label vectors are random, sparse, and ncar-orthogonal by design, while the query vectors are learned and sparse. We theoretically prove that our way of one-sided learning is equivalent to learning both query and label embeddings. With these unique properties, we can successfully train 500K dimensional SOLAR embeddings for the tasks of searching through 1.6M books and multi-label classification on the three largest public datasets. We achieve superior precision and recall compared to the respective state-of-the-ae baselines for each task with up to 10x x faster speed.
INTRODUCTION
Embedding models have been the mainstay algorithms for several machine learning applications like Information Retrieval (IR) ( and Natural Language Processing (NLP) 21 16 31, (9) in the last decade. Embedding models are learned spin-off's from the low-rank approximation and Matrix Factorization techniques that dominated the space of recommendation systems prior to the emergence of Deep Learning (DL). The primary purpose of these models is to project rather simple and intuitive representation of an input to an abstract low-dimensional dense vector space. This projection enables two things: 1) tailoring the vectors specific downstream applications and 2) pre-processing and storing documents or products as vectors, thereby making the retrieval process computationally efficient (often matrix multiplication followed by sorting, which are conducive to modern hardware like GPUs).
Besides the computational advantage, embedding models capture the semantic relationship between queries and products. A good example is product prediction for service like Amazon. A user-typed query has to be matched against millions of products and the best search results have be displayed within fraction of a second. With naive product data, it would be impossible to figure out that products with 'aqua' their titles are actually relevant to the query 'water'. Rather, if we can project all the products to a dense oww-dimeniional vector space, query can also be projected to the same space and an inner product computation can be performed with all the product vectors (usually dot product). We can then display the products with the highest inner product. These projections can be learned to encapsulate semantic information and can be continually updated to reflect temporal changes in customer preference. To the best of our knowledge, embedding models the most prevalent ones in the industry, particularly for product and advertisement recommendations (Amazon's DSSM 23 Facebook's DLRM (22)

---

Published as a conference paper at ICLR 2021
However, the scale of these problems has blown out of proportion in the past few years prompting research in extreme classification tasks, where the number of classes runs into several million. Consequentially, approaches like Tree-based Models [ and Sparse-linear Models (36) [9] (8) have emerged as powerful alternatives. Particularly, Tree-based models are much faster to train and evaluate compared to the other methods. However, most real Information Retrieval systems have dynamically changing output classes and all the extreme classification models fail to generalize to new classes with limited training data (e.g., new products being added to the catalogue every day). This has caused the resurgence of embedding models for large scale Extreme Classification ( 29 7).
Our Contributions: In this paper, we argue that sparse, high dimensional, orthogonal embeddings are superior to their dense low dimensional counterparts. In this regard, we make two interesting design choices: 1) We design the label embeddings (e.g. produucts in the catalogue) to be high dimensional, super-sparse, and orthogonal vectors. 2) We fix the label embeddings throughout the training process and learn only the input embeddings (one-sided learning), unlike typical dense models, where both the input and label embeddings are learned. Since we use combination of Sparse, Orthogonal, Learned and Random embeddings, we code-name our method SOLAR. We provide theoretical premise for SOLAR by showing that one-sided and two-sided learning mathematically equivalent. Our choices manifest in a five-fold advantage over prior methods:
Matrix Multiplication to Inverted-Index Lookup: Sparse high dimensional embeddings can obtain a subset of labels using a mere inverted-index (8) lookup and restrict the computation and sorting to those labels. This enhances the inference speed by a large margin.
Load-balanced Inverted Index: By forcing the label embeddings to be near-orthogonal and equally sparse (and fixing them), we ensure that all buckets in an inverted index are equally filled and we sample approximately the same number of labels for each input. This omits the well-known imbalanced buckets issue where we sub-sample almost all the labels for popular inputs and end up hurting the inference speed.
Lower Embedding Memory: Dense embedding models need to hold all label embeddings in GPU memory perform real-time inference. This is not scalable solution with millions of labels (which is a practical industry requirement). On the contrary. SOLAR needs to store only few integers indices per label which is very memory efficient with modern sparse array support all platforms. These vectors can also be used with Locality Sensitive Hashing based indexing systems like FLASH (34).
cormuninmmii:::o:::: Our unique construction of label embeddings enables distributed training over multiple GPUs with zero-communication Hence, we can afford train on a 1.67 M book recommendation dataset and three largest extreme classification datasets and outperform the respective baselines on all 4 of them on both precision and speed. Learning to Hash: An Inverted-Inde are hashed into a few buckets (8, (3). By fixing the label buckets and learning to map the inputs to the corresponding label buckets, we are doing a 'partial learning to hash" task in the hindsight (more on this in Appendix A..
can be perceived as a hash table where all the output classes
2 RELATED WORK
While there have been a plethora of dense embedding models, there is only one prior work called SNRM (Standalone Neural Ranking Model) (40) that trains sparse embeddings for the task of suggesting documents relevant to an input query (classic web search problem). In SNRM, the authors propose to learn high dimensional output layer and sparsify it using a typical LI or L2 regularizer. However, imposing sparsity through regularization causes lopsided inveted-inded with imbalanced loads and high inference times. As we see in our experiments later, these issues lead to the poor performance of SNRM on our 1.67M product recommendation dataset.
SNRM:
GLaS: Akin to SOLAR's construction of near-orthogonal label embeddings, another recent work from Google 111 also explores the idea of enforcing orthogonality to make the labels distinguishable and thereby easier for the classifier to learn. The authors enforce it in such a way that frequently co-occurring labels have high cosine-similarity and the ones that rarely co-occur have low cosine similarity. This imposition was called a Graph Laplacian and Spreadout (GLaS) regularizer. However, this was done entirely in the context of dense embeddings and cannot be extended to our case due to the differentiability issue. We show the comparison of SOLAR against dense embedding models with and without Gl regularizer later on in section 5.1
2

---

Published as a conference paper at ICLR 2021
Preprocessed Label Vectors
Cross-Entropy
Classifier
True Labels
Classifiery
N (num labels)
OR
Cussifiergaa
Tokenized
Input
Classifierg-
Figure 1: Schematic diagram for label vector construction (on the right) and the training process (on the left). Each label vector is B K dimensional divided into K components of length B. Each vector is K- K-sparse with exactly one non-zero index in each component (colored on the right). The components are separated by dotted vertical lines. For a given input, we perform an 'OR' operation the true label vectors and feed the resultant pieces to independent small classifiers.
Fix your Classifier: The idea of fixing label vectors explored in 113 In (3), the authors propose to initialize the last weight matrix of popular CNN architectures with Hadamard matrices and only train the preceding layer weights. With minimal loss in precision, the number of trainable parameters can be greatly reduced. However, 'Fix your Classifier' does not scale to the the huge number of labels in the tasks of our interest the model cannot be elegantly distributed across independent workers. As shown later in section 5.2 we observe huge performance degradation too with similar network configurations SOLAR.
Sparsifying Dense Embeddings: Several prior works have proposed to project pre-trained dense embeddings to a sparse high dimensional vectors using techniques like over-complete dictionaries (10), denoising k-sparse auto-encoders (88 19), permutation maps on unit spheres (4). While all these approaches vindicate the superiority of sparse vectors, none of them learn end-to-end high dimensional sparse vectors and have been confined to tasks with lot fewer labels.
All other embedding models for query-label pairs, differing in the choice of projection functions. Pairwise training needs negative sampling (12) to avoid degenerate solutions and has large training times as the number of training instances (query-label pairs, both relevant and irrelevant) effectively blows up.
primarily optimize a pairwise similarity- loss function
SOLAR, in addition to being sparse, also solves these challenges by learning a classifier instead of similarity based loss function, encapsulating all labels of input at once. Since classifier has intrinsic negative sampling, the number effective training samples much lower.
OUR METHOD: SOLAR
In this section, we describe in detail the workflow of our algorithm SOLAR. First, we will discuss the pre- pre-processing phase where we construct random sparse label vectors (figure[] and an inverted-index of the labels (figure 2 Then, we move to the training phase where we split the label vectors into independent contiguous components and train each of them in parallel (figure [].. In the end, we show the inference procedure where obtain the picce-wist query vector in parallel and sparsify by retaining only top buckets from each piece. We then look up the saved inverted index to retrieve and score the candidate labels sort and predict the best ones (figure 3)
the sparse vector dimension. K is the number of non-zeros in label vectors. B - is the number of buckets in each component of the vector.
Notations: N denotes the total number of labels.
Pre-processing: Construction of Label Embeddings and Inverted-Index: As presented in figure let there be N labels (N is large, in the order of million). We intend to construct K K-sparse
3

---

Published as a conference paper at ICLR 2021
(having K non-zero indices) high dimensional vectors for each label. As noted earlier, large output dimension makes training a cross-entropp loss prohibitively expensive. Therefore, inspired by recent work on coroocommuniittionn Model Parallelism (20), we partition the large dimensional vector into K' subsets and train each one independently. Each subset of the partition comprises of buckets with exactly one non-zero index. The colored blocks the right side in figure [ denote the non-zero indices for each label vector.
To adhere to our design principle of load-balancing, for each label, we pick the non-zero index randomly in the range of B for each of the K components. To be precise, for any label, we randomly generate K integers in the range B. As in most of our experiments, set K 16 and
30K. This makes the overall dimension D = B x K = 480K and a sparsity ratio of 0.000533 (0. (0.0533%). As an example, let the generated integers be (18189, 8475, 23984, ..... 17924, 459). Then the non-zero indices of the overall vector are simply B-shifted, i.e., {18189, 38475, 83984, ..... 437924, 450459). Although any random number generator would work fine, we pick our non-zero indices using sklearn's murmurhash function. It is rather straightforward to see that these vectors are near-orthogonal. The expected dot-product between any two label vectors 42 and 13 is,
K B
E(I +1z) = Ep(ha(() = ha(()) =
2 0.
(1)
Figure shows the toy inverted index for the label vectors shown in figure [T Since we train K indepen- dent models, each model is expected to predict its own "buckets of high relevance'. Hence we maintain K sep- arate inverted-indexes. For any input, we accumulate the candidates from each of the K inverted-indexer and take a union of them for scoring and sorting. It is noteworthy that two unrelated labels might be pooled into the same bucket. While this sounds rather jarring from Icarnability perspective, it is essential for the load-balance and also to learn a positive-only associ- ation of input tokens and true-label buckets (more on this Appendix B
Inverted Indexo
Inverted Index,
B
Labels
B
Labels
0
2
3
2
3
N-4
N-3
3
N-4
N-2
Inverted Indes,.2
Inverted Indexg.1
B
Labels
B
Labels
0
N-3
1
2) Training: Figure | also depicts the training process (on the left side). In multilabel learning problem, each input has a variable number of true labels. We lookup all the true label vectors for an input and perform an "R'' operation over the respective sparse label vectors. Please note that at the level of sparsity we are dealing, even with zero pairwise collisions among the non-zero indices of label vectors, still have super-sparse representation for the resultant 'OR' vector. We parti- tion this combined-label vector into K parts just like before and train individual classifiers (simple feed for- ward neural networks with 1 hidden layer) with a binary cross entropy loss function with the B dimensional few-hot vectors. Please note that these models do not communicate with each other. Since there is no overhead of parameter sharing, training can be embarrassing parallellized across multiple GPUs Cetro-Comuunication Model Parallellism).
2
N-4
N-2
2
3
3
3
N-3
Figure 2: Inverted- Index construction for the label vectors shown in figure We con- struct one index for each of the K chunks. Each bucket will have the same number of labels by design
Input Feature Hashing: Usually, naive input tokenization like bag-of-wordd (BoW) leads very high dimensional input. This in turn makes the first layer of the network intractable. Hence, an elegant solution for this problem is to hash the token indices to lower dimension (called Feature Hashing (35)). In case,
different random seed for each of the K models and hash the input indices to feasible range. Although we lose some inputiinformation in each individual model (due to feature hash collisions), the variation in random seed minimizes this loss when all the models are collectively taken into account.
3) Inference One of the key advantages of SOLAR over dense embedding models is faster inference. As mentioned earlier, the primary reason for this is the replacement matrix-multipe matrix-multpplication and sorting with simple lookups and aggregations. This workflow is depicted in figure Given tokenized
4

---

Published as a conference paper at ICLR 2021
input, we pass it through all the K models in parallel and obtain the respective B dimensional probability vectors. We then sort these probabilities and obtain the top-m (m varies among 50 and 100) buckets for each model. These x K integers constitute the non-zero indices of the SOLAR embedding for the input query. We can query the K inverted-indexes with the respective top-m buckets for candidates. union of all these candidates candidates, we sum up the predicted probability scores from the corresponding buckets and sort for the top results.
target of labels. For each of these
Filtering Noisy Labels: Ran- dom mitialiiatiin of embeddings will inevitably result in unrelated labels being assigned the same bucket in any of the K subsets of the partition. Hence, a lot of the candidate labels obtained from the inverted-indexes would ir- relevant to the query. However, is unlikely that an unrelated la- bel would appear in the top m buckets more than one of teh K models. Hence, we can omit the labels that appear in the top- m buckets less than threshold times. The larger d is, the more precise the retrieved candidates will be. However, setting large would mean fewer candidates and thereby lower recall. Later in section [5.1 (in (). we ex- periment with multiple values of and corroborate that d = K/2 is optimal trade-off between precision and candidate set size.
Sparsification
A3
Best Label
Classifiery
0.93+10900-0.6 2.44
1.90
0.76
Classifiery
N-3
0.61-0,76 1.37
Classifierg.a
0.93-0.90000 -1.83
Tokenized Input
Chasifierg..
Figure 3: Schematic diagram for Inference. We first get K prob- ability vectors of dimensions each. Then we only retain the top-m buckets after sparsification (m=1 in above figure. For experiments, m varies among 50 and 100). We accumulate the candidate labels based on inverted-index for these top-buckets and aggregate their scores and identify the best labels.
up the log of probabilities across the K models for every candidate label as it represents the log-likelihood Another potential strategy is the logit values directly (as logits have wider range and are more expressive). In case, we chose to assign the sum of predicted probabilities for each candidate (as sum is just scaled version of mean). The rationale behind this is shown in the following analysis assuming a multi-class classification setting.
Alternate Scoring Methods: It is quite customary
For an input denote Pr(y = i) = Psi E 20. Let Pr(y = b(O,) = pg: b e (0, 1,2, B} and 1..,. K}. Since our fash-functions are random, we have
Phl Ps Σ
A()))
Aepli
Hence E(Ph ps Exsi Ph = Pi (1-ps)
After rearrangement, we get
B * F(P)) h(3)
=
B 1)
B -
This analysis shows that the original label probabilities are linearly monotonic with expected value of the respective bucket probabilities. And since expected value is proportional to the sum across all K models, summing probabilities is a principled scheme to preserving ranking. While we primarily report the precision with sum of probabilities, we compare it against the other two heuristics (summing org-prbbabilities and logits) too in our experiments (in table
N Time- Com-lCompe:::t: Since our inverted indexes are ball-balanced, each bucket accommodates B labels. Hence, the top-m buckets contribute mN candidates. The candidates retrieved from K models
5

---

Published as a conference paper at ICLR 2021
bound have some overlapping labels, accompanied by some unrelated counterparts from the respective buckets (since we randomly initialized the label vectors).
In the worst case of zero overlaps, the total number of candidates would be Km,,, The aggregation of scores and frequencies of occurrence in top-m buckets is a by-product of the candidate selection step. We then omit the candidates with frequency < d. Finally, the remaining candidates. Including the two sorting steps: 1) to get top-m buckets 2) to get top KmN
sort the aggregated scores for
5 labels, the total number of operations performed is B log m + B + B log 5. A dense embedding model on the other hand needs NmK + N log 5 steps (assuming dense vectors of dimension d mK, since SOLAR also has mk non non-zero zeros after inference). For the scale of N and mK we are dealing with (N- = 1M, K = 16, m = 50, B = 30K), SOLAR supposedly has 1+log times faster inference. However, matrix multiplications have specialized processes with hardware acceleration unlike SOLAR and the practical gains would be in the order of 5x (more in section 5.1)
KmN
B
4 ANALYSIS: Is ONE-SIDED LEARNING ALL WE NEED?
As argued before, we need distributed training to learn ultra-high dimensional embeddings. Our distributed process requires randomly initializing and fixing label embeddings, which might seem to be questionable approach. However, it turns out that this method of learning is mathematically equivalent to the standard two-sided learning approach with orthogonality constraints. Enforcing such orthogonality in the embedding space for information gain is common practice 11. More specifically, we prove that the following two processes are mathematically equivalent under any kernel: 1) learning standard two-sided embedding (for both inputs and labels) with orthogonality constraint on the label embedding 2) starting with any fixed orthogonal embedding in the label space and learning the input embeddings. This is a nuanced analogy the 'Principle of Deferred Decision'.
An embedding model comprises of two functions /t and Jt which map the inputs and labels respectively a common vector space. Let XX be the set of all inputs and be the set of all labels. For some x E X and E YY we seek to optimize fr and fr such that the inner product (f)())) fz (v)) (or any kernel) the desired similarity metric S(x, v). Typieally, fi and f are neural networks that map
tokenized sentences to vector space and S(r,, v) (fr(z), fL (w)) = fx fz(
(cosine
similarity). A special case of the embedding models are the popular Siamese Networks 23 2. in which fi = fL. i.e., both inputs and outputs learn shared embedding space.
The imposition of orthogonality on the label vectors supposedly learns a function fr such that
(fI())) (z))) = 5.j Vy,. Uj E
where 6t is the Kronecker-delta function. Hence, {fr (v1). fo fy))), form an orthonormal basis (since we ensure that the learned vectors unit norm). The following theorem states that both the aforementioned learning methods are equivalent.
Theorem 1. Law of Deferred Orthogonality of Learned Embedding Given any positive semi- definite kernel S(..-), and functions Si and ft, where St. is orthogonal. For any orthogonal function with the same input and range space as SL, there always exist a function f, such that ((f((z), fz())) S(f(x), R(y)).
Proof. Please refer to Appendix C for detailed proof. The result mainly follows from lemma 2 Lemma 1. For any two orthonormal basis matrices, A = [aj a2 ag ... anl and B
[b, 22 by ... bn] in the same vector space, there exists an orthogonal matrix P such that A PB.
Note that, since construct fixed norm label vectors, orthogonal vectors form orthonormal basis vectors (up to a constant norm factor multiplication).
The popular law of deferred decision in probability allows to pre-generate random numbers for efficiency. In an analogous fashion, Theorem 2 allows us to pick any orthogonal transformation R in advance and only learn oie-sided embedding function f. By exploiting this flexibility we design random, binary, and ultra-sparse label vectors which make training affordable at 500K dimensions.
Power of Randomness:
EXPERIMENTS
We now validate our method on two main tasks 1) Product to Product Recommendation on a 1.67M book dataset. This dataset simulates the typical product recommendation task in most search engines.

---

Published as a conference paper at ICLR 2021
Model
epochs
P@i
P@5
Rec
Train Time (hrs)
Eval Time (ms/point)
SOLAR (m=100)
10
35.24
29.71
26.98
34.19
2.65
0.96
DSSM 1600)
5
31.34
27.55
24.41
32.71
25.27
1.77
GLaS (d= 1600)
5
32.51
28.31
25.41
33.17
37.14
1.77
SNRM (d=30K)
5
1.59
2.01
1.93
2,41
AnnexMI. (d=800)
10
26.31
22.22
19.37
26.13
16
3.06
Table 1:
Comparison of SOLAR against DSSM, DSSM+GLaS, and SNRM baselines. SOLAR's metries are better than the industry-standar DSSM model while training 10x faster and evaluating 2x faster (SOLAR-CPU vs DSSM-GPU evaluation). GLaS regularizer improves the metrics but still lags behind SOLAR.
scoring method
P@1
P@5
P@ 10
Rec 100
sum probabilities
35.24
29.71
26.98
34.19
sum log probabilities
35.89
30.13
27.11
34.69
sum logits
35.93
30.17
27.14
34.77
Table 2: Comparison of different scoring schemes. SOLAR inference admits any aggregation scheme that is monotonic function of true label probabilities. We observe that summing probabilities, log-probabilities and logits all give nearly the same precision with logits being slightly better.
2) Extreme Classification with the three largest public datasets. Most of the deployed models on modern search engines show promising results on these public datasets in addition to their respective private datasets (25) 14 20). Additionally, we also train SOLAR embeddings to retrieve a set of target words (unordered) given the source sentence which can perform translation effectively when coupled with a target Language Model with copy mechanism. Please refer to Appendix D details.
5.1 PRODUCT TO PRODUCT RECOMMENDATION
Dataset: This dataset is curated from the raw Amazon Book dataset on extreme classification repository (XML-Repo) (30). This dataset comprises of 1604777 training books whose titles serve as input queries. Each query book mapped to a set of target books serving as labels (related products recommendation problem). There are total of 1675657 label books with titles. After parsing both the query titles and label titles, the total vocabulary comprises of 763265 words. The average query length is 9 for both input titles and label titles. There additionally 693K eval books.
Hyperparameters: As mentioned before, we train 480K dimensional SOLAR embeddings split into K = 16 chunks of B 30K buckets each. The label embeddings fixed to be exactly 16-sparse while the learned query embeddings are evaluated with 1600 non-zero indices (by choosing m 100 top buckets). We feature hash the 763265-dimensione independent model a feed-forward network with an input layer with 100K nodes, one hidden layer with 4096 nodes, and output layer with B 30K nodes. For minimizing the information loss due to feature hashing, we choose a different random seed for each model. Note that these random seeds have be saved for consistency during evaluation.
BOW inputs to 100K dimensions. Each
Machine and Frameworks: We train with Tensorflow (TF) v1.14 on an DGX machine with NVIDIA-V V100 GPUS. We use TF Records data streaming to reduce GPU idle time. During training. we use a batch size of 1000. During inference, except getting the sparsified probability scores, all
min. freq. d
candidates
P@
P@5
P@ 10
Rec 100
88495.015
34.62
28.50
25.25
25.34
2
2483.83
35.19
29.62
26.85
33.08
4
96.425
35.22
29.65
26.89
33.54
8
43.885
35.24
29.71
26.98
34.19
Table 3: Filtering Noisy Candidates: We only retain candidates which appear in at-least d of the K models in the top-m buckets. For K = 16, m 100 and B = 30000, precision and average candidate set size is listed above. Recall improves a lot when we filter out noisy candidates.
7

---

Published as a conference paper at ICLR 2021
other steps performed CPU using python's multiprocessing module with 48 threads. Our metrics of interest are standard precision and recall. We measure precision at 1,5,10 and recall at 100 (denoted by P@ 1, P 10 and Rec 100).
The most natural comparison arises with recent industry standard embedding models, namely Amazon's Deep Semantic Search Model (DSSM) (23) and Facebook's s Deep Learned Rec- ommendation Model (DLRM) (22.. DLRM takes mixed inputs (dense and sparse) and learns token embeddings through a binary classifier for ad prediction. On the other hand, DSSM trains embed- dings for semantic matching where we need to suggest relevant products for a user typed query. We compare against DSSM as aligns with this dataset. Additionally, we impose orthogonality in DSSM using GlaS (IT) regularizer. We also compare against other embedding models AnnexML (29) and
Baselines:
SNRM (40). Under any reasonable setting, we could not train a 'Fix your Classifier' (FyC) 13
baseline for 1.67M labels due to model memory constraints. However, we do compare against FyC Please refer to Appendix for baseline settings.
for other datasets in section 5.2
Results: compares SOLAR against all the aforementioned baselines. The top row corresponds to the case where we pick the top- buckets each of the models (and hence an 1600 sparse vector and a sparsity ratio of 1600/48KK 0.333% We notice that on all the metrics, SOLAR noticeably better than DSSM and its improved variant with a GLaS regularizer. SNRM clearly underperforms due to reasons mentioned in section 2 An interesting point to note is that the evaluation for DSSM was totally done on GPU while SOLAR spends most of its time on CPU. Despite that, SOLAR infers much faster than other baselines.
Table 2 shows the precision performance for different score aggregation schemes. We observe that SOLAR is robust multiple aggregation strategies as long as the scores are monotonic functions of actual label probabilities. Table 3 also shows the effect of filtering out noisy candidates based on the number of occurrences in the top-m buckets across models. We can observe that the number of active candidates falls exponentially with d and the precision and recall improve.
Please refer to Appendix for some sample evaluation queries which show that DSSM works well for frequently queried books while it falters for the tail queries. SOLAR on the other hand is more robust this phenomenon.
5.2 EXTREME CLASSIFICATION DATASETS
Let us now shift our focus to the 3 largest multi-label learning datasets available on the XML-Repo, namely Amazon-3M, Amazon-670K and Wiki-500K datasets with 3M, 670K and 500K labels respectively. The statistics of these datasets are available on the repository.
Hypper-araametes: For Amazon-3M, the hyper-parameters remain the same as the book recom- mendation dataset. For the Wiki-500K and Amazon-670k datasets, we use the latest versions with dense 512-dimensional inputs as outlined in (4) Since the input now much lower-dimensional than the sparse versions of the same datasets, we train K = 32 models in parallel with B = 20K, thereby making the overall dimension 640K as opposed the 480K before. We report the standard P@ 1, P@3, and P@5 metrics and perform two levels of sparsification for all 3 datasets; m 50 in addition to the previous m 100.
Embedding Models
Other Baselines
Dataset
Metrie
SOLAR (m==100)
SOLAR (m=50)
AnnexML
SLEEC
FyC
Parabel
Plastre XML
SLICE
P@1
60.92
60.52
56.81
30.86
46.86
59.34
55.00
59.89
Wiki-500K
P@3
46.94
46.56
36.78
20.77
31.29
39.05
36, 14
39,89
P@5
45.32
45.28
27.45
15.23
25.17
29.35
27.38
30.12
P@1
34.37
34.19
26.36
18.77
24.47
33,93
28.51
37.77
Amz-670K
P@3
32.71
32.51
22.94
16.5
20.44
30.38
26.06
33.76
P@5
32.55
32.46
20.59
14.97
17.13
27.49
24.17
30.70
44.89
44.61
41.79
47.51
43.83
Amz-3M
P@0
42.36
42.08
44.68
P@B
41.03
40.69
35.98
42.58
40.09
Table 4: SOLAR vs popular Extreme Classification benchmarks. Embedding models AnnexML and SLEEC clearly underperform compared to SOLAR. SOLAR even outperforms the state-of-the-ar non-embedding baselines like Parabel and Slice. The gains in P@5 are particularly huge (45.32% vs 31.57%). SLEEC and SLICE do not scale up to 3M labels (corroborated on XML-Repo).
8

---

Published as a conference paper at ICLR 2021
Dataset
SOLAR (m=100)
SOLAR (m=50)
SLICE
Parabel
Pfastre XML
Training (hrs)
2.52
2.52
2.34
6.29
11.14
Wiki-500K
Eval (ms/point)
0.76
1.37
2.94
6,36
Training (hrs)
1.19
1.19
1.92
1.84
2.85
Amz-670K
Eval (ms/point)
2.56
1.58
3.49
2.85
19.35
Training (hrs)
5.73
5.73
5.39
15.74
Amz-3M
Eval (ms/point)
2.09
1.87
1.72
4.05
Table 5: Training and Evaluation speeds against the fastest baselines.
Since the labels do not have annotations for these datasets, we cannot aspire to train Siamese models like DSSM and SNRM here. Hence we choose compare against the popular
Baselines:
embedding models AnnexML (29) and SLEEC (3) in addition to other Extreme Classification
benchmarks like the pure tree-based Xfa (15), and 1-vs-all model Parabel (25) and also
against the recent NN-graph based SLICE (14 which is the state-of-the the-art for the first 2 datasets.
Results: Comparison of precision for SOLAR against both embedding and non-embedding baselines are shown in table We use the reported numbers for all available baselines. However, AnnexMI. and SLEEC do not have reported scores for the smaller datasets with dense inputs. We run the official C++ and MATLAB packages for either of them. It is noteworthy that the training and evaluation for SLEEC are rather slow even though the model size is smaller with dense inputs. Hence, SLEEC could not be scaled to the large 3M class dataset. This fact is independently verified on the repository. It is clear that SOLAR outperforms the state-of- sfate-of-the-arrd because SLICE has been very successful on Bing Search for query suggestion (improving the trigger coverage by 52%, mores so for tail queries).
offthe-ard art baselines, including SLICE which is noteworthy
The speed comparison for SOLAR against the fastest baselines is shown in table We SOLAR either matches or surpasses the best ones on both training and inference. Parabel closes in on SOLAR on Amz-3M while SOLAR is much faster on Wiki-500K. PfastreXML the slowest.
that
Ablation Study on Choice of B and K: Choosing an appropriate number of partitions K and buckets B is very important as it causes trade-off between precision and speed. We usually have diminishing gains in precision with increasing B and K at cost of training and inference speeds. Hence, to strike good balance, we start with B 10K buckets and increment by 10K until the gains are insignificant. Similarly, we increase K in powers of 2 until convergence in precision performance. Table 6/shows the performance trend for Amazon-670K dataset. We notice that 20K, 32 is an optimal setting for this dataset.
K=8
K=16
K=32
P@1
P@3
P@5
Time (ms)
P@1
P@3
P@5
Time (ms)
P@1
P@3
P@5
Time (ms)
B=30K
31.34
28.45
0.647
33.27
31.34
30,90
0.908
33,99
32.39
32.31
1.65
B=20K
30.2
28.25
27.31
0.621
32.55
30.69
33.74
32.06
31.78
1.52
B=10K
27.99
25.58
24.36
0.97
29.72
27.85
27.04
1.326
32.07
30.22
29.65
1.39
Table 6: Effect of B, K on PW1/3/5 for Amz-670K dataset (with 25). linearly and K exponentially and choose an optimal trade-off between precision and inference time (shown in ms/point).
We increment B
CONCLUSION
This paper proposes SOLAR to learn high-dimensional sparse vectors against dense low-dimensional ones. Sparse vectors are conducive to efficient data structures like inverted-indexes for large scale Information Retrieval. However, training high dimensional vectors has major bottlenecks. Through some elegant design choices, SOLAR ensures that the high dimensional embeddings are trainable in a distributed fashion with crtoo-Comunication. Additionally, SOLAR enforces near equal inference times for all queries by load-balance balancing the inverted- of product recommendations and extreme classification datasets, SOLAR outperforms the respective mate-ooftthe-as methods by large margin on precision and speed.
When applied to multitude

---

Published as a conference paper at ICLR 2021
REFERENCES
[I] Rahul Agrawal, Archit Gupta, Yashoteja Prabhu, and Manik Varma. Multi-label learning with millions of labels: Recommending advertiser bid phrases for web pages. In Proceedings of the 22nd international conference on World Wide Web, pages 13-24, 2013.
[2] Ricardo Baeza-Yates, Berthier Ribeiro-Neto, et al. Modern information reirieval, volume 463.
ACM press New York, 1999.
[3] Kush Bhatia, Himanshu Jain, Purushottam Kar, Manik Varma, and Prateek Jain. Sparse local embeddings for extreme multi-label classification. In Advances in neural information processing systems, pages 730-738, 2015.
[4] Avradeep Bhowmik, Nathan Liu, Erheng Zhong, Badri Bhaskar, and Suju Rajan. Geometry aware mappings for high dimensional sparse factors. In Artificial Intelligence and Statistics, pages 455 2016.
[5] Wei Bi and James Kwok. Efficient multi-label classification with many labels. International Conference on Machine Learning, pages
2013.
[6] Moses S Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 380-388, 2002.
[7] Yao-Nan Chen and Hsuan-Tier Lin. Feature- aware label space dimension reduction for multi- label classification. In Advances in Neural Information Processing Systems, pages 1529-1537, 2012.
[8] W Bruce Croft, Donald Metzler, and Trevor Strohman, Search engines: Information retrieval in practice, volume 520.
[9] Jacob Devlin, Ming-Was Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint: 1810.04805, 2018.
[10] Manaal Faruqui, Yulia Tsvetkov, Dani Yogatama, Chris Dyer, and Noah Smith. Sparse overcomplete word vector representations. In Proceedings of the 53rd Annual Meeling of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 1491-1500, 2015.
[11] Chuan Guo, Ali Mousavi, Xiang Wu, Daniel N Holtmann Rice, Satyen Kale, Sashank Reddi, and Sanjiv Kumar. Breaking the glass ceiling for embedding- based classifiers for large output spaces. In Advances in Neural Information Processing Systems, pages 4944-4954, 2019.
[12] Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In Proceedings of the Thirteenth International Conference Artificial Intelligence and Statistics, pages 297-304, 2010.
[13] Elad Hoffer, Itay Hubara, and Daniel Soudry. Fix your classifier: the marginal value of training the last weight layer. International Conference on Learning Representations, 2018.
[14] Himanshu Jain, Venkatesh Balasubramamian, Bhanu Chunduri, and Manik Varma. Slice: Scal- able linear extreme classifiers trained on 100 million labels for related searches. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, 2019.
[15] Himanshu Jain, Yashoteja Prabhu, and Manik Varma. Extreme multi-label loss functions for recommendation, tagging, ranking & other missing label upplications. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 935-944 2016.
[16] RichardSocher JeffreyPennington and ChristopherD Manning. Glove: Global vectors for word representation. Citeseer.
[17] Gregory Koch. Siamese neural networks for one-shot image recognition. 2015.
[18] Brian Kulis and Trevor Darrell. Learning to hash with binary reconstructive embeddings. In Advances in neural information processing systems, pages 1042-1050, 2009.
10

---

Published as a conference paper at ICLR 2021
[19] Alireza Makhzani and Brendan Frey. K-sparse autoencoders. arXiv preprint arXiv:1312.5663, 2013.
[20] Tharun Kumar Reddy Medini, Qixuan Huang, Yiqiu Wang, Vijai Mohan, and Anshumali Shrivastava. Extreme classification in log memory using count-min sketch: A case study of amazon search with 50m products. In Advances in Neural Information Processing Systems 32, pages 13265-13275. 2019.
[21] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean, Distributed repre- sentations of words and phrases and their compositionality. In Advances in neural information processing systems, pages 31 3111-311 1-3119. 19, 2013.
[22] Maxim Naumov, Dheevatsa Mudigere, Hao-Jun Michael Shi, Jianyu Huang, Narayanan Sun- daraman, Jongsoo Park, Xiaodong Wang, Udit Gupta, Carole-Jean Wu, Alisson Azzolini, et al. Deep learning recommendation model for personalization and recommendation systems. arXiv preprint arXiv: 1906,0009,, 2019.
[23] Priyanka Nigam, Yiwei Song, Vijai Mohan, Vihan Lakshman, Weitian Ding, Ankit Shingavi, Choon Hui Teo, Hao Gu, and Bing Yin. Semantic product search. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2876 2885, 2019.
[24] Federico Pernici, Matteo Bruni, Claudio Baecchi, and Alberto Del Bimbo. Fix your features: Stationary and maximally discriminative embeddings using regular polytope (fixed classifier) networks. arXiv preprint 1rXiv:1902.10441] 2019.
[25] Yashoteja Prabhu, Anil Kag, Shrutendra Harsola, Rahul Agrawal, and Manik Varma. Parabel: Partitioned label trees for extreme classification with application dynamic search advertising. In Proceedings of the 2018 World Wide Web Conference, pages 993-1002, 2018.
[26] Yashoteja Prabhu and Manik Varma. Fastxml: A fast, accurate and stable tree-classifier for extreme multi-label learning. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 263-272, 2014.
[27] Anshumali Shrivastava and Ping Li. Asymmetric Ish (alsh) for sublinear time maximum inner product search (mips). In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 27, pages 2321-2322 Curran Associates, Inc., 2014.
[28] Anant Subramanian, Danish Pruthi, Harsh Jhamtani, Taylor Berg-Kirkpatricke and Eduard Hovy. Spine: Sparse interpretable neural embeddings. arXiv preprint
2017.
[29] Yukihiro Tagami. Annexml: Approximate nearest neighbor search for extreme multi-label classification. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 455-464 2017.
[30] Manik Varma. Extreme Classification Repository. downloads wttpaadds/xxcxxMReossststoo httml
http://mankkvara..oo
2014.
[31] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998 6008, 2017.
[32] Jianfeng Wang, Jingdong Wang, Nenghai Yu, and Shipeng Li. Order preserving hashing for approximate nearest neighbor search. In Proceedings of the 21st ACM international conference on Multimedia, pages 133-142, 2013.
[33] Jingdong Wang, Ting Zhang, Nicu Sebe, Heng Tao Shen, et al. A survey on learning to hash. IEEE transactions pattern analysis and machine intelligence, 40(())769-799 2017.
[34] Yiqiu Wang, Anshumali Shrivastava, Jonathan Wang, and Junghee Ryu. Flash: Randomized algorithms accelerated over cpu-gpu for ultra-high dimensional similarity search. arXiv preprint arXiv:1709.01 190, 2017.
11

---

Published as a conference paper at ICLR 2021
[35] Kilian Weinberger. Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. Feature hashing for large scale multitask learning. In Proceedings of the 26th annual international conference on machine learning, pages 1113-1120, 2009.
[36] Jason Weston, Ameesh Makadia, and Hector Yee. Label partitioning for sublinear ranking, In International conference on machine learning, pages 181 181-189, 2013.
[37] Song Xu, Haoran Li, Peng Yuan, Youzheng Wu, Xiaodong He, and Bowen Zhou. Self-attention guided copy mechanism for abstractive summarization. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 1355-1362. Association for Computational Linguistics, July 2020.
[38] Ian EH Yen, Xiangru Huang, Wei Dai, Pradeep Ravikumar, Inderjit Dhillon, and Eric Xing. Ppdsparse: parallel primal-dual sparse method for extreme classification. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 545-553, 2017.
[39] Ian En-Hsu Yen, Xiangru Huang, Pradeep Ravikumar, Kai Zhong, and Inderjit Dhillon. Pd- sparse: A primal and dual sparse approach to extreme multiclass and multilabel classification. In International Conference on Machine Learning, pages 3069-3077, 2016.
[40] Hamed Zamani, Mostafa Dehghani, W Bruce Croft, Erik Learned-Mille and Jaap Kamps. From neural re-ranking to neural ranking: Learning a sparse representation for inverted indexing. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pages 497-506, 2018
[41] Xu Zhang, Felix X Yu, Sanjiv Kumar, and Shih-Fu Chang. Learning spread-out local feature descriptors. In Proceedings of the IEEE International Conference on Computer Vision, pages 4595-4603, 2017.
A ADDITIONAL RELATED WORK
A.1 LEARNING TO HASH
Learning to Hash (LTH) 333 has become a very integral research area for Near Neighbor Search recently. LTH learns a function y (1) for a vector x in such a way that f accomplishes two goals:
1) is a compact representation of a
2) nearest neighbor of x. x' has y' f(x' such that y' and y are close as possible if not same.
The 2nd condition is a restatement of the typical Locality Sensitive Hashing (LSH) (27 constraint. The major difference between LTH and LSH is the fact that f is learned.
Assume a scenario of learning d dimensional vector representations for product search and using Near Neighbor Search to lookup related products. An LSH algorithm maps each vector compact hash code. Many similar vectors can have the same hash code (LSH property). For a lookup, we compute the hash code of a query vector and perform true Near Neighbor Search with the candidates having the same hash code. All LSH algorithms assume the vectors to be distributed throughout the d-space. For example, the typical Simhash or Signed Random Projection (SRP) 66) algorithm samples a few hyper-planes randomly in the d-space. For each label vector, it performs dot product with all hyper-planes. For each plane, if the dot product of a label vector is 2 O, it assigns bit '1', otherwise '0'. In this way, if we sample P hyper-planes, we get P-bit hash code for every label vector. These label vectors obey the above two properties. However, if the vectors are not distributed uniformly in the d space, simhash miserably assigns lot of vectors to the same hash code making the Near Neighbor Search almost cxhaustive and slow.
propose to optimize two objective functions: 1) pairwise Hence, recent LTH Approaches 32
momilarity--reseervee 2) bucket balance by maximizing entropy of learned representations. However, no objective function has successfully solved the problem of imbalanced Hash functions.
SOLAR tackles this problem in a unique way by assigning load uniformly to each bucket and then repeating this process multiple times to ensure the distinguishability of dissimilar items. So hash
12

---

Published as a conference paper at ICLR 2021
tables are predetermined and fixed. We learn map the inputs to respective buckets which might return relevant candidates along with several irrelevant ones too. However, the final step of scoring and sorting climinates the irrelevant ones and accomplishes the overall functionality of hash table.
A.2 SNRM
While there have been plethora of dense embedding models, there is only one prior work called SNRM (Standalone Neural Ranking Model) (40) that trains sparse embeddings for the task of suggesting documents relevant to an input query (classic web search problem). In SNRM, the authors propose to learn a high dimensional output layer and sparsify it using a typical LI or L2 regularizer. Further, they opt for a weak-labelling strategy wherein each training sample has a query q, documents d1 and d2 and a binary label I suggesting whether d1 is more relevant to than d2 or vice-versa. The query and documents are passed through a Neural Network (RNN for a text input) to obtain their high-dimensional sparse embeddings. These embeddings are concatenated and hinge-loss is trained to learn the label l. After training, a standard inverted-index is constructed where all the products partitioned based on the non-zero indexes in their sparse embeddings. During inference, query is mapped to its sparse vector using the neural network and the non-zero indexes are obtained. All documents that have atleast one matching non-zero index with the query are shortlisted and scored to get the best predictions.
While SNRM looks good to be an efficient sparse alternative dense embeddings, imposing sparsity through regularization has multiple issues 1) The training and inference becomes too sensitive to the regularization weight. A larger regularization weight causes the embeddings to be too sparse and in all likelihood, we retrieve zero labels for many inputs. On the other hand, if the regularization weight very small, we end up retrieving too many candidates defeating the purpose of sparse embeddings. 2) The -eerted-index generally has lopsided label distribution causing imbalanced loads and high inference times. As we see in our experiments later, these issues lead to the poor performance of SNRM on our 1.67M product recommendation dataset.
B POSITIVE-ONLY ASSOCIATION
The random choice of buckets in constructing SOLAR embedding might pool totally unrelated labels into a bucket in each component, For example, two books titled "Velveteen Rabbit and 'Gravitational Waves' might be assigned the same bucket in a particular component of the embedding. Even though this pooling appears unconventional, it is necessary maintain the load balance of each bucket. However, the convergence of cross-entropy loss might come under the scanner in such a scenario.
Going by our training design, we choose to train that specific bucket with '1' if the input query is either related to 'Velveteen Rabbit' or 'Gravitational Waves'. By choosing an 'OR' operation over the true labels, we enforce the model reasonably fire up the bucket for all queries containing terms 'waves', "gravity', 'rabbit' etc. This is called 'positive-only association'. . Although single bucket might correspond to unrelated labels, the labels that have high scores in all of the K components would be truly related to the input.
C LAW OF DEFERRED ORTHOGONALITY OF LEARNED EMBEDDING
Lemma 2. For any two orthonormal basis matrices, aa a2 ag anl and B
[b1 b2 by ... bn] in the same vector space, there exists an orthogonal matrix such that A = PB.
Note that, since we construct fixed norm label vectors, orthogonal vectors form orthonormal basis vectors (up to constant norm factor multiplication..
Proof. Proving the existence is simple. We can perform an orthogonal projection of a; on to B as:
a; (a. b1)61 + +... ... (a: - bn )bn = Σ by b,)
13

---

Published as a conference paper at ICLR 2021
Query remington the science and prac- tice of pharmacy volumes
Query hello there a big sisters book of waiting
Query 3: beginners guide american mah
jongg how to play the game amp win
SOLAR Top Preds (All Correct)
SOLAR Top Preds (All Correct)
SOLAR Top Preds (only correct)
pharmacotherapy a patho-physiolose ap- proach 8th edition
im a big sister
winning american mah jongg strategies
guide for the novice player
the sanford guide to antimicrobial therapy
you and me new baby
fudge dice black 4 dice in plastic tube
sanford guides
goodman and gilmans the pharmacological
look at me new baby
the great mahjong book history lore and play
basis of therapeutics twelfth edition
basic and clinical pharmacology 12e lange
the berenstain bears new baby
beginners guide to american mah jongg how play the game amp win
basic science
GLaS Top Preds (All Correct)
GLaS Top Preds (All Wrong)
GLaS Top Preds (All Correct)
goodman and gilmans the pharmacological basis of therapeutics twelfth edition
just me and my little brother little critter picturebackr
winning american mah jongg strategies guide for the novice player the great mahjong book history lore and play
pharmaceutical calculations 13th edition
the day the crayons quit
basic and clinical pharmacology 12e lange basic science
the invisible boy
beginners guide to american mah jongg how to play the game amp win
the sanford guide to antimicrobial therapy 2013
the name jar
national mah jongg league scorecard large 2014
Table 7: Sample queries and the respective top predictions from SOLAR and DSSM+GLaS. The first
query a relatively frequent one. The second and third are relatively infrequent. We can see that on infrequent queries, SOLAR is more robust than dense embedding models.
Hence, a matrix P can be designed as P = (P.)) = (a+ bb) to obey A = PB. For the orthogonality, consider
=by ( (Eloxa)) b:
(PP*)/ (by ((by-as)en bi) k
b
Since A and B have orthonormal columns, we have Σ ( 1 and (PPT)} =67 858 This leads to the orthogonality of P.
PPT =I =I=-- = P
Theorem 2. Law of Deferred Orthogonality of Learned Embedding Given any positive semi- definite kernel S(...), and functions fi and ft. where fL is orthogonal. For any orthogonal function with the same input and range space as fL, there always exist a function f. such that S(fr(z), f(()) = ((f(x) R(y)).
Proof. Lemma 2 states that we can transform one orthonormal basis to another using an orthogonal matrix. Let the SOLAR's s label vectors be denoted by A R(v1), R(y2), ... R(gN)]. Here, R. refers to the random initialization matrix that maps label ids to sparse vectors. Similarly, the two-sided learnt label vectors are denoted by transformation matrix from B to A, i.e., A; = R(ys) = PB, = P((().) By virtue of orthogonality, P preserves the inner product objective function as follows:
JI(UN)]. Let P be Jr. [y2), (yr(()),
(P]r(x), P(r(w)) = (P)r(*), R(y))
Hence learning one function fSOLAR = P/r is equivalent to learning two function fr and fr. provided the columns of B are orthonormal.
14

---

Published as a conference paper at ICLR 2021
Method
P@1
P@5
Rec@50
Inference time (ms/point)
SOLAR (m=50)
96.71
83.56
63.007
0.548
Parabel 95.85
77.54
48.03
1.16
Table 8: SOLAR vs Parabel on Word Prediction for French to English translation.
D MACHINE TRANSLATION EXPERIMENTS
In this section, we make an innovative formulation of machine translation task. Translation can be perceived as classification task where given the input sentence (source language), we aim predict the words in the target language. This setup is unpopular mainly because a multi-label classifier is agnostic to the order which the words are predicted. Hence generating meaningful sentences not possible by pure classifier.
However, with the advent of Tranformer models with Copy Mechanism (37), we can train Target language model that takes in set of scrambled words and generates meaningful sentences from it. Training such an LM beyond the scope this paper. Assuming the existence of such a model, SOLAR can effectively solve the prediction of words challenge.
To re-iterate, we decouple translation into segments: 1) given a source language sentence, we first want predict all the words in the target sentence using SOLAR (and compare against SOTA Extreme Classification Algorithms) 2) use a pre-trained Target Language Model to generate meaningful sentences from predicted words.
To demonstrate this setup, we perform the word prediction task on French to English WMT dataset. The dataset has 2007723 matched sentence pairs from French English and 2677 additional pairs for evaluation. The source language French has a vocabulary size of 96270 and the target language English has vocabulary size of 83213. The mean sentence length in both languages is 35.
We use B = 5000 and K = 8 to train 40000 dimensional sparse SOLAR vectors. For inference, we use m 50 to obtain 400-sparse representation for each input sentence and retrieve the most relevant target language words. We additionally train Parabel with the same model size and compare the two on @@ 1/5 and Recall@50 (we truncate sentences maximum of 50 words in both languages). The results are in table
E ADDITIONAL INFORMATION FOR EXPERIMENTS
Baselines and our settings: The most natural comparison arises with recent industry standard embedding models, namely Amazon's 's Deep Semantic Search Model (DSSM) (23) and Facebook's ss Deep Learned Recommendation Model (DLRM) (22). DLRM takes mixed inputs (dense and sparse) and learns token embeddings through binary classifier for ad prediction. On the other hand, DSSM trains embeddings for semantic matching where we need to suggest relevant products for a user typed query. Because DSSM's goal aligns with this dataset, we compare SOLAR against it. For DSSM, we train a 763265 x 1600 embedding matrix where each word in the vocabulary has 1600 dimensional dense vector (to be consistent with the query sparsity of SOLAR). This matrix is shared across input and output titles (Siamese Network). We tokenize a title into words and lookup their embeddings and mean-pool pool them. This is followed by batch normalization and tanh activation. The resultant embeddings of both input and label titles are optimized to have high cosine similarity. For every input title, we also train minimize cosine similarity with one irrelevant label title (Negative Sampling).
We additionally incorporate orthogonality on DSSM label embeddings using the recent GLaS (II regularizer. We shuffle the entire training data, pick one label from each row and obtain the label vector matrix V. Then, we add a 2nd optimization function (in addition to the cosine similarity) of the form:
1 |CZ + +
ICLaS VIVVVV
(2)
2
where, C is the label co-occurrence matrix and Z the diagonal component of C. Hence, CZ- [i p(llj) and Z-1 [(.j] p(ll)).
15

---

Published as a conference paper at ICLR 2021
Another natural comparison arises with the lone sparse embedding model SNRM (40). We did try to use the available code for SNRM with our data generator. However, for reasons explained in section A.2] could not get any reasonable metrics even with very low regularization weight. The training would eventually culminate in the learned vectors being absolutely zero and thereby retrieving nothing from the inverted indexes. Even the label vectors end up being empty most of the time. We included SNRM results in the main paper.
Sample queries and predictions for SOLAR DSSM: SOLAR and + to assess the robustness to infrequent and spurious queries. For each test query, we sum up the frequency of each term in the corpus and sort the queries. We pick a random query from the top half and classify it as 'frequent query'. Similarly, we pick a random query from the bottom half and classify as an 'infrequent query'. We manually examined 10 such queries and listed three of them in table The first query was classified as frequent and the rest two as infrequent. We show the top predictions from either algorithm and the number of ground truth labels among them.
We perform qualitative assessment of
16


Reviews:
[{"review_id": "vLB1vMcHvCk", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies the problem of document retrieval using embedding based models. It argues that performing near-neighbour search on a large number of dense embeddings hurts performance and accuracy. As an alternative, the paper proposes SOLAR (SPARSE ORTHOGONAL LEARNED AND RANDOM EMBEDDINGS), a model which uses high-dimensional, ultra sparse embeddings, on which near-neighbour search can be done using simple lookup operations. In SOLAR the document labels are divided into equal chunks of sparse vector, and independent models are learned for mapping the query to each chunk. Hence, SOLAR could be trained on multiple GPUs in an embarrassingly parallel way without requiring any communication between the GPUs. The paper demonstrates the effectiveness of SOLAR by comparing it against strong baselines on various recommendation and extreme classification datasets. It also provides theoretical justification for SOLAR by showing how “one-sided” learning (i.e. fixing label embedding but learning mapping from query to label) is mathematically equivalent to “two-sided” learning (i.e. jointly mapping the label and query to a common space).\n\n#### Strong points: \n- **Well-motivated problem:** The paper does a very good job in motivating the problem, and highlighting the potential issue with dense embedding based models for large scale problems.\n- **Interesting result:** The paper argues the current convention for document retrieval is of using low dimensional dense embeddings. It is thus interesting that a method that against the standard notions could perform so well. \n- **Practical approach:** The proposed method seems to be simple to implement and easily scalable to a large number of parallel processes. This makes it practically valuable, especially in large-scale problems.\n- **Empirical evidence:** The paper provides strong empirical evidence. SOLAR outperforms industry standard embedding models while taking less query time on a \tProduct to Product Recommendation dataset. SOLAR also performs equally well on various extreme classification benchmarks.\n- The paper is well written and well structured. The theoretical results are also presented in an easy-to-follow format with consistent notations.\n\n#### Weak points: \n- **Potential Issues/Questions about the baselines:** I was wondering why are the baselines in Table 1 trained for only 5 epochs and not until convergence.  Can the performance of the baselines be improved by training more?\n- Similarly, I could not find information about the compute used during inference for the baselines and SOLAR. Can the inference speed of the baselines and SOLAR be improved by simply using more compute?\n- How sensitive is SOLAR with respect to the random seeds chosen for the K models? In other words, how much would the performance vary if we start with a different set of random seeds? \n \n#### Overall Recommendation:\nAlthough some information about the baselines is missing, overall I feel that the paper presents an interesting and practical method with strong empirical evidence. The paper is also well presented and is easy to follow. I currently support acceptance, but would form a final opinion based on the authors response.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "i_WKwiZ0Qg", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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 submission addresses the problem of learning document embeddings for document retrieval/recommendation tasks. Such tasks are characterized by a large number of documents and a large set of semantic class labels. In contrast to the now standard approach of representing documents and their labels as dense low dimensional embeddings, this work proposes to use sparse high dimensional embeddings for documents/labels and claims that the proposed approach has certain advantages over state of the art:\n\t1. It results in memory efficient and load balanced inverted index that facilitates fast index based lookup for retrieval  \n\t2. It enables distributed training on disjoint parts of the label vector and thereby speeding up training.\n\nUnlike the common approach of jointly learning the document and label embeddings, the proposed approach employs random binary embeddings for labels.  The label embeddings are high dimensional, sparse and mostly orthogonal by design. Each label in the training data is assigned a random K-sparse (only K > 0 bits are 1 and rest are 0) binary embedding independent of other labels as well as documents associated with the label and any semantic features (such as label text/title) the label might have. When they are sufficiently high dimensional, random embeddings ensure that the resulting inverted index is both balanced and  each bucket in the index has only a small number of labels. \n\nAs the label embeddings are random and each bit in the embedding is independent of all other bits by design, the embeddings can be partitioned into multiple disjoint blocks and each block can be used to independently learn partitioned embeddings for the documents. As this requires no communication between the different threads working on different blocks, training can be very fast.  \n\nTo keep the model size low, the work proposes to use a simple feed-forward network with only one hidden layer. There is one such network for each block and as they are trained independently, there is no sharing among the models.  Also, unlike other approaches, the proposed work doesn't make use of pre-trained word embeddings for training document embeddings. Instead it uses a feature hashing scheme to map the very high dimensional text data to reasonably low dimension. This eliminates the need to store word embeddings in memory. As feature hashing is memory efficient, the only structures that need to be in memory are the parameters of the feed-forward network and the inverted index thereby achieving memory efficiency at query time.\n\nThe submission presents experimental results comparing the proposed approach with a few baselines. The results are promising in terms of retrieval efficacy on multiple data sets.\n\nWhile the proposed approach is well engineered to achieve its twin goals of memory efficient and load balanced inverted index and distributed training, there are a few concerns about the methodology. \n\nFirst is about the rationale behind using random binary embeddings for labels. As observed earlier, such an embedding is independent of other labels as well as documents associated with the label and any semantic features (such as label text/title) the label might have. This seems to be a rather poor utilization of the rich semantic relatedness in the data for the sake of engineering gains. It can be argued that methods that ignore label correlations and other semantic relationships in the data are suboptimal.\n\nSecond concern is about the harmful consequences of random embeddings. As authors note in the appendix, unrelated labels fall into the same bucket. As each bucket has only a small number of labels, it is unlikely that a significant number of the labels assigned to a bucket are related. Therefore, it is unclear to this reviewer what does a bucket represent semantically other than being a collection of unrelated labels. Would this not affect the training of the classifier mapping documents to the bucket adversely? Empirical results seem to suggest otherwise, but this is an issue that needs both deeper theoretical and empirical investigation. Further, in the proposed approach, semantically related labels are likely to have dissimilar embeddings. This goes against the traditional view, particularly in semantic hashing, that similar labels should have similar embeddings. \n\nThird, authors claim that one-sided and two-sided learning are mathematically equivalent. This is true only when label embeddings are orthogonal. When the embeddings are low dimensional as in other methods, orthogonality of label embeddings is neither strictly guaranteed nor necessary. \n\nFourth, though authors don't say it, K and B are hyper parameters in the proposed approach. The tuning of these hyper parameters does add a significant overhead to training which is not shown in the experiments. So the claim on significant training speed gains over baselines is suspect. \n\nFifth, it is not clear whether the proposed work uses the same tokenization scheme as used by the authors of DSSM, viz Unigrams+Bigrams+Char Trigrams+OOV, in the experimental comparison with DSSM. As observed in DSSM paper, the choice of tokenization affects the retrieval accuracy significantly and a fair comparison would necessarily need to use the best tokenization scheme. \n\nSome suggested corrections:\n\t1. In figure 1, classifier 1 appears twice.\n\t2. In figures 1 and 3, k should be K.\n\t3. In the feature ablation study, the best performing setting is B = 30K, K = 32 (based on P@1, P@3, P@5 reported in Table 3) whereas the submission claims that B = 20K, K = 32  is the optimal setting.\n\t\n\n---\n\nBased on author feedback, here are some additional comments:\nI would like to thank the authors for their response to the reviews. As noted in my original review, the proposed method is a well-engineered method for a particular type of document recommendation problem. Empirical performance on the chosen data sets is impressive compared to the baselines. The claim on gain in training speed is suspect as there is a hyper parameter tuning step that has been not taken into account while reporting the speed gain over the baselines. Label correlations are not taken into account for label embeddings and might hurt the performance when there are not many documents in the training data for the long tail of labels in many real-world applications. Random embedding puts unrelated labels into the same bucket. Though this doesn't seem to hurt retrieval performance in the experiments reported in the submission thanks to filtering, it is not clear how training will be affected by this non-semantic bucketing of labels. Overall, I think the submission has several things going in its favor though there is substantial scope for strengthening. \n\nI've updated the rating. \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "afBIWiXqjPe", "reviewer": "AnonReviewer1", "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": "The work describes an extreme classification strategy which leverages the computational efficiency of multiclass (and multilabel) efficiency on small label sets (circa 10K) composed with the near-orthogonality of random sparse embeddings; while exploiting inherent parallelism of repeated independent instantiations of this primitive technique to mitigate statistical issues.  \n\nThe use of fixed near-orthogonal label embeddings is elegantly motivated, the computational properties of the technique are favorable (especially, amenability to inverted indexing), and the statistical performance is competitive.\n\nInference only gets passing treatment in the entire exposition, without any supporting rationale.   For instance, this reviewer was surprised that inference involves summing over predicted probabilities, rather than summing logs of predicted probabilities.  Essentially there are a collection of K independent predictors that we are trying to ensemble, a problem that has received lots of attention in the literature.  Making these connections would both help the reader and also potentially improve the technique.", "extra_scores": {}, "extra_text": {}}, {"review_id": "JyBFQngO3Q", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes to use high-dimensional sparse representation as opposed to low-dimensional dense representation for representing input text. This can be useful in information retrieval applications. The proposed model is evaluated on a \"product to product recommendation\" dataset and shows superior performance compared to the prior work.\n\nThe paper's strengths:\n1. Studying an important and interesting research problem (i.e., learning sparse representation for information retrieval)\n2. The paper is well-written and easy to follow. It is also well-structured. The results are well presented.\n\nThe paper's weaknesses:\n1. In several places there are some overclaims that should be fixed. For example, in abstract and introduction (when describing the paper's contributions) it is mentioned that \"In this paper, we make a novel and unique argument that sparse high dimensional embeddings are superior to their dense low dimensional counterparts.\" This is simply not true. As we go forward in the related work, we can see that the authors mention that SNRM [40] has exactly the same idea with empirical evidences. I think the authors should be more careful in claiming what is novel in their paper and what is borrowed from prior work.\n\n2. I think the weakest part of the paper is its evaluation. Here is the detailed comments:\n2.1. First of all, it has been only evaluated on a single dataset. It would be nice to see how the results can be generalized across datasets. Second, the task they used for evaluating their model is pretty artificial. There is no such real-world task as \"product to product recommendation\" and the experimental setting is not realistic at all. I believe using such synthetic datasets for evaluating models is acceptable when there is no good alternative publicly available. However, in this case, there are numerous large-scale datasets that can be used to evaluate the model. For example, MS MARCO dataset from Microsoft has been widely adopted by the research community and can be used for evaluating the model. A lot of Open-Domain QA datasets are available too. \n\n2.2. As mentioned multiple times in the paper, SNRM is the only paper with the same idea of learning high-dimensional sparse representation. However, the results reported in the table are strangely low. Looking at the SNRM paper (which was published in 2018, so it's not an old paper) we can see that it outperformed a lot of strong baselines on a number of benchmark. I understand that sometimes it is difficult to reproduce the results from some papers. However, the SNRM paper seems to be cited by over 60 papers and some of them reported its results on different datasets and they all reported a reasonable performance for the model. I personally think that the authors did not carefully select the sparsity hyper-parameter in the SNRM model. I also recommend the authors to include some non-neural baselines, such as BM25 and RM3 as they sometimes outperform neural network models on information retrieval related tasks.\n\n3. It is not clear how scalable the model is and actually I have some doubt about its scalability. What will happen when the number of items goes beyond tens of millions or even billions? These questions are important to be answered when a model is proposed for information retrieval or recommender systems.\n\nAll in all, I believe the authors are working on an interesting problem but the experimental results are not convincing and some claims should be changed. Some questions about scalability remain unanswered.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an approach to learn sparse embeddings for documents/labels which can be trained by using multiple GPUs in parallel, and are more amenable to nearest neighbor search. 

The paper certainly seemed to have botched  comparison to SNRM and requires to fix the claims in  section 5.1. 
But, the impressive performance on extreme classification tasks is quite convincing. Also, reviewers in general are quite enthusiastic about the paper. So we would recommend the paper for acceptance, but authors certainly need to take comments of reviewers into account (especially around baselines and comparison to SNRM).
Decision: Accept (Poster)