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

#dreamcoder​ #programsynthesis​ #symbolicreasoning​

Classic Machine Learning struggles with few-shot generalization for tasks where humans can easily generalize from just a handful of examples, for example sorting a list of numbers. Humans do this by coming up with a short program, or algorithm, that explains the few data points in a compact way. DreamCoder emulates this by using neural guided search over a language of primitives, a library, that it builds up over time. By doing this, it can iteratively construct more and more complex programs by building on its own abstractions and therefore solve more and more difficult tasks in a few-shot manner by generating very short programs that solve the few given datapoints. The resulting system can not only generalize quickly but also delivers an explainable solution to its problems in form of a modular and hierarchical learned library. Combining this with classic Deep Learning for low-level perception is a very promising future direction.

OUTLINE:

0:00​ - Intro & Overview

4:55​ - DreamCoder System Architecture

9:00​ - Wake Phase: Neural Guided Search

19:15​ - Abstraction Phase: Extending the Internal Library

24:30​ - Dreaming Phase: Training Neural Search on Fictional Programs and Replays

30:55​ - Abstraction by Compressing Program Refactorings

32:40​ - Experimental Results on LOGO Drawings

39:00​ - Ablation Studies

39:50​ - Re-Discovering Physical Laws

42:25​ - Discovering Recursive Programming Algorithms

44:20​ - Conclusions & Discussion

Paper: https://arxiv.org/abs/2006.08381​

Code: https://github.com/ellisk42/ec​

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.

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

Links:

TabNine Code Completion (Referral): http://bit.ly/tabnine-yannick​

YouTube: https://www.youtube.com/c/yannickilcher​

Twitter: https://twitter.com/ykilcher​

Discord: https://discord.gg/4H8xxDF​

BitChute: https://www.bitchute.com/channel/yann...​

Minds: https://www.minds.com/ykilcher​

Parler: https://parler.com/profile/YannicKilcher​

LinkedIn: https://www.linkedin.com/in/yannic-ki...​

BiliBili: https://space.bilibili.com/1824646584​

If you want to support me, the best thing to do is to share out the content :)

If you want to support me financially (completely optional and voluntary, but a lot of people have asked for this):

SubscribeStar: https://www.subscribestar.com/yannick...​

Patreon: https://www.patreon.com/yannickilcher