Exact Exponent in Optimal Rates for Crowdsourcing

arXiv:1605.07696v2 [stat.ML] 26 May 2016

Chao Gao1, Yu Lu1 , and Dengyong Zhou2
1

2

Yale University
Microsoft Research, Redmond
May 27, 2016

Abstract
In many machine learning applications, crowdsourcing has become the primary means
for label collection. In this paper, we study the optimal error rate for aggregating labels
provided by a set of non-expert workers. Under the classic Dawid-Skene model, we
establish matching upper and lower bounds with an exact exponent mI(π) in which m is
the number of workers and I(π) the average Chernoff information that characterizes the
workers’ collective ability. Such an exact characterization of the error exponent allows
1
log 1ǫ in order to achieve an
us to state a precise sample size requirement m > I(π)
ǫ misclassification error. In addition, our results imply the optimality of various EM
algorithms for crowdsourcing initialized by consistent estimators.

1

Introduction

In many machine learning problems such as image classification and speech recognition, we
need a large amount of labeled data. Crowdsourcing provides an efficient while inexpensive
way to collect labels. On a commercial crowdsourcing platform like Amazon Mechanical
Turk [1], in general, it takes only few hours to obtain hundreds of thousands labels from
crowdsourcing workers worldwide, and each label costs only several cents.
Though massive in amount, the crowdsourced labels are usually fairly noisy. The low quality is partially due to the lack of domain expertise from the workers and presence of spammers.
To overcome this issue, a common strategy is to repeatedly label each item by different workers, and then estimate truth from the redundant labels, for example, using majority voting.
Since the pioneering work by Dawid and Skene [7], which jointly estimates truth and workers’
abilities via a simple EM algorithm, various approaches have been developed in recent years
for aggregating noisy crowdsourced labels. See [21, 20, 16, 11, 3, 13, 23, 6, 24, 19, 15, 17] and
references therein.
Compared with the active progress in aggregation algorithms, statistical understandings
of crowdsourcing do not get much attention except [10, 12, 22, 4]. These papers not only
show exponential convergence rates for several estimators, they also provide lower bounds
1

to justify the optimality of the rates. However, the exponents found in these work are not
matched in their upper and lower bounds. They are optimal only up to some unspecified
constants. The main focus of this paper is to find the exact error exponent to better guide
algorithm design and optimization.
Main Contribution. We study the minimax rate of misclassification for estimating the
truth from crowdsourced labels. We provide upper and lower bounds with exact exponents
that match each other. The exponent has a natural interpretation of the collective wisdom of
a crowd. In the special case where each worker’s ability is modeled by a real number
 p pi ∈ [0, 1],

1 Pm
the exponent takes a simple form −(1+ o(1))mI(p) with I(p) = − m i=1 log 2 pi (1 − pi )
being the average Rényi divergence of order 1/2. Therefore, in order to achieve an error of ǫ in the misclassification proportion, it is necessary and sufficient that the number
of workers m satisfies m ≥ (1 + o(1))I(p)−1 log(1/ǫ). Note that in previous work, only

m = Ω I(p)−1 log(1/ǫ) can be claimed. Moreover, our general theorem has implications on
the convergence rates of several existing algorithms.
This paper is organized as follows. In Section 2, we present the problem setting. In
Section 3, given the workers’ abilities, we derive the optimal error exponent. In Section 4,
we show that spectral methods can be used to achieve the optimal error exponent, followed
by a discuss on other algorithms in Section 5. The proofs are gathered in Section 6.

2

Problem Setting

Let us start from the classic model proposed by Dawid and Skene [7]. Assume there are m
workers and n items to label. Denote the true label of the jth item by yj that takes on a
value in [k] = {1, 2, ..., k}. Let Xij be the label given by the ith worker to the jth item. The
ability of the ith worker is assumed to be fully characterized by a confusion matrix
(i)

πgh = P(Xij = h|yj = g),

(1)

(i)
h=1 πgh = 1. Givenyj = g, Xij is generated
(i)
(i)
(i)
parameter πg∗ = πg1 , ..., πgk . Our goal is to estimate

which satisfies the probabilistic constraint

Pk

by a multinomial distribution with
the true labels y = (y1 , · · · , yn ) using the observed labels {Xij }. Denote the estimate by
ŷ = (ŷ1 , ..., ŷn ). The loss is measured by the error rate
n

L(ŷ, y) =

1X
I{ŷj 6= yj }.
n

(2)

j=1

We would like to remark that the true labels are considered as deterministic here. It is
straightforward to generalize our results to stochastic labels generated from a distribution.
Also, we assume that every worker has labeled every item. Otherwise, we can regard the
missing labels as a new category and the results in this paper stay the same.
2

3

Main Results

In this section, we assume the confusion matrices {π (i) } are known. Our goal is to establish
the optimal error rate with respect to the loss in Equation (2). Let Pπ,y be the joint probability
distribution of the data {Xij } given π and y specified in (1), and let Eπ,y be the associated
expectation operator. Then the optimality is characterized by
M = inf sup Eπ,y L(ŷ, y),

(3)

ŷ y∈[k]n

which identifies the lowest error rate that we can achieve uniformly over all possible true
labels.
Our main result of the paper is to show that under some mild condition the minimax risk
(3) converges to zero exponentially fast with an exponent that characterizes the collective
wisdom of a crowd. Specifically, the error exponent is −mI(π) with
I(π) = min C(πg∗ , πh∗ ),

(4)

g6=h

where C(πg∗ , πh∗ ) is given as
m
k 

 
X
1 X
(i) t
(i) 1−t
− min
πhl
log
πgl
0≤t≤1 m
i=1

l=1

!

.
(i)

