Vaclav Kosar's face photo
Vaclav Kosar
Software, Machine Learning, & Business

DreamCoder: Wake & Sleep Program Learning

Learning to code by growing function library, fantasising coding tasks, and training neural search.

Why Code with Neural Networks?

  • Regression is not enough. Neural Networks are missing System 2:
  • humans can
    • think algorithmically using symbols
    • accumulate “knowledge” from small amount of samples
  • GAI via symbolic + neural? (Francois Chollet)

Wiki disambiguation problem and submodularity

How DreamCoder Works?

  • DreamCoder uses:
    • learned library of functions
    • learned neural search on the program space
  • Such that:
    • given inputs-output examples
    • produces the best solution
    • and learns from that

Why DreamCoder?

  • builds on RobustFill and DeepCoder
  • DeepCoder does not predict the probability of a program
  • DeepCoder predicts DSL primitive will be used in the program at least once
  • DeepCoder & DreamCoder libraries are
    • modestly-sized set
    • generally useful routines
    • interpretable routines

DreamCoder’s The Best Program Definition

  • program search space is too large
  • short program given previously useful functions is the best
  • So, DreamCoder
    • growths library of functions that compress valid solutions
    • learns neural guided search

DreamCoder vs AlphaZero

Similarities to AlphaZero:

  • also trains a neural search
  • also does “self-play” (Dream phase)
Solved domains from the DreamCoder paper
Solved domains (sourced from the paper)

How is DreamCoder Trained?

  1. provide program primitives (map, fold, if, cons, >)
  2. wake phase:
    1. search for the best solution given the library
    2. store successful solutions
  3. sleep phase
    1. abstract
      1. replay successful solutions
      2. compress them by adding to library
    2. dream:
      1. generate & replay programs
      2. train neural search
  4. Loop to wake phase

Visualization of DreamCoder Training

DreamCoder Training phases
Training phases (sourced from the paper)

Wake Phase

  • neural network \( Q \) ranks potential solutions
    • given input-outputs and programs returns probability
    • called recognition model
  • the best solution:
    • many programs solve
    • select 5 smallest programs
    • use for next sleep

Abstraction phase:

  • propose new library functions
  • minimizing the new functions
  • minimizing the length of solutions
  • reduce number of refactorings \( \sim 10^{14} \)
    • ideas from:
      • version space algebras
      • equivalence graphs
    • plus limit to small programs
    • lead to improvement \( \sim 10^6 \)

Dream Phase:

  • replay programs ~100s
  • 50/50 mixing generated and replay programs
  • to augment data but stay representative
  • train Q function for search
DreamCoder logo task
DreamCoder LOGO task (A: tasks, B & C: learned functions, D & E: dreams. (sourced from the paper)

DreamCoder’s Results

  • list processing
    • primitives: map, fold, cons (pre-pend), …
    • 109 training tasks
    • created library of 20 routines
      • filter, max, n-th largest
    • learned to sort
  • text editing
    • e.g. “Alan Turing” -> “A.T.”
    • train set: 128 auto-generated text editing task
    • test set: 2017 SyGuS program synth
    • prior-train solved 3.7%
    • post-training solved 84.3% vs 82.4% prior art
      • CVC4 competition
      • others used handpicked library from SysGuS
      • DreamCoder used only primitives + training samples
      • but is that really better?
  • Ablations:
    • abstraction & dreaming are important

Bonus Paper: Regex Generator++

  • regex is represented by a tree
  • nodes are
    • sub-node placeholder *
    • primitives (\d, \w, [*], [^*], look-around, …)
  • tree structure is DNA of the candidates
  • keep only performing candidates ~ library in DreamCoder
  • genetic crossover via swap of candidates’ sub-trees
  • genetic mutation via replacement of a subtree with random subtree
  • fitness is “Character Precision”, “Character Accuracy”, length of the expression (~ DreamCoder’s code length)

Regex Generator++ vs GP-Regex and Others

  • the method outperforms, but not on all datasets
  • solution time is human comparable ~10 minutes


Created on 27 Apr 2021.

Let's connect

Privacy Policy How many days left in this quarter? Twitter Bullet Points to Copy & Paste