16 ms·

Having studied this extensively back when they were called Genetic Algorithms, I would like to offer a few insights. 1) One of the biggest reasons they fell ou

Having studied this extensively back when they were called Genetic Algorithms, I would like to offer a few insights. 1) One of the biggest reasons they fell out of favor for more "mathematical" approaches was that no one could really explain why exactly they worked. It makes sense on the surface that "survival of the fittest" and doing something akin to multiple stochastic gradient descents would work, but no one has really been able to produce a mathematical proof as to why. Since other folks are producing good examples of "explainable AI", I don't know how Genetic Algorithms/programming could be made 'explainable' as to why they achieved an optimal solution other than hand-waving to how evolution works in nature. 2) The most important thing to define is the fitness function, this defines what the search space looks like and how easily a globally optimal solution can be derived. For a good example of an interesting search space that a genetic program would have a difficult time with, see Schwefel functions [0]. Back when I researched these things closely, my intuition was that reality rarely fits neatly into good fitness functions and I felt that at the point you are understanding the problem, you may just be better off with a direct approach, which leads to 3) Genetic programming should only really be considered when there are no known alternatives or they are way too computationally expensive. In either case, I would welcome a resurgence in a topic I once knew quite well, though I haven't been in that field for a few years now. [0] https://jamesmccaffrey.files.wordpress.com/2011/12/schwefelsfunction.jpg https://jamesmccaffrey.files.wordpress.com/2011/12/schwefels...

azakai 9y ago
Regarding 1, that seems surprising: biology has had many mathematical proofs and models (for almost a century now, e.g. Fisher) explaining why evolution works. Evolution works in nature for non-hand-wavey reasons, doesn't the same logic justify artificial evolution in genetic algorithms?
ewjordan 9y ago
Wait, I'm confused...you're saying genetic approaches fell out of favor because they're basically just stochastic gradient descent? Most of modern DL relies heavily on SGD at various points during training. My impression is that they fell out of favor precisely because don't actually use any gradients, and end up converging on good maxima slower than you could if you used the gradients from the net. Am I off base here?
- mav3r1ck 9y ago
  You are not off base at all, thanks for clarify and sorry for the confusion, I did not mean to say it was using gradient descent. It's been a while. The term I was thinking of was multiple "simulated annealing".
- yorwba 9y ago
  If you mutate genomes by small additive modifications to a vector of continuous parameters, then taking lots of samples and keeping the best is essentially a stochastic approximation to gradient descent. However, unlike the SGD used in deep learning, it doesn't make use of calculus and therefore requires many more samples (exponentially more, in the worst case) to get a gradient of equivalent accuracy. I.e. it's slow. If your mutations aren't small, or your parameters are not continuously valued, or your fitness function is hard to differentiate analytically, genetic algorithms might still come out ahead.
  - xants 9y ago
    Is it true that genetic algorithms have the benefit of being able to find the global optima more consistently due to the incorporation of randomness in subsequent generations? Whereas DL models often get stuck at local optima?
    - maksimum 9y ago
      What do you mean by "find" and how do you define "global optima"? For "find" you could discuss convergence rates vs. the points that are being converged to. If you add randomness at every iteration you're not even converging, at which point annealing rate becomes a related issue. For "global optima" are we talking about training error, or test error, or some other kind of function value?
    - turingcompeteme 9y ago
      It depends, but I don't think general statements like that are necessarily true. Most methods allow trade-offs between converging quickly on local optima vs finding global optima. The mutation aspect of genetic algorithms is just one way to do this. With well tuned mutation parameters, genetic algorithms can definitely be successful at finding global optima, but similar measures exist for most methods.
bitL 9y ago
Crossing two genotypes and making mutations so that they produce consistent encoding was for me what put genetic algorithms to purely academic area - for things like TSP I either couldn't come up with good crossing function or it was producing mostly the same results after applying some "consistentification".
koube 9y ago
Where's the posts on explainable AI? I did a ctrl+f but didn't see any.
- oftenwrong 9y ago
  https://distill.pub/2018/building-blocks/ https://distill.pub/2018/building-blocks/ https://news.ycombinator.com/item?id=16531246 https://news.ycombinator.com/item?id=16531246
Geee 9y ago
Isn't that the same question as to why the whole universe exists? Why chaos results in order? Isn't there a proof that 'given such random process, an universe like we have is inevitably created'?
vanderZwan 9y ago
Regarding 3), do you know of any work on genetic programming as a method of doing research into evolvability itself? So basically, as a form of simulation? Tierra obviously counts, but I was thinking of more specific examples. Say, something like this paper, which showed that adding a tiny cost-function to a network spontaneously makes it more modular: [0] http://rspb.royalsocietypublishing.org/content/280/1755/20122863 http://rspb.royalsocietypublishing.org/content/280/1755/2012...
- robotresearcher 9y ago
  Here are a couple. The keyphrase is 'evolution of evolvability'. http://users.sussex.ac.uk/~lionelb/downloads/EASy/publications/alife11.pdf http://users.sussex.ac.uk/~lionelb/downloads/EASy/publicatio... http://dynamics.org/Altenberg/FILES/LeeEEGP.pdf http://dynamics.org/Altenberg/FILES/LeeEEGP.pdf
- guest12268 9y ago
  Yes there has been some very interesting recent work. In particular, how evolvability emerges and is harnessed in evolutionary computation. A few papers come to mind: 1. Evolvability is Inevitable: http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0062186 http://journals.plos.org/plosone/article?id=10.1371/journal.... 2. Extinction Events can Accelerate Evolution (2015): http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0132886 http://journals.plos.org/plosone/article?id=10.1371/journal.... 3. Evolvability Search: Directly selecting for evolvability in order to study and produce it (2016): http://www.evolvingai.org/mengistu-lehman-clune-2016-evolvability-search-directly http://www.evolvingai.org/mengistu-lehman-clune-2016-evolvab...
  - Houshalter 9y ago
    Evolvability can also evolve away too. For instance, a gene that decreases the mutation rate to 0. Most mutations are harmful, so any organism with the gene will be more likely to have successful children. And eventually the gene will become dominant and there will be no more mutations. And evolution will stop.
jorgemf 9y ago
Regarding your points: 1) "explainable AI" is better in GA than in deep learning. GA gives you a structure that works and probably easier to understand than any Deep Learning model (which it is a huge math function). There are so many things that also doesn't make sense why they work in deep learning but we still use them, that is the same with GA. 2) Knowing the fitness function doesn't mean you can solve the problem. When the search space is so big you need something to search on it, and there is where GA can shine. It is also the same with Deep Learning and mostly evolutionary computation. The search space is so huge for a "brute force algorithm". You need heuristics and GA works well for some problems, the same way gradient descent works well for others too.
sampo 9y ago
> no one could really explain why exactly they worked Genetic algorithms work on problems where some subsets of variables are approximately separable (uncorrelated) from some other subsets of variables. F(a,b,c,d,e,f) ≈ F1(a,b,c) × F2(d,e,f) So if you have found a good combination or a,b,c it makes sense to try how it works it any promising combinations of d,e,f. Some natural world problems really have this property.
verdverm 9y ago
If you like GP, you might like PGE more (self bias) http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.394.140&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.394...
Nomentatus 9y ago
Re 3, last resort: isn't it also true that any other method can likely be improved upon by taking whatever network results and using it as a starting point for genetic improvements? Sometimes the extra expense won't be worthwhile, of course, but if you want to reduce the number of edge cases for autonomous driving, say, it might well be worthwhile IMHO. (There's an earlier discussion about the myth of local optima here that might or might not answer my question.)
resu_nimda 9y ago
1) One of the biggest reasons they fell out of favor for more "mathematical" approaches was that no one could really explain why exactly they worked. Kind of like how nobody can really explain how the brain works, or life in general. My gut feeling is that it is hubris to think that we are going to "figure out" intelligence with increasingly sophisticated mathematical models anytime soon. We are not giving proper credit to how complex it is, and the multi-billion year developmental process that it took. We think we can just short-circuit that with some fancy math because we've had success with planetary orbits and other comparatively rudimentary phenomena. The current industry approaches are great for extracting certain kinds of value out of large data sets, but in terms of producing a result that could even begin to be considered as interesting as life (i.e. AGI or "strong AI"), I believe we will have to rely on creating a system whose inner workings are too complex for us to understand. In other words, going off of Arthur C Clarke's definition, life is magic. And we're trying to create something equally magical. Almost by definition, if we can analytically understand it, it's not going to be interesting enough.
- pas 9y ago
  > We are not giving proper credit to how complex it is, and the multi-billion year developmental process that it took. Or we are simply not ready to accept that it's simply a big book of heuristics fine-tuned over biological eons. It's just big. We have too many interwoven, interdependent, synergistic faculties. Input, output, and a lot of mental stuff for making the right connections between the ins and the outs. Theory of mind, basic reasoning, the whole limbic system (emotions, basic behavior, dopaminergic motivaton), the executive functions in the prefrontal cortex, all are very specialized things, and we have a laundry list of those, all fine-tuned for each other. And there's no big magic. Nothing to "understand", no closed formula for consciousness. It's simply a faculty that makes the "all's good, you're conscious" light go green, and it's easy to do that after all the other stuff are working well that does the heavy lifting to make sense of reality.
  - resu_nimda 9y ago
    Your last paragraph seems to contain the kind of overconfidence that I'm talking about. I don't understand how you can say "consciousness is simply X" or "it's easy to do that [if you handwave away the hard parts]." Clearly it's not that simple or easy, or we would have done it. We can't even create life from non-life. How can we begin to understand all the stuff you're talking about that's been layered on top? We don't understand this stuff well enough to just handwave it away as unimportant or trivial.
jfz 9y ago
I'll admit that finding the right fitness function is hard, but I find that multi-dimensional fitness functions are well-suited to finding a set of solutions that a human can choose from. If you are finding paths for a fleet of delivery trucks, you can optimize separately for time, distance, and cost. Then, with the solutions that are better at all three than every other solution, pick 10 different ones and let a human make a decision. I agree that when there's a fast, perfect solution, it doesn't make sense to use genetic algorithms. But when finding solutions to a non-general problem (optimize CNC tooling to produce a list of orders, each of which has a series of operations that require a certain amount of time, on certain machines, and require being moved from machine to machine, such that you produce the most on-time orders for high-priority clients), genetic algorithms can work very well.
marcosdumay 9y ago
> no one could really explain why exactly they worked That is the first time I have heard that claim, and since we have a large body of knowledge describing how evolution works (that sampo description is one the clearest I've seen) and how it can be optimized, I imagine you are talking about some other problem. Is it about predicting the causes of some learned trait? Is there some interesting research on that?
- Cacti 9y ago
  They are referring to Genetic Algorithms. There was a theory called the "building block hypothesis" but no one could prove it (turned out it was impossible to prove). The field was sort of run on hand waving for several decades.
  - eafan 9y ago
    Clearly lack of a sound theoretical basis or proof for why deep learning works has not stopped its proliferation. For a practitioner, the proof is in the pudding: generalized results, novel solutions that provably work, new designs that fulfill the given objective(s). At the end of the day, those are what really matter for practical applications.
  - marcosdumay 9y ago
    The fact that it is impossible to prove is what is new to me. Even more because it's clearly not a property of genetic algorithms in general, but a very powerful effect that one aims into achieving with genetic algorithms and a good domain modeling. I don't really understand what is the meaning of something like that being impossible to prove.
Cacti 9y ago
Yep. The original wave of genetic algorithms largely depended on some hand-wavy "building block" ideas that no one could really prove. It turned out that it was because proving them is impossible in the general sense, as we found out from the NFL theorems in the mid-to-late 90s, and it wasn't even clear the field had a scientific basis at all. So I was surprised to see them make a return about a decade later. Hopefully there is a little more rigor this time around.
- sampo 9y ago
  > as we found out from the NFL theorems in the mid-to-late 90s, and it wasn't even clear the field had a scientific basis at all. NFL theorems are, should I say, purely theoretical and provide no insight on real-world problems. Say we try to find a function that is an optimal solution to something. NFL theorems consider the space of all possible functions, the overwhelming majority of which are discontinuous. Whereas real life problems tend to have functions that are at least more or less continuous.
  - letitgo12345 9y ago
    Not just discontinuous but have high Kolmogorov complexity (effectively meaning that the value of the objective function is random and has no real relation to the input arguments) so not a surprise that you can't do better than random! Honestly, there's no justification to be using NFL theorems to explain why we can't optimize well on real world tasks. Edit: And such high Kolmogorov complexity function constitute most possible objective functions -- i.e. exponentially more than the number of objective functions that don't have high Kolmogorov complexity. And all real world objective functions have comparatively low Kolmogorov complexity.
    - sampo 9y ago
      Good notion, pointing the Kolmogorov complexity. Yeah. You have a function, so basically a long array of numbers, and you want to find the maximum. If the data in the array has some structure, like it's sampled from a sine wave or something, you can use some strategies to find the maximum. Like gradient descent, or binary search. Something. But if the array is filled with random numbers, looking at other arrays elements give absolutely no hint on what might be in an array element you haven't yet looked at. So there doesn't exist any more efficient strategies to find the maximum number, than linear or random search. And the space of all possible functions mostly consists of discontinuous functions that are, for all purposes, just samples of random noise. This is all NFL theorems say. I really don't understand how they got be such a big deal.
evolutioner 9y ago
Sentient employee here. I'll give an example on a problem for which we use evolutionary algorithms: website optimization. Say you want to try many various changes like the title of your page, the color of the background, the position of your buy button etc. We solve this problem by trying out random variations of these websites - like A/B testing with more candidates - and by crossing the best performing ones to create a new generation of websites. This helps us find good performing variations in a very big search space. This would be hard to do with deep learning as we start with no data at all, measuring the performance is quite noisy and you can't compute a gradient to know how to evolve your website. There is no smoothness between a title and another. Also you could try to make a linear model for to see what effect each change has, but that doesn't take into account all the dependencies that can be complex, for example what title goes well with what background color. Evolutionary computation helps implicitly optimize without having to formulate a model.
- avip 9y ago
  Ok... so... let's say your A/B only optimizes the colour and location of a single CTA button, and conversion rate is your fitness. 2 previous generations have top/blue and bottom/red. How does the next one look?
  - evolutioner 9y ago
    Each generation has like 10~20 candidate websites. The better the conversion rate, the more likely it is to get chosen as a parent. With your example, let's say two parents with top/blue and bottom/red are chosen, then their offspring will either be top/red or bottom/blue because we make sure the same website isn't tested twice. More generally each feature of the offspring will be randomly picked from the features of the two parents. So two parents A/A/B and B/C/B can give the offspring A/C/B or B/A/B. There is also some random mutations that are possible with a low likelihood. link to the product: https://www.ascend.ai/ https://www.ascend.ai/
- avilay 9y ago
  What is the advantage of using evolutionary algos in this case over using something like Thompson Sampling or Contextual Multi-Armed Bandit? (http://www.kdd.org/kdd2017/papers/view/an-efficient-bandit-algorithm-for-realtime-multivariate-optimization http://www.kdd.org/kdd2017/papers/view/an-efficient-bandit-a...)
yazr 9y ago
In your experience, are GA/EA suitable for combinatorical problems? My domain is basically a combinatorical problem on large, sparse graphs. I am currently focused on DL with lots of custom feature engineering. I am making progress but its slow.
inverse_pi 9y ago
My thesis was on Generic Algorithm. I stopped and started working on Deep Learning mainly because like you said, GAs don't really have a strong mathematical foundation. Ironically, no one could really explain why CNNs work mathematically either. I've heard a lot of hand-wavy arguments about local search, local sensitivity, etc. However, no one could really prove anything meaningful. There are some papers around certain types of architecture is invariant under certain types of affine transformations. But all of them sounds like trying to convince ourselves rather than putting a firm mathematical framework to guide our research. Maybe that's why natural inspired algorithms are getting attention, the community is throwing stuff on the wall to see what sticks. It's funny to me because Genetic Algorithms were once frowned upon by majority of the community. I guess the moral lesson is stop chasing what's trendy.
- Houshalter 9y ago
  Why should we expect there to be any mathematical foundation to this stuff? It's quite possible to imagine an alternate universe where GAs and neural nets don't work. Because they have different datasets that don't fit the structure of NNs well. Or problems that happen to not be solvable by the search strategies of GAs. In fact we have many such problems in our own universe. I can give many examples of things NNs and GAs don't work well on right now. Those are just ignored by the research.
  - inverse_pi 9y ago
    why does the existence of such problems disprove the existence of a mathematical foundation? A well-founded mathematical foundation would prove/predict/explain why such problems don't "fit" with the "structure of NNs" with precise lower/upper bounds. Anything that works, and especially everything that doesn't work, must have an explanation. God doesn't play dice.
    - Houshalter 9y ago
      Maybe there's a reason. But I don't think you will ever be able to "prove" it. In any kind of formal way that would be satisfying to mathematicians. Solomonoff induction is the best attempt to try to formalize machine learning. And in theory any machine learning algorithm that works, works because it approximates Solomonoff induction somehow. But proving anything approximates Solomonoff induction is absurdly difficult or impossible. Because it's incomputable and involves the search space of all possible computer programs.
hyperpallium 9y ago
> I felt that at the point you are understanding the problem, you may just be better off with a direct approach I formed a similar impression in my PhD research.
- hyperpallium 9y ago
  Not that relevant, but wanted to elaborate a little: I exhaustively solved a toy version of my problem on a cluster, but found no discernable gradients. Good solutions were isolated spikes, with no elevations adjacent that could lead to them. So, random sampling would be as good as you'd get. The thing to do is change the problem, transform the space/dimensions, so better solutions were spatially proximate. But then, I'd be solving the problem. Another approach is to have the computer do this, seach the space of search spaces. But this higher-level space is even less likely to have informative gradients. OTOH, the data was in terms of a language, which would have introduced its own artefacts. A better search space would compensate for those, and might have been easy to find.
diyseguy 9y ago
I don't understand why A.I. can't be explainable. Can't they just add logging every time it makes a decision and then trace through the trail of decisions to the final result?
- abhgh 9y ago
  The AI that is not explainable is not because it cannot log things, its because the semantic interpretation of what it can log is hard. Starting with the real world input (which we understand) a lot of algorithms progressively apply mathematical transformations till reaching the output. It is the real world "meanings"of these transformations, or what is eventually learned: the stack of these transformations - that is hard to grasp.
- Maybestring 9y ago
  If you are willing to accept that as an explanation. Yes, it's easily explainable. A big list of anonymous decisions is easy. Naming those decisions is hard.
jmmcd 9y ago
I think you've confused genetic algorithms with genetic programming. They're not the same thing. > I don't know how Genetic Algorithms/programming could be made 'explainable' as to why they achieved an optimal solution other than hand-waving to how evolution works in nature. This is quite confused. You're comparing different levels of the systems. In neural networks, we would like to know why a numerical model (which has been optimised by gradient descent) gives the outputs it gives. In GAs, (1) the objects being created usually aren't numerical models -- think instead of solutions to TSPs; (2) the reason the object is good is rather easy to see -- one just has to look at the objective function and verify that that the object has the desired properties; (3) we don't really care what other objects were considered during the search process.
- randomsearch 9y ago
  > (2) the reason the object is good is rather easy to see -- one just has to look at the objective function and verify that that the object has the desired properties; Minor point: whether the result of evolution is easy to understand or not depends on the representation (encoding). Even GA results can be difficult to understand if they describe complex objects. In the case of GP, bloat (rapid increase in average program size in your population) can make results very difficult to interpret.
cabalamat 9y ago
> I don't know how Genetic Algorithms/programming could be made 'explainable' as to why they achieved an optimal solution other than hand-waving to how evolution works in nature. With either GA or ANN, you don't know that the algorithm has achieved the optimal solution and I would be surprised if you could ever prove that in the general case. What you can know is that your algorithm performs well, e.g. by testing how well it plays go or drives a car or recognises faces, or whatever.
sdubois 9y ago
I pretty much agree with what you said, but DL (and even more deep reinforcement learning) is really computationally expensive
tripzilch 9y ago
Another reason is for most demos and examples of Genetic Algorithms, that Simulated Annealing is almost always more optimal. Let me first say that I'm not certain this is the case for the purposes lined out in the article, because I'm not entirely sure what they're trying to do. Unless you have a crossover operator that really makes sense for your fitness function and problem, a GA is basically nothing but a bunch of SA processes running in parallel. In that case you would prefer SA, because it has less hyperparameters to tune, convergence is better defined, and there are proven methods to tune the hyperparameters. It's not that hard if you have a working GA optimizer, to test how well it does with SA as a baseline, because the algorithms are fairly similar. Unfortunately not many demos do this baseline comparison and I'm pretty sure most of them won't do significantly better with GAs.

azakai 9y ago

Regarding 1, that seems surprising: biology has had many mathematical proofs and models (for almost a century now, e.g. Fisher) explaining why evolution works. Evolution works in nature for non-hand-wavey reasons, doesn't the same logic justify artificial evolution in genetic algorithms?

ewjordan 9y ago

Wait, I'm confused...you're saying genetic approaches fell out of favor because they're basically just stochastic gradient descent? Most of modern DL relies heavily on SGD at various points during training. My impression is that they fell out of favor precisely because don't actually use any gradients, and end up converging on good maxima slower than you could if you used the gradients from the net. Am I off base here?

mav3r1ck 9y ago
You are not off base at all, thanks for clarify and sorry for the confusion, I did not mean to say it was using gradient descent. It's been a while. The term I was thinking of was multiple "simulated annealing".
yorwba 9y ago
If you mutate genomes by small additive modifications to a vector of continuous parameters, then taking lots of samples and keeping the best is essentially a stochastic approximation to gradient descent. However, unlike the SGD used in deep learning, it doesn't make use of calculus and therefore requires many more samples (exponentially more, in the worst case) to get a gradient of equivalent accuracy. I.e. it's slow. If your mutations aren't small, or your parameters are not continuously valued, or your fitness function is hard to differentiate analytically, genetic algorithms might still come out ahead.
- xants 9y ago
  Is it true that genetic algorithms have the benefit of being able to find the global optima more consistently due to the incorporation of randomness in subsequent generations? Whereas DL models often get stuck at local optima?
  - maksimum 9y ago
    What do you mean by "find" and how do you define "global optima"? For "find" you could discuss convergence rates vs. the points that are being converged to. If you add randomness at every iteration you're not even converging, at which point annealing rate becomes a related issue. For "global optima" are we talking about training error, or test error, or some other kind of function value?
  - turingcompeteme 9y ago
    It depends, but I don't think general statements like that are necessarily true. Most methods allow trade-offs between converging quickly on local optima vs finding global optima. The mutation aspect of genetic algorithms is just one way to do this. With well tuned mutation parameters, genetic algorithms can definitely be successful at finding global optima, but similar measures exist for most methods.

bitL 9y ago

Crossing two genotypes and making mutations so that they produce consistent encoding was for me what put genetic algorithms to purely academic area - for things like TSP I either couldn't come up with good crossing function or it was producing mostly the same results after applying some "consistentification".

koube 9y ago

Where's the posts on explainable AI? I did a ctrl+f but didn't see any.

oftenwrong 9y ago
https://distill.pub/2018/building-blocks/ https://distill.pub/2018/building-blocks/ https://news.ycombinator.com/item?id=16531246 https://news.ycombinator.com/item?id=16531246

Geee 9y ago

Isn't that the same question as to why the whole universe exists? Why chaos results in order? Isn't there a proof that 'given such random process, an universe like we have is inevitably created'?

vanderZwan 9y ago

Regarding 3), do you know of any work on genetic programming as a method of doing research into evolvability itself? So basically, as a form of simulation? Tierra obviously counts, but I was thinking of more specific examples. Say, something like this paper, which showed that adding a tiny cost-function to a network spontaneously makes it more modular: [0] http://rspb.royalsocietypublishing.org/content/280/1755/20122863 http://rspb.royalsocietypublishing.org/content/280/1755/2012...

robotresearcher 9y ago
Here are a couple. The keyphrase is 'evolution of evolvability'. http://users.sussex.ac.uk/~lionelb/downloads/EASy/publications/alife11.pdf http://users.sussex.ac.uk/~lionelb/downloads/EASy/publicatio... http://dynamics.org/Altenberg/FILES/LeeEEGP.pdf http://dynamics.org/Altenberg/FILES/LeeEEGP.pdf
guest12268 9y ago
Yes there has been some very interesting recent work. In particular, how evolvability emerges and is harnessed in evolutionary computation. A few papers come to mind: 1. Evolvability is Inevitable: http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0062186 http://journals.plos.org/plosone/article?id=10.1371/journal.... 2. Extinction Events can Accelerate Evolution (2015): http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0132886 http://journals.plos.org/plosone/article?id=10.1371/journal.... 3. Evolvability Search: Directly selecting for evolvability in order to study and produce it (2016): http://www.evolvingai.org/mengistu-lehman-clune-2016-evolvability-search-directly http://www.evolvingai.org/mengistu-lehman-clune-2016-evolvab...
- Houshalter 9y ago
  Evolvability can also evolve away too. For instance, a gene that decreases the mutation rate to 0. Most mutations are harmful, so any organism with the gene will be more likely to have successful children. And eventually the gene will become dominant and there will be no more mutations. And evolution will stop.

jorgemf 9y ago

Regarding your points: 1) "explainable AI" is better in GA than in deep learning. GA gives you a structure that works and probably easier to understand than any Deep Learning model (which it is a huge math function). There are so many things that also doesn't make sense why they work in deep learning but we still use them, that is the same with GA. 2) Knowing the fitness function doesn't mean you can solve the problem. When the search space is so big you need something to search on it, and there is where GA can shine. It is also the same with Deep Learning and mostly evolutionary computation. The search space is so huge for a "brute force algorithm". You need heuristics and GA works well for some problems, the same way gradient descent works well for others too.

sampo 9y ago

> no one could really explain why exactly they worked Genetic algorithms work on problems where some subsets of variables are approximately separable (uncorrelated) from some other subsets of variables. F(a,b,c,d,e,f) ≈ F1(a,b,c) × F2(d,e,f) So if you have found a good combination or a,b,c it makes sense to try how it works it any promising combinations of d,e,f. Some natural world problems really have this property.

verdverm 9y ago

If you like GP, you might like PGE more (self bias) http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.394.140&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.394...

Nomentatus 9y ago

Re 3, last resort: isn't it also true that any other method can likely be improved upon by taking whatever network results and using it as a starting point for genetic improvements? Sometimes the extra expense won't be worthwhile, of course, but if you want to reduce the number of edge cases for autonomous driving, say, it might well be worthwhile IMHO. (There's an earlier discussion about the myth of local optima here that might or might not answer my question.)

resu_nimda 9y ago

1) One of the biggest reasons they fell out of favor for more "mathematical" approaches was that no one could really explain why exactly they worked. Kind of like how nobody can really explain how the brain works, or life in general. My gut feeling is that it is hubris to think that we are going to "figure out" intelligence with increasingly sophisticated mathematical models anytime soon. We are not giving proper credit to how complex it is, and the multi-billion year developmental process that it took. We think we can just short-circuit that with some fancy math because we've had success with planetary orbits and other comparatively rudimentary phenomena. The current industry approaches are great for extracting certain kinds of value out of large data sets, but in terms of producing a result that could even begin to be considered as interesting as life (i.e. AGI or "strong AI"), I believe we will have to rely on creating a system whose inner workings are too complex for us to understand. In other words, going off of Arthur C Clarke's definition, life is magic. And we're trying to create something equally magical. Almost by definition, if we can analytically understand it, it's not going to be interesting enough.