To better present our main result, let us introduce some notations. Let ρm = mini,g,l πgl .
Suppose the minimum of C(πg∗ , πh∗ ) is achieved at g = a and h = b. For any α > 0, we
define a set of workers
n
o
(i)
(i)
(i)
(i)
Aα = i ∈ [m] : πaa
≥ (1 + α)πab , πbb ≥ (1 + α)πba .

These workers in Aα have better expertise in distinguishing between categories a and b. Then,
our main result can be summarized into the following theorem.
√
Theorem 3.1. Assume log k = o(mI(π)), | log ρm | = o(ρm |A0.01 |1/2 ) and | log ρm | = o( mI(π)),
as m → ∞. Then, we have
inf sup Eπ,y L(ŷ, y) = exp (−(1 + o(1))mI(π)) ,
ŷ y∈[k]n

where I(π) is defined by (4).
In Theorem 3.1, the assumption that | log ρm | = o(ρm |A0.01 |1/2 ) can be relaxed to that
| log ρm | = o(ρm α|Aα |1/2 ) for some α > 0. To better present our result, we set α = 0.01 in
the theorem. To prove the upper bound, we only need the first assumption log k = o(mI(π)).
The other two assumptions on ρm are used for proving the lower bound. One could imagine
that the larger ρm is, the more mistake we might make to estimate the true labels. When
there is a constant c (independent of m) such that ρm ≥ c, the last two assumptions reduce
3

√
√
to |A0.01 | → ∞ and mI(π) → ∞. That means as long as I(π) = Ω(1/ m) and the number
of experts goes to infinity as m grows, exp(−(1 + o(1))mI(π)) serves as a valid lower bound.
Theorem 3.1 characterizes the optimal error rate for estimating the ground truth with
crowdsourced labels. It implies exp (−(1 + o(1))mI(π)) is the best error rate that can be
achieved by any algorithm. Moreover, it also implies there exists an algorithm that can
achieve this optimal rate. The error exponent depends on an important quantity I(π). When
m = 1 and k = 2, this theorem reduces to the Chernoff-Stein Lemma [5], in which I(π) is the
Chernoff information between probability distributions. For the general problem, C(πg∗ , πh∗ )
(i) m
(i)
can be understood as the average Chernoff information between {πg∗ }m
i=1 and {πh∗ }i=1 , which
measures the collective ability of the m workers to distinguish between items with label g
and items with label h. Then, I(π) is the collective ability of the m workers to distinguish
between any two items of different labels. The higher the overall collective ability mI(π), the
smaller the optimal rate.
By Markov’s inequality, Theorem 3.1 implies
n

1X
I{ŷj 6= yj } ≤ exp (−(1 + o(1))mI(π)) ,
n
j=1

with probability tending to 1. This allows a precise statement for a sample size requirement
to achieve a prescribed error. If it is required that the misclassification proportion is no
1
greater than ǫ, then the number of workers should satisfy m ≥ (1 + o(1)) I(π)
log 1ǫ . A special
P
case is ǫ < n−1 . Since n1 nj=1 I{ŷj 6= yj } only takes value in {0, n−1 , 2n−1 , ..., 1}, an error
rate smaller than n−1 implies that every item is correctly labeled. Therefore, as long as
1
log n, the misclassification rate is 0 with high probability.
m > (1 + o(1)) I(π)
When k = 2, a special case of the general Dawid-Skene model takes the simple form
#
"
# "
(i)
(i)
π11 π12
pi
1 − pi
.
(5)
(i)
(i) =
1 − pi
pi
π21 π22
This is referred to as the one-coin model, because the ability of each worker is parametrized
by a biased coin with bias pi . In this special case, I(π) takes the following simple form
I(π) = I(p) = −

m
 p

1 X
log 2 pi (1 − pi ) .
m

(6)

i=1


 p
Note that −2 log 2 pi (1 − pi ) is the Rényi divergence of order 1/2 between Bernoulli(pi )
and Bernoulli(1 − pi ). Let us summarize the optimal convergence rate for the one-coin model
in the following corollary.
Corollary 3.1. Assume max1≤i≤m (| log(pi )| ∨ | log(1 − pi )|) = o(mI(p)), Then, we have
inf

sup Ep,y L(ŷ, y) = exp (−(1 + o(1))mI(p)) ,

ŷ y∈{1,2}n

where I(p) is defined by (6).
4

Corollary 3.1 has a weaker assumption than that of Theorem 3.1. When each pi is
assumed to be in the interval [c, 1 − c] with some constant c ∈ (0, 1/2), the assumption of
Corollary 3.1 reduces to mI(p) → ∞, which is actually the necessary and sufficient condition
for consistency.
The 
result of Corollary 3.1 is very intuitive. Note that the Rényi divergence
 p
−2 log 2 pi (1 − pi ) is decreasing for pi ∈ [0, 1/2] and increasing for pi ∈ [1/2, 1]. When
most workers have pi ’s that are close to 1/2, then the rate of convergence will be slow. On
the other hand, when pi is either close to 0 or close to 1, that worker has a high ability,
which will contribute to a smaller convergence rate. It is interesting to note that the result
is symmetric around pi = 1/2. This means for adversarial workers with pi < 1/2, an optimal
algorithm can invert their labels and still get useful information.

4

Adaptive Estimation

The optimal rate in Theorem 3.1 can be achieved by the following procedure:
Y Y  (i) I{Xij =h}
ŷj = arg max
πgh
.
g∈[k]

(7)

i∈[m] h∈[k]

This is the maximum likelihood estimator. When k = 2, it reduces to the likelihood ratio test
by Neyman and Pearson [14]. However, (7) is not practical because it requires the knowledge
of the confusion matrix π (i) for each i ∈ [m]. A natural data-driven alternative is to first get
an accurate estimator π̂ of π in (7) and then consider the plug-in estimator,
ŷj = arg max
g∈[k]

Y Y  (i) I{Xij =h}
π̂gh
.

(8)

i∈[m] h∈[k]

In the next theorem, we show that as long as π̂ is sufficiently accurate, (8) will also achieve
the optimal rate in Theorem 3.1.
Theorem 4.1. Assume that, as m → ∞,


X
(i)
(i)
max log π̂gh − log πgh > δ → 0
P max
g∈[k]

i∈[m]

h∈[k]

(9)

with δ such that δ + log k = o(mI(π)). Then, for any y ∈ [k]n , we have
n

1X
I{ŷj 6= yj } ≤ exp (−(1 + o(1))mI(π)) ,
n
j=1

with probability tending to 1, where I(π) is defined by (4).
Theorem 4.1 guarantees that as long as the confusion matrices can be consistently estimated, the plugged-in MLE (8) achieves the optimal error rate. In what follows, we apply
this result to verify the optimality of some methods proposed in the literature.
5

4.1

Spectral Methods

Let us first look at the spectral method proposed in [22]. They compute the second and
third order empirical moments and then estimate the confusion matrices by using tensor
decomposition. In particular, they randomly partition the m workers into three different
groups G1 , G2 and G3 to formulate the moments equations. For (a, h) ∈ [3] × [k], let
⋄
=
πah

1 X (i)
πh∗ ,
|Ga |

ωh =

i∈Ga

|{j : yj = h}|
.
n

⋄ is a k dimensional vector and we denote its lth component as π ⋄ . They use
Note that πah
ahl
two steps to estimate the individual confusion matrices. They first estimate the aggregated
⋄ by deriving equations between the moments of the labels {X } and
confusion matrices πa∗
ij
⋄ ,
the following moments of πah
X
X
⋄
⋄
⋄
⋄
⋄
.
⊗ πah
⊗ πah
, M3 =
ωh πah
⊗ πah
M2 =
ωh πah
h∈[k]

h∈[k]

