DreamCoder: Wake & Sleep Program Learning

JS disabled! Watch DreamCoder: Wake & Sleep Program Learning on Youtube

Why Code with Neural Networks?

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

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)

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

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’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++

• Inference of Regular Expressions for Text Extraction from Examples (2016)
• given texts and extractions
• Genetic Programming search for regular expressions
• try demo

Regex Generator++ Solution search

• 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

Continue

• DreamCoder’s author video
• Expire-Span solves reinforcement-learning-like problems with a transformer memory