DeepXML: Scalable & Accurate Deep Extreme Classification for Matching User Queries to Advertiser Bid Phrases
Authors: Kunal Dahiya
Anshul Mittal
Deepak Saini
Kushal Dave
Himanshu Jain
Sumeet Agarwal
Manik Varma
Venue:  (2020)
Keywords: extreme multi label learning
extreme classification
deep extreme multi label learning
deep extreme classification
large output space

Abstract: The objective in deep extreme multi-label learning is to jointly learn feature representations and classifiers to automatically tag data points with the most relevant subset of labels from an extremely large label set. Unfortunately, state-of-the-art deep extreme classifiers are either not scalable or inaccurate for short text documents.  This paper develops the DeepXML algorithm which addresses both limitations by introducing a novel architecture that splits training of head and tail labels.  DeepXML increases accuracy by (a) learning word embeddings on head labels and transferring them through a novel residual connection to data impoverished tail labels; (b) increasing the amount of negative training data available by extending state-of-the-art negative sub-sampling techniques; and (c) re-ranking the set of predicted labels to eliminate the hardest negatives for the original classifier. All of these contributions are implemented efficiently by extending the highly scalable Slice algorithm for pretrained embeddings to learn the proposed DeepXML architecture. As a result, DeepXML could efficiently scale to problems involving millions of labels that were beyond the pale of state-of-the-art deep extreme classifiers as it could be more than 10x faster at training than XML-CNN and AttentionXML. At the same time, DeepXML was also empirically determined to be up to 19% more accurate than leading techniques for matching search engine queries to advertiser bid phrases.

Under review as a conference paper at ICLR 2020
DEEPXML: SCALABLE & ACCURATE DEEP EXTREME CLASSIFICATION FOR MATCHING USER QUERIES TO ADVERTISER BID PHRASES
Anonymous authors Paper under double-blind review
ABSTRACT
The objective in deep extreme multi-label learning is to jointly learn feature repre- sentations and classifiers to automatically tag data points with the most relevant subset of labels from an extremely large label set. Unfortunately, state-of-the- art deep extreme classifiers are either not scalable or inaccurate for short text documents. This paper develops the DeepXML algorithm which addresses both limitations by introducing a novel architecture that splits training of head and tail labels. DeepXMI. increases accuracy by (a) learning word embeddings on head labels and transferring them through a novel residual connection to data impov- erished tail labels; (b) increasing the amount of negative training data available by extending state-of-the-ar negative sub-sampling techniques; and (c) re-ranking the set of predicted labels to eliminate the hardest negatives for the original clas- sifier. All of these contributions are implemented efficiently by extending the highly scalable Slice algorithm for pretrained embeddings to learn the proposed DeepXML architecture. As a result, DeepXML could efficiently scale to problems involving millions of labels that were beyond the pale of state-of-the-arr deep extreme classifiers as it could be more than 10x faster at training than XML-CNN and AtIentionXMI.. At the same time, DeepXMI. was also empirically determined to be up to 19% more accurate than leading techniques for matching search engine queries advertiser bid phrases. Source code for DeepXML can be downloaded from (Anonymous 2019
INTRODUCTION
Objective: This paper develops the DeepXML algorithm for deep extreme multi-label learning applied to short text documents such as web search engine queries. DeepXML is demonstrated to be significantly more accurate and an order of magnitude faster to train than state-of-the-art deep extreme classifiers XML-CNN (Liu et al. 2017) and AttentionXMLL (You et al. 2018). As a result, DeepXML could efficiently train problems involving millions of labels beyond the scaling capabilities of leading deep extreme classifiers This allowed DeepXML to be applied to the problem of matching millions of advertiser bid phrases user's query a popular web search engine where it was found to increase prediction accuracy by more than 19 percentage points compared the leading techniques currently in production.
single GPU that were
Deep extreme multi-label learning: The objective in deep extreme multi-label learning is to learn feature representations and classifiers to automatically tag data points with the most relevant subset of labels from an extremely large label set. Note that multi-label learning is a generalization of multi-class classification which aims to predict single mutually exclusive label.
Notation: Throughout the paper: N refers to number of training points, refers to representation dimension, and T. refers to number of labels. Additionaly, Y refers the label matrix where yij if 8thh label is relevant tth instance, and ( otherwise. Please note that differences in accuracies reported in absolute percentage points unless stated otherwise.
Matching queries to bid phrases: Web search engines allow ads to be served for not just queries bidded on directly by advertisers, referred to as bid phrases, but also for related queries with matching intent. Thus matching query that just entered by the user to the relevant subset of millions of

---

Under review as a conference paper at ICLR 2020
advertiser bid phrases in milliseconds is an important research application which forms the focus of this paper. DeepXML reformulates this problem as an extreme multi-label learning task by treating each of the top 3 Million monetizable advertiser bid phrases classifier to predict the relevant subset of bid phrases given an imput query. For example, given the user query "what is diabetes type 2" input, DeepXML. predicts that ads corresponding the bid phrases is type 2 diabetes mellitus", "diabetes type 2 definition", "do i have type 2 diabetes". etc. could be relevant to the user. Note that other high-impact applications have also been reformulated as the extreme classification of short text documents such as queries, webpage titles, etc. For instance, (Jain al. 2019) applied extreme multi-label learning to recommend the subset of relevant Bing queries that could be asked by a user instead of the original query. Similarly, extreme multi-label learning could be used predict which subset of search engine queries might lead to click on webpage from its title alone for scenarios where the webpage content might not be available due to privacy concerns, latency issues in fetching the webpage, etc.
separate label and learning deep
State-of-the-an extreme classitiers: Unfortunately, ofate-of-the-art extreme classifiers are either not scalable or inaccurate for queries and other short text documents, In particular, leading extreme clas- sifiers based on bag-of-words (BoW) features (Prabhu et al. 2018b) and pretrained embeddings (Jain et al. 2019) are highly scalable but inaccurate for documents having only or 4 words. While feature 2017:WWieiig engineering (Arora 2017] Joulinn et al. 2017; WWeting & Kiela| 2019). including taking subwword
tokens, bigram tokens, etc can ameliorate the problem somewhat, their accuracy still lags that of deep learning methods which learn features specific to the task at hand. However, such methods, as exemplified by the state-of-the-art XML-CNN (Liu et al.] 2017) and AttentionXMI (You et al., 2018), can have prohibitive training costs and have not been shown to scale beyond million labels on a single GPU, At the same time, there is a lot of scope for improving accuracy as XML-CNN and AttentionXML's architectures have not been specialized for short text documents.
Tail labels: is worth noting that all the computational and statistical complexity in extreme classification arises due to the presence of millions of tail labels each having just a few, often single, training point, Such labels can be very hard to learn due to data paucity. However, in most applications, predicting such rare tail labels accurately is much more rewarding than predicting common and obvious head labels. This motivates DeepXML to have specialized architectures for head and tail labels which lead to accuracy gains not only in standard metrics which assign equal weights to all labels but also in propensity scored metrics (Jain et al. 2016) designed specifically for long-tail extreme classification.
XeLL DeepXML improved both accuracy and scalability over existing deep extreme classifiers by partitioning all L labels into small set of head labels, with cardinality less than O.1L, containing the most frequently occuring labels and a large set of tail labels containing everything else. DeepXML first represented document by the tf-idf weighted linear combination of its word- embeddings as this architecture was empirically found to be more suitable for short text documents than the CNN and attention based architectures of XML-CNN and Xttention respectively. The word-vector embeddings of the training documents were learnt on the head labels where there was enough data available to learn good quality representation of the vocabulary. Accuracy was then further boosted by the introduction of a novel residual connection to fine-tune the document representation for head labels. This head architecture could be efficiently learnt on single GPU with a fully connected final output layer due to the small number of labels involved. The word-vector embeddings were then transferred the tail network where there wasn't 't enough data available to train them from scratch. Accuracy gains could potentially be obtained by fine tuning the embeddings but this led to a dramatic increase in the training and prediction costs. As an efficient alternative, DeepXML achieved of-te-of-the-art accuracies by fine tuning only the residual connection based document representation for tail labels. number of modifications were made to the highly scalable Slice classifier (Jain) et al. 2019) for pre-trained embeddings to allow it to also train the tail residual connection without sacrificing scalability, Finally, instead of learning an expensive ensemble of base classifiers to increase accuracy (Prabhu et al.) 2018b; You et al.] 2018). DeepXML improved performance by re-ranking the set of predicted labels to eliminate the hardest negatives for the base classifier with only a 10% increase in training time.
Results: Experiments on medium scale datasets of short text documents with less than a million labels revealed that DeepXML's 's accuracy gains over XML-CNN and AttentionXML could be up to 3.92 and 4.32 percentage points respectively in terms of precision @ k and up to 5.32 and 4.2 percentage points respectively in terms of propensity-score precision @ kt At the same time, DeepXML could
2

