Recovering Top-Two Answers and Confusion Probability in Multi-Choice Crowdsourcing
Authors: Hyeonsu Jeong
Hye Won Chung
Venue: Submitted to ICLR 2023 (2023)
Keywords: Crowdsourcing
multiple choice
detecting confusion
task difficulty
two-stage inference algorithm
minimax optimal convergence rate

Abstract: We consider multi-choice crowdsourced labeling with the goal of recovering not only the ground truth but also the most confusing answer and the confusion probability. The most confusing answer provides useful information about the task by revealing the most plausible answer other than the ground truth and how plausible it is. To theoretically analyze such scenarios, we propose a model where there are top-two plausible answers for each task, distinguished from the rest of choices. Task difficulty is quantified by the confusion probability between the top two, and worker reliability is quantified by the probability of giving an answer among the top two. Under this model, we propose a two-stage inference algorithm to infer the top-two answers, where the first stage uses the spectral method to obtain an initial estimate for the top two, and the second stage uses the result of the first stage to refine the estimates based on the maximum likelihood estimator (MLE). We show that our algorithm achieves the minimax optimal convergence rate. We conduct both synthetic and real-data experiments and demonstrate that our algorithm achieves the performance near the optimal MLE for synthetic datasets and the best performance for real datasets compared to other recent algorithms. This shows that our model explains well the real datasets with heterogeneous task difficulties due to confusion between plausible answers. 


Crowdsourcing has been widely adopted to solve large number of tasks in time- and cost-efficient manner with the aid of human workers. In this paper, we consider 'multiple-choic" tasks where a follows: Under review as a conference paper at ICLR 2023
RECOVERING ToP-Two ANSWERS AND CONFUSION PROBABILITY IN MULTI-CHOICE CROWDSOURCING
Anonymous authors Paper under double-blind review
ABSTRACT
Crowdsourcing has emerged as an effective platform to label a large volume of data in cost- and time-efficient manner. Most previous works have focused on designing an efficient algorithm to recover only the ground-truth labels of the data. In this paper, we consider multi-choice crowdsourced labeling with the goal of recovering not only the ground truth but also the most confusing answer and the confusion probability. The most confusing answer provides useful informa- tion about the task by revealing the most plausible answer other than the ground truth and how plausible it is. To theoretically analyze such scenarios, we propose a model where there are top-two plausible answers for each task, distinguished from the rest of choices. Task difficulty is quantified by the confusion probabil- ity between the top two, and worker reliability is quantified by the probability giving answer among the top two. Under this model, we propose two-stage inference algorithm to infer the top-two answers as well as the confusion prob- ability. We show that our algorithm achieves the minimax optimal convergence rate. We conduct both synthetic and real-data experiments and demonstrate that our algorithm outperforms other recent algorithms. We also show the applicability of our algorithms in inferring the difficulty of tasks and training neural networks with the soft labels composed of the top-two most plausible classes.
INTRODUCTION
worker is asked provide a single answer among multiple choices. Some examples 1) Using crowdsourcing platforms such as MTuurk, we solve object counting or classification tasks on large collection of images. Answers can be noisy either due the difficulty of the scene due to unreliable workers who provide random guesses. 2) Scores are collected from reviewers for papers submitted at a conference. For certain papers, scores can vary widely among reviewers, either due to the paper's 's inherent nature (clear pros and cons) or due to the reviewer's is subjective interpretation of the scoring scale (Stelmakh al. 2019: Liu et al. (0022).
In the above scenarios, responses provided by human workers may not be consistent among them- selves not only due to the existence of unreliable workers but also due the inherent difficulty of the tasks. In particular, for multiple-choice tasks, there could exist plausible answers other than the ground truth, which we call confusing answers | For tasks with confusing answers, even reli- able workers may provide wrong answers due to confusion. Thus, we need to decompose the two different causes of wrong answers: low reliability workers and confusion due to task difficulty.
Most previous models for multi-choice crowdsoureing, however, fall short of modeling the confu- sion. For example, in the single-coin Dawid-Skena model (Dawid Skene 1979). which is the most widely studied crowdsourcing model in the literature, it is assumed that a worker is associated with a single skill parameter fixed across all tasks, which models the probability of giving a correct answer for every task. Under this model, any algorithm that infers the worker skill would count confused labeling as the worker's error and lower its accuracy estimate for the worker, which results in wrong estimate for their true skill level.
'This phenomenon is evident on public datasets: for 'Weh' dataset (houu et al. 2012). which has five labels, the most dominating top-two answers take 80% of the overall answers and the ratio between the top is 2.4:1.

---

Under review as a conference paper at ICLR 2023
To model the effect of confusion in multi-choice crowdsoureing problems, propose new model under which each task can have a confusing answer other than the ground truth, with a varying confusion probability across tasks. The task difficulty is quantified by the confusion probability, and the worker skill is modeled by the probability of giving an answer among the top two, to distinguish reliable workers from pure spammers who just provide random guesses among possible choices. We justify the proposed top-two model with public datasets. Under this new model, we aim to recover both the ground truth and the most confusing answer with the confusion probability, indicating how plausible the recovered ground truth is compared to the most confusing answer.
We provide an efficient two-stage inference algorithm to recover the top-two plausible answers and the confusion probability. The first stage of our algorithm uses the spectral method to get an initial estimate for top-two answers as well as the confusion probability, and the second stage uses this initial estimate to estimate the worker reliabilities and to refine the estimates for the top-two answers. Our algorithm achieves the minimax optimal convergence rate. We then perform experiments where we compare our method to recent crowdsourcing algorithms on both synthetic and real datasets, and show that our method outperforms other methods in recovering top-two answers. This result demonstrates that our model better explains the real-world datasets including errors from confusion. Our key contributions can be summarized as follows.
Top-two model: We propose a new model for multi-choice crowdsourcing tasks where each task has top-two answers and the difficulty of the task is quantified by the confusion probability between the top-two. We justify the proposed model by analyzing six public datasets, and showing that the top-two structure explains well the real datasets.
Inference algorithm and its applicaitons: We propose a two-stage algorithm that recovers the top-two answers and the confusion probability of each task the minimax optimal convergence rate. We demonstrate the potential applications of our algorithm not only in crowdsourced labeling but also in quantifying task difficulty and training neural networks for classification with soft labels including the top-two information and the task difficulty.
Related works In crowdsourcing (Welinder et al. 2010: Liu & Wang, 2012 Demartini et al.)
2012 Aydin et al. 2014 Demartini et al. 2012). one of the most widely studied models is the Dawid-Skene (D&S) model (Dawid & Skene 1979). In this model, each worker is associated with single confusion matrix fixed across all tasks, which models the probability of giving a label & E [K] for the true label [K] for K-ary classification task. In the single-coin D&S model, the model is further simplified such that each worker possesses a fixed skill level regardless of the true label or the task. Under the D&S model, various methods were proposed estimate the confusion matrix or skill of each worker by spectral method (Zhang et al. 2014 Dalvi et al.] 2013: Ghosh et al.,
2011 Karger et al., 2013). belief propagation or iterative algorithms (Karger et al.] 2014 201
& Yu, 2014] Liu Liu et 20122 Ok et al. 2016)) or rank-1 I matrix completion (Ma et al., 2018 Ma
& Olshevsky 2020; [lbahim et al. 2019). The estimated skill can be used to infer the ground-truth
answer by approximating the maximum likelihood (ML))-tpee estimators (Gao & Zhou 2013 Gao
let al.
2016 /Zhag et al. 2014, Karger et al.) 2013)] Li & Yu, 2014, Raykar et al., 2010 |Syyh
et al. 1994 Ipeirotis et al. 2010 Berend & Kontorovich 2014). In contrast to the D&S models, our model allows the worker to have different probability of error caused by confusion. Thus, our
algorithm needs to estimate not only the worker skill but also the task difficulty. Since the number of tasks is often much larger than the number of workers in practice, estimating the task difficulties is much more challenging than estimating worker skills. We provide ttaistically-effccientt algorithm to estimate the task difficulties and use this estimate to infer the top-two answers.
We also remark that there are some recent attempts to model task difficulties (Khetan & Oh
2016
Shah et al. 22200; Krivosheev et al. 2020 Shah & Lee 2018 Bachrach et al. 2012 Li et al.
2019
Tian & Zhu (2015). However, these works are either restricted binary tasks (Khetan & Oh
2016
Shah et al. 2020 Shah & Lee 2018) or focus on grouping confusable classes (Krivosheev el al.
2020 Li et al. 20199] Tian Zhu (015). Our result, on the other hand, applies to any set of multi-
choice tasks, where the choices of each task are not necessarily restricted to fixed set of classes.
Notation. For vector æ, F; represents the i-th component of æ. For matrix M, My refers to the (ih entry of M. For any vector x, its &2 and -orm are denoted by || and ||x|| loo respectively. We follow the standard definitions of asymptotic notations, O(-), O(.). o()), and ((.).
2

---

Under review as a conference paper at ICLR 2023
2 MODEL AND PROBLEM SETUP
We consider a crowdsourcing model to infer the top-two most plausible answers among choices for each task. There are workers and tasks. For cach task j E [m]] := {I...., m.. we denote the correct answer by 9j E [K] and the next plausible, or the most confusing answer by h3 E [K] We call the pair (9j. h2)) the top-two answers for task j [m]] Let E [0, 1]" and q E (1/2, 1 be parameters modeling the reliability of workers and difficulty of tasks, respectively. For every pair of (i,j), the j-th task is assigned to the i-th worker independently with probability We use matrix A E IR to represent the responses of workers, where Aij = 0 if the j-th task is not assigned to the i-th worker, and if it is assigned, and Aij is equal the received label. The distribution of Aij is specified by the worker reliability Pk and task difficulty Øj as follows:
with prob. (p:gj + 1-P;)
9j. hjs
K
with prob. (p: 91) K k)
Ag
each b E [K]](9), 0,
with prob. (**²))
with prob. s.
Here p4 stands for the reliability of the i-th worker, in giving the answer from the most plausible top two (gg.hy), If p: O, the worker is considered a spammer who provides random answers among K choices, and larger value of p; indicates higher worker reliability. The parameter qj represents the inherent difficulty of the task j in distinguishing between the top two answers: for an easy task, zj is closer to I, and for a hard task, qj is closer to 1/2. We call 1 the confusion probability. Our goal is to recover top-two answers (gj. h2) for all j E [m] with high probability with the minimum possible sampling probability s. We assume that the model parameters (p, q) are unknown.
We propose the top-two model to reflect common attributes of public crowdsourcing datasets, sum- marized in Appendix |A| The most important observation is that the top-two answers dominate the overall answers, and only the second- dominatin answer has incidence rate comparable to that of the ground truth. In other words, the standard deviation in the incidence rate of the second dom- inating answer has overlap with that of the ground truth, but not the third-, fourth-dominating answers. This indicates that assuming a unique 'confusing answer' is sufficient to model the confu- sion stemming from task difficulty. More details are available in Appendix [AA
The K-ary task can be decomposed into (K- - -1)-binary tasks (Karger et al, y013; define (R) for 1 S k K such that the (i, entry A(6) indicates whether the answer Ay is larger than k. i.e., 1/0)
Binary conversion.
if S A.j S k; A! if A. K; and A/4) 0 if Ay = O. We show that (E(A (A)) is rank-1 1 and the singular value decomposition (SVD) of [[(A()) can reveal the top-two answers {(g5, h2y hg)] and the confusion probability vector q.
Proposition For every S k < K, the binary-mapped matrix A (k) (-1,0, 1]mxm satisfies
[(A(k))
1nxm = 22p(p= (K)),, where (1k) = [ri ... .. is defined as
(k)
(K)
K
Case 1: gj
> hi
Case II: 9j < hi
k
where k hys
where k < gji
(b)
9i)
where hū < k < 95;
(k)
qi
where gj S k: hyj
1
where 9j S k.
where h2 S k.
K
By defining Ar (k)
= r -r
(K)
(k-1) for l E
[K] with
r3 (0)
0 and (,K) = 0 for all j. we have
1
where t = gt-
K
(k)
1
(1
91) where k: = hj+ otherwise.
(2)
K
Note that Ar has its minimum at l 9j and the second smallest value at is hy for qj (1/2, 1]. If one can specify gj. the task difficulty Qj can also be revealed from _े - Arr In the next section, we use this structure of (k) for k E [K] to infer the top two answers and the confusion probability
We assume that n < ||pl|2 < vn for some n > 0, i.c., there are only o(n) spammers (p. = 0), and (1 ||2 = @(ym) for every & E [K]. which can be casily satisfied except exceptional cases from equation
3

---

Under review as a conference paper at ICLR 2023
Algorithm Spectral Method for Initial Estimation (TopTwol Algorithm)
Input: data matrix A' {0, I............ ,,....,KJ.... Kjnxm and parameter 7) > O where ny - llpll2 S vn.
2: Randomly split (with equal probabilities) and convert A into binary matrices X
{-1, O, 1 1 and ( E (-1, 0, 1jaxm for 1 S k < K as described in Sec. 3.1
3: Let (k) be the leading normalized left singular vector of X Trim the abnormally large
components of (8) by letting it be zero if uz > _ and denote the resulting vector as ū(k),
4: Calculate the estimate of [[p]|[(() by v(kk) = (Y (k)) TuTTTt (i)), Assume v(O) := 0 and ((K)
0.
5: For l E [K], calculate AoSt) = 1) vj 1 Estimate the top-two answers for j E [m]] by
فو == arg min A (M) hy == arg min Au (k) RE kc(K]
Ao3
(3)
kE[K]
6: Estimate |lp|2 by defining I
E k k
Av and I := 1 m
E-
K-2
7: Estimate qj for j E [mi] by defining
i = = 1/K
An, (15)
(4)
8: Output: estimated top-two answers
{(oj. h,)) and confusion probability vector q.
PROPOSED ALGORITHM
Our algorithm consists of two stages. In Stage 1, we compute initial estimate on top-two answers and the confusion probability q. In Stage 2, we estimate the worker reliability vector p by using the result of the first stage, and use the estimated p and q to refine estimates for the top two answers. Assume that we randomly split the original response matrix A into A' and A² with probability $1 and 81, respectively, and use only A for stage and (A², A2) for stage 2.
3.1 STAGE 1: INITIAL ESTIMATES USING SVD
The first stage begins with randomly splitting A again into two independent matrices B and C with equal probabilities. We then convert B and C' into (K bi-binary matrices (kk) and (())
explained in Sec. 2 Define ( and (*) ( (k) (kk)2k) 1.xm and (
(kk) ='(K22R) Laxm s' $1/2. We have E[X (8)] Ey (k) s' (k)) from Prop.
We use X (4) and (k) to estimate p" := p/ [pll2 and [|p]|2((()) respectively. The estimators are denoted by (k)) and u(A), respectively. We define (k) as the left singular vector of X (k) with the largest singular value. Sign ambiguity of the singular vector is resolved by defining (²)) as the one between (u(*), (+)) in which at least half of the entries are positive. After trimming abnormally large components of (k) and defining the trimmed vector (k), we calculate (* (Y (+)) (k), which is an estimate for (p))) By using (k) for 1 S k < K. we get estimates for top-two answers (Ô). hy) based on the observation equation 2 Lastly, we estimate ||p||2 and use (k) /llp||a R (k) to estimate the confusion probability vector q. See Algorithm for details.
3.2 STAGE PLUG-IN MAXIMUM LIKELIHOOD ESTIMATOR (MLE)
The second stage uses the result of Stage to estimate the worker reliability vector p. We first propose an estimate for the worker reliability vector p by using the estimated top-two answers (g),,,))) 1m from Algorithm | We randomly split the original response matrix A into A' and A with probability sı and S1, respectively, and use A only for Algorithm I and A only for calculating the estimator p. Our estimate for the worker reliability is defined as
K
I(A?, = Ô, or hn))
2
P. = (K 2)
(5)
s(1- - 31)
K
4

---

Under review as a conference paper at ICLR 2023
Algorithm 2 Plug-in MLE (TopTwo2 Algorithm)
1: Input: data matrix A E {0, 1...,.... K)nxm and the sample splitting $1 0.
2: Randomly split A into A and A by defining A' := A and A = A [x S) where
S is an n X m matrix whose entries are i..d. with Bern(s1) and is an entrywise product.
3: Apply Algorithm| 1 to A to yield estimates for top-two answers {(0}, hn)] and confusion probability vector q.
4: By using {(),, h- and A calculate the estimate p as in equation
5: By using the whole A and (p. q). find the plug-in in MLE estimates (g) hn AMLE) by
arg max
log
Kp pi
+1) 1(A - a) log
Kpp(1
4j) Pi
+ 1 1 [(A -b.
(6)
a.bE (k]pb
6: Output: estimated top-two answers {COBLE, )
Our plug-in MLE uses the estimated (f. in the place of (p, at the oracle [K] (1, (K, K)} such that hg
MLE, which finds (0g; hi) arg (a)jaa Diz1 log (AA p. 95 (a, 6)) as in equation 6 Details can be found in Alg
The time complexity of Alg. 2 is (m² log m nmk22, since the SVD in Alg. 1 can be computed m steps (Boutsidis et al. al.55 and the step for finding the
via power iterations within O l))
pair of answers maximizing equation 6 requires O(umk*) steps.
PERFORMANCE ANALYSIS
To state our main theoretical results, first need to introduce some notation and assumptions.
Let () denote the probability that worker [v] gives label [K] for the assigned task
(i.))
j E [m] of which the top-two answers are hy) = (a, Note that (f,5)
H(a.b).k can be written
in terms of (pisg)) from the distribution in equation for every b, E [K] Let ((a,)
(tJ)
(i.j)
(3.)) (o.,),k We introduce a quantity that measures the average ability
((a.)).1 P(a,b),2
of workers in distinguishing the ground-truth pair of top-two answers hy) from any other pair (a, b) E [K]3/((9,, h₂)} for the task j E [m]] We define
D = min
1 Σ DKL (1)s), (a.)) D: min ( jE[m)
(a. b)
where (2, = Σ, P(i) (og(P(i)/((i) is the KL-divergence between P and Q. Note that ((0) strictly positive if there exist at least one worker with p; 0 and gj E (1/2, 1) for the dis- tribution in equation [ so that (gir h2) can be distinguished from any other (a, [K]/((g))) hj)} statistically. We define D as the minimum of (5) over j E [m)). indicating the average ability of workers in distinguishing (g, ht) from any other (a, b) for the most difficult task the set of tasks.
We split the performance analysis of our algorithm into two parts. First, Theorem performance guarantees for Alg.
I states the
Theorem (Performance Guarantees for Algorithm D. For any e, 6 > 0, if the sampling probabil- ity 8-88 = काााा log )). Algorithm guarantees the recovery of the ordered top-two answers (g3, h1)) with probability at least forr any j E [m] with q₁ (1/2, 1), i.e.
P (G) (9), h1) 2 - for all E [mm] with qj E (1/2,1),
(8)
and the recovery of the confusion probability qj with P (lá; 9i4 < 61) 2 for all j [m), for every sufficiently large number m of tasks and the number of workers O(m/ log m).
5

---

Under review as a conference paper at ICLR 2023
By using Theorem I can also find the sufficient conditions to guarantee the recovery of paired top-two answers for all tasks and q with an arbitrarily small &oc -nonn error.
Corollary 1. For any e, 81 > O, if the sampling probability 8-81 52 ffll log mk Al Algorithm I
guarantees the recovery of {gg by)) and with probability at least 1 as and
such that
IP (Ggr. (gg, h1) Vi E (ml)
[ 11 < σ1) 1 (10)
Proof's of Theorem D andd Corollary are available in Appendix G
which uses Alg. as the first stage. Before providing the main theorem for Alg. (2] we state a lemma charactering sufficient condition for estimating the worker reliability vector p from equation 5 with an arbitrarily small lo -norm error.
We next analyze the performance of Alg.
Lemma 1. Conditioned on (őj- h2)) = (gg, hg) for all j E [m], if s(1 s1) Ω 63m log ?) the
estimator Pu defined in equation 5 Alg. guarantees TP (llp - م0 < 82) 2 - é for any > O.
Combining Corollary and Lemma I we can have the estimators (f), Q) for the worker reliability vector p and the confusion probability vector q with -nomm error bounded by any arbitrarily small
5 > 0 with probaiblity at least 1 2e if
= 8 81 + s11 - -1) = Ω [lo(mm//))
log(n/c) = log(mm//
(11)
8'mm
82 1
where the last equality is from the assumption that lpll = @(vn) and n. (mm/ / log logm). this regime, the sample complexity for estimating the task difficulty q is larger than that for estimating worker reliability p. To make sure that the sampling probability s < 1, we need n = 2(log m).
Our second theorem, Theorem 2 characterizes the sufficient condition on the sampling probability to guarantee the recovery of the pair of top-two answers for all tasks by equation Alg. 2 when a sufficiently accurate estimation of (p. q) given.
(i-)) Theorem 2. Assume that there is a positive scalar such that Ri),, 2 f.r all (1,j,g;,h,.0 E [n] x [m] [K]]. For any e >> 0, if (p. q) are given with
P
pD
max 2l l|q (1150) S min
(12)
4(6 D)
and the sampling probability s = Ω log(1 /p) log(mm? /c)+ + log(mm//))
). then for any e > 0 the esti-
mates of [(gs, / from equation 6 of Algorithmm 2 guarantees
(ūg 11y) = (gj, h1), Vj E [m]) 2
(13)
Proofs of Lemma and Theorem are available in Appendix [H] The assumption in Theorem 2 (i.5)
that M(a, 2 for some 0 holds if p. < 1 for all i E [n]. i.e., there is no perfectly reliable be easily satisfied by adding arbitrary small random noise to the worker answers as well. By combining the statements in Corollary [ Lemma [ and Theorem 2 with 8, = 62 8 for å defined in equation [2] we get the overall performance guarantee for Alg.
worker. This assumption
Corollary (Performance Guarantees for Alg. 2). Alg.
2 guarantees the recovery of top-two an-
swers for all tasks with P (G), hy) (gj, h.),
[m]]
M 21-EX e any > if satisfies
8 = .2 [lg(mm//))
log(1/p) log(mk2 /E) + Dlog(m//e) =
llo(mm/e log(m/c)
nD
nD
(14)
In equation 14 the first term is for guaranteeing accurate estimates of p and q with loe -norm error bounded by and the second term is for guaranteeing the recovery of the top-two answers from MLE with high probability. Since | = ((n), the two terms effectively have the same order but with different constant scaling, depending on model-specifie parameters (p.q).
Lastly, we show the optimality of convergence rates of Alg. and Alg. with respect to two types of minimax errors, respectively. The proof of Theorem 3 is available in Appendix !

---

Under review as a conference paper at ICLR 2023
Theorem 3. (a) Let F& be set of E [0, such that the collective quality of workers, measured by |ll|2 is parameterized by P as Fp := {p= 31pl1 p). Assume that p S 2/3. If the average number rıs of samples (queries) per task less than (1/2p) log(1/e), then
min
max
P(O; + -g)
(15)
9
PEJp. p. 9EIK]" Th
jElm]
(b) There is a universal constant e such that for any p [0, q E [L/2,1]", if the sampling probability s < S (1/(nD)), then
min
max
P((,), hy) * (gg, hz)) 2 c.
(16)
(G.h) to [K] " [K]"
as Mi(m))
jE[m)
From part (a) Theorem it is necessary to have > P ((1/ (1/llp/)) log(1/e)) to make the minimax
error in equation 15 less than Since Theorem I shows that Alg. recovers (ăz, h2) with probabil- ity at least
e if s > 22 ((1/llp (2) log(1/e)) when 81 1, we can conclude that Alg. 1 achieves the minimax optimal rate for a fixed collective intelligence of workers, measured by || From part (b) of Theorem 3 for any (p. q). unless we have >> (2(1/(nD) there always exists a con- stant fraction of tasks for which the recovered top-two answers are incorrect. This bound matches with our sufficient condition on from Alg. 2 in equation 14] upto logarithmic factors, as long as 5" l|[p||2 2 nD, showing the minimax optimality of our Alg. for any (p. q). More discussions on the theoretical results are available at Appendix
5 EXPERIMENTS
We evaluate the proposed algorithm under diverse scenarios of synthetic datasets in Sec. 5.1 and for two applications-in identifying difficult tasks in real datasets Sec. [5.2 and in training neural network models with soft labels defined from the top-two plausible labels in Sec. 5.3
5.1 EXPERIMENTS ON SYNTHETIC DATASET
We compare the empirical performance of Alg. D and Alg. 2 (referred as TopTwol and TopTwo2) with other basclines: majority VoV, OTP D&S and MV-D&S (Zhang et al. 2014), PGD (Ma et al. 2018), M-MSR (Ma & Olshevsky 2020) and oracle-MLE, whose details can be found in Appx. We choose these baselines since they have the strongest established guarantees in the literature and they are all MLE-based approaches, from which the top-two answers can be inferred. Obviously, oracle-MLE, which uses the ground-truth model parameters, provides the best possible performance, We devise four scenarios described in Table to verify the robustness of our model for various (p. q) ranges,
m) (50, 500) with (0, 0.2]. The number of choices for each task is fixed as 5. Fig. reports the empirical error probability 1 2n- IP(()), * (g)));)) averaged over 30 runs, with 95% confidence intervals (shaded region). Four columns correspond to the four scenarios, resp. The prediction errors for gj and hj are plotted in Fig. of Appx. DDII
We can observe that for all the considered scenarios TopTwo2 achieves the best performance, near the oracle MLE, in recovering (gj,hy) h2). Depending performs can be explained differently. For the Easy scenario, since qj is close to 1, it is easy to distinguish gj from hy but hard to distinguish h, from other labels. Our algorithm achieves the best
the scenarios, the reason TopTwo2 out-
Table 1: Parameters for synthetic data experiments under diverse scenarios.
Easy
Hard
Few-smin sma-smart
High-variance
90% ps [0, 0.1] 10% p. [0.9, 1]
Worker
Ps E [0, 1]
ps [0,1]
pt E [0, 1]
50% Ø E (0.5. 0.6 50% q3 E [0.9, 1.0
Task
4y E [0.9, 1]
45 E (0.5, 0.6]
E (0.5, 1]
7

---

Under review as a conference paper at ICLR 2023
Easy
Hard
Few Smart
High Variance
07
Pilo.)) PG.A0
14
0.
Avg of quarta took
bock
quaris
Figure/ 1: Prediction error for hg, h) for four scenarios the avg. number of queries per task changes. Our Top achieves the best performance, near the oracle MLE for all the scenarios.
performance in estimating h by a large margin (Fig. 6 For the Hard scenario, is hard to distin- guish gj and hj. but our algorithm, which uses an accurate új. can better distinguish 9j and hy. For Few-smart, our algorithm achieves the biggest gain compared to other methods, since our algorithm can effectively distinguish few smart workers from spammers. High-variance shows the effect of having diverse 9; in dataset. We remark that our algorithm achieves the best performance, near that of the oracle-MLF, for all the scenarios, while the next performer keeps changing depending on scenarios. For example, the OPT D&S is the second best performer in the Easy scenario, while is the worst performer in the Few-smart scenario. We also show the robustness of our algorithm against changes in model parameters in Appendix D
5.2 EXPERIMENTS ON REAL-WORLD DATASET: INFERRING TASK DIFFICULTIES
We next provide experimental results using real-world data collected from MTurk and show that our algorithm can be used for inferring task difficulties. We devised a color comparison task where we asked the crowd to choose a color, among six given choices, that looks the most similar a reference color of each task. See Fig. 4 in Appx. [A.] for example tasks. After randomly generating reference color and the six choices, we identified the ground truth and the most confusing answer for each task by measuring the distance between colors using the CIEDE2000 color difference formula (Sharma et al. 2005). If the distance from the reference color to the ground truth is much shorter than that to the most confusing answer, then the task was considered easy. We designed 1000 tasks and distributed to 200 workers, collecting 19.5 responses on each task. After collecting the data, subsampled it simulate how the prediction error decreases the number of responses per task increases. Fig. [aashows the performances in detecting (g), h2 9y
9j and h,, averaged over 10 times of random samplig. with 95% confidence interval (shaded region). TopTwo2 algorithm achieved the best performance in detecting (gj. h2), 9j and h, in all ranges. We further examined the correlation between the task difficulty quantified by the distance gap between the ground truth and the most
Wr663 OF71-82 POD UAGA TopTnot TopThes
P(Gy R) y Pig. 6:)
Plg 8)
PIA
Prodeten
Color distenoe
(a) The average prediction error color comparison tasks
(b) Histogram of dist. gap
Figure 2: (a) Prediction error for (g,, hy). 9n and hy (from left to right) for color comparison tasks using real data collected from MTurk. Our TopTwo2 algorithm achieves the best performance. (b) Histogram of color distance gap for the task groups with the highest q (casiest tasks) and lowest gj (most difficult tasks). The difficult task group (blue) tends to have smaller color distance gap.
8

---

Under review as a conference paper at ICLR 2023
confusing answer from the reference color- and the estimated confusion probability qj across tasks. We selected top 50 most difficult/easiest tasks according to the estimated confusion probability gj and plotted the histograms of the distance gap for the two groups in Fig 2b We can that the difficult group (blue, having lowest Qj) tends to have a smaller distance gap than those of the easy task group (red). This result shows that our algorithm can identify difficult tasks in real datasets.
5.3 TRAINING NEURAL NETWORKS WITH SOFT LABELS HAVING TOP-TWO INFORMATION
An appealing example where we can use the knowledge of the second best answer is in training deep neural networks for classification tasks. Traditionally, a hard label (one ground-truth label per image) has been used to train a classifier. In recent works, it has been shown that using a soft label (full label distribution that reflect human perceptual uncertainty) is sometimes beneficial in obtaining model with better generalization capability (Peterson et al. 2019). However, obtaining accurate full label distribution requires much higher sample complexity than recovering only the ground- truth. For example, Peterson et al. (2019) provided CIFAR 10H dataset with full human label distributions for 10000 instances of CIFAR 10 test examples by collecting on average 50 judgements per image, which is about 5-10 times larger than those of usual datasets (Table 4 in Appendix A.
Our top-two model, on the other hand, can effectively reduce the required sample complexity. while still guaranteeing the advantages in training models with soft labels. To demonstrate this idea, trained two deep neural networks, VGG-19 and ResNet18, with the soft-label vectors having the top-two structure (top2) for CIFAR datase We then compared the training/test results with those of the hard label (hard) and full label distribution (full). Experimental details are in Appendix B Compared the original training with hard labels, training with top-two soft labels achieved 1.56% and 4.09% higher test accuracy in VGG-19 and ResNet18, 18, respectively (averaged in three runs, 150 epochs) as shown in Table which even higher than that of the full label distribution in VGG-19. This result shows that training with the top-two soft labels results in better generalization (test accuracy) than training with hard labels, since the top-two soft label includes simple yet helpful side information, the most confusable class and the confusion probability.
f
Table 2: Comparison of performances for CIFARIOH dataset with hard/soft label training
Network
Train accuracy
Training loss
Test accuracy
Test loss
VGG-19 (hard)
97.46=0.59%
0.08110.012
77.64=1.5549
1.057:0.118
VGG-19 (top2)
97.00= %
0.231-10.014
79.20
0.754:10.000
VGG-19 (full)
96.69=0.488 %
0.282++0.010
08.66%
0.740++0.030
ResNet18 (hard)
98.47:#0.3200 6320%
0.046:10.009
76.49%=11 1. 1.80%
1.275++0.157
ResNet18 (top2)
98.67:10.491
0.068
80.58% -236%
0.640-10.093
ResNet18 (full)
99.19=t0.125% %
0.189+00.023
80.93% 22.66%
0.611+001102
DISCUSSION
We proposed new model for multiple-choice crowdsoureing, with top-two confusable answers and varying confusion probability over tasks. We provided an algorithm to infer the top-two answers and the confusion probability. This work can benefit several query-based data acquisition systems such as MTurk or review systems by providing additional information about the task such as the most plausible answer other than the ground truth and how plausible it is, which can be used quantify the accuracy of the ground truth or to classify the tasks based on difficulty. The topic of confusion getting increasing attention in the machine learning community for designing reliable classifiers (Jin et al. [017 Luque et al. 2019) Chang et al. 2017). We also demonstrated possible applications of our algorithm in designing soft labels for better generalization of neural networks.
3 As in (Peterson et al. 2019). we used the original 10000 test examples of CIFARIO for training and 50000 training examples for testing. Thus, the final accuracy is lower than usual. Since CIFAR 10H is collected from selected 'reliable' workers who answered a set of test examples with an accuracy higher than 75% we directly used the top-two dominating answers and the fraction between the two designing the soft lahel vector (top2).

---

Under review as a conference paper at ICLR 2023
REFERENCES
Bahadir Ismail Aydin, Yavuz Selim Yilmaz, Yaliang Li, Qi Li, Jing Gao, and Murat Demirbas. Crowdsourcing for multiple-choice question answering. In Proceedings of the Twenty-Eight AAAI Conference on Artificial Intelligence, pp. 2946-2953, 2014.
Yoram Bachrach, Thore Graepel, Tom Minka, and John Guiver. How to grade a test without knowing the answers bayesian graphical model for adaptive crowdsourcing and aptitude testing, arXiv preprint arXiv:1206.6388 6366, 2012.
Afonso S Bandeira and Ramon Van Handel. Sharp nonasymptotic bounds on the norm of random matrices with independent entries. The Annals of Probability, (4(4):2479-500 2016.
Daniel Berend and Aryeh Kontorovich. Consistency of weighted majority votes. Advances in Neural Information Processing Systems, 27, 2014.
Christos Boutsidis, Prabhanjan Kambadur. and Alex Gittens. Spectral clustering via the power method-provably. In International conference on machine learning, pp. 40-48. PMLR, 2015.
Joseph Chee Chang, Saleema Amershi, and Ece Kamar. Revolt: Collaborative crowdsourcing for la- beling machine learning datasets. In Proceedings of the 2017 CHI Conference on Human Factors in Computing Systems, pp. 2334-2346, 2017.
Nilesh Dalvi, Anirban Dasgupta, Ravi Kumar, and Vibhor Rastogi. Aggregating crowdsourced binary ratings. In Proceedings of the 22nd international conference on World Wide Web, pp- 285-294, 2013.
Alexander Philip Dawid and Allan Skene. Maximum likelihood estimation of observer error-rates using the em algorithm. Journal of the Royal Statistical Society: Series C' (Applied Statistics), 28 (1):20-28, 1979.
Gianluca Demartini, Djellel Eddine Difallah, and Philippe Cudré-Mauroux, Zencrowd: leveraging probabilisticc reasoning and crowdsourcing techniques for large-scale entity linking. In Proceed- ings of the s1 international conference on World Wide Web, pp. 469-478, 2012.
Chao Gao and Dengyong Zhou. Minimax optimal convergence rates for estimating ground truth from crowdsourced labels. arXiv preprint 1rX15:1310.5764, 2013.
Chao Gao, Yu Lu, and Dengyong Zhou. Exact exponent in optimal rates for crowdsourcing. In International Conference on Machine Learning, pp. 603-611. PMLR, 2016.
Arpita Ghosh, Satyen Kale, and Preston McAfee. Who moderates the moderators? crowdsoure- ing abuse detection in user-generated content. In Proceedings of the 12th ACM conference Electronic commerce, pp. 167-176, 2011.
Shahana Ibrahim, Xiao Fu, Nikolaos Kargas, and Kejun Huang. Crowdsourcing via pairwise co- occurrences: Identifiability and algorithms. Advances in neural information processing systems, 32, 2019.
Panagiotis G Ipcirotis, Foster Provost, and Jing Wang. Quality management on amazon mechanical turk. In Proceedings of the ACM SIGKDD workshop on human computation, pp. 64-67, 2010.
Ruochun Jin, Yong Dou, Yueqing Wang, and Xin Niu. Confusion graph: detecting confusion com- munities in large scale image classification. In Proceedings of the 26th International Joint Con- ference Artificial Intelligence, pp. 1980-1986, 2017.
David Karger, Sewoong Oh, and Devavrat Shah. Iterative learning for reliable crowdsourcing sys- tems. Advances in neural information processing systems, 24, 2011.
David R Karger, Sewoong Oh, and Devavrat Shah. Efficient crowdsourcing for multi-class label- ing. In Proceedings of the ACM SIGME//RCSYineeattioon conference Measurement and modeling of computer systems, pp. 81-92, 2013.
David R Karger, Sewoong Oh, and Devavrat Shah. Budget-optimal task allocation for reliable crowdsourcing systems. Operations Research, 62(1):1-24, 2014.
10

---

Under review as a conference paper at ICLR 2023
Ashish Khetan and Sewoong Oh. Achieving budget-optimality with adaptive schemes in crowd- soureing. Advances in Neural Information Processing Systems, 29:4844 4852, 2016.
Evgeny Krivosheev, Siarhei Bykau, Fabio Casati, and Sunil Prabhakar. Detecting and preventing confused labels in crowdsourced data. Proceedings the VLDB Endowment, 13(12):2522-25 2535, 2020.
Hongwei Li and Bin Yu. Error rate bounds and iterative weighted majority voting for crowdsoureing. arXiv preprint arXiv:1411.4086, 2014.
Yuan Li, Benjamin Rubinstein, and Trevor Cohn. Exploiting worker correlation for label aggregation in crowdsourcing. In International conference on machine learning, pp. 3886-3895, PMLR, 2019.
Chao Liu and Yi-Min Wang. Truelabel + confusions: A spectrum of probabilistic models in analyz- ing multiple ratings. In Proceedings of the 29th International Conference on Machine Learning, ICMI., 2012.
Qiang Liu, Jian Peng, and Alexander T Ihler. Variational inference for crowdsoureing. Advances in neural information processing systems, 25, 2012.
Yusha Liu, Yichong Xu, Nihar B Shah, and Aarti Singh. Integrating rankings into quantized scores in peer review. arXiv preprint arXiv:2204 2022.
Amalia Luque, Alejandro Carrasco, Alejandro Martín, and Ana de Las Heras. The impact of class imbalance in classification performance metrics based on the binary confusion matrix. Pattern Recognition, 91:216-231, 2019.
Qianqian Ma and Alex Olshevsky. Adversarial crowdsourcing through robust rank-one matrix com- pletion, Advances in Neural Information Processing Systems, 33:21841-21852. 2020.
Yao Ma, Alexander Olshevsky, Csaba Szepesvari, and Venkatesh Saligrama. Gradient descent for sparse rank-one matrix completion for growd-sourced aggregation of sparsely interacting workers. In International Conference on Machine Learning, pp. 3335-3344. PMLR, 2018.
Jungseul Ok, Sewoong Oh, Jinwoo Shin, and Yung Yi. Optimality of belief propagation for crowd- sourced classification. In International Conference Machine Learning, pp. 535-544. PMLR, 2016.
Joshua Peterson, Ruairidh M Battleday, Thomas Griffiths, and Olga Russakovsky. Human uncertainty makes classification more robust. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 9617-9626, 2019.
Vikas C Raykar, Shipeng Yu, Linda Zhao, Gerardo Hermosillo Valadez, Charles Florin, Luca Bogoni, and Linda Moy. Learning from crowds. Journal of machine learning research, 11(4), 2010.
Devavrat Shah and Christina Lee. Reducing crowdsourcing to graphon estimation, statistically. In International Conference on Artificial Intelligence and Statistics, pp. 1741-1750, 2018.
Nihar B Shah, Sivaraman Balakrishnan, and Martin J Wainwright. A permutation-bast model for crowd labeling: Optimal estimation and robustness. IEEE Transactions on Information Theory, 67(6))4162 4184, 2020.
Gaurav Sharma, Wencheng Wu, and Edul Dalal. The ciede2000 color-difference formula: Im- plementation notes, supplementary test data, and mathematical observations. Color Research & Application: Endorsed by Inter-Society Color Council, The Colour Group (Great Britain), Canadian Society for Color, Color Science Association of Jupan, Dutch Society for the Study of Color, The Swedish Colour Centre Foundation, Colour Society of Australia, Centre Français de la Couleur, 30(1):21-30, 2005.
Padhraic Smyth, Usama Fayyad, Michael Burl, Pietro Perona, and Pierre Baldi. Inferring ground truth from subjective labelling of venus images. Advances in neural information processing sys- fems, 7, 1994.
11

---

Under review as a conference paper at ICLR 2023
Ivan Stelmakh, Nihar B Shah, and Aarti Singh. Peerreview4all: Fair and accurate reviewer assign- ment in peer review. In Algorithmic Learning Theory, pp. 828-856888 PMLR, 2019.
Tian Tian and Jun Zhu, Max-margin majority voting for learning from crowds. Advances in neural information processing systems, 28, 2015.
Peter Welinder, Steve Branson, Pietro Perona, and Serge Belongie. The multidimensional wisdom of crowds. Advances in neural information processing systems, 23, 2010.
Yuchen Zhang, Xi Chen, Dengyong Zhou, and Michael Jordan. Spectral methods meet em: A provably optimal algorithm for crowdsourcing. Advances in neural information processing sys- tems, 27, 2014.
Dengyong Zhou, Sumit Basu, Yi Mao, and John Platt. Learning from the wisdom of crowds by minimax entropy. Advances in neural information processing systems, 25, 2012.
12

---

Under review as a conference paper at ICLR 2023
A VERIFICATION FOR THE PROPOSED Top-TwO MODEL
We proposed the top-two model to reflect the key attributes of seven datasets including Adult2, Dog, Web, Flag, Food, Plot, and Color, of which the details summarized in Appendix A.1
Table empirical distributions of the mean incidence of responses for the top-three dominat- ing answers, sorted by the dominance proportions, for the six public datasets and the Color dataset that we collected, with the standard deviation over the tasks in the dataset. In Fig. 3 we also plot empirical distributions of the mean incidence responses sorted by the dominant proportion with error bars indicating the standard deviation. The i-th data point represents the average incidence of the i-th highest response in each task. For example, in Adul12 dataset, the most dominating answer takes 0.8 portion of the total answers, and the next dominating answer takes 0.14 portion of the total answers on average.
Table Proportions of top-three dominating answers in public datasets
Dataset
Ground truth
2nd dominating answer 3rd dominating answer
Adult2
0.80:10.19
0.14:10.13
0.04+10007
Dog
0.76
0.22:10.14
0.01
Web
0.59:10.20
0.25::0112
0.12::0.09
Flag 0.
0.0
0.01
Food
0.80:10.18
0.17+00.15
0.02++0.05
Plot
0.62:1021
0.30110.16
0.06:10.07
Color
0.43+-0.1
0.23+-0.06
0.15
Adult2
Dog
Web
Flag
protestally
Bd
84
Empiriaal
Emprriall
Bu
Label
Label
Label
Label
(a)
(b)
(c)
(d)
Food
Plot
Color
Empincal probadakyy
6.
Empincal protadalkyy
1.
Empircal protasallyy
3.5
2.3
Ro
Label
Label
Label
(c)
(f)
Figure 3: Empirical distribution of the mean incidence of responses sorted by the dominant propor- tion, averaged over all tasks in each dataset. The i-th data point represents the average incidence of the i-th highest response in each task. The error bars indicate the standard deviation of the mean incidence of the i-th dominating answer over the tasks in the dataset.
From the table and figure, we can observe that for all the considered public datasets the top-two answers dominate the overall answers, i..., about 65-90% of the total answers belong to the top two. Furthermore, the average ratio from the most dominating answer to the second one is 4:1, while that between the second and the third is 7.5:1. There often exist overlaps in the error bars between
13

---

Under review as a conference paper at ICLR 2023
(a) = 6 and hy =
(h) = and h5 =
2
6
(c) = 5 and ht =
(d) 6 and A5 = 2
Figure 4: Example tasks for 'Color' dataset where the ground truth y and the most confusing answer h are determined by the color distance from the reference color (top).
the ground truth and the second dominating answer, e.g., for Web, Plot, and Color datasets, but no such overlap is found between the ground truth and the third dominating answer. What a 'confusing answer' is an answer that has an incidence rate comparable to that of the ground truth. In all the considered datasets, only the second dominating answer shows such tendency, and thus, we can conclude that the third dominating answer cannot be called a 'confusing answer', and the top-two model in equation well describes the errors in answers caused by confusion.
call
Moreover, from the public datasets, we also observe that the task difficulty can be quantified by the confusion probability between the top-two answers. As an example, for the Web dataset, when we select the easiest 500 tasks and hardest 500 tasks by ordering tasks with the ratio of correct answers, the ratio between the mround-truth to the 2nd best answer was 10.7:1 for the easiest group, while was 1 1.5:1 for the hardest group. This observation shows that the ratio between the top-two answers indeed captures task difficulty as does our model parameter for task difficulty qj equation] [
A.1 DATASETS
We collect six publicly available multi-class datasets: Adult2, Dog, Web, Flag, Food and Plot. Since these datasets do not provide information about the most confusing answer or the task difficulty, additionally create a new dataset called 'Color', for which we can identify the confusing answer and also quantify the task difficulty for all the included tasks.
Color is a dataset where the task is find the most similar color the reference color among six different choices. For each task, we randomly create reference color and then choose six choices of colors. The distance from the reference color the ground truth color is in between 4.5 and 5.5, the distance the most confusing answer is in between 5.5 and 6.5, and the distance the rest of choices is between 11 and 12, where distance between the pairs of colors is measured by CIEDE2000 (Sharma et al. (005) color difference formulation. The tasks are ordered terms their difficulty levels by measuring the gap between: the distance from the reference color to the ground truth: and that to the most confusing answer. the distance from the reference color to the ground truth is much shorter than that the most confusing answer, then the task is considered easy. Using MTurk, we collected 19600 labels from 196 workers for 1000 tasks. Each Human Intelligence Task (HIT) is composed of randomly selected 100 tasks, and we pay $1 to each worker who completed HIT. Fig. 4 shows an example task for the Color dataset.
Adult2 [ppeirotis et al.) 2010) is 4-class dataset where the task is to classify the web pages into four categories (G, PG. R, X) depending on the adult level the websites. This dataset contains 3317 labels for 333 websites which offered by 269 workers.
14

---

Under review as a conference paper at ICLR 2023
(a) Images with lowest y (considered be hard)
(b) Images with highest 9 (considered to be easy)
Figure 5: Training images with (a) lowest and (b) highest confusion probabilities.
Dog (Zhang et al. 2014) is 4-class dataset where the task to discriminate breed (out of Norfolk Terrire, Norwich Terrier, Irish Wolfhound, and Scottich Deerhound) for a given dog. This dataset contains 7354 labels collected from 52 workers for 807 tasks.
Web (Zhou et al., 2012) is a 5-class dataset where the task is to determine the relevance of query-URL pairs with 5-level rating (from to 5). The dataset contains 15567 labels for the 2665 query-URL pairs offered by 177 workers.
Flag (Krivosheev et al. 2020) is dataset for multiple-choice tasks where each task is identify the country for a given flag from 10 given choices. total of 1600 votes are collected from 220 workers for the 100 tasks.
Food (Krivosheev al. 2020) is dataset for multiple-choice tasks where each task asks to identify picture of given food or dish from 5 given choices. This dataset contains 1220 labels for 76 tasks collected from 177 workers.
Plot (Krivosheev et al., 2020 is a dataset for multiple-choice tasks where the task is to identify movie from description of its plot from 10 given choices. Only workers who correctly solved the first 10 test questions can answer the rest of the tasks. A total of 1937 labels are collected from 122 workers for 100 tasks.
Table 4 shows a summarized information for the introduced datasets.
Table 4: Dataset information
Dataset
# workers
tasks
labels or choices
sparsity
deask
dworker
Adult2
269
333
0.037
10.0
12.4
Dog
109
807
0.092
10.0
74.0
Web
176
2653
5
0.033
5.9
88.3
Flag
220
100
10
0.073
16.0
7.3
Food
177
54
0.125
22.1
6.7
Plot
122
56
10
0.293
35.7
16.4
Color
196
1000
0.1
19.5
99.4
B EXPERIMENTAL DETAILS FOR NEURAL NETWORK TRAINING IN SEC.
5.3
We show the details of the experiments in Sec. 5.3
B. DATASETS
The CIFARIOF dataset (Peterson et al., 2019) consists 511,400 human classifications by 2,571 participants which were collected via Amazon Mechanical Turk. Each participant classified 200 images, 20 from each category. Every 20 tasks, trivial question is presented to prevent random guessing, and participants who scored below 75%
excluded from the dataset. We present the images with the lowest/highest q from the training samples in Fig The image with lower means that the first answer and the second answer hard to distinguish.
15

---

Under review as a conference paper at ICLR 2023
B.2 MODEL
We trained two simple CNN architectures, VGG-19 and ResNer-18, to show the usefulness of the second answer and the confusion probability. For each model, our loss function is defined as the cross-entropy between the softmax output and the two-hot vector (in which the values are q and 1 q for g and h, respectively). We compare the results of our top-two label training with those of full-distribution training and hard label (one-hot vector) training.
B.3 TRAINING
We train each model using 10-fold cross validation (using 90% of images for training and 10% images for validation) and average the results across 5 runs. We run a grid search over learning rates, with the base learning rate chosen from {0.1, 0.01, 0.001). We find 0.1 be optimal in all cases. We trained each model for a maximum of 150 epochs using SGD optimizer with a momentum of 0.9 and weight decay of 0.0001. Our neural networks trained using NVIDIA GeForce 3090 GPUs.
C BASELINE METHODS
In this section, we explain the baseline methods with which we compare the performance of algorithms. To analyze the performance in recovering the top-two answers, we considered the ML- based algorithms, including the Spectral-EM algorithm (MV-D&S and OPT-D&S) (Zhang al. 2014), Projected Gradient Descent (PGD) (Ma et al. 2018) and M-MSR (Ma & Olshevsky 2020) which provide "score" for each label so that we can recover the top-two answers.
Spectral-EM algorithm (MV-D&S and OPT-D&S) Zhang et al. 2014) is a two-stage algorithm for multi-class crowd labeling problems. These algorithms are built for the D&S model where each worker has his/her own confusion matrix. In the first stage of the algo- rithm, the confusion matrix of each worker is estimated via spectral method (OPT-D&S) or majority voting (MV-D&S), respectively, and in the second stage, the estimates for the confusion matrices refined by optimizing the objective function of the D&S estimator via the Expectation Maximization (EM) algorithm.
Projected Gradient Descent (PGD) Ma et al. 2018) is an approach to estimate the skills of each worker in the single-coin D&S model. The authors formulate the skill estimation problem as a rank-one correlation-matrix completion problem. They propose projected gradient descent method solve the correlation- matrix completion problem.
M-MSR (Ma & Olshevsky] 2020) algorithm is an approach to estimate the reliability of each worker in the multi-class D&S model. M-MSR algorithm utilizes that the rank of the response matrix one. To estimate the reliability of the workers, they use update rules to find the left singular vector and right singular vector of the response matrix. In this process, the extreme values are filtered out to guarantee the stable convergence of the algorithm.
D SYNTHETIC EXPERIMENTS
D.1 ADDITIONAL PLOTS FOR SYNTHETIC DATA EXPERIMENTS SEC. 5.
we devised four scenarios described in Table I to verify the robustness of our model for various (p. q) ranges, with (n, m, s) (50, 500, 0.2). The performance of algorithms is measured by the empirical average error probabilities in recovering 9j. h; and (gi,hz), h2), i.e., P(0; g3). E== P(hh # h2) and 1 ", hy) + (gj, hy)) and plotted in m Fig. We observe that for all the considered scenarios TopTwo2 achieves the best perfor- mance, near the oracle MLE, in recovering (g,, hy). Depending on scenarios though, the reason Two2 outperforms can be explained differently. For Easy scenario, since qi is close to be- comes easy distinguish 9; from hj but hard distinguish hy from other labels. Our algorithm achieves the best performance in estimating h; by a large margin. For Hard scenario, it becomes hard to distinguish 9j and hy, but algorithm, which uses accurate dj. better distinguish
In Section 5.1
16

---

Under review as a conference paper at ICLR 2023
TepTard -+0O
Easy
Hard
Few Smart
High Variance
P(oxA) P1A A/
4.20
06
02
2.0
06
1.29
Flo 91
02
610
3.10
04
04
Avg.
quedin
Aug.
Figure 6: Prediction error for hg) (top row), Bj (middle) and hy (bottom) for four scenarios. Our algorithm (TopTwo2) achieves the best performance, near the oracle MLE for all the scenarios.
Jj and hj. High-variance show the effect of having diverse qj in a dataset. For Few-smart, our algorithm achieves the biggest gain compared other methods, since our algorithm can effectively distinguish few smart workers from spammers. We remark that even though the performance gap between TopTwo2 and the next best performer not significant for some cases, our algorithm ways achieves the best performance, near that of the oracle-MLE, for all the scenarios, while the next performer keeps changing depending on scenarios. For example, the OPT D&S the second best performer in the 'Easy" scenario, while it is the worst performer in the 'Few smart' scenario.
D.2 ROBUSTNESS OF OUR METHODS
In this section, we present a set of four additional synthetic experiments to demonstrate the ro- bustness of methods, Alg. [ and Alg. (referred TopTwol and TopTwwo2.. In each experiment, we change a parameter of our synthetic error model and compare the prediction error of algorithms to the baselines: majority voting(MV), OTP-D&S and MV-D&S Zhang et al. (2014), PGD Ma et al. (2018) and Oracle-MLE. We measure the performance of each algorithm by the empirical average error probabilties in recovering the ground truth gy. the most confusing answer hy and the pair of top two (gj, hy), i.e., 1 m E P(q; # 9j). 1 Σn P(hy # hj) and 1 E PP((;; Fy)) # (gi,h,)). Obviously, Oracle-MLE provides lower bound for the perfor- mance.
m
Changing the dimension of observed matrix: We first check the robustness of our methods against the change of dimensions of the observation matrix A E {0, K x with < m. We vary the number of workers (n) or the number of tasks (m) while fixing the other dimension. The default values of and m are 50 and 500, respectively, and the sampling probability is fixed 0.1 throughout the experiments. The worker reliability p: and the task difficulty qj is sampled uniformly
random from [0, and (1/2, 1), respectively, for all [n] and [m].
17

---

Under review as a conference paper at ICLR 2023
Plo
Pee Pee ano
0.0
Mi
oi worker
ofwcroess
of workers
(a) Effect of the number of workers the performance
P1G M ee
0.0
Plo
6.72
0.75
0.5
2.60
0.00
0.4
0.4
0.2
E20
0.00
0.5
0.2
3.5
0.40
0.7
450
800
1300
200
600
650
1000
344
250
430
800
1000
of 2014
A bokk
(b) Effect of the number of tasks on the performance
0.75
PC's Mi di
0.34
Plastai
3.7
PiL
0.32
0.3
Phodoon 6RC21
Prudider
9.
24
5.00
3.5
2.1
8:15
0.22
0.6
0.15
0.2
0.25
0.55
2.15
52
625
relabiity
relabiliy
(c) Effect of the variance of worker reliability on the performance
Eae
2.
6:15
2.15
(d) Effect the variance of task difficulty on the performance
08
0-2
0.3
Tecleec
Porfoe
Porkon
Pooton
(c) Effect the portion spammers on performance
Figure 7: Prediction error for (g,, h2) (first column), 9j (second column), and hy (third column) for five different setups. The solid lines represent the mean prediction emrors of each algorithm averaged over 10 runs, and the shaded regions represent the standard deviations.
18

---

Under review as a conference paper at ICLR 2023
In Fig. 7a and 7b report the results when change n for a fixed m and when we change m for a fixed n and s, respectively. From Fig. 7a we can see that as the number of workers increases, the performance of every algorithm improves since the number of samples per task scales as ns for a fixed 8. Our algorithm achieves the performance close to the Oracle-MIF for all the considered range, which implies that the worker reliabilities {pe} } are well estimated with our methods. From Fig. [7b] we can see that our algorithm achieves a robust performance against the change in the number of tasks, although the performance gets closer to that of Oracle-MLE as the number of tasks increases. Since our method uses SVD in the first stage, the larger dimension is beneficial for the concentration of the random perturbation matrix with respect to the expectation of the observation matrix. This phenomenon is observed for other baseline methods as well, which are based on the spectral method, OPT D&S, for example.
Changing the variance of worker reliability: In this experiment, we change the range of ps. the parameter for worker skill/reliaiility, for [m], with fixed mean order to observe the impact of the variance of the worker reliability on the prediction error. We randomly sample p; from the window [0.5 - x, 0.5 + x] with x varying from 0.05 to 0.25. The mean of the worker reliability is fixed as 0.5.
As shown in Fig. 7c when the variance of the worker reliability increases, the baseline methods estimating worker reliabilities perform better than the majority voting. Our TopTwo2 algorithm achieves the best performance close to Oracle-MLE, as the standard deviation increases, i.e., as the workers become more heterogeneous.
Changing the variance of task difficulty: We also design an experiment to observe the impact of the variance of ạz- j E [m]] the parameter for task difficulty, on the prediction error. We randomly sample dj from the window [0.75 - x 0.75 + x] with x varying from 0.05 to 0.25. The mean of the worker reliability fixed as 0.75. If the variance of the task difficulty is small, it could be sufficient to only estimate the worker reliability since all the tasks have almost the similar task difficulties.
As shown in Fig. 7 when the variance of the task difficulty increases, our TopTwo2 algorithm performs better than the other baselines. This is the evidence for the validity of our method in estimating the task difficulty.
Changing the portion of spammers: Spammers who provide random answers always exist in crowdsourcing systems. To improve the inference performance, it is important distinguish spam- mers from reliable workers. In our experimental setup, we define a spammer as worker whose reliability parameter p; is in the range 0.1). We change the portion of spammers among the workers from 0.1 to 0.9 and compare the prediction error of our methods to those of other baseline methods.
In Fig. 7e we can see that our algorithm achieves the best performance among all the considered baselines except Oracle-MLE, which can exactly distinguish spammers from reliable workers. This result demonstrates the superiority of our methods in detecting spammers compared to other meth- ods.
D.3 ESTIMATING THE WORKER RELIABILITY VECTOR AND THE TASK DIFFICULTY VECTOR
In this section, we examine the accuracy of our estimates for the worker reliability vector p and the task difficulty vector q. The worker reliability is estimated by و defined in equation 5 of Algorithm and the task difficulty is estimated by I defined in equation of Algorithm I To analyze the accuracy of these estimators, we compute the mean squared error (MSE), n h1lp pl2 and 1 ll q 4.. respectively.
2
To analyze the estimation accuracy for the worker reliability. we first sample p; uniformly at random from [0, 1] for all i E [n] and fix the worker reliability vector p. Then, we randomly sample the task difficulty vector q E (1/2, 1|m fifty times and then sample the observation matrices from the distribution equation for each (p. pair with a fixed p. For each observation matrix, we subsample the data with varying probabilities and apply Algorithmm get the estimate p. which is then used to calculate the MSE of p. We report the MSE averaged over these fiftyy cases. Similarly, to analyze the estimation accuracy for the task difficulty, vector E (1/2, 11r" and generate fifty different observation matrices while varying the worker reliability vector p. We again report the MSE averaged over these fifty cases. The number of workers
randomly sample and fix a task difficulty
19

---

Under review as a conference paper at ICLR 2023
and that of tasks is set be 500) for the worker reliability estimation, and to be (100, 1000) for the task difficulty estimation.
In Fig. 8a and 8b plot the MSE for p and q, respectively, as the average number of queries per task increases. We can see that both for p and q, the MSEs converge to near zero as the average number of queries per task increases. However, estimating the task difficulty requires more number of samples as our theory equation 11 suggests.
Maxt Sraae Stee
0.00
2.
Mann
0.2
0:19
0.30
60
100
Aug del BUSFDS per
Ang. quorio 1984
(a) Mean squared error 1
in I
2
(h) Mean squared error 1
l1
m
Figure 8: Mcan squared errors in estimating the worker reliability vector (left) and the task diffi- culty vector (right), respectively.
E DISCUSSION OF THEORETICAL RESULTS
In this section, we present discussion of the main theoretical results.
Theorem asserts that the sampling probability of Ω x & log ) is sufficient re- cover the top-two answers (gj. for any task j [m]] and to estimate the confusion probability with accuracy of (;; gz < 51 by Algorithm 1 with probability at least 1 1 c. Combined with Theorem part (a), we can that this sample complexity is the minimax optimal rate for a fixed collective quality of workers, measured by ||p|
It is also worth comparing our algorithm with the simple majority voting (MV) scheme. The MV scheme infers the top-two answers by counting the majority of the received answers. Simple analysis shows that the MV scheme requires the sampling probabil- ity such that ns θ Σx p:)
p llog 2) to recover (gj, h2y with probability 1
log K samples per task. Since Remind that Algorithm requires ns Ω 3f
= = (H by Cauchy-Schwarz Schwarz inequality, Algorithm achieves strictly better trade-offs unless p; is same for all workers i E [n]. As an example, for spammer- heammer-hammer model where a (0, 1) fraction of workers are hammers with p; and the rest are spammers with p. 0, Algorithm requires ns θ (1 log !) samples per
task, while MV requires ns = θ + log t) samples per task to recover top-two answers with probability 1
Theorem 2 shows that when we have an entrywise bound on the estimated worker reliabil- ity vector p and the task difficulty vector q, the plug-in MLE estimator, used in Algorithm guarantces the recovery of top-two answers if the sampling probability s = 22 log( (m/e)
nD
where D, which depend on (p, q), indicates the average reliability of workers in distin- guishing the top-two answers from any other pairs for the most difficult task. Combined with Theorem 3 part (b), we can see that this sample complexity is the minimax optimal rate for any (p. q), ignoring the logarithmic terms.
Combining the conditions for the accurate estimation of model parameters in equation and the convergence of the plug-in MLE (Theorem (). Corollary 2 shows the condition on the sample complexity to guarantee the performance of Algorithm 2
20

---

Under review as a conference paper at ICLR 2023
F PROOF OF PROPOSITION 1
For each task j and label kt define four indicator functions:
[a(,, k)) : k; h1 > k):
[sj k) : _ h, k):
(17)
[T. k) :=1 (9) > k h, S k):
[T k) : (g) S h3 S k): 1
which satisfy [T K) + (j) + II( + Ia(i, R) 1. For notational simplicity, will often drop (j. k) fron II. The pmf of (4) is given by
with probability s(1 - Pij
(k)
1
with probability spij
(k)
(18)
with probability 1
8,
(k) II, (j. k)p; + II, () 93) + II, k)p,q; (K ()(-p)) and its expectation is
where Pij
E 1j (k)
(80) s(2pk) (k) 1). Note that by using II, 1 II II II. the probability Pij can be
(k)
written Pij pi (4s (II. Ib. (II. IIa) + x) K-k
K Thus, by defining
(0) 3
== qf (II. - -Ib) - (Il + Ia) +
(19)
K
the expectation of ! can be written as
B[A B[A - =(2pl)) -1) (1)==0 =
(2prr ( +
(K)
K 2k
(20)
K
and
E[A (8)) s(K- - 2k)
1 1xx 22p(r
(21)
Note that
Case 9j > hj
Case II: 9j < hjj IL = 1 where k < 9j
[i, k) where lo < hy:
(22)
[T, k) where h2 < k < Jj.
[6 k) = where 9j S k: < h13
Ila(i,k) k) where 9j _ k;
Ia k) = 1 where h1 k.
Thus, r
(k)
in equation 19 is equal to
Case I: gi > h3
Case II: gj < h3
where k < hy;
where k < 9j:
(k)
(1 43)
where hj < k < 9j:
r
(k)
4
where gj k hy;
where 9j k,
where h, S k.
G PERFORMANCE ANALYSIS OF ALGORITHM I
G. PROOFS THEOREM I AND COROLLARY 1
In Algorithm 1 we use the data matrix A', which is obtained by randomly splitting the original
data matrix into A and 2 with probability s and (1 (1-5 $1), respectively. Then, the first stage of Algorithm begins with randomly splitting A again into two independent matrices B and C with equal probabilities, and then converting B and C' into (K - 1)-binary matrices (k) and
(kk) as explained in Sec. We define (k) and (k) (k) = ((k) s'(K-2k) 1nxm and (k) (K))
K
e'(K 1 2k) K axm where s' 8. 81/2. We have ([ By s ((1)
21

---

Under review as a conference paper at ICLR 2023
from Prop. For notational simplicity, will ignore this random splitting for moment and just pretend that (k) and ( are sampled independently with s' throughout this section.
We first outline the proof. Based on the observation that [X) = sp(r(()) if (k) is available we can recover p Ti P_ by SVD, and by using p" it is possible to recover |1 which then reveals {(g,,h) hy) j well q from the relation in equation
2 To estimate p" from x(k), we first bound the spectral norm of the perturbation, || (A) E ( Jl2.. We then use this bound and Wedin Sine theorem to bound sin (()(*), p²) where (8) is the left singular vector of (() with the largest singular value. We trim the abnormally large components (A)) and denote the resulting vector by (k,), After trimming, it is still possible to show that sin (()(), pp) can be bounded in the same order as that of sin (()(),, p²). Finally, we provide an entrywise bound between (k) 2 (Y(()) T (k) and [lll2r(()) in Lemma 5 which is the main lemma to prove We state our main technical lemmas first and then prove Theorem
Theorem 1
Let us define the perturbation matrix
- (*)) s(K 2k)
E (x=
Laxm (p(( (1h) (E]B())
(23)
where
1-1 w.p. s(1 Pij 1
-1
(k) 0 w.p.
1 w.p. Spij 1
(24)
and Pij IL k). I1 k)pp(1 9j)
(k)
Il k)piq; + (K (K-I)I-E)) for (Il HI, II. Ila)
K
defined in equation 17
For the perturbation matrix in equation 23
we have
E[E, and Eayl $2, 1sisn, n,, 15j S m,
(25)
and also
var(E;g) var( B = E[ -
(B
(26)
= - (s(p)) (k) - 1/2))² S.
Note that (Fgg) are independent across all i,j. Define
V max
max Σ
E E
max Σ
max(m,n]s
(27)
By applying the spectral norm bound to random matrices with independent entires, appeared in Bandeira & Van Handel (2016) and summarized in Theorem we can bound the spectral norm of E as below.
Lemma 2 (Spectral norm bound of E). With probability 1 (n + m) we have
E < 4 max n) + +ō ēo/log(n + m)
(28)
for some constant > when m 2 n. For some sufficiently large m, assuming n = o(m) and O[oog(n + m)/m), the spectral norm of E can be further bounded by
E < 5ysmm
(29)
Using the bounded spectral norm E equation 29 and applying the Wedin SinO theorem, sum- marized in Theorem 5 we can bound the angle between (k) and p².
Lemma 3. For some sufficiently large m, assuming n. o(m) and R(log(n + m)/m), have
sin (i (K) p²) < ((1/vsn)
(30)
with probability at least 1 -nn++ m)
22

---

Under review as a conference paper at ICLR 2023
Proof. By applying the Wedin SinO Theorem (Theorem
5 have
v2 E
sin ((n( s|pl|2 ||
(31)
|
We have |pl| = @(v)) and || @(ym) by assumptions on model parameters. By
Lemma 2 for some sufficiently large m, assuming
o(m) and Øloog(n + m)/m),
have S 5/sm with probability at least 1 - (n + m) Combining these bounds, we get
(vvsm)
sin ((u()) ,p) s ((s/mm) (v sm) θ (vsn)
(32)
(1) > 2/ (11/n) and denote We trim the abnormally large components of u (k) by letting it zero u; the resulting vector as i(k)) This process required to control the maximum entry size of a(8), which is used later in the proof. For the next lemma, show that after the trimming process, the
norm of (k) is still close to 1 and the angle between (*) and p" has the same order that of sin 0 p*).
Lemma 4, Given 1|p 1l2 2 nyT, we have
a 1a 2 50sin ((u(k),)') sin ((
(33)
pp)) S 2 ((u (k), .p").
(34)
The proof Lemma is provided in Section G.2
Finally, we provide our main lemma giving the entrywise bound the difference between (R)
(Y T (R) and (|p]|
Lemma (Entrywise Bound). For any 51, e > O, and any task j E [mm] and label index k E [K], if
the sampling probability 2 O اसاा log 2) Ihen we can guarantee
P
y (k) ;(()) 1pl|rr,
< <0ı1|p112
> >1-c
(35)
as m >> 0o when (m/ log m).
Proof. For notional simplicity, denote ((T by 0. To prove equation 35 two probabilities,
we show bounds on
P
(1()) (k) v (0 112llp11221 (k) cos 0
51 |||||
e/2,
(36)
2
[Iaa 122111111)) cos 0 |12| (1)
81 ||lp
</2
(37)
2
Then, the triangle inequality implies equation
We first prove equation 36 Remind that we do the random splitting of the input matrix A and define the two independent binary-converted matrices as ( and ( for < < K, which are used to estimate (b) and (8)) respectively. Thus, (k) is independent from (k) and this independence
is used when we bound the first and second moments of (k) ((X-(4) ((()). For any 1 S S
the first and second moments of v 1 (Y-(M) (k)) satisfy
E
(k)
(K)
(p. a ( (K) = (1) O(Vn)
(38)
(K) if 3
0 by Lemma
and and
var
Y (k)
a (
Σ
(k)
E
(K)
(39)
22
i=1
23

---

Under review as a conference paper at ICLR 2023
since B(( ]=] O(s) and (i (2 (1) by Lemma and 4 Furthermore, have
maxigism 12 u; - since u, I 2_ By applying the Bernstein's inequality, we
can show that
81 Ipllz
(
x(()) - 11 (k) 12l101222 cos
S 2 exp
2
+ (t) + (0
I exp (-0 l|p())
(40)
where the second inequality is due to the assumption ||l|| = (vv)). To make this probability less
than 5, it is sufficient to have 2 52
of log :)
We next prove equation 37 by bounding equality, we have
||
(K) cos 0 ||ppllrr By the triangle in- 11 11
(K)
(k) 12 12llpller, (R) cos 0 - -11pller
1 | l2 (1rll cos 11p12r cos 0
(41)
+ [pller? (K) cos - ||pllrr
Note that
1
| (1)))11211 12llp11er3
(k) cos 0 - -11pll2r, (k)
cos 0
= rr (k)
cos 0 | 112
(42)
1
S Osin ((u .p'))
- (ns)'
with probability 1 - (n + m)- by Lemma 3 and 4 and also note that
||lllr]*)) cos ( = r (1 - cos 0)
|pl|
(43)
(sin 0(u -p))) + (ns)*
with probability 1- (n + m) -8 by Lemma and than 51 is sufficient to have Ω 2.
To make these errors of order 1/0 (ns) less
61m
By combining the above results, it can be guaranteed that with probability at least if the sampling probability
Y
(R)
a(())
[1ller
< 0||lp|1
28
max 12 8fllp11B
log 1)
}
1
1
8 1p11p1 log 1)
1
=2
(44)
81n
where the last equality due to ||p|| = ( (vn). The condition = 2(log(n + +m)mm) in Lemma
3 is immediately satisfied by equation 44 when O(m/ (mm/logm m).
Proof of Theorem 1
By using Lemma we next prove Theorem I
By applying the union bound
over l [K], if θ
log K then have
87 [ill
[1 51) u/ (k)
1 (Y (k) x < (1 + 61). Ak: E [K]
(45)
for any & > and j E [m] with probability at least - c. Under the condition equation 4 E (1/2, 1) and min 2q:-1 1-g. we can guarantee that
45
for any
1
4j +
K - (1-o0 45) - and
K - (1 +1 K 6,
+8
(46)
K
24

---

Under review as a conference paper at ICLR 2023
which implies hو) (gg, h2) for (āg. hy) defined in equation This proves equation 8 of Theorem I
We next prove equation
9 the accuracy guarantee in estimating the task difficulty vector q. After
estimating (1 by es (Ak = ( a(!),, we estimate l/Pl2 by calculating I where 1; ==
K_ K-2 ERAB
Au (k) and / := N. ンm= 44. Assume that ||]p|2 4 - l|p|l26'. We will specify
4 199)
the required order of 8' later. Remind that the estimate for qj is defined as ŪJ := *
Under (k) I || both of which are satisfied under the
the condition that 93 9j and |0, 112llar,
conditions of Lemma we have
K 4j 261)
Au (0,)
qi 1 +211)
< 1
(47)
1 1+0 8'
1 1 8'
By the Taylor expansion for I-x = 1 + + (x² as + 0, we have
( - + 26, + 0 = + 8').
(6, 1 5 261 + 6'
(48)
Thus, both the order of 8', which is the estimation error of |p||, and that of 6, which is the estimation error of lpllerr (8) govern the estimation accuracy gf. We next show that we can have 8' (
By Lemma we have [ - 1pller /1) S 1|2||201, which implies
| (1) 201)= S Au (k) I (
(K) + 281).
(49)
Under the condition (ūj, h1) (gjz hT), since A (k) j
t for k + Øz hij we have
||pll2 ||p|2 K
28 K
S 11 K #g
K
Σ
Auf (8) s ||l||2 + ||2||2
26 K
(50)
K 2
and thus 8' equation 9
26, K-2
(())). Thus, it is enough to have s = d
log +) to guarantee
Proof of Corollary 1
By using Lemma 5 and taking the union bound over all tasks j E [m]] as in similar way that of Theorem I
well as & E [K]. we can prove Corollary [
G.2 PROOF OF LEMMA 4
We first prove equation 33
1 (4) 1|2 2
1 50sin2 0(z(())))))
Let I be the set of indices
1 < i S n such that u,
(k)
2 ... Then, we have u,
(k) ppt 2 nVत for all
i E since p- = pp/llpplz
1
due to the assumption that ||p|22 2 n2.n. Thus, we have
nym
[u
(k)
pi)a < llea >= 112.
(51)
VET
By using the triangle inequality, we can show that
(K)
2
2
|
u
n
NEl
SEI
2
Σ
(k)
2
4
P
n
+
ui
p
+
V
172n
(52)
SEI
YE!
A
(N)
4|7
<
+
pp
+
\/
NEl
<
51 (k)
1/2-
25

---

Under review as a conference paper at ICLR 2023
Therefore, get
1 2 ( 11 =
(8) )2
2 - -25/lee(h) p²112-
(53)
iE!
By the law of cosine, we have
pp" (8) 1/22 = sin ((u(A) (())())pp)) + (1
cos cos "=)))",")>> =2 cos ((ee!)) .p")
= 2 - V sin" ((ul()) = 1+ v sin? ((x(k))
sin² 0(u (1)) pp)
(54)
sin ((u (k)
p"
Combining equation 53 and equation 54 proves equation 33
We next prove equation 34
sin ((ū .p") S 6v sin ((u(k) pp).
First, note that || (4) 1/2 Eier
(k) We have
";
sin @( (k), p") S || pll2 v (1()) u ( 1|2 1 (K)
p'1|2 S
61/zz (k)
pp l2
(55)
where the last incquality is from equation 52 Combined with equation (4
we get equation 34
H PERFORMANCE ANALYSIS OF ALGORITHM
H.1 PROOF OF LEMMA
In this lemma, we show that conditioned on (ğ), hg)
(gg, h2) for all j E [m], s(1 - s1)
62m log a ). the estimator p. defined in equation 5
K
1
m2
1 (A وJ or hs))
2
Pi (K 2)
8(1 81)
K
guarantees P P(Ip 1l < 52) 2 1 for any >
Given (0s, h1) = (gز for all j E [m]. since A is independent of (Øj, hz), we have
(A3 = ف3 or h₂)] P(A وT or h₂) s(1 (1)
K
2
2
Pt
+
K
(56)
var (1(42) وز or h,)) S s11 81)-
By applying the Bernstein's 's inequality, we can show that
K -
2 K 2))
(K2))ms(1 1 - s1)82
(K- - 2)ms(1
P
L(A 93 or h2)) s(1 s1) s1))
K pi
K
(K-2)ma(1-s)) 2
S exp
2 K
S exp (ms((1 - 81 )o?))
ms(1
81) + (K 2)ma((1 11001111100 111812
K
(57)
Thus, if the sampling probability satisfies
s(1 - 91) =Ω log
(58)
mod
then we can guarantee that PP(): - Pil < (82 > 1 - e. By taking the union bound over i E [n], if the
sampling probability satisfies
log n
s11 81) = Ω
(59)
mo
then guarantee that TP (1lp pllss 00 52)
26

---

Under review as a conference paper at ICLR 2023
H.2 PROOF OF THEOREM! 2
To prove this theorem, we use similar proof techniques from Zhang et al. (2014). Since the work in Zhang al. (2014) focuses the recovery of only the ground-truth label for each task, generalize the techniques to recover not only the ground-truth label but also the most confusing answer.
We first introduce some notations. Let P(a,)), denote the probability that a worker E [Tx] gives
(i.j)
label & [K] for the assigned task j [ma] of which the top-two answers are hy) (a, b). Let
(G5) = ((,66)11 ((a.b),2
(i.)
(6.j)
M ((.,6), xI. We introduce a quantity that measures the average
[i,s]
1 (a.b)
ability of workers in distinguishing the ground-truth pair of top-two answers (gj. h2) from any other
pair (a,b) E [K]] //g,, h2)} for the j
E [m]]. We define
D = min
Σ DKLL (1:) (1))) ((.)))
D: min D()) jE/ml
(60)
(aa,))((a.b))
==1
where [KL( = P() log( (og((()))(()) is the KL-divergence between P and Q. Note that DD)) is strictly positive if g E (1/2, and there exists at least worker i with pj 0 for the distribution equation 1 so that (gj, h2) can be distinguished from any other (a, b) E [K]3/(0) h,)} statistically. We define D as the minimum of D over j E [m], indicating the average ability of workers in distinguishing (gj, h2) from any other (a, b) for the most difficult task in the set.
Let us define an event that will be shown holding with high probability,
K
(i.)
(Ay = 1b) log
2 nsD/2 for all j E [m]] and (a, 6) E [X] hz).
(1.))
((a,)),k
(61)
Define
= Σ k) log (Monn / ((.b).,))
(i:))
(6-5)
(62)
km
We can see that .t....,,. are mutually independent on any value of (gj. h2). and each 1 belongs to the interval [0, log(1/p)) where (1,5) easily show that
"(gj.kg). p for all (f, B3: hy [m] [m]] [K].. We can
E
Σ
(gj h1)
(ir) Σ sDKL (H
H (a.b))
(5.5)
(63)
We define
Σ TKL (1((2))) (t.)) (1)))))) ((.))
D
(
(64)
The following lemma shows that the second moment of bounded above by the KL-divergence between the label distribution under (gj. h2) pair and the label distribution under (a, b) pair.
Lemma 6. Conditioning on any value of (gg, h2). we have
2 2log(1/p)
alDkI. (1 (2.1) [ (g), h1)] S 1-p
(65)
The proof of this lemma be obtained by following the proof of the similar result, Lemma 4 of Zhang et al. (0014).
According to Lemma the aggregated second moment of I, is bounded by
E
12 (gj, h1)
<
2 2log(1/p)
slkL (Ht (t.f)
1 1-p
1=1
(66)
2 (log(1/p)
sD.
1 1-p
27

---

Under review as a conference paper at ICLR 2023
Thus, applying the Bernstein's inequality, have
2 1 - exp (-Z (sD/2)) 1-p
P
Σ 4 z 8D/2
222DD/2
(g3> k1g
(67)
[2loR(1/0) sD + (2 (20o)(11)))ss/)))
Since S 1/2 and D 2 nD j E [m], we have
2 nDD combining the above inequality with union bound over
n&D
P - mK exp
(68)
33log(L/p)
The maximum likelihood estimator finds pair of (a, b) E [K] a a b, maximizing
(ăj, h,)
arg max
II
IP(A; p. Qj (a, b))
[a. o,,bbbbbbbbbb i=1
arg max
log PAi Pp, 45 (a, ())
[k] [K]]]]]],a ,asth i=1
I(A = log (i.)
arg max
(a.b)..
(69)
(n.M) ,apth i=1 k=1
The plug-in MLE in equation
6 on the other hand, finds pair of (a, b) E [K]P, b, maximizing
K ΣΣ (Aig =M log (3.1 (a,b).
(āS hy)
arg max
(70)
(a.
where (2.3)
P(a.)). the estimated probability that worker E [n] gives label & [K] for the assigned
task j E [m] of which the top two answers are (gjz h2) = (a, b) assuming p; = P. from equation
and Qj = d from equation 4 in the distribution equation [ Thus, for the plug-in MLE correctly
find the ground-truth top two answers (gj, ht), we need to satisfy the following event:
K
(Aig = k:) log ( ( (a.b), 2 0 for all (a, b) E [K] x (Kj)).))s). (71)
1=1 1=1
For any arbitrary (a, b) * (gg: hz), consider the quantity
Q(a,)) Σ
1(A, k:) log (1J)
/ (a.b).))
(72)
which can be written as
((a,)) 1(A log
n
M
(15)
Σ>
a
K
(Ais k) log
Parhiia (5.5
log
(o,b).
(1-)
(12)
(b.2)
((a.b).
((a,)).k
(73)
Assuming that there exist p > 8g such that
(1.1) (a,b),. 2 and ( - M(a,b), I 8g for all i [m].] E [m], (a, E [K]3
(3.1)
(74)
we have
(t.f)
(8.3) (t,f)
(gg. log (t.5)
((a,),,k (t,1)
P p)
max [[[K]
log
2
(75)
p- 5z
((ss.hy).t
(la.b),k
By the Bernstein's 's inequality, we also have
ΣΣ
Σ
n K
[(A = k)) ns > ns
]
< exp
(-
+ (1ss/2)
(ns/2)2
= -exp (- 3ns
(-28)
(_nns)
28
(76)
k=1
28

---

Under review as a conference paper at ICLR 2023
By taking the union bound over j [m], we have
K
|3ns
P
(Ai = k) - ns > nns/2 for any j E [m]]
$ m exp
(77)
28
Under the intersection of the event Σラ= En=1 1 [Ais = k) ns I ns/22 for all j [mi] and the
event E, we guarantee
(1))
K
(1-1)
A (12)
((a.b)
Σ
(Ai
k)) log
(ggshs).kk
1 (Ais = k)
log
llog
(a,b).
(4.)
(1,5)
(b5))
k=1
==1
(1,k)
M4 (a,b),
2 nsD
P
D
363 53
3ns log
2
ns8
00
2
03
(78)
for every E [m]] where the last inequality holds if
D
0g < P
(79)
6 D
In summary, under that the event
E ii=1 Σ 1=1 (Air k) -s8 S ns/2 for all j E [m]] and the
event & hold, if we have dz such that
Ma..),. (a.b),
(5.5) (h.2)
5g for all i E [m],] [m], (a, [K]²
(80)
and
D
83 < p and
83 < D
(81)
then we can guarantee that the plug-in MLE in equation 70 successfully recovers the pair of top two
(gj, hT) for all the tasks j E [m]. To make the right-hand side of equation 68 and equation 77
less
than e/2, it sufficient have
Ω log((1/) (o(mm + D llo(mm/e) nD
(82)
Lastly, when we have
max(llp
91100} S 8,
(83)
can guarantee that
(i.1)
(o.b)..
(a,
I 46 = 63.
(84)
Thus, is sufficient to guarantee equation
83 with
p
pD
8 min
(85)
4(6 + D)
I PROOF OF THEOREM 3
1.1 PROOF OF PART (A)
To prove this minimax bound, we use the similar arguments from Karger et al. (004)). In particular, we consider spammer-hammer model such that
0, for sis [(1 10--pp1 p)nl
p; =
(86)
1, otherwise.
Assume that total I, workers randomly sampled from [n] provide answers for the task j. Under the spammer-hammer model, the oracle estimator makes mistake on task j with probability K)/K if it is only assigned spammers. When 1, is the number of assignments, we have
K-1 (1 (1-
P(0; *g,)
(87)
K
29

---

Under review as a conference paper at ICLR 2023
By convexity and using Jensen's inequality, the average probability of error is lower bounded by z
K
P(0; + タj)
(1 -D)
(88)
m jE|m]
K
where J. Eie(m) 4 S I. By assuming 2/3, we have (1 P)) 2 e (T+7') Thus,
min PETS. DE K]
max
1
P(g + 91) K -
(0+p"))
K - 2pl
E-2pl
(89)
mI
K
K
JE
The inequality in equation 89 implies that is less than the minimax error in equation 89 less than e. Since the average number of queries per task in our model is ns, it implies that it is necessary to have 12 |pp log
2n log (K-1). then no algorithm can make
1.2 PROOF PART (B)
To prove the second part of the theorem, we use proof techniques from Zhang et al. (201)). but generalizes the results for pair of top two answers. We assume that je E ml) (ge, he) [K]² and (a,, bb) E [K]2 are the task index and the pairs of labels such that
(f.Jc) (t.de) (M H (ac,bo))
DKL
(90)
Y2
for D defined in equation 60
Let Q be uniform distribution over the set {ge, he), (aer be]l". For any (g, h), we have
((0r, h1) + (gg. h2))) (g. h) = (v, u)
max (u,u)E[K m V/lml
(91)
Σ
Q((v, u)) [((0), h1) * (o), (b)) k.)) = (v, (v.2)) w)
1=1 (ow.)ello..hhhaaa....
Let A = {Ai : E [n], E [m]} be the set of observations. Define two probability measures Po and P1, such that Po is the measure of A conditioned on (gj: hy) (ge, he), while P1 is that
(gj, h1) = (ac, be). Then, we can have
Σ
Q((o, W)) [((0s) hy) + (0,, h2) hj) h) h)= (v, m)
Q((gg,,h) h,) (9c, P h1) (gc. he)) + 2l(g, (a ( h,) + (ac, bc))
2 2 2
[Po - PPllIV
1
(P', Pt). 2 4
(92)
where the second to the last inequality is by Le Cam's method and the last inequality is by Pinsker's inequality
Conditioned on (9), h2). the set of random variables A, {Ay [n]] are independent of A for both IP and P,, and thus
DK (Po, PP) Di (P,)), DKL (A)AA
DD (PP (A)))
(93)
'The total variation distance between probability distributions P and Q defined on set X is defined as the maximum difference hetween probabilities they assign on subsets of X:: Q1lTv = supAcx PP(A) ((A))
30

