Elamur Research⌕
☰
home / papers / 2020 / DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning

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

Paper · 2020 · Kevin Ellis, Catherine Wong, Maxwell Nye et al.

Summary

Program induction treats learning a task as finding a program that produces the desired behavior. It generalizes well from a few examples and yields knowledge humans can read. In practice, though, it has relied on hand-crafted domain-specific languages (DSLs) and search procedures tuned to them. DreamCoder learns both instead. Starting from a sparse set of generic primitives, it cycles through three phases:

  • Wake: a neural recognition model guides the search for programs that solve training tasks.
  • Abstraction sleep: recurring fragments of the solutions found are extracted and added to a growing library, which acts as the prior over programs.
  • Dream sleep: the network is retrained on replayed tasks and on "fantasy" tasks sampled from the library.

Across eight domains, including classic list-processing synthesis, picture drawing and scene building, the system builds layered, interpretable libraries in which new concepts reuse older ones. It also rediscovers core ideas of functional programming, vector algebra and classical physics. This points to program learning as a scalable, data-efficient way to accumulate reusable symbolic knowledge.

Key points

  • Learns two kinds of expertise together: an explicit library (the DSL, a Bayesian prior over programs) and implicit search skill (a neural network that approximates the posterior). It extends the authors' earlier EC² algorithm.
  • In the list domain, cycling through 109 tasks produced a library of roughly 20 list operations. After six iterations, "Sort List" was solved with five calls to learned functions in under 10 minutes. The same program written in the initial primitives needs 32 calls and would take over 10^72 years of brute-force search.
  • New tasks are typically specified by only 5–10 examples, or by a single image or scene.
  • Among the physics results, it recovered Newton's and Coulomb's laws from minimal starting primitives.
  • Compute cost is high: building the "origami" functional-programming library took about a year of total CPU time. The authors therefore favor richer built-in starting knowledge over learning from scratch.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelf 1The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 works

Cite

Cite as Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lucas Morales, Luke Hewitt, Armando Solar-Lezama and Joshua B. Tenenbaum. 2020. DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning. arXiv:2006.08381.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2006.08381 · arXiv 2006.08381

@misc{ellis2020dreamcoder,
  title = {{DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning}},
  author = {Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lucas Morales, Luke Hewitt, Armando Solar-Lezama and Joshua B. Tenenbaum},
  year = {2020},
  doi = {10.48550/arxiv.2006.08381},
  eprint = {2006.08381},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2006.08381}
}

References

61 references, 6 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Alan M Turing. Computing machinery and intelligence. Mind, 1950. find
  2. Ray J Solomonoff. A formal theory of inductive inference. Information and control, 7(1):1–22, 1964. find
  3. Percy Liang, Michael I. Jordan, and Dan Klein. Learning dependency-based compositional semantics. In ACL, pages 590–599, 2011. find
  4. Tejas D Kulkarni, Pushmeet Kohli, Joshua B Tenenbaum, and Vikash Mansinghka. Picture: A probabilistic programming language for scene perception. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4390–4399, 2015. find
  5. Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350(6266):1332–1338, 2015. find
  6. Nick Chater and Mike Oaksford. Programs as causal models: Speculations on mental programs and mental representation. Cognitive Science, 37(6):1171–1191, 2013. find
  7. Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. In ACM SIGPLAN Notices, volume 46, pages 317–330. ACM, 2011.
  8. Miguel Lázaro-Gredilla, Dianhuan Lin, J Swaroop Guntupalli, and Dileep George. Beyond imitation: Zero-shot task transfer on robots by learning concepts as cognitive programs. Science Robotics, 4(26):eaav3150, 2019. find
  9. Jacob Devlin, Rudy R Bunel, Rishabh Singh, Matthew Hausknecht, and Pushmeet Kohli. Neural program meta-induction. In NIPS, 2017. find
  10. Yadin Dudai, Avi Karni, and Jan Born. The consolidation and transformation of memory. Neuron, 88(1):20 – 32, 2015. find
  11. Magdalena J Fosse, Roar Fosse, J Allan Hobson, and Robert J Stickgold. Dreaming and episodic memory: a functional dissociation? Journal of cognitive neuroscience, 15(1):1–9, 2003. find
  12. Geoffrey E Hinton, Peter Dayan, Brendan J Frey, and Radford M Neal. The ”wake-sleep” algorithm for unsupervised neural networks. Science, 268(5214):1158–1161, 1995. find
  13. Eyal Dechter, Jon Malmaud, Ryan P. Adams, and Joshua B. Tenenbaum. Bootstrap learning via modular concept discovery. In IJCAI, 2013. find
  14. Percy Liang, Michael I. Jordan, and Dan Klein. Learning programs: A hierarchical bayesian approach. In ICML, 2010. find
  15. Matej Balog, Alexander L Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. ICLR, 2016. find
  16. Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. ICML, 2017. find
  17. Kevin Ellis, Lucas Morales, Mathias Sablé-Meyer, Armando Solar-Lezama, and Josh Tenenbaum. Library learning for neurally-guided bayesian program induction. In NeurIPS, 2018. find
  18. Tessa Lau, Steven A Wolfman, Pedro Domingos, and Daniel S Weld. Programming by demonstration using version space algebra. Machine Learning, 53(1-2):111–156, 2003. find
  19. Tom M Mitchell. Version spaces: A candidate elimination approach to rule learning. In Proceedings of the 5th international joint conference on Artificial intelligence-Volume 1, pages 305–310. Morgan Kaufmann Publishers Inc., 1977. find
  20. Oleksandr Polozov and Sumit Gulwani. Flashmeta: A framework for inductive program synthesis. ACM SIGPLAN Notices, 50(10):107–126, 2015. find
  21. Ross Tate, Michael Stepp, Zachary Tatlock, and Sorin Lerner. Equality saturation: a new approach to optimization. In ACM SIGPLAN Notices, volume 44, pages 264–276. ACM, 2009. find
  22. Armando Solar Lezama. Program Synthesis By Sketching. PhD thesis, 2008.
  23. John K Feser, Swarat Chaudhuri, and Isil Dillig. Synthesizing data structure transformations from input-output examples. In PLDI, 2015. find
  24. Rajeev Alur, Dana Fisman, Rishabh Singh, and Armando Solar-Lezama. Sygus-comp 2017: Results and analysis. arXiv preprint arXiv:1711.11438, 2017. — [arXiv:1711.11438](https://arxiv.org/abs/1711.11438) find
  25. M. M. Bongard. Pattern Recognition. Spartan Books, 1970. find
  26. Douglas Hofstadter and Gary McGraw. Letter spirit: An emergent model of the perception and creation of alphabetic style. 1993. find
  27. Jean Raven et al. Raven progressive matrices. In Handbook of nonverbal assessment, pages 223–237. Springer, 2003. find
  28. David D. Thornburg. Friends of the turtle. Compute!, March 1983. find
  29. Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojciech Zaremba, and Pieter Abbeel. Domain randomization for transferring deep neural networks from simulation to the real world. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 23–30. IEEE, 2017. find
  30. Patrick Winston. The MIT robot. Machine Intelligence, 1972. find
  31. Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181–211, 1999. find
  32. Gary F Marcus, Sugumaran Vijayan, S Bandi Rao, and Peter M Vishton. Rule learning by seven-month-old infants. Science, 283(5398):77–80, 1999. find
  33. Brenden Lake, Chia-ying Lee, James Glass, and Josh Tenenbaum. One-shot learning of generative speech concepts. In Proceedings of the Annual Meeting of the Cognitive Science Society, volume 36, 2014. find
  34. Luke Hewitt and Joshua Tenenbaum. Learning structured generative models with memoised wake-sleep. under review, 2019. find
  35. Christopher M. Bishop. Pattern Recognition and Machine Learning. Springer-Verlag New York, Inc., 2006. find
  36. Andrew Cropper. Playgol: Learning programs through play. IJCAI, 2019. find
  37. Michelene TH Chi, Paul J Feltovich, and Robert Glaser. Categorization and representation of physics problems by experts and novices. Cognitive science, 5(2), 1981.
  38. M.T.H. Chi, R. Glaser, and M.J. Farr. The Nature of Expertise. Taylor & Francis Group, 1988. find
  39. Herbert A Simon, Patrick W Langley, and Gary L Bradshaw. Scientific discovery as problem solving. Synthese, 47(1):1–27, 1981. find
  40. Pat Langley. Scientific discovery: Computational explorations of the creative processes. MIT Press, 1987. find
  41. Michael Schmidt and Hod Lipson. Distilling free-form natural laws from experimental data. science, 324(5923):81–85, 2009. find
  42. Jeremy Gibbons. Origami programming. 2003. find
  43. Kevin Ellis, Daniel Ritchie, Armando Solar-Lezama, and Joshua B Tenenbaum. Learning to infer graphics programs from hand-drawn images. NIPS, 2018. find
  44. Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska-Barwińska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, et al. Hybrid computing using a neural network with dynamic external memory. Nature, 538(7626):471, 2016. find
  45. Lazar Valkov, Dipak Chaudhari, Akash Srivastava, Charles Sutton, and Swarat Chaudhuri. Houdini: Lifelong learning as program synthesis. In Advances in Neural Information Processing Systems, pages 8687–8698, 2018. find
  46. Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Neural module networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 39–48, 2016.
  47. Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic programming. In Advances in Neural Information Processing Systems, pages 3749–3759, 2018.
  48. Halley Young, Osbert Bastani, and Mayur Naik. Learning neurosymbolic generative models via program synthesis. arXiv preprint arXiv:1901.08565, 2019. — [arXiv:1901.08565](https://arxiv.org/abs/1901.08565) find
  49. Reuben Feinman and Brenden M. Lake. Generating new concepts with hybrid neuro-symbolic models, 2020. find
  50. Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In ICML, 2009.
  51. Jeffrey L Elman. Learning and development in neural networks: The importance of starting small. Cognition, 48(1):71–99, 1993. find
  52. Jonathan St BT Evans. Heuristic and analytic processes in reasoning. British Journal of Psychology, 75(4):451–468, 1984. find
  53. Daniel Kahneman. Thinking, fast and slow. Macmillan, 2011. find
  54. Ray J Solomonoff. A system for incremental learning based on algorithmic probability. Sixth Israeli Conference on Artificial Intelligence, Computer Vision and Pattern Recognition, 1989. find
  55. Jürgen Schmidhuber. Optimal ordered problem solver. Machine Learning, 54(3):211–254, 2004. find
  56. Marcus Hutter. Universal artificial intelligence: Sequential decisions based on algorithmic probability. Springer Science & Business Media, 2004. find
  57. Jerry A Fodor. The language of thought, volume 5. Harvard University Press, 1975. find
  58. Steven Thomas Piantadosi. Learning and the language of thought. PhD thesis, Massachusetts Institute of Technology, 2011. find
  59. Brenden M Lake, Tomer D Ullman, Joshua B Tenenbaum, and Samuel J Gershman. Building machines that learn and think like people. Behavioral and brain sciences, 40, 2017. find
  60. Elizabeth S Spelke, Karen Breinlinger, Janet Macomber, and Kristen Jacobson. Origins of knowledge. Psychological review, 99(4):605, 1992. find
  61. Susan Carey. The origin of concepts: A précis. The Behavioral and brain sciences, 34(3):113, 2011. Supplement. Supplementary materials available at https://web.mit.edu/ellisk/www/dreamcodersupplement.pdf. Acknowledgments. We thank L. Schulz, J. Andreas, T. Kulkarni, M. Kleiman-Weiner, J. M. Tenenba… ↗

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/ellis-2020-dreamcoder-growing-generalizable-interpretable-knowledge/