Towards Human-AI Complementarity with Prediction Sets

[Lines 125-146 & Algorithm 1] To ease readability, we will rewrite 135-146 and we will add comments to the pseudo-code in Algorithm 1.

[Limitation section] In the limitation section under "Evaluation", we will add a discussion of and citation to Stutz et al., 2023.

[Other popular datasets] We agree that it would be interesting to evaluate our greedy algorithm in other datasets besides ImageNet-16H. However, there is a scarcity of publicly available datasets with multiple expert predictions per sample, a relatively large number of samples, and more than two/three classes. In the suggested datasets, either the performance of the human experts on their own is very high (CIFAR-10H) or the number of classes is very small (hatespeech) for decision support systems based on prediction sets to be practical.

[Lines 91-93] If we allow the expert to predict label values from outside the prediction set, the expert would have to decide when to believe that the true label is in the prediction set and thus predict a label from the prediction set, and when to question that the true label is in the prediction set and thus predict a label from outside the prediction set.

In this context, it is worth pointing out that, as shown in a large-scale human subject study by Straitouri et al. (ICML 2024) [19], if we allow the expert to predict label values from outside the prediction sets, the number of predictions in which the prediction sets do not contain the true label and the experts succeed is consistently smaller than the number of predictions in which the prediction sets contain the true label and the experts fail, as shown in Figure 10 in their paper.

[Brute force search] Since the greedy algorithm achieves the same performance as brute force search, we omitted brute force search from Table 1, Table 2 and Figure 3. However, we missed to clarify that in the caption of Table 2 and Figure 3. We will clarify that in the revised version of the paper.

[Optimal] We will define what we mean by optimal the first time we mention optimal in the revised version of the paper.

[Role of $a$] In the generative model we used in the synthetic experiments, out of 20 features per sample, $d=4$ of these features correlate with the label value and thus are informative and the rest are just noise. In this context, "a" denotes the value of one of these four informative features. We will bring this information from Appendix C to the main in the revised version of the paper.

[Efficient algorithm] The computational complexity of our greedy algorithm is polynomial on the size of the label set $|\mathcal{Y}|$, as shown in lines 171-176 in Section 4 and Appendix B. We will clarify that, by efficient, we refer to "computational efficiency" in the revised version of the paper.

[Class of non-conformity scores and expert models] The guarantees of our greedy algorithm with respect to conformal prediction (Proposition 1) apply to any non-conformity score that is nonincreasing with respect to the classifier scores $f_y(x)$ and expert models parameterized by a mixture of multinomial logit models (MNLs). We will clarify this in the revised version of the paper.

[Exploitation-exploration dilemma] Straitouri et al. (ICML 2024) [19] conducted a large-scale human subject study where they compared a setting where users are not allowed to select label values outside the prediction sets against another setting where users are allowed to select label values outside the prediction sets. They found that, in the latter setting, the number of predictions in which the prediction sets do not contain the true label and the experts succeed is consistently smaller than the number of predictions in which the prediction sets contain the true label and the experts fail, as shown in Figure 10 in their paper. As a consequence, humans perform better in the former setting than in the latter setting, as shown in Figure 3 in their paper. Following the reviewer's suggestion, we will include such a discussion in the revised version of the paper.

[RAPS and SAPS] Following the reviewer's suggestion, we conducted extensive additional experiments using the best conformal predictors created with RAPS and SAPS [*], and we will include them as baselines in the revised version of the paper. Both methods present additional hyperparameters ($k_{reg}$ and $\lambda_{raps}$, for RAPS, and $\lambda_{saps}$ for SAPS) we optimize using a held-out validation set and the procedure outlined in the original papers (e.g., see Appendix E [49]).

The empirical evaluation shows that their performance is worse than our greedy algorithm for synthetic and real-world tasks (Tables 1 and 2 of the rebuttal PDF). Moreover, RAPS and SAPS offer comparable performances to NAIVE and APS in all the tasks. The complete results can be found in the PDF attached to the general rebuttal comment above.

[*] Huang, Jianguo, et al. "Conformal prediction for deep classifier via label ranking." ICML (2024).

