Later On

A blog written for those whose interests more or less match mine.

Evolution is an effective method: Computers Evolve a New Path Toward Human Intelligence

leave a comment »

Matthew Hutson writes in Quanta:

In 2007, Kenneth Stanley, a computer scientist at the University of Central Florida, was playing with Picbreeder, a website he and his students had created, when an alien became a race car and changed his life. On Picbreeder, users would see an array of 15 similar images, composed of geometric shapes or swirly patterns, all variations on a theme. On occasion, some might resemble a real object, like a butterfly or a face. Users were asked to select one, and they typically clicked on whatever they found most interesting. Once they did, a new set of images, all variations on their choice, would populate the screen. From this playful exploration, a catalog of fanciful designs emerged.

Stanley is a pioneer in a field of artificial intelligence called neuroevolution, which co-opts the principles of biological evolution to design smarter algorithms. With Picbreeder, each image was the output of a computational system similar to a neural network. When an image spawned, its underlying network mutated into 15 slightly different variations, each of which contributed a new image. Stanley didn’t intend for Picbreeder to generate anything in particular. He merely had a hunch that he, or the public, might learn something about evolution, or about artificial intelligence.

One day Stanley spotted something resembling an alien face on the site and began evolving it, selecting a child and grandchild and so on. By chance, the round eyes moved lower and began to resemble the wheels of a car. Stanley went with it and evolved a spiffy-looking sports car. He kept thinking about the fact that if he had started trying to evolve a car from scratch, instead of from an alien, he might never have done it, and he wondered what that implied about attacking problems directly. “It had a huge impact on my whole life,” he said. He looked at other interesting images that had emerged on Picbreeder, traced their lineages, and realized that nearly all of them had evolved by way of something that looked completely different. “Once I saw the evidence for that, I was just blown away.”

Stanley’s realization led to what he calls the steppingstone principle — and, with it, a way of designing algorithms that more fully embraces the endlessly creative potential of biological evolution.

Evolutionary algorithms have been around for a long time. Traditionally, they’ve been used to solve specific problems. In each generation, the solutions that perform best on some metric — the ability to control a two-legged robot, say — are selected and produce offspring. While these algorithms have seen some successes, they can be more computationally intensive than other approaches such as “deep learning,” which has exploded in popularity in recent years.

The steppingstone principle goes beyond traditional evolutionary approaches. Instead of optimizing for a specific goal, it embraces creative exploration of all possible solutions. By doing so, it has paid off with groundbreaking results. Earlier this year, one system based on the steppingstone principle mastered two video games that had stumped popular machine learning methods. And in a paper published last week in Nature, DeepMind — the artificial intelligence company that pioneered the use of deep learning for problems such as the game of Go — reported success in combining deep learning with the evolution of a diverse population of solutions.

The steppingstone’s potential can be seen by analogy with biological evolution. In nature, the tree of life has no overarching goal, and features used for one function might find themselves enlisted for something completely different. Feathers, for example, likely evolved for insulation and only later became handy for flight.

Biological evolution is also the only system to produce human intelligence, which is the ultimate dream of many AI researchers. Because of biology’s track record, Stanley and others have come to believe that if we want algorithms that can navigate the physical and social world as easily as we can — or better! — we need to imitate nature’s tactics. Instead of hard-coding the rules of reasoning, or having computers learn to score highly on specific performance metrics, they argue, we must let a population of solutions blossom. Make them prioritize novelty or interestingness instead of the ability to walk or talk. They may discover an indirect path, a set of steppingstones, and wind up walking and talking better than if they’d sought those skills directly.

New, Interesting, Diverse

After Picbreeder, Stanley set out to demonstrate that neuroevolution could overcome the most obvious argument against it: “If I run an algorithm that’s creative to such an extent that I’m not sure what it will produce,” he said, “it’s very interesting from a research perspective, but it’s a harder sell commercially.”

He hoped to show that by simply following ideas in interesting directions, algorithms could not only produce a diversity of results, but solve problems. More audaciously, he aimed to show that completely ignoring an objective can get you there faster than pursuing it. He did this through an approach called novelty search.

The system started with a neural network, which is an arrangement of small computing elements called neurons connected in layers. The output of one layer of neurons gets passed to the next layer via connections that have various “weights.” In a simple example, input data such as an image might be fed into the neural network. As the information from the image gets passed from layer to layer, the network extracts increasingly abstract information about its contents. Eventually, a final layer calculates the highest-level information: a label for the image.

In neuroevolution, you start by assigning random values to the weights between layers. This randomness means the network won’t be very good at its job. But from this sorry state, you then create a set of random mutations — offspring neural networks with slightly different weights — and evaluate their abilities. You keep the best ones, produce more offspring, and repeat. (More advanced neuroevolution strategies will also introduce mutations in the number and arrangement of neurons and connections.) Neuroevolution is a meta-algorithm, an algorithm for designing algorithms. And eventually, the algorithms get pretty good at their job.

To test the steppingstone principle, Stanley and his student Joel Lehman tweaked the selection process. Instead of selecting the networks that performed best on a task, novelty search selected them for how different they were from the ones with behaviors most similar to theirs. (In Picbreeder, people rewarded interestingness. Here, as a proxy for interestingness, novelty search rewarded novelty.)

In one test, they placed virtual wheeled robots in a maze and evolved the algorithms controlling them, hoping one would find a path to the exit. They ran the evolution from scratch 40 times. A comparison program, in which robots were selected for how close (as the crow flies) they came to the exit, evolved a winning robot only 3 out of 40 times. Novelty search, which completely ignored how close each bot was to the exit, succeeded 39 times. It worked because the bots managed to avoid dead ends. Rather than facing the exit and beating their heads against the wall, they explored unfamiliar territory, found workarounds, and won by accident. “Novelty search is important because it turned everything on its head,” said Julian Togelius, a computer scientist at New York University, “and basically asked what happens when we don’t have an objective.”

Once Stanley had made his point that the pursuit of objectives can be a hindrance to reaching those objectives, he looked for clever ways to combine novelty search and specific goals. That led him and Lehman to create a system that mirrors nature’s evolutionary niches. In this approach, algorithms compete only against others that are similar to them. Just as worms don’t compete with whales, the system maintains separate algorithmic niches from which a variety of promising approaches can emerge.

Such evolutionary algorithms with localized competition have shown proficiency at processing pixels, controlling a robot arm, and (as depicted on the cover of Nature) helping a six-legged robot quickly adapt its gait after losing a limb, the way an animal would. A key element of these algorithms is that they foster steppingstones. Instead of constantly prioritizing one overall best solution, they maintain a diverse set of vibrant niches, any one of which could contribute a winner. And the best solution might descend from a lineage that has hopped between niches.

Evolved to Win

For Stanley, who is now at Uber AI Labs, the steppingstone principle explains innovation: If you went back in time with a modern computer and told people developing vacuum tubes to abandon them and focus on laptops, we’d have neither. It also explains evolution: We evolved from flatworms, which were not especially intelligent but did have bilateral symmetry. “It’s totally unclear that the discovery of bilateral symmetry had anything to do with intelligence, let alone with Shakespeare,” Stanley said, “but it does.”

Neuroevolution itself has followed an unexpectedly circuitous path over the past decade. For a long time, it has lived in the shadows of other forms of AI.

One of its biggest drawbacks, according to Risto Miikkulainen, a computer scientist at the University of Texas, Austin (and Stanley’s former doctoral adviser), is  . . .

Continue reading.

Written by LeisureGuy

6 November 2019 at 3:48 pm

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.