When Redundancy Matters: Machine Teaching of Representations

Abstract In traditional machine teaching, a teacher needs 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, both theoretically, and also experimentally for languages where redundancy can vary (DNF expressions and Turing-complete P3 programs). Our theoretical and experimental results indicate that there are various types of redundancy, related, e.g,. to the spread of the redundant representations, handled better by the new Greedy schema introduced here than by the Eager schema. For P3 programs witness sets found by Greedy are usually smaller than the programs they identify, corroborating previous results that conveying information efficiently is a leitmotif of machine teaching.