DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning
deep learning machine learning arxiv explained neural networks artificial intelligence wake sleep algorithm program synthesis ai program synthesis program synthesis deep learning dreamcoder dream coder mit dream coder bayesian program search neural guided search learning to sort a list neural networks learn sorting deep learning physical laws deep learning symbolic reasoning symbolic machine learning symbolic artificial intelligence deep learning tutorial
#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/yannic-kilcher
Minds: https://www.minds.com/ykilcher
Parler: https://parler.com/profile/YannicKilcher
LinkedIn: https://www.linkedin.com/in/yannic-kilcher-488534136/
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/yannickilcher
Patreon: https://www.patreon.com/yannickilcher
Bitcoin (BTC): bc1q49lsw3q325tr58ygf8sudx2dqfguclvngvy2cq
Ethereum (ETH): 0x7ad3513E3B8f66799f507Aa7874b1B0eBC7F85e2
Litecoin (LTC): LQW2TRyKYetVC8WjFkhpPhtpbDM4Vw7r9m
Monero (XMR): 4ACL8AGrEo5hAir8A9CeVrW8pEauWvnp1WnSDZxW7tziCDLhZAGsgzhRQABDnFy8yuM9fWJDviJPHKRjV4FWt19CJZN9D4n
 Hi there, I have a little challenge for you right here. Look at these numbers and see if you can figure out what comes where the question mark is. Now, if you look at it a little bit, you'll recognize that this is the sorting algorithm. You're supposed to sort these numbers in ascending order, and that's going to be the solution. Why I'm showing you this isn't because it's particularly hard or because I'm particularly good at sorting numbers. It is because this is a core feature of human intelligence that we haven't been able to reach with machine learning quite yet. We are able to look at very few examples and then generalize to new examples. We do that not by the way machine learning does it by gradient descent into a model, but we do it by coming up with a rule such as, hey, this is sorting. Even if we didn't know what sorting was, we would be able to come up with the rule nevertheless, because we would realize, I need to compare the numbers and I need to pick the lowest one first, and then the second lowest one second, and so on. We humans are able to come up with rules to solve the problem, and in more general sense, we're able to come up with a program, with an algorithm that solves the problem. That is the point of this paper, to solve problems not with pure brute force machine learning like gradient descent from a dataset but with coming up with rules with algorithms to solve the problem. Now, this brings its inherent challenges. It's not a new approach, but this paper makes it more scalable than before. The paper is called Dream Coder, Growing Generalizable Interpretable Knowledge with Wake Sleep Bayesian Program Learning. It's by Kevin Ellis, Catherine Wong, Maxwell Nye, Matthias Sable-Meier, Luke Carey, Luca Moral, Luke Hewitt, Armando Soler-Lesema, and Joshua B. Tenbaum. Again, the paper says itself, we present Dream Coder, 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. The entire model is going to be a system that sees problems, just a few of them, and comes up with programs that solve these problems. It does so in its own language. It builds up its own programming language, and then it's able to synthesize programs in this language that solve the problem. It does so by having a neural network guide that search. That's Dream Coder. It includes this wake-sleep algorithm, which has been also around for a while, but it's a different take on it. The wake-sleep learning algorithm alternatively extends the language with new symbolic abstractions and trains the neural network on imagined and replayed problems. The past ventures into program synthesis have all been not really scalable, because either they have some handcrafted programming language that you search over, or they have handcrafted rules of how you search, and so on. This system here is much more general, and it can solve a vast variety of different tasks. For example, here you can see the different types of tasks that the system can solve. There is list processing. Sorry, that's a bit heavy. There's list processing, such as summing lists, doubling each element, check for evens, text editing, learning regex for stuff, and also very creative things like creating graphics, creating block towers, regressing symbolically, recursive programming, and figuring out physical laws. We've already looked at paper that figure out physical laws from data, but they have been geared towards that. This is the same system that can figure out all of these things. Now, of course, it's going to be configured a little bit differently if you talk about list processing versus figuring out physical laws, but it is the same underlying system. Ultimately, what does that amount to? That amounts to you giving the system a problem. Let's say the problem right here is... What do we have here? To sort a list. That's what we came up with at the beginning. Here you have the problem of sorting a list. You're going to give the program a few examples, like three like I gave you at the beginning, and the system is going to come up with a program. The program ultimately is going to look like the thing down here. It's going to come up with a program that implements the list sorting algorithm. It's going to do that by a few principles. Principle one, of course, it needs to fit all of the examples. It needs to explain all of the examples, otherwise it's not a correct program. And concept two is it needs to be easy. It needs to be very, very explainable in the sense of it needs to be very short, because there are many different rules that these lists follow. I can come up with... I can literally create this as a hash table. I can implement this as a hash table for these three lists, and that hash table would solve the problem exactly as well as the sorting algorithm. Now, the sorting algorithm is much more compact. It's simply... Well, it's this thing down here. And beyond that, what the system does is it builds up a library of concepts. So not only... The system doesn't see the program at the bottom. The system actually sees this program right here. So this is the sorting algorithm in the system's language, because the system has built up a learned library of concepts over time. So as we train the system to solve different tasks on lists, such as sum a few things, double a few things, and so on, it builds up this library of concepts. So there are these primitives right here that you give it, and then it's able to come up with these concepts that we as programmers might call functions. So it's able to come up with a thing that can filter a list. It doesn't have it in its initial primitives, but it's able to discover that because it uses it again and again and again. And now it's able to use that function instead of the primitives. So whereas before, it would have used the entire code in this thing, now it's just able to say, well, I want to use concept four right here. And that makes the programs that are written much shorter. So it uses this to implement the maximum function, which it calls concept 13. Of course, it has no concept of what we name function. And then it's able to use concept 13 and concept four together to implement the nth largest element function. And once I have the nth largest element function, I can simply iterate from the beginning. I have a list, I simply iterate over its length. So I iterate that, and I always use the nth largest number. And that will sort my list. So you can see that the program that sorts the list is super short in terms of this library we've built up. So this is our challenge for building this system. We somehow need a system that is able to come up with programs to solve problems, that is able to build up a library, and that is able to efficiently search through that self-built up library of concepts. And DreamCoder does all of this at the same time. So DreamCoder has three different stages in which these things are tackled. So imagine you have a data set of tasks. So the tasks here are these Xs. So X are the tasks. Now, the tasks can either be, as I understand it, of a single thing like list sorting, right? But they can also be the general class of list problems, which makes more sense in our class. So imagine we have the general class of list problems. Now, it maintains, as we said, this library L. And you can really imagine this as a programming library. So it contains functions that the program can call. And it also contains all the primitives that you give it. So there are going to be a bunch of... So this is going to be like a set. There are going to be a bunch of primitives like a plus b, a minus b, a times b. That's in terms of math, right? Here we're in lists. And there's also going to be a section down here that the program can fill itself. So the program can define a function that's like 2a plus b, right? And then it's able to call that. So that's the library right here. Now, what the system needs to do is it's given a task. So the task here, as you can see, is a few examples of... I don't even know what it does here. Do you know what it does? It kind of reverses the list and adds one or subtracts one, something like this. Yeah, I think it reverses the list and then it adds one, right? That's the task that we handle right here. You can see all of these things is reversing and adding. I've actually not solved that before, so it might be wrong. So what we have to do is we have to come up with a program that solves these tasks, right? That if we give the left side as an input, the right side appears. And that is hard. That is a hard problem because we start right here with an empty program and we build up a search tree. Now every single one of those rules here could be applied, right? So the program could be... Let's take the... Or yeah, let's say these are not math things, but these are list things. So I guess reversing is one of them, map is another one, but you get the point. So you have you put these rules here and you apply, you could apply the first rule, right? You could build a program made up out of the first rule. You could build a program made up of the second or the third. Now if you already have, so here your program is A plus B. If you have that, you could then again apply the first rule, which would give you A plus, sorry, A plus A plus B. You could apply the second rule, which would give you A plus A minus B, right? I'm just substituting kind of the second element right here. This is obviously implemented in a functional programming language that makes all of this really well defined. I'm just kind of showing it in easy mode, right? But you get the point. I can arbitrarily search through this tree and I can apply each of those rules over and over and over again. You can already see that this is going to give me a massive search tree. How am I going to solve these problems in these kind of massive trees? And that's where the neural network comes in. It's actually the only part in the system that is machine learned as far as I understand it or at least that is neural networked since machine learning isn't only deep learning. But the search through a discrete space that is really large is hard, but you as a human are able to do it. How are you able to do it? You have an intuition, right? You have some intuition that, you know, here, for example, the lists appear to be the same length if you look at the problem. So you know, you look at that and you say, well, maybe there's something with the ordering, maybe the first corresponds to the first or the first to the last or something like this. So you have some kind of intuition of which rules you want to apply. And this intuition, whenever you say intuition in a program, that's a prime place to put in a neural network. So if you know alpha go or alpha zero, that is exactly what it does, right? It is here at a particular chess board, right? And it could do all of these different moves. But it cannot brute force search all of the game tree because that would be impossible. It's computationally too expensive. So what it does is it employs a neural network that tells it, well, this here looks promising, you know, off the bat, and this one doesn't, this one doesn't, this one looks promising, and so on. And then you only go down those two. And from there, again, you have many options, but the neural network eliminates almost all of them and tells you which ones look promising. So if the neural network is a good guide, that enables you to quickly build a program that might solve the problem. So you do that, you search, you search, a newly guided search, you propose programs in decreasing order under your model. So this here, this is your guiding model. This is a likelihood model, like how likely is a program given the task that you're trying to solve, you try the most likely one first, and then you go down. So you search for the best program, which in this case means the program that solves the task, but is also the shortest, right? The intuition is always that a very short program is going to be, is going to be the better program, because it's a kind of a simpler explanation, right? So here, the fewer steps you make in your search, that's a better program. And the more the neural network likes the program, that's a better program, because the neural network is trained for this, right? So the best pro and you come up with the best program for the task. So you choose the program that maximizes the likelihood of the program given the task and the library, which is proportional if you apply Bayes rule to the likelihood of the likelihood that the program generates the solution, which this is just one or zero. If you have a, if you have a non probabilistic program, and then this here, the likelihood of generating a program from your library is just going to be proportional to the number of steps, the number of search steps that you need to make. Okay. So that's the wake algorithm in the wake phase, you try to solve the problem from the training set. You, sorry, you try to solve the, the tasks by coming up with programs that solve them. Now that gives you a data set of solved programs, right? So initially you're going to have a data set of tasks. You're going to run this through the wake phase. And most of the time you're probably going to fail, right? Most of the time it's like, no, can't solve it. But some of the time you're going to succeed. So you're going to have a little bit of a data set of where you've actually succeeded. And this data set is now going to be the, the input into the sleep phases. So what do the sleep phases do? And the sleep phases are crucial here, because if you only, if you only have the guided search, that's already okay. That's already good, right? But it's not going to help you to build more complex programs, because those are still, if you look at the program that is the list sorting program down here, like this is so large, you can never get here with search at least, you know, not in a reasonable time. You need to construct these abstract concepts, because this program here is much shorter. This short program is much shorter than the long program. And you can only get there by building these, these useful concepts by building up the library. So in the sleep phase, we're going to build, first of all, build up the library, which means we're going to take this data set that we've constructed, like here are all the things that we could solve. Now we're going to take that. And what we're going to do is we're going to look at our solutions. And we're going to compress them grow library to compress programs found during waking. Okay, so here we have a bunch of primitives, this is all the stuff we can do. Now we're going to see which of the things that we use often in combination with each other. So if we did very often dead, like, apply the first rule twice, right? So if we applied a plus b, and then we applied a plus b again, which would amount to a plus a plus b, which is to a plus b, we can say, since I use these two rules, we can say, since I use these two rules in conjunction very often, I'm going to make a new rule in my library, that allows me to simply apply this with just one step instead of two. So I'm going to add to a plus b to my library. Because now, since I already know I need those two often together, I, this is simply going to be just a single rule in reinforcement learning, this is sometimes called an option. So it's kind of a higher order action that you can take. And it is, you know, it's, it's, there, there's a lot of work trying to get these options. So what they do right here is sort of the same, it's a compression step. So they're trying to compress the programs that you found during the wake phase. So here you can see an example of this, you have a program for task one, and a program for task two. These don't necessarily even need to be the same tab, like they don't need to be the same. They don't need to come from the same task description, right? But it's just kind of from the same data set. And you notice that you've used this subroutine right here, the orange subroutine in both programs. What they do is they extract this subroutine into the library. And they have special algorithms for this. This is not an easy thing. So they have a very efficient way to search through these program trees, recognize commonalities and extract those. They don't describe that in the paper. But it is it is not a trivial trivial thing to do this. However, imagine that you can just do this. And then you expand your library. So mathematically, you expand the library with the routine that maximizes the following. So you essentially want to do two things. This here is simply the the p of the library itself is simply how large the library is. So you want to you want to keep your library small, right? If you could just add things at will, your search problem would again become too large because you have all these rules you could apply. So you only want to keep the best rules. But then also, you want to maximize this right here over refactorings of the programs that you found. So you want to keep programs. Again, this first term simply means the programs actually solve the tasks that you have. So there, if it's probabilistic, it's different. But we will just say the programs need to solve the tasks that you've encountered. And also, the programs need to be reasonably short given your library, right? And the given your library, you've already seen this before in the wake algorithm right here. This is the same term. And the important thing is that is given your library, right? A program that the sorting program up top isn't short. It's like it's freaking long. But the the program, the same program, given the library is really short because I can use this concept 15 from the library and the concept 15 in itself can again use the concept 13 and the concept four. So the gray box right here will be kind of the size of your library, right? Because this is all the concept. And then the orange box on the right would be the length of the program itself given the library, these two things combined need to be small, which makes sense. So you extend your library by the rules that are themselves small in terms of the library that are used often that solve a lot of problems. And that don't grow your library too much. So now that you've come up with new new rules, you're going to the third phase, and they call this dreaming. So dreaming this, this would already be I think this would already be enough and they do ablations where they leave out different parts right here. But a thing you can do if you have this, essentially, you have a DSL for your problems, right? And what you can do if you have a DSL is you can just apply, you can just build programs at random, right? You can just take a bunch of rules and apply them. And if you do that, you if de facto generate new, new problems to solve. So if usually during the wake phase, you have an input x and you have an output y, and you ask yourself, which program solves this, right? And these come from the data set. But this right here is built from a grammar, right? There's a grammar, which is your library. So your library builds those programs. Now what I can do is I can simply I can simply instead of doing the search tree thing, I can just apply a bunch of those rules, I can just simply start here and apply rule one, then apply rule two, apply rule five, and so on. And that's going to give me a program. I can apply that program to some input data that comes also from my training set is going to give me some different output data because it's a different program. But this now gives me another training data point. It's not from the real program. But I don't care, right? I can train my neural network to I can train my neural network. Now it's again, let's find this program. I can train my neural network to get better at finding programs because I know the program in this case, right? The difference between in the wake phase, I don't know what my program is. In the dream phase, I construct the program. So I know what the neural network should suggest as my steps, right? Here it should suggest of all the options, it should suggest the first one. Here it should suggest the third one, and so on. So I can do supervised learning of my neural network to to learn to search better in the space of programs by coming up with my own programs, and therefore generating my own training data. That's exactly what this dreaming phase does. So in the dreaming phase, actually, we're going to take two things. So we're going to train this neural network, which which they call the recognition model. And you can see, this is this is the thing that guides your search to predict the best programs for typical tasks and the current library. And typical tasks means either tasks that we sample or tasked with the input from the training set. But, you know, we come up with the output ourselves. So this what I've just described, they call fantasies, draw programs from the library. So construct the program, set task x to the output of executing the program, and then learn, learn, given x, I want the program P train the neural network to come up with the program P since I know what the program was. Or alternatively, I can again use these tasks that I solved correctly, right here. And I can use those as a training data set. Since I already I know that I just like I don't necessarily know that the program is the correct one. I just know that the program I came up with is able to solve the examples that I had. But it's good enough, right? It's good enough to act as a data set as well. And we do that to keep ourselves grounded in reality. We can't just start, you know, start dreaming up fantasies, because the fantasies, it's sort of a cycle. And like, this is a cycle, we come up with a library of like a language to describe the problems. And then we use the language to generate new problems. And then we use those generated problems to train our neural network. If we were to only do that, the danger is that we kind of drift away from reality and that our neural network learns very well to search through our imagined things. But you know, as soon as something real comes along, it's so different from what we imagined, it's no longer viable. That's why we also use the replays. And I think they use a 5050 mix of fantasies and replays. The reason why they even use fantasies is to be more data efficient. So you could do all of these things without the fantasy dreaming stage by simply training the neural network on successful replays. But that would be much more data inefficient. So yeah, it's sort of a house of cards that you build up. And I feel it depends a lot on many things right here. Like it depends a lot on the primitives that you give beforehand. It depends a lot on the tasks you choose and how well they are suited. It depends on the language itself, like how you can apply the rules. Of course, the paper is trying to tell us that the same basic algorithm can solve a lot of these tasks. But I still think the tasks are very suited to what the network does. And the network is or the system is built a lot with tasks like that in mind. And that leads to the that leads to this opportunity that you can even do this dreaming, because you can only do this dreaming thing if you know if constructing problems out of your library right here out of your library L is is useful for training your recognition model. If that were not useful, this algorithm would probably work much worse. But as it turns out for these problems, it's useful. So here you see another example of this abstraction step. So we have we have two tasks in the in the wake phase that the the system solved by the way, there is a little bit of a mistake here. But you know, we're we're humans, we can we can successfully work our way around this problem, which, yeah. So there are, you know, these these, the wake phase has actually solved both by coming up with programs. And now the the sleep the abstraction phase is able to search through a giant number of refactorings in order to come up with this primitive, the map primitive. And they stress again, so their algorithm that they have for this compression, which they don't explain necessarily in this paper, but is is able to wade through a giant number of possible refactorings to come up with these common sub algorithms. It's not as easy as simply looking at comparing trees. It's actually much harder because you can refactor programs in many different ways, as especially if you have a sufficiently general programming language like this one right here. So ultimately, it would extract this map primitive. And then you can see that both programs immediately become a lot shorter, like the the top program. Sorry, the left one is this and the right one is this. Once you have the primitive, they become super duper easy. So in terms of experiments, what they do is they they apply this, as we said, to these kind of list tasks, but also to these drawing tasks. And here the primitives aren't as much plus and minus and so on, or these languages that you've seen, the primitives are much more like you have a pen. And you know, it is at a point and you're able to kind of move the pen in very basic forms, I imagine. So it's sort of a descriptive descriptive language of a vector graphic. And you can see right here. So this is these logo graphic tasks, the model writes programs controlling a pen that draws the target picture. So that's just these are the tasks. The task is simply get me a program that draws these pictures. Okay, those are the tasks you can see they are fairly diverse. So there is a lot of things that you somehow have to have to get in order to be able to draw this. And when they analyze what the algorithm comes up with during training of on these tasks is that it discovers these primitives. So the primitives if they analyze the library after training contains things like the semicircle function. So the algorithm comes up with a function that takes a value or and draws a semicircle with the given radius, you can see that depending on the value of our the semicircle is larger, right? It all it comes up with primitives like I can draw a Greek spiral, I can draw an S curve. And so on. It also comes up with so what do you see in C right here. So each row, sorry, each row and B shows the same code executed with different parameters. Each image in C shows the same code executed with different parameters and a different sub program. So it is able to to come up with higher order functions that so functions that take another function as an input in this case, the the radial symmetry function that takes in a number n and a lower order function, and it will replicate that lower order function in in kind of a circle manner. So this, it comes it comes up with these things by itself. Now, again, this is pretty cool, by the way. And at the bottom, you can see what the dreaming phase comes up with. So at the beginning, you can see that the programs that the dreaming phase comes up with are fairly simple, right? And as the library grows, so grows the complexity of the programs it's able to come up with. So this is sort of a built in curriculum that the model has. It starts by constructing problems from its own library, given that at the beginning, the library is pretty primitive. It, you know, it doesn't do much, but over time, it does. Now here you can, by the way, I think the the pen starts at the dark and goes to the light like the color coding is where the pen starts and ends. And I'm not I'm not sure the exact direction they stated. So yeah, it's starts at blue and finishes at pink. Okay, and you can this is during super early, like this doesn't need many iterations. So illustrate the most interesting dreams found across five runs. Oh, sorry, no across five runs both before and after learning. But the sort of the iterations that it takes aren't that many to find solutions to new programs. But you can see, I feel right, this is just my opinion, that if you look at the problems, and if you look at the primitives that the thing comes up with, you probably see like I see that the person or the system who came up with these tasks is constructed in much the same way as these sort of primitives, like probably the person that came up with the tasks wrote a little DSL, saying, okay, you know, I'm gonna, you know, have a semicircle function, and that's going to be parameterized, and so on. And no, so these, these problems themselves are sort of generated by already by a DSL or by a human that has kind of this DSL in mind and applies it. And therefore, I think that's what I said when I said it's probably the system is very geared towards these problems, because what it's going to end up doing, it's going to end up kind of rediscovering how the data was generated. And that makes me a bit so so the question now is, does is this going to work on data that wasn't generated in this way? Or alternatively, you can ask, does the universe have a structure like this? And there's good arguments like it like it can discover physical laws. So here, it can also do, by the way, the same thing with these tower buildings. And you can see the primitives it's discovering are things like build an arch, build a wall, build a pyramid, like those are primitives and with arguments, and the different arguments will give you different structures right here is very cool. And these are the dreams down here, what it comes up with. So it's, you know, pretty intricate dreams, the combination of those rules. Now, again, the question is, does this work on let's say, real world data? And I feel that is, you know, is real world data? Does it behave similarly? And you know, maybe, I don't know. Yeah. So here you can see a bunch of ablations where they show that if you for example, if you're missing the abstraction, you won't get very far very often. For example, in these in these logo graphics, you see pretty clearly that without abstraction or without dreaming, you won't you won't get very far, especially I feel that abstraction hurts quite a bit. Because if you can't abstract, you're only going to go so far in constructing programs. So you can't construct large programs, even if you have a very good neural network guiding your search. And lastly, they go about, as I said, discovering sort of physical laws, and they sort of rediscover physical laws from numerical inputs. And that's what I mean, maybe the world is actually like this, at least that's how we humans solve problems, right? We search for a simple, simple explanation to the things that we see. And you know, science has been very successful, especially, you know, Newton has described, Newton's second law is like literally this big. So and it describes a whole lot of interesting physics. And you know, similarly, lots of other physical laws, which is kind of an unsolved mystery why everything is so simple. But given that it is a program like this might very well be appropriate, so our program search system might very well be appropriate. You know, that being said, it probably can't out of the box solve computer vision or something like this. And they admit that in the in the in the last part here, but just look at kind of the primitives it discovers itself. So just from the initial primitives that you see right here, like map zip, call, I don't even know what that is, like I'm not into functional programming. But from the initial primitives, it discovers the concept of subtracting vectors, adding vectors, dividing by two, and so on. From those, it constructs things like the square root function, which, you know, it's pretty remarkable. And from those, it discovers things like the inverse square law. And you can then see that, for example, Newton's second law is only a combination of, you know, very few applications of library rules. So it's an exceptionally short program, given this library. And also Coulomb's law, you can see, it's just kind of two rules applied to the four inputs, which if you expand this, it's a fairly large program. But because you have this library built up, it's it's a short program. And they do one other experiment where they give it so they they do recursive programming algorithms, like list operations again, but they only give it like the bare minimum that according to functional programming theory, as far as I understand it, you these are the real the primitives you need to solve the problems. And specifically, what it does is it first discovers the fold and unfold functions. So fold is also called reduce, I think if like that's a more common name. First it discover these these and from these, it builds all the other ones. And they say, if you go and you look at kind of functional programming theory, that's exactly what they say is necessary. So they say, given fold and unfold, you can sort of build all the other ones and these primitives. And again, you can see list difference function is very super duper short in terms of this, if you have this library. So if you've discovered the zip function, and that expands to a program that is fairly long that you would never reach with even with neural guided program search. And not only like reaching it is one point, but then you also have to recognize that that is actually the correct one. Right. And you do that as a human by looking how short it is. And this is not a short program, like you could building this as a hash table is shorter than this program. So you would rather take the hash table, I guess, if you just have two examples, rather than the program, but given that you have all this library, the zip a minus b is actually much shorter than encoding it as a hash table. All right, so they say, you know, the real world data, they say that here, much real world data is far messier. A key challenge for program induction going forward is to handle more pervasive noise and uncertainty by leaning more heavily on probabilistic and neural AI approaches. Recent research has explored program induction with various hybrid neuro symbolic representations and integrating these approaches with the library learning and bootstrapping capacities of DreamCoder could especially be valuable going forward. And I agree this. So we if it's not out yet, we had Francois Chollet on the machine learning street talk. And if you if you know him, he came up with this this arc challenge where you do like it's almost the same thing as DreamCoder does, except with these kind of pictures. And you assume that humans have this thing called core knowledge, which they also allude to in this paper. And core knowledge is things like an intuitive understanding of physics and objectness and so on. So one of the arc challenge things is like, there's kind of a thing here. And there's a thing here. And then the solution, the solution to that is there's again the thing here. And that, so that's the solution, right. And you can already see from one example, it's kind of like a ball bouncing off the wall. And you do that by applying your core knowledge, so to say. So this, again, is very, very clean data. So the in arc, I think everything is super clean data, and they say, you know, if we want to apply this to real world problems. And this is also something that Chollet has said in the podcast, which I invite you to listen to as soon as it's out, is that we're going to have to combine this search. So the the DreamCoder, it does kind of the search, which the search over a DSL. So and the DSL is learned, right. Now what we need, this is kind of these are different layers. What deep learning usually does is this perception. So deep learning is really good at doing perception. So this is current deep learning. And this up here is what DreamCoder does, or generally, program synthesis approaches do. And we need a way to connect the two. So we need a way to learn these jointly, because that's what you as a as a human some somehow do. You're able to learn your perception model, which is kind of a perceiving model, and your your logic model, your reasoning model at the same time, or just jointly in some way. And we haven't exactly figured out how to do that yet. And I feel, and I agree with this paper, that is probably going to be a very valuable thing to do. All right, so let me know what you think about this paper, I invite you to read it. It is it is high level, right. But there are some other cool things in it, like the DreamCoder learning reg exes for different types of numbers and so on. But yeah, I think it's an interesting field. It's a bit different from just kind of core machine learning. And that was it. I'll see you next time. Bye.
 Hi there, I have a little challenge for you right here.
 Look at these numbers and see if you can figure out what comes where the question mark is.
 Now, if you look at it a little bit,
 you'll recognize that this is the sorting algorithm.
 You're supposed to sort these numbers in ascending order,
 and that's going to be the solution.
 Why I'm showing you this isn't because it's particularly hard or because I'm
 particularly good at sorting numbers.
 It is because this is a core feature of
 human intelligence that we haven't been able to reach with machine learning quite yet.
 We are able to look at very few examples and then generalize to new examples.
 We do that not by the way machine learning does it by gradient descent into a model,
 but we do it by coming up with a rule such as,
 hey, this is sorting.
 Even if we didn't know what sorting was,
 we would be able to come up with the rule nevertheless,
 because we would realize,
 I need to compare the numbers and I need to pick the lowest one first,
 and then the second lowest one second, and so on.
 We humans are able to come up with rules to solve the problem,
 and in more general sense, we're able to come up with a program,
 with an algorithm that solves the problem.
 That is the point of this paper,
 to solve problems not with pure brute force machine learning like gradient descent from
 a dataset but with coming up with rules with algorithms to solve the problem.
 Now, this brings its inherent challenges.
 It's not a new approach,
 but this paper makes it more scalable than before.
 The paper is called Dream Coder,
 Growing Generalizable Interpretable Knowledge with Wake Sleep Bayesian Program Learning.
 It's by Kevin Ellis, Catherine Wong, Maxwell Nye,
 Matthias Sable-Meier, Luke Carey,
 Luca Moral, Luke Hewitt,
 Armando Soler-Lesema, and Joshua B. Tenbaum.
 Again, the paper says itself,
 we present Dream Coder,
 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.
 The entire model is going to be a system that sees problems,
 just a few of them,
 and comes up with programs that solve these problems.
 It does so in its own language.
 It builds up its own programming language,
 and then it's able to synthesize programs in this language that solve the problem.
 It does so by having a neural network guide that search.
 That's Dream Coder.
 It includes this wake-sleep algorithm,
 which has been also around for a while,
 but it's a different take on it.
 The wake-sleep learning algorithm alternatively extends the language with
 new symbolic abstractions and trains
 the neural network on imagined and replayed problems.
 The past ventures into program synthesis have all been not really scalable,
 because either they have some handcrafted programming language that you search over,
 or they have handcrafted rules of how you search, and so on.
 This system here is much more general,
 and it can solve a vast variety of different tasks.
 For example, here you can see
 the different types of tasks that the system can solve.
 There is list processing.
 Sorry, that's a bit heavy.
 There's list processing,
 such as summing lists,
 doubling each element, check for evens,
 text editing, learning regex for stuff,
 and also very creative things like creating graphics,
 creating block towers, regressing symbolically,
 recursive programming, and figuring out physical laws.
 We've already looked at paper that figure out physical laws from data,
 but they have been geared towards that.
 This is the same system that can figure out all of these things.
 Now, of course, it's going to be configured a little bit differently
 if you talk about list processing versus figuring out physical laws,
 but it is the same underlying system.
 Ultimately, what does that amount to?
 That amounts to you giving the system a problem.
 Let's say the problem right here is...
 What do we have here?
 To sort a list.
 That's what we came up with at the beginning.
 Here you have the problem of sorting a list.
 You're going to give the program a few examples,
 like three like I gave you at the beginning,
 and the system is going to come up with a program.
 The program ultimately is going to look like the thing down here.
 It's going to come up with a program
 that implements the list sorting algorithm.
 It's going to do that by a few principles.
 Principle one, of course, it needs to fit all of the examples.
 It needs to explain all of the examples,
 otherwise it's not a correct program.
 And concept two is it needs to be easy.
 It needs to be very, very explainable
 in the sense of it needs to be very short,
 because there are many different rules that these lists follow.
 I can come up with...
 I can literally create this as a hash table.
 I can implement this as a hash table for these three lists,
 and that hash table would solve the problem
 exactly as well as the sorting algorithm.
 Now, the sorting algorithm is much more compact.
 It's simply...
 Well, it's this thing down here.
 And beyond that, what the system does
 is it builds up a library of concepts.
 So not only...
 The system doesn't see the program at the bottom.
 The system actually sees this program right here.
 So this is the sorting algorithm in the system's language,
 because the system has built up a learned library of concepts over time.
 So as we train the system to solve different tasks on lists,
 such as sum a few things, double a few things, and so on,
 it builds up this library of concepts.
 So there are these primitives right here that you give it,
 and then it's able to come up with these concepts
 that we as programmers might call functions.
 So it's able to come up with a thing that can filter a list.
 It doesn't have it in its initial primitives,
 but it's able to discover that because it uses it again and again and again.
 And now it's able to use that function instead of the primitives.
 So whereas before, it would have used the entire code in this thing,
 now it's just able to say,
 well, I want to use concept four right here.
 And that makes the programs that are written much shorter.
 So it uses this to implement the maximum function,
 which it calls concept 13.
 Of course, it has no concept of what we name function.
 And then it's able to use concept 13 and concept four together
 to implement the nth largest element function.
 And once I have the nth largest element function,
 I can simply iterate from the beginning.
 I have a list, I simply iterate over its length.
 So I iterate that, and I always use the nth largest number.
 And that will sort my list.
 So you can see that the program that sorts the list is super short
 in terms of this library we've built up.
 So this is our challenge for building this system.
 We somehow need a system that is able to come up with programs to solve problems,
 that is able to build up a library,
 and that is able to efficiently search through that self-built up library of concepts.
 And DreamCoder does all of this at the same time.
 So DreamCoder has three different stages in which these things are tackled.
 So imagine you have a data set of tasks.
 So the tasks here are these Xs.
 So X are the tasks.
 Now, the tasks can either be, as I understand it,
 of a single thing like list sorting, right?
 But they can also be the general class of list problems,
 which makes more sense in our class.
 So imagine we have the general class of list problems.
 Now, it maintains, as we said, this library L.
 And you can really imagine this as a programming library.
 So it contains functions that the program can call.
 And it also contains all the primitives that you give it.
 So there are going to be a bunch of...
 So this is going to be like a set.
 There are going to be a bunch of primitives like a plus b, a minus b, a times b.
 That's in terms of math, right?
 Here we're in lists.
 And there's also going to be a section down here that the program can fill itself.
 So the program can define a function that's like 2a plus b, right?
 And then it's able to call that.
 So that's the library right here.
 Now, what the system needs to do is it's given a task.
 So the task here, as you can see, is a few examples of...
 I don't even know what it does here.
 Do you know what it does?
 It kind of reverses the list and adds one or subtracts one, something like this.
 Yeah, I think it reverses the list and then it adds one, right?
 That's the task that we handle right here.
 You can see all of these things is reversing and adding.
 I've actually not solved that before, so it might be wrong.
 So what we have to do is we have to come up with a program that solves these tasks, right?
 That if we give the left side as an input, the right side appears.
 And that is hard.
 That is a hard problem because we start right here with an empty program and we build up
 a search tree.
 Now every single one of those rules here could be applied, right?
 So the program could be...
 Let's take the...
 Or yeah, let's say these are not math things, but these are list things.
 So I guess reversing is one of them, map is another one, but you get the point.
 So you have you put these rules here and you apply, you could apply the first rule, right?
 You could build a program made up out of the first rule.
 You could build a program made up of the second or the third.
 Now if you already have, so here your program is A plus B. If you have that, you could then
 again apply the first rule, which would give you A plus, sorry, A plus A plus B. You could
 apply the second rule, which would give you A plus A minus B, right?
 I'm just substituting kind of the second element right here.
 This is obviously implemented in a functional programming language that makes all of this
 really well defined.
 I'm just kind of showing it in easy mode, right?
 But you get the point.
 I can arbitrarily search through this tree and I can apply each of those rules over and
 over and over again.
 You can already see that this is going to give me a massive search tree.
 How am I going to solve these problems in these kind of massive trees?
 And that's where the neural network comes in.
 It's actually the only part in the system that is machine learned as far as I understand
 it or at least that is neural networked since machine learning isn't only deep learning.
 But the search through a discrete space that is really large is hard, but you as a human
 are able to do it.
 How are you able to do it?
 You have an intuition, right?
 You have some intuition that, you know, here, for example, the lists appear to be the same
 length if you look at the problem.
 So you know, you look at that and you say, well, maybe there's something with the ordering,
 maybe the first corresponds to the first or the first to the last or something like this.
 So you have some kind of intuition of which rules you want to apply.
 And this intuition, whenever you say intuition in a program, that's a prime place to put
 in a neural network.
 So if you know alpha go or alpha zero, that is exactly what it does, right?
 It is here at a particular chess board, right?
 And it could do all of these different moves.
 But it cannot brute force search all of the game tree because that would be impossible.
 It's computationally too expensive.
 So what it does is it employs a neural network that tells it, well, this here looks promising,
 you know, off the bat, and this one doesn't, this one doesn't, this one looks promising,
 and so on.
 And then you only go down those two.
 And from there, again, you have many options, but the neural network eliminates almost all
 of them and tells you which ones look promising.
 So if the neural network is a good guide, that enables you to quickly build a program
 that might solve the problem.
 So you do that, you search, you search, a newly guided search, you propose programs in decreasing
 order under your model.
 So this here, this is your guiding model.
 This is a likelihood model, like how likely is a program given the task that you're trying
 to solve, you try the most likely one first, and then you go down.
 So you search for the best program, which in this case means the program that solves
 the task, but is also the shortest, right?
 The intuition is always that a very short program is going to be, is going to be the
 better program, because it's a kind of a simpler explanation, right?
 So here, the fewer steps you make in your search, that's a better program.
 And the more the neural network likes the program, that's a better program, because
 the neural network is trained for this, right?
 So the best pro and you come up with the best program for the task.
 So you choose the program that maximizes the likelihood of the program given the task and
 the library, which is proportional if you apply Bayes rule to the likelihood of the
 likelihood that the program generates the solution, which this is just one or zero.
 If you have a, if you have a non probabilistic program, and then this here, the likelihood
 of generating a program from your library is just going to be proportional to the number
 of steps, the number of search steps that you need to make.
 Okay.
 So that's the wake algorithm in the wake phase, you try to solve the problem from the training
 set.
 You, sorry, you try to solve the, the tasks by coming up with programs that solve them.
 Now that gives you a data set of solved programs, right?
 So initially you're going to have a data set of tasks.
 You're going to run this through the wake phase.
 And most of the time you're probably going to fail, right?
 Most of the time it's like, no, can't solve it.
 But some of the time you're going to succeed.
 So you're going to have a little bit of a data set of where you've actually succeeded.
 And this data set is now going to be the, the input into the sleep phases.
 So what do the sleep phases do?
 And the sleep phases are crucial here, because if you only, if you only have the guided search,
 that's already okay.
 That's already good, right?
 But it's not going to help you to build more complex programs, because those are still,
 if you look at the program that is the list sorting program down here, like this is so
 large, you can never get here with search at least, you know, not in a reasonable time.
 You need to construct these abstract concepts, because this program here is much shorter.
 This short program is much shorter than the long program.
 And you can only get there by building these, these useful concepts by building up the library.
 So in the sleep phase, we're going to build, first of all, build up the library, which
 means we're going to take this data set that we've constructed, like here are all the things
 that we could solve.
 Now we're going to take that.
 And what we're going to do is we're going to look at our solutions.
 And we're going to compress them grow library to compress programs found during waking.
 Okay, so here we have a bunch of primitives, this is all the stuff we can do.
 Now we're going to see which of the things that we use often in combination with each
 other.
 So if we did very often dead, like, apply the first rule twice, right?
 So if we applied a plus b, and then we applied a plus b again, which would amount to a plus
 a plus b, which is to a plus b, we can say, since I use these two rules, we can say, since
 I use these two rules in conjunction very often, I'm going to make a new rule in my
 library, that allows me to simply apply this with just one step instead of two.
 So I'm going to add to a plus b to my library.
 Because now, since I already know I need those two often together, I, this is simply going
 to be just a single rule in reinforcement learning, this is sometimes called an option.
 So it's kind of a higher order action that you can take.
 And it is, you know, it's, it's, there, there's a lot of work trying to get these options.
 So what they do right here is sort of the same, it's a compression step.
 So they're trying to compress the programs that you found during the wake phase.
 So here you can see an example of this, you have a program for task one, and a program
 for task two.
 These don't necessarily even need to be the same tab, like they don't need to be the same.
 They don't need to come from the same task description, right?
 But it's just kind of from the same data set.
 And you notice that you've used this subroutine right here, the orange subroutine in both
 programs.
 What they do is they extract this subroutine into the library.
 And they have special algorithms for this.
 This is not an easy thing.
 So they have a very efficient way to search through these program trees, recognize commonalities
 and extract those.
 They don't describe that in the paper.
 But it is it is not a trivial trivial thing to do this.
 However, imagine that you can just do this.
 And then you expand your library.
 So mathematically, you expand the library with the routine that maximizes the following.
 So you essentially want to do two things.
 This here is simply the the p of the library itself is simply how large the library is.
 So you want to you want to keep your library small, right?
 If you could just add things at will, your search problem would again become too large
 because you have all these rules you could apply.
 So you only want to keep the best rules.
 But then also, you want to maximize this right here over refactorings of the programs that
 you found.
 So you want to keep programs.
 Again, this first term simply means the programs actually solve the tasks that you have.
 So there, if it's probabilistic, it's different.
 But we will just say the programs need to solve the tasks that you've encountered.
 And also, the programs need to be reasonably short given your library, right?
 And the given your library, you've already seen this before in the wake algorithm right
 here.
 This is the same term.
 And the important thing is that is given your library, right?
 A program that the sorting program up top isn't short.
 It's like it's freaking long.
 But the the program, the same program, given the library is really short because I can
 use this concept 15 from the library and the concept 15 in itself can again use the concept
 13 and the concept four.
 So the gray box right here will be kind of the size of your library, right?
 Because this is all the concept.
 And then the orange box on the right would be the length of the program itself given
 the library, these two things combined need to be small, which makes sense.
 So you extend your library by the rules that are themselves small in terms of the library
 that are used often that solve a lot of problems.
 And that don't grow your library too much.
 So now that you've come up with new new rules, you're going to the third phase, and they
 call this dreaming.
 So dreaming this, this would already be I think this would already be enough and they
 do ablations where they leave out different parts right here.
 But a thing you can do if you have this, essentially, you have a DSL for your problems, right?
 And what you can do if you have a DSL is you can just apply, you can just build programs
 at random, right?
 You can just take a bunch of rules and apply them.
 And if you do that, you if de facto generate new, new problems to solve.
 So if usually during the wake phase, you have an input x and you have an output y, and you
 ask yourself, which program solves this, right?
 And these come from the data set.
 But this right here is built from a grammar, right?
 There's a grammar, which is your library.
 So your library builds those programs.
 Now what I can do is I can simply I can simply instead of doing the search tree thing, I
 can just apply a bunch of those rules, I can just simply start here and apply rule one,
 then apply rule two, apply rule five, and so on.
 And that's going to give me a program.
 I can apply that program to some input data that comes also from my training set is going
 to give me some different output data because it's a different program.
 But this now gives me another training data point.
 It's not from the real program.
 But I don't care, right?
 I can train my neural network to I can train my neural network.
 Now it's again, let's find this program.
 I can train my neural network to get better at finding programs because I know the program
 in this case, right?
 The difference between in the wake phase, I don't know what my program is.
 In the dream phase, I construct the program.
 So I know what the neural network should suggest as my steps, right?
 Here it should suggest of all the options, it should suggest the first one.
 Here it should suggest the third one, and so on.
 So I can do supervised learning of my neural network to to learn to search better in the
 space of programs by coming up with my own programs, and therefore generating my own
 training data.
 That's exactly what this dreaming phase does.
 So in the dreaming phase, actually, we're going to take two things.
 So we're going to train this neural network, which which they call the recognition model.
 And you can see, this is this is the thing that guides your search to predict the best
 programs for typical tasks and the current library.
 And typical tasks means either tasks that we sample or tasked with the input from the
 training set.
 But, you know, we come up with the output ourselves.
 So this what I've just described, they call fantasies, draw programs from the library.
 So construct the program, set task x to the output of executing the program, and then
 learn, learn, given x, I want the program P train the neural network to come up with
 the program P since I know what the program was.
 Or alternatively, I can again use these tasks that I solved correctly, right here.
 And I can use those as a training data set.
 Since I already I know that I just like I don't necessarily know that the program is
 the correct one.
 I just know that the program I came up with is able to solve the examples that I had.
 But it's good enough, right?
 It's good enough to act as a data set as well.
 And we do that to keep ourselves grounded in reality.
 We can't just start, you know, start dreaming up fantasies, because the fantasies, it's
 sort of a cycle.
 And like, this is a cycle, we come up with a library of like a language to describe the
 problems.
 And then we use the language to generate new problems.
 And then we use those generated problems to train our neural network.
 If we were to only do that, the danger is that we kind of drift away from reality and
 that our neural network learns very well to search through our imagined things.
 But you know, as soon as something real comes along, it's so different from what we imagined,
 it's no longer viable.
 That's why we also use the replays.
 And I think they use a 5050 mix of fantasies and replays.
 The reason why they even use fantasies is to be more data efficient.
 So you could do all of these things without the fantasy dreaming stage by simply training
 the neural network on successful replays.
 But that would be much more data inefficient.
 So yeah, it's sort of a house of cards that you build up.
 And I feel it depends a lot on many things right here.
 Like it depends a lot on the primitives that you give beforehand.
 It depends a lot on the tasks you choose and how well they are suited.
 It depends on the language itself, like how you can apply the rules.
 Of course, the paper is trying to tell us that the same basic algorithm can solve a
 lot of these tasks.
 But I still think the tasks are very suited to what the network does.
 And the network is or the system is built a lot with tasks like that in mind.
 And that leads to the that leads to this opportunity that you can even do this dreaming, because
 you can only do this dreaming thing if you know if constructing problems out of your
 library right here out of your library L is is useful for training your recognition
 model.
 If that were not useful, this algorithm would probably work much worse.
 But as it turns out for these problems, it's useful.
 So here you see another example of this abstraction step.
 So we have we have two tasks in the in the wake phase that the the system solved by the
 way, there is a little bit of a mistake here.
 But you know, we're we're humans, we can we can successfully work our way around this
 problem, which, yeah.
 So there are, you know, these these, the wake phase has actually solved both by coming up
 with programs.
 And now the the sleep the abstraction phase is able to search through a giant number of
 refactorings in order to come up with this primitive, the map primitive.
 And they stress again, so their algorithm that they have for this compression, which
 they don't explain necessarily in this paper, but is is able to wade through a giant number
 of possible refactorings to come up with these common sub algorithms.
 It's not as easy as simply looking at comparing trees.
 It's actually much harder because you can refactor programs in many different ways,
 as especially if you have a sufficiently general programming language like this one right here.
 So ultimately, it would extract this map primitive.
 And then you can see that both programs immediately become a lot shorter, like the the top program.
 Sorry, the left one is this and the right one is this.
 Once you have the primitive, they become super duper easy.
 So in terms of experiments, what they do is they they apply this, as we said, to these
 kind of list tasks, but also to these drawing tasks.
 And here the primitives aren't as much plus and minus and so on, or these languages that
 you've seen, the primitives are much more like you have a pen.
 And you know, it is at a point and you're able to kind of move the pen in very basic
 forms, I imagine.
 So it's sort of a descriptive descriptive language of a vector graphic.
 And you can see right here.
 So this is these logo graphic tasks, the model writes programs controlling a pen that draws
 the target picture.
 So that's just these are the tasks.
 The task is simply get me a program that draws these pictures.
 Okay, those are the tasks you can see they are fairly diverse.
 So there is a lot of things that you somehow have to have to get in order to be able to
 draw this.
 And when they analyze what the algorithm comes up with during training of on these tasks
 is that it discovers these primitives.
 So the primitives if they analyze the library after training contains things like the semicircle
 function.
 So the algorithm comes up with a function that takes a value or and draws a semicircle
 with the given radius, you can see that depending on the value of our the semicircle is larger,
 right?
 It all it comes up with primitives like I can draw a Greek spiral, I can draw an S curve.
 And so on.
 It also comes up with so what do you see in C right here.
 So each row, sorry, each row and B shows the same code executed with different parameters.
 Each image in C shows the same code executed with different parameters and a different
 sub program.
 So it is able to to come up with higher order functions that so functions that take another
 function as an input in this case, the the radial symmetry function that takes in a number
 n and a lower order function, and it will replicate that lower order function in in
 kind of a circle manner.
 So this, it comes it comes up with these things by itself.
 Now, again, this is pretty cool, by the way.
 And at the bottom, you can see what the dreaming phase comes up with.
 So at the beginning, you can see that the programs that the dreaming phase comes up
 with are fairly simple, right?
 And as the library grows, so grows the complexity of the programs it's able to come up with.
 So this is sort of a built in curriculum that the model has.
 It starts by constructing problems from its own library, given that at the beginning,
 the library is pretty primitive.
 It, you know, it doesn't do much, but over time, it does.
 Now here you can, by the way, I think the the pen starts at the dark and goes to the
 light like the color coding is where the pen starts and ends.
 And I'm not I'm not sure the exact direction they stated.
 So yeah, it's starts at blue and finishes at pink.
 Okay, and you can this is during super early, like this doesn't need many iterations.
 So illustrate the most interesting dreams found across five runs.
 Oh, sorry, no across five runs both before and after learning.
 But the sort of the iterations that it takes aren't that many to find solutions to new
 programs.
 But you can see, I feel right, this is just my opinion, that if you look at the problems,
 and if you look at the primitives that the thing comes up with, you probably see like
 I see that the person or the system who came up with these tasks is constructed in much
 the same way as these sort of primitives, like probably the person that came up with
 the tasks wrote a little DSL, saying, okay, you know, I'm gonna, you know, have a semicircle
 function, and that's going to be parameterized, and so on.
 And no, so these, these problems themselves are sort of generated by already by a DSL
 or by a human that has kind of this DSL in mind and applies it.
 And therefore, I think that's what I said when I said it's probably the system is very
 geared towards these problems, because what it's going to end up doing, it's going to
 end up kind of rediscovering how the data was generated.
 And that makes me a bit so so the question now is, does is this going to work on data
 that wasn't generated in this way?
 Or alternatively, you can ask, does the universe have a structure like this?
 And there's good arguments like it like it can discover physical laws.
 So here, it can also do, by the way, the same thing with these tower buildings.
 And you can see the primitives it's discovering are things like build an arch, build a wall,
 build a pyramid, like those are primitives and with arguments, and the different arguments
 will give you different structures right here is very cool.
 And these are the dreams down here, what it comes up with.
 So it's, you know, pretty intricate dreams, the combination of those rules.
 Now, again, the question is, does this work on let's say, real world data?
 And I feel that is, you know, is real world data?
 Does it behave similarly?
 And you know, maybe, I don't know.
 Yeah.
 So here you can see a bunch of ablations where they show that if you for example, if you're
 missing the abstraction, you won't get very far very often.
 For example, in these in these logo graphics, you see pretty clearly that without abstraction
 or without dreaming, you won't you won't get very far, especially I feel that abstraction
 hurts quite a bit.
 Because if you can't abstract, you're only going to go so far in constructing programs.
 So you can't construct large programs, even if you have a very good neural network guiding
 your search.
 And lastly, they go about, as I said, discovering sort of physical laws, and they sort of rediscover
 physical laws from numerical inputs.
 And that's what I mean, maybe the world is actually like this, at least that's how we
 humans solve problems, right?
 We search for a simple, simple explanation to the things that we see.
 And you know, science has been very successful, especially, you know, Newton has described,
 Newton's second law is like literally this big.
 So and it describes a whole lot of interesting physics.
 And you know, similarly, lots of other physical laws, which is kind of an unsolved mystery
 why everything is so simple.
 But given that it is a program like this might very well be appropriate, so our program search
 system might very well be appropriate.
 You know, that being said, it probably can't out of the box solve computer vision or something
 like this.
 And they admit that in the in the in the last part here, but just look at kind of the primitives
 it discovers itself.
 So just from the initial primitives that you see right here, like map zip, call, I don't
 even know what that is, like I'm not into functional programming.
 But from the initial primitives, it discovers the concept of subtracting vectors, adding
 vectors, dividing by two, and so on.
 From those, it constructs things like the square root function, which, you know, it's
 pretty remarkable.
 And from those, it discovers things like the inverse square law.
 And you can then see that, for example, Newton's second law is only a combination of, you know,
 very few applications of library rules.
 So it's an exceptionally short program, given this library.
 And also Coulomb's law, you can see, it's just kind of two rules applied to the four
 inputs, which if you expand this, it's a fairly large program.
 But because you have this library built up, it's it's a short program.
 And they do one other experiment where they give it so they they do recursive programming
 algorithms, like list operations again, but they only give it like the bare minimum that
 according to functional programming theory, as far as I understand it, you these are the
 real the primitives you need to solve the problems.
 And specifically, what it does is it first discovers the fold and unfold functions.
 So fold is also called reduce, I think if like that's a more common name.
 First it discover these these and from these, it builds all the other ones.
 And they say, if you go and you look at kind of functional programming theory, that's exactly
 what they say is necessary.
 So they say, given fold and unfold, you can sort of build all the other ones and these
 primitives.
 And again, you can see list difference function is very super duper short in terms of this,
 if you have this library.
 So if you've discovered the zip function, and that expands to a program that is fairly
 long that you would never reach with even with neural guided program search.
 And not only like reaching it is one point, but then you also have to recognize that that
 is actually the correct one.
 Right.
 And you do that as a human by looking how short it is.
 And this is not a short program, like you could building this as a hash table is shorter
 than this program.
 So you would rather take the hash table, I guess, if you just have two examples, rather
 than the program, but given that you have all this library, the zip a minus b is actually
 much shorter than encoding it as a hash table.
 All right, so they say, you know, the real world data, they say that here, much real
 world data is far messier.
 A key challenge for program induction going forward is to handle more pervasive noise
 and uncertainty by leaning more heavily on probabilistic and neural AI approaches.
 Recent research has explored program induction with various hybrid neuro symbolic representations
 and integrating these approaches with the library learning and bootstrapping capacities
 of DreamCoder could especially be valuable going forward.
 And I agree this.
 So we if it's not out yet, we had Francois Chollet on the machine learning street talk.
 And if you if you know him, he came up with this this arc challenge where you do like
 it's almost the same thing as DreamCoder does, except with these kind of pictures.
 And you assume that humans have this thing called core knowledge, which they also allude
 to in this paper.
 And core knowledge is things like an intuitive understanding of physics and objectness and
 so on.
 So one of the arc challenge things is like, there's kind of a thing here.
 And there's a thing here.
 And then the solution, the solution to that is there's again the thing here.
 And that, so that's the solution, right.
 And you can already see from one example, it's kind of like a ball bouncing off the
 wall.
 And you do that by applying your core knowledge, so to say.
 So this, again, is very, very clean data.
 So the in arc, I think everything is super clean data, and they say, you know, if we
 want to apply this to real world problems.
 And this is also something that Chollet has said in the podcast, which I invite you to
 listen to as soon as it's out, is that we're going to have to combine this search.
 So the the DreamCoder, it does kind of the search, which the search over a DSL.
 So and the DSL is learned, right.
 Now what we need, this is kind of these are different layers.
 What deep learning usually does is this perception.
 So deep learning is really good at doing perception.
 So this is current deep learning.
 And this up here is what DreamCoder does, or generally, program synthesis approaches
 do.
 And we need a way to connect the two.
 So we need a way to learn these jointly, because that's what you as a as a human some somehow
 do.
 You're able to learn your perception model, which is kind of a perceiving model, and your
 your logic model, your reasoning model at the same time, or just jointly in some way.
 And we haven't exactly figured out how to do that yet.
 And I feel, and I agree with this paper, that is probably going to be a very valuable thing
 to do.
 All right, so let me know what you think about this paper, I invite you to read it.
 It is it is high level, right.
 But there are some other cool things in it, like the DreamCoder learning reg exes for
 different types of numbers and so on.
 But yeah, I think it's an interesting field.
 It's a bit different from just kind of core machine learning.
 And that was it.
 I'll see you next time.
 Bye.