2021/06/29 by Manuel García Piqueras, Manuel Garcia-Piqueras, Garcia-Piqueras, Manuel +3
Computer Science · Mathematics · #Algorithms and Data Compression #Artificial Intelligence (cs.AI) #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning and Algorithms #cs.AI #cs.CC #cs.IT #cs.LG #math.IT
paper · pdf · doi:10.48550/arxiv.2107.07038
26 pages
arxiv created 2021/06/29 · openalex publication_date 2021/06/29 · arxiv updated 2021/07/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Recent research in machine teaching has explored the instruction of any concept expressed in a universal language. In this compositional context, new experimental results have shown that there exist data teaching sets surprisingly shorter than the concept description itself. However, there exists a bound for those remarkable experimental findings through teaching size and concept complexity that we further explore here. As concepts are rarely taught in isolation we investigate the best configuration of concepts to teach a given set of concepts, where those that have been acquired first can be reused for the description of new ones. This new notion of conditional teaching size uncovers new insights, such as the interposition phenomenon: certain prior knowledge generates simpler compatible concepts that increase the teaching size of the concept that we want to teach. This does not happen for conditional Kolmogorov complexity. Furthermore, we provide an algorithm that constructs optimal curricula based on interposition avoidance. This paper presents a series of theoretical results, including their proofs, and some directions for future work. New research possibilities in curriculum teaching in compositional scenarios are now wide open to exploration.