Consistent algorithms for multi-label classification with macro-at-$k$ metrics

We sincerely thank the reviewer for the insightful review. We appreciate the hard work. Below, we address the main questions and concerns:

For instance, the first main result in Theorem 4.1. Just looking at the constants a_j and b_j, one can see, not surprisingly, that these are the same constants one would see for weighted binary classification problems, see Lemma 2 of https://www.jmlr.org/papers/volume18/15-226/15-226.pdf (of course, there's no top-k notion here in binary classification). It would be good to draw these connections, position the main results in the context of known results, and tease apart new observations and insights.

The cost-sensitive binary classification is indeed a special case of our linear metric setup with a single label, which is why these constants turn out to be the same. In our work, we choose top-$k$ labels with respect to a linear transformation of marginals, while in binary classification a single label is selected whenever that linear transformation of class conditional probability is non-negative. Having said that, we agree that we should make a better connection between the results presented in our paper and known results.

Similarly, with respect to, Theorem 4.4, it would be good to see some form of the result, say special cases, that can be dotted lined to known results for multi-label problems.

The easiest special case are linear/weighted measures, i.e., $\Psi(\mathbf{C}) = \mathbf{L} \cdot \mathbf{C} + d$. In that case, $\nabla \Psi = \mathbf{L}$, so the statement reduces to the trivial claim that any $\mathbf{C}$ maximizing $\mathbf{L} \cdot \mathbf{C}$ also maximizes $\mathbf{L} \cdot \mathbf{C} + d$.

For a more interesting case, consider macro-recall: Here,

and

Thus, the theorem claims that one needs to optimize the linear measure

Note that, in fact, for any given problem, $C^j_{10} + C^j_{11} = \pi_j$ is a constant, so we can simplify the expression:

As macro-recall is formulated as a loss function, our goal is to minimize the expression above. As $\pi_j^{-1} C^{\star j}\_{11}$ is a constant, the optimization objective becomes

Thus, this recovers the solution for optimizing macro-recall.

It's nice to see the consistency between Macro-R_prior and Macro-R_FW in the experiments for the recall metric. Did the authors also experiment with balanced accuracy in the experiments, where the closed form solution is also easy to compute?

We have performed such an experiment, and we can confirm that the proposed Frank-Wolfe algorithm (Macro-BA$\_{FW}$) also recovers the optimal analytical solution for Balanced Accuracy obtained directly from label priors (Macro-BA$_{PRIOR}$). We present the results below, showing that both approaches get almost the same performance.

Mediamill:

Flickr:

RCV1x:

AmazonCat:

Regarding ethical concerns (comparison to Wang et al)

We thank the reviewer for bringing this work to our attention. We were not aware of it (if not wrong, it was not published in a peer-reviewed venue or journal). After reading it, we see substantial differences from our submission.

The reviewer is correct that this paper does look similar to ours. However, this is not surprising; both papers are different extensions of earlier works, such as Narasimhan et al. We tried to clearly indicate in our submission that it is based on this line of work. Below we discuss the differences between our paper and Wang et al.

That paper considers multi-output classifiers with $K$ classes in each output, and makes $M$ such outputs, which is conceptually quite different from at-$k$ prediction considered in our paper. This can already be seen in the respective definitions of the confusion tensor: In our case, it is an $m \times 2 \times 2$ object, and in the other paper, it is an $M \times K \times K$ object.

In case of multi-output classification, each of the outputs chooses a class independently of the other. Of course, an $m$-label multilabel problem can be considered as a multi-output problem, with $K=2$ and $M=m$. In that case, though, the setting of Wang et al. does not contain the at-$k$ constraint, which is what makes this problem really challenging.

On a technical side, our formulation of the theoretical results and our proof techniques are different (as a side note, their proof of the compactness of the feasible confusion set is incorrect as it falsely assumes the space of bounded functions to be compact).

On the basis of the above arguments, we hope that we have assured the reviewer that we do not plagiarize any other work. Nevertheless, we admit that paper of Weng et al. is related to our submission and we should cite it.

