Towards Human-AI Complementarity with Prediction Sets

Summary

The paper analyzes decision support systems based on prediction set algorithms. The authors show that: (i) the usage of conformal prediction techniques is generally sub-optimal in terms of accuracy; (ii) the problem of finding the optimal prediction sets under human assistance is NP-hard. Moreover, they provide (iii) a greedy algorithm that is guaranteed to find prediction sets that are better than those provided by conformal predictors. Experimental evaluation on synthetic and real data show the effectiveness of the considered approach.

Strengths

The main strengths of the paper are: 1. the actual paper contribution is well framed; 2. the theoretical analysis is sound; 3. the proposed algorithm improves over existing approaches.

Weaknesses

I think this work is a good paper, without major weaknesses, as it provides solid theoretical insights. The concerns I have are mainly due to typos/details missing. I will point out here these and a few remarks that might be considered for the final version of the paper. 1. It seems to me that Table 2 and Figure 3 are missing the BRUTE FORCE baseline. 2. regarding the style of the paper, I found lines 135-146 very dense. Maybe providing a more concrete example (e.g., what could 1,2,3 represent?) might help the reader getting through it. 3. In Algorihm 1, I think adding a comment to the pseudo-code (from lines 4 to 13) could be useful 4. regarding the limitation section (evaluation) a useful reference might be [Stutz et al., 2023], where the authors evaluate the possibility that human experts might not be approximating the true probability distribution 5. the experimental analysis (on real data) could be enriched with other popular Learning-to-Defer datasets, such as Cifar10H or hatespeech. [Stutz et al., 2023] - Stutz, David, Abhijit Guha Roy, Tatiana Matejovicova, Patricia Strachan, Ali Taylan Cemgil, and Arnaud Doucet. "Conformal prediction under ambiguous ground truth." Transactions on Machine Learning Research (2023).

Questions

I have a couple of questions/remarks: 1. Can you elaborate a bit more on lines 91-93? I am not fully sure I understand the point there. 2. Can you add the results for BRUTE FORCE SEARCH in Table 2 and Figure 3?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The paper adequately discussed the limitations and societal impact.

Summary

The authors first show that conformal prediction sets may not lead to human decision optimality. The authors then introduce a greedy algorithm to generate candidate prediction sets that improve human decisions regarding the accuracy metric.

Strengths

The authors find the sub-optimality of conformal prediction sets on providing candidates for human decisions. Thereby, they propose a novel method to produce prediction sets that helps to improve human prediction.

Weaknesses

* The presentation somewhere is unclear: * Line 86. Please break the sentence properly. * Line 40/43/48: It is unclear for readers when the authors mention “optimal” multiple times but delay its explicit definition later. * Line 197: It is confusing when the authors refer to the role of $a$. What is the value of $a$? * The authors claim they propose an efficient algorithm. However, I am not sure which part is efficient. Are there any numerical metrics, e.g., running time, supporting this contribution? Additionally, how should we understand this restriction of “for a large class of non-conformity scores and expert models” in line 51? * Line 90: But you also miss the possibility outside the prediction set, especially when the prediction set is not that good. I think the authors need to discuss the exploitation-exploration dilemma. * The authors use the scores related to softmax and APS. Other papers propose alternative scores like RAPS and SAPS. I think they should be included.

Questions

* Typo in the title: Predictions --> Prediction * Did you include the results from the conformal prediction sets by varying the value of $\alpha$? * Why choose those values of $\omega$? I think their magnitudes are close. The authors may consider even smaller and larger values of $\omega$ to show its sensitivity.

Rating

5

Confidence

3

Soundness

2

Presentation

2

Contribution

2

Limitations

Please see the above sections.

Summary

The paper shows the conformal prediction set may not be the optimal set recommendation to humans if humans follow certain choice models. The authors then propose a greedy algorithm by modeling $P(y|x)$ and the choice model of humans assuming it follows MNL model. Authors compare the proposed method against the standard conformal prediction set under synthetic human experts and the proposed method has a slightly better performance compared to traditional conformal sets.

