Multiple Noisy Label Distribution Propagation for Crowdsourcing

1 Introduction

In many pervasive applications of supervised learning, particularly with the rapid growth of deep learning, one frequently encounters the situation in which extensive data remain unlabeled. Traditionally, labeling tasks have been typically processed by domain experts. This provides accurate labels but is inefficient and involves a high cost [Tian and Zhu, 2015; Zhang et al., 2016b]. Thus, crowdsourcing has emerged as an effective paradigm for annotating large datasets in domains such as computer vision and natural language processing [Liu et al., 2012; Karger et al., 2014]. Crowdsourcing platforms such as Amazon Mechanical Turk 1 and Crowdflower 2 provide participative online markets where the requesters publish specific types of human intelligence tasks (HITs) and collect numerous labels from ordinary labelers (or annotators) in a short time and at a relatively low cost. However, the qualities of collected labels provided by a single crowd labeler are often poor and the noise associated with the labels can compromise practical applications. To our knowledge, these unreliable labels may be caused by personal preference, low payment for each task, and varying cognitive abilities [Sheng et al., 2008; Rodrigues and Pereira, 2017; Qiu et al., 2018]. To solve this problem, multiple labels are frequently requested from different crowd labelers for a single instance. In other words, repeated labeling is performed [Li et al., 2016; Zhang and Wu, 2018; Li et al., 2019]. After acquiring multiple noisy label sets of each instance by repeated labeling, label integration methods can be used to infer (estimate) the unknown true label of each instance.

∗Corresponding author

1 http://www.mturk.com

2 http://crowdflower.com

Consequently, integrating labels from multiple noisy labels has recently attracted considerable research attention [Sheshadri and Lease, 2013; Zhang et al., 2016a]. The most straightforward label integration (consensus) method is majority voting (MV), which naively assumes that all labelers have the same reliability. In addition to MV, more sophisticated methods have been proposed to improve the performance of label integration [Dawid and Skene, 1979; Whitehill et al., 2009; Raykar et al., 2010; Demartini et al., 2012; Karger et al., 2014; Zhang et al., 2016a; Rodrigues and Pereira, 2017]. These improved methods have clearly achieved remarkable progress to model crowdsourcing based on different parameters such as the reliabilities of labelers, the difficulties of instances, and labeling biases. However, to the best of our knowledge, nearly all existing label integration methods focus solely on the multiple noisy label set itself of the individual instance while totally ignoring the intercorrelation among multiple noisy label sets of different instances.

To solve this problem, in this study we propose a multiple noisy label distribution propagation (MNLDP) method. MNLDP focuses on the intercorrelation among multiple noisy label sets of different instances instead of directly estimating the aforementioned parameters. In MNLDP, the traditional multiple noisy labels are first transformed into multiple noisy label distributions, and a feature space based on the overlapped local linear neighborhood patches is constructed, where the edge weights of each patch can be calculated by a standard quadratic programming procedure. Then, the topological structure of the feature space is globally shared with the multiple noisy label space for simplicity. With the multiple noisy label space available, MNLDP then propagates the multiple noisy label distribution of each instance to its nearest neighbors. Consequently, each instance absorbs a fraction of the multiple noisy label distributions from its nearest neighbors and yet simultaneously maintains a fraction of its own multiple noisy label distribution.

The main contributions of this work are briefly summarized as follows: 1) The multiple noisy label integration problem is transformed into an MNLDP problem, which provides a new perspective from which to solve the multiple noisy label integration problem. 2) A novel MNLDP algorithm is designed to exploit the intercorrelation among multiple noisy label sets of different instances, and thus the effect of the multiple noisy label set itself of the individual instance is weakened.

The remainder of this paper is organized as follows. Section 2 introduces related work. Section 3 describes the proposed MNLDP method in detail. Section 4 presents a convergence analysis of MNLDP. Section 5 describes the experimental setup and results. Section 6 concludes the study and outlines the main directions for future work.

2 RelatedWork

