Source-linked AI summary
DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning
Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lucas Morales, Luke Hewitt, Armando Solar-Lezama, Joshua B. Tenenbaum
TL;DR
DreamCoder addresses the difficulty of program induction without hand-designed domain-specific languages by learning both symbolic abstractions and neural search guidance. Its wake-sleep procedure grows libraries from solved tasks while training recognition models on replays and fantasies, producing general-purpose expertise across qualitatively different domains. The paper concludes that this combination yields interpretable, reusable, and generalizable knowledge, while noting that pervasive real-world noise remains a challenge.
Problem
Program induction has had limited practical impact because effective systems typically require hand-engineered languages and search strategies for combinatorial program spaces.
Method
DreamCoder alternates waking program search with sleep phases that abstract reusable library concepts and train a neural recognition model on replayed and imagined tasks.
Results
DreamCoder learns expertise and improves with experience across many qualitatively different domains, including list processing, text editing, and creative tasks.
Takeaways & Limitations
DreamCoder combines symbolic, probabilistic, and neural learning to create deep explicit representations of domain structure that are understandable to humans.
Takeaways & Limitations
The work focuses on problems whose solution spaces are well captured by crisp symbolic forms, whereas pervasive noise and uncertainty remain key challenges.
Abstract
from arXiv · showhide
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 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 multi-layered symbolic representations that are interpretable and transferrable to new tasks, while still growing scalably and flexibly with experience.
Wake/Sleep Program Learning
DreamCoder alternates waking program search with abstraction and dreaming sleep phases to jointly grow a symbolic library and train a neural recognition model. These cycles bootstrap increasingly useful concepts and search guidance from solved tasks, replays, and imagined problems.
- Probabilistic formulation: The system jointly infers task programs, a library prior over programs, and an approximate posterior predicted by the recognition model.The library defines P[ρ|L], while the recognition network predicts programs conditioned on task observations.
- Bootstrapping: Successive cycles bootstrap both expertise and efficiency: learned concepts deepen the library, while improved recognition guides waking search toward better solutions.Library learning reduces program depth at the expense of breadth, and recognition training reduces effective search breadth.
- Wake phase: Wake searches for task-solving programs with high posterior probability, balancing task likelihood against prior preference for short programs in the current language.The recognition model ranks candidates, while Bayesian scoring combines how well programs solve tasks with their prior plausibility.
- Abstraction phase: Abstraction refactors waking solutions to expose reusable semantic patterns, then adds components that improve a Bayesian compression objective to the library.DreamCoder searches bounded refactorings and uses shared structure to discover primitives such as map.
- Dreaming phase: Dreaming trains the recognition model on replayed waking experiences and fantasies generated from programs sampled from the learned library.The network learns to predict solutions to imagined tasks by solving them during sleep and training on the resulting observable data and programs.
- Bootstrapping: Refactoring can expose higher-order abstractions such as map, making existing solutions shorter and more interpretable while enabling harder later tasks.DreamCoder represents programs as polymorphically typed λ-calculus expressions and searches a finite but potentially astronomically large refactoring space.
Results
DreamCoder learns reusable symbolic abstractions and neural search guidance across classic and creative program-induction tasks. Across domains, it improves held-out performance, develops structured dreams and libraries, and can rediscover functional-programming abstractions from minimal primitives.
- Classic program induction: DreamCoder composed around 20 new list-processing routines, building from filter to sorting through successive layers of abstraction.The learned routines include higher-order functions such as filter and are reused to construct increasingly complex list operations.
- Classic program induction: 79.6% of SyGuS text-editing problems were solved after learning, versus 3.7% before learning, with average search time falling from 235 to 40 seconds.With the competition’s more generous compute budget, DreamCoder solved 84.3%, compared with CVC4’s 82.4%.
- Creative tasks: After learning, dreams became richly structured, recombining acquired building blocks and motifs in novel ways to generate training data for the recognition model.Before learning, dreams were largely unstructured; after learning, they were compositionally recombined and more varied.
- Cross-domain evaluation: Across domains, DreamCoder solved the most held-out tasks and generally did so in the least time, with mean and median solving times of 54.1s and 15.0s.In LOGO graphics and tower building, alternatives solved no more than 60% of held-out tasks, while DreamCoder approached 100%.
- Library growth: Deeper learned libraries correlated with solving more tasks (r = 0.79), while recognition models improved performance at all library depths and produced deeper final libraries.The results connect symbolic library structure with recognition-model guidance across wake-sleep learning.
Discussion
DreamCoder combines symbolic, probabilistic, and neural learning to build interpretable expertise that grows with experience. Its discussion also identifies boundaries: current methods favor crisp symbolic problems, require substantial resources, and do not yet generate tasks autonomously.
- Contributions: DreamCoder jointly learns explicit declarative knowledge and implicit procedural skill, enabling a general-purpose system to improve across qualitatively different domains.The declarative component captures conceptual abstractions, while the procedural component helps use the learned language efficiently.
- Contributions: Its symbolic abstraction hierarchies produce human-understandable knowledge that can adapt and grow, unlike fixed expert systems or conventional neural representations.The paper presents this as a consequence of combining symbolic, probabilistic, and neural approaches.
- Limitations and future work: The demonstrated approach focuses on domains whose solution spaces are well captured by crisp symbolic forms, leaving pervasive noise and uncertainty as a key challenge.The authors suggest integrating hybrid neuro-symbolic representations with DreamCoder’s library learning and bootstrapping.
- Learning dynamics: DreamCoder’s unsupervised exploration pushes beyond its current abilities, but unlike humans it cannot choose or generate tasks as stepping stones toward harder problems.The authors identify autonomous problem generation as an important next step.
- Limitations and future work: Learning substantial expertise from very little built-in knowledge can demand extensive data or compute; constructing functional-programming knowledge took approximately a year of total CPU time.The discussion therefore favors learning on top of rich systems of built-in knowledge rather than pursuing blank-slate learning.