Deep Learning From Crowdsourced Labels: Coupled Cross-Entropy Minimization, Identifiability, and Regularization
Authors: Shahana Ibrahim
Tri Nguyen
Xiao Fu
Venue: ICLR 2023 poster (2023)
Keywords: deep learning
learning under noisy labels
neural classifier
end-to-end learning
crowdsourcing

Abstract: Using noisy crowdsourced labels from multiple annotators, a deep learning-based end-to-end (E2E) system aims to learn the label correction mechanism and the neural classifier simultaneously. To this end, many E2E systems concatenate the neural classifier with multiple annotator-specific label confusion layers and co-train the two parts in a parameter-coupled manner. The formulated coupled cross-entropy minimization (CCEM)-type criteria are intuitive and work well in practice. Nonetheless, theoretical understanding of the CCEM criterion has been limited. The contribution of this work is twofold: First, performance guarantees of the CCEM criterion are presented. Our analysis reveals for the first time that the CCEM can indeed correctly identify the annotators' confusion characteristics and the desired ``ground-truth'' neural classifier under realistic conditions, e.g., when only incomplete annotator labeling and finite samples are available. Second, based on the insights learned from our analysis, two regularized variants of the CCEM are proposed.  The regularization terms provably enhance the identifiability of the target model parameters in various more challenging cases. A series of synthetic and real data experiments are presented to showcase the effectiveness of our approach.

Published as a conference paper at ICLR 2023
DEEP LEARNING FROM CROWDSOURCED LABELS: COUPLED CROSS-ENTROPY MINIMIZATION, IDENTI-
FIABILITY, AND REGULARIZATION
Shahana Ibrahim, Tri Nguyen, and Xiao Fu" School of Electrical Engineering and Computer Science
Oregon State University Corvallis, OR 97330, USA
ABSTRACT
Using noisy crowdsourced labels from multiple annotators, deep learning-basse based end-to-end (E2E) system aims to learn the label correction mechanism and the neural classifier simultaneously. To this end, many E2E systems concatenate the neural classifier with multiple annotator-specific "label confusion" layers and co-train the two parts in coupped manner. The formulated coupled cross-entropy minimization (CCEM)-type criteria are intuitive and work well in practice. Nonetheless, theoretical understanding of the CCEM criterion has been limited. The contribution of this work is twofold: First, performance guarantees of the CCEM criterion are presented. Our analysis reveals for the first time that the CCEM can indeed correctly identify the annotators' confusion characteristics and the desired "ground-
neural classifier under realistic conditions, e.g., when only incomplete annotator labeling and finite samples are available. Second, based on the insights learned from our analysis, two regularized variants of the CCEM are proposed. The regularization terms provably enhance the identifiability of the target model parameters in various more challenging cases. A series of synthetic and real data experiments are presented to showcase the effectiveness our approach.
INTRODUCTION
The success of deep learning has escalated the demand for labeled data to an unprecedented level. Some learning tasks can easily consume millions of labeled data (Najafabadi et al. 2015) Goodfellow et 201 However, acquiring data labels is nontrivial task-it often requires a pool of annotators with sufficient domain expertise to manually label the data items. For example, the popular Microsoft COCO dataset contains 2.5 million images and around 20,000 work hours aggregated from multiple annotators were used for its category labeling (Lin et al. 2014).
Crowdsourcing is considered an important working paradigm for data labeling. In crowdsourcing platforms, e.g., Amazon Mechanical Turk (Buhrmester et al. 2011). Crowdflower (Wazny| 2017). and ClickWork (Vakharia & Lease 2013), data items are dispatched and labeled by many annotators; the annotations are then integrated to produce reliable labels. A notable challenge is that annotator-output labels are sometimes considerably noisy. Training machine learning models using noisy labels could seriously degrade the system performance (Arpit et al. [2017] 2017:Zhang et al. 2016a). In addition, the labels provided by individual annotators are often largely incomplete, as dataset is often divided and dispatched to different annotators.
Early crowdsoureing methods often treat annotation integration and downstream operations. e.g.. classification, as separate tasks; see, (Dawid & Skene 1979; Karger et al.) [00 Whitehill et al. 2009 Snow et al. 20088] Welinder et al., 2010) Liu al.] 2012 Zhang et al. [016b]] Ibrahim et al. 2019 Ibrahim & Fu 2021). This pipeline estimates the annotators' confusion parameters (e.g., the confusion matrices under the Dawid & Skene (DS) model (Dawid & Skene 1979)) in the first stage.
*Contact Information: Shahana Ibrahim, Tri Nguyen, and Xiao Fu: (ibrahish, nguyetr9, xi ac. fu) @oregonsttte..dd

---

Published as a conference paper at ICLR 2023
Then, the corrected and integrated labels along with the data used for training the downstream tasks' classifiers. However, simultaneously learning the annotators' confusions and the classifier in an end-to-end (E2E) manner has shown substantially improved performance in practice. (Raykar
et al. 2010 Khetan et al. 2018; Tanno et al. 2019 Rodrigues & Pereira 2018 Chu et al. 2021
Guan al. 2018 Cao al. 2019 Li at. 2020 Wei et al. 2022
Chen al. 2020).
To achieve the goal of E2E-based learning under crowdsourced labels, a class of methods concatenate a "confusion layer" for each annotator to the output of neural classifier, and jointly learn these parts via a parameter-coupled manner. This gives rise to a coupled cross entropy minimization (CCEM)
criterion (Rodrigues & Pereira 2018; Tanno et al., 2019; Chen et al., 2020; Chu et al. 2021 Wei et al. 2022). In essence. the CCEM criterion models the observed labels as annotators confused outputs from the "ground-truth " predictor (GTP>iie. the classifier as if being trained using the noiseless labels and with perfect generalization- which is natural and intuitive. A notable advantage of the CCEM criteria is that they often lead to computationally convenient optimization problems, as the confusion characteristics are modeled as just additional structured layers added to the neural networks. Nonetheless, the seemingly simple CCEM criterion and its variants have shown promising performance. For example, the crowdlayer method is typical CCEM approach, which has served as a widely used benchmark for E2E crowdsourcing since its proposal (Rodrigues & Pereira 2018). In (Tanno al., 2019), similar CCEM-type criterion is employed, with a trace regularization added. More CCEM-like learning criteria are seen in (Chen et al. 2020 Chu et al. 2021 Wei et al. 2022).
with some additional constraints and considerations.
Challenges. Apart from its empirical success, understanding of the CCEM criterion has been limited. Particularly,
often unclear if CCEM can correctly identify the annotators' confusion characteristics (that are often modeled as "confusion matrices") and the GTP under reasonable settings (Rodrigues & Pereira 2018 Chu et al., [20T] Chen al.] 2020 Wei al., (022). but identifiability stands as the key for ensured performance. The only existing identifiability result on CCEM was derived under restricted conditions, e.g., the availability of infinite samples and the assumption that there exists annotators with Hiagonally-dominaa
confusion matrices (Tanno et al. 2019). To our best knowledge, model identifiability of CCEM has not been established under realistic conditions, c.g., in the presence of incomplete annotator labeling and non-experts under finite samples.
We should note that a couple of non-CCEM approaches proposed identifiability -uraritttedg solu- tions for E2E crowdsoureing. The work in (Khetan et al. 2018) showed identifiability under their expectation maximization (EM)-based learning approach. but the result is only applicable to binary classification. An information-theorrttee loss-based learning approach proposed in (Cao al.. 2019) presents some identifiability results, but under the presence of a group of independent expert annota- tors and infinite samples. These conditions are hard to meet or verify. In addition, the computation of these methods are often more complex relative to the CCEM-based methods.
Contributions. Our contributions are as follows:
Identifiability Characterizations of CCEM-based E2E Crowdsourcing. In this work, we show that the CCEM criterion can indeed provably identify the annotators' confusion matrices and the GTP up to inconsequential ambiguities under mild conditions. Specifically, we show that, if the number of annotator-labeled items is sufficiently large and some other reasonable assumptions hold, the two parts can be recovered with bounded errors. Our result is the first finite-sample identifiability result for CCEM-based crowdsoureing. Moreover, our analysis reveals that the success of CCEM does not rely on conditional independence among the annotators. This is favorable (as annotator independence a stringent requirement) and surprising, since conditional independence is often used to derive the CCEM criterion; see, e.g., (Tanno et al. 2019: Rodrigues & Pereira 2018 Chu et al. 2021).
Regularization Design for CCEM With Provably Enhanced Identfiability. Based on the key insights revealed in our analysis, propose two types of regularizations that can provide enhanced identifiability guarantees under challenging scenarios. To be specific, the first regularization term ensures that the confusion matrices and the GTP can be identified without having any expert annotators if one has sufficiently large amount of data. The second regularization term ensures identifiability when class specialists are present among annotators. These identifibbllit-ennance approaches demonstrate promising label integration performance in our experiments.
Notation. The notations are summarized in the supplementary material.
2

---

Published as a conference paper at ICLR 2023
2 BACKGROUND
Crowdsourcing is a core working paradigm for labeling data, as individual annotators are often not reliable enough to produce quality labels. Consider a of N items { J Each item belongs to one of the K classes. Here, In E IRP denote the feature vector of nihh data item. Let {ym Ji=1 denote the set of ground-truth labels, where Yn E [K], Vn. The ground-truth labels {yr, J are unknown. We ask M annotators to provide their labels for their assigned items. Consequently, each item Vn is labeled by a subset of annotators indexed by S, S [M]] Let (olhm) (i,,))es denote the set of labels provided by all annotators, where S {(m, n²) m E Sn, n E [NA] and gh [K]. Note that |S] < NM usually holds and that the annotators may often incorrectly label the items, leading
incomplete and noisy (m)) Mm.a)es. Here, "incomplete" means that S does not cover all possible combinations of (m, ni.-ie. not all annotators label all items. The goal of an E2E crowdsourcing system is to train reliable machine learning model (often a classifier) using such noisy and incomplete annotations. This is normally done via blindly estimating the confusion characteristics of the annotators from the noisy labels.
Classic Approaches. Besides the naive majority voting method, one of the most influential crowd- sourcing model is by Dawid & Skene (Dawid & Skene 1979). Dawid & Skene models the confusions of the annotators using the conditional probabilities Pr(z!!"") [y.).. Consequently, annotator m's confusion is fully characterized by a matrix defined as follows: Am. k') == Pr(gh = klyyn = k),, Vk, k' [K]. Dawid & Skene also proposed an EM algorithm that estimate A.. 's under naive Bayes generative model. Many crowdsourcing methods follow Dawid & Skene's modeling ideas Ghosh al. 2011 Dalvi et al., [2013] Karger et al., [2013] Zhang al. [016b] (Traaaniiis et al. 2018 2019 Ibrahim & Ful (022).. Like (Dawid & Skene 1979). many of these methods do
Ibrahim et al.
not exploit the data features F,, while learning the confusion matrices of the annotators. They often treat confusion estimation and classifier training as two sequential tasks. Such two-stage approaches
may suffer from error propagation.
E2E Crowdsourcing and The Identifiability Challenge. The E2E approaches in (Rodrigues & Pereira 2018; Tanno al.] 2019; Khetan et al. 2018) model the probability of mtth annotator's
response to the data item Ty as follows:
K
Pr(O(m) = k((x)) =
Σ Pr(Ofm) = klyn = k')Pr(yn = k(xx)), k [K], V
where the assumption that the annotator confusion is data-independent has been used to derive the right-hand side. In the above, the distribution Pr(gh") (ym) (1))) models the confusions in annotator responses given the true label y/u and Pr(ym denotes the true label distribution of the data item
Fn The distribution Pr(y, (zr,) can be represented using mapping f IRD [0, 1]K [f [f(x)))e
Pr(yn = k(xx). Define a probability vector pk (()) E [0, 1]x for every m and n, such that [p ((m)) =
Pr(ak() (m) ke)z,)) With these notations, the following model holds:
(!n)
Am (Ix,), Vm, n.
(2)
In practice, one does not observe p (mm) Instead, the annotations gf(") are categorical realizations of the distribution (m²) i.e.,
xmm) ~ Cart(p(m)) (m))
The goal of E2E crowdsourcing is to identify A. and f in 2 from noisy labels (Th" (1))
} n) and
data (a,, W Note that even pa in (2) is observed, Am and f(-) are in general not identifiable. The reason is that one can easily find nonsingular matrices Q E R such that pn (m) A. (wn).
where A, A., and f(x,) = 1 f(x.). If an E2E approach does not ensure the identifiability of A. and f. but outputs f(x,) = 1- f(xx). then the learned predictor is not likely to work reasonably. Identifying the ground-truti truth f not only identifies the true labels for the training data (data for which the annotations have been collected), but useful to predict the true labels for unseen test data items. In addition, correctly identifying A,, 's helps quantify how reliable each annotator is.
3

---

Published as a conference paper at ICLR 2023
CCEM-based Approaches and Challenges. A number of existing E2E methods are inspired by the model in (2) to formulate CCEM based learning losses.
Crowdlayer (Rodrigues & Pereira 2018): For each (m, n) E S, the generative model in naturally leads to a cross-entropy based learning loss, i.e., CE(Amf(z)).))) glm)).
As some annotators co-label items, the components f( (x,) associated with the co-labeled items shared by these annotators. With such latent component coupling and putting the cross-entropy losses for all (m, n) S together, the work in (Rodrigues & Pereira 2018) formulate the following CCEM loss:
1 [S]
minimize FEF. (e,
CE(softax((Am (xn)). Dlm)))
(m.n)ES
where S (f(x) E RK| f(z) E AK. Var) a function class and the softmax operator is applied
as the output of flr,) is supposed to be probability mass function (PMF). The method based on the formulation in (4) was called crowdlayer (Rodrigues & Pereira 2018). The name comes from the fact that the confusion matrices of the "crowd" A. ' can be understood as additional layers if f is represented by a neural network. The loss function in (4) is relatively easy to optimize, as any off fi-thhe-sheff neural network training algorithms can be directly applied. This seemingly natural and simple CCEM approach demonstrated substantial performance improvement upon classic methods. However, there is performance characterization for 4
TraceReg (Tanno et al. 2019) : The work in (Tanno et al. 2019) proposed a similar loss function- with a regularization term in order establish identifiability of the Am and f:
M
minimize f AA S
Σ
C In plm) + +
trace trace(Am))
(5)
(m,N)ES
where A is the constrained set {A E RK*K A 2 A- It was shown that (i) if plm) =
instead of yn ((()) is observed for every m and n and (ii) the mean of the Am's are diagonally dominant, then solving (5) with
(xx),, yn s(m)) replaced by enforcing (1²) fmf(()) ensures identifying A. for all m, up to column permutations. Even though, the result provides some justification for using CCEM criterion under trace regularization, the result is clearly unsatisfactory, as it requires many stringent assumptions to establish identifiability.
Speel.FC (Chen et al. 2020), Union-Ner (Wei et al. 2022), CoNAL (Chu et al., 2021): A number of other variants of the CCEM criterion are also proposed for E2E learning with crowdsourced labels. The work in (Chen et al., 2020) uses a similar criterion as in (4, but with the softmax operator applied on the columns of Am 's instead on the output of A [xx). The work in (Wei et al. 2022) concatenates Am 's vertically and applies the softmax operator on the columns of such concatenated matrix, while formulating the CCEM criterion. The method in (Chu et al. 2021 models common confusion matrix in addition to the annotator-specific confusion matrices A,, and employs a CCEM-type criterion to learn both in a coupled fashion. Nonetheless, none of these approaches have successfully tackled the identifiability aspect. The work (Wei et al., 2022) claims theoretical support for their approach, but the proof is flawed. In fact, understanding to the success of CCEM-based methods under practical E2E learning settings is still unclear.
Other Related Works. A couple of non- Mon-CCEM approaches have also considered the identifiability aspects (Khetan al., 2018 Cao et al. 2019). The work in (Khetan et al. 2018)) presents an EM- inspired alternating optimization strategy. Such procedure involves training the neural classifier multiple times, making it a computationally intensive approach. In addition, its identifiability guarantees are under certain strict assumptions, e.g., binary classification, identical confusions and conditional independence for annotators which are hard to satisfy in practice. The approach in (Cao) et al. 2019) employs an information- -thooretic loss function to jointly train predictor network and annotation aggregation network. The identifiability guarantees are again under restrictive assumptions, e.g., infinite data, no missing annotations and existence of mutually independent expert annotators.
We should also note that there exist works considering data-dependent annotator confusions as well, e.g., (Zhang al. 2020) (multiple annotator case) and (Cheng et al. 2021 Xia et al.] 2020 Zhu et al.) 2022) (single annotator case)- leveragiin more complex models and learning criteria. In our work, focus the criterion designed using a model in (1) it is shown be effective in practice.
4

