MiSC: Mixed Strategies Crowdsourcing

1 Introduction

In recent years, with the advent of many complex machine learning models, the need for large amounts of labeled data is boosted. Though we can obtain unlabeled data abundantly and cheaply, acquiring labeled data from domain experts or well-trained workers with specific background knowledge is usually expensive and time-consuming. Crowdsourcing provides an effective way of collecting labeled data quickly and inexpensively. However, as crowd workers are usually nonexperts or even spammers, the individual contribution from one worker can be unreliable. To improve the label quality, each item is presented to multiple workers. Therefore, inferring the true labels from a large sum of noisy labels is a key challenge in crowdsourcing.

Existing learning-from-crowds works mainly focus on eliminating annotations [Li and Jiang, 2018] from unreliable workers or reducing their weights. In line with this goal, a series of work focusing on evaluating workers' quality are proposed based on accuracy [Whitehill et al., 2009; Karger et al., 2011], and confusion matrix [Dawid and Skene, 1979; Raykar et al., 2009; Liu et al., 2012; Zhou et al., 2012; Zhang et al., 2016]. Apart from that, two emerged works [Zhou and He, 2016] and [Li and Jiang, 2018] aim at completing annotations by translating single/multi-label crowdsouring tasks to tensor completion problems. However, their improvements in performance over conventional annotations methodologies are limited. In this work, we present a label aggregation algorithm by mixing the two strategies: We view the label tensor as an incomplete and noisy tensor, which is coherent to the reality where incompleteness comes from heavy workloads and noise stems from mislabelling. In a nutshell, we capture the structural information and filter out noisy information from the label tensor through tensor completion. This is followed by a conventional label aggregation procedure. We iterate over the above two steps until convergence. Despite the generality of the proposed framework, we highlight our use of tensor decomposition techniques.

Tensors are a higher-order generalization of vectors and matrices and constitute a natural representation for many reallife data that are intrinsically multi-way. In analogy to the significance of matrix QR factorization and singular value decomposition in matrix preconditioning and principal component analysis, tensor decomposition concepts have been deployed in modern machine learning models. Iconic examples include text analysis [Collins and Cohen, 2012; Liu et al., 2015], compression of neural networks [Denton et al., 2014; Novikov et al., 2015], and tensor completion [Suzuki, 2015; Imaizumi et al., 2017]. Among various popular tensor decomposition techniques, we specifically have interests in the Tucker model [Tucker, 1963; Levin, 1963; De Lathauwer et al., 2000a]. The Tucker decomposition factorizes a tensor into a core tensor of generally smaller size, along with factor matrices for each of the tensor modes. We exemplify through a case study and show that for a perfectly labeled matrix, its corresponding label tensor will have an intrinsically low-rank Tucker decomposition. The main contributions of this article

• are:· A general mixed strategies framework for crowdsourcing tasks is proposed, in which annotations are completed by tensor recovery and ground-truth labels are estimated by conventional deduction algorithms.
• To our knowledge, this is the first work that introduces tensor decomposition methods to exploit the structural information in the label tensor. This scheme also bears a clear physical interpretation.
• Experimental results demonstrate that the proposed algorithms manage to improve existing methods to achieve higher aggregation accuracy.

• Most importantly, the proposed algorithms are shown to be particularly powerful compared to conventional pure label aggregation methods when the annotations are highly sparse and severely noisy. This is crucial since obtaining low-sparsity/ high-quality annotations can be arduous and expensive.

In the following, Section 2 briefly summarizes the related work. Then, Section 3 presents the necessary tensor preliminaries. Section 4 focuses on one of the proposed models, mixed low-rank Tucker DS-EM aggregation, and showcases the algorithm. Next, numerical experiments comparing the proposed MiSC (mixed strategies crowdsourcing) with pure label aggregation methods are given in Section 5. Finally, Section 6 concludes this work.

2 RelatedWork

