Interactive Learning from Multiple Noisy Labels

Shankar Vembu, Sandra Zilles

Introduction

In traditional supervised learning, models typically process training data in a random sequence. However, human learning is often more effective when structured as a curriculum—starting with simple concepts before progressing to complex ones. This paper explores "interactive learning," a form of curriculum learning that leverages the collective disagreement among multiple noisy annotators to rank the difficulty of training examples. By prioritizing "easy" examples where annotators agree, the proposed framework improves classification performance and provides tighter theoretical mistake bounds.

Quantifying Difficulty through Disagreement

The central challenge in curriculum learning is defining a robust metric for "easiness." In real-world scenarios like crowdsourcing, ground-truth labels are often unavailable. Instead, we have multiple noisy labels. The authors propose that annotator disagreement serves as a geometric signal: high agreement suggests an example is far from the decision boundary (easy), while sharp disagreement indicates proximity to the boundary (hard) and higher susceptibility to noise.

Methodology

The framework integrates this disagreement into a regularized risk minimization objective, specifically using weighted least-squares regression. For each example $x_i$, a disagreement score $d_i$ is calculated based on the variance of labels from $L$ annotators. These scores are then mapped to weights using a monotonically decreasing function:

$$g(d) = (1 + e^{\alpha d})^{-1}$$

Weighting function $g(d)$ for various values of the hyperparameter $\alpha$.

As shown in the figure above, the hyperparameter $\alpha$ determines the aggressiveness of the curriculum. A high $\alpha$ value aggressively prioritizes examples where annotators agree, while a low $\alpha$ approaches uniform weighting. The algorithm iteratively optimizes classifier weights and estimates annotator "expertise" by measuring their alignment with the current model.

Experimental Evaluation

The researchers evaluated the approach using synthetic 10-dimensional Gaussian distributions and 20 standard LibSVM benchmark datasets (e.g., a1a-a5a, diabetes, breast-cancer). To simulate crowdsourcing on benchmarks with single ground-truth labels, they injected noise that increased as examples approached the true decision boundary.

Key Results and Theoretical Insights

The interactive approach demonstrated superior performance, winning in up to 89 out of 100 trials on synthetic data compared to non-interactive baselines. It also showed statistically significant improvements across most LibSVM datasets, particularly when the noise parameter was set to reflect realistic crowdsourcing conditions.

Beyond empirical gains, the paper extends the classical Perceptron mistake bound. By sorting examples from "farthest from the boundary" to "closest," the authors prove that the Perceptron makes significantly fewer mistakes than under random ordering.

Theoretical x-fold improvement in mistake bounds compared to standard learning.

The figure above illustrates the theoretical "x-fold improvement" in mistake bounds, highlighting how an interactive "teacher" can reduce error rates relative to the standard Novikoff bound.

Discussion and Limitations

While promising, the method faces challenges with high class imbalance, where the "easiness" metric may bias toward the majority class. Additionally, the current model assumes a dense label matrix, which is rare in real-world crowdsourcing where annotators typically label only a subset of data. Future work will focus on handling sparse annotator data and validating the approach on actual crowdsourced datasets where human biases may differ from distance-based noise models.

Summary updated

Abstract

Interactive learning is a process in which a machine learning algorithm is provided with meaningful, well-chosen examples as opposed to randomly chosen examples typical in standard supervised learning. In this paper, we propose a new method for interactive learning from multiple noisy labels where we exploit the disagreement among annotators to quantify the easiness (or meaningfulness) of an example. We demonstrate the usefulness of this method in estimating the parameters of a latent variable classification model, and conduct experimental analyses on a range of synthetic and benchmark datasets. Furthermore, we theoretically analyze the performance of perceptron in this interactive learning framework.
BibTeX
@inproceedings{vembu2016interactive,
  author = {Shankar Vembu and Sandra Zilles},
  title = {{Interactive Learning from Multiple Noisy Labels}},
  booktitle = {ECML/PKDD},
  year = {2016},
  url = {https://openreview.net/forum?id=yo7XbyKlCO},
}
Figure