On the Utility of Prediction Sets in Human-AI Teams

1 Introduction

Human-AI collaboration is of increasing importance. Several works have shown the benefits of human-AI collaboration in boosting accuracy, fairness, and compatibility [Madras et al., 2018; Bansal et al., 2019; Mozannar and Sontag, 2020]. One form of collaboration in the medical domain is the effect of AI explanations on team performance [Lundberg et al., 2018], where team performance improves if model explanations are provided. Another form of human-AI collaboration develops techniques for models to defer to an expert. Prior literature exploring both these forms of collaboration has mainly considered models which output singular predictions. However, this does not allow experts to gauge and interpret the predictive uncertainty of the model, which can prevent deployment in high risk settings. A solution to this is for the model to display set valued predictions. We define a set valued model prediction Γ as a mapping from the input space X to the power set of the label space Y, i.e. Γ : X → 2Y . One way to construct a set valued predictor is through a technique called Conformal Prediction (CP) [Vovk et al., 2005]. CP generates a prediction set that may contain multiple labels, but contains the true label with a user defined error probability. The goal of CP is to construct predictive sets that are sufficiently small but have high probability of containing the true label.

One problem often associated with CP sets is that they can be quite large, which can limit their usefulness in time and cost sensitive domains such as medical diagnostics, where it is crucial to narrow down the list of possible diagnoses. Previous work such as [Bellotti, 2021] and [Stutz et al., 2022] have devised surrogate loss functions for minimizing set sizes whilst maintaining coverage guarantees. [Angelopoulos et al., 2020] regularize the low scores of unlikely classes to provide small, stable sets. However, CP literature in general has given little consideration given to a) how useful such predictive sets are in human-AI teams and b) how human expertise could be leveraged to get smaller predictive sets [Sadinle et al., 2016; Romano , 2020; Angelopoulos and Bates, 2021 ]. Recently, [Straitouri et al., 2022] explored improving expert predictions using CP, with a focus on finding the optimal error tolerance parameter α that benefits the expert. In this concurrent work, we fix α and use deferral as a mechanism to provide sets that are smaller and hence more useful to an expert. Our contributions are the following:

• Through human subject experiments on CIFAR-100, we

first show that CP sets result in higher levels of reported trust and utility as compared to Top-1 predictions.

• We empirically demonstrate one limiting aspect of CP sets: they can be very large for some examples. In order to mitigate this, we propose combining set valued classification and learning to defer. Through a toy example, we show the utility of learning to defer for the predictive set size of non-deferred examples.
• We then introduce D-CP, a general practical scheme that learns to defer on some examples and perform conformal prediction on others. We prove that, under mild conditions, the set size associated with non-deferred examples will be smaller than that of the original dataset.
• Through further human subject experiments on the CIFAR-100 dataset, we discover two benefits of D-CP: smaller predictive sets and improved team performance. We find that D-CP leads to higher reported utility and expert accuracy compared to showing only CP sets.

2 RelatedWork

2.1 Conformal Prediction

There is growing interest in conformal prediction [Vovk et al., 2005] as a method of rigorous uncertainty quantification. Given a test example Xtest and its (hidden) true label Ytest, this method allows the user to construct sets Γ(Xtest) that control for the binary risk, i.e. the error probability α = P(Ytest /∈ Γ(Xtest)). This is done by performing a statistical test for each label in order to decide whether the label should be present in the set. In particular, we define a conformity score τ(Xtest, y) : X × Y → R that determines how different example (Xtest, y) is from already observed data {(Xi, Yi)}ni=1 . This is a design choice and several papers explore different choices of conformity functions [Sadinle et al., 2016; Angelopoulos et al., 2020; Romano et al., 2020]. To include label y in a predictive set, we require that the conformity score τ(Xtest, y) is at least α-common with respect to conformity scores on previously observed data, i.e. Quantile(τ(Xtest, y), {τ(Xi, Yi)}) ≥ α.

