Non Clashing Constraints for Collusion Free Machine Teaching

This direction is merged into another direction: teaching-to-learning complexity ratio. Its last version stays readable and citable here.

Version 1 of 118 papers38 conceptsfrozen 2026-10-04

In the classical "Machine Teaching" framework, a teacher's goal is to select the smallest possible set of examples to guide a learner to a specific target concept. While this sounds efficient, it hides a fundamental flaw: collusion. Without strict constraints, a teacher and learner could agree on a "secret code"—for instance, "the coordinate (0,0) always means the concept is a 4th-degree polynomial"—allowing them to communicate complex ideas with a single data point. This bypasses the actual semantic content of the data, rendering the "learning" process meaningless.

To solve this, researchers have developed the Non-Clashing Teaching (NCT) model. This framework ensures that the information density of teaching remains high without descending into arbitrary coding.

The Problem of the Cheating Teacher

In standard computational learning theory, we often measure the "Teaching Dimension"—the minimum number of examples needed to identify a concept. However, as David G. Kirkpatrick and Hans Ulrich Simon argue in Optimal Collusion-Free Teaching, many teaching models allow for "cheating" where the teacher and learner use non-semantic features to encode information.

If a teacher can pick any set of examples, they might choose a set that is technically consistent with many concepts but which the learner "knows" (by prior agreement) refers to only one. To prevent this, we need a structural constraint that forces the teaching set to be inherently tied to the concept's properties.

The Non-Clashing Condition

The core mechanism of collusion-free teaching is the non-clashing property. As defined by Hans Ulrich Simon in Tournaments, Johnson Graphs, and NC-Teaching, a teaching map is non-clashing if, for any two distinct concepts $C$ and $C'$, it is impossible for the teacher's examples for $C$ to be consistent with $C'$ at the same time that the examples for $C'$ are consistent with $C$.

Intuition:

  • If I give you examples for a "Square," and those examples also fit the definition of a "Rectangle," that's fine—as long as the examples I would give you for a "Rectangle" do not fit the definition of a "Square."
  • A "clash" occurs only if the evidence for both concepts is mutually ambiguous. By forbidding this mutual ambiguity, we ensure that the learner can always distinguish between any two hypotheses based on the data provided.

This constraint is minimalist. It doesn't require the teacher to provide a "witness" for every possible alternative concept; it only requires that the union of evidence for any two concepts cannot support both simultaneously.

Teaching with Only Positive Evidence

A more restrictive version of this idea is Positive Non-Clashing Teaching. In this model, the teacher is limited to providing only positive examples (members of the target set). Robert Ganian and Liana Khazaliya explore this in The Computational Complexity of Positive Non-Clashing Teaching in Graphs.

This is significantly harder because the teacher cannot use "negative" examples to rule out larger, encompassing concepts. The teacher must find a set of positive points unique enough that no other concept in the class could "claim" them without violating the non-clashing rule. This turns machine teaching into a combinatorial puzzle: finding the smallest "identifying set" within a complex structure.

The Geometry of Teaching in Graphs

To study these properties rigorously, researchers often apply them to graph theory, specifically using "balls" or "closed neighborhoods" in a graph as the concepts to be learned. Fionn Mc Inerney and Sébastien Ratel demonstrate in Non-Clashing Teaching Maps for Balls in Graphs that the complexity of teaching depends heavily on the graph's geometry.

While finding the optimal non-clashing teaching set is generally NP-hard—and can even reach "double-exponential" lower bounds—it becomes efficiently solvable (Fixed-Parameter Tractable) in graphs with specific structural properties, such as trees, hyperbolic graphs, or those with low vertex integrity Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds.

A Hierarchy of Efficiency

Not all collusion-free models are created equal. Jan Arne Telle and Hans Ulrich Simon have mapped out a Hierarchy of Saturating Matching Numbers, which ranks different teaching constraints by their efficiency.

For example, Antichain-constrained teaching requires that no teaching set can be a subset of another. This is a stricter requirement than non-clashing and results in larger teaching sets (lower efficiency). The non-clashing model sits at the "sweet spot" of this hierarchy: it is the most efficient possible model that still fundamentally prevents collusion.

Towards Natural Learning

While early models were rigid and binary, recent work by Jose Hernandez-Orallo and Cèsar Ferri in Non-Cheating Teaching Revisited suggests moving toward probabilistic, Bayesian-style models. In these frameworks, "cheating" is prevented not by hard combinatorial rules, but by ensuring the teacher's examples align with a learner's natural prior distributions. This aligns machine teaching with how humans actually learn: by prioritizing "simple" or "representative" examples, as explored in early work on Learning DFA from Simple Examples by Rajesh Parekh and Vasant G Honavar.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_clashing_constraints_for_collusion_f_5b4b53bf,
  title = {Non Clashing Constraints for Collusion Free Machine Teaching},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-clashing-constraints-for-collusion-free-machine-teaching/rdr_5b4b53bfb2bf4fa59706aad32fd48988},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_clashing_constraints_for_collusion_f_5b4b53bf_v1,
  title = {Non Clashing Constraints for Collusion Free Machine Teaching},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-clashing-constraints-for-collusion-free-machine-teaching/rdr_5b4b53bfb2bf4fa59706aad32fd48988/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}