---

Under review as a conference paper at ICLR 2020
be up to x and 41x faster to train than AML-CNN and AttentionXMML respectively on these datasets using a single GPU. Furthermore, XML-CNN and AttentionXML were unable to scale to a proprietary dataset for matching queries to bid phrases containing 3 million labels and 21 million training points on which DeepXML trained in 14 hours on a single GPU. On this dataset, DecpXML was found to he least 19 percentage points more accurate than Slice, Parahel (Prabhu al. 2018b). and other leading query bid phrase-matching techniques currently running in production.
This paper makes the following contributions: (a) It proposes the DeepXML ar- chitecture for short text documents that is more accurate than state-of-the-art extreme classifiers; (b) it proposes an efficient training algorithm that allows DeepXML to be order of magnitude more scalable than leading deep extreme classifiers; and (c) it demonstrates that DeepXML. could be significantly better matching user queries to advertiser bid phrases as compared leading techniques in production on a popular web search engine. Source code for DeepXML. and the short text document datasets used in this paper can be downloaded from (Anonymous 2019).
Contributions:
2 RELATED WORK
Much work has been done in extreme multi-label classification which can be broadly categorized
in tWO categories: a) learning the classifier with pre-computed features (Agrawal al. 2013 Cissé
et al.
2013 Prabhu & Varma 2014, Yu et al. 2014, Weston et al. 2013 2013; Mineiro & Nikos 2014; Jain
al.
2016 2017: 2019 Yen et al. 2016 2018 [u al., 20166 Babbar & Schölkopf| 2017 2019
Niculescu- Mizil & Abbasnejad]
1017/appankokaa
& I'soumakas | Prabhu et al. [20 Sa b
Barezi et al.] 2019 Dasinskka et al. [2016), b) jointly learning feature representation along with the
classifier (Chen & Lin, [002 Balasubramanian & Lebanon 2012 Bi & Kwok 2013 Liu et al.
Demite et al. 2017] Wydmuch et al. 2018 Bhatia et al., 2015|
lagami| 2017 You et al., 2018
Krichene et al. 2019 Barezi et al. 2019). More extensive survey of extreme classification and deep
learning approaches can be found in section[A.5]jm the supplementary material.
Traditionally, extreme classification approaches used sparse BoW features due to fast & efficient feature computation as well as state-of-the-an performance for a large number of labels. However, for short text documents such as queries, which form the focus of the paper, deep learning representations are more effeetive than BoW (Jain et al. 2011)) Unfortunately, existing deep learning approaches for extreme classification yielding state-of ofute-of-the-rr the-art accuracy are not scalable, while scalable approaches have not been shown to yield state- ofe-te-rttttttto accuracy. In particular, XML-CNN, acheives state-of- the-art accuracy on short text documents but have not been shown to scale beyond million labels, whereas AttentionXXML was found to be slightly more scalable but less accurate as shown in table [ Scalability: Deep learning techniques have been very successful and comprehensively beaten BoW features in small output space (Kim) 2014: Yang et al.) 2016). Unfortunately, the scalablity of such techniques degrades in extreme multi-label (XML) setting as the final fully connected layer leads to cost linear in number of labels (Liu et al. 2017). Traditional approach to solve this problem is negative sampling (Mikolov et al. 2013). Unfortunately, at the extreme scale, negative sampling has to be applied more aggressively as demonstrated in Fig 5] in the appendix. To eliminate this
problem, many approaches have been proposed such as tree based (Prabhu et al.) 2018b] You et al.
2018 Mikolov et al. 2013 Jernite et al., (017)) and hashing based (Shrivastava & Li [014]] 40 Vijaya-
narasimhan al. (2014), approximate nearest neighbor sub-sampling techniques (Jain al. [009]]
Reddi et al. 2018). 9. Adding to that, prediction time complexity remains (dL), which is not suitable
for real-time predictions. Approaches such as Maximum Inner Product Search (Yen et al. 2018) and
Local Sensitive Hashing
Aiculescu-Mizil & Abbasnejad 2017) can speed-up up one-vs.-al inference
but it leads to further loss in accuracy when applied post-training.
Accuracy: Tail labels are harder to predict as compared to head labels due to training data scarcity but might also be more informative and rewarding in XMI. setting. For instance, predicting tag "Artificial intelligence researchers" could be more informative than tag "1954 deaths" on Wikipedia page of "Alan Turing". Hence, propensity based precision and nDCG are the focus of the paper. (Wei& & Li 2018) demonstrates that trimming tail labels leads to marginal decay in performance on vanilla metrics. However, a) trimming tail labels lead to loss in propensity based metrics, b) this approach has been demonstrated scale to z 30K labels only. Researchers have also tried to improve performance on tail labels by directly optimizing propensity scored metrics (Jain et al. 2016), posing learning in the presence of adversarial perturbations (Babbar& & Schölkopf] 2019) and treating tail labels as outliers (Xu et al. 2016). Although, these approaches boost performance on tail labels, however they are not well suited for short text documents due to, a) support only for fixed
3

---

