Selective Classifier Ensemble
Authors: Qiang Ding
Yixuan Cao
Ping Luo
Venue: Submitted to ICLR 2023 (2023)
Keywords: selective prediction
selective classification
ensemble learning

Abstract: Selective classification allows a machine learning model to abstain on some hard inputs and thus improve the safety of its predictions. In this paper, we study the ensemble of selective classifiers, i.e. selective classifier ensemble, which combines several weak selective classifiers to obtain a more powerful model. We prove that under some assumptions, the ensemble has a lower selective risk than the individual model under a range of coverage. This is nontrivial since the selective risk is a non-convex function of the model prediction. The assumptions and the theoretical result are supported by systematic experiments on both computer vision and natural language processing tasks. A surprising empirical result is that a simple selective classifier ensemble, namely, the ensemble model with maximum probability as confidence, is the state-of-the-art selective classifier. For instance, on CIFAR-10, using the same VGG-16 backbone model, this ensemble reduces the AURC (Area Under Risk-Coverage Curve) by about 24%, relative to the previous state-of-the-art method.

Under review as a conference paper at ICLR 2023
SELECTIVE CLASSIFIER ENSEMBLE
Anonymous authors
Paper under double-blind review
ABSTRACT
Selective classification allows machine learning model to abstain from predict- ing some hard inputs and thus improve the safety of its predictions. In this pa- per, we study the ensemble of selective classifiers, i.e. selective classifier ensem- ble, which combines several weak selective classifiers to obtain a more powerful model. We prove that under some assumptions, the ensemble has lower selective risk than the individual model under a range of coverage. The proof is nontriv- ial since the selective risk a non-convex function of the model prediction. The assumptions and the theoretical result are supported by systematic experiments on both computer vision and natural language processing tasks. A surprising em- pirical result is that a simple selective classifier ensemble, namely, the ensemble model with maximum probability as confidence, is the state-of-the-art selective classifier. For instance, this ensemble reduces the AURC (Area Under Risk-Coverage Curve) by about 24%, relative to the previous state-of of-the-art method.
CIFAR-10, using the same VGG-16 backbone model,
INTRODUCTION
Although recent years have witnessed the broad applications of deep learning models, their securities have not been fully guaranteed, which gives rise to the study of selective classification. For any given deep learning classifier, there might be inputs that the model is not able classify in practical applications, for which the model might make unpredictable errors. To prevent this kind of error, we must accurately delimit the deep learning classifier's upplication scope. This need gives rise to the study of selective classification that learns a selective classifier (J.g), where f is conventional classifier, and g a selective function that decides whether the selective classifier should abstain from prediction. Since the classifier is well studied, the study of selective classification focuses on the design of the selective function.
A standard approach to designing the selective function is to design confidence score function with a threshold, and several confidence score functions have been developed. A simple confidence score function is the maximum predictive probability of the classifier (Hendrycks & Gimpel 2017). More advanced methods modify the model architecture (Geifman & El- Yaniv (201)) or the loss function (Liu al. 2019 Huang al. 2020) of the classifier to train the confidence score function and the classifier simultaneously. For example, Deep Gambler (Liu et al.) 2019) regards the selective classification problem as gambling and proposes novel loss function to train the classifier and the confidence score function. Although there are various individual models for the selective classifier, there has been no systematic study of the ensemble method in selective classification.
It is well known that the ensemble method, which combines the individual models to obtain a more powerful model, can improve the predictive performances of machine learning models (see Zhou (2012) for review), but only particular selective classifier ensemble, the ensemble of Softmax Response (Hendrycks & Gimpell 2017). has been empirically studied by [aakshinnaraynnnn et al. (017). Ensembles of other kinds of selective classifiers, and the theoretical foundation of the en- semble in selective classification have not been studied yet. this paper, we first demonstrate the theoretical foundation of the ensemble on selective classifiers, that is, with some assumptions, the ensemble has a lower selective risk than the individual model under a range of coverage. The proof is nontrivial since the selective risk (with the 0/1 loss) non-convex. Second, show the exper- imental results of the ensemble's performance in selective classification. The contributions this paper summarized as follows.

---

Under review as a conference paper at ICLR 2023
We are the first to theoretically demonstrate that based several reasonable assumptions, the ensemble has a lower selective risk than the individual model under a range of cover- age. We verify this by systematic experiments the tasks of image classification and text classificattin..
We show surprising experimental result that two simple methods, the SR ensemble and the Reg-curr ensemble, which can be summarized as the ensemble model with maximum probabiliiyy confidence, are the state-of-the-ar selective classifiers.
PROBLEM FORMULATION OF SELECTIVE CLASSIFICATION
A selective classifier is composed of standard classifier and a selective function. Considering
standard classification problem, X is a feature space, Y {1, 2,.,,... ..., K} finite label set, and classifier f is a function ff X + Y. labeled dataset DD = {z y:) y:) S X x Y sampled standard classifier
from distribution px,y- Our goal is to learn selective classifier where and g X - {0, }] is a selective function that estimates the correctness of f"s prediction. Given input æ, the output of selective classifier (f.g) is
[(x), g() (bsttann, g(z)
(f.9)(x)
Usually, g realized by confidence score A X R with threshold Geifman & ElnYaniv 2017). namely
g(x) [( > J}.
where I is the indicator function.
Coverage and selective risk are two basic evaluation metrics of selective classifiers, and the goal of selective classifiers is to minimize the selective risk for target coverage. The coverage of f.g) is
defined to be the probability of (f.g) 9) not abstaining from prediction (Geifman & El- Elnivy 2017
ie.
o(f.g = Ep(=)1(<)),.
(3)
where p(z) is the probability density function of input x. The selective risk (Geifman & El- Yaniy 2017) of (f.g) is
R(f.g) = E (1Cc)
(4)
Bp(a) (u(x:)
where é Y R+ is given loss function. Usually, é is the 0/1 loss (Geifman & El- Caniv 2017 2019 Liu al. 2019 Huang et al. 2020). Based on these definitions, the objective of selective classifiers is formalized as
min R(f.)) g). s.t. o(f.)) 2 Curgets
where Caarget a given target coverage.
When the selective function g is developed as the confidence threshold controls the trade- off between coverage and selective risk. With different values of т, (f. g) has different pairs of coverage and selective risk (ø(f.g: R(f. T)). which forms the risk-coverage curve (Geifman) & Yaniy 2017) of (J,g). The risk-coverage curve specifies the entire performance profile of that the selective classifier with lower risk-coverage curve is better. To evaluate selective classifiers more concisely, the area under the risk-coverage curve (AURC) is introduced as a metric of selective classifiers (Xin al. 202I), and the selective classifier with a lower AURC is better.
selective classifier, and it is easy
RELATED WORK
Here, we summarize the previous studies on selective classification and ensemble methods. We also discuss the difference between selective classification and out-of-distributtin detection.
2

---

Under review as a conference paper at ICLR 2023
3.1 SELECTIVE CLASSIFICATION
The critical problem of designing a selective classifier is to design its selective function, and there are two types of selective function g. One is the implicit selective function, which is derived from the classifier. The other is the explicil selective function, a neural network trained with the classifier f simultaneously. Previous works for selective classifiers are listed as follows.
Selective classifiers with implicit selective functions include SR (Softmax Response) (Hendrycks & Gimpel 2017), MC-Dropout (Monte Carlo-Dropout) (Gal & Ghahramani 2016), and Reg-curr (Xin et al. 2021p. In SR, the selective classifier is vanilla classifier with its maximum predictive probability as confidence (i.e., the maximum output of the softmax layer). In MC-Dropout, it enables the dropout layer of the classifier and runs multiple feed-forward iterations at inference time to obtain the variance of the maximum probability output of f's softmax layer, whose negative value used as the confidence score. Reg-curr behaves the same the SR at inference time but uses an RPP- based regularizer at training time, where RPP (Reversed Pair Proportion) (Xin et al. 2021 is the proportion of reversed pairs of confidence scores.
Selective classifiers with explicit selective functions include SN (SelectiveNet) (Geifman & El- Yaniv 2019), Gambler (Deep Gambler) (Liu et al. 2019), and SAT (Self-Adaptive Training) (Huang et and have their separate fully-connected layers. The loss function of the model is the selective risk with some regularizers. A hyperparameter e is needed to specify the target coverage. Gambler adds the abstention option to the classifier as an extra class, that is, for a given input z, the predictive prob- ability of the extra class is the confidence of abstention, i.e., 1 - (zz). At training time, it regards the selective classification problem as gambling and trained to maximize the gambling reward. Simi- lar to Gambler, SAT adds the abstention option to the classifier as an extra class. However, SAT has a different training procedure, which is trained with a soft label that tells the model which sample to reject. SAT is the previous ofate-of-the-art selective classifier for image classification tasks.
al. 2000). SN is a neural network that combines f and g. where f and share convolutional layeers
3.2 RANDOMIZATION BASSD ENSEMBLE
In the randomization- ensemble method, each member model is trained independently with the same architecture and training procedure but with different randomization seeds for the random initialization of parameters and the random shuffling of training data for each training epoch. At inference time, the predictive probability of the ensemble for each class is the average of those of member models. Lakshminarayanaa et al. (2017) applies this ensemble method to deep neural net- works (Deep Ensemble) and has achieved state-of-the oftthe-rtttttttto performance in uncertainty estimation. The difference between Lakshminarayanal et al. (017)) and our work is that they only empiri- cally study the ensemble of vanilla classifiers (the SR ensemble), but we not only empirically study ensembles of multiple outstanding selective classifiers but also provide the theoretical foundation of the ensemble in selective classification. As for the theoretical works, Krogh & Vedelsby (1994) proposes the error-ambiguity decomposition to explain the better performance of the randomization- based ensemble in regression tasks. However, for classification tasks, there is no such simple and elegant analysis, since the evaluation metrics are non non-convex Zhoo 2021). Thus, the corresponding analysis for classification tasks needs additional assumptions, e.g., unbiased, uncorrelated, and iden- tically distributed estimation errors for the posterior probability distribution (Tumer& & Ghosh] [996] Fumera & Roli 2005). Nevertheless, these assumptions are impractical (Fumera & 2005). As far as we know, there is no systematic study of the ensemble in the context of selective classification.
3.3 OUT-OF--ISTRIRUTIOON DETECTION
A related topic of selective classification is out-of distri-ditttittioonn (OOD) detection (Lakshminarayanan let al. (017)) (also called as open set recognition (Scheirer et al. 2012), or novelty detection (Schölkopf et al. (00T)), which detects samples that differ significantly from a given dataset, i.e., OOD samples. The essential difference between selective classification and OOD detection lies in their different goals. The goal of the former is to detect samples where the classifier predicts incorrectly, which depends on both the classifier and samples, while that of the latter is to detect samples that differ significantly from a given dataset, which depends on samples only. In addition, at present, selective classification assumes that test data and training data are sampled from the same distribution (Geifman & Yaniv 2017), instead of using OOD test data as OOI) detection. Thus,
3

---

