Label Correction of Crowdsourced Noisy Annotations with an Instance-Dependent Noise Transition Model
Authors: Hui Guo
Boyu Wang
Grace Yi
Venue: NeurIPS 2023 poster (2023)
Keywords: Noisy Label
Instance-Dependent Transition Matrix
Label Correction
Crowdsourcing
TL;DR: Label correction for crowdsourced noisy annotations using annotator-specific instance-dependent transition matrices

Abstract: The predictive ability of supervised learning algorithms hinges on the quality of annotated examples, whose labels often come from multiple crowdsourced annotators with diverse expertise. To aggregate noisy crowdsourced annotations, many existing methods employ an annotator-specific instance-independent noise transition matrix  to characterize the labeling skills of each annotator. Learning an instance-dependent noise transition model, however, is challenging and remains relatively less explored. To address this problem, in this paper, we formulate the noise transition model in a Bayesian framework and subsequently design a new label correction algorithm. Specifically, we approximate the instance-dependent noise transition matrices using a Bayesian network with a hierarchical spike and slab prior. To theoretically characterize the distance between the noise transition model and the true instance-dependent noise transition matrix, we provide a posterior-concentration theorem that ensures the posterior consistency in terms of the Hellinger distance. We further formulate the label correction process as a hypothesis testing problem and propose a novel algorithm to infer the true label from the noisy annotations based on the pairwise likelihood ratio test. Moreover, we establish an information-theoretic bound on the Bayes error for the proposed method. We validate the effectiveness of our approach through experiments on benchmark and real-world datasets.

