Approximate Conditional Coverage via Neural Model Approximations
Authors: Allen Schmaltz
Danielle Rasooly
Venue: Submitted to ICLR 2023 (2023)
Keywords: distribution-free uncertainty quantification
split-conformal prediction sets
Venn Predictors

Abstract: We propose a new approach for constructing prediction sets for Transformer networks via the strong signals for prediction reliability from KNN-based approximations. This enables a data-driven partitioning of the high-dimensional feature space and a new Inductive Venn Predictor for calibration, the Venn-ADMIT Predictor. Our approach more closely obtains approximate conditional coverage than recent work proposing adaptive and localized conformal score functions for deep networks. We analyze coverage on several representative natural language processing classification tasks, including class-imbalanced and distribution-shifted settings.

Under review as a conference paper at ICLR 2023
APPROXIMATE CONDITIONAL COVERAGE & CALI- BRATION VIA NEURAL MODEL APPROXIMATIONS
Anonymous authors Paper under double-blind review
ABSTRACT
A minimal required desideratum for quantifying the uncertainty from classi- fication model as a prediction set is class-conditional singleton set calibration. That is, such sets should map to the output of well-calibrated selective classifiers, matching the observed frequencies of similar instances. Recent works proposing adaptive and localized conformal p- p-values for deep networks do not guarantee this behavior, nor do they achieve it empirically. Instead, we use the strong sig- nals for prediction reliability from KNN-based approximations of Transformer networks to construct data-driven partitions for Mondrian Conformal Predictors, which are treated as weak selective classifiers that are then calibrated via a new Inductive Venn Predictor, the classifiers are well-calibrated, in a conservative but practically useful sense for a given threshold, unlike conformal sets. They are inherently robust to changes in the proportions the data partitions, and straightforward conservative heuris- ties provide additional robustness to covariate shifts. We compare and contrast to the quantities produced by recent Conformal Predictors on several represen- tative and challenging natural language processing classification tasks, including class-imbalanced and distribution-shifed settings.
Predictor. The resulting selective
INTRODUCTION
Uncertainty quantification is hard. The problem of the reference class (see, e.g., Vovk et al. 2005 p- 159) necessitates task-specific care interpreting even well-calibrated probabilities that agree with the observed frequencies. It is made harder in practice with deep neural networks, for which the otherwise strong blackbox point predictions are typically not well-calibrated and can unexpectedly under-perform over distribution shifts. And it is harder still for classification, given that the promis- ing distribution-fii approach of split-conformal inference (Vovk et al., 2005 [Papadopoulos et al.) 2002), assumption-light frequentist approach suitable when sample sizes sufficiently large, produces a counterintuitive p-value quantity in the case of classification (cf., regression).
Setting. In typical natural language processing (NLP) binary multi-class classification task, we have access to a computationally expensive blackbox neural model, F; training dataset, Drr = (Z.H=1 {X,, Y of [Derl instances paired with their corresponding ground-truth dis- crete labels, Y; E y {1, (1,.... C); and a held-out labeled calibration dataset, Dea = ,= of (Deal J instances. We are then given a new test instance. XN+1, from an unlabeled test set, Dic. One approach to convey uncertainty in the predictions is to construct a prediction set, produced by some set-valued function C(XN+1) E 20, containing the true unseen label with specified level 1-a E 10, 1) on average. We consider two distinct interpretations: As coverage and as a conser- vatively coarsened calibrated probability (after conversion to selective classification), both from frequentist perspective.
Desiderata. For such prediction sets to be of general interest for classification, we seek class- conditional singleton set calibration (CCS). We are willing to accept noise in other size stratifica- tions, but the singleton sets, |C| 1, must contain the true value with a proportion of 2 1 - a, at least average per class. We further seek singleton set sharpness; that is, maximize the number of singleton sets. We seek reasonable robustness to distribution shifts. Finally, we seek informative sets that avoid the trivial solution of full cardinality.

---

Under review as a conference paper at ICLR 2023
If are willing to fully dispense with specificity in the non-singleton-se stratifications for tasks with |>| > 2, our desiderata can be achieved, in principle, with selective classifiers.
Definition 1 (Classification with reject option). A selective classifier. g g: X 2 y U {1}, maps from the input to either a single class or the reject option (represented here with the falsum symbol). Remark 1 (Prediction sets are selective classifications). The output of any set-valued function C(XN+1) E 2 corresponds that of selective classifier: Map non-singleton sets, (e(XN+1)) + 1, to 1. Map all singleton sets to the corresponding class in y.
To date, the typical approach for constructing prediction sets is not via methods for calibrating probabilities, but rather in the hypothesis testing framework of Conformal Predictors, which carry PAC-style (a, ()val-v coverage guarantee. In the inductive (or "split") conformal formulation [ork 2012] Papadopoulos et al. [20)2] inter alia), the p-value corresponds to confidence that a new point is as more conforming than held-out set with known labels. More specifically,
require a measurable function A : Z x Z + R, which measures the conformity between 2 and other instances. For example, given the softmax output of neural network for æ, म E RC, with # as the output of the true class, A A(( 21), (z, y) = H is typical choice. We construct p-value, v², as follows: v |[j=[+1..... STN 11+11 where Tj A( 21),2)) V 2j E Pea and N+1
TN+1 A((z)..... (z 0N+1) )), where we suppose the true label is ÿ. We then construct the prediction set: C(IN+1) = {0: v > a.. This is accompanied by a kinie-sample, distribution- free coverage guarantee, which we state informally here
Theorem (Marginal Coverage of Conformal Predictors (Vovk et al. 2005)). Provided the points Dea and Dre are drawn exchangeably from the same distribution Pxy (which need not be further
specified), the following marginal guarantee holds a given a: TP { (Y441 E e((Xx+1)] 2 1 a.
The distribution of split-conformal coverage is Beta distributed (Vovk] 2012). from which PAC- style (ax, ---vaiiiity guarantee can be obtained, and from which we can determine a suitable sample size to achieve this coverage in expectation. Unfortunately, this does not guarantee singleton set coverage (the hypothesis testing analogue of our CCS desideratum), a known, but under- aadre-appre, negative result that motivates the present work:
Corollary 1. Conformal Predictors do not guarantee singleton set coverage. If they did, would imply stronger than marginal coverage guarantee.
Existing approaches. Empirically, Conformal Predictors are weak selective classifiers, limiting their real-world utility. We show this problem is not resolved by re-weighting the empirical CDR near test point (uan 2022), nor by applying separate per-class hypothesis tests, nor by APS con- formal score functions (Romano al. 2020), nor by adaptive regularization RAPS (Angelopoulos et al. 202T. and occurs even on in-distribution data.
Solution. In the present work, we demonstrate, with focus on Transformer networks (Vaswani iet al. (207)). first that closer notion of approximate conditional coverage obtained via the stronger validity guarantees of Mondrian Conformal Predictors not sufficient in itself to achieve our desired desiderata. Instead, we treat such Conformal Predictors as weak selective classifiers, which serve as the underlying learner to construct a taxonomy for Venn Predictor (Vovk et al., (003), a valid multi-probubiliity calibrator. This is enabled by data-driven partitions determined by KNN (Devroye) jet al. 1996) approximations, which themselves encode strong signals for prediction reliability. The result principled, well-calibrated selective classifier, with a sharpness suitable even for highly imbalanced, low-accuracy settings, and with at least modest robustness to covariate shifts.
2 MONDRIAN CONFORMAL PREDICTORS AND VENN PREDICTORS
A stronger than marginal coverage guarantee can be obtained by Mondrian Conformal Predictors (Vovk et al. 2005). which guarantee coverage within partitions of the data, including conditioned on the labels. Such Predictors are not sufficient for obtaining our desired desiderata, but serve as principled approach for constructing a Venn taxonomy with a desirable balance between specificity vs. generality (a.k.a., over-fitting vs. mnder-fitting). the classic problem of the reference class.
We omit the randomness component, which is not practically relevant the sample sizes considered here.
2

---

Under review as a conference paper at ICLR 2023
Both Mondrian Conformal Predictors and Venn Predictors defined by the choice of par- ticular taxonomy. A taxonomy is a measurable function E Z' x 2 + E, where E is measurable space. A E(( 2r), 2) is referred to category, and corresponds to classification of 2, as via an attribute or label. The p-value of a Mondrian Conformal Predic- tor is then determined similarly to Conformal Predictors, but with conditioning the category:
e = |i=/+I,....N ey
where ej = E((ZI...., 21),,,) A 2j E Dea and eN+1 == E((2),..., (IN+1, (N+1)). We will refer to the resulting coverage as approximate conditional coverage, middle ground between marginal coverage and conditional coverage, which is not possible in the distribution-fiee setting with a finite sample (Lei & Wasserman 2014):
N+1
Theorem 2 (Approximate Conditional Coverage of Mondrian Conformal Predictors Vovk et al. 2005 Vovk 2012)). Provided the points of Dea and Die exchangeable within their categories defined by laxonomy E Moondrinnexchhngeablin
the following coverage guarantee holds for given a: P (Yx+1 E C(XN+1) El, (EN+1))) -1.
Venn Predictors dispense with p-values (and coverage) and instead seek validity via calibration. They are multi-pro puobi-probabiiltty calibrators, in that they produce not one probability, but multiple proba- bilities for a single class, a compromise which yields an otherwise quite strong theoretical guarantee. Venn Predictors have simple, intuitive appeal: They amount to calculating the empirical probabil- ity among similar points to the test instance. The quirk to enable the theoretical guarantee that this is done by including the test point itself, assigning each possible label; hence, the generation of multiple empirical probability distributions. Specifically, for #N+1 we first determine its category, typically some classification from the underlying model We will use T to indicate all instances in the category, where we have added (IN+1, c) assuming the true label is c. We then calculate the empirical probability:
Pe(c') M('" "ie,,")TT: D'' =cH AddE
We repeat this assuming each label is the true label, in turn, equivariant with respect to the tax- onomy (that is, without respect to the ordering of points in the category). Remarkably, one of the probabilities from multi-probability Venn Predictor is guaranteed to be perfectly calibrated. For our purposes, will be sufficient to show this for the binary case. For a random variable O E [0, 1]. such as the probablistic output of classifier, and a binary random variable Y {0, 1). we will follow previous work (Vovk& & Petej] 22014) in saying O is perfectly calibrated if E(Y () = O a.s. The validity of the Venn Predictor is then:
Theorem 3 (Venn Predietor Calibration Validity (Theorem Vovk & Petej (2014) ). Provided the
points of Dea and Dre are IID, among the two probabilities output by a Venn Predictor for Y = 1, po(1) and pi (1), one perfectly calibrated.
TASKS: CLASSIFICATION WITH TRANSFORMERS FOR NLP
The taxonomies will be chosen based on the need to partition the high-dimensional input of NLP tasks without having explicit attributes known in advance. We first introduce general notation for sequence labeling and document classification tasks. Each instance consists of a document, æ = 31. St. TT, of T tokens: Here, either words amino acids. In the case of supervised sequence labeling (SSL), we seek to predict أ = .i,..., .a......th.. .... .r. the token-level labels for each token in the document, and we have the ground-truth token labels, Yr. for training. For document classification (DC), we seek to predict the document-level label ÿ. and we have at training.
For each task, our base model is Transformer network. After training and/or fine-tuning, we fine- tune a kertel-width CNN (MEMORY lAYER) over the output representations of the Transformer, producing predictions and representative dense vectors at a resolution (c.g., word-level or document- level) suitable for each task. Following past work, we will refer to these representations as "exemplar vectors" primarily to contrast with "prototype", which is sometimes taken refer class-centroids,
Existing taxonomies for Venn Predictors include using the predictions from classifier (Lambrou et al. 2015), variations on nearest neighbors (Johansson al. 2018). and isotonic regression, the Venn-ABERS
Predictor (Vovk& & Petej] 2014 Vovk et al. 2015).
3

---

Under review as a conference paper at ICLR 2023
Table I: Overview of experiments.
Label
Task
|Pattaa
iPael
Buse network
Acc.
Characteristics
PROTEIN
SSL
560k
(30k.7k)
12000
BERTAASE
Mid
In-domain (2 test sets)
GRAMMAROOD
SSL
35k
93k
B
BERT
Low
memmii--sitte--mmbblle
SENTIMENT
DC
2
16k
488
BERT
High
In-domain (acc. > a)
SENTIMENTOOD
DC
2
16k
5k
R2000
BER' LARCEE
Mid-Low
Domain--hifted//On
Trua deep siluaa ischert cavid
Toll Traa laye (1-D CSN your bödlen lepuns
1 +
1 Vgl fi
22 mose Mnlel
Save ensepli vacies auocinndrens dra fo sokking othocion endl
Trate ENN aprodiaatio of dop unooet
Caneenl wook
ADVEL Prakstenccs
409,
Vij R
Qutont
Cenernt Yens-AUNE Prckse
adectee chottiio
PIEE wkuthi chadfeattos
1 Canaa vnalin brrtoc dl
(a) Overview
(b) Taxonomy and prediction signals
Figure 1: On left is a high-level overview. The right illustrates category assignment for the VENN-ADMIT Predictor, and the key prediction signals enabled by f(x) KNN, Predictions become more reliable with increased label and prediction matches into training (g) and lower distances to training (d). The resulting well-calibrated selective classifiers are robust changes in the proportion of these categories.
whereas the "exemplars" are unique to each instance. We will subsequently use fxxe) RC for the prediction logits produced by the MEMORY LAYER corresponding to the token at index (; ne as the corresponding softmax normalized output for class c; and T, as the associated exemplar vector. For SSL there are T such logits and vectors. For DC, f corresponds to single representation of the document, with (xxx formed by a combination of local and global predictions (as described further in the Appendix). In the present work, we will primarily only be concerned with Transformers at the level of abstraction of the exemplar vectors, Tr; we refer the reader to the original works describing Transformers (Vaswani et al., 2017) and the particular choice for the MEMORY LAYER (Schmaltz) 2021) for additional details. Splits. Our baselines of comparisons use Di.. Dea. as the training and calibration sets, respectively. For our methods, will assume the existence of an additional disjoint split of the data, Dknn for setting the parameters of the KNNs. We will also require two calibration sets, Dme, which serves the calibration set for the Mondrian Conformal Predictor, and Dvp, which serves as the calibration set for the Venn Predictor.
METHODS
We first define the taxonomy for our Mondrian Conformal Predictor, ADMIT. The resulting sets will serve as baselines of comparisons, but will primarily be used as weak selective classifiers for defining the taxonomy of our Venn Predictor, the VENN-ADMIT Predictor. In both cases, we make use of non-parametric approximations of Transformers, which encode strong signals for prediction reliability, including over distribution-shiffs, and are at least as effective as the model being approx- imated (Schmaltz) 2021). Predictions become less reliable at L distances farther from the training set and with increased label and prediction mismatches among the nearest matches. We further in- troduce an additional KNN approximation that serves as a localizer, relating a test instance to the distribution of the conformal calibration set, which serves conservative heuristic for category assignments. Figure provides an overview of the components and a visualization the prediction signals and Venn taxonomy.
4

---

Under review as a conference paper at ICLR 2023
4.1 KNN APPROXIMATION OF TRANSFORMER NETWORK
In order to partition the feature space, we first approximate the Transformer as a weighted combina- tion of predictions and labels over Der (Section 4.1.1.. This approximation, f()) then becomes the model we use in practice, rather than the logits from the Transformer itself. We use this approxi- mation partition the data via feature that separates more reliable points from less reliable points (Section 1..2 and via a coatnce-to-trainnng band (Section 4.1.3).
4.1.1 RECASTING A TRANSFORMER PREDICTION AS WEIGHTTING OVER TRAINING SET
We adapt the weighte KNN approximation of Schmaltz (002)) for the multi-class setting. As in the original work, the KNN is trained to minimize prediction mis mas-hht against the output of the MEMORY LAYER (not the ground-truc truth labels). Training is performed on a 50/50 split D described further in Appendix C
(x,) = (I
KNN 3 +
Σ b arg K min Payl)
wk w (fanh(f((zx) + + -7)
(2)
11r.-r111
exp (- 1|r
Tkll2/1)
where Wk
exp (-1|r: - rk 12/1)
ME arg K min ic (Prl))
||re-rilla
7f the ground-truth label (y for DC, Yt for SSL) for class c transformed to in {-1,1}. K small in practice; K 25 in all experiments here, and in general can be chosen using k This approximation has 2 C + learnable parameters, corresponding to 8 and y for each class, and the temperature parameter 77. We indicate the softmax normalized output for each class with x (Ix) KNN, This model is used to produce approximations over all calibration and test instances.
4.1.2 DATA-DRIVEN FEATURE-SPACE PARTITIONING: TRUE POSITIVE MATCHING CONSTRAINT
For each calibration and test point, we define the feature q. [0. K] as the count of conseculive sign matches of the prediction of the KNN, JKNN with the true label and MEMORY LAYER prediction of the up to K nearest matches from the training set, Dr.:
g.. (K)=
Σ
[ KNNN
0h
Tot = -tt] A lg. 1) = 1],
(4)
K
arg K. MID LE(1 (Piel..PPPLl)
O. We further also use the 2 distance to the nearest training set match as basis for subsetting the distribution into distance bands, as discussed in the next section:
with (0) =
min ||,, -rrll,, {1,...,, (P.r
4.1.3 DATA-DRIVEN FEATURE-SPACH PARTITIONING: COTTANCE-TO-TRAIIINGG BAND
We define the partition, B, around each v, Dre, constrained to q, the -i- sesttacce-to-traiing band with a radius of ッ = 5 8,, with E + as user-specified parameter and & as the estimated standard deviation of constrained true positive calibration set distances, š std((d, 1, I (Daul), I,ll 11 0, KNN y;l):
(T+
B(x,, w, qo de Dea) {ay : x. Dea. dj E (d. w, de + w). = 9
(6)
4.2 PREDICTION SETS WITH APPROXIMATE CONDITIONAL COVERAGE: ADMIT
We then define a taxonomy for our Mondrian Conformal Predictor by the partitions defined by B and the true labels: (,,, )z = B(x,, 9r, de; Dea) A This conditioning on the labels means we apply split-conformal prediction separately for each label, ""abcl-condittonaa" conformal prediction (Vovk et al. 2005) Vovk 2012 Sadinle et al. 2018). which provides built-in robustness to label proportion shifts (c.f., Podkopavy & Ramdas 2021 }. We will refer to this method and the resulting sets with the label ADMIT. We always include the predicted label in the set. Pseudo-code appears in Appendix E
5

---

Under review as a conference paper at ICLR 2023
4.3 INDUCTIVE VENN-ADMIT PREDICTORS & SELECTIVE CLASSIFIERS
An ADMIT Predictor maps to a weak selective classifier. We instead seek a well-calibrated selec- tive classifier, which we define as follows, as a straightforward coarsening of the probability, only calculated over the admitted subset:
Definition 2 (Well-calibraie calibrated selective classifiers). We take as S E [0.1] the random variable dicating the probability non-rejected prediction from selective classifier, g. should be admit- ted. We will say selective classifier conservatively well-calibrated (or just "well-calibrtted" if a for given (0,1).
B(Y S 2 - a)
We construct such a selective classifier, 9. as follows. Construct ADMIT sets for DTP and Die. in both cases using Dine the calibration set. Next, convert the ADMIT sets into selective classifiers, Sweak. as in Remark cq Calibrate the non-rejected predictions of Deo (i.e., the JKNN predictions that and now admitted predictions of gweak) using Venn Predictor with a taxonomy defined by B and the prediction of the KNN, jKNN now using Did as the calibration set. The TENN-ADMIT selective classifier is then the following decision rule, where Po(1), P1 (1) are the two Venn probabilities associated with Iweak:
were singleton
{1
if min(po(1).pi(1)) < -a otherwise
g(Iz)
LOKNN
We can then take as S == 1, if g(x+)) * 1 (as used in Def. 2): i.e. a coarsening of the probability of the points admitted by g-
Proposition 1 (VENN-ADMIT selective classifiers are well-calibrated). Provided the points of DvD and De.. restricted to are IID, the selective classifier g defined by Eq. 7is well-calibrated the sense of Definition 2
This follows directly from Theorem
4.4 ROBUSTNESS
VENN-ADMIT selective classifiers robust covariate shifts that correspond changes in the proportion of the partitions. We propose two simple heuristics that provide additional robustness. We first state useful propositions that will justify the heuristics.
Proposition 2 (VENN-ADMIT calibration invariance to partition censoring). VENN-ADMIT se- lective classifiers remain well-calibrated in the sense of Definition with censoring of I or more partitions B.
This directly follows from the fact that both the weak selective classifier (ADMIT) and the well- calibrated selective classifier VVEN-ADMMT treat each partition independently. We thus struct a new selective classifier, g', that maps any input in the censored partition(s) to 1. D
Proposition 3 (VENN-ADMIT calibration invariance to test point up-weighting). VENN-ADMIT selective classifiers remain well-calibrated in the sense of Definition 2 [1, 00) when calculating the empirical probabilities of the TENN-ADMIL Predictor.
using any test point weight
Increasing the test point weight above can only decrease the lower probability produced by the VENN-ADMIT Predictor (since the denominator in Eq. can only increase). Since Def. 2 is only calculated for admitted points, this notion of conservative well-calibration is retained. D
4.4.1 CENSORING LESS RELIABLE DATA PARTITIONS
The feature can be viewed as an ensemble across multiple similar instances from training. Greater agreement suggests greater confidence in the prediction. We can restrict partitions with the max- imum value, q = K 25, here. By Prop. calibration of the selective classifier is maintained.
4.4.2 LOCALIZED UP-WEIIHTING BASED ON CATEGORY SIMILARITY
We can up-weight the test point when calculating the VENN-ADMIT probabilities using an addi- tional KNN localizer, / (x: KNN in this with Dea the support set of the KNN and single
KNN

---

Under review as a conference paper at ICLR 2023
parameter, temperature weight. Weights increase above with greater dissimilarity between test point and its assigned category. Additional details in Appendix B By Prop. B. calibration of the selective classifier is maintained.
4.4.3 ROBUST
SELECTIVE CLASSIHICATIONS
For given test point, 2t, first construct weak selective classifier with the ADMIT procedure of Section 4.2, followed by calibration via the VENN- ADMIT Predictor (Section (43) Optionally,
apply the heuristics described in Sections 4.4.1 4.4.1
and 4.4.2 Pseudo-code appears in Appendix E
5 EXPERIMENTS
We have established that the VENN-ADMIT selective classifications are conservatively well- calibrated; however, we have not said anything about the proportion of points that will be admit- ted. If the procedure unnecessarily strict, we may nonetheless prefer the output from alternative approaches, such Conformal Predictors. Additionally, the VENN- ently robust to changes in the proportions of the data partitions, but whether that corresponds to real-world distribution shifts is task and data dependent. To address these concerns, we turn to em- pirical evaluations. We evaluate on a wide-range of representative NLP tasks, including challenging domain- shifted and class imsalancbbdeeed settings, and in settings in which the point prediction accura- cies are quite high (marginally > 1-a) and in which they are relatively low. We follow past work in setting a 0.1 in our main experiments. We set 6 1. We summarize and label our benchmark tasks, the underlying parametric networks, and data in T disjoint set of size 144k, the CB5 13 from PROTEIN, was used for initial methods development. In the Table, D Dvalid is the original held-out validation set associated with each task. For the ADMIT and VENN-ADMIT approaches, a random 10% sample of Dvalid serves as the disjoint Kun set for training the KNNs, with the re- maining data split evenly for Dine and Dvp. The baseline and comparison methods are given the full Dvalid as Dra- The Appendix provides implementation details on constructing the exemplar vectors, for each of the tasks from the MEMORY LAYER.
Predictor is inher-
5.1 COMPARISON MODELS
As a distribution-free baseline of comparison we consider the size- and adaptivenesssoptimiie RAPS algorithm of Angelopoulos et al. (202T) RAPS sizE and RAPS which combine reg- ularization and post-hoc Platt-scaling calibration (Plat 1999; Guo et al. 2017), on the output of the MEMORY LAYER. Using stratification of coverage by cardinality as metric, RAPSADAPT. in particular, was reported to more closely approximate conditional coverage than the alternative APS (Romano et al. 2020), with smaller sets. CONFBASE a split-conformal point of reference for simply using the output of f [(z)KNN without further conditioning, nor post-hoc calibration. LOCALcose is localized conformal (Guan 2022) baseline using the KNN localizer f (x)
KNN Across methods, the point prediction is included in the set, which ensures conservative (but necessarily exact/upper- bounded) coverage by eliminating null sets.
We use the label ADMIT indicate the Mondrian Conformal sets. We use the label VENN-ADMIT to indicate VENN-ADMIT selective classifications with test-point up-weighting with the KNN localizer (Sec. 4.4.2. and VENN-ADMIT,K
those with the further restric- tion of q = K (Sec. 4.4.1. The results VENN-ADMIT- exclude test-point upieeighting; VENN- A DMIT, gK- - excludes test-point weiweighting, but restricts to = K.
Calibration in general is difficult to evaluate, with conflicting definitions and metics (Kull et al. 2019 Gupta & Ramdas, 2022 inter alia). In the hypothesis testing framework, approaches have been proposed to make marginal Conformal Predictors more adaptive (i.e., to achieve closer approx- imations to conditional coverage), but evaluations omit class-wise singleton set coverage, arguably the baseline required quantity needed in practice for classification. In contrast, our desiderata are easily evaluated and resolve these concerns: Of the admitted points, we calculate the proportion of points matching the true label, y E C, for each class. That is, given an admitted prediction (or simi- larly, a singleton set), an end-usee user should have confidence that the pla-slass accuracy is at least 1 a-a. Additionally, other things being equal, the proportion of admitted points (+) should be maximized.
7

---

Under review as a conference paper at ICLR 2023
Table 2: Model approximation vs. MEMORY LAYER accuracy/
PROTEIN (ACC.)
GRAMMARDOD (Fis)
SENTIMENT (ACC.)
SENTIMENTOOD (Acc.)
Model/Approx.
1015
%
Ph.
The
MEMORY LAVER
0.75
0.77
0.70
0.59
0.40
0.92
0.93
0,92
0.78
0.76
0.77
0.71
0.58
0.43
0.92
0,93
0.92
0.79
fla
0.77
0.70
0.42
0.93
0.78
Table 3: The empirical behavior of the calibration points differs significandly with q = vs. 4 4= K, and as the distance to training (de) varies, in terms of f (x)) point accuracy (ACC.), and the distribution of over-confidence and under-confidence (reflected in 20.1 0.1 quantile threshold), (Validation set of PROTEIN.)
PROTHIN:
Class Label
Sequence
Labeling)
HELIX
y = STRAND
y
OTHER
y
(H,
0]
Subset
#0.1
ACC.
+01
AcC.
#0.1
AcC.
40.1
Acc.
0.07
0.59
0.07
0.07
0.56
0.05
0.18
0.56
0.10
0.11
0.57
0.22
9 K
0,96
0.98
0.12
0.95
0.94
0.04
0.92
0.92
0.08
0.94
0.96
0.24
[0,
0.12
0.81
0.37
0.06
0.70
0.21
0.13
0.74
0.42
0.11
0.76
d, < median
0 0.09
0.64
0.02
0.07
0.65
0.01
0,16
0.55
0.03
0.12
0.60
0.07
== K
0.96
0.98
0.07
0.95
0.96
0.03
0,93
0.94
0.06
0.94
0.96
0.15
2 E []
0.27
0.87
0.16
0.09
0.81
0.08
0.14
0.79
0.18
0.16
0.82
0.43
median 0
0.07
0.57
0.05
0.07
0.53
0.04
0.19
0.57
0.07
0.11
0.56
0.16
0.98
0.04
0.90
0.01
0.03
0.02
0.93
0.94
E [0, K]
0.09
0.76
0.21
0.05
0.62
0.12
0.13
0.70
0.24
0.09
0.70
0.57
6 RESULTS
Across tasks, the KNNs consistently achieve similar point accuracies the base networks (Table This justifies their use in replacing the output logit of the underlying Transformers. Table 3 then highlights our core motivations for leveraging the signals from the KNNs: There are stark differences across instances as increases and as the distance to training increases (shown here for PROTEIN, but observed across tasks). In order to obtain calibration, coverage, or even similar point accuracies, on datasets with proportionally more points with q < K, and/or far from training, we must control for changes in the proportions of these partitions.
Table 4 and Table [S) contain the results. The Conformal Predictors RAPS and APS behave as advertised, obtaining marginal coverage (not shown) for in-distribution data. However, the addi- tional adaptiveness of these approaches does not translate into reliable singleton set coverage. More specifically: The Conformal Predictors tend to only obtaín singleton set coverage when the point accuracy of the model is > 1 a, including over in-distribution data. Only for the high- accuracy, in-distribution SENTIMENT task 5T is adequate singleton set coverage obtained. For the in- mn-distribution PROTEIN task, coverage falls to the 70s for CASP12 and the low 80s for TS 1 15 for the y = OTHER class (Table 4 On the low- low-accuracy, class-imbalanen imbalanced GRAMMAROOD task (Table 5). in which the minority class occurs with proportion less than o, singleton set coverage for the minority class is very poor. Re-weighting the empirical CDF near a test point is not an adequate solution to obtain singleton set coverage. The LOCALcOSP approach obtains cov- erage on the distribution-shifted SENTIMENTOOD task (Table 5) but coverage is inadequate, as with simpler Conformal Predictors, for the GRAMMAROOD task. The stronger per-elass Mon- drian Conformal guarantee is also not sufficient to obtain singleton set coverage in practice. The ADMIT sets obtain less severe under-coverage on the GRAMMAROOD task compared to the marginal Conformal Predictors, but singleton set coverage is not clearly better on the in-distribution PROTHIN task. The under-coverage of these approaches could come as a surprise to end-users. In this way, such split-conformal approaches are not ideal for instance-level decision making.
Fortunately, we can nonetheless achieve the desired desiderata with distribution- meth- ods, but we need to instead rely on Venn Predictors, and recast our goal in terms of calibra- tion rather than coverage. The base approach with test- pest-point up-weighting, VENN-ADMIT, is well-calibrated across tasks. We further note that there is cost to be paid these datasets by rejecting points in all partitions other than that with q = K, as seen with VENN-ADMIT, ,x- That is, the admitted points are almost exclusively in the q K partition. By means of comparison
8

---

Under review as a conference paper at ICLR 2023
Table 4: Selective classification evaluation PROTEIN test
[C] =1 by Class Label (Amino-Arid/Tolen- avel Sequenee I Labeling)
HELIX
STRAND
OTHER
y [IL. U. O.
Method
VEC
(N
RAPS
0.88
RAPS
0.96
0.24
0.86
0.07
0.82
0.17
0.90
0.48
APS
0.96
0.24
0.86
0.07
0.83
0.17
0.90
0.48
LoCAL
0.96
0.23
0.85
0.07
0.86
0.18
0.91
0.49
ADMIT
0.95
0.23
0.88
0.07
0.76
0.14
0.88
0.43
VENN- ADMITW
0.98
0.14
0.91
0.01
0.512
0,U8
0.95
0.24
VENN-ADMIT
0.98
0.14
0.92
0.03
0.93
0.08
0.96
0.24
VENN-ADMIT
MENT-ADMITor
7,2501
RAPSan
0.96
0.14
0.85
0.05
0.77
0.13
0.87
0.31
RAPS
0995
0.16
0.85
0.96
0.78
0..1
0.86
0.36
APS
0.95
0.15
0.86
0.05
0.74
0.15
0.85
0.36
LOCALç00
0.97
0.14
0.82
0.03
0.84
0.12
0.90
0.30
ADMIT
0:94
0.16
0.87
0.06
0.67
0.12
0.83
0.34
MMMIT
0.95
0.09
0.85
0.90
0.06
0.92
0.16
DEST-ADMIT,
0.09
0.81
0.89
VENN-ADMIT,RF
0.09
0.87
0.89
Table 5: Selective classification evaluation on distribution-shiftee data. SENTIMENT (in-dist.) for contrast.
[C] -1 by Class Label (Binacy SSL and DC1
(0.1)
SENTIMENTOOD (V 4750)
[Li)g (AcC.)
0.86
0.50
0.72
0.50
0.79
1.0
CONNToo
0.86
0.50
0.72
0.50
0.79
1.0
RAPS
0.79
0.27
0.91
0.33
0.86
0.61
0.75
LoCALeow
ADMIT
0.96
0.16
0.18
0.33
TENN-ADMIT-W
0.95
0.14
0.94
0.17
0.94
0.31
VENN-ADMIT
0.96
0.14
0.94
0.17
0.94
0.31
VENN-ADMIT
0.95
0.13
0.94
0.17
0.95
0.29
VENN-ADMIT
0.95
0.13
0.94
0.17
0.95
0.29
SENTIMENT 485)
[
(LO (AcC.
CONFaAI
0.94
0.50
0.91
0.50
0.93
1.0
RAPS.mrT
0.97
0.47
0.96
0.46
0.96
0.91
RAPS
0.94
0.50
0.91
0.50
0.90
1.00
APS
0.96
0.47
0.95
0.46
0.96
0.92
LoCALoow
0,95
0.43
0.94
0.44
0.95
0.55
ADMIT
0.95
0.42
0.93
0.40
0.94
0.82
VENN-ADMIT-W
0.34
0.75
SEN-ADMITTa--W
0.75
VINN-ADMIT
0.94
0.40
0.94
0.76
VENN- PENN-ADMIT.r:
0.94
0.37
0.94
0.40
0.94
0.76
GRAMMAROOD (V 92597)
160 (ACC.)
0.98
0.93
0.27
0.07
0.93
1.0
0.98
0.99
RAPS
RAPS.o
0.97
0.54
APS
0.97
0.79
0.34
0.05
0.94
0.83
LoCALcese
1.00
0.85
0.19
0.05
0.95
0.91
ADMIT
0.95
0.20
0.77
0.02
0.92
0.22
VENN-ADI ADMIT w
1,00
0.11
0.75
0.01
0.98
0.12
MONN-ADMIT.x-.
1.00
0.08
0.80
20.01
0.99
0.00)
VENN-ADMIT
1,00
0.05
0.92
<0.01
0.99
0.05
VENN-ADMIT,C
with the VENN- ADMIT- w and VENN-ADMIT, -- ablations, which calibration obtained by VENN-ADMIT gk without weighting, we would recommend making this restriction (i.e., using VENN-ADMIT gK) as the default approach in higher-risk settings as an additional safeguard.
7 CONCLUSION
The finite-sample, distribution-fred guarantees of Conformal Predictors are appealing; however, the coverage guarantee is too weak for typical classification use-cases. We have instead demonstrated that the key characteristics desired for prediction sets are instead achievable by calibrating weak selective classifiers with Venn Predictors, enabled by KNN approximations of the deep networks.

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
We will provide link our pytorch code and replication scripts with the camera-ready version of the paper. The data and pre-trained weights of the underlying Transformers are publicly available and are further described for each experiment in the Appendix.
ETHICS STATEMENT
Uncertainty quantification is a comeestone for trustworthy AI. We have demonstrated principled approach for selective classification that achieves the desired desiderata in challenging settings (low accuracy, Mlas-imbbllanced distribution shifted) under a stringent class-wise evaluation scenario. We have also shown that alternative existing distribution-free approaches do not achieve the quanti- ties typically needed in classification settings.
Whereas the use-cases for prediction sets with marginal coverage are relatively limited, the use-cases for reliable selective classification are numerous. For example, reliable class-conditional selective classification directly applies to routing to reduce overall computation (e.g., use small, fast mod- els, only deferring to larger models for rejected predictions), and higher-risk settings where less confident predictions must be sent to humans for further adjudication.
An unusual and advantageous aspect of a VENN- ADMIT Predictor, and which further distinguishes it from post-hoc Platt-scaling-style calibration (Plati 1999 Guo et al. 2017). is degree of inherent example-based interpretability: The calibrated distribution for a point is a simple transformation of the empirical probability among similar points, with partitions determined by a KNN that can be readily inspected. This matching component yields a direct avenue for addressing group-wise faireess: Known group attributes can be incorporated categories ensure group-wise calibration.
REFERENCES
Anastasios N. Angelopoulos and Stephen Bates. A Gentle Introduction to Conformal Prediction and Distribution-Frre Uncertainty Quantification. CoRR, abs/2107.07511, 2021. URL. https:
//atxxiv.org//abs/2007..0.00
Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Uncertainty Sets for Image Classifiers using Conformal Prediction. In International Conference on Learning Representations, 2021. URL https: httt:::://oenzeeieeww
Helen M Berman, John Westbrook, Zukang Feng, Gary Gilliland, Talapady N Bhat, Helge Weissig, Ilya N Shindyalov, and Philip E Bourne. The protein data bank. Nucleic acids research, 28(1): 235-242, 2000.
Ciprian Chelba, Tomás Mikolov, Mike Schuster, Qi Ge, Thorsten Brants, Phillipp Koehn, and Tony Robinson. One Billion Word Benchmark for Measuring Progress in Statistical Language Mod- eling. In Haizhou Li, Helen M. Meng, Bin Ma, Engsiong Chng, and Lei Xie (eds.), INTER- SPEECH 2014, 15th Annual Conference the International Speech Communication Association, Singapore, September 14-18, 2014, pp. 2014/114 2635. html Sppech..rg//aree. httg:/arcivee/iine
ISCA, 2014. URL holllhtt:///// //ww. isca
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedingy of the 2019 Confer- ence of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Volume I (Long and Short Papers), pp. 4171-4188 Minncapolis, Min- nesota, June 2019. Association for Computational Linguistics. doi: 10.18653/v1/N19. 1423. URL http:///wacaaattoo........o
1423
Lue Devroye, Lászłó Györfi, and Gábor Lugosi. A Probabilistic Theory of Pattern Recognition. In Stochastic Modelling and Applied Probability, 1996.
Sara El-Gebali, Jaina Mistry, Alex Bateman, Sean R Eddy, Aurélien Luciani, Simon C Potter, Mat- loob Qureshi, Lomna J Richardson, Gustavo A Salazar, Alfredo Smart, Erik L L Sonnhammer, Layla Hirsh, Lisanna Paladin, Damiano Piovesan, Silvio C Tosatto, and Robert D Finn. The Pfam protein families database in 2019. Nucleic Acids Research, 474DD):1427 2019.
10

---

Under review as a conference paper at ICLR 2023
ISSN 0305-1048. doi: 10.1093/har/gky9955
URL
atticle/4T/bL/D42/5544131
Leying Guan. Localized Conformal Prediction: A Generalized Inference Framework for Conformal
Prediction. Biometrika, 07 2022. ISSN 1464-3510. doi: 10. 1093//iomettssac00400 URL httppts::
//doi. www.oogg//... //doi.org/10..eooooooo 1093/009///0 omet asac040 asac040.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On Calibration of Modern Neural Networks. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' 17, pp. 1321-1330. JMLR.org, 2017.
Chirag Gupta and Aaditya Ramdas. Top-label calibration and multiclass-to-binary reductions. In International Conference Learning Representations, 2022. URLhtttss://ppeeeeeee
net feet/foree Eorum? Wid-miiiw--aaPP.ee
Ulf Johansson, Tuve Löfström, and Häkan Sundell. Venn predictors using lazy learners. In The 2018 World Congress in Computer Science, Computer Engineering & Applied Computing, July 30-August 02, Las Vegas, Nevada, USA, pp. 220-226. CSREA Press, 2018.
Divyansh Kaushik, Eduard Hovy, and Zachary Lipton. Learning The Difference That Makes A Difference With Counterfactually Countefactuully-AAggeent
Representations, 2020. URL Augmentee Data. International Conference on Learning
Michael Schantz Klausen, Martin Closter Jespersen, Henrik Nielsen, Kamilla Kjaergaard Jensen, Vanessa Isabell Jurtz, Casper Kaae Soenderby, Morten Otto Alexander Sommer, Ole Winther, Morten Nielsen, Bent Petersen, et al. Netsurfp-2.0: Improved prediction of protein structural features by integrated deep learning. Proteins: Structure, Function, and Bioinformatics, 2019.
Meelis Kull, Miquel Perello-Nicto, Markus Kängsepp. Telmo Silva Filho, Hao Song, and Peter Flach. Beyond Temperature Scaling: Obtaining Well-Calibrated Multiclass Probabilities with Dirichlet Calibration. Curran Associates Inc., Red Hook, NY, USA, 2019.
Antonis Lambrou, Ilia Nouretdinov, and Harris Papadopoulos. Inductive Venn Prediction. Annals of Mathematics and Artifficaa Intelligence, 74(1):181-201, 2015, doi: 10.10077/10047--0144444222
Jing Lei and Larry Wasserman. Distribution-free prediction bands for non-parametric regression.
Journal of the Royal Statistical Society: Series B (Statistical Methodooogy),, 76(1): 2014. doi: https://doi.oor//0000 11tss 12021. URL ftttp:://za..onnieeet wwl.ey......ly...............e.. wiley.
com/ com/doi/abs// wwtp//a////// httpaa///11..1111....... 1111/ 12021
Ilya Loshchilov and Frank Hutter. Decoupled Weight Decay Regularization, 2019.
Andrew L. Maas, Raymond E. Daly, Peter Pham, Dan Huang, Andrew Y. Ng. and Christopher Potts. Learning Word Vectors for Sentiment Analysis. In Proceedings the
the 49th Annual Meeting of the Association for Computational Linguisties: Human Language Technologies, pp. 142-150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics. URL https:
w/aclanthology.ozg//3
1015
John Moult, Krzysztof Fidelis, Andriy Kryshtafovych, Torsten Schwede, and Anna Tramontano. Critical assessment methods of protein structure prediction (CASP)-Round XII. Proteins: Structure, Function, and Bioinformatics, 86:7-15, 2018. ISSN 08873585. doi: 10.1002/prot.
25415. BtLhhttp://ee htttt::://o...wlee............ee wwwwy..ww.... com. 10. 1001 www.11000/ppro....0 wtt.:////....1.........
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In Proceedings of the 13th European Conference Machine Learning, BCML'02, pp. 345-356, Berlin, Heidelberg, 2002. Springer- ISBN 3540440364. doi: 10. 10.100773-540-367555
stllhttss://do1
C. 0011://11110070000000000 1_29
John C. Platt. Probabilistic Outputs for Support Vector Machines and Comparisons to Regularized Likelihood Methods. In Advances in Large Margin Classifiers, pp. 61-74. MIT Press, 1999.
11

---

Under review as a conference paper at ICLR 2023
Aleksandr Podkopaev and Aaditya Ramdas. Distribution-fiee uncertainty quantification for clas- sification under label shift. In Cassio de Campos and Marloes H. Maathuis (eds.), Proceed- ings of the Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pp. 844-853. PMLR, 27-30 Jul 2021. URL https: httpass//ppoceeiingg......
www..ppees//ve 61/padkopaev2la. html]
Roshan Rao, Nicholas Bhattacharya, Neil Thomas, Yan Duan, Xi Chen, John Canny, Pieter Abbeel, and Yun S Song. Evaluating Protein Transfer Learning with TAPE. Advances in Neural Information Processing Systems, 2019.
Marek Rei and Helen Yannakoudakis. Compositional Sequence Labeling Models for Error De- tection in Learner Writing. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1181-1191, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10.18655/11P11-1122 URL hittps://wwe ac web. org/ antho Sorerhhoooyyyooooo ogy/p16-1111
Yaniv Romano, Matteo Sesia, and Emmanuel J. Candès. Classification with valid and adaptive coverage. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS 20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
Sara Rosenthal, Noura Farra, and Preslav Nakov. SemEval-2017 Task 4: Sentiment Analysis in Twit- ter. In Proceedings of the I 11th International Workshop Semantic Evaluation (SemEvvl-2011), pp. 502-518, Vancouver, Canada, August 2017. Association for Computational Linguistics. doi: 10.18653/v//S17-2000 URL https: /www: http://wwwwwb.....r///atttoooo//
Mauricio Sadinle, Jing Lei, and Larry A. Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114:223 234, 2018.
Allen Schmaltz. Detecting Local Insights from Global Labels: Supervised and Zero-Shot Sequence Labeling via a Convolutional Decomposition. Computational Linguisties, 47(4):729 De- cember 2021. doi: 10. 162/coli 1.00416.
4.25
Allen Schmaltz and Andrew Beam. Exemplar Auditing for Multi-Label Biomedical Text Classifi- cation. CoRR, abs/2004.03093, 2020. URL/attss://axxiitt wwwp//////////aoaaa/eaa///aaeeee /t.p//20004 03093
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is All you Need.
I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems, volume 30, pp. 6000-6010. Curran Asso- ciates, Inc., 2017. URL 3f5ee24354 (ibiee243577dee9113a00 htt.44/ceeeeeee100ccccccaaaaaaa0 Paper. pdf
nwwrips.....ppp..pp cc/paperr2017/Eile)
Vladimir Vovk. Conditional validity of inductive conformal predictors. In Steven C. H. Hoi and Wray Buntine (eds.), Proceedings of the Asian Conference Machine Learning, volume 25 of Proceedings of Machine Learning Research, pp. 475-490, Singapore Management University, Singapore, 04-06 Nov 2012. PMLR. URL https: http:ss//poccceeeiiee ngs. ml vovk12 html
www.:ingg....s......... press/v25/
Vladimir Vovk and Ivan Petej. Venn-Abers Predictors. In UAI, 2014.
Vladimir Vovk, Glenn Shafer, and Ilia Nouretdinov. Self-calibrating Probability Forecasting. In S. Thrun, L. Saul, and B. Schölkopf (eds.), Advances in Neural Information Processing Sys- tems, volume 16. MIT Press, 2003. httL/ttttss////rceeeee wttp::/wwweed.n..........eeeeeee neur www.nnurri.c..mm htt..//di.nnn...r...ppppeeeeepe 2003 fi 1e/ 10c 000.6622c2200
Ba
pdd
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic Learning in a Random World. Springer-Verlag, Berlin, Heidelberg, 2005. ISBN 0387001522.
Vladimir Vovk, Ivan Petej, and Valentina Fedorova. Large-scale probabilistic predictors with and without guarantees of validity. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 28. Curran As- sociates, Inc., 2015. URL ht htwp::/wwweeeee.......i.ooe.a.o. wttpe//ws..cc/pppp/////////e.1.. http:///wt//////ooo.....oaaoa/t/
12

---

Under review as a conference paper at ICLR 2023
Helen Yannakoudakis, Ted Briscoe, and Ben Medlock. A New Dataset and Method for Auto- matically Grading ESOL Texts. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguisties: Human Language Technologies. pp. 180-189, Portland, Oregon, USA, June 201 Association for Computational Linguistics. URL hww.t:tttp//... /www///www/w/////////////// ac web.
org/anthologg 1og/hh1111111111111199
Matthew D. Zeiler. ADADELTA: An Adaptive Learning Rate Method. CoRR, abs/1212.5701, 2012.
URL
abs
13

---

Under review as a conference paper at ICLR 2023
A APPENDIX: CONTENTS
Appendix B describes the KNN localizer, and Appendix provides additional details for training the KNNS. Appendix D provides guidelines on controlling for-and conveying the variance of- the sample size. We provide pseudo-code in Appendix In Appendix and H we provide additional details for each of the tasks.
B KNN LOCALIZER
We use KNN localizer, against the calibration set, as a localized conformal (Guan 2022) baseline of comparison, and to re-weight category assignments for the VENN-ADMIT Predictor. This KNN localizer recasts the test approximation output as weighted linear combination over the calibration set approximations:
(x1)
KNN
(xx))s KNN
Σ
Un (Ix))
KNN where K |Deal
(8)
arg K 11re-rslla S (Pal)
The single parameter, the temperature parameter of the [0, 1], which is calculated in an analogous manner as we in Equation is trained via gradient descent against Dto to minimize prediction discrepancies between (x:) (II:)[N KNN and f(x))(NNN As with f(x) training is performed using Dknn-
As noted in the main text, tribution shifts within the data partitions. For given test point, we calculate ff (x, KNN (Eq. 8). and then determine the augmented distribution (i.e., Pe(-). the empirical probability for a point when including the point itself, assuming a given label c) for the Venn Predictor by adding the test point up-weighted according to the weights of this KNN localizer. Specifically, the new weight for the test point is follows:
the weights from this approximation
guard against dis-
(x)))
E(j: aAET) 1bj"
where T is the set of calibration points belonging to the same category as Tt. When this weight is 1, we have the standard Venn Predictor; when this weight is greater than otherwise aberrant category assignment) and the minimum proba-
a sign of mismatch
(due distribution shift, bility estimated by the Venn Predictor becomes smaller. w E [I, 20) satisfies Prop. 3 so calibration of the selective classifier is maintained when using this weight to up-weight the test point.
C KNN TRAINING
We train f (x) and fx)) with the same learning procedure, the only difference being the underlying model that is approximated. Here, we take as of the unnormalized output logit for class c of the model be approximated (either the MEMORY LAYER f (x) and a the unnormalized output logit for class of the approximation (either f(I) KNN or fx))KNN) The binary cross- entropy loss for a token, is then calculated follows:
C. = V Σ -0(0)) logo (a - - (11-0(01) log (1 o (a
(10)
That is, we seek to minimize the difference between the original model's output and the KNN's output, for each class, holding the parameters of the original model fixed. L. is averaged over all classes in mini-batches constructed from the tokens of shuffled documents. We train with Adadelta (Zeiler 2012) with learning rate of 1.0, choosing the epoch that minimizes
8KNN Σ
arg max (o) # arg max (a)) cE)
(11)
eE)
14

---

Under review as a conference paper at ICLR 2023
the total number of prediction discrepancies between the original model and the KNNN approximation over the KNN DEV set. During training, the immediately preceding epoch did not yield a new minimal 8NNN among the running epochs, subsequently only calculate C, for the tokens with prediction discrepancies until a new minimum JKNN is found (after which we return to calculating the loss over all points), or the maximum number of epochs is reached. This has a regularizing effect: There is signal in the magnitude of the KNN output, so we aim to optimize in the direction of minimizing the residuals; however, we seek avoid over-fitting the magnitude of the outliers.
A key insight is that we can readily approximate the vast majority of the predictions from the Trans- former networks (possibly other networks, as well) using such KNN approximations, and critically, when the approximations diverge from the model, those points tend to be from the subsets over which the underlying model is itself unreliable. This implies a non-homogenous error distribution, and we find that the aforementioned procedure of iterative masking effectively learns the KNN pa- rameters without the need introduce other regularization approaches. In practice, we find that a relatively small amount of data (e.g., only 10% of the original validation sets for the tasks in the experiments in the main text) is sufficient to learn the low number parameters of the KNNs.
D CONTROLLING FOR SAMPLE SIZE
Given a single sample from Pxy (i.e., our single Deu of some fixed size), we need to convey the variance due to the observed sample size. We opt for simple hard threshold. к, given that the dis- tribution of split-conformal coverage is Beta distributed [Vovk] (012).. With, for example k = 1000, S 0.02 coverage variation within conditioning band of size 2 1000 with a 0.1, [Dtel cc. See the comprehensive tuto- rial Angelopoulos & Bates (202I) p for additional details. our experiments, if the size of least I label-specific band for a given point falls below K. we revert to set of full cardinality. For the PROTEIN, SENTIMENT, and SENTIMENTOOD tasks, we set K 1000. With the low accuracy and low frequency of the minority class in the GRAMMAROOD task, the g K partition is compara- tively small. As such, for the GRAMMAROOD task, we set K = 100 to avoid heavily censoring the q K partition, at the expense of potentially higher variability.
assuming exchangeability, the finite-sample guarantee then implies
E PSEUDO-CODE
Algorithm provides pseudo-code for constructing a well-calibrated selective classification, via the two stage approach described in the text. First, Algorithm 2 constructs an ADMIT prediction set for test point, 24. If the set only includes single class (i.e., the weak selective classifier admitted the class), the output is then calibrated via the TENN-ADMIT' Predictor (Algorithm (3) The class prediction then returned if the calibrated probability exceeds the provided threshold, a. As an additional safeguard, we can further restrict the partitions based on q. as described in Section 4.4.1
In the main text, we also compare to variation without the test-point weighting. This unweighted variation appears in Algorithm 4 and replaces the corresponding line in Algorithm |
Algorithm 1 VENN-ADMIT Selective Classification
Input: Dea. (xt Dee. 9., de), band radius w. f(z) localizer f (x)
1: procedure SLLECIVE-
de, di,w, w, (x=) aa, localizer f(x
(N) KNN
gt
Reject option
3:
C(x+) ADMIT(DP., 2t, de, (NN ..)
Mondrian Conformal prediction set (Alg
4:
i[(((x=]] =1 then
5: c'cCE ((xx)(
t Output of the weak selective classifier
6: plc') +- WEIGIITED- WENNIIIDDD-ENNN-MMMYYDD 21, qo di, we, f())
KNN (=))
7: if pf)(')
then
8:
s d'
Output: s. selective classification (class prediction reject option)
15

---

Under review as a conference paper at ICLR 2023
Algorithm 2 ADMIT Prediction Sets via Neural Model Approximations
Input: Dea, (xt Dee. 9.. de), band radius w, f(x)
I: procedure "TRRESOLLD(T) aa)
Standard split-conformal if Den Conformity scores over calibration subset
2: Sj s(2;) = # (ry))r Va, E
f [([T) 1)(1 - quantile
return 7 --
5: procedure ADMIT(D
de, w, fxx) KNN ,0)
6:
C(xx) + (0t 1
7:
I B(xr, de; Dea)
P Calibration points in band centered at xy (Eq.
8:
for E (1...., C). do
I I (zg E 1 c} Pc T a)
Subset of band for which class
11:
C(z.) C(x)) ( 2 12)
return ((x+)
Output: ((+)), prediction set
Algorithm Conservative Calibration via Inductive VENN-ADMIT Predictor (weighted)
Input: D.a. (at E Dro. 9₁, de), band radius w. f(x)ttr localizer / (x)) I: procedure CATEGORY (x,,,/
KNN
Same as in Alg. y' is the assumed true label for ar
2: T [(xr.,8))
for Iy do
4:
A C(xs) C(z,) then if it KENNN KKNN
è caleulated in Alg.
T TU ((()
b My is the true label for æ5
6:
return
7:
procedure WEIGHTED- BEEEED--EENNAAEE AENN-ADM Ie, de, f(z) KNN (x))a
8:
+ B(xi, 96, di; Dea)
> Calibration points in band centered at (Eq.
for (I....,C) CATEGOOYY x4, ((z,,0))
10:
Exclude x, from the category
11:
V + -[taaaeTT] 1/9
Sum of weights from KNN localizer Eq. 8 a E (0,
12:
for c' E (l,...,00 C} do
Pelc') 11(x" Ve:::
13:
Test point weighted empirical probability
IT+
14:
for e' E (l,.... C) do
15:
p(c)) min Pelc')
Lower Venn probability for each class (across augmented distributions)
16:
return p(-)
Output: p()). lower Venn calibrated distribution for 21.
F TASK: PROTEIN SECONDARY STRUCTURE PREDICTION (PROTEIN)
In the supervised sequence labeling PROTEIN task, seek to predict the secondary struc- ture of proteins. For each amino acid, we seek to predict one of three classes, E (HELIX, STRAND, OTHER).
For training and evaluation, we use the TAPE datasets of Rao et al. 2019 the Transformer of Rao et al. (2019). which is not SOTA on the task: while not degenerate, this fine-tuned self-supervised model was outperformed by models with HMM alignment- features in the original work. Of interest in the present work is whether coverage can be obtained with a neural model with otherwise relatively modest overall point accuracy. We use the publicly available model and pre-trained w
We approximate
input
'TAPE provides a standardized henchmark from existing models and data (El-Gebali et al. 2019 Berman
ct a
2000 Moult ct al. 2018 K Klausen et al. 2019).
https thub. com/ songl ab 1/tape
16

---

Under review as a conference paper at ICLR 2023
Algorithm 4 Conservative Calibration via Inductive VENN-ADMITT Predictor (unweighted)
Input: Dea, (+e Deer do de), band radius w, (x)
I: procedure CATEGORY(Z, 12:
2:
T [(x),,0)}
y is the assumed true label for xy
3: for E I do
4:
if 9t KNN
V3 KNNN A AC(as) = C(z,) then
D é calculated as in Alg.
5:
T T ((25.
> Mj is the true label for 2i
6: return T
7:
procedure VENN- VENN-ADMIT(Dp.. It, 9e: de,w, (2)) I I+-B(ae w. Zo Aed Dea)
8:
Calibration points in band centered at dt (Eq.
9:
for (1....; }}
10:
CATEGGGG for (l............. ............. C] do pelc)) + [((e), V
11:
12:
Empirical probability
13:
for E f1,....,C0 ......,C...
0} do p(c) min (c)) EEC
14:
Lower Venn probability for each class (across augmented distributions)
15:
return p(-)
Output:
pl.). lower Venn calibrated distribution for zz.
F.1 MEMORY LAYER
The base network consists of a pre-trained Transformer similar to BERT basE with a final convolu- tional classification layer, consisting of two I-dimensional CNNs: The first over the final hidden layer of the Transformer corresponding to each amino acid (each hidden layer is size 768), us- ing 512 filters of width 5, followed by ReLU and a second CNN using 3 filters of width 3. Batch normalization is applied before the first CNN, and weight normalization is applied to the output of each of the CNNs. The application of the 3 filters of the final CNN produces the logits, R for each amino acid.
The MEMORY LAYER consists of an additional 1-dimensional CNN, which uses 1000 filters of width 1. The input to the MEMORY LAYER corresponding to each amino acid the concatenation of the fi- nal hidden layer of the Transformer, the output of the final CNN of the base network, and randomly initialized 10-dimensional word-embedding. The output of the CNN is passed to a LinearLayer of dimension 1000 by 3. (Unlike the sparse supervised sequence labeling task of GRAMMAROOD, we use neither ReLU, nor a max-pool operation. The sequences are very long in this setting up to 1000 used in training and 1632 at inference avoid truncation-se so removing the max pool bottleneck enables keeping the number of filters of the CNN lower than the total number of amino acids. In this way, we also do not use the decomposition of the CNN with the LinearLayer, as the GRAMMAROOD task, since the sparsity over the input is not needed for this task.) The exemplar vectors for the KNNs are then the r E R 1000 filter applications of the CNN corresponding to each amino acid.
We fine-tune the base network and train the MEMORY LAYER an iterative fashion. Each epoch either update the gradients of the base network, or those of the MEMORY LAYER, freezing the counter-part each epoch. We start by updating the hase network (and freezing the MEMORY LAYER)), and we use separate optimizers for each: Adadelta (Zeiler) 2012) with learning rate of 1.0 for the MEMORY LAYER and Adam with weight decay (Loshchilov & Hutter (209)) with a learning rate of 0.0001 and warmup proportion of 0.01 for the base network. For the latter, we use the BertAdam code from the Hugging re-implementation of Devlin et al. (2019). We fine-tune for up to 16 epochs, and we use a standard cross- cross-entropy loss.
G SUPERVISED GRAMMATICAL ERROR DETECTION CANACTIAAGGRAMMARROOO (GRAMMAROOD)
The GRAMMAROOD task is a binary sequence labeling task in which aim to predict whether each word the input does (y, = 1) or does not (y/ = 0) have a grammatical error. D., and
Dra consist of essays written by second-language learners (Yannakoudakis et al. 2011 Rei & Yan-
17

---

Under review as a conference paper at ICLR 2023
nakoudakis, 2016) and Die consists of student written essays and newswire text (Cellaa et al. 2014). The test set is the FCE+NEWS2K set Schmaatz (202I).
The test set is challenging for two reasons. First, the y class appears with proportion of 0.07 of all of the words. This is less than our default value for a, with the implication that marginal coverage can potentially be obtained by altogether ignoring that class. Second, the in-domain task itself is relatively challenging, but made yet harder by adding newswire text, as evident in the large Fo.5 score differences across Dea and Di in Table 2
The exemplar vectors, r E 100000 used in the KNNs are extracted from the filter applications of a penultimate CNN layer over frozen BERT large model, in (Schmaltz (202
H TaSKS: SENTIMENT CLASSIFICATION (SENTIMENT) AND OUT-OF-DOMAIN SENTIMENT CLASSIFICATION (SENTIMENTOOD)
SENTIMENT and SENTIMENTOOD are document-level binary classification tasks in which we aim predict whether the document of negative (y 0) or positive (y 1) sentiment. The training and calibration sets, as well as the base networks, are the same for both tasks, with the distinction in the differing test sets. The training
the 3.4k IMDb movie review set used in Kaushik et al. 2020) from the data of Maas et al. 12011) For calibration, we use disjoint 16k set of reviews from the original training set of Maas et (201T). The test set of SENTIMENT is the 488-review domain test set of original reviews used in Kaushik al. (2020), and the test set of SENTIMENTOOD consists of 5k Twitter messages from SemEval-2017 Task 4a (Rosenthal et al. 2017).
Similar to the GRAMMAROOD task, the exemplar vectors, E 22000 are derived from the filter applications of penultimate CNN layer over a frozen BERT model. However, in this case, 10000 and the
the vectors are the concatenation of the document-level max-pooled vector, vector associated with a single representative token in the document, r E 1000 To achieve this, model the task multi-label classification and fine-tune the penultimate layer CNN and a final layer consisting of two linear layers with the combined min-max and global normalization loss of Schmaltz & Beam (200)). In this way, can associate each word with of (or in principle, both) positive and negative sentiment, or a neutral class, while nonetheless having single exclusive global prediction. This provides sparsity over the detected features, and captures the notion that a document may, in totality, represent one of the classes (c.g., indicate a positively rated movie overall) while at the same time including sentences or phrases that are of the opposite class (e.g., aspects that the reviewer rated negatively). This behavior is illustrated with examples from the calibration set in Table 6 We use the max scoring word from the "convolutional decomposition", a hard-attention-style approach, for the document-level predicted class the single representative word for the document. For the document-lewe prediction, we take the max over the multi-label logits, which combine the global and max local scores.
18

---

that it has not been released on video in Australia Under review as a conference paper at ICLR 2023
Table Model feature detections from snippets from D.. for SENTIMENT and SENTIMENTOOD, for which prediction sets are constructed for the binary document-level predictions. Most documents only have features of single class detected (as in the example in the final row). but our modeling choice (Section H. does enable multi-label detection as the first example, for which the true document label is positive sentiment, and the
second example, for which the true document label is negative sentiment document underlined.
The max scoring word for each
Model predictions over Dea
What an amazing film. [...] My only gripe is
and is therefore only available on TV. what
waste.
/...] But the story that then develops lacks any of the stuff that these opening fables display. [...] will say that the music by Aimee Mann was great and 1f11 be looking for the Soundtrack CD. /...!
Kenneth Branagh shows off his excellent skill in
both acting and writing in this deep thought provoking interpretation of Shakespeare's s most classic and well tten tragedy. [...]
19


Reviews:
[{"review_id": "cdA4Fq76_0", "reviewer": "Reviewer_AM2c", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This work introduces a new conformal prediction-based approach for constructing calibrated predictive intervals. The improvements are from the reliability of KNN-based approximation and a novel Venn predictor. The proposed approach is evaluated on large scale sequence modeling tasks.", "summary_of_the_review": "The proposed method in this work is novel and shows promising empirical results. I would consider raising the score if my concerns could be addressed properly.", "strength_and_weaknesses": "1. I am confused why the proposed method makes sense. Usually, such new algorithms should be justified through proper theoretical guarantee from a statistical perspective. For example, predictive inference-based methods should at least provide results on valid (unconditional) coverage and conditional coverage.\n\n2. Why is the proposed method still valid under distribution shift? Previous works need to assume the knowledge of the exact form of shifting to guarantee the exchangeability, while in this work there is no such assumption.\n\n3. Is it possible that the proposed is trading performance with computation? A time-complexity analysis is missed.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MlzEFXPrzkp", "reviewer": "Reviewer_ZHj3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors propose a KNN-based Venn-predictor for improved approximate coverage for text and token classification tasks.", "summary_of_the_review": "I do not believe this paper to be ready for publications. This is mainly based on confusing writing, that makes it difficult to understand not only the method but also the provided guarantees and judge novelty and experiments.", "strength_and_weaknesses": "Strengths:\n- The paper addresses an important problem of improving approximate conditional coverage.\n- It is generally ambitious to demand conditional coverage not only in neighborhoods but also depending on label _and_ the prediction set size. The later, in particular, is known to be difficult and sometimes hinders interpretation of uncertainty for individual examples.\n- The introduction clearly states this motivation and I also like the short overview of the NLP tasks tackled.\n- The paper includes experiments on several interesting datasets and Table 1 helps to get an overview of the tasks.\n\nWeaknesses:\nWriting:\nIn general, I feel that the method is very difficult to follow. This is mainly due to a missing high-level overview of how individual methods are put together, what is trained/calibrated on which set and how it comes together. It is made worse by an extremely confusing description of VENN predictors that are used on top of standard conformal prediction sets.\nIndividual comments:\n- The paper seems to highlight to work on transformers, which is fine. However, I find that the method itself should be independent of the architecture, so I find this emphasize confusing at times. In my opinion, writing would benefit from assuming a general function that produces features for tokens or documents depending on the task. Or am I overlooking anything transformer-specific?\n- I had difficulties following the KNN approximation introduced in 4.1. This is partly due to notation (is arg K min the K-minimum elements over I?) and some ambiguity how the parameters are actually learned. Moreover, the definition of q_t – the “count of consecutive sign matches” is not very intuitive. Is the argument really capital K, or should it be lower-case k? Why is q_t assumed to be useful?\n- Based on the appendix, in 4.2, standard conformal calibration is used to obtain thresholds. This is not really clear from 4.2 and I feel the main paper would benefit from the algorithms and a discussion.\n- There is no real introduction of VENN predictors which really makes 4.3 difficult if not impossible to follow without reading up on it. Footnote 1 is redundant and not helpful.\n- Footnote 2 is also a bit vague. So leave-one-out-cross-validation is used to obtain a prediction set for each calibration set. But what implication does this have in terms of a coverage guarantee? Especially as it is stated to be explicitly different from cross-conformal or Jacknife+ conformal prediction.\n- The third paragraph in 4.3 is entirely unclear to me – what are these augmented distributions and points?\n- Footnote 4 is also a bit unmeaning.\n- Tables 3, 4 and 5 are very packed and in my opinion poorly introduced/described. Throughout the text it remains unclear what exactly is shown and how I should read these tables in order to draw the same conclusions as the authors.\n\nMethod:\n- The method requires an additional training set for the KNN, this is not really ablated or discussed. Compared to other methods working without the KNN, does that introduce a disadvantage?\n- What is the intuition of the additional mass calibration?\n- Regarding contributions, I am a bit unsure whether the main contribution is the combination of the KNN approach with conformal prediction and VENN predictors or whether there is any methodological contribution in the VENN predictors itself. Could the authors clarify? For me it looks like the main contribution is the combination of these approaches, but this combination is partly difficult to follow due to poor writing.\n- What kind of guarantee do I get from this approach. Due to confusion of the leave-one-out conformal predictor, I am unsure whether a standard marginal or even class-conditional guarantee is obtained in addition to better empirical conditional coverage.\n\nExperiments:\n- In general, I do not understand how experiments are run. Are the reported numbers averaged across different KNN/cal/test splits on these datasets? If so, how many samples have been used and why not plot or report the variation in coverage and size?\n- Why is RAPS applied on the transformer but VENN-ADMIT on the KNN? I am missing a KNN-based RAPS baseline and a discussion why VENN-ADMIT does not work directly on the KNN.\n- In Table 3, I cannot really see where the “empirical behavior of the calibration points differs significantly”. Across most parts, numbers seem to be roughly similar across some labels. What am I supposed to compare?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "M8yA_q43Gr", "reviewer": "Reviewer_sxyD", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new approach for prediction set construction for transformer networks, which is mainly designed to obtain approximate conditional coverage. The proposed approach is evaluated in NLP classification tasks to show its efficacy. ", "summary_of_the_review": "I think that the method section writing needs to be improved, the conditional coverage guarantee of the proposed approach needs to be proved, and the proposed approach requires to outperform the baseline (in terms of conditional coverage) to show its efficacy. Thus, currently, I vote for rejection. ", "strength_and_weaknesses": "**Strengths**:\n* Extensive evaluation on NLP tasks\n\n**Weaknesses**:\n* A proposed approach is unclear (e.g., due to not well-defined terms)\n* A proof on coverage guarantee is missing\n* An interpretation on empirical coverage results is unusual. \n\n\n\n(Weakness 1)\nThe Method section is unclearly written. First, “ADMIT” prediction sets and “Venn-ADMIT Predictor” are not well defined — probably either adding simplified algorithm blocks in the main paper (instead of Appendix) or defining the prediction sets for each type may help. Moreover, the description on Venn Predictor is missing, but pointing to an external reference; I think the paper needs to be self-contained by providing a brief summary. \n\n(Weakness 2)\nI think the main claim of this paper is that the proposed approach achieves a conditional coverage guarantee. However, its proof is missing. Considering that the conformal prediction work mainly focuses on proving correctness guarantees, this work needs rigorous proofs on the conditional guarantee. Otherwise, this work only provides empirical evidence, which is interesting, but not enough.\n\n(Weakness 3)\nTable 4 and 5 show the empirical coverage of baselines and also the proposed approach. Given alpha=0.1, the empirical coverage of conformal prediction is around 0.1 (mainly because the empirical coverage of conformal prediction sets is usually evaluated, assuming that it is conditioned on a calibration for practical reasons); thus, baseline coverage results look okay with me. I cannot see why 0.88 or 0.89 empirical coverage is bad for baselines.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "LS5Xjvwfvr", "reviewer": "Reviewer_dUK3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper aims to construct approximate conditional coverage models using KNN (which approximates a transformer model). By firstly partitioning the data and then applying CP conditioned on the label and the partition they derive an algorithm which allows them to obtain approximate conditional coverage guarantees.", "summary_of_the_review": "I believe the paper has to be rewritten significantly in order to be accepted. As someone who has published in the field of CP before it is even hard for me to understand what is happening in this paper. Hence I recommend the authors to add additional intuition into their paper to make their goal as well as methodology clearer.\n\nIf they authors are able to update the script with clarity I would be willing to raise my score.", "strength_and_weaknesses": "Strengths:\n- The paper looks at a new way to use CP in the transformer setting.\n- But firstly, they can construct a novel method by approximating the transformer using a KNN and then subsequently using this approximation to perform CP.\n\n\nWeakness:\n- Unfortunately, the paper is very poorly written. I barely understand the method even as a person that has published in CP before.\n- For example, I don't understand the data partitioning 4.1.2. there is no intuition on what is happening, and the notation seems non-understandable. q_t is defined as a feature but then it is also a function(q_t(k-1)) ? Could the authors please add a simple example for the reader to understand the intuition behind it?\n- There is no explanation on Venn Arber in the paper. 4.3 is not self contained and it is hard to understand what is happening without having knowledge on this from the get go. A paper should be self contained or at least should intuition on what is happening in the algorithm.\n- Also the notion of memory layer is not well explained in the paper at all hence assuming this knowledge from the reader.\n- Following all of the above I have big difficulties reading this paper and getting any intuition on what the paper is trying to achieve.\n- The experiments are also explained barebones and I don't understand the main message behind it. what does \"Only the VENN-ADMIT sets consistently obtain acceptable singleton set coverage across datasets\".", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject