Abstract
Machine Teaching (MT) traditionally relies on rigid non-collusion constraints that prevent learners from updating their hypotheses in ways that are natural in Bayesian learning. This paper introduces a probabilistic framework for MT based on joint distributions over concepts and witnesses. By shifting from binary consistency to a witness joint distribution, the authors demonstrate that "changing one's mind" upon receiving more evidence is a rational, non-cheating behavior. The framework encompasses classical models as special cases and establishes a new hierarchy of teaching dimensions.
Introduction: The Collusion Problem
In the field of Machine Teaching, a teacher aims to select an optimal witness $w$ to help a learner identify a target concept $c^*$. To ensure the teaching process is meaningful, researchers have long sought to prevent "cheating"—where the teacher and learner use a secret code to communicate the concept regardless of the data's actual meaning.
The standard solution has been the "GM-collusion-free" (or non-clashing) condition. This condition requires that if a learner identifies concept $c$ from witness $w$, they must continue to identify $c$ for any superset $w' \supset w$ that is also consistent with $c$. While mathematically convenient, this "monotonicity" requirement is often violated in real-world learning. For instance, seeing the number "3" might lead a learner to hypothesize the concept "odd numbers." However, seeing "3, 11, 29" might naturally shift the hypothesis to "prime numbers," even though all three numbers are odd. Classical models would label this shift as illegal collusion, whereas it is actually a hallmark of rational Bayesian updating.
A Probabilistic Framework for Teaching
The authors move away from binary consistency graphs toward a witness joint distribution $p(c, w)$. This distribution represents the probability that a teacher chooses witness $w$ to teach concept $c$.
MLE and MAP Teaching
The framework introduces two primary learning objectives:
- Maximum Likelihood Estimation (MLE): The learner chooses the concept $c$ that maximizes the likelihood $p(w|c)$.
- Maximum a Posteriori (MAP): The learner chooses the concept $c$ that maximizes the posterior $p(c|w) \propto p(w|c)p(c)$.
Witness Sampling Composition (WSC)
The core technical innovation is Witness Sampling Composition (WSC). This method derives the probability of a complex witness (a set of examples) from a simpler "ground" distribution $q(c, x)$ of individual examples. This ensures that the teacher and learner share a common "factual" understanding of the world. By basing the joint distribution on $q$, the model ensures that any "change of mind" is driven by the underlying statistics of the data rather than a hidden code.
As shown in the table above, the probability $p(c, w)$ allows for dynamic hypothesis testing. When only the number 3 is observed, the concept $c_{odd}$ has a higher joint probability (0.022) than $c_{prime}$ (0.013). However, when the witness is expanded to {3, 11}, the probability for $c_{odd}$ drops significantly, and $c_{prime}$ becomes the most likely hypothesis (0.005).
Key Insights and Results
The paper demonstrates that classical teaching models, such as Classical Teaching (CT) and Preference-Based Teaching (PBT), are specific, "uniform" instances of this broader probabilistic framework.
Taxonomy of Models
The authors categorize MT models based on whether the likelihood $p(w|c)$ and the prior $p(c)$ are uniform or "free" (determined by the ground distribution).
This taxonomy allows for a precise comparison of different Teaching Dimensions (TD)—the minimum number of examples required to teach a concept. The authors prove that their MLE and MAP models can reach the theoretical lower bound of teaching complexity ($LBTD$) while remaining "fair" and non-collusive.
Monotonicity and Power
A key result is the proof that if the likelihood is uniform (the ULUP and ULFP cases), the model remains "monotone," aligning with classical non-clashing conditions. However, when likelihoods are allowed to vary ("free"), the model gains significant power, often achieving lower TDs than the traditional Non-Clashing Teaching Dimension (NCTD).
Conclusion and Future Directions
By redefining non-cheating through the lens of joint probability distributions, this work reconciles Machine Teaching with Bayesian inference. The proposed WSC models provide a "sweet spot" in teaching theory: they are more efficient than classical non-clashing models but more grounded and less prone to unnatural assignments than raw theoretical bounds. Future research will look to extend this framework to infinite concept classes and explore interactive teaching scenarios where the teacher and learner can engage in a feedback loop.
Summary updated