Empirical moments are used to approximate the population moments. Due to the symmetric
structure of M2 and M3 , a robust tensor power method [2] is applied to approximately solve
these equations. Then they use another moment equation to get an estimator π̂ (i) of the
⋄ .
confusion matrices π (i) from the estimator of πah
⋄ } and σ be the minimum kth
⋄
− πahl
Let ωmin = minh∈[k] ωh , κ = mina∈[3],l6=h∈[k]{πahh
k
P
⋄ ⊗ π ⋄ for a, b ∈ [3]. Applying Theorem 1 in
eigenvalue of the matrices Sab = h∈[k] ωh πah
bh
[22] to Theorem 4.1, we have the following result.
log m
Theorem 4.2. Assume log k = o(mI(π)) and ρm I(π) ≤ min{ 36kκ
ωmin σL , 2 log m}. Let ŷ be
the estimated labels from (8) using the estimated confusion matrices returned by Algorithm 1
in [22]. If the number of items n satisfies

 5
k log3 m log k
n=Ω
2 σ 13 ,
ρ2m I 2 (π)ωmin
k

then for any y ∈ [k]n , we have
n

1X
I{ŷj 6= yj } ≤ exp (−(1 + o(1))mI(π)) ,
n
j=1

with probability tending to 1, where I(π) is defined by (4).
Combined with Theorem 3.1, this result shows that an one-step update (8) of the spectral
method proposed in [22] can achieve the optimal error exponent.

4.2

One-coin Model

For the one-coin model, a simpler method of moments for estimating pi is proposed in
[10]. Let n1 = |{j : yj = 1}|, n2 = n − n1 , and γ = n2 /n. They observe the equation
6

1
n

Pn

j=1 P {Xij

= 2} = γpi + (1 − γ)(1 − pi ). This leads to a natural estimator
p̂i =

1
n

Pn

j=1 I {Xij

= 2} − (1 − γ̂)

2γ̂ − 1

,

(10)

where γ̂ is a consistent estimator of γ proposed in [10]. Combining the consistency result of
p̂i in [10] and Theorem 4.1, we have the following result.
Theorem 4.3. Assume |2γ − 1| ≥ c for some constant c > 0, ρm ≤ pi ≤ 1 − ρm for all
1 P
4
2
i ∈ [m] and m
i∈[m] (2pi − 1) ≤ 1 − m . Let ŷ be the estimated labels from (8) using (10).
If the number of items n satisfies
 2

log m log n
n=Ω
,
ρ2m I 2 (p)
then for any y ∈ [k]n , we have
n

1X
I{ŷj 6= yj } ≤ exp (−(1 + o(1))mI(p)) ,
n
j=1

with probability tending to 1, where I(p) is defined by (6).

5

Discussion

In this section, we show the implications of our results on analyzing two popular crowdsourcing algorithms, EM algorithm and majority voting.

5.1

EM Algorithm

In the probabilistic model of crowdsourcing, the true labels can be regarded at latent variables.
This naturally leads to apply the celebrated EM algorithm [8] to obtain a local optimum of
maximum marginal likelihood with the following iterations [7]:
• (M-step) update the estimate of workers’ abilities
X
(i)
P(t) {yj = g} I{Xij = h}
π(t+1),gh ∝

(11)

j

• (E-step) update the estimate of true labels
P(t+1) {yj = g} ∝

Y
i,h

(i)

π(t+1),gh

I{Xij =h}

(12)

The M-step (11) is essentially the maximum likelihood estimator. Bayesian versions of
(11) are considered in [16, 13]. Though the E-step (12) gives a probabilistic predication of
the true label, a hard label can be obtained as ŷj = arg maxg∈[k] P(t+1) {yj = g}. According
7

to Theorem 4.1, as long as the M-step gives a consistent estimate of the workers’ confusion
matrices, the E-step will achieve the optimal error rate. This may explain why the EM
algorithm for crowdsourcing works well in practice. In particular, as we have shown, when it
is initialized by moment methods [22, 10], the EM algorithm is provably optimal after only
one step of iteration.

5.2

Majority Voting

Majority voting is perhaps the simplest method for aggregating crowdsourced labels. In what
follows, we establish the exact error exponent of the majority voting estimator and show that
it is inferior compared with the optimal error exponent. For simplicity, we only discuss the
one-coin model. Then, the majority voting estimator is given by
ŷj = arg max

g∈{1,2}

m
X

I{Xij = g}.

i=1

Its error rate is characterized by the following theorem.
Theorem 5.1. Assume pi ≤ 1 − ρm for all i ∈ [m], ρ2m
√
and | log ρm | = o( mJ(p)). Then, we have

P

i∈[m] pi (1

− pi ) → ∞ as m → ∞

sup Ep,y L(ŷ, y) = exp (−(1 + o(1))mJ(p)) ,

y∈{1,2}n

where

m



1 X
log pi t + (1 − pi )t−1 .
J(p) = − min
t∈(0,1] m
i=1

The theorem says that −mJ(p) is the error exponent for the majority voting estimator.
Given the simple relation
m



1 X
J(p) = − min
log pi t + (1 − pi )t−1
t∈(0,1] m
i=1

m


1 X
min log pi t + (1 − pi )t−1
≤ −
t>0
m

= −

1
m

i=1
m
X

= I(p),

i=1

(13)


 p
log 2 pi (1 − pi )

we can see that the majority voting estimator has an inferior error exponent J(p) to that of
the optimal rate I(p) in Theorem 4.3. In fact, the inequality (13) holds if and only if pi ’s
are all equal, in which case, the majority voting is equivalent to the MLE (7). When pi ’s are
varied among workers, majority voting cannot take the varied workers’ abilities into account,
thus being sub-optimal.
8

6
6.1

Proofs
Proof of Theorem 3.1

Proof. The main proof idea is as follows. Consider the maximum likelihood estimator (7),
we first derive the upper bound by union bound and Markov’s inequality. The proof of lower
bound is quite involved and it consists of three steps. Based on a standard lower bound
technique, we first lower bound the misclassification rate by testing error. Then we calculate
the testing error using the Neyman-Person Lemma. Finally, we give a lower bound for the
tail probability of a sum of random variables, using the technique from the proof of the
Cramer-Chernoff Theorem [18, Proposition 14.23].
Upper Bound. Let ŷ = (ŷ1 , ..., ŷn ) be defined as in (7). In the following, we give a bound
for P(ŷj 6= yj ). Let us denote by Pl the joint probability distribution of {Xij , i ∈ [m]} given
π and yj = l. Without loss of generality, let yj = 1. Using union bound, we have
P1 (ŷj 6= 1) ≤

k
X

P1 (ŷj = g).

g=2

For each g ≥ 2, we have


P1 (ŷj = g) ≤ P1 
=

≤



Y Y

(i)

(πgh )I{Xij =h} >

Y Y

(i)

(π1h )I{Xij =h} 

i∈[m] h∈[k]

i∈[m] h∈[k]

I{Xij =h}



(i)
 Y Y  πgh 
P1 
(i)
π1h
i∈[m] h∈[k]






> 1

tI{Xij =h}
(i)
π
 gh 
E1
min
(i)
t≥0
π1h
h∈[k]
i∈[m]
Y

= min
t≥0

Y



(14)

Y X  (i) 1−t  (i) t
πgh ,
π1h

i∈[m] h∈[k]

where (14) is due to Markov’s inequality for each t ≥ 0. Therefore, we have
P1 (ŷj 6= 1) ≤
which leads to
1 X
n

j∈[n]

k
X
g=2




exp (−mC (π1∗ , πg∗ )) ≤ (k − 1) exp −m min C(π1∗ , πg∗ ) ,
g6=1

Pyj (ŷj 6= yj ) ≤ (k − 1) exp (−mI(π)) = exp (−(1 + o(1))mI(π)) ,

when log k = o(mI(π)).
9

Lower Bound.
tion. Define

Now we establish a matching lower bound. We first introduce some nota(i) (i)
Bt (πg∗ , πh∗ )

k 

 
X
(i) t
(i) 1−t
=
πhl .
πgl
l=1

Without loss of generality, we let

C(π1∗ , π2∗ ) = min C(πg∗ , πh∗ ) = I(π).
g6=h

Using the fact that the supremum over [k]n is bigger than the average over [k]n , the minimax
rate M can be lower bounded as
1 X
sup Eπ,y L(ŷ, y) ≥
Eπ,y L(ŷ, y)
kn
y∈[k]n
n
y∈[k]
k

=
≥

n

1 XX
Pl {ŷj 6= l}
kn
l=1 j=1

n 
1
2 X 1
P1 {ŷj 6= 1} + P2 {ŷj 6= 2} .
kn
2
2

(15)

j=1

Taking an infimum of ŷ on both sides leads to


n
1
1
2 X
inf P1 {ŷj = 2} + P2 {ŷj = 1} .
inf sup Eπ,y L(ŷ, y) ≥
ŷj
ŷ y∈[k]n
kn
2
2

(16)

j=1

By the Neyman-Pearson Lemma [14], the Bayes testing error 12 P1 {ŷj = 2} + 12 P2 {ŷj = 1} is
minimized by the likelihood ratio test
ŷj = arg max

g∈{1,2}

Y Y 

i∈[m] h∈[k]


(i) I{Xij =h}

πgh

.

Therefore,


P1 (ŷj = 2) = P1 

Y Y

i∈[m] h∈[k]

where Sm =

P

i∈[m] Wi ,

(i)
π2h
(i)
π1h

!I{Xij =h}



> 1 = P(Sm > 0),

with the random variable Wi defined as
(i)

P Wi = t log

π2h

(i)
π1h

10

!!

(i)

= π1h .

(17)

Here t is a positive constant that we will specify later. We lower bound P(Sm > 0) by
X Y
X Y
P(Wi ) ≥
P(Wi )
0<Sm <L i∈[m]

0<Sm i∈[m]

Y Bt (π (i) , π (i) )
1∗
2∗
=
Wi
(i) (i)
e
B
(π
,
π
)
0<Sm <L i∈[m] t 1∗
2∗ i∈[m]
Y
X
(i)
(i) −L
≥
Bt (π1∗ , π2∗ )e
Qi (Wi )
X

Y

P(Wi )eWi

0<Sm <L

i∈[m]

≥

Y

(i)
(i)
Bt (π1∗ , π2∗ )e−L Q(0

< Sm < L),

i∈[m]

where the distribution Qi is defined as
Qi

Wi = t log

(i)
π2h
(i)
π1h

!!

=


 

(i) 1−t
(i) t
π1h
π2h
(i)

(i)

Bt (π1∗ , π2∗ )

,

(18)

and Q is defined as the joint distribution of Q1 , · · · , Qm . To precede, we will need the
following two lemmas.
Lemma 6.1. If Aα is not empty, there is an unique t0 such that
Y
(i)
(i)
Bt (π1∗ , π2∗ ).
t0 = argmin

(19)

t∈[0,1] i∈[m]

Moreover, we have 0 < t0 < 1.
Lemma 6.2. Let t = t0 defined in (19). Then under the assumption of Theorem 3.1, Sm is
a zero mean random variable satisfying the central limit theorem, i.e. for any x,
!
Sm
≤ x → Φ(x), as m → ∞,
Q p
Var(Sm )
where Φ is the cumulative distribution function of a N (0, 1) random variable.

The proof of Lemma 6.1 and Lemma 6.2 are deferred to Section 6.5. Let t = t0 and
p
L = 2 VarQ (Sm ). Using Lemma 6.2 and Chebyshev’s inequality, we have
Q(0 < Sm < L) ≥ 1 − Q(Sm ≤ 0) − Q(Sm ≥ L) ≥ 1 − 5/8 − 1/4 = 1/8

for sufficiently large m. Note that
(i)

EQ Wi2 =

X

t log

h∈[k]

π2h

(i)

π1h

(i)

≤ max t log
i,h

π2h

(i)

π1h

!!2
!!2

≤ log2 ρm .
11

(i)

Qi

Wi = t log

π2h

(i)

π1h

!!
(i)

X

h∈[k]

Qi

Wi = t log

π2h

(i)

π1h

!!

Consequently,
VarQ (Sm ) =

X

i∈[m]

VarQ (Wi ) ≤

X

i∈[m]

EQ Wi2 ≤ m log2 ρm .

√
2
Under the assumption that log2 ρm = o(mI 2 (π)), we have e−L ≥ e− m log ρm ≥ e−o(mI(π)) .
This leads to the lower bound
Y
(i)
(i)
P1 (ŷj = 2) ≥
Bt (π1∗ , π2∗ )e−o(mI(π)) = exp (−(1 + o(1))mI(π)) .
i∈[m]

Note that the same bound holds for P2 (ŷj = 1). Hence,
inf sup EL(ŷ, y) ≥
ŷ y∈[k]n

2
exp (−(1 + o(1))mI(π)) = exp (−(1 + o(1))mI(π)) ,
k

under the assumption that log k = o (mI(π)). This completes the proof.

6.2

Proof of Corollary 3.1

Proof. Under the assumption that mI(π) → ∞, the upper bound is a special case of Theorem
3.1. Note that
m


1 X
log p1−t
(1 − pi )t + p1−t
(1 − pi )t
I(π) = − min
i
i
0≤t≤1 m
i=1

m

 p
1 X
= −
log 2 pi (1 − pi )
m
i=1

= I(p).

We focus on the proof of the lower bound, which involves weaker assumptions than that of
Theorem 3.1. Using a similar analysis as (15)-(16), we have


n
1
1
1X
inf P1 {ŷj = 2} + P2 {ŷj = 1} .
inf sup EL(ŷ, y) ≥
ŷj
ŷ y∈{1,2}n
n
2
2
j=1

Following the proof of Theorem 3.1 with the confusion matrix π (i) replaced by (5), we have


1
1
inf P1 {ŷj = 2} + P2 {ŷj = 1} ≥ exp (−mI(p)) e−L Q(0 < Sm < L),
ŷj
2
2
P
where Sm = i∈[m] Wi , and under the distribution Q,




1 − pi
pi
1
1
1
= Qi Wi = log
= .
Qi Wi = log
2
pi
2
1 − pi
2
p
Therefore, Sm has a symmetric distribution around 0. Letting L = 2 VarQ (Sm ), we have
Q(0 < Sm < L) ≥

1 VarQ (Sm )
1
1
− Q(Sm ≥ L) ≥ −
≥ .
2
2
L2
4
12

Finally, we need to show that L = o(mI(p)). We claim that

m 
m
X
1X
1 − pi 2
VarQ Wi =
log
4
pi
i=1

i=1

≤ −8 max (| log(pi )| ∨ | log(1 − pi )| ∨ 2)
1≤i≤m

This is becase when pi ∈ [1/16, 15/16], we have log

1−pi
pi

2

m
X
i=1

 p

log 2 pi (1 − pi ) .

≤ 6(2pi −1)2 ≤ −6 log (4pi (1 − pi )).

i
i
When pi ∈ (0, 1/16)∪(15/16, 1), log 1−p
≤ −2 log (4pi (1 − pi )) and log 1−p
≤ 2| log(pi )|∨
pi
pi
2| log(1 − pi )|. Therefore, under the assumption that

max (| log(pi )| ∨ | log(1 − pi )|) = o(mI(p)),

1≤i≤m

L = o(mI(p)) holds, and the proof is complete.

6.3

Proof of Theorem 4.1

Proof. Define
E=




max
 g∈[k]

X

i∈[m]

(i)

(i)

max log π̂gh − log πgh ≤ δ
h∈[k]




.



Then, we have




X
X
1
1
I{ŷj 6= yj } > ǫ ≤ P 
I{ŷj =
6 yj } > ǫ, E  + P(E c )
P
n
n
j
j


X
1
= P
I{ŷj =
6 yj } > ǫ E  P(E) + P(E c )
n
j

≤

=

1X
P (ŷj =
6 yj |E) P(E)/ǫ + P(E c )
n
j
1X
P (ŷj =
6 yj , E) /ǫ + P(E c ).
n
j

Let us give a bound for P (ŷj 6= yj , E). Without loss of generality, let yj = 1. Then,
P (ŷj 6= yj , E) ≤

k
X

≤

k
X

=

k
X

P (ŷj = g, E)

g=2









I{Xij =h}
(i)
Y
Y
π̂

 gh 
P
(i)
π̂1h
g=2
i∈[m] h∈[k]




> 1, E 

I{Xij =h}
I{Xij =h}

(i)
(i) (i)
Y
Y
Y
Y
π
π
π̂

 gh 
 gh 1h 
P
(i)
(i) (i)
π1h
πgh π̂1h
g=2
i∈[m] h∈[k]
i∈[m] h∈[k]
13




> 1, E  .

On the event E,

I{Xij =h} 



(i) (i)
(i)
(i)
Y
Y
X
X
π
π̂
π̂
π̂


 gh 1h 
log gh − log 1h  I{Xij = h} ≤ 2δ.
log 
≤
(i) (i)
(i)
(i)
πgh π̂1h
πgh
π1h
i∈[m] h∈[k]
i∈[m] h∈[k]

Then





I{Xij =h}

(i)
πgh
 2δ


P e
(i)
π
g=2
i∈[m] h∈[k]
1h

P (ŷj 6= yj , E) ≤

k
X

≤

k
X
g=2

Y Y

e2δ min

0≤t≤1




> 1

Y X  (i) 1−t  (i) t
πgh
π1h

i∈[m] h∈[k]


≤ (k − 1) exp −m min C(π1∗ , πg∗ ) + 2δ .
Thus,



g6=1

1 X
P (ŷj 6= yj , E) ≤ (k − 1) exp (−mI(π) + 2δ) .
n
j∈[n]

p
Letting ǫ = (k − 1) exp (−(1 − η)mI(π) + 2δ) with η = 1/ mI(π), we have

 p
1X
P (ŷj 6= yj , E) /ǫ ≤ exp − mI(π) .
n
j

Thus, the proof is complete under the assumption that log k + δ = o(mI(π)) and P(E c ) =
o(1).

6.4

Proof of Theorem 5.1

P
Proof. The risk is n1 nj=1 P{ŷj 6= yj }. Consider the random variable I{ŷj 6= yj }. It has the
P
same distribution as I{ m
i=1 (Ti − 1/2) > 0}, where Ti ∼ Bernoulli(1 − pi ). Therefore,
)
(m
n
X
1X
(Ti − 1/2) > 0 .
P{ŷj 6= yj } = P
n
i=1

j=1

We first derive the upper bound. Using Chernoff’s method, we have
!
)
(m
m
m
i
h
X
Y
X
λ/2
−λ/2
λ(Ti −1/2)
.
log (1 − pi )e
+ pi e
Ee
= exp
(Ti − 1/2) > 0 ≤
P
i=1

i=1

i=1

The desired upper bound follows by letting t = e−λ/2 and optimizing over t ∈ (0, 1].

14

Now we show the lower bound using the similar arguments as in the proof of Theorem
P
3.1. Define Wi = λ(Ti − 1/2) and Sm = m
i=1 Wi . Then, we have
)
(m
X
(Ti − 1/2) > 0
= P {Sm > 0}
P
i=1

X

≥

m
Y

P(Wi )

0<Sm <L i=1
m
Y
X

=

0<Sm <L
m 
Y

≥

i=1

m
Y
(1 − pi )eλ/2 + pi e−λ/2
P(Wi )eWi
eWi
(1 − pi )eλ/2 + pi e−λ/2 i=1
i=1

!


(1 − pi )eλ/2 + pi e−λ/2 e−L Q {0 < Sm < L} .

Note that under Q, Wi has distribution
Qi (Wi = λ/2) =
Qi (Wi = −λ/2) =

(1 − pi )eλ/2
,
(1 − pi )eλ/2 + pi e−λ/2
pi e−λ/2
.
(1 − pi )eλ/2 + pi e−λ/2


Q
λ/2 + p e−λ/2 . This leads to the
We choose λ0 ∈ [0, ∞) to minimize f (λ) = m
i
i=1 (1 − pi )e
equation EQ Sm = 0. It is sufficient to lower bound e−L Q {0 < Sm < L} to finish the proof.
To do this, we need the following result.
P
Lemma 6.3. Suppose pi ≤ 1 − ρm for all i ∈ [m] and ρ2m i∈[m] pi (1 − pi ) → ∞ as m → ∞.
Then we have
i) λ0 ≤ −2 log ρm .
ii) √

