DL Podcast #3 | Yannic Kilcher | Population-Based Search

Key Takeaways

[Music] thanks for watching the Henry Aird labs deep learning podcast today I'm joining with Jana Kilcher Yannick is works in the data analytics lab at ETH he has a great YouTube channel I really enjoy watching his paper summary videos if you liked any of the videos that I'm making you've definitely also like checking out this channel I'm gonna put the link in the description at the end of the talk Yannick thanks for doing this and appreciate it thanks for having me it's cool so what we're gonna talk about is population-based search and presentation that I see though that I really thought was interesting about emphasizing diversity and novelty in search so the first question I just wanted to start by generally talking about your opinion on population based search and the differences between population based search and like gradient descent going straight for one solution yes so the the kind of main difference is that in population based search as the name implies you maintain kind of a large population of solutions so you don't want to limit yourself to just one trajectory say I start here and then I run towards my goal but you kinda maintain a lot of hypotheses of what the solution could be and then you kinda want to update all of them at the same time and so there's many different variants of population based search but they all have this this thing in common where you maintain many solutions and you kind of bet on one of them becoming a good one basically yes so one of the things they present their paper where they have the robot walking and if it breaks one of its legs for example it can go back to the map elites table and and say okay well I lost this leg but I think maybe this solution I was I wasn't too clear on how that would really be related so as maybe wondering if you had a more insight on that yes so the so that may be the the context is yeah we want to teach a robot to walk and the robot had six legs I believe so and if you think of what's the solution to the problem a solution is kind of an algorithm that takes the current sensor input and outputs how to move the motors right so and if you just have flexing your gradient descent algorithm converging on the best solution of how to move the robot it's just going to be like oh these are the sensors okay I'm going to move like this like this like this like this but if one leg breaks of course you're lost because you only know this one way of moving and now the sorry so you only know this one way of moving basically and that's it but in population based search if you think of the solution as a way to move you maintain many many ways to move so you basically the objective if you can call it like this is algorithm find me a lot of different ways to move right with my six legs and now if one of my legs I still can evaluate all of them I still can find okay which one's the best but if not one of them falls away I have all these other solutions that I can try right so then what they would do is like this life was wait now they just re-evaluate all of those solutions while only having five legs and the best of those like is much more likely to kind of work than if you had just your single solution so that kind of that's the it's population-based because you maintain many different ways of solving the problem yes I was thinking about like using the search algorithms that control neural architecture search and things like that so it's trying to think of how you might extend these ideas from the robot I'm walking with six legs to the RNN controller designing the convolutional Network like maybe I might have like more of them storage constraint or more of a latency constraint and I could jump to a different solution like that I'm just wondering how you think like these ideas of population-based search translate into the No architecture search and specifically if it really is important and because like you've got I feel like in neural architecture search you have such a direct signal with the classification accuracy like I don't see as much variance I suppose in the in the objective function yeah I really think this population based approaches they shine in so they shine in multiple different areas but one area where they shine is definitely when the environment changes so when you know something about whatever your input changes like the robot losing a leg so in kind of neural architecture search you might you might find these methods working if you then go for let's say transfer learning so you kinda train your network on one task you want to actually do it on another task right and then if you maintain many solutions and you can evaluate all of them in this transfer setting it's much more likely that one of them you know it's gonna be is gonna be fine so but you're right of I also believe that directly in architecture search maybe it's not maybe it doesn't yield that many great results though the other of course the other area where these methods shine and this is with respect to algorithms like novelty search which can be implemented as a population based method is they gave this really good example of deception in a search problem so a deception would be like if you have a robot walking a maze and the robot just wants to get to the goal right and you would program it the robot to be rewarded the closer gets to the goal but if like there's a wall in between and you actually need to go around the wall kind of then for a while you will need to move away from the goal in order to reach it so if you have like a pure objective driven approach you just go straight to the the goal you would always get stuck at the wall but if you then kind of do what is called a novelty search where he basically reward the robot for things it has never done before it would actually and it's way around the wall so you can maintain population of solutions that all kind of explore the space and that in neuro architecture search maybe it's of a benefit that actually you know if I I probably always benefit from like adding more layers or neurons or something like this but maybe I actually want to prune some stuff first and then add some more stuff so maybe want to get worse first before I can get even better right so mmm so is it reached where I can imagine I think but I don't know yeah I was thinking the changing environment I definitely think like when you deploy a model and then you're getting new data that you could frame that as a changing environment and then also thinking about like in the context of Gans which is something that I think is really interesting that the discriminator classifying the Gans and the generator samples it's a changing environment because the generators updates so maybe having some kind of population-based can our discriminator model might help it avoid that like continual learning problem I guess is sort of it yeah that could that might as might very well be there are approaches to Gans I believe where you based you have like many discriminators and each one kind of only has let's say has its own limited view on the day turn you're trying to kind of fool a lot of them at the same time but it's not the same thing but yes I think that yeah I've seen that multiple generator multiple discriminator model - I think that's really interesting as well so one other thing I was curious about is this idea of goal switching and how that might relate to the like auto ml on our existing I'm well like heavily studied things like classification localization semantic segmentation like how do you think goal switching could be important like one idea I had is maybe if you've got like multi-class classification and it's got like a really low false positive rate or something on like one class you might say well you've somehow learned a decision boundary on that class or do you think that wouldn't generalize and that there's no sense and go swinging like a multi-class classification problem so yep in general well when you think of goal switching in general how they introduced it was also in the context of like this population-based search of these map elites maybe it's kind of so what map elites the algorithm does basically is it says okay I have a number of dimensions that I could solve the problem on and they introduced okay let's take life on Earth needs to whatever survive so I can either be like a super tall creature right to reach food that no one else can reach I can be a super fast creature right to kind of run away from everything or it can be a super heavy creature so that no one can attack me and so these are kind of the dimensions that you can solve the problem of reproduction and survival and within so that what map elites does it it would segment this area so let's say size and speed it would segment this into a grid and in each grid it would kind of maintain the best solution so far that is within that grid and then what they see is when they then kind of evolve this over time and improve each each grid is that inventions let's say inventions algorithm discoveries in one grid say for a very fast creature they would then kind of be adapted to the very let's say the very heavy creature so like fast creature kind of discovers or longer legs make me even faster maybe the longer legs can even be combined in the heavy creature to do something else so this kind of goal switching it's think of like feathers being first kind of developed or evolved for warmth for temperature regulation then being goal switched over to adapt it for flight so in the in terms of multi-class classification i guess it's a bit of a different problem if you just have one classifier you could definitely make the argument that since you know you're learning maybe two classify one class really well a low false positive rate you have learned very good features for that class and if some other class kind of like the zebra is a worse with stripes and then the horse is a horse but with the feature stripes being really low you can probably classify that better something making stuff up here but it's a bit of a different context i i feel the if you have a single classifier do multi-class classification but definitely the logic applies in the feature space I would say where you learn features for one class and they might become useful for another class yeah when you're discussing eyes like we've got like a multi class multitask learning like maybe my intermediate feature is getting mapped to a classifier I get mapped to a segmentation get mapped to again like good goal switching improve multitask learning yeah I would definitely say so I think that that's exactly what we're seeing when you look at for example pre-training so if you think of like this these newest big language models like Bert or something they're really good at tasks I don't know what it was Anna no Pete asked us labeling of sentiment sentiment classification because it's so easy but let's say Birds is really good at sentiment classification but if you were just to Train it outright on sentiment classification it's probably not gonna work because there's just too little signal but then what happens is you pre train it as a language model as this masked language model and it kind of gets really good at simply comprehending a language and that skill can then be kind of adapted over into the into the Samantha sorry into the sentiment classification realm so I I think if you look at yep something like retraining or multitask as you say then definitely one tab what addition of a task might give rise to certain features that then all of a sudden can be adapted by another task whereas if you just trained the latter task by itself that maybe would have been too difficult so yeah definitely in an analogy so then what I think about is so I'm going from my pre trand language model into sentiment classification and maybe I also add like question answering document summarization name entity like this like a vector of tasks that it can go do I'm then curious like when your goal switching it's like how do you then combine the features later on or you just like take it as if I need this task I'll go to this model like yeah well the question here is do you whether or not you implement this as a single model and kind of refer to the goal switching of features within that model or whether you also do this now as a population based method where basically you maintain you you maintain different neural networks for different combination of these tasks then you'd actually need a method to kind of combine and reproduce the neural networks themselves which I yeah I I see that's it's gonna be a bit of a difficult task like some cross distillation or some something crazy yeah I don't know how that would work exactly yeah yeah I just wonder about two things it's like do for my population-based serve could you have like the weights be the populations like different sets of weights or would it necessarily need to be like taking apart the layers and designing new internal like cells in the architecture search like because if I just have the weights maybe I could treat the diversity search or goal switching as like stochastic boyd averaging and just like mesh them all together when I'm finished with my goal switching at the end but if it's yeah if I definitely be if you wanted to if you if you wanted to if you wanted to implement your multi task t tasks tasking as a population based approach where yeah you could definitely give you an easier time if you keep the architecture of your neural networks the same and simply have different weights and then you could indeed consider something like weight averaging or or yeah I guess a more modern approach will be like distillation from it the two teacher models into one child model it's actually a good metaphor for a for reproduction kind of a distillation from multiple teacher model don't know if anyone's done that yet but they're I guess that that might be the way to do it if you also maintain different architectures for different problems that might be a bit of a yeah that's an interesting thing too you have the little switching and then you model distill it all into one model that is yes well if you think of math elites right it simply it simply distill it into the the appropriate I don't even know what the what the axis would be probably I can imagine okay you have like three tasks so you have three axes and then you'd mix the tasks maybe in accordance on how far up your of these axes you are or something like this it's not exactly mathletes because your actual objectives are on the axis yes but just to backtrack one step I want to talk about like diversity centric search novel to you like when I was thinking about that I was like can't you just initialize it such that it has maximum diversity like can't you just initialize the population such that they're all like uniformly spaced and then search locally from there so I just wonder what you think on that and how this is different from that so yeah and these in this diversity search algorithms basically what you're you're doing is you're your only goal is or your main goal depends on the other but let's say your only goal is to find diverse behaviors or diverse solutions diverse I think the main problem with that is is that the search space is so extremely large that you're gonna have a hard time even even defining what a kind of a uniform distribution is because it's such a high dimensional space that even if you sample uniformly it it's it's almost empty like you're almost right you're not you're not getting anywhere because you have finite finite computer you need to implement an algorithm even if you even if a nice computer can hold a hundred thousand different members of a population in high dimensions that is nothing so me yet the initialization might be definitely important but I don't think you you get around some sort of iterative procedure and carry them around weeding out weeding out things such that you have space for interesting things because ultimately what you want to find is something interesting in the robot maze example the novelty search basically is here is a robot you started right and then you want to do something that you haven't done yet right so if the robots crashes into a ball the first time that's a good thing you say are cool you haven't done that yet but if it crashes into the wall a second time you're like you've done that already right so you you you basically need a measure of saying how close to behaviors are but if the robot has crashed into every wall once the only thing it can do if it wants to do something new is actually go around the wall and then you're like oh cool you've done something new but the space of behaviors often is so large that you can't simply enumerate all the all the behaviors so you I think that's the main problem y-you can't just make it diverse from the beginning yeah when I was thinking about that I thinking that maybe the like reward function if you're like navigating the maze it needs to be more refined so I gave it crashes into the wall that needs to be like I don't know plus three you some some like unique signal I feel like in order to create that kind of because I get thinking you know if it's just like rewards zero everywhere but one if you hit that finish line and then maybe some kind of like discounting for how long it takes you to get there it's like I don't see how it could interpret that it's done a new behavior if all it has is me it feels like it's all about the design of the reward space now implement such a thing yes absolutely so the that definitely if you wanted to do novelty search you would need to implement a measure of how close to behaviors are so there's no way around it and I think that's kind of crux of the of this method is that by specifying how close to behaviors are so what what constitutes novelty and what doesn't you already implicitly kind of telling the robot something about the nature of of the world so I think that the kind of the objective because they now say oh we don't give the robot the objecting of reaching the target we simply give it the objective of not doing the same thing twice I think the the kind of objective sneaks in in like again through the specification of how view how closer to behaviors but definitely this is just kind of a really simple example what they want to say is that these methods really become important when you have ambitious objectives right in the maze we can all agree if we just design the reward crashing walls bad you don't have to actually go straight to the goal you can you know but go around walls good and so on then it's easy right but in really ambitious objectives like no flying reaching the moon in the in the 1960s designing general AI curing cancer and so on we don't actually know how to design the reward right because we don't know which steps need to be fulfilled in order to to fly to the moon I guess now we do in hindsight right but we you couldn't have predicted we don't know which steps need to be discovered in order to cure cancer and it's very very probable if you look at history that the fundamental discoveries that lead to us curing cancer will not directly come from cancer research that's that's their entire point right it's not like you can have a goal go straight towards it if it's like a really ambitious goal very probably the solutions will come in part from extremely non related fields and they and you kind of have to make advances everywhere and in order to solve that problem so the the question of it's all design it's all designed to reward yes but we would have to know how the reward must be must look and in these really ambitious objectives we don't and that's that's where they argue well the best thing actually you can do is to just explore and you just find interesting things along the way and you kind of hope that these interesting things will come no you know the interesting things will combine to form new interesting things right but you just don't know where you're gonna end up right yes I guess maybe you could just keep a trick like the trajectory of States and use that as your signal novelty but then I think like if you've got like a robotic arm with like X degrees of freedom it's like this state space this would be to infinite to really like say oh this is significantly this is a significantly different sequential procedure of states and this other thing so then the next thing yes I think this is a good transition into their pick breeder experiment and so anyone who listens to this who hasn't watched their top the pig breeder is like they've got these generator neural network with sets of weights and they have like humans go on and they pick two of the generated images to blend together and derive a new image and so this repeats on and on until it goes from like just like a spiral pattern into like a skull face drawing or a butterfly drawing or something like that and they so this idea is supposed to represent open-endedness in an environment and not so it just generally I I just found it to be really interesting I think it's one of the things in their talk that you look at it and you're like oh that's interesting what what is going on here but it's like the the mutation is really guided by the human search which is so complex I feel like they're just wondering what you thought of that pick reader experiment II yeah it's really cool and it's it's it's actually the basis for their entire books I've read the the book the UM my greatness cannot be planned I believe I've got the title so that this they actually they kind of start out with this as a motivational example of what if what if the only goal is to do something interesting and without any objective so all you do is kind of choose slight variations on a current picture and you see what you end up with and I thought I thought it Allah straights their points extremely well so it illustrates for example goal switching is that so if you were done with your sequence of image manipulations you could then save it into the database and someone else could pick up from it and then kind of continue it and since every human finds slightly different things interesting right you could take someone else's final result and say uh you know that that kind of looks weird but then you your modifications to it will be different than had that human continued breeding the picture so what you you end up is and they show this for example one picture ends up being a car and it had been adapted from an alien face where the eyes of the alien face became the wheels of the car and so that first the first person might have been like oh this this this looks more and more like an alien face I'm gonna you know make it more like an alien face and then the second person is like other kind of looks nice I'm gonna modify it in a different so they they basically they basically give this example of if you have an ambitious goal like getting to a car just from these very simple picture generation networks then the stepping stones to get there have nothing to do with cars and the people that did it didn't have a car in mind while going there and the second thing is that if you try to get a car from the beginning I believed if they write they've done this if you try to you can't like it's just the sequence of things that you have to go through is so complicated and convoluted if you were to try to end up with a result it's it's basically impossible so these kind of illustrate their points very very nicely and I mean it's a cool experiment in itself but they use it kind of as a basis metaphor for then going on jumping off yeah I just think it's so interesting this idea that it's like you can't design a car unless unless you don't try it unless you just happen to come across that it's sort of like I think about like if I was to fire up GarageBand and start trying to make a song it's like I don't know exactly what its gonna sound like I'm just gonna kind of explore until I come across something so then I was thinking about like with the Gans and the way that the Gans design images like so this is like sort of a design I drew up that I'm curious what you think of its like what if the generator just like tries to make some object and then a pre-trained classifier says oh I think it looks like this maybe and then you send it to like a refining network so the Gann just sort of searches for objects and then some cost fires like I think it looks like sort of like how the pig breeder sort of like how we're like I think this looks like a school or whatever so I'm gonna Chuck had a you know refine it now do you think that would be an interesting thing or you'd have like a two-stage process first you do something general and then it gets classified and then you'd have like a special generator just for the skull class and the special discriminator just for that yeah I don't see why not might be hard it might be hard to get the first generator to to be sufficiently diverse so you might might need some kind of discriminator signal at the even at the beginning you're like how do you think the pig breeder experiment could be fully automated such that there's no human in the loop yeah that's that's a thought I had as well because it to me it seems that it'd be kind of of course the resulting pictures the fact that they look like human objects or recognizable object is it a result from them being being bred by humans like the fact that it looks like a car or a skull or something like this is it's very much also I guess that that could be abstracted in we just not expect the results to be like human recognizable objects but maybe something else like the much more deeper construction in pig breeder is the fact that the measure of interestingness is provided by the humans right so the humans stay they click on a picture and then they get variants of that picture and they click on the one that they most like this this sense of interestingness of I like this one this that's what's that's the fundamental core that's provided by the humans as an input to the system that's what drives the entire thing that's exactly the same as before it's when you write when you teach the robot which two behaviors are close enough like oh no that's too close to before that's not novel or yes that's sufficiently different than before that is novel right this the sense is somehow you either need to specify a Toria you need to have the human in the loop to provide it I feel it's very very hard to capture that in an algorithm as as of today yeah like something I think about is like maybe I'd have liked my a thousand class imagenet classifier and then maybe I'd have like like a style classifier like a neuro style transfer network that I've liked chopped off the I like some intermediate feature I'm gonna take that as my style and so maybe I'm like classifying I think it's like an airplane and then I kind of like this style for it that's sort of like my like how I would think about trying to automate that like I don't know I guess like I don't know if I I guess it's interesting but I also feel like when you're doing the pig breeder you're kind of like oh I'm gonna try it now at now that I see this vision I'm gonna try to make it like look like that now I suppose like that yeah yeah I think yeah yeah I got a good name this into a school and then you start doing yes yeah yes they're very much so they're not they're not advocating random exploration what they're advocating is basically if you have an ambitious goal then you basically don't know the stepping stones but from stepping stone to stepping stone that's where objectives are very handy so when you want to say I this already kinda looks like something I want to make it more like that I wanna make it more into a scholar idea already has like two circles it's kind of the shape but I'm going to drive it there that that is very that can be very objective driven but in the grand scheme of things you don't know then once you have the skull right someone else can develop that into an even new thing so yeah indeed if if you if you're in kind of a local search in this space then an objective driven you really like what you're saying like I want to make it as much this as possible that's very that's actually the thing they're advocating for but then from their end result yeah you would need to then restart again do the same thing with like something else yeah interesting just thinking about yeah and think about like the stepping stones and like is how would you define the space of stepping stones to such a to any kind of thing I guess it's like you could still design some kind of maybe it's discrete or maybe you have some kind of signal you can get back from it and I guess it's it's just a lot to think about they give this they give this great analogy I feel like if you have a really ambitious objective it's like crossing a lake but the lake is covered in fog so you basically can't really see very far but you can always kind of see the next stepping stones right and you can then you can then try to go from stepping stone to stepping stone but you don't know which one did it take if there's like a fork and there's two ways pause you don't know which one right so all you can do is basically go the most interesting one and they relate this to scientific research so yeah if we want to accomplish some really great research goal like artificial general intelligence we don't like we don't know but we can see the next stepping stones right we can see Oh from what we have right now what interesting combination could we make that's still kinda it still kind of makes that's not total garbage right so in in the local search I can try to say I want to I don't know I want to do this I want to do multiple generators and it's multistage and then this thing right just this is kind of a stepping stone and maybe that will then lead to something more interesting and so on so yeah that's that's kind of how they're related I like this metaphor of the lake yeah yeah like could like a meta controller try to put the stones down and then the objective is that or is the space too enormous that that idea of having a meta controller guide the stepping stone placement is just like absurdum it and there's no way that that would work that's sort of where I'm thinking with this now is like so they actually that's that's exactly the the question right of what I so I believe you need such a matter whatever because the space is too large you somehow need a way to choose the stepping stones in the first place right you somehow need a way to do this now what they're saying is that if you're if your goal is really ambitious then a meta controller that simply wants to reach the goal is bad because right because what we discussed before you might need a lot of inventions from other fields in order to me goal happen and if you simply go your field maximum power towards your goal that's not gonna happen now if your meta controller is actually just something that wants to produce interesting things then that's actually something they they advocate for that is exactly what their algorithms are trying to capture they're trying to capture locally yeah we want to get better at a particular thing what those particular things are and the order of these that should be novelty driven instead of gold ribbon yeah yeah yeah the interesting component I guess I'm sort of biased towards liking the objective design and now I'm thinking like okay well let's abstract those Medic controllers one level up and have a meta meta controller and just repeat this and share hierarchy makes sense and that if you if you if you're if you're a bit cynical that is what you will also hear out of here out of and they have to argue in in their book a lot of guests that like isn't the question isn't the kind of isn't the implementation of a meta controller that just searches for novelty in itself an objective again and then it gives some good reasons why actually you don't you it is different it's more like a constraint on your search if you think of natural evolution for example it isn't really doesn't really have an objective and and if you think reproduction and survival is the objective of natural evolution it doesn't really the good reason they give is the objective has already been fulfilled by the very first organism to ever live right why didn't it stop there why didn't it stop very first cell okay done we fulfill its it's more of a it's more of an actually a constrained optimization where the constraint is you need to be able to survive that's kind of the minimum bar of to being on this planet and then but I'm saying constrained optimization but it's it's not it's not an optimization it's more of like a constraint constraint search yeah I guess it's like I definitely think I'm closed in this world of trying to think of these constraints and problems and I haven't really like thought more generally about just like exploration as a whole but but anyway so I just wanted to ask you generally like your deep learning research I want to ask like what areas of deep learning are you really interested in right now and what do you think is promising in the near future so I'm currently working in adversarial examples that is a really interesting topic there's lots of questions still still open but I'm generally interested in pretty much any anything that is not I'm not too interested in like the newest the newest fine technique on getting the latest state-of-the-art numbers even though that's probably super important for practitioners I'm basically agreeing more with the authors of this tutorial of that let's just try to do interesting things and to me these actually these are these areas in in terms of open-ended open-ended search open-ended learning are very interesting I think reinforcement learning still has a long way to go I think actually NLP still has a long way to go because I don't believe it's the current models are at the end of it so I think it's a really exciting time yeah although think about adversary examples because it definitely flips the CNN idea on its head and in the night so I had one other thing about adversarial examples that I'm interested in is uh there is like an interview with Elon Musk and this Lex Friedman researcher where he asks him about adversarial examples on his self-driving cars and he seems dismissive of it he says he thinks basically you could just average different patches with like test time augmentation to overcome adversarial examples so like in your research do you think that like the example where they add the noise masks to the Panda and they're like oh that's a given now if they just perturb it like nine more times do you think the prediction would average out to pandas so that is a that is a very difficult question and in from experience simply adding noise and then feeding it to the classifier even if you average after that usually will it will defend against adversarial examples to a point but it will also degrade your your classification performance because so maybe I understood it wrong but my understanding is I haven't my input right and I simply add noise to it and then feed it through the network and I could do this many times right in an average the prediction but usually this will help against adversarial examples but it will also also degrade the accuracy of that classifier so it might actually make your self-driving car worse in the in the overall because how often is it gonna be attack against a adversarial example it's gonna be attacked maybe I don't know once or twice a year maybe drives by some some hackers house writes big sticker on a stop sign or something but the rest of the time I would actually like to retain retain the best possible classifier and if I always have to add noise then that that's not possible so there the research we're doing is actually into the direction of can we retain the original accuracy while still kind of detecting these these samples it's I mean it's you somehow have to get a trade off somewhere but just adding noise isn't D isn't the final solution yet like so with these adversarial examples they're only gonna make misclassifications like that if it really is adversarially sought after it's not just like the noise perturbation would be such an enormous base to find it otherwise so yes you really need to try so it was very unlikely that that some random thing of course these networks can be confused by random noise but I think one of the self-driving cars once drove into a big white truck because it was large and white so it thought it was sky but other like like other than these failures yeah you really have to try to find an adversarial example really cool oh yeah I think thanks so much for doing this anybody watching you're listening definitely check out Yannick YouTube channel he has really great paper summaries and all sorts of things thank you hey thanks so much for having me