4 ms·

Indeed, the old local maxima problem. Why doesn't evolution get stuck in local maxima; what pushes it out of those valleys and into the mountains? Why have al

Indeed, the old local maxima problem. Why doesn't evolution get stuck in local maxima; what pushes it out of those valleys and into the mountains? Why have all our evolution simulations gotten stuck? Luckily machine learning came along and has shown empirically that the solution is to increase the number of dimensions. Our tiny neural nets of the 90s also got stuck in local maxima. But when we could finally make huge and deep networks, the problem more or less disappeared. I believe this is the real solution to the local maxima problem in evolution. Real evolution works with a massive number of parameters, which means exploration of the problem space doesn't get stuck in local maxima, just as it doesn't in Deep Learning. When the number of tweakable parameters outstrips the dimensionality of the problem space then there is always some angle pointing up out of the valleys. This is a different, and I think more general way of expressing the typical counterargument which you explained. "There is always some angle pointing up" is a more general way of saying "just one mutation is usually enough to create a functional prototype".

fiatjaf 11y ago
I don't understand the comparison with the neural nets of the 90s and deep learning today. There was _human intelligence_ operating on the transition between these two technologies. How does evolution compare to this? (honest question, because I probably didn't get the angle and problem space thing)
- pyre 11y ago
  It sounds like @fpgaminer is saying that when humans created something similar (the neural nets of the 90's) it had issues (local maxima) until we increased the complexity (the number of variables that the system could/did respond to) in a way that started approaching the complexity of evolution.
  - fiatjaf 11y ago
    Thank you.
- hiddencost 11y ago
  It's not about the design of the network, it's about the training. Optimizing the weights of a DNN is a non convex optimization problem solved using gradient based search for weights that minimize a loss function. If you can only search in 10 dimensions, it's harder to move in the correct direction. Once you're searching in 1000 directions, you can usually find a path that gets you to the right place. Think of it this way: there may exist a 10 dimensional solution, but it requires learning a very dense solution.
  - fiatjaf 11y ago
    Ok, that made sense.
- Dylan16807 11y ago
  The question is not about how we got from old neural nets to new neural nets. The question is about how a search works within old neural nets, vs. how a search works within new neural nets.
- Retric 11y ago
  The single largest difference is simply the size of the networks. We are tossing billions of times more processing power at the same problems you see progress by simply change some constants. PS: Of course there are also software / algorithm changes, but often same problem 1,000,000,000x the processing power just works.
hyperbovine 11y ago
> Luckily machine learning came along and has shown empirically that the solution is to increase the number of dimensions. Ah yes, that's just what brilliant scientists like Mendel, Darwin, Fisher, Wright, Watson et al. were missing: Deep Learning! /s. The number of local optima grows exponentially in problem dimension, so increasing the dimension simply provides an even stronger guarantee that your optimizer will converge to one. Evolution, for its part, is definitely stuck in one, as evidenced by the fact that I cannot fly.
- jdmichal 11y ago
  > The number of local optima grows exponentially in problem dimension, so increasing the dimension simply provides an even stronger guarantee that your optimizer will converge to one. Forgive my potential ignorance, but it seems to me that there's a difference between the dimensionality of a problem and the dimensionality of a neural net working on the problem. Did you mean to imply that adding more dimensions to a neural net increases the number of local maxima for the problem? > Evolution, for its part, is definitely stuck in one, as evidenced by the fact that I cannot fly. Flying requires a large number of biological tweaks that are not necessarily good for every organism. For instance, lower bone density. When humans have this, we call it osteoporosis and it's generally a Bad Thing(tm). Also, I could argue that evolution has done a better job than you give it credit for, considering that I don't know any other animal that can travel over land at sustained high speeds, fly at extreme altitude, swim to extreme depths, and burrow through mountains.
- hiddencost 11y ago
  Your statement is true-ish, but not true enough. It is true there are more local minima, but they're generally pretty equivalent. In fact, in high dimensions, saddle points are a much bigger problem than local minima. [0] The fact that optimization works on these large, non-convex problems is kind of a marvel, and raises really interesting questions. (mostly "this shouldn't work this well unless there's some kind of regularity to these problems that makes them nicely behaved"). What this says about evolution I neither know nor care to speculate (above my pay grade). [0] http://arxiv.org/abs/1406.2572 http://arxiv.org/abs/1406.2572 Yes, the backpropaganda can get annoying.
stordoff 11y ago
> Why doesn't evolution get stuck in local maxima Is there any compelling reason to believe evolution _doesn't_ get stuck in local optima? It's not my field, so may be missing something obvious, but I see no reason that evolution requires complete avoidance of local optima. Different species could be the result of being "pulled" towards to different local optima. Local optima could disrupt evolution but, over time, a single large enough mutation or large enough change in external environment will either push you out of that optima, or stop it from being an optima.
- adevine 11y ago
  Evolution most certainly DOES get stuck in local maxima: http://m.youtube.com/watch?v=cO1a1Ek-HD0 http://m.youtube.com/watch?v=cO1a1Ek-HD0 . Also, it's quite easy for me to imagine an animal like an angel, with arms and wings. Tetrapods only have 4 limbs to work with though. For bats to gain wings they had to lose their front legs.
- GFK_of_xmaspast 11y ago
  One obvious local sticking point is mammalian cervical vertebrae (a couple critters have more or fewer, but basically you're stuck at 7 whether you're a rat or giraffe)
- roywiggins 11y ago
  Cephalopod eyes are better than mammalian ones. They evolved independently, but cephalopods ended up with an arguably "better" solution, and mammals aren't about to swap their eyes around entirely given that their eyes work just fine, even with a blindspot. https://en.wikipedia.org/wiki/Cephalopod_eye https://en.wikipedia.org/wiki/Cephalopod_eye > In vertebrate eyes, the nerve fibers route before the retina, blocking some light and creating a blind spot where the fibers pass through the retina. In cephalopod eyes, the nerve fibers route behind the retina, and do not block light or disrupt the retina.
hexagonc 11y ago
I think a simpler explanation for why evolution doesn't get stuck in local maxima is because the environment on earth hasn't been static. Resources get depleted, animals migrate to different habitats, mass extinctions occur, competitors enter and leave, etc. All of these change the balance of which genes aid survival at any given time and make a mutation that might have bad at one point good and vice versa.

fiatjaf 11y ago

I don't understand the comparison with the neural nets of the 90s and deep learning today. There was _human intelligence_ operating on the transition between these two technologies. How does evolution compare to this? (honest question, because I probably didn't get the angle and problem space thing)

