Source-linked AI summary
An Overview of Machine Teaching
Xiaojin Zhu, Adish Singla, Sandra Zilles, Anna N. Rafferty
TL;DR
Machine teaching asks how data can convey a known target to a learner, including targets whose behavior is understood but not succinctly parameterized. The paper organizes this area across dimensions such as learner knowledge and teacher–student roles, and relates teaching complexity to passive-learning complexity. It also notes boundaries including unfair coding schemes and the framework’s deliberately incomplete scope.
Problem
Machine teaching concerns conveying a target through data even when the teacher knows the target behavior without a succinct parameter representation.
Method
The paper organizes machine teaching problems along dimensions and examines their formal objectives, learner knowledge, roles, and theoretical complexity.
Results
Teaching complexity has formal relationships to passive-learning complexity through RTD and PBTD bounds involving VCD, although TD and VCD have no general relationship.
Takeaways & Limitations
Machine teaching is a broader data-optimization perspective encompassing transmission, control, persuasion, influence, and attacks on adaptive systems.
Takeaways & Limitations
Teaching models must avoid unfair coding tricks or collusion, and the proposed organization is explicitly incomplete and non-prescriptive.
Abstract
from arXiv · showhide
In this paper we try to organize machine teaching as a coherent set of ideas. Each idea is presented as varying along a dimension. The collection of dimensions then form the problem space of machine teaching, such that existing teaching problems can be characterized in this space. We hope this organization allows us to gain deeper understanding of individual teaching problems, discover connections among them, and identify gaps in the field.
1 Introduction
Machine teaching designs training data for a known target, whereas passive and active learning infer a model from data or queries. In a 1D threshold problem, teaching can achieve any specified error with two examples, compared with error-dependent passive or active sample requirements.
- Passive learning: Passive learning estimates a threshold from n i.i.d. uniformly sampled items, with generalization error O(n^-1).The uncertainty is determined by the spacing between the innermost negative and positive training items.
- Passive learning: n ≥ O(ϵ^-1) passive examples are needed for ϵ generalization error; error 0.001 requires roughly 1000 examples.
- Active learning: Active learning uses adaptive label queries and binary search, reducing threshold error geometrically as O(2^-n).
- Active learning: n ≥ O(log(ϵ^-1)) active queries achieve ϵ error; error 0.001 requires around 10 queries.
- Machine teaching: Machine teaching selects two labeled examples bracketing the target threshold within ϵ, so the teaching-set size remains two regardless of ϵ.
- Additional examples: For a d-dimensional Gaussian, a teacher can use d + 1 points arranged as appropriately scaled vertices of a tetrahedron centered at µ∗.
- Formal contrast: Teaching formally chooses D so a learner trained on it approximates θ∗, while the teacher typically optimizes over discrete teaching sets and must know the learning algorithm.
2 Why bother if the teacher already knows θ∗?
Machine teaching matters because data can transmit a known target, control or persuade learners, and manipulate adaptive systems. Its formulation treats learning as a decoder and varies objectives, costs, constraints, and the teacher’s representation of the target.
- Motivation: Training-set poisoning illustrates machine teaching: an attacker manipulates adaptive training data so a victim’s system learns a desired behavior.
- Coding perspective: The learning algorithm acts as a decoder that maps teaching sets to models, so teaching selects a small set encoding θ∗.
- Decoder dependence: A single on-line example teaches homogeneous linear regression under OLS, but ridge regression requires an upward y adjustment that depends on λ.
- Motivation: Machine teaching generates data to transmit a model, control a learner, shape reinforcement learning, persuade an agent, influence vertices, or attack an adaptive system.
- General formulations: Teaching objectives can minimize teaching risk, generalize teaching cost beyond item count, or optimize learning subject to a teaching-cost budget.
- General formulations: Exact teaching with teaching-set cardinality and version-space risk recovers the classical Teaching Dimension.
- Target representation: Machine teaching also covers teachers who know target behavior without a succinct parameter representation, such as humans specifying representative extraction examples.
3 Characterizing the machine teaching space
The paper organizes machine teaching as a multidimensional space in which teaching problems occupy points or regions. Dimensions include the teacher–student roles and the teacher’s knowledge of the student, while the framework remains open to revision.
- Framework: Each teaching problem is represented as a point or region in a space formed by dimensions of machine teaching.
- Framework: The organization is explicitly incomplete and non-prescriptive, intended to be updated as the field develops.
- Teacher and student roles: Applications vary with teacher and student identities, including machine–machine, machine–human, human–machine, and human–human settings.
- Teacher and student roles: Human experts can select optimal examples for machine learners, potentially outperforming active learning that uses humans only as label oracles.
- Teacher and student roles: Machines can guide nonoptimal human teachers with analogues of optimal examples, while human teachers may provide features, comparisons, or rules when learners support them.
3.2 The teaching signal dimension: What can the teacher use?
Machine teaching can use different kinds of teaching signals, ranging from labeled examples to features, comparisons, demonstrations, and artificial rewards. For supervised learning, the examples may be synthetically constructed, selected from a finite pool, or mildly modified.
- The teaching signal depends on the learner and may include spacing prompts for human memory recall.
- Supervised teaching commonly uses labeled training items, with synthetic, pool-based, and hybrid settings.
- Synthetic teaching allows arbitrary feature-space items, while honest teachers must use target-consistent labels and lying teachers may choose any labels.
- Pool-based teaching restricts the teacher to a finite pool of actual candidate items, such as images or documents.
- Newer supervised signals include features and pairwise comparisons, while reinforcement learning can use demonstrations or artificial rewards.
3.3 The batch vs. sequential dimension: Teaching with a set or a sequence?
Batch teaching provides an unordered training set, whereas sequential teaching also optimizes presentation order for a sequential learner. Ordering can matter for cognitive models, robots, curriculum learning, and convergence guarantees.
- Batch teaching gives a training set to a batch learner, so item order does not matter and repetitions may or may not be allowed.
- Sequential teaching optimizes the order of examples for learners including SGD algorithms, multi-armed bandits, and reinforcement learners.
- Sequential teaching is used in robot teaching by demonstration and curriculum learning that presents examples from simple to difficult.
- Perceptron-type learning has better convergence-rate guarantees when distant-from-boundary examples precede examples closer to the decision boundary.
3.4 The model-based vs. model-free dimension: How much does the teacher know about the student?
The model-based versus model-free dimension captures how much the teacher knows about the student, with graybox teaching occupying the middle ground. Partial knowledge can prevent exact teaching but permit probing and adaptive optimization.
- Machine teaching critically depends on the teacher’s knowledge of the student.
- A model-based teacher treats the student as a clearbox and knows the learning algorithm and relevant parameters.
- Full student knowledge allows teaching to be formulated as a bilevel optimization problem.
- A model-free teacher treats the student as a blackbox, observes TeachingRisk after supplying data, and can use derivative-free optimization.
- A graybox teacher has partial algorithmic knowledge; uncertainty about regularization can prevent exact teaching with any finite set, motivating probing through predictions.
3.5 The student awareness dimension: Does the learner know it is being taught?
Student awareness distinguishes settings where learners do not anticipate teaching from anticipatory models that account for how examples are selected. Awareness can change teaching efficiency and may enable translation or rejection of a teacher’s strategy.
- Most teaching settings assume the student does not anticipate teaching and treats specially constructed data as ordinary training data.
- An increasing number of settings involve students aware that they are being taught.
- Recursive and preference-based teaching models assume teacher and learner share preferences over hypotheses and use examples to distinguish the target from higher-ranked concepts.
- These anticipatory models outperform classical Teaching Dimension in the number of examples required because the learner knows the teacher’s selection strategy.
- A student aware of a human teacher may improve received teaching or switch to active learning when the teacher is highly suboptimal.
- When teacher and student assume different algorithms, the student can translate the teaching set if it knows both models; otherwise, an optimal set for one may be suboptimal for the other.
3.6 The one vs. many dimension: how many students are simultaneously taught?
Machine teaching usually addresses one teacher and one student, but some settings involve multiple students with different learning algorithms. Because one shared teaching set may not perfectly teach everyone, the teacher can optimize either the worst-case or average student.
- Most teaching settings involve one teacher and one student.
- With multiple students using different learning algorithms, the teacher must use the same teaching set for all of them.Perfectly teaching every student is generally impossible, even when the teacher knows each learning algorithm.
- Minimax teaching optimizes performance for the worst student.
- Bayes-risk teaching optimizes performance for the average student using a prior distribution over students.
3.7 The angelic vs. adversarial dimension: Is the teacher a friend or foe?
Machine teaching ranges from angelic goals, such as personalized education and efficient training, to adversarial goals, such as training-set poisoning attacks.
- Angelic machine teaching includes optimized education, improved cognitive models, and fast classifier training.
- Adversarial machine teaching includes training-set poisoning attacks.
3.8 The theoretical vs. empirical dimension: What is the work style?
Machine teaching spans work styles from theoretical studies of teaching complexity to empirical heuristic methods used in computer tutoring systems.
- Most teaching problems contain both theoretical and empirical components, with one usually emphasized.
- Theoretical work studies Teaching Dimension and variants such as Recursive Teaching Dimension and Preference-based Teaching Dimension.
- Computer tutoring systems often use heuristic teaching methods to improve human student performance.
4 Some research directions in machine teaching
Research directions extend machine teaching theory beyond classical assumptions, connect teaching complexity to learning complexity, and broaden applications to richer students, signals, interactions, reinforcement learning, education, and adversarial settings.
- 4.1 Algorithmic teaching theory: Teaching Dimension can be formulated as constrained optimization using a version-space learner, singleton target risk, and teaching-set cardinality cost.
- 4.1 Algorithmic teaching theory: Classical Teaching Dimension can be weakened by collusive coding tricks, motivating collusion-free notions such as RTD and PBTD.The paper identifies systematic study of different collusion notions as future research.
- 4.1 Algorithmic teaching theory: TD has no general relationship with VCD, whereas RTD is in O(VCD^2), PBTD ≤ RTD, and whether RTD is in O(VCD) remains open.
- 4.1 Algorithmic teaching theory: Teaching sets and compression sets are connected, so resolving whether RTD is in O(VCD) could inform the sample compression conjecture.
- 4.1 Algorithmic teaching theory: Open directions include non-version-space learners, richer teaching signals, interactive batch alternatives, and students with limited memory or computation.Examples include ridge regression, logistic regression, SVMs, Bayesian learners, feature-providing teachers, and pairwise comparison queries.
- 4.2 Reinforcement learning and education: Reinforcement-learning directions include teaching through selected demonstrations and reward shaping that minimizes learning time and reward manipulation.Personalized education similarly motivates sequential teaching using learner information and progress feedback, including flashcard review models.
- 4.4 Trustworthy AI: Trustworthy machine teaching could model attacker–learner interactions as repeated games to develop forward-looking defenses.