Generalized test utilities for long-tail performance in extreme multi-label classification
Authors: Erik Schultheis
Marek Wydmuch
Wojciech Kotlowski
Rohit Babbar
Krzysztof Dembczynski
Venue: NeurIPS 2023 poster (2023)
Keywords: extreme multi-label classification
long-tail labels performance
complex performance measures

Abstract: Extreme multi-label classification (XMLC) is the task of selecting a small subset of relevant labels from a very large set of possible labels. 
As such, it is characterized by long-tail labels, i.e., most labels have very few positive instances. With standard performance measures such as precision@k, a classifier can ignore tail labels and still report good performance. However, it is often argued that correct predictions in the tail are more "interesting" or "rewarding," but the community has not yet settled on a metric capturing this intuitive concept. The existing propensity-scored metrics fall short on this goal by confounding the problems of long-tail and missing labels. In this paper, we analyze generalized metrics budgeted "at k" as an alternative solution. To tackle the challenging problem of optimizing these metrics, we formulate it in the expected test utility (ETU) framework, which aims to optimize the expected performance on a given test set. We derive optimal prediction rules and construct their computationally efficient approximations with provable regret guarantees and being robust against model misspecification. Our algorithm, based on block coordinate descent, scales effortlessly to XMLC problems and obtains promising results in terms of long-tail performance.

Generalized test utilities for long-tail performance in extreme multi-label classification
Erik Schultheis
Marek Wydmuch
Aalto University Helsinki, Finland
Poznan University of Technology
Poznan, Poland
erik. whh.hhhhshsssssatto.... fi
mwydmuchêcs put. poznan. pl
Wojeiech Kotlowski
Rohit Babbar
Poznan University Technology Poznan, Poland wkotlowski0cs put poznan. pl
University Bath Aalto University Bath, UK Helsinki, Finland rb26080bath. ac. uk
Krzysztof Dembezyíski
Yahoo! Research / Poznan University of Technology New York, USA / Pozman, Poland
krzysztof www.r/dd..eeeeeeeaaaeeeoooooc..o
Abstract
Extreme multi-lahel classification (XMLC) is the task of selecting small subset of relevant labels from a very large set of possible labels. As such, it is characterized by long-tail labels, i.e., most labels have very few positive instances. With standard performance measures such as precision@k. a classifier can ignore tail labels and still report good performance. However, it often argued that correct predictions in the tail are more "interesting" or "rewarding," but the community has not yet settled metric capturing this intuitive concept. The existing propensity-scored metrics fall short on this goal by confounding the problems of long-tail and missing labels. In this paper, we analyze generalized metrics budgeted "at k" solution. To tackle the challenging problem of optimizing these metrics, we formulate in the expected test utility (ETU) framework, which aims to optimize the expected performance on fixed test set. We derive optimal prediction rules and construct computationally efficient approximations with provable regret guarantees and robustness against model misspecification. Our algorithm, based on block coordinate ascent, scales effortlessly to XMLC problems and obtains promising results in terms of long-tail performance.
alternative
Introduction
Extreme multi-label classification (XMLC) is challenging task with a wide spectrum of real-life
applications, such as tagging of text documents 10] content annotation for multimedia search [14). different type of recommendation ( 33
28 Because of the nature of its applications,
the typical approach in XMLCC is to predict exactly & labels (e.g., corresponding to k slots in the user interface) which optimize a standard performance metric such as precision or (normalized) discounted cumulative gain. Given the enormous number of labels in XMLC tasks, which can reach millions more, it is not surprising that many of them are very sparse, and hence make the label distribution strongly long-tailes tailed (2). It has been noticed that algorithms can achieve high performance on the standard metrics, but never predict any tail labels 42 Therefore, there is need to develop
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Performance measures (%) on AmazonCat- C3k of a classifier trained on the full set of labels and classifier trained with only 1k head labels.
Metric
full labels @3
head labels @33 (ditt.)
@
@
(ditt.)
@5 (dift.)
Precision
93.03
78.51
63.74
93.08 (+0.05%)
76.42 (-2.66%)
58.21 (-8.679)
nDCG
93.03
87.25
85.35
93.08 (+0.05%)
85.75 (-1.11%)
80.91 (-5.19%)
PS- PS-Prrcision
49.76
62.63
70.35
49.07 (-1.99%)
57.71 (-7.44%)
57.41 (-18.40%)
Macro-Precision
13.28
32.65
44.16
4.31 (-67,54%)
5.28 (-83.82%)
4.32 (-90.219)
Macro-Recall
1.38
11.06
30.57
0.47 (-65.61%)
2.69 (-75.715)
4.10 (-86.598)
Macro-F1
2.26
14.67
32.84
0.74 (467.37%)
3.10 (-78.88%)
3.77 (-88.519)
Coverage 15.19
40.53
60.88
5.11 (-66.329)
7.37 (-81.825)
7.52 (-87 (-87.654)
metric that prefers "rewarding" 48 "diverse" 3 and "rare and informative" [34 labels over
frequently-occurring head labels. Currently, the XMLC community attempts to capture this need using sespeenstty-scoree performance metrics [15]. These metrics give increased weight to tail labels, but have been derived from the perspective of missing labels, and as such they are not really solving the problem of tail labels [4].
In Table I we compare different metrics for budgeted at k predictions. We train a PLT model [7 on the full AMAZONCAT- 3 dataset (27) and reduced version with the 1000 most popular labels only, The test performed for both models on the full set of labels. The standard metrics are only slightly perturbed by reducing the label space to the head labels. This holds even for propensity-scores precision, which decreases by just -00 despite discarding over 90% of the label space. In contrast, macro measures and coverage decrease between 60% and 90% if tail labels are ignored. These results show that budgeted-att k macro measures might be very attractive in the context of long tails. Macro-averaging treats all the labels equally important, preventing the labels with small number of positive examples to be ignored. Furthermore, the budget of k: labels "requires" " the presence of fong-tail labels in a compact set of predicted labels.
While we can easily use these measures to evaluate and compare different methods, we also would like to make predictions that directly optimize these metrics. The existing approaches to macro- averreed metrics consider the unconstrained case, in which label-wise optimization is possible [47 23
16 22 26. Each binary problem can be then solved under one of two frameworks for optimizing
complex performance measures, namely population utility (PU) or expected test utility (ETU) 49
The former aims at optimizing the performance on the population level. The latter optimizes the performance directly on a given test set. Interestingly, in both frameworks the optimal solution is based on thresholding conditional label probabilities [1], but the resulting thresholds are different with the discrepancy diminishing with the size of the test set. The threshold tuning for PU usually performed on validation set [47 26), while the exact optimization for ETU is performed test set. It requires cubic time in a general case and quadratic time in some special cases [49 Approximate solutions can be obtained in linear time [25] 12].
These approaches cannot be directly applied if prediction of exactly k: labels for each instance is required. In such case, the optimization problems for different labels are tightly coupled through this constraint, making the final problem much more difficult. Despite the fact that optimization of com- plex performance metrics is well-established problem, considered not only in binary and multi-label classification as discussed above, but also in multi-class classification [30 RT the results presented in this paper go beyond the state-of-the-att in this context. Let us underline that the requirement of & predictions is natural for recommendation systems, in which exactly A slots available in the user interface to display recommendations. Even in situations where this does not apply, requiring the prediction to be "at kn can be advantagcous, as it prevents trivial solutions such as predicting nothing (for precision) everything (for recall).
att - predictions have not yet been analyzed
In this paper, we investigate optimal solutions for the class of utility functions that can be linearly decomposed over labels into binary utilities, which includes both instance- weighted measures and macro-averages. We solve the problem in the ETU framework which is well-suited, for example, to recommendation tasks in which recommendations for all users or items are rebuilt in regular intervals. this case, we can first obtain probability estimates of individual labels for each instance in the test set, and then provide optimal predictions for given metric based these estimates. We

---

derive optimal prediction rules and construct computationally efficient approximations with provable guarantees, formally quantifying the influence of the estimation error of the label probabilities on the suboptimality of the resulting classifier. This result is expressed in the form of a regret bound 80 22 13 It turns out that for most metrics of interest, a small estimation error results in at most a small drop of the performance, which confirms our method is viable for applications. Our general algorithm, based on block coordinate ascent, scales effortlessly to XMLC problems and obtains promising empirical results.
2 Setup and notation
Let a E X denote an input instance, and y E distributed according to (fyla)). We consider the prediction problem in the expected test utility (ETU) framework, that is, we assume that we are given a known set of ni instances X = [=i,...., 2n,] E x with unknown labels, on which we have make predictions Our goal a set of exactly & (out of m) labels represented as k-hot vector D; E Y4 == {y E y : l k}. and we let Y ju...... "n denote the entire n x m prediction matrix for a set of instances X.
the vector indicating the relevant labels,
assign each instance I;
In the ETU framework, we treat as given and only make an assumption about the labeling process for the test sample: the labels y; y corresponding æ; X' do not depend any other instances, that is X = II. P(y, where we use Y = . label matrix. We assume the quality predictions Y is jointly evaluated against the observed labels Y by a task utility VYY YY) and define the optimal (Bayes) prediction Y* as the one maximizing the expected task utility VETU:
E y to denote the entire
Y argmax E x (Y.Y)) =: TegmaxWerlle (Y).
(1)
YEyT
YEVT
We consider task utilities (Y, Y) that linearly decompose over labels, i.e., there exists vid such that m
(Y Y)
(g))
We allow the functions & to be non-linear themselves and different for each label j. This is large class of functions, which encompasses weighted instance-wist and macro-averagee utilities, the two groups of functions which we thoroughly analyze in the next sections.
Let us next define the binary confusion matrix Cyy. ÿ) for vector of n ground truth labels and corresponding vector ý of binary predictions:
Cly 9) = -ー (1 91) 9.)
+> (1- v.)
(3)
1. 91)
E V:ū.
By indexing from O, the entry Coo corresponds to true negatives, Co1 to false positives. to false negatives, and C11 to true positives. We define the multi-label confusion tensof(C(YY Y) = [C(g.11 D..)..., C(y.,, 9mm) being the concatenation of binary confusion matrices of all m labels.
Assuming the utility function 2 to be invariant under instance reordering, i.e., its value does not change if rows of both matrices are re- re-ordered using the same permutation, we can define & in terms of confusion matrices, instead of ground truut labels and predictions (shown in Appendixx A.I):
((Y - - X))
Σ
G (Cly.,, 0.)).
Finally, we assume that we have access to a label probability estimator (LPE) (xx that estimates the marginal probability of each label given the instance, vy(xx) (1)( ... 7m (a)) Ey ie [y). Such an LPE can be attained by fitting a model on an additional training set of n' examples (x,, y:) y: using a proper composite loss function 337 which is common approach in XMLC, e.g.. [8]
We use calligraphic letters for sets S, bold font for vectors with entries v., bold capital letters for matrices Y with entries yij. rows yi. and columns y.g. 1[[] denotes indicator of event and [s] == (L.....s) $}
'Notice that the confusion matrix can be computed either for multi-label predictions for given instance binary predictions for label j obtained on set of instances X. In the following, we focus on the latter.
3

---

Performance measures for tail labels
3.1 Instance-wise weighted utility functions
By assigning utility (or cost) to each correct/wrong prediction for each label, we can construct an instance-wise weighted utility uw: y R220 with labels y E y and predictions ÿ y as
(y. 0)
Σ f=1
2 9,)(1,)1111 - 05) + w (1 - Uş)ū, + wi ú5) w
(5)
We use who- W61 w1o+ and w/n to express the utility of true negatives, false positives, false negatives, and true positives, respectively. The corresponding task loss results from summing over all instances. By interchanging the order of summation, we can see that it is of form
1
((Y = Σ Uw (yi, Ui)
Σ coo + wor oi + wio w/ d1 = Σ (Clys, (6)
=
In other words, the instance-wise weighted utilities can be seen as linear confusion-based metrics. By choosing w/6- = w11 m and w w/o 0, the expression (5) reduces to the @k-variant of the Hamming utility. Similarly, wi = and who = win wio 0 yield precision@k.
Another example is the popular propensity-scoring approach [15]. commonly used as tail- performance metric in XMLC. Here, the weights are computed based on training data through
p.rop = = (1 + (log n' () (n' b)) wh
where n' is the number of training instances, řj is the empirical prior of label j. and parameters a and b (potentially) dataset-dependent. This form of weighting has been derived from missing-labels perspective, so its application to tail labels is not fully justified 4I.. Also, it introduces two more hyperparameters, which makes the interpretation and comparison of its values rather difficult. is not less heuristical than other approaches like power-law or logarithmic weighting, given by:
wiil ,,
log log (fty)
(8)
3.2 Macro-average of non-decomposable utilities
Macro-averaging usually concerns non non-decomposable binary utilities such as the F-measure. In this case, set up v (c, = --)((.,)) for all labels j in 2 yielding:
V(Y, Y) m
v (V))) = m Σ (C(..,
By using ph = /n/ (en + co1). this becomes macro-precision, for vire (C) = cn/(en c10) get macro-recall, and for urr, (C) (B+1)cn/((111))) 8)cn :82c10 c the macro-F-min macro-F-measure.
Another measure that promising for the evaluation of long-tailed performance coverage. is sometimes used as auxiliary measure in XMLC [ B 42 41. This metric detects for how many different labels the classifier is able make at least one correct prediction. In our framework, this achieved by using an indicator function on the true positives, vicw (C) == 1 [en 0).
4 Optimal predictions
Let us start with the observation that the label probabilities n are sufficient to make optimal predictions. With the assumption that P(Y Y X) II. P(y, we obtain (cf. Appendix A.2):
Ex // Y Y) = Σ Σ
II 1=1
T (2:)1/ + (1 n,, (1:))) v1)) v (y) 18)). (10)
J=1 (00
This equation lays out a daunting optimization task, as is requires summing over 2n summands y In case of binary classification, there exist methods to solve the problem exactly in O(n²) or in O(n²)

---

in some special cases [3]. By using semi-empirine quantities (defined below), 12 provides an approximate algorithm that runs (n)). Following this approach, we construct a semi-empirical ETU approximation. If this approximation results in a linear function of the predictions, the problem decomposes over instances and can be solved easily. Otherwise, we use an algorithm that leads to locally optimal predictions. A minor modification of this algorithm can be used for coverage.
4.1
Semi-empirical ETU approximation
Since the entries of the confusion matrix linearly dependent, it suffices combinations. More precisely, we parameterize the confusion matrix by the true positíves / 1= C11, predicted positives q Cn CD1, and ground-truth positives p c11 + C10. and use = (41,-.., (m).
three independent
(91...., (m). and (pi...., pm)) to reformulate the ETU objective:
VETU = x V CCY,, Y) Erix V (t. q. p)] = Erjx
Σ (t,
(11)
In order to compute VETU, one needs to take into account every possible combination of confusion- matrix values, and calculate the corresponding value of V, which is then averaged according to the respective probabilities. A computationally easier approach is to take the expectation over the labels first, leading to semi-empirical quantities:
:= Ey x [t], q= Txxxyl44 q, p = Ey 'p]
(12)
where o = q follows because the number of predicted positives depends only on the predictions Y This allows to define the semi-empiriie ETU risk
(Y) v (t, q. == [V = VETU
(13)
In particular, the third argument V p. is constant that does not depend predictions.
Note that, / is linear all arguments depending on the random variable then the approximation is exact, due to the lincarity of expectations. Aside from instance measures, which we showed be linear above, the approximation also exact for the more general class of functions of the form
(t, q.P) = f(()) - f4(2) + fp(1) p.
(14)
An important example is macro-precision with fi(g) q and fa fp - 0. In the general case, & ETU as a surrogate for ETU leads only to (1/v/n) error as will be shown in Theorem 5.2 while substantially simplifying the optimization process.
4.2 Linear confusion-matrte measures
We start the discussion on optimization of (3) with special case in which VETU is linear in the prediction-depender arguments t, g, that is, if
(t, q) = f((p) t fc(p)-9. 9.
(15)
i.e, both fi(p) and fp) depend on p only, and (p) can be dropped as it is constant.
Aside from instance-wise weighted utilities (cf. Appendix A.3) which linear in all arguments, this form also holds for weights dependent on the (empirical) label priors, e.g., power law weights of the form fi()) = p and ʃ4 which reduce to macro-recall for 1. one defines the weights with respect to externally determined label priors, i.e., approximations to E[yy], which are fixed and thus in- dependent of the test sample X, then the power-law metrics turn into instance-wise weighted utilities.
From (6) we know that we can reformulate the optimization problem using an mistance-wise weighted utility th with weights:
w f(p,) + f((P)), w/o = fg(p)), w/o = 0, w = 0. Hence, the optimal predictions can be derived for each instance æ E X' separately, leading to
(16)
/ argmax Eyya (w, Ø)
(17)
Plugging in the definition uw from and collecting terms, the expected loss is of the form
> m
m
Eyja (w. (y. 0)]
Eye wH10, + woon v;)0s Σ Úg (n,(() - f4(2,)) (18)
1=1
5

---

the gain of predicting label j for a given instance The optimal prediction to select the labels with the largest values (z))
where we call gy(x)) = ()(=))( + (pp))
arginax DEV,
م)(مو = select-top-k(ggz)).
(19)
Here, select-top-k(gg denotes an operation that maps vector of scores to a binary vector that contains Is only at the positions of the k largest elements of g.
4.3 General non-decomposable macro measures
Finally, we turn to the general problem for budgeted-at-k macro-measures based on non- linear V. As this can be a very hard discrete optimization problem in general, erative approach based on block-coordinate as- cent that constructs sequence of predictions, y Y with non-decreasing utility, so that end up with solution that is locally optimal.
Algorithm 1 BCA(X, k,)
I: Di select-random-ki (mm) for e [n]
2: t + Σ n(x)) @ y:
use it-
3: t n - Di. P + 1 Ei= f(æ;))
4: Usad f -00, Uhew + (t, q.P)
5: while unew > Hald + do
6: for shuffle([n]] do
--t--n @ y. q + q U.
Assume the predictions are fixed for all instances except as. where they are given by In that case, we can write the semi-empirical quantities
for j E [m]] do
9:
(1) < <0f 1 (2.)), (, +
10:
(0) (;f,,
from 12) as
9j + (1) (0)
= nr (z,)2) +
Σ nh (xx))))s)
(20)
12:
y. + select-top-kkgg
13:
с + (xx)) ) @ Un. q + 9 1.
iE(m|Ma)
14:
Uold Unew. Unew (l.
with analog expansions for q and p. Plugging into (3) leads to the following optimization:
15: return Y
T
max REVI
2/ ( (nn)( +
Σ (,,))) 1 + n Σ Des Σ M3 n,(x:)) vE(M]((0)
(21)
/E(n]\ss
As everything except 2j 10. is given, a gain vector with elements Øj (1) e (0). The optimal prediction 2" is then given by z = select-top-k(g). in a similar form as in case of linear confusion-matris measures. We get ýr++1 by replacing the ht row of Y with z², and know that V ETU VETU(YY-1) (Yr-1)= 2 EETU(Y") Then we switch to the next instance s + s + 1, and repeat this process until no more progress is made.
interpret e/S as linear function of 2j, and define
The algorithm starts by predicting ls random labels for each instance. To speed up the computations we cache two quantities, 13 and Tz. for each label:
25 = E (m:))))
7,t2= = i7 (.. Key),
(22)
1+1= = o3 + (0 o',)) 9
With this, we can compute (2 in (m) time using the following formulas:
v (1) = 2/ (z.)), 9f 1 D.y pb)
(2 02,)) of + n F'y), p3)
(23)
2 (0) w
The block coordinate ascent (BCA) procedure shown more detail in Algorithm I Obviously, the actual implementation cannot use the unknown values 17, but instead has to rely on the LPE estimates (x;). The stopping criterion for the algorithm is whether, after going over a whole set of instances, the improvement in the objective value over the previous value is lower than which ensures that the algorithm terminates for every bounded utility in (l)e). In practice, even with small e, the algorithm usually terminates after a few iterations. The time and space complexity of the single iteration are both Onm) If 3b is a linear function, corresponding to an instance- wise weighted utility (6) such as macro- recall, the algorithm recovers the optimal solution in the first iteration, stopping after the second.
In general. Algorithm requires multiple iterations. This can be computationally expensive and requires all of the data to be available at once. We thus propose a greedy algorithm that takes into account only statistics of previously seen instances while performing a single pass over the dataset, which allows for semi-online optimization. The greedy algorithm is outlined in Appendixx B.4

