Near-Optimally Teaching the Crowd to Classify

Abstract

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.

References in corpus (1)

• Galaxy Zoo : Morphologies derived from visual inspection of galaxies from the Sloan Digital Sky Survey

Cited by in corpus (23)

• On Human Predictions with Explanations and Predictions of Machine Learning Models: A Case Study on Deception Detection
• Quality Control in Crowdsourcing: A Survey of Quality Attributes, Assessment Techniques and Assurance Actions
• Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learning
• Enabling Robots to Communicate their Objectives
• The effectiveness of feature attribution methods and its correlation with automatic evaluation scores
• Towards Black-box Iterative Machine Teaching
• Stochastic Conditional Gradient++
• Adaptivity in Adaptive Submodularity
• Streaming Submodular Maximization under a $k$-Set System Constraint
• Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environments
• Non-monotone DR-submodular Maximization: Approximation and Regret Guarantees
• Unlearn What You Have Learned: Adaptive Crowd Teaching with Exponentially Decayed Memory Learners
• Black Box Submodular Maximization: Discrete and Continuous Settings
• SCOUT: Self-aware Discriminant Counterfactual Explanations
• The Teaching Dimension of Kernel Perceptron
• Fair Clustering Using Antidote Data
• Continuous Submodular Maximization: Beyond DR-Submodularity
• Iterative Machine Teaching without Teachers
• Teaching an Active Learner with Contrastive Examples
• Iterative Teaching by Label Synthesis
• Iterative Classroom Teaching
• Scalable Projection-Free Optimization
• Submodular + Concave