Improving Tail Label Prediction for Extreme Multi-label Learning
Authors: Tong Wei
Wei-Wei Tu
Yu-Feng Li
Venue:  (2021)
Keywords: classification
multi-label learning
extreme multi-label classification
tail label

Abstract: Extreme multi-label learning (XML) works to annotate objects with relevant labels from an extremely large label set. Many previous methods treat labels uniformly such that the learned model tends to perform better on head labels, while the performance is severely deteriorated for tail labels. However, it is often desirable to predict more tail labels in many real-world applications. To alleviate this problem, in this work, we show theoretical and experimental evidence for the inferior performance of representative XML methods on tail labels. Our finding is that the norm of label classifier weights typically follows a long-tailed distribution similar to the label frequency, which results in the over-suppression of tail labels. Base on this new finding, we present two new modules: (1)~\algoa~learns to re-rank the predictions by optimizing a population-aware loss, which predicts tail labels with high rank; (2)~\algob~augments tail labels via a decoupled learning scheme, which can yield more balanced classification boundary. We conduct experiments on commonly used XML benchmarks with hundreds of thousands of labels, showing that the proposed methods improve the performance of many state-of-the-art XML models by a considerable margin (6\% performance gain with respect to PSP@1 on average).

Under review as a conference paper at ICLR 2021
IMPROVING TAIL LABEL PREDICTION FOR EXTREME MULTI-LABEL LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Extreme multi-label learning (XML) works to annotate objects with relevant labels from extremely large label set. Many previous methods treat labels uniformly such that the learned model tends to perform better on head labels, while the performance is severely deteriorated for tail labels. However, it is often desirable to predict more tail labels in many real-world applications. To alleviate this problem, in this work, we show theoretical and experimental evidence for the inferior performance of representative XML methods on tail labels. Our finding is that the norm of label classifier weights typically follows a long-tailed distribution similar to the label frequency, which results in the over-suppression of tail labels. Base on this new finding, we present two new modules: (1) RANKNET learns to re-rank the predictions by optimizing population-aware loss, which predicts tail labels with high rank; (2) TAUG augments tail labels via a decoupled learning scheme, which yield more balanced classification boundary. We conduct experiments on commonly used XML benchmarks with hundreds of thousands of labels, showing that the proposed methods improve the performance of many state-of-the-arr XML models by a considerable margin (6% performance gain with respect to PSP@ @ on average).
INTRODUCTION
Extreme multi-label learning (XML. aims to annotate objects with relevant labels from extremely large candidate label set. Recently, XMI. has demonstrated its broad applications. For example, in webpage categorization Partalas et al. (2015), millions of labels (categories) are collected in Wikipedia and one wishes to annotate new webpages with relevant labels from a huge candidate set; in recommender systems McAuley et al. (2015), one hopes to make informative personalized recommendations from millions of items. Because of the high dimensionality of label space, classic multi-label learning algorithms, such as Zhang & Zhou (2007); Tsoumakas & Vlahavas (2007). become infeasible. To this end, a number of computational efficient XML approaches are pro- posed Weston (201T Agrrwal al. (2013): Bi & Kwok (2013); Yu al. (2014): BBatia et al. (0015 H. Yen et al. (2016); Ych et al. (2017); Yen et al. (2017): Tagami (2017).
In XML, one important statistical characteristic is that labels follow long-tailed distribution as illustrated in Figure (left). Most labels occur only a few times in the dataset. Infrequently occurring labels (referred to as tail label) possess limited training samples and are harder to predict than frequently occurring ones (referred to as head label). Many existing XML approaches treat labels with equal importance, such as Prabhu& & Varmal (2014); Babbar & Schölkopf (2017); Khandagale et al. (2019). while Wei & Li] (2018) demonstrates that most predictions of well-established methods are heads labels. However, many real-world applications, is still desirable to predict more tail labels which are more rewarding and informative, such as recommender systems Jain et al. (2016);
Babbar & Schölkopf (2019); Wei & Li (0018); Wei et al. (2019).
To improve the performance for tail labels. existing solutions typically involve optimizing loss functions that are suitable for tail labels JaainnnJinn et al. (2016): Babbar & Schölkopi (20199, leveraging the sparsity of tail labels in the annotated label matrix Xu et al. (2016), and transferring knowledge from data-rich head labels to data-scarce tail labels K. Dahiya (2019). These methods typically achieve better performance tail labels than standard XMI. methods which treat labels equally, while they

---

Under review as a conference paper at ICLR 2021
140
100
2008
2000 2500
3500
2083 audice
2000
3800
25W
1014
1200
2008
2000
Labulladion
Iadion
Figure 1: Left: Label frequency follows a long-tailed distribution. Middle: Norm of classifier weights of Bonsai models Khandagale al. (2019). Right: Norm of classifier weights of Bonsai models when decoupled tail label augmentation is applied.
usually involve high computational costs. Moreover, previous studies do not explicitly explain the underlying cause the inferior performance of many standard XML methods for tail labels.
In this work. we disclose theoretical and experimental evidence for the inferior performance of previous XML methods on tail labels. Our finding is that the norm of label classifier weights follows long-tailed distribution similar to the label frequency as shown in Figure f (middle), and the prediction score of tail labels thereby is underrated. To alleviate this problem, we propose to rectify the classifier's outputs and training data distribution such that the prediction of tail labels is enhanced. We present two general modules suitable for any well-established XML methods: (1) RANKNET learns to re-rank the predictions by optimizing a population- aware loss function, which predicts tail labels with high rank; (2) TAUG augments tail labels via a decoupled learning scheme, which reduces the skewness training data and yields more balanced classification boundary.
We conduct experiments to verify the effectiveness of the aforementioned instantiations. From our extensive studics across four benchmark datasets, we make the following intriguing contributions:
We show that from both theoretical and experimental perspectives, the norm of label classifier weights follow long-tailed distribution, i.c., the norms head label classifier weights are considerably larger than that of tail label classifiers, which is key cause of the inferior performance many XML methods on tail labels.
We propose two general modules: RANKNET for prediction score re-ranking by optimizing new population-aware loss, and TAUG for decoupled tail label augmentation. Both methods can be paired with any XML model without changing the model.
Experiments verify that our proposed modules achieve significant improvements (6% w.r.t. @ 1 average) for well-established XML methods on benchmark datasets.
We provide an ablation study to highlight the effectiveness of each individual factor.
PREVIOUS EFFORTS
Existing work on XML can be roughly categorized as three directions:
One-vs-all methods. This branch of work trains classifiers for each label separately. Due to the huge size of label set, parallelization Babbar & Schölkopf (2017). label partitioning Khandagale
et al. (2019), and label filter Miculescu-Mizzl & Abbasnejad (2017) techniques are used to facilitate efficient training and testing. alleviate memory overhead, recent works restrict the model capacity by imposing sparse constraints E.-H. Yen et al. (2016) removing spurious parameters Babbar & Schölkopf 2017). One criticism of one-vs-all methods is that fails to capture label correlations.
Embedding- based methods. Along this direction, researchers have proposed to embed the feature space and label space onto a joint low-dimensional space, then model the correlation between features and labels in hidden space Tai & Lin 2012); Chen & Lin (2012): : Yu et al. (2014); 4); Bhatia et al. (2015): Tagami (2017): Evron et al. (2018). ) This method can dramatically reduce the model parameters compared with the one-vs vs-al methods, but involves solving complex optimization problems.
Tree-based methods, In comparison to other types of approaches, tree-based methods greatly reduce inference time, which generally scales logarithmically in the number of labels. There are typically
2