Sm

VarQ (Sm )

N (0, 1) under the distribution Q.

p
The proof of Lemma 6.3 will be given in Section 6.5. Let L = 2 VarQ (Sm ), and we have
√
e−L Q(0 < Sm < L) ≥ 0.25e−2 VarQ (Sm ) .

Finally, we need to show
Var(Sm ) ≤

p

VarQ (Sm ) = o(mJ(p)). This is because

m
X
i=1

EQ Wi2 ≤ mλ20 /4 ≤ m log2 ρm = o(m2 J(p)2 ),

√
where the last equality is implied by the assumption | log ρm | = o( mJ(p)). The proof is
complete.

15

6.5

Proof of Technical Lemmas

Pm
(i)
(i)
′
Proof of Lemma 6.1. Let f (t) =
i=1 log Bt (π1∗ , π2∗ ). Then we have f (t0 ) = 0 by its
definition. First, we are going to prove 0 < t0 < 1. The concavity of logarithm gives us
xt y 1−t ≤ tx + (1 − t)y for non-negative x, y and t ∈ [0, 1], which implies
!
k 

X
X
X
(i)
(i)
(i) (i)
= 0.
(1 − t)π1h + tπ2h
f (t) =
log Bt (π1∗ , π2∗ ) ≤
log
i∈[m]