Because of the openness of crowdsourcing, inferring the unknown true labels of instances from multiple noisy labels is a challenge. Many label integration (consensus) methods have been proposed for crowdsourcing. Majority voting (MV) [Sheng et al., 2008] is the simplest and most effective method. However, it naively assumes that all labelers have the same reliability, which weakens its performance in many real-world crowdsourcing scenarios.

To improve the quality of integration labels, researchers have proposed numerous label integration (consensus) methods. [Dawid and Skene, 1979] proposed a method (DS) based on the expectation maximization algorithm, which uses the maximum likelihood estimation to estimate a confusion matrix for each labeler and a class prior. [Demartini et al., 2012] proposed the ZenCrowd method (ZC), which uses only a two-element parameter to weight the reliability of a labeler. [Karger et al., 2014] proposed a belief propagation-like label integration method (KOS) based on the reliabilities of labelers. [Zhang et al., 2016a] proposed another novel method called the ground truth inference using clustering (GTIC) that is based on Bayesian statistics for multi-class labeling. Focusing on binary labeling, [Raykar et al., 2010] proposed a Bayesian estimation-based method to model the two parameters of sensitivity and specificity to denote labelers' biases toward positive and negative instances, respectively. [Whitehill et al., 2009] proposed a method to infer the true labels, the expertise of workers, and the difficulty of items simultaneously. [Rodrigues and Pereira, 2017] proposed a deep neural network layer known as a crowd layer. [Guan et al., 2017] proposed an approach for training deep neural networks that exploits information about the annotators.

All of these improved methods have clearly achieved remarkable progress to model crowdsourcing based on different aspects such as the reliabilities of labelers, the difficulties of instances, and labeling biases. However, to the best of our knowledge, nearly all existing label integration methods focus solely on the multiple noisy label set itself of the individual instance while totally ignoring the intercorrelation among multiple noisy label sets of different instances. To solve this problem, we propose an MNLDP method. In MNLDP, each instance absorbs a fraction of the multiple noisy label distributions from its nearest neighbors and yet simultaneously maintains a fraction of its own multiple noisy label distribution.

Please note that our proposed MNLDP is entirely different from the well-known label distribution learning (LDL) [Geng, 2016], which is a new machine learning paradigm in which each instance is annotated by a label distribution. The label distribution in LDL covers a certain number of labels, representing the description degree of each label to the data point. One label may only partially describe the instance, but that the label describes the instance is completely true. However, in a multiple noisy label distribution, only one label is regarded as completely true, and the other labels are all wrong. Please also note that our proposed MNLDP is entirely different from the linear neighborhood propagation (LNP) [Wang and Zhang, 2008] for semi-supervised learning. LNP propagates the labels from the labeled points to the whole dataset using these linear neighborhoods with sufficient smoothness. By contrast, MNLDP propagates the multiple noisy label distributions rather than the multiple noisy labels themselves.

3 MNLDPMethod

In crowdsourcing scenarios, a dataset can be expressed as S = {(xi,Li)|1 ≤ i ≤ n}, where xi denotes the i-th (i = 1, 2, · · · , n) instance, and Li = {lir}Rr=1 denotes its multiple noisy label set provided by R labelers. Each element lir represents the label provided by the r-th (r = 1, 2, · · · , R) labeler, which takes the value from the class label set Y = {y1, y2, · · · , yc}. To construct the multiple noisy label space, Li is first transformed into a multiple noisy label distribution Pi = {py1 i , py2 i , · · · , pyc i }, where pym i (m = 1, 2, · · · , c) denotes the probability (frequency) that all labelers label xi as ym. Obviously, pym i ∈ [0, 1] and ∑cm=1 pym i = 1. Based on the defined distribution, the dataset S can then be transformed into S = {(xi, Pi)|1 ≤ i ≤ n}.

In addition, to construct the multiple noisy label space, we still must construct a feature space with the neighbor information of each data point. As with many common graph-based learning methods, the topological structure of the feature space can be represented by G =< V, E,W >, where V is the vertex set corresponding to data points, E is the edge set associated with each edge eij representing the relationship between each pair of data points xi and xj , and W is the weight matrix of G with each element wij measuring how similar xi is to xj. Note that usually wij ̸= wji.