---

Under review as a conference paper at ICLR 2021
two types of trees including instance trees Prabhu & Varma (2014); Siblini et al. (2018) and label trees Daume III et al. (2016); You et al. (2018). depending whether instance or label is partitioned in tree nodes. Tree-baset methods usually suffer from low prediction accuracy affected by the cascading effect, where the prediction error at the top cannot be corrected at a lower level.
These methods readily scale up problems with hundreds of thousands of labels. However, Weil & Li (2018) 2019) claims that head labels make a significantly higher contribution to the performance than tail labels. Therefore, many work are conducted improve the performance for tail labels.
Optimization. Jain
Jain et al. (2016) proposes propensity scored loss functions that promote the prediction of tail label with high ranks. Xu et al. (2016) decomposes the label matrix into low-rank matrix and a sparse matrix. The low-rank matrix is expected to capture label correlations, and the sparse matrix used capture tail labels. Babbar & Schölkopi (2019) views tail label from an adversarial perspective and optimizes hamming loss to yield robust model.
Knowledge transfer. K. Dahiya 20199) trains two deep models on head labels and tail labels. The semantic representations learned from head labels are transferred to the tail label model.
These methods achieve better performance on tail labels than standard XML methods which treat labels equally, while they do not explicitly explain the underlying cause of the inferior performance of many standard XMI. methods for tail labels. In this work, we find that the classification boundary of existing XML methods is skewed to head labels, causing the inferior performance.
3 METHODOLOGY
In XML., we possess fewer data about tail labels, models learned long-tailed datasets tend to exhibit inferior performance on tail labels WWii & Li (2018). However in practice, is more informative and rewarding accurately predict tail labels than head labels [Jae et al.) (2016). In this work, we attempt to alleviate this problem from the perspective of the classification boundary. We make an observation that the norm of label classifier weights follow a long-taile -tilld distribution similar to the label frequency, which means that the prediction of tail labels is perrssuppessed. This finding provides an evidence for us to improve the prediction of tail labels. We present ways of rectifying the classifier's s outputs and data distribution via re-ranking and tail label augmentation, respectively.
Notations. We first describe notations used through the paper. Let = [x,) Y {yy) be a training set of size N, where y; is the label vector for data point x,. Formally, XML is the task of learning a function f that maps an input (or instance) x E RD to its target y E 104, We
denote n2, = > Yij as the frequency of the j-th label. Without loss of generality, we assume that the labels are sorted by cardinality in non-increasing order, i.c., if j < k, then n. 2 fig, where 1 I j, k < L. In our setting, we have n1 >> n.. According to the label frequency, we can split the label set into head labels and tail labels by a threshold т E (0, 1). We denote head label set H (.....,IL]] and tail label set T = [[rL] + + L}. is user-specified parameter.
3.1 THE LONG-TAILED TAILED DISTRIBUTION OF CLASSIFIER WEIGHTS NORM
We present a different perspective regarding XML. model, showing its inferior performance on tail labels is due to the imbalanced classification boundary. In Figure 4 (middle), we empirically observe that the norm of label classifier weights follows a similar long-tailed distribution as the label frequency. The results are produced on EUR-Lex dataset using a representative one-vs-all method Bonsai Khandagale et al. (2019) A similar observation on Wiki10-31K dataset is presented in the supplementary material. Since the norm of tail label classifier weights is considerably smaller than that of head label classifier weights. the predicted score of tail labels are typically underestimated in inference. We further support our finding theoretically and demonstrate the fact that the small norm of tail label classifier weights is the root cause of inferior performance.
We make the following mild assumption on the data: every input x is sampled from feature space completely at random, and there exists a constant threshold > 0 for the input x, such that the top-k prediction for x is made as ((k) {y1 PP x) 1 < I L}, where PP(2) x) denotes the estimated label distribution. We assume W = [w,]f= be the weight matrix of standard XML. method. In particular, for binary relevance and tree-based classifier, W can be obtained by
3

---

