PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning From Noisy Singly-labeled Data

Ashish Khetan, Zachary C. Lipton, Anima Anandkumar

arXiv:1712.04577v2cs.LG

TL;DR

The paper addresses how to train classifiers from noisy crowdsourced labels while allocating a fixed annotation budget between more examples and repeated annotations. It introduces an alternating method that estimates worker quality and updates a quality-adjusted model, with theory and experiments supporting single labeling when worker quality is sufficiently high.

  • Problem

    Crowdsourced labels are noisy, and redundant annotation reduces the number of labeled examples available under a fixed budget.

  • Method

    An alternating algorithm estimates worker quality from disagreement with model predictions and trains the classifier using a modified loss based on those estimates.

  • Results

    The method estimates worker quality with one label per example, provides generalization guarantees, and finds that one label per example is optimal above a worker-quality threshold.

  • Takeaways & Limitations

    When unlabeled examples are cheap and annotation budget is fixed, collecting single labels for many examples can outperform repeated labeling for fewer examples.

  • Takeaways & Limitations

    The theoretical analysis assumes binary classification, a known uniform class prior, finite VC dimension, and fresh samples across alternating rounds.

Abstract

from arXiv · show

Supervised learning depends on annotated examples, which are taken to be the \emph{ground truth}. But these labels often come from noisy crowdsourcing platforms, like Amazon Mechanical Turk. Practitioners typically collect multiple labels per example and aggregate the results to mitigate noise (the classic crowdsourcing problem). Given a fixed annotation budget and unlimited unlabeled data, redundant annotation comes at the expense of fewer labeled examples. This raises two fundamental questions: (1) How can we best learn from noisy workers? (2) How should we allocate our labeling budget to maximize the performance of a classifier? We propose a new algorithm for jointly modeling labels and worker quality from noisy crowd-sourced data. The alternating minimization proceeds in rounds, estimating worker quality from disagreement with the current model and then updating the model by optimizing a loss function that accounts for the current estimate of worker quality. Unlike previous approaches, even with only one annotation per example, our algorithm can estimate worker quality. We establish a generalization error bound for models learned with our algorithm and establish theoretically that it's better to label many examples once (vs less multiply) when worker quality is above a threshold. Experiments conducted on both ImageNet (with simulated noisy workers) and MS-COCO (using the real crowdsourced labels) confirm our algorithm's benefits.

1 INTRODUCTION

Crowdsourced labels reduce annotation costs but introduce worker noise, while redundant labeling trades more reliable examples for fewer labeled examples. The paper connects worker-quality estimation with downstream supervised learning and develops an approach that can operate without redundant labels.

  • 1 INTRODUCTION: Crowdsourcing makes large annotated datasets affordable but introduces noisier labels than expert annotation.Workers may vary in skill and may prioritize speed because they are paid per answer.
  • 1 INTRODUCTION: Practitioners commonly collect multiple independent labels and aggregate them, often using majority vote, to address variation in worker quality.
  • 1 INTRODUCTION: Crowdsourcing research and machine-learning research often proceed separately, leaving downstream training utility under-addressed.
  • 1 INTRODUCTION: The proposed algorithm alternates between estimating worker quality from disagreement with model predictions and updating the model with a modified loss.
  • 1 INTRODUCTION: The method can estimate worker quality with one label per example when each worker labels sufficiently many examples.
  • 1 INTRODUCTION: The paper provides theoretical guarantees and reports that, under a fixed annotation budget, singly labeling more examples is preferable when worker quality is sufficiently high.

2 RELATED WORK

Prior work aggregates noisy labels, incorporates supervised-learning predictions, studies active annotation, and analyzes repeated labeling, but important differences remain in redundancy requirements, task scope, and modeling assumptions.

  • 2 RELATED WORK: Traditional crowdsourcing methods estimate ground-truth labels by aggregating multiple noisy annotations, using majority voting or agreement-based models.
  • 2 RELATED WORK: Some methods combine noisy labels with supervised-learning predictions, but prior approaches described here may fail with one label per example and focus on binary classification.
  • 2 RELATED WORK: The paper differs by training its model with a weighted loss whose weights are posterior probabilities of the true labels.
  • 2 RELATED WORK: Human-in-the-loop vision work often assumes expert, noiseless annotators, whereas this paper models unreliable workers with varying skills.
  • 2 RELATED WORK: Active-learning approaches filter high-confidence examples and obtain additional labels for difficult examples under varying-difficulty assumptions.
  • 2 RELATED WORK: Studies of repeated labeling relate its usefulness to annotation cost, example cost, worker quality, and classifier expressiveness.
  • 2 RELATED WORK: Noisy-label methods commonly assume a shared noise rate, unlike the worker-specific quality modeling considered here.

