When majority voting fails: Comparing quality assurance methods for noisy human computation environment

Yu-An Sun, Christopher R. DancearXiv 2012 · OpenReview

Abstract

Quality assurance remains a key topic in human computation research. Prior work indicates that majority voting is effective for low difficulty tasks, but has limitations for harder tasks. This paper explores two methods of addressing this problem: tournament selection and elimination selection, which exploit 2-, 3- and 4-way comparisons between different answers to human computation tasks. Our experimental results and statistical analyses show that both methods produce the correct answer in noisy human computation environment more often than majority voting. Furthermore, we find that the use of 4-way comparisons can significantly reduce the cost of quality assurance relative to the use of 2-way comparisons.

Introduction

In human computation, researchers typically aggregate worker outputs using Majority Voting (MV). While MV is highly effective for simple tasks like image tagging, it frequently breaks down when applied to difficult tasks where the error rate is high. In these "noisy" environments, the correct answer might only be provided by a small minority (10-15%) of workers. Consequently, the majority often converges on a plausible but incorrect answer, such as a literal translation of an idiom rather than its figurative meaning.

This paper addresses the challenge of quality assurance for these complex tasks. The authors hypothesize that while the crowd may struggle to generate a complex correct answer, they are significantly better at recognizing it when presented with a list of options. The goal is to identify an algorithmic approach to surface these "hidden" correct answers efficiently.

Comparison of groundtruth translations versus majority vote results for Chinese idioms, highlighting the failure of majority voting in noisy environments.

Methodology

The study compares three comparison-based selection methods designed to identify the best output from a noisy pool:

  1. Tournament Selection: Items are placed in a pool. In each round, $n$ items are randomly sampled, and a worker selects the best one. The winner advances to the next generation. This repeats until a single item dominates.
  2. Elimination Selection: All items start in a pool. $n$ items are sampled, and a worker picks the best. Every item not selected receives a "loss." Once an item reaches a threshold $T$ of losses, it is eliminated. The process continues until one item remains.
  3. Condorcet Voting (Baseline): A brute-force approach where every possible subset of items is compared, and the item winning the most comparisons is chosen.

The researchers specifically investigated $n$-way comparisons (where $n=2, 3, \text{ or } 4$) to determine if asking workers to choose one-out-of-four is more efficient than standard pairwise matchups.

Experimental Setup

The study utilized two primary datasets collected via CrowdFlower:

  • Chinese Idiom Translation: Five idioms where literal translations are misleading. Each idiom was translated by 30 different workers to create a noisy pool of candidate answers.
  • Logic Puzzles: Three classic brain teasers (e.g., water measurement and probability puzzles).
  • Comparison Data: A set of 1,273 $n$-way comparisons was generated to model worker behavior and fit statistical parameters.

Key Results and Discussion

The experimental results revealed a stark failure of traditional aggregation methods. In the idiom translation task, the error rate for Majority Voting was above 85% for all five idioms, as workers consistently favored literal translations over the ground truth.

In contrast, both Tournament and Elimination methods successfully identified the correct translations. Elimination selection generally outperformed tournament selection because it tracks losses across the entire process, making it more robust against occasional "noisy" judgments from workers in early rounds.

Error rate versus cost (number of matches) for different selection methods and comparison types, demonstrating the efficiency of 4-way comparisons.

A critical finding was the efficiency of higher-order comparisons. Increasing the number of items compared simultaneously from 2 to 4 significantly reduced the total cost (number of tasks paid for) required to reach a correct conclusion without sacrificing accuracy. Simulations showed that 4-way comparison schemes consistently provided a lower error rate than pairwise or 3-way schemes for the same total budget.

Conclusion

When the "wisdom of the crowd" fails to generate correct answers, it can still be harnessed to recognize them. By moving from simple majority voting to comparison-based elimination or tournament selection—particularly using 4-way comparisons—researchers can accurately identify high-quality results in noisy environments at a lower cost. Future work will explore accounting for worker intent and spammers through mixture models and hybridizing these selection methods with gold-standard filtering.

Summary updated

Abstract

Quality assurance remains a key topic in human computation research. Prior work indicates that majority voting is effective for low difficulty tasks, but has limitations for harder tasks. This paper explores two methods of addressing this problem: tournament selection and elimination selection, which exploit 2-, 3- and 4-way comparisons between different answers to human computation tasks. Our experimental results and statistical analyses show that both methods produce the correct answer in noisy human computation environment more often than majority voting. Furthermore, we find that the use of 4-way comparisons can significantly reduce the cost of quality assurance relative to the use of 2-way comparisons.
BibTeX
@misc{sun2012when,
  author = {Yu-An Sun and Christopher R. Dance},
  title = {{When majority voting fails: Comparing quality assurance methods for noisy human computation environment}},
  year = {2012},
  eprint = {1204.3516},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1204.3516},
}
Figure