Non-Cheating Teaching Revisited: A New Probabilistic Machine Teaching Model

Cèsar Ferri, José Hernández-Orallo, Jan Arne Telle

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:

  1. Maximum Likelihood Estimation (MLE): The learner chooses the concept $c$ that maximizes the likelihood $p(w|c)$.
  2. 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.

Probabilistic shifts in concept identification. As more evidence is added (from {3} to {3, 11}), the most probable concept shifts from 'odd' to 'prime'.

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).

Taxonomy of Machine Teaching models based on likelihood and prior distributions.

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

Abstract

Over the past decades in the field of machine teaching, several restrictions have been introduced to avoid ‘cheating’, such as collusion-free or non-clashing teaching. However, these restrictions forbid several teaching situations that we intuitively consider natural and fair, especially those ‘changes of mind’ of the learner as more evidence is given, affecting the likelihood of concepts and ultimately their posteriors. Under a new generalised probabilistic teaching, not only do these non-cheating constraints look too narrow but we also show that the most relevant machine teaching models are particular cases of this framework: the consistency graph between concepts and elements simply becomes a joint probability distribution. We show a simple procedure that builds the witness joint distribution from the ground joint distribution. We prove a chain of relations, also with a theoretical lower bound, on the teaching dimension of the old and new models. Overall, this new setting is more general than the traditional machine teaching models, yet at the same time more intuitively capturing a less abrupt notion of non-cheating teaching.
BibTeX
@inproceedings{ferri2022non,
  author = {Cèsar Ferri and José Hernández-Orallo and Jan Arne Telle},
  title = {{Non-Cheating Teaching Revisited: A New Probabilistic Machine Teaching Model}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/412},
}
Figure