Class-Conditional Conformal Prediction with Many Classes

Summary

Standard conformal prediction provides a marginal coverage guarantee which is insufficient for many practical applications. Class-conditional conformal prediction is suitable for many applications, especially in $Y \rightarrow X$ settings, e.g., image data. Achieving class-conditional coverage relies on learning a separate threshold for each label, and hence splitting the calibration set into label-dependent groups. This becomes prohibitive in classification problems with many classes. The current paper proposes a method based on clustering similar classes (which share similar conformal scores) and performing cluster-conditional conformal threshold calibration.

Strengths

The paper is well-written, and provided figures help the reader to follow the content easily. Relevant works and the limitations of the respective methods are highlighted. The proposed method is validated on a large number of large-scale public datasets, illustrating its general practical relevance.

Weaknesses

To avoid tautology, most of my concerns will be outlined in the questions box: those are related to the issues arising empty prediction sets and clustering based on the nonconformity scores. There is also a couple of minor typos: 1. Line 26: $\mathcal{C}(X_{test})\subseteq \mathcal{Y}$. 2. Proposition 1: missing full stop in the equation between lines 156 and 157. Finally, a couple of stylistic suggestions: 1. In Figure 1, it may be better to make sub-captions consistent (i.e., point out that the left su-plot refers to standard CP and the right one to Classwise CP). 2. In Figure 2, it may be better to use different markers (in addition to different colors) for depicting the results of using different methods. 3. I believe that [1] should also be cited and discussed. [1] "Least Ambiguous Set-Valued Classifiers with Bounded Error Levels". Sadinle et al., 2016

Questions

I hope that the authors can provide answers to the following questions/concerns: 1. One of the issues with class-conditional CP which has been pointed out in [1] is that there could be cases when the resulting prediction sets are empty (the authors also proposed several ways to handle this issue). Does this issue also apply to the proposed method? 2. I am concerned regarding clustering based on nonconformity scores. Is it possible to (empirically) demonstrate that (even in the most straightforward cases) such classes form "meaningful"/"interpretable" clusters if nonconformity scores are used as features? Consider CIFAR-100 dataset as an example: class "apples" is "closer" to the class "mushrooms" than it is to the class "rocket". However, suppose those happened to be assigned to the same cluster. In that case, the coverage guarantee reads as "among images with apples, mushrooms, and rockets, the true label is contained in the prediction set with probability at least $1-\alpha$" and may not be that interpretable. 3. For many datasets, there is a known taxonomy/hierarchy of classes, e.g., for CIFAR-100, even though there are 100 classes, these are grouped into 20 superclasses. Such taxonomies can also be used to convert the low-data class-conditional calibration step to a high-data group-conditional calibration step, while resulting in interpretable clusters/groups. Even if such taxonomy is not provided, one can still try to come up with one that guarantees that there are "enough" calibration points in each group. What are the advantages of the proposed method over this strategy? [1] "Least Ambiguous Set-Valued Classifiers with Bounded Error Levels". Sadinle et al., 2016

Rating

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

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

The current work is a part of methodological research and does not have a potential negative societal impact. Overall, I hope that the authors can better highlight the downsides of the proposed method (e.g., grouping based on existing dataset taxonomy).

Summary

This article studies the clustered conformal prediction, mitigating the issues in the standard conformal and class-wise conformal, by grouping some similar classes together.

Strengths

* The authors proposed clustered conformal prediction to strike the balance between marginal coverage and class-wise coverage for the setting of many classes with limited data per class. * When calibration data is limited, the empirical results show that the proposed method achieves a relatively small coverage gap according to the designed metric (CovGap), effectively balancing marginal coverage and class-wise coverage.

Weaknesses

* The authors need to specify the low-data scenario (at least on the calibration data from the perspective of the experiments) in the title, otherwise, there are other works related to many classes. Moreover, from the main manuscript, it looks more like cluster-conditional conformal instead of class-conditional conformal in the title. * The setting and the numerical study somehow contradict each other. Now that the authors used deep learning to train the score function, it does not make sense that there is a limited calibration dataset in practice. If that, why don’t allocate some from the training data? * There is no sensitivity analysis on the clustering procedure. What if different schemes are used for choosing $M$? How does $M$ (e.g., $M < K$ or $M > K$) affect the results? * Using CovGap as a metric might obscure the issue of coverage for each class from methods, e.g., the standard and the proposed method. The results are difficult to say without explicitly showing the coverage for each class. For example, class-wise conformal has high coverage than $1-\alpha$ with the larger gap, but the proposed method could return the coverage below $1-\alpha$ with a smaller gap.

Questions

* The strikingly large prediction set of class-wise conformal is due to the threshold set as in Line 115, but why don’t we set it as the largest score in the calibration data instead of the infinity? There might be a loss of coverage, but it is unclear how large it is in these empirical results, and whether or not this kind of loss is tolerable, especially when the other two competing methods may also lose the coverage for the individual class. * Line 149: It seems the idea of finding the threshold for the null cluster is the same as that for the marginal coverage. Now that you criticized the standard conformal’s overall coverage ability, why not merge some clusters until you get the desired sample size instead of merging all clusters in the proposed method? * Line 176: The authors also notice the issue of class imbalance may affect the clustering, then can we up-sample the minor classes to mitigate the issue mentioned in Line 115 and then follow the class-conditional conformal instead of the proposed clustered conformal? Or what if you do the clustering on the original dataset to obtain the desired sample size, and then use class-conditional conformal?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good 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

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