Under review as a conference paper at ICLR 2023
selective classification and OOD detection are complementary in preventing enror predictions of machine learning models, as Figure 3 shows.
METHOD
With the randomization- based ensemble method, propose the selective classifier ensemble. The basic idea is that each predictive probability (as well as the confidence score in the case of explicit selective functions) of the ensemble should be the average of those of the member models. Formally, we assume that for an input sample z, a classifier f at first provides the predictive probability distribution मश (#). ... # and then makes prediction fa; 0) = arg m # (x)) where K the number of classes, denotes the parameters of f. and # (x)) is the predictive probability for class k (the superscript is not an exponent). Then, the predictive probability distribution of the ensemble classifier of M member models is
M Σ (m).). m=1
Tens = M
(5)
The ensemble of the selective function is defined as follows. For implicit selective functions (e.g- SR), to keep the ensemble the same kind of selective classifier as the individual model (for example, the ensemble of SR should still be an SR model), the confidence score of the ensemble is derived from tens in the same way as the individual model. For example, the confidence score of the SR ensemble is
Rens (x) max # (z).
(6)
For explicit selective functions (e.g. SAT), the confidence score of the ensemble is the average of those of member models,
Reass (x)
1
Σ Rm (I).
M
THEORETICAL ANALYSIS OF SELECTIVE CLASSIFIER ENSEMBLE
In this section, we analyze the selective risk (with the 0/1 loss) of the ensemble of simple selective classifier, the SR ensemble (see Section for its definition). If the selective risk is a convex function of the predictive probability distribution, then according the definition of the convex function, (6) implies that the selective risk of the ensemble is less than or equal to that of the individual model. However, the selective risk is non-convex because the 0/1 loss a step function. Thus, the analysis
is not easy. We need some assumptions to prove a lower selective risk of the ensemble. We introduce
the assumptions in Section (verified in Section (. and the theoretical results in Section 5.2 The analysis for the other selective classifiers is left for future study.
5.1 ASSUMPTIONS
Given an SR ensemble with M (M > 1) members, we assume that there are samples on which all member models provide almost the same predictive probability distributions. Furthermore, we idcalize them as definite samples, for which all member models provide precisely the same predictive probability distribution. Then, the rest samples are referred the event that the input sample is definite and A be the event that the input sample is ambiguous. Considering that the input sample is randomly drawn from dataset, the predictive probability for class A (1 < k < K) and the confidence of the SR model are random variables. We denote these random variables as II and C respectively and use z² and к. to denote their values respectively. Generally, for any continuous random variable Z, Pz denotes the probability density function (PDF) of Z. and for any real variable 2, z + 1 denotes that & approaches from the left. Based on the idealization and notations above, we introduce the following assumptions.
ambiguous samples. Let D be
Assumption 1. For any individual SR model, with its confidence score denoted C, have
lim Pr(EEr|A, T) lim Pr(Err) D,EERr/DCC. r),
(8)
T-1
T-1
where Frr is the event that the model makes error prediction.
4

---

Under review as a conference paper at ICLR 2023
In Assumption | Pr(Err|AA, 7) is the selective risk of the individual model with confidence threshold of r for ambiguous samples, and Pr(Err]D, C 2 7) is that for definite samples. The motivation for Assumption is that ambiguous samples seem more difficult to classify than definite samples.
Assumption 2. For any individual SR model, both lim Pc(x: and lim Pc(K]A) exist and are non-zero, i.e., positive, where C is the confidence score of the SR model.
Assumption 2 claims that for both ambiguous samples and definite samples, when the confidence score of the individual model approaches 1, its PDF approaches a non-zero value. In other words, the individual model is not modest over both ambiguous samples and definite samples.
Assumption 3. For any SR ensemble of M member models, let II be the predictive probability of the i-th member model for class k. Then Ak E fl..... K}. Pm mI...... Mr (-[4), the joint probability density function of 11f 11,,..... 11 given the input sample being ambiguous, is bounded.
Assumption 3 is related the definition of ambiguous samples and can be understood via the fol- lowing example. Consider an ensemble with two members 0 and 0g. Let their predictive probability for class k be 11 and I1 k 21, 2, ..., K}. respectively. On definite samples, both 01 and 02 pro- vide the same predictive probability distribution (II = Ii Ak E 21,2... .... H)). Thus, for all k Put.ng (+) the joint distribution of IIş and I1 given the input samples being definite, collapses to AJJA E [0, 1]]. In other words.
{ +000 00 otherwise
if (u, E ((A, A)JA E [0, 1])
Pnt my (u,
On the contrary, ambiguous samples do not have such a property. We intensify this by Assumption to provide good analytical property of ambiguous samples. Furthermore, Assumption 3 reflects the diversity of the ensemble over ambiguous samples. Still consider the example above. If the predictions of 0, and 0₂ are sure to coincide, i.e., the ensemble model has no diversity, then the PDF of Th and IT is unbounded. Conversely, if the PDF of ITţ and ITA is bounded, then the predictions of the member models are diverse. Thus, Assumption [3 provides the diversity of the ensemble over ambiguous samples. It is well known that the randomization-bass 2012). Since the ensemble does not have diversity over definite samples, must have diversity over ambiguous samples. Thus, we do not provide experimental verification for Assumption
ensemble has diversity (Zhou)
5.2 ANALYSIS RESULTS
With the assumptions above, we derive Theorem (see Appendix B for proof details), which shows that the selective risk of the ensemble is lower than that of the individual model under a range of coverage. The intuition of its proof as follows. According to Assumption I] the individual model is not modest over ambiguous samples. On the contrary, based on Assumption 3 we prove that the ensemble modest over ambiguous samples (Proposition []. In addition, both the individual model and the ensemble are not modest over definite samples (due to Assumption 2 and the definition of definite samples). Thus, considering that the classifier's 's error rate over ambiguous samples is higher than that over definite samples when confidence approaches I (Assumption I.. the individual model suffers more wrong but confident predictions that come with ambiguous samples than the ensemble. Therefore, the selective risk of the individual model is higher than that of the ensemble (Theorem 2). In a word, the intuition is that because the ensemble avoids to be overconfident over ambiguous samples, the ensemble has lower selective risk.
Before Theorem 2, we discuss Proposition which provides critical insight into the better perfor- mance of the ensemble.
Proposition 1. If d'Assmpptio] 3 holds, then lim limmema+1 -11 PC (Niens (A) 0, where Cens is the confi- dence score of the ensemble.
Proposition I suggests that given the input sample being ambiguous, when the confidence of the ensemble approaches one, its PDF approaches zero. In other words, the ensemble is modest over ambiguous samples. Based on this proposition, we prove that the SR ensemble has a lower selective risk than an SR individual model under range of coverage.
5

---

Under review as a conference paper at ICLR 2023
Theorem 2. If Assumption 1 holds, then for any individual SR model and any SR ensemble, Bou E (0,1) such that Vo E (0,
Rens (0) < Rina
where (Ø) and ( are the selective risks of the SR ensemble and the individual SR model under coverage o, respectively
6 EXPERIMENTS
Datasets. We conduct experiments on multiple datasets for image classification and text classifi- cation tasks. Following Geifman & El- Yaniv (2017) 2019); Liu al. (2019); Huang et al.) (2020), we use CIFAR-10, CIFAR-100 (Krizhevsky) 2009). and SVHN (Netzer et al. 2011) for image clas- sification tasks, and following Xin al.] (2 use MRPC (Dolan & Brockett 2005). MNLI
(Williams et al., 2018), and QNLI (Wang et al. 2018) for text classification tasks. The usage of the training set and test set in selective classification are the same as the standard classification, because current selective classification focuses on in-domain data (i.e., data from the same distribution as the training set) (Geifmaa EI- Yaniv, 2017). For example, if the selective classifier is trained on the training set of CIFAR-10 10 (Krizhevsky 2009). then it will be tested on the test set of CIFAR-IN 10. Furthermore, MNLI's development set and test set are divided into matched and mismatched parts. The matched parts are sampled from the same source the training set (so they are in-domain data), while the mismatched parts are sampled from different sources. In our experiments, only the matched parts used since the current selective classification only considers in-domain data. In addition, test sets of MRPC, QNLI, and MNLI are not accessible, so we use their development sets test sets. Following Liu al. (20T9); Huang et al. (2020), since CIFAR-10, CIFAR-100 and SVHN originally had no development set, their development sets were 2000 samples randomly split from corresponding test sets. More details of all the datasets in our experiments are described in Appendix C.T
Evaluation Metrics. The evaluation metrics are AURC and selective risk (the lower, the better for both). AURC is comprehensive metric of selective classifiers, and selective risk is a standard metric in previous works (Geifman & El- Yaniv 2019 Liu et al. 2019 Huang et al. 2020). In this paper, given a selective classifier, the result of selective risk is shown in the form of risk-coverage curves, which shows the selective risk of the selective classifier against its coverage. According to the object of selective classification, selective classifier with lower risk-coverage curve is better.
Networks. Following Huang et al. p Xin et al. (202I). for image classification and text clas- sification, we use VGG-16 (Simonyan & Zisserman
2014) and BERT-base (Devlin et al.) 2019) as
the backbones of selective classifiers, respectively. More details of the backbone models and their training procedures are provided in Appendix C.2
Baselines. We use SR (Geifman & El- Yanyyniv (017). SN (SelectiveNet) (Geifman & El- Yaniy 2019),
Gambler (Liu et al.] 2019). SAT (Huang al.) 2020), and Reg-curr (Xin al.) 2021) for both image classification and text classification. Note that the SN is optimized for fixed coverage, so the comprehensive metries AURC and risk-coverage curve, which summarizes performances under different coverages, are not suitable for evaluating the SN. Thus, we only evaluate the selective risk for a fixed coverage of the SN ensemble and provide the results in Appendix [E] To ensure fair comparison, for tasks of image classification, all the baselines are re-implemented based on the open resource code of SAT (Huang al., 2020), and for tasks of text classification, they are re-implemented based on the open resource code of Reg-curr (Xin et al. 202T). The details of the hyperparameters of each baseline are provided in Appendix
6.1 VERIFICATION OF THE ASSUMPTIONS
We examine Assumption I and Assumption 2 (only for the baseline of SR) on datasets for both image classification and text classification. Since the definite samples are the idcalization of samples on which member models provide almost the same predictive probability distributions, with a standard deviation of predictive probability distributions of member models (or STD for short) less than a small positive number as definite samples and the other samples as ambiguous samples
take samples
Beyond Theorem we provide elaborate analysis the lower bound of do in Appendix G

---

