Enhanced Nearest Neighbor Classification for Crowdsourcing

Jiexin Duan, Xingye Qiao, Guang ChengarXiv 2022 · DOI · arXiv

Introduction

Crowdsourcing platforms have become indispensable for generating the massive labeled datasets required by modern machine learning. However, the low cost of platforms like Amazon Mechanical Turk often comes at the price of label quality. "Crowd" labels are inherently noisy, reflecting the varying expertise, biases, and attention spans of individual workers.

Standard non-parametric tools, such as the $k$-Nearest Neighbor ($k$NN) classifier, are poorly equipped for this environment because they assume training labels are largely accurate. While existing solutions attempt to mitigate this noise, they often rely on expensive "expert-labeled" gold standards or restrictive prior assumptions about data distribution. This paper introduces the Enhanced Nearest Neighbor (ENN) classifier, a robust non-parametric method designed to achieve expert-level performance using only noisy crowdsourced data.

The ENN Framework

The core innovation of the ENN algorithm is its ability to "denoise" labels mathematically before classification. The framework operates in three distinct stages:

  1. Label Enhancement: The authors model worker quality using a "two-coin model," defined by sensitivity ($a^j$) and specificity ($b^j$). By applying a specific transformation to the noisy labels, the algorithm "enhances" them, effectively shifting the observed labels back toward the latent ground truth.
  2. Local Estimation: For each worker, the algorithm calculates a local Weighted Nearest Neighbor (WNN) regression estimator based on their specific contributions.
  3. Weighted Aggregation: The final classification is determined by a weighted vote across all $s$ workers, ensuring that higher-quality contributors have a greater influence on the final output.

Handling Unknown Worker Quality

In practical scenarios, worker quality ($a^j, b^j$) is rarely known. The authors propose two variants to address this:

  • ENN2: Utilizes a small subset of expert-labeled data to calibrate worker quality estimates.
  • ENN3: Employs an iterative algorithm that requires no expert data. It functions similarly to an Expectation-Maximization (EM) approach, starting with the assumption that all workers are reliable and iteratively refining worker quality estimates based on the consensus of the crowd.

Theoretical Contributions: The "Oracle" Property

The most significant theoretical finding of this research is the "Oracle" property. The authors prove that ENN achieves the same optimal convergence rate—or "regret"—as a classifier trained on perfect, expert-labeled data. This means that as the dataset grows, the performance gap between ENN (trained on noise) and an ideal classifier (trained on truth) vanishes.

Additionally, the authors identified a technical "sample size floor." They demonstrated that if the number of samples assigned to each worker is too small relative to the total data size, the resulting bias and variance become too large to maintain optimal performance. This provides a vital practical guideline for researchers on how to distribute tasks effectively in a crowdsourcing campaign.

Empirical Evaluation

The authors validated ENN using both synthetic simulations and real-world benchmarks.

Simulation Results

Testing across various settings—including easy classification tasks and complex bimodal distributions—the results showed that ENN1 (with known quality) and ENN3 (iterative estimation) performed nearly as well as an "Oracle $k$NN." Both versions significantly outperformed a "Naive $k$NN," which simply accepts noisy labels at face value.

Real-World Performance

The method was tested on nine datasets from the UCI Machine Learning Repository (covering medical, biological, and physical data) with simulated noisy workers. ENN3 consistently demonstrated lower error rates compared to established crowdsourcing benchmarks, such as the Dawid-Skene (DS) and LFC methods. The algorithm proved particularly robust in scenarios where worker quality was generally low or highly variable.

Limitations and Future Directions

While ENN provides a powerful framework for binary classification, several avenues for future research remain:

  • Multicategory Extension: The current model is optimized for binary (0/1) labels; extending the enhancement logic to multi-class problems is a logical next step.
  • High-Dimensionality: Like all nearest-neighbor approaches, ENN faces challenges with the "curse of dimensionality" in very high-feature spaces.
  • Adversarial Actors: The model assumes workers are "noisy but well-intentioned." It does not currently account for malicious actors who might intentionally provide incorrect labels.
  • Contextual Quality: Future iterations could account for workers who are experts in specific sub-domains of a dataset but novices in others, moving beyond the assumption of constant worker quality.

Conclusion

The Enhanced Nearest Neighbor classifier represents a significant step forward in non-parametric learning for crowdsourcing. By proving that expert-level accuracy is theoretically and practically achievable without expert data, the authors provide a scalable, cost-effective solution for building high-quality models from imperfect human input.

Summary updated

Abstract

In machine learning, crowdsourcing is an economical way to label a large amount of data. However, the noise in the produced labels may deteriorate the accuracy of any classification method applied to the labelled data. We propose an enhanced nearest neighbor classifier (ENN) to overcome this issue. Two algorithms are developed to estimate the worker quality (which is often unknown in practice): one is to construct the estimate based on the denoised worker labels by applying the $k$NN classifier to the expert data; the other is an iterative algorithm that works even without access to the expert data. Other than strong numerical evidence, our proposed methods are proven to achieve the same regret as its oracle version based on high-quality expert data. As a technical by-product, a lower bound on the sample size assigned to each worker to reach the optimal convergence rate of regret is derived.
BibTeX
@misc{duan2022enhanced,
  author = {Jiexin Duan and Xingye Qiao and Guang Cheng},
  title = {{Enhanced Nearest Neighbor Classification for Crowdsourcing}},
  year = {2022},
  eprint = {2203.00781},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2203.00781},
}
Figure