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

Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.

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

Response: We will include error bars in the final version, which show minimal variability and do not impact the demonstrated superiority of our cardinality-aware algorithms. We will also follow Reviewer 5ki4's suggestions to provide a more comprehensive experimental analysis of various aspects of our cardinality-aware algorithms in the final version. In the global response, we have included two additional experimental results related to this analysis. The assumptions of symmetry and completeness in Section 4.3 can be met by common hypothesis sets, including classes of linear models and multilayer feedforward neural networks typically used in practice. Note that these assumptions are made on the hypothesis set $\mathcal{R}$ of the cardinality selector, which we can choose ourselves. We impose no specific assumptions about the hypothesis set of base classifiers $h$ used in our cardinality-aware algorithms, which can be any practical hypothesis set used for various tasks.

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?

Response: That's a great question. Our method can indeed be applied to those scenarios as well, where the corresponding measure—rather than standard cardinality—is taken into account in the cost function. Our analysis is general and makes no assumptions about costs, which provides flexibility in choosing costs adapted to different cases, including the one the reviewer pointed out. We will elaborate on this in the final version.

Thank you for your thoughtful feedback and suggestions. We will take them all into account when preparing the final version. Below please find responses to specific questions.

Weaknesses:

1. 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.

Response: The original loss comprises indicator functions, which are discrete and non-continuous, making them difficult to optimize. In contrast, the cost-sensitive surrogate loss is continuous, smooth, and differentiable, which makes it tractable for optimization. This is analogous to how the zero-one loss is intractable to optimize in standard classification, whereas the standard constrained loss is tractable. We will clarify this point in the text.

