DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning

id:

2006.08381

Authors:

Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lucas Morales, Luke Hewitt, Armando Solar-Lezama, Joshua B. Tenenbaum

Published:

2020-06-15

arXiv:

https://arxiv.org/abs/2006.08381

PDF:

https://arxiv.org/pdf/2006.08381

DOI:

N/A

Journal Reference:

N/A

Primary Category:

cs.AI

Categories:

cs.AI, cs.LG

Comment:

N/A

github_url:

_

abstract

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.

premise

outline

quotes

notes

summary

  1. Brief Overview

DreamCoder is a machine learning system designed to learn by writing programs. It builds expertise by creating programming languages to represent domain concepts and using neural networks to guide the search for programs within these languages. A “wake-sleep” algorithm allows DreamCoder to extend its language with new symbolic abstractions and train the neural network on both real and imagined problems. This allows it to solve various tasks, from classic inductive programming to creative tasks like drawing pictures, and rediscovers core concepts from fields such as functional programming and classical physics. The system produces multi-layered symbolic representations that are interpretable and transferable.

  1. Key Points

  • Learns to solve problems by writing programs.

  • Creates programming languages to express domain concepts.

  • Employs a “wake-sleep” learning algorithm.

  • Solves both classic and creative tasks across multiple domains.

  • Generates multi-layered, interpretable, and transferable symbolic representations.

  • Grows scalably and flexibly with experience.

  • Learns domain-specific languages and search strategies.

  • Achieves high performance on benchmark program synthesis tasks.

  • Demonstrates few-shot learning capabilities across diverse domains.

  1. Notable Quotes

None explicitly stated in the provided text that stand out as particularly notable quotes.

  1. Primary Themes

  • Program induction as a learning paradigm: The paper strongly advocates for viewing learning as program induction, highlighting its advantages in generalization, sample efficiency, interpretability, and universality compared to purely statistical approaches.

  • Bayesian program learning: The use of Bayesian methods is central to DreamCoder’s approach, enabling the system to learn both a prior over programs and an inference algorithm to efficiently approximate the posterior.

  • Wake-sleep learning: The wake-sleep algorithm is presented as a crucial mechanism for scaling program induction, allowing DreamCoder to iteratively grow its knowledge and improve its efficiency.

  • Interpretability and generalizability: A key goal is to develop a system that learns interpretable and generalizable knowledge, which is achieved through the use of symbolic representations and the compositional nature of the learned languages.

  • Human-like learning: The paper draws parallels between DreamCoder’s learning mechanisms and aspects of human learning, especially the role of sleep in memory consolidation and the development of expertise.