Cardinality-Aware Set Prediction and Top-$k$ Classification

Summary

This paper proposes a method to handle cardinality-aware top-k classification. It designs an optimization problem where the cardinality of set selectors is also considered. The authors then generalize it to two types of surrogate losses. Given certain assumptions on the hypothesis set H, the authors theoretically justify their method. **I must say I am no expert on this domain, so the AC must take my comments wisely.**

Strengths

This paper tackles a very important problem. And achieves, according to my view, a very nice result. The authors manage to transfer the cardinality-aware term into surrogate terms, and theoretically demonstrate their sub-optimal properties. This paper is also very well written.

Weaknesses

No error bar, very limited evaluation, very strong assumption on the hypothesis set, which is usually not easy to achieve in practice.

Questions

In some cases, like those generative modeling questions, the cardinality of predictors may be evaluated by measure, meaning the true answer assembles a region of infinite points. Can your method apply to those scenarios where the cardinality is evaluated by measures?

Rating

8

Confidence

2

Soundness

3

Presentation

4

Contribution

4

Limitations

As said in weakness.

Summary

This paper introduces a new loss function for top-k set prediction where k may vary as a function of the input, which the authors call cardinality-aware top-k classification. However, this loss is intractable to optimize in all but trivial cases, so the authors introduce surrogate loss functions for learning these cardinality-aware set predictors, and provide a theoretical analysis of these surrogate losses. The paper also explores the proposed algorithms empirically, on benchmark computer vision datasets.

Strengths

- The contribution seems novel -- the authors identify a new type of prediction problem in which top-k sets of input-varying size can be predicted. - The introduction of two new surrogate loss functions for optimizing the proposed (but intractable) cardinality-aware top-k loss seems to be a good contribution. - Empirically, the authors show on benchmark datasets that by giving up control over specific cardinalities, their top-k predictors can outperform existing top-k predictors that prescribe specific cardinalities a priori.

Weaknesses

- It isn't immediately clear why the cost-constrained surrogate loss is tractable to optimize, while the original (non-surrogate) loss is intractable. Please clarify this in the text. - (clarity of the abstract) The abstract should elaborate on H-consistency and the types of losses being introduced, or discuss these at a higher level. Without knowing what these are prior to reading the abstract, the significance of these is unclear. - The usage of the term "accuracy" in Figure 1 is strange, as the actual "accuracy" definitions vary slightly between the two methods being compared. Additionally, the expected cardinality is used, which makes the comparison strange. Furthermore, this comparison on four benchmark computer vision datasets makes up the bulk of the experimental results. The experimental results section could be additionally strengthened by analyzing other aspects of the predictors generated by the authors' framework, such as the distribution of cardinalities, whether or not harder examples indeed correspond to higher cardinality, the top-k accuracy scores of worst-case cardinalities and best-case cardinalities, and so on. - The value of Figure 2 is unclear. What is the significance of making the cost function linear?

Questions

- Out of curiosity, have the authors considered simpler techniques for cardinality-varying top-k prediction, such as setting a total probability threshold on prediction probabilities, and returns the top-k that maximizes the probability, subject to the threshold? At least empirically, it seems like simpler techniques such as this one should be included as a baseline. - Is it in fact the case that for "harder" examples, the top-k cardinality of the predictions are larger in this framework? Have the authors explored this empirically? Examples of this would strengthen the argument for this new type of prediction.

Rating

4

Confidence

2

Soundness

3

Presentation

2

Contribution

2

Limitations

The authors discuss limitations.

Summary

The paper introduced a new cardinality-aware set prediction algorithm with cost-sensitive comp-sum and constrained surrogate losses. Additionally, the paper established theoretical guarantees for top-k classification with fixed cardinality k using the H-consistency bounds. Finally, experiments on linear classifiers show the superiority of their algorithms.

Strengths

1. The paper is presented clearly and is easy to follow. 2. The paper considers the set prediction, which is a novel setting in recent years. 3. The paper proposes new algorithms with rigorous guarantees and good performance on various datasets.

Weaknesses

1. Since the theoretical results include the neural network class as a special case, the experiments should additionally consider training whole neural networks on the mentioned datasets (at least CIFAR), which is more important in practice.

Questions

1. Can we estimate the $M$ in H-consistency bounds? 2. Authors claim the framework includes the standard conformal prediction, so do some relationships exist between the H-consistency bounds and coverage bounds?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors have adequately discussed the limitations.

re

Good work. Please give me a short summary of your new analysis regarding the question before the due date. I have raised the score to 8.