Image 01

21st Century AI

A blog about achieving meaningful Artificial Intelligence

Posts Tagged ‘algorithm’

Learning without Supervision (Part 2): Objects & Attributes

Tuesday, June 21st, 2011

As I mentioned in my previous posting, I’m reading the Dalai Lama’s My Spiritual Journey. Actually, I’m reading it for the second time and I will probably read it again at least once more. It’s not hard to understand. It’s well written. Ninety percent of what the Dalai Lama writes I understand perfectly and I agree with completely. What throws me for a loop is when he writes, “Phenomena, which manifest to our faculties of perception, have no ultimate reality.”

Is the Dalai Lama speaking metaphorically? I don’t think so; though apparently there are two schools of Buddhist thought on the subject of reality (see here).

This is especially confusing for me because I am a scientist. There are days that I have a hard time believing this, myself, but I’ve hung my diplomas in my office so whenever I have a moment of self-doubt I can gaze at the expensively framed certificates. The signatures look real. I doubt if the President of the Board of Regents signs the undergrad degrees but his signature on my doctorate looks pretty legit.

My doctoral research, and the research that I do now, involves unsupervised machine learning (UML) and it is very much tied to reality; or at least our perceptions of reality. Curiously, the early research in what would become UML was conducted by psychologists who were interested in visual perception and how the human brain categorizes perceived objects.

So, let’s proceed as if this universe and everything in it are objects that can be described. Our perceptions may be completely wrong – they may have no ultimate reality – but I know the technique of unsupervised machine learning works; at least in this illusion that we call ‘reality’.

For a machine to make intelligent decisions about the world it has to understand the world. It has to grok the world.

Key concept: The world is made up of objects. Objects are described by attributes.

Therefore, the world can be described and the world can be understood within the context of a previously observed similar situation(s). In essence, the machine says, “I can categorize this new situation. I have seen something similar (or many similar things) before. I can put this new situation in the context of previously observed things. This is what happened previously. These are the things that I need to be aware of. This is what I need to look at now.”

So, let’s talk about objects and attributes.

Let’s start by selecting some random object on our desk. Okay, a coffee cup. What attributes can we use to describe the coffee cup object? Well, it’s a cylinder, closed at one end and open at the other and it has height and a radius and weight and a handle. It also has a cartoon on it. It also has some fruit juice in it. So we can describe the object with these attributes. However, some of these attributes are very important while others (the fact that the coffee cup contains fruit juice or that it has a cartoon on it) are irrelevant to the object being a coffee cup.

Now let’s look at some other random objects on my desk. I’ve got five plastic paper clip containers on it. They are also cylinders, closed at one end and open at the other, but none of them have handles. Also on my desk there are a couple of cylinders closed at both ends that are plastic barrels of Juicy Fruit gum.

So, if we were to take these eight objects found on my desk (yes, I have a very large desk) and start ‘feeding’ them into our machine we would end up with three ‘clusters’ of objects: one cluster would contain five objects described as cylinders, closed at one end and open on one end, one cluster would contain two objects described as cylinders closed at both ends and one cluster would contain one object described as a cylinder closed at one end, open at the other end and with a handle.

Now I just went and got a cup of coffee and put it on my desk. The machine asks itself (and we’ll get into how this is done in the next installment) does this new object belong with the paper clip holders? No, it has a handle. Does it belong with the Juicy Fruit gum barrels? No, one end of the cylinder is open and it has a handle. The machine then compares it with the other ‘coffee cup’ object and sees that they’re very similar and places the new object with the previously observed and categorized coffee cup. Voilà!

How does the machine ‘see’ where to place new objects? It involves a category utility function and this will be the subject of the next blog post.

How do you know which attributes are important for classification and which are irrelevant (like the cartoon on the coffee cup)? This involves humans; specifically Subject Matter Experts (SMEs). In my doctoral research I showed that it is crucial to include SMEs throughout the development process. We conduct blind surveys with SMEs to determine:

  1. If there is a consensus among the SMEs that specific objects can be defined by specific attributes.
  2. What those attributes are.
  3. To validate algorithms that return ‘real world values’ that describe these attributes.
  4. To validate the machine’s output.

A three handled cup called a 'tug'. The Greeks called 3 handled cups 'hydras'.

Algorithms that describe attributes must return ‘real world values’ which is just a fancy way of saying numbers with a decimal point. For example, an algorithm that returns a value for ‘number of closed ends of a cylinder’ would return either 0, 1.0 or 2.0. And an algorithm that returns a value for ‘number of handles’ would return 0, 1.0, 2.0, 3.0… What, you say, a three handled cup? Yup, such beasts exist (see picture at the right).

Okay, the next episode involves some math. So first have a lie down and think cool thoughts until the panic subsides.

 

Pathfinding, Academia and the Real World

Thursday, July 15th, 2010

“When game developers look at AI research, they find little work on the problems that interest them, such as nontrivial pathfinding, simple resource management and strategic decision-making, bot control, behavior-scripting languages, and variable levels of skill and personality — all using minimal processing and memory resources. Game developers are looking for example “gems”: AI code that they can use or adapt to their specific problems. Unfortunately, most AI research systems are big hunks of code that require a significant investment of time to understand and use effectively.”
- John Laird, “Bridging the Gap Between Developers & Researchers”

Pathfinding is a least-weighted path graph problem. There, I said it.

My plan for this blog was to keep it at a fairly high level of abstraction and not to use terms that would scare away computer game designers who, for the most part, feel about math the way vampires feel about garlic (or silver or crosses depending on which particular form of vampire fiction you’re reading this week). But, yeah, pathfinding (which is an important part of RPGs, wargames and even sports games) can be reduced to well researched and well understood mathematical problem.

Computer game designers (or programmers) usually work in a grid; that is to say their world (or battlefield, or playing field) can be represented by a two-dimensional matrix. Though we often think of a graph as a tree-like object, a two-dimensional matrix in which every cell is connected to its neighbors (e.g. a battlefield, RPG world, football field, etc.), can also be represented as a graph.

So, as a computer game programmer, why do we care that RPG worlds can be represented as a graph? Well, it turns out that there is an algorithm that can be mathematically proven to return the shortest path between two points in a graph. Now, if you’re not a computer game programmer you’re probably saying, “well, if they’ve got this whole shortest path thing worked out, why is that half the time in a game when I tell my player to go from Point A to Point B it gets stuck behind a wall or a rock or something trapped like a doofus?”  And the answer to that is: because the programmer didn’t use a guaranteed least weighted path algorithm.

The reason that we refer to this type of an algorithm as a “least weighted path” algorithm is because we can give a ‘weight’ representing the ‘cost’ of moving from one cell (or square) to the next cell (or square). For example, we might say that moving ‘north’ through ‘clear’ terrain costs 1, and moving northeast through a swamp costs 3 and moving east through a forest costs 2, etc. So we’re not really talking about a ‘fastest’ path or a ‘shortest’ path, but, technically, the path with the lowest ‘movement costs’ or weight. Does that make sense? If it doesn’t, drop me an email and I’ll explain it, hopefully more clearly, in another post.

And now let’s look at the reasons why the programmer didn’t use a guaranteed least weighted path algorithm:

  1. Speed. The oldest guaranteed least weighted path algorithm is commonly known as Dijkstra’s algorithm. It was first discovered by Edsger Dijkstra in 1959 and there is a very good explanation of how it works (complete with animation) here. Dijkstra’s algorithm is taught in every undergrad AI class. It’s not very complicated and it’s easy to implement (in fact, it’s usually an assignment by the middle of the semester). So if the “fastest path from Point A to Point B in a computer game” problem has been solved why doesn’t everybody use Dijkstra’s algorithm? Good question. The reason that computer game programmers don’t use Dijkstra’s algorithm is that it is an “exhaustive search” (which means that it has to look at every possible path) and then determines the fastest route. In other words, it’s sloooooow. Really, really slow.
  2. Time. I’m not talking game development time – though often the problem is simply that the game publisher is forcing the game ‘out the door’ before it’s really completed – I mean ‘clock cycles’ or there isn’t enough time for the computer to both render all these polygons that represent explosions and mountains and whatever and for the computer to do AI calculations. AI is constantly getting short shrift when the CPU budget is being determined.
  3. Ignorance. There’s another solution to the “least weighted path problem” known as A*; pronounced ‘A star’ (I once had the temerity to ask Nils Nilsson, one of the authors of A* what the ‘A’ stood for and he replied, “algorithm;” and now we all know).  Thankfully, Amit Patel has done a great job of explaining A* (with lots of graphics) here, so I don’t have to. Again, I’m not going to get into the math behind A* but I am going to leave you with this mind-blowing statement, “the guaranteed worst-case runtime of A* is the best-case runtime of Dijkstra’s algorithm.” What did he just say? That Dijkstra’s algorithm will never return a least weighted path in less time than A*. So, you should be asking, “well, why doesn’t everybody  use A* instead of Dijkstra’s algorithm?” The answer, as crazy as this sounds is, A* is rarely, if ever, taught in academia. What?!?!? Yeah, there is a weird prejudice against it because Dijkstra solved the problem way back in ’59, it is a mathematically proven solution, so why bother with anything else?

You see in Academia, especially in computer science which is usually a department inside the division of mathematical science, RAM and runtime are often thought of as ‘infinite’ commodities. I suspect that this way of thinking about problems stems, in part, from Turing’s theoretical machine which had infinite RAM (an infinite strip of paper) and an infinite amount of time to solve a problem. Unfortunately, those of us that live and work in the ‘Real World’ have neither infinite RAM or time. We need algorithms that return solutions fast.

Lastly I would like to mention  Dimdal’s work on optimizing A* in “Real World Terrain” situations. I wrote a paper about it which is available here. I use a modified version of Dimdal’s modification of Nilsson’s A* for my own pathfinding routines in TIGER. The result is an extremely fast least weighted path algorithm that takes a fraction of the time to calculate as Dijkstra’s algorithm or A*.

And now you know the difference between academia and the real world and why your character in an RPG gets stuck behind a bunch of rocks acting like a doofus.