Strengths

The authors consider conformal prediction in the human-in-the-loop setting, which is an important problem. The first part of the paper shows the conformal prediction set may not be the best recommendation set for humans, which is easy to understand since most conformal sets arrange the set in a ranked order and we can play with the human choice models to create an example that conformal sets may not be the best recommendation set.

Weaknesses

The problem setting is not realistic: The authors do not allow humans to select outside the conformal prediction set. However, in the setups of most empirical successes of human-AI collaboration with conformal prediction, this is allowed. Similarly, if the authors do not allow humans to select outside the conformal prediction set, humans' value is greatly reduced and the optimal thing to do may be just to use fully automated AI prediction and in all the toy examples the authors provided, kicking humans out of the loop is the optimal system (humans only make things worse). The theoretical analysis seems useless: I think the theoretical analysis is useless for two reasons: 1) while identifying the optimal set is NP-hard, in practice the metric we care about is $\mathbb{E} g(S|x)$, not identifying the optimal set. If an algorithm can get a good rate of convergence for this regret, then this problem is not hopeless, so I think authors need to show for all conformal prediction algorithms, what is the regret lower bound for $\mathbb{E} g(S|x)$; 2) while I can see that sometimes the label set can be large. In practice, the theoretical results may not be a big issue for many problems since most problems have small label set (binary or three classes). This negative results may not seem that severe as the authors presented in the paper. The solution is disconnected and not useful in human-AI collaboration: 1) The proposed solution does not enjoy the distributionally-free guarantee, which is the main reason why people use conformal prediction. I would expect authors to provide a conformal prediction algorithm that is human-centered, rather than directly switch lanes to traditional prediction methods. 2) The proposed solution requires $P(y|x)$ and the true human choice model, which is too strong to be realistic. If I know $P(y|x)$, why should I involve humans in the loop anymore (recall that authors can restrict humans only select from prediction set so humans are not necessary in the system). The optimal strategy would be directly use $P(y|x)$ to select actions. Baselines: For human-AI collaboration tasks, I expect to see the proposed solution is better than human working alone or AI working alone. The authors should compare with AI only baseline using $P(y|x)$. Based on the toy example and my current understanding of the paper, the proposed solution cannot beat AI only baseline.

Questions

See weakness.

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

Yes

Summary

This paper aims to construct optimal prediction sets under which experts can achieve the highest accuracy. The authors claim that human experts cannot attain maximum accuracy with the prediction sets generated by conformal predictors. To address this issue, the paper proposes an efficient greedy algorithm based on maximum marginal gain to find prediction sets that outperform those generated by conformal predictors. The paper offers two main theoretical contributions: the first proves that finding the optimal prediction set is an NP-hard problem, while the second demonstrates that the proposed method enables experts to achieve higher accuracy than conformal predictors. Empirical results further validate the effectiveness of the proposed approach.

Strengths

1. The paper is well-motivated and easy to follow. 2. The authors provide a theoretical analysis for their motivation and offer a theoretical guarantee for the superior performance of the proposed greedy algorithm. 3. The paper presents an extensive set of experiments, including both synthetic and real data.

Weaknesses

1. Further validation on more realistic datasets, such as ImageNet and CIFAR100, could strengthen the main points of the paper. 2. The experiments lack comparison with other classical score functions, such as Regularized Adaptive Prediction Sets.

Questions

1. In Figure 3, how is the Empirical Success Probability for each image calculated? 2. In line 210, why does the score function of APS discard the random variable? In other words, does the random variable affect the performance of the empirical average test accuracy? 3. Can you report the empirical coverage of the Greedy algorithm, since valid coverage is the fundamental guarantee for conformal prediction?

Rating

6

Confidence

4

Soundness

2

Presentation

3

Contribution

3

Limitations

They are adequately discussed.

Response to the Rebuttal

I thank the authors for their clarifications. I have no further questions. After reading the rebuttals and the other reviews, I am keeping my score as I think this is a sound paper.