---

Under review as a conference paper at ICLR 2023
where P(X) denote the distribution of X with respect to the probability measure P. Given (g), h2),
since Aij....; Ang are independent, we can show that
DKL (M(Po(A)))P(AA)) = DKL (P))))
1
+ +DLL (p( H (auste))
(15)
(94)
5) log
-
Σ snD.
Combining equation
equation 94 we have
Σ
1 ((0j, h2) + (0j, (g)))))) h) = (u,
max ( K| x[K]
m
1=1
(95)
2 2 sn
Thus, s <
I then the above inequality is lower bounded by 3/8. This completes the proof.
4nD
J USEFUL INEQUALITIES
In this section, we summarize the usefull inequalities used in the proof of the main results.
The following inequality, which appeared in Bandeira & Van Handel (2016) provides a non- asymptotic spectral norm bound for random matrices with independent random entries.
Theorem 4 (Spectral norm bound of random matrice with independent entries). Consider dom matrix Raxm, whose entries are independently generated and obey
s = 0, and [Xasl SB, B, isism, 15i5 m.
(96)
Define
v: max
max E[X2,]
max EE[X
(97)
Then there exists some universal constant
such that for any t
0,
t²
P [ 2 4 +t s (n + m) exp
(98)
cB2
We also present a useful corollary of Theorem which can be shown from equation 98 by setting
č = V and t = B / log(n + m).
Corollary 3 (Corollary of Theorem 4 E[X & o² for all i,j and satisfying conditions in Theorem then we have
X < 4a / max(m, n) TB Vogglonn---.// m)
(99)
with probability 1 - (n + m)-
8 for some conslunt ē> 0.
We next summarize the eigenspace perturbation theory for asymmetric matrices with singular value composition (SVD). Suppose X := XX. X1] and Z = ZZ, Z, are orthonormal matrices. When
we define the distance between two subspaces X, and Zp by
dist(Xo: Zo) X Zo Z
(100)
then we have
dist Xo, Zo) = || Z 12 XiII
(101)
31

---

Under review as a conference paper at ICLR 2023
Given |X Zu! || I I, write SVD of X₁j Zo Rx as X Zu U cos T where cos O diag(co cos fj..... cos f,). We call {01..... /r) principal angles between Xo and Zo. Then, we have
X Zi sin Ø| max sin 011. TM. 0.l)
(102)
Let M and M M + E be two matrices R= with n S m, whose SVD are represented by M = E of and M - o,u;v;" where 01 2 ... 2 On (resp. of 2 ... 2 o,))
Let us define
U0 u1 u,l E R Vo V1 U Rmxr.
(103)
The matrices Ug and Vo are defined analogously. Theorem (Wedin sin θ Theorem). If E| < of - T then one has
/2I E
max U,) ||dist Vo. Vo
(104)
o - 0 E
where Ug (Vo) and Uo (Vo) are subspaces spanned by the largest left (right) singular vectors of M and M, respecively.
Lastly, we also write down two useful concentration inequalities.
Theorem 6 (Hoeffding). Let X1, .2....... Xn be independent random variables such that X₃ E [a;, b.] for 1 Si i n. Then, we have
2t
P
Σ (x, E(X,)) 1=1
< 2exp
(105)
Σ Ei=1 (b: a;33
Theorem 7 (Bernstein). Let X1, N [a,, bo]for 1 sis Let == maxi
X, be independent random variables such that X; E a;) and 0² = i Then we have
var(X.).
82/2
Σ (X; E(X,)) > 22cxp
(106)
32


Reviews:
[{"review_id": "rzCI6K9MeF", "reviewer": "Reviewer_pX1G", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a \"top-two\" model in which crowdsourcing tasks admit two plausible answers (the ground truth and a \"confusing\" answer). The authors argue and show that this model can be applied to many of the crowdsourcing tasks used for existing public datasets. In this framework, they describe a two-stage algorithm to infer the two types of answers and the workers' abilities. The first stage uses SVD on a transformation of a split of the workers x task answers matrix to estimate the difficulty of the task (defined in their eq 1). The second stage obtains the final estimates of the workers' abilities and task difficulty via maximum likelihood. The authors conduct a performance analysis of the algorithm and show that it recovers the two most plausible answers. Lastly, they conduct experiments on both synthetic and real-world datasets, including training a neural network with the top two answers rather than soft labels or the majority vote. ", "summary_of_the_review": "The authors propose to model the difficulty of crowdsourcing tasks with two plausible answers and carefully details the properties of the proposed algorithm in this framework. I only have minor concerns and questions about the existing work that I hope the authors can address in their answer. ", "strength_and_weaknesses": "I found that the paper provided a thorough description of the existing methods (although I am not an expert on this), clearly characterized the proposed model, and contained an extensive description of the the theoretical and empirical properties of the algorithm. The experiments seemed to be reasonable. I only have the following minor comments: \n\n* 10 repetitions of the experiments to estimate the standard deviation is not enough to get accurate estimates (neither of the mean nor of its sampling variation). This should be increased. In addition, please report the 95% confidence intervals. Based on the reported errors, the intervals might reveal that the performances of the algorithms are not significantly different. The shaded regions in Figure 2a should be described. \n* What happens in the \"easiest\" case where the q=1? Does any of the other algorithms outperform Toptwo2 or Toptwo1?\n* Can the model be easily extended to more than two plausible tasks? \n* How does performance vary in settings where crowdworkers are all experts with similar ability (p=1)?\n* Details about IRB approval for the experiment that has been run should be provided. \n\nTypos: * \"ssume\" in footnote 2. \"achieveed\" in page 8. \n* \"lower bound for the performance\" -> upper bound for the performance and lower bound for the error probably?\n* \\eta is described in footnote 2 and then appears in algorithm 1. It might be worth reintroducing it.  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "pJtU5_upNZ", "reviewer": "Reviewer_oTxe", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In crowd-computing tasks there are often two causes for wrong answers: 1) low reliability of worker (i.e. possibly a spammer or someone making a random guess), 2) confusion due to task (or question) difficulty (i.e. the question is simply harder than others or the potential answers could be confusing). The David-Skene model only captures the worker reliability portion of this. The authors have built a model for multi-choice crowdsourcing, that infers the top-two answers and the confusion probability. This would benefit downstream uses of these crowdsource tasks by providing the most plausible answer other than the ground truth and how plausible that second answer is. The authors show how using this top-two information can add neural network training versus using a single hard label.", "summary_of_the_review": "Overall it was a well written paper. The evaluations on the synthetic and real-world datasets were well done. I am unsure of the results of the neural network training.", "strength_and_weaknesses": "- The authors evaluate on both synthetic and real-world datasets. They also demonstrate how their model can improve neural network performance.\n- As I was reading through the paper I wondered why only top-two, the authors provided good explanation in the appendix using analysis of public crowdsourcing datasets.\n\nWeakness\n- 5.3, It isn't clear to me that top-two is much better than full distribution. ", "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": "oUTGRn8Hdb", "reviewer": "Reviewer_UdYX", "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": "In order to simulate the effect of confusion in multi-choice crowdsourcing problems, this paper proposes a new multi-choice crowdsourcing task model and provides a two-stage inference algorithm to recover the first two answers and the confusion probability of each task. Finally, it shows the potential application of the proposed algorithm.", "summary_of_the_review": "Most previous multiple-choice crowdsourcing models cannot simulate this kind of confusion of plausibility. This paper provides an effective two-stage inference algorithm to reply to the first two plausible answers and confusion probability and can achieve the optimal convergence speed. This method is compared with other recent crowdsourcing algorithms and achieves superior results. This paper is relatively innovative.", "strength_and_weaknesses": "Please refer to Summary Of The Review.", "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": "lmk2WAAM2G", "reviewer": "Reviewer_mv6B", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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 considers the multiple-class crowdsourcing problem, where the confusing answers and confusion probability are considered. To address this problem, a new model was proposed to identify the top-two plausible answers for every task. Based on the proposed model, a new algorithm was also developed. To show the effectiveness of the proposed model, both theoretical guarantees and empirical evaluations are provided.", "summary_of_the_review": "In my opinion, this work is not ready to be published yet. The baseline methods used are not start-of-art methods. The novelty of this work is kind of limited. Also, the organization of this paper can be further improved.", "strength_and_weaknesses": "This work is technically sound, to show the effectiveness of the proposed method, some theoretical guarantees are provided, also some experiments on both synthetic and real datasets were implemented. However, this work can be further improved in the following aspects:\n\n- The baseline methods used are not state-of-art methods. The most recent crowdsourcing method is from 2018. It would be better to compare with more recent works like [1] and \n[1]https://proceedings.neurips.cc/paper/2020/file/f86890095c957e9b949d11d15f0d0cd5-Paper.pdf\n[2] https://dl.acm.org/doi/10.5555/3454287.3454992\n\n- All the figures are not vector graphs. It should be revised.\n\n- It is not quite clear how the proposed model and algorithm can be applied to real applications.\n\n- The organization of this work is not clear enough, especially the theoretical analyses part. It would be better to have some discussions after the proposition and theorem.\n\n- I also have concerns about the novelty of the proposed model and algorithm. There already exists some work to divide the prediction in crowdsourcing into two stages, where the first stage is focusing on filtering the top answers, and the second stage is doing the prediction. Also, there exist some works to predict the reliability of the workers to do prediction. The proposed model gives me the impression that it is a combination of these methods. I am not sure how much insight this work can bring to the study of crowdsourcing or the ML community.\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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject