KFNN: K-Free Nearest Neighbor For Crowdsourcing

Authors: wenjun  zhang
liangxiao  jiang
chaoqun  li
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 03:31:24

Abstract: To reduce annotation costs, it is common in crowdsourcing to collect only a few noisy labels from different crowd workers for each instance. However, the limited noisy labels restrict the performance of label integration algorithms in inferring the unknown true label for the instance. Recent works have shown that leveraging neighbor instances can help alleviate this problem. Yet, these works all assume that each instance has the same neighborhood size, which defies common sense. To address this gap, we propose a novel label integration algorithm called K-free nearest neighbor (KFNN). In KFNN, the neighborhood size of each instance is automatically determined based on its attributes and noisy labels. Specifically, KFNN initially estimates a Mahalanobis distance distribution from the attribute space to model the relationship between each instance and all classes. This distance distribution is then utilized to enhance the multiple noisy label distribution of each instance. Subsequently, a Kalman filter is designed to mitigate the impact of noise incurred by neighbor instances. Finally, KFNN determines the optimal neighborhood size by the max-margin learning. Extensive experimental results demonstrate that KFNN significantly outperforms all the other state-of-the-art algorithms and exhibits greater robustness in various crowdsourcing scenarios.

Main paper: 
 introduction: 
 Crowdsourcing provides a more cost-effective way to obtain annotated instances than traditional expert annotation [1] . Through crowdsourcing platforms such as Figure Eight and Clickworker, instances can be annotated by crowd workers at a low cost [2, 3] . While more affordable, these workers possess less expertise than domain experts and are more prone to assigning noisy labels to instances [4] . To address this issue, the concept of repeated annotation is introduced and becomes popular in crowdsourcing [5] . With repeated annotation, each instance is annotated by several workers, thereby obtaining multiple noisy labels. To train supervised models using multiple noisy labels, two main categories of methods have been developed: one-stage methods and two-stage methods. One-stage methods [6, 7, 8] train models directly using multiple noisy labels. Two-stage methods [1, 9] first infer the unknown true label for each instance from its multiple noisy labels via label integration (also known as answer aggregation or ground truth inference) [10] and then train models on integrated labels. One-stage methods, although end-to-end, can only be used to train specifically designed models. As a result, label integration, which is required for the more common two-stage methods, has received a great deal of attention from researchers.It has been theoretically demonstrated that, when worker annotation is more accurate than random annotation, the more noisy labels an instance receives, the easier it becomes to infer its unknown true label [11] . However, to reduce annotation costs, only a few noisy labels can be collected for each instance in crowdsourcing. The limited noisy labels restrict the performance of label integration algorithms in inferring the unknown true label for the instance. Furthermore, some common strategies in crowdsourcing, such as worker modelling, worker elimination and task assignment [12] , fail to mitigate the effects of limited labels in label integration. To alleviate this problem, recent works have begun to focus on leveraging neighbor instances [13, 14, 1] . These works successfully improve the performance of label integration by leveraging the information from neighbor instances obtained by the K-nearest neighbor (KNN) algorithm. However, due to the use of KNN, these algorithms all assume that each instance has the same neighborhood size. This assumption is difficult to hold because it defies common sense, e.g. instances close to the center of classes should have more neighbors than instances close to the boundary of classes.To address this gap, we propose a novel label integration algorithm called K-free nearest neighbor (KFNN). In KFNN, the optimal neighborhood size of each instance is automatically determined based on its attributes and noisy labels. Notably, KFNN is different from some supervised works [15, 16] that determine the optimal K-value for KNN. Unlike in supervised learning, the true label of each instance in crowdsourcing is unknown and only its multiple noisy labels can be used, which makes it difficult to model the relationship between the instance and all classes. To do this, KFNN initially estimates a Mahalanobis distance distribution from the attribute space to model the relationship between each instance and all classes. This distance distribution is then utilized to enhance the label distribution for each instance. Subsequently, a Kalman filter is designed to mitigate the impact of noise incurred by neighbor instances. Finally, KFNN determines the optimal neighborhood size by the max-margin learning. In general, the contributions of this paper can be summarized as follows:• We reveal the limitations caused by fixing the neighborhood size in existing label integration algorithms and propose a novel algorithm called KFNN. In KFNN, the neighborhood size of each instance is automatically determined based on its attributes and noisy labels. • We estimate a Mahalanobis distance distribution from the attribute space to model the relationship between each instance and all classes. This distance distribution enhances the multiple noisy label distribution of each instance. • We design a Kalman filter to mitigate the impact of noise incurred by neighbor instances and then determine the optimal neighborhood size by the max-margin learning, which provides strong theoretical support for our algorithm. • Extensive experimental results demonstrate that KFNN significantly outperforms all the other state-of-the-art label integration algorithms and exhibits greater robustness than existing algorithms in various crowdsourcing scenarios. 
related work: 
 Depending on whether neighbor instances are leveraged or not, existing label integration algorithms can be divided into two categories. The first category of algorithms does not leverage neighbor instances, which considers only the information of the instance itself or the information of all instances globally in label integration. For example, [17] models the ability of each worker with a confusion matrix. In this matrix, each element reflects the probability that this worker annotates an instance with the class corresponding to the row as the class corresponding to the column. [18, 19] are Bayesian versions of [17] , which can be used for binary tasks and multi-class tasks, respectively. Further, [20, 21] improve [19] by introducing the correlation between workers. [11, 22, 23] are classical algorithms based on majority voting and they tend to use the label with the highest number of votes as the integrated label. [24, 25, 26] synchronously model the ability of workers and the difficulty of tasks from different perspectives. [27, 28] use clustering algorithms to divide instances into different clusters from different views, and then map these clusters to different classes. Recently, [29] augments the multiple noisy label distributions of instances as new attributes to the original attribute space and then learns a classifier on the augmented attribute space to predict the integrated labels of instances. [9] constructs graphs for workers and uses a graph neural network to aggregate multi-order information in label integration.The second category of algorithms performs label integration by leveraging the information from neighbor instances obtained by the KNN algorithm. For example, [13] proposes to use the labels assigned to the neighbor instances of an instance to augment this instance's multiple noisy labels and use the augmented multiple noisy labels to infer the integrated label of this instance. [14] considers both nearest and farthest neighbors in weighted voting to address class-imbalanced tasks. Further, inspired by label distribution learning [30, 31] , given an instance, [1] iteratively absorbs the label distributions of its neighbor instances into its label distribution through label distribution propagation.While simpler and more efficient, the first category of algorithms are limited in effectiveness because each instance can only obtain few noisy labels. Both experimental results and theoretical analysis demonstrate the effectiveness of the second category of algorithms in leveraging the information from neighbor instances. However, these algorithms all assume a fixed neighborhood size for each instance, which is often unrealistic and thus limits their performance. To further ensure that each instance has a free neighborhood size, this paper proposes a novel label integration algorithm called KFNN. KFNN automatically determines the optimal neighborhood size for each instance based on its attributes and noisy labels, which improves the performance and robustness of label integration.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We mentioned the limitations of our KFNN in the Conclusion and future work section. KFNN has two empirical parameters and its distribution transformation process is not refined enough.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
algorithm: 
 In this section, we respond to how to automatically determine the optimal neighborhood size for each instance. First, we present some basic notations in crowdsourcing and then define the problem settings. Subsequently, we introduce our KFNN for label integration.Let D = {(x i , L i )} N i=1 denote a crowdsourced dataset, where N is the number of instances, and x i denotes the i-th instance in D. x i can be represented as {x im } M m=1 . Here, M is the dimension of attributes, and x im denotes the attribute value of x i on the m-th attribute A m . L i denotes multiple noisy labels of x i , which can be expressed as {l ir } R r=1 . R is the number of workers and l ir denotes the label of x i annotated by the r-th worker u r . l ir takes a value from a fixed set {-1, c 1 , . . . , c q , . . . , c Q }, where Q is the number of classes, c q denotes the q-th class and -1 indicates that u r has not annotated x i . Label integration aims to infer an integrated label ŷi for x i and minimize the error between ŷi and the unknown true label y i .Recent works [1, 13] have shown that leveraging neighbor instances N i = {x k i } K k=1 of x i can mitigate the restriction of limited noisy labels on the performance of label integration. Here, x k i denotes the k-th nearest neighbor of x i and K is the neighborhood size. However, in these works, the value of K is fixed for each instance within the same dataset, which does not make sense. On the one hand, instances closer to the center of a class benefit from a larger K, as it enables them to collect more labels from similar instances. Conversely, for instances close to the boundary of classes, a larger K plays a negative role in label integration. On the other hand, using a fixed K can bias algorithms towards the majority class in class-imbalanced datasets, as instances from the majority class are more likely to dominate the neighborhood of instances from minority classes. Therefore, we define the Problem 1 to be addressed in this paper as follows:Problem 1. Given a crowdsourced dataset D, how to automatically determine the optimal neighborhood size K * i for each instance x i with {x im } M m=1 and {l ir } R r=1 but without y i .Problem 1 cannot be treated simply as learning an optimal neighborhood size for the KNN algorithm in supervised learning [15, 16] . This is because the true labels of instances in crowdsourcing are unknown. As a result, K can not be evaluated accurately by supervised metrics such as classification accuracy. Moreover, label integration does not divide the crowdsourced dataset into training, validation and test sets, which means that KFNN has to determine K * i immediately when inferring ŷi , rather than with a validation phase.In this subsection, we propose our KFNN to address Problem 1. We argue that K * i should be related to the information from both the attribute space and the multiple noisy label space. Based on this, KFNN divides Problem 1 into two parts: 1) How to fuse the information from the attribute space and the multiple noisy label space? 2) How to determine an optimal K * i for x i ? Correspondingly, KFNN consists of two components, namely label distribution enhancement and K-free optimization, which are used to address the two parts of Problem 1.For each instance x i , {x im } M m=1 reflects all the information of it in the attribute space and {l ir } R r=1 reflects all the information of it in the multiple noisy label space. Inspired by label enhancement (LE) [32, 33] , we design a label distribution enhancement (LDE) component for KFNN. LDE recovers a potential label distribution using {x im } M m=1 , and then enhances the multiple noisy label distribution calculated from {l ir } R r=1 by this potential label distribution. Specifically, KFNN first uses majority voting to initialize the integrated label ŷi for x i as follows:EQUATIONwhere p(c q |L i ) can be calculated as follows:EQUATIONHere, p(c q |L i ) reflects the proportion of labels in L i that take the value c q . The function δ(•) outputs 1 if its two parameters are identical, and 0 otherwise. Subsequently, according to ŷi , the crowdsourced dataset D can be divided into Q subsets {D q } Q q=1 . The subset D q contains all instances with initial integrated labels of c q , i.e., D q = {x i |ŷ i = c q } N i=1 . Then, KFNN calculates a Mahalanobis distance distribution {d(x i , D q )} Q q=1 as follows:EQUATIONwhere µ q denotes the centroid of D q and C -1 q denotes the inverse matrix of the covariance matrix of D q . d(x i , D q ) is the Mahalanobis distance from x i to D q calculated in the attribute space. A larger d(x i , D q ) means that x i is less likely to belong to c q , conversely a smaller d(x i , D q ) means that x i tends to belong to c q . Therefore, {d(x i , D q )} Q q=1 can be used to model the relationship between each instance and all classes. Based on this, {d(x i , D q )} Q q=1 can be transformed into a potential label distribution {p(c q |x i , D q )} Q q=1 as follows:EQUATIONwhere max(•) and min(•) denote the maximum and minimum values of the set, respectively.In addition to the potential label distribution, a multiple noisy label distribution {p(c q |L i )} Q q=1 can also be directly transformed from L i . Different from {p(c q |x i , D q )} Q q=1 , which learns the potential relationship between instances and classes from the attribute space, {p(c q |L i )} Q q=1 learns the label distribution reflected by noisy labels from the multiple noisy label space. Finally, KFNN fuses them into an enhanced label distribution P i = {p iq } Q q=1 by averaging as follows:EQUATIONIn this way, the enhanced label distribution P i can fuse the information from the attribute space and the multiple noisy label space. Therefore, the first part of Problem 1 has been addressed.After obtaining P i by label distribution enhancement, KFNN proceeds to determine the optimal neighborhood size K * i for x i . First, KFNN calculates the distance between each pair of instances x 1 and x 2 by:EQUATIONwhere d(x 1 , x 2 |D q ) can be calculated as follows:EQUATIONCompared to the Euclidean distance, Eq. ( 6) introduces the label information by calculating the distance between x 1 and x 2 on each subset D q . According to Eq. ( 6), we can calculate distances between x i and all instances in D. By sorting these distances we can obtain a neighbor sequence< x 1 i , . . . , x k i , . . . , x N i > for x i . Here, x k i is the k-th neighbor instance of x i satisfying d(x i , x k i ) ≥ d(x i , x k-1 i) when k greater than 1. Then, we calculate the weight w ik for x k i as follows:EQUATIONwhere l ikr denotes the label of x k i annotated by the r-th worker u r . w ik reflects the proportion of workers assigned the same label for x i and x k i . Subsequently, x i is allowed to absorb the enhanced label distributions of neighbor instances in the neighbor sequence one by one. LetP k i = {p k iq } Q q=1denote the label distribution of x i after absorbing x k i , which can be updated as follows:EQUATIONwhere p ikq denotes the probability value corresponding to c q in the enhanced label distribution of x k i . Since the first neighbor instance of x i is itself, P k i = P i when k is equal to 1. According to P k i , KFNN calculates a class margin as follows:EQUATIONwhere sec(•) denotes the second-largest value of the set. Since the true labels are unknown, Eqs.(5) (7) ( 8) are all designed based on multiple noisy labels, which lead to that M k contains a degree of noise incurred by neighbor instances. Therefore, KFNN designs a Kalman filter to mitigate the impact of noise in M k as follows:EQUATIONwhere Mk denotes the filtered margin, determined by both the estimated margin Mk and the calculated margin M k . The designed Kalman filter can be divided into an estimation phase and an update phase. In the estimation phase, the filter estimates Mk and the estimated error P - k based on the filtered margin Mk-1 and error P k-1 of the previous time index. In the update phase, the filter first updates the Kalman gain K k of the k-th time index and then updates Mk and error P k of the k-th time index according to K k . α and β are the process error and the measurement error in the Kalman filter. When k is equal to 0, Mk takes the value of 0 and P k takes the value of 1.To address the second part of Problem 1, KFNN determines the optimal neighborhood size K * i for x i by the max-margin learning as follows:EQUATIONUltimately, according to K * i , KFNN updates the integrated label ŷi for x i as follows:EQUATIONThe whole learning process of KFNN is shown in Algorithm 1. In Algorithm 1, lines 1-3 initialize the integrated label and multiple noisy label distribution for each instance and their time complexity is O(N QR). Line 4 divides the crowdsourced dataset D into Q subsets and its time complexity is O(N Q). Lines 5-9 perform label distribution enhancement and their time complexity is O(N M 2 Q). Line 11 calculates the distances from x i to other instances and sorts these distances, its timecomplexity is O(N M 2 Q + N log(N )). Lines 12-16 calculate the margins { M k } N k=1 and their time complexity is O(N R + N Q). Line 17 filters the margins { M k } N k=1and its time complexity is O(N ). Line 18 determines the optimal neighborhood size and its time complexity is O(N ). Line 19 infers the integrated label for each instance and its time complexity is O(Q). Therefore, the time complexity of lines 10-20 is O(N 2 (M 2 Q + log(N ) + R)). If only the highest order terms are taken, the timecomplexity of KFNN is O(N (N M 2 Q + N log(N ) + N R + QR)).Algorithm 1 The learning process of KFNNRequire: D = {(x i , L i )} N i=1 -a crowdsourced dataset; α, β -the predefined parameters Ensure: {ŷ i } N i=1 -the integrated labels 1: for i = 1 to N do 2:Initialize ŷi and {p(cEQUATIONTransform {d(x i , D q )} Q q=1 into {p(c q |x i , D q )} Q q=1 by Eq. (4)8:Fuse {p(c q |x i , D q )} Q q=1 and {p(c q |L i )} Q q=1 into P i = {p iq } Q q=1 by Eq. (5) 9: end for 10: for i = 1 to N do 11:Calculate < x 1 i , . . . , x k i , . . . , x N i > for x i by Eqs. (6) (7) 12:for k = 1 to N do 13:Calculate the weight w ik for x k i by Eq. ( 8)14:Update the label distribution P k i by Eq. ( 9)15:Calculate the M k by Eq. (10) 16:end for 17:Filter { M k } N k=1 using the designed Kalman filter by Eq. (11) 18:Determine the optimal neighborhood size K * i for x i by Eq. ( 12)19:Infer the integrated label ŷi for x i by Eq. ( 13) 20: end for 21: return {ŷ i } N i=1 
theoretical analysis: 
 In this section, we provide some detailed theoretical analysis for KFNN. First, in Eq. ( 6), KFNN defines the distance d(x 1 , x 2 ) between x 1 and x 2 based on the Mahalanobis distance d(x 1 , x 2 |D q ) rather than the traditional Euclidean distance d E (x 1 , x 2 ). According to Eqs. (3) (7), the Mahalanobis distance works based on a basic assumption, which can be described as follows: Assumption 1. Given the subset D q , its covariance matrix C q is a nonsingular matrix.The Assumption 1 holds based on the condition that |C q | is non-zero, which is usually satisfied. Even if this condition is not satisfied, we can ensure that the Assumption 1 holds by adding a small value to each element of the principal diagonal on C q until |C q | is non-zero.Theorem 1. If Assumption 1 holds, there will be an orthogonal matrix P satisfying that P -1 C q P = P T C q P = Λ, where Λ is a diagonal matrix with all M eigenvalues of C q as its elements of the principal diagonal.Due to the limited pages, the proof of Theorem 1 is provided in Appendix A. Based on Theorem 1, we can obtain some interesting corollaries about Eqs. (3) (6) (7) . Corollary 1. Compared to d E (x 1 , x 2 ), d(x 1 , x 2 ) in Eq. (6) does not suffer from the correlation and magnitude of attributes.Proof. According to Theorem 1, d(x 1 , x 2 |D q ) can be transformed as follows:EQUATION)When Λ -1 is not considered, the derivation of Eq. ( 14) implies that d(x 1 , x 2 |D q ) is the Euclidean distance of instances after orthogonal transformation using P T . After orthogonal transformation, the attributes are independent of each other, so d(x 1 , x 2 ) does not suffer from the correlation of attributes.Λ -1 is equivalent to diag( 1 λ1 , 1 λ2 , . . . , 1 λ M ), where λ M is the M -th eigenvalue of C q and is equal to the variance on the direction of the corresponding eigenvectors. Briefly, Λ -1 ensures that the calculated result on each dimension is normalized by the corresponding variance when calculating the distance by Eq. ( 7). Therefore, d(x 1 , x 2 ) does not also suffer from the magnitude of attributes. 6) provides a smaller distance for x 1 and x 2 coming from the same class.Corollary 2. Compared to d E (x 1 , x 2 ), d(x 1 , x 2 ) in Eq. (Proof. P T causes the original attribute space to be rotated according to the direction of the eigenvectors of C q , and Λ -1 causes the rotated attribute space to be scaled according to the eigenvalues C q . Referring to the principle of principal component analysis [34] , the eigenvectors of C q reflect the principal component directions of D q . This means that d(x 1 , x 2 ) will provide a smaller distance for instances coming from the same class compared to d E (x 1 , x 2 ).Assumption 2. When we estimate Mk based on Mk-1 , the estimated error satisfies N(0, P - k ). When we measure M k by Eq. (10), the measurement error satisfies N(0, β).The Kalman filter we designed as Eq. ( 11) works based on Assumption 2, which usually holds because the noise in practice usually satisfies a normal distribution. Since Mk-1 changes in each time index, the variance of the estimated error P - k changes with the time index. Since Eq. ( 10) remains constant, the variance of the measurement error β is constant. According to Assumption 2, the following theorem can be proved: Theorem 2. When the Kalman gain K k takes the valueP - k P -k +β , the error between the filtered margin Mk and the true margin M k is minimized.Mk = M- k + K k * ( M k -M- k ), it can be proved that minimizing the error between Mk and M k is equivalent to minimizing the variance of Mk . Since Mk and M k are independent of each other, the following equation can be derived:EQUATIONwhere V ar(•) denotes the variance of the variable. According to Assumption 2, V ar( Mk ) equals to P - k and V ar( M k ) equals to β. To minimize the error between the filtered margin Mk and the true margin M k , we can calculate the partial derivative ∂V ar( Mk )∂K k as follows:∂V ar( Mk )EQUATIONUltimately, it can be proved that K k is equal toP - k P - k +β by setting ∂V ar( Mk )∂K k to 0.Theorem 3. The larger Mk is, the better the corresponding neighborhood size k is.Theorem 3 ensures the effectiveness of KFNN in determining the optimal neighborhood size by the max-margin learning, and its proof is provided in Appendix B due to the limited pages.5 Experiments 
experimental setup: 
 To evaluate the effectiveness of KFNN, we construct extensive experiments on the whole 34 simulated and two real-world crowdsourced datasets published on the Crowd Environment and its Knowledge Analysis (CEKA) [35] platform. For simulated datasets, we first use the unsupervised attribute filter ReplaceMissingValues in the Waikato Environment and Knowledge Analysis (WEKA) [36] platform to replace all missing values. Subsequently, with the CEKA platform, we hide true labels of simulated datasets and simulate five workers whose label qualities are randomly generated from a normal distribution with N(0.65, 0.05 2 ) to annotate these datasets. The real-world datasets, Income and Leaves, which were both collected from the online platform Amazon Mechanical Turk (AMT), can be used directly without any processing since they do not contain missing values.We compare our KFNN with six state-of-the-art label integration algorithms. Among them, MV (majority voting) [11] is the simplest label integration algorithm and is used as a baseline for all algorithms. IWMV (iterative weighted majority voting) [22] , AALI (attribute augmentation-based label integration) [29] , and LAGNN (label aggregation with graph neural networks) [9] are three state-of-the-art label integration algorithms that do not leverage neighbor instances. LAWMV (label augmented and weighted majority voting) [13] and MNLDP (multiple noisy label distribution propagation) [1] are two state-of-the-art label integration algorithms that leverage neighbor instances.For MV, we use the existing implementation of the CEKA platform. For IWMV, AALI, LAGNN, LAWMV, and MNLDP, we use the implementations provided by their authors. All parameters of the comparison algorithms are set to the recommended values in the corresponding published papers. In addition, since true labels are unknown in our experiments, we use the lazy version of LAGNN. In our KFNN, α and β are set to 0.1 and 1 by default.The performance of each algorithm is evaluated using the Macro-F1 score, which highlights the performance of algorithms on different classes and better reveals algorithmic limitations compared to traditional integration accuracy. Due to the limited pages, more detailed descriptions of the experimental datasets and metrics are provided in Appendix C. All experiments are independently repeated ten times on a Windows 10 machine with an AMD Athlon(tm) X4 860K Quad Core Processor @ 3.70 GHz and 16 GB of RAM, and we report the average results of ten experiments.Simulation experiment results. Table 1 shows the detailed Macro-F1 score (%) comparisons of each label integration algorithm on each simulated dataset, respectively. Based on these results, we perform the Wilcoxon signed-rank test [37] to further compare each pair of algorithms. Table 3 summarizes the Wilcoxon test results. In Table 3 , the symbol • indicates that the algorithm in the row significantly outperforms the algorithm in the corresponding column, the symbol • indicates the exact opposite of that indicated by the symbol •, and the missing item indicates no significant difference between the algorithm in the row and the algorithm in the column. The significance levels of the lower and upper diagonals are α = 0.05 and α = 0.1, respectively. Based on these experimental results, we can summarize the following highlights: 1) The average Macro-F1 score of KFNN on all datasets is 79.64%, which is much higher than those of MV (72.46%), IWMV (72.71%), AALI (72.95%), LAGNN (73.71%), LAWMV (73.44%) and MNLDP (76.68%). KFNN achieves the highest Macro-F1 - • • • • • IWMV • - • • • • AALI • • - • • LAGNN • • - • • LAWMV - • MNLDP • • • • - • KFNN • • • • • • - Table 4:The integration accuracy (%) comparisons using Wilcoxon tests for KFNN versus its comparison algorithms.MV IWMV AALI LAGNN LAWMV MNLDP KFNN MV - • • • • • • IWMV • - • • • • • AALI • • - • • • • LAGNN • • • - • • • LAWMV • • • • - • MNLDP • • • • • - KFNN • • • • -score, which indicates that KFNN is more effective and robust than these comparison algorithms in various crowdsourcing scenarios. 2) Among all comparison algorithms of KFNN, MNLDP performs better than IWMV, AALI and LAGNN, which demonstrates the advantages of leveraging neighbor instances. 3) Based on the Wilcoxon test results, KFNN significantly outperforms all comparison algorithms, which strongly validates the effectiveness and robustness of KFNN. Besides, we also observe the experimental results in terms of the integration accuracy, which are shown in Tables 2 and 4 . According to Tables 2 and 4 , we can see that KFNN can also achieve better or comparable integration accuracy compared with these state-of-the-art label integration algorithms. These results again validate the effectiveness and robustness of KFNN.Real-world experiment results. Compared to simulated crowdsourced datasets, real-world crowdsourced datasets may include some special factors that influence label integration to work effectively, such as sparsity and bias. Therefore, we further observe the performance of KFNN and its comparison algorithms on two real-world datasets, Income and Leaves. Figure 1 shows the detailed Macro-F1 score (%) and integration accuracy (%) comparisons of each label integration algorithm on Income and Leaves, respectively. As can be seen from Figure 1 , compared to these state-of-the-art label integration algorithms, our KFNN achieves the highest integration accuracies and Macro-F1 scores on both Income and Leaves. These results strongly support the effectiveness of our KFNN.Parameter sensitivity analysis. There are two parameters α and β that can be adjusted in the Kalman filter designed by KFNN. To observe the effect of these two parameters on the performance of KFNN, we perform the parameter sensitivity analysis for KFNN on Income and Leaves. We change both α and β from 0.1 to 1 and then observe the Macro-F1 score of KFNN on two datasets. Figure 1 : The Macro-F1 scores (%) and integration accuracies (%) of KFNN and its comparison algorithms on the Income and Leaves datasets.Figure 2a and Figure 2b show the Macro-F1 score of KFNN on Income and Leaves when α and β vary. Based on these results, we can find that KFNN is more sensitive to β compared to α. As β tends to 1, KFNN tends to achieve optimal performance. Therefore, the default value of β in this paper is set to 1. α hardly affects the performance of KFNN, which is set to 0.1 by default. Ablation experiment. There are two components in KFNN, namely label distribution enhancement (LDE) and K-free optimization (KF). To validate their effectiveness, we observe the Macro-F1 score of KFNN after taking away each component on the Income dataset. For simplicity, we use "KFNN-KF" to denote the variant of KFNN after taking away the component KF. Similarly, we create its another two variants "KFNN-LDE" and "KFNN-KF-LDE". Based on the results shown in Figure 3a , it can be seen that the performance becomes worse when any component is taken away. These results validate the effectiveness of LDE and KF. Figure 3b shows the change of the class margin before and after using our designed Kalman filter (observed on the first instance of Income). As can be seen from Figure 3b , compared to the margin before filter ( M k ), the filtered margin ( Mk ) changes smoother. These results validate the effectiveness of our designed Kalman filter, which successfully mitigates the impact of noise incurred by neighbor instances.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: This paper provides open access to the data and code, and provides a document to guide readers in reproducing all experimental results in supplemental material. Guidelines:• The answer NA means that paper does not include experiments requiring code. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
conclusion and future work: 
 To ensure that each instance in crowdsourced datasets has a free neighborhood size, we propose a novel algorithm called KFNN. KFNN consists of two key components, namely label distribution enhancement and K-free optimization. Label distribution enhancement fuses the information from the attribute space and the multiple noisy label space. K-free optimization automatically determines the optimal neighborhood size for each instance by the max-margin learning. Both theoretical analysis and experimental results validate the effectiveness and robustness of KFNN.Nevertheless, there are still some limitations in KFNN that can be improved in the future. For example, the parameters α and β in the Kalman filter designed by KFNN can not automatically adapt to the dataset, which restricts the robustness of KFNN. In addition, in Eq. ( 4), transforming the distance distribution into the potential label distribution using max-min normalization is rough. Considering that the distance metric is not effective across all datasets (e.g., autos and breast-cancer in Table 1 ), this transformation may also lead to KFNN performing poorly. In the future, we will design more sophisticated parameters and transformations to improve KFNN. Justification: We clearly claim in the abstract and introduction section that the KFNN proposed in our paper is mainly used to improve the effectiveness and robustness of label integration in crowdsourcing. The contributions of our paper are also highlighted in the introduction.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: The new algorithm proposed in this paper helps to improve the effectiveness and robustness of label integration. There are no negative societal impacts.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix:  