We sincerely thank the reviewer for the review. We appreciate the hard work. Below, we address the question and concern:

The theoretical results could be accompanied by an intuition to ease understanding of the results.

We thank the reviewer for the suggestion; we will try to incorporate more intuitions in the next revision. If the reviewer has specific suggestions regarding which results would benefit the most from them, we would be happy to focus on these parts.

A comparison to something like binary relevance learning treating each label independently for demonstrating also empirically that these measures cannot be sufficiently tackled by such an approach would be desirable.

For metrics for which macro averages can be written in a linear form (see page 5), the optimal solution can also be obtained by binary relevance-like approaches. In the experiments, we explicitly include methods (e.g., Top-K, Macro-R$_{\text{PRIOR}}$) of this type. In the general case, binary relevance methods do not lead to the optimal solution, as discussed in Appendix E.

In https://doi.org/10.1007/s10994-021-06107-2 an @k metric interpolating between Hamming and subset 0/1 loss is presented. To what extent would this relate to the considered @k-metrics in this paper?

While the Hamming loss is a part of the framework we consider in our work, the 0/1 loss is not, as it cannot be represented as a function of the confusion tensor we use. That also applies to the family of losses introduced by Hüllermeier et al. 2022, which are a generalization of these two losses. Therefore, we cannot consider them in our framework.

minor: p. 4 "define in Table 1" p. 7 "tensor measure measure"

We thank the reviewer for noticing and letting us know.

The key difference between the approach of Hüllermeier et al. and ours is that the former measures performance jointly on each instance, while we focus on macro-averages.

In our work, $k$ is a strict requirement on the number of predicted positive labels per instance. In case of the other work, $k$ is a parameter of a loss function that indicates the minimal size of correctly predicted subsets of labels for an instance that will be rewarded by the loss function. It does not limit in any way the number of predicted positive labels.

To see the difference, consider $k = 1$. In our case, we will predict only one label per instance. The Bayes classifier will be a label with the highest value of the linear transformation of the label marginal (with parameters $\mathbf{a}$ and $\mathbf{b}$ depending on the base loss function and data distribution). In case of Hüllermeier et al., $k=1$ leads to the standard Hamming loss without any restriction on the number of predicted labels. The optimal prediction is then a set of labels with marginal probabilities being greater than (or equal) 0.5.

We sincerely thank the reviewer for the review. We appreciate the hard work. Below, we address the questions:

From the results of Table 2, the proposed method seems to greatly sacrifice instance-wise metrics to trade for gains in macro-average metrics. Is it possible for the proposed method to optimize a interpolated version of the objective that flexibly control the performance tradeoff between instance-wise metrics and macro-averaged metrics?

Yes, it is possible to optimize a measure that interpolates between instance-wise metric and macro-metric as long as the resulting objective is a function of confusion tensor $\mathbf{C}$ and ideally meets all assumptions required by the Frank Wolfe procedure. Such objective is, for example, a linear interpolation between instance-precision@k and macro-f1@k:

Below, we link to the image presenting plots for two datasets, Mediamill and Flickr. The results show that, in this case, 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 small drop in instance-measures. We will include this discussion and more results in the appendix.

Plots: https://i.imgur.com/LJTTxyq.png

Some baseline methods that claim to also perform good on tail-labels are not discussed in related work, or compared in the experiment section. For example [1] and [2], to name just a few.

In the paper, we included a comparison with some popular techniques that are domain-agnostic. However, we will be happy to include a comparison with more methods of that type if the reviewer has some particular in mind. Regarding the ones already mentioned by the reviewer:

• [1] considers multi-class ($y \in [m]$) setting, while in this work we consider multi-label ($\mathbf{y} \in \\{0,1\\}^m$) setting. Post-hoc logit adjustment presented in Section 4 of [1] is the simple weighting by the inverse of priors, which we also use in experiments (denoted as $\textrm{Macro-R}_{\text{PRIOR}}$).

• [2] heavily relies on the problem domain (textual data) and cannot be applied to all datasets we consider. Please also note that the approach proposed in our submission can be used on top of any method aiming at improving the probability estimates of tail labels. We will try to highlight it more in the revised version of the paper.

