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: arxiv.org/abs/2006.08381
Code: 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): bit.ly/tabnine-yannick
KZbin: / yannickilcher
Twitter: / ykilcher
Discord: / discord
BitChute: www.bitchute.com/channel/yann...
Minds: www.minds.com/ykilcher
Parler: parler.com/profile/YannicKilcher
LinkedIn: / yannic-kilcher-488534136
BiliBili: 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: www.subscribestar.com/yannick...
Patreon: / yannickilcher
Bitcoin (BTC): bc1q49lsw3q325tr58ygf8sudx2dqfguclvngvy2cq
Ethereum (ETH): 0x7ad3513E3B8f66799f507Aa7874b1B0eBC7F85e2
Litecoin (LTC): LQW2TRyKYetVC8WjFkhpPhtpbDM4Vw7r9m
Monero (XMR): 4ACL8AGrEo5hAir8A9CeVrW8pEauWvnp1WnSDZxW7tziCDLhZAGsgzhRQABDnFy8yuM9fWJDviJPHKRjV4FWt19CJZN9D4n

[@YannicKilcher]

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

[@prabhanshurajpoot7419]

And one day, after a dreaming phase, the machine wakes up, and asks about the nature of its existence.

[@bluel1ng]

The basic idea of extracting and reusing parts of synthesized programs is pretty old, e.g. in genetic programming it was called Automatically Defined Functions (Koza 1992 ...) - it simply did never work really well in the past (AFAIK). So kudos to these guys if they really found an effective way - it might then also revolutionize genetic programming.

[@freemind.d2714]

Most of important ideas is based on idea in the past, that's why it's call the "research" I guess

[@dewinmoonl]

kevin found a way to burn thousands of dollars on google compute so I'm sure this is the right way aha :D

[@andres_pq]

@Kevin Ellis What do you plan as future work?

[@andres_pq]

Have you tried to use this model for the ARC dataset?

[@jacksonmeeks9313]

This is really cool. I actually created a program that had some similar concepts to this a few years ago, where the nodes in the program tree were weighted so certain functions could "fade in" and "fade out" depending on how useful they were, and it was trained with a genetic algorithm. I actually used it to try and trade stocks, but the search space was so large that it was difficult to get reliable results. It's really cool to see how coherent of a solution the authors were able to create.

[@slackstation]

An amazing paper. Thank you for this presentation. This might seems to be one of the important milestones but, we won't know that until we are well past it and to recognize where the bit steps were.

[@Kram1032]

cons is essentially a comma in a linked list. It's short for "constructor" and usually is a pair of a value and a pointer. So you get the value at that position at the list as well as the location of the next value. For instance, in Haskell, a linked list [a,b,c] is actually just a short hand for what amounts to a cons b cons c cons empty (or written a bit more neatly, a : b : c : [] )

[@JasonRute]

I've really enjoy this paper and its possibilities, and I'm really excited to see you cover it!

[@wagbagsag]

I'm glad you presented this one! I think that program synthesis is greatly under-appreciated in the field.

[@citiblocsMaster]

This is my favorite work/paper of all time. Cool to see you featuring it.

[@nathancooper1001]

Would be interesting to have Kevin Ellis on y'all podcast. He's a very nice dude (have me an hour of his time when I was applying to grad schools) and his work is very fascinating!

[@amirpourmand]

I have a schedule for myself that roughly every day, I will watch one of your videos. All of them are greats. Thanks a lot.

[@23kl104]

super interesting paper. Thanks Yannic. Your videos are so helpful for staying up to date with research. Your work is much appreciated.

[@reneahn5908]

Promising and inspiring, thanks. Clever and "universal" combination of various approaches. I am amazed to see so much aspects of GOFAI in a very recent paper. Nice!

[@freemind.d2714]

This is one step towards efficient explorations, explore in high level concept space

[@drhilm]

Such a great explanation. mind blowing. 🤯

[@trevormartin1944]

Nice, thank you for covering this.

[@jamiekawabata7101]

Incredible! Thank you Yannic!

[@billgalen9014]

So excited about this for discovering learning dynamics in higher ed space!

[@jonatan01i]

I like the birds sounds in the background.

[@johnrobinson5081]

Great explanation of a super interesting paper!

[@nessbrawlaaja]

Really appreciate these!

[@albinoameise]

super interesting paper! Thanks for the explanation

[@bmatichuk]

When I did my MSc (15 years ago) I used Program Refinement (Refinement calculus by Morgan published in 1988), to generate code using planning. I think if you combine refinement with DreamCoder you could get a very robust program synthesis system that could be commercialized. Refinement is a method for converting specifications into code. The problem with specification-based code generation is that the specification is harder to write than the program - which is why it has never been used. By allowing some of the specification to be in the form of input/output examples, this might simplify the specification process. I articulated as much in my thesis, but I wasn't able to get that solved. DreamCoder seems like the answer.

[@willjeremijenko4633]

Could you link to some of the important work in Program Refinement?

[@EugeneMikhantiev]