Decision: This paper proposes a novel label integration approach KFNN by adaptively determining the optimal neighborhood size. KFNN utilizes a Mahalanobis distance distribution to model the relationship between each instance and all classes.  The reviewers have reached a consensus to accept this paper.  Please follow the reviewers' suggestions to polish the main paper.

Reviews: review: paper_summary: paper_summary: This paper introduces a new algorithm for label integration called KFNN. Existing methods related to KNN produce more noisy labels; however, they fix the neighborhood size, regardless of the fact that instances close to the center of classes should have more neighbors than instances close to the boundary of classes. To tackle this problem, KFNN estimates a Mahalanobis distance distribution between each instance and all classes to enhance the multiple noisy label distribution and utilizes a Kalman filter to mitigate the impact of noise. Finally, KFNN can automatically determine the optimal neighborhood size through max-margin learning.
strength_weakness: strength_weakness: W1. The motivations need more enhancements.   
W2. Some technical details require more explanations.   
W3. The application scope of the proposed method in crowdsourcing is limited.    
W4. The performance improvement of the proposed method is unsatisfactory.    
W5. Experiments are conducted in a simulation environment, which can be much simpler than a real-world crowdsourcing platform.
questions: questions: D1. The paper focuses on the KNN-related methods for label integration. However, the introduction didn’t justify the motivation of this concentration with convincing proofs. For instance, the motivation is basically explained with the sentence, “to alleviate this problem, recent works have begun to focus on leveraging neighbor instances [1, 11, 12] …”. However, there are also alternatives for label integration, so why considers KNN-related instead of the other types of solutions? Besides, there are much more studies (eg [R1]) that also target on this problem, which should be carefully discussed their pros and cons. Otherwise, the motivation looks weak.

