Is the Performance of My Deep Network Too Good to Be True? A Direct Approach to Estimating the Bayes Error in Binary Classification
Authors: Takashi Ishida
Ikko Yamane
Nontawat Charoenphakdee
Gang Niu
Masashi Sugiyama
Venue: ICLR 2023 notable top 5% (2023)
Keywords: Bayes error
best achievable error
irreducible error

Abstract: There is a fundamental limitation in the prediction performance that a machine learning model can achieve due to the inevitable uncertainty of the prediction target. In classification problems, this can be characterized by the Bayes error, which is the best achievable error with any classifier. The Bayes error can be used as a criterion to evaluate classifiers with state-of-the-art performance and can be used to detect test set overfitting. We propose a simple and direct Bayes error estimator, where we just take the mean of the labels that show \emph{uncertainty} of the class assignments. Our flexible approach enables us to perform Bayes error estimation even for weakly supervised data. In contrast to others, our method is model-free and even instance-free. Moreover, it has no hyperparameters and gives a more accurate estimate of the Bayes error than several baselines empirically. Experiments using our method suggest that recently proposed deep networks such as the Vision Transformer may have reached, or is about to reach, the Bayes error for benchmark datasets. Finally, we discuss how we can study the inherent difficulty of the acceptance/rejection decision for scientific articles, by estimating the Bayes error of the ICLR papers from 2017 to 2023.

Published as a conference paper at ICLR 2023
Is THE PERFORMANCE OF MY DEEP NETWORK TOO GOOD TO BE TRUE? A DIRECT APPROACH TO ESTIMAT- ING THE BAYES ERROR IN BINARY CLASSIFICATION
Takashi Ishida Ikko Yamanc
Nontawat Charoenphakdee
Gang Niu² Masashi Sugiyama
'Tee University of Tokyo 2RIKEN
ENSAI/CREST
ABSTRACT
There is a fundamental limitation in the prediction performance that a machine learning model can achieve due the inevitable uncertainty of the prediction target. In classification problems, this can be characterized by the Bayes error, which is the best achievable error with any classifier. The Bayes error can be used as a criterion to evaluate classifiers with state-of sifee-of-hhee ohetth-art performance and can be used to detect test set overfitting. We propose simple and direct Bayes error estimator, where we just take the mean of the labels that show uncertainty of the class assignments. Our flexible approach enables us to perform Bayes error estimation even for weakly supervised data. In contrast to others, our method is model-free and even instance- free. Moreover, it has no hyperparameters and gives a more accurate estimate of the Bayes error than several baselines empirically. Experiments using method suggest that recently proposed deep networks such as the Vision Transformer may have reached, is about to reach, the Bayes error for benchmark datasets. Finally, we discuss how we can study the inherent difficulty of the acceptance/rejection decision for scientific articles, by estimating the Bayes error of the ICLR papers from 2017 to 2023.
INTRODUCTION
Comparing the prediction performance of a deep neural network with the state-of-the-as (SOTA) performance is common approach validating advances brought by a new proposal in machine learning research. By definition, SOTA performance such as error or 1-AUC! monotonically decreases over time, but there is fundamental limitation in the prediction performance that machine learning model can achieve. Hence, it is important to figure out how close the current SOTA performance is to the underlying best performance achievable (Theisen al., 2021). For example, Henighan et al. (2020) studied the scaling law (Kaplan et al., 2020) of Transformers (Vaswani et al., 2017) by distinguishing the reducible and irreducible errors.
In classification problems, one way to characterize the irreducible part is the Bayes error (Cover & Hart, 1967: Fukunaga, 1990), which the best achievable expected error with any measurable function. The Bayes error will become zero in the special case where class distributions are completely separable, but in practice, we usually deal with complex distributions with some class overlap. Natural images tend to have lower Bayes error (e.g., 0.21 % test error on MNIST (LeCun et al., 1998) in Wan et al. (2013)), while medical images tend to have a higher Bayes error, since even medical technologists can disagree on the ground truth label (Sasada et al., 2018). If the current model's performance has already achieved the Bayes error, it is meaningless to aim for further error improvement. We may even find out that the model's error has exceeded the Bayes error. This may imply test set overfitting (Recht et al., 2018) is taking place. Knowing the Bayes error will be helpful avoid such common pitfalls.
Estimating the Bayes error has been a topic of interest in the research community (Fukunaga & Hostetler, 1975; Fukunaga, 1990; Devijver, 1985; Berisha al., 2016; Noshad et al., 2019; Michelueci
"Currently at Preferred Networks. AUC stands for "Area under the ROC Curve."

---

Published as a conference paper at ICLR 2023
et al., 2021; Theisen et al., 2021). To the best of our knowledge, all previous papers have proposed ways to estimate the Bayes error from a dataset consisting of pairs instances and their hard labels. When instances and hard labels are available, one can also train a supervised classifier, which is known to approach the Bayes classifier (that achieves the Bayes error) with sufficient training data provided that the model is correctly specified.
This is an interesting research problem from the point of view of Vapnik's 's principle" (Vapnik, 2000) since we can derive the Bayes error from the Bayes classifier (and the underlying distribution) while we cannot recover the Bayes classifier from the knowledge of the Bayes error, which is just a scalar, How can we take full advantage of this property? While the Bayes error is usually defined as the best achievable expected eπror with any measurable function, it is known to be equivalent to the expectation of the minimum of class-posteriors with respect to classes for binary classification. Inspired by Vapnik's 's principle, our main idea is to skip the intermediate step of learning a function model, and we directly approximate the minimum of the class-posteriin by using soft labels (corresponding to the class probability) or uncertainty labels (corresponding to the class uncertainty).
Our proposed method has two benefits. Firstly, our method is model-free. Since we do not learn a model, we can escape the curse of dimensionality, while dealing with high-dimensional instances would cause issues such as overfitting if we were to train a model. High dimensionality may cause performance deterioration for other Bayes error estimation methods (Berisha et al., 2016; Noshad et al., 2019) due to divergence estimation. We experimentally show how our method can more accurately estimate the Bayes error than baselines that utilize instances and soft labels. Our model- free method is also extremely fast since we do not have any hyperparameters to tune nor a function model train.
The second benefit is a more practical one: our method is completely instance-free. Suppose our final goal to estimate the Bayes error instead of training classifier. In that case, we do not need to collect instance-label pairs, and it may be less costly to collect soft/uncertainty labels without instances. Dealing with instances can cause privacy issues, and it can be expensive due to data storage costs especially when they are digensiimns or can come in large quantities. It may lead to security costs to protect instances from a data breach. As an example of an instance-free scenario, we can consider doctors who are diagnosing patients by inspecting symptoms and asking questions, without explicitly collecting or storing the patients' data in the database. In this scenario, the hospital will only have the decisions and confidence of doctors, which can be used soft labels.
The contributions of the paper is as follows. We first propose a direct way to estimate the Bayes error from soft (or uncertainty) labels without model nor instances. We show that our estimator is unbiased and consistent. In practice, collecting soft/uncertainty labels can be difficult since the labelling process can become noisy. We propose a modified estimator that is still unbiased and consistent even when the soft labels are contaminated with zero-mean noise. We also show that our approach can be applied to other classification problems, such as weakly supervised learning (Sugiyama et al., 2022). Finally, we show the proposed methods' behavior through various experiments. Our results suggest that recently proposed deep networks such as the Vision Transformer (Dosovitskiy et al., 2021) has reached or is about to reach the Bayes error for benchmark datasets, such as CIFAR-1OH (Peterson et al., 2019) and also demonstrate how our proposed method can be used to estimate the Bayes error for academic conferences such as ICLR, by regarding them as an accept/reject binary classification problem.
(which a new dataset we present; explained in Sec. 5.3). We
2 BACKGROUND
Before we discuss setup, will review ordinary binary classification from positive and negative data and binary classification from positive-confidence data in this section.
Learning from positive-negative data Suppose a pair of d-dimensional instance x E Rd and its class label y E (-1,-1] follows unknown probability distribution with probability density
"The Vapnik's 's principle is known the following: "When solving a given prohlem, try to avoid solving a more general problem as an intermediate step." (See. 1.2 of Vapnik, 2000) 3 An uncertainty label is subtracted by the dominant class posterior. We will discuss how to obtain soft lahels in practice in Sec. 3.
2

---