This is equivalent to learning a threshold conformity score for including labels in a set. Defining the threshold as τcal = Quantile(α, {τ(Xi, Yi)}), we require τ(Xtest, y) ≥ τcal to include the label y in the predictive set for Xtest. The conformal set is therefore defined as: Γ(Xtest, τcal) = {y : τ(Xtest, y) ≥ τcal}. In this paper, we employ a computationally efficient scheme called Inductive Conformal Prediction (ICP) [Papadopoulos, 2008]. This requires an additional calibration dataset Dcal = {(Xi, Yi)}ni=1 drawn from the same distribution as training and validation sets. After training a classifier on a training dataset, we can use this calibration dataset to choose the α Quantile threshold τcal.

None of the works that have previously studied CP [Sadinle et al., 2016; Angelopoulos et al., 2020; Romano et al., 2020; Stutz et al., 2022] involved experts in the loop or even considered the utility of prediction sets generated in the context of human-AI teams.

2.2 Learning to Defer

Many works have studied the idea of learning a model that adapts to an underlying expert. One approach is to learn a rejector and a classifier, wherein, given a cost of deferring c, one learns a binary classifier that rejects whenever it is less than 1 - c confident [Bartlett and Wegkamp, 2008; Cortes et al., 2016]. For multi-class problems, [Mozannar and Sontag, 2020] learn a model that predicts the true label whenever the expert is wrong and defers otherwise. Similarly, [Okati et al., 2021] develop a method for exact triage under multiple expert annotations and prove its optimality under conditions where there is expert disagreement. [Wilder et al., 2021], on the other hand, develop a decision theoretic approach, training 3 probabilistic models representing the AI, expert, and joint human-AI to maximize utility. However, all these approaches only examine settings where the AI makes point predictions whereas we aim to defer some examples and provide principled, calibrated prediction sets on others.

3 Are Prediction Sets better for Human-AI teams than Top-1 Predictions?

Our first study focuses on establishing the value of set valued predictions. For our experiments, we focus on one particular CP scheme called Regularised Adaptive Prediction Sets (RAPS) [Angelopoulos et al., 2020]. We recruit 30 participants on Prolific, paying them at a rate of £10 per hour prorated, and divide them into 2 equal groups. The first group is shown 18 images from the CIFAR-100 dataset alongside the model's most probable prediction (Top-1). The second group is shown the same images but alongside a RAPS prediction set with error rate α = 0.1. To understand the effect of set valued predictions on examples of varying difficulty, we divide the CIFAR-100 test dataset into 3 difficulty quantiles, where difficulty is defined as the entropy of the model predictive distribution. We select 6 images from each difficulty quantile. For each quantile, we show 2 images whose Top-1 prediction is incorrect but whose RAPS set contains the true label. This is consistent with the accuracy of the model (≈ 65%) and lets us determine the effect of set valued predictions on examples on which the model is almost correct. Given these model predictions for each image, we ask participants in both groups to predict the correct class, rate their confidence in their predictions, and rate how useful they found the model predictions on that example. At the end of the survey, we ask participants to rate their overall trust in the model's predictions. All ratings are on a scale from 1 - 10. We employ preliminary attention checks by first asking them to classify 3 easy examples, rejecting any participants who classify these examples incorrectly. We evaluate the statistical significance of our results using a two sample t-test.

From Table 1, we see that Top-1 predictions result in statistically significant lower levels of trust (p < 0.001) and perceived utility (p = 0.003) compared to RAPS. However, both schemes result in similar accuracy and confidence in predictions. We also see that users find Top-1 and RAPS predictions equally useful for easy examples (Table 2). This makes sense because in such cases, the predictive set will be small and therefore comparable to a Top-1 prediction. However, users are more confident about their answers when they observe RAPS predictions. On the other hand, RAPS sets are perceived to be much more useful on hard examples, where Top-1 predictions will often be wrong.

Takeaway: While there is seen to be no significant difference in team accuracy when shown either Top-1 or set-valued predictions, displaying set-valued predictions in human-AI teams results in higher reported utility of predictions as well as higher reported overall trust in the model.

4 Proposed Approach

4.1 The Problemwith CP Sets

