When Redundancy Matters: Machine Teaching of Representations
Cèsar Ferri Dario Garigliotti Brigt Arve Toppe Håvardstun Josè Hernández-Orallo Jan Arne Telle
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.