Harmonizing Program Induction with Rate-Distortion Theory
This work addresses a theoretical gap in cognitive science for modeling human learning with programs, though it is incremental in adapting existing frameworks.
The paper tackled the challenge of applying Rate-Distortion Theory to mental programs by introducing a trade-off among description length, error, and computational costs, showing through simulations on a melody task that shared program libraries improve performance but are sensitive to curricula, with methods generating curricula that enhance generalization.
Many aspects of human learning have been proposed as a process of constructing mental programs: from acquiring symbolic number representations to intuitive theories about the world. In parallel, there is a long-tradition of using information processing to model human cognition through Rate Distortion Theory (RDT). Yet, it is still poorly understood how to apply RDT when mental representations take the form of programs. In this work, we adapt RDT by proposing a three way trade-off among rate (description length), distortion (error), and computational costs (search budget). We use simulations on a melody task to study the implications of this trade-off, and show that constructing a shared program library across tasks provides global benefits. However, this comes at the cost of sensitivity to curricula, which is also characteristic of human learners. Finally, we use methods from partial information decomposition to generate training curricula that induce more effective libraries and better generalization.