Performance as a Constraint: An Improved Wisdom of Crowds Using Performance Regularization

1 Introduction

In spite of the recent significant advances in artificial intelligence technologies, it is still difficult for machines to solve open-world and knowledge-intensive problems. Human computation [Law and Ahn, 2011] is a promising idea of combining human intelligence and machine intelligence to solve such "AI-hard" problems. On the other hand, the recent rise of crowdsourcing allows one to recruit human labor that can be scaled in an on-demand manner. This not only has such a quantitative advantage but also has a qualitative advantage, that is, the crowds often include experts who know correct solutions to the problems at hand. Consequently, crowdsourcing is often regarded as a favorable execution platform for human computation. However, despite such huge merits, there are still several challenges in the effective use of crowdsourcing. One of the typical problems is the quality control of

∗Contact Author

Performance as a Constraint:

An Improved Wisdom of Crowds Using Performance Regularization

Jiyi Li1∗ , Yasushi Kawase2 , Yukino Baba3 and Hisashi Kashima4

1University of Yamanashi

2Tokyo Institute of Technology 3University of Tsukuba

4Kyoto University

jyli@yamanashi.ac.jp, kawase.y.ab@m.titech.ac.jp, baba@cs.tsukuba.ac.jp, kashima@i.kyoto-u.ac.jp

Q: Which of the following drugs is most likely to cause Cushing's syndrome with long-term use? (a) Heparin, (b) Insulin, (c) Theophylline, (d) Prednisolone

Figure 1: An example of heterogeneous multiple-choice questions.

crowd work. Because there is huge variability in the diligence and ability of crowd workers, the quality of crowdsourcing results also has a huge variance. There are at least two typical approaches to the quality control problem: one is the unsupervised approach and the other is the supervised approach. The unsupervised approach is based on the statistical inference of latent true answers. One of the typical methods is majority voting. More sophisticated statistical models that consider worker ability and task difficulty have also been proposed (e.g., Dawid and Skene (1979), Karger et al. (2011), Zhou et al. (2012), Venanzi et al. (2014), Whitehill et al. (2009), Welinder et al. (2010), Wauthier and Jordan (2011), Bachrach et al. (2012), Ma et al. (2015), Zhou and He (2016), and Yin et al. (2017)).

However, because most of the unsupervised aggregation methods basically enhance the majority opinions (and the workers who provided them), their performance is limited in difficult cases where majority voting fails [Li et al., 2017]. Figure 1 shows a difficult multiple-choice question requiring professional medical knowledge. Among the four candidate answers, the correct one is '(d) Prednisolone'. However, '(b) insulin' is probably the most familiar medical term for nonexperts, and therefore, incapable workers are likely to choose it, which sometimes results in the wrong answer winning in the majority voting. This is the so-called availability heuristic by which people tend to choose answers that are easier to recall [Baker et al., 2004]. A simple remedy for the difficult aggregation problem is the supervised approach that estimates worker performance more directly. It typically uses qualification questions whose true answers are known to the requester, but unknown to the workers. The estimated performance allows us to give large importance weights to the expert workers or screen out incapable workers. Instead of qualification questions, the performance on past tasks the workers engaged in is sometimes available.

In this paper, we propose a hybrid approach that we call performance constraint that combines the supervised and unsupervised approaches in a novel manner. Our approach does not involve the typical usages of worker performance such as the use as the seeds or local constraints for the answers in semi-supervised aggregation methods. Instead, we solve a constraint satisfaction problem to find answers that are consistent with given worker performance. In other words, we use worker performance as a global constraint for inferring the true answer. Our theoretical analysis guarantees that we can find true answers with high probability if we have a sufficient number of workers even when used by itself.

We demonstrate the idea of our approach using an example. Assume that we have three heterogeneous multiple-choice questions and obtain the answers shown in Figure 2. The ground truth answers to the three questions are A, C, and E, respectively. Like the previous example (Figure 1), the majority voting fails and results in wrong answers B, D, and F that are more popular than the correct answers. What if we know the exact performance of each worker? Even in this case, since the performance of all the workers are equally 1/3, the answers of all workers should be considered equally important, and therefore the performance-weighted majority voting still results in the wrong answers. However, if we change the way in which we exploit the worker performance, it is possible to estimate the correct answers. Instead of using the performance information as the reliability of the workers, we use it as a constraint on the ratio of correct answers of each worker. In the present example, assuming that the correct answer to question 1 is B, workers 2 and 3 are correct on this question, and worker 1 is not. Considering the constraint that the performance of all workers is 1/3, workers 2 and 3 cannot make any more correct answers, and therefore none of C, D, E, F can be correct answers for the other questions; this is a contradiction for worker 1. Similarly, we can exclude D and F from the answers of questions 2 and 3, respectively, and obtain the correct answers, A, C, and E. Note that if we set the ground truth answers as B, D, and F, although majority voting succeeds; our method can also give the correct answers; our method has higher capacity than majority voting.

In practice, the constraints cannot always uniquely identify the correct answers, or the worker performance is known only approximately. We relax the above constraint satisfaction problem as an optimization problem to minimize the discrepancy between the performance on the estimated answers and the performance constraint. As well as standard divergence measures such as the Euclidean distance and KL divergence, we also propose a ranking-based relaxation.

In addition to using the performance information as a constraint for aggregation, we also propose to use it as a regularizer for existing the statistical aggregation methods, which we call performance regularization. Because the performance constraint itself is independent of the underlying probabilistic generative models of worker answers, we use it in combination with such models to boost their performance.

The experimental results show the proposed method is quite powerful when we know the exact worker performance. The aggregation accuracy degrades when the performance estimates are not accurate, but the ranking-based constraint relaxation alleviates the weakness. In addition, when combined with existing statistical aggregation methods, the performance regularizer consistently boosts the performance.

2 Problem Setting

We address a problem of aggregating answers provided by crowd workers for rather difficult questions. In contrast to the standard unsupervised aggregation setting, we additionally suppose that we know the performance of each worker.

Assume that we have M questions, each of which is a heterogeneous K-choice question that has its own K potential answers (e.g., the medical knowledge question in Figure 2). For simplicity, we assume that K is the same for all questions, but this is not a requirement. We ask the questions to N workers, and obtain a set of responses {rij}i,j, where rij is the response of worker i to question j. For notational simplicity, we assume that all workers answer all questions, but this assumption is not necessarily required. Here, rij is represented as a K-dimensional one-hot vector only one of whose elements is 1, that is, rij = (0, . . . , 0, 1, 0, . . . , 0)⊤ ∈ {0, 1}K. The goal is to estimate the ground truths {gj}j, where gj is the estimated ground truth for question j and denoted by a K-dimensional one-hot encoded binary vector, that is, gj = (0, . . . , 0, 1, 0, . . . , 0)⊤ ∈ {0, 1}K. An important assumption we make in this paper is that we somehow know the performance pi of worker i; in other words, pi is the ratio of correct answers by worker i.

In summary, the aggregation problem with worker performance takes the input as {rij}i,j , the set of worker responses, and {pi}i, the performance levels of the workers, and the outputs are the estimated ground truths {gj}j .

One might be afraid that it is a too strong assumption that we know the worker performance; however, it is often the case that we can know (or at least guess) the worker performance based on the past tasks the worker has accomplished or the answers to qualification questions.

3 Performance Constraint

3.1 Worker Performance as a Constraint

In crowdsourcing, we often use qualification questions to test if the workers have sufficient capacity to execute the given tasks. Unlike that in the case of the main tasks, the requester knows the true answers for the qualification questions. They are given to workers before they start the main tasks, or are just mixed in with the main tasks in an indistinguishable way.

The requester can evaluate the worker ability using the qualification questions. The qualification questions can also be used in statistical aggregation methods in a semi-supervised manner. Most of the existing aggregation models are unsupervised and usually estimate the true answers as latent variables; however, they can easily incorporate the qualification questions by fixing their latent answers to their true answers.

In this paper, we consider a totally different way to exploit the results of the qualifications questions, that is, to use the performance on the qualification questions as a global constraint for aggregation. More precisely, suppose that the performance (i.e., accuracy) of worker i on the qualification questions is pi, we force the performance (i.e., the ratio of correct answers) on the other (main) questions also to be pi. Our idea is represented as a constraint satisfaction problem to find {gj}j that satisfies the constraint

where I is the indicator function. Note that I(rij = gj) can also be written as I(rij = gj) = r⊤ ij gj .

3.2 Theoretical Justification

We gave an intuitive explanation of how the performance constraint helps aggregation, but it is still not theoretically clear if the performance constraint is generally capable of finding the ground truth answers. The following theorem guarantees that we can obtain the ground truth answers with high probability if we have a sufficient number of workers. For simplicity, we consider a simple case where K = 2 and each worker i gives the ground truth answers for piM questions independently and uniformly at random (i.e., ( M piM) possibilities occur with the same probability). We assume pi ̸= 1/2 for some i, because otherwise the all-wrong answers (g† j )j (i.e., g† j ̸= g∗ j for all question j) always satisfy the constraint (1).

Theorem1. If p1 ̸= 1/2 andN >MlnM, then the ground truth answers are uniquely determined by the performance constraint (1) with high probability.

Proof. Without loss of generality, we assume that pi ̸∈ {0, 1} for all i, because if pi ∈ {0, 1}, the ground truth answers are determined by the answers of worker i.

For s = 1, . . . ,N, consider an integer linear system:

Then, (1) has a unique solution if and only if IP(N) has a unique solution. Indeed, if (ˆ gj)j is a solution of (1), then

is a solution of IP(N), and vice versa. In particular, the allone vector of length M (which corresponds to the ground truth answers) is always a solution of IP(s) for any s.

If rank(a⊤1 , . . . , a⊤s ) = M (i.e., full rank), then the solution of IP(s) is uniquely determined. Suppose that the solution of IP(s) is not uniquely determined and let ρ = rank(a⊤1 , . . . , a⊤s ) (< M). Then, for any s′ > s, we have a⊤s′ ̸∈ span{a⊤1 , . . . , a⊤s } with probability at least (i) (M- ρ - 1)/M if ρ < M- 1, and (ii) 1/M if ρ = M- 1 (see supplementary material for proof). Note that a⊤s′ ̸∈ span{a⊤1 , . . . , a⊤s } implies rank(a⊤1 , . . . , a⊤s′) > ρ. Hence, by the standard analysis of the coupon collector's problem, IP(N) has a uniquely solution with high probability (see, e.g., Motwani and Raghavan [1995]).

A detailed proof can be found in the appendix.

4 Relaxation and Performance Regularization 4.1 Distance-based Constraint Relaxation

In practice, there might be neither an exact solution nor a unique solution satisfying Eq. (1), so we relax the ground truth vector; let gj ∈ [0, 1]K be a K-dimensional vector in a simplex such that gj ≥ 0 and |gj|1 = 1. We obtain a relaxed optimization problem as

subject to gj ≥ 0 and |gj |1 = 1, where d is a distance function between two probability values. The choice of d is arbitrary; for example, we can choose the Euclidean distance

or the KL-divergence, which also seems a reasonable choice:

4.2 Ranking-based Constraint Relaxation

Obviously, the worker accuracy is not exactly the same between the qualification questions and the main questions, and therefore, there is a risk that the performance constraint becomes harmful when the performance estimate is wrong. Our solution is that, instead of using the constraint based on the distance, we relax the constraint by the relative order of worker accuracies. More precisely, if a worker i1 has higher accuracy than that of another worker i2 on the qualification questions, we impose the constraint that i1 has higher accuracy than i2 on the main questions. We implement this idea as another relaxed objective function instead of Eq. (2) as

The constant T > 0 controls how strict the constraint is.

All of the above choices are convex functions; hence, the optimal solutions are found by the simple gradient-based update, followed by the projection to the constraints gj ≥ 0 and |gj|1 = 1 (normalizing gj so as to be a probability vector). The computation cost of the rank-based constraint is higher than the distance-based constraints, but it does not give a significant impact on the scalability of the entire optimization.

4.3 Performance Regularization

The performance constraint itself is model agnostic; that is, it works independently of the underlying probabilistic generative models of worker answers. Now, we combine the constraint with the existing statistical methods; namely, we include the performance constraint as a regularization term.

For example, let us consider a simple generative model. Assume that the probability of worker i giving a correct answer is ai and that when a worker fails to give a correct answer, the worker chooses a wrong answer uniformly at random, namely,

The log-likelihood of the worker answers is given as

In practice, we apply the following re-parameterization to ensure the positiveness of ai:

By including the distance d in (2) as a regularization term, the overall objective function is given as

where λ > 0 is the regularization constant. Instead, we can use the ranking constraint term in Eq. (3) as the regularization term. We call this performance regularization.