h=1

i∈[m]

(i)

(i)

For t ∈ (0, 1), the equality holds if and only if π1h = π2h for all h ∈ [k] and i ∈ [m]. As there
is at least one non-spammer, we must have f (t) < 0 = f (0) = f (1) for t ∈ (0, 1). Hence the
minimizer t0 ∈ (0, 1).
Now we are going to show the uniqueness of t0 by proving that
f ′′ (t) = Var(Sm ) > 0, ∀t ∈ (0, 1)


P

(i)

π2h



where Sm =
and
i∈[m] Wi . To simplify the notation, let us define wih = t log π (i)
1h
t
1−t 

P
(i)
(i)
π2h for all i ∈ [m] and h ∈ [k]. Now Qi (Wi = wih ) = pih / h pih and
pih = π1h
P
(i) (i)
d
Bt (π1∗ , π2∗ ) = h∈[k] pih . Notice that dt
pih = pih wih , we have
X
X P pih wih
d
h
P
=
EWi = ESm ,
(20)
f (t) =
dt
h pih
i∈[m]

i∈[m]

and

X P pih w2 P pih − (P pih wih )2
X
d2
h
h
h
ih
f
(t)
=
=
Var(Wi ) = Var(Sm ).
P
dt2
( h pih )2
i∈[m]