Label Correction of Crowdsourced Noisy Annotations with an Instance-Dependent Noise Transition Model
Hui Guo
Boyu Wang
Department of Computer Science University Western Ontario hguo2888uwo.co
Department of Computer Science
University of Western Ontario bwang&csd, uwo.
Grace Y. Yi
Department of Statistical and Actuarial Sciences Department of Computer Science University of Western Ontario gy15@uwo.cm ca
Abstract
The predictive ability of supervised learning algorithms hinges on the quality of annotated examples, whose labels often come from multiple crowdsourced an- notators with diverse expertise. To aggregate noisy crowdsourced annotations, many existing methods employ an annotator-speciff instance- iettance-indepeneerr noise transition matrix characterize the labeling skills of each annotator. Learning an instance-dependen noise transition model, however, is challenging and remains relatively less explored. To address this problem, in this paper, we formulate the noise transition model in Bayesian framework and subsequently design a new label correction algorithm. Specifically, we approximate the instance-dependen noise transition matrices using Bayesian network with hierarchical spike and slab prior. To theoretically characterize the distance between the noise transi- tion model and the true instance-dependent noise transition matrix, we provide a cesterior-concetrraie of the Hellinger distance. We further formulate the label correction process as hypothesis testing problem and propose a novel algorithm to infer the true label from the noisy annotations based the pairwise likelihood ratio test. Moreover, we establish an information-thes theoretic bound on the Bayes error for the proposed method. We validate the effectiveness of our approach through experiments benchmark and real-world datasets.
theorem that ensures the posterior consistency in terms
1 Introduction
Deep neural networks (DNNs) have achieved remarkable performance in various tasks i 2] and they have proven be useful in handling sizable labeled data. Acquiring large accurately annotated datasets, however, is usually expensive and time consuming. To enhance the efficiency of annotation, many applications, crowdsourcing (3] employed as an alternative way for data labeling, where the labels are provided by multiple annotators with varying and imperfect labeling skills, and thus, the collected labels suffer from unavoidable noise. As deep models have a strong memorization power, using these noisy labels as the ground truth deteriorates the performance of DNNs 4 [] and most importantly, yields erroneous learning results. Further, potentially substantial disagreement among
"oorresponding authors.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the annotators for each instance presents extra challenges in the application of traditional supervised learning algorithms. Hence, the crowdsoureing scenario, to effectively train DNNs on noisy labeled datasets, a fundamental question is how to aggregate the noisy crowdsourced annotations and infer the latent true labels [
One naive approach to aggregate the crowdsourced labels is simply by computing the majority vote, which can be ineffective when the number of annotators is not large enough or the labeling task is Recent research has developed more powerful techniques for inferring the ground truth
difficult 7 g among which the annotator- -pecctifc noise transition matrix, aka annotator confusion, plays an important role by modeling the labeling process for each individual annotator. To estimate the transition matrix, available research [8] [3 usually makes the instance instance-independen assumption that for annotator r, given the true label y, the corruption process is independent of the input x, i.c.,
labels
((y(+) = 4ly = k,x) = (P(((r) = fly = k), where x denotes the random variable for instance/feature, f(r)) represents the noisy label given by annotator and y is the underlying ground truth label. This assumption, however, is often violated in applications. Instance-dependent annotation noise is more realistic and appropriate for real-world datasets, as suggested by the example that factors such as the quality of ultrasound images and the domain expertise of human annotators can greatly influence the actual diagnostic process in medical analysis [14 15). For annotator r, the transition matrix 7(*)(x)
is a matrix-valued function, with the (k, 1) element defined as Tel (x) (r)
P(y(*) = Bly = k; x). Unfortunately, the case of dnstnece-dependent annotation noise remains challenging and less explored. Most existing works considering instance-dependent noise are designed for the single annotator case [8 For the case with multiple annotators, existing methods investigate the human annotation process and use different models to estimate instance-dependent noise matrices. Approaches in B 22 use traditional classification models such as logistic regression, while others 23]
cater to large datasets and deep models. Methods in [ [9 (2] and [24] 25) are heuristic in nature and lack theoretical guarantees in estimating instance-depende
noise matrices. (23) makes some
theoretical progress in justifying the use of the trace regularisation, and extends the work of [8] which establishes the theory only for settings with an instance- instance-independen noise matrix. The theory in 23 is constrained to individual samples rather than the population setting. Importantly, the theoretical characterization of the distance of the noise model and the true annotator confusion remains absent from the literature.
In this paper, we address this notable problem by framing it within the Bayesian paradigm. We formulate the instance-dependent annotator-specifie label transition matrix, and further propose a novel algorithm to infer the underlying ground truth by aggregating the noisy annotations. To model the noise transition matrix, we invoke the Bayesian generalized linear mixed effects model (GLMM), which can be learned by deploying anchor points within the deep learning framework To facilitate the fact that the number of anchor points learned from the noisy training data is relatively small compared to the sample size, we employ a hierarchical spike and slab prior on the network parameters. This approach offers an interpretable mechanism for variable selection and allows us to establish the theoretical result within the deep learning setup. Our study reveals that the proposed noise transition model is close to the underlying true transition matrix with respect to the Hellinger distance in the Bayesian framework. Such a result is established for independently, nonidentically distributed (i.n.idd.) observations, substantially extending the existing sparse Bayesian theories within the deep learning paradigm. Further, we develop a label correction method using the pairwise likelihood ratio test to aggregate and infer the ground truth from the noisy crowdsourced annotations. This development is carried out by formulating the label correction process hypothesis testing problem and utilizing the proposed Bayesian model in place of the unknown transition matrix in the pairwise likelihood ratio test (LRT). More importantly, with the posterior consistency result, we also derive rnformatiiontthercee proposed algorithm even without access to the underlying true noise transition matrix.
11 26 27
bounds on the Bayes error for the
This research brings forth several noteworthy advancements: (1) We formulate the annotator-specific noise transition matrix in the Bayesian framework (Section B.T.. This method offers a practical and flexible framework to address real-world problems with noisy annotators. (2) We theoretically characterize the closeness of the proposed model and the underlying annotator confusions with respect the Hellinger distance. (Section 3.2). (3) We develop novel label correction algorithm by aggregating the noisy annotations using the pairwise likelihood ratio test, and identify information- theoretic bounds on the Bayes error (Section 3.3) The effectiveness of the proposed algorithm is

---

confirmed by the application to both synthetic and real-workds noisy datasets (Section 5 Code is available at htttpp///gghhoo.oom///o/////////
Problem Setup
Objective and Data. Consider a classification task with a feature space X C IP and a label space )' = [ where is the dimension of the features, K is the number of classes, and [k] represents {1...., }} for any positive integer k. Our goal is to develop a classifier h : X + V. which can accurately predict the true label for test instance. However, in applications, the true label y E y is often not observed for each input vector x E X. Instead, we receive set of noisy crowdsourced labels y = ( 5(()) } from R distinct annotators, where y(r) Y represents the label given by the rth annotator for E [R]. Thus, noisy dataset D of size N is defined as D {x,,y; (11) ,.",,; J==1+ where for each instance x,, the true label y; is unobserved. Under this setting, we aim to learn a reliable classifier h by utilizing the noisy crowdsourced dataset D.
( v.V
In practice, on commercial crowdsoureing platforms, large-scale labels can often be collected from independent human annotators. We thereby make common assumption that the R annotators | The conditional probability of the R noisy labels, given an
independently label the instances instance, can then be formulated as
12
R = II
P(y (.,)) = II (
(10)
I KEY
k(y)) = x()))
(I)
where for k E V. P(y = k|x), called the base model [28] denotes the conditional probability of the latent true label given x, which can be modeled by the output of a DNN parameterized by parameter vector, say 0; and (y = x, is the noise transition model for the rth annotator 8 satisfying Σ P(y(r) = 7/y = k. x) = for any x E X and k E [K. For ease of theoretical presentation, assume the accessibility to all the annotations from the R workers for now, and consider more general situations in the experimental part in Section extensions to accommodating the case where each instance only annotated by a subset of annotators are straightforward.
Notation.
this paper, sets are denoted by calligraphic upper case letters, and vectors and matrices denoted by bold lower and upper case letters, respectively. For vector u, Uy denote its jth element, and v denotes its transpose. For u = (V1, va) we denote ||v|l = (Σj= (0yl9)
for 9 > 0, || = max, luyl. and ||o||o = شØ= ((, * 0). with 1(-) denoting the indicator function. The Lg norm of a is also denoted by ||a|| for simplicity. For a matrix V, we use Vi, to represent its (i, element. Let (2,,,, (4) denote the measure space under consideration, where Ω is a set, 9 is the o-field of subsets of Ω and is the associated measure. For measurable function f + Rd, we write [Ifll, & [[ffllz((0) when there is no ambiguity of the domain, where
[[fllea())) = (Ja Σ lf)(z))d 1/v for q > 0. For two sequences, {a,} and {b,}, we write an 3 bn if there exists positive constant C' such that on S Cb,, for large enough n, and we write an x bn if a, = bn and b, I an.
3 Main Results
3.1 Instance-dependent transition matrix with multiple annotators
Annotator-specific instance-dependent noise transition model. Given an instance x, the condi- tional probability mass function of noisy annotations can be characterized by R instance-dependent matrices of dimension K x K, termed transition matrices or annotator confusions [8] [3]. with the kth row of the rth matrix denoted (P(ş(r) = 11y = k; x).... P(5(r)) = ly = k, x)). Thus, the distribution of noisy annotation depends on the instance in different ways due to the differences in the annotator and the underlying true label y. which can characterized by a Bayesian generalized linear mixed effects model (GLMM) [29] 30 in the deep learning framework.

---

Specifically, conditioned on the true label, y = k and the feature vector we treat the noisy label f(r)) from annotator r as a random variable generated from the distribution:
H = ki x} Cat(s)(k.r),
(2)
where s(kir) (a//kr) (har)) T sK-1 with Sk-1 {(8),..., 8K) RRK : 83 2 for [K] and ΣØ= 83 = 1 representing the (K - 1) dimeession simplex, and Cat(s(kr)) represents a categorical distribution specified by the parameter vector g( We extend existing works on mixed effects neural networks (MNN) [I 32 by employing two nonlinear transformations t/ and 1/2 to incorporate different effects in the mnstance-dependen noise transition model, and set
s (k.r) G(w/) with w ( A
(R) (x)).. 2s (x) + B
(3)
where A = (a a R and B (0 (x) T are the regression weights; 4/1 v1 (x) and (x) can be modeled by some suitable networks; and G is a function mapping IR K to S - which, in practice, is chosen to be the softmax function in the final layer. Utilizing two different network components 4/1 and 2/2 enables us to flexibly reflect possibly different effects of the annotator expertise (r) and the ground truth (k) in the annotation process, which can be interpreted as the input in mixed effects models.
Approximating the transition matrices. The proposed dependeede noise transition model can be learned by leveraging anchor points [22 26 27), or instances that are similar to anchor points learned from noisy training data 33 An instance x is defined to be an anchor point of class & if belongs the kth class almost surely, that is, Ply = k|x)
and hence, P(f(() [x) = PP = k, x). For & [K] let Do, be the set of anchor points of the ktth class and the associated noisy annotations, i.e., P
5x) IP(y; = k|x) 1}. Define Do Do U Do. U... U Do.k. and let n denote the subsample size of the learned anchor points, i.e., the cardinality of Do- Paired variables {x, 5r} in Du are independent, but not necessarily identically distributed (i.m.i.d). We write the input dimension p as pn from now on to emphasize that its dependence on n is allowed.
In applications, overfitting can occur when the subsample size of the learned anchor points is relatively small compared to the main sample size N. To address this issue, we propose to learn (x) with a sparse Bayesian DNN, denoted w/ (x; (63)), where ( represents the vector of all involved parameters in the network with j = 1, Furthermore, invoking the sparse Bayesian setting allows us to rigorously characterize the distance between the proposed model and the underlying true transition matrices, as presented in Theorem of Section 3.2
3.2 Bayesian analysis and posterior consistency result
Prior specification. To implement sparse Bayesian analysis, we utilize the spike and slab prior [3 on the network parameters, offering an interpretable mechanism for variable selection. The spike and slab model is formulated by constructing a prior hierarchy of the involved parameters and selects nonzero coefficients according to the posterior inclusion probability. Marginally, these priors are mutually independent and have mixture distribution consisting of flat distribution (slab) and distribution concentrated at zero (spike). Parameters with a small posterior mean will be set to zero to achieve sparsity.
Specifically, for network b (x: (x; 0(1)), ) we write ( as 060 ) with J, denoting the .T.))
....,
length of g for j = 1,2. For E [Jy], we treat o(6) as a random variable generated from the following prior hierarchy:
lk Bernouli()ns),
(
(4a)
(62 hi 7h
(1)
(1) (1) (o()) 2n) +1 - (1- (TO( ky)
(4b)
where ())
1) indicates whether not o(:) is nonzero, Cuj is specified as very small positive number, oñy and Enjony are the parameters related to the variances of distributions mi (-) and To()), respectively, and Any (0, 1) determines the ratio of the mixture distribution. As Cnj + 0.

---

To(Ok)) Cny becomes the degenerate distribution at zero The marginal distribution of 0 is then determined by
1 AnyTi 10k) + (1 Any)ro(Ok eng
(5)
which is presented as 7 (.) for short; and this is taken as the prior distribution of (()
To further incorporate the effects of the true label information and the randomness from different
annotators in (3. we place the following probabilistic structure on the generic weights for A,") and
B in
A (r) (ai K
(r)) and ((k) = (B) ..... 3 3k))
NOO, (r) and 3 N ! for j. 1 [K] and [R], where D and Σ
(6)
(k) nonnegative definite matrices. We use л (t)
and BB (-) to denote the prior distribution of (r) and (kk) in (6). Here the regression weights A (r)
and (*k) can be seen as fully connected layers on top of t/1 (x; ((1)) and (>; 0(2)), respectively.
The conditions on the aforementioned priors are given in Appendix A.3
Prior and posterior probability measure. Let 0 = (OCDT ((2) (TT ....... (K))
v (A),, (A T
E o stand for the vector of all involved parameters in the noise transition model, with @ denoting the parameter space. We use 0, to represent the true value of 0, which is an interior point of O. The foregoing specification of the prior distribution places prior probability measure, denoted [I(.), on O. With the data Do, the posterior probability measure II(-IDo) given by
P (Do) (o)() [I So PO (Do)dlI(()
for any G E G:
where G is the -iflldd on O and Pă is the joint probability density or mass function for the observations in Du under 0. Let Pn denote the probability measure associated with pp (-), and write IP (-) & Pe, (-). Hence, the data Dp is generated from (-) in our setup.
Let denote the unknown density of x. For {x, } E Do let (k.rr) and for respectively represent
the underlying true distributions for gi()) and ý, given {y = k, x}. determined by (2) and (3); and let ((hrr) and p(k) denote the corresponding distributions characterized by the model indexed by O. We
let a _ p(::) denote the probability density or mass function of the ith component in Do under 0, with k; [K] denoting the class that the instance belongs to almost surely. Then, the joint probability density or mass function p6 is calculated as pg I Po.i. The following theorem describes the closeness of the proposed noise transition model and the true annotator confusions with respect to the Hellinger distance within the Bayesian framework.
Theorem 1. Suppose Conditions A.1-A.4 in Appendix A.2 and B-I. in Appendix
A are satisfied. Let d(.,-) -) and (-, 'denote the Hellinger distance given in Definition I and the semimetric defined
in [6) in Appendix B. respectively. Then there exists sequence of constants {e2] n=1 with
< = =0 5
+ (a) and and|og( log(1 (1/22) (22)) - ne?, satisfying <
2 <1, fn - and ne. -> 00 as
+ co, such that
I E e (, > Man, +0
(8)
in P& probability for every M, co, where ( jmnn } is sequence of nonnegative numbers converging to 0 as n + Do for j = 1,2 as given in [4). and {Gx 120 is a sequence given in Appendix A.3
"The anchor point assumption can be relaxed and Theorem 1 can be extended to a more general setting. For any given 5 E (0. 1). we define the 6-pseudo anchor point for class k as P(y k/x) >
8 and denote D, d., 0,) > positive constant. From the modified
the of all 6-pseudo anchor point accordingly. Then, the following result holds: [I M,C.. + DD, + 0 P6 probability for every M., + co, where theory, as 5 approaches O slowly, the Hellinger distance of the transition model and the true transition probability converges to zero at slow rate. In other words, the transition model will still converge even if the collection of set of anchor points is not guaranteed, albeit slow rate.
5

---

depending on the structures of 1/1 (1(-1((1)) and 2)((1 with Sa + 0 as + cc. If we further assume that (Do |Pol > for some positive constant St, with representing the cardinality of a set, then for any k E [ and r E [R]
II T e :d a(serm) fohrr) Ma
in P6 probability for any M + co.
Intuitively, Theorem 1 reveals that the sparse noise transition model is close the underlying true transition matrix with respect to the Hellinger distance under mild conditions. Notably, our posterior consistency result extends the existing theories in sparse Bayesian learning (35/37] to the setup of i.n.id observations. Moreover, this result on the convergence rate of the posterior measure allows us infer the underlying true label from the noisy annotations with theoretical guarantee on the bounds of the Bayes error, which will be discussed in detail in the following section.
3.3 Pairwise likelihood ratio test for label correction
The asymptotic result (9) in Theorem | indicates that for each annotator, the underlying true instance- dependent transition matrix can be accurately modeled under the Bayesian framework. This enables us aggregate and infer the ground truth label from noisy crowdsourced annotations.
novel label correction algorithm. To highlight the idea, we first assume that the noise transition matrix P(y((r)l = k, x), or pk.r (.), is known. To simplify the notation, for each x; in the noisy dataset D, denote (r) A (r)
Tikki Tkl (x:) A PP(((r) Ily x.) for i [N] and k [K]. We assign class prior 38 h (hi,,, .... )T, for the ground truth label for the ith task, where the ha for A E [K] are nonnegative weights satisfying Σ Ri,A 1. For each instance, with the class prior and the noise transition matrices, the label correction process can be formulated as a hypothesis testing problem, where different hypotheses are generated from different choices of the true label values. Specifically, selecting the label for the instance x; from {g. g'), with 1 I g < g' S K, is equivalent to choosing from the competitors IP(ý/y 9. xs) and (ylyy = x;). We thereby consider the following hypothesis testing problem: Hg Vy, x:} ~ PPyly = 9, x;) versus Hg: Vyl x y g' x;). By the Peyman-PParsoo Lemma (39), the Bayes testing error is minimized by the likelihood ratio test, and the decision region for hypothesis H, is given by
I08 1(00==
K
(r) iigl
ÿ: Plyl g.x,)
hig
P P(yly = g', x:) ha.g r=
1(((r)
1=1
Building from the abovementioned reformulation of the label correction process, we now propose an algorithm to infer the underlying ground truth by aggregating noisy crowdsourced annotations with the help of the annotator confusions. Formally, we propose the following label correction method by
setting the estimated label of x; to be y. e g if
1(8 (()(==))
(r)
higg I
S for any g' + 9.
(10)
100 =1)
hi
I
K (r)
where Q 2 1 is a pre-specified threshold.
intommation-hhereete bounds the Bayes error. To theoretically justify the effectiveness of the proposed label correction method (TO), we derive information-theeretii bounds on the Bayes error, given the instances. Let D = / denote the collection of instances with estimated labels, where ń represents the size of D. We write y = { and the corresponding true label is denoted y {y. A loss measured by the accuracy of the estimated labels is given by f(y, y) Di 1(7 A yt). Let PP(-):: denote the joint probability distribution of (fx), given y and T, and let E(Ily:)) denote the associated expectation operator, where & {T. (+9))

---

[ represents the collection of the corresponding transition matrices T!" having (r) 12 as its
(k, element. Then, the Bayes risk is defined
40
Bayes (h, C) inf
Σ LEIK
(11)
Rnayes for short, where hyy) is the joint prior probability of calculated from h _ [h:]= The following theorem identifies bounds for the Bayes risk.
Theorem 2. Let DEL Tigg IT...) denote the Kullback- Leibler (KL) divergence for discrete distributions T Tige and T i. where, E [m], E [R], and g. g' E [K]. Tige and T T stand for the gth and g' rows of T respectively. For h |i and T = (T:))=n define
K R
(KL
hi DxL Fiigalt//o and
ñ
c 99'
min OSASI
R
1
Alog
Shhigg hs.g'
log
Egg
(n)
For E ñt and g E [K], bounded as follows:
11 (:), = ming' #9 9g"
Then the Bayes error defined in
is
D (ki(h,T) T) + log(2 II ma hs.
ñ
E log (maxke [K] h4,x) /
K
K
Rayys L)
higg exp -RI (h, T:)}
g=
Remark 1. Theorem 2 establishes information-theoredt bounds the Bayes error RBayes for arbitrary priors hd with E [7] which theoretically quantifies the combined impact of the prior knowledge and annotators' expertise on label accuracy using algorithm (1O). The lower bound is proved in light of Bayes lower bound based on Fano's inequality 43 44 The proof of the upper bound considers the inference procedure of y and applies Markov's 's inequality. The details are given in Appendix B
the concept of f-informativity 42), and is stronger than the commonly-use
Remark 2. The quantity (9 in E how the identified upper bound of the Bayes error may be influenced by the prior h; and the ability of the R annotators to distinguish between labels
g and g' for instance i. If we set h; to the uniform prior and let Ω 1, ((+) will degenerates to
"s'
the average of the Chernoff information between (7(r) 1 and {-! {T "igg 1 45 46), which is
i.g
statistical divergence measuring the deviation between two probability distributions.
Result under the sparse Bayesian model. The label correction method (0)) is not immediately applicable if we have no access to the underlying true annotator confusions, which is usually the case in real-world applications. To get around the issue induced from the unknownness of the true
noise transition probability fo ((k.r) we consider the model fl c(k.r) given in Theorem and write the
corresponding transition matrices Tikki -T (x.) é (k.r) ( (ūix+)) for k, [K] and E [R]
(r) (r)
We then replace the ((r) notation, we still use D ( Raayes denote the resulting Bayes error. We let Dx fx, lT represent the set of the considered instances. Combining Theorems [ the following corollary.
with =(.)) to determine corrected labels. With a slight abuse of 18
Tggl
to denote the set of instances with estimated labels but let
Corollary 3. Suppose that the conditions in Theorem are satisfied, and further assume that f(x.) > for x, Dx and min, 7(() S3. where f()) is the probability density
7

---

function of x, and and are some positive constants. Then, for any > 0.
K-1
(i) Bigg exp ( R1 (R,, Ti) (.):: + Do 1
0 R Bayes
7
g=1
in P probability as n oo, where 1/20) (N,, T() is given in Theorem Fori [r]] and g E [K].
4 Algorithm
Learning the noise transition model. In the warm-up stage, we train the base models on noisy training data and obtain the set of anchor points Do [26]. With Do, we first obtain the maximum a posteriori (MAP) estimate of network parameters of the transition model 0 by maximizing the log posterior distribution of 0, with the constant term omitted,
log Po, + log π ((()) }
f arg mAx
(12)
where po.: is the probability mass function of the ith component in Do given before Theorem and (0) the probability density function of relative to the prior probability measure II(.). Given the MAP estimate 0, according to the prior hierarchy (4). the posterior inclusion probability of the kth
parameter in the network 2/ (-; gb)) is calculated as
Ang TI (0()) () o2g))
P(yk)) = -
(13)
A1 1 (0()) + (1 (1- Anz (Ty)Tol To To(00) :ngo
for k [رر] with 1, If the posterior inclusion probability is smaller than pre-specified threshold, chosen to be 0.5 in our experiments, the associated parameter is zet to be zero. We then fine tune the sparse network and obtain the noise transition model.
Training the classifiers with corrected labels. With the noise transition model trained, we then train the base models with the label correction algorithm proposed in Section 3.3 Specifically, train two base classifiers to reciprocally provide class priors for each instance in the label correction process. In the tth epoch, for instance X, if y; satisfies the condition (IO) for the pre-specified threshold Sr we put {x, J&} in Dr. The base models are then updated on the collected dataset D.. The complete pseudocode of our algorithm is included in Appendix C
Experiments
Datasets. We assess the effectiveness of our method on three image datasets with synthetic annota- tions, MNIST [47, CIFAR-10 [48, and CIFAR-100 [48], and two datasets with human annotations, CIFAR-ION 49 and LabelMe [50 51). Detailed information can be found in Appendix C For all the datasets except LabelMe, we leave out 10% of the training data as noisy validation set.
Noise generation. For the three datasets, MNIST, CIFAR1O, and CIFAR 100, we consider three groups of annotators with varying expertise, with an average labeling error rate of about 20% 35% and 50%, respectively. We abbreviate these three groups IDN-LOW, IDN-MID, and IDN-HIGH, which represent instance-dependent annotators with low, middle ("mid" for short), and high labeling error rates, respectively. To generate noisy annotations, we independently simulate for each group according to Algorihtm 2 in 12). with IDN-T denoting that the noise rate is upper bounded by T for each annotator. For each instance, we then randomly choose one of the annotations given by the R annotators, which is designed to evaluate the methods under incomplete annotator labeling. We manually corrupt the three datasets according to the following three groups of annotators:
annotators
(I) IDN-LOW. IDN-10%, IDN-10%, IDN-20% IDN-20%, IDN:30%;
(II) IDN-MID. IDN-30% IDN-30%, IDN-40% IDN-40%, IDN-50%;
(III) IDN-HIGH. IDN-50%, IDN-50%, IDN-60%, IDN-60% IDN-70%
8

---

Experiment setup. The network structure for the MNIST dataset is chosen to be Lenet-5 [52]. We choose ResNet- 18 2 for CIFAR- 10 and CIFAR-ION, and ResNet-34 architecture for CIFAR-IO0
dataset. As in 53 we employ the pretrained VGG-16 network followed by fully connected layer and softmax output layer for the LabelMe dataset, using 50% dropout. More implementation details can be found in Appendix C
Competing methods. We compare the proposed method with the following state-of-an art methods:
(E) CE (Clean). which trains the network with the standard cross entopy loss on the clean datasets;
CE CE (MV), which trains the network using the labels from majority voting: (3) CE (EM) (9); (4)
DoctorNet [4 : (5) GCE 55 (6) Co-teaching [56]: (6) Co-teaching+ [ (7) BLTM [7]: (8)
MBEM I : (9) Crowd Layer (53: (10) TraceReg 8 : (11) Max-MIG 7 (12) CONAL 58 (13)
GeoCrowdNet (F) [3]; and (14) GeoCrowdNet (W) 133. Among these methods, GCE, Co-teaching,
Co-teaching+, and BLTM are strong baselines dealing with single noisy label issues, and we adapt
them to the multiple annotations setting by utilizing the majority vote labels for loss computation.
Ablation study. In Figure We plot the average estimation error for the noise transition matrices to demonstrate the effectiveness of the proposed method in modeling the instance-dependent annotator confusions. For instance x; with clean class label y; in the validation set, we analyse the y;th row rather than the whole noise transition matrix as in previous studies [16 12] Specifically, let 7(r) (x:)
and ,(*) (x,) represent the estimated and the true noise transition matrix for annotator r, respectively. The estimation error on instance x; is defined as err:" (1) = maxig (xir) - -(r) (x:)x.l.. where f(r) (x:)s., and (()())))):)))))) stand for the (y:, element in the corresponding matrices. The average estimation error for annotator is then calculated as 1 Σ err!") (r) with ny denoting the size of the validation set. For each annotator, we compare the average estimation error of the proposed method with six baselines, CrowdLayer [53]. TraceReg [8) GeoCrowdNet (F) [13], GeoCrowdNet (W) [33, MBEM [T], and BLTM [77, on the CIFAR dataset. In most of the cases, the proposed method leads to smaller estimation error especially when the noise rate is high, which shows the efficacy of the proposed sparse Bayesian model.
no
835
3
645
2125
6335
(35
832
0.8
Areobrr
Annoatar
Ameouaor
(a) IDN-LOW
(b) IDN-MID
(c) IDN-HIGH
Figure I: Average estimation error of annotator-specific instance-dependent noise transition matrices on CIFAR10. The error bar for standard deviation has been shaded.
125
775
758
Oben
TM
CAMA
Number Af
Mumroe Arritaions
Namber Geretatoo
(a) IDN-LOW
(b) IDN-MID
(c) IDN-HIGH
Figure 2: Average accuracy of learning CIFAR-10 dataset with varying number of annotators. The error bar for standard deviation has been shaded.

---

Table 1: Average accuracy of learning CIFAR-10, CIFAR-100 100, CIFAR-ION and LabelMe datasets
CIFAR-I0
CHEAR-100
CIFAR-ION 10N
LabelMe
IDN-LOW
IDN-MID
IDN-HIGH
IDN-LOW
IDN-MID
IDN-HIGH
CE (Clean)
88.60 88.60
58. 35.055
58.60
91.45g0..0
CE (MV)
s0.90
76.05
09. 69.65.1.7s
50.96
-4.80=0.9
38 08.51
82.822+0.0
79. 19.49+..c 00
CE (EM)
9
81.15
75.8420.97
69 69.85.1.43
51.2941.00
45.2420:41
38.011...0
38.01
80.6410.5 83.14.0..00
DoctorNet
S4
81.85.0.41 78.6910.75
76.2611.28
50
47.80=0.80
43.5010.58
84.52
79.09
GCF 65
82.78=0.51
78.06+1.18
72.99+1.92
55.88+1.32
48.46
40.53++..8
85.25
80. 80.27+0.27
Co-teaching
83.20+0.5a
80.50+0.77
82 82.02=0.42
63.27
47.58-0.45
45.49-0.72
85.90+0.50
80, 00.24+0.71
Co Co-teaching+
57
81 81.27
78, 26
72. 72.1020.98
53.31
48,
15.1550
42.07:10.06
82.31
81.6710.58
BLTM
17
81.06
70.64 07.34
52.21
46.90_0.55
41.2611.59
82.02
80.4411.05
MBEM [
82.37 78.05
71.43:2245
52.20.0.07
15.26=0.50
38.921a.09
85. 19.49
80.10+1.00
CrowdlLaeer
53
83.98 77.7611.00 o5
67. 67.7711.69
51.28g0.61
45.28_0.61
38.9310.7
52.8410.24
82, g0.
TraceRey
83.49
78.69
70.39
51.60
45.16_0.45
29.01
53.16.0.24
82.93
Max-MIG 2
81.00+0.72 75.90+0.52
70.96+0.96
51.76+1.11
44.93-0.71
38.70+0.4
85. 32
23.25+00.0
CoNAL
$1.00.0.a2 76.0220.79
09 10
51.61
44.19=0..2
$3.01.0.21 38 28.244
82.96.0.30
GeoCrowdNet (F) 13
86. 86.3610.00
83.7820.08
79.7010.42
51.37
45.04g0:56
38.9410.91
87.70.0.31
88. 17
GooCrowdNet (W)
$3.9520.41
72
06.48
51.5820.72
45.24=1.15
39.241o.76
87.84
83.28
Ours
86.88+0.65 85, 45.40 13.46
59.81 +0.65
54.88 40.60
49.44 30 88. 10.19 40.447 84.85+0.22
Classification accuracy. Table D presents the average test accuracy of 5 random trials on the datasets of CIFAR-10 10, CIFAR-100, CIFAR-ION and LabelMe, together with the standard errors of the test accuracies of the random trials, expressed after the plus/minus sign ł. where the two highest accuraries are bold faced; standard errors of the accuracies are calculated based on repeating those experiments 5 times, each with a different random seed. All the results demonstrate the superior performance of the proposed method on both synthetic and real-world noisy datasets. Moreover, to investigate the influence of the sparsity of annotations, we conduct more experiments with the number of annotators varying from 5 to 100, and each instance only has one label. Figure shows the average accuracy with various numbers of annotators, which further exhibit the advantages of the proposed method under different settings. Additional experimental results, including the test accuracy on MNIST, the average estimation error on MNIST and CIFAR 100, and the accuracy of the corrected labels using algorithm (10), deferred to Appendix to save space.
6 Conclusion
In this paper, we address the challenge of training classifiers using noisy crowdsourced labels, common issue in various applications. We formulate the annotator-specific iistance-dependen noise transition matrix within the Bayesian framework, and theoretically characterize the closeness of the proposed model and the true annotator confusions with respect to the Hellinger distance. Our result established for the setup of i.n.i.d. observations, which substantially broadens the application scope of our method. Building on the convergence rate of the posterior measure, we propose a novel algorithm to aggregate noisy annotations and infer the ground truth label based using pairwise LRT. Additionally, we provide information -thooretic bounds on the Bayes error of the proposed algorithm. Empirical evidence demonstrates the effectiveness of our algorithm on both synthetic and real-world noisy datasets.
Limitations and Extensions
Our work can be further extended in different directions. It is interesting to generalize the setup here to the hierarchical classification setup. Instance-dependent transition matrices can be further refined with varying structures imposed and are learned with manifold regularization.
Acknowledgements
Yi is the Canada Research Chair in Data Science (Tier 1). Her research was supported by the Canada Research Chairs Program and the Natural Sciences and Engineering Research Council of Canada (NSERC).
10

---

References
[1] Alex Krizhevsky, llya Sutskever, and Geoffrey B Hinton. Imagenet classification with deep convolutional neural networks. Communications of the ACM, 60(6):84-90, 2017.
[2] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition.
In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016.
[3] Yan Yan, Rómer Rosales, Glenn Fung, Ramanathan Subramanian, and Jennifer Dy. Learning from multiple annotators with varying expertise. Machine Learning. 95:291 1271111772200000 2014.
[4] Devansh Arpit, Stanislaw Jastrzębski. Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kan- wal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, et al. A closer look at memorization in deep networks. In International Conference on Machine Learning, 2017.
[5] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):007-115, 2021.
[6] James Surowiecki. The Wisdom of Crowds. Anchor, 2005.
[7] Peng Cao, Yilun Xu, Yuqing Kong, and Yizhou Wang. Max-mig: an information theoretic approach for joint learning from crowds. arXiv preprint arXiv: 1905::1905.143333 13436, 2019.
[8] Ryutaro Tanno, Ardavan Saeedi, Swami Sankaranarayanan, Daniel C. Alexander, and Nathan Silberman. Learning from noisy labels by regularized estimation annotator confusion. Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, 2019.
[9] Alexander Philip Dawid and Allan M Skene. Maximum likelihood estimation observer error-rates using the em algorithm. Journal of the Royal Statistical Society: Series C, 28(1)20 28, 1979.
[10] Jacob Whitehill, Ting-fan Wu, Jacob Bergsma, Javier Movellan, and Paul Ruvolo. Whose vote should count more: Optimal integration of labels from labelers of unknown expertise. Advances in Neural Information Processing Systems, 22, 2009.
[11] Ashish Khetan, Zachary Lipton, and Anima Anandkumar. Learning from noisy singly- data. arXiv preprint arXiv: arxiiv:/12..00 1712.04577 2017.
[12] Xiaoho Xia, Tongliang Liu, Nannan Wang, Bo Han, Chen Gong, Gang Niu, and Masashi Sugiyama. Are anchor points really indispensable in label-noise learning? Advances in Neural Information Processing Systems, 32, 2019.
[13] Shahana Ibrahim, Tri Nguyen, and Xiao Fu. Deep learning from crowdsourced labels: Coupled cross- entropy minimization, identifiability, and regularization. In The International Conference on Learning Representations, 2023.
[14] Andrew B Rosenkrantz, Ruth P Lim, Mershad Haghighi, Molly Somberg, James S Babb, and Samir Taneja. Comparison of interreader reproducibility of the prostate imaging reporting and data system and likert scales for evaluation of multiparametric prostate mri. American Journal of Roentgenology, 201(4): W618, 2013.
[15] Davood Karimi, Haoran Dou, Simon K Warfield, and Ali Gholipour. Deep learning with noisy labels: Exploring techniques and remedies in medical image analysis. Medical Image Analysis, 63:101759) 2020.
[16] Xiaobo Xia, Tongliang Liu, Bo Han, Nannan Wang, Mingming Gong, Haifeng Liu, Gang Niu, Dacheng Tao, and Masashi Sugiyama. Part-dependent label noise: Towards mnstanc-ddepndden label noise. Advances in Neural Information Processing Systems, 33:7597-7610 2020.
[17] Shuo Yang, Erkun Yang, Bo Han, Yang Liu, Min Xu, Gang Niu, and Tongliang Liu. Estimating instance- dependent bayes-label transition matrix using a deep neural network. In International Conference on Machine Learning, 2022.
[18] Le Zhang, Ryutaro Tanno, Mou-Cheng Xu, Chen Jin, Joseph Jacob, Olga Cicarrelli, Frederik Barkhof, and Daniel Alexander. Disentangling human error from ground truth in segmentation of medical images. Advances in Neural Information Processing Systems, 33:15750- 15762, 2020.
[19] Peter Welinder. Steve Branson, Pietro Perona, and Serge Belongie. The multidimensional wisdom of crowds. Advances in Neural Information Processing Systems, 23, 2010.
[20] Paul Ruvolo, Jacob Whitehill, and Javier R Movellan. Exploiting structure in crowdsourcing tasks via latent factor models. Citeseer, 2010.
11

---

[21] Yan Yan, Rómer Rosales, Glenn Fung. Mark Schmidt, Gerardo Hermosillo, Luca Bogoni. Linda Moy. and Jennifer Dy. Modeling annotator expertise: Learning when everybody knows bit of something. In Proceedings of the International Conference on Artificial Intelligence and Statistics, 2010.
[22] Wei Bi, Liwei Wang, James T Kwok, and Zhuowen Tu. Learning to predict from crowdsourced data. In The Conference on Uncertainty in Artificial Intelligence. 2014.
[23] Joseph Jacob, Olga Ciccarelli, Frederik Barkhof, and Daniel Alexander. Disentangling human error from the ground truth segmentation of medical images. In Advances in Neural Information Processing Systems, 2021.
[24] Zhenggi Gao. Fan-Keng Sun. Mingran Yang. Sucheng Ren, Zikai Xiong, Mare Engeler, Antonio Burazer, Linda Wildling, Luca Daniel, and Duane S Boning. Learning from multiple annotator noisy labels via sample-wise label fuusion. In European Conference on Computer Vision, 2022.
[25] Jingzheng Li, Hailong Sun, and Jiyi Li. Beyond confusion matrix: learning from multiple annotators with awareness of instance features. Machine Learning, 12(3):1053-100 1075, 2023.
[26] Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting. IEEE Transactions on Puttern Analysis and Machine Intelligence, 38(3):447-411, 2015.
[27] Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu Making deep neural networks robust to label noise: A loss correction approach. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, 2017.
[28] Hwanjun Song, Minseok Kim, Dongmin Park, Yooju Shin, and Jae-Gil Lee. Learning from noisy labels with deep neural networks: survey. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[29] Neal S Grantham, Yawen Guan, Brian J Reich, Elizabeth T Borer, and Kevin Gross. Mimix: A bayesian mixed-effects model for microbiome data from designed experiments. Journal of the American Statistical Association, (1555)))599-660, 2020.
[30] Wei Liu, Huazhen Lin. Shurong Zheng, and Jin Liu. Generalized factor model for ultra-high dimensional correlated variables with mixed types. Journal of the American Statistical Association, 118:1-17, 2021.
[31] Yunyang Xiong, Hyunwoo J Kim, and Vikas Singh. Mixed effects neural networks (menets) with applications to gaze estimation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019.
[32] Giora Simchoni and Saharon Rosset. Using random effects to account for high-cardinality categorical features and repeated measures in deep neural networks. Advances in Neural Information Processing Systems,
2021.
[33] Jiacheng Cheng. Tongliang Liu, Kotagiri Ramamohanarao, and Dacheng Tao. Learning with bounded instance and label-dependent label noise. In International Conference on Muchine Learning, 2020.
[34] Heraant Ishwaran and Sunil Rao. Spike and slab variable selection: frequentist and bayesian strategies. The Annals of Statistics, 33(2):30--73,, 2005.
[35] Yan Sun, Qifan Song, and Faming Liang. Consistent sparse deep lcarning: Theory and computation. Journal of the American Statistical Association, 1 117(540):--1,, 2021.
[36] Yuexi Wang and Veronika Rocková. Uncertainty quantification for sparse deep learning. In International Conference on Artificial Intelligence and Statistics, 2020.
[37] Yan Sun, Wenjun Xiong, and Faming Liang, Sparse deep learning: A new framework immune to local traps and miscalibration. Advances in Neural Information Processing Systems, 34:22301-22312, 2021.
[38] Shantamu Jain, Martha White, and Predrag Radivojac. Estimating the class prior and posterior from noisy positives and unlabeled data. Advances in neural information processing systems, 29, 2016.
[39] Jerzy Neyman and Egon Sharpe Pearson. On the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, 18996-776)) 1933.
[40] Xi Chen, Adityanand Guntuboyina, and Yuchen Zhang. On bayes risk lower bounds. The Journal of Machine Learning Researck, 17(1):6877-744, 2016.
[41] Imre Csiszár. A class of measures of informativity of observation channels. Periodica Mathematica Hungarica, 2(1-4):191-213 213,, 1972.
12

---

[42] Anuran Makur and Lizhong Zheng, Comparison of contraction coefficients for f-divergences. Problems of Information Transmission, 56:103-156, 2020.
[43] Hideaki Imamura, Issei Sato, and Masashi Sugiyama. Analysis of minimax error rate for crowdsourcing and its application to worker clustering model. In International Conference Machine Learning, 2018.
[44] Bin Yu. Festschrift for Lucien Le Cam, chapter 29. Springer, 1997.
[45] MTCAJ Thomas and A Thomas Joy. Elements of information theory. Wilcy- Wiley-Interscience, 2006.
[46] Chao Gao, Lu, and Dengyong Zhou. Exact exponent in optimal rates for crowdsourcing. In International Conference on Machine Learning, pages 603-611, PMLR, 2016.
[47] Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/nmist// 1998.
[48] Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
[49] 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 International Conference on Learning Representationss 2022.
[50] Filipe Rodrigues, Mariana Lourenco, Bernardete Ribeiro, and Francisco C Pereira. Learning supervised topic models for classification and regression from crowds. IEEE Transactions on Puttern Analysis and Machine Intelligence, 39(12):2409 2422, 2017.
[51] Antonio Torralba, Bryan C Russell, and Jenny Yuen. Labelme: Online image annotation and applications. Proceedings of the IEEE, 9868):1467-1484 2010.
[52] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 1):278--2224, 1998.
[53] Filipe Rodrigues and Francisco Pereira. Deep learning from crowds. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
[54] Melody Guan, Varun Gulshan, Andrew Dai, and Geoffrey Hinton. Who said what: Modeling individual labelers improves classification. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
[55] Zhilu Zhang and Mert Sabuncu. Generalized cross entropy loss for training deep neural networks with noisy labels. Advances in Neural Information Processing Systems, 31, 2018.
[56] Bo Han, Quamming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In Advances in Neural Information Processing Systems, 2018
[57] Xingrui Yu, Bo Han, Jiangehao Yao, Gang Niu. Ivor Tsang, and Masashi Sugiyama. How does disagreement help generalization against label corruption? In International Conference on Machine Learning, pages 7164-7173. PMLR, 2019.
[58] Zhendong Chu, Jing Ma, and Hongning Wang. Learning from crowds by modeling common confusions. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[59] Kolyan Ray, Botond Szabó, and Gabriel Clara. Spike and slab variational bayes for high dimensional logistic regression. Advances in Neural Information Processing Systems, 33:14423-14434, 2020.
[60] Wenxin Jiang, Bayesian variable selection for high dimensional generalized linear models: convergence rates of the fitted densities. The Annals of Statisticx, 35(4): 1581-1111 2007.
[61] Nicholas G Polson and Veronika Ročková. Posterior concentration for sparse deep learning. Advances in Neural Information Processing Systems, 31, 2018
[62] Song Han, Jeff Pool, John Tran, and William Dally, Learning both weights and connections for efficient neural network. Advances in Neural Information Processing Systems, 28, 2015.
[63] Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang. Model compression and acceleration for deep neural networks: The principles, progress, and challenges. IEEE Signal Processing Magazine. 3561)::26-136. 2018.
[64] Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. In International Conference Machine Learning, 2019.
13

---

[65] Philipp Petersen and Felix Voigtlaender. Optimal approximation of piecewise smooth functions using deep relu neural networks. Neural Networkx, 108:296-330, 2018.
[66] Helmut Boleskei, Philipp Grohs, Gitta Kutyniok, and Philipp Petersen. Optimal approximation with sparsely connected deep neural networks. SIAM Journal on Mathematics of Data Science, 1(1):8 45) 2019.
[67] Minerva Mukhopadhyay and David B Dunson. Targeted random projection for prediction from high- dimensional features. Journal the American Statistical Association, 115(532):1998-2011 2020.
[68] Michael R Sampford, Some inequalities on mill's ratio and related functions, The Annals of Mathmatical Statistics, 24(1):130-12, 1953.
[69] Rajarshi Guhaniyogi and David B Dunson. Bayesian compressed regression. Journal of the American Statistical Association, 110 12:00014400- 2015.
[70] Abdulhamid A Alzaid and Maha A Omair. On the poisson difference distribution inference and applications. Bulletin of the Malaysian Mathematical Sciences Society. Second Series, 33(1):17-45, 2010.
[71] C. M. Joshi and S. K. Bissu. Some inequalities of bessel and modified bessel functions. Journal of the Australian Mathematical Sociery, 50(2):333-342 1991.
[72] Martin J Wainwright. High-Dimensional Statistics: A Nom-Asymptotic Viewpoint. Cambridge University Press, 2019.
[73] Subhashis Ghosal and Aad Van Der Vaart. Convergence rates of posterior distributions for noniid observations. The Annals of Statistics, 1:192-223, 2007.
[74] Syed Mumtaz Ali and Samuel D Silvey. general class of coefficients of divergence of one distribution from another. Journal the Royal Statistical Society: Series B (Methodological), 28( 28(1):131-142, 1966.
[75] John Duchi. Information theory and statisties. Lecture Notes for Statistics, 311, 2019.
[76] Michael Short. Improved inequalities for the poisson and binomial distribution and upper tail quantile functions. International Scholarly Research Notices, 2013.
[77] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412. 6980, 2014.
14

---

Supplemental Materials
In the supplementary materials, we first summarize the regularity conditions on the underlying true model and prior distributions of the network parameters in Section [A] The proofs of Theorem []] Theorem 2 and Corollary 3 are provided in Sections B.2 B.4 with all the needed preliminaries presented in Section B.I Implementation details of the proposed method and additional experiment results are exhibited in Section C including the accuracy and number of selected labels using the proposed label correction algorithm (TO). the test accuracy on MNIST, the hyperparameter analysis on CIFARI00 100, the classification accuracy on CIFAR100 with varying number of annotators, and the average estimation error on CIFARIO and CIFAR 100 with varying number of annotators.
A Regularity Conditions
A.1 Network structure
To incorporate the sparse high dimensional setting [59,, we utilize sparse Bayesian DNNs to re- construct d/ (x) and (x) in (3) [37 60). Specifically, approximate , (x) with 1,2, consider a network with Hnj 1 hidden layers and a width vector D = (40)
()) 1(4 ...., Hon)",
where the width of the hihh layer is denoted ( for h O, Haj with (g) Pn for the input layer
and I ( A MG) for the output layer. Then the DNN with network architecture (Hnj. L() is the "Haj nonlinear function of the form:
(x; 060) w(i.aas (...0 (woik) (.. J + BGNN) + b.i.Hno),
where for h 1,.,. Haj. W(A)) L 1 weight matrix, b(.)) RR is the bias of layer h, (-) is nonlinear activation function, and gl1) represents the Jng X 1 vector formed from stacking (W(i,) b(i.) b Hay from bottom to the top, with Jns & E x *,,0 + 1.))
We treat weights and biases equally without distinguishing them in ((0) and write 0l0) O00) (0(3) "i,,....,/))) y() = ()) ....,,,9)) denote the indicator vector, with 7/ = 1(0 + 0)
for 1 Jnj. For ease of presentation, we use (x; 9())) and ab (x; p(i), ,())) exchangeably to represent the model for , (x). and let F, F(Hm1, Hn., L ( L
(2) C1 C2, e1) denote the space
of all sparse networks that satisfy Condition A.3 in Appendix A.2 and are constrained by positive constants Ct. C2 and E1.
To determine the parameters of the sparse DNNs (x; 000) r01 that best approximate why (x) for j = 1, 2. we define
(0)1)* 0000000 0(2)x (2)))
arg min (0(0),700 0000 _ je I1 (x):0(1) - Il (x:00))) (1t) (22x))))
{ + (14)
where for j = 2, Wny is an n-dependent positive constant satisfying Way 0 as + We call ( (1), g(2)* and (2) the true parameters of (()), (1), e and 22)) respectively.
A.2 Conditions for the sparse GLM
A.I The input vector is standardized so that x E Ω C [-1, where Q is the support of x, and the probability density f(-) of x satisfies that supxeq [f(x) < Co for some positive constant Co-
A.2 The activation function o--) is I-Lipschitz.
In this definition, the Toz norm of the network approximation error is bounded. Consider a measure space (2, G. ()) and 0 < p < < 2o, we have that I| < /((0))/>->//111/ I/ll using Hölder's inequality and therefore, || < || and L (22, R)) C L2 μ1) for probability measure Thus, the L, norm of the network approximation error also bounded, which will be used in the following proofs.
15

---

A.3 The true sparse DNN model satisfies the following conditions.
A.3.1 For j 1,2, let Tnj | denote the connectivity of y0o) let Inj maxighs L% denote the maximum layer width, and let 8nz represent the in- put dimension of y05) Let Sn { {rmm + (H, + log + (Fm1 (log Ln111 +log Ln2) + +8m1+882)) log Pm //. The true sparse DNN model satisfies that Sn S Cin for some constants C1 and 0 Ej
A.3.2 For j 1, ||00)|>> S Eng. where positive constant Eng S na for some constant
C2 > 0.
A.4 Write the function G(-) in
((())...GK((]] For E Ω2 r E [R] and k E [K]. write (R.r) = A (r) t/1 (x; ( + +B(h) 1/ 0(2).
A.4.1 For [K] and r E [R), in the neighbourhood Oo.
(G)(w)
Gj Gj(w((kr)) Gj Gy(w? (
sup ]
Our w=w(()))
C3 and sup jE(K]
-
for some constants C3 > 0 and 62 E (0, 1), where the latter requirement can be achieved if (ww))) > for some positive constant 0.
A.4.2 For [R] and j, [K], |1 (r) llo Fi and / ao F2, where F1 and F2 positive constants.
A.3
Conditions for the prior
B. For j = 2, assume each element of (05) has independent continuous prior distribution, de- noted (.). Thus, its minimum value the interval [-Eng Enj + exits, and let x ( denote it. For sequence positive constants r(5) with log T(5) Ollg n.), let Eng and 6n be two sequences of constants satisfying that 6nj < 1/nJnj (co 1((2) )
(n/ Hnj) Has and 6/, < 1//nJnj (Co Enn) Hnn (rnj/ Hnj) Hms for some constant Co > 1, respectively. Assume that:
B.1.1 log(1/Ig
(1)
O(Hlnj log log Lns);
B.1.2 Tg (1-8nj, 5ngl) 2
(5)
- 1 Jns cxp (()) {(Ha) + Haz) logn
+ log Lmi + log Luz + log }
for some constant s(1) > 2;
(5) (1-8ng, 8n Jng T
1
B.1.3 -log Jn (1) (10())))) 1 (2 + (5) 2 for some positive constant eg
B.2 For & E [K], let B (*) and B(k) denote the largest and the smallest eigenvalues of (k) re-
spectively, and for [R), let A and A(r) denote the largest and the smallest eigenvaluus of (rr) respectively. Assume that for large enough n,
B.2.1 T < S(t) (1)g and A Z (log -00-1 for some positive constants 5(1),
s and q1
B.2.2 D (M)
n < s (2) and ((*) 2 s/22 (log 12) for some positive constants 5(2)
S and 92!
(
A.4 Remark
Assumption A. specifies that the hypothesis set we consider class of DNNs, which is common setting in the literature [61 35
16

---

2. Assumption A.2 ensures that the underlying noise transition probability can be approximated by sparse model. Existing works 66 empirically show that large DNNs often contain large number of redundant parameters and propose methods for compressing neural networks without affecting performance. Moreover, theoretical works [65] [66] approximation theory provide theories that guarantee uniform approximation rates for broad family of function classes. Similar assumptions can be found [35 67
3. Assumption A.3 specifies the constraints
use. As in experiments in Section | we may employ the spike-and-slab prior X,,N(O,, ofx) + (1 (0, oin) for each element of the parameter vector ((3) of the sparse Bayesian DNN (x; 0 with j regression weights. It can be verified that Condition 1 in A.3 is satisfied if the values of An. dins and Un are properly chosen [35] In particular, the value of X, is related to the sparsity of the model and require it to satisfy that A,, (ng fn (Im Ln)))aa) for some positive constant e. and j = 1,2, which should be chosen by considering the network structure and the number of data points, n. Moreover, by using techniques such as Mill's ratio [68], Condition B.2 in A.3 is satisfied if c1 < On < C2 for some positive
the prior distribution
2: we take the normal prior (O ofi)) for each element of the
constants e and C2. which related to S(ú), s( -q and MD) for 1, in Condition B.2 60 67 Similar assumptions can be found in [60 35
B Proofs
In this section, present the proofs of Theorem Theorem 2 and Corollary 3 Specifically, we provide all the need preliminaries in Section [. where the definitions and results in Sections 1.I.I...1.. will be used in the proof of Theorem] [| and the information-theoretiios definitions and lemmas provided in Section B.1.5 will be utilized in the proof of Theorem 2 and Corollary 3
B.1 Preliminaries
B.1.1 Definitions of some discrepancy measures
Definition 1 (169) )) Let f and fo denote two conditional probability density/mass functions of y. given x. Let vn (dx) denote the probability measure for x associated with the density f(x) and
let 1/2 (dl = r= (d)((r)())) be a dominating measure for f and fo. and hence, dominating
measure of (x, y) taken as the product vn (2x)
(i) The Hellinger distance between f and fo is defined as
a(S.oo) = / J (VF (o))
iii For any t > 0, define
d(f, = { fo (2))))s (dx) -11
(iii) The Kullback- Leibler divergence between ff and fo is defined as
do(s, & K(S,So) / so log )
(iv) For g > 1, define
vg(J,fo) / fo log 6 {) (ddd))u (dx).
For q = 2, the index of ()) is omitted and the discrepancy measure is denoted V(..)).
60 shows that (1) d(f. s do fo): (2) (f. fo) decreases to do fo) as decreases to 0.
17

---

B.1.2 Mathematical details about the regression weights
Adapting the proof in 69, we prove the following proposition.
Proposition Assume that B3 ~ (o Ds), where D3 is a positive definite matrix. Then, for any
given dim x vector of functions (xx; 0) of and O, and for any constant A >> 0,
P (1((((x0)) (x; 0) 0ol }}
(x(x;
12 +
A
> 8cxp
2B
d x: 6) 12
0))x4))1
where B and are the largest and the smallest eigenvalues of Dg, respectively. Proof. The proof is established in two steps.
Step 1. We first prove that
P((((x;0) - -xxx0))))3(((000003 < P(X - 2),
(15)
A where X Pois( @1) and Y Pois()), with A (xx0)) and X {o(x:0)" 3.) and and are independent.
By the definition of the noncentral chi-squared distribution, it can be easily that T - (oxxx0""""<((00000 (²)2 is distributed according to the noncentral chi-squared distribution (A). (xx,0)DDa((xx0))
Thus, by utilizing the cumulative distribution function (CDF) of xf()), we obtain that P(](o(x;0)' o(x;)) < A}
[P A
+-2 (3)² Q(41; 22),
exp
j!
3=0
where Q(: 1()1)) is the CDF of xi+2)- the central chi-squared distribution with 2ÿ degrees of freedom.
Noting that Q(A 1 + 2j) > Q(4.; + 2j), by the result that Z51 + Zis+1 X2425 if Zji...., Z1,+1 Lid. x3 = )) we obtain that Q(Ar: 21) > P(Z,1 + ... + Zy,st1 < A.). According to the relationship between the Poisson counting process and exponential variables, have that the counting process with Zz1,-.. Zj.++1 1 as inter-arrival times is the Poisson process with rate 1 2- Let N(A1) denote the total number of occurrences or events that have happened up to d time A1. Then, N(A1) follows the Poisson distribution with parameter 2 i.e., N(Ai) = X, and {Zy + +... + Zz.+z < A = (N(() > j + 1}. Consequently, we have that
A1
(2) Q(A1; 25)
cxp 2) (2)' P(Zzi + Zjstt < AI)
exp
j!
1=0
1=U
exp
P(N(A,) >
(#)
Σ exp
P(X 2j+2]
j!
Σ P(Y j)p(X 2j+2)
P(X 2 +2,
1=0
= P(X- - -Y>2
18

---

where we use the distribution assumptions and the independence assumption for X and Y. Thus, 15 proved.
Step 2. Since X ~ Pois( + and Y Pois( $), and they are independent, have that X Y
follows the Poisson difference distribution (aka the Skellam distribution): for = 0, 11, =2,
A A 2
A A
P(X - Y Y k3 exp
I(VD,))
where 1z)2 = 2 m=u mil
(2/2)*+3m [v++++1] is the modified Bessel function of the first kind [70] Using the
fact that [=(2) > 2 (( 1) for [71] and plugging in A and X, we obtain that
A + A
P(X Y P(X Y 8exp
A
[Ø(x: 0)T B,) A²
A
-8 exp
200(;; DD
f)(x;0)" D D30(x: 0))²
[Ø(x; B,) A 2 0)1
A
28exp
11 0)1
where the last inequality follows from the fact that for symmetric matrix D, |up||u||= u Du Amaz (D) and |n|=| u" Du Amin (D), where Amaz (D) and Aman (D) represent the largest and the smallest eigenvalues of D, respectively. This completes the proof.
B.1.3 Mathematical details about the sparse Bayesian DNNs
Consider DNN with network architecture (H,, L), where H,, is the number of hidden layers, and L (Lo, II...., LH.)" J is the width vector with Lp Pn. for the input layer and LH., M for the output layer. For the corresponding indicator vector y and for h 1.... Hn, let rh denote the number of nonzero connections to the hth hidden layer which includes the bias for the hth hidden layer and the weights between the (h - 1)th and the /th layer, such that Σ rh = 1y/ Ta. For parameter vector 0, let On. (0, x) represent the output value of the jth node of the lihh hidden layer for = 1.... L/je-
Lemma (37 Lemma S1). Consider sparse DNN with parameter vector 0 (f1...., 0y) T with dimension the corresponding indicator vector and the network architecture as mentioned above. Suppose that Conditions A.1-A.2 Section A.2 are satisfied and 0 xo S E,, for a positive constant En. Then, for S h < Hn, the summation of the outputs of the hth layer is upper bounded by
I
On.
x) S E II Tk
Lemma (37) Lemma S2). Consider a sparse DNN @(0, x) with indicator vector 7 satisfying the conditions in Lemma | and DNN s(0, x) with 0 A. where A is defined as
A= (0 (01, (0.,... "TT TT 0, 0,| < 6n for j E y and 10, 0,1 82 for $ {}
for given 8, and 82 > 0. Then
H
max [|o(0.x) 6(0,x)l1 (in H. x
II Th
h=1
Hn
H
+ d2
Pn Ia +
Σ
Lu
II h=1
{EE,, + 61)r + T
P=1
B.1.4 useful lemma
Assume P,, is a sequence of sets of probability densities and P denotes the complement of P. for each Let e,, be sequence of positive numbers. An cover of P., with respect to (w..t.)
19

---

distance d is set (fi...,,kk Pn such that for each f E Pa. there exists j E f1..... k) such that d(f.fj) I Cn- The 6, coveriig number the cardinality of the smallest 6₁ -coerr [72]. Let (en, d) denote the ---ovriing number of Pr w.r.t. the distance d.
Consider vector of independently (not necessarily identically) distributed observations D where the ith component is generated from distribution Pe.. with the density pe,; relative to a o-finite measure V4 on (2,,4) for [n.], and 0 is the vector of parameters in the parameter space O We define Po to be the product measure i0 iee on the corresponding product measurable space We define the square of ( ).). Assume that D is generated from the true distribution Pe.. the semimetric d, in 73
(,) - - (Vpo.. /Poo..) dd
Σ
(16)
which can be seen as the average of the squares of the Hellinger distances. For e >> O, we define the e-neighborhood around O,:
1 7 Σ 0o,
s;; 1 n Σ Vi 0o) se -e. sej.
G (00.e) 6)
0
(17)
where K2 0o) = (F.....e....) and V.) = V(Po... Po..s). defined in Definition !
Let (I) denote the prior probability measure on 0, and let II(-IDD" represent the associated posterior measure given the data D For ease of exposition, we put (T())) for IT( E O*) }) for any O C θ The following lemma is modified from Theorem 4 in (73 and will be used in the proof of Theorem
Lemma 3. Suppose that for a sequence of sets O₂ C θ and for sequence of positive numbers
{en)==1 such that en - 0 as n > oc and ne,, bounded away from zero, the following conditions hold large enough n.
(a) SUPESen log (e/36,, 10 On (0,00) < <c), S ne
(b) (())),)) = o(expf (r n),,
(c) (OG; cn 2 exp(-rne.)
for some constant > 0. Then for any Mn > 0 Pa l1(e d0, 2 Mnen/D") + 0 as Mn + xo.
B.1.5 Useful information-thcorriiee definitions and lemmas
We give some useful iiformation-thhoreiiii definitions and lemmas in this subsection, which will be used in the proof of Theorem and Corollary
Lemma 4 (Log sum inequality, 45 For positive numbers, 01, On and b ..... bn
Σ a4 log
ag
log
bi
with equality if and only if by equals for = 1,..., 77.
Definition 2 (5). Let P' and Q be probability distributions on the set X, and let f R, - R Without loss of generality, assume that P and Q are absolutely continuous with respect to the base measure p. The f-divergence between / and Q is then defined
be convex function satisfying f(1)
(P([I) =- / a(x)s
p(x) du(x) + l'(o)) 0}
((x))
where p and q are the densitics of P and Q with respect to the measure μ4, respectively, and f(())
represents lim f
of Example 1. By taking different / functions, we provide some popular / /-divergences.
Kullback-Leibler (KL. divergence: taking f(t) = loo gives Dy(PIIQ) e DRa (PI()) =
f plog(p/g) /d), which is also denoted do (p, q) in Definition
20

---

The total variation distance: taking f(t) = 1 yields Dy(PIIQ) - || 1lv g/d scp PP(A) Q(A),, which is also denoted do(p, q) in Definition
1
The Hellinger distance: taking f(t) (vt 1)2 = -t 2 + leads the squared Hellinger distance D (Pl _ (2 f(v du,, which also denoted (p, q) in Definition
The x²-divergence: taking f(1) 1 - 1)² produces the d-vivergeecc D2(P)Q) & QP) 1/2 1)
Lemma 5 ((75)). For the quantities defined in Example
7 the following relationships hold:
(i) For the Hellinger distance,
-
(ii) Pinsker's 's inequality: for any distributions P and Q,
1 = (P((I)).. 1P-Q11 S
Definition 3 44 Let (Po E θ} be a family of probability measures on space X, indexed by 0 E θ and let w be probability measure on O. For each f satisfying the conditions in Definition 2 the f-informativity. (w, P), is defined as
[s(w,)) P) = inf / (PPP)(Q)))d))
where the infimum is taken over all possible probability measures Q on X. In particular, when ft) t log t. the f-informativity is equal to the mutual information and is denoted by [w, P).
For each satisfying the conditions in Definition 2 let Φ : [0, 1)2 IR be the function defined as follows: for a, b E [0, 1J2 o (a, b) is the f-divergence between the two probability measures P and Then, oy (a, b) has following expression:
Q on {0, }} given by P[1] = a and Q(1}
a bf ( +11 -1 (1-6) for b < 1; f(1 a) (20) (((a) + (x))
by(a,b)
(18)
for b 0;
for b = 1.
The following lemma implies monotonicity and convexity properties of øy by taking it univariate function with one argument of Φ, fixed at a given value.
Lemma 6 ((40). For each f satisfying the conditions in Definition 2 consider Φ defined in [8 Then
(a). for every fixed b > O, the map g(a): ( b) is non-increasinng for E |0, b] and g(a) is convex and continuous o;
(b). for every fixed a < 1, the map h(b) : b (a b) is non-decreasing for E [a,
Lemma 7 (440). Let P = (Po E θ} be a family of probability measures on a space X and let be probability measure O Suppose that the loss function L is zero-one valued. Define the Bayes error as RRaye(W) = inf Je EL d ((X))))))))) (d) with X - θ denoting a mapping from the sample space to the parameter space. For any f satisfying the conditions Definition 2 we have that
1, P) 2 ( (w), Ro).
where dy is given by (18,, and Ry is defined as Ry e infoge So C(O, adw(d
21

---

B.2 Proof of Theorem 1
We now establish the proof of Theorem by checking the three conditions in Lemmaaaetaallisteeee for the sparse Bayesian deep learning framework. We first provide a useful result on the discrepancy measures for generalized linear models in Section B.2.1 and then verify the three conditions in Sections B B.2.2 B.2.4 following the proof techniques in 37 67
B.2.1 Discrepancy measures for generalized linear models
Paired variables the of anchor points Do Do, U... U D k in Section 3.1 can be seen as independently (not necessarily identically) distributed, and we let D" denote Do the following derivations emphasize its dependence the sample size n. For (x, E Da, with k [K] write the rth element of y, y(0), in the I-of-K fashion, i.e., only the jth element is equal while others are all 0 if y(r) is the jthh class, and then, the conditional probability density/mass function of j(r) induced by 0 is given by
(g(0)) G (WWlkr)))))) -G1 (G (G (G.(( (wolt:))) go(1)
(19)
for E [10]. We denote the joint conditional probability density/mass function of y as f (F), given by
1 (5)
II fo (g0)),
(20)
and in contrast, we denote the underlying true conditional probability density/maas functions for 5i())
and y as (krrr and f( respectively.
Result 1. If Conditions A.4 in Section A.2 are satisfied, then, for any k E [K].
K(So² 100) CK Σ Ex w(kkr) w0 ( 112:
(21)
V(L( (( s Cv
Σ Ex Ex|lw((trr)
(22)
for some positive constants Cx and Cy in the neighbourhood 0
Proof. By Definition (iii) and (0) we have that
(k)
K(fe
(k)
/
(k)
log
22 (d5))s (db))
(k)
fo
(k.rr)
Σ
(k)
log
(2(d)) (dx)
(krrr
(k.r)
Σ
fo
(k.r)
log
fo (krr
U2 (dz(t) (dx).
'These two distances can also be upper bounded by the La norm of wa since the L1 norm and L equivalent _R in the sense that (wl2 [w)1 S vp/w12.
22

---

According to 19) and by taking the Taylor's expansion of log (10-)) at w w
we obtain that
(krr)
log
Jo f0 [(k.r))
12rr
(d))(1)
log sl dw
T (wolk.r) - w6(rr))) u2 (dz(r))
/ 5o p(l
=-
f fo p(hrr)
i Olog(G((u (F(n)
) (woltor) -w@t wfttr)) 12 (di(t))))
dw
f so kkr)
)G(()) (wo(tor) - -fftir)
12 (dg(())))
dw
where + = (W1, ..., wk) is between (kir) and (htrr) and
(G)
8Gx
TG((3)
(W)
(Gx(w))
d
aw
Ow
Ow
8G (
aGx 8ag
82k
Since 3((1) is discretely distributed, according to 19) and Condition 1.4.1, we further obtain that
fo (R.r)
/ 5o
(k.r))
log
22 (dz(())
10 (k.r)
Gy Gy(w!
(1r))
{ [OG](0)
} (w w!hh))
G5(w3)
dw
CaK
| (kir)
w/! (
62
Thus, the proof of inequality (1 is completed.
Similarly, write V(Soh)
:Jo as:
(k)
/ / ((())
( 16
log
12 (z
(k)
2
| (k)
log
12 (dd)
log
12,r (dy (1))"))))n (d)
f (krF1)) (k.r))
va.r (cg((12))
log
in
[
(
fo ((fora)
12.22 (1185122) es (dbx).
log
fo [lkirz]
where the second term can be upper bounded by
CaK 2
Σ
Ex| ((
w/t ((fkrr))) || (|
wf(trr))11 ||a,
11-0
and for the first term, we have
f 10 ((her)
f(tti))
2 }
k 22 (dg(t))
G,(w! {
G/(ww 2
()(w(()))) }
log
Σ
log
f ((krr)
j=1
23

---

If (wol)))) ( S (1 - w I11, we have that
{ log
G)(wp(rr) (tir))
Gz(wb(rr)
max{ - |ogg[1 + (2)اا||[(( w
||1
Cy(ws(kri))
according to Condition A.4.1. If (Wo > (| - w similar to the proof for (21). we obtain that
C,(wbhir)) 1og
Ci(w((-r) Gy(w((ir)))
2 }
=Gylub (()
} (w(l)r) w/t w
G2(w))
Gj(wo!r) (kir)
(Callu((t - w ( 2
(1 (2)
I C3
(wwlter) w (krr) ||1,
where is between w ((trr and (1tr)) Thus, the inequality (2 holds in the neighbourhood of Op-
B.2.2 Verification of Condition (c) in Lemma
Proof. For the sequence {cn, [_=] in Lemma 3 by 21 and (2) in Result I and (17p we obtain that
11( (n) 2 11 (0 Ex (x wh 1la S An for &s E [K], E [11]
where An, = e for some positive constant UI.
For simplicity of presentation, we now omit k and r in fo (((r)) (k..r) woth w(lkrr) B(k) and A (r)
in this proof here. Note that
w wulli [B'
T 1 (x; (()) + A 11 (x; 0 ((1)) BJ (22()) A 4/2 (x)]11
(x; ) B (2(x))) 1 + A
$1 (x: ( - A (2(x))12
B (x; 0(2)) BB (x 0 111 + [ the (x: 0(2)) By 2 0 (()))
B 1/2 (x; 0 e(2))) - B (x) + || (x ((1)) Ad (x: 0 (1))))1
+ ||A di (x; 00)) AT v/ (x; 0 (1 + ||A 1 (x; 0'0)-) A vi (x)]lI.
Corresponding each term above, we consider the following six terms:
(I) I1(0: Ex B (x; ((2) BJ v2 ((2) |/1 S A6/6];
(M: : F B the
( 212)) BJ (xx ((2))) ||1 S A,//6:
(II): Ex J
2/2
x ( BJ (x)))1 S A,/6];
(23)
01: E. | e (x: (1) ) AJ ( 0 (()))] S A,/6);
(II): 1T(0: E J 1hi (x; 0 - wix 00)))) S An/6):
(IIY: :1(0: : TE 1/ (x; 0 0))) A (x))l)) s sA./6).
Corresponding to ((k) for (6) we write (B, 3x) and Bg = (B 10 .... 3xu). Then for (I),
we have that
1 :
Ex
B
(x;
2i2 (x; ((2) - B (x; |1) ||| S 6m
K
-I(10UT
TDTT BTJT Σ
Ex13] ( (()) 30 12 (x: 0(2) S An
Ø=1
211(0 T. Ex13] 12 012) (x) 0 |ا
An
for j
1, 1,.., K
6K
[ ,TTTT E1I (2 0()) - (xx 0 2(1 <
A n
=
6K
24

---

where the last equality holds since all columns of B have independent and identical prior.
Taking A oR
US 6R
by Proposition
we have that for any given nonzero (/2(x; 0 ).
M₁ >
and M2 > 0,
B1 1/1 ()2(x; 2 - 1108/2(x: 2()) = A
2/22 (x;; 0 0(21)
Li (x: 0 1,00 1 A2
8A4
> exp
2B 1/2 1/2222 (x; (2))
B
(x: 0 2(2))|
F3 1/22 x; A )12 A
8A 4
cxp
Minc
2Mine S/²0 (log M(2) [x; 212
{s M (2
22 (x; 0 ((2)))
Mine (F2 1) log (2)
eexp
2M, S!²))
22 s(2) + 24p log M + 4 log (x; 0())
-og (85((88))))))
exp
2 for large enough n, where the second inequality follows from Condition A.4.2 in Section A.2
exp(-
and Condition B.2.2 in Section A.3 and the third inequality holds since A definition and 6, enough n and log (//1///xxx/ 21)) MMnne, where, according to Lemma [ the latter holds
6R Ui by
n + oc. The last inequality holds if 1og((1/5) (1/3) S .MMme for large
Hnz log Eng + log In2 H,,
< Mynez, which can be guaranteed by Condition A.3.1 in Section A.2
Since the result above holds for any given (x; 2 by summarizing the discussion above, we obtain that
An 4/2 ()2(x; ((3)) } K
(l) ス inf II 3,- Ex10] 1/2 (2 1 20)
BET
6K
2 (M + M.
Now consider the second term (II) in 23 which can be written
(II) (2
Ex B the (x: (2)) BJJ (x: ((2)* )|1 S An/6}
0 3
jo
2he
(x) (2) 3 1/ ((2))) S An/6
An
11
((2)
Ex 1/ (x: 0(2)
t/2 (x; 0 (2)
|||
5
6KF2
where the last inequality follows from Condition A.4.2 in Section A.2 Consider the set
(02) (0))) 10
062001 T/n for (2), 10 0.90111
1/. for $ (2),,
(24)
where 7/ and 2//2 will be specified later. Let rh. denote the number of nonzero connections to the ftt hidden layer which includes the bias for the hth hidden layer and the weights between the (h - 1)th
and the hth layer, such that Σ rh (2) 1|1 A r.2. Then, for any satisfying ||x||cc I 1,
1x; (2)) - -x: )11
Haa
Hwz
I (2)
Hn + mm ) 1 II
rh + Th
II
Enz + nn +
Tb
Th
h=1
h=1
ΣnH rr
Hi,2
Σnh Hnz
STnHnn Hna
+ Un Hn2
Hna
<2Ug22
25

---

where the first inequality follows from Lemma and the second and the third inequalities hold V/1 = U (/n2/ (Jn2(U2 (n=)))=((r22)) Hnz) }Bma for some constants U2 > 1 and Uz > 0. By taking small enough 33
we take ?n Uz
Mn (rnz/ H2z) Hn2
and
obtain that Ex (x 222(x; 0 ((()))l Il S GKFi for any oe2) E ( defined in 24 Then, it suffices to prove that II(((a) = 11()) (S(2)) 2 exp(-
A_
for some positive constant M3, where (-) is the prior measure of o as given in Section A.3
As defined in (5) in Section 3.2 each element of ((2) has an independent continuous prior, denoted T (.), and we use I to denote the minimal density value of me (+)(()) (-) on the interval E-E En2 1]. Then, we obtain that
(S(22)
II
TB (0 - -m = s 0 + nm)
II 5
To (0 - 1// =0f0 s =0 + t1mh))
jEy(2)-
2(2gg
(2)
mm
mm
vn
(2) (0) 1 nlll)) Jn2
and thus, according to Conditions B.1.1 1.1 and B. 1.2 in Section A.3
we have that
1
log (S((2) & n2
log
+ log
+ log
+ Jnz log
2
(2)
(2) (0 E El-nho Khrl)
Ig
S rn
constant + Hn log n + log Iina + log
+ log Hn2
Tn2 Hn2
Jn1 Jn2 -
+ Hnz log(U2En2)) + Hn2 log
+
Jnz log
x Tn2lllnn log Tm log Ln2,
where the last asymptotic equality follows from Condition A.3 in Section
A.2 and
the fact that log(1/c,) = Ologn). Thus, (II) 2 I(S()) 2 exp(-Mane.) holds
Hn logn n + Tne log I, & Unne, for some sufficiently small positive constant U4. Now we consider the third term in (23)
Ex BJ 1/2 (x; ((2))) BB (x))11 Σ Ex B 10 (x; (x(()))
K KF Uh (x: ())))) e2((x)
K KF2
where the second inequality follows from Condition A.4.2 in Section A.2 and the last inequality follows from the definition of the true model given in 14 Thus, we can take c, O(wnz) so that
(III) = 1 for large enough
Similar discussion can be applied (I),, (II) and (III) in 23 and we can obtain that
An
001) K
0' 2 inf II a1 ExlaT (x 0(1) I 0 (())) OeT
2b (x; (x:
6K
K(M + +M)nchh
(II) > (1) ) > expl-Mani
(II) ~ for large enough
where Mi Mr and M2 are constants, and ((1) can be similarly defined as 24h. Since the discussion above holds for any k E [K] and [R]. by choosing proper Mi, M2, Ma. Mi, M2 and My. Condition (c) of Lemma 3 can be verified.
26

---

B.2.3 Verification of Condition (a) in Lemma 3
Proof. Condition (a) in Lemma 3 can be verified if we can find a parameter set O C Q such that log N (en/36, Pn, dn) < ne", where P.. represents the set of all densities that can be represented by model in Section 3.1 with parameters in O,, Consider the following parameter space:
i = Sm1 @ Snz @ Bn @ An;
where
Sn1 10()) 10000 S (1 170 = =10 10 2 8.13 S kn1TnI, 11 lin I Kn iniki
Sn2 (0()) -0101 < 1 he (2) = =1( 10 2 8,23 S kn2 (2) lin S kn2
В₁ = [ (R) = (8) 1 .. 3k for k E [K] 1 - bn: for k E [K] and j E [M J]:
An = (A (5) = (a) ... K for r E [R] : 1
(r) S On. for r E [R], I E [K], and j E [M.
Here, 1/00 lin and (22) in denote the input dimensions of the sparse network structures % and 7 respectively, and r(a) 7(22, 8/1. 822, kaiS n/ra1), knz(5 n//r2), ( n//m1), 2, n n/),2) by and On are positive constants whose values will be described later.
The parameter space O can be covered by set of Loo balls of the form (ej Pr: Lj + Pm pn) where for the jth coordinate, 2 is the center which lies inside On, Pn is the radius, and Wn = Jnl + Jna + (1) + R(M(3) is the number of all involved parameters. It can be verified that the number of balls needed to cover the parameter space is upper bounded by
knarwa
(2) (P)(i)
Knn
Σ
(i)
x
Pm
Pr
1=1
(on + 1)
x22
(nn
+1)
RKa0()
Pn
Pr
KKn Knn Kns Kens
(25)
where for 1, x²) (i) denotes the number of all valid networks with exactly j connections and no more than Sni inputs.
Then we consider the number of d,, balls needed to cover the set of all densities, Pn- Consider
two parameters in ØN On A (0(!), 0(2)T B(1)T B(K)T A (1)T ,..., A (2) T) and 0, -
(o!!)T 0 B B ( (1)T A u (TRT)T which satisfy that
(i) there exists a network structure (1) such that [y(1) S knirmI, (1) S K2 8m1, 10%2
" S pm for j E (1)) o!!) S & and o!)) S 8%11 for j & (1);
(ii) there exists a network structure (2) such that (2) S kn27ne, (2) S Kn28n2, 10
8 ) s Pm for j E (2), l!2) < 8/22 and 0²2) s 8,22 for j & (2);
(iii) |3(0)) |(hi]] S Pn for k I E [K] and j E [M()]];
(iv) la (r) (r) < Pr for E [R]] E [K]. and E [M
( aptyl
where 8n1 and s,2 are defined in Condition A.3.1 in Appendix A.2, and Pn. is positive constant whose values will be discussed later.
Let Jo and (k)
(kk)
fe_ denote the corresponding densities in Pn. for k E []] By (21 in
Result and the fact that f2) < / VK(i,, f2) in Appendix B.I.I we obtain that dg (0.,, 0.) < max U (krr) ((krr) [|2 for some positive constant Us. where
(k.r) B
( 22 ) (T)T tb (x: ((!) and woth (k.r) (R)T (()x: (r)T (x: +A(1)
27

---

for k E [K] and r E [R] For ease of presentation, we omit & and r in B( B( A A! ".!! (k.r)
and (k,rr) and further obtain that
[ w < B 2/ ( B, (x (0) + | 21 (x:
A 1h 0
- B 22 (
B, (x ( (1 B 12
B 12 0 01 )|1
+ A 1 x: ())) - A 2 (x: 0 011] + || 2 (x: ) A 1/ (x: (x:
Σ
|B (1h (x: (x; 22 0 2 +
(B -Ba)) (x:
K
K
+
a a
1 (x; - 11 (x: 1) + Σ
((cui and (xx
1=1
< Kb, 1/ 12
( (x: 0(2) |11 K pm 1/ (x: 0!?
+ Ka 1/ (x; (()) 1 (x: 0 || + K pm 1/ (x; |!
where the preceding four boundness assumptions for 0,, and 0.. together with the definition of A.. and Bn, are used.
Similar to the proof in Appendix B.2.2 by using Lemmas and 2 we can further obtain that
dh ( 0,) - (s./36)2 if we choose Pnr 8n1 and 822 in the preceding derivations follows:
(i &, Uee/ bb, Jai (U 1
(1) Hma (km, (nIITnI Hhi for some constants Ug 0 and U >
(ii) 622 U / an n U41 (22) Haz (Knn2Tn2/ Hn, Haz for some constants Uz and U4 >
(ii) Pn. = min Us bb H (U%, (11) ) (k:11T11/ Hm1) Hmm) Hmo,
Us a Hn (U/ 11 ((2) Haz (hin2 Hng Haz
for some constants Ug.1, Us.2 > 0 and U/ U/22 1.
Thus, the log covering number of Pn, log /66n/36, Pn: dn), can be upper bounded by log Knn =
log Kn1 + log Knn + log Kn, + log with Kny given in 25) for 2, 4.
Considering the fact that log (") I log (A: ( Hhi S Kn S.1 log(pa) +
j jlog(k 811 + HnI 1 8n1 log(pn) + knirm log Hn (Kn) Inn) )) and by choosing log 1 O(log n)) log n((2) O(log n), an = /neg and bn x v neg we have that
log K..
(1())
< <log(kn1Fa)) + log x (kmiTTi) + FniFai log +
Pr
< (log(kniFa)) + Kn1 Sn1 log(p.) + knITni log Hn + 2kmIT log K 8n1 + Lni)
+ Kna constant + loog r(1) + log b, + log H,1 + Hn1 log(U?, + HA1 log(karFa//a Haa))
1
+ loga, + log Hn2 + Hng UU + Hn2 log(k H H22) ) + log 2
1 Sn1 log(pn) + knITnI O (Hm1 logn Hna logn + log Ln1 + log Lnz)
where the last equality holds since knITaI S n, hn2Tn2 I n, K 881 S n and 1 S n. By choosing Ky and 1n such that kn1771 (H,r log + Hnz logn + log Ina + log Lnz) x K418 I log(p.) ) = ne?, we have ne? = Ofrma Hm logn + raa H,z logn + raa log Ton trai log Lnd + 8.1 log(p.)}. By applying similar discussion on Kn2, log Kns and log Mnns. we further obtain that log (Pn,, en) log I nez, where the sequence
28

---

(erhn= satisfies that ne, = (f(r + (Ha + Hnz) logn n + (Tai + rn2) In1 + log Ln2)
+Sa1 + 5x2) log Pn
B.2.4 Verification of Condition (b) Lemma 3
Proof. Since (T)))) S (T(S + (2) + [T + IT(A))) we first examine (T(5)) and IT (AA)).
For any bn 0, by the prior assumption given in 66. have that
(T = II { B = (8 .k..,k%) for &s E [K] | I bn for 1, k E [K], and j E [M
[[ [8(1] bn)
K M
Σ
"B (1813) bm)
(1)
K M
K
B (10( > bn).
where a (.) denotes the measure induced by the prior distribution of (k) as defined in Section 3.2
Applying the bounds on the Mills ratio [76 for the standard normal distribution:
(-)(x)
2 + for -0 < x < 0o, where ((.) and yp(-) denote the CDF and probability density function (PDF) of the standard normal distribution, respectively, we further obtain that, by taking
bn = max
5B, ne?
2p /
Dan
"
(k) (18(N))
> bn)
exp
{
1
(b/////)))
/a/ V
(Ix(
)is
V 2/b2 (k))
(1) )5s
2
1
(b
/
}
5 ncn
exp
exp
2
1
where Aj represents the (j.j) clement of matrix A, the first step is due to the Mills ratio bounds, the second step comes from the definition of the PDF of the standard normal distribution, the third step is due the fact that the sum of the eigenvalues of matrix equals the trace of the matrix and the positivity of 1 (k:)
and the last step comes from the choice of bn- Therefore, it follows that ij
I(B)) < (2) exp(-xne") for large enough n..
Similarly, we can obtain that II(Ag) < (²M exp(=5nee) for large enough n by taking a, = m
5A" (r) nc?.
We then consider IT(S)) which can be upper bounded by
I((S)) < (I()()) U/ 0f01 > r(2) + (T(())) 1100=111 11;: 1000 2 8, H > knrra)
+ (0 1700 (1) Im K,, sn1)
-n ( (10( 1(("1) + P (Binomiaal(Jn kn1rn) (1)
(26)
vn) (1) ((Binomial(p..))
(0) (1- 1) + (Xp( Hn2) logn + log Ini log Lnd + logpn}
where Vn 1 T
according to Condition B.1 in Section A.3 For the first term in 266. we have that Jn1 (1) (10
1121) ex <s ) following Condition B.1.3 in Section A.3 where Eg 0
(k)
(k)
29

---

constant. The second term can be upper bounded by
P(Binomial(Ja:.2a Un) >> kn1
Ju
Jul
(1 - Vnn) Ma
j=kmimat+1
Jul
Ju 12 (1 Un) S Jnl (J) k
j=kni"ni+1
|S| ((2)) k Kni (Hn1 + Hn2) log + log Inj + log Lnz + log Pr.
Inn exp
<eep -56" ne
where the last inequality is due to the choice of 1, in Appendix B.2.3 and s(1) is a constant given in Condition 1.1.2 in Section A.3
Similarly, for the third term in (66 we have that
[(Binomial(paL)" vn) Sn15
(1)
P (0)
(PnL))
Σ
yull1 vn) vn)ant. 1.
j= #11+1
p)
=pr 1. (Jalun)) (aasa (ull jkass -v..) 11
Σ
Un,
Jn
Spat. (14 exp|
(1)
- -(()) Kni Snt { (Hm) + Hnz) log n + log Tun log Tenz log pm)
Jnl Pnl1 (2)
-k log
xcxpf-S ne
Thus, Condition (b) in Lemma B is verified.
B.3 Proof of Theorem 2
We now prove Theorem The proof of the upper bound adapts the techniques in [46. and the proof of the lower bound employs general mechanism for lower bounding the Bayes risk [40), which is tighter than the Fano's inequality 44
Proof. Upper Bound. The Bayes risk can be written as
Rayys
inf
Σ
My))((((,.))l::n
YE|K
inf
Σ My) Σ Ply # voly
7
yE[K]
inf y
M()) tylyttt
y
inf
h P(y, -
1=
30

---

We first consider the situation g 1:
K
P(y. + 11;;= S
Σ
p(y. - glyy
g'=2
For each g' 2 2, considering the inference procedure of yx. we have that PF = 9 Iy: = L;T)
Tor!"=
R K
hi.g
T
>
yy Yi = 1:7
hig1
72,1
hi.g'
A
R
K
3.9'l
(r)
=P
> 1 y, 1:T
1
1=1=1
7,,11
ATOy ( =!)
hi.g'
n
Figgl
min
E
Yi 1:T
X20
(r)
Ti.1!
ha.g''
K
(r) (ig'
A
(r) (1,11
1-1
min
X20
1
1=1
Sh higg'
R
K
S eexp
- R
min USAS1
R
x log
log
i.g
1.11
1=1
where the inequality in the third line follows from Markov's inequality. 1-A
Denote c( 9g'
-iinsssi 2/ -Xlog Wis he."" + + log |
(r)
(r)
{] and 1 (h., T:)
(i.l
(.gg')
ming+/g clO) we further obtain that
Ply: = lly = 1; S Sexp { (-CC }
Sexp
R min ((())
exp {-R1
Rl (Ai, (i).
s' 99'
Thus, obtain the upper bound of the Bayes risk: risk:
K
K
ha (l
R
Bayes
7
Lower Bound. Using Markov's inequality, we obtain that
Raayes = inf
Σ
My)
yE|KT
inf
Σ YE[K]"
M(y) 1 nt
((ix.)) > [ n
inf ñ y
Σ (
yE(K]A
inf n Y
Σ yE(Ki"
MyyE (1 + x
R. 7
31

---

where the second step is due to Markov's inequality. Using Lemma 7 we can obtain that
(, P) 2 Φy Ro),
where P is the set of distributions of { induced by y, and for 0-1 loss, Ro has the expression
[4] Rg = [ B((((a) with B(a) - (y E [K] 1(y + a) = 03. Then, it can be
easily verified that Ro 1 II maxke x] fu.
Let g()) = o5(4, Ro). which is, by Lemma 6 non-increasing for / E [0, RoJ. convex, and continuous in I. Using the convexity of g((), obtain that for every E (0, Ro]
Φ Ro) 2 (t, Ro) + (t Ro ( - t),
where (t Ro) denotes the left derivative of x + Φ5 Ro) at r = t. Then we can obtain that
Os,R Ro) (5 Ro)
(h, P) Ö5 Ro)
(y(tt.Ro)
(t- RR)
where the inequalities come from the fact that I(h, > Øy R. Ro) by Lemma 7 and that 6' (t=, RR) I
due to the non-increasing function g(t) over [0, Rol. By taking ft) = tlog t
and R. we obtain that R-
R21+ I(h, P) + loogll1 Ro)
log(1 Ro)
where [(h, P) is the mutual information of h and P.
Let Y and Z denote two independent random variables such that Y ~ h and Z ~ P, and let Dxz (-II.) denote the KL divergence of the associated distributions. For ease of notation, we use P(Y). P(Z), P(Y, and P(Z denote the h, P. the joint distribution of Y and Z, and the conditional distribution of 2, given Y. Then / (hi P) can be evaluated as follows 43):
I(h, P) I)
= Dxz ((X)))))))
P(Y)P(ZI))
E
P(Y)P(Z)X) log {
P(Y)P(Z)
YE[K]A,ZE(K|AR
Σ x))
YE[K]a
= Σ P)
Σ P(ZIY))P(Y'))
YE[K]
Y'E[K]
Using the log sum inequality in Lemma
we further obtain that
I(h,P) Σ P(Y) Σ PY")Duu(P(V))IP(ZY)
VE(K]
Y'ERR
Σ Σ P(Y)P(Y))
ΣΣ DR. (P(Z)) (PPXM)IP))))
VE[K]- Y'E(K]n
Σ
E
ΣΣ P(Y)P(Y')DKL (1)
YELK Y'E[K]"
R K
Σ
P(Y: = g) =g''
=
(11
R K
ΣΣΣΣ
hig Ri Dxz
A RD (h.T)
32

---

Combining the discussion above, we obtain that
Dx (h, r) + 1
x log(22 (2- I max [|] 1i.k)
R Bayes
Σ === logí maXNe[K] hi,x)) /
B.4 Proof of Corollary 3
Proof. For k E [K], [R], and consider the following set:
{ 0
5 - 0:
UkE(K))rE(RR) max
(F/ww())) f/hrm) (F(w Matn {E(K),xEDx
where 0, and M, satisfy the conditions in Theorem (R.r) and w/tm? (kir) depend and Dx represents the set of observations of the instances in D. Then, according to Theorem ] and using the union bound, we have that
/ (1/ - 16th ((hir)) (5lw@ Moen(Do }
II(S)))) <
Σ
oo:
0:
max
SEIK]
Σ
0 [1 -10 (0(kt)))l Ug Do)
kE[K]]rE[R]
Σ
(( d(f(kir), -5t 2n Do)
II
AE(R)
in Po probability distributions as defined Example and Ug is positive constant. Here, the second inequality is due to the definition of the total variation distance of discrete distributions and the fact that [(x > for
where || 1/rv denotes the total variation distance of the associated
x E Dx, and the third inequality follows the (i) in Lemma 5 Thus, ITS))o) - in Pù probability as n - 00, where can be written as
S s= 5-00
0:
max | (x) - (r) (x) S M.C., k E [K], r E [R] LE|R]XED=
We now consider the Bayes risk Rayess, which, according to the proof of Theorem can be written
as RByyes = infy { Ei= Egen PI, # gly. = g: r)) We first consider g = 1:
ply, * 1ly; = L:T)
K
Pl = o' ly: = L:T)
, -1)
hi.g'
Lig't
1 yi 1;T
g
16)
(r)
(r)
(r)
biig"
L.ght
5,11
i.g't
P
1
81
1:7
(r)
(r)
(r)
1=1
T.11
( O1KE()) S, using Taylor's expansion, we have that
1
K
(r)
Tight
log
(r)
1.17
Tigg
R
K
(n)
(r)
log
Light (r)
log
Tall
1 = & K.M.c.
(r)
(r)
kml
Tig''l
33

---

for some constant K > O and large enough n. For any > 0, we have that KMnen < by taking M c2(nm en). Thus, we further obtain that
16!
P(y; # 1ly, 1;7) -
Σ g'= =2
k
exp(c)
fus.o' Wii.
R
Light
> 1 ys = 1:
(r)
2,11
S (K 1) exp
{ (-R1 (hi, Ti) +
for (1)e))) E S, where in the second step, we use Markov's inequality and the definition of l2 T.). Similar results also hold for g 2, ..., K. Hence, according to Theorem that
we have
K-1
he RI (i,, Do 2 II(())o),
II T Bayes
7
9=1
where (I())Do) - 1 in Po probability as + co. Thus, the proof is completed.
C Implementation details and additional experimental results
C.1 Implementation details
Dataset description. We assess the effectiveness of our method on three image datasets with synthetic annotations, MNIST 47.. CIFAR-I0 48), and CIFAR-IO0 100 (48. and two datasets with human annotations, CIFAR-ION 49 and LabelMe [50 STI. MNIST consists of 28 x 28 grayscale images with 10 classes, containing 60,000 training images and 10,000 test images. CIFARIO has 10 classes of 32 x 32 3 color images, with 50,000 images used for training and 10,000 for testing. CIFAR100 also consists of 50,000 training images and 10,000 test images, whose size is 32 x 32 but with 100 fine-grained classes. We further consider two additional datasets with human annotations,
CIFAR- 1ON 44] and LabelMe [50 51). For each instance CIFAR 10, CIFAR- 1ON provides three independent human annotated noisy labels, with the aggregation of three noisy labels by majority voting being 9.03%. LabelMe an image classification dataset consists of 10,000 training images, 500 validation images, and 1,188 test images. For images in the training set, LabelMe has noisy and incomplete labels provided by a total R = 59 annotators, with each image being labeled by an average of 2.547 annotations. For all the datasets except LabelMe, we leave out 10% of the training data as a noisy validation set.
Experiment setup. The network structure for the MNIST dataset is chosen to be Lenet-5 [52]. We choose ResNet-18 [2] for CIFAR-10 and CIFAR-ION, and ResNet-34 architecture (2] for CIFAR- 100. As in [53] we employ the pretrained VGG-16 network, followed by a fully connected layer and a softmax output layer for the LabelMe dataset, using 50% dropout. We take the batch size to be 128 for all the datasets. For MNIST, we use the SGD optimizer with momentum 0.9, weight decay 5 x 10-4, and an initial learning rate of 10-2 The learning rate is divided by 10 at the 40th epoch, and we set 80 epochs in total, in which the first 20 epochs are used warm up the model on the noisy dataset and to determine anchor points. For CIFAR 10, CIFAR 100, CIFARION and LabelMe. the Adam optimizer 777 is utilized with the weight decay
10-4 For CIFARIO, CIFARI00 and CIFAR ION, the initial learning rate is set to be 10 3 and the network is trained for 120, 150, and 120 epochs for CIFAR1O. CIFAR and CIFARION, repectively, with the first 30 epochs used as the warm-up stage. The model is trained on LabelMe for 100 epochs, with an initial learning rate x 10-4 and first 20 epochs as the warm-up stage.
Baselines.
We compare the proposed method with the following state-of-ar art methods: (1) CE (Clean), which trains the network with the standard cross entopy loss on the clean datasets; (2) CE
(MV), which trains the network using the labels from majority voting; (3) CE (EM) 9. which obtains
the aggregated labels utilizing the EM algorithm; (4) DoctorNet [54], which models the annotators
individually and then learns averaging weights for combining them: (5) GCE (55), which generalizes
34

---

the mean absolute error and the cross entopy loss to combat errors in training labels; (6) Co-teaching
56
which trains two networks and cross-trains on instances with small loss values; (6) Co-teaching+
S7 which bridges the "Update by Disagreement" strategy with the Co-teaching method; (7) BLTTM
which directly models the transition matrix from Bayes optimal labels to noisy labels and learns classifier to predict Bayes optimal labels; (8) MBEM []]. which alternates in rounds between
estimating annotator quality from disagreement with the current model and updating the model by
optimizing the a loss function that accounts for the current estimate of worker quality; (9) CrowdLayer [53] which concatenates the classifier with multiple amnotator-speciffi layers and simultaneously learns the parameters; (10) TraceReg [8]. which uses loss function similar to CrowdLayer [53].
but adds a regularization to establish identifiability of the confusion matrices and the classifier; (11)
Max-MIG 77.. which jointly aggregates the noisy crowdsourced labels and trains the classifier; (12)
CoNAL 58,, which decomposes the annotation noise into common and individual confusions; (13)
regularized variants of the coupled cross-entropy minimization to enhance the identifiability of the confusion matrices. Among these methods, GCE and Co-teaching are strong baselines dealing with single noisy label issue, and we adapt them to the multiple annotations setting by utilizing the majority vote labels for loss computation.
GeoCrowdNet (F) (3); and (14) GeoCrowdNet (W) [3] which
Implementation details. We first warm up the base models on the noisy dataset with majority vote labels, obtain the set anchor points D. and train the sparse Bayesian model on Do by maximizing the log posterior distribution of network parameters and excluding non-informative parameters with low posterior inclusion probability. With the noise transition model trained, we then iteratively implement the label correction algorithm (1O) and update the base models, where linearly increase the threshold Ωt in the training process. Specifically, let ER denoted the estimated average noise rate, and let ro and ri represent two prespecified constants with rı 2 ro > O, which determine the magnitude of Q at the beginning and the end of the training process. In the /th epoch, we set the threshold 22 be Ω4 (1 (1-ER) ER) (ro + D in the experiment. The implementation procedure of the proposed method is summarized in Algorithm
Algorithm Annotator Speeciff Instance-Dependent Label Noise Learning via Sparse Bayesian Network and Pairwise LRT Input Noisy training data D &t)
1 // Warm Up the Base Models hı and 12;; Collect Anchor Points Do
P6
// Sections 3. and 3.2 Train Sparse Transition Matrices
3 Maximize the log posterior distribution 12) of network parameters and obtain the MAP 0:
Calculate the posterior inclusion probability P(yk)) (1) 1 using 13 P( = =1 < 0.5,
zero out the corresponding parameter:
5 Fine tune the sparse network and obtain the noise transition model f:
// Section 3.3 Pairwise Likelihood Ratio Test and Update the Base Models
7 for epoch t = =T,..... T do
Update the linearly increasing threshold Ω, for pairwise LRT; for each instance x; do
Use (xx, as the prior of x;; y, satisfies (10 with threshold 2,, put (x,,Ft) in D Use fx(x,) as the prior of x;; yf satisfies 10 with threshold 22, put [x,,5,) in D
10
11
12
end for
13
Update f1 using Dr2;
14
Update fa using D
15 end for
Output: :/1,, h2 and f.
35

---

C.2 Additional experimental results.
Accuracy and number of selected labels. To validate the effectiveness of the proposed label correction method, we plot the accuracy and the number of corrected labels using criterion (1O) in Figures and for all the considered datasets, where the solid line is the accuracy (left y-axis) and the dashed line is the number (right y-axis) of corrected labels.
1.000
Accuracy labels
53000
0.908
Num ber eeetee label
52000
51000
49000
48000
IDN-IIGGI: Accuracy
IDN-IIIGIT: Number
Accuracy
IDN-MID: Number
IDN-LOW: Accuracy
IDN-LOW: Number
46000
45000
10
20
Epoch
(a) MNIST
39000
Accuracy of selected labels
0.98
38000
0.96
33700
36000
0.94
35000
0.92
34000
33000
Number
0.90
IDN-HIGH: Accuracy
IDN-HIGH: Number
IDN-MID: Accuracy
IDN-MID: Number
0.88
IDN-LOW: Accuracy
IDN-LOW: Number
31000
20
40
30000
Epoch
(b) CIFARIO
0.95
44000
Accuracy of selected labels
0.90
42000
0.85
0.75
38000
0.70
36000
0.65
IDN-HIGHH: Accuracy
HIG-H: Number
34000
IDN-MID: Accuracy
IDN-MID: Number
IDN-LOW: Accurec
IDN-LOW: Number
0.58
40
100
120
30000
Epoch
(c) CIFAR100
Figure 3: The accuracy and the number of corrected labels using the label correction algorithm TO on synthetic noisy datasets. The eπror bar for standard deviation has been shaded.
36

---

Accorat selecee babelt
43000
ccrussy of selected Iabals
4400
2405
6.062
Numbber Selocted
4203
8-370
$1500
9306
6.865
0100
8100
IDN EIGEL Nocuncey EDN-FIGEE Namber
IDN JEGURAy
6.99
LDN HEGIE Number
Epoch
Epoch
(a) CIFARION
(b) LabelMe
Figure 4: The accuracy and the number of corrected labels using the label correction algorithm (10) on real-world noisy datasets. The error bar for standard deviation has been shaded.
Classification accuracy on MNIST. The test accuracy on CIFARIO. CIFARI00, CIFARIO, and LabelMe are provided in Section []] Here we present the average test accuracy on the MNIST dataset Table 2] where the two highest accuraries are bold faced. Clearly, that the proposed method achieves the best performance.
Table 2: Average accuracy of learning MNIST dataset
IDN-LOW IDN-MID IDN-HIGH
CE (Clean)
99.1420.10
CE (MV)
98.5920.13
97.97
96.60+0.32
CE (EM)
9
98.19
75.84
96.7840.52
DoctorNet
64
98.17
97.3610.23
95.3210.51
GCE 55
99.02=0.15
98,51+0.24
98.05+0.4r
Co-teaching 56
98.85_0.11
98.61
98 20
Co-teaching+ 57
98.33
97.67 20.44
BLTM 17
98.69 05.6992.00
98.1110.09
96.4010.81
MBEM 11
98.66 20.
98.24
4..464..21
Crowdl 53
97. 07.29
94.88
90.51
TraceReg
98.6820.05
97.9640.18
96.7040.57
Max-MIG
98.6220.06
97.97
96.4640.26
CoNAL 58
98. 98.6020.00
97.8910.06
96.0340.78
GeoCrowdNet (F) 13
98. 08.998
97.70+0.71
96.91
GcoCrowdNet (W)
13
97. 97.33-0.13
94.7440.67
90.7940.97
Ours
99.13
98 98.9810.1
98.80
Hyperparameter analysis the CIFAR100 dataset. We conduct sensitivity analyses about hyperparameters ro and rı on the CIFAR 100 dataset, where we choose ro from {3,5. 5, 10, 15, 20) and r from (200, 250, 300). As discussed in the implementation details in Section C. ro and ri determine the magnitude of the threshold Ω2 at the beginning and the end of the training process, respectively. With higher values of ro and rı, the accuracy of the corrected labels using algorithm (10) will increase accordingly, but the number of corrected labels will decrease. As shown in Table 3 with different choices of ru and ri, the proposed method consistently outperforms the compared methods.
Classification accuracy on CIFAR100 with varying number of annotators. Figure shows the average accuracy on CIFAR 100 with the number of annotators varying from 100, which further demonstrate the superiority of the proposed method under different settings.
37

---

Table 3: Average accuracy of learning the CIFARIO0 dataset with different hyperparameters.
IDN-LOW
IDN-MID
IDN-HIGH
To =
200
52.98 1.18
45.5011.30
P1
250
58.19_0.22
52.04_1.77
46.28
300
58. 58.16_0.57
53.03_n.82
45.48+1.97
5
Y1 200
59.01
52.75-1.a
45.76
r1
250
58.58
52.76-0.99
46.59+1.28
300 r1
59.34 52.88-1.04
47. 47.04
10
rı 200
53.23 59.39-u.44
47.10+1.78
F1
250
59. u9
47.27 53.74-u.54
T1
300
59.06-0.94 53.73_u.93
48.0941.47
Ygg
V1
200
59.43-u.56
51.46-0.337
17.40+1.22
T1
250
59.38-1.22
54.48_0.87
48. 48.59
300
59.36_0.33 54.93_0.63
48.2
No
20
ri
200
59.8 59.81_o.65
54.88_0.60
49 19.4441.30
250
59.38_0.66
55.48_0.75
19.39
r1
300
60.14_0.87
55. 55.10_0.88
49.07 +1.22
Booky
(a) IDN-LOW
(b) IDN-MID
(c) IDN-HIGH
Figure 5: Average accuracy of learning CIFAR- 100 dataset with varying number of annotators. The eтror bar for standard deviation has been shaded.
Average estimation error. For synthetic noisy datasets CIFARIO and CIFARI00, we compare the average estimation eтror of the proposed method with six competing methods, CrowdLayer [53] TraceReg [ GeoCrowdNet (F) [13] GeoCrowdNet (W) [B. MBEM [TT. and BLTM (17]. The definition of the average estimation error and the results on CIFAR1O with 5 annotators are given in the Ablation study of Section 5 In Figures 6 and [ we respectively present the average estimation eтrоr on the validation set of CTFAR10 and CIFART00 with varying numbers of annotators, where the results of CrowdLayer, TraceReg, GeoCrowdNet (F) and GeoCrowdNet (W) overlap in some subfigures of Figure 7 The proposed method outperforms all the compared methods with lower average estimation error for each annotator in most of the cases, further demonstrating the effectiveness of the proposed sparse Bayesian model.
38

---

1442
Orwlle
422
2REM
(a) IDN-LOW
(b) IDN-MID
(c) IDN HIGH
0,433
0.30
1.42
0/40
On Oredee
035
SEEM
(d) IDN-LOW
(e) IDN-MID
(f) IDN-HIGH
4.45
0.500
444
0.0%
3.35
3330
23
(g) IDN-LOW
(h) IDN-MID
ii) IDN-HIGH
4.45
0,500
0,315
225
IDN-LOW
(k) IDN-MID
(I) IDN-HIGH
0.500
GATS
6,75
6:31
122
(m) IDN-LOW
(n) IDN-MID
(0) IDN-HIGH
Figure 6: Average estimation error of annotator-specific mestance-dependent noise transition matrices on CIFAR10. From the first to the fifth row, the number of annotators is 5, 10, 30, 50 and 100 respectively. Standard emrors are represented by shaded regions.
39

---

RETM
PETM
(a) IDN-LOW
(b) IDN-MID
(c) IDN-HIGH
0.44
6.44
6.55
6.5
0.44
Anndator
Areosier
(d) IDN-LOW
(c) IDN-MID
(f) IDN-HIGH
6.44
Theling
RENU
6/6
PENM
(g) IDN-LOW
(h) IDN-MID
(i) IDN-HIGH
530
1.4
(10)
ii) IDN-LOW
(k) IDN-MID
(I) IDN-HIGH
3.5
37
2.6
Tauring
E41
6/66-
Ansdlata
(m) IDN-LOW
(n) IDN-MID
(0) IDN-HIGH
Figure 7: Average estimation error of annotator-ppecific instance-dependen noise transition matrices on CIFARIOG From the first to the fifth row, the number of annotators is 5, 10, 30, 50 and 100 respectively. Standard errors are represented by shaded regions.
40


Reviews:
[{"review_id": "lALtfV97uE", "reviewer": "Reviewer_i77Y", "summary": "This paper proposes a new method for label correction of crowdsourced data via an instance-dependent noise transition model. It parameterizes the instance-dependent noise transition matrices by a Bayesian network. A theoretical analysis that guarantees the posterior consistency of noise transition matrices is provided.   A new label correction way based on the instance-dependent noise transition matrices is also provided. Experiments show the proposed method can achieve better performance than some existing methods.", "questions": "See above.", "limitations": "The authors have discussed the limitations at the end of the main body, while I think the demand of a set of anchor points is difficult to meet in real-world scenes.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. Estimating the instance-dependent noise transition matrices for crowdsourcing is an important topic.\n2. This paper provides some theoretical analyses to understand and guarantee some useful properties of the proposed method.\n3. Experiments on synthetic and real crowdsourced datasets verified the effectiveness of the proposed methods.", "weaknesses": "1.  General instance-dependent noise matrix is not new for crowdsourcing. For example, several prior methods [1-5] have studied it in the early period. Recently, this topic receives more attention [6-8], due to the increasing demand for large-scale well-annotated datasets. I think the paper should include these background and existing works, and discuss the difference with them.\n\n2.  The conditions to guarantee the posterior consistency of the noise transition model seems very complex. How can we know such conditions are met in real scenes? Besides, since the anchor point assumption is strong in label-noise learning [9-11], the requirement of the proposed method that a set of anchor points can be used for training the noise transition model seems much more difficult.\n\n3.  The experiments are insufficient in terms of the following aspects: \n- The number of annotators is usually large, while the experiments on synthetic data only assume 5 annotators, which is not a typical setting. \n- Also due to the small number of annotators, the annotations are not sparse for each annotator as usual case.  \n- I suggest the authors compare the proposed method with some baselines that model instance-dependent noise matrices [6-8], and more truth inference baselines [12-14] to show its advantage more clearly.  \n- Since the experimental datasets are all image classification datasets, it would be better to do some experiments on the dataset from other modalities, e.g. Music dataset [15].\n\n4.  Lack of ablation discussion on label correction way. How to use noise transition for inferring clean labels has been explored in previous works [16,13], I think it is necessary to discuss and compare the proposed label correction way with the existing truth inference methods with noise transition matrix to when to use such label correction way.\n\n[1] The multidimensional wisdom of crowds. NeurIPS 2010\n\n[2] Exploiting structure in crowdsourcing tasks via latent factor models. Citeseer. 2010\n\n[3] Modeling annotator expertise: Learning when everybody knows a bit of something. AISTATS 2010\n\n[4] Learning from multiple annotators with varying expertise. MLJ 2014\n\n[5] Learning to Predict from Crowdsourced Data. UAI 2014\n\n[6] Disentangling human error from the ground truth in segmentation of medical images. NeurIPS 2020\n\n[7] Learning from Multiple Annotator Noisy Labels via Sample-wise Label Fusion. ECCV 2022\n\n[8] Beyond confusion matrix: learning from multiple annotators with awareness of instance features. MLJ 2023\n\n[9] Are Anchor Points Really Indispensable in Label-Noise Learning? NeurIPS 2019\n\n[10] Provably End-to-end Label-noise Learning without Anchor Points. ICML 2021\n\n[11] Estimating Noise Transition Matrix with Label Correlations for Noisy Multi-Label Learning. NeurIPS 2022\n\n[12] Bayesian classifier combination. AISTATS 2012\n\n[13] Learning from noisy singly-labeled data. ICLR 2018\n\n[14]  Exploiting worker correlation for label aggregation in crowdsourcing. ICML 2019\n\n[15] Gaussian process classification and active learning with multiple annotators. In ICML 2014\n\n[16] Maximum likelihood estimation of observer error-rates using the em algorithm. Journal of the Royal Statistical Society, 1979", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for providing such a comprehensive review. \n\n1.We appreciate your thoughtful remarks. We will include this background and an explanation of how our work differs from earlier works in our paper. Specifically, existing methods investigate the human annotation process and propose different models to estimate the instance-dependent noise matrix. [1-5] use traditional classification models such as logistic regression, and [6-8] are works in the context of large datasets and deep models. However, [1-5] and [7-8] are heuristic and lack theoretical guarantees in estimating instance-dependent noise matrix.  [6] makes some theoretical progress to justify the use of the trace regularisation, and extends the work of [A] in the case of instance-independent noise matrix. However, the theory in [6] only holds for individual samples, rather than the population setting.  In contrast to existing papers, our work first theoretically characterizes the distance between the noise transition model and the true instance-dependent noise transition matrix, which largely complements the theoretical gaps in the consistency of the noise transition model. Moreover, based on the posterior consistency result, we propose an algorithm to infer the true label utilizing the noise transition model. \n\n2.Thank you for your comments. We will add remarks on these conditions for clarifications in our paper. Specifically, the conditions to guarantee the posterior consistency can be roughly categorized into the three parts. \n\n(1) Part 1: the hypothesis set we consider is a class of DNNs. \n\n(2) Part 2: the underlying noise transition probability can be approximated by a sparse model.\n\n(3) Part 3: the prior we use should satisfy some conditions. \n\nThe condition (1) is a general setting in literature. Below we illustrate how conditions (2) and (3) are met in real scenes.\n\nRegarding (2), existing works [B-D] empirically show that large DNNs contain a large number of redundant parameters and propose various methods on compressing neural networks without impacting performance. Moreover, theoretical works [E-G] in approximation theory establish theories guaranteeing uniform approximation rates for a broad family of function classes.\n\nConcerning (3) we can consider the prior $\\theta\\sim \\lambda_n N(0, \\sigma^2_{1n})+(1-\\lambda_n)N(0, \\sigma^2_{0n})$ for each parameter $\\theta$ in the training process. By using techniques such as Mill's ratio, we prove that this prior satisfies the conditions in  Appendix A.3 if the values of $\\lambda_n$ and $\\sigma_{0n}$ are small enough and $\\sigma_{1n}$ is taken a proper value.\n\nThe anchor point assumption is used in our paper for theoretical consideration, which, however,  can be relaxed to be the existence of a set of points belonging to the $k$th class with high probability (denoted $1-\\delta_n$) for $k\\in[K]$. We prove that a similar result to Theorem 1 still holds, with the distance $d_n$ multiplied by a term related to $1-\\delta_n$. Moreover, we add an additional baseline method VolMinNet[10] which does not exploit anchor points and present the result in Table 3. We observe that our approach still outperform this baseline, which further verifies the effectiveness of the proposed method.\n\n3.We take your suggestions and run additional experimentals. The results can be found in the attached PDF. \n\n(1) \\& (2)  We now consider different settings on the CIFAR10 dataset with the number of annotators set to 10, 20, and 30, respectively. To evaluate the methods under incomplete labeling, for each data item, we consider the case where an annotator labels it with probability $p=0.2$. The performance of the proposed method under different settings can be found in Table 4 and Figure 2. Due to the time constraint, we have not obtained all results yet; we are still running some experiments. In the subsequent discussion period, we will give the results of the experiments with varying values of $p$.\n\n(3) The experimental results with additional baselines Multi-AnT[7] and MBEM [13] are shown in Table 3.\n\n(4) We now present the results on the MUSIC dataset in Table 2.\n\n4.Thanks for your insightful comments and we will add this part in the related work of our paper. The EM[16] and MBEM[13] methods are proposed under the instance-independent transition matrix setting, while our method is developed in the instance-dependent case. In the process of truth inference, we all need to utilize the transition matrix, but the difference is that the EM and MBEM methods directly select the inferred label as the label value corresponding to the maximum label posterior distribution. Our method, however, conduct the pairwise likelihood ratio test between different label values and we select only labels with the likelihood ratio greater than a pre-specified threshold to train the classifier, thus greatly increasing the accuracy of the inferred labels. The efficiency of the proposed approach is further confirmed by the performance comparison with the EM and MBEM methods, as shown in Table 3.\n\n**References**\n\n[A] Learning from noisy labels by regularized estimation of annotator confusion. CVPR, 2019.\n\n[B] Optimal approximation with sparsely connected deep neural networks. SIAM Journal on Mathematics of Data Science, 2019.\n\n[C] Learning both weights and connections for efficient neural network. NeurIPS, 2015.\n\n[D] Model compression and acceleration for deep neural networks: The principles, progress, and challenges. IEEE Signal Processing Magazine, 2018.\n\n[E] Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. ICML, 2019.\n\n[F] Optimal approximation with sparsely connected deep neural networks. SIAM Journal on Mathematics of Data Science, 2019\n\n[G] Optimal approximation of piecewise smooth functions using deep ReLU neural networks. Neural Networks, 2018.\n\n\n\n"}, {"review_id": "SjGBIwkphb", "reviewer": "Reviewer_PGxM", "summary": "This paper focuses on the problem of estimating annotator-specific instance-dependent transition matrices. The authors propose a solution based on a family of Bayesian estimators to approximate these matrices, supported by theoretical foundations. Through rigorous mathematical proofs, the authors demonstrate that their estimator can effectively approximate transition matrices under claimed mild conditions. Additionally, they introduce a novel label correction method with bounded Bayes error. To evaluate the effectiveness of their proposed method, the authors conduct experiments using three commonly used benchmarks and synthetic annotations. Overall, this paper has potential significant insights that could benefit the community. The experiment evaluation is not very convincing, but I'm tending to accept it at this stage.\n\n\n", "questions": "1. Why are the results on CE trained with clean labels so low? This is inconsistent with prior works.\n\n2. How are the sythentic annotations generated?\n\n", "limitations": "N.A.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "There are several main theoritical contributions in this paper:\n\n1. Authors proposed a sparse Bayesian approach to learn the annotator-specific instance-dependent transition matrices to model the relationship between label noise and crowdsourced annotators.\n\n2. The proposed estimator is claimed to approxmiate true transition processs with guarantee (minimizes Hellinger distance).\n\n3. Based on the derived theorem, the authors also provided a novel correction algorithm named that leverages likelihood ratio test, an upper-bound of the Bayes error for the proposed algorithm is provided.\n\nWith the approxmiation guarantee and error-bound on the correction algorithm, the proposed method is therefore considered to have significant theoritical implications and considerable novelties, provided that the proof are rigourous and correct, which is under further checking.", "weaknesses": "1. The section numbers provided in the appendix do not correspond to the references in the main paper, where are assumptions A.1-A.4 in A.1? \n\n2. Compared baselines are not known for their advantages in modeling instance-dependent label noise, methods such as PartT [1], BLTM [2] should be compared instead. Also, SOTA methods based on geometrical properties such as [3,4] should also be compared. \n\n3. One of the main issues is that the use of sparse Bayesian approach is not strongly motivated, it remains unclear to me why using sparse Bayesian estimators is better or non-trivial compared with existing works.\n\n[1] Xia, Xiaobo, et al. \"Part-dependent label noise: Towards instance-dependent label noise.\" Advances in Neural Information Processing Systems 33 (2020): 7597-7610.\n\n[2] Yang, Shuo, et al. \"Estimating instance-dependent bayes-label transition matrix using a deep neural network.\" International Conference on Machine Learning. PMLR, 2022.\n\n[3] Li, Xuefeng, et al. \"Provably end-to-end label-noise learning without anchor points.\" International conference on machine learning. PMLR, 2021.\n\n[4] Yong, L. I. N., et al. \"A Holistic View of Label Noise Transition Matrix in Deep Learning and Beyond.\" The Eleventh International Conference on Learning Representations. 2022.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weaknesses**\n\n1.Thanks so much for pointing this out. The assumptions A.1-A.4 are in Appendix A.2 and we will revise this error in the final version of our paper. We apologize for the misreference and thanks again for reading our paper carefully.\n\n2.We have now added more baseline methods PartT [1], BLTM [2] and VolMinNet[3], and the results are presented in Table 3 in the attached PDF. \n\n3.Thanks for this thoughtful remark. The motivation and the advantages of the proposed approach can be summarized as follows. \n\n(1) Utilizing such a sparse Bayesian model enables us to consistently estimate the instance-dependent noise transition matrix with limited number of anchor points. As shown in Figure 1 on page 9 of our paper, the average estimation error of the proposed method is apparently smaller than that of the baseline methods. We also present the average estimation error under different annotator number settings in Figure 2 of the attached PDF.\n\n(2) Most of existing works related to the estimation of instance-dependent matrix are heuristic and lack theoretical justifications. [A] made some theoretical progress to justify the use of the trace regularisation, which extends the work of [B] for the case of instance-independent noise matrix. However, the theory in [A] only holds for individual samples, rather than the population setting. Our work first theoretically characterizes the distance between the noise transition model and the true instance-dependent noise transition matrix in terms of the Hellinger distance, which largely closes the theoretical gaps in the consistency of the noise transition model. \n\n(3) The posterior consistency of the noise transition model enables us to conduct further analysis. In particular, based on the posterior consistency result, we propose an algorithm to infer the true label utilizing the noise transition model, and provide an information-theoretic bound on the Bayes error of the label inference method. \n\n**Questions**\n\n1. This could be attributed to the different choices of the network structure and the number of training epochs. In particular, for CIFAR-10 and CIFAR-100 datasets, we choose ResNet-18 and ResNet-34 architecture and train the network for 120 and 150 epochs respectively. And we train the model from scratch instead of using pre-trained weights. \n\n2. We generate three groups of annotators with varying expertise as described on page 8 of our paper, where 5 annotators are in each group. For each annotator, we generate the instance-dependent noisy annotations according to Algorihtm 2 in [C]. \n\n**References**\n\n[A] Disentangling human error from the ground truth in segmentation of medical images. NeurIPS, 2021.\n\n[B] Learning from noisy labels by regularized estimation of annotator confusion. CVPR, 2019.\n\n[C] Xia, Xiaobo, et al. \"Part-dependent label noise: Towards instance-dependent label noise.\" Advances in Neural Information Processing Systems 33 (2020): 7597-7610.\n\n"}, {"review_id": "cDS0oubMMK", "reviewer": "Reviewer_wDkZ", "summary": "The paper deals with the noisy annotation problem with crowdsourcing data. Instead of traditional transition matrices, the paper proposed to learn an instance-dependent transition model that uses a Bayesian network with guaranteed consistent posterior to approximate the noise in labels. The paper then proposes to infer the true label from the noisy annotations and improve the performance based on the corrected labels.", "questions": "1. Can there be a more convincing claim that an instance-dependent noise model can be learned with limited training data?\n2. Is the main theoretical result asymptotic? Can there be a clearer message that indicates the dependency on the number of data samples?\n3. Can there be more analysis on the reasons for the change of performances with the number of annotators on some datasets?\n", "limitations": "Although the paper does mention limitations and extensions, the impact of modeling annotators and instance-dependent noise model is not adequately addressed. The noisy problem is often associated with biases or fairness concerns, so some careful consideration needs to be made.\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is clearly motivated and deals with a potentially meaningful problem for supervised learning with noisy annotations.\n2. The paper provides a detailed theoretical analysis of the proposed Bayesian model and an information-theoretic bound on the Bayes error.\n3. The experiments on MNIST and CIFAR datasets show that the proposed method outperforms the baselines most of the time.\n", "weaknesses": "1. The assumption that an instance-dependent noise model can be learned with limited training data is quite strong. It seems that the proposed method is still associated with preset thresholds like existing methods, which is particularly difficult to set in a noisy problem with multiple annotators.\n2. The conditions for Theorem 1 are not listed in the main paper. I think some remarks are necessary for people to have a fair understanding of the proposed theorems.\n3. The proposed method does not always outperform baselines, and the advantage is not significant. In some cases, the biggest difference appears in the IDN-MID case, which is not thoroughly investigated or explained. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for assessing our paper and providing meaningful comments. Below we address each question in detail.\n\n**Weaknesses**\n\n1.Thanks for your question. \n\n(1) As shown in Appendix A.1 and Appendix A.2, we assume that the underlying noise transition probability can be approximated by a sparse model. This assumption is supported by empirical studies [A-C] which explore different methods on compressing neural networks without impacting performance. Besides, theoretical works [D-E] in approximation theory have established theories guaranteeing uniform approximation rates for a broad family of function classes. Additionally, as shown in Figure 1 on page 9 of our paper, the average estimation error of the proposed method is apparently smaller than that of the baseline methods, which in turn provides empirical evidence for our assumption.\n\n(2) The threshold value in the proposed label correction method is directly related to accuracy of the inferred labels. In our experiment, we start with a smaller value, which is chosen from {5, 10, 15, 20} and linearly increases the value in the training process.\n\n2.Thank you for this suggestion. We will add remarks on these conditions when preparing a revision shortly. Specifically, the conditions to guarantee the posterior consistency can be roughly categorized into the three parts. \n\n(1) Part 1: the hypothesis set we consider is a class of DNNs. \n\n(2) Part 2: the underlying noise transition probability can be approximated by a sparse model.\n\n(3) Part 3: the prior we use need to satisfy some conditions. \n\n3.Thanks for your comment. As shown in Table 1 of our paper, the proposed method outperforms the baseline methods in most cases. On the CIFAR-10 and CIFAR-100 datasets, the performance of our method is always the best, but the second-best method is always changing, which may be the reason why the biggest difference is sometimes seen in the IND-MID case. We display the results from Table 1 in Figure 1 of the PDF attachment, which may help to demonstrate the benefits of the proposed method more clearly. \n\n**Questions**\n\n1. Please see the first point in **Weaknesses**.\n\n2. Yes. The main theoretical result is asymptotic. To investigate the dependency on the number of data samples $n$, we may look at the conditions on the prior in Appendix A.3. For computational considerations, we may consider the prior $\\theta\\sim \\lambda_n N(0, \\sigma^2_{1n})+(1-\\lambda_n)N(0, \\sigma^2_{0n})$, where the values of $\\lambda_n$, $\\sigma_{1,n}$ and $\\sigma_{0,n}$ depends on $n$, and it can be verified that this prior satisfies the conditions in  Appendix A.3 if the values of $\\lambda_n$, $\\sigma_{1n}$ and $\\sigma_{0n}$ are properly chosen. In particular, the value of $\\lambda_n$ is related to the sparsity of the model and we require it to satisfy that $\\lambda_n =O(1/J_{nk}[n^{H_{n1}+H_{n2}}(L_{n1}+L_{n2}p_{n})]^{c})$ for some positive constant $c$ and $k=1, 2$, which should be chosen by considering the network structure and the number of data points $n$. The meaning of the notations in the preceding formula is the same as in the paper. This procedure sheds some light on the consideration of the dependency on $n$.\n\n3. Thanks for your question. We now also consider different settings on the CIFAR10 dataset with the number of annotators set to 10, 20, and 30, respectively. To evaluate the methods under incomplete labeling, for each data item, an annotator labels it with probability 0.2. The performance of the proposed method under different settings can be found in Table 4 and Figure 2, which further demonstrates the effectiveness of the proposed method.\n\n**References**\n\n[A] Learning both weights and connections for efficient neural network. NeurIPS, 2015.\n\n[B] Model compression and acceleration for deep neural networks: The principles, progress, and challenges. IEEE Signal Processing Magazine, 2018.\n\n[C] Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. ICML, 2019.\n\n[D] Optimal approximation with sparsely connected deep neural networks. SIAM Journal on Mathematics of Data Science, 2019\n\n[E] Optimal approximation of piecewise smooth functions using deep ReLU neural networks. Neural Networks, 2018.\n"}, {"review_id": "uwBM4Vwojy", "reviewer": "Reviewer_uiTb", "summary": "The paper introduces a method for modelling input-dependent label noise for classification in the presence of multiple annotators. The generative process of annotation is modelled as a hierarchical Bayesian model in which the observed labels are noisy versions of the latent true labels that are corrupted through a noise transition model that is dependent on the input as well as the annotator. The authors propose a method for inferring the true labels based on the approximated noise model  and demonstrate benefits on classification benchmarks with both synthetic and real annotation noise. ", "questions": "- how does the algorithm scale with the number of annotators?\n- how does the accuracy of the method depend on the \"sparsity\" of labels (e.g., if we had only one label per image, would it still be possible to model the input-dependent noise)? ", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The idea of modelling labeling noise as a function of both input and annotator is much more realistic than the majority of related works which drop the input dependence or ignore the differences between annotators. \n- They propose a practical algorithm with demonstrable efficacy on classification benchmarks with both synthetic  & real label noise. \n- The authors provide a sound theoretical justification for the above algorithm; 1) the concentration theorem shows the \"tightness\" of the approximation of the noise transition model; 2) formulating inference of true labels as a statistical test gives an information-theoretic bound on the error. \n\n\n", "weaknesses": "-  The empirical analysis lacks insights into which components of the annotation model are actually important e.g., how sensitive is the model to a different specification of the prior distribution.\n-  There seems to be no comparison with other works that employ instance-specific noise transition models --- e.g., [18] seems to propose a much simpler model that simultaneously learn the instance-specific confusion matrix per annotator and the true label distribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for reading our paper and providing meaningful feedback. Below we address each question in detail.\n\n**Weaknesses**\n\n1.The performance of the proposed method is relatively robust to the prior distribution as long as it satisfies the conditions listed in Appendix A.3. Specifically, for computational considerations, we consider the prior $\\theta\\sim \\lambda_n N(0, \\sigma^2_{1n})+(1-\\lambda_n)N(0, \\sigma^2_{0n})$ for each parameter $\\theta$, which satisfies the conditions in  Appendix A.3 if the values of $\\lambda_n$ and $\\sigma_{0n}$ are small enough and $\\sigma_{1n}$ is taken a proper value. We provide experimental results with different choices of $\\lambda_n$ in Table 1, from which we can observe that the model performance is relatively stable with respect to different values of $\\lambda_n$ if $\\lambda_n$ is within a reasonable range.\n\n2.Thanks so much for pointing this out. The reference [18] in our paper is intended for segmentation tasks so that we do not include it as a baseline method in our paper. But your suggestion that we should compare with other works employing instance-specific noise matrix is insightful. We have now added more baseline methods Multi-AnT[A], Part-T[B], and BLTM[C] to highlight the advantages of the proposed approach, and the results are presented in Table 3 in the attached PDF.\n\n**Questions**\n\n1.In the network structure of our experiments, each annotator corresponds to a linear fully-connected layer, connected after the shared representation layer, and thus accounts for a small percentage of the overall parameters. We consider different settings on the CIFAR10 dataset with the number of annotators set to 10, 20, and 30, respectively. The performance of the proposed method under different settings can be found in Table 4, with the total training hours listed below.\n\nNumber of Annotators | IDN-LOW | IDN-MID | IDN-HIGH\n|     ---      |   ---  |   ---  |   ---  |\n|       5       |   2.59  |   2.64  |   2.65  |\n|       10      |   2.67  |   2.62  |   2.63  |\n|       20      |   2.65  |   2.65  |   2.67  |\n|       30      |   2.67  |   2.67  |   2.71  |\n\n2.To evaluate the methods under incomplete labeling, for each data item, an annotator labels it with probability 0.2.\n\n**References**\n\n[A] Learning from Multiple Annotator Noisy Labels via Sample-wise Label Fusion. ECCV 2022\n\n[B] Part-dependent label noise: Towards instance-dependent label noise. NeurIPS, 2020.\n\n[C] Estimating instance-dependent bayes-label transition matrix using a deep neural network. ICML, 2022.\n\n"}, {"review_id": "N7ebGOYrrP", "reviewer": "Reviewer_ysQF", "summary": "The authors formulate the noise transition model in a Bayesian framework and design a new label correction algorithm. The authors further formulate the label correction process as a hypothesis testing problem and propose a novel algorithm to infer the true label from the noisy annotations based on the pairwise likelihood ratio test (LRT). The experimental results on benchmark and real-world datasets validate the effectiveness of the proposed approach. ", "questions": "1. From Table 1, the performance of the proposed approach outperforms other algorithms on three image datasets with synthetic annotations, but does not have significant advantages on two datasets with human annotations, CIFAR-10N and LabelMe. The authors have less analytical discussion of the experimental results. The authors should give a fuller discussion of the experimental results and add other datasets with human annotations to verify the validity of the proposed approach.\n\n2. The authors claim that “Learning an instance-dependent noise transition model, however, is challenging and remains less explored.”. But to my knowledge, there are many algorithms proposed to solve this problem. The authors should notice t and cite these papers.\n\n3. The proof section of the text is relatively substantial, but the author's explanation of the motivation of the article is slightly lacking. \n", "limitations": "1. From Table 1, the performance of the proposed approach outperforms other algorithms on three image datasets with synthetic annotations, but does not have significant advantages on two datasets with human annotations, CIFAR-10N and LabelMe. The authors have less analytical discussion of the experimental results. The authors should give a fuller discussion of the experimental results and add other datasets with human annotations to verify the validity of the proposed approach.\n\n2. The authors claim that “Learning an instance-dependent noise transition model, however, is challenging and remains less explored.”. But to my knowledge, there are many algorithms proposed to solve this problem. The authors should notice t and cite these papers.\n\n3. The proof section of the text is relatively substantial, but the author's explanation of the motivation of the article is slightly lacking. \n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper provides a posterior-concentration theorem, which guarantees the posterior consistency of the noise transition model in terms of the Hellinger distance.\n\n2. This paper formulates the label correction process as a hypothesis testing problem and propose a novel algorithm to infer the true label from the noisy annotations based on the pairwise likelihood ratio test (LRT).\n\n3. This paper presents extensive experiments on benchmark and real-world datasets to validate the effectiveness of the proposed approach.\n", "weaknesses": "The performance of the proposed approach outperforms other algorithms on three image datasets with synthetic annotations, but does not have significant advantages on two datasets with human annotations, CIFAR-10N and LabelMe. The authors do not provide a reasonable explanation for these results. In addition, some of the author's statements in the abstract need to be considered, such as “ Learning an instance-dependent noise transition model, however, is challenging and remains less explored.”.  To my knowledge, there are many algorithms proposed to solve this problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks so much for your valuable comments on our paper. Below we address each question in detail.\n\n1.As shown in Table 1 of our paper, the proposed method outperforms the baseline methods in most cases. We also display the results from Table 1 in Figure 1 of the PDF attachment, which may help demonstrate the benefits of the proposed method more clearly. Concerning the reason why the advantage of our approach is more pronounced on the datasets with synthetic annotations than on the real dataset, it may be pertinent to that we strictly follow the instance-dependent assumption in generating the annotations. To further verify the effectiveness of our method, we now add additional experiments on the MUSIC dataset and the results are shown in Table 2.\n\n2.Thanks so much for your suggestion. In preparing a revision, we will take your suggestion and include this background information and an explanation of how our work differs from earlier efforts in our paper. Related references will be added too. In addition, to highlight the advantages of the proposed approach, we have now conducted additional empirical analyses by comparing with baseline methods [A-C] which employ instance-dependent matrix; the results are presented in Table 3 in the attached PDF.\n\n3.Thanks for this thoughtful remark. The motivation and the advantages of the proposed approach can be summarized as follows. \n\n(1) Utilizing such a sparse Bayesian model enables us to consistently estimate the instance-dependent noise transition matrix with limited number of anchor points more. As shown in Figure 1 on page 9 of our paper, the average estimation error of the proposed method is apparently smaller than that of the baseline methods. We now also present the average estimation error under different annotator number settings in Figure 2 of the attached PDF.\n\n(2) Most of existing works related to the estimation of instance-dependent matrix are heuristic and lack theoretical guarantees. [D] made some theoretical progress to justify the use of the trace regularisation, extending the work of [E] in the case of instance-independent noise matrix. However, the theory in [D] only holds for individual samples rather than the population setting. Our work first theoretically characterizes the distance between the noise transition model and the true instance-dependent noise transition matrix in terms of the Hellinger distance, which largely closes the theoretical gaps in the consistency of the noise transition model. \n\n(3) The posterior consistency of the noise transition model enables us to conduct further analysis. In particular, based on the posterior consistency result, we propose an algorithm to infer the true label utilizing the noise transition model, and provide an information-theoretic bound on the Bayes error of the label inference method. \n\n**References**\n\n[A] Learning from Multiple Annotator Noisy Labels via Sample-wise Label Fusion. ECCV 2022\n\n[B] Part-dependent label noise: Towards instance-dependent label noise. NeurIPS, 2020.\n\n[C] Estimating instance-dependent bayes-label transition matrix using a deep neural network. ICML, 2022.\n\n\n[D] Disentangling human error from the ground truth in segmentation of medical images. NeurIPS, 2021.\n\n[E] Learning from noisy labels by regularized estimation of annotator confusion. CVPR, 2019.\n"}]

Author rebuttal:
Dear reviewers,

Thank you for providing feedback! We appreciate your comments and the time and effort you took to read, comprehend, and assess our paper. We value your comments and concerns regarding how to emphasize our motivations and clarify the assumptions more clearly (Reviewer i77Y, PGxM, wDkZ), as well as your suggestions that we compare with more baseline methods to highlight the advantages of the proposed method (Reviewer i77Y, PGxM, uiTb, ysQF). We carefully reviewed every one of your queries, concerns, and remarks. Here we addressed each review separately with a thorough response. In order to reflect our responses, we have also uploaded a one-page PDF with additional experimental results. The baseline methods used in the experiments are listed below.

We hope that our responses have adequately addressed all of the concerns raised. However, if further details, justifications, or results are needed, we would be pleased to provide them.



[1] Gao, Zhengqi, et al. Learning from multiple annotator noisy labels via sample-wise label fusion. European Conference on Computer Vision. Cham: Springer Nature Switzerland, 2022.

[2] Xia, Xiaobo, et al. Part-dependent label noise: Towards instance-dependent label noise. Advances in Neural Information Processing Systems 33 (2020): 7597-7610.

[3] Yang, Shuo, et al. Estimating instance-dependent bayes-label transition matrix using a deep neural network. International Conference on Machine Learning. PMLR, 2022.

[4] Dawid, Alexander Philip, and Allan M. Skene. Maximum likelihood estimation of observer error‐rates using the EM algorithm. Journal of the Royal Statistical Society: Series C (Applied Statistics) 28.1 (1979): 20-28.

[5] Khetan, Ashish, Zachary C. Lipton, and Anima Anandkumar. Learning from noisy singly-labeled data. The Ninth International Conference on Learning Representations. 2018.

[6] Li, Yuan, Benjamin Rubinstein, and Trevor Cohn. Exploiting worker correlation for label aggregation in crowdsourcing. International conference on machine learning. PMLR, 2019.

[7] Li, Xuefeng, et al. Provably end-to-end label-noise learning without anchor points. International conference on machine learning. PMLR, 2021.

[8] Ibrahim, Shahana, Tri Nguyen, and Xiao Fu. Deep learning from crowdsourced labels: Coupled cross-entropy minimization, identifiability, and regularization. ICLR, 2023.



Meta-review: This paper introduces a method for modelling input-dependent label noise for classification in the presence of multiple annotators. The generative process of annotation is modelled as a hierarchical Bayesian model in which the observed labels are noisy versions of the latent true labels that are corrupted through a noise transition model that is dependent on the input as well as the annotator. The authors propose a method for inferring the true labels based on the approximated noise model and demonstrate benefits on classification benchmarks with both synthetic and real annotation noise.

Specifically, the idea of modelling labeling noise as a function of both input and annotator is much more realistic than the majority of related works which drop the input dependence or ignore the differences between annotators. They propose a practical algorithm with demonstrable efficacy on classification benchmarks with both synthetic & real label noise. The authors provide a sound theoretical justification for the above algorithm: namely the concentration theorem shows the "tightness" of the approximation of the noise transition model; and formulating inference of true labels as a statistical test gives an information-theoretic bound on the error. However, there still have some rooms to be improved. For example, the relaxed condition and its analysis still need to be largely improved; the description of the anchor-point collection method and the transition-model learning process should be improved; and the roles of different modules were not fully decoupled in the ablation experiments.

Although the reviewers had some concerns and follow-up questions, the authors did a point-to-point rebuttal in details. The score of reviewer i77Y should have been increased after the rebuttal (but it wasn't). Meanwhile, the clarity and novelty are above the bar of NeurIPS. Therefore, this paper can be accepted as a poster.
Decision: Accept (poster)