---

Published as a conference paper at ICLR 2023
3 IDENTIFIABILITY OF CCEM-BASED E2E CROWDSOURCING
In this section, we offer identifiability analysis of the CCEM learning loss under realistic settings. We consider the following re-expressed objective function of CCEM:
minimiize f.(A.))
Σ
In m)) k] log (mn()))((e))l
(6a)
S
(m.n)ES k=1
subject to f FEF, Am A, Vm,
(6b)
where F C (f(x)) RK f(()) Ak, vz) is function class and A is the constrained set (A RA*A x A 2 0,1 A = 1 }. since each column of Am are conditional probability distributions.
The rationale is that the confusion matrices Am 's act as correction terms for annotator's labeling noise to output a true label classifier f. Intuitively, the objective in (6a) encourages the output estimates f, {Am. to satisfy the relation ph.") f f(x,), Vm, One easily note that the identifiability guarantees for A... and f i.e. when does the ground-truth A. and the ground-truth can be identified) are not straightforward since there exists an infinite number of nonsingular matrices Q E R j such that pa. (Am QQ f(x.)).
To proceed, we make the following assumptions:
Assumption Each data item Dn, E [N] is frawnffrom a distribution 'D independently at random and has a bounded l2 norm. The observed index pairs (m, n) are included in S uniformly random.
Assumption The neural networkfumm function class F has a complexity measure denoted R..
Here, we the sensitive complexity parameter introduced in (Lin & Zhang 2019) the complexity measure Fx. In essence, Ry gets larger as the neural network function class F. gets deeper and alder-also supplementary material Sec. K for more discussion.
Assumption 3 There exists GTP f
RD - [0, [], such that [f*(x,)) = Pr(y, = k< where Yn denotes the true label of the data item Tn- In addition, there exists E F succ that [)f(),)) ff (xx))l22 S v for all In, DD where S cc.
Assumption (Near-Clas, Specialist Assumption) Let A denote the ground-truth confusion matrix for annotator m. For each class k. there exists near-class specialist, indexed by mg, such that Ab, (k.:) e E1, where &1
Assumption (Near-Anchor Point Assumption) For each class k, there exists a near-anchor point, Fny. such that ( e2 S E2), where & oc.
Assumptions 1 are standard conditions for analyzing performance of neural models under finite sample settings. The Near-Class Specialist Assumption (NCSA) implies that there exist annotators for each class l E [K] who can correctly distinguish items belonging to class i from those belonging to other classes. It important to note that NCSA assumption much milder compared to the commonly used assumptions such as the existence of all-class expert annotators (Cao et al. 2019 or diagonally dominant A (Tanno al. 2019). Instead, the NCSA only requires that for each class, there exists one annotator who is specialized for it (i.e., class-specialist)- but the annotator needs not be an all-class expert: see Fig. [ in the supplementary material for illustration. The Near-Anchor Point Assumption (NAPA) is the relaxed version of the exact anchor point assumption commonly used in provable label noise learning methods (Xia al. 2019
Liet al. 2021). Under Assumptions
5
we have the following result:
Theorem Assume that each f (x and [An (x YA,, E A. E F are at least (1/8). Also assume that maax A I a, Vm, for certain O. Then, for any a 0, with
5

---

Published as a conference paper at ICLR 2023
probability greater than 1 K/N", any optimal solution A.. and f of the problem 6 satisfies the following relations:
min
Am A m + E2), Vm E [M],
(7a)
min [[f(z)) II f1(2))1 K(n + E2).
(7b)
where n²² O [SMNN// V log S + (||X|| 1+)) +VKKMN II 10, is permutation matrix, and X = [am...... Lash. (.)) E S, if conditions E2, S 1/K, v S M/K,, and S = S| = Ω (82 K2 max (Mlg ( hold.
The proof of Theorem D is relegated to the supplementary material in Sec. B The takeaways are as follows: First, the CCEM can provably identify the A?, and the GTP f under finite samples and such fnite-ssmple identifiability of CCEM was not established before. Second, some restrictive conditions (e.g., the existence of all-class experts (Tanno et al. 2019 Cao et al. 2019)) used the literature for establishing CCEM's identifiability are actually not needed. Third, many works derived the CCEM criterion under the maximum likelihood principle via assuming that the annotators are conditionally independent; see (Rodrigues & Pereira 2018 Chen et al.) 20200] Tanno et al. [219 A and f under
Chu et al., 2021). Interestingly, as we revealed in our analysis, the identifiability the CCEM criterion does not rely the annotators' independence. These new findings support and explain the effectiveness of CCEM a wide range of scenarios observed in the literature.
4 ENHANCING IDENTIFIABILITY VIA REGULARIZATION
Theorem confirms that CCEM is a provably effective criterion for identifying A 's and ft. The caveats lie in Assumptions and Essentially, these assumptions require that some collection { m } and some vectors of the collection (xx)) are close to the canonical vectors. These are reasonable assumptions, but satisfying them simultaneously may not always be possible. A natural question is if these assumptions can be relaxed, at least partially.
of the
In this section, we propose variants of CCEM that admits enhanced identifiability. To this end, we use a condition that is often adopted in the nonnegative matrix factorization (NMF) literature:
Definition 1 (SSC) Fu al. 2019 Gillis 2020) Consider the second-order cone C {xc
RKIVK ||| 1 2/. A nonnegative matrix Z E RL*K satisfies the sufficiently scattered condition (SSC) C S cone Z") and (ii) cone 2 S cone(Q) does not hold for any orthogonal Q E RK except for the permutation matrices.
Geometrically, the matrix Z satisfying the SSC means that its rows span a large "area" within the nonnegative orthant, so that the conic hull spanned by the rows contains the second order cone C as a subset. Note that the SSC condition subsumes the the NCSA (Assumption 4 where { 0) and the NAPA (Assumption (5) where & = 0) as special cases.
Using SSC, we first show that the CCEM criterion in 6 attains identifiability of A 's and ft without using the NCSA or the NAPA, when the problem size grows sufficiently large.
Theorem 2 Suppose that the incomplete labeling paradigm in Assumption
7 holds with S = S2(1)
and N = =O(t"), ), for a certain > O. Also, assume that there exists Z Th Ti....,ryy such that F² [f(((0)))..... f (xx satisfies the SSC and W = [ATT,... A M. satisfies the SSC as well. Then, at the limit of t cc, if f F, the optimal solutions (fAm), of (6) satisfies A, = A II for all m and f(x) = II ft)) for all x ~ D, where is a permutation matrix.
The proof is via connecting the CCEM problem to the classic nonnegative matrix factorization (NMF) problem at the limit of t - oo; Sec. D It is also worth to note that Theorem doess does not require complete observation of the annotations to guarantee identifiability. Another remark is that W and Fi satisfying the SSC is more relaxed compared to that they satisfying the NCSA and NAPA,

---

Published as a conference paper at ICLR 2023
respectively. For example, one may need class specialists with much higher expertise to satisfy NCSA than to satisfy SSC on W'salso see geometric illustration in Sec. L Compared to the result in Theorem I Theorem 2 implies that when N is very large, the CCEM should work under less stringent conditions relative to the NCSA and NAPA. Nonetheless, the assumption that both the GTP and the annotators' confusion matrices should meet certain requirements may not always hold. In the following, we further show that the SSC on either W or F can be relaxed:
Theorem Suppose that the incomplete labeling paradigm in Assumption I hoold with S ==0 (t(t) and N = Ott)), for a certain t >> O. Then, at the limit of t + oc, if fü E F, we have A = A II for all m and fx) = II fä (z) for all x ~ DD when any of the following conditions hold:
(a) If there exists Z = {Tu,..... n such that (Fz) [[ (( rank W = K, and ). f*) is the optimal solution of (6) with the maximal log det (F*FFF F
II satisfies the SSC,
(b) 1f W = [ A satisfies the SSC, rank FR) = K, and (Am, 8 is the optimal solution of 6 with the maximal log det((W")W"))
Theorem 3aa) shows that if the number of annotated data items is large and the GTP-outputs associated with En are diverse enough to satisfy the SSC, then f and A are identifiable even if there are no class specialists available. Compared to Theorem 2 the identifiability clearly enhanced, as the conditions on the annotators have been relaxed. Theorem 3(b) implies that if W satisfies SSC, identifiability can be established irrespective of the geometry of F Intuitively, when there are more annotators available, W is more likely to satisfy SSC (the relation between the size of W and SSC was shown in (Ibrahim et al. 2019. Theorem 4) under reasonable conditions). Hence, in practice, Theorem b) may offer ensured performance in cases where more annotators are available.
Similar to the proof in Theorem the proof here connects the CCEM-based E2E crowdsourcing problem to the simplex-structured matrix factorization (SSMF) problem (see (Fu et al. 2015; 2018)
at the limit of t + co. The detailed proof is provided in Sec. B We should mention that various connections between matrix factorization models and data labeling problems were also observed in
related prior works, e.g, the classic approaches based on Dawid & Skene model (Dawid & Skene
1979 Zhang al. 20166b Ibbahim al. 2019; Ibrahim & Ful 2021) and E2E learning under noisy labels (Li et al. 2021). Nonetheless, the former does not consider cross-entropy losses or involve any feature extractor, whereas, the latter does not consider multiple annotators or incomplete labeling.
Implementation via Regularization Theorem 3 naturally leads to regularized versions of CCEM. Correspondingly, we have the following two cases:
Following Theorem 3 (a), when the GTP is believed to be diverse over different x,, 's, we propose to employ the following regularized CCEM:
K
minimize Am A.Vmm fEF
Σ
Σ
([(k)) (llog(AAm((x))) - A log det FF",
(8)
S
(m,))E8 k=1
where F = [f(z)).... )TT. In similar spirit, following Theorem (b, we propose the
following regularized CCEM when M is large (so that W likely satisfies SSC):
K
minimize An E.A.m. FEF
1
Σ
(ppl = k) f(x,)) - A Alog det W WTW
(9)
S
(m.N)ES 1=1
where W- = AT. A Ml The implementations for S and (9) are called as reouetry-
crowdsoureing network, abbreviated as GeoCrowdNe: (F) and GeoCrowiNet (W). respectively.
Remark Based on our analyses, our suggested rule of thumb for choosing regularization is as fol- lows: When M is large but N is relatively small, using GedNrowdNet (W) is recommended, as W is more likely to satisfy the SSC compared to FT. However, when N is large. using GeoCrowsiet (F) is expected to have better performance as F is likely to satisfy the SSC in this case. Under big data settings, N is often large and the GTP outputs of x,, 's are often reasonably diverse. Hence, (8) oftentimes works well, as will be seen in our experiments. Nonetheless, for cases where the geometry of F violates the SSC, the employment of more annotators can help via using 99) which is also an intuitive advantage of crowdsourcing.
7

---

Published as a conference paper at ICLR 2023
Table 1: Average test aceuracy (# std) of the proposed methods and the baselines on MNIST &
Dushion-MNIST dataset under various (N, M)'s ss; labels are produced by machine annotators; 0.1.
MNNST
WishonnMMNIS
Methods
Case
Lase
Case
Case
[1000, 151
11000.
201
[5
100000
51
10000
11000,00
301
15100).5
(1000),00
GepCrowdNet (F)
79.89 1 3.08
82
18
1 3.48
85.92
1 2.73
87.21
1 2.47
78.98
283
84.47
1.4
80.00
1 0.46
K3.68
2.17
GeoGrowdNet (K)
80.97
83.09
2.37
17.79
K.77
82.37
9.18
79.50
85.56
72.36
3.84
74.03
GeoCrowdKeet (A ()
75.15 + 6.73
09.17
2.61
71,66
+ 4,4 4,48
60.29
+ 7.91
70.92
4.14
81.88
4,41
69.31 = 4.77
75.04
7.50
ToggoRRo
70.14
6.93
178.09
3.52
63.71
10.76
64.45
75.06
83.79
69.82
6.46
72.21
8.44
Growdlayer
65.72 4.81
122900
12.90+22: 2.31
51.25
+ 6.24
55,122
63.91
= 2.11
76,50 = 3,68
64.73
6.89
63,18
3,55
=
MB3M
57.24 8.54
33.33
+: 5.72
28.14
= 6,24
2.00
23.144
2.36
25,43
= 5.68
37.34
3.73
38.62
5.45
CONAL
51.33 4.27 (55.59
5.32
44.79 1. 7:01
39.41
139.76
3: 3.34
71.44
1: 6.22
52.15
6:08
54,61
7.54
Max KIG
$1.32 1.31 183.34
3.36
83.71
= 123
81.05
+ 0.63
70.93
2 5.61
81.27
= 5.37
73,45
5.21
NN-KV
78.98
1 3.21
182.78
1.45
K3.44
1 198
83.10
2.86
62.61
2 6.38
73.61
1 3.88
61.95
2. 3.73
71.64
2.25
NR-D8EM
73.95
1 4.90
77.37
4.06
65.81
2.74
69:09
1 3.21
55589
5.97
73.64
4.44
31.40
3.86
35.10
4.89
5
EXPERIMENTS
Baselines. The proposed methods are compared with number of existing E2E crowdsourcing methods, namely, TraceReg[Tang et al. 2019), MBEM (Khetan et al.) 2018). CrowdLayer (Rodrigues & Pereira 2018), CoNAL (Chu et al. (02T), and Max MIG (Cao et al. 2019). In addition
to these baselines, we also learn neural network classifiers using the labels aggregated from majority voring and the classic EM algorithm proposed by Dawid &S kene (Dawid & Skene 1979), denoted as NN-MV and NN respectively.
Real-Data Experiments with Machine Annotations. The settings are follows:
Dataset. We use the MNIST dataset (Deng 2012) and Fashion-MNIST dataset (Xiao et al. 2017); more details in Sec. N
Noisy Label Generation. We train a number of machine classifiers to produce noisy labels. Five types of classifiers, including support vector machines (SVM), k-Nearest Neighbour (kNN), logistic regression, convolutional neural network (CNN), and fully connected neural network are considered to act as annotators. To create more annotators, we change some of their parameters (e.g., the number of nearest neighbour parameter k of kNN and the number of epochs for training the CNN). We consider two different cases: (i) Case I: NCSA (Assumption 4 holding: Each annotator is chosen to be an all-class expert with probability 0.1. If an annotator is chosen to be an all-class expert, it is trained carefully so that its classification accuracy exceeds a certain threshold; see details in Sec. N Note that the existence of an expert implies that the NCSA and the SSC are likely satisfied by W but the reverse is not necessarily true. We use this strategy to enforce NCSA only for validation purpose. It does not mean that the CCEM criterion needs the existence of experts to work. (ii) Case 2: NCSA not holding: Each machine annotator is trained by randomly choosing a small subset of the training data (with 100 to 500 samples) so that the accuracy of these machine annotators are low. This way, any all-class expert or class-specialist is unlikely to exist.
We use the two cases to validate our theorems. Under our analyses, GeoCrowdNet (W) is expected to work better under Case 1, as NCSA approximately implies SSC. In addition, GeoCrowdNet (F) does not rely the geometry of W and thus can work under both cases, if N is reasonably large (which implies that (FF) is more likely to satisfy the SSC). Once the machine annotators are trained, we let them label unseen data items of size N. To evaluate the methods under incomplete labeling, an 0.1. Under this labeling strategy, every data item
annotator labels any data item with probability only labeled by a small subset of the annotators.
Settings. The neural network classifier architecture for MNIST dataset is chosen to be Lenet-5 (Lecun et al.) 1998), which consists of two sets of convolutional and max pooling layers, followed by flattening convolutional layer, two fully-connected layers and finally a softmax layer. For FaSHion-MNIST dataset, we use the ResNet-18 architecture (He al., 2016). Adam (Kingma & Ba 2015) is used an optimizer with weight decay of 10-4 and batch size of 128. The regularization parameter À and the initial learning rate of the Adam optimizer are chosen via grid search method using the validation set from {0.01, 0.001, 0.0001) and (0.01, 0.001), respectively. We choose the same neural network structures for all the baselines. The confusion matrices are initialized with identity matrices of size K for proposed methods and the baselines TraceReg and CrowdLayer.
Results. Table presennss the average label prediction accuracy on the testing data of the MNIST and the Mashion-MNIST over 5 random trials, for various cases. One can observe that GeoCrowdNet (F)
8

---

Published as a conference paper at ICLR 2023
Table 2: Average test accuracy of the proposed methods and the baselines on LabelMe (M 59, K 8) and Music (M = 44, K = 10) datasets.
Methods
LabelMe
Music
GeoCrowdNet (F)
85.85 0.33
67.13 + 1.27
GeoCrowdNet (W)
81.59 0.73
66.46 + 1.77
GeoCrowdNeet (A=0)
80.35 0.40
65.93 1.81
TraceReg
$0.89 0.73
66.40 = 0.90
Crowd
81.41 0.90
65.53 + 1.74
MBEM
80.05 3.31
69.00 2.15
CoNAL
81.68 2.72
60.93 = 0.61
Max-MIG
85.03 + 0.44
64.33 + 2.31
NN-MV
79.57 1.24
63.40 2.68
NN -SEM
78.26 1.18
64.66 + 2.34
performs the best when there are more number of annotated items, even when there are no class specialist annotators present (i.e., case 2). On the other hand, GeoCrowdNet (W) starts showing its advantage over GeoCrowdNet: (F) when there are more number of annotators and class spe- cialists among them. Both consistent with theorems. In addition, the baseline Ma XMXXI performs competitively when there are all-class experts-which is consistent with their identifiability analysis. However, when there are no such experts (case 2), its performance drops compared to the proposed methods, especially GeoCrowdNet (F) whose identifiability does not rely on the existence of all-class experts or class specialists. Overall, GeoCrowdNet (F) exhibits consistently good performance.
Real-Data Experiments with Human Annotators. The settings are follows:
Datasets, We consider two different datasets, namely, LabelMe (M = 59) (Rodrigues et al. 2017
Russell al., 2007) and Music (M = 44) (Rodrigues et 2014), both having noisy and incomplete labels provided by human workers from AMT.
Setrings. For LabelMe, we employ the pretrained VGG-16 embeddings followed by fully connected layer as used in (Rodrigues & Pereira 2018). For Music, we choose similar architecture, but with batch normalization layers. We use batch size of 128 for LabelMe and batch size of 100 for Music dataset. All other settings are the same as the machine annotator case. More details of the datasets and architecture can be seen in Sec.
Results. Table 2 shows the average label prediction accuracies the test data for 5 random trials. One can see that GeoCrowdNet (Q=0) works reasonably well relative to the machine annotation case in the previous experiment. This may be because the number of annotators for both LabelMe and Music are reasonably large (M = 59 and M = 44, respectively), which makes W satisfying 4 become easier than before. This validates limitations of the plain-vanilla CCEM-tha is, it may require a fairly large number of annotators start showing promising results. Similar the previous experiment, both GeoCrowdNet (F) and GeoCrowdNet (W) outperform the unregularized version GeoCrowdNet (A=0), showing the advantages of the seiifiaablity--ehhneihi regularization terms. More experiments and details are presented in Sec. N due to page limitations.
Assumption
claims in Theorem [ but also shows the
6 CONCLUSION
In this work, we revisited the CCEM criterion-one of the most popular E2E learning criteria for crowdsourced label integration. We provided the first smite-sample identifiability characterization of the confusion matrices and the neural classifier which are learned using the CCEM criterion. Compared to many exiting identifiability results, our guarantees are under more relaxed and more realistic settings. In particular, take-home point revealed in our analysis is that CCEM can provably identify the desired model parameters even the annotators are dependent, which is surprising but favorable result. We also proposed two regularized variants of the CCEM, based on the insights learned from our identifiability analysis for the plain-vanilla CCEM. The regularized CCEM criteria provably enhance the identifiability of the confusion matrices and the neural classifier under more challenging scenarios. We evaluated the proposed approaches on various synthetic and real datasets. The results corroborate our theoretical claims.

---

Published as a conference paper at ICLR 2023
This work is supported in part by the National Science Foundation under Project NSF IIS-2007836.
Acknowledgement.
REFERENCES
Devansh Arpit, Stanistaw Jastrzundefinedbsi,, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S. Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, and Simon Lacoste-Julien. A closer look at memorization in deep networks. In Proceedings of International Conference on Machine Learning, pp. 233-242, 2017.
Peter I. Bartlett, Dylan Foster, and Matus J Telgarsky, Spectrally-normalizedd margin bounds for neural networks. In Advances in Neural Information Processing Systems, volume 30, 2017.
Michael Buhrmester, Tracy Kwang, and Samuel Gosling. Amazon's s Mechanical Turk: A new source of inexpensive, yet high-quality. data? Perspectives on Psychological Science, 6:3-5, 02 2011.
Peng Cao, Yilun Xu, Yuqing Kong, and Yizhou Wang. Max-MIG: An information theoretic ap- proach for joint learning from crowds. In Proceedings of International Conference on Learning Representations, 2019.
Zhijun Chen, Huimin Wang, Hailong Sun, Pengpeng Chen, Tao Han, Xudong Liu, and Jie Yang. Structured probabilistic end-to-end learning from crowds. In Proceedings of International Joint Conference on Artificial Intelligence, pp. 1512-1518, 7 2020.
Hao Cheng, Zhaowei Zhu, Xingyu Li, Yifei Gong, Xing Sun, and Yang Liu. Learning with instance- dependent label noise: A sample sieve approach. In Proceedings of International Conference Learning Representations, 2021.
Zhendong Chu, Jing Ma, and Hongning Wang. Learning from crowds by modeling common confusions. Proceedings of the AAAI Conference on Artificial Intellignnce 35(7):583,-5840, May 2021.
Nilesh Dalvi, Anirban Dasgupta, Ravi Kumar, and Vibhor Rastogi. Aggregating crowdsourced binary ratings, In Proceedings of International Conference on World Wide Web, pp. 285-294, 2013,
Alexander Philip Dawid and Allan M Skene. Maximum likelihood estimation of observer error-rates using the EM algorithm. Applied statistics, pp. 20-28, 1979.
Li Deng. The MNIST database of handwritten digit images for machine learning research. IEEE Signal Process. Mag., 29(6))141-144) 2012.
A.A. Fedotov, P. Harremoes, and F. Topsoe. Refinements of pinsker's inequality. IEEE Trans. Inf. Theory, 49(6): 1 491-44999999 2003.
Xiao Fu, Wing-Kin Ma, Kejun Huang, and Nicholas D. Sidiropoulos. Blind separation of quasi- stationary sources: Exploiting convex geometry covariance domain. IEEE Trans. Signal Process., 63(9):2306-233 2320, 2015.
Xiao Fu, Kejun Huang, and Nicholas D Sidiropoulos. On identifiability of nonnegative matrix factorization. IEEE Signal Process. Lett. 2583):328-332, 2018.
Xiao Fu, Kejun Huang, Nicholas D Sidiropoulos, and Wing-Kin Kin Ma. Nonnegative matrix factorization for signal and data analytics: Identifiability, algorithms, and applications. IEEE Signal Process. Mag., 36(2):59-80, 2019.
Arpita Ghosh, Satyen Kale, and Preston McAfee. abuse detection in user-generated content. In Proceedings of the ACM conference on Electronic commerce, pp. 167-176, 2011.
Who moderates the moderators?: Crowdsourcing
Nicolas Gillis. Nonnegative Matrix Factorization. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2020.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016.
10

---

Published as a conference paper at ICLR 2023
Melody Guan, Varun Gulshan, Andrew Dai, and Geoffrey Hinton. Who said what: Modeling individual labelers improves classification. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), 2018.
Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
K. Huang, N. Sidiropoulos, and A. Swami. Non-negative matrix factorization revisited: Uniqueness and algorithm for symmetric decomposition. IEEE Trans. Signal Process., 62(1))221 2014.
Kejun Huang, Nicholas D. Sidiropoulos, Evangelos E. Papalexakis, Christos Faloutsos, Partha Pratim Talukdar, and Tom M. Mitchell. Principled neuro-fumctional connectivity discovery. In Proceedings of the SIAM International Conference on Data Mining, 2015.
Kejun Huang, Xiao Fu, and Nikolaos D Sidiropoulos. machor-free correlated topic modeling: Identifiability and algorithm. In Advances in Neural Information Processing Systems, pp. 1786- 1794, 2016.
Shahana Ibrahim and Xiao Fu. Crowdsourcing via annotator co-occurrence imputation and provable symmetric nonnegative matrix factorization. In Proceedings of International Conference on Machine Learning, volume 139, pp. 4544-4554, 2021.
Shahana Ibrahim, Xiao Fu, Nikos Kargas, and Kejun Huang. Crowdsourcing via pairwise co- occurrences: Identifiability and algorithms. In Advances in Neural Information Processing Systems, volume 32, pp. 7847-7857, 2019.
David Karger, Sewoong Oh, and Devavrat Shah. Iterative learning for reliable crowdsourcing systems. In Advances in Neural Information Processing Systems, volume 24, pp. 1953-1961, 201 la.
David R Karger, Sewoong Oh, and Devavrat Shah. Efficient crowdsourcing for multi-class labeling. ACM Sigmetrics Performance Evaluation Review, (1(1):81-92, 2013.
Ashish Khetan, Zachary Chase Lipton, and Anima Anandkumar. Learning from noisy singly-labeled data. In Proceedings of International Conference on Learning Representations, 2018.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of International Conference Learning Representations, 2015.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical Report, University of Toronto, 2009.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-25) 22224,2,,,, 1998.
Shikun Li, Shiming Ge, Yingying Hua, Chunhui Zhang, Hao Wen, Tengfei Liu, and Weiqiang Wang. Coupled-view deep classifier learning from multiple noisy annotators. Proceedings of the AAAI Conference Artificial Intelligence, 34:4667 4674, 2020.
Xuefeng Li. Tongliang Liu, Bo Han, Gang Niu, and Masashi Sugiyama. Provably end-to-end label- noise learning without anchor points. In Proceedings of International Conference on Machine Learning, pp. 6403-6413, 2021.
Shan Lin and Jingwei Zhang. Generalization bounds for convolutional neural networks. arXiv preprint, arXiv: 191.01991.. 2019.
Tsung- Yi Lin, Michael Maire, Serge Belongie, James Hays, Pictro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick. Microsoft COCO: Common objects in context. In European Conference on Computer Vision, 2014.
Qiang Liu, Jian Peng, and Alexander T lhler. Variational inference for crowdsoureing. In Advances in Neural Information Processing Systems, volume 25, pp. 692-700, 2012.
Shuying Liu and Weihong Deng. Very deep convolutional neural network based image classification using small training sample size. In Asian Conference on Pattern Recognition (ACPR), pp. 730-734, 2015.
11

---

Published as a conference paper at ICLR 2023
Andreas Maurer. A vector-contraction inequality for rademacher complexities. In International Conference on Algorithmic Learning Theory, pp. 7-13, 2016.
Maryam M Najafabadi, Flavio Villanustre, Taghi M Khoshgoftaar, Naeem Seliya, Randall Wald, and Edin Muharemagic. Deep learning applications and challenges in big data analytics. Journal of Big Data, 2(1):1-21, 2015.
Vikas C. Raykar, Shipeng Yu, Linda H. Zhao, Gerardo Hermosillo Valadez, Charles Florin, Luca Bogoni, and Linda Moy. Learning from crowds. Journal of Machine Learning Research, 11: 1297-1322, 2010.
Filipe Rodrigues and Francisco Pereira. Deep learning from crowds. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), 2018.
Filipe Rodrigues, Francisco Pereira, and Bernardete Ribeiro. Gaussian process classification and active learning with multiple annotators. In Proceedings of International Conference on Machine Learning, volume 32, pp. 433 441, 2014.
Filipe Rodrigues, Mariana Lourenco, Bernardete Ribeiro. and Francisco C. Pereira. Learning supervised topic models for classification and regression from crowds. IEEE Trans. Pattern Anal. Mach. Intell., (9)11)24099-222 2017.
Bryan C. Russell, Antonio Torralba, Kevin P. Murphy, and William T. Freeman. Labelme: database and web-based tool for image annotation. International Journal of Computer Vision, 77:157-173, 2007.
Pinsker M The information stability gaussian random variables and processes (in russian). Dokl. Akad. Nauk SSSR, 133:28-30, 1960.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithmss. Cambridge University Press, 2014.
Rion Snow, Brendan O' O'Connor, Daniel Jurafsky, and Andrew Y Ng. Cheap and fast but is it good?: evaluating non-expert annotations for natural language tasks. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pp. 254-263, 2008.
Ryutaro Tanno, Ardavan Saeedi, Swami Sankaranarayanan, Daniel C. Alexander, and Nathan Sil- berman. Learning from noisy labels by regularized estimation of annotator confusion. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 11236-11245. 2019.
Panagiotis A Traganitis, Alba Pages-Zamora, and Georgios B Giannakis, Blind multiclass ensemble 2018.
classification. IEEE Trans. Signal Process. 66(
Donna Vakharia and Matthew Lease. Beyond AMT: An analysis of crowd work platforms. Computing Research Repository, 2013.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices, pp. 210-268. Cambridge University Press, 2012.
Kerri Wazny. "Crowdsourcing" ten years in: A review. Journal of Global Health, 7:020602, 2017.
Hongxin Wei, Renchunzi Xie, Lei Feng, Bo Han, and Bo An. Deep learning from multiple noisy annotators union. IEEE Trans. Neural Netw. Learn. Syst., pp. 1-11, 2022.
Peter Welinder, Steve Branson, Pietro Perona, and Serge J Belongie. The multidimensional wisdom of crowds. In Advances in Neural Information Processing Systems, pp. 2424-2432, 2010.
Jacob Whitehill, Ting fan Wu, Jacob Bergsma, Javier R. Movellan, and Paul L. Ruvolo. Whose vote should count more: Optimal integration of labels from labelers of unknown expertise. In Advances in Neural Information Processing Systems, volume 22, pp. 2035-2043. 2009.
Xiaobo 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, volume 32, 2019.
12

---

Published as a conference paper at ICLR 2023
Xiaobo Xia, Tongliang Liu, Bo Han, Nannan Wang. Mingming Gong, Haifeng Liu, Gang Niu, Dacheng Tao, and Masashi Sugiyama. Part-dependent label noise: Towards instance-dependen label noise. In Advances in Neural Information Processing Systems, volume 33, pp. 7597-7610, 2020.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNISTT: a novel image dataset for bench- marking machine learning algorithms. arXiv preprint, 1etXiv:1708.0711 2017.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In Proceedings of International Conference Learning Reprexentations, 2016a.
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. In Advances in Neural Information Processing Systems, volume 33, pp. 15750-15762, 2020.
Yuchen Zhang, Xi Chen, Dengyong Zhou, and Michael Jordan. Spectral methods meet EM: provably optimal algorithm for crowdsourcing. Journal of Machine Learning Research, 17(102): 1-4,, 2016b.
Zhaowei Zhu, Jialu Wang, and Yang Liu. Beyond images: Label noise transition matrix estimation for tasks with lower-quality features. In Proceedings of International Conference Machine Learning, volume 162, pp. 27633-27653, 2022.
13

---

Published as a conference paper at ICLR 2023
Supplementary Material of Deep Learning From Crowdsourced Labels: Coupled Cross-entropy Minimization, Identifiability, and Regularization"
A NOTATION
2, æ, and X represent scalar, a vector, and matrix, respectively. [a0] and (x)) both denote the
ith entry of the vector æ. X (:, denotes the jth column vector of X and X (i.:) denotes the ith
row vector of X. X and X (i. both mean the (i, entry of XX. [x La212 and |X || mean the
Euclidean (Frobenius) norm of the augment. [7] means an integer set {1, ...., T}.
denote transpose.
Ax {o RR Σ, x<i)= = 1, 0} denotes the probability simplex. X 2 0 implies that all the entries of the matrix are nonnegative. [[A] denotes an indicator function for the event such
that [[A] = the event A happens, otherwise [A]] = O. CE(x, y) > Bly = k) log (k)) denotes the cross entropy function. Iι denotes an identity matrix of size x K. m (X) and min (X) denote the largest and the smallest singular values of the matrix X, respectively. cone (X) denotes the conic hull formed by the columns of the matrix X. det(X) represents the determinant of X. (ec(X) denotes the vectorization operation that concatenates the columns of X. trace(X)
Zk=1
outputs the trace (the sum of the diagonal elements) of X.
B PROOF OF THEOREM
If the vectors pl for all m, available, then one represent the model in 2 low-rank nonnegative matrix factorization (NMF) model as follows:
P1
(1)
Px
(1)
A
:
:
(
f(NN)]
(10)
PN
(M)
AM
FERKXN
PERMKXN
WERMEXK
where the factors W and F are both nonnegative per their physical meaning.
((m) Let Pa denote the ground-truth and p
E RK the (m, n)th block in ph, following the representa-
a(m) tion TT)). Note that we do not observe the entire på but only the yn sampled from pa ((m) for (m,n) S. We first show that the CCEM criterion in (6) implicitly estimates p from incomplete
labels indexed by S. To this end, we consider the objective function in (6a):
K
Ds Ds S
Σ
[itt = k) log P(mm - 1)K + k,n).
(11)
(m. k=1
where D denotes the set of observed noisy labels, i.e., (Dl (m.))E. Let (Am Jm=1 and f denote the estimates given by the learning criterion (6). Then, the criterion (6) helps define the following term:
J.M
P arg min Ds(P:
(12)
PEP
where P= W [f(21) f(æN)), W W= [
ATI.
f(zN)) W E E, fEF). A (W = [[T...,, AT E MKXK A = - Am 2 0, Vm),
a MMKN P= (f(z)))
} is the neural network function class. FC (f(x) ERK f(x) E Ak, Vo E CRD)
Our main goal is to characterize the estimation emoos of {A bounding the estimation error 2(m)
J.M m= and f. This can be done via first
Pn 12, where pa
(()) is given by:
p(m)
fxx,) Vm,n,
in which A and fü denote the mth ground-truth confusion matrix and the GTP, respectively, and (m) denote the (m, n)th block in P.
14

---

Published as a conference paper at ICLR 2023
B.1 ESTIMATING (pp.).)) -
We first show the following proposition:
Proposition 1 Under the assumptions in Theorem !
the following result hold with probubility at
least 1
8:
M 11 4V2K599s(P) 10 (B) 2 (4/6)
Ip
m(m)
+ 233KK, (13)
NM
VS
m=1
where Rs(P) Rademacher complexity of the set P under the observed samples S.
16
MK log (4SVK) |1 and is related to the empirical
/
The proof is provided in Sec. Proposition
I provides an upper-bound for |P - PIE To achieve the main goal, i.e., characterizing the estimation errors of (Am JM m== and f. require upper-
bound for Em=1 m==
MM
P
b(m)
pn. p!,n)13 as well. The following result gives a tighter upper bound for
Σ
Em=1
M
Pn
((m)
m))
Proposition 2 Under the assumptions in Theorem for any a > 0 and d E (0, 1), the following result holds with probability at least N
1 M
Σ
(m)mm)
/2 log (4/5)
46) -6)) Vn, (14)
S Na
(V22339s(P)) + 10 (B)
2BV Kv Kv+ 46
VS
where Rs(P)
16 /
MK (45KK) X 1r)
The proof is provided in Sec. [ Note that the bound in 14 looks divergent at the first glance, as the second term in the R.H.S. could go to infinity. However, given large enough S, can choose appropriate a and 8 such that the bound in (14) does not explode.
B.2 ESTIMATION ERRORS FOR Am ANDF
In this section, we characterize the estimation error of the confusion matrices and the GTP. We start with using simplified notations to represent the results in Propositions i.e.,
| P
c²
(15)
M
(
((m)
D
(m
S 2², Vn.
(16)
with probability greater than - 5 and 1 respectively.
Assumptions 4 imply that there exists index sets = {m mx and v (ii..... Axx) such that:
w Ix + Nw
F' ('(, IK + NNe.
where ||wlep & VK5, and ||r||F & VKtz. Note that the conditions do not require any confusion matrices to be near identity; i.e., do not need any annotators be all-class specialists.
15

---

Published as a conference paper at ICLR 2023
Nonetheless, for notation simplicity, let A (l..... } and vr fl...., K]. which is without loss of generality for our proof in the sequel. Under this simplification, the following holds:
A
A
W
F
(f)()))
f(xN)]
[F]
Eg]
A M-
where A = Ix + Nw, F = Ix + Nr. and F E RKx(N-R), ||Wwll S VKGi, and
|| S v 22
Let Am and f denote the estimates of A and fa, respectively, using the learning criterion 6 and construct
Å
A
W
F F=
(f(r)
f(xN)]= = [F E2).
A
where Am E RRXK F1 E R and Fr E RKx(N-R), Then, we have:
ph P1 = :| WFIF
I + Nw + No + NW F + 1 Nw F
A + N Fi
Σ
1 A. 12
(17)
m=
Let us define the error matrices as below:
E A o
[K + Nw)II II, ((m)
& A. A Vm > 1,
(18)
A
A
E
(1) A F
II Nr), E A F2 II F
(19)
IFF:
where II [0, 1] is column permutation matrix and is the same across all the error blocks. We hope to characterize the norm of these error matrices.
Upper bound for | || and | (1) I|=-
We start by considering the first term the R.H.S.
of [7), ie.. | + Nw NF + Nw NN F lR. From (6),, we have the following with probability greater than :
2² > I + Nw + NF + NW A
1+ A( (.AARRA))))
ΣΣ - - A.G.))()))))
(20)
1=1
where N Nw +N NF. The absolute value of the largest entry in N can be bounded by E + VKE Let us denote vp E + &a + / KKg for conciseness. Then, from (0). we
get the following conditions:
A :) (c, b3
K, 4k E [K]
(21a)
A (k: F (:. j)l & K, vk * マ j.
(21b)
From the conditions (21a) and 21b). have the following result:
16

---

Published as a conference paper at ICLR 2023
Lemma Assume that the conditions in 21ab and (1bb hold and that S K+1. Then, we have the
following relations satisfied:
Srg max, M A, () + arg max, Ai(j,)), 4k i
(22a)
Brg max, , F1 (q. k)) * arg max Fi(q.j), Ak )
(22b)
arg max, A (k. E) arg max Fi (q. k), vk.
(22c)
The proof of the lemma is given in Sec. F
From the lower bound condition in 2la we have the following result:
K
K À (k, (1, + +.. (,, K)
k)
K
[ A1, ()kk, (1, A
+... +1. (K)
km
| (k,
(23)
where the last equality is obtained due to the probability simplex constraints on the columns of F. From the lower bound condition in 21a), have the below result well:
K
K
(k, () + ....
(,(K
k=1
k=1
K
max; (ks (1, +... (KK)))
K
max; Fi (k)
(24)
A=1
where the last equality is obtained due to the probability simplex constraints on all the columns of Á,.
Next, we characterize the term E 1 To achieve this, by employing the result 22a in Lemma
we fix the column permutation II as follows:
1, j j= arg max, A (k:
II k)
(25)
0, otherwise.
17

---

Published as a conference paper at ICLR 2023
We get the following set of relations:
K (kb,)) e 1
|
I
11
2
km1
K
Σ 1kik; KK- K-2 Σ Ai (k, ex
K
| 11 + K - Σ
A (k, IT ek
k=
22K
2
A (ki, IT. ek
k=1
(0)
2K 2
max (k,E)
(0)
K
S
2K
(1 k)
=K
k=1
where the last inequality (b) is by
23 and the relation (a) is obtained by choosing II as defined in
25
Hence, we have the following with probability greater than 1
K
No
E 11
F
S
|
Ix Ix
||/ V2K + VKGI
(26)
We proceed to consider the error term
| ||3. To achieve this, consider the following:
K
F
II
L 1
(k, :) e II T 1
k=1
Σ
i (12 + K - Σ
i (k;)) ea
K + - Σ
= A
fk, (IT,)))TT. ek
Jmm1
K
< 2K 2
II es
k=
K
2K 2
max F1 (k:
(6)
K
< 2K 2
(1 - R3) = 2KK,
where the last incquality (b) is by 24 and the relation (a) is by combining the definition of II in 25 and 22c in Lemma Hence, we get the following with probability greater than N=:
|| < F I F NN S V2Kk + VKE2.
(27)
18

---

Published as a conference paper at ICLR 2023
Upper bound for E ||.. Next, we consider the second term in
17 i.e. || | + NN F2 A F2lFF.
From (5). we have the following with probability greater than d:
Ç F + F
F2lel
Fj + Nw F (I
Nw II E E (2) II Fille
(IxIII + Nw II + E
E 2) + E
I II F2ll
A EE4 II F ||F
IV@ V33 IVS.
| E (2) F
||I - |E F ll
Omin ( E |E || 2
min
|F (V2KK + VEei
(28)
where the inequality (a) is by using the triangle inequality, (b) is obtained by applying the following two relations for any two matrices A E RK*K B E xR L 2 K
|| |B F 2 min (mmii(A)l (A)
(29)
AAB
I || | B|rr.
(30)
The inequality (c) obtained by applying 26
Hence, 28 combined with the fact that
Fg ||
F || gives the following relation with probability
greater than 6 8
K
Na
C + (V2Kx VKEI) F
S
(31)
Mmin (Ai)
Next, we use the following lemma characterize min (A
Lemma Suppose that the matrix X E RRKK takes the form X IK + E₁ + Ez, Assume that | S and |Ea]|r v2. for cerlain U1, 12 >> O. Then, have
min
X
2 - U1 U//-
The proof is relegated to Sec. G Applying Lemma than - K
2 we get the following with probability greater
< +
2KK v KE
C1(S + / KR F'
E
F
(32)
V2K= R
KRi
for certain constant C₁ 0. where we used the fact that & S Vn since k = E1 E2 + VKE and and < 1.
Upper bound for | lle, > 1. We consider the third term on the R.H.S. of (17. From 16...
for each m, we have the following with probability greater than 1
K Na
V K 2 | + N A. FilF = || i
+
A N
(A;, II +
E (m)
XII I + +II NF + E ll
E
Ix II
Nr
E + A ITE! ||
E
IE !1)
A m
IE!! p
||
IVS I
(FIILE
(m) || Tmax (A E
mmin
Jmin (f || (V2Kk+ + K max (A
where the relation (a) by the triangle inequality, (b) is by applying
29 and 33 and (c) is via 27
19

---

Published as a conference paper at ICLR 2023
Hence, Vm > get the following with probability greater than 1
2K Na
VK++ (V2Kk + ( (A
C2V K max (At m
m
(33)
1 V2KK - 2v
|| VKr
for certain constant C2 O, where we used the fact that S VK and & S vK since K = 4 E
E2 + VI and K < 1. In the above, have also applied miin (F1) 1 v2KK 2v K
following Lemma 2 and (7
Putting Together. From
33
we have the following with probability greater than 1 -
2K.
No
G2K2K
Am
A S
Vm.
(34)
A
VKk|2'
where we have used the fact that Fmax (Aa)
A 11e S V.
Similarly, by combining 27
and
32 we have the following with probability greater than 1 1- 5 2K
N
II
Ft |
E 1
1
(V2KR + VK + E + KR| VK F211E)²
1 VKx22
s asS VNKK)²
(35)
vknl2
for certain constant C3 > 0, where we have used the fact that || S VN.
We hope to characterize the generalization performance the predicted function f from 35 Towards this, we have the following result:
Lemma 3 Under Assumptions Hand? 2 the following holds with probability greater than 1 8:
EnND [11((z) II (x))) I
F
64N-444-5 5/8
N
2log(4/8)
16V
(36)
N
The proof given in Sec.
H
Hence, combining Lemma with
35
have the following with
probability greater than
28-
2K N
ca(C + 2
2 2og (4/8)
EAND [1f(z) - II (x)
+64N X BB) :
+16/
N 2
N
(37)
where
K xSp+2VK((i+E)
/2log (4/6)
(P) 10NM (8)
+ KNMBKKy
VS
V2 (4/5)
6² < 4V MK (P) + 10. (B)
VS
16
Rs (P)
MK log
4SvK + [2 2
VS
satisfied only if k. S - given by Lemma This gives the final conditions on E1. Ez. V, and S. By letting = J. we obtain the final results in Theorem 1
Also note that the final bounds in 34 and (37)
20

---

Published as a conference paper at ICLR 2023
C PROOF OF PROPOSITION 1
Let us consider the following notation:
P P(w) (m)
(38)
where (m, n) [M] i... P(w) "reads out" the (m, n)th block in 10 We also define
(w) = "!." With this notation, we have
s (E(()
Ds(P:
=
8=1
where CE(x, y) = Ex
1 Dly k) (og(((())) S |S|, and W. (m. E S. Under Assump-
Lion] we can define:
M
Du(P, 5) A Es-[(C((P(w)) (W))) =
Σ Σ
(m)
CE(p, (m/) (1hh))
An
where II denotes the uniform distribution and (m) annotation for the index pair (m, n²).
NM denotes the probability of observing the
Eq. implies
Ds Ps(P)) S Ds(P:))&Ds(PP Ds(P:)),
(39)
where P is defined using the following construction:
p= W [f(m)
f(xx))
and f is learning function constructed under Assumption 3
To be specific, f satisfies
[[(x)) f*(x))la S v. D.
Hence, by taking expectation w.r.t. D we have
E[Pn(P:)) - Dn(P': E[Pn D) Ds PP(P)) + Ds(Pt: E[Dn(Pt; 50)
+ DDs(P:)) Ds (P:)) Ds(P: Ds(Pt: 57)
E(Di E(Dm(P::)) - Ds(P: + Ds(Pa:)) - E(Dr (Pt;
+ Ds (P:)) - Ds(P
Ds(P:5) EiDn (P: (P: + +|/ -EINEEEDD 5>
< sup PEP
( Ds (ss; -Ds(P:))
(40)
where the first inequality is obtained from 39 Let us consider the L.H.S. of (40):
E
Dm(P::)) Dm (P::))
(m)
pa 1)K k. log P((m 1)K + k,
+ ((m
1)K + k, n) log Pd (mm 1)K + ki n))
N
M
K
Pi( 1)K + k,n) log Pa((m 1)K + k. k)
(m)
P((m - 1) + k, n)
#=1
m=
k=1
DKL
[pt
(41)
21

---

Published as a conference paper at ICLR 2023
where expectation is taken w.r.t 5 (while taking expectation, used the uniform probability Tn (m)) NM V, n, m for observing each annotation gllm) and used the ground-truth probability Pi((m 1)K k n) for each event [[ k)) and DKL DKL(P: ( P) is the average Kullback- (KL) divergence between the entries of the matrices p and P E RMMKNN which is given by
N M
DKL Pt
Σ
DKL (p , p(!)))
NM
n=1 m=11
Upper-bounding the first term the R.H.S of (40).
Next, we characterize the first term on the R.H.S. of (40). To achieve this, we invoke the following theorem (Theorem 26.5 in (Shalev-Shwartz
Ben-Davis 2014))
& Ben-Davinn 2014 Theorem 26.5) Assume that for all y and for all we have CCE x: y) S 2max- Then for any E P. the following holds with probability greater than
Theorem 4
1 6:
2log(4/6)
Ds(P: - E[Dn(P::))) -S(P.))-EID((PP))))
s 2 42max V
(42)
S
where denotees the set
topoS a {CE(P(())) M(LI))........ CE(P(ws) Muss))
P PEP]
and Rx( denotes the empirical Rademacher complexity of the set X.
To apply Theorem 4 will characterize Rs p S) which is defined follows (Shalev-Shwart/
& Ben- David 2014:
Rs o Po
sup PEP
o, CE((((..):
(43)
where expectation is w.r.t. the independent Rademacher random variables o, E (-1, Note that P(w) is vector-valued [see Eq. [38)] Hence, we invoke the following contraction result to upper bound Rs(E o P S):
Lemma Maurer 2016) Let P be a class of mappings (P: -RK),, where be any set and (Wi,.... wS) E XSS Also assume that & IRK - IR has the Lipschitz constant L. Then
E
sup PEP
Σ c.((P((w))) S V2LE
sup Σ (L..P((W)) PEP 8
where Pu(w) denotes the kih component of P(w), Jsk is an independent (doubly indexed) Rademacher random variable and the expectations are laken w.rl. the Rademacher random variables.
Let define vector & (P)))) (P)())))))) ..... (.)( (w.w)) E RSK and the set Z A
{z = (Pi(w))..... Pk(w))) P P PEP.. With these definitions, we apply Lemma 4 in (43 and
obtain
V23
Rs(lo P PoS)
sup Σ T. PEP 5,k
5
-22 E
sup
Σ
0i2(1))
FEZ
-28K
1
E
sup Σ 01)
(28KRs(2),
(44)
SK
ZEZ
where /3 is an upper bound the Lipschitz constant of the cross entropy loss function CE(::y) -Ek Bly = k] log ark) when æ E A with æ(k) > (1/3). Vk.
Next, will characterize Rs (2) using the covering number of the set 2.
22

---

Published as a conference paper at ICLR 2023
Definition 2 /Vessynnn 2012 The e-net covering of the set Z (denoted as Z) is a finite subset of Z (i.e.. - 2) such that for any & E Z, there exists an Z satisfying -| 2 I c. The smallest cardinality of the e-nets of Z known as the covering number of Z, which is denoted as N(e, Z).
Let us consider pair of vectors 2, 2 below:
(P (w1) ................................ Px (wa)) E RSK P(w,) Fm,.A.FFFFF... F(:
(w1) (w.)...... ..... Px (wa)) RRSK, P(ws) A,, Fl,,
where wis (mg, nz) and all Am: Am, F, and F satisfy the nonnegativity constraints and have unit --orr the columns. Then, have
2 - 21/ =
Amm F() F..
n
Amm F(: Am, Ft:nn,)l2
Amm F() Am, F(i, + Am, F(;, (s) Am, F(:, n2)l2
|| ((: 11 1|Am F(; F(,, n.)ll
==1 || Am,lle + VK Σ
-F -
#=1
where the first inequality is by ||0|| S | if the entries of æ are smaller than 1. The second inequality is by triangle inequality. The last inequality uses the fact the Frobenius norm of Am 's are bounded by VK and the & norm of any column of F is bounded by 1. Hence, to obtain an e-net covering for the set Z (i.e.) > ø S E), only need to show that there exists =² nnet covering 2/K
for S and - -net net covering for each Am since
s
Σ
VK
=
25
2/K
==1
Here F S denotes
Fo = [[f(x..)) ).... f( ) E RKx f F
where (m,, n.) = WP E S. Note that the full rank matrix Am RR can be represented as
-"=ddimesionnal vector whose Euclidean norm is bounded by VK. Hence, the cardinality of the
K²
29 25-net
2²
nnt covering for Am RRKKK is at most [SSVKK
Shalev-Shwartz & Ben-David 201 4).
Next, we consider the covering number corresponding to the function class / S. Using Lemma 14 of Lin & Zhang 2019), we get the cardinality of the net covering for F S as below:
2VK
2 FoS)
22K X R
S exp
2
E2
where X [ Ønsl E R and the parameter By is from Assumption 2
Using the covering number results, the cardinality of the E-net covering of set Z is bounded by the following:
MK²
4SKVK g2
2 K
X
N(s, 2)
exp
(45)
Now that we have characterized N(e, 2), we invoke the below lemma to obtain the Rademacher complexity Rs(2):
23

---

Published as a conference paper at ICLR 2023
Lemma 5 (Bartlett al. 2017 Lemma A.5) The empirical Rademacher complexity of the set Z with respect to the observed set having size SK is upper bounded as follows:
4a VSK
12
rV3
Vlog N(,, 2)dμ
Rs(Z) S inf a20
(46)
SK
We apply 45
in Lemma
and obtain
4a
12
Ss 23)
inf a>0
VSK log N(a, 2)
VSK
SK
4a
12
4SKVK
2v 2v 1
inf
MK log
+
020
VSK
VSK
a²
a
12
MK2 log (SSVK) + (2||X 1x))
VS
VSK
MK log (SSKK) + X 1F)
(47)
VS
In the above, the first inequality (a) is obtained using the relation
VSK
log N(H, Z)da s VSK V log N(a, 2),
which holds because V log (u, 2) decreases monotonically J increases. The inequality (b) is
obtained by applying (45). and (c) obtained by fixing vK which is smaller than vSK.
Combining the upperbound of Rs{ (2) given by (47) with the upper bound of As P P as given by (44) and with the result in (42) get that with probability greater than 6,
2 log(4/))
E
s 2V23KRRs(2)) + 42max
(48)
S
where Rs(Z) is upper bounded by (47) and 2max the upperbound the value of the function CE(x, y) which can be characterized as below:
K Uly k] log (k)) < max
max CE(æ, u) < max <<))>>
log log(3). (49)
2max
(<))>
k=
<>
ыЕ[K]
μE[K]
Upper-bounding the second term on the R.H.S of (40). Next, we proceed to upper bound the second term the R.H.S of (40). Let consider the Hoeffding's inequality
Lemma Let Zi,..., Zs be independent bounded random variables with Z, E [zmins Zmax] for all where 30 < Zmin 2max < X.. Then for all I. 2 O,
s Σ ==1
2St²2
Pr
(2.- 21 S exp
(2maxx 2min )2
To use Lemma 6 let us define the random variable Z(m) as follows:
((m) CE(p)(m) ((7)),
where Pr At f The maximum and minimum values of (m) are 2max log(3)) (see
a(m)
49
and Zmin = O, respectively. Then, invoking Lemma 6 one can obtain
Pr (Ds((P::))) (P 100--E-p0 E[Pn (P); 2 exp (- ([log())))
2512
(50)
24

---

Published as a conference paper at ICLR 2023
l+)(+)
Hence, by substituting = log (3) greater than -
where 8 E (0,1) 1) in (50), we get that with probability
28
log (3)
Ds(P: 5) (((n((((())))) = log (8) V
(51)
25
Upper-bounding the third term on the R.H.S of (40)
Ds((P:) Ds( Ds((P::))
[0 = k] kllog P((m - 1)K + k)
(m, k=1
K
10 = log Pa(m - 1)K + k.
S
(M, km
K
Up = log(A!, f( f f(x
5
(m,n)ES k=1
k=1
K
Σ
[ k|p ( f(en)
(m,a)ES k=1
K [ptkm)
113114 (f):))))l) f(xr))l2
5
(m,a)ES k=1
< SBVKV,
(52)
where the first inequality uses the triangle inequality, the second incquality uses the Lipschitz continuity of log function, the third inequality via Cauchy Schwartz inequality, and the last inequality employs Assumption 3
Putting Together. Hence, by combining the result in 48 with that with probability greater than 25,
40
51
and
52
we get
llog(4/8) log (3)
log
DKL pt P < 2V23KRs(22) 3))
V
+ BVKu. (53)
S
25
Using Pinsker's inequality S
1960 Fedotov et al.
2003)
we get
N
M
DKL (t Pp
DkL (m)) -
h(m)
P p(m)
NM
2NM
N
M
2
2
12
mmml
where the last inequality uses the fact that ||a||] 2 || The above relation combined with (53) implies that with probability greater than 1 - 28:
M
pi 4 4v (2 10 10 (B) V 2 (4/8)
Ip
+ Kv, (54)
NM
VS
m=!
where Rs(Z) ) upper-bounded in
D PROOF OF THEOREM 2
The proof of Theorem Theoremmutillzess utilizes some key results from the proof of Theorem We start by employing the result from Proposition 1 Let us fix and in the result of Proposition Then,
25

---

Published as a conference paper at ICLR 2023
implies that when f F, Le., 0, the limit + oc, we get the following:
Cit, N S C2t². for certain constants C1 C2 > 0 and
p P F 0,
with probability 1, i.e.
P= F
(55)
On the other hand, the matrix P can be constructed using the estimates of the CCEM criterion ( via
p= WF.
(56)
Hence, in order to identify W and F from the NMF model 55 we invoke the following result:
Lemma (Huang et al. 2014) Consider the matrix factorization model Z XXY, where X RI*K, Y E RRXX and rank x) = rank((Y) = K. If X. 2 0 and both X and Y satisfy SSC,
then any X and Y that satisfy Z XY must have the following form:
XIE,, TY
where is column permutation matrix and Σ a diagonal nonnegative and scaling matrix.
Next, show that Lemma 7 can be applied given the conditions in Theorem The matrix F (xm)) man..... ..., (xnz) includes a subset of columns of F²,, i.c., cone F C cone(F*).
Hence, we have
C C cone (F2) = C S cone(F*).
(57)
where C (x E RRR
-
|||||2 S 1xx is the second-orde cone.
Also for any orthogonal matrix Q E R x
K except for the permutation matrices, the below holds:
cone F (Qne
cone( F cone(Q).
(58)
Eqs (57 and (58) imply that Få satisfies SSC, given the assumption that F2 satisfies SSC. In addition, the column scaling does not affect the conic hull, i.e,
cone F*) cone -- PF)),
cone( W cone EW:T)
Since both W and F satisfy SSC, rank [F) rank W*) K hold (see (Huang al. 2016
Hence, the conditions Lemma] holds for 55) Comparing (55) and (56) and invoking Lemma get
W'II.
(59a)
== F
(59b)
where the scaling Σ is automatically removed due to the sum-to-one constraints on the columns of Am 's and F.
The first result (59a) implies that
Åm A II, Vm.
Applying the second result (59b) in Lemma along with the assumption that + co, we get
F FanD
[f((z)
IT f (=))
(60)
Fact 1 Let X be a nonnegative random variable with E[x] = 0. Then, X is zero almost surely, i.c.,
Pr(X 0) 1.
Employing Fact in 600.
get that
lf(z) II ( 0, D. = f(x) -I (2))
due to the nonnegativity of f and f.
26

---

Published as a conference paper at ICLR 2023
E PROOF OF THEOREM 3
To prove Theorem 3 let us first consider the CCEM criterion in (6) Let W and F be any optimal
solution of (6) and
p = WF.
(61)
From Proposition 1 by fixing 8 = $ and $/ and using the conditions in the statement of Theorem
3 i.e., S E F implying 0, S 2 Cil, N C2l , for certain constants Cı, C2 0, we get the
following at the limit of + oo:
p
P F 0,
with probability i.e.
P= W'
(62)
Proof of Theorem 3a) We consider the following result which distilled and summarized from the proof of Theorem in (Fu et al. 2015):
Lemma Suppose matrix Y E RKKx xJ satisfies Y 2 0, 1 = rank(Y) K, and SSC.
Then, for any Y QY satisfying Y 0.1 T,, the following holds:
|dtt(Qu (Q)) S 1,
The equality holds only if Q a permutation matrix.
Let us start by considering the following criterion:
maximize (ct(FFT) W.F
(63a)
s.t. P = WF
(63b)
F 2 1
(63c)
where P is the optimal solution from the CCEM criterion
66 and hence, as shown before, P satisfies
62
Let W and F* be optimal solutions of (63) then the following holds:
det FFF det (F Ftt
(64)
From 62.. we observe that W and F satisfies W = W'Q F' = QF for certain invertible matrix Q. Let assume that Q not permutation matrix, Then, have
det F* F* det(Q F't Ft Q)
det dett (e
< Fe
where the last inequality from Lemma using the SSC condition on Ft, Note that the result is a contradiction from (64). Hence, Q must be permutation matrix. This implies that the optimal solution W and F of Problem 63 satisfies the following:
W WII..
(65a)
F II Ft
(65b)
Following the last part Theorem
2 by using Lemma 3 and Fact I
we have
A m II, Vm.
f' II' (x)) Va D.
27

---

Published as a conference paper at ICLR 2023
Note that since log is monotonically increasing function, by using log Fet(FFF) in 63 in place of (F) does not change the optimal solution, yet keeps the objective function in differentiable domain (this is because, det(XX) becomes zero if X is singular). Hence, we can conclude that the following criterion
maximize log det(FF)) W.F
(66a)
s.t. P WF F
(66b)
(66c)
also results in the same optimal solutions W and F* satisfying (65)
Proof of Theorem 3[: We consider the following result which modified version of Lemma A.I from (Huang al. 2015):
Lemma Suppose a matrix X RRIK satisfies 2 0. 1 = p11, p> 0, (X) = K,
and SSC. Then, for any X XQ satisfying X
> 0,
1 p1", the following holds:
det Q) -
The equality holds only if Q permutation matrix.
Note that, in Lemma 9 we are given that 1 = =pl_. -hen, by multiplying Q on both sides, we obtain
1 T'Q p1'
(67)
Since 1 xQ pl1 also holds by the assumption in Lemma 9 combining with (67). get
p1 Q p1
1-Q 1
(68)
The result in (68) is used in order to conclude Lemma 9 from Lemma A. of (Huang et al.
2015
We consider the following criterion:
maximize det(W" WW) W
(69a)
s.t. P WF
(69b)
W 2 0, W = M1
(69c)
where we used the constraint W = M1 since 1 Am = 1 for all m.
Let W and F* be optimal solutions of (69). then we have:
det W - W") 2 det (eetWWtTy W*).
(70)
Applying 62
W* F" satisfies V W'Q. F = Q--1Ft a certain invertible matrix Q
Let us assume that Q is not permutation matrix, Then, we have
det(W W*) de T T
(e) det (et W
det T W*)
where the last incquality from Lemma 9 using the SSC condition on Wi which a contradiction from (70). Hence, Q must be permutation matrix. This implies that the optimal solution W and of Problem 69 satisfies the following:
W' WII,
(71a)
F" II F
(71b)
Similar to the last part of Theorem?
by using Lemma 3 and Fact we have
I
A A III Vm.
('(x) = II (=), ~.
In this case as well. the optimal solutions do not change if we employ log det W W) in (69) in place of det (WW W..
28

---

Published as a conference paper at ICLR 2023
Remark 2 Geometrically, Theorem 3 seeks maximum volume solutions w.r.t. the conic hulls of F and W respectively. One can also note that both cases of Theorem 3 the corresponding optimal solutions do not change if minimize log det ( in (63) and minimize log det(FF [ FF in
(69). However, relying on the SSC of F (W") and minimizing the volume of conic hull of W may be inefficient since p W Fc does not hold exactly in practice.
F PROOF OF LEMMA
Let us define some notations:
G arg max [K] Aik, E)
9 arg p [K] k))
Consider the following conditions given in Lemma !
A (k: (1) 1 K,, Ak: E [K]
(72a)
A kx vK j.
(72b)
F.1 PROVING & # oz. vk ÿj
We begin by noticing the below relation from 72a
(1 - x) - (k, 1) (L, + + Āi
I maxeE[K] A (k: (F (1, +... (i),
= A
(k; Ak,
(73)
where the first equality employs the probability simplex constraints on the columns of F.
We further proceed to prove by using contradiction. First, assume the below for certain k + j.
arg max, A (k, E) = arg max, Fi (g. = oj-
(74)
For (7bb) to hold, we need to satisfy the below for Under the assumption consider 72b
certain & + j:
À (k: f2 (1)5 < (4 1) < - k
K
where the last relation is obtained from
73
This also implies that
Ke
Filg. k) <
=
1 1-
1=1
1
R
+1 K
However, Lemma I Jassmmes that x - K+i Hence, the assumption (74) does not hold and we get
1
arg max, max,A1 (k, o arg max, (q. k + j.
(75)
F.2 PROVING E 0%. Vk
From the result in
75 we consider
72b for certain k + j.
Å (k. f Fi(g.)) Sx
Fi(g.)) <
K
+ 25.
(76)
29

---

Published as a conference paper at ICLR 2023
where the last relation is obtained from 73
Since E, (q 1, we get
Oo - Kr Vj.
(77)
From the result in 75 and the condition in (2b). we also have the following for a certain k +
j
1 (k. e) (9)- S n
x(1 R) l Eg.
(k, 1) 1 KK
(78)
where the last relation by
Next, we proceed to prove by contradiction. First, assume the below for certain k
0 + Tie
(79)
Hence, for each k, we have
A (k: :) (i( = Ai 1)F (1, k) + ... + A, (),
S Σ (i k) + A,k,, 2
(K 1)k x(1 kk
(80)
1-K
KE
where we have used the fact that all the entries of Å₁ and F1 are smaller than 1, the first inequality and have applied (76) and (88) in the last inequality.
The lower-bound condition (2a)) gives that for each k,
Ā (k, :) F1 A:] 2 k.
(81)
Then, comparing both
and
81 we hope to have
(K
1)
K
K +
V (K + -
2
K+1- (K+1)--4
K+1 which leads contradiction to assumption that Hence, the assumption 79) does not hold and we get
However,
K+1
arg max, A, (kc E) arg max, Fi k), Vk.
(82)
Combining both 82 and 82
we get
arg max A (k:, + arg max Ai(i, f), Vk jj
arg max, F (4, k)) j arg max, F (g. vk 4
G PROOF OF LEMMA
We have
Tmin (X) Umin(Ir + Ei + E2) min
[[ + Ei + E2)æ212
||
[ + (E1 + Eg)a112 (c)
min #||==1
min
||
[| + E2)x212
101==1
min
| 1|
max
E
Eg 22)0012
max ||a||==1
EE + E2)2112
==
||||==
(b)
1
E + Ez1la1
|1 - E || - 11 E2lle
(83)
30

---

Published as a conference paper at ICLR 2023
where the inequality (a) employs the triangle inequality, (6) is obtained via the matrix equiva-
Ience relation || E1 + Eg 12
E1
IF 1 | E2llE, (c) is obtained by the assumption Eg
that || Un and E2
U2
H PROOF OF LEMMA 3
First, let us define the following w.r. the loss function g y) = 115 3 A Ff IR and the input data X (I1....., .,N) where each on is sampled i.i.d from the distribution D under Assumption T
Lx(f) Σ g(f(an), f
Σ n=
lf(xn) II ( I
-
II
F'
Il
(84a)
LD (D( E I = EnND [1f(z)) II ((x))
(84b)
We invoke Theorem 26.5 in Shalev-Shwartz & 2014) and get that with probability greater than 6:
2 2lo((4/8)
Lo(f) S Ix(f) + 2g F) 10v
N
- EaND [1f() -I 11))
F + (F) 16
2 llo((4/5)
(85)
N
where the last inequality utilizes the definitions in 84 the contraction lemma (Lemma 26.9 from "Shalev-Shwart & Ben-David 2014)) and also applied ج 4 since (g(f. < 4 in our case. The term (xF) denotes the empirical Rademacher complexity of the neural network function class J which is upperbounded via the sensitive complexity parameter R, follows (Lin & Zhang 2019):
RN(F) S 16N 5/8 (2/ 1r.
I PROOF OF PROPOSITION 2
Our goal is to bound 1 Σ
k(m)
Pa [/ for each n. To achieve this, let us define the random
M7
m=
variable U NM ΣN Emez
M
h(m)
p! 113. From Proposition the following result hold:
Pr(U S (()) 2
where randomness is due to all wn 's Th ((m) s, and S and (5) is given by the R.H.S. (54)
Then have
Umax
((8) h(ujudu + Jaco) h(u)udu
E[U] J
h(u)udu
((() h(u)du + Umax
( h(u)du
Vanax
< 0(6)
J0(8)
< 05) + Umaxx
< 06) + 46
(86)
where Umax denotes the maximum value of the random variable U and is given by umax S 4 and h(u) denotes the probability density function of the random variable U.
Also, we have
E[U] =
Unl
(87)
N
where Un A 1 EM To proceed, we have the following lemma:
M
|
((m)
Pa
31

---

Published as a conference paper at ICLR 2023
Lemma 10 Let Un Em
Pm [pnm
2(m)
-in Then E(Un) = E(Un), V,n,n'
where expectation taken w.r.t all æn 's, gh"") 's, and S.
The proof is provided in Sec.
Combining Lemma
TO with 86 and (8 we get
E(Un) S d()) 46.
Applying Markov inequality, get the following for any
Pr(U, rE(U,)) 2 Pr(U, S TŪ()) + 4T8) 2
Letting 7 =
No, where < a < 1, we get that with probability greater than 1 - N
M
1
lp
h(m))
11 < N") + 4Nº8.
M
m=1
J PROOF OF LEMMA
Let us define the following:
M
u( D O on ux
Ip (m)) (pmm) 112
.
m=1
Ad
| f (xn) - f
M
m=1
where un (In. ( Jmes, Sn3 and denotes estimates {Am) and ff which are obtained using the data {VI,.... .n...., Un',... UN = (II...., ( DN. One can observe that for any n'' # n,
UN O w..., ts
(88)
since the order of vn does not affect the value of the estimates. Then have
F
[u(xn; P Parm "a
IF a " 23 Jænn.
[u( ① P. m
(89)
2n Fe 25 J=n.n
where the first equality is by (88) and the last equality is obtained since æ, and a, are identically distributed.
From
89
can obtain that
E (n θ Py....... ........ P. ww....
E [ul(En' O Oop Parm.. p..... "I.....EN
(u( Ou..... Pat ux
= EEz
[u(xn' Der...eer..........
Es
Eg
E
[u(xnn O
Es
E
[u(xw .
W1.....NN
B1....N
E [u(20,, ① o Wn......... wa
E [u(Ew ; O Our Po......
32

---

Published as a conference paper at ICLR 2023
A m, (1,:)
ei
A' (2,))
W
A m.
13
W
m, (3.:)
Figure I: (left) W = [AiT] J satisfying NCSA with K = 3, meaning that there exists specialists for each class & e [K] and (right) all-class expert annotator m among M annotators. meaning A Re IK.
Specialists for Class
61
C
02
C3
02
e2
NCSA (1)
NCSA (61> 0)
SSC
R
cone(W"i)
Figure The dots denote the rows of W and the circle denote the second-ored -odder cone C.
K MORE DETAILS ON THE COMPLEXITY MEASURE Ry
The work in (Lin & Zhang 2019 introduces complexity measure for measuring the expressiveness of different family of neural network classes. For example, consider a general convolution neural network (CNN) architecture with L layers such that
... on f(x) oz (L
(H))))
vf EF
where (.).) (o.())...,;:())
Rd: represents element-wisg activation function at ith layer satisfying (0) = and o, being p-Lipschitz continuous for all i. Let GF denote the set of layer indices with fully connected layers and Gc denote the layer indices with convolutional layers. If i Gr. we have % H = H. E x Suppose E Gc, then we have 7/s (
H 2;-1, where the matrix H; R contains convolutional filters each of which having dimension ri. z;-1 denotes the output the (i 1)th layer, and @ denotes the convolution operation. Here do = the dimension of the of the input data items vn, 's. Then, its sensitive complexity R is defined as
follows:
2 L2
Ee Egr de/c iEGc
SE
Note that such as a general CNN architecture covers many popular neural networks, e.g., fully connected neural networks, CNNs such as Lenet-5 (Lecun al. 1998), VGG-16 (Liu & Deng 2013 and so on.
L TEAR-CLASS SPECIALIST ASSUMPTION AND SSC
NCSA is a relaxed condition compared to having all-class expert annotators or having diagonally dominant annotators Fig. [ It can be understood that NCSA assumption does not require any single annotator to be specialists with respect to all classes. Nonetheless, having an all-class expert annotator m, satisfies NCSA, but not vice versa.
33

---

Published as a conference paper at ICLR 2023
The SSC [Definition is relaxed condition compared the NCSA (Assumption 4 To illustrate this, we consider the geometry of the matrix W satisfying the NCSA and the SSC as shown in Fig.
M ALGORITHM DESCRIPTION
In this section, detail the implementation of the regularized criteria in and 9 The neural network predictor function f E parameterized using and can be denoted as fo Rd A. Let
a vec A1) ..... vec( AM) vec(O)
Let us also define the following for certain batch B C [N]:
Lr(bb,B)
(i/k")) log] fo A log det FF"
B
NEB mES, k=1
K
Lw(bb,
[p!(m)) = log Amff(zz)l - Alog det W W
B
nEB mES,
k=1
where F= 1F=1f((m)) (f(n)) (Z )]s Bl...., [|8] and W [A] ..... ALI..
Let (ebr( B) denote the stochastic gradient of L (4b, B) w.r.t. ap and V (1b, B) denote the stochastic gradient of (w(,, w.r.t sb. Under these notations, the proposed methods GeoCrowdNet (F) and GeoCrowdNet (W) are described in Algorithm and respectively. The Python implementation of the algorithms is available in GitHut
Algorithm 1: GeoCrowdNes (F)
input Data {æn, )!(") m S, m==1
Initialize A., to identity matrices Ix;
Initialize the parameters O of the neural network function class F;;
v/- = [vec(A:)] T....................... ve)(AAs) T, vec(O)
while stopping criterion is not reached do
while stopping criterion is not reached do
Draw random batch Compute & db. B);
/ + AdamOptimizer( (bb, V Crbb,B))) for m 1 to M do
Am softmax(A...
softmax operation the columns of A...
11
end
12
end
13 end
output: Estimates Am, Vm, Ø
34

---

Published as a conference paper at ICLR 2023
Algorithm 2: GeoCrowöNet, (W)
input :ata {zn, Bl.") Sn
Initialize Am to identity matrices 1x:
Initialize the parameters A of neural network function class F;;
vb [vec(A:)".... vec(AAs) vec(0)
while stopping criterion is not reached do
while stopping criterion is not reached do
Draw random batch B:
Compute V Cw (sb, B);
< AdamOptimizer(p)) V..wwwwr (1b; for m to M do
Am < softmax Am)
D softmax operation on the columns of A...
end
12
end
output: Estimates Am, Vm, θ
13 end
N ADDITIONAL EXPERIMENTS AND IMPLEMENTATION DETAILS
N.1 SYNTHETIC ANNOTATORS
Dataset. We consider the CIFAR-I 10 (Krizhevsky 2009) dataset for synthetic noisy label experiments. CIFAR-10 10 consists of 60, 000 labeled color images of animals, vehicles and so on, each having size of 32 x 32 and belonging K 10 different classes, We use 45, 000 images for training, 5, 000 images for validation, and 10, 000 images for testing.
Noisy Label Generation. In order to produce noisy annotations for the images of the training data, we simulate M = synthetic amnotators. We randomly choose an annotator m among M annotators and its confusion matrix is generated by A Ix + arand K, K). followed by normalization the & norm of the corresponding columns. Here, I denotes the identity matrix of size K and rand(K, K, K') denotes the K x K matrix with its entries randomly chosen from uniform distribution between and The parameter 7 controls how well the annotator m correctly identifies the ground-truth truth labels. The confusion matrices of the remaining M annotators are generated such that they provide labels uniformly at random-i.c.. the M - annotators are all unreliable. This type of modeling for the confusion matrices resembles the hammer- works (Rodrigues & Pereira 2018: Tanno et al. 2019). Using the ground-truth label yn 's provided by
model as employed in the
p((")ss are produced. Each the dataset and the generated confusion matrices, the noisy annotations gh
annotation g(()) is observed independently random such that only 20% of the total annotations available for training. Note that, the true labels are not accessible by any of the methods.
Neural Network Architecture and Settings. For the CIFAR-10 dataset, choose the ResNet-9 architecture (He et al. 2016). Adam (Kingma & Ba 2015) is used as the optimizer with weight decay of 10 and batch size of 128. The regularization parameter À and the initial learning rate of the Adam optimizer are chosen via grid search method over the validation set from {0.01, 0.001, 0.0001} and (0.01, 0.001), respectively. We choose the same neural network structures for all the baselines. The confusion matrices are initialized with identity matrices for the proposed method and the baselines TraceReg and CrowdLayer.
Results. Table presents the results under various values of y-when is smaller, the chance of annotator m correctly labeling the data items better. One can see that the proposed approach, namely, GeoCrowdNet (F), outperforms the basclines in all the scenarios under test. When annotator m labeling accuracy drops drastically (i.c., when 7 becomes larger), GeoCrowaNet (F) performs the best. This implies that even if there no class specialists, GeoCrowdNet (F) works well under the large N cases.
Figs. 4 and 5 show the ground-truth confusion matrices and the corresponding estimates when 0.01 for the GeoCzowdNet methods. One can see all methods estimate the confusion matrices reasonably well, corroborating our identifiability claims.
35

---

Published as a conference paper at ICLR 2023
Table Average accuracy of the proposed methods and the baselines on the CIFAR-I0 dataset (K 10), labeled by M = 5 synthetic annotators.
Methods
0.01
0.2
0.3
GeoCrowdNNet (F)
84.82 0.43
71.66 + 1.08
67.97 1.44
GeoCrowdNet (W)
82.76 0.46
+ 0.50
63.86
1.64
GeoCrowdNet (A=0)
82.50 0.38
69.14 + 1.29
63.73 2.64
TraceReg
82.54 + 0.34
70.01 1.16
65.01 = 2.30
Crowdlayer
83.01 + 0.23
69.91 +: 1.48
65.70 2.32
MBEM
81.01 0.32
69.45 + 1.56
64.15 2.21
CoNAL
81.41 + 0.43
68.56 + 1.78
63.21 + 1.98
Max Max-MIC MIG
82.01 + 0.78
69.96 + 1.23
62.01 + 2.46
NN-MV
50.96 0.83
37.90 = 1.19
33.24 1.17
NN-DSEM
52.02 + 0.80
37.95 = 1.41
33.64 = 0.69
1.0
1.0
CO00 aeverr COMA coene cOMO C0MM 0:00 OUTT
OPG
3,00
IITS
0015
0.8
DOVD
CORT
D:EW 5/O0 031
Lodda copl 5-i0 SA00 sura
2014 coDu C/OW
60%
000
0611
save
2010
0.0
0.0
2
3
6
0
3
4
The ground-trute A. (left) and the estimate Amx (right)
1.0
0100
0.8
P9
21
DUBT
0.6
SUW
S11
COM
COR
EM
25
0.0
2
6
9
0
3
7
The ground-trute A3, (left) and the estimate An (right), m m
The illustration of the ground-truth confusion matrices and the estimated confusion matrices by the proposed approach GeoC rowdNet. (F) for CIFAR-10 dataset, with M 5 machine annotators and = 0.01. The average mean squared error (MSE) of the confusion matrices is 0.088.
Figure 3:
N.2 REAL DATA EXPERIMENTS MACHINE ANNOTATIONS
Here, we provide additional details of the real data experiments. For experiments with machine annotations, consider the MNIST and the FaSHi datasets. Each image in these datasets of size 28 28 the scale format. We consider 57, 000 images as training data, 3000 images for validation, and 10, 000 images for testing.
36

---

Published as a conference paper at ICLR 2023
1.0
o/1kk 2012 Sowe
0.8
0.8
TV
C-O0 100%
0.6
0.6
0.44
0.4
1000 0081 CONN 40000 1.00% CON60 C0050
1/M41 10003 0300
0.99
80000
0.2
0.2
JO cODD c:aN SUZE oUIZI comu
DER 20144
zoin cave
0.0
The ground-truth A (left) and the estimate Ame (right)
1.0
81
6:14
CCP
2/00
CUNT
0.8
0.8
2
2V
CCM
DXT
C201
COBI
2:11
CON
O31
CONI
0.6
0.6
SCD
SCW
0.4
0.4
X1
SODT
COM
115
0.M
0.2
0.2
2 AF
0t
o
af
COM
ROM
en
31
0.0
6
9
3
7
The ground-truth A (left) and the estimate A. (right), m + m
Figure 4:
The illustration of the ground-truth confusion matrices and the estimated confusion matrices by the proposed approach GeoCrowdNet (W) for CIFAR-I0 dataset, with M = 5 machine annotators and y 0.01. The average mean squared error (MSE) of the confusion matrices is 0.102.
For machine annotation, we train number of machine classifiers to act as annotators. In Table [ under Case 2, we choose M = 5 annotators. Specifically, Linear SVM, logistic regression, k-NN with & = 5, CNN with two convolution layers followed by a max pooling layer, fully connected layer and softmax layer, and fully connected neural network (FCNN) with hidden layer and 128 hidden units are trained. The CNN is trained for epochs and the FCNN is trained for 10 epochs. The classifiers are intentionally not well trained, that they mimic error-proning annotators. For example, for the MNIST dataset, the individual label prediction accuracy of these annotators on unseen data items of size N ranges from 15.88% 82.23% (averaged over 5 random trials) and 2 annotators have less than 50% accuracy on average. Also note that our algorithm does not know which annotator is more accurate.
For Case 2, we train more annotators by changing some parameters of the above mentioned machine classifiers. Specifically, we use linear SVM, polynomial kernel-based SVM, and Gaussian SVM as different variants of SVM. For k-NN, we choose & from {3,5, 7, 10). FCNN, CNN, and logistic regression are trained with different number of epochs (10, 15, 20, 25) and with random initializations for each case. Under case 1, if an annotator is chosen to be specialist, it is trained with more number of samples (10, 000 samples) with more number of epochs such that its label prediction accuracy is higher than 90%. Under this strategy, in Table for the case M 15, the individual label prediction accuracy of the anmotators on unseen data items of size ranges from 3.15% to 95.27% (2 annotators with more than 90% accuracy). For the case with M 20, the individual label prediction accuracy of the annotators on unseen data items of size ranges from 3.24% to 95.73% (3 annotators with more than 90% accuracy).
37

---

Published as a conference paper at ICLR 2023
1.0
0.8
0.8
0.6
0.6
SINN SO:A
0.11
0.000
0.4
0.4
1000 0081 CONN 40000 1.00% CONOA C0051
6/81 300 2,004
88077
0.99
0.2
0.2
JO cODD c-aH SUZEN
2:00 201M 0221
10M 20: coure
0.0
The ground-truth A (left) and the estimate Ame (right)
1.0
81
02M
0296
0.8
0.8
2
2V
011
012
OUNG
0.6
0.6
SUY
0.4
0.4
R1
OZT
COM
R12
0.2
0.2
2 AF
o a
COM
21
00R
000
cm
en
03r 6:
0.0
6
9
1 3
The ground-truth A3, (left) and the estimate Å. (right), m + m
Figure 5: The illustration of the ground-truth confusion matrices and the estimated confusion matrices by GeoCrowdNet (A = 0) for CIFAR-10 dataset, with M = 5 machine annotators and 7 0.01. The average mean squared error (MSE) of the confusion matrices 0.097.
Table 4: Average test accuracy (# std) of the proposed methods and the baselines on Mushion-MNIST" under various (N, M)'s Case 1; labels produced by machine annotators; p 0.1.
Methods
(1000, 25)
(750,30)
GeoCrowdNet (F)
82.81 + 2.05
82.40 = 1.51
GeoCrowdNNet (W)
83.33 + 3.39
83.65 = 4.11
GeoCrowdNet: (A 0)
79.43 + 4.07
79.07 = 2.91
TraceReg
80.79 3.87
81.12 4.03
CrowdLayer
6.55
75.56 = 8.19
MBEM
1.19+33.
26.67 + 3.45
CoNAL
03.13:8... 8.53
66.02 5.65
Max MIG
77.05 3.06
72.59 = 8.38
NN-MV
68.48 3.15
71.74 = 2.21
NN-DSEM
68.84 + 2.46
73.08 = 4.09
Additional experiment results using the MNIST and Fashion-MNIS datasets can be found in Tables 6 As expected, GeoCrowdNet (W) and GeoCrowaNet (F) offer the best performance in Case 1 and Case 2, respectively.
38

---

Published as a conference paper at ICLR 2023
Table Average test accuracy std) of the proposed methods and the baselines on MNIST under various (N, MM's on Case 2; labels are produced by machine annotators; 0.1.
Methods
(5000, 25)
(10000, 25)
GeoCrowdNeet (F)
87.26 + 0.70
87.66 = 1.23
GeoCrowdNet: (W)
84.64 +: 4.04
86.53 = 3.24
GeoCrowdNet (λ 0)
80.08 + 3.14
TraceReg
78.06 6.72
86.85 = 5.45
CrowdLayer
4:
56.66 = 6.34
MBEM
4
21.82 6.54
CoNAL
46.35 6.75
46.86 = 5,43
Max MIG
83.34 +: 1.54
86.84 = 2.13
NN-MV
83.46 + 0.67
83.32 = 1.34
NN- NN-DSEM
84.37 + 0.70
83.78 = 1.11
Table 6: Average test accuracy (# std) of the proposed methods and the baselines on Fashion-MNIST under various (N, M)'s Case 2; labels produced by machine annotators; p 0.1.
Methods
(5000, 25)
(10000, 25)
GeoCrowdNee (F)
87.47 = 0.86
88.39 1.92
GeoCrowdNet (W)
85.80 = 1.26
87.09 + 2.71
GeoCrowdNet (A 0)
85.58 = 2.23
85.37 = 2.59
TraceReq
85.20 2.36
84.02 2.74
CroweLayer
70.07 7.19
74.92 6.19
MBEM
42.15 + 3.65
44.34 3.48
CoNAL
4.94
62.65 7.02
Max MIG
83. 33 2.09
85.94 1.93
NN-MV
79.85 + 2.88
83.53 1 1.53
NN-DSEM
81.34 1.65
84.67 1.15
N.3 REAL DATA EXPERIMENTS HUMAN ANNOTATORS
For experiments with annotations collected from AMT, we use the LabelMe dataset (Rodrigues et al. 2017 Russell et al. 2007) and the Music dataset (Rodrigues et 2014).
The LabelMe dataset (Rodrigues et al. 2017 Russell et al.) 2007) is an image classification dataset consisting of 2688 images from street, forest, coast, mountain, and open country. From the available images, 1000 images are annotated by M = 59 AMT workers. total, about 2547 image annotations are obtained by the AMT workers whose labeling accuracy ranges from 0% to 100% with a mean accuracy of 69.2%. In order to enrich the training dataset, standard augmentation techniques such as rescaling, cropping, horizontal flips, etc., are employed and accordingly. the training dataset consists of 10, 000 images annotated by 59 workers; see more details in (Rodrigues & Pereira 2018; Chu et al. (021). The validation set consists of 500 images and the remaining 1188 images are used for testing.
8 different classes, namely, highway, inside city, tall building,
The Music dataset (Rodrigues et al. 2014) consists of audio samples of 10 different genres of music such as classical, country, disco, hiphop, jazz, rock, blues, reggae, pop, and metal. The dataset has about 1000 samples of songs each having a duration of 30 seconds. About 700 samples are annotated by 44 AMT workers (overall, about 2946 annotations are observed) and the remaining 300 are allocated for testing. Out of the annotated 700 samples, we consider 595 samples for training, and the remaining 105 samples are used for validation.
For the LabelMe dataset, we employ the settings used in (Rodrigues & Pereira 2018). The pretrained VGG-16 embeddings for the images are given as inputs to a fully connected (FC) neural network with one hidden layer having 128 hidden units and ReLUU activation functions. A dropout layer with rate 50% is also used followed by a softmax layer. For the Music dataset, we choose the same FC layer and the softmax layer as employed in the LabelMe settings, but with batch normalization layers before each these layers.
39


Reviews:
[{"review_id": "ec07lmbTQK", "reviewer": "Reviewer_MaWv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides theoretical analysis to guarantee the performance of the CCEM criterion for the first time. Furthermore, to improve the identifiability of the classifiers and the workers, the authors also proposed two variants of the CCEM by introducing two different regularization terms. Experimental results on several synthetic and real-world datasets show corroborate the theoretical claims and the effectiveness of the proposed methods.", "summary_of_the_review": "Overall, this is a valuable piece of work. The proposed methods and the theoretical analysis are conducive and attractive for researchers in the areas of CCEM in crowdsourcing. However, there are also some weaknesses in the paper. The quality of the paper could be further improved.", "strength_and_weaknesses": "The presentation of this paper is easy to follow and the study is technically sound. The design and technique details of the software structure are disclosed and reproducible. In addition, the theoretical analysis presented in this paper is conducive to research on the CCEM criterion.\n\nThere are several issues:\n- The experimental results in Table 1 are somewhat weak, and the authors should discuss the results in more detail, e.g. the performance of Max-MIG is competitive in most cases, and in case 1, GeoCrowdNet(W) does not show the advantages well compared with GeoCrowdNet(F) though the N is small and M is relatively large.\n- Whether there is an appropriate strategy or method to make decisions about which variant (GeoCrowdNet(W) or GeoCrowdNet(F)) should be used on a specific dataset?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "aSEoUD2U6s", "reviewer": "Reviewer_v39Y", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper designed new regularization terms of coupled cross entropy minimization criterion in crowdsourcing tasks. It relaxed the assumption of conditional independence among the annotators.", "summary_of_the_review": "This paper relaxed the assumptions of current coupled cross entropy minimization criterion based crowdsourcing tasks. More experiments needed to be provided to illustrate how to choose the regularization terms.", "strength_and_weaknesses": "Strength: This paper relaxed the assumption conditional independence among the annotators in crowdsourcing tasks with coupled cross entropy minimization criterion. The newly designed regularization terms based on the relaxed assumption consider 1) when the annotation data is large (voting matrix is not sparse), no expert/dominate is also ok, can set the classifier-related regularization terms; 2) when there are more annotators, can set the voting matrix as regularzation term. This paper transfers an intuitive impression \"the more annotators/annotations and the stronger classifiers, the better the performance of the crowdsourcing task\" in a mathematical way.\n\nWeakness/problems: \n- The author should provide a more detailed analysis of how and when to select the regularization term, with varying N and M. Table 1 has only 6 combinations, it's really hard to make an accurate conclusion of how to choose the regularization term.  \n - When N and M are large, are the performances of GeoCrowdNet(M) and GeoCrowdNet(F) come close to majority voting? Does it still works when the voting marix is sparse?\n - In Table 1, case 2, N = 5000, why TraceReg perform much worse than GeoCrowdNet(λ = 0)? TraceReg has trace constraints compared with GeoCrowdNet(λ = 0).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7pTJT-dhlHK", "reviewer": "Reviewer_WQN3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the author proposed two different regularised versions of CCEM to enhance the identifiability of the method by introducing geometric conditions. The comprehensive experiment is conducted to demonstrate the effectiveness of the proposed approach where GeoCrowdNet(F) performs better when more annotated items available, where GeoCrowdNet(W) shows advantages when class specialists are available.", "summary_of_the_review": "The weakness outweighed the strengths in the current version. ", "strength_and_weaknesses": "Strength\nOverall, the paper is logically organised. The research problem is clear and formulated. Theoretically seems sound. Comprehensive experiments were conducted to show the effeteness of the proposed approaches.\n\nWeaknesses\nIn session 1, too much spend on the background of the course source while the importance of identification is not mentioned.\nThe author claims that the existing identifiability result on CCEM was derived under restricted conditions, while the proposed method needs to hold under five different assumptions, and some of the assumptions are difficult to hold under real-world conditions.\nThe performance improvement seems marginal by comparing it to the existing methods such as Max-MIG.\nThe discussion on the experiment's result is not sufficient. Especially the performance difference between Max-MIG needs to be discussed.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster