11 ms·
The quest to evolve neural networks through evolutionary algorithms
- wei_jok 9y agoFor those new to the subject, here is a nice visual primer to Evolution Strategies. http://blog.otoro.net/2017/10/29/visual-evolution-strategies/ http://blog.otoro.net/2017/10/29/visual-evolution-strategies...
- xoroshiro 9y agoThanks for that. My undergrad was Industrial Engineering but I always loved the Operations Research stuff (which I'm hoping will lead me to more CS-y stuff if I can get a job or a Masters or something). All that OR with LPs and MIPs was a headache and but somehow Stochastic programming, GAs and NNs were scary and I never even tried to understand them. I always thought people describing them as simple were probably geniuses or something. Maybe one day I'll understand the second half of that link.
- deleted 9y ago[deleted]
- rdlecler1 9y agoI spent more than 10 years working on this problem. One major challenge is how to represent the genotype-phenotype map so that genetic variation leads to favorable phenotypic changes. For this you start going down a rabbit hole of developmental evolution and the evolution of evolvability and then a seemingly unrelated subject: the evolution of robustness. For anyone that’s interested here’s an article I published in 2008–it has about 175 citations. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2538912/ https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2538912/ I’d also recommend the work by Peter Eggenberger from the late 90s.
- mindcrime 9y agoI assume this is the Peter Eggenberger you are referring to? https://www.semanticscholar.org/author/Peter-Eggenberger-Hotz/1728171 https://www.semanticscholar.org/author/Peter-Eggenberger-Hot...
- rdlecler1 9y agoLooks like the same guy.
- fizixer 9y agoDo you think creating a 3D universe (like that being worked on by open.ai), putting the evolvable agents in it and trying to make them evolve learning and intelligence is a good idea? I mean starting at a very primitive level, you could first aim for something like ant-level intelligence, then go to higher and higher intelligences from there.
- halflings 9y agoI think these type of discussions are really detached from the reality of what neural networks, AI or evolutionary algorithms are. These are mathematical models that optimise a specific fitness function, they borrow some biological concepts but they are not going to "evolve into ant-level intelligence".
- smallnamespace 9y ago> they are not going to "evolve into ant-level intelligence" How do we know until we've tried it? I mean, at a certain level of abstraction, you can just view humans as a bunch of atoms that have been placed in a heat bath for a very long time. And yet intelligence seems to have spontaneously self-organized from it.
- halflings 9y agoAgain, this is very detached from what ANNs or genetic algorithms are: relatively simple methods to optimise fitness (or "cost") functions. They are nowhere close to the complexity of a brain, and certainly do not have enough capacity to be a realistic simulation of the universe. > How do we know until we've tried it? Tried what, is the question? What's an ant-level intelligence? We have algorithms that can detect images/speech at super-human level (at least in some conditions). Worthy questions, but unrelated to these algorithms.
- Turing_Machine 9y agoI'm not sure that ants are doing a "realistic simulation of the universe", though, or anything like it. From what I understand, they're a lot closer to little robots than they are to something that can do Kip Thorne-level astrophysics, or Thomas Aquinas-level philosophy. I am thinking, in particular, of an experiment done by Richard Feynman where he got ants walking across small sheets of glass. After shuffling the sheets around so the chemical trail became a loop, he was able to get the ants tirelessly marching around in a circle (which they would presumably do until they dropped). Heck, you probably don't even need an ANN at all to do that, much less an evolutionary one.
- halflings 9y agoI have always seen evolutionary algorithm as a version of gradient descent that throws away the gradient, and instead just goes randomly in all directions until it finds something that works (which is extremely wasteful). I suppose this is wrong since people still find these techniques useful, but what are the advantages of these techniques compared to gradient descent? (other than the fact that you don't need your fitness function to be differentiable)
- MereInterest 9y agoRandom walks work well in high dimension soaces, where calculating the gradient gets to be very expensive. Depending on your metaparameters, random walk can also try to jump out of a local minimum, where gradient descent only optimizes within the initial local mimimum.
- halflings 9y agoGradient descent can also jump out of a local minimum if the learning rate is large enough, so they're equal in that sense. But it does make sense that a random walk would be more efficient in very high dimensional problems!
- pavelchristof 9y agoAbsolutely no. Random search does not work in high dimensions because of the "curse of dimensionality" - the number of directions to search grows exponentially with dimension. Gradient descent avoids the problem because it knows the right direction. Evolutionary strategies are doing (natural) gradient descent using an estimate of the gradient. Here's a good article: http://www.inference.vc/evolutionary-strategies-embarrassingly-parallelizable-optimization/ http://www.inference.vc/evolutionary-strategies-embarrassing...
- dragontamer 9y agoI think you confused "evolutionary algorithm" with Simulated Annealing. Because Simulated Annealing is LITERALLY a random walk (biased towards higher values, but its strongly random nonetheless). https://en.wikipedia.org/wiki/Simulated_annealing https://en.wikipedia.org/wiki/Simulated_annealing Simulated Annealing works because it doesn't get stuck in local maximums. Do a simple gradient ascent on this simple 2d plot, and its very, very unlikely to achieve the true global value: https://upload.wikimedia.org/wikipedia/commons/d/d5/Hill_Climbing_with_Simulated_Annealing.gif https://upload.wikimedia.org/wikipedia/commons/d/d5/Hill_Cli... But if you do Simulated Annealing (aka: random walk), you get to the global maximum much more reliably. Genetic Algorithms have a similar effect as Simulated Annealing because Genetic Algorithms are strongly randomized. But they still "hill climb" explicitly, because its rare for parents to be thrown away if they were superior to the children.
- smallnamespace 9y ago> evolution of evolvability and then a seemingly unrelated subject: the evolution of robustness. Isn't there a an analogue to this in software engineering? There is an extremely large space of programs that produce the exactly same output on a given input, but we humans favor programs that we can read and understand. We also favor programs that are modular and composable, because bits of those programs tend to get reused to create new programs and are easier to write than new 'blob of code' programs. One can view programs as memetic 'self-replicators', with a selection process dominated by the preferences of human readers and writers. If we analyzed many dependency graphs between code modules, or a graph of function call usage between snippets, I bet you'd find that actual human-written programs have the same 'sparse' connectivity that you see, because maintainability implies writing code along sane API abstraction boundaries. TL;DR evolutionary pressure might means nature naturally abstractions within genetic code
- Retric 9y agoThe mechanism for evolution is often the opposite of abstraction. Living things tend to make a copy of some really important bit of 'code' and then mutate that 'copy' rather than say losing the ability to form cell walls. On the other if a cell is making X then the new process can easily leverage the existence of that X when doing something new. Net result copy paste coding + dependency hell.
- mannigfaltig 9y ago> evolution of evolvability and then a seemingly unrelated subject: the evolution of robustness. Isn't evolvability only about robustness? What other criteria would improve evolution? Mutations just happen, so the question is how well the phenotype can deal with these mutations. If it can incorporate mutations well, it can tunnel to different useful phenotypes and therefore is robust.
- rdlecler1 9y agoAgree, but it’s not not obvious to most people. Robustness itself if a murky subject: are you robust to mutation, to the environment, genetic noise, genetic background? Also if you are too robust then you can’t evolve. What we want to say with evolvability is that we’re more predisposed positive selection.
- fouc 9y agoWhat are your thoughts about Grammatical Evolution? It cleverly uses BNF to constrain the possibilities to legitimate ones.
- zedpm 9y agoThat was my first thought as well; GE is the easiest way I know of to introduce domain-specific knowledge into the genotype > phenotype translation.
- kiechu 9y agoI also thought of that problem and I created language for representing agents in these systems. https://github.com/romankierzkowski/langner https://github.com/romankierzkowski/langner Unfortunately, I didn't carry on that work, so I haven't evaluated that kind of representation yet. I would love to know your opinion on Langner.
- Frogolocalypse 9y agoYou know the counter intuitive thing for myself that i found? Sexual reproduction sucks. It doesn't nearly have the performance gains I'd expect. In order to really own the gamut of a solution space, only asexual reproduction really has good consistent results. I've learned a lot more about why that is probably the case now, but i spent a long time getting to the bottom of it.
- CapacitorSet 9y ago>Sexual reproduction sucks. There is a joke to be made here.
- Frogolocalypse 9y agoPlants just wanna have fun?
- slewis 9y agoCliff-hanger! Can you elaborate on why asexual reproduction might perform better?
- Frogolocalypse 9y agoMy theory is that sexual reproduction focuses genes on performance in a stable environment, and asexual reproduction grows to encompass the entire gamut of every survivable environment. When you don't know the traits that are beneficial in an environment, a significant change adversely affects all sexually reproduced algorithms to a significant degree, whereas it affects all asexually produced algorithms at varying degrees.
- rdlecler1 9y agoI think the depends on your genotype-phenotype map. It’s hypothesized that sexual reproduction helps drive modularity because evolution needs to solve the problem of how to bring together two genetically different individuals and still come out with a viable offspring. This is why robustness is so entwined with evolvability. If your genotype-phenotype map is simple then robustness doesn’t need to evolve but this may limit evolvability. The thing I always found with with evolution is that there is no free lunch.
- pron 9y agoTuring proposed using genetic algorithms to evolve neural networks, and realizing the same issues you have, he then studied those underlying problems more in general (in particular, morphogenesis).
- yters 9y agoIsn't detecting unlimited novelty impossible due to Chaitin's incompleteness theorem?
- deepnotderp 9y agoOne thing I find interesting to note is that modern day policy gradient deep reinforcement learning methods are incredibly similar to evolutionary algorithms and DRL methods have been applied quite successfully to neural architecture search.
- tonmoy 9y agoI wonder why evolutionary algorithms never managed to be that successful.
- uoaei 9y agoThey're quite successful on complex multiobjective problems, but you need a lot of compute power to cover the solution space sufficiently. Most problems either 1) don't have such stringent requirements on multiobjective optimization (i.e. the problem can be recast with a single objective function, likely one with a gradient), or 2) more typical machine learning algorithms are "good enough" and require less compute power. But for instance designing complex geometries under numerous constraints is well-suited to evolutionary algorithms. EAs also shine when the evaluation for fitness is computationally-intensive, as you can defer the fitness evaluations until absolutely necessary.
- yters 9y agoMy understanding is MOEAs are not a whole lot better than random search.
- Jizzle 9y agoWhile perhaps not immediately pertinent to the problem, the emergence of sexual reproduction is credited as a major factor in the explosion of variation in multicellular organisms. Part of the advantage, ironically, is that sexual reproduction is a rather large burden compared to evolutionary strategies that came before. The fact that sexual reproduction is so challenging perhaps ensures that less is left to chance by filtering out individuals that cannot meet the burden and rewarding those that tend to be better at achieving reproduction itself. Likely there is some relation between improved reproductive success and some novel traits that helped to achieve it. I don't have the knowledge to weigh in on AI analogs, but I could imagine roughly a strategy that involves co-related burdens and goals to improve the chances of choosing the right individuals.
- mannigfaltig 9y agoI think, the main effect of sexual reproduction is that, much like GANs and competitive self-play, it creates species-internal competition: Both sexes need to impress, which makes cheating an obvious strategy (makeup, steroids, Shakespeare quotes, LISP etc., but many such examples can be found in the animal world), and hence both sexes also need to be able to detect cheating. Some species are rather asymmetric in that regard. For example, in humans it is mainly women who attract (they masquerade as fruits [make up is likely a cross-cultural phenomenon; and, well, breasts] tapping into male food gathering circuitry); men compete in hierarchies trying to impress and women select men from the top of the hierarchy. Complex dynamics emerging from this likely lead to the immense growth of the human cortex. Sexual reproduction basically outsources some of the selection effort to the cognitive apparatus of the species itself, thereby introducing a massive amount of additional selection signals (mainly by the much increased necessity to model other minds, namely minds of the opposite sex). Many of these signals promote traits that are useful for survival (mainly intelligence and health).
- mfrye0 9y agoI was thinking the same thing. I think it would be interesting to explore this area more and try to model it computationally. Your point about physical features made me think of how physical attractiveness plays into human development as well. Research has shown that beauty in humans is defined as physical symmetry. So "novelty" in our case might be defined as someone who is really ugly - the elephant man. So in this case, beauty wouldn't really fit into the robot walking example as it's neither fitness (moving the foot forward) or novelty. More a different type of fitness that increases the odds of reproduction.
- ponderingHplus 9y agoNice article, lots of good tidbits and insights. The thoughts on indirect encoding seem like an especially interesting area of research. I actually just finished up a project that used a genetic algorithm to tune some of the hyperparameters of an RNN [1]. I didn't evolve the architecture except which cell to use (LSTM or GRU), but it wouldn't be much of an extension to the proof of concept I coded. Thanks for sharing. [1] http://cole-maclean.github.io/blog/Evolving%20the%20StarCraftII%20Build%20Order%20Meta/ http://cole-maclean.github.io/blog/Evolving%20the%20StarCraf...
- briga 9y agoI came up with a similar idea recently--it figures that every original idea I ever have turns out to be not original and decades-old. Perhaps the lack of success so far has been due to the fact that the faculties of the brain we attribute to higher-order complex thought are themselves based upon brain regions that are much older evolutionary-speaking. So it's not just one system you have to evolve--it's many hierarchical subsystems. And given the amount of time it took before human-level intelligence arose in the animal kingdom it's pretty clear that randomly evolving a human-level intelligence isn't something that's going to happen very often. It also seems to me that the only reason intelligence evolved in the first place was because of the complex environment provided by our natural world. I have a feeling that we're not going to see much in the way of intelligent learning systems unless we can provide those systems with a sufficiently complex environment to learn and evolve within.
- XorNot 9y agoMy personal hypothesis is that strong AI will evolve when Google decide to add live feedback to google search suggestions. At the point that system can unprompted change what it shows the user, it'll be interactive enough that we will presumably just have to wait for adequate computational backing for it to "wake up".
- grblovrflowerrr 9y agoI wonder how much damage(physical damage) comes into play with evolving robust systems and creating interesting variations in nature. Using the robotic gait example, in the real world organisms have a high enough chance of losing limbs that having the neural circuitry to survive in the absence of one or more limbs is advantageous. Maybe these simulations could increase their ability to produce robust networks by modeling accidental damage(from tiny to catastrophic) to random parts of networks and selecting those that survive in spite of such damage.
- netheril96 9y agoLike dropout or stochastic depth?
- PeachPlum 9y agoDo you see many wild animals with missing limbs? Especially mammals
- robotresearcher 9y agoSee the work of Josh Bongard and Hod Lipson, examining exactly this topic. http://science.sciencemag.org/content/314/5802/1118 http://science.sciencemag.org/content/314/5802/1118
- yters 9y agoEvolutionary algorithms are perennially intriguing, but generally other approaches are favored. Odd, considering the incredible success of evolution with extremely limited trials from a computational perspective. I wonder why evolutionary computation does not live up to the expectation?
- cjalmeida 9y agoI'd guess limited computing resources. Nature had billions of years times trillions of "experiments" instance to reach it's amazing current state.
- jamesrom 9y agoNot only that, but a virtually unbounded population space to test. Count every single organism alive today.
- yters 9y agoOur top supercomputers can process tens of petaflops. That seems to easily dwarf these biological time scales you mention. There appears to be some magic in evolution that surpasses mere trial limitations.
- jamesrom 9y agoI'd like to double down and say the top supercomputers today couldn't, in reasonable time, simulate a single generation of the genetic variation in your gut flora alone.
- yters 9y agoSure, but that means the magic does not lie in evolution, but in the extreme amounts of information in biological organisms. Evolution is supposed to be able to generate incredibly complex organisms from very simple beginnings, all within a number of trials that can be simulated on today's desktop. Insofar as we displace the problem from evolution to the organism or environment we are saying there is nothing special about evolution. In which case it begs the question what is so special about evolution in the first place?
- jamez1 9y ago> At the time, its small group of practitioners thought it might be an alternative to the more conventional ANN training algorithm called backpropagation (a form of stochastic gradient descent). The author doesn't seem to understand what backpropagation is - gradient descent is performed on the derivative formed from backpropagation, they are not forms of one another.
- jhj 9y agoYep, also SGD is not necessarily implied either (for example, full batch gradient descent).
- mfrye0 9y agoI found this article really intriguing as someone new to this field. If I'm understanding this right, it seems like most approaches up to this point are focused on evolving a single "unit" or brain / person. You have the concept of "nature" that selects which units will advance to the next generation and passing on "DNA". First based on fitness and now the new approach is novelty. This may seem a bit naive, but has anyone explored adding a social dimension? For the robot walking example, you have nature choosing novelty and those that made progress. A basic social dimension could have units observing other units and sharing information. But then there's a variety of other dimensions - a unit blocking another unit from walking (cheating), a bigger unit destroying a smaller one, maybe success via misc factors like physical symmetry / popularity. Idk. Just curious to learn more and where the research is at.
- rdlecler1 9y agoThe is mostly in the real of Artificil Life. Check out Chris Adami’s work from the late 90s as a starting point.
- mfrye0 9y agoAwesome, thanks! I've been reading up a bit and this is exactly what I was hoping to find.
- isseu 9y agoI believe competition could be a big force towards progress. GANs are based on this topic and are very successful.
- mfrye0 9y agoYeah, I figured that. I imagine it's a bit challenging to model though. You'd have to be running every instance simultaneously and have them all observing and reacting to each other. Also gets into some interesting "morality" type of questions. As in if an instance cheats to get ahead, are there consequences?
- redcalx 9y agoAuthor of SharpNEAT here if anyone has any questions.
- pinouchon 9y agoWhat would be your recommendation to learn about these topics ? Moocs, books, having some pet project ?
- redcalx 9y agoI don't know of any online teaching material, I think this is because it is a relatively niche and under explored area of research - which is one of main reasons I continue to maintain and develop sharpneat. What has been useful for me is just setting up experiments and seeing what happens, and observing the way things go wrong. Typically evolution will find the flaws in any fitness score (metric) that is defined, often resulting in solutions that give good scores, but only because evolution was 'cheating', or rather, exploiting the flaws in the metric. This problem comes up a lot and it is is educational to go through that process and try to think up more robust tasks and ways of measuring success on those tasks. Ideally we want metrics that are continuous, so that we can 'follow the gradient' of success rather than e.g. having a fitness score just go from zero to a perfect score in one step. Also it's been educational seeing how networks evolve. One of the early modifications I made to NEAT was to periodically disable additive mutations (add nodes and connections), so as to strip away any redundant structure that could be slowing down evaluation of each neural net. This came from just seeing the networks grow rapidly, and not always with an fitness score gains to show for it. In summation I don't have a good answer for you, but if you can get interested in setting up an experiment and seeing how evolution tries to solve it all by itself hen maybe you'll get the 'bug' and start to think about where the limits to this approach are, and different ways of overcoming some of the present limits. From there you might want to pick through the occasional research paper to see what others are doing - I've found the NEAT based research to be quite accessible, i.e. e.g. not requiring a a lot of maths knowledge as is the case with deep learning and the like. Although I admit I do follow that world and have had to learn quite a bit of maths to keep up - and I think that's useful to draw ideas from that area. Hope that is of some help anyway.
- fnl 9y agoHow do evolutionary hyper-parameter optimizations compare to Bayesian ones? My impression always was that Bayesian optimization is more targeted, and therefore more efficient and ultimately finds optimal parameters faster. However, evolutionary algorithms are easier to parallelize, so maybe EAs indeed have a place in a non-research-oriented, applied DL setting?
- levesque 9y agoCovariance matrix adaptation is comparable on real-valued hyperparameters, but you're stuck outside of that. More typical genetic algorithms waste a TON of compute time, so they might end up finding a good solution, but the computational budget is out of reach of normal companies.