Sunday, December 05, 2010

Bid "A" Little "i" - Part II

In Part I I gave what I hope was a convincing argument for why software developers should care about Ai. In this article I will show how looking at problems from an Ai perspective can yield immediate benefits. I will then introduce the fundamental tenet of Ai, the red thread that ties all the approaches I will discuss (and indeed those I will not) together. 

It is Good to Talk

A seemingly obvious but rather useful thing that Ai does for us as software developers is it equips us with ways of thinking about thought and ways of talking about thought. By giving the techniques and algorithms we use names, it makes it easier to reason about them and to discuss them. The discussion or communication aspect should be familiar to most software developers as it is widely considered one the major benefits of Design Patterns, it is similarly beneficial in Ai.

An example of a rather simple algorithm that has been given a name in Ai is: Generate and Test. Lets say your task is to recognise a specific make and models of cars given a set of features, what would you do? Well, you could build yourself the Rube Goldberg machine below.

So what does this device do? The Generator flips through all the pages of the popular car buyers and sellers magazine Autotrader, it offers the cars on each page as possibilities to the Tester. The Tester takes each possibility from the Generator and checks its features to determine if it matches the type of car being searched for. Cars that don't match are discarded and the Tester moves on to the next possibility, once a match is found it presented as the result of the computation, if all the pages are exhausted but still no match is found no result is returned.

Why glorify such as simple computation with a name? As we eluded to earlier it allows us to answer concisely questions like: "How are you going to solve this problem?". We can now answer: "I am going to solve this problem using Generate and Test". Even more importantly we can now talk precisely about the properties of the Generator and the Tester.

Interesting properties of the Tester include:
  •  Accuracy: Do we require 100% accuracy or would 99% accuracy suffice? A Bayesian mathematician would tell you that 99% accuracy is is definitely not good enough!
  •  Speed: A tester that contemplates each possibility for too long may not find a solution in a reasonable amount of time.
Desirable properties of the Generator are:
  • Complete: If there exists a car in the world we would like our generator to produce it. By this measure our choice of using the Autotrader magazine might have been a bad one since it is unlikely that all possible cars types are always for sale in this magazine.
  • Inform-able: If I am looking for a small hatchback it does not make sense to offer a van as a possibility to the tester, it would be nice if we could tell the generator that.
  • Non-Redundant: We do not want the same car offered as a possibility more than once, as could happen if our page turner went through pages at random rather than in sequence.
While it is helpful to be able to think and talk about ideas more freely, that is of course not the end of the story. Indeed it is but a single ice crystal on the tip of the iceberg, meant only to illustrate that you do not need to go far down the Ai road to get some real value.

Framing Problems

One of the most important things human beings do in problem solving is framing questions in a way that makes them easier to solve. We are all aware of this intuitively from phrases like: "looking at it from another point of view I realised...". My thesis is that the ability to frame problems appropriately is the basis for intelligence and indeed genius. Problem framing is at the heart of most of the topics that I am going to cover over the next few posts. I would argue that one of the biggest problems for Artificial General Intelligence (which as you may remember from Part I is about artificial agents comparable to, or smarter than humans) is that our algorithms are not very good at framing problems for themselves. A human being has to frame the problem then the computer can do its thing. This limitation places an upper bound on how intelligent an artificial agent can be.

This limitation is however perfectly acceptable for the masquerade of intelligence that I am interested in here. For our purposes we need to make the concept of problem framing more concrete, hence heretofore I will refer to Representations instead. To show how choosing the right representation is key to solving problems in general and in particular to conditioning problems for solution by a computer another example is order.

Most children have seen the puzzle of the farmer, the fox, the goose and the grain. All four are on one side of a river and the farmer wants to get all of them to the other side of the river (I always wondered why the farmer was ferrying a fox around). However the fox if left alone with the goose will eat it, the goose if left alone with the grain will eat it. A child would probably solve the problem relatively quickly by trial and error. What we need to do though is condition the problem for solving by a computer, we need a representation:

This representation looks promising as it makes explicit which side of the river everyone is on, lets see if we can use it to make progress with the puzzle. We did not mention it earlier but to get across the river the farmer must take the other across in a boat that has only room for two. What happens if our robot farmer takes whatever happens to be nearest to him across the river, in this case that is the fox:

This didn't work out too well, the goose was left unattended to feast on the grain - game over, we lost. Even though we lost the game, the representation has exposed an important constraint that might be obvious to us humans but must be explicitly stated for an Ai farmer, things that eat each other cannot be on the same side of the river without the farmer also being there. Our representation is serving us well so far, it has exposed constraints that we can exploit to solve the problem. The constraint shows which state transitions are valid and which ones are not:

There is really not much left for us to do to fully program our robot farmer. The problem can now be solved as a series of valid transitions between states involving the farmer moving from one side of the river to another. Once an appropriate representation has been chosen it is often a mechanical process to get to the solution, standard computer science algorithms (searching, sorting, finite state machines an so on) exploiting the constraints exposed are all that is required to take us the rest of the way.

It may seem like overkill to solve this rather simple puzzle which could be expressed in a few "if-else" statements in the manner we have but it is not! Take another look at what we have done, we have taken the puzzle and generalized it into a good representation and the constraints the representation exposes. This means we can solve any puzzle of this nature without any change to the code. Even if we change the entire cast, just by adding the knowledge of who eats who, that new puzzle is automatically solved.

An even more important point to note is that the person programming the farmer robot does not need to be able to solve the puzzle. They solve the problem at a different level, I doubt for example that any of the engineers that worked on Deep Blue were chess grandmasters. This is not such a big win for a simple puzzle like this, however there are problems which human beings cannot solve because of the time it would take, the errors a human would introduce, the amounts of data that need to be processed or host of other reasons. Hence Ai gives us the ability to solve problems that would otherwise be impossible to tackle!

We have seen how to get some quick wins out of Ai thinking and introduced the central concept of representations (as well as the ancillary concept of constraints). Having set the scene in Part I and given a technical introduction to Ai in this article the coming instalments will cover the main classical Ai techniques.