3 PROBLEM FORMULATION

The formulation models examples, true labels, worker assignments, and noisy observations, then learns a predictor by minimizing a loss adjusted using estimated worker confusion matrices and label priors.

  • 3 PROBLEM FORMULATION: Examples are drawn i.i.d. from a distribution over features X and true labels Y, with K possible classes.
  • 3 PROBLEM FORMULATION: Each example receives r noisy labels from randomly selected workers, with r denoting redundancy.
  • 3 PROBLEM FORMULATION: Worker quality is represented by a confusion matrix whose diagonal entries give correct-label probabilities and off-diagonal entries give mislabeling probabilities.
  • 3 PROBLEM FORMULATION: The observed training data consist of features, noisy labels, and the worker identities associated with those labels.
  • 3 PROBLEM FORMULATION: The learned predictor minimizes a modified loss based on estimated worker confusion matrices and the estimated prior distribution of true labels.

4 ALGORITHM

The paper’s Model Bootstrapped EM alternates between estimating worker quality from model disagreement and learning a predictor with a posterior-weighted loss. It targets settings with limited annotation redundancy and provides performance guarantees, including when labeling each example once.

  • Model Bootstrapped EM: Model Bootstrapped EM jointly estimates worker confusion matrices and the predictor by alternating between model-based worker estimation and loss minimization.The method replaces hidden labels with model predictions when estimating worker quality, then updates the predictor using a modified loss.
  • Weighted loss: The modified loss weights each example’s possible labels by their posterior probability given noisy observations, worker confusion estimates, and the class prior.It recovers the original loss without noise and becomes identical across predictors when observed labels are uniformly random.
  • Low-redundancy learning: Standard EM has limited use with low redundancy, whereas MBEM estimates worker quality from model predictions even when each example has only one label.Standard EM initialized from majority votes can estimate all workers as perfect in the one-label-per-example setting.
  • Performance guarantees: After two iterations, the theory bounds both the learned predictor’s excess risk and the estimated workers’ confusion-matrix error with probability at least 1 − δ.The bound is stated for binary classification with 0-1 loss and depends on the hypothesis class’s finite VC dimension and total annotations N = nr.
  • Annotation allocation: For a fixed annotation budget, redundancy r = 1 is theoretically optimal when worker quality 1 − ρ is at least 0.825.The analysis also states that confusion-matrix estimation becomes sufficiently accurate with sufficiently many training examples, while experiments observe r = 1 as optimal at lower worker qualities.

5 EXPERIMENTS

Experiments evaluate MBEM on synthetic noisy labels from CIFAR-10 and ImageNet and real MS-COCO annotations. Across varying worker skills, redundancy, and fixed budgets, MBEM performs strongly, especially with singly annotated examples.

  • Experimental setup: MBEM is evaluated on CIFAR-10 and ImageNet with synthetic workers, plus raw crowdsourced annotations from MS-COCO.Synthetic workers follow hammer-spammer or class-wise hammer-spammer skill models.
  • CIFAR-10: On CIFAR-10 with one label per example, MBEM significantly outperforms baselines and closely matches oracle weighted EM.This indicates accurate recovery of worker confusion matrices in the singly annotated setting.
  • CIFAR-10: At small redundancy on CIFAR-10, MBEM substantially outperforms weighted-EM, while standard EM performs comparably when redundancy is large.Weighted-MV and weighted-EM also outperform unweighted MV and EM as redundancy varies.
  • Budget allocation: With a fixed 1.2M annotation budget, MBEM achieves the lowest generalization error using many singly annotated examples.Redundancy ranges from 1 to 9, so higher redundancy reduces the number of available training examples.
  • ImageNet: ImageNet plots distinguish top-5 error with solid lines from top-1 error with dashed lines, comparing MBEM, weighted majority vote, and majority vote.The caption identifies the color mapping for each method.
  • MS-COCO: On MS-COCO, MBEM is compared with majority vote, EM, and ground-truth training using real annotations and 80 independent binary object classifiers.The experiment uses 35K training images, 1K validation images, and 4K test images.