Performance regularization is also applicable to more sophisticated generative models. For example, if we use GLAD [Whitehill et al., 2009] as the underlying model, we use the following re-parameterization instead of (5): ai = 1/ (1+ e-αidj ) , where dj denotes the easiness of task j. With the help of proper underlying models, the performance regularization method can incorporate both worker performance constraint and other types of useful factors for truth estimation such as task difficulty. The latent variables in the performance regularization term are only the estimated truth gj. Therefore, it is easy to include the performance regularization term in the objective function of an underlying model to iteratively estimate the truths and other potential factors such as worker expertise on each question. One example is to use the MINMAX [Zhou et al., 2012] approach as the underlying model. Note that, if the performance of only a subset of workers is known, we can use the performance constraint or regularization only for such workers.

5 Experiments

We investigate the following issues in the experiments: (1). How powerful is the performance constraint (PC) alone? (2). How robust is the performance constraint (PC) when we do not know the true worker performance? (3). Does the performance regularization (PR) improve aggregation results?

We use the six real datasets collected by Li et al. (2017), which consist of multiple-heterogeneous-answer questions on Chinese language, English language, Information technology (IT), Medicine, Pok´emon, and Science. They are relatively difficult questions in which the simple majority voting performs poorly (See the 'MV' column in Table 1.)

5.1 How Powerful is PCAlone?

The first question we investigate is whether the performance constraint is informative in guessing the ground truths. In this experiment, we assume that we somehow know the true worker accuracy. We test the performance constraint using two different divergence measures, i.e., the Euclid distance and the KL divergence, and the ranking-based constraint. We compare the proposed method with some baselines that are applicable to heterogeneous multiple-choice questions: (i) the simple majority voting (MV), (ii) the weighted majority voting (WMV) [Kuncheva and Rodr´ıguez, 2014] which is the solution that maximizes Eq. (4) with respect to {gj}j (with ai = pi), and (iii) several existing unsupervised aggregation methods (D&S [Dawid and Skene, 1979], GLAD [Whitehill et al., 2009], DARE [Bachrach et al., 2012], and the min-max entropy method (MINMAX) [Zhou et al., 2012]). The weighted majority voting method corresponds to the optimal and standard approach when we know the worker performance. We use the entire datasets in the experiments.

Table 1 shows the accuracy achieved by the performance constraint with two different distances (PC(EUC) and PC(KL)), the one with the ranking-based constraint (PC(RANK)), as well as the WMV and other existing unsupervised aggregation methods. Surprisingly, the distancebased constraint achieves almost perfect aggregation, in contrast with the inferior performance achieved by WMV, which is the standard usage of the performance information. The ranking-based constraint shows sub-optimal performance since it cannot exploit the full performance information, but it still significantly outperforms WMV. This shows that our method exploits the performance information very differently from the standard approaches. It is noteworthy that the proposed method even outperforms DARE, one of the most powerful unsupervised Bayesian aggregation methods, and MINMAX, a powerful minimax entropy method.

5.2 HowRobust is PCWhenWe Do Not Know True Worker Performance?

As discussed earlier, it is just an ideal case that we know the accurate worker performance; such assumption does not necessarily hold in practice, and hence all we can do is only to "guess" the worker performance from past work or qualification questions. In order to test the robustness to inaccurate estimates of worker performance, we add noise with the bias to the estimated worker accuracy parameters {pi}i and test the robustness against the noise. We add a noise generated by a Gaussian distribution N(η, σ2 ) with bias η of estimated worker performance to true worker performance as the mean and fit into [0, 1], and we use it as the performance estimate.

Figure 3 shows the results when we change η ∈ {-0.1, 0.1} and σ ∈ {0.05, 0.1}. We compare the performance constraint with the weighted majority voting (4). WMV is not quite sensitive to the inaccurate estimation of worker performance, but always not quite good. The performance of the proposed methods drops as the noise level increases. The general tendency of the performance degrade of each PC variation looks similar among different datasets. When the noise level is not very high (σ = 0.05), in most of the cases, the proposed methods (PC) keep their performance relatively high. Among the three variations, the ranking constraint (PC(RANK)) fights relatively better against the noise, while the other two (PC(EUC) and PC(KL)) suffer from the increasing noise. From these observations, the robustness to high-level noise in the performance estimate is one of the weaknesses of the proposed method; but the ranking-based constraint relaxation alleviates this problem for practical use.

5.3 Does PR Improve Aggregations?