Our two-stage mixed algorithms build upon the standard label aggregation algorithms. Majority voting, as the most straightforward crowdsourcing technique, has served as a baseline method for years. Besides, the seminal work of Dawid and Skene based on expectation maximization (EM), denoted as DS-EM henceforth, is also among the earliest work of crowdsourcing [Dawid and Skene, 1979] which is a generative method by assuming the performance of each worker is consistent across different tasks. Moreover, the crowdsourcing problem is further translated into a variational Bayesian inference problem of a graphical model in [Liu et al., 2012]. Using Mean Field algorithm, the parameters are tuned to maximize the marginal likelihood. [Zhou et al., 2012] introduces the minimax entropy principle into crowdsourcing tasks and infers true labels by minimizing the Kullback-Leibler (KL) divergence between the probability distribution over workers, items, labels, and the ground truth.

In matrix completion, most problems are formulated into the construction of a structurally low-rank matrix X having the same observed entries: minX rank(X), s.t. (X-A)Ω = 0, where A represents the matrix with missing values filled by zeros and Ω is the mapping that specifies the locations of originally non-zero elements. Directly solving the above optimization problem is NP-hard, which results in extensive research on solving alternative formulations. One of the two popular candidates is to minimize the nuclear norm as the convex envelope of the matrix rank-operator [Cand`es and Recht, 2009; Chen, 2015]. This nuclear norm minimization idea is then further generalized to tensor completion problems by computing matricizations of the tensor along its k modes and summing over the nuclear norm of the resulting k matrices (abbreviated as LRTC in the remainder of this paper) [Liu et al., 2013; Signoretto et al., 2014]. Methods that exploit tensor decomposition formats were also introduced to tensor completion problems in recent years. In [Jain and Oh, 2014; Suzuki, 2015; Zhao et al., 2015], the authors use the Canonical Polyadic (CP) decomposition for tensor estimators.

The pioneers of introducing tensor completion concepts to crowdsourcing problems are [Zhou and He, 2016] and [Li and Jiang, 2018], where authors build label aggregation algorithms upon the methodologies introduced in [Liu et al., 2013]. This work contrasts with them in two main aspects:

(1) Aims - we focus on introducing a versatile completeaggregate two-step looping structure for crowdsourcing tasks, where completion techniques adopted can be of any kind. (2) Approaches - we introduce tensor decomposition driven completion algorithms and showcase its advantages over LRTC methods in crowdsourcing tasks.

3 Preliminaries

Tensors are high-dimensional arrays that generalize vectors and matrices. In this paper, boldface capital calligraphic letters A, B, . . . are used to denote tensors, boldface capital letters A,B, . . . denote matrices, boldface letters a, b, . . . denote vectors, and Roman letters a, b, . . . denote scalars. A d-way or d-order tensor A ∈ RI1×I2×···×Id is an array where each entry is indexed by d indices i1, i2, . . . , id. We use the convention 1 ≤ ik ≤ Ik for k = 1, . . . , d, where the Ik is called the kth dimension of tensor A. MATLAB notation A(i1, i2, . . . , id) is used to denote entries of tensors. Fibers are high-dimensional analogue of rows and columns in matrices. In a matrix A, a matrix column can be referred by fixing a column index. By again adopting MATLAB convention, the i2th column of matrix A is denoted A(:, i2), which is also called a 1-mode fiber of the matrix. Similarly, a matrix row A(i1, :) is known as a 2-mode fiber of the matrix. For a d-way tensor, a k-mode fiber is determined by fixing all the indices but the kth one, which we denote as A(i1, . . . , ik-1, :, ik+1, . . . , id).

Tensor k-mode matricization, also known as tensor k-mode unfolding/flattening, reorders the elements of a d-way tensor into a matrix. It is formally defined as:

Definition 1 [Kolda and Bader, 2009, p. 459] The kmode matricization of a tensor A ∈ RI1×···×Id , denoted by A(k) ∈ RIk×I1···Ik-1Ik+1···Id , arranges the k-mode fibers to be the columns of the resulting matrix. Tensor element A(i1, . . . , id) maps to matrix element A(k)(ik, j), where j = 1 + ∑dp=1,p̸=k (ip - 1)Jp and Jp = ∏p-1 m=1,m̸=k Im.

The generalization of the matrix-matrix multiplication to tensor involves a multiplication of a matrix with a d-way tensor along one of its d modes:

Definition 2 [Kolda and Bader, 2009, p. 460] The k-mode product of a tensor G ∈ RR1×···×Rd with a matrix U ∈ RJ×Rk is denoted A = G ×k U and defined by

Following Definition 2, the full multilinear product of a dway tensor with d matrices is:

Definition 3 [Cichocki et al., 2015, p. 147] The full multilinear product of a tensor G ∈ RR1×···×Rd with matrices U (1) ,U (2) , . . . ,U (d) , where U (k) ∈ RIk×Rk , is denoted A = [[G; U (1) , U (2) , . . . , U (d) ]] and defined by A = G ×1 U (1) ×2 U (2) · · · ×d U (d) , where A ∈ RI1×···×Id .

Following the definition of the full multilinear product, we define the Tucker decomposition as follows:

Definition 4 The Tucker decomposition decomposes a tensor A ∈ RI1×···×Id into a core tensor G ∈ RR1×···×Rd multiplied by a matrix U (k) ∈ RIk×Rk along the kth mode for k = 1, . . . , d. That is, a d-way tensor A is regarded as a multilinear transformation of a small core tensor G by d factor matrices U (1) ,U (2) , . . . ,U (d) . By writing out U (k) = [u(k) 1 ,u(k) 2 , . . . , u(k) Rk ] for k = 1, 2, . . . , d, we have

where r1, r2, . . . , rd are auxiliary indices that are summed over, and ◦ denotes the outer product.

The dimensions (R1,R2, . . . ,Rd) of these auxiliary indices are called the Tucker ranks. It is worth noting that Rk is in general no bigger than rank(A(k)), which is also called the multilinear rank. In other words, for a Tucker representation with Tucker ranks (S1, S2, . . . , Sd), if there exists a k, where 1 ≤ k ≤ d and Sk > rank(A(k)), then we can always find an equivalent Tucker representation with Tucker ranks no bigger than the multilinear ranks.

When the core tensor S is cubical and diagonal, a Tucker model reduces to a CP model. By writing out the formula, a CP decomposition expresses a d-way tensor A as

4 When Label AggregationMeets Tensor Completion

We now exemplify the proposed complete-aggregate two-step looping scheme using the case of mixed low-rank Tucker DSEM aggregation. Firstly, we showcase in Section 4.1 that Tucker model bears a clear physical meaning in completing label tensor. In Section 4.2, we explain in detail how to combine a low-rank Tensor completion with traditional label aggregation to form one loop. The MiSC algorithms are then given in 4.3.

4.1 Basic Idea

We use A ∈ RNw×Ni to denote the label matrix, where Nw is the number of workers and Ni is the number of items. If item i is labeled by worker w as class c, then we have A(w, i) = c. Now we proposed to form a three-way binary tensor A of size Nw×Ni×Nc by using the label matrix. This is done by using the canonical basis vectors to denote the non-zero elements in the matrix and all-zero vectors to denote unlabeled entries. Due to the fact that each worker gives at most one label for one item, there then contains at most one 1 in each of the 3mode fibers of tensor A. We use a small example to illustrate this process.

Example 1 Suppose there are two workers labeling for three items among four classes. The first worker believes the first item and the third item belong to the first class and the fourth class, respectively. The second worker labels the first item as the first class and the second item as the third class. We use label matrix A ∈ R2×3 to describe the above setting, where

Considering matrix A contains four non-zero elements, four 3-mode fibers of the resulting tensor contain a 1, while the remaining two fibers are initiated with zeros vectors. For A(1, 1) = 1 and A(2, 1) = 1, the canonical basis vector e1 = (1, 0, 0, 0)T is used. For A(1, 3) = 4 and A(2, 2) = 3, the canonical basis vectors e4 = (0, 0, 0, 1)T and e3 = (0, 0, 1, 0)T are needed respectively. Collecting these fibers renders the following tensor

We call the above-defined tensor A label tensor. Our goal is to complete the label tensor A by assuming a specific underlying structure. Hence the problem can be regarded as a tensor completion task. As is well-known, the quality of the label matrix is in general not guaranteed. Therefore, it is of great importance that the proposed method should not only fill in entries but also serve as a pre-processor to de-noise the label tensor before doing deduction.

Similar to the traditional matrix completion problem formulations, in this paper we propose to form the following optimization problem:

The optimization problem is solved via a truncated Tucker decomposition. It is worth noting that finding an exact Tucker decomposition of rank (R1,R2,R3), where Rk = rank(A(k)), of A is easy. However, finding an optimal truncated Tucker decomposition is nontrivial [Kolda and Bader, 2009]. In this paper, the Tucker model is initialized using a truncated higher-order SVD [De Lathauwer et al., 2000a] and updated by a higher-order orthogonal iteration algorithm [De Lathauwer et al., 2000b]. We now use an extreme case to demonstrate the vivid physical meaning behind the choice of a Tucker model.

Example 2 Suppose the label matrix is perfectly given by two workers for three items among four classes as follows

The label tensor is then constructed as

Now we consider the exact Tucker decomposition of this label tensor. By taking three different mode matricizations, we obtain rank(A(1)) = 1, rank(A(2)) = 3, rank(A(3)) = 3, where min (Ni, Nc) = min (3, 4) = 3.

As is demonstrated in the above example, if given a noiseless label tensor, it can be naturally decomposed into an exact low-rank Tucker format with Tucker ranks equal to (1, min (Ni, Nc), min (Ni, Nc)).

4.2 Methodology

In general, the proposed MiSC consists of two phases: label tensor completion and deduction. In each phase, a wide range of algorithms are available as will be seen in Section 5. We visualize the architecture of MiSC in Figure 2.

The method starts from a binarized label tensor constructed as described in Section 4.1. A conventional label aggregation algorithm is adopted to infer a 1 ×Ni resultant initial guess of the ground-truth labels. Similar to the idea explained in Example 1, the initial guess can then be encoded to a 1 × Ni × Nc slice S and concatenated with the raw binarized label tensor. By doing so, we enlarge the size of the label tensor fromNw ×Ni ×Nc to (Nw +1)×Ni ×Nc and form a target tensor T = [A;S], which follows by completion iterations. The all-zero 3-mode fibers of tensor A are filled in during the annotation completion step as depicted in (2) and (3). At the same time, the imposed low-rank constraint also automatically smooths the noisy label tensor. When the stopping criteria are not satisfied, the bottom annotated slice of the completed tensor is separated and concatenated again with the binarized raw data to form an iterative refinement loop.

4.3 Algorithms

Before proposing the pseudocode of the MiSC algorithms, we will briefly introduce the truncated higher-order SVD

Algorithm 1 Truncated higher-order singular value decomposition (SVD)

Input: Tensor T ∈ RI1×···×Id , ranks: R1, . . . ,Rd Output: Core tensor G ∈ RR1×···×Rd , factor matrices U (1) ,U (2) , . . . ,U (d) , where U (k) ∈ RIk×Rk for

Algorithm 2 Higher-order orthogonal iteration

Input: Tensor T ∈ RI1×···×Id , initial rank: R0 , ranks: R1, . . . , Rd.

Output: Core tensor G ∈ RR1×···×Rd , factor matrices U (1) ,U (2) , . . . ,U (d) , where U (k) ∈ RIk×Rk for 1 ≤ k ≤ d.

Initial factor matrices U (k) ∈ RIk×R0 for 1 ≤ k ≤ d using Algorithm 1 with T and R0 1 = . . . = R0d = R0 as the input.

while stopping criteria not satisfied do

(HOSVD) procedure [De Lathauwer et al., 2000a] (denoted as Algorithm 1) and the higher-order orthogonal iteration (HOOI) algorithm [De Lathauwer et al., 2000b] (denoted as Algorithm 2), which serve as two cornerstones for the lowrank Tucker completion.

The ultimate goal of Algorithms 1 and 2 is to find a (nearly) optimal low-rank Tucker decomposition approximation of the target tensor T . While finding an exact Tucker decomposition of the multilinear ranks is rather straightforward by directly employing HOSVD algorithm, the Tucker decomposition of ranks smaller than the multilinear ranks found by truncated HOSVD is demonstrated to be non-optimal in [Kolda and Bader, 2009], in terms of the norm of the difference. Hence we only use a truncated HOSVD step as an initialization procedure. Algorithm 1 takes in a tensor T and prescribed Tucker ranks as inputs, and followed by consecutive SVDs operating on different mode matricizations. Factor matrices of the Tucker model are determined by the leading leftsingular vectors within each SVD step. Lastly, the core tensor G is computed through the full multilinear product of the tensor T ∈ RI1×···×Id with matrices U (1)T , U (2)T , . . . , U (d)T . An initial Tucker decomposition is thereby obtained. It is worth noting that in the HOSVD algorithm, the mode matricizations are always computed directly from the input tensor.

Algorithm 3 Mixed Strategies Crowdsourcing (MiSC)

Input: Label matrix A ∈ RNw×Ni , prior statistics S, initial rank: R0 , ranks: R1,R2,R3.

Output: Inferred true labels.

Find Nc by checking the maximum entry of A Initialize conventional aggregation result s fromA Construct A through the following for-loop:

end for

while stopping criteria not satisfied do

S ← binarize s as discussed in Example 1

T ← concatenate A and S

s ← separate the last slice fromL

end while

ˆA ← choose the indices of the maximum values of all 3mode vectors in L

Infer the true labels from the completed label matrix ˆA by conventional label aggregation techniques

Hence the computation of each of the factor matrices is completely independent of other factor matrices.

The higher-order orthogonal iteration (HOOI) algorithm was proposed in [De Lathauwer et al., 2000b] to give a lowrank Tucker decomposition with a smaller norm of the difference, without guarantees to converge to the global optimum. In Algorithm 2, a Tucker decomposition of prescribed initial ranks is firstly constructed using Algorithm 1. Then the updates follow an alternating linear scheme (ALS): the factor matrices are updated iteratively by updating one at a time and keeping all the others fixed. In contrast to HOSVD, the update of a factor matrix in HOOI is not independent of others. Specifically, the i-mode matricization A(i) in HOOI is computed from tensor A, where A ∈ RR1×···×Ri-1×Ii×R0×···×R0 in the first ALS sweep (a full for-loop corresponds to one sweep). Starting from the second ALS sweep, the size of tensor A before i-mode matricization becomes R1 × · · · × Ri-1 × Ii × Ri+1 × · · · × Rd. One can update the Tucker decomposition for a fixed amount of sweeps or until the residual stops decreasing.

We summarize the proposed MiSC algorithms with an exemplary Tucker completion case in Algorithm 3. The forloop realizes the label matrix to label tensor conversion process explained in Example 1. Within the while-loop, HOOI subroutines are employed to fill in and augment the label tensor. One can iterate over the filling process for a prescribed amount of sweeps or until the last slice stops evolving. After the loops, we binarize the completed 3-way tensor which then follows by a deduction step. The binarization is realized by choosing the indices of the maximum values in each of the 3-mode vectors. A new (Nw + 1) ×Ni label matrix ˆA is thereby constructed. The most computationally expensive steps in Algorithm 3 are SVDs in the HOSVD and HOOI subroutines, which have computational complexities of approximately O((I1I2I3)2 /Ii) and O(Ii(R0 )4 ) flops, respectively.

5 Experimental Results

In this section, the proposed mixed complete-aggregate strategies crowdsourcing algorithms are compared with conventional label aggregation methods on six popular datasets, including Web dataset [Zhou et al., 2012], BM dataset [Mozafari et al., 2014], RTE dataset [Snow et al., 2008], Dog dataset [Deng et al., 2009; Zhou et al., 2012], Temp dataset [Snow et al., 2008], and Bluebirds dataset [Welinder et al., 2010]. Details of their nonzero rates defined by #worker labels #items×#workers , and annotation error rates defined by #wrong labels #worker labels are recorded in Table 1.

Five conventional crowdsourcing methods are considered in the aggregation step of the proposed MiSC. They are: Majority Voting (MV), Dawid-Skene model + Expectation Maximization (DS-EM), Dawid-Skene model + mean field (DSMF) [Liu et al., 2012], and Categorical/ Ordinal Minimax Conditional Entropy (MMCE(C), MMCE(O)).

We consider three tensor completion algorithms in the MiSC algorithms: LRTC 1 , TenALS 2 , and Tucker. These methods represent three different approaches towards the completion problem. LRTC [Liu et al., 2013] aims at minimizing the sum of nuclear norms of the unfolded matrices. While TenALS [Jain and Oh, 2014] and Tucker utilize CP decomposition and Tucker factorization, respectively.

5.1 Comparison with State-of-the-Arts

The estimation errors of all five pure conventional label aggregation algorithms and fifteen MiSC approaches on six real-life datasets are reported in Table 1. It is shown that the proposed MiSC algorithms achieve lower estimation errors than traditional pure crowdsourcing methods on all six datasets. We observe the greatest breakthrough in the Web dataset, where the state-of-the-art estimation errors of around 10.33% are brought down to around 5.24%. The second noticeable refinement is in the Bluebirds dataset, where MiSC algorithms produce error rates lower than 5%, in contrast to the > 8% state-of-the-art records. For the BM, RTE, Dog datasets, the MiSC algorithm via DS-MF+Tucker also reaches the lowest errors of 26.2%, 6.75%, and 15.37%, respectively, among others.

5.2 Pure vs. Mixed Strategies Crowdsourcing

Besides evaluating all MiSC algorithms together with pure label aggregation methods, we also zoom in on pairwise comparisons between pure and mixed strategies that use the same label deduction approaches. Specifically, in the Web dataset, the MiSC algorithms stacked by DS-EM/ DS-MF and Tucker completion have estimation errors of 5.77%/5.73%, compared with the initial 16.92%/16.10% by pure DS-EM/ DS-MF. In the Temp dataset, both DS-EM+Tucker and DSMF+Tucker improve the performance of their corresponding pure counterparts by approximately one point. In the Bluebirds dataset, mixing MMCE aggregations with Tucker completion helps the crowdsourcing reach the lowest error rate of 4.63% compared with the original 8.33%.

1 http://www.cs.rochester.edu/u/jliu/code/TensorCompletion.zip

2 http://web.engr.illinois.edu/∼swoh/software/optspace

Consequently, we have empirically verified that the proposed MiSC algorithms can consistently improve the performance on top of conventional label aggregation schemes. By and large, we also remark that this complete-aggregate twostep looping structure is readily compatible with other stateof-the-art label deduction and tensor completion algorithms.

5.3 MiSC for Sparse and Noisy Annotations

As noticed in Section 5.1, although MiSC successfully improves the annotation quality in all six datasets, the striking refinement obtained in Web dataset stands out and raises the question: when will MiSC be remarkably advantageous? Referencing Table 1, one can see that the Web dataset has the sparsest and "poorest" annotations. Only 88 items out of 2665 are labeled on average per worker, and 63.4% of the total 15567 labels are misleading. We emulate similar scenarios by simultaneously eliminating worker labels from and adding noise to the RTE dataset. The resultant label matrix has a nonzero rate of 3.7%, and four different degrees of annotations error rates: 30.4%, 41.6%, 51.4%, 60.9%. Figure 3 records the corresponding error rates. We can then see that MiSC is significantly more robust to high sparsity and severe noise. Replacing reliable annotations by erroneous labels only slightly affects the accuracy of MiSC, while the performance of traditional pure label aggregation degrades rapidly. We highlight this important finding since the number and quality of worker labels have a huge implication on the crowdsourcing cost. To this end, the proposed MiSC approach provides a means to substantially relax the labor and labeling quality requirements while maintaining superior accuracy.

6 Conclusion

This paper has introduced the mixed strategies crowdsourcing (MiSC) framework, a versatile complete-aggregate twostep iterative procedure, for crowdsourcing tasks. MiSC is readily compatible with various completion techniques and deduction schemes. By integrating tensor completion procedures, and importantly, tensor decomposition methods, into label aggregation, the proposed methods can largely improve the crowdsourcing performance. By further assuming a lowrank Tucker structure, the mixed low-rank Tucker model with conventional label aggregation approaches are shown to be particularly favorable when the annotations are highly sparse and severely noisy. Experiments have shown that MiSC consistently outperforms state-of-the-art methods in terms of estimation errors.

Acknowledgments

This work is partially supported by the General Research Fund (Project 17246416) of the Hong Kong Research Grants Council.