To improve the clarity of the proposed methods, the author may consider a toy synthetic dataset where data distributions are known, and show derivations of the proposed method, and verify the consistency property through simulations.

We thank the reviewer for the suggestion! We will add an experiment on synthetic data to improve the presentation of our paper.

This submission also seems highly related to [3]. The author should discuss what's the difference, and compare it empirically.

Our submission and paper [3] look at the same problem setup, but using two different optimization frameworks. The latter follows the Expected Test Utility (ETU) framework where one assumes a given fixed test set $\boldsymbol{X}$ and then tries to predict the corresponding labels $\boldsymbol{Y}$. This has important consequences, both theoretical and practical.

From a theoretical perspective, by having a fixed test set, the optimal classifier is always deterministic, and one essentially solves a discrete optimization problem over the space of all at-$k$ predictions. As this becomes computationally intractable except for trivial cases, [3] needs to make an approximation, actually optimizing $\Psi(\mathbb{E}[\mathbf{C}(\boldsymbol{Y}, \hat{\boldsymbol{Y}}) \mid \boldsymbol{X}])$ instead of the actual ETU objective, $\mathbb{E}[\Psi(\mathbf{C}(\boldsymbol{Y}, \hat{\boldsymbol{Y}})) \mid \boldsymbol{X}]$. This objective is then minimized using a block-coordinate-ascent algorithm.

In contrast, the Population Utility (PU) framework adopted in this work means we are looking for (potentially stochastic) classifiers $\boldsymbol{h}$ that work on the level of a single instance. Thus, we want to optimize $\Psi(\mathbb{E}[\mathbf{C}(\boldsymbol{y}, \boldsymbol{h}(\boldsymbol{x}))])$. While this resembles the approximation above, there are important differences. Firstly, the expectation is no longer conditioned on the test set $\boldsymbol{X}$. Secondly, instead of matrices, $\boldsymbol{Y}$ and $\boldsymbol{X}$, we now only need vectors $\boldsymbol{y}$ and $\boldsymbol{x}$, as the expectation is taken over single instances.

From a practical point of view, this means that the PU-classifier introduced in this paper can be employed in an online inference setting, where queries are presented one-by-one, instead of being in one large batch. In contrast, if you apply the ETU algorithm [3] in online inference, i.e., independently apply to test sets of size 1, it degenerates back to the top-k prediction. However, when evaluating on a given test set, the ETU solution can play its strengths, since it is possible to exploit the actual instances present in the test set, which PU cannot do. Thus, when using the same label probability estimator $\boldsymbol{\eta}$, we generally expect ETU to perform better than PU.

To illustrate our expectation empirically, we present below the results obtained for the Flickr data set (the method introduced in [3] is denoted in the table below with $_{BCA}$ subscript).

Flickr:

We sincerely thank the reviewer for the insightful review. We appreciate the hard work. Below, we address the main questions and concerns:

It lacks (...) the discussion which of proposed metrics and macro-at-k approach should be chosen for different problems from practitioners perspectives

What would be the conclusions or "rule of thumb" of selecting particular heuristics from the practitioners' point of view for certain applications or multi-label classification problem?

The basic heuristics might be more robust than the FW method in the case of datasets with very long tails and a very small number of positive instances. In this case, simplicity might be preferred over the sophisticated optimization procedure (which is the general rule of thumb in statistics and machine learning). Nevertheless, we believe that by improving the probability estimation for long tail labels (what we do not discuss in this paper), we should also get a more stable and better performance of the FW method.

Regarding the metrics, macro-averaging treats all the labels equally important. This prevents ignoring tail labels (when used with an imbalance-sensitive binary loss). The budget of $k$ predictions requires the prediction algorithm to choose the labels “wisely.” The choice of the base metric (e.g., precision, recall, F-measure, etc.) depends on a given application, exactly in the same way as in the case of binary classification applications. For example, suppose a user wants to cover as many as possible relevant labels. In that case, they should use recall, but in our setting, the budget per each instance is precisely defined and recall for each label has the same importance.