Learning Multiple Tasks in Parallel with a Shared Annotator

Haim Cohen, Koby CrammerNeurIPS 2014

In the world of supervised machine learning, data is cheap, but labels are expensive. We often have dozens of models running in parallel—filtering spam, categorizing news, or recognizing speech—and all of them are hungry for human feedback. But what happens when you only have one human expert and a limited "budget" of time?

A paper by Haim Cohen and Koby Crammer from The Technion, titled "Learning Multiple Tasks in Parallel with a Shared Annotator," introduces a clever framework to solve this exact logistical nightmare.

TL;DR

The authors propose SHAMPO, an online learning algorithm designed for scenarios where multiple tasks must share a single, bandwidth-limited annotator. By intelligently picking which task needs a label most at any given moment, SHAMPO achieves higher overall accuracy than standard methods for the same amount of human labor.

What Problem Does This Paper Address?

Shared Annotator Framework

The dominant bottleneck in machine learning is the need for annotated data. Traditionally, we treat tasks in isolation: we collect data for Task A, get it labeled, then move to Task B.

However, in real-world systems—like a news aggregator serving multiple agencies or a personal assistant adapting to different users—many learning tasks run simultaneously. If every task queries the user for a label independently, the user is flooded with requests. The challenge is resource allocation: on every round of learning, which of the $K$ parallel tasks should get the single available label to maximize the "bang for the buck"?

Methods

The authors introduce SHAMPO (SHared Annotator for Multiple PrOblems). It operates in an online setting where, in each round, every task receives an input and makes a prediction. A central mechanism then decides which one task gets to see the true label.

Key components include:

  • Margin-Based Selection: The algorithm looks at the "confidence" of each task's prediction (the distance from the decision boundary, or margin). If a margin is small, the model is uncertain.
  • Exploration-Exploitation Tradeoff: SHAMPO doesn't just pick the most uncertain task (pure exploitation); it uses a stochastic (randomized) mechanism. A parameter $b$ allows the system to balance between picking the "hardest" instance and maintaining enough exploration to ensure all tasks eventually learn.
  • Aggressive Updates: Based on the Perceptron algorithm, SHAMPO doesn't just update when it makes a mistake. It also updates if it was "barely right" (a small margin), which helps the model reach a robust solution faster.
  • Bandit Reductions: The authors show that complex "contextual bandit" problems (where you only get feedback on the choice you made) can be mathematically reduced to this multi-task framework.

Datasets

The researchers evaluated SHAMPO across a diverse range of domains:

  • OCR (Optical Character Recognition): The classic MNIST and USPS handwritten digit datasets.
  • Speech Recognition: The Vocal Joystick (VJ) dataset for vowel recognition.
  • NLP (Natural Language Processing): A collection of 31 binary tasks including spam filtering and newsgroup classification.
  • MIXED: A challenging "kitchen sink" dataset combining images, audio, and text tasks to test the algorithm's versatility.

Key Insights and Ideas

  • Task Equalization: One of the most striking findings is that SHAMPO naturally "equalizes" task difficulty. It automatically diverts more human attention to the "hard" tasks while letting the "easy" tasks coast once they are sufficiently accurate.
  • The Power of Randomness: Purely picking the hardest task (low $b$) can lead to overfitting on noisy data. By introducing a controlled amount of randomness, SHAMPO remains more robust than a purely "greedy" strategy.
  • Efficiency: The algorithm achieves a performance level comparable to models that see all the labels, despite only seeing a fraction of them. This suggests that most labels in standard supervised learning are actually redundant.

Key Results

Performance of SHAMPO vs Baselines

The empirical results were consistent across all datasets:

  • Superior Accuracy: SHAMPO consistently outperformed "Uniform" allocation (picking a task at random) and "Exploit" (always picking the lowest margin).
  • Mean Score: In a ranking of algorithms across all test cases, Aggressive SHAMPO earned a mean score of 1.1 (where 1 is best), significantly beating the Exploit baseline (2.7) and Uniform allocation (5.2).
  • Labor Savings: In the MNIST experiments, harder tasks received roughly 4x more queries than easier tasks. This targeted approach reduced the total error across all 45 parallel tasks by more than 40% compared to full exploration.

Limitations and Future Work

While powerful, the current version of SHAMPO has some constraints:

  • Linearity: The core analysis focuses on linear models (though the authors note that kernel methods can be swapped in).
  • Single Query: The primary framework assumes only one label per round, though an appendix begins to explore multi-query scenarios.
  • Priors: While the authors showed that "priors" (pre-existing knowledge about task difficulty) can help, they haven't yet fully automated the process of generating these priors.

The authors suggest that future work could involve more complex "Error-Correcting Output Codes" to further bridge the gap between binary multi-tasking and complex multi-class problems.

Summary updated

BibTeX
@inproceedings{cohen2014learning,
  author = {Haim Cohen and Koby Crammer},
  title = {{Learning Multiple Tasks in Parallel with a Shared Annotator}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure