DreamCoder: growing generalizable, interpretable knowledge with wake–sleep Bayesian program learning

By Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sablé-Meyer, Luc Cary, Lucas Morales, Luke B. Hewitt, Armando Solar-Lezama, Josh Tenenbaum. 2020

266 citations recorded by the source corpus.

Expert problem-solving is driven by powerful languages for thinking about problems and their solutions. Acquiring expertise means learning these languages—systems of concepts, alongside the skills to use them. We present DreamCoder, a system that learns to solve problems by writing programs. It builds expertise by creating domain-specific programming languages for expressing domain concepts, together with neural networks to guide the search for programs within these languages. A ‘wake–sleep’ learning algorithm alternately extends the language with new symbolic abstractions and trains the neural network on imagined and replayed problems. DreamCoder solves both classic inductive programming tasks and creative tasks such as drawing pictures and building scenes. It rediscovers the basics of modern functional programming, vector algebra and classical physics, including Newton’s and Coulomb’s laws. Concepts are built compositionally from those learned earlier, yielding multilayered symbolic representations that are interpretable and transferrable to new tasks, while still growing scalably and flexibly with experience. This article is part of a discussion meeting issue ‘Cognitive artificial intelligence’.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Representation & Self-Supervised Learning, Code Generation & Program Synthesis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Representation & Self-Supervised Learning

In Code Generation & Program Synthesis

Citations in the corpus

Grammar-Based Grounded Lexicon Learning (2022, background): “Finally, future work may consider integrating G2L2 with program-synthesis algorithms [13] for learning of more generic and complex semantic programs.”
Neurosymbolic Program Synthesis (unknown): “D REAM C ODER [42] is a canonical example of such an approach.”
Language to Rewards for Robotic Skill Synthesis (2023, background): “Code generation models have been widely studied both in and outside robotics context [36, 8, 37].”
Improving Coherence and Consistency in Neural Sequence Models with Dual-System, Neuro-Symbolic Reasoning (2021, methodology): “Improvements would come from automatically learning and updating this structured knowledge, possibly by incorporating neuro-symbolic learning techniques (Ellis et al., 2020; Mao et al., 2019), or other neuro-symbolic integration work such as Tsamoura et al. (2021); Michael & Valiant (2008).”
A Reinforcement Learning Environment for Mathematical Reasoning via Program Synthesis (2021, result): “This is similar to the operator abstraction process in Dreamcoder [9].”
Inventing Relational State and Action Abstractions for Effective and Efficient Bilevel Planning (2022, methodology): “Inspired by prior work [16, 17, 29], we approach the predicate invention problem from a program synthesis perspective [30, 31, 32, 33].”
A large-scale benchmark for few-shot program induction and synthesis (2021, methodology): “Program induction datasets There have been multiple few-shot program induction datasets, such as those used in FlashFill (Gulwani, 2011; Gulwani et al., 2015) and Dream-Coder (Ellis et al., 2020), as well as the Abstract Reasoning Challenge(ARC) (Chollet, 2019), a list functions benchmark (Rule, 202”
Code as Policies: Language Model Programs for Embodied Control (2022, methodology): “Code generation has been explored with LLMs [1], [48] and without [49].”
Voyager: An Open-Ended Embodied Agent with Large Language Models (2023, methodology): “Inspired by the generality, interpretability, and universality of programs [46], we represent each skill with executable code that scaffolds temporally extended actions for completing a specific task proposed by the automatic curriculum.”
Symbolic Behaviour in Artificial Intelligence (2021, background): “[32] Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lucas Morales, Luke Hewitt, Armando Solar-Lezama, and Joshua B Tenenbaum.”
Learning to Synthesize Programs as Interpretable and Generalizable Policies (2021, background): “[44] Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lucas Morales, Luke Hewitt, Armando Solar-Lezama, and Joshua B Tenenbaum.”
Neurosymbolic Programming (2021, methodology): “gramming domain, a transfer learning system might learn and reuse recursive control flow patterns (Ellis et al., 2020).”
Leveraging Language to Learn Program Abstractions and Search Heuristics (2021, background): “Recent approaches to program synthesis have attempted to learn search models (Gulwani et al., 2015; Polozov & Gulwani, 2015; Balog et al., 2016; Devlin et al., 2017), program libraries, or both jointly from data (Shin et al., 2019; Dumancić & Cropper; Ellis et al., 2021; 2020; Lázaro-Gredilla et a”