Under review as a conference paper at ICLR 2023
in experiments. Formally, STD := V V (+
M Ei #
*.)²
where म is the predictive probability distribution vector of the j-th member model, and samples with STD < e approximates definite samples in experiments. We choose e <= 10 for datasets of image classification and c = 10 10-2 for datasets of text classification. Figure [ and Figure [(e) show the selective error rates (selective risks) of samples with STD < 10-3 and samples with STD 2 10-3 given a range of confidence thresholds (which approximate Pr(Err| [arr) 2 7) and Pr(Err[A, A, 2 T)) on the test set of each dataset. The results show that the selective risk of samples with STD < 10-3 is lower than that of samples with STD > 10- 30 for all confidence thresholds near on all datasets, which verifies Assumption I. Figure l(b) I(d) and Figure ((t) I(h) shows the histogram of confidence scores of samples with STD < e and that of other samples, which approximate Pc(k D) and pe (x(x: on the
test set of each dataset. The results show that the number of samples with STD < 10 is non-zero
in the top bin on all datasets, which verifies Assumption In summary, Assumption and hold
on all datasets.
CIFAR-10
SVHN
CIFAR-100
STD 9.833
33200
513 0.001
S1D x 2.03L
number samples
others
1430
others
3100
1230
2032
4000
8:0
4100
2012-
200
6.902 6.941
3,948
6.990 0.2 6.44 1e 33303
8,442 6,966 3,400 1,000
5.692 3.444 6.44
confidence
confidence
confidence
(a)
(b)
(c)
(d)
MRRC
QNLI
MNLI
STD 0.E30 othere
5 01
0.030
40000
513 - 5.000
23
number of camplees
58-
others
35:30
others
2000
23:00
15
2100
2000
20-
1000
1000
5:0
0.50
0.52
0.94
3.50
0.53
666 confidence
3.64
3.30
6.24
1.6
63e
0.00
100
confidence
confidence
(c)
(f)
g
(h)
Figure I: (a)((): the selective error rates (selective risks) of definite samples and ambiguous samples given a range of confidence thresholds on the test set of each dataset for image/text classification. (b)-(d): the histogram of confidence scores of samples with STD < 10-3 and that of other samples on the test set of each dataset for image classification. (f)-(h): the histogram of confidence scores of samples with STD < 10-2 and that of other samples on the test set of each dataset for text classification.
6.2 EVALUATION OF SELECTIVE CLASSIFIER ENSEMBLES
We first verify Theorem 2 Figure shows the risk-coverage curves of the ensembles and the indi- vidual models of each baseline on each dataset. As we can see, except on MRPC, the risk-coverage curve of the ensemble is always entirely below that of the individual model, i.c., the ensemble has a lower selective risk than the individual model under any coverage, which is consistent with The- orem 2 The abnormal results on MRPC dataset may be because of the small number of samples in MRPC The development set of MRPC has only 0.4k samples, which is much smaller than de- velopment sets other datasets (see Table 2). More importantly, when the coverage is low, say 10%, only about 40 samples in MRPC are selected to predict, which may cause large variance in selective risk estimation. Thus, the estimation of selective risk is not accurate under low coverage, which may explain the violation of Theorem on MRPC. In summary, except the results on MRPC, which might have a large variance in seleetive risk estimation, the experimental results in Figure 2 verify the correctness and practicability of Theorem 2
7

---

Under review as a conference paper at ICLR 2023
SR
GAMBLER
SAT
REG-CURR
CPAR26
CEN010
CFARLS
CIPACO
CRGAL00
CARLSO
5YIN
SVIN
SANN
MEPC
MA-IC
MAFC
NAPI
ONL
anommble
annamble
0.00
0.4
0.6
0.8
1.0
0.0
0.2
0.6
0.8
0.2
0.4
0.6
1,0
0.0
0.2
0.6
0.8
Figure 2: Risk-coverage curves of ensembles and individual models of each baseline on multiple datasets, where ensembles consist of 5 member models.
AURC/10-4 on each dataset, where MNLI-(m) the matched part of the MNLI develop- ment set. The means and standard deviations are calculated over three trials. The best entries are marked in bold.
Table 1:
Dataset
#Member
SR
Gambler
Reg-curr
1
66.1-15.6
70.7=2.6
67.110.3
67.1=2.0
2
55.5=11.7
6..2
63.0::..4
59.2=1.1
CIFAR-IB 10
3
53.0:11.7
6.2
59.1t1.11
16.0::1.6
4
51.3:1.2.2
6-2.20
58.91:2.0
58.3100.5
$4.6.11.0
51.2++2.00 5
a=2.201
57.4=1100
57.6:00.6
53.5=005
1
793.1-9.0
o=4.60
93,
807.316.0
851.9112.8
2
722.6=3.5
em466
880.7=7.00
756.711.6
767.6-1.11
CIFAR-100
3
695.9
em460
871.3:144.3
741.2:13.8
5.9
4
681.8
859.0114.6
729.2:16.9
721.817.9
672,5=1.9 5
857.1+44.7
715.5+12.2
714.2+6.3
46.7+0.2
2=6.0
44.2:12.5
35.011..5
43.8-110
2
42.1118
==266
41.3:12.9
33.5:0.88
39.9=144
SVHN
39.4:10.8 3
==060
38.2:10.8
32.91111
38.2-10.3
4
38. 38.9
e-2.60 37.2:11.0
32.7.0,99
37.0
37.1++0.3 5
e-2.00 37.0=2088
32,4+0.9
36.6#11.2
1
654.3.168.3
695.6_16.9
794.6151.9
696.8-66.0
560.1-157.0 2
a=1.80
721.4=38.2
643.4114.22
631.4156.0
MRPC
566.0:1.7..3
707.3
581.2+11.0
653.7:167.3
560.2.1.6.2
0=1.80
400.3:1:0.0
571.515.3
645.8
561.3+555.6 5
0=1.80
650.1=224.8
563.0+16.55
64..3=14.11
1
221.5 +1.11
o=1.60235.8 =35.1
246.6 14.2
201.0 +1.3
2
196.4 +7.0
a=1.60195.5 =128
220.0
186.9 11.5
QNLI
3
180.1 +:4.4
1-.60188.4 1990
201.5 #4.6
176.6 +33.3
4
175.7 13.5
o-1.60 181.0 1.6.2
196.0 155.5
174.3 13355
5
173.3 11.8
o...80177.7 15.3
192.9 11.8
171.9 12444
1
515.3 18.6
o=2.60
1193
519.8 4800
496.8 19,5
2
482.3 19.3
a=2.00900.6
199.4
482.8 116.5
466.9
17.7
MNLI-(m)
3
475.0
+8.4
a=2.0063..0 =114
470.1 46.5
458.5 15.3
4
467.1 12.8
o-2.80567.1
14.9
460.1 16.4
453.0 11.0
5
465.2
13.8
o-2.80569.4 1114
454.4 13.1
451.9 12.1
Next, we show the AURCs of the ensembles in Table [ where o is the hyperparameter of Deep Gambler, and each ensemble has 2-5 member models. As can see, the ensemble with five mem- bers has a significantly lower AURC than the individual model on each dataset. On CIFAR-10, 10FAR-100, SVHN, MRPC, QNLI, and MNLI, the AURCs of the best ensemble models with five members are 23% 15%. 7%, 14%, 14%, and 9% lower than those of the best individual models. Among all ensembles, SR ensemble has the lowest AURCs CIFAR-10. CIFAR- 100, and MRPC,
8

---

Under review as a conference paper at ICLR 2023
SAT ensemble has the lowest AURCs SVHN and Reg-curr has the lowest AURCs on QNLI and MNL
Surprisingly, the SR ensemble and Reg-curr ensemble are sate-of-theear selective classifiers for image and text classification tasks, respectively. They only use the maximum probability as the confidence score, while SAT and SN use more sophisticated and explicit confidence score functions. Note that, on SVHN, the SAT ensemble performs better than the SR ensemble. We find that the annotations on SVHN are noisy, and after manually removing some noisy samples in the training set, the SR ensemble performs better than SAT ensemble. Therefore, the SVHN result indicates that SAT is better at handling label noise rather than selecting when abstain. Please refer Appendix F3 for more details.
In addition, we conduct experiments to explore further properties of the selective classifier ensem- ble, including the effect of the number of members and the relationship between the classification performance and the selective classification performance (see Appendix (F)) The results are that an ensemble with more member models has better selective performance, and good classification per- formance of the ensemble does not necessarily imply good selective classification performance.
DISCUSSION
A possible direction for future work is adapt analysis to standard classification. The previous analyses the randomization based ensemble for standard classification need some impractical as- sumptions (Tumer& & Ghosh] 1996 Fumera & Roli 2005).. On the contrary, this paper's assumptions are a good approximation of practical settings (see Section 6.1). and more importantly, the standard classification is particular case of selective classification, i.e., selective classification with coverage of 1. Therefore, our analysis (although it does not cover the case of coverage of 1, i.e., the case of standard classification) may motivate the analysis of the randomization-base ensemble for standard classification in practical settings.
Another possible direction for future work is the relaxation of assumptions. This paper's assumption is little strong for the convenience of proof. Although the experimental results suggest that these assumptions are the actual behaviors while the conclusion keeps the same. It is interesting to relax the assumption of the idealization of the definite samples. Although the idcalization may be a good approximation of practical setting, it is unrealistic anyway. We believe that a similar theoretical result holds in the absence of the idealization.
the SR model, we guess the assumptions can be relaxed
CONCLUSION
We prove that under some assumptions, the ensemble has lower selective risk than the individual model under range of coverage. Although the metrics of selective classification are non-convex, complete the proof with the help of several assumptions motivated by empirical observations. The assumptions and the result are well supported by the experimental results on multiple datasets of image classification tasks and text classification tasks. A surprising empirical result is that two simple methods, SR ensemble and its variant Reg Reg-curr ensemble, (which can be summarized as the ensemble models with maximum probability as confidence) are state-of-the-ar art selective classifiers.
REFERENCES
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of
"The result that only on SVHN is SAT the state-of-the-art contradicts that of Huang et al. 2020 This contradiction may be because Huang et al (2020) directly cites the evaluation results of other methods from different papers, which may have subtle differences in the training settings of the backbone model (e.g., data augmentation). By contrast, re-implement all selective classification methods based the open resource code of SAT (Huang al. 2020) for image classification in our experiments, the faimess of comparison guaranteed.
Foor more details on the comparison of ensembles, see Table and 4 which provide the selective risks of ensembles under coverage 10%-100%

---

Under review as a conference paper at ICLR 2023
the North American Chapter the Association for Computational Linguistics: Human Language Technologies. Volume (Long and Short Papers), pp. 4171-4186, 2019.
Bill Dolan and Chris Brockett. Automatically constructing corpus of sentential paraphrases. In Third International Workshop on Puraphrasing, 2005.
Giorgio Fumera and Fabio Roli. A theoretical and experimental analysis of linear combiners for multiple classifier systems. IEEE transactions on pattern analysis and machine intelligence, 27 (6):942-956, 2005.
Yarin Gal and Zoubin Ghahramani. Dropout as bayesian approximation: Representing model uncertainty in deep learning. In International Conference on Machine Learning, pp. 1050~1059, 2016.
Yonatan Geifman and Ran EI- Yaniv. Selective classification for deep neural networks. Advances in Neural Information Processing Systems, 2017.
Yonatan Geifman and Ran El- Yaniv. Selectivenet: A deep neural network with an integrated reject option. In International Conference Machine Learning. pp. 2151 2151-2159, 2019.
Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and out-of- out-of-distributis d--striibution examples in neural networks. International Conference on Learning Representation, 2017.
Lang Huang, Chao Zhang, and Hongyang Zhang. Self-adaptive training: beyond empirical risk
minimization. Advances in Neural Information Processing Systems, 2020.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pp. 448-4444444 456, 2015.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Anders Krogh and Jesper Vedelsby. Neural network ensembles, cross validation, and active learning. Advances in Neural Information Processing Systems, 1994.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predic- tive uncertainty estimation using deep ensembles. Advances Neural Information Processing Systems, 2017.
Ziyin Liu, Zhikang Wang, Paul Pu Liang, Russ R Salakhutdinov, Louis-Philippe Morency, and Masahito Ueda. Deep gamblers: Learning to abstain with portfolio theory. Advances in Neural Information Processing Systems, 2019.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint 2017.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Walter Scheirer, Anderson de Rezende Rocha, Archana Sapkota, and Terrance E Boult. Toward open set recognition. IEEE transactions pattern analysis and machine intelligence, 35(7): 1757-1772, 2012.
Bernhard Schölkopf, John C Platt, John Shawe-Taylor, Alex J Smola, and Robert C Williamson. Estimating the support of high nigh-ddmenssionll distribution. Neural computation, 13(7):14431177, 2001.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint
2014.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The Journal of Machine Learning Research, 15()):199--1958 2014.
10

---

Under review as a conference paper at ICLR 2023
Kagan Tumer and Joydeep Ghosh. Analysis of decision boundaries in linearly combined neural classifiers. Pattern recognition, 29(2)334-334,, 1996.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill. Omer Levy, and Samuel Bowman. Glue: A multi-tase benchmark and analysis platform for natural language understanding. Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 353-355, 2018.
Adina Williams, Nikita Nangia, and Samuel Bowman. A broad-coverage challenge corpus for sen- tence understanding through inference. In Proceedings of the 2018 Conference of the North Amer- ican Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long Papers), pp. 12-21122, 2018.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. Transformers: State-of-the-ar natural language processing. In Proceedings of the 2020 conference on empirical methods in natural language processing: system demonstrations, pp. 38-45 45, 2020.
Xin, Raphael Tang, Yaoliang Yu, and Jimmy Lin. The art of abstention: Selective prediction and error regularization for natural language processing. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguisties and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 1040-1051, 2021.
Zhi-Hus Zhou. Ensemble methods: foundations and algorithms. CRC press, 2012.
Zhi- Zhou. Machine learning. Springer Nature, 2021.
A RELATIONSHIP BETWEEN SELECTIVE CLASSIFICATION AND OOD DETECTION
Figure shows the relationship between selective classification and OOD detection (or open set recognition, novelty detection).
At present, selective classification detects P
U: input space
P: in-domain data
in-demain that f classifies correctly
OOD detection (or novelty detection, open recognition) detects V/ P.
Figure 3: Relationship between selective classification and OOD detection (or open set recognition, novelty detection).
B PROOFS
The complete proof is somewhat complex, but its intuition is straightforward. In word, the intuition that because the ensemble avoids being overconfident over ambiguous samples, the ensemble has a lower selective risk. Details of the intuition are as follows:
1. the individual model is not "modest" over both ambiguous samples and definite samples (Assumption 2
11

---

Under review as a conference paper at ICLR 2023
2. by contrast, based Assumption 3
prove that the ensemble provides modest confi- dence to ambiguous samples (Proposition Dp. addition, the confidence of definite sam- ples remains the same throughout ensembling (due the definition of definite samples);
3. thus, when confidence approaches 1, as long as the classifier's error rate over definite sam- ples is lower than the enror rate over ambiguous samples (Assumption 1), the individual model suffers more error predictions that come with the ambiguous samples than the en- semble. Based on this, we prove that the selective risk drops under range of coverage via ensembling (Theorem 2)
We prove Proposition Section 1 and prove Theorem in Section B.2 complete proof of the final result, i... Theorem 2
The road map of
is shown Figure 4
Assumption
Assumption 2
Assumption
Lemma
Lemma 6
Lemma
Lemma
Lemma
Proposition 1
Theorem 2
Figure 4: The road map of the proof of Theorem
B. PROOF OF PROPOSITION
To prove Proposition I that is, the ensemble is modest over ambiguous samples, first show that over ambiguous samples, the ensemble provides a moderate predictive probability for each class. By moderate predictive probability. we mean a predictive probability whose PDF approaches zero when itself approaches one zero Formally, we have the following lemma (proof is provided in Section (..tionB.1.II..
Lemma 3. If Assumption holds, then
PIIA (0/A) 0, PIT (1/A) O,
(10)
(11)
and
Prts ( (A) ( MM-1) (m + ++), M (Tee - 1m
(12)
Pris (Tin IA) = 0(11 T
(13)
where the notation follows that of Assumption 3 and II is the predictive probability of the ensem- ble for class k.
Secondly, prove the ensemble is modest over ambiguous samples, we show the relationship be- tween the PDF of confidence and the PDFs of predictive probabilities. Note that the confidence of an SR model is the maximum predictive probability. Thus, the following lemma (proof is provided in Section 1.2) bounds the PDF of confidence by PDFs of predictive probabilities, and then it clear that ensemble modest over ambiguous samples, considering the moderate predictive probabilities of the ensemble over ambiguous samples.
'Thus, Proposition that the ensemble is modest over ambiguous samples, is equivalent to that the ensemble provides moderate confidence over ambiguous samples
12

---

Under review as a conference paper at ICLR 2023
Lemma 4. Let II (1 K) be K continuous random variables, and C == maxy II Then have
K
PC(R)
Prre (R:).
(14)
Finally, since Cens max; II ems
Lemma 3 and Lemma derive that when Kens + 17.
K
PCana (Keus (A) -
Pns (Keus (A) O((1 Kenns) )d 11-
1=1
and thus Proposition hoold.
B.1.1 PROOF OF LEMMA
We first derive the PDF of the average of multiple continuous random variables in terms of the PDFs of these random variables (Lemma []. which helps us to analyze the PDF of the ensemble's predictive probabilities.
Lemma 5. Let X1,X2, X2...., XM M continuous random variables, and their average is Xavg 1 E Xz. Then the PDF of Xavg is
M
M-1
PXave PX (Fawg) =M ( JRM
dridrz ... dxM-- M-1 Px ....... ZM M
I;);
(15)
1=1
where Px is PX, Xat Xat for short.
Proof. The distribution function of Xavg is
Exavy (Favg) = [ Mane
dx1 ... d.----d Pg(x1.......... aM
Mawu MM-11
| JBM-1 dx ... dx /
du P& 02(1111"' ".M.)
Let LM EE1
M-1 Ty. then the integral above is equal to
M-1 du p.(p., RM 1, dæ dr /
Meave
Ri)
BM--
1=1
Maws
du
dæy dras- (x (r. TM-
xx))-
(16)
-M-1
The PDF of Xavg the derivative of Fx which, combined with 16 derives
Pxwe (Favg) =F (Favg)
d(Mxraz)
dFxive
drang
d( d(Msavg)
M-1
M / JR dri ... ...dd---- P2((.)..... FM M
xi).
which is exactly (15
Proof of Lemma 3 Based on Lemma and Assumption 3
we prove Lemma 3 as follows.
Proof. With Lemma applled to ITA: S S M, we have
PITk (A M { daf ... dr - Piuu (TT
2 11 M m
Σ T IA).
(17)
Teus
13

---

Under review as a conference paper at ICLR 2023
where Pria is my for short. requires
The integrand in the right-hand side of (17) being
I के S =1,1= 1.2...... 0
M- Liml T. 2 S M - --
(18)
Firstly, we prove 10 and
When 0 S x I 17. it casy to verify that 18 is equivalent to
S कं 2 MTTus
0 S u2 - MTeus oं
(19)
0 के S M T
xi-1
0 S TM - & M
M o
xk
2-
Thus,
17
transforms into
Ma cas
Malus
Ejsi
M Em 75
Pir (Tens A)) M
d
dmf
d M-11
Prie (T) ....... -M
mens
m A).
Considering that Pne (-14) is bounded, as Assumption Then we have
claims, be one of its upper bounds.
M
Mar
Ma - M-2 xf
PILE... (Tens AA) S M
da
dm
dn
d B
M
Mxt emu
M
< M
dr
dr k
dr k
d-M-11 B
0
M M Tome
M Tone
MB.
dr
d
MB (M
k
M-1
MM B. (m M-1
(20)
which directly derives 100 and 12
(note that the PDF is non-negative).
Secondly, we prove and 13 These two equations could be derived like (10 and 12
However, here we take another way that uses little trick to simplify the proof. Let II; and
eos be the corresponding random variables of aद and m respectively, and U; 1 T
Uens 1 M U,
II Applying 20 U; and Uens, we get that when Wens
PU (Meus (A) M B MM1
(21)
It is easy to see that Puo (Wensl A) PITA (1 Vensl A). Sticking this into (1 have
PII (1 Vens (A) < M B
M-1
uons
when 0 I tlen I M7 With the (1 Uens) in the equation above replaced with m we have
PiLk (A) < M B
* M-1
when 1
M7
nx ens
< 1, which directly derives and (13).
B.1.2
PROOF LEMMA
Proof. First of all, we prove VKL, Nig, Ki < Kiz.
Fo(Ra) Pc(Ki) <
Fun (x2) Fir (K1)
(22)
1=1
14

---

Under review as a conference paper at ICLR 2023
It is easy to see that
(c(K) = .........I (K...., = (-o0,]]
. do p 1I (a .: ,,)),
so the left-hand side of (2 is
dn ... dr Pir DI......I(TTT ( x
(~00,80/
(-00,m) dn ......dee dx pm Prr,..... n
Prr,...i*( (m ,,,
dn ... dr K
Pm Pm...... n (T²
x),
(23)
(-00,xg/ ( (-
where the last equality is due to (-00, mi] C (-00, 82]. and the right- hand side of
22 is
d praa (TT*
[61182)
dn ...... dd Pur Pur.....x (,",
U Rt- ma) d d Pm T (T , x*))
(24)
where the last inequality is because Rk [N1, K2] x K for different < k < K, may have an intersection. To prove (22). we only need to prove that the night-hand side of (23) is less than or equal the right-hand side of (2), which equivalent to prove
K
(-oc, k2) KK
x0,
U
R
1p--1
[151, RK-k
(25)
Now we prove
25 v(
n k
(-o0, K2] (-x0, ki K we have
1k, S K, π S K2:
(26)
3kg 1 < Ko < K, ko K1,
(27)
where (7 is because if all x is less than equal to instead, then (a ...., "......kk)) (.) (-o0, m11* which contradicts with (ir1 .......... x) (=),, (-o0, Thus, 2 E [M], K2), so
(Tt (mr....., 1o-1 x [11,
R Ko ko
U k=1
k- x [2i RK
which is precisely 2.5p. and therefore 22 is proved.
With 22 and the definition of derivatives, it is easy to that FC(()) Ek=1 Fl (1)), which is
equivalent to (x) < E Pn= (x). Thus, Lemma is proved.
B.2 PROOF OF THEOREM
The intuition of the proof is as follows. Intuitively, since the ensemble is more modest than the individual over ambiguous samples and is the same modest as the individual model over definite samples, the ensemble tends to select more definite samples when the confidence threshold ap- proaches 1, compared with the individual model (Lemma 7 Thus, (still intuitively) as long as the selective risk over definite samples lower than that over ambiguous samples when the confidence threshold approaches I (Assumption[]) [T] the ensemble is certainly have lower selective risk when the confidence threshold approaches
Although the intuition is straightforward, the rigorous proof is not easy. For the convenience of the proof, we show Lemma 6 and Lemma 7 first. Lemma 6 claims that for the individual model, the selective risk given definite samples is lower than the overall selective risk. Lemma 7 claims that the ensemble is unlikely to select ambiguous samples to predict when the confidence threshold approaches 1.
15

---

Under review as a conference paper at ICLR 2023
Lemma 6. If Assumption 7 holds, then for any individual SR model,
lim R(o(T)) lim Pr(Err\D, T):
(28)
where the notation follows those of Assumption
Proof. Using Bayes' rule, we have
Pr(C (A)) 2r(A(C Pr(C (A) Pr(C 2 TD))P((
(29)
Using L'Hospital's rule, we have
Pr(C 2 r
I D)(x
lim T-1
lim
Pr(C 2 T(A)
r-ル S (c((AA))
lim D)
-PC(T(A)
--11-
lim D)
--1- Pc(TIA)
>0.
(30)
where the last inequality is due Assumption
Combining this with 29 we have
Pr(A)
lim Pr(A|C 21) Pr(A) + Pr(D)
T-1
lim,
Pr Dj
Pr(C2r(A)
Pr(A)
Pr(A) + Pr(D) lim,-11
(c(1AA
>0.
(31)
Now we derive 28
R(o(T)) Pr((Frr AP
According to the equation above, we have
R(o(T)) -1
lim
=[ lim Tr(Er|AA,C2 lim Pr(Bmr(D,C21) --- lim Pr(A|C + lim ((
7-1
(32)
Due to 31 and Assumption I the first term of the equation above is positive, 28 derived.
Lemma 7. If Assumption hold, then
lim
Pr(A|Cens 2 Teus) = O,
(33)
where the notation follows those of Assumption
Proof:
Similar to
31 with Bayes' rule and I." L'Hospital's rule, we can derive that
Pr(A) lim -1
Pr 27anz (4)
lim Teu +1
Pr(A Tens)
PriComs 2 Tame 12)
Pr(A) lim fim -1-
Pr(Cane 2 (A)
+ Pr(D)
Pr(Cone27end D)
Pr(A) lim lim PComn (Tuns A)
(Tome D)
(34)
Pr(A) lim -1-
DCan TTens D + Pr(D)
pC (Temal A)
16

---

Under review as a conference paper at ICLR 2023
where Cens is the confidence score of the ensemble. Because for definite sample, the confidence score of the ensemble is equal to that of the individual model, we have
lim PC... Cicas(Tennee (Tens)
PC (Tens (A)
lim
0,
Teur PC (Tens]
Team
pC (eesTens Tens
where the last equality is due Proposition and Assumption 2
Substituting this to 34 we obtain
33
Proof of Theorem
Proof. First, for the convenience of the proof, given SR model (f.g), we define threshold-to- coverage function P(S.g) of (S.9) that maps the confidence threshold to the corresponding coverage.
P(s.a) (0, 1) (0,1), ((),+>
Second, we prove that 30 E (0, 1). Venus E (1 (1-66, 5),,
Pr(A[Cens 2 Tens) Pr( Errind C 2 + Pr(Errens D, Cens 2 Tens) < 0,
(35)
max Peus (Tens)
(36)
where is the confidence score of the individual SR model, ErTind the event that the individual model makes error prediction, Errens is the event that the ensemble makes an error prediction, and Pens are the threshold-to-coovragg functions the individual model and the ensemble respec- tively. Note that the symbol p=1 denotes the preimage under p, rather than the inverse function of p.
Because when Tens + 1_ the coverage of the ensemble Pens (Teus) approaches O, and the coverage of the individual model is equal to the coverage of the ensemble, i.c., P(T) Pens CenusTeante (Teus), we have
r + 1 when Tens -> 1- Thus,
lim Pr(Errmal 2 2) lim Pr Pr(Errinale |2 r). Tens
(37)
--11
In addition, for definite samples, the confidence of the ensemble and that of the individual model are the same, and the ensemble and the individual model make error predictions on the same set of samples, i.e. Errind Err So
lim Pr(Errens/ D, Cens 2 Tens)
lim Pr(Errens) D, C 2 Tens)
Teza +1
-1-
lim Pr(Errens| D, C r-1
lim Pr(Errind| D, D,C T), T-1
(38)
where the second equality is just a variable substitution. Finally, we have lim [PrsA|Cous 2 Tems) Pr(Errind C 2 T) + Pr(Errens) D, Cens 2 Tens))
lim [0- Pr(Errina C r) Pr Pr(ErTens D, Cens 2 Tena)l lim Pr(Errind D2C r)
Tmm-+1-
lim Pr(Errinal C +1
Tom
Tens
= lim Pr(Errind C 2 r) + lim Pr( (Errmal D,C T)
--1-
<0,
(39)
where the first equality is due to Lemma the second equality is due (37 and (38. and the last inequality is due to Lemma 6 Thus, with 39). it is easy to see that (35) holds.
Third, we have
Pr(Errent Cenu 2 Tens)
Prr(Erees, A ACeuus 2 Tens) + Pr Errens DICeus 2 Teus)
Pr( Errer A, Cens 2 Tens (A((AACCes 2 Tens)
Pr(Er Prrrree D, Cens 2 Teus Pr Cens 2 Tens)
Pr(Errens! A, Cens 2 Tems Pr
Pr Pr(pP (A|Cens 2 Teus)
Pr(Erreus] D, Ceus 2 Tens) PPr--PrCCCCaa 2 Teus))
Pr(Errees A, Cens 2 Tens) Pr Pr(Erreus D, Ceus 2 Tens
Pr(A[Cens 2 Tene) + Pr(Errens D. Cens 2 Fens)
<Pr(A|Cous Temx) + Pr(Errenn D, Cens 2 Teus);
(40)
17

---

Under review as a conference paper at ICLR 2023
where the last inequality is because any probability is in [0, 1]. Combining this with 35 have 36 E (0, 1), Teus E (1 - 1),
Pr(Erreus Cens 2 Tens) <Pr(A|Ceus 2 Tems) + Pr(ErTens D, Cens 2 Teas)
< <Pr(ErTind) 2 T) Prreerrens D, Cena 2 Tens)
+ Pr( Pr(Ereeul D, Ceus 2 Teus)
Pr(Errind T);
(41)
where the second inequality is due to 335.. Pr((rrena|Caa Cens 2 Tens) is the selective risk of the en-
semble given the confidence threshold of Tens (or given coverage of Pens (Feus)) and Pr Pr(Ermma 2 T) is the selective risk of the individual model given the confidence threshold of r (or given cover- under the same coverage Pens (Tens). Thus, (41) is equivalent to that 36 E (0, 1). VTens E (1 6, 1), the ensemble has a lower selective risk than the individual model given the coverage of Φ Prnns (Tens). This statement be simplified as 36 E (0, 1). Vo E (0, Pens (1 - 8)), the ensemble has a lower selective risk than the individual model, given the coverage Φ.
age of p(T) (ens(Tens)) These two selective risks
C DETAILS OF EXPERIMENTS
C.I DATASETS
The experiments were conducted on multiple data sets of image classification and text classification.
The image classification datasets are CIFAR-10, 10, CIFAR-100. (Krizhevsky) 2009) and SVHN (Net-) zer et al. 1) whose image sizes are all 32 x 32 x 3 pixels. The datasets of text classification are MRPC (Dolan & Brockett 2005), MNLI (Williams et al. 2018) and QNLI (Wang et al.) (2018). The task of MRPC is to judge whether two paragraphs of text are semantically equivalent. MNLI's task to judge the inferential relationship between sentences (three categories). The task QNLI to determine whether paragraph has the answer set, development set, and test set of each data set used in experiments are shown in Table 2 MNLI's development set and test set are divided into matched and mismalched parts. In the table, (m) rep- resents matched, and (mm) represents mismatched. The matched parts are sampled from the same source as the training set, while the mismatched parts are sampled from different sources. Current selective classification only considers test samples from the same distribution as the training set, so only the matched parts are used in experiments. In addition, test sets of MRPC, QNLI, and MNLI are not accessible, so we use their development sets as test sets. According to Liu et al. (2019); Huang et al. (2020), since CIFAR-1O, CIFAR-100 and SVHN originally had no development set, their development sets were 2000 samples randomly divided from corresponding test sets.
given question. The sizes of the training
Table 2: Sizes of training sets, development sets, and test sets for each dataset used in experiments
Datasets
Training Set
Development Set
Test Set
Number of Classes
CIFAR-10
50.0k
10.0k
10
CIFAR-100 100
50.0k
10.0k
100
SVHN
73.3k
26.0k
10
MRPC
3.7k
0.4k
1.7k
QNLI
104.7k
5.5k
5.5k
2
MNLI
392.7k
9.8k (m)/ 9.8k(m))
(ok(m)/9.8k(mm)
C.2 MODEL IMPLEMENTATIONS AND TRAINING PROCEDURES
For image classification, the backbone model is VGG-16 Simonyan & Zisserman, 2014 with Dropout (Srivastava et al.] 2014), batch normalization (loff & Szegedy] 2015). It is trained in the same way Huang et al. (2020). The model is optimized using SGD with initial learning rate 0.1 (the learning rate decays by half in every 25 epuchs), the momentum of 0.9, weight de- cay of 0.0005, batch size of 128, and total training epoch of 300. Data preprocessing includes
18

---

Under review as a conference paper at ICLR 2023
data augmentation (random cropping and flip) and normalization. The implementations of the back- bone model and data preprocessing are based on the official open-sourced implementation of SAT to ensure fair comparison.
For text classification, the backbone model of selective classifiers is BERT-base (Devlin et al. 2019). Pretrained BERT-base is provided by the Huggingface Transformer Library (Wolf al. 2020).
trained/fine- tuned in the same way as Xin et al. (202T), except on dataset MRPC. On QNLI and MNLI, the model is trained/fine-tuned using AdamW W (Loshchilov & Hutter 2017] for epochs, with a learning rate of 2 x 10-5, batch size of 32, and the maximum input sequence length of 128. On MRPC, the model is trained/fine-tung QNLI and MNLI. This unique setting of training epoch is due to the small number of samples in MRPC, which makes the training require more epochs reach convergence on MRPC.
for 10 epoch. with other settings the same as those on
C.3 HYPERPARAMETERS OF SELECTIVE CLASSIFIERS
For the hyperparameter of SN, choose 0.9 for evaluating its selective risk, given the coverage of 90%. The results of SN are reported in Appendix F For the hyperparameter o of Gambler, we tune o on validation sets in the same way as Liu al. (2019). For the hyperparameter of SAT, we set a = 0.99, the same as Huang et al. (2020). For the hyperparameter À of Reg-curr, set 0.05.
D ADDITIONAL EXPERIMENTAL RESULTS
Table shows the selective risks of ensembles under coverage 10% 100% on each dataset, where hyperparameters of Gambler are the same as those in Table Notably, no ensemble consis- tently outperforms others under coverage on all datasets, so it is not easy tell which ensemble is state-of-the-art in this regard. This phenomenon is because different ensembles have similar over- all performance but adopt different trade-offs between coverage and selective risk. In this case, we need a comprehensive metric, e.g., AURC, identify the state-of-the-arr (see Table I.
E EMPIRICAL RESULTS OF SN
With the hyperparameter of 0.9, we report the selective risks given the coverage of 90% of SN ensembles and the individual SN in F) The coverage set to 90% because the target coverage of the SN is (Geifman El-Yaniv 2019)), and is 0.9 in our experiments. The results show that each ensemble of SN has a lower selective risk than the individual SN.
F FURTHER PROPERTIES OF SELECTIVE CLASSIFIER ENSEMBLE
F.1 THE EFFECT OF NUMBER OF MEMBERS ON SELECTIVE CLASSIFIER ENSEMBLE
We evaluate AURCs of the SR ensemble, Gambler ensemble, and SAT ensemble different num- bers of members on CIFAR10, 10, and find that an ensemble with more members has better perfor- mance, but less efficient. The results are shown in Figure 6 In most cases, the AURC on the test set of CIFAR-10 10 decreases the number of members in the ensemble increases. In addition, as the number of members in the ensemble grows, the effect of adding one member drops. On the one hand, the result shows that ensemble with small number of members has good selective clas- sification performance. On the other hand, it indicates that when the number of member models is large, increasing the number of members improve the performance of the selective classification ensemble is inefficient.
F.2 GOOD CLASSIFICATION PERFORMANCE DOES NoT IMPLY GOOD SELECTIVE CLASSIFICATION PERFORMANCE
It is well known that the ensemble has better classification performance than an individual model, but this does not guarantee a better selective classification performance of the ensemble, To demon- strate this, design an SR model with big backbone, and show that it has as good classification
19

---

Under review as a conference paper at ICLR 2023
The selective risks of ensembles under coverage 10%-100% image classification datasets. The means and standard deviations are calculated over three trials. those that overlap with the best entries are marked in bold.
Table 3:
The best entries and
Dataset
coverage (%)
SR ensemble
Gambler ensemble
SAT ensemble
Reg-curr ensemble
100
5.31=00.33
5.29:10.03
5.47:10.04
5.74=0.07
90
1.68:+0.02
1.99=:001
2.15+0.06
1.89=0.02
80
0.45=+0.05
0.51=00.02
0.63+00.03
0.61
70
0.17-10.01
0.21100.01
0,26:10.01
0.18-00.2
60
0.11-:0.01
0.18++0.03
0.17+00.01
0.08
CIFAR-10
50
0.11+0.01
0.14+0.02
0,11+00.01
0.07=0.01
40
0.12++0.33
0.15
0.06+0.01
0.07
30
0.13+0005
0.13
0.06110.02
0.08=0.03
20
0.12+-0.02
0.17+40.05
0.00-10.00
0.02+-0.02
10
0.10++0.08
0.14+00.05
0.00-10000
0.00++0.00
100
2.44+00.01
2.42+00.22
2.36+-0.01
2.41+0.001
90
0.09
0.60
0.50
0.04
80
0.42+10.03
0.38
0.34
0.39
70
0.34+:002
0.32110.1
0.3110001
0.35100001
60
0.32+0002
0.30+0.01
0,28+0001
0.35++0.01
SVHN
50
0,29++0.22
0.26+-0.01
0,26+-0.00
0.30+0001
40
0.25++0.02
0.27++0.2
0.25++0.01
0.28++0.01
30
0.22:10.03
0.26110.01
0,20:10.01
0.25+10.03
20
0.22
0.26110.01
0.1810.02
0.19-10.03
10
0.21100.02
0.23
0.17-10.02
0.18
100
24.66+00.08
25.50=00.05
25.23++0.13
25.70=00.09
90
19.15=00115
09.88
19.77
20.16=0.114
80
14.32-+0.22
15.75+00.09
15.00+0.220
15.22+0.07
70
9.78.10.13
12.11
10.2910.224
10.41
60
5.81
8.
6.43.10.20
6.58.10.27
CIFAR- 100
50
2.95
6.22.10.10
3.41
3.45
40
1.40+00.13
4.37+0.06
1,96+0.13
1.74+0.11
30
0.75++0.05
2.67+:0.01
1.13+0.02
0.89
0.62-10.06
1.9110.04
0.72.10.06
0.62-10.04
10
0.33.10.09
1.42.0.16
0.57
0.13
performance as an SR ensemble with a standard backhone but worse selective classification perfor- mance than SR model with a standard backbone. The big backbone designed to have twice as many filters in every convolutional layer and neurons in every fully connected hidden layer as those of the standard VGG-16, which is therefore called Big VGG-16. It is easy to see that its number of parameters is approximately 2 4 times as many as that of standard VGG-16. We train an ensemble of VGG-16s and an model with a backbone of Big VGG-16 on CIFAR- and show the evaluation results in Figure 7 and Table Figure 7 shows that when coverage is high, the ensemble and the big individual model have similar selective risks, and especially, the classification rates (i.c., selective risk of 100% coverage) of the ensemble and the big individual model are similar. However, when coverage low, the big individual model has significantly higher selective risk than the ensemble. Table shows that the AURC of Big VGG-16 is much higher than the ensemble of 4 VGG-166 166 and even higher than SR. summary, we show that a selective classifier with a good classification performance is guaranteed have good selective classification per- formance, so the good selective classification performance of the ensemble is not trivial result of its good classification performance.
F.3 THE EFFECTS OF LABEL NOISE OF SVHN ON SELECTIVE CLASSIFIER ENSEMBLES
In this section, compare the effect of label noise of SVHN the SR ensemble with that SAT ensemble, whose result might explain the abnormal experimental results (compared to results other datasets) SVHN in Section 6.2
SVHN is not clean dataset, and much more label
20

---

Under review as a conference paper at ICLR 2023
Table The selective risks of ensembles under coverage 10%-100% text classification datasets. The means and standard deviations are calculated over three trials. The best entries and those that overlap with the best entries marked in bold.
Dataset
coverage (%)
SR ensemble
Gambler ensemble
SAT ensemble
Reg-curr ensemble
100
14.13::.23
14.62:t0.23
13.64:10.33
15.2840.31
90
11.41=11002
11.50=:0.46
10.69:10.13
11.68:+0.44
80
7.75++0.29
9.99
8.46:10.63
8.36+
70
6.41-10.33
8.31
7.93:1044
6.64=10229
60
5.71
7.35=+1.20
6.39::0.19
6.12=00.3
MRPC
4.08++1.29
4.41+-0.0
3.59+1.001
4.74+00.3
40
0.25
3.76
3.25+00.6
3.66+0..5
30
3.25
3.32
3.52:10.88
2.98=0.77
20
2.44
3.25110.88
3.25
3.6621..00
10
3.25
4.88+10.00
1.6311.11
5.69
100
8.164:0.0
8.18:1020
8.03:10.09
8.17=0.01
90
0.04
5.04--0.14
5.03++0.09
4.74+00.1
80
2.94
3.08+10.08
2.07
2
70
1.84
1.91:10.04
1.92:1.111
1.86
60
1.20
1.27=10.05
1.36::0.01
1.30=0.08
QNLI
1.04:0.055
1.04:10.08
1.13:00.03
0.08
40
0.72+0.02
0.73
1.02:1..11
0.70
30
0.45
0.51
0.83
0.49
20
0.30-10.11
0.37
0.67
0.30=10.09
10
0.30
0.12:10.09
0.61
0.12:10.09
100
15.04:10.06
14.82:10.15
05.03
14.89:10.14
90
11.01=10.11
11.78:10.09
11.37
11.21:10.17
80
7.93
9.62-10.08
8.26++0.20
8.02=10007
70
5.81+
8.03+-0.23
5.81
5.85
60
0.28
6.41
0.09
4.05
MNLI
50
3.22
4.9511..10
2.99
3.04
40
2.69
3.57+0.21
2.08
2.22
30
0.13
2.35++0.18
1.57++0.03
1.75+0.06
20
1.34+0.10
1.53++0.17
1.39+0.13
1.36+00.66
10
0.98
1.32-10.14
0.71
0.71
Table 5: The AURCs(/10~1) of Big VGG-16, vanilla VGG-16, and the ensemble of 4 VGG-16s on CIFAR-10. The best entries are marked bold.
Dataset
Big VGG-16
VGG-16
Ensemble
CIFAR-10
89.2
69.6
49.3
noise can be detected in SVHN than in CIFAR-10 and CIFAR-100. Using the soft label of SAT (Huang et al. 2020), we detect label noise in SVHN, CIFAR-10, and CIFAR-I00, and find that SVHN has significantly more label noise than CIFAR-10 and CIFAR-100. The result is presented in the following. In addition, is known that SAT is robust to label noise (Huang et al.) (020),, while not so, so we conjecture that the label noise of SVHN is why SR ensemble inferior to SAT on SVHN.
We detect label noise with the help of the soft label of SAT. For a sample x; the soft label SAT (Huang al. 2020), fi is used to measure z; 's learning difficulty. The soft label of SAT is initialized as and updated at every training epoch as below
tig t ti (1 a) po(()
21

---

Under review as a conference paper at ICLR 2023
err(%) given coverage of 90%
25
20
15
CIFAR-10
10
SVHN
CIFAR-10
QNLI
MNLI
1
2
3
4
5
Number of Members
Figure 5: Selective risks of SN ensembles (with 2 to 5 members) and the individual SN (with only member) given the coverage of 90%
AURC on CIFAR-10
SR
70
Gambler
SAT
AURC / 1e-4
65
60
55
50
10
15
20
Number of Members
Figure 6: The AURCs on the test set of CIFAR-10 of the SR ensemble, Gambler ensemble, and SAT ensemble of different numbers of members
where (Y(r)) is the predictive probability distribution of the classifier, yi is the label of 24 a is hyperparameter. The smaller the fr.y. is, the lower the true class predictive probability of the classi- fier on z; during training time, indicating that æ; is more difficult to learn. By selecting a percentage of samples with the lowest Li.y,, we get the most difficult samples to learn for the classifier, from which we can easily detect label noise manually.
In training sets of SVHN, CIFAR-10, 10, and CIFAR-100, detect label noise manually among the top-0.1% difficult (measured by the soft label SAT) samples. The numbers of mislabeled sam- ples detected in SVHN, CIFAR-10, and CIFAR100 SVHN has significantly more mislabeled samples detected than CIFAR- 10 and CIFAR-100, indicat- ing much more label noise in SVHN than in CIFAR-10 and CIFAR-100.
shown in Table 6 The result shows that
To verify the effect of label noise, the following experiments are designed. Firstly, we detect label noise manually among the 1 1% of the hardest-to-lear samples of SVHN training set and test set,
22

---

Under review as a conference paper at ICLR 2023
0.06
4 VGG-16 Ensemble
0.05
Big VGG-16
selective risk
0.04
0.03
0.02
0.01
0.00
0.0
0.2
0.4
0.6
0.8
1.0
coverage
Figure 7: Risk-coverage curves of the ensemble of 4 VGG-16s and the Big VGG-16 on CIFAR-10
Table 6: Numbers of mislabeled samples in the top-0.1% difficult training samples of SVHN, CIFAR-10, and CIFAR-100.
Dataset
#Mislabeled
#Top-0.1%
Proportion
SVHN
73
73
100%
CIFAR-10
1
50
2%
CIFAR-100
1
50
2%
using the soft label of SAT. Secondly, remove the detected mislabeled samples from the original dataset. The remaining SVHN dataset is called the clean SVHN. Accordingly, the original dataset called the original SVHN. Finally, we retrain and test the SR ensemble and SAT ensemble and compare their test results. In the second step, the reason for removing mislabeled samples rather than modifying them that some samples cannot be classified even by humans, and some samples are not in the range of categories of SVHN. Thus, the label noise cannot be eliminated by modifying the labels but by removing mislabeled samples.
The test results of the SR ensemble and SAT ensemble on clean SVHN are shown in Table 7 It not surprising that the AURCs of the SR ensemble and SAT ensemble are significantly lower on the clean SVHN than the original SVHN. Furthermore, on the clean SVHN, when the number of members is 5, the AURC of the SR ensemble is lower than that of SAT ensemble. Combined with results the original SVHN, where the AURC of the SR ensemble is higher than that of SAT ensemble, we conclude that label noise in SVHN is why the SR ensemble has a higher AURC than SAT ensemble. In other words, label noise is why the SR ensemble performs worse in selective classification than SAT ensemble on SVHN.
Table 7: AURC/10-4 of SR ensemble and SAT ensemble on the clean SVHN
Dataset
#Member
SR
SAT
12.3
7.8
2
8.2
7.1
clean SVHN
3
7.3
6.8
4
6.8
6.8
5
6.4
6.8
23

---

Under review as a conference paper at ICLR 2023
In summary, by experiments, show that the SR ensemble is not robust to label noise SAT ensemble, and label noise in SVHN is why the SR ensemble is not as good as SAT ensemble on SVHN. We construct the clean SVHN, which is SVHN without some mislabeled samples. On the clean SVHN, we compare the SR ensemble with SAT' ensemble and find that the SR ensemble is superior SAT ensemble in selective classification performance. Combined with former experi- mental results, we conclude that label noise in SVHN is why the SR ensemble is inferior to SAT on SVHN.
Considering the experimental results on the clean SVHN and previous experimental results on CIFAR- 10 and CIFAR-100 (see Table and Table the SR ensemble is superior to SAT ensemble in selective classification on clean image classification datasets, Thus, SR ensemble is the state-of- the-art selective classification method on clean image classification datasets, but not as robust to label noise as SAT ensemble.
G AN EXTENSION OF THEOREM 2
This section discusses the lower bound of Φo mentioned in Theorem We aim to calculate do's 's's lower bound without training an ensemble (otherwise, we can measure it directly on the ensemble). Preliminaries. The do can be obtained by solving the following optimization problem.
max Φ
s.t. (Ø) < R(Ø).
where (Ø) and R(ő) are the selective risks of the ensemble and the individual model under coverage o, respectively. Suppose we know all about the individual model, e.g., the mapping from á to R is known. Since maximizing coverage is equivalent to minimizing the confidence threshold for a fixed model, the original optimization problem can be substituted by
min T T T,Teno
(42)
S.I. Pens (Tens) = (b(T)
Rens (Wens
(Tens)) (Ten))))s)) < R(ő(T)),
where Pens (Teus) coverage of the ensemble with confidence threshold Tens, and ((T) is coverage of the individual model given the confidence threshold т, and then do o(7"), where r" is the optimal solution to 422. Assume that R is a monotone increasing function and that ó a monotone
decreasing function then it is easy to show, using proof by contradiction, that (42 can be further transformed into
min T T, Tene
(43)
s.t. Qens (Tens) 2 Ø(T) Reus (Pens (Teus)) < R(o(T)).
we need more information about the ensemble. Besides the number of classes K, assume that know: oracle that tells whether sample definite; M, the number of member models; and B, the upper bound of ITT; (-IA) for all l: E (1,2..., 22....K). K). It is natural to know K and M, and we need the oracle and B because they provide critical information about the ensemble's behavior. The oracle can be implemented by an ensemble with M' (M' < M) members.
To solve 443
Eliminating the Unknowns. We are now committed to translating the unknowns in the 443 into known quantities. Firstly, we eliminate the unknowns in the first constraint. According 20 and
Lemma 4 it is easy to prove (by an integral)
Pr(Cens 2 Tens A) < B(1 Tens) M
(44)
where C and Cens the confidence scores of the individual model and the ensemble, respectively, A/D represents the event that the input sample is ambiguous/definite, 3 = K M-1 B. Combining
'The latter actually obvious fact.
24

---

Under review as a conference paper at ICLR 2023
44
with Pens
Pr(C 2 Tens:
A)+ Tensy D) Pr(C Tens (Ans(A))P(() - 2 Teus: D),
we have
Pr(C 2 Tens: D) S Pens (Tens) S 8(1 Tans) T PP Thus, we can intensify the first constraint as
Pr(C
Tens: D).
(45)
((T) S Pr(C Teus: D).
(46)
Secondly, we eliminate the unknowns in the second constraint. according (41. (35 a sufficient
condition of Rens < R. We rewrite 35 as
Pr(A]Cens
2 Tens) + Pr(Err|D, Tens) R(o(T)),
(47)
where Cons is the confidence score of the ensemble, and Err represents the event that the individual model makes an error prediction. Note that the first term in the second constraint of (47) contains
Cens. which is unknown, so we cannot directly replace eliminate Cens as follows: Pr(A|Cens Teus)
443)'s
second constraint with (47) We
Pr(A, Cens 2 Teas)
Pr(Cens Tens)
Pr(A, Cens 2 Tens)
Pena (Tons)
Pr(A) Pr(Cens 2 Tens A)
Dens (Tens)
Pr(A) 331 Teus) M
Pons (Tens)
Pr(A) :311 Tens)" M
((T)
where the first inequality is due to 44), and the second inequality is due to (45) and (46). Thus, sufficient condition (47 is
Pr Pr(A) 3(1 - T + Pr(Err|D, D Tens) < R(o(T)),
(48)
((T)
with which we replace the second constraint of 433 In summary, we can intensify the constraints of (43) and obtain the following optimization problem that does contain the unknowns. is easy to see that the optimal solution to (49 is an upper bound of that to (4).
min
(49)
Tenens
((T) S Pr(C 2 Tens: D)
Pr(A) 11(1 Tens) + Pr(Err|DD,C Tens) < R(((T))
((T)
Further Simplification and Final Result. It is easy to show. by proof of contraction, that the first constraint of (49) can be substituted by
Φ(T) = Pr(C 2 Teus D).
Thus, the second constraint of 49 can be simplified as
Pr(A): B(1 Tens)
M
Pr(Err D, C 2 Te))) < R(O(T))O(T)
Pr(A): B(1
Tens)
Pr(Err D, C Tens) Pr 2 Fens) < R(o(T))
+ Pr((A) -(1 Tens)" M
Pr(Err, D, Teux) R(p(T))((T)
Prr(A) 8(1 Tens) M PP(Err, D,C 2 Teus) < Pr(Err, C T).
Thus, the final version the optimization problem with respect to is
min
(50)
T,Tons
s.t. ((T) = Pr((C 2 Teass D)
Pr(A): B(1 Tens) Pr(Err, D,C Tens) Pr(Err, C T).
25

---

Under review as a conference paper at ICLR 2023
Algorithm 1: A Lower Bound of Φ0-
Input: the individual model 0: the test set D = {(z,, Je)),= the number of classes K; the oracle f2 X' - {0. 1} that tells whether a sample definite; the number of member models M; and B, the upper bound of Pmit....m, (-14) for all k E (1,2,... K}.
Output: An lower bound of Φu mentioned in Theorem
left=
right =1
10-9
while right - left ft > c do
(left right)/2
Tens = SEARCHFORTAAEESS(T (,
if Tens is not None and VERIFY VERIFSSCCONDCONNTRANNGG Tens 0, D.D. K, M, B) is True then
right= =
else
left T
(left. + r2ght)/2 return N Ei=1 I(C(x;;;) 2 // C(ay;; 0) is the confidence of 9 on sample 2ç.
Suppose do = ((T)), since to is the optimal solution (43 as T provides an upper bound of To- Thus, considering IS a monotone decreasing function of r, <(T*) is lower bound of du = ((To).
the optimal solution to (50) (denoted
Algorithm.
We design Algorithm search for the solution to (50) and then obtain the lower bound of do- Since Tens is determined by r (the first constraint of (50)). (50) can be reduced to one-dimensional search problem. Our algorithm adopts a binary search for efficiency, although this method might provide a suboptimal solution. The procedure of Algorithm in each iteration of the binary search as follows.
1. Given current T, A determines Tens using SEARCHFORTAUENS (see Algorithm 2 procedure that searches for Tens E [0, 1] using binary search s.t. Φ(T) = Pr(C Z D). Note that Tens might not exist, long as is low that ((T) Pr(D)
Tens:
sup, Supr.ar Pr(C 2
Tens, D). This problem will be addressed shortly.
2. Algorithm D exxms whether Tens exists. If Tens exists, Algorithm then examines whether the second constraint of (50) holds for current and Teus, which implemented by VERI- FY SEECONDONNTTAAIITT (see Algorithm 3)
3. If Tens exists and the second constraint holds, Algorithm 1 searches for a smaller t in the left half feasible area; otherwise, Algorithm [ feasible area.
searches for greater in the right half
Once the binary search completes and outputs r", Algorithm I returns the coverage of 0 with confi- dence threshold n"
An Example.
To show that Algorithm I works in reality, we run this algorithm on CIFAR-10, using the same individual model as Section 6 this example, K 10. M 5, the oracle is implemented by another ensemble with two individual models (the oracle outputs True if and only if the STD over member models' predictive distributions < 10-3). Note that it difficult to estimate B. On the one hand, we need to train ensemble with M models to estimate B, which is costly. On the other hand, the domain of PITK....IIT (-1A) has high dimension, so the observed data points are sparse in this domain, which makes the estimation of B more difficult. Thus, we do not estimate but try several hypothetical values of B we obtain different lower bounds of Φn as shows. We can see that when B < 10ah the lower bound of dn is greater than 50%, which indicates that Algorithm Imay may be robust to the choice of B.
at what B the lower bound of do is big. With different Bs,
26

---

Under review as a conference paper at ICLR 2023
Algorithm 2: SEARCHFORTAUENS
Input: the confidence threshold r; the individual model 0: the test set D = {(2,, W)) the oracle f2 X + (0, 1} that tells whether a sample definite.
Output: Tens E [0, 1] that satisfies the first constraint of (50).
EE == [x; 0) 2 // C(a;; 0) is the confidence of f on sample #;-
N >
Ci-1 M(xx then
L return None
left=
right= =1
10-9
while right - left do
Tens (left + right)/2
= [[C(2;;)) 0) 2 Fens (2(;) then
N
right= = Tens
else
L left = Tens
return
(left + right)/2
Algorithm 3: VERIIFSSCCONCCONNTRAIN
Input: the confidence threshold t; Teusi the individual model 0; the test set D {(x,, y: } the oracle Q X' - {0, }} that tells whether sample is definite; the number of classes K: the number member models M; and B, the upper bound of Prij....m,,, (-|4) for all
Ji=
1s E (1, 2,..... K}.
Output: True if and only if and Tens satisfy the second constraint of (50)
PA - [(xx)]] 3 K M
leftHandSide
PA 3(1 Tems) ) 1[(=0) # I[C(x,;;) 2 Teus)
E' I [[f(;;;) & ((C()()(); &rightHandSide)
return
This example also indicates the relationship between the ensemble's diversity and its selective clas- sification performance. Since an ensemble with smaller B seems to have more diversity over ambiguous samples, the result in Table g suggests that as long the ensemble has enough diver- sity over ambiguous samples, the ensemble guaranteed to have a lower selective risk than the individual model under a considerable range of coverage.
Table 8: The relationship between 6o 's lower bound and B on CIFAR-10, where the individual model the same as Section i
B
10
10a
10a
10
10a
10"
107
10"
10"
1019
10a1
1012
1028
10t
Jower bound du 0.737
0.737
0.737
0.736
0.735
0.729
0.705
0.599
0
27


Reviews:
[{"review_id": "oDkyM-SJm8a", "reviewer": "Reviewer_fKnJ", "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": "Selective classifiers have the ability to abstain on certain datapoints and consist of two functions - the classification function and the selection function. This paper considers ensembes of selective classifiers by averaging the probability distributions of the classifiers and also defining the selection function in a certain way. They provide some assumptions and theoretically prove that under those assumptions, the ensemble of selective classifiers has better selective risk than each of the individual models for certain values of coverage. They also verify these assumptions on a few datasets. They also find that the simplest ensemble of classifiers with maximum probability as the selection function has the best performance compared to the previous selective classification approaches.", "summary_of_the_review": "I think the idea is interesting but the paper lacks clarity and is not well written.", "strength_and_weaknesses": "The idea of combining ensembles and selective classification is interesting. \n\nIn assumption 2, why do we need the definite samples probability at confidence approaching 1 to be non-zero? It seems that the entire advantage of ensembles is coming out of the ambiguous samples. \n\nFor the ambiguous samples, assumption 2 says that there are a few ambiguous samples which are predicted with confidence by individual models. Why it can’t be the case that all the models predict the wrong label with confidence approaching 1?\n\nIt is very hard to understand assumption 3 in the paper and it is not clear what the intention of that assumption is. It would be good to explain that in the paper. Also, the authors have verified assumptions 1 and 2 but have not commented on the applicability of assumption 3 for practical settings. Can the authors please comment on that?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "nV95gca-x_", "reviewer": "Reviewer_X5Ed", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 analyze ensembles in the context of selective prediction. The authors show that under loose assumptions, a selective classifier using the probability assigned to the predicted class to decide whether to abstain from predicting can be improved by ensembling $n$ copies of it (differing only in their random seed). \n\nThe three assumptions required are, paraphrased:\n- A1: When all models agree on a prediction, they are less likely to be incorrect than when they disagree. \n- A2: Each individual model has a non-zero probability of assigning predicting a class with probability one (implying that models can be overconfidently incorrect).\n- A3: The joint PDF of all ensemble members is bounded on ambiguous queries (no prediction has PDF = $+\\infty$).\n\nThese assumptions in hand, the authors show (Prop 1.) that on ambiguous queries, an ensemble _cannot_ assign probability 1 to any class. It follows that (Thm. 2) ensembling will improve the selective risk up to a coverage $\\phi_0 > 0$.\n\nThe authors then evaluate their assumptions on vision and NLP datasets, as well as different ensembling techniques for selective prediction (including, but not restricted to, deep ensembles).", "summary_of_the_review": "This is an interesting paper addressing an important question in the ML community. However, this paper could be significantly improved by probing the derived theoretical and empirical results in much more detail. As it stands, the import of this work remains unclear, and it is difficult to place the specific results and limitations within the greater context of the selective prediction problem. \n\nThat being said, I believe that these weaknesses may be easily resolved, making this paper a valuable contribution to the field.", "strength_and_weaknesses": "# Strengths\n- The paper is well structured and motivated; the literature review and general positioning of this paper is clear and well situated within the greater context of the field.\n- The paper addresses an important task with clear applications to real life problems (can we automatically detect when to abstain from predicting), and analyzes a well-known, simple technique (ensembling) within this new context.\n- The authors conclusively show under intuitive hypotheses that ensembling will improve selective prediction.\n- Empirical results confirm that the hypotheses are most of the time reasonable; furthermore, empirical results show that ensembling for selective prediction is beneficial even beyond what theoretical results are provided.\n \n# Weaknesses\n- I believe the greatest issue with this work is that the theoretical and empirical results could be more detailed, as the current statements would benefit from greater investigation. For example:\n  * (Thm. 2) How does $\\phi_0$ depend on various ensemble characteristics? Can we bound it away from zero? Under which conditions?\n  * Similarly, I think a deeper analysis of what causes the MRPC dataset to violate the assumptions (which datapoints, and understanding why) would significantly strengthen the paper, especially as the scope of the theoretical results is somewhat limited (next point).\n- The scope of the theoretical results is limited to deep ensembles (i.e., ensembles whose predicted probability vector is obtained via a softmax). It wasn't very clear to me whether this assumption is required on top of the three assumptions detailed earlier -- if so, could the authors clarify why this is?\n- I found some of the notation unclear -- in some cases, the quantities being manipulated are vectors (of length = number of classes), but numerical estimates are scalars. For example, the standard deviation in $\\S$ 6.1. Similarly, is $R_\\text{ind}$ in Thm. 2 the average selective risk of all ensemble members?\n\nMinor: \n- I would recommend reordering Figure 2, so that each subfigure compares different models on a single dataset.\n- This paper could benefit from some quick SPAG proofreading, as there are several minor grammar mistakes throughout the paper.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "jVBObl1S3W", "reviewer": "Reviewer_zrP4", "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": "In this paper the authors address the selective classification problem with the goal of reducing the selective risk (a non-convex function of the model prediction). A selective classifier is a pair (f, g), where f is a classifier, and g: X -> {0, 1} is a selection function, that allows to abstain {= 0} on some difficult input. In this paper the approach combines several weak selective classifiers (ensemble wit M = 2 to 5 members). \nThe contribution is to prove that an ensemble has a lower selective risk than the individual model under a range of coverage.\nThe method has been tested on image classification (CIFAR-10/100 and SVHN) and text classification (MRPC, MNLI, QNLI) tasks. The backbones used are a VGG-16 and BERT-base networks respectively. The method is compared against selective classification approaches.\n", "summary_of_the_review": "The paper presents a series of experiments that support the hypothesis that a set of selective classifiers reduces selective risk. At the same time it suggests that the number of members of the ensemble should be low (2-5). Obviously, a high number of member classifiers corresponds to a cost in terms of resources, especially in DL. The paper is clear and readable. There is no technical novelty.", "strength_and_weaknesses": "**Strength**\n\n- Classification with abstention has gained a lot of attention in recent years. It is an important topic.\n- Interesting comparison between methods.\n\n\n\n**Weaknesses**\n\n- Novelty.\n\n- Table 1: it is not clear whether the results are presented with the same level of coverage. If the coverage level is different, it is difficult to compare the values. (It is recommended to add the coverage in the table, or to specify and use a fixed coverage).\n\nEnsemble techniques are presently hard to realize in the context of DNNs, for which it could be very costly to train sufficiently many ensemble members [1] [2].\n\n- What is a sufficient number of ensemble members? \n\nFigure 6 shows that the AURC  for the SR method on the test set decreases as the number of members in the ensemble increases. What is the accuracy of the model and coverage at M=20 for SR? \n\n- The big backbone is designed to have twice as many filters in every convolutional layer (VGG-16) why the authors didn't consider a ResNet-50/101?\n\n\n\n[1] Kush R Varshney. A risk bound for ensemble classification with a reject option. In Statistical Signal Processing Workshop (SSP), 2011 IEEE, pages 769–772. IEEE, 2011\n\n[2] Yoav Freund, Yishay Mansour, and Robert E Schapire. Generalization bounds for averaged classifiers. Annals of Statistics, pages 1698–1722, 2004.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "R1b34F_wO-B", "reviewer": "Reviewer_KH7o", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 submission shows that simple randomization-based learning of deep ensembles improves on training a single model when performing selective classification, regardless of the selective classification method that is employed. Given some assumptions that seem to hold in most of the classification scenarios considered in the submission, it is proven that this must indeed be the case. Another, empirical, finding of the submission is that simple selective classification based on a threshold on the maximum class probability is preferable to other methods, including the current state-of-the-art.", "summary_of_the_review": "Although the main finding of the submission, that randomization-based ensembles outperform individual models, is unsurprising, particularly considering the experiments reported by Lakshminarayanan et al., it may be useful to have the additional theoretical justification for this method that the submission presents. This justification, based on some assumptions that seem reasonable (and seem to hold in pertinent benchmark problems), appears to be novel. For practitioners, it is also useful to see that selective classification based on maximum probability beats the state of the art in the experiments presented in the submission.", "strength_and_weaknesses": "+ selective classification is an interesting and important problem\n+ results challenge what is considered the state of the art\n+ convincing empirical findings with theoretical support\n\n- the proposed method is not new and the improvements observed with ensemble learning are unsurprising\n- no discussion of work on estimating epistemic uncertainty, which seems a highly relevant topic\n\nQuestions and comments:\n\nAre the numbers after \"+/-\" in Table 1 standard deviations? How were these obtained?\n\n\"there has been no systematic study of ensemble methods in selective classification\" - repeated verbatim in two adjacent sentences\n\n\"selective risk ... are\"\n\n\"which detects samples different greatly from a given dataset\" - rephrase\n\n\"to the overconfident problem\" - rephrase\n\n\"For definite samples, given the predictive probability distribution of one member model...\" - I could not follow the reasoning here\n\n\"AURCs of the individual model\"\n\n\"for the better performance of the ensemble than the individual selective classifier\" - rephrase\n\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": "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