A comprehensive human computation framework: with application to image labeling

Yang Yang 0059, Bin B. Zhu, Rui Guo, Linjun Yang, Shipeng Li, Nenghai YuACM Multimedia 2008 · DOI

TL;DR

This paper introduces HumanSense, a novel framework that leverages the collective "common sense" of internet users to solve complex problems like image labeling, which are difficult for computers. It addresses challenges like bot detection and answer quality by employing a multi-stage refinement process and a robust ecosystem design.

What Problem Does This Paper Address?

The core problem this paper tackles is the difficulty and cost associated with manually labeling large datasets of images and videos. While computers struggle with tasks requiring common sense (e.g., understanding image content), humans excel at them. However, manual labeling is tedious and expensive, making it impractical for the scale of data generated today. Existing approaches like "games with a purpose" (e.g., ESP game) and CAPTCHAs have limitations: they can be difficult to design for arbitrary problems, require specific user engagement (playing games), or are primarily for security. This paper aims to provide a more general, scalable, and economically viable solution for acquiring human intelligence for common sense tasks.

Methods

The paper proposes a comprehensive Human Computation Framework called HumanSense. Its key components and methods include:

  • Ecosystem Design: HumanSense involves four players: problem providers (seeking solutions), the HumanSense server (managing the process), participating Web sites (hosting the tasks), and Internet users (providing answers). This ecosystem supports various business models, including profit-sharing and integration with existing web services.
  • Problem Representation: Problems are defined by resource files (images, videos) and a manifest file containing metadata like ID, resources, priority, value, and type. This allows for a problem-agnostic system.
  • Incremental Refinement Stages (for Image Labeling):
    1. Candidate Label Collection: Users provide free-form descriptions of objects in an image.
  • Label Refinement & Synonym Correlation: Candidate labels are presented as multiple-choice options. "Trap labels" (semantically unrelated fake labels) are introduced to deter bots and lazy users. Semantic distance (using WordNet) is employed to generate effective trap labels.
  • Object Localization: Users are asked to locate specific objects within a segmented image based on a given label.
  • Bot Detection and Answer Distillation:
    • Bot Removal: A statistical method is proposed to identify and remove spurious answers from bots, assuming bot answers are i.i.d. uniform.
  • Human Answer Distillation: A majority voting scheme is used to combine surviving human answers into a high-quality final solution. This method considers the frequency and relative differences in answer frequencies.
  • Security Mechanisms: The framework incorporates measures to prevent malicious actors (problem providers, web sites, users) from attacking the system or gaining unfair advantages, including using <iframe> isolation and random problem IDs.

Datasets

The paper mentions using the WordNet project for calculating semantic distances between words to generate trap labels. For experimental evaluation, they collected labels from approximately 200 people for five images. They also used bots to generate random labels for comparison. No new benchmark datasets were introduced.

Key Insights and Ideas

  • Leveraging "Common Sense" as a Resource: The paper frames human common sense as a valuable, albeit difficult-to-quantify, resource that can be harnessed for computational tasks.
  • Problem-Agnostic Framework: The design emphasizes a general framework that can handle various common sense problems without needing specific problem-type knowledge upfront, making it highly adaptable.
  • Incentive-Driven Participation: By integrating with existing web services or offering monetary rewards, HumanSense motivates users to contribute, addressing the challenge of maintaining user enthusiasm seen in game-based approaches.
  • Sophisticated Bot Deterrence: The use of "trap labels" generated using semantic distance is a clever way to identify and discard bot-generated answers without requiring explicit bot detection algorithms for every answer.
  • Scalability through Ecosystem: The distributed nature of the framework, involving numerous participating web sites and internet users, allows for massive scalability.

Key Results

The experimental results, though on a small scale (200 people, 5 images), are reported as "very encouraging." The paper demonstrates that:

  • The proposed scheme effectively removes spurious answers from bots. Figure 10 shows that after applying the bot removal procedure, all surviving labels were meaningful words, indicating successful removal of bot-generated gibberish.
  • The combined bot removal and majority voting distillation scheme can produce high-quality image labels. Figure 11 shows that the final labels accurately represent the major objects in the test image.

Limitations and Future Work

  • Experimental Scale: The authors acknowledge that the experiments were conducted on a small scale (about 200 people for five images) and that testing at a much larger scale will require substantial time and effort.
  • CAPTCHA Dependency: While the framework can operate without CAPTCHAs, the paper notes that if CAPTCHAs are used (as in the reCAPTCHA example), it simplifies bot removal as all collected answers are assumed to be from humans.
  • Future Work: The paper implies future work will involve scaling up testing and potentially exploring other types of common sense problems beyond image labeling. The framework's adaptability suggests it could be applied to a broader range of tasks.

Summary updated

BibTeX
@inproceedings{yang2008comprehensive,
  author = {Yang Yang and Bin B. Zhu and Rui Guo and Linjun Yang and Shipeng Li and Nenghai Yu},
  title = {{A comprehensive human computation framework: with application to image labeling}},
  booktitle = {ACM Multimedia},
  year = {2008},
  doi = {10.1145/1459359.1459423},
}
Figure