In our experiments above, we showed users examples where the set sizes on CIFAR-100 are small enough to be considered useful. However, this may not always be the case, especially on tasks with large label spaces. For instance, a standard WideResNet model trained on CIFAR-100 (≈ 65% accuracy) with APS conformal prediction yields prediction sets with greater than 15 labels for 20% of examples. One option to mitigate this issue is to defer examples with the largest CP set sizes to an expert. However, this provides no guarantee that the expert will be able to classify them with sufficient accuracy. Furthermore, we also lose the finite sample coverage guarantees provided by contemporary CP methods, i.e. we cannot ascertain that P(Ytest /∈ Γ(Xtest)) ≤ α.

4.2 Our Scheme

Our scheme, described in Algorithm 1, is centered around two components: a deferral policy π(x) : X → {0, 1} and a CP method. The deferral policy is based on our knowledge of the expert's strengths either acquired during training or a-priori. For example, if an expert is better at identifying brain tumors than our model, our policy should learn to defer those examples with high probability. Using this black box policy, we first prune our calibration dataset, removing all examples where our deferral policy recommends deferral. One could use any scheme in [Mozannar and Sontag, 2020; Okati et al., 2021;

Wilder et al., 2021] to learn a deferral policy. While Algorithm 1 specifies a deferral policy as an input, for some deferral methods (such as [Mozannar and Sontag, 2020]), the policy is trained alongside the model. In others, such as [Okati et al., 2021], the policy is applied post-hoc. In this paper, we consider the former deferral policy: the D-CP algorithm for this is outlined in Algorithm 2 in the Supplementary Material. After training a model and a suitable deferral policy, we perform conformal calibration on this pruned dataset of nondeferred examples. In this procedure, for any predictive set Γ(Xtest, τcal) for an example Xtest we can guarantee that:

where 1 represents the action of deferral. From [Angelopoulos et al., 2020], when the conformity scores are known to be almost surely distinct and continuous, we can also guarantee:

where n is the size of the non-deferred calibration dataset. Because the deferral policy π probabilistically decides which unseen examples to defer, all non-deferred examples can be thought of as being generated from a data generating distribution X ∼ p(X|π(X) = 0). Any new test example Xtest that is not deferred is therefore independently drawn from this distribution. Thus, {Xi}ni=1 ∪ {Xtest} ∼ p(X1, ..Xtest|π(X1), ..π(Xtest) = 0) are exchangeable, thereby satisfying the coverage guarantee in Equation 1. To

show the utility of our scheme, a good deferral policy would guarantee that resulting predictive sets on non-deferred examples will contain fewer incorrect labels than before. We prove

Algorithm 1 General D-CP

Input: Classifier mθ(x) ∈ R|Y| , Deferral Policy π(x) ∈ {0, 1}, Training Set D, Expert h(x) ∈ Y, Calibration Set Dcal, Validation Set Dval, Test Example xtest, Conformity Score Function τ(X, y), Loss function l(mθ(x), y, h(x))

Parameter: Number of Epochs N, Learning Rate γ, Error Tolerance α

1: for i ∈ {1, ...N} do 2: for Batch B ∈ D do 3: θ = θ - γE(x,y)∈B[∇θl(mθ(x), y, h(x))] 4: end for 5: end for 6: D′cal = {(X, Y )|π(X) = 0, (X, Y ) ∈ Dcal} 7: τcal = Quantile(α, {τ(Xi, Yi)|(Xi, Yi) ∈ D′cal}) 8: if π(Xtest) = 0 then 9: return Γ(Xtest, τcal) = {y|τ (Xtest, y) ≥ τcal} 10: else if π(Xtest) = 1 then 11: Defer to Expert h(Xtest) 12: end if

this formally in Theorem 1 in the Supplementary Material. While this technically applies to conformity scores τ(x, y) that are monotonic with respect to softmax probabilities (such as LAC), our subsequent experiments with other CP methods such as RAPS and APS suggest that our scheme generalises well across other classes of conformity score functions.

5 Toy Example

One way to combine conformal prediction and deferral is to only perform CP on "easy" examples and defer the "hard" examples. An "easy" example would be one which the model is confident on and a "hard" example is the converse. This can lead to smaller sets. To demonstrate the intuition, we generate equiprobable synthetic data using a Mixture of Gaussians (MoG) model. Each datapoint is generated from one of 4 Gaussians - N(1, 1), N(1, -1), N(-1, 1), and N(-1, -1) - and we wish to infer class memberships. We first train a multilayer perceptron (MLP) on 1000 training samples (not shown) to infer the decision boundaries. Then, using a held out calibration set, we perform CP with error tolerance α = 5% using the Least Ambiguous Classifiers (LAC) method [Sadinle et al., 2016]. In this method, we use the model softmax probabilities p(y|x) = τ(x, y) as conformity scores. Figure 5 (top) shows a 1-D scatter plot of conformity scores assigned to ground truth labels in the toy dataset.

Figure 4 shows the resulting test datapoints colored according to their true classes with model decision boundaries overlaid. We see that points closer to the decision boundary have larger predictive set sizes, reflecting their inherent uncertainty. If we defer points with conformity scores in the bottom 15th percentile (naive decision policy) as in Figure 5, the α threshold conformity score will increase. From Figure 5 (Right), for non-deferred examples, this increases the threshold for including labels in the set, resulting in more confident sets for the same error control. However, this naive deferral method, whilst ensuring small set sizes on the remaining examples, does not take into account the expertise of the expert involved.

Furthermore, we assumed access to ground truth labels for test examples, which is not practical. We can engage the expert in a better manner and approximate the idea of the toy example by learning a deferral policy which incorporates estimates of expert ability as well as machine difficulty. This scheme makes an implicit assumption that the expert is a) either better than the model on average or b) not necessarily better than the model on average, but is proficient in classifying certain subgroups of examples. In these situations, our deferral policy is more likely to defer examples that a model is less confident on. Given these assumptions about an expert, we are assured of lower predictive set sizes on non deferred examples.

6 Experiments with D-CP

To validate our approach, we perform experiments with synthetic expert labels on the CIFAR-100 dataset and real expert labels on the CIFAR-10H [Peterson et al., 2019] dataset 1 . Because the CIFAR-10H dataset contains expert labels only on the CIFAR-10H validation set, we employ the approach in [Mozannar and Sontag, 2020] and train a binary classifier to predict examples where the expert is correct. We then provide synthetic expert labels Ih(x)=y or Ih(x)̸=y for examples the training set according to whether the expert errs on them. Note that, in line with the assumption made in this paper, the experts chosen in this setting are, on average, better than the model trained. We consider 2 scenarios:

1 Our code is hosted at https://github.com/cambridge-mlg/d-cp.

• We have access to a single expert's annotations. For CIFAR-100, we generate a synthetic expert with 70% accuracy. To motivate this choice, we ran a control study where we asked 20 participants to classify 15 randomly chosen CIFAR-100 examples. We found participants had average accuracy of 69% with a standard error of ≈ 2.5%. For the CIFAR-10H dataset, we randomly sample a label from the predictive distribution provided.
• We have access to multiple expert annotations. This is an ensemble of the above experts, and the predicted class is chosen through majority voting for both datasets. For the CIFAR-100, we generate predictions from 5 experts.

Our deferral policy is based on the loss function in [Mozannar and Sontag, 2020]. We train a WideResNet [Zagoruyko and Komodakis, 2016] classifier mθ(x) : X → Y∪ ⊥ on CIFAR-10H and CIFAR-100 for 5 and 10 epochs respectively using the learning rate schedule in [Mozannar and Sontag, 2020]. ⊥ represents the action of deferral to an expert h(x). We modify the loss function used in this work as below:

where we set α = 1 and vary the β ∈ [0, 1] penalty term to control the deferral rate. The policy π(x) is therefore:

To compute conformity scores, we renormalize the softmax probabilities for examples where π(x) = 0 using Bayes' rule:

In our experiments, we did not notice any statistically significant difference in accuracy of non-deferred examples or predictive set sizes when employing multiple experts as opposed to a singular expert, at least in the deferral rate regimes tested. Because we are performing experiments in the low deferral rate regime, it is likely that the deferral scheme defers similar examples to both expert types - examples the model is sure the expert(s) will get right. Thus, in Table 6, the classifier accuracy and predictive set sizes are representative for both singular and multiple experts. However, we benefit from increased team accuracy by using ensemble voting across multiple experts. In addition, per Table 6 and Figure 6, our scheme ensures smaller set sizes across all conformal methods and deferral rates tested. Increasing the deferral rate reduces the predictive set size. In Figure 7, the model and expert have a mutually beneficial relationship: the model provides smaller predictive sets on examples the expert is more uncertain on and defers examples it is less certain of than an expert.

Takeaway: D-CP provides smaller predictive set sizes on non-deferred examples for the same level of coverage. For the policy in [Mozannar and Sontag, 2020], while the number of experts does not make a difference in the resulting predictive set size of non-deferred examples, having more experts predict through majority voting improves the team accuracy.

7 Evaluation on Experts

Our second human subject experiment focuses on establishing the value of smaller set predictions and learning to defer - the 2 promises of D-CP. We choose another set of 15 examples from the CIFAR-100 test set for which we generate RAPS prediction sets with error rate α = 0.1 and D-RAPS prediction sets with deferral rate 0.2 and error rate α = 0.1. We select 12 non-deferred examples at random wherein the D-RAPS predictive set is smaller than the RAPS predictive set, but the ground truth labels are contained in both sets. Lastly, we choose the remaining 3 deferred examples where the model is underconfident, i.e. the ground truth label is not in the RAPS set. This aims to establish the value of deferral in situations where the model may provide misleading predictions. We ask participants the same questions as in Section 3 and follow a similar recruitment procedure as in Section 3 (60 participants total, 2 groups, reward of £10 per hour prorated).

Tables 4 and 5 suggest that there is a statistically significant increase in expert accuracy when the D-CP scheme is employed, with borderline significance on non-deferred examples. Even though participants did not perform as well on deferred examples in general, we noticed that their accuracy was still higher than when they were shown CP sets, which contained misleading labels. Equally interestingly, on examples where both RAPS and D-RAPS sets contain the ground truth label (i.e. the non-deferred examples), the perceived utility of D-CP sets is higher (p < 0.001). As D-RAPS sets are smaller, this shows that, for the same confidence level, smaller set sizes are more useful to experts and therefore a preferred choice for human-AI teams. Table 4 also shows a statistically significant difference in reported trust in the model between D-RAPS and RAPS. These are important considerations for real world human-AI teams. We provide further results in the Supplementary Material which show that participants display a bias towards towards incorrect predictions shown in larger CP sets, warranting caution when deploying models with large CP sets in human-AI teams.

Takeaway: There are statistically significant improvements increases in reported utility, trust, and accuracy in the model when the D-CP scheme is employed.

8 Conclusion

In this paper, we explored the importance of set valued predictions for human-AI teams. We first showed experts find CP predictive sets more useful than Top-1 predictions. However, CP set sizes can be very large for some examples, especially in large label spaces. Thus, we motivate the need for combining the ideas of learning to defer and set valued predictions. We introduce D-CP, a general practical scheme that defers some examples and performs CP on others. Empirical and theoretical evidence shows that the scheme provides smaller set sizes on non-deferred examples for any CP method compared to performing CP on all examples. The scheme allows the model and expert to have a mutually beneficial relationship by leveraging the expert and the model's respective strengths. Our human subject experiments show that, compared to CP, experts find the smaller D-CP predictive sets more useful, the model more trustworthy, and are more accurate. We hope that this informs a) future research on improved deferral policies that consider the predictive uncertainty of the model and b) larger scale human evaluations that uncover specific, desirable properties of a predictive set.

Acknowledgements

The authors thank the anonymous reviewers for their thorough feedback. UB acknowledges support from DeepMind and the Leverhulme Trust via the Leverhulme Centre for the Future of Intelligence (CFI), and from the Mozilla Foundation. AW acknowledges support from a Turing AI Fellowship under grant EP/V025279/1, The Alan Turing Institute, and the Leverhulme Trust via CFI.