When LISP inventors claims that LISP is a language for artificial intelligence it seems they was misunderstood. This is not the language to create AI but the language for AI to write programs by himself

[@AThagoras]

Lisp is a cruel joke perpetrated by AI on humanity. It is a language that is easy for machines to parse, but all but the simplest of Lisp programs are not human readable. The AIs are laughing at us.

[@alpers.2123]

Is it easier for AI to write assembler code or lisp code?

[@AThagoras]

@@alpers.2123 Probably Lisp, but it depends on what it is trying to do. If its writing Lisp, it is probably using a small library of simple functions. Much simpler than most assembly languages.

[@piotr780]

During Google AI challenge 'Planet Wars' in 2010 the winner - Bocsimackó (Gábor Melis) have been using lisp due to its expressive power (as he stated), so lisp simply represent language allowing for thinking on higher level of abstraction

[@DamianReloaded]

This is clever. I imagine you could build the library manually and make it start from there. I wonder if a language model could be trained to generate functions given an output. Maybe a language model that works in reverse? One to which you give the last tokens of a series and it predicts what came before? Which'd be really just a NLP model with the data reversed...

[@bluel1ng]

Also worth watching: Kevin Ellis talk about the DreamCoder: kzbin.info/www/bejne/hIqsloNnndOmbKM

[@Mikey-lj2kq]

wow, just wow, i know ramanujan machines and such but this is kinda what i wanna do: encode concepts and use them to solve problems. for the longest time i wanddered across automatic theorem provers and such. but it seems this paper got some nice ideas toward agi.

[@chrisliu254]

Hey, thanks for all this wonderful content! I'm wondering what software you are using for annotating papers?

[@FunBotan]

I refused to accept that I'm too dumb for this and then my brain exploded

[@herp_derpingson]

I wonder if one day we could build an end-to-end differentiable version of this.

[@paulix9960]

This seems a good way to approximate Kolmogorov complexity of a given sequence

[@alitaghibakhshi944]

Hi Yannic. First of all, thanks for the great explanation. You mentioned you reviewed paper(s) that extract physical laws from data. Could you explicitly name those papers? Thanks

[@HoriaCristescu]

I understand the algorithm searches for short solutions, but how is the initial phase bootstrapped given the distance to the goal? (curriculum learning? just by dreaming up to it?)

[@EctoMorpheus]

All that remains now is adding neural primitives that can be trained 🚀

[@marat61]

For me main takeaway is that models should be more structured. Interesting question what results might have RL in case of using such explicit library/cache?

[@theocachet6496]

Hi Yannic. Thanks for the video. I am wondering how they do wrt syntaxically incorrect programs. Do they mask the possible next token during the tree search? Or is it just learnt that the generative program model have to choose tokens that are syntaxically correct? Mask incorrect tokens/concepts could heavily reduce the tree width

[@y__h]

Given unbounded concept library size, What will be the concept number of recursive self-learning?

[@rickybloss8537]

This is dope

[@st33lbird]

needs more transformers

[@ohjumpa]

Nooooooooo

[@billykotsos4642]

lmao

[@jeremykothe2847]

What's a transformer? Where could I find out more about them?

[@DistortedV12]

Finally real research

[@brandomiranda6703]

I vote that you should go through a paper that explains how to expand the library of abstractions! Maybe going through fragment grammars by Timothy O'Donnel et al.?

[@finlayl2505]

My mind is blown

[@ChazAllenUK]

I don’t think it’s correct to say it learns fold/unfold first The researchers are presenting the achieved concept hierarchy after some number of runs, but I believe this is the result of first discovering more complex concepts and then incrementally compressing until it discovers the most fundamental concepts. Still very impressive it can do this! Great paper & thank you for sharing it!

[@rotacidni]

I noticed there were several studies on generating a program to solve a given problem, including this work. However, I wonder if such methods can search over a Turing complete program space. If true, does it mean this method is also able to test any program stops? Is it conflict with halting theory?

[@jabowery]

I thought their language was Turing complete. That is to say the language in which they define domain specific languages.

[@jabowery]

@Kevin Ellis Number sequence induction requires iteration without termination. Program transformation between iteration and, at least tail recursion is a solved problem, is it not?

[@rnoro]

My feeling is this is still in the scope of parametrized-moduli-search structure. The current so called AI system has this similar structure: parametrizing the searching space, which is equivalent to finding a good representation. Then use so called deep learning/neuron-network/function approximation to fit the given data with desired target (a map which can bring data-points to its labels). In this case, the parameter is function/functional programming. The map is program/functionals --> task. The framework is more abstract, but the core idea is still the same.

[@oleg.dats.88]

How do they extend Recognition model by a new concepts? Is the neural network retrained from the ground up each time a new concept arises?

[@TimScarfe]

I'm thinking the neurally guided search would still be a greedy search so like in gpt3 for example, suffer massivly from deception and cycles. There is a lot of work to be done right there

[@brandomiranda6703]

do you have a reference for options in reinforcement learning?

[@marat61]

This also reminds me genetic search, caching good genes and use them letter

[@futurisold]

36:17 the dream phase could generate tons of fonts of alien languages for SF movies or video games.

[@brll5733]

Soooo...Schmidhuber already did this when?

[@jabowery]

His General claim is that current state-of-the-art usually fails to properly cite prior art. This reflects an improper prior on the search for prior art. The sheer volume of work in recent years is overwhelming. A lot of the fundamentals were discovered during the second connectionist summer. The first connectionist summer that Minsky and Papert shut down with "Perceptrons" didn't have much of a chance to get going.

[@brll5733]

@@jabowery He is not wrong, but I think the issue is his presentation. It rubs people wrong.

[@hannesstark5024]

What sort of program will DreamCoder come up with if the problem is actually a dictionary with random keys and values?

[@jabowery]

That depends on the keys and values. If truly random keys and values then it will simply be a hash. Otherwise there is the potential of reaching the kolmogorov complexity description

[@JasonRute]

While real world messy data (44:22) is an important next step, I still have a lot of questions about what DreamCoder is capable of with clean mathematical data. Can it solve the Rubik's cube from scratch as in Agostinelli et al. 2019, providing an algorithm instead of a (slow) neural guided tree search? Can it solve symbolic integration similar to Lample et al. 2019, providing an algorithm instead of a (computationally expensive) language model? Can it solve Euclidean geometry constructions? Can it do symbolic simplification or symbolic rewriting? Can it do basic theorem proving? We need better benchmarks.

[@JanBlok]

Great explanation! Seems made to solve the Kaggle ARC challenge, bit surprised Yannic does not refer to this.

[@Anoyzify]

Didn’t he?

[@EctoMorpheus]

I wonder why Yannick even bothers naming all the authors while they're displayed on the screen anyway. I think he secretly enjoys butchering the names 😏

[@AICoffeeBreak]

"Butchering" is a little harsh, because he still does a pretty good job. Perhaps he does a little research beforehand?

[@fia6559]

She's always defending him lol

[@stochasticmage]

@@AICoffeeBreak Doubtful, considering his pronunciation of "Lucas Morales" when it took me 2 minutes to find this: kzbin.info/www/bejne/hIqsloNnndOmbKM I mean, I'll watch his videos anyway, just... ouch

[@AICoffeeBreak]

@@stochasticmage Haha, when someone knows how to pronounce "Lucas Morales", then it's you. 👍 Ok, you proved it, he doesn't seem to do research. What I just mean to say is: I've seen so much worse than what he does that it does not fall into my "butchering" bucket (yet).

[@emuccino]

@@stochasticmage Morales is a French word. Yannic possibly recognized it as such and so pronounced it the French way. The prior two names were French and likely primed Yannic's interpretation of the name.

[@TechyBen]

"I'm showing you this because I'm particularly good at sorting numbers". Drops mic. Ends video. But more on the topic, *we* have extra context outside of the individual training data. So could we show this list (sorting training data) to an AI that had other data to reference it to?

[@isaacclayton4022]

Holy cow.

[@DistortedV12]

This paper is quite old. I wonder what authors have done since.

[@Nellak2011]

I am very excited to hear about this paper, but imagine so limitations of this. Some problems will remain intractable to this, prime example : Alpha Zero. No amount of programming can beat that, unless it rediscovers what Google did. Does the library prune itself of inefficiencies and redundancies? If Not it could grow into an unweildy mess. Also Does this algorithm converge onto efficient solutions or only the naive solutions to problems?

[@y__h]

My personal heuristics is that this model will get trapped graphing Mandelbrot fractal long before it discovers language modelling.

[@alpers.2123]

Execution time can be added to the loss function to punish inefficiencies maybe

[@swordwaker7749]

The list sorting was selection sort at best, so, I think not yet.

[@swordwaker7749]

@@alpers.2123 Yay... but benchmarking a function at an array size of say... 1000 will be costly. And the researchers will need to make a system which efficiently executes this language. Understanding of virtual machine will probably be required.

[@Nellak2011]

@@y__h What do you mean by language modelling?

[@G12GilbertProduction]

Nine-numerical systems of 1x6 bit code referral reduction is being probably goes this group: {9, 18, 72 ... 156} - and was being finite. But group sorting is really unequal them to 0.8 subitation rate in eventually recombination of group from {156, 86, 72 ... 9} and so on, but he was still finite.

[@alpers.2123]

Combine this with GPT3 and CLIP then connect to the internet

[@justfoundit]

I'm kind of scared of this option, but it will happen eventually. At the end of the day it will write its own programs too, driving Teslas remotely, just for fun. I'm a big fun of AGI, but I would like it to get to that point with our supervision.

[@jabowery]

Better than that would be to devote 10% of the resources that have gone into Hardware specialized for deep learning instead toward Hardware specialized toward this kind of program search.

[@justfoundit]

@@jabowery Absolutely, I love the idea.

[@alpers.2123]

Well, give it tensorflow primitives, then feed it with deep learning problems...

[@scottmiller2591]

"All you need is Genetic Programming"

[@lukkuuu6368]

muzero

[@josegois9124]

Ocan's razor

[@alpers.2123]

First