Under review as a conference paper at ICLR 2020
features and, b) large training and prediction time.
Matching user queries bid phrases: Approaches in this domain can be categorized as embed-
dings based (Jain et al., 2019). sequence-to-ssqquene models (Gao et al., 2012. Jones et al. 2006 Riezler & Liu, 2010; 0 He et al., 2016; Lee et al. 2018) Lian et al. 2019) and query graph based models (loannis al. 2008). Unfortunately, the trigger coverage, suggestion density and quality of recommendations could be poor for many of these techniques. For instance, query graph based methods only recommend suggestions for previously coverage, Additionally, Sequence-fo-sequene
triggers thereby limiting their trigger models suffers from expensive training and prediction cost. Although, efficient structures such as trie (Lian et al. 2019) have been deployed reduce output complexity, however, at the cost of limited bid phrase coverage.
Transfer
jANNS
Cosine Sim.
ANNS
Label Shortlist
Label Weights (W)
dxLt
Embedding Matrix (E) Vxd
Label Weights (Wh) d=I.h
Embedding Matrix (E) Vxd
f(x)
(x(x)
f(x)
(x))
ReLU
Residual
ReL.U
Residual
Dets
X 6 nV
Dropout
Block
R
Dropout
Block
DeepXML-h
DeepXML-t
Figure 1: Architecture of DeepXML. with DeepXML-h for head labels and DeepXMI.-t for tail labels. Residual block is sequence of linear transformation, Batch Normalization, ReLU and Dropout operations. Here, refers to matrix-vector multiplication. Gradients are not propagated through dotted lines. Please refer to Fig. for Deep architecture with an intuitive example.
DEEPXML
State-of-the oftth-rr- deep extreme classifiers neither scalable nor accurate for short text documents because: (a) representations learnt through CNNs (XML-CNN), LSTM+Attention (AttentionXMLL or context (Bert (Devlin et al.] 2018), Elmo (Peters et al., 2018), etc.) might not be accurate given limited tail data with only few words per document and might also be expensive to compute; and (b) they face scalability issues as the final fully connected output layer has millions of outputs making both the forward pass as well gradient backpropagation prohibitive for even a single training point. DeepXML addresses these limitations by using feature representation inspired by FastText (Joulin et al. (017) and an output layer inspired by Slice (Jain et al., 2019) as these have been demonstrated be both accurate and scalable for short text documents in their individual capacities. Unfortunately, combining FastText and Slice in straight forward fashion also turns out to be neither accurate nor scalable. The rest of this section details the design choices and modifications that needed be made in order to get the combination to work.
FastText represents a document as an efficiently computable linear combination of its (sub) word- embeddings making it highly scalable and well suited for extreme classification scenarios. Unfortunately, the FastText architecture linear and low-capacity thereby leading to loss in accuracy when there isn't 't vast amount of unsupervised data available for training. Furthermore, previous attempts (Wydmuch al., 2018) at learning FastTeex representations in supervised manner by replacing the fully connected output layer by a fixed Probabilistic Label Trees (PLT) extreme classifier (Jasinska et al. 2016) have led to even worse accuracies than XML- CNN and AttentionXML. Replacing the fixed tree PLT by learnt Slice improves accuracy somewhat but does not lead to state-of-the-an results and also greatly increases training time (please see ablation experiments in Section 5p. DeepXML addresses these limitations by adding non linearity and residual block to make up for the lack of FastTexxt's expressive power and training the word-vector embeddings using fully connected output layer small number of head labels rather than through Slice. Please refer to Figure [ for full architecture of DeepXML. Once the word-vector embeddings have been trained the head, they frozen and transferred to the tail where only the residual
XeL, Fast Slice:
4

---

Under review as a conference paper at ICLR 2020
block is fine tuned. This increases both accuracy as there isn't enough training data available to learn good quality word embeddings from scratch on the tail as well as scalability as fine-tuning the head embeddings the tail would prove too expensive large problems.
3.1 ARCHITECTURE AND TRAINING
DeepXMLL-h: Model parameters i.e. words embeddings, residual block and fully connected classifier are learnt with Binary Cross Entropy loss and Adam optimizer. DeepXML-h can be efficiently trained with fully connected final layer on a single GPU, as La (Label set containing head labeli)sontains only small subset of labels. In practice, the size of La does not grow beyond 0.2M even for datasets with millions of labels. Additionally, an approximate nearest neighbour search (ANNS) structure was trained over label centroids L of head labels. Note that label centroids (LG) are computed as:
LÍ Y please note that X' = fxx) + (x) from the Fig. This brings down inference cost of classifier from (dd Lal) to Odd + d'log LA,)), given |s] Lisl- Here, [s] is the size of label shortlist queried from ANNS structure during prediction which is kept as 300 in practice.
Unfortunately, ANNS trained over label centroids may lead to poor recall values when a single centroid is unable to capture diversity in training instances for labels with highly different contexts (say L,). For instance, 280K articles, ranging from scientists to athletes, are tagged with the 'living people' tag in WikiTitle-500k (Bhatia et al. 2016 dataset. Slice increases the shortlist improve recall; however, at the cost of 6x increase in prediction time. DeepX tackles this issue by allowing multiple representations for labels in T/,- Documents are clustered using the KMeans algorithm into c clusters for each label in this set. Therefore, e representatives for each label in T' computed. This leads to 5% increase in recall @ 300 and 6% precision @ @300 with shortlist of size 300. Clustering will lead to LA Lí + c| c label representations and hence could potentially lead to increased time complexity. However, clustering just the top labels into 300 clusters seems to work well in our experiments without significant change in training time, and it doesn't 't impact prediction time at all.
DeepXML-t: XeepXML still relies on Slice to fine-tune the residual block in the tail network and learn the weights in the fully connected output layer for millions of tail labels. Slice cuts down the time for both the forward pass and the gradient backpropagation from linear to logarithmic in the number of labels. Slice achieves this by first representing each label by the unit normalized mean of the feature vectors of the training points tagged with the label. It then learns an ANNS data structure (Malkov Yashunin 2016) over the label representations to determine the most likely labels for a given data point (please see the supplementary material for more detailed description). This technique was shown to efficiently scale to millions of labels and training points when the feature representation was fixed (Jain et al. 2019). Unfortunately, when the feature representation is being learnt, the ANNS data structure needs to be constantly updated as the label representations change with each training batch. This can lead to marked slowdown as maintaining the ANNS data structure can incur significant computational cost.
DeepXML speeds up training by redefining the label representation to be the unit normalized mean of the document representation before the residual block computed using the learnt word embeddings alone. This allows the ANNS data structure to be learnt just once after the word embeddings have been learnt on the head labels and before training starts on the tail. Unfortunately, this also leads to a loss in training accuracy as the label representation is now approximation to the true representation that should have been defined as the unit normalized mean of the document representations computed after the residual block. This loss in accuracy can be compensated by requiring Slice generate 3x more nearest labels to a given data point. This allowed the hard negative labels to now be present in the longer list but this significantly increased training time. It was empirically determined that more efficient strategy was to extend the shortlist by adding randomly sampled negative labels as this led to no loss in accuracy with only a minimal increase in training time.
3.2 PREDICTION
Initially, classifier scores and ANNS scores from both DeepXML-h and DeepXML-t are merged in a single vector ÿ. As demonstrated in Fig. I ýeffh is the classifier score (logit) from DeepXML-h and Yanns-A is the cosine similarity from ANNS-h. Similarly, Sas-e is the classifier score from DeepXML-1 and ý Yann-t & is the cosine similarity from ANNS-1. The final DeepXML. score vector (ý)
5

---

Under review as a conference paper at ICLR 2020
is computed as follows:
- - (1 ([Bannss-ni Mi ( (B
(1)
Note that -t - N ha and Vanns-t are sparse vectors, o is sparse-sign -iggood function computed only at non-zero entries and 3 E 1]. The average cost of prediction can be broken down into the following four components: a) computing dense feature representation: O(dy), b) generating a shortlist: (d log I.l).. e) computing classifier scores: (d]=))) Here, 7 the average number of features per document and s| is the shortlist size in ANNS.
3.3 DEEPXML-RE
Extreme classifiers such as Parabel (Prabbu et al. 2018b). AttentionXML You et 2018 learn mul- tiple models to get better prediction accuracy. However, this leads to increased training and prediction time (200% for both Parabel and AttentionXMML linearly with the number of models. Whereas, DeepXML-RE learns a re-ranker with training cost logarithmic in the number of labels by training over a shortlist of negative labels. Specifically, false positive labels predicted by DeepXMI. (a.k.a hardest negatives) are selected as negatives for DeepXML--RE. This leads to only 10 20% increase in training time. The architecture of DeepXML-RE same as DeepXML-t, i.c., a word embedding layer, residual block, and classifier. Model parameters are learnt with binary cross entropy loss and AdamseAdam optimizer. During prediction, DeepXML-RE evaluates on labels shortlisted by DeepXML only, thereby incurring a prediction cost of (d(s)).
4 EXPERIMENTS AND RESULTS
4.1 DATA SETS AND EVALUATION METRICS
Experiments carried out on the Query Bid phrases (Q2B-3M) dataset, with million labels, by mining the logs of popular search engine. Each user query was treated as an instance and relevant advertiser bid phrases became its labels. Unfortunately, only Slice (Jain et al.) (019) and Parabel (Prabhu et al.) 2018b) could scale to this dataset. DeepXMI. is also compared to state-of-the-ane methods for query keyword prediction such Simrank+ + et al. 20088 and Sequeeneett--equenee model based on BERT (Devlin et al. 2018 Lian al., 2019).
AmazonTTtles667k
DeepXMLL
Contribution to P.S
2.5
DeeptMM
XML CNN
1.5-
1.0-
Experiments were also carried out on four moderate size datasets (Anonymous (2019)). The applications consid- ered were tagging Wikipedia pages (WikiTitles-500K) suggesting relevant articles WWikiSeeAlsoTitles25500 and item-to-item recommendation of Amazon prod- uets [AmazonTiules-67000 and AmazonTitles-3M, Please refer to supplementary Table for dataset statistics. For these moderate size datasets DeepXML was compared to leading deep learning and BoW feature-based methods including XMLLCNN, Attention XML, Slice, AnnexML (Tagami 2017). XML (Jain et al. 2016)), Parabel (Prabhu et al., (0185). XT (Wydmuch et al. 2018), and DiSMEC (Babbar & Schölkopf 2017). The implementation of all algorithms was provided by the respective authors.
2
4
Label Frequency (Log scale)
Figure 2: Contribution P@5 by labels of a given frequency for miazzonTilees67000 The dotted vertical blue line marks the thresh- old to the right of which are head labels, and left of which are tail labels.
4.2 HYPERPARAMETERS
DeepXML has hyperparameters: (a) learning rate and epochs for DeepXML-h; (b) learning rate and epochs for DeepXML-t; (c) embedding dimensions (d); (d) shortlist size ([s)) and (e) threshold to split label set into head and tail labels. Results are reported for d = 300 and s = 300. The label threshold is chosen via cross-vall validation (please refer to section A.2 in the supplementary material). Binary cross-entropy loss and the Adam optimizer were used to update the model parameters. Please refer Table in the supplementary section for full parameter settings.

---

Under review as a conference paper at ICLR 2020
Table 1: DeepXML and DeepXML-RE accurate both vanilla and propensity scored metrics, and are faster at training. '-' used for the methods which are unable to seale. * used for the results provided by respective authors.
Dataset
Method
P@1
P
P@s
PSP@1
PSP@3
PSP@5
PSN@s
Training Time (hrs)
Prediction Time (ms))
Model Size (GB)
DeeXXML
19.62
13.76
10.79
19.73
10.43
12.4
13.23
0.94
1.03
1,02
WilciSeeAbo 350K
DespXMLLRRE
20.18
14.04
10.99
20.05
9.95
11.87
13.51
12.64
1.09
1.52
1.52
DeepXML-fr
19.82
13.95
11.02
19.87
9.26
11.25
13.01
11.98
3.91
0.48
0.44
XML-CNN
17.75
12.34
9.73
17.48
8.24
9.72
11.15
10.31
14.25
5.08
0.78
XT
16.55
11.37
8,93
16.47
7.38
8.75
10.05
9.46
3.25
4.53
2
Tes
18.13
12.87
10.29
18.52
8.63
10.78
12.74
11.63
0.22
1.33
0.97
AtteniioNML-1
6.56
AMtentionMMI.
15.86
10:43
8.01
14.86
6.39
7.2
8.15
7.64
30.44
14.88
4.07
DISMBC
16.61
11.57
9.14
16.72
7,48
9.19
10.74
9.99
6.63
7.63
0.09
7.56
AnnexML.
14,96
10.2
8.11
14.76
5.63
7.04
8.59
7.76
0.2
D.1
3.59
PlastreXMI,
15.09
10.49
8.24
15.59
9.03
9.69
10.64
10.52
0.51
3.17
5.22
DeepXML
DeepXMILAR RRE
45.26
24.34
16.94
31.21
18.76
18.1
18.06
21
4.63
3.49
2.47
Wikipedia 500K
DopXML--t
45.67
25.59
18.23
32,67
17.86
17.81
18,07
20.7
16.72
0.74
0.76
1.17
XT
39.44
21.57
15.31
27.65
15,23
15
15.225
17.59
3.89
3.89
3.3
28.07
16.78
12.28
22.87
15.1
14.69
15.33
17.67
0.55
1.11
1.5
AtentionMMI-
41.75
21.49
14.86
14.56
13.25
15.53
34.15
3.07
AltattinXML
42.89
22.71
15 15,89
23.93
15.12
14.32
14:22
16.75
102.4
8.79
9.21
DISMEC
39.89
21.23
14.96
27.32
15.89
15.15
15.43
17.86
23.95
8.57
0.35
Parahel
42.5
23.04
16.21
29.45
16.55
18.77
0.34
2.15
AmnexML
39.56
20.5
14.32
26.54
15.44
13,83
13.79
16.58
1.78
0.09
10.7
PfastreMML
30.99
18.07
13.09
23.88
17.87
15.4
15.15
18.46
3.07
7.75
16.85
DeepXMI.
38.38
34.32
31 11.25
27.63
28.98
1.42
1.12
2.09
DosXMML-RE
34.93
31
35,72
27.31
29.22
30.94
28.90
1.55
1.39
2,92
Amazon- Titles-670K
DeepXML-ir
38.42
34.47
31 .44
35.21
25.54
27.91
29.94
27.76
6.3
0.82
XML-CNN
35.02
31.37
28
31.94
21.99
24.93
26.84
24.67
23.52
1.36
SIJCCaaaastes Text
33,85
30.077
26-97
34..5
21.91
24.15
25.81
24.03
0.22
1.59
2.01
AttemtioXML-11
36,08
31.68
28.3
32.04
23.03
24.63
25.98
24.33
12.79
5.87
4,04
AMentionXML.
30.57
DiSMEC
39.84
35.63
32.68
36.58
24.84
27.64
30.46
Parabel
38
33.54
30.1
33,98
23.1
25.57
27.61
25.48
0.09
1.11
1.06
AnnexML
30.9
2.99
PfastreMMI.
32.88
30.54
28.8
31.85
26.61
27.79
29:22
27.59
0.99
9.31
5.32
DeepXML
38.36
36.45
34.
36.48
15.7
17.95
19.52
18.14
7.4
2.9
8.64
DespXML-RE
DeepXMI .7 XML-CNN
Title--hh
SLICE-FasIText
29.88
28.14
26.82
28.05
9.85
11.68
13:05
11.89
3.65
1.13
8.45
AttentionMML-1
AMtentioNMI.
DiSMEC
40.81
38.58
36.76
38.56
Parabel
40.97
38.56
36.68
38.44
11.4
13.69
15.4
14
1.94
1.26
13.4
AnnexMI.
PfastrcXML
27.58
27.76
27.5
28.37
20.02
21.95
23.29
21.99
12.56
22.55
23.3
4.3 RESULTS ON MODERATE SIZE DATA SETS
Table compares the performance of DeepXML and DeepXML-RE with state-of-the-art deep learning approaches namely XML-CNN and AttentionXML. DeepXML is upto percentage points more accurate than AML-CNN and AttentionXML and supplementary Fig demonstrate that tail labels contribute more DeepXML's predictions w.r.t other methods. Furthermore, DeepXML can be 2-4 percentage points more accurate than XML-CNN and AttentionXML. on vanilla precision and nDCG. Table also demonstrates that DeepXML. can be 33-42x faster to train as compared to XML-CNN and AttentionXMi respectively on a single GPU. DeepXMI.-RE can be scaled to Titles-M on one GPU and is able train with only a 10% increase in training time and 20% increase in prediction time from DeepXML compared to 200% increase in training and prediction time of AttentionXML from AttentionXML--I. This demonstrates that DecpXML and DeepXML-RE can outperform current state-of-the-al accuracy as well as scale to millions of labels Table shows that DeepXML and DeepXML-RE. can outperform sfate-of of off-the-rt based approaches well. Note that AmazonTitles-33 Pfasttee PfastreXML is 5.6 percentage points better than DeepXML as well as DeepXML-RE. for propensity-scone
propensity-scoree metrics. Additionally, Fig
metrics but incurs loss of 10 percentage points for vanilla precision, which is clearly unacceptable for real world tasks where both metrics are important. Please refer to Section A.3 the appendix for more discussion.
7

