Unbiased Estimates for Multilabel Reductions of Extreme Classification with Missing Labels
Authors: Erik Schultheis
Rohit Babbar
Venue: NeurIPS 2022 Submitted (2022)

Abstract: This paper considers the missing-labels problem in the extreme multilabel classification (XMC) setting, i.e. a setting
with a very large label space. The goal in XMC often is to maximize either precision or recall of the top-ranked
predictions, which can be achieved by reducing the multilabel problem into a series of binary (One-vs-All) or multiclass
(Pick-all-Labels) problems. Missing labels are a ubiquitous phenomenon in XMC tasks, yet the interaction between missing
labels and multilabel reductions has hitherto only been investigated for the case of One-vs-All reduction. In this
paper, we close this gap by providing unbiased estimates for general (non-decomposable) multilabel losses, which enables
unbiased estimates of the Pick-all-Labels reduction, as well as the normalized reductions which are required for
consistency with the recall metric. We show that these estimators suffer from increased variance and may lead to
ill-posed optimization problems. To address this issue, we propose to use convex upper bounds which trade off an
increase in bias against a strong decrease in variance.

Unbiased Estimates for Multilabel Reductions of Extreme Classification with Missing Labels
Anonymous Author(s)
Affiliation
Address
email
Abstract
This paper considers the missing-labee problem in the extreme multilabel clas- sification (XMC) setting, i.c. setting with a very large label space. The goal XMC often is to maximize either precision or recall of the top-ranked predictions, which can achieved by reducing the multilabel problem into series of binary (One-vs-All) multiclass (Pick-all-Labels) problems. Missing labels are ubiqui- tous phenomenon in XMC tasks, yet the interaction between missing labels and multilabel reductions has hitherto only been investigated for the case of One-vs-All reduction. In this paper, we close this gap by providing unbiased estimates for general (non-decomposable) multilabel losses, which enables unbiased estimates the Fick-all-Labell reduction, as well as the normalized reductions which are required for consistency with the recall metric. We show that these estimators suffer from increased variance and may lead to ill-posed optimization problems. To address this issue, propose
6
10
12
convex upper bounds which trade off an increase in bias against a strong decrease in variance.
14
Introduction
15
Extreme multilabel classification (XMC) is machine learning setting in which the goal is predict a small subset of positive (or relevant) labels for each data instance out of a very large (thousands to
17
millions) set of possible labels. Such problems arise for example when annotating large encyclopedia
19
7 28), in fine-grained image classification (9. and next-word prediction (25). Further applications of
XMC recommendation systems, web-advertising and prediction of related searches [ 29 17 6).
21
Typical datasets in these scenarios are very large, resulting in possibly billions of (data, label) pairs []. making it impossible for human annotators to check each pair. Even annotating only few samples fully order to generate a clean test set can be prohibitively expensive. Therefore, both available training- and test-data are likely to contain some errors. Fortunately, in many cases it is possible to constrain the structure of the labeling errors. Consider, for example, the case tagging documents: Here,
23
24
25
assume that each label with which the document has been tagged has been deemed relevant by the annotator, and thus is relatively surely a correct label. On the other hand, the annotator cannot possibly check hundreds of thousands of negative labels. This leads to the setting
27
29 of missing labels investigated this paper, in which only positive labels are affected by noise (they go missing), whereas negative labels remain unchanged (no spurious labels). This model has been introduced to the XMC setting by Jain et al. [16), along with estimates for the propensities, the chance of relevant label to be observed. Similar models are using in learning-to-Pen
31
32
(0 27 37
33
For a formal definition the setting we refer the reader to section 3] and for more thorough discussion of prior works missing labels and related settings
and recommendation systems 32 14 15
35
section 6
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

36 A common strategy for learning XMC classifiers is to reduce the multilabel problem 34 into series of binary 8 3 40] or multiclass [8] 38 31] problems, which then can be solved using existing techniques. Such loss reductions can be shown to be consistent for the tasks of maximizing precision 39 at i or recall at k. but never both at the same time (24]. For one of these methods, One-vs-All,
37
38
40
adaptation to the missing labels setting has been shown to yield an improvement in propensity-scorel
41 precision (an unbiased estimate of precision @k) metrics [30]. The reductions consistent for precision lead to loss functions that can be decomposed into sum of contributions from each label, which means the results of Natarajan et al. [26] can be applied. In contrast, the reductions consistent for recall contain normalization term that is the inverse of the total number of true labels. This term is also necessary for calculating the recall metric itself, demonstrating the need for unbiased estimates for true, non -eoooocomeo multilabel loss functions.
43
45
47
Contributions Our contributions are 1) A mathematical model of the missing labels setting that describes the observed labels as product of an (unknown) mask variable with the true labels. Crucially, this mask can be chosen to be independent of the labels (Theorem [ enabling simple proofs for our theorems. 2) The unique unbiased estimate (Theorems 2 3
48
49
50
for arbitrary multilabel losses, and in particular for the loss functions arising from multilabel reductions. The unbiased estimate of a unbiased estimate leads to an increase in variance. Therefore, we develop 3) convex upper-bound 4 for losses based on the normalized Pick-all-Labels reduction. In the missing- labels setting, the generalization error is composed of two contributions: the error due to overfitting to the specific, observed noise-pat patter,,,, and the error because only a finite sample has been observed.
51
52
loss need not be lower-bounded, and even for bounded losses the
53
54
(Theorem
55
56
57 We present empirical evidence 4) that the former can be much stronger than the latter, and may be reduced by switching to the upper bounds.
58
59 In the main paper, we provide shortened proofs that illustrate the key steps. Detailed step-by-step proofs can be found in the appendix.
60
Notation Random variables will be denoted by capital letters X, Y. whereas calligraphic letters denote sets and lower case letters their elements, x E X.... Vectors will be denoted by bold font, 63 E y. if we plan to make use of the fact that they can be decomposed into components yi...... Vkk 64 with y-& denoting the vector of all components except the k t'th. The letters f. g. l and are reserved for functions, i, J. k denote integers, [k] is the set (l,...,Ai) ..... We denote with X' the duta space,
61
62
86 y = (0, 1}' the label space and Y' R' the prediction space. A dataset defined through the three 87 random variables X X Y E Y and Y E Y, that represent the data, observed label, and ground
68 truth label. We mark quantities pertaining to the unobservable ground-trun -ruth with a superscript star
69 and call (X, Y") the clean data.
2 Multilabel Reductions
71 In Menon et al. [4], five different reductions for turning the multilabel learning problem into sum of
72 binary multiclass problems are presented (cf. appendix). In the following, let fBc : {0, 1} x R
73 R be binary loss and {MC [4] IR' - R be a multiclass loss. Below, present four of those
74 reductions, and rearrange their loss functions so that a common pattern emerges.
75 For one-vs-all (OVA) reduction, each label is considered independently, meaning that for each
76 instance binary problems are be solved. This leads to loss function
lova (y",8)
Σ (uc(uf.00 03)
Σ Us (E 05) - (Oc 0;)) + (0c(0,0))
(1)
77 In contrast, pick-all-labels (PAL) considers all the positive labels for each instance and tries to 78 minimize their corresponding multiclass loss, leading to
ly
Σ (cc(i
Σ (c. JE(I]
j.y
79 Both approaches are consistent for precision at k. In order to make the reductions consistent for recall instead of precision, the label value needs to be replaced with a normalized label

---

03
y
0j
(3)
Lim1 Vi
Eins yi
81 where the expression on the right has the advantage of being well defined even if there are no positives 82 for the sample. This leads to the OVA-N and PAL-N reductions. By moving label-independent parts into functions/ f and gj. the reductions get a common structure
ex (yy f(y)
Σ {}) j=1
(4)
84 where 2; = 37 for the normalized reductions and 2j = ur otherwise. The functions / and gj are the same for the normalized and regular reduction (see appendix).
86 3 Unbiased Estimates with Missing Labels
87 We are interested in noisy labels where the noise is such that labels can only go missing. This is
88 described by the next definitions, where the first gives phenomenological characterization of
89 the setting, whereas the second defines the mathematical model used to describe it. For this setting
90 we then develop unbiased estimates for the preceding loss reductions, in the sense that for given
loss l we are looking for new loss function & such that E (( Y) -E e Et)
92 Definition (Propensity). The missing-labeli setting we described informally in the introduction
93 leads to the following conditions on the random variables
P(Y, = 1 1, 5 x} P)()),
Y P(V, = 1 1Y) 0, Y , x = (5)
94
The value (2) E (0. 1] is called the propensity of the label j at point
95
Such propensity models have been used in extreme classification
30
16 39
learning-to-rank
96
20
27
37 and recommendation systems 32
14 15).
97
The following proposition guarantees that a fixed pred-propensity unbiased estimator can be used to construct eestance-dependee unbiased estimator
98
99
Let ["(X,, Y*) be some function such that for fixed propensity p. an unbiased estimate is given by fp. i.e. Eifp(X,Y) = Elf "X,Y")], For mustance-dependen propensity p(z), an unbiased estimator of f given by fp(X)-
Proposition 1.
100
101
102
Proof. Using the law of total expectation gives
Exf"(X, = EE x]] (X
(X,xx)
103
Therefore, we will supress the dependence of the propensity on the data point in the rest of the paper. The relation between Y and can modeled by a set of independent mask variables M: Theorem (Masking Model), Assuming Y and follow Definition ! then then there exists a random variable M E {0. 13' such that Y = M & Y almost surely and Mj is independent of Y X, M ;) for all E [1]. It holds that E E(M P
104
105
108
107
108
This can be seen multilabel generalization of the similar statement given in Teisseyre et al. (33 The independent variables M provide a convenient framework for proving the results that follow, because the independence allows to factorize expectations containing M.
109
110
111
Proposition 2 2 (Unbiased Estimate for Decomposable Reductions). Assume the setting of Definition !
with the additional condition that the predictions Y are independent of the missing mask M. Then the unbiased estimate for the loss 4 with z y. denoted by l ((()),, is given by
112
((y.8) f(}) +
Vj
g3 (9).
(6)
Pj
3

---

114 The predictions have to be independent of the locations M where the labels go missing. This is fulfilled if the predictions Y = ix,, W) are the output of classifier h whose weights W are independent of M
115
116
117 For the normalized reductions, it would suffice to find unbiased estimate of Y in order to apply the same argument as above. However, we are not aware of a derivation for such an estimate that is simpler than the fully generic case presented below.
118
118
Theorem 2 (Unbiased Estimate for Non- Non-Decomposable Loss). For generic multilabel loss function E,, the unbiased estimate = (()))) under the conditions of Theorem is given by
121
0/
Pj) + Pa
P(y,8) = Σ II
e (y),
Pj
where y' 3 means {0, 3 v/} S y/-
122
This means that for instance with k positive labels, we need 2 evaluations of the original loss function in order to calculate the unbiased estimate. This is only feasible because, despite having a very large label space, typical extreme-classification datasets have only few positives per instance.
124
125
126
Unfortunately, the division by (products of) propensity values means that the unbiased estimates will have much larger variance than the original loss function would have on clean data. As an illustrative example, consider the binary case in the limit < 1. We can show that in this case the variance grows with compared to the evaluation clean data.
128
130
Proposition& 3 (Increase in Variance). Setting qº == E|y"] and l -L"),, ), for small propensities
p< < 1, the variance increases with the inverse of the propensity, VIe(Y, 5) কリ- Vie (Y", .))
131
132
This means that in the binary case the variance increases linearly with inverse propensity. In the multilabel case, this is amplified further due to the product of propensities.
138
134
The result above raises the question whether there might be other unbiased estimators with reduced variance. For example, the conditional expectation EEL (Y*, [X]Y] also gives an unbiased estimate with lower variance, but cannot be calculated without knowledge of the conditional probabilities P[Y X). }. The following theorem states that & ((() is unique if we want the loss function to work for all possible distributions of data. Thus we cannot reduce the variance.
136
138
139
Theorem (Uniqueness). Letp; (0, 1] Vj [1]. For an arbitrary loss function E', let l and E' be
140
unbiased versions, in the sense that for all X, Y, Y that fulfill the masking model Theorem / with propensity p. holds
141
Ele X) = E X)) FFC (Y,
142
Then, 8' =l
The unavoidable increase in variance indicates that there might be bias-variance trade-off between using the unbiased loss that may overfit more strongly on the observed noise, and using the original loss function which gives wrong results even if n co. If one calculates standard Rademacher bound for generalization (see appendix), this error bound increases with factor 2-p
144
146
147 In a classical learning setup, the generalization error would be described by the difference between Rí- [i.. However, in the case of missing labels, this
the empirical risk and the true risk RT-
h
148
149 can be decomposed in two ways
0
R [M] RR(M/]
Re(h R&[N] Re(AA] = [h] R [M] + R₁. [h] - Re(h)
= Ri.1/]
(10)
finite sample
noise partern
150 Whereas the first equation is just a restatement of the unbiasedness, the second contains some new 151 insight: The generalization error can be decomposed into the difference between the true risk R [h]
In this sense, we will use the notation E(y, 2) to evaluate loss also on a data point.
'The bound in this paper corresponds to Natarajan et al. [26) Thm. 9J. though that published result is wrong and missing the increase in the bound due to the increased range of the function.

---

and the empirical risk on clean training data R2, [h], and the difference between that and the estimated empirical risk observed data Re Re( Because the classifier h depends (through Y = M Y*) on the mask variables, E does not give an unbiased estimate (on training data) and thus the second term non-zero even in expectation. In fact, in the low-regularization regime this term may dominate the entire error, as we will demonstrate in Section 5
152
154
155
156
Convex Upper-Bounds
157
158
The unbiased estimate allows us calculate the loss even on data with missing labels, but can we also use it for training? Ideally, the loss function should be lower-bounded, so the minimization is well defined, it should be convex so the minimum is unique. Further, the variance of the unbiased estimator should not be too large, so that reasonable amount of training samples is sufficient.
159
180
If assume BB and (Mc to be bower-bounded and convex, then only the PAL-reduction results in an unbiased estimate that is guaranteed to have the same properties, as it is positive combination of (MC- Due to the uniqueness result, it is not possible to find unbiased estimate that is always convex for the other reductions. Thus, in order to make them amenable for training, we propose to switch from unbiased estimates to convex upper-bounds bounds. Below we present solutions for the OvA and normalized PAL-reduction. The normalized OVA-reduction remains an open problem.
169
165
187
Upper-Bound for OvA-Reduction The OvA-reduction is based 189 is convex surrogate for the 0-1 loss. To get a convex loss in the missing-labels case, we thus switch the order of operations [30 5: Instead of taking unbiased estimate of convex surrogate,
binary loss, which often
170
171
we form a convex surrogate of an unbiased estimate. Taking 0 to be a thresholding function (e.g.
172
((s) I 0}), the 0-1-loss can be written as
(v. 9) = y0) + (1 - v) (((1) 0(0))
(11)
with unbiased estimate
2 Pú -1 y0( + -) +
Pi (
(0-1
(12)
Pj
174 As the last term does not depend on the predictions, it can be dropped for an optimization objective. If (1, ú) is convex upper-bound on 0(ÿ) and (0, ú) (1 (()), so that overall LBc is convex upper-bound on the 0-1 loss, then performing these substitutions gives a convex loss function
176
177 for the OvA-reduction:
1 Σ j=1
((2-1 By (l. (1 y3 (Bc DT)
(y,A(y,8)
(13)
Pj
We have formulated the normalized multilabel reductions in terms of the variable Y A naive attempt of correcting for the noisy labels by replacing Y with Y/p is not unbiased. However, the resulting estimator Y turns out to be an upper bound. The two estimators are given by
Upper-Bound for Normalized
181
Y Ej
Ys/ps
8
(14)
Ejp YsPs
Theorem 4 (Normalized Label Üpper-Bounde Under the conditions of Theorem 2 183 true label with the unbiased estimate of the observed label as shown in Equation 14 results in an upper bound, whose error itself can be bounded by data- dependent term
replacing the
- Pj
Y:
Yi
2
Y
N
E Y1
(15)
Pj
Ps
Pj
Proof. For convenience denote S := Ejje Yj and S; E Ys/p;. and note that St is indepen-
186
dent of M,. By pulling out known factors and using the independence of M and Y we can show that
187
LSS; Y* = Σ WLMMy,5/0 Y+ Σ Yj M
Y== ST S
(16)
5

---

188
Expanding terms and using independence of M,, then applying the tower property and pulling out the measurable factor results in
189
M,Y,
/p:
M2 Pi
Y
E Y
1E
E
E
E
Y E
Y
1+
S
S.
S.
The function h R20 - R given by + 1/(1+ I) is convex, because its second derivative is 2(1 + t) -3 which larger than zero for non-negative Because S; 2 0 almost surely, we can apply Jensen's 's inequality to the inner expectation and use 16
190
Y
Y
Y
E
E
I+ES
Y
1+
On the other hand, we can use the Taylor formula with intermediate point Ç E [S,, S
to expand
-
+ S;
(17)
1 1 S
1 S
(1 S1+
(1+
192
Using Ç 2 0 to bound the denominator, then multiplying with Y," and taking the expectation gives
Y
Y S
<
+ -S
(18)
I+S
The variance term be calculated by substituting St and S expanding the sum, and using the independence of M to show that the mixed terms are zero:
194
Mj Pj
1)
E - S7) = E Y,
Σx jti
M,
)
Mj
M
Σ 3ø1
E
Σ
E8 E[x
E
E
Pj
Pj
Ph:
j&i top (
Σ JA
E
M
Mj
+
Pj
IE
Y
Y
(19)
Pj
Pj
jfi
Note that the transformation of equation crucial for this calculation, because it makes the mask variables in the numerator and denomina- tor independent.
Table I: Error bound for XMC datasets
196
Dataset
Average
Worst Case
Eurlex-4K
0.02
0.51
198
AmazonCat-133
0.0006
0.24
199
In practice, most entries of the co-occurrence matrix EE[Y; Yj] will be extremely small, caus-
200
ing only minute contribution to the error bound. This can be illustrated by calculating, two real datasets, the upper-bound for the error of the proposed estimator, by approximating E|Y; Y,J with estimated as in Jain et al. [16]. Looking at the mean value, and the worst case for any label (Table 1). We can see that the error on average is very small, indicating that the worst-case bound only applies very few labels.
202
the label co-occurrence frequency. The propensities
204
208
Corollary (PAL Upper-Bound), Under the assumptions of Theorem 2 if the underlying multiclass
207
loss tMC is non-negative convex function, the expression
Ys/p:
ily = E
j=1 II+ (mclj.ý)
(20)
208
gives a nonnegative, convex upper- on the true normalized PAL loss in expectation.
Experimental Results
209
In this section we present some empirical evidence that illustrates the influence of missing labels and 211 the unbiased estimates and upper bounds on overfitting and bias-variance trade-off. Additional results and more detailed description of the procedure can be found in the appendix.

---

20
unbiased
upper-bound
15
standard
true value
Recall @
10
11.5
5
11
10.7
0.5
0.55
0.6
0.2
0.25
0.3
0.35
0.4
0.45
0.5
0.55
0.6
0.65
0.7
propensity
Figure 1: Unbiased estimate of per-example recall with artificial data described in the main text. The shaded region corresponds to one standard deviation, estimated over 100 repetitions. The black line denotes the true recall.
213
Prediction Setting First, we want to demonstrate the variance problem in a simple prediction setting, where the classifier is fixed and we want to determine its performance. Consider setting in which there are 100 different labels, which are independent and each has probability of 10%. We randomly draw 10 000 ground-truth label vectors, and generate observed labels by removing according to a propensity p that identical for all labels. The predictions are generated by randomly choosing label from the ground-truth. We calculate the average per-example recall using the standard estimator, the unbiased estimator, and the upper bound, and plot the results in Figure
215
217
219
As can be seen, for moderate propensities the unbiased estimator works well, but for propensities below 0.45 the 10000 samples are not sufficient to get an accurate estimate. this setting, the upper-bound results in larger error than using the standard estimator.
221
223
Training Setting Ideally, we would benchmark our loss functions on a real XMC task. However, validate that the unbiased estimates and
for those neither know the exact propensities, upper bounds produce reasonable results, since the fully-labeled ground truth is unknown.
225
Instead of using fully artificial data, chose to construct dataset based existing data: We took AmazonCat- 22) and consider only the 100 most common labels, which are the ones with the highest propensity according Jain et al. [16]. We artificially remove labels according to inverse propensity, which increases linearly based on the ordering of label frequencies, such that the most common label has inverse propensity of 2 and the 100th most common of 20. This process partially preserves the strong imbalances that are typical of extreme classification datasets.
227
229
231
On this data, we train linear classifier with Iæ-regularization using different basis loss functions with a) the original (standard) loss on clean training data and b) noisy training data, as well as e) the unbiased version and d) the upper-bound version noisy data. For each training run, we evaluate
233
235 the loss on noisy and clean training and test data. For the evaluation on noisy data, the corresponding unbiased estimators used.
In this lincar-classffier experiment, the noise-pattern overfitting is much stronger than the overfitting due to finite sampling Figure shows this for the case of the BCE loss in OvA-reduction and CCE loss in normalized PAL reduction. For the classifier trained on clean data (blue), the weights are independent of the noise pattern and thus the dashed and dotted lines coincide in expectation. For case of OvA reduction using the BCE loss, the training loss gets reduced much further using the unbiased loss function or the upper-bound loss function than using the standard loss. This decrease
239
241
243
more than compensates the increase generalization gap, and as such the minimal loss better with these two variants of the loss function. In contrast, in the non nonmdccomposable case, even though

---

0.150
Setting
0.125
clean
standard b)
0.100
loss
unbiased
0.075
bound d)
Evaluation
0.050
clean test RA--
0.025
noisy train Rg
0.000
clean train R₁
10-7
10 10-6
10
10
10
10
10
10
L
5
Setting
clean a)
standard b)
3
loss
unbiased c)
2
bound d)
Evaluation
clean test RA-
0
noisy train R; clean train Ri-
-1
10 10 10
10
10
10
L2
Figure 2: Binary cross-entropy (top) and normalized categorical cross-entropy (bottom) for different regularization strengths, evaluated on noisy training data, clean training data, and clean data. The gaps between dashed and dotted lines correspond to overfitting to the noise pattern, the smaller gaps between dotted and solid lines show the generalization gaps due the finite training sample. As the dashed lines are for noisy data, they are calculated using the unbiased estimate (6)
245
the observed training loss decreases drastically with the unbiased loss, the increase in overfitting makes the test loss worse than using the biased standard loss function.
247 In this case, using the upper-bound 20 can mitigate the effect, though there still significant overfitting, evidenced by the estimated training loss being less than zero. This is possible because
249
even though the loss we use for training a non-negative upper bound on the expected unbiased loss, the dashed curves show the value estimated for the loss using the unbiased estimator, which can be negative due to overfitting. For the OVA case, the upper bound (3) also reduces overfitting, but does not result in overall better classifier on test data.
251
253
In terms of the bias-variance trade-off, for training noisy data is larger than on clean data. It is also larger when using the unbiased or upper-bound loss as compared to standard loss. This is as expected from the variance analysis and generalization bound presented in the theory.
graphs show clear trend: The optimal regularization
255

---

257
6
Related Work
258
Unbiased Estimates for Noisy Labels Learning with missing labels is a specific instance of
259
learning with class-conditional noise. For the case of binary labels, unbiased estimates of the loss function can be found in Natarajan et al. [26). A more general approach is given in Van Rooyen and Williamson 335. In their notation, f is a function and the probability distribution over clean data, that is transformed by the invertible operator T into a corrupted probability distribution. Let R be the inverse of T, and R its adjoint, then (P, = (R o [) = (T(P), (J)).. This equation forms the basis for their "Theorem 5 (Corruption Corrected Loss)", which states that corruption corrected function IR is given Va E A by (R(:.)) ) = R* (I(-, a)), where A denotes the set of possible actions that will be evaluated by the loss functions. For finite label space with n possible, the operator R* can be represented with an n x n matrix. For the multilabel case here, applying this naively would require 2' evaluations of the original loss function. In contrast, the direct approach presented in section 3 is much more efficient.
280
261
262
263
264
265
267
289
270
Alternatives In some settings with noisy labels, it is possible to use a learning algorithm that is inherently noise tolerant [2 36). Certain performance objectives such as the balanced error or the
271
272
AUC are noise robust even under the more general setting of mutually contaminated distributions as shown in Menon al. 22). A data re-calibration approach tries identify from the training data which samples are corrupted, e.g. by looking at samples for which the network is very unsure, and
273
274
275
adapt the training process correspondingly [13 42 19 It is also possible to first train scorer on the
276
noisy data naively, from which classifier adapted to given rate of missing labels can be constructed
277
by choosing an appropriate threshold [23]. Similarly, the inference procedure of PLTs can be adapted
to take into account propensity model [39]
Related Learning Settings Learning with missing labels is highly related to learning from positive and unlabeled (PU) data [[]] An unbiased loss function for this setting is given in Du Plessis et al. The appearing difficulties, that non-negativity and convexity need not be preserved, are the same as in our setting (2.. A slightly different setting with missing labels is given by semi-supervised learning, where it is know for which labels are missing [4
280
281
282
283
7
Summary and Discussion
284
This paper provides unbiased estimates for four cases of multilabel reductions given in Menon et al. [24]. Except for the PAL reduction, these estimators can be non-convex and even negatively unbounded. The unbiased estimates come with an increase in variance. This is unavoidable if unbiasedness is required, as the estimators can be shown to be unique. If sufficient training data is available, then the unbiased loss functions can be used, but for the normalized reductions we found that even 1.2 million instances in AmazonCat are not enough. Much fewer data points are needed in order estimate the overall loss of a classifier. This is because for training, an accurate estimate for [T" h(X) X needs to be formed, whereas for evaluation this is averaged over the entire dataset, E(e(Y*, (()).. This indicates that the unbiased estimates can be useful for hyperparameter tuning and model selection.
286
287
288
289
290
291
292
293
294
For training, however, another approach is needed. A method that fixes the negative unboundednesss and non-convexity and also reduces the variance is to switch to a convex upper-bound. We have shown that this can stabilize the training and improve the results.
296
287
296
Furthermore, the data in section 5 suggest training with missing labels requires more regularization, irrespective of whether training uses standard-, unbiased-, or convex upper-bound losses. Our findings agree with Arpit et al. 2 who found that typical regularizers prevent deep network from memorizing noisy examples, while not hindering the learning of patterns from clean instances.
300
302
All in all, our results show that a) unbiasedness can be achieved for generic multilabel losses, and in particular the losses resulting from multilabel reduction, but also that b) these losses might not
303
304
be suitable for optimization. We have presented one method that trades away unbiasedness for the
ability to handle training with lower amounts of data. An exciting future research prospect would be
306
to investigate families of loss functions that can continuously trade off bias and variance, and thus allow for optimal training with different amounts of available data.

---

References
308
309
[1] 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, WWW '13, page 13-24, New York, NY, USA, 2013. Association for Computing Machinery.
311
312
[2] D. Arpit, S. Jastrzebski, N. Ballas, D. Krueger, E. Bengio, M. Kanwal, T. Maharaj, A. Fischer, 313
314
A. Courville, Y. Bengio, and S. Lacoste-Julien. A Closer Look at Memorization in Deep Networks. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 233-242. PMLR, 06-11 Aug 2017.
315
318
317
[3] R. Babbar and B. Schölkopf. Dismec: Distributed sparse machines for extreme multi-label classification. In WSDM, pages 721-729, 2017.
318
319
[4] K. Bhatia, K. Dahiya, H. Jain, Y. Prabhu, and M. Varma. The extreme classification repository: artp///ommloodd///////lllepsssss Multi-label datasets and code. htttp:/manikvarrnt
321
html 2016.
322
[5] Y.-T. Chou, G. Niu, H.-T. Lin, and M. Sugiyama. Unbiased Risk Estimators Can Mislead: A Case Study of Learning with Complementary Labels. In International Conference on Machine Learning, pages 1929-1938 PMLR, Nov. 2020.
324
325
[6] K. Dahiya, A. Agarwal, D. Saini, K. Gururaj, J. Jiao, A. Singh, S. Agarwal, P. Kar, and M. Varma. Siamesexml: Siamese networks meet extreme classifiers with 100m labels. In Proceedings of the International Conference on Machine Learning, July 2021.
326
327
328
[7] O. Dekel and O. Shamir.
classification with more classes than examples. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pages 137-144, 2010.
329
330
[8] K. Dembczynski, W. Cheng, and E. Hüllermeier. Bayes optimal multilabel classification via probabilistic classifier chains. In ICML, 2010.
332
333 [9] J. Deng, A. C. Berg, K. Li, and L. Fei-Fei. What does classifying more than 10,000 image categories tell us? In ECCV, 2010.
335
[10] M. Du Plessis, G. Niu, and M. Sugiyama. Convex formulation for learning from positive and unlabeled data. In International conference on machine learning, pages 1386-1394, 2015.
336
337
[1]] C. Elkan and K. Noto. Learning classifiers from only positive and unlabeled data. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. KDD '08, pages 213-220 New York, NY, USA, Aug. 2008. Association for Computing Machinery.
338
339
340
341
[12] A. Ghosh, N. Manwani, and P. S. Sastry. Making risk minimization tolerant to label noise. Neurocomputing, 160:93-107, 2015. Publisher: Elsevier.
[13] B. Han, Q. Yao, X. Yu, G. Niu, M. Xu, W. Hu, I. Tsang, and M. Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
314
346
347 [14] J. Huang, H. Oosterhuis, M. De Rijke, and H. Van Hoof. Keeping dataset biases out of the simulation: A debiased simulator for reinforcement learning based recommender systems. In Fourteenth ACM conference on recommender systems, pages 190-199, 2020.
348
349
350
[15] J. Huang, H. Oosterhuis, and M. de Rijke. It is different when items are older: Debiasing recommendations when selection bias and user preferences are dynamic. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pages 381-389, 2022.
351
352
353
354
[16] H. Jain, Y. Prabhu, and M. Varma. Extreme multi-label loss functions for recommendation, tagging, ranking and other missing label applications. In KDD, August 2016.
10

---

356
[17] H. Jain, V. Balasubramanian, B. Chunduri, and M. Varma. Slice: Scalable linear extreme classifiers trained on 100 million labels for related searches. In WSDM, pages 528-536, 2019.
357
358
[18] Y. Jernite, A. Choromanska, and D. Sontag. Simultaneous learning of trees and representations for extreme classification and density estimation. In D. Precup and Y. W. Teh, editors, Proceed- ings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1665-1674, PMLR, 06-11 Aug 2017.
359
360
362
[19] L. Jiang, Z. Zhou, T. Leung, L.-J. Li, and L. Fei-Fei. MentorNet: Learning data-driven curriculum for very deep neural networks on corrupted labels. In J. Dy and A. Krause, edi- tors. Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Reseurch, pages 2304-2313. PMLR, 10-15 Jul 2018.
363
365
386
[20] T. Joachims, A. Swaminathan, and T. Schnabel. Unbiased learning-to- -triin with biased feedback. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, pages 781-789, 2017.
368
389
[21] R. Kiryo, G. Niu, M. C. du Plessis, and M. Sugiyama. Positive-nnlablle Learning with Non-Negative Risk Estimator. In I. Guyon, U. V. Luxburg, S. Bengioo, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems
371
372
30, pages 1675-1685. Curran Associates, Inc., 2017.
[22] J. McAuley and J. Leskovec. Hidden factors and hidden topics: understanding rating dimensions with review text. In Proceedings of the 7th ACM conference on Recommender systems, pages 165-172, 2013.
374
375
[23] A. Menon, B. Van Rooyen, C. S. Ong, and B. Williamson. Learning from corrupted binary labels via class-probability estimation. In International Conference on Machine Learning, pages 1 125-134, 2015.
377
378
[24] A. K. Menon, A. S. Rawat, S. Reddi, and S. Kumar. Multilabel reductions: what is my loss optimising? Advances in Neural Information Processing Systems, 32, 2019.
380
381
[25] T. Mikolov, K. Chen, G. Corrado, and J. Dean. Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3788 2013.
382
383
26 N. Natarajan, I. S. Dhillon, P. Ravikumar, and A. Tewari. Cost-sensitive learning with noisy labels. The Journal of Machine Learning Research, 18(1):666656698, 2017. Publisher: JMLR. org.
384
385
386
[27] H. Oosterhuis and M. de Rijke. Policy-aware unbiased learning to rank for top-k rankings. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 489 -999, 2020.
387
388
389
[28] I. Partalas, A. Kosmopoulos, N. Baskiotis, T. Artieres, G. Paliouras, E. Gaussier, I. Androut- sopoulos, M.-R. Amini, and P. Galinari. Lshte: A benchmark for large-scale text classification. arXiv preprint arXiv: arXiv:1503.008 085581, 2015.
390
391
392
[29] Y. Prabhu and M. Varma. Fastxml: A fast, accurate and stable tree-classifier for extreme multi-label learning. In KDD, pages 263-272. ACM, 2014.
383
394
[30] M. Qaraci. E. Schultheis. P. Gupta, and R. Babbar. Convex Surrogates for Unbiased Loss Functions in Extreme Classification With Missing Labels. In Proceedings of the Web Conference 2021, pages 371 1711-3720 Ljubljana Slovenia, Apr. 2021. ACM.
395
396
397 [3] S. J. Reddi. S. Kale, F. Yu, D. Holtmann-Ries Rice, J. Chen, and S. Kumar. Stochastic negative mining for learning with large output spaces. In K. Chaudhuri and M. Sugiyama, editors. P Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statisties, volume 89 of Proceedings of Machine Learning Research, pages 1940-1949. PMLR, 16-18 Apr 2019.
398
389
400
402
[32] N. Sachdeva, C.-J Wu, and J. McAuley. On sampling collaborative filtering datasets. In Proceedings of the Fifteenth ACM International Conference on Weh Search and Data Mining, WSDM '22, page 842-850, New York, NY, USA, 2022. Association for Computing Machinery.
403
11

---

405
[33] P. Teisseyre, J. Mielniczuk, and M. Lazecka. Different strategies of fitting logistic regression for positive and unlabelled data. In V. V. Krzhizhanowskaya, G. Závodszky, M. Lees, J. J. Dongarra, P. M. A. Sloot, S. Brissos, and J. Teixeira, editors, Computational Science - ICCS 2020, pages 3-17, Cham, 2020. Springer International Publishing. ISBN 978-3-030-50423--
406
408
409
[34] G. Tsoumakas and M. Katakis. Multi-label classification: An overview. Int. J. Data Warehous. Min., 3:,-13, 2007.
411
[35] B. Van Rooyen and C. Williammsn. theory of learning with corrupted labels. The Journal of Machine Learning Research, 18(1):8501-8855) 2017. ISSN 1532-4435.
412
[36] B. Van Rooyen, A. Menon, and R. C. Williamson. Learning with symmetric label noise: The importance of being unhinged. Advances in Neural Information Processing Systems, pages 10-18. 2015.
414
416
[37] X. Wu, Chen, Zhao, L. He, D. Yin, and Y. Chang. Unbiased learning to rank in feeds recommendation. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pages 490-498, 2021.
417
418
419
[38] M. Wydmuch, K. Jasinska, M. Kuznetsov, R. Busa-Fekete, and Dembezynski. no-regret generalization of hierarchical softmax to extreme multi-label classification. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
421
[39] M. Wydmuch, K. Jasinska-Kobus R. Babbar, and K. Dembezynski. Cropensity-Scoree Proba- bilistic Label Trees, page 2252-2256. Association for Computing Machinery, New York, NY, USA, 2021.
424
425
426
[40] R. You, Z.. Zhang, Z. Wang. S. Dai, H. Mamitsuka, and Zhu. Attentionxml: Label tree-based attention-aware deep model for high-performance extreme multi-label text classification. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
427
428
[41] H.-F Yu, P. Jain, P. Kar, and I. Dhillon. Large-scale multi-label learning with missing labels. In International conference on machine learning, pages 593-601, 2014.
431
[42] S. Zheng, P. Wu, A. Goswami, M. Goswami, D. Metaxas, and C. Chen. Ervor-bounded correction of noisy labels. In International Conference on Machine Learning, pages 11 11447-11457. PMIR, 2020.
433
Checklist
435
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
438
contributions and scope? [Yes]
439
(b) Did you descrihe the limitations of your work? [Yes]
440
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
442
443
2. If you are including theoretical results...
444
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
445
(b) Did you include complete proofs of all theoretical results? [Yes] Some proofs are in the appendix
447
3. If you ran experiments..
448
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
449
450
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
12

---

452
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
453
454
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [No]
456
4. If you are using existing assets (e.g., code, data, models) or curating/releasng new assets...
457
(a) If your work uses existing assets, did you cite the creators? [Yes]
458
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
460
461
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
463
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
485
5.
If you used crowdsourcing or conducted research with human subjects...
466
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
468
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
489
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
471
13


Reviews:
[{"review_id": "u9AD1Sd9YX", "reviewer": "Reviewer_YLGN", "summary": "In this paper, the authors address the problem of unbiased estimates for multi-label reductions of extreme classification with missing labels. Specifically, the unbiased estimates for four cases of multi-label reductions are discussed. The authors first show the unbiased estimates for general multi-label losses capable for pick-all-labels and normalized reductions, and then prove the upper-bounds for two reductions, which trade-off bias and variance. The empirical experiments demonstrate the influence of missing labels, as well as unbiased estimates. The results also indicate that although unbiased loss functions work well with sufficient training data, normalized reductions can still be starving. Besides, the authors also show that generic multi-label losses with achievable unbiasedness could not be suitable for optimization while the presented trade-off method works well for handling training with fewer data.", "questions": "* Most of the existing state-of-the-art methods for XMC problems are tree-based methods. In each layer, not all of the labels will participate in optimization and loss calculations. Moreover, the predictions and inference also usually are based on beam search. I wonder if the conclusions and guidelines can be also applied to those methods.\n\n* The authors model missing-label setting by treating them as independent noises, but real-world noises can be more complicated with many different distributions and correlations among labels. I wonder if the methods can be further extended to more different types of noises (or distributions of missing labels).", "limitations": "The authors did not address any limitations and potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n* Comprehensive coverage on different types and cases reductions.\n* Theorems and proofs for both unbiased estimates and convex upper-bounds.\n* Empirical studies and practical conclusions that emphasize the contributions\n\nWeaknesses\n* Lack of discussions on the relations to tree-based XMC methods, which are one of the most popular conventional methods for tackling XMC problems.\n* Lack of discussions of different types of noises.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ssMSbU07RQ7", "reviewer": "Reviewer_6sB5", "summary": "This paper discusses the problem of  missing labels in extreme multi-label classification (XMC). First a framework for defining the loss function is defined, which can be applied to various one-vs-all (OVA) and pick-all-labels reduction methods. Next, unbiased estimators for the loss functions based on propensity  are discussed, and it is shown that such estimators have high variance. Next, convex upper-bounds for the loss functions are discussed, in order to obtain efficient solvers. Numerical results on two datasets are presented to illustrate the various aspects of missing labels in XMC problems.\n", "questions": "Missing labels is an important problem in XMC literature. The paper might be presenting an interesting framework for solving XMC problems with missing labels. \nHowever, the current version of the paper has the following shortcomings:  \n\n1. Significance: Unbiased loss functions for XMC with missing labels have been proposed before, see [1],[2]. It is not clear how the proposed estimators in this paper differ from the existing ones and what are the significance of the proposed estimators. Also, certain aspects are  not clear, eg., why the upper bounds would have reduced variance and how the bias looks like in these cases.\n\n2. Numerical results: The experiment results seem limited. Only two datasets are considered. Many aspects of the framework are not studied, e.g., whether the considers loss functions solve the original XMC problem efficiently, what type of XMC algorithms perform best (OvA or PAL), also, comparison to [1],[2] would be helpful to better understand the advantages of the popped framework. \n\n3. Scalibity: Since in XMC set up, the number of instances and labels can be very large (in millions), it is not clear if OvA or PAL is scalable. There are many other reduction methods (label reduction or tree based methods) that are scalable. So, it is not clear if studying OvA type methods is useful in XMC settings.\n\n\n4. Minor comment:\ni. In Theorem 2, under the conditions of Theorem 2 --> under the conditions of Proposition 2?\n\n\nReferences:\n\n[1] Schultheis, Erik, and Rohit Babbar. \"Unbiased Loss Functions for Multilabel Classification with Missing Labels.\" arXiv preprint arXiv:2109.11282 (2021).\n\n[2] Schultheis, Erik, et al. \"Unbiased Loss Functions for Extreme Classification With Missing Labels.\" arXiv preprint arXiv:2007.00237 (2020).\n", "limitations": "Yes, the paper addresses these.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strengths of the paper  are:\n1. An important problem in XMC, that of missing labels is discussed.\n2. Unbiased loss functions and their convex upper bounds are discussed.\n3. The framework is general and addressed a range of XMC methods that can be written as OvA or PAL.\n\nThe weaknesses of the paper  are:\n1. Significance of the results are not clear.\n2. Numerical results seem limited.\n3. Scalability issues are not addressed.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "d1dlEeVTKiL", "reviewer": "Reviewer_s9K4", "summary": "The paper studies the problem of extreme multi-label learning with missing labels. To solve the problem, the paper considers reducing the multi-label problem into a serious binary or multi-class problems. To deal with missing labels, the paper proposes unbiased estimates for multi-label reduction loss functions. To reduce the variance of estimates, the paper proposes convex upper-bound for the OVA and PAL-reduction.", "questions": "In experiments, why use BCE for OVA reduction and CCE for PAL reduction? \n\nIn Related Work, authors claim that “learning with missing labels is a specific” instance of learning with class-conditional noise. Why? Is it there any reference?", "limitations": "The experiments are weak due to the lack of comparison with counterpart methods. The results on real-world scenarios are also insufficient.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\n1.The paper proposes a framework for dealing with missing labels in extreme multi-label setting. In the proposed framework, the unbiased estimates in terms of decomposable reduction and non-decomposable losses under missing-label setting are derived.\n\n2.To deal with issue of increased variance, the paper proposes convex upper bounds for normalized PAL reduction, which provides trade-off between bias and variance.\n\nWeakness\n\n1.The experiments are weak. The paper only conducts a toy experiment and an experiment on a real-world dataset. Furthermore, the proposed method does not compare with other counterpart methods. The experimental results on the current submission are insufficient to validate the effectiveness of the proposed method.\n\n2.The paper is not well written. Many important details are missed or placed on the appendix, which make the paper hard to understand. For example, Eq.(4) is difficult to understand without any detailed introduction (in appendix). This makes this paper become difficult to follow. The organization of this paper should be improved. For example, the figures in experiments are too large with limited information.\n\n3.The paper fails to sufficiently discuss its pioneering works. Many related works are missed. For example, authors do not discuss the relevant works in extreme multi-label classification that are very relevant to this work. The very relevant works about multi-label noise are also missed.\n", "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": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "7IRcOKRoeJh", "reviewer": "Reviewer_uLF6", "summary": "This paper tackles the missing label problem in the Extreme Classification setting. In particular -\n1) It provides unbiased estimation of all kind of losses (decomposable or non decomposable over labels) under the missing label setting. Previous papers mostly focused on decomposable losses.\n2) Shows that if propensities are low then these losses can have very high variance and may lead to ill-posed optimization problems.\n3) Proposes to use convex upper bounds of these losses which significantly reduces the variance at cost of slight increase in bias.\n ", "questions": "It would have been nice to see if the proposed convex upper bound framework actually improves the performance on standard tasks/datasets. I believe for a lot of public datasets the propensity scores have been provided [1] so it should be pretty simple to try them out and compare against methods which do not take variance reduction into account.\n\n[1] The Extreme Classification Repository: Multi-label Datasets & Code: http://manikvarma.org/downloads/XC/XMLRepository.html", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: While the issue of high variance with inverse propensity models has been explored previously such as in [1], this paper studies it in the extreme classification setting where it hasn't been explored much. \n\nQuality: In terms of experimental results I feel like the paper is a bit weak. It would have been good to see some comparison of the proposed technique with other popular variance reduction methods such as one proposed in [1]\n\n\n[1] Swaminathan, Adith, and Thorsten Joachims. \"Counterfactual risk minimization: Learning from logged bandit feedback.\" International Conference on Machine Learning. PMLR, 2015", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject