Conformal prediction under ambiguous ground truth
Authors: David Stutz
Abhijit Guha Roy
Tatiana Matejovicova
Patricia Strachan
Ali Taylan Cemgil
Arnaud Doucet
Venue: Accepted by TMLR ()

Abstract: Conformal Prediction (CP) allows to perform rigorous uncertainty quantification by constructing a prediction set $C(X)$ satisfying $\mathbb{P}(Y \in C(X))\geq 1-\alpha$ for a user-chosen $\alpha \in [0,1]$ by relying on calibration data $(X_1,Y_1),...,(X_n,Y_n)$ from $\mathbb{P}=\mathbb{P}^{X} \otimes \mathbb{P}^{Y|X}$. It is typically implicitly assumed that $\mathbb{P}^{Y|X}$ is the ``true'' posterior label distribution. However, in many real-world scenarios, the labels $Y_1,...,Y_n$ are obtained by aggregating expert opinions using a voting procedure, resulting in a one-hot distribution $\mathbb{P}_{\textup{vote}}^{Y|X}$. This is the case for most datasets, even well-known ones like ImageNet. For such ``voted'' labels, CP guarantees are thus w.r.t. $\mathbb{P}_{\textup{vote}}=\mathbb{P}^X \otimes \mathbb{P}_{\textup{vote}}^{Y|X}$ rather than the true distribution $\mathbb{P}$. In cases with unambiguous ground truth labels, the distinction between $\mathbb{P}_{\textup{vote}}$ and $\mathbb{P}$ is irrelevant. However, when experts do not agree because of ambiguous labels, approximating $\mathbb{P}^{Y|X}$ with a one-hot distribution $\mathbb{P}_{\textup{vote}}^{Y|X}$ ignores this uncertainty. In this paper, we propose to leverage expert opinions to approximate $\mathbb{P}^{Y|X}$ using a non-degenerate distribution $\mathbb{P}_{\textup{agg}}^{Y|X}$. We then develop \emph{Monte Carlo CP} procedures which provide guarantees w.r.t. $\mathbb{P}_{\textup{agg}}=\mathbb{P}^X \otimes \mathbb{P}_{\textup{agg}}^{Y|X}$ by sampling multiple synthetic pseudo-labels from $\mathbb{P}_{\textup{agg}}^{Y|X}$ for each calibration example $X_1,...,X_n$. In a case study of skin condition classification with significant disagreement among expert annotators, we show that applying CP w.r.t. $\mathbb{P}_{\textup{vote}}$ under-covers expert annotations: calibrated for $72\%$ coverage, it falls short by on average $10\%$; our Monte Carlo CP closes this gap both empirically and theoretically. We also extend Monte Carlo CP to multi-label classification and CP with calibration examples enriched through data augmentation.

Published in Transactions on Machine Learning Research (10/2023)
Conformal prediction under ambiguous ground truth
David Stutz', Abhijit Guha Roy", Tatiana Matejovicova', Patricia Strachan', Ali Taylan Cemgil', Arnaud Doucet'
!Google
DeepMind, "Google
{dstutz, agroy, tatianama, trishs, taylancemgil, arnandoocct/@ggggg..com
Reviewed OpenReview: http:///oouurreeeeeee//////////a
Abstract
Conformal Prediction (CP) allows to perform rigorous uncertainty quantification by con- structing a prediction set C(X) satisfying P(Y E C(X)) 2 1 for user-chosen a E [0, 1] by relying calibration data (X,; Y.)...., (X,, Y,) from P px & prix. It is typically implicitly assumed that pxxx is the "true" posterior label distribution. However, in many real-world scenarios, the labels Yı...., Y, are obtained by aggregating expert opinions using voting procedure, resulting in one-hot distribution paix vote This is the case for most datasets, even well-known ones like ImageNet. For such "voted" labels, CP guarantees are thus w.r.t. Pvoce- px PXIX rather than the true distribution F. In cases with unam- biguous ground truth labels, the distinction between Prote and IP is irrelevant. However, when experts do not agree because of ambiguous labels, approximating P with one-hot distribution X ignores this uncertainty. In this paper, we propose to leverage expert opinions to approximate p using non-degenerate distribution Pags We then develop Monte Carlo CP procedures which provide guarantees w.r.t. Pags = P P Pagk by sampling multiple synthetic pseudo-labels from PYIX for each calibration example X,, In case study of skin condition classification with significant disagreement among expert anno- tators, we show that applying CP w.r.t. Pvote under-covers expert annotations: calibrated for 72% coverage, it falls short by on average 10%; our Monte Carlo CP closes this gap both empirically and theoretically. We also extend Monte Carlo CP to multi-label classification and CP with calibration examples enriched through data augmentation.
1 Introduction
Many application domains, especially safety-critical applications such as medical diagnostics, require reason- able uncertainly estimates for decision making and benefit from statistical performance guarantees. Con- formal prediction (CP) is a statistical framework allowing to quantify uncertainty rigorously by providing finite-sample, non-asymptotic performance guarantees. First introduced by Vovk al. (2005), it has be- come very popular in machine learning as it is widely applicable while making no dsitributional or model assumptions, e.g,, see (Romano et al., 2019; Sadinle et al., 2019; Romano et al., 2020; Angelopoulos et al., 2021; Stutz et al., 2021; Fisch et al., 2022) and Angelopoulos & Bates (2021) for more references.
Specifically, we consider a classification task with K classes and denote by [K] the set (l...., K}. Then, a classifier म : X + A outputs the class probabilities where AK is the K-simplex. Based only on held-out set of calibration examples (X,, Y2) ~ P, CP allows us to return a prediction set C(X) C [K] for given test point (X,Y) (with Y being unobserved) dependent on the calibration data such that
IP(Y E C(X)) 2 21-00 02
(1)
whatever being IP and as long as the joint distribution of ((X,,Y)),... Yi)...,, Yn), (X,)(X)))) exchangeable. Here [0, 1] is a user-specified parameter and the probability in Equation (1) is not only over (X, Y) but

---

Published in Transactions on Machine Learning Research (10/2023)
Distribttion human annotation
Distribution human annotations
arpll
turne
Gees
Figure 1: Two ambiguous examples from CIFARI0-H (Peterson et al., 2019) with the corresponding anno- tations of p= 50 experts. These annotations can be used to build P Pa = y|X = x. y yi,..,, YP), see lext for details.
also over the calibration set. This is called the coverage guarantee of CP. The size of such prediction sets [C(X),, also called inefficiency, is a good indicator of the uncertainty for X.
It is commonly taken for granted that I = px & px|x where pr|x is the "true" posterior label distribution so that the l.h.s. of Equation (1) is the probability for the ground truth label Y being an clement of the prediction set C(X). However, in many practical applications, the calibration labels (Y:)se(m) are obtained based on (multiple) expert opinions. In medical applications, for example, it is usually impossible to identify the patient's 's actual condition as this would require invasive and expensive tests. Instead, labels are derived from expert annotations, c.g., doctor ratings (Liu et al., 2020). Beyond medical diagnosis, however, this is generally the case for many popular dalasets such CIFARIO (Krizhevsky, 2009; Peterson et al., 2019), COCO (Lin et al., 2014), ImageNet (Russakovsky et al., 2015) or many datasets from the GLUE benchmark (Wang et al., 2019) such as MultiNLI (Williams ct al., 2018) (sec Appendix A). Based on the expert anno- tations, the majority voted label is then typically selected as the ground truth label. Formally, this means that we consider V ~ (- = xx) where (Votee =y=yp y X = x) is a one-hot distribution. Thus, when using CP on these voted labels, we obtaín guarantees of the form P Poote E C(X) 2 1 1 for Pvote P & PYXX rather than a guarantee w.r.t. to the true distribution, PPY E C(X)) 2 1 1- a. The difference between Poot and P is small for some tasks, including popular benchmarks such as CIFAR10, bocause most examples are lairly unambiguous, meaning that annotators do rarely disagree because P(Y = y| = x) is one-hot anyway and a simple aggregation strategy can unambiguously determine the true class. However, in complex tasks such the dermatology problem addressed in this work, there are many examples where experts disagree. More importantly, this disagreement is often "irresolvable" (Schackermann et al., 2016; Gordon et al., 2022; Uma et al., 2022), meaning that obtaining more annotations will likely not reduce disagreement. In such cases, IYotte (Y = y|X x) differs significantly from the true conditional distribution P(Y y|X =x)
In such scenarios, performing CP using voted labels can severely underestimate the true uncertainty (see Section 2.2 for an intuitive example). Instead of summarizing the expert annotations by a single one-hot distribution, we propose here to rely on an approximation of IP PYagg(Y = y/ x) to P(Y = y x) to better account for this uncertainty. As a simple example, assume that for each calibration data X, expert g [p] annotates single class Y [K] as done CIFAR10-H (Peterson et al., 2019), an illustration. Then, let Pa= = Σ I(Y" k) be the number of experts selecting class k. a simple voting procedure sets Pvote = x = x. "....,Yy = T(y = Y) where y = arg max Pk (disregarding ties for simplicity) and unconditionally we also typically will have Poote = x = x) a one-hot distribution in unambiguous cases (i.e. the same label is selected for all expert annotations). Obviously, if there is sufficient disagreement among annotators, taking y will ignore many of the (usually expensive) annotations. As result, performing CP on the voted labels ignores this uncertainty. Instcad, we argue that selecting aggregated distribution, e.g., (Y v|X x, y1 ...., .P.. capture uncertainty presont in the annotations. Idcally, by integrating over (Y!,..,, YP), the resulting IP PaRK is a good approximation of the true distribution (and we discuss common ways of constructing IF Fags Section 3.1).
Figure 1 for
EkEjK] pally = k), allows us to better
2

---

Published in Transactions on Machine Learning Research (10/2023)
Contributions: In this paper, propose CP procedures that allow us to construct a prediction set C(X) satistying (Y E C(X)) 2 1 - a for PARK = px 2 PPgs as long as one can sample from Pygg Note that while would be desirable to have instead guarantees w.r.t. the distribution P. this an impossible task as we never observe any data with labels sampled from pP|x Whether PYI is a good approximation to pY|x will be application dependent. Instead, the prediction set C(X) outputted by our procedures is the one we could compute if the experts had access to X and their opinions were aggregated through Pags This is the best one can hope for. We emphasize that we are not making more model assumptions than is currently made by applying CP to voted labels from PYxx In contrast, make the usually implicit assumptiins on label collection explicit. To perform calibration with PY we propose a sampling-base approach, coined Monte Carlo CP, which proceeds by sampling multiple "pseudo ground truth" labels from Pag for each calibration example XI,...,X, We show how this approach can provide rigorous coverage guarantees despite not having access to exchangeable calibration examples. We present experiments on a skin condition classification case study: Here, calibration with voted labels from P is shown to under- cover expert annotated labels by a staggering 10%. Our approach closes this gap both theoretically and empirically. Moreover, we discuss extensions to multi-label classification and calibration with augmented calibration examples for robust CP.
Outline:
The rest of this paper structured as follows: In Section 2, we illustrate the problem on a toy dataset and introduce required background on CP. Then, Section 3 introduces our original Monte Carlo CP procedures, highlights the applicability of this approach to related problems and discusses related work. In Section 4, we present application to skin condition classification following (Liu et al., 2020), multi-label classification and data augmentation before concluding in Section 5.
2 Background and Motivating Example
2.1 Conformal prediction
In the following, we briefly review standard (split) CP (Vovk et al., 2005; Papadopoulos et al., 2002). To this end, we assume a classifier (x(x)) x P(Y = y| x) approximating the posterior label probabilities is available. This model will be typically based on learned parameters using a training set. Then, given a set of calibration examples (X,, Mi)e(()) from P, we want to construct prediction set C(X) S [K] for the test point (X, Y) such that the coverage guarantee from Equation (1) holds. As mentioned earlier, this requires the calibration examples and the test example to be exchangcable but does not make any further assumption on the data distribution or on the underlying model m.
A popular conformal predictor proceeds as follows: given a real-valued conformity score E(X, k) based on the model predictions (2)) E A we define
C(X) = [K] E(X, 2
(2)
where 5 is the La(n+ + 1)J smallest element of (F(X,, V.))en) equivalently 7 is obtained by computing the [a(n + 1)J/n quantile of the distribution of the conformity scores of the calibration examples
T == (IF(X (i)K)a)
La(n + 1)1
(3)
n
Here, Q(:gg) denotes the q-quantile. By construction of the quantile, see c.g. (Romano et al., 2019; Vovk et al., 2005; Angelopoulos & Bates, 2021), this ensures that the lower bound on coverage in Equation (1) is satisfied. Additionally, if the conformity scores are almost surely distinct, then we have the following upper bound IP(Y E C(X)) < 1 - a + n+I. The conformity score is a design choice. A standard choice, which we will use throughout the paper, is E(z, k) = T& (x) (Sadinle al., 2019) but many alternative scores have been proposed in the literature (Romano et al., 2020; Angelopoulos et al., 2021).
1
Pggs but only exchangeable ones. This prevents the use of concentration inequalities obtain bounds on PY E C(X) = for given C(X).
1 As explained further, we cannot obtain i.i.d. samples from P X
3

---

Published in Transactions on Machine Learning Research (10/2023)
baarstes to ther out lids unndery
Cont, scores
p-vallsss
Posteriors
Cont, scores
p.voluuss
1: Posteriors
1.00
preduse for clask
Flx (5 maale
0.4
0.6
0.35
0.2
0.4
0.1
01
0.2
X 022
0.0
0.0
03 34
25
3.4
14
Class
Class
Clas
Class k
Class k
Class
Figure 2: Illustration of CP on toy dataset detailed in Section 2.2 for two examples X, indexed 0 and 1. Here, the conformity scores (E(X,)))ke are taken to be the estimated posterior probabilities Ty. (X) of a multilayer preceptron (MLP) whose decision boundaries are shown. To construct the prediction sets C(X), these scores are thresholded using the threshold т, cf. Equations (2) and (3). Equivalently, we can use the p-value associated formulation and threshold (Py)yE(K) at confidence level a, of Equations (4) and (5).
Calibrating against true labels, both approaches obtain coverage a (w.r.t. the true labels).
An alternative view on CP can be obtained through a p-value formulation; see e.g. (Sadinle et al., 2019). The conformity scores of the calibration examples and test example (X, Y) are exchangeable so if the distribution of E(X,Y) is continuous then
PY | E [m]: E(X,, Y,) & E(X, +] E. T[ V.) S E(X, +1 n ++1
(4)
n 1+
is uniformly distributed over {1/(n + 1),2/ + 1)..,, 1} and thus py is a p-value in the sense it satisfies P(pr I a) S a, equivalently P(py > a) 2 11aa. a. If the distribution is not continuous, then it can be checked that P(pr S <a)= S a still holds (see e.g. (Bates et al., 2023)). It follows directly that
C(X) = (v E [K] : > a}
(5)
satisfies P(Y E C(X)) 2 1-aa and the prediction set obtained this way is identical to the one obtained using Equations (2) and (3). For completeness, the equivalence between both formulations is detailed in Section B.1 of Appendix B. In contrast to calibrating the threshold т, the p-value formulation requires computing (p=) for each test example X and is thus computationally more expensive. The p-value formulation will be useful in our context as p-values can easily be combined to obtain a new p-valu;; see e.g. (Vork & Wang, 2020). We illustrate an application of CP to a 3-class classification problem in Figure 2.
2.2 Motivating Example
We now consider a toy dataset to illustrate the impact a voting strategy can have on prediction sets produced by CP. Consider the true distribution = pa & P pp & paxlx be defined as follows: pxlx admits a density p(xly)= = [x; My d)))(oz)) with By E Rd and diag(a)) E RRdxd being mean and variance. Further, one has P(Y y) Wy with Σx wy = 1. To generate examples (X,Y) P, first sample Y from P(Y =) y) = Wy and then X from p(xll)) so we have ground truth labels for each example. Furthermore, by Bayes' rule we have access to the true posterior probability mass function IP(Y = v|X = x). If the Gaussians are well-separated, P(Y = y x) will be crisp, i.e. close to one-hot with low entropy. However, encouraging significant overlap between these Gaussians, e.g., by moving the means (He) close together, will result in highly ambiguous P(Y = y|X
x). We sample examples (X,, Yi)ke()) as outlined above and indicate classes by color in Figure 3 (top left). These synthetie data were previously used in the example displayed in Figure 2 to illustrate CP. The true posterior label probabilities TP(Y, = y =x)) are also displayed, cf. Figure 3 (top middle). As can be seen, these distributions can be very ambiguous in between all three classes. Let us assume large set of annotators that allow us by majority vote to recover & == arg max P(Y = = = X,), i.e,, the voted label, as shown on Figure 3 (lop right). This defines the one-hot distribution Pooto = y) X.) = I(y Y.). Clearly, these voted labels ignore the fact that pr|x can have high entropy.
Contrary to Figure 2, we now perform standard split CP using calibration data relying on the voted labels (X,, 8))s(( from Prote p.x & PYI rather than (X,, Y.)vetn) from PP px PYIX using a conformity
4

---

Published in Transactions on Machine Learning Research (10/2023)
Smooth, true and voted labels on toy dataset
Examples with their smooth labels
Examples with their true labels
Examples with their voted labels
Class
Clss 0
Class
Caass
0.5
0.4
Clsss
0.5
Clss 2
X
X 0.4
0.4
0.2
0.2
0.2
0.2
0.8
0.6
Calibration with voted labels
Callbration with voted labels
Coverage w.r.t.
0.14
Targe:
Cove uge true label
true labels
Cave word lubes
0.08
0.05
Coverage w.r.t. voted labels
coverage gap
Empintcll coverage
Figure 3: Illustration of an ambiguous problem with K 3 classes, in two dimensions, using toy dataset. Top: We show examples colored by their true posteriors P(Y = y|X x) (left), true labels (middle) and voted labels, i..., Y = arg m P(Y = y|X = x) (right). Note the high ambiguity between the classes, which is clearly ignored in the voted labels. Bottom: Empirical coverage over random aalibration/tess splits, i.e. the proportion of true or voted labels included the constructed prediction sets C(x), when calibrating against the voted labels. This produces prediction sets that significantly undercover w.r.t. true labels. Figure shows how our Monte Carlo conformal prediction, as introduced in Section 3, overcomes this gap.
score E(x,, k)) = TT(x) where TA (1) is given by multilayer perceptron. We randomly split the examples in two halves for calibration and testing. In Figure 3 (bottom), we plot the empirical coverage, i.c., the fraction of test examples for which (a) the true label (blue) or (b) the voted label (green) is included in the predicted prediction set. In this case, CP guarantees the latter by design, (b), to be 95% (on average across calibration /test /test splits). Strikingly, however, coverage against the (usually unknown) true labels is significantly worse. Of course, this gap depends on the ambiguity of the problem.
3 Monte Carlo conformal prediction
As discussed in the introduction and illustrated in Section 2.2, want to avoid using one-hot distribution P when labeling ambiguous examples. Instead we first explain here how, based on expert opinions, we can obtain non-degenerate estimates y of pYiX, We then show how PPgS can be leveraged to provide novel CP procedures for constructing prediction sets that satisfy coverage guarantees w.r.t. Pags = IP & P.Y XX Given that we never observe labels from the true distribution priX providing guarantees w.r.t. Pags the best we can hope do. For test example X, this can be understood as guaranteeing coverage against labels that expert annotators would assign if they had access to X and their annotations were aggregating using P
3.1 From expert annotations to PIX
From now on, we assume that we have calibration data (X,, Bi) ~ P for i [n] and a test data X, B ~ P with B unobserved; the joint distribution of (X,, Bi)kejs) and (X, B) being exchangeable. Here B, corresponds to a set of expert annotations, the space of annotations being dependent on the application. For example, on CIFAR-10H (Peterson et al., 2019), each expert provides a single label in [K]. In contrast, in our dermatology application, using data from (Liu et al., 2020), B, represents a set of partial rankings whose cardinality depends i. This corresponds to differential diagnoses from dermatologists. However, while
5

---

Published in Transactions on Machine Learning Research (10/2023)
the format of the B''s can vary, always interested in returning prediction sets of classes C(X) S [K] satisfying a coverage guarantee w.r.t. Pagg where IP Pagg needs to be specified based on the expert annotations 2
We give two simple examples to illustrate how F Pag can be obtained and then present a more generic framework. However, the aim of this section is not to provide the best way to aggregate expert opinions. This is application dependent and there is a substantial literature on the topic. Instead, we focus here on showing how such techniques can be exploited in CP framework:
Single labels: We first revisit and exlend the construction presented in Section where B (Y',..,, YP) with Y E [K] corresponding the single label the expert q assigns to X. We then consider Pagg (Y = B)
1/ ExeiK] Pxl(y = k) for pk - 1(Y k)². Note that this approximation is deterministic given (X, However, we could also use a bootstrap procedure by resampling the entries of B with replacement.
Partial rankings: In medical applications, it is common for expert annotations to be given by differential diagnoses, corresponding to partial rankings. That is, out of the K possible conditions, each expert returns a partial ranking of conditions because multiple conditions are deemed plausible while large majority of the conditions can be excluded. While probabilistic models for aggregating such rankings exist (Hajek al., 2014; Zhu et al., 2023), we follow (Liu al., 2020) and describe simple deterministic procedure called inverse rank normalization which we will also exploit in experiments, see Section 4.1. Let B = (B',... ,.... B²) be the collection of available partial rankings for data X. Each partial ranking 8 is divided into ny blocks, 1 = (B% B4 ), with B eC [K] and
B 0 and B% the collection of excluded conditions. The conditions in Bi are assessed being more plansible than the conditions in B3 for j. We then define
p Rg-1
0g
B I(y E BD),
F Pagg(( (Y = g)
Cgy K
(6)
2k=1
Oz
As above, this approximation is deterministic given (X, B). Again, we could also use a bootstrapping procodure by resampling the entries of B with replacement.
More generally, we assume the distribution of B) admits a density p(a, b). Then, we will denote by x = (x) the probabilities (Pagg(Y B). P RY = K|X, B)) obtained by some deterministic or stochastic annotations aggregation procedures. We refer to À as plausibilities since they quantify how plausible the different classes are to be the actual ground truth label given the annotations B. Then, the
resulting marginal density of (X, X) is given by
p(x,)) / D(Zr,,, / x(),,
In the examples above, note that p(A(b,z)) p(Al)). Then, our aggregation model for label Y can be written as
PP Pagg (V = y|x= = x) = P(UIANAAMMONN / /
(8)
In words, p(blz)) corresponds to the annotation process, i.c., how exports draw their annotations when observing data v, and a()(,,z)) models aggregation of annotations into plausibilities. Given data (X, p(z, b), then B is distributed according to X)b given X. So by sampling À ~ P(A|B, X) and then Y such that P(Y = A) = Xy. we obtain a sample from P Pagg (Y = y XX) Note however that we cannot obtain i.i.d.
Based this setup, could in principle develop a CP method returning prediction sets for B, e.g. prediction sets of rankings, satisfying coverage guarantee w.r.t P. However,
interested here in prediction sets for labels.
3p &aage (Y = X| B) obviously converges towards PP(Y x) as p oc if yo i.d. Page ())(())), Le., this assumes that expert. annotations fallow the true distribution P.
6

---

Published in Transactions on Machine Learning Research (10/2023)
Algorithm 1 Monte Carlo CP with 1- coverage guarantee for m = 1 and 1 - 2ox for m 2 2. Input: Calibration examples (X,, Ai)e[[j] test example X; confidence level a; number of samples m Output: Prediction set C(X) for test example
1. Sample m labels (Y:)) Jelm) per calibration example (Xi)ieja) where PPY? = k) = Ask-
2. Calibrate the threshold 7 using
T T= Q ( (B(Xs)
Lam(n + 1]] - m 1
(10)
mm
3. Return C(X) {k E [K] E(X,)) k)) n..
Monte Carlo conformal calibration
0.175
Target
Figure 4: Monte Carlo CP with m 10 sampled labels per cali- bration example (see Algorithm 1) applied to the toy datasel from Figure 3. We use the true posterior probabilities PP(Y = y = x) as plausibilities Ay to sample labels (see Figure 3, left). Again, we show coverage wrt. true or voted labels. In contrast stan- dard CP calibrated against voted labels, Monte Carlo CP clearly obtains the target coverage (black) of 1 - 95% (on average) w.r.t. the true labels.
Coverage of true labels
Frequency
0.125
Coverage voted labels
0.100
0.050
0.025
0.000
0.94
0.95
0.96
0.97
0.98
0.99
Empirical coverage
samples from (Y = x as we only have access to one sample from B given X. We can only obtain exchangeable samples by repeating sampling from x ~ p(A B, X) and P(Y = uy\) xy-- Hence we cannot use concentration inequalities to obtain finite sample bounds for quantities such Pagx (Y C(X))X x) for given C(X).
We will instead develop CP procedures returning prediction sets satisfying Pagg( (Y E C(X)) 2 a, it is worth clarifying what this means when (aggs(Y|X)) is ambiguous, i.e, not one-hot. With Pags P P Pags we can rewrite the coverage guarantec as
I Pagg (Y E C(X)) Ex-ex (xx)) e C(X)I]]
(9)
It makes explicit that, coverage is marginal across examples and classes: in ambiguous cases, the prediction set C(X) might cover only part of the classes with non-zero plausibility. We will refer to Pagg(( C(X)) defined in Equation (9) as aggregated coverage to emphasize that this is w.r.t. Pagg- This is to contrast from voted coverage (Y E C(X)) which is w.r.t. Pvote. To obtain prediction sets with aggregated coverage guarantees, we will assume access to set of exchangeable calibration data (X,, Ai) of examples and corresponding plausibilities from p(z, A). To obtain this calibration data, we can simply rely on the orig- inal (exchangeable) calibration data (X,, Bi) and then sample X; ~ p(, B:) where X = (Ara..., ..x).. In the examples given above, A is given deterministically given (X,, B,) so p()|a, b) is a delta-Dirac mass but, if a bootstrapping procedure is used account for uncertainty in the annotation process, then it is not anymore.
3.2 Introduction to Monte Carlo conformal prediction
We propose Monte Carlo CP, a sampling- approach to CP under ambiguous ground truth. Given the calibration examples (x)())) we sample m labels Y for each X, according to plausibilities A i..
P(Y:' k) = Au and duplicate the corresponding inputs". That is, we obtain m n new calibration examples (X,, YY') ve') JE(m] and then apply the conformal calibration outlined in Algorithm 1. As shown in Figure 4, Monte Carlo CP overcomes the coverage gap illustrated on our toy dataset in Figure 3.
AAn alternative valid procedure would sample m plausabilities Xf ~ p(1),, B,) for each X, and then Y? such that F(Y/) = k) X/e- When p( X3, B.) delta-mass distribution for i, this coincides with the procedure described previously.
7

---

Published in Transactions on Machine Learning Research (10/2023)
Variation in aggregated coverage from sampled babel
Aggregated coverage for 10% callbration data
Standard devistion in aggregated coverage
Aggregated overuge
Target
0.150
0.175
Target
samp labels
ampincal couecage
m-1 sampled laves
m-5 sampled lose's
m= samp ed labels
0.125
10 samoled labul
0.005
0.100
0.004
2.075
0.003
3.000
2.025
0.002
2.000
0.945
0.943
0.900
0,052
0.004
0.956
090
0.11
0.92
0.33
0.23
0.06
0.97
0.00
0.2 0.3
Empiiical coverage
Empliicll coverage
Left: Empirical aggregated coverage for Monte Carlo CP, m 1, with fixed calibration /test split but different randomly sampled labels Y?, ef. Algorithm 1. The approach obtains coverage 1- across calibration /test splits but overestimates coverage slightly for this particular split. However, in Monte Carlo CP, coverage is marginal across not only test and calibration examples but also the sampled labels during calibration, as shown in this histogram. Middle and right: Instead fixing the sampled labels for different m and plotting variation in coverage across random calibration/tess split shows that aggregated coverage is empirically close to a even for m > 1. Large m generally reduces the variability in coverage observed across calibration/tess splits, especially for small calibration sets (we consider 5% to 50% calibration data).
Figure 5:
The aggregated coverage guarantees we will provide for Algorithm 1 are marginal over the sampled la- bels (X))) This is illustrated in Figure 5 (left) on the toy dataset of Section 2.2 using a fixed calibration ciatiiiontsstt test split but multiple samples of (Y,") (e) The empirical aggregatod coverage across cal- ibration/test Lest splits is - (see Figure 5 (left)) but the variability across such splits is high if the entropy of PY is high for many calibration data. This variability can be reduced by increasing m (sce Figure 5, right), this is especially beneficial in the low calibration data regime.
We now discuss the theoretical coverage properties of Algorithm 1. Recall that we have assumed in Section 3.1 that the joint distribution of Be)agjn and a test data (X, B) is exchangeable. This implies that the joint distribution of (X,, XY)x))) and (X, Y) is exchangeable for any j E [m]. For m = 1, it is clear that this approach boils down to standard split CP applied to calibration data (X,, Y,") ~ Pagg and thus P (Y E C(X)) 2 - a follows directly. For m 2 2, the calibration examples include mn repetitions of each X; and exchangeability with the test example X, typically used to establish the validity of CP, is not satisfied anymore. Nevertheless, mentioned carlier, we empirically observe an empirical coverage close to --a on average in Figure 5 (middle).
In the following, Section 3.3, we focus on establishing rigorous coverage guarantees for Monte Carlo CP when m 2 2, showing that we can establish PA E C(X)) 2 1 - 2a. This is akin to the observation in (Barber et al., 2021) that jackknife+, cross- cross-conformal or out-of-bag, CP consistently obtain empirical coverage 1 a while they only guarantee
2a. In applications where rigorous coverage guarantees better than 1- 2a are necessary, we show in Section 3.4 that this can be achieved by developing an alternative Monte Carlo CP procedure presented in Algorithm 2 which relies on additional split of the calibration examples.
3.3 Coverage - 2a by averaging p-values
In order to establish the coverage guarantee Page ( (VE)(X)) 2 1 - 2a when m 2 2 for Algorithm 1, let us introduce for j E [m]:
By EELTTE [[ Y/) < F(X,Y))
(11)
n ++1 1
The random variables Pe are p-values, iee Plpy S a) S a, since the scores (F((,, Y2) het and (E(X, Y)) are exchangeable for fixed j E [m]. We can now average these quantities over j E [m]] to obtain
T Ci [E(X, v!) s EXX,Y) +1)
1
m
py
(12)
m
min + 1)
8

---