(21)

i∈[m]

Since the set Aα is non-empty, there is at least one Var(Wi ) > 0. Thus, f ′′ (t) = Var(Sm ) >
0.
Proof of Lemma 6.2. From (20), we know ESm = f ′ (t0 ) = 0. Since t0 > 0 by lemma 6.1, we
p
can rescale Wi by Wi /(−t0 log ρm ) and the value of Sm / Var(Sm ) will not change. Let us
P
define Vi = Wi /(−t0 log ρm ) and Rm = m
i=1 Vi . Then we have |Vi | ≤ 1. To prove a central
limit theorem of Sm , it is sufficient to check the following Lindeberg’s condition [9], that is,
for any ǫ > 0,
m
X

1
E (Vi − EVi )2 I{(Vi − EVi )2 ≥ ǫ2 Var(Rm )} → 0 as m → ∞.
Var(Rm )

(22)

i=1

Note that for a discrete random variable X who takes value xa with probability pa for a ∈ [N ],
!2
!
!
X
X
X
X
2
=
p a xa
pa pb (xa − xb )2 .
p a xa −
pa
Var(X) =
a

a

a

16

a,b

Then, for any i ∈ Aα , we have
Var(Vi ) =

1
log2 ρm
1

≥

log2 ρm

≥

2

≥
≥

1


 

(i) (i) t
(i) (i) 1−t
π2a π2b
X π1a π1b
(i)

a,b

(i)

Bt2 (π1∗ , π2∗ )

(i) (i)

log


 

(i) (i) 1−t
(i) (i) t
π12 π11
π22 π21 log2

2

π2a π1b

(i) (i)

π1a π2b
!
(i) (i)
π22 π11

!

(i) (i)

π12 π21

1−t 
t

(i) (i)
(i) (i)
π12 π11
π22 π21 log2 (1 + α)2

log ρm
ρ2m
4 log2 (1 + α)
log2 ρm
ρ2m
min{α2 , 1}.
log2 ρm

(i)

(i)

Here the second inequality is due to the assumption that for any i ∈ A, πaa ≥ πab (1 + α) for
(i)
any b 6= a. We have used the assumption that πab ≥ ρm for the third inequality. The last
inequality is because log(1 + α) ≥ α/(1 + α) ≥ min{α/2, 1/2} for positive α. Take a sum of
Var(Vi ) over i ∈ Aα ,
Var(Rm ) =

X

i∈[m]

Var(Vi ) ≥ |Aα |

ρ2
ρ2m
min{α2 , 1} ≥ cm 2m min{α2 , 1},
2
log ρm
log ρm

for some constant c ∈ (0, 1). Since (Vi − EVi )2 ≤ 2Vi2 + 2(EVi )2 ≤ 4, we will have
I{(Vi − EVi )2 ≥ ǫ2 Var(Rm )} = 0
when 4 log2 ρm < ǫ2 |Aα |ρ2m min{α2 , 1}. Notice that E(Vi −EVi )2 ≤ 4, we apply the Dominated
Convergence Theorem to conclude

E (Vi − EVi )2 I{(Vi − EVi )2 ≥ ǫ2 Var(Rm )} → 0.

Thus, the Lindeberg condition holds when | log ρm | = o(ρm |A0.01 |1/2 ).

Proof of Lemma 6.3. We are first going to show λ0 ≤ −2 log ρm . Recall that
f (λ) =

m 

Y
(1 − pi )eλ/2 + pi e−λ/2 .
i=1

Qm
For all λ ≥ −2 log ρm , we have f (λ) > ρ−m
m
i=1 (1 − pi ) ≥ 1, and f (0) = 1. Thus, the
minimizer of f (λ) must be in the interval (0, −2 log ρm ].
Again, we are going to prove the central limit theorem of Sm by checking the following
Lindeberg’s condition. For any ǫ > 0,



