Efficient PAC Learning from the Crowd with Pairwise Comparisons

Shiwei Zeng, Jie ShenICML 2022 · OpenReview

Introduction: The Challenge of Crowdsourced Labels

In the era of big data, machine learning models heavily rely on "the crowd"—platforms like Amazon Mechanical Turk—to annotate massive datasets. However, crowd workers are human: they make mistakes, experience fatigue, and sometimes even act maliciously.

Standard Probably Approximately Correct (PAC) learning, the theoretical backbone of machine learning, traditionally assumes access to a "perfect" teacher. While recent research demonstrates that models can learn from a noisy crowd, doing so typically requires a massive "constant labeling overhead." If a perfect teacher requires $N$ labels to train a model, a noisy crowd might require $10N$ or even $100N$ labels to achieve the same accuracy.

The authors of this paper identify a fundamental psychological reality driving this inefficiency: absolute labels are cognitively demanding. Asking a human to provide an exact rating or a definitive binary label for a complex instance is difficult. Conversely, relative judgments are much easier. It is far simpler for a human to determine that "Movie A is better than Movie B" than to assign Movie A an exact score of 7.4/10. This paper investigates whether these "easier" pairwise comparisons can be leveraged to make crowdsourced learning exponentially more efficient.

Algorithmic Approach: Boosting with Comparisons

To solve this, the authors propose a multi-phase algorithm rooted in Schapire's celebrated 1990 boosting framework. The core concept is to train three "weak" hypotheses and combine them into a single, highly accurate strong classifier. Rather than batching all annotations upfront, the algorithm interleaves learning and annotation, using what it has already learned to dictate which comparisons will be most informative.

The researchers introduce two key algorithmic components to achieve this:

  • COMPARE-AND-LABEL: This routine takes a small subset of data and applies a noisy version of Randomized Quicksort to order the instances based purely on pairwise comparisons. Once the data is sorted, the algorithm uses binary search—requiring only a few absolute label queries—to pinpoint the "threshold" where labels flip from negative to positive. This clever technique allows the algorithm to label an entire dataset while only asking the crowd for a logarithmic number of actual labels.
  • FILTER: Often considered the "secret sauce" of the approach, this algorithm is used to train the second weak hypothesis, which specifically requires examples that the first hypothesis got wrong. Instead of wastefully labeling thousands of points to find these rare errors, the FILTER algorithm uses "support instances" and a handful of comparison queries to identify "hard" examples without ever asking for their true absolute labels.

Key Theoretical Results

Operating within the theoretical PAC learning framework, the authors provide mathematical proofs that hold for any class of threshold functions (such as linear separators or halfspaces) under any data distribution.

The paper yields several breakthrough theoretical results:

  • Exponential Label Savings: The algorithm reduces the number of required absolute labels from the standard $O(1/\epsilon)$ to $O(\text{polylog}(1/\epsilon))$. In practical terms, as the demand for model accuracy increases, the need for expensive absolute labels barely grows.
  • Constant Overall Overhead: Even when factoring in the cost of the pairwise comparison queries, the total "query complexity" remains within a constant factor of the standard PAC model.
  • Adversarial Robustness: The algorithm is highly resilient to malicious actors. It continues to function effectively even if nearly half the crowd (up to a $1/2 - \alpha$ fraction) behaves adversarially, provided the majority remains reliable.
  • Zero Labeling Overhead: The authors prove a label-efficient result where the "labeling overhead" effectively drops to zero ($o(1)$) as the desired error rate decreases. This is the first algorithm to achieve $o(1)$ labeling overhead and $O(1)$ comparison overhead simultaneously for crowdsourced PAC learning of threshold functions.

Limitations and Future Directions

While a significant theoretical step forward, the paper notes a few limitations. First, the current proofs are specifically tailored to threshold functions; extending this framework to more complex hypothesis classes, such as deep neural networks, remains an open challenge. Second, the paper operates in the "realizable" setting, assuming a perfect classifier exists that could theoretically label the data correctly. Adapting this to "agnostic" settings, where data is inherently noisy or overlapping, will require new theoretical approaches.

Finally, the authors suggest that pairwise comparisons are just the beginning. Future work could explore other human-centric query types—such as asking a worker to identify the outlier among three instances—to further optimize the machine learning pipeline.

Summary updated

Abstract

We study crowdsourced PAC learning of threshold function, where the labels are gathered from a pool of annotators some of whom may behave adversarially. This is yet a challenging problem and until ...
BibTeX
@inproceedings{zeng2022efficient,
  author = {Shiwei Zeng and Jie Shen},
  title = {{Efficient PAC Learning from the Crowd with Pairwise Comparisons}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=osKeXmqyPo5},
}
Figure