Please see the above two parts.

Summary

The paper studies how to achieve class-conditional coverage (in the setting of conformal prediction) for multiclass classification problems, in particular for tasks with large label spaces. Previous techniques either provide no class-wise guarantees or tend to produce conservative prediction sets due to lack of data. The key insight here is that non-conformity scores from different classes may be grouped together if their class-conditional score distributions are similar, since the $(1- \alpha)$-quantile value to achieve desired coverage would be the same across these classes. Essentially, we can extrapolate about a class with low amounts of data by simply using data from other classes with a similar score distribution. This work is particularly applicable in settings where there is a large number of classes (and thus higher likelihood of small amount of data for some of these classes) and / or high class imbalance.

Strengths

• Firstly, I found this paper particularly well-written and structured; was written to make the discussion quite intuitive and easy to follow. • Method is a natural solution in settings where there is an underlying structure / similarity in how the base model performs on certain groups of classes. • Strikes a balance between getting meaningful prediction sets (not overly conservative) and getting low variance in class-wise coverage rates. • Empirically, the proposed method performs quite well, performing on par or better than the baseline methods for the studied metrics.

Weaknesses

• This performance of CLUSTERED seems to be essentially a data and model-driven problem. If there are different classes with similar score distribution, it improves performance. Is there a possibility of artificially inducing clusters, if such a similarity doesn’t exist? • The CovGap metric seems to penalize both overcoverage and undercoverage without distinguishing between the two. It would be nice to see how much each of the methods overcover and undercover (classwise) separately. For example, in Table 2 I would expect that the high CovGap values for CLASSWISE is mostly due to overcoverage, while for STANDARD it is probably undercovering and overcovering in equal measure, but this metric hides that potential distinction. • Minor typo: use of $h$ in line 146, equation after line 146 and in Proposition 1 should be $\hat{h}$.

Questions

• Though equation (2) implies equation (1), in general we may not achieve the guarantee of (2) as you have mentioned in Section 2.2, so the CLUSTERED algorithm may not necessarily achieve marginal coverage. Do you see this method as more of on a continuum with STANDARD and CLASSWISE, with each of them having situations where they work better, especially since CLUSTERED guarantees are not as consistent as the others? • Clarification about the usage of Algorithm CLASSWISE: when generating a prediction set for a new input, to choose a conformal predictor to use, we need to know the true label, which we do not. So which of the K predictors is chosen? Do we run all of them and choose the most conservative quantile value?

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

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

• The theoretical guarantee on class-conditional coverage depends on the value of $\epsilon$ defined in Proposition 3 which can vary based on the actual score distributions across classes, the value of $m$ used and the clustering algorithm used, so there may be concern on achieving close to $(1 - \alpha)$-coverage performance in general, although in all experiments, the method seems to work quite well.

Summary

The paper describes a method for conformal prediction specially addressed for the case where there is few avaliable data in some of the classes. To address this problem, the proposed method performs a clustering of classes with similar score distributions with the goal of increasing the data used to select the set of classes for a given sample. Experimental results on standard image datasets with a large number of classes with different settings of data availability are reported comparing the proposed method with other standard approaches for conformal prediction.

Strengths

1. The paper addresses the problem of conformal prediction with a large number of classes and with few data per classe, and proposes a new method specifically designed for this setting. The method is well motivated and formalized. 2. Extensive experiments are performed on different datasets and different settings of data availability, comparing the proposed method with standard and classwise approaches. Results show that the proposed method achieves a better average coverage. 3. The paper include useful practical recommendations about when to use each of the conformal prediction approaches.

Weaknesses

1. One of the motivating points of the paper is that, in some cases average coverage can be good enough, but specific coverage for some underepresented classes can be very low. Results show that average coverage improves with the proposed method, but there is not any discussion or results about the specific coverage for particular classes, specially those with few data. Therefore, we cannot validate the original motivation of the paper. Furthermore, as fas as I understand, classes with few data will most probably assigned to the null cluster and then, those classes will follow the standard approach, and there will be no difference between the proposed method and the standard one for these classes. 2. Although the average coverage improves, the AvgSize measure is, in general worse than with the standard method. 3. Some technical details could be better explained or motivated. - In section 2.1, what do you exactly mean by "scores for all classes in a given cluster are exchangeable? That score distributions are equal? - The k-means clustering algorithm is very dependent on the selected number of clusters. Although there is a explanation on how the number of cluster is defined, wouldn't it be better to use an adaptive clustering algorithm where the number of clusters can be automatically determined? - The representation used to perform the clustering is based on a few discrete number of quantile scores. Wouldn't it be better to use a larger and more dense number of quantile scores that could give a better approximation of the distribution of score values? 3. Related work is very oriented to describe on which types of data conformal prediction has been applied. I miss a more technical discussion describing the different techniques and methods used in the existing works.

Questions

See above, specially questions regarding performance on specific classes with few data. ----------------------------- I have read the rebuttal and it has clarified most of the questions I had about the paper, specially those related with classes with few samples and technical issues. After reading all comments and discussion, I increase my rating to weak accept.

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

2 fair

Limitations

The authors discuss on the limitations of the method and no potential negative impacts are foreseen