NeuroEvolution of Augmenting Topologies (NEAT) and Compositional Pattern Producing Networks (CPPN)
❤️ Become The AI Epiphany Patreon ❤️
https://www.patreon.com/theaiepiphany

👨‍👩‍👧‍👦 Join our Discord community 👨‍👩‍👧‍👦
https://discord.gg/peBrCpheKE

In this video I cover 2 papers:
1) NEAT: NeuroEvolution of Augmenting Topologies - a seminal paper from 2002 that evolves not just the network weights but also network architectures
2) CPPN: Compositional Pattern Producing Networks:
A Novel Abstraction of Development - an interesting model of developmental biology with a completely different approach compared to e.g. cellular automata models

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
✅ NEAT paper: http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf
✅ CPPN paper: http://eplex.cs.ucf.edu/papers/stanley_gpem07.pdf
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

⌚️ Timetable: 
00:00 Intro to NEAT and CPPNs
02:35 Basic ideas behind NEAT
07:55 NEAT genome explained
11:05 Competing conventions problem
13:25 NEAT mutations explained
15:30 NEAT genome mating explained
19:20 Maintaining innovations via speciation
25:25 Explicit fitness sharing
29:45 NEAT on XOR task
31:30 CPPNs and neural automata
36:40 Spatial signal as a chemical gradient abstraction
39:20 Composing functions
45:10 CPPN main idea recap
46:45 Breeding "images" using CPPNs
49:20 CPPNs are highly expressive (symmetries, repetition...)
54:17 HyperNEAT idea explained
57:43 Outro

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
💰 BECOME A PATREON OF THE AI EPIPHANY ❤️ 

If these videos, GitHub projects, and blogs help you,
consider helping me out by supporting me on Patreon! 

The AI Epiphany - https://www.patreon.com/theaiepiphany
One-time donation - https://www.paypal.com/paypalme/theaiepiphany 

Huge thank you to these AI Epiphany patreons:
Eli Mahler
Kevin Stone
Petar Veličković

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

💼 LinkedIn - https://www.linkedin.com/in/aleksagordic/ 
🐦 Twitter - https://twitter.com/gordic_aleksa 
👨‍👩‍👧‍👦 Discord - https://discord.gg/peBrCpheKE

📺 YouTube - https://www.youtube.com/c/TheAIEpiphany/
📚 Medium - https://gordicaleksa.medium.com/ 
💻 GitHub - https://github.com/gordicaleksa 
📢 AI Newsletter - https://aiepiphany.substack.com/

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

