# Near-Optimally Teaching the Crowd to Classify

arXiv: https://arxiv.org/abs/1402.2092 · HTML: https://mlsanity.com/paper/1402.2092/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2014.

## Built on by (most cited first, 30 of 32)

- [The effectiveness of feature attribution methods and its correlation with automatic evaluation scores](https://mlsanity.com/paper/2105.14944/) (2021)
- [Visual correspondence-based explanations improve AI robustness and human-AI team accuracy](https://mlsanity.com/paper/2208.00780/) (2022)
- [Teaching Humans When To Defer to a Classifier via Exemplars](https://mlsanity.com/paper/2111.11297/) (2021)
- [Machine Teaching for Inverse Reinforcement Learning: Algorithms and Applications](https://mlsanity.com/paper/1805.07687/) (2018)
- [Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environments](https://mlsanity.com/paper/2102.08492/) (2021)
- [Interactive Teaching Algorithms for Inverse Reinforcement Learning](https://mlsanity.com/paper/1905.11867/) (2019)
- [Learner-aware Teaching: Inverse Reinforcement Learning with Preferences and Constraints](https://mlsanity.com/paper/1906.00429/) (2019)
- [Nonparametric Teaching of Implicit Neural Representations](https://mlsanity.com/paper/2405.10531/) (2024)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [Teaching an Active Learner with Contrastive Examples](https://mlsanity.com/paper/2110.14888/) (2021)
- [Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration](https://mlsanity.com/paper/2305.08367/) (2023)
- [Fair Clustering Using Antidote Data](https://mlsanity.com/paper/2106.00600/) (2021)
- [Iterative Teaching by Label Synthesis](https://mlsanity.com/paper/2110.14432/) (2021)
- [Nonparametric Iterative Machine Teaching](https://mlsanity.com/paper/2306.03007/) (2023)
- [Iterative Teaching by Data Hallucination](https://mlsanity.com/paper/2210.17467/) (2022)
- [Towards Effective Human-AI Decision-Making: The Role of Human Learning in Appropriate Reliance on AI Advice](https://mlsanity.com/paper/2310.02108/) (2023)
- [Submodular Minimax Optimization: Finding Effective Sets](https://mlsanity.com/paper/2305.16903/) (2023)
- [Nonparametric Teaching for Multiple Learners](https://mlsanity.com/paper/2311.10318/) (2023)
- [Improve Learning from Crowds via Generative Augmentation](https://mlsanity.com/paper/2107.10449/) (2021)
- [Nonparametric Teaching for Graph Property Learners](https://mlsanity.com/paper/2505.14170/) (2025)
- [Learning Human-Compatible Representations for Case-Based Decision Support](https://mlsanity.com/paper/2303.04809/) (2023)
- [ML-Based Teaching Systems: A Conceptual Framework](https://mlsanity.com/paper/2305.07681/) (2023)
- [Transferring Domain Knowledge with (X)AI-Based Learning Systems](https://mlsanity.com/paper/2406.01329/) (2024)
- [L-WISE: Boosting Human Visual Category Learning Through Model-Based Image Selection and Enhancement](https://mlsanity.com/paper/2412.09765/) (2024)
- [Time-Constrained Learning](https://mlsanity.com/paper/2202.01913/) (2022)
- [Visual Knowledge Tracing](https://mlsanity.com/paper/2207.10157/) (2022)
- [On the Perception of Difficulty: Differences between Humans and AI](https://mlsanity.com/paper/2304.09803/) (2023)
- [Nonparametric Teaching of Attention Learners](https://mlsanity.com/paper/2602.20461/) (2026)
- [Scalable Projection-Free Optimization](https://mlsanity.com/paper/2105.03527/) (2021)
- [One-shot Machine Teaching: Cost Very Few Examples to Converge Faster](https://mlsanity.com/paper/2212.06416/) (2022)

## Abstract (arXiv)

How should we present training examples to learners to teach them classification rules? This is a natural problem when training workers for crowdsourcing labeling tasks, and is also motivated by challenges in data-driven online education. We propose a natural stochastic model of the learners, modeling them as randomly switching among hypotheses based on observed feedback. We then develop STRICT, an efficient algorithm for selecting examples to teach to workers. Our solution greedily maximizes a submodular surrogate objective function in order to select examples to show to the learners. We prove that our strategy is competitive with the optimal teaching policy. Moreover, for the special case of linear separators, we prove that an exponential reduction in error probability can be achieved. Our experiments on simulated workers as well as three real image annotation tasks on Amazon Mechanical Turk show the effectiveness of our teaching algorithm.