ARN

AI technology comes of age

"Stair, please fetch the stapler from the lab," says the man seated at a conference room table. The Stanford Artificial Intelligence Robot, standing nearby, replies in a nasal monotone, "I will get the stapler for you."

Stair pivots and wheels into the adjacent lab, avoiding a number of obstacles on the way. Its stereoscopic camera eyes swivel back and forth, taking in the contents of the room. It seems to think for a moment, then approaches a table for a closer look at an oblong metallic object. Its articulated arm reaches out, swivels here and there, and then gently picks up the stapler with long, rubber-clad fingers. It heads back to the conference room.

"Here is your stapler," says Stair, handing it to the man. "Have a nice day."

These are indeed nice days for artificial intelligence researchers. While Stair's performance might not seem much better than that of a dog fetching the newspaper, it's a technological tour de force unimaginable just a few years ago.

Indeed, Stair represents a new wave of AI, one that integrates learning, vision, navigation, manipulation, planning, reasoning, speech and natural-language processing. It also marks a transition of AI from narrow, carefully defined domains to real-world situations in which systems learn to deal with complex data and adapt to uncertainty.

AI has more or less followed the "hype cycle" popularized by Gartner: Technologies perk along in the shadows for a few years, then burst on the scene in a blaze of hype. Then they fall into disrepute when they fail to deliver on extravagant promises, until they eventually rise to a level of solid accomplishment and acceptance.

AI has its roots in the late 1950s but came to prominence in the "expert systems" of the 1980s. In those systems, experts -- chess champions, for example -- were interviewed, and their rules of logic were hard-coded in software: If Condition A occurs, then do X. But if Condition B occurs, then do Y. While they worked reasonably well for specialized tasks such as playing chess, they were "fragile," says Eric Horvitz, an AI researcher at Microsoft Research.

"They focused on capturing chunks of human knowledge, and then the idea was to assemble those chunks into reasoning systems that would have the expertise of people," Horvitz says. But they couldn't "scale," or adapt, to conditions that had not explicitly been anticipated by programmers.

Today, AI systems can perform useful work in "a very large and complex world," Horvitz says. "Because these small [software] agents don't have a complete representation of the world, they are uncertain about their actions. So they learn to understand the probabilities of various things happening, they learn the preferences [of users] and costs of outcomes and, perhaps most important, they becoming self-aware."

These abilities derive from something called machine learning, which is at the heart of many modern AI applications. In essence, a programmer starts with a crude model of the problem he's trying to solve but builds in the ability for the software to adapt and improve with experience. Speech recognition software gets better as it learns the nuances of your voice, for example, and over time Amazon.com more accurately predicts your preferences as you shop online.

Page Break

It's All About the Data

Machine learning is enabled by clever algorithms, of course, but what has driven it to prominence in recent years is the availability of huge amounts of data, both from the Internet and, more recently, from a proliferation of physical sensors. Carlos Guestrin, an assistant professor of computer science and machine learning at Carnegie Mellon University, combines sensors, machine learning and optimization to make sense of large amounts of complex data.

For example, he says, scientists at the University of California, Los Angeles, put sensors on robotic boats to detect and analyze destructive algae blooms in waterways. AI algorithms learned to predict the location and growth of the algae. Similarly, researchers at Carnegie Mellon put sensors in a local water-distribution system to detect and predict the spread of contaminants. In both cases, machine learning enabled better predictions over time, while optimization algorithms identified the best sites for the expensive sensors.

Guestrin is also working on a system that can search a huge number of blogs and identify those few that should be read by a given user every day based on that user's browsing history and preferences. He says it may sound completely different from the task of predicting the spread of contaminants via sensors, but it's not.

"Contaminants spreading through the water distribution system are basically like stories spreading through the Web," he says. "We are able to use the same kind of modeling ideas and algorithms to solve both problems."

Guestrin says the importance of AI-enabled tools like the blog filter may take on importance far beyond their ability to save us a few minutes a day. "We are making decisions about our lives -- who we to elect, and what issues we find important -- based on very limited information. We don't have time to make the kind of analyses that we need to make informed decisions. As the amount of information increases, our ability to make good decisions may actually decrease. Machine learning and AI can help."