For computational simplicity, we assume that each data point can be optimally reconstructed using a linear combination of its neighbors in the feature space [Roweis and Saul, 2000; Wang and Zhang, 2008]. Thus, our objective is to minimize the following:

where N(xi) is the set of the k-nearest neighbors of xi. We further constrain 1Twi = 1, where

∑j wij = 1 and wij ≥ 0. For the local weight matrix wi, the minimization can be defined as:

where Gijk = (xi - xj)T (xi - xk) is the (j, k)-th entry of the local Gram matrix Gi .

Thus, the construction can be solved by the following n standard least square programming problems, which is formulated as Equation 4. Note that we first obtain a series of weight matrix wi and then merge them to construct the whole space.

Inspired by the smoothness assumption [Zhu et al., 2005] and multi-label manifold learning [Hou et al., 2016], we can naturally infer that the multiple noisy label space locally shares the topological structure of the feature space. However, learning the topological structure from the feature space to the multiple noisy label space is difficult. Thus, we further assume that the global topological structure can be simply shared. With the W and the aforementioned assumption, the multiple noisy label space is approximately formulated as:

where µi = {µy1 i , µy2 i , ..., µyc i } is the multiple noisy label distribution of xi in the propagation. µi is different fromPi. Pi is the initial multiple noisy label distribution. However, µi is the multiple noisy label distribution at a particular propagation state. Although this hypothesis is naive, we believe it is reasonable in most cases because the annotators provide the multiple noisy labels based on the features of the instance.

In the t-th propagation, the propagated multiple noisy label distribution can be divided into two sections: 1) a fraction of the multiple noisy label distributions from its nearest neighbors, and 2) some multiple noisy label information of its initial state (i.e., Pi). Thus, the µi at the t+1-th propagation is:

where αi ∈ (0, 1) is the controlling factor that adjusts the proportions from its nearest neighbors and its own original state (distribution). More specifically, when αi < 0.5, the propagated multiple noisy label distribution relies more on its own original state. The extreme case is αi = 0, and thus our MNLDP degenerates into the simplest MV (i.e., µi = Pi). Conversely, when αi > 0.5, the propagated multiple noisy label distribution relies more on its nearest neighbors. When αi = 1, MNLDP completely abandons its own original state Pi (i.e., µt+1 i = ∑j:xj∈N(xi) wijµtj).

We estimate the controlling factor αi using the label uncertainty [Sheng et al., 2008]. The detailed equation is:

where η ∈ [0, 0.5] is a hyper-parameter used to adjust the influence from its nearest neighbors, and

where

where Lym p is the number of the class label ym, Lym n is the number of other classes, and the decision threshold d = 0.5.

After a certain number of iterations, Equation 6 reaches to a state of convergence. The convergence analysis of Equation 6 is presented in Section 4. Let µi = {µym i }cm=1 be the final multiple noisy label distribution of xi. Its integration label is then defined as:

Figure 1 graphically shows the basic framework of our proposed MNLDP.

Now, let us take an artificial binary toy classification dataset as an example to illustrate the process and effectiveness of our proposed MNLDP. The dataset is artificially generated from two interleaving half circles, and the standard deviation of the Gaussian noise is 0.1. It contains 200 data points with two-dimensional features. We then employ 20 simulated labelers who possess the same level of reliability to label each point. In our experiments, we set the number of nearest neighbors k to 5, and then we observe the label integration process and results when the numbers of iterations are 0, 10, and 20.

Figure 2 graphically shows the detailed process and results, where Figure 2 (a) shows the original data with the true class label distributions. The blue squares and red triangles represent two classes. When the numbers of iterations are 0, 10, and 20, the label integration process and results are shown in Figure 2 (b), Figure 2 (c), and Figure 2 (d), respectively. The grey dashed lines among the different data points connect their five nearest neighbors. From these, the multiple noisy label space is constructed and then the multiple noisy label distributions are propagated through the multiple noisy label space.

4 Convergence Analysis of MNLDP

