Generalized test utilities for long-tail performance in extreme multi-label classification

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.

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. 2. 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. Moreover, there are some minor issues, such as the related works should be discussed.

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?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

N/A

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.

Strengths

This paper is sound and clearly written.

Weaknesses

Limited contribution: The 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. The algorithm block coordinate ascent looks not new to me.

Questions

Table 1 shows that the macro measures are suitable for long tails experimentally. Would you please explain the reason for it in theory?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Yes.

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.

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. The 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". Minor: * Line 82: $C_{11}$ to true positives

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?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

It would be great to see the complexity analysis of the optimal prediction rules to understand the inference overhead.

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.

Strengths

- The proposed approach works as a plugin method that can be used with any existing XMC method without any need for retraining - Proposed approach is well reasoned - 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. - Section 4 is a bit hard to follow Minor typo: line 82, "c11 to true negatives." -> "c11 to true positives."

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?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

Yes

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.

Strengths

- Leverage the ETU framework to approximately optimize Macro-average metrics seems novel - 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. **Reference** - [1] Y. Yang. A Study on Thresholding Strategies for Text Categorization. SIGIR 2001 - [2] Lewis et al. RCV1: A New Benchmark Collection for Text Categorization Research. JMLR 2004 - [3] Fan et al. A Study on Threshold Selection for Multi-label Classification. Technical Report 2007

Questions

**Major Questions** - Q1: How does the proposed method relate and connect to other conventional threshold tuning approaches (e.g., [1,2,3])? - Q2: How does the proposed method compare empirically to other conventional threshold tuning approaches (e.g., [1,2,3])? - 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? - 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? **Minor issues** - 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()$. - 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)? **Reference** - [1] Y. Yang. A Study on Thresholding Strategies for Text Categorization. SIGIR 2001 - [2] Lewis et al. RCV1: A New Benchmark Collection for Text Categorization Research. JMLR 2004 - [3] Fan et al. A Study on Threshold Selection for Multi-label Classification. Technical Report 2007 - [4] https://web.eecs.umich.edu/~fessler/course/600/l/lmono.pdf

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

To my knowledge, there's no potential negative societal impact for this submission.