[$\alpha$ value] In Table 1 and Table 2, we report the results for the value of achieving the highest empirical success probability for each non-conformity score and classification task, as noted in lines 211-212 and 262-263. In Appendix G, for the experiments with real data, we report the result for all values of $\alpha$.

[$\omega$ values] The ImageNet-16H dataset contains only images with the $\omega$ values we used and thus we cannot experiment with smaller or larger values. However, we would like to point out that, even if the levels of phase noise $\omega$ seem close, the accuracy of the predictions made by humans on their own varies significantly among $\omega$ values, as shown in Figure 4S of Steyvers, Mark, et al. "Bayesian modeling of human–AI complementarity." Proceedings of the National Academy of Sciences 119.11 (2022): e2111547119.

[Problem setting] Straitouri et al. (ICML 2024) [19] conducted a large-scale human subject study where they compared the setting we adopted, where users are not allowed to select label values outside the conformal prediction sets, against the setting the reviewer suggests, where users are allowed to select label values outside the sets. The results of their study (refer to Figure 3 in their paper) suggest that humans perform better under the setting we adopted, which Straitouri et al. refer to as the strict implementation of their system, than under the setting the reviewer suggests, which they refer to as the lenient implementation of their system.

Further, we would like to clarify that, in our experiments, we found that kicking humans out of the loop is not the optimal system (humans do not make things worse) in the setting we adopted. More specifically, in the experiments with synthetic data, both the accuracy of the classifier $P(Y'=Y)$ we used (shown in the top row of Table 1) and the accuracy of the human (rows under NONE in Table 1) are always lower than the accuracy of the human using the prediction sets provided by our greedy algorithm (shown in rows under GREEDY of Table 1). This suggests that even if the human has low performance overall, it may still be beneficial to use prediction sets tailored to the performance of humans rather than "kicking them out".

In the experiments with real data, the accuracy of the (fine-tuned) VGG-19 classifier we used ($0.896$ for $w=80$, $0.894$ for $\omega=95$, $0.857$ for $\omega=110$ and $0.792$ for $\omega=125$) and the accuracy of the human working alone ($0.9$ for $\omega=80$, $0.859$ for $\omega=95$, $0.771$ for $\omega=110$ and $0.603$ for $\omega=125$), which we missed reporting in our paper, are also always lower than the accuracy of the humans using the prediction sets provided by our greedy algorithm (shown in rows under GREEDY in Table 2). In the revised version of the paper, we will report the accuracy of the (fine-tuned) VGG-19 classifier we used and of the human working alone.

[Theoretical analysis] Our hardness analysis implies that finding the optimal prediction sets that maximize the metric $\mathbb{E}[g(\mathcal{S}|x)]$ is NP-hard, and even finding a prediction set that approximates this to a reasonable factor (e.g. a constant factor) is also NP-hard. As a consequence, there is no polynomial-time algorithm with a sublinear regret (i.e., a good regret) with respect to the (oracle) algorithm that creates optimal prediction sets that maximize $\mathbb{E}[g(\mathcal{S}|x)]$. We will clarify this in the revised version of the paper.

While there are certainly many problems with small label sets, there are also many problems with large label sets. In fact, two of the most popular benchmark datasets in the machine learning literature used by thousands of papers, ImageNet and its more commonly known subset ImageNet-1k, contain over 20,000 and 1,000 different label values, respectively. As an additional example of tasks with large label space, we mention a clinical text annotation task where each span of text has to be mapped to a "concept label in a large (>400,000) medical vocabulary" [1].

[1] Levy, Ariel, et al. "Assessing the impact of automated suggestions on decision making: Domain experts mediate model errors but take less initiative." Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems. 2021.

[Distributionally-free guarantees of conformal prediction] One of the main contributions of our paper is to demonstrate that, in human-AI collaboration, the distributionally-free guarantees offered by conformal prediction may be insufficient to achieve optimal performance. More specifically, in Section 3, we show that, under common choices of non-conformity scores, there are many data distributions for which the optimal prediction set under which the human expert achieves the highest accuracy cannot be constructed by any conformal predictor. As suggested by the reviewer, one may think of developing human-centered conformal predictors that incorporate information about the distribution of experts’ predictions in the definition of the non-conformity score. However, as argued in lines 118-122, our hardness results show that one cannot expect to fully close the performance gap with such human-centered conformal predictors.

[Knowledge of $P(Y|X)$] Even if one knows the conditional distribution of the ground-truth label $P(Y|X)$, one may benefit from involving humans in the loop if the humans have access to additional features besides X, as pointed out in footnote 4. For instance, in the example in lines 106-117, the optimal prediction set under which the human achieves the highest accuracy does not contain the label value with the highest $P(Y|X)$ value. Further, under this prediction set, the human achieves higher accuracy than a classifier that picks the label value with the highest $P(Y|X)$ value (0.6 vs 0.4).

[Human-only and AI-only baselines] In our experiments, both with synthetic and real data, our proposed solution is better than humans working alone or AI working alone. Regarding the comparison with AI working alone, please, refer to our previous reply under [Problem setting]. Regarding the comparison with human working alone, in the experiments with synthetic data, the accuracy of the human working alone is reported under "NONE" and, in the experiments with real data, the accuracy of the human working alone is $0.9$ for $\omega=80$, $0.859$ for $\omega=95$, $0.771$ for $\omega=110$ and $0.603$ for $\omega=125$, which we missed reporting in our paper and we will report in the revised version of the paper.

[More realistic datasets] The dataset ImageNet-16H is among the only publicly available datasets that we found containing multiple expert predictions per sample, a relatively large number of samples, more than two/three classes and a reasonable level of difficulty. The suggested datasets, ImageNet and CIFAR100, do not contain multiple expert predictions per sample. Another dataset for a multiclass classification task is CIFAR-10H which also has multiple expert predictions per sample and 10 classes. However, we found that the experts on their own already achieve high accuracy ($\sim 0.95$), making it a less challenging scenario than ImageNet-16H.

[RAPS] Following the reviewer's suggestion, we conducted extensive additional experiments using the best conformal predictors created with RAPS and SAPS [*], and we will include them as baselines in the revised version of the paper. Both methods present additional hyperparameters ($k_{reg}$ and $\lambda_{raps}$, for RAPS, and $\lambda_{saps}$ for SAPS), which we optimized using a held-out validation set and the procedure outlined in the original papers (e.g., see Appendix E [49]).

The empirical evaluation shows that their performance is worse than our greedy algorithm for synthetic and real-world tasks (Tables 1 and 2 of the rebuttal PDF). Moreover, RAPS and SAPS offer comparable performances to NAIVE and APS in all the tasks. The complete results can be found in the PDF attached to the general rebuttal comment above.

[*] Huang, Jianguo, et al. "Conformal prediction for deep classifier via label ranking." ICML (2024).

[Empirical success probability] For each image $x$ and prediction set $\mathcal{S}$, we estimate the empirical success probability using the mixture of multinomial logit models (MNLs), i.e., $P_{\mathcal{S}}(\hat Y = y | X=x, Y=y) = \frac{C_{yy}}{\sum_{y' \in \mathcal{S}} C_{y'y}}$, where $\hat{Y}$ denotes the prediction by the human, $Y$ denotes the true label and, in the experiments with real data, the confusion matrix $\mathbf{C}$ is estimated using predictions made by real human experts on their own.

[Randomization in APS] We did not find the randomization in APS, which is just needed to achieve $1-\alpha$ coverage exactly, to influence the empirical success probability in our experiments. Therefore, for simplicity, we decided to omit it. We will clarify this in the revised version of the paper.

[Empirical coverage of Greedy] We will report the empirical coverage achieved by the greedy algorithm and the best conformal predictors used as baselines in the revised version of the paper. Here below we show the empirical coverage for the synthetic tasks.

In summary, prediction sets constructed with our greedy algorithm present a comparable empirical coverage with respect to the best conformal predictors (Naive and APS) in both synthetic and ImageNet-16H tasks. Moreover, in those few settings in which the conformal predictors coverage is higher (e.g., $P(\hat{Y} = Y) = 0.3$ and $\gamma = 0.3$), the conformal predictors' empirical success probability is lower (see Table 1 of the main paper), which underlines how coverage alone can be a bad proxy to estimate the empirical human accuracy. Moreover, please note how the empirical success probability of the human acting alone with the full label set, that achieves perfect coverage (1.0), is always worse than the combination of human + predictions sets in all of our experiments.