In this section, we analyze the convergence property of MNLDP theoretically. Let the entire propagative multiple noisy label distribution sequence U t = [(µt1 )T , (µt2 )T , · · · , (µtn )T ]T , the entire initial multiple noisy label distribution sequence P = [P T 1 ,P T 2 , · · · ,P T n ]T , and the diagonal matrix be expressed as:

where αi is the controlling factor for xi. Equation 6 can then

Because the initial condition is U 0 = P, Equation 12 becomes:

Because of αiwij ∈ αW ≥ 0 and ∑i αiwij = αi, from the Perron-Frobenius theorem, the spectral radius of αW ranges from rmin(αW) to rmax(αW) (i.e., rmin(αW) ≤ ρ(αW) ≤ rmax(αW)), where rmin(αW) = mini ∑j αiwij and rmax(αW) = maxi ∑j αiwij. The eigendecomposition of (αW)t can be represented as:

where diag(λ) is the diagonal matrix composed of all eigenvalues and V is connected by all eigenvectors. With the process of propagation, the eigenvalues, which are less than 1, are reduced to 0. Thus,

where ∑t-1 i=0 (αW)i can be regarded as the infinite series. It is rewritten as:

Therefore,

Based on this analysis, U t will converge to:

5 Experiments and Results

We validated the effectiveness of our proposed MNLDP by comparing it with five baseline methods, namely, MV, DS, ZC, KOS, and GTIC on simulated and real-world datasets. We implemented our proposed MNLDP on the crowd environment and its knowledge analysis (CEKA) platform [Zhang et al., 2016b] and used the existing implementations of MV, DS, ZC, KOS, and GTIC on the CEKA platform [Zhang et al., 2016b]. In MNLDP, we set the number of nearest neighbors k to 5 and the hyper-parameter η to 0.5.

5.1 Experiments on Simulated Datasets

To validate the effectiveness of our proposed MNLDP in a slightly more controlled environment, six popular benchmark datasets were used by simulating multiple labelers with different levels of expertise. Table 1 provides detailed information on these datasets, which came from the University of California at Irvine (UCI) repository and represent a wide range of domains and data characteristics.

To simulate a crowdsourcing process to obtain multiple noisy labels of each instance, the original true labels of all instances were hidden. For each labeler, the original true label was assigned to each instance with the probability p and any one of false labels otherwise. To maintain the robustness of the experiments under different situations, two simulating strategies were considered:

1. In the first series of experiments, the labeling quality of each labeler was fixed at 0.6 and the number of labelers varied from 3 to 50.

1. In the second series of experiments, the number of labelers was fixed at 10 and the labeling quality of each labeler was randomly generated from a uniform distribution on the interval [0.1, 0.95].

After obtaining the multiple noisy label set of each instance, we applied label integration (consensus) methods to infer its integration label. We know that each simulation process has a certain degree of randomness that cannot be avoided. To reduce the fluctuations caused by this randomness, each experiment was repeated 20 times independently and the integration accuracies were averaged.

Figure 3 displays the detailed comparison results for the first series of experiments. From these results, we can see that: 1) The integration accuracy of MNLDP was much higher than the five baseline methods, particularly when the number of labelers was less than 10. 2) The differences among the different label integration (consensus) methods gradually disappeared as the number of labelers increased, particularly when the number of labelers approached 50.

Figure 4 displays the detailed comparison results for the second series of experiments. From these comparison results, we can see that: 1) As expected, the integration accuracy improved as the labeling quality of each labeler increased. 2) Compared to the five baseline methods, an apparent turning point was reached, which mainly concentrated at around 0.3 in the different datasets. When the labeling quality of each labeler was below this turning point, our proposed MNLDP was even worse than a few of the baseline methods. However, when the labeling quality of each labeler surpassed this turning point, our proposed MNLDP significantly outperformed all the baseline methods until the labeling quality approached 0.7. 3) The differences among different label integration (consensus) methods gradually disappeared when the labeling quality reached 0.8.

Based on these comparison results, we can see that the performance of MNLDP was much better overall, that is, more stable and robust than all the other baseline methods. This is because, in MNLDP, each instance absorbed a fraction of the multiple noisy label distributions from its nearest neighbors and yet simultaneously maintained a fraction of its own original multiple noisy label distribution. Therefore, when the labeling quality of each labeler was very low (for example, less than 0.3), MNLDP was even worse than some existing baseline methods because it enlarged the incorrect label distributions in the process of propagation.

5.2 Experiments on Real-World Datasets

To evaluate further the performance of MNLDP, we conducted our experiments on three real-world crowdsourced datasets: Leaves, LableMe, and Music Genre, which were collected from Amazon Mechanical Turk (AMT) and are publicly available.

The crowdsourced dataset Leaves [Zhang et al., 2016b] is a traditional classification dataset, which distinguishes six types of leaves depending on their shape and other characteristics. The LabelMe dataset [Rodrigues and Pereira, 2017] is an image classification domain derived from LabelMe data [Russell et al., 2008]. To find neighbor images, MNLDP computes the image similarities based on 512 numerical features determined by the GIST descriptor 3 , which was proposed by [Oliva and Torralba, 2001]. The Music Genre dataset 4 is published on AMT and used to collect multiple noisy labels by [Rodrigues et al., 2013]. Because different genres have different extraction criteria and the criteria are non-overlapping [Aucouturier and Pachet, 2003], we utilized Principal Component Analysis to extract 31 pivotal features from the 124-dimensional full combined feature vector. Table 2 summarizes the detailed data characteristics of these crowdsourced datasets.

Table 3 presents detailed comparison results obtained by different label integration (consensus) methods on three realworld crowdsourced datasets. As expected, our proposed MNLDP significantly outperformed all the baseline methods. The integration accuracies of MNLDP on three real-world crowdsourced datasets were 65.1%, 82.3%, and 79%, respectively, which were much higher than those of MV, DS, ZC, KOS, and GTIC. Based on these results, we can draw nearly the same conclusions as those from the simulated benchmark datasets. However, we also should note that the KOS performed very poorly on both the LabelMe and Music Genre datasets. We believe that this was because some labelers only labeled a tiny portion of instances, and KOS failed to estimate the reliabilities of these labelers.

To explore the effect of the global sharing of the topological structure on both the feature and multiple noisy label spaces, we modified the parameters of the GIST descriptor to obtain different features on the LabelMe dataset. Based on these different features, the degree of sharing between the feature and multiple noisy label spaces was approximated as different. In the GIST descriptor, the number of blocks and scale of filters were fixed at 4. In addition, the number of orientations per scale was changed from 2 to 16, which indicates that the number of features varied from 2 ∗ 4 ∗ 42 = 128 to 16 ∗ 4 ∗ 42 = 1024. Figure 5 shows that the integration accuracy (%) improved as the number of different orientations per scale increased. These comparison results reveal that the integration accuracy (%) of our proposed MNLDP steady improved as the number of different orientations per scale increased until the number of generated features approximated 9 ∗ 4 ∗ 42 = 576. These results also reveal the rationality for the global sharing of the topological structure between the feature and multiple noisy label spaces.

3 http://people.csail.mit.edu/torralba/code/spatialenvelope

4 http://fprodrigues.com//mturk-datasets.tar.gz

6 Conclusion and FeatureWork

This study proposed an MNLDP method to improve the performance of label integration for crowdsourcing. MNLDP first transforms the multiple noisy label set of each instance into its multiple noisy label distribution and then propagates this distribution to its nearest neighbors. The extensive experimental results on simulated and real-world crowdsourced datasets show that, in many cases, our proposed MNLDP significantly outperformed all the other state-of-the-art label integration (consensus) methods used in comparison.

For simplicity, we naively assumed that the multiple noisy label space shared nearly the same topological structure with the feature space. We noticed that this global sharing assumption is quite simple and rough. Therefore, alleviating this assumption more or less to improve further the performance of the current MNLDP and strengthen its advantage is a main direction for our future work.

Acknowledgments

The work was partially supported by the National Natural Science Foundation of China (U1711267), the Open Research Project of Hubei Key Laboratory of Intelligent Geo-Information Processing (KLIGIP201601) and the Fundamental Research Funds for the Central Universities (CUG2018JM18 and CUGGC03).