Published as a conference paper at ICLR 2023
function p(z, v). The goal of binary classification is to train binary classifier g: R - R so that the following classification risk R(g) will be minimized: R(g) Ep(m.y) (((g(())) where is a margin-bane based surrogate loss function such as the logistic loss (z(2) = log(1 + exp( squared loss (z(2) (z 1)². The classification error is Roi(g) = Bp(a,y) |fo1 (x)()))),, where we use the zero-one loss εuI, which takes 0 when y g(x) > 0 and 1 otherwise. In empirical risk
or the
minimization, the following estimator R(g) is often used:
R(g) :/- Ei= ((v1)(z;)).
1..d. p(x.y).
where
In this paper, our focus is not on the classifier itself but on the value of (g) when a good classifier is learned. This can be nicely captured by the notion of the Bayes error, defined as follows:
Definition 2.1. (Mohri et al., 2018) The Bayes error the infimum of the classification risk with respect to all measurable functions: 3 inf Rd-RR measurable Ep(x.y) fo0 (yg(æ))).
Learning from positive-confidence data positive-confidence classification (Ishida et al., 2018; Shinoda et al., 2020), we only have access positive data equipped with confidence { r;) J where 2; is positive instance drawn independently from p( y = +1) and r, is the positive confidence given by r. plu + +1)z)) Since we only have positive instances, cannot directly minimize Eq. (1). However, Ishida et al. (2018) showed that the following theorem holds.
Theorem 2.2. (Ishida et al., 2018) The classification risk can be expressed
R(g) = T E+ [((g())) 1-r(=) 1-r(z) ((-9(z))
(2)
if we have r(x) = ply +1)=) + 0 for all æ sampled from p(x). E+ is the expectation over the positive density p(z = +1) and π pvy = +1).
Since the expectation is over p = +1). we do not have to prepare negative data. Although т. usually unknown, we do need this knowledge since क can be regarded as proportional constant when minimizing Eq. (2). Hence, we can see how learning classifier is possible in this setup, but is estimating the Bayes error also possible? We will study this problem further in Sec. 4.
3 ESTIMATION WITH ORDINARY DATA
In this section, we propose our direct approach to Bayes error estimation.
Clean soft labels First of all, it is known that the Bayes enror can be rewritten as follows (Devroye et al., 1996; Mohri et al., 2018):
B Ex)p(a) [min(((y +1 p(y -1 [))]]
This means that we can express the Bayes error 33 without explicitly involving the classifier we assume that we have soft labels, which are {c:] where & = ply +1 ax)) and i.ddd (ar J p(z), we can construct an extremely straightforward estimator for the Bayes error:
= Σ min(fs, -c)-
In fact, Eq. (4) just the empirical version of Eq. (3). However, the significance lies in the observation that this can be performed in model-free and instonce-free fashion, since taking the averages of the smaller one out of a; and 1 c in Eq. (4) does not require model training and does not involve æ;,
Note that we can further weaken the supervision by sampling uncertainty labels, i.e., minye(=1) p(y æ&). Practically, this would mean that the label provider does not need to re- veal the soft label. Although the two similar, we can see how uncertainty labels are weaker by the fact that we cannot recover p(y = +1 x) from min (11) p(y x)) Furthermore, we can recover n = ply = +1) by the expectation of soft labels E Epp = +1 =)) = T_, but #4 cannot be recovered by averaging uncertainty labels.
Our estimator enjoys the following theoretical properties.
Forr example, if (1n) p(y .)) 0.1, we do not know whether p(y =1 ||| (z) is 0.9 0.1.
3

---

Published as a conference paper at ICLR 2023
Proposition 3.1. 3 is an unbiased estimator of the Bayes error.
Proposition 3.2. For any 8 > 0, with probability at least we have, 1 31
log +hf
V
The proofs are shown in App. C.I and App. C.2, respectively. This implies that | is consistent estimator to the Bayes error, i.e., Ve > 0, lim,- P( B 2) 0. The rate of convergence is | - 3| Op(1/ vn), where Op is the stochastic big- O notation, cf. App. D. This rate is the same as classifier training and is the optimal parametric rate (Mendelson, 2008) although our method can be regarded non-parametric. We also free from the curse of dimensionality since the instance dimension d does not appear in the bound.
Noisy soft labels So far, our discussions were based on an assumption that soft (or uncertainty) labels is precisely the class-posterior (or c)). Since this may not be satisfied in practice, we consider a situation where noise & is added to the class-posterior values. We observe noisy soft labels {u; )= where u, C, + &, Since we ask labellers to give us a probability, a constraint is 0 s uy S 1, and we assume [[] = If we naively use these noisy versions, our estimator becomes
= [min (u;, 1 - u4)
(5)
However, we can show the following negative result.
Theorem 3.3. 3 is generally biased estimator of the Bayes error: E
((c.&)))) Hid p(c.g) [8] # B.
This is basically due to the noise inside the nonlinear min operation. We show the proof in App. C.3.
This issue can be fixed we have an additional binary signal that shows if the instance is likely to be more positive negative. Formally, if we have access to sign labels, i.e.
we can divide {u:}i into {u V and {u, Y depending on the sign label, with n n + ng Then we can construct the following estimator:
sign [p(y = +1|=;; 0.5] Vi E f1,2, 2,,.,....
.., n
BNoise = 1 E (1 - (1-4))++3 E
With this modified estimator BNoises show the following propositions.
Proposition 3.4. 8xoise an unbiased estimator of the Bayes error.
The proof is shown in App. C.5. The proof itself is simple, but the main idea lies in where we modified the estimator from Eq. (4) to avoid dealing with the noise inside the min operator, by utilizing the additional information of s,.
Proposition 3.5. For any > O, with probability at least 6, we have, 1âNoisc - B S
log 2 8
2n
The proof is shown in App. C.6. This implies that ANoise is consistent estimator the Bayes error, i.., for Ve 0, lim P( P( - B) 2 e) O. The rate of convergence is OpLL/vn).
In practice, one idea of obtaining soft labels is to ask many labellers to give a hard label for each instance and then use the proportion of the hard labels as noisy soft label. This is the main idea which we use later on in Sec. 5.2 with CIFAR-10H (Peterson et al., 2019). For simplicity, suppose that we have m labels for every instance i, and u, is the sample average of those labels: 1). where Vij is the jth hard label for the ith instance and 1 denotes
M4 = ΣØ= 1 [Us. the indicator function. This satisfies our assumptions for noisy soft labels since 0 < u, S 1 and Elg, c:] 0 for any m N. If in practice we do not have access to sign labels, we cannot use the unbiased estimator BNoise and we have no choice but to use the biased estimator However, in the following proposition, we show that the bias can be bounded with respect to m.
Proposition 3.6. The estimator B is asymptotically unbiased, i.e., |3 Vlog m2) (2m), where m is the number of labellers for each of the n instances.
E| < 2
The proof is shown in App. C.4. The rate of convergence is O( O(Voo((2nm)/m
4

---

Published as a conference paper at ICLR 2023
Hard labels Surprisingly,
regard the usual hard labels special case of noisy soft labels.
This enables us to estimate the Bayes error with hard labels and sign labels. To see why this is the case, consider specific type of noise: & is 1 ply = +1 x;)) w.p. ply +1 x;)) and -p(y = +1 x;) w.p. - p(u = +1 2;)) Since u4 = G &.. this implies u4 = 1 w.p. pyy = +1 (z))) and u, 0 w.p. ply -1 ). We can easily confirm that our assumptions for noisy soft labels
satisfied: 0 < & S and Eig ci] = 0.
If assign y - +1 for u; and y - for u, 0. this will be equivalent providing a hard label based on a Bernoulli distribution Be(ply = + (x:)) for an instance æ; sampled from p(æ).
This corresponds the usual data generating process in supervised learning.
ESTIMATION WITH POSITIVE-CONFIDER
DATA
In this section, we move our focus to the problem of estimating the Bayes error with positive- confidence (Pconf) data (Sec. 2). First, we show the following theorem.
Theorem 4.1. The Bayes enror can be expressed with positive-confdence data and class prior:
Breont == a+ (1 - 11-E+ max (0. 2 - )) =
Recall that B, is Eptaly=+11 1) and r(x) = pyy = +1|2). The proof is shown in App. C.7. Based on Theorem 4.1, can derive the following estimator:
Brconl π (1 (1-22 n E max (0.2- 2.).
(8)
where = ppy +1 (ax)) for an; p(aly +1), and n4 is the number of Pconf data. We can estimate the Bayes eπrоr in an instance-free fashion, even if we do not have any r; from the negative distribution. All we require is instance-free positive data and TT. A counter-intuitive point of Eq. (8) is that we can throw away r; when r; < 0.5, due to the max operation. If the labeler is confident that rs < 0.5, we do not need the specific value of r;. Note that in practice, T; may occur for positive samples. This will cause an issue for classifier training (since Eq. (2) will diverge), but such samples can be ignored Bayes error estimation (due to the max in Eq. (8)).
As discussed in Sec. 2, . was unnecessary when learning a Pconf classifier, but it is necessary for Bayes error estimation. Fortunately, this is available from other sources depending on the task, e.g., market share, government statistics, other domain knowledge (Quadrianto et al., 2009; Patrini et al., 2014). Instead of the Bayes error itself, we may be interested in the following: 1) the relative comparison between the Bayes error and the classifier's error, 2) whether the classifier's error has exceeded the Bayes error or not. In these cases, T. is unnecessary since we can divide both errors (Eq. (8) and empirical version of Eq. (2) by क. without changing the order of the two.
We can derive the following two propositions.
Proposition 4.2. Pooon is unbiased estimator of the Bayes error.
Proposition 4.3. For any â > 0, with probability at least 8, we have, [8peont - B] S
$V
x2 2n
log 2.
The proof' are shown in App. C.8 and App. C.9, respectivelly This implies that the estimator 3poont is consistent to the Bayes error, i.e., for Ve > 0. lim,-toc P(]SPeout A 2 c) 0. The rate of convergence Op(1/ (1(1//m)) We can also see that the upper bound Prop. 4.3 is equivalent to the upper bound in Prop. 3.2 when the data is balanced, i.e., π 0.5.
5 EXPERIMENTS
In this section, we first perform synthetic experiments to investigate the behavior of our methods. Then, we use benchmark datasets to compare the estimated Bayes error with SOTA classifiers. Finally, we show a real-world application by estimating the Bayes error for ICLR papers.
Our code will be available at https:////// htpp::////t //gi thub. ctt.tb...mtaaaaaaaaaa ishi da/ rreducible
5

---

Published as a conference paper at ICLR 2023
Agprnieet HMK coarte
peniiii lars Cham
HRRE Cla for
Hart clas
Sent canole 2ets EardEn
Selt caes Se5
Selt clasiii
Caas LandE
caas
24 2
(a) Sctup A
(b) Sctup B
(c) Setup C
(d) Setup D
Figure Comparison of the proposed method (blue) with the true Bayes error (black), recent Bayes eπrоr estimator "Ensemble" (orange) (Noshad et al., 2019), and the test error of multilayer perceptron (hard labels: green, soft labels: purple). We also use the classifier's probabilistic output and plug it into the Bayes error equation in Eq. (3), shown as "Classifier-BBe labels: brown). The vertical/horrizontal axis is the test error or estimated Bayes error/# of training samples per class, respectively. Instance-free data was used for Bayes error estimation, while fully labelled data was used for training classifiers. We plot the mean and standard error for 10 trials.
(hard labels: red, soft
Figure 2: Bayes error with and without noise on the labels, with mean and standard error for 10 trials. The vertical/horizontal axis is the esti- mated Bayes error/the number of samples. With noisy labels, the estimation tends to become in- accurate with a larger standard error. With more samples, the difference between clean labels be- comes smaller, but a small bias remains. With modified estimator, the bias vanishes.
volse! telioo
28 32 04 353 256 5333855
35 32 24 3i2
(a) Sctup
(b) Sctup B
5.1 ILLUSTRATION
nesitive-negative data Setup: We use two Gaussian distributions to construct a binary classification dataset. We then derive the positive-class posterior analytically for each data and use it our label. We use Eq. (4) to estimate the Bayes error. We change the number of training samples per class (2, 22...8.... S,.., 1028) to observe how quickly we can approach the true Bayes error. We perform experiments with four setups (A, B, C, and D) and the details are explained after Sec. 6. To compare with the true Bayes error of the setup, we take the average of c(x>) for 10, 000 samples. We expect this to be good substitute because we are using the analytically derived class posteriors for the soft labels. Although our problem setting does not require instances, we also compare with a recent Bayes error estimator that uses instances and hard labels (Noshad et al., 2019) and classifiers trained from instances and hard labels. We train a multi-layer perceptron model with two hidden layers (500 units each, followed by BatchNorm (loffe & Szegedy. 2015) and ReLU (Nair & Hinton, 2010)). We use the following cross-entropy loss: - 11y, = +1] log po (y = +1/x,) 1ly lo] Pv -2,,), where Po(y)ar) is the probabilistic output of the trained classifier and 0 represents the model parameters. We chose the cross entropy loss because it is a proper scoring rule (Kull & Flach, 2015). We use stochastic gradient descent for 150 epochs with learning rate of 0.005 and momentum of 0.9. We also compare with another baseline ("classifier-BER) we plug in ( (z)) to Eq. (3). Finally, we add stronger baseline "soft classifier" which utilizes soft labels. If the soft label is r; for sample F,, then the cross-entropy loss is modified as follows: -r; log Po +1,,,) (1 r;) log Po -1xx))
where
We construct dataset with the same underlying distribution ten times and report the means and standard error for the final epoch in Fig. 1. We can see how the estimated Bayes error is relatively accurate even when we have few samples. The benefit against classifier training is clear: the MLP model requires much more samples before the test error approaches the Bayes error. The classifier is slightly better when it can use soft labels but is not good as our proposed method. It is interesting how the "hard classifier-Be BERR" tends to underestimate the Bayes error (except Fig. 1d). This can be explained by the overeonfidence of neural networks (Guo et al., 2017), which will lead to small minye (11} p(y x). This underestimation does not occur with "soft classifier- "eessffirrBBR,""" implying that there are less room to be overconfident when we learn with the modified cross-entropy loss.
Results:
6

---

Published as a conference paper at ICLR 2023
Figure 3: Estimated Bayes error with PN (positive and negative) and Pconf (positive- confidence). The vertical/horizontal axis is the estimated Bayes error/number of samples. We plot the mean and standard error for 10 tri- als. The difference between the two becomes smaller as we increase the number of training samples.
armeed Dayt anr TM
Jost
10.
urtrend Dep
12
60
24-
120 236 5b 3320
120 26 512 3035
(a) Sctup A
(b) Setup B
Positive-negative data with noise Setup: Next, we perform experiments when we have noise on the labels. We follow the assumption in Sec. 3, and we design the noise to have mean 0 and the label to be between 0 and 1 after adding this noise, to be valid probability. For this purpose, we add noise to the underlying class posterior and use a truncated Gaussian distribution p(z) with standard deviation 0.4. We truncate the left tail { E [R S μ min(1 H4 14 - 0)} and the right tail {a E R|2 2 + min(1 μ. μ - 0)} where μ E [0, I] is the mean of the distribution, i.c., the true class posterior. We compare three estimators: 1) Original estimator /3 in Eq. (4) with clean labels, 2) original estimator 3 in Eq. (4) with noisy labels, and 3) proposed estimator &Noise in Eq. (6) with noisy labels. We repeat the experiment 10 times with different data realizations. Results: The mean and standard error for 10 trials
shown in Fig. 2, for varying number of training samples. As expected, using noisy soft labels lead to worse results for 3,
can see with the larger standard errors. Increasing the sample size is effective to some degree, but the bias does not vanish. However, if we use modified estimator &Noise. the bias vanishes completely and works well even with noise.
Positive-confidence data Setup: Similarly, we perform experiments for positive-coffidncce (Pconf) data. The data is generated so that the class prior T. is 0.5, and we assume this information is available. We only use the confidence of data from the positive distribution and do not use the confidence of data from the negative distribution. We use this data to estimate 3Peonf and compare it with the / derived earlier. Results: We report the mean and standard error for 10 trials in Fig. 3. Although Bayes error estimation tends to be inaccurate with Pconf data for fewer samples, the difference between the two disappears with more samples.
5.2 EXPERIMENTS WITH BENCIMARK DATASETS: CIFAR-10
Setup: We use CIFAR-10 (C10) (Krizhevsky, 2009), ciFAIR- 100 (C10F) (Barz & Denzler, 2020), CIFAR-10. 10.1 (C10.1) (Recht et al., 2018), and CIFAR-1OH (C10H) (Peterson al., 2019). C10 an image dataset of 10 classes: airplane, automobile, bird, cat, deer, dog, frog, horse, ship, and truck. However, the test set C10 is known to include complete duplicates and near-duplicates from the training dataset. C10F replaces the duplicates in the test set with a different image. C10.1 is new test set to evaluate C10 classifiers. It ensures the underlying distribution to be as close to the original distribution as possible, but it does not include any images from the original test set. C10H is dataset with additional human annotations for the C10 test set. Each image in the test set has class labels annotated by around 50 different human labelers. We take the proportion to construct soft labels that we will use for Bayes error estimation. Although these datasets are originally multi-class setups with 10 classes, we re-construct binary datasets in the following four ways: animals vs. artifacts, land vs. other (water/sky), odd vs. even, and first five vs. last five. See the details after Sec. 6.
We compare the estimated Bayes error 3 with the base model of Vision Transformer (Dosovitskiy et al., 2021) with 16 x 16 input patch size (ViT B/16), DenseNet169 (Huang et al., 2017). ResNet50 (He et al., 2016), and VGG11 (Simonyan & Zisserman, 2015). For ViT B/16, we downloaded the official pretrained model (Dosovitskiy et al., 2021) and used the implementation by Jeon (2020) to fine-tune on C10. For others, we use the models provided in Phan (2021), which are trained on C10. Although these are ten-class classifiers, we transform them into binary classifiers by swapping the predictions into positive and negative based on the setups (details shown after Sec. 6). For example, prediction of "cat" would be swapped with a positive label in "animals vs. artifacts".
Results: We compare the estimated Bayes error 3 with classifier training in Fig. 4. As expected, the test error (shown in light blue) is lower for newer network architectures, with ViT achieving the
7

---

Published as a conference paper at ICLR 2023
C-10
Figure 4: Comparing the estimated Bayes er- ror with four classifiers and two setups (Fig- ures 4a, 4b). Although it seems that ViT B/16 has surpassed the Bayes error for all four se- tups for CIFAR-10 (C10), ciFAIR-10 (C10F), and CIFAR-1O.1 (C10.1), it is still comparable or larger than the Bayes error for CIFAR- 10H (CIOH). In Sec. 5.2, we discuss how this has to be investigated carefully. The black error bar for the Bayes error is the 95% confidence interval. The black error bar for the C10H is the standard error for sampling test labels 20 times.
C100
Error (K)
110.1
Error (N)
101.1
C10H
C10HH
Demsoliet
estimated Bayes error
Mtsie Transfommr 826
entimated Bayos eruur
Transtormer B2G
(a) Animals vs, artifacts
(b) Land vs. other
lowest test error. An interesting observation is that the test error of ViT has exceeded the estimated Bayes error in all four setups, which theoretically should not take place. We first suspected that ViT's error is too low (overfitting to the test set; Sec. B) but found out this is not necessarily the case. We investigated the degree of overfitting to the test set by performing experiments with C10F and C10.1. The former dataset excludes the duplicated images between training and test set, and the latter dataset a fresh test set that is designed to close to the original distribution of C10. The test error for the C10F dataset becomes slightly worse and much worse for CI0.1. This is what we expected and implies that overfitting to the test set may be happening to some degree. However, VIT's error is still below the estimated Bayes error even for C10.1.
To explain why ViT's error is still below the estimated Bayes error, we discuss the discrepancy between the underlying p(y|æ) for C10 and C10H. C10 is constructed with three-step procedure: first, collect images by searching for specific terms in search engines, downscale them to 32 x 32 (Torralba al., 2008), and finally ask labelers to filter out mislabelled images (Krizhevsky, 2009). On the other hand, C10H constructs the labels by asking labelers to choose the correct class out ten classes after seeing each downscaled image of C10. This makes visually harder for human labellers. Hence, the labelling process will become less confident, and this may lead to a higher entropy of the distribution of the human labels. According to Eq. (4), this will lead to an overestimation of B.
To adjust for the distribution discrepancy, we also plot the test errors when we sample a test label for each sample from the C10H dataset (repeated 20 times) and show this in Fig. 4 with pink. Note that this generally will not go below the estimated Bayes error. For example, consider an extreme case with zero test error for the original test set. If test sample has ply = +l)w) = 0.8 in C10H, then it will incur an error of 0.2 on average for the new test labels. After adjusting for the discrepancy, we see how the test error of ViT is par with or slightly higher than the estimated Bayes error. This implies that we have reached (or is about to reach) the Bayes error for C10H.
5.3 EXPERIMENTS WITH BENCHMARK DATASETS: MASHION-MNIST
Setup: To our knowledge there is only one large-scale dataset with over 10 annotations per sample (Peterson et al., 2019), which we used in Sec. 5.2. Hence, it would be beneficial to construct another benchmark dataset with multiple annotations. We collected multiple annotations for each test image in Fashion- (Xiao et al., 2017). Similar to CIFAR- 10H, we name our dataset as Fashion-MNIST-H See our data collection details in App. E.
Since aiming for SOTA performance on Fashion- MNniiionM-NNSTTTI is less common in our community compared with CIFAR-10, 10, we simply chose ResNet- 18 (He et al., 2016) for our model architecture. We trained for 100 epochs with batch size 128, learning rate 0.001 on the original labels (no data augmentation) and reconstructed the 10-class predictions into binary predictions by grouping shirt, dress, coat, pullover, and t-shirt/top as the positive class, and the other 5 categories as the negative class.
Results: We compared the binary predictions with a test label sampled from the multiple annotations (repeated 10 times) and derived the error, which is basically the same procedure of the pink bar in Fig. 4. The error 3.852% (+ 0.041% 1)), where the percentage in the parentheses is the standard error. On the other hand, the estimated Bayes error was 3.478% (+ 0.079%). where the percentage in the parentheses is the 95% confidence interval. We can how the estimated Bayes error is
8

---

Published as a conference paper at ICLR 2023
higher than the results for CIFAR-1OH in Fig. 4, implying that Fashion-MNIST is more difficult than CIFAR-10. This is intuitive as the 28 x 28 grayscale images are ambiguous while the original 51 x 73 PNG image is much more clear, e.g.. see Fig. 1 in Xiao et al. (2017), and also consistent with the results in Theisen et al. (2021). The R8 error is approaching the estimated Bayes error, but may still have room for small improvement. Since made simple choice of model architecture, we may be able to close this gap by other architectures that are more suited for Fashion-MNIST images, adding data augmentation, and trying extensive hyper-parameter tuning.
5.4 EXPERIMENTS WITH REAL-WORLD DATASETS: ACADEMIC PAPER CLASSIFICATION
We consider accept/reject binary classification task for ICLR papers and estimate the Bayes error for this task. We believe this is an interesting real-world application because it may be used as a tool to help gain deeper understanding of the trends/characteristies of academic conferences.
Setup: We used the OpenReview API to get data from ICLR 2017 to 2023. We removed papers that do not have decision, e-g., withdrawn desk-rejected papers. This real-world application is interesting because we have access to expert soft labels, i.e., the recommendation scores of the reviewers. We can derive a weighted average of the scores based on the confidence provided by the reviewer, (E, C. /E ct), where C is the confidence and s; is the score for reviewer i, respectively. In ICLR, this average between and and is not probability. Fortunately, we also have access to the hard label (final decision) for each paper which we can use for calibration. We used Platt scaling (Platt et al., 1999) with the hard labels so that we have a calibrated score between and 1. Then we use our proposed estimator to derive the Bayes error for each year of ICLR.
Assumptions of the data generation process: First, reviewer provides score between 0 and for cach paper. Then the Area Chair (or SAC/PC) samples a binary label (accept/reject) based on a Bernoulli distribution
ICLR's s Bayes error
2017
6.8%(+1.0%))
with the score provided by the reviewers. We feel this is realistic since
2018
8.7%
the AC usually accepts/rejects papers with very high/low average scores
2019
7.9%(++0.%))
while the AC puts more effort into papers with borderline scores meaning
2020
8.8%(+0.5%)
that papers close to borderline can end up both ways. These are the papers
2021
9..5
responsible for raising the Bayes error. Our motivation for deriving Bayes error estimates for conference venues is to investigate this kind of intrinsic difficulty.
2022
(.0.5)
2023
8.0%
From Table 1, we can see that the Bayes error is stable to some extent and there are no disruptive changes over the years, e.g., Bayes error is not doubling or tripling. We can also confirm that Bayes error for ICLR paper accept/reject prediction is higher than the other benchmark experiments with CIFAR- 10 and Fashion-MNIST, which is expected since understanding the value of a paper is much more difficult than identifying dogs, cars, t-shirts, etc.
Results:
Table 1: Parenthesis is 95% confidence interval.
This example demonstrates the benefit of our instance-free approach. At least at the time of writing, we do not rely on state-of-the-art ML to review papers submitted to academic conferences/joumalls Even if we wanted to, it is not clear what the features would be. Since new papers are reviewed based on the novelty compared to all previous papers, how to handle this is nontrivial. This implies we cannot easily instance- based Bayes error estimators. It also demonstrates where we can directly sample soft labels from experts instead of collecting multiple hard labels.
situation
CONCLUSIONS
We proposed a We showed how we can estimate it with uncertainty labels, noisy soft labels, or positive-confidence. In experiments, we demonstrated how Bayes error estimation can be used to compare with the SOTA performance for benchmark datasets, and how it can be used to study the difficulty of datasets, e.g., paper selection difficulty. Although we did not detect strong evidence of test set overfitting in Secs. 5.2 and 5.3, we interested in investigating other benchmark datasets in the future.
Bayes error estimation method that is unbiased and consistent.

---

Published as a conference paper at ICLR 2023
ETHICS STATEMENT
Constructing soft labels may rely on collecting human annotations. This may potentially have a negative impact, e.g., cost of the annotations. We are hoping lower the cost of annotations in our future work. We will only publish our annotations we collected in Sec. 5.3 in a way that does not contain any private information, e.g., only the category counts for each images and drop all other worker-related information.
REPRODUCIBILITY STATEMENT
We will upload the code for implementing our proposed methods and labels of Fashion-MNIST-H in https: / /tt//g/ttuutttt thub. cwm/taaaaaaaaoooeeoo tatttaaassshiiaa www.ssisssiiii iisiiiiaa//iie http/iireedubbbbb
Synthetic experiments: In the synthetic experiments, we used four setups: A, B, C. and A and are 2-dimensional anisotropic setups and is borrowed from the first two synthetic datasets in Ishida et al. (2018), where the code is provided in https: //github.bb////// com/t takashi wwwssiisiiiaa. dao.oa//ppoooooooooooooooooooood C is 10-dimensional isotropic setup with means μ44 = [0,.... ..... OJ and μ [I,...: 1] with identity matrices for the covariance matrices. is the same as except that the dimension is doubled 20.
We used https: http:/g/ttttttt com www.m//mnttohhh//aaaaeee..e ble method (Noshad et al., 2019). To make it advantageous for this baseline, used KNN for bw sew.seeeciinn when we had 16 or more samples per class but used manual when we had less than 16. We partially used ht tps:: : / /ggthubb. , com http/taaashiiii www.sshiiihhaaaeemee shida/ flooding for training classifiers in synthetic experiments with Gaussian distributions.
Betor__stiii imstorror for the ensem-
Benchmark experiments: We used data and code provided in https::/cvjeem: www.wee.eaiitttaeeeeeo io/cifair// for ciFAIR-10 (Barz & Denzler, 2020), We used data and code provided in https://github com/ jwwptersoo/cciaaraaaar/rr 10h for CIFAR-IOH (Peterson al., 2019). We used data and code provided in https: //gi thub. CIFAR-10,1 for CIFAR-10.1 (Recht et al,, 2019) and PyTorch wrapper provided in We used data provided for CIFAR-1O. We used CIPAR1O for VGG11, ResNet50, and modelss trained on CIFAR-10. We used the ResNet-18 implementation provided in We used https: //qi thub. com//jeonsvorrld//ii---tooooooo to fine-tune VIT and downloaded pretrained weights from s tab=
in https://gttnibb.commmuyuaaaaaa/p
tttps://gitthub.comrraattt http://eeeeeeeeeeeeeeeeeeeeoeeee
http:::/coonsole.ccoodd...o
com/ httmm/ttragg///eee
We are not aware of any personally identifiable information or offensive content in the datasets we used. We also collected annotations by using Amazon Mechanical Turk (Buhrmester et al., 2016). We explained the details of how we collected the annotations in Sec. 5.3, and we plan remove all personally identifiable information when we publish the data.
The details of the two (or four) binary datasets that are used in Sec. 5.2 (or App. 8) are as follows.
Animals vs. artifacts: we divide the dataset into cat, deer, dog, frog, and horse for the positive class and plane, car, ship, truck, and bird for the negative class.
Land vs. other (water/sky): we divide the dataset into car, truck, cat, deer, dog, horse for the positive class and plane, ship, bird, and frog for the negative class.
Odd vs. even: we divide the dataset into odd and even class numbers, with plane, bird, deer, frog, and ship for the positive class and car, cat, dog, horse, and truck for the negative class.
First five vs. last five: we divide the dataset into the first five and last five classes based on the class number, with plane, car, bird, cat, and deer for the positive class and dog, frog, horse, ship, and truck for the negative class.
Real-world experiments:
We used the OpenReview API (https: /tttps://bocs.opezeeri..e openreview net/) and openreview-py (https: /pppi.. org/ ppwpject/ppeeeeviiiiiieeeeeeeeee reviewers' scores for papers from ICLR 2017 to ICLR 2023.
to collect
10

---

Published as a conference paper at ICLR 2023
All of our experiments were conducted with single Mac Studio except when trained ResNet- 18 in Sec. 5,3 and fine-tuned ViT in Sec. 5.2, which was when we utilized Google Colab Pro+ in https: http://ooaabb..eereeeeeeee google com.
ACKNOWLEDGEMENTS
We thank Taiji Suzuki, Hiroshi Kera, Futoshi Futami, and Toshihiro Kamishima for the helpful discussions. TI was supported by JST, ACT-X Grant Number JPMIAX2005, Japan. IY acknowledges the support of the ANR part of the "Investissements d' avenir" program, reference ANR-19-P315 0001 (PRAIRIE 3IA Institute). MS was supported by JST CREST Grant Number JPMJCR 18A2
REFERENCES
Han Bao, Gang Niu, and Masashi Sugiyama. Classification from pairwise similarity and unlabeled data. In ICML, 2018.
Björn Barz and Joachim Denzler. Do we train test data? Purging CIFAR of near-duplicates. Journal of Imaging, 6:41, 2020.
Visar Berisha, Alan Wisler, Alfred O. Hero, and Andreas Spanias, Empirically estimable classification bounds based nonparametric divergence measure. IEEE Transactions Signal Processing. 64:580 - 591, 2016.
Lucas Beyer, Olivier Hénaff, Alexander Kolesnikov, Xiaohua Zhai, and Aäron van den Oord. Are done with imagenet? arXiv preprint arXiv:2006.07159 2020.
Michael Buhrmester, Tracy Kwang, and Samuel D Gosling. Amazon's mechanical turk: A new
source of inexpensive, yet high-quality data? American Psychological Association, 2016.
O. Chapelle, B. Schölkopf, and A. Zien (eds.). Semi-Supervised Learning. MIT Press, Cambridge, Massachusetts, USA, 2006.
Thomas Cover and Peter Hart. Nearest neighbor pattern classification. IEEE transactions information theory, 13(1):21-27, 1967.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In CVPR, 2009.
Pierre A. Devijver. A multiclass, k-NN approach Bayes risk estimation. Pattern Recognition Letters, 3:1 6, 1985.
Luc Devroye, László Györfi, and Gábor Lugosi. Probabilistic Theory of Pattern Recognition. Springer, 1996.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In ICLR, 2021.
M. C. du Plessis, G. Niu, and M. Sugiyama. Analysis of learning from positive and unlabeled data. In NeurlPS, 2014.
Keinosuke Fukunaga. Introduction Statistical Pattern Recognition. Academic Press, 2nd edition, 1990.
Keinosuke Fukunaga and Larry D. Hostetler. k-nearest-neighbor Bayes-risk estimation. IEEE Transactions on Information Theory, 21:285 -933, 1975.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In ICML, 2017.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.
11

---

Published as a conference paper at ICLR 2023
Tom Henighan, Jared Kaplan, Mor Katz, Mark Chen, Christopher Hesse, Jacob Jackson, Heewoo Jun, Tom B. Brown, Prafulla Dhariwal, Scott Gray, Chris Hallacy. Benjamin Mann, Alec Rad- ford, Aditya Ramesh, Nick Ryder, Daniel M. Ziegler, John Schulman, Dario Amodei, and Sam McCandlish. Scaling laws for autoregressive generative modeling. arXiv:2010. /470 2020.
Gao Huang. Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. In CVPR, 2017.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In ICML, 2015.
Takashi Ishida, Gang Niu, and Masashi Sugiyama. Binary classification from positive-confidence data. In NeurIPS, 2018.
Eunkwang Jeon. Vision transformer. httppp///ggtaaa...c//////ssse/es 2020. Accessed: 2021-10-01.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. In arXiv:2001.08366 2020.
Douwe Kiela, Max Bartolo, Yixin Nie, Divyansh Kaushik, Atticus Geiger, Zhengxuan Wu, Bertie Vidgen, Grusha Prasad, Amanpreet Singh, Pratik Ringshia, Zhiyi Ma, Tristan Thrush, Sebastian Riedel, Zeerak Waseem, Pontus Stenetorp. Robin Jia, Mohit Bansal, Christopher Potts, and Adina Williams. Dynabench: Rethinking benchmarking in NLP. In NAACI, 2021.
Diederik Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible 1 convolutions. In NeurIPS, 2018
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Meelis Kull and Peter Flach. Novel decompositions of proper scoring rules for classification: Score adjustment as precursor calibration. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 68-85. Springer, 2015.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (6(11):2278-222 1998.
Patrick Lewis, Pontus Stenetorp, and Sebastian Riedel. Question and answer test-train overlap in open-domain question answering datasets. In EACL, 2020.
Gang Li, Jan Zrimee, Boyang Ji, Jun Geng, Johan Larsbrink, Aleksej Zelezniak, Jens Nielsen, and Martin KM Engqvist. Performance of regression models as function of experiment noise. Bioinformatics and Biology Insights, 15:1-10, 2021.
Nan Lu, Gang Niu, Aditya Krishna Menon, and Masashi Sugiyama. On the minimal supervision for training any binary classifier from only unlabeled data. In ICIR, 2019.
Horia Mania, John Miller, Ludwig Schmidt, Moritz Hardt, and Benjamin Recht. Model similarity mitigates test set overuse. In NewrIPS, 2019.
Shahar Mendelson. Lower bounds for the empirical minimization algorithm. IEEE Transactions Information Theory, 54(8):3797-3800 2008
Umberto Michelucci, Michela Sperti, Dario Piga, Francesca Venturini, and Marco A. Deriu. A model-agnostic algorithm for Bayes error determination in binary classification. arXiv preprint arXiv:2107.11609 2021.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, 2nd edition, 2018.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In ICMI,, 2010.
12

---

Published as a conference paper at ICLR 2023
Morteza Noshad, Li Xu, and Alfred Hero. Learning to benchmark: Determining best achievable misclassification error from training data. arXiv:1909.07192, 2019.
Giorgio Patrini, Richard Nock, Paul Rivera, and Tiberio Caetano. (almost) no label no cry. In NeurIPS, 2014.
Joshua C. Peterson, Ruairidh M. Battleday, Thomas L. Griffiths, and Olga Russakovsky. Human uncertainty makes classification more robust. In ICCV, 2019.
Huy Phan. Siarch_cifallue
httpp:///ggtaaa...o////yaaaaaa// 2021. Accessed: 2021-10-01.
John Platt et al. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances in large margin classifiers, 10(3):61-74, 1999.
Novi Quadrianto, Alex J Smola, Tiberio S Caetano, and Quoc Le. Estimating labels from label proportions. Journal of Machine Learning Research, 10(10), 2009.
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do CIFAR-10 classifiers generalize to CIFAR-10? In arXiv: /806 100600051,, 2018
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do ImageNet elassifiers
generalize to ImageNet? In ICML, 2019.
Cedric Renggli, Luka Rimanic, Nora Hollenstein, and Ce Zhang. Evaluating Bayes error estimators on real-world datasets with FeeBee. In NeurlPS Datasets and Benchmarks track, 2021.
Rebecca Roclofs, Vaishaal Shankar, Benjamin Recht, Sara Fridovich-Koe Keil, Moritz Hardt, John Miller, and Ludwig Schmidt. A meta-analysis of overfitting in machine learning. In NeurIPS, 2019.
Tomoya Sakai, Marthinus Christoffel du Plessis, Gang Niu, and Masashi Sugiyama. Semi-supervised classification based on classification from positive and unlabeled data. In ICML, 2017.
Keiko Sasada, Noriko Yamamoto, Hiroki Masuda, Yoko Tanaka, Ayako Ishihara, Yasushi Takamatsu, Yutaka Yatomi, Waichiro Katsuda, Issei Sato, Hirotaka Matsui, and on behalf of the Kyushu regional department of the Japanese Society of Laboratory Hematology. Inter-observer variance and the need for standardization in the morphological classification of myelodysplastic syndrome. Leukemia Research, 69:54-59, 2018
Salimeh Yasaei Sekeh, Brandon Oselio, and Alfred O. Hero. Learning to bound the multi-class Bayes error. IEEE Transactions on Signal Processing, 68:3793 3807, 2020.
Vaishaal Shankar, Rebecca Roclofs, Horia Mania, Alex Fang, Benjamin Recht, and Ludwig Schmidt. Evaluating machine accuracy imagenet. In /CML, 2020.
Kazuhiko Shinoda, Hirotaka Kaji, and Masashi Sugiyama. Binary classification from positive data with skewed confidence. In IJCAI, 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In ICLR, 2015.
Masashi Sugiyama, Han Bao, Takashi Ishida, Nan Lu, Tomoya Sakai, and Gang Niu. Machine Learning from Weak Supervision: An Empirical Risk Minimization Approach. MIT Press, 2022.
Ryan Theisen, Huan Wang, Lav R. Varshney, Caiming Xiong, and Richard Socher. Evaluating state-of-the-art classification models against Bayes optimality. In NeurlPS, 2021.
Antonio Torralba, Rob Fergus, and William T. Freeman. 80 million tiny images: large dataset for non-parametric object and scene recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 30:1958-1970. 2008
Vladimir N. Vapnik. The nature of statistical learning theory. Springer, New York, USA, 2nd edition, 2000.
13

---

Published as a conference paper at ICLR 2023
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In NeurlPS, 2017.
Li Wan, Matthew Zeiler, Sixin Zhang, Yann Le Cun, and Rob Fergus. Regularization of neural networks using dropconnect. In ICML, 2013.
Jiaheng Wei, Zhaowei Zhu, Hao Cheng, Tongliang Liu, Gang Niu, and Yang Liu. Learning with noisy labels revisited: A study using real-world human annotations. In ICLR, 2022.
Roman Werpachowski. András György, and Csaba Szepesvári. Detecting overfitting via adversarial examples. In NewrIPS, 2019.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST:: a novel image dataset for bench- marking machine learning algorithms. arXiv preprint arXiv:/708.007:: 2017.
Chhavi Yadav and Léon Bottou. Cold case: The lost MNIST digits. In NeurlPS, 2019.
Sangdoo Yun, Seong Joon Oh, Byeongho Heo, Dongyoon Han, Junsuk Choe, and Sanghyuk Chun. Re-labeling imagenet: from single to multi-labels, from global to localized labels. In CVPR, 2021.
Chi-Hua22 Zhou. A brief introduction weakly supervised learning. National science review, 5(1): 44-53, 2018.
14

---

Published as a conference paper at ICLR 2023
A
SUMMARY OF THE PROPOSED METHODS
Our proposed method can be summarized into two steps as shown in the following table.
Table 2: A summary of our proposed methods.
Situation
Step I: collect data
Step estimate Bayes error
Clean soft labels
{qH==
3 = 1 E min (on - ci}
Uncertainty labels
{<))==
= Ein cj
Noisy soft labels
{(u,,8))) 8t)
Nosis = 1 n E - u² Ei u/
Multiple hard labels
{mr / for [r]
B = min
(ui, min(
ui} where ui
1/2 Σ, 1
Positive confidence
(r:)=1 and 4
Breont = # -1- m. EE= max (0,2 - 112 )
B RELATED WORK
Bayes error estimation has been topic of interest for nearly half a century (Fukunaga & Hostetler, 1975). Several works have derived upper and lower bounds of the Bayes error and proposed ways to estimate those bounds. Various f-divergences, such as the Bhattacharyya distance (Fukunaga, 1990) or the Henze-Penrose divergence (Berisha et al., 2016; Sekeh et al., 2020), were studied. Other approaches include Noshad et al. (2019), which directly estimated the Bayes error with -ddivergence representation instead of using bound, and Theisen et al. (2021), which computed the Bayes error of generative models learned using normalizing flows (Kingma & Dhariwal, 2018). Michelucci et al. (2021) proposed method to estimate the Bayes error and the best possible AUC for categorical features. More recently, Renggli et (2021) proposed a method to evaluate Bayes error estimators on real-world datasets, for which usually do not have access to the true Bayes error.
All of these works that estimate the Bayes error are based on instance-label pairs. Not only do they require instances, but they also usually have model, which may need careful tuning of hyperparameters to avoid overfitting. Li et al. (2021) proposed to estimate the maximal performance for regression problems, while we focus the classification problem.
Weakly supervised learning tries to learn with a weaker type of supervision, c.g., semi-supervised learning (Chapelle et al., 2006; Sakai et al., 2017), positive-unlabeled learning (du Plessis et al., 2014), -unibeledd learning (Bao et al., 201 8), unlabeled-uulabelldd learning (Lu et al., 2019), and others (Zhou, 2018; Sugiyama et al., 2022).
On the other hand, the focus of most previous works on estimating the Bayes error is on ordinary classification problems with full supervision. To our knowledge, Bayes error estimation for weakly supervised data has not been studied. We discussed how our formulation introduced in this paper is flexible and can be extended to weakly supervised learning in Sec. 4.
Overlitting to the test dataset is one of the issues that concerns the machine learning community al., 2019; Kiela et al., 2021). Models can overfit to the test
(Mania et al., 2019; Werpachowski dataset by training on the test set, explicitly or implicitly. Barz & Denzler (2020) reported that 3% of the test data in CIFAR-10 has duplicates and duplicatss in the training set. Lewis et (2020) studied popular open-domain question answering datasets and reported that 30% of test questions have a near-duplicate in the training data. These are examples of when we may explicitly train on the test set. Barz& & Denzler (2020) and Lewis et al. (2020) showed how removing the duplicates will lead to substantially worse results.
Overfitting to the test set can also happen implicitly because research is conducted on the same test data that is public for many years (often with a fixed train/test partition), in contrast to how engineers in industry can sample fresh unseen data for evaluation. Recht et al. (2018) constructed CIFAR- 10.1, an alternative unseen test set for CIFAR- 10 classifiers and showed how deep learning models became worse with respect to the test error, with 4% to 10% increase. Yadav & Bottou (2019) and Recht
15

---

Published as a conference paper at ICLR 2023
al. (2019) showed similar results for MNIST (LeCun al., 1998) and ImageNet (Deng al., 2009), respectively. With closer inspection, however, Recht et al. (2019) discussed how the accuracy improvement proportional to that in the original test set observed in the test set, for both CIFAR-10 and ImageNet. Roelofs et al. (2019) studied Kaggle competition datasets by comparing accuracies based public test set (which is used repeatedly by practitioners) and private test set (which is used to determine the final rankings), but found little evidence of overfitting.
Constructing new test datasets is one way to examine the degree of overfitting the test dataset. In Sec. 5, we discussed how estimating the Bayes error can be another way to detect overfitting to the test dataset. If models have lower test error than the estimated Bayes error, that is strong signal for this type of overfitting. We compared the test error of recent classifiers with the estimated Bayes error Sec.
C PROoFS
C.I PROOF OF PROPOSITION 3.1
Proof.
n
Him
sia p(x)
[3]
(1.12-1
ldd. p(x)
n
min {p(v +1|xx), 1|x,)|1
(9)
1
E
ppp(p) [min (ply 11xx)), 11/x;)11
(10)
B
(11)
1=1
B.
(12)
C.2 PROOF PROPOSITION 3.2
Proof. Since 0 min[p(y +1|2), -1/=)] < 0.5, the Hoeffding's inequality as follows:
2ne²
P([3 01 2 2xxp
2 exxp(=8ne"
(13)
(1)²
Therefore, for any > 0, with probability least
5, have,
B1 <
log
(14)
8n
16

---

Published as a conference paper at ICLR 2023
C.3
PROOF THAT 3 IS A BIASED ESTIMATOR
Proof.
E
[3] E
(a.s112 " p(ag) Σ
min {u;, 1 - ui
(15)
fei "i ple.))
E ((onki))p(ce)) [minfu;, u.}l
(16)
(nin(eerpleleellull - [
(17)
7
1
E expp() minf,,,1-a cil
(18)
71
1
E pp())( [min(p(y 1/x.), -1/4))1
(19)
1
3 3
(20)
n1
1=1
C.4 PROOF OF PROPOSITION 3.6
For simplicity, suppose that have labels for every sample i, and u, is the sample average of those labels:
U4
Ui.j = 1].
(21)
1=1
Since [ E
E [0, 1]. using Hoeffding's inequality, we get
Pr
U f1u - -cl 2 c) l
(22)
n
Pr[lu c: el cl]
(union bound)
(23)
2me²
< cxp
(-11- (1-0)²
(24)
cxp (-2mc").
(25)
for any e > 0. In other words, for any 8' > O, with probability at least 1 - 8', we have
2n
lm4 0sl <
log
c(8')
(26)
2m 8
for all i = 1.....n Note that
B = min (c, - c.}
(27)
(Blu ci), E[1 u; c|)
(28)
Simin(u,, 1 - w c]]
(29)
B c.]-
(30)
17

---

Published as a conference paper at ICLR 2023
The conditional bias can be bounded as
8
E
3
c:)
B.
min {us, 1 - ui) 1/ Ci
(31)
I2 [min
ci) min uz3 [c)]
(32)
71
Pr[lu; cal 2 c'(6') c c.IEmmmn (c, ci) minfu; u. ci | cal 2 c(6')]
71
(33)
1
Pr[lus- -al < <(())) 1100|cBB [/mimin of minfu,, u;} cs Lu - c:l < <((0))
11
1=1
(34)
Pr[lu c: 2 (()) c](112 0)
(35)
71
Pr|lu: al < <6'(6') c](min(e; 1 ai) min(c--e
-
(36)
s 8 + (8'),
(37)
where the last line follows from Eq. (26. Eq. (36 holds because min 1-4] e [0,1/2], min Ui 1
wi} E [0. 1/2], and Iu -| < (88) implies that u, > G; - e'(8') and 1 - u, 4 - (8)))
Further taking the expectation both sides, get bound the bias:
8 - E1 = EJB, B[ cill
(38)
5 + c((8')
(39)
2m 8
82 + |
log
(40)
2m
Setting to m 1/2 yields
=0
-(V
(V
log (2nm))
B E
+ +V
log(2n//m)
(41)
2/m
2m
C.5 PROOF PROPOSITION 3.4
Proof. &Noise can be expressed
NNoise (1[c 0.5] u.) + 1[c, 0.5]u.)
(42)
Recall that ii Gi + &.. Hence, we have
1
E. E[GNoisel
E
(one) tia m(n) [1c 0.5] -2)] (cne)) th mine) [1[e
[1 < 0.5)u.]
n
(43)
E
11 p(n5) [1[ 2 0.5)(1 c;) - E
(a,e,, 12 ((ns) [1[ 2 0.5|g]
+ E
(o))))) li4 p [1 < 0.5]cs] + E
(ore)))) ui m(ne) [1/G < 0.5]gl).
(44)
18

---

Published as a conference paper at ICLR 2023
The second term in Eq. (44) is,
/
E (an,Ei) the (ire)) (0[c 0.5]6:]
1/c 0.5) & p(a,, Ed)d,
(45)
2:2055 (fsw((iic))))) ) p(cs)de:
(46)
B[Elclo(c))d
(47)
0,20.55
(48)
Similarly, the fourth term in Eq. (44) becomes zero. Then,
E [
Barp(o) 11/ 2 0.5](1 - c2) + E Rerpte [1 < 0.5)al)
(49)
n Σ Ba(p(() [minfc,,1- c3]
(50)
Ee)p(e) [minfc, 1-c]
(51)
Ex)p()) [min(p(y 1(x),, p(y -1/=)]
(52)
B.
(53)
C.6 PROOF OF PROPOSITION 3.5
Proof. Broise can be expressed as
1 11
n1
NNoisc
bis
(54)
where
b; = 1/c 2 0.5] (1 - (1-u;) + 1[c < 0.5] u,.
(55)
Since derive that < 6, <
again the Hoeffding's inequality:
2ne2
P( - -B 2 e) < 2exp
(-11-0) 0)2 = 2 -eep (-2ne?)
(56)
Therefore, for any > 0, with probability least
5, we have,
2
18Noise .|5
log
(57)
2n
19

---

Published as a conference paper at ICLR 2023
C.7
PROOF OF THEOREM 4.1
Proof.
pp(z) (minfp(2) +1/=), 11/=)]
(58)
min(p(y = +1/=), p(u = - [x) (<=)dd
(59)
min(p(y = + [z). ply = 1 | ++p( y = +1)
dx
(60)
p = + +1
min mnly = +1 |az); ; 1 ply +1 |x)} T= ( +1)
(61)
p'y = +1
1 ply +1 (z) 1,
min
*+p(arly = +1)
(62)
plu = +1/
1, 1- r(x)
ग. E+
min
(63)
r(zz
( E+
- 2 111
min
0, r(x:)
(64)
C.8 PROOF OF PROPOSITION 4.2
Proof.
[ Ligh p1x [Pcnnt]]
= =T
T4
E++
max
0,2 r(x;;)
1
(65)
71
1=1
0,2 r(x)) 31)
E_
max
(66)
- }1
π
1+
E_
min
0, r(xx)
(67)
/ -1 1
π
1+
(68)
+
3
(69)
In the third equality, we used max(a, b) = min ( - - b}. In the fourth equality, we used which can be derived from Eq. (64).
E+ min
0, r(w) 2
C.9 PROOF OF PROPOSITION 4.3
We rewrite 3reant as
nh+
T - #4 max { {0.2
Seeont
0,2 r(x;)
(70)
n2+
1=1
Although 1/r(æ:) is not bounded, since S n - x max (0, r(m.))
_1
I T+, we can use the
Hoeffding's 's inequality derive,
-2ne?
P([]rroott - 3 2) < 2 2exp
(-#
(71)
m
Therefore, for any > with probability at least d we have,
13pcont - -B1 $
. log
2
(72)
2n 8'
20

---

Published as a conference paper at ICLR 2023
D STOCHASTIC BIG-O NOTATION
Suppose (X,) (n = ..)....) is a sequence of random variables and {a,) } (n = 1,2....) is a sequence of positive numbers, respectively. We say Xn Op(an) when for all > there exists C' E R and finite such that for all n > N, P( [x_l > C) <6
E
DATA COLLECTION
We chose the Fashion-MNIST dataset (Xiao et al., 2017) as a more challenging dataset. This is 10 class classification dataset with small fashion images with categories such dress, bag, and sneaker. We used Amazon Mechanical Turk (Buhrmester et al., 2016) to collect multiple annotations per each image in the test dataset with 10,000 images. We designed the task that the worker is instructed to annotate 10 randomly chosen fashion images, with a multiple choice of 10 labels. We showed several correct images for each categories in the beginning of the task, so that the worker can have good understanding of each labels. For each task with 10 image annotations, we paid $0.06 $0.08 to the worker. We removed the duplicates when the same worker provide label for the same image more than once. We further removed the annotation when the worker provided an answer within 30 seconds, which we considered as too short, e.g., when we performed the task, it took us 45 seconds when skipped reading the instructions. After removing the shorter ones, the mean and median answering time was about 147 and 78 seconds, respectively. Finally, we ended up with around 67 annotations per image. The least number was 53 and the largest number was 79 annotations. By following the naming convention of CIFAR-10H, we call this dataset as Fashion-MNIST-HH
F FULL RESULTS FOR SEC. 5.1 AND SEC. 5.2
In Sec. 5.1 and Sec. 5.2, we only showed two setups for each set of experiments. In this section, we show all four setups.
Prancerette Nenriiooe
Prepced reliee
Poperntiantial
Prese soe Hart booalee
Hore woateer auF courter
Nort rooollss cariii"
Herd chaatle--Ch dlaatier Sel roooli
Soft clsstarr sul
ze viz
12 5i2 Ioo
126
(a) Setup A
(b) Setup B
Setup C
Setup D
Figure 5: Comparison of the proposed method (blue) with the true Bayes error (black), recent Bayes error estimator "Ensemble" (orange) (Noshad al., 2019), and the test error of multilayer perceptron (hard labels: green, soft labels: purple). We also use the classifier's probabilistic output and plug it into the Bayes error equation Eq. (3), shown as "Classifier-BER (hard labels: red, soft labels: brown). The vertical/horizontal axis is the test error estimated Bayes error/# of training samples per class, respectively. Instance-free data was used for Bayes error estimation, while fully labelled data was used for training classifiers. We plot the mean and standard error for 10 trials.
"Other popular datasets such CIFAR-100 (Krizhevsky, 2009) and ImageNet (Deng et al., 2009) are problematic because they known be essentially multi-label classification datasets rather than single-label (Shankar al., 2020; Beyer al., 2020; Yun et al., 2021; Wei al.. 2022). Since the Bayes error defined for the single-labeled case, this means we have to define a similar but different and novel concept that corresponds to the lowest error for multi-label classification if we want to estimate the best possible performance on datasets such CIFAR- 100 and ImageNet. This is definitely interesting direction to pursue in the future, but is out of the scope of the current paper since we focusing the Bayes error.
21

---

Published as a conference paper at ICLR 2023
23
28
66-
12
16 256 512
38
14 DOe
Sctup A
(b) Setup
Sctup C
(d) Sctup D
Figure 6: Bayes error with and without noise on the labels, with mean and standard error for 10 trials. The vertical/horizontal axis the estimated Bayes error/the number of samples. With noisy labels, the estimation tends to become inaccurate with larger standard error. With more samples, the difference between clean labels becomes smaller, but small bias remains. With our modified estimator, the bias vanishes.
mise Giyas (eart!
assmated and Fiset
actrustd Riyss anc Hirr!
eltended PPreet
122
(a) Setup A
(b) Sctup B
(c) Sctup C
(d) Setup D
Figure 7: Estimated Bayes error with PN (positive and negative) and Pconf (positive-confidence) The vertical/horizontal axis is the estimated Bayes error/number of samples. We plot the mean and standard error for trials. The difference between the two becomes smaller as we increase the number of training samples.
0:30F
C-10F
C-19F
10.0
C-10F
Error (S)
C-10.1
C-10.1
10 Gror
6-10.1
C-10.1
Error
5.0
2,5
VGG11
RasNeSo
DunsoNele
Milin Tranffrma 8216
extinated Bayus stro 3
vGci1
ResNeso
DensoNe16
Vision Tranforma
estimated Bayes error
Voc1l
Bastaa00
DensoNette
0.0
V6G11
ResNe5o
DensoNet183
Vision Transforma
estimated Bayes oreor
(a) Setup A
(b) Setup B
(c) Setup
(d) Setup D
Figure 8: Comparing the estimated Bayes error with four classifiers and four setups (Figures 8a, 8b, 8c, and 8d). Although it seems that ViT B/16 has surpassed the Bayes error for all four setups for CIFAR-10 (C10), ciFAIR-10 (C10F), and CIFAR-10.1 (C10.1), it is still comparable or larger than the Bayes error for CIFAR- 10H (C10H). In Sec. 5.2, we discuss how this has to be investigated carefully. The black error bar for the Bayes error is the 95% confidence interval. The black error bar for the C10H is the standard error for sampling test labels 20 times.
22


Reviews:
[{"review_id": "frCQf6766eq", "reviewer": "Reviewer_Y3qe", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "To examine the intrinsic soundness of the classifier (maybe formulated as a deep neural network), this paper proposes a new method to estimate the limit Bayes error, where we just take the mean of the labels that show the uncertainty of the classes. The proposed method is claimed to be model-free and instance-free, and experimental results show its effectiveness. ", "summary_of_the_review": "Please see the above analysis. ", "strength_and_weaknesses": "Strengths: \n\n* This paper is well-written, and there are many mathematical formulations to formally illustrate the logic and soundness of the proposed method. \n* The experimental results seem promising. \n\nWeaknesses:\n\n* The proposed method seems simple. However, it is not clear in practice how a practitioner implements the whole method.\n\n* The method is supposed to be instance free. However, I still see that real instances would be desired in experiments.  ", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "M_k33N5ydwq", "reviewer": "Reviewer_bzQr", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a method of estimating the Bayes' error of a class of models for binary classification. They compare the estimation with datasets with multiple human annotated labels to compare the estimated Bayes error with an empirical estimate of the Bayes error. ", "summary_of_the_review": "Overall, I feel positive about the results presented in the text. I raised a number of points above, and I look forward to hearing the responses from the authors regarding the points raised. ", "strength_and_weaknesses": "## Strengths\n\n- The authors provide many rigorous proofs to support their claims. \n- The empirical results provide further support, showing bias where expected, etc. \n\n\n## Weaknesses\n\n- Theorem 2.2 is introduced from previous work without much context around why it is useful or important for this work. It would be helpful to the reader to provide some context of where and why it will come into play later in the text. \n\n- Until section 3, there is no mention of where the soft labels come from. It seems that the soft labels would have to be soft labels that are given from the true distribution of the data, which it seems would be impossible to attain in most realistic circumstances. Although, this is explained later, I think it would reduce reader confusion by at least alluding to this fact and that it will be dealt with later.\n\n- Section 3, paragraph 3: Why can uncertainty labels not recover $p(y = +1 | \\mathbf{x})$ from $\\min_{y \\in \\pm 1}p(y | \\mathbf{x})$? If one has access to one, doesn't it guarantee we know the other? If $\\min_{y \\in \\pm 1}p(y | \\mathbf{x}) = 0.1$, then isn't $p(y = +1 | \\mathbf{x}) = 0.9$ If this is a subtle misunderstanding about the meaning of soft labels and uncertainty labels introduced in Section 1, then I think there needs to be more time devoted to explaining those concepts in detail.\n\n- Theorem 3.3 seems to show that if one has a noisy corruption of the true class of an instance, then $\\hat{\\beta}$ is an unbiased estimate of the Bayes error. Later on in page 4, the authors state \"In practice, one idea is to ask many labellers for each instance and then use the histogram of the hard labels as a noisy soft label.\" Therefore wouldn't this just produce an unbiased estimate of the Bayes error of the aggregated labellers, which is not in fact an unbiased estimate of the true Bayes error? For example, the estimated Bayes error of a ResNet on CIFAR-10H is higher than that of the human annotated $\\hat{\\beta}$ in figure 4. This might be an obvious point, but I still think it should be stated clearly somewhere in the text.    \n\n- It would be interesting to see the other baseline performances on something other than the toy dataset. For example, ensembles tend to not show much diversity in decision boundaries when considering toy datasets, and therefore often do not outperform simple MLP baselines by much. This changes when the dimensionality of the data increases. It would therefore be interesting to see what happens with the Bayes error of an ensemble of at least one of the network baselines in figure 4.\n\n\n## Minor\n\n- Page 4: reference error, \"which we use later on in Sec. ??\"\n- Page 8: reference error, \"(App. ??)\"", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "FXB3gHX-m9S", "reviewer": "Reviewer_5ZHz", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "This paper proposes a simple estimator for Bayes error in binary classification. The authors are able to show several properties of the proposed estimator including unbiasedness and some convergence guarantee. Experiments on synthetic datasets, CIFAR-10, and Fashion-MNIST show the effectiveness of the proposed estimator. \n", "summary_of_the_review": "Overall I feel the work is an interesting try and it does show some promising preliminary results. But as I stated in the weakness section I do have some serious concerns. The assumption that p(y=+1|x_i) is known is so strong that the problem is not interesting any more in theory. In application, the work does not propose convincing ways of estimating p(y=+1|x_i) either. And the experiments are not extensive either. ", "strength_and_weaknesses": "Strength: The proposed estimator is simple to implement. Also it is nice that the authors show some guarantee of the proposed estimator.\n\n\nWeakness: I feel the proposed estimator does not really resolve the core of the Bayes error estimation. For the theory part of the paper, e.g., Theorem 4.1 and Proposition 4.2 and 4.3, the assumption is r_i= p(y=+1|x_i) is known. But to me this is actually the core and hard part of Bayes error estimation, since given r_i one can easily get the Bayes estimator. \n\n\nIn the empirical section of the paper, p(y=+1|x_i) is estimated using deep models, but as we all know from the uncertainty estimation literatures, deep models are not doing a good job calibrating their output scores to p(y=+1|x_i), and their outputs are usually highly screwed. As a result I am not quite sure how I should trust the estimated Bayes error.\n\n\nExperiments are also kind of lacking. I only see two real-world datasets used. To fully show empirically the proposed estimator work I would like to see more numbers on other datasets.\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": {}}, {"review_id": "Cf8M_xLTYrd", "reviewer": "Reviewer_YXWn", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an instance-free and model-free Bayes error estimation method for weakly supervised data. It leverages the fact that the expectation of the (perfect) predicted probability is the unbiased estimator of the Bayes error. Further, in a more practical and general case where the noises exist, the estimator is asymptotically unbiased. The authors also studied one case where only positive data and their confidence are available, and they show the error is also bounded. ", "summary_of_the_review": "The paper provides an interesting method for estimating the Bayes error that is conceptually simple but theroetically grounded. I believe it would be beneficial to the community and inspire future research.  ", "strength_and_weaknesses": "Strengths: \n- The concept is conceptually simple and well-motivated. \n- The presentation is clear overall. \n- The experiments involve ``real-world'' scenes which may bring practical interest\n- The proposed estimators works (except on ViT and some datasets) better than other trained models in estimating the Bayes error. \n\nQuestions:\n- Some reference are missing. For example, page 4 has a ''Sec. ??'' and page 8 has a ''App. ??''. \n- One paper [1] might be worthy to discuss (and maybe compare) but seems to be missing. It is also a model-agnostic algorithm for estimating the Bayes error, although they require the access to instances. \n- I might be wrong but since human labeler are also imperfect, why is it not possible that ViT can outperform human in providing reliable confidence? \n\n[1] A Model-Agnostic Algorithm for Bayes Error Determination in Binary Classification", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%