Published in Transactions on Machine Learning Research (10/2023)
= 1+ [[E v.) & B(r,k)
po = rr//ut1
1 1+ Σ [ v B(z,)) p = =rt/n+1
Tx((a) I
Exx, k)
F(x))
r3" = 1+ Ex [[E( v(") S B(r,k)] - p8 /2/n+11
Figure 6: The m label samples result in (pL)se(m) for the test example X, (py (e(m))) being p-values. We can average & over j and threshold the resulting average Pa at level a to obtain the prediction set, this is equivalent to Algorithm as explained in Section 3.3. Alternatively we can combine the p-values by using the ECDF approach described in Section 3.4; see Algorithm 2 for a detailed computational description.
As py is average of (dependent) p-values, it follows from standard results (Rüschendorf, 1982; Meng, 1994) that PP(ppy < 2a) < 2a, equivalently P(βr > a) 2 1 - 2o.. Hence we have P(Y C(X)) 2 1 - 2a for C(X)= = (y E [K] Py > a). Nevertheless, as discussed previously, we obtain empirical coverage close to a- cf. Figure+ 5 (middle), see also the discussion in (Barber et al., 2021, Section 4). This approach is illustrated in Figure 6. Note that in the context of aggregating m different models, Linusson et al. (2017)
also considered similar types of averaging.
Practically, we do not have to compute and actually average Pg for j E [m] and y E [K] to determine C(X) {y [K] Py a}. As in Section 2.1, reformulate this prediction set as C(X) { [K] E(X,k) 2 r} as in Equation (2) where r the (em(n+1)] [-]m-++- smallest element (E(X,, be) equivalently is obtained by computing
T == ( (F(X,,
[am(n + 1)] +
(13)
mn
and confidence sets are constructed C(X) = {k [K] E(X, 2 r) for given in Equation (10). This is established in Section B.2 of Appendix B.
3.4 Beyond coverage 1 -2a
The 1 1-2a coverage guarantee from Monte Carlo CP arises from the fact that we use a standard result about average of p-values (Risscendorff, 1982; Meng, 1994). When the p-values independent, few techniques have been proposed to obtain 1 coverage; see e.g. (Cinar & Viechtbauer, 2022) for comprehensive review. However, in our case, the valuue (py))e(m)) we want to combine are strongly dependent as they use the same calibration examples X, and then rely on different pscudo-labels Y? from the same distribution (given by As). In this setting, many standard methods yield overly conservative results.
We follow here method that directly estimates the cumulative distribution function (CDF) of the combined, e.g., averaged p-values (Balasubramanian et al., 2015; Toccaceli & Gammerman, 2019; Toccaceli, 2019). Let PY = 1/m EØ= Py be the averaged p-values. As shown in Figure 7 (left), these averaged p-values will not be uniformly distributed. However, if F denotes the CDF of py, then PY F(rr) is a p-value" and thus the prediction set C(X)- (y E [K] Py > a} will obtain coverage - The true CDF is unknown but we can split the original calibration examples into XI and X and used the second split to obtained an empirical estimate F of F. The procedure is doscribed in Algorithm 2.
As F is not the true CDF F but an empirical CDF (ECDF) estimate, C(X) (v E [K] F(2,) > a} would only provide an approximate coverage guarantee at level 1- a. However, the original calibration examples XI+1,..,, Xn are iid., then the
incquality (sce c.g. (Wasserman,
We have F(F( S =(F(F(((- < f) for uniform random variable on 10, 1] for F-1()) inf(peR: F()) f.. However (FF) P(F(F-1()) < f) < P(U S $ = f. Hence, we have P(py a) a.
9

---

Published in Transactions on Machine Learning Research (10/2023)
Distribution of combined p-values
ECDF correction of p-values
Averaged p-values FCDF
1.0
Baseline
ECDF
0.10
Requenty
0.08
0.06
Empirical
0.04
0.0
0.2
0.4
0.6
0.8
1.0
0.6 0.8
Value
Target coverage
Figure For illustration, we sample 10k p-values for m 10 independent tests and duplicate them obtain m 20 dependent tests. Left: Histograms for averaged and ECDF-corrected p-values. The ECDF correction is able to ensure that p-values are distributed approximately uniformly. Right: Target confidence level plotted against the empirical confidence level when calibrating with averaged p-values (blue) and ones (green). The Dvoretzky-Kiont Kieferr--Kiee----- -eee--iieeeffowweeeeee Wolfowitz inequality provides tight finite-sample guarantees on the ECDF correction, using here = 0.0001 = 0.01%.
the
Aggregated coverage of ECDF based approach
Target
Monte CP
Figure 8: On our toy dataset, we plot aggregated coverage ob- tained using Monte Carlo CP without and with ECDF correction for 10 and I [w/2]_ As expected, Monte Carlo CP, even for 2 2, does not result in reduced coverage. Thus, ECDF correc- tion does not yield meaningfully different results besides exhibit- ing higher variation in coverage across calibration/teen test splits due to the additional split I.
0.12
BCDF Monte
0.10
0.08
0.04
0.02
0.00
0.94
0.95
0.96
Empirical coverage
2006)) provides rigorous finite sample guarantees for the ECDF, i.e.
P( sup SE(o.1]
[F()) - > e) < 2ee22xxx2222 -))?).
(14)
Basic manipulation results in a confidence band for F
P(V E [0,1), < F() < (() 2 1-8 with P=(f)
min
F()+ V 2(n -)
2 1 log 6 0
(15)
max
This confidence band is illustrated shown in Figure (right). We can now define the prodiction set C(X) (v E [K] Py > a for pv = F+ (σv) and show that it satisfies P Pagg(( E C(X)) > (1 (1)1-)) Indeed, writing F+ 2 F abbreviate (f) 2 F(f) Vf, we have (py+(py) > a) 2 P(F+ (pr) >
>
F) 2 ((F(py) > a F. > F)P 2 F). Now have from Equation (14) that P(F, 2 F ô and
P(F(pr) > a,F, F) P(F > a) as the probability in Equation (14) is over (X, ()) while
Py is only a function (X,, )e).).smm and (X,Y). Using the fact that P(F(py) > a) 2 1 1-aa a, we obtain the desired coverage guarantee.
Figure 8 compares the empirical coverage obtained using standard CP with true labels both approaches of Monte Carlo CP (ef. Algorithms 1 and 2) to verify that this approach indeed obtains coverage - (1 - a1 a1 - 8) average for 8 < 1. As discussed, without the ECDF correction discussed here, this is only empirical as the approach discussed in the previous section can only guarantee 1 1 2a. We also did not observe a significant difference in prediction set size when using or not using the ECDF correction.
3.5 Summary
We have presented two Monte Carlo CP techniques, Algorithms 1 and 2, which rely on sampling multiple synthetic pseudo-labels from PYIX X for each calibration data. In this setting, the coverage guarantees
agg
10

---

Published in Transactions on Machine Learning Research (10/2023)
Algorithm 2 ECDF Monte Carlo CP with (1 a)( 5) coverage guarantee.
Calibration examples (X,, At)eEjnii test example X; confidence levels a, o; data split 1 1 n -- number of samples m Output: Prediction set ((X) for test example X
Input:
1. Sample m labels (Emm) per calibration example (Xi)eej where PVY2 k) = Aik-
Sample one label Y per calibration example (X)))e where P(Y, k) Ask-
3. Compute (()),.)))....)))) where
Σ j=
Ep=1 [[ yB) S E(X, E()x m(l + 1)
p
(16)
4. Build the ECDF F()) = - Ei=141 1lp S f] and its upper bound Ff) using Equation (15).
5. For Lest example X, compute for l: E [K]
=== 2p [[((p, YB) S E(X, x))
Pk
Pk
carr
FF()))
(17)
mll + 1)
Return C(X) {k E [K] Pk prorr a).
obtain have to be understood marginally across calibration examples and their sampled labels. We summarize the advantages and drawbacks of these methods in Table 1. In the following, we show that these developments are relevant beyond the setting of ambiguous ground truth and discuss related work.
Theoretical coverage
Avg. empirical coverage
Variability emp. coverage
Additional calibration split
Procedure
Alg. m
a (1
a 1
High Low
No
Alg. 1, m 2 2
1- 2a
No
Alg. 2
(1 8)
(1 - o1 8)
Low
Yes
Table 1: Overview of the proposed Monte Carlo CP procedures in terms of the provided theoretical cover- age guarantee, the observed empirical coverage (averaged across sampled pseudo labels), variability of the empirical coverage (w.r.t. sampled pseudo labels) and whether an additional split of the calibration data is required.
3.6 Applications to related problems
Multi-label classification: Let Vi C [K] be the known, ground truth multi-label set for each calibration example X,. For simplicity, we express the multi-label setting using plausibilities xç that divide probability mass equally across the I, = D.I labels. We can then apply Monte Carlo CP to this setup. When m > 1, we obtain calibration examples where the proportion of (Y?') equal a given class approximately 1/4. This is related
empirical existing method to perform multi-label CP (Tsoumakas & Katakis, 2007; Wang et al,, 2014; 2015) where for each calibration example (X,,J) we perform CP using the calibration examples (X,, Y,),,..,,,,,,....... Y.4). Monte Carlo CP provides coverage guarantees on Pagg( (Y C(X)) for
P Page (Y yl|' =x) Σ A(2), p(1[z)
(18)
with p(2/lz)) being the conditional probability of the set y given X = x and A()), T④y 3//////
11

---

Published in Transactions on Machine Learning Research (10/2023)
Data augmentation and robustness: Consider scenario where we have exchangeable calibration data (X,, (i) for Y; E [K]. We want to augment the set of calibration data by using data augmentation, i.e for each x ;= X; we sample additional X!" ~ p(-1X,). For example, these could correspond to versions of X, which are (adversarially or randomly) perturbed or corrupted, rotated, flipped, etc. As we usually train with data augmentation and frequently want to improve robustness against distribution shifts or specific types of perturbations, considering these angmentations for calibration is desirable. However, when using the augmented set m n of calibration data (X, (e) the joint distribution of calibration data and test data is not exchangeable anymore. However, we can still provide rigorous coverage guarantees using a procedure very similar to Monte Carlo CP. For each test data (X, Y), we set X = X and sample augmentations X² , X ~ p(-))). We then proceed by averaging the following m p-values
dy E IEX Y)) E(X
1 m PY
m Σ py
(19)
n n+1 1
By following arguments similar to Section 3.3, the prediction set C(X², x") [K] Py >
a} satisfies P Paug( (Y E C(X', ,x? x²)...,"))) 2 2a where I' Faug is the joint distribution of the test data (X X1.Y) and the augmentations (X² ,.,, X²) Tn this case, the coverage guarantee is marginal across xx....,x²,, and (X3, ()eem))
3.7 Related work
CP (Vovk al., 2005) has recently found numerous applications in machine learning, see e.g. (Romano al., 2019; Sadinle et al., 2019; Romano et al., 2020; Angelopoulos et al., 2021; Stutz et al., 2021; Fisch et al., 2022). In this paper, we focus on split CP (Papadopoulos et al., 2002). However, there are also transductive and cross-validation/ baaliiattiionbgggnnggg bagging- inspired variants being studied (Vovk et al., 2005; Vovk, 2015; Steinberger & Loeb, 2016; Barber et al., 2021; Limusson et al., 2020). Our work is related to these approaches in that many of them guarantec coverage 1 - 2a while empirically obtaining coverage close to 1 - a. For example, cross-CP (Vovk, 2015) was recently shown to satisfy
2a guarantee (Vovk et al., 2018; Kim et al., 2020). Moreover, this guarantee is also based on combining p- valuus without making any assumption about their dependence structure.
As outlined before, our work is also related to CP for multi-label classification which faces similar challenges as CP for ambiguous ground truth (Wang et al., 2014; 2015; Lambrou & Papadopoulos, 2016; Papadopoulos, 2014; Cauchois et al., 2021). Finally, our work has similaritics to work on adversarially robust CP (Gendler et al., 2022), especially in terms of our ideal coverage guarantee.
There is also a long history of work on combining dependent or independent p-values (Fisher, 1925; Rüschen- dorf, 1982; Meng, 1994; Heard & Rubin-Delanchy, 2017). Key work has been done in (Vovk et al., 2018), showing results without dependence assumption and thereby establishing guarantees for, e.g., cross-CH Sim- ilar to us, (Balasubramanian et al., 2015; Linusson et al., 2017; Toccaceli & Gammerman, 2019; Toccaceli, 2019) use the ECDF to combine p-values but they do not provide rigorous coverage guarantees for this procedure.
4 Applications
4.1
Main case study: skin condition classification
In the main case study of this paper, we follow (Liu et al., 2020; Stutz et al., 2023) and consider a very ambignous as well as safety-critiaal application in dermatology: skin condition classification from multiple images. We use the datasel of Liu el al. (2020) consisting of 1949 test examples and 419 classes with up to 6 color images resized to 448 x 448 pixels. The classes, i.e., conditions, were annotated by various dermatologists who provide partial rankings. These rankings are aggregated deterministically to obtain the plausibilities using the inverse rank normalization procedure of (Liu al., 2020) described in Section 3.1. We followed (Roy et al., 2022; Stutz et al., 2023) to train classifier that achieves 72.6% top-3 accuracy
12

---

Published in Transactions on Machine Learning Research (10/2023)
Realized voted and aggregated coverage for CP with voted labels
Realized coverage
1.0
0.5
Aggregated coverage 62)
Voted coverage (0.73)
Argmax plausibility
0.0
200
400
600
Sorted examples
Figure 9: Realized voled coverage, i.e. [arg max An C(X.) (green), and aggregated coverage, i.e., EyEiK| Avylly E C(X))] (blue), for standard CP using voted labels, ie., arg max; Ask- Additionally, plot the maximum plausibility per example (dashed black) as proxy of ambiguity. We sort examples on the x-axis according to each plot. individually. Clearly, many cases very ambiguous and aggregated coverage is underestimated severely (62% vs. the target of 73%).
labels
Monte Carlo
ECDF Monte Carlo CP
frequency
0.100
0.125
Voted Aggrogoda coverage
Target
Freqanccy
0.125
0.300
Ago Aggregated cveraaee
Voted coverane
Target
Frequecyy
0.35
Aggredab coverage
Voced coverage
Target
0.10
0.050
0.050
0.06
0.025
0.025
0.000
0.000
0.00
0.65 Empirical coverage
0.75
0.750
0.775 0.800
0.550
0.80
Empirical coverage
Empiriaal coverage age
Freguncy
0.15
Average:
0.10
Average: 4.57
Pesuency
0.15
4.54
0.10
0.05
0.05
0.00
0.00
0.00
2.3
2.4
2.5
2.6
2.7
2.8
2.9
3.0
4.2
4.4
4.6
4.8
5.0
3.5
4.0
4.5
5.0
5.5
Inefficiency
Inefficiency
Inefficiency
Figure 10: Comparison between CP applied to voted labels (left), Monte Carlo CP (middle) and ECDF Monte Carlo CP (right) in terms of voted coverage (blue) and aggregated coverage (green) across 100 random calibration test splits (top) as well as inefficiency (bottom). We use m = 10. With voted labels does not reach the 73% aggregated target coverage (black). Monte Carlo CP overcomes this gap at the expense of higher inefficiency (bottom). Using ECDFF-corrected p-values increases observed variation slightly due to the additional calibration data split (half of the original split).
against the voted label from the plausibilities". We chose a coverage level of 1 1 73% for our experiments (with results for a = 0.1 in the appendix) to stay comparable to the base model.
In Figure 9, we highlight how ambiguous the plausibilities for skin condition classification are: in dotted black, we plot the largest plausibility against (sorted) examples. As baseline, we performed CP using the classifier's softmax output conformity scores and calibrating against the voted labels ý arg max; Aae per calibration example Ax). In blue, we plot the realized coverage by evaluating I[0 E C(X,)] per example. This is step function and roughly 27% of the examples on the x-axis are covered. Tn green, we plot the realized aggregated coverage by evaluating ΣeE[K] Awil(k E C(X,) per example. For many examples, aggregated coverage lies in between 10 showing that the obtained prediction sets only cover part of the plausibility mass. More importantly, aggregated coverage is 62% on average, i.e., significantly under-estimated by calibrating against voted labels. This is the core problem we intend to address.
While the above results consider a fixed calibration/tes split, Figure 10 shows our overall results across 100 random splits. As suggested above, on the left, we show how standard CP applied to voted labels does not achieve (as expected) the target of 73% for the aggregated coverage Page(Y C(X)) (green). As highlighted in Figure 11, the prediction sets miss highly plausible conditions. In the middle and on the right, we demonstrate that Monte Carlo CP with m = 10 overcomes this problem and achieves (on average) the target aggregated coverage of 73%. Note that coverage w.r.t. the voted label (bluc) increases alongside
6To be precise, 72.6% of the cases, the voted label from the plausibilities is included in the top-3 prediction set derived from the predicted softmax output n (2)) without any conformal calibration.
13

---

Published in Transactions on Machine Learning Research (10/2023)
CP with voted labels
Monte Carlo CP
1.00
Husiiliies
1.00
Haus Bus
Carfilence sat
Cenfde 10e
0.50
0.50
0.25
0:25
0.00
Homa
5kn Mel
Classes
Classes
CP with voted labels
Monta Caroo CP
1.00
1.00
Paus bi
12.40 app covtmag
Confidence
0.75
Contidern
agp coverget
0.50
0.30
0.25
0.00 Calc
0.00
hyod Vane
Acan
Adc
Peed
Absc Acas
Figure 11: Comparison of CP with voted labels and Monte Carlo CP on two concrete examples. Both are ambiguous cases as shown by the righ plausibilities. Monte Carlo CP clearly covers more plausibility mass (i.e., yields higher realized aggregated coverage), potentially improving patient outcome. Appendix C includes more qualitative results.
Inefficiency histogram
Aggragated coverage multé-label class Fication
0.12
Awergg:: ency
S
booel
0.150
Target
0.30
0.125
60
0155
0.050
2.075
3.04
Co
9.02
0.000
5.5
5.0
6.2
6.4
6.6
Emprical
Inefficiecy
The multi-label CP strategy of Wang et al. (2015; 2014); Tsoumakas & Katakis (2007) is a slight variant of our Monte Carlo CP approach. As shown on this example of up to two overlaid, differently colored digits, Monte Carlo CP achieves target coverage of 90% (top left). However, it free to decide how many labels to cover per examples (top middle) and, due to the poor performance of the base model (58.8% aggregated coverage), inefficiency is rather high. On the bottom, show two examples of our dataset with the corresponding ground truth label set ) (blue) and the obtained Monte Carlo p-values (green).
Figure 12:
aggregated coverage (i.e., the gap between voted and aggregated coverage remains approximately the same). In terms of inefficiency, avoiding over-confidence by improving aggregated coverage leads to significant increase in the average prediction set size from 2.66 to 4.57. However, Figure 11 highlights that this is necessary for the prediction sets to include relevant conditions.
4.2 Case study: multi-label classification
In Figure 12 we consider simple MNIST-based multi-label classification problem with to two, differently colored digits per image We trained 10 multi-layer perceptrons with 100 hidden units for each digit to determine if the digit is present the image. This simple classifier achieves 58.8% aggregated coverage when thresholding the 10 individual sigmoids 0.5. As discussed Section 3.6, common strategy (Wang et al., 2015; 2014; Tsoumakas & Katakis, 2007) of performing multi-label CP consists in repeating each example according to its number of labels (here, most 2). We achieve something similar with rigorous aggregated coverage guarantee by uniformly sampling labels to perform Monte Carlo CP. We illustrate this procedure in Figure 12 (top left) where we show that it achieves the 90% coverage target. Furthermore, our discussion in Section 3.2 establishes the corresponding guarantee of 1 - 2a without ECDF correction. However, it is important to understand what aggregated coverage means for multi-label classification: CP decides how many of the labels it intends to cover per example in order to achieve the marginal coverage guarantee. This is highlighted Figure 12 (bottom) showing the corresponding p-values for two examples. In the first example, only one out of two examples is covered by the prediction set..
14

---

Published in Transactions on Machine Learning Research (10/2023)
Standard CP
Monte Carlo CP
Monte Cario CP m 10
0.125
Targel Clear Augmented
Target Clean Augmented
0.100
Frequnccy
0.300
0.10
0.075
0.075
0.050
Target
0.050
0.05
0.025
Clean
0.000
0.00
0.86
3.86
0.88
0.90
0.84
0.86
0.88
0.90
0.92
0.94
0.88
0.90
0.92
0.94
0.96
Empirical coverage
Empinical
Empirical
Presunncy
0.15
Augmented average
Clean
3.41
Frequency
0.2
Augmented averageri.
Clean aveaage: 6.37
Frqueecyy
0.2
Clean average: 9.51 Augmentedd average:1
0.05
Augmented
Clean
0.1
Augmented
Clean
0.1
Clean
Augmented
0.00
0.0
0.0
10.0
12.5
15.0
20
100
Inoffiiincyy
Inefficinncy
Inefficiency
Figure 13: Standard CP applied to original images (left) and Monte Carlo CP (middle and right) applied to the original plus augmented images from ImageNet for m = (middle) and m = 10 (left). We show coverage on original (blue) and augmented images (green, average across 25 AutoAugment augmentations per image). Monte Carlo CP is able to increase coverage on augmented images significantly at the expense of higher inefficiency (on both original and augmented images). Using more augmentations during calibration generally increases coverage augmented images and reduces the observed variation across random calibration/tess splits.
4.3
Case study: data augmentation and robustness
We also apply Monte Carlo CP in the data augmentation and robustness setting outlined Section 3.6. Specifically, we took a pre-trained MobileNet V2 (Howard et al., 2017) achieving 71.3% (top-1) accuracy on the first 5k test examples of ImageNet (Russakovsky et al., 2015) and additionally evaluated on augmented images using AutoAugment (Cubuk et al., 2018). We generated 25 random augmentations per test example. The model achioves 60.2% accuracy on average, significantly lower than on the original images. Similarly, Figure 13 shows significant gap in coverage when calibrating only on the original images. While coverage original examples is around the target of 90%, depending on the random calibration/ters split, coverage of augmented images is only slightly above 80%. With the Monte Carlo CP procedure described in Section 3.6, we can use as calibration data the original and augmented images. This procedure increases coverage on the augmented images significantly at the cost of higher inefficiency. As coverage is marginal and thus split across augmented and original images, the coverage increase is largest when using more augmented images during calibration. We interpret these results in two ways: First, there no reason anymore to train state- of- the-arr models with data augmentation but discard augmented images during calibration. Second, our Monte Carlo CP approach is effective in improving robustness against augmentations or other corruptions.
5 Discussion
In many classification tasks, the available ground truth labels arise from voting process relying on several expert annotations resulting in a one-hot distribution PPXXX However, in scenarios where annotators tend to disagree because ground truth labels are ambiguous, this voting approach ignores the label uncertainty, Thus, performing CP with such voted labels can only guarantec coverage w.r.t. P This can have severe consequences, especially in safely-critical applications such as the dermatology case study in this paper. Instead, we use standard procedures from the literature to aggregate expert opinions and return non- degenerate conditional probability distribution PYIX that can caplure uncertainly about Y. In this paper, we proposed two Monte Carlo CP procedures which can output prediction sets satisfying some pre-specified coverage guarantees under the corresponding distribution Pags = p & PPI by sampling m exchangcable synthetic labels from Pag for each calibration data. This allows to reduce the variability of the empirical coverage across realizations of the sampled labels. For a test example X, the prediction set outputted by such procedures can be thought as the one expert would assign if they had access to X and their annotations
15

---

Published in Transactions on Machine Learning Research (10/2023)
were aggregated using P In the scenario considered here where true labels are never observed, this is the best one hope for. We have established rigorous coverage guarantees for these Monte Carlo CP procedures despite the fact that the joint distribution between the calibration data and the test data is not exchangeable. While the averaged empirical coverage provided by Algorithm 1 is 1 a, our theoretical result only guarantees 2x. In applications where rigorous tighter theoretical guarantees are required, we show how it is possible to modify this procedure to obtain (1-a) (1 - 6) coverage at the cost of an additional calibration split, see Algorithm 2. We demonstrated the applicability of these approaches in the safety-critical and particularly ambiguous setting of skin condition classífication. In this context, the use of voted labels leads to overconfident prediction sets which leads to severe under-coverage of critical conditions. Our Monte Carlo CP overcomes this gap empirically and theoretically. We also demonstrated how our methodology allows conformal calibration with augmented examples and provides, for the first time, a coverage guarantee for multi-label CP.
We also want to highlight the assumptions that underlie our work and some potential extensions. First, we assume access to calibration data of the form (X,, B.)e(() for annotations B, from which we obtain calibration data Ae)(j)) for plausibilities A and then,by sampling, pscudo-labels (X,, (e) While assuming that the joint distribution of (X;, YT))s and test data (X, Y) is exchangeable for Algorithm standard, this is not true in presence of distribution shift
and that these data are iidd. for Algorithm at test time. However, we believe it should be possible adapt Monte Carlo CP to this setting using the techniques developed in (Tibshirani et al., 2019). We note finally that is also possible bypass having to sample pseudo-labels and perform conformal calibration directly the plausibilities using calibration data (X,, ):)ejm but this leads to prediction intervals which are difficult to interpret and exploit. Second, our method relies on an aggregation model P However, we emphasize that we are not making more assumptions than is currently made by applying CP to voted labels. On the contrary, we explicilly state the typically implied assumptions regarding label collection. Finally, it is important to keep in mind that, as any CP technique, the proposed Monte Carlo CP procedures only provide unconditional coverage guarantees of the form P Pggs( (Y E C(X)) 2 1 a and not guarantees of the form P. Pagg( (Y C(X){X x) l
Broader impact
Our work addresses the problem of conformal calibration in ambiguous settings where ground truth labels are not crisp as generally implicitly assumed in supervised machine learning. As discussed in our skin condition classification case study, ignoring this ambiguity can have severe consequences if used standard techniques relying on voted labels: key conditions (such as the cancerous " "Melanoma" in Figure 11) may not be covered in the outputted prediction sets despite experts including them in their annotations. This can have very immediate negative consequences for patients well increase cost and strain the healthcare system. Therefore, we generally view the impact of our work very positively, especially in the deployment of safety- critical applications such as in health. However, it is also important to look into how the methods proposed here affect different demographic groups.
Data availability
The de-identified dermatology data used in this paper is not publicly available due to restrictions in the data-sharing agreements.
References
Anastasios N. Angelopoulos and Stephen Bates, A gentle introduction to conformal prediction and distribution-free uncertainty quantification. orXiv.org, abs/2107.07511, 2021.
Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Uncertainty sets for image classifiess using conformal prediction. In Proc. of the International Conference on Learning Representations (ICLR), 2021.
16

---

Published in Transactions on Machine Learning Research (10/2023)
Vineeth Nallure Balasubramanian, Shayok Chakraborty, and Sethuraman Panchanathan. Conformal predic- tions for information fusion- - A comparative study of p-value combination methods. Annals of Mathemalics and Artificial Intelligence, 74(1-2):45 65, 2015.
Rina Foygel Barber, J. Candès, Aaditya Ramdas, and Ryan J. Tibshirani. Predictive inference with the j The Annals of Statistics, 49(1):486- 507, 2021.
Stephen Bates, Emmanuel Candès, Lihua Lei, Yaniv Romano, and Matteo Sesia. Testing for outliers with conformal p-values. The Annals of Statistics, 51(1), 2023.
Maxime Cauchois, Suyash Gupta, and John C. Duchi. Knowing what you know: valid and validated confidence sets in multiclass and multilabel prediction. Journal of Machine Learning Research (JMLR),
22:81:1-81:42, 2021.
Daniel M. Cer, Mona T. Diab, Eneko Agirre, lūigo Sopez-Gazpia and Lucia Specia. Semeval-2017 task 1: Semantic textual similarity multilingual and cross-lingual focused evaluation. arx.v.org, abs/ 1100.00005.5555 2017.
Ozan Cinar and Wolfgang Viechtbauer. The poolr package for combining independent and dependent, p values. Journal of Statisticol Software, 101(1), 2022.
Ekin Dogus Cubuk, Barret Zoph, Dandelion Mané, Vijay Vasudevan, and Quoc V. Le. Autoaugment:
Learning augmentation policies from data. arXic.org, abs/1805.09501, 2018.
Adamn Fisch, Tal Schuster, Tommi Jaakkola, and Regina Barzilay. Conformal prediction sets with limited false positives. In Proc. of the International Conference on Machine Learning (ICML), 2022.
Ronald Aylmer Fisher. Statistical Methods for Research Workers. Edinburgh Oliver & Boyd, 1925.
Asaf Gendler, Tsui-Wa Weng, Luca Daniel, and Yaniv Romano. Adversarially robust conformal prediction. Proc. of the International Conference on Learning Representations (ICLR), 2022.
Mitchell Gordon, Michelle S. Lam, Joon Sung Park, Kayur Patel, Jeffrey T. Hancock, Tatsunori Hashimoto, and Michael S. Bernstein. Jury learning: Integrating dissenting voices into machine learning models. In Proc. of the Conference Human Factors in Computing Systems, 2022.
Yash Goyal, Tejas Khot, Douglas Summers-Ster Dhruv Batra, and Devi Parikh. Making the V in VQA matter: Elevating the role of image understanding in visual question answering. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
Bruce Hajek, Sewoong Oh, and Jiaming Xu. Minimax-optimal inference from partial rankings. Advances in Neural Information Processing Systems, 27, 2014.
Nicholas A. Heard and Patrick Rubin-Delanchy. Choosing between methods of combining p-values. Biometríka, 105:239
246, 246, 2017.
Andrew G. Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv. org, abs/ abs/1704.04861, 2017.
Byol Kim, Chen Xu, and Rina Foygel Barber. Predictive inference is free with the jal In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Antonis Lambrou and Harris Papadopoulos. Binary relevance multi-label conformal predictor. In Proc. of the Symposium Conformal and Probubilistic Prediction and Applications (COPA), 2016.
17

---

Published in Transactions on Machine Learning Research (10/2023)
Tsung- Yi Lin, Michael Maire, Serge J. Belongie, James Hays, Pictro Perona, Deva Ramanan, Piotr Dol- lár, and C. Lawrence Zitnick. Microsoft COCO: common objects in context. In Proc. of the European Conference on Computer Vision (ECCV), 2014.
Henrik Linusson, Ulf Norinder, Henrik Boström, Ulf Johansson, and Tuve Löfström. On the calibration of aggregated conformal predictors. In Proc. of the Symposium on Conformal and Probabilistic Prediction and Applications (COPA), 2017.
Henrik Linusson, Ulf Johansson, and Henrik Boström. Efficient conformal predictor ensembles. Neurocom- puling, 397:266 278, 2020.
Yuan Liu, Ayush Jain, Clara Eng, David H. Way, Kang Lee, Peggy Bui, Kimberly Kanada, Guilherme de Oliveira Marinho, Jessica Gallegos, Sara Gabriele, Vishakha Gupta, Nalini Singh, Vivek Natarajan, Rainer Hofmann- Hofmann-Wellenhof, Gregory S. Corrado, Lily H. Peng, Dale R. Webster, Dennis Ai, Susan Huang, Yun Liu, R. Carter Dunn, and David Coz. A deep learning system for differential diagnosis of skin diseases. Nature Medicine, 26:900-908, 2020.
Xiao-Li Meng. Posterior Predictive V-luuss. The Annals of Statistics, 22(3):1142 - 1160, 1994.
Harris Papadopoulos. A cross-conformal predictor for multi-label classification. In Proc. of the Symposium on Conformal and Probabilistic Prediction and Applications (COPA), IFIP Advances in Information and Communication Technology, 2014.
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alexander Gammerman. Inductive confidence machines for regression. In Proc. of the European Conference Machine Learning and Knowledge Dis- covery in Databases (ECML PKDD), 2002.
Joshua C. Peterson, Ruairidh M. Battleday, Thomas L. Griffiths, and Olga Russakovsky. Human uncertainty makes classification more robust. In Proc. of the IEEE International Conference Computer Vision (ICCV), 2019.
Yaniv Romano, Evan Patterson, and Emmanuel J. Candès. Conformalized quantile regression. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Yaniv Romano, Matteo Sesia, and Emmanuel J. Candès. Classification with valid and adaptive coverage. In Advances in Newral Information Processing Systems (NeurIPS), 2020.
Abhijit Guha Roy, Jie Ren, Shekoofeh Azizi, Aaron Loh, Vivek Natarajan, Basil Mustafa, Nick Pawlowski, Jan Freyberg, Yuan Liu, Zachary Beaver, Nam Vo, Peggy Bui, Samantha Winter, Patricia MacWilliams, Gregory S. Corrado, Umesh Telang, Yun Liu, A. Taylan Cemgil, Alan Karthikesalingam, Balaji Laksh- minarayanan, and Jim Winkens. Does your dermatology classifier know what it doesn't know? detecting the long-tail tail of unseen conditions. Medical Image Analysis, 75:102274, 2022.
Ludger Rticchendoff. Random variables with maximum sums. Advances in Applied Probability, 14(3):623- 632, 1982.
Olga Russakovsky, Jia Dong, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael S. Bernstein, Alexander C. Berg, and Fei-Fei Li. Imagenet large scale visual recognition challenge. International Journal of Computer Vision (IJCV), 115(3):211 252, 2015.
Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 11 (22)):223)22222 2019.
Mike Schaekermann, Edith Law, Alex C Williams, and William Callaghan. Resolvable vs. irresolvable ambiguity: A new hybrid framework for dealing with uncertain ground truth. In SIGCHI Workshop on Human-Centered Machine Learning, volume 2016, 2016.
Richard Socher, Alex Perclygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Y. Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proc. of the Conference on Empirioal Methods in Natural Language Processing, 2013.
18

---

Published in Transactions on Machine Learning Research (10/2023)
Lukas Steinberger and Hannes Leeb. Leave-one-out prediction intervals in linear regression models with many variables. ar Xin. org, abs/ abs/1602.05801,, 2016.
David Stutz, Krishnamurthy Dvijotham, Ali Taylan Cemgil, and Arnaud Doucet. Learning optimal conformal classifiers. In Proc. of the International Conference on Learning Representations (TCI.), 2021.
David Stutz, Ali Taylan Cemgil, Abhijit Guha Roy, Tatiana Matejovicova, Melih Barsbey, Patricia MacWilliams, Mike Schaekermann, Jan Freyberg, Rajeev Rikhye, Beverly Freeman, Javier Perez Matos, Umesh Telang, Dale Webster, Yuan Liu, Greg Corrado, Yossi Matias, Pushmect Kohli, Yun Liu, Arnand Doucet, and Alan Karthikesalingam. Evaluating ai systems under uncertain ground truth: a case study in dermatology. or Xiv.orr, abs/2307 2307.02191, 2023.
Ryan J. Tibshirani, Rina Foygel Barber, Emmanuel J. Candès, and Aaditya Ramdas. Conformal prediction under covariate shift. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Bue, Emily B. Fox, and Roman Garnett (cds.), Advances in Newral Information Processing Systems (NewrIPS), pp. 2526 2536, 2019.
Paolo Toccaceli. Conformal predictor combination using Neyman-Peant lemma. In Proc. of the Symposium on Conformal and Probabilistic Prediction and Applications (COPA), 2019.
Paolo Toccaceli and Alexander Gammerman. Combination of inductive Mondrian conformal predictors. Machine Learning, 108(3))489-55) 510, 2019.
Grigorios Tsoumakas and Ioannis Katakis. Multi-label classification: An overview. International Journal on Dola Warehousing and Mining, 3(3):1 13, 2007.
Alexandra Uma, Dina Almanca, and Massimo Pocsio. Scaling and disagreements: Bias, noise, and ambignity. Frontiers in Artifical Intelligence, 5, 2022.
Vladimir Vovk. Cross-conformal predictors. Annals of Mathematics and Artificial Intelligence, 74(1-2):9 28, 2015.
Vladimir Vovk and Ruodu Wang. Combining p-values via averaging. Biometrika, 107(4))791-808, 2020.
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic Learning in a Random World. Springer- Verlag, Berlin, Heidelberg, 2005.
Vladimir Vovk, Ila Nouretdinov, Valery Manokhin, and Alexander Gammerman. Cross-conformal predictive distributions. In Proc. of the Symposium on Conformal and Probabilistic Prediction and Applications (COPA), 2018
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. GLUE: A multi-task benchmark and analysis platform for natural language understanding. In Proc. of the Interna- tional Conference on Learning Representations (ICLR), 2019.
Hua-zhen Wang, Xin Liu, Ila Nouretdinov, and Zhiyuan Luo. A comparison of three implementations of multi-label conformal prediction. In Proc. of the International Symposium on Statistical Learning and Data Sciences, 2015.
Huazhen Wang, Xin Liu, Bing Lv, Fan Yang, and Yanzhu Hong. Reliable multi-label learning via conformal predictor and random forest for syndrome differentiation of chronic fatigue in traditional chinese medicine. PLOS ONE, 966):1-14, 2014.
Larry Wasserman. All of Nonparametric Statistics. Springer Science & Business Media, 2006.
Adina Williams, Nikita Nangia, and Samuel R. Bowman. A broad-coverage challenge corpus for sentence understanding through inference. In Proc. of the Conference of the North American Chapler of the Asso- ciation for Computational Linguistics: Human Language Technologies (NAACL-HLT)) 2018.
Wanchuang Zhu, Yingkai Jiang, Jun Liu, and Ke Deng. Partition Partition-Mallows model and its inference for rank aggregation. Journal of the American Statistical Association, 118(541):343 359, 2023.
19

---

Published in Transactions on Machine Learning Research (10/2023)
A Annotations in popular datasets
Many popular machine learning datasets have been created using annotators to determine labels. Often, they also use very basic aggregation and voting mechanisms (corresponding to PaRz and Fvote) such as majority voting or averaging, For example, the list of most cited datasets on Papers with Code? includes the following:
The CIFAR1O dataset (Krizhevsky, 2009) a popular multiclass classification benchmark of 32 x 32 pixel color images. Tt. was labeled using a strategy similar majority voting: first, a crowd-sourced label was collected which was then verified and potentially corrected by an author.
CIFAR10H (Peterson et al., 2019) revisited the CIFAR10 dataset by gathering additional human annotations where each annotator provides a single label.
ImageNet (Russakovsky et al., 2015) uses multiple annotators with majority voted labels.
COCO (Lin et al., 2014) labels category present if any out of 8 annotators labeled it present (even if all other annotators disagree).
The Stanford sentiment treebank (Socher al., 2013) includes annotations per example which are used in various ways during evaluation.
MultiNLI (Williams et al., 2018) includes annotations which are majority voted.
The semantic textual similarity benchmark (Cer et al., 2017) averages scores across multiple anno- tators.
The Recognizing Textual Entailment datasets also consider multiple annotators and several editions of the corresponding challenge simply neglected examples with disagreeing annotators (equivalent to majority voting while ignoring ambiguous examples).
The above natural language processing datasets are all part of the GLUE benchmark (Wang et al., 2019) the go-to benchmark for natural language understanding. Datasets beyond (multi-label) classification also often include multiple annotations. VQA (Goyal et al., 2017), for example, includes 10 free-form answers per question; aggregating them is clearly non-trivial. For many datasets, it might also be unclear how annotations have been collected or aggregated. The Quora Question Pairs webpage? explicitly mentions label errors but does not give details on annotation and aggregation. All of these examples emphasize that aggregating annotations and using majority voted or averaged labels extremely common across supervised machine learning. This means that plausibilities are typically readily obtainable and the core problem we address using majority voted labels on ambiguous tasks for calibration leads to under-coverage is highly relevant.
B
Calibration threshold and p-values
B.1
Single p-value
We include for completeness proof of the results presented in Section 2.1. These standard results. The p-value formulation detailed here will be then exlended to establish the validity of some of the procedures proposed in this work.
We first establish that the prodiction set defined by Equations (2) and (3) satisfics
1 S P(Y E C(X)) < 1 a n+11
(20)
the upper bound requiring the additional assumption that the conformity scores are almost surely distinct.
hhttes//aacaisstooo////////eeeep _daaa//ndex.htmm
httpe//ggurnaatt.qqurrr.ooo//tt Quorr Dataset-
Dataset-Release- Release- Question- Pairs
20

---

Published in Transactions on Machine Learning Research (10/2023)
Let write (Xa+1, kx+1) = (X,Y) and S, E(X,, Y.). As (St)ig(n+1] are exchangeable, then direct application of (Romano et al., 2019, Appendix A, Lemma 2) shows that for any E (0, and r' =
Q (1-Stheea) - () + +) 1)]/n)
P(-S 2
(21)
and, if the random variables (Si)e((+1) are almost surcly distinct, then
P(-Sa+1 51- 11-10 a+ n-1
(22)
So c(xx+1) includes all the values y such that -(( is smaller or equal than the [(1- smallest values of (-S:) This equivalent to considering all the values y such that 5(X,+1, y) is larger
- a) + 1)]
or equal than the [a(n+ [1] smallest values of (S)) Hence this corresponds to the prediction set defined by Equations (2) and (3).
We now show that this prodiction set can also be obtained by thresholding p-values. Indeed Equation (4) can be rewritten as
En+ I(S; I Sn+1)
PY
(23)
n + 1
As (S)) are exchangeable, then PY,, is uniformly distributed { 1 -fT.:.. the scores is continuous and thus Pr is a p-value, i.e. P(Pr... I a) S a > P(pr.-, > a) 2 It can be checked that this property still holds if the distribution of the scores is not continuous (see e.g. (Bates et al., 2023)). So if we define the prediction set as
.. 1) if the distribution of
C(Xa+1) by: Pv aa
(24)
then by construction it follows that
P(Y++1 E C(Xn+1))
2 1-a a.
(25)
We show here that Equation (24) does indeed coincide with the set defined by Equations (2) and (3). We have
Py > + Σ I(S, < E(Xn+1,8)) > a(n + 1) - 1.
(26)
If ann + 1) is integer then I[S; E(Xn+1,,)) v)) 2 a(n + 1), i.e E(X,+1, y) is larger equal than the a(n + 1) smallest values of (S))) If aln 1) is not an integer then it means that Σ T(S s E(Xa+1,3) B)) 2 Ja(n+ (o]]+1)]]- 1, 1)
Le. E(Xn+1,b) v) is larger than the [a(n+ + 1)] - smallest values of (S:) However, we have Ja(n + 1) -1 = la(n + 1)] as a(n + 1) is not an integer. So overall, we have that Py > a corresponds to E(Xa+1, y) being larger or equal than the [a(n + +1] smallest values (St) So the prediction set in Equation (24) does coincide with the set defined by Equations (2) and (3).
Finally note that when the distributions of the scores is continuous, i.e. the scores are almost surely distinct, then we also have P( aa l/n+1 so PPY... a) < 1 a + 1/nt1.
B.2 Average of p-values
We establish here the expression of the prodiction set obtained by thresholding the following average p-value
E. m n+ I(S} < 1)
PY
(27)
m(n + 1)
where S Sx+1 for all j E [m]. We know that by construction the set C(Xn+1) {y Py a} such that
P(Y+1 C(Xn+1)) 2 2a.
(28)
21

---

Published in Transactions on Machine Learning Research (10/2023)
Standard CP w/ m 1 sampled label
Standard CP w/ m 10 sampled label
Target
Tardet
Voted coveree
Voted coverage
0.08
Aggregar gate overage
Frequency
0.30
Aporopated coverage
0.05
0.02
0.00
0.00
0.700
0.750
0.800
0.925 0.850
0.80 0.82 0.84 Empirical coverage
0.76
0.78
Empirical coverage
0.15
Frequency
Average: 4.57
Average 4.55
0.30
0.05
0.05
0.00
0.00
Inafficiancy
Inafficiency
Figure 14: Complementary to Figure 10, we show results for standard CP with m = 1 and m = 10 sampled labels per example in terms of voted coverage (blue) and aggregated coverage (green) across 100 random calibration test splits (top) as well as inefficiency (bottom). As for Monte Carlo CP in Algorithm 2, we sample m labels from the plausibilities, but use the quantile from Equation (3) for calibration. For 1, this coincides with Monte Carlo CP: for m however, the quantile computation differs from Equation (13).
We have
m
72
Pg >a a
I(S S E((x+1.))) am(n + 1) m.
(29)
i=1
smallest values of (5) [e[]).mmm)) If amm(++1] 1) is not an integer then Σ Σ I(S S E(X,+1, v)) 2 [am(n++1]] m, i.c. E(X, y) larger or equal than the [am(n +1]] -m] smallest values of S.. However, we have [am(n+1)] [am(n + +1] am(n++ 1) is not integer. So [am(n + 1)1 m [am(n 1)J ] + So overall we need E(X.+1,2) larger or equal than the [am[n+1)] m + smallest values of (5 je(m) equivalently larger that the quantile of (5 Je( at level [am[n+1] -m+1 i.e. C(Xn+1) = {K E [K] ((x,+1 2 r for T defined in Equation (10).
If am++1) is an integer then (( v) needs to be larger or equal than the am
+)]]-m
C Additional results for skin condition classification
Figure 14 shows a baseline experiment using standard CP with sampled labels instead of our Monte Carlo CP from Algorithm 2. Specifically, we sample m and m = 10 labels as we would for Monte Carlo CP but apply the standard quantile from Equation (3) for calibration. Specifically, we use [a(x+1)//n (Equation (3)) instead of com(n+1))-m+1]
(Equation (13)) which is used for Monte Carlo CP. For = 1, these coincide; for m > 2, the quantiles may differ but are still close for large n. Thus, it is not surprising that this approach also obtains (on average) target coverage 1 - a. However, in contrast to Monte Carlo CP, this approach does not provide any coverage guarantee for m > 1.
Figure 15 shows the paluuues of standard CP (with voted labels, left) and Monte Carlo CP (with sampled labels, right) w.r.t. to the voted labels (top) and 10 labels randomly sampled from the plausibilities (per example, bottom). CP against voted labels results in the correspouding p-values being uniformly distributed. However, the distribution of vavuuu corresponding to the black line). With Monte Carlo CP, we observe the opposite: the p-values corresponding to voted labels are not entirely uniformly distributed while those corresponding to sampled labels are. This highlights the impact of ambiguity on the corresponding p-values.
sampled labels is slightly skewed towards 0 (compare
Figure 16 presents complementary results to Figure 9 the main paper. Specifically, on top, we addi- tionally consider ties among the voted labels (i.e., there is no unique arg max in the plausibilities A). In the calibration examples, we break these ties randomly. At test time, however, decide to evaluate
22

---

Published in Transactions on Machine Learning Research (10/2023)
CP with voted labels: p-valles for voted labels
Monte Carlo CP: p-values for voted labels
Uniform
EP with vated labek
0.06
Uniform
Simple NCCP
ECOP MECP
0.04
0.02
0.02
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
p-valuee
p-value
CP with voted labels: p-values for sampled labels
Monte Carlo CP: p-values sampled labels
0.06
Requans
Uriform
voted
Unifomm
Smple
ECDP
0.04
0.04
0.02
6.00
0.00
0.0
0.0
p-value
p-value
Figure 15: p-value histograms for CP with voted labels (left) and Monte Carlo CP (right). In both cases, we show the p-values for the voted labels (arg max plausibilities, top) and labels samples from the plausibilities (bottom). Calibrating against voted labels guarantees a uniform distribution of the p-values shown top, Monte Carlo calibration guarantees the same for the bottom histograms. As result, compared to the expected uniform distribution (black), the distribution of p-values w.r.t. sampled labels is skewed for CP with voted labels (bottom left.) while p-values w.r.t. to voted labels are skewed for Monte Carlo CP (top right).
Realtzed coverage
Realized voled and aggregated ted coverage for CP with vated labels
1.0
Abbregated coverage
0.5
Voted coverage (0.73)
Voted coverage w/
Argmax plausibiiity
0.0
200
400
600
800
Sorted examples
Realized coverage
Realized aggregated coverage c comparison
1.0
"U with voted labels (0 61)
Simple (0.72)
ECDF MCCP (0. 72)
Argmax plausibility
800
Sorted examples
Figure 16: Top: Complementary to Figure 9, we include evaluation against voted labels while considering ties (red, 1/1. E E C(X.) with Y being one of Li tied labels for case i) which hints towards several ambiguous cases. Looking at aggregated coverage (i.e., Σye[k] A&Ily E C(X,))) in blue, however, shows that a significant portion of examples are ambiguous and standard evaluation against the voted labels (i.c., I[arg max; Ask E C(X,)l) is unreasonable. Bottom: Aggregated coverage plot for Monte Carlo CP procedures compared to CP with voted labels, highlighting that CP with voted labels does not obtain the target aggregated coverage.
coverage proportional the tied labels. Formally, we assume that Y,,..., Y.....,,!.. are the tied labels and compute 1/2, Σ/= I[Y E C(X,)] instead of the binary indicator 1[Y, E C(X)) to evaluate coverage. red, we see that quite few examples exhibit ties and the predicted prediction sets often cover only a part of the tied labels. This is an carly indicator for high ambiguity the ground truth of this dataset. On the bottom, we additionally plot aggregated coverage for (ECDF) Monte Carlo CP in comparison to CP on voted labels. Again, CP with voted labels significantly under-estimates aggregated coverage. While both Monte Carlo approaches (with and without ECDF correction) look identical in this example, they do not have to be due to randomness in how the calibration set is further split (cf. Algorithm 2). In expectation across splits, however, we found that they coincide. This also highlights that the simple variant empirically achieves aggregated coverage - a despite only guaranteeing 1 2a.
Figure 17 reproduces Figure 5 on our skin condition classification case study showing the advantage of using m in Monte Carlo CP to reduce variation in aggregated coverage across calibration /test splits.
23

---

Published in Transactions on Machine Learning Research (10/2023)
Variation aggregated coverage Monte Carlo CP
0.15
Target
m
Figure 17: Empirical aggregated coverage for Monte Carlo CP with various m. As on our toy datasct in Figure higher m clearly reduces the variation in coverage across the evaluated 100 calibra- tion/test splits despite using 50% of the 1949 examples for calibra- tion.
Requency
m-
0.10
0.00
0.85
0.87
0.88
0.89
0.90
0.91
0.92
0.93
Empirical coverage
CP with voted labels
Monte Carlo
1.00
Haustalfles
1.00
Raus Bi5
Confideris sst
Contiriio denee asc
0.50
0.50
0.00
0.80
Anne
Fall
Sebo
Abst
Sabo
Acan
Classes
Classes
CP with voted labels
Monte Carlo CP
Haubiikee
Plussh files
0.75
Confitence
10.23 ag). ovveagel
Confidecc
$5.36 app. coverge)
0.50
0.25
0.00
Homa Dnyc Ony:
Only 0ryc
Figure 18: Additional qualitative results corresponding to Figure 11.
Figure 18 shows two additional qualitative examples where Monte Carlo CP improves results, i.e., more conditions with significant plausibility (bluc) are covered (green) but important conditions are still not covered. This can be addressed using a lower confidence level such as = 0.1 Figure 20.
Results of our main experiments in dermatology for a 0.1 can be found in Figures 19 20.
24

---

Published in Transactions on Machine Learning Research (10/2023)
veted
ECDF Monte Carlo CP
0.15
Target Voted
Target
Targat
Voted
0.125
Voted Geveraee
0.10
Aggregai caverage
Frequency
Aggregat coverage
Agginga
0.075
0.10
0.05
0.025
0.00
0.50
0.82
0.84
0.86
0.88
0.90
0.92
0.88
0.90
0.92
0.94
0.96
0.86
0.88
0.90
0.92
0.94
0696
Empirical
Empirica
Empirical
0.15
Iverage:
Frequency
Average: 15.02
Average: 14.87
0.10
0.30
0.3
0.05
0.08
0.00
0.0
0.00
7.0
Inelficency
Inefficiency
Inefficiency
Figure 19: Results corresponding to Figure 10 with 0.1.
labels
Carlo
0.75
1587 top celenge)
0.75
10AT sop coverge!
0.25
0.25
1ema Mela
Angl
Pyog
Scn
Mela
Any OZ
Iema Mata
Angi
Pyce 5kh
Va
Abp
Q/E
Classes
Classss
CP with voted labels
Monte Carlo CP
1.00
Bus
1.00
Hass Bus
Canfibonce 54
Contie ice
0.550
0.50
0.25
0.00
0.50
Cell
Classes
Classes
CP with voted labels
Monta Carla CP
1.00
1.50
Pauch lime
Confiderce
5.55 vph covergg))
0.75
Contieico
epp covers sage
0.50
0.50
0.25
0.25
0.03
0.80
Pall
Absc
Sa5o
Acan
Mousica
0.75
10.9 colngge)
0.75
89 corcopt ogd
0.50
0.29
0.25
Hema Orye Dryt
5G1
The
Xem
free
Abe
Hema Dny: Ony:
5K1 Tno
Xem Erze
Abc
Clacses
Classes
Figure 20: Additional qualitative results for = 0.1 corresponding to Figures 11 and 18.
25


Reviews:
[{"review_id": "t4m25mQ9DQ", "reviewer": "Reviewer_czeu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper brings the fact that the label distribution itself is ambiguous and we need to consider the uncertainty of it in conformal prediction. This would be an interesting aspect, but I have the following major concerns on this paper’s representation and claims. \n\n- The paper’s basic premise is that the label that we can access is actually the top-1 label (i.e., “the top-1 labels ignore the underlying ambiguity” in page 2. Based on this premise this paper claims that we have to consider a label distribution directly as a label. However, this is not true; the labels that we access for a calibration set are drawn from the label distribution, instead of the top-1 label. This means, the standard conformal prediction is already considering the ambiguity from the label uncertainty and I’m not sure if we need a novel approach. \n\n- I agree that having “plausibility” is good, but we never get this label in practice (as it is too expensive). The “plausibility” labels obtained in skin condition classification is estimated one (from multiple experts). In this case, the estimation error will introduce another uncertainty, which is not handled by the method. So, I’m not convinced of introducing a “plausibility” label and making a new method for it. \n\n- The paper representation along with the main claim is difficult to understand. In conformal prediction literatures, they only have a single coverage guarantee definition. However, this paper has multiple coverage guarantees, i.e., (1), (8), (13), (15) and I’m not sure which one is used in evaluation. Please discuss the relation among them and clarify the “coverage” definitions used in figures. \n\n- “Monte Carlo conformal prediction” is introduced saying that “To avoid working with plausibility regions“ in page 8. This is inconsistent with the original claim that we need “plausibility” labels/regions. Moreover, introducing “Monte Carlo conformal prediction” breaks the exchangeability assumption, which is not desirable and undermines the usability of this approach.\n\n\nMinor editorial comments:\n- The caption of the first figure in Figure 1 should be “true label”?\n- Prediction sets are more usual than confidence sets in conformal prediction.\n- In (10), a parenthesis is not closed. \n- The subscription of $\\lambda$ is confusingly used. In $\\lambda_i$, $i$ is the index of samples while in $\\lambda_k$, $k$ is the $k$-th element of the vector $\\lambda$.\n\n\nI’m happy to correct my understanding if I misunderstood anything.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The standard conformal prediction builds a conformal set based on one-hot label vectors, though these one-hot vectors do not precisely provide the uncertainty on label. This paper proposes a novel approach for conformal prediction with ambiguous labels (called “plausibilities” in the paper). Assuming that the labels of a calibration set is represented in a label distribution vector, the paper introduces new terms, e.g., expected coverage in (8), expected conformity scores in (11). Based on this Algorithm 1 builds a “plausibility region” in (12) that satisfies the coverage guarantee in (13) and a reduced confidence set in (14) satisfies the coverage guarantee in (15). To improve usability and weak coverage rates, this paper further proposes Algorithm 2 and Algorithm 3. The proposed approach is evaluated on a synthetic dataset and a real dataset for skin condition classification. Along with these, the method is evaluated on two case studies.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please provide a convincing argument that labels used in a calibration set are top-1 labels instead of sampling from a label distribution,\n- Having “plausibility” labels is very expensive. Please discuss why should we use “plausibility” labels even with this high cost.\n- Please discuss the relation among them and clarify the “coverage” definitions used in figures. \n- Please discuss why we need “Monte Carlo conformal prediction”, which is inconsistent to the previous part of the paper and which breaks the exchangeable assumption (thus the method anyway does not provide any rigorous guarantee)", "broader_impact_concerns": "The Broader Impact Statement section is not presented. I think the users of this algorithm need to know the assumptions under which they can trust the output of the algorithm.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "72irXUrK6w", "reviewer": "Reviewer_ZZHz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nS1) The paper studies an interesting and relevant problem\nS2) it provides insightful visualizations using a running example on simple synthetic data\n\nWeaknesses:\n(I have to say that conformal prediction is not my field of expertise, still I tried to read the paper carefully)\nW1) the guarantees that the algorithms provide are not w.r.t. the true distribution P, but w.r.t. the aggregation model P_{agg}. This is a major limitation in my opinion, whose consequences are not sufficiently discussed (e.g., how should one interpret the confidence sets? how does their meaningfulness depend on the quality of the plausibility model?). This limitation is also not mentioned in the abstract or introduction of the paper. There is also no discussion whether / why such limitation is necessary. \nW2) The relevance of the first approach is unclear to me as it gives plausibility regions rather than confidence sets in the first place and the derived confidence sets are very inefficient in the experiments. Furthermore, the proposed approach to derive confidence sets is computationally inefficient so that it only works with three classes in the experiments.\nW3) Section 3 is very hard to read in my opinion. It would benefit from\n- rethinking whether the first approach shouldn’t be removed at all, or at least restructure its presentation (Sec. 3.1, 3.2, 3.3 – without any sub-subsections - are about Approach 1, Sec. 3.4, 3.4.1, 3.4.2 are about Approach 2)\n- avoiding ambiguous names: the word “expected” is already overloaded, still the authors ‘refer abusively to Equation (8) as “expected” coverage’; even worse, in the following they write “expected” coverage (with quotation marks), expected coverage (without quotation marks), *expected* coverage (italic), or (expected) coverage (with parentheses) -- do these all mean the same thing?\n- generally improving the presentation, e.g., formally introducing the plausibilities, discussing the conditional independence assumption of the aggregation model, etc.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the problem of conformal prediction in the setting where labels in the calibration set are not necessarily ground-truth labels, but one rather has a set of potentially disagreeing expert annotations for each datapoint. The paper provides two approaches to the problem and three algorithms (Approach 1 comes with one algorithm, and Approach 2 comes with two algorithms) that provide different guarantees. The paper compares these algorithms to standard conformal prediction in a case study of skin tone classification.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Address weaknesses W1 and W3 (critical to securing my recommendation for acceptance)\n\nMinor fixes:\n*) Figure 3 is not mentioned / discussed in the text\n*) page 5, first sentence: \"admits a distribution\" -> admits a density\n*) page 21: (Romano et al., 2019, Lemma 1) should be (Romano et al., 2019, Theorem 1)\n*) page 15, first paragraph: \\lambda_{ik} -> \\lambda_{iy}\n*) page 15, second paragraph: different -> difference ", "broader_impact_concerns": "The paper does not provide any discussion of its broader impact. While I don’t think such discussion is strictly necessary, the case study of skin condition classification somewhat cries out for at least a remark that a follow-up study should look into how the proposed method affects different demographic groups.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "jNlSwEl6Rf", "reviewer": "Reviewer_k2YP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is relatively well-written. I can easily follow the structure to understand the proposed methods. Uncertainty quantification and conformal prediction are timely research topics, particularly important for certain medical applications. This paper considers these timely topics and proposes a setting where ground-truth labels are inherently uncertain, which is new. Considering a real-world dataset of skin condition classification is also a plus.\n\nAlthough the proposed setting is of practical importance, I have to say that when reading the paper, I got pretty confused about the evaluation criteria for comparisons between different conformal prediction algorithms under the new setting. It seems that the main contribution of the paper is the design of various conformal prediction algorithms which potentially work for the new setting, but it is vague what the exact improvements are when compared with baseline methods. This is a major weakness from my perspective, so I further provide my comments and questions below.\n\nFor standard conformation prediction (where the ground-truth label is deterministic), the conformal/confidence set's size and the coverage guarantee are typically considered as the evaluation criteria for comparing different methods. However, you are considering a different setting where the ground-truth labels are uncertain, so it is essential to clarify the metrics you use for the new setting. For example, if an input has uncertain labels of class 3 and class 5 with equal probabilities, could you explain what an ideal predicted conformal set for that input looks like? In addition, how to evaluate the performance of a conformal prediction algorithm with respect to an inherently uncertain data distribution? Moreover, it is unclear why we want to reduce the estimates of plausibility regions to a set of labels if the ground-truth label of the corresponding input is inherently uncertain. Please justify why this additional step is necessary for the considered setting.\n\nFinally, I strongly recommend clarifying the contributions of your work in the introduction. The last paragraph of the introduction section just lists what you do in the paper. It is unclear what performance gain your method achieves for different datasets and what the implications are for practitioners deploying conformal prediction methods in real-world applications.\n\nOther questions:\n\n1. It is likely that a data distribution consists of both uncertain and deterministic components. How will your methods affect the performance of the deterministic components? Will there be a trade-off between the two components?\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers conformal prediction tasks under scenarios where the ground-truth labels are inherently uncertain. By leveraging a set of label annotations from multiple experts (as an approximation of the posterior class probabilities), it first introduces a notion of plausibilities, then provides a method to estimate confidence intervals of plausibilities with associated coverage guarantee (termed as plausibility regions) by extending a standard conformal regression procedure. In addition, two strategies are proposed to reduce the estimates of plausibility regions to conformal sets of labels. Experimental results of the proposed strategies are provided with respect to both synthetic datasets of Gaussian mixtures and a real dataset for skin condition classification.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Clarify the evaluation criteria for the considered problem setting.\n\n2. Add a paragraph in the introduction to explain the contributions of your work.\n\n3. Discuss the limitations and potential implications of deploying your methods in real-world scenarios.\n\n4. Can you explain how the proposed methods affect the performance with respect to inputs with more deterministic labels?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Following the reviewers' recommendations, the paper is worth publication in TMLR. However, one of the reviewers asked for additional comparisons between available baselines and the proposed methods: 
1. Please apply the proposed method to the toy example in Figure 3 to compare with applying standard CP to voted labels
2. Please compare the proposed method to a baseline that applies standard CP to labels drawn from the given plausibilities $\lambda$ in the main experiments of the paper
Decision: Accept (poster)