D2. From the perspective of crowdsourcing, the studied problem is closely related to “truth inference”. However, in the references, there are only two papers on this topic: [25] (published in 2016) and [26] (published in 2023). More studies, which can be easily found in Google Scholar or DBLP, should be reviewed and compared (if possible).

D3. It is a little unclear how the principle of employing the same neighborhood size can impact performance. Please give more explanations.

D4. In addressing the question of fusing information from the attribute space and the multiple noisy label space, this paper tends to take an average between the multiple noisy label distribution and the potential label distribution. However, it might be worth exploring the possibility of introducing a tunable parameter to achieve a more optimal balance between these two distributions, rather than relying solely on an equal (50%) average. 

D5. The application scope of the proposed method in crowdsourcing is limited. In my opinion, the proposed KFNN can be only used in simple and micro tasks in crowdsourcing, there are many other kinds of tasks in a real-world crowdsourcing platform, such as ranking [R2], which is not considered in the problem setting. Yet, the title, “KFNN: K-Free Nearest Neighbor For Crowdsourcing”, is a little over-claimed. At least, the paper should explicitly define the application scope. More types of crowdsourcing task can be found in existing surveys [R3, R4] on crowdsourcing.

D6. The performance improvement of the proposed method is unsatisfactory.    
(1) Although the average Macro-F1 score of KFNN is better than the compared baselines, it can be notably worse than some of the baselines in certain datasets (eg MNLDP on the anneal dataset). This pattern weakens the motivation, since it’s unclear whether the limitation of existing solutions has been well addressed or not.   
(2) In Table 2, the integration accuracy of KFNN is lower than that of MNLDP. Besides, it can be also notably worse than some of the baselines in terms of the integration accuracy (eg LAGNN and LAWMV on the breast-cancer dataset).   
(3) Based on the current experimental results, the effectiveness of the proposed solution KFNN is questionable.

D7. Although several datasets are conducted in the experimental study, existing work on truth inference in crowdsourcing (eg [R2, R5]) usually deploys their solution in a real-world platform, such as AMT, to verify the performance. Therefore, the setup of the experimental study can be simplifier and less practical than the real-world scenario.

References:  
[R1] Adaptive Integration of Partial Label Learning and Negative Learning for Enhanced Noisy Label Learning. AAAI 2024.   
[R2] Xi Chen et al. Pairwise ranking aggregation in a crowdsourced setting. WSDM 2013.   
[R3] Guoliang Li et al. Crowdsourced Data Management: A Survey. IEEE TKDE 2016.   
[R4] Hector Garcia-Molina et al. Challenges in Data Crowdsourcing. IEEE TKDE 2016.   
[R5] Yudian Zheng et al. Truth Inference in Crowdsourcing: Is the Problem Solved? VLDB 2017.
limitations: limitations: Please refer to the weaknesses and questions.
paper_summary: paper_summary: This paper proposes a novel label integration approach KFNN by adaptively determining the optimal neighborhood size. KFNN utilizes a Mahalanobis distance distribution to model the relationship between each instance and all classes. The authors also provide adequate theoretical analysis to illustrate the effectiveness of the proposed method. Experiments demonstrate that the proposed method can achieve the state-of-the-art performance on simulation and real-world dataset. The paper is well-written and easy to follow. This idea is very intuitive and effective for crowdsourcing task. The paper proves the effectiveness of introducing Mahalanobis distance distribution for crowdsourcing from the perspective of methodology, theory and experiments.
strength_weakness: strength_weakness: 1. In section 2, the authors introduce two categories of label integration algorithms. And the proposed KFNN belongs to the algorithms which leverage neighbor instance. I suggest adding some discussion about the pros and cons of these two categories of approaches.
2. In methodology part and theoretical analysis part, the authors discuss the superiority of Mahalanobis distance compared with Euclidean distance. Can the authors verify the difference between Mahalanobis distance and Euclidean distance on this task from an experimental perspective?
3. In Table 3 and Table 4, why some results are missing? Appropriate explanation facilitates reading of the paper.
questions: questions: Please refer to weakness. My biggest concern is the experiments for the comparison between Mahalanobis distance and Euclidean distance.
limitations: limitations: yes
paper_summary: paper_summary: The paper presents a novel label integration algorithm, KFNN (K-Free Nearest Neighbor), designed to enhance the performance of crowdsourcing platforms by intelligently determining the optimal neighborhood size for each instance based on its attributes and noisy labels. The authors propose a two-component solution involving label distribution enhancement and K-free optimization, which leverages the Mahalanobis distance and a Kalman filter to mitigate noise from neighbor instances. The paper's claims are well-aligned with the theoretical and experimental results, demonstrating the effectiveness and robustness of KFNN against existing state-of-the-art algorithms in various crowdsourcing scenarios.
strength_weakness: strength_weakness: 1.	Simulation experiment results
The symbol • indicates that the algorithm in the row significantly outperforms the algorithm in the corresponding column. How is "significantly outperforms" defined for Macro-F1 score and integration accuracy?

2.	Ablation experiment results
Since this study focuses on automatically adjusting neighborhood sizes, how does the performance of this method compare with baselines that use fixed neighborhood sizes?
questions: questions: see weaknesses
limitations: limitations: see weaknesses
paper_summary: paper_summary: This paper proposes a novel algorithm, KFNN (K-free Nearest Neighbor), which is specifically designed to enhance label integration for crowdsourcing. KFNN integrates two key components named label distribution enhancement and K-free optimization, which significantly contribute to improving the effectiveness and robustness of the label integration process. The idea of automatically determining the optimal neighborhood size for each instance is particularly innovative and well-executed. The experimental results further validate the effectiveness and robustness of the proposed algorithm.
strength_weakness: strength_weakness: 1. While the paper provides strong theoretical and experimental results, there is limited discussion on the computational efficiency and scalability of the proposed KFNN algorithm. I suggest moving the algorithmic flow and time complexity analysis from Appendix A to the main text.
2. There are some repetitive sentences and structures in this paper that should be further condensed. For example, Sections 5.1 and 5.2 should be merged and the repetitive statements in them should be deleted.
3. The experiments are already comprehensive, but analysis and discussion of the optimal neighborhood size determined by KFNN could still be added, which would help to understand how the neighborhood size should be set. Moreover, according to the results presented in Tables 1-4, KFNN is generally highly effective. However, on few datasets, KFNN does not perform as well as MV. These anomalies are valuable for identifying deficiencies in KFNN and should be further investigated and discussed.
questions: questions: Please refer to the Weaknesses.
limitations: limitations: The authors openly discuss the limitations of their work, particularly the empirical parameters in the Kalman filter and the roughness of the distribution transformation process. Please refer to the Weaknesses for other limitations I have found.

Comments: title: Response to the rebuttal
Response to the author feedback
Response
Response for Rebuttals.
comment: Dear Reviewer MQSy,

Thank you very much for your kindly reply and consideration.

Thanks again.
Dear authors,

I acknowledge your further responses. When discussing with the other reviewers on the final recommendation, I will consider the rebuttal.

Thanks,
**Reviewer MQSy：**

**(1):** Q1 asks whether there are alternatives for label integration that can be used in crowdsourcing. If so, please discuss. Otherwise, please clarify that there are no such alternatives.

**(2):** Q2: thank authors for acknowledging that these two terms are synonymous. That's why ... method instead of the others in Q1.

**Author Response for (1) and (2):** Thanks for your valuable explanations. According to [R3] mentioned by the reviewer, there are alternatives for label integration (also known as answer aggregation or ground truth inference) in crowdsourcing to control the quality of crowdsourced datasets. These include worker modeling, worker elimination, and task assignment. Worker modeling characterizes the quality of workers, worker elimination eliminates low-quality workers and spammers, and task assignment assigns informative tasks to high-quality workers. However, these alternatives do not fully alleviate the impact of insufficient labels in label integration. Additionally, reminded by the comments of the reviewer, we will clarify our motivation and refine the title to "KFNN: K-Free Nearest Neighbor for Label Integration in Crowdsourcing" in the final version of the paper. Thanks again for your valuable comments.

**(3):** Q3 is generally satisfactory.

**Author Response for (3):** Thanks for your appreciative comments.

**(4):** The claims for Q4 should be verified through experimental evaluations.

**Author Response for (4):** Thanks for your valuable explanations. To verify our claims for Q4, we conducted experiments on the real-world crowdsourced dataset Income. According to the weighted version of Eq. (5) provided in the rebuttal, we set $\lambda$ to 0.1, 0.3, 0.5, 0.7, and 0.9, respectively, and then observed the performance of KFNN on the Income dataset. The experimental results are as follows: 
| |λ=0.1|λ=0.3|λ=0.5|λ=0.7|λ=0.9|
|--|--|--|--|--|--|
|F1|77.95|78.07|78.69|77.93|76.19|
|Accuracy|76.33|76.50|77.17|75.83|73.33|
| |

From these results, it can be found that KFNN achieves optimal performance with $\lambda$ set to 0.5 (equal average). Therefore, these experimental results support our claims for Q4. Thanks again for your valuable comments.

**(5):** Q5 asks to clarify the type of crowdsourced task. Notice that, a ranking task ... may need to be refined to avoid over-claiming.

**Author Response for (5):** Thanks for your valuable explanations. According to [R3] mentioned by the reviewer, crowdsourced task types include single choice, multiple choice, rating, clustering, and labeling. Our current version of KFNN can be used for both single choice tasks and labeling tasks. We will clarify the application scope of KFNN in the final version of the paper. Furthermore, we plan to expand KFNN to other task types in the future. Thanks again for your valuable comments.

**(6):** Q6: as shown in the experimental results (Tables 1 and 2), the proposed method ... the optimal among the compared ones.

**Author Response for (6):** Thanks for your valuable explanations. Indeed, the current results show that under certain datasets (1) different methods have their own pros and cons, and (2) the proposed method is not always the optimal among the compared ones. These findings are normal and do not negate the effectiveness of our KFNN. KFNN is not restricted to specific crowdsourcing scenarios, so we conducted experiments on the whole 34 datasets published by the CEKA platform. In fact, no label integration algorithm can always achieve the best performance on all these datasets. Therefore, we performed the Wilcoxon signed-rank test to further compare each pair of algorithms. The statistical test strongly validates the effectiveness of KFNN. Thanks again for your valuable comments.

**(7):**  Q7: thank you for acknowledging that the proposed method has not been verified ...  integrated in a real-world platform or not.

**Author Response for (7):** Thanks for your valuable explanations. In the current version of the paper, both real-world and simulated experiments have been conducted to validate the effectiveness of KFNN. In our real-world experiments, we used the Income dataset and the Leaves dataset, which were collected from the real-world crowdsourcing platform AMT. The collection process of these two datasets is similar to that described in Section 5.2 in [R2]. The experimental results shown in lines 294-301 of our paper validate the effectiveness of KFNN in real-world crowdsourcing scenarios. Due to cost constraints, the number of real-world datasets is limited. Therefore, we also validated the effectiveness of KFNN through statistical tests on a large number of simulated datasets. The results in Tables 1-4 further validate the effectiveness of KFNN. In the final version of the paper, we will provide a more detailed description of the collection of datasets Income and Leaves from the AMT platform. Thanks again for your valuable comments.
Thanks for the author's reply, my concerns have been well explained. I will keep my score.
As the discussion period deadline nears, we would be deeply appreciative if you could kindly review our rebuttal and let us know if we have addressed your concerns. We’re more than happy to continue the conversation if you have any further questions. Thank you very much for your time and consideration.
Dear authors,

I have read the rebuttal, and thank you for considering my suggestions. Some of my concerns are well addressed, and the others aren't:

(1) Q1 asks whether there are alternatives for label integration that can be used in crowdsourcing. If so, please discuss. Otherwise, please clarify that there are no such alternatives.

(2) Q2: thank authors for acknowledging that these two terms are synonymous. That's why I have asked whether there are alternatives for the studied problem. As reviewed in the seminal survey work published in [R3], there are other options for this problem. Based on this reason, I have asked the authors to enhance the motivation of using KNN-based method instead of the others in Q1.

(3) Q3 is generally satisfactory.

(4) The claims for Q4 should be verified through experimental evaluations.

(5) Q5 asks to clarify the type of crowdsourced task. Notice that, a ranking task in crowdsourcing still requires label integration (or ground truth inference). Thus, it is important to clearly define the application scope. From the current form of submission, the proposed method might be limited to only limited tasks types instead of general tasks in crowdsourcing. If this is the fact, the title and some other contents may need to be refined to avoid over-claiming.

(6) Q6: as shown in the experimental results (Tables 1 and 2), the proposed method could perform worse than the selected baselines in either Macro-F1 score and integration accuracy under certain datasets by a large margin. Based on the current results, it seems that (1) different methods have their own pros and cons, and (2) the proposed method is not always the optimal among the compared ones.

(7) Q7: thank you for acknowledging that the proposed method has not been verified by a real-world platform like AMT. Existing studies on crowdsourcing often conduct evaluations on a real-world platform, such as CrowdFlower (see Section 5.2 in [R2]), since real-world scenarios are more complex than a simulated experiment. Besides, the evaluation can be conducted under the double blind policy. Based on the current evaluations, it is unclear whether the proposed method can be effectively integrated in a real-world platform or not.

Overall, I appreciate the efforts made in the rebuttal. I will take your responses into consideration when making my final decision.

Best regards,
Thanks for your reply. Please incorporate some of the discussion into the final paper.
Thank you for the helpful response that addressed my concern.