Image 01

21st Century AI

A blog about achieving meaningful Artificial Intelligence

Archive for the ‘Unsupervised Machine Learning’ Category

Quoted in the NY Times

Thursday, May 10th, 2012

We were recently quoted in an article in the New York Times about unsupervised machine learning and the Office of Naval Research’s program on intuition.

In addition to enhanced military training, researchers also want to use the new program to develop enhanced technology. Ezra Sidran, a computer scientist, said he planned to apply for the naval research funding to investigate “unsupervised machine learning,” in which a computer program independently “analyzes, remembers and learns.”

“When Pandora suggests a song for you or when Amazon suggests a book for you,” Mr. Sidran said, “this is an example of supervised machine learning” because “you, albeit unknowingly, are supervising the learning of the machine” with each book or song selection.

“In unsupervised machine learning,” he explained, “the program looks at all the unsorted data and – without any human intervention – clusters the data into separate categories.” After that sorting process, experts can then identify “these clusters as places an I.E.D. is likely to be hidden or places where an ambush is likely to occur.”

The complete article can be read here: U.S. Navy Program to Study How Troops Use Intuition.

MATE (Machine Analysis of Tactical Environments)

Sunday, October 30th, 2011

MATEI’ve been working on this project since about 2003 (you could reasonably argue that I actually started development in 1985 when I began work on UMS: The Universal Military Simulator) and I’m finally in a position to share some of this work with the world at large. TIGER (for Tactical Inference GenERator) was my doctoral research project and it was funded, in part, by a DARPA (Defense Advanced Research Project Agency) ‘seedling-grant’.

After I received my doctorate, DARPA funded my research on computational military reasoning. Since DARPA was already funding a project called TIGR (Tactical Ground Reporting System) my TIGER was renamed MATE.

MATE was created to quickly arrive at an optimal tactical solution for any scenario (battlefield snapshot) that is presented to the program. It also designed to facilitate quickly entering unit data (such as location, strength, morale, etc.) via a point and click graphical user interface. (GUI). There are three main sections to MATE’s decision making process:

  1. Analysis of the terrain and opposing forces (REDFOR and BLUFOR) location on the terrain. This includes the ability to recognize certain important tactical situations such as ‘anchored’ or ‘unanchored flanks’, ‘interior lines of communication’, ‘restricted avenues of attack’, ‘restricted avenues of retreat’ and the slope of attack.
  2. Ability to implement the five canonical offensive maneuvers: turning maneuver, envelopment, infiltration, penetration and frontal assault. This includes the ability to determine flanking goals, objectives and optimal route planning (including avoiding enemy line of sight and enemy fire).
  3. Unsupervised Machine Learning which allows MATE to classify the current tactical situation within the context of previously observed situations (including historically critiqued battles).

I wished to test MATE with an actual tactical situation that occurred recently in either Afghanistan or Iraq. Even though my research was supported by DARPA I did not have access to recent ‘after action’ reports. However, when I saw the HBO documentary, “The Battle for Marjah,” I realized that enough information was presented to test MATE.

The clip, below, from the HBO documentary, shows the tactical situation faced by Bravo Company, 1/6 Marines February 13, 2010:

It took only a few seconds to enter RED and BLUE unit locations to MATE (the map was downloaded from Google Earth):

The Battle for Marjah as shown on MATE (actual screen capture).

Screen capture of MATE showing the Battle for Marjah tactical situation. Click on image to see full-size.

After clicking on the ‘Calculate AI’ icon, the ‘Analyze and Classify Current Situation’ button and the, ‘Generate HTML Output and Launch Browser’ button, MATE’s analysis of the tactical situation was displayed. Total elapsed time was less than 10 seconds (on a Windows XP system, or 5 seconds on a Windows 7 system).

MATE then automatically generated HTML pages of its recommendations including graphically displaying optimal paths for an envelopment maneuver that encircled enemy positions:

MATE output for Envelopment Maneuver COA.

MATE output for Envelopment Maneuver COA. Click on image to see full-size.

MATE automatically produced HTML pages of its analysis and optimal course of action (COA) routes and instructions and launched the default browser on the computer.

To see the actual HTML output of MATE’s analysis of, “The Battle for Marjah” situation click here (opens in a new window).

For more information about MATE contact sidran [at] RiverviewAI.com.

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.

 

Learning Without Supervision (Part 1)

Tuesday, August 10th, 2010

When I was a kid I read about Summerhill School (the book seems to be out of print but see here and here) and I was extraordinarily impressed. I think to some extent that a lot of the trouble that I had in school was because I wanted the stodgy elementary and high school that I attended to be more like this wonderful Summerhill were students were just encouraged to learn on their own, without supervision if they chose. I’ve never been much of a fan of rules so perhaps it shouldn’t be much of a surprise that when I began my doctoral research in AI I was more interested in ‘unsupervised machine learning’ rather than ‘case based’ (rules) reasoning.

One of these things...

Cookie Monster explains Unsupervised Machine Learning and Clustering

Unsupervised Machine Learning (specifically ‘clustering’ which is the form of machine learning that interests me) to quote Wikipedia, “is a class of problems in which one seeks to determine how the data are organized.” That’s a pretty succinct description of the subject, but there isn’t much more information on the page. Unsupervised Machine Learning (okay, I’m getting tired of typing this mouthful, so henceforth it will be ‘UML’) first appeared in 1980s and was an outgrowth of psychology. At its core UML is not that different from the old Sesame Street song (“One of these things isn’t like the other…“).

Let’s look at Cookie Monster’s data set: he has four plates, three of the plates contain two cookies and one plate contains three cookies. Technically we would say that Cookie Monster’s data can be clustered using certain object attributes. In this case, the only significant object attribute for clustering is the number of cookies. So, Cookie Monster’s data set of four objects (plates) and nine cookies would (should) be divided into two clusters: one cluster containing three plates each with two cookies and one cluster of one plate with three cookies.

Obviously, this is an extremely simple problem involving just four objects and only one attribute that is found in all objects. But, hopefully, you can see how this is a very powerful concept. Instead of separating plates of cookies into clusters (or groups) imagine separating battlefields into similar tactical situations (my doctoral research), or 3D topographical data into likely places to drill for oil, or find diamonds, or situations in a baseball game when it’s a good idea to send in a substitute runner, or…

Okay, that’s the general idea for UML; in the next episode we’ll push on and explain how we will accomplish clustering. Warning: there will be a little math involved.