Under review as a conference paper at ICLR 2021
optimizing Eq.
where L denotes the loss function, e.g., squared hinge loss, and constant À is trade-off parameter. Note that for some bese methods, such as Bonsai Khandagale et al. (2019) and Parabel [Prabhu et al. (2018), consider W be the label classifier weights in leaf nodes, I..., excluding meta-labels of internal tree nodes.
N min Ww 112 A CV.... x1) 1A SISL
For deep learning methods, we denote W be the weights the last linear layer for classification by optimizing Eq. ②). where o is the softmax function, fo is the feature extractor parameterized by 6, and L denotes also be adapted to typical embedding- based methods, such as Yu et al. (2014), where So is linear and a is the identity function.
selected loss function, e.g., binary cross entropy. Note that this interpretation can
N min i=1
Σ Cyi. (WT fo (x:)))
With the above setup, we summarize our findings in Theorem 1
Theorem 1. Lei D ((x,,))) be sample set and W, which can be decomposed as { 3
be the label classifier weights learned on DD by optimizing Eq. 4 and Eq. (). For an uniformly
sampled point x which is i.i.d. with points in D, we have [|w,] x E [y) =B(k) 11 1 L. where
3(k) denotes the k top-ranked indices of predicted labels F(y x).
This theorem shows that the need for ce-balancing the classifier weights to improve the performance on tail labels. Motivated by our finding, in the following we propose two new modules and discuss their effectiveness on tail labels. Proof of this theorem can be found in the supplementary material.
3.2 RANKNET: PREDICTION SCORE RE-RANKING NETWORKS
We introduce novel re-ranking module motivated by our finding that the prediction score of tail labels are usually over-suppressed. Conventionally, the ranked list of predicted labels is determined by sorting the predicted score by XML model Since the prediction score of tail labels underrated as analyzed above, to alleviate this problem, we propose a re-ranking module to prioritize tail labels with higher score than head labels. More specifically, for given sample x, the probability of I-th label yt being relevant any existing XML model f. A RankNet block is a computational unit which maps the raw predictions its enhanced population-awee aware predictions. Formally, given the raw prediction ý fxx and y E R4x1, RankNet building block is defined as:
usually
is specified by ý1 - f(x); P( x), which can be estimated by
F(x) = y
where W R L. is learnable parameters of this RankNet block which is able to capture label correlations. To train RankNet, we propose a new population-awe -awaat loss function to minimize, which enforces higher predictions for tail labels than head labels and maintains prediction accuracy:
[(F(x).)) = Σ NET JET,
The ny (F(x):F((x))) F(x)))) + + [F(xx F(x); + cl+ n. + nz.
RELy R
Here, [z]+ := max(0, 2) and Ly denotes the set of indices that are non-zero in y, where Ly < 2 is constant which controls the margins. In particular, the first term enforces F(x); < F(x); if n; > nj and the denominator n; nn is used for normalization. The second term aims to retain the predictive accuracy by enforcing predicted score of relevant labels to be larger than that of irrelevant labels. Finally, X is used to balance these two terms. Note that since Ly & L, the first term can be calculated effectively. To further speedup the training. a subset of irrelevant labels sampled randomly. Therefore, RankNet introduces limited computational overhead, hence more expressive networks can be used. In other words, our design for function F can be formally defined as:
F(x) " + +
where n E RR VXL and V E L are learnable weights using gradient descent, V < the dimension of bottleneck layer reduce the number of parameters, and is the activation function.
4

---

Under review as a conference paper at ICLR 2021
Actually, stack any number of RankNet blocks form deep RankNet module and the output of each block is an enhancement over the output of the previous block. By doing so, the enhanced predictions F(x) is able to aware the population of labels. We also provide simple instantiations of F(x) as F(x), = (x)( for the I-th label, where rı represents the inverse propensity score: 1 C' (nu + --= A, B, C. are set recommended in paper Jain et al. (2016). Finally, the top-ranked predictions in F(x), rather than [xx), are selected as final predictions. As one can expect, it increases the propensities of tail labels in inference, thereby more tail labels shortlisted in final predictions. Unlike existing re-ranking methods Jain et al. (2016), RankNet is general architecture and it can be concatenated after any standard XML methods.
3.3
TAUG: DECOUPLED LEARNING SCHEME AND TAIL LABEL AUGMENTATION
From another point of view, since the root cause of the imbalance of classifier norms, which is caused by the long-tailed data distribution, we propose to resolve this problem by reducing the skewness of training data.
Decoupling the learning of head label and tail label. We propose to decouple the learning of head labels and tail labels, instead of learning models jointly. This has two main benefits: (1) decoupled learning scheme helps prevent from modeling highly imbalanced data, i.e., the data distribution within head labels and tail labels are relatively less imbalanced; (2) head label model and tail label model can be trained in parallel manner which reduces the training time. Recall that H. and T into two parts: D = {(x., May 1, Vj E H} and D' = {(x,, y:) Vij = 1, Vj E T). Models are then respectively learned on Dh and D' inference, the prediction score of models are integrated.
denote head label set and tail label set, respectively. We split the training set = y;,
Tail Label Augmentation. To better explore the data distribution of tail labels, we consider two data augmentation techniques, Input dropout and Input swap.
1. Inpul dropout: For selected keep probability E [0, 1] and an input sample x, it produces an augmented input x Bernoulli(p. D), where @ denotes element-wisg multiplication.
2. Imput swap: For each instance x, two activated features are randomly identified and their values are swapped. This procedure can repeat multiple times. Formally, for a pair of feature coordinates i, where 1 I i,j - D, we swap their values and æz--
Note that both data augmentation methods are label-invariant. other words, for given sample yx, and its augmented instance x', we take y' y as the corresponding label vector of x'. Importantly,
observed that there significant variation in the input features of tail labels from training set to test set Babbar & Schölkopf (2019). by generating more similar samples, it discourages the model from fitting spurious patterns in input features when training data is scarce and it also promotes the model to be robust to the corruption of the input features. The proposed decoupled learning scheme and tail label augmentation methods are observed to yield more balanced classification boundary demonstrated in Figure (right).
EXPERIMENTS
We perform experiments on four XML datasets which are publicly available from the XML repository. Detailed statistics are summarized Table where L denotes average labels per sample and N denotes average sample per label
Datasets.
Table 1: Statistics of datasets.
Dataset
Train
# Features
Labels
Test
L
N
EUR-Lex
15,539
5,000
3,993
3,809
5.31
25.73
AmazonCat-133
1.186.239
203,882
13,330
306,782
5.04
448.57
Wiki10-31K
14.146
101,938
30,938
6,616
18.64
8.52
Amazon-670K
490,499
135,909
670,091
153025
3.9
5.4
Datasets are available the Extreme Classification Repository.
5

---

Under review as a conference paper at ICLR 2021
Implementation. Without further specification, set the label splitting threshold 0.1 for EUR-Lex, and r = 0.01 for AmazonCat-
Wiki10-31K, and Amazon-67000 For tail label augmentation, we fix aug 4, which means four auxiliary data points generated for each sample. Recommended settings are used for all XMI. algorithms as specified in their paper.
Evaluation Metrics. We evaluate XML models the test set and report results with respect to the commonly used evaluation metrics, i.e., P@ k. nDCG@ k. PSP@k, and PSnDCG@K k (PSN k),, where & (1,3,5). Due limited space, we elaborate the definitions in the supplementary material.
4.1 How DOES THE PREDICTION SCORE RE-RANKING AFFECT THE RESULTS
We evaluate the effectiveness of the proposed score re-ranking method RANKNET. We run three popular XML algorithms, including FastXML Prabhu & Varma (2014). Bonsai Khandagale al.) (2019). and Parabel [Prabhu et al. (2018) for comparisons.
From Table 2 is effortless to observe that in all cases, three XML methods employing prediction score re-ranking achieve significantly higher PSP@ k and PSnDCG@ k compared with their baselines. In particular, FastXMI. respectively achieves as much as 5.81 %, 8.4%, 0.94%, and 2.39% overall improvement on four datasets across PSP@ k and PSnDCG @ k. In comparison, Bonsai outperforms its baseline by larger margin, i.e., 5.31%, 7.49%, 5.84%, and 2.64% on four datasets, respectively. Similarly, Parabel achieves performance gains comparable Bonsai, i..., 5.31 31, 7.51%. 5.26%, and 2.66%. This demonstrates that RANKNET provides an effective way to rectify the predictions for existing XML models, by which the predicted score of tail labels indeed over-suppressed.
Table 2:
Comparison between well-established XML methods with (w/) and without (w/o) RANKNET w.rt. PSP@ k and PSnDCG@K & k). The biggest improvements are bold.
w/o RANKNET
Improvement w/ RANKNET
Dataset
Method
PSP@1
PSP@3
PSP@5
PSP@1
PSP@3
PSP@5
Avg.
FastXML
26.29
33.57
37.80
+7.78
+5.60
+3.94
+5.25
EUR-Lex
Bonsai
36.91
44.89
49.46
+8.15
+4.59
+2.36
+5.03
Parabel
36.42
44.08
48.46
+7.79
+4.68
+2.17
+4.88
FastXML 48.06
59.25
66.70
+12.31
+7.62
+3.10
+7.68
AmazonCat-13K
Bonsai
51.07
62.37
68.84
+11.76
+6.15
+2.32
+6.74
Parabel
49.52
61.13
67.87
+11.62
+6.34
+2.37
+6.78
FastXML
9.76
10.31
10.64
+0.95
+0.90
+0.98
+0.94
Wikil0-31K
Bonsai
11.79
13.44
14.71
+8.17
+5.10
+3,29
+5.52
Parabel
11.68
12.72
13.69
+6.52
+4.71
+4.01
+5.08
FastXML 18.69
21.87
24.44
+3.44
+2.49
+1.63
+2.52
Amazon-6700
Bonsai
27.10
30.69
33,91
+3.84
+2.45
+1.12
+2.47
Parabel
26.35
29.94
33.16
+3.74
+2.48
+1.27
+2.50
Dataset
Method
PSN@1
P
PSN@5
PSN@1
PSN@3
PSN@5
Avg.
FastXML
26.29
31.59
34.40
+7.78
+6.23
+5.14
+6.38
EUR-Lex
Bonsai
36.91
42.43
45.23
+8.15
+4.91
+3.74
+5.60
Parabel
36.42
41.99
44.90
+7.79
+5.53
+3.90
+5.74
FastXML
48.06
56.13
61.00
+12.31
+8,99
+6.09
+9.13
1mazonCat-13K
Bonsai
51.07
59.25
63.53
+11.76
+7.73
+5.23
+8.24
Parabel
49.52
57.92
62.38
+11.62
+7.84
+5.26
+8.24
FastXML 9.76
10.17
10.41
+0.95
0.91
+0.96
+0.94
Wiki10-31K
Bonsai
11.79
13.03
13.92
+8.17
+5.85
+4.54
+6.17
Parabel
11.68
12.47
13.13
+6.52
+5.15
+4.62
+5.43
FastXML 18.69
22.05
23.58
+3.44
+1.81
+1.52
+2.26
Amazon-670K
Bonsai
27.10
29.74
31.94
+3.84
+2.83
+1.92
+2,86
Parabel
26.35
29.01
31.20
+3.74
+2.81
+1.99
+2.85

---

Under review as a conference paper at ICLR 2021
4.2 How DOES THE DECOUPLED TAIL LABEL AUGMENTATION AFFECT THE RESULTS
In the following, we verify the effectiveness of the decoupled tail label augmentation. We choose Bonsai Khandagale et al. 2019) as base model for its appealing performance shown in Table
Bag-of-Wordd (BOW) vs. Dense Emmeeding. Since many benchmark datasets for XMI are text data, we find that the dense embedding used in Chang et al. (2020) achieves significant gains over BOW. We compare the results on EUR-Lea -Ux, and find that dense embedding respectively achieves 2.87% and 3.13% higher performance w.r.t. @ & and PSnDCG@ & on average. We conduct experiments using dense embedding in the rest of this paper except for Amazon-670K, which is not available.
Classifier Weights Normalization. As straightforward way of balancing the norm of classifier weights Kang et al. (2020), we examine the effectiveness of weights normalization. It does not show significant effect on the performance. PSnDCG @ k, but drops the performance with 0.57% w.r.t. PSP@k, k, on EUR-Lex. This suggests that weights normalization, which equalizes the propensity labels, is undesirable for XML.
particular, it improves the performance by 0.63% w.r.f.
Tail Label Augmentation. To justify our claim that it is beneficial to decouple the learning of head labels and tail labels, and augment the tail label, which generate more balanced classification boundaries. The results reported in Table 3 Since the focus of this paper is the performance improvement for tail label, we report and compare the results in terms of PSP@ l and PSnDCG@ As from the results, TAUG achieves averagely 3%, 1.06%, 1.59%. 7.42% improvement w.r.t. PSP@ k and 3.5%, 1.08%, 1.41 %, 7.54% w.r.t. PSnDCG@1 k. on four datasets. This demonstrates that the investigated two data augmentation techniques via decoupled learning scheme can help the learning of tail labels, by yielding more balanced classification boundary which predicts tail labels with relatively larger score compared with the baseline.
Table 3: Comparison between methods with (w/) and without (w/o) TAUG w.r.t PSP@ and PSnDCG@K k: (PSN@k). The biggest improvements across four datasets are bold.
w/o TAUG
Improvement w/ TAUG
Dataset
PSP@1
PSP@3
PSP@5
PSP@1
PSP@3
PSP@5
Avg.
EUR-Lex
39.66
47.92
52.28
+4.64
+2.69
+1.67
+3,00
AmazonCat-13K
49.41
60.39
66.49
+2.22
+0.73
-0.24
+1.06
Wiki10-31K
12.41
14.13
15.52
+0.75
+1.91
+2.12
+1.59
Amazon-670s
27.10
30.69
33.91
+10.21
+7.18
+4.87
+7.42
Dataset
PSN
PSN@3
PSN@5
PSN@1
PSN@3
PSN @5
Avg.
BUR-Lex
39.66
45.81
48.48
+4.64
+3.14
+2.72
+3.50
AmazonCat-13K
49.41
57.36
61.41
+2.22
+0.75
+0.27
+1.08
Wiki10-31K
12.41
13.69
14.68
+0.75
+1.65
+1.83
+1,41
Amazon-670n
27.10
29.74
31.94
+10.21
+7.99
+4.43
+7.54
4.3 COMPARISON WITH THE STATE OF THE ARTS
In Table 4 we compare the performance of the proposed modules with recent XML methods, including PfastreXML, et al. (2016). ProXML Babbaa & Schölkopi (2019), AttentionXML You ct al. (2018), and GLas Guo et al. (2019), that report state-of-the-an results on tail labels. Since PSnDCG@k is unavailable for AttentionXLL and GLaS, report and compare the results w.r.t. P in this part. We apply the proposed prediction score re-ranking module (RANKNET) individually and jointly with the decoupled tail label augmentation module (TAUG) for comparison. Though both AttentionXML. and GLaS are carefully designed deep learning methods, it is surprising see that our Bonsai based variants achieve the best results out of 12 cases, and the second-best results in other cases. Apart from deep learning methods, PfastreXML and ProXML are two leading approaches which achieve good performance on tail labels, while they are outperformed by our methods in most cases. In comparison with the baselines in Table BANKNET+TAUG demonstrates more than 6% performance gains w.r.t. PSP@1 on average
"Our anonymous code is availahle in the supplementary material.
7

---

Under review as a conference paper at ICLR 2021
Table 4: Comparison with state-of-the-arr methods w.r.t PSP@ k. Bold numbers are the best and underlined numbers are the second-best. RANKNET and RANKNET+TAUG are our proposed methods.
Dataset
Metric
PfastreXMI.
ProXMI.
GLa$
AttentionXMi.
RANKNET
RANKNET+TAUGG
PSP@1
43.53
45.20
49.77
44.97
48.44
51.86
EUR-Lex
PSP@3 3
45.38
48.50
51.05
51.91
52.94
54.29
PSP@S
47.02
$1.00
53.82
54.86
55.69
55.45
PSP@1
63.51
61.92
47.53
53.76
62.83
63.45
AmazonCat-133
PSP@3 3
68.71
66.93
62.74
68.72
68.52
69.96
PSP@5
71.21
68.36
71.66
76.38
71.17
70.88
PSP@
18.75
17.17
15.57
20.16
23.06
Wiki10-31K
PSP@
18.47
16.07
16.80
19.65
21.60
PSP@5
18.50
16.38
17.82
20.48
21.66
PSP@1
29.28
30.31
38.94
30.29
30.94
40.41
Amazon-670K
PSP@
30.79
32,31
39.72
33.85
33.
39.63
PSP@5
32.40
34,43
41.24
37.13
35.04
39.54
4.4 How DOES THE STRENGTII OF DATA AUGMENTATION MATTER
We are interested in how would the strength of data augmentation affects the classifier weights and the model performance. In Figure 2 (left), we illustrate the norm of classifier weights by choosing n_aug [0, 4, 8). where n_aug indicates the number of augmented samples to generate for each data point. Note that when aug O, models are learned on the initial training data with augmentation. It can be noted that the norms of the tail label classifiers become larger as n aug increases. Figure 2 (right), the performance tends to improve as n_aug increases w.r.t. PSP@ k. As one can expect, P@k le drops with a narrow margin. These results suggest that data augmentation can help re-balance the norm of classifier weights, which is beneficial to tail labels. In addition, we conduct ablation studies to compare two data augmentation techniques, i.c., input dropout and input swap, in the supplementary material. We also demonstrate the effect of different label splitting threshold
R_aug
.ugg
57.5
Scores
Claodfer
98.0
80
47.5
45.0
1086
1.00
2000
Label indices
Augmentation amounts
Figure 2: Left: Norms of classifier weights with varying n_ aug. Right: The performance w.r.t. P@5 and PSP@ ls as a function of aug. Results in both figures are produced using Bonsai on EUR-Lex
CONCLUSION
In this paper, we show that from both theoretical and empirical perspectives, norm of label classifier weights follows long-tailed distribution, if labels are treated uniformly, which is a key cause of the inferior performance for tail labels. To alleviate this problem, we explore the re-ranking module that optimizes new population-awar loss, and tail label augmentation module that decouples head labels and tail labels. Through extensive studies, our proposed two modules achieve significant performance gains. Moreover, both modules can be readily applied to any well-established XML methods without changing their models. We believe that our findings not only contribute to a deeper understanding of the tail label problem, but offer inspiration for future work.
8

---

Under review as a conference paper at ICLR 2021
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 Proceedings of the 22nd International Conference on World Wide Web, pp. 13 13-24, Rio de Janeiro, Brazil, 2013.
R. Babbar and B. Schölkopf. Dismec: Distributed sparse machines for extreme multi-label classifica- tion. In Proceedings of the 10th ACM International Conference on Web Search and Data Mining, pp. 721-729, Cambridge, UK, 2017.
R. Babbar and B. Schölkopf. Data scarcity, robustness and extreme multi-label classification, Machine Learning, 108: 1889139--3311 2019.
K. Bhatia, H. Jain, Kar, M. Varma, and P. Jain. Sparse local embeddings for extreme multi-label classification. In Advances in Neural Information Processing Systems, pp. 730-738, Montreal, Canada, 2015.
W. Bi and J. T. Kwok. Efficient multi-lahel classification with many labels. In Proceedings of the 30th International Conference on Machine Learning, pp. 405-413, Atlanta, GA, 2013.
W.-C. Chang. H.-F. Yu, K. Zhong, Y. Yang, and I. Dhillon. X-bert: extreme multi-label text classification with bert. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2020.
Y.-N. Chen and H.-T. Lin. Feature-aware label space dimension reduction for multi-lahel classification. In Advances in Neural Information Processing Systems, pp. 1529-1537, Lake Tahoe, NV, 2012.
H. Daume III, N. Karampatziakis, J. Langford, and P. Mineiro. Logarithmic time one-against-some. arXiv preprint arXiv: 1606. 1606.0488888 2016.
I. E.-H. Yen, X. Huang, P. Ravikumar, K. Zhong, and I. Dhillon. PD-Sparse: : A Primal and Dual Sparse Approach Extreme Multiclass and Multilabel Classification. In Proceedings The 33rd International Conference Machine Learning, pp. 3069-3077, 3077, New York, NY, 2016.
I. Evron, E. Moroshko, and K. Crammer. Efficient loss-based decoding on graphs for extreme classification. In Advances in Neural Information Processing Systems, Montréal, Canada, pp. 7233-7244, 2018
C. Guo, A. Mousavi, X. Wa, D. Holtmann-Rice, S. Kale, S. Reddi, and S. Kumar. Breaking the glass ceiling for embedding- baased classifiers for large output spaces. In Advances in Neural Information Processing Systems, 2019.
H. Jain, Y. Prabhu, and M. Varma. Extreme multi-label loss functions for recommendation, tagging, ranking & other missing label applications. Proceedings of the 22nd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 935 944, San Francisco, CA, 2016.
D. Saini K. Dave H. Jain S. Agarwal M. Varma K. Dahiya, A. Mittal. Deepxml: Scalable & accurate deep extreme classification for matching user queries to advertiser bid phrases. 2019.
B. Kang, S. Xie, M. Rohrbach, Z. Yan, A. Gordo, Feng, and Kalantidis. Decoupling represen- tation and classifier for long-tailed recognition. Proceedings of the International Conference on Learning Representations, 2020.
S. Khandagale, H. Xiao, and R. Babbar. Bonsai-diverse and shallow trees for extreme multi-label classification. arXiv preprint arXiv:1904.088: 088449, 2019.
J. McAuley, R. Pandey, and J. Leskovec. Inferring networks of substitutable and complementary products. In Proceedings of the 21 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 785-794, Sydney, Australia, 2015.
A. Niculescu-Mizil and M. E. Abbasnejad. Label filters for large scale multi-label classification. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pp. 1448 1457, Fort Lauderdale, Fl., 2017.

---

Under review as a conference paper at ICLR 2021
1. Partalas, A. Kosmopoulos, N. Baskiotis, T. Artieres, G. Paliouras, E. Gaussier, I. Androutsopoulos, M.-R. Amini, and P. Galinari. Lshte: benchmark for large-scale text classification, arXiv preprins arXiv:1503.08581. 2015.
Y. Prabhu and M. Varma. Fastxml: A fast, accurate and stable tree-classifier for extreme multi-label learning. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 263 272, New York, NY, 2014.
Y. Prabhu, A. Kag. S. Harsola, R. Agrawal, and M. Varma. Parabel: Partitioned label trees for extreme classification with application to dynamic search advertising. In Proceedings of the 2018 World Wide Web Conference, WWWW, pp. 1902, 2018.
W. Siblini, P. Kuntz, and F. Meyer. CRAFTML, efficient clustering- extreme multi-label learning. In Proceedings of the 35th International Conference on Machine Learning, pp. 4664 4673, Stockholmsmässan, Stockholm Sweden, 2018.
(luttering-bssed based random forest for
Y. 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, pp. 455-464, 2017.
F. Tai and H.-T. Lin. Multilabel classification with principal label space transformation. Neural Computation, 24(9):2508-255 2012.
G. Tsoumakas and I. Vlahavas. Random k-labelsets: An ensemble method for multilabel classification.
In European Conference Machine Learning, pp. 406 417, Warsaw, Poland, 2007.
T. Wei and Y.-F. Li. Does tail label help for large-scale multi-label learning. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp. 2847-2853, Stockholm, Sweden, 2018.
T. Wei and Y.-F. Li. Learning compact model for large-scale multi-label data. In The 33rd AAAI Conference on Artificial Intelligence, pp. 5385-5392, 2019.
T. Wei, W.-W. Tu, and Y.-F. Li. Learning for tail label data: A label-specific feature approach. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. Macau, China, 2019.
J. Weston, S. Bengio, and N. Usunier. Wsabie: Scaling up to large vocabulary image annotation. In Proceedings of the 20th International Joint Conference Artificial Intelligence, volume 11, pp. Barcelona, Spain, 2011.
C. Xu, D.-C. Tao, and C. Xu. Robust extreme multi-label learning. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1275-122 -2844, San Francisco, CA, 2016.
C.-K. Ych, W.-C Wu, W.-. Ko, and Y.-C. F. Wang. Learning deep latent space for multi-label classification. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pp. 2838 2844, San Francisco, CA, 2017.
I. E. Yen, X.R. Huang, W. Dai, P. Ravikumar, I. Dhillon, and E. Xing. Ppdsparse: A parallel primal-dual sparse method for extreme classification. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 545-553, Halifax, Canada, 2017.
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. Advances in Neural Information Processing Systems, 2018.
H.-F. Yu, P. Jain, P. Kar, and I. S. Dhillon. Large-scale multi-label learning with missing labels. In Proceedings of the 31st International Conference on Machine Learning, pp. 593-601, Beijing, China, 2014.
M.-L. Zhang and Z.-H. Zhou. MI-knn: A lazy learning approach multi-label learning. Pattern Recognition, 40(7):2038-200 2007.
10

---

Under review as a conference paper at ICLR 2021
A THEORETICAL JUSTIFICATION OF THE INFERIOR PERFORMANCE ON TAIL LABELS
Theorem 1. Let (xx,, be sample set and W, which can be decomposed {w; 1ー=1"
be the label classifier weights learned on D by optimizing Eq. 4 and Eq. ( For an uniformly
sampled point x which is i... with points DD we have [|w,]] I 1ys E ((()) J where
3(%) denotes the k top-ranked indices of predicted labels in (y 1x).
| > 0. For any input x, its prediction score computed as P3(y x) = g(w] x) for the j-th label, where g(-) is a monotonically increasing link function, such as the exponential function, the largest top-k prediction score will be selected as the final predictions. For simplicity, we assume g(z) = 2 as an identical function and our analysis can be easily extended to the exponential function. Suppose that / E (0, 1) is the threshold of input x, such that the final prediction is g(k) {y1 w x 2 t, S S L}, where |,8()| k.
Proof. Without loss of generality, assume ||w/|| W2
Here we assume there exists a small constant < L such that w x 2 0, 1A S S k, which is reasonable in extreme classification. Since w)
||w, || ||x|| cos f,. where fg denotes the included angle of classifier wj and sample x. Note that x is usually normalized in advance and ||x| can be considered as constant for different samples. In other words, the prediction can be rewritten as g(k) {リ cos 0 2 |[ |||]|
S S L}. This can be considered as that x is sampled from a ball with radius equals ||x] in the feature space completely at random, which means that 8, is uniformly sampled from [0, rr. Note that always have ||w,ll 1, A1 S j S L because the bias term of each label classifier is set to be 1, which means Twyll < Let 6 arccos [[y]1|||x]]
we have
P(y; (()()) b By taking the expectation over 0j. we have
E [ E 3(0)
1-" P(y, E ((0) dA,
Since typically scales as l|w we conclude that the probability of the j-th label included in top-k predictions of input is proportional to its classifier's 's norm ||w or formally
wyJ
E
y E 300)
v1 sii L.
We empirically illustrate this finding Figure
Wi Ci
C
W
Figure 3: Illustration on different classifiers and their corresponding decision boundaries, where and w,. |wsll > ||w,l|, denote the classification weights for class and respectively. C, and C, are the classification cone belongs to the i-th and j-th class in the feature space, respectively. The classifier with larger weights norm, i.e., w,, has wider decision boundary.
B ADDITIONAL EXPERIMENTAL RESULTS
B.1 VIRTUALIZATION OF THE NORMS OF CLASSIFIER WEIGHTS ON WIKI10-31K
B.2 EVALUATION METRICS
P@k. Top-k precision is a commonly used ranking based performance measure in XML and has been widely adopted for ranking tasks. In Top-k precision, only few top predictions of instance
11

---

Under review as a conference paper at ICLR 2021
method Inbel sugucated
64
Clusliee
3:9000
Indlices
Figure 4: The norm classifier weights Bonsai models before (blue) and after (red) applying data augmentation for tail label. Results are produced Wiki10-31K dataset.
will be considered. For each instance x, the Top-k precision is defined for a predicted score vector y R! and ground truth label vector y E {-1, as
P@k = 1
Σ y1.
k
(Erank+
where (ý) returns the indices of lt largest value in y ranked descending order.
nDCG@k. nDCG@k is another commonly used ranking based performance measure:
DCG@k
nDCG@k
E1=1
log(I+1)
where DCG@k:= ( = 3 and ||yllo returns the O-norm of the true-label vector.
PSP@k. Propensity scored variants of such losses, including precision@k and nDCG@k. developed and proved to give unbiased estimates the true loss function even when ground-truth labels go missing under arbitrary probabilistic label noise models.
Y1
PSP ==
Pt
1Erank (y)
Here, is the propensity score for label which helps in making metrics unbiased.
PSnDCG@ Similar to nDCG@k, its propensity scored variant defined as
PSDCG@k
PSnDCG@k Σt= log((+1)
where
PSDCG@ :
Pt log(1 1)
IEranka
B.3 RESULTS OF RE-RANKING W.R.T. P@K AND NDCG@K
As shown in Table 5 performance with respect to P@k and nDCG@k usually deteriorates. By using RANKNET, more tail labels are predicted with higher confidence than head labels, which would introduce more false-positive predictions. This shows that there a trade-off between propensity scored measures and vanilla measures according to specific demands in applications.
B.4 How DOES THE LABEL SPLITTING THRESHOLD MATTER
In Figure we demonstrate how the splitting threshold affects the results. We experiment with LA [ and L, L [TL], where E {0.1, 0.2, 0.3, 0.4, 0.5, 1} for EUR-Lex and e (0.01, 0.02, 0.03, 0.04, 0.05, 1 for Wikil0-31k Note that, when T = 1, all labels are considered as the head label and no data augmentation is conducted. As L, decreases (i.e., increases), performance in terms PSP@ & typically drops slightly suggesting most labels are should be considered as the tail label and in the need for data augmentation.
12

---

Under review as a conference paper at ICLR 2021
Table Comparison between methods with and without re-ranking terms of P@ and nDCG@k.
Dataset
Method
P@ 1
P@3
P@5
nDCG@3
nDCG@5
FastXML.
70.64
59.20
49.41
62.23
57.16
RANKNETPGstXMM
72.40
60.26
50.20
63.42
58.20
Bonsai
82.75
69.44
58.25
72.84
67.26
EUR-Lex
RANKNET Bonsai
81.46
68.53
56.79
71.80
65.87
Parabel
82.20
68.70
57.53
72.16
66.53
RANKNET RANKNETParahh Parafel
80.67
68.34
56.29
71.56
65.34
FastXML
92.78
77.38
62.25
86.37
84.12
RANKNET MT
90.69
76.75
62.38
85.29
83.60
Bonsai
91.59
76.92
62.21
85.56
83.54
AmazonCat- 13K
RANKNETBoRen
88.47
75.85
61.89
83.84
82.35
Parabel
92.06
76.81
62.05
85.62
83.54
RANKNET Parabel
88.23
75.83
61.50
83.81
82.03
FastXML.
82.93
68.01
57.98
71.41
63.58
RANKNET
84.23
69.46
59.21
72.84
64.85
Bonsai
84.58
73.72
64.44
76.25
69.19
Wiki10-31K
RANKNETBool Bonsai
82.58
71,86
63.67
74.31
68.02
Parabel
84.18
72.46
63.37
75.21
68.21
RANKNET Parabel
83.26
71.33
62.82
74.08
67.50
FastXML
35.89
31.80
28.58
34.03
32.79
RANKNET PasttN MT
34.13
31.18
28.47
33.20
32.39
Bonsai
45.48
40.22
36.37
42.64
40.85
Amazon-6700
RANKNET Bonsai
43.96
39.32
35.77
41.66
40.11
Parabel
44.91
39.76
35,98
42.11
40,33
RANKNET Parabel
43.85
39.19
35.57
41.48
39.85
PSP@:
PSP
PSP@5
PSP
PSP
PSP@5
52
17
50
16
Scores
Scores
15
46
42
13
40
6.1
0.2
0.3
0.5
0.11
0.82
0.03
0.84
0,8
Splitting thershold
Splitting thershold
Figure 5: The performance terms of PSP@k k as function splitting thresholds on EUR-Lex (left) and Wikil0-31K (right). Results are produced using Bonsai method.
B.5 ABLATIONS ON THE INPUT DROPOUT AND INPUT SWAP
We conduct ablation studies to compare the effectiveness of the proposed two tail label data augmen- tation strategies. We compare four methods using Bonsai as the base model:
baseline: this method does any data augmentation techniques.
TAUG-d: this method uses input dropout only with aaa 4.
13

---

Under review as a conference paper at ICLR 2021
TAUG-s: this method uses input swap only with auaug 4.
TAUG-ds: this method uses both input dropout and inpur swap with n_ n_aug =4
We report the results in 6 On EUR-Lex dataset, effortless to see that both input dropout and input swap achieve performance gains, i.e., respectively 2.67% and 2.06% average, against the baseline method. It further improves the performance when both techniques are incorporated into the Bonsai, i.c., TAuG-ds. On Wiki10-31K dataset, shows relatively smaller margin of improvement. Nevertheless, TAUG-ds still improves the performance with 1.65% on average.
Table 6: Comparison between input dropout (-d) and input swap (-s) using dense embedding repre- sentations on EUR-Lex and Wiki10-31K datasets. The best results are in bold.
Dataset
Method
PSP@1
PSP@3
PSP@5
PSnDCG@3
PSnDCG@5
baseline
40.10
47.91
51.85
45.81
48,48
TAUG-d
43.52
50.45
53.94
48.63
50.99
EUR-Lex
TAUG-S
42.81
49.94
53.27
48.09
50.35
TAUG-ds
44.20
50.58
53.97
48.91
51.19
baseline
12.41
14.13
15.52
13.69
14.68
TAUG-d
13.14
15.94
17.60
15.26
16.46
Wiki10-31K
TAUG-S
12.99
15.70
17.26
15.03
16.17
TAUG-ds
13.18
16.05
17.63
15.34
16.50
14


Reviews:
[{"review_id": "VCu-I6_T9nY", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers the setting of extreme multi-label classification, where labels typically follow a power-law distribution with many infrequently-observed labels (so-called tail labels). In this setting it often happens that multi-label classifiers more often predict frequent labels as positive than infrequent labels. In practical applications this is not always wanted, and the authors present a new algorithm that favors tail labels over frequent labels. To this end, a specific ranking-based loss function that consists of two parts is minimized. The first part of the loss ranks positive tail labels higher than positive frequent labels. The second part is more standard, and ranks positive labels higher than negative labels. \n\nImproving predictions for tail labels is an interesting research goal that has not been thoroughly addressed in the literature, but I am not convinced of the theoretical results and the introduced algorithm. \n\nTheorem 1 does not hold because an important condition is missing. The theorem would only hold if w_j^T x > 0 for all x. However, in practice, such a condition cannot be guaranteed. The formulation of the theorem is more difficult than needed, but what the authors want to say is the following: \"P(y_j|x) is a monotonically increasing function of the norm of w_j\". The proof that is found in the appendix cannot be correct because one can easily construct a counterexample when w_j^T x < 0, and the proof is also more complicated than needed. In fact P(y_j|x) is just a transformation of w_j^T x via a monotone function g with [0,1] as codomain. Useful choices for g are the logit or probit link, but not an exponential function (as stated in the proof). With this insight one can easily see that, when w_j^T x < 0, the probability P(y_j|x) will decrease when for example all coefficient in w are multiplied with a factor two. In that case the norm of w_j all increases, and we have a counterexample for the theorem. To my opinion, the proof makes a few very strange constructions, but I cannot immediately see where the mistake is. \n\nI also do not understand why the link function is only introduced in the appendix, because it is a key concept to link w_j^T x and P(y_j|x). To increase readability, I would advise to discuss this early in Section 2. I also do not understand what w_j represents in the case of tree-based models. More discussion is needed. For tree-based models, one doesn't have a weight vector per class, isn't it? \n\nI am also not convinced of the algorithm that is introduced in Section 3.2. The method is very ad-hoc, without any theoretical justification. As a result of pairwise terms, it might also be computationally challenging to optimize the proposed loss for extreme multi-label datasets. Isn't there a much simpler solution? Using the terminology of Section 2.1, one could simply improve the performance for tail labels by adjusting the threshold t for such labels only. Has such a simple solution been considered in literature? In that way one could fit standard probabilistic classifiers during training, following by a reasoning on probabilities in a post-training procedure. Similar to the approach of the authors, one could take label frequencies into account during this post-training procedure, resulting in a threshold t that depends on label frequency.  \n\nIn the experiments it is not clear to me why only four XML datasets are used. Why were the other datasets in the XML repository not analyzed? Please provide a good motivation or analyze all datasets. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "Hup9l_42p3", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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 paper presents a method for improving tail-label performance in extreme multi-label learning setup where the number of target labels can be extremely large. It is based on the finding that the distribution of the norms of the learnt weight vectors also follows a power-law as does the distribution of the samples among labels. The main contribution of the paper is proposing methods for re-ranking which encourages precedence of tail-labels and a data augmentation mechanism. It achieves improvements when applied to sota methods on relevant PSP metrics.\n\nSome of the concerns regarding the paper are :\n- The approach overall seems more like an ad-hoc post-processing step rather than a learning algorithm. It is possible that the impact of RankNet proposed in section 3.2 can be achieved in a more simple way of reranking scores. In the code provided, it was not clear where RankNet as described in section 3.2 was implemented. \n- The theorem 1 seems incorrect. The probability model is not completely specified as it is not clear what exactly is meant by the test point being randomly sampled. Is it uniformly at random (as seems to be from the proof) or from the distribution that is same as the training distribution (as the typical i.i.d assumption in ML). Also, it seems to compute expectation of some event {y_j \\in \\beta^{k}}, which is strange as expectations can be computed only of random variables. Overall, the statement of the theorem seems quite vague and imprecise. There are some notational issues also, the W, and w symbols in the theorem don't match the preceding text.\n- In terms of the experimental results, it is not clear what happens with vanilla p@k and nDCG@k. Even though it is mentioned on page 6 para2 that the these metrics are computed but these are not given anywhere. Also, the Table 4 does not seem to be of much consequence as the re-ranking method can be potentially be applied to all the competing methods.\n- Other minor comments - the references are improperly given. In some places abbreviations are used for conference names, and in others full names are given. In many places, arxiv versions of the papers are mentioned, even though the corresponding papers are published with conferences/journals.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Hr1MdPpcfT", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n=======\nIn prediction problems with millions of labels also known as Extreme Multi-label Learning (XML) problems, e.g., recommender systems, the model predictions are not as good for the tail (rarer) labels. This paper proposes two models for this problem. The first model is re-ranking-based, that is, it reranks the prediction scores of a standard XML model. The second model tries to augment the rarer labels to reduce the skew in data. Results shown on several real-world datasets highlight the superior predictive ability of the proposed reranking model for tail labels compared to a host of competitive baselines.\n\n\nComments:\n==========\nThe paper solves an important problem which has several industrial applications of extreme multi-label learning. The proposed methods are novel, perhaps less so to someone who is an expert in XML. The experimental evaluation is highly impressive. Both the proposed methods outperform a host of highly competitive baselines on a variety of datasets by significant margins. However, I have a couple of concerns regarding the proposed methods:\n\n\n1). The RANKNET method which re-ranks the XML model's predictions needs to be compared against a baseline which also performs re-ranking for an apples-to-apples comparison in Table 2. Sure, the improvements due to reranking (vs no-reranking) are impressive, but how would a simple re-ranking approach which is not population-aware perform? How is the lambda chosen? By CV? Since you can stack RankNet modules to make it deep, how many were used for results in Table 2? How sensitive are the results to the number of modules?\n\n2). The data augmentation for the tail labels seems arbitrary. Why only Input dropout and Input swap? Also, it is unclear how one should split the data between head and tail labels? More importantly, how are the model scores for head and tail labels integrated to make a final prediction?   \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents some interesting insights, but all reviewers have agreed that it does not meet the bar of ICLR. The theoretical results require revision as several issues have been indicated in the reviews. The authors have tried to correct them during the rebuttal, but the reviewers remain unconvinced.  Also the novelty is limited as re-ranking is a well-known concept and decoupling of head and tail labels is an approach often used in practice across many applications.

The authors should also clarify the way the RankNet method is used and implemented to clarify the issue raised by Reviewer 1. Finally, let me notice that adjusting thresholds for labels has been considered in the XMLC literature, in the context of optimization of the macro F-measure (Extreme F-measure Maximization using Sparse Probability Estimates, ICML 2016).


Decision: Reject