Finally, we test our approach in a more realistic scenario, where we do not know the true worker performance and use several qualification questions to estimate it. Our primary interest here is to find out if the performance regularization improves the aggregation accuracy when combined with ordinary statistical aggregation methods. To test the hypothesis, we combine the proposed method ('PR') with the WMV, GLAD and MINMAX. In this experiment, a subset (25%) of the questions in each dataset is considered as a set of qualification questions; we estimate the worker performance using their ground truths. The others are used as a test set. We iterate the split and test ten times, and obtain the average aggregation accuracy. For tuning the hyper-parameter λ in the performance regularization, we utilize the idea of the KL cost annealing method [Bowman et al., 2016] to avoid running the optimization many times for the candidate hyper-parameters. We first gradually and linearly increase λ from zero during optimization until the perplexity on the test subset reaches zero. After that, we fix λ and optimize until convergence. The perplexity is defined as P({gk j }j,k) = ∑j ∑k -gk j log gk j , where gk j is the estimated value of g for question j and its k-th candidate answer. It only needs to run the optimization once, which speeds up the hyper-parameter tuning considerably. Note that we do not use the ground truth labels at all.

Table 2 summarizes the results. In contrast with the previous where we knew the exact performance of the workers, the overall accuracy of the performance constraint ('PC(alone)') degrades as implied by Figure 3. However, it is still comparable with WMV, the direct competitor, as well as the other methods such as MV, GLAD and MINMAX. Among the three choices of the performance constraint, the one with the ranking-based constraint performs the best, which is also consistent with the results of the previous experiment. When combined with the unsupervised aggregation methods, i.e., WMV, GLAD and MINMAX, the performance regularization ('+PR') consistently boosts the accuracy of its unsupervised analogue, especially with the ranking constraint.

The performance regularization exploits the qualification questions in a very different way than the semi-supervised methods; it does not rely on detailed worker labels for the qualification questions, while most of the semi-supervised approaches assume they are available. In practice, it is sometimes difficult to obtain the detailed worker labels in past tasks, for example, due to privacy reasons, even in the cases where we know the overall past performance of a worker.

6 RelatedWork

Majority voting is probably the simplest answer aggregation method. Since it assigns equal weights to all workers, the aggregation performance is not stable due to the wide variety of crowd workers in their ability and diligence; therefore researchers have studied more sophisticated statistical aggregation methods that allow diverse worker abilities and other uncertainties. Some approaches jointly estimate worker ability and true answers using the expectation-maximization (EM) algorithm [Dawid and Skene, 1979], bipartite models [Karger et al., 2011], the maximum entropy principle [Zhou et al., 2012], and Bayesian inference [Liu et al., 2012; Venanzi et al., 2014]. More sophisticated models that incorporate task difficulty [Whitehill et al., 2009], worker-task affinity [Welinder et al., 2010], and their Bayesian treatments [Wauthier and Jordan, 2011; Bachrach et al., 2012] have also been proposed. Unsupervised quality control is a quite active area, so we do not exhaustively enumerate all the work, but just to name a few, Zhou and He (2016), Yin et al. (2017), Kawase et al. (2019) are such examples. For truth discovery on the Web, Zheng et al. (2017) reviewed and compared various existing aggregation methods. Some of those methods are applicable to the heterogeneous multiple-choice questions.

Another practical and typical way of crowdsourcing quality control is to perform qualification tests [Downs et al.,

2010; Ipeirotis et al., 2010; Mortensen et al., 2013]. A qualification test is a set of questions whose ground truth answers are known only to the requester, and are performed before proceeding to the main tasks to appraise the workers or to filter out incapable workers. Instead of such pre-screening, qualification questions are also injected into the main tasks to perform post-screening. If the workers were engaged in previous tasks, their results and evaluations by past requesters are also considered as qualification results. Besides directly using the qualification results for pre- or post-worker screening, they are also used in semi-supervised aggregation as the seeds or local constraints for latent ground truths. Ipeirotis et al. (2010) implemented a variant of D&S [Dawid and Skene, 1979] by using injected qualification questions. Qualification tests are also used for targeting the expert workers [Downs et al., 2010]; however, it is not always guaranteed that well-designed qualification tests are available for requesters. Mortensen et al. (2013) utilized crowdsourcing for constructing biomedical ontologies and selected knowledgeable workers using qualification tests. Unlike the previous usages of qualification questions, we use them as a global constraint or a regularizer to infer the ground truths. Recently, although in a different context and with a different motivation, Whitehill (2019) discussed the possibility of guessing the ground truth labels from AUC values of machine learning classifiers, whose settings are somewhat similar to ours.

Most semi/un-supervised approaches strengthen the opinions of the majority workers, and therefore do not perform well in cases where the number of capable workers (i.e., experts) is smaller than that of incapable workers. There are a few studies addressing such few-expert scenarios. Li et al. (2014) used worker profiles such as demographic information to predict their abilities. Ma et al. (2015) focused on task information such as the words appearing in task descriptions, and combined a topic model and a worker ability model to characterize worker expertise. Kazai et al. (2012) used demographics information and personality traits. Ipeirotis and Gabrilovich (2014) used sponsored search associated with medical terms to guide medical experts to medical question tasks. Prelec et al. (2017) used the response for an additional question asking the answer distribution of other workers. Different from those approaches exploiting auxiliary information, Li et al. (2017) proposed a method not relying on side information by bundling questions into "hyper questions".

7 Conclusion

We addressed the crowd aggregation problem when we know the worker performance. Unlike the previous semisupervised approaches, we use worker performance as the constraint to infer ground truth labels. We also proposed performance regularization, which can be combined with ordinary aggregation methods. The experiments showed that the proposed method is quite powerful when we know the exact worker performance. The aggregation accuracy degrades when the performance estimates are not accurate, but the ranking-based constraint alleviates the weakness. When combined with statistical aggregation methods, the performance regularizer boosted the aggregation performance.

Acknowledgments

This work was partially supported by JSPS KAKENHI Grant Number 19K20277 and 15H01704.

A Proofs

Here, we provide omitted proofs from the proof of Theorem 1.

Claim 1. For any s′ > s and ρ < M- 1, we have a⊤s′ ̸∈ span{a⊤1 , . . . , a⊤s } with probability at least (M-ρ-1)/M.

Proof. We regard as′ a vector of random variables but a1, . . . , as are fixed. We define E as the event that a⊤s′ ̸∈ span{a⊤1 , . . . , a⊤s }.

Let b⊤1 , . . . , b⊤ρ be a basis of span{a⊤1 , . . . , a⊤s }, and let J be the index set of the rows that form a basis of (b⊤1 , . . . , b⊤ρ ). Note that |J| = ρ. In addition, we write At for the set of vectors in {1,-1}J with exactly t ones (i.e., At := {α ∈ {1,-1}J | ∑j∈J αj = 2t - ρ}) and T for the set of t such that (as′ j)j∈J contains exactly t ones and (as′ j)j̸∈J contains both one and minus one for some realization of as′ (i.e., T := {t | max{0, ρ-M(1-ps′ )+1} ≤ t ≤ min{ρ, Mps′ -1}} since as′ contains exactlyMps′ ones). Then, for any α ∈ At with t ∈ T , we have

since a ∈ span{a⊤1 , . . . , a⊤s } with (aj)j∈J = α is uniquely determined but as′ with (as′ j)j∈J = α has at least M- ρ possibilities and they occur with the same probability. Moreover, we have

since 0 <Mps′ <M. Hence, we have

Claim 2. For any s′ > s and ρ = M- 1, we have a⊤s′ ̸∈ span{a⊤1 , . . . , a⊤s } with probability at least 1/M.

Proof. We regard as′ a vector of random variables but a1, . . . , as are fixed. Let ℓ =Mps′ and let ˜x be a solution of IP(s) that is not the all-one vector nor the all-minus-one vector. Such an ˜x must exist since IP(s) has multiple solutions and the all-minus-one vector is not feasible by p1 ̸= 1/2. It is sufficient to prove that ∑j as′ j ˜xj = (2ℓ -M) happens with probability at most (M- 1)/M. Let t be the number of minus ones in ˜x. Since ˜x is not the all-one vector nor the all-minus-one-vector, we have 1 ≤ t ≤ M- 1.

(Mℓ ) since it occurs when (as′ j, ˜xj) = (-1, -1) holds for exactly t/2 choices of j. This probability is equal to the probability that exactly t/2 balls are red out of ℓ balls drawn one after another without replacement from a bag that containing t red balls andM-t black balls. If ℓ >M-t/2, the probability is clearly zero. If ℓ =M- t/2, the probability is at most

since t ≤M- 1. For the case when ℓ <M- t/2, consider the situation that we have drawn ℓ-1 balls and about to draw the final one ball from the bag. We have two cases to draw t/2 red balls: (i) the number of drawn red balls is t/2 - 1 and the final ball is red or (ii) the number of drawn red balls is t/2 and the final ball is black. Thus the event occurs with probability at most

B Additional Experiments

In practice, not all workers answer all questions. We randomly remove 50% of the answers of each test question for each trial in the experiment of Table 2. Table 3 shows that the performance regularization still contributes to the performance gain.