pas 9y ago
> We are not giving proper credit to how complex it is, and the multi-billion year developmental process that it took. Or we are simply not ready to accept that it's simply a big book of heuristics fine-tuned over biological eons. It's just big. We have too many interwoven, interdependent, synergistic faculties. Input, output, and a lot of mental stuff for making the right connections between the ins and the outs. Theory of mind, basic reasoning, the whole limbic system (emotions, basic behavior, dopaminergic motivaton), the executive functions in the prefrontal cortex, all are very specialized things, and we have a laundry list of those, all fine-tuned for each other. And there's no big magic. Nothing to "understand", no closed formula for consciousness. It's simply a faculty that makes the "all's good, you're conscious" light go green, and it's easy to do that after all the other stuff are working well that does the heavy lifting to make sense of reality.
- resu_nimda 9y ago
  Your last paragraph seems to contain the kind of overconfidence that I'm talking about. I don't understand how you can say "consciousness is simply X" or "it's easy to do that [if you handwave away the hard parts]." Clearly it's not that simple or easy, or we would have done it. We can't even create life from non-life. How can we begin to understand all the stuff you're talking about that's been layered on top? We don't understand this stuff well enough to just handwave it away as unimportant or trivial.

jfz 9y ago

I'll admit that finding the right fitness function is hard, but I find that multi-dimensional fitness functions are well-suited to finding a set of solutions that a human can choose from. If you are finding paths for a fleet of delivery trucks, you can optimize separately for time, distance, and cost. Then, with the solutions that are better at all three than every other solution, pick 10 different ones and let a human make a decision. I agree that when there's a fast, perfect solution, it doesn't make sense to use genetic algorithms. But when finding solutions to a non-general problem (optimize CNC tooling to produce a list of orders, each of which has a series of operations that require a certain amount of time, on certain machines, and require being moved from machine to machine, such that you produce the most on-time orders for high-priority clients), genetic algorithms can work very well.