pyre 11y ago
It sounds like @fpgaminer is saying that when humans created something similar (the neural nets of the 90's) it had issues (local maxima) until we increased the complexity (the number of variables that the system could/did respond to) in a way that started approaching the complexity of evolution.
- fiatjaf 11y ago
  Thank you.
hiddencost 11y ago
It's not about the design of the network, it's about the training. Optimizing the weights of a DNN is a non convex optimization problem solved using gradient based search for weights that minimize a loss function. If you can only search in 10 dimensions, it's harder to move in the correct direction. Once you're searching in 1000 directions, you can usually find a path that gets you to the right place. Think of it this way: there may exist a 10 dimensional solution, but it requires learning a very dense solution.
- fiatjaf 11y ago
  Ok, that made sense.
Dylan16807 11y ago
The question is not about how we got from old neural nets to new neural nets. The question is about how a search works within old neural nets, vs. how a search works within new neural nets.
Retric 11y ago
The single largest difference is simply the size of the networks. We are tossing billions of times more processing power at the same problems you see progress by simply change some constants. PS: Of course there are also software / algorithm changes, but often same problem 1,000,000,000x the processing power just works.

hyperbovine 11y ago

> Luckily machine learning came along and has shown empirically that the solution is to increase the number of dimensions. Ah yes, that's just what brilliant scientists like Mendel, Darwin, Fisher, Wright, Watson et al. were missing: Deep Learning! /s. The number of local optima grows exponentially in problem dimension, so increasing the dimension simply provides an even stronger guarantee that your optimizer will converge to one. Evolution, for its part, is definitely stuck in one, as evidenced by the fact that I cannot fly.

jdmichal 11y ago
> The number of local optima grows exponentially in problem dimension, so increasing the dimension simply provides an even stronger guarantee that your optimizer will converge to one. Forgive my potential ignorance, but it seems to me that there's a difference between the dimensionality of a problem and the dimensionality of a neural net working on the problem. Did you mean to imply that adding more dimensions to a neural net increases the number of local maxima for the problem? > Evolution, for its part, is definitely stuck in one, as evidenced by the fact that I cannot fly. Flying requires a large number of biological tweaks that are not necessarily good for every organism. For instance, lower bone density. When humans have this, we call it osteoporosis and it's generally a Bad Thing(tm). Also, I could argue that evolution has done a better job than you give it credit for, considering that I don't know any other animal that can travel over land at sustained high speeds, fly at extreme altitude, swim to extreme depths, and burrow through mountains.
hiddencost 11y ago
Your statement is true-ish, but not true enough. It is true there are more local minima, but they're generally pretty equivalent. In fact, in high dimensions, saddle points are a much bigger problem than local minima. [0] The fact that optimization works on these large, non-convex problems is kind of a marvel, and raises really interesting questions. (mostly "this shouldn't work this well unless there's some kind of regularity to these problems that makes them nicely behaved"). What this says about evolution I neither know nor care to speculate (above my pay grade). [0] http://arxiv.org/abs/1406.2572 http://arxiv.org/abs/1406.2572 Yes, the backpropaganda can get annoying.

stordoff 11y ago

> Why doesn't evolution get stuck in local maxima Is there any compelling reason to believe evolution _doesn't_ get stuck in local optima? It's not my field, so may be missing something obvious, but I see no reason that evolution requires complete avoidance of local optima. Different species could be the result of being "pulled" towards to different local optima. Local optima could disrupt evolution but, over time, a single large enough mutation or large enough change in external environment will either push you out of that optima, or stop it from being an optima.

adevine 11y ago
Evolution most certainly DOES get stuck in local maxima: http://m.youtube.com/watch?v=cO1a1Ek-HD0 http://m.youtube.com/watch?v=cO1a1Ek-HD0 . Also, it's quite easy for me to imagine an animal like an angel, with arms and wings. Tetrapods only have 4 limbs to work with though. For bats to gain wings they had to lose their front legs.
GFK_of_xmaspast 11y ago
One obvious local sticking point is mammalian cervical vertebrae (a couple critters have more or fewer, but basically you're stuck at 7 whether you're a rat or giraffe)
roywiggins 11y ago
Cephalopod eyes are better than mammalian ones. They evolved independently, but cephalopods ended up with an arguably "better" solution, and mammals aren't about to swap their eyes around entirely given that their eyes work just fine, even with a blindspot. https://en.wikipedia.org/wiki/Cephalopod_eye https://en.wikipedia.org/wiki/Cephalopod_eye > In vertebrate eyes, the nerve fibers route before the retina, blocking some light and creating a blind spot where the fibers pass through the retina. In cephalopod eyes, the nerve fibers route behind the retina, and do not block light or disrupt the retina.

hexagonc 11y ago

I think a simpler explanation for why evolution doesn't get stuck in local maxima is because the environment on earth hasn't been static. Resources get depleted, animals migrate to different habitats, mass extinctions occur, competitors enter and leave, etc. All of these change the balance of which genes aid survival at any given time and make a mutation that might have bad at one point good and vice versa.