Asking the Right Questions to the Right Users: Active Learning with Imperfect Oracles

Shayok ChakrabortyAAAI 2020 · OpenReview

Abstract: Active learning algorithms automatically identify the salient and exemplar samples from large amounts of unlabeled data and tremendously reduce human annotation effort in inducing a machine learning model. In a traditional active learning setup, the labeling oracles are assumed to be infallible, that is, they always provide correct answers (in terms of class labels) to the queried unlabeled instances. However, in real-world applications, oracles are often imperfect and provide incorrect label annotations. Oracles also have diverse expertise and while they may be noisy, certain oracles may provide accurate annotations to certain specific instances. In this paper, we propose a novel framework to address the challenging problem of active learning in the presence of multiple imperfect oracles. We pose the optimal sample and oracle selection as a constrained optimization problem and derive a linear programming relaxation to select a batch of (sample-oracle) pairs, which can potentially augment maximal information to the underlying classification model. Our extensive empirical studies on 9 challenging datasets (from a variety of application domains) corroborate the usefulness of our framework over competing baselines.

Introduction

Active Learning (AL) is a powerful strategy for training machine learning models with minimal human effort. Instead of labeling a massive dataset upfront, the algorithm "queries" a human (an oracle) to label only the most useful examples. However, traditional AL makes two risky assumptions: that the oracle is infallible and that queries are processed serially. In reality, crowdsourcing platforms like Amazon Mechanical Turk provide labels with varying degrees of noise, and serial processing is inefficient for large-scale applications.

This paper introduces a novel Batch Mode Active Learning (BMAL) framework that simultaneously selects the most informative data samples and the best "imperfect" oracles to annotate them. By modeling oracle expertise as instance-specific and formulating the selection as a solvable linear programming problem, the authors significantly reduce the cost and error associated with training models on noisy, real-world data.

Methodology

The proposed framework balances four key criteria to optimize the selection of (sample, oracle) pairs:

  1. Informativeness: Using Shannon’s entropy to find samples where the current model is most uncertain.
  2. Redundancy: Ensuring the selected batch contains diverse samples (using cosine similarity) so the budget isn't wasted on near-identical data points.
  3. Oracle Error Probability: Expertise is modeled as local; an oracle might be an expert in one part of the data space but noisy in another. The system trains a Logistic Regression model for each oracle to predict their likelihood of mislabeling a specific instance.
  4. Labeling Cost: The framework accounts for the fact that more accurate oracles are typically more expensive, seeking a cost-effective balance.

A key contribution is the mathematical proof that this complex, quadratic binary optimization problem can be relaxed into a Linear Programming (LP) problem. This allows the framework to be solved efficiently using standard solvers, making it practical for real-world deployment.

Experimental Evaluation

The framework was evaluated on 9 diverse datasets spanning multiple domains, including Computer Vision (MNIST, SVHN, CIFAR-10, VidTIMIT), Affective Computing (MindReading, MMI), and General/Medical fields (Spambase, Sensor, Breast Cancer). Five different oracles were simulated for each dataset using various classification models to represent diverse levels of expertise.

Test accuracy on the CIFAR-10 dataset, showing the proposed method's performance against baselines.

Results and Discussion

Across all 9 datasets, the proposed method consistently outperformed state-of-the-art baselines like CEAL and MLAL, reaching higher test accuracy with fewer iterations.

Comprehensive results across all 9 datasets demonstrate the consistent superiority of the proposed framework.

Key insights from the results include:

  • Superior Accuracy: The method achieves faster convergence and higher final accuracy by "asking the right person."
  • Effective Oracle Selection: In 7 out of 9 datasets, the framework achieved the highest labeling accuracy, successfully identifying which oracle was most likely to provide the correct ground truth for a given query.
  • Cost-Awareness: By selecting the most cost-effective oracle for each sample, the system preserves the "expert budget" for the most challenging cases.

Conclusion

This work provides a robust solution for active learning in the presence of multiple, imperfect, and costly oracles. By bridging the gap between theoretical AL and practical crowdsourcing workflows, the proposed BMAL framework offers a scalable approach to high-quality data annotation. Future research will focus on extending this framework to multi-label learning and handling dynamic oracle costs.

Summary updated

Abstract

Active learning algorithms automatically identify the salient and exemplar samples from large amounts of unlabeled data and tremendously reduce human annotation effort in inducing a machine learning model. In a traditional active learning setup, the labeling oracles are assumed to be infallible, that is, they always provide correct answers (in terms of class labels) to the queried unlabeled instances. However, in real-world applications, oracles are often imperfect and provide incorrect label annotations. Oracles also have diverse expertise and while they may be noisy, certain oracles may provide accurate annotations to certain specific instances. In this paper, we propose a novel framework to address the challenging problem of active learning in the presence of multiple imperfect oracles. We pose the optimal sample and oracle selection as a constrained optimization problem and derive a linear programming relaxation to select a batch of (sample-oracle) pairs, which can potentially augment maximal information to the underlying classification model. Our extensive empirical studies on 9 challenging datasets (from a variety of application domains) corroborate the usefulness of our framework over competing baselines.
BibTeX
@inproceedings{chakraborty2020asking,
  author = {Shayok Chakraborty},
  title = {{Asking the Right Questions to the Right Users: Active Learning with Imperfect Oracles}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=FgAdU6YRu-C3},
}
Figure