m
q
X
1
2
EQ (Wi − EQ Wi ) I |Wi − EQ Wi | > ǫ VarQ (Sm )
=0
(23)
lim
m→∞ VarQ (Sm )
i=1

17

When λ0 ∈ (0, −2 log ρm ], a lower bound of VarQ (Wi ) is given by
VarQ (Wi ) = λ20

pi (1 − pi )

)eλ0 /2

2
e−λ0 /2

≥ λ20 e−λ pi (1 − pi ) ≥ λ20 ρ2m pi (1 − pi )

(1 − pi
+ pi
P
P
2 2
Therefore, VarQ (Sm ) = m
i∈[m] pi (1 − pi ). Notice that |Wi − EQ Wi | ≤
i=1 VarQ (Wi ) ≥ λ0 ρm
|Wi | + E|Wi | = λ, for any fixed ǫ > 0, we will have


q
I |Wi − EQ Wi | > ǫ VarQ (Sm ) = 0
P
when ρ2m i∈[m] pi (1 − pi ) → ∞ as m → ∞. Since VarQ (Wi )/λ20 ≤ 1/4, the Dominated
Convergence Theorem implies the desired Lindeberg’s condition (23).

References
[1] Amazon Mechanical Turk. https://www.mturk.com/mturk.
[2] Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade, and Matus Telgarsky.
Tensor decompositions for learning latent variable models. The Journal of Machine
Learning Research, 15(1):2773–2832, 2014.
[3] Yoram Bachrach, Thore Graepel, Tom Minka, and John Guiver. How to grade a test
without knowing the answers — a Bayesian graphical model for adaptive crowdsourcing
and aptitude testing. In Proceedings of the 29th International Conference on Machine
Learning (ICML-12), pages 1183–1190, 2012.
[4] Daniel Berend and Aryeh Kontorovich. A finite sample analysis of the naive bayes
classifier. Journal of Machine Learning Research, 16:1519–1545, 2015.
[5] Thomas M Cover and Joy A Thomas. Elements of information theory. John Wiley &
Sons, 2006.
[6] N. Dalvi, A. Dasgupta, R. Kumar, and V. Rastogi. Aggregating crowdsourced binary
ratings. In Proceedings of the 22nd international conference on World Wide Web, pages
1220–1229, 2013.
[7] A. P. Dawid and A. M. Skene. Maximum likeihood estimation of observer error-rates
using the EM algorithm. Journal of the Royal Statistical Society, 28(1):20–28, 1979.
[8] A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete
data via the EM algorithm. Journal of the Royal Statistical Society, 39(1):1–38, 1977.
[9] Rick Durrett. Probability: theory and examples. Cambridge university press, 2010.
[10] Chao Gao and Dengyong Zhou. Minimax optimal convergence rates for estimating
ground truth from crowdsourced labels. arXiv preprint arXiv:1310.5764, 2013.
18

[11] Arpita Ghosh, Satyen Kale, and Preston McAfee. Who moderates the moderators?
Crowdsourcing abuse detection in user-generated content. In Proceedings of the 12th
ACM conference on Electronic commerce, pages 167–176, 2011.
[12] David R Karger, Sewoong Oh, and Devavrat Shah. Budget-optimal task allocation for
reliable crowdsourcing systems. Operations Research, 62(1):1–24, 2014.
[13] Q. Liu, J. Peng, and A. Ihler. Variational inference for crowdsourcing. In Advances in
Neural Information Processing Systems 25, pages 701–709, 2012.
[14] J Neyman and ES Pearson. On the problem of the most efficient tests of statistical
hypotheses. Philosophical Transactions of the Royal Society of London A: Mathematical,
Physical and Engineering Sciences, 231(694-706):289–337, 1933.
[15] Fabio Parisi, Francesco Strino, Boaz Nadler, and Yuval Kluger. Ranking and combining multiple predictors without labeled data. Proceedings of the National Academy of
Sciences, 111(4):1253–1258, 2014.
[16] V. C. Raykar, S. Yu, L. H. Zhao, G. H. Valadez, C. Florin, L. Bogoni, and L. Moy.
Learning from crowds. Journal of Machine Learning Research, 11:1297–1322, 2010.
[17] Tian Tian and Jun Zhu. Max-margin majority voting for learning from crowds. In
Advances in Neural Information Processing Systems 28, pages 1612–1620, 2015.
[18] Aad W Van der Vaart. Asymptotic statistics. Cambridge university press, 2000.
[19] Matteo Venanzi, John Guiver, Gabriella Kazai, Pushmeet Kohli, and Milad Shokouhi.
Community-based Bayesian aggregation models for crowdsourcing. In Proceedings of the
23rd international conference on World wide web, pages 155–164, 2014.
[20] Peter Welinder, Steve Branson, Pietro Perona, and Serge J. Belongie. The multidimensional wisdom of crowds. In Advances in Neural Information Processing Systems 23,
pages 2424–2432, 2010.
[21] J. Whitehill, P. Ruvolo, T. Wu, J. Bergsma, and J. Movellan. Whose vote should count
more: optimal integration of labels from labelers of unknown expertise. In Advances in
Neural Information Processing Systems 22, pages 2035–2043, 2009.
[22] Yuchen Zhang, Xi Chen, Dengyong Zhou, and Michael I Jordan. Spectral methods meet
em: A provably optimal algorithm for crowdsourcing. In Advances in neural information
processing systems, pages 1260–1268, 2014.
[23] D. Zhou, J. C. Platt, S. Basu, and Y. Mao. Learning from the wisdom of crowds by
minimax entropy. In Advances in Neural Information Processing Systems 25, pages
2204–2212, 2012.

19

[24] Dengyong Zhou, Qiang Liu, John Platt, and Christopher Meek. Aggregating ordinal
labels from crowds by minimax conditional entropy. In Proceedings of the 31st International Conference on Machine Learning (ICML-14), pages 262–270, 2014.

20