#NEAT #CPPN #evolution
 What's cracking guys in this video I'll be covering two very interesting older seminal papers one of them being this one that introduces a method called new revolution of augmented topologies or Neat for short so you may know it by the by the acronym neat And if you ever watched some of those neural network learns to play a game Types of videos and YouTube such as these two are very very popular So the fun fact is both of these videos used the neat algorithm that was introduced in this paper to Train a neural network to play the snake game or to play the Super Mario in this video here the second video I'm gonna the second paper I'm gonna cover is the compositional pattern producing networks or Cpp ends for short and the reason I'm so excited about this paper and that I've discovered it quite recently is that Well, I've been personally thinking about Like approaching machine learning from various different perspectives one of those being genetics The other one being neuroscience and as you may know like there's a lot of people Like doing genetics as their as their primary job And maybe then additionally learning machine learning or deep learning and infusing those two fields together and that's super exciting but like if genetics is step one and Neuroscience ie adult human brains are like step three then like for whatever reason we are missing out on this whole Step in between where after the fertilization after you have the sperm cell Fertilizing the XL and you get the zygote. So then this whole process of development development whereby from this single cell called zygote you end up with a like a adult I mean baby brain baby human brain we kind of don't know what's going on there and In my opinion just understanding that whole procedure Can help us design better architectures. So that's at least my intuition. So basically instead of crafting neural architectures why not understand the actual process a biological process that leads to To like such a complex architectures as the human brain and then train that that architecture So that's the rough idea the CPPM paper Is one of the models of this development process? So covering this this number two here on this drawing and I'll be covering it after need So before that let's just dig into neat and understand how this like optimization method works. Okay So let's start here The goal of fixed topology neural evolution is to optimize the connection weights that determine the functionality of a network And that's something we are we are very familiar with we usually have a fixed architecture of this fixed topology and we try and We try and tune the weights now they see here the basic question However remains can evolving topologies along with weights provide an advantage over evolving weights on a fixed topology So again, let me just kind of reiterate here Usually what you end up with in machine learning is at least in deep learning So if you have a neural network, let me just kind of draw for simplicity sake a simple NLP model a single hidden layer So it's gonna be connected something like this. So you have Connection going from input neurons to output neurons something like this and Now what you usually end up doing is you have depending on your task You define a loss function and then you apply some gradient based optimization method Usually Adam is very popular or just a plain old SGD, etc. Etc. So what this like paper instead proposes is Why not learn I mean learn when I discover? architectures and then Tune them along the way as well. So instead What it does is it starts with the simplest possible neural networks where depending on the on the task up obviously you have for example Let's say we have such a task where the input is a scalar and the output is a scalar in that case It will start with a simple neural networks as this one where you have a just a single Connection directly from the input output. There is some weight here and that's that's it very simple and then what they do is basically they have a population of these neural networks and They'll basically be evolving them. They'll be mutating them. They will be discovering new architectures tuning the parameters and By doing that solving the task, so it's a very rough idea behind needs now Let's let's dig into a bit more details. So first let's let's kind of open it up with some questions They say here so evolving structure incrementally presents several technical challenges first Is there a genetic representation that allows disparate? Topologies to cross over in a meaningful way because you can imagine if you have very different topologies like for example Let's take this one and let's take this super simple one. It's not quite clear. How do you go about? doing cross mating between these two architectures, how do you Mix up the genes behind these architectures and if the terminology is not clear enough now I'll get to that in a second, but like Just have some rough mental map for now 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 So what they say here is the following so imagine you have a Imagine you have again a set of population of neural networks and I'm gonna just know them by these simple rectangles just for abstraction sake for for simplicity sake, so Let's say we have like three neural networks and let's say you mutate one of these so these are just MLPs So this is like neural network one two three and let's say you mutate this one by adding additional node here. Okay, and Now what will happen is if you were to continue comparing this novel like this mutated neural network with the Networks two and three it would be a suboptimal probably because initially This is just randomly initialized or something and then it cannot compete and so what they do how needs solves This is they basically do this speciation process whereby they group similar networks together And then they form niches and then these networks compare between each other, but they don't compare with other Global like arbitrary network from from the whole population So that will be the the solution that need introduces to cope with this problem. So basically speciation The third question is how can topologies be minimized throughout evolution without the need for a specially contrived fitness function? that measures complexity and I kind of hinted at the solution already here and the solution is to start with the simplest networks possible and then gradually keep adding the complexity and Because they the optimization procedure of need has this this bias this this inherent bias That's why it's going to be looking for simpler architectures In the first place and this aligns very neatly with the with the principle of the OCam's razor Whereby the the simpler the simplest hypothesis the simplest model that performs Like good enough is probably the best one Okay And the first question will be solved by these historical markings But we're gonna get at that point in a couple of minutes Okay Let me first show you how they represent the networks in the background because if you're not familiar with genetic algorithms Did this all all this may be a bit like weird? And so because of that, let me just start here So what they do is for every neural network in the population of neural networks They keep up they keep this genome in the background So also known as genotype and each genotype corresponds one to two one to one to the to the phenotype Corresponding phenotype. So this genotype basically determines this this phenotype this neural network here And this is just a terminology from genetics So phenotype basically means any observable trait for example in humans that may be like the eye color That means like maybe like blood type whatnot and there is some gene that's going up for that particular phenotype for that observable trait So that's the terminology they are taking here because this is this whole optimization field is roughly loosely inspired by the genetics and and Thus the terminology Okay, so you can see here they have two different lists of of uh, like genes versus the node genes So we have node one through node five corresponding to these nodes here one through five And you can see there are different types of nodes So some of these are sensor nodes, which means input nodes Some of these are output nodes like node four here and then we have the hidden nodes the node five here More interestingly, they have these connections genes and you can see how each of these squares basically describes these connections So let's take this one for example, so you can see here. We have one. Let me just change the color to red here So we have one as the input and then four as the output so that basically specifies this particular connection here You can see the weight is 0.7. You can see that it's enabled I'm going to tell you what that is in a minute and we have this innovation number also known as this historical marker Which is a very important part of this whole algorithm and i'll get into a bit more details a bit later Okay, so this enabled thing so let me contrast that with disabled So we have this connection between two and four and if you take a look There is no connection between two or four because it's disabled and again this terminology comes from the genetics Genes can be expressed or not expressed if a gene is not expressed then basically you don't have the associated phenotype so for example You don't want to so for example if you have you have obviously different cell types in your body You have like skin cells you have like muscle cells you have neurons or neural cells and obviously a muscle cell Doesn't need a certain proteins that the neural that the neural cell needs and thus those are the Neural that the neural cell needs and thus those genes are not expressed in that particular cell So that's the rough Like yeah background in genetics behind all of this terminology so That's that's roughly it. So now that we have this list this list This genotype completely specifies a particular network and then you can kind of mutate these and we'll get to that in a second Okay, so before that let me just uh first mention this problem of competing conventions so Let me tell you what this is and why should we care? You can see two neural networks here on the left and the right And basically these two neural networks have the same function And the reason is you can see here Basically c is the same as c here b's are the same nodes and a's are the same node They're just permuted and because we have a sum function here because we as you know How these neurons work you have a summation here, which is permutation invariant Which means we don't really care about the order of these nodes and because of that the function will be the same and you can Just kind of think about it and you'll see that what I just said makes sense So it doesn't matter like no matter the permutation you'll you'll end up with the same functionality in the neural network Now why this is problematic for genetic algorithms is the following So if you want to cross these two genomes, so let's say we have genome a b and c and we have c b and a If you were to do a point wise mutation So that means you'll take a certain gene from let's say we have a b c and we take Instead of c we take the gene a we end up with a b and a if we had a point mutation That's happening in this genome. So if this one was the dominant genome and we were to mutate a into c by randomly taking the gene from this genome instead We end up with c b c now why this is bad is because as you may notice here We just lost one third of the information in from the from the from the original Genotypes and that's obviously undesirable. So we want to be able to recognize and match corresponding genes Because we don't want to lose them and that's where these historical markings come into play and we'll get to those in a minute So let me just kind of reiterate when one of these permutations crosses over with another critical information is likely to be lost For example crossing a b c and c b a can result in c b c a representation that has lost one third of the information that both of the parents had Okay, so neat basically solves this problem by doing this historical Markings stuff Okay, let's continue here and let me show you the mutation procedure And then we're going to slowly build up the whole holistic picture of how this need algorithm works So i'm kind of going bottom up which is contrary to my usual approach of going top to bottom But like in this particular paper, I guess that makes some sense There are two types of mutations we can we can imagine here one is Adding like a connection and the other one is adding a node. So Let's focus on the first one adding connection. You can see here that we add this connection between neurons three between nodes Three and five and you can see that we added so starting from this genotype here After we added the connection between three and five with the historical marking seven or innovation number as it's also called So we end up with this novel genome here. We have the other Mutation having a node Um mutation happening here here. Uh, we add the node so you can see here. We add node six which basically Like disables this previous connection and that's two novel connections and that's why we have so between three and four This one will be disabled and you can see that we added from three to six So we have this one and we have from six to four So we added two novel connections and we have the novel innovation numbers here So this is the way in which um basically Neat adds the additional complexity to the current population So again, retracing the top number in each genome is the innovation number of that gene The innovation numbers are historical markers that identify the original historical ancestor of each gene New genes are signed new increasingly higher numbers In case in other instance of a neural network adds the exact same connection. Let's say Uh this connection three to five then They would reuse the this innovation number seven for that particular instance as well So there would not be like a blow up artificial blow up of these of this historical markings and that's why they they work Okay So that's some background now. Let's dig a bit deeper Um, so they say here i'm just going to skip this part because we already covered it So in the future whenever these genomes meet the offspring will inherit the same innovation numbers on each gene Innovation numbers are never changed Okay, they are never changed thus the historical origin of every gene in the system is known throughout evolution Okay So when crossing over the genes in both genomes with the same innovation numbers are lined up So we line them up we're going to see an image in a second and these genes are called matching genes So we have the matching genes genes that do not match are either disjoint or excess Depending on whether they occur within or outside the range of other parents innovation numbers In composing the offspring genes are randomly chosen from either parent and matching genes Whereas all excess or disjoint genes are always included from the more fit parent. So that's an important detail here Okay So let's see all of that pictorially here Let's assume we have two different topologies from the same population from the same subpopulation Same species if you want, although they sometimes do interspecies and intra species. They do both intra and interspecies Crossing but here so you can see two genomes and what they do. Let me just kind of zoom in a bit They align these two genomes according to these Like innovation numbers so you can see one one two two three three four four five five All of these are aligned and then you have the disjoint ones because six and seven from this one does not exist In this genotype and then we have eight being disjoint and finally we have these excess genes Because they are out of the range of the parent one Okay So now how the crossing works is you basically randomly take gene from either parent one or parent two Uh when it comes to these matched genes, so you can see here This is kind of gray, which means we took that one from the parent one then this is uh Okay darker gray, which is maybe from either of the parents and this is uh, White-ish which means we took it from here then we took it from here and finally we took it from here So that means we are randomly taking genes from from either parent Finally, we take the the genes from the more fit parent and because in this particular case They kind of have equal fitness both of these they they kind of end up taking all of the genes and we end up with the offspring Genotype here and you can see the corresponding phenotype exactly here Okay So that's cool now We can slowly start and build up the whole picture Let me first read a couple more sentences and then i'm gonna kind of draw a diagram explaining the whole the big picture Okay. So again retreating in this case equal fitnesses are assumed. So the disjoint and excess genes are also inherited randomly so the reason I kind of highlighted this is to show that one of the the cons of this approach is that it's super complicated compared to gradient-based methods such as sgd Where it's quite straightforward and uh, there is not a lot of hyper parameters Whereas here in need there is a lot of things you have to kind of tune the population size how to speciate how to set The thresholds we'll see that in a second But it's there's a much more details to to think about compared to gradient-based optimizations so For example, the disabled genes may become enabled again in future generations So that means some of these may be randomly enabled again Also, there's a preset chance that an inherited gene is disabled if it is disabled in either parent So that's another detail to think about okay Now as I mentioned these mutations will create suboptimal neural networks After the the actual mutation happens and before the optimization of that neural network happens There's going to be a suboptimal architecture So how do we make sure that the innovations survive and the answer is here? By adding new genes to the population and sensibly meeting genomes representing different structures The systems can form a population of diverse topologies However, it turns out that such a population on its own cannot maintain topological innovation and that's quite important to maintain Because smaller structures optimize faster than larger structures and adding nodes and connections usually initially decreases the fitness of the network Recently augmented structures have little hope of surviving more than one generation Even though the innovations they represent may be crucial towards solving the task in the long run The solution is to protect innovation by speciating the population as explained in the next section And this is the most important part of the paper Probably, I mean it's one of the most important details. So let's dig a bit deeper So let's see how they define how do they discriminate between how do they separate a special neural a new neural network a new offspring into into a species How do they assign a species to that particular neural network? And we can see it here So the number of excess and disjoint genes between a pair of genomes is a natural measure of their compatibility distance The more disjoint two genomes are the less evolutionary history they share and thus the less compatible they are Therefore we can measure the compatibility distance delta of different structures in need as a simple linear combination of the number of excess and disjoint genes As well as the average weight differences of matching genes including disabled genes So you can see a simpler a very simple way to determine how different how incompatible to or compatible to genotypes are So you can see the more of excess genes we have between two genotypes and or the more disjoint genes we have Or even if we have matching like genes if the actual weights of those connections are quite different than depending on c3 and this variable here this delta can explode So once we have this once we have this way of measuring compatibility we can just they just set a threshold So the distance measure delta allows us to speciate using a compatibility threshold delta t And that's how you basically speciate So continuing on a given genome g in the current generation is placed in the first species in which g is compatible with the representative genome of that species If g is not compatible with any existing species a new species is created with g as its representative Okay now it's a good time to draw some diagram and explain what's going on here So imagine we have multiple subpopulations so let's imagine we have multiple species so here is a species one Then we have some bit bigger species we have another species here and so what happens is the following Now these are the most like these are the fittest individuals from the last generation and I'm going to explain how do we determine fitness and how do we prune based on fitness a bit later But for now just assume all of these subpopulations are left with the fittest individuals Now what you do is you do some basically crossing so you'll take two parents here and you cross those two and you end up with another with the offspring And so this offspring now needs to be compared with representative genomes in order to determine which species it belongs to So even though it originates from this species it now because of these mutations and because of the crossing of the genes from the parents It may end up being a different species altogether which does not make a lot of sense when it comes to this like discussing I guess biological creatures At least not the vertebrates but yeah so let me denote that like this so let's let me just do this So basically what I do is you randomly pick a genotype from this population and that's going to be G and you do the same thing here just randomly pick one and then you do the same thing here and for every single subpopulation And now what you do is the following so you take the freshly created offspring here and you calculate the compatibility measure so this thing here So you can basically you'll basically end up with a couple of numbers you'll have some some delta here you'll have and you'll see whether this delta is below the threshold If it's below the threshold that means that we need to assign this particular offspring to this species So what I do they have some canonical ordering of these subpopulations so that means maybe maybe this one's going to be like subpopulation one then two then three And the first subpopulation where the compatibility is lower than the threshold they just kind of allocate they just kind of assign that offspring to that subspecies So for example these two were not compatible if this G the representative genome from this subpopulation was not compatible with the offspring then we would continue with with the representative G from the second subpopulation Which is in this particular case the same species from which this offspring originates from so now if the compatibility was lower than threshold with would kind of assign again the offspring to this subpopulation so that's the rough idea So after this crossing happens I guess what happens next is just some random mutations and then they assert the fitness of all of the individuals of individual genotypes genomes in the whole population Let's see how the fitness is determined so fitness is basically depends on the particular task at hand so depends what you're trying to solve with need so fitness will be very very domain specific basically The important detail is that they use something called explicit fitness sharing which means they do this and that means that so not only do you care about the particular individual You also care how big is the species that that individual belongs to and that's denoted like algebraically by this formula so basically summation from one to through n where n is the whole population size so including all the species And then we have this sh function which is basically set to one when the this compatibility threshold is below below the this compatibility measure is below the threshold which basically means hey this is going to be the size of the species that this individual belongs to So that's a long long story short so because of that even if you have very very fit individuals if the species it belongs to is very big the this adapted I think is adjusted fitness is going to be lower so that means some other less fit individuals from smaller subpopulations have the chance of surviving to the next generation Let me just read you a couple of more sentences here so they say every species is assigned a potentially different number of offspring in proportion to the sum of adjusted fitness is of its member organisms species then reproduce by first eliminating the lowest performing members from the population The entire population is then replaced by the offspring of the remaining organisms in each species okay let me recap what I think is going on here so the bad thing about the paper is that they don't have like a like a pseudo algorithm specifying the steps in the exact order so I kind of have to infer what's going on without digging into the actual software packages which are as I said quite complex compared to just your regular back back grading based optimizations so as I said let's let's assume we have these subpopulations here and then we determine the fitness of each of the individuals and then basically we're going to prune the less fit individuals in each of these subpopulations so we'll end up with some subsets of each of these subpopulations okay and now depending on the size of those like subsets each of these species will have a certain number of offsprings they can generate so that means now we'll take the parents we'll do the crossing we'll have an offspring and then we'll just kind of alloc assign it to your species depending on the as I previously discussed on this compatibility measure and we rinse and repeat for all of the subpopulations that same algorithm after we do that I guess what happens is inside of the before you start evaluating them and trying to figure out the fitness of these novel individuals you do some mutations so adding connections adding notes and then only then do you evaluate the fitness and then the circle repeats you prune out the weakest individuals the ones with the lowest fitness value and rinse and repeat and rinse and then you rinse and repeat okay final detail worth mentioning is that so as discussed in section 2.4 blah blah blah so this just means topology and weight evolution artificial neural networks so basically evolving both the topology and the weights and not just the weights as we are used to so these twins if that's the way you pronounce this typically start with an initial population of random topologies in order to introduce diversity from the outset so that's how these other approaches do it in contrast neat biases the search towards minimal dimensional spaces by starting out with a uniform population of networks with zero hidden nodes and we saw that in the beginning of video but I thought worth mentioning that okay so that's pretty much it that's neat they then showed some results on a couple of tasks one of those tasks is this XOR so your your logical gate using all over computer science and they show that they can basically find a topology that can perform the XOR function for that you need to have at least one hidden node and you can see here so basically this is the initial individual of the of the population and then after applying meet they end up with this phenotype with this individual they can solve the XOR problem you can see it had to add some novel nodes you see a novel note here you can see novel connections here and basically the weights which you can see on this on this diagram are also changed so that this performs the XOR function okay so hopefully you like the idea behind the neat paper I think it's very cool because it's inspired by evolution and it has this progressive building of build up of complexity and you're trying to find the topologies you're trying to at the same time tweak those weights and find the simplest individual that can solve the task that you care about now the the con side about this whole approach as you can see it's quite intricate there's a lot of details you need to care about and all of that makes it a bit less attractive and since this paper was published in two thousand two we haven't seen we really haven't seen the push towards this research direction but nonetheless I think it's a very valuable like idea to keep in your mind okay next up let me walk you through the compositional pattern producing networks okay so on to compositional pattern producing networks a novel abstraction of development paper and before we dig into CPPN's deeper let me give you another example of a very popular like model of development with which you may be familiar with already and that's the cellular automata models so let me open up this very cool distilled pop and let me just kind of slow this down so that you can see what's going on so you can see here that through local interactions so each of the cell is communicating only with the neighboring cells and via a couple of simple rules and in this case the rules are learned and hence this is called neural cellular automata you can see that this phenotype this body plan this morphology albeit a 2D one is built up and this could easily be generalizable to 3D space and thus to the space where we live in and we could be building like real 3D bodies using cellular automata so this is a model of development as well so you can see you can imagine starting from a zygote from a single cell and then through some type of communication local communication that's very important you end up with this particular morphology so now what CPPN show is that you don't need to have this local communication going on and temporal unfolding and that's just like a consequence of the fact that we live in a physical world with physics where the laws of physics are at play and this constrains the developmental process to do it like this so let me now go back to CPPN and let's see how they actually approach this let's start by reading the abstract a little bit natural DNA can encode complexity on an enormous scale researchers are attempting to achieve the same representational efficiency in computers by implementing developmental encodings ie encodings that map the genotype to the phenotype through a process of growth from a small starting point to mature form a major challenge in this effort is to find the right level of abstraction of biological development to capture its essential properties without introducing unnecessary inefficiencies okay so the rest of the paper will show how they found a different model how can a Stanley found a different model to for this developmental process so basically the main contribution of the paper is to establish that CPPN are legitimate abstraction of natural developmental encoding which may not be super obvious on the first glance of this paper so let's start here so what like the example here shows that you can have basically this phenotype being generated by this function F instead of having so basically instead of having local interactions are having this temporal unfolding to get the final to the morphology in this case the morphology is just a triangle so this is not like a biological like morphology but nonetheless you can just kind of abstract it away and let's deal with mathematical objects into the space so it's the same thing so F is a developmental model of this of this triangle if you will okay so so basically they say here that a developmental chronology is only one way of producing a particular constellation of particles it follows that encoding and unfolding process may be unnecessary to produce complex phenotypes because a functional description could alternatively have been evolved such description would not necessitate a long unfolding chain of interactions and productions so the reasoning is why go through why simulate every single intermediate step with what when what we care about is the actual like phenotype and if you could catch capture the whole development inside of a function why not do just that so they state here that so looking at this diagram here so this observation implies that any phenotype produced through a temporal progression is also possible to represent through a functional description so in fact this paper from I think 1989 show that any function can be approximated by neural network with two hidden layers that's the universal approximation theorem and the more neurons in networks to the wider network the more accurate the approximation can be that's any morphology when viewed as a distribution of particle in space is possible to represent as a function without the notion of time so that's the thing they're trying to kind of skip over here and just kind of understanding that that's a more of a physical constraint and something we need to care about when we're trying to develop mathematical models such as this one okay let's let's see this sentence a significant function and early stage of development in natural embryo Jenny is to define a coordinate frame i.e. a set of virtual coordinate axes upon which future stages of development will be based the simplest and most basic of these coordinates frames are the main axis of the body which are defined at the very beginning of development inside the egg itself these axes include the anterior posterior axis i.e. head to feet and the doors or ventral i.e. back to front so what are what they are basically saying here is the following so so the gist of this is that during the development we have to somehow form this intricate patterns and those are usually just chemical gradients and if you if you if you manage to form those chemical gradients then the cells then each cell depending on where it is located in depend on this and this and this chemical gradient map will know what to do so we'll know what exactly to do depending on the on the on that scalar of the of the chemical gradient so if you are able to capture the pattern of this chemical gradient without even having the local interactions or the temporal unfolding then we can capture the development itself and you can see that because of this left to right gradient which is in the form of a Gaussian function this this if this basically implies that we'll have will end up with a bilateral symmetry and you can see that this fly here has a symmetry bilateral symmetry so if I were to draw a vertical axis through this fly here you can notice that we have a symmetry here can just flip it and nothing would change the underlying structure which is in this case that the fly the to the image of a fly would not change and similarly there is a gradient along this anterior posterior axis and different patterns along along those those along the axis produce different cells so basically you can ignore all of this and you can imagine so you can ignore all of this and you can imagine we have a certain like just draw this so we have a certain to the spatial pattern here so it will be hard to draw but you can imagine going from so around this axis here it's going to be quite symmetric left and right and that's so basically this to the spatial signal is going to directly in code those chemical gradients and that's gonna basically allow us to to to form this this this this morphology here and that means we can ignore we can just focus on trying to generate these intricate to the spatial patterns okay so now let's see how do we generate these to the spatial signals which are going to loosely represent these chemical gradients and that's gonna be a blueprint for how to generate the morphology like the body of some biological organism or or whatnot so because we're trying to remember we're trying to build a developmental model for biological organisms so so here's one way we could be composing functions so here we have a symmetric function here we have a periodic function you can see we can generate arbitrary patterns by doing this they mentioned here that coordinate frames created through a developmental process interact with each other to produce complex patterns with regularities in the same way functionally represented frames can be composed to create complex regularities so in this way and this has been mentioned over and over again throughout the paper so the composition the function composition replaces local interactions okay so instead of having some some local cellular automata like communication we can just compose the the the various functions to end up with these to the spatial signals we we care about I mean I'm saying to the but those could be 3d or or even 40 as we'll later see and it's just a pattern we're trying to to to generate so here is the how cppn's look like and they say that the main idea is that the order in which functions are composited is an abstraction for the chronology of events over the course of development without the need for simulating such events locally so in a way signal flowing from from here to here is is an abstraction for the chronology of time so even though we don't have any notion of time in this network per se we are kind of capturing the time and all of these local interactions by doing this functional compositing so starting from X and Y which are just the coordinate coordinates of your of your Cartesian plane we can generate the output the phenotype by by by composing functions and here compared to your regular artificial neural networks what cppn's do is instead of like just using rally or sigmoid for the activation function they use arbitrary like functions which are which have some nice properties so it's either like a Gaussian or some symmetric function or like identity function or a periodic function etc etc so this is what how cppn's look like okay they mentioned here that providing the initial coordinate axis as inputs to the graph is what allows local interaction to be eliminated in physical space there are no intrinsic coordinates that are individual cell can access to determine its location and hence its identity therefore local interaction becomes a way of asking where am i that is through the collective negotiation for Jason cells that interact with each other it is possible to derive a coordinate frame however by composing functions and that take as arguments and absolute frame of reference the need for such negotiation is eliminated and all identities and relative locations can be determined completely independently so basically what they said here is we can kind of feed these absolute coordinates into the cppn to generate this this output pattern and instead you can imagine the difficulty that a cell has like it needs to figure out where it is based on the local communication with the with the neighboring cells and this this this cppn model basically replaces a little bit of cppn model basically replaces eliminates the need for for that type of communication to happen so as I mentioned there is a lot of similarity between like neural networks your regular neural networks and cppn's and they say here interesting a graph of such compositions is very similar to an artificial neural network with arbitrary topology the only difference between the two is that artificial neural networks generally use sigmoid functions and sometimes gossians or relius or whatnot as activation functions in each note whereas the function composition graph may use any of a variety of biological functions at each note as I previously mentioned they then say that the analogy between a function composition graph and a neural network is so strong in fact that is stamping to equate the two however while from an external objective standpoint they are closely related so from the mathematical standpoint I guess using the term artificial neural network would be misleading in the context of this discussion because neural networks were so named in order to establish a metaphor with a different biological phenomena and that's the brain and the terminology should avoid making the implication that biological thinking brains are in fact the same as developing embryos this is kind of loose because in one of their follow up papers in one of Kenneth Stanley's follow up papers called a hyper neat he shows that you can basically use cppn's to model neural networks by just modeling for the spatial signals you can map that to neural networks so which means that in the fact this can be a model of a brain as well so these are very abstract objects cppn's are very abstract and they are very abstract and they can capture arbitrary spatial patterns which can be mapped to various things so they can be mapped to like chemical gradients fields which then can be used as a guide for formulating morphology like the body of an organism or it can be just a like a plan for how to construct construct the actual brain the architecture the design of a of a of a neural network okay so let me recap what what we've seen so far it's a bit harder to follow along because there is a lot of text and not that many images so yeah stick with me basically the idea is the following so if you want to produce a certain morphology beat the 2d body like in this case or a 3d body all you want to do is be able to specify arbitrarily complex spatial signals so that means you want to have certain properties like you want to be able for your your system to generate symmetric patterns you want to be able to generate imperfect symmetry you want to be able to basically a model a repetitiveness etc etc and once you have that spatial signal you can imagine you can you can basically treat that as a as an abstraction for actual physical processes such as chemical gradients which is cell uses to communicate and build up the body so if you can get to the spatial signal then you're basically you've solved the task and you've successfully modeled the developmental process and so how we can do that that's what the cpn paper shows is by just composing these arbitrary not arbitrary these special functions such as gaussians symmetric functions periodic functions etc and you can generate those those patterns by doing this we basically skip through the whole local communication temporal unfolding thingies that are going on and we just end up with a final plan with the final map that's eventually going to build up the phenotype okay so now for the fun part let me show you what I've done they basically used and that's why I cut where I covered neat so they basically is need to evolve cpn such that we can produce very complex patterns with all of the necessary properties that showcase that this is indeed a good model of development and now we're going to show you a couple things so here is the experiments they've done so various people created these platforms so you on the left you can see this Nelphy neat platform on the right you can see this sharp neat platform and basically what you can see here is the following so this is a phenotype so basically this this this chemical gradient map that was created by a cpn in the background so each of these images is you can see are these 2d spatial signals which we can interpret as I said multiple times chemical gradients and each of these are in the background created by a particular cpn and the same thing on the right and so what you do here is using neat and using people to select the parents we can we can evolve more complex and more complex spatial signals so what that means is the following so they said this particular pattern is going to have a cpn in the background so it's going to be some cpn number one this is going to be cpn number two so somebody for user takes these two and we match the genes and we do the crossing and then we do all the mutations etc etc we're going to end up with a novel cpn which means that in turn we're going to end up with a novel pattern and now because humans are in the loop here they can select interesting patterns and thus across breed interesting patterns to create even more complex patterns and if you do that you end up with very school parents and let me show you some of those by the way just a slight detail so aside from x and y what they additionally input is this signal d which is just your your your distance from the center of your domain here and this could be in theory learned by the cpn by just composing some some functions there but like this makes it a bit easier this is just a kind of a shortcut the biases this cpn towards being i guess radially symmetric i think they mentioned somewhere so however since the is radially symmetric it does not automatically provide a bilaterally symmetric coordinate frame okay so the is biasing the cpn towards radial symmetry let's see some results so you can see that people manage to generate symmetric patterns such as this one which is a very important finding because as we saw with the fly example when you have this bullet bilateral symmetry pattern then that means you can form by let bilaterally symmetric bodies and this is the corresponding cpn that is generating this particular pattern they also showed that they can evolve quite intricate patterns so you can see here the idea is to create a spaceship and again people were just playing taking certain parents certain cpns across breeding them and mutating them and we end up with this sequence so this is these are like this is like maybe generation number one and then basically we are evolving with each generation you have more and more intricate patterns and you can see what happens is that we're kind of elaborating on certain details whereas this overarching pattern this this bilateral symmetry is preserved throughout this whole sequence all the way to the end where we have these all this looks more like mental rate and then like a spaceship maybe this looks like an airplane but in all case in any case you can see that we can generate very very complex patterns with all of the necessary properties using cpns important thing is to to be able to represent not just perfect symmetry but also imperfect symmetry because for example take human body as an example so your heart is not perfectly symmetric so your heart is moved a bit to the left instead of being centrally positioned so that's a very good example of imperfect symmetry in our bodies so we want to be able to represent that in our in our in these signals so here they show that aside from having perfectly symmetric sunglasses pattern that somebody produced we can have also this this this imperfect symmetry where you can see that this part is of different size compared to the to this left I guess part of the signal so that's another important argument for the expressivity of the cpns now again repetition is something that's super important and repetition with variation is also important so similarly to how it's important to have imperfect symmetry and not just perfect symmetry so we will also want to have some variations in the repetition not just perfect repetition so here they show that if you input these additional these special signals like sign sign of 10x and sign of 10y and then the d which is the distance from the center if you input these signals we generate very complex patterns and now you may think to yourself now this is cheating because why would you input sign so it's instead of just your regular x and y coordinates and the thing is this is just kind of convenience because cpns could in theory learn without any problem to combine because they do have signs at their disposal when composing the cpns itself so they could learn the same thing this is just for convenience and you can see amazing patterns popping up here so here you can see there is a lot of repetition obviously but there is some variation as well so if we were to zoom in into this region then you get this one here and you can see that obviously that this kernel here is is different from from this one here and yet yeah like a bunch of images further testify that this is the case yeah going forward you can see that in some cases that the cpn learns to ignore those sinusoids and focuses more on the d signal either distance from the center of the image and then you end up with these very intricate patterns which are much more radio symmetric compared to the previous ones and they indeed they showcase that that's not like a cherry picked example a lot of times the cpns end up with these signals that have all of these nice patterns that have all of these nice properties so that's pretty much it they mention finally this is an important sentence so the importance of local interaction to developmental abstraction is an open question they basically show that cpns are an interesting alternative to cellular automata or other models of developmental biology now I did briefly mention that even though they are using cpns as a as a developmental model they can also use it to just model various neural network architectures and let me show you how that could be done like a simple interpretation of these spatial signals that are generated by by by cpns so if you if I were to take this simple cpn let me just find the diagram so this one here now let's imagine that instead of feeding in the signal deep let's imagine we feed in x1 y1 and x2 y2 and then we somehow learn cpn so that the outputs this output scalar is has such prop like the similar properties to what we've seen in 2d signals so being symmetric being being repetitive etc etc now if we were to constrain the the range of these signals to be from 0 to 1 this is basically a signal defined on on a 4d hypercube and what's now interesting is how you can interpret this so you can interpret it the following way so imagine we have a grid imagine we have a grid like this and so let me just draw the vertical lines and the horizontal lines and let's now imagine you input the coordinate so this is x1 y1 and this is x2 y2 and you plug in these numbers so this is going to be for example 0 0 this is going to be maybe 0 and this is going to be 0.2 because like basically what I've done is I've normalized the the the length of this grid to be so this is where 0 is this is 1 and similarly here so we have 0 being here and 1 being here and then we just take the coordinates and you get output and you get some number as the output and you can interpret that as a as a as a weight of the connection between these two cells and that means you can now build neural networks that have symmetric connections that have repetitive connections etc etc by just finding appropriate cpp ends so that's the whole idea behind the hyper need paper that's a follow-up work after that came after this paper so again let's imagine this is maybe output 0.7 for these particular coordinates so that means this is going to be of weight 0.7 and then you just start tracing you just do an extensive search you basically input all the possible combinations here and for example you set a certain threshold so if a certain weight is below I don't know like maybe 0.3 then there is no connection there otherwise you have a connection with the given weight and that's how you form a neural network by using a cppn so why this is very cool is because you can use a much smaller model so this cppn may have like hundreds or thousands of nodes and you may end up with like millions or even billions of connections in your in your neural networks this is like basically a low dimensional representation like the gist of your of your phenotype which is in this particular case a neural network cool hopefully you found some interesting ideas in these two papers if you did consider subscribing share the video out and join the discord community as well and until next time bye bye you
