Neuroevolution of Augmenting Topologies (NEAT)

Key Takeaways

[Music] thanks for watching Henry AI labs this video is gonna explain the neuro evolution of augmenting topologies the neat algorithm laying the groundwork for neuro evolutionary algorithms this video is the first in line of the September theme for Henry AI labs deep learning artificial intelligence videos focusing on Auto ml neural architecture search and hyper cram drop is the optimization with a focus on neuro evolution so please subscribe to Henry air labs if you're interested in these topics neuro evolution is the idea of the artificial evolution of neural networks using genetic algorithms is a really cool idea thinking about combining the biological evolutionary algorithms and simulating them to design neural networks this has shown great promise and complex reinforcement learning tasks like control problems like the cart pole balancing problem and miscellaneous other things dating back from 1993 the neat foundational algorithm for this kind of research and evolving not just the weights as an alternative to stochastic gradient descent but also using neural using evolution to search for the architectures of neural networks was published in 2001 so the motivations for neuro evolution this has been really successful in reinforcement learning control tasks like pole balancing or game play in addition things like auto ml hyper parameter optimization neural architecture search contain these kinds of meta parameters and which we're trying to figure out ways in which we can design neural networks reinforcement learning it has some promise but it's generally been found to be slow differentiable search because things like darts have been pretty successful but neural evolution is a very promising technique that we will explore further in this September theme starting with the foundational paper of the NEET algorithm so prior research to evolving neural networks to the NEET algorithm published in 2001 they mostly focused on evolving just the weights rather than the architecture as well so the topology or the architecture of the network would be chosen before the evolutionary algorithm would begin and then the weight space would be explored by a crossover of network weights and mutation of a single networks weights so you can think about evolutionary optimization comparative back propagation back propagation is where you take the partial derivative with respect to every parameter than networks whereas evolutionary optimization doesn't bother with the partial derivatives with respect to the parameters or rather just mutates them and uses some sort of fitness function and usually crossover as well generally evolutionary algorithms can be viewed in this framework they start with some form of initialization of the population and then these population members are evaluated there might be some form of crossover this can be omitted and then they would be mutated and this cycle would repeat for a given amount of iterations so the key questions that the NEET algorithm looks to answer for its time is is there a genetic representation that allows different topologies to crossover in a meaningful way meaning that how do you encode neural network topologies such that you can have crossover so for example if you have a binary encoding or a graph encoding of neural network architectures it isn't so obvious how you would crossover and mutate different members of the population the second question is how can topological innovation that needs a few generations to be optimized be protected so that it does not disappear from the population prematurely now what this means is that in neural network architectures a bigger model will require more time to optimize so if the population member is mutated such that it becomes more complex and it has random weights odds are that network is not going to perform as well so what you need to do in the neural evolution algorithm is to protect these type of innovations these new structures and developing complexity in the neural networks such that they aren't penalized too much for the additional complexity right away because you do want your neural network in the end to be as small as possible so you have to develop some kind of speciation technique to ensure that the neural networks have enough time to potentially benefit from adding complexity and then the third question is how can topologies be minimized throughout evolution without the need for especially contrived fitness function that measures complexity so this idea is basically how can you reward networks for being as simple as possible without having some function because it's hard to design such a function that doesn't restrict and limit the capacity of the evolution too much some of the key ideas of the NEET algorithm are the genetic encoding the way that they encode the neural networks such that they have a phenotype and a genotype where the genotype is the underlining and underlying encoding of the neural network that will be using crossover and mutation and then the phenotype is the resulting neural network which is used in evaluation the next key idea is the historical marking technique that allows for crossover between neural network architectures and then the speciation technique that allows for you know adding complexity to be rewarded later on so sort of like how biological niches are formed the speciation add on to the neat framework will allow neural network topology is too niche themselves and then only compete within their niche and then this is also done in this next idea the explicit fitness sharing which is where you only compete within your own species but well not only within your own species but generally you're penalized based on your own species rather than competing with the whole population and then the final idea is this minimal structure of initialization rather than starting with a random initialization similar to nature you start with the bare minimum a neural network and then you go up from there this is the technique used in the NEET algorithm to encode neural network architectures so each network architecture has a genotype and then the resulting phenotype so the way the genotype is composed it has a node gene set and that connection gene set so the known gene set just contains the input nodes the number of hidden nodes and then the output so this is used as the reference when the connection nodes find these in and now parameters to construct the connections between nodes and the neural network so each of the connection genes contain the in value out value the weight and then whether it's enabled or disabled meaning that you know just if it's active or not and then an innovation number which we'll discuss further would and this is the innovation number is the technique for how they're going to do crossover in the need algorithm so neat mutations and the encoding space this is the way in which the neat algorithm mutates neural architectures in you know in an evolutionary algorithm this is like the key component this is really like you know like the equivalent of back propagation is mutation in in evolutionary algorithms so the way that this works is the network can either add a connection or add a node so if it adds a connection is basically just connecting nodes that already exists in the network that don't have a connection already so you see that when it adds a connection from three to four it is appended to the end of the genotype and it's given this innovation number so the innovation numbers are maintained through like a global table to maintain that they have this consistency in the ordering so this somewhat limits the synchronous nature of it although like the asynchronous capability of evolutionary algorithms which is one of the best things about using absolute evolutionary algorithms is that it's so easy to paralyze it because you're just mutating and then you know you have things like deep minds population-based search which just grabs to end population evaluates them to further promote asynchronous evolution but this just requires a global table so you could just read right to it and still have an asynchronous kind of procedure but anyways back to this so another mutation it has is to add a node so in this example it's gonna add this new node six so the way that this works is the connection from three to five is disabled remember the disable flag from the connection genotype would be now disabled for the previous connection from three to five so the connection from three to six is appended to the back of the genotype as is the connection from six to five so crossover and network topologies is a challenging problem because of competing conventions meaning that there are many different ways to encode the same function in neural network so in this case both of these networks compute the same funk combination of a B and C even though they're ordered differently and their genotypes might be represented this way and when you cross over you could result with an ABA or CBC you know missing information from the parent networks so the solution of this is to use the historical markings to do sort of an alignment similar to how biological crossover has the alignment of the genes that share the same trait like the alleles of genes so what this does is the parent one and parent 2 are selected for crossover the first lined up based the historical traits that they share so see how they both share one and two but not three and then four and six but not these other ones so the way that the ones that aren't included work is the parrot that performed better is is you keep the historical markings from them so in this case parrot too has a better performance according to the fitness evaluation function so you keep three seven and eight and discard five this is the equation that they use to protect innovation with speciation in the neat algorithm so if you remember back to the original key questions address and the need algorithm they want to have a way to speciate different neural network topologies so that they can only compete with other networks of a similar structure and then therefore networks that are in the process of evolving more complex structure can avoid being penalized for this complex structure and eventually it will optimize their weights for better performance so this Delta function is based on the number of excess genes number of disjoint genes and the average weight difference of matching jeans between two different samples of the population so if this Delta exceeds a certain threshold Delta sub T it will be grouped into a noose it will be grouped into that species so the way that Fitness computation works with speciation is the fitness of a member of the population is penalized with this value being 0 or 1 based on this Delta distance parameter so basically the fitness of a model is penalized based on the size of its species so if a function has a high number like so there's ten other members of this species it's going to be divided by ten or is it there's only two it's going to be divided by two so obviously the less members of the species the better the fitness function so another key innovation in the need paper is the idea of minimal initialization so the in some evolutionary algorithms they are randomly initialized which means that a network could initially have a massive amount of complexity in its structure but we want networks to be as simple as possible and analogous with nature we wanted to start from the you know start from the bare basics but noting the effectiveness of the neat algorithm is initially tested with the XOR boolean logic problem this is frequently used to test neural networks because it requires learning the non garetty to separate with the xor logic so this diagram just shows the initial population sample and then the learned structure when it solves the XOR problem then nee graduates to the cart pole balancing problem this is where it earns to apply a force every like 0.02 seconds such as to keep this pole balanced above the cart from like avoid it from following all the way over so these are the comparisons with the NEET algorithm and other algorithms of its time measured based on how many evaluations it takes until it can successfully balance the pole on different problems this is the same comparison but with a harder pole balancing problem whether it's like two poles and other miscellaneous things that make balancing the pull harder control problem so this is an ablation study on the different techniques proposed like things like using fixed apologies this has the most amount of evaluations and still high failure rate on the pole balancing not using speciation using starting from initially random population numbers actually has it very surprisingly high evaluations required and then not using crossover and then all this compared to all of the innovations proposed in the NEET algorithm so you see how all the different techniques like the historical marking allowing for crossover the speciation the mutation and the initialization all sort of interact with each other in the context of the evolutionary algorithm so another interesting thing to think about with a hyper parameter optimization neural evolution and all these techniques is the is that even the hyper parameter optimization technique NEET has high parameters of itself it has these fitness sharing parameters the population size and the mutation sampling distribution so an interesting thing to investigate could be is it useful to abstract another layer out to have an evolutionary algorithm optimizing an evolutionary algorithm optimizing a neural network and then another idea is the context of evolving weights only developing Tunney that involves the weights and the topology and then recently we've seen weight agnostic neural networks which don't even bother with the weights at all they just focus on a topology and weight agnostic neural networks are so surprisingly successful that they can make net neural networks work even when every single parameter in the network is the same thanks for watching this video on the neuro evolution of augmenting topologies the neat algorithm please subscribe to Henry AI labs if you are interested in deep learning and artificial intelligence and specifically in September focusing on Auto ml neural architecture search hyper parameter optimization with a special emphasis on neuro evolutionary algorithms thanks for watching