When Redundancy Matters: Machine Teaching of Representations
This addresses a foundational issue in machine teaching for AI researchers, focusing on representation redundancy, but it is incremental as it builds on existing teaching schemas.
The paper tackles the problem of teaching concepts when multiple equivalent representations exist, which complicates the teaching process, and explores teaching representations directly using schemas like Eager, Greedy, and Optimal, showing that Greedy handles redundancy better than Eager but both can be far from Optimal, with experimental results for P3 programs indicating witness sets are often smaller than the programs.
In traditional machine teaching, a teacher wants to teach a concept to a learner, by means of a finite set of examples, the witness set. But concepts can have many equivalent representations. This redundancy strongly affects the search space, to the extent that teacher and learner may not be able to easily determine the equivalence class of each representation. In this common situation, instead of teaching concepts, we explore the idea of teaching representations. We work with several teaching schemas that exploit representation and witness size (Eager, Greedy and Optimal) and analyze the gains in teaching effectiveness for some representational languages (DNF expressions and Turing-complete P3 programs). Our theoretical and experimental results indicate that there are various types of redundancy, handled better by the Greedy schema introduced here than by the Eager schema, although both can be arbitrarily far away from the Optimal. For P3 programs we found that witness sets are usually smaller than the programs they identify, which is an illuminating justification of why machine teaching from examples makes sense at all.