Microsoft Research has combined sensors, machine learning and analysis of human behavior in a road traffic prediction model. Predicting traffic bottlenecks would seem to be an obvious and not very difficult application of sensors and computer forecasting. But MSR realized that most drivers hardly need to be warned that the interstate heading out of town will be jammed at 5pm on Monday. What they really need to know is where and when anomalies, or "surprises," are occurring and, perhaps more important, where they will occur.

So MSR built a "surprise forecasting" model that learns from traffic history to predict surprises 30 minutes in advance based on actual traffic flows captured by sensors. In tests, it has been able to predict about 50% of the surprises on roads in the Seattle area, and it is in use now by several thousand drivers who receive alerts on their Windows Mobile devices.

Page Break

Few organizations need to make sense of as much data as search engine companies do. For example, if a user searches Google for "toy car" and then clicks on a Wal-Mart ad that appears at the top of the results, what's that worth to Wal-Mart, and how much should Google charge for that click? The answers lie in an AI specialty that employs "digital trading agents," which companies like Wal-Mart and Google use in automated online auctions.

Michael Wellman, a University of Michigan professor and an expert in these markets, explains: "There are millions of keywords, and one advertiser may be interested in hundreds or thousands of them. They have to monitor the prices of the keywords and decide how to allocate their budget, and it's too hard for Google or Yahoo to figure out what a certain keyword is worth. They let the market decide that through an auction process."

When the "toy car" query is submitted, in a fraction of a second Google looks up which advertisers are interested in those keywords, then looks at their bids and decides whose ads to display and where to put them on the page. "The problem I'm especially interested in," Wellman says, "is how should an advertiser decide which keywords to bid on, how much to bid and how to learn over time -- based on how effective their ads are -- how much competition there is for each keyword."

The best of these models also incorporate mechanisms for predicting prices in the face of uncertainty, he says. Clearly, none of the parties can hope to optimize the financial result from each transaction, but they can improve their returns over time by applying machine learning to real-time pricing and bidding.

Brainy Studies

One might expect AI research to start with studies of how the human brain works. But most AI advances have come from computer science, not biology or cognitive science.

These fields have sometimes shared ideas, but their collaboration has been at best a "loose coupling," says Tom Mitchell, a computer scientist and head of the Machine Learning Department at Carnegie Mellon University. "Most of the progress in AI has come from good engineering ideas, not because we see how the brain does it and then mimic that."

But now that's changing, he says. "Suddenly, we have ways of observing what the brain is really doing, via brain imaging methods like functional MRI. It's a way to look into the brain while you are thinking and see, once a second, a movie of your brain's activity with a resolution of 1mm."

Page Break

So, cognitive science and computer science are now poised to share ideas as they never could before, he says. For example, certain AI algorithms send a robot a little reward signal when it does the right thing and a penalty signal when it makes a mistake. Over time, these have a cumulative effect, and the robot learns and improves.

Mitchell says researchers have found with functional MRIs that regions of the brain behave exactly as predicted by these "reinforcement learning" algorithms. "AI is actually helping us develop models for understanding what might be happening in our brains," he says.

Mitchell and his colleagues have been examining the neural activity revealed by brain imaging to decipher how the brain represents knowledge. To train their computer model, they presented human subjects with a list of 60 nouns -- such as telephone, house, tomato and arm -- and observed the brain images that each produced. Then, using a trillion-word text database from Google, they determined the verbs that tend to appear with the 60 base words -- ring with telephone , for example -- and they weighted those words according to the frequency of both occurring.

The resulting model was able to accurately predict the brain image that would result from a word for which no image had ever before been observed. Oversimplifying, the model would, for example, predict that the noun airplane would produce a brain image more like that for train than for tomato .

"We were interested in how the brain represents ideas," Mitchell says, "and this experiment could shed light on a question AI has had a lot of trouble with: What is a good, general-purpose representation of knowledge?" There may be other lessons as well. Noting that the brain is also capable of forgetting, he asks, "Is that a feature or a bug?"

Andrew Ng, an assistant professor of computer science at Stanford University, led the development of the multitalented Stair. He says the robot is evidence that many previously separate fields within AI are now mature enough to be integrated "to fulfill the grand AI dream."

And just what is that dream? "Early on, there were famous predictions that within a relatively short time computers would be as intelligent as people," he says. "We still hope that some time in the future computers will be as intelligent as we are, but it's not a problem we'll solve in 10 years. It may take over 100 years."