marcosdumay 9y ago

> no one could really explain why exactly they worked That is the first time I have heard that claim, and since we have a large body of knowledge describing how evolution works (that sampo description is one the clearest I've seen) and how it can be optimized, I imagine you are talking about some other problem. Is it about predicting the causes of some learned trait? Is there some interesting research on that?

Cacti 9y ago
They are referring to Genetic Algorithms. There was a theory called the "building block hypothesis" but no one could prove it (turned out it was impossible to prove). The field was sort of run on hand waving for several decades.
- eafan 9y ago
  Clearly lack of a sound theoretical basis or proof for why deep learning works has not stopped its proliferation. For a practitioner, the proof is in the pudding: generalized results, novel solutions that provably work, new designs that fulfill the given objective(s). At the end of the day, those are what really matter for practical applications.
- marcosdumay 9y ago
  The fact that it is impossible to prove is what is new to me. Even more because it's clearly not a property of genetic algorithms in general, but a very powerful effect that one aims into achieving with genetic algorithms and a good domain modeling. I don't really understand what is the meaning of something like that being impossible to prove.

Cacti 9y ago

Yep. The original wave of genetic algorithms largely depended on some hand-wavy "building block" ideas that no one could really prove. It turned out that it was because proving them is impossible in the general sense, as we found out from the NFL theorems in the mid-to-late 90s, and it wasn't even clear the field had a scientific basis at all. So I was surprised to see them make a return about a decade later. Hopefully there is a little more rigor this time around.

sampo 9y ago
> as we found out from the NFL theorems in the mid-to-late 90s, and it wasn't even clear the field had a scientific basis at all. NFL theorems are, should I say, purely theoretical and provide no insight on real-world problems. Say we try to find a function that is an optimal solution to something. NFL theorems consider the space of all possible functions, the overwhelming majority of which are discontinuous. Whereas real life problems tend to have functions that are at least more or less continuous.
- letitgo12345 9y ago
  Not just discontinuous but have high Kolmogorov complexity (effectively meaning that the value of the objective function is random and has no real relation to the input arguments) so not a surprise that you can't do better than random! Honestly, there's no justification to be using NFL theorems to explain why we can't optimize well on real world tasks. Edit: And such high Kolmogorov complexity function constitute most possible objective functions -- i.e. exponentially more than the number of objective functions that don't have high Kolmogorov complexity. And all real world objective functions have comparatively low Kolmogorov complexity.
  - sampo 9y ago
    Good notion, pointing the Kolmogorov complexity. Yeah. You have a function, so basically a long array of numbers, and you want to find the maximum. If the data in the array has some structure, like it's sampled from a sine wave or something, you can use some strategies to find the maximum. Like gradient descent, or binary search. Something. But if the array is filled with random numbers, looking at other arrays elements give absolutely no hint on what might be in an array element you haven't yet looked at. So there doesn't exist any more efficient strategies to find the maximum number, than linear or random search. And the space of all possible functions mostly consists of discontinuous functions that are, for all purposes, just samples of random noise. This is all NFL theorems say. I really don't understand how they got be such a big deal.

evolutioner 9y ago

Sentient employee here. I'll give an example on a problem for which we use evolutionary algorithms: website optimization. Say you want to try many various changes like the title of your page, the color of the background, the position of your buy button etc. We solve this problem by trying out random variations of these websites - like A/B testing with more candidates - and by crossing the best performing ones to create a new generation of websites. This helps us find good performing variations in a very big search space. This would be hard to do with deep learning as we start with no data at all, measuring the performance is quite noisy and you can't compute a gradient to know how to evolve your website. There is no smoothness between a title and another. Also you could try to make a linear model for to see what effect each change has, but that doesn't take into account all the dependencies that can be complex, for example what title goes well with what background color. Evolutionary computation helps implicitly optimize without having to formulate a model.

avip 9y ago
Ok... so... let's say your A/B only optimizes the colour and location of a single CTA button, and conversion rate is your fitness. 2 previous generations have top/blue and bottom/red. How does the next one look?
- evolutioner 9y ago
  Each generation has like 10~20 candidate websites. The better the conversion rate, the more likely it is to get chosen as a parent. With your example, let's say two parents with top/blue and bottom/red are chosen, then their offspring will either be top/red or bottom/blue because we make sure the same website isn't tested twice. More generally each feature of the offspring will be randomly picked from the features of the two parents. So two parents A/A/B and B/C/B can give the offspring A/C/B or B/A/B. There is also some random mutations that are possible with a low likelihood. link to the product: https://www.ascend.ai/ https://www.ascend.ai/
avilay 9y ago
What is the advantage of using evolutionary algos in this case over using something like Thompson Sampling or Contextual Multi-Armed Bandit? (http://www.kdd.org/kdd2017/papers/view/an-efficient-bandit-algorithm-for-realtime-multivariate-optimization http://www.kdd.org/kdd2017/papers/view/an-efficient-bandit-a...)

yazr 9y ago

In your experience, are GA/EA suitable for combinatorical problems? My domain is basically a combinatorical problem on large, sparse graphs. I am currently focused on DL with lots of custom feature engineering. I am making progress but its slow.

inverse_pi 9y ago

My thesis was on Generic Algorithm. I stopped and started working on Deep Learning mainly because like you said, GAs don't really have a strong mathematical foundation. Ironically, no one could really explain why CNNs work mathematically either. I've heard a lot of hand-wavy arguments about local search, local sensitivity, etc. However, no one could really prove anything meaningful. There are some papers around certain types of architecture is invariant under certain types of affine transformations. But all of them sounds like trying to convince ourselves rather than putting a firm mathematical framework to guide our research. Maybe that's why natural inspired algorithms are getting attention, the community is throwing stuff on the wall to see what sticks. It's funny to me because Genetic Algorithms were once frowned upon by majority of the community. I guess the moral lesson is stop chasing what's trendy.

Houshalter 9y ago
Why should we expect there to be any mathematical foundation to this stuff? It's quite possible to imagine an alternate universe where GAs and neural nets don't work. Because they have different datasets that don't fit the structure of NNs well. Or problems that happen to not be solvable by the search strategies of GAs. In fact we have many such problems in our own universe. I can give many examples of things NNs and GAs don't work well on right now. Those are just ignored by the research.
- inverse_pi 9y ago
  why does the existence of such problems disprove the existence of a mathematical foundation? A well-founded mathematical foundation would prove/predict/explain why such problems don't "fit" with the "structure of NNs" with precise lower/upper bounds. Anything that works, and especially everything that doesn't work, must have an explanation. God doesn't play dice.
  - Houshalter 9y ago
    Maybe there's a reason. But I don't think you will ever be able to "prove" it. In any kind of formal way that would be satisfying to mathematicians. Solomonoff induction is the best attempt to try to formalize machine learning. And in theory any machine learning algorithm that works, works because it approximates Solomonoff induction somehow. But proving anything approximates Solomonoff induction is absurdly difficult or impossible. Because it's incomputable and involves the search space of all possible computer programs.

hyperpallium 9y ago

> I felt that at the point you are understanding the problem, you may just be better off with a direct approach I formed a similar impression in my PhD research.

hyperpallium 9y ago
Not that relevant, but wanted to elaborate a little: I exhaustively solved a toy version of my problem on a cluster, but found no discernable gradients. Good solutions were isolated spikes, with no elevations adjacent that could lead to them. So, random sampling would be as good as you'd get. The thing to do is change the problem, transform the space/dimensions, so better solutions were spatially proximate. But then, I'd be solving the problem. Another approach is to have the computer do this, seach the space of search spaces. But this higher-level space is even less likely to have informative gradients. OTOH, the data was in terms of a language, which would have introduced its own artefacts. A better search space would compensate for those, and might have been easy to find.

diyseguy 9y ago

I don't understand why A.I. can't be explainable. Can't they just add logging every time it makes a decision and then trace through the trail of decisions to the final result?

abhgh 9y ago
The AI that is not explainable is not because it cannot log things, its because the semantic interpretation of what it can log is hard. Starting with the real world input (which we understand) a lot of algorithms progressively apply mathematical transformations till reaching the output. It is the real world "meanings"of these transformations, or what is eventually learned: the stack of these transformations - that is hard to grasp.
Maybestring 9y ago
If you are willing to accept that as an explanation. Yes, it's easily explainable. A big list of anonymous decisions is easy. Naming those decisions is hard.

jmmcd 9y ago

I think you've confused genetic algorithms with genetic programming. They're not the same thing. > I don't know how Genetic Algorithms/programming could be made 'explainable' as to why they achieved an optimal solution other than hand-waving to how evolution works in nature. This is quite confused. You're comparing different levels of the systems. In neural networks, we would like to know why a numerical model (which has been optimised by gradient descent) gives the outputs it gives. In GAs, (1) the objects being created usually aren't numerical models -- think instead of solutions to TSPs; (2) the reason the object is good is rather easy to see -- one just has to look at the objective function and verify that that the object has the desired properties; (3) we don't really care what other objects were considered during the search process.

randomsearch 9y ago
> (2) the reason the object is good is rather easy to see -- one just has to look at the objective function and verify that that the object has the desired properties; Minor point: whether the result of evolution is easy to understand or not depends on the representation (encoding). Even GA results can be difficult to understand if they describe complex objects. In the case of GP, bloat (rapid increase in average program size in your population) can make results very difficult to interpret.

cabalamat 9y ago

> I don't know how Genetic Algorithms/programming could be made 'explainable' as to why they achieved an optimal solution other than hand-waving to how evolution works in nature. With either GA or ANN, you don't know that the algorithm has achieved the optimal solution and I would be surprised if you could ever prove that in the general case. What you can know is that your algorithm performs well, e.g. by testing how well it plays go or drives a car or recognises faces, or whatever.

sdubois 9y ago

I pretty much agree with what you said, but DL (and even more deep reinforcement learning) is really computationally expensive

tripzilch 9y ago

Another reason is for most demos and examples of Genetic Algorithms, that Simulated Annealing is almost always more optimal. Let me first say that I'm not certain this is the case for the purposes lined out in the article, because I'm not entirely sure what they're trying to do. Unless you have a crossover operator that really makes sense for your fitness function and problem, a GA is basically nothing but a bunch of SA processes running in parallel. In that case you would prefer SA, because it has less hyperparameters to tune, convergence is better defined, and there are proven methods to tune the hyperparameters. It's not that hard if you have a working GA optimizer, to test how well it does with SA as a baseline, because the algorithms are fairly similar. Unfortunately not many demos do this baseline comparison and I'm pretty sure most of them won't do significantly better with GAs.