5 ms·

As a researcher studying evolutionary algorithms, one thing these algorithms are quite adept at is finding holes in the objective functions you give to them. Th

by jal278 12y ago

As a researcher studying evolutionary algorithms, one thing these algorithms are quite adept at is finding holes in the objective functions you give to them. They are like automated lawyers seeking loopholes. You want to evolve a controller for a robot that walks far, it will find exploits in the physics engine that defy gravity or somehow catapult the robot through the air (this sort of exploit is the bane of those doing research in virtual creatures [1]). You want to evolve a talented player for an atari game like beamrider, and evolution will find an infinite score-loop exploit [2]. It's meeting the letter of the law in maximizing your measure, but it's missing the forest for the trees. This kind of problem has led some in the community to look at driving evolution by other means -- e.g. my dissertation was on evolving neural network controls for robots by choosing the most novel behaviors instead of those that performed the best by the fitness measure [3]. [1] https://archive.org/details/sims_evolved_virtual_creatures_1994 https://archive.org/details/sims_evolved_virtual_creatures_1... [2] http://www.cs.utexas.edu/users/ai-lab/?atari http://www.cs.utexas.edu/users/ai-lab/?atari [3] http://eplex.cs.ucf.edu/noveltysearch/userspage/ http://eplex.cs.ucf.edu/noveltysearch/userspage/

acadien 12y ago
That sounds like over fitting. It happens with all optimization routines, is the EA somehow special in this regard?
- jal278 12y ago
  Overfitting is when your model is over-fit to the data you are training on [1], but what we're talking about here is slightly different -- the EA has maximized the given objective function correctly, but it turns out that your objective function is corruptible: A high value on your simple measure doesn't match the intuition motivating it. You had something particular in mind when you set the objective function for your biped robot to be distance travelled before it falls. Finding an exploit in the underlying physics engine that allows the biped to explode and travel quite far -- while indeed excelling at the function, is far from what you had in mind. Yet it does reveal a vulnerability in your physics engine, which while unexpected, may be valuable in its own right, as the application the post's author argues. This isn't entirely unique to EAs -- but it seems to happen more frequently in the kinds of domains EAs are often applied to -- complex simulations where the gradient of an objective function is difficult or impossible to calculate. [1] http://en.wikipedia.org/wiki/Overfitting http://en.wikipedia.org/wiki/Overfitting
  - tlarkworthy 12y ago
    It happens in EA because the researchers don't account for over fitting. The experimenters often do not validate so the population converges to the training set maxima too far. If you had 2 simulations of walking. You would select and mutate based on one sim and stop the evolution when performance degraded on the second sim. Not blindly maximize the one measure. if validation were performed the population would not evolve into the cracks of unlikely physics loop holes.
  - darkmighty 12y ago
    I think he had something else in mind, somewhat related to overfitting -- you're maximizing (too much) a metric over an unrealistic solution space, and that solution when applied to a real solution space won't behave as intended. So those are "overfitting" for the exact quirks of the engine. I agree, it's a stretch, but not unlike in ML, it shows that optimizing too much will show quirks if your 'objective function/simulation' pair is not exactly equal to the 'desired objective function/reality', or if there is an innumerable ensemble of situations you might expect the solution to behave well.
jacquesm 12y ago
> They are like automated lawyers seeking loopholes. That means we're getting there. This sounds like any toddler that I've ever met!
Houshalter 12y ago
Very related: Conjuring An Evolution To Serve You: http://lesswrong.com/lw/l8/conjuring_an_evolution_to_serve_you/ http://lesswrong.com/lw/l8/conjuring_an_evolution_to_serve_y...

by jal278 12y ago

acadien 12y ago

That sounds like over fitting. It happens with all optimization routines, is the EA somehow special in this regard?

jal278 12y ago
Overfitting is when your model is over-fit to the data you are training on [1], but what we're talking about here is slightly different -- the EA has maximized the given objective function correctly, but it turns out that your objective function is corruptible: A high value on your simple measure doesn't match the intuition motivating it. You had something particular in mind when you set the objective function for your biped robot to be distance travelled before it falls. Finding an exploit in the underlying physics engine that allows the biped to explode and travel quite far -- while indeed excelling at the function, is far from what you had in mind. Yet it does reveal a vulnerability in your physics engine, which while unexpected, may be valuable in its own right, as the application the post's author argues. This isn't entirely unique to EAs -- but it seems to happen more frequently in the kinds of domains EAs are often applied to -- complex simulations where the gradient of an objective function is difficult or impossible to calculate. [1] http://en.wikipedia.org/wiki/Overfitting http://en.wikipedia.org/wiki/Overfitting
- tlarkworthy 12y ago
  It happens in EA because the researchers don't account for over fitting. The experimenters often do not validate so the population converges to the training set maxima too far. If you had 2 simulations of walking. You would select and mutate based on one sim and stop the evolution when performance degraded on the second sim. Not blindly maximize the one measure. if validation were performed the population would not evolve into the cracks of unlikely physics loop holes.
- darkmighty 12y ago
  I think he had something else in mind, somewhat related to overfitting -- you're maximizing (too much) a metric over an unrealistic solution space, and that solution when applied to a real solution space won't behave as intended. So those are "overfitting" for the exact quirks of the engine. I agree, it's a stretch, but not unlike in ML, it shows that optimizing too much will show quirks if your 'objective function/simulation' pair is not exactly equal to the 'desired objective function/reality', or if there is an innumerable ensemble of situations you might expect the solution to behave well.

jacquesm 12y ago

> They are like automated lawyers seeking loopholes. That means we're getting there. This sounds like any toddler that I've ever met!

Houshalter 12y ago

Very related: Conjuring An Evolution To Serve You: http://lesswrong.com/lw/l8/conjuring_an_evolution_to_serve_you/ http://lesswrong.com/lw/l8/conjuring_an_evolution_to_serve_y...