Population-Based Search and Open-Ended Algorithms
machine learning ai artificial intelligence open ended learning quality diversity conference icml icml2019 tutorial population-based search goal switching serendipidy evolution
Comments on the ICML2019 tutorial on population-based search and open-ended learning.

Talk: https://www.facebook.com/icml.imls/videos/481758745967365/
Slides: http://www.cs.uwyo.edu/~jeffclune/share/2019_06_10_ICML_Tutorial.pdf
Book: https://www.amazon.com/dp/B00X57B4JG/
Event: https://icml.cc/Conferences/2019/ScheduleMultitrack?event=4336
 This is huge. This is just one hall and most people I guess are still waiting for registration. Yeah, but definitely the size of these things is ginormous. The tutorials have just started. There we go. It's finding a place. Hi, so I just wanted to give a little update on a tutorial that I liked which was the population-based search and open-ended learning tutorial which happened on Monday here. So I was pleasantly surprised by this tutorial because I knew almost nothing about these techniques and they seem really cool. It seems to be a really cool line of research. So I started out with what is population-based search and basically in population-based search you don't want to just reach one solution of a problem but you want to maintain a population of solutions that you develop over time. So natural evolution would be an example of that. So this can have many benefits that were explored in the tutorial. So the culprit of traditional optimization, let's say you have a classification problem, you just train one classifier on it, is what they call deception, meaning that a better example is an RL problem where you need to reach some goal but since the goal might be very hard to reach, your algorithm has basically nothing to go on. There's no stepping stone. So usually people go and construct a reward function in a very clever way. But this can be overcome with these techniques as well. So just imagine the hardest video game in the Atari suite. This would be something like Montezuma's Revenge where you first need to collect some key and then go to some door and only then you get a score. So this reward function is too ambitious and is a problem they call your deception. An observation they make is if you look at nature and natural evolution, it is very successful even without a goal. So there's no goal in mind to natural evolution except reproduction creates other reproduction. But it's not a goal, that's simply a kind of underlying mechanism. And if you look at nature, all this variety of life was produced without a goal in mind. And all this variety of life filling different niches and basically reproducing at their own pace. So it's a very interesting observation. The goal of this entire field is kind of to model, to go into this direction of what if we don't really go after only the cost function, but what if we... So in the most extreme case, what if we build a search algorithm that only wants to create novel things? So where kind of novelty is the only goal, what happens then? And it turns out some interesting things can be achieved with that. So they introduced this notion of quality diversity, which basically means if you look at, let's again take a life on earth, you want all the achievable behaviors that there are. So maybe one achievable behavior is a very fast life form that can hunt other life forms, and another achievable behavior is one that camouflages very well and so on. And you want to kind of find for each of these behaviors, you want to find the best possible example. So that's the direction that these algorithms go into. And an algorithm that they presented was MapElites, so M-A-P-Elites, which goes as follows. So let's say you have a bunch of dimensions you care about, say how fast a creature is, how tall it is, how well it is camouflaged and so on. Now you want to discretize each of those dimensions. So this will give you cells basically. So each of these discretization will introduce a grid of cells. And what you now do is you want to keep the best examples of each cell. So if you have a creature that's very fast but not very well camouflaged at some cell, you look at how well it's doing at the goal that you have in mind. And you want to keep the best one of those. You have a population and whichever ones are in that cell, you keep the best. And then you go ahead and you kind of change them. You could do this via evolutionary process, like you can mutate them, or it could be via gradient descent something. But you mutate them and I guess they will probably end up in a different cell. So you go look at that cell. Are these new ones better than the ones that you remembered from that old cell? And if so, replace them. For each cell, keep the best one and then kind of start continue developing from those. Sort of like Dijkstra's shortest path algorithm. So what it will return is like an entire landscape of possible behaviors. And for each behavior, it will give you the best result. Now it doesn't mean they all do equally. Some will be better, some cells will be not as good with regards to your cost function. But it will give you an entire landscape and you could see then that there are many kind of modes in this landscape. As I said, some creatures are very fast hunters, some camouflage very well. But then they are kind of slower. So you will be able to see these modes in that. I found this pretty interesting and opens the door to a lot of different applications. So a principle they employ is what is called goal switching. Namely, that means if a line of development can benefit from inventions of another line. So let's say the very fast hunters, they are good at that, but then maybe they don't reach quite optimal performance. But then another line develops somewhere else and these are camouflaged, like the camouflaged life forms develop. So they invent kind of camouflage. Now because of the way this mutation and so on is, you kind of keep the camouflaged ones around and the hunters. And now the camouflage can kind of jump over to the hunters. It's very difficult to explain like this, but they call this goal switching. And what it means is that the hunters can now adopt a little bit of camouflage through, let's say mutating one of the camouflaged ones into the hunters or vice versa. And then can kind of benefit from that invention over there. And so a good example of that, they mentioned, is that in order to discover the microwave, you first had to work on radar technology, which had nothing to do with microwaves. But because of the inventions made in radar technology, you could then invent the microwave easily. So it kind of jumped over into the space of ovens, basically. Before, all you had to make food warm was just put it in an oven and heat it up. Now you had the microwave. So that kind of these algorithms capture the spirit of this. A book that the people who gave the tutorial wrote is Why Greatness Cannot Be Planned. I'll definitely get that. And I can't recommend it since I haven't read it yet, but I'm going to get and read it. Should be fairly interesting. So they give them a number. They gave a number of examples of this, for example, robots that can recover from damage because so they had a robot with six legs. They trained it to move. Now they disabled one leg. Now, usually you have one solution like you trained your neural network. I don't think it was even a neural network, but you trained your like your system to move this robot as efficiently as possible. And now because you only have one solution, one legs broken, it doesn't work anymore. But since you have the entire landscape of solutions, you can easily kind of jump to other not as good solutions if you have all legs. But you can jump to other solutions in the solution space and try them out. Which ones do still work? If I only now have five legs, since you have the entire landscape, you're very well able to do that. So that's pretty cool. Another algorithm they presented was GoExplore, which is an algorithm that kind of solved these really hard Atari games while back. And what they do in specific is they kind of have an archive of states that they have reached in the past. So it's a video game and you do some things and then you are in certain states. So it's an archive of states. And you just pick one of that. Right. You pick like, OK, this state means I'm like my little person I control is somewhere over there. And then you just explore from it. Right. You do a population based. You just kind of go around from it and so on. And then you look at the state you end up in. And if the state you end up in is a known state like you've been there before. So it's also in your archive. Then you compare the two. Did you get faster to that state via the new route or did you get faster to that state via the route that was already in your archive? And if you're faster in that state via the new route, you will you replace the archived one with the new one. So this again is kind of like a Dijkstra shortest path algorithm extrapolated to this to this kind of domain where you have to explore. You don't actually have a graph. So I think it's it's pretty cool. It's all kind of the same principle, but it can employ this goal switching thing. Right. So you go to a certain state, but then all of a sudden, because you explored something else, you find a much quicker way to that state, which you never intended. But it happens. So this is a basic principle that kind of if you explore a lot, then good things might happen. So kind of a serendipity discovery mechanism, and you could use those good things, incorporate them into the things that already work. The last topic they covered was open ended search. So a distinction from what they've already discussed to open ended is now. They give the example again life on earth. If you consider it, it's a single run of an algorithm. It's not that for every life form, a different optimization was started and kind of started and finished, optimized for a certain thing. It's all one single run of the same algorithm. And it doesn't really have a goal in mind. So open ended algorithms are like that. They kind of define interesting notion. Is it still interesting if we were to just let it run for a billion years? Like, would it still be interesting? If yes, consider it an open ended algorithm, which I find a really good kind of definition. So the fundamental property that open ended algorithms have and research in this has defined is that constantly not only is the population shifting, but also the environment is shifting. So there's kind of a never static situation. The environment's always shifting. That also means there's always new opportunities opening up for kind of new life on earth, for new creatures to evolve, to kind of fill the niches that open up. And the research community around this, the open ended search, open ended learning community is considering exactly those types of environments. Like how can they even describe those, manufacture those and then learn in those. So pretty cool. The cool experiment they've shown was the pick breeder experiment, where basically it's a human in the loop. So they gave humans could cooperate. So as a human, you go to a website, you pick one picture and these pictures are procedurally generated. So they start out with a very simple pattern and you just have the opportunity to kind of you pick one and it gives you a bunch of random perturbations of the procedurally generated image. And you pick the ones that you like and then you continue exploring from there. And if you're happy, you can just save that to the database and someone else can look through the database and then pick yours, for example, to continue. And the things that the humans came up with or the result of that was extremely interesting. So not only could you perturb, but you could also kind of mix pictures as far as I remember. Not sure anymore. But the things they end up with is you could breed pictures, right? You could you could kind of also put pictures together. So the procedural generation of them and what you end up with is remarkable, remarkably interesting things. And the point they made is it's really only from very few iterations. These are like tens or hundreds of iterations of development, not like a million like we're used to. And there's a real tree of phylogenies that emerge. And the crucial lesson, they say, is people only find when they are not looking. So if you had a certain goal in mind, you would never be able to, you know, change the pictures in the way that this goal would appear. But if you have no goal in mind, you might discover all kinds of interesting things. So that that is kind of all I'm going to say of this. They discussed many more things, but I think these are the main takeaways. So population population based search is interesting because it can kind of overcome the problems that if you only had one optimizer, one optimization run of one algorithm, if you employ quality diversity in the algorithm map elites, this this enables this kind of goal switching gives you back an entire landscape of of the of learned actors or systems that for each one, you know, it's kind of the best performing one in that particular constraint of of the of the dimensions you care about. And yeah, open ended algorithms, open ended search is definitely a cool research direction. And I encourage you to check it out. All right. That was it so far. Thanks for listening. Bye.
 This is huge. This is just one hall and most people I guess are still waiting for registration.
 Yeah, but definitely the size of these things is ginormous.
 The tutorials have just started.
 There we go. It's finding a place.
 Hi, so I just wanted to give a little update on a tutorial that I liked
 which was the population-based search and open-ended learning tutorial
 which happened on Monday here.
 So I was pleasantly surprised by this tutorial because I knew almost nothing about these techniques
 and they seem really cool. It seems to be a really cool line of research.
 So I started out with what is population-based search
 and basically in population-based search you don't want to just reach one solution of a problem
 but you want to maintain a population of solutions that you develop over time.
 So natural evolution would be an example of that.
 So this can have many benefits that were explored in the tutorial.
 So the culprit of traditional optimization, let's say you have a classification problem,
 you just train one classifier on it, is what they call deception,
 meaning that a better example is an RL problem where you need to reach some goal
 but since the goal might be very hard to reach, your algorithm has basically nothing to go on.
 There's no stepping stone.
 So usually people go and construct a reward function in a very clever way.
 But this can be overcome with these techniques as well.
 So just imagine the hardest video game in the Atari suite.
 This would be something like Montezuma's Revenge where you first need to collect some key
 and then go to some door and only then you get a score.
 So this reward function is too ambitious and is a problem they call your deception.
 An observation they make is if you look at nature and natural evolution,
 it is very successful even without a goal.
 So there's no goal in mind to natural evolution except reproduction creates other reproduction.
 But it's not a goal, that's simply a kind of underlying mechanism.
 And if you look at nature, all this variety of life was produced without a goal in mind.
 And all this variety of life filling different niches and basically reproducing at their own pace.
 So it's a very interesting observation.
 The goal of this entire field is kind of to model, to go into this direction of
 what if we don't really go after only the cost function, but what if we...
 So in the most extreme case, what if we build a search algorithm that only wants to create novel things?
 So where kind of novelty is the only goal, what happens then?
 And it turns out some interesting things can be achieved with that.
 So they introduced this notion of quality diversity, which basically means if you look at,
 let's again take a life on earth, you want all the achievable behaviors that there are.
 So maybe one achievable behavior is a very fast life form that can hunt other life forms,
 and another achievable behavior is one that camouflages very well and so on.
 And you want to kind of find for each of these behaviors, you want to find the best possible example.
 So that's the direction that these algorithms go into.
 And an algorithm that they presented was MapElites, so M-A-P-Elites, which goes as follows.
 So let's say you have a bunch of dimensions you care about, say how fast a creature is,
 how tall it is, how well it is camouflaged and so on.
 Now you want to discretize each of those dimensions.
 So this will give you cells basically.
 So each of these discretization will introduce a grid of cells.
 And what you now do is you want to keep the best examples of each cell.
 So if you have a creature that's very fast but not very well camouflaged at some cell,
 you look at how well it's doing at the goal that you have in mind.
 And you want to keep the best one of those.
 You have a population and whichever ones are in that cell, you keep the best.
 And then you go ahead and you kind of change them.
 You could do this via evolutionary process, like you can mutate them,
 or it could be via gradient descent something.
 But you mutate them and I guess they will probably end up in a different cell.
 So you go look at that cell. Are these new ones better than the ones that you remembered from that old cell?
 And if so, replace them.
 For each cell, keep the best one and then kind of start continue developing from those.
 Sort of like Dijkstra's shortest path algorithm.
 So what it will return is like an entire landscape of possible behaviors.
 And for each behavior, it will give you the best result.
 Now it doesn't mean they all do equally.
 Some will be better, some cells will be not as good with regards to your cost function.
 But it will give you an entire landscape and you could see then that there are many kind of modes in this landscape.
 As I said, some creatures are very fast hunters, some camouflage very well.
 But then they are kind of slower.
 So you will be able to see these modes in that.
 I found this pretty interesting and opens the door to a lot of different applications.
 So a principle they employ is what is called goal switching.
 Namely, that means if a line of development can benefit from inventions of another line.
 So let's say the very fast hunters, they are good at that, but then maybe they don't reach quite optimal performance.
 But then another line develops somewhere else and these are camouflaged, like the camouflaged life forms develop.
 So they invent kind of camouflage.
 Now because of the way this mutation and so on is, you kind of keep the camouflaged ones around and the hunters.
 And now the camouflage can kind of jump over to the hunters.
 It's very difficult to explain like this, but they call this goal switching.
 And what it means is that the hunters can now adopt a little bit of camouflage through, let's say mutating one of the camouflaged ones into the hunters or vice versa.
 And then can kind of benefit from that invention over there.
 And so a good example of that, they mentioned, is that in order to discover the microwave, you first had to work on radar technology, which had nothing to do with microwaves.
 But because of the inventions made in radar technology, you could then invent the microwave easily.
 So it kind of jumped over into the space of ovens, basically.
 Before, all you had to make food warm was just put it in an oven and heat it up.
 Now you had the microwave. So that kind of these algorithms capture the spirit of this.
 A book that the people who gave the tutorial wrote is Why Greatness Cannot Be Planned.
 I'll definitely get that. And I can't recommend it since I haven't read it yet, but I'm going to get and read it.
 Should be fairly interesting.
 So they give them a number. They gave a number of examples of this, for example, robots that can recover from damage because so they had a robot with six legs.
 They trained it to move. Now they disabled one leg.
 Now, usually you have one solution like you trained your neural network.
 I don't think it was even a neural network, but you trained your like your system to move this robot as efficiently as possible.
 And now because you only have one solution, one legs broken, it doesn't work anymore.
 But since you have the entire landscape of solutions, you can easily kind of jump to other not as good solutions if you have all legs.
 But you can jump to other solutions in the solution space and try them out.
 Which ones do still work? If I only now have five legs, since you have the entire landscape, you're very well able to do that.
 So that's pretty cool.
 Another algorithm they presented was GoExplore, which is an algorithm that kind of solved these really hard Atari games while back.
 And what they do in specific is they kind of have an archive of states that they have reached in the past.
 So it's a video game and you do some things and then you are in certain states. So it's an archive of states.
 And you just pick one of that. Right. You pick like, OK, this state means I'm like my little person I control is somewhere over there.
 And then you just explore from it. Right. You do a population based. You just kind of go around from it and so on.
 And then you look at the state you end up in. And if the state you end up in is a known state like you've been there before.
 So it's also in your archive. Then you compare the two. Did you get faster to that state via the new route or did you get faster to that state via the route that was already in your archive?
 And if you're faster in that state via the new route, you will you replace the archived one with the new one.
 So this again is kind of like a Dijkstra shortest path algorithm extrapolated to this to this kind of domain where you have to explore.
 You don't actually have a graph. So I think it's it's pretty cool. It's all kind of the same principle, but it can employ this goal switching thing.
 Right. So you go to a certain state, but then all of a sudden, because you explored something else, you find a much quicker way to that state, which you never intended.
 But it happens. So this is a basic principle that kind of if you explore a lot, then good things might happen.
 So kind of a serendipity discovery mechanism, and you could use those good things, incorporate them into the things that already work.
 The last topic they covered was open ended search. So a distinction from what they've already discussed to open ended is now.
 They give the example again life on earth. If you consider it, it's a single run of an algorithm.
 It's not that for every life form, a different optimization was started and kind of started and finished, optimized for a certain thing.
 It's all one single run of the same algorithm. And it doesn't really have a goal in mind.
 So open ended algorithms are like that. They kind of define interesting notion.
 Is it still interesting if we were to just let it run for a billion years? Like, would it still be interesting?
 If yes, consider it an open ended algorithm, which I find a really good kind of definition.
 So the fundamental property that open ended algorithms have and research in this has defined is that constantly not only is the population shifting, but also the environment is shifting.
 So there's kind of a never static situation. The environment's always shifting. That also means there's always new opportunities opening up for kind of new life on earth, for new creatures to evolve, to kind of fill the niches that open up.
 And the research community around this, the open ended search, open ended learning community is considering exactly those types of environments.
 Like how can they even describe those, manufacture those and then learn in those. So pretty cool.
 The cool experiment they've shown was the pick breeder experiment, where basically it's a human in the loop. So they gave humans could cooperate.
 So as a human, you go to a website, you pick one picture and these pictures are procedurally generated.
 So they start out with a very simple pattern and you just have the opportunity to kind of you pick one and it gives you a bunch of random perturbations of the procedurally generated image.
 And you pick the ones that you like and then you continue exploring from there.
 And if you're happy, you can just save that to the database and someone else can look through the database and then pick yours, for example, to continue.
 And the things that the humans came up with or the result of that was extremely interesting.
 So not only could you perturb, but you could also kind of mix pictures as far as I remember. Not sure anymore.
 But the things they end up with is you could breed pictures, right? You could you could kind of also put pictures together.
 So the procedural generation of them and what you end up with is remarkable, remarkably interesting things.
 And the point they made is it's really only from very few iterations.
 These are like tens or hundreds of iterations of development, not like a million like we're used to.
 And there's a real tree of phylogenies that emerge.
 And the crucial lesson, they say, is people only find when they are not looking.
 So if you had a certain goal in mind, you would never be able to, you know, change the pictures in the way that this goal would appear.
 But if you have no goal in mind, you might discover all kinds of interesting things.
 So that that is kind of all I'm going to say of this.
 They discussed many more things, but I think these are the main takeaways.
 So population population based search is interesting because it can kind of overcome the problems that if you only had one optimizer,
 one optimization run of one algorithm, if you employ quality diversity in the algorithm map elites,
 this this enables this kind of goal switching gives you back an entire landscape of of the of learned actors or systems
 that for each one, you know, it's kind of the best performing one in that particular constraint of of the of the dimensions you care about.
 And yeah, open ended algorithms, open ended search is definitely a cool research direction.
 And I encourage you to check it out. All right. That was it so far.
 Thanks for listening. Bye.