[{"start": 0.0, "end": 6.76, "text": " What's cracking guys in this video I'll be covering two very interesting older seminal papers"}, {"start": 7.04, "end": 14.36, "text": " one of them being this one that introduces a method called new revolution of augmented topologies or"}, {"start": 15.040000000000001, "end": 18.740000000000002, "text": " Neat for short so you may know it by the by the acronym neat"}, {"start": 18.740000000000002, "end": 23.400000000000002, "text": " And if you ever watched some of those neural network learns to play a game"}, {"start": 23.92, "end": 27.76, "text": " Types of videos and YouTube such as these two are very very popular"}, {"start": 27.76, "end": 30.200000000000003, "text": " So the fun fact is both of these"}, {"start": 31.240000000000002, "end": 36.68, "text": " videos used the neat algorithm that was introduced in this paper to"}, {"start": 37.44, "end": 43.56, "text": " Train a neural network to play the snake game or to play the Super Mario in this video here"}, {"start": 44.28, "end": 47.480000000000004, "text": " the second video I'm gonna the second paper I'm gonna cover is the"}, {"start": 48.400000000000006, "end": 51.120000000000005, "text": " compositional pattern producing networks or"}, {"start": 51.12, "end": 58.239999999999995, "text": " Cpp ends for short and the reason I'm so excited about this paper and that I've discovered it quite recently is that"}, {"start": 58.76, "end": 60.76, "text": " Well, I've been personally thinking about"}, {"start": 61.559999999999995, "end": 67.08, "text": " Like approaching machine learning from various different perspectives one of those being genetics"}, {"start": 67.64, "end": 71.72, "text": " The other one being neuroscience and as you may know like there's a lot of people"}, {"start": 72.32, "end": 75.68, "text": " Like doing genetics as their as their primary job"}, {"start": 75.68, "end": 82.52000000000001, "text": " And maybe then additionally learning machine learning or deep learning and infusing those two fields together and that's super exciting"}, {"start": 82.64, "end": 85.12, "text": " but like if genetics is step one and"}, {"start": 86.16000000000001, "end": 93.24000000000001, "text": " Neuroscience ie adult human brains are like step three then like for whatever reason we are missing out on this whole"}, {"start": 93.56, "end": 98.60000000000001, "text": " Step in between where after the fertilization after you have the sperm cell"}, {"start": 99.44000000000001, "end": 104.16000000000001, "text": " Fertilizing the XL and you get the zygote. So then this whole process of development"}, {"start": 104.16, "end": 111.2, "text": " development whereby from this single cell called zygote you end up with a like a adult I mean baby"}, {"start": 111.72, "end": 115.75999999999999, "text": " brain baby human brain we kind of don't know what's going on there and"}, {"start": 116.39999999999999, "end": 120.32, "text": " In my opinion just understanding that whole procedure"}, {"start": 121.24, "end": 127.28, "text": " Can help us design better architectures. So that's at least my intuition. So basically instead of"}, {"start": 128.0, "end": 129.8, "text": " crafting neural architectures"}, {"start": 129.8, "end": 134.4, "text": " why not understand the actual process a biological process that leads to"}, {"start": 135.0, "end": 141.8, "text": " To like such a complex architectures as the human brain and then train that that architecture"}, {"start": 141.8, "end": 145.12, "text": " So that's the rough idea the CPPM paper"}, {"start": 145.64000000000001, "end": 149.32000000000002, "text": " Is one of the models of this development process?"}, {"start": 149.32000000000002, "end": 155.48000000000002, "text": " So covering this this number two here on this drawing and I'll be covering it after need"}, {"start": 155.48, "end": 162.84, "text": " So before that let's just dig into neat and understand how this like optimization method works. Okay"}, {"start": 163.51999999999998, "end": 165.12, "text": " So let's start here"}, {"start": 165.12, "end": 172.95999999999998, "text": " The goal of fixed topology neural evolution is to optimize the connection weights that determine the functionality of a network"}, {"start": 172.95999999999998, "end": 179.28, "text": " And that's something we are we are very familiar with we usually have a fixed architecture of this fixed topology and we try and"}, {"start": 179.51999999999998, "end": 183.85999999999999, "text": " We try and tune the weights now they see here the basic question"}, {"start": 183.86, "end": 192.34, "text": " However remains can evolving topologies along with weights provide an advantage over evolving weights on a fixed topology"}, {"start": 192.48000000000002, "end": 194.84, "text": " So again, let me just kind of reiterate here"}, {"start": 195.72000000000003, "end": 199.12, "text": " Usually what you end up with in machine learning is at least in deep learning"}, {"start": 199.16000000000003, "end": 206.28000000000003, "text": " So if you have a neural network, let me just kind of draw for simplicity sake a simple NLP model a single hidden layer"}, {"start": 206.44000000000003, "end": 209.8, "text": " So it's gonna be connected something like this. So you have"}, {"start": 209.8, "end": 213.36, "text": " Connection going from input neurons to output neurons"}, {"start": 214.28, "end": 216.28, "text": " something like this and"}, {"start": 216.44, "end": 220.84, "text": " Now what you usually end up doing is you have depending on your task"}, {"start": 220.84, "end": 225.68, "text": " You define a loss function and then you apply some gradient based optimization method"}, {"start": 225.68, "end": 231.96, "text": " Usually Adam is very popular or just a plain old SGD, etc. Etc. So what this"}, {"start": 232.64000000000001, "end": 234.8, "text": " like paper instead proposes is"}, {"start": 234.8, "end": 239.20000000000002, "text": " Why not learn I mean learn when I discover?"}, {"start": 239.84, "end": 241.60000000000002, "text": " architectures and then"}, {"start": 241.60000000000002, "end": 244.96, "text": " Tune them along the way as well. So instead"}, {"start": 245.60000000000002, "end": 253.44, "text": " What it does is it starts with the simplest possible neural networks where depending on the on the task up obviously you have for example"}, {"start": 253.44, "end": 258.6, "text": " Let's say we have such a task where the input is a scalar and the output is a scalar in that case"}, {"start": 258.6, "end": 263.28000000000003, "text": " It will start with a simple neural networks as this one where you have a just a single"}, {"start": 263.28, "end": 267.67999999999995, "text": " Connection directly from the input output. There is some weight here and that's that's it"}, {"start": 267.67999999999995, "end": 273.71999999999997, "text": " very simple and then what they do is basically they have a population of these neural networks and"}, {"start": 274.35999999999996, "end": 280.47999999999996, "text": " They'll basically be evolving them. They'll be mutating them. They will be discovering new architectures tuning the parameters and"}, {"start": 282.15999999999997, "end": 287.0, "text": " By doing that solving the task, so it's a very rough idea behind needs now"}, {"start": 287.0, "end": 292.58, "text": " Let's let's dig into a bit more details. So first let's let's kind of open it up with some questions"}, {"start": 292.58, "end": 299.09999999999997, "text": " They say here so evolving structure incrementally presents several technical challenges first"}, {"start": 299.09999999999997, "end": 302.74, "text": " Is there a genetic representation that allows disparate?"}, {"start": 303.18, "end": 310.62, "text": " Topologies to cross over in a meaningful way because you can imagine if you have very different topologies like for example"}, {"start": 310.78, "end": 316.59999999999997, "text": " Let's take this one and let's take this super simple one. It's not quite clear. How do you go about?"}, {"start": 317.38, "end": 321.06, "text": " doing cross mating between these two architectures, how do you"}, {"start": 321.06, "end": 326.78000000000003, "text": " Mix up the genes behind these architectures and if the terminology is not clear enough now"}, {"start": 326.78000000000003, "end": 329.18, "text": " I'll get to that in a second, but like"}, {"start": 329.9, "end": 333.26, "text": " Just have some rough mental map for now"}, {"start": 333.78000000000003, "end": 340.78, "text": " The second question is how can topological innovation that needs a few generations to be optimized be protected?"}, {"start": 340.78, "end": 343.78, "text": " So that it does not disappear from the population"}, {"start": 344.54, "end": 346.06, "text": " prematurely"}, {"start": 346.06, "end": 350.26, "text": " So what they say here is the following so imagine you have a"}, {"start": 350.26, "end": 355.94, "text": " Imagine you have again a set of population of neural networks and I'm gonna just know them by these"}, {"start": 356.5, "end": 361.34, "text": " simple rectangles just for abstraction sake for for simplicity sake, so"}, {"start": 362.21999999999997, "end": 367.62, "text": " Let's say we have like three neural networks and let's say you mutate one of these so these are just MLPs"}, {"start": 367.62, "end": 375.14, "text": " So this is like neural network one two three and let's say you mutate this one by adding additional node here. Okay, and"}, {"start": 376.3, "end": 379.14, "text": " Now what will happen is if you were to continue"}, {"start": 379.14, "end": 381.14, "text": " comparing this"}, {"start": 381.7, "end": 385.58, "text": " novel like this mutated neural network with the"}, {"start": 386.58, "end": 390.78, "text": " Networks two and three it would be a suboptimal probably because initially"}, {"start": 390.78, "end": 396.38, "text": " This is just randomly initialized or something and then it cannot compete and so what they do how needs solves"}, {"start": 396.38, "end": 403.02, "text": " This is they basically do this speciation process whereby they group similar networks together"}, {"start": 403.02, "end": 409.78, "text": " And then they form niches and then these networks compare between each other, but they don't compare with other"}, {"start": 410.41999999999996, "end": 413.41999999999996, "text": " Global like arbitrary network from from the whole population"}, {"start": 413.41999999999996, "end": 418.7, "text": " So that will be the the solution that need introduces to cope with this problem. So basically speciation"}, {"start": 419.53999999999996, "end": 427.06, "text": " The third question is how can topologies be minimized throughout evolution without the need for a specially contrived fitness function?"}, {"start": 427.38, "end": 429.38, "text": " that measures complexity and"}, {"start": 429.38, "end": 432.74, "text": " I kind of hinted at the solution already here"}, {"start": 432.74, "end": 438.86, "text": " and the solution is to start with the simplest networks possible and then gradually keep adding the complexity and"}, {"start": 439.34, "end": 444.82, "text": " Because they the optimization procedure of need has this this bias this this inherent bias"}, {"start": 445.14, "end": 448.34, "text": " That's why it's going to be looking for simpler architectures"}, {"start": 448.9, "end": 454.9, "text": " In the first place and this aligns very neatly with the with the principle of the OCam's razor"}, {"start": 454.9, "end": 458.94, "text": " Whereby the the simpler the simplest hypothesis the simplest model"}, {"start": 459.46, "end": 461.26, "text": " that performs"}, {"start": 461.26, "end": 463.85999999999996, "text": " Like good enough is probably the best one"}, {"start": 464.85999999999996, "end": 466.29999999999995, "text": " Okay"}, {"start": 466.29999999999995, "end": 470.7, "text": " And the first question will be solved by these historical markings"}, {"start": 470.7, "end": 473.94, "text": " But we're gonna get at that point in a couple of minutes"}, {"start": 474.26, "end": 474.73999999999995, "text": " Okay"}, {"start": 474.73999999999995, "end": 480.38, "text": " Let me first show you how they represent the networks in the background because if you're not familiar with genetic algorithms"}, {"start": 480.38, "end": 485.1, "text": " Did this all all this may be a bit like weird?"}, {"start": 485.1, "end": 487.9, "text": " And so because of that, let me just start here"}, {"start": 487.9, "end": 493.3, "text": " So what they do is for every neural network in the population of neural networks"}, {"start": 493.3, "end": 495.9, "text": " They keep up they keep this genome in the background"}, {"start": 495.9, "end": 502.86, "text": " So also known as genotype and each genotype corresponds one to two one to one to the to the phenotype"}, {"start": 502.86, "end": 508.46, "text": " Corresponding phenotype. So this genotype basically determines this this phenotype this neural network here"}, {"start": 508.46, "end": 510.46, "text": " And this is just a terminology from genetics"}, {"start": 511.09999999999997, "end": 517.34, "text": " So phenotype basically means any observable trait for example in humans that may be like the eye color"}, {"start": 517.34, "end": 525.1, "text": " That means like maybe like blood type whatnot and there is some gene that's going up for that particular phenotype for that observable trait"}, {"start": 525.1, "end": 530.62, "text": " So that's the terminology they are taking here because this is this whole optimization field is roughly"}, {"start": 531.34, "end": 533.74, "text": " loosely inspired by the genetics and and"}, {"start": 534.38, "end": 536.38, "text": " Thus the terminology"}, {"start": 536.38, "end": 543.42, "text": " Okay, so you can see here they have two different lists of of uh, like genes versus the node genes"}, {"start": 543.42, "end": 548.3, "text": " So we have node one through node five corresponding to these nodes here one through five"}, {"start": 548.3, "end": 550.3, "text": " And you can see there are different types of nodes"}, {"start": 550.3, "end": 553.74, "text": " So some of these are sensor nodes, which means input nodes"}, {"start": 553.74, "end": 559.26, "text": " Some of these are output nodes like node four here and then we have the hidden nodes the node five here"}, {"start": 559.26, "end": 567.18, "text": " More interestingly, they have these connections genes and you can see how each of these squares basically describes these connections"}, {"start": 567.18, "end": 573.58, "text": " So let's take this one for example, so you can see here. We have one. Let me just change the color to red here"}, {"start": 573.58, "end": 581.18, "text": " So we have one as the input and then four as the output so that basically specifies this particular connection here"}, {"start": 581.9, "end": 585.5, "text": " You can see the weight is 0.7. You can see that it's enabled"}, {"start": 585.5, "end": 591.66, "text": " I'm going to tell you what that is in a minute and we have this innovation number also known as this historical marker"}, {"start": 591.66, "end": 597.66, "text": " Which is a very important part of this whole algorithm and i'll get into a bit more details a bit later"}, {"start": 598.22, "end": 602.3, "text": " Okay, so this enabled thing so let me contrast that with disabled"}, {"start": 602.86, "end": 606.46, "text": " So we have this connection between two and four and if you take a look"}, {"start": 606.46, "end": 612.38, "text": " There is no connection between two or four because it's disabled and again this terminology comes from the genetics"}, {"start": 612.38, "end": 619.02, "text": " Genes can be expressed or not expressed if a gene is not expressed then basically you don't have the associated phenotype"}, {"start": 619.42, "end": 621.42, "text": " so for example"}, {"start": 621.42, "end": 625.98, "text": " You don't want to so for example if you have you have obviously different cell types in your body"}, {"start": 625.98, "end": 633.18, "text": " You have like skin cells you have like muscle cells you have neurons or neural cells and obviously a muscle cell"}, {"start": 633.5, "end": 639.5, "text": " Doesn't need a certain proteins that the neural that the neural cell needs and thus those are the"}, {"start": 639.5, "end": 644.7, "text": " Neural that the neural cell needs and thus those genes are not expressed in that particular cell"}, {"start": 645.18, "end": 647.18, "text": " So that's the rough"}, {"start": 647.18, "end": 649.5, "text": " Like yeah background in genetics"}, {"start": 650.14, "end": 652.14, "text": " behind all of this terminology"}, {"start": 652.54, "end": 653.5, "text": " so"}, {"start": 653.5, "end": 656.62, "text": " That's that's roughly it. So now that we have this list this list"}, {"start": 657.5, "end": 664.62, "text": " This genotype completely specifies a particular network and then you can kind of mutate these and we'll get to that in a second"}, {"start": 665.9, "end": 667.9, "text": " Okay, so before that let me just"}, {"start": 667.9, "end": 668.9399999999999, "text": " uh"}, {"start": 668.9399999999999, "end": 673.18, "text": " first mention this problem of competing conventions"}, {"start": 674.14, "end": 675.1, "text": " so"}, {"start": 675.1, "end": 677.66, "text": " Let me tell you what this is and why should we care?"}, {"start": 678.9399999999999, "end": 681.74, "text": " You can see two neural networks here on the left and the right"}, {"start": 682.3, "end": 685.5, "text": " And basically these two neural networks have the same function"}, {"start": 686.22, "end": 688.22, "text": " And the reason is you can see here"}, {"start": 688.22, "end": 693.5799999999999, "text": " Basically c is the same as c here b's are the same nodes and a's are the same node"}, {"start": 693.58, "end": 698.5400000000001, "text": " They're just permuted and because we have a sum function here because we as you know"}, {"start": 698.5400000000001, "end": 702.38, "text": " How these neurons work you have a summation here, which is permutation invariant"}, {"start": 702.7, "end": 708.86, "text": " Which means we don't really care about the order of these nodes and because of that the function will be the same and you can"}, {"start": 709.1800000000001, "end": 712.94, "text": " Just kind of think about it and you'll see that what I just said makes sense"}, {"start": 713.1800000000001, "end": 718.3000000000001, "text": " So it doesn't matter like no matter the permutation you'll you'll end up with the same functionality in the neural network"}, {"start": 719.0200000000001, "end": 722.7, "text": " Now why this is problematic for genetic algorithms is the following"}, {"start": 722.7, "end": 729.26, "text": " So if you want to cross these two genomes, so let's say we have genome a b and c and we have c b and a"}, {"start": 729.98, "end": 732.1400000000001, "text": " If you were to do a point wise mutation"}, {"start": 732.22, "end": 737.1, "text": " So that means you'll take a certain gene from let's say we have a b c and we take"}, {"start": 737.74, "end": 742.86, "text": " Instead of c we take the gene a we end up with a b and a if we had a point mutation"}, {"start": 742.86, "end": 749.26, "text": " That's happening in this genome. So if this one was the dominant genome and we were to mutate a into c"}, {"start": 749.26, "end": 751.98, "text": " by randomly taking the gene from this genome instead"}, {"start": 752.3, "end": 757.18, "text": " We end up with c b c now why this is bad is because as you may notice here"}, {"start": 757.18, "end": 761.9, "text": " We just lost one third of the information in from the from the from the original"}, {"start": 762.38, "end": 769.26, "text": " Genotypes and that's obviously undesirable. So we want to be able to recognize and match"}, {"start": 769.74, "end": 771.26, "text": " corresponding genes"}, {"start": 771.26, "end": 777.8199999999999, "text": " Because we don't want to lose them and that's where these historical markings come into play and we'll get to those in a minute"}, {"start": 777.82, "end": 785.4200000000001, "text": " So let me just kind of reiterate when one of these permutations crosses over with another critical information is likely to be lost"}, {"start": 785.4200000000001, "end": 793.82, "text": " For example crossing a b c and c b a can result in c b c a representation that has lost one third of the information that both of the parents had"}, {"start": 793.82, "end": 799.2600000000001, "text": " Okay, so neat basically solves this problem by doing this historical"}, {"start": 801.0200000000001, "end": 803.0200000000001, "text": " Markings stuff"}, {"start": 803.02, "end": 807.1, "text": " Okay, let's continue here and let me show you the mutation procedure"}, {"start": 807.1, "end": 811.42, "text": " And then we're going to slowly build up the whole holistic picture of how this need algorithm works"}, {"start": 811.9, "end": 817.1, "text": " So i'm kind of going bottom up which is contrary to my usual approach of going top to bottom"}, {"start": 817.42, "end": 820.3, "text": " But like in this particular paper, I guess that makes some sense"}, {"start": 821.26, "end": 824.62, "text": " There are two types of mutations we can we can imagine here one is"}, {"start": 825.26, "end": 828.86, "text": " Adding like a connection and the other one is adding a node. So"}, {"start": 828.86, "end": 835.82, "text": " Let's focus on the first one adding connection. You can see here that we add this connection between neurons three between nodes"}, {"start": 836.46, "end": 841.66, "text": " Three and five and you can see that we added so starting from this genotype here"}, {"start": 842.3000000000001, "end": 849.1800000000001, "text": " After we added the connection between three and five with the historical marking seven or innovation number as it's also called"}, {"start": 849.5, "end": 853.34, "text": " So we end up with this novel genome here. We have the other"}, {"start": 854.78, "end": 856.78, "text": " Mutation having a node"}, {"start": 856.78, "end": 864.14, "text": " Um mutation happening here here. Uh, we add the node so you can see here. We add node six which basically"}, {"start": 865.8199999999999, "end": 871.5799999999999, "text": " Like disables this previous connection and that's two novel connections and that's why we have so between three and four"}, {"start": 871.8199999999999, "end": 875.74, "text": " This one will be disabled and you can see that we added from three to six"}, {"start": 875.8199999999999, "end": 878.6999999999999, "text": " So we have this one and we have from six to four"}, {"start": 878.9399999999999, "end": 883.5799999999999, "text": " So we added two novel connections and we have the novel innovation numbers here"}, {"start": 883.58, "end": 886.62, "text": " So this is the way in which um"}, {"start": 887.4200000000001, "end": 888.7800000000001, "text": " basically"}, {"start": 888.7800000000001, "end": 892.86, "text": " Neat adds the additional complexity to the current population"}, {"start": 893.82, "end": 897.58, "text": " So again, retracing the top number in each genome is the innovation number of that gene"}, {"start": 897.98, "end": 904.7, "text": " The innovation numbers are historical markers that identify the original historical ancestor of each gene"}, {"start": 905.1800000000001, "end": 908.46, "text": " New genes are signed new increasingly higher numbers"}, {"start": 908.46, "end": 914.3000000000001, "text": " In case in other instance of a neural network adds the exact same connection. Let's say"}, {"start": 914.7, "end": 916.7, "text": " Uh this connection three to five"}, {"start": 917.1800000000001, "end": 918.0600000000001, "text": " then"}, {"start": 918.0600000000001, "end": 923.82, "text": " They would reuse the this innovation number seven for that particular instance as well"}, {"start": 923.98, "end": 930.3000000000001, "text": " So there would not be like a blow up artificial blow up of these of this historical markings and that's why they they work"}, {"start": 931.34, "end": 932.46, "text": " Okay"}, {"start": 932.46, "end": 936.38, "text": " So that's some background now. Let's dig a bit deeper"}, {"start": 936.38, "end": 940.3, "text": " Um, so they say here i'm just going to skip this part because we already covered it"}, {"start": 940.46, "end": 947.66, "text": " So in the future whenever these genomes meet the offspring will inherit the same innovation numbers on each gene"}, {"start": 948.12, "end": 950.12, "text": " Innovation numbers are never changed"}, {"start": 950.54, "end": 956.3, "text": " Okay, they are never changed thus the historical origin of every gene in the system is known throughout evolution"}, {"start": 956.38, "end": 957.02, "text": " Okay"}, {"start": 957.02, "end": 962.38, "text": " So when crossing over the genes in both genomes with the same innovation numbers are lined up"}, {"start": 962.38, "end": 967.58, "text": " So we line them up we're going to see an image in a second and these genes are called matching genes"}, {"start": 967.58, "end": 972.38, "text": " So we have the matching genes genes that do not match are either disjoint or excess"}, {"start": 973.02, "end": 978.78, "text": " Depending on whether they occur within or outside the range of other parents innovation numbers"}, {"start": 979.34, "end": 983.9, "text": " In composing the offspring genes are randomly chosen from either parent and matching genes"}, {"start": 984.22, "end": 991.5, "text": " Whereas all excess or disjoint genes are always included from the more fit parent. So that's an important detail here"}, {"start": 991.5, "end": 992.94, "text": " Okay"}, {"start": 992.94, "end": 995.02, "text": " So let's see all of that pictorially here"}, {"start": 995.9, "end": 1001.26, "text": " Let's assume we have two different topologies from the same population from the same subpopulation"}, {"start": 1001.74, "end": 1009.18, "text": " Same species if you want, although they sometimes do interspecies and intra species. They do both intra and interspecies"}, {"start": 1010.3, "end": 1015.74, "text": " Crossing but here so you can see two genomes and what they do. Let me just kind of zoom in a bit"}, {"start": 1016.14, "end": 1018.14, "text": " They align these two genomes"}, {"start": 1018.68, "end": 1020.38, "text": " according to these"}, {"start": 1020.38, "end": 1025.26, "text": " Like innovation numbers so you can see one one two two three three four four five five"}, {"start": 1025.34, "end": 1030.78, "text": " All of these are aligned and then you have the disjoint ones because six and seven from this one does not exist"}, {"start": 1031.18, "end": 1036.06, "text": " In this genotype and then we have eight being disjoint and finally we have these excess genes"}, {"start": 1036.3, "end": 1038.94, "text": " Because they are out of the range of the parent one"}, {"start": 1039.5, "end": 1040.7, "text": " Okay"}, {"start": 1040.7, "end": 1047.74, "text": " So now how the crossing works is you basically randomly take gene from either parent one or parent two"}, {"start": 1047.74, "end": 1050.86, "text": " Uh when it comes to these matched genes, so you can see here"}, {"start": 1050.94, "end": 1055.58, "text": " This is kind of gray, which means we took that one from the parent one then this is uh"}, {"start": 1056.3, "end": 1060.7, "text": " Okay darker gray, which is maybe from either of the parents and this is uh,"}, {"start": 1061.1, "end": 1066.14, "text": " White-ish which means we took it from here then we took it from here and finally we took it from here"}, {"start": 1066.3, "end": 1069.74, "text": " So that means we are randomly taking genes from from either parent"}, {"start": 1070.6200000000001, "end": 1075.02, "text": " Finally, we take the the genes from the more fit parent and because in this particular case"}, {"start": 1075.02, "end": 1081.34, "text": " They kind of have equal fitness both of these they they kind of end up taking all of the genes and we end up with the offspring"}, {"start": 1081.8799999999999, "end": 1084.24, "text": " Genotype here and you can see the corresponding"}, {"start": 1085.32, "end": 1087.32, "text": " phenotype exactly here"}, {"start": 1087.98, "end": 1089.34, "text": " Okay"}, {"start": 1089.34, "end": 1091.34, "text": " So that's cool now"}, {"start": 1091.42, "end": 1094.94, "text": " We can slowly start and build up the whole picture"}, {"start": 1095.98, "end": 1102.06, "text": " Let me first read a couple more sentences and then i'm gonna kind of draw a diagram explaining the whole the big picture"}, {"start": 1102.06, "end": 1109.34, "text": " Okay. So again retreating in this case equal fitnesses are assumed. So the disjoint and excess genes are also inherited randomly"}, {"start": 1110.46, "end": 1113.1799999999998, "text": " so the reason I kind of highlighted this is to show that"}, {"start": 1113.82, "end": 1120.3, "text": " one of the the cons of this approach is that it's super complicated compared to gradient-based methods such as sgd"}, {"start": 1120.78, "end": 1124.94, "text": " Where it's quite straightforward and uh, there is not a lot of hyper parameters"}, {"start": 1125.1799999999998, "end": 1131.26, "text": " Whereas here in need there is a lot of things you have to kind of tune the population size how to speciate how to set"}, {"start": 1131.26, "end": 1132.94, "text": " The thresholds we'll see that in a second"}, {"start": 1132.94, "end": 1138.3, "text": " But it's there's a much more details to to think about compared to gradient-based optimizations"}, {"start": 1139.02, "end": 1140.22, "text": " so"}, {"start": 1140.22, "end": 1144.22, "text": " For example, the disabled genes may become enabled again in future generations"}, {"start": 1144.3, "end": 1147.34, "text": " So that means some of these may be randomly enabled again"}, {"start": 1148.06, "end": 1154.46, "text": " Also, there's a preset chance that an inherited gene is disabled if it is disabled in either parent"}, {"start": 1155.02, "end": 1157.34, "text": " So that's another detail to think about okay"}, {"start": 1157.34, "end": 1160.62, "text": " Now as I mentioned these mutations will create suboptimal"}, {"start": 1161.1799999999998, "end": 1163.1799999999998, "text": " neural networks"}, {"start": 1163.1799999999998, "end": 1167.98, "text": " After the the actual mutation happens and before the optimization of that neural network happens"}, {"start": 1167.98, "end": 1169.98, "text": " There's going to be a suboptimal architecture"}, {"start": 1169.98, "end": 1174.86, "text": " So how do we make sure that the innovations survive and the answer is here?"}, {"start": 1175.6599999999999, "end": 1181.02, "text": " By adding new genes to the population and sensibly meeting genomes representing different structures"}, {"start": 1181.02, "end": 1183.98, "text": " The systems can form a population of diverse topologies"}, {"start": 1183.98, "end": 1190.94, "text": " However, it turns out that such a population on its own cannot maintain topological innovation and that's quite important"}, {"start": 1191.82, "end": 1193.34, "text": " to maintain"}, {"start": 1193.34, "end": 1201.1, "text": " Because smaller structures optimize faster than larger structures and adding nodes and connections usually initially decreases the fitness of the network"}, {"start": 1201.58, "end": 1205.42, "text": " Recently augmented structures have little hope of surviving more than one generation"}, {"start": 1205.42, "end": 1211.18, "text": " Even though the innovations they represent may be crucial towards solving the task in the long run"}, {"start": 1211.18, "end": 1216.54, "text": " The solution is to protect innovation by speciating the population as explained in the next section"}, {"start": 1216.54, "end": 1218.54, "text": " And this is the most important part of the paper"}, {"start": 1219.26, "end": 1223.98, "text": " Probably, I mean it's one of the most important details. So let's dig a bit deeper"}, {"start": 1223.98, "end": 1234.54, "text": " So let's see how they define how do they discriminate between how do they separate a special neural a new neural network a new offspring into into a species"}, {"start": 1234.54, "end": 1237.74, "text": " How do they assign a species to that particular neural network?"}, {"start": 1237.74, "end": 1238.8600000000001, "text": " And we can see it here"}, {"start": 1238.86, "end": 1246.3799999999999, "text": " So the number of excess and disjoint genes between a pair of genomes is a natural measure of their compatibility distance"}, {"start": 1246.3799999999999, "end": 1252.78, "text": " The more disjoint two genomes are the less evolutionary history they share and thus the less compatible they are"}, {"start": 1253.26, "end": 1262.2199999999998, "text": " Therefore we can measure the compatibility distance delta of different structures in need as a simple linear combination of the number of excess and disjoint genes"}, {"start": 1262.22, "end": 1269.02, "text": " As well as the average weight differences of matching genes including disabled genes"}, {"start": 1269.02, "end": 1279.58, "text": " So you can see a simpler a very simple way to determine how different how incompatible to or compatible to genotypes are"}, {"start": 1279.58, "end": 1288.78, "text": " So you can see the more of excess genes we have between two genotypes and or the more disjoint genes we have"}, {"start": 1288.78, "end": 1303.66, "text": " Or even if we have matching like genes if the actual weights of those connections are quite different than depending on c3 and this variable here this delta can explode"}, {"start": 1303.66, "end": 1311.8999999999999, "text": " So once we have this once we have this way of measuring compatibility we can just they just set a threshold"}, {"start": 1311.8999999999999, "end": 1317.5, "text": " So the distance measure delta allows us to speciate using a compatibility threshold delta t"}, {"start": 1317.5, "end": 1320.86, "text": " And that's how you basically speciate"}, {"start": 1320.86, "end": 1332.06, "text": " So continuing on a given genome g in the current generation is placed in the first species in which g is compatible with the representative genome of that species"}, {"start": 1332.06, "end": 1339.26, "text": " If g is not compatible with any existing species a new species is created with g as its representative"}, {"start": 1339.26, "end": 1345.02, "text": " Okay now it's a good time to draw some diagram and explain what's going on here"}, {"start": 1345.02, "end": 1352.94, "text": " So imagine we have multiple subpopulations so let's imagine we have multiple species so here is a species one"}, {"start": 1352.94, "end": 1359.34, "text": " Then we have some bit bigger species we have another species here and so what happens is the following"}, {"start": 1359.34, "end": 1370.06, "text": " Now these are the most like these are the fittest individuals from the last generation and I'm going to explain how do we determine fitness and how do we prune based on fitness a bit later"}, {"start": 1370.06, "end": 1375.74, "text": " But for now just assume all of these subpopulations are left with the fittest individuals"}, {"start": 1375.74, "end": 1388.06, "text": " Now what you do is you do some basically crossing so you'll take two parents here and you cross those two and you end up with another with the offspring"}, {"start": 1388.06, "end": 1397.82, "text": " And so this offspring now needs to be compared with representative genomes in order to determine which species it belongs to"}, {"start": 1397.82, "end": 1405.4199999999998, "text": " So even though it originates from this species it now because of these mutations and because of the crossing of the genes from the parents"}, {"start": 1405.4199999999998, "end": 1414.1399999999999, "text": " It may end up being a different species altogether which does not make a lot of sense when it comes to this like discussing I guess biological creatures"}, {"start": 1414.1399999999999, "end": 1422.1399999999999, "text": " At least not the vertebrates but yeah so let me denote that like this so let's let me just do this"}, {"start": 1422.14, "end": 1434.3000000000002, "text": " So basically what I do is you randomly pick a genotype from this population and that's going to be G and you do the same thing here just randomly pick one and then you do the same thing here and for every single subpopulation"}, {"start": 1434.3000000000002, "end": 1446.3000000000002, "text": " And now what you do is the following so you take the freshly created offspring here and you calculate the compatibility measure so this thing here"}, {"start": 1446.3, "end": 1456.86, "text": " So you can basically you'll basically end up with a couple of numbers you'll have some some delta here you'll have and you'll see whether this delta is below the threshold"}, {"start": 1456.86, "end": 1463.74, "text": " If it's below the threshold that means that we need to assign this particular offspring to this species"}, {"start": 1463.74, "end": 1473.74, "text": " So what I do they have some canonical ordering of these subpopulations so that means maybe maybe this one's going to be like subpopulation one then two then three"}, {"start": 1473.74, "end": 1483.66, "text": " And the first subpopulation where the compatibility is lower than the threshold they just kind of allocate they just kind of assign that offspring to that subspecies"}, {"start": 1483.66, "end": 1497.1, "text": " So for example these two were not compatible if this G the representative genome from this subpopulation was not compatible with the offspring then we would continue with with the representative G from the second subpopulation"}, {"start": 1497.1, "end": 1511.26, "text": " Which is in this particular case the same species from which this offspring originates from so now if the compatibility was lower than threshold with would kind of assign again the offspring to this subpopulation so that's the rough idea"}, {"start": 1511.26, "end": 1527.02, "text": " So after this crossing happens I guess what happens next is just some random mutations and then they assert the fitness of all of the individuals of individual genotypes genomes in the whole population"}, {"start": 1527.02, "end": 1541.74, "text": " Let's see how the fitness is determined so fitness is basically depends on the particular task at hand so depends what you're trying to solve with need so fitness will be very very domain specific basically"}, {"start": 1541.74, "end": 1554.06, "text": " The important detail is that they use something called explicit fitness sharing which means they do this and that means that so not only do you care about the particular individual"}, {"start": 1554.06, "end": 1571.74, "text": " You also care how big is the species that that individual belongs to and that's denoted like algebraically by this formula so basically summation from one to through n where n is the whole population size so including all the species"}, {"start": 1571.74, "end": 1590.6200000000001, "text": " And then we have this sh function which is basically set to one when the this compatibility threshold is below below the this compatibility measure is below the threshold which basically means hey this is going to be the size of the species that this individual belongs to"}, {"start": 1590.62, "end": 1612.54, "text": " So that's a long long story short so because of that even if you have very very fit individuals if the species it belongs to is very big the this adapted I think is adjusted fitness is going to be lower so that means some other less fit individuals from smaller subpopulations have the chance of surviving to the next generation"}, {"start": 1612.54, "end": 1629.98, "text": " Let me just read you a couple of more sentences here so they say every species is assigned a potentially different number of offspring in proportion to the sum of adjusted fitness is of its member organisms species then reproduce by first eliminating the lowest performing members from the population"}, {"start": 1629.98, "end": 1650.6200000000001, "text": " The entire population is then replaced by the offspring of the remaining organisms in each species okay let me recap what I think is going on here so the bad thing about the paper is that they don't have like a like a pseudo algorithm specifying the steps in the exact order so I kind of have to infer what's going on"}, {"start": 1650.62, "end": 1668.54, "text": " without digging into the actual software packages which are as I said quite complex compared to just your regular back back grading based optimizations so as I said let's let's assume we have these subpopulations here and then we determine the fitness of each of the individuals"}, {"start": 1668.54, "end": 1694.78, "text": " and then basically we're going to prune the less fit individuals in each of these subpopulations so we'll end up with some subsets of each of these subpopulations okay and now depending on the size of those like subsets each of these species will have a certain number of offsprings they can generate"}, {"start": 1694.78, "end": 1712.7, "text": " so that means now we'll take the parents we'll do the crossing we'll have an offspring and then we'll just kind of alloc assign it to your species depending on the as I previously discussed on this compatibility measure and we rinse and repeat for all of the subpopulations that same algorithm"}, {"start": 1712.7, "end": 1741.42, "text": " after we do that I guess what happens is inside of the before you start evaluating them and trying to figure out the fitness of these novel individuals you do some mutations so adding connections adding notes and then only then do you evaluate the fitness and then the circle repeats you prune out the weakest individuals the ones with the lowest fitness value and rinse and repeat and rinse"}, {"start": 1741.42, "end": 1760.38, "text": " and then you rinse and repeat okay final detail worth mentioning is that so as discussed in section 2.4 blah blah blah so this just means topology and weight evolution artificial neural networks so basically evolving both the topology and the weights and not just the weights as we are used to"}, {"start": 1760.38, "end": 1786.38, "text": " so these twins if that's the way you pronounce this typically start with an initial population of random topologies in order to introduce diversity from the outset so that's how these other approaches do it in contrast neat biases the search towards minimal dimensional spaces by starting out with a uniform population of networks with zero hidden nodes and we saw that in the beginning of video but I thought worth mentioning that"}, {"start": 1786.38, "end": 1816.3000000000002, "text": " okay so that's pretty much it that's neat they then showed some results on a couple of tasks one of those tasks is this XOR so your your logical gate using all over computer science and they show that they can basically find a topology that can perform the XOR function for that you need to have at least one hidden node and you can see here so basically this is the initial individual of the of the"}, {"start": 1816.3, "end": 1846.22, "text": " population and then after applying meet they end up with this phenotype with this individual they can solve the XOR problem you can see it had to add some novel nodes you see a novel note here you can see novel connections here and basically the weights which you can see on this on this diagram are also changed so that this performs the XOR function okay so hopefully you like the idea behind the neat paper"}, {"start": 1846.22, "end": 1876.14, "text": " I think it's very cool because it's inspired by evolution and it has this progressive building of build up of complexity and you're trying to find the topologies you're trying to at the same time tweak those weights and find the simplest individual that can solve the task that you care about now the the con side about this whole approach as you can see it's quite intricate there's a lot of details you need to care about and all of that makes it a bit less attractive"}, {"start": 1876.14, "end": 1887.98, "text": " and since this paper was published in two thousand two we haven't seen we really haven't seen the push towards this research direction but nonetheless I think it's a very valuable"}, {"start": 1887.98, "end": 1890.46, "text": " like idea to keep in your mind"}, {"start": 1890.46, "end": 1899.38, "text": " okay next up let me walk you through the compositional pattern producing networks okay so on to compositional pattern producing networks"}, {"start": 1899.38, "end": 1919.94, "text": " a novel abstraction of development paper and before we dig into CPPN's deeper let me give you another example of a very popular like model of development with which you may be familiar with already and that's the cellular automata models so let me open up this very cool distilled pop"}, {"start": 1919.94, "end": 1940.3400000000001, "text": " and let me just kind of slow this down so that you can see what's going on so you can see here that through local interactions so each of the cell is communicating only with the neighboring cells and via a couple of simple rules and in this case the rules are learned and hence this is called neural cellular automata"}, {"start": 1940.34, "end": 1964.58, "text": " you can see that this phenotype this body plan this morphology albeit a 2D one is built up and this could easily be generalizable to 3D space and thus to the space where we live in and we could be building like real 3D bodies using cellular automata so this is a model of development as well so you can see"}, {"start": 1964.58, "end": 1994.34, "text": " you can imagine starting from a zygote from a single cell and then through some type of communication local communication that's very important you end up with this particular morphology so now what CPPN show is that you don't need to have this local communication going on and temporal unfolding and that's just like a consequence of the fact that we live in a physical world with physics where the laws of physics"}, {"start": 1994.34, "end": 2021.06, "text": " are at play and this constrains the developmental process to do it like this so let me now go back to CPPN and let's see how they actually approach this let's start by reading the abstract a little bit natural DNA can encode complexity on an enormous scale researchers are attempting to achieve the same representational efficiency in computers by implementing developmental encodings"}, {"start": 2021.06, "end": 2040.1, "text": " ie encodings that map the genotype to the phenotype through a process of growth from a small starting point to mature form a major challenge in this effort is to find the right level of abstraction of biological development to capture its essential properties without introducing unnecessary inefficiencies"}, {"start": 2040.1, "end": 2068.3399999999997, "text": " okay so the rest of the paper will show how they found a different model how can a Stanley found a different model to for this developmental process so basically the main contribution of the paper is to establish that CPPN are legitimate abstraction of natural developmental encoding which may not be super obvious on the first glance of this paper so let's start here so"}, {"start": 2068.34, "end": 2095.2200000000003, "text": " what like the example here shows that you can have basically this phenotype being generated by this function F instead of having so basically instead of having local interactions are having this temporal unfolding to get the final to the morphology in this case the morphology is just a triangle so this is not like a biological like morphology but nonetheless you can just kind of abstract it away"}, {"start": 2095.22, "end": 2125.14, "text": " and let's deal with mathematical objects into the space so it's the same thing so F is a developmental model of this of this triangle if you will okay so so basically they say here that a developmental chronology is only one way of producing a particular constellation of particles it follows that encoding and unfolding process may be unnecessary to produce complex phenotypes because a functional description could alternatively have"}, {"start": 2125.14, "end": 2155.06, "text": " been evolved such description would not necessitate a long unfolding chain of interactions and productions so the reasoning is why go through why simulate every single intermediate step with what when what we care about is the actual like phenotype and if you could catch capture the whole development inside of a function why not do just that so they state here that so looking at this diagram here so this observation implies"}, {"start": 2155.06, "end": 2184.98, "text": " that any phenotype produced through a temporal progression is also possible to represent through a functional description so in fact this paper from I think 1989 show that any function can be approximated by neural network with two hidden layers that's the universal approximation theorem and the more neurons in networks to the wider network the more accurate the approximation can be that's any morphology when viewed as a distribution of particle in space is possible to represent as a function without the notion of time"}, {"start": 2184.98, "end": 2214.98, "text": " so that's the thing they're trying to kind of skip over here and just kind of understanding that that's a more of a physical constraint and something we need to care about when we're trying to develop mathematical models such as this one okay let's let's see this sentence a significant function and early stage of development in natural embryo Jenny is to define a coordinate frame i.e. a set of virtual coordinate axes upon which future stages of development will be"}, {"start": 2214.98, "end": 2244.9, "text": " based the simplest and most basic of these coordinates frames are the main axis of the body which are defined at the very beginning of development inside the egg itself these axes include the anterior posterior axis i.e. head to feet and the doors or ventral i.e. back to front so what are what they are basically saying here is the following so so the gist of this is that during the development we have to somehow form this intricate patterns"}, {"start": 2244.9, "end": 2265.9, "text": " and those are usually just chemical gradients and if you if you if you manage to form those chemical gradients then the cells then each cell depending on where it is located in depend on this and this and this chemical gradient map will know what to do so we'll know what exactly to do depending on the on the on that scalar of the of the chemical gradient"}, {"start": 2265.9, "end": 2295.86, "text": " so if you are able to capture the pattern of this chemical gradient without even having the local interactions or the temporal unfolding then we can capture the development itself and you can see that because of this left to right gradient which is in the form of a Gaussian function this this if this basically implies that we'll have will end up with a bilateral symmetry and you can see that this fly here has a symmetry bilateral symmetry so if I were to draw a vertical axis"}, {"start": 2295.86, "end": 2325.82, "text": " through this fly here you can notice that we have a symmetry here can just flip it and nothing would change the underlying structure which is in this case that the fly the to the image of a fly would not change and similarly there is a gradient along this anterior posterior axis and different patterns along along those those along the axis produce different cells so basically you can ignore all of this and you can imagine so you can ignore"}, {"start": 2325.82, "end": 2347.82, "text": " all of this and you can imagine we have a certain like just draw this so we have a certain to the spatial pattern here so it will be hard to draw but you can imagine going from so around this axis here it's going to be quite symmetric left and right and that's so basically this to the spatial signal is going to directly in code those chemical"}, {"start": 2347.82, "end": 2373.82, "text": " gradients and that's gonna basically allow us to to to form this this this this morphology here and that means we can ignore we can just focus on trying to generate these intricate to the spatial patterns okay so now let's see how do we generate these to the spatial signals which are going to loosely represent these chemical gradients and that's gonna be a blueprint for how to generate the morphology"}, {"start": 2373.82, "end": 2395.82, "text": " like the body of some biological organism or or whatnot so because we're trying to remember we're trying to build a developmental model for biological organisms so so here's one way we could be composing functions so here we have a symmetric function here we have a periodic function you can see we can generate arbitrary"}, {"start": 2395.82, "end": 2424.82, "text": " patterns by doing this they mentioned here that coordinate frames created through a developmental process interact with each other to produce complex patterns with regularities in the same way functionally represented frames can be composed to create complex regularities so in this way and this has been mentioned over and over again throughout the paper so the composition the function composition replaces local interactions okay"}, {"start": 2424.82, "end": 2449.82, "text": " so instead of having some some local cellular automata like communication we can just compose the the the various functions to end up with these to the spatial signals we we care about I mean I'm saying to the but those could be 3d or or even 40 as we'll later see and it's just a pattern we're trying to to to generate so here is the"}, {"start": 2449.82, "end": 2478.82, "text": " how cppn's look like and they say that the main idea is that the order in which functions are composited is an abstraction for the chronology of events over the course of development without the need for simulating such events locally so in a way signal flowing from from here to here is is an abstraction for the chronology of time so even though we don't have any notion of time in this network per se we are kind of capturing the time"}, {"start": 2478.82, "end": 2501.82, "text": " and all of these local interactions by doing this functional compositing so starting from X and Y which are just the coordinate coordinates of your of your Cartesian plane we can generate the output the phenotype by by by composing functions and here compared to your regular artificial neural networks what cppn's do is instead of like just using rally or sigmoid for the activation function they use arbitrary like functions which are"}, {"start": 2501.82, "end": 2520.82, "text": " which have some nice properties so it's either like a Gaussian or some symmetric function or like identity function or a periodic function etc etc so this is what how cppn's look like okay they mentioned here that providing the initial coordinate axis as inputs to the graph is what allows local interaction to be eliminated in physical space there are no intrinsic coordinates that are"}, {"start": 2520.82, "end": 2539.82, "text": " individual cell can access to determine its location and hence its identity therefore local interaction becomes a way of asking where am i that is through the collective negotiation for Jason cells that interact with each other it is possible to derive a coordinate frame however by composing functions and"}, {"start": 2539.82, "end": 2558.82, "text": " that take as arguments and absolute frame of reference the need for such negotiation is eliminated and all identities and relative locations can be determined completely independently so basically what they said here is we can kind of feed these absolute coordinates into the"}, {"start": 2558.82, "end": 2584.82, "text": " cppn to generate this this output pattern and instead you can imagine the difficulty that a cell has like it needs to figure out where it is based on the local communication with the with the neighboring cells and this this this cppn model basically replaces a little bit of"}, {"start": 2584.82, "end": 2603.82, "text": " cppn model basically replaces eliminates the need for for that type of communication to happen so as I mentioned there is a lot of similarity between like neural networks your regular neural networks and cppn's and they say here interesting a graph of such compositions is very similar to an artificial neural"}, {"start": 2603.82, "end": 2618.82, "text": " network with arbitrary topology the only difference between the two is that artificial neural networks generally use sigmoid functions and sometimes gossians or relius or whatnot as activation functions in each note whereas the function composition graph may use any of a variety of"}, {"start": 2618.82, "end": 2635.82, "text": " biological functions at each note as I previously mentioned they then say that the analogy between a function composition graph and a neural network is so strong in fact that is stamping to equate the two however while from an external objective standpoint they are closely related"}, {"start": 2635.82, "end": 2657.82, "text": " so from the mathematical standpoint I guess using the term artificial neural network would be misleading in the context of this discussion because neural networks were so named in order to establish a metaphor with a different biological phenomena and that's the brain and the terminology should avoid making the implication that biological thinking brains are in fact the same as developing embryos"}, {"start": 2657.82, "end": 2686.82, "text": " this is kind of loose because in one of their follow up papers in one of Kenneth Stanley's follow up papers called a hyper neat he shows that you can basically use cppn's to model neural networks by just modeling for the spatial signals you can map that to neural networks so which means that in the fact this can be a model of a brain as well so these are very abstract objects cppn's are very abstract and they are very abstract"}, {"start": 2686.82, "end": 2710.82, "text": " and they can capture arbitrary spatial patterns which can be mapped to various things so they can be mapped to like chemical gradients fields which then can be used as a guide for formulating morphology like the body of an organism or it can be just a like a plan for how to construct construct the actual brain the architecture the design of a"}, {"start": 2710.82, "end": 2730.82, "text": " of a of a neural network okay so let me recap what what we've seen so far it's a bit harder to follow along because there is a lot of text and not that many images so yeah stick with me basically the idea is the following so if you want to produce a certain morphology beat the 2d body like in this case or a 3d body"}, {"start": 2730.82, "end": 2749.82, "text": " all you want to do is be able to specify arbitrarily complex spatial signals so that means you want to have certain properties like you want to be able for your your system to generate symmetric patterns you want to be able to generate imperfect symmetry you want to be able to"}, {"start": 2749.82, "end": 2770.82, "text": " basically a model a repetitiveness etc etc and once you have that spatial signal you can imagine you can you can basically treat that as a as an abstraction for actual physical processes such as chemical gradients which is cell uses to communicate and build up the body so if you can get to the spatial signal"}, {"start": 2770.82, "end": 2799.82, "text": " then you're basically you've solved the task and you've successfully modeled the developmental process and so how we can do that that's what the cpn paper shows is by just composing these arbitrary not arbitrary these special functions such as gaussians symmetric functions periodic functions etc and you can generate those those patterns by doing this we basically skip through the whole local communication temporal unfolding thingies"}, {"start": 2799.82, "end": 2828.82, "text": " that are going on and we just end up with a final plan with the final map that's eventually going to build up the phenotype okay so now for the fun part let me show you what I've done they basically used and that's why I cut where I covered neat so they basically is need to evolve cpn such that we can produce very complex patterns with all of the necessary properties that showcase that this is indeed a good model of development"}, {"start": 2828.82, "end": 2858.82, "text": " and now we're going to show you a couple things so here is the experiments they've done so various people created these platforms so you on the left you can see this Nelphy neat platform on the right you can see this sharp neat platform and basically what you can see here is the following so this is a phenotype so basically this this this chemical gradient map that was created by a cpn in the background so each of these images is"}, {"start": 2858.82, "end": 2888.78, "text": " you can see are these 2d spatial signals which we can interpret as I said multiple times chemical gradients and each of these are in the background created by a particular cpn and the same thing on the right and so what you do here is using neat and using people to select the parents we can we can evolve more complex and more complex spatial signals so what that means is the following so they said this particular pattern is going to have a cpn"}, {"start": 2888.78, "end": 2918.7400000000002, "text": " in the background so it's going to be some cpn number one this is going to be cpn number two so somebody for user takes these two and we match the genes and we do the crossing and then we do all the mutations etc etc we're going to end up with a novel cpn which means that in turn we're going to end up with a novel pattern and now because humans are in the loop here they can select interesting patterns and thus across breed interesting patterns to create even more complex patterns and if you do that you end up with very"}, {"start": 2918.74, "end": 2947.74, "text": " school parents and let me show you some of those by the way just a slight detail so aside from x and y what they additionally input is this signal d which is just your your your distance from the center of your domain here and this could be in theory learned by the cpn by just composing some some functions there but like this makes it a bit easier this is just a kind of a shortcut the biases this cpn towards being"}, {"start": 2947.74, "end": 2961.74, "text": " i guess radially symmetric i think they mentioned somewhere so however since the is radially symmetric it does not automatically provide a bilaterally symmetric coordinate frame okay so the is biasing the cpn towards radial symmetry"}, {"start": 2961.74, "end": 2988.74, "text": " let's see some results so you can see that people manage to generate symmetric patterns such as this one which is a very important finding because as we saw with the fly example when you have this bullet bilateral symmetry pattern then that means you can form by let bilaterally symmetric bodies and this is the corresponding cpn"}, {"start": 2988.74, "end": 3013.74, "text": " that is generating this particular pattern they also showed that they can evolve quite intricate patterns so you can see here the idea is to create a spaceship and again people were just playing taking certain parents certain cpns across breeding them and mutating them and we end up with this sequence so this is"}, {"start": 3013.74, "end": 3036.74, "text": " these are like this is like maybe generation number one and then basically we are evolving with each generation you have more and more intricate patterns and you can see what happens is that we're kind of elaborating on certain details whereas this overarching pattern this this bilateral symmetry is preserved"}, {"start": 3036.74, "end": 3058.74, "text": " throughout this whole sequence all the way to the end where we have these all this looks more like mental rate and then like a spaceship maybe this looks like an airplane but in all case in any case you can see that we can generate very very complex patterns with all of the necessary properties using cpns"}, {"start": 3058.74, "end": 3079.74, "text": " important thing is to to be able to represent not just perfect symmetry but also imperfect symmetry because for example take human body as an example so your heart is not perfectly symmetric so your heart is moved a bit to the left instead of being centrally positioned so that's a very good example of imperfect symmetry"}, {"start": 3079.74, "end": 3105.74, "text": " in our bodies so we want to be able to represent that in our in our in these signals so here they show that aside from having perfectly symmetric sunglasses pattern that somebody produced we can have also this this this imperfect symmetry where you can see that this part is of different size compared to the to this left"}, {"start": 3105.74, "end": 3128.74, "text": " I guess part of the signal so that's another important argument for the expressivity of the cpns now again repetition is something that's super important and repetition with variation is also important so similarly to how it's important to have imperfect symmetry and not just"}, {"start": 3128.74, "end": 3147.74, "text": " perfect symmetry so we will also want to have some variations in the repetition not just perfect repetition so here they show that if you input these additional these special signals like sign sign of 10x and sign of 10y and then the d which is the distance from the center if you input these signals we generate"}, {"start": 3147.74, "end": 3176.74, "text": " very complex patterns and now you may think to yourself now this is cheating because why would you input sign so it's instead of just your regular x and y coordinates and the thing is this is just kind of convenience because cpns could in theory learn without any problem to combine because they do have signs at their disposal when composing the cpns itself so they could learn the same thing this is just for convenience and you can see amazing patterns popping up"}, {"start": 3176.74, "end": 3202.74, "text": " here so here you can see there is a lot of repetition obviously but there is some variation as well so if we were to zoom in into this region then you get this one here and you can see that obviously that this kernel here is is different from from this one here and yet yeah like a bunch of images further testify that this is the case"}, {"start": 3202.74, "end": 3231.74, "text": " yeah going forward you can see that in some cases that the cpn learns to ignore those sinusoids and focuses more on the d signal either distance from the center of the image and then you end up with these very intricate patterns which are much more radio symmetric compared to the previous ones and they indeed they showcase that that's not like a cherry picked example a lot of times the cpns end up with these signals that have all of these nice patterns"}, {"start": 3231.74, "end": 3260.74, "text": " that have all of these nice properties so that's pretty much it they mention finally this is an important sentence so the importance of local interaction to developmental abstraction is an open question they basically show that cpns are an interesting alternative to cellular automata or other models of developmental biology now I did briefly mention that even though they are using cpns as a as a developmental"}, {"start": 3260.74, "end": 3286.74, "text": " model they can also use it to just model various neural network architectures and let me show you how that could be done like a simple interpretation of these spatial signals that are generated by by by cpns so if you if I were to take this simple cpn let me just find the diagram so this one here now let's imagine that instead of feeding in the signal deep let's imagine we feed in x1"}, {"start": 3286.74, "end": 3315.74, "text": " y1 and x2 y2 and then we somehow learn cpn so that the outputs this output scalar is has such prop like the similar properties to what we've seen in 2d signals so being symmetric being being repetitive etc etc now if we were to constrain the the range of these signals to be from 0 to 1 this is basically a signal defined"}, {"start": 3315.74, "end": 3337.74, "text": " on on a 4d hypercube and what's now interesting is how you can interpret this so you can interpret it the following way so imagine we have a grid imagine we have a grid like this and so let me just draw the vertical lines and the horizontal lines and let's now imagine you input the coordinate"}, {"start": 3337.74, "end": 3364.74, "text": " so this is x1 y1 and this is x2 y2 and you plug in these numbers so this is going to be for example 0 0 this is going to be maybe 0 and this is going to be 0.2 because like basically what I've done is I've normalized the the the length of this grid to be so this is where 0 is this is 1 and similarly here"}, {"start": 3364.74, "end": 3392.74, "text": " so we have 0 being here and 1 being here and then we just take the coordinates and you get output and you get some number as the output and you can interpret that as a as a as a weight of the connection between these two cells and that means you can now build neural networks that have symmetric connections that have repetitive connections etc etc"}, {"start": 3392.74, "end": 3412.74, "text": " by just finding appropriate cpp ends so that's the whole idea behind the hyper need paper that's a follow-up work after that came after this paper so again let's imagine this is maybe output 0.7 for these particular coordinates so that means this is going to be of weight 0.7 and then you just start"}, {"start": 3412.74, "end": 3434.74, "text": " tracing you just do an extensive search you basically input all the possible combinations here and for example you set a certain threshold so if a certain weight is below I don't know like maybe 0.3 then there is no connection there otherwise you have a connection with the given weight and that's how you form a neural network by using a cppn"}, {"start": 3434.74, "end": 3455.74, "text": " so why this is very cool is because you can use a much smaller model so this cppn may have like hundreds or thousands of nodes and you may end up with like millions or even billions of connections in your in your neural networks this is like basically a low dimensional representation"}, {"start": 3455.74, "end": 3475.74, "text": " like the gist of your of your phenotype which is in this particular case a neural network cool hopefully you found some interesting ideas in these two papers if you did consider subscribing share the video out and join the discord community as well and until next time bye bye"}, {"start": 3485.74, "end": 3488.74, "text": " you"}]