TL;DR
This paper introduces "Playgol," a novel approach to program induction that mimics how children learn through play. By allowing an AI system to first "play" and discover reusable building blocks (programs) on its own, Playgol significantly improves its ability to learn complex tasks later, reducing the need for extensive, pre-defined background knowledge.
What Problem Does This Paper Address?
Traditional program induction systems often struggle with learning complex programs because they rely heavily on pre-existing, human-engineered background knowledge (BK). This BK acts as a set of rules or concepts the system can use. However, creating this BK is time-consuming and can limit the system's ability to discover novel solutions. The challenge is to develop program induction systems that can acquire useful BK autonomously, without requiring a large corpus of user-provided training tasks. This is analogous to how children learn: they explore and play, discovering fundamental concepts before tackling specific, structured tasks.
Methods
The core of Playgol's approach is a two-stage process:
- Unsupervised Playing Stage: The system is given a set of possible examples (the "instance space") and initial BK. Instead of immediately trying to solve user-defined tasks, it generates its own "play tasks" by sampling from the instance space. It then attempts to solve these play tasks and saves any discovered programs (solutions) into its BK. This stage is unsupervised because the play tasks are not user-defined, and no explicit labels are provided.
- Supervised Building Stage: After the playing stage, the system uses the augmented BK (which now includes programs learned during play) to solve the user-supplied build tasks.
Playgol is implemented using Meta-Interpretive Learning (MIL), a technique that allows for learning recursive programs and supports "predicate invention" – the automatic discovery of new, reusable sub-programs. The authors theorize that this "playing" phase helps by increasing the number of available predicate symbols (discovered concepts) in the BK, which, according to their theoretical analysis, can reduce the sample complexity (the number of examples needed) for learning the target programs.
Datasets
- Robot Planning Domain: The experiments used a simulated robot in an $n \times n$ grid. The instance space was defined for $5 \times 5$ and $6 \times 6$ grids.
- String Transformations Domain: The authors used 94 real-world string transformation tasks, augmented with manually created tasks from various sources. The instance space was formed from random string transformations using an alphabet of 80 symbols.
Key Insights and Ideas
- Play as Unsupervised Bootstrapping: The paper frames "playing" as a form of unsupervised bootstrapping for program induction, where the system learns foundational concepts before tackling specific goals.
- Reducing Textual and Sample Complexity: The core hypothesis is that discovering reusable general programs during play reduces the complexity of the target concepts, thereby reducing the number of examples needed to learn them.
- Predicate Invention is Crucial: The experiments suggest that the ability to invent new predicates (sub-programs) during play is key to discovering highly reusable concepts that can be composed to solve complex problems.
- Play is More Than Just Sampling: The results indicate that playing significantly improves performance even with a relatively small number of play tasks, refuting the argument that it's merely equivalent to sampling build tasks.
Key Results
- Robot Planning: Playgol significantly improved the percentage of build tasks solved compared to a baseline (Metagol without play). For instance, in a $5 \times 5$ space, performance increased from 12% to nearly 100% with 1000 play tasks. In a $6 \times 6$ space, performance rose from 7% to over 60% with 1200 play tasks.
- String Transformations: Playgol showed improved predictive accuracy compared to the baseline. Accuracy increased from 25% to almost 37% (a 12% improvement) after 2000 play tasks.
- Predicate Invention Benefit: Experiments comparing Playgol with a variant that didn't save invented predicates (Playgol NH3) showed that Playgol consistently performed better, especially in the robot planning domain, suggesting that invented predicates are valuable.
Limitations and Future Work
- Domain Generality: While promising in robot planning and string transformations, the authors acknowledge that the generality of the "play" approach across all domains is still unclear. Future work aims to determine in which domains playing is most beneficial.
- Number of Play Tasks: The paper shows that playing improves performance without needing many play tasks, but a precise theory predicting the optimal number of play tasks for different problem complexities is still needed.
- Instance Space Size: The current approach assumes a suitably large instance space for effective play. The authors question whether the approach would work if such a space is unavailable.
- Sampling Strategy: In the string transformation experiment, performance plateaued. This suggests that the relevancy of sampled play tasks matters. Future work will explore more intelligent or semi-supervised sampling strategies to create more useful play tasks.
Summary updated