2. (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.

Response: Thank you for the suggestion. We will certainly provide additional explanations about the new cost-sensitive loss functions proposed and their H-consistency guarantees. This will highlight the novelty of our surrogate losses and underscore the strong theoretical foundation of our algorithms.

3. The usage of the term "accuracy" ... and so on.

Response: We use the same definition of accuracy for both methods: for top-$k$ classifiers and cardinality-aware algorithms, accuracy measures the fraction of samples where the prediction sets include the true label. However, the definition of the prediction set differs between the methods. In top-$k$ classifiers, the prediction set consists of the labels associated with the top $k$ scores. In contrast, for cardinality-aware algorithms, the prediction set is determined by the set predictor $\mathsf g_k$ chosen by the selector $r$.

The average cardinality appears to be a natural measure of the size of the prediction sets. But, we are open to alternative metrics suggested by reviewers and would be happy to include results based on such alternatives.

We appreciate the feedback on enhancing the experimental section. We will provide a more detailed analysis of our cardinality-aware algorithms in the final version. Our algorithm dynamically adjusts prediction set cardinality based on input complexity—choosing larger sets for more challenging inputs to ensure high accuracy and smaller sets for simpler inputs to keep the cardinality low. This dynamic adjustment has been validated through our experiments.

In the global response, we have included two additional experimental results related to this analysis:

Figure 1 illustrates the cardinality distribution for top-$k$ experts $\mathcal{K} = \\{1, 2, 4, 8\\}$ for the CIFAR-10 and CIFAR-100 datasets, analyzed under two different $\lambda$ values. For a given dataset, increasing $\lambda$ results in fewer samples with the largest cardinality of $8$, and more samples with smaller cardinalities. This is because increasing $\lambda$ amplifies the impact of cardinality in the cost functions. When comparing across different datasets, the distribution differs for the same $\lambda$ due to the varying complexity levels of the classification tasks.

Figure 2 illustrates the comparison of hard and easy images as judged by humans in original quality on the CIFAR-10 dataset for top-$k$ experts $\mathcal{K} = \\{1, 2, 4, 8\\}$. Hard images are predicted correctly by our algorithms with a cardinality of $8$ but predicted incorrectly when using a cardinality of $4$ instead. Easy images are correctly predicted by our algorithms with a cardinality of $1$.

Additionally, we wish to emphasize that further experiments with top-$k$ classifiers (see Figures 3 and 4 in Appendix J) and threshold-based classifiers (see Figures 5 and 6 in Appendix K) illustrate the robustness and superiority of our cardinality-aware algorithms.

4. The value of Figure 2 is unclear. What is the significance of making the cost function linear?

Response: The value of Figure 2 lies in demonstrating that the choice of the cost function—whether linear or logarithmic—has a negligible impact on our algorithm's performance. This highlights its robustness in this regard, as our framework is very general and allows for the choice of any cost function.

Questions:

1. Out of curiosity, have the authors ... included as a baseline.

Response: We have included additional experiments with threshold-based classifiers (Figures 5 and 6) in Appendix K, which demonstrate the superiority of our cardinality-aware algorithms in these scenarios. These include a comparison to conformal prediction, which provides cardinality-varying prediction sets using a threshold on prediction probabilities. We are happy to provide more comparisons as requested by the reviewers.

2. Is it in fact the case that for "harder" examples ... this new type of prediction.

Response: Yes, our algorithm dynamically adjusts the cardinality of its prediction sets based on input instances. It selects larger sets for more difficult inputs to ensure high accuracy and opts for smaller sets for simpler inputs to maintain low cardinality. This property of our algorithm has been substantiated through our experimental analysis. In the global response, we present one example (Figure 2) from the analysis, with additional examples to be included in the final version. Figure 2 illustrates the comparison of hard and easy images as judged by humans in original quality on the CIFAR-10 dataset for top-$k$ experts $\mathcal{K} = \\{1, 2, 4, 8\\}$. Hard images are predicted correctly by our algorithms with a cardinality of $8$ but predicted incorrectly when using a cardinality of $4$ instead. Easy images are correctly predicted by our algorithms with a cardinality of $1$.

Thank you for your encouraging review. We will take your suggestions into account when preparing the final version. Please find responses to your specific questions below.

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.

Response: The main focus of our cardinality-aware algorithm is in training the cardinality selector $r$, which we do in fact implement as a neural network. We used a two-hidden-layer feedforward neural network, which aligns with the assumptions of our theoretical guarantees for cardinality-aware surrogate losses. The base classifier $h$ is derived from well-trained neural networks (ResNet for CIFAR-10, CIFAR-100, and SVHN datasets; CLIP for ImageNet) with an additional linear model on top. This setup mirrors common practices in the field such as linear probing, resembling the fine-tuning of existing neural network models.

Furthermore, we are happy to report additional experimental results in which the base classifier $h$ is trained on entire neural networks without fine-tuning in the final version. However, we do not anticipate significant differences in results, as our algorithm focuses on training the cardinality selector $r$. The base classifier $h$ in our approach is pre-trained and remains fixed, providing specified costs and inputs to the algorithm.

We would also like to clarify that our theoretical guarantees in Section 4.3 make no assumptions about the base classifier $h$, which appears in the cost functions. We also assume only symmetry and completeness for the cardinality selector $r$.

Questions:

1. Can we estimate the $M$ in H-consistency bounds?

Response: This is an excellent question. Currently, no general method exists for accurately estimating $M$ from finite samples because the problem seems to require estimating both the best-in-class loss and the average pointwise infimum. However, useful upper bounds can be derived in specific cases. For instance, Theorems 4.1 and 4.2 in Mao et al.'s paper [1] provide bounds for the family of comp-sum losses.

The challenge of deriving more precise estimates based on samples, along with leveraging known information about the hypothesis set and distribution, remains an interesting avenue for future research.

Additionally, minimizability gaps are upper bounded by the approximation error, which is often small or even zero in practical applications of neural networks. In cases where the approximation error is zero, minimizability gaps also vanish.

[1] Mao et al., "Cross-Entropy Loss Functions: Theoretical Analysis and Applications," ICML 2023.

2. Authors claim the framework includes the standard conformal prediction, so do some relationships exist between the H-consistency bounds and coverage bounds?

Response: Yes, our framework covers threshold-based classifiers, including those used in conformal prediction. In conformal prediction, the threshold is determined using an $\alpha$-quantile based on a scoring function derived from a validation set. However, while standard conformal prediction provides coverage bounds that guarantee a desired $(1 - \alpha)$ accuracy, it does not provide any guarantee regarding the size of the prediction set.

In contrast, our approach offers guarantees that account for both accuracy and the size of the prediction set. Specifically, for our cardinality-aware algorithms, $H$-consistency bounds ensure that the cardinality selector $r$ is optimized to minimize the cardinality-aware loss function. This means that each input instance $x$ is assigned the most appropriate prediction set to achieve high accuracy while also keeping the average cardinality low.

Therefore, $H$-consistency bounds provide a stronger guarantee than standard coverage bounds, as they address both accuracy and cardinality, rather than focusing solely on accuracy.