Friday, October 18, 2013

Salute Your Solution Space

Last weekend I went to an SF writing convention at which the esteemed George R. R. Martin himself was guest of honor. I had a good time, managed to snag an autograph, and even got conclusive proof that he is, in fact, working on The Winds of Winter. (He read 2 chapters.) So my blog post for today is inspired by the convention visit, but has nothing to do with science fiction, writing, or ASOIAF.

The most interesting panel at the convention, personally, wasn’t even a panel at all. It was a talk given by computer scientist Dr. Alice Armstrong on artificial intelligence and how to incorporate AI into stories without pissing off people like Dr. Alice Armstrong. It was an amusing and informative talk, although not as many people laughed at her jokes as should have. A couple points she made resonated particularly well with me, not because of my fiction, but because of my math courses the past two semesters.

Specifically, about a quarter of her talk was given over to the concept of genetic algorithms, in which a whole bunch of possible solutions to a problem are tested, mutated, combined, and tested again until a suitable solution is found. This is supposed to mirror the concept of biological evolution, however Dr. Armstrong pointed out numerous times that the similarities are, at this point, rather superficial.

But one thing she said is that genetic algorithms are essentially search engines. They go through an infinite landscape of possible solutions—the solution space—and come out with one that will work. This reminded me of a topic covered in linear algebra, and one we’re covering again from a different perspective in differential equations. The solution space in differential equations is a set of solutions arrived at by finding the eigenvectors of a system of linear differential equations.

Bluh, what? First, let’s talk about differential equations. Physics is rife with differential equations—equations that describe how systems change—because physics is all about motion. What kind of motion? Motion like, for example, a cat falling from up high. As we all know, cats tend to land on their feet. They start up high and maybe upside down, they twist around in the air, and by the time they reach the ground they’re feet down (unless buttered toast is involved).

If you could describe this mathematically, you’d need an equation that deals with lots of change, like, say, a differential equation. In fact, you might even need a system of differential equations, because you have to keep track of the cat’s shape, position, speed, and probably a few other variables.

Going back to linear algebra for a moment, you can perform some matrix operations on this system of differential equations to produce what are called eigenvectors. It’s not really important what eigenvectors are, except to know that they form the basis for the solution space.

To explain what a basis is, I’m going to steal from Dr. Armstrong for a moment. The example she gave of a genetic algorithm at work was one in which a “population” of cookie recipes are baked, and the more successful recipes pass on their “genes” to the next generation. A gene, in this sense, is the individual components of the recipe: sugar, flour, chocolate chips, etc.

You have some number of cups of sugar, add that onto some number of cups of flour, add that onto some number of cups of chocolate chips, and so on, and you have a cookie recipe. These linear combinations of ingredients—different numbers of cups—can be used to form a vast set of cookie recipes, a solution space of cookie recipes, if you will. So a basis is the core ingredients with which you can build an infinite variety of a particular item.

Let’s get back to our cat example. If you take a system of linear differential equations about falling cats and find their eigenvectors, then you will have a basis for the solution space of cat falling. That is, you will know an infinite number of ways that a cat can fall, given some initial conditions. But what ways of falling are better than others? That’s where genetic algorithms come in.

In our case, a genetic algorithm is what produced the cat righting reflex. You see, as we discovered, there are an infinite number of ways for a cat to fall. (While there are an infinite number of solutions, infinity is not everything. For example, there are an infinite number of numbers between 0 and 1, but the numbers between 0 and 1 are not all the numbers. Similarly, there are ways in which you can arrange the equations of cat falling that don’t produce meaningful results, like a cat falling up, so these aren’t a part of the infinite solution space.)

It would take a very long time to search through an infinite number of cat falling techniques to find the best one. Genetic algorithms, then, take a population of cats, have a lot of them fall, and see which ones fall better than others. This is, of course, natural selection. Now, you may think of evolution as a slow process, but it’s important to remember that this genetic algorithm is not just testing the fitness of cat falling, but of every other way in which a cat could possibly die. From that standpoint, evolution has done an absolutely remarkable job of creating an organism that can survive in a great many situations.

If you don’t believe me, consider that there is a Wikipedia page dedicated to the “falling cat problem” which, among other things, compares the mathematics of falling cats to the mathematics of quantum chromodynamics (which I don’t understand a lick of, btw).

Some of you may be wondering how what is essentially a search algorithm can be considered a form of “artificial intelligence.” Well, to answer that question, you have to give a good definition of what intelligence really is. But this blog post is probably long enough already, so I’m not going down that road. Consider for a moment, however, that there is a certain segment of the population that is absolutely convinced life originated via intelligent design. While their opinion on this matter is almost always bound up in belief, it’s not hard to look at nature and see something intelligent. If nothing else, nature produced humans, and it’s difficult to imagine any definition of intelligence that doesn’t include us (despite our occasional idiocy).

One final note: I lied in the beginning. I think Solution Space would make an excellent title for an SF story, so there’s your connection to science fiction and writing. And don’t steal my title, Mr. Martin.

No comments:

Post a Comment