---

Under review as a conference paper at ICLR 2020
Table 2: Results Q2B-3M 3M. DeepXML-RE RE is 19% more accurate P@ than the second-best method.
Method
P@
P@3
P@5
N@3
N@5
PSP@1
PSP@3
PSP@5
PSN@3
PSN@5
DeepXML
70.99
33.7
21.72
82.26
84.15
61.18
83.55
76.72
79.33
DeepXML-RE
73.37
33.91
21.67
83.52
85.13
64,8
85.13
90.42
79.1
81.24
Parabel
54.29
27.15
17.94
64.56
66.98
43.09
61.66
55.1
58.07
Slice+CDSSM
53.23
27.53
18.56
65.08
68.26
42.35
64.51
74.14
56.94
61.09
Parahel-weighted
43.82
22.25
14.97
52.15
54.61
37.83
53.19
59.57
47.26
49.94
Seq2Seq
28.25
13.06
22.96
21.7
23.32
17.59
15.42
21.31
21.3
Simrank++
52.7
29.69
19.33
50.02
48.82
43.5
41.67
39.36
45.71
45.73
4.4
RESULTS ON Q2B
Table
indicates that DeepXMI.-RE upto 20-45 percentage points more accurate than the methods currently in production, Simrank++ and Seq2Seq respectively. Further, DeepXML-RE is also compared to other scalable extreme classifiers such as Parabel and Slice and is seen to be 19 and 20 percentage points more accurate respectively. Additionally, supplementary Table Sable ineluuess example documents which demonstrate that DeepXML can make accurate and diverse predictions.
includes
5 ABLATION, EXTENSIONS
This section discuss impact of feature represen- tations (DeepXML-SW, DeepXML-f) and classi- fiers (DeepXML-fr. DeepXML-ANNS, DeepXML-P, DeeDXML-NS). The detailed architectures included in section A.6 in the supplementary section.
Table 3: Ablation results for different feature representations and classifiers on Amazon Titazzoniille660KK DeepXML is ac- curate
alternate configurations.
Sub-word features: DeepXML can also exploit sub-word features (Joulin et al. 2017) for an additional 1% gain in precision demonstrated in Table
Method
P@1
P@5
PSP@1
PSP65
DeepXML
30.83
DeepXMI-RF -RE
39
31.85
27.31
30.94
Label split and classifier: DeepXML-fr refers to joint
DeepXML-P
37.07
28.75
23.29
26.54
DeepXML architecture, i.e. without splitting labels, trained with fully connected layer. As demonstrated in Table [ the proposed algorithm is more scalable and accurate tail labels w.r.t DeepXML-fr. DeepXML. could be up to 1-3% more accurate then DeepXMI.-NS & DeNNXMI-ANNS where the classifier is trained using negative sampling. Additionally, DeepXMI. was found be 1.3% more accurate than DeepXMLL-P which uses tree based classifier.
DeepXML-NS
35.71
29.93
24.26
DoepMML-E
34.8
27.53
21.29
23.23
DeeXMLLSW
28.6
DeepXML-ANNS
36.73
30.07
26.72
29.83
Slic>+BERT
26.99
22.05
16.75
20.27
SlicetSIF
30.82
Pre-trained features: DeepXML could be upto 10% more accurate than pre-trained representations such as FastText, BERT (Devlin et al. (018)) and
with Slice classifier (refer to Tables SIF (Arora 2017).
CONCLUSION
This paper developed DeepXML, an algorithm to jointly learn representations for extreme multi- label learning on text data. The proposed algorithm addresses the key issues of scalability and low accuracy (especially on tail labels and very short documents) with existing approaches such as Slice, AttentionXMIL, and XML-CNN, and hence improves on them substantively. Experiments revealed that DeepXML-RE. can lead to 1.0-4.3 percentage point gain in performance while being x faster training than XtIentionXMIL.. Furthermore, DeepXML. was upto 15 percentage points more accurate than leading techniques for matching search engine queries to advertiser bid phrases. We note that DeepXML's gains are predominantly seen to be on predicting tail labels (for which very few direct word associations are available at train time) and on short documents (for which very few words are available at test time). This indicates that the method doing especially well, compared to earlier approaches, at learning word representations which allow for richer and denser associations between words which allow for the words to well-clustered in meaningful semantic space, and hence useful and generalisable information about document labels extracted direct word co-occurrences observed is very limited. In the future we would like to better understand the nature of these representations, and explore their utility for other linguistic tasks.
when the number of
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
R. Agrawal, A. Gupta, Y. Prabhu, and M. Varma. Multi-label learning with millions of labels: Recommending advertiser bid phrases for web pages. In WWW, May 2013.
Anonymous. Source code and datasets for deepxml. In Anonymous, 2019.
Liang Y. Ma T. Arora, S. A simple but tough to beat baseline for sentence embeddings. In JCLR, 2017.
R. Babbar and B. Schölkopf. Dismee: Distributed sparse machines for extreme multi-label classifica- tion. In WSDM, 2017.
R. Babbar and B. Schölkopf. Data scarcity, robustness and extreme multi-label classification. ML, 2019.
K. Balasubramaniaa and G. Lebanon. The landmark selection method for multiple output prediction. In ICML, June 2012.
J. Barezi, I. D. W., P. Fung, and H. R. Rabiee. submodular feature-aware framework for label subset selection in extreme classification problems. In NAACL,
K. Bhatia, H. Jain, Kar, M. Varma, and P. Jain. Sparse local embeddings for extreme multi-label classification. In NIPS, December 2015.
K. Bhatia, K. Dahiya, H. Jain, Y. Prabhu, and M. Varma. The extreme classification repository: Multi-label datasets code, 2016. URL http://maaaiaaaaaa..rrr//d/odod/
XMLRepository.c htt.stttoootl..ll. html
W. Bi and J. T. Y. Kwok. Efficient multi-label classification with many labels. In ICML, June 2013.
Y. N. Chen and T. Lin. Feature-aware label space dimension reduction for multi-label classification. In NIP. Curran Associates, Inc., 2012.
M Cissé, N. Usunier, T. Artières, and P. Gallinari. Robust bloom filters for large multilabel classifica- tion tasks. In NIPS, December 2013.
J. Devlin, M. W. Chang, K. Lee, and K. Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805, 2018.
Gao, S. Xie, X. He, and A. Ali. Learning lexicon models from search logs for query expansion. In EMNLP, 2012.
Y. He, J. Tang, H. Ouyang, C. Kang, D. Yin, and Y. Chang. Learning to rewrite queries. In CIKM, 2016.
A. loannis, G. M. Hector, and C. C. Chi. Simrank++: Query rewriting through link analysis of the click graph. In WwW, 2008
H. Jain, Prabhu, and M. Varma. Extreme multi-label loss functions for recommendation, tagging, ranking and other missing label applications. In KDD, August 2016.
H. Jain, Balasubramanian, B. Chunduri, and M. Varma. Slice: Scalable linear extreme classifiers trained on 100 million labels for related searches. In WSDM, February 2019.
V. Jain, N. Modhe, and P. Rai. Scalable generative models for multi-label learning with missing labels. ICML, 2017.
K. Jasinska, K. Dembczynski, R. Busa-Fekete, K. Pfannschmidt, T. Klerx, and E. Hullermeier. Extreme f-measure maximization using sparse probability estimates. In ICML, June 2016.
Y. Jernite, A. Choromanska, and D. Sontag. Simultaneous learning of trees and representations for extreme classification and density estimation. In ICML, August 2017.
R. Jones, B. Rey, O. Madani, and W. Greiner. Generating query substitutions. In WWW. 2006.

---

Under review as a conference paper at ICLR 2020
A. Joulin, E. Grave, P. Bojanowski, and T. Mikolov. Bag of tricks for efficient text classification. In Proceedings of the European Chapter of the Association for Computational Linguistics, April 2017.
Y. Kim. Convolutional neural networks for sentence classification. EMNLP, October 2014.
W. Krichene, N. Mayoraz, S. Rendle, L. Zhang, X. Yi, L. Hong. E. Chi, and J. Anderson. Efficient training on very large corpora via gramian estimation. In ICLR, 2019.
M. C. Lee, Gao, and Zhang. Rare query expansion through generative adversarial networks in search advertising. In KDD, 2018.
Y. Lian, Z. Chen, J. Hu, K. Zhang, C. Yan, M. Tong, W. Han, H. Guan, Y. Li, Y. Cao, Y. Yu, Z. Li, X. Liu, and Y. Wang. An end-to-end generative retrieval method for sponsored search engine decoding efficiently into closed target domain. CoRR, 2019.
Liu, W. Chang, Wu, and Yang. Deep learning for extreme multi-label text classification, In SIGIR, 2017.
A. Y. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. CoRR, 2016.
T. Mikolov, I. Sutskever, K. Chen, G. Corrado, and J. Dean. Distributed representations of words and phrases and their compositionality. In NIPS, December 2013.
P. Mineiro and N. K. Nikos. Fast label embeddings for extremely large output spaces. CoRR, abs/1412.6547, 2014.
A. Niculescu-Mizil and E. Abbasnejad. Label filters for large scale multilabel classification. In AISTATS, 2017.
Y. Papanikolaou and G. Tsoumakas. Subset labeled lda for large-scale multi-labe classification. ArXiv, 2017.
A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin, A. Desmaison, L., Antiga, and A. Lerer. Automatic differentiation pytorch. In NIPS- W, 2017.
M. E. Peters, M. Neumann, M. lyyer, M. Gardner, C. Clark, K. Lee, and I.. Zettlemoyer. Deep contextualized word representations. NAACI, 2018.
Y. Prabhu and M. Varma. Fastxml: A fast, accurate and stable tree-classifier for extreme multi-label learning. In KDD, August 2014.
Y. Prabhu, A. Kag, S. Gopinath, K. Dahiya, S. Harsola, R. Agrawal, and M. Varma. Extreme multi-label learning with label features for warm-start tagging, ranking and recommendation. In WSDM, February 2018a.
Y. Prabhu, A. Kag, S. Harsola, R. Agrawal, and M. Varma. Parabel: Partitioned label trees for extreme classification with application dynamic search advertising. In WWW, April 2018b.
J. Reddi, S. Kale, F.X. Yu, D. N. H. Rice, J. Chen, and S. Kumar. Stochastic negative mining for learning with large output spaces. CoRR, 2018.
S. Riezler and Y. Liu. Query rewriting using monolingual statistical machine translation. Comput. Linguist., 2010.
A. Shrivastava and P. Li. Asymmetric 1sh (alsh) for sublinear time maximum inner product search (mips). In NIPS, 2014.
Y. Tagami. Annexml: Approximate nearest neighhor search for extreme multi-label classification. In KDD, August 2017.
S. Vijayanarasimhan, J. Shlens, R. Monga, and J. Yagnik. Deep networks with large output spaces. CoRR, 2014.
10

---

Under review as a conference paper at ICLR 2020
T. Wei and Y. F. Li. Does tail label help for large-scale multi-label learning. In IJCAI, 2018.
J. Weston, A. Makadia, and H. Yee. Label partitioning for sublinear ranking. In ICML, June 2013.
J. Wieting and D. Kiela. No training required: Exploring random encoders for sentence classification. In ICLR, 2019.
M. Wydmuch, K. Jasinska, M. Kuznetsov, R. Busa-Fekete and K. Dembezynski. A no-regret generalization of hierarchical softmax to extreme multi-label classification. In NIPS. Curran Associates Inc., 2018.
C. Xu, D. Tao, and C. Xu. Robust extreme multi-label learning. In Proceedings of the 22Nd International Conference on Knowledge Discovery and Data Mining, 2016.
Z. Yang, D. Yang, C. Dyer, X. He, A. Smola, and E. Hovy. Hierarchical attention networks for document classification. In NAACL-HLT, 2016.
E.H. I. Yen, Huang, K. Zhong, P. Ravikumar, and S. Dhillon. Pd-sparse: primal and dual sparse approach to extreme multiclass and multilabel classification. In ICML, June 2016.
E.H. I. Yen, X. Huang. W. Dai, I. Ravikumar, P.and Dhillon, and E. Xing. Ppdsparse: A parallel primal-dual sparse method for extreme classification. KDD, August 2017.
Yen, S. Kale, Yu, D. Holtmann R., S. Kumar, and Ravikumar, Loss decomposition for fast learning in large output spaces. In ICML, 2018.
R. You, S. Dai, Z. Zhang, H. Mamitsuka, and S. Zhu. Attentionxml: Extreme multi-label text classification with multi-label attention based recurrent neural networks. CoRR, 2018.
H. Yu, P. Jain, Kar, and I. S. Dhillon. Large-scale multi-label learning with missing labels. In ICML, June 2014.
W. Zhang, L. Wang, J. Yan, X. Wang, and H. Zha. Deep extreme multi-labed learning. ICMR, 2018.

---

Under review as a conference paper at ICLR 2020
Table 4: Dataset Statistics. Please note that in Q2B-3M dataset, character 3-grams and 4-grams tokens also included in vocabulary for DeepXML. DeepXML RE and Parabel. This increases average number of features per document.
Train
Labels
Number of Test Instunces
Average Labels per snmple
Average per
Average per instances
WikiSeeAAso Talll 350K
629:18
91414
352072
162491
2.33
5.24
2.73
WikiTilee-S00e S00K
1699722
185479
501070
722678
1.89
23,62
2.73
Amaoon TT0K-660K
485176
66666
6700991
150875
5.39
5.11
5.26
AmareeTirkes-5M
1712536
2812281
739665
36.18
Q2B-3M
21561529
1284191
3192113
6995038
A SUPPLEMENTARY
A.1
HYPERPARAMETERS OF DEEPXML FOR REPRODUCIBILITY
Table lists the parameter settings for different data sets. Experiments were performed with random-seed of 22 on a P40 GPU card with CUDA 10, CuDNN 7.4, and Pytorch 1.2 (Paszke et al.
2017
AmazonTittes-670K
AmazonTTtes:3M
32
DeepXMLL RE
PSP@5
DeepXML
Pg5
30
XML-CNN
40-
Precision@s
AttantionXMML-1
28
35-
26-
20-
15
22:
5.0
0.2
0.4
0.6
0.5
Percentage of most frequent labels
Figure 3: Variation of (Precision and Figure 4: Precision @5 in k(%) most frequent la- bels
Propensity scored Precision) with
Table 5: Parameter setting for Dee on different datasets. Dropout with probability was used for all datasets. Learning rate is decayed by Decay factor after interval of Decay steps. For HNSW, values of construction parameter M = 100, efC' = 300 and query parameter, ef 300. Denoted by 'T. DeepXML-h and DeepXMI.-t might take different values for some parameters. Note that DeepXMI.- uses shortlist of size 500 during training. However, shortlist of size 300 queried from ANNS is used prediction time for both DeepXML-h and DeepXML-L.
Learning Rate
Batch Size
Decay Factor
Decay Steps
Label Threshold
Shortlist
Datnset
Lg
[G,]
Epuchs
Size
WitiSeeAlsoTTiles-5555
52,245
252,205
25 1:0
0.005
10.002
255
0.5
14,71
5
3001500
WikTTitle-S00K
43,7845
25 250
0.005 10.002
255
0.5
14.7
25
3001500
AmazanTilles6700K
109,379
556,696
25 10
0.02
0.002
255
0.5
14,7
6
3001500
AmazonTTtles-3
165.722
2,645,458
250
0.007
10.002
255
0.5
14
75
300/500
Q2B-3M
160.651
3,019,249
815
0.02 0.002
512
0.5
412
25
300/500
A.2 SPLITTING INTO L1, AND T.
Label set L is divided into two disjoint sets, i.c. Ln, and L, based on the frequency of the labels. Labels with a frequency more than splitting threshold y are kept in set Ln and others Lt. The splitting threshold 7 is chosen while ensuring that most of the features (or words) are covered in documents that one at least one instances label in the set L;, and |ا, < 0.2.M. Two components trained
for DeepXML, Deep and DeepXML-t, strategies like clustering of labels, connected components labels in a graph were also tried, but the above-men mentioned strategy provides good results without any additional overhead. More sophisticated algorithms for splitting such as label clustering, may yield better results, however at the cost of increased training time.
L₁, and L,- Please note that other
12

---

Under review as a conference paper at ICLR 2020
Table 6: Qualitative comparision for DeepXML. on WikiTitles-500K datasct. Bold indicates correct predictions.
Document Text
Ground Truth
DeepXMI-rr
DeepXMI.
XML.-CNN
AttentionXMI.
Confederate Secret
1861 establish-
1865 disestab- 1865 disestab-
1865 disestab- lishments the Confeder- ate States of America. 1861 establishments
American films, English-language films, Military history of the Confederate States Amer- ica, 2011 tele- vision episodes, English-language television pro- gramming
Service
ments the Confederate Stutes of America, 1865 disestab-
lishments the Confederate States of Amer- ica. Government the Confed- erate States of America, 1861 establishments establishments in the Confed- erate States of America, Eco- nomic history Confodcrate States of America. Confederate
lishments in the Confederate States of Amer- ica. Government of the Confed- erate States of America, 1861
lishments in the Confederate States of America, American Civil espionage,
the Confed- erate States of America, American films, -aaguug- films, Black-and- white films
in the Confed- Defunct intelli- erate States of gence agencies, Government of the Confederate States of America, Military history of the Confederate States of America, Military units and formations established in 1861
America, Eco- nomic history of Confederate States of America, Military history the Confed-
States Americu monuments and memorials
erate States of America
Table 7: Qualitative comparison DeepXML on Q2B-3M dataset. Bold indicates correct predictions. Please note that system in production filters label internally and then outputs them.
Document text
Ground Truth Labels
what is diabetes type 2;what type diabetic
diabetes type 1 and 2:type diabetes I and 2:1ype and 2 diabetes, what causes type diabetes, diabetes type 2 definition;2 definition diabetes type;definition diabetes type 2:definition type diahetessdiabetes definition type 2:type 2 diabetes definition, do i have type diabetes, what is type 2 diabetes, what are type 2 diabetes, what is type 2 diabetes mellitus, type 2 diabetes
Method
Predicted labels
Seq2Seq
what is type ii diabetes, "whats type 2 diabetes"
SimRank++
type diabetes
Parabel
what type diabetes, type diabetes, what is type 2 diabetes symptoms, diabetes 2;2 diabetes,diahetes 2, whats type 2 diabetes, what is email marketing, what is type I and type 2 diabetes, what are the symptoms of diabetes type 2, what is anemiaranemia is what:anemia what is:what anemia what psd2, what identity theft is, what is google adwords. what is radiation therapy. what is emilys list, what is pork belly. what is qualcomm, what is smartboard, what is an unlocked phone, mpls, what is the invoice price
DeepXML
what is type 2 diabetes, what is a type 2 diabetes, type 2 diabetes, what are type diabetes, what the type 2 diabetes, do have type 2 diabetes, "whats type 2 diabetes", what type 2 diabetes mellitus, diabetes type 2 defini- tion;2 definition diabetes type:definition diabetes type 2;definition type 2 diabetes;diabetes definition type 2;type 2 diabetes definition, what is type and type diabetes
DeepXML-RE
what is type 2 diabetes, type 2 diabetes, what is type diabetes, do have type diabetes, what the type diabetes, what are type diabetes, "what's type 2 diabetes". what is type 2 diabetes mellitus, diabetes type 2 defini- tion;2 definition diabetestype:deffiitoo diabetes type 2;definition type 2 di- abetes;diabetes definition type 2:type diabetes definition, what is type and type 2 diabetes, what are the causes of diabetes type 2, types of diabetes 2, what is diabetes 2, what causes type 2 diabetes
13

---

Under review as a conference paper at ICLR 2020
AmazonTitles-66
AmazonTille-6700
DeepXML-fr
fecpXML-fr
24
36
35
22
34
21
Varila negative Sampling
negative Sampling
32
19
Mikelev et al.
300
500
1000
2000
Shortlist Size [s]
Shortlist Size
(a) Variation of @recision@1 @1 for DeepXML-fr with increase in shortlist size. Black line at the top of the graph indicates Precision for DeepXML-ffr witthou without negative sampling
(b) Variation of Propensity scored Precision @ 1 (PS- Precision @ 1) for DeepXML-fr with inerease in short- list size. Black line the top of the graph indicates PS- Precision for DeepXMI.-fr without negative sam- pling
Figure 5: Performance of negative sampling approaches in comparision to 1-vs,-all classifier
A.3 COMPARISON WITH BOW APPROACHES
DeepXML, DeepXML-RE yields 4% better accuracy on propensity scored metries and can be upto 2% more accurate on vanilla metrics. Note that PfastreXML. outperform DeepXML. and DeepXML-RE on AmazonTitles-3M, propensity scored metrics, however suffers substantial loss of 10% vanilla precision and nDCG which is unacceptable for real world applications.
A.4 EVALUATION METRICS
Performance has been evaluated using propensity scored precision @k and nDCG@k, which unbiased and more suitable metric the extreme multi-labels setting (Jain et al., 2016 Babbar & Schölkopf, 2019 Prabhu et al. 20188 b). The propensity model and values available The Extreme Classification Repository (Bhatia et al. 2016) were used. Performance has also been evaluated using vanilla precision @ and nDCG@K (with l 1, and 5) for extreme classification.
For predicted score vector ý E R. and ground truth vector y E {0, 1)4:
Pêk
Σ
yt
(Erankz(()
PSP@k
Pt
lEranka (8)
DCG@k 1
Σ
3/1 log(1 + 1)
k
(Eranku())
(2)
PSDCG@k
Σ
y1
Pi log(l +
tEranki (8)
DCG@k
nDCG@k
min
Σ
log (1+1)
PSnDCG@k= PSDCG@k
Σ log 1+1
Here, pi is propensity of the label proposed in (Jain et al. 2016).
14

---

Under review as a conference paper at ICLR 2020
A.5 LITERATURE SURVEY
Representations: Deep architectures such as CNN (Lu et al. 2017). MLP (Zhang et al. 2018). and LSTM with Attention You al. 2018) have been applied to learn semantically and syntactically rich features. Barring Attention YYou et al. 2018), these methods suffer from low accuracy. which more prominent tail labels indicating inep document representation for tail labels. However, performance of AttentionXML also degrades for short text documents as discussed in section 4.3
Parabel: Parabel learns hierarchy over labels to select hardest negatives for each labels and hence bring down the training cost to O(N L). However, Parabel is designed specifically for sparse BoW features and its performance degrades on low dimensional features.
Slice: Negative sampling is popular approach to reduce training complexity in extreme classification setting. Several strategies have been proposed in literature select negatives labels for each instance Mikolov et al. (2013); Reddi et al. (2018) or negative examples for each label (Yen et al. 2017:Dain al. 2019 Prabhu al. 2018b). Slice approach has been shown to scale 100 million labels and more accurate than alternate approaches (Yen et al. [2017 Prabhu et al. (2018)) for low dimensional dense features. Slice uses ANNS select O T, log L) hardest negative examples
and train with selected examples only, thereby reducing the training cost to O log L). Slice also brings down the prediction cost to (d log L) by evaluating only O(log L) most probable labels selected from ANNS.
A.6 ABLATION STUDY
Experiments were carried out with several variations of DeepXML where labels were not splitted in head and tail labels. Here are the different configurations:
DeepXMI.-f: This variation refers to word embedding layer, ReLU non-linearity, Dropout and fully connected output layer.
DeepXMI.fr:: This variation refers to a word embedding layer, ReLU non-linearity, Dropout, residual block and fully connected output layer.
DeepXML-NS: This variation refers to word embedding layer, ReLU non-linearity, Dropout, residual block and a classifier trained via negative sampling (Mikolov et al. 2013)).
exploit sub- words features proposed in (Joulin et al. 2017). This variations refers to DeepXML with sub-word information. Here, character tri-grams were added to the vocabulary in addition to unigrams.
DeepXML-SW: DeepXML
DeepXML-ANNS: This variation refers to a word embedding layer, ReLU non-linearity, Dropout, residual block and classifier trained via Slice. This version trains only with hardest negatives labels selected via ANNS (Jain et al.] 2019). However, the hardest negatives keeps changing as the document representations
being updated. Hence, it requires ANNS graph to be trained multiple time. Here, ANNS graph was updated after an interval of 5 epochs.
Deep This variation refers word embedding layer, ReLU non-linearity, Dropout, residual block and shallow tree based classifier proposed in AttentionXML.
15

---

Under review as a conference paper at ICLR 2020
Table 8: DeepXML and DeepXML-RE can perform on par with Parabel and DiSMEC on full-text documents. Please note that marked algorithms uses slightly different version of the dataset. Values indicated by '-' were not available. Please note that the focus of the paper short-text datasets.
Dataset Method
P@1
P@3
P@5
N@s
PSP@1 1
PSP@3
PSP@5
PSN@5
DeepXML
68.56
47.64
36.62
56.91
28.67
33.27 34.46
36.51
36.04
DeepXML-RE
69.58
47.56
36.02
56.62
30.16
37.21
37.13
XML--CNN
59.85
39.28
29.81
46.12
Wikipedia-50m 500K
XT
64.48
45.84
35.46
AttentionXML-1
75.07
56.49
44.41
65.77
30,05
37.31
41.74
AttentionXMI *
76.95
58.42
46.14
68.23
30.85
39.23
44.34
FastetFas
27.98
16.61
12.11
22.69
15.04
14.61
15.17
17.59
DiSMEC
70.2
50.6
39.7
40.5
31.2
33.4
37
37.1
Parabel
68.7
49.57
38.64
58.62
26.88
31.96
35.26
34.61
AnnexML
64.64
43.2
32.77
52.42
26.88
30.24
32.79
33.33
PfastreXML
59.5
40.2
30.7
28.7
29.2
27.6
27.7
28.3
ProXMI.
68.8
48.9
37.9
33.1
35
39.4
39
DeepXML
44.32
39.87
36.55
40.8
30.55
33.12
35.51
32.95
DeepXML-RE
44.78
40.28
36.94
41.21
30.17
33.13
35.79
33.03
XMI--CNN
35.39
31.93
29.32
32.64
28.67
33.27
36.51
Amazon-670k
XT
42.5
37.87
34.41
38.43
24.82
28.2
31.24
28.29
AtteationXML-1
45.66
40.67
36.94
41.35
29.3
32.36
35.12
XtLentionXML
47.58
42.61
38.92
43.5
30.29
33,85
37.13
SLICE+FasIText
33.15
29.76
26.93
30.27
20.2
22.69
24.7
22.72
DiSMEC
44.7
39.7
36.1
40.5
27.8
30.6
34.2
30.7
Parabel
44.89
39.8
36
40.36
25.43
29.43
32.85
30.71
AnnexML
42.39
36.89
32.98
37.04
21.56
24.78
27.66
24.76
PfastreXML
39.46
35.81
33.05
36.69
29.3
30.8
32.43
31.49
ProXML
43.5
38.7
35.3
30.8
32.8
32.6
"citrus"
f(x)
rn (x)
x
(x)
B
"fruits"
Hard negatives
backpropagates
does not backpropagate
Approx NN Search
Figure 6: An intuitive example with DeepXML architecture. (To be viewed under magnification.)
16


Reviews:
[{"review_id": "SylqCgSG5H", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers extremely multi-label learning (XML) where the label size is very large . It aims to improve the accuracy as well as the scalability of XML algorithms, especially for short text inputs. The accuracy for XML with short text inputs can be significantly improved using deep learning representation than using TFIDF features. This paper proposes several tricks to handle the issue for efficiently learning both neural network parameters and classification weights of extremely large number of labels. The proposed method borrowed ideas from several previous literature, and is mainly based on SLICE, where a pre-trained fixed deep learning representation for the inputs are used with ANNS graph for labels to improve the scalability. The main difference is that instead of using a fixed input embedding, the proposed method learns the word embedding parameters via a set of head labels. The remaining labels are then trained using SLICE with fixed word embeddings from the learned word embedding model. \n\nOverall the paper tackles the problem well. And the empirical results show improved results. However, I don't think this paper is ready for publication due to the following concerns. \n\n1. My main concern is that the proposed method seems to be a combination of a number of tricks. This makes the overall algorithm/model very complicated and introduces a lot of hyper-parameters, for example, head label portion, L-h', c, beta, s neural network hyper-parameters and so on. Hence, it will be hard to be used in real applications.  \n\n2. Another concern is about the experiments. \n    a. The most significant improvement of the proposed method over existing method happens in the private dataset, Q2B-3M, which can't be reproduced.  \n     b. On the public datasets, DeepXML seems to show good results on small datasets, WikiSeeAlsoTItles-350K and WkipediaTitle-500K, while on large datasets, DeepXML performance is close to the existing methods. \n     c. The largest label size in the experiments is 3M. SLICE can be scaled up to 100M labels. \n\n3. The writing and the organization of this paper needs to be improved. \n    a. Some notations are not clearly defined. For example, L_h in Line 6 and X' in Line 9 on Page 5. \n    b. Several method names are not defined. For example, DeepXML-fr, AttentionXML-l, Sliced-CDSSM, DeepXML-SW, DeepXML-f. I have to guess what they are. \n    c. The last two paragraphs on Page 4 seems to be related work, while there is a section called \"Related work\".\n\nOther minor comments:\n1. It seems it is not stated how Beta is set. \n2. I am wondering if it's true that the shorter the input text is, the better improvement over non-deep-learning methods DeepXML can achieve.\n3. In the first paragraph of Sec 3.1, it is mentioned \"clustering just the top 3 labels into 300 clustering\". Why choose 3 and 300? Are these numbers used for all datasets?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "HyxA3eVAYr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a deep learning method for extreme classification and apply it to the application of matching user queries to bid phrases. The main idea is to learn the deep models separately for head and tail labels. Since there is abundant training data for the head labels and transfer the learnt word embeddings for the network for tail-labels, while keeping the head network fixed.\n\nOn the positive side, given that there are relatively few successful approaches for deep learning in extreme classification, the main contribution of the paper is towards making an attempt towards this goal.\n\nHowever, since the paper is mostly empirical in nature and based on algorithmic implementation, the experimental evaluation does not seem quite convincing for the following reasons :\n\n1. Firstly, all the datasets used in the work are private and not publically available. This is quite in contrast to all the various works in this community which use publicly available data and codes.\n\n2. It is not clear why the authors did not to evaluate their approach on the \"standard\" datasets from the Extreme Classification Repository http://manikvarma.org/downloads/XC/XMLRepository.html. Though it is clear that the focus of the paper is on short text classification, but it is important to evaluate what happens when that is not case. Does the method also works well in longer training/test instance, as there is no immediate reason for it to not work well in that case. Or is it that other methods outperform in that scenario.\n\n3. The performance of the proposed method DeepXML is not significantly better than Parabel. For instance,  on two of the four datasets in Table 1, it gives same predictive performance with order of magnitude less training time and much lower prediction time. This begs the question of utility of proposed approach.\n\n4. Related to above is impact of data pre-processing for different methods. DeepXML seems to use tf-idf weighted word embeddings while other methods use simply BoW representation. It is possible that using simialr data representation or combination with bigrams/trigrams might also improve performance of Parabel and DiSMEC, since it is known from short text classification that using this info can improve performance (https://www.csie.ntu.edu.tw/~cjlin/papers/libshorttext.pdf).\n\n5. Lastly, it is unclear why AttentionXML and DiSMEC are shown to be non-scalable for Amazon3M when they have shown to be evaluated on the bigger version of the same datasets in other works. Also, it might be noted that AttentionXML in the latest version can be combined with shallow trees for efficient scaling.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "BJe2vF789S", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a new algorithm for extreme multi-label classification. The focus of this paper is on being able to handle short documents with all experiments focussed on matching user queries to advertiser bid phrases. The key novelty in this paper is to split the labels into two buckets: head labels and tail labels. The model learns word embeddings on the head labels + a classifier on top of those embeddings. For the tail labels, the embeddings from the head labels are used as the input for another classifier which is trained on only the tail.\n\nMy thoughts on the paper:\n- I really like the paper writeup; its succinctness (in most sections, some comments below).\n- Small nit: why choose head labels as 0.1L? I would have expected a more natural choice to be based on frequency?\n- Figure 1 (and explanation in section 3.1): I understand the head setup completely (although it seems to be missing the ANNS). For the DeepXML-t part, I am not very clear from the picture nor the explanation how the ANSS feeds into the weights and how that leads to the label \\hat{y}+{clf-t}?\n- Section 3.1, DeepXML-h section: the bit after \"Additionally ...\" until \"DeepXML-t\" section is unclear. I think this needs to be explained better.\n- I might have missed it but is PSP metric defined explicitly somewhere?\n- The experiment section contains lots of baseline comparisons; unfortunately not all on publicly available datasets.\n- The paper uses a large number of aconyms which are defined sometimes after their first use, sometimes never: i.e. PLT, ANNS.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new method for extreme multi-label classification. However, this paper only combine some  well known tricks, the technical contributions are too limited. And there are many problems in the experiments, such as the reproducibility, the scal of data set and the results on well-known extreme data sets and so on. The authors are encouraged to consider the reviewer's comments to revise the paper.
Decision: Reject