6 CONCLUSION

The paper introduces a noisy-worker learning algorithm and presents theoretical and empirical evidence favoring one annotation per example above a worker-quality threshold. It identifies active query schemes as an avenue for future work.

  • Conclusion: The paper introduces a new algorithm for learning from noisy crowd workers.The conclusion presents this as a central contribution.
  • Conclusion: When examples are cheap and annotations expensive, labeling many examples once is better than labeling fewer examples multiply above a worker-quality threshold.The conclusion describes this insight as supported theoretically and empirically.
  • Future work: Future work includes active query schemes that jointly choose examples and annotators using current knowledge of the data and worker confusion matrices.The proposed extension would route annotations based on both model and worker information.

A PROOF OF THEOREM 4.1

The proof combines bounds for the algorithm’s two alternating steps: learning with the modified loss and estimating worker confusion matrices from model predictions. Applying these lemmas across initialization and subsequent rounds yields the theorem’s stated guarantees.

  • Proof strategy: The analysis treats worker-quality estimation and modified-loss model learning as the two alternating steps requiring separate bounds.The first step estimates confusion matrices from model predictions; the second bounds excess risk when minimizing the modified loss.
  • Model-learning bound: The model-learning lemma bounds excess risk under the posterior distribution, with majority-vote initialization replacing βbπ by α.The guarantee holds with probability at least 1 −δ1 and uses a universal constant C.
  • Worker-quality bound: The confusion-matrix lemma bounds the ℓ∞ error of estimated worker matrices when model predictions are used as ground-truth labels.Its assumptions include n samples, a predictor with bounded risk, and fresh samples for matrix estimation.
  • First round: The first round initializes the model using majority vote and bounds the resulting confusion-matrix estimation error by ϵ.The bound applies when n is sufficiently large so the denominator condition in Equation (18) holds.
  • Second round: In the second round, the posterior replaces majority vote for model learning, after which the confusion-matrix error is bounded by ϵ1.The proof applies the two lemmas again, beginning with an existing ℓ∞ bound of ϵ on the worker estimates.
  • Probability guarantee: Choosing δ1 = δ/4 in both lemmas and applying a union bound gives the theorem’s target probability of error δ.The probability bookkeeping combines the guarantees from the two lemma applications.

A.1 PROOF OF LEMMA A.1

The proof of Lemma A.1 decomposes excess risk under the modified loss into estimation, optimization, and bias terms, then controls the latter through βbπ.

  • Risk decomposition: The proof uses the learned function’s minimization of empirical modified risk and a basic excess-risk bound involving the VC dimension V.The resulting bound also contains a universal constant C and a βbπ-dependent term.
  • Binary case: For binary classification, the 0-1 loss identity ℓ(f(X), Y) + ℓ(f(X), −Y) = 1 controls the comparison between the two class labels.This identity is used in the inequality supporting the excess-risk decomposition.
  • Bias term: The modified-loss bias is expressed as an expectation weighted by βbπ(Y) over the difference between losses for Y and −Y.When weighted majority vote is used, βbπ(Y) is replaced by α(y).

A.2 PROOF OF LEMMA A.2

The proof of Lemma A.2 bounds confusion-matrix estimation error by concentrating empirical worker-label counts around their expectations.

  • Setup: The analysis fixes a worker, predicted class, and observed class, then tracks several empirical quantities indexed by these choices.The notation suppresses dependence on worker a and classes k and s for readability.
  • Deviation bounds: Differences between empirical quantities and their expectations are bounded through intermediate quantities using triangle inequalities.Equations (34) and (35) separately control the deviations for A and B.
  • Concentration: The quantity C is a sum of nr independent Bernoulli variables with mean δ/m, so a Chernoff bound controls its deviation.This supplies a high-probability bound uniformly over workers and classes.
  • Concentration: The quantity D is likewise a sum of nr independent Bernoulli variables, with mean πks/(mk), and receives a corresponding Chernoff bound.The resulting control applies for all workers and class pairs with the stated probability.
  • Conclusion: Combining the concentration bounds for intermediate quantities yields the required control of the confusion-matrix estimation error.The proof proceeds from bounds on |D − Ā| and related deviations to the lemma’s conclusion.
Loading 1712.04577v2…