---

4.4 Optimization of coverage
One measure for which the ETU approximation is not exact coverage as eevv (t, q. 1 0] is nonlinear. In this case, we can do better than Algorithm 1, by reformulating V VETU for coverage as
VYtu = Eyx
Σ
1 0] = 1 m
(1-
(24)
== E=
and performing block coordinate ascent directly on this expression, as detailed Appendix B.3
5
Regret bounds
Computing optimal predictions relies on an access to the conditional marginal probabilities (æ).. In practice, however, 77x)) are unknown, and are replaced by the LPE ()))) do inference (plug-in approach). Furthermore, we replaced the ETU objective ETU with an approximation ETTU- As generally (x))) * n7x)) and V ETU * VETU. this procedure may result in sub-optimal predictions, the errors of which we would like to control.
If able control the change of the utility under small changes in its arguments, can show that the suboptimality of the plug-in predictor relative to the optimal predictor (called v--regret) decreases with increasing test size n and decreasing probability estimation error.
To this end we assume that each vi is a p-Lipschitz function, which allows us to bound the approxi- mation error.
Definition 5.1 (p-Lipschitz 131 ). A binary classification metric vi q. is said to be p-Lipschitz
(t..t. - (t',, .')l & L(p)tt - t'1 + Lg g'l + [p(p)p - p'l. for any 9. E [0, 1]. p.p' E (0, 1). 0 < < min(p, q), and 0 < t' < min(p', d'). The constants Lp)), LD),,, (p) are allowed depend on p. in contrast the standard Lipschitz functions.
(25)
As shown in Appendix C.3 most of metrics of interest satisfy p-Lipschitz assumption, including the linear confusion-matrie measures (6) with fixed weights (e.g., Hamming utility, precision), macro-recall, macro-FPr macro-F-meane F-measure, etc., with macro precisson and coverage being notable exceptions.
Theorem 5.2. Let each viS be p-Lipschitz with constants L (p), (p) (p).) For any Ý it holds:
METU (Y; X) VETU x 2/n
Σ (1((6, + (((,,) ==1
(26)
Thus, using VETU surrogate for METU leads only O(1/ error, diminishing with the test size, while substantially simplifying the optimization process.
Given decomposable metric of the form 44), let Yt be the plug-in prediction matrix optimizing the semi-empirical ETU with plugged-in in probability estimates, (Ey~n(x)) [t), q. Ey~n(( [p]).
Theorem 5.3. Let ÿ be defined as above. Under the assumptions of Theorem 5.2
VETU ; X) VETU 8 x):
B+2
m1
[[ - (xx))l,,
(27)
where = ===mm=
- -- m ; (L) + 1z the quadratic mean of the Lipschitz constants.
A similar statement, presented in Appendix C.4 can be made for the unapproximated ETU case.
Thus, the methods described in Section 4 can be used with probability estimates replacing the true marginals, and as long as the estimator is reliable, the resulting predictions will have small -rrrgrett This also justifies the plug-in approach used in the experiments in Section 7
Efficient inference
The optimization algorithms introduced so far need to obtain ())( for all labels and instances first. Then, the BCA inference is of O(n)) time and ((rm) space complexity for single iteration. This
7

---

is problematic in the setting of XMLC. where many methods aim to predict probabilities only for top labels in time sublinear in m. Fortunately, this characteristic of XMLC algorithms can be combined with the introduced algorithms to efficiently obtain an approximate solution. Instead of predicting all 77, we can predict probabilities only for top-k' labels with highest vij. where < k' < m. For all other labels we then assume fī 0. Under the natural assumption that db is non-decreasing in true positives and non-increasing in predicted positives, we can leverage the sparsity and consider labels with non-zero f, only (using sparse vectors to represent (x;)) to reduce the time and space complexity to (n'''' + k log k)) and (n((k' + k)), respectively. As in real-world datasets the number of relevant labels |/3/|| is much lower than m, and most ny (2;) are close O, with reasonably selected K, according to Theorem 5.3, we should only slightly increase the regret. A pseudocode for the sparse variant of Algorrthmm I caa be found in Appendix D.
Alternatively, we can leverage probabilistic label trees (PLTs) 16] a popular approach in XMLC
19 [50 7 to efficiently search for "interesting" labels. Originally, PLTSs find top labels with the highest 7T. In 46. an A -search algorithm has been introduced for finding h labels with highest value of gi (a=), where dj E [0, oo) is a gain assigned to label j. In Apppendii F we present more general version of this procedure that can be used to efficiently obtain an exact solution of presented BCA or Greedy algorithms for some of the metrics considered in this work.
K5 45
7 Experiments
To empirically test the introduced framework, we use popular benchmarks from the XMLC reposi- tory [6). We train the LIGHTXML [8 model (with suggested default hyper--arameters) on provided training sets to obtain vj for all test instances. We then plug these estimates into different inference strategies and report the results across the discussed measures. To run the optimization algorithm efficiently, we use K' = 100 or k = 1000 to pre-select for each instance the top k labels with the highest f as described in Section
We use the following inference strategies:
TOP-K- the optimal strategy for precision@k: selection of k labels with the highest my (default prediction strategy in many XMLC methods).
PS-K- the optimal strategy for propensity-score
precision@k: selection of k labels with the
highest wiip"'r nj. with poppoop given by the empirical model of Jain et al. [15] (Equation 7 with values a and b recommended by the authors.
Pow-K, LoG-K- the optimal strategy for power-law and log weighted instance- utilities:
selection of & labels with the highest wriipl,, fy or wo nリ- For power-law, we use 0.5. MACRO-Paar BCA. PBCA MACRO-RECM, MACRO-Fi F1 BeA. COV BCA the block coordinate ascent AAgoo
rithm I
for optimizing macro-presss macro--recision, rrcall, -F1, and coverage.
We expect a strategy suited for a given metric to obtain the best results this metric. Never- theless, this might not always be the case, as in the derivation of our algorithms, we needed to apply different types of approximation to scale them XMLC problems. We are mainly in- terested in the performance on the general non- decomposable macro measures since they seem to be well-tailored to long tails, and their opti- mization is the most challenging. The results are presented in Table 2) Notice that in almost all cases, the specialized inference strategies are indeed the best on the measure they aim to optimize and achieve substantial gains on corre- sponding metrics compared to the basic ToP-K inference. The other weighted strategies, PS-K. Pow-K, LOG-K, usually provide a much smaller improvement over ToP-K and never beat strategies designed for specific macro measures. As the reported performance depends three things: the inherent difficulty of the data, the success of the inference algorithm, and the quality of the provided
Instance. 198
TÔP K
80
PS-k
Loo-Ke
PoR-K
70-
MAcRO FlaCA
10
20
30
Macro-F F163
Figure 1: Results of an inference strategy with a mixed utility on AMAZONCAT 133K and k = The green line shows the results for different interpolations between two measures.
A code reproduce all the experiments: httpp:://githu/ http://wwww...mm//m//m//////uuua
8

---

Table 2: Results of different inference strategies on @k measures with & E {3, 103. Notation: P-precision, R- R-recall, #1--F-mmasumn Cov Coverage The green color indicates cells in which the strategy matches the metric. The best results are in bold and the second best are in italic.
Inference straleyy
Instance de1
Macro dh3
Instance 6h5
Macro 85 F1
Instance 6:10
Macro dt 1D
Cos
P
Cov
Cov
BURLEX IK,
100
Top-K
74.20
44.21
24.85
16.45
18.63
51.27
62.31
60.59
27:43
99
25.50
39.76
39.29
75.11
22.15
36,59
26,01
47.55
PS-K
41,05
30.12
23.72
25.08
40.29
60.77
59.17
29.89
28.17
44.05
38.96
14.54
21.36
38.27
25.78
49.47
30.49
25.26
25.93
58.53
57.10
31.25
28.53
13.66
20.77
50.13
Lon-K
77.03
42.30
29.04
22.10
23.76
37.99
61.51
28.47
27.26
42.32
89.12
74.89
21.60
37.49
25.83
48.61
MACRO- Pass
41.13
26.29
38.78
16.77
20.63
40.60
31.05
30.33
38.70
18.46
21.39
41.66
18.45
35,65
37.94
20.26
21.82
42,89
MACRO-Russ
41.47
26.61
30.36
25.16
24.57
44.26
18.32
37.54
28.97
31.27
27.05
49.01
29.80
57.58
22. 22.99
38.14|
25.99
52.15
MACRO-Flar
56.18
CONarA
24.00
14.03
31.46
21.30
19,05
47.19
16.40
15.95
20.86
24.53
18.81
50.09
9.31
18.05
26.99
28.28
17,41
52.84
AMAZZONCAT-L
13K, K
100
TOP-K K
83.35
63.01
25.71
11.37
13.83
33.05
68.01
79.01
33.92
31.34
29.28
52.60
41.72
89.41
24,63
51.76
26.84
58.61
38.31
+1.30
22.56
Pow- awns
66.52
50.75
38.18
46.4
39.26
67.76
56.94
68.
31.65
54.05
36.90
71.95
37.86
83.91
19.26
64.05
26.29
77.27
Lon-K
75.30
56.79
41.09
33.92
35.04
56.05
64.07
75.21
37.40
41.86
36.78
61. 14
40.66
51.005
23.09
55.85
28.91
71.37
MACRO-PP Pacs
54.97
41.61
64.27
29.22
35.76
76.18
11.53
49.66
63.81
30.43
35.99
76.75
25.32
57.33
61.84
33.06
35.08
78.17
MACRO-BR
80.77
38.93
30.37
62.91
17.53
81.84
MAtao-Flas
70.61
53.86
77.83
60:70
71.93
52.32
49.48
79.63
92:24
55.17
$1.39
CON
4.53
2.29
34,93
35.16
15.91
182.67
3.20
2.63
29:40
39.05
14.23
84.39
2.13
3.35
19.02
44.28
10.74
85.40
W1KI-31K K1
1.00
0.72
2.54
19.59
2.66
0.92
1.24
3.72
29.05
3.55
2.07
2.34
PS-K
67.95
11.89
3.89
1.47
1,93
5.47
62.65
18.07
1.21
2.14
2.56
6.51
50.16
28.20
4.64
3.62
3.61
9.01
Pow-K K o-n.
55.06
9.59
4.49
2.14
2.59
6.98
50.12
14.40
4.83
3.13
3.37
8.53
40.15
22.57
5.07
5.10
4.47
11:37
Lon-K
65.20
11.34
3.40
1.24
1,66
4.84
57.74
16.49
3.74
1.86
2.25
5.99
43.82
24.37
4.24
3,46
3.37
8.61
MACRO-Pas
5.66
2.55
3.38
30.52
9.68
13.62
9.79
2.96
10.04
MACRo-Racs
13.78
2,36
4.77
3.24
5.10
7,26
14.01
3.96
5.79
4.71
10:72
13,88
7.79
5.72
7.21
15.72
MACRO-P1A Plazs
37.32
6.52
7.81
3.15
4.10
10.42
38.98
11:24
8.30
4.14
5:08
11.88
39:31
22.28
8.18
5.11
5.78
13.00
CONER
27.00
4.63
6.24
3.18
3:41
11.04
20,80
5.88
6.42
4.60
4.18
13:23
13.95
7.78
6.23
6.88
4.81
16.39
1000
ToP-K
56,02
45.70
20.15
18.87
17.14
32.24
43.12
54.28
20.51
25.86
19.84
40.62
22:01
63.13
17.16
34.79
19.57
50.15
PS-K
54.97
45.61
23.38
22.68
20.41
57.85
42. 86
54.51
21.84
29. 1:5
21.77
45.03
27.05
63.43
16.70
37.58
19.87
53.67
Pow-K
51.81
43.94
23.75
23.67
21.13
39.36
40.55
52.72
21.87
30.03
22.18
46.21
26.09
62.26
16.48
38.17
19.85
54.38
Lou-K
54.82
45.21
21.43
20.18
34.28
42.66
54.09
26,81
20.49
41.86
63.19
17.08
35.51
$1.04
MACRO-Pes
25.19
21,81
37.69
20.18
23.44
45.0K
16.25
22.54
37,888
21.12
24.10
46.23
8.48
27.97
37.77
21.46
24.19
46.65
MArRD-Rass
43.40
39.60
25.35
27.55
23.72
46.34 30
13.58
47.
23.00
33.56
23.63
51.91
21.81
56.27
15.92
40.97
20.07
58.42
MALxo-Flas.
43.82
36.40
15.42
23.69
26.01
46.36
32.96
41.21
15,79
26,19
27.64
49.
19.32
44,17
15.55
27.45
28.15
50.67
27.31
24.55
25.92
26.76
19.46
28.06
32.13
21.08
55.40
32,09
18.45
18,08
61.15
AMAZZOX-670K.
1,000
ToP-K
41.71
24.08
10.77
9.68
9.51
14.35
37.71
35.23
14.26
15.16
13.76
20:41
25:35
46.75 74
14.83
21.56
16.20
26.85
PS-K
41.05
25.77
11.86
10.54
10.42
15.50
37.54
35.13
14.86
15.73
14.31
21.16
25.22
46.65
14.89
21.85
16.34
27.22
Pow-K Jans
40.90
11.99
10.65
15.64
37.47
35.07
14.98
15.84
14.42
21.30
46.66
14.90
16.36
27.30
Lou-K
24.00
11.34
10.10
9.98
37.09
J5.22
14.48
15.37
13.97
20.68
46.75
21.64
16.24
26.94
Macso-Pacs
33.79
19.75
17.27
18.55
12.12
17.75
27.52
26.09
21,09
14.38
15.96
21. 16
15:00
28.23
23.21
16.36
17.90
24.13
MACRO Racs
39.42
22.92
13.71
11.17
11.47
17.12
36.43
34,19
16.48
16.35
15.40
22.67
24.72
45.70
16.30
22.23
17.46
28.08
MACRO-Fl,,
37.34
21.70
16.19
10.75
12,17
17.65
31.97
30.01
20.39
15.15
16.37
22.25
18.18
31.28
22.79
17.95
18.89
25.12
CONarA
14,04
17.79
30.27
28.
15.94
14.85
22.03
37.23
28.15
marginal probabilities, the results might diverge from expectations in some cases. In Appppddix E we provide more details and conduct further experiments to investigate the impact of randomness, stopping conditions, quality of probability estimates, and shortlisting on the results. We also present similar experiments with probabilistic label trees used as an LPE.
Unfortunately, our results show that optimization of macro-measures comes with the cost of significant drop in performance on instance-wise measures. Ideally, we would like to improve the performance on tail labels without sacrificing too much of general performance. To achieve such a trade-off, we can use straight-forward interpolation of instance-wise precision-at-k, as it covered by our framework, and a selected macro-measure since the considered class of utility functions is closed under linear combinations. Such an objective can be optimized by the proposed block-coordinate algorithm without any modification. As an example, we plot in Table the results of optimizing a linear combination of instance-wise precision and the macro-Fi measure: ( (1 a Instaanc-PP YY, Y) + aV Maco-F1 (Y, Y), using different values of E [0. 1). In Appendix E.S) we provide more plots for different utilities, datasets, and values of k. All the plots show that the mistance-vs-mace
curve has a nice concave shape that dominates simple baselines. In particular, the initial significant improvement on macro-measures comes with minor drop in measurs, and only if one wants to optimize more strongly for macro-meat measures, the drop on instance-wiss measures becomes more severe.

---

8 Discussion
The advantage of the ETU framework is that one can use multiple inference strategies without re-training model. This is especially useful in cases where is not a-priori clear which performance measure should be optimized, or predictions for different purposes are needed at the same time. On the other hand, as this framework optimizes the performance directly on a given test set, it is not designed to make predictions for single instances independently. The ETU framework has mainly been studied the case of binary classification problems. We are not aware of any work that focuses on optimizing the complex performance metrics in the ETU framework for multi-label classification. One could try to generalize the results from binary classification, but the existing algorithms might not scale well to the extreme number of labels and they do not take the budget of k labels into account.
Our paper gives novel and non- non-trivial results regarding this challenging optimization problem. We have thoroughly analyzed the ETU framework for a wide class of performance metrics, derived optimal prediction rules and constructed their computationally efficient approximations with provable regret guarantees and being robust against model misspecification. Our algorithm, based on block coordinate descent, scales effortlessly to XMLC problems and obtains promising empirical results.
Overall, we identified four categories of utili- ties. that differ in the complexity of the opti- mization algorithm- -whether to use instance- wise optimization as in [neeecioon& 4.2] or the block coordinate-ascent (Algorithm 1) and the guar- antees for the result whether cemi-empirical quantities (Section 4.1) lead to an optimal so- lution, or suboptimal with error bounded by Theorem 5.2] These are given as follows and summarized in Table 3
Table 3: Four different classes of utilities
Linear in Approx.
Algorithm
1, P.P t,
No
Instance-wise
Yes
Instance-wist
t,p
No
Block-Coording
Yes
Block-Coordinate
Fully linear:
Optimal predictions for metrics that are linear in all entries of the confusion matrix, as (6). can be solved exactly in an instance-wise manner. Examples are classical metrics such instance-wise precision@k; or propensity-scone
precision@kk.
Linear in predictions: Approximately optimal predictions for metrics that are linear in the predictions as given in (15) can be obtained using instance-wise optimization, by switching from VrT to VETU. An example is macro recall@ok.
Linear in labels: If metric linear in the label variables as given in (14, then VETU = VETU. However, the resulting combinatorial optimization problem for VETU is still complex enough, and we can solve it only locally. An example is macro precision@k.
Nonlinear metrics: If none of the above apply. we have VEU + VETU and have to solve it locally using block-coordinate ascent. This is the case of macro F-measure@k; or coverage@kk.
The macro-are avcrr-e metrics budgeted at k are attractive for measuring the long-tal tail performance. Macro- Macro-averaggng treats all the labels as equally important, while the budget of k: predictions requires the prediction algorithm to choose the labels "wisely." We believe that this approach substantially better than the one based on propensity-scores metrics. is important to make the distinction between a metric used as a surrogate for training or inference, and its use as a performance metric in itself. While the former might be well justified for many metries, the latter not necessarily as metric might not have a clear interpretation of the calculated numbers.
Finally, the proposed framework is plug-in approach that works on estimates of marginal probabilities and can be seamlessly applied to many existing otate-of-thheart XMLC algorithms that are able to output such predictions, including XR-Transforma [5T), CascadeXMML [20], and algorithmic approaches for dealing with missing labels [40 36). can also be combined with recently proposed methods that try to improve predictive performance on the tail labels by, e.g..
leveraging labels features to estimate labels-correlations [2 39 9 52 or to do data augmentation
and generate new training points for tail labels 43 218
10

---

Acknowledgments
part of computational experiments for this paper had been performed in Poznan Supercomputing and Networking Center. We want to acknowledge the support of Academy of Finland via grants 347707 and 348215, and also thank Mohammadreza Qaraei for providing pre-generated LPEs, n). obtained by LightXML using computational resources of CSC - IT Center for Science, Finland.
References
[1] Rahul Agrawal, Archit Gupta, Yashoteja Prabhu, and Manik Varma. Multi-label learning with millions of labels: Recommending advertiser bid phrases for web pages. In 22nd International World Wide Web Conference, WWW 11, Rio de Janeiro, Brazil, May 1 13-17, 2013, pages 13-24, International World Wide Web Conferences Steering Committee / ACM, 2013.
[2] Rohit Babbar and Bernhard Schölkopf. Dismec: Distributed sparse machines for extreme multi-label classification. In Proceedings of the tenth ACM international conference web search and data mining, pages 721-729, 2017.
[3] Rohit Babbar and Bernhard Schölkopf. Data scarcity, robustness and extreme multi-label classification. Machine Learning, (288)))332-135111 2019.
[4] Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, (314473)138-1555 2006.
[5] Alina Beygelzimer, John Langford, Yury Lifshits, Gregory B. Sorkin, and Alexander L. Strehl. Conditional probability tree estimation analysis and algorithms. In UAI 2009, Proceedings of the Twenty-Fifth Conference Uncertainty in Artificial Intelligence, Montreal, QC. Canada, June 18-21, 2009, pages 51-58. AUAI Press, 2009.
[6] Kush. Bhatia, Kunal. Dahiya, Himanshu Jain, Anshul Mittal, Yashoteja Prabhu, and Manik Varma. The extreme classification repository: Multi-label datasets and code, 2016. URL http::/mastt :ttp::/manikvarme. org/ brg//dwwn downloads XC/ KMteeposRResssrrry..o.o.oooooote html
[7] Wei- Wei-Cheng Chang, Hsiang-Fu Fu Yu, Kai Zhong, Yiming Yang, and Inderjit S. Dhillon. Taming pretrained transformers for extreme multi-label text classification. In Rajesh Gupta, Yan Liu, Jiliang Tang, and B. Aditya Prakash, editors, KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020, pages 3163-3171, ACM, 2020.
[8] Eli Chien, Jiong Zhang, Cho-Jui Hsich, Jyun Yu Jiang, Wei-Cheng Chang, Olgica Milenkovic, and Hsiang-Fu Yu. Pina: Leveraging side information in extreme multi-label classification via predicted instance neighborhood aggregation. arXiv preprint arXiv:2305. / /2349, 2023.
[9] Kunal Dahiya, Ananye Agarwal, Deepak Saini, Gururaj. Jian Jiao, Amit Singh, Sumeet Agarwal, Purushottam Kar. and Manik Varma. Siamesexml: Siamese networks meet extreme classifiers with 100m labels. In International Conference on Machine Learning, pages 2330- 2340. PMLR, 2021.
[10] Ofer Dekel and Ohad Shamir. Multiclas--ulttlabell classification with more classes than examples. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2010, Chia Laguna Resort, Sardinia, Italy, May 13-15, 2010, volume of JMLR Proceedings, pages 137-144. JMLR.org, 2010.
[11] Krzysztof Dembczynski, Arkadiusz Jachnik, Wojciech Kotlowski, Willem Waegeman, and Eyke Hüileermeier. Optimizing the f-measure in multi-label classification: Plug-in rule approach versus structured loss minimization. In International conference on machine learning, pages 1130-1138, PMLR, 2013.
[12] Krzysztof Dembezynski, Wojciech Kotlowski, Oluwasanmi Koyejo, and Nagarajan Natarajan. Consistency analysis for binary classification revisited. In Proceedings of the 34th International Conference on Machine Learning, ICMI. 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 961-969, PMLR, 2017.

---

[13] Krzysziof Dembezyúski, Wojciech Kottowski, Oluwasanmi Koyejo, and Nagarajan Natarajan. Consistency analysis for binary classification revisited. In Proceedings of the 34th International Conference on Machine Learning (ICMI. 2017), volume 70 of Proceedings of Machine Learning Research, pages 961-969. PMLR, 2017.
[14] Jia Deng. Sanjeev Satheesh, Alexander C. Berg, and Fei-Fei Li. Fast and balanced: Efficient label tree learning for large scale object recogmition. In Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 201 Proceedings of a meeting held 12-14 December 2011, Granada, Spain., pages 567-575, 2011.
[15] Himanshu Jain, Yashoteja Prabhu, and Manik Varma. Extreme multi-label loss functions for recommendation, tagging, ranking and other missing label applications. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 16, page
Association for Computing Machinery, 2016. ISBN 9781450342322.
[16] Kalina Jasinska, Krzysztof Dembezynski, Róbert Busa-Fekete, Karlson Pfannschmidt, Timo Klerx, and Eyke Hüllermeier. Extreme F-measure maximization using sparse probability estimates. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 1435 1355-1444. 1444. JMLR. 2016.
[17] Kalina Jasinska-Kotaa Marek Wydmuch, Krzysztof Dembezyúski, Mikhail Kuznetsov, and Róbert Busa-Fekete. Probabilistic label trees for extreme multi-label classification. CoRR, abs/2009.1 1218, 2020.
[18] Ting Jiang. Deqing Wang, Leilei Sun, Huayi Yang. Zhengyang Zhao, and Fuzhen Zhuang. Lightxml: Transformer with dynamic negative sampling for gegh-performance extreme multi- label text classification. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 35, pages 7987-7994, 2021.
[19] Sujay Khandagale, Han Xiao, and Rohit Babbar. Bonsai: diverse and shallow trees for extreme multi-label classification. Machine Learning, 109(11))2099-21 2119, 2020.
[20] Siddhant Kharbanda, Atmadeep Banerjee, Erik Schultheis, and Rohit Babbar. Cascadexml: Rethinking transformers for end-to-end multi-resolution training in extreme multi-label classifi- cation. Advances in Neural Information Processing Systems, 35:2074-2087, 2022.
[21] Siddhant Kharbanda, Devaansh Gupta, Erik Schultheis, Atmadeep Banerjee, Vikas Verma, and Rohit Babbar. Gandalf: Data augmentation is all you need for extreme classification. 2022.
[22] Wojeiech Kotlowski and Krzysztof Dembezyúski. Surrogate regret bounds for generalized classification performance metrics. Machine Learning, 10:549-572, 2017.
[23] Oluwasanmi Koyejo, Nagarajan Natarajan, Pradeep Ravikumar, and Inderjit S. Dhillon. Con- sistent multilabel classification. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 3321-3329, 2015.
[24] Siu Kwan Lam, Antoine Pitrou, and Stanley Seibert. Numba: A llvm-based python jit compiler. In Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC, pages 1-6, 2015.
[25] David D. Lewis. Evaluating and optimizing autonomous text classification systems. In SI- GIR '95, Proceedings of the 18th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Seattle, Washington, USA. July 9-13, 1995 (Special Issue of the SIGIR Forum), pages 246-254, ACM Press, 1995.
[26) Yu-Jen Lin and Chih-Jen Lin. On the thresholding strategy for infrequent labels in multi-label classification. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, CIKM '23, page 1441 1441-1450, New York, NY, USA, 2023. A Association for Computing Machinery.
12

---

[27] Julian McAuley, Rahul Pandey, and Jure Leskovec. Inferring networks of substitutable and complementary products. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 785-794, 2015.
[28] Tharun Kumar Reddy Medini, Qixuan Huang. Yiqiu Wang, Vijai Mohan, and Anshumali Shrivastava. Extreme classification in log memory using count-min sketch: A case study of amazon search with 50m products. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 13265-13275. Curran Associates, Inc., 2019.
[29] Anshul Mittal, Noveen Sachdeva, Sheshansh Agrawal, Sumeet Agarwal, Purushottam Kar, and Manik Varma. Felare: Extreme classification with label graph correlations. In Proceedings of the Web Conference 2021, pages 3721-3732, 2021.
[30] Harikrishna Narasimhan, Harish Ramaswamy, Aadirupa Saha, and Shivani Agarwal. Consistent multiclass algorithms for complex performance measures. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 2398-2407, Lille, France, 07 2015. PMLR.
[31] Harikrishna Narasimhan, Harish G. Ramaswamy, Shiv Kumar Tavker, Drona Khurana, Praneeth Netrapalli, and Shivani Agarwal. Consistent multiclass algorithms for complex metries and constraints, 2022. bttppss:s///riiii
2aabs//2110 09695
[32] Nagarajan Natarajan, Oluwasanmi Koyejo, Pradeep Ravikumar, and Inderjit Dhillon. Optimal classification with multivariate losses. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1530-1538, New York, New York, USA, 20-22 Jun 2016. PMLR.
[33] Yashoteja Prabhu and Manik Varma. Fastxml: a fast, accurate and stable tree-classifier for extreme multi-label learning. In The 20th ACM SIGKDD International Conference on Knowl- edge Discovery and Data Mining, KDD '14, New York, NY, USA August 24 27, 2014, pages 263-272. ACM, 2014.
[34] Yashoteja Prabhu, Anil Kag. Shilpa Gopinath, Kunal Dahiya, Shrutendra Harsola, Rahul Agrawal, and Manik Varma. Extreme multi-label learning with label features for warm-start tagging, ranking & recommendation. In Proceedings of the Eleventh ACM International Conference Web Search and Data Mining, pages 141-449, 2018
[35] Yashoteja Prabhu, Anil Kag, Shrutendra Harsola, Rahul Agrawal, and Manik Varma. Parabel: Partitioned label trees for extreme classification with application to dynamic search advertising. In Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, Lyon, France, April 23-27, 2018, pages 993-1002. ACM, 2018
[36] Mohammadreza Qaraei, Erik Schultheis, Priyanshu Gupta, and Rohit Babbar. Convex surrogates for unbiased loss functions in extreme classification with missing labels. In Proceedings of The Web Conference 2021, www '21, New York, NY, USA, 2021, Association for Computing Machinery. 1011100.114574442881133333 345103 URL http:: //doi. org/ 10. 1145/3442381
3450139
[37] Mark Reid and Robert Williamson. Convexity of proper composite binary losses. In Yee Whye Teh and Mike Titterington, editors, Proceedings of the Thirteenth International Conference on A Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pages 637-644. Chia Laguna Resort, Sardinia. Italy, 13-15 May 2010. PMLR. URL https //proceedings. mlr prress//9/reid10a.ntte html
[38] Stuart J. Russell and Peter Norvig, Artificial Intelligence: modern approach. Pearson, edition, 2009.
[39] Deepak Saini, Arnay Kumar Jain, Kushal Dave, Jian Jiao, Amit Singh, Ruofei Zhang, and Manik Varma. Galaxe: Graph neural networks with labelwise attention for extreme classification. In Proceedings of the Web Conference 2021, pages 3733-3744, 2021.
13

---

[40] Yuta Saito, Suguru Yaginuma. Yuta Nishino, Hayato Sakata, and Kazuhide Nakata. Unbiased recommender learning from cosssinng-otat-raaae
implicit feedback. In Proceedings of the 13th International Conference Web Search and Data Mining, WSDDM '20, page 501-509, New York, NY. USA, 2020. Association for Computing Machinery. ISBN 978 150368222. 111001145/333311113777777 URL htRlhttps:://ooi org/ 10. 111111113333311 3371783
[41] Erik Schultheis, Marek Wydmuch, Rohit Babbar, and Krzysztof Dembezynski. On missing labels. long-tails and propensities in extreme multi-label classification. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1547-1557, 2022.
[42] Tong Wei and Yu-Feng Li. Does tail label help for large-scale multi-label learning? IEEE Transactions Neural Networks and Learning Systems, 31(7):2315 2324, 2020.
[43] Tong Wei, Wei Tu, Yu-Feng Li, and Guo-Ping Yang. Towards robust prediction on tail labels. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1812-1820, 2021.
[44] Jason Weston, Ameesh Makadia, and Hector Yee. Label partitioning for sublinear ranking, In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013, volume 28 of JMLR Workshop and Conference Proceedings, pages 181-189. JMLR. org, 2013.
[45] Marek Wydmuch, Kalina Jasinska, Mikhail Kuznetsov, Róbert Busa-Fekete, and Krzysztof Dembczynski. A 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. Gamett, editors, Advances in Neural Information Processing Systems 31, pages 6355-6366. Curran Associates, Inc., 2018.
[46] Marek Wydmuch, Kalina Disinska-Kobus Rohit Babbar, and Krzysztof Dembezynski. Propensity-scon scoree probabilistic label trees. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '21, page 2252-2256, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781 7781450380379.
[47] Yiming Yang. A study of thresholding strategies for text categorization. In Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '01, page 137-145, New York, NY, USA, 2001. Association for Computing Machinery. ISBN 1581 133316.
[48] Hui Ye, Zhiyu Chen, Da- Ha- Wang, and Brian Davison. Pretrained generalized autoregressive model with adaptive probabilistic label clusters for extreme multi-labe text classification. In International Conference on Machine Learning, pages 10809-10819, PMLR, 2020.
[49] Nan Ye, Kian Ming Adam Chai, Wee Sun Lee, and Hai Leong Chieu. Optimizing F-measure: tale of two approaches. In Proceedings of the 29th International Conference on Machine Learning, ICML 2012, Edinburgh, Scotland, UK, June 26 - July 1, 2012. icml.cc/ / Omnipress, 2012.
[50] Ronghui You, Zihan Zhang, Ziye Wang, Suyang Dai, Hiroshi Mamitsuka, and Shanfeng Zhu. Attentionxml: Label tree- based attention-awar deep model for high-performance extreme multi-label text classification. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Bin Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 1812-5822. Curran Associates, Inc., 2019.
[51] Jiong Zhang, Wei-Cheng Chang, Hsiang-Fu Yu, and Inderjit Dhillon. Fast multi-resolution trans- former fine-tuning for extreme multi-label text classification. Advances in Neural Information Processing Systems, 34:7267-7280, 2021.
[52] Ruohong Zhang, Yau-Shian Wang, Yiming Yang, Donghan Yu, Tom Vu, and Likun Lei. Long- tailed extreme lubti-label text classification with generated pseudo label descriptions. arXiv preprint arXiv:2204.0095 00958, 2022.
[53] Jingwei Zhuo, Ziru Xu, Wei Dai, Han Zhu, Han Li, Jian Xu, and Kun Gai. Learning optimal tree models under beam search. In Proceedings of the 37th International Conference on Machine Learning, Vienna, Austria, 2020. PMLR.
14

---

A Order-invariant linearly decomposable task metrics
In this section, we provide a closer look at the family Lor of order-invariant task utilities that can be decomposed into a sum of label-specific functions as laid out in [Section 2 the main paper.
We first formalize the notion of instance-order invariance, and then show that this implies the possibility of reformulating the utility function based on the confusion matrix. We further prove that is sufficient to know the marginal label probabilities 17x)) for each instance æ in order to evaluate any utility vi Coi in the TTU-framework.
A.1 Order-invariant task utilities as confusion- matrix metrics
We show in Theorem A.3 that any utility function (YY Y) that is invariant under instance reordering can be defined in terms of confusion matrices. In this way, we justify our choice in the main paper to focus on losses of the form given in (4).
More precisely, let a E ((n) be permutation of rows, that is, for Y = "un....,yn. ynl", we define
oY= (1) ................................ V=(m)]" I" Then we can make the following definition:
Definition A.1 (Invariant under instance reordering). Let n, m E N and V: {0. 1 x {0, 1) )
R be a function of discrete labels and predictions. If vp remains unchanged for every permutation of rows a E G(n), i.e.,
YY - ,Y))
(28)
then we call v function that invariant under instance reordering. We denote the set of instance- order-invariant losses with m labels as
10"m Im V 13.1) mm {0, 13 mm
R: v/ is invariant under instance reordering]
(29)
We further define the set of all possible confusion matrices with instances as
C(n) = {C: nC E IN2x2 || = 1}}
(30)
where IN is the set of natural numbers including O. Now we are ready to provide a lemma for the binary case:
Lemma A.2. Let so: 10, 10, - R be a binary loss function that is invariant under instances reordering. Then there exists a function Φ: C(n) - It such that v = o C.
Proof. We provide an explicit construction of v.. To that end, let E E C(n) be one such confusion matrix, then there exists (y. 9) E 13, 10, given by
(v.9) = (1, (1, (0, 1),...., (0, (1,0), (1.0),
(0,0)
(31)
xn-
xn
xn
X
Define e such that ((C) (y 9)
Now, let (y', ÿ¹) E {0, 1)" x {0, 13" an arbitrary label-prediction combination, with Cly' 0') C. Then there exists a permutation such that aу² y and oÿji ÿ. By the invariance assumption, it holds that
('y' Φ¹) ('ay', agg) ( -(č)= (C('' .))).
(32)
As the original C e C(n) was arbitrary, the statement shown.
We can now extend this lemma to show the equivalence of two definitions of the task losses considered in this paper:
Theorem A.3 (Equivalence of order- inder-invariance and confusion-matrix losses). Let n, m. E IN, and
y (0, 1] m. Define the set of instance-order invariant, label-averagee losses as
m 4 (y.j. 9ー)
Lot = { E Im :Y,
(33)
15

---

and the set of confusion-matrix based, label-averaged losses as LCM == { C(n) - R s.t. C Σ Ed(C')
(34)
Then these two descriptions are equivalent, in the sense that
Lor f C: & LcM}.
(35)
that is, every instance-order invariant loss can be written as a confusion-matrix loss, and every confusion-men maarrix loss leads to an instance-order invariant loss.
Proof. As calculating the confusion matrix is in itself an operation that is invarant under instance reordering, each 4 o C clearly instance-order invariant.
On the other hand, let (Y, Y) = ンラ= v (y F.)). then by Lemma A.2 there exist ,',..., 6th such that
(y の.)) d' (I 9())).
(36)
Summing up the individual &i gives & the correct form.
A.2 Sufficiency of label probability estimates
If & E Lor is an instance-order invariant decomposable task utility, then its ETU risk is a function of the predictions Y and the marginal label probabilities n)x) as given by (TO). This means that is not required to estimate the m values of the full joint probability distribution IP x)).
Lemma A.4. Let E Loi be an instance-order invariant decomposable task utility, and assume that the labels of different instances are independent, i.e., that (Y III Py (.;). Then we have
Ex W = Σ
Σ
(II
n;(2;)u/ + (1 (1-n)(2:)))) (x(2))) v/)) (0 D.)) (37)
j=1
y' g' i=1
Proof.
m Ey 8] }=]= Σ
Ey J (2. 9.)]
Σ
Σ
Ply = y |XW'' v.))
j=1
5=1 D' 1
II
P\Y 1/2 æ:1) (3'
y' 2
m
Σ Σ
[I (2:)v + (1 - -n, (2x))) v1)) (z
(38)
==1 y' 1),
A.3 Representation change from the instance-wise form to the cost-matrix form
we start with the linear metric given in the instance-wist form according to (5). the corresponding representation according to (15) may be shifted by a constant value, and can be derived through the following:
111 + Co1 C10 + Woo C11W11 Wo1 + (p t)w + (1 - p Co1 Woo
= t (W11 W1o) + co1 (Wor Woo) + pw1o + (1 - p)
(W11 Who wol + Woo) q (Wor - woo + const.
(39)
Thus, get fi(p) Wi1 Wio Wol + woo and (p) wol Woo-
16

---

B Block Coordinate Ascent
In this section, we provide additional analysis and variations of the block coordinate ascent algorithm. We first give an intuition into the gain-based selection of labels performed by the algorithm in the case of macro-preed peero-precision. Then, we will illustrate how, for metrics that are linear in the prediction argument as per (15), the algorithm will recover the closed-form solution given in (I9). Afterwards, we present an alternative formulation specifically for coverage, and conclude with greedy versions of the BCA algorithm.
B.1 Example: Macro-Precision
As an example, consider the optimization of macro-preeision. In this case, vi (t, q, = =t/q. Plugging into the gain formula gives
+ (xx) 9j
t
(t + (z,())) 2a (a) + +1) o' (q' + +1
q (x. - q (q' + 1)
(40)
o' +1
This term is positive only if t/ /4" < (rr,), i.e., predicting the label has positive impact on the overall utility if its chance of being relevant, (2.)). is larger than the current estimate of precision for label j. Of course, the "at-k" constraint means that, for given instance, it may not be possible to select all labels with positive gain, or necessary to select some labels with negative gain to fulfill the constraint.
B.2 Global optimality for linear metrics
If dad is a linear function, i.e., it corresponds to an instance- wise measure as (6. the gain g, defined through lines 9-11 in Algorithm 1 becomes
/ (t + (x.). + 1,p) w (t, q. - (t+ = = f((P),
+ (g+ 1
(41)
because the influence of the other instances cancels out. This exactly reproduces the gain formula from Section 4.2, which means that for each instance, the block coordinate-ascent algorithm will select the globally (approximately) optimal decision on the first pass. If the metric is fully linear, this will be the Bayes-optimal decision, otherwise, it approximately optimal in the sense Theorem 5.2] In both cases, the algorithm will perform a second pass over the entire dataset in order to check the stopping criterion. This second pass will leave all predictions unchanged.
B.3 The ETU approach for coverage
In this section, we derive the ETU risk presented initially in Section 4.4] Then, we present a block coordinate ascent algorithm for optimizing it. The step-by-step derivation of (24) is given below:
EETU (:: X)=
Fy x W cav (t(Y,
Y), qY Y). PYY, Y))
Exix
1
[t,
0]
Exix Σ (1 1[1 01)
m
m
m i
Exix
(1-
Ey x
1- -IIII F=
(42)
m
Because we assume labels for one instance to be independent on all other instances, i.e., P(Y X) IF Pp æ.), we obtain:
m
12
17
V V Y: X) =1
Σ
Ply.
1xx)))
m 1=1
==
=1 m 1=
(1 ny (x)))()))
(43)
17

---

Based on this result we can construct block coordinate ascent procedure which, for predictions being fixed for all instances except x,, optimizes the following problem:
max
cav (2z)
(1 (1 (z.)))=
II (1 ()(
(44)
LEVE
j=1
Analogously to Section 4.3 everything except Zy E {0, is given and we can define a gain
Algorithm 2 BCA for coverage X, 17, k7,,c))
1: 9. f sclect-raddom-k(() m) for all i E [n]
vector with elements 9j Viloy (1) V (0). Again the optimal prediction 2" is then given by z² select-top-k(g) and we get y by replacing the Thh row of Y with zz. Then we switch to the next instance + 8+ I, and repeat this process until no more progress made.
2: + II- (m,) @ (.)
3: Vold t -0, Uee t (m 23 fz)
while Unew Uold + c do
5:
for s E ([uf do
6:
f + f о (1 nxx o ú.)
7:
g f (xx)) y. f- select-top-k(g)
Notice that IT==1 (1 ()x)))) corresponds the probability of label j being irrelevant for all instances it was selected for. We denote this value as f and use it to speed up computations in each iteration of the algorithm:
9:
f - f (1 n)x ) ① y.)
10:
Mold <- Unew. Nhew t - (m 1 Σ/= 13)
11:
return Y
(2,)) ff -- (20
II= (1-n((x.)0))
(45)
We can then compute the gain vector using the following formula:
1 1 - (20.) (2
(1
11 (3(3rs))²
9j
(46)
(2 )
This block coordinate ascent procedure for coverage is presented as Algorithm
B.4 Greedy version of block coordinate-ascent
The inference strategy presented in Algorithm I requires multiple passes over the entire data. This might be computationally expensive and requires the whole dataset to be available at once. We, thus, propose a greedy version of the algorithm, that performs just single pass over the dataset and makes decisions for each instance by taking into account only statistics previously seen instances instead of all other instances in the dataset. This allows to apply this algorithm to the semi-online setting, where the algorithm observes and predicts for instances one by one, but does not receive immediate feedback for its decisions, in contrast to the usual online learning setting. The procedure is outlined as Algorithm 3] and its greedy variant as Algorithm 4 The results of this algorithm in comparison to the BCA approach are given later in Appendix E
Algorithm 3 Greedy (X, k)
Algorithm Greedy for coverage (X, n,, k)
I: t 0, 1-gg000 0,
1: f [-) 1
2: for E [n] do
2: for E [ni do
p p+ 1 (z.)))
3: g + fo (1,)))
4: for j E [m] do
4: yi select top-k(g)
5:
(1) < 4 +
5: f fo (1 (.)) 3 (.)
6:
(0)0) + (t, (,),
6: return
7:
Ø1 (1)-)))
8:
ÿi + top-k(g))))
9:
+ it (2x) C
10:
q q 1 g.
11:
return
18

---

C Detailed Regret Analysis
In this section, we discuss the p-Lipschitzness condition of the metries of interest, and prove Theorem Theormm 5.3
Theorem
C.1 p-Lipschitz utility functions
First, recall the definition from the main paper:
Definition 5.1 (p-Lipschitz [33). A binary classification metric (0(4, q, is said to be p-Lipschitz
g.p. wit', ,')l S L(p))t - t'I
(p)2) L,))l 9'1 Lp(p)lp p'l,
(25)
for any q. E [0, p.p'' E (0, 1). 0 < < min(p, q), and 0 - t' < min(p', d'). The constants (p)) (p) are allowed to depend on in contrast to the standard Lipschitz functions.
The rationale behind this definition is that while need to control the change in value of the metric under small changes in its arguments, standard definition of Lipschitzness (with global constant) would not be satisfied by many pop- ular metrics. For the same reason, only re- quire stability for non-trivial problems, that is, in cases where the rate of positives is neither zero nor one.
Table 4: Examples of p-Lipschitz metrics. We use tp. fp, fi, and tn to denote true positives, false positives, false negatives, and true negatives.
Metric
Definition
at q.p)
Accuracy
tp + tn
I + 2t
Recall
Ip+tin Ip/2
Bal. Acc.
tn/2
(+p(1-9-P)
Relaxing the definition to allow the constants vary as a function of p suffices to prove our stability results well as regret bounds, while it satisfied by most of the metrics interest, as shown below. The notable exception not present in Table 4 is the precision metric, which is not p- Lipschiit due to its behavior for 9 - O.
tp++fn tn+ffp
2p(1-p)
Fø
(1+ jep
(1+.99
5-pto
Jaccard
tp tp-t-p-i +f
p+g-2t
G-Mean
tp-tn
kl-q--pth
(ta+la
p(1-p)
AUC
fp-fn (fp+tfn(((D
(p-))p-1)
Lemma C.1. The linear confusion-matrix mea-
p(1-p)
sures defined by (6):
V YY
woo + wo wooco + w(1c(1)
(47)
with fixed coefficient matrices {W') decomposable functions with p-Lipschitz components.
Proof. The metric can be rewritten decomposable form v Eg v3 where each zid in the (L, q. paraaapaarannnnnnitaiionnnn has the following form:
(t. (t, q. p) .
f - Pp.
(48)
where R, C. are some combinations of the coefficient matrices {W"} Being a linear function of q, vid is Lipschitz.
Lemma C.2 (p-Lippchitzzness of common utilities 13 All metrics in Table 4 are p-Lipschitz
Proof. Here, we only prove the lemma for recall, which has not been covered by Proposition I of Dembezyński et al. [13].
(t(,q.p)) o d. =
1'
l'
p'
p
//
p
p
1
t!
1
<
||
e'
+
1p
p'I
(49)
P
1
P
=L(vx)
11
=Lp(p)
19

---

C.2 Stability of the semi-ETU approximation
We are now ready to prove that when the metric of interest has p-Lipschitz components, the semi-ETU approximation EeUu presented in Secciio 4.1 remains close to the true objective VETU. For the sake of convenience, let us recall the definition of the ETU objective:
m Σ
ETU Y: x)= Erxx Y)
[ (t)
(50)
well as its approximation:
U ETU YY: :
Σ v [Eyix Exx
(51)
We prove the following result:
Theorem 5.2. Let each vi be L-Lisschitz with constants Li (p), Lg(p), (p). For any Y it holds:
1 2/7 (1(6,
:E) - V ETO Y; xx) -
(26)
Proof. For the sake of the analysis, denote the Lipschitz constants as L = (0,) and L Lz(0,)
Using definitions (50) and (51) and applying Jensen's 's inequality, we have
VETU (Y; VETU (Ý: x)| =
Fx x 1 (t., v/' (tg(t (tg.
j=1
m
E Ex x (ty.g.t.)))))) - (3))
(52)
f=1
We now bound each term in the sum by (Lf + (2)((2/))) which will prove the theorem.
For each j E [m]. using p-Lipschitzness of 1b we have:
| (1z.0.Pp)) - v/² (5,,0),8,)) = | (E, P5) - (1,, (i,,))
< Liit Ey] + Lglp, pyl.
(53)
Taking expectation on both sides gives:
Ex,x [] 11 (Lg, (i. w/2 (Gg. 13)1] < Tif Exix - [1]] + T Fx P511
I Eyix V(1)- - Eyix V(D:
$ L Erixl(t - 21 + 1/4 Ey x [1D; - p,)31
(54)
where the last inequality follows from Jensen's inequality applied to concave function + Vx. Using the fact that i, Exixl [ty] and p, Ey xx [py]. we have
1
Ey x [(t }²} Vary <
(55)
4n
as 1 = n n- En Vogii is an average of n Bernoulli i.i.d. random variables Vizūij. each having variance at most 1: and using the same argument, Fx [(p - -,,) I L This gives
L + L
Ey,x [1 (E,, (tg,
(56)
2/7
and finishes the proof.
C,3 Regret of semi-ETU under model misspecification
In this section, we quantify the influence of the estimation error of marginal probabilities, prov- ing Theorem 5.3
20

---

Notation To emphasize the dependence of ETTU on the label probability estimates, in this section we will write
VETU (Y; X)
Fyy Pix) (x)
(
= ETUU (Y; m):
(57)
This notation is well-defined, as we have shown in Appendix A.2 that in fact, the dependence on X is mediated only through the marginal label probabilities ny (X) (v7(2))) -.... ( (2+)), and abbreviate r7 x) as Similarly, we will write
(n) Fy n (x)
(x) Myy. U-53]
75 (2:)(
(n) (x) =n -n-1 Σ My (2:))
(58)
i=1
Note that q is independent of n. This allows us to write the semi-ETT objective as
YY (
((t.q.p)
(59)
where we dropped the dependence of t and p on as clear from the context. The optimal (Bayes) predictor Y the one which maximizes the expected utility with regard the true label probabilities. In the notation of this chapter, ( reads
Y argmax (Y:n).
(60)
YEYT
Unfortunately, the learning algorithm does not know the true label marginals (X),, but has only access to the estimates (X) = (f(x.),.... (..,) for the considered set of instances. The
algorithm computes its predictions Y i by using the estimates in place of the true marginals. Thus, can only generate
r argmax EY
(61)
YE
We make the same definitions also for the semi-empirical ETU optimization, leading to
Y argmax u (Y
and Yt
argmax & (Y; (Y:
(62)
YE
Ye
Regret for semi-ETU approximation First, we show that for metrics with p-Lipschitz components, the & W-regret of the resulting semi-ETU predictor (62). which is the suboptimality of Y (with respect Y**) in terms of V ETU, is well-controlled and upuer-d by the estimation error of the marginals. As the resulting expression is somewhat unwieldy, we then apply some further bounding arrive at the much simpler result stated in the main paper in Theorem 5.3
Lemma C.3 (Misspecification for semi-ETU approximation). Let & E Loi be instance orrdrr invariant linearly decomposable loss function that is p- p-Liscchitz and Y an arbitrary set of predictions. Then, the difference of the semi-empirical ETU risk when using two different versions of the marginals, and vy,, is bounded by the difference 'f' through
Veru (Y nn Σ
+ (1))
(m, ny (xx1) (63)
Proof. Plugging in the definitions, we have
NETU (Y;;) VETUOY (Y; =mml= Σ s (f Σ
3 ((()))))
<
Σ w (((m)) (F())
< ( - +/ -f(m)
(64)
1=1
where the last line used the definition of p-L.ipschitzness.
21

---

The terms under the sum can be bounded by the estimation error of ny':
(1)()) - 1(001= Σ (n)())(()))))) {
Σ (m)()c)) - -11 (2;()
S n
1=1
(p,(n) - (5(0 = Σ (1)(2x)) m7 (a(2i:))
S Σ
My (x;) - -75 ()'(1)))>
(65)
1=1
where in the first line used Dig (0,1).
Lemma C.4 (Regret bound for semi-ETU approximation). Let vp Loi be an instance-order invariant linearly decomposable loss function that is p-Lipschitz. Then we have
VTTU ;x;X) X) VTTU -VTTU(PY;; (Yt;)) S 1
==1
+ (T)(, (1)
Σ
(n5(2:)) - (2,(2))) (66)
j=l
Proof. Using the optimality of Ýt and supremum bound, get
Vru ( n) ETTU (Y!:n) = v VY ; - 1 VeuU (Y:; n))
VETU( Y ; VELU (Y:;)) + VETU (Y n)) Eru (Y!:n)
cTU (Y;
.n) ;;:)
VETU (Y* r n))
(67)
VETU (Yt; n) VETU (Ytu()))))
S sup / M (Y:)();n) V (Y;
(68)
We then use Theorem 5.2 and Lemma C.3 to bound
v ETTU Y: n) VETU (Eru(Y;;)
VVETUU y;n) ;n) Verul Y; :)) VETU (Y: n) VETU ;n)l
< V Y;n) Verul (Y; + ViETU( ;n) - VETU( n)]
m
m Σ
[2 + (T,),))
n Σ
S n
Σ (1)( + +1(b)))++(()))))))))))))))))))))
(a;))) ,,)2))) (69)
n
where we use the shorthand ú; = (n)
At the cost of having less strict bound, we can simplify this to Theorem 5.3. Let Y be defined as above. Under the assumptions of Theorem 5.2
VELU VYTT((";;)) VETU (81 (x1;))=
B+2
B
B
[[ - (xx))l2,
(27)
Vn
where B = 10mmmmm1pmmm (1 + [2(r)))2 is the quadratic mean of the Lipschitz constants.
/m- (T)
22

---

Proof. Using Seuchy-Schwartz, we can bound
m
(n) (n))
(n(())) - (2))))
n
==1
S
(L())(())) + [g(p)(n)))) +1(p(()))))
(a;) (x;))
(1(((()) + (n)))
[I((a:)) (0x))
m
(mx))) (>x
(70)
For the other term, we can use the inequality between arithmetic and quadratic mean, so that
m
m
Σ + m
+466 mBB
(71)
==1
C.4 Regret for non-approximated ETU
We can formulate the equivalent of Lemma C.4 also for the maximizer of the true empirical ETU risk, Yt:
Lemma C.S (Regret bound for ETU maximization). Let v E Loi be an instance-order invariant linearly decomposable loss function that p-Lipschitz. Then we have
VETU(Y" ; - (8I; <
+
Vn
j=1
(r) + (n))
(n,(2;) - )))()x))) (72)
n
Proof. Following the same line of argument for Lemma C.4
we get
Vnn (Y* 1)) VrrU ( n)
ETU Y " 17) VE (
+ VETU (+; - V (Y:; :)
Viru (\:; VeTU (Ýt:))
v
- VETU(Y" (Y+;
VETU (it: n) VETU (Y::
2sup V (Y;)) VETU (Ý; ni)
(73)
y
Next, we make use of the semi-empirical ETU risk to bound
M m) ETUU Y; A) < Meru ( m) V [Y:n)
+ V Y m) VETU n)
ETu (Y:)) V (Y; ?)
(74)
The individual terms can now again be bounded by Theorem 5.2 and Lemma C.3
23

---

Algorithm 5 Sparse BCA(X, 177 ,,,))
Algorithm 6 Sparse BCA for coverage
I: Vi" t select-random-k( for [x]
[X, 17 c)
2: i <- Σ "f (ae)) "
1: 9." <
select-random-k(( for all [x]
3: 1 - 0i
2: f
p 1 -E Ei (x:)
3: for E [r]] do
5: Uald f- -00, Meew <- V/ (t,,q,9)
"
4: for (j. (2. 17 (x.)
y.
5: f
î1 (x.))
6: while Unew Hold + do
7:
for shuffle([n) [n] do
6: uald -00, Usen t - (m Σド= j=1 Sz)
t - (xx) (T:) ) ④ ya
7:
while Unew > Held + do for 8 shuffle do
9:
q a -0
8:
10:
9r'
<- 0
9:
for (J. (o: E (
@ 8. do
11:
for
(j. f1 (x.)) E (x;; do
10:
fj + f//(1 fy (x.))
12:
(1) vi (z.))
P.)
11:
9rr <- (j. (x.)) E 1) (a.)) do
13:
(0) 93.
14:
gd + 9rd u {ú) (1) (0))
13:
9º t gd U {Ui (xx))) y. + selectttop-k "
15:
y. - selectttop--(gg"
14:
it i -1 (x) O ys
15:
for (5.))((x)) "
(xx) ) ② y do
16:
f3 + f3 n (xx))
17:
+ q ".
Mold 6- Usews Unew
f- V (t, q)
17:
Mold Neews Vhew
(m 25 f3)
19: return peu
18:
return Y
Algorithm 7 Sparse greedy (X, n)
Algorithm
Sparse greedy for coverage
X, 17055 .k)
I: i E 0, q + 0, - 0
2: for E [m] do
1: f f-
3:
p p : (a.)
2: for [n do
4:
gº +
3: g
+ 0
5:
for (2:)) E () do
4:
for (J. (x.)) n (z:)
6:
(1)) t (t, (m.) p.)
5:
9 or g {(. (x.)),))
7:
+ (i, +(,) 2,)
6:
car + select (gg
8:
gdt +
9xh (01
/ (0)))
7:
for (), E n (a.) ) of do
8:
f5+ (x,))
9:
D.tH select k(g")
9:
return Y
10:
i + ! (x;) @ "
11:
a + 1 v.
12:
return yer
D Sparse and greedy algorithms
In this section, we present pseudocodes for sparse variants of the introduced algorithms, which we used in the main experiment to compute efficiently the results for large datasets. These variants use compressed sparse row (CSR) representation for row vectors. CSR vectors are represented as a list of tuples a == {(index value): value & 0}. In these algorithms, we replace (xx;) and ÿ; with their sparse variants, 17 (ax)) := {(j. f (x:)) : (x;) of 0} and g == { 0ig) : Dis # 0}. respectively. We need to ensure that of both (x,,) and ofth are ordered by their indices for efficient element-wise wise multiplication (Hadamard product) between them. we assume that the size of [ l: and (x.)) = k.' the resulting time and space complexity of the sparse algorithms are On((k' I,',,, + k: log k)) and O(n(k' k + k)), respectively. Additionally, we present the greedy variants of sparse BCA algorithms introduced so far that do only one pass over the dataset.
We present the sparse variant of BCA (Algorithm in Algorithm 5 and the sparse variant of Greedy (Algorithm 3) in Algorithm 7 The sparse versions of their specialized counterparts for coverage are presented in Algoriim 6|and Algorithm
24

---

E Extended results, experiments and details of empirical comparison
E.1 Datasets characteristics
In Table we include overview of the main characteristics of the datasets used in this paper.
Table 5: Multi-label datasets from XMLC repository 6 per label and average labels per point, respectively.
APpL and ALpP represent average points
Dataset
#Labels
#Training
#Testing
#Fcatures
APpL
ALpP
3,993
15,539
3,809
5,000
25.7
WIKI-31K
30,938
14,146
6,616
101,938
8.5
18.6
AMAZONCAT- 13K
13,330
1,186,239
306,782 782
203,882
448.6
5.0
WIKIPEDIALARGE-SON
501,070
1,813,391
783,743
2,381,304
24.8
4.8
AMAZON-670K
670,091
490,449
153,025
135,909
4.0
5.5
E.2
Extended results of the main experiment
In this section, we present the extended results of our main experiment from Section 7 Here in Table and Table 7 we present additional results for k = 1, well as results for additional methods:
MACRO-POREER MACRO-FloRERT COV oREED- the greedy algorithms (Algorithm 3) for optimizing macro-precision, -F1, and coverage (Algorithm 4).
MACRO-RRRIOR- the optimal strategy for macro-recall: selection of labels with the highest Pj M). with p estimated the training set.
Because both greedy and block coordinate- algorithms depend on the order in which examples are presented, we check if this has significant influence on the results. ran the procedures times with different seeds and presented both mean and standard deviation, which is mostly less than 0.25 for the macro measures.
E.3 Results on true labels
In the main experiment, the reported performance depends on three things: the inherent difficulty of the data, the success of the inference algorithm and the quality of the provided marginal probabilities. To be able to judge these terms, we also ran the inference algorithms on probabilities generated from the test set labels: 7i (x;)
iff Y 1 to rest only our inference strategy. We present the result of this experiment Table 8 Notice that in this experiment, the specialized inference strategies are almost always the best on measures they aim to optimize. Also, the obtained results for macro measures are significantly below 100%. This is because, this datasets, not all labels are represented with even positive training example in the test set. Still, there remains significant gap between these results and the results of the main experiments, with probability estimates coming from the LIGHTXML model.
E.4 Impact of stopping criterion and using only top-k' predictions on predictive and computational performance.
In this section, we investigate the impact of stopping criterion and using precalculated top-k' predic- tions on the predictive performance well as computational performance.
To materialize all marginal probability estimates for datasets like WIKIPEDIALARGE WIKIPEDIALARGE-500K and AMAZON-670K, one requires an enormous amount of memory and time. Because of that, we are not able calculate the exact results for these datasets, and instead, we used pre-select top-k' labels with the highest fi described in Secction 6) In the main experiment in [Section we used k' = 100 for smaller datasets (EURLEX-4K, WIKI-3 K, AMAZONCAT-IE and AMA - Here, we additionally compare the results for k' 100 and = 1000 for WIKIPEDIALLARGE. 500K and A AMAZON-670K investigating the impact of predictive and computational performance.
TO00 for larger datasets
WIIKIPEDIALARGE-
25

---

Table 6: Mean results with standard deviation of different inference strategies on @k measures calculated with & (1,3), using probability estimates from LIGHTXML model. Notation: P precision, R recall, FI--F-mmasurr, Cov Coverage The green color indicates cells in which the strategy matches the metric. The best results are in bold and the second best are in italic.
Inference sintegy
Instance G
Mazro $1
Instance 63
Mazro $:3
P
R badd
P aadd
R iird
F] and
Cov cod
P sivd
R
R toad
F1 and
Cov cad
EuaLix--K
Toe-
88.77 m0
17.41 s000
15,02 4s00
5.10
6.98
16.63
=0
74.20 50100
44.21
=000
[24.55
16.45 10.0
18.63
31.21
PS-K
74.39
14.99
24.76 2000
13:00
15.22
28.80
69.01
41.05
10.12
23.72
25.05
40.29
Pow. a.a
15:42
12.50
14.86
70.08
29.43
22.57
24.34
38,93
Pow a.
14.07
13:48
15.55
65:35
38.95
30,49
25,26
25.93
42.11
76:00
15.88
1000
71.08
10/0
22.10
1000
100
57.90
Macan-PParm
10.04
10:82
13.45
53.85
49 15
20.16
11:18
22.65
23.15
MACIo Pers
47.16
2521
+0.03
=0:1
41.13
18.78
2005
MACRO-FP Rooce
57.59 =500
11.49
2000
53.09
29.85
MACRO- Rass
2816
1500
12.11
10.20
14.59
00:00
41.47 50.00
3500
30.36
0000
25.16
51.00
24.37
1009
44.26
MACRO- Plossu
63.90 =8:1 12:78
12:77
10.34
15:77
09.20
60.95
31,60
-8:11
24.55
s1.11
26.26
2012
43.96
=030
Macao-Flar. lace
62.34 -031
12:49
1000
1611
13.55
1825
16.78
100
61.06
10.06
44.53
45.44
.864
27.92
1836
10.79
10.3
13.11
1811
10.13
10/8
36.78
21.23
15.38
1M77
Covers
43.77
-931
8.61
2006
30.89
#621
11:65
10.7
14.06
2014
36.14
-9:44
24:00
10.77
[4.00
2000
31,46
21:30
19.05
1100
47.19 -0.13
AMARON 13K
Top-K
96.38 000
27.49
1000
11:29
1000
1881
10:00
2.79
1,00
13.06
-0:0
K3.35
10:50
63,01
1000
25.71
-000
11:37
10:00
13.85
1.0m
33.05 -010
PS-
56.41 =010
24.26
100
42.58
1000
25.
12
$0.00
28.17
2000
55,50
=0:00
79.0%
10.00
60.15
2000
43.89
=0:0
38.64
20.00
38.56
1000
62.
=010
Pow-K
79.34 1000
21:47
100
40:09
500
23:09
10:00
27.09
200
53.74
-3:00
74:40
10:00
56.50
20/
41.87
20:0
39.07
10:00
18.17
1m0
61.
10 =010
Pow K
71,88 =010
19.08
2009
80,09
28.57
$0.20
30.02
2000
59.59
=0.0
66.52
+0.00
50.75
38.18
=010
46.42
m0.00
39.26
2000
67.76 =010
Loo K
80.12 =0:0
21.30
2000
37.42
8000
19.75
+0.20
23.32
2000
47.55
-0:0
75.30
t0.00
56.79
2000
41.09
=0:00
33.92
m0.00
35.01
2000
56.02
=010
Macao-Parm
64.10
15
23.96
jom
50.05
1m0
27.65
1/:34
50.90
1oos
73.70
14
65.
49.76
1.77
44.89
11:7
48:79
41.63
1007
79.96
-00
Macaa-Pars
02.29 _am 26.30
63.33
1mm
22.58
20.95
73.35
10
54.97
15
41.61
1021
64.27
29:22
35.76
Jom
76,15
.016
Macao-Ra Roore
61.09
15.00
36.45
34.71
51.01
64.30
19.32
30.64
54.35
34.06
75.91
Macso-Rars
59,70 -010 15:80
37.95
37.71
52.90
69.50
47:74
31,40
58.32
34.65
00.71
Macao
19.14
49.15
Macao Plac.
72.50
19.30
31.67
70.61
51.95
48:22
47.93
77.83
10/0
2.44
00
9.79 0800
00.00
Top-K
88.95 _000
0.99 10/0
10:00
1000
1.31
-000
77.17
10.00
10/0
2.01 0:10
0.50 1.:00
0.72 1,00
PS-K
73.00 _000
3.0 15/0
10.20
1.00
1000
3.78
0000
67.
10000
15/0
3.89 8:00
1.47 11000
1.93 11/0)
0000
Pow-K aweas
72.91 =010
1009
2.80 1000
0.61
1:100
0.01
2000
3.50
-000
66
1::00
11:50
1000
3,60
2010
1:35
2:100
1.79 110m
=000
Prre-K awe
60.12 2010
100
1.44 1000
0.90
1::30
2000
4.57
-0:0
55.06
1:100
0.50
10/0
4.49
5010
1:1.0
2.50 .m/m
6.98
=000
Loo K
23.17 =910
4.32 2000
2.52 4500
0.53
+0.20
0.81
2400
3,16
-0:00
65:20
50..0
11.34
=200
3.40
=010
1.24
$1.00
1.66 -1000
4,84
=010
MaCRO Posas
33.114 =340
2.15 20/4
3.17 H00P
1.04
20.23
1.53 2005
6.17
=0:00
32:65
t0.13
3.62 1000
6,89
=010
2.78
3.44 11055
10.02 =00e
Macao-Pass
31,46 -034
1,80 1e01
6.48 100e
1.24 1033
1,80 1007
6:48
-300
32:96
10
5.66
17:17
9.13
0.00
2.55
3.38 1mm
9.21 2010
Maczo-Raus
45.30 .010
2.63 160h
3.91 1000
1.51 1030
1.45 1000
5.37
04:00
36.67
10:00
6.35 10/0
5.34
-010
3.55
10:00
3.60 10m
9.35 .010
MACRO-RA Razs
12.95 =010
0.74 1m0
3.29 200
1.7 10:30
1.41 2000
2.61
=0:00
13.78
10:00
3.36 200
4.77 -000
3:24
10:00
3.10 1m/
7.26 =010
MaCRo-Flann Fleamm
43.15 46
2.53 16m
5.05 2016
123 1033
1:78 2009
6.20
20:0
36.
6.85 20m
6.56 -m
2.91
10:03
2,67 1m0
9.01 =00
MACRO Fiiee
39.82 =0:0
2.33 200
3.67 1004
[.4] 20.2
2,03 200
6.43
11.04
37.32
k0.07
6.52 m0m
7.87 =000
3.15
25.02
4,10 2002
10.42
=012
CoVo
40.24 =044
2.33 200
4.34 4000
0.95 #022
1,30 2002
6.15
27.39
4.06 200
5.21 =000
2.72
2.97 2001
10.00 =010
Coverss
40.52 :0:38
2.35
5.10 10/C
1.11 10.30
1.60
6.72
27.00
4.63 a530
6.24 00:0
3.18 10.1
3.41 1001
11.04
WIKIFIDIAL LARGI-S0RGS
Tor
74.94 =00
24.26
12:21
6.74
7.75
15.36
56,02
45.70
20.15
18:37
17.14 1:0m
32,24
PS
72.00
23:50
18.99
10.96
12.47
23.58
$1.91
45.61
23.33
22.68
20.41
37.85
Pow- aua
23:73
19:54
36.29
Pow 2-0.5
23.26
13.14
39.36
L.0G-K
_000
10/0
10.30
300
10/0
1mmm)
Macao Prarm
=0.0
15.49
2001
12:99
200
=0:00
46.19 20.25
200G
26.33
25.49
21102
23.29
1000
46.04
MACRO Pass
47.68
=000
15.02
13:38
20.21
16,94
2001
=0000
2000
37,69
=0:00
2500)
45,05
Macao--Raue
_00e
10:0
1//0
14:26
1,030
1000
0.00
46
1.000
10/0
34,82
8:
(4:00
22.92
1800
44.13 .000
MACaa-Ra.. Razs
21.47
1000
24.76
14.91
10.20
16.71
1000
32.61
00000
43:40
15/0
25.35
00
27.55
1:100
22.72
10/3)
46.30
MacRo-FFin hesm
21
4:
1001
1000
12.84
1:31
15
2001
$1.09
-100
48
1:1
10m
05.50
1:11
22:26
1001
43.65
=00)
Macaa-Flu.. lere
-mm
20.98
100
10ml
13,61
10.00
16.84
1000
0100
41.32
1::00
10/0
23,69
1:100
26.01
1pm
46.
CoVcamn
47.41
=300
15.55
2001
23,70
#000
13.07
1021
14.26
200
35.36
-000
18.67
25
25
200
23.56
=010
25:40
#1:1
20.65
1000
47
06 =010
Covecs
40.84
=000
15:47
200
16
#001
14.30
2001
16.05
200
36.06
01
27:31
10:00
24.55
2000
25.92
=010
26.76
21.60
11000
50.
16
=00)
AxA220--67KK
Top-K
46.86 -000
9.68 Lenh
5,85 10/0
3.34 10:00
3.68 1,0
6.13
00:00
41.71
10:00
24.08
1bme
10.77
-000
9.68
1:00
9.51
1pm
14.35 2000
PS
46,95 =010
9.37 20/0
5,87 2000
3.97
$0.20
4.35 2400
6.55
-0.00
41.05
00.00
23.77
2000
11.86
20:0
10.36
20.00
10:42
2000
15.50
=000
Pow-K K
45.49 20:0
9:45 20/0
5.75 5000
3.56
20.20
4.25 2000
6.79
-9.00
41:30
00.00
23.80
2000
11.65
00:0
10:35
20.00
10.24
200
15.27 =010
Pow- K
44.08 =0.0
9.33 200)
5.94 s000
4.04
s0.23
4.41 2000
6.53
00.00
40.90
00.00
23.71
4000
11.99
0010
10.65
10.00
10.53
10m
15.64 =010
Loo K
46.09 =0.00
9.54 2000
5,55 2000
3.68
20.23
4.06 2000
0,61
10.00
11.54
50.00
26.00
2000
11.34
0010
10.10
20.00
9.95
2000
14.94
Macmo-Parm
43.47 -0:1
9.03 ieni
7.04 1000
3.86 1:330
4.69 1001
8.51
-000
16
30
10:00
23.43
10m
14.18
10.63
108)
11:34
1001
17.30
Macao-Par.
42.37 -016
5.83
8.73 10ml
3.99 1n
4.97
8.77
-00
13.79
19:75
1040
17.27
10.53 1m
12.12 1pm
17.75
Macao Rouce
43.08
9.08
6.09
1.25
6.58
39.35
23.20
12.45
11.07
10.91
16.12
MaCao-
42.33
6.82
4.35
4.86
7,46
39:42
22.92
13.71
11.17
11.47
17.12
Macao-
7.74
16.93
MaCao Placs
43.36
8.12
8.36
37.34
16.69
12.17
17.65
13.05
10.75 1001
Covers
10/0
10.30
10/0
10m
1000
(m/)
26

---

Table 7: Mcan results with standard deviation of different inference strategies on @k measures calculated with l E {5, 10}, using probability estimates from LIGHTXML model. Notation: P precision, R recall,, FI--F-measure Cov Coverage The green color indicates cells in which the strategy matches the metric. The best results are in bold and the second best are in italic.
Inference stntegy
Instance G5
Macro 85
Instance @ 10
Macro 8010
P
R todt
P aiad
R mod
F1 toad
Cov
P poal R
R at
Fl ann
Cov mad
DURLEX-4K
Toe-
62.31
68:59 1000
25.43 +smm
25.99
25.50
2000
39,76
=0
39.29
75.11 =0/0
22.15
26.59
=3re
26.01
sumn 47.55
PS-K
59.17
29.89
28.17
25.78
49.47
Pow. a.2
59.40 06
29.23
27.24
39.09
21.50
25.88
Pow-K a.
11:25
20.77
1030
1000
(00)
21.60
037e
MaCao Prarm
=0.25
40.8
27.42
21.89
20:15
25.52
34,62
=324
19.64 =021
MACRO Pets
30.33
2009
18:46
21.59
18:45
5316
2005
42.89
Macsa-Raaie
48.36 00:00
47-42 1000
1500
32.82
27.36
1000
00.00
15.00
50000
19:74
1000
3310
24.28
1009
51.64 2010
MACRO- Rass
38.32 00.00
37.54
1000
1500
31.27
0010
27:05
3000
49.04
00.00
29.30
5000
57.58
1003
22.99 300m
2310
1009
52.15 =010
Macso-Fleu hess
1015 53.53
1017
10:00
30.46
17
46.70
-0:0
13:01
1016 65.06
1n
88 100f
20:1
26.04
1007
Macao-Flar. Flac.
56.18
1034 54.70
1000
-800
30.1
1005
-400
33.55
1:0
64.20
32.78
13M
30.47
1m0
Covcamo
18.81
11
18.19
20.0
21.48
25:24
=9:66
17.84
2011
11.02
20.9
21.23
2009
18.
1:00
29.82
=0.0
15:25
1007
Covers
16.40
29:9
15.95
2005
10.00
24.53
-915
18.1
2007
30.09
-0:11
9.31
2014
18.05
3m:0
26.99
20114
28.28
2316
17.41
1000
52.84
AMAZONCAT--1 13K
ToP-K
68.01 1000
79.11
1000
33.92
1000
11.34
0000
29.28
(000
52,60
-000
41.77
1000
89.41
24.63 1000
51.76
1510
28.84
10m
68.61
-010
PS
06.63 20.00
77.89
2000
38.41
1000
45.00
=9:0
38.34
2000
65.82
-0:0
4/
1.50 2010
89.7
1000
22.
56 200
58.69
=3:0
28.59
74.29
=010
Pow-K
63.59 00
75.08
100
16.24
100
45:96
38.15
2000
65.55
20
40
10:58
1010
88.17
1000
21
96 100
58.50
2310
28.41
1pm
73.36
-010
Pow K
56.94 =9.00
68.14
1000
31,05
54.06
=910
36.90
2000
71.95
-0.0
37.56
0010
83.91
20/0
19.25
100
64.05
=330
26.29
77.27
=010
Loo K
66.07 =0.00
75.21
57.40
4000
41.86
=9:0
36.78
2000
61.84
-0.0
40.56
85.05
1000
23.09
200
55,55
#310
28.91
200
71.37
=010
Macmo-Paarm
152.18 1935
62.08
10:15
41.03
54.76
11
40.70
1o07
82.58
19. 50
1:14
66.03
10:1
99
101
54.54
10:17
37.46
1om
R1.86
-00
Macao-Pars
41.53
10:13
49.66
63.11
1000
30.43
35.09
76.75 -40
15.
57.35
jnil
61,84
1o0l
33.06
13M
35.08
1o0
78.17
.016
Macao- Roace
40.67
69.85
29.63
79,08
27.5 07.59
16:25
70:77
21.96
82.57
Macao-Rar. Rars
36.91
48.26
17
100
65.47
50.37
2009
82.91
26. 50
61.99
17.53
72.63
23.22
84.84
Macao
70.41
36.35
Macao Place
60.70
71.93
50.89
12.32
49.48
79.63
37,50
19.47
49.21
11.10
00.0
19,02
Top-K
68.31 1930
19.59 1001
3.66 1000
0000
1.24
[0:00
3.72
00
52.00
10:00
in/r
1000
2.07 1310
2.34 1100)
PS-K
62.65 1:000
18:07
1000
4.21 1500
2.14
00:00
2.56 10000
6.54
10:00
50000
11:00
1000
3.62
8330
3.61 1100
2000
Pow-K aweas
59.09 =0
17:26
1009
4.00 1100
2.01
2010
2:42 2000
6:20
00
48
2010
27.20
10/3
1000
3.50
2310
3.49 1100
=010
Prre-K awe
50.12 -0:0
1000
4:83 1000
3.13
1010
3.97 1000
8.53
40
10100
1m/0
1000
5.10
2310
4.47 1mm
11.37
Loo K
57.74 =0:00
15.49
2000
3.74 +500
1,56
=0:0
2:25 24000
5.59
-0.00
43.82
5000
24.37
10000
4,24
2000
3,46
=310
3.37 2000
8.61
=010
MacRo Posas
331.3 =0.17
8,96 2107
1.25 110F
3:93
=010
4.39 2405
11.93
=0.00
27.42
20.15
15:45
20:43
7.07 2006
5.34
2310
5.14 100
13,99 =010
Macco-Pais
30.52 La35
8:56 inta
9.68 1000
2.85
.000
3.74 indi
9.82
-3:00
24.51
1031
13.62
in17
9.79 1001
2.98
13m
3.85 1801
10.04
.00)
Maczo-Rmucs
31.32 1030
K97 1000
5.78 1000
5.02
0000
4.53 (800
11.63
00:00
24:23
1,00
13.66
103)
5.55 10m
7.38
1510
5.31 18m
14.75 .010
MACRO- Razs
14.01 =9:00
196 100
5.79 100
71
2010
4.05 2000
10.72
-0:00
13:88
2010
7.70 k00
5.72 20m
7.2
2310
5.02 1mm
15.72 :010
MaCRo-Flaan Fleamm
36.50 =2 15
10.50
1005
6.91 100
4.06
2004
4:64
1005
11:00
14.80
2018
19.72
1005
6.80 100
5.68
23m
561
100
13.80
2016
MAC3O Fiiee
38.98 =9.9
11.24
20m
8,30 4000
4.14
2012
5.08 2002
11.88
11.04
29.31
22.28
200
8.18 2002
5.11
=300
5.76 2001
13.00
=010
CoV
21.19 =0:10
5.04
2002
5.26 4004
4,00
m000
3.71
2002
12:25
-000
14.77
2014
8.20
2002
5.03 100
6.22 2300
4.40
2004
15.32 =004
Covers
20.30 00:77
588
6.42 100
4,50
0010
4.18
1001
13:33
13:95
6034
7.78 1002
6.23
6.58
8300
4.81 1001
16.39
WIKIPEDIALARCE LARGI-500K
Tor
43.12
51.28
20.51
=50m 25.86
19.86
40.62 10
27:00
63.15 =m/)
17.16
34.79
19.57 -10m
50,15
PS
42.86
$4.51
21.64
29.15
21.77
45,00
27,05
63.45
16.70
37.55
19.87
53.67
Pow-K aua
54.07
28.04
19:81
52.36
Pow 2-0.5
52.72
30.00
22.18
26.09
16.45
19:85
54,35
L.0G-K
54.09 1001
10/0
20.49
1003
17.08
55re
19.69
Macao-Parm
42.70
11.48
34.20:2
50.04
22:11
56.11
MaCRo Pars
=0.0
22.54
2500
21.12
=0:0
21.10
2000
=0.00
200
37.77
=310
1000
=000
MACRO Rooce
35.00 =0.00
1500
22.95
2000
=0.00
23:09
2010
2000
200
=310
19:51
57.65 =000
MACRO-R, Razs
33.58 20:0
47.34
1000
1500
33.56
23.63
1000
00000
21.81
80:00
10/0
15.92
100
40.97
2310
20.07
100
58.42
MACRO-FP Fless
37.25 m03 48.36
som
150
31.47
2010
26001
51.32
00000
20.96
50.00
sm0
21.61
150m
34.15
=330
1001
56.67 =010
Macao-Flur, Plee.
32.06 2030
1000
85.79
10m
19
10
27.64
1000
40.30
06
19:30
1010
1000
180
37.49
2310
25.15
1m0
50.67
2000
Covcamo
20.75
Los
1001
15ml
31.08
20.35
1881
0000
12:57
10000
in01
15:11
1001
37.95
130
17.19
1m01
Covars
19.46 =0:0
26.06
2000
24.14
400
32.13
=910
21.08
2000
55,40
00
11.59
2010
32.09
1000
18:45
2000
38.56
=3:0
18.08
2000
61.15 -000
AMAZON 670K
Top-K
37.71 200e
35.23
1000
14.26
1000
15.16
0010
13.76
1o00
30.41
-000
25.36
1010
46, 74
14.83 100
31.56
1310
16.20 1o0
26.85 _000
PS K
37.54 2010
35.13
200
14.95
4000
15.73
2910
14,31
2000
21.16
-0.0
25
2010
45.65
11.89
200
21.85
=310
16.34
27.
=000
Pow-K
37644 2010
35.21
100
14.71
2000
15.58
29:0
14.17
2000
20:95
-0:00
25:33
2010
45.7
:000
14.85
200
21.76
2310
16.30
2mm
27.09 =010
Pow- K swas
37.77 sa.0
35.07
2001
14.95
s000
15.54
14.42
2000
21.30
00.00
25.24
00.00
46.00
14.90
100
21.92
=310
16.36
2mm
27.30 =010
Loo K
37.69 =0.0
15.22
14.45
2000
15.37
29.00
13.97
2000
20.68
00.00
25.35
50.00
=001 46.75
14.85
200
21.54
2330
16.24
2000
26.94 =010
Macao-Pasm
34.06 2a
31.94
1pm
17.00 100l
15.67
200
15.27
100
20.30
-00
19.91
20:0
37.00
inos
16.65 100l
19.64
23m
16.47
1n01
15.76
Macao-Pas.
27.52 T1
26.09
21,09 1m1
14.38
21
15.95
21.06
-4:44
15.00
1a1e
28.33 inai
23,21 1nm
16.36
291e
17.50
1nm
24.13
Macao Reses
36.78
34.50
16.23
14.76
21.84
24.90
15:02
16.46
27.60
MaCao-
36.43 49
34.19
16.68
16.38
15:40
22.61
24.72
45.20
16.30
22,23
17.46
28.08
Macao-
33.04
16.70
MaCao
30.04
15.15
22.25
18.48
22.79
18.89
25.12
20:05
15.67
20.87
16.12
Covers
28.39
10/0
15:54
(00)
20100
1nd1
16:20
1510
27

---

Table 8: Results of different inference strategies on @k measures calculated with & E (1, 10), us- ing true labels as predictions. Notation: P preciiiio,, R R-recall, #1-F1-measum The green color indicates cells in which the strategy matches the metric. The best results are in bold and the second best are in italic.
Inference
Instance 6:1 P
Macro #1 R
Insiance @5
Mocro @3 R
Instance 65
Macro 655 R
Instance 810 P
Macro 8 R
stratogy
R
R
F
R
F]
P1
EURLEXX-K
WEIGHTED--OO Tor-K
100.00
20.53
33.19
36.83
99.12
69.06
65.95
55.09
00:45
92.58
99.95
66.43
65.11
05.06
52.93
66.42
66.42
MA MACRK--Paa
100.00
20.55
55,47
28.26
33.76
99.12
60.06
03.54
56.65
59.69
92.58
89.95
06.36
64.93
03.54
52.93
99.96
66.43
66.42
66.42
MACRO-Pa Pars
100.00
20.53
60.13
11.89
37.57
99.12
68.06
66.35
58.33
67.02
92.58
89:95
66.43
65.18
65.77
52.93
99:96
66.43
66.42
66.42
MACRO Rasse
100.00
20.53
50,05
33.19
16.83
99.13
69.06
05.95
58.09
00.43
92.58
89:95
66.43
05:11
65.06
52.93
99.96
06.43
06.43
66.42
MAURO--R Racs
100.00 30.53
53.01
35.24
79.11
99.12
68.06
06.34
55.699
61.00
92.58
89.95
66.43
65.11
65571
52,93
99.96
66.43
66.42
66.42
MACRO- Fl
100.00 20.53
55.17
31.35
96.27
99.12
60.06
65.64
57.17
59:99
92.58
89:95
66.36
04.94
65:55
52,93
99.96
66.43
06.42
66:42
Flacs
20.53
92.58
AM552ONCx1--38
W WEIGHTED-TOP- K] 100.00
29.06
53300
74.51
78.21
991.73
69.95
99.55
95.30
90.87
77.27
88.81
999.58
98.37
95.82
47.43
97.30
599.58
55.44
99:49
MAC Passas
100.00
29.16
98.49
70.30
77.46
91.75
69.95
99.55
95.27
98.78
77.27
89.81
59:.58
98.31
98.80
47.43
97.80
99.58
99:44
99:49
MACROOPPas Pars
100.00
29.06
99.14
72:14
78:03
91.73
69.95
99.58
95.48
00
77.27
88.81
99.58
98.
08.83
47.43
97.50
99.58
99.44
99.49
MACRO
100.00
29.06
53.05
74:51
78.21
91.73
69.95
99.58
95.36
96.87
97.27
88.81
99.55
98.37
98.82
47.43
97.50
99.58
99.09
MAURO-Raa
100.00 29.06
74.75
78.72
91.73
69.95
99.58
95.58
77.27
88.81
99.55
47.43
99.49
MACRO-PP Fleam
29.06
72.53
78.68
96.82
77.27
47.43
999.49
MArao-F1,.
100.00
29.06
08.38
74.03
79.68
91.73
69.95
05.55
96.92
77.27
50.81
98.83
47.43
07.50
99.58
99.43
99.49
WIKI-1K
WEIGHTED-TON TOP- K. 100.00
6.19
17:45
13.91
14.84
99,99
18.55
47.007
37.35
29.94
99.93
30,82
644.25
52.71
55.27
99.10
58,83
71.10
67.39
08.56
MACRO-P.
100,00
6.19
10.62
12:45
99.99
18.55
52.07
36.77
99.93
30.82
49.18
53.46
66.52
67.96
MArRo-Pars
10.65
99.09
18.55
57.54
68.57
MACRO- Rasie
18:55
37:05
39.94
30.82
52.71
55.27
MACRO- Racs
100.00
6.19
31.06
18:28
19.02
99.99
18:55
54,62
42.65
45
99.93
30.82
69.59
55.60
58
96.10
58.3
71.26
67.74
65.
MACRO-PI Planar
100.00
6.19
21.20
14.00
16:09
99.99
18.55
54,09
37.19
00.99
99.93
30.82
66.47
31.53
55.19
95.10
5523
70
66.73
08.09
MACRO-FFI Flara
100.00
6.19
27.36
18.26
19.00
99.09
18.55
59.04
42.23
46.11
99.03
30,82
70. 70
55.97
58.86
98.
10
58.53
71.27
67.72
68.89
WIKIPSDIAA L.REI S00K
WEIGHTED Tor
100,00
37.10
72.36
49.26
84440
73.79
96.74
83.98
87.72
68.87
87.71
93.53
44.11
97.48
98.49
98.90
MACRO- Parsas
100.00
37.10
46.25
52.36
73:79
87-17
87.71
92.92
95.19
97.48
99:35
98.98
MArmo-Pacs
100.00
48.46
57.03
73.79
85.00
89.67
68.H7
H7.71
94.00
W6-07
44.11
97.48
99.61
98.
MA Royie
100.00
37.10
72:36
49.26
54.43
84,80
73:79
96.74
83.00
87.72
68.87
87.71
98.
03.53
95.42
44.11
97.48
99.52
09.49
98. 98.90
MACRO- Ruck
100.00
37.10
78.55
53.86
59.3 30
84.40
73.79
98.52
85.87
59 60
68.87
K7.71
99:42
94.22
96.04
44.11
97.48
99.58
98.60
08.00
MACCO- F Planaur
100.00
37.10
30.33
48.26
55.45
84.40
73.79
97.63
K3.29
$7.80
68.87
87.71
99.08
93.19
95.33
44.11
97.48
99.54
95.43
98.88
MAC Flare
100.00
37.10
85.18
53.26
60.45
84,40
73.79
92.08
85.69
89.00 88
68.87
87.71
99.49
94.17
96.11
44.11
97.48
99.59
08 60
99.00
AMAZIN-670X
WHIGHTI-TOO-K
100.00
25.99
17:51
14.64
15:41
993.99
69.62
40.14
35.43
36.71
18.655
87.65
449.91
47.71
49:41
51..00
100.00)
51,81
51.81
51.81
MACRO- MACRO-PanLa
100.00 25.99
21:37
12.72
14.61
93.399
68.02
43.83
34.21
39.10
$7.65
87.65
50,05
47.50
48.63
51.70
100.00
$1.81
$1.81
$1.81
MACRO- Pars
100.00 25.99
21.84
12.96
14.88
93.39
69.62
46.14
35.91
38.92
87.65
87.65
51.13
48:27
49.33
51.70
100.00
51.81
51.81
51.81
MAURO-Rass
100.00 25.99
17.51
14:64
15:41
93.39
68.62
40.14
35.43
36.71
87.65
N7.65
49.91
47:31
45.41
51.70
100.00
51.81
51.88
51.81
MACRO-RA Rucs
100.00 25.99
19.58
16.63
17:43
93.39
68.62
43.45
37.54
89.
87.65
87.65
50.88
48.44
49.23
51.70
108.00
51.81
51.81
51.81
MACRO Fl
100.00 25.99
21.15
14.45
16.03
93.39
68.62
41.10
35.16
35.71
87.65
87.4
47.65
45.67
51,70
100.00
51.81
$1.81
51.81
MACRO-F1ara
100.00
25.99
16.50
60.62
37.24
$7.65
N7.65
48.38
51.70
51.51
51.81
Another factor that impacts the running time is stopping criterion c, which indicates minimal ex- pected utility gain to continue BCA algorithm. Here we test and report results for 3 values of WIKIPEDIALARGE-500K and AMAZON-670K
e E {10-3, 10 - 10-7} on AMAZONCAT-133. datasets that are the largest in terms of number of samples and labels.
The results of BCA methods with different values of e and k' are presented in Table 9 we additionally report the number of iterations (number of passes over datasets performed by the BCA algorithm) and time in seconds. The numbers are the mean results over runs with different seeds. For all values of e and K. the results are very similar. In the case of WIKIPEDIALARGE--000 dataset, K/ 1000 achieves slightly better results than K' = 100 in a few cases. In the case of all datasets, the smallest = 10-7 is usually the best. However, even the largest tested c = 10-3 that is greater than the inverse of number of labels and samples is only slightly worse at the same time, requiring much smaller number of iterations. For all values of and k', the BCA algorithm terminates in just a few iterations, finishing always in less than 20 minutes. Please note that we implemented our algorithms in Python with some parts optimized using Numba (44- - LLVVM-aased just-in- -imettimmeaani (JIT) compiler for Python. Because of that, we believe that the running time can be further reduced by using more performant programming language.
In this table,
E.5 Results with mixed utilities
the optimization of macro-measures comes with the cost of a significant drop in performance on instance-wist wise measures, which in some cases may not be acceptable. To achieve the desired trade-off between tail and head label performance, one can optimize
As we already discussed in Section 7,
trade-offbetwenn
28

---

Table 9: Impact of different values of k and on the results of @k measures calculated with k E {3,5). Notation: P P-precision, R R-recall, Fm-auu-e Cov-Coverage, I-number of iterations, time in seconds. The green color indicates cells in which the strategy matches the metrie. The best results are in bold and the second best are in italic.
Inference strategy
Instance P
It/Time T
Instance
68.5
Macro R
It.TTime T
R
R
Fl
Cov
P
R
P
Fl
Cov
AMAZUNCAT- 13K.
100
MACRO-Pics 10
[57.62
43.92
64.22
29.28
35.79
5.00
127.13
43.08
51.52
63.73
30.55
36.05
5.00
127.90
MACRO-PA Paoo-PP 10"3
55.95
42.55
64.25
29.25
35.76
76.20
7,00
171.43
41.70
49.91
63.79
30.44
35.98
76.77
8.40
208.17
MACRO-Pam 10
54,97
41.61
64.27
29.22
35.36
13.80
334.67
41.53
49.66
63.81
76.75
16.40
400.34
MACRO-Flacs i 10-3
70.60
53.84
51.90
48.23
47.91
3.00
91.22
60.70
71.93
50.78
52.40
3.00
91.50
MACRO-Flas, e 10
70.61
53.86
51.95
48.22
47.92
77.82
4.60
134.85
60.70
71.93
50.89
52.32
49.48
79.64
5.00
147.03
MACRO-Flas. 10-7
70.61
53.86
51.95
77.83
201.24
60.70
71.93
79.63
8.20
248.82
Covana 6 10-3
4.55
2:30
34.23
35.20
15.87
82.65
3,00
21.35
2.64
28
39:11
14.18
84.39
3.00
21.75
CoYaca e= = 10
4.53
2.29
34.83
35.16
15.90
82
5.20
34.64
3.20
2.63
29 19.30
39.05
14,23
84.39
5.00
33.54
Covaca c 10
34.93
35.16
8.60
$7.96
29:40
39.05
8.20
54.86
W WIKIPEDIAT.AO ROB-500KK R/
100
MACRO-PiC. 10
31.25
25.50
37:43
20.77
23,
45.9
4,00
261.61
22.30
28. 10
37:23
22
23.82
48.01
4.00
264.13
MACRO-Pas PIe 10-5
31.12
25.43
37:48
20.74
23.37
6.00
355.70
22.17
22.38
47.92
359.58
MACRO-Pass C 10"
31.09
25.40
37.50
20.72
23,37
45.85
15,20
928.40
24
27.95
37.33
22,36
23.85
47.88
19.60
1198.52
MACRO-FIA Seso--Flassie 10
44,28
36.70
35
23.92
25.92
46,72
3.00
234.15
33.51
41.86
35
26.93
27.30
50.24
3.00
235.64
MACRO-Flaca- 10-3
44.28
36.69
35.40
23.89
25.95
5.00
358.02
33.50
41.84
35.42
26.87
27.33
5.00
361.94
MACRO- Fl
10-7
36.69 44.28
35.42
23.89
25.96
46.67
10.60
764.05
33.50
41.5 84
26.86 35.45
27.35
50.12
14.40
1040.98
CoVara 1 = 10-8
27.56 24.71
25.95
26.86
21.68
50.16
3.00
54. 30
19.66
28, 26
23.17
32.29
21.19
55:45
3.00
55.61
CoYaca , 10-5
27.48 24.65
25.98
26.85
6.00
95.63
19.60
23.19
32.28
55,46
5,00
79.93
CoYaca = 10-7
24.65 27.48
25.98
26.85
21.66
50.19
9.00
143.27
19.60
28.19
23.20
32.28
21.17
55.47
9.00
142.02
WIKIPEDIAL ARRGAA 500K,
1000
MACRO-Pie. i 10-3
25.26
21.87
37.65
20:21
23,43
45.12
4.00
447.443
16.33
37.86
24.09
46.29
4.00
448.26
MACRO-Pas LACRO-PIa.-. 10
25.19 21.81
37.69
20.18
23.44
45.08
6.00
597.66
16.26
22. 54
37.87
21.13
24.09
46.24
5,20
550.41
MACRO- Pat. 10
25.19 21.81
37.69
9.60
16.25
10.00
1063.38
MACRO-FI ,6= 10-3
43.83
36.41
35.30
23:73
25.97
46.41
3,00
386.38 38
32.97
41.23
35:67
26.27
27.61
49.32
3.00
388.71
MACRO-FI 10-3
43.82 36.40
33.41
23.69
26.01
46.36
5.00
604.95
32.96
41.20
35.78
26.19
27.63
49.20
5.00
627.05
MACRO-Flaca- 10-7
43.82 36.40
35.42
23.69
1041.18
32.96
41.21
35.79
9.60
1168.04
CoVana 10"3
27.40
24.61
25.89
26.76
21.63
50.13
3,00
102.62
19.53
28.13
23.11
32.14
21.11
58.38
3.00
103.42
Covana 6 = 10-5
27.31 24.55
25.92
26,76
21.60
50.16
6.00
186.13
19:46
28. 06
23:13
33.13
21.08
55.39
5.00
160.21
CoYaca , 10-7
27.31 24.55
25.92
26.76
268.57
19:46
23.14
32.13
8.60
261.12
AMAZON- 670K, A² 1.00
MACRO-Pas Pseu , 10
33.13
19:38
17:45
10:50
12.11
17.76
4.00
53.67
26.79
25 A4
21:21
14:22
15.84
21.88
4.00
53.32
MACRO-PIC. 8 10
33.12
19.38
17:46
12.11
6.00
70.77
26.78
5.00
59.85
MACRO-Pas Paca.== 10
33.12 19.38
17.46
10.49
12.11
17.76
7.60
89.95
26.77
25.44
21.22
14.22
15.85
21.88
8.40
100.14
MACRO-FI
10-41
37.08
21.54
16.65
10:75
12.21
17.69
3.00
46.75
31.64
29.75
20:53
15.06
16:35
22:21
3.00
46.34
MACRO-FI ie 10-3
37.04
21.33
16.67
17.69
5.00
71.70
31.63
29.73
20.55
15.06
16.36
5.00
72.32
MACRO-FIaa 10-7
37.04
21.53
16.67
10.75
12.22
17.69
7.60
109.27
31.63
29.73
20.55
15.06
16.36
22.21
7,00
100.73
CoYan <- 10-3
33..40
20.32
14.04
10.84
11.23
17.69
3.00
11.11
30.30
28. 28.40
16.43
15.94
14,85
22.99
3,00
10.93
Covens 10-b
35.38 20:31
14.04
10.85
11.23
17.70
5.00
15.67
30.28
28.
16.44
15.94
14.85
22.93
5.00
16.06
Covaca = 10-7
35.38 20.31
14.04
10.85
11.23
17.70
7.20
22. 22.30
30.28
28.30 38.38
16.44
15.94
14.85
22.93
6.60
21.12
AMAZON- 670K,
R² 1000
MACRO-Pao. 10
33.08
19:36
17:46
10:48
12.11
17.75
4,00
101. 39
26.64
25.
27.25
14.16
15.85
21.82
4,00
102.97
MACRO-PIC. 1 10
33.07
19:35
17.46
10:48
12.11
17.75
5.40
117.07
26.63
25. 30
21.25
14.16
15.85
21.81
5.00
111.32
MACRO-PIa. 10
33.79
19.75
10:53
7.40
164.02
27.52
26.09
21.09
7.40
166.23
MACRO-Fla.. 10
37.05
21.54
16.65
10:74
12.27
17.69
3.00
86.95
31.60
29.70
20.54
15.04
16.35
22.18
3.00
88.40
MACRO-FIan. 1e 10-a
37.03
21.53
16.67
10:74
12.21
17.69
5.00
131
31.58
29
20.57
15.03
16.36
22.17
5.00
133.04
MACRO-Flacs 1
37.34
21.70
7.20
182.83
31.97
30.04
20.39
22.25
7.00
181.63
CoVan 1
35.40
20.33
14.04
10.84
11.23
17.69
3.00
22:07
30.30
41
16.43
15.94
14.85
22.93
3.00
21.96
CoVan - 10
35.38
20.32
14.04
10.85
11.23
17.90
5.00
33.10
30.28
28.
16.44
15.94
14.85
22.93
5.00
33.53
Covans 10-7
35.38 20:32
10.85
11.23
17.70
7,20
44.79
30:27
28.35 39
16.44
15.94
14.85
7.00
45.04
29

---

Earles-KK
Barkes-IK
70.0
70-
725-
60-
201
Bak
67.5-
37-
Micse
525
Corbol
913
25
AmtonnCat 13X
AmuorsCCtt L3K
AmsonnCall 1SK
100
50
Wikit-11KK
Wikil0a1K
Wik600031K
22-
Park
Preccty
30
MaxrsP103
Whippollo S00K
Wikipeiis TAKTS
WikepelisSSook
Intore $750
50
Pur Roaes
32.
50.0
For
Bakk
82
Coutsy Teen
40
208-
47.
28-
30-
Minsindoo
35
15
30
35
Marro 1463
Cheeagy02
Amnasos-
Aimazoa-6700
42-
40-
Miow
25
Marro P13
Mivin F103
Chenagros
Figure 2: Comparison of the baseline algorithms with the BCA inference with mixed objectives with A 3. The green line shows the results for different interpolations between two measures.
30

---

Bardee
Barkes-
Birkes-KK
1od.a PML
Porkiaer
F105
AmazooCat 1IR
AmusnnCar 13K
2012
37.3
P455
Run
96.0
Regil TeeRoass
50-
82.3
913
$2.5
$6.9
Wikito311K
Wikil&a1K
72-
Look
20
15
MaxrsP103
Wilkpolia-S00K
Wilepwdia-SS0K
WikepelisSS0o
47-
Invese BNC
21-
Macre
Orrdo
23
23
Marro 33
24
25
43
10
30
Moorn
Chergge2
Amuaxc--670t
Amnasos
Ammizs--770
Iatono 9786
Lapk Jar
65
33-
Mess
Cordo
13.5
14.0
14.5
$2.0
12.5
20.5
21.2
22.5
21.0
Miaroo P35
Micen F105
Figure 3: Comparison of the baseline algorithms with the BCA inference with mixed objectives with A 5. The green line shows the results for different interpolations between two measures.
31

---

mixed utility that is linear combination of instance- wise measures and selected macro-measure Here, we present the results for three such mixed utilities (combinations of instance- preenccipreiiiionn with macro-precision, Saccro-l--masunee and coverage):
Y) = (1 a M Instance-P Y, Y) + Cel Macro-P Y, Y)
11C
(UInttanc--P(yp) + a Macro (y:g U:))
j=1
Σ a) + a tj
mgj
j=1
2Y Y)
a V Instance-P p( Y Y) + all MacroFF1 (Y, Y) (1
Σ
a) P + ancr (g..)..)
j=1
= > (1 a) 4 k ]=1
21j
+ m(gj + Pt)
V3 Y) = (1 W Instance Y Y) + a& (Y, Y)
Σ (1 a Inntance- ply, F:5)) + an (V.j. 9:5)
]=1
1 0
(1
a
a
(75)
k
==1
In Figure 2 and Figure we present the plots with results on two combined measures for different values of {0.01, 0.05, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.95, 0.99, 0.995, 0.999). Once again, the presented results are the mean values over 5 runs with different seeds. The plots show that the instance-vs-macn curve has a nice concave shape that dominates simple baselines. In particular, we can initially improve macro-measures significantly with only minor drop in instance-measures, and only if we want to optimize even more strongly for macro-measures, we get larger drops in instance-wise measures. A particularly notable feature of the plug-in approach is that the curves in the figure are cheap to produce since there is no requirement for expensive re-training of the entire easily select optimal interpolation constant according to some criteria, such as a maximum decrease of instance-wist wise performance.
architecture,
E.6 Hardware
The LIGHTXML model was trained on a workstation with single Nvidia Tesla V100 GPU with 32 GB of memory and 64 GB RAM. All the inference strategies were then run on the workstation with 64 GB of RAM. However, to run them, one requires only 16 GB of memory.
32

---

F Efficient inference with Probabilistic Label Trees
In this section, we describe probabilistic labels trees (PLTs) [6]], which allow for efficient retrieval of only the top-k labels with the highest conditional probabilities. Then, we introduce a weighted version and show how to modify it to achieve efficient and exact optimal prediction for any 95( (a)) that is monotonous in My (z:). Thus, if the LPE 17 is modeled by PLT, this provides an alternative to the sparse inference introduced in Appendix D that also scales XMLC problems.
F1 Probabilistic labels trees
We denote a tree by 7. the set of all its nodes by VT, the root node by IT, and the set of its leaves by CT. The leaf I3 E LT corresponds to the label j [m-] The parent node of v is denoted by pa(v). and the set of child nodes by ch(v). The set of leaves of a (sub)tree rooted in node is denoted by L.v. and path from node v to the root by path(v).
A PLT uses tree T to factorize conditional probabilities of labels, 7y (z))) Ply, 1 | [m]. by using the chain rule. Let us define an event that Lv contains at least one relevant label in y. denoting 2v ] 1 Ly yj 1]. Now for every node VT, the conditional probability of containing at least one relevant label is given by:
m7 (x) = P(z, 1 œ
II n(x,v', v'Epath(v)
(76)
where 77( v) P[[z- 1 pp)(v) 1, x]] for non-root nodes, and n( v) P(z, 1 | for the root. Notice that 76 can also be stated recursively as
(xx)) 77 v) (az),
(77)
and that for leaf nodes we get the conditional probabilities of labels
My (x) (x=), for Cr.
(78)
To obtain a PLT, it suffices, for a given T. to train probabilistic classifiers estimating 71æ,, v) for all E VT. Analogously the main paper, we denote estimates of by í).
F22
Weighted PLTs
46
introduced an -s-scarch based algorithm for efficiently finding the leaves with the highest
gain 0(} ..- Wyyy (,))())) where wy E [0, oo) is the weight given to label j. The outline of the search method presented below is an adapted description from [6
For the gain function g(l,. x)- = w wyn (z). the procedure uses a cost function c(lj, x) for each path from the root leaf. Notice that the following holds:
exp (- (-log
log log w Σ log M( v)).
و01و x) = w
(79)
Because exp is monotonous, we can define the following cokt cokt Fulletion for selected label j. which the algorithm will aim to minimize:
oll, x) log w
Σ log f(
logg
(80)
vεpathill)
We can then guide the A search with the function ε(v, x) plv, + hi(, æ)), estimating the value of the optimal path in the subtree of node v, where
p(v, = Σ log (xx
(81)
v'Epath(v)
the cost of reaching tree node v from the root, and
h(v, x = log max Wy JeC.
(82)
is a heuristic function estimating the cost of reaching the best leaf from node The A -earch in procedure evaluates nodes in ascending order of their estimated cost values e(ly.
This approach has been proven by [46 to guarantee that A*-search finds the optimal solution- top-k labels with the highest e(l, ar) and thereby top-k labels with the highest ( the optimally efficient way, i.c., there is no other algorithm used with this heuristic that expands fewer nodes [38]
33

---

Algorithm 9 Select top-k labels with highest gain using PLTs (T, 2t, k, g.)(()))))
I: y 4 0
P Initialize prediction y vector to all zeros b Initialize priority queue Q, ordered descending by g(v, a) b. Calculate estimated conditional probability p(rr, for the tree root Calculate estimated gain g(rr, a)) for the tree root > Add the tree rool with estimates p(rr, æ) and @(rT, ax) to the queue > While the number of predicted labels is less than b Pop the element with the lowest cost from the queue the node is a leaf, set the corresponding label in the prediction vector > If the node is an internal node, for all child nodes P Calculate p(v', x)) Calculate estimate g(V', a)) > Add v', and its estimates p(rr, x) and g(T,, x) to the queue b. Return the prediction vector
2: Q --
3: p(rr,=)= + (T)
4: g(rr,æ) < max (s)(p(r),=))
5: Q.add((rr.p(e p(rr. a). A(r,, =)))
6: while [1 < <k do
7: (..((.)). t 2.pop()
8: v a leaf then S. +
9: else for v' E cc(v)) do
10:
p(v..)) () + p(v,,)miz, v)
11: J(V'x) + max (p(', (v)(((())))) x))) Q.add((V ((V',(('''' p(v (V))))()))))) x)))
12:
13:
return /
E33
PLTs for monotonous gain functions
Notice that in Weighted PLTs instead of minimizing cost, one can directly optimize gain by using a tree-search procedure that evaluates nodes in descending order of their estimated gain g(v, x) p(v, æ²) h(v, 2;), where p(v, 2)) Evepathiv (z v') and h(v, x) maxjec, Wy. To generalize this formulation and apply it to the proposed algorithms, we need to be able to find the top-k with
any gain function 9, (1g (z)) that is monotonous with fly (z).
We can guide the tree search using the estimated gain function J(v. x)
x)). where
plv, x) = II v)),
(83)
v'ppah(iv)
the same in the case of Weighted PLT, it simply corresponds to the conditional probability of finding at least one positive label in the subtree of node v, and the heuristic part is:
h(v, x)
max (g) (p(v,
(84)
JEC.
As in the case of Weighted PLT, we would like to guarantee that this search procedure finds the optimal solution-the the top-k labels with the highest g(l,, .)) To do that, we need to ensure that J(v. x) is admissible, i.e., in case of maximization, it never underestimates the gain from reaching a leaf node (38). We also would like g(v, x) to be consistent, making the proposed tree search procedure optimally efficient, i.e., there is no other algorithm used with the same J(v, æ) that expands fewer nodes 38 Algorithm 9 outlines this procedure for finding the top-k labels with highest values of 9, (n, that is monotonous with n, (z), and that can replace the select top-k(g) operation in the proposed BCA and Greedy algorithms. Unfortunately. not all gain functions gj (7, (z)) can be calculated efficiently. To calculate the semi-empirical quantity ğ exactly, one needs to know all the (xx). To obtain them, the whole tree need to be evaluated, which prevents this method from being efficient. Because of that, we use this technique get exact predictions for the measures that defined solely on f. and q. like macro-precision and coverage.
F.4 Experimental comparison of inference with PLTs
In this experiment, we evaluate the inference using probabilistic label trees that can efficiently perform the exact select (gg) operation. We compare inference times of these variants the methods that require only one pass over the dataset: ToP-K, K, PS-K, Pow-K, LOG-K, MACRO-PA POREED. MACRO- RYRIOR. and COVEREEDS for = {3, 5). As a baseline, we use the same PLT to obtain the k' 100 and k' = 1000 highest x7, and then run the sparse algorithms top of these predictions. We use a modified implementation of PS-PLT 46 17]. trained with default settings.
As in the case of the main experiment, we again observe that the specialized inference strategies are indeed the best on the measure they aim to optimize. Compared to the cost of obtaining marginals for k' = 100 and k' = 1000 labels, which can be later used with one of the proposed inference algorithms (the cost of running this step not included the table), the greedy methods combined with PLT-based search consistently achieve speed-up when compared to
We present the results in Table 10
34

---

Table 10: Results of different inference strategies @k measures with & (3.5) using PLT model. Notation: P-prrecsion, R-recall, FI-FI-measure, Cov- Coverae f-time in seconds, K'=100/1000 1=1000/10000ppeeeee speed-up relative the time required obtain top- 1p-100011000 m)x) for all the instances in X. The green color indicates cells in which the strategy matches the metric. The best results are in bold and the second best in italic.
Tanckppcckap 2'-100
85 2'=100 e'=1000
E'=1000
EURLEX-4K
1000
0.35
PLT
1,00
59.76
12.59
2.12
13,09
13.51
20.41
5.50
K
19.90
13.36
41.19
5.52
2.78
54.85
24,09
2.78
PUJ-PoW-K
62105
19.61
14.37
16.45
43.83
8:00
54.5
53,00
15.62
24.93
8.00
2005
P1 PLS-LOG-K
67.42
19.36
12.87
14.96
40.15
4.35
350
56,70
14.55
22.50
3,0
PLTT PLY-MACRO- Paum
19.68
11.39
25.49
16.05
14.54
57.95
14.00
1.36
1.98
13.56
13.33
28.92
18.09
18.15
61.50
16.74
0.97
1.66
PLT FLT-MACRO- Rouce
$4.53
32.09
24.01
11.72
20.96
$6.38
14.21
1.34
1.96
38.04
56,97
24.76
28.69
23.40
67.90
14.21
1.14
1.96
PLT-COV seae
34.19
19.84
23.80
20.84
18.65
63.11
6.58
2,46
4.22
24.79
23.58
21.10
25.91
18.76
66.88
9.79
1.34
3.16
AMAZONCAT: 13K
TTT 1000
2952.01
0.26
1.00
2952.01
0.26
1.00
PUPTOP--O
708.51
1.00
3.94
708.51
1.00
3.64
PLT K
78.46
59.42
33.15
11:09
14.79
60.97
66.31
11.59
64.52
163.71
74,66
44.40
30.05
33.00
61.00
57.49
8.78
33.74
PLIFPS-K
25.27
59.72
37.09
1300
17.39
46.21
229.04
3.36
12.89
61.30
74.35
30.10
68.12
65.94
75.66
22900
3.36
12.89
PLJE-PoW-K a-6.5
12.30
54.56
41.85
22.84
77-46
60.19
481
1.60
6.13
56.06
16. 13
40.20
601
45.28
84.57
481.55
1.60
6.13
Loc- &
76.15
57.63
37.90
14.01
18.59
47.89
142.18
3.41
20.76
61.44
72.13
48.26
42.91
42.08
72:71
142.08
5.41
20.76
PLTT MACEO- Poums
3.98
2.07
42.12
32.69
20.55
85.07
1135,00
0.68
2.60
2.67
2.30
54.90
34.99
32.50
85.40
1127.85
0.68
2.62
PLTT MACRO Roace
46.83
31.15
34.79
49.93
37.54
79.72
1248.41
0.62
2.56
31,02
33.37
27.85
668.51
33.42
90.17
1248.41
0.62
2.36
PLT-CoVaam
6.20
3.26
29.86
63.04
20.32
89.03
903.45
0.30
3.05
3.96
3.42
24.46
45.22
17.00
91.33
1052.03
0.71
2.73
WIKI-31K
POPTOP-1000 PUP-T09-100
6,58
0.38
638.46
0.38
1.00
2.9.52
1.00
219.52
1.50
PUP-TOP-K
72:30
12.55
1.97
0.48
16.45
14.56
36.81
661.0
10:05
2.58
0.59
1.01
4.91
23.57
9:37
24.97
PUI-PS-K
1:34
100:75
2.38
18:36
2:38
C.5
257.97
11.26
3.24
Pasas
Coveaas
35.13
7.29
18.00
top //' 1000 inference. Unfortunately. they also often slower than k' 100 inference. As showed the previous section, = 100 is usually enough to get good predictive performance on macro measures using BCA and Greedy algorithms. However, here, the PLT-based methods obtain the exact solution for finding the prediction with the highest expected gain. While it is worth noting that tree structure and the type of node estimator have impact the performance of PLT- PLT-based algorithms and we conducted this experiment with just a single setup, we believe that this experiment shows that PLT-based inference, in some cases, be alternative to inference with sparse marginal estimates.
35


Reviews:
[{"review_id": "OqxwgpvQ1c", "reviewer": "Reviewer_4ZEa", "summary": "This paper discusses evaluation metrics to measure the long-tail labels' performance of the extreme multi-label classification (XMLC) problems. The author proposed that macro-average based metrics (e.g., macro-avg Precision/Recall/F1 at k) are more suitable to measure the performance of long-tail labels compared to conventional instance-wised precision/recall at k. The author further discuss how to optimize these metrics on a given test set, with theoretical justification on the objective functions and deviation bounds. The empirical results verified the effectiveness of their proposed optimization methods for the given target metric.", "questions": "**Major Questions**\n- Q1: How does the proposed method relate and connect to other conventional threshold tuning approaches (e.g., [1,2,3])? \n- Q2: How does the proposed method compare empirically to other conventional threshold tuning approaches (e.g., [1,2,3])?\n- Q3: For the block coordinate ascent algorithm, how sensitive is it to the initial point? If it is a non convex function, I suppose the initialization problem matters? Any better heuristic than \"predicting k random labels\" that described at line 185?\n- Q4: For Line 195-198, monotonicity alone is not enough to ensure convergence [4]. Any more thorough/technical statement for the convergence analysis of the proposed block coordinate ascent algorithm?\n\n**Minor issues**\n- In Eq(5), the first summation has index $i$ in the subscript, but not index $i$ seems not being used in the function of $u_w()$. \n- At Line 154: \"the proof is given in Appendix F\". However, it seems to me that the proof appeared in Appendix G (Theorem G.4)?\n\n**Reference**\n- [1] Y. Yang. A Study on Thresholding Strategies for Text Categorization. SIGIR 2001\n- [2] Lewis et al. RCV1: A New Benchmark Collection for Text Categorization Research. JMLR 2004\n- [3] Fan et al. A Study on Threshold Selection for Multi-label Classification. Technical Report 2007\n- [4] https://web.eecs.umich.edu/~fessler/course/600/l/lmono.pdf", "limitations": "To my knowledge, there's no potential negative societal impact for this submission.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Leverage the ETU framework to approximately optimize Macro-average metrics seems novel\n- Theoretical justifications sounds reasonable and technical derivations are solid", "weaknesses": "- Selecting thresholds to optimize Marco-average metrics are not new in multi-label community. The author seems not aware of some  classical/heuristic approaches. For example, the sCut and SCutFBR methods studied in [1,2,3]. The author should also compare these methods in the experiment sections.\n\n**Reference**\n- [1] Y. Yang. A Study on Thresholding Strategies for Text Categorization. SIGIR 2001\n- [2] Lewis et al. RCV1: A New Benchmark Collection for Text Categorization Research. JMLR 2004\n- [3] Fan et al. A Study on Threshold Selection for Multi-label Classification. Technical Report 2007", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the review and questions. We appreciate the hard work. Below we address the main questions:\n\n> *Selecting thresholds to optimize Marco-average metrics are not new in multi-label community. The author seems not aware of some classical/heuristic approaches. For example, the sCut and SCutFBR methods studied in [1,2,3]. The author should also compare these methods in the experiment sections.*\n\n> *Q1: How does the proposed method relate and connect to other conventional threshold tuning approaches (e.g., [1,2,3])?*\n\nWe fully agree with the reviewer that unbudgeted macro-averaged measures are popular in multi-label problems. It is easy to notice that optimization of those metrics boils down to solving $m$ independent binary classification problems. Each such binary problem can be solved using one of two frameworks for optimizing complex performance measures. The methods from the cited papers can be seen as implementation of the optimal strategy for the Population Utility (PU) framework. For the Expected Test Utility (ETU) framework, the exact optimization on a test set for those measures is of quadratic complexity. An approximate solution can be obtained in linear time. For more detailed discussion on PU and ETU frameworks and optimization of macro- and micro-averages in multi-label classification we refer the reviewer to these papers: [4, 5, 6].\n\nIn this paper, we optimize macro-averaged measures with budgeted@k predictions in the ETU framework. This additional constraint is critical in many practical applications of extreme multi-label classification such as recommender systems and search engines. Unlike in the case of unbudgeted metrics, this constraint does not allow us to solve the problem for each label independently, and hence requires more sophisticated treatment. Therefore, our considerations are novel and not trivial.\n\n---\n\n> *Q2: How does the proposed method compare empirically to other conventional threshold tuning approaches (e.g., [1,2,3])?*\n\nThe conventional thresholding methods do not have the restriction on the number of predicted labels. Therefore, a direct comparison of these approaches is not straight-forward. Moreover, the conventional thresholding methods are designed for the PU framework. For ETU without the budgeted predictions, one would rather use different algorithms to find the threshold. For a detailed discussion please refer to [4].\n\n**References for Q1 and Q2:**\n1. Y. Yang. A Study on Thresholding Strategies for Text Categorization. SIGIR 2001\n2. Lewis et al. RCV1: A New Benchmark Collection for Text Categorization Research. JMLR 2004\n3. Fan et al. A Study on Threshold Selection for Multi-label Classification. Technical Report 2007\n4. Dembczynski et al.: Consistency analysis for binary classification revisited. ICML 2017.\n5. Koyejo et al.: Consistent Multilabel Classification. NeurIPS 2015.\n6. Kotłowski, Dembczyński: Surrogate regret bounds for generalized classification performance metrics. Machine Learning 2017.\n\n---\n\n> *Q3: For the block coordinate ascent algorithm, how sensitive is it to the initial point? If it is a non convex function, I suppose the initialization problem matters? Any better heuristic than \"predicting k random labels\" that described at line 185?*\n\nIn addition to predicting $k$ random labels as the initial point, we also tested top-$k$ labels with the highest marginals $\\eta$. Both initialization methods gave very similar final results in all cases, so we omitted this experiment in the submitted paper. Also, please note that all the experiments were repeated 5 times with different random initial points. We reported the standard deviation in Tables 6 and 7. In most cases, the deviation is no more than 0.1%.\n\n---\n\n> *Q4: For Line 195-198, monotonicity alone is not enough to ensure convergence. Any more thorough/technical statement for the convergence analysis of the proposed block coordinate ascent algorithm?*\n\nWe thank for this interesting comment. For metrics taking values in a bounded range and $\\epsilon > 0$, the algorithm can only make up to $O(1/\\epsilon)$ steps in the `while’ loop, as each step must decrease the objective by at least $\\epsilon$. However, even when $\\epsilon=0$, the algorithm terminates after a finite number of steps. This is because each step must strictly decrease the objective (otherwise, the algorithm terminates), which is only possible if the algorithm changes at least one prediction (from 0 to 1 or the other way around) among all instances and labels in that step. Since the number of possible predictions is finite (precisely, $\\binom{m}{k}^n$), this guarantees that the algorithm will stop after a finite number of steps.\n\nIn practice, despite small $\\epsilon$, the algorithm usually terminates after a few iterations (in the worst observed cases, it was a few tens of iterations). In Tables 6 and 7 in the Appendix, one can observe that the Greedy variant (one-pass algorithm) obtains good results in most cases, and based on that, larger improvements than $\\epsilon$ are expected.\n\nIn Table 1 in the PDF attached to the global response, we also present the number of iterations and CPU time that was used for our inference procedures.\n\n---\n\n**Minor issues**\n\nWe thank for pointing out the typographical issues. We will correct them in the final version of the paper.\n"}, {"review_id": "cXEb8220uW", "reviewer": "Reviewer_ELgR", "summary": "This paper critiques that the existing extreme classification evaluation metrics don't give the complete picture with respect to all labels (more specifically performance on head labels overpowers performance on tail labels), hence it recommends using macro-averaged metrics which are more favorable to tail labels. The authors use expected test utility framework to come up with BCA based methods to get modified prediction rules given a prediction matrix from a trained XMC model. Experiments on benchmark datasets indicate that just taking the top-k predictions is not ideal for marco averaged metrics and the proposed approach performs significantly better.", "questions": "is it possible to optimize for a weighted combination of standard precision and macro precision, so that we can smoothly interpolate between these two metrics?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The proposed approach works as a plugin method that can be used with any existing XMC method without any need for retraining\n- Proposed approach is well reasoned\n- Approximate versions scalable to large datasets without the need for specialized hardware ", "weaknesses": "- Not sure how important are macro measures for evaluating performance on XMC datasets as the data imbalance is inherent to XMC applications and in most scenarios we do want to mimic this imbalance in model predictions as well (for e.g. in ad recommendation problem with a billion ads in corpus, certain products are popular, so giving equal weightage to each product during evaluation might not be very useful). I agree that we do want to improve quality of predictions on tail labels as well but not at the cost of making worse overall predictions. Results indicate that trying to do well on macro-averaged metrics heavily impacts the performance on standard metrics which is not desirable.\n- Section 4 is a bit hard to follow\n\nMinor typo:\nline 82, \"c11 to true negatives.\" -> \"c11 to true positives.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the review and questions. We appreciate the hard work. Below we address the main questions:\n\n**Regarding the importance of macro measures for evaluating performance on XMC datasets as the data imbalance and a trade-off between performance on standard metrics and macro-averaged metrics.**\n\nWe think it is a serious problem if a model only manages to get *at least one* true positive on about 25% of all labels (as suggested by the coverage results in Table 2). Ideally, we would like to improve the performance on tail labels without sacrificing too much performance on head labels. This naturally leads to the question the reviewer has posed whether it is possible to interpolate between the instance and macro metrics to find a better trade-off. The answer is yes, and there are actually two ways this can be achieved.\n\nThe first is a straight-forward interpolation, as instance-wise precision-at-k is covered by our framework, and our class of utility functions is closed under linear combinations. Such an objective can be optimized by the proposed block-coordinate algorithm without any modification. In the PDF attached to the general response, we present plots with a result of the optimization of two following objectives with different values of $\\alpha$:\n\n$\\Psi(\\mathbf{Y}, \\mathbf{\\hat Y}) = (1 - \\alpha) \\times \\text{Instance-P}@k(\\mathbf{Y}, \\mathbf{\\hat Y}) + \\alpha \\times \\text{Macro-P}@k(\\mathbf{Y}, \\mathbf{\\hat Y})$\n\nand\n\n$\\Psi(\\mathbf{Y}, \\mathbf{\\hat Y}) = (1 - \\alpha) \\times \\text{Instance-P}@k(\\mathbf{Y}, \\mathbf{\\hat Y}) + \\alpha \\times \\text{Macro-F1}@k(\\mathbf{Y}, \\mathbf{\\hat Y})$.\n\nThe plots show that the instance-vs-macro curve has a nice concave shape that dominates simple baselines. In particular, we can initially improve macro-measures significantly with only a minor drop in instance-measures, and only if we want to optimize even more strongly for macro-measures we do get larger drops in instance-wise measures. A particularly notable feature of the plug-in approach is that the curves in the figure are cheap to produce since there is no requirement for expensive re-training of the entire architecture, so one can easily select an optimal interpolation constant according to some criteria, such as a maximum decrease of instance-wise performance.\n\nSecond, we note that our framework admits using different binary measures for each label. The most simple way to exploit this is to use a weighted macro-average, giving more weight to head labels. We have actually employed this in the paper, in the sense that instance-wise precision-at-k is just macro-precision-at-k with a 1/prior weighting for the different labels. Parametrizing the exponent $(1/\\text{prior}^\\beta)$ allows for a different way of interpolation to standard macro-averages, which are realized by beta=0. The results for beta=1/2 are presented in Table 2.\n\n---\n\n> *Section 4 is a bit hard to follow*\n\nWe thank for the suggestion. We will definitely try to improve the clarity of this section in the next version using additional space (if the reviewer has some more specific suggestions, we will be glad to hear them).\n"}, {"review_id": "v4Zz1HrS7A", "reviewer": "Reviewer_4FGQ", "summary": "In this paper, the authors studies the evaluation metrics for the long tailed extreme multilabel classification problems. Compared with existing heuristics, such as PSP, they formulate the metrics in the expected test utility framework. Inference rules are derived to obtain optimal metrics. Approximations are construct for the metrics that are difficult to compute.", "questions": "Inference with a global budget k is easy to implement but not always optimal in terms of utility-budget trade-off. If there's no top-k constraint, how can we design the metrics/inference rules to determine the number of predictions for each instance?", "limitations": "It would be great to see the complexity analysis of the optimal prediction rules to understand the inference overhead.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper picks an interesting but not well studied direction and gives thorough study with reliable derivations and proofs. It is well known that the existing metrics for XMC problems cannot measure the performance on tail labels because of the data distribution. I agree with the authors that the widely used proensity scores are heuristics that are not to be used as metrics, especially it requires hyper-parameters which would introduce much consistency issues when used for comparison. The authors express the metrics in the ETU framework thus unifying the existing and potential metrics.\n\nThe paper gives detailed derivations for the optimal prediction rules for each of the derived metrics and provides cheap and easily applicable approximations for metrics that are hard to compute. Empirical results on 4 public XMC benchmark datasets indicates that the optimal rules can actually obtain the best score for the corresponding metrics.", "weaknesses": "The paper is overall well presented but some of the terms are used without introducing/explaining, such as \"macro-average\".\n\nMinor:\n* Line 82: $C_{11}$ to true positives", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the review and questions. We appreciate the hard work. Below we address the main questions.\n\n> *Inference with a global budget k is easy to implement but not always optimal in terms of utility-budget trade-off. If there's no top-k constraint, how can we design the metrics/inference rules to determine the number of predictions for each instance?*\n\nWe are not entirely sure what the reviewer is asking for. We would appreciate additional clarification if possible. \n\nWe agree that the global budget of $k \\times n$ labels, with $n$ being the number of test examples, could be an alternative definition of the problem. However, it would be suited to different applications than our formulation. In such a case, the optimization procedure would determine the number of predicted labels per instance.  Let us also notice that by using unbudgeted metrics like Hamming loss or the standard macro-averaged F-measure one naturally obtains a varying number of predictions per instance. \n\n---\n\n> *It would be great to see the complexity analysis of the optimal prediction rules to understand the inference overhead.*\n\nWe discuss the complexity in Section 6 of our paper. One iteration of the proposed block coordinate algorithm, assuming we have a non-sparse matrix of estimates of $\\eta$, has time complexity of $O(n(m \\log k))$ and space complexity of $O(nm).\n\nThis can be improved by short-listing using a sparse matrix of $\\eta$s with only $k’$ non-zero elements per row, resulting in $O(n(k ′ \\log k))$ time and $O(n(k ′ + k))$ space complexity. The important question is then how many iterations the algorithm runs before terminating. We also answer this question in response to Reviewer 4ZEa. For metrics taking values in a bounded range and $\\epsilon > 0$, the algorithm can only make up to $O(1/\\epsilon)$ steps in the `while’ loop, as each step must decrease the objective by at least $\\epsilon$. However, even when $\\epsilon=0$, the algorithm terminates after a finite number of steps. \n\nIn practice, despite small $\\epsilon$, the algorithm usually terminates after a few iterations (in the worst observed cases, it was a few tens of iterations). In Table 1 in the PDF attached to the global response, we also present the number of iterations and CPU time that was used for our inference procedures.\n"}, {"review_id": "WP5dttnLXJ", "reviewer": "Reviewer_UXPM", "summary": "This paper analyzes generalized metrics budgeted “at k” by formulating it in the expected test utility (ETU) framework. They derive optimal prediction rules and construct their computationally efficient approximations with provable regret guarantees and being robust against model misspecification. ", "questions": "Table 1 shows that the macro measures are suitable for long tails experimentally. Would you please explain the reason for it in theory?", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper is sound and clearly written.", "weaknesses": "Limited contribution:\n\nThe paper investigates optimal solutions for the class of utility functions that can be linearly decomposed over labels into binary utilities. Is it possible to extend this method to a more broad class of utility functions.\n\nThe algorithm block coordinate ascent looks not new to me.\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the review and questions. We appreciate the hard work. Below we address the main concerns.\n\n**Regarding the extensibility of the proposed approach**\n\nWe first want to stress that the class of linearly decomposable into labels functions studied in this paper is already quite general, including standard instance-wise measures (at k) like precision, Hamming loss, weighted instance-wise losses such as PSP, as well as macro measures with arbitrary binary loss function as basis (ref. Table). Further, linear combinations of these utilities are permitted (see our answer to Reviewer ELgR).\n\nThe first challenge in extensibility is that a crucial feature of the investigated loss functions is that they can be optimized using only marginal label probabilities $\\eta_i(x) = P[Y_i=1 | X]$. This is important for the plug-in approach, as estimating the full joint distribution of labels is intractable. This still leaves some design space for generalizations, foremost probably replacing the arithmetic mean in the macro-average with a more general aggregation function. We haven't investigated these options, but if the reviewer has a concrete example of a loss function in mind, we would be happy to discuss it.\n\n---\n\n> *Table 1 shows that the macro measures are suitable for long tails experimentally. Would you please explain the reason for it in theory?*\n\nPlease note that we do not claim that *all* macro-averages are long-tail metrics, e.g., macro-average Hamming loss is equivalent to instance-wise Hamming loss, and thus not more tail-adapted. The main claim of Table 1 is that typical instance-wise loss functions are almost invariant under the removal of a large portion of tail labels, whereas there exist macro metrics that are sensitive to this operation. There is no \"first principles\" theoretical explanation for why macro-averages are good for measuring tail-performance. We can give a partial explanation as follows:\n\nAssume that the binary utility over which we take the macro-average has range [0, 1], and it is zero if there is no true positive in the prediction. If we have m labels in total, of which m' are tail labels, then removing the entire tail means that the binary utility on all these m' labels is zero, and the overall macro-average is upper-bounded by 1 - m'/m. This is not true for popular instance-wise measures such as Precision@k.\n"}, {"review_id": "TiyNyxcIu5", "reviewer": "Reviewer_m6Nv", "summary": "This paper focuses on the long-tail problem in extreme multi-label classification. To address this problem,  the authors propose a new method to optimize performance metrics for extreme multi-label tasks via the expected test utility (ETU) framework. Experimental and theoretical results are also provided.", "questions": "1. There are also some other works that focus on the long-tailed multi-label classification tasks, instead of directly optimizing the performance metrics, how about the performance of these works?", "limitations": "N/A", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The long-tail problem in the extreme multi-label classification task is important. It is good to explore how to fairly evaluate the performance of multi-label learning algorithms on tail labels.\n2. The proposal is technically sound. Directly optimizing performance measures for tail labels is make sense.", "weaknesses": "The main concern about the paper is the experiments. There are also some other novel algorithms that are proposed for the long-tail problem in multi-label classification tasks and can achieve good performance, but the authors did not compare with these studies in the experiments.\n\nMoreover, there are some minor issues, such as the related works should be discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the review and questions. We appreciate the hard work. Below we address the main question.\n\nIn contrast to many works in extreme classification, which are mainly algorithmic and aimed to obtain \"better\" performance on tail-labels with existing metrics, our work mainly focuses on the performance metric itself. Through Table 1 of the paper, we argue that the prevalent instance-based measures, such as P@k and PSP@k, used by the community, are largely insensitive to the removal of a large fraction of tail-labels. We speculate that the novel algorithms mentioned by the reviewer would not help much in this regard, as the existing metrics are mainly focusing on head labels.  \n\nFurthermore, we would like to highlight the comments by reviewer 4FGQ : \"It is well known that the existing metrics for XMC problems cannot measure the performance on tail labels because of the data distribution. I agree with the authors that the widely used propensity scores are heuristics that are not to be used as metrics, especially it requires hyper-parameters which would introduce much consistency issues when used for comparison. The authors express the metrics in the ETU framework, thus unifying the existing and potential metrics.\" In other words, a direct algorithm-to-algorithm comparison on existing metrics would be misleading. The comparison on the budgeted@k macro-measure could also be challenging as the mentioned algorithms would need to be tailored for predicting top-$k$ labels. \n\nIn our work we are (i) investigating some shortcomings of the existing metrics, (ii) proposing alternatives based on macro-measures for budgeted@k predictions, and (iii) introducing algorithms to optimize them based on a plug-in approach assuming access to an estimator for conditional label probabilities $\\eta$. The algorithms mentioned by the reviewer might be useful in improving the estimates of $\\eta$s. This is an interesting question, but beyond the scope of this paper. Nevertheless, we would appreciate if the reviewer would explicitly say which algorithms she/he has in mind."}]

Author rebuttal:
We thank the reviewers for their thorough comments and questions. We answer them in specific responses to the reviewers. We use the global comment to attach a PDF with additional plots containing results for “meta-measures” that combine instance and macro-averaged measures. These plots have been prepared as a part of the response to Reviewer ELgR. A detailed response has been given in the specific response to this Reviewer. In the PDF, we also include a table with the running time and the number of iterations of the proposed inference method in addition to the response to Reviewer 4ZEa and 4FGQ.

Meta-review: Reviewers were unanimously supportive of this paper, which provides a set of new top-k metrics for better capturing performance of multi-label classifiers on tail labels. This is supplemented with rigorous theory and solid experimental results. In all, this work should be of broad interest to the community.
Decision: Accept (poster)