2024/01/23 by Cèsar Ferri, Ferri, Cèsar, Darío Garigliotti +7
Computer Science · Engineering · #68T05 #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Ferroelectric and Negative Capacitance Devices #I.2.6 #Machine Learning (cs.LG) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2401.12711
openalex publication_date 2024/01/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.