DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning
A program synthesizer learns two things as it solves tasks: a library of functions taken from the programs it writes, and a neural network that tells it which functions to try.
DreamCoder (MIT, 2020) solves tasks given as a few examples by searching for a program that reproduces them. After each round of search it rewrites the programs it found, turns the code they share into new library functions, and trains a network on solved and imagined tasks to predict which functions a new task needs. On list processing, a sort that takes 32 function calls in the starting language takes 5 in the learned one.
Explaining the paperDreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learningBelow: the search problem in numbers, the library as a probability distribution with one program's probability worked by hand, each phase of the learning cycle on concrete programs (the discovery of map, a 32-call sort, a toy of the compression score, the objective that teaches the network one canonical form), and the results in eight domains.
What DreamCoder does
A task is a handful of input/output examples, such as [1 2 3] → [2 4 6] and [4 3 4] → [8 6 8]. Solving it means finding a program that maps every input to its output. DreamCoder writes programs in a small typed functional language (the lambda calculus with types, the core of languages like Haskell and OCaml) and searches for them by trying candidates in order of how likely they are. It is given 100 to 200 tasks from one domain and cycles through them many times.
Across those cycles it learns two things. The first is a library of new functions written in the language itself, each one built from the starting primitives and from functions learned earlier; the paper calls this declarative knowledge. The second is a neural network, the recognition model, that reads a task's examples and predicts which library functions its program will use; this is procedural knowledge, and it decides the order in which the search tries programs. The paper applies one algorithm to eight domains: list processing, text editing, regular expressions, LOGO turtle graphics, block towers, symbolic regression, recursive programming from 1959 Lisp primitives, and physical laws.
The rest of the page explains the method in this order: why search over programs is expensive, how a library defines a probability for every program, the three phases of the learning cycle (wake, abstraction sleep and dreaming sleep), and the results.
Why program search is hard
A program is a tree of function calls, and a search builds it one call at a time. If each call has about plausible choices and the program has calls, there are about candidates of that size to try. The paper states this in a footnote: the difficulty of search is roughly breadth to the power depth. Two things lower it. A library with higher-level functions lets the same program be written with fewer calls (smaller ), at the cost of more functions to choose from at each call (larger ). A model that predicts which functions a task needs concentrates probability on a few of them (smaller effective ).
For scale, the paper's brute-force baseline enumerates up to 400 million programs per task in 24 hours, about 4,630 programs per second. The paper's sort program needs 32 calls in the starting primitives and 5 in the learned library. With 4 choices per call, 32 calls give candidates, about 126 million years at that rate; 5 calls give 1,024 candidates, a fraction of a second. Even 8 choices per call at depth 5 is 32,768 candidates, 7 seconds.
At 32 calls only below 1.86 fits in 24 hours (). At 5 calls, up to 19 choices per call fit in 10 minutes and up to 52 in 24 hours. Halving divides the count by , so a better guide helps most on deep programs, and the routines a library adds, which raise , stay affordable only while the guide keeps the effective small. The paper's own figure for brute-forcing the 32-call sort is more than years; it comes from the program's actual probability rather than a uniform , and this page does not reproduce it.
A library as a distribution over programs
DreamCoder turns "how likely is this program" into a number by treating the library as a generative model. The library is a pair : a set of functions plus a weight for each function and one weight shared by all variables. To sample a program of a requested type, the generator works top-down (supplement, Algorithm 2). If the type is a function type, it writes a and samples a body of the result type. Otherwise it lists every library function and every in-scope variable whose return type can match the requested type, draws one with probability proportional to for functions and divided by the number of matching variables for variables, and recursively fills in its arguments. Types prune the candidates: a slot that needs an integer never offers cons, which builds lists, so the type system removes most of the breadth before any weight is applied.
This defines the prior , how probable a program is before any task is looked at. It is the product of the program's choice probabilities, so its negative log, the description length, is a sum of per-choice costs, measured in nats (information in natural-log units; 1 nat is 1.44 bits):
A worked example with a seven-function library, map, cdr, cons, nil, car, + and 1, all weights equal, and the request list(int) → list(int). The program is (λ (l) (map (λ (z) (+ z z)) l)), "double every element". The request is a function type, so λ (l) is forced and costs nothing. The body must be a list(int): the candidates are map, cdr, cons, nil, car (whose return type is a type variable, so it can match anything) and the variable l, six in all, and map has probability 1/6. Its first argument is a function, so λ (z) is forced; the body must be an integer, with candidates +, 1, car and z, so + costs 1/4 and each z another 1/4. The second argument of map is a list again, six candidates, and l costs 1/6. The product is , a description length of , or 7.74 nats.
That number is also a search cost. Probabilities sum to at most 1, so at most 2,304 programs can have probability at least , and a search that enumerates programs in decreasing order of probability reaches this one within its first 2,304 candidates. Raising the weight of map or shrinking the candidate lists makes it cheaper; this is how both the library weights and the recognition model speed up search.
The other half of the model is the likelihood of a task given a program. For input/output tasks it is 1 if the program reproduces every example and 0 otherwise. For the regular-expression domain, where a program is a probabilistic generator of strings, it is the probability that the program generates the observed strings. Bayes' rule combines the two into the posterior,
which, among the programs that explain the task, prefers the one with the shortest description.
How DreamCoder works: wake, abstraction, dreaming
The algorithm alternates three updates, which the paper writes together as its Eq. (1). Wake finds a program for each training task , searching among programs the recognition model rates highly for one with high posterior probability:
Abstraction sleep picks the library that makes those programs most probable, after rewriting each program in whatever equivalent form suits the new library best:
Dreaming sleep trains the recognition model to approximate the posterior, on tasks drawn either from the training set (replays) or from the library itself (fantasies):
Figure 2 shows which piece of state each phase reads and which it writes. The four pieces are the tasks, a beam of up to five solutions per task, the library, and the recognition model.
The supplement states what the cycle optimizes. Writing the library as , the target is the joint probability of the library and the tasks, summed over every program that could explain each task:
The sum over all programs is infinite, so DreamCoder keeps a beam of at most 5 programs per task and sums over the beam instead. Dropping terms from a sum of non-negative numbers can only make it smaller, so the beam version is a lower bound on :
Wake raises by adding programs to the beams with the library fixed. Abstraction raises it by changing the library with the beams fixed. Dreaming leaves unchanged and trains so that the next wake phase finds high-posterior programs sooner. The supplement notes that this bound is tighter than the evidence lower bound (ELBO, the bound a VAE maximizes) built from the same beams, by at least the entropy of the beam distributions. In the 1995 wake-sleep algorithm of Hinton, Dayan, Frey and Neal, which the name borrows, the generative model learns during waking and the recognition model during sleep; DreamCoder has two sleep phases and learns its generative model, the library, in one of them.
Wake: searching for programs
Waking is enumeration with a timeout: 12 minutes per task for lists and text, 1 hour for LOGO and towers, 4 hours for physics. The enumerator lists programs in decreasing order of probability under either the library weights or the recognition model's output for the task, runs each finished program on the task's examples, and keeps every program with . To spread the work over many CPUs it runs a best-first search until it has about ten partial programs per CPU, then hands each one to a depth-first worker, and it does this in bands of 1.5 nats of description length (0 to 1.5, then 1.5 to 3, and so on), so the overall order is still approximately most-probable-first.
Each task's beam keeps the five solutions with the highest posterior . A task typically has many solutions (doubling a list can be written with map, with fold, or with explicit recursion), and keeping several lets the abstraction phase compress whichever ones share the most structure with other tasks. The supplement's Algorithm 1 runs wake twice per minibatch: once ordered by the library weights, then, after dream training, once ordered by the recognition model. Minibatches hold 10 tasks for lists and text and 50 for LOGO and towers.
Abstraction: refactoring and compression
The abstraction phase looks for a function that many found programs could share. Shared structure is often invisible in the programs as written. The paper's Fig. 3 example takes two list tasks, double every element and subtract one from every element, solved during waking with only explicit recursion. The two programs differ in the middle, and neither contains map as a subexpression. A rewriting step exposes it:
; Two list tasks, solved during waking with only Y (recursion), if, nil?, cons,
; car, cdr, + and -. Task A: [1 2 3] -> [2 4 6]. Task B: [1 2 3] -> [0 1 2].
(Y (λ (r l) (if (nil? l) nil (cons (+ (car l) (car l)) (r (cdr l)))))) ; A
(Y (λ (r l) (if (nil? l) nil (cons (- (car l) 1) (r (cdr l)))))) ; B
; One refactoring of each: pull the per-element work out as an argument f.
((λ (f) (Y (λ (r l) (if (nil? l) nil (cons (f (car l)) (r (cdr l)))))))
(λ (z) (+ z z)))
((λ (f) (Y (λ (r l) (if (nil? l) nil (cons (f (car l)) (r (cdr l)))))))
(λ (z) (- z 1)))
; The shared function becomes a library routine, and both programs shrink.
map = (λ (f) (Y (λ (r l) (if (nil? l) nil (cons (f (car l)) (r (cdr l)))))))
(map (λ (z) (+ z z))) ; A
(map (λ (z) (- z 1))) ; BThe rewriting runs beta-reduction backwards. Beta-reduction is the lambda calculus's evaluation rule: applying (λ (f) body) to an argument substitutes the argument for f in the body. Run in reverse, it picks a subexpression, replaces it by a fresh variable, and applies the resulting function to that subexpression, which gives a program that evaluates to the same thing. The program (+ 1 1) alone has refactorings like ((λ (x) (+ x x)) 1), ((λ (x) (+ x 1)) 1) and ((λ (x) (x 1 1)) +). Any function abstracted this way is a candidate library routine; the two refactorings in the code block above abstract the same one, map.
DreamCoder allows up to 3 inverse steps per program (4 for the recursive-programming experiment). Even with that bound the number of refactorings explodes: about for the programs in Fig. 3. The paper represents them with a version space, a graph in which shared subtrees are stored once and "union" nodes stand for "any one of these alternatives". It combines version-space algebras from program synthesis with the e-graphs (equivalence graphs) used in compiler optimization. The version space for the Fig. 3 programs has about nodes and takes minutes to build. Its size grows polynomially with program size and exponentially with the number of inverse steps, which is why the step bound is small; the paper reports no loss in performance at 3.
Each subtree of a version space is a candidate routine. For a candidate , the phase forms the library , finds the shortest rewrite of every beam program that uses it, re-estimates the weights, and scores the result. The prior on libraries charges for their size, with for lists, text, regexes, LOGO and towers and elsewhere:
The phase adds the single best candidate, rewrites the beams with it, and repeats, until no candidate raises the score. In the code the score is the log of the beam likelihood under the re-estimated weights, minus times the total size of the library's routines, minus a constant (1.0 by default) per routine. Scoring every candidate exactly would cost time quadratic in the number of programs, so a cheaper beam search first ranks candidates by how short they make the programs, and only the top 300 are scored with weight re-estimation.
The score trades program length against library size, the minimum-description-length principle: adding a routine lowers the total when the description length it removes from programs exceeds times its own size. Figure 3 computes that trade-off for the map example, measuring everything in symbols (primitives, variables and constants). The figure's corpus holds up to four list tasks (double, subtract 1, add 1, square each element); with explicit recursion their programs take 14, 13, 13 and 14 symbols; map itself has 12; each task written with map takes 4.
At the default , map is not worth adding for one task (22 against 14 for keeping the recursive program) and wins from two tasks on (26 against 27). Memorizing each solution as its own routine wins only when routines are cheap: below with two tasks, below 0.29 with four. At , where routines cost nothing, it wins for any number of tasks: without a size penalty the best "library" is a lookup table of the training solutions. That table does nothing for a new task (13 symbols, the same as no library), while map cuts the new task to 4. The paper's Memorize baselines, which add whole solutions as primitives, solve fewer held-out tasks than DreamCoder in every domain.
The weights are re-estimated for every proposal by expectation-maximization, which sets each routine's weight to how often it was used divided by how often it could have been used. A Dirichlet pseudocount smooths both counts, acting as 30 imaginary uses and 30 imaginary opportunities, so a routine seen rarely stays near weight 1. With the expected number of uses of in the beam programs and the expected number of choice points at which was type-compatible, the released code computes
The supplement's Eq. (7) adds only to the numerator. The two versions rank rarely-available routines differently (the Provenance panel works one example), and this page follows the code.
What a learned library looks like
On the list domain (218 tasks split evenly into training and test, 15 examples each) DreamCoder builds about 20 routines, and later routines call earlier ones. Fig. 1B of the paper shows a chain of three. The system first learns concept_4, which is filter: fold over a list and keep the elements that satisfy a predicate. It then learns concept_13, the maximum, written as "the first element such that filtering the list for elements greater than gives the empty list". Then concept_15, which takes a list and a number , keeps the elements that have fewer than smaller elements, and returns their maximum. After six iterations, the sort task is solved by mapping concept_15 over up to the list's length.
The paper labels concept_15 "nth largest element". The elements with fewer than smaller ones are the smallest (more when there are ties), so their maximum is the th smallest, and the sort comes out ascending, as the task examples require: [9 2 7 1] → [1 2 7 9]. Figure 4 shows the program at four levels of inlining and runs the routine on the paper's example lists.
Inlining concept_15 doubles the count from 5 calls to 10. Inlining the maximum doubles it again to 20, because the maximum mentions its argument twice and that argument is now a whole filter expression. Replacing the six remaining filters by fold, if and cons adds two calls each and reaches the paper's 32. Every level evaluates to the same ascending sort. With the learned library the solution was found in under 10 minutes of search.
Dreaming: training the search network
The recognition model is the network that turns a task into search weights. For list, text and regex tasks it reads each example (input, a delimiter, output) with a bidirectional GRU of 64 units over 64-dimensional symbol embeddings and max-pools the final states (the GRU explainer covers that recurrent unit). For LOGO, towers and symbolic regression it uses a convolutional network on the image or plot. An MLP with 128 ReLU units then outputs the weights. It is trained with Adam at learning rate 0.001 for 5,000 steps or one hour, whichever comes first.
Its output is not one weight per routine but one per routine and syntactic context: is the weight of choosing routine as argument of a parent . For a library of 30 routines whose largest arity is 3, that is a tensor of shape (the extra parents are "start" and "variable", the extra child is "variable"), 2,976 numbers per task. The paper calls this a bigram model over syntax trees. The network runs once per task, and the enumerator then uses the table exactly as it would use the library weights, with no further network calls during search. The bigram form lets the model express rules like "never put 0 as an argument of +", which a single weight per routine cannot.
Training data comes from two sources in equal parts. Replays are the training tasks paired with the best programs found for them during waking; they keep the model accurate on the tasks it actually has to solve. Fantasies are new tasks generated from the library: enumerate programs from the library's prior, run each on inputs drawn from the training tasks, and treat the resulting input/output behaviour as a task. With only 100 to 200 real tasks, replays alone are too few to train a network; fantasies are unlimited. Their quality depends on the library, which is one of the two ways the phases bootstrap each other: a richer library produces more varied and domain-like fantasies, and a better network solves more tasks during waking, which gives the next abstraction phase more programs to compress.
Programs sampled from the starting library are mostly short scribbles, which teach the network little about the kinds of images in the training set. Programs from the learned library are polygons, flowers and spirals combined in ways that never appeared in the training images; the paper reports the same contrast for its real LOGO dreams before and after learning and argues that this variety helps the network generalize. A fantasy needs a target program, and DreamCoder does not use the program it happened to sample: it enumerates the prior, groups programs by their input/output behaviour, and keeps for each behaviour the most probable programs that produce it (supplement, Algorithm 5). The next section explains why.
Why the network is trained for MAP
Many syntactically different programs compute the same function. (+ (+ 1 1) 1) and (+ 1 (+ 1 1)) both compute 3, use the same three symbols, and so have the same prior probability. A recognition model trained toward the full posterior, as in classic wake-sleep, learns to spread its probability evenly over all such equivalent forms, and the search then spends time on every one of them. DreamCoder instead trains for MAP (maximum a posteriori), rewarding the model only for the probability it gives to one most probable program:
The expectation is over replays and fantasies. The alternative objective weights the log-probability of every beam program by its posterior (normalized over the beam),
and is maximized when copies the posterior, ties included. The supplement proves (Theorem 6) that the best model under (9) puts all its probability for a task on a single program, and that program maximizes the posterior. Figure 6 shows the two objectives for a task built from additions of 1, whose additions can be bracketed in a Catalan number of ways (2 for , 14 for , 429 for ), all equally probable a posteriori.
The two objectives agree at the even split and disagree everywhere else. The posterior objective is highest at the even split and falls to when the model commits to one form, because the other forms then get probability zero. The MAP objective is lowest at the even split and reaches its maximum, 0, at full commitment. At , committing saves , or 2.64 nats, on the program, which by the counting argument above shrinks the number of candidates the search may try first by a factor of 14.
Committing needs the bigram output, because a rule like "no + as the first argument of +" depends on the parent node. In the supplement's experiment with programs built from +, 0 and 1, the bigram model trained for MAP produced right-associated additions 97.9% of the time and added zero in 2.5% of samples. With the posterior objective, 55.8% and 31.9%. A unigram model (one weight per routine) trained for MAP produced 48.6% right-associated sums and learned to avoid 0 almost entirely (0.5%), even for a task whose answer is 0, because it cannot say "no 0 under +" without saying "no 0 anywhere". Hand-written rules of this kind (no adding zero, one fixed association order) are a standard part of earlier synthesizers; DreamCoder learns them. The supplement notes that the theorem guarantees one canonical form per task, not the same choice across tasks; consistency across tasks comes from the network finding it simpler to break a symmetry the same way everywhere.
Results across eight domains
The comparisons hold out half of each domain's tasks for testing. DreamCoder is compared with two ablations, one without the recognition model and one without abstraction, and with baselines: Exploration-Compression (Dechter et al., 2013), which alternates search and compression but without refactoring; a RobustFill neural synthesizer trained on samples from the initial library; plain type-directed enumeration for 24 hours per task; and the two Memorize variants. In every domain the full system solves the most held-out tasks, with a mean solve time of 54.1 seconds and a median of 15.0. In LOGO graphics (160 images) and block towers (107 tasks), no other model solves more than 60% of held-out tasks while DreamCoder solves nearly all of them. Training to convergence typically takes about a day on 20 to 100 CPUs.
On text editing the system trained on 128 automatically generated tasks and was tested on the 108 problems of the 2017 SyGuS program-synthesis competition, with tasks like "Alan Turing" → "A.T.". Before learning it solved 3.7% within 10 minutes, with an average search time of 235 seconds; after learning, 79.6%, in 40 seconds on average. The competition's best entry, CVC4, solved 82.4% with 1 hour and 8 CPUs per problem; under that budget DreamCoder solved 84.3%. SyGuS also supplies each problem with its own hand-picked primitives, while DreamCoder used one learned library for all of them.
Library depth tracks performance. Across domains, deeper libraries correlate with more tasks solved (r = 0.79), and at every depth the system with a recognition model does better. The recognition model also produces deeper libraries by the end of training, because it solves more training tasks during waking and so gives the abstraction phase more programs to compress.
The generative domains show other kinds of knowledge. In LOGO the learned library contains parametric routines for polygons, circles and spirals, and a higher-order routine for radial symmetry. In towers it contains arches, staircases and bridges. For regular expressions (256 columns of web CSV data, 5 example strings per concept) it learns concepts like phone numbers, dates and dollar amounts: from $5.70, $2.80, $7.60 it generates $2.40 and $3.30. In symbolic regression it fits curves with real-valued parameters, tuned by gradient descent inside the search and penalized with the Bayesian information criterion, so it uses no more parameters than the data support: data from gets a program with three continuous parameters, data from one with two.
Learning a language from scratch
Two experiments start from much less domain knowledge. In the first, the tasks are 60 physical laws and mathematical identities from AP and MCAT physics reference sheets, each given as numerical data that obeys it, and the starting language has a few sequence primitives such as map and fold, plus arithmetic, and no vector operations. After 8 cycles DreamCoder solves 93% of them. It first learns vector operations (inner product, vector sum, norm) and then builds on them, for example an inverse-square-law routine that gives both Newton's law of gravitation and Coulomb's law.
In the second, the starting language is a subset of the primitives of 1959 Lisp (car, cdr, cons and a few more) plus the Y combinator, which provides recursion and so can express any recursive function, but no recursive function is given. The tasks are 20 introductory programming exercises. With roughly five days on 64 CPUs and 4 refactoring steps instead of 3, the system solves all 20 and builds map, fold, zip, length and a function that lists the integers in an interval. It learns fold first, then unfold, and expresses the rest through them. Folds consume a recursive data structure and unfolds generate one; Jeremy Gibbons's 2003 chapter calls programming built on the pair "origami programming".
Cost and limitations
The compute is large for the size of the data. A domain with a few hundred tasks takes about a day on 20 to 100 CPUs, and the origami experiment took about a year of CPU time in total. The paper uses this to argue against learning from a minimal language: it is possible, but expensive, and the authors favour starting from rich general-purpose libraries and growing domain knowledge on top. Hyperparameters were set by an informal coarse search, and the paper names the wake-phase timeout as the setting that matters most.
The method suits problems whose solutions are crisp symbolic programs. The domains include pixel inputs, exceptions in text patterns and continuous parameters, but the paper names noisier real-world data as the main open problem. The task sets are chosen and split by the authors: DreamCoder picks no curriculum of its own and cannot propose new problems to work toward, which the paper lists as a next step. Library learning is greedy, one routine at a time, and scores each library on a beam of 5 programs per task, the bound (6).
The search is still enumeration. The neural network reorders candidates but does not construct programs, so a solution whose description length stays large under both the library and the network remains out of reach within the timeout. The division of labour resembles the policy network in AlphaZero, which sets the priors of a tree search without replacing it; in DreamCoder the language being searched, the library, is learned as well.
Implementation notes
The official implementation is github.com/ellisk42/ec: a Python front end, an OCaml back end for enumeration and compression, and the recognition model in PyTorch. The outer loop, in the order of the supplement's Algorithm 1:
# DreamCoder's outer loop (supplement, Algorithm 1), one minibatch at a time.
library = initial_primitives() # D; weights theta start uniform
beams = {x: [] for x in tasks} # B_x: at most 5 programs per task
while True:
for batch in minibatches(shuffle(tasks), size=B): # B = 10 lists, 50 LOGO
for x in batch: # wake, ordered by prior
beams[x] += [p for p in enumerate_by_prob(prior(library), T)
if likelihood(x, p) > 0]
Q = train_recognition(replays=beams, # dream sleep: 50/50
fantasies=dreams(library, tasks))
for x in batch: # wake, ordered by Q(.|x)
beams[x] += [p for p in enumerate_by_prob(Q(x), T)
if likelihood(x, p) > 0]
beams[x] = top_k(beams[x], 5, key=lambda p: posterior(x, p, library))
library, beams = abstraction(library, beams) # abstraction sleepAnd the abstraction phase, with the score as the code computes it (compression.ml) rather than as Algorithm 4 prints it:
# Abstraction sleep (supplement, Algorithm 4): add one routine at a time.
def abstraction(library, beams, lam=1.5, aic=1.0, n_steps=3):
while True:
vs = {p: version_space(p, n_steps) for p in programs_in(beams)}
cands = top_300(subtrees(vs)) # cheap beam pre-ranking first
def score(D): # higher is better
theta = estimate_weights(D, beams) # EM, Eq. (8)
ll = sum(log(sum(lik(x, p) * prior(shortest(vs[p], D), D, theta)
for p in beams[x])) for x in beams)
return ll - lam * total_size(D) - aic * len(D)
best = max((library | {c} for c in cands), key=score)
if score(best) <= score(library):
return library, beams
library = best # rewrite beams with it
beams = {x: [shortest(vs[p], library) for p in ps]
for x, ps in beams.items()}Per-domain settings from the supplement: wake timeout 2 minutes on 20 CPUs for symbolic regression, 12 minutes on 64 CPUs for lists, text and regexes, 1 hour on 96 (LOGO) or 64 (towers) CPUs, 4 hours on 64 CPUs for physics and recursive programming; minibatches of 10 or 50 tasks, or all unsolved tasks for the last two; of 1.5 or 1; ; beam size 5. The predecessor system, EC² (Ellis et al., NeurIPS 2018), used a unigram recognition model, one weight per routine (supplement, footnote 6); the version-space refactoring is new in DreamCoder.
Questions you might still have
Does a neural network write the programs?
No. Every program comes from enumeration: the search builds syntax trees one choice at a time, in decreasing order of probability, and runs each finished program on the task's examples. The network reads the examples once and outputs a table of weights for those choices, which changes the order of the enumeration. A task counts as solved only when a program reproduces every example.
How is this different from the original wake-sleep algorithm?
In Hinton and colleagues' 1995 algorithm the generative model learns while awake and the recognition model learns while asleep, trained to recover the hidden causes of fantasies sampled from the generative model. DreamCoder learns its generative model, the library, in a sleep phase by compressing programs found while awake. Its recognition model is trained on replays as well as fantasies, and on the most probable program for each fantasy rather than the one that was sampled. The VAE explainer covers the other modern descendant of the Helmholtz machine, where recognition and generation are trained jointly by gradient descent.
Why not add every solved program to the library?
The paper tests that as its Memorize baselines, which add each task solution as a new primitive, with and without a recognition model. They solve fewer held-out tasks than DreamCoder. A memorized solution helps only a task with exactly that solution, while the prior charges for its whole size; a routine like map is charged once and shortens every program that applies a function to each element of a list, including programs for tasks it has not seen.
Does DreamCoder still need a hand-written domain-specific language?
It needs a starting language, chosen per domain: list functions for list processing, pen and loop commands for LOGO, arithmetic with real-valued parameters for symbolic regression. These are generic for their domain and much smaller than what earlier synthesizers used; DreamCoder learns the domain-specific layer on top. The physics and recursion experiments start from less (map, fold and arithmetic; or 1959 Lisp primitives and the Y combinator) at a large compute cost.
How much compute does it take?
Typically about a day on 20 to 100 CPUs to reach the curves in Fig. 6A. Wake-phase search timeouts range from 2 minutes per task (symbolic regression) to 4 hours (physics). Learning functional programming from 1959 Lisp took about five days on 64 CPUs, and the paper puts that whole experiment at roughly a year of CPU time.
In what sense is the learned knowledge interpretable?
Every learned routine is a lambda-calculus expression built from earlier routines, so a person can read it, run it, and check what it does, as with filter, maximum and the sort in Figure 4 here. The system names its routines concept_4, concept_13 and so on; the readable names in the paper were assigned by the authors after reading the code.
Why does the abstraction step need version spaces at all?
To find map, the system must notice that two programs share structure only after each is rewritten into a form with an explicit function argument. The number of such rewrites is about 10^14 for the programs in Fig. 3. A version space stores them as a graph of shared subtrees with union nodes, about 10^6 nodes built in minutes, and candidate routines are read off its subtrees.
Footnotes & further reading
- The paper: Ellis et al., DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning (2020); the conference version, DreamCoder: bootstrapping inductive program synthesis with wake-sleep library learning (PLDI 2021). The paper with its supplement: dreamcoder_with_supplement.pdf.
- Code: ellisk42/ec; the compression score and weight estimator are in solvers/compression.ml.
- Wake-sleep: Hinton, Dayan, Frey & Neal, The "wake-sleep" algorithm for unsupervised neural networks (Science, 1995). Amortized inference with a recognition network trained by gradient descent: the VAE explainer.
- The predecessor: Ellis, Morales, Sablé-Meyer, Solar-Lezama & Tenenbaum, Learning Libraries of Subroutines for Neurally-Guided Bayesian Program Induction (EC², NeurIPS 2018; the DreamCoder paper cites it as "Library learning for neurally-guided Bayesian program induction"). Exploration-Compression: Dechter, Malmaud, Adams & Tenenbaum, Bootstrap learning via modular concept discovery (IJCAI 2013).
- Data structures behind refactoring: Mitchell, Version spaces: a candidate elimination approach to rule learning (IJCAI 1977); Tate, Stepp, Tatlock & Lerner, Equality saturation: a new approach to optimization (POPL 2009).
- Gibbons, Origami programming (in The Fun of Programming, 2003